计算机操作系统原理与核心设计-第6章.ppt

*/19 4. 银行家算法举例： 设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图: 资源情况 进程 Max A B C Allocation A B C Need A B C Available 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 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 (1) T0时刻可以找到一个安全序列{p1,p3,p4,p2,p0}, 系统是安全的 */19 4. 银行家算法举例： (2) P1发出请求Request(1,0,2)，执行银行家算法: 资源情况 进程 Max A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 2 3 0 P1 3 2 2 2 0 0 3 0 2 1 2 2 0　2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 可以找到一个安全序列{p1,p3,p4,p0,p2}，系统是安全的，可以将P1的请求分配给它。 */19 4. 银行家算法举例： (３) P4发出请求Request(3,3,0), 执行银行家算法: 资源情况 进程 Max A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 1 0 7 4 3 2 3 0 P1 3 2 2 3 0 2 0　2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 Available=（2, 3, 0），Request[i]≤Available ），所以P4等待。 */19 4. 银行家算法举例： (4) P0请求资源Request（0，2，0），执行银行家算法，试分配后: 资源情况 进程 Max A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 3 0 2 0　2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 Available＝(2,1,0) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配 */19 6.5 死锁的检测与解除 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行 */19 6.5.1 死锁的检测 1.资源分配图（SRAG） 由二元组G=（V，E） V：结点集，分为P(进程)，R(资源)两部分 P={p1,p2,…,pn}, R={r1,r2,…,rm} E：边的集合，其元素为有序二元组: (pi,rj)或(rj,pi) */19 6.5.1 死锁的检测 1.资源分配图（SRAG） 表示法 资源类:用方框表示（资源的不同类型） 资源实例:用方框中的黑圆点表示（存在于每个资源中） 进程 :用圆圈中加进程名表示 分配边：资源实例?进程的一条有向边 申请边：进程?资源类的一条有向边 */19 6.5.1 死锁的检测 资源分配图示例 */19 6.5.1 死锁的检测 2. 死锁判定法则 (1)如果资源分配图(SRAG)中没有环路，则系统内没有死锁。 (2)如果SRAG中有环路，且每类资源只有一个，则有环是系统存在死锁的必要充分条件。 (3)如果SRAG中有环路，但每类资源的个数不全为1，则可以利用对SRAG化简的方法，来检测系统是否存在死锁 */19 资源分配图示例 有环无死锁 */19 资源分配图示例 有环有死锁 */19 6.5.1 死锁的检测 资源分配图化简 1）找一个非孤立进程结点且只有分配边，去掉分配边，将其变为孤立结点 2）再把相应的资源分配给一个等待该资源的进程，即将