处理机调度与死锁.ppt

第三章处理机调度与死锁,3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除,3.1处理机调度的基本概念,3.1.1高级、中级和低级调度3.1.2调度队列模型3.1.3选择调度方式和调度算法的若干原则,高级调度：又称为作业调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，大多配有作业调度，但在分时和实时系统中，却往往不配置作业调度。作业调度的运行频率较低，通常为几分钟一次。,3.1.1高级、中级和低级调度调度的类型,执行作业调度时，需要解决：（1）一次接纳多少作业：即允许多少个作业同时在内存中运行。（2）接纳哪些作业：即哪些作业调入内存，取决于所采用的算法。比如先来先服务调度算法；或者是短作业优先调度算法；还有基于作业优先权的调度算法，响应比高者优先调度算法等。,2.低级调度：又称为进程调度、短程调度。用于决定就绪队列中的哪个进程能获得处理器,并将处理机分配给该进程。进程调度程序是操作系统最为核心的部分，进程调度策略的优劣直接影响到整个系统的性能。三种类型的操作系统中，都必须配置此级调度。,有两类低级调度方式：(1)非抢占方式一旦把处理机分配给某个进程后，让该进程一直执行，直到该进程完成或者发生某事件而阻塞。引起进程调度的因素：正在执行的进程执行完毕；执行中的进程因为提出I/O请求而暂停执行；进程通信或同步过程中执行了原语操作。,(2)抢占方式当一进程正在处理机上执行时，系统可根据某种原则暂停它的执行，并将已分配给它的处理机重新分配给另一个进程。抢占的原则有：优先权原则：就绪的高优先权进程有权抢占低优先权进程的CPU。短作业优先原则：就绪的短作业(进程)有权抢占长作业(进程)的CPU。时间片原则：一个时间片用完后，系统重新进行进程调度。,3.中级调度又称平衡负载调度、中程调度。目的是为了提高内存利用率和系统吞吐量。实质是进程的内外存对换功能：将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。,在三种调度中，进程调度的运行频率最高，作业调度的周期较长，中级调度的运行频率在上述两者之间。,3.1.2调度队列模型,根据os中所引入的调度的类型，形成了三种类型的调度队列模型：仅有进程调度的调度队列模型；具有高级和低级调度的调度队列模型；同时具有三级调度的调度队列模型。,1.仅具有进程调度的调度队列模型,2.具有高级和低级调度的调度队列模型,3.同时具有三级调度的调度队列模型,3.1.3选择调度方式和调度算法的若干原则,面向用户的准则(1)周转时间短作业周转时间：作业提交计算机到作业完成为止的时间间隔。它是作业在系统里的等待时间与运行时间之和。平均作业周转时间：带权周转时间：W=T/Ts注意：带权周转时间总大于1。平均作业带权周转时间：主要用于评价批处理系统。,T:作业的周转时间，Ts:作业的运行时间。,(2)响应时间快从用户通过键盘提交一个请求到系统首次产生响应之间的时间间隔称响应时间。主要用于评价分时系统。(3)截止时间的保证任务必须开始执行的最迟时间或必须完成的最迟时间称截止时间。主要用于评价实时系统。(4)优先权准则在三种OS中，都可遵循。,2.面向系统的准则系统吞吐量高吞吐量:单位时间内系统所完成的作业数。(2)处理机利用率好CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间CPU利用率=CPU有效工作时间/CPU总的运行时间(3)各类资源的平衡利用,3.2调度算法,3.2.1先来先服务和短作业优先调度算法3.2.2高优先权优先调度算法3.2.3基于时间片轮转调度算法,调度算法:,根据系统的资源分配策略所规定的资源分配算法称为调度算法。通常将作业或进程归入各种就绪或阻塞队列。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。,3.2.1先来先服务和短作业优先调度算法,最简单的调度算法。用于作业调度时：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。用于进程调度时：按照进程就绪的先后次序来调度进程。算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。,1.先来先服务调度算法（FCFS）,例：在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：,用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间：,2.短作业(进程)优先调度算法（SJF/SPF）,用于作业调度时：SJF调度算法。以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。用于进程调度时：SPF调度算法。从就绪队列中选出估计运行时间最短的进程，将处理机分配给它。算法易于实现，能有效降低作业的平均等待时间。缺点是：对长作业不利，有可能导致长作业（进程）长期不被调度；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。,1,3,5,2,4,运行步骤,例：,3.2.2高优先权优先调度算法,用于作业调度时：系统将从后备队列中选择若干个优先权最高的作业装入内存。用于进程调度时：该算法把处理机分配给就绪队列中优先权最高的进程。非抢占式优先权算法抢占式优先权调度算法,优先权的类型：静态优先权在创建进程时确定的，且在进程的整个运行期间保持不变。静态优先权法简单易行，但随着进程的推进，其优先权可能与进程的情况不再相符。动态优先权在创建进程时所确定的优先权，可以随着进程的推进而改变。例如：可以规定就绪进程的优先权随着等待时间的增长以速度a增加；正在执行进程的优先权以速度b下降，这样便可防止一个长作业长期垄断处理机。,3.高响应比优先调度算法（HRRF）：,实际上是一种动态优先权调度算法。FCFS与SJF/SPF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时间，SJF/SPF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。但每次调度前，都要进行响应比的计算，会增加系统开销。,优先权的变化规律可描述为：,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：,如果等待时间相同，短作业容易得到较高优先权。长作业等待时间足够长后，也将获得足够高的优先级。如果要求服务时间相同时，作业的优先权决定于其等待时间，实现的是先来先服务。,例如：以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业1020作业2515作业3105作业41510,FCFS调度算法：平均作业周转时间T=(20+30+30+35)/4=28.75平均带权作业周转时间W=(20/20+30/15+30/5+35/10)/4=3.13SJF调度算法：调度顺序为作业1、3、4、2，平均作业周转时间T=(20+15+20+45)/4=25平均带权作业周转时间W=(20/20+15/5+25/10+45/15)/4=2.25,高响应比调度算法：开始只有作业1，被选中执行时间20；作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5；作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15；作业2执行完毕，作业4被选中，执行时间10；平均作业周转时间T=(20+15+35+35)/4=26.25平均带权作业周转时间W=(20/20+15/5+35/15+35/10)/4=2.42,3.2.3基于时间片轮转调度算法,把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间。,1.时间片轮转法（RR）,2.多级反馈队列调度算法（FB）,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片越短；新进程进入内存后，放入第一队列末尾，按FCFS原则等待调度，如果在一个时间片结束时没完成，将该进程转入第二队列末尾重新等待调度执行如此下去，当一个长作业从第一级队列降到最后一级队列时，便在该队列中采取时间片轮转方式运行。,仅当第一队列空闲时，调度程序才调度第二队列中的进程运行类推之，仅当第1(i-1)级队列均空时，才调度第i级队列上的进程执行。如果处理机正在为某队列的进程服务，又有新进程插入到较高优先级的队列中，则新进程将抢占正在运行进程的处理机。,多级反馈队列调度算法,就绪队列,1,就绪队列,2,就绪队列,3,就绪队列,n,S,1,S,2,S,3,至,CPU,至,CPU,至,CPU,至,CPU,(时间片：,S,1,S,2,S,3,),多级反馈队列调度算法性能：较好的性能，能够较好地满足各种类型用户的需要。终端型作业用户短批处理作业用户长批处理作业用户,3.3实时调度,3.3.1实现实时调度的基本条件3.3.2实时调度算法的分类3.3.3常用的两种实时调度算法,1.实时调度,根据实时系统的特点，对实时系统中的调度有特殊的要求，故引入一种新的调度方式实时调度。,3.3.1实现实时调度的基本条件,2.实时系统的特点,有限等待时间（决定性）有限响应时间用户控制可靠性高系统出错处理能力强,3.实现实时调度的基本条件,提供必要的信息如：就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或软实时）系统处理能力强采用抢占式调度机制具有快速切换机制对外部中断的快速响应能力、快速的任务分派能力,3.3.2实时调度算法的分类,根据时实任务性质，分为硬实时调度算法软实时调度算法根据调度方式，分为（）非抢占式调度算法抢占式调度算法根据调度程序调度时间，分为静态调度算法动态调度算法在多处理机环境下，分为集中式调度算法分布式调度算法,1.非抢占式调度算法,非抢占式轮转调度算法将实时任务排成轮转队列，调度程序每次选择队列中的第一个任务运行，当任务自我终止或运行完成后，此时调度程序选择下一个队首任务运行；未完成的任务被挂在轮转队列的队尾。用于要求不太严格的实时控制系统。非抢占式优先调度算法在就绪队列中，优先级高的任务位于队首，当任务自我终止或运行完成后，调度程序选择下一个队首任务运行。用于有一定要求的实时控制系统。,2.抢占式调度算法,基于时钟中断的抢占式优先权调度算法当新到来的实时任务的优先级高于当前任务，则等到时钟中断到来时，调度程序剥夺当前任务的执行，将处理机分配给新到的高优先权任务。用于大多数的实时系统。立即抢占的优先权调度算法操作系统能快速相应外部时间中断，一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，将处理机分配给请求中断的紧迫任务。用于实时要求比较严格的实时控制系统。,进程，并立即执行,(,a,),非抢占轮转调度,当前进程,实时进程,实时进程请求调度,实时进程枪占当前,(,d,),立即抢占的优先权调度,调度时间,进程,1,进程,2,实时进程要求调度,进程,n,实时进程,调度实时进程运行,(,b,),非抢占优先权调度,当前进程,实时进程,实时进程请求调度,当前进程运行完成,调度时间,当前进程,实时进程请求调度,时钟中断到来时,调度时间,(,c,),基于时钟中断抢占的优先权抢占调度,调度时间,实时进程,图3-6实时进程调度,响应时间：数秒至数十秒,响应时间：几十毫秒至几毫秒,响应时间：数秒至数百毫秒,响应时间：几百毫秒至几毫秒,3.3.3常用的两种实时调度算法,1.最早截止时间优先算法（即EDF算法）,根据任务的开始截止时间来确定任务的优先级。该调度算法首先运行队首进程，即开始截止时间最近的那个进程。算法即可采用非抢占调度方式，也可采用抢占调度方式。,例：非抢占调度方式下的EDF算法。,2.最低松弛度优先算法（即LLF算法）,根据任务的紧迫程度（或松弛程度）来确定任务的优先级。松弛度最低的任务排在就绪队列的最前面，调度程序总是选择队列中的首任务执行。算法主要用于可抢占调度方式中。松弛度=必须完成时间-其本身的运行时间-当前时间,例：如果系统中有两个周期性的实时任务A和B：任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms；任务A和B每次必须完成的时间分别为A1、A2、A3和B1、B2、B3见图。,A1A2A3A4A5A6A7A8,0102030405060708090100110120130140150160,t,B1B2B3,调度情况：,t,3.4多处理机系统中的调度,3.4.1多处理机系统的类型3.4.2进程分配方式3.4.3进程(线程)调度方式,多处理机系统,MPS，MultiProcessorSystem20世纪70年代出现多处理机系统：是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统。,3.4.1多处理机系统的类型,根据多处理器之间耦合的紧密程度，分为紧密耦合MPS松散耦合MPS根据系统中所用处理器的相同与否，分为对称多处理器系统SMPS非对称多处理器系统,3.4.2进程分配方式,1.对称式多处理系统中的进程分配方式：静态分配方式每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。优点：调度算法开销小。缺点：容易出现处理机忙闲不均。动态分配方式各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。优点：消除个处理机忙闲不均的现象。缺点：对松散耦合系统，会增加调度开销。,2.非对称式多处理系统中的进程分配方式,主从处理机系统。操作系统核心驻留在主机上，由主处理机执行调度，从机上只是用户程序；主机管理一个公共就绪队列，并分派进程给从处理机执行；各个处理机有固定分工，如执行OS的系统功能，I/O处理，应用程序。优点：系统处理较简单。缺点：存在不可靠性。当主机太忙时，会出现系统瓶颈；当主机出现故障时，会导致整个系统瘫痪。克服方法：利用多台处理机（而非一台）来管理整个系统。,注重整体运行效率（而不是个别处理机的利用率）。更多样的调度算法。多处理机访问OS数据结构时的互斥（对于共享内存系统）。调度单位广泛采用线程。,3.多处理机调度与单处理机调度的区别,3.4.3进程(线程)调度方式,指在系统中设置一个公用的进程(或线程)队列，所有的处理器在空闲时，都可自己到该队列中取一进程(或线程)来执行。是最简单、最常用的调度方式，采用单处理机环境下的调度方式。需要对就绪队列的数据结构进行互斥访问控制。,1.自调度(self-scheduling)方式：,优点：易将单处理机系统的调度机制移植到多处理机系统。避免处理机忙闲不均的现象。缺点：瓶颈问题（对就绪队列的访问）低效性线程切换频繁,为了解决自调度方式中线程被频繁切换的问题。是指将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上去同时执行。分配处理机时间时，可采用两种方式：面向所有应用程序平均分配处理机时间面向所有线程平均分配处理机时间,2.成组调度(gangscheduling)方式,两种分配处理器时间的方式：,面向所有应用程序平均分配处理机时间,面向所有线程平均分配处理机时间,优点：对于一组相互合作的线程，成组调度能够提高这些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统的吞吐量。每次调度可以完成多个线程的分派，能够减少调度次数，从而减少调度的开销。,是指在一个应用程序执行期间，专门为该应用程序分配一组处理器，每个线程分配一个CPU。这组处理器仅供该应用程序专用，直至该应用程序执行完成。适用于CPU数量众多的高度并行系统，单个CPU利用率已不太重要。线程的总和不应超过系统中的处理机数目。缺点：有线程阻塞时，造成CPU的闲置优点：线程执行时不需切换，相应的开销可以大大减小，推进速度更快。,3.专用处理机分配(dedicatedprocessorassignment)方式,以下是线程数对加速比的影响：,例：具有16个处理器的系统，运行两个应用程序：矩阵相乘、快速傅立叶变换。,3.5产生死锁的原因和必要条件,3.5.1产生死锁的原因3.5.2产生死锁的必要条件3.5.3处理死锁的基本方法,死锁的定义,所谓死锁，是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将不能再向前推进。注意：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,3.5.1产生死锁的原因,一个操作系统基本上是一个资源管理者，它负责分配不同类型的资源给进程使用。系统中的资源分两类：可剥夺性资源指资源占有进程虽然需要使用该资源，但另一个进程却能强行把资源从占有者进程处抢来。不可剥夺性资源指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。,1.资源,资源,可剥夺：CPU、主存、硬盘，该资源可为几个进程共同使用。,不可剥夺：打印机、读卡机、磁带驱动器，该资源为某个进程独享。,永久性资源和临时性资源：,永久性资源可顺序重复使用的资源：如打印机；临时性资源由一个进程产生，被另一进程使用一短暂时间后便无用的资源：如消息，故也称之为消耗性资源。,竞争资源（不可剥夺性、临时性）当系统中供多个进程共享的资源不足时，将引起进程对资源的竞争而产生死锁。进程推进顺序不合理进程在运行过程中具有异步性特征，如果它们之间的请求和释放资源的顺序不当，也同样会导致进程产生死锁。,2.死锁产生的根本原因,(1)竞争资源产生的死锁：,生产出一产品；P（empty）P（mutex）将产品放入缓冲区；V（mutex）V（full）,(2)进程推进顺序不合理产生的死锁：,例1：生产者消费者问题中，若PV操作使用不当，把生产者进程两个P操作次序互换，先执行P(mutex)，后执行P(empty)，则会引起死锁。,P（full）P（mutex）从缓冲区取出产品；V（mutex）V（empty）消费该产品；,生产者,消费者,例2：,P1:Request(R1);Request(R2);Release(R1);Release(R2);,P2:Request(R2);Request(R1);Release(R2);Release(R1);,3.5.2产生死锁的必要条件,四个必要条件：互斥条件：涉及的资源是非共享的。请求和保持条件：进程在等待一新资源时继续占有已分配的资源。不剥夺条件：不能强行剥夺进程拥有的资源。环路等待条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。以上四个条件须同时具备。,3.5.3处理死锁的基本方法,(1)预防死锁：,通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。,(2)避免死锁：,不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。实现较难，只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。,事先并不采取任何限制，允许发生死锁，但可以通过系统的检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源。,(3)检测死锁：,与检测死锁相配套，用于将进程从死锁状态解脱出来。常用的方法是撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。实现难度大，但可获得较好的资源利用率和系统吞吐量。,(4)解除死锁：,3.6死锁的预防和避免,3.6.1预防死锁3.6.2避免死锁3.6.3利用银行家算法避免死锁,1.摒弃“请求和保持”条件,系统要求所有进程在开始运行之前，要一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则完全分配；否则，进程等待。,3.6.1预防死锁,优点：简单、易于实现且安全。,基本思想：打破产生死锁的四个必要条件中的一个或几个。,缺点：实用性不强：在许多情况下，一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的，不可预测的；资源利用率低：无论所分资源何时用到，一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程在生存期间却一直占有它们，造成长期占着不用的状况。造成极大的资源浪费；延迟进程的运行：因为进程只有获得了其所需的全部资源才开始运行，但有些资源可能长期被其它进程占用，导致该进程迟迟不能运行。,2.摒弃“不剥夺”条件,一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。缺点：实现复杂、要付出很大的代价。原因：一个资源在使用一段时间后被释放，可能会造成前阶段工作的失效；反复地申请和释放资源，又会使进程的执行无限推迟，从而进一步增加系统的开销，降低系统的吞吐量。,3.摒弃“环路等待”条件,系统中的所有资源都有一个确定的唯一号码，所有分配请求必须以序号上升的次序进行。例如：系统中有下列设备：输入机(1)，打印机(2)，穿孔机(3)，磁带机(4)，磁盘(5)。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。,优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。缺点：系统中各类资源的编号必须相对稳定，限制了新设备类型的增加；进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可避免死锁的发生。,3.6.2避免死锁,1.安全状态,如果系统能按某种顺序（P1，P2，,Pn）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。其中，称为安全序列。,并非所有的不安全状态都导致死锁，但当系统进入不安全状态后，便可能进而进入死锁状态；只要系统处于安全状态，便可避免进入死锁状态避免死锁的本质在于：当进行资源分配时，如何避免进入不安全状态。,安全状态举例：,有三个进程p1、p2、p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。在T0时刻，p1、p2、p3分别获得5、2、2台，尚有3台空闲。,经分析，在T0时刻，系统是安全的。因为存在一个安全序列p2、p1、p3。见下图。,3.6.3利用银行家算法避免死锁,最有代表性的避免死锁算法，由Dijkstra提出。,1.银行家算法中的数据结构,可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。分配矩阵Allocation。n*m矩阵，表示每个进程分配的资源数。需求矩阵Need。n*m矩阵，表示每个进程还需要各类资源数。,2.银行家算法描述,当进程pi提出资源申请时，系统执行下列步骤：(1)若RequestiNeedi，转(2)；否则错误返回。(2)若RequestiAvailable，转(3)；否则进程等待。(3)假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti(4)执行安全性算法，若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原状态，进程等待。,3.安全性算法,为进行安全性检查，设置两个向量：工作向量Work:表示系统可提供给进程继续运行所需的各类资源数目，含有m个元素，在执行安全算法开始时，Work:=Available;Finish:表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi:=false;当有足够资源分配给进程时，再令Finishi:=true。,安全性算法步骤：,(1)Work:=Available;Finish:=false；(2)寻找满足下列条件的i：a)Finishi=false；b)NeediWork；若找到，转(3)；若找不到，则转(4)。(3)Work:=Work+Allocationi；Finishi:=true；转(2)。(4)若对所有i，Finishi=true，则系统处于安全状态，否则处于不安全状态。,4.银行家算法举例,设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图：,(1)T0时刻的安全性检查：,T0时刻可以找到一个安全序列p1,p3,p4,p0,p2。系统是安全的。,(2)T0时刻P1请求资源，请求向量Request1(1,0,2)。,执行银行家算法：Request1(1,0,2)Need1(1,2,2)Request1(1,0,2)Available(3,3,2)系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图一所示。进行安全性检查：如图二所示。可以找到一个安全序列p1,p3,p4,p0,p2。故系统是安全的，可以将P1的请求分配给它。,图一：,图二：,(3)P4请求资源，请求向量Request4(3,3,0)。,执行银行家算法:Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available(2,3,0);所以P4等待。P4的请求不能分配。,(4)P0请求资源,请求向量Request0(0,2,0),Request0(0,2,0)，执行银行家算法：Request0(0,2,0)Need0(7,4,3);Request0(0,2,0)Available(2,3,0);系统暂时先假定可为P0分配资源，并修改图一有关数据，如后图所示。进行安全性检查：Available2,1,0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配。,3.7死锁的检测与解除,3.7.1死锁的检测3.7.2死锁的解除,死锁检测与解除是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。,允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。,3.7.1死锁的检测,1.资源分配图,用来描述系统资源及资源的申请和分配情况的有向图。定义为：二元组G=（V，E）其中：V：结点集，分为P(进程集合)，R(资源集合)两部分。即P=p1,p2,pn；R=r1,r2,rm。E：边的集合，其元素为有序二元组(pi,rj)或(rj,pi)。,资源请求边：e=pi,rj进程资源的一条有向边表示进程pi申请rj类资源中的一个资源。资源分配边：e=rj,pi资源进程的一条有向边表示rj类中的一个资源已被进程pi占用。,例：,P1,P2,r1,r2,请求r2,资源请求边,资源分配边,(1)如果资源分配图中无环路，则此时系统没有发生死锁。(2)如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统