V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
movq
V2EX  ›  程序员

哲学家就餐问题的一个解法

  •  
  •   movq · 2023-02-17 20:45:42 +08:00 · 2196 次点击
    这是一个创建于 405 天前的主题,其中的信息可能已经有所发展或是发生改变。

    阻塞 lock 拿到一个筷子后,非阻塞 tryLock 另一个筷子。如果得不到,就把手里的筷子释放掉

    这样感觉也可以解决

    网上搜了下貌似没看到有人写这种解法?

    第 1 条附言  ·  2023-02-17 23:13:31 +08:00
    本帖不是表面楼主有什么“重大发现”,只是看了 Wikipedia 和 Google 的一些搜索结果的具体例子,说得比较多的几个例子不包括楼主说的这个,所以想问下大家对这种解法有什么看法
    28 条回复    2023-02-18 23:21:44 +08:00
    bxb100
        1
    bxb100  
       2023-02-17 21:01:55 +08:00   ❤️ 3
    有没有种可能死锁之外还有个叫活锁的概念
    dcsuibian
        2
    dcsuibian  
       2023-02-17 21:37:29 +08:00
    早就有人说了吧。
    死锁的四个条件:禁止抢占、持有和等待、互斥、循环等待
    这不就是破坏“持有和等待”么?
    lessMonologue
        3
    lessMonologue  
       2023-02-17 22:11:11 +08:00
    。。。。。
    如果每个人同时拥有一个筷子呢?
    xyjincan
        4
    xyjincan  
       2023-02-17 22:12:49 +08:00
    死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。死锁需要必要的条件才能产生,下面为大家介绍死锁的四个必要条件。

    产生死锁的四个必要条件

       1 、互斥条件:一个资源每次只能被一个进程使用;

       2 、请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放;

       3 、不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺;

       4 、循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系;

    这个相当于放弃 2 这个必要条件
    shawnsh
        5
    shawnsh  
       2023-02-17 22:16:20 +08:00 via Android
    @bxb100 当然有活锁了。只消耗 CPU ,不干事情。比死锁更消耗资源
    hhjswf
        6
    hhjswf  
       2023-02-17 22:23:29 +08:00 via Android
    这都主动释放锁还谈死锁有什么意思
    movq
        7
    movq  
    OP
       2023-02-17 22:44:44 +08:00 via iPhone
    @lessMonologue 拥有一个筷子拿不到别的不就释放了吗,这样别的线程就可以拿到了
    movq
        8
    movq  
    OP
       2023-02-17 22:46:45 +08:00 via iPhone
    @bxb100 没抢到锁就设置随机睡眠时间应该可以吧
    movq
        9
    movq  
    OP
       2023-02-17 22:48:35 +08:00 via iPhone
    @dcsuibian 你说的这个几个条件属于比较抽象的,我看了下 Wikipedia 和 Google 头几条,具体的例子里面貌似没人提到这个,就来问下大家什么看法
    lessMonologue
        10
    lessMonologue  
       2023-02-17 22:49:36 +08:00
    @movq 那如果这个拿起-阻塞-释放的过程一直在持续下去呢? 如果你设置的随机睡眠时间,每一次都相同呢?
    movq
        11
    movq  
    OP
       2023-02-17 22:53:18 +08:00 via iPhone
    @shawnsh 感觉活锁的危害性是没死锁大的。如果进入了死锁,除非杀掉某个线程,不然解决不了问题。而活锁属于概率性问题。CPU 调度线程往往不会这么凑巧。调度差几个时钟周期就可以跳出活锁。应该不会持续太久。
    movq
        12
    movq  
    OP
       2023-02-17 22:54:29 +08:00
    @lessMonologue 为什么我设置的随机睡眠时间会每次都相同呢?那这个只能问是不是有这么弱的标准随机数库了
    lessMonologue
        13
    lessMonologue  
       2023-02-17 22:57:14 +08:00
    @movq 恰恰相反。准确来说,应该是“无法稳定复现但常常出现的活锁问题比死锁更为严重”。解决死锁只需要破坏 4 个条件之一,而能写出存在活锁现象代码的人,根本不会考虑随机时间的问题。
    movq
        14
    movq  
    OP
       2023-02-17 23:04:31 +08:00
    @lessMonologue 你的主张比较牵强
    movq
        15
    movq  
    OP
       2023-02-17 23:11:56 +08:00
    @lessMonologue

    你一边声称「懂得怎么避免死锁的人可以避免死锁」,然后又说「不懂活锁现象的人考虑不到随机时间」。

    逻辑漏洞太多:
    1. 这两句话跟活锁死锁哪个更严重根本就毫无关联。
    2. 前后两句话本身也毫无关联,不懂在一起说想表达什么。

    对 2 的证明:
    「懂得怎么避免死锁的人可以避免死锁」,并不能否定「懂得怎么避免活锁的人也会考虑到随机时间」

    对 1 的证明:
    懂不懂得死锁活锁,只是一个专业知识的问题,和活锁死锁哪个严重,毫无关联,是在偏离讨论的问题。
    movq
        16
    movq  
    OP
       2023-02-17 23:15:48 +08:00
    @lessMonologue 这么说吧,不知道你哪来的莫名的优越感。

    一开始你根本没看懂我在说什么,就打几个逗号表示无语,说每个人拿个筷子就能反驳我这种做法。结果反而让自己成了小丑。

    后来又强行说什么「如果随机事件恰好相同呢?」这种脑残假设

    我反驳之后又来信口开河说什么“恰好相反”,结果你对你的主张的论证漏洞百出

    真是笑死人
    movq
        17
    movq  
    OP
       2023-02-17 23:20:16 +08:00
    我总结一下死锁和活锁的对比,以下来自于《 C++ Concurrency in Action 》

    1.死锁没法救活,除非编程时就避免。这一点活锁有优势,因为活锁就算你编程时不避免,由于 CPU 的调度存在一定的偏差,也有可能可以自行脱离活锁。(可以看引用的“not-so-serious cases”)
    2.死锁发生时因为是等待,所以不会自旋,不占 CPU ,这方面是比活锁好的。


    > Deadlock - As you saw in chapter 3, in the case of deadlock, one thread is waiting for another, which is in turn waiting for the first. If your threads deadlock, the tasks they're supposed to be doing won't get done. In the most visible cases, one of the threads involved is the thread responsible for the user interface, in which case the interface will cease to respond. In other cases, the interface will remain responsive, but some required tasks won't complete, such as a search not returning or a document not printing.

    > Livelock - Livelock is similar to deadlock in that one thread is waiting for another, which is in turn waiting for the first. The key difference here is that the wait is not a blocking wait but an active checking loop, such as a spin lock. In serious cases, the symptoms are the same as deadlock (the app doesn't make any progress), except that the CPu usage is high because threads are still running but blocking each other. In not-so-serious cases, the livelock will eventually resolve because of the random scheduling, but there will be a long delay in the task that got livelocked, with a high CPU usage during that delay.
    Nerv
        18
    Nerv  
       2023-02-17 23:38:29 +08:00
    死锁的四个条件维基百科不是明明白白的给列出来了吗。这种操作浪费计算资源,同时要考虑到如果对第一只“筷子”做出了修改,还需要进行相应的恢复流程。
    这种在计算机发展初期就有的大问题,肯定是被大佬们研究烂了,思而不学不可取。
    movq
        19
    movq  
    OP
       2023-02-17 23:45:50 +08:00
    @Nerv 来 v 站发帖不就是为了看大家意见从而学习吗?光思考的话为什么要发帖子呢?我认为自己是对的不就行了
    movq
        20
    movq  
    OP
       2023-02-17 23:46:47 +08:00
    @Nerv 那你的意思是对凡是已经有定论的的东西都绝对不要提出个人想法是么
    Nerv
        21
    Nerv  
       2023-02-17 23:58:01 +08:00
    @movq 那我只能说以你这种学习方式不大可能真的取得什么进展。
    lessMonologue
        22
    lessMonologue  
       2023-02-18 00:08:53 +08:00
    @movq
    随手打了几个句号没想到你反应这么大。

    你说我有莫名的优越感,我根本就不知道你所说的“莫名优越感”我在哪里体现出来了?难道是因为 #10 这句话吗?那我是在认真的告诉你那句话是我基于经验说的话,可能在你看来有些莫名其妙,但你还不配让我用我的知识来嘲讽你。

    #12 楼的爆笑“逻辑判断”言论让人笑掉大牙。你不如去研究语言学?

    最后,你先分清楚你在研究计算机科学还是在研究计算机工程学。
    WuSiYu
        23
    WuSiYu  
       2023-02-18 00:21:19 +08:00
    单看你这种算法是可以工作的,但其实和一般讨论哲学家进餐问题时不是一个语境。

    你这种算法算是一种自旋锁,假设一个哲学家 trylock 的那个筷子在较长时间内都有人在使用,那么期间它就会重复 [阻塞 lock 拿到一个筷子 - 非阻塞 tryLock 另一个筷子 - 得不到 - 释放掉] 的循环,会耗费很多 CPU 时间;

    一般在 OS 课上我们讨论哲学家进餐问题时,只会允许算法使用信号量,也就是阻塞式的锁,在等待的时间中线程会切出去,不占用 CPU 时间。而自旋锁的实现并不在讨论的范围中。
    movq
        24
    movq  
    OP
       2023-02-18 08:15:43 +08:00 via iPhone
    @lessMonologue 笑死人,已 block😁
    ccagml
        25
    ccagml  
       2023-02-18 09:40:28 +08:00 via Android
    互斥条件、请求与保持条件 、不剥夺条件、循环等待条件,
    如果先锁筷子 1 ,有了筷子 1 再锁筷子 2 ,这算是破坏循环等待条件吗?
    yankebupt
        26
    yankebupt  
       2023-02-18 14:53:05 +08:00
    樓主説錯了一個步驟,但我是知道他怎麽想的
    鎖桌子,拿筷子 1 ,如果被筷子被鎖了,左邊人在吃飯,放棄,如果右邊筷子被鎖了,右邊人在吃飯,放棄,同時(桌子鎖内)拿起兩雙筷子,鎖筷子,解桌子。已經在吃的人不看桌子
    更大粒度的沒性能鎖永遠解決問題(但這基本就是個排隊),但這個比更大粒度好一點點,因爲不影響已經在吃的人。
    movq
        27
    movq  
    OP
       2023-02-18 15:27:35 +08:00
    @yankebupt

    你说的这个是你自己想的吧。我的意思是第一个筷子先阻塞式锁,第二个筷子非阻塞锁。你的说法是第一个筷子也非阻塞锁。

    不过感觉先锁桌子,然后左右 tryLock 也是可以的。
    hxndg
        28
    hxndg  
       2023-02-18 23:21:44 +08:00
    没看明白上面在争吵什么,这个我印象中计算机教材应该讲过“哲学家就餐”,而且附录应该是有 lz 提到的解法
    教材很多年前看的,不记得了。

    不过 wiki 上应该有这种解法,一般来说是不会将这种确定性问题交给随机性来解决的

    有一点可能要注意,死锁活锁是针对锁而言的,和通用概念的“死锁”可能不一致
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   930 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 20:55 · PVG 04:55 · LAX 13:55 · JFK 16:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.