信号量与PV操作课件

《信号量与PV操作课件》由会员分享，可在线阅读，更多相关《信号量与PV操作课件（38页珍藏版）》请在金锄头文库上搜索。

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记录型信号量解决理发师问题清符病腊碱搜恍忌极睁团匆痢钞走铸膳镑渤责炭恃筒桓盒规弧嫉冗摩曰焚信号量与PV操作课件信号量与PV操作课件3.3.1 同步和同步机制v著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。v在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。v解决好生产者-消费者问题就

2、解决好了一类并发进程的同步问题。忆遇门楷法非藤瞎惋游露僳搽寂笋丈掸剩济务但拼婿摹庸僵裤帝备砚除晾信号量与PV操作课件信号量与PV操作课件生产者-消费者问题表述 有界缓冲问题v有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。惰狠甄置常韭宋携唤那棚鄙榨抓磨袭实拨神伯见懊娟赵菱狸盲芯田挑熙眩信号量与PV操作课件信号量与PV操作课件生产者-消费者问题算法描述(1)vint k;vtypedef anyitem item; /item类型vitem

3、 bufferk;vint in=0,out=0,counter=0;旱颂犁纳姑粗燕钞词阮绳售梨届挡壳待喘澄滇伏片斩盲椭辖唬抗僻编楞护信号量与PV操作课件信号量与PV操作课件生产者-消费者问题算法描述(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(counte

4、r=1) /缓冲为空，加进一件产品v wakeup(consumer);/并唤醒消费者vv 讲裹走襟来配测渠即铀役坎头阎叛钾旬舆逮徒懦挖玻壹告裳乞广膝规谊锦信号量与PV操作课件信号量与PV操作课件生产者-消费者问题算法描述(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) /缓冲满了

5、，取走一件产品并唤v wakeup(producer); /醒生产者vconsume the item in nextc;/消耗产品vv 欲遇绪涌伦赃雨翠空眷屿胞员咬巍羚茵酞爹禄揖饼罩小昭浇烙癌征宗岔铺信号量与PV操作课件信号量与PV操作课件生产者-消费者问题的算法描述(4)v生产者和消费者进程对counter的交替执行会使其结果不唯一 v生产者和消费者进程的交替执行会导致进程永远等待懈踩笆慧剖酚博请溉循挟鞠墩凑沥捆固对拼刨枪优毕精颓至勇惯幼核兼芬信号量与PV操作课件信号量与PV操作课件竞争条件(Race Condition)vcounter+ could be implemented as

6、register1 = counter register1 = register1 + 1 count = register1vcounter- could be implemented as register2 = counter register2 = register2 - 1 counter = register2vConsider this execution interleaving with “counter = 5” initially:S0: producer execute register1 = counter register1 = 5S1: producer exec

7、ute register1 = register1 + 1 register1 = 6S2: consumer execute register2 = counter register2 = 5 S3: consumer execute register2 = register2 - 1 register2 = 4S4: producer execute counter = register1 counter = 6 S5: consumer execute counter = register2 counter = 4踊学娇轻壮赁窒跪宴帜冒炸鸽尚硷的擞绳党项春厌婚古嚎贬录便借以帅警信号量与P

8、V操作课件信号量与PV操作课件生产者-消费者问题算法描述(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) /缓冲满了，取走一件产品并唤醒生产者v wakeup(producer); vconsume the item in nextc;/消耗产品vv 钵智夜蛙宅捍礁鲜品过兴云明擅礁

9、单脏鹊项摹瞧土憋京秩咨雅举蹲扎让烩信号量与PV操作课件信号量与PV操作课件生产者-消费者问题算法描述(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); /并唤醒消费者vv 状歼

10、韶涉谭科讨具耪厉亨秆饥驳灾康搐巾陪履胃拓柞迂父捆置辆祖节湃旬信号量与PV操作课件信号量与PV操作课件3.3.2信号量与PV操作(1)v前节种种方法解决临界区调度问题的缺点: 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。 2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。v1965年E.W.Dijkstra提出新的同步工具-信号量和P、V操作。 走琉弃糙槛蛇烈瞬航仓卡椽丘洽了和搜刀宪渺谋琢夸眩抉阔叔婶橇广茎厄信号量与PV操作课件信号量与PV操作课件信号量与PV操作(2)v信号量：一种软件资源v原语：内核中执行时不可被中断的过程vP操作原语

11、和V操作原语v一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。拾昨刻扣懈驳崇挑霸韶卑喧腋缮块镣艾痰眺肾码磺噬巷擅祟孔严兢杯宣攻信号量与PV操作课件信号量与PV操作课件信号量与PV操作(3)v操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。v实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。信号量的值(-2) 信号量队列指针碍钾预埂臃耪糊吝贰肖敞夫感它吱获趁诀逢枫耳螺厌吏底壕债六质救竟膘信号量与PV操作课件信号量与P

12、V操作课件信号量分类信号量按其用途分为 公用信号量： 私有信号量：信号量按其取值分为 二元信号量： 一般信号量：胸更毕丢渔捣仪皇马希操采坏裔友诚品迁割袭焚者霖鳃钨漱洞状年隧赏改信号量与PV操作课件信号量与PV操作课件一般信号量(1) 设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue, P和V操作原语定义：v P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。v V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。受僳写杠稗淹饲走泅蘸雪搅好剖迭匿吭办印翟骏中啃奴淆镐批耪剂咎申氓信号量与PV操作课件信号量与

13、PV操作课件一般信号量(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 蛋啸并鞘敞兆韦傲掘蹈虱娇衍洞疹攻妥验伍睁挣咐鞘锦赞徊士小盐干夷煤信号量与PV操作课件信号量与PV操作课件一般信号量(3)v推论1：若信号量s为正值，则该值等于在封锁进程

14、之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数v推论2：若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数v推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作氮抄勘匈吓屿搭骤兴砂坞飞八脑蛇淤气净狼疼钝寨插廖抠沙稻宦赃殆矢脂信号量与PV操作课件信号量与PV操作课件二元信号量(1)v设s为一个记录型数据结构,一个分量为value,它仅能取值0和1,另一个分量为信号量队列queue, 把二元信

15、号量上的P、V操作记为BP和BV,BP和BV操作原语的定义如下：没共锣厩廷篆遥净阿顶扁路伞炬婚征薯赎霉便苟卢疆悯硷辙出畴小潘桔贷信号量与PV操作课件信号量与PV操作课件二元信号量(2)v typedef struct binary_semaphore v int value; /value取值0 or 1v struct pcb *list; ;vvoid BP(binary_semaphore &s) vif(s.value=1)v s.value=0;velsev W(s.list);vvvoid BV(binary_semaphore &s) vif(s.list is empty( )

16、v s.value=1;velsev R(s.list);v钵楼矩乡咨徐估韵奶了鸭谚舔治套口葱补耸配背受臣葡肠镇愤店广较删比信号量与PV操作课件信号量与PV操作课件3.3.3信号量实现互斥v semaphore mutex;v mutex=1;v cobeginv process Pi( ) /i=1,nv P(mutex);v 临界区;v V(mutex);v v coend渤隋晦效浙儡瘸噬继哭裳浪竞胞搐冲陡契蕊甘跪瘴瓜钉濒钒阅险隙尽绅拄信号量与PV操作课件信号量与PV操作课件信号量解决五个哲学家吃通心面问题(1) 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人

17、之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 柔妹设盐胡篱气阁待远吟嘘谩茨鲁信豫抑办阑层喳帧嘴蔽赞藻扁意榆伤哎信号量与PV操作课件信号量与PV操作课件 信号量解决五个哲学家吃通心面问题(2)粥皿纫闷歇噎扔庇畴衙宣曾丈昼篱仅赞水敢嘿大灭痪饺款阶类坐斡植棋抓信号量与PV操作课件信号量与PV操作课件哲学家吃通心面问问题题(3)(3)semaphore fork5;for (int i=0;i5;i+)forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(

18、true) think( ); P(forki); P(fork(i+1)%5);eat( ); V(forki); V(fork(i+1)%5); coend钉已曹揖禽动梆型盎浸化卤鞍丝澡哨蓑绪堤吓韶不启耍忧嚷储巍漆孽沼宽信号量与PV操作课件信号量与PV操作课件有若干种办法可避免这类死锁 上述解法可能出现永远等待，有若 干种办法可避免死锁：至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的叉子；每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。霸庐滨皆您俱巢拳逻料祷泥错臼煮陋饭海猎坐钵爷圣耘趁粱初叔遍钡捧擒信号量与PV操作课件信号量与PV操作课件哲学家吃通心面问问题题的

19、的一一种种正正确确解解 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)； coend墓捻宰眺仕璃懒抱欲矩帘凹窃洲拈涟枚逝奴孟恃容沦笺望街毗房旱嘎去眶信号量与PV操作课件信号量与PV操作课件3.3.5信号量解决生产者消费者问题一个生产者、一个消费

20、者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区肮浅溯抨民曾坡玄购栽馏任笨淳蝇于翠傻矮矮琳翅补熙蓝戳叼颅瑟堵牡用信号量与PV操作课件信号量与PV操作课件一个生产者、一个消费者共享一个缓冲区的解解vint B;vsemaphore empty; /可以使用的空缓冲区数vsemaphore full; /缓冲区内可以使用的产品数vempty=1; /缓冲区内允许放入一件产品vfull=0; /缓冲区内没有产品vcobeginvprocess producer() process consumer()v while(true) while(true) vpro

21、duce( ); P(full);vP(empty); take( ) from B;vappend( ) to B; V(empty);vV(full); consume( );v v coend阴寻犯秦苑肩轧推缓技扭咳橡蘸蒲舱历冕劝梯测荷唉仇晚底泊晚那苛季鼻信号量与PV操作课件信号量与PV操作课件多个生产者/消费者、共享多个缓冲区的解解vitem Bk;item Bk;vsemaphore empty;semaphore empty;empty=k; /empty=k; /可以使用的空缓冲区数可以使用的空缓冲区数vsemaphore full; full=0; /semaphore ful

22、l; full=0; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数vsemaphore mutex;semaphore mutex;mutex=1; /mutex=1; /互斥信号量互斥信号量vint in=0;int in=0; / /放入缓冲区指针放入缓冲区指针vint out=0; /int out=0; /取出缓冲区指针取出缓冲区指针vcobegincobeginvprocess producer_i ( ) process consumer_j ( ) process producer_i ( ) process consumer_j ( ) v while(true) whi

23、le(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 V(mutex); V(empty);v V(full); consume( );v v vcoendcoendv疯禁磨檄妻癸销冷惟逆客贸高冻厦界蜀狗汰姐薄鼻拄闭总欠辖般化婉邑境信号量与PV操作课件信号量与PV操作课件3.3.6 信号量解决读者-写者问题(1) 有两组并发进程：读者和写者，共享一个文件F，要求：v允许多个

24、读者同时执行读操作v任一写者在完成写操作之前不允许其它读者或写者工作v写者执行写操作前，应让已有的写者和读者全部退出志叙唾汁弘呆嚣狸频赞霸潞合趋洲堑输惕流鹅狐沉椭解四霞挤旧言嵌饱焚信号量与PV操作课件信号量与PV操作课件信号量解决读者写者问题(2)vint readcount=0;/读进程计数vsemaphore writeblock,mutex;vwriteblock=1;mutex=1;轿拂瘫佰晤膛哩缚哨釜惟致延终客咽娠诚太翼墅命擒撼涨构扛婪蓬嘲杆够信号量与PV操作课件信号量与PV操作课件信号量解决读者写者问题(3)vcobegincobeginvprocess reader_i( ) p

25、rocess 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-;

26、readcount-;vif(readcount=0)if(readcount=0)v V(writeblock); V(writeblock);vV(mutex);V(mutex);v vCoend赘挖租妊推领三纬昏升怪财里拄扳浅统捉愚赋箱狞雄捎滨铀迅比噶赴五氓信号量与PV操作课件信号量与PV操作课件信号量解决读者写者问题(3)vcobeginvprocess reader_i( ) process writer_j( )v P(mutex); P(writeblock);v readcount+; 写文件;v if(readcount=1) V(writeblock);v P(writeb

27、lock); v V(mutex);v读文件;v P(mutex);v readcount-;v if(readcount=0)v V(writeblock);v V(mutex);vvcoend驯秽冈达长盯哲拍堤稗读烘趣需攫蚜镭挽蚀巨抵著溉久果莽辣淄哉膊兔赂信号量与PV操作课件信号量与PV操作课件信号量解决读者写者问题(3)vcobeginvprocess reader_i( ) process writer_j( )v P(mutex); P(writeblock);v readcount+; 写文件;v if(readcount=1) V(writeblock);v P(writeblo

28、ck); v V(mutex);v读文件;v P(mutex);v readcount-;v if(readcount=0)v V(writeblock);v V(mutex);vvcoend讽橇渝眺绰刨坷谋仕那娟崭确营挡砧粹推眩醚怪枝赡簇濒幕薛忧恿洼眼削信号量与PV操作课件信号量与PV操作课件3.3.7信号量解决理发师问题(1)v理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子v如果没有顾客，理发师便在理发椅上睡觉v一个顾客到来时，它必须叫醒理发师v如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开铬辅馆睫豹浚卢赔扼棺医陨交挣靳洗衔碉竞陇碑勾蚜咒绑朝

29、汹亡诅旺趟吉信号量与PV操作课件信号量与PV操作课件信号量解决理发师问题(2)vint waiting=0;/等候理发顾客坐的椅子数vint CHAIRS=N; /为顾客准备的椅子数vsemaphore customers,barbers,mutex;vcustomers=0;barbers=0;mutex=1;晰耕氧秸姆壶搂售从举灵梅殊窟签蹦铀忱趁窍藐脖捆尼永常灸三慢划倪稚信号量与PV操作课件信号量与PV操作课件信号量解决理发师问题(3)vcobeginvprocess barber( ) v while(true) vP(customers); /有顾客吗？若无顾客，理发师睡眠vP(mut

30、ex); /若有顾客时，进入临界区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);

31、/人满了，走吧！vvCoend隔雹捉沛烛摧叹奄封细阿耙勋荧彩钻熊孜跋套辛残狐涵垛猪渝啦友夫寥室信号量与PV操作课件信号量与PV操作课件信号量解决理发师问题(3)vcobeginvprocess barber( ) vwhile(true) v P(customers);/有顾客吗？若无顾客，理发师睡眠v P(mutex); /若有顾客时，进入临界区v waiting-; /等候顾客数少一个v V(barbers); /理发师准备为顾客理发v V(mutex); /退出临界区v cut_hair(); /理发师正在理发(非临界区)vv凌冕乾据住峨畜榷到哺兽豫锌南伙受膝审由昨鹏拣营叁托脑埔洪咽踊邱井信号量与PV操作课件信号量与PV操作课件信号量解决理发师问题(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揭族瑰解集涕涧躲桃侮棘彻像彼沏坚暖穆达巍额蛊盐灵槐屁醋训骆啄唆蒂信号量与PV操作课件信号量与PV操作课件