同步与互斥实例

《同步与互斥实例》由会员分享，可在线阅读，更多相关《同步与互斥实例（25页珍藏版）》请在文档大全上搜索。

1、进程同步与互斥实例进程同步与互斥实例同步实例同步实例1.1.经典的生产者经典的生产者消费者问题消费者问题消费者消费者生产者生产者1.1.经典的生产者经典的生产者消费者问题消费者问题lvar B : integer;l empty:semaphore; /* 可以使用的空缓冲区数可以使用的空缓冲区数 */l full:semaphore; /* 缓冲区内可以使用的产品数缓冲区内可以使用的产品数 */l empty := 1; /* 缓冲区内允许放入一件产品缓冲区内允许放入一件产品 */l full := 0; /* 缓冲区内没有产品缓冲区内没有产品 */lcobegin /*多个子进程并发执行函

2、数多个子进程并发执行函数*/ lProcess producer process consumer lbegin beginl L1: L2:lProduce a product; P(full);lP(empty); 取产品取产品l 直到取为空直到取为空l放产品；放产品；l 直到为满；直到为满； V(empty);lV(full); Consume a product;lGoto L1; Goto L2;l end; end;l coendl2.2.实例实例l设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区B1，然后再复制到缓

3、冲区B2，并在打印机上打印出来。l问问：系统可设哪些进程来完成这个任务？用P-V原语写这些进程的同步算法。 解：由上图可见，系统可设3个进程：输入进程、复制进程、打印进程；分别用进程R、进程C、进程P来表示。 这些进程之间的相互制约关系： R受C的约束；C受R、P的约束；P受C的约束。 设4个信号量：S1=1，S2=0，S3=1，S4=0 同步算法如下：3.理发师问题理发师问题l理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子l如果没有顾客，理发师便在理发椅上睡觉l一个顾客到来时，它必须叫醒理发师l如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开记录

4、型信号量解决理发师问题 var waiting : integer; var waiting : integer; / /* *等候理发的顾客数等候理发的顾客数* */ / CHAIRS:integer; / CHAIRS:integer; /* *为顾客准备的椅子数为顾客准备的椅子数* */ / customers, barbers customers, barbers，mutex : semaphore;mutex : semaphore; customers := 0; barbers := 0; waiting := 0; mutex := 1; customers := 0; bar

5、bers := 0; waiting := 0; mutex := 1;Process barber;Process barber;beginbeginwhile(TRUE); while(TRUE); / /* *理完一人理完一人, ,还有顾客吗还有顾客吗? ?* */ / P(cutomers); / P(cutomers); /* *若无顾客若无顾客, ,理发师睡眠理发师睡眠* */ / P(mutex); / P(mutex); /* *进程互斥进程互斥* */ / waiting := waiting 1; / waiting := waiting 1; /* *等候顾客数少一个等候

6、顾客数少一个* */ / V(barbers); / V(barbers); /* *理发师去为一个顾客理发理发师去为一个顾客理发* */ / V(mutex); / V(mutex); /* *开放临界区开放临界区* */ / cut-hair( ); / cut-hair( ); /* *正在理发正在理发* */ /end;end;process customerprocess customerbeginbegin P(mutex); / P(mutex); /* *进程互斥进程互斥* */ / if waitingCHAIRS begin / if waitingCHAIRS begin

7、 /* *看看有没有空椅子看看有没有空椅子* */ / waiting := waiting+1; / waiting := waiting+1; /* * 等候顾客数加等候顾客数加1 1* */ / V(customers); / V(customers); /* *必要的话唤醒理发师必要的话唤醒理发师* */ / V(mutex); / V(mutex); /* *开放临界区开放临界区* */ / P(barbers); / P(barbers); /* *无理发师无理发师, , 顾客坐着养神顾客坐着养神* */ / get-haircut( ); / get-haircut( ); /*

8、 *一个顾客坐下等理发一个顾客坐下等理发* */ / end end V(mutex); / V(mutex); /* *人满了人满了, ,走吧走吧! !* */ /end;end;互斥实例互斥实例有三个用户进程A、B和C，在运行过程中都要使用系统中的一台打印机输出计算结果。 试说明A、B、C进程之间存在什么样的制约关系？ 为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。l (1) A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。l（2）mutex：用于

9、互斥的信号量，初值为1。l 各进程的代码如下 ：l 进程A 进程B 进程C l . .l . .l P(mutex) P(mutex) P(mutex)l 申请打印机 申请打印机 申请打印机l 使用打印机 使用打印机 使用打印机l V(mutex) V(mutex) V(mutex)l购物问题。某超级市场，可容纳100个人同时购物，入口处备有篮子，每个购物者可持一个篮子入内购物。出口处结账，并归还篮子（出、入口仅容纳一人通过）。请用P、V操作完成购物同步算法。Var S, mutex1, mutex2: semaphore; S:=100; mutex1:=1; mutex2:=1 proce

10、ss Pi: begin P(S);P(mutex1);进入口处，取一只篮子；V(mutex1);选购商品;P(mutex2);结账，并归还篮子；V(mutex2);V(S); endl独木桥问题。某条河上只有一座独木桥，以便行人过河。现在河的两边都有人要过桥，按照下面的规则过桥。为了保证过桥安全，请用P、V操作分别实现正确的管理。l 过桥的规则是：每次只有一个人通过桥。过桥的规则是：每次只有一个人通过桥。Var mutex: semaphore;process (E-W)i: begin P(mutex);过桥；V(mutex); endprocess (W-E)j: begin P(mut

11、ex);过桥；V(mutex); endl.独木桥问题。某条河上只有一座独木桥，以便行人过河。现在河的两边都有人要过桥，按照下面的规则过桥。为了保证过桥安全，请用P、V操作分别实现正确的管理。l 过桥的规则是：同一方向的可连续过桥，过桥的规则是：同一方向的可连续过桥，某方向有人过桥时另一方向的人要等待。某方向有人过桥时另一方向的人要等待。Var S, S1, S2: semaphore; rc1,rc2: integer; S, S1, S2:=1; rc1,rc2:=0; process (E-W)i: begin P(S1);rc1:=rc1+1;if rc1=1 then P(S);V(

12、S1);过桥；P(S1);rc1:=rc1-1;if rc1=0 then V(S);V(S1); endprocess (W-E)j: begin P(S2);rc2:=rc2+1;if rc2=1 then P(S);V(S2);过桥；P(S2);rc2:=rc2-1;if rc2=0 then V(S);V(S2); endl拣棋子问题。生产围棋的工人不小心把相等数量的黑棋子和白棋混装在一个箱子里，先要用自动分拣系统把黑棋子和白棋子分开，该系统由两个并发执行的进程组成，系统功能如下：l(1)进程A专门拣黑子，进程B专门拣白子；l(2)每个进程每次只拣一个子，当一个进程在拣子时不允许另一进

13、程去拣子；l(3)当一个进程拣了一个子（黑或白）以后，必让另一个进程拣一个子（黑或白） 。l请用P、V操作管理两个并发进程，使其能正确实现上述功能。Var S1, S2: semaphore:=1,0;process A: begin repeat P(S1);拣黑子；V(S2); until false; endprocess B: begin repeat P(S2);拣白子；V(S1); until false end某寺庙有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一井水。水井狭窄，每次只能容一个桶取水。水桶总数为3个。每次入、出水缸仅一桶，

14、且不可同时进行。试给出有关取水、入水的算法描述。Var mutex1, mutex2, empty, full, count: semaphore; mutex1:=1; mutex2:=1; empty:=10; full:=0; count:=3;process 小和尚: begin repeat P(empty);P(count);P(mutex1);从井中取水；V(mutex1);P(mutex2);送水入水缸；V(mutex2);V(count);V(full); until false; endprocess 老和尚: begin repeat P(full);P(count);P

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

16、烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者采用信号量机制解决问题。 同步与互斥的解题思路同步与互斥的解题思路l分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。l对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。l对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。l在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作，但V操作的顺序没有严格要求。 同步与互斥的解题步骤同步与互斥的解题步骤l（1）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。l（2）确定同步互斥关系。根据是否使用的是临界资源，还是处理的前后关系，确定同步与互斥，然后确定信号量的个数、含义，以及对信号量的P、V操作。l（3）用类C语言描述同步或互斥算法。