《操作系统死锁.pptx》由会员分享，可在线阅读，更多相关《操作系统死锁.pptx（25页珍藏版）》请在第壹文秘上搜索。
1、操作系统原理第3章 进程管理第7讲 进程死锁 2023-4-242今日主题n什么是死锁？（了解）n死锁防止（熟悉）n死锁避免（掌握）n死锁检测和恢复（熟悉）重点：死锁必要条件、死锁防止、避免、检测和恢复难点：银行家算法。 2023-4-243 汽车竞争汽车竞争路口路口 它们到达路口的时间很它们到达路口的时间很“凑巧凑巧” 每个车队既每个车队既占有占有一一个路口，又个路口，又等待等待另一车队让出路口另一车队让出路口交通拥堵现象所有的所有的车车都都在在等待等待，如果如果没有交警来没有交警来，只好只好无限无限等待下去！等待下去！2023-4-244输出井输出井 满啦！满啦！ 不够！不够！进程进程A
2、AABCCDEFABCD进程进程B BABCD 不够！不够！ 进程竞争进程竞争资源资源 每一进程既每一进程既占有占有一个资源，又一个资源，又等待等待另一进程让出资源另一进程让出资源 要是输出井再多一个就好啦要是输出井再多一个就好啦! !SPOOLing系统死锁示例一 什么是死锁？ 死锁的定义2023-4-245一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为进程死锁死锁(Deadlock)，这一组进程就称为死锁进程。P1P2.GPS照相机照相机请求请求请求请求分配分配每一进程既占有一个资源，又等待另一进程让出资源！每一进程既占有一个资源，又等
3、待另一进程让出资源！进程进程P1和和P2拍拍照并在照片上照并在照片上标定位置信息标定位置信息死锁的原因起因是并发进程的资源竞争。根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。是否死锁取决于各进程申请和释放资源的顺序。因此，死锁的原因归为两点： （1）系统资源不足。(资源数比进程需要量少)。 （2）进程推进顺序不当。2023-4-246死锁的必要条件(1)互斥（Mutual Exclusion） 必须存在需要互斥使用的资源 (2)不剥夺（No Preemption） 进程占有的资源未主动释放时不可以剥夺(3)部分分配(又叫占有等待Hold and Wait) 进程占有已分到的部分
4、资源而又等待其它资源(4)环路（又叫循环等待Circular Wait） 进程集合P0, P1, , Pn，Pi等待Pi+1的资源，Pn等待P0的资源。形成等待环。2023-4-2474P0P1P2PnPiPi+1.死锁的解决方法 死锁预防（Deadlock prevention） 死锁避免（Deadlock avoidance） 死锁的检测和恢复（Deadlock Detection and Recovery from Deadlock） 忽略（ignore)2023-4-248因为死锁的处理开销较大，所以很多操作系统，因为死锁的处理开销较大，所以很多操作系统，如如Linux、Windows
5、，都忽略，都忽略死锁。死锁。二 死锁预防 什么是死锁预防？ 采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。 死锁预防方法 破坏“互斥”条件：共享使用资源。缺点：不一定可行。 破坏“部分分配”条件：进程申请资源时必须一次性申请其全部所需资源。缺点：资源利用率低，可能饥饿。 破坏“不剥夺”条件：当进程申请的资源不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。缺点：释放的资源的前期工作将失效。 破坏“环路”条件：系统将资源编号，进程按照资源序号递增的次序提出资源申请。缺点：限制了新设备增加，资源可能限制，用户变成受限制。202
6、3-4-249三 死锁避免 什么是死锁避免？ 系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免的方法。 有代表性的死锁避免算法是Dijkstra提出的银行家算法。2023-4-2410借给Q:1银行家算法示意【例】设银行家有10万元，顾客P,Q,R分别需要8,3,9万元搞项目（假设任何人满足资金总额后都会归还所有贷款）。如果P、Q、R分别已借到了4万、2万、2万。以后银行家怎样放贷？2023-4-2411P Q R4 2 2剩 余：2P Q R4 3 2剩 余：1Q还款:3P Q R4 0 2剩 余：4借给P:4P Q R8 0 2剩 余：0P还款:8P Q R0 0 2剩
7、余：8借给R:7P Q R0 0 9剩 余：1R还款:9P Q R0 0 0剩余：10得到借款的安全序列：得到借款的安全序列：Q P R其他借款序列，如其他借款序列，如PQR、PRQ、都不安全！都不安全！ 所谓安全状态，是指系统能按某种进程顺序(P1, P2, Pn)来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都能顺利地完成，则称这个系统处于安全状态，序列(P1, P2, Pn)称为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。2023-4-2412设单类资源系统中有设单类资源系统中有n个进程，若存在一个个进程，若存在一个序列序列(P1,
8、P2, Pn)使得使得Pi(i1，2n)以后还需要的资源可以通过系统现有资源加上所有以后还需要的资源可以通过系统现有资源加上所有Pj(ji)占有的资源来满足占有的资源来满足 ，则则该该系统系统处于安全状态，处于安全状态，序列序列(P1，P2 Pn)称为称为安全序列。安全序列。安全状态与安全序列讨论：安全状态与死锁的关系2023-4-2413 安全安全状态状态不是死锁不是死锁状态状态。死锁。死锁状态状态是不是不安全状态安全状态。 并非并非所有的不安全状态都会死锁，但不安全状态可能导致死锁所有的不安全状态都会死锁，但不安全状态可能导致死锁。 系统处于安全状态系统处于安全状态，可，可避免进入死锁状态
9、。避免进入死锁状态。避免避免死锁死锁就是就是要在系统要在系统在进行资源分配时，如何使系统在进行资源分配时，如何使系统不不进入不安全状态。进入不安全状态。死锁死锁不安全不安全安全安全银行家算法（Bankers Algorithm） 把银行家比作系统，把资金比作资源，把顾客比作进程。 银行家算法：在系统处理资源申请时，判断在满足申请时，系统是否还处于安全状态？是则满足本次资源申请 ，否则拒绝。分3步进行： 第一步，根据资源数据结构建立资源分配表 第二步，试分配：按照进程申请分配，修改资源分配表 第三步，安全检查：对哦是分配状态进行安全检查，若出现不安全状态，则回复试分配资源，结束。若安全则结束。2
10、023-4-2414银行家算法数据结构n：进程总数：进程总数m：资源类型总数：资源类型总数Availablem：剩余资源：剩余资源。 Availablej=k; 表示表示j类类资源资源剩余剩余k个个。Maxn,m; 资源最大需求量。资源最大需求量。 Maxi,j=k; 表示进程表示进程Pi最多需要最多需要j类类资源资源K个。个。Allocation n, m; 已分配资源。已分配资源。 Allocationi,j=k;表示进程表示进程Pi已分配已分配j类类资源资源k个个。Needn, m; 还需要的资源。还需要的资源。 Needi,j=k;表示进程表示进程Pi以后以后还需要还需要j类资源类资源
11、k个。个。Request m; 进程申请的资源。进程申请的资源。 Requestj=k;表示进程申请表示进程申请j类资源类资源k个。个。2023-4-2415Needi,j=Maxi,j-Allocationi,j;银行家算法描述：试分配安全检查试分配算法试分配算法设进程设进程Pi申请资源，申请资源向量为申请资源，申请资源向量为Requestj，则有如下的资源，则有如下的资源分配过程：分配过程：(1)if(RequestjNeedi,j) 报错返回报错返回;(2)if(RequestjAvailablej) 进程进程Pi等待等待;返回返回;(3)假设进程假设进程Pi的申请已获准，修改系统状态：
12、的申请已获准，修改系统状态： Availablej=AvailablejRequestj; Allocationi,j=Allocationi,j+Requestj Needi,j=Needi,jRequestj;(4)调用安全状态检查算法。调用安全状态检查算法。(5)若系统处于安全状态，则将进程若系统处于安全状态，则将进程Pi申请的资源分配给进程申请的资源分配给进程Pi，返，返回。回。(6)若系统处于不安全状态，则进程若系统处于不安全状态，则进程Pi进入等待资源状态并恢复系统进入等待资源状态并恢复系统状态后返回：状态后返回： Availablej=Availablej+Requestj; A
13、llocationi,j=Allocationi,j-Requestj; Needi,j=Needi,j+Requestj;2023-4-2416银行家算法描述：试分配安全检查安全检查算法安全检查算法 为进行安全性检查，定义数据结构：为进行安全性检查，定义数据结构：Workm：为临时工作向量：为临时工作向量,表示剩余资源。表示剩余资源。Finishn：表示剩余资源是否满足进程的需要。：表示剩余资源是否满足进程的需要。安全性检查的步骤：安全性检查的步骤：(1) Work=Available; Finish=false;(2) 寻找满足条件的寻找满足条件的i，使得：，使得： NeediWork &
14、 Finishi=false; 如果不存在，则转如果不存在，则转(4)(3) Work=Work+Allocationi; Finishi=true; 转转(2)(4) 若对所有若对所有i，Finishi=true, 则系统处于安全状态，则系统处于安全状态， 否则处于不安全状态否则处于不安全状态2023-4-2417银行家算法举例【例】系统中有r1,r2,r3三类资源，在T0时刻P1,P2,P3,P4四个进程对资源的最大需求数分别为P1(3,2,2), P2(6,1,3), P3(3,1,4), P4(4,2,2)，已分配的资源数量分别为P1(1,0,0), P2(4,1,1), P3(2,1
15、,1), P4(0,0,2),此时系统中可用的资源数为(2,1,2)。试问该状态安全吗？是否存在安全序列，为了避免死锁应如何进行分配。2023-4-2418【方法方法】（1 1）求资源分配表）求资源分配表; ; （2 2）试分配）试分配; ; （3 3）安全检查）安全检查 资源资源进程进程最大需求最大需求已分配资源已分配资源还需要资源还需要资源剩余资源剩余资源r1 r2 r3r1 r2 r3r1 r2 r3r1 r2 r3P1 3 2 2 1 0 02 1 2P2 6 1 34 1 1P3 3 1 42 1 1P4 4 2 20 0 2【解答解答】 T0 T0时刻资源分配表：时刻资源分配表：2
16、023-4-2419P2申请资源后的申请资源后的安全检查表安全检查表： 资源资源进程进程工作向量工作向量已分配已分配还需要还需要工作工作+已分配已分配完成情况完成情况r1 r2 r3r1 r2 r3r1 r2 r3r1 r2 r3P11 0 02 2 2P24 1 12 0 2P32 1 11 0 3P40 0 24 2 02 1 26 2 36 2 37 2 37 2 39 3 49 3 49 3 6满足满足满足满足满足满足满足满足 资源资源进程进程最大需求最大需求已分配已分配还需要还需要剩余资源剩余资源r1 r2 r3r1 r2 r3r1 r2 r3r1 r2 r3P1 3 2 2 1 0 02 2 22 1 2P2 6 1 34 1 12 0 2P3 3 1 42 1 11 0 3P4 4 2 20 0 24 2 0T0T0时刻时刻资源分配表资源分配表：安全序列安全序列p2, p1,p3, p4 四 死锁的检测和恢复1 死锁死锁检测算法检测算法2023-4-24201)work=available；2)如果allocationk,*!=0，令finishk=false;否则fin
