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

[gantleman]

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

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

原文如下为： “

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).”

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

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

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

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

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

[LANB0]

@gantleman 如果完整地实现了，那在你实现这一层一样会出现“死锁”，这有什么疑问呢？注意这里的死锁我加了引号，是你实现的锁的死锁。虽然不是原有系统实现的锁，但意义是一样的，除非你实现的调度和锁环境强行破坏了上述四个条件之一。但这不正证明了 4 个必要条件的正确性吗？

[fasionchan]

@codehz 而且做到最后，可能出现这样的情况：所有的 task 都要在同个线程里执行……

[gantleman]

@LANB0 总结一下你的脑回路，多线程必须服从两个定律，1 必须服从四个必要条件，2 不服从的参考第一条。既然这样，1，pelagia 是解决了现有缺陷。2，反对的请遵守第一条。你要是喜欢玩这种文字游戏我可以和你玩上几天。

[gantleman]

@fasionchan 为了避免多线程的缺陷，把所有服务都塞到一个线程的事情还少吗？ nodejs 和 go 的哪些破烂事无需多说。

[fasionchan]

@gantleman 那就没必要这么兴奋了，好像改变了世界？我不否认这个思路在某些场景可以起作用，如果这么简单的想法就可以解决大量复杂的工程问题，应该早就有前辈搞出来了吧？轮不到你我在这讨论。

[gantleman]

@fasionchan pelagia 有 4 万行代码，从文件数据库分页开始写，到嵌套锁，多线程日志，线程池，消息路由。每个功能都能拿出写上万八千都字。为了让你们看明白我绞尽脑汁把事情说的简单明了。我把事情说简单了还不行，有说我是民科，有说偷换概念的。当然也有人愿意了解新知识和我讨论到的，今天下载的人也不少。

[fasionchan]

@gantleman 确实没看过代码不好评论，也许你可以用示意图后者其他直白的手段将思想描述出来。

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

另外，其他人也提到了任务提交顺序问题，解决起来也是相当棘手的，也不知道你是怎么解决的？

[gantleman]

@fasionchan 谢谢，不要着急，都会有的。pelagia 只是我工作之余的一个意外。三年前本来只是想写本书，在查找论文资料的过程中发现原来的理论有缺陷。然后扯呀查呀，结果越搞窟窿越大。本来想写个示例，结果三年来写成了 pelagia 。我一个只有两双手呀，慢慢来都会做起来。

[mahogany]

之所以有死锁这个问题，是因为并发的场景很有价值，我们不得不面对这个问题。你这是把洗澡水和婴儿一起倒了.....

[aeon113]

不知道合并 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]

@aeon113 第二种的结论呢？ task 相同和不相同的结论呢？说话千万不要说一半，会让人睡不着觉的。年纪大了起夜就多，一睁眼睛下半夜又睡不着了。

[gantleman]

@mahogany 虽然前面已经回复过了，对于你这种不看帖子就说话的我也不赚你哪 5 毛钱。但只能享受复制粘贴了。

如果你有 100 个任务，其中 2 个任务死锁。把这两个任务单独放到一个线程里，剩下 98 个任务分别放的 98 个线程里。对于剩下 98 个任务死锁就不是问题吗？我没有否定线程，我只是否定有死锁条件的线程。我没有说有 2 个任务死锁，剩下的 98 个任务就不分线程了！

[aeon113]

@gentleman 论文里的 task 是进程或线程，你这玩意和这篇论文没有半毛钱关系。

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

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

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

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

不要总想着在网上搞大新闻，辣眼睛。

[gantleman]

@aeon113 让你说个结论把你的观点补全了，就开始气急败坏的骂街。我特别理解你这种一辈子拿不出半点东西的人，活着非常焦虑。有人一辈子就是做不出东西，该认命的认命，没准靠学习 pelagia 下半辈子还能混口饭吃。

[aeon113]

@gantleman 哈哈，小老弟急了。
建议拿你长满老茧的食指把你的百元机屏幕向上滑一滑，看看发帖记录是谁先骂街的吧，还是两三点起夜来骂的噢😁 。
你要是想硬广你这小玩意，好好说话还是可以讨论讨论的。这个态度嘛还是算了吧。
不过还是建议你先把工作找到，这个岁数应该去考虑养老的问题了。
你这账号我就先 block 了，下次你有新的神论了我们再切磋。

[gantleman]

@aeon113 别了，好走不送，我没有办法帮你从负能量中解脱。但希望我在技术领域的勤奋努力，积极进取能给你的生活带来一点点阳光。

[fasionchan]

@gantleman @aeon113 他已经把话说得很清楚了，至少我得看明白，应该不算话说一半……前面我好像也提过，你这个方案本质就是串行化，可能适用于少量特定的场景，但在我认知的范围内，看不到普适性。就像如果数据库串行化真的好使，那些大神们何必去折腾各种隔离级别和多版本并发呢？

[mahogany]

@gantleman 我觉得现实不是你想的那么简单，你的 2/98 是怎么得出来的？为什么不是 50/50 ？
你有没有想过你的这种想法能否应对下面的场景：高并发情况下也只有很小的概率造成死锁。这种情况难道直接全部串行？
为什么不能干脆允许死锁出现，然后在死锁检测上多下功夫？
而且我个人觉得"能发现两个 task 有潜在的死锁可能"这个一点都不现实。

别 5 毛 5 毛的，讨论问题不要人身攻击 =_=-

[no1xsyzy]

https://arxiv.org/help/submit

[no1xsyzy]

我先拍脑袋提段（伪）代码，你的工具将彻底降级体验，场景是 /t/691526 的 #6 楼，假设 100 个完全相同的 Task
if(random()<0.01){
syncronized(x){
x--;
}
}
如果你只靠静态分析，那么全部只能塞进一个串行绪。
所以上述必然要拆分，把 random()<0.01 判断完之后重新构造 Task，这个新 Task 才能加锁。
否则就是近似 100 倍性能损失。
结果就是没解决复杂性，最多是些锁语义的语义糖，还优先解决死锁问题。

如果你觉得真的有必要，如上，请给 arXiv 发论文。