查看更多
当前 - 选择题 - 前趋图
简单
单选题
2021年11月第4题
#第二版教材
#必须掌握

前趋图是一个有向无环图,记为:→={(Pi,Pj)} | 在 Pj 开始前,Pi 需要完成 },假设系统中进程P={P1,P2,P3,P4,P5,P6,P7,P8},且进程的前驱图如下:

问题(1)
浓缩知识点

前趋图是用于描述进程执行先后依赖关系的有向无环图(DAG),其中节点对应进程,图中的显式有向边(Pi,Pj)代表直接前趋关系,即只有当Pi执行完成后,Pj才能启动,这种直接依赖仅由图中存在的有向边定义,不能随意添加、遗漏或颠倒边的方向,同时前趋图不能存在环,否则会引发进程循环等待的逻辑错误。此外,要区分直接前趋与间接前趋:若进程间依赖需经过至少一个中间进程传递,则属于间接前趋关系,这类关系不会体现在直接前趋的边集合中。前趋图是进程同步设计的重要工具,能清晰梳理进程间的依赖逻辑,帮助构建正确的进程执行序列。

正确答案
C

本题考察的是前趋图(DAG)中直接前趋关系的识别
直接前趋仅对应图中的有向边。观察图可读出边:P1→P2、P1→P3、P2→P3、P2→P5、P3→P4、P3→P5、P4→P6、P5→P6、P5→P7、P5→P8、P6→P8、P7→P8,刚好与选项C一致。
A选项:包含不存在的边与明显错误方向,例如(P3,P1)、(P4,P1)与(P7,P6),还出现与图相悖的关系(如同时给出(P7,P6)与(P6,P7)会形成环),不符合有向无环图且与图不符,错误。
B选项:大部分边方向正确,但把(P4,P6)误写为(P4,P5),并将(P5,P8)误写为(P8,P5),同时多写了(P6,P7)这条图中不存在的边,因此整体不正确。
C选项:逐一与图中连线吻合,无多写、漏写或方向错误,完全对应所有直接前趋关系,因此正确。
D选项:包含图中不存在或方向错误的边,如(P3,P6)、(P4,P7)、(P6,P7),还出现与图相反方向的(P6,P5)、(P7,P5),因此错误。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有