一种实时进程调度算法的研究

郑坤

摘要：在实时系统中，进程调度算法性能的好坏直接对系统的实时性起着决定性的作用。因此，该文介绍实时调度和进程调度算法的相关定义，对常见的动态优先级调度算法和静态优先级调度算法的不足之处进行了解析。据此提出了一种基于优先级的动态分配策略（Dynamic allocation strategy based on priority）的进程调度算法。

关键词：实时操作系统；进程调度；调度算法

中图分类号：TP316 文献标识码：A 文章编号：1009-3044（2014）31-7310-03

在实时系统的使用中，我们应理解它的一些基本特点才能更好的应用它。在实时系统中，计算的正确性不仅依赖于程序运行的逻辑结果，还依赖于这个结果产生的时间，在逻辑上和时间上出现的任何偏差将对系统产生严重后果。实时系统主要分为两种类型：硬实时系统和软实时系统。在硬实时系统中，系统要确保进程有最坏情况下的处理时间，即对于各进程不仅要执行无误，并且响应时间的截止期限必须得到满足（即做到准时）。在软实时系统中，进程能够得到有确保的处理时间，能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误（即允许不准时）。实时系统的应用领域很广泛，计算机系统为了提供对于实时性的支持，其操作系统必须对 CPU 和其他资源进行有效的调度和管理。

1 实时系统调度算法

在多任务实时系统中，处理任务的最终目标是通过进程调度算法，在进程截止期前执行使尽可能多的进程，从而提高系统性能。然而，在处理时间有限的实时系统中对多个进程进行调度的决策是很困难的，因为该决策会涉及到大量的实时进程属性和实时系统相关参数。

多进程的系统必须担负起调度进程的责任，不断地进行切换进程，以使CPU获得最大的利用率。当有多个进程就绪时，操作系统必须决定先运行那一个，对CPU访问权限裁决的过程被称为调度（Scheduling）。本质上调度其实就是系统根据调度算法策略与资源控制协议的规则，为一组处于就绪状态的进程分配资源并选择符合系统要求的进程组成一个队列到处理机上去依次执行，并而在这一过程中要保证所有进程对时限的要求。假如实时系统若有m个周期性进程，进程i的周期为[Pi]，其中每个事件进程需要[Ci]秒的CPU时间来处理，则只有满足以下条件：[i=1mCiPi≤1]才可能处理所有负载。满足该条件的系统进程集认为是可调度的（Schedulable）。实时调度强调的是进程的时间约束，尤其是在硬实时系统的设计中，评价调度程序好坏与否不在于调度的公平性和最小响应时间，而是所有硬实时系统中进程能否在最后截止期限内完成。在实时调度过程中使用的调度策略方法或资源控制协议，通常我们称为实时调度算法。

2 常见的实时调度算法及其不足

实时系统必须保证在确定的时间内对事件进行处理，因此必须要有一个良好的进程调度算法，它具有如下特点：①公平；②高效；③响应及时；④利用率高[1]。显然，在任何一个操作系统中同时满足这几个目标是不太现实的，必须在这几个方面进行相应的取舍与折中考虑，从而确定自己的调度算法。目前在实时系统中常见的实时调度算法有单调速率调度算法（RMS），最早截止时间优先调度算法（EDF）等。还有一些在此基础上进行优化或者改进而成的算法，如截止期限单调调度算法（Deadline Monotonic Scheduling， DMS）、最短空闲时间优先调度算法（Least Laxity First， LLF）等。

1）速率单调调度算法

单调速率调度（RMS）算法是C. L. Liu和J. W. Layland在1973年提出的一种基于周期和多进程的静态优先级可抢占调度算法[2]。RMS是针对周期进程的优先级调度算法，当进程的截止时间等于其周期时，RMS算法已被证明是静态最优的调度算法。C. L. Liu和J . W. Layland给出了RMS算法可调度的充分非必要条件，[C0T0+C1T1+……+CnTn≤n（21n-1）]，其中C为进程，T为周期，n为进程个数。这种算法执行起来开销很小，可调度性测试简单，但最大的局限性就在于该算法不可能总使CPU被完全利用。在最差情况下可调度的范围为[Wn=n（21n-1）]。不难看出，当系统中只有一个进程运行时，最差的可调度范围为100%；当系统中有多个进程运行时，可调度范围逐渐降低，达到极限值69.3%左右。所以，当系统中的进程总量不超过[n（21n-1）]）时，RMS算法可以调度执行系统所有的进程并满足它们的时限要求。当系统超过此负载限制时，系统调度就有可能出现不能满足进程执行时限的现象。

2） 最早截止期限优先调度

最早截止期限优先调度算法（EDF） [3]是一种基于优先级的抢占式动态最优调度算法，也称为死限驱动调度算法（Deadline Driver Scheduling， DDS）。该算法的进程优先级初始之时并不固定，而是随着启动时间的变化而动态地改变，以距离最后截止期限时间的长短来分配优先级，具体地说就是距离最后截止期限时间越短的进程越紧急，相应的进程优先级也就越高；距离最后截止期限时间越长的进程对完成截止时间要求越松弛，该进程的优先级也就越低。系统每时每刻总是在就绪队列中挑选最早到达绝对最后截止期限的进程在处理机上执行。事实上，EDF算法是一种最优的单处理器调度算法，对于相对期限等于周期且总资源利用率不大于[n（21n-1）]的周期进程集，可由该算法进行调度。实践表明，EDF算法的优点在于系统负载较低时，效率较高，相对容易实现。缺点在于该算法理论上能对系统可调度负载进行优化，但不能解决系统负载较重时，系统性能急剧下降的问题。C. L. Liu和J. W. Layland给出了采用EDF算法可调度的充分必要条件，[C0T0+C1T1+……+CnTn≤1]，其中C为进程，T为周期，n为进程个数。由于EDF算法在运行时系统开销较大，特别是在过载情况下，由于大量进程错过最后截止期限引发CPU频繁的进程调度，消耗了大量的CPU时间，这时候系统的性能可能还不如先来先服务FIFO（First In First out）调度算法稳定。另外EDF算法在实际应用中可能会出现优先级倒置的现象，所以EDF算法在实际应用中还存在一些问题。

3）最短空闲时间优先调度

最短空闲时间优先调度算法（LLF）也叫最小松弛时间优先调度算法，是在EDF算法的基础之上发展起来的一种动态调度算法。该算法首先根据进程完成的截止时间和剩余的执行时间来计算进程的空闲时间，即空闲时间=截止时间-剩余执行时间；然后再根据进程的空闲时间来动态分配优先级，空闲时间越短，优先级越高，空闲时间越长，优先级越低。在执行的过程中，随着时间的向前推进，等待进程的空闲时间越来越短，相应的进程等待执行的紧急程度也就越来越紧迫，因此，等待进程随时可能会抢占当前执行的进程，从而造成了进程之间的相互竞争，导致了进程之间的频繁切换现象较为严重，大大增加了系统时间开销，其实际应用受到了一定的限制。

假设在开始运行时，实时系统的所有进程同时放行，首先获得系统执行权的是基本优先级最高的进程。随着系统运行时间的推移，所有进程的优先级在动态变化着，其中执行进程的执行紧迫性保持不变，而其剩余价值密度却在不断增加，这就避免了其它进程来抢占执行进程。对于活动进程和等待进程恰好相反，其执行紧迫性不断增加，而剩余价值密度保持不变，这就为抢占系统执行权提供了机会。此外，通过调节参数q和p的取值，可以调节进程执行紧迫性和剩余价值密度对进程动态优先级的影响力。若q的值较大时，可以增加价值密度低的进程参与系统执行的机会，但使进程抢占的概率大大增加，可能会造成部分价值密度大的进程夭折而降低系统累积价值收益。若p值较大时，能提高系统累积价值收益，能减少执行进程被抢占而夭折的概率，进而减少了进程抢占的次数，提高进程的执行成功率。

4 总结

本文综合了进程执行紧迫性和剩余价值密度随时间变化的这两方面因素，提出了基于优先级的动态分配策略DAS，通过论证证明该算法可通过改变参数q和p的取值，调节进程执行紧迫性和剩余价值密度对进程优先级影响的权重，从而提高了算法应对不同应用需要的灵活性，提高了进程的执行效率。

参考文献：

[1] 邹勇，王青，李明树.Linux内核的实时支持的研究与实现[J].计算机研究与发展，2002，39（4）：466-472.

[2] Liu C L，Layland James W. Scheduling algorithms for multiprogramming in a hard real-time environment[J].Journal of the ACM， 1973，20（1）：46-61

[3] Haritsa J R， Livny M，Carey M J.Earliest deadline scheduling for real-time database systems [C]//Proceedings of the 12th IEEE Real-Time Systems Symposium. San Antonio TX， USA，1991：232-243。

[4] Aldarmi S A，Burns A.Dynamic value-density for scheduling real-time systems[C]//Proceedings of the 11th Euromicro Conference on Real-Time Systems. York， England， UK，1999：270-277.