计算机操作系统第三章课件.ppt

2022/12/10,1,第三章 进程同步与通信,2022/12/10,2,前言,在并发(多任务)环境下，若一个进程不会受到其他进程的影响，则称该进程为独立进程；若一个进程会受到其他进程的影响，则称该进程和影响它的进程为协作进程。这种影响关系可能有：,2022/12/10,3,(1) 互斥。很多资源是进程互斥使用的，例如：CPU、打印机、数据等。(2) 同步。同步是指一个进程的执行会因等待另一进程的某个事件而受其影响。相应地，异步是指两个进程的执行步调和速度不相互影响。(3) 通信。进程之间需要交换数据。,前言,2022/12/10,4,实际上，在并发环境下，不存在完全独立的进程。进程间至少存在互斥关系(对资源的并发共享、互斥使用)。上述互斥、同步或通信关系，有些是隐式的，例如对CPU的互斥使用是通过进程状态转换和进程切换来实现的；有些是显式的，需要专门的机制来实现。显式地实现上述关系的机制称为进程通信机制。,前言,2022/12/10,5,本章主要目录,3.1 进程同步的基本概念3.2 信号量机制3.3 经典进程同步问题3.4 管程机制3.5 进程通信总结本章基础要点练习及参考答案,2022/12/10,6,3.1 进程同步的基本概念,进程同步的主要任务，是使并发执行的进程之间有效地共享资源和相互合作，使程序的执行具有可再现性。,所谓进程同步是指，对多个相关进程在执行次序上的协调。这些进程相互合作，在一些关键点上可能需要互相等待或互通消息。,2022/12/10,7,3.1 进程同步的基本概念,3.1.1 临界资源3.1.2 临界区一、临界区的定义和进入二、同步机制应遵循的准则3.1.3 利用软件方法解决进程互斥问题3.1.4 利用硬件方法解决进程互斥问题 一、中断屏蔽方法二、利用Test-and-Set指令实现互斥三、利用Swap指令实现进程互斥,2022/12/10,8,3.1.1 临界资源,生产者消费者问题及其同步技术是由Dijkstra于1965年提出的。计算机系统中的许多问题都可以将它归结为生产者和消费者问题。生产者，在生产消息，提供给消费者进程去消费。在它们之间设置了一个具有n个缓冲区的缓冲池，生产者进程将生产的消息放入一个缓冲区中，消费者进程从一个缓冲区中取走一个消息消费。,2022/12/10,9,生产者进程和消费者进程，必须保持同步，即不允许消费者到一个空缓冲区取消息，也不允许生产者进程向一个已装满消息且尚未被取走的缓冲区中去投放消息。,3.1.1 临界资源,2022/12/10,10,用数组表示具有n个缓冲区的缓冲池，组织成循环缓冲。 用一个输入指针in表示下一个可投放消息的缓冲区，每当生产者生产并投放一个消息后，in:=(in+1)mod n。 用一个输出指针out表示下一个可获取消息的缓冲区，每当消费者取走一个消息后，out=(out+1)mod n。,3.1.1 临界资源,1,2,3,4,5,0,n-1,6,环形缓冲池,in,out,2022/12/10,12,当(in+1) mod n=out时表示缓冲池满，当in=out表示缓冲池空。用counter作投放消息的计数器，投放一个消息就增1，取走一个消息就减1。,3.1.1 临界资源,2022/12/10,13,生产者和消费者共享如下变量： var n：integer; type item=; var buffer：array0,1,n-1 of item; in,out:0,1,n-1; counter:0,1,n;,3.1.1 临界资源,2022/12/10,14,in 和out初值为1。 no-op表示是一条空操作。 While condition do no-op表示重复的测试条件condition，直至条件不成立为止，即其值为false。 nextp用来存放刚生产的消息， nextc表示要消费的消息。,3.1.1 临界资源,2022/12/10,15,生产者和消费者程序如下：Producer repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=in+1 mod n; counter:=counter+1; until false;,3.1.1 临界资源,2022/12/10,16,Consumer:repeat while counter=0 do no-op; nextc:=bufferout; out:=out+1 mod n; counter:=counter-1; consume the item in nextc; until false;,3.1.1 临界资源,2022/12/10,17,#define N 100 缓冲区中的槽数目 int count=0; 缓冲区中的数据项数目 voidproducer(void) int item; while (true) item=produce_item(); if(count=N)sleep(); insert_item(item); count=count+1; if(count=1)wakeup(consumer); ,3.1.1 临界资源,2022/12/10,18,Void consumer(void) int item; while(TRUE) if(count=0)sleep(); item=receive_item(); count=count-1; if(count=N-1)wakeup(producer); consume_item(item); ,3.1.1 临界资源,2022/12/10,19,上述两程序分别运行时，是有效的，预期的。 但并发运行时，由于两者共享counter。 若其初值为5，看下列程序结果： register_1:=counter; regiser_1:=regiser_1+1; counter:=register_1; register_2:=counter; register_2:=register_2-1; counter:=register_2; 顺序执行时，最后counter的结果为5。,3.1.1 临界资源,2022/12/10,20,但若如下执行： register_1:=counter; register_1:=register_1+1; register_2:=counter; register_2:=register_2-1; counter:=register_1; counter:=register_2;,3.1.1 临界资源,2022/12/10,21,则得到的counter结果是4。若再改变执行顺序，可能会得到counter为6的结果，所以，程序的执行不具有可再现性。解决此类问题，要把counter作为临界资源处理，生产者和消费者互斥地访问counter。,3.1.1 临界资源,2022/12/10,22,一、临界区的定义和进入 定义：每个进程中访问临界资源的代码段称为临界区(段)critical section。 若能保证每个进程能互斥地进入自己的临界区，可实现它们对临界资源的互斥访问。,3.1.2 临界区,2022/12/10,23,解决方法：每个进程在进入临界区之前先对欲访问的临界资源进行检查，是否正被访问， 若未被访问，该进程可进入临界区，对该资源进行访问，并设置正被访问的标志。 若进入之前，临界资源正被其它进程访问，则本进程不能进入临界区。,3.1.2 临界区,2022/12/10,24,为保证临界资源的正确使用，可以把临界资源的访问分成四个部分：(1)进入区：为了进入临界区使用临界资源，在进入区要检查是否可以进入临界区；如果可以进入临界区，设置相应的“正在访问临界区”标志，以阻止其他进程同时进入临界区。(2)临界区：进程中访问临界资源的那段代码，又称临界段。,3.1.2 临界区,2022/12/10,25,(3)退出区：临界区后用于将“正在访问临界区”标志清除的部分。(4)剩余区：进程中除进入区、临界区、退出区以外的其他部分。,3.1.2 临界区,2022/12/10,26,访问一个临界资源的循环进程可描述成：,repeat entry section进入区 critical section;临界区 exit section退出区remainder section剩余区 until false;,3.1.2 临界区,2022/12/10,27,为了禁止两个进程同时进入临界区，可采用软件解决方法或同步机构来协调它们。但是，不论从软件算法或同步机构都应遵循如下准则：,3.1.2 临界区,2022/12/10,28,(1)当有若干进程要求进入它们的临界区时，应在有限时间内使一个进程进入临界区。(2)每次至多有一个进程处于临界区内。(3)进程在临界区内仅逗留有限的时间。这是由著名的计算机科学家Dijkstra于1965年提出的临界段设计原则。,3.1.2 临界区,2022/12/10,29,三、同步机制应遵循的准则1、空闲让进2、忙则等待3、有限等待4、让权等待:当进程不能进入临界区时,应立即释放处理机,以免进程陷入“忙等”状态。,3.1.2 临界区,2022/12/10,30,另外说法：(1)互斥性。不能同时有两个进程位于临界区内。(2)前进性。在临界区外的进程不能阻塞别的进程进入临界区。(3)有限等待。进程不能无休止地等着进入临界区。这称为饥饿或死锁。(4)通用性。对进程速度或CPU个数、有无硬件指令支持等不作假设。,3.1.2 临界区,2022/12/10,31,3.2.1 整型信号量机制一、整型信号量二、利用信号量实现互斥三、利用信号量来描述前趋关系3.2.2 记录型信号量机制3.2.3 信号量集机制一、And型信号量集机制二、一般信号量集机制,3.2 信号量机制,2022/12/10,32,一、整型信号量整型信号量为一个整型量s，除初始化(其初值不能是负值)外，只能通过两个标准的原子操作wait(s)和signal(s)来改变。这两个操作被称为P、V操作。分别描述：,3.2.1 整型信号量机制,2022/12/10,33,P操作P(S)：wait(s):while S0 do no-op s:=s-1; V操作V(S)：signal(s):s:=s+1; P、V是两个原子操作。,3.2.1 整型信号量机制,2022/12/10,34,信号量按其用途可分为：(1)二元信号量(binary semaphore)：它仅允许取值为“0”与“1”，主要用作互斥变量(2)一般信号量：它允许取值为非负整数，主要用于进程间的一般同步问题(但在许多应用中允许其值为负整数，即对Dijkstra的原定义进行了扩充),3.2.1 整型信号量机制,2022/12/10,35,二、利用信号量实现互斥要使多进程互斥地访问某临界资源： 先为该资源设置一个互斥信号量mutex，置初值为1，表示该临界资源未被占用，然后将各进程的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。,3.2.1 整型信号量机制,2022/12/10,36,每个要访问该临界资源的进程，进入临界前，先对mutex执行wait，若该资源此时未被访问，本次wait成功，进程可进入自己的临界区，此时若有其它进程也要进入自己的临界区，它们对mutex执行wait要失败，所以阻塞。为什么？当进程退出临界区后，要对mutex执行signal，释放该临界资源。,P(mutex):while mutex0 do no-op mutex:=mutex-1;V(mutex): mutex:=mutex+1;,3.2.1 整型信号量机制,2022/12/10,37,利用信号量实现互斥的进程描述如下： var mutex:semaphore:=1 begin parbegin process_1:begin repeat wait(mutex); CS signal(mutex); RS until false; end,3.2.1 整型信号量机制,2022/12/10,38,process_2:begin repeat wait(mutex); CS signal(mutex); RS until false end parend,3.2.1 整型信号量机制,2022/12/10,39,注：wait和signal必须成对出现，缺少wait不能保证对临界资源的互斥访问， 缺少signal会使临界资源永远不能释放，使等待该资源而阻塞的进程不能被唤醒。,3.2.1 整型信号量机制,2022/12/10,40,三、利用信号量来描述前趋关系 可用信号量来描述程序或语句之间的前趋关系。实现这种前趋关系，使两个进程共享公用信号量s，其初值为0，将signal(s)放在S1后面，在S2前面插入wait(s)，即：P1中：有S1;signal(s);P2中：有wait(s);S2;,3.2.1 整型信号量机制,2022/12/10,41,若先执行P2，由于S初值为0，所以阻塞，只能先执行P1，使S增1后，才能执行P2。又有如下并发执行的程序：,S1,S4,S5,S2,S3,S6,3.2.1 整型信号量机制,2022/12/10,42,var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;六个信号量 begin parbegin begin 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,3.2.1 整型信号量机制,2022/12/10,43,该程序所构造的前趋图：,S1,S4,S5,S2,S3,S6,3.2.1 整型信号量机制,2022/12/10,44,整型信号量机制中，wait只要是S0，就会不断地测试，所以，不能满足让权等待的原则，而使该进程处于忙等的状态。记录型信号量机制中，采用了记录型的数据结构。由此称为记录型信号量机制。此时的信号量是一个确定的二元组(value,L)，value是一个具有非负值的整形变量，L是一个初始状态为空的队列。,3.2.2 记录型信号量机制,2022/12/10,45,type semaphore=record value:integer; L:list of process; end其P、V操作描述如下：,3.2.2 记录型信号量机制,2022/12/10,46,procedure signal(s) var s:semaphore; begin s.value:=s.value+1; if s.value0 then wakeup(s.L); end,3.2.2 记录型信号量机制,2022/12/10,47,rocedure wait(s) var s:semaphore; begin s.value:=s.value-1; if s.value0 then block(s.L) (自我阻塞) end,3.2.2 记录型信号量机制,2022/12/10,48,其中：s.value的初值表示某类资源的数目，又称资源信号量，每次的wait操作，意味着进程请求一个单位的资源，s.value0表示资源分配完毕，该进程调用block原语，自我阻塞，插入到信号量链表s.L中。遵循了让权等待的准则。此时的s.value的绝对值表示在该信号量表中已阻塞进程的数目。,3.2.2 记录型信号量机制,2022/12/10,49,每次signal操作，表示执行进程释放一个单位资源，所以，s.value=s.value+1表示资源加1。加1后s.value0表示在该信号量链表中，还有等待该资源的进程被阻塞，应调用wakeup原语，将s.L链表中第一个等待进程唤醒。 若s.value初值为1，表示只允许一个进程访问临界资源，信号量转化为互斥信号量。,3.2.2 记录型信号量机制,2022/12/10,50,一、And型信号量集机制 (为防止死锁)前述进程互斥问题，针对的是进程之间要共享一个临界资源。若一个进程需要获得多个共享资源，即有多个临界资源时，应如何处理。,3.2.3 信号量集机制,2022/12/10,51,设有两个进程A和B，都要求访问共享数据D和E。则为两个数据分别设置用于互斥的信号量Dmutex和Emutex，其初值均为1。则两进程中都包含两个对Dmutex和Emutex的原子操作。即： process A: wait(Dmutex); wait(Emutex); process B: wait(Emutex); wait(Dmutex);,3.2.3 信号量集机制,2022/12/10,52,若A和B交替执行wait操作： process A:wait(Dmutex); process B:wait(Emutex); process A:wait(Emutex); process B:wait(Dmutex); 最后 A和B都处于等待状态。此时A和B进入死锁状态。所以，当进程同时要求共享的资源数目愈多，死锁的可能性愈大。 And同步机制的思想是：,Dmutex=0,Emutex=0,Emutex=-1 A阻塞,Dmutex=-1 B阻塞,将进程在整个运行期间所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后，一次性释放。只要有一个资源不能分配给该进程，其它所有的资源也不能分配给它。,2022/12/10,53,即，对若干个临界资源的分配，采取原子操作，要么全部分配，要么一个也不分配。所以，在wait中增加了一个And条件，故称为And同步，或称为同时wait操作，即Swait（simultaneous wait），其定义如下： swait(s1,s2, ,sn) if s11 and and sn 1 then for i:=1 to n do si=si-1; endfor else,3.2.3 信号量集机制,2022/12/10,54,Place the process in the waiting queue associated with the first si found with si1,and set the program counter of this process to the beginning of Swait operation. endif,3.2.3 信号量集机制,2022/12/10,55,Ssingal (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,3.2.3 信号量集机制,2022/12/10,56,二、一般“信号量集”机制 (每次对n个某类共享资源进行操作)记录型信号量机制中，Wait、Signal操作仅能对信号量进行增1或减1的操作，即每次只能获得或释放一个单位的临界资源。,3.2.3 信号量集机制,2022/12/10,57,当需n个某类临界资源时，需要进行n次wait操作。而在有些情况下，当资源数量低于某一下限值时，系统不予分配，所以，每次分配前，需测试该资源的数量是否大于测试值。基于此，对And信号量机制进行扩充，形成了一般化的信号量集机制。,3.2.3 信号量集机制,2022/12/10,58,swait操作描述如下：swait (s1,t1,d1,sn,tn,dn) if s1 t1 and and sn tn 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;,Si表示第i类资源初始数目，ti表示需要该类资源的下限值，di表示进程需要第i类资源的数目,3.2.3 信号量集机制,2022/12/10,59,Ssingal (s1,d1;sn,dn) for i:=1 to n do si:=si+di; Remove all the process waiting in the queue associated with si into the ready queue. endfor;,3.2.3 信号量集机制,2022/12/10,60,有几种特殊情况需要注意：（1）Swait(s,d,d)。此时在信号量集中只有一个信号量s，但它允许每次申请d个资源，当现有资源数少于d时，不予分配。（2）Swait(s,1,1)。此时的信号量集已蜕化为一般的记录型信号量（s1时）或互斥信号量（s=1时） 相当于wait(s)。,3.2.3 信号量集机制,2022/12/10,61,（3）Swait(s,1,0)。一种特殊但有用的信号量。当s 1时，允许多个进程进入某特定区，当s=0后，将阻止任何进程进入特定区。相当于一个可控开关。(读者写者问题中用到),3.2.3 信号量集机制,2022/12/10,62,3.3 经典进程同步问题,3.3.1 生产者-消费者问题一、利用记录型信号量解决生产者-消费者问题二、利用And信号量解决生产者-消费者问题3.3.2 读者-写者问题一、利用记录型信号量解决读者- 写者问题二、利用信号量集机制解决读者-写者问题3.3.3 哲学家进餐问题一、利用记录型信号量解决哲学家进餐问题二、利用And信号量机制解决哲学家进餐问题练习总结1,2022/12/10,63,前 言,(1)生产者和消费者问题。有界缓冲区的问题。(2)读写问题。与生产者和消费者问题的区别在于： 读写的数据是不“拿走”或“增加”；“者”的个数不同。(3)哲学家就餐问题。这个问题的象征在于：哲学家相当于进程，刀叉意味着每个进程可能需要同时拥有多个资源才能运行下去。,2022/12/10,64,生产者和消费者问题之后的总结使用P、V操作实现进程互斥时应该注意：(1)每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。(2)P、V操作应分别紧靠临界区的头尾部，临界区的代码尽可能短，不能有死循环。(3)互斥信号量的初值一般为1。,前 言,2022/12/10,65,使用P、V操作实现进程同步时应注意：(1)分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源(信号量)进行协调，从而明确要设置哪些信号量。(2)信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。(3)同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。,前 言,2022/12/10,66,生产者消费者问题及其同步技术是由Dijkstra于1968年提出的，是许多相互合作进程关系的一种抽象，它共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品(如：输入时，输入进程是生产者，计算进程是消费者，输出时，计算进程是生产者，打印进程是消费者)。,3.3.1生产者消费者问题,2022/12/10,67,一、利用记录型信号量解决生产者消费者问题三种同步关系： (1)诸进程互斥访问公用缓冲池 (2)生产者速度过快 (3)消费者速度过快隐含的前提条件：每个消息只被消费一次。,3.3.1生产者消费者问题,2022/12/10,68,生产者消费者问题描述如下： var mutex,empty,full:semaphore:=1,n,0; buffer:array0,n-1 of item; in,out:integer:=0,0; begin parbegin,3.3.1生产者消费者问题,2022/12/10,69,roducer:begin repeat producer an item in nextp; wait(empty);减少一个空缓冲区数 wait(mutex); buffer(in):=nextp; in:=(in +1)mod n; signal(mutex); signal(full);增加一个满的缓冲区数 until false; end,3.3.1生产者消费者问题,2022/12/10,70,consumer:begin repeat wait(full);减少一个满的缓冲区数 wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty);增加一个空的缓冲区数 consume the item in nextc; until false; end Parend end,3.3.1生产者消费者问题,2022/12/10,71,注意：（1）在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对出现（2）对资源信号量empty和full的wait和signal，也要成对出现，但是分别处于不同的程序中。（3）在每个程序中的多个wait顺序不能颠倒。要先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起死锁。,3.3.1生产者消费者问题,2022/12/10,72,3.3.1生产者消费者问题,生产者和消费者问题的变型：生产者和消费者问题是进程互斥和同步问题的典型实例，实际应用中，许多并发进程之间的互斥与同步问题都可以归结为生产者和消费者问题1、一对一：一个生产者和一个消费者，利用一个缓冲区进行交换数据的问题。2、一对多：多类消费者3、多对多：书上的原问题，多类生产者和多类消费者4、每个消息可被消费m次5、生产者之间也存在着同步关系。,2022/12/10,73,#define N 100 typedef int semaphore; semaphore mutex=1; semaphore empty=N; semaphore full=0; void producer(void) int item; while (TRUE) item=produce_item(); down( ,3.3.1生产者消费者问题,2022/12/10,74,void consumer(void) int item; while(TRUE) down( ,3.3.1生产者消费者问题,2022/12/10,75,所谓读者写者问题，是指保证一个writer进程必须与其它进程互斥地访问共享对象的同步问题。并发进程对数据库中数据的访问，对一个文件的访问，对一块内存空间的访问或对一组寄存器的访问等，都可以归结为读者和写者问题。,3.3.2 读者写者问题,2022/12/10,76,一、利用记录型信号量解决读者写者问题读者写者问题描述如下：var rmutex,wmutex:semaphore:=1,1; readcount:integer:=0; begin parbegin,3.3.2 读者写者问题,2022/12/10,77,writer:begin repeat wait(wmutex); perform write peration; signal(wmutex); until false; end parend end,3.3.2 读者写者问题,2022/12/10,78,读者优先的算法，可能会造成写进程的饥饿现象。 对此算法的改进-优先让写入者进入，作为一个练习大家考虑一下。即一旦有写者到达，后续的读者必须等待。而无论是否有读者在读文件。,3.3.2 读者写者问题,2022/12/10,79,1、某数据库有一个写进程，多个读进程，它们之间读、写操作的交互要求是： 写进程正在写该数据库时不能有其他进程读该数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。 请用信号量及P、V操作描述这一组进程的工作过程。,3.3.2 读者写者问题,2022/12/10,80,解：本题中，允许读进程同时读数据库，但写进程正在写数据库时不允许其他进程读数据库，也不允许其他进程写该数据库。,3.3.2 读者写者问题,2022/12/10,81,为了解决读、写进程之间的同步，应设置两个信号量和一个共享变量；读互斥信号量rmutex，用于使读进程互斥地访问共享变量count，其初值为1，写互斥信号量wmutex，用于实现写进程与读进程的互斥及写进程与写进程的互斥，其初值为1；共享变量count，用于记录当前正在读数据库的读进程数目，初值为0。其工作过程如下：同教材。,3.3.2 读者写者问题,2022/12/10,82,2、(中国科学院软件研究所95年试题) 多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。请：(1)说明进程间的相互制约关系，应设置哪些信号量？,3.3.2 读者写者问题,2022/12/10,83,(2)用P、V操作写出其同步算法。(3)修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等待。而无论是否有读者在读文件。,3.3.2 读者写者问题,2022/12/10,84,解：(1)进程间的相互制约关系有三类： 一是读者之间允许同时读； 二是读者与写者之间须互斥； 三是写者之间须互斥。,3.3.2 读者写者问题,2022/12/10,85,为解决读者、写者之间的同步，应设置两个信号量和一个共享变量：读互斥信号量rmutex，用于使读者互斥地访问共享变量count，其初值为1，写互斥信号量wmutex，用于实现写者与读者的互斥及写者及写者的互斥，其初值为1，共享变量count，用于记录当前正在读文件的读者数目，初值为0。,3.3.2 读者写者问题,2022/12/10,86,(2)进程间的控制算法如下： reader:begin repeat p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); 读文件；,3.3.2 读者写者问题,2022/12/10,87,p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until false end,3.3.2 读者写者问题,2022/12/10,88,Writer:begin repeat p(wmutex); 写文件； v(wmutex); until false; end,3.3.2 读者写者问题,2022/12/10,89,(3)为了提高写者的优先级，增加一个信号量s，其初值为1，表示未有写进程正在写。用于在写进程到达后封锁后续的读者。 其过程如下：,3.3.2 读者写者问题,2022/12/10,90,Reader:begin repeat p(s); p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); v(s);,3.3.2 读者写者问题,2022/12/10,91,读文件； p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until false; end,3.3.2 读者写者问题,2022/12/10,92,Writer:begin repeat p(s); p(wmutex); 写文件； v(mutex); v(s); until false; end,3.3.2 读者写者问题,2022/12/10,93,3、在一个飞机订票系统中，多个用户共享一个数据库。多用户同时查询是可以接受的，但若一个用户要订票需更新数据库时，其余所有用户都不可以访问数据库。请画出用户查询与订票的逻辑框图。要求：当一个用户订票而需要更新数据库时，不能因不断有查询者的到来而使他长期等待。,3.3.2 读者写者问题,2022/12/10,94,本题是一个典型的“读者写者”问题，查询者是读者，订票者是写者，而且要求写者优先。 为此，应设置五个信号量rsem、wsem、rm、wm、wait，两个共享变量rcount、wcount。 共享变量rcount，用于记录当前正在查询的用户数，初值为0。 共享变量wcount，用于记录当前正在订票的用户数，初值为0。,3.3.2 读者写者问题,2022/12/10,95,信号量rm用于使查询用户互斥地访问共享变量rcount，其初值为1。 信号量wm用于使订票用户互斥地访问共享变量wcount，其初值为1。 信号量rsem用于在订票者到达后封锁后续查询者，其初值为1。,3.3.2 读者写者问题,2022/12/10,96,信号量wsem用于实现订票者与查询者的互斥以及订票者与订票者的互斥，其初值为1。 信号量wait用于查询者排队（为了实现订票者优先，rsem上不允许排长队，否则订票者无法跳过这个队列，为此，只允许一个查询者在rsem上排队，而所有其他查询者在等待rsem之前，在信号量wait上排队），其初值为1。用户查询和订票的逻辑框图如下：,3.3.2 读者写者问题,P(wait),P(rsem),P(rm),rcount=rcount+1,rcount=1?,P(wsem),V(rm),V(rsem),V(wait),在数据库中查询所需信息,P(rm),rcount=rcount1,rcount=0?,V(wsem),V(rm),N,Y,N,Y,查询者,用户查询的逻辑框图,P(wm),wcount=wcount+1,wcount=1?,P(rsem),V(wm),P(wsem),更新数据库中的数据信息,P(wm),wcount=wcount1,wcount=0?,V(rsem),V(wm),N,N,Y,Y,V(wsem),订票者,用户订票的逻辑框图,2022/12/10,99,问题设有n个进程共享一个程序段，对于如下两种情况：（1）如果每次只允许一个进程进入该程序段。（2）如果每次最多允许m个进程（mn）同时进入该程序段。 试问：所采用的信号量初值是否相同？信号量值的变化范围如何？,3.3.2 读者写者问题,2022/12/10,100,二、利用信号量集机制解决读者写者问题(最多允许RN个读者同时读)对前述的读者和写者问题，增加一条限制，即最多允许RN个读者同时读。所以，又引入一个信号量L，其初值为RN，用执行Swait(L,1,1)控制读者的数目，每当有一个读者进入时，要先执行Swait(L,1,1)操作，使L减1。当有RN个读者正在读时，RN为0，第RN1个读者执行Swait(L,1,1)时失败而被阻塞。利用信号量集解决读者写者问题描述如下：,3.3.2 读者写者问题,2022/12/10,101,var RN integer; L,mutex:semaphore:=RN,1; begin parbegin reader:begin repeat swait(L,1,1); swait(mutex,1,0);其功能是mutex为0时，阻塞 perform read operation; signal(L,1); until false; end,reader:begin repeat swait(L,1,1); swait(mutex,1,0);