死锁特征
必要条件
- 互斥(Mutual exclusion)
- 占有与等待(Hold and wait)
- 非抢占(No preemption)
- 循环等待(Circular wait)
资源分配图
死锁问题可用系统资源分配图的有向图进行更为精确描述。
从进程Pi指向资源Rj的有向边称为申请边，有向边Rj -> Pi称为分配边。
在图上，用圆形表示进程Pi，用矩形表示资源类型Rj。由于资源类型Rj可能有多个实例，所以在矩形中用圆点表示实例。
如果分配图没有环，那么系统就没有进程死锁。如果分配图有环，那么可能存在死锁。
如果每个资源类型刚好有一个实例，那么有环就意味着已经出现死锁。如果环涉及一组资源类型，而每个类型只有一个实例，那么就出现死锁。环所涉及的进程就死锁。
如果每个资源类型有多个实例，那么有环并不意味着已经出现了死锁。
死锁处理方法
- 可使用协议以预防或避免死锁，确保系统不会进入死锁状态。
- 可允许系统进入死锁状态，然后检测它，并加以恢复。
- 可忽视这个问题，认为死锁不可能在系统内发生。
死锁预防(Deadlock Prevention)
通过确保至少一个必要条件不成立
互斥
通过资源共享，但是，通常不能通过否定互斥条件来预防死锁，因为有的资源本身就是非共享的。
占有与等待
通过保证：当一个进程申请一个资源时，它不能占有其他资源。例如：每个进程在执行前申请并获得所有资源；或者，允许进程在没有资源时才可申请，在申请更多其他资源之前，必须释放现已分配的所有资源。
这两种协议的缺点：
- 资源利用率低
- 可能发生饥饿，一个进程如果需要多个常用资源，可能会永久等待。
非抢占
可以使用以下协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。
循环等待
一个确保此条件不成立的方法是对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。
死锁避免
死锁预防的方法限制确保四个必要条件之一不会发生，因此死锁不成立。然而，通过这种方法预防死锁的副作用是低设备使用率和系统吞吐率
安全状态：对于进程序列\
安全状态不是死锁状态。相反，死锁状态是不安全状态。然而，不是所有不安全状态都能导致死锁状态。只要状态为安全，操作系统就能避免思索状态。
资源分配图算法
银行家算法
数据结构：
- Available：表示每种资源的现有实例数量
- Max：n * m矩阵，定义每个进程的最大需求
- Allocation：n * m矩阵，定义每个进程现在已分配的各种资源类型的实例数量。
- Need：n * m矩阵，表示每个进程还需要的剩余的资源。
安全性算法：
