操作系统2002-进程同步与互斥

进程同步与互斥一、进程的并发性二、进程的互斥三、进程的同步四、同步与互斥的混合问题一、进程的并发性

程序并行性的表示：CobeginS1；S2；…；SnCoend

在多道系统中，假如有两个进程A和B，它们要求顺序执行的操作如下：进程A：a1,a2,a3,a4,…,an进程B：b1,b2,b3,b4,…,bm这两个进程是在处理器上交替执行的，可能出现的执行序列有：a1,b1,a2,b2,…和a1,a2,b1,b2,…,等等，它们的执行在时间上是重叠的，这被称为“可同时执行的”。在多道程序环境下，进程之间存在以下关系资源共享关系相互合作关系观察者beginL：observealorry；count:=count+1；gotoLend；报告者beginprintcount；count:=0；end；样例1：假定某一时刻，观察者已记录了N辆车，又在记录下一辆车，此时，报告者也开始工作。与时间有关的错误执行顺序1：（观察者）count:=count+1;（报告者）report;（报告者）count:=0;这是正确的结果。执行顺序2：（报告者）reportcount;（观察者）count:=count+1;（报告者）count:=0;观察者刚刚记录的一辆车的信息丢失了

造成不正确的因素是与进程占用处理器的时间、执行的速度以及外界的影响有关。这些因素都与时间有关，所以，称它们为“与时间有关的错误”样例2：飞机航班有N个售票处，每个售票处通过终端访问系统的公共数据区。

售票处1begin从数据单元中取出现有余票；做减1操作；把结果送回到数据单元end;售票处2begin从数据单元中取出现有余票；做减1操作；把结果送回到数据单元end;假定现有余票为1执行顺序：（售票处1）从数据单元中取出现有余票；（售票处2）从数据单元中取出现有余票；（售票处1）做减1操作；（售票处1）把结果送回到数据单元；（售票处2）做减1操作；（售票处2）把结果送回到数据单元；结果是把一张票卖给了两个顾客。

与时间有关的错误产生的原因：多个进程不受限制的对同一数据对象进行存取操作。二、进程的互斥

有共享资源的进程执行时出现与时间有关的错误，其根本原因是对共享资源的使用不受限制。进程交叉使用了共享资源从而造成了错误。几个基本概念

1、临界资源一次仅允许一个进程访问的资源被称为临界资源

2、临界区临界区的定义：把在进程中那段访问临界区的代码称为临界区。对临界区管理的要求：一次最多让一个进程进入临界区任何一个进入临界区的进程必须在一个有限的时间内退出临界区。若有多个进程同时要求进入它们的临界区，则应在有限的时间内让其中之一进入。处理临界区的原则：1、当无进程处于临界区时，允许一进程立即进入临界区2、当某一进程已进入临界区时，其它试图进入临界区进程必须等待3、当某已进程离开临界区时，若有进程等待，则允许其中之一进入临界区4、当进程不能进入临界区时，应立即释放处理机，避免忙等。对临界资源同时提出访问请求的诸进程的执行要加以限制，以防止上述“与时间有关的错误”。这种对临界资源的排它访问称为互斥。

早期的研究结果表明，互斥问题的解决并不是一件很简单的事情。解决互斥问题的软件方法假设有两个进程Pi和Pj，共享一个临界资源R。方法一：设置一公用整型变量turn，用于指示被允许进入临界区的进程的编号。repeatwhiletern<>idonoop;进入临界区turn=j;untilfalse;repeatwhiletern<>jdonoop;进入临界区turn=i;untilfalse;该方法可以确保每次只允许一个进程进入临界区，但不符合处理临界区的原则1，易造成资源利用不充分。方法二：基本思想：在每一个进程访问临界资源之前，先查看一下临界资源是否正被访问。若正被访问，则进程等待；否则进入自己的临界区。为此，设置一个数组flag，每个元素的初值为false，表示进程未进入临界区，进程进入临界区后，相应标志位置为true。repeatwhileflag[j]donoop;flag[i]=true；进入临界区flag[i]=false;untilfalse;repeatwhileflag[i]donoop;flag[j]=true；进入临界区flag[j]=false;untilfalse;方法二可以满足原则1，但又出现了新的问题。比如，当Pi和Pj几乎在同时都要求进入临界区，因而都发现对方的访问标志为false，于是两进程都先后进入临界区，显然，这不符合临界区处理的原则2。为了解决这个问题，把标志位的含义改变为：true表示进程希望进入临界区，即当进程要进入临界区前，先将标志位flag置为true，表示进程已要求进入临界区，然后再去查看另一进程的标志，若另一进程的flag标志也为true，则本进程等待，否则，本进程进入临界区。换句话说，进程要进入临界区，首先设置其要求进入的标志，然后，再去查看其他进程的标志。方法三：repeatflag[i]=true；whileflag[j]donoop;进入临界区flag[i]=false;untilfalse;repeatflag[j]=true；whileflag[i]donoop;进入临界区flag[j]=false;untilfalse;该方法可以有效地防止两个进程同时进入临界区，但仔细分析又可看出，该方法可能会造成两个进程都不能进入临界区的后果。例如，当两个进程同时要求进入临界区，分别将自己的标志位置为true，再去查看另一进程的标志，发现也为true，于是都等待，谁也无法进入临界区。方法四：repeatflag[i]=true；turn=j;while[flag[j]andturn=jdonoop;进入临界区flag[i]=false;untilfalse;假如进程Pi和Pj几乎同时要求进入临界区，它们分别将flag[i}]和flag[j]置为true。Pi先将turn置为j，当它执行while语句时，条件成立，故等待。但Pj会立即将turn置为i，这样Pi就可以进入临界区。Pi退出临界区时会将flag[i]置为false，从而可以使Pj进入临界区。利用软件方法解决互斥问题有一定难度，在使用同一资源的进程数量较大时，有很大的局限性。另外一种解决互斥问题的方法是锁机制。为临界资源设置一个锁w，当进程在进入临界区之前，首先测试w的状态。w等于1表示上锁，该资源已被占用；w等于0表示开锁，该资源已空闲，未被占用。Lockw:L:ifw=1thengotoLelsew:=1Unlockw:w:=0;软件的解决方法四和锁机制虽然可以在一定程度上解决互斥问题，但进程在等待时都需要不停地进行测试。这不满足处理临界区的原则4，降低了系统工作效率。信号量同步机制

一个信号量可以看成由两个部分组成：一个是整型变量，另一个是队列。整型变量队列ProcedureP(VarS:Semaphore)beginS:=S–1;ifS<0thenW(S)end;ProcedureV(VarS:Semaphore)beginS:=S+1;ifS<=0thenR(S)end;P、V操作是原语操作，即它们的执行是不可中断的。

相应地，信号量的P、V操作可以被描述如下：W(S)：将当前进程挂起在信号量等待队列上R(S)：从信号量等待队列上唤醒一个等待进程临界区的管理一般形式：

进程Abegin…P（S）;临界区；V（S）…end;进程Bbegin…P（S）;临界区；V（S）…end;P、V操作必须合理使用，否则可能造成由于交叉使用资源而引发的错误。用P、V操作实现进程的互斥①用P、V操作实现车辆观察系统的互斥将S定义为一个信号量，初值为1ProcessObserverbeginL:observealorry;P(S);count:=count+1;V(S);gotoLend;ProcessReportbeginP(S);printcount;count:=0;V(S)end;错误方式1：ProcessObserverbeginL:P(S);

observealorry;count:=count+1;V(S);gotoLend;降低了进程的并发程度错误方式2：ProcessObserverbeginL:observealorry;P(S);count:=count+1;

gotoL；V(S)end;将造成系统瘫痪。②用P、V操作实现售票系统的互斥

将S定义为信号量，初值为1，余票的数量值放在整型变量A中。PROCESSPir:integer;beginP(S);r:=A;ifr>=1thenbeginr:=r–1;A:=r;V(S);{售出一张票};endelse{售出票已售完};end；PROCESSPir:integer;beginP(S);r:=A;ifr>=1thenbeginr:=r–1;A:=r;V(S);{售出一张票};endelsebeginV(S);{售出票已售完}endend；无法退出临界区③读者写者问题：规定：允许多个进程同时读；只允许一个进程写；当有进程读时不允许其它进程写。第一种方案：定义信号量：S:semaphore；初值1；定义一个整数：rs，初值0；

读者：PROCESSReaderibeginrs:=rs+1;ifrs=1thenP(S);readfileF;rs:=rs–1;ifrs=0thenV(S);end;写者：PROCESSWriterjbeginP(S);writefileF;V(S);end;问题：对共享变量rs访问的程序段也是临界区。

改进的方案：定义信号量：S,Sr:semaphore；分别为互斥访问文件和计数变量的信号量，初值均为1；定义一个整数：rs，初值0；读者：PROCESSReaderbeginP(Sr);rs:=rs+1;ifrs=1thenP(S);V(Sr);readfileF;P(Sr);rs:=rs–1;ifrs=0thenV(S);V(Sr);end;写者：PROCESSWriterbeginP(S);writefileF;V(S);end;例题：试用P、V操作写出读者优先的同步算法。解答：定义两个变量RC和WC，分别用于对进入临界区的读者和写者进程计数。为了互斥的操作这两个变量，需设置两个相应的信号量RCS和WCS。为了使读者-写者之间和写者-写者之间互斥的访问缓冲区，设置信号量S。为了阻止读者进程和链接等待的写者进程，设置信号量W。为了链接等待的读者进程，设置信号量R。这样，当有第一个写者进程进入临界区后，所有的试图进入临界区的读者进程将被阻塞在信号量R上，而写者进程将优先进入临界区。读者：PROCESSReaderbeginP(R);P(W);P(RCS);ifRC=0thenP(S);RC:=RC+1;V(RCS);V(W);V(R);readfileF;P(RCS);RC:=RC–1;ifRC=0thenV(S);V(RCS);end;写者：PROCESSWriterbeginP(WCS);ifWC:=0thenP(W);WC:=WC+1;V(WCS);P(S);writefileF;V(S);P(WCS);WC:=WC–1;ifWC=0thenV(W);V(WCS);end;R:=W:=RCS:=WCS:=S:=1;RC:=WC:=0;例题：举例说明P、V操作为什么要被设计成原语（即对同一信号量上的操作必须互斥）。解答：对于P操作，过程为：ProcedureP(VarS:Semaphore)beginS:=S–1;ifS<0thenW(S)end;假如有两个进程P1、P2几乎在同时作P操作，信号量S的初值为1。如果进程P1先作P操作，则S的值为0，P1进程不应被阻塞（或挂起）。但是，如果P操作不是原语操作，则可能有如下执行顺序：P1：S:=S-1P2：S:=S-1P1：ifS<0thenW(S)由于此时S为–1，P1将被阻塞，这样，P操作就不符合原来的语义了。同样，对于V操作，过程为：ProcedureV(VarS:Semaphore)beginS:=S+1;ifS<=0thenR(S)end;假如有两个进程P1、P2几乎在同时作V操作，信号量S的初值为-1。如果进程P1先作V操作，则S的值为0，该V操作应该唤醒一个被P操作阻塞的进程。但是，如果V操作不是原语操作，则可能有如下执行顺序：P1：S:=S+1P2：S:=S+1P1：ifS<=0thenR(S)由于此时S为1，P1所作的V操作将不再去唤醒被阻塞的进程，这样，V操作就不符合原来的语义了。

另外，如果在P操作过程中插入了V操作，也会出现不符合语义的情况。例如，假定S的值为0，按照P操作的语义，作P操作的进程应该被阻塞，但是，如果有如下执行顺序：A进程的P操作语句：S:=S-1B进程的V操作语句：S:=S+1A进程的P操作语句：ifS<0thenW(S)

则作P操作的进程将不会被阻塞，这不符合语义。三、进程的同步

协作

buffer1buffer2输入设备打印设备输入进程计算进程打印进程P1P2P3这里，计算进程C和打印进程P的工作必须相互协作：计算进程只有在缓冲区中无数据时才能向其写入数据；打印进程只有在缓冲区中已有数据时才能将从中取出并打印。两个进程应做如下协作1、进程C把一个记录存入缓冲区后，应向进程P发送“缓冲区中有等待处理的记录”的消息；2、进程P从缓冲区取出记录后，应向进程C发送“缓冲区中的记录已取走”的消息；3、进程C只有在得到进程P发送来的“缓冲区中的记录已取走”的消息后，才能把下一个记录存入缓冲区，否则，进程C等待，直到消息到达；4、进程P只有在得到进程C发送来的“缓冲区中有等待处理的记录”的消息后，才能从缓冲区取出记录，否则，进程P等待，直到消息到达。buffer1buffer2输入设备打印设备输入进程计算进程打印进程P1P2P3PROCESScalculatorbeginL1:P(SB);计算下一个数据并送入缓冲区;V(SA);gotoL1;end;PROCESSprinterbeginL2:P(SA);从缓冲区中取出数据并打印;V(SB);gotoL2;end;同步机制调用P操作测试消息是否到达调用V操作发送消息生产者-消费者问题简单的生产者、消费者问题（单缓冲区）定义：整型变量：Buffer，信号量：SP=1,SG=0

PROCESSProducerbeginL1:produceaproduct;P(SP);Buffer:=product;V(SG);gotoL1endPROCESSConsumerbeginL2:P(SG);TakeaproductformBuffer;V(SP);gotoL2end多缓冲区生产者、消费者问题PROCESSProducerbeginL1:produceaproduct;P(SP);B[k]:=product;k:=(k+1)modn;V(SG);gotoL1endPROCESSConsumerbeginL2:P(SG);TakeaproductformB[t];t:=(t+1)modnV(SP);consumer;gotoL2end定义：整型变量：k=0,t=0整型数组：B[0…n-1]信号量：SP=n,SG=0例子：三个进程R、W1、W2，共享一个缓冲区B，B中最多只能存放一个数。进程R负责不断地向B中存入整数，进程W1、W2分别负责取出B中的奇数和偶数并进行打印。PROCESSRx:integer;beginL1:{从输入设备中读入一个数};x:=读入的数；P(S);B:=x;ifB=奇数thenV(SO)elseV(SE)gotoL1;endPROCESSW1y:integer;beginL2:P(SO);y:=B；V(S);{打印y中数}；gotoL2;endPROCESSW2z:integer;beginL3:P(SE);z:=B；V(S);{打印z中数}；gotoL3;end定义信号量：S初值为1表示初始时缓冲区可用SO初值为0用于向打印奇数的进程发消息SE初值为0用于向打印偶数的进程发消息四、同步与互斥的混合问题

例子：有m个生产者和r个消费者共享容量为n的缓冲器（m、r、n均大于1）。每个生产者把自己生产的物品存入缓冲区，每个消费者从缓冲区中取出物品去消费。要求用P、V操作对这些生产者和消费者进行正确管理。定义：整型数组：B[0…n-1]整型变量：k，t初值均为0信号量：S1：初值1用于生产者放入物品S2：初值1用于消费者取出物品SP：初值n缓冲区是否可用SG：初值0缓冲区里是否有物品PROCESSPibeginL1:produceaproduct;P(SP);P(S1);B[k]:=product;k:=(k+1)modn;V(S1);V(SG);gotoL1endPROCESSCjbeginL2:P(SG);P(S2);takeaproductfromB[t];t:=(t+1)modn;V(S2);V(SP);consume;gotoL1end生产者分别向缓冲区送产品，由S1控制互斥访问。消费者分别从缓冲区中取出产品，由S2控制互斥访问。例子：现有四个进程R1、R2、W1、W2，它们共享一个可以存放一个数的缓冲器B，R1、R2从键盘和磁盘上读入数据，放到缓冲器B中，W1、W2从缓冲器中分别读取R1，R2写入的数据并输出打印。怎样用P、V操作来协调四个进程的并发执行？定义：信号量S初值为1用于写入进程的互斥S1初值为0R1向W1发送消息S2初值为0R2向W2发送消息整型变量BPROCESSR1x:integerbeginL1:{接受来自键盘的数}；x:=接受的数;P(S);B:=x;V(S1);gotoL1endPROCESSR2y:integerbeginL2:{从磁盘上读一个数}；y:=读入的数;P(S);B:=y;V(S2);gotoL2endPROCESSW1k:integerbeginL4:P(S1);k:=B;V(S);{打印k中的数}；gotoL3endPROCESSW2j:integerbeginL4:P(S2);j:=B;V(S);{打印k中的数}；gotoL3end例题：假定一个阅览室最多可以同时容纳100个人阅读，，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记或去掉登记。试用P、V操作编写读者进程的同步算法。分析：设读者有任意多个，但能同时阅览的只能100人，所以，设一个信号量S代表空座位数目，初值为100，用它来控制进入阅览室的读者进程不超过100。另设信号量m，用于控制对登记表这一共享资源的互斥使用，其初值为1。Process第i个读者进程beginP(S);P(m);填写登记表；V(m);坐下阅览;P(m);在登记表上去掉登记；V(m);V(S);gotoL1;end例题：有一个仓库存放两种零件A和B，最大库容量各为M个。有一车间不断的取A和B进行装配，每次各取一个。有两组供应商分别不断的供应A和B（每次供应一个）。为保证配套和合理库存，当某种零件的数量比另一种的数量超过n（n<M）个时，暂停对数量大的零件的进货，只补充数量少的零件。试用P、V操作正确地实现之。分析：这里除了生产者-消费者这一对控制关系外，还增加了生产者之间的相互制约关系。这种相互制约关系需要另外设置信号量来实现。解答：信号量初值S1实现存取零件的互斥aval_am零件A的库存容量aval_bm零件B的库存容量full_a0零件A的可用数量full_b0零件B的可用数量san控制零件B是否超过零件An个sbn控制零件A是否超过零件Bn个A零件供应商的进程B零件供应商的进程生产车间的进程beginL1:P(aval_a);P(sa);P(S);storeA;V(full_a);V(sb);V(S);gotoL1:endbeginL2:P(aval_b);P(sb);P(S);storeB;V(full_b);V(sa);V(S);gotoL2:endbeginL3:P(full_a);P(full_b);P(S);takeAandB;V(aval_a);V(aval_b);V(S);gotoL3:end例题：当进程X和进程Y共享某个资源r，进程并发执行时的程序如下(信号量S的初值为1)：请回答：1、两个进程并发执行时，能否保证互斥使用资源，为什么？2、如果要使两个进程交替使用资源，若仍使用P、V操作来进行管理，写出应定义的信号量及其初值；3、修改上述程序，使两个进程能交替使用资源；ProcessXbeginL1:P(S);使用资源r;V(S);gotoL1;endProcessYbeginL2:P(S);使用资源r;V(S);gotoL2;end1、能保证互斥使用资源。因为在两个进程中“使用资源r”都作为临界区，由P(S)和V(S)操作保证了互斥执行，S的初值定义为1，符合要求；2、要使两个进程交替使用资源，仅仅保证互斥使用资源是不够的，必须使两个进程互相等待、互相通知。为此，必须定义新的信号量来实现进程的同步通信。这里定义信号量S1和S2，假定进程X先使用资源，那么S1的初值定义为1，S2的初值定义为0。S1和S2的使用可以保证互斥，所以原来的信号量S可以不要；3、两个进程可以改写为：ProcessXbeginL1:P(S1);使用资源r;V(S2);gotoL1;endProcessYbeginL2:P(S2);使用资源r;V(S1);gotoL2;endS1:semaphore:=1;S2:semaphore:=0;例题：假定三个进程间的同步算法如下，其中S1、S2、S3的初值都是1。问：算法在什么情况下会发生死锁。ProcessAbeginP(S1);P(S2);......V(S2);V(S1);endProcessBbeginP(S2);P(S3);......V(S3);V(S2);endProcessCbeginP(S3);P(S1);......V(S1);V(S3);end假定出现了如下的进程执行顺序：进程A执行P(S1)，进程B执行P(S2)，进程C执行P(S3)，进程A执行P(S2)，进程B执行P(S3)，进程C执行P(S1)，即A、B、C都在试图执行各自第二个P操作。此时，A阻塞在S2，B阻塞在S3，C阻塞在S1，它们都等待其它进程释放相应的信号量，处于相互等待和循环等待的状态，此时就是死锁。其它控制同步与互斥的机制1、信号量集在某些应用场合，一个进程可能要访问多个临界资源，比如同时申请输入和打印设备。相应的描述如下：ProcessAbeginP(Si);P(So);......V(Si);V(So);endProcessBbeginP(So);P(Si);......V(So);V(Si);end仔细分析一下可以看出，这样互斥使用临界资源可能造成死锁。另外，在前述的信号量机制中，P、V操作仅能对信号量施以加1或减1操作，即每次只能获得或释放一个单位的临界资源。当一次需要N个某类资源时，便需要进行N次操作。显然这是低效的。信号量集机制的基本思想是：将进程在整个运行过程中所需要的所有临界资源一次性地全部分配给进程，待该进程使用完后一次性的释放。亦即，对若干个临界资源的分配，采取原子操作方式。所谓“and信号量集”的思想是：将进程所需要的所有临界共享资源一次全部分配给它，待其使用完后再一起释放。只要有一个资源不能获得，其他资源也都不分配给它。这种同步机制称为“同时P操作”（SP）同时P操作定义如下：ProcedureSP(S1,…，Sn)Beginif(S1>=1and...andSn>=1)fori:=1tondoSi:=Si–1;else将当前执行进程插入到Si的等待队列，Si是第一个满足Si<1的信号量，程序计数器设为P操作的开始；end;同时V操作定义如下：ProcedureV(S1,...,Sn)beginfori:=1tondoSi:=Si+1;唤醒Si等待队列上的所有等待进程，将它们插入到就绪队列中。end;采用同步信号量集描述同时申请输入和打印设备的进程如下：ProcessAbeginSP(Si，So);......SV(Si，So);endProcessBbeginSP(So，Si);......SV(So，Si);end

此外，在有些情况下，当资源数量低于某一下限值时，便不予分配。因而在每次分配前都必须测试资源的数量是否满足要求。基于上述两点，可以对信号量机制作进一步扩充，形成一般的信号量集机制。满足最低要求的资源数量为ti，请求分配的资源数量为di。ProcedureP(S1,t1,d1,...,Sn,tn,dn)beginif(S1>=t1and...andSn>=tn)fori:=1tondoSi:=Si–di;else将当前执行进程插入到Si的等待队列，Si是第一个满足Si<ti的信号量，程序计数器设为P操作的开始；end;ProcedureV(S1,d1,...,Sn,dn)beginfori:=1tondoSi:=Si+di;唤醒Si等待队列上的所有等待进程，将它们插入到就绪队列中。end;信号量集几种特殊情况的讨论：(1)P(S,d,d)，此时在信号量集中只有一个信号量，但它允许每次申请d个资源，当现有资源数少于d时，不予分配；(2)P(S,1,1)，此时的信号量集已蜕化为一般的信号量（S>1）或互斥信号量（S=1）;(3)P(S,1,0)，这是一种很特殊且很有用的信号量。当S>=1时，允许多个进程进入某特定区，当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。2、管程信号量机制的一个特点是：在每个并发进程中都要设置大量的同步操作原语，同步控制部分分散在各个进程中。这不仅给编程带来了麻烦，而且如果P、V操作不当还可能会导致数据的不确定性和系统的死锁。Dijkstra认为应把各进程中与同一共享数据有关的同步控制和同步处理集中起来，构成独立于进程的实体。系统中的各种硬件资源和软件资源均可用数据结构抽象地描述，既用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。当共享资源用共享数据来表示时，资源管理程序可以用对该数据结构进行操作的一组过程来表示。我们把这样一组相关的数据结构和过程称为管程。Hansen为管程下的定义是：一个管程定义了一个数据结构和能为并发进程所执行的（在该数据结构上的）一组操作，这种操作能同步进程和改变管程中的数据。管程的组成：局部于管程的共享数据说明对该数据结构进行操作的一组过程对局部于管程的数据的初始化语句在管程的实现中必须考虑：互斥：当几个进程调用管程时，仅允许一个进程进入管程，其它调用者必须等待。同步：在管程中必须设置两个同步操作原语wait和signal。当进程通过管程请求访问某共享数据而未能满足时，管程便调用wait原语使该进程等待，并将它排在等待队列上。仅当另一进程访