复习资料3PV操作

1、P、V、生产者-消费者问题（采用信号量机制）Varmutex,empty,full:semaphore:=1,n,0;buffer:array0,.n-1;ProducerConsumeP(empty);P(mutex)进入区P(full);P(mutex)进入oneunit->bufferneunit<-V(mutex);V(full);/退出区V(mutex);V(empty)退出full是”满”数目，初值为0,empty是"空”数目，初值为N。实际上,fullin,out:integer:=0,0;"beginparbegin生产者：beginrepeat

2、由生产一个产品nextp;）uffeeuP（mutex）;将产品输入到buffer中+empty=N;mutex用于访问缓冲区时的互斥，初值是1;每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥一一否则可能死锁三、读者-写着问题（采用信号量机制）消费者：beginrepeatP(full);P（mutex）;从buffer中取一个产品nextc=bufferout;end;bufferin:=nextp;in=(in+1)modn;V(mutex);V(full);untilfalse;parend;end;end;out:=(out+1)modn;V(mutex);V(em

3、pty);untilfalse;第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待Varwmutex,rmutex:semaphore=1,1;buffer:array0,.n-1;Rcount:integer:=0;beginWmutex表示”允许写”，初值是1。公共变量Rcount表示"正在读”的进程数，初值是0;WriterReaderP(Wmutex);write;V(Wmutex);P(Rmutex);if(Rc

4、ount=0)P(Wmutex);+Rcount;V(Rmutex);read;P(Rmutex);-Rcount;if(Rcount=0)V(Wmutex);V(Rmutex);Rmutex表示对Rcount的互斥操作，初值是1。第二类：写者优先Wmutex表示”允许写”，初值是1。公共变量Rcount表示"正在读”的进程数，初值是0;Rmutex表示对Rcount的互斥操作，初值是1。“为了使写者优先，可在原来读者优先的基础上增加一个初值为parbegin读者：beginrepeatP(rmutex);if(Rcount=0)P(wmutex);Rcount=Rcount+1;V

5、(rmutex);执行read操作;P(rmutex);Rcount=Rcount-1;if(Rcount=0)V(wmutex);V(rmutex);untilfalse;end;parend;end;写者：beginrepeatP(wmutex);进行write操作;V(wmutex);untilfalse;end;1的信号量S,使得至少有一个写者准备访问共享对象时，他可以使后续的者进程等待与完成。初值为0的Wcount用来对与者进行计数，初值为1的互斥信号量mutex用来实现多个与者对Wcount的互斥访问”。VarS,wmutex,rmutexmutex:semaphore=1,1,1

6、,1;buffer:array0,.n-1;Rcount:integer:=0;beginparbegin读者：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);untilfalse;end;写者：beginrepeatP(mutex);if(Wcount=0)P(S);Wcount=Wcount+1;V(mutex);P(wmutex);进行write操

7、作；V(wmutex);P(mutex);Wcount=Wcount-1;if(Wcount=0)V(S);V(mutex);untilfalse;end;parend;end;二、哲学家进餐问题Varsm:semaphore:=4;Philosopheri:while(true)(P(sm);P(chopSticki);/getleftchopstickP(chopStick(i+1)%5);/getrightchopstickeat;V(chopSticki);/returnleftchopstickV(chopStick(i+1)%5);/returnrightchopstickV(sm

8、);think;)老和尚喝水问题：某寺庙，有小、老和尚若干，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井窄，每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶，且不可同时进行。试给出有关取水、入水的算法。Mutex1=1,mutex2=1,empty=10,full=0,count=3X:BeginRepeatP(empty);P(count);/申请水桶P(mutex1);L:BeginRepeatP(full);P(count);P(mutex2);Fetchfromwell;Fetchfromcrock;V(mutex1);V(mutex2);P(mut

9、ex2);V(empty);Pour;V(count);V(mutex2);V(count);/释放水桶V(full);Untilfalse;Untilfalse吃水果问题：桌上有一只盘子，每次只能放一个水果，爸爸向盘中放苹果或桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出三人之间的同步关系，并用P、V操作实现三人正确活动的程序。分析:此问题实际上是生产者-消费者问题的一个变形生产者：爸爸，消费者：女儿、儿子，缓冲区：盘子(SIZE=1)解答：设置3个信号量：互斥信号量mutex=1;资源信号量：S1

10、=0表示盘中是否有苹果，实现爸爸与女儿的同步；S2=0表示盘中是否有桔子，实现爸爸与儿子的同步爸爸：P(mutex);将水果放入盘中；IF苹果V(S1)elseV(S2)女儿：P(S1);从盘中取苹果；V(mutex)；吃苹果儿子：P(S2);从盘中取桔子；V(mutex)；吃桔子22.隧道问题1一座山中有一条隧道，规定每次只允许一辆车过隧道。现在山南、山北都有车要过隧道，如果把每个过隧道者看作一个进程，为保证安全，请用PV操作实现正确管理。VarS:semaphore:=1;Beginparbeginprocess(S-N)i(i=1,2-)process(N-S)i(i=1,2-)begi

11、nbeginP(S);P(S);过隧道；过隧道；V(S);V(S);end;end;parend;end;24.隧道问题2一座上中有一条隧道，规定每次只允许一辆车过隧道，而且山南、山北交替过隧道。现在山南、山北都有车要过隧道，如果把每个过隧道者看作一个进程，为保证安全，请用PV操作实现正确管理。假设约定南边的先入隧道。VarS1，S2:semaphore:=1,0;Beginparbeginprocess(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;某系

12、统由数据输入、计算和输出三个进程组成，输入进程把数据送入由M个缓冲块组成的输入缓冲区(每次向一个缓冲块送数据)，计算进程从输入缓冲区取数据计算(每次取一个缓冲块的数据)，并将计算结果送入到由N个缓冲块组成的输出缓冲区(每次向一个缓冲块送数据)，输出进程每次从输出缓冲区取一个结果输出。请写出利用记录型信号量机制实现三者之间同步的算法。Varfull-in,empty-in,mutex-in,full-out,empty-out,mutex-out:semaphore:=0,M,1,0,N,1;buffer-in:array0,M-1ofitem;buffer-out:array0,N-1ofit

13、em;in1,out1,in2,out2:integer:=0,0,0,0BeginparbeginprocessIN:beginrepeatinputanitemnextin;P(empty-in);P(mutex-in);buffer-in(in1):=nextin;in1:=(in1+1)modM;V(mutex-in);V(full-in);untilfalse;endprocesscompute:beginrepeatP(full-in);P(mutex-in);nextc:=buffer-in(out1);out1:=(out1+1)modM;V(mutex-in);V(empty

14、-in);P(mutex-out);P(empty-out);buffer-out(in2):=nextc;in2:=(in2+1)modN;V(mutex-out);V(full-out);untilfalse;endprocessout:beginrepeatP(full-out);V(mutex-out);nexto:=buffer-out(out2);out2:=(out2+1)modN;V(mutex-out);V(empty-out);outputtheiteminnexto;untilfalse;endparend;end;八、设在公共汽车上，司机和售票员的活动分别如下：司机的活

15、动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。1、在汽车不停地到站、停车以及行驶的过程中，司机和售票员之间的活动有什么同步关系?2、请将以下描述这两个活动的PV操作补充完整：Vars1,s2:semaphore=0,0;beginparbegindriver()(while(1)(p(s1);启动车辆；正常行车；到站停车；v(s2);)conductor()(while(1)关车门;v(s1)；售票；p(s2);开车门；上下乘客；)parend;end;首先分析两个进程之间的同步关系。汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号

16、，司机接到开车信号后起动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。因此，司机起动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。那么，定义两个信号量s1:表示是否允许司机起动车辆,s2:表示是否允许售票员开门。初值为0。25.流水线问题某流水线有4个并发工序P1、P2、P3、P4,他们执行情况如下：P1先执行；P1结束后，P2,P3同时开始执行，P2,P3都结束后,P1才能继续下一次执行，同时P4开始执行。试用PV操作实现他们之间的同步VarSA12，SA13，SA24，SA34，SB12，SB13，SB24，

17、SB34:Semophore:=1,1,1,1，0，0，0，0;BeginparbeginProcessPABeginP(SA12)/p2结束后发给p1的信号P(SA13)/p3结束后发给p1的信号执行P1V(SB13)/p1结束后发给p3的信号V(SB12)/p1结束后发给p2的信号End;(PA)ProcessPBBeginP(SB12)/p1结束后发给p2的信号P(SA24)/p4结束后发给p2的信号执行P2V(SB24)/p2结束后发给p4的信号V(SA12)/p2结束后发给p1的信号End;(PB)ProcessPCBeginP(SB13)/p1结束后发给p3的信号P(SA34)/p

18、4结束后发给p3的信号执行P3V(SB34)/p3结束后发给p4的信号V(SA13)/p3结束后发给p1的信号End;(PC)ProcessPDBeginP(SB24)/p2结束后发给p4的信号P(SB34)/p3结束后发给p4的信号执行P4V(SA34)/p4结束后发给p3的信号V(SA24)/p4结束后发给p2的信号End;(PD)parend;End.26.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题。1) 用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的

19、初值以及信号量各种取值的含义。2) 根据所定义的信号量，执行PV操作，以保证进程能正确地并发执行。3) 若预购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。答：1)定义一个信号量S，初值为20。意义：S>0S的值表示可继续进入售票厅的人数；S=0表示售票厅已有20个人；S<0|S|的值为等待进入售票厅的人数。2) cobeginprocesspl(l=1,2，)beginP(S)；进入售票厅；购票；退出；V(S);end;coend;S的最大值为20，最小值为20-no7.10睡觉的理发师问题顾客进程和理发师进程之间存在着多种同步关系(1) 只有在理发椅空闲时，顾客

20、才能坐到理发椅上等待理发师，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才开始理发，否则他也必须等待。这种同步关系类似于单缓冲(对应于理发椅)的生产者-消费者问题中的同步关系，故可通过信号量empty和full来控制。(2) 顾客理完发后必须向理发师付费，并等理发师收费后顾客才能离开；而理发师则需等待顾客付费，并在收费后通知顾客离开。这可分别通过两个信号量payment和receipt来控制。(3) 等待室中的N张沙发是顾客进程竞争的资源，故还需为它们设置一个资源信号量。(4) 为了控制顾客的人数，使顾客能在所有沙发都被占用时离开理发店，还必须设置一个整形变量count来对理发店中的顾客

21、进行计数，该变量将被多个顾客进程互斥地访问并修改，这可以通过一个互斥信号量mutex来实现。为解决上述问题，需设置一个整形变量count用来对理发店中的顾客进行计数，并需要设置6个信号量；其中：mutex用来实现顾客进程对count变量的互斥访问，其初值为1;sofa是对应于等候室中n张沙发的资源信号量，其初值为n；empty表示是否有空闲的理发椅，其初值为1;full表示理发椅上是否坐有等待理发的顾客，其初值为0;payment用来等待付费，其初值为0;receipt用来等待收费，其初值为0;Varcount:integer:=0;mutex,sofa,empty,full:semaphore:=1,n,1,0;cut,payment,Receipt=0,0,0;BeginParbeginBarbr:beginrepeatP(full);/等待顾客替顾客理发P(payment);/等待付费收费；V(receip