linux Posix 信号量 三 (经典例子)

本文将阐述一下信号量的作用及经典例子,当中包括“《越狱》寄信”,“家庭吃水果”,“五子棋”,“接力赛跑”,“读者写者”,“四方恋爱”等

 

首先,讲 semWait操作(P操作)和semSignal操作(V操作)的一些基本原则。(接下来同意称为P,V操作)

1. P操作,s - -,if(s<0)阻塞自己

2. V操作,s++,if(s<=0)唤醒一个其他进程

3. P,V操作时原语(通俗讲,就是执行PV操作时时不能被打打断的)

4. P,V操作总是成对出现的。P:资源申请/分配;V操作:资源的释放

 

 

 

一般每个进程的PV操作代码:

s = ?  //根据资源数进行初始化

P(s)

临界区

V(s)

 

 

 

 

一.《越狱》寄信

 技术分享

 题目描述:

T-boy给brad送信,Mike给Lincon送信,但他们送信收信都通过同一个树洞。

 

解答:

信号量:

 

Lincon: 是否有Mike的信,s1 = 0

Brad:    是否有T-boy的信,s2 = 0

Mike和T-boy: 树洞是否为空,s3 = 1

 

Mike:                    T-boy:                 Lincon:                 Brad:

 

write()                  write()                P(s1)                    P(s2)                               

P(s3)                    P(s3)                  getit()                   getit()                                    

putit()                   putit()                 V(s3)                   V(s3)                                           

V(s1)                     V(s2)                 readit()                 readit()

 

 

 

二. 家庭吃水果(对第一题的扩充,不同的只是现在资源比之前多了,变成了3个)

 

技术分享                                       

 

                                                                                             

 

 

解答:

信号量:

 

儿子: 是否有苹果,s1 = 0

女儿: 是否有桔子,s2 = 0

爸妈: 是否可以放水果,s3 = 3

 

爸:                          妈:                     儿子:                      女儿:

 

makeit()               makeit()              P(s1)                    P(s2)                               

P(s3)                    P(s3)                  getit()                   getit()                                    

putit()                   putit()                 V(s3)                   V(s3)                                           

V(s1)                    V(s2)                   eatit()                  eatit()

 

 

 

 三. 五子棋

题目描述:白子和黑子各有32个,黑子先行,怎样设置信号量,才能黑子先行,且是交替下子

 

解答:

信号量: 

白子可下吗? s1 = 0

黑子可下吗? s2 = 1

     白                                             黑

for(i=0;i<32;i++){                   for(i=0;i<32;i++){                             

   取子                                          取子       

   P(s1)                                        P(s2)         

   放白子                                       放黑子     

   V(s2)                                        V(s1)

}                                              }

 

 

四.接力赛跑

题目描述:四个人进行接力赛跑,要求使用信号量的方法使得跑的顺序是P1->P2->P3->P4

解答:

信号量:

s2:2号接棒 0

s3:3号接棒 0

s4:4号接棒 0

 

P1                P2                 P3                       P4

 

                  P(s2)             P(s3)                   P(s4)                    

run             run                 run                      run               

V(s2)          V(s3)             V(s4)    

 

接上篇的信号量经典例题,其中包括“读者写者”,“过独木桥”,“公交车”,“四方恋爱”等

 

一. 读者写着问题(这里有很多种情况):

(1)读者优先

题目描述:有一本书,有多个读者和写者,读写互斥,写写互斥。当多个读者可以同时读,即当有读者在读这本书时,其他的读者也可以进来读,但写者就不能进来写。

解答:

信号量:

w:可写否:1

nReader:读者数 :0

mutex:读者之间的“互斥”,进出的先后顺序而已:1

写者:                读者

 

P(w)                P(mutex)

写                    nReader ++ 

V(w)                if(nReader == 1)//第一个读者

                             P(w)            //堵塞写者

                       V(mutex)

                       读

                       P(mutex)

                       nReader - -

                       if(nReader==0)//最后一个读者

                             V(w)          //唤醒写者

                        V(mutex)

 

(2)写者优先

题目描述:有一本书,有多个读者和写者,读写互斥,写写互斥,不同的是只要有写者等,后续读者必须等待在写者后面

w:可写否:1

nReader:读者数 :0

mutex:读者之间的“互斥”,进出的先后顺序而已:1

s:用于封锁后续读者 :1

写者:                读者

 

                       P(s)

P(s)                   P(mutex)

P(w)                nReader ++ 

写                    if(nReader == 1)//第一个读者

V(w)                      P(w)            //堵塞写者

V(s)                  V(mutex)

                       V(s)

                       读

                         P(mutex)

                       nReader - -

                       if(nReader==0)//最后一个读者

                             V(w)          //唤醒写者

                         V(mutex)

 

 

二.过独木桥

技术分享

 

 

题目描述:

桥单向通行,分别从西到东和从东到西

解答:

信号量:

s : 表示桥可用? :1

nw : 东向西人数 :0

ne :  西向东人数 : 0

m1: 互斥对nw的修改 :1

m2: 互斥对ne的修改  :1

 

ToWest                                                   ToEast

 

P(m1)                                                      P(m2)

nw++                                                      ne ++

if(1==nw)                                                if(1==ne)

    P(s)                                                           P(s) 

V(m1)                                                      V(m2)

cross the bridge  to west                        cross the bridge to east        

P(m1)                                                      P(m2)

nw--                                                        ne - -

if(0==nw)                                                if(0==ne)

    V(s)                                                           V(s)

V(m1)                                                      V(m2)

 

 

三.四方恋爱

题目描述:有两男两女,男士送女士玫瑰,女士送男士手表。一一对应,每个只能连接一个

解答:

(1)老师答案

信号量:

m1:互斥女士之间的收花送表行为:1

m2:互斥男士之间的收表送花行为:1

s1:有花? 0

s2:有表? 0

 

女士                                     男士

 

P(s1)                                  P(m2)

P(m1)                                 送花

收花                                    V(s1)

送表                                    P(s2)

V(s2)                                  手表

V(m1)                                 V(m2)

恋爱                                    恋爱

 

(2)自己的答案

四个分别是李四(男),张三(男),嘻嘻(女),哈哈(女)

信号量:

g1:是否有表收 :0

g2:是否有玫瑰收:0

s1:是否可以送表:1

s2:是否可以送玫瑰:1

note:这里只运行一次的,不能够循环

李四                               张三                               嘻嘻                               哈哈

P(s2)                             P(s2)                            P(s1)                             P(s1)     

sendRose()                   sendRose                     sendWatch                   sendWath

V(g2)                             V(g2)                            V(g1)                            V(g1)

P(g1)                             P(g1)                            P(g2)                            P(g2)

getWatch                      getWatch                     getRose                        getRose

V(s1)                             V(s1)                            V(s2)                             V(s2)

 

ps:这个解答我逻辑上想了一下,没有错误,但我一个同学说实际上载机器上跑时好像有问题,自己就没想明白,请高手指教了

    

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。