一、前驱图 与 PV 操作

---

1、前驱图概念

前驱图（Precedence Graph）概念 : 前驱图是一种 有向无环图（DAG），用于表示 多个进程 / 任务 之间的‌ 执行顺序 的 依赖关系‌。

• 节点‌ : 表示一个 进程 或 任务 ;
• 有向边‌（→） : 表示 任务间的依赖关系 , 若存在边 A → B , 说明 进程 B 必须等待 进程 A 完成后才能开始执行 ;
  • 进程 A 是 进程 B 的前驱 , 进程 B 是 进程 A 的后继 ;
• 核心作用‌ : 确保 多进程 / 多线程 环境下 , 存在依赖关系的任务按正确顺序执行 , 避免逻辑错误 ;

2、前驱图示例

前驱图示例 : 下图中的 A B C D E 操作分别为

• A 绞肉
• B 切葱
• C 切姜
• D 搅拌
• E 包饺子

下图中 , 如果这 5 个操作顺序执行 , 显然是错误的 ;

A 绞肉 / B 切葱 / C 切姜 互相之间没有依赖关系 , 可以独立并行执行 ;

D 搅拌 操作 的 前提是 A 绞肉 / B 切葱 / C 切姜 三个任务必须执行完毕 , 因此 D 有 ABC 三个 前驱 , D 是 ABC 的 后继 ;

D 搅拌 和 E 包饺子 的操作 有先后关系 , 搅拌完成后 才能 包饺子 , 因此 D 是 E 的 前驱 , E 是 D 的 后继 ;

下图 的 前驱图 才是 最能体现出 上述 5 个操作 的 前后依赖关系 ;

3、前驱图 的 PV 操作 - 简单版本

进程 A 和 进程 B , A 是 B 的前驱 , B 是 A 的后继 ;

前驱图 是 A → B ;

前驱进程 A 完成前 , 进程 B 无法执行 ;

" 进程 A 的 执行完成 " 就是 进程 B 需要的资源 , 这里将 " 进程 A 的 执行完成 " 的资源数量 设置为 信号量 Sa = 0 , 该信号量初始值 为 0 , 当 进程 A 执行完毕 , 执行 V ( Sa ) 操作 , 该信号量 Sa = 1 ;

该 信号量 Sa 只有 0 和 1 两个取值 ;

前驱进程 A 执行完成后 , 执行 V ( Sa ) 操作 , 释放 " 进程 A 的 执行完成 " 资源 ;

执行 进程 B 时 , 会进行 P ( Sa ) 操作 , 检查 前驱 进程 A 是否完成 , 也就是 " 进程 A 的 执行完成 " 资源 是否被释放 ;

4、前驱图 的 PV 操作 - 复杂版本

以上述 的 A B C D E 操作

• A 绞肉
• B 切葱
• C 切姜
• D 搅拌
• E 包饺子

为例 , 设置 四个 前驱进程 A B C D 四个信号量 , 分别是

• 信号量 Sa , 表示 " 进程 A 的 执行完成 " 资源的数量 , 初始值 为 0 , 也就是进程 A 没有执行完毕 , 当 进程 A 执行完毕后 , 执行 V ( Sa ) 操作 , 将信号量值设置为 1 ;
• 信号量 Sb , 表示 " 进程 B 的 执行完成 " 资源的数量 , 初始值 为 0 , 也就是进程 B 没有执行完毕 , 当 进程 B 执行完毕后 , 执行 V ( Sb ) 操作 , 将信号量值设置为 1 ;
• 信号量 Sc , 表示 " 进程 C 的 执行完成 " 资源的数量 , 初始值 为 0 , 也就是进程 C 没有执行完毕 , 当 进程 C 执行完毕后 , 执行 V ( Sc ) 操作 , 将信号量值设置为 1 ;
• 信号量 Sd , 表示 " 进程 D 的 执行完成 " 资源的数量 , 初始值 为 0 , 也就是进程 D 没有执行完毕 , 当 进程 D 执行完毕后 , 执行 V ( Sd ) 操作 , 将信号量值设置为 1 ;
  

当 执行 进程 D 之前 , 会执行

• P ( Sa ) ,
• P ( Sb ) ,
• P ( Sc )

三个 P 操作 , 检查

• " 进程 A 的 执行完成 " 资源数量
• " 进程 B 的 执行完成 " 资源数量
• " 进程 C 的 执行完成 " 资源数量

是否都为 1 , 如果不为 1 , 则继续阻塞等待 ;

当 执行 进程 E 之前 , 会执行 P ( Se ) 操作 , 检查 " 进程 E 的 执行完成 " 资源数量 是否为 1 , 如果不为 1 , 则继续阻塞等待 ;

5、前驱图 有向边 对应的 PV 操作

有向边‌（→） : 表示 任务间的依赖关系 , 若存在边 A → B , 说明 进程 B 必须等待 进程 A 完成后才能开始执行 ;

有向边 的 流出位置 , 都是 V 操作 ; 也就是 进程 执行完毕 , " 进程 的 执行完成 " 资源数量 增加 1 ;

有向边 的 流入位置 , 都是 P 操作 ; 也就是 进程 开始执行前 , 都要检查其 前驱操作 是否完成 , 也就是 " 进程 的 执行完成 " 资源数量 是否为 1 ;

二、软考考点

---

1、前驱图表示形式

前驱图如下 : 这是一个 有向无环图 ;

该前驱图可以标记为 :

→={ (P1, P2) , (P1, P3) , (P1, P4) , (P2, P5) , (P3, P5) , (P4, P6) , (P5, P7) , (P6, P7) , (P7, P8) }

2、并行操作分析

计算机 中有

• CPU 中央处理器 , 图像处理操作 Ci ( i = 1 , 2 ,3 ) , C1 / C2 / C3 分别是 CPU 的 图像处理操作 ;
• Scanner 扫描仪 , 扫描操作 Si ( i = 1 , 2 ,3 ) , S1 / S2 / S3 分别是 扫描仪 的 扫描 操作 ;
• Printer 打印机 , 打印操作 Pi ( i = 1 , 2 ,3 ) , P1 / P2 / P3 分别是 打印机 的 打印 操作 ;

① 并行操作分析

可并行操作分析 : 不存在 前驱后继 关系的操作 , 是可并行操作 ,

• C1 和 S2 操作 是可并行操作 ;
  

• P1 , C2 , S3 操作 是 可并行操作 ;
  

• P2 , C3 是 可并行操作 ;

② 直接制约关系分析

直接制约关系 ( 无法并行执行的 直接制约关系 ) :

直接制约关系 主要是 先后顺序的影响 , 导致 多个进程 无法并行执行 ;

C1 和 P1 收到 S1 的 直接制约 ;

C2 和 P2 收到 S2 的 直接制约 ;

C3 和 P3 收到 S3 的 直接制约 ;

③ 间接制约关系分析

间接制约关系 ( 无法并行执行的 间接制约关系 ) :

间接制约关系 主要是 间接使用的资源 的影响 , 导致 多个进程 无法并行执行 ;

S1 / S2 / S3 扫描操作 , 都需要用到 扫描仪 , 这三个操作 不能并行执行 , 因为 三个操作 都 间接受到 扫描仪 资源的 间接制约 ;

S2 要执行 , 必须等待 S1 执行完毕 , 这里 S2 受到 S1 的间接制约 ;

S3 要执行 , 必须等待 S1 / S2 执行完毕 , 这里 S3 收到 S1 / S2 的 间接制约 ;

总结下 间接制约关系 :

• C1 / C2 / C3 操作 不能并行执行 , 都需要用到 CPU 资源 , 都间接受到 CPU 的 制约 ;
• S1 / S2 / S3 操作 不能并行执行 , 都需要用到 扫描仪 资源 , 都间接受到 扫描仪 的 制约 ;
• P1 / P2 / P3 操作 不能并行执行 , 都需要用到 打印机 资源 , 都间接受到 打印机 的 制约 ;

相同字母的进程 , 也就是 相同类型的 进程 , 间接受到 相同资源 的制约 , 这是 间接制约关系 ;

3、前驱图 与 PV 操作结合考察

有四个进程 P1 , P2 , P3 , P4 , 对应的 前驱图 如下 :

使用 PV 操作 , 控制 P1 , P2 , P3 , P4 四个进程的执行 ;

设置 5 个信号量 S1 , S2 , S3 , S4 , S5 , 初始值 都为 0 ;

分析 上述 进程执行的 信号量 PV 操作 ;

考点 是 有向边 对应的 PV 操作 :

• 有向边 的 流出位置 , 都是 V 操作 ; 也就是 进程 执行完毕 , " 进程 的 执行完成 " 资源数量 增加 1 ;
• 有向边 的 流入位置 , 都是 P 操作 ; 也就是 进程 开始执行前 , 都要检查其 前驱操作 是否完成 , 也就是 " 进程 的 执行完成 " 资源数量 是否为 1 ;

P1 进程 : 有 0 个流入操作 ; 有 2 个 流出操作 , 是 P2 和 P3 的 前驱进程 ,

• P1 执行前 , 有 0 个 前驱操作 , 对应 0 个 P 操作 ;
• P1 执行后 , 有 2 个 后继操作 , 对应 2 个 V 操作 ;

P2 进程 : 有 2 个流入操作 , 对应 P1 和 P3 的 前驱进程 ; 有 1 个 流出操作 , 是 P4 后继进程 ,

• P2 执行前 , 有 2 个 前驱操作 , 对应 2 个 P 操作 ;
• P2 执行后 , 有 1 个 后继操作 , 对应 1 个 V 操作 ;

P3 进程 : 有 1 个流入操作 , 对应 P1 前驱进程 ; 有 2 个 流出操作 , 是 P2 和 P4 后继进程 ,

• P3 执行前 , 有 1 个 前驱操作 , 对应 1 个 P 操作 ;
• P3 执行后 , 有 2 个 后继操作 , 对应 2 个 V 操作 ;

P4 进程 : 有 2 个流入操作 , 对应 P2 和 P3 前驱进程 ; 有 0 个 流出操作 ;

• P4 执行前 , 有 2 个 前驱操作 , 对应 2 个 P 操作 ;
• P4 执行后 , 有 0 个 后继操作 , 对应 0 个 V 操作 ;

分析下面 几个位置的 信号量 操作 ;