扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 前趋图简单
单选题
2022年11月第2题
收藏
分享
#操作系统
#前趋图
#第二版教材
#凯恩建议必须掌握
前趋图是一个有向无环图，记为:→={（Pi，Pj）} | 在 Pj 开始前，Pi 需要完成 }，假设系统中进程P= { P1，P2，P3，P4，P5，P6，P7，P8 }，且进程的前趋图如下图所示。那么，该前趋图可记为（__）
问题（1）
正确答案B
凯恩解析
题目考察的是进度图的表示方法，尤其是针对有向无环图（DAG）的进度依赖关系。
根据图中提供的信息，可以将图的结构转化为进度图中相应的依赖关系。图中的各节点表示不同的任务，而边表示任务之间的先后依赖关系。
在该图中，任务 P1 需要在 P2 和 P3 开始之前完成，任务 P3 必须在 P5 完成之后才能开始，P6 需要在 P5 完成之后开始，P7 必须等 P6 完成后开始，P8 需要在 P5 或 P7 完成后开始等。
通过分析图形的结构，可以发现该图的拓扑排序为：
P1 -> P2 -> P3 -> P5 -> P6 -> P7 -> P8
即任务的执行顺序应当是 P1 → P2 → P3 → P5 → P6 → P7 → P8。
因此，该进度图可以表示为：
{（P1，P2），（P1，P3），（P1，P4），（P2，P3），（P2，P5），（P3，P4），（P3，P5），（P4，P6），（P5，P7），（P5，P8），（P6，P7），（P7，P8）}
该进度图的表示方式符合进度依赖的要求。
选择选项 B。