信号量的PV操作(例题)汇总.doc

信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。
参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。
V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。
PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。

1、 设公共汽车上，司机和售票员的活动分别是：
司机的活动：启动车辆；
正常行车；
到站停车；
售票员的活动：
关车门；
售票；
开车门；
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。

设两个信号量S和C，初值为S＝0；C＝0；
司机： L1： 正常行车 售票员： L2： 售票
到站停车 P（S）
V（S） 开车门
P（C） 关车门
启动开车 V（C）
GO TO L1 GO TO L2

2、请用PV操作实现他们之间的同步关系：
（1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。
（2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。
参考答案：
第一步：确定进程
4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter（女儿）
Father进程：
l 将苹果放入盘中
Mother进程：
l 将桔子放入盘中
Son进程：
l 从盘中取出桔子
l 吃桔子
Daughter进程：
l 从盘中取出苹果
l 吃苹果
第二步：确定进程的同步、互斥关系
l 同步：Father当盘中无水果时，才可以将苹果放入盘中
l 同步：Mother当盘中无水果时，才可以将桔子放入盘中
l 同步：Son当盘中有桔子时，才可以从盘中取出桔子
l 同步：Daughter当盘中有苹果时，才可以从盘中取出苹果
第三步：设置信号量
l 盘中无水果，Sp，初值1
l 盘中有桔子，So，初值0
l 盘中有苹果，Sa，初值0
第四步：用伪代码描述
begin
Sp,So,Sa：semaphore;
Sp :=1;
So :=0;
Sa :=0;
cobegin
Father ( );
Mother ( );
Son ( );
Daughter ( );
coend;
end;

process Father ( )
begin
L1: P（Sp）;
将苹果放入盘中；
V（Sa）;
goto L1;
end;

process Mother ( )
begin
L2: P（Sp）;
将桔子放入盘中；
V（So）;
goto L2;
end;

process Son ( )
begin
L3: P（So）;
从盘中取出桔子；
V（Sp）
吃桔子；
goto L3；
end;

process Daughter ( )
begin
L4: P（Sa）;
从盘中取出苹果；
V（Sp）
吃苹果；
goto L4；
end;

（2）
第一步：确定进程
3个进程Father（爸爸）、Mother（妈妈）、Son（儿子）
Father进程：
l 将苹果放入盘中
Mother进程：
l 将桔子放入盘中
Son进程：
l 从盘中取出水果（桔子或苹果）
l 吃水果（桔子或苹果）
第二步：确定进程的同步、互斥关系
l 同步：Father当盘中无水果时，才可以将苹果放入盘中
l 同步：Mother当盘中无水果时，才可以将桔子放入盘中
l 同步：Son当盘中有水果（桔子或苹果）时，才可以从盘中取出水果
第三步：设置信号量
l 盘中无水果，empty，初值1
l 盘中有水果（桔子或苹果），full，初值0
第四步：用伪代码描述
begin
empty, full：semaphore;
empty:=1;
full :=0;
cobegin
Father ( );
Mother ( );
Son ( );
coend;
end;

process Father ( )
begin
L1: P（empty）;
将苹果放入盘中；
V（full）;
goto L1;
end;

process Mother ( )
begin
L2: P（empty）;
将桔子放入盘中；
V（full）;
goto L2;
end;

process Son ( )
begin
L3: P（full）;
从盘中取出水果;
V（empty）;
吃水果;
goto L3；
end;

3. 某工厂有一个可以存放设备的仓库，总共可以存放10台设备。生产的每一台设备都必须入库，销售部门可从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一台运输工具，每次只能运输一台设备。请设计一个能协调工作的自动调度管理系统。
参考答案：
第一步：确定进程
可以为入库（Pin）和出库（Pout）各设置一个进程
Pin进程：
l 生产了一台设备
l 使用运输工具入库
Pout进程：
l 使用运输工具出库
l 提出设备供应客户
第二步：确定进程的同步、互斥关系
l 同步：当仓库中有空余位置存放设备时，设备才可以入库
l 同步：当仓库中有存放的设备时，设备才可以出库
l 互斥：运输工具是临界资源，要互斥访问
第三步：设置信号量
l 仓库中有空余位置数量，empty，初值10
l 仓库中有存放的设备数量，full，初值 0
l 为运输工具设置互斥信号量S，初值 1，表示当前可用
第四步：用伪代码描述
begin
empty, full, S：semaphore;
empty := 10;
full := 0;
S := 1;
cobegin
Pin ();
Pout ();
coend;
end;

process Pin ( )
begin
L1: 生产了一台设备 ;
P（empty）;
P (S);
使用运输工具入库;
V （S）;
V（full）;
goto L1;
end;

process Pout ( )
begin
L2: P（full）;
P (S);
使用运输工具出库;
V （S）;
V（empty）;
提出设备供应客户;
goto L2;
end;

4、写者优先的“读者――写者”问题：
1）共享读
2）互斥写、读写互斥
3）写者优先于读者（一旦有写者，则后续 读者必须等待，唤醒时优先考虑写者）

wmutex:semaphore=1 //读者与写者之间、写者与写者之间互斥使用共享数据
S：semaphore=1 //当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成
S2：semaphor＝1 //阻塞第二个以后的等待读者
readcount,writecount: semaphore = 0,0; //当前读者数量、写者数量
mutex1 :semaphore = 1 //多个读者互斥使用readcount
mutex2 :semaphore = 1 //多个写者互斥使用writecount
Cobegin:
Reader: begin
Repeat
Wait（S2）；
wait(S);
wait(mutex1)
if readcount=0 then wait(wmutex);
readcount++;
signal (mutex1);
signal(S);
signal（S2）；
reading…
wait(mutex1);
readcount--;
if readcount=0 then signal(wmutex);
signal(mutex1);
until false;
begin;
writer: begin
repeat;
wait(mutex2);
if writecount=0 then wait(S);
writecount++;
signal （mutex2）;
wait(wmutex);
writing…
signal(wmutex);
wait(mutex2);
writecount--;
if writecount=0 then signal(S);
signal （mutex2）;
until false;
end;
coend;

5、有一个仓库，可以存放A、B两种产品，但要求：
① 每次只能存入一种产品（A或B）；
② A产品数量－B产品数量 Begin
Loop:
P(Sb);
P(Mutex);
产品B入库；
V(Mutex);
V(Sa);
Goto Loop;
End;
CoEnd;

5、进程A1、A2、……An1通过m个缓冲区向进程B1、B2……Bn2不断地发送消息。发送和接收工作遵循如下规则：
（1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；
（2） 对每一个消息，B1，B2，…，Bn都必须接收一次，读入各自的数据区内；
（3）m个缓冲区都满时，发送进程等待没有可读的消息时，接收进程等待。

解答：本题是生产者——消费者问题的一个变形，一组生产者A1，A2，…….An1和一组消费者B1，B2，……Bn2公用m个缓冲区，每个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。
Mutex,empty[n2],full[n2]:semaphore;
Mutex=1; //多进程互斥使用缓冲区
empty[0,1,……n2]={m,m,……m};
full[0,1,…..n2]={0,0,……0};
int I;
Cobegin:
Process Ai
Begin:
Loop:
Int I;
For ( I=0; I
Goto Loop;
End;
CoEnd;

6、理发师问题：一个理发店有N张沙发和一张理发椅，没有顾客要理发时，理发师便去睡觉；当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。使用信号量实现这一同步问题。
解答：为解决上述问题，需要设置一个整形变量count用来对理发店中的顾客进行计数，再设置7个信号量：mutex用来实现顾客进程对count变量的互斥访问，其初值为1；sofa是对应于等候室中N张沙发的资源信号量，其初值为N；empty表示是否有空闲的理发椅，其初值为1；full表示理发椅上是否坐有等待理发的顾客，其初值为0；cut用来等待理发的完成，其初值为0；payment用来等待付费，其初值为0；receipt用来等待收费，其初值为0。

Int count =0;
Mutex,sofa,empty,full,cut,payment,receipt: semaphore =1,N,1,0,0,0,0;
CoBegin:
Process Guest:
Begin:
P (mutex);
Ifcount>N) then
{
v(mutex);
exit shop;
}
else
{
count ++;
if ( count >1)then
{
p(sofa);
sit on sofa;
p(empty);
get up from sofa;
v(sofa);
}
else //count=1
{
p(empty);
sit on the baber_chair;
v(full);
p (cut);
pay;
v(payment);
p(receipt);
get up from the baber_chair;
v(empty);
p(mutex)
count--;
v(mutex);
exit shop;
End;
Process Barber:
Begin
Loop:
P(full);
Cut hair;
V(cut);
P(payment);
Accept payment;
V(receipt);
Goto Loop;
CoEnd;

7、一个海底隧道中只有一个车道，规定同一个方向的可以连续过隧道；某方向有列车过隧道时，另一个方向的列车就要等待，现在东岸和西岸都有列车要过隧道，如果把每个过隧道的列车看作一个进程，为保证安全，使用P、V操作实现正确管理。

8、如果系统中有N个进程，
• 运行进程最多几个，最少几个？
• 就绪进程最多几个，最少几个？
• 等待进程最多几个，最少几个？
解答： 运行进程最多1个，最少0个；
就绪进程最多N-1个，最少0个；
等待进程最多N个，最少0个；

12、假设有三个并发进程P，Q，R，其中P负责从输入设备上读入信息并传送给Q，Q将信息加工后传送给R，R则负责将信息打印输出。写出下列条件的并发程序：
（1）进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。
（2）进程P、Q共享一个由m个缓冲区组成的缓冲池，进程Q、R共享另一个由n个缓冲区组成的缓冲池。
参考答案：（1）
第一步：确定进程
3个进程P、Q、R
P进程：
l 从输入设备上读入信息
l 将信息放入缓冲区1
Q进程：
l 从缓冲区1取出信息
l 将信息放入缓冲区2中
R进程：
l 从缓冲区2取出信息
l 将信息打印输出
第二步：确定进程的同步、互斥关系
l 同步：P当缓存区1无数据时，才可以向缓冲区1写入信息
l 同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息
l 同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息
l 同步：R当缓存区2有数据时，才可以从缓冲区2读取信息
第三步：设置信号量
l 缓存区1无数据，empty1，初值1
l 缓存区1有数据，full1，初值0
l 缓存区2无数据，empty2，初值1
l 缓存区2有数据，full2，初值0
第四步：用伪代码描述
begin
empty1,empty2,full1,full2：semaphore;
empty1 :=1;
empty2 :=1;
full1 :=0;
full2 :=0;
cobegin
P ( );
Q ( );
R ( );
coend;
end;

process P ( )
begin
L1: 从输入设备上读入信息;
P（empty1）;
将信息放入缓冲区1；
V（full1）;
goto L1
end;

process Q ( )
begin
L2:P（full1）;
从缓冲区1取出信息;
V（empty1）;
P（empty2）;
将信息放入缓冲区2；
V（full2）;
goto L2
end;

process R ( )
begin
L3:P（full2）
从缓冲区2取出信息;
V（empty2）;
将信息打印输出 ;
goto L3 ;
end;

（2）
第一步：确定进程
3个进程P、Q、R
P进程：
l 从输入设备上读入信息
l 将信息放入缓冲池1中的一个空缓冲区中
Q进程：
l 从缓冲池1中的一个非空缓冲区中取出信息
l 将信息放入缓冲池2中的一个空缓冲区中
R进程：
l 从缓冲池2中的一个非空缓冲区中取出信息
l 将信息打印输出
第二步：确定进程的同步、互斥关系
l 同步：P当缓冲池1中有空的缓冲区时，才可以向缓冲池1写入信息
l 同步：Q当缓冲池1中有非空的缓冲区时，才可以从缓冲池1读取信息
l 同步：Q当缓冲池2中有空的缓冲区时，才可以向缓冲池2写入信息
l 同步：R当缓冲池2中有非空的缓冲区时，才可以从缓冲池2读取信息
第三步：设置信号量
l 缓冲池1中的空缓冲区的数量，empty1，初值m
l 缓冲池1中的非空缓冲区的数量，full1，初值0
l 缓冲池2中的空缓冲区的数量，empty2，初值n
l 缓冲池2中的非空缓冲区的数量，full2，初值0
第四步：用伪代码描述
begin
empty1,empty2,full1,full2：semaphore;
empty1 :=m;
empty2 :=n;
full1 :=0;
full2 :=0;
cobegin
P ( );
Q ( );
R ( );
coend;
end;

process P ( )
begin
L1: 从输入设备上读入信息;
P（empty1）;
将信息放入缓冲池1中的一个空缓冲区中；
V（full1）;
goto L1
end;

process Q ( )
begin
L2:P（full1）;
从缓冲池1中的一个非空缓冲区中取出信息;
V（empty1）;
P（empty2）;
将信息放入缓冲池2中的一个空缓冲区中；
V（full2）;
goto L2
end;

process R ( )
begin
L3:P（full2）;
从缓冲池2中的一个非空缓冲区中取出信息;
V（empty2）;
将信息打印输出 ;
goto L3 ;
end;

13、有四个并发进程：R1，R2W1和W2，它们共享可以存放一个数的缓冲区。进程R1每次从磁盘读入一个数存放到缓冲区中，供进程W1打印输出；进程R2每次从键盘读一个数存放到缓冲区中，供进程W2打印输出。当缓冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。
参考答案：
第一步：确定进程
4个进程R1、R2、W1、W2
R1进程：
l 从磁盘上读入一个数
l 将数存放到缓冲区中
W1进程：
l 将R1进程放进缓冲区中的数取出
l 打印输出
R2进程：
l 从键盘读入一个数
l 将数存放到缓冲区中
W2进程：
l 将R2进程放进缓冲区中的数取出
l 打印输出
第二步：确定进程的同步、互斥关系
l 同步：R1当缓存区无数据时，才可以向缓冲区写入数据
l 同步：R2当缓存区无数据时，才可以向缓冲区写入数据
l 同步：W1当缓存区中是R1写的数据时，才可以将数据从缓冲区中读出
l 同步：W2当缓存区中是R2写的数据时，才可以将数据从缓冲区中读出
第三步：设置信号量
l 缓存区无数据，empty，初值1
l 缓存区中是R1写的数据，full1，初值0
l 缓存区中是R2写的数据，full2，初值0
第四步：用伪代码描述
begin
empty, full1,full2：semaphore
empty :=1;
full1 :=0;
full2 :=0;
cobegin
R1 ( );
R2 ( );
W1 ( );
W2 ( );
coend;
end;

process R1 ( )
begin
L1: 从磁盘上读入一个数；
P（empty）;
将数存放到缓冲区中；
V（full1）;
goto L1
end;

process R2 ( )
begin
L2: 从键盘上读入一个数；
P（empty）;
将数存放到缓冲区中；
V（full2）;
goto L2
end;

process W1 ( )
begin
L3:P（full1）;
将缓冲区中的数取出；
V（empty）;
打印输出;
goto L3
end;

process W2 ( )
begin
L4:P（full2）;
将缓冲区中的数取出；
V（empty）;
打印输出;
goto L4
end;

15、有一个阅览室，共有100个座位。读者进入阅览室时必须在入口处进行登记；离开阅览室时必须进行注销。试用PV操作描述读者进入/离开阅览室的同步与互斥关系。
参考答案：
第一步：确定进程
可以进入阅览室的读者可以有很多，这里设为n，即
n个Reader（读者）进程
Reader进程：
l 登记
l 进入阅览室
l 读书
l 离开阅览室
l 注销
第二步：确定进程的同步、互斥关系
l 同步：当教室内有空座位时，读者才可以登记，并进入阅览室
l 互斥：同时只能有一个读者在入口处进行登记
l 互斥：同时只能有一个读者在出口处进行注销
第三步：设置信号量
l 教室内空座位数量，seat，初值100
l 为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用
l 为出口处进行注销设置互斥信号量Sout，初值 1，表示当前可用
第四步：用伪代码描述
begin
Sin, Sout, seat：semaphore;
seat :=100;
Sin := 1;
Sout := 1;
cobegin
process Reader-i ( i = 1,2,…,n );
begin
P(seat);
P(Sin);
登记;
VSin);
进入阅览室;
读书;
离开阅览室;
P(Sout);
注销;
V(Sout);
V（seat）;
end
coend;
end;

17、设一个机票订购系统有n个售票处，每个售票处通过网络终端访问系统的公共数据区，假定公共数据区中的一些单元Aj（j＝1,2,……）分别存放各次航班的余票数，售票时，若某次航班还有余票，则售给乘客，否则，拒绝售票。请用信号量的PV操作实现各售票进程的并发执行。
解: 设Pi（i=1,2,…,n）表示各售票处的售票处理进程，公共数据区是多个售票进程共享的临界资源，为其设置互斥信号量S，初值为1，表示资源可用。算法描述如下：
begin
S：semaphore;
S :=1;
cobegin
process Pi(i=1,2,…,n)
begin
Ri：integer // 表示各进程执行时所用的工作单元
P（S）
Ri := Aj;
if Ri ≥1 then begin Ri := Ri －1；
Aj := Ri；
V（S
输出一张票
end
else begin V（S）；
输出“票已售完”信息；
end；
end；
coend；
end；
注意：算法中“else”部分的V操作不能少，否则当进程在临界区中判别条件Ri ≥1不成立时无法退出临界区，当然也就不能唤醒等待进入临界区的其它进程，这就违反了同步机制应遵循的“空闲让进”和“有限等待”两个原则。

18、有三个进程PA、PB、PC合作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的记录复制到缓冲区2，每执行一次复制一个记录；PC打印缓冲区2中的记录，每执行一次打印一个记录。每个缓冲区只能存放一个记录。请用信号量机制实现文件的正确打印。
解：本题中，进程PA、PB、PC之间的合作关系如图2－3所示：

图2－3 文件打印流程图
当缓冲区1为空时，PA可将记录读入其中，否则，PA需等待；当缓冲区1有记录而缓冲区2为空时，PB可进行复制工作，否则PB需等待；当缓冲区2有记录时，PC可打印记录，否则PC需等待。为此，设置4个信号量empty1、empty2、full1、full2，其中empty1、empty2分别表示缓冲区1和缓冲区2是否为空，初值均为“1”；full1、full2分别表示缓冲区1和缓冲区2中是否有记录，其初值均为“0”。算法描述如下：
begin
empty1,empty2,full1,full2：semaphore;
empty1 :=1;
empty2 :=1;
full1 :=0;
full2 :=0;
cobegin
PA ( );
PB ( );
PC ( );
coend;
end;
process PA ( )
begin
L1: 从磁盘读一个记录;
P（empty1）;
将记录存入缓冲区1；
V（full1）;
goto L1
end;

process PB ( )
begin
L2: P（full1）;
从缓冲区1取一个记录；
V（empty1）
P（empty2）;
将记录存入缓冲区2；
V（full2）;
goto L2
end;
process PC ( )
begin
L3: P（full2）
从缓冲区2取出一个记录;
V（empty2）;
打印输出记录；
goto L3
end;