Product Design, Manufacturing & Innovation Resources
家 » 速率单调调度(RMS)

速率单调调度(RMS)

1973
  • C. L. Liu
  • James Layland
Computer workstation in a control room analyzing Rate-Monotonic Scheduling for real-time systems.

(图片仅供参考)

速率单调调度(RMS)是一种用于实时系统中周期性任务的静态优先级调度算法。它根据任务频率分配优先级:任务周期越短(速率越高),优先级越高。RMS 是一种最优静态优先级算法,这意味着如果任何静态优先级算法能够调度一组任务,RMS 也能够调度。可以通过基于利用率的测试来检验其可调度性。 Traveling salesman problem applications also include sequencing jobs, a combinatorial task related to real-time scheduling. Scheduling theory, like the linear programming developed by Dantzig, aims for the best use of limited resources.

速率单调调度(RMS)是实时系统理论的基石,由刘和莱兰在1973年的一篇开创性论文中提出。它提供了一种简单而强大的方法,用于在单个处理器上调度一组独立的、可抢占的周期性任务。其核心原则是为每个任务分配一个与其周期成反比的固定优先级。例如,每10毫秒运行一次的任务的优先级高于每100毫秒运行一次的任务。

RMS 的意义在于其最优性以及存在一个简单的可调度性测试。它已被证明是一种最优的静态优先级调度策略。这意味着,如果一组任务可以被任何静态优先级算法调度,那么它们也可以被 RMS 调度。可以使用利用率界限测试来确定 RMS 下任务集的可调度性。对于一组 n 个任务,总处理器利用率 U 是每个任务 i 的执行时间 C_i 除以周期 T_i 的总和:U = sum_{i=1}^{n} frac{C_i}{T_i}[/latex]。 Liu 和 Layland 证明,如果总利用率小于或等于特定界限 U ≤ n(2^{1/n}-1),则任务集保证可调度(即不会错过截止时间)。当 n 趋于无穷大时,该界限收敛于 ln(2) ≈ 0.693。这提供了可调度性的充分条件,但并非必要条件。还可以使用更精确但更复杂的测试方法,称为精确分析或响应时间分析。

UNESCO Nomenclature: 1203
– Computer science

类型

Software/Algorithm

中断

Incremental

用法

广泛使用

前体

  • 排队论
  • 运筹学
  • 计算机调度算法的早期研究
  • 分时操作系统的开发

应用程序

  • 卫星控制系统
  • 汽车控制应用
  • 航空电子设备和 flight control 系统
  • 工业自动化和机器人技术
  • 即时的 信号处理

专利:

NA

潜在创新理念

  • 混合关键性系统的可调度性分析器
  • 能够调整任务速率的节能调度算法
  • 面向多核实时系统的分区调度
  • 人工智能应用中执行时间可变的任务的自适应均方根误差
  • 时间敏感网络 (TSN) 交换机中的网络数据包调度
  • 实时云计算的资源预留协议
  • 大规模分布式实时系统的组合分析框架
  • 针对执行时间不确定的系统的概率可调度性分析
  • 安全感知调度可防止基于时间的侧信道攻击
  • 在单个处理器上协同调度实时任务和非实时应用程序
相关内容:速率单调调度、RMS、实时系统、调度算法、静态优先级、周期性任务、可调度性分析、利用率界限、Liu 和 Layland、最优调度。

历史背景

速率单调调度(RMS)

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(如果日期未知或不相关,例如“流体力学”,则提供其显著出现的近似估计)

第十年 周年纪念日

只有注册会员才能免费获取完整尺寸的图片和下载内容。

> 登录 <