扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 前趋图简单
单选题
2017年11月第5题
简单
单选题
2017年11月第5题
#第二版教材
#必须掌握
前趋图是一个有向无环图，记为:→={（Pi，Pj）} | 在 Pj 开始前，Pi 需要完成 }。假设系统中进程P={P1，P2，P3，P4，P5，P6，P7，P8}，且进程的前趋图如下：
那么前趋图可记为：（__）。
问题（1）
浓缩知识点
前趋图是用于描述进程间执行先后约束关系的有向无环图（DAG），核心规则是图中的有向边（Pi，Pj）代表Pi完成后Pj才能开始执行，这类图不允许出现循环结构，否则会引发进程执行死锁问题。在操作系统中，它常被用于刻画进程同步逻辑、作业调度先后顺序等场景。梳理前趋图的边集时，需逐一明确每个进程的前驱（前置完成的进程）与后继（后续启动的进程），保证边的方向为前驱指向后继，同时要完整覆盖所有约束关系，避免出现边方向反转、关键约束边遗漏等错误，以此准确反映进程间的执行依赖逻辑。
正确答案
C
本题考察的是前趋图（有向无环图，DAG）对进程先后约束关系的表示。
根据定义，有向边（Pi，Pj）表示Pj开始前Pi必须完成。从给定图中逐一读取所有有向边，可得到：P1→P2、P1→P3、P1→P4、P2→P5、P3→P5、P4→P6、P5→P7、P6→P7、P7→P8，正好与选项C一致。
A选项把方向全部反了（如写成P2→P1），与“先做Pi再做Pj”的含义相反，错误。
B选项遗漏了关键边P3→P5与P4→P6，边集合不完整，错误。
C选项完整且方向正确，逐条对应图中的每一条有向边，正确。
D选项同样把方向反转（如写成P5→P2而非P2→P5），与定义不符，错误。
因此，选择 C。