并发控制互斥与同步

1、1第3章 并发控制互斥与同步 本章知识点：本章知识点：n3.1 并发原理并发原理 n3.2 互斥互斥软件解决方法软件解决方法n3.3 互斥互斥硬件解决方法硬件解决方法 n3.4 信号量信号量n3.5 管程管程n3.6 消息传递消息传递n3.7 读者读者/写者问题写者问题n3.8 系统举例（略）系统举例（略） 23.1 并发原理 在单处理机多道程序的系统中，进程的并发执行方式是插入执行（图3.1a），表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行（图3.1b） 。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物

2、理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关（P73 例 echo）。33.1.1 进程间的相互作用 进程之间常常相互作用，存在某种彼此依赖或相互制约（直接或间接）的关系，表现为同步和互斥关系。 根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察（见表3.1）。43.1.2 进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题：n互斥临界资源、临界区的概念n死锁例如、系统中只有1个输入设备、1个输出设备，而进程P1占有输入设备、申请输出设备；进程P2占有输出设备、申请输入设

3、备。n饥饿P77例 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。53.1.3 进程间的相互合作 1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题（见P78例）。63.1.3 进程间的相互合作2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式（例如、信箱通信）。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但

4、是还存在死锁和饥饿问题。 73.1.4 互斥的要求 并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以下要求：n互斥执行 n执行非临界段的进程不能受到其他进程的干扰 n有限等待n有空让进 n没有进程相对速度和数目的假设 n进程进入到临界段中的时间有限 83.2 互斥软件解决方法 软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程负荷和较多的错误，但有利于深刻理解并发的复杂性。93.2.1 Dekker算法 Dekker算法

5、的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。 103.2.1 Dekker算法n1.第1种途径：两进程解法 (算法 1)l设两个进程共享一个整型变量 turnl如果变量 turn 的值为 i ，则进程 Pi 可以在其临界区内执行l当 Pi 退出临界区，它置 turn 的值为 jl确保仅有一个进程可以在它的临界区内l存在进程推进问题l如果 turn 的值是 j，而进程 j 并不需要进入临界区；当进程 i 试图进入临界区时，它将被阻塞。113.2.1 Dekker算法 这种方法保证了

6、互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。如果有一个进程以后不进临界区，则另一个进程也无法进入。 var turn: 0.1; turn为共享的全局变量PROCESS 0 PROCESS 1 while turn0 do nothing while turn1 do nothing；critical section; critical section;turn: =1; turn: =0; 123.2.1 Dekker算法 2.第2种途径 有可能两个进程同时进入临界区。这种解决方法依赖于进程执行的相对速度。共享的全局变量是：var flag: array0.1of bo

7、olean;它被初始化为falsePROCESS 0 PROCESS 1 while flag1do nothing; while flag0do nothing;flag0: =true; flag1: =true;critical section; critical section;flag0: =false; flag1: =false; 133.2.1 Dekker算法n3.第3种途径：两进程解法 (算法 3) l用一个布尔类型的数组 flagl 数组元素初始化为 false；lflagi = false；lflagj = false；l当进程 Pi 要进入它的临界区，先置 flagi

8、为真 flagi = true； l进入临界区前，Pi 确信 Pj 没有准备进入临界区 while(flagj=true)；l存在有限等待问题l两个进程可能同时设置它们的标志为 true ，那么就会在各自的 while 语句内无穷循环143.2.1 Dekker算法这种方法保证了互斥但会导致死锁问题。 PROCESS 0 PROCESS 1 flag0: =true; flag1: =true;while flag1 do nothing; while flag0 do nothing;critical section; critical section;flag0: =false; flag

9、1: =false; 153.2.1 Dekker算法4.第4种途径（接近正确，但还有缺陷；书上有错）PROCESS 0 PROCESS 1 flag0: =true; flag1: =true;while flag1 do while flag0 do begin begin flag0: =false; flag1: =false; delay for a short time; delay for a short time; flag0: =true; flag1: =true;end; end;critical section; critical section;flag0: =fal

10、se； flag1: =false; 163.2.1 Dekker算法5.第五种途径(一个正确的解决方法)用变量turn表示哪个进程坚持进入临界区 设计一个“指示”小屋，小屋内的黑板标明“turn”，当P0想进入其临界段时，置自己的flag为“true”，这时它去查看P1的flag，如果是“false”，则P0就立即进入自己的临界段，反之P0去查看“指示”小屋，如果turn=0，那么它知道自己应该坚持并不时去查看P1的小屋， P1将觉察到它应该放弃并在自己的黑板上写上“false”，以允许P0继续执行。 P0执行完临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进

11、入权交给P1 。173.2.2 Peterson算法 Dekker算法（正确的解法）可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将Peterson 算法推广到多个进程的情况。 183.2.2 Peterson算法n结合前面的算法 3l用 flag 数组标志和一个 turn 变量lturn变量确保不会死锁l满足互斥，有空让进和有限等待的需求l仅解决两个进程的临界区问题l参见下面的代码n(本书解决 n 个进程的临界区问题)193.2.2 Peterson算法flagi = true; / I wa

12、nt to go criticalturn = j; / but you go first if you want while (flagj & turn = j) ; / wait while j is in criticalcritical section/ go criticalflagi = false; / Im done203.2.2 Peterson算法flagj = true; / I want to go criticalturn = i; / but you go first if you want while (flagi & turn = i) ; /

13、wait while i is in criticalcritical section/ go criticalflagj = false; / Im done213.2.2 Peterson算法var flag: array0.1 of boolean; flag1: =true; turn: 0.1; turn: =0;procedure P0; while flag0 and turn=0 do nothing;begin critical section; repeat flag1: =false; flag0: =true; remainder turn: =1; foreverwh

14、ile flag1 and turn=1 do nothing; end; critical section; begin flag0: =false; flag0: =false; remainder flag1: =false; forever turn: =1;end; parbeginprocedure P1; P0; P1begin parend repeat end.223.3 互斥硬件解决方法 完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度，且有很大局限性，现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥，可以降低开销。

15、233.3.1 禁止中断 在单处理机中，禁止进程被中断即可保证互斥，通过操作系统内核定义的禁止和允许中断的原语就可获得这种能力。进程执行临界段时不能被中断。 优点：n在单处理机中可保证互斥。 缺点：n代价较高，使执行效率显著降低n在多处理机系统中，禁止中断不能保证互斥243.3.2 使用机器指令1.特殊的机器指令 在多处理机系统中，多个处理机共享一个共同的主存，这里并没有主/从关系，也没有实现互斥的中断机制。许多系统都提供了一些特殊的硬件指令，允许我们在一个存储周期内去测试和修改一个字的内容（Test and Set指令），或者交换两个字的内容（Exchange指令）等等。这些特殊指令可以用来

16、解决临界段问题。 253.3.2 使用机器指令n现代计算机系统可以支持像 test-and-set 和 swap 硬件指令；这些指令在一个指令周期内完成，是 原子的 (即不可被中断)操作。n如果进程在进入临界区前首先必须运行如此的指令，那么可以达到互斥。n例如，如果两个 test-and-set 指令同时执行(在不同的 CPU 上)，那么它们会按任意顺序来执行。263.3.2 使用机器指令273.3.2 使用机器指令n用 test-and-set 实现互斥283.3.2 使用机器指令lockfalsetruefalsetrue n y293.3.2 使用机器指令n用 swap (全局的 loc

17、k，局部的 key)30pkeytruefalseslockfalsetruefalsetruepkeytruetruefalsetrue313.3.2 使用机器指令2.机器指令方法的特性优点： 可用于含有任意数量进程的单处理机或共享主存的多处理机； 比较简单，易于验证； 可支持多个临界段，每个临界段用各自的变量加以定义。缺点： 采用busy-waiting技术，进程等待进入临界段时耗费处理机时间； 可能产生饥饿（参见P87）； 可能产生死锁（参见P87） 。323.4 信号量 信号量是一个由整型变量和对应的队列所组成的特殊变量，除对其初始化外，它只可以由两个不可中断的P（Wait）、V（Si

18、gnal）操作存取。不论是采用一般信号量还是二元信号量，进程都将排队等候信号量，但这并不意味着进程移出的顺序与队列次序相同。 基本原则： 两个或多个进程可通过单一的信号量展开合作，即进程在某一特定的地方停止执行，直到某个特定的信号量到来为止。通过信号量，任何复杂的合作要求都可被满足。 333.4 信号量n定义 wait 和 signal 函数n当 wait 被调用时如果信号量在使用中其值=1 then begin Pn;Xi:=Xi-1; parendcount:=Xi; end.Signal(s);输出一张票输出一张票;EndElseBeginSignal(s);输出输出“票已售完票已售完”

19、;End;End;40n如果改成下面这种写法行吗？为什么？如果改成下面这种写法行吗？为什么？Process Pi(i=1,2,n) beginBegin s:semaphore; count:integer;Var Xi:integer; s:=1;按旅客要求找到按旅客要求找到 count; parbeginWait(s); P1;Xi:=count; P2;If Xi=1 then begin Pn;Xi:=Xi-1; parendXi:=count; end.Signal(s);输出一张票输出一张票;EndElse输出输出“票已售完票已售完”;End; 413.4.2 用信号量解决生产者/

20、消费者问题 问题描述如下： 一个或更多的生产者生产出某种类型的数据(记录、字符)，并把它们送入缓冲区，惟一的一个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。 423.4.2 用信号量解决生产者/消费者问题n这是一个进程同步问题 生产者进程在送数据前要确定缓冲区不满，把一个数据送入缓冲区后要发信号给消费者；同样消费者在取数据前要确定缓冲区不空，从缓冲区取一个数据后要发信号给生产者。n如果进程间不能同步（相互制约），那么可能导致数据被覆盖或重复取数或取无用的数据（随机数）。433.4.2 用信号量解决生产者/消费者问题n假如

21、是一个生产者、一个消费者，且缓冲区只有一个单元。假如是一个生产者、一个消费者，且缓冲区只有一个单元。Begin Process producer Process consumer Buffer:integer; Begin Begin Se,Sf:semaphore; Repeat Repeat Se:=1;Sf:=0; Produce a product; Wait(Sf); parbegin Wait(Se); Take a product; producer; Buffer:=product; Signal(Se); consumer; Signal(Sf); Consumer; par

22、end Forever Forever End. End; End;验证：验证：1、缓冲区满生产者不能送数；缓冲区空消费者不能取数、缓冲区满生产者不能送数；缓冲区空消费者不能取数 2、在这个问题中同步隐含着互斥。、在这个问题中同步隐含着互斥。443.4.2 用信号量解决生产者/消费者问题n假如是一个生产者、一个消费者，且缓冲区有假如是一个生产者、一个消费者，且缓冲区有 N 个单元。个单元。n当缓冲区没有放满 N 个数据时，生产者进程调用 wait(Se)都不会成为等待状态，可以把数据送入缓冲区。但当缓冲区中已有 N 个数据时，生产者进程想要再送数将被拒绝。由于每送入一个数后要调用 Signal

23、(Sf) ，所以此时 Sf 的值表示缓冲区中可取的数据数，只要 Sf 0，消费者进程在调用 wait(Sf) 后总可以从缓冲区取数。每取走一个数据就调用 Signal(Se)，因此增加了一个存放数据的位置。可以用指针 in 和 out 分别指示生产者进程向缓冲区送数和消费者进程从缓冲区取数的相对位置；指针的初始值为“0”。n这种情况下生产者与消费者进程的同步算法为： 453.4.2 用信号量解决生产者/消费者问题Begin Process producer Process consumer B:array0.n-1 of integer; Begin Begin in,out:integer;

24、 Repeat Repeat Se,Sf:semaphore; Produce a product; Wait(Sf); in:=out:=0; Wait(Se); Take a product from Bout; Se:=n;Sf:=0; Bin:=product; out:=(out+1) mod n; parbegin in:=(in+1) mod n; Signal(Se); producer; Signal(Sf); Consumer; consumer; Forever Forever parend End; End;End. 说明：这时缓冲区可以看成是头尾相连一个环形，说明：这

25、时缓冲区可以看成是头尾相连一个环形，in、out 指针指出存取数的位置。指针指出存取数的位置。验证：验证：1、缓冲区满生产者不能送数；缓冲区空消费者不能取数、缓冲区满生产者不能送数；缓冲区空消费者不能取数 2、在这个问题中生产者与消费者进程有可能同时进入缓冲区，但不会出错。、在这个问题中生产者与消费者进程有可能同时进入缓冲区，但不会出错。463.4.2 用信号量解决生产者/消费者问题n假设是假设是M个生产者、个生产者、R个消费者，且缓冲区有个消费者，且缓冲区有 N 个单元。个单元。n现在不仅生产者与消费者之间要同步，而且现在不仅生产者与消费者之间要同步，而且 M 个生产者之个生产者之间、间、R

26、 个消费者之间还必须互斥地访问缓冲区。个消费者之间还必须互斥地访问缓冲区。n要同步的原因和前面的问题一样；之所以要互斥是因为如要同步的原因和前面的问题一样；之所以要互斥是因为如果果 M 个生产者进程各自个向缓冲区送数，当第一个生产者个生产者进程各自个向缓冲区送数，当第一个生产者按指针按指针 in 指示的位置送一个数，但在改变指针前可能被打指示的位置送一个数，但在改变指针前可能被打断执行，于是当第二个生产者送数时仍按原指针所指出的断执行，于是当第二个生产者送数时仍按原指针所指出的位置存放，这样两个数被放在同一个单元，造成数据丢失。位置存放，这样两个数被放在同一个单元，造成数据丢失。同样，同样，R

27、 个消费者都要取数时可能都从指针个消费者都要取数时可能都从指针 out 指出的位指出的位置取数，造成一个数据被重复取出。置取数，造成一个数据被重复取出。473.4.2 用信号量解决生产者/消费者问题n按课本的问题描述在任一时刻只能有一方(生产者或消费者)访问缓冲区。 即一次只能有一个进程可以进入缓冲区。这是第一种方法。n可是、当有一个生产者（或消费者）在送数（或取数）时，可以允许一个消费者（或生产者）同时访问缓冲区去取数（或送数）。因此这是第二种方法。n显然、第二种方法的并行性要比第一种方法的并行性高。483.4.2 用信号量解决生产者/消费者问题n第一种方法Begin Process pro

28、ducer i Process consumer j B:array0.n-1 of integer; Begin Begin in,out:integer; Repeat Repeat S,Se,Sf:semaphore; Produce a product; Wait(Sf); in:=out:=0; Wait(Se) Wait(S); S:=1;Se:=n;Sf:=0 Wait(S); Take a product from Bout; parbegin Bin:=product; out:=(out+1) mod n; producer; in:=(in+1) mod n; Signa

29、l(Se); consumer; Signal(Sf) ; Signal(S); parend Signal(S); Consumer;End. Forever Forever End; End; n思考：1、如果生产者或消费者进程中的两个 Wait 操作次序对调 可以吗？ 2、第二种方法应该如何改写？493.4.2 用信号量解决生产者/消费者问题 用二元信号量来解决此问题*： 在任何时候生产者(P)都可向缓冲区中添加数据，在添加数据前，P执行waitB(s)，然后执行signalB(s)以防止在添加过程中，别的消费者(C)或P访问缓冲区。在进入到临界段时，P将增加n的值，如果n=1则在此次添

30、加数据前缓冲区为空，于是P执行signalB(delay)并将这个情况通知C。C最初执行waitB(delay)来等待P生产出第一个数据，然后取走数据并在临界段中减小n的值。如果P总保持在C前面，那么C就不会因为信号量delay而阻塞，因为n总是正数，这样P和C都能顺利地工作。这个方法也存在缺陷有可能导致死锁。解决这个问题的一个方法是引入一个附加变量，它在消费者的临界段中设置。这样，就不会出现死锁了。 503.4.3 信号量的实现 wait和signal操作都必须作为原子操作实现。显然，用硬件方法或固件方法都可解决这一问题，而且还有其他解决方法。尽管wait和signal操作执行的时间较短，但

31、因包含了忙-等，故忙-等占用的时间是主要的（见图3.15a）。 对单处理机系统而言，可以在wait和signal操作期间屏蔽中断，而且这些操作的执行时间相对较短（见图3.15b） 。固件注：固件注：现在硬件与软件间的界限越来越模糊，许多原来属于软件的功 能，通过程序设计技术可以转化为硬件，即所谓的固化；因此 具有软件功能的硬件称为固件。513.4.4 用信号量解决理发店问题* 理发店问题是使用信号量实现并发的另一个例子，它同操作系统中的实际问题非常相似。如图示理发椅沙发收款台出口入口顾客休息区523.5 管程 信号量为实现互斥和进程间的协调提供了一个功能强大而灵活的工具，然而，使用信号量来编制

32、正确的程序是困难的。因为：（1）临界区操作的代码以及进入和退出临界区的操作代码，均要由用户编写。（2）所有 wait、 signal操作部分都分散在用户编写的各程序代码中，由进程来执行。这样系统无法有效地控制和管理这些 wait、 signal操作。（3）用户编程时难免会发生不正确地使用wait、 signal操作的错误，这种错误会给系统带来不堪设想的后果（如死锁）；编译程序和操作系统都无法发现和纠正此类错误。 作为程序设计语言中的一种结构，管程(Monitor)提供了与信号量相同的表达能力，但它更容易控制。 533.5.1 带信号量的管程 管程是一种并发性的结构，它包括用于分配一个特定的共享

33、资源或一组共享资源的数据和过程。管程由三部分组成：n局部于管程的共享变量说明。n对该数据结构进行操作的一组过程。n对局部于管程的数据设置初始值的语句。此外，还需为该管程赋予一个名字。 543.5.1 带信号量的管程管程最主要的特点如下：n 只能通过管程中的过程而不能用其他外部过程访问其局部数据变量。n进程通过调用管程的过程而进入管程。n每一时刻只能有一个进程在管程中执行，任何其他调用管程的进程将被挂起直至管程可用为止。n同步手段：（1）cwait(c) :等待操作，调用进程在条件 c 上挂起，管程可以被其他进程使用。（2）csignal(c) :发信号操作，在条件 c 上被 cwait 挂起的

34、进程被再次执行，如果没有就什么都不做。n注意：管程的 cwait/csignal 操作与信号量中的wait/signal 操作不同，如果在管程中的进程发信号并且没有一个进程等待条件变量，这个信号就丢失了。553.5.2 用管程解决生产者/消费者问题 管程模块控制着缓冲区。管程包括两个条件变量：当缓冲区中还有空位置时，变量 notfull 为 true，如果缓冲区中至少有一个字符存在，则变量 notempty为 true。生产者只能通过管程中的过程append 向缓冲区添加字符，生产者不能直接访问缓冲区。这个例子（P100）比较了管程和信号量。563.6 消息传递 进程间的相互作用必须满足两个条

35、件： 同步和通信，进程需要同步来实现互斥，进程间的协同需要交换信息，一个能解决上述两个问题的方法是消息传递(message passing)。消息传递还有一个优点是，它的适应性很强，能在分布式系统、共享存储器的多处理机系统以及单处理机系统等不同系统中实现。 573.6.1 消息传递原语原语：nsend (destination, message)Destination 可以是进程（直接寻址）或邮箱（间接寻址）。nreceive (source, message)Source 可以是进程（直接寻址）或邮箱（间接寻址）。583.6.2 用消息传递实现同步 无论是发送方还是接收方都可能被阻塞。下面有

36、三种最一般的组合，任何特定系统都实现了其中的一种或两种：n阻塞发送，阻塞接收：阻塞发送，阻塞接收：严格同步方式，发送进程阻塞，直到消息为接收进程或邮箱所接收；接收进程阻塞，直到有消息可用。 n无阻塞发送，阻塞接收：无阻塞发送，阻塞接收：常用的组合方式，发送进程发送消息并再继续操作；接收进程阻塞，直到有消息可用。 例如向打印机发送打印请求。 n无阻塞发送，无阻塞接收：无阻塞发送，无阻塞接收： 较常用的组合方式，发送进程发送消息并再继续操作；接收进程接收消息并再继续操作。593.6.3 寻址方式1. 直接寻址 对直接寻址方式，send原语中明确标明了目的进程。receive原语有两种方式：第一种方

37、式接收进程预先知道发送消息的源进程，另一种方式则不可能预先知道源进程。603.6.3 寻址方式2. 间接寻址 消息不直接由发送方传给接收方，而是通过一个共享的数据结构，包括临时存放消息的队列（邮箱式端口）。这种方法有很大的灵活性。进程与邮箱的关系可以是静态的或动态的，端口通常与一个特定的进程相关联。端口通常由接收进程产生并为其所有。 613.6.4 消息格式 消息格式依赖于消息系统的用途和消息系统是在单个计算机上运行还是在分布式系统中运行，一些操作系统选择了较短的定长消息以减小处理和存储的开销，如果有大量的数据需要传递，那么可以将数据存入文件并把文件作为消息传递，一种更为灵活的方法是允许变长消

38、息。 623.6.4 消息格式支持变长消息的操作系统中的消息格式 消 息 源目 的 地消息长度控制信息消息类型消息头消息体消息的内容633.6.5 排队规则 最简单的排队规则是先进先出，但这远远不够。一个改进的方法是由发送方或接收方基于消息的类型标明消息的优先权；另一个改进方法是允许接收方检查消息队列并选择要接收的消息。 643.6.6 用消息传递实现互斥 假设使用阻塞 receive 原语和无阻塞send 原语，并发进程集共享一个邮箱mutex，将邮箱初始化为仅包含一个空消息，欲进入临界段的进程首先要接收相应的消息，如果邮箱为空则该进程被阻塞，一旦进程得到消息它就执行其临界段，然后再将消息放

39、回邮箱，这样消息就如同令牌一样在进程之间传递。 653.6.6 用消息传递实现互斥 这种解决方法是假设有多于一个进程并发执行 receive 操作，则有：n如果仅有一个消息，那么它只可传递给一个进程，其他进程将被阻塞。n如果邮箱为空，则所有的进程将被阻塞。当消息可用时，仅有一个阻塞进程被激活并得到消息。663.6.6 用消息传递实现互斥Program mutualexclusion; Procedure P(i:integer);const n=; var msg:message; Begin ( * main program * ) BeginCreat-mailbox(mutex); re

40、peatSend(mutex,null); Parbegin receive(mutex,msg); P(1); ( critical section ); P(2); send(mutex,msg); P(n); foreverParend End; End.673.6.6 用消息传递解决生产者/消费者问题 使用消息传递所支持的互斥和信号量不具备传递数据的能力可以解决带有界缓冲区的生产者/消费者问题。 这个方法非常灵活，可以允许有多个生产者和消费者，系统还可以是分布式的。683.6.6 用消息传递解决生产者/消费者问题Const Procedure producer; Capcity=n;

41、var pmsg:message; Null=n; BeginVar i:integer; while true doBegin Begin Creat mailbox(mayproduce); receive(mayproduce,pmsg); Creat mailbox(mayconsume); pmsg:=produce; For i=1 to capacity do send(mayconsume,pmsg);Send(mayproduce,null); End Parbegin End;Producer; Procedure consumer;Consumer; var cmsg:m

42、essage; Parend BeginEnd. while true do Begin receive(mayconsume,cmsg); consume(cmsg); send(mayproduce,null); End End;693.7 读者/写者问题readers/writers问题的定义如下： 一些进程共享一个数据区。数据区可以是一个文件、一块内存空间或一组寄存器。readers 进程只能读数据区中的数据，而 writers 进程只能写。所谓读者/写者问题就是指保证一个 writer 进程必须与其他进程互斥地访问共享对象的同步问题。 703.7 读者/写者问题解决该问题必须满足的条

43、件如下：n任意多个 readers 可以同时读；n任一时刻只能有一个 writers 可以写；n如果 writers 正在写，那么 readers 就不能读。713.7.1 读者优先 信号量 wsem 用来实现互斥，只要有 writer在访问共享数据区，其他 writers 或 readers 就不能访问数据区。reader 进程同样利用 wsem 实现互斥。为了适用于多个 reader，当没有 reader 读时，第一个进行读的 reader 要测试 wsem，当已经有 reader 在读时，随后的 reader 无须等待就可读取数据区。 一旦有一个 reader 访问数据区，只要还有一个

44、reader 在进行读操作，reader 就可以保持对数据区的控制，这就容易导致 writers 饥饿。 723.7.1 用信号量解决读者用信号量解决读者/写者问题（读者优先）写者问题（读者优先）Program readerandwriters; Procedure reader; Procedure writer; var readcount:integer; Begin Begin x,wsem:semaphore(:=1); repeat repeat Begin wait(x); wait(wsem); Readcount:=0; readcount:=readcount+1; WRITEUNIT; Par