《《计算机操作系统》课件.ppt》由会员分享，可在线阅读，更多相关《《计算机操作系统》课件.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、湘 潭 大 学第第3 3章章进程的同步与通信进程的同步与通信进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同步的主要任务，是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。3.1 3.1 进程同步的基本概念进程同步的基本概念1.进程间的相互制约关系在多道程序环境下，系统中可能有着许多进程，这些进程之间可能存在以下两种关系。间接相互制约关的系：多个进程之间彼此无关，并不知道其他进程的存在，但这些进程既然同处于一个系统中，也就必然存在资源共享的关系，如共享CPU、I/O设备等。此时进程同步的主要任务是保证诸进程能互斥地访问临界资源。这样，系统中的资源应由
2、系统统一管理，不允许用户进程直接使用。直接相互制约的关系：在某些进程间还存在相互合作关系，此时进程同步的主要任务是保证诸进程在执行次序上的协调，不会出现与时间有关的差错。2.2.临界资源临界资源临界资源，也称独占资源，是在一段时间内只允许一临界资源，也称独占资源，是在一段时间内只允许一个进程访问的资源。对临界资源，进程间应采取互斥个进程访问的资源。对临界资源，进程间应采取互斥方式共享。方式共享。例子：例子：Producer-Producer-ConsumerConsumer问题描述了一个生产者进程（问题描述了一个生产者进程（PPPP）生产消息）生产消息，并提供给一个消费者（，并提供给一个消费者
3、（CPCP）进程消费。为使）进程消费。为使PPPP和和CPCP能并发执行，设置一个有能并发执行，设置一个有n n个缓冲区的缓冲池，个缓冲区的缓冲池，PPPP将将其生产的消息放入一缓冲区中，其生产的消息放入一缓冲区中，CPCP可从一缓冲区取得可从一缓冲区取得消息。尽管所有消息。尽管所有PPPP和和CPCP都以异步方式运行，但它们之都以异步方式运行，但它们之间必须保持同步，即不允许间必须保持同步，即不允许CPCP到一空缓冲区取消息，到一空缓冲区取消息，也不允许也不允许PPPP向一满的缓冲区投放消息。向一满的缓冲区投放消息。0 01 12 23 35 54 4n-2n-2n-1n-1ininouto
4、utcountercounter计数器输入指针输出指针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)mo
5、d 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 nextc until
6、 false;until false;以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的。但若并发执行就会出错，原因是这二个进程共享变量counter,生产者对它加1，消费者对它减1，这两个操作用机器语言实现时的形式可为：设counter的当前值是5若按下述方式运行若按下述方式运行register1:=counter;register1:=counter;（register1:=5register1:=5）register1:=registe1+1register1:=registe1+1（register1:=6)register1:=6)register2:=counter;reg
7、ister2:=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;Producer:register1:=counter;register
8、1:=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正确的正确的答案答案应是是5 5，而而现在是在是4 4故故应将将countercounter作作为临界界
9、资源源处理理3.3.临界区临界区临界区的定义临界区的定义定义：在每个进程中访问临界资源的那段代码称为临定义：在每个进程中访问临界资源的那段代码称为临界区（界区（critical section).critical section).若能保证诸进程互斥地进入自己的临界区，便可实现若能保证诸进程互斥地进入自己的临界区，便可实现它们对临界资源的互斥访问。为此，进程在进入临界它们对临界资源的互斥访问。为此，进程在进入临界区之前应检查欲访问的临界资源，若临界资源未被访区之前应检查欲访问的临界资源，若临界资源未被访问，便可进入临界区，否则不能进入。因此须在临界问，便可进入临界区，否则不能进入。因此须在临界
10、区前设置一段称为进入区区前设置一段称为进入区(entry(entry section)section)的代码段；同样在其后加上一段称为退出区的代码段；同样在其后加上一段称为退出区的代码段的代码段(exit(exit section)section)。进程中除进入区、临界区、及退出区之外。进程中除进入区、临界区、及退出区之外的其他代码段称为剩余区。的其他代码段称为剩余区。一一个个访问临界界资源的源的循循环进程描述如下：程描述如下：Repeat Repeat Entry sectionEntry sectionCritical section;Critical section;Exit secti
11、onExit sectionRemainder sectionRemainder sectionUntil false Until false 同步机制应遵循的准则空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态。可允许一请求进入临界区的进程立即进入自己的临界区。忙则等待：当已有进程进入到临界区时，表明临界资源正被访问，故其他试图进入临界区的进程必须等待。有限等待：对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等状态”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。4.4.硬件同步机制硬件同步机制目前许多计算机已提供
12、了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或是对两个字中的内容进行交换等，可利用这些特殊的指令来解决临界区问题。实际上，在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程，必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时，则应立即将其锁上，以阻止其他进程进入临界区。显然，为防止多个进程同时测试到锁开的情况，测试和关键操作必须是连续的，不允许分开进行。关中断关中断是实现互斥的最简单方法之一。在进入锁测试之前，关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机
13、系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。关中断的缺点：1滥用关中断权力可能导致严重后果；2关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；3不适用于多处理器系统。利用利用test-and-set test-and-set 指令实现互斥指令实现互斥这是借助“测试并建立”硬件指令TS来实现互斥的方法，该指令的一般性描述为：Function TS(var lock:boolean):boolean Begin TS:=lock;Lock:=true;EndTS指令可看作一个函数过程，其执行过程是不可分的，即是一条原语。其中，lock有两种状态：当lock=fal
14、se时，表示该资源空闲；当lock=true时，表示该资源正在被使用。用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，用lock代表该资源的状态，可以看成一把锁，初值为false,表示该临界资源空闲，进程进入临界区之前，首先用TS指令测试lock，如果其值为false，则表示没有进程在临界区内，可以进入，并将lock赋值为true,这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试，直到TS(s)为false。利用TS指令实现互斥的循环进程结构可描述为：Reapt While TS(lock)do skip;Critical section;Lock:=fal
15、se;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指令实现进程互斥的循环进程可描述为：Repeat key:=true;repeat Swap(lock,key);until key=false;临界区
16、操作；Lock:=false;Until false;利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访问进程必须不断地进行测试，处于一种“忙等”状态，不符合“让权等待”的原则，造成处理机时间浪费，同时也很难将它们用于复杂的进程同步问题。3.2 3.2 信号量机制信号量机制信号量机制是一种有效的进程同步工具。只能用于对一个临界资源实现互斥访问的信号量机制：整型信号量记录型信号量能同时对多个临界资源实现互斥访问的信号量机制：“AND”信号量信号量集3.2.1 3.2.1 整型信号量和记录型信号量整型信号量和记录型信号量1.整型信号量整型信号量定义为一个用于表示资源数目的整型量整型信号量
17、定义为一个用于表示资源数目的整型量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;signal(s):s:=s+1;wait(s)wait(s)和和signal(s)signal(s)是原子操作的含义：一是当一个是原子操作的含义：一是
18、当一个进程在修改某信号量时，没有其他进程可同时对该信进程在修改某信号量时，没有其他进程可同时对该信息量进行修改；二是息量进行修改；二是waitwait操作中，对操作中，对s s值的测试和做值的测试和做s:s:=s-1=s-1操作时，都不可中断。操作时，都不可中断。2.记录型信号量 注意到整型信号量机制的操作：wait(s):while s0 do no-op s:=s-1并未遵循“让权等待”的准则。但记录型信号量机制则不存在“忙等”问题,但采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况，为此在信号量机制中采用记录型数据结构来构造记录型信号量，可描述为：type sema
19、phore=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 S:semaphore begin S.value:=S.value+1;if S.value0 then wakeup(S.L);end记录型信号量初值表示系统中某类资源的数
20、目,减1操作表示进程请求一个单位的资源.若小于0，表示资源已分配完毕,该进程调用阻塞原语,进行自我阻塞，放弃处理机，并插入到信号链表S.L中。此时S.value的绝对值表示在该信号链表中已阻塞的进程的数目。表示执行的进程释放一个单位的资源。若不大于0。表示在该信号链表中，仍有等待该资源的进程，故应调用唤醒原语，将S.L链表中的第一个等待进程唤醒。3.2.2 AND3.2.2 AND型信号量和信号量集型信号量和信号量集1.1.ANDAND型信号量集型信号量集 整型和记录型信号量机制是针对进程间共享一个临界资源而言的。多个进程共享多个临界资源时则要采取另外的信号量机制。设A和B为进程，都要求访问共
21、享数据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 1）processA:wait(Dmutex);/Dmutex=0 processA:wait(Dmutex);/Dmutex=0 processB:wait(Emutex);/Emutex=0
22、 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进入死入死锁状状态。显然，然，进程要求程要求的共享的共享资源越多，死源越多，死锁的可能性越大。的可能性越大。AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程用完后再一起
23、释放，即对若干个临界资源的分配，采取原子操作方式要么全部分配到进程，要么一个也不分配，这样可避免死锁的情况发生。为此，在wait操作中增加一个“AND”条件，故称为AND同步，或称为同时wait操作，即SWait（Simultaneous Wait），其定义为：Swait(SSwait(S1 1,S,S2 2,S,Sn n)if S if S1 11and and S1and 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 endi
24、fSsignal(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;2.信号量集机制在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1操作，既每次只能获得或释放一个单位的临界资源。当一次需N个某类临界资源时，便需要做N次wait操作，这是低效的。另外有时当资源数量低于某一下限值时，便不分配资源给请求进程。因此，在每次分配之前，都必须测试该资源的数量是否大于测试值t。基于这二点可对AND信号量机制进行扩充，形成一般化的
25、“信号量集”机制。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 Si with Si1S1）或互斥信）或互斥信号号量（量（S=1S=1）。）。（3 3）SwaitSwait（S S，1 1，0 0）。）。当当S S 1 1时，允，允许多多个个进程程进入某特定入某特定区区；当当S S变为0 0后，后，将将阻止任何阻止任何
26、进程程进入入特定特定区区。换言之，言之，它它相相当当于一于一个个可控可控开关开关。是一。是一种种很特殊且很有用的信很特殊且很有用的信号号量。量。Si:某类资源数量,ti:下限测试值,di:申请的资源数.1.利用信号量实现进程互斥3.2.3 3.2.3 信号量的应用信号量的应用1.1.利用信号量实现进程互斥：利用信号量实现进程互斥：var var mutex:semaghore:=1;mutex:semaghore:=1;beginbegin parbegin parbegin process1:begin process1:begin repeat repeat wait(mutex);wai
27、t(mutex);critical sectioncritical section signal(mutex);signal(mutex);remainder sectionremainder section until false;until false;end endprocess2:beginprocess2:begin repeat repeat wait(mutex);wait(mutex);critical sectioncritical section signal(mutex);signal(mutex);remainter sectionremainter section u
28、ntil 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-op mutex:=mutex-1;signal(mutex):mutex:=mutex+1;为使多个进程能互斥地访问某临界资源，而为该资源设置的一个互斥信号量。2.2.利用信号量实现前趋关系利用信号量实现前趋关系var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0
29、,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(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
30、;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;end;begin wait(e);wait(f);wait(g);S6;end;parend parendend end S1S2S3S5S4S6abcdefg3.3 3.3 管程机制管程机制管程的引入管程的引入引入信号量机制的目的是为了消除与时间有关引入信号量机制的目的是为了消除与时间有关的错误，在信号量机制中每
31、个要访问临界资源的错误，在信号量机制中每个要访问临界资源的进程都必须自备同步操作的进程都必须自备同步操作wait(s),wait(s),signal(s)signal(s)，就使大量的同步操作分散在各个，就使大量的同步操作分散在各个进程中，故容易因同步操作的使用不当而同样进程中，故容易因同步操作的使用不当而同样会造成与时间有关的错误。例如：会造成与时间有关的错误。例如：错误错误1 1：颠倒：颠倒wait(s)wait(s)和和signal(s)signal(s)使用顺序。使用顺序。错误错误2 2：程序中的：程序中的signal(s)signal(s)被误写为被误写为wait(s)wait(s)
32、。错误错误3 3：程序中遗漏：程序中遗漏wait(s)wait(s)或或signal(s)signal(s)。基于上述情况，基于上述情况，7070年代提出了管程的概念。年代提出了管程的概念。3.3.1 3.3.1 管程的定义管程的定义系统中的各种软硬件资源，均可用数据系统中的各种软硬件资源，均可用数据结构加以抽象描述，即用少量信息和对结构加以抽象描述，即用少量信息和对该资源所执行的操作来表征该资源，而该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。当共忽略它们的内部结构和实现细节。当共享资源用共享数据结构来表示时，资源享资源用共享数据结构来表示时，资源管理程序可用对该数据结构进
33、行操作的管理程序可用对该数据结构进行操作的一组过程来表示。把这样一组相关的数一组过程来表示。把这样一组相关的数据结构和过程一并称为管程。据结构和过程一并称为管程。定义（定义（HansanHansan）：一个管程定义了一个数据结）：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程的一组操作，这组操作能同步进程和改变管程中的数据。中的数据。从定义知管程由四部分组成从定义知管程由四部分组成:(1)(1)管程的名称管程的名称(2)(2)局部于管程的共享数据结构局部于管程的共享数据结构说明；说明；(3)(3)
34、对该数据结构进行操作的一组过程对该数据结构进行操作的一组过程；(4)(4)对局部于管程的共享数据设置初始值的对局部于管程的共享数据设置初始值的语句。语句。管程有一个重要的特性，即任一时刻管程中只管程有一个重要的特性，即任一时刻管程中只能有一个活跃进程，从而能有效地完成互斥。能有一个活跃进程，从而能有效地完成互斥。管程的语法为：管程的语法为：进入入队列列初始化代码一组操作过程条条件件队列列管程示意图type monitor-name=monitor variable declarations procedure entry P1();beginend;procedure entry Pn();b
35、eginend;begin initialization codeend管程命名管程命名共享共享变量量说明明一一组过程程初始化初始化变量量3.3.2 3.3.2 条件变量条件变量利用管程实现进程同步时须设置两个同步操作原语利用管程实现进程同步时须设置两个同步操作原语waiwait t和和signalsignal。进程通过管程请求临界资源未果时，管程。进程通过管程请求临界资源未果时，管程调用调用waitwait原语使该进程等待，并将其排在等待队列，原语使该进程等待，并将其排在等待队列，仅当另一进程访问完并释放之后，管程又调用仅当另一进程访问完并释放之后，管程又调用signalsignal原语，唤
36、醒等待队列中的队首进程。原语，唤醒等待队列中的队首进程。为区别等待的原因，引入条件变量，且管程予以说明为区别等待的原因，引入条件变量，且管程予以说明，其形式为：，其形式为：var var x x，y y：conditioncondition。变量置于。变量置于waitwait和和signalsignal之前，即之前，即x.x.waitwait和和x.signalx.signal。x.signalx.signal的作用是重新启动一个被阻塞进程，若无进的作用是重新启动一个被阻塞进程，若无进程被阻塞，则程被阻塞，则x.signalx.signal不产生任何后果，与信号量机不产生任何后果，与信号量机制
37、中的制中的signalsignal操作不同。因为后者总是要执行操作不同。因为后者总是要执行s:=s+1s:=s+1，总会改变信号量的状态。，总会改变信号量的状态。3.3.3 3.3.3 利用管程解决生产者利用管程解决生产者消费者问题消费者问题解决该问题首先是为它们建立一个管程，命名解决该问题首先是为它们建立一个管程，命名为为PCPC。其中包含两个过程：。其中包含两个过程：（1 1）put(item)put(item)过程：生产者利用该过程将生产过程：生产者利用该过程将生产的消息投放到缓冲池，用整型变量的消息投放到缓冲池，用整型变量countcount表示表示缓冲池中已有的消息数，当缓冲池中已有
38、的消息数，当countncountn时，表示时，表示缓冲池已满，生产者需等待。缓冲池已满，生产者需等待。（2 2）get(item)get(item)过程：消费者利用该过程从缓冲过程：消费者利用该过程从缓冲池中取得一个消息，当池中取得一个消息，当count0count0时，表示缓冲时，表示缓冲池已无可用消息，消费者应等待。池已无可用消息，消费者应等待。PCPC管程描述如下：管程描述如下：Type PC=monitorvar in,out,count:integer;buffer:array0,.,n-1 of item;notfull,notempty:condition;procedure
39、entry put(x)begin if countn then notfull.wait;buffer(in):=x;in:=(in+1)mod n;count:=count+1;if notempty.queue then 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;coun
40、t:=0;end因池中无空因池中无空缓冲冲区区而等待，此而等待，此时调用用管程中管程中该过程的程的进程排入等待空程排入等待空缓冲冲区区队列。列。若等待若等待满缓冲冲区区队列列中有中有进程，程，则唤醒醒对首首进程。若无程。若无则什什么么都不做。都不做。因池中无因池中无满缓冲冲区区而等待，此而等待，此时调用管程中用管程中该过程的程的进程排入等程排入等待待满缓冲冲区区队列。列。在利用管程解在利用管程解决决生生产者者消消费者者问题时，其中的生，其中的生产者和消者和消费者可描述者可描述为：Producer:begin repeat produce an item in nextp;PC.put(next
41、pnextp);until false；end Consumer:begin repeat PC.get(nextcnextc);consume the item in nextc;until false;end 3.4 3.4 经典进程同步问题经典进程同步问题3.4.1 3.4.1 生产者生产者消费者问题消费者问题 The Proceducer-Consumer The Proceducer-Consumer ProblemProblem是相互合作进程关系的一种抽象，有是相互合作进程关系的一种抽象，有很大的代表性和实用价值。很大的代表性和实用价值。一、利用记录型信号量解决生产者一、利用记录型
42、信号量解决生产者消费者问题：设在生产者和消费者之间的共用消费者问题：设在生产者和消费者之间的共用缓冲池中有缓冲池中有n n个缓冲区，利用互斥信号量个缓冲区，利用互斥信号量mutexmutex使诸进程实现对缓冲池的互斥使用；利用资源使诸进程实现对缓冲池的互斥使用；利用资源信号量信号量emptyempty和和 fullfull分别表示池中空缓冲区和满缓冲区数量。分别表示池中空缓冲区和满缓冲区数量。此问题可描述如下：此问题可描述如下：var mutex,empty,full:var mutex,empty,full:semaphore:=1,n,0;semaphore:=1,n,0;buffer:a
43、rray0,n-1ofbuffer:array0,n-1of item;in,out:integer:=0,0;item;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)mo
44、de n;in:=(in+1)mode n;signal(mutex);signal(mutex);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);s
45、ignal(empty);signal(empty);consume the item in consume the item in nextc;nextc;until false;end until false;end parend;end parend;end应注意的注意的问题：1、每、每个个程序中用于程序中用于实现互斥的互斥的wait(mutex)和和signal(mutex)必必须成成对出出现。2、对资源信源信号号量量empty和和full的的Wait和和signal操作，操作，须成成对出出现，但分但分别处于不同的程序中。于不同的程序中。3、应先先执行行对资源信源信号号量的量的Wait
46、操作，然后再操作，然后再执行行对互斥互斥信信号号量的量的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 哲学家进餐问题哲学家进餐问题一、利用记录型信号量解决哲学家一、利用记录型信号量解决哲
47、学家进餐问题进餐问题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。04321043211.1.利用记录型信号量解决哲学家进利用记录型信号量解决哲学家进餐问题餐问题var chopstick:array0,4
48、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)mod5);think until
49、 false该解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。对于死锁的问题有几种解决方法。例如：例如：5 5个哲学家同时饥饿而各自拿起左边的个哲学家同时饥饿而各自拿起左边的筷子，当他们试图去拿右边的筷子时，因无筷筷子，当他们试图去拿右边的筷子时，因无筷子可拿而无限期地等待。从而死锁。子可拿而无限期地等待。从而死锁。解决死锁的方法有几种：解决死锁的方法有几种：至多只允许至多只允许4 4个哲学家同时进餐，以保证有个哲学家同时进餐，以保证有1 1个哲学家能够进餐。个哲学家能够进餐。仅当哲学家左右两边的筷子都可用时，才允仅当哲学家左右两边的筷子都可用时，才允许拿起筷子进餐。许拿起筷子进餐。
50、规定奇数号哲学家先拿他左边的筷子，然后规定奇数号哲学家先拿他左边的筷子，然后再拿右边的筷子；偶数号哲学家先拿他右边再拿右边的筷子；偶数号哲学家先拿他右边的筷子，然后再拿左边的筷子。的筷子，然后再拿左边的筷子。2.2.利用管程解决哲学家进餐问题利用管程解决哲学家进餐问题哲学家可以处于进餐、饥饿和思考这三种状态哲学家可以处于进餐、饥饿和思考这三种状态之一。相应地引入数据结构：之一。相应地引入数据结构：var state:array04of var state:array04of(think,hungry,eat)(think,hungry,eat)为每一位哲学家设置一个条件变量为每一位哲学家设置一