2.2操作系统-进程管理：前趋图、前趋图与PV操作

前趋图与PV操作，一般出现了，分值在2~3分左右，技巧性很强。

前趋图

前趋图是为了描述一个程序的各部分间的依赖关系，或者是一个大的计算的各个子任务间的因果关系的图示。

注意：前趋图中必须不存在循环

前趋图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存
在的偏序（Partial Order）或前趋关系（Precedence Relation）“→”，
→={(Pi,Pj)|在Pj开始前Pi必须完成}
如果（Pi，Pj）∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继
例如，具有九个结点的前趋图：
P1为初始结点，P9为终止结点
每个结点还具有一个重量
该前趋图，存在下面的前趋关系：
P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，
P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；
或表示为：
P={P1,P2,P3,P4,P5,P6,P7,P8,P9}
={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),
(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),
(P8,P9)}

前趋图与PV操作

前趋图节点表示进程，箭头表示进程间的先后关系，前趋节点完成之后，才能执行后继节点。

复杂一点的前趋图，会有进程之间的并行关系，会体现进程之间的直接制约关系
前趋图可以体现直接制约关系，也就是同步关系。

在执行D操作的时候，必须先去验证前趋节点是否已经准备就绪，也就是说，需要P(Sa)、P(Sb)、P(Sc)操作去验证ABC三个前趋节点是否已经完成；而PV操作是成对出现的，因此有了P操作，还需要三个V操作与之对应。

A完成之后，会有V(Sa)；
B完成之后，会有V(Sb)；
C完成之后，会有V(Sc)；

也就是说，在前趋图中，所有的箭线中的箭头流出会对应一个V操作，箭头流入对应一个P操作

用前趋图表示PV就是

练习

某计算机系统中有一个CPU、一台扫描仪、一台打印机。现有三个图像任务，每个任务有三个程序段：扫描Si，图像处理Ci，打印Pi，i=(1,2,3)。
下图为三个任务个程序段并发执行的前趋图，其中，（A）可并行执行，（C）的直接制约，（B）的间接制约。

A.“C1S2” “P1C2S3” “P2C3”
B.“C1S1” “S2C2P2” “C3P3”
C.“S1C1P1” “S2C2P2” “S3C3P3”
D.“S1S2S3” “C1C2C3” “P1P2P3”

A.S1受到S2和S3、C1受到C2和C3、P1受到P2和P3
B.S2和S3受到S1、C2和C3受到C1、P2和P3受到P1
C.C1和P1受到S1、C2和P2受到S2、C3和P3受到S3
D.C1和S1受到P1、C2和S2受到P2、C3和S3受到P3

A.S1受到S2和S3、C1受到C2和C3、P1受到P2和P3
B.S2和S3受到S1、C2和C3受到C1、P2和P3受到P1
C.C1和P1受到S1、C2和P2受到S2、C3和P3受到S3
D.C1和S1受到P1、C2和S2受到P2、C3和S3受到P3

并行执行： 不存在前趋后继关系的，表示可以并行执行；
直接制约关系：有先后顺序影响的是直接制约关系；
间接制约关系：属于一整套流程(流水线)，但是需要上个流程执行完毕。