PK 使人进步：highgear 向网友刘前辈提出很简单的切磋请求

发表于 2011-10-17 21:15

老刘啊，请在此讨论“哲学家就餐”:
https://bbs.21ic.com/viewthread.php?tid=224063&highlight=%E5%93%B2%E5%AD%A6%E5%AE%B6

这个帖子，你可以讨论三角函数的数字实现，或是接受 PK.

发表于 2011-10-17 21:43

本帖最后由刘前辈于 2011-10-17 21:45 编辑

哈哈，90#信箱已经发出了。

就算写的不怎么样，毕竟是第一个写出来的。很多人看了心里都冒酸水，那个醋劲：“那么差的玩意也要……”

哈……想当年，Dijkstra 第一个想出的信号量机制不过是个整型量，可以记录丢失的信号而已，——这件事促进了世界长期静止不前的OS 领域研究的快速发展，这篇论文被载入OS发展史册了。如今看：不带等待队列的简单信号量简直就是少儿科，连初中生都能想出来。

——可惜，那么多OS研究大师，那么多年就是没想出来，Dijkstra 第一个想出来了，然后所有OS研究大师都恍然大悟：“这么简单的机制，我怎么就没想到呢……”然后冒出一大堆更高明，完善的“类信号量”。个个都比Dijkstra 聪明。——有什么用啊，千年老二！谁知道第二个登上月球的人是谁？

所长，算了吧。你的BIOS 代码还要等到猴年？即使你现在贴出你的代码，也是千年老二啦……
红眼病又犯了……，没用啊……

、、

发表于 2011-10-17 21:58

老刘啊，你的弱智在 101 楼又再次体现，搞的好像 Dijkstra 就是你老刘似的。

懂不懂 OS, 用 PK 说话。很简单，老刘你只要在下面选择一个：
1）接受 PK
2) 不接受

发表于 2011-10-17 22:02

这江湖恩怨好几年了啊。
卷入这战争的不少啊
不过有战争就是好竞争才能进步。

发表于 2011-10-17 22:07

97#
老刘，不是我瞧不起你(们），总是拿着一些小儿科的东西出来炫耀，被不断打脸就是活该了。你想玩“哲学家就餐“，先去掂量我做的两个程序，想玩“LED", 先把以前的PK完成，我的程序都是公开的：
https://bbs.21ic.com/viewthread.php?tid=52070&highlight=
https://bbs.21ic.com/viewthread.php?tid=43825&highlight=

哈哈，所长真逗，写了2个裸奔喂猪程序也算是玩“哲学家就餐”？

首先，你的程序不是在OS平台上完成的，是纯粹的裸奔程序，没学过OS的任何人都能写出来。

告诉你一个基本概念：哲学家就餐经典问题是多任务并发问题，——5道并发。

你写8个喂猪程序也不过是在那玩单道程序。风牛马不相及，差远啦…… 这么大年纪，再学多道并发也来不及了，还是跟HOT大叔学学，HOT大叔知道研究OS，所长就不醒悟。
还在那里抱着“OS 能做到的，我裸奔也能做到。”不放。愚呀……

编了2个喂猪程序，连个输出显示都没有。也跟老刘学学，用LED灯表示一下自己想说什么。屏幕上显示一下也行呀，编了一辈子裸奔程序，printf 总会玩吧。也打个包让众人下载来看看，你做的是什么东西。
把哲学家怎么喂成猪的。

、、

发表于 2011-10-17 22:12

呵呵，这个论坛上没有了刘前辈，就不好玩了。其实，我也很怕这个刘前辈不来了，这样这个论坛就没有什么意思了。

发表于 2011-10-17 22:28

老刘，说你的技术水平低， 104楼可见一斑。我的那两个程序使用了多线程
你老刘不知道什么是多线程，对吧？
至于输出显示？呵呵，可见你老刘水平之低。还是我来告诉你，那个程序是 Console 程序，使用的是 DOS 窗口。

发表于 2011-10-17 22:43

我明白了，难怪这个老刘**不懈的提及什么“哲学家”，原来是老刘的水平根本就看不懂，理解不了我所作的多线程程序，以为在这个上面能捞回点面子。不过这个“哲学家就餐”问题实在太简单了，做不了 PK 的题目。

发表于 2011-10-18 08:27

本帖最后由刘前辈于 2011-10-18 09:37 编辑

106#highgear
至于输出显示？呵呵，可见你老刘水平之低。还是我来告诉你，那个程序是 Console 程序，使用的是 DOS 窗口。

哈，highgear所长一开口就露怯：自己这边PK的题目是“独立完成一个最基本的多任务操作系统，……” 那边又拿Console 多线程到这边来说事！多线程平台是你自己独立完成的？你到底想PK什么，自己都忘了自己想干嘛了。

   首先重要的是，不管你玩的是多线程还是路由器，你把你的程序输出显示出来给大家看看，把程序员自己编的程序所要表达的意思最后用几个简单的显示灯表达出来，是一个程序员的基本能力；否则，谁知道你的程序想干什么？！达不到正确输出的目的，一堆乱码，错在哪都不知道。玩什么？
         你不是计算密集型程序，（计算密集也要输出显示啊。）你这的控制输出是5个哲学家的行为。即使你用的是Console ，DOS窗口，不也得显示输出行为结果么。——你的DOS窗口难道还不如KEIl的简单输出窗口？还不如单片机输出的几个灯的能力？怎么微软风靡世界的DOS 到你手里就连清屏，定位显示几个亮点都不行啦？

      要不要老刘教教你怎么在DOS窗口里显示5个灯亮/灭？玩了几十年DOS，不会连这么点技巧都不知道吧。——至少可以跟圈圈版主学学怎么在屏幕上转显示的，哈……

   唉，所长的脑力真是越来越退化了 ……跟你交流很困难。

   问个简单的问题，所长就头大：多线程是多道并发么？5 道并发你来个5线程。

     还有啦：LZ要求PK题目是：

独立完成一个最基本的多任务操作系统，并在此 os 上解决哲学家就餐问题

独立自己写一个简单的OS……，怎么所长玩起了Console ，DOS？哈……Console 是你所长写的？DOS是你所长独立写的？切！要不要脸。不合题意耶！自我矛盾。——输急眼了，顾不得自己打自己的脸。自创的“寒冰大fa”也使出来了，——阴招！大概下面又要用MINIUNIX了。
      唉，自己先认输得了。

      俺写的test2S2.C ，所有代码均是自己写的，（除了库函数调用）代码长度 17K。
      所长的代码长度方便公开一下？70K还是170K还是……。——如若小于17K，（还有内存量），俺老刘就认输。（我最简功能代码长度是 1104字节）。——你的Console 属于安装第三方软件，自己的PK题目都忘啦，是不是准备下面要用MINIUNIX继续玩？

         唉！还玩什么呀，什么事转眼就忘，老糊涂了。

、、

发表于 2011-10-18 10:12

本帖最后由刘前辈于 2011-10-18 10:29 编辑

#97 highgear
老刘，不是我瞧不起你(们），总是拿着一些小儿科的东西出来炫耀，

所长老人家真是健忘，是你老人家在LZ 找老刘PK 哲学家就餐这些小儿科的东西出来炫耀，俺只是被动接招而已。（老刘从来没有在论坛上主动开贴讨论过这些OS经典问题，仗着自己比所长学历高，忽悠本科生所长？俺没那么逊。俺周围博士多着呢，知道自卑的滋味。）

是你在LZ开的哲学家就餐讨论贴出来想炫耀自己，自己开的帖子自己又忘了，骂自己小儿科了。——提醒一下：俺有个亲戚，开始症状和你一样，就是健忘，发展很快，健忘时间越来越短，刚到解放军30X医院检查确诊：老年痴呆症。也是不到60岁的人。建议所长尽快到医院检查一下，医生说，发现得越早越可能制止发展。

我没有恶意。否则你6号开的帖子，怎么不到 3 天又忘了PK内容，转而自己攻击自己呢。——不是什么行为都会引人发笑，过于反常的行为让人理解为病态行为，通常不会发笑，只会产生对病人的同情、怜惜……

、、

发表于 2011-10-18 15:15

图帮你改了，也就两三分钟的事儿，100大洋就不必了，虽然俺比较穷，但赚这钱太没挑战了，有损我DownCloud大侠的风范呀、、、

发表于 2011-10-18 20:51

顶顶 DownCloud 这个认真好学的大侠。

老刘啊，去看看104楼引用的连接里PK的内容，以及我给出的C51, VC++, C#, VB 的程序，LED 的闪烁也只不过是小得不能再小的问题了，”哲学家就餐“也是如此，作为本科生的论文都勉强。

老刘你的帖子我就不多说了，108，109楼所表现出来的弱智，大家心里都明白是怎么回事。
此帖越来越无聊了，算了，反正老刘是死活也不肯PK, 我也不再逼迫老刘。老刘你什么时候想PK了，通知我就可以了，这个帖子我就不奉陪了。

发表于 2011-10-19 06:07

顶highgear老师，确实越来越无聊了，俺出个小题目，看二姨家有几个大虾能答对算~~~

先回忆一下《哲学家就餐问题》，下面回答引自维基百科全书。

----------------------------------------------------------------------------------------------------------------

哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步(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）争用任意数量的资源。与迪科斯彻的解法不同的是[来源请求]，这里编号可以是任意的。

对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。
这个解法允许很大的并行性，适用于任意大的问题。

发表于 2011-10-19 06:15

俺出的小题目就是：

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

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

上面写到，在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。

那么，著名的计算机科学家艾兹格·迪科斯彻肯定有自己的《哲学家就餐问题》之解法，请简单描述一下艾兹格·迪科斯彻之解法。

登录 · 发表于 2011-10-19 19:10

顶112楼Cortex-M0 ，描述很详细，都是世界级OS 大师想出来的方法。我下面的实验是结合Dijkstra 和Chandy/Misra 解法，其实1971年以后的解法都是在Dijkstra 的解法技术上的变形；Dijkstra 的解法很精彩，不是一般人能想出来的。即使看了源代码，也不一定当时就能看懂。虽然也是C语言写的。

我实验的是7个哲学家，其实Dijkstra 基本方法也可以是任意多个哲学家，只是5个就足够说明概念了。我因为P1口只有8个灯，其实9个、11个，2N+1个，随便的，越多约为眼花缭乱了。

Cortex-M0 · 发表于 2011-10-19 21:19

顶123姐姐的资料。

哈哈，老刘，不是我打击你，114楼纯属笑话。

123姐姐，Dijkstra的解法以及源代码在《Modern Operating Systems》一书中的 127 页，
https://bbs.21ic.com/viewthread.php?tid=224063&extra=&highlight=%E5%93%B2%E5%AD%A6%E5%AE%B6&page=5
我给出的两个C#的源程序，当时并没有参考任何别人的解法，仅凭自己的经验作出，这并不是说明我水平高，而是说明在计算机技术飞速发展的今天，当年的这些问题都已经变成很小的问题了，而当年高山仰止的大型计算机，性能还不如我的手机。

这个楼太高了，已经不适合讨论，恳请123姐姐新开一楼。

发表于 2011-10-19 22:09

谢谢highgear老师~~~

Dijkstra的解法以及源代码上次您已贴出，已拜读过，写的真好，天才之作啊，感叹现在还不落伍~~~

今天又重温拜读了一遍 Dijkstra的天才解法。

发表于 2011-10-19 22:17

123姐姐不用客气。

发表于 2011-10-20 03:14

哈哈，PK让人进步~~~

下面是HotISP V2.65B
腾讯微群(入群密码：250)：
http://t.qq.com/download.php?fkey=/7b99e7fa-46b7-4842-8998-ffad25ff7076&qid=78184763&ftype=2

新浪微群(入群密码：250)：
http://q.weibo.com/316539/file/13960456

需要PK的拿BIN或HEX转成汇编的A51文件~~~

disasm51是俺20年前的构思，俺认为还不落伍。
若俺被PK了，俺会改进算法继续PPKK~~~

HotISP内嵌的超级反汇编disasm51.exe(V5.08)是一个控制台程序。
它可以独立运行，也可以被任何采用控制台回显技术的软件调用。

例如:
disasm51.exe a51demo
disasm51.exe a51demo.bin
disasm51.exe a51demo.bin a51demo
disasm51.exe a51demo.bin a51demo.a51
disasm51.exe a51demo.bin a51demo.asm

发表于 2011-12-5 20:33

本帖最后由刘前辈于 2011-12-5 20:51 编辑

LZ所长这次终于先动手了，写了一个漂亮的OS奥秘——调度器。想表示一下，俺不是不懂OS。

结果，落荒而逃，没有结论了。——自己写的2个任务，输出窗口连个影都没有！——LZ还想用这个调度器玩哲学家就餐？！梦话。——那么，自己都玩不出的技术，拿出来和别人PK？然后假模假式装相“谅你也不敢……”；这是所长的一贯做法，好像自己早就懂了似地。哈哈，下次PK，跟老刘学学，挑战者先来。——让所长先来，就露大怯了，—— 原来自己都不懂！还假惺惺找人PK？鼻子里插葱，嘎嘎。

上文备份了15个字节，下文恢复6个字节！——牛头不对马嘴，按网友的话说，“第一次中断进入，程序就不知道跑哪去了。”

露怯呀。做了一辈子软件的人。还以自诩C++，C#，JAVA什么都会来嘲笑别人，以后恐怕再也不敢和谁“切磋”OS了。

哈哈……这倒给老刘一个露脸的机会，让LZ所长见识一下老刘怎么在你写的，到处BUG，没有输出的所谓OS大揭秘调度器上玩哲学家就餐的！——你自己已经认输玩不出来了吧，3个星期都没把自己的BUG修改好，就算放弃了吧。——轮到老刘啦！看老刘怎么给你修改的，怎么在其上玩哲学家就餐的；在你自己写的调度器上实现哲学家就餐，你无话可说了吧。
      哈哈……

高兴了再让所长老爷子见识一下老刘怎么在你写的调度器上实现20个任务的。你撑死只能玩8个任务？结果怪“51这种结构不适合玩OS……”

   你不会玩就别找原因，给自己下台阶。别人怎么就能玩？玩20个任务还有余地。——老刘让你见识见识，开开老眼。

   所以，送LZ所长一句话：你自己不懂的事情，并不表示别人可笑。——只怪自己无知罢了

、、

PK 使人进步：highgear 向网友刘前辈提出很简单的切磋请求

本帖子中包含更多资源

评分

浏览过的版块

核心会员奖章

坚毅之洋流

七世轮回

技术高手奖章

社区建设奖章

以坛为家

欢快之小溪

技术奇才奖章