信号量的PV操作(例题]
![信号量的PV操作(例题]](https://img.wendangku.net/img70/1d6gm4riz80rgwne6ef3rpw0mbmhxwdl-01.webp)
![信号量的PV操作(例题]](https://img.wendangku.net/img70/1d6gm4riz80rgwne6ef3rpw0mbmhxwdl-d2.webp)
？？？信号量的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进程：
将苹果放入盘中
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两种产品，但要求：
①每次只能存入一种产品（A或B）；
②A产品数量－B产品数量 ③B产品数量－A产品数量 其中M、N是正整数，使用P、V操作描述产品A与产品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 (empty[I]); P(Mutex); 将消息放入缓冲区； v(Mutex); for( I=0; I v(full[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个售票处，每个售票处通过网络终端访问系统的公共数据区，假定公共数据区中的一些单元A j（j＝1,2,……）分别存放各次航班的余票数，售票时，若某次航班还有余票，则售给乘客，否则，拒绝售票。请用信号量的PV操作实现各售票进程的并发执行。 解: 设P i（i=1,2,…,n）表示各售票处的售票处理进程，公共数据区是多个售票进程共享的临界资源，为其设置互斥信号量S，初值为1，表示资源可用。算法描述如下： begin S：semaphore; S :=1; cobegin process P i(i=1,2,…,n) begin R i：integer // 表示各进程执行时所用的工作单元 P（S） R i := A j; if R i ≥1 then begin R i := R i －1； A j:= R i； V（S）； 输出一张票 end else begin V（S）； 输出“票已售完”信息； end； end； coend； end； 注意：算法中“else”部分的V操作不能少，否则当进程在临界区中判别条件R i ≥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; 1.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用PV操作实现管理。 解：定义一个信号量S，初值为20 parbegin process pl(l=1,2,……) begin wait(S); 进入售票厅； 购票； 退出； signal(S) end 2.桌上有一空盘，允许存放一个水果，爸爸可向盘内放苹果，妈妈可向盘内放桔子，儿子专等吃盘内的桔子，女儿专等吃盘中的苹果，请用P、V 操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。 int S=1;int Sa=0;int Sb=0; main() {cobegin father(); mather(); son(); daughter(); coend} father() mather() {while(1) { while(1) {p(S); {p(S) ; 将一个苹果放入盘中将一个桔子放入盘中 V(Sa);} V(Sb);} } } son() daughter() { while(1) { while(1) {p(Sb); { p(Sa); 从盘中取出桔子从盘中取出苹果 V(S);吃桔子；} V(S);吃苹果；} } 3.生产围棋的工人不小心把相等数量的黑子和白子混装在一个盒子里，现在要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程PA和PB组成，系统功能如下： （1）PA专拣黑子，PB专拣白子； （2）每个进程每次只拣一个子，当一个进程拣子时，不允许另一个进程去拣子； （3）当一个进程拣一个子（黑或白）后，必须让另一个进程去拣一个子（白或黑） 请回答：①这两个并发进程之间的关系是同步还是互斥 ②写出PV操作管理时应定义的信号量及其初值。 ③根据定义的信号量，写出用PV操作管理两个并发进程的程序 答：①两个进程之间是同步关系 ②定义两个信号量S1和S2，初值为1和0 ③process PA process PA begin begin repeat repeat wait(S1) wait(S2) 拣黑子拣白子 signal(S2) signal(S1) until false until false end end 4.有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假若阅览室共有100个座位。试用信号量和PV操作来实现用户进程的同步算法。 解：设置如下3个信号量 seat：表示阅览室中空座位数，其初值为100. （一）图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序有多少个进程（答：一个程序；为每个读者设一个进程） （1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; （二）有一座东西方向的独木桥；用P,V操作实现：（1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。 （3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数) 从东向西： P (MD) IF (CD=0) {P (MUTEX) } CD=CD+1 V (MD) 过桥 P (MD) CD=CD-1 IF (CD=0) {V (MUTEX) } V (MD) 从西向东： P (MX) IF (CX=0) {P (MUTEX) } CX=CX+1 V (MX) 过桥 P (MX) CX=CX-1 IF (CX=0) {V (MUTEX) } V (MX) (3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。 1、进程P0和P1的共享变量定义及其初值为： boolean falg[2]; int turn=0; falg[0]=FALSE; falg[1]=FALSE; 若进程P0和P1访问临界资源的类C伪代码实现如下： 则并发执行进程P0和P1时产生的情形是【全国联考2010】 A. 不能保证进程互斥进入临界区、会出现“饥饿”现象 B. 不能保证进程互斥进入临界区、不会出现“饥饿”现象 C. 能保证进程互斥进入临界区、会出现“饥饿”现象 D. 能保证进程互斥进入临界区、不会出现“饥饿”现象 分析进程的执行过程：一开始，没有进程处于临界区中，现在进程P0开始执行，通过设置其数组元素和将turn置1来标识它希望进入临界区，由于进程P1并不想进入临界区，所以P0跳出while循环，进入临界区。如果进程P1现在开始执行，进程P1将阻塞在while循环直到flag[0]变为false，而该事件只有进程P0退出临界区时才会发生。 现在考虑两个进程几乎同时执行到while循环的情况，它们分别在turn中存入1和0，但只有后被保存进去的进程号才有效，前一个被重写而丢失。假设进程P1是后存入的，则turn为0。进程P0将循环0次而进入临界区，而进程P1则将不停地循环且不能进入临界区，直到进程退出临界区为止。 因此，该算法实现了临界区互斥。 “饥饿”出现的时机：使用忙等待实现互斥，当一个进程离开临界区时，如果有多个进程等待进入临界区，系统会随机选择一个进程执行，因为这种随机性，会导致有些进程长期得不到执行，因而导致“饥饿”。 本题中，如果P1已经等在while上的时候，P0至多执行一次临界区，否则下次执行的时候，即便它在P1测试条件前出了临界区并重新设定了flag，但由于它必须要设定turn=1（此时P1不会再设置turn了），因此这样P0必然卡在while上，从而换到P1执行。所以不会出现“饥饿”现象。 2、在一间酒吧里有三个音乐爱好者队列，第一个音乐爱好者只有随身听，第二个只有音乐磁带，第三个只有电池，而要听音乐就必须有随身听，音乐磁 PV操作的例题 一、线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行线程。进程的多个线程都在进程的地址空间内活动。 资源是分给进程的，而不是分给线程的，线程需要资源时，系统从进程的资源配额中扣除并分配给它。处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。线程在执行过程中，需要同步。 二、在计算机操作系统中，PV操作是进程管理中的难点。 首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。 什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。 一般来说，信号量S>=0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。 利用信号量和PV操作实现进程互斥的一般模型是： 进程P1 进程P2 ……进程Pn ……………… P（S）；P（S）；P（S）； 临界区；临界区；临界区； V（S）；V（S）；V（S）； …………………… 其中信号量S用于互斥，初值为1。 使用PV操作实现进程互斥时应该注意的是： （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。 利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。 使用PV操作实现进程同步时应该注意的是： 用P，V操作实现下述问题的解。 一、桌上有一个盘子，可以放一个水果；父亲总是放苹果到盘子中；母亲总是放香蕉到盘子中。一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。父母只放水果不吃，儿女只吃水果不放。实现父亲，母亲，儿子，女儿的进程同步。 二、在公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆，正常行车，到站停车。 售票员的活动：上下乘客，关车门，售票，开车门，上下乘客。 在汽车不停的到站，停站，行驶过程中，这两个活动有什么同步关系？用信号量和P，V操作实现它们的同步。 三、某寺庙，有小，老和尚若干，有一个水缸，有小和尚提水入缸供老和尚饮用。水缸可以放10桶水，水从一个井里面提。水井狭窄，每次只能容纳一个桶取水。水桶总数为3个。每次入、取缸水只能是1桶，且不可以同时进行。试给出取水，入水的算法描述。 四、一个快餐厅有4类职员：（1）领班：接受顾客点菜，出菜单；（2）厨师：根据菜单，准备顾客的饭菜；（3）打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。 五、假设有一个作业由四个进程组成，这四个进程在运行时必须按如图所示的次序依次执行，试用P,V原语表达四个进程的同步关系： 六、观察者和报告者是两个并发执行的进程，观察者不断观察并对通过的卡车计数，报告者定时的将观察者的计数值打印，打印完毕，将计数值清零。 七、假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。 在计算机操作系统中，PV操作是进程管理中的难点。 首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下： P（S）：①将信号量S的值减1，即S=S-1； ②如果S30，则该进程继续执行；否则该进程置为等待状态，排入等待队列。 V（S）：①将信号量S的值加1，即S=S+1； ②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。 PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。 什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。 一般来说，信号量S30时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S￡0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。 利用信号量和PV操作实现进程互斥的一般模型是： 进程P1 进程P2 ……进程Pn ……………… P（S）； P（S）； P（S）； 临界区；临界区；临界区； V（S）； V（S）； V（S）； …………………… 其中信号量S用于互斥，初值为1。 使用PV操作实现进程互斥时应该注意的是： （1）每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。 （2）P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为1。 利用信号量和PV操作实现进程同步 PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。 使用PV操作实现进程同步时应该注意的是： （1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。 ？？？信号量的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进程： 将苹果放入盘中 计算机操作系统P V操 作例题 WTD standardization office【WTD 5AB- WTDK 08- WTD 2C】 问题1一个司机与售票员的例子在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()有三个进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每次读出一个记录并把它存放在缓冲区中：M在缓冲区加工读入的记录；P把加工后的记录打印输出。输入的记录经加工输出后，缓冲区中又可存放下一个记录。请用P、V操作为同步机构写出他们并发执行时能正确工作的程序。 答：三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量： S1：表示是否可把读人的记录放到缓冲区，初始值为1. S2：表示是否可对缓冲区中的记录加工，初始值为0. S3：表示记录是否加工好，可以输出，初始值也为0. 三个进程可如下设计： Begin S1，S2，S3：semaphore； S1：＝l；S2：＝S3：＝0； cobegin process R begin L1：读记录； P（S1）； 记录存入缓冲区； V（S2）； goto L1； end； process M begin L2：P（S2）； 加工记录； V（S3）； goto L2； end； process P begin L3：P（S3）； 输出加工后的记录； V（S1）； goto L3； end； coend； end. 6.现有4个进程R1，R2，W1，W2，它们共享可以存放一个数的缓冲器B.进程R1每次把从键盘上投入的一个数存放到缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数放到缓冲器B中，供进程W2打印输出。当一个进程把数据存放到缓冲器后，在该数还没有被打印输出之前不准任何进程再向缓冲器中存数。在缓冲器 问题1 一个司机与售票员的例子 在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()//司机进程 { while (1)//不停地循环 { P(S1);//请求启动汽车 启动汽车; 正常行车； 到站停车； V(S2); //释放开门变量，相当于通知售票员可以开门 } } busman()//售票员进程 { while(1) { 关车门; V(S1)；//释放开车变量，相当于通知司机可以开车 售票 P(S2)；//请求开门 开车门； 上下乘客； } } 注意：busman() driver() 两个不停循环的函数 问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; 问题3 有一座东西方向的独木桥；用P,V操作实现： （1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数) 从东向西： P (MD) IF (CD=0) 1. 推广例子中的消息缓冲问题。 消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？ Send： SB=k; //信号量，标记当前空余缓冲区资源。 i = 0; //标记存放消息的缓冲区位置 while (true) { P(SB); 往Buffer [i]放消息; V(SM); i = (i+1) % k; }; Receive： j = 0; //标记取产品的缓存区位置 SM=0；//信号量，标记初始没有消息 ReadCount=0；//读进程计数器 Mutex =1；//读进程互斥信号量 SW=0; //信号量，读进程在此信号量等待 while (true) { P(SM); 从Buffer[j]取消息; ReadCount++ If（ReadCount rc=0, //正在读者计数器 wc, //写计数器 rw, //读等计数器 R //等待读信号量 W //等待写信号量 读者： while (true) { P(mutex); if (wc >0){ rw++ P (R); } rc++; If（rw>0&&wc=0）{ V(R) rw-- } V(mutex); 读 P(mutex); rc --; if (rc==0){ If（wc>0）V(w) } V(mutex); }; 写者： while (true) { P(mutex); wc ++; if((wc >1)||(rc>0)){ P(W) } V(mutex); 写 P(mutex); Wc --; if（wc>0） V(W); Else if(rw>0) V(R) 一、用P、V操作描述前趋关系。P1、P2、P3、P4、P5、 P6为一组合作进程，其前趋图如图2．3所示，试用P、V 操作描述这6个进程的同步。p23 图2．3说明任务启动后P1先执行，当它结束后P2、P3可以开始执行，P2完成后P4、P5可以开始执行，仅当P3、P4、P5都执行完后，P6才能开始执行。为了确保这一执行顺序，设置5个同步信号量n、摄、f3、f4、g分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。这6个进程的同步描述如下： 图2．3 描述进程执行先后次序的前趋图 int f1=0; /*表示进程P1是否执行完成*／int f2=0; /*表示进程P2是否执行完成*／int f3=0; /*表示进程P3是否执行完成*／int f4=0; /*表示进程P4是否执行完成*／int f5=0; /*表示进程P5是否执行完成*／main() { cobegin P1( ); P2( ); P3( ); P4( ); P5( ); P6( ); coend } P1 ( ) { ┇ v(f1); v(f1)： } P2 ( ) { p(f1); ┇ v(f2); v(f2); ) P3 ( ) { p(f1); ┇ v(f3); } P4( ) { p(f2); ┇ v(f4); } P5 ( ) { p(f2); ┇ v(f5); } P6( ) { p(f3); p(f4); p(f5); ┇ } 二、生产者-消费者问题p25 生产者-消费者问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。生产者-消费者问题是许多相互合作进程的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者;在输出时，计算进程是生产者，打印进程是消费者。因此，该问题具有很大实用价值。 我们把一个长度为n的有界缓冲区(n>0)与一群生产者进程P１、P２、…、Pm和一群消费者进程C１、C２、…、Ck 联系起来，如图2．4所示。假定这些生产者和消费者是互相等效的。只要缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲区中取走物品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。 图2．4 生产者-消费者问题 为解决这一类生产者-消费者问题，应该设置两个同步信号量，一个说明空缓冲单元的 P就是请求资源，V就是释放资源。 问题1 一个司机与售票员的例子 在公共汽车上，为保证乘客的安全，司机和售票员应协调工作： 停车后才能开门，关车门后才能行车。用PV操作来实现他们之间的协调。 S1：是否允许司机启动汽车的变量 S2：是否允许售票员开门的变量 driver()//司机进程 { while (1)//不停地循环 { P(S1);//请求启动汽车 启动汽车; 正常行车； 到站停车； V(S2); //释放开门变量，相当于通知售票员可以开门 } } busman()//售票员进程 { while(1) { 关车门; V(S1)；//释放开车变量，相当于通知司机可以开车 售票 P(S2)；//请求开门 开车门； 上下乘客； } } 注意：busman() driver() 两个不停循环的函数 问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程） （1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2）当图书馆中没有座位时，后到的读者不等待，立即回家。 解（1 ) 设信号量：S=100; MUTEX=1 P(S) P(MUTEX) 登记 V(MUTEX) 阅读 P(MUTEX) 注销 V(MUTEX) V(S) 解(2) 设整型变量COUNT=100; 信号量：MUTEX=1; P(MUTEX); IF (COUNT==0) { V(MUTEX); RETURN; } COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX); RETURN; 问题3 有一座东西方向的独木桥；用P,V操作实现： （1）每次只允许一个人过桥； （2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。 （3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。 （1）解 设信号量MUTEX=1 P (MUTEX) 过桥 V (MUTEX) (2)解 设信号量：MUTEX=1 (东西方互斥) MD=1 (东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥) 经典P、V操作问题详解 lionxcat@https://www.wendangku.net/doc/7a1011189.html, 一、基本概念 1. 信号量 struct semaphore { int value; // 仅且必须附初值一次，初值非负 PCBtype* wait_queue; // 在此信号量上阻塞的进程队列 } S; // 信号量实例为S 2. P、V操作 P(S){ S := S-1; if (S<0) 调用进程自己阻塞自己，等待在S的等待队列末尾; } V(S){ S := S+1; if (S≤0) 从S等待队列头释放一进程就绪在就绪队列尾; 调用进程继续执行; } 3. 使用方法 (i). P、V操作成队出现，处理互斥时出现在同一进程中；处理同步时出现在不同进程中。(ii). 同步P先于互斥P调用，V的顺序无关。 4. 另类P、V操作导致的问题(或信号量的栈实现方法或漏斗法) [习题P174-23] 某系统如此定义P、V操作： P(S): S = S-1; 若S＜0，本进程进入S信号量等待队列的末尾；否则，继续执行。 V(S): S＝S+1; 若S≤0，释放等待队列中末尾的进程，否则继续运行。 (1)上面定义的P、V操作是否合理？有什么问题？ (2)现有四个进程P1、P2、P3、P4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面定义的P、V操作正确解决P1、P2、P3、P4对该互斥资源的使用问题。 答： (1)不合理：先进后出；可能“无限等待”，即等待队列头的进程得不到释放。 (2)思路：令每个信号量上的等待队列中始终只有一个进程。解决方案如下：(n个进程) n个进程至多有n-1个等待。设置n-1个信号量，每个进程阻塞在不同的信号量上，使每个等待队列至多有一个进程等待。用循环模拟队列。 例1 在某展示厅设置一个自动计数系统，以计数器count表示在场的人数，count是动态变化的，若有一个人进入展示厅进程pin对计数器count加1，当有一个人退出展示厅时，进程pout实现计数器减1。由于进、出所以展示厅的人是随机的，用P-V操作实现。（并发进程之间的互斥问题） 解：定义信号量：S——表示是否有进程进入临界区，初值为1.（表示没有进程进入临界区）begin count: Integer; S: semaphore; count:=0; S:=1; cobegin process Pin R1: Integer; begin P (S); R1:=count; R1:=R1+1; count:=R1; V(S); end; Process Pout R2: Integer; begin P (S); R2:=count; R2:=R2-1; count:=R2; V (S); end; count; end; 例2 与生产者和消费过者相似的问题，把―A进程将记录送入缓冲器‖看生产者生产了一件物品且把物品存入缓冲器，把―B进程从缓冲器中取出记录并加工‖看作是消费者从缓冲器取出物品去消费，缓冲器中只能放一个记录（一件物品），用P-V操作实现。（并发进程之间的同步问题） 解：定义两个信号量为：sp和sg。 sp:表示生产者是否右以把物品存入缓冲器。由于缓冲器只能存放一个物品，因此sp的初值为1，即sp:=1。 sg：表示缓冲是否存有物品，它的初值应该为0，即sg：=0，表示缓冲器中还没有物品存在。 生产者和消费者两个进程并发执行时，可按以下的方式实现同步： sp:=1;sg:=0; cobegin PV操作题 1.独木桥问题：若规定同一方向的人可连续过桥，但同时在桥上人 数最多4人，当某方向无人过桥后，另一方向的人才能过桥．请用ＰＶ操作模拟实现． 2.独木桥问题：若规定同一方向的人可连续过桥最多10人，当某方 向连续通过达到10人后，另一方向的人才能过桥．请用ＰＶ操作模拟实现． 3.类似题目：车辆过单行隧道，火车过单行轨道 4．有一阅览室只能容纳100人(每人一个座位)，读者进入时必须先在一张登记表上登记一个座位，离开时要销掉登记内容。请用PV机制描述读者进程的同步关系。 5．超市购物过程：共有100个购物篮，每人进入取一个篮子购物，出去结帐并归还篮子。出入口共用一个通道。 6．地下停车场车位管理。（共100个车位） 7．某银行最多只允许容纳N个储户办理业务，如果此时银行只有一个柜员，将此柜员和储户的行为看成两个不同进程，请用PV操作模拟上述过程。 其中储户取号等待叫号，若叫到则到柜员处办理业务，结束自行离开；柜员按顺序叫号并为储户办理业务，若N个号已取完需结束当前业务后才能让后来者取号 8. 某银行最多只允许容纳N个储户办理业务，如果此时银行有M个柜员，将此柜员和储户的行为看成两个不同进程，请用PV操作模拟上述过程。 其中储户取号等待叫号，若叫到则到柜员处办理业务，结束自行离开；柜员按顺序叫号并为储户办理业务，若N个号已取完需结束当前业务后才能让后来者取号，但是柜员间叫号是互斥的 9.有个师傅和三个徒弟，徒弟不断组装产品，做一个产品需要A,B,C 三种零件(分别被三个徒弟掌握)，师傅不断提供上述三种零件，但每次只能将其中两种放到桌上，具有另一种零件的徒弟则组装产品，且做完后向师傅发信号，然后师傅再拿出两种零件放到桌上，如此反复，请用PV操作模拟上述活动。 10.书本上司机和售票员问题 后续内容继续更新中…… 1、某寺庙有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一井水。水井狭窄，每次只能容一个桶取水。水桶总数为3个。每次入、出水缸仅一桶，且不可同时进行。试给出有关取水、入水的算法描述。 Var mutex1, mutex2, empty, full, count: semaphore; mutex1:=1; mutex2:=1; empty:=10; full:=0; count:=3; process 小和尚: begin repeat wait(empty); wait(count); wait(mutex1); 从井中取水； signal(mutex1); wait(mutex2); 送水入水缸； signal(mutex2); signal(count); signal(full); until false; end process 老和尚: begin repeat wait(full); wait(count); wait(mutex2); 从缸中取水； signal(mutex2); signal(empty); signal(count); until false; end 2、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。 3：有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名，读者离开时，要删掉登记的信息，阅览室共有100个座位，试问： （1）为描写读者动作，应编写几个程序，应设置几个进程？进程与程序间关系如何？ （2）试问P、V操作写出这些进程间的同步算法。 解法1： 进程同步练习题 1. 在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司机 售票员 图司机和售票员工作流程图 2. 桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。 3. a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：（1）当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab 段外等待； （2）当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a 点和b点同时驶入； （3）当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用信号量为工具，对ab段实现正确管理以保证行驶安全。 4．将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P、V操作正确实现“读者”与“写者”的同步。（第二类读者写者问题，信号量解决方法） 5．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。 设一民航售票系统有n个售票处。每个售票处通过终端访问系统中的公用数据区，假定公用数据区中分别用R1、R2、R3、…Rn表示×月×日×次航班的现存票数。设P1、P2、P3、Pn表示各售票处的处理进程，试用信号量实现进程间的互斥关系 Var s: semaphore :=1; begin parbegin process Pi: begin repeat Wait (s); 按旅客定票要求找到Rk if Rk>=1 then begin Rk=Rk-1; Signal (s); 输出一张票； end; else begin Signal (s); 输出“票已售完”； end; until false; end parend end 生产围棋的工人不小心把相等数量的黑子和白子混装在一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下： （1）进程A专门拣黑子，进程B专门拣白子； （2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子； s:semaphore:=1; parbegin process A：begin L1: Wait(s); 拣黑子； Signal(s); goto L1; end; process B：begin L2:Wait(s); 拣白子； Signal(s); goto L2; end; parend; 某车站售票厅共有20 个售票窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一 个进程。 s:semaphore=20; parbegin process Pi(i=1,2,……) begin Wait(s); 进入售票厅； 购票； 退出； Signal(s); end; parend 有座东西方向架设、可双向通行的单车道简易桥，最大负荷为4 辆汽车。请定义合适的信号量，正确使用wait/signal 操作，实现双向车辆的过桥过程。 信号量应该有4 个： S ,初值为1,代表桥的互斥使用的信号量；Scounteast,初值为1,代表由东向西行驶的桥上的车辆计数器的互斥使用； Scountwest,初值为1,代表由西向东行驶的桥上的车辆计数器的互斥使用； Scount4 ,初值为4,代表桥上车辆的计数信号量。 var S,Scounteast,Scounwest,Scount4:semaphore； S: = 1；Scounteast＝1； Scountwest: = 1；Scount4: = 4； Counteast，Countwest：integer； Counteast: = 0；Countwest: = 0； Cobegin , process east( i ) begin P( Scounteast ) ; if Counteast = 0 then P( S ) ; Counteast : = Counteast + l ; V( Scounteast ) ; P( Scount4 ) ; 上桥：过桥：下桥； V ( Scount4 ) ; P ( Scounteast ) ; Counteast: = Counteast - 1 ; if Counteast = 0 then V( S ) ; V ( Scounteast ) ; end ; process west( i ) begin P( Scountwest ) ; if Countwest = 0 then P( S ) ; Countwest: = Countwest + 1 ; V( Scountwest ) ; 进程同步练习题 1.在公共汽车上，司机和售票员的工作流程如图所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。 司机 售票员 图司机和售票员工作流程图 ①约束：怎么密切配合协调工作才能保证安全呢？ a)关车门之后再启动车辆；利用前驱图解释 b)到站停车之后再开车门； ②根据约束定义信号量； 关车门和启动车辆需要一个信号量进行同步S1；到站停车和开车门之间需要一个信号量进行同步S2； ③建立几个进程呢？ a)为司机建立一个进程Driver； b)为售票员建立一个进程Conductor； Driver： Repeat 启动车辆； 正常行驶； 到站停车； Until false; Conductor： Repeat 关车门； 售票； 开车门； Until false; ④加入同步关系： Driver： Repeat Wait (s1); 启动车辆； 正常行驶； 到站停车； Signal(s2) Until false; Conductor： Repeat 关车门； Signal(s1); 售票； Wait(s2) 开车门； Until false; main() { Driver(); Conductor (); } 2.桌子上有一只盘子，盘子中只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。 分析： ①约束： a)爸爸和妈妈竞争盘子，往盘子放水果，爸爸在放时，妈妈等待，或者相反； b)爸爸和女儿要同步，即爸爸放完苹果之后通知女儿来吃；同时女儿吃完之后要通知盘 子可用； c)妈妈和儿子要同步，即妈妈放完橘子之后通知儿子来吃；同时儿子吃完之后要通知盘 子可用； ②经上述分析可知： 需要3个信号量：S1表示临界资源盘子，初值1；爸爸和女儿需要一个信号量进行同步S2=0 妈妈和儿子需要一个信号量进行同步S3=0; ③建立进程？ 爸爸：妈妈：女儿：儿子：p_v操作例题
PV操作题解
pv操作的一些习题
PV操作的例题
pv操作练习题
经典PV操作讲解和练习题
信号量地PV操作(例题)
计算机操作系统PV操作例题
计算机操作系统PV操作例题
操作系统PV操作经典例题与答案
操作系统PV操作习题
P,V操作经典例题
经典PV操作问题
pv操作典型例题
PV操作题
PV操作题
进程同步典型例题(操作系统)
pv操作习题
进程同步典型例题(操作系统)