操作系统5--信号量机制

20115.1/28操作系统3.3.2信号量(semaphore)机制P51前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段1965年，由荷兰学者Dijkstra提出，他把互斥的关键概念抽象到信号量这个概念中，是一种卓有成效的进程同步机制1、整型信号量机制2、记录型信号量机制3、信号量集机制信号量是一个被保护的变量，并且只能通过初始化和两个标准的原子操作来访问.20115.2/28操作系统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;20115.3/28操作系统process1:beginrepeatP(mutex);critcialsection;V(mutex);remaindersection;untilfalse;end2).利用信号量实现互斥利用信号量实现进程互斥：Varmutex:semaphore；//说明一个信号量process1:beginrepeatwait(mutex);criticalsection;signal(mutex);remaindersection;untilfalse;endprocess2:beginrepeatwait(mutex);criticalsection;signal(mutex);remaindersection;untilfalse;end为临界资源设置一个互斥信号量mutex(MUTualEXclusion)，初值为1；在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间20115.4/28操作系统注意：必须成对使用wait和signal原语wait、signal原语不能出现次序错误、重复或遗漏遗漏wait原语则不能保证互斥访问遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；20115.5/28操作系统3).利用信号量来描述前趋（合作）关系•前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；C1C2P2P1C1C2V(S12);P(S12);•为每个前趋关系设置一个互斥信号量S12，其初值为020115.6/28操作系统例：用信号量来描述如下的前趋图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;s1s2s4s5s3s6Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0,0;ParbeginParend;20115.7/28操作系统引入进程阻塞机制在信号量里增加对阻塞进程的记录typedefstructSemaphore{intvalue;process_list*list;}semaphore;资源个数阻塞进程（PCB）队列2、记录型信号量机制20115.8/28操作系统P(s)s.value=s.value-1s.value0?本进程获得一个资源临界区/资源访问区本进程进入s.list队列，进入阻塞状态NYV(s)s.value=s.value+1s.value=0?将s.list中第一个进程唤醒，NY记录型信号量的P，V操作(wait(s)和signal(s))20115.9/28操作系统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时，转化为互斥信号量20115.10/28操作系统3、信号量集信号量集用于进程需要多个资源时的信号量操作；整型信号量机制和记录型信号量机制都是针对进程间要共享一个临界资源而言的；当一段处理代码需要同时获取两个或多个临界资源时，使用整型或记录型信号量，会产生各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”的问题---死锁。如：A,B进程都要访问共享资源D,E.20115.11/28操作系统1)AND型信号量集机制将一段代码同时需要的多个临界资源，采用原子方式，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。同样地，使用结束后一起释放，称为Ssignal;基本思想：20115.12/28操作系统Swait(SimultaneousWait)Swait(S1,S2,…,Sn)//P原语；{if(S1≥1andS2≥1…Sn≥1){//满足资源要求时的处理；for(i=1;i=n;++i)Si=Sj-1;//注：与wait的处理不同，这里是在确信可满足//资源要求时，才进行减1操作}else{//某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue,阻塞调用进程;}}//次序并不重要，虽然会影响进程归入哪个阻塞队列，但由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁20115.13/28操作系统Ssignal(S1,S2,…,Sn){for(i=1;i=n;++i){++Si;//释放占用的资源；for(eachprocessPwaitinginSi.queue){//检查每种资源的等待队列中的所有进程；从等待队列Si.queue中取出进程P;if(判断P是否通过Swait中的测试){//注:与signal不同，需重新判断进程P进入就绪队列;break;}else{//未通过检查（资源不够用）时的处理；进程P进入某等待队列；//然后继续循环判断下一个进程}}}}Ssignal(SimultaneousSignal)20115.14/28操作系统2)一般“信号量集”机制一次需要N个某类临界资源时，要进行N次wait操作——低效一般“信号量集”的几种特定情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量；Swait(S,1,0)作为一个可控开关，并不申请资源当S=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);20115.15/28操作系统多个进程共享一个临界资源And型信号量集机制：同时需要多种资源且每种占用一个时的信号量操作；一般信号量集机制：同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；信号量整型信号量机制记录型信号量机制信号量集机制20115.16/28操作系统3.3.3经典进程同步问题P581.生产者－消费者问题(producer-consumerproblem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程.可对共享缓冲区进行操作。生产者共享缓冲区一次只可放一个产品20115.17/28操作系统生产者--消费者同步的关键问题需要保证以下同步关系：1.多个进程互斥地访问公共缓冲区；2.不能向满的缓冲区中添加产品；3.不能从空的缓冲区中提取产品。互斥信号量mutex可用的空资源信号量empty可用的满资源信号量fullfull+empty=N涉及两类进程：生产者进程和消费者进程20115.18/28操作系统每个进程中各个wait操作的次序是重要的：先检查资源数目，再检查是否互斥.否则可能死锁(?)采用AND信号量集：Swait(empty,mutex)；|Swait(full,mutex)；Ssignal(mutex,full)；|Ssignal(mutex,empty);ProducerWait(empty);Wait(mutex);//进入区Oneunitbuffer;Signal(mutex);Signal(full);//退出区ConsumerWait(full);Wait(mutex);//进入区Oneunitbuffer;Signal(mutex);Signal(empty);//退出区varmutex,full,empty:semaphore:=1,n,0采用记录型信号量机制解决该同步问题20115.19/28操作系统2.读者－写者问题(readers-writersproblem)问题描述：一个数据对象（数据文件或记录），可以被多个进程共享。其中有些进程要读，有些要写或修改。允许多个读者进程同时读一个共享对象，但不允许一个写者进程和其它读者或写者进程同时访问共享对象。该同步问题涉及两类进程：读者（reader)进程和写者(writer)进程。并且，这两个进程的同步问题就是指:保证“读－写”互斥，“写－写”互斥，“读－读”允许的问题。20115.20/28操作系统Wmutex：互斥信号量：表示“允许写”，初值是1。公共变量Readcount表示“正在读”的进程数，初值是0；Rmutex:互斥信号量：表示对Readcount的互斥操作，初值是1。A.采用记录型信号量机制Wait(Wmutex);Write;Signal(Wmutex);writerwait(Rmutex);if(Readcount=0)thenwait(wmutex)Readcount=Readcount+1;Signal(Rmutex);//关闭写的同时允许读（无上限）read;Wait(Rmutex);Readcount:=Readcount-1;ifReadcount=0thensignal(Wmutex);Signal(Rmutex);//适当的时候打开写reader20115.21/28操作系统WriterSwait(mx,1,1;L,RN,0);Write;Ssignal(mx,1)ReaderSwait(L,1,1;mx,1,0)；Read;Ssignal(L,1)采用一般“信号量集”机制：增加一个限制条件:同时读的读者最多R个mx表示允许写，初值是1L表示当前允许读者数目，初值为RNB.采用一般信号量集机制//保证多个读，有人写时不能读（进入读的开关）//有人读时不能写：（进入写的开关）//并与写互斥20115.22/28操作系统3.哲学家进餐问题(thediningphilosophersproblem)（由Dijkst