1. The Deadlock Problem

2. System Model

资源类型（resource type)： R 1 , R 2 , . . . , R m R_1,R_2,...,R_m R1​,R2​,...,Rm​
例如CPU cycle，内存空间，IO设备

认为每个资源类型Ri拥有Wi数量的实例，这些实例被process利用

每个进程使用一系列的protocol利用这些资源类型的实例：

• request
• use
• release

3. Deadlock Characterization

如果以下情况同时发生，死锁就有可能出现

• Mutual exclusion：对某种资源，在同一时间只有1个进程能够对它进行使用（同时刻的互斥性）。
• hold and wait：
• no preemption：除非进程完成工作并且主动释放资源，否则资源不会被释放
• circular wait：在系统中存在一个环形回路集合：{P0,P1,…Pn}，其中P0等P1，P1等P2,…Pn却在等P0.

Resource-Allocation Graph（资源分配图）

有两种类型的节点：

• process：用圆表示
• resource：用方块表示，方块内的小方块表示资源的instance

两种边:

实例：

此处没有死锁
有死锁的情况

有cycle但没有死锁（没有hold and wait）
从这个例子中也能看出来，每个resource的instance是通用的

所以可发现:
有cycle是有死锁的必要不充分条件。要视资源的instance情况而定

4. Methods for Handling Deadlocks

可选的几条策略：

• 防止死锁情况发生
• 允许系统进入死锁情况，但是可以让这种情况恢复正常
• 无视死锁情况，假装死锁从未发生（但却是在操作系统最常用的策略）

5. Deadlock Prevention

对应四种情况的策略：
见ppt

Circular wait：给所有资源编号，而每个进程只能从小到大申请资源

6. Deadlock Avoidance

需要系统添加 priori(先验) 的信息

• 简单却最有用：每个进程事先申报一下它每种资源使用的最大数量

safe state

老师的解释：系统的进程可以以一种确定的排列方式，这样他们可以使用可用的资源而全部完成

重要的推论

• 如果系统能够进入safe state => 必然没有deadlock
• 如果系统处于unsafe state => 有可能出现deadlock
• avoidance的目的就是防止系统进入unsafe state。

avoidance algorithm

分single和multiple instance

Resource-allocation Graph Scheme

• 添加了Claim edge：如果Pj可能会请求Rj，那么画一条虚线：Pi → Rj
• 如果确实请求了，Claim edge就变成了实线的Request edge

例子:

处于unsafe state的 RAG：

对应的算法见ppt

Banker`s Algorithm

前提条件：

• multiple instances
• 每个process必须提供一个先验的最大使用量
• 当进程请求资源时，它可能需要等待
• 当进程获得了它的所有所需资源后，它必须在有限时间内归还