面试题：并发与同步：操作系统需求图在死锁避免中的基础应用

Question

请简要阐述操作系统需求图的构成元素，以及如何利用它来检测系统是否可能进入死锁状态，并举例说明一个简单系统中通过需求图进行死锁检测的步骤。

Answer 1

操作系统需求图的构成元素

1. 进程节点（Process Nodes）：用圆圈表示，代表系统中的各个进程。每个进程可能需要获取和释放不同类型的资源以完成其任务。
2. 资源节点（Resource Nodes）：用矩形表示，代表系统中的各类资源。资源节点中的小黑点表示该资源类型的具体实例数量。
3. 请求边（Request Edges）：从进程节点指向资源节点的有向边，表示进程对某种资源的请求。例如，进程 ( P_i ) 指向资源 ( R_j ) 的请求边，表示 ( P_i ) 请求 ( R_j ) 类型的资源。
4. 分配边（Allocation Edges）：从资源节点指向进程节点的有向边，表示资源已分配给某个进程。例如，资源 ( R_j ) 指向进程 ( P_i ) 的分配边，表示 ( R_j ) 类型的某个资源实例已分配给 ( P_i )。

利用需求图检测系统是否可能进入死锁状态

1. 化简需求图：
   • 寻找一个既不阻塞（即其请求的所有资源都有可用实例）也不孤立（即至少有一条请求边或分配边与之相连）的进程节点。
   • 将该进程节点及其所有相关的请求边和分配边从需求图中移除。这模拟了该进程获取所需资源并执行完毕后释放资源的过程。
   • 重复上述步骤，对剩余的需求图进行化简。
2. 判断死锁状态：
   • 如果最终需求图中所有节点（进程节点和资源节点）都被移除，说明系统不存在死锁，因为所有进程都可以按照某种顺序依次获取资源并执行完毕。
   • 如果化简过程无法移除所有节点，即存在至少一个进程节点无法满足其资源请求（请求边指向的资源没有足够可用实例），且不能通过移除其他进程节点来改变这种情况，那么系统可能进入死锁状态。

简单系统中通过需求图进行死锁检测的步骤举例

假设系统中有两个进程 ( P1 ) 和 ( P2 )，两种资源 ( R1 )（有 1 个实例）和 ( R2 )（有 1 个实例）。

1. 初始需求图：
   • 进程 ( P1 ) 有一条请求边指向资源 ( R1 )，表示 ( P1 ) 请求 ( R1 )。
   • 资源 ( R1 ) 有一条分配边指向进程 ( P2 )，表示 ( R1 ) 已分配给 ( P2 )。
   • 进程 ( P2 ) 有一条请求边指向资源 ( R2 )，表示 ( P2 ) 请求 ( R2 )。
   • 资源 ( R2 ) 有一条分配边指向进程 ( P1 )，表示 ( R2 ) 已分配给 ( P1 )。
2. 化简过程：
   • 对于进程 ( P1 )，它请求 ( R1 )，但 ( R1 ) 已分配给 ( P2 )，所以 ( P1 ) 阻塞。
   • 对于进程 ( P2 )，它请求 ( R2 )，但 ( R2 ) 已分配给 ( P1 )，所以 ( P2 ) 阻塞。
   • 由于没有既不阻塞也不孤立的进程节点可移除，化简无法继续。
3. 结论：
   • 需求图无法完全化简，存在无法满足资源请求的进程节点，所以该系统可能进入死锁状态。