P,V原语的应用

 

P,V原语不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。

1.用P V原语实现进程互斥

把临界区置于P(sem) 和V(sem)之间。当一个进程想要进入临界区时，它必须先执行P原语操作以将信号量sem减1，在进程完成对临界区的操作后，它必须执行V原语操作以释放它所占用的临界区。从而就实现了进程的互斥：

具体的过程我们可以简单的描述如下：

PA:

P(sem)

;

V(sem)

PB:

P(sem)

;

V(sem)

2.用P V原语实现进程同步

进程同步问题的解决同样可以采用这种操作来解决，我们假设两个进程需要同步进行，一个进程是计算进程，另一个进程是打印进程，那么这个时候两个进程的定义可以表示为：

PC（表示计算进程）

A: local buf

      repeat

buf=buf

      until buf=空

      计算

       得到计算结果

       buf=计算结果

       goto A

PP:（表示打印进程）

B: local pri

      repeat

      pri=buf

      until pri!=空

      打印buf中的数据

      清除buf中的数据

      goto B

相应用P,V原语的实现过程为：

PA: deposit(data)

Begin local x

P(bufempty)

按FIFO方式选择一个空缓冲区buf(x)

buf(x)=data

buf(x)置满标记

             V(buffull)

end

PB:remove(data)

Begin local x

P(buffull)

按FIFO方式选择一个装满

数据的缓冲区buf(x)

data=buf(x)

buf(x)置空标记

V(bufempty)

end

3.用P V原语实现进程通信

我们以邮箱通信为例说明问题：

邮箱通信满足的条件是：

<1>;发送进程发送消息的时候，邮箱中至少要有一个空格能存放该消息。

<2>;接收进程接收消息时，邮箱中至少要有一个消息存在。

发送进程和接收进程我们可以进行如下的描述：

Deposit(m)为发送进程，接收进程是remove(m). Fromnum为发送进程的私用信号量，信箱空格数n。mesnum为接收进程的私用信号量，初值为0.

Deposit(m):

Begin local x

P(fromnum)

选择空格x

将消息m放入空格x中

置格x的标志为满

V(mesnum)

end

Remove(m)

Begin local x

P(mesnum)

选择满格x

把满格x中的消息取出放m中

置格x标志为空

V(fromnum)

end

以上仅从最基本的进程问题上论述P,V原语的应用。

 

4.白子—黑子问题

　　生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：

　　（1）进程A专门拣黑子，进程B专门拣白子；

　　（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；

　　分析：

　　第一步：确定进程间的关系。由功能（2）可知进程之间是互斥的关系。

　　第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设为1。

　　实现：

　　begin

　　s:semaphore;

　　s:=1;

　　　cobegin

　　　　process A

　　　　begin

　　　　L1: P(s);

　　　　　拣黑子；

　　　　　V(s);

　　　　　goto L1;

　　　　end;

　　　　process B

　　　　begin

　　　　L2:P(s);

　　　　　拣白子；

　　　　　V(s);

　　　　　goto L2;

　　　　end;

　　　coend;

　　end;

　　判断进程间是否互斥，关键是看进程间是否共享某一公有资源，一个公有资源与一个信号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体数。如下实例：

　　5.售票问题：

　　某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。

　　分析：第一步：确定进程间的关系。售票厅是各进程共享的公有资源，当售票厅中多于20名购票者时，厅外的购票者需要在外面等待。所以进程间是互斥的关系。第二步：确定信号量及其值。只有一个公有资源：售票厅，所以设置一个信号量s。售票厅最多容纳20个进程，即可用资源实体数为20，s的初值就设为20。

　　实现：

　　begin

　　s:semaphore;

　　s:=20;

　　cobegin

　　　process PI(I=1,2,……)

　　　　begin P(s);

　　　　　进入售票厅；

　　　　　购票；

　　　　　退出；

　　　　　V(s);

　　　　end;

　　　coend

     当购票者进入售票厅前要执行P(s)操作，执行后若s大于或等于零，说明售票厅的人数还未满可进入。执行后若s小于零，则说明售票厅的人数已满不能进入。这个实现中同时最多允许20个进程进入售票厅购票，其余进程只能等待。