信号量的PV操作(例题)

1、？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作

2、，S值减1，表示请求分配一个资源，若S0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。1、 设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆； 正常行车； 到站停车；售票员的活动： 关车门； 售票； 开车门；

3、 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S0；C0；司机： L1： 正常行车 售票员： L2： 售票到站停车 P（S）V（S） 开车门P（C） 关车门启动开车 V（C）GO TO L1 GO TO L22、请用PV操作实现他们之间的同步关系： （1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。（2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。参考答案：第一步：确定进程4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter

4、（女儿）Father进程：l 将苹果放入盘中Mother进程：l 将桔子放入盘中Son进程：l 从盘中取出桔子l 吃桔子Daughter进程：l 从盘中取出苹果l 吃苹果第二步：确定进程的同步、互斥关系l 同步：Father当盘中无水果时，才可以将苹果放入盘中l 同步：Mother当盘中无水果时，才可以将桔子放入盘中l 同步：Son当盘中有桔子时，才可以从盘中取出桔子l 同步：Daughter当盘中有苹果时，才可以从盘中取出苹果第三步：设置信号量l 盘中无水果，Sp，初值1l 盘中有桔子，So，初值0l 盘中有苹果，Sa，初值0第四步：用伪代码描述begin Sp,So,Sa：semaphor

5、e; Sp :=1; So :=0; Sa :=0;cobeginFather ( );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 (

6、 ) 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

7、l 盘中有水果（桔子或苹果），full，初值0第四步：用伪代码描述begin empty, full：semaphore; empty:=1; full :=0;cobeginFather ( );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

8、）; 从盘中取出水果; V（empty）; 吃水果; goto L3； end;3. 某工厂有一个可以存放设备的仓库，总共可以存放10台设备。生产的每一台设备都必须入库，销售部门可从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一台运输工具，每次只能运输一台设备。请设计一个能协调工作的自动调度管理系统。参考答案：第一步：确定进程可以为入库（Pin）和出库（Pout）各设置一个进程Pin进程：l 生产了一台设备l 使用运输工具入库Pout进程：l 使用运输工具出库l 提出设备供应客户第二步：确定进程的同步、互斥关系l 同步：当仓库中有空余位置存放设备时，设备才可以入库l 同步：

9、当仓库中有存放的设备时，设备才可以出库l 互斥：运输工具是临界资源，要互斥访问第三步：设置信号量l 仓库中有空余位置数量，empty，初值10l 仓库中有存放的设备数量，full，初值 0l 为运输工具设置互斥信号量S，初值 1，表示当前可用第四步：用伪代码描述begin empty, full, S：semaphore; empty := 10;full := 0;S := 1;cobeginPin ();Pout ();coend;end;process Pin ( ) begin L1: 生产了一台设备 ;P（empty）; P (S);使用运输工具入库;V （S）; V（full）;

10、goto L1; end;process Pout ( ) beginL2: P（full）;P (S);使用运输工具出库;V （S）;V（empty）;提出设备供应客户; goto L2; end;4、写者优先的“读者写者”问题：1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）wmutex:semaphore=1 /读者与写者之间、写者与写者之间互斥使用共享数据S：semaphore=1 /当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成S2：semaphor1 /阻塞第二个以后的等待读者readcount,writecou

11、nt: semaphore = 0,0; /当前读者数量、写者数量mutex1 :semaphore = 1 /多个读者互斥使用readcountmutex2 :semaphore = 1 /多个写者互斥使用writecountCobegin: 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 r

12、eadcount=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

13、;5、有一个仓库，可以存放A、B两种产品，但要求： 每次只能存入一种产品（A或B）； A产品数量B产品数量<M； B产品数量A产品数量<N；其中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)

14、; V(Sa); Goto Loop; End;CoEnd; 5、进程A1、A2、An1通过m个缓冲区向进程B1、B2Bn2不断地发送消息。发送和接收工作遵循如下规则：（1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；（2） 对每一个消息，B1，B2，Bn都必须接收一次，读入各自的数据区内；（3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。解答：本题是生产者消费者问题的一个变形，一组生产者A1，A2，.An1和一组消费者B1，B2，Bn2公用m个缓冲区，每个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者

15、需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。 Mutex,emptyn2,fulln2:semaphore; Mutex=1; /多进程互斥使用缓冲区empty0,1,n2=m,m,m;full0,1,.n2=0,0,0;int I;Cobegin: Process Ai Begin: Loop:Int I;For ( I=0; I<n2; I+) P (emptyI);P(Mutex);将消息放入缓冲区；v(Mutex);for( I=0; I <n2; I+) v(fullI);Goto Loop;End;Process BiBegin:Lo

16、op: P (fullI); P(Mutex); 从消息缓冲区取出消息； v(Mutex); v(emptyI);Goto Loop;End; CoEnd;6、理发师问题：一个理发店有N张沙发和一张理发椅，没有顾客要理发时，理发师便去睡觉；当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。使用信号量实现这一同步问题。解答：为解决上述问题，需要设置一个整形变量count用来对理发店中的顾客进行

17、计数，再设置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 (mut

18、ex); 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)

19、; 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个进程， 运行进程最多几个，最少几个？ 就绪进程最多几个，最少几个？ 等待进程最多几个，最少几个？解答

20、： 运行进程最多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、RP进程：l 从输入设备上读入信息l 将信息放入缓冲区1Q进程：l 从缓冲区1取出信息l 将信息放入缓冲区2中R进程：l 从缓冲区2取出信息l 将信息

21、打印输出第二步：确定进程的同步、互斥关系l 同步：P当缓存区1无数据时，才可以向缓冲区1写入信息l 同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息l 同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息l 同步：R当缓存区2有数据时，才可以从缓冲区2读取信息第三步：设置信号量l 缓存区1无数据，empty1，初值1l 缓存区1有数据，full1，初值0l 缓存区2无数据，empty2，初值1l 缓存区2有数据，full2，初值0第四步：用伪代码描述begin empty1,empty2,full1,full2：semaphore;empty1 :=1; empty2 :=1; full1

22、 :=0; full2 :=0;cobeginP ( );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 ; e

23、nd;（2）第一步：确定进程3个进程P、Q、RP进程：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中

24、的空缓冲区的数量，empty1，初值ml 缓冲池1中的非空缓冲区的数量，full1，初值0l 缓冲池2中的空缓冲区的数量，empty2，初值nl 缓冲池2中的非空缓冲区的数量，full2，初值0第四步：用伪代码描述begin empty1,empty2,full1,full2：semaphore;empty1 :=m; empty2 :=n; full1 :=0; full2 :=0;cobeginP ( );Q ( ); R ( );coend;end;process P ( )begin L1: 从输入设备上读入信息; P（empty1）; 将信息放入缓冲池1中的一个空缓冲区中； V（fu

25、ll1）; 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每次从键盘读

26、一个数存放到缓冲区中，供进程W2打印输出。当缓冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。参考答案：第一步：确定进程4个进程R1、R2、W1、W2R1进程：l 从磁盘上读入一个数l 将数存放到缓冲区中W1进程：l 将R1进程放进缓冲区中的数取出l 打印输出R2进程：l 从键盘读入一个数l 将数存放到缓冲区中W2进程：l 将R2进程放进缓冲区中的数取出l 打印输出第二步：确定进程的同步、互斥关系l 同步：R1当缓存区无数据时，才可以向缓冲区写入数据l 同步：R2当缓存区无数据时，才可以向缓冲区写入数据l 同步：W1当

27、缓存区中是R1写的数据时，才可以将数据从缓冲区中读出l 同步：W2当缓存区中是R2写的数据时，才可以将数据从缓冲区中读出第三步：设置信号量l 缓存区无数据，empty，初值1l 缓存区中是R1写的数据，full1，初值0l 缓存区中是R2写的数据，full2，初值0第四步：用伪代码描述begin empty, full1,full2：semaphore;empty :=1; full1 :=0; full2 :=0;cobeginR1 ( );R2 ( ); W1 ( );W2 ( );coend;end;process R1 ( )begin L1: 从磁盘上读入一个数； P（empty）;

28、 将数存放到缓冲区中； 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个座位。读者进入阅览室时必须在入口处进行登记；离开阅览室时必须进行注销

29、。试用PV操作描述读者进入/离开阅览室的同步与互斥关系。参考答案：第一步：确定进程可以进入阅览室的读者可以有很多，这里设为n，即n个Reader（读者）进程Reader进程：l 登记l 进入阅览室l 读书l 离开阅览室l 注销第二步：确定进程的同步、互斥关系l 同步：当教室内有空座位时，读者才可以登记，并进入阅览室l 互斥：同时只能有一个读者在入口处进行登记l 互斥：同时只能有一个读者在出口处进行注销第三步：设置信号量l 教室内空座位数量，seat，初值100l 为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用l 为出口处进行注销设置互斥信号量Sout，初值 1，表示当前可用第四步

30、：用伪代码描述begin Sin, Sout, seat：semaphore; seat :=100; Sin := 1; Sout := 1;cobeginprocess Reader-i ( i = 1,2,n );beginP(seat);P(Sin);登记;V(Sin);进入阅览室;读书;离开阅览室;P(Sout);注销;V(Sout);V（seat）;endcoend;end;17、设一个机票订购系统有n个售票处，每个售票处通过网络终端访问系统的公共数据区，假定公共数据区中的一些单元Aj（j1,2,）分别存放各次航班的余票数，售票时，若某次航班还有余票，则售给乘客，否则，拒绝售票。请用信号量的PV操作实现各售票进程的并发执行。解: 设Pi（i=1,2,n）表示各售票处的售票处理进程，公共数据区是多个售票进程共享的临界资源，为其设置互斥信号量S，初值为1，表示资源可用。算法描述如下：begin S：semaphore; S :=1;cobegin process Pi(i=1,2,n) begin Ri：integer / 表示各进程执行