考点清单

• [x] 前趋图概念与表示
• [x] 进程资源图（阻塞节点/非阻塞节点/死锁判断）
• [x] 资源图化简方法

笔记

前趋图

用来表示哪些任务可以并行执行，哪些任务之间有顺序关系：

• 任务间的并行：无依赖关系的任务可同时执行
• 任务间的先后顺序：前驱任务完成后，后继任务才能开始

如上图：A、B、C 可并行执行，但必须全部完成后才能执行 D。

进程资源图

用来表示进程和资源之间的分配和请求关系：

• P 代表进程，R 代表资源，R 方框中圆球数 = 该资源的个数
• R→P 箭头：资源已分配给进程
• P→R 箭头：进程还需请求该资源

节点判断：

• 阻塞节点：进程所请求的资源已全部分配完毕，无法获取所需资源（如上图 P2）
• 非阻塞节点：进程所请求的资源还有剩余，可以分配给该进程（如上图 P1、P3）
• 死锁：进程资源图中所有进程都是阻塞节点时，陷入死锁

资源图化简方法：从非阻塞节点开始，将其所有边去掉变成孤立点，回收分配给它的资源，重复此过程直到所有节点孤立；若无法全部化简则存在死锁。

练习题

进程资源图判断

问题：关于图中进程状态和化简顺序，正确的是？

答案：P1、P2是阻塞节点，P3是非阻塞节点；化简顺序为 P3→P1→P2。

解析：P3 不阻塞，先孤立 P3 并回收资源 R1，此时 P1 获得 R2 变为非阻塞，孤立 P1 回收 R2，最后 P2 获得 R1 变为非阻塞。

前趋图表示

问题：图中前趋图应记为？

答案：→=