实时调度：操作系统原理中实时调度算法的基本要求

实时调度是为了完成实时处理任务而分配CPU的调度方法，它的基本要求是保证计算机在规定的时间内对外部事件的请求做出响应。使用实时调度的实时操作系统具有及时响应、高可靠性、专用性、少人工干预等特征，被广泛应用于工业控制、信息通信、网警传输、媒体处理等领域。在实时系统中，存在一个或多个实时任务，它们反映或控制某个或某些外部事件，带有某种程度的时间紧迫性。

实时调度与非实时调度的区别表现在以下4个方面。

（1）实时调度所调度的任务有完成时限，而非实时调度则没有。所以实时调度算法的正确与否不仅与算法的逻辑有关，也与调度算法调度的时限有关。

（2）实时调度要求有较快的进程/线程切换时间，而非实时调度的进程/线程切换时间较长。

（3）非实时调度强调资源利用率（批处理系统）或用户共享CPU（分时系统），实时调度则主要强调在规定的时限范围内完成对相应对象的控制。

（4）实时调度为抢占式调度，而非实时调度除分时系统外则很少采用抢占式调度。

根据对截止时间的要求，实时任务分为硬实时任务和软实时任务两种。对硬实时任务，系统必须满足任务对截止时间的要求，否则可能出现难以预料的后果。对软实时任务，也有一个截止时间，要求任务也能够在截止期限到来之前得到处理，但偶尔违反截止期限并不会带来致命的错误。

根据实时任务是否具有周期性，还可以将实时任务分为周期性实时任务和非周期性实时任务。周期性实时任务以固定的时间间隔出现；非周期性实时任务的出现时间则无明显周期性，但必须遵守一个开始截止时间或完成截止时间。

要进行实时调度，系统需要向调度程序提供有关实时任务的信息，如就绪时间、开始截止时间或完成截止时间、任务处理时间、资源要求和任务优先权等。

并不是所有系统都可以进行实时调度。一个系统中往往有多个实时任务，若CPU的处理能力不强，则可能因CPU忙不过来使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。在单CPU情况下，若系统有m个周期性的硬实时任务，它们的处理时间和周期分别为G i和T i（i=1，2，3，…，m），则只有满足以下条件实时系统才是可调度的。

满足该条件则意味着系统能够及时处理实时任务，不满足该条件则可能出现CPU忙不过来的情况。(www.xing528.com)

按照实时任务性质的不同，可以将实时调度算法分为硬实时调度算法和软实时调度，算法。

按照调度方式的不同，可以将实时调度算法分为抢占式实时调度算法和不可抢占式实时调度算法。抢占式实时调度算法具有良好的时间响应性能，调度延迟可以降到毫秒级以下，常用在要求严格的实时系统中。不可抢占式实时调度算法比较简单，容易实现，常用在一些要求不严格的实时系统中。

根据调度的时间可以将实时调度算法分为静态调度算法和动态调度算法。静态调度算法通常是在系统配置过程中就决定了所有任务的执行时间，而动态调度算法则在系统运行过程中根据实际情况灵活决定任务的执行时间。静态调度无论是单CPU调度还是分布式调度，一般以比率单调（RMS）调度算法为基础，而动态调度则以最早截止时间优先（EDF）调度算法和最短空闲时间优先（LLF）调度算法为基础。

（1）比率单调（Rate Monotonic Scheduling，RMS）调度算法。该算法的任务优先级是按照任务周期来确定的。那些执行周期短的任务具有较高的优先级，而执行周期长的任务其优先级较低。调度程序总是将CPU分配给当前优先级最高的进程/线程，且进程/线程执行过程中，允许更高优先级的新进程/线程抢占当前运行进程/线程所使用的CPU。

比率单调调度算法实现简单、系统开销小、灵活性较好，是实时调度的基础性算法，缺点是CPU的利用率低。

（2）最早截止时间优先（Earliest Deadline First，EDF）调度算法。该算法也称截止时间驱动调度算法，是一种动态调度算法。它根据任务的截止时间来动态确定任务的优先级，截止时间越短则优先级越高，这种调度算法更多用于抢占式调度。调度使用的进程就绪队列可以按照任务截止时间的早晚进行排队，具有最早截止时间的进程排在最前面并最先获得CPU执行。每当有新进程到达时，系统就检查新进程的截止时间是否比当前运行进程的截止时间更早（即任务更紧迫），以决定是否剥夺（抢占）当前运行进程的CPU及其他资源。

（3）最短空闲时间优先调度算法。该算法也称为最小松弛度（Least Laxity First，LLF）优先调度算法，它也是一种动态调度算法。最短空闲时间优先是指在进行调度时，任务的优先级根据任务的空闲时间动态确定，任务的空闲时间越短则任务的优先级越高。

最短空闲时间优先调度算法主要用于抢占式调度。调度使用的进程就绪队列可以按照任务空闲时间的长短进行排队，具有最短空闲时间的进程排在最前面，并最先获得CPU执行。每当有新进程到达时，系统就检查新进程的空闲时间是否比当前运行进程的剩余时间更短（更加紧迫），以决定是否剥夺（抢占）当前运行进程的CPU及其他资源。

最短空闲时间优先调度算法在每个调度时刻都要计算任务的空闲时间，并根据计算的结果改变任务的优先级，因此系统开销较大，实现起来也相对麻烦。