第2章进程同步演示

1、22 进程间通信221 竞争条件 并发进程的相关性 资源共享方式：a)内存，CPU，设备，文件，系统分配和协调；b)小量软资源，共享队列，通过手段协调。 进程合作。1间接相互制约方式2直接相互制约方式这些关系可以归结为两种关系:互斥和同步。互斥（mutual exclusion）-共享某资源的各进程不能同时进行同一操作。竞争条件-(race condition,书P24)即两个或多个进程读写某些数据,而最后的结果取决于进程运行的精确时序,就称为竞争条件。这就是为什么会产生与时间有关的错误的原因。同步（synchronization）-关于进程间合作时操作的时间顺序的限制。互斥和同步的区别:一个

2、只要不同时发生就行，谁先谁后看排队、优先级;一个是动作要有严格的时间顺序。下面我们先讨论互斥的问题222 临界区(Critical Section)我们把一次仅允许一个进程使用的资源称为临界资源(Critical Resource)。如打印机，绘图仪，磁带机等，公共变量，公用表格，公用队列等。访问临界资源的那段程序称为临界区。它能够从概念上分离出来，而，或叫临界段(互斥段)。例1:有两个进程共享一个变量count。P1:R1:=COUNT;| R1:=R1+1;| COUNT:=R1;|P2:R2:=COUNT;| R2:=R2+1;| COUNT:=R2;此时两个进程各自对count作了加操

3、作，而count增加了2。如果执行是另一种顺序。P1:R1:=COUNT;| 发生时钟中断P2:R2:=COUNT;|P2:R2:=R2+1;|COUNT:=R2;|P1:R1:=R1+1;|COUNT:=R1;虽然两个进程也各自对count作了加一操作，但count却只增加了一。例2:两个进程在系统中共用一个缓冲队列。如果程序顺序是p1:return ptr1:=ptr;获得第一个缓冲区的PTR ptr:=tail(ptr);指针指向下一个p2:reture ptr2:=ptr;获得第二个缓冲区的PTRptr:=tail(ptr);指针指向第三个但如果程序顺序是：p1:return ptr1

4、:=ptr;获得第一个缓冲区的PTR发生时钟中断：p2:reture ptr2:=ptr;也获得第一个缓冲区的PTRp1:ptr:=tail(ptr);指针指向第二个PTRp2:ptr:=tail(ptr);指针指向第三个PTR执行结果造成p1，p2共得一个缓冲区，第二个缓冲区丢失，第三个缓冲区成为首部。设置准则:P24 任何两个进程不能同时处于临界区。 不应对CPU的速度和数目作任何假设。 临界区外的进程不得阻塞其它进程。 不得使进程在临界区外无休止地等待。223 忙等待的互斥2231 关闭中断2332 设置锁变量在测试与设置方法中，设置个变量w来代表某种临界资源的状态，因此w又成为锁或锁位

5、。w=0 表示资源空闲(可用)w=1 表示资源已被使用关锁原语: lock(w)；关中断L:if w=1 then goto L else w:=1开中断开锁原语: unlock(w)；w:=0；大家注意:由于原语执行时不能中断。考虑三个进程P1：P2：P3：lock(w);lock(w);lock(w);执行临界段1；执行临界段2；执行临界段3；unlock(w);unlock(w);unlock(w);2233 严格轮换法（书P25）2234 Peterson解决方案（书P26）2235 TSL指令例1:IBM360/370采用汇编实现LOCK(X)TSX 测锁位并置1，送PSW(条件码)

6、BNZ -4 不为0，往回跳4字节，继续执行TSX。UNLOCK(X)MOI X，00例2:Intel 8086/8088 汇编指令也能实现锁原语。LOCK PROC FAR汇编语言的过程保留字MOV AL，1;将1送入AL寄存器AGAIN:XCHG AL，FLAG ;交换指令，状态进入AL，FLAG=1关锁TEST AL，AL;测试AL，看状态是什么JNZ AGAIN;AL=1时回跳(FLAG=1)RET;返回主程序UNLOCK PROC FAR;开锁MOV FLAG ，0;FLAG=0RET;修改后的关锁和开锁原语为:lock w:begin if w=1 then begin block

7、(n); insert(wL，n); scheduler end else w:=1end;unlock w:begin if wn then begin remove(wL，q); states(q):=readya; insert(RL，q) end; w:=0end;225 信号量(semaphores machini)一、信号量信号量是表示资源的物理实体，是一个与队列有关的整型变量。在类pascal中，将它表示为一个记录。type semaphore=record val:integer;值域 L:pointer;指针域end;信号量实际是一个计数锁(广义锁)，它的值只能由P、V操作来

8、改变。二、P、V操作(计数信号量机制)procedure p(s)；var s:semphore;beginLock out interrupt;关中断 s.value=s.value-1; if s.value0 then beginstates(q):=blockeda;活动阻塞insert(wL，q);插入等待队列unlock interrupt;开中断scheduler; 重新分配CPUend else unlock interrupt;开中断end；procedure v(s)var s:semaphore;begin lock out interrupt;关中断 s.value:=

9、s.value+1; if s.value=0等待队列不空 then beginremove(wl，r);从wl队中摘下rstates(r):=readya;活动就绪insert(rl，r);插入就绪队列length(rl):=length(rl)+1endl; unlock interrupt开中断end;P、V操作必须是原语，执行期间不可分割。P、V操作的物理意义：P操作:信号量s可以看成一个资源量。例如有几台打印机，即信号量 s.value初值=n，如果有进程对s进行P操作就是申请该资源的一个单位(申请一台打印机)，所以进行一次P操作，s.value要减1(减少一个资源)。进行到最后S分

10、配完毕(s.value=0)，再有进程申请资源(进行P(s)，使s.value0 其值为剩余(尚有)资源s.value=0 无资源，无等待进程s.value0 s.value的绝对值即为等待该资源的进程数。V操作:表示释放资源，s.value=s.value+1。如果s.value=1 then x:=x-1; write(x); V(mutex)end;procedure t2(x); var x:integer; begin P(mutex);read(x);if x=1 then x:=x-1;write(x);V(mutex);end;Hansen提出并行PASCAL语言之前，Dijk

11、stra提出： COBEGIN S1;S2;S3；;Sn COENDP、V操作在这里起到了lock和unlock的作用，实现了互斥。2利用信号量实现进程同步例1:有一个缓冲区，有计算进程和打印进程同时并行工作，计算进程将结果放在缓冲区，放之前要申请缓冲区空，打印进程负责把结果打印出来，做之前要申请缓冲区满，这是一个同步问题，初始，一定要计算进程先动作，先缓冲区写入，然后再打印进程工作。在缓冲区满时，计算进程不能写。在缓冲区空时，打印进程不能读。打印进程计算进程 缓冲区我们可以设空、满信号量 empty:=1； full:=0；P计算：P打印：RepeatRepeatP(empty);P(ful

12、l); 写入数据；输出数据；V(full);V(empty);Until false;Until false;用P、V操作，实现了题意要求*生产者-消费者问题(producer-consumer problems)生产者和消费者问题，是从操作系统中许多实际同步问题中抽象出来的具有代表性的问题。它反映了操作系统中典型的同步例子。生产者进程生产信息，例如它可以是计算进程;消费者进程使用信息，它可以是输出打印进程。由于生产者和消费者进程彼此独立，且运行速度不确定，可能出现生产者已生产了信息，而消费者却没有来得及接受的情况，为此引入了一个或若干个存储单元组成的临时存储区，以便存放生产者所产生的信息，以

13、平滑进程间由于速度不确定所带来的问题。这个临时存储区叫做缓冲区，通常用一维数组来抽象。例2：如果图变成如下 S TGETCOPYPUTGET、COPY、PUT三进程共用两个缓冲区S、T(其大小为每次存放一个记录)。GET进程负责不断把输入记录送入缓冲区S中，COPY进程负责从缓冲区S中取出记录复制到缓冲区T中，PUT进程负责把记录从缓冲区T中取出打印，试用P、V操作实现这三个进程之间的同步。例3：有穷缓冲区生产者和消费者问题（P30-图2-11）设有多个生产者和消费者，他们共享一个具有n个存储单元的有穷缓冲区0n-1。inout满空指针in指出空缓冲区头，out指出满缓冲区头，每当有生产者要求

14、一个空缓冲区，则分给其指针in指出的空缓冲区，同时指针in按箭头方向移动一个位置，消费者要求满缓冲区操作，也类似移动out指针，分一个满缓冲区。为使生产者进程和消费者进程协调合作，它们应遵循以下规则:1)只要缓冲区有空闲单元，生产者都可存放信息，当缓冲区满时，任一生产者提出要求时，都必须等待。2)只要缓冲区中有信息可取，消费者都可以从缓冲区中取用信息，当缓冲区空时，任一消费者取用信息都必须等待。3)生产者们和消费者们不能同时读写缓冲区。设缓冲区编号为0n-1，设三个信号量。var mutex，empty，full:semphore:=1，n，0;buffer:array 0.n-1of mas

15、sege;in，out:0.n-1;begin cobeginproducer:begin repeat produce a new message m;p(empty);p(mutex);buffer(in):=m;in:=(in+1)mod n;v(mutex);v(full); until falseend;consumer:begin repeatp(full);p(mutex);in:=buffer(out);out:=(out+1)mod n;v(mutex);v(empty);consume message m until falseend; coendend.环型缓冲区机构适用

16、于实现操作系统中的假脱机控制，经常使用的是spooling系统。生产者实际是假脱机入口进程，缓冲区大小要使入口进程和出口进程速度匹配。私用信号量（Private Semaphore）。一个进程的私用信号量是从制约它的进程发送来的、使它能继续执行条件所需的消息。与私用信号量相对应，我们称互斥信号量为公用信号量。例4：利用信号量描述前驱关系为了实现这种前驱关系，我们只需为进程P1，P2，P6各设置一个私用信号量a，b，c，d，e，作为同步信号，赋初值为0。S1S2S3S4S5S6begin cobeginp1:begin S1;v(s1);v(s1); end;p2:begin p(s1); S2

17、; v(s2);v(s2); end;p3:begin p(s1); S3; v(s3); end;p4:begin p(s2); S4; v(s4); end;p5:begin p(s2); S5; v(s5); end;p6:begin p(s4); p(s5); p(s3); S6; end;在考虑进程同步问题时，要注意到几个问题: 分析有几个临界区，是否需要公用互斥信号量，初值是多少（资源量）。 考虑几个进程如何同步，如何通过信号量互通消息，初值是多少。如何用信号量作为进程阻塞和唤醒的机构。a）在资源分配和释放情况中，进程所等待的事件是其所要求的资源被其它进程释放出来成为可用。这时信号

18、量代表该资源的数量，而信号量上的P、V操作可以成为资源分配和释放的机构。b）在进程间相互协同情况下，使进程等待某事件来控制其执行顺序，此时进程所等待的事件主要是等待相关的协作进程完成某个操作，当进程在等待这类事件时，最好将它自己阻塞，以等待该事件的发生或完成。当一个相关的协同进程完成了它的操作后，要唤醒等待它的进程。于是它可以用V操作作为唤醒工具。例:两个协同进程A和B，进程A要等待进程B的计算结果，则这两个进程的执行如下:进程A:进行计算P(Bi);阻塞自己等B的结果继续计算进程B:进行计算;V(Bi);唤醒Ac) 在进程同步中，V操作次序无关紧要，而P操作顺序不能颠倒，它会引起死锁（死锁时

19、会分析）。d) P、V必须配对。若多一个P操作，必然会有进程总在阻塞队列中等待，永远得不到唤醒；若多一个V操作，就会两个进程同时进入临界区的可能，资源已用完，而某个进程仍进一步获得资源而出错。对信号量及P、V操作的评述：从以上例举的几个例子中可见，信号量可用来实现同步和互斥。(1)用信号量实现互斥时，各进程中使用临界资源的那段程序代码(临界区)的开始和末尾，分别用P(s)和V(s)括起来，格式为Pi:p(s); Pj: p(s); Csi; csj; v(s) ; v(s); (2)当信号量用来实现同步时，伙伴进程间要通过缓冲区来存放要交换的信息，消费者在使用信息之前，通过p(s)询问缓冲区中

20、是否有信息可取用，若无则阻塞在相应队列中等待。而生产者生产出信息后，要通过V(s)通知消费者来取信息。因此在协作进程间p(s)，v(s)通常按如下方式安排：生产者： 生产信息 V（S）消费者： P（S） 消费信息发消息 (3)并行系统中的进程相互依赖、相互制约关系，表现为进程间的互斥与同步关系。为了实现互斥与同步，进程间不仅要传递信息，而且为了传递信息还要通过公共变量s进行通讯联系。因此通常也把同步与互斥叫做进程通讯。 (4)P、V存在许多不足之处： 必须配对，p次序不能颠倒 P、V分散在共享同一资源的各进程中，增加程序复杂性，各进程互相依赖，独立性差。容易死锁。227 管程(monitor)

21、-P32一、管程定义Hansen为管程所下的定义是：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程由4部分组成1管程名 monitor monitor-name2数据说明部分:描述共享资源的数据结构。它们是局部于该管程的局部变量。3若干过程:管程中的过程是为了分配或使用共享资源，并在相应数据结构上进行操作所必须的程序代码。procedure (，形参，)begin过程体end;4对变量赋初值的语句。管程能使并发进程同步，并在它们之间传送数据。管程也能控制竞争，使共享物理资源的各个进程遵循所应的次序。二、实现管程的基本原则。

22、1一个管程管理一个或一组共享资源。2一个进程请求使用资源时，必须先通过调用指定的”管程入口”，才能进入管程，然后通过管程中的过程使用资源。每一个管程入口，对应一个对临界资源进行操作的过程。调用管程入口的格式为monitor-nameprocedure-name （实参）3互斥： 4、同步:进程必须在管程外等待，因此引入了条件变量这个概念。每个独立的条件变量是和进程可能需要等待的不同原因相联系。5每一条件变量名就是一个先进先出队或一个排队栈。我们可以把一个缓冲区定义为一个管程，它由表示缓冲区内容的一些共享变量组成。它还包括两个管程过程。发送和接受。开始初启操作将缓冲区置空。局部于管程内的数据结构

23、只能被局部于管程内的过程所访问。不能被管程外的过程对其进行操作。反之，局部于管程内的过程只能访问管程内的数据结构，因此管程相当于围墙一样把共享变量(数据结构)和对它进行的若干操作过程围了起来。进程要访问共享资源。(进入围墙使用某操作过程)就必须经过管程(围墙的门)才能进入。管程每次只允许一个进程进入管程内，即互斥地访问共享资源。共享数据XY过程（操作）初始化代码X 为条件变量Y 等待进入管程的队列例：用管程实现生产者消费者问题Type procedure-consumer=monitor;定义管程名var in，out，count:0.n-1;定义变量buffer:array0.n-1 of

24、message;notfull，notempty:condition;条件变量procedure entry-put(in);beginif count=n then notfull.wait;如无空缓冲区，调用wait阻塞自己，插入等候空缓冲区队，同时以notfull为条件查有要无进管程的消费者进程。buffer(in):=m;in:=(in+1) mod n;count:=count+1;count=n满，count=0空if notempty.queue then notempty.signalend;procedure entry-get(m);beginif ountfile即把当前

25、目录中的文件名等信息输出到文件file中当另一进程执行命令$ws file则把file 中由ls写入的内容又输到ws中。用pipe机构，直接写$ls | wc利用pipe文件作为管道，把ls命令的输出作为wc命令的输入，不用通过中介文件，管道的作用类似消息缓冲区通信，但不是用内存缓冲区，而是借助文件进行通信。4直接通信的实例-消息缓冲通信 消息缓冲通信的数据结构(p55)所谓消息(message)，通常由消息头和消息正文构成，可用Pascal描述如下type msg=record msgsender 消息发送者名 msgnext 下一个消息，链指针 msgsize 整个消息的字节数 msgte

26、xt 消息正文 end;在直接通讯情况下进程可以调用原语send(p，msg) 向进程p发送一个消息receive(q，msg) 接受来自进程q的一个消息这一技术的基本思想是由系统管理一个消息缓冲池(许多缓冲区)，缓冲池分成若干个缓冲区，每个缓冲区可放一个消息。当一进程需发送消息时，先向系统申请一缓冲区，写入消息后，连接到接收进程PCB指示的消息队列上，然后通知接收进程。设置消息队列的原因是因为一个进程可能在一段时间收到多个消息，而来不及处理。消息队列的头由接收进程PCB中的队列指针给出，PCB就要增加几项内容:mutex:用于消息队列互斥访问的信号量。sm:表示接收消息的计数同步信号量。pm

27、:消息队列的队首指针mutexSmPmMsgsendmsgsizemsgtextPCB 发送和接收消息的原语send和read功能如下图：循环队操作申请一个消息缓和冲区发送区内容复制到缓冲区找到到接收进程的PCBP(mutex)把消息缓冲区链入接收进程的消息链尾 V(Sm)V(mutex) P(Sm) P(mutex)取下Pm所指消息链首的缓冲区，修改链首指针把缓冲区中内容全部复制到接收区V(mutex)释放空缓冲区(a) send(b) receive23 经典的IPC问题231 哲学家进餐问题（P39）一、利用信号机制解决哲学家进餐问题哲学家进餐问题也是一个经典的同步问题，它是由Dijks

28、tra1965a提出并解决的。对上述问题的一个简单的解是为每只筷子设置一个信号量，一个哲学家通过在相应信号量上执行p操作抓起一只筷子，通过执行v操作放下一只筷子，5个信号量构成如下的数组:var chopstick array0.4 of semaphore;每个信号量都置初值为1，于是哲学家们的活动可描述如下:repeatp(forki);p(forki+1 mod 5);Eat;v(forki);v(forki+1 mod 5);think;until fale;此解虽然可以保证互斥使用筷子，但有可能产生死锁，假设5个哲学家同时抓起各自左边的筷子，于是5个信号量的值都为0，当每一个哲学家企

29、图拿起他右边的筷子时，便出现了循环等待的局面-死锁。为了防止死锁的产生，可以有以下措施:l 至多允许4个哲学家同时坐在桌子的周围l 当一个哲学家左右的筷子都可用时，才允许他抓起筷子l 让所有哲学家顺序编号，对于奇数号的哲学家必须首先抓起左边的筷子，然后抓起右边的筷子，而对偶数的哲学家则反之。实际程序见书P41图2-20二、用管程解决五个哲学家进餐问题:条件:(1) 相邻两哲学家不能同时进餐(2) 最多只能有两人进餐，即最大并行性为二(3) 为排除随机因素，规定哲学家进餐时，先拿左筷，后拿右筷，不能同时拿起两只筷子，餐后放筷时，也先左后右同样顺序forks(i)不是叉子状态，而是第i位哲学家可用

30、叉子数(0，1，2)，当fork(i)=2时才可以吃。否则等待在自己的条件变量上。type forkscontrol=monitor;var forks，right，left:array0.4 of integer; ready:array0.4 of boolean; i:integer;procedure entry pickup(var me:integer);begin if fork(me)2 then wait(ready(me); forks(right(me):=forks(right(me)-1;右叉子减1 forks(left(me):=forks(left(me)-1;左

31、叉子减1end;procedure entry putdown(var me:integer);begin forks(right(me):=forks(right(me)+1; forks(left(me):=forks(left(me)+1; if forks(right(me)=2 右边符合条件唤醒右边 then signal(ready(right(me); if forks(left(me)=2左边符合条件唤醒左边 then signal(ready(left(me);end；begin for i:=0 to 4 dobegin forks(i):=2;初值是可以吃 right(i

32、):=i+1mod 5;第i位的左、右哲学家号 left(i):=i+4 mod 5; ready(i):=false;end;运行时:cobeginphilosopher 0: process(var HUNGRY:boolean);begin repeat if HUNGRY=true then begin forkscontrol.pickup(0); EATING; forkscontrol.putdown(0);end;THINKING;until false;end;philosopher 2:；philosopher 3:；philosopher 4:；philosopher 5

33、:；coend;232 读者与写者问题(readers-writers problem)一个数据集(如文件或记录)，被几个并发进程共享。通常我们把读进程称为读者，而把要求修改数据的进程称为写者，显然几个读者可以同时读此数据集，不互斥也不会产生问题。例如，设想一个飞机定票系统，大量的订票者要查询共享数据库中有关飞机航班的各种信息，而各个售票台却要试图读写其中的数据。多个进程同时读是可以接受的，但如果一个进程正在更新数据库，则所有的其他进程都不能访问数据库，即使是读操作也不行，它们之间必须互斥，否则将破坏此数据的完整性。1解决此问题的最简单的方法:当没有写者时，读者可以进入访问，否则等待。var

34、rmutex，wmutex:semaphore; readcount:integer;begin rmutex:=1wmutex:=1;readcount:=0;cobegin reader:begin repeat p(rmutex);对readcount互斥修改 if readcount=0 then p(wmutex); readcount:=readcount+1; v(rmutex); 作读操作 p(rmutex);退出读时，互斥地将读者计数减1 readcount:=readcount-1; if readcount=0 then v(wmutex);当没有读者时，可写 v(rmutex);until false;end;writer:begin repeat p(wmutex);