2.4 死锁

2.4.1 死锁的概念

死锁产生的必要条件：

（1）互斥

某段时间某个资源只能被一个进程所占有。

（2）不剥夺

进程所获得的资源在未使用完成之前，不能被其他进程强行夺走，只能主动释放。

（3）请求并保持

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程所占有

（4）循环等待

死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。

2.4.2 死锁预防（资源动态分配当前）

1.破坏互斥条件

不可行，SPOOLing 技术

2.破坏不剥夺条件

复杂，增加系统开销

3.破坏请求并保持条件

采用预先静态分配法，在进程运行之前一次申请玩它所需要的所有资源。

4.破坏循环等待条件

采用顺序资源分配法，每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。

2.4.3 死锁避免（资源动态分配当中）

1.系统安全状态

存在一种顺序分配完所有资源

2.银行家算法

Dijkstra 1965 年提出了一种能够避免死锁的调度算法，成为银行家算法。一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度。下图有三个客户小明、小红、小强。每个客户都有一定的贷款额度。因为银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留 10 元来服务客户。这里将客户比作进程，贷款单位比作资源，银行家比作操作系统。

用于计算动态资源分配的完全性以避免系统进入死锁状态，不能用于判断系统是否进入死锁。

虽然银行家算法很有意义但缺乏使用价值，因为很少有进程能够在运行前知道其所需资源的最大值。

2.4.4 死锁的检测和解除（检测当前有无产生死锁）

1.资源分配图

2.死锁定理

如果能满足一个进程，那么可以消除该进程所有的边。

死锁定理：死锁等价于资源分配图不能完全化简

3.死锁解除

（1）资源剥夺法

（2）撤销进程法

（3）进程回退法