《计算机操作系统》汤小丹

1、湘 潭 大 学第第3 3章章进程的同步与通信进程的同步与通信 进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同步的主要任务，是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。3.1 3.1 进程同步的基本概念进程同步的基本概念进程间的相互制约关系在多道程序环境下，系统中可能有着许多进程，这些进程之间可能存在以下两种关系。间接相互制约关的系：多个进程之间彼此无关，并不知道其他进程的存在，但这些进程既然同处于一个系统中，也就必然存在资源共享的关系，如共享CPU、I/O设备等。此时进程同步的主要任务是保证诸进程能互斥地访问临界资源。这样，系统中的资源应由系

2、统统一管理，不允许用户进程直接使用。直接相互制约的关系：在某些进程间还存在相互合作关系，此时进程同步的主要任务是保证诸进程在执行次序上的协调，不会出现与时间有关的差错。临界资源临界资源临界资源，也称独占资源，是在一段时间内只允许一临界资源，也称独占资源，是在一段时间内只允许一个进程访问的资源。对临界资源，进程间应采取互斥个进程访问的资源。对临界资源，进程间应采取互斥方式共享。方式共享。例子：例子：Producer-ConsumerProducer-Consumer问题描述了一个生产者进问题描述了一个生产者进程（程（PPPP）生产消息，并提供给一个消费者（）生产消息，并提供给一个消费者（CPCP

3、）进程）进程消费。为使消费。为使PPPP和和CPCP能并发执行，设置一个有能并发执行，设置一个有n n个缓冲个缓冲区的缓冲池，区的缓冲池，PPPP将其生产的消息放入一缓冲区中，将其生产的消息放入一缓冲区中，CPCP可从一缓冲区取得消息。尽管所有可从一缓冲区取得消息。尽管所有PPPP和和CPCP都以异步方都以异步方式运行，但它们之间必须保持同步，即不允许式运行，但它们之间必须保持同步，即不允许CPCP到一到一空缓冲区取消息，也不允许空缓冲区取消息，也不允许PPPP向一满的缓冲区投放消向一满的缓冲区投放消息。息。0 01 12 23 35 54 4n-2n-2n-1n-1ininoutoutcou

4、ntercounter计数器输入指针输出指针 PP和CP共享的变量：Var n,integer;Type item=;Var buffer:array0,1n-1 of item;in,out:0,1n-1;counter:0,1n;PP:repeatPP:repeat produce an item in nextp;produce an item in nextp; while counter=n do no-op; while counter=n do no-op; bufferin:=nextp; bufferin:=nextp; in:=(in+1)mod n; in:=(in+1)

5、mod n; counter:=counter+1; counter:=counter+1; until false; until false;CP:repeatCP:repeat while counter=0 do no-op while counter=0 do no-op nextc:=bufferout; nextc:=bufferout; out:=(out+1)mod n; out:=(out+1)mod n; counter:=counter-1; counter:=counter-1; consume the item in nextc consume the item in

6、 nextc until false; until false; 以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的。但若并发执行就会出错，原因是这二个进程共享变量counter,生产者对它加1，消费者对它减1，这两个操作用机器语言实现时的形式可为： 设counter的当前值是5若按下述方式运行若按下述方式运行register1:=counter; register1:=counter; （register1:=5register1:=5） register1:=registe1+1register1:=registe1+1（register1:=6)register1:=6)regi

7、ster2:=counter;register2:=counter; (register2:=5) (register2:=5) register2:=registe2-1; register2:=registe2-1; (register2:=4) (register2:=4) counter:=register1 counter:=register1 (counter=6) (counter=6) counter:=register2;counter:=register2; (counter=4) (counter=4)Producer: register1:=counter;Produc

8、er: register1:=counter; register1:=registe1+1; register1:=registe1+1; counter:=register1; counter:=register1; Consumer: register2:=counter;Consumer: register2:=counter; register2:=registe2-1; register2:=registe2-1; counter:=register2; counter:=register2;(counter=5)(counter=5)countercounter正确的正确的答案答案

9、应应是是5 5，而而现现在是在是4 4故故应将应将countercounter作作为临为临界界资资源源处处理理临界区临界区临界区的定义临界区的定义定义：在每个进程中访问临界资源的那段代码称为临定义：在每个进程中访问临界资源的那段代码称为临界区（界区（critical section).critical section).若能保证诸进程互斥地进入自己的临界区，便可实现若能保证诸进程互斥地进入自己的临界区，便可实现它们对临界资源的互斥访问。为此，进程在进入临界它们对临界资源的互斥访问。为此，进程在进入临界区之前应检查欲访问的临界资源，若临界资源未被访区之前应检查欲访问的临界资源，若临界资源未被访问

10、，便可进入临界区，否则不能进入。因此须在临界问，便可进入临界区，否则不能进入。因此须在临界区前设置一段称为进入区区前设置一段称为进入区(entry section)(entry section)的代码段；的代码段；同样在其后加上一段称为退出区的代码段同样在其后加上一段称为退出区的代码段(exit (exit section)section)。进程中除进入区、临界区、及退出区之外。进程中除进入区、临界区、及退出区之外的其他代码段称为剩余区。的其他代码段称为剩余区。一一个访问临个访问临界界资资源的源的循循环进环进程描述如下：程描述如下： Repeat Repeat Entry sectionEnt

11、ry sectionCritical section;Critical section;Exit sectionExit sectionRemainder sectionRemainder sectionUntil false Until false 同步机制应遵循的准则空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态。可允许一请求进入临界区的进程立即进入自己的临界区。忙则等待：当已有进程进入到临界区时，表明临界资源正被访问，故其他试图进入临界区的进程必须等待。有限等待：对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等状态”。让权等待：当进程不能进入

12、自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。硬件同步机制硬件同步机制目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或是对两个字中的内容进行交换等，可利用这些特殊的指令来解决临界区问题。实际上，在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程，必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时，则应立即将其锁上，以阻止其他进程进入临界区。显然，为防止多个进程同时测试到锁开的情况，测试和关键操作必须是连续的，不允许分开进行。关中断关中断是实现互斥的最简单方法之一。

13、在进入锁测试之前，关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。关中断的缺点：1滥用关中断权力可能导致严重后果；2关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；3不适用于多处理器系统。利用利用test-and-set test-and-set 指令实现互斥指令实现互斥这是借助“测试并建立”硬件指令TS来实现互斥的方法，该指令的一般性描述为：Function TS(var lock:boolean):boolean Begin TS:=lock; Lock:=true; EndTS

14、指令可看作一个函数过程，其执行过程是不可分的，即是一条原语。其中，lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。 用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，用lock代表该资源的状态，可以看成一把锁，初值为false,表示该临界资源空闲，进程进入临界区之前，首先用TS指令测试lock，如果其值为false，则表示没有进程在临界区内，可以进入，并将lock赋值为true,这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试，直到TS(s)为false 。利用TS指令实现互斥的循环进程结构可描述为：

15、Reapt While TS(lock)do skip; Critical section; Lock:=false; Remainder section;Until false利用Swap指令实现进程互斥Swap称为对换指令，用于交换两个字的内容，其处理过程描述为：Procedure Swap(a,b:boolean) Var temp:boolean; Begin temp:=a; a:=b; b:=temp end 利用Swap实现互斥的方法是为每个临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中在利用一个局部布尔变量key，利用Swap指令实现进程互斥的循环进程可

16、描述为：Repeat key:=true; repeat Swap(lock,key); until key=false;临界区操作；Lock:=false;Until false; 利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访问进程必须不断地进行测试，处于一种“忙等”状态，不符合“让权等待”的原则，造成处理机时间浪费，同时也很难将它们用于复杂的进程同步问题。3.2 3.2 信号量机制信号量机制 信号量机制是一种有效的进程同步工具。 只能用于对一个临界资源实现互斥访问的信号量机制： 整型信号量 记录型信号量 能同时对多个临界资源实现互斥访问的信号量机制： “AND”信号量 信号

17、量集3.2.1 3.2.1 整型信号量和记录型信号量整型信号量和记录型信号量整型信号量整型信号量定义为一个用于表示资源数目的整型量整型信号量定义为一个用于表示资源数目的整型量S S，除初始化外，仅能通过两个标准的原子操作，除初始化外，仅能通过两个标准的原子操作wait(s)wait(s)和和signal(s)signal(s)来访问，这两个操作分别称为来访问，这两个操作分别称为P P、V V操作，可描述为：操作，可描述为： wait(s): while s0 do no-opwait(s): while s0 do no-op s:=s-1; s:=s-1; signal(s): s:=s+1

18、; signal(s): s:=s+1; wait(s)wait(s)和和signal(s)signal(s)是原子操作的含义：一是当一个是原子操作的含义：一是当一个进程在修改某信号量时，没有其他进程可同时对该信进程在修改某信号量时，没有其他进程可同时对该信息量进行修改；二是息量进行修改；二是waitwait操作中，对操作中，对s s值的测试和做值的测试和做s:=s-1s:=s-1操作时，都不可中断。操作时，都不可中断。 记录型信号量 注意到整型信号量机制的操作： wait(s):while s0 do no-op s:=s-1并未遵循“让权等待”的准则。但记录型信号量机制则不存在“忙等”问题

19、,但采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况，为此在信号量机制中采用记录型数据结构来构造记录型信号量，可描述为： type semaphore=record value:integer; /资源数目 L:list of process; /链接所有等待进程的 end 进程链表22相应地，wait(s)和signal(s)操作可描述为：Procedure wait(S) var S:semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); endProcedure signal(S) var

20、S:semaphore begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end记录型信号量初值表示系统中某类资源的数目,减1操作表示进程请求一个单位的资源.若小于0，表示资源已分配完毕,该进程调用阻塞原语,进行自我阻塞，放弃处理机，并插入到信号链表S.L中。此时S.value的绝对值表示在该信号链表中已阻塞的进程的数目。表示执行的进程释放一个单位的资源。若不大于0。表示在该信号链表中，仍有等待该资源的进程，故应调用唤醒原语，将S.L链表中的第一个等待进程唤醒。3.2.2 AND3.2.2 AND型信号量和信号量集型信号量和信号量集

21、ANDAND型信号量集型信号量集 整型和记录型信号量机制是针对进程间共享一个临界资源而言的。多个进程共享多个临界资源时则要采取另外的信号量机制。设A和B为进程，都要求访问共享数据D和E，这时D和E为临界资源。为D、E设置用于互斥的信号量Dmutex、Emutex，令初值为1，这时A和B有操作： Process A: process B: wait(Dmutex); wait(Emutex); wait(Emutex); wait(Dmutex);若若A A和和B B按下述次序按下述次序执执行行waitwait操作操作: : (Dmutex,Emutex(Dmutex,Emutex初初值为值为1

22、 1） processA:wait(Dmutex);/Dmutex=0 processA:wait(Dmutex);/Dmutex=0 processB:wait(Emutex);/Emutex=0 processB:wait(Emutex);/Emutex=0 processA:wait(Emutex);/Emutex=-1,AprocessA:wait(Emutex);/Emutex=-1,A阻塞阻塞processB:wait(Dmutex);/Dmutex=-1,BprocessB:wait(Dmutex);/Dmutex=-1,B阻塞阻塞 此此时时A A，B B进进入死入死锁状态锁状态

23、。显显然，然，进进程要求程要求的共享的共享资资源越多，死源越多，死锁锁的可能性越大。的可能性越大。 AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程用完后再一起释放，即对若干个临界资源的分配，采取原子操作方式要么全部分配到进程，要么一个也不分配，这样可避免死锁的情况发生。为此，在wait操作中增加一个“AND”条件，故称为AND同步，或称为同时wait操作，即SWait（Simultaneous Wait），其定义为：Swait(SSwait(S1 1,S,S2 2,S,Sn n) ) if S if S1 11and and S1and

24、 and Sn n1 then1 then for i :=1 to n do for i :=1 to n do S Si i :=S :=Si i-1;-1; endfor endfor else endif else endifSsignal(SSsignal(S1 1,S,S2 2,S,Sn n) ) for i :=1 to n do for i :=1 to n do S Si i :=S :=Si i+1;+1; ; ; endfor; endfor;信号量集机制在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1操作，既每次只能获得或释放一个单

25、位的临界资源。当一次需N个某类临界资源时，便需要做N次wait操作，这是低效的。另外有时当资源数量低于某一下限值时，便不分配资源给请求进程。因此，在每次分配之前，都必须测试该资源的数量是否大于测试值t。基于这二点可对AND信号量机制进行扩充，形成一般化的“信号量集”机制。SWait操作可描述为：Swait(S1,t1,d1,Sn,tn,dn) if S1t1 and and Sntn then for i:=1 to n do Si:=Si-di; endfor else Place the executing process in the waiting queue of the first

26、 Si with Si1S1）或互斥信）或互斥信号号量（量（S=1S=1）。）。（3 3）SwaitSwait（S S，1 1，0 0）。）。当当S S1 1时时，允，允许许多多个进个进程程进进入某特定入某特定区区；当当S S变为变为0 0后，后，将将阻止任何阻止任何进进程程进进入入特定特定区区。换换言之，言之，它它相相当当于一于一个个可控可控开关开关。是一。是一种种很特殊且很有用的信很特殊且很有用的信号号量。量。 Si:某类资源数量,ti:下限测试值, di:申请的资源数. 利用信号量实现进程互斥3.2.3 3.2.3 信号量的应用信号量的应用利用信号量实现进程互斥：利用信号量实现进程互斥：

27、var var mutex:semaghore:=1;mutex:semaghore:=1;beginbegin parbegin parbegin process1: begin process1: begin repeat repeat wait(mutex);wait(mutex); critical sectioncritical section signal(mutex);signal(mutex); remainder sectionremainder section until false; until false; end endprocess2:beginprocess2:b

28、egin repeat repeat wait(mutex);wait(mutex); critical sectioncritical section signal(mutex); signal(mutex); remainter sectionremainter section until false until false end end parend parendwait(mutex): while mutex0 do no-op mutex:=mutex-1; signal(mutex): mutex:=mutex+1; wait(mutex): while mutex0 do no

29、-op mutex:=mutex-1; signal(mutex): mutex:=mutex+1; 为使多个进程能互斥地访问某临界资源，而为该资源设置的一个互斥信号量。利用信号量实现前趋关系利用信号量实现前趋关系var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0begin begin parbegin parbegin begin S1;signal(a);signal(b);end; begin S1;signal(a);signal(b);end; begin wait(

30、a);S2;signal(c);signal(d);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(b);S3;signal(e);end; begin wait(b);S3;signal(e);end; begin wait(c);S4;signal(f);end; begin wait(c);S4;signal(f);end; begin wait(d);S5;signal(g);end; begin wait(d);S5;signal(g);end; begin wait(e);wait(f);wait(g);S6;en

31、d; begin wait(e);wait(f);wait(g);S6;end; parend parendend end S1S2S3S5S4S6abcdefg3.3 3.3 管程机制管程机制 管程的引入管程的引入 引入信号量机制的目的是为了消除与时间有关引入信号量机制的目的是为了消除与时间有关的错误，在信号量机制中每个要访问临界资源的错误，在信号量机制中每个要访问临界资源的进程都必须自备同步操作的进程都必须自备同步操作wait(s), wait(s), signal(s)signal(s)，就使大量的同步操作分散在各个，就使大量的同步操作分散在各个进程中，故容易因同步操作的使用不当而同样进

32、程中，故容易因同步操作的使用不当而同样会造成与时间有关的错误。例如：会造成与时间有关的错误。例如： 错误错误1 1：颠倒：颠倒wait(s)wait(s)和和signal(s)signal(s)使用顺序。使用顺序。 错误错误2 2：程序中的：程序中的signal(s)signal(s)被误写为被误写为wait(s)wait(s)。 错误错误3 3：程序中遗漏：程序中遗漏wait(s)wait(s)或或signal(s)signal(s)。 基于上述情况，基于上述情况，7070年代提出了管程的概念。年代提出了管程的概念。3.3.1 3.3.1 管程的定义管程的定义 系统中的各种软硬件资源，均可用

33、数据系统中的各种软硬件资源，均可用数据结构加以抽象描述，即用少量信息和对结构加以抽象描述，即用少量信息和对该资源所执行的操作来表征该资源，而该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。当共忽略它们的内部结构和实现细节。当共享资源用共享数据结构来表示时，资源享资源用共享数据结构来表示时，资源管理程序可用对该数据结构进行操作的管理程序可用对该数据结构进行操作的一组过程来表示。把这样一组相关的数一组过程来表示。把这样一组相关的数据结构和过程一并称为管程。据结构和过程一并称为管程。 定义（定义（HansanHansan）：一个管程定义了一个数据结）：一个管程定义了一个数据结构和能为

34、并发进程所执行（在该数据结构上）构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程的一组操作，这组操作能同步进程和改变管程中的数据。中的数据。 从定义知管程由四部分组成从定义知管程由四部分组成: (1): (1)管程的名称管程的名称(2)(2)局部于管程的共享数据结构说明；局部于管程的共享数据结构说明；(3)(3)对该对该数据结构进行操作的一组过程；数据结构进行操作的一组过程；(4)(4)对局部于对局部于管程的共享数据设置初始值的语句。管程的共享数据设置初始值的语句。 管程有一个重要的特性，即任一时刻管程中只管程有一个重要的特性，即任一时刻管程中只能有一个活跃进程

35、，从而能有效地完成互斥。能有一个活跃进程，从而能有效地完成互斥。 管程的语法为：管程的语法为：进进入入队队列列初始化代码一组操作过程条条件件队队列列管程示意图type monitor-name=monitor variable declarations procedure entry P1(); beginend; procedure entry Pn(); beginend;begin initialization codeend管程命名管程命名共享共享变变量量说说明明一一组过组过程程初始化初始化变变量量3.3.2 3.3.2 条件变量条件变量 利用管程实现进程同步时须设置两个同步操作原语利

36、用管程实现进程同步时须设置两个同步操作原语waitwait和和signalsignal。进程通过管程请求临界资源未果时，。进程通过管程请求临界资源未果时，管程调用管程调用waitwait原语使该进程等待，并将其排在等待队原语使该进程等待，并将其排在等待队列，仅当另一进程访问完并释放之后，管程又调用列，仅当另一进程访问完并释放之后，管程又调用signalsignal原语，唤醒等待队列中的队首进程。原语，唤醒等待队列中的队首进程。 为区别等待的原因，引入条件变量，且管程予以说明，为区别等待的原因，引入条件变量，且管程予以说明，其形式为：其形式为：var xvar x，y y：conditionco

37、ndition。变量置于。变量置于waitwait和和signalsignal之前，即之前，即x.waitx.wait和和x.signalx.signal。 x.signalx.signal的作用是重新启动一个被阻塞进程，若无进的作用是重新启动一个被阻塞进程，若无进程被阻塞，则程被阻塞，则x.signalx.signal不产生任何后果，与信号量机不产生任何后果，与信号量机制中的制中的signalsignal操作不同。因为后者总是要执行操作不同。因为后者总是要执行s:=s+1s:=s+1，总会改变信号量的状态。总会改变信号量的状态。3.3.3 3.3.3 利用管程解决生产者利用管程解决生产者消费

38、者问题消费者问题 解决该问题首先是为它们建立一个管程，命名解决该问题首先是为它们建立一个管程，命名为为PCPC。其中包含两个过程：。其中包含两个过程：（1 1）put(item)put(item)过程：生产者利用该过程将生产过程：生产者利用该过程将生产的消息投放到缓冲池，用整型变量的消息投放到缓冲池，用整型变量countcount表示表示缓冲池中已有的消息数，当缓冲池中已有的消息数，当countncountn时，表示时，表示缓冲池已满，生产者需等待。缓冲池已满，生产者需等待。（2 2）get(item)get(item)过程：消费者利用该过程从缓冲过程：消费者利用该过程从缓冲池中取得一个消息，

39、当池中取得一个消息，当count0count0时，表示缓冲时，表示缓冲池已无可用消息，消费者应等待。池已无可用消息，消费者应等待。 PCPC管程描述如下：管程描述如下：Type PC=monitorvar in,out,count:integer;buffer:array0,.,n-1 of item;notfull,notempty:condition;procedure entry put(x) begin if countn then notfull.wait;buffer(in):=x;in:=(in+1)mod n;count:=count+1;if notempty.queue t

40、hen notempty.signal; end procedure entry get(x) begin if count0 then notempty.wait; x:=buffer(out); out:=(out+1)mod n; count:=count-1; if notfull.queue then notfull.signal; endbegin in:=out:=0;count:=0;end因池中无空因池中无空缓缓冲冲区区而等待，此而等待，此时调时调用用管程中管程中该过该过程的程的进进程排入等待空程排入等待空缓缓冲冲区队区队列。列。若等待若等待满缓满缓冲冲区队区队列列中有中有进

41、进程，程，则唤则唤醒醒对对首首进进程。若无程。若无则则什什么么都不做。都不做。因池中无因池中无满缓满缓冲冲区区而等待，此而等待，此时时调调用管程中用管程中该过该过程的程的进进程排入等程排入等待待满缓满缓冲冲区队区队列。列。在利用管程解在利用管程解决决生生产产者者消消费费者者问题时问题时，其中的生，其中的生产产者和消者和消费费者可描述者可描述为为： Producer:begin repeat produce an item in nextp; PC.put(nextpnextp); until false； end Consumer:begin repeat PC.get(nextcnextc)

42、; consume the item in nextc ; until false; end 3.4 3.4 经典进程同步问题经典进程同步问题3.4.1 3.4.1 生产者生产者消费者问题消费者问题 The Proceducer-Consumer ProblemThe Proceducer-Consumer Problem是相互是相互合作进程关系的一种抽象，有很大的代表性和合作进程关系的一种抽象，有很大的代表性和实用价值。实用价值。一、利用记录型信号量解决生产者一、利用记录型信号量解决生产者消费者问题：消费者问题：设在生产者和消费者之间的共用缓冲池中有设在生产者和消费者之间的共用缓冲池中有n

43、n个缓冲区，利用互斥信号量个缓冲区，利用互斥信号量mutexmutex使诸进程实使诸进程实现对缓冲池的互斥使用；利用资源信号量现对缓冲池的互斥使用；利用资源信号量emptyempty和和 fullfull分别表示池中空缓冲区和满缓冲分别表示池中空缓冲区和满缓冲区数量。此问题可描述如下：区数量。此问题可描述如下：var mutex,empty,full:var mutex,empty,full:semaphore:=1,n,0;semaphore:=1,n,0;buffer:array0,n-1ofbuffer:array0,n-1of item; in,out:integer:=0,0; it

44、em; in,out:integer:=0,0;beginbegin parbegin parbegin producer:begin producer:begin repeat repeat produce an item in nextp; produce an item in nextp; wait(empty);wait(empty); wait(mutex);wait(mutex); buffer(in):=nextp; buffer(in):=nextp; in:=(in+1)mode n; in:=(in+1)mode n; signal(mutex);signal(mutex)

45、; signal(full);signal(full); until false; end until false; end consumer:beginconsumer:begin repeat repeat wait(full);wait(full); wait(mutex);wait(mutex); nextc:=buffer(out); nextc:=buffer(out); out:=(out+1)mod n; out:=(out+1)mod n; signal(mutex);signal(mutex); signal(empty);signal(empty);consume the

46、 item in nextc;consume the item in nextc; until false;end until false;end parend; end parend; end应应注意的注意的问题问题： 1、每、每个个程序中用于程序中用于实现实现互斥的互斥的wait(mutex)和和signal(mutex)必必须须成成对对出出现现。 2、对资对资源信源信号号量量empty和和full的的Wait和和signal操作，操作，须须成成对对出出现现，但分但分别处别处于不同的程序中。于不同的程序中。 3、应应先先执执行行对资对资源信源信号号量的量的Wait操作，然后再操作，然后再执

47、执行行对对互斥互斥信信号号量的量的wait操作，操作，顺顺序不能序不能颠颠倒。否倒。否则则可能引起死可能引起死锁锁。 Procedure wait(s) var s:semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); endProcedure signal(s) var s:semaphore begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end3.4.2 3.4.2 哲学家进餐问题哲学家进餐问题一、利用记录型信号量解决哲学家一、利用记录型信号量解决

48、哲学家进餐问题进餐问题var chopstick:array0,4 of semaphore; 第i个哲学家的活动可描述为：repeat wait(chopsticki); wait(chopstick(i=+1)mod5); eat; signal(chopsticki);signal (chopstick (i=+1)mod5); think until false 该解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。对于死锁的问题有几种解决方法。见P78。0432104321利用记录型信号量解决哲学家进利用记录型信号量解决哲学家进餐问题餐问题var chopstick:array

49、0,4 of var chopstick:array0,4 of semaphore;/semaphore;/初始值为初始值为1 1 第第i i个哲学家的活动可描述为：个哲学家的活动可描述为：repeatrepeat wait(chopsticki); wait(chopsticki); wait(chopstick(i+1)mod5); wait(chopstick(i+1)mod5); eat; eat; signal(chopsticki); signal(chopsticki);signal (chopstick (i+1)mod5);signal (chopstick (i+1)mo

50、d5); think until false 该解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。对于死锁的问题有几种解决方法。 例如：例如：5 5个哲学家同时饥饿而各自拿起左边的个哲学家同时饥饿而各自拿起左边的筷子，当他们试图去拿右边的筷子时，因无筷筷子，当他们试图去拿右边的筷子时，因无筷子可拿而无限期地等待。从而死锁。子可拿而无限期地等待。从而死锁。 解决死锁的方法有几种：解决死锁的方法有几种： 至多只允许至多只允许4 4个哲学家同时进餐，以保证有个哲学家同时进餐，以保证有1 1个个哲学家能够进餐。哲学家能够进餐。 仅当哲学家左右两边的筷子都可用时，才允许仅当哲学家左右两边的筷子都

51、可用时，才允许拿起筷子进餐。拿起筷子进餐。规定奇数号哲学家先拿他左边的筷子，然后再规定奇数号哲学家先拿他左边的筷子，然后再拿右边的筷子；偶数号哲学家先拿他右边的筷拿右边的筷子；偶数号哲学家先拿他右边的筷子，然后再拿左边的筷子。子，然后再拿左边的筷子。 利用管程解决哲学家进餐问题利用管程解决哲学家进餐问题哲学家可以处于进餐、饥饿和思考这三种状哲学家可以处于进餐、饥饿和思考这三种状态之一。相应地引入数据结构：态之一。相应地引入数据结构： var state:array04of (think,hungry,eat)var state:array04of (think,hungry,eat)为每一位哲

52、学家设置一个条件变量为每一位哲学家设置一个条件变量self(i)self(i)，每每 当哲学家饥饿，但又得不到进餐所需的筷当哲学家饥饿，但又得不到进餐所需的筷子子 时，他可以执行时，他可以执行self(i).waitself(i).wait操作，来推操作，来推迟进餐，条件变量可描述为：迟进餐，条件变量可描述为： var self:array04of conditionvar self:array04of condition在管程中还设置三个过程：在管程中还设置三个过程：（1 1）pickup(i:04)pickup(i:04)过程。在哲学家进程过程。在哲学家进程中，可利用该过程去进餐。某哲学家

53、饥中，可利用该过程去进餐。某哲学家饥饿时，且其左、右两边的哲学家都未进饿时，且其左、右两边的哲学家都未进餐，则他可以进餐。餐，则他可以进餐。 但只要其左右两位有一位在进餐，他但只要其左右两位有一位在进餐，他便不能进餐，此时执行便不能进餐，此时执行self(i).waitself(i).wait操操作来推迟自己的进餐。作来推迟自己的进餐。（2 2）putdown(i:04)putdown(i:04)过程。哲学家进餐毕，他过程。哲学家进餐毕，他去看其左右两边的哲学家，若他们都饥饿且他去看其左右两边的哲学家，若他们都饥饿且他左右两边的哲学家都未用餐时，便可让他们进左右两边的哲学家都未用餐时，便可让他

54、们进餐。餐。（3 3）test(i:04)test(i:04)。该过程为测试过程，用它。该过程为测试过程，用它去测试哲学家是否已具备用餐条件，即去测试哲学家是否已具备用餐条件，即statek+4mod 5eat and statek=hungry statek+4mod 5eat and statek=hungry and statek+1mod 5eatand statek+1mod 5eat条件是否为真。若条件是否为真。若为真，方允许哲学家进餐。该过程被为真，方允许哲学家进餐。该过程被pickuppickup和和putdownputdown两过程所调用。两过程所调用。 Type DP=mo

55、nitorType DP=monitorvar state: array04of var state: array04of (think,hungry,eat);(think,hungry,eat);var self: array04ofvar self: array04ofcondition;condition;procedure entry pickup(i:04);procedure entry pickup(i:04); begin begin statei:=hungry; test(i); statei:=hungry; test(i);if statei eat then sel

56、fi.if statei eat then selfi.wait;wait; end; end;procedure entry putdown(i:04);procedure entry putdown(i:04);begin statei:=think;begin statei:=think;test(i+4mod 5);test(i+4mod 5);test(i+1mod 5); endtest(i+1mod 5); endprocedure test(k:04)procedure test(k:04)beginbegin if statek+4 mod 5eat if statek+4

57、mod 5eat and statek=hungry and statek=hungry and statek+1mod5eat and statek+1mod5eat then begin then begin statek:=eat; statek:=eat; selfk.signal; selfk.signal; end; end; end end beginbegin for i:=0 to 4 for i:=0 to 4 do statei:=think; do statei:=think; end end3.4.3 3.4.3 读者读者写者问题写者问题 一个数据文件或记录一个数据文

58、件或记录(统称数据对象统称数据对象)可被多可被多个进程共享。其中有些进程在读（个进程共享。其中有些进程在读（reader进进程）；另一些进程要对数据对象进行写或修程）；另一些进程要对数据对象进行写或修改（改（writer进程）。允许多个进程）。允许多个reader进程同时进程同时读一共享对象，但绝不允许一个读一共享对象，但绝不允许一个writer进程进程和其他的和其他的reader进程或进程或writer进程同时访问共进程同时访问共享对象。所谓享对象。所谓The Reader-Writer Problem，是指保证一个是指保证一个writer进程必须与其他进程互进程必须与其他进程互斥地访问共享

59、对象的同步问题。斥地访问共享对象的同步问题。 var rmutex,wmutex:semaphore:=1,1;readcount:intger:=0;beginparbegin reader:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); Perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); sign

60、al(rmutex); until false;endwriter:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; endparend end为实现reader进程与writer进程读或写时的互斥，而设置的互斥信号量。表示正在读的进程数目。因为readcount是一个可被多个reader进程访问的临界资源，故应为它设置一互斥信号量rmutex。由于只要有一个reader进程在读，便不允许writer进程去写。故当readcount=0时，表示尚无reader进程在读，这时reade