第3章并发进程

第三章并发进程一、概述

为了增强计算机系统处理数据的能力，提高资源的利用率，现代计算机系统采用多道程序设计技术，从而使得若干作业并存于内存中且同时执行。每个作业的操作步骤都是由相应的进程完成的。多个作业同时执行的状态，表现为一个进程的工作还没有全部完成之前，另一个进程就开始工作，把这些可同时进行工作的进程称为“并发进程”。在并发进程的执行过程中，进程同步是操作系统管理共享资源，避免出错的一个有效手段。进程的同步包括进程的同步与进程的互斥两个方面。进程的互斥是指并发进程即多个执行进程，同时竞争共享资源时，若某共享正在被一个进程使用，其他申请该资源的进程必须等待，直至该资源被释放后，另一个进程才能使用该资源。也就是说，共享资源应该互斥的使用。进程的同步是指一个进程的执行依赖于其他进程的执行状况，即并发进程中，一个进程在没有得到其他进程发来的消息时必须等待，直至另一个进程送来消息后才能继续执行。进程的死锁是并发进程之间相互等待对方占有的资源的现象。二、进程间的制约关系

在多道程序系统中，由于资源共享与进程合作，使诸进程之间可能产生两种形式的制约关系：１．间接相互制约

这种制约主要源于资源共享。例如，有两进程Ａ和Ｂ，如果在Ａ进程提出打印请求时，系统已将打印机分配给进程Ｂ，则进程Ａ阻塞；一旦进程Ｂ将打印机释放，也就使进程Ａ由阻塞改为就绪状态。２．直接相互制约

这种制约主要源于进程合作。例如，有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时，计算进程Ｂ因不能获得所需数据而阻塞，当进程A把数据送入缓冲时，便将B唤醒；反之，进程Ａ因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区内数据取走时唤醒A。第三章并发进程

可见，诸进程在并发执行时，必须按照一定的次序执行。进程同步例子：对于共享一个缓冲区的输入进程和计算进程，当输入进程未将数据送入缓冲区时，计算进程不能开动计算；同样，若计算进程未从缓冲区中取走数据时，输入进程不能再启动下一次的输入。输入进程计算进程缓冲区

3.1进程的并发性1、虽然对于一个程序的输入、计算和打印必须顺序执行，但在对一批程序进行处理时，则可使上述三种操作并发执行，以提高系统的吞吐量。例如，输入程序在输入第三个程序（I3）的同时，计算程序可以正在对第二个程序进行计算（C2），而打印程序正在打印第一个程序（Ｐ1）的计算结果。如下图所示：I1I2I3I4C1C2C3C4P1P2P3P4程序段并发执行的有向图

第三章并发进程2、与时间有关的错误例如，某展示厅设置了一个自动计数系统，用一个计数器count指示在场的人数。当有一人进人时，进程pin实现计数加１，当退出一人时，进程POUT实现计数减１。由于人场与退场是随机的，因此，进程pin和pout是并发的。用cobegin和coend表示并发执行，这两个进程的程序如下：begincount:integer;count：=0;cobeginprocesspinR1：integer；beginR1：＝count；R1：=R1＋1；count：=R1；end；processpoutR2：integer；

beginR2：=count；R2：=R2-1；count:＝R2;end;coend;end；

假定某时刻的计数值count=ｎ，这时有一个人要进人，正好另一个人要退出，于是进程pin和pot都要执行。如果进程ｎ和pout的执行都没有被打断过，那么各自完成了count+1和count-1的工作，使计数值保持为ｎ，这是正确的。如果两个进程执行中，由于某种原因进程ＰＩＮ被打断，且进程调度使它们的执行呈下面的次序：占有CPU执行过程进程执行的操作count值pinR1:=countR1:=R1+1npin中断，由pout占用CPU并执行过程R2:=countR2:=R2+1Count:=R2n-1pin继续执行Count:=R1+1n+1按这样的次序执行后，count的最终值不能保持为ｎ，而变成ｎ+1。如果进程被打断的情况如下：占用CPU执行过程进程执行的操作count值pinR1:=countR1:=R1+1npin被打断，pout占用R2:=countR2:=R2+1npout被打断，pin占用count:=R1n+1pin被打断，pout占用count:=R2n-1于是，两个进程执行完后，count的终值为ｎ-1。也就是说，这两个进程的执行次序对结果是有影响的，关键是它们涉及到共享变量count，且两者交替访问了count，在不同的时间里访问count，就可能使count的值不同。所以，造成计数值不正确的因素是与进程被打断的时间和能占用处理的时间有关，由于这种原因造成的错误称为“与时间有关的错误”。3.2进程的互斥与同步一、进程互斥

从上面例子可知：当若干个进程都要使用某一共享资源时，任何时刻最多只允许一个进程使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放了该资源，这就是进程的互斥。具有互斥关系的进程并不是它们的所有操作都要互斥进行，只需要确保涉及共享变量操作的那一段程序实现互斥。通常把这一段程序称为临界区或临界段，进程的互斥实质上就是并发进程对临界区的访问是互斥的。二、临界区（criticalsection）1.临界资源：一次仅允许一个进程使用的资源。

例如，有两个进程共享一个变量count：（R1和R2是处理机中的寄存器）：

当两个进程按下述顺序执行时但若P1和P2按另一种顺序对count进行修改

P1：R1：=count；P1：R1：=count;

R1:=R1+1;P2:R2:=count;

count:=R1;P1:R1:=R1+1;count:=R1;

P2:R2:=count;P2:R2:=R2+1;count:=R2;

R2:=R2+1;虽然P1和P2都各自对count作了加

count:=R2;1操作，但最后的count却只增加了1。亦其结果使count增加了2；即发生了与执行顺序有关的错误。

为了预防这种错误，对变量count应按临界资源处理，即令P1和P2互斥地使用count。

2.

临界区：访问临界资源的那段代码。诸进程在访问临界资源时，必须互斥。我们把每个进程中访问临界资源的那段代码称为临界区。为了实现对临界区的互斥访问，应保证诸进程互斥地进入自己的临界区。为此，每个进程在进入其临界区前，必须先提出申请，经允许后方可进入。若干个并发进程临界区程序的执行准则如下：（1）若干个进程都要求进入临界区访问共享变量时，只允许一人进程进入，其他进程必须等待；（2）任何一个进入临界区的进程必须在有限的时间内退出临界区；（3）当某一进程退出临界区时，若有其他进程等待进入，同必须允许一个进程进入临界区。3、P-V操作20世60年代中期发明的P-V操作能够满足对临界区的管理要求。P-V操作由两个原语：P操作原语与V操作原语组成。P-V操作是一个整型变量上的两个操作，设整型变量S称作信号量或信号灯。通过s的操作，对进程和资源进行管理，从而实现对临界区的互斥访问。（1）P操作：s：=s-1，若s大于等于0，则表示有资源，当前进程继续运行，若s小于0，表示已无资源，则当前进程由执行状态转变为阻塞状态，将其插入到与信号量s有关的等待队列中，直到其他进程在s上执行V操作为止。（2）V操作：s:=s+1，若s大0，则本进程继续执行，若s小于等于0，则从与信号s相关的等待队列中移出列首的进程，将其由阻塞状态转变为就绪状态，插入到就绪队列中，当前进程仍继续执行。利用P-V操作实现互斥：A进程B进程…….……..p(s)p(s)临界区临界区v(s)v(s)…….…….前面例子中的两个并发进程都要使用共享的计数器count，从分析中看到，只有当一个进程不在使用count时另一个进程再去使用，才不会出错．如果它们交叉地使用count则会现与时间有关的锗。为了保证两个进程互斥地使用计数器count，可以用ＰＶ操作来管理。定义一个信号量s的初值为１，把两个并发进程的程序改写成如下：begincount：integer；s：semphorecount:=0；s:=1；cobeginprocesspinR1：integer;beginp(s)；R1：＝count;R1：=R1+1;count：=R1;v(s)end；processpoutR2：integer;beginp(s);R2：＝count；R2：=R2—1;count:=R2；v(s)end；coend；end；这里p操作p(s)限制了一次只有一个进程在临界区执行。如果一个进程在临界区执行时被打断，另一个进程想进入临界区，但由于进人临界区前必须先调用p(s)，而此时已在临界区的进程尚未退出临界区，所以s的值为“０”，想进人临界区的进程调用p(G)的结果必然是等待，直到已进入临界区的进程再次得到处理器执行完临界区中的操作调用v(s)后才结束等待．所以，改写后的程序在执行中即使被打断，也不会出现两个进程交叉访问count，保证了进程互斥地使用共享的计数器。一般说，当ｎ个进程Ｐ1，Ｐ2，…Pn要共享某一资源时，为保证资源的互斥，首先找出ｎ个进程各自的临界区，对每个进程都用ＰＶ操作来实现进入和退出临界，进程Ｐｉ（ｉ=１，２，…ｎ）互斥的一般形式为：begins：semphore；s:=1;cobeginprocessPibeginp(s);临界区v(s);......end；coend;end；processPibeginp(s);临界区v(s);end；coendend；但是，任何粗心地使用PV操作会违反临界区的管理要求．例如对7．2中的第二个例子，用PV操作管理临界区时，若粗心地把程序改写成：

begins：semaphores：=1；cobeginprocessPi（i＝1，2，…n）begin按旅客订票要求找到Aj；p(s)；Ri：=AjifRi＞=lthenbeginRi：=Ri—1;Ai:=Ri；v(s);输出一张票endelse输出“票已售完”end;coend；end进程执行时调用P(S）决定是否能进入临界区，由于S的初值为1，故每次只能有一个进程进入临界区，其它想进入临界区执行的进程必须等待，这符合临界区管理的第一个要求。但在改写的程序中忽略了当条件Ri＞=1不成立时执行else部分的V操作，以致使进程在临界区中判到条件Ri＞=1不成立时无法退出临界区，当然也就不能释放等待进入临界区的进程，造成进程无限地等待进入临界区，这就违反了对临界区管理的第二、第三的两个要求。正确的做法应该是；beginS：semphore；S：＝1；cobeginprocessPi(0，1,2,…,n）begin按旅客订票要求找到Aj；p(s)；Ri:=Aj；ifRi>=1thenbeginRi：=Ri－1，Aj：=Ri；v(s)；输出一张票endelsebeginv(s);输出“票已售完”……2、P-V操作实现同步进程的同步是并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到这才被唤醒。先看一个例子。设有两个进程A和B，它们共享一个缓冲器，进程A不断地读人记录并送到缓冲器，进程B不断地从缓冲器中取出记录并加工。假定缓冲器的容量为每次只能存放一个记录，于是正确的工作应该是这样的：进程A把一个记录送人缓冲器后．应等到进程B发来消息（已将缓冲器的记录取走）才能把下一个送入缓冲器。进程B也应等到进程A发来消息（缓冲器中已送入一个记录），才能从缓冲器中取出记录并加工。如果这两个进程不是相互制约的话，那么可能出现：进程A又向缓冲器送入一个新记录而把上一个尚未取走的记录覆盖了；进程B在下一个记录送入缓冲器之前又去取缓冲器中的记录，造成重复地取同一个记录加工。PV操作不仅可以用来实现互斥进入临界区而且还是一个简单而又方便的同步工具，用它来解决生产者/消费者问题，可以防止生产者把物品放入已经装有物品的缓冲器中，也可防止消费者在物品存入缓冲器之前去取物品，现在假定有一个生产者和一个消费者，它们公用一个缓冲器，生产者不断地生产物品，每生产一件物品就要存入缓冲器，但缓冲器中每次只能存入一件物品，只有当消费者把物品取走后，生产者才能把第二件物品存入缓冲器，同样地，消费者要不断地取出物品去消费，，当缓冲器中有物品进他就可去取，每取走一件物品后必须等生产者放入一件物品才可再取，用PV操作实现生产者/消费者之间的同步，可以定义两个信号量：

SP：表示是否可以把物品存入缓冲器，由于缓冲器中只能放一件物品，所以SP的初值取为“1”。SG；表示缓冲器中是否存有物品，显然，它的初值应该为“0”，表示还没有物品。对生产者来说，生产一件物品后应调用P（SP），当缓冲器中无物品时（这时SP=1）则调用p（SP）后不会成为等待状态，可继续执行，把物品存入缓冲器。调用一次P（SP）后，SP=0，若消费者尚未取走物品，而生产者又生产了一件物品欲存入缓冲器，这时调用P（SP）将使生产者处于等待状态而阻止它把物品再存人缓冲器。当在缓冲器存人一件物品后，应调用V（SG），告诉消费者缓冲器中已经有一件物品了（调用V（SG）后，SG的值从“0”变为“l”）。对消费者来说，取物品前应查看缓冲器中是否有物品，即调用P（SG）。当无物品时，由于SG＝0，调用p（SG）后消费者等待，不能去取物品；当有物品时，由于SG=1调用P(SG)后消费者可继续执行去取物品。每取走一件物品后，应调用V（SP），通知生产看缓冲器中物品已取走，可以存入一件新的物品。生产者和消费者并发执行时，可按如下方式同步：beginBuffer：integer；SP，SG：semaphore；Sp：=1；SG：=0;cobeginprocessproducerbeginL1：produceaproduct；P（SP）；Buffer：＝product；v（SG）;gotoL1endbeginL2：P（SG）；takeaproductV（SP）；consume；gotoL2end;coend；end；

如果一个生产者和一个消费者他们共享的缓冲器容量为可以存放n件物品，那么只要把信号量SP的初值定为n。当缓冲器中没有放满n件物品时，生产者调用P（SP）都不会成为等待状态而可把物品存人缓冲器。但当缓冲器中已经有n件物品，生产者想再存入一件物品将被拒绝。每存人一件物品后，由于调用V（SG），故SG的值表示缓冲器中可用的物品数，只要SG40，消费者调用P（SG）后总可去取物品。每取走一件物品后，由于调用V（SP），便增加了一个可用来存放物品的位置。用指针k和t分别指示生产者往缓冲器存物品和消费者从缓冲器中取物品的相对位置，它们的初值为“0”，那么，一个生产者和一个消费者共用容量为n的缓冲器时，可如下同步工作：beginB：array［0...n—1]ofInteger；k，t：integer;Sp，SG：Semphore；K：=t:=0;SP：＝n；SG：＝0；cobeginprocessproducerbeginL1：produceaproduct；P(SP)；B[K］：=product;k：=（k+1）modn;

v（SG）;gotoL1endprocessconsumerbeginL1：P（SG）；takeaproductfromB[t];t：＝（t＋1）modn；V（SP）；consumegotoL2end；coend；end；3.3进程通信一、

低级和高级进程通信方式

虽然一个作业可分为若干个能并发执行的进程，但它们应经常保持联系，以便协调一致地完成指定任务。这种联系是指在进程之间交换一定数量的信息。信息量可多可少，多是指能交换成千个数据，少则仅是一个状态或数值。显然，进程同步是一种简单通信方式，进程通过修改信号量，可向另一进程表明临界资源是否可用。在生产者－消费者问题中，可由生产者进程向消费者进程传送一批消息，或者说，生产者通过缓冲池与消费者通信。应当指出，信号量机制作为同步工具是卓有成效的，但作为通信工具则不够理想，因为其效率甚低，因此，称为低级通信方式。

1、低级进程通信

进程的互斥和同步可归结为低级进程通信。在进程互斥中进程通过修改信号量，向其他进程表明临界资源是否可用；在生产者－消费者问题中，生产者通过缓冲池与消费者通信。应当指出，信号量机制作为同步工具是卓有成效的，但作为通信工具则不够理想，主要表现在：

（１）效率低生产者每次只能向缓冲区中投放一个消息，消费者每次只能从缓冲区中取得一个消息；

（２）通信对用户不透明即设置共享数据结构，数据的传送、进程的互斥与同步都是由程序员去实现，操作系统只提供共享存储器。

简言之，这种通信方式的效率低，不方便，故只适用于传送少量信息的情况。

2.

高级进程通信

以较高的效率传送大量数据的一种通信方式。高级通信的目的不是为了控制进程的执行速度，而是为了交换信息。在这种通信方式中，程序员可直接利用系统提供的一组通信命令（通信原语），高效地传送大量数据，操作系统隐藏了实现通信的细节，这大大简化了通信程序编制上的复杂性。高级通信原语不仅保证相互制约的进程之间的正确关系，还同时实现了进程之间的信息交换。目前常用的高级通信机构有消息缓冲通信、管道通信和信箱通信。二、进程通信的类型(１）消息缓冲通信消息缓冲通信方式也称为直接通信方式，即一个进程直接发送一个消息给接收进程。所谓消息