第5章死锁与饥饿幻灯片.pptVIP

第五章 死锁 本章要点： 什么是死锁？ 死锁产生的必要条件 死锁的处理 1）死锁的预防 2）死锁的避免 3）死锁的检测 4）死锁的解除 死锁的概念 死锁定义 一组并发进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。 由定义得到的结论 参与死琐的进程至少有二个； 每个参与死锁的进程均等待资源； 参与死锁的进程中至少有两个进程占有资源； 死锁进程是系统中当前进程集合的一个子集。 死锁产生的必要条件 资源独占（mutual exclusion） 进程应互斥使用资源, 当请求资源被占用 时，它被置成等待状态。 死锁的处理 死锁预防 （deadlock prevention） 死锁避免 （deadlock avoidance） 死锁检测 （deadlock detection） 死锁恢复 （deadlock recovery） 死锁预防 通过破坏死锁产生的必要条件实现，对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。 预防方法： 预先分配法(破坏保持申请条件)； 有序分配法(破坏循环等待链) 。 预先分配法 进程：运行前申请所需全部资源； 系统： 能够满足，全部分配， 否则，一个也不分配。 缺点： 资源利用效率低； 一次提出申请困难。 有序分配法 例子 算法设计 死锁避免 银行家算法 银行家算法(Cont.) 安全性检测算法 银行家算法例子 银行家算法例子 死锁的检测 死锁检测算法 死锁例子 死锁检测时刻 死锁的恢复 塞车情形一 * 软件教研室 例子： r1 和 r2为可再用资源，各一个; P1: {apply for r1; ... apply for r2; ... return r1; ... return r2;} P2:{ apply for r2; ... apply for r1; ... return r1; ... return r2;} 1 2 不可抢占（non preemption） 任一进程不能从另一进程那里抢夺资源 循环等待（circular wait） 存在一个循环等待链 。 保持申请（hold-while-applying） 一个进程请求资源得不到满足而等待时，不释放已占有的资源。 资源集：R={r1,r2,…,rn} 编号集：N={1,2,…,n} 函 数：F：R?N 进程pi可以申请资源rj中的实例??rk,pi占有rk, F(rk)?F(rj) r1 r2 rk rn ... ... 申请次序 D B A C W:直行 E：左转 S：左转 资源编号：F(D)=1; F(B)=2; F(A)=3; F(C)=4; Var S1,S2,S3,S4:semaphore; (1,1,1,1) C→D D→B→A B→A→C 是否存在塞车情况? Procedure S: P(S1); 驶入D； P(S2); 驶入B; V(S1); P(S3); 驶入A； V(S2); 驶出A; V(S3) Procedure E: P(S2); 驶入B； P(S3); 驶入A; V(S2); P(S4); 驶入C； V(S3); 驶出C; V(S4); Procedure W: P(S1); P(S4); 驶入C; 驶入D； V(S4); 驶出D； V(S1); D(s1) B(s2) A(s3) C(s4