处理机调度36Linux系统中的进程调度.ppt

对于一组给定的作业来说，短作业优先法给出最小的平均等待时间。可以证明，在这方面它是最佳的。证明的办法是，把一个短作业移到长作业之前所减少的短作业的等待时间大于增加的长作业等待时间。相应地，平均等待时间也减少了，如图3-11所示。图3-11SJF有最小平均等待时间3.5.3优先级（Priority）短作业优先法是一般优先级调度算法的特例。每个进程有一个优先级，CPU分给优先级最高的进程。优先级相同的进程按FCFS调度。短作业优先法是简化的优先级算法，这里优先级（p）反比于估计的下一次CPU工作时间（τ）,p=1/τ。CPU工作时间越长，其优先级越低。3.5.4抢占式和非抢占式算法SJF既可以为抢占式，又可以为非抢占式。当一个作业正在执行时，一个新作业到来，并进入就绪队列，而新作业比当前正在执行的作业还短，在此情况下，就有两种不同的处理方式：抢占式短作业优先算法强行中止当前正在执行的作业，调度新作业执行；而非抢占式SJF将允许当前作业继续运行，直到完成它的CPU运行工作。抢占式短作业优先法也叫做最短剩余时间优先法（SRTF，ShortesRemainingTimeFirst）。作为例子，考虑下面4个作业（如图3-12所示）。图3-124个作业示例如果这些作业按上面所示的时间进入就绪队列并需要指定的运行时间，那么下面的示意图（如图3-13所示）就说明了最短剩余时间优先法调度的结果。图3-13SRTF法调度示例表3-1SRTF调度算法的性能3.5.5轮转法（RR）轮转法（RR，RoundRobin）主要是为分时系统设计的。一个极为重要的参数就是时间片，它是一个小的时间单位，不能取得过大或者过小，通常为10～100ms数量级。就绪队列可看成是一个环形队列，CPU调度程序轮流地把CPU分给就绪队列中的每个进程，时间长度都是一个时间片。图3-14RR法q=1和q=4时进程运行的情况由图3-14可以看出，在轮转法中，一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片。如果一个进程在一个时间片内没有做完自己的事情，那么在时间片用完时，该进程就被剥夺对CPU的控制权，放回到就绪队列的末尾。所以，一个需运行较长时间的进程要经过多次轮转才能完成工作。表3-2给出各进程的周转时间和带权周转时间项等指标。表3-2RR调度算法的性能时间片的长短通常由以下几个因素确定：（1）系统的响应时间：在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求；（2）就绪队列进程的数目：当系统要求的响应时间一定时，时间片的大小反比于就绪队列中的进程数；（3）进程的转换时间：若进程的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10；（4）CPU运行指令速度：CPU运行速度快，则时间片可以短些；反之，则应取得长些。3.5.6多级队列法（MQ）另一类调度算法是把多个进程分成不同级别的组。例如，通常的划分方式是分为前台进程（交互）和后台进程（批处理）。这两类进程的响应时间要求是完全不同的，所以有不同的调度算法。多级队列（MQ，MultilevelQueue）调度算法把就绪队列划分成几个单独的队列（如图3-15所示）。图3-15多级队列调度下面是多级队列调度法的一个例子，有如下5个队列：（1）系统进程；（2）交互进程；（3）交互编辑进程；（4）批处理进程；（5）学生批处理进程。3.5.7多级反馈队列法（MFQ）通常在多级队列法中，进程是永久性地放到一个队列中的，它们不能从一个队列移到另一个队列。而多级反馈队列法（MFQ，MultilevelFeedbackQueue）允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来。图3-16多级反馈队列3.5.8多级调度综合示例在一个系统中会采用多级调度，如作业调度和进程调度，并且各采