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

？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S0时，其值表示当前可供分配的资源数目；当S0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S0，表示可以为进程分配资源，即允许进程进入其临界区；若S0，表示等待队列为空；若S0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。1、 设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆； 正常行车； 到站停车；售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用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（女儿）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：semaphore; 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 ( ) 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，初值1l 盘中有水果（桔子或苹果），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）; 从盘中取出水果; V（empty）; 吃水果; goto L3； end;3. 某工厂有一个可以存放设备的仓库，总共可以存放10台设备。生产的每一台设备都必须入库，销售部门可从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一台运输工具，每次只能运输一台设备。请设计一个能协调工作的自动调度管理系统。参考答案：第一步：确定进程可以为入库（Pin）和出库（Pout）各设置一个进程Pin进程：l 生产了一台设备l 使用运输工具入库Pout进程：l 使用运输工具出库l 提出设备供应客户第二步：确定进程的同步、互斥关系l 同步：当仓库中有空余位置存放设备时，设备才可以入库l 同步：当仓库中有存放的设备时，设备才可以出库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）; 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,writecount: 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 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产品数量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); 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组缓冲区，每个发送者需要同时写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; In2; I+) P (emptyI);P(Mutex);将消息放入缓冲区；v(Mutex);for( I=0; I 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、RP进程：l 从输入设备上读入信息l 将信息放入缓冲区1Q进程：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，初值1l 缓存区1有数据，full1，初值0l 缓存区2无数据，empty2，初值1l 缓存区2有数据，full2，初值0第四步：用伪代码描述begin empty1,empty2,full1,full2：semaphore;empty1 :=1; empty2 :=1; full1 :=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 ; end;（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中的空缓冲区的数量，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（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、W2R1进程：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，初值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）; 将数存放到缓冲区中； 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，初值100l 为入口处进行登记设置互斥信号量Sin，初值 1，表示当前可用l 为出口处进行注销设置互斥信号量Sout，初值 1，表示当前可用第四步：用伪代码描述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 / 表示各进程执行时所用的工作单元 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之间的合作关系如图23所示：图23 文件打印流程图 当缓冲区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;cobeginPA ( );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;