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

我们来为“死锁的四个必要条件”加一条

  •  
  •   gantleman ·
    gantleman · 2020-07-26 09:13:39 +08:00 · 10006 次点击
    这是一个创建于 1582 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我们都知道多线程下必须要彻底解决死锁的问题。因为死锁是无法使用常规测试手段发现的,并且在项目运行中随机出现导致软件拒绝服务的一级 BUG 。

    死锁问题是由 E. G. Coffman,M. J. Elphick,A. Shoshani 在 1971 年的论文“System Deadlocks”提出的。并且给出了知名的4种解决方式,被称为“死锁的四个必要条件”。

    原文如下为: “

    This deadlock situation has arisen only because all of the following general conditions were operative:

    1. Tasks claim exclusive control of the resources they require ("mutual exclusion" condition).
    2. Tasks hold resources already allocated to them while waiting for additional resources ("wait for" condition).
    3. Resources cannot be forcibly removed from the tasks holding them until the resources are used to completion ("no preemption" condition).
    4. A circular chain of tasks exists, such that each task holds one or more resources that are being requested by the next task in the chain ("circular wait" condition).”

    互斥条件:一个资源每次只能被一个任务使用。 请求和保持条件:一个任务因为请求资源而阻塞时,对已获得的资源保持不放。 不剥夺条件:任务已经获得的资源在没有使用完之前,不能强行剥夺。 循环等待条件:若干任务之间形成一种头尾相接的循环等待资源关系。

    这4个必要条件做了一个隐含假设的条件,就是 task 是必须运行在不同的线程或进程中。 哪么这个隐含假设如果不成立,死锁也必然不会发生。所以4个必要条件中缺乏1个隐含的必要条件。 task 之间必须是并行才会发生死锁。

    假设两个运行在不同线程或进程中的 task 会因为两个 resources 发生死锁。如果将两个 task 放在一个线程或进程中依次执行,哪么死锁也不会发生。

    这就给了我一个新的启发,如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。

    关注项目  github.com/surparallel/pelagia  发现一些不同的并行计算的知识。

    第 1 条附言  ·  2020-07-26 09:56:59 +08:00
    如果我的理论是错误的,那么必然写不出 pelagia 。因为这是 pelagia 的理论基石之一。是不是偷换概念欺世盗名就让代码去说话吧。
    第 2 条附言  ·  2020-07-27 14:00:28 +08:00
    ysmood 14 小时 29 分钟前 ❤️ 1
    @gantleman 我只是想表达这个问题跟线程没有关系,单线程也可以 mutex 嵌套阻塞。很好奇单线程是如何防止我故意 mutex 嵌套阻塞的。并没有说你解决问题的过程有问题,只是觉得可能表达的方式让大家容易不太容易接受。比如你扔一个项目地址,然而我看了半天文档,却感觉很难跟你说的关联起来。

    能简单介绍下 pelagia 的工作原理就好了。目前我稍微看了

    gantleman 9 小时 39 分钟前
    @ysmood 考虑对性能的榨取,阿达姆尔定律是多线程的上限,那么死锁就是多线程的下限。只有上下限都确定了,才能正确的使用多线程。死锁的问题在于其随机性无法通过简单测试就能发现,最终导致软件产品在不断升级
    第 3 条附言  ·  2020-07-27 14:01:57 +08:00
    gantleman 9 小时 39 分钟前
    @ysmood 考虑对性能的榨取,阿达姆尔定律是多线程的上限,那么死锁就是多线程的下限。只有上下限都确定了,才能正确的使用多线程。死锁的问题在于其随机性无法通过简单测试就能发现,最终导致软件产品在不断升级的过程中走向不可控。pelagia 的意义在于通过一系列的规则让不可控的下限在开发过程中就能被发现。这样就把不可控变成了可控。在完全可控的前提下才能追求极致,去压榨多线程的上限效率。
    第 4 条附言  ·  2020-07-28 13:39:20 +08:00
    /*****************************************************
    帖子引起了一些争议,我不会再对这个帖子做任何的回复。
    希望帖子里的各种观点对需要解决死锁和多线程的问题有所帮助。
    *****************************************************/
    84 条回复    2020-07-29 19:40:04 +08:00
    cmqwan
        1
    cmqwan  
       2020-07-26 09:22:26 +08:00 via iPhone   ❤️ 9
    总结下:

    “我们都知道多线程下必须要彻底解决死锁的问题。”

    “这就给了我一个新的启发,如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。”
    codehz
        2
    codehz  
       2020-07-26 09:23:49 +08:00
    你这不就相当于给潜在发生死锁的任务加了个大锁么。。
    gantleman
        3
    gantleman  
    OP
       2020-07-26 09:30:13 +08:00
    @codehz 准确的说是在无数个任务中找到可能死锁的任务,并将每组可能死锁的任务都放入一个线程。所以不是一个大锁,是无数个分组的锁。
    gantleman
        4
    gantleman  
    OP
       2020-07-26 09:31:42 +08:00
    @cmqwan 人如其名的 帅
    binux
        5
    binux  
       2020-07-26 09:32:40 +08:00 via Android
    > 这就给了我一个新的启发,如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。

    如果你的意思是将 task 放在一个线程中打破条件 4,那么你就违反了条件 1 。
    gantleman
        6
    gantleman  
    OP
       2020-07-26 09:35:40 +08:00
    @binux 套娃啦,这不是一个层面的问题
    binux
        7
    binux  
       2020-07-26 09:40:34 +08:00   ❤️ 3
    @gantleman 那是因为你在偷换概念。
    条件一是说 resources 是 exclusive 于 task 的,然而你给一个任务起名叫做 task,但是 resources 却是 exclusive 于线程中的。所以你违反了条件 1
    否则,即使你将他们重新放回到一个线程中,由于 resources 是 exclusive 于 task 的,它们还是死锁的。
    lance6716
        8
    lance6716  
       2020-07-26 09:45:26 +08:00 via Android   ❤️ 4
    全部串行,解决死锁问题
    gantleman
        9
    gantleman  
    OP
       2020-07-26 09:52:39 +08:00
    @binux 如果我的理论是错误的,那么必然写不出 pelagia 呀。因为这是 pelagia 的理论基石之一。是不是偷换概念欺世盗名就让代码去说话吧。
    binux
        10
    binux  
       2020-07-26 10:00:39 +08:00
    @gantleman 只要通过阻断 “死锁的四个必要条件” 中任意一个就不会死锁,你写的 pelagia 也是如此。而不是你所谓的加一条。
    WangRicky
        11
    WangRicky  
       2020-07-26 10:04:28 +08:00
    这个隐含条件,恰恰是讨论死锁问题的前提,你推翻了这个前提,把死锁的问题放回了同一个线程中,死锁问题当然被你彻底解决了
    vindurriel
        12
    vindurriel  
       2020-07-26 10:12:14 +08:00 via iPhone
    这 4 个条件里 前三个说的其实是锁 第四个才是死锁
    所谓 task 的粒度 其实是 db connection 任务放一个 process / thread 里可以打破 4 的前提是 在同个 process / thread 里只开一个 db connection
    如果工作都能放一个 connection 里 那连锁都不用了 更不会出现死锁 但现实是 这样的系统吞吐量不够 也不结实
    gantleman
        13
    gantleman  
    OP
       2020-07-26 10:16:41 +08:00
    @WangRicky 如果你有 100 个任务,其中 2 个任务死锁。把这两个任务单独放到你个线程里,剩下 98 个任务分别放的 98 个线程里。对于剩下 98 个任务死锁就不是问题吗?我没有否定线程,我只是否定有死锁条件的线程。我没有说有 2 个任务死锁,剩下的 98 个任务就不分线程。
    PopRain
        14
    PopRain  
       2020-07-26 10:18:51 +08:00
    对于复杂系统,发现“潜在的死锁”基本不可能,如果能发现,那就可以用顺序访问解决了。。。。
    gantleman
        15
    gantleman  
    OP
       2020-07-26 10:23:39 +08:00
    @PopRain 先不要急着说不可能,顺序访问只是解决方法之一。有了消息队列和线程池后系统环境和当时写论文的情景已经完全不同了。
    lance6716
        16
    lance6716  
       2020-07-26 10:25:16 +08:00 via Android   ❤️ 1
    @gantleman 人家那 2 个任务明明能通过其他方式检测、避免死锁,整个的放在一起不是减少效率吗

    而且很多任务要获取的锁是不能静态分析的,那就按照“最大范围获取锁”去处理吗
    gantleman
        17
    gantleman  
    OP
       2020-07-26 10:28:35 +08:00
    @lance6716 你的意思是减少效率和死锁二选一?我认为多线程应用死锁是必须解决的不是二选一。静态分析不是不可能,静态分析是有前提条件的。
    AlexaZhou
        18
    AlexaZhou  
       2020-07-26 10:32:07 +08:00
    比较可行的方法,是确保用一致的顺序来加锁,这样肯定不会死锁
    flyingsheep123
        19
    flyingsheep123  
       2020-07-26 10:33:30 +08:00
    并发导致死锁,消灭并发就消灭死锁,串行万岁!
    whileFalse
        20
    whileFalse  
       2020-07-26 10:35:09 +08:00
    你说的是对的,帮你重新表达下会更清晰:

    “已经完成的 task 不会和当前正在执行的 task 之间形成死锁”

    听起来是不是正确的废话?
    lance6716
        21
    lance6716  
       2020-07-26 10:35:24 +08:00 via Android   ❤️ 1
    @gantleman 有很多死锁检测和死锁避免算法,我觉得他们比起“合并任务减少并行度”更不影响效率,不知道你这个方法有什么优势

    另外也不知道你这个方法如何合并任务,请给个具体例子。
    比如任务 ABC 根据用户输入不同使用相同或者不同的资源,你这个方法是不是 ABC 按照最坏情况考虑,一定会串行处理
    Akiyu
        22
    Akiyu  
       2020-07-26 10:51:51 +08:00   ❤️ 2
    是的, 按照你说的, 的确可以规避死锁.
    极端情况, 比如说只有两个线程执行两个任务, 当冲突的时候, 将两个任务放到一个线程中.
    这当然可以规避死锁(都只有一个任务了!).

    但显而易见有些缺陷和矛盾, 一是和本身多线程的想法有点冲突, 二是任务的粒度加大, 并发性进一步降低.
    多线程是串行转并行, 为了提高效率. 但按你这么说, 反而并行转回串行(虽然是部分, 但的确有).
    和本身引入多线程技术的想法冲突了. 而且, 将两个任务合并为一个任务, 这样任务的粒度就会变大. 并发性再次减少.
    考虑一下这种情况: A 和 B 冲突, AB 合并(合并后, 该任务执行时间必定加长), 如果一种比较糟糕的情况出现了, 比如出现了 C 任务, 他和 AB 冲突了. 这种情况怎么办? 再次合并么?
    719465553
        23
    719465553  
       2020-07-26 11:18:10 +08:00
    什么脑回路,单进程,就不会死锁,这个意思?死锁的四个条件你认真理解了吗。如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。同一个线程,也只是降低资源互斥的可能性,还有跨进程的问题
    gantleman
        24
    gantleman  
    OP
       2020-07-26 11:26:52 +08:00
    @Akiyu 是的没错,打开了一个新世界的大门了吧!任务不光可以拆分还能合并。很多技术细节没办法在一个帖子说清楚的。以后想到什么慢慢说吧。
    momocraft
        25
    momocraft  
       2020-07-26 11:29:00 +08:00
    第一次看了原文

    有限的 cpu, 即导致线程不能同时前进的那个东西, 在原文被分类为资源.
    liuminghao233
        26
    liuminghao233  
       2020-07-26 12:18:57 +08:00 via iPhone
    “多线程下必须要彻底解决死锁的问题”


    总结一下:
    A B 两个 task 在多线程下会出现死锁
    怎么解决?
    那就不用多线程。
    jinliming2
        27
    jinliming2  
       2020-07-26 12:46:11 +08:00
    我的理解,你自己加的这个“隐含假设的条件”不对,多线程并不是死锁的条件,单线程下依旧会出现死锁。
    只不过实际开发在单线程条件下,因为通常不会出现资源访问冲突,所以单线程开发是不会加锁的,也就不会死锁。
    但是,如果在单线程下使用了锁,那么如果资源获取、释放的顺序不对,也会产生死锁。也就是条件中的循环依赖,自己依赖自己。
    最简单的例子就是,对一个资源进行加锁访问,在没有释放的时候,再对其进行加锁。这符合四个条件。

    真实的情况可能会复杂一些,就是在多线程环境下,其中某一个线程出现了加锁、释放顺序不对的情况。
    Jooooooooo
        28
    Jooooooooo  
       2020-07-26 13:34:28 +08:00
    你这不是死锁问题

    是定义问题
    Jooooooooo
        29
    Jooooooooo  
       2020-07-26 13:35:55 +08:00
    另外别人在一个 50 年前论文提出的相当著名的东西, 一直都不被人认为是错误的.

    那么你认为他是错误并且可以证明, 那至少是值得重新写一篇论文而不是发 github
    mind3x
        30
    mind3x  
       2020-07-26 13:52:57 +08:00   ❤️ 2
    恭喜你重新发明了 coroutine
    kkbblzq
        31
    kkbblzq  
       2020-07-26 14:23:21 +08:00
    你以为解决问题的理论实际上并不是你的理论。。你这玩意都本质跟那些分段加锁其实没什么区别
    Mohanson
        32
    Mohanson  
       2020-07-26 14:56:51 +08:00 via Android
    死锁是代码逻辑有问题吧,我们应该修复逻辑 bug 而不是引入一个东西隐藏 bug
    luozic
        33
    luozic  
       2020-07-26 15:55:28 +08:00 via iPhone
    无并发,单线程跑?
    leimao
        34
    leimao  
       2020-07-26 15:56:05 +08:00
    我觉得 AsyncIO 基本就是这套路。
    leimao
        35
    leimao  
       2020-07-26 15:56:48 +08:00
    或者是结合 AysncIO 和 Thread 。但是这应该不是新的理念。
    leimao
        36
    leimao  
       2020-07-26 16:00:27 +08:00
    @Jooooooooo 看他意思也不是说前人是错的,他意思是在四个必要条件下,在得出一个推论出来的必要条件。但这个可能是 trivial 的 。
    gantleman
        37
    gantleman  
    OP
       2020-07-26 16:06:25 +08:00   ❤️ 3
    @kkbblzq 今天我轻描淡写的说出来,简单的不可思议。但我不光在理论上尝试解决这个问题,还写了一万字的论文和 4 万多行代码的工程和测试用例。我不是万能的,如果在并行计算有类似论文和解决方案也可以推荐给我。都是成年人了,请尽量让自己的回复能够对别人有帮助。
    leimao
        38
    leimao  
       2020-07-26 16:11:48 +08:00
    @gantleman 可以贴一下论文地址,这样有这方面背景的人可以深入了解一下。
    SingeeKing
        39
    SingeeKing  
       2020-07-26 16:22:54 +08:00
    「如果将两个 task 放在一个线程或进程中依次执行,哪么死锁也不会发生。」这明显忽略了不可重入锁啊……
    gantleman
        40
    gantleman  
    OP
       2020-07-26 18:33:06 +08:00
    @SingeeKing
    @jinliming2
    在单线程里死锁就失去可不可测试随机出现的条件。单线程被阻塞无论黑盒还是白盒跑一遍就发现了。写出有随机性质的需要一定的经验和技巧。
    MarshallMathers
        41
    MarshallMathers  
       2020-07-26 18:49:09 +08:00
    草草的看了一下,你知道协程吗?感觉就是协程的原理啊.
    Inn0Vat10n
        42
    Inn0Vat10n  
       2020-07-26 19:00:27 +08:00
    “如果将两个 task 放在一个线程或进程中依次执行,哪么死锁也不会发生” 这是错的,就算在一个线程里,如果满足这 4 个条件也照样会死锁。为什么有人会以为 coroutine 能解决死锁问题??
    gantleman
        43
    gantleman  
    OP
       2020-07-26 21:11:03 +08:00
    @Inn0Vat10n 在一个线程里每个任务的执行是连续非中断的。你假设的条件是第一个任务执行一半,然后执行第二个任务,然后再执行剩下一半。其实就变成任何锁只要锁了不释放都必然会阻塞。更准确的说只要嵌套请求锁就有可能因为嵌套的次序不同而阻塞。那么你就是在说 70 年论文对死锁的定义不严谨准确。那么你得到另一个有趣的结论。只要请求锁的嵌套次序都相同就不会死锁。所以循环嵌套也不是死锁的必然条件。

    你看好好讨论就会得到一些有趣的结论。这不你又发现了一些奇怪的知识。所以死锁究竟应该如何定义?
    ysmood
        44
    ysmood  
       2020-07-26 21:38:56 +08:00
    你说的多线程既不是充分条件也不是必要条件,就算不是多线程也是可以死锁的,就算是多线程也可以不死锁。很多单核 OS 也是可以模拟多线程的,那种 OS 的程序就不会死锁了吗?

    我倾向于广义的死锁,即等待一件永远不会发生的事。可以看到这个跟是否多线程,协程等没有任何关系。比如在程序里轮询等待一个变量被设置为 0,但是轮询的时候没有写这个变量,就不可能停止轮询,这部分代码就像是卡住了一样,单线程也是可以复现这种情况的。

    我觉得 4 个都有点多余了,还来第 5 个。其实可根据具体情况加无限个条件的,全看你怎么定义死锁,问题太宽泛以至于难以吊起人们的讨论欲望。
    crclz
        45
    crclz  
       2020-07-26 21:53:43 +08:00
    “这就给了我一个新的启发,如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。”

    这个方案的问题是:事务(上文的 task )不是放在一个任务列表中等待 DBMS 去处理的,而是经过数据库连接不断到来的。假如在某时刻 t1,一个任务到来了,你无法判断这个任务是否和其他即将到来的任务有冲突(因为未来的任务还没到来)。你有 2 条路可以选择:

    1. 等待一个时间Δt,累积一些任务,看看如何调度这些任务来使得死锁不发生。(你会浪费Δt,并且每个任务的响应时间 至少增加Δt )
    2. 两阶段锁协议。(被 DBMS 广泛采用)
    3. 单线程( LMAX Architecture )
    gantleman
        46
    gantleman  
    OP
       2020-07-26 22:17:58 +08:00
    @ysmood 虽然看样子你的思绪已经飘到了外太空,但我决定还是把你拉回来。
    这里锁的定义很明确就是 mutex,死锁的范围就是 mutex 嵌套使用的阻塞问题。
    更深的问题是涉及了嵌套次序和多层嵌套的问题。
    ysmood
        47
    ysmood  
       2020-07-26 23:28:05 +08:00   ❤️ 1
    @gantleman 我只是想表达这个问题跟线程没有关系,单线程也可以 mutex 嵌套阻塞。很好奇单线程是如何防止我故意 mutex 嵌套阻塞的。并没有说你解决问题的过程有问题,只是觉得可能表达的方式让大家容易不太容易接受。比如你扔一个项目地址,然而我看了半天文档,却感觉很难跟你说的关联起来。

    能简单介绍下 pelagia 的工作原理就好了。目前我稍微看了下,错了请指正。感觉就是把逻辑问题转嫁了而已,用户需要花更多的时间来思考如何把用锁能解决的问题转化为 job 调度问题,把问题提前解决了而已,感觉就是用库或语法辅助思考模式而已。
    future0906
        48
    future0906  
       2020-07-27 00:03:38 +08:00   ❤️ 1
    推广自己的项目总要一些吸引眼球的点,不过这样故作高深没什么用,不如直接引战说"C 语言是世界上最好的语言?"

    如果是 Actor 模型,的确是规避死锁的方法,代价是牺牲一致性。
    如果说你刚才描述的,"发现"潜在死锁再放同一个线程的,你如何“发现”。连发生死锁这件事你都检测不出来,还“潜在”?假设你真的能检测潜在死锁,完成这件事情(函数)需要 3 个资源,分别在 3 个线程?你如何分? 4 个资源? 5 个资源?

    这种无意义的推广帖我只回一次,恳请建议管理员移到:https://www.v2ex.com/go/ohno
    gantleman
        49
    gantleman  
    OP
       2020-07-27 04:08:45 +08:00
    @future0906 既然你都想到了静态分析很难,就说明你也发现原来定义的不严谨。
    gantleman
        50
    gantleman  
    OP
       2020-07-27 04:18:44 +08:00
    @ysmood 考虑对性能的榨取,阿达姆尔定律是多线程的上限,那么死锁就是多线程的下限。只有上下限都确定了,才能正确的使用多线程。死锁的问题在于其随机性无法通过简单测试就能发现,最终导致软件产品在不断升级的过程中走向不可控。pelagia 的意义在于通过一系列的规则让不可控的下限在开发过程中就能被发现。这样就把不可控变成了可控。在完全可控的前提下才能追求极致,去压榨多线程的上限效率。
    crclz
        51
    crclz  
       2020-07-27 08:23:05 +08:00
    在?为什么不回复我上面那楼?
    gantleman
        52
    gantleman  
    OP
       2020-07-27 08:32:30 +08:00
    @crclz 因为这个问题在多线程和多进程下表现出完全不同的性质。
    lyi4ng
        53
    lyi4ng  
       2020-07-27 11:26:06 +08:00
    "如果能发现两个 task 有潜在的死锁可能。把他们重新放回到一个线程中,就可以彻底解决软件死锁的问题。"

    这个`潜在可能`是指你的两个`task`会访问相同的临界资源吗?本来两个 task 只有临界代码会串行,其余都是并行操作,如果直接就因为`潜在可能`就放到相同线程操作这样会不会直接就没有并发的效果了啊?
    cc100
        54
    cc100  
       2020-07-27 12:06:14 +08:00
    有一个问题想请教一下楼主:
    “如果我的理论是错误的,那么必然写不出 pelagia “ 。
    写出了这个项目为什么就能证明这个理论是正确的。(怎么能证明现在的理论无法覆盖你的实现,从而必须引入一个新的条件)
    lamy
        55
    lamy  
       2020-07-27 12:19:01 +08:00 via Android
    单线程不会死锁?了解下递归锁为什么存在吧
    gantleman
        56
    gantleman  
    OP
       2020-07-27 13:55:29 +08:00
    @cc100 你是程序就必然能看懂代码,下载示例运行下就会得到结果,计算机是不会骗人的。linus 说的好:“不要和我说狗屁理论,请亮出你的代码。”
    acerlawson
        57
    acerlawson  
       2020-07-27 14:04:48 +08:00 via iPhone   ❤️ 2
    几天前连发两贴介绍自己的项目没人理,楼主只能靠这种标题党挨骂来推广了。

    真的很讨厌这样民科式的推广帖子,举报。
    gantleman
        58
    gantleman  
    OP
       2020-07-27 14:17:41 +08:00
    @acerlawson 我现在特别理解 Linus 为什么喜欢怼天怼地的,你刚毕业也就一年吧。我 06 年参加工作,先后就职于快车,金山,优信做开发。不看帖子,不看代码,上来指着一个工作 15 年的工程师说这货是民科。你不是,做过什么亮出来看看。
    LANB0
        59
    LANB0  
       2020-07-27 14:33:20 +08:00   ❤️ 1
    支持 @binux 的说法,你只是偷换了概念。task 原本指的就是调度的最小单元,传统意义上称为进程或线程,而不是你包装一层的东西。除非你包装的这一层完成地实现任务调度和锁,这样你的任务也还是会出现“死锁”了。
    gantleman
        60
    gantleman  
    OP
       2020-07-27 14:38:07 +08:00
    @LANB0 pelagia 实现了任务调度和锁,请阅读基本代码后再说结论。手写的代码可以解决死锁,那么 pelagia 为什么不能解决死锁?为什么必然会出现死锁?你的结论是怎么推导出来的?
    LANB0
        61
    LANB0  
       2020-07-27 15:18:56 +08:00
    @gantleman 如果完整地实现了,那在你实现这一层一样会出现“死锁”,这有什么疑问呢?注意这里的死锁我加了引号,是你实现的锁的死锁。虽然不是原有系统实现的锁,但意义是一样的,除非你实现的调度和锁环境强行破坏了上述四个条件之一。但这不正证明了 4 个必要条件的正确性吗?
    fasionchan
        62
    fasionchan  
       2020-07-27 15:31:30 +08:00
    @codehz 而且做到最后,可能出现这样的情况:所有的 task 都要在同个线程里执行……
    gantleman
        63
    gantleman  
    OP
       2020-07-27 15:38:13 +08:00
    @LANB0 总结一下你的脑回路,多线程必须服从两个定律,1 必须服从四个必要条件,2 不服从的参考第一条。既然这样,1,pelagia 是解决了现有缺陷。2,反对的请遵守第一条。你要是喜欢玩这种文字游戏我可以和你玩上几天。
    gantleman
        64
    gantleman  
    OP
       2020-07-27 15:40:50 +08:00
    @fasionchan 为了避免多线程的缺陷,把所有服务都塞到一个线程的事情还少吗? nodejs 和 go 的哪些破烂事无需多说。
    fasionchan
        65
    fasionchan  
       2020-07-27 15:55:38 +08:00
    @gantleman 那就没必要这么兴奋了,好像改变了世界?我不否认这个思路在某些场景可以起作用,如果这么简单的想法就可以解决大量复杂的工程问题,应该早就有前辈搞出来了吧?轮不到你我在这讨论。
    gantleman
        66
    gantleman  
    OP
       2020-07-27 16:10:13 +08:00
    @fasionchan pelagia 有 4 万行代码,从文件数据库分页开始写,到嵌套锁,多线程日志,线程池,消息路由。每个功能都能拿出写上万八千都字。为了让你们看明白我绞尽脑汁把事情说的简单明了。我把事情说简单了还不行,有说我是民科,有说偷换概念的。当然也有人愿意了解新知识和我讨论到的,今天下载的人也不少。
    fasionchan
        67
    fasionchan  
       2020-07-27 16:23:27 +08:00
    @gantleman 确实没看过代码不好评论,也许你可以用示意图后者其他直白的手段将思想描述出来。

    我没看过代码,这么短的时间也不可能深入去看,从文字介绍,我总结出了这样的结论:将有可能产生死锁死锁的任务挑出来,放在一个线程里面串行执行。说白了就是用串行解决死锁问题,不知道我又没有理解对。如果是我理解的这样,操作系统书也介绍过吗,只不过将其当做一个不那么好的方案来引出其他方案。

    另外,其他人也提到了任务提交顺序问题,解决起来也是相当棘手的,也不知道你是怎么解决的?
    gantleman
        68
    gantleman  
    OP
       2020-07-27 17:05:38 +08:00
    @fasionchan 谢谢,不要着急,都会有的。pelagia 只是我工作之余的一个意外。三年前本来只是想写本书,在查找论文资料的过程中发现原来的理论有缺陷。然后扯呀查呀,结果越搞窟窿越大。本来想写个示例,结果三年来写成了 pelagia 。我一个只有两双手呀,慢慢来都会做起来。
    mahogany
        69
    mahogany  
       2020-07-27 18:29:28 +08:00
    之所以有死锁这个问题,是因为并发的场景很有价值,我们不得不面对这个问题。你这是把洗澡水和婴儿一起倒了.....
    aeon113
        70
    aeon113  
       2020-07-28 00:43:54 +08:00 via Android
    不知道合并 task 是怎么样的一种合并,是在一个线程里来回切换各个 task 吗,还是每个 task 都必须依次完成。
    如果是第一种的话事实上解决不了死锁问题。如果熟悉 Linux 用户态 C/C++开发的话你可以尝试写一段测试代码,先 set cpu affinity,把当前进程绑在一个核上,然后起几个使用 mutex 引起死锁的子线程,观察死锁问题是否还存在。
    如果是第二种,那其实是把并发执行换成串行执行,也不符合死锁的引发前提。你 quote 的论文的 Introduction 节第一句话是 One of the objectives ...... among many concurrently executing tasks. 在 4 个条件的后一页有对它们的总结: Deadlocks can be expressed more precisely in terms of graphs. Suppose we have a set of tasks { T1, T2, ..., Tn, } in some arbitrary state of execution; ......
    你可以理解一下"concurrently executing tasks"、"tasks in some arbitrary state of execution"和你的"task"是否是一个概念。
    gantleman
        71
    gantleman  
    OP
       2020-07-28 02:29:56 +08:00
    @aeon113 第二种的结论呢? task 相同和不相同的结论呢?说话千万不要说一半,会让人睡不着觉的。年纪大了起夜就多,一睁眼睛下半夜又睡不着了。
    gantleman
        72
    gantleman  
    OP
       2020-07-28 03:22:02 +08:00
    @mahogany 虽然前面已经回复过了,对于你这种不看帖子就说话的我也不赚你哪 5 毛钱。但只能享受复制粘贴了。

    如果你有 100 个任务,其中 2 个任务死锁。把这两个任务单独放到一个线程里,剩下 98 个任务分别放的 98 个线程里。对于剩下 98 个任务死锁就不是问题吗?我没有否定线程,我只是否定有死锁条件的线程。我没有说有 2 个任务死锁,剩下的 98 个任务就不分线程了!
    aeon113
        73
    aeon113  
       2020-07-28 08:55:34 +08:00 via Android
    @gentleman 论文里的 task 是进程或线程,你这玩意和这篇论文没有半毛钱关系。

    拿别人的文章给自己站台前,建议先把全文看完。

    还有,我发完贴就直接睡觉了,倒是你自己半夜两三点红着眼爬起来阴阳怪气。

    看你 58 楼说自己工作 15 年,估计快 40 了吧。24 小时守着 V2 怼这怼那还挺闲。

    再看你 8 天前的发帖记录,“寻找有价值的互联网公司”,看样子兄弟要么是工作不行,要么就是被优化了啊。😂

    不要总想着在网上搞大新闻,辣眼睛。
    gantleman
        74
    gantleman  
    OP
       2020-07-28 09:26:13 +08:00
    @aeon113 让你说个结论把你的观点补全了,就开始气急败坏的骂街。我特别理解你这种一辈子拿不出半点东西的人,活着非常焦虑。有人一辈子就是做不出东西,该认命的认命,没准靠学习 pelagia 下半辈子还能混口饭吃。
    aeon113
        75
    aeon113  
       2020-07-28 11:32:10 +08:00 via Android
    @gantleman 哈哈,小老弟急了。
    建议拿你长满老茧的食指把你的百元机屏幕向上滑一滑,看看发帖记录是谁先骂街的吧,还是两三点起夜来骂的噢😁 。
    你要是想硬广你这小玩意,好好说话还是可以讨论讨论的。这个态度嘛还是算了吧。
    不过还是建议你先把工作找到,这个岁数应该去考虑养老的问题了。
    你这账号我就先 block 了,下次你有新的神论了我们再切磋。
    gantleman
        76
    gantleman  
    OP
       2020-07-28 12:24:00 +08:00
    @aeon113 别了,好走不送,我没有办法帮你从负能量中解脱。但希望我在技术领域的勤奋努力,积极进取能给你的生活带来一点点阳光。
    fasionchan
        77
    fasionchan  
       2020-07-28 13:52:52 +08:00   ❤️ 1
    @gantleman @aeon113 他已经把话说得很清楚了,至少我得看明白,应该不算话说一半……前面我好像也提过,你这个方案本质就是串行化,可能适用于少量特定的场景,但在我认知的范围内,看不到普适性。就像如果数据库串行化真的好使,那些大神们何必去折腾各种隔离级别和多版本并发呢?
    mahogany
        78
    mahogany  
       2020-07-28 18:53:04 +08:00
    @gantleman 我觉得现实不是你想的那么简单,你的 2/98 是怎么得出来的?为什么不是 50/50 ?
    你有没有想过你的这种想法能否应对下面的场景:高并发情况下也只有很小的概率造成死锁。这种情况难道直接全部串行?
    为什么不能干脆允许死锁出现,然后在死锁检测上多下功夫?
    而且我个人觉得"能发现两个 task 有潜在的死锁可能"这个一点都不现实。

    别 5 毛 5 毛的,讨论问题不要人身攻击 =_=-
    no1xsyzy
        79
    no1xsyzy  
       2020-07-28 22:31:44 +08:00
    no1xsyzy
        80
    no1xsyzy  
       2020-07-28 23:27:05 +08:00
    我先拍脑袋提段(伪)代码,你的工具将彻底降级体验,场景是 /t/691526 的 #6 楼,假设 100 个完全相同的 Task
    if(random()<0.01){
    syncronized(x){
    x--;
    }
    }
    如果你只靠静态分析,那么全部只能塞进一个串行绪。
    所以上述必然要拆分,把 random()<0.01 判断完之后重新构造 Task,这个新 Task 才能加锁。
    否则就是近似 100 倍性能损失。
    结果就是没解决复杂性,最多是些锁语义的语义糖,还优先解决死锁问题。

    如果你觉得真的有必要,如上,请给 arXiv 发论文。
    cnnblike
        81
    cnnblike  
       2020-07-29 07:24:52 +08:00   ❤️ 2
    1.1k 的 star,11 个 fork 10 个 watch,哥,你这 star 刷得也忒明显了
    cnnblike
        82
    cnnblike  
       2020-07-29 07:25:45 +08:00   ❤️ 1
    30 个 issue 全都是自己发自己 resolve,绝了,建议多开几个小号吧,更可信点
    dreampet
        83
    dreampet  
       2020-07-29 07:32:31 +08:00 via Android   ❤️ 1
    也许是个好产品,但运作、推广方式让人反感
    ksedz
        84
    ksedz  
       2020-07-29 19:40:04 +08:00   ❤️ 1
    支持楼主下,最近一直想学习无锁架构,提供的论文线索也很有价值。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2070 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 16:14 · PVG 00:14 · LAX 08:14 · JFK 11:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.