《计算机操作系统教案_第02章 进程管理(2进程同步).ppt》由会员分享，可在线阅读，更多相关《计算机操作系统教案_第02章 进程管理(2进程同步).ppt（110页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 进 程 管 理 计算机操作系统教案计算机操作系统教案第第2章进程管理章进程管理郭霞郭霞1第二章 进 程 管 理 2.3 进进 程程 互斥与同互斥与同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1.程序执行并发性的产生环境程序执行并发性的产生环境(1)单CPU的多道批处理系统(2)多多CPU系统系统2第二章 进 程 管 理 2.3 进进 程程 互斥与同互斥与同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 2.并发引起的问题并发引起的问题(1)失去封闭性，进程间临界资源的竞争，称为间接制约。(2)结果的不可再现性，进程间数据合作，称为直接制约临界资源：硬临界资源、
2、软临界资源临界区3第二章 进 程 管 理 分析下列活动属于什么制约关系若干同学去图书馆借书两队举行篮球比赛流水线生产的各道工序之间商品的生产和社会的消费4第二章 进 程 管 理 2.3 进进 程程 互斥与同互斥与同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 3.进程同步的概念进程同步的概念指多个相关进程在执行次序上的协调，用于保证这种关系的相应机制称为同步机制5第二章 进 程 管 理 2.3 进进 程程 互斥与同互斥与同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 4.进程同步的技术进程同步的技术(1)互斥机制：解决临界资源的竞争问题。会引起另外两个问题a)进程的死锁
3、b)进程饿死：P1,P2,P3都需要访问资源R，那么有可能只在P1P3之间轮流，P2永远都不能执行。6第二章 进 程 管 理 2.3 进进 程程 互斥与同互斥与同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 4.进程同步的技术进程同步的技术（2）进程间合作的技术a.共享数据（变量、文件、数据库）b.通信7第二章 进 程 管 理 5.同步机制应遵循的设计规则同步机制应遵循的设计规则(1)空闲让进：空闲让进：临界资源空闲，应允许请求进入。(2)(2)忙则等待：忙则等待：临界资源忙，其余程序等待。(3)(3)有限等待：有限等待：要求访问临界资源的进程，不能饿死(4)(4)让权等待：让权等
4、待：不能进入临界区的进程，释放CPU8第二章 进 程 管 理 2.3.2 信号量信号量(Semaphores)机制机制 1.整型信号量整型信号量 最最初初由由Dijkstra把把整整型型信信号号量量定定义义为为一一个个整整型型量量，除除初初始始化化外外，仅仅能能通通过过两两个个标标准准的的原原子子操操作作(Atomic Operation)wait(S)和和signal(S)来来访访问问。这这两两个个操操作作一一直直被被分分别别称称为为P、V操作。操作。wait和和signal操作可描述为：操作可描述为：wait(S):while S0 do no-op S=S-1;signal(S):S =
5、S+1;9第二章 进 程 管 理 2.记录型信号量记录型信号量 在在整整型型信信号号量量机机制制中中的的wait操操作作，只只要要是是信信号号量量S0，就就会会不不断断地地测测试试。因因此此，该该机机制制并并未未遵遵循循“让让权权等等待待”的的准准则则，而而是是使使进进程程处处于于“忙忙等等”的的状状态态。记记录录型型信信号号量量机机制制，则则是是一一种种不不存存在在“忙忙等等”现现象象的的进进程程同同步步机机制制。但但在在采采取取了了“让让权权等等待待”的的策策略略后后，又又会会出出现现多多个个进进程程等等待待访访问问同同一一临临界界资资源源的的情情况况。为为此此，在在信信号号量量机机制制中
6、中，除除了了需需要要一一个个用用于于代代表表资资源源数数目目的的整整型型变变量量value外外，还还应应增增加加一一个个进进程程链链表表L，用用于于链链接接上上述述的的所所有有等等待待进进程程。记记录录型型信信号号量量是是由由于于它它采采用用了了记记录录型型的的数数据据结结构构而而得得名名的的。它它所所包包含的上述两个数含的上述两个数据项可描述为：据项可描述为：10第二章 进 程 管 理 type semaphore=record value:integer;L:list of process;end相应地，相应地，wait(S)和和signal(S)操作可描述为：操作可描述为：procedu
7、re wait(S)var S:semaphore;begin S.value =S.value-1;if S.value0 then block(S,L)end procedure signal(S)var S:semaphore;begin S.value =S.value+1;if S.value0 then wakeup(S,L);end 11第二章 进 程 管 理 在在记记录录型型信信号号量量机机制制中中，S.value的的初初值值表表示示系系统统中中某某类类资资源源的的数数目目，因因而而又又称称为为资资源源信信号号量量，对对它它的的每每次次wait操操作作，意意味味着着进进程程请请
8、求求一一个个单单位位的的该该类类资资源源，因因此此描描述述为为S.value =S.value-1；当当S.value0时时，表表示示该该类类资资源源已已分分配配完完毕毕，因因此此进进程程应应调调用用block原原语语，进进行行自自我我阻阻塞塞，放放弃弃处处理理机机，并并插插入入到到信信号号量量链链表表S.L中中。可可见见，该该机机制制遵遵循循了了“让让权权等等待待”准准则则。此此时时S.value的的绝绝对对值值表表示示在在该该信信号号量量链链表表中中已已阻阻塞塞进进程程的的数数目目。对对信信号号量量的的每每次次signal操操作作，表表示示执执行行进进程程释释放放一一个个单单位位资资源源，
9、故故S.value =S.value+1操操作作表表示示资资源源数数目目加加1。若若加加1后后仍仍是是S.value0，则则表表示示在在该该信信号号量量链链表表中中，仍仍有有等等待待该该资资源源的的进进程程被被阻阻塞塞，故故还还应应调调用用wakeup原原语语，将将S.L链链表表中中的的第第一一个个等等待待进进程程唤唤醒醒。如如果果S.value的的初初值值为为1，表表示示只只允允许一个进程访问临界资源，此时的信号量转化为互斥信许一个进程访问临界资源，此时的信号量转化为互斥信号量。号量。12第二章 进 程 管 理 说明如何在消费者和生产者中的应用13第二章 进 程 管 理 3.AND型信号量型
10、信号量 在在两两个个进进程程中中都都要要包包含含两两个个对对Dmutex和和Emutex的的操操作作，即即process A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A:wait(Dmutex);于是于是Dmutex=0process B:wait(Emutex);于是于是Emutex=0process A:wait(Emutex);于是于是Emutex=-1 A阻塞阻塞process B:wait(Dmutex);于是
11、于是Dmutex=-1 B阻塞阻塞 14第二章 进 程 管 理 AND同同步步机机制制的的基基本本思思想想是是：将将进进程程在在整整个个运运行行过过程程中中需需要要的的所所有有资资源源，一一次次性性全全部部地地分分配配给给进进程程，待待进进程程使使用用完完后后再再一一起起释释放放。只只要要尚尚有有一一个个资资源源未未能能分分配配给给进进程程，其其它它所所有有可可能能为为之之分分配配的的资资源源，也也不不分分配配给给他他。亦亦即即，对对若若干干个个临临界界资资源源的的分分配配，采采取取原原子子操操作作方方式式：要要么么全全部部分分配配到到进进程程，要要么么一一个个也也不不分分配配。由由死死锁锁理
12、理论论可可知知，这这样样就就可可避避免免上上述述死死锁锁情情况况的的发发生生。为为此此，在在wait操操作作中中，增增加加了了一一个个“AND”条条件件，故故称称为为AND同同步步，或或称称为为同同时时wait操操作，作，即即Swait(Simultaneous wait)定义如下：定义如下：15第二章 进 程 管 理 Swait(S1,S2,Sn)if Si1 and and Sn1 then for i =1 to n do Si=Si-1;endfor else place the process in the waiting queue associated with the firs
13、t Si found with Si1,and set the program count of this process to the beginning of Swait operation endifSsignal(S1,S2,Sn)for i =1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;16第二章 进 程 管 理 4.信号量集信号量集 Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and
14、 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 Siti and set its program counter to the beginning of the Swait Operation.endif signal(S1,d1,Sn,dn)for i=1 to n do Si =Si+di;Remove all the process waiting in the queue associated wit
15、h Si into the ready queue endfor;17第二章 进 程 管 理 一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况：(1)Swait(S,d,d)。此此时时在在信信号号量量集集中中只只有有一一个个信信号号量量S，但但允允许许它它每每次次申申请请d个个资资源源，当当现现有有资资源源数数少少于于d时时，不予分配。不予分配。(2)Swait(S,1,1)。此此时时的的信信号号量量集集已已蜕蜕化化为为一一般般的的记记录型信号量录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)。(3)Swait(S,1,0)。这这是是一一种种很很特特殊殊且且很很有有用用的
16、的信信号号量量操操作作。当当S1时时，允允许许多多个个进进程程进进入入某某特特定定区区；当当S变变为为0后后，将将阻阻止止任任何何进进程程进进入入特特定定区区。换换言言之之，它它相相当当于于一一个个可可控控开关。开关。18第二章 进 程 管 理 2.3.3 信号量的应用信号量的应用 1.利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下：利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore =1;begin parbegin process 1:begin repeat wait(mutex);critical section sig
17、nal(mutex);remainder seetion until false;19第二章 进 程 管 理 end process 2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend 20第二章 进 程 管 理 2.利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 abcde,f,g21第二章 进 程 管 理 Var a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;begin parbegin be
18、gin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end 22第二章 进 程 管 理 2.4 经典进程的同步问题经典进程的同步问题 2.4.1 生产者生产者消费者问题消费者问题生生产产者者-消消费费者者(producer-consu
19、mer)问问题题是是一一个个著著名名的的进进程程同同步步问问题题。它它描描述述的的是是：有有一一群群生生产产者者进进程程在在生生产产产产品品，并并将将这这些些产产品品提提供供给给消消费费者者进进程程去去消消费费。为为使使生生产产者者进进程程与与消消费费者者进进程程能能并并发发执执行行，在在两两者者之之间间设设置置了了一一个个具具有有n个个缓缓冲冲区区的的缓缓冲冲池池，生生产产者者进进程程将将它它所所生生产产的的产产品品放放入入一一个个缓缓冲冲区区中中；消消费费者者进进程程可可从从一一个个缓缓冲冲区区中中取取走走产产品品去去消消费费。尽尽管管所所有有的的生生产产者者进进程程和和消消费费者者进进程
20、程都都是是以以异异步步方方式式运运行行的的，但但它它们们之之间间必必须须保保持持同同步步，即即不不允允许许消消费费者者进进程程到到一一个个空空缓缓冲冲区区去去取取产产品品；也也不不允允许许生生产产者者进进程程向向一一个个已已装装满满产产品品且且尚尚未未被被取取走走的的缓缓冲区中投放产品。冲区中投放产品。23第二章 进 程 管 理 2.4.1 生产者生产者消费者问题消费者问题一个或者多个生产者产生某种类型的数据，放置在缓冲区一个或者多个生产者产生某种类型的数据，放置在缓冲区有一个或者多个消费者从缓冲区中取数据，每次取一项有一个或者多个消费者从缓冲区中取数据，每次取一项系统保证只有一个代理访问缓冲
21、区系统保证只有一个代理访问缓冲区24第二章 进 程 管 理 1.利用记录型信号量解决生产者利用记录型信号量解决生产者消费者问题消费者问题问题的三个限制条件：问题的三个限制条件：a)互斥访问互斥访问buffer：mutex。b)有空的有空的buffer才生产：才生产：empty，c)有数据才消费：有数据才消费：fullinitwaitsignalmutex1P或C进入临界区P或C退出临界区emptynP放入数据C取走数据Full0C取走数据P生产数据25第二章 进 程 管 理 Var mutex,empty,full:semaphore=1,n,0;buffer:array0,n-1 of it
22、em;in,out:integer=0,0;begin parbegin proceducer:begin repeat producer an item nextp;wait(empty);/有空地放物品吗？有空地放物品吗？wait(mutex);/有人占用了吗？有人占用了吗？buffer(in)=nextp;in=(in+1)mod n;signal(mutex);/我不占用了我不占用了 signal(full);/里面有物品可以拿了里面有物品可以拿了 until false;end 26第二章 进 程 管 理 consumer:begin repeat wait(full);/有物品可以
23、拿吗？有物品可以拿吗？wait(mutex);/有人占用了吗？有人占用了吗？nextc =buffer(out);out =(out+1)mod n;signal(mutex);/我不占用了我不占用了 signal(empty);/有空地可以放物品了有空地可以放物品了 consumer the item in nextc;until false;end parend end 27第二章 进 程 管 理 1.生产速度生产速度和消费速度和消费速度一样快一样快PRODUCERCOSUMMEREFM1n012wait(empty);n-1013wait(mutex);n-10045signal(mut
24、ex);n-1016signal(full);n-1117wait(full);n-1018wait(mutex);n-1009n-10010signal(mutex);n-10111signal(empty);n0128第二章 进 程 管 理 2.生产者快，消费者慢的极端情况生产者快，消费者慢的极端情况Buffer满，那么Empty=0,FULL=n,生产者将会在wait(empty)语句中等待3.生产者慢，消费者快的极端情况生产者慢，消费者快的极端情况Empty=n,Full=0,消费者会在wait(full)阻塞;29第二章 进 程 管 理 生产者程序中生产者程序中交换交换empty和和
25、mutex的顺序的顺序(n=1)PRODUCERCOSUMMEREFM101wait(mutex);100wait(empty);000signal(full);010wait(full);000wait(mutex);(wait)000signal(mutex);001wait(mutex);000wait(empty);(wait)00030第二章 进 程 管 理 2.利用利用AND信号量解决生产者信号量解决生产者消费者问题消费者问题 ar mutex,empty,full:semaphore =1,n,0;buffer:array0,n-1 of item;in out:integer
26、=0,0;begin parbegin producer:begin repeat produce an item in nextp;Swait(empty,mutex);buffer(in)=nextp;in =(in+1)mod n;Ssignal(mutex,full);until false;end 31第二章 进 程 管 理 consumer:begin repeat Swait(full,mutex);nextc =buffer(out);out =(out+1)mod n;Ssignal(mutex,empty);consumer the item in nextc;until
27、false;end parend end 32第二章 进 程 管 理 2.4.2 哲学家进餐问题哲学家进餐问题(The Dinning Philosophers Problem)1.利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题 经经分分析析可可知知，放放在在桌桌子子上上的的筷筷子子是是临临界界资资源源，在在一一段段时时间间内内只只允允许许一一位位哲哲学学家家使使用用。为为了了实实现现对对筷筷子子的的互互斥斥使使用用，可可以以用用一一个个信信号号量量表表示示一一只只筷筷子子，由由这这五五个个信信号号量量构构成成信信号号量数组。其描述如下：量数组。其描述如下：Var cho
28、pstick:array0,4 of semaphore;33第二章 进 程 管 理 所有信号量均被初始化为所有信号量均被初始化为1，第第i位哲学家的活动可描述为：位哲学家的活动可描述为：repeat wait(chopsticki);wait(chopstick(i+1)mod 5);eat;signal(chopstick(i+1)mod 5);signal(chopsticki);think;until false;34第二章 进 程 管 理 死锁的情况死锁的情况35第二章 进 程 管 理 可采取以下几种解决方法：可采取以下几种解决方法：(1)至至多多只只允允许许有有四四位位哲哲学学家家
29、同同时时去去拿拿左左边边的的筷筷子子，最最终终能能保保证证至至少少有有一一位位哲哲学学家家能能够够进进餐餐，并并在在用用毕毕时时能能释释放出他用过的两只筷子，从而使更多的哲学家能够进餐。放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅仅当当哲哲学学家家的的左左、右右两两只只筷筷子子均均可可用用时时，才才允允许许他拿起筷子进餐。他拿起筷子进餐。(3)规规定定奇奇数数号号哲哲学学家家先先拿拿他他左左边边的的筷筷子子，然然后后再再去去拿拿右右边边的的筷筷子子；而而偶偶数数号号哲哲学学家家则则相相反反。按按此此规规定定，将将是是1、2号号哲哲学学家家竞竞争争1号号筷筷子子；3、4号号哲哲学学
30、家家竞竞争争3号号筷筷子子。即即五五位位哲哲学学家家都都先先竞竞争争奇奇数数号号筷筷子子，获获得得后后，再再去去竞竞争争偶偶数号筷子，最后总会有一位哲学家能数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。获得两只筷子而进餐。36第二章 进 程 管 理 2.利用利用AND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题 在在哲哲学学家家进进餐餐问问题题中中，要要求求每每个个哲哲学学家家先先获获得得两两个个临临界界资资源源(筷筷子子)后后方方能能进进餐餐，这这在在本本质质上上就就是是前前面面所所介介绍绍的的AND同步问题，故用同步问题，故用AND信号量机制可获得最简洁的解法。信号量机制
31、可获得最简洁的解法。Var chopsiick array 0,4 of semaphore =(1,1,1,1,1);processi repeat think;Sswait(chopstick(i+1)mod 5,chopstick i);eat;Ssignat(chopstick i，chopstick(i+1)mod 5);until false;37第二章 进 程 管 理 2.4.3 读者读者-写者问题写者问题(Reader-Writer Problem)定定义义：有有一一个个许许多多进进程程共共享享的的数数据据区区（文文件件、主主存存空空间间、寄寄存器），多个读（存器），多个读（r
32、eader）写）写(writer)进程满足以下条件：进程满足以下条件：1。读进程可以同时读。读进程可以同时读2。一次只有一个写进程可以往文件中写。一次只有一个写进程可以往文件中写3。如果写进程正在写，禁止任何读程序。如果写进程正在写，禁止任何读程序38第二章 进 程 管 理 2.4.3 读者读者-写者问题写者问题(Reader-Writer Problem)1.利用记录型信号量解决读者利用记录型信号量解决读者-写者问题写者问题分析读写程序的限制条件：分析读写程序的限制条件：写程序：写程序：Wmutex。a)写程序互斥 b)写程序同读程序互斥读读程程序序：a)读程序计数器需要互斥访问，Rmute
33、x。b)读时，写程序不能访问；当最后一个读程序退出，写程序可以访问 Wmutex。initwaitsignalWmutex1写进程进入第一个读进程写进程退出最后一个读进程退出Rmutex1读进程进入计数器临界区读进程退出计数器临界区39第二章 进 程 管 理 读者读者-写者问题可描述如下：写者问题可描述如下：Var rmutex,wmutex:semaphore =1,1;Readcount:integer =0;begin parbegin Reader:begin repeat wait(rmutex);/有人修改计数器吗？有人修改计数器吗？if readcount=0 then wait
34、(wmutex);/没人在阅读，有人在写吗？没人在阅读，有人在写吗？Readcount =Readcount+1;signal(rmutex);/我已经在阅读了，不用修改计数器了我已经在阅读了，不用修改计数器了 perform read operation;40第二章 进 程 管 理 wait(rmutex);/我已经阅读完了，有人在修改计数器吗？我已经阅读完了，有人在修改计数器吗？readcount =readcount-1;if readcount=0 then signal(wmutex);/没人读了，可以写了没人读了，可以写了 signal(rmutex);/我已经阅读完了，不用修改计
35、数器了我已经阅读完了，不用修改计数器了 until false;end writer:begin repeat wait(wmutex);/有人在阅读吗？有人在阅读吗？perform write operation;signal(wmutex);/我写完了，可以阅读了我写完了，可以阅读了 until false;end parend end 41第二章 进 程 管 理 存在的问题：存在的问题：当读进程进入后，数据区的使用权交给读进程，所谓读进程优先，写进程可能饿死。解决的办法：解决的办法：写进程优先，当有写进程要求写数据，不能再调入 新的读进程。42第二章 进 程 管 理 解决的办法：解决的办
36、法：写进程优先，当有写进程要求写数据，不能再调入 新的读进程。写进程优先限制条件：写进程优先限制条件：写写程程序序：a)写进程互斥。Wmutex b)有读进程进入，等待Rmutex c）写进程计数的互斥访问WcntMutex读读程程序序：a)读程序计数器需要互斥，RcntMutex。b)有写进程进入，不能再调入读进程RinMutex c)有写进程进入，正在读的进程需要等待Wmutex43第二章 进 程 管 理 写进程优先：写进程优先：Var RinMutex,Rmutex,RcntMutex,semaphore =1,1,1;Var Wmutex,WcntMutex:semaphore =1,
37、1;Readcount:integer =0;Writecount:integer =0;44第二章 进 程 管 理 begin parbegin Reader:begin repeat wait(Rmutex);/有读或者写进程已经进入？有读或者写进程已经进入？wait(RcntMutex);/有人修改计数器？有人修改计数器？if readcount=0 then wait(Wmutex);/没人在阅读，有人在写吗？没人在阅读，有人在写吗？Readcount =Readcount+1;signal(RcntMutex);/我已经在阅读了，不用修改计数器了我已经在阅读了，不用修改计数器了 si
38、gnal(Rmutex);/我已经进入读的过程我已经进入读的过程 45第二章 进 程 管 理 perform read operation;wait(RcntMutex);/我已经阅读完了，有人在修改计数器吗？我已经阅读完了，有人在修改计数器吗？readcount =readcount-1;if readcount=0 then signal(wmutex);/没人读了，可以写了没人读了，可以写了 signal(RcntMutex);/我已经阅读完了，不用修改计数器了我已经阅读完了，不用修改计数器了 until false;end 46第二章 进 程 管 理 writer:begin repe
39、at wait(WcntMutex);/有人在修改计数器？有人在修改计数器？WriteCount；if(WriteCount=1)wait(Rmutex);/有读进程正在读？有读进程正在读？signal(WcntMutex);/计数器修改完毕计数器修改完毕 wait(wmutex);/是否有写或读进程？是否有写或读进程？perform write operation;signal(wmutex);/我写完了，可以阅读了我写完了，可以阅读了 wait(WcntMutex);/有人在修改计数器？有人在修改计数器？WriteCount；if(WriteCount=0)signal(Rmutex);/
40、写完成，可以读写完成，可以读 signal(WcntMutex);/计数器修改完毕计数器修改完毕 until false;end parend end 47第二章 进 程 管 理 分析写进程优先程序：分析写进程优先程序：请分析是否满足读者写着问题请分析是否满足读者写着问题：1。读进程可以同时读。读进程可以同时读2。一次只有一个写进程可以往文件中写。一次只有一个写进程可以往文件中写3。如果写进程正在写，禁止任何读程序。如果写进程正在写，禁止任何读程序 只有读进程设置wMutex无队列只有写进程写进程在wMutex上排队读和写进程都存在写进程设置wMutex，Rmutex写进程在wMutex排队读
41、进程在Rmutex上排队48第二章 进 程 管 理 2.利用信号量集机制解决读者利用信号量集机制解决读者-写者问题写者问题 Var RN integer;L,mx:semaphore =RN,1;begin parbegin reader:begin repeat Swait(L,1,1);/阅读人数满了吗？如果没满，则可以阅读人数减阅读人数满了吗？如果没满，则可以阅读人数减1 Swait(mx,1,0);/可以阅读了吗？即有人在写吗？可以阅读了吗？即有人在写吗？perform read operation;49第二章 进 程 管 理 Ssignal(L,1);/我不阅读了，可增加一个名额阅读
42、了我不阅读了，可增加一个名额阅读了 until false;end writer:begin repeat Swait(mx,1,1;L,RN,0);/可以写了吗？还有人占有阅读名额吗？可以写了吗？还有人占有阅读名额吗？perform write operation;Ssignal(mx,1);/我不写了，可以阅读了我不写了，可以阅读了 until false;end parend end 50第二章 进 程 管 理 2.4.4 信号量的实现信号量的实现(如何保证原子性如何保证原子性)软件方法：软件方法：Dekker算法或者算法或者peterson算法算法利用中断利用中断wait(s)sign
43、al(s)inhibit interrupts;inhibit interrupts;s.count-;s.count+;if(s.count 0)if(s.count=0)place this process in s.queue;remove a process P block this process from s.queue;and allow interrupt;place P on ready list;else allow interrupt;allow interrupt;51第二章 进 程 管 理 2.5 管管 程程 机机 制制 2.5.1 管程的基本概念管程的基本概念 1.
44、管程的引入管程的引入 信信号号量量的的问问题题：功能强大灵活；但由于wait和signal的操 作遍布程序中，难于控制困难。解解决决的的一一个个思思路路：采用面向对象技术的思路，将一个需要同步的资源做成一个数据结构，并在其上定义操作，以避免用户程序去设计wait和signal的位置。52第二章 进 程 管 理 2.5 管管 程程 机机 制制 2.5.1 管程的基本概念管程的基本概念 2.管程的定义管程的定义 定定义义：一一个个管管程程定定义义了了一一个个数数据据结结构构和和能能为为并并发发进进程程所所执执行行(在在该该数数据据结结构构上上)的的一一组组操操作作，这这组组操操作作能能同同步步进进
45、程程和和改改变变管管程程中中的的数数据据。即即它它描描述述并并发发环环境境中中的的抽抽象数据类型。象数据类型。管管程程由由三三部部分分组组成成：局局部部于于管管程程的的共共享享变变量量说说明明；对对该该数数据据结结构构进进行行操操作作的的一一组组过过程程；对对局局部部于于管管程程的的数数据据设设置置初初始始值值的的语语句句。此此外外，还还须须为为管管程程赋赋予予一一个个名字。名字。53第二章 进 程 管 理 2.5 管管 程程 机机 制制 2.5.1 管程的基本概念管程的基本概念 3.管程的特点管程的特点 a)局局部部数数据据变变量量只只能能被被管管程程的的过过程程访访问问，任任何何外外部部进
46、进程程不能访问不能访问b)一个进程通过调用管程的一个过程进入管程一个进程通过调用管程的一个过程进入管程c)任任何何时时候候，只只能能有有一一个个进进程程在在管管程程中中执执行行，其其余余调调用用管程的进程都被挂起，以等待管程可用管程的进程都被挂起，以等待管程可用54第二章 进 程 管 理 图图 2-11 管程的示意图管程的示意图 55第二章 进 程 管 理 管程的另一示意图管程的另一示意图 56第二章 进 程 管 理 管程的语法如下：管程的语法如下：type monitor-name=monitor variable declarations procedure entry P1();begi
47、n end;procedure entry P2();begin end;procedure entry Pn();begin end;begin initialization code;end 57第二章 进 程 管 理 2.条件变量条件变量 a)管管程程中中使使用用条条件件变变量量提提供供对对同同步步的的支支持持。如如果果正正在在使使用用管管程程的的进进程程因因x条条件件被被阻阻塞塞或或者者挂挂起起，X.wait将将自自己己插插入入到到X条条件件的的等等待待队队列列上上，并并释释放放管管程程，直直到到X条条件件有有变变化化。.此时其它进程可以调用该管程。此时其它进程可以调用该管程。b)需要
48、声明需要声明c)应应当当指指出出，X.signal操操作作的的作作用用，是是重重新新启启动动一一个个被被阻阻塞塞的的进进程程，但但如如果果没没有有被被阻阻塞塞的的进进程程，则则X.signal操操作作不不产产生生任任何何后后果果。这这与与信信号号量量机机制制中中的的signal操操作作不不同同。因因为为，后者总是要执行后者总是要执行s:=s+1操作，因而总会改变信号量的状态。操作，因而总会改变信号量的状态。58第二章 进 程 管 理 如如果果有有进进程程Q处处于于阻阻塞塞状状态态，当当进进程程P执执行行了了X.signal操操作作后后，Q唤唤醒醒；怎怎样样决决定定由由哪哪个个进进行行执执行行，
49、哪哪个等待，可采用下述两种方式之一进行处理：个等待，可采用下述两种方式之一进行处理：(1)P等待，直至等待，直至Q离开管程或等待另一条件。离开管程或等待另一条件。(2)Q等待，直至等待，直至P离开管程或等待另一条件。离开管程或等待另一条件。采用哪种处理方式，采用哪种处理方式，当然是各执一词。当然是各执一词。但是但是Hansan却采用了第一种处理方式。却采用了第一种处理方式。59第二章 进 程 管 理 2.5.2 利用管程解决生产者利用管程解决生产者-消费者问题消费者问题 在在利利用用管管程程方方法法来来解解决决生生产产者者-消消费费者者问问题题时时，首首先先便便 是是 为为 它它 们们 建建
50、立立 一一 个个 管管 程程，并并 命命 名名 为为 Proclucer-Consumer,或简称为或简称为PC。其中包括两个过程：其中包括两个过程：(1)put(item)过程。过程。(2)get(item)过程。过程。60第二章 进 程 管 理 (1)put(item)过过程程。生生产产者者利利用用该该过过程程将将自自己己生生产产的的产产品品投投放放到到缓缓冲冲池池中中，并并用用整整型型变变量量count来来表表示示在在缓缓冲冲池池中中已已有有的的产产品品数数目目，当当countn时时，表表示示缓缓冲冲池池已已满满，生生产产者者须等待。须等待。(2)get(item)过过程程。消消费费者者