第8讲处理机调度与死锁之处理机调度的基本概念e

第八讲处理机调度与死锁之处理机调度的基本概念与调度算法引言处理机管理可以归结为进程管理。在多道程序环境下，进程数目往往多于处理机数目，就会竞争使用处理机，这样就要求系统采用某种算法，合理的分配处理机给那些就绪态进程，使之能够执行。分配处理机的任务是由处理机调度程序也就是进程调度程序来完成的，此为操作系统的核心问题之一。1调度的层次一个作业，从进入系统并驻留在外存的后备队列上开始，直到作业运行完，要经历三级调度：高级调度，低级调度和中级调度。也就是一个作业从提交到完成要经历三级调度。调度的层次如图所示：1.1高级调度（HighScheduling）(作业/长程/宏观调度)1.1.1任务用于把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要资源，再讲新创建的进程挂在就绪队列。注意：a)在批处理系统中，大多配有作业调度；分时/实时系统中，一般不配置。b)作业调度执行频率很低，甚至几分钟一次，甚至更久。1.1.2高级调度需要解决的问题a)接纳多少个作业？主要任务是从外存后备队列中选择多少作业进入就绪队列或挂起就绪，也就是允许多少作业同时在内存中运行，它决定着多道程序的“道或度”。若作业太多，则可能会影响系统的服务质量（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。因此，应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。b)接纳哪些作业？应将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等算法）1.2低级调度（lowlevelscheduling）（短程/CPU/进程/微观调度）1.2.1任务主要任务就是从就绪队列中选择一个进程来执行并给其分配处理机。注意：a)是OS中最基本的调度。b)调度频率非常高，一般几十毫秒一次。c)常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。1.2.2进程调度方式a)非抢占式（preemptivemode）原理：处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。特点：现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用b)抢占式（preemptivemode）原理：度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。特点：处理紧急任务，故实时与分时系统中常采用。时间片、优先权、短进程优先原则见课本P71。例1，有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。假如它们就按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24、26个单位时间，平均周转时间是23.33个时间单位。假如用时间片原则的抢占式调度方式，可得到：02468101226P1P2P3P1P2P1P1...P12222216可见：P1、P2、P3的周转时间分别为26、10、6个单位时间，平均周转时间为14个单位时间。补充：衡量进程调度性能的指标有：周转时间、响应时间、截止时间。概念：周转时间：作业从提交到完成（得到结果）所经历的时间。平均周转时间T。见课本74平均带权周转时间（带权周转时间W是T(周转)/T(CPU执行)〕响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。与周转时间有些相似。1.2中级调度（intermediate-levelscheduling）(中程/交换调度)1.2.1任务在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。详见P72。2、调度队列模型在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。2.1仅有进程调度的调度队列模型仅有进程调度的调度队列模型2.2具有高级和低级调度的调度队列模型2.3同时具有三级调度的调度队列模型3选择调度方式和算法的若干准则3.1面向用户的准则周转时间短、响应时间快、截止时间的保证、优先权准则3.2面向系统的准则系统吞吐量、处理机利用率好、各类资源平衡利用3.3最优准则最大的CPU利用率、最大的吞吐量、最短的周转时间、最短的等待时间、最短的响应时间4调度算法调度算法：是指根据系统的资源分配策略所规定的资源分配算法。这里所谓的调度算法，是指批处理系统、分时系统的调度，而不包括实时系统的调度。4.1先来先服务和短作业（进程）优先调度算法FCFS,FirstComeFirstService；SJF,ShortestJobFirst；SPF，ShortestProcessFirst4.1.1先来先服务调度算法1．基本思想：按照进程进入就绪队列的先后次序来分配处理机。一般采用非剥夺的调度方式。适用于作业调度也用于进程调度。当作业调度采用该算法：每次调度都是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，并分配资源、创建进程，之后进入就绪队列。当进程调度采用该算法：该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。2．例子：见课本。3．优缺点：有利于长作业进程，而不利于短作业进程这是因为若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。有利于CPU繁忙型作业，不利于I/O，忙的作业。课本p76页。现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。4.1.2短作业（进程）优先调度算法（SJF/SPF）1、基本思想：短作业或短进程优先调度。短作业优先调度算法（SJF）用于作业调度主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程优先调度算法（SPF）用于进程调度主要任务是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。2、例子，见课本3。、优缺点：降低作业的平均等待时间，提高系统吞吐量。对长作业不利；未考虑作业的紧迫程度；对进程估计执行时间难以预测。4.2高优先权优先调度算法PrioritySchedulingFirst为了考虑作业的紧迫程度，引入了最高优先权调度算法（FPF）4.2.1优先权调度算法类型1非抢占式优先权算法基本原理：系统把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成；或因发生某时间使该进程放弃处理机时，系统才可将处理机重新分配给另一优先权最高的进程。适用：批处理系统，实时性要求不高的实时系统。2抢占式优先权算法基本原理：系统把处理机优先权最高的进程，使之执行。若在其执行期间，只要又出现另一个优先权更高的进程，则立即停止当前进程的执行，重新分配处理机给新来的优先权更高的进程。适用：实时性要求高的实时系统，对性能要求高的批处理和分时系统。4.2.2优先权类型1、静态优先权静态优先权是在创建进程的时确定的，且在进程的整个运行期间保持不变。一般，利用某一范围内的整数来表示，如，0~7或0～255中的整数。2、动态优先权是指在创建进程时确定的优先权，在进程的运行期间会发生变化。4.2.3高响应比优先调度算法思想：利用响应比也就是优先权来决定给作业分配处理机。pR为响应比。我们可以看出，优先权随等待时间的增加而提高，因此长作业在等待一定时间后，就有机会分配到处理机执行。说明：1)如等待时间相同,则要求服务时间愈短,其优先权愈高—SPF。就是短作业优先算法2)如要求服务时间相同,优先权决定于等待时间----FCFS。就是先来先服务算法3)对长作业,若等待时间足够长，优先权也高，也能获得CPU。是本算法的优点，解决了短作业优先算法中，长作业的运行得不到保证的情况。也就是引入该算法的原因。4.3基于时间片的轮转调度算法RR,RoundRobin早期的分时系统采用时间片轮转算法，90年代后，采用多极反馈队列调度算法。4.3.1时间片轮转法基本思想：系统将所有就绪进程按FCFS的原则，排成一个队列，依次调度，把CPU分配给队首进程，并令其执行一个时间片/CPU时间，通常为几个毫秒～几百毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。4.3.2多级反馈队列调度算法RoundRobinwithMultipleFeedback1、基本思想：多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。2、实现过程：（1）设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。（2）每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。（3）当一个新进程进入系统时，首先将它放入队列1的末尾，按FCFS等待调度。如能完PR要求服务时间响应时间要求服务时间要求服务时间等待时间优先权成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按FCFS再次等待调度，如此下去，进入队列n按时间片轮转算法调度执行。（4）仅当队列1为空时，才调度队列2中的进程运行。若队列I中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。原进程转移至下一队列。如下图：