Scheduling Mixed-Criticality Systems on Varying-Speed Processors: A Meta-Reinforcement Learning Approach for Non-Preemptive Tasks

Abstract

Mixed-Criticality (MC) systems have to guarantee the timely execution of high-criticality tasks even under adversarial processor conditions. Prior work addresses preemptive scheduling, leaving, the NP hard, non-preemptive scheduling problem unexplored.

This paper presents a novel Meta-Reinforcement Learning (Meta-RL) framework that acts as an adaptive scheduler selector in offline, non-preemptive MC scheduling on processors that are subject to stochastic degradation. Our work develops a pretrained RL-based scheduler that is capable of handling adversarial workloads, where classical algorithms, such as Earliest Deadline First (EDF), would fail and then integrate this RL scheduler into a meta-agent that is able to select between Earliest Deadline First (EDF) and the RL scheduler based on workload characteristics.

Key Contributions of our work:

• We introduce a novel Meta-RL environment in which a meta-agent learns to choose between EDF and an RL scheduler, combining their complementary strengths.
• We propose a reinforcement learning-based scheduler to address an NP-hard challenge that remains largely unaddressed in existing literature.
• We conduct comprehensive experiments using realistically inspired workloads across 1,000,000+ instances to thoroughly evaluate the effectiveness of our approach, demonstrating that the Meta-RL framework achieves higher criticality than EDF in the presence of adversarial instances.