chapter3new

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 处理机调度与死锁,1,第三章 处理机调度与死锁,3.1,处理机调度的基本概念,3.2,进程调度算法,3.3,实时调度,3.4,多处理机系统中的调度,3.5,产生死锁的原因和必要条件,3.6,预防死锁的方法和死锁避免,3.7,死锁的检测和解除,2,3.1,处理机调度的基本概念,在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。,3,进程调度要解决的问题,WHAT,：按什么原则分配,CPU,进程调度算法,WHEN,：何时分配,CPU,进程调度的时机,HOW,： 如何分配,CPU,CPU,调度过程（进程的上下文切换）,4,1.,高级、中级和低级调度,处理机是计算机系统中的重要资源,处理机调度算法对整个计算机系统的综合性能指标有重要影响,可把处理机调度分成三个层次：,高级调度,中级调度,低级调度,5,高级调度,也称为作业调度或宏观调度,高级调度的时间尺度通常是分钟、小时或天,中级调度,涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问,低级调度,也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效,6,2.,进程调度的任务,进程调度的任务是控制协调进程对,CPU,的竞争,即按一定的调度算法从就绪队列中选中一个进程，把,CPU,的使用权交给被选中的进程,7,3.,确定算法的原则,具有公平性,资源利用率高（特别是,CPU,利用率）,在交互式系统情况下要追求响应时间（越短越好）,在批处理系统情况下要追求系统吞吐量,8,4.,进程调度方式,非剥夺方式,(Non-preemptive Mode),：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。可能情况正在执行的进程正常或异常执行完毕、提出,I/O,请求而暂停执行、执行某种原语（,P,、,Block,、,Wakeup,）等,剥夺方式,(Preemptive Mode),：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。,9,5.,进程调度性能衡量的主要指标,周转时间,响应时间,10,6.,进程调度模型,1),只有进程调度的调度队列模型,图,3 - 1,仅具有进程调度的调度队列模型,11,2),具有高低级调度的调度队列模型,图,3-2,具有高、低两级调度的调度队列模型,12,3),具有三级调度的调度队列模型,图,3-3,具有三级调度时的调度队列模型,13,7.,选择进程调度方式的准则,面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则,面向系统的准则：系统吞吐量高；,处理机利用率好；各类资源的平衡利用,14,3.2,进程调度算法,先进先出,(FIFO),算法,最短,CPU,运行期优先调度算法,最高优先权优先调度算法,轮转法,多级反馈队列,15,1.,先进先出,(FIFO),算法,该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。,优点,:,实现简单,.,缺点,:,没考虑进程的优先级,16,2.,最短,CPU,运行期优先调度算法,该算法从就绪队列中选出,“,下一个,CPU,执行期,”,最短的进程，为之分配处理机。,该算法虽可获得较好的调度性能，但难以准确地知道下一个,CPU,执行期，而只能根据每一个进行的执行历史来预测。,17,图,3-4 FCFS,和,SJF,调度算法的性能,3.,FCFS,和,SJF,的性能比较,18,4.,最高优先权优先调度算法,该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权,(,优先级根据优先数来决定,),静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。,动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,19,5.,高响应比优先调度算法,优先权,(,响应比,),的变化规律可描述为：,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比,R,P,又可表示为：,20,6.,轮转法,把,CPU,划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有,CPU,，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的,CPU,，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,简单轮转法：系统将所有就绪进程按,FIFO,规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。,多级队列方法：将系统中所有进程分成若干类，每类为一级。,21,7.,分时系统中常用时间片轮转法,时间片选择问题,：,固定时间片,可变时间片,与时间片大小有关的因素：,系统响应时间,就绪进程个数,CPU,能力,22,1),简单轮转法的调度模型,23,2),多队列反馈调度算法,将就绪队列分为,N,级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，,.,当运行进程用完一个时间片，放弃,CPU,时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列,24,*,首先系统中设置多个就绪队列,* 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大,* 各个队列按照先进先出调度算法,* 一个新进程就绪后进入第一级队列,* 进程由于等待而放弃,CPU,后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列,* 当有一个优先级更高的进程就绪时，可以抢占,CPU,，被抢占进程回到原来一级就绪队列末尾,* 当第一级队列空时，就去调度第二级队列，如此类推,* 当时间片到后，进程放弃,CPU,，回到下一级队列,25,3),多队列反馈调度算法,26,8.,进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行,当一个进程在运行中处于等待状态（等待,I/O,）,分时系统中时间片到,当有一个优先级更高的进程就绪（可抢占式）,例如：新创建一个进程，一个等待进程变成就绪,在进程通信中，执行中的进程执行了某种原语操作（,P,操作，阻塞原语，唤醒原语）,27,何时切换进程,只要,OS,取得对,CPU,的控制，进程切换就可能发生，如,:,超级用户调用,来自程序的显式请求,(,如：打开文件,),，该进程通常会被阻塞,陷阱,某一条指令出错，导致进程移至退出状态,中断,外部因素影响当前指令的执行，控制被转移至,IH,（中断处理程序）,28,9.,引起进程调度的原因,正在执行的进程执行完毕或因发生某事件而不能再继续执行；,执行中的进程因提出,I/O,请求而暂停执行；,在进程通信或同步过程中执行了某种原语操作如,P,操作、阻塞、挂起原语等；,在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；,在时间片轮转法中，时间片完。,通常系统是按先来先服务或优先权形式来组织调度队列。,29,3.3,实 时 调 度,1.,实现实时调度的基本条件,提供必要的信息,(,就绪时间、截止时间、处理时间、资源优先级,),系统处理能力强,采用抢占式调度机制,具有快速切换机制,30,2.,实时调度算法的分类,1),非抢占式调度算法,:,非抢占式轮转调度算法,非抢占式优先调度算法,2),抢占式调度算法,:,基于时钟中断的抢占优先调度算法,立即抢占优先权调度算法。,31,图,3-5,实时进程调度,32,3.,常用的几种实时调度算法,1,）最早截止时间优先即,EDF(Earliest Deadline First),算法,图,3-6 EDF,算法用于非抢占调度方式,33,2,）最低松弛度优先,(LLF),算法,该算法是根据任务紧急,(,或松弛,),的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。,假如在一个实时系统中，有两个周期性实时任务,A,和,B,，任务,A,要求每,20 ms,执行一次，执行时间为,10 ms,；任务,B,只要求每,50 ms,执行一次，执行时间为,25 ms,。,图,3-7 A,和,B,任务每次必须完成的时间,34,在刚开始时,(,t,1,=0),，,A,1,必须在,20ms,时完成，而它本身运行又需,10 ms,，可算出,A,1,的松弛度为,10ms,；,B,1,必须在,50ms,时完成， 而它本身运行就需,25 ms,，可算出,B,1,的松弛度为,25 ms,，故调度程序应先调度,A,1,执行。在,t,2,=10 ms,时，,A,2,的松弛度可按下式算出：,A,2,的松弛度,=,必须完成时间,-,其本身的运行时间,-,当前时间,=40 ms-10 ms-10 ms=20 ms,类似地，可算出,B1,的松弛度为,15ms,，调度程序应选择,B2,运行。,t,3=30 ms,时，,A2,的松弛度已减为,0,，,B1,的松弛度为,15 ms,，于是调度程序应抢占,B1,的处理机而调度,A2,运行,.,图,3-8,利用,ELLF,算法进行调度的情况,35,3.4,多处理机系统中的调度,提高计算机系统性能的主要途径有：,提高构成计算机的元器件的运行速度，特别是处理器芯片的速度,改进计算机系统的体系结构，特别是在系统中引入多个处理器或多台计算机，以实现对信息的高度并行处理，达到提高系统吞吐量和可靠性的目的。,70,年代出现了多处理器系统即,MPS,，,90,年代中期，功能较强的主机系统和服务器，都采用了多处理机系统。,36,多处理机系统中的调度,1.,多处理器系统的类型,从多处理器之间的耦合紧密程度分：,(1),紧密耦合,(Tightly Coupted)MPS,。,共享主存系统和,I/O,设备，并要求将主存划分为若干个能独立访问的存储器模块，以便多个处理器能同时对主存进行访问。系统中的所有资源和进程，都由操作系统实施统一的控制和管理。,(2),松散耦合,(Loosely Coupled)MPS,。,37,每台计算机有自己的存储器和,I/O,设备，并配置了,OS,来管理本地资源和在本地运行的进程,多处理机系统中的调度,2.,对称多处理器系统和非对称多处理器系统,根据系统中所用处理器的相同与否分：,(1),对称多处理器系统,(Symmetric MultiProcessor Syetem,）,SMPS,在系统中所包含的各处理单元，在功能和结构上都是相同的，例如,IBM,公司的,SR/6000 Model F50,(2),非对称多处理器系统,系统中有多种类型的处理单元，它们的机构和功能各不相同，只有一个主处理器，有多个从处理器,38,多处理机系统中的调度,3.,进程分配方式,(1),对称多处理器系统中的进程分配方式,静态分配,(Static Assigenment),方式,一个进程从开始执行直至其完成，都固定地分配到一个处理器上去执行。每一处理器设置一专用的就绪队列。优点是进程调度开销小，缺点是各处理器忙闲不均,动态分配,(Dynamic Assgement),方式,在系统中仅设置一个公共就绪队列。克服了忙闲不均现象，对紧密耦合系统不增加系统开销，松散耦合系统明显增加,39,多处理机系统中的调度,(2),非对称,MPS,中的进程分配方式,非对称,MPS,，,OS,大多采用主,从（,Master-Slave,）式，即核心部分驻留在一台主机上，而从机上只是用户程序，进程调度只由主机执行。从机空闲时，便向主机发送一请求进程信号，然后等待主机为它分配进程。在主机上保持有一个就绪队列，只要不空，主机便从其队首摘下一个进程分配给请求的从机。优点系统处理比较简单，缺点不可靠，主机一旦出现故障，整个系统瘫痪，容易形成瓶颈,40,多处理机系统中的调度,4.,进程,(,线程,),调度方式,(1,）自调度,(Self-Scheduling),方式,1,）自调度机制,最简单的调度方式，直接由单处理机环境下的调度方式演变而来。在系统中设置一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列中取得一个进程或线程来运行。可采用单处理机环境下的调度算法,FCFS,、,FPF,或抢占式,FPF,。,90,年，,Leutenegger,等研究发现,FCFS,算法在多处理机环境下反而优于其它两种算法,41,多处理机系统中的调度,(1,）自调度,(Self-Scheduling),方式,1,）自调度方式的优点,容易将单处理机环境下的调度机制移植到多处理机系统，其次不会发生处理机忙闲不均现象，利于提高处理器的利用率,2,）自调度方式的缺点,瓶颈问题：一个就绪队列互斥访问,低效性：阻塞重新调度很少仍在阻塞前的处理器上运行，高速缓存单使用率低,线程切换频繁：相互合作的线程很难同时或得处理器同时运行，某些线程因其合作线程阻塞而被切换下来,42,多处理机系统中的调度,（,2,）成组调度,(Gang Scheduling),方式,解决自调度方式中线程被频繁切换问题提出的，将一个进程中的一组线程分配到一组处理器上去执行。为应用程序分配处理器时间可采用如下两种方式：,1,）面向所有应用程序平均分配处理器时间,假定系统中有,N,个处理器和,M,个应用程序，每个应用程序至多含有,N,个线程，则每个应用程序至多可有,1/M,的时间去占有,N,个处理器,2,）面向所有线程平均分配处理器时间,书上,P88,图,43,多处理机系统中的调度,成组调度方式的主要优点：,如果一组相互合作的进程或线程能并行执行，则有效地减少线（进）程阻塞情况的发生，减少线程的切换，使系统性能得到改善；,每次调度都可以解决一组线程的处理器分配问题，显著减少调度频率，减少系统开销,44,多处理机系统中的调度,（,3,）专用处理器分配,(Dedicated Processor Assigement),方式,1989,年,Tucker,提出专用处理器分配方式。该方式是指在一个应用程序的执行期间，专门为该应用程序分配一组处理器，每一个线程一个处理器。这组处理器仅供该应用程序专用，直至该应用程序完成。,明显造成处理机的严重浪费。这种调度方式用于并发程度相当高的多处理器环境，因为：在具有数十个乃至数百个处理器的高度并行系统中，单个处理器的利用率不像单机系统那么重要，其次完全避免切换，大大加速了程序的运行,45,第三章,处理机调度与死锁,3.5,产生死锁的原因和必要条件,46,3.5.1,死锁的概念,1.,死锁例子,:,一个由于,申请不同类型资源,而产生死锁的例子,设系统有一台打印机,(R1),一台扫描仪,(R2),，两进程共享这两台设备。,用信号量,S1,表示,R1,是否可用，用信号量,S2,表示,R2,是否可用，,S1,、,S2,初值为,1,。,47,死锁例子,这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁。,48,2.,死锁概念,指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。,即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。,49,3.,关于死锁的一些结论,参与死锁的进程最少是两个,参与死锁的进程至少有两个已经占有资源,参与死锁的所有进程都在等待资源,参与死锁的进程是当前系统中所有进程的子集,注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,50,4.,永久性资源和临时性资源,永久性资源：可以被多个进程多次使用（可再用资源）,可抢占资源,不可抢占资源,临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）,“,申请,-,分配,-,使用,-,释放,”,模式,51,3.5.2,产生死锁的原因,1.,竞争系统资源,2.,进程的推进顺序不当,52,1.,竞争系统资源,若系统中只有一台打印机,R1,和一台读卡机,R2,，可供进程,P1,和,P2,共享。若,形成环路,，这样会产生死锁。,53,2.,进程的推进顺序不当,在进程,P1,和,P2,并发执行时，按照左图曲线,所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线,的顺序推进时，进入不安全区,D,内，两进程再推进会产生死锁。,54,3.5.3,产生死锁的必要条件,互斥条件,（资源独占）,请求和保持条件,（部分分配，占有申请）,不剥夺条件（,不可强占）,环路等待条件。,55,解决死锁的基本办法,预防死锁,避免死锁,检测死锁,解除死锁,56,3.6,预防死锁的方法和避免死锁,1.,预防死锁的方法,在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。,1),资源一次性分配；,(,破坏请求和保持条件,),2),可剥夺资源；,即当某进程新的资源未满足时，释放已占有的资源,(,破坏不可剥夺条件,),3),资源有序分配法,；做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反,(,破坏环路等待条件,),57,2.,死锁避免,死锁避免定义,:,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。,由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。,58,3.,安全状态与不安全状态,安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。,59,1),安全序列,一个进程序列,P,1,，,，,P,n,是安全的，如果对于每一个进程,P,i,(1,i,n,），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程,P,j,(j i ),当前占有资源量之和，系统处于安全状态。,(,安全状态一定是没有死锁发生的,),60,2),安全状态之例,我们通过一个例子来说明安全性。假定系统中有三个进程,P,1,、,P,2,和,P,3,，共有,12,台磁带机。进程,P,1,总共要求,10,台磁带机，,P,2,和,P,3,分别要求,4,台和,9,台。假设在,T,0,时刻，进程,P,1,、,P,2,和,P,3,已分别获得,5,台、,2,台和,2,台磁带机，尚有,3,台空闲未分配，如下表所示：,进 程,最 大 需 求,已 分 配,可 用,P,1,P,2,P,3,10,4,9,5,2,2,3,61,3),由安全状态向不安全状态的转换,如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在,T,0,时刻以后，,P,3,又请求,1,台磁带机，若此时系统把剩余,3,台中的,1,台分配给,P,3,，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的,2,台分配给,P,2,，这样，在,P,2,完成后只能释放出,4,台，既不能满足,P,1,尚需,5,台的要求，也不能满足,P,3,尚需,6,台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。,62,安全状态与不安全状态,不安全状态,:,不存在一个安全序列，不安全状态一定导致死锁,63,4.,利用银行家算法避免死锁,1),银行家算法中的数据结构,(1),可利用资源向量,Available,。这是一个含有,m,个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果,Available,j,=K,，则表示系统中现有,R,j,类资源,K,个。,64,(2),最大需求矩阵,Max,。这是一个,n,m,的矩阵，它定义了系统中,n,个进程中的每一个进程对,m,类资源的最大需求。如果,Max,i,j,=K,，则表示进程,i,需要,R,j,类资源的最大数目为,K,。,(3),分配矩阵,Allocation,。这也是一个,n,m,的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果,Allocation,i,j,=K,，则表示进程,i,当前已分得,R,j,类资源的数目为,K,。,(4),需求矩阵,Need,。这也是一个,n,m,的矩阵，用以表示每一个进程尚需的各类资源数。如果,Need,i,j,=,K,，则表示进程,i,还需要,R,j,类资源,K,个，方能完成其任务。,Need,i,j,=Max,i,j,-Allocation,i,j,65,2),银行家算法,设,Request,i,是进程,P,i,的请求向量，如果,Request,i,j,=,K,，表示进程,P,i,需要,K,个,R,j,类型的资源。当,P,i,发出资源请求后，系统按下述步骤进行检查：,(1),如果,Request,i,j,Need,i,j,，便转向步骤,2,；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。,(2),如果,Request,i,j,Available,j,，便转向步骤,(3),；否则， 表示尚无足够资源，,P,i,须等待。,66,(3),系统试探着把资源分配给进程,P,i,，并修改下面数据结构中的数值：,Available,j,=Available,j,-Request,i,j,;,Allocation,i,j,=Allocation,i,j,+Request,i,j,;,Need,i,j,=Need,i,j,-Request,i,j,;,(4),系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程,P,i,，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程,P,i,等待。,67,3),安全性算法,(1),设置两个向量： 工作向量,Work:,它表示系统可提供给进程继续运行所需的各类资源数目，它含有,m,个元素，在执行安全算法开始时，,Work=Available; Finish:,它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做,Finish,i,=false;,当有足够资源分配给进程时， 再令,Finish,i,=true,。,68,(2),从进程集合中找到一个能满足下述条件的进程： ,Finish,i,=false; Need,i,j,Work,j,； 若找到， 执行步骤,(3),， 否则，执行步骤,(4),。,(3),当进程,P,i,获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：,Work,j,=Work,i,+Allocation,i,j,;,Finish,i,=true;,go to step 2;,(4),如果所有进程的,Finish,i,=true,都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,69,4),银行家算法之例,假定系统中有五个进程,P,0, P,1, P,2, P,3, P,4,和三类资源,A, B, C,，各种资源的数量分别为,10,、,5,、,7,，在,T,0,时刻的资源分配情况如图,3-15,所示。,图,3-8,T,0,时刻的资源分配表,70,(1) ,T,0,时刻的安全性：,图,3-9,T,0,时刻的安全序列,71,(2) P,1,请求资源：,P,1,发出请求向量,Request,1,(1,，,0,，,2),，系统按银行家算法进行检查：,Request,1,(1, 0, 2)Need,1,(1, 2, 2), Request,1,(1, 0, 2)Available,1,(3, 3, 2),系统先假定可为,P,1,分配资源，并修改,Available, Allocation,1,和,Need,1,向量，由此形成的资源变化情况如图,3-15,中的圆括号所示。, 再利用安全性算法检查此时系统是否安全。,72,图,3-10 P,1,申请资源时的安全性检查,73,(3) P,4,请求资源：,P,4,发出请求向量,Request,4,(3,，,3,，,0),，系统按银行家算法进行检查：,Request,4,(3, 3, 0)Need,4,(4, 3, 1);, Request,4,(3, 3, 0) Available(2, 3, 0),，让,P,4,等待。,(4) P,0,请求资源：,P,0,发出请求向量,Requst,0,(0,，,2,，,0),，系统按银行家算法进行检查：,Request,0,(0, 2, 0)Need0(7, 4, 3);, Request,0,(0, 2, 0)Available(2, 3, 0);,系统暂时先假定可为,P,0,分配资源，并修改有关数据，如图,3-18,所示。,74,图,3-11,为,P,0,分配资源后的有关资源数据,75,允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生,一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行,3.7,死锁的检测和解除,76,1.,检测时机,当进程等待时检测死锁,（其缺点是系统的开销大）,定时检测,系统资源利用率下降时检测死锁,77,2.,死锁检测算法,每个进程和资源指定唯一编号,设置一张资源分配表,记录各进程与其占用资源之间的关系,设置一张进程等待表,记录各进程与要申请资源之间的关系,78,1),资源分配表和进程等待表,资源分配表 进程等待表,r1 p2 p1 r1,r2 p5 p2 r3,r3 p4 p4 r4,r4 p1,79,2),资源分配表和进程等待表,当进程,P4,申请资源,3,时，会产生死锁吗？,80,3),检测算法,81,3.,死锁的解除,重要的是以最小的代价恢复系统的运行。方法如下：,1,）重新启动,2,）撤消进程,3,）剥夺资源,4,）进程回退,82,4.,资源分配图,用有向图描述进程的死锁,准确、形象,系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例,83,资源分配图,二元组,G=,（,V,，,E,）,V,：结点集，分为,P,，,R,两部分,P=p1,p2,pn, R=r1,r2,rm,E,：边的集合，其元素为有序二元组,: (pi,rj),或,(rj,pi),表示法,:,资源类,:,用方框表示（资源的不同类型）,资源实例,:,用方框中的黑圆点表示（存在于每个资源中）,进程,:,用圆圈中加进程名表示,分配边：,资源实例,进程的一条有向边,申请边：,进程,资源类的一条有向边,84,5.,死锁定理,如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。,如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。,85,有环有死锁,86,有环无死锁,87,2.,死锁定理,图,3-12,资源分配图的简化,88,6.,资源分配图化简,方法如下,:,1,）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点,2,）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边,89,7.,解除死锁,当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有：,剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；,撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。,90,死锁的解除,图,3-13,付出代价最小的死锁解除方法,91,The End,92,