《第三章 处理机调度和死锁优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三章 处理机调度和死锁优秀课件.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 处理机调度和死锁第1页，本讲稿共68页处理机调度处理机调度o进程数目处理机数目o动态分配o由处理机调度程序完成o作业提交处理机调度获得处理机,执行第2页，本讲稿共68页3.1处理机调度的层次处理机调度的层次 3.1.1 高级调度高级调度（作业调度、长程调度、接纳调度）（作业调度、长程调度、接纳调度）-把外存上处于后备队列中的作业调入内存。把外存上处于后备队列中的作业调入内存。1 1作业和作业步作业和作业步(1)(1)作业作业(Job)(Job)。程序和数据。程序和数据+作业说明书。作业说明书。在批处理系统中，是以作业为基本单位从外存调入内存的。(2)(2)作业步作业步(Job Step
2、)(Job Step)。顺序加工步骤。顺序加工步骤。相对独立，相互关联。例如：“编译”作业步，“连结装配”“运行”作业步(3)(3)作业流。输入的作业流；处理作业流。作业流。输入的作业流；处理作业流。第3页，本讲稿共68页2 2作业控制块作业控制块JCB(Job Control Block)JCB(Job Control Block)每个作业设置一个作业控制块，是作业在系统中存在的标志，每个作业设置一个作业控制块，是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。其中保存了系统对作业进行管理和调度所需的全部信息。作业创建JCB后备队列作业调度进入内存结束回收资源撤销J
3、CB 就绪队列3.1.1 高级调度高级调度第4页，本讲稿共68页3 3作业调度作业调度作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。n 调度特性调度特性1.1.接纳作业数（内存驻留数）接纳作业数（内存驻留数）太多太多周转时间周转时间T T长长 太少太少系统效率低系统效率低2.2.接纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短作业优先等、短作业优先等3.1.1 高级调度高级调度第5页，本讲稿共
4、68页 3.1.2 低级调度低级调度（进程调度或短程调度）1 1低级调度的功能低级调度的功能低级调度用于决定就绪队列中的哪个进程(或内核级线程，为叙述方便，以后只写进程)应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。2进程调度中的三个基本机制进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：(1)排队器。(2)分派器(分派程序)。(3)上下文切换机制。第6页，本讲稿共68页3 3进程调度方式进程调度方式1)1)非抢占方式非抢占方式(Nonpreemptive Mode)(Nonp
5、reemptive Mode)不允许抢占正在运行进程的处理机。实现简单，系统开销小 难以满足紧急任务的要求，不适合实时系统 2)2)抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)允许根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。优先权原则。短作业(进程)优先原则。时间片原则。3.1.2 低级调度低级调度第7页，本讲稿共68页 3.1.3 中级调度中级调度（中程调度）o使那些暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。o当这些进程重又具备运行条件且内存又稍
6、有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。o中级调度实际上就是存储器管理中的对换功能第8页，本讲稿共68页3.2.1调度队列模型调度队列模型o一、仅有进程调度的调度队列模型一、仅有进程调度的调度队列模型就就 绪绪 队队 列列CPU阻阻 塞塞 队队 列列交互用户交互用户时间片完时间片完进程调度进程调度等待事件等待事件事事件件出出现现进程完成进程完成3.2 调度队列模型和调度准则调度队列模型和调度准则 第9页，本讲稿共68页o二、具有高二、具有高/低级调度的调度队列模型低级调度的调度队列模型就就 绪绪 队队 列
7、列CPU阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现阻阻 塞塞 队队 列列等待事件等待事件2事件事件2出现出现作业作业调度调度后备队列后备队列N3.2.1调度队列模型调度队列模型第10页，本讲稿共68页三、具有三级调度的调度队列模型三、具有三级调度的调度队列模型就就 绪绪 队队 列列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻阻 塞塞 队队 列列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作
8、业3.2.1调度队列模型调度队列模型第11页，本讲稿共68页3.2.2选择调度方式和算法的若干准则选择调度方式和算法的若干准则 o一、面向用户的准则一、面向用户的准则n1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）o概念：作业从提交概念：作业从提交 完成的时间完成的时间.o分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间第12页，本讲稿共68页o一、面向用户的准则一、面向用户的准则n平均周转时间平均周转时间 n平均带权周转时间平均带权周转时间 n可见带权可见带权W W
9、越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。3.2.2选择调度方式和算法的若干准则选择调度方式和算法的若干准则 第13页，本讲稿共68页o一、面向用户的准则一、面向用户的准则n2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业）o概念：键盘提交请求到首次响应的时间概念：键盘提交请求到首次响应的时间（1 1）输入传送时间）输入传送时间（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间n3 3截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）n4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）3.2.2选择调度方式和算法的若干准
10、则选择调度方式和算法的若干准则 第14页，本讲稿共68页o二、面向系统的准则二、面向系统的准则n1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数n2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型多贵，特别于大中型多用户系统）用户系统）n3 3各类资源的平衡利用。各类资源的平衡利用。3.2.2选择调度方式和算法的若干准则选择调度方式和算法的若干准则 第15页，本讲稿共68页 3.3 调度算法调度算法 是一个资源分配问题是一个资源分配问题 o3.3.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法
11、 n1.1.先来先服务调度算法先来先服务调度算法FCFSFCFSo特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业进程名到达时间 服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99第16页，本讲稿共68页3.3.1先来先服务和短作业（进程）优先调先来先服务和短作业（进程）优先调度算法度算法2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F 选出估计运行时间最短的作业（进程）选出估计运行时间最短的作业（进程）提高了平均周转时间
12、和平均带权周转时间（从而提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）提高了系统吞吐量）对长作业不利，有可能得不到服务（饥饿）对长作业不利，有可能得不到服务（饥饿）未考虑作业的紧迫性未考虑作业的紧迫性 估计时间不易确定估计时间不易确定第17页，本讲稿共68页图3.4 FCFS和SJF比较进程名进程名 A B C D E平均平均到达时间到达时间 0 1 2 3 4服务时间服务时间 4 3 5 2 4FCFS完成时间完成时间 4 7 12 14 18周转时间周转时间 4 6 10 11 149带权周转时间带权周转时间 1 2 2 5.5 3.52.8SJF完成时间完成时间 4 9 1
13、8 6 13周转时间周转时间 4 8 16 3 98带权周转时间带权周转时间 1 2.67 3.1 1.5 2.252.10417231241418ABCDEFCFS041923184613ABCDESJF第18页，本讲稿共68页3.3.2高优先权优先调度算法高优先权优先调度算法o1.1.优先权调度算法类型优先权调度算法类型n非抢占式优先权算法非抢占式优先权算法n抢占式优先权算法，实时性更好。抢占式优先权算法，实时性更好。o2.2.优先权类型：优先权类型：n1 1静态优先权：静态优先权：o进程优先权在整个运行期不变。进程优先权在整个运行期不变。o确定优先权依据确定优先权依据n（1 1）进程类型
14、）进程类型n（2 2）进程对资源的需求；）进程对资源的需求；n（3 3）根据用户需求。）根据用户需求。o特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。第19页，本讲稿共68页3.3.2高优先权优先调度算法高优先权优先调度算法(2)o2 2动态优先权：动态优先权：n如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时间而升高。n响应比响应比Rp=Rp=（等待时间服务时间）（等待时间服务时间）/服务时间服务时间 作为优先权作为优先权n优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRpo3.3.高响应比优先算法：高响
15、应比优先算法：n特点：特点：n响应比响应比Rp=Rp=（tw+tstw+ts）/ts/tsn（1 1）短作业）短作业RPRP大。大。n（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。n（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。第20页，本讲稿共68页3.3.3基于时间片的轮转调度算法基于时间片的轮转调度算法o1.1.时间片轮转时间片轮转n时间片大小的确定时间片大小的确定o太大：退化为太大：退化为FCFSFCFS；o太小：系统开销过大太小：系统开销过大n系统对响应时间的要求；系统对响应时间的要求；T=nqT
16、=nqn就绪队列中进程的数目；就绪队列中进程的数目；n系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个时间片处理完常用命令）第21页，本讲稿共68页v2.2.多级反馈队列调度多级反馈队列调度1.多个就绪队列，不同优先级多个就绪队列，不同优先级2.2.新进程首先进入第一队列尾，新进程首先进入第一队列尾，FCFSFCFS；时间片结束后未；时间片结束后未完成的进入第二队列完成的进入第二队列尾尾3.3.第一队列空闲时才调度第二队列，抢占式第一队列空闲时才调度第二队列，抢占式3.3.3基于时间片的轮转调度算法（基于时间片的轮转调度算法（2）n特点：长、短作业兼顾，有较好的响
17、应时间特点：长、短作业兼顾，有较好的响应时间o（1 1）短作业一次完成；）短作业一次完成；o（2 2）中型作业周转时间不长；）中型作业周转时间不长；o（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。第22页，本讲稿共68页就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2Available(2,3,0)(2)Request4(3,3,0)Available(2,3,0)，让，让P4P4等待。等待。（4 4）P0 P0请求资源请求资源 P P0 0发出请求向量发出请求
18、向量Request0(0,2,0),Request0(0,2,0),系统按银行家算法进行检查：系统按银行家算法进行检查：(1 1)RequestRequest0 0(0,2,0)(0,2,0)N Needeed0 0(7,4,3);(7,4,3);(2)Request (2)Request0 0(0,2,0)Available(2,3,0)(0,2,0)Available(2,3,0)，(3)(3)进行安全性检查进行安全性检查 可用资源可用资源Available2,1,0Available2,1,0已不能满足任何进程的需要，故系统进入不安全状已不能满足任何进程的需要，故系统进入不安全状态，此时
19、系统不分配资源。态，此时系统不分配资源。3.6.3利用银行家算法避免死锁利用银行家算法避免死锁 第58页，本讲稿共68页3.7死锁的检测和解除死锁的检测和解除3.7.1、死锁的检测死锁的检测o系统必须须提供检测和解除死锁的手段：系统必须须提供检测和解除死锁的手段：（1 1）保存有关资源的请求和分配信息；）保存有关资源的请求和分配信息；（2 2）提供算法以利用这些信息来检测系统是否进入死锁。）提供算法以利用这些信息来检测系统是否进入死锁。1 1、资源分配图（、资源分配图（Resource Ailocation GraphResource Ailocation Graph）系统死锁可利用资源分配图
20、来描述。系统死锁可利用资源分配图来描述。G=G=（N N，E E）：）：（1 1）N N分为两个互斥的子集，进程结点分为两个互斥的子集，进程结点P=P=（P P1 1，P P2 2,P,Pn n）,资源结点资源结点R=R=rr1 1,r,r2 2,r,rn n,N=PR,N=PR。（2 2）E E中的边中的边eE,eE,都连接着都连接着P P中的一个结点和中的一个结点和R R中的一个结点，中的一个结点，e=pe=pi i,r,rj j 是是资源请求边，由进程资源请求边，由进程p pi i指向资源指向资源r rj j,它表示进程它表示进程p pi i请求一个单位的请求一个单位的r rj j资源。
21、资源。第59页，本讲稿共68页p1p2R2R1分配请求3.7.1死锁的检测死锁的检测第60页，本讲稿共68页2 2、死锁定理、死锁定理o简化资源分配图来检测系统处于简化资源分配图来检测系统处于S S状态时，是否为死锁状态。简化方状态时，是否为死锁状态。简化方法如下：法如下：（1 1）在资源分配图中，找出一个既不阻塞又非独立的进程结点）在资源分配图中，找出一个既不阻塞又非独立的进程结点p pi i。在顺利情。在顺利情况下，况下，p pi i可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当于消去部资源。这相当于消去p
22、 pi i所有的请求边和分配边，使之成为孤立的结点。所有的请求边和分配边，使之成为孤立的结点。p1p2R2R1p1p2R2R13.7.1死锁的检测死锁的检测第61页，本讲稿共68页（2 2）p1p1释放资源后，便可使释放资源后，便可使p2p2获得资源而继续运行，直到获得资源而继续运行，直到p2p2完完成又释放出它所占有的全部资源，而形成图（成又释放出它所占有的全部资源，而形成图（c c）所示的情况。）所示的情况。（3 3）在进行一系列的简化中，若能消去图中所有的边，使所有进程都）在进行一系列的简化中，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是成为孤立结点，则称该图是可完全简化可
23、完全简化的，若不能通过任何过程使的，若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。该图完全简化，则称该图是不可完全简化的。p1p2R1p1p2R1R2R23.7.1死锁的检测死锁的检测第62页，本讲稿共68页2 2、死锁定理、死锁定理oS S为死锁状态的充分条件是：当且仅当状态为死锁状态的充分条件是：当且仅当状态S S的资源分配图是不可完全简化的。的资源分配图是不可完全简化的。3.7.1死锁的检测死锁的检测第63页，本讲稿共68页可完全简化可完全简化?p1p3R1p23.7.1死锁的检测死锁的检测第64页，本讲稿共68页3 3、死锁检测中的数据结构、死锁检测中的数据结构死锁检测中
24、的数据结构，类似于银行家算法中的数据结构：死锁检测中的数据结构，类似于银行家算法中的数据结构：可利用资源向量可利用资源向量AvailableAvailable。它表示了。它表示了m m类资源中的每一类资源的类资源中的每一类资源的可用数目。可用数目。把不占用资源的进程向量把不占用资源的进程向量AllocationAllocation：=0=0记入表记入表L L中，即中，即L Li iLL。从进程集合中找到一个从进程集合中找到一个RequestRequesti iWorkWork的进程，做如下处理：的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量将其资源分配图简化，释放出资源，增加
25、工作向量Work Work：=Work+Allocation=Work+Allocation。将它记入将它记入L L表中。表中。3.7.1死锁的检测死锁的检测第65页，本讲稿共68页若不能把所有的进程都记入若不能把所有的进程都记入L L表中，则表明系统状态表中，则表明系统状态S S的资源分的资源分配图是不完全简化的，因此，该系统状态将发生死锁。配图是不完全简化的，因此，该系统状态将发生死锁。Work:=Available;Work:=Available;L:=L L:=Li i|Allocation|Allocationi i=0=0RequestRequesti i=0=0 for all
26、L for all Li i!L L dodo begin begin for all RequestiWork do for all RequestiWork do begin begin Work:=Work+Work:=Work+AllocationAllocationi i;L Li iL;L;end end end end deadlock:=deadlock:=(L=P(L=P1 1,P,P2 2,P,Pn n););3.7.1死锁的检测死锁的检测第66页，本讲稿共68页3.7.2死锁的解除死锁的解除当发现有进程死锁时，便应立即把它们从死锁状态中解脱出当发现有进程死锁时，便应立即把
27、它们从死锁状态中解脱出来，常采用的方法：来，常采用的方法：（1 1）剥夺资源剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；以解除死锁状态；（2 2）撤消进程撤消进程。最简单的撤消进程方法，是使全部死锁进。最简单的撤消进程方法，是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用死锁状态消除为止。地撤消进程，直至有足够的资源可用死锁状态消除为止。在出现死锁时，可采用各种策略来撤消进程。例如，为在出现死锁时，可采用各种策略来撤消进程。例如，为解除死锁状态所需的进程数目最小；或者，撤消进程所付解除死锁状态所需的进程数目最小；或者，撤消进程所付出的代价最小等。出的代价最小等。第67页，本讲稿共68页作业oP115-13、18、22第68页，本讲稿共68页