前趋图

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

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

如上图：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 变为非阻塞。

前趋图表示

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

答案：→=

练习题

以下题目需要结合原题库中的前趋图图示，建议在 Obsidian 中对照图示作答。

[Q21] 前趋图表示

Q21. 进程 P1、P2、P3、P4、P5 的前趋图如下。

若用 PV 操作控制进程并发执行的过程，则需要相应于进程执行过程设置 5 个信号量 S1、S2、S3、S4 和 S5，且信号量初值都等于零。下图中 a 处应填写 （1） ；b 和 c、d 和 e 处应分别填写 （2），f、g 和 h 应分别填写 （3） 。

• A. P（S1）和 P（S2）
• B. V（S1）和 V（S2）
• C. P（S1）和 V（S2）
• D. P（S2）和 V（S1）

📝答案与解析

正确答案：B

根据前驱图，P1进程运行结束需要利用V操作分别通知P2和P3进程，所以用V(S1)操作通知P2进程，用V(S2)操作通知P3进程。

[Q29] 前趋图表示

前趋图是一个有向无环图，记为→=｛（Pi，Pj）pi完成时间先于Pj开始时间｝。假设系统中进P=｛P1，P2，P3，P4，P5，P6，P7，P8｝，那么，该前趋图可记为（1），图中（2）。

• A. →={（P1，P2），（P1，P3），（P1，P4），（P2，P5），（P3，P2），（P3，P4），（P3，P6），（P4，P7），（P5，P8）
• B. →={（P1，P2），（P1，P4），（P2，P3），（P2，P5），（P3，P4），（P3，P6），（P4，P7），（P5，P6），（P7，P6），（P6，P8）}
• C. →={（P1，P2），（P1，P4），（P2，P5），（P3，P2），（P3，P4），（P3，P6），（P4，P6），（P4，p7），（p6，p8），（p7，P8）}
• D. →={（P1，P2），（P1，P4），（P2，P3），（P2，P5），（P3，P4），（P3，P6），（P4，P7），（P5，P6），（P5，P8），（P7，P6），（P6，P8）}

📝答案与解析

答案：D

解析：逐一核对图中每条有向边，D 选项完整匹配前趋图关系。

---

[Q30] 前趋图关系

同上题图，那么图中（2）正确的是（ ）。

• A. 存在着11个前趋关系，P1为初始结点，P8为终止结点
• B. 存在着2个前趋关系，P6为初始结点，P2P4为终止结点
• C. 存在着9个前趋关系，P6为初始结点，P8为终止结点
• D. 存在着10个前趋关系，P1为初始结点，P7为终止结点

📝答案与解析

答案：A

解析：图中 11 条有向边，P1 无前驱（初始），P8 无后继（终止）。

---

[Q67] 前趋图用途

在软件项目管理中，前趋图主要用于表示任务之间的哪些关系（ ）。

• A. 任务的优先级和重要性
• B. 任务的资源分配和成本估算
• C. 任务之间的并行和顺序关系
• D. 任务的完成时间和延迟风险

📝答案与解析

答案：C

解析：前趋图=有向无环图，表达任务间的先后依赖关系（哪些可并行、哪些必须顺序）。

---

以下 PV 操作综合题需对照原题库中的前趋图作答。

[Q66] PV前趋规则 （已在进程管理文件）

在使用信号量实现前驱关系时，信号量数量等于有向边数量，初始值为0。前驱完成后执行V，后继执行前P。

---

[Q8] PV前趋图-P1~P5

进程P1、P2、P3、P4和P5的前趋图如下：

若用PV操作控制进程P1～P5并发执行的过程，则需要设置6个信号S1～S6，初值都等于零。图中a和b处应分别填写（1）；c和d处应分别填写（2），e和f处应分别填写（3）。

• A. P(S1)P(S2)和P(S3)P(S4)
• B. P(S1)V(S2)和P(S2)V(S1)
• C. V(S1)V(S2)和V(S3)V(S4)
• D. P(S1)P(S2)和V(S1)V(S2)

📝答案与解析

答案：C

解析：a和b处P1执行完后发出信号→V(S1)V(S2)。口诀：前驱V后继P。

---

[Q32] 生产者消费者变体

某企业的生产流水线上有2名工人P1和P2，1名检验员P3。P1将半成品放入B1；P2从B1取出继续加工，加工好的产品放入B2；P3从B2取出产品检验。

B1可存放n件，B2可存放m件。设置6个信号量S1～S6，S3和S6的初值都为0。则信号量S1和S5（ ）；S2、S4的初值分别为（ ）。

• A. 分别为同步信号量和互斥信号量，初值分别为0和1
• B. 都是同步信号量，其初值分别为0和0
• C. 都是互斥信号量，其初值分别为1和1
• D. 都是互斥信号量，其初值分别为0和1

📝答案与解析

答案：C

解析：S1(B1互斥)和S5(B2互斥)都是互斥信号量，初值=1。S2=n(空位数)，S4=m(空位数)。

---

[Q33] 生产者消费者变体-初值

同上题。S2、S4的初值分别为（ ）。

• A. n、0
• B. m、0
• C. m、n
• D. n、m

📝答案与解析

答案：D

解析：S2=B1空闲位数量初值=n；S4=B2空闲位数量初值=m。