复习资料3(PV操作)

1P、V一、生产者--消费者问题（采用信号量机制）ConsumerProducerP(empty);P(mutex);//进入区oneunit--buffer;V(mutex);V(full);//退出区P(full);P(mutex);//进入区oneunit--buffer;V(mutex);V(empty);//退出区full是满数目,初值为0,empty是空数目,初值为N。实际上,full+empty==N;mutex用于访问缓冲区时的互斥,初值是1;每个进程中各个P操作的次序是重要的：先检查资源数目,再检查是否互斥――否则可能死锁;Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,.....n-1];in,out:integer:=0,0;beginparbegin生产者：beginrepeat生产一个产品nextp;P(empty);P(mutex);将产品输入到buffer中buffer[in]:=nextp;in=(in+1)modn;V(mutex);V(full);untilfalse;end;消费者：beginrepeatP(full);P(mutex);从buffer中取一个产品nextc=buffer[out];out:=(out+1)modn;V(mutex);V(empty);untilfalse;end;parend;end;三、读者--写着问题（采用信号量机制）第一类：读者优先如果读者来：1）无读者、写者,新读者可以读2）有写者等,但有其它读者正在读,则新读者也可以读3）有写者写,新读者等如果写者来：1）无读者,新写者可以写2）有读者,新写者等待3）有其它写者,新写者等待Wmutex表示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0；Rmutex表示对Rcount的互斥操作,初值是1。P(Rmutex);if(Rcount==0)P(Wmutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)V(Wmutex);V(Rmutex);ReaderP(Wmutex);write;V(Wmutex);WriterVarwmutex,rmutex:semaphore=1,1;buffer:array[0,.....n-1];Rcount:integer:=0;beginparbegin读者：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);untilfalse;end;写者：beginrepeatP(wmutex);进行write操作；V(wmutex);untilfalse;end;parend;end;第二类：写者优先2Wmutex表示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0；Rmutex表示对Rcount的互斥操作,初值是1。“为了使写者优先,可在原来读者优先的基础上增加一个初值为1的信号量S,使得至少有一个写者准备访问共享对象时,他可以使后续的读者进程等待写完成。初值为0的Wcount用来对写者进行计数,初值为1的互斥信号量mutex用来实现多个写者对Wcount的互斥访问”。VarS,wmutex,rmutexmutex:semaphore=1,1,1,1;buffer:array[0,.....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操作；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(chopStick[i]);//getleftchopstickP(chopStick[(i+1)%5]);//getrightchopstick......eat;......V(chopStick[i]);//returnleftchopstickV(chopStick[(i+1)%5]);//returnrightchopstickV(sm);......think;......}3老和尚喝水问题:某寺庙,有小、老和尚若干,由小和尚提水入缸供老和尚饮用。水缸可容10桶水,水取自同一井中。水井窄,每次只能容一个桶取水。水桶总数为3个。每次入、取缸水仅为1桶,且不可同时进行。试给出有关取水、入水的算法。Mutex1=1,mutex2=1,empty=10,full=0,count=3X:BeginRepeatP(empty);P(count);//申请水桶P(mutex1);Fetchfromwell;V(mutex1);P(mutex2);Pour;V(mutex2);V(count);//释放水桶V(full);Untilfalse;L:BeginRepeatP(full);P(count);P(mutex2);Fetchfromcrock;V(mutex2);V(empty);V(count);Untilfalse吃水果问题：桌上有一只盘子,每次只能放一个水果,爸爸向盘中放苹果或桔子,儿子专等吃盘里的桔子,女儿专等吃盘里的苹果。只要盘子空,则爸爸可向盘中放水果,仅当盘中有自己需要的水果时,儿子或女儿可从中取出,请给出三人之间的同步关系,并用P、V操作实现三人正确活动的程序。分析:此问题实际上是生产者-消费者问题的一个变形生产者:爸爸,消费者：女儿、儿子,缓冲区：盘子（SIZE=1）解答：设置3个信号量：互斥信号量mutex=1；资源信号量：S1=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……)beginP(S);过隧道;V(S);end;process(N-S)i(i=1,2……)beginP(S);过隧道;V(S);end;parend;end;24.隧道问题2一座上中有一条隧道,规定每次只允许一辆车过隧道,而且山南、山北交替过隧道。现在山南、山北都有车要过隧道,如果把每个过隧道者看作一个进程,为保证安全,请用PV操作实现正确管理。假设约定南边的先入隧道。4VarS1,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;某系统由数据输入、计算和输出三个进程组成,输入进程把数据送入由M个缓冲块组成的输入缓冲区（每次向一个缓冲块送数据）,计算进程从输入缓冲区取数据计算（每次取一个缓冲块的数据）,并将计算结果送入到由N个缓冲块组成的输出缓冲区（每次向一个缓冲块送数据）,输出进程每次从输出缓冲区取一个结果输出。请写出利用记录型信号量机制实现三者之间同步的算法。Varfull-in,empty-in,mutex-in,full-out,empty-out,mutex-out:semaphore:=0,M,1,0,N,1;buffer-in:array[0,M-1]ofitem;buffer-out:array[0,N-1]ofitem;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-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;八、设在公共汽车上,司机和售票员的活动分别如下：司机的活动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。1、在汽车不停地到站、停车以及行驶的过程中,司机和售票员之间的活动有什么同步关系？2、请将以下描述这两个活动的PV操作补充完整：Vars1,s2:semaphore=0,0;beginparbegin5driver(){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操作实现他们之间的同步。VarSA12,SA13,SA24,SA34,SB12,SB13,SB24,SB34:Semophore:=1,1,1,1,0,0,0,0;BeginparbeginProcessPABeginP(SA12)//p2结束后发给p1的信号P(SA13)//p3结束后发给p1的信号执行P1V(SB13)//p