《进程死锁》PPT课件.ppt

《《进程死锁》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《进程死锁》PPT课件.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章进程死锁死锁的概念死锁产生的原因死锁的必要条件死锁预防死锁避免死锁检测与解除死锁现象n引例：系统中有两个进程P1、P2，两份资源S1、S2，目前状况是：S1P1S2P2死锁现象进程P1拥有资源S1，进程P2拥有资源S2，但他们都在不放弃已拥有资源的情况下，申请对方所占有的资源。出现：P1和P2相互等待对方资源的现象。死锁死锁：系统中的一组进程，每一个进程都在等待另一个进程所占有的资源，使系统处于无限期的等待状态。死锁产生的原因资源分配不合理进程推进速度不合理。著名的哲学家问题:哲学家问题每个人必须同时拿到两根筷子才能吃到面条。如果每个人都拿到了一根筷子，就永远吃不到面条了。思考：思考：哲

2、学家之间是什么关系？如何用信号量和PV原语实现他们之间的制约关系？注意：死锁讨论的范畴不属于讨论的范畴进程申请了不存在的资源申请资源最大数超过了系统拥有的最大数硬件故障或程序性错误引起的循环等待假定：任何一个进程要求资源的最大数不超过系统提供最大数量申请资源得到满足，一定在有限时间内完成只有在申请资源得不到满足时才处于等待状态死锁存在的必要条件资源的互斥使用资源的不可抢占占有并等待（资源的部分分配）资源的循环等待。S1 S2P1P2资源分配图用有向图来表示进程对资源的占有情况。顶点：进程，资源边：如果一个进程已经占有了一份资源，则画一条指向进程的边。如果一个进程申请一份资源，则画一条指向资源的

3、边。如果同一份资源有多个，则用顶点中的圆点数表示。P1P2P3r1r2r3r4资源分配图用资源分配图判断死锁如果没有环路，则一定没有死锁如果有环路，且环路中资源类只有一个资源，则有死锁。如果有环路，但环路中资源类有多个资源，则不一定有死锁。例题假定某系统当时的资源分配图如下所示：（1）分析当时系统是否存在死锁。（2）若进程P3再申请R3时，系统将发生什么变化，说明原因。死锁的防止防止原理：打破死锁存在的四个必要条件之一。互斥条件：不能人为打破。占有并等待：措施一：资源的静态分配。在进程运行前，将进程所需要的所有资源分配给进程，且在整个进程运行过程中，进程所占有资源不能被其他进程使用。释放已占资

4、源死锁的防止防止不可抢夺允许抢占：资源尚未占用；进程处在等待状态只有处理器、主存资源可以抢占循环等待：资源的按序分配。将资源编号，紧缺资源的编号大，充裕资源的编号小。只有低编号的资源得到满足后，才能分配高编号资源。打破了资源的循环等待。按序分配的例哲学家问题n将叉子编号，F1、F2、F3、F4、F5P1：P2：P3：L：P（F1）L：P（F2）L：P（F3）P（F2）P（F3）P（F4）吃面吃面吃面V（F1）V（F2）V（F3）V（F2）V（F3）V（F4）GOTOLGOTOLGOTOL按序分配的例哲学家问题P4：P5：L：P（F4）L：P（F1）P（F5）P（F5）吃面吃面V（F4）V（F1

5、）V（F5）V（F5）GOTOLGOTOL8.4死锁避免n资源的动态分配：允许根据用户需求分配资源，但每次分配之前都要检查系统是否安全，如果不安全，即使有资源，也不能分配给进程。n安全的含义：如果系统中存在着一个进程序列，使所有的进程都能够运行结束，则称系统是安全的。否则是不安全的。n如何判断系统是否安全？“不安全”与死锁的区别“不安全”并不一定发生死锁死锁状态集是不安全状态集的子集不安全状态死锁状态银行家算法-基本思想一个用户对资金的最大需求量不超过银行家现有的资金用户可以分期贷款，但贷款总数不能超过最大需求量可以推迟支付，但总能在有限的时间内让用户得到贷款当用户得到所需全部资金后，一定能在

6、有限的时间内归还银行家算法-原理当进程首次申请资源时：测试该进程对资源的最大需求量，如果系统现存现存的资源可以满足它的最大需求量，则按申请分配，否则推迟分配。执行过程中申请：先测试已占用的资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量再测试系统现存的资源能否满足该进程尚尚需需的最大资源量银行家算法-数据结构系统中总的资源进程运行所需的最大资源数已经分配的资源数 P还需要申请的资源数 R银行家算法-过程准备：计算系统中的剩余资源剩余资源F；计算进进程请求资源程请求资源R（1）找到一个进程Pi，满足Ri=Ri，则说明系统不安全。（5）若所有进程都能够运行结束，则系统安全。例题教材P2

7、40例1银行家算法的应用实例现有三个进程P1、P2、P3，共享A、B、C三类资源，进程对资源的需求量和目前分配情况如下表：进程已占有资源数最大需求数ABCABCP1263265P2201201P3210285若系统还有剩余资源分别为：A类2个，B类6个，C类2个。请回答下列问题：（1）目前系统是否处于安全状态？（2）如果进程P3提出申请（0，5，2）个资源，系统是否能为它分配资源？问题1:步骤一：计算和系统当前的空闲资源为：（2，6，2）进程要运行结束，还需请求的资源为：进程ABCP1002P2000P3075步骤二：是否存在进程序列n由于P2不需要申请更多的资源，可以运行结束，释放它占有的资

8、源（2，0，1），空闲资源变为：（4，6，3）。n空闲资源满足P1的资源要求，P1运行结束，释放它占有的资源（2，6，3），空闲资源变为：（6，12，6）。n空闲资源满足P3的资源请求，P3可以运行结束。n系统中的进程能在有限时间内全部运行结束（213），所以系统是安全的。问题2:n假设可以为进程P3分配它申请的资源（0，5，2），则系统当前状况是：n空闲资源F为：（2，1，0）n进程要运行结束，还需请求的资源R为：进进 程程 A B CP1002P2000P3023是否存在进程序列:n进程P2运行，释放它所占有的资源（2，0，1），系统空闲资源变为：（4，1，1）。n由于空闲资源不能满足系统

9、中任一进程的资源请求，进程P1和P3陷入无限期等待，系统出现死锁。n所以，系统不能为P2分配资源。银行家算法-基本公式系统中资源数m个并发进程数：n个每个进程申请该类资源的最大数：x（1xm)若满足：n*(x-1)+1m 1mn时X=1+(m-1)/nmn时8.5死锁检测如果每次分配资源，都需要做一次银行家算法，系统效率会非常低。假设：系统中发生死锁的可能性很小，因此，没有必要每次都检查系统是否安全，只需定期检查以下系统是否存在死锁就可以了。当进程请求资源时，若系统中有资源，就分配给进程。如何检测系统是否死锁？死锁检测算法n原理：是否存在资源的循环等待？n资源状态图：n用有向图来表示进程对资源

10、的占有情况。n顶点：进程，资源n边：如果一个进程已经占有了一份资源，则画一条指向进程的边。n如果一个进程申请一份资源，则画一条指向资源的边。n如果同一份资源有多个，则用顶点中的圆点数表示。P1P2P3r1r2r3r4资源状态图死锁判定法则n如果资源分配图中没有环路，则系统没有死锁。n如果资源分配图中出现了环路，则系统可能存在死锁。n如果处于环路中的每个资源类中均包含一个资源实例，则意味着死锁的存在。n如果处于环路中的每个资源类中包含的资源实例个数不全为1，则环路的存在是必要条件。死锁的检测方法每类资源中只有一个资源占用表：资源占用进程等待表：进程等待资源（见P242表8-8）判断是否有循环等待

11、的进程等待占有关系与间接等待占有关系等待占有关系矩阵（见P243表8-9）当矩阵中有某个Bii（i=1，2，n）=1时，说明存在循环等待死锁的检测方法资源类中含有若干个资源按银行家算法检测例题（1）进程资源的使用情况和可用情况如下表所示：（四个进程和三类资源）（1）请画出资源分配图。（2）分析目前系统中是否会发生死锁。死锁解除n策略：n重新启动系统（撤消所有进程）n剥夺资源法n逐一终止进程n选择哪些进程剥夺资源或终止？-最小代价原则：n一个例子：甲、乙两个人，过一个独木桥最小代价原则甲乙1、甲、乙都在桥头，甲的优先级高。2、甲已经走了50米，乙走了20米。3、甲、乙都走到了桥中间，但甲的后面跟了许多人。进程的代价n进程优先数。n进程类的外部代价。n运行代价。重新启动进程并运行到当前撤消点所需要的代价。本章小结死锁的含义死锁产生的原因死锁存在的必要必要条件解决死锁问题的策略:死锁避免死锁预防死锁检测和解除两个重要的算法哲学家问题银行家算法