本帖最后由 刘前辈 于 2011-10-21 19:28 编辑
太让人兴奋了！中午一小时证明了哲学家就餐人数为什么必须是奇数2N+1 ！所长搬起石头打自己的脚：你不支声，没人知道你不懂，偏要站出来说几句装懂的话，结果露大怯了：
16,17楼 highgear 所长
3） “Dijkstra 的哲学家就餐经典问题首先条件就是哲学家人数为奇数”， 我kao, 竟然还有这样认为人数为偶数，死锁就不存在的蠢人！！！ 真不知道刘公公你的哲学家就餐的研究生论文是如何通过的？
下面证明一下，看看究竟谁是蠢人，俺太得意了……要不要再给54岁的所长留点面子？自己收回，还是向俺道歉，还是以后继续不懂装明白？看下面示意图：
假定偶数4个哲学家就餐，4把叉子可以同时2个人吃饭，假定1、3同时吃饭，2、4由于拿不到叉子，只好（休眠）等待；当1、3 两个人吃完饭，放回叉子时，按照 Dijkstra 信号量休眠唤醒机制，有责任唤醒等待叉子资源的伙伴；——也即：1号哲学家吃完饭应该唤醒左右 2、4 两个伙伴拿叉子吃饭，3号哲学家应该唤醒 4、2 两个伙伴。
问题来了，假定1号和3号两个人同时吃完饭，并同时检测自己左右两个伙伴是否满足2把叉子资源条件时，——都不满足！
例如（唉！这么明显的问题，54岁的所长还想不明白……）：1号测查右手伙伴（休眠者）4号是否满足左右手（在1号，3号手里）都有空叉子时，由于3号没有放下叉子，所以4号因缺乏资源而不能被唤醒；同理，1号左手伙伴休眠者2号也不满足唤醒条件。结果1号无奈，吃完饭后只好放下叉子，Thinking去了。唤醒义务一点没尽到。
再看3号，由于是和1号并发行为，也无奈放下叉子进入Thinking 。结果等待叉子吃饭的2号、4号哲学家继续休眠，忍耐饥饿。
哈哈，再加上一个5号哲学家就大不一样啦；如图：
不用讲下去了吧，这时1号检测的右手伙伴是5号，5号已经有了一把叉子的资源，等待的是1号手里的另一把叉子，1号正好吃完饭交给5号，结果1号成功唤醒伙伴5号，——5号吃完当然有责任唤醒4号，于是系统连续运行下去，不会出现饥饿现象和系统不正常停止现象了。对于另一就餐完毕者3号哲学家情况相同，即使他和1号并发行为，但这时当他唤醒左手伙伴4号哲学家时，测试到4号的左右资源不再是1号没放下的叉子，而是5号放在桌子上的叉子资源，结果唤醒4号条件满足。……
推广到任意偶数，原理一样。加了一个奇数哲学家，意义深远，——他总保留一把和其他人没有关系的叉子；说简单点，所有问题都是因为人类有2只手——偶数。
且看唤醒程序源代码就清楚了：
void test ( i )
{
if ( state [ i ]= =HUNGRY && state [LEFT] !=EATING && state [RIGHT ] !=EATING )
{
state [ i ]=EATING;
up ( & s[ i ] );
}
}
、、 |
楼主
