信号量与PV操作

1、操操作作系系统统3.3 信号量与PV操作3.3.1同步与同步机制同步与同步机制3.3.2信号量与信号量与PV操作操作3.3.3信号量实现互斥信号量实现互斥3.3.4信号量解决五个哲学家就餐问题信号量解决五个哲学家就餐问题3.3.5信号量解决生产者信号量解决生产者-消费者问题消费者问题3.3.6信号量解决读者信号量解决读者-写者问题写者问题3.3.7信号量解决理发师问题信号量解决理发师问题1操操作作系系统统3.3.1 同步和同步机制著名的生产者著名的生产者-消费者问题（消费者问题（Producer-consumer Problem)是计算机操作系统中并发进程内在关系是计算机操作系统中并发进程内在

2、关系的一种抽象，是典型的进程同步问题。的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进送进程；而消费者进程可以是打印进程、接收进程等等。程等等。解决好生产者解决好生产者-消费者问题就解决好了一类并发消费者问题就解决好了一类并发进程的同步问题。进程的同步问题。2操操作作系系统统生产者-消费者问题表述 有界缓冲问题有界缓冲问题有有n个生产者和个生产者和m个消费者，连接在一个有个消费者，连接在一个有k个个单位缓冲区的有界缓冲上。其中，单位缓冲区的有界缓冲上。其中，pi和和cj都是并都是并发

3、进程，只要缓冲区未满，生产者发进程，只要缓冲区未满，生产者pi生产的产生产的产品就可投入缓冲区；只要缓冲区不空，消费者品就可投入缓冲区；只要缓冲区不空，消费者进程进程cj就可从缓冲区取走并消耗产品。就可从缓冲区取走并消耗产品。3操操作作系系统统生产者-消费者问题算法描述(1)int k;typedef anyitem item; /item类型类型item bufferk;int in=0,out=0,counter=0;4操操作作系系统统生产者-消费者问题算法描述(2)process producer(void) while (true) /无限循环无限循环produce an item i

4、n nextp;/生产一个产品生产一个产品if (counter=k) /缓冲满时，生产者睡眠缓冲满时，生产者睡眠 sleep(producer);bufferin=nextp;/将一个产品放入缓冲区将一个产品放入缓冲区in=(in+1)%k; /指针推进指针推进counter+; /缓冲内产品数加缓冲内产品数加1if(counter=1) /缓冲为空，加进一件产品缓冲为空，加进一件产品 wakeup(consumer);/并唤醒消费者并唤醒消费者 5操操作作系系统统生产者-消费者问题算法描述(3)process consumer(void) while (true) /无限循环无限循环if

5、(counter=0) /缓冲区空，消费者睡眠缓冲区空，消费者睡眠 sleep(consumer); nextc=bufferout;/取一个产品到取一个产品到nextc out=(out+1)%k; /指针推进指针推进 counter-; /取走一个产品，计数减取走一个产品，计数减1if(counter=k-1) /缓冲满了，取走一件产品并唤缓冲满了，取走一件产品并唤 wakeup(producer); /醒生产者醒生产者consume the item in nextc;/消耗产品消耗产品 6操操作作系系统统生产者-消费者问题的算法描述(4)生产者和消费者进程对生产者和消费者进程对coun

6、ter的交的交替执行会使其结果不唯一替执行会使其结果不唯一 生产者和消费者进程的交替执行生产者和消费者进程的交替执行会导致进程永远等待会导致进程永远等待7操操作作系系统统3.3.2信号量与PV操作(1)前节种种方法解决临界区调度问题的前节种种方法解决临界区调度问题的缺点缺点: 1)对不能进入临界区的进程，采用忙式等待测试法，对不能进入临界区的进程，采用忙式等待测试法，浪费浪费CPU时间。时间。 2)将测试能否进入临界区的责任推给各个竞争的进将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。程会削弱系统的可靠性，加重了用户编程负担。1965年年E.W.Dijks

7、tra提出新的同步工具提出新的同步工具-信号量和信号量和P、V操作。操作。 8操操作作系系统统信号量与PV操作(2)信号量：一种软件资源信号量：一种软件资源原语：内核中执行时不可被中断的过程原语：内核中执行时不可被中断的过程P操作原语和操作原语和V操作原语操作原语一个进程在某一特殊点上被迫停止执行直到接收一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是到一个对应的特殊变量值，这种特殊变量就是信信号量号量(semaphore)，复杂的进程合作需求都可以通过，复杂的进程合作需求都可以通过适当的信号结构得到满足。适当的信号结构得到满足。信号量的值只能通过信号量的值只

8、能通过P、V操作改变。操作改变。9操操作作系系统统信号量与PV操作(3)操作系统中，信号量表示操作系统中，信号量表示物理资源物理资源的实体，它是的实体，它是一个与队列有关的整型变量。一个与队列有关的整型变量。实现时，信号量是一种实现时，信号量是一种记录型记录型数据结构，有两个数据结构，有两个分量：一个是信号量的分量：一个是信号量的值值，另一个是信号量队列，另一个是信号量队列的的队列指针队列指针。信号量的值信号量的值(-2)(-2) 信号量队列指针信号量队列指针10操操作作系系统统信号量分类信号量按其用途分为：信号量按其用途分为：公用信号量公用信号量：联系一组并发进程，：联系一组并发进程，相关的

9、进程相关的进程均可在此信均可在此信号量上执行号量上执行P、V操作，初值通常为操作，初值通常为1，用于实现互斥；用于实现互斥；私有信号量私有信号量：联系一组并发进程，仅允许此信号量的：联系一组并发进程，仅允许此信号量的拥有拥有进程进程执行执行P操作，而操作，而其它其它相关进程执行相关进程执行V操作，初值往往为操作，初值往往为0或正整数，常用于实现同步；或正整数，常用于实现同步；信号量按其取值分为信号量按其取值分为： 二元信号量二元信号量：值仅取：值仅取0和和1，主要用于实现主要用于实现互斥互斥 一般信号量一般信号量：计数信号量，主要用于实现：计数信号量，主要用于实现同步同步11操操作作系系统统一

10、般信号量(1)设设s为一个记录型数据结构为一个记录型数据结构,一个分量为整形一个分量为整形量量value，另一个为信号量队列另一个为信号量队列queue，P和和V操作操作原语定义：原语定义： P(s)：将信号量：将信号量s减去减去l，若结果小于，若结果小于0，则，则调用调用P(s)的进程被置成的进程被置成等待等待信号量信号量s的状态。的状态。 V(s)：将信号量：将信号量s加加1，若结果不大于，若结果不大于0，则，则释放释放一个等待信号量一个等待信号量s的进程。的进程。12操操作作系系统统一般信号量(2)typedef struct semaphore int value; /信号量值信号量值

11、struct pcb *list; /信号量队列指针信号量队列指针 ; void P(semaphore &s) s.value-; if(s.value0) sleep(s.list); void V(semaphore &s) s.value+; if(s.value=0) wakeup(s.list); 13操操作作系系统统一般信号量(3)推论推论1：若信号量：若信号量s为为正值正值，则该值等于在封锁进程之前对信，则该值等于在封锁进程之前对信号量号量s可施行的可施行的P操作数，亦等于操作数，亦等于s所代表的实际还可以使用所代表的实际还可以使用的的物理资源数物理资源数推论推

12、论2：若信号量：若信号量s为为负值负值，则其，则其绝对值绝对值等于登记排列在该信等于登记排列在该信号量号量s队列之中等待的进程个数，亦即恰好等于对信号量队列之中等待的进程个数，亦即恰好等于对信号量s实实施施P操作而被封锁起来并进入信号量操作而被封锁起来并进入信号量s队列的队列的进程数进程数推论推论3：通常，：通常，P操作意味着请求一个资源，操作意味着请求一个资源，V操作意味着释操作意味着释放一个资源。在一定条件下，放一个资源。在一定条件下，P操作代表挂起进程操作，而操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作操作代表唤醒被挂起进程的操作14操操作作系系统统二元信号量(1)设设s为一个

13、记录型数据结构为一个记录型数据结构，一个分量为一个分量为value，它它仅能取值仅能取值0和和1，另一个分量为信号量队列另一个分量为信号量队列queue， 把二元信号量上的把二元信号量上的P、V操作记为操作记为BP和和BV，BP和和BV操作原语的定义如下：操作原语的定义如下：15操操作作系系统统二元信号量(2) typedef struct binary_semaphore int value; /value取值取值0 or 1 struct pcb *list; ;void BP(binary_semaphore &s) if(s.value=1) s.value=0;else sl

14、eep (s.list);void BV(binary_semaphore &s) if(s.list is empty( ) s.value=1;else wakeup(s.list);16操操作作系系统统3.3.3信号量实现互斥semaphore mutex; mutex=1; cobegin process Pi( ) /i=1,n P(mutex); 临界区临界区; V(mutex); coend17操操作作系系统统信号量解决哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。

15、每个哲学每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子获得两把叉子，且每人只能直接从自己左边或右边去取叉子 18操操作作系系统统哲学家就餐问题(3)semaphore fork5;for (int i=0;i5;i+) forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(forki); P(fork(i+1)%5); eat( );

16、V(forki); V(fork(i+1)%5); coend19操操作作系系统统有若干种办法可避免这类死锁上述解法可能出现上述解法可能出现永远等待永远等待，有若干种办法可避，有若干种办法可避免死锁：免死锁：至多允许四个哲学家同时吃；至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的奇数号先取左手边的叉子，偶数号先取右手边的叉子叉子；每个哲学家取到手边的两把叉子才吃，否则一把每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。叉子也不取。20操操作作系系统统哲学家就餐问题的一种正确解 semaphore fork5;for (int i=0;i5;i+) forki= 1;

17、cobeginprocess philosopher_i( )/*i=0,1,2,3 */ while(true) think( )；P(forki； /*i=4,P(fork0)*/P(fork(i+1)%5 )；/*i=4,P(fork4)*/eat( )；V(forki)；V(fork(i+ 1 % 5)； coend21操操作作系系统统3.3.5信号量解决生产者消费者问题一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区2

18、2操操作作系系统统一个生产者、一个消费者共享一个缓冲区的解int B;semaphore empty; /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数empty=1; /缓冲区内允许放入一件产品缓冲区内允许放入一件产品full=0; /缓冲区内没有产品缓冲区内没有产品cobeginprocess producer() while(true) produce( ); P(empty); append( ) to B; V(full); coend23process consumer() while(true) P(fu

19、ll);take( ) from B;V(empty);consume( ); 操操作作系系统统一个生产者、一个消费者共享多个缓冲区item Bk;semaphore empty; empty=k; /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; full=0; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数int in=0; /放入缓冲区指针放入缓冲区指针int out=0; /取出缓冲区指针取出缓冲区指针 cobeginprocess producer ( ) while(true) produce( ); P(empty); append to Bin; i

20、n=(in+1)%k; V(full); coend 24process consumer ( ) while(true) P(full); take( ) from Bout; out=(out+1)%k; V(empty); consume( ); 操操作作系系统统多个生产者/消费者、共享多个缓冲区的解item Bk;semaphore empty; empty=k; /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; full=0; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数semaphore mutex; mutex=1; /互斥信号量互斥信号量int i

21、n=0; /放入缓冲区指针放入缓冲区指针int out=0; /取出缓冲区指针取出缓冲区指针 cobeginprocess producer_i ( ) while(true) produce( ); P(empty); P(mutex); append to Bin; in=(in+1)%k; V(mutex); V(full); coend 25process consumer_j ( ) while(true) P(full); P(mutex); take( ) from Bout; out=(out+1)%k; V(mutex); V(empty); consume( ); 操操作作

22、系系统统3.3.6 信号量解决读者-写者问题(1) 有两组并发进程：读者和写者，共享有两组并发进程：读者和写者，共享一个文件一个文件F F，要求：，要求：允许多个读者同时执行读操作允许多个读者同时执行读操作任一写者在完成写操作之前不允许其它读者或写任一写者在完成写操作之前不允许其它读者或写者工作者工作写者执行写操作前，应让已有的写者和读者全部写者执行写操作前，应让已有的写者和读者全部退出退出26操操作作系系统统信号量解决读者写者问题(2)int readcount=0;/读进程计数读进程计数semaphore writeblock,mutex;writeblock=1;mutex=1;cobe

23、ginprocess reader_i( ) P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex);读文件读文件; P(mutex);readcount-; if(readcount=0) V(writeblock);V(mutex);coend27process writer_j( ) P(writeblock); 写文件写文件; V(writeblock);操操作作系系统统3.3.7信号量解决理发师问题(1)理发店理有一位理发师、一把理发椅和理发店理有一位理发师、一把理发椅和n把供等候把供等候理发的顾客坐的椅子理发的顾客

24、坐的椅子如果没有顾客，理发师便在理发椅上睡觉如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开椅子可坐，就坐下来等待，否则就离开28操操作作系系统统29信号量解决理发师问题(2)我走了，谁爱来谁来！操操作作系系统统信号量解决理发师问题(3)int waiting=0;/等候理发顾客坐的椅子数等候理发顾客坐的椅子数int CHAIRS=N; /为顾客准备的椅子数为顾客准备的椅子数semaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;cobeginprocess barber( ) while(true) P(customers); /有顾客吗？若无顾客，理发师睡眠有顾客吗？若无顾客，理发师睡眠P(mutex); /若有顾客时，进入临界区若有顾客时，进入临界区waiting-; /等候顾客数少一个等候顾客数少一个 V(ba