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

发表于 2011-3-15 18:29

19# 刘前辈
刘前辈，您为什么抱着这一解不放呢，实际上的解法有很多也很简单，您所给的材料中一样，那只是一解罢了，真正实际应用中解法很多，为什么认为我的不对呢，您是否仔细了阅读了我的贴子，不管怎么说，我阅读了您的贴子，并积极的研究，同时搜罗了不少资料，您是否认真阅读了我的贴子，并且您为什么只**您所认同的解法呢？

登录 · 发表于 2011-3-15 18:35

本帖最后由刘前辈于 2011-3-15 18:44 编辑

相信上面1、2、3种方法已经很全面了，好像还有书上见过有第4种方法，反正我想不出LZ那样的方法。LZ如果**说自己的方法是正确的，写篇论文投稿呀。还可以翻译成英文投到国际OS论坛什么的。——如今就鼓励创新。有才能不能埋没。让咱们中国人扬眉世界多好。

、

发表于 2011-3-15 18:43

我为什么说你的是错的：因为你把2只筷子分裂为2个资源，而且不在同一个临界区了。所以，从OS并发角度，死锁条件就来了。见教材：确实有很多种方法解这个经典问题，但是基本前提就是2个资源同时获取，同时释放。所有 ...
刘前辈发表于 2011-3-15 18:15

很遗憾，您的说法太武断了，如果您阅读过UCOS，您可能就不会这么说了，其次并发的概念问题，并发，什么叫并发，宏观上的并发，微观上的单步的，除非他是多处理器，如果多处理机之间是相互影响的，实际上要涉及到同步于互斥问题，微观上又不是并发的

发表于 2011-3-15 18:51

本帖最后由 singleywy 于 2011-3-15 19:05 编辑

54426
54427

相信上面1、2、3种方法已经很全面了，好像还有书上见过有第4种方法，反正我想不出LZ那样的方法。LZ如果**说自己的方法是正确的，写篇论文投稿呀。还可以翻译成英文投到国际OS论坛什么的。——如今就 ...
刘前辈发表于 2011-3-15 18:35

我没有说的我的方法是完全正确，因为我只是你所介绍方法中1的方法，所以我才说我对，同时，您介绍的教材上方法，我搜罗的资料也有，正如我所说的，解此题的方法很多，在三种方法中，您为什么只**其中2的方法呢？而您向我介绍的时候，又给出三种解法，您不是自己打自己的嘴么？
不知您是否认真阅读我先前的贴子，我没有并否认你所说的解法；

发表于 2011-3-15 19:11

为什么说我的方法就是刘前辈材料中的方法1；
请注意我申请的顺序
TaskA :申请顺序4,0，释放顺序，0,4
TaskB :申请顺序0,1，释放顺序，1,0
TaskC :申请顺序1,2，释放顺序，2,1
TaskD :申请顺序2,3，释放顺序，3,2
TaskE :申请顺序4,3，释放顺序，3,4,与任务A同时申请的4，即
是否，满足最多只允许四个哲学家去拿右边的筷子，或者左边的筷子；
不知刘前辈是否阅读了我的代码，也草率地说我错了，这不与您给出教材的理论相违背嘛；
您是否再次意思到这个问题

登录 · 发表于 2011-3-15 19:37

本帖最后由刘前辈于 2011-3-15 19:47 编辑

宏观上的并发，微观上的单步的，除非他是多处理器，如果多处理机之间是相互影响的，实际上要涉及到同步于互斥问题，微观上又不是并发的

千万别再讨论这种最基本的概念理解偏差问题了。教你一个重要概念：书上没怎么强调的：

就是：当你在一个OS环境下写一个任务时，你不用考虑什么其他任务什么时间会抢占你之类的影响问题，你只认为你正在编写的当前任务是一个自己独占CPU的while(1)独立循环程序。——这就叫虚拟处理器的观点；10个程序员可以同时编写10个任务（任务划分是一门艺术），如果他们互相讨论谁先执行，互相什么影响，那叫裸奔。等讨论结果出来，多少年过去了。怎么同时运行这10个任务，那是操作系统的任务管理问题。用户操什么心？你用户还要考虑宏观微观，OS研究个什么劲？
——互斥，就是为了解决程序并发后所造成的异步不确定结果问题所采用的机制。如果你宏观并发，微观顺序，你用得着互斥机制？你也用不着OS那么多服务，你自己管理就行了，10个任务，你慢慢顺序调度管理。反正你一个人顶10个，有的是时间。

这里还有一道题你应该看一看：是我抄来的，单处理器上并发任务的最好应用，
2个独立不相关的任务1和任务2，——相当于过去的张教授和王教授提交的2个批处理程序
张教授任务1：每秒钟运行一次，运行时间开销500ms ；软实时任务。
王教授任务2：每分钟运行一次，运行时间开销3000ms（3秒），王教授优先级别高，硬实时任务。

请问张、王2教授任务如何在单处理器上并发运行？

实验板如图：
张教授500ms任务驱动数码显示屏计数显示，每500ms计数一次，——仅个位显示即可。0~9~0……

王教授3秒任务驱动P1口上的D1，每秒闪烁一次。

这道题比哲学家简单，但是如果微观顺序执行，大概无解。只好交给OS管理，怎么并发是OS的事，我用户才不关心。
所以，OS 对系统用户的水平门槛要求低多了。否则，这道题，高手也难。即使能解，至少也要一星期时间。像我这样的菜鸟，借助OS，20分钟就完成了。——如果微观上去算时序，可能要算一年也出不来。借助LZ的rtos好算么？20分钟能完成？

、

发表于 2011-3-15 19:44

本帖最后由 singleywy 于 2011-3-15 19:45 编辑

千万别再讨论这种最基本的概念理解偏差问题了。教你一个重要概念：书上没怎么强调的：

就是：当你在一个OS环境下写一个任务时，你不用考虑什么其他任务什么时间会抢占你之类的影响问题，你只认为你正在编写的当前 ...
刘前辈发表于 2011-3-15 19:37

您又说错了，您还是没有仔细看我的说法，我说的是单步，不是顺序，请您仔细看我说的是什么，再发言好么？所谓的单步，指的是，同一时刻，处理器只能处理一条指令，没有谁说是顺序执行指令的，OK?

发表于 2011-3-15 19:53

千万别再讨论这种最基本的概念理解偏差问题了。教你一个重要概念：书上没怎么强调的：

就是：当你在一个OS环境下写一个任务时，你不用考虑什么其他任务什么时间会抢占你之类的影响问题，你只认为你正在编写的当前 ...
刘前辈发表于 2011-3-15 19:37

同时，我告诉你，你给的问题之前早就阅读过了，21IC上的精华贴，凡是我涉及到的，我都看过了，这道题，学过OS的人都会，OK？我不是三岁小孩，什么也不懂，虽然我很菜，也不至于菜到基本的并发概念还不懂，如果我这些基本的东西都不懂，我还有什么能力写OS，即使写出来也是狗屎一坨，不是么？
还有一点，您在发表贴子的时候，请仔细看看我说的什么好不好，不要学我，很草率的下结论

发表于 2011-3-15 20:10

本帖最后由刘前辈于 2011-3-15 20:47 编辑

所谓的单步，指的是，同一时刻，处理器只能处理一条指令

太对了！我以为LZ不知道什么叫原子语句呢。
所以，下一时刻，单处理器就执行其他任务去了。结果，执行了5条指令，说不定就是5个任务并发呢。（内核调度器执行指令不算，平台下面，看不见的东西。）

LZ说我又错了？你知道我抄的是什么教材上的内容？你知道我们授课教师是谁么？

当然，你可以说书上错了，世界著名教材都是误人子弟，教授也讲错了，那有什么意思？

LZ看的都是源代码，从来没问过OS为什么要那样设计。

算了，别说不着边际的话了。有什么我说错的地方指出来我不吝花时间找书证实。

解不出26楼的题目什么都不好说。解出来，刘前辈佩服LZ，自我惭愧。哑口无言。是比我们教授厉害的人。
解出来也不好，解出来正好以事实证实什么叫并发和并发程序的写法。——管它微观宏观，宏观叫并行，并发本来就意指微观。这也要追究？证实自己对？
多处理器叫并发么。嘻嘻……

、

、

highgear · 发表于 2011-3-15 20:31

LZ看的都是源代码，从来没问过OS为什么要那样设计 ...
刘前辈发表于 2011-3-15 20:10

您又错了，如果只看源代码，能够弄懂，那只能算是半个菜鸟；
只知其然，而不知其所以然，那学这个还有什么用，还不如直接拿来主义，想用就用？
只有知道了它，为什么会这样设计，设计的目的是什么，才能够深刻地理解OS的内涵；没有理解OS内涵的人，不能算是真正的了解什么是操作系统，而我承认我并没有完全理解它，毕竟要想深入了解，并不是一朝一夕的事情，我也无权评价别人对OS理解如何，因为我是半壶水；在评价别人的时候，先应该确定一下自己的言论是否草率了一些，自己的分量是否够格。

发表于 2011-3-15 20:35

也许，我说话略显偏激了，还望海谅

发表于 2011-3-16 02:06

26楼，这样的两个破 led 还好意思拿出来。
“否则，这道题，高手也难。即使能解，至少也要一星期时间”，我*，刘工你挂一幅画都几个星期没挂上，最后发现墙是水泥做的，你是不是因此就认为挂一幅画是一件难度极高的事情？

"你知道我们授课教师是谁么？"
你的授课教师应该叫
.
.
.
.
.
.
.
.
.
李刚

highgear · 发表于 2011-3-16 06:19

应singleywy小盆友在 [侃单片机] 主题：大家共同来探讨一下吧，请大家评论评论！
中的要求，想让大家一起来探讨，聊一聊，俺不懂OS, 但俺知道，在优先级绝对平等，并发同步处理解决这个5个哲学家吃饭问题，真正的结果是-------死锁！无解！

为了解决死锁无解问题，聪明的人类想出了一个又一个法子，适当的插入少量微量优先级，打破优先级绝对平等，但尽量做到绝对平等，将这个问题变相解决了，于是，这道题，这5个哲学家吃饭问题，变成了有解-------其本质是引入少量微量优先级，打破死锁！

highgear · 发表于 2011-3-16 08:22

我来谈谈我的看法，虽然我不懂什么OS，也不想再弄个OS和裸奔之争。
看着这个讨论想起了中学里我们每天都有一节自习课，可是很多老师都想占用这节课来给学生补课，但是课只有一节，语文、数学、外语等等老师不可能每个都一起上，那就是有冲突了，有的老师上一节课就是他的课，他就霸着这资源顺延，有的老师是班主任，一般他能最先到达教室，一般他补的最多，还有就是谁先到谁上，还有就是几个老师商量好，今天谁上，明天谁上，轮流来。。。
从微观上来看任何多任务不是绝对的同时触发的，认为其同时触发的原因是CPU的采样速度，如果CPU的运行速度很低，所有的任务都可以被认为是同时触发的。如果运行速度很高，任务触发先后还是能分辨的。
OS处理并行任务时一般我认为就是时间分片运行（一个时钟只能运行一条指令，不说多处理器）如果一个任务独立占用CPU10mS，那么N个并行任务运行时间>N*10mS，因为调度任务也要花费CPU的时间。如果不相信把某一IO口每条CPU指令翻转一次，使其输出频率为时钟的1/2，看看多任务怎么运行的。
OS其实就是裸奔加个外壳并没有该变其运行的实质，OS也是翻译成汇编指令再转成机器码来执行的。OS和裸奔的区别就像全自动相机和全手动相机的区别差不多，他只是搭了个框架让你不用考虑很多细节问题而已，就像是没必要每个人都要去发明一次同样轮子。但是这个轮子很特别还是要自己发明的哦。
处理并行问题的时候对于MCU还是有优先级的，不少MCU有中断等级，如果像PIC等这种无中断等级的MCU，你中断后先查询哪个就表示他的优先级比较高，绝对的平等是没有的。

123jj · 发表于 2011-3-16 08:31

这和“哲学家”没关系，哲学家通常是单打独斗的主....

这是所谓的“资源瓶颈”，各进程或线程占着资源不放而又想申请别的被占资源。如此，便形成了一个死结——资源请求环路。

解决的最佳方法是预测，就是在“环”即将形成之际置相关资源为忙态（虽然表面上可用）。待即将形成的环中进程或线程归还相关资源后再进行分配。当然，为了能预测环的形成，必须建立一个相关的数据结构，以跟踪各进程或线程的资源占用和申请关系。总之，是力求防止环路的形成，而不是形成环后没辙了而再去强拆。

123jj · 发表于 2011-3-16 08:58

哲学家就餐问题是大学本科三年级的作业题。

哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步(Synchronization)时产生的问题。

在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

解法

[编辑] 服务生解法

一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。

为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。

[编辑] 资源分级解法

另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。

尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。

这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。

[编辑] Chandy/Misra解法

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

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

http://zh.wikipedia.org/zh/%E5%9 ... 0%E9%97%AE%E9%A2%98

发表于 2011-3-16 09:05

英文版有pascal 和 java 的程序：
http://en.wikipedia.org/wiki/Dining_philosophers_problem

发表于 2011-3-16 09:23

本帖最后由刘前辈于 2011-3-16 09:43 编辑

#33楼
在优先级绝对平等，并发同步处理解决这个5个哲学家吃饭问题，真正的结果是-------死锁！无解！

-------其本质是引入少量微量优先级，打破死锁！

真的呀！那这帮学者教授真是白吃饭了。整天忽悠人呢。

1、“你某一时刻只允许4个人吃饭不就结了……剩下那个饿着？剩下谁好？打起来了，打不过的那个人不许吃……”

2、优先级是要抢占的。这意味着，当如果有2个人欲同时拿一只筷子时，具有优先级的那位依仗自己力气大等优势，可以从对方手里抢夺下筷子。……哈，原来所谓世界经典问题就是看谁力气大啊……

3、……

看来这所谓OS经典问题研究都是大忽悠啊……

众多人正忽悠着，偏偏，出来一个人，把这个经典问题解了；他就是写的5个人完全一样的程序，5胞胎，没谁特别长得不一样。（这时候又要有人跳出来了：“5胞胎还有个老大，老五呢……）

其实很简单的方法：LZ 殷文跃本来已经接近目标了，还是那句话，关键是怎样用程序语言来描述算法，怎样使用信号量……

1、A 饥饿时，先预测一下坐在两边的兄弟是否处在吃饭状态；——如果有一个正在吃饭的，他就忍一会（睡眠）等待他们吃完，谁吃完了之后会唤醒身边的兄弟A的。
2、利用信号量集机制；
3、利用AND信号量机制。

其实意思都差不多，就是把2个资源当做一体，同时获取，同时释放。

殷文跃了不起的地方，就是他写出了代码，他能用代码描述自己的算法。—— 一切空理论方法都没什么意思。这个说应该这么解，那个说根本无解。

说有解的人把自己的解法像殷文跃那样用代码写出来，给那些认为“根本无解”的人看看，什么叫算法。让他们开开眼，也长点本事。

、
、、

发表于 2011-3-16 09:44

呵呵，楼主这个挺有意思

登录 · 发表于 2011-3-16 09:59

看看别人在研究什么。什么优先级，时间片……

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

本帖子中包含更多资源

本帖子中包含更多资源

评分

评分

评分

评分

评分

本帖子中包含更多资源

浏览过的版块

社区建设奖章

甘甜之泉水

以坛为家

技术高手奖章

核心会员奖章

技术奇才奖章

七世轮回

坚毅之洋流

无冕之王奖章

十世金身

沉静之湖泊

荣誉元老奖章

技术领袖奖章

偶尔光临