【操作系统】前趋图与PV操作（结合前趋图解题）

考点频率★★★★★下午题必考选择题常考难度⭐⭐⭐⭐建议掌握前趋图与PV操作的互转规则这是下午题信号量填空的核心技能1️⃣ 什么是前趋图前趋图是一个有向无环图DAG用于描述多个进程或程序段之间的执行顺序依赖关系。节点表示一个进程或程序段用P1, P2, ...或S1, S2, ...表示有向边Pi → Pj表示Pi必须在Pj之前执行Pi是Pj的前驱生活类比前趋图就像菜谱里的步骤依赖图——必须“先洗菜才能切菜先切菜才能下锅”。每条有向边都代表一个“必须等上一步完成”的约束。2️⃣ 前趋图与PV操作的关系前趋图描述的是同步关系谁先谁后而PV操作是实现同步的工具。软考下午题的经典考法给前趋图补全PV操作代码中的信号量给PV操作代码画出对应的前趋图两者的转换有一套固定的规则转换规则入边 → P出边 → V对于每个节点进程/程序段规则说明入边 → P操作有几条入边开头就放几个P(信号量)按顺序等待所有前驱出边 → V操作有几条出边末尾就放几个V(信号量)逐个通知所有后继3️⃣ 完整转换示例给定前趋图┌───┐ │ S1│ └─┬─┘ │ ┌────┴────┐ │ │ ▼ ▼ ┌───┐ ┌───┐ │S2 │ │S3 │ └─┬─┘ └─┬─┘ │ │ └────┬────┘ │ ▼ ┌───┐ │ S4│ └───┘转换步骤第1步识别所有边为每条边分配一个信号量边信号量名S1 → S2aS1 → S3bS2 → S4cS3 → S4d所有信号量初值均为0同步信号量。第2步对每个节点按“入边P、出边V”规则生成代码节点入边数量出边数量需要写的PV操作S102→S2, →S3末尾写V(a); V(b)S21S1→S21S2→S4开头P(a)末尾V(c)S31S1→S31S3→S4开头P(b)末尾V(d)S42S2→S4, S3→S40开头P(c); P(d)第3步写完整的代码框架semaphore a0;// S1→S2semaphore b0;// S1→S3semaphore c0;// S2→S4semaphore d0;// S3→S4S1(){// S1的代码V(a);// 通知S2V(b);// 通知S3}S2(){P(a);// 等待S1完成// S2的代码V(c);// 通知S4}S3(){P(b);// 等待S1完成// S3的代码V(d);// 通知S4}S4(){P(c);// 等待S2完成P(d);// 等待S3完成// S4的代码}4️⃣ 反过来由PV操作画前趋图如果题目给你PV操作代码让你画前趋图按以下步骤反推找出所有信号量统计出现了哪些信号量注意初值是否为0同步信号量或1互斥信号量。同步信号量初值为0才是用来表示前趋关系的。确定边的方向对每个同步信号量s找到V(s)所在的位置和P(s)所在的位置画一条从V(s)所在的节点 →P(s)所在的节点的有向边确认节点列出所有执行单元函数/进程按边画图。示例已知代码中有一个同步信号量s初值0S1中执行V(s)S2中执行P(s)→ 画出S1 → S2。5️⃣ 考试中的常见陷阱陷阱正确做法漏掉信号量初始化每个边对应的信号量必须初值 0同步信号量P操作个数不匹配入边数量 P操作数量必须相等V操作个数不匹配出边数量 V操作数量必须相等把互斥信号量初值1混入前趋图前趋图中只涉及同步信号量初值0互斥信号量是另外加的忘记写P操作的顺序一个节点有多个P操作时顺序一般不重要因为要全部完成才能继续但应写全。前趋图中若某节点有多个前驱必须所有P都通过才能执行注意审题看信号量是“与”关系还是“或”关系。6️⃣ 经典例题例题1某系统有3个进程P1、P2、P3前趋关系为 P1→P2P2→P3。信号量s1、s2初值为0补全代码P1() { // 代码 (1) ; // 空处填什么 } P2() { (2) ; // 代码 (3) ; } P3() { (4) ; // 代码 }解边为 P1→P2 和 P2→P3。对应关系为P1的V通知P2P2先P后V通知P3。按规则填入即可。答案(1)V(s1)(2)P(s1)(3)V(s2)(4)P(s2)例题2稍复杂前趋图有4个节点S1、S2、S3、S4边为S1→S2S1→S3S2→S4S3→S4。信号量 a,b,c,d 对应4条边初值均为0。则S4中应写 。A.P(a); P(b)B.P(c); P(d)C.V(c); V(d)D.V(a); V(b)解析S4的入边是 S2→S4 和 S3→S4对应的信号量是 c 和 d。入边对应P操作所以 S4 开头写P(c); P(d)。选B。7️⃣ 记忆口诀前趋图有向无环入边P来出边V。每条边对应一信号初值全部设为0。V在末尾P在头顺序执行靠它走。8️⃣ 小测验评论区对答案某系统有4个进程P1、P2、P3、P4前趋图如下P1→P2P1→P3P2→P4P3→P4。信号量 s1、s2、s3、s4 分别对应4条边初值均为0。则 P4 中需要写几个 P 操作分别对应哪些信号量本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #前趋图 #PV操作 #进程同步 #操作系统