打印

强烈要求大家都来讨论!如何解决解决哲学家吃饭问题

[复制链接]
楼主: singleywy
手机看帖
扫描二维码
随时随地手机跟帖
41
123jj| | 2011-3-16 10:46 | 只看该作者 回帖奖励 |倒序浏览
...
Chandy/Misra解法

1984年,K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法,允许任意的用户(编号P1, ..., Pn)争用任意数量的资源。与迪科斯彻的解法不同的是[來源請求],这里编号可以是任意的。
1.对每一对竞争一个资源的哲学家,新拿一个餐叉,给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初,所有的餐叉都是脏的。
2.当一位哲学家要使用资源(也就是要吃东西)时,他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉,他都发送一个请求。
3.当拥有餐叉的哲学家收到请求时,如果餐叉是干净的,那么他继续留着,否则就擦干净并交出餐叉。
4.当某个哲学家吃东西后,他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉,那他就擦干净并交出餐叉。

这个解法允许很大的并行性,适用于任意大的问题。


highgear 发表于 2011-3-16 08:58



这个方法好!学习了,谢谢highgear老师~~~

使用特权

评论回复
42
123jj| | 2011-3-16 11:14 | 只看该作者
本帖最后由 123jj 于 2011-3-16 11:18 编辑

38楼推荐的方法,其本质是轮班制,张三吃完了,轮到边上的李四拿起筷子继续吃,李四吃完了,轮到边上的丙五拿起筷子继续吃,其优先级还是有少量微量区别,根本没法做到绝对平等,其典型的例子是开始时这5个哲学家同时想吃饭,不引入少量微量优先级,打破死锁,根本无解!

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
singleywy + 1 揭露现象的本质,支持姐姐
43
singleywy|  楼主 | 2011-3-16 12:14 | 只看该作者
33# 123jj
呵呵,首先感谢123jj姐姐的支持,我个人感觉其实这个问题,如果上升到一定的高度,即从哲学抽象的角度来说,绝对的平等是不存在的,世界上没有什么是平等的,就比如一根筷子,你说应该你先得到,还是我先得到,如果我先得到的,对于对方来说是不平等的,如果对方先得到,其实对于自己来说是不平等的,这个问题本来就是一个悖论,所以说正向123jj姐姐说的那样,如果哲学家平等,这题无解,不管是刘前辈给出的解法,还我写的解法,实质上增加了少量的优先级问题,即如果要想题目有解,哲学家之间必不平等。。。。。。。。。

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
123jj + 1
44
程序匠人| | 2011-3-16 12:23 | 只看该作者
很有趣的一个话题,给其中两个回帖加酷了。

刘前辈每次传的PDF好像都是节选,能不能把完整文档传一份上来?因为我很好奇其余部分的内容。

使用特权

评论回复
45
123jj| | 2011-3-16 13:24 | 只看该作者
43# singleywy

呵呵!
singleywy小盆友对此问题解释的很清楚,赞一个~~~

本题的用意和目的,俺认为,是用最小的代价(如代码长度,执行效率),来达到最佳的效果(即最接近平等公正的并发效果),否则,讨论毫无意义~~~

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
highgear + 1
46
kubuco| | 2011-3-16 13:39 | 只看该作者
MARK

使用特权

评论回复
47
highgear| | 2011-3-16 20:46 | 只看该作者
顶 123jj的少量的优先级。
顶 43 楼 singleywy。

使用特权

评论回复
48
原野之狼| | 2011-3-16 23:56 | 只看该作者
时不时的就有关于OS的讨论帖~

使用特权

评论回复
49
123jj| | 2011-3-17 04:09 | 只看该作者
呵呵!

目前本贴分两大派别,一派的领头大虾主张写程序,谁能写出程序用代码描述自己的算法—— 谁牛X。
另一派的领头大虾主张算法理论,让小菜们能理解且学会基本算法理论—— 授之以渔。

不过,这两派别的争论与PK,让俺小菜们大开眼见,长了点本事。

使用特权

评论回复
50
123jj| | 2011-3-18 23:16 | 只看该作者
现在台湾有一款采用FPPA技术的8核八位MCU,将这块*币售价仅一块钱左右的8核MCU,用于OS,一定是一流的,一切争论全部和谐掉!可最多同时8道程序并发处理,没有冲突,没有资源瓶颈,也没有死锁,简化编程,提高OS程序的坚固性和稳定性~~~

使用特权

评论回复
51
aihe| | 2011-3-19 16:14 | 只看该作者
没冲突、没资源瓶颈、没死锁是不可能的
8核同时用的简化编程?!不可能!只能造成编程复杂化

使用特权

评论回复
52
123jj| | 2011-3-19 16:40 | 只看该作者
这世上没有什么不可能,只有想不到~~~

这种小容量芯片应用,根本不需要用OS系统,因为本身的8道程序并发处理,就是现成的硬件最小OS系统~~~

省掉了软件OS系统,难道不是简化程序~~~

8道程序同步并发处理,本身就是解决软件OS系统8道程序异步并发处理而产生的资源瓶颈之良药,至于没冲突、没死锁是相对的,严格的说,有竞争就有冲突、死锁产生,但8道程序同步并发处理比软件OS系统8道程序异步并发处理即时响应速度更快,执行时间均匀性更好,同样的算法和程序,在8道程序同步并发处理,可能产生冲突、死锁的概率和机会会降低~~~

使用特权

评论回复
53
aihe| | 2011-3-19 17:23 | 只看该作者
把一个任务分给8个核同步并发完成要考虑的事情比单个核多的多,多个核心如何同时访问RAM或外设等等而不会引起冲突、死锁是件很费心的事,比单核心发生问题的几率要高很多,除非同一时刻每个核心访问的资源是不同的,不用合适的OS很难达到预期的效果

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
123jj + 1
54
123jj| | 2011-3-19 19:08 | 只看该作者
aihe老师正解!

OS系统的优势,在于对单核MCU的分时管理,即对单核MCU处理比较实用,OS系统处理多核发生问题的几率要高很多~~~

而对多核MCU而言,其硬件本身就是一个简易OS系统,无需额外软件支持,这是他的优势。
多核MCU,同时处理多个任务,有绝对的优势,通过软件模拟,能简化硬件成本。

对于单个任务,对于多核MCU,一般方法是,可通过拆分成多个独立小任务,独立完成后,最终再归纳处理。

使用特权

评论回复
55
123jj| | 2011-3-19 19:19 | 只看该作者
再比如,有一个系统,要用到7路高速串口,采集数据,要找到一片同时拥有7路高速串口的廉价MCU很难,但用这块售价仅一元*币左右的8核八位MCU就能用软件模拟轻松做到!

使用特权

评论回复
56
123jj| | 2011-3-19 21:00 | 只看该作者
更正一下55楼:

对最简单的多道程序模拟中断程序,可用单指令 wait0 代替 t0sn + goto 组合指令,对PA.5下降沿或低电平执行模拟中断,这样,响应中断速度最快,只需一个机器周期(由于是单周期MCU, 即只需一个时钟周期),远远高于一般MCU的硬件中断响应时间。
如想对PA.5上升沿或高电平执行模拟中断,则需将等待跳转指令 wait0 改为 wait1 即可。

label: wait0 pa.5   ;如果PA.5是0, 执行模拟中断程序,否则,循环等待。
      ..........          ;模拟中断程序。


用多道程序并发执行软件模拟中断程序,其优点是中断响应快且应用灵活,只需1个机器周期(由于是单周期MCU, 即只需一个时钟周期),如用第一核执行主程序,剩余的7核全部实时模拟外部中断,这7路外部中断源,每一路的中断响应均为1个机器周期(即只需一个时钟周期),这是普通MCU硬件外中断无法做到的!

使用特权

评论回复
57
刘前辈| | 2011-3-20 21:21 | 只看该作者
本帖最后由 刘前辈 于 2011-3-20 21:37 编辑
如果哲学家平等,这题无解,不管是刘前辈给出的解法,还我写的解法,实质上增加了少量的优先级问题,即如果要想题目有解,哲学家之间必不平等。。。。。。。。。


谁说哲学家平等就无解?开玩笑,学过操作系统课程的都知道这个经典问题如何解。——不妨看看银行家算法讲的是什么意思。没学过最好别“这不可能,那样无解。”别人怎么能解?荷兰人能解,咱中国人就解不了?

要不要我把几种解法贴上来?看看别人大师是如何解的。

强调一点:哲学家就餐问题是现实世界的经典例子。国际OS大师们讨论的是机制不是策略。——这与采用什么处理器,单处理器还是8处理器,高速低速,宏观  微观,并行还是并发,优先还是平等,根本没有关系!风牛马不相及!

5个哲学家绝对是平等的!5个人同时拿起一只筷子的情景在现实世界中是绝对存在的。大学里食堂都是11:30准点开饭,大家都准点同时涌向食堂。(可别说极个别人上午没课,11:25就去食堂窗口排第一。)到了咱们这就非要给谁来点少量优先级?劲儿大能挤的排前面……,练练“加塞儿”的技巧……优先级高啦。

就好像一帮首脑在讨论二战国际战略问题,结果咱上去“给他2颗原子弹不就完了?”“还讨论个啥?”——那不是一码事。

别谈处理器,谈谈现实世界中怎么办,算法和什么处理器,单核多核没关系。几十年都是一样经典的。——不是什么随着处理器能力提高,这个经典问题就没意思了什么的,再过500年,人还是人,5个哲学家还是平等,没谁和别人不一样。

非要让5个哲学家不平等,聪明过头了吧,把世界经典问题都修改了。——如此创新……不知什么心理……玄

使用特权

评论回复
58
123jj| | 2011-3-21 09:28 | 只看该作者
这个世界上,P民们想往绝对平等,可现实社会中,要实现有限平等都很难,更不要说绝对平等~~~

这个世界上,P民们都指忘人人平等,没有聪明与笨之分,可现实社会中,聪明的就是聪明,笨的就是笨,喜欢胡打蛮缠的始终胡打蛮缠,前有AVR坛主PK菜农的密码学技术,吓得菜农结结巴巴,无话可说,只能拿出革命奖状充门面。如今,要是爱因斯坦称第二,就没人敢称第一的世界上,突然发现,二姨家有一人能胜过爱因斯坦称第一 ~~~

使用特权

评论回复
59
singleywy|  楼主 | 2011-3-21 10:54 | 只看该作者
谁说哲学家平等就无解?开玩笑,学过操作系统课程的都知道这个经典问题如何解。——不妨看看银行家算法讲的是什么意思。没学过最好别“这不可能,那样无解。”别人怎么能解?荷兰人能解,咱中国人就解不了?

要不 ...
刘前辈 发表于 2011-3-20 21:21

呵呵,刘前辈,也许每个人的世界观不同吧,如果学过哲学,从哲学的角度,确实是这样的,让哲学家来回答这个问题,估计他也会这样说的,只是不会用专业术语来表达罢了

使用特权

评论回复
60
aihe| | 2011-3-21 13:26 | 只看该作者
看不惯动不动就拿老外的东西炫耀,学了几天外语,看了几本外国书,就认为外国的月亮特别圆,外国的老爸特别厉害什么的
有空研究研究周易,看看自己老祖宗怎样解决类似问题的吧
说到食堂排队,那你说说看就算是大家都是同时到,食堂排队也是有先后的,排除插队等问题,你认为食堂里那个师傅该如何打饭来实现每个学生都是平等的

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
highgear + 1
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则