下面我们来讨论如何用前面的
信号量和管程的方法
来解决几个经典的同步问题
这就是我们这里说到的
哲学家就餐问题和读者写者问题
首先我们来看哲学家就餐问题
这个问题的描述是这样的
有五位哲学家围坐在一个圆桌旁
这是这五位哲学家
他们编号分别为0到4
然后桌子上呢放了5把刀叉
每个哲学家之间呢有一个
那这地方纯粹是为了我们在这里
来讨论同步互斥而设置一种场景
在这里头呢
每个哲学家会进行思考
或者就餐两种操作
那思考呢不需要周围的资源
而就餐呢 他需要拿到两个叉子
他才可以开始就餐
所以这时候呢
两个哲学家之间
会需要共享一把叉子
那我们可以在这儿认为呢
这个叉子是我在这里头
两个哲学家之间的共享资源
在思考的时候
哲学家会把两把叉子都放回原处
在他旁边的哲学家就可以用
这个叉子来进行就餐了
好 我的问题是我如何让
这五个哲学家能够有序的进行
他们想进行的操作
也就说他思考的时候
这时候随时可以进行
不就餐的话
他就可以在这里进行思考
那关键问题是
他想就餐的时候会怎么样
如果说相邻的两个哲学家都想就餐
那这时候呢
他们就需要有一个人等待
原因在于 这时候他们俩之间
只有一个叉子
这个叉子只能保证一个人用
好 这时候我们说
用什么办法我们能解决这些问题呢
说我在这里首先想到的
是用信号量的办法
那信号量的办法我如何来解决呢
那我们在这里做法呢
第一个方案是说我每把叉子
算是一个资源对应着一个信号量
那它的初值是1
好 然后说先有一个程序的框架
五个哲学家
每个哲学家的ID呢这里的i
它可能是0到4
它可以进行两种操作 思考和就餐
我们在这里需要考虑
主要部分是他就餐这一部分
就餐的时候他需要拿到
左边的刀叉和右边的刀叉
那这时候我们说两个P操作
来获得他左边和右边的叉子
如果他能获得到他就会就餐
等他吃完之后
他释放两边的刀叉
整个又回来 他可以又进行思考
那这时候的问题是
这个算法行吗
那在多数情况下它是没问题的
你比如说在这里头
我先申请左边的刀叉
那如果申请不到
那我再去申请右边的刀叉
如果两边申请到我就就餐
如果申请到一个
旁边这个人呢已经先拿取
我的右边的刀叉
对于他来说是左边
好 那也时候呢
我就会等着他就餐完毕之后
他放下刀叉然后进行思考的时候
我再拿起右边刀叉
这时候我也可以开始就餐了
但是在一种极端的情况下
大家可以想象
如果五个哲学家
他们都在同一时间
进行相同的动作
这时候会出现什么情况
大家一起拿左边的刀叉
先假定在前面所有的刀叉
都是放在那儿的
好 大家一起拿左边刀叉
然后这时候都拿到左边之后
这时候五个哲学家
每个人拿到一个刀叉
都是左边的对于他们来说
好 这时候他开始拿去拿右边这个
那这时候会出现啥情况
每个哲学家右边都没有了
好 那按照刚才我们约定说
这时候等着下一个用完了我再来用
但实际上这时候呢
每一个人都拿到了左边的刀叉
没有拿到右边了
而这时候所有人呢都开始等待
那这时候会等出结果来吗
没有任何一个人可以开始就餐
那这样一来的话
所有的人都是无限期等待下去
好 那所以这时候出现什么问题
这个算法是不正确的
有可能进入死锁
也就是五个人同时
拿左边刀叉的时候
那它就会进入死锁状态
好 那这个不行我怎么改呢
那这就是我们想到的第二种做法
极端的做法
因为实际上在我们系统里头
我们希望把资源得到充分的利用
一旦我没有办法做充分利用的时候
我就把所有资源打成一个整包
然后说只有一个进程
可以占用这一整包的资源
不管它是不是都需要
那在这种情况下
我这个系统也能正常的运行下去
只是效率低一些就是了
好 那我们想到是这种做法
我设置一个互斥变量
我任何一个时刻
只有一个哲学家可以就餐
那这事呢也变得可以能解决出来
那在这儿也是这样的
这是思考就餐
我需要保护就餐这一段
我用这个 mutex
来作为这个互斥信号量
好 在这个地方呢
P操作和V操作 任何一个哲学家
他只要是申请到这个互斥信号量
也就是我们这里说二进制信号量
好 那这时候呢它就可以进行就餐
因为它的初值是1
所以任何一个时刻
只有一个哲学家能够
获取到这个信号量
然后他再去依次
拿起左边和右边的刀叉
那这时候它会碰到障碍吗
不会 因为这五个信号量
你只有在申请到了
二进制信号量之后
你才有可能来申请到
刀叉的信号量
而任何一个时刻呢
我只有一个进程
申请到二进制信号量
好 那这时候呢
后面这两个申请不会碰到问题
好 他会就餐
吃完之后他放下刀叉
然后释放互斥信号量
他继续上面的思考
那从这种做法里头呢
我们看到 这是能够保证
大家顺序吃饭的
但是我这时候的情况
是我有五把刀叉
按道理来说
我可以给两个人一起吃
因为总会剩一把刀叉在那儿放着
而我们现在这里头呢
我只要他一个人吃
好 那这样话它的效率就降低了
但是它是正确的
这种做法呢我们认为它可以接受
但是性能不好
我们有没有更好的办法
好 那这时候我们说
再给出第三种解决方案
我仍然是用五把刀叉
但是我不会设一个全局的锁
把整个就餐这事
变成一个临界区的操作
那我怎么办呢
针对我们刚才说到的
五个哲学家一起拿起左边的刀叉
之后所面临的死锁的情况
我让他们每个人
拿刀叉的时候有差异
不至于是所有的人
全部都一起拿起左边的
那这样一来的话就
不会出现构成环路的情况
那总会有先有后
好 最后保证大家都能拿到
那在通常情况下呢
我可以两个人一起就餐
那在这儿怎么做呢
好 我在这儿设一个分支结构
如果说根据每个人的编号不同
我采取不同的动作
偶数编号的
我先拿左边后拿右边
奇数的先拿右边后拿左边
那这样一来的话
就不会出现五个都拿到
一部分资源构成环路这种情况
好 那等他就餐完了之后
我把刀叉放回去
那这时候我有必要再在这个地方
再把它分成两种情况吗
实际上这个操作它是不会堵塞的
所以你不用把它分成两种情况
好 那么这时候说
在这种情况下我可以
两个哲学家同时就餐吗
你比如说0号和2号
假定这时候没有其他人的话
那他们俩是可以的
因为中间隔了一个哲学家
好 那这时候他们俩
都可以拿到相应的叉子
他不断是正确的
不会出现死锁
并且允许 有可能的话
两个人同时就餐
这是我们在这里呢
用信号量能给出的
一种比较理想的办法
那这时候问
这种做法是不是最优的呢
我是不是可以
还想得出更好的办法呢
这个呢留给大家
下去之后进行思考