计算机操作系统中的实时调度与非抢占式优先调度算法

实时系统中都存在若干个实时进程或任务，这些任务的特征是将时间作为关键参数，一般都带有某种程度的紧迫性。因此对实时系统的调度也提出了某些特殊要求。

4.4.1 实现实时调度的基本条件

在实时系统中，硬实时任务和软实时任务都联系着一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求，为此，实现实时调度应具备下述几个条件。

1.提供必要的信息

为了实现实时调度，系统应向调度程序提供有关任务的下述一些信息：

（1）就绪时间。这是该任务成为就绪态的起始时间，在周期任务的情况下，它就是事先预知的一串时间序列；而在非周期任务的情况下，它也可能是预知的。

（2）开始截止时间和完成截止时间。对于典型的实时应用，只需知道开始截止时间，或者知道完成截止时间。

（3）处理时间。这是指一个任务从开始执行直至完成所需的时间。在某些情况下，该时间也是系统提供的。

（4）资源要求。这是指任务执行时所需的一组资源。

（5）优先级。如果某任务的开始截止时间已经错过，就会引起故障，则应为该任务赋予“绝对”优先级；如果开始截止时间的推迟对任务的继续运行无重大影响，则可为该任务赋予“相对”优先级，供调度程序参考。

2.系统处理能力强

在实时系统中，通常都有多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：系统才是可调度的。假如系统中有6个硬实时任务，它们的周期时间都是50 ms，而每次的处理时间为10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。

解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为

顺便说明一下，上述的限制条件并未考虑到任务的切换时间，包括执行调度算法和进行任务切换，以及消息的传递时间等开销。因此，当利用上述限制条件来确定系统是否可调度时，还应适当地留有余地。

3.采用抢占式调度机制

在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行。这样便可满足该硬实时任务对截止时间的要求，但这种调度机制比较复杂。

对于一些小型实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务。

4.具有快速切换机制

为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制，以保证能进行任务的快速切换。该机制应具有以下两方面的能力：

（1）对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机（其他紧迫任务）。

（2）快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开销。

4.4.2 实时调度算法的分类

可以按不同方式对实时调度算法加以分类，如根据实时任务性质的不同，可将实时调度的算法分为硬实时调度算法和软实时调度算法；而按调度方式的不同，又可分为非抢占式调度算法和抢占式调度算法；还可因调度程序调度时间的不同而分成静态调度算法和动态调度算法，前者是指在进程执行前，调度程序便已经决定了各进程间的执行顺序，而后者则是在进程的执行过程中，由调度程序届时根据情况临时决定将哪一进程投入运行。在多处理机环境下，还可将调度算法分为集中式调度和分布式调度两种。这里，仅按调度方式的不同对调度算法进行分类。

1.非抢占式调度算法

由于非抢占式调度算法比较简单，易于实现，故在一些小型实时系统或要求不太严格的实时控制系统中经常采用之。

（1）非抢占式轮转调度算法。该算法常用于工业生产的群控系统中，由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个（队首）任务运行。这种调度算法可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。

（2）非抢占式优先调度算法。如果在实时系统中存在要求较为严格（响应时间为数百毫秒）的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。这种调度算法在做了精心的处理后，有可能获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。(www.xing528.com)

2.抢占式调度算法

在要求较严格的（响应时间为数十毫秒以下）的实时系统中，应采用抢占式优先权调度算法。可根据抢占发生时间的不同而进一步分成以下两种调度算法：

（1）基于时钟中断的抢占式优先权调度算法。在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。这种调度算法能获得较好的响应效果，其调度延迟可降为几十毫秒至几毫秒。因此，此算法可用于大多数的实时系统中。

（2）立即抢占（immediate preemption）的优先权调度算法。在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。这种算法能获得非常快的响应，可把调度延迟降低到几毫秒至100μs，甚至更低。

图4-11分别示出了采用非抢占式轮转调度算法、非抢占式优先权调度算法、基于时钟中断抢占的优先权调度算法和立即抢占的优先权调度算法四种情况的调度时间。

图4-11 实时进程调度

4.4.3 实时调度算法

目前已有许多用于实时系统的调度算法，其中有的算法仅适用于抢占式或非抢占式调度，而有的算法则既适用于非抢占式，也适用于抢占式调度方式。在常用的几种算法中，它们都是基于任务的优先权，并根据确定优先级方法的不同而又形成了以下几种实时调度算法。

1.最早截止时间优先（earliest deadline first，EDF）算法

EDF算法是根据任务的开始截止时间来确定任务的优先级。截止时间越早，其优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；当然，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。最早截止时间优先算法既可用于抢占式调度，也可用于非抢占式调度方式中。

图4-12 EDF算法用于非抢占调度的调度方式

（1）非抢占式调度方式用于非周期实时任务。图4-12示出了将EDF算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。

图4-13 最早截止时间优先算法用于抢占调度方式

（2）抢占式调度方式用于周期实时任务。图4-13示出了将最早截止时间优先算法用于抢占调度方式之例。在该例中有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0 ms、20 ms、40 ms、…；任务A的最后期限为20 ms、40 ms、60 ms、…；任务B的到达时间为0 ms、50 ms、100 ms、…；任务B的最后期限为50 ms、100 ms、150 ms、…。

为了说明通常的优先级调度不能适用于实时系统，该图特增加了第二和第三行。在第二行中假定任务A具有较高的优先级，所以在t＝0 ms时，先调度A1执行，在A1完成后（t＝10 ms）才调度B1执行；在t＝20 ms时，调度A2执行；在t＝30 ms时，A2完成，又调度B1执行；在t＝40 ms时，调度A3执行；在t＝50 ms时，虽然A3已完成，但B1已错过了它的最后期限，这说明了利用通常的优先级调度已经失败。第三行与第二行类似，只是假定任务B具有较高的优先级。

第四行是采用最早截止时间优先算法的时间图。在t＝0 ms时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行；在t＝10ms时，A1完成，又调度B1执行；在t＝20 ms时，A2到达，由于A2的截止时间比B2早，B1被中断而调度A2执行；在t＝30 ms时，A2完成，又重新调度B1执行；在t＝40 ms时，A3又到达，但B1的截止时间要比A3早，仍应让B1继续执行直到完成（t＝45 ms），然后再调度A3执行；在t＝55 ms时，A3完成，又调度B2执行。在该例中利用最早截止时间优先算法可以满足系统的要求。

2.最低松弛度优先（least laxity first，LLF）算法

LLF算法是根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高，为该任务所赋予的优先级就越高，以使之优先执行。例如，一个任务在200 ms时必须完成，而它本身所需的运行时间就有100 ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度（松弛程度）为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行150 ms，则其松弛程度为250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。

该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms；任务B只要求每50 ms执行一次，执行时间为25 ms。由此可得知任务A和B每次必须完成的时间分别为：A1，A2，A3，…和B1，B2，B3，…，如图4-14所示。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。

图4-14 A和B任务每次必须完成的时间

在刚开始时（t1＝0ms），A1必须在20 ms时完成，而它本身运行又需10 ms，可算出A1的松弛度为10 ms；B1必须在50 ms时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2＝10 ms时，A2的松弛度可按下式算出：

A 2的松弛度＝必须完成时间－其本身的运行时间－当前时间＝40 ms－10 ms－10 ms＝20 ms类似地，可算出B1的松弛度为15 ms，故调度程序应选择B2运行。在t3＝30ms时，A2的松弛度已减为0 ms（即40－10－30），而B1的松弛度为15 ms（即50－5－30），于是调度程序应抢占B1的处理机而调度A2运行。在t4＝40ms时，A3的松弛度为10 ms（即60－10－40），而B1的松弛度仅为5 ms（即50－5－40），故又应重新调度B1执行。在t5＝45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms（即60－10－45），而B2的松弛度为30 ms（即100－25－45），于是又应调度A3执行。在t6＝55ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7＝70 ms时，A4的松弛度已减至0 ms（即80－10－70），而B2的松弛度为20 ms（即100－10－70），故此时调度又应抢占B2的处理机而调度A4执行。图4-15示出了具有两个周期性实时任务的调度情况。

图4-15 利用LLF算法进行调度的情况