Improving Mixed-Criticality Scheduling with Reinforcement Learning

📄 arXiv: 2504.03994v2 📥 PDF

作者: Muhammad El-Mahdy, Nourhan Sakr, Rodrigo Carrasco

分类: cs.LG, cs.AI, cs.MA, eess.SY

发布日期: 2025-04-04 (更新: 2025-04-08)

备注: This work was submitted to the 32nd International Conference on Real-Time Networks and Systems (RTNS) on June 8, 2024

💡 一句话要点

提出基于强化学习的混合关键性系统调度方法，提升任务完成率。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 混合关键性系统 实时调度 非抢占式调度 马尔可夫决策过程

📋 核心要点

  1. 现有混合关键性系统调度方法难以在复杂动态环境下实现高效调度，尤其是在非抢占式调度中。
  2. 论文将调度问题建模为马尔可夫决策过程，利用强化学习训练智能体，生成接近最优的调度策略。
  3. 实验表明，该方法显著提高了任务完成率，尤其是在高关键性任务上，验证了其有效性和可扩展性。

📝 摘要（中文）

本文提出了一种新颖的强化学习（RL）方法，用于在具有不同速度处理器的混合关键性（MC）系统上进行调度。在[1]的基础上，我们将他们的工作扩展到解决非抢占式调度问题，该问题已知是NP-hard问题。通过将此调度挑战建模为马尔可夫决策过程（MDP），我们开发了一个RL agent，能够为实时MC系统生成接近最优的调度方案。我们的基于RL的调度器在保持整体系统性能的同时，优先考虑高关键性任务。通过大量的实验，我们证明了我们方法的可扩展性和有效性。RL调度器显著提高了任务完成率，在100,000个合成数据和真实数据实例中，在不同的系统条件下，总体任务完成率达到约80%，高关键性任务完成率达到85%。此外，在没有性能下降的稳定条件下，调度器实现了94%的总体任务完成率和93%的高关键性任务完成率。这些结果突出了基于RL的调度器在实时和安全关键应用中的潜力，为处理复杂和动态的调度场景提供了显著的改进。

🔬 方法详解

问题定义：论文旨在解决混合关键性系统中非抢占式任务调度问题。现有方法在处理复杂和动态的调度场景时，难以保证高关键性任务的完成率，并且难以达到最优的调度方案。非抢占式调度问题本身是NP-hard问题，传统的启发式算法难以找到全局最优解。

核心思路：论文的核心思路是将调度问题建模成马尔可夫决策过程（MDP），利用强化学习算法训练一个智能体，使其能够学习到最优或接近最优的调度策略。通过奖励函数的设计，引导智能体优先完成高关键性任务，同时兼顾整体系统性能。

技术框架：整体框架包括以下几个主要模块：1) 环境建模：将混合关键性系统和调度过程建模为MDP，定义状态空间、动作空间和奖励函数。2) 智能体设计：选择合适的强化学习算法（具体算法未知），构建智能体。3) 训练过程：通过与环境的交互，不断优化智能体的策略。4) 调度执行：使用训练好的智能体进行实时调度。

关键创新：该方法将强化学习应用于混合关键性系统调度，能够自适应地学习最优调度策略，无需人工设计复杂的启发式规则。与传统方法相比，该方法能够更好地处理复杂和动态的调度场景，提高任务完成率。

关键设计：论文中关键的设计包括：1) 状态空间的设计，需要能够充分描述系统的状态，包括任务的到达时间、截止时间、关键性级别等。2) 动作空间的设计，定义智能体可以采取的调度动作。3) 奖励函数的设计，需要能够引导智能体优先完成高关键性任务，同时兼顾整体系统性能。具体的参数设置、损失函数、网络结构等技术细节未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该RL调度器在各种系统条件下显著提高了任务完成率。在100,000个合成数据和真实数据实例中，总体任务完成率达到约80%，高关键性任务完成率达到85%。在没有性能下降的稳定条件下，总体任务完成率达到94%，高关键性任务完成率达到93%。这些结果表明，该方法在实际应用中具有很大的潜力。

🎯 应用场景

该研究成果可应用于各种实时和安全关键系统，例如航空航天、自动驾驶、工业控制等领域。通过优化任务调度，可以提高系统的可靠性和安全性，降低系统故障的风险。未来，该方法可以进一步扩展到更复杂的调度场景，例如多处理器调度、分布式调度等。

📄 摘要（原文）

This paper introduces a novel reinforcement learning (RL) approach to scheduling mixed-criticality (MC) systems on processors with varying speeds. Building upon the foundation laid by [1], we extend their work to address the non-preemptive scheduling problem, which is known to be NP-hard. By modeling this scheduling challenge as a Markov Decision Process (MDP), we develop an RL agent capable of generating near-optimal schedules for real-time MC systems. Our RL-based scheduler prioritizes high-critical tasks while maintaining overall system performance. Through extensive experiments, we demonstrate the scalability and effectiveness of our approach. The RL scheduler significantly improves task completion rates, achieving around 80% overall and 85% for high-criticality tasks across 100,000 instances of synthetic data and real data under varying system conditions. Moreover, under stable conditions without degradation, the scheduler achieves 94% overall task completion and 93% for high-criticality tasks. These results highlight the potential of RL-based schedulers in real-time and safety-critical applications, offering substantial improvements in handling complex and dynamic scheduling scenarios.