信号量与PV操作课件.ppt

《信号量与PV操作课件.ppt》由会员分享，可在线阅读，更多相关《信号量与PV操作课件.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信号量与PV操作课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望3.3.1 同步和同步机制v著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。v在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。v解决好生产者-消费者问题就解决好了一类并发进程的同步问题。生产者-消费者问题表述 有界缓冲问题v有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并

2、发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。生产者-消费者问题算法描述(1)vint k;vtypedef anyitem item;/item类型vitem bufferk;vint in=0,out=0,counter=0;生产者-消费者问题算法描述(2)vprocess producer(void)vwhile(true)/无限循环vproduce an item in nextp;/生产一个产品vif(counter=k)/缓冲满时，生产者睡眠v sleep(producer);vbufferin=nextp;/

3、将一个产品放入缓冲区vin=(in+1)%k;/指针推进vcounter+;/缓冲内产品数加1vif(counter=1)/缓冲为空，加进一件产品v wakeup(consumer);/并唤醒消费者vv 生产者-消费者问题算法描述(3)vprocess consumer(void)vwhile(true)/无限循环vif(counter=0)/缓冲区空，消费者睡眠v sleep(consumer);v nextc=bufferout;/取一个产品到nextcv out=(out+1)%k;/指针推进v counter-;/取走一个产品，计数减1vif(counter=k-1)/缓冲满了，取走一

4、件产品并唤v wakeup(producer);/醒生产者vconsume the item in nextc;/消耗产品vv 生产者-消费者问题的算法描述(4)v生产者和消费者进程对counter的交替执行会使其结果不唯一 v生产者和消费者进程的交替执行会导致进程永远等待竞争条件(Race Condition)vcounter+could be implemented as register1=counter register1=register1+1 count=register1vcounter-could be implemented as register2=counter regi

5、ster2=register2-1 counter=register2vConsider this execution interleaving with“counter=5”initially:S0:producer execute register1=counter register1=5S1:producer execute register1=register1+1 register1=6S2:consumer execute register2=counter register2=5 S3:consumer execute register2=register2-1 register

6、2=4S4:producer execute counter=register1 counter=6 S5:consumer execute counter=register2 counter=4生产者-消费者问题算法描述(3)vprocess consumer(void)vwhile(true)/无限循环vif(counter=0)/缓冲区空，消费者睡眠v sleep(consumer);v nextc=bufferout;/取一个产品到nextcv out=(out+1)%k;/指针推进v counter-;/取走一个产品，计数减1vif(counter=k-1)/缓冲满了，取走一件产品并

7、唤醒生产者v wakeup(producer);vconsume the item in nextc;/消耗产品vv 生产者-消费者问题算法描述(2)vprocess producer(void)vwhile(true)/无限循环vproduce an item in nextp;/生产一个产品vif(counter=k)/缓冲满时，生产者睡眠v sleep(producer);vbufferin=nextp;/将一个产品放入缓冲区vin=(in+1)%k;/指针推进vcounter+;/缓冲内产品数加1vif(counter=1)/缓冲为空，加进一件产品v wakeup(consumer);

8、/并唤醒消费者vv 3.3.2信号量与PV操作(1)v前节种种方法解决临界区调度问题的缺点:1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。v1965年E.W.Dijkstra提出新的同步工具-信号量和P、V操作。信号量与PV操作(2)v信号量：一种软件资源v原语：内核中执行时不可被中断的过程vP操作原语和V操作原语v一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。信号量与PV

9、操作(3)v操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。v实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。信号量的值(-2)信号量队列指针信号量分类信号量按其用途分为 公用信号量：私有信号量：信号量按其取值分为 二元信号量：一般信号量：一般信号量(1)设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue,P和V操作原语定义：v P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。v V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。一般

10、信号量(2)vtypedef struct semaphore vint value;/信号量值vstruct pcb*list;/信号量队列指针v;vvoid P(semaphore&s)v s.value-;v if(s.value0)v W(s.list);v vvoid V(semaphore&s)vs.value+;v if(s.value=0)v R(s.list);v 一般信号量(3)v推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数v推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的

11、进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数v推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作二元信号量(1)v设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue,把二元信号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：二元信号量(2)v typedef struct binary_semaphore v int value;/value取值0 or 1v struct pcb*list;vvoid BP(b

12、inary_semaphore&s)vif(s.value=1)v s.value=0;velsev W(s.list);vvvoid BV(binary_semaphore&s)vif(s.list is empty()v s.value=1;velsev R(s.list);v3.3.3信号量实现互斥v semaphore mutex;v mutex=1;v cobeginv process Pi()/i=1,nv P(mutex);v 临界区;v V(mutex);v v coend信号量解决五个哲学家吃通心面问题(1)有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于

13、，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 信号量解决五个哲学家吃通心面问题(2)哲学家吃通心面问问题题(3)(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();V(forki);V(fork(i+1)%5);coend有若干种办法可避免这类死锁 上述解法可能出现永远等待，有若 干种办

14、法可避免死锁：至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的叉子；每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。哲学家吃通心面问问题题的的一一种种正正确确解解 semaphore fork5;for(int i=0;i5;i+)forki=1;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)；coend3.3.5信号量解决生产

15、者消费者问题一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区一个生产者、一个消费者共享一个缓冲区的解解vint B;vsemaphore empty;/可以使用的空缓冲区数vsemaphore full;/缓冲区内可以使用的产品数vempty=1;/缓冲区内允许放入一件产品vfull=0;/缓冲区内没有产品vcobeginvprocess producer()process consumer()v while(true)while(true)vproduce();P(full);vP(empty);take()from B;vappe

16、nd()to B;V(empty);vV(full);consume();v v coend多个生产者/消费者、共享多个缓冲区的解解vitem Bk;item Bk;vsemaphore empty;semaphore empty;empty=k;/empty=k;/可以使用的空缓冲区数可以使用的空缓冲区数vsemaphore full;full=0;/semaphore full;full=0;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数vsemaphore mutex;semaphore mutex;mutex=1;/mutex=1;/互斥信号量互斥信号量vint in=0;int

17、in=0;/放入缓冲区指针放入缓冲区指针vint out=0;/int out=0;/取出缓冲区指针取出缓冲区指针 vcobegincobeginvprocess producer_i()process consumer_j()process producer_i()process consumer_j()v while(true)while(true)v produce();P(full);v P(empty);P(mutex);v P(mutex);take()from Bout;v append to Bin;out=(out+1)%k;v in=(in+1)%k;V(mutex);v

18、V(mutex);V(empty);v V(full);consume();v v vcoendcoendv3.3.6 信号量解决读者-写者问题(1)有两组并发进程：读者和写者，共享一个文件F，要求：v允许多个读者同时执行读操作v任一写者在完成写操作之前不允许其它读者或写者工作v写者执行写操作前，应让已有的写者和读者全部退出信号量解决读者写者问题(2)vint readcount=0;/读进程计数vsemaphore writeblock,mutex;vwriteblock=1;mutex=1;信号量解决读者写者问题(3)vcobegincobeginvprocess reader_i()pr

19、ocess writer_j()process reader_i()process writer_j()v P(mutex);P(writeblock);P(mutex);P(writeblock);v readcount+;readcount+;写文件写文件;v if(readcount=1)V(writeblock);if(readcount=1)V(writeblock);v P(writeblock);P(writeblock);v v V(mutex);V(mutex);v 读文件读文件;v P(mutex);P(mutex);vreadcount-;readcount-;vif(r

20、eadcount=0)if(readcount=0)v V(writeblock);V(writeblock);vV(mutex);V(mutex);v vCoend信号量解决读者写者问题(3)vcobeginvprocess reader_i()process writer_j()v P(mutex);P(writeblock);v readcount+;写文件;v if(readcount=1)V(writeblock);v P(writeblock);v V(mutex);v读文件;v P(mutex);v readcount-;v if(readcount=0)v V(writeblo

21、ck);v V(mutex);vvcoend信号量解决读者写者问题(3)vcobeginvprocess reader_i()process writer_j()v P(mutex);P(writeblock);v readcount+;写文件;v if(readcount=1)V(writeblock);v P(writeblock);v V(mutex);v读文件;v P(mutex);v readcount-;v if(readcount=0)v V(writeblock);v V(mutex);vvcoend3.3.7信号量解决理发师问题(1)v理发店理有一位理发师、一把理发椅和n把供

22、等候理发的顾客坐的椅子v如果没有顾客，理发师便在理发椅上睡觉v一个顾客到来时，它必须叫醒理发师v如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开信号量解决理发师问题(2)vint waiting=0;/等候理发顾客坐的椅子数vint CHAIRS=N;/为顾客准备的椅子数vsemaphore customers,barbers,mutex;vcustomers=0;barbers=0;mutex=1;信号量解决理发师问题(3)vcobeginvprocess barber()v while(true)vP(customers);/有顾客吗？若无顾客，理发师睡眠vP

23、(mutex);/若有顾客时，进入临界区vwaiting-;/等候顾客数少一个v V(barbers);/理发师准备为顾客理发vV(mutex);/退出临界区vcut_hair();/理发师正在理发(非临界区)vvvprocess customer_i()v P(mutex);/进入临界区v if(waitingCHAIRS)/有空椅子吗vwaiting+;/等候顾客数加1vV(customers);/唤醒理发师vV(mutex);/退出临界区vP(barbers);/理发师忙，顾客坐下等待vget_haircut();/否则顾客坐下理发v velsevV(mutex);/人满了，走吧！vvC

24、oend信号量解决理发师问题(3)vcobeginvprocess barber()vwhile(true)v P(customers);/有顾客吗？若无顾客，理发师睡眠v P(mutex);/若有顾客时，进入临界区v waiting-;/等候顾客数少一个v V(barbers);/理发师准备为顾客理发v V(mutex);/退出临界区v cut_hair();/理发师正在理发(非临界区)vv信号量解决理发师问题(3)vprocess customer_i()v P(mutex);/进入临界区v if(waitingCHAIRS)/有空椅子吗v waiting+;/等候顾客数加1v V(customers);/唤醒理发师v V(mutex);/退出临界区v P(barbers);/理发师忙，顾客坐下等待v get_haircut();/否则顾客坐下理发v velsev V(mutex);/人满了，走吧！vvcoend