OS5_6(信号量机制)ppt课件

3.3.2信号量(semaphore)机制P51,前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段1965年，由荷兰学者Dijkstra提出，他把互斥的关键概念抽象到信号量这个概念中，是一种卓有成效的进程同步机制,1、整型信号量机制2、记录型信号量机制3、信号量集机制,信号量是一个被保护的变量，并且只能通过初始化和两个标准的原子操作来访问.,1、整型信号量机制,1).整型信号量是一个整数，表示空闲资源总数（又称为“资源信号量”）-若为非负值表示当前的空闲资源数，-为负值其绝对值表示当前等待临界区的进程数-初值应该大于零。两个原子操作即:P,V操作。也常称为wait(s),singal(s)（P、V分别是荷兰语的test(proberen)和increment(verhogen)）即：P(s):Wait(s):whiles=0dono_ops:=s-1;V(s):Singal(s):s:=s+1;,process1:beginrepeatP(mutex);critcialsection;V(mutex);remaindersection;untilfalse;end,2).利用信号量实现互斥,利用信号量实现进程互斥：Varmutex:semaphore；/说明一个信号量process1:beginrepeatwait(mutex);criticalsection;signal(mutex);remaindersection;untilfalse;end,process2:beginrepeatwait(mutex);criticalsection;signal(mutex);remaindersection;untilfalse;end,为临界资源设置一个互斥信号量mutex(MUTualEXclusion)，初值为1；在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间,注意：,必须成对使用wait和signal原语wait、signal原语不能出现次序错误、重复或遗漏遗漏wait原语则不能保证互斥访问遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；,3).利用信号量来描述前趋（合作）关系,前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；,C1,C2,为每个前趋关系设置一个互斥信号量S12，其初值为0,例：用信号量来描述如下的前趋图,beginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;,Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0,0;ParbeginParend;,引入进程阻塞机制,在信号量里增加对阻塞进程的记录,2、记录型信号量机制,P(s),s.value=s.value-1,s.value0?,本进程获得一个资源,临界区/资源访问区,本进程进入s.list队列，进入阻塞状态,N,Y,V(s),s.value=s.value+1,s.value=0?,将s.list中第一个进程唤醒，,N,Y,记录型信号量的P，V操作(wait(s)和signal(s),Procedurewait(s)varS:semaphore;beginS.value:=s.value-1;ifS.value0thenblock(S,L);end;Proceduresignal(s)VarS:semaphore;BeginS.value:=S.value+1;IfS.value=0thenwakeup(S.L);End;,伪码描述,当s.value初值为1时，转化为互斥信号量,3、信号量集,信号量集用于进程需要多个资源时的信号量操作；,整型信号量机制和记录型信号量机制都是针对进程间要共享一个临界资源而言的；当一段处理代码需要同时获取两个或多个临界资源时，使用整型或记录型信号量，会产生各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”的问题-死锁。如：A,B进程都要访问共享资源D,E.,1)AND型信号量集机制,将一段代码同时需要的多个临界资源，采用原子方式，要么全分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。同样地，使用结束后一起释放，称为Ssignal;,基本思想：,Swait(SimultaneousWait),Swait(S1,S2,Sn)/P原语；if(S11andS21Sn1)/满足资源要求时的处理；for(i=1;i=n;+i)Si=Sj-1;/注：与wait的处理不同，这里是在确信可满足/资源要求时，才进行减1操作else/某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue,阻塞调用进程;,Ssignal(S1,S2,Sn)for(i=1;i=1时，可以通过测试，允许多个进程进入某特定区；当S=0时，无法通过测试，禁止任何进程进入某特定区；,一般信号量集的基本思想：在AND型信号量集的基础上进行扩充,扩充为进程需要申请多个资源，每个资源可能申请多个的情况，每个资源对应一个信号量Si：进程对资源i的需求值为di:每次申请或释放di个，Si=Si-di和Si=Si+di资源i的测试值为ti:当资源个数小于ti时，便不再分配,PV原子操作：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);,多个进程共享一个临界资源,And型信号量集机制：同时需要多种资源且每种占用一个时的信号量操作；,一般信号量集机制：同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；,信号量,整型信号量机制记录型信号量机制信号量集机制,3.3.3经典进程同步问题P58,生产者消费者问题(producer-consumerproblem),问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程.可对共享缓冲区进行操作。,消费者,生产者,共享缓冲区,放产品,取产品,一次只可放一个产品,生产者-消费者同步的关键问题,需要保证以下同步关系：1.多个进程互斥地访问公共缓冲区；2.不能向满的缓冲区中添加产品；3.不能从空的缓冲区中提取产品。,互斥信号量mutex可用的空资源信号量empty可用的满资源信号量full,full+empty=N,涉及两类进程：生产者进程和消费者进程,每个进程中各个wait操作的次序是重要的：先检查资源数目，再检查是否互斥.思考：否则会怎样(?)采用AND信号量集：Swait(empty,mutex)；|Swait(full,mutex)；Ssignal(mutex,full)；|Ssignal(mutex,empty);,Producer,Consumer,varmutex,full,empty:semaphore:=1,n,0,采用记录型信号量机制解决该同步问题,2.读者写者问题(readers-writersproblem),问题描述：一个数据对象（数据文件或记录），可以被多个进程共享。其中有些进程要读，有些要写或修改。允许多个读者进程同时读一个共享对象，但不允许一个写者进程和其它读者或写者进程同时访问共享对象。,该同步问题涉及两类进程：读者（reader)进程和写者(writer)进程。并且，这两个进程的同步问题就是指:保证“读写”互斥，“写写”互斥，“读读”允许的问题。,Wmutex：互斥信号量：表示“允许写”，初值是1。公共变量Readcount表示“正在读”的进程数，初值是0；Rmutex:互斥信号量：表示对Readcount的互斥操作，初值是1。,A.采用记录型信号量机制,WriterSwait(mx,1,1;L,RN,0);Write;Ssignal(mx,1),ReaderSwait(L,1,1;mx,1,0)；Read;Ssignal(L,1),采用一般“信号量集”机制：增加一个限制条件:同时读的读者最多R个mx表示允许写，初值是1L表示当前允许读者数目，初值为RN,B.采用一般信号量集机制,/保证多个读，有人写时不能读（进入读的开关）,/有人读时不能写：（进入写的开关）/并与写互斥,3.哲学家进餐问题(thediningphilosophersproblem)（由Dijkstra首先提出并解决）,问题描述：5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时进餐的冲突情况.,进餐,不能进餐,进餐,问题分析,可以保证不会有两个相邻的哲学家同时进餐；但会引起死锁。,临界资源：筷子为临界资源设置信号量：varchopstick:array04ofsemaphore;初值均为1。,则第i个哲学家的动作可描述为：wait(chopsticki);wait(chopsticki+1mod5);eat;signal(chopsticki);signal(chopsticki+1mod5);think;,死锁,不能进餐！,不能进餐！,不能进餐！,不能进餐！,不能进餐！,死锁问题的几种解决方法P62,1）最多只允许四个哲学家同时进餐，以保证至少一个哲学家能够进餐，最终释放出他所使用过的筷子，从而使得更多的哲学家进餐。2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。3）规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。,方法一：加一个资源信号量,Varchopstick:array04ofsemaphore=(1,1,1,1,1);Varcount:semaphore:=4;第i个哲学家的活动：repeatwait(count);wait(chopsticki);wait(chopstickI+1mod5);eat;signal(chopsticki);signal(chopstickI+1mod5);signal(count);think;Untilfalse;,方法二:左、右两只筷子均可用时，才允许拿起进餐,Varchopstick:array0,4ofsemaphore:=(1,1,1,1,1)ProcessIRepeatthink;swait(chopstick(i+1)mod5,chopsticki);eat;ssginal(chopstick(i+1)mod5,chopsticki);Untilfalse;,And信号量机制解决。每个筷子设一个信号量P62.,方法三,Varchopstick:array04ofsemaphore=（1,1,1,1,1）;第i个哲学