操作系统复习资料全第二章进程管理-经典同步问题.ppt

《操作系统复习资料全第二章进程管理-经典同步问题.ppt》由会员分享，可在线阅读，更多相关《操作系统复习资料全第二章进程管理-经典同步问题.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习v为什么需要进程同步？v哪些进程需要同步？v进程同步的两种解决方法v什么是临界资源和临界区？v信号量的物理意义？v信号量有哪些应用？并发进程的同步问题（包括资源共享和进程之并发进程的同步问题（包括资源共享和进程之间的合作），是多道环境下操作系统必须解决间的合作），是多道环境下操作系统必须解决重要问题。否则，将会造成计算错误、资源不重要问题。否则，将会造成计算错误、资源不能共享、系统混乱等严重错误发生。能共享、系统混乱等严重错误发生。本节将研究几个典型的进程同步问题。本节将研究几个典型的进程同步问题。2.4 2.4 经典进程的同步问题经典进程的同步问题 进程同步机制应遵循的准则进程同步机制应

2、遵循的准则(掌握掌握)v空闲让进空闲让进v忙则等待忙则等待v有限等待有限等待v让权等待让权等待几种不同类型的信号量几种不同类型的信号量1 1、整型信号量、整型信号量 （最早期的信号量实现）（最早期的信号量实现）v定义一个整型变量定义一个整型变量S S；v当当S0S0时，表示某类可用资源数目时，表示某类可用资源数目，即表示还有，即表示还有S S个资源空闲个资源空闲可供共享使用；可供共享使用；v当当S S0 0时，其绝对值表示信号量时，其绝对值表示信号量S S所代表资源的阻塞队列中所代表资源的阻塞队列中的进程数的进程数，即系统中因请求该类资源而被阻塞的进程数目。，即系统中因请求该类资源而被阻塞的进

3、程数目。v信号量信号量S S的值除初始化（为资源数目）外，其值只能通过原的值除初始化（为资源数目）外，其值只能通过原语语waitwait和和signalsignal，也称，也称P P、V V操作来改变。操作来改变。整型信号量的整型信号量的P P、V V操作描述操作描述wait和和signal操作原语为：操作原语为：wait(S):while S0 do no-op；S=S-1;signal(S):S=S+1;解释：解释：P P或或waitwait操作：操作：当当S0S0时，说明无资源可用，时，说明无资源可用，一直测试一直测试直到其他进程直到其他进程释放该类资源。释放该类资源。V V或或sign

4、alsignal操作：操作：使用完资源时释放该资源，简单地将资源数目加一即可。使用完资源时释放该资源，简单地将资源数目加一即可。并不需要唤醒等待该资源的进程（并不需要唤醒等待该资源的进程（为什么为什么）。）。2.记录型信号量记录型信号量v整型信号量机制中的整型信号量机制中的wait操作，操作，只要信号量只要信号量S0，就会不断地测试就会不断地测试,系统处于空转状态系统处于空转状态。因此，该机制并因此，该机制并未遵循未遵循“让权等待让权等待”的准则，的准则，而是使而是使进程处于进程处于“忙等忙等”的状态。的状态。v记录型信号量机制，采用记录型信号量机制，采用“让权等待让权等待”策略，策略，必然出

5、现多个进程等待访问同一临界资源的必然出现多个进程等待访问同一临界资源的情况。为此，信号量设置除需要一个用于代情况。为此，信号量设置除需要一个用于代表资源数目的整型变量表资源数目的整型变量value外，还应增加一外，还应增加一个个进程链表进程链表L，用于链接等待资源的进程队列。，用于链接等待资源的进程队列。2.记录型信号量的定义记录型信号量的定义type semaphore=record value:integer;L:list of process;end相应地，相应地，wait(S)操作可描述为：操作可描述为：procedure wait(S)var S:semaphore;begin S.

6、value=S.value-1;if S.value0 then block(S,L)end2.记录型信号量的定义记录型信号量的定义signal(S)操作可描述为操作可描述为procedure signal(S)var S:semaphore;begin S.value=S.value+1;if S.value0 then wakeup(S,L);end3.AND型信号量型信号量v假若并发进程假若并发进程A和和B都要访问两个数据都要访问两个数据D和和E，因共，因共享数据为临界资源。为享数据为临界资源。为D和和E设置用于互斥的信号量设置用于互斥的信号量分别为分别为Dmutex和和Emutex，且

7、，且初始值为初始值为1，则进程，则进程A和和B共享临界数据共享临界数据D和和E必须进行同步操作：必须进行同步操作：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

8、);于是于是Dmutex=-1 B阻塞阻塞 形成死锁！形成死锁！AND同步机制的基本思想是：同步机制的基本思想是：v将进程在整个运行过程中需要的所有资源，将进程在整个运行过程中需要的所有资源，一次性一次性全部分配给进程全部分配给进程，待进程使用完后再一起释放。只，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。之分配的资源，也不分配给他。v为实现这种机制，在为实现这种机制，在wait操作中增加了一个操作中增加了一个“AND”条件，故称为条件，故称为AND同步，或称为同步，或称为同时同时wait操作，

9、即操作，即Swait(Simultaneous wait)定义如下：定义如下：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 first Si found with Si1,and set the program count of this process to the beginning of Swait operation endifSsignal(S1,S2,Sn)for

10、 i=1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;4.信号量集（自学）信号量集（自学）v之前的信号量机制在分配资源时之前的信号量机制在分配资源时一次只能分一次只能分配一个单位配一个单位的资源，当进程对某类资源的需的资源，当进程对某类资源的需求量不是求量不是1个，而是个，而是N个时，就需要执行个时，就需要执行N次次P操作，操作，V操作也是一样，效率较低。为此，引操作也是一样，效率较低。为此，引入信号量集。入信号量集。v信号量

11、集定义如下：信号量集定义如下：Swait(S1,t1,d1,Sn,tn,dn)/S为信号量，为信号量，t为下限，为下限，d为需求量为需求量 if Sit1 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 Siti and set its program counter to the beginning of the Swait Operation.endifsignal(S1,d1,Sn,dn)

12、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;信号量集的几种特殊情况：1）Swait(S，d，d)：此时在信号量集中只有一个信：此时在信号量集中只有一个信号量号量S，但允许它每次申请，但允许它每次申请d个资源，当现有资源数个资源，当现有资源数少于少于d时，不予分配。时，不予分配。2）Swait(S，1，1)：此时的信号量集已蜕化为一般：此时的信号量集已蜕化为一般的记录型信号量的记录型信号量(S1时时)或互斥

13、信号量或互斥信号量(S=1时时)。3）Swait(S，1，0）：这是一种很特殊且很有用的）：这是一种很特殊且很有用的信号量操作。当信号量操作。当S1时，允许多个进程进入某特定时，允许多个进程进入某特定区；当区；当S变为变为0后，将阻止任何进程进入特定区。换后，将阻止任何进程进入特定区。换言之，它相当于一个言之，它相当于一个可控开关可控开关。2.4.1 2.4.1 生产者生产者消费者问题消费者问题一组生产者生产产品一组生产者生产产品一组消费者取走产品一组消费者取走产品1n3n-12公用缓冲池，共有公用缓冲池，共有n n个缓冲区个缓冲区inoutVar mutex,empty,full:semap

14、hore:=1,n,0;buffer:array0,n-1 of item;in,out:integer:=0,0;/空、满缓冲区队列起始位置空、满缓冲区队列起始位置 begin parbegin proceducer:begin repeat producer an item nextp;/nextp为临时缓冲区为临时缓冲区 buffer(in):=nextp;in:=(in+1)mod n;until false;end consumer:begin repeat wait(full);wait(mutex);nextc:=buffer(out);/临时消费缓冲区临时消费缓冲区 out:=

15、(out+1)mod n;signal(mutex);signal(empty);consumer the item in nextc;until false;end parend end 每次都是两个每次都是两个wait和两个和两个signal操作，因此可以改造成操作，因此可以改造成AND型信号量。型信号量。2.2.利用利用ANDAND信号量解决生产者信号量解决生产者消费者问题消费者问题 var mutex,empty,full：semaphore：=1,n,0;buffer:array0,n-1 of item;in out:integer：=0,0;begin parbegin prod

16、ucer:begin repeat produce an item in nextp;Swait(empty,mutex);buffer(in)=nextp;in=(in+1)mod n;Ssignal(mutex,full);until false;end consumer:begin repeat Swait(full,mutex);nextc：=buffer(out);out：=(out+1)mod n;Ssignal(mutex,empty);consumer the item in nextc;until false;end parend end 2.4.2 2.4.2 哲学家进餐问

17、题哲学家进餐问题 1.1.利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题问问题题：5 5位位哲哲学学家家进进餐餐共共用用一一张张圆圆桌桌，分分别别坐坐在在周周围围的的5 5把把椅椅子子上上，每每座座位位前前依依次次前前摆摆放放一一个个碗碗一一个个筷筷子子（即即桌桌上上共共5 5个个碗碗和和5 5只只筷筷子子）。哲学家生活方式是交替思考和进餐。哲学家生活方式是交替思考和进餐。经经分分析析可可知知，放放在在桌桌子子上上的的筷筷子子是是临临界界资资源源，在在一一段段时时间间内内只只允允许许一一位位哲哲学学家家使使用用。为为了了实实现现对对筷筷子子的的互互斥斥使使用用，可可以以用

18、用一一个个信信号号量量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：表示一只筷子，由这五个信号量构成信号量数组。其描述如下：第第i i位哲学家的活动可描述为：位哲学家的活动可描述为：Var chopstick:array0,4 of semaphore=（1,1,1,1,1);repeat wait(chopsticki);wait(chopstick(i+1)mod 5);eat;signal(chopsticki);signal(chopstick(i+1)mod 5);think;until false;问题：上述算法有可能引起死锁。为什么？如何解决？问题：上述算法有可能引起死

19、锁。为什么？如何解决？可采取以下几种解决方法：可采取以下几种解决方法：1.1.至至多多只只允允许许有有四四位位哲哲学学家家同同时时去去拿拿左左边边的的筷筷子子，最最终终能能保保证证至至少少有一位哲学家能够进餐。有一位哲学家能够进餐。（增加一个总资源信号量（增加一个总资源信号量S=4S=4）2.2.仅仅当当哲哲学学家家的的左左、右右两两只只筷筷子子均均可可用用时时，才才允允许许他他拿拿起起筷筷子子进进餐餐（ANDAND型信号量）。型信号量）。3.3.规规定定奇奇数数号号哲哲学学家家先先拿拿他他左左边边的的筷筷子子，然然后后再再去去拿拿右右边边的的筷筷子子；而而偶偶数数号号哲哲学学家家则则相相反反

20、。按按此此规规定定，将将是是1 1、2 2号号哲哲学学家家竞竞争争1 1号号筷筷子子；3 3、4 4号号哲哲学学家家竞竞争争3 3号号筷筷子子。即即五五位位哲哲学学家家都都先先竞竞争争奇奇数数号号筷筷子子，获获得得后后，再再去去竞竞争争偶偶数数号号筷筷子子，最最后后总总会会有有一一位位哲哲学学家家能获得两只筷子而进餐。能获得两只筷子而进餐。2.2.利用利用ANDAND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题在在哲哲学学家家进进餐餐问问题题中中，要要求求每每个个哲哲学学家家先先获获得得两两个个临临界界资资源源(筷筷子子)后后方方能能进进餐餐，这这在在本本质质上上就就是是前前面面所

21、所介介绍绍的的ANDAND同同步步问问题题，故故用用ANDAND信信号号量量机机制制可可获得最简洁的解法。获得最简洁的解法。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+1)mod 5,chopstick i);until false;另外两种方法，自己试着写代码实现另外两种方法，自己试着写代码实现2.4.3 2.4.3 读者读者-写者问题写者问题 （自学，学期结束再讲）

22、（自学，学期结束再讲）读读者者-写写者者问问题题：有有多多个个并并发发执执行行的的进进程程对对一一个个数数据据文文件件或或一一个个记记录录或或一一个个变变量量进进行行共共享享，要要求求在在同同一一时时间间段段可可由由多多个个读读者者进进程程共共享享文文件件，而而写写者者进进程程与与读读者者进进程程、写写者者进进程程与与写写者者进进程程只只能能互互斥斥共共享享文文件件。这这就就是是读读者者-写写者者进程同步问题。如何解决？进程同步问题。如何解决？2.4.3 2.4.3 读者读者-写者问题写者问题 1.1.利用记录型信号量解决读者利用记录型信号量解决读者-写者问题写者问题F为为实实现现Reader

23、Reader与与WriterWriter进进程程间间在在读读或或写写时时的的互互斥斥而而设设置置了了一一个个互互斥信号量斥信号量WmutexWmutex；F设置一个整型变量设置一个整型变量ReadcountReadcount表示正在读的进程数目；表示正在读的进程数目；F当当Readcount=0Readcount=0时时，表表示示尚尚无无ReaderReader进进程程在在读读时时，ReaderReader进进程程才才需需要要执执行行Wait(Wmutex)Wait(Wmutex)操操作作。若若wait(Wmutex)wait(Wmutex)操操作作成成功功，做做Readcount+1Read

24、count+1和读文件操作；和读文件操作；F当当ReaderReader进进程程在在执执行行了了ReadcountReadcount减减1 1操操作作后后其其值值为为0 0时时，才才须须执行执行signal(Wmutex)signal(Wmutex)操作，以便让操作，以便让WriterWriter进程写；进程写；F又又因因为为ReadcountReadcount是是一一个个可可被被多多个个ReaderReader进进程程访访问问的的临临界界资资源源，因此，应该为它设置一个互斥信号量因此，应该为它设置一个互斥信号量rmutexrmutex。读者读者-写者问题可描述如下：写者问题可描述如下：Var

25、 rmutex,wmutex:semaphore=1,1;Readcount:integer=0;begin parbegin Reader:begin repeat wait(rmutex);/对对Readcount互斥访问互斥访问 if readcount=0 then wait(wmutex);/第一个进入读访问的进程关闭写进程进入第一个进入读访问的进程关闭写进程进入 Readcount=Readcount+1;signal(rmutex);perform read operation;wait(rmutex);/要对要对readcount资源互斥访问资源互斥访问 readcount=r

26、eadcount-1;if readcount=0 then signal(wmutex);signal(rmutex);until false;end writer:begin repeat wait(wmutex);perform write operation;signal(wmutex);until false;end parend end 2.2.利用信号量集机制解决读者利用信号量集机制解决读者-写者问题写者问题 Var RN integer;/最多允许最多允许RN读者进程共享文件读者进程共享文件 L,mx:semaphore=RN,1;/L/L读者数控制信号量，读者数控制信号量，m

27、xmx写互斥信号量写互斥信号量 begin parbegin reader:begin repeat Swait(L,1,1);/读进程检查读进程检查L=1L=1，才可进入临界区，才可进入临界区 Swait(mx,1,0);/如果无写进程进入临界区，如果无写进程进入临界区，mx=1mx=1 perform read operation;Ssignal(L,1);until false;end writer:begin repeat Swait(mx,1,1;L,RN,0);/既无写者进程在写，又无读者进程在读时，才允许写进程进入临界区既无写者进程在写，又无读者进程在读时，才允许写进程进入临界区

28、 perform write operation;Ssignal(mx,1);until false;end parend end 练习题v三个进程P1、P2、P3互斥使用一个包含N(N0)个单元的缓冲区。P1每次用put()将一个正整数送入缓冲区的一个单元中，P2每次用getodd()从缓冲区中取出一个奇数，P3每次用geteven()从缓冲区中取出一个偶数。试用信号量机制实现这三个进程的互斥与同步活动，用伪代码实现。vSemaphoreempty=N,mutex=1,s1=s2=0;vp1()p(empty);p(mutex);put();if(是奇数)thenv(s1);elsev(s2);vv(mutex);p2()p(s1);p(mutex);getodd();v(mutex);v(empty);p3()p(s2);p(mutex);geteven();v(mutex);v(empty);