首页 / 算法 / 关于处理周期任务的调度算法
关于处理周期任务的调度算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了关于处理周期任务的调度算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6731字，纯文字阅读大概需要10分钟。
内容图文
关于处理周期任务的调度算法
- 单调速率调度算法（Rate Monotonic）
- 最早时限优先调度算法（Earliest Deadline First）
- 时限单调调度算法（Deadline Monotonic）
- 最小空闲时间优先调度算法（Least-Slack-Time-First）
- 小结
最近在跟着专业老师做一个关于多核系统节能问题的项目，其中涉及到了能耗与可靠性方面的问题，此类问题都是基于实时周期任务展开，与调度策略相关。对于处理周期任务的调度问题，其中有几类较为经典的算法（速率单调静态优先级DM算法、最早时限优先调度动态优先级算法、最小空闲时间/松弛时间优先算法、时限单调调度算法）。由于部分算法只能在相关论文中找到，所以在这里汇总出来，作为自己的学习笔记。
单调速率调度算法（Rate Monotonic）
单调速率（RM）调度算法采用抢占的、静态优先级的策略，调度周期性任务。其中心思想为：有一被调度任务集S，对于周期T最短的任务，其任务优先级P最高，即优先级与周期成反比。当较低优先级的进程正在运行且较高优先级的进程可以运行时，较高优先级进程会抢占低优先级。
并且RM算法具有以下限制条件：
1.所有具有硬时限的任务均为周期任务，且周期等于时限。
2.所有具有硬时限的任务必须在其时限到来前结束。
3.所有具有硬时限的任务相互独立。
4.所有具有硬时限的任务均具有恒定的运行时间。
5.系统中所有非周期任务均为软实时任务，它们的执行超越死限对系统正常运行没有影响。
对此，我们进行举例说明。
假设有两进程P1与P2。P1与P2对应的周期分别为50与100，即ρ1 = 50，ρ2 = 100。P1与P2对应的处理时间分别为20与35，即t1 = 20，t2 = 35。每个周期的截止期限为下一个周期开始的时间点，即任务周期等于任务时限，在下一个周期到来之前完成任务CPU执行。
假设一种分配方案，P2优先级大于P1，执行情况如图1所示。
图1 当P2优先级高于P1时的任务调度
从图1可以得知，P2首先开始执行，且在t = 35时完成执行，之后P1开始执行，然后P1的任务处理时间t1 = 20，在t = 55时完成执行。P1的第一个截止期限在t = 50处，意味着此时P1已经错过了截止期限，然而P2的第一个截止期限在t = 100处，这就导致t ∈ [55, 100]区间内并无任务执行，大大降低了CPU的利用率。
假设另外一种分配方案，P1优先级大于P2，即单调速率调度（Rate Monotonic）算法（P1周期小于P2，故优先级更高）。
执行情况如图2所示。
图2 单调速率调度RM算法
从图2可以得知，P1首先开始执行，并在t = 20处完成执行（在第一个截止期限t = 50前完成），之后P2开始执行，并运行至t = 50处。此时，进入P1的第二个任务执行周期，为了满足P1的优先执行，P2被迫暂停任务，由P1接替。在t = 70处，P1完成执行，此时P2恢复执行，在t = 75时完成之前剩余的任务。从t = 75到t = 100之间，P1与P2无任务执行，系统一直空闲至t = 100，即进入P1的第三个任务执行周期与P2的第二个任务执行周期。
接着，我们更改P1与P2的参数，假设ρ1=50，t1=25，ρ2=80，t2=35。仍然按照单调速率算法为P1分配高优先级。两个进程的总 CPU 利用率为 (25/50)+(35/80)=0.94，因此似乎合乎逻辑的结论是：这两个进程可以被调度，并且仍让 CPU 有 6% 的可用时间。
执行情况如图3所示。
图3 错过截止期限的单调速率调度RM算法
从图3可以得知，P1首先开始执行，并在t = 25处完成执行（在第一个截止期限t = 50前完成），之后P2开始执行，并运行至t = 50处。此时，进入P1的第二个任务执行周期，为了满足P1的优先执行，P2被迫暂停任务，由P1接替。在t = 75处，P1完成执行，此时P2恢复执行，在t = 85时完成之前剩余的任务，但是却超过了t = 80的截止期限。
尽管是最优的，然而单调速率调度有一个限制，CPU 的利用率是有限的，并不总是可能完全最大化 CPU 资源。
对于具有一个进程的系统，CPU 利用率是 100%；但是当进程数量接近无穷时，它大约接近 69%。对于具有两个进程的系统，CPU 利用率是 83%。图 1 和图 2 调度的两个进程的组合利用率为 75%，因此单调速率调度算法保证能够调度它们。图 3 所示的两个进程的组合利用率为 94%，因此，单调速率调度不能保证它们可以调度以便满足它们的截止期限。
最早时限优先调度算法（Earliest Deadline First）
最早时限优先（EDF）调度算法根据截止期限动态分配优先级。其中心思想为：有一被调度任务集S，对于距离截止期限越近的任务，优先级越高，即优先级高低与截止期限早晚成反比。
我们仍然假设有两进程P1与P2，对应参数为ρ1=50，t1=25，ρ2=80，t2=35。执行情况如图4所示。
图4 最早时限优先调度EDF算法
进程P1的截止时限最早，所以P1的优先级大于P2。当P1执行完成后，P2开始执行。然而，对于RM算法，在t = 50时，P1应当抢占P2开始它的第二个周期任务，但是在EDF算法中，P2的下一个截止期限为t = 80，P1的下一个截止期限为t = 100，因此P2的优先级大于P1，P2继续执行。两者在各自第一个周期任务中均满足截止期限。
进程P1在t = 60时再次运行，在t = 85时完成第二个周期任务，也满足t = 100的第二个截止期限。此时P2开始执行，但是在t = 100时刻被P1抢占，原因是P1的下一个截止期限为t = 150，P2的下一个截止期限为t = 160，相比之下P1截止期限更早，P1优先级更高。
从该实例中可以看出，EDF算法是动态分配优先级，并且不要求进程应是周期的，也不要求进程的 CPU 执行的长度是固定的。只不过EDF算法必须已知任务的截止期限，以此来动态分配优先级。EDF 调度具有吸引力的地方是，它是理论上最佳的。从理论上说，它可以调度进程，使得每个进程都可以满足截止期限的要求并且 CPU 利用率将会是 100%。然而，在实际中，由于进程的上下文切换和中断处理的代价，这种级别的 CPU 利用率是不可能的。
时限单调调度算法（Deadline Monotonic）
时限单调调度算法是对RM算法的一种改进，它将RM调度的限制条件1更改为：所有被调度的任务均具有确定的时限和周期，且时限小于周期。其中心思想为：有一被调度任务集S，对于时限越小的任务，优先级越高，即优先级与时限成反比。
RM调度是静态最优实时调度算法，但是其对任务集的限制过于苛刻，在很大程度上限制了它在实际工程的应用。DM调度是对RM调度的进一步优化，它放款了任务时限必须等于周期的限制，但是其可调度条件计算复杂度很高，这也影响着它在实际中的应用。
最小空闲时间优先调度算法（Least-Slack-Time-First）
最小空闲时间优先（Least-Slack-Time-First）调度算法策略为结合任务执行的缓急程度来给任务分配优先级，任务所剩的空闲时间越少，就越需要尽快执行，这样保证了紧急任务（并非是截止期越早的任务）的优先执行。然而，由于等待执行任务（简称等待任务）的空闲时间是严格递减的，其等待执行的缓急程度也随时间越来越紧急，因此在系统执行过程中，等待任务随时可能会抢占当前执行的任务。LSF 算法造成任务之间的频繁切换或称为颠簸(thrashing)现象较为严重.颠簸现象增大了系统开销，并限制了 LSF 算法的应用。
LSF 调度策略按照任务的空闲时间的非降顺序动态地分配优先级，空闲时间越短,任务的优先级就越高，然后选择具有最小空闲时间的任务进行优先调度。空闲时间算法的意义在于，测量任务需要被调度的缓急程度。假设一个特定任务在变为活动任务时，处理器正被具有更高优先级的其他任务所占用，从而阻止了该任务接受调度处理.随着时间的推移，这个等待任务的空闲时间稳定地减小直至小于正占用 CPU 的任务的空闲时间时，按LSF 调度策略，处理器必须切换到调度执行该等待任务；当该等待任务的空闲时间减小到 0 时，意味着该任务在其截止期前刚好能够完成。此时，该任务需要立即抢占 CPU 资源以便在其截止期前完成，如果处理器在此关键时刻还不开始调度该任务，那么该任务的空闲时间将变成负值;当空闲时间为负时，意味着该任务不可能在其截止期前完成，此时，没有必要让空闲时间为负的任务占用 CPU 资源，以免造成 CPU 资源浪费。
小结
本文主要介绍了四种关于处理周期任务的调度算法，由于本人所学知识优先，大部分内容是从前人所提出或总结的观点中摘录或提炼所得，做一个抛砖引玉的作用吧。
参考文献或网址：
http://c.biancheng.net/view/1253.html
http://c.biancheng.net/view/1254.html
[1]陈宇,熊光泽.单调时限调度算法的可调度分析[J].计算机工程与应用,2001(23):19-21.
[2]金宏,王宏安,王强,戴国忠.改进的最小空闲时间优先调度算法[J].软件学报,2004(08):1116-1123.
内容总结
以上是互联网集市为您收集整理的关于处理周期任务的调度算法全部内容，希望文章能够帮你解决关于处理周期任务的调度算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。