1、3.3 进 程 调 度进程调度是OS中必不可少的一种调度。因此在三种类型的OS中，都无一例外地配置了进程调度。此外它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。3.3.1 进程调度的任务、机制和方式 1.进程调度的任务进程调度的任务主要有三：(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。2.进程调度机制为了实现进程调度，在进程调度机制中，应具有如下三个基本部分，如图3-1所示。(1)排队器。(2)分派器。(3)上下文切换器。图3-1 进程调度机制3.进程调度方式1)非抢占方式(Nonpreemptive Mode)在采用这种调度方
2、式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。2)抢占方式(Preemptive Mode)这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。在分时系统中，只有采用抢占方式才有可能实现人机交互。在实时系统中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付
3、出的系统开销也较大。3.3.2 轮转调度算法1.轮转法的基本原理在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。2.进程切换时机在RR调度算法中，应在何时进行进程的切换，可分为两种情况：若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪
4、队列中队首的进程运行，并启动一个新的时间片。在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。3.时间片大小的确定在轮转算法中，时间片的大小对系统性能有很大的影响。图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)是时间片小于典型交互的时间。图3-3示出了时间片分别为q=1和q=4时对平均周转时间的影响。图3-2 时间片大小对响应时间的影响 图3-3 q=1和q=4时进程的周转时间3.3.3 优先级调度算法1.优先级调度算法的类型优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，
5、又可进一步把该算法分成如下两种。(1)非抢占式优先级调度算法。(2)抢占式优先级调度算法。2.优先级的类型1)静态优先级静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：(1)进程类型。(2)进程对资源的需求。(3)用户要求。2)动态优先级动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。3.3.4 多队列调度算法如前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪
6、队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程度上弥补这一缺点。3.3.5 多级反馈队列(multileved feedback queue)调度算法 1.调度机制多级反馈队列调度算法的调度机制可描述如下：(1)设置多个就绪队列。图3-4是多级反馈队列算法的示意图。图3-4 多级反馈队列调度算法(2)每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即
7、它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。(3)按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行；换言之，仅当第1(i-1)所有队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。2.调度算法的性能在多级反馈队列调度算法中，
8、如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要。(1)终端型用户。(2)短批处理作业用户。(3)长批处理作业用户。3.3.6 基于公平原则的调度算法 1.保证调度算法保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n。在实施公平调度算法时系统中必须具有这样一些功能：(1)跟踪计算每个进程自创建以来已经执行的处理时间。(2)计算每个进程应获得的处理机时间，即自创建以来的时间除以n。(3)计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。(4)比较各进程获得处理机时间的比率。如进程A的比率最低，为0.5，而进程B的比率为0.8，进程C的比率为1.2等。(5)调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。2.公平分享调度算法分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。
