os_ch3处理机调度与死锁.ppt

1,第三章处理机调度与死锁,2,本章主要内容,处理机调度层次调度队列调度算法死锁概念死锁处理方式：预防；避免；检测；解除。,3,Question,什么是调度？常用操作系统类型?,4,3.1处理机调度的层次和调度算法的目标,3.3.1处理机调度的层次高级调度中级调度低级调度,5,处理机调度的层次,6,处理机调度与进程状态转换,7,调度队列模型,1.仅有进程调度的调度队列模型,8,2.具有高级和低级调度的调度队列模型,调度队列模型,9,3.同时具有三级调度的调度队列模型,10,3.1.2处理机调度算法的目标,1.共同目标：资源利用率；公平；平衡；2.批处理系统的目标：平均周转时间短；平均带权周转时间系统吞吐量高；处理机利用率高,11,3.1.2处理机调度算法的目标,3.分时系统的目标：响应时间快；均衡4.实时系统的目标：截止时间保证；可预测性,12,3.2作业与作业调度,3.2.1批处理系统中的作业作业和作业步作业控制块（JCB）作业三种状态：收容，运行，完成,13,3.2.2作业调度的主要任务,接纳多少个作业接纳哪些作业,14,3.2.3作业调度算法,1先进先出算法（FCFS）按照作业进入后备队列的先后次序，先进入后备队列的作业优先被挑选装入内存。算法容易实现，效率不高，用于作业调度和进程调度。有利于长作业，不利于短作业。,15,2短作业优先调度算法,短作业优先调度算法SJF，是指对短作业优先调度的算法。可以用于作业调度和进程调度。,16,17,18,SJF调度算法的缺点,(1)该算法对长作业不利。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,19,3.高响应比优先调度算法,20,3.3进程调度,3.3.1进程调度的任务、机制和方式1.低级调度的功能（1）保存处理机的现场信息（2）按照某种算法选取进程（3）把处理机分配给进程2.进程调度中的三个基本机制（1）排队器（2）分派器（3）上下文切换机制,21,3.进程调度方式（1)非抢占方式(Non-preemptiveMode)可能引起进程调度的因素：正在执行的进程执行完毕，或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语,22,（2）抢占方式（PreemptiveMode)允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给进程的处理机重新分配给另一进程。抢占的原则有：优先权原则。短作业(进程)优先原则。时间片原则。,23,3.3.2时间片轮转调度算法,时间片轮转调度算法：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。,24,时间片轮转调度算法,时间片大小确定轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。,25,时间片轮转调度算法,时间片取选时间片取值太小，多数进程不能在一个时间片内运行完毕，切换就会频繁，开销显著增大，从系统效率来看，时间片取大一点好。时间片取值较大，随就绪队列里进程数目增加，轮转一次的总时间增大，对进程的响应速度放慢了。为满足响应时间要求，要么限制就绪队列中进程数量，要么采用动态时间片法，根据负载状况，及时调整时间片的大小。,26,时间片轮转调度算法,时间片取选时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。,27,3.3.3优先级调度算法,1.优先权调度算法的类型（1）非抢占式优先权算法批处理系统（2）抢占式优先权调度算法实时系统,28,2.优先权的类型（1）静态优先权：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。确定进程优先权的依据有如下三个方面：进程类型。进程对资源的需求。用户要求。,29,（2）动态优先权动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,30,动态优先数法基本原则：根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长,在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。,31,UNIX动态优先数计算公式,Switch:采用动态优先数法p_pri=p_cpu/2+PUSER+p_nice+NZERO2520,.计算方法：1.每个时钟周期,当前进程p_cpu+1;2.每秒钟时钟中断时，全部进程的p_cpu/2，计算所有进程的p_pri,若当前进程不是最小，设调度标志3.进程从中断或陷入返回时，计算当前进程的p_pri,32,UNIX动态优先数调度效果,(1)如果一个进程连续占用处理机较长时间，那么，它的p-cpu值就增大，计算出的p-pri也增大，于是优先权下降。(2)如果一个进程长时间未被调用到或者虽频繁调度到，但每次占用的时间都小于200ms，那么，p-cpu就较小甚至为0，从而，计算出的p-pri也较小，于是优先权上升。,33,3.3.5多级反馈队列调度算法,算法主要思想:系统设立多级就绪队列，分别具有不同的优先级，每一级就绪队列按照时间片轮转算法调度，优先级高的队列时间片短；新进程插入第一级就绪队列末尾；若进程执行过程中时间片到还没有完成，则插入下一级就绪队列；每次调度都是选择第一级队列上的进程执行，仅当上一级队列空时，才调度下一级队列上的进程。,34,35,多级反馈队列调度算法的性能(1)终端型作业用户(2)短批处理作业用户(3)长批处理作业用户,36,课后作业,1.处理机调度有几种层次？分别完成什么功能？2.假设一个系统中有5个进程，到达时间为0，2，4，6，8，服务时间为3，6，4，5，2，忽略I/O以及其他开销时间，若分别按FCFS，时间片轮转RR(R=2)，多级反馈队列FB(R=2i-1)调度算法进行CPU调度，计算各进程的完成时间，周转时间，带权周转时间，平均带权周转时间。3.总结进程调度有哪些调度时机（何时进行进程调度）,37,3.4实时调度（略）,38,3.5死锁概述,3.5.1资源问题1.可重用性资源和消耗性资源2.可抢占性资源和不可抢占性资源,39,3.5.2产生死锁的原因,竞争资源。进程间推进顺序非法。,40,竞争资源引起进程死锁竞争不可抢占性资源竞争可消耗性资源,41,图3-12共享设备/文件时的死锁情况,42,图3-13进程之间通信时的死锁,43,2.进程推进顺序不当引起死锁,44,3.5.3死锁的定义、必要条件,1.死锁的定义如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的时间，那么该组进程就是死锁。,45,3.5.3死锁的定义、必要条件,2.死锁的必要条件互斥条件请求和保持条件不可抢占条件循环等待条件,46,3.5.3死锁的定义、必要条件,3处理死锁的方法预防死锁避免死锁检测死锁解除死锁,47,3.6预防死锁,3.6.1预防死锁破坏“请求和保持”条件破坏“不可抢占”条件破坏“循环等待”条件,48,3.7避免死锁,3.7.1系统安全状态1.安全状态所谓安全状态，是指系统能按某种进程顺序(P1,P2,，Pn)(称P1,P2,Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,49,2.安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,50,3.由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。,51,3.7.2利用银行家算法避免死锁,银行家拥有一笔周转资金客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款银行家应谨慎的贷款，防止出现坏帐,52,用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）,53,单项资源的银行家算法,4个客户每个都有一个贷款额度,安全状态,不安全状态,54,多项资源的银行家算法,总的资源E、已分配资源P、剩余资源A,55,银行家算法中的数据结构,(1)可利用资源向量Available:Availablej=K，则表示系统中现有Rj类资源K个(2)最大需求矩阵Max。Maxi,j=K，表示进程i需要Rj类资源的最大数目为K(3)分配矩阵Allocation。Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。(4)需求矩阵Need。Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。,56,银行家算法,ifRequestijNeedi,jthenelseifRequestijAvailablejthenelsedefinenewstateby:Allocationi,j:=Allocationi,j+RequestijAvailablej:=Availablej-RequestijNeedi,j:=NeedI,j-Requestijend;ifsafe(newstate)thencarryoutallocationelserestoreoriginalstatesuspendprocessendend,57,3.安全性算法,functionsafe(state:s):boolean;/*bankersalgorithm*/work:array0m-1ofinteger;/工作向量finish：array0.n-1ofboolean;/进程是否能够获得足够资源，运行完成beginwork:=available;for(i=0;in;i+)finishi:=false;possible:=true;whilepossibledofindaPksuchthatfinishk=false;Needk,jworkjl;iffoundthenwork:=work+Allocationk,*;finishk:=true;elsepossible:=false;ifallfinishi=truesafe:=true;elsesafe:=false;end.,58,4银行家算法举例,processAllocationClaimNeed=CkiAkiABCABCP0010753743P1200322122P2302902600P3211222011P4002433431Available:332,59,4银行家算法举例,进程P0申请资源request0=(1,0,2),检查request0Available、比较(1,0,2)(7，5，3),结果满足条件,试分配,得到新状态：processAllocationClaimAvailableABCABCABCP0112753230P1200322P2302902P3211222P4002433,60,3.8死锁的检测和解除,3.8.1死锁的检测,1.资源分配图(ResourceAllocationGraph),图3-20每类资源有多个时的情况,61,进程-资源分配图PRAG(1),62,进程-资源分配图PRAG(2),63,(1)如果进程-资源分配图中无环路，则此时系统没有发生死锁。(2)如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。,64,(3)如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。,65,如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理。,66,3.8.2死锁的解除,立即结束所有进程的执行，并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。撤销陷于死锁