复习资料3(P、V操作).doc

P、V1、 生产者-消费者问题（采用信号量机制）full是满数目,初值为0,empty是空数目,初值为N。实际上,full + empty = N;mutex用于访问缓冲区时的互斥,初值是1;每个进程中各个P操作的次序是重要的：先检查资源数目,再检查是否互斥否则可能死锁;Var mutex,empty,full:semaphore:=1,n,0;buffer:array0,.n-1;in,out:integer:=0,0;begin parbegin生产者：beginrepeat生产一个产品nextp;P(empty);P(mutex);将产品输入到buffer中bufferin:=nextp;in=(in+1)mod n;V(mutex);V(full);until false;end;消费者：beginrepeatP(full);P(mutex);从buffer中取一个产品nextc=bufferout;out:=(out+1) mod n;V(mutex);V(empty);until false;end; parend;end;三、读者-写着问题（采用信号量机制）第一类：读者优先如果读者来：1）无读者、写者,新读者可以读2）有写者等,但有其它读者正在读,则新读者也可以读3）有写者写,新读者等如果写者来：1）无读者,新写者可以写2）有读者,新写者等待3）有其它写者,新写者等待Wmutex表示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0；Rmutex表示对Rcount的互斥操作,初值是1。Var wmutex,rmutex:semaphore=1,1;buffer:array0,.n-1;Rcount:integer:=0;begin parbegin读者：beginrepeatP(rmutex);if(Rcount=0)P(wmutex);Rcount=Rcount+1;V(rmutex);执行read操作;P(rmutex); Rcount=Rcount-1;if(Rcount=0)V(wmutex);V(rmutex);until false;end;写者：beginrepeatP(wmutex);进行write操作；V(wmutex);until false;end; parend;end;第二类：写者优先Wmutex表示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0；Rmutex表示对Rcount的互斥操作,初值是1。“为了使写者优先,可在原来读者优先的基础上增加一个初值为1的信号量S,使得至少有一个写者准备访问共享对象时,他可以使后续的读者进程等待写完成。初值为0的Wcount用来对写者进行计数,初值为1的互斥信号量mutex用来实现多个写者对Wcount的互斥访问”。Var S,wmutex,rmutexmutex:semaphore=1,1,1,1;buffer:array0,.n-1;Rcount:integer:=0;begin parbegin读者：beginrepeatP(S);P(rmutex);if(Rcount=0)P(wmutex);Rcount=Rcount+1;V(rmutex);V(S);执行read操作;P(rmutex); Rcount=Rcount-1;if(Rcount=0)V(wmutex);V(rmutex);until false;end;写者：beginrepeatP(mutex);if(Wcount=0)P(S);Wcount=Wcount+1;V(mutex);P(wmutex);进行write操作；V(wmutex);P(mutex);Wcount=Wcount-1;if(Wcount=0)V(S);V(mutex);until false;end; parend;end;二、哲学家进餐问题Var sm:semaphore:=4;Philosopher i:while (true) P(sm);P(chopSticki);/ get left chopstickP(chopStick(i + 1) % 5);/ get right chopstick.eat;.V(chopSticki);/return left chopstickV(chopStick(i + 1) % 5);/ return right chopstick V(sm);. think;.老和尚喝水问题: 某寺庙,有小、老和尚若干,由小和尚提水入缸供老和尚饮用。水缸可容10桶水,水取自同一井中。水井窄,每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶,且不可同时进行。试给出有关取水、入水的算法。Mutex1 = 1, mutex2 = 1, empty = 10, full = 0, count =3X: BeginRepeat P(empty); P(count);/申请水桶 P(mutex1); Fetch from well; V(mutex1); P(mutex2); Pour; V(mutex2); V(count);/释放水桶 V(full); Until false;L:BeginRepeat P(full); P(count); P(mutex2); Fetch from crock ; V(mutex2); V(empty); V(count); Until false 吃水果问题：桌上有一只盘子,每次只能放一个水果,爸爸向盘中放苹果或桔子,儿子专等吃盘里的桔子,女儿专等吃盘里的苹果。只要盘子空,则爸爸可向盘中放水果,仅当盘中有自己需要的水果时,儿子或女儿可从中取出,请给出三人之间的同步关系,并用P、V操作实现三人正确活动的程序。分析:此问题实际上是生产者-消费者问题的一个变形生产者:爸爸,消费者：女儿、儿子, 缓冲区：盘子（SIZE=1）解答：设置3个信号量：互斥信号量mutex=1；资源信号量：S1=0表示盘中是否有苹果,实现爸爸与女儿的同步；S2=0表示盘中是否有桔子,实现爸爸与儿子的同步爸爸：P（mutex); 将水果放入盘中； IF 苹果 V（S1） else V（S2）女儿：P（S1）; 从盘中取苹果；V（ mutex ）； 吃苹果儿子：P（S2）；从盘中取桔子；V（ mutex ）；吃桔子22. 隧道问题 1 一座山中有一条隧道,规定每次只允许一辆车过隧道。现在山南、山北都有车要过隧道,如果把每个过隧道者看作一个进程,为保证安全,请用PV操作实现正确管理。Var S:semaphore:=1;Begin parbeginprocess(S-N)i (i=1,2) begin P(S); 过隧道; V(S); end;process(N-S)i (i=1,2) begin P(S); 过隧道; V(S); end; parend;end; 24. 隧道问题 2一座上中有一条隧道,规定每次只允许一辆车过隧道,而且山南、山北交替过隧道。现在山南、山北都有车要过隧道,如果把每个过隧道者看作一个进程,为保证安全,请用PV操作实现正确管理。假设约定南边的先入隧道。Var S1,S2:semaphore:=1,0;Begin parbeginprocess(S-N)i (i=1,2)beginP(S1);过隧道;V(S2); end;process(N-S)i (i=1,2)beginP(S2);过隧道;V(S1); end; parend;end;某系统由数据输入、计算和输出三个进程组成,输入进程把数据送入由M个缓冲块组成的输入缓冲区（每次向一个缓冲块送数据）,计算进程从输入缓冲区取数据计算（每次取一个缓冲块的数据）,并将计算结果送入到由N个缓冲块组成的输出缓冲区（每次向一个缓冲块送数据）,输出进程每次从输出缓冲区取一个结果输出。请写出利用记录型信号量机制实现三者之间同步的算法。Var full-in,empty-in,mutex-in,full-out,empty-out,mutex-out : semaphore:= 0,M,1,0,N,1;buffer-in: array0,M-1 of item;buffer-out: array0,N-1 of item;in1,out1,in2,out2: integer :=0,0,0,0Begin parbeginprocess IN:beginrepeatinput an item nextin; P(empty-in);P(mutex-in);buffer-in(in1):=nextin;in1 :=(in1+1) mod M;V(mutex-in);V(full-in);until false; endprocess compute:beginrepeatP(full-in);P(mutex-in);nextc:=buffer-in(out1);out1 :=(out1 + 1) mod M;V(mutex-in);V(empty-in);P(mutex-out);P(empty-out);buffer-out(in2):=nextc;in2 :=(in2+1) mod N;V(mutex-out);V(full-out); until false; endprocess out:beginrepeatP(full-out);V(mutex-out);nexto:=buffer-out(out2);out2 :=(out2 + 1) mod N;V(mutex-out);V(empty-out);output the item in nexto;until false; end parend;end;八、设在公共汽车上,司机和售票员的活动分别如下：司机的活动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。1、在汽车不停地到站、停车以及行驶的过程中,司机和售票员之间的活动有什么同步关系？2、请将以下描述这两个活动的PV操作补充完整：Var s1,s2:semaphore =0,0;begin parbegindriver()while(1)p(s1); 启动车辆； 正常行车； 到站停车； v(s2) ；conductor()while(1)关车门； v(s1) ； 售票； p(s2); 开车门； 上下乘客； parend;end;首先分析两个进程之间的同步关系。汽车行驶过程中,司机活动与售票员活动之间的同步关系为：售票员关车门后,向司机发开车信号,司机接到开车信号后起动车辆,在汽车正常行驶过程中售票员售票,到站时司机停车,售票员在车停后开车门让乘客下车。因此,司机起动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。那么,定义两个信号量s1：表示是否允许司机起动车辆,s2：表示是否允许售票员开门。初值为0。 25. 流水线问题 某流水线有4个并发工序P1、P2、P3、P4,他们执行情况如下： P1先执行；P1结束后,P2,P3同时开始执行,P2,P3都结束后,P1才能继续下一次执行,同时P4开始执行。试用PV操作实现他们之间的同步。Var SA12,SA13,SA24,SA34,SB12,SB13,SB24,SB34:Semophore:=1,1,1,1,0,0,0,0;Begin parbeginProcess PABeginP(SA12)/p2结束后发给p1的信号P(SA13)/p3结束后发给p1的信号执行P1V(SB13)/p1结束后发给p3的信号V(SB12)/p1结束后发给p2的信号End;(PA)Process PBBeginP(SB12)/p1结束后发给p2的信号P(SA24)/p4结束后发给p2的信号执行P2V(SB24)/p2结束后发给p4的信号V(SA12)/p2结束后发给p1的信号End;(PB)Process PCBeginP(SB13)/p1结束后发给p3的信号P(SA34)/p4结束后发给p3的信号执行P3V(SB34)/p3结束后发给p4的信号V(SA13)/p3结束后发给p1的信号End;(PC)Process PDBeginP(SB24)/p2结束后发给p4的信号P(SB34)/p3结束后发给p4的信号执行P4V(SA34)/p4结束后发给p3的信号V(SA24)/p4结束后发给p2的信号End;(PD) parend;End.26.某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时,则厅外的购票者可立即进入,否则需在外面等待。若把一个购票者看作一个进程,请回答下列问题。1)用PV操作管理这些并发进程时,应怎样定义信号量,写出信号量的初值以及信号量各种取值的含义。2)根据所定义的信号量,执行PV操作,以保证进程能正确地并发执行。3)若预购票者最多为n个人,写出信号量可能的变化范围（最大值和最小值）。答：1)定义一个信号量S,初值为20。 意义：S0 S的值表示可继续进入售票厅的人数； S=0 表示售票厅已有20个人； Sn)then/顾客数多于沙发数 Begin V(mutex); 离开理发店； End;else/顾客数小于沙发数 Begin count=count+1;/顾客数加1 if(count1)thenBegin P(sofa);/申请沙发 在沙发中就坐； P(empty);/申请理发椅 从沙发上起来； V(s