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:这个解答我逻辑上想了一下,没有错误,但我一个同学说实际上载机器上跑时好像有问题,自己就没想明白,请高手指教了
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。