前趨圖與PV操作，一般出現(xiàn)了，分值在2~3分左右，技巧性很強(qiáng)。

前趨圖

前趨圖是為了描述一個(gè)程序的各部分間的依賴關(guān)系，或者是一個(gè)大的計(jì)算的各個(gè)子任務(wù)間的因果關(guān)系的圖示。

注意：前趨圖中必須不存在循環(huán)

前趨圖中的每個(gè)結(jié)點(diǎn)可以表示一條語(yǔ)句、一個(gè)程序段或一個(gè)進(jìn)程，結(jié)點(diǎn)間的有向邊表示兩個(gè)結(jié)點(diǎn)之間存
在的偏序（Partial Order）或前趨關(guān)系（Precedence Relation）“→”，
→={(Pi,Pj)|在Pj開(kāi)始前Pi必須完成}
如果（Pi，Pj）∈→，可寫成Pi→Pj，Pi是Pj的直接前趨，Pj是Pi的直接后繼
例如，具有九個(gè)結(jié)點(diǎn)的前趨圖：
P1為初始結(jié)點(diǎn)，P9為終止結(jié)點(diǎn)
每個(gè)結(jié)點(diǎn)還具有一個(gè)重量
該前趨圖，存在下面的前趨關(guān)系：
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操作

前趨圖節(jié)點(diǎn)表示進(jìn)程，箭頭表示進(jìn)程間的先后關(guān)系，前趨節(jié)點(diǎn)完成之后，才能執(zhí)行后繼節(jié)點(diǎn)。

復(fù)雜一點(diǎn)的前趨圖，會(huì)有進(jìn)程之間的并行關(guān)系，會(huì)體現(xiàn)進(jìn)程之間的直接制約關(guān)系
前趨圖可以體現(xiàn)直接制約關(guān)系，也就是同步關(guān)系。

在執(zhí)行D操作的時(shí)候，必須先去驗(yàn)證前趨節(jié)點(diǎn)是否已經(jīng)準(zhǔn)備就緒，也就是說(shuō)，需要P(Sa)、P(Sb)、P(Sc)操作去驗(yàn)證ABC三個(gè)前趨節(jié)點(diǎn)是否已經(jīng)完成；而PV操作是成對(duì)出現(xiàn)的，因此有了P操作，還需要三個(gè)V操作與之對(duì)應(yīng)。

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

也就是說(shuō)，在前趨圖中，所有的箭線中的箭頭流出會(huì)對(duì)應(yīng)一個(gè)V操作，箭頭流入對(duì)應(yīng)一個(gè)P操作

用前趨圖表示PV就是

練習(xí)

某計(jì)算機(jī)系統(tǒng)中有一個(gè)CPU、一臺(tái)掃描儀、一臺(tái)打印機(jī)?，F(xiàn)有三個(gè)圖像任務(wù)，每個(gè)任務(wù)有三個(gè)程序段：掃描Si，圖像處理Ci，打印Pi，i=(1,2,3)。
下圖為三個(gè)任務(wù)個(gè)程序段并發(fā)執(zhí)行的前趨圖，其中，（A）可并行執(zhí)行，（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

并行執(zhí)行： 不存在前趨后繼關(guān)系的，表示可以并行執(zhí)行；
直接制約關(guān)系：有先后順序影響的是直接制約關(guān)系；
間接制約關(guān)系：屬于一整套流程(流水線)，但是需要上個(gè)流程執(zhí)行完畢。