操作系统作业调度(精品)

,第三章 处理机调度与死锁,3.1,处理机调度概述,3.2,调度算法,3.3,实时调度,3.4,死锁的概念,3.5,死锁的预防和避免,3.6,死锁的检测和解除,3.1,处理机调度概述,处理机调度（,CPU,调度）,要解决的问题：,WHAT：,按什么原则分配,CPU,调度算法,WHEN：,何时分配,CPU,调度的时机,HOW：,如何分配,CPU,CPU,调度过程（进程的上下文切换）,3.1.1,处理机调度的三个层次,作业调度（高级调度）,交换调度（中级调度）,进程调度（低级调度）,！,进程调度频率最高，约,10100 ms,进行一次，因而进程调度算法不能太复杂，以免占用太多,CPU,时间,（,1）作业,程序,+,数据,+,作业说明书,（2）作业步,作业调度,（,4,）作业控制块（,JCB：Job Control Block）,作业控制块是作业存在的标志,保存有系统进行作业管理所需要的全部信息,位于磁盘区域中,（,5,）作业调度,1),接纳多少个作业,2),接纳哪些作业,FCFS,、,SJF,、,HPF,、,HRN,一、进程调度的功能,:,在,PCB,中保存处理机的现场信息,根据算法选取进程,分派程序将处理机分配给进程,附：,调度方式,非,抢占方式：,运行进程完成或阻塞时，才再分配处理机。,抢占方式：,将正运行进程强行撤下，处理机分配给其它进程。,进程调度,二、进程调度的时机：,当前进程结束,当前进程调用阻塞原语将自己阻塞,当前进程调用,P(),申请资源不能满足或调用,V(),唤醒了等待进程,当前进程提出了,I/O,请求,时间片到,在抢占调度中，有一个优先权更高的进程进入就绪队列,三、进程调度算法：,就绪队列的两种组织：,进程进入就绪队列时，插入到合适的优先位置。调度时取队首进程。,进程进入就绪队列末尾，调度时扫描整个队列，选择最合适的进程。,FCFS,、,SPF,、,HPF,、,RR,3.1.2,调度队列模型,1.,仅有进程调度的调度队列模型,图,3-1,仅具有进程调度的调度队列模型,2.,具有高级和低级调度的调度队列模型,图,3-2,具有高、低两级调度的调度队列模型,3.,同时具有三级调度的调度队列模型,图,3-3,具有三级调度时的调度队列模型,3.1.3,选择调度方式和调度算法的若干准则,1.,面向用户的准则,(1),周转时间短。,平均周转时间：,作业的周转时间,T,与系统为它提供服务的时间,T,S,之比，即,W,=,T/T,S,，称为带权周转时间，而平均带权周转时间则可表示为,:,(2),响应时间快。,(3),截止时间的保证。,(4),优先权准则。,2.,面向系统的准则,系统吞吐量高。,(2),处理机利用率好。,(3),各类资源的平衡利用。,3.2,调度算法,3.2.1,先来先服务和短作业,(,进程,),优先调度算法,先来先服务调度算法,FCFS：First Come First Serve,2.,短作业,(,进程,),优先调度算法,SJF：Shortest Job First,例,假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间。应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间,先来先服务调度算法计算结果,最短作业优先作业算法计算结果,3.2.2,高优先权优先调度算法,1.,优先权调度算法的类型,非抢占式优先权算法,抢占式优先权调度算法,把处理机分给优先权最高的就绪进程。,（,HPFHighest Priority First,静态优先权：创建进程时根据进程类型、资源需求、用户要求等因素确定优先级，并保持不变。,动态优先权：创建进程时赋予进程一个优先权初值，但随着进程的等待时间及执行时间的延长，其优先级会增加或降低。,例：线性优先级调度策略：,享受服务进程队列,新建进程队列,CPU,优先级,P=P+a*t,优先级,P=P-,b*t,(ab0),2.,优先权的类型,3.,高响应比优先调度算法,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比,R,P,。,（,HRRN：Highest Response Ratio Next）,(1),如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。,(2),当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。,(3),对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。,最高响应比优先作业算法计算结果,练习,应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,8:00,120,2,8:30,40,3,9:00,8,4,9:30,12,平均周转时间,t=,平均带权周转时间,w=,先来先服务,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,8:00,120,8:00,10:00,120,1,2,8:30,40,10:00,10:40,130,3.25,3,9:00,8,10:40,10:48,108,13.5,4,9:30,12,10:48,11:00,90,7.5,平均周转时间,t=112,平均带权周转时间,w=6.31,短作业优先,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,8:00,120,8:00,10:00,120,1,2,8:30,40,10:20,11:00,150,3.75,3,9:00,8,10:00,10:08,68,8.5,4,9:30,12,10:08,10:20,50,4.17,平均周转时间,t=97,平均带权周转时间,w=4.355,最高响应比优先,作业,提交时间,运行时间,开始时间,完成时间,周转时间,带权周转时间,1,8:00,120,8:00,10:00,120,1,2,8:30,40,10:20,11:00,150,3.75,3,9:00,8,10:00,10:08,68,8.5,4,9:30,12,10:08,10:20,50,4.17,平均周转时间,t=97,平均带权周转时间,w=4.355,各进程按提交顺序排成就绪队列，然后依次占用处理机，运行某一时间片（通常,100ms,是一个比较好的折衷），时间片到则排入就绪队列尾。,时间片的确定：时间片,q=,响应时间,T/,进程数,N,系统开销：如时间片,100ms,，进程切换需,5ms,，则系统开销所占比率：,5/,（,100+5,）,=4.8%,可变时间片：一轮调度开始时，根据现有就绪进程数目重新计算,q,，以减少当进程数很少时频繁调度的开销。,1,、时间片的轮转法（,RR,：,Round Robin,）,3.2.3,基于时间片的轮转调度算法,CPU,就绪队列,1,（,q1=8ms,）,就绪队列,2,（,q2=16ms,）,就绪队列,3,（,q3=32ms,）,就绪队列,n,（,qn=x ms,）,新进程,CPU,CPU,CPU,能较好地满足交互型作业、短批处理作业、长批处理作业的要求。,2,、多级反馈队列算法：,设立多个就绪队列，优先级越高的队列，其执行的时间片越小；,当进程在一个时间片内未运行完，则降到下一级队列；,当本级队列均无进程就绪时，才调度下级队列内进程；,新进程可以抢占优先级比它低的当前进程；,某队列内进程按,FCFS,法调度，末级队列按时间片轮转法调度。,3.4,实时调度,1,）实时系统(,real-time system),实时：表示,“,及时,”,，实时系统是系统能及时响应外部事件请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。,用于工业过程、军事、金融等实时控制、实时信息处理领域,按任务执行时是否呈现周期性来划分：,周期性实时任务：每隔一段固定的时间发生,非周期性实时任务：在不可预测的时间发生。,截止时间(,deadline),：,开始截止时间（最晚开始时间）,完成截止时间（最晚完成时间）,根据对截止时间的要求来划分：,硬实时任务：存在必须满足的时间限制。,软实时任务,:,可以容忍偶尔超过时间限制。,实时任务的类型：,2,）实现实时调度的基本条件,提供必要的信息,(,就绪时间、截止时间、处理时间、资源要求、资源优先级,),系统处理能力要足够强,:,单处理机情况下：设有,m,个周期性事件，事件,i,的周期为,P,i,，,其中每个事件需要,C,i,秒的,CPU,时间来处理，可调度的的实时系统必须满足：,C,1,/P,1,+C,2,/P,2,+C,m,/P,m,1,采用抢占式调度机制,具有快速切换机制,3,）实时调度算法的分类,1),非抢占式调度算法,:,非抢占式轮转调度算法,(,实时要求不太严格，,s),非抢占式优先调度算法,(,要求比较严格,数百,ms),2),抢占式调度算法,:,基于时钟中断的抢占优先调度算法,(,要求比较严格,数,10ms),立即抢占优先权调度算法,(,紧迫任务,几,ms,甚至百微秒,),图,3-8,实时进程调度,4,）常用的几种实时调度算法,I.,最早截止时间优先即,EDF(Earliest Deadline First),算法,1,）非抢占式调度用于非周期实时任务：最早开始截止时间优先,图,3-9 EDF,算法用于非抢占调度方式,2,）抢占式调度用于周期实时任务：最早完成截止时间优先,II.,最低松弛度优先即,LLF(Least Laxity First),算法,该算法是根据任务紧急,(,或松弛,),的程度，来确定任务的优先级，即,选择松弛度最少的进程执行,该算法。主要用于可抢占调度方式中。,松弛度：即各个进程的富裕时间（裕度,）,松弛度,=,必须完成时间,-,其本身的运行时间,-,当前时间,图,3-12,利用,LLF,算法进行调度的情况,图,3-11,A,和,B,任务每次必须完成的时间,假如在一个实时系统中，有两个周期性实时任务,A,和,B,，任务,A,要求每,20 ms,执行一次，执行时间为,10 ms,；任务,B,只要求每,50 ms,执行一次，执行时间为,25 ms,。,练习,1,对下面的,5,个非周期性实时任务，按最早开始截止时间优先调度算法如何进行,CPU,调度？,(,非抢占式,/,抢占式,),进程,到达时间,执行时间,开始截止时间,A,10,20,110,B,20,20,20,C,40,20,50,D,50,20,90,E,60,20,70,0,10,20,30,40,50,60,70,80,90,100,110,A,B,C,D,E,B,C,E,D,A,到达时间,开始截止时间,练习,2,若有,3,个周期性任务，各任务的周期和执行时间如下表所示，考虑应如何按最低松弛度优先算法对它们进行,CPU,调度？,进程,周期,执行时间,A,20,10,B,50,10,C,50,15,0,10,20,30,40,50,60,70,80,90,100,110,A1,B1,C1,A2,A3,B2,C2,A4,A5,A6,B3,C3,A1,A2,A3,A4,A5,时间,各进程到达时间,必须完成时间,B1C1,B2C2,假设一个系统中有,5,个进程，它们的到达时间和服务时间如下表所示，忽略,I/O,以及其它开销时间。分别按先来先服务,FCFS,、非抢占及抢占的短进程优先,SPF,和最高响应比优先,HRRN,、时间片轮转,RR,法 进行,CPU,调度，分别计算出各进程的周转时间、带权周转时间、平均周转时间和带权的平均周转时间。,进程,到达时间,服务时间,A,0,3,B,2,6,C,4,4,D,6,5,E,8,2,有一个内存中只能装入两道作业的批处理系统，作业调度数是指采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。作业序列如下表所示，表中所列的优先进程调度的优先数，且优