同步与互斥实例

进程同步与互斥实例同步实例1.经典的生产者─消费者问题消费者生产者1.经典的生产者─消费者问题varB:integer;empty:semaphore; /*可以使用的空缓冲区数*/full:semaphore; /*缓冲区内可以使用的产品数*/empty:=1;/*缓冲区内允许放入一件产品*/full:=0;/*缓冲区内没有产品*/cobegin/*多个子进程并发执行函数*/ProcessproducerprocessconsumerbeginbeginL1:L2: Produceaproduct;P(full); P(empty);

取产品直到取为空

放产品；直到为满；

V(empty); V(full);Consumeaproduct;

GotoL1;GotoL2;

end;

end;

coend

2.实例

设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区B1，然后再复制到缓冲区B2，并在打印机上打印出来。问：系统可设哪些进程来完成这个任务？用P-V原语写这些进程的同步算法。解：由上图可见，系统可设3个进程：输入进程、复制进程、打印进程；分别用进程R、进程C、进程P来表示。这些进程之间的相互制约关系：

R受C的约束；C受R、P的约束；P受C的约束。设4个信号量：S1=1，S2=0，S3=1，S4=0

同步算法如下：3.理发师问题理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开记录型信号量解决理发师问题

varwaiting:integer;/*等候理发的顾客数*/CHAIRS:integer;/*为顾客准备的椅子数*/customers,barbers，mutex:semaphore;customers:=0;barbers:=0;waiting:=0;mutex:=1;Processbarber;beginwhile(TRUE);/*理完一人,还有顾客吗?*/

P(cutomers);/*若无顾客,理发师睡眠*/

P(mutex);/*进程互斥*/waiting:=waiting–1;/*等候顾客数少一个*/V(barbers);/*理发师去为一个顾客理发*/

V(mutex);/*开放临界区*/cut-hair();/*正在理发*/end;processcustomerbegin

P(mutex);/*进程互斥*/ifwaiting<CHAIRSbegin/*看看有没有空椅子*/waiting:=waiting+1;/*等候顾客数加1*/V(customers);/*必要的话唤醒理发师*/

V(mutex);/*开放临界区*/P(barbers);/*无理发师,顾客坐着养神*/get-haircut();/*一个顾客坐下等理发*/end

V(mutex);/*人满了,走吧!*/end;互斥实例有三个用户进程A、B和C，在运行过程中都要使用系统中的一台打印机输出计算结果。试说明A、B、C进程之间存在什么样的制约关系？为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。

(1)

A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。（2）mutex：用于互斥的信号量，初值为1。各进程的代码如下：进程A进程B进程C...…......…...

P(mutex)P(mutex)P(mutex)

申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机

V(mutex)V(mutex)V(mutex)购物问题。某超级市场，可容纳100个人同时购物，入口处备有篮子，每个购物者可持一个篮子入内购物。出口处结账，并归还篮子（出、入口仅容纳一人通过）。请用P、V操作完成购物同步算法。VarS,mutex1,mutex2:semaphore;S:=100;mutex1:=1;mutex2:=1processPi:begin P(S); P(mutex1);

进入口处，取一只篮子；

V(mutex1);

选购商品; P(mutex2);

结账，并归还篮子；

V(mutex2); V(S);

end独木桥问题。某条河上只有一座独木桥，以便行人过河。现在河的两边都有人要过桥，按照下面的规则过桥。为了保证过桥安全，请用P、V操作分别实现正确的管理。

过桥的规则是：每次只有一个人通过桥。Var

mutex:semaphore;process(E-W)i:begin

P(mutex);

过桥；

V(mutex);

endprocess(W-E)j:begin

P(mutex);

过桥；

V(mutex);

end.独木桥问题。某条河上只有一座独木桥，以便行人过河。现在河的两边都有人要过桥，按照下面的规则过桥。为了保证过桥安全，请用P、V操作分别实现正确的管理。过桥的规则是：同一方向的可连续过桥，某方向有人过桥时另一方向的人要等待。VarS,S1,S2:semaphore;rc1,rc2:integer;S,S1,S2:=1;rc1,rc2:=0;

process(E-W)i:begin P(S1); rc1:=rc1+1; ifrc1=1thenP(S); V(S1);

过桥；

P(S1); rc1:=rc1-1; ifrc1=0thenV(S); V(S1);

endprocess(W-E)j:begin P(S2); rc2:=rc2+1; ifrc2=1thenP(S); V(S2);

过桥；

P(S2); rc2:=rc2-1; ifrc2=0thenV(S); V(S2);

end拣棋子问题。生产围棋的工人不小心把相等数量的黑棋子和白棋混装在一个箱子里，先要用自动分拣系统把黑棋子和白棋子分开，该系统由两个并发执行的进程组成，系统功能如下：(1)进程A专门拣黑子，进程B专门拣白子；(2)每个进程每次只拣一个子，当一个进程在拣子时不允许另一进程去拣子；(3)当一个进程拣了一个子（黑或白）以后，必让另一个进程拣一个子（黑或白）。请用P、V操作管理两个并发进程，使其能正确实现上述功能。VarS1,S2:semaphore:=1,0;processA:beginrepeat P(S1);

拣黑子；

V(S2);untilfalse;

endprocessB:beginrepeat P(S2);

拣白子；

V(S1);untilfalse

end某寺庙有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一井水。水井狭窄，每次只能容一个桶取水。水桶总数为3个。每次入、出水缸仅一桶，且不可同时进行。试给出有关取水、入水的算法描述。Varmutex1,mutex2,empty,full,count:semaphore;mutex1:=1;mutex2:=1;empty:=10;full:=0;count:=3;process小和尚:beginrepeat

P(empty);

P(count); P(mutex1);

从井中取水；

V(mutex1); P(mutex2);

送水入水缸；

V(mutex2);

V(count);

V(full);untilfalse;

endprocess老和尚:beginrepeat

P(full);

P(count); P(mutex2);

从缸中取水；

V(mutex2);

V(empty);

V(count);untilfalse;

end习题1.司机和售票员问题问题描述：在公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆正常运行到站停车售票员的活动：关车门售票开车门在汽车不断的到站，停车，行驶过程中，这两个活动有什么同步关系？用信号量和Ｐ，Ｖ操作实现．2.吸烟者问题三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将