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

复习,为什么需要进程同步？哪些进程需要同步？进程同步的两种解决方法什么是临界资源和临界区？信号量的物理意义？信号量有哪些应用？,并发进程的同步问题（包括资源共享和进程之间的合作），是多道环境下操作系统必须解决重要问题。否则，将会造成计算错误、资源不能共享、系统混乱等严重错误发生。本节将研究几个典型的进程同步问题。,2.4 经典进程的同步问题,进程同步机制应遵循的准则(掌握),空闲让进忙则等待有限等待让权等待,几种不同类型的信号量,1、整型信号量（最早期的信号量实现）定义一个整型变量S；当S0时，表示某类可用资源数目，即表示还有S个资源空闲可供共享使用；当S0时，其绝对值表示信号量S所代表资源的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程数目。信号量S的值除初始化（为资源数目）外，其值只能通过原语wait和signal，也称P、V操作来改变。,整型信号量的P、V操作描述,wait和signal操作原语为：wait(S):while S0 do no-op；S=S-1;signal(S):S=S+1;解释：P或wait操作：当S0时，说明无资源可用，一直测试直到其他进程释放该类资源。V或signal操作：使用完资源时释放该资源，简单地将资源数目加一即可。并不需要唤醒等待该资源的进程（为什么）。,2.记录型信号量,整型信号量机制中的wait操作，只要信号量S0，就会不断地测试,系统处于空转状态。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，采用“让权等待”策略，必然出现多个进程等待访问同一临界资源的情况。为此，信号量设置除需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接等待资源的进程队列。,2.记录型信号量的定义,type semaphore=record value:integer;L:list of process;end相应地，wait(S)操作可描述为：procedure wait(S)var S:semaphore;begin S.value=S.value-1;if S.value0 then block(S,L)end,2.记录型信号量的定义,signal(S)操作可描述为procedure signal(S)var S:semaphore;begin S.value=S.value+1;if S.value0 then wakeup(S,L);end,3.AND型信号量,假若并发进程A和B都要访问两个数据D和E，因共享数据为临界资源。为D和E设置用于互斥的信号量分别为Dmutex和Emutex，且初始值为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);于是Dmutex=-1 B阻塞 形成死锁！,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。为实现这种机制，在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即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 endif,Ssignal(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;,4.信号量集（自学）,之前的信号量机制在分配资源时一次只能分配一个单位的资源，当进程对某类资源的需求量不是1个，而是N个时，就需要执行N次P操作，V操作也是一样，效率较低。为此，引入信号量集。信号量集定义如下：,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.endif,signal(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;,信号量集的几种特殊情况：,1）Swait(S，d，d)：此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。2）Swait(S，1，1)：此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。3）Swait(S，1，0）：这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。,2.4.1 生产者消费者问题,一组生产者生产产品,一组消费者取走产品,1,n,3,n-1,2,公用缓冲池，共有n个缓冲区,in,out,Var mutex,empty,full:semaphore:=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:=(out+1)mod n;signal(mutex);signal(empty);consumer the item in nextc;until false;end parend end 每次都是两个wait和两个signal操作，因此可以改造成AND型信号量。,2.利用AND信号量解决生产者消费者问题,var mutex,empty,full：semaphore：=1,n,0;buffer:array0,n-1 of item;in out:integer：=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,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 哲学家进餐问题,利用记录型信号量解决哲学家进餐问题问题：5位哲学家进餐共用一张圆桌，分别坐在周围的5把椅子上，每座位前依次前摆放一个碗一个筷子（即桌上共5个碗和5只筷子）。哲学家生活方式是交替思考和进餐。经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：,第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;问题：上述算法有可能引起死锁。为什么？如何解决？,可采取以下几种解决方法：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。（增加一个总资源信号量S=4）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐（AND型信号量）。规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。,2.利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。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 读者-写者问题,1.利用记录型信号量解决读者-写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex；设置一个整型变量Readcount表示正在读的进程数目；当Readcount=0时，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，做Readcount+1和读文件操作；当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写；又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。,读者-写者问题可描述如下：Var 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=readcount-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.利用信号量集机制解决读者-写者问题,Var RN integer;/最多允许RN读者进程共享文件 L,mx:semaphore=RN,1;/L读者数控制信号量，mx写互斥信号量 begin parbegin reader:begin repeat Swait(L,1,1);/读进程检查L=1，才可进入临界区 Swait(mx,1,0);/如果无写进程进入临界区，mx=1 perform read operation;,Ssignal(L,1);until false;end writer:begin repeat Swait(mx,1,1;L,RN,0);/既无写者进程在写，又无读者进程在读时，才允许写进程进入临界区 perform write operation;Ssignal(mx,1);until false;end parend end,练习题,三个进程P1、P2、P3互斥使用一个包含N(N0)个单元的缓冲区。P1每次用put()将一个正整数送入缓冲区的一个单元中，P2每次用getodd()从缓冲区中取出一个奇数，P3每次用geteven()从缓冲区中取出一个偶数。试用信号量机制实现这三个进程的互斥与同步活动，用伪代码实现。,Semaphore empty=N,mutex=1,s1=s2=0;p1()p(empty);p(mutex);put();if(是奇数)then v(s1);else v(s2);v(mutex);p2()p(s1);p(mutex);getodd();v(mutex);v(empty);p3()p(s2);p(mutex);geteven();v(mutex);v(empty);,