操作系统课件-第三章进程管理8(死锁问题2)

进程管理1安全状态的例子例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列P2，P1，P3进程管理2虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。系统的状态可能通过下述来描述：进程剩余申请数＝最大申请数－占有数。可分配资源数＝总数－占有数之和。进程管理3银行家算法银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。进程管理4一、银行家算法中的数据结构1可利用资源向量Available是一个含有m个元素，其中的每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。如果Available[j]=k，表示系统中现有Rj类资源k个。2最大需求矩阵Max是一个含有nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k，表示进程i需要Rj类资源的最大数目为k。Available=354283861进程管理53分配矩阵Allocation是一个含有nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k，表示进程i当前已分得Rj类资源k个。4需求矩阵Need是一个含有nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k，表示进程i还需要Rj类资源k个，方能完成其任务。Need(i,j)=Max(i,j)-Allocation(i,j)进程管理6二、银行家算法设Requesti是进程Pi的请求向量，如果进程Pi需要K个Rj类资源，当Pi发出资源请求后，系统按下述步骤进行检查：1如果Requesti≤Needi,则转向步骤2；否则认为出错。（因为它所需要的资源数已超过它所宣布的最大值。2如果Requesti≤Available,则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待3系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Available:=Available-Requesti;Allocation:=Allocation+Requesti;Needi:=Needi-Requesti;4系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。进程管理7三、安全性算法系统所执行的安全性算法可描述如下：1设置两个向量①工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，执行安全算法开始时，Work:=Available。②Finish.它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够的资源分配给进程时，令Finish[i]:=true.2从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false;②Needi≤Work.如找到，执行步骤3；否则执行步骤4。3当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故执行：Work:=Work+Allocation;Finish[i]:=true;Gotostep2;4如果所有进程的Finish[i]=true，则表示系统处于安全状态；否则，系统处于不安全状态。要记住的一些变量的名称1Available（可利用资源向量）某类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。2Max最大需求矩阵某个进程对某类资源的最大需求数3Allocation分配矩阵某类资源当前非配给某进程的资源数。4Need需求矩阵某个进程还需要的各类资源数。Need=Max-Allocation系统把进程请求的资源分配给它以后要修改的变量Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request;进程管理9银行家算法之例假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)600011431332(230)332122200资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)600011431332(230)753资源情况进程NeedABCworkABCWork＋AllocationABCAllocationABCP1P3P4P2P0finish532truetruetruetruetrue011211532743743431002745745600302104710477430101057最大值已分配还需要可用若P1发出请求向量Request（1，0，2）工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目10,57进程管理11思考和练习假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图请找出该表中T0时刻以后存在的安全序列（至少2种）资源情况进程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200302211002743122600011431332753进程管理123死锁的检测和恢复死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。(1)死锁的检测检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。进程管理13死锁的检测：实质是确定是否存在环路等待现象，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图RAG和死锁定理的检测死锁算法。进程管理14资源分配图（RAG）系统死锁可用资源分配图来描述，该图是由一组结点N和一组边E所组成的一对偶G=(N,E)。（用圆圈代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源）几个概念：请求边，分配边P1P2r1r2请求r2资源分配图进程管理15封锁进程：是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。非封锁进程：即没有被系统封锁的进程资源分配图的化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行）。进程管理16死锁定理：系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。P1P2r1r2P1P2r1r2P1P2r1r2进程管理17死锁的恢复。是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。常用的方法有：1撤消进程；最简单撤消进程的方法是使全部死锁的进程夭折掉；另一方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止2挂起进程（剥夺资源）。使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。目前挂起法比较受到重视。进程管理181．（北大95）一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？2．死锁和饥饿的主要差别是什么？例题进程管理191答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。2答：简言之，死锁是某进程等待一个不会发生的事件的一种现象；而饥饿现象是某进程正等待这样一个事件，它发生了但总是受到其它进程的影响，以至轮不到（或很难轮到）该进程。进程管理201.在某系统中，三个进程共享四台同类型的设备资源，这些资源一次只能一台地为进程服务和释放，每个进程最多需要二台设备资源，试问在系统中是否会产生死锁？2.某系统中有n个进程和m台打印机，系统约定：打印机只能一台一台地申请、一台一台地释放，每个进程需要同时使用的打印机台数不超过m。如果n个进程同时使用打印机的总数小于m+n，试讨论，该系统可能发生死锁吗?并简述理由。3.仅涉及一个进程的死锁有可能存在吗?为什么?作业进程管理21进程管理22小结进程的并发执行，使得它们之间存在着两种制约关系：由共享资源引起的间接制约关系称为互斥；由于协作完成同一任务而引起的直接制约关系称为同步。为了正确地解决进程之间的同步和互斥，系统设置同步机构：锁和信号量机构。这种同步机构称为低级通信。进程之间的高级通信机构有消息缓冲、信箱、管道、共享内存和共享文件等机构，其最大特点是通信双方可交换大量的数据。进程管理23系统中并发运行进程由于共享资源或相互通信，如果调度不当，可能导致系统死锁。解决死锁的方法有三种：(1)预防死锁，它是通过破坏死锁的四个必要条件实现的。(2)避免死锁，它是在进程请求分配资源时，采用银行家算法等防止系统进入不安全状态。(3)检测和恢复死锁，它是通过设置一个死锁检测机构进行死锁检测，一旦检测出来，通过逐一撤消进程使系统恢复。进程管理243.9线程(Thread)3.9.1线程的概念引入的线程目的：提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，便于系统管理。（减少程序并发执行时所付出的时空开销，使OS具有更好的并发性。）进程管理25分析说明：进程的两个基本属性：1进程是一个可拥有资源的独立单位；2进程又是一个可独立调度和分配的基本单位。合起来，进程便成为一个能独立运行的基本单位，从而构成了程序并发执行的基础。简言之，由于进程是一个资源的拥有者，在执行这些操作时会付出较大的时间开销。因此在系统中所设的进程数目不宜过多，切换不宜过于频繁，这就限制了系统的并发程度。进程管理26线程的定义定义：线程是进程中的一个实体，是被系统独立调度和分配的基本单位，故又称为轻权（轻型）进程(LightWeightProcess)，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。{传统的进程称为重型进程(HeavyWeightProcess)。}线程与进程的主要区别１进程是资源管理的基本单位，它拥有自己的地址空间和各种资源；线程只是处理机调度的基本单位，它只和其他线程一起共享进程资源，它自己没有任何资源。２以进程为单位进行处理机切换和调度时，处理机切换时间长，资源