3第三章处理机的调度与死锁第四版.

第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度（自学内容）3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除处理机调度的基本概念：在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。3.1处理机调度的层次和调度算法的目标3.1.1处理机调度的层次处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次：高级调度中级调度低级调度•高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天•中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问•低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效3.1.2处理机调度算法的目标1.处理机算法调度的共同目标1）资源利用率：CPU利用率=有效工作时间/总时间2）公平性：公平性是相对的3）平衡性：保持系统资源使用的平衡性4）策略强制执行2.批处理系统的目标1）平均周转时间短：2）系统吞吐量高3）处理机利用率高niiTnT11niiTTnW1s13.分时系统的目标1）响应时间快2）均衡性4.实时系统的目标1）截止时间的保证2）可预测性3.2作业与作业调度3.2.1批处理系统中的作业•1作业和作业步•2作业控制块（JCB）在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。3.作业运行的三个阶段和三种状态1）收容阶段：建立JCB2）运行阶段：建立PCB3）完成阶段：回收PCB与JCB3.2.2作业调度的主要任务作业调度每次要接纳多少个作业进入内存，取决于多道程序度(DegreeofMultiprogramming)，即允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，因此，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。（接纳多少个作业）应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法。（接纳哪些作业）3.2.3作业调度算法1先来先服务（FCFS）先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。作业调度性能分析在此，我们通过一个例子来说明采用FCFS调度算法时的调度性能。下图示出有五个进程A、B、C、D、E，它们到达的时间分别是0、1、2、3和4，所要求的服务时间分别是4、3、5、2和4，其完成时间分别是4、7、12、14和18。从每个进程的完成时间中减去其到达时间，即得到其周转时间，进而可以算出每个进程的带权周转时间。2.短作业优先调度算法•结论：FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。•短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。•SJ(P)F调度算法也存在不容忽视的缺点：(1)该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。3.2.4优先级调度算法和高响应比优先调度算法1．优先权调度算法为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。1）非抢占式优先2）抢占式优先对于最高优先权优先调度算法，其关键在于：它是使用静态优先权，还是用动态优先权，以及如何确定进程的优先权。2.高响应比优先调度算法在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：要求服务时间要求服务时间等待时间优先权要求服务时间响应时间要求服务时间要求服务时间等待时间PR3.3进程调度3.3.1进程调度的任务、机制和方式1.进程调度的任务1）保存处理机的现场信息。2）按某种算法选取进程。3）把处理器分配给进程。2.进程调度机制1）排队器2）分派器3）上下文切换器3.进程调度方式1）非抢占方式：突发事件、I/O请求、进程通信2）抢占方式：①优先权原则②短进程优先原则③时间片原则3.3.2轮转调度算法1.轮转法的基本原理在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。2.进程切换时机3.时间片大小的确定在时间片轮转算法中，时间片的大小对系统性能有很大的影响，如选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。一个较为可取的大小是，时间片略大于一次典型的交互所需要的时间。这样可使大多数进程在一个时间片内完成。图为q=1和q=4时各进程的平均周转时间和带权平均周转时间进程名ABCDE平均到达时间01234作业情况时间片服务时间43424完成时间151216917周转时间15111461311.8RRq=1带权周转时间3.753.673.533.333.46完成时间47111317周转时间46910138.4RRq=4带权周转时间122.2553.332.53.3.3优先级调度算法该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权(优先级根据优先数来决定)•静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。•动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变3.3.4多级反馈队列算法•1多就绪队列设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。图是多级反馈队列算法的示意。就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1＜S2＜S3)多级反馈队列调度算法•2各队列FCFS算法当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。•3队列优先级调度仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。3.4实时调度3.4.1实现实时调度的基本条件•提供必要的信息(就绪时间、截止时间、处理时间、资源优先级)•系统处理能力强•采用抢占式调度机制•具有快速切换机制3.4.2实时调度算法的分类1)非抢占式调度算法:•非抢占式轮转调度算法•非抢占式优先调度算法2)抢占式调度算法:•基于时钟中断的抢占优先调度算法•立即抢占优先权调度算法。实时进程调度3.4.3最早截止时间优先EDF(EarliestDeadlineFirst)算法EDF算法用于非抢占调度方式3.4.4最低松弛度优先(LLF)算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。A和B任务每次必须完成的时间在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms；B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度为25ms，故调度程序应先调度A1执行。在t2=10ms时，A2的松弛度可按下式算出：A2的松弛度=必须完成时间-其本身的运行时间-当前时间=40ms-10ms-10ms=20ms类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30ms时，A2的松弛度已减为0，B1的松弛度为15ms，于是调度程序应抢占B1的处理机而调度A2运行…….利用ELLF算法进行调度的情况3.5死锁概述•3