OS5_6(信号量机制)ppt课件

Lifang2011*OperatingSystem3.3.2信号量(semaphore)机制P51 前面的互斥算法都存在问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段 1965年，由荷兰学者Dijkstra提出，他把互斥的关键概念抽象到信号量这个概念中，是一种卓有成效的进程同步机制1、整型信号量机制2、 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 型信号量机制3、信号量集机制 信号量是一个被保护的变量，并且只能通过初始化和两个标准的原子操作来访问.（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）goto有害论Dijkstra最短路径算法Lifang2011*OperatingSystem1、整型信号量机制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;Lifang2011*OperatingSystemprocess1:beginrepeat P(mutex); critcialsection; V(mutex); remaindersection;untilfalse;end2).利用信号量实现互斥利用信号量实现进程互斥：Varmutex:semaphore；//说明一个信号量process1: begin repeat wait(mutex); criticalsection; signal(mutex);remaindersection; untilfalse;end process2: begin repeat wait(mutex); criticalsection; signal(mutex);remaindersection; untilfalse;end 为临界资源设置一个互斥信号量mutex(MUTualEXclusion)，初值为1；在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间Lifang2011*OperatingSystem注意： 必须成对使用wait和signal原语 wait、signal原语不能出现次序错误、重复或遗漏 遗漏wait原语则不能保证互斥访问 遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；Lifang2011*OperatingSystem3).利用信号量来描述前趋（合作）关系 前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；C1C2 为每个前趋关系设置一个互斥信号量S12，其初值为0Lifang2011*OperatingSystem例：用信号量来描述如下的前趋图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;Lifang2011*OperatingSystem引入进程阻塞机制在信号量里增加对阻塞进程的记录2、记录型信号量机制Lifang2011*OperatingSystemP(s)s.value=s.value-1s.value<0?本进程获得一个资源临界区/资源访问区本进程进入s.list队列，进入阻塞状态NYV(s)s.value=s.value+1s.value<=0?将s.list中第一个进程唤醒，NY记录型信号量的P，V操作(wait(s)和signal(s))Lifang2011*OperatingSystemProcedurewait(s)varS:semaphore;begin S.value:=s.value-1; ifS.value<0thenblock(S,L);end;Proceduresignal(s)VarS:semaphore;Begin S.value:=S.value+1; IfS.value<=0thenwakeup(S.L);End;伪码描述当s.value初值为1时，转化为互斥信号量此时的互斥信号量是让权的。Lifang2011*OperatingSystem3、信号量集信号量集用于进程需要多个资源时的信号量操作； 整型信号量机制和记录型信号量机制都是针对进程间要共享一个临界资源而言的； 当一段处理代码需要同时获取两个或多个临界资源时，使用整型或记录型信号量，会产生各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”的问题---死锁。如：A,B进程都要访问共享资源D,E.Lifang2011*OperatingSystem1)AND型信号量集机制将一段代码同时需要的多个临界资源，采用原子方式，要么全分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。同样地，使用结束后一起释放，称为Ssignal;基本思想：Lifang2011*OperatingSystemSwait(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,阻塞调用进程;}}并将进程的程序计数器指向Swait操作的开始。Lifang2011*OperatingSystemSsignal(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)Lifang2011*OperatingSystem2)一般“信号量集”机制一次需要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);Lifang2011*OperatingSystem多个进程共享一个临界资源And型信号量集机制：同时需要多种资源且每种占用一个时的信号量操作；一般信号量集机制：同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；信号量整型信号量机制记录型信号量机制信号量集机制Lifang2011*OperatingSystem3.3.3经典进程同步问题P58 生产者－消费者问题(producer-consumerproblem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程.可对共享缓冲区进行操作。消费者生产者共享缓冲区放产品取产品一次只可放一个产品Lifang2011*OperatingSystem生产者--消费者同步的关键问题需要保证以下同步关系：1.多个进程互斥地访问公共缓冲区；2.不能向满的缓冲区中添加产品；3.不能从空的缓冲区中提取产品。互斥信号量mutex可用的空资源信号量empty可用的满资源信号量fullfull+empty=N涉及两类进程： 生产者进程和消费者进程一般情况下，每个同步关系对应一个信号量。转化为：可用的曼资源Lifang2011*OperatingSystem 每个进程中各个wait操作的次序是重要的：先检查资源数目，再检查是否互斥.思考：否则会怎样(?) 采用AND信号量集：Swait(empty,mutex)；|Swait(full,mutex)；Ssignal(mutex,full)；|Ssignal(mutex,empty); Producer Consumervarmutex,full,empty:semaphore:=1,n,0采用记录型信号量机制解决该同步问题 Wait(empty);Wait(mutex);//进入区 Oneunitbuffer; Signal(mutex);Signal(full);//退出区 Wait(full);Wait(mutex);//进入区 Oneunitbuffer; Signal(mutex);Signal(empty);//退出区可能死锁如：producer先申请互斥，进入后，申请空资源，发现空资源不可用，必须等待comsumer先申请满，使用后释放出来。但此时，由于producer占用了互斥资源，因此consumer无法进入。故而陷入死锁状态Lifang2011*OperatingSystem2.读者－写者问题(readers-writersproblem)问题描述：一个数据对象（数据文件或记录），可以被多个进程共享。其中有些进程要读，有些要写或修改。允许多个读者进程同时读一个共享对象，但不允许一个写者进程和其它读者或写者进程同时访问共享对象。该同步问题涉及两类进程： 读者（reader)进程和写者(writer)进程。并且，这两个进程的同步问题就是指: 保证“读－写”互斥， “写－写”互斥，“读－读”允许的问题。Lifang2011*OperatingSystemWmutex：互斥信号量：表示“允许写”，初值是1。公共变量Readcount表示“正在读”的进程数，初值是0；Rmutex:互斥信号量：表示对Readcount的互斥操作，初值是1。A.采用记录型信号量机制只描述了循环体对读没有约束，多少个读都可以Lifang2011*OperatingSystemWriterSwait(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.采用一般信号量集机制//保证多个读，有人写时不能读（进入读的开关）//有人读时不能写：（进入写的开关）//并与写互斥限定了读的个数Lifang2011*OperatingSystem3.哲学家进餐问题(thediningphilosophersproblem)（由Dijkstra首先提出并解决）问题描述：5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时进餐的冲突情况.进餐不能进餐进餐Lifang2011*OperatingSystem问题 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 可以保证不会有两个相邻的哲学家同时进餐；但会引起死锁。临界资源：筷子为临界资源设置信号量：varchopstick:array[0…4]ofsemaphore;初值均为1。则第i个哲学家的动作可描述为： wait(chopstick[i]); wait(chopstick[i+1]mod5); eat; signal(chopstick[i]); signal(chopstick[i+1]mod5); think;Lifang2011*OperatingSystem死锁不能进餐！不能进餐！不能进餐！不能进餐！不能进餐！Lifang2011*OperatingSystem死锁问题的几种解决方法P621）最多只允许四个哲学家同时进餐，以保证至少一个哲学家能够进餐，最终释放出他所使用过的筷子，从而使得更多的哲学家进餐。2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。3）规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。Lifang2011*OperatingSystem方法一：加一个资源信号量Varchopstick:array[0…4]ofsemaphore=(1,1,1,1,1);Varcount:semaphore:=4;第i个哲学家的活动： repeatwait(count); wait(chopstick[i]); wait(chopstick[I+1]mod5); eat; signal(chopstick[i]); signal(chopstick[I+1]mod5); signal(count); think;Untilfalse;一般的记录型信号量。解释嵌套Count现释放，必然会影响对筷子的申请。Count与筷子之间有制约关系。Count就是为了制约对筷子的访问的。Lifang2011*OperatingSystem方法二:左、右两只筷子均可用时，才允许拿起进餐Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1)ProcessIRepeat think; swait(chopstick[(i+1)mod5],chopstick[i]); eat; ssginal(chopstick[(i+1)mod5],chopstick[i]);Untilfalse;And信号量机制解决。每个筷子设一个信号量P62.不必引入新的资源信号量Lifang2011*OperatingSystem方法三Varchopstick:array[0…4]ofsemaphore=（1,1,1,1,1）;第i个哲学家的活动：Repeat ifimod2=1then begin//奇数哲学家 wait(chopstick[i]); wait(chopstick[I+1]mod5; eat; signal(chopstick[i]); signal(chopstick[I+1]mod5); end else begin//偶数哲学家 wait(chopstick[I+1]mod5; wait(chopstick[i]); eat; signal(chopstick[I+1]mod5); signal(chopstick[i]); End; think;Untilfalse;解释嵌套此初不嵌套右筷子不释放不会影响对左筷子的申请。即两个筷子之间没有制约关系。（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）goto有害论Dijkstra最短路径算法此时的互斥信号量是让权的。并将进程的程序计数器指向Swait操作的开始。一般情况下，每个同步关系对应一个信号量。转化为：可用的曼资源可能死锁如：producer先申请互斥，进入后，申请空资源，发现空资源不可用，必须等待comsumer先申请满，使用后释放出来。但此时，由于producer占用了互斥资源，因此consumer无法进入。故而陷入死锁状态只描述了循环体对读没有约束，多少个读都可以限定了读的个数一般的记录型信号量。解释嵌套Count现释放，必然会影响对筷子的申请。Count与筷子之间有制约关系。Count就是为了制约对筷子的访问的。不必引入新的资源信号量解释嵌套此初不嵌套右筷子不释放不会影响对左筷子的申请。即两个筷子之间没有制约关系。