参：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进程：
●将苹果放入盘中
Mother进程：
●将桔子放入盘中
Son进程：
●从盘中取出桔子
●吃桔子
Daughter进程：
●从盘中取出苹果
●吃苹果
第二步：确定进程的同步、互斥关系
●同步：Father当盘中无水果时，才可以将苹果放入盘中
●同步：Mother当盘中无水果时，才可以将桔子放入盘中
●同步：Son当盘中有桔子时，才可以从盘中取出桔子
●同步：Daughter当盘中有苹果时，才可以从盘中取出苹果
第三步：设置信号量
●盘中无水果，Sp，初值1
●盘中有桔子，So，初值0
●盘中有苹果，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进程：
●将苹果放入盘中
Mother进程：
●将桔子放入盘中
Son进程：
●从盘中取出水果（桔子或苹果）
●吃水果（桔子或苹果）
第二步：确定进程的同步、互斥关系
●同步：Father当盘中无水果时，才可以将苹果放入盘中
●同步：Mother当盘中无水果时，才可以将桔子放入盘中
●同步：Son当盘中有水果（桔子或苹果）时，才可以从盘中取出水果
第三步：设置信号量
●盘中无水果，empty，初值1
●盘中有水果（桔子或苹果），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进程：
●生产了一台设备
●使用运输工具入库
Pout进程：
●使用运输工具出库
●提出设备供应客户
第二步：确定进程的同步、互斥关系
●同步：当仓库中有空余位置存放设备时，设备才可以入库
●同步：当仓库中有存放的设备时，设备才可以出库
●互斥：运输工具是临界资源，要互斥访问
第三步：设置信号量
●仓库中有空余位置数量，empty，初值10
●仓库中有存放的设备数量，full，初值 0
●为运输工具设置互斥信号量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两种产品，但要求：
1每次只能存入一种产品（A或B）；
2A产品数量－B产品数量 Mutex,Sa,Sb: Semaphore; Mutex =1; Sa=M-1; Sb=N-1; CoBegin: Process PA: Begin Loop: P(Sa); P(Mutex); 产品A入库； V(Mutex); V(Sb); Goto Loop; End; Process PB: 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 P(Mutex); 将消息放入缓冲区； v(Mutex); for( I=0; I Goto Loop; End; Process Bi Begin: Loop: P (full[I]); P(Mutex); 从消息缓冲区取出消息； v(Mutex); v(empty[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); If(count>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进程： ●从输入设备上读入信息 ●将信息放入缓冲区1 Q进程： ●从缓冲区1取出信息 ●将信息放入缓冲区2中 R进程： ●从缓冲区2取出信息 ●将信息打印输出 第二步：确定进程的同步、互斥关系 ●同步：P当缓存区1无数据时，才可以向缓冲区1写入信息 ●同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息 ●同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息 ●同步：R当缓存区2有数据时，才可以从缓冲区2读取信息 第三步：设置信号量 ●缓存区1无数据，empty1，初值1 ●缓存区1有数据，full1，初值0 ●缓存区2无数据，empty2，初值1 ●缓存区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进程： ●从输入设备上读入信息 ●将信息放入缓冲池1中的一个空缓冲区中 Q进程： ●从缓冲池1中的一个非空缓冲区中取出信息 ●将信息放入缓冲池2中的一个空缓冲区中 R进程： ●从缓冲池2中的一个非空缓冲区中取出信息 ●将信息打印输出 第二步：确定进程的同步、互斥关系 ●同步：P当缓冲池1中有空的缓冲区时，才可以向缓冲池1写入信息 ●同步：Q当缓冲池1中有非空的缓冲区时，才可以从缓冲池1读取信息 ●同步：Q当缓冲池2中有空的缓冲区时，才可以向缓冲池2写入信息 ●同步：R当缓冲池2中有非空的缓冲区时，才可以从缓冲池2读取信息 第三步：设置信号量 ●缓冲池1中的空缓冲区的数量，empty1，初值m ●缓冲池1中的非空缓冲区的数量，full1，初值0 ●缓冲池2中的空缓冲区的数量，empty2，初值n ●缓冲池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，R2，W1和W2，它们共享可以存放一个数的缓冲区。进程R1每次从磁盘读入一个数存放到缓冲区中，供进程W1打印输出；进程R2每次从键盘读一个数存放到缓冲区中，供进程W2打印输出。当缓冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。 参： 第一步：确定进程 4个进程R1、R2、W1、W2 R1进程： ●从磁盘上读入一个数 ●将数存放到缓冲区中 W1进程： ●将R1进程放进缓冲区中的数取出 ●打印输出 R2进程： ●从键盘读入一个数 ●将数存放到缓冲区中 W2进程： ●将R2进程放进缓冲区中的数取出 ●打印输出 第二步：确定进程的同步、互斥关系 ●同步：R1当缓存区无数据时，才可以向缓冲区写入数据 ●同步：R2当缓存区无数据时，才可以向缓冲区写入数据 ●同步：W1当缓存区中是R1写的数据时，才可以将数据从缓冲区中读出 ●同步：W2当缓存区中是R2写的数据时，才可以将数据从缓冲区中读出 第三步：设置信号量 ●缓存区无数据，empty，初值1 ●缓存区中是R1写的数据，full1，初值0 ●缓存区中是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进程： ●登记 ●进入阅览室 ●读书 ●离开阅览室 ●注销 第二步：确定进程的同步、互斥关系 ●同步：当教室内有空座位时，读者才可以登记，并进入阅览室 ●互斥：同时只能有一个读者在入口处进行登记 ●互斥：同时只能有一个读者在出口处进行注销 第三步：设置信号量 ●教室内空座位数量，seat，初值100 ●为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用 ●为出口处进行注销设置互斥信号量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); 登记; V(Sin); 进入阅览室; 读书; 离开阅览室; 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； j := 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; 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 begin L3: P（full2） 从缓冲区2取出一个记录; V（empty2）; 打印输出记录； goto L3 end; end; process PA ( ) end; process PC ( )
