操作系统精髓与设计原理--单处理器调度

概述

在多道程序设计系统里，内存有多个进程，且或者在处理器上运行，或者在等待某种事件的发生（如I/O完成）。当处理器（或组）通过执行某个进程而保持忙状态，则其他的进程处于等待状态。

多道程序设计的关键是调度，操作系统根据进程的执行有三种类型的处理器调度方案和一种I/O调度方案：

• 长调度方案：确定何时允许一个新进程进入系统

• 中调度方案：负责内存的交换功能，确定何时将一个程序的部分或全部取进内存。

• 短调度方案：确定哪个就绪进程下一次被处理器执行。

• I/O调度方案：决定哪一个进程挂起的I/O请求将被可用的I/O设备处理

这里对处理器调度方案的进行总结，且短调度方案占主要部分，I/O调度方案将总结于下一次有关I/O问题的总结里。

考虑到执行的频繁程度，长调度程序执行的频率相对较低（仅仅粗略地决定是否接受新进程以及接受哪一个）；中程度调度方案执行的略为频繁（决定进程的交换）；短调度程序（分派程序）只执行的最频繁（精确地决定下一次执行哪一个进程）。长调度与中调度方案主要由系统并发度相关性能驱动，之后会给出三种调度方案的关联。由于多处理器对的使用有额外的复杂度，这里参考单处理器系统的调度情况，以更清楚地发现调度算法的区别。

调度方案的关联图

进程状态和调度转换图

调度方案的嵌套图

用于调度的队列图

长程调度

由于决定了哪个程序可以进入系统里处理，因此控制了系统并发度。

长程调度程序运行时创建相应的进程，此过程涉及两个决策：决定什么时候操作系统能接受一个或多个进程、决定接受哪个作业或哪些作业并转为进程。

对于决定什么时候操作系统接受一个或多个进程，通常由系统的并发度来驱动。进程越多则每个进程执行事件所占百分比越小（更多的进程竞争同样数量的处理器时间）。为了给当前的进程集提供适合的处理器资源，长程调度可能限制系统并发度，当一个作业终止或处理器的空闲时间片超过一定阈值后，会限制系统并发度或启动长程调度程序。

对于允许哪个作业进入的决策可以基于简单的先来先服务原则，或者基于管理系统性能的工具（包括优先级、期待执行时间、I/O需求）。

对于分时系统的交互程序，用户试图连接到系统的动作可能产生一个进程创建的请求，分时下的用户不是仅仅排队等待，直到系统接收他们。相反操作系统会接收所有的授权用户，直到系统饱和为止。此时用户再次连接会得到操作系统已经饱和并要求用户重试的消息。

中程调度

是交换功能的一部分，典型情况下换入取决于管理系统并发度需求，在不使用虚拟内存的系统里，系统管理也是一个问题。因此换入决定将考虑换出进程的存储需求。

短程调度

主要目标是按照优化系统的若干方面行为的方式来分配处理器时间，当可能导致当前进程阻塞或可能抢占当前运行进程的事件发生时，调用短程调度程序，事件包括时钟中断、I/O中断、操作系统调用、信号等。

短程调度的设计准则

设计时要对可能被评估的各种调度策略建立一系列规则。该准则按两种维度分类：一个维度是面向用户或面向系统，另一个维度是与性能直接相关或非直接相关。

面向用户与面向系统的准则

面向用户的准则：与的那个用户或进程感知到的系统行为相关，如交互式系统的响应时间，此时间数量对用户是可见的。对于响应时间可以定义一个阈值，则调度机制的目标是使平均响应时间小于等于此阈值的用户数量最大。

面向系统的准则：重点是处理器的使用的效果和效率，如吞吐量，即进程完成的速度。该准则是系统管理员所关注的。

面向用户的准则在所有系统中都非常重要，而面向系统的原则在单用户系统的重要性较低。在单用户系统里，只要系统对用户应用程序的响应时间可以接受，则实现处理器的高利用率或高吞吐量可能并不重要。

与性能直接或非直接相关

与性能直接相关的准则是定量且通常易于度量的，如响应时间和吞吐量。

与性能非直接相关的准则是定性的且不易于测量与分析，如可预测性，即服务随时间改变时表现出一贯相同的特性，且与系统执行的其他工作无关（可以通过计算负载函数的变化量来度量，但不像吞吐率或相应时间关于工作量的函数一样直接）。

相互依赖的调度准则

以上的调度准则不可能 同时让它们达到最优，如提供好的响应时间则可能要调度算法在进程间频繁的切换而增加了系统开销，降低吞吐量。以下是一些比较重要的调度准则。

• 周转时间：一个进程从提交到完成之间的时间间隔，包括实际执行时间、等待资源时间，对于批处理作业是很适宜的度量。

• 响应时间：对于交互进程，指提交一个请求后到开始接收响应之间的时间间隔。通常进程处理请求时就开始给用户一些输出，对于用户的角度是更好的度量。此调度准则试图达到较低的响应时间，在可接受的时间里使交互的用户数量最大。

• 最后期限：进程完成的最后期限，调度原则将降低其他目标的执行，使满足最后期限的作业数目执行百分比最大。

• 可预测性：无论系统的负载如何，一个给定工作运行的总时间和总开销是相同的，即响应时间后周转时间变化不能太大，可能需要在系统工作负载大范围抖动时发出信号或需要系统来处理不稳定性。

• 吞吐量：室每个时间单位里完成的进程数目最大，是对可以执行多少工作的一种度量。主要取决于一个进程的平均执行长度，也受调度策略的影响（会影响处理器的利用率）。

• 处理器利用率：处理器忙的百分比，对于昂贵的共享系统是一个重要的准则，对于单用户系统和其他系统（如实时系统）则不太重要。

• 公平性：在没有来自用户的指导或其他系统提供的指导是，进程要被平等的对的，没有进程处于饥饿。

• 强制优先级：当进程被指定优先级后，调度策略要优先选择高优先级进程。

• 平衡资源：调度策略保持系统资源处于忙状态，较少使用紧缺资源的进程要优先调度。同样适用于长程调度和中程调度。

短程调度算法

选择上取决于预期的性能和实现的复杂度。

各种调度策略的特点

w:进程等待时间；e:当前已执行的时间；s:进程所需的总服务时间，包括e

先来先服务 FCFS

会选择等待时间最长的进程，当一个进程停止时，就从就绪队列里取存在时间最长的进程执行。对于执行短进程，执行一个长进程的效果更好，当执行有长进程先执行时，短进程就不得不等待长进程执行完，短进程归一化周转时间（周转时间/服务时间）比长进程多得多。

对于I/O密集型进程，相比处理器密集型不利于调度。当同时有I/O密集型和处理器密集型的进程时，如果此时处理器密集型程序正在运行，则I/O密集型必须等待。有的I/O密集型进程可能在I/O队里，且处理器密集型进程正在执行时进入了就绪队里，I/O设备就有可能是空闲的，即使有其他进程要使用。当前的进程执行完后，等待的I/O密集型进程会快速通过运行态，再次进入到I/O队列里，期间对处理器的使用时间并不长。如果处理器密集型进程阻塞了，则处理器和I/O设备都会空闲。

轮转 RR

为了减少FCFS对短作业不利的情况，一个简单的方法是采用基于时钟的抢占策略，最简单的方法是轮转算法。以一个周期性间隔产生时钟中断，中断发生时当前运行的进程被置于就绪队列里，然后基于FCFS策略选择下一个就绪作业运行。此技术也叫做时间片，每个进程被抢占前被分给一定的时间。

其主要的设计问题时使用的时间片长度，较短则短作业会较快的通过系统。同时处理时钟中断、执行调度和分派函数都需要处理器开销，因此要避免过短的时间片。较好的思想是时间片要略大于一次典型交互所要时间，如果小于则大多数进行要至少两个时间片长度；如果过长会退化成FCFS策略。该策略在通用的分时系统或事务处理系统特别有效。

轮转策略的一个缺点是依赖于处理器密集型的进程和I/O秘籍型的进程的不同。如果两者都存在的话会有如下情况：一个I/O秘籍型进程用了很短的处理器时间后，进入到I/O队列，等待I/O操作完成后进入就绪队列；同时，一个处理器密集型进程在执行过程中使用了一个完整的处理器时间后，进入就绪队列。因此对于这两类进程，占用的处理器分时间并不平等，I/O密集型进程获得处理器的时间不等，等待的时间受就绪进程数的影响，使I/O密集型进程性能降低、使用I/O设备低效、响应时间的变化大。

对此的改进是虚拟轮转法，和简单的轮转策略不同的是，当没有用完一个时间片且被阻塞后，就绪时进入一个FCFS辅助队列，当进行一次调度决策时，辅助队列优先于就绪队列的进程，并在剩余的时间片时间上执行。

最短进程优先 SPN

减少FCFS固有对长进程偏向的另一种方法是最短进程优先，是一个非抢占策略，原则是选择下一次预计处理时间最短的进程。短进程会优先于长进程执行，因此响应的波动增加，可预测性降低。

SPN策略难点在于预测每个进程所需要的执行时间。对于批处理作为，系统要求程序员估计该值并提供给操作系统。如果值远低于实际值则可能提前终止此作业。在生产环境中，相同的作业频繁运行，可以收集它们的统计值，对于交互进程，操作系统可以为为每个进程保留一个运行平均值。

最短剩余时间 SRT

针对SPN添加的抢占机制，此时调度程序总是选择预期剩余时间最短的进程。当一个新进程进入就绪队列时，就可能比当前运行的进程剩余时间要短。所以每次有新进程进入到就绪队列里，调度程序就可能抢占当前正在运行的进程。和SPN一样，需要有关处理时间的估计，同时有长进程饥饿的可能。

由于SRT不会像FSFC那样偏向于长进程，也不会像RR那样产生额外的中断，从而减少了开销；同时它必须记录过去的服务时间而增加了开销。从周转时间上来看，SRT比SPN有更好的性能，因为相对于正在运行的长进程，短进程可以被选择运行。

最高响应比优先 HRRN

归一化周转时间是周转时间和实际服务时间的比率（R=(w+s)/s，R为归一化周转时间，w为等待时间，s为预期的服务时间），可作为性能度量，且每个进程和所有进程的平均值都越小越好。

调度规则每次选择R最大的就绪进程，此方法的一个特点是参考了进程的执行历史。当偏向短作业是（s小，比值大），长进程由于得不到服务而增加等待时间，从而增加了比值（分子大，比值大），最终被会优于短进程而被调度。

和SPN、SRT一样，需要估计服务时间。

反馈 FB

如果没有关于个个进程的相对长度的任何信息，则SPN、SRT、HRRN都不能使用。另一种使短作业优先的方法是降低长作业的优先级，即不能获得剩余执行时间，则关注已执行时间。

调度基于按时间片的抢占原则，同时有动态的优先级机制。当一个进程第一次进入系统中时被放置在RQ0（优先级最高的就绪队列），当被抢占后就绪时放入到RQ1里（优先级次于RQ0的就绪队列），以此类推指定放入到优先级最低的的就绪队列RQN，并在此队列使用FCFS调度策略。由于一个短进程很快就执行完，以此优先级不会降低很多，而长进程由于执行时间较长则优先级会降得较多。

简单的反馈策略依据时间片长度轮转，同时有其他变体。简单的返回策略存在一个问题，长进程的周转时间会不断增加，如果频繁的有新进程进入系统，则可能产生饥饿。为解决此问题，有以下几个变体策略

• 按照队列改变抢占次数，如每个进程每次在RO0队列允许执行一个时间单位、RO1允许2个时间单位、RON允许2^n个时间单位等。

• 即使给较低队列执行较多的时间，长进程仍然有饥饿的情况存在，另一个方法是当一个进程在当前就绪队列里等待服务的时间超过一定的量后，就提高此进程的优先级。