计算机操作系统第5章死锁.ppt

《计算机操作系统第5章死锁.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第5章死锁.ppt（34页珍藏版）》请在三一办公上搜索。

1、计算机操作系统,第5章 死 锁,从进程同步的概念可以知道，当并发进程需要竞争使用资源或需要相互协作向前推进时，如果不采取同步措施，或同步措施不恰当，则很容易导致并发进程不能向前推进而陷入僵局，即死锁现象。死锁是发生在一组相互竞争或协作的进程与线程之间的一个非正常现象。死锁是所有操作系统都面临着的潜在问题，操作系统除了需要预防死锁、避免死锁外，还需要能够检测死锁，并从死锁中进行恢复。,本章的主要内容如下：死锁的产生；死锁的预防；死锁的避免；死锁的检测和解除；线程死锁。,5.1 死锁的产生,5.1.1 死锁产生的原因竞争资源引起死锁 在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是

2、不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如CPU、内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。进程推进顺序不当引起死锁 在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。,5.1.1 死锁产生的原因（续）,进程推进顺序不当引起死锁例：进程P和Q并发执行，进程P和Q程序如下：Process P Process Q.Get A G

3、et B.Get B Get A.Release A Release B.Release B Release A.,5.1.1 死锁产生的原因（续）,当P、Q按如下次序执行时：P:GET A Q:GET BP:GET BQ:GET A,哲学家吃面的问题,A:P(S1)P(S3)EatingV(S3)V(S1),B:P(S2)P(S1)EatingV(S1)V(S2),C:P(S3)P(S2)EatingV(S2)V(S3),A:P(S1),B:P(S2),C:P(S3)A:P(S3):阻塞B:P(S1):阻塞C:P(S2):阻塞,A,S1,C,S3,S2,B,5.1.2 死锁产生的条件,1.产

4、生死锁的必要条件（Conditions for Deadlock）互斥（Mutual exclusion）条件：一个资源一次只能被一个进程所使用，即是排它性使用。不可抢占（No preemption）条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。请求和保持（Hold-and-wait）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。环路等待（Circular wait）条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。如一系统状态的资源分配图所示，P1正在等待一个P

5、2 占用的资源R2，P2正在等待一个P1占用的资源R1。,5.1.2 死锁产生的条件(续),2.资源分配图由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是申请边，它由进程结点指向资源结点。返回,5.1.2 死锁产生的条件(续),3.处理死锁的基本方法a.死锁的预防 静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。B.死锁的避免 动态的方法：在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条

6、件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。C.死锁的检测和解除 这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。,5.2 死 锁 预 防(Deadlock Prevention),预防死锁的方法是破坏四个产生死锁的必要条件之一。1。破坏互斥条件 互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用SPOOLing技术可将“独享”打印机改变为“共享”的打印机。2。破坏不可抢占条件 抢占式调度法主要用于处理机和存贮器资源调

7、度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。,5.2 死 锁 预 防(Deadlock Prevention)-1,3。破坏请求和保持条件 系统可采用资源静态予分配方式来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，若系统有足够资源满足给进程，则在运行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很安全，但其资源利用率很低，进程也延迟运行。4。破坏循环等待条件 有序资源使用法 该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入

8、机的序号为1，打印机序号为2，磁盘机序号为3等。,5.2 死 锁 预 防(Deadlock Prevention)-2,所有进程对资源的请求必须严格按资源序号递增的次序提出。这样在所形成的资源分配图中不可能再出现环路，因而摒弃了“环路等待”条件，在采用这种策略时总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可以一直向前推进。这种预防死锁的策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。资源按级分配法 该方法是把资源递增排序成若干等级（如L1、L2.Lm），其中每级可包含几类资源，要求每个进程在获得了Lj级中资源之后，它才能

9、申请更高级的LK（LKLj）级中的资源；如果它还需申请比LK级低的LI级（LILK）资源，则必须先释放所有大于LI级的资源。该方法是Haveder 1968年在设计IBM360 OS时提出的，资源共分三级，第一级数据集或文件，第二级主存，第三级I/O设备。,5.3 死 锁 避 免(Deadlock Avoidance),该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。1.系统的安全状态 安全状态是指系统的一种状态，在此状态开始系统能按某种顺序

10、（例如P1、P2Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（P1、P2.Pn）称为安全序列。若系统此状态不存在一个安全序列，则称系统处于不安全状态。例：假如系统中有P1、P2和P3三个进程和12台磁带机。各进程最大需求和T0时刻分配状态如下：进程最大需求 已分配 还需请求 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7,死锁的避免-1,分析T0状态，可以找到一个安全序列（P2、P1、P3）,即系统按此进程序列分配资源，每个进程都可顺利完成，其步骤如下：先将可用的3台磁带机中2台分配给P2，P2满足了最大的资源需求，在有限时间内运

11、行完毕，释放它占有的全部资源，使可用资源数量增至5台。再将可用的5 台磁带机分配给P1，最后将可用10台中7台磁带机分配给P3。这样三进程可按照（P2、P1、P3）序列顺序地一个个执行完成，则（P2、P1、P3）序列是安全序列，T0时刻状态也是安全状态。2.由安全状态向不安全状态的转换 如果在T0 状态不按安全序列进行分配，可能会导致系统进入一个不安全状态，例如在T0状态下P3中申请1台磁带机。如系统实施此次分配使系统状态由T0变为T1状态，分析T1状态安全情况。,死锁的避免-2,T1时刻状态：进程 最大需求 已分配 还需请求 可用 可用 分配资源前 释放资源后 P1 10 5 5 4 P2

12、4 2 2=4 因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以T1状态是不安全状态，由于实施分配给1台磁带机给P3的操作会引起系统状态由安全状态T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足，P3为申请1台磁带机而必须阻塞等待。,3.利用银行家算法避免死锁,最具代表的避免死锁算法是Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。银行家算法的数据结构可用资源向量 Available m m为系统中资源种类数，Availablej=k表示系统中第j类资源数为k个。最大需求矩阵Maxn，m n为系统中进程数

13、，Maxi,j=k表示进程i对j类资源的最大需求数为中k。分配矩阵Allocationn，m 它定义了系统中每一类资源当前已分配给每一进程资源数，Allocationi,j=k表示进程i已分得j类资源的数目为k个。,3.利用银行家算法避免死锁-1,需求矩阵Needn,m 它表示每个进程尚需的各类资源数，Needi,j=k 表示进程i还需要j类资源k个。Needi,j=Maxi,j-Allocationi,j银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行安全检查：如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需

14、求值的错误。如果RequestiAvailable则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。系统试探把要求的资源分配给进程i并修改有关数据结构的值：Available=Available-Requesti；Allocationi=Allocationi+Requesti；Needi=Needi-Requesti；,3.利用银行家算法避免死锁-2,系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法安全性算法执行步骤如下：A.初始化设置工作向量Workm表

15、示系统可提供的各类资源数目，用以保护原数据结构有关值。Work=Available，设置完成标志向量 Finishn。Finishi=false 表示i进程尚末完成，如值为true则表示进程i已完成。B.从进程集合n中找到一个能满足下述二个条件:Finishi=false和NecdiWork，如找到则执行步骤C，如找不到同时满足以上二条件的进程则执行步骤D。,3.利用银行家算法避免死锁-3,C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：work=work+Allocationi；Finishi=true；转执行步骤B。D.如果所有的Finishiture，则表示系

16、统处于安全状态，否则系统处于不安全状态。,银行家算法例：,假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下 所示。Max Allocation Need Available A B CA B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1试问：T0时刻是否安全？P1请求资源Request1(1,0,

17、2)是否允许？P4请求资源Request4(3,3,0)是否允许？,银行家算法例-1,T0时刻是否安全？从表中可找出一个序列(P1、P3、P4、P2、P0）使各进程顺序地一个个地执行完成。Max Allocation Need Available Available(分配资源前)(释放资源后）A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3=10 4 7 10 5 7P1 3 2 2 2 0 0 1 2 2=3 3 2 5 3 2P2 9 0 2 3 0 2 6 0 0=7 4 5 10 4 7P3 2 2 2 2 1 1 0 1 1=5 3

18、2 7 4 3P4 4 3 3 0 0 2 4 3 1=7 4 3 7 4 5安全序列为P1、P3、P4、P2、P0，T0时刻系统是安全的。P1请求资源Request1(1,0,2)可否允许？,银行家算法例-2,Request1(1,0,2)Need1(1,2,2)，P1请求在最大需求范围内。Request1(1,0,2)Available(3,3,2)，可用资源可满足P1请求需要。试探把要求的资源分配给进程P1并修改有关数据结构的数值：Available=Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；Need1=Need1(1,2,2)Re

19、quest1(1,0,2)=Need1(0,2,0)；Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；利用安全性算法检查试探将资源分配后状态的安全性如下：,银行家算法例-3,Max Allocation Need Available Available(分配资源前)(释放资源后）A B C A B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3=10 4 7 10 5 7P1 3 2 2 3 0 2 0 2 0=2 3 0 5 3 2P29 0 2 3 0 2 6 0 0=7 4

20、 5 10 4 7P32 2 2 2 1 1 0 1 1=5 3 2 7 4 3P44 3 3 0 0 2 4 3 1=7 4 3 7 4 5 因为先分配资源给P1进程符合按安全序列P1、P3、P4、P2、P0分配资源，所以试探将资源分配给进程P1后的状态是安全的，可将资源分配给进程P1。P4请求资源Request4(3,3,0)是否允许？Request4(3,3,0)Need4(4,3,1)，P4请求在最大需求范围内。Request4(3,3,0)Available(2,3,0)不成立，即可用资源暂不能满足P4请求资源需要，P4阻塞等待。,5.4 死锁的检测和解除(Deadlock Dete

21、ction),5.4.1 死锁的检测 死锁的避免算法增加了系统的开销，死锁的检测采用资源分配图的简化判断是否发生了不安全状态。如发现系统处于不安全状态时，即执行死锁解除的策略，采用此法开销相对减少。1.资源分配图的简化：系统处于某S状态时可用资源分配图表示，可用资源分配图简化来判断系统是否处于死锁状态。资源分配图简化的方法如下：在资源分配图中找一个既不阻塞又非孤立的进程结点PI（如某进程既无已分配的资源也不需申请资源，即既无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，这相当于取消PI的分配边和请求边，使它成为孤立结点。经过以上简化，

22、如所有的进程结点都是孤立结点则称资源分配图是可完全简化的。若不能通过任何过程使该图完全简化，则该图是不可完全简化的。资源分配图简化如下图：,R1 R2 R1 R2,。,P1,资源分配图的简化例：,5.4.1 死锁的检测-1,2.死锁定理：S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。3.死锁检测的数据和算法类似于银行家算法。,5.4.2 死锁解除,当检测死锁的软件判别死锁存在时，就要解除死锁，使系统从死锁中恢复。1利用结束死锁进程释放资源 强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链，并收回分配给终止进程的全部资源供剩下的进程使用。借

23、助于撤消进程来解除死锁可以使用两种方法。一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个撤消死锁的进程直至死锁环路消除。这里存在一个按照什么原则进行逐个撤消进程的问题。目前较实用而又简便的方法是撤消那些代价最小的进程。所谓影响一个进程的撤消代价因素有该进程的优先权，该进程运行到今的运行代价（包括CPU时间，使用资源的种类和时间等）、与相关的作业类型和外部代价等。,死锁的解除-1,2利用资源抢占死锁恢复的另一种办法是使用一个有效的挂起和解除机构来挂起一些死锁的进程，其实质是从被挂起的进程那里抢占资源以解除死锁，许多学者认为在此领域的研究工作比起其它死锁恢复的办法更为重

24、要。问题：现场（包扩CPU、内存、外设的状态）保护不好解决3利用回退释放资源例如一个系统提供了检查点和重新启动的便利的话，我们可以暂时仃止一个系统，而后从各进程的最近的检查点（系统保留了检查点的状态）逐次地重新启动。这既可以从死锁中恢复，又使进程损失最小（从检查点以后的损失）。但许多系统还没有此功能，在IBM4300系列等机器上提供了此类功能。,练 习 5,5.1 什么是死锁？引起死锁的原因和必要条件是什么？5.2 比较解决死锁的方法中，哪种方法最容易实现？哪种方法使得资源 的利用率最高？5.3 预防死锁的方法有哪些？5.4 叙述银行家算法的主要思想。5.5 死锁检测的方式有哪些？5.6 举例

25、说明如何消除死锁。5.7 一个系统是否会处于既不死锁，也不安全状态？为什么？5.8 系统中有3个进程共享4个资源，每个进程每次只能申请或释放一个 资源，每个进程最多需要2个资源，该系统是否会发生死锁，为什 么？5.9 系统中有20个进程，每个进程最多使用3个资源，每个进程逐个申 请并竞争使用60个同类资源。一旦某进程获得所需要的资源，完成 后立即释放全部资源。系统是否会发生死锁？为什么？5.10 一台计算机有8台打印机，被N个进程竞争使用，每个进程最多需 要3台。请问N为多少时，系统没有死锁的危险，说明原因,练 习 5（续）,5.11 考虑图5.9所示的资源分配图，哪个进程会发生死锁？,图5.9,5.12 假定有3个人排队等候上电梯。当电梯门打开的时候，3个人都朝门口冲去，但是门不够大，他们3人不能同时进门。描述解决这种死锁的方法，可以让 3个人都上电梯。说明你的解决方案清除了哪个死锁的必要条件。,练 习 5（续）,5.13 假定一个系统具有四个系统类型，C=3，7，2，3，最大资源需求数表 如图5.10所示。资源分配器根据图5.11中的表来分配资源，这个状态安全吗？为什么？,图5.10,图5.11,