OS5,6(信号量机制)

1、Lifang 20151Operating System2.3.2 2.3.2 信号量信号量(semaphore)(semaphore)机制机制 P53P53前面的互斥算法都存在问题，它们是前面的互斥算法都存在问题，它们是平等进程平等进程间的一种间的一种协商协商机机制，需要一个地位高于进程的制，需要一个地位高于进程的管理者管理者来解决公有资源的使用问题来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，可从进程管理者的角度来处理互斥的问题，信号量信号量就是就是OS提提供的管理公有资源的有效手段供的管理公有资源的有效手段19651965年，由荷兰学者年，由荷兰学者Dijkstra

2、Dijkstra提出，提出，他把互斥的关键概念抽象他把互斥的关键概念抽象到信号量这个概念中，到信号量这个概念中，是一种卓有成效的进程同步机制是一种卓有成效的进程同步机制1 1、整型信号量机制、整型信号量机制2 2、记录型信号量机制、记录型信号量机制3 3、信号量集机制、信号量集机制信号量是一个被保护的变量，并且只能通过信号量是一个被保护的变量，并且只能通过初始化初始化和和两个标准两个标准的原子操作的原子操作来访问来访问. .Lifang 20152Operating System1 1、整型信号量机制、整型信号量机制1).1).整型信号量整型信号量是一个整数值，表示是一个整数值，表示空闲资源总

3、数空闲资源总数（又称为（又称为“资源信号量资源信号量”）-若为非负值表示若为非负值表示当前的空闲资源数当前的空闲资源数，-为负值其绝对值表示为负值其绝对值表示当前等待临界区的进程数当前等待临界区的进程数-初值应该大于零。初值应该大于零。v两个原子操作即两个原子操作即: P,V: P,V操作。也常称为操作。也常称为wait(s),singal(s)wait(s),singal(s)（P P、V V分别是荷兰语的分别是荷兰语的test(proberen)test(proberen)和和increment(verhogen)increment(verhogen)）即：即：P(s): Wait(s):

4、 while s=0 P(s): Wait(s): while s=1 then y:=y+1;(4) z:=y;EndparendProcess P2var t,u:integer;Begin(5) x:=0;(6) t:=0;(7) if x=1 then y:=y+1;V(s);(4) z:=y;EndparendProcess P2var t,u:integer;BeginP(s);(5) x:=0;(6) t:=0;(7) if x=1 then t:=t+2;V(s);(8) u:=t;End改正方法：找到临界区，设置信号量s，初值为1Lifang 20159Operating S

5、ystem实例2假设在某单CPU系统中有两个合作进程P1、P2，他们的主要操作如下：P1： Calculating;P2：InputOutput;若要求的执行顺序为：InputCalculatingOutput;请用信号量上的P、V操作实现P1和P2进程的协调执行。Lifang 201510Operating System实例2P1： Calculating;P2：InputOutput;CalculatingInputOutput画出该问题的前趋图：ICOP1 P2P(s1)CalculatingV(s2)InputV(s1)P(s2)OutputP1 P2设置信号量s1,s2,初值为0同步

6、方案：Lifang 201511Operating System引入进程阻塞机制引入进程阻塞机制在信号量里增加对阻塞进程的记录在信号量里增加对阻塞进程的记录typedef struct Semaphoretypedef struct Semaphoreint value;int value;process_list process_list * * list; list; semaphore ; semaphore ;资源个数资源个数阻塞进程（阻塞进程（PCBPCB）队列）队列2 2、记录型信号量机制、记录型信号量机制Lifang 201512Operating SystemP( s )s.v

7、alue = 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 201513Operating SystemProcedure wait(s) var S: semaphore; begin S.value:=s.value-1;

8、if S.value0 then block(S,L); end;Procedure signal(s) Var S:semaphore; Begin S.value:=S.value+1;If S.value=0 then wakeup(S.L); End;伪码描述伪码描述当当s.values.value初值为初值为1 1时，转化为互斥信号量时，转化为互斥信号量Lifang 201514Operating System3 3、信号量集、信号量集信号量集信号量集用于进程需要多个资源时的信号量操作；用于进程需要多个资源时的信号量操作；n整型信号量机制和记录型信号量机制都是针对进程间要共享整型信号

9、量机制和记录型信号量机制都是针对进程间要共享一个一个临界资源而言的；临界资源而言的；n当一段处理代码需要同时获取两个或多个临界资源时，使用当一段处理代码需要同时获取两个或多个临界资源时，使用整型或记录型信号量，整型或记录型信号量，会产生会产生各进程分别获得部分临界资源，各进程分别获得部分临界资源，然后等待其余的临界资源，然后等待其余的临界资源，“各不相让各不相让”的问题的问题-死锁。死锁。如：如：A,BA,B进程都要访问共享资源进程都要访问共享资源D,E. D,E. Lifang 201515Operating System1) AND1) AND型信号量集机制型信号量集机制 将一段代码同时需

10、要的多个临界资源，采用原子将一段代码同时需要的多个临界资源，采用原子方式，要么全分配给它，要么一个都不分配。称为方式，要么全分配给它，要么一个都不分配。称为SwaitSwait(Simultaneous Wait)(Simultaneous Wait)。同样地，使用结束后一。同样地，使用结束后一起释放，称为起释放，称为SsignalSsignal; ;基本思想：基本思想：Lifang 201516Operating SystemSwait(Simultaneous Wait)Swait(Simultaneous Wait) Swait(S1, S2, , Sn)/P原语；原语； if (S1

11、1 and S2 1 Sn 1) /满足资源要求时的处理；满足资源要求时的处理； for (i = 1; i = n; +i) Si=Sj-1;/注：与注：与wait的处理不同，这里是在确信可满足的处理不同，这里是在确信可满足/资源要求时，才进行减资源要求时，才进行减1操作操作 else /某些资源不够时的处理；某些资源不够时的处理； 调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue ,阻阻塞调用进程塞调用进程; /次序并不重要次序并不重要，虽然会影响进，虽然会影响进程归入哪个阻塞队列，但由于是程归入哪个阻塞队列，但由于是对资源全分配或不分配，所以

12、总对资源全分配或不分配，所以总有进程获得全部资源并在推进之有进程获得全部资源并在推进之后释放资源，后释放资源，因此不会死锁因此不会死锁Lifang 201517Operating System Ssignal(S1, S2, Ssignal(S1, S2, , Sn), Sn) for (i = 1; i = n; +i) for (i = 1; i =1S=1时，可以通过测试，允许多个进程进入某特定区；时，可以通过测试，允许多个进程进入某特定区；当当S=0S=0时，无法通过测试，禁止任何进程进入某特定区；时，无法通过测试，禁止任何进程进入某特定区；一般信号量集的基本思想一般信号量集的基本思想

13、：在：在ANDAND型信号量集的基础上进行扩充型信号量集的基础上进行扩充, ,扩充为扩充为进程需要申请多个资源，每个资源可能申请多个的情况，进程需要申请多个资源，每个资源可能申请多个的情况，每个资源对应一个每个资源对应一个信号量信号量SiSi： 进程对资源进程对资源i i的的需求值为需求值为di:di:每次申请或释放每次申请或释放didi个个，Si=Si-diSi=Si-di和和Si=Si+diSi=Si+di 资源资源i i的的测试值为测试值为ti:ti:当资源个数小于当资源个数小于titi时，便不再分配时，便不再分配PVPV原子操作：原子操作： Swait(S1, t1, d1; .; S

14、n, tn, dn);Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1; .; Sn, dn); Ssignal(S1, d1; .; Sn, dn);Lifang 201519Operating System多个进程共享一个临界资源多个进程共享一个临界资源And型信号量集机制：型信号量集机制： 同时需要多种资同时需要多种资源且每种占用一个时的信号量操作；源且每种占用一个时的信号量操作；一般信号量集机制：一般信号量集机制：同时需要多种资源同时需要多种资源、每每种占用的数目不同、且可分配的资源还存在种占用的数目不同、且可分配的资源还存在一个临界值时

15、的处理；一个临界值时的处理；信号量信号量整型信号量机制整型信号量机制记录型信号量机制记录型信号量机制信号量集机制信号量集机制Lifang 201520Operating System2.3.3 2.3.3 经典进程同步问题经典进程同步问题 P60P60生产者消费者问题生产者消费者问题(producer-consumer problem)(producer-consumer problem)问题描述：若干进程通过问题描述：若干进程通过有限的共享缓冲区有限的共享缓冲区交换数据。其中，交换数据。其中，“生产者生产者”进程不断写入，而进程不断写入，而“消费者消费者”进程不断读出；共进程不断读出；共享缓

16、冲区共有享缓冲区共有N N个个；任何时刻只能有一个进程任何时刻只能有一个进程. .可对共享缓冲可对共享缓冲区进行操作。区进行操作。消费者消费者生产者生产者共享缓冲区共享缓冲区放产品放产品取产品取产品一次只可放一个产品一次只可放一个产品Lifang 201521Operating System生产者生产者-消费者同步的关键问题消费者同步的关键问题 需要保证以下同步关系：需要保证以下同步关系：1.1.多个进程互斥地访问公共缓冲区；多个进程互斥地访问公共缓冲区；2.2.不能向满的缓冲区中添加产品；不能向满的缓冲区中添加产品；3.3.不能从空的缓冲区中提取产品。不能从空的缓冲区中提取产品。互斥信号量互

17、斥信号量 mutex可用的空资源信号量可用的空资源信号量 empty可用的满资源信号量可用的满资源信号量 fullfull + empty=Nfull + empty=N涉及两类进程：涉及两类进程：生产者进程和消费者进程生产者进程和消费者进程Lifang 201522Operating Systemn每个进程中各个每个进程中各个waitwait操作的次序是重要的：先检查资源数目，再操作的次序是重要的：先检查资源数目，再检查是否互斥检查是否互斥. .思考：否则会怎样思考：否则会怎样( (? ?) )n采用采用ANDAND信号量集：信号量集：Swait(empty, mutex)Swait(emp

18、ty, mutex)；| Swait(full,mutex)| Swait(full,mutex)； Ssignal(mutex,full)Ssignal(mutex,full)；| Ssignal(mutex,empty);| Ssignal(mutex,empty);ProducerWait(empty);Wait(mutex); /进入区进入区One unit buffer;Signal(mutex);Signal(full); /退出区退出区ConsumerWait(full);Wait(mutex); /进入区进入区One unit buffer;Signal(mutex);Sign

19、al(empty); /退出区退出区var var mutex,full,emptymutex,full,empty:semaphore:=:semaphore:=1,n,01,n,0采用记录型信号量机制解决该同步问题采用记录型信号量机制解决该同步问题Lifang 201523Operating System类类C C伪代码描述伪代码描述semaphore full=0； /满缓冲区单元个数semaphore empty=n； /空缓冲区单元个数semaphore mutex=1； /互斥信号量：控制对临界资源的访问char buffern; /说明其他类型变量int in=0;int out

20、=0;char nextc,nextp;void main() cobegin /进程并发执行 producer(); consumer(); coendLifang 201524Operating System类类C C伪代码描述伪代码描述void producer() /生产者进程 while (1) produce an item nextp; /生产一个数据 wait(empty); /空缓冲区数量减1 wait(mutex); /进入临界区 bufferin=nextp; /将一个数据送入缓冲池 in=(in+1) mod n; /修改in指针 signal(mutex); /退出临

21、界区 signal(full); /满缓冲区数量增1 void consumer() /消费者进程 while (1) wait(full); /满缓冲区数量减1 wait(mutex); /进入临界区 nextc=bufferout; /从缓冲区读出一个数据 out=(out+1) mod n; /修改out指针 signal(mutex); /退出临界区 signal(empty); /空缓冲区数量增1 consume the item in nextc; /消费一个数据 Lifang 201525Operating System2. 2. 读者写者问题读者写者问题 (readers-wr

22、iters problem)(readers-writers problem)问题描述：问题描述： 一个数据对象（数据文件或记录），可以被多个进程共享。一个数据对象（数据文件或记录），可以被多个进程共享。其中有些进程要读，有些要写或修改。其中有些进程要读，有些要写或修改。 允许多个读者进程同时读一个共享对象，但不允许一个写者允许多个读者进程同时读一个共享对象，但不允许一个写者进程和其它读者或写者进程同时访问共享对象。进程和其它读者或写者进程同时访问共享对象。该同步问题涉及两类进程：该同步问题涉及两类进程：读者（读者（reader)reader)进程和写者进程和写者(writer)(writer

23、)进程。进程。并且，这两个进程的同步问题就是指并且，这两个进程的同步问题就是指: :保证保证“读写读写”互斥，互斥， “写写写写”互斥，互斥， “读读读读”允许的问题。允许的问题。Lifang 201526Operating SystemWmutexWmutex：互斥信号量：互斥信号量：表示表示“允许写允许写”，初值是，初值是1 1。A.A.采用记录型信号量机制采用记录型信号量机制Wait(Wmutex);Write;Signal(Wmutex);writerwait(Rmutex);if(Readcount=0) wait(wmutex)Readcount=Readcount+1;Signa

24、l(Rmutex); /关闭写的同时允许读（无上限）关闭写的同时允许读（无上限）read;Wait(Rmutex); Readcount:=Readcount-1; if Readcount=0 then signal(Wmutex);Signal(Rmutex); /适当的时候打开写适当的时候打开写readerif(Readcount=0) if(Readcount=0) wait(wmutex)wait(wmutex)Readcount=Readcount+1;Readcount=Readcount+1; Readcount:=Readcount-1;Readcount:=Readcoun

25、t-1; if Readcount=0 if Readcount=0 then then signal(Wmutex);signal(Wmutex);Rmutex:Rmutex:互斥信号量：互斥信号量：表示对表示对ReadcountReadcount的互斥操作，初值是的互斥操作，初值是1 1。公共变量公共变量ReadcountReadcount表示表示“正在读正在读”的进程数，初值是的进程数，初值是0 0；Lifang 201527Operating SystemWriterWriterSwait(mx,1,1;L,RN,0);Swait(mx,1,1;L,RN,0);Write;Write;

26、Ssignal(mx,1)Ssignal(mx,1)ReaderReaderSwait(L,1,1;mx,1,0)Swait(L,1,1;mx,1,0)；Read;Read;Ssignal(L,1)Ssignal(L,1)采用一般采用一般“信号量集信号量集”机制：增加一个限制条件机制：增加一个限制条件: :同时读的同时读的 读者读者 最多最多R R个个Fmxmx表示表示 允许写允许写 ，初值是，初值是1 1FL L表示当前表示当前 允许读者数目允许读者数目 ，初值为，初值为RNRNB.B.采用一般信号量集机制采用一般信号量集机制/保证多个读，有人写时不能读保证多个读，有人写时不能读（进入读的开

27、关）（进入读的开关）/有人读时不能写：有人读时不能写：（进入写的开关）（进入写的开关）/并与写互斥并与写互斥Lifang 201528Operating System3. 3. 哲学家进餐问题哲学家进餐问题(the dining philosophers problem)(the dining philosophers problem)（由（由DijkstraDijkstra首先提出并解决）首先提出并解决）问题描述：问题描述：5 5个哲学家个哲学家围绕一张围绕一张圆桌圆桌而坐，桌子上放而坐，桌子上放着着5 5支筷子支筷子，每两个哲学家之间放一支；，每两个哲学家之间放一支；哲学家的动作包括哲学家

28、的动作包括思考思考和和进餐进餐，进餐时进餐时需要同时拿起他左边和右边的两支筷子需要同时拿起他左边和右边的两支筷子，思考时思考时则同时将两支筷子放回原处。则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如何保证哲学家们的动作有序进行？如：不出现相邻者同时进餐的冲突情况如：不出现相邻者同时进餐的冲突情况. .进餐不能进餐进餐Lifang 201529Operating System问题分析问题分析临界资源：筷子临界资源：筷子为临界资源设置信号量：为临界资源设置信号量：var chopstick:array0var chopstick:array04 of semaphore; 4 of

29、semaphore; 初值均为初值均为1 1。0123412340则第则第i个哲学家的动作可描述为：个哲学家的动作可描述为：wait(chopsticki);wait(chopsticki+1 mod 5);eat;signal(chopsticki);signal(chopsticki+1 mod 5);think;死锁死锁不能进餐！不能进餐！不能进餐！不能进餐！不能进餐！可以保证不会有两个相邻的哲学家同时进餐；但会引起死锁可以保证不会有两个相邻的哲学家同时进餐；但会引起死锁Lifang 201531Operating System死锁问题的几种解决方法死锁问题的几种解决方法 P62P6201234012341 1）最多只允许四个哲学家同时进餐，以保证至少一个哲学家能够进餐）最多只允许四个哲学家同时进餐，以保证至少一个哲学家能够进餐，最终释放出他所使用过的筷子，从而使得更多的哲学家进餐。，最终释放出他所使用过的筷子，从而使得更多的哲学家进餐。2 2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。3 3）规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；）规定奇数号哲学家先拿他左