p,v作业

例1: 使用多个进程计算Y=F1(X)+F2 (X). 解

(1) 确定并发和顺序操作

在这个问题中，F1(X)和F2 (X)的计算是可以并行处理的，因此F1(X)和F2 (X)可以分别出现在两个进程中。

(2) 确定互斥或同步的规则

在F1(X)+F2 (X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。 (3) 同步的操作流程 〈进程main〉

创立进程p1来计算F1(X)； 创立进程p2来计算F2(X)；

F1(X)计算是否完成？没有，等待；① F2(X)计算是否完成？没有，等待；② 进行加法运算。

〈进程p1〉

y1= F1(X)；

设置F1(X)计算完成标志； ③

〈进程p2〉 y1= F2(X)；

设置F2(X)计算完成标志。 ④

(4) 确定信号量的个数和含义

根据同步规则以及操作流程确定信号量的个数是2个，S1和S2： S1含义是F1(X)计算是否完成； S2含义是F2(X)计算是否完成。 (5) 确定信号量的初值 S1=0； S2=0。

(6) 确定P、V操作的位置

上面①处是一个P操作，P(S1)； 上面②处是一个P操作，P(S2)； 上面③处是一个V操作，V(S1)； 上面④处是一个V操作，V(S2)。 解法1 Main ( )

Public y, y1, y2,. P1, P2 Semaphore S1,S2 {

S1=0; S2=0;

P1=Creat(N-F1, F1,x,……); P2=Creat(N-F2, F2, x,……); P(S1); P(S2); y=y1+y2; }

Procedure F1(x)

{

y1= 计算1; V(S1)； }

Procedure F2(x) {

y2=计算2; V(S2)

}

解法2 Main ( )

Public y, y1, y2,. P1,x Semaphore S1 { inget(x); S1=0;

P1=Creat(N-F1, F1,x,……); Y2=F2(x); P(S1); y=y1+y2; }

Procedure F1(x) {

y1= 计算1; V(S1) }

采用2个进程和1个信号量来实现Y=F1(X)+F2 (X)的时候，采用的方法是父进程创立子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此F1(X)和F2(X)计算仍然是并发进行的。S1信号量的含义为F1(X)是否完成。改进的方法比原来的方法节约一个进程和一个信号量，但并发操作的程度并没有降低。

例2. 一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。

解 〈购票者进程〉 { ┋ P(S)；

进入售票厅； 购票；

退出售票厅； V(S)； }

信号量的初值 S=300

例3.2.15 针对如下所示的优先图解答下列问题： P1

P4 P2 P3

P5 P6

图 4.4 进程优先图

（1）使用信号量机构，该优先图将如何转换成正确的程序？ 解

(1) 使用信号量机构，就可以将其转换成程序。

Var S12, S13, S14, S25, S24, S35, S46, S56: Semaphores; {初值均为0} Parbegin

Begin P1; V(S12); V(S13); V(S14); End Begin P(S12); P2; V(S25); V(S24); End

Begin P(S13); P3; V(S35); End Begin P(S14); P4; V(S46); End Begin P(S25); P(S35); P5; V(S56); End Begin P(S46); P(S56); P6; End Parend

例3. 设A、B为两个并发进程，它们共享一个临界资源，其执行临界区的算法框图如下图所示。试判断该算法是否有错？请说明理由。如果有错，请改正。S1、S1的初值为0，CSA、CSB为临界区。

CSA P(S1) V(S1) A进程 CSB B进程 P(S2) V(S2) 图 4.3 进程操作图

分析 咋一看， 好像是A进程开始未执行P操作，便直接进入临界区，以为问题出在这里。从图中可分析出A、B两进程的执行思路：A进程对临界资源操作结束后，将其释放给B进程，而B进程对临界资源操作结束后，将释放给进程A。系统初启时，S1、S2初值为0，则B执行P(S1)被阻塞，而A进程可直接访问临界资源。故A、B两个并发进程不可能同时操作临界资源，该算法是可以保证互斥的。按本题的要求，两个进程对临界资源的操作是没有先后顺序的，但是，在上面的实现中，只有A进程先操作完临界资源后，B进程才能操作。

解 该算法有错。

若A进程永不要求访问临界资源，则不会执行V(S1)，意味着B进程的申请永远得不到操作临界资源的机会；同理，若B进程不要求访问临界资源，则不会执行V(S2)，意味着A进程下次也得不到操作临界资源的机会。所以问题在于本应进行互斥控制而使用的却是同步控制。实现改正：

设置信号mutex mutex:=1;

cobegin A进程： Begin repeat

P(mutex); CSA;

V(mutex);

until false

End

B进程： Begin repeat

P(mutex); CSB;

V(mutex);

until false

End

Coend