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

1、一、进程的并发性 二、进程的互斥三、进程的同步四、同步与互斥的混合问题一、进程的并发性一、进程的并发性 程序并行性的表示：程序并行性的表示：Cobegin S1；S2；SnCoend 在多道系统中，假如有两个进程在多道系统中，假如有两个进程A A和和B B，它们要求顺序执行的操，它们要求顺序执行的操作如下：作如下： 进程进程A A：a a1 1,a,a2 2,a,a3 3,a,a4 4,a,an n 进程进程B B：b b1 1,b,b2 2,b,b3 3,b,b4 4,b,bm m这两个进程是在处理器上交替执行的，可能出现的执行序列有：这两个进程是在处理器上交替执行的，可能出现的执行序列有：

2、a a1 1,b,b1 1,a,a2 2,b,b2 2,和和a a1 1,a,a2 2,b,b1 1,b,b2 2,等等，它们的执行在时间上是重叠等等，它们的执行在时间上是重叠的，这被称为的，这被称为“可同时执行的可同时执行的”。 在多道程序环境下，进程之间存在以下关系在多道程序环境下，进程之间存在以下关系q 资源共享关系资源共享关系q 相互合作关系相互合作关系 观察者观察者begin L：observe a lorry； count := count +1； goto Lend；报告者报告者begin print count； count := 0；end；样例样例1 1：假定某一时刻，观察

3、者已记录了：假定某一时刻，观察者已记录了N N辆车，又辆车，又在记录下一辆车，此时，报告者也开始工作。在记录下一辆车，此时，报告者也开始工作。 与时间有关的错误与时间有关的错误执行顺序执行顺序1 1：（观察者）（观察者）count := count + 1;count := count + 1;（报告者）（报告者）report;report;（报告者）（报告者）count := 0;count := 0;这是正确的结果。这是正确的结果。 执行顺序执行顺序2 2：（报告者）（报告者）report count;report count;（观察者）（观察者）count := count +1;cou

4、nt := count +1;（报告者）（报告者）count := 0;count := 0;观察者刚刚记录的一辆车的信息丢失了观察者刚刚记录的一辆车的信息丢失了 造成不正确的因素是与进程占用处理器的时间、造成不正确的因素是与进程占用处理器的时间、执行的速度以及外界的影响有关。这些因素都与时间执行的速度以及外界的影响有关。这些因素都与时间有关，所以，称它们为有关，所以，称它们为“与时间有关的错误与时间有关的错误”样例样例2 2：飞机航班有：飞机航班有N N个售票处，每个售票个售票处，每个售票处通过终端访问系统的公共数据区。处通过终端访问系统的公共数据区。 售票处售票处1begin 从数据单元中

5、取出现从数据单元中取出现 有余票；有余票； 做减做减1操作；操作； 把结果送回到数据单元把结果送回到数据单元end;售票处售票处2begin 从数据单元中取出现从数据单元中取出现 有余票；有余票； 做减做减1操作；操作； 把结果送回到数据单元把结果送回到数据单元end;假定现有余票为假定现有余票为1 1执行顺序：执行顺序：（售票处（售票处1 1）从数据单元中取出现有余票；）从数据单元中取出现有余票；（售票处（售票处2 2）从数据单元中取出现有余票；）从数据单元中取出现有余票；（售票处（售票处1 1）做减）做减1 1操作；操作；（售票处（售票处1 1）把结果送回到数据单元；）把结果送回到数据单元

6、；（售票处（售票处2 2）做减）做减1 1操作；操作；（售票处（售票处2 2）把结果送回到数据单元；）把结果送回到数据单元；结果是把一张票卖给了两个顾客。结果是把一张票卖给了两个顾客。 与时间有关的错误产生的原因：多个进程与时间有关的错误产生的原因：多个进程不受限制的对同一数据对象进行存取操作。不受限制的对同一数据对象进行存取操作。 二、进程的互斥二、进程的互斥 有共享资源的进程执行时出现与时间有关的错误，有共享资源的进程执行时出现与时间有关的错误，其根本原因是对共享资源的使用不受限制。进程交叉其根本原因是对共享资源的使用不受限制。进程交叉使用了共享资源从而造成了错误。使用了共享资源从而造成了

7、错误。 几个基本概念几个基本概念 1 1、临界资源临界资源 一次仅允许一个进程访问的资源被称为一次仅允许一个进程访问的资源被称为 临界资源临界资源 2 2、临界区临界区 临界区的定义：把在进程中那段访问临临界区的定义：把在进程中那段访问临 界区的代码称为临界区。界区的代码称为临界区。 对临界区管理的要求：对临界区管理的要求： 一次最多让一个进程进入临界区一次最多让一个进程进入临界区 任何一个进入临界区的进程必须在一个有限的时间任何一个进入临界区的进程必须在一个有限的时间 内退出临界区。内退出临界区。 若有多个进程同时要求进入它们的临界区，则应在若有多个进程同时要求进入它们的临界区，则应在 有限

8、的时间内让其中之一进入。有限的时间内让其中之一进入。处理临界区的原则：处理临界区的原则：1、当无进程处于临界区时，允许一进程立即进入临界区、当无进程处于临界区时，允许一进程立即进入临界区2、当某一进程已进入临界区时，其它试图进入临界区进、当某一进程已进入临界区时，其它试图进入临界区进 程必须等待程必须等待3、当某已进程离开临界区时，若有进程等待，则允许其、当某已进程离开临界区时，若有进程等待，则允许其 中之一进入临界区中之一进入临界区4、当进程不能进入临界区时，应立即释放处理机，避免、当进程不能进入临界区时，应立即释放处理机，避免 忙等。忙等。 对临界资源同时提出访问请求的诸进程的执行要加对临

9、界资源同时提出访问请求的诸进程的执行要加以限制，以防止上述以限制，以防止上述“与时间有关的错误与时间有关的错误”。这种对临。这种对临界资源的排它访问称为互斥。界资源的排它访问称为互斥。 早期的研究结果表明，互斥问题的解决并不是一件早期的研究结果表明，互斥问题的解决并不是一件很简单的事情。很简单的事情。解决互斥问题的软件方法解决互斥问题的软件方法假设有两个进程假设有两个进程P Pi i和和P Pj j，共享一个临界资源，共享一个临界资源R R。方法一：方法一： 设置一公用整型变量设置一公用整型变量turnturn，用于指示被允许进入，用于指示被允许进入临界区的进程的编号。临界区的进程的编号。re

10、peat while tern i do no op; 进入临界区进入临界区 turn = j;until false;repeat while tern j do no op; 进入临界区进入临界区 turn = i;until false; 该方法可以确保每次只允许一个进程进入临界该方法可以确保每次只允许一个进程进入临界区，但不符合处理临界区的原则区，但不符合处理临界区的原则1 1，易造成资源利用，易造成资源利用不充分。不充分。方法二：方法二： 基本思想：在每一个进程访问临界资源之前，先基本思想：在每一个进程访问临界资源之前，先查看一下临界资源是否正被访问。若正被访问，则进查看一下临界资源

11、是否正被访问。若正被访问，则进程等待；否则进入自己的临界区。为此，设置一个数程等待；否则进入自己的临界区。为此，设置一个数组组flagflag，每个元素的初值为，每个元素的初值为falsefalse，表示进程未进入临，表示进程未进入临界区，进程进入临界区后，相应标志位置为界区，进程进入临界区后，相应标志位置为truetrue。repeat while flagj do no op; flagi = true； 进入临界区进入临界区 flagi = false;until false;repeat while flagi do no op; flagj = true； 进入临界区进入临界区 fl

12、agj = false;until false; 方法二可以满足原则方法二可以满足原则1 1，但又出现了新的问题。，但又出现了新的问题。比如，当比如，当P Pi i和和P Pj j几乎在同时都要求进入临界区，因几乎在同时都要求进入临界区，因而都发现对方的访问标志为而都发现对方的访问标志为falsefalse，于是两进程都先，于是两进程都先后进入临界区，显然，这不符合临界区处理的原则后进入临界区，显然，这不符合临界区处理的原则2 2。 为了解决这个问题，把标志位的含义改变为：为了解决这个问题，把标志位的含义改变为：truetrue表示进程希望进入临界区，即当进程要进入临表示进程希望进入临界区，即

13、当进程要进入临界区前，先将标志位界区前，先将标志位flagflag置为置为truetrue，表示进程已要，表示进程已要求进入临界区，然后再去查看另一进程的标志，若求进入临界区，然后再去查看另一进程的标志，若另一进程的另一进程的flagflag标志也为标志也为truetrue，则本进程等待，否，则本进程等待，否则，本进程进入临界区。则，本进程进入临界区。 换句话说，进程要进入临界区，首先设置其要换句话说，进程要进入临界区，首先设置其要求进入的标志，然后，再去查看其他进程的标志。求进入的标志，然后，再去查看其他进程的标志。方法三：方法三：repeat flagi = true； while fla

14、gj do no op; 进入临界区进入临界区 flagi = false;until false;repeat flagj = true； while flagi do no op; 进入临界区进入临界区 flagj = false;until false; 该方法可以有效地防止两个进程同时进入临界该方法可以有效地防止两个进程同时进入临界区，但仔细分析又可看出，该方法可能会造成两个区，但仔细分析又可看出，该方法可能会造成两个进程都不能进入临界区的后果。例如，当两个进程进程都不能进入临界区的后果。例如，当两个进程同时要求进入临界区，分别将自己的标志位置为同时要求进入临界区，分别将自己的标志位置

15、为truetrue，再去查看另一进程的标志，发现也为，再去查看另一进程的标志，发现也为truetrue，于是都等待，谁也无法进入临界区。于是都等待，谁也无法进入临界区。方法四：方法四：repeat flagi = true；turn = j; while flagj and turn = j do no op; 进入临界区进入临界区 flagi = false;until false; 假如进程假如进程P Pi i和和P Pj j几乎同时要求进入临界区，它几乎同时要求进入临界区，它们分别将们分别将flagiflagi和和flagjflagj置为置为truetrue。PiPi先将先将turntu

16、rn置为置为j j，当它执行，当它执行whilewhile语句时，条件成立，故等待。语句时，条件成立，故等待。但但P Pj j会立即将会立即将turnturn置为置为i i，这样，这样P Pi i就可以进入临界区。就可以进入临界区。P Pi i退出临界区时会将退出临界区时会将flagiflagi置为置为falsefalse，从而可以，从而可以使使P Pj j进入临界区。进入临界区。 利用软件方法解决互斥问题有一定难度，利用软件方法解决互斥问题有一定难度，在使用同一资源的进程数量较大时，有很大的在使用同一资源的进程数量较大时，有很大的局限性。局限性。 另外一种解决互斥问题的方法是锁机制。另外一种

17、解决互斥问题的方法是锁机制。为临界资源设置一个锁为临界资源设置一个锁w w，当进程在进入临界区，当进程在进入临界区之前，首先测试之前，首先测试w w的状态。的状态。w w等于等于1 1表示上锁，该表示上锁，该资源已被占用；资源已被占用；w w等于等于0 0表示开锁，该资源已空表示开锁，该资源已空闲，未被占用。闲，未被占用。Lock w: L: if w = 1 then goto L else w := 1Unlock w: w := 0; 软件的解决方法四和锁机制虽然可以在一软件的解决方法四和锁机制虽然可以在一定程度上解决互斥问题，但进程在等待时都需定程度上解决互斥问题，但进程在等待时都需要

18、不停地进行测试。这不满足处理临界区的原要不停地进行测试。这不满足处理临界区的原则则4 4，降低了系统工作效率。，降低了系统工作效率。信号量同步机制信号量同步机制 一个信号量可以看成由两个部分组成：一一个信号量可以看成由两个部分组成：一个是整型变量，另一个是队列。个是整型变量，另一个是队列。整型整型变量变量队列队列Procedure P (Var S: Semaphore) begin S := S 1; if S 0 then W(S) end;Procedure V (Var S: Semaphore) begin S := S + 1; if S = 1 then if r = 1 the

19、n begin begin r := r 1; r := r 1; A := r; A := r; V(S); V(S); 售出一张票售出一张票; end end else else 售出票已售完售出票已售完;endend；PROCESS PiPROCESS Pir : integer;r : integer;beginbegin P(S); P(S); r := A; r := A; if r = 1 then if r = 1 then begin begin r := r 1; r := r 1; A := r; A := r; V(S); V(S); 售出一张票售出一张票; end e

20、nd else else begin begin V(S); V(S); 售出票已售完售出票已售完 end endendend；无法退出无法退出临界区临界区读者写者问题：读者写者问题：规定：允许多个进程同时读；只允许一个进程写；规定：允许多个进程同时读；只允许一个进程写；当有进程读时不允许其它进程写。当有进程读时不允许其它进程写。第一种方案：定义信号量：第一种方案：定义信号量：S: semaphoreS: semaphore；初值；初值1 1；定义一个整数：定义一个整数：rs rs ，初值，初值0 0； 读者：读者：PROCESS Readeribegin rs := rs + 1; if r

21、s = 1 then P(S); read file F; rs := rs 1; if rs = 0 then V(S);end;写者：写者：PROCESS Writerjbegin P(S); write file F; V(S);end;问题：对共享变量问题：对共享变量rsrs访问的程序段也是临界区。访问的程序段也是临界区。 改进的方案：改进的方案：定义信号量：定义信号量：S, Sr: semaphoreS, Sr: semaphore；分别为互斥访问；分别为互斥访问文件和计数变量的信号量，初值均为文件和计数变量的信号量，初值均为1 1；定义一个；定义一个整数：整数：rs rs ，初值，

22、初值0 0； 读者：读者：PROCESS Readerbegin P(Sr); rs := rs + 1; if rs = 1 then P(S); V(Sr); read file F; P(Sr); rs := rs 1; if rs = 0 then V(S); V(Sr);end;写者：写者：PROCESS Writerbegin P(S); write file F; V(S);end;例题：试用例题：试用P P、V V操作写出读者优先的同步算法。操作写出读者优先的同步算法。解答：解答： 定义两个变量定义两个变量RCRC和和WCWC，分别用于对进入临界区的，分别用于对进入临界区的读者

23、和写者进程计数。为了互斥的操作这两个变量，读者和写者进程计数。为了互斥的操作这两个变量，需设置两个相应的信号量需设置两个相应的信号量RCSRCS和和WCSWCS。 为了使读者为了使读者- -写者之间和写者写者之间和写者- -写者之间互斥的访写者之间互斥的访问缓冲区，设置信号量问缓冲区，设置信号量S S。 为了阻止读者进程和链接等待的写者进程，设置为了阻止读者进程和链接等待的写者进程，设置信号量信号量W W。 为了链接等待的读者进程，设置信号量为了链接等待的读者进程，设置信号量R R。 这样，当有第一个写者进程进入临界区后，所有这样，当有第一个写者进程进入临界区后，所有的试图进入临界区的读者进程

24、将被阻塞在信号量的试图进入临界区的读者进程将被阻塞在信号量R R上，上，而写者进程将优先进入临界区。而写者进程将优先进入临界区。读者：读者：PROCESS Readerbegin P(R); P(W); P(RCS); if RC = 0 then P(S); RC := RC + 1; V(RCS); V(W); V(R); read file F; P(RCS); RC := RC 1; if RC = 0 then V(S); V(RCS);end;写者：写者：PROCESS Writerbegin P(WCS); if WC:= 0 then P(W); WC := WC + 1; V

25、(WCS); P(S); write file F; V(S); P(WCS); WC := WC 1; if WC = 0 then V(W); V(WCS);end;R := W := RCS := WCS := S := 1;RC := WC := 0;例题：举例说明例题：举例说明P P、V V操作为什么要被设计成原语（即对同一信操作为什么要被设计成原语（即对同一信号量上的操作必须互斥）。号量上的操作必须互斥）。解答：解答：对于对于P P操作，过程为：操作，过程为： Procedure P (Var S: Semaphore) begin S := S 1; if S 0 then W(

26、S) end;假如有两个进程假如有两个进程P1P1、P2P2几乎在同时作几乎在同时作P P操作，信号量操作，信号量S S的初值为的初值为1 1。如果进程如果进程P1P1先作先作P P操作，则操作，则S S的值为的值为0 0，P1P1进程不应被阻塞（或挂进程不应被阻塞（或挂起）。但是，如果起）。但是，如果P P操作不是原语操作，则可能有如下执行顺序：操作不是原语操作，则可能有如下执行顺序：P1P1：S := S - 1S := S - 1P2P2：S := S - 1S := S - 1P1P1：if S 0 then W(S)if S 0 then W(S)由于此时由于此时S S为为 1 1，

27、P1P1将被阻塞，这样，将被阻塞，这样，P P操作就不符合原来的语操作就不符合原来的语义了。义了。 同样，对于同样，对于V V操作，过程为：操作，过程为： Procedure V (Var S: Semaphore)Procedure V (Var S: Semaphore) begin S := S + 1; begin S := S + 1; if S = 0 then R(S) if S = 0 then R(S) end; end;假如有两个进程假如有两个进程P1P1、P2P2几乎在同时作几乎在同时作V V操作，信号量操作，信号量S S的初值的初值为为-1-1。如果进程。如果进程P1P

28、1先作先作V V操作，则操作，则S S的值为的值为0 0，该，该V V操作应该唤操作应该唤醒一个被醒一个被P P操作阻塞的进程。但是，如果操作阻塞的进程。但是，如果V V操作不是原语操作，操作不是原语操作，则可能有如下执行顺序：则可能有如下执行顺序： P1P1：S := S + 1S := S + 1 P2 P2：S := S + 1S := S + 1 P1 P1：if S = 0 then R(S)if S = 0 then R(S)由于此时由于此时S S为为1 1，P1P1所作的所作的V V操作将不再去唤醒被阻塞的进程，操作将不再去唤醒被阻塞的进程，这样，这样，V V操作就不符合原来的语

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

30、W(S)if S 0 then W(S) 则作则作P P操作的进程将不会被阻塞，这不符合语义。操作的进程将不会被阻塞，这不符合语义。 三、进程的同步三、进程的同步 协作协作 buffer1buffer2输入设备输入设备打印设备打印设备输入进程输入进程计算进程计算进程打印进程打印进程P1P2P3这里，计算进程这里，计算进程C C和打印进程和打印进程P P的工作必须相互的工作必须相互协作：计算进程只有在缓冲区中无数据时才能协作：计算进程只有在缓冲区中无数据时才能向其写入数据；打印进程只有在缓冲区中已有向其写入数据；打印进程只有在缓冲区中已有数据时才能将从中取出并打印。数据时才能将从中取出并打印。两

31、个进程应做如下协作两个进程应做如下协作1 1、进程、进程C C把一个记录存入缓冲区后，应向进程把一个记录存入缓冲区后，应向进程P P发发 送送“缓冲区中有等待处理的记录缓冲区中有等待处理的记录”的消息；的消息；2 2、进程、进程P P从缓冲区取出记录后，应向进程从缓冲区取出记录后，应向进程C C发送发送 “ “缓冲区中的记录已取走缓冲区中的记录已取走”的消息；的消息；3 3、进程、进程C C只有在得到进程只有在得到进程P P发送来的发送来的“缓冲区中的缓冲区中的 记录已取走记录已取走”的消息后，才能把下一个记录存的消息后，才能把下一个记录存 入缓冲区，否则，进程入缓冲区，否则，进程C C等待，

32、直到消息到达；等待，直到消息到达；4 4、进程、进程P P只有在得到进程只有在得到进程C C发送来的发送来的“缓冲区中有缓冲区中有 等待处理的记录等待处理的记录”的消息后，才能从缓冲区取的消息后，才能从缓冲区取 出记录，否则，进程出记录，否则，进程P P等待，直到消息到达。等待，直到消息到达。buffer1buffer2输入设备输入设备打印设备打印设备输入进程输入进程计算进程计算进程打印进程打印进程P1P2P3PROCESS calculatorbeginL1: P(SB); 计算下一个数据计算下一个数据 并送入缓冲区并送入缓冲区; V(SA); goto L1;end;PROCESS pri

33、nterbeginL2: P(SA); 从缓冲区中取出从缓冲区中取出 数据并打印数据并打印; V(SB); goto L2;end;同步机制同步机制 调用调用P P操作测试消息是否到达操作测试消息是否到达 调用调用V V操作发送消息操作发送消息 生产者生产者- -消费者问题消费者问题简单的生产者、消费者问题（单缓冲区）简单的生产者、消费者问题（单缓冲区）定义：整型变量：定义：整型变量：BufferBuffer，信号量：，信号量：SP=1, SG=0SP=1, SG=0 PROCESS Producerbegin L1: produce a product; P(SP); Buffer := p

34、roduct; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Buffer; V(SP); goto L2end多缓冲区生产者、消费者问题多缓冲区生产者、消费者问题 PROCESS Producerbegin L1: produce a product; P(SP); Bk := product; k := (k + 1) mod n; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Bt; t := (t +

35、 1) mod n V(SP); consumer; goto L2end定义：整型变量：定义：整型变量：k = 0, t = 0k = 0, t = 0 整型数组：整型数组：B0n-1B0n-1 信号量：信号量：SP = n, SG = 0 SP = n, SG = 0 例子：三个进程例子：三个进程R R、W1W1、W2W2，共享一个缓冲区，共享一个缓冲区B B，B B中最多只能中最多只能存放一个数。进程存放一个数。进程R R负责不断地向负责不断地向B B中存入整数，进程中存入整数，进程W1W1、W2W2分分别负责取出别负责取出B B中的奇数和偶数并进行打印。中的奇数和偶数并进行打印。PRO

36、CESS Rx: integer;beginL1: 从输入设备中读入从输入设备中读入 一个数一个数; x := 读入的数；读入的数；P(S);B := x; if B=奇数奇数 then V(SO) else V(SE) goto L1;endPROCESS W1y: integer;beginL2: P(SO); y := B； V(S); 打印打印y中数中数； goto L2;endPROCESS W2z: integer;beginL3: P(SE); z := B； V(S); 打印打印z中数中数； goto L3;end定义信号量：定义信号量：S S 初值为初值为1 1 表示初始时缓

37、冲区可用表示初始时缓冲区可用 SO SO 初值为初值为0 0 用于向打印奇数的进程发消息用于向打印奇数的进程发消息 SE SE 初值为初值为0 0 用于向打印偶数的进程发消息用于向打印偶数的进程发消息四、同步与互斥的混合问题四、同步与互斥的混合问题 例子：有例子：有m m个生产者和个生产者和r r个消费者共享容量为个消费者共享容量为n n的缓冲的缓冲器（器（m m、r r、n n均大于均大于1 1）。每个生产者把自己生产的物）。每个生产者把自己生产的物品存入缓冲区，每个消费者从缓冲区中取出物品去消品存入缓冲区，每个消费者从缓冲区中取出物品去消费。要求用费。要求用P P、V V操作对这些生产者和

38、消费者进行正确操作对这些生产者和消费者进行正确管理。管理。定义：整型数组：定义：整型数组：B0n-1B0n-1 整型变量：整型变量：k k，t t 初值均为初值均为0 0 信号量：信号量：S1S1：初值：初值1 1 用于生产者放入物品用于生产者放入物品 S2S2：初值：初值1 1 用于消费者取出物品用于消费者取出物品 SPSP：初值：初值n n 缓冲区是否可用缓冲区是否可用 SGSG：初值：初值0 0 缓冲区里是否有物品缓冲区里是否有物品PROCESS PibeginL1: produce a product; P(SP); P(S1); Bk := product; k := (k + 1)

39、 mod n; V(S1); V(SG); goto L1endPROCESS CjbeginL2: P(SG); P(S2); take a product from Bt; t := (t + 1) mod n; V(S2); V(SP); consume; goto L1end生产者分别向缓冲区送产品，由生产者分别向缓冲区送产品，由S1S1控制互斥访问。控制互斥访问。消费者分别从缓冲区中取出产品，由消费者分别从缓冲区中取出产品，由S2S2控制互斥访问。控制互斥访问。例子：例子：现有四个进程现有四个进程R1R1、R2R2、W1W1、W2W2，它们共享一个，它们共享一个可以存放一个数的缓冲器

40、可以存放一个数的缓冲器B B，R1R1、R2R2从键盘和从键盘和磁盘上读入数据，放到缓冲器磁盘上读入数据，放到缓冲器B B中，中，W1W1、W2W2从从缓冲器中分别读取缓冲器中分别读取R1R1，R2R2写入的数据并输出打写入的数据并输出打印。怎样用印。怎样用P P、V V操作来协调四个进程的并发执操作来协调四个进程的并发执行行？定义：信号量定义：信号量 S S 初值为初值为1 1 用于写入进程的互斥用于写入进程的互斥 S1 S1 初值为初值为0 R10 R1向向W1W1发送消息发送消息 S2 S2 初值为初值为0 R20 R2向向W2W2发送消息发送消息 整型变量整型变量 B BPROCESS

41、 R1x: integerbeginL1: 接受来自键盘的数接受来自键盘的数； x := 接受的数接受的数; P(S); B := x; V(S1); goto L1endPROCESS R2y: integerbeginL2: 从磁盘上读一个数从磁盘上读一个数； y := 读入的数读入的数; P(S); B := y; V(S2); goto L2endPROCESS W1k: integerbeginL4: P(S1); k := B; V(S); 打印打印k中的数中的数； goto L3endPROCESS W2j: integerbeginL4: P(S2); j := B; V(S)

42、; 打印打印k中的数中的数； goto L3end例题：假定一个阅览室最多可以同时容纳例题：假定一个阅览室最多可以同时容纳100100个人阅读，读者进入和离开阅览室时，个人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记都必须在阅览室门口的一个登记表上登记或去掉登记。试用或去掉登记。试用P P、V V操作编写读者进程操作编写读者进程的同步算法。的同步算法。分析：设读者有任意多个，但能同时阅览分析：设读者有任意多个，但能同时阅览的只能的只能100100人，所以，设一个信号量人，所以，设一个信号量S S代表代表空座位数目，初值为空座位数目，初值为100100，用它来控制进入，用它

43、来控制进入阅览室的读者进程不超过阅览室的读者进程不超过100100。另设信号量。另设信号量m m，用于控制对登记表这一共享资源的互斥，用于控制对登记表这一共享资源的互斥使用，其初值为使用，其初值为1 1。Process 第第i个读者进程个读者进程 begin P(S); P(m); 填写登记表；填写登记表； V(m); 坐下阅览坐下阅览; P(m); 在登记表上去掉登记；在登记表上去掉登记； V(m); V(S); goto L1; end例题：有一个仓库存放两种零件例题：有一个仓库存放两种零件A A和和B B，最大库容量各为，最大库容量各为M M个。有一车间不断的取个。有一车间不断的取A A

44、和和B B进行装配，每次各取一个。进行装配，每次各取一个。有两组供应商分别不断的供应有两组供应商分别不断的供应A A和和B B（每次供应一个）。（每次供应一个）。为保证配套和合理库存，当某种零件的数量比另一种的为保证配套和合理库存，当某种零件的数量比另一种的数量超过数量超过n n（n Mn = 1 and . and S = 1 and . and Sn n = 1) = 1) for i:=1 to n do for i:=1 to n do S Si i := S := Si i 1; 1; else else 将当前执行进程插入到将当前执行进程插入到S Si i的等待队列，的等待队列，

45、S Si i是第一个满足是第一个满足S Si i 1 = t = t1 1 and . and S and . and Sn n = t = tn n) ) for i:=1 to n do for i:=1 to n do S Si i := S := Si i d di i; ; else else 将当前执行进程插入到将当前执行进程插入到S Si i的等待队列，的等待队列， S Si i是第一个满足是第一个满足S Si i t 1）或互斥信号量）或互斥信号量（S=1）;(3) P(S,1,0)，这是一种很特殊且很有用的，这是一种很特殊且很有用的 信号量。当信号量。当S=1时，允许多个进程

46、进入时，允许多个进程进入 某特定区，当某特定区，当S变为变为0后，将阻止任何进后，将阻止任何进 程进入特定区。换言之，它相当于一个程进入特定区。换言之，它相当于一个 可控开关。可控开关。2、管程、管程 信号量机制的一个特点是：在每个并发进程信号量机制的一个特点是：在每个并发进程中都要设置大量的同步操作原语，同步控制部分中都要设置大量的同步操作原语，同步控制部分分散在各个进程中。这不仅给编程带来了麻烦，分散在各个进程中。这不仅给编程带来了麻烦，而且如果而且如果P、V操作不当还可能会导致数据的不操作不当还可能会导致数据的不确定性和系统的死锁。确定性和系统的死锁。 Dijkstra认为应把各进程中与

47、同一共享数据认为应把各进程中与同一共享数据有关的同步控制和同步处理集中起来，构成独立有关的同步控制和同步处理集中起来，构成独立于进程的实体。系统中的各种硬件资源和软件资于进程的实体。系统中的各种硬件资源和软件资源均可用数据结构抽象地描述，既用少量信息和源均可用数据结构抽象地描述，既用少量信息和对该资源所执行的操作来表征该资源，而忽略它对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。当共享资源用共享数们的内部结构和实现细节。当共享资源用共享数据来表示时，资源管理程序可以用对该数据结构据来表示时，资源管理程序可以用对该数据结构进行操作的一组过程来表示。我们把这样一组相进行操作的一

48、组过程来表示。我们把这样一组相关的数据结构和过程称为管程。关的数据结构和过程称为管程。 Hansen为管程下的定义是：一个管程定义了为管程下的定义是：一个管程定义了一个数据结构和能为并发进程所执行的（在该数一个数据结构和能为并发进程所执行的（在该数据结构上的）一组操作，这种操作能同步进程和据结构上的）一组操作，这种操作能同步进程和改变管程中的数据。改变管程中的数据。 管程的组成：管程的组成： 局部于管程的共享数据说明局部于管程的共享数据说明 对该数据结构进行操作的一组过程对该数据结构进行操作的一组过程 对局部于管程的数据的初始化语句对局部于管程的数据的初始化语句 在管程的实现中必须考虑：在管程

49、的实现中必须考虑：互斥互斥：当几个进程调用管程时，仅允许一个进程：当几个进程调用管程时，仅允许一个进程进入管程，其它调用者必须等待。进入管程，其它调用者必须等待。同步同步：在管程中必须设置两个同步操作原语：在管程中必须设置两个同步操作原语wait和和signal。当进程通过管程请求访问某。当进程通过管程请求访问某共享数据而未能满足时，管程便调用共享数据而未能满足时，管程便调用wait 原原语使该进程等待，并将它排在等待队列上。语使该进程等待，并将它排在等待队列上。仅当另一进程访问完该共享资源且释放后，仅当另一进程访问完该共享资源且释放后，管程又调用管程又调用signal原语，唤醒等待队列中的原语，唤醒等待队列中的队首进程。队首进程。条件变量条件变量：条件变量是用来区别不同的等待：条件变量是用来区别不同的等待原因，该条件变量应置于原因，该条件变量应置于wait和和signal之前。之前。操作操作共享数据共享数据初始化代码初始化代码XY入口队列入口队列.type