DeadLock

死锁 ：两个或多个进程无线等待一个事件，而该事件只能由等待进程之一来产生

死锁特征

死锁产生的必要条件 ：

• 互斥，至少一个资源处于非共享状态
• 占有并等待，一个进程必须占有一个资源并等待另一个资源
• 非抢占，资源不能被抢占
• 循环等待，有一组等待进程{P1,P2,P3…Pn}，P1等待P2，P2等待P3…

系统中上述四个条件同时满足会引起死锁

资源分配图

死锁问题可通过资源分配图来简化

• Pi -> Rj 称为申请边
• Rj -> Pi 称为分配边

如果资源分配图没有环，那么系统不处于死锁状态，另一方面，如果有环，系统可能处于死锁

• 若每种资源的实例只有一个，则处于死锁
• 若每种资源的实例有多个，则不一定死锁

死锁处理

• 可通过协议以预防或避免死锁，确保系统不会进入死锁状态（预防）
• 可允许系统进入死锁状态，然后检测恢复（检测恢复）
• 可忽视这个问题，认为死锁不可能发生在系统内（避免）

死锁预防

通过使产生死锁的必要条件不成立来预防

• 互斥 ：共享资源（有的资源不能共享，所以此条牵强）
• 占有等待 ：保证一个进程申请资源时，不能占有其它资源
• 非抢占 ：如果一个进程申请一个不能被立即释放的资源，那么其现拥有的资源可抢占
• 循环等待 ：一个进程申请Rj时，必须先释放Ri（i的顺序在j前面）

死锁检测和恢复

系统应提供一个用来检测系统是否死锁的算法和一个用来从死锁状态恢复的算法

死锁恢复的方法

• 终止一个或多个进程打破循环
• 从死锁进程中抢占资源

死锁避免

要求操作系统事先得到有关进程申请资源的额外信息，使用这些信息决定如何分配资源，死锁避免算法动态检测资源分配状态以确保循环等待条件不可能发生

有两种算法

• 资源分配图算法
• 银行家算法

资源分配图算法

在图中引入一种新类型的边，申请边：Pi -> Rj 表示Pi可能在未来某个时间申请Rj，申请边用虚线表示，在申请的时候变成实现

只有在申请边变成分配边不会导致图中形成环的时候才分配

银行家算法

在其它博客中详细讲，请移步