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

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

Tasks claim exclusive control of the resources they require ("mutual exclusion" condition).
Tasks hold resources already allocated to them while waiting for additional resources ("wait for" condition).
Resources cannot be forcibly removed from the tasks holding them until the resources are used to completion ("no preemption" condition).
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 　发现一些不同的并行计算的知识。

gantleman

2020-07-26 21:11:03 +08:00

@Inn0Vat10n 在一个线程里每个任务的执行是连续非中断的。你假设的条件是第一个任务执行一半，然后执行第二个任务，然后再执行剩下一半。其实就变成任何锁只要锁了不释放都必然会阻塞。更准确的说只要嵌套请求锁就有可能因为嵌套的次序不同而阻塞。那么你就是在说 70 年论文对死锁的定义不严谨准确。那么你得到另一个有趣的结论。只要请求锁的嵌套次序都相同就不会死锁。所以循环嵌套也不是死锁的必然条件。

你看好好讨论就会得到一些有趣的结论。这不你又发现了一些奇怪的知识。所以死锁究竟应该如何定义？

ysmood

2020-07-26 21:38:56 +08:00

你说的多线程既不是充分条件也不是必要条件，就算不是多线程也是可以死锁的，就算是多线程也可以不死锁。很多单核 OS 也是可以模拟多线程的，那种 OS 的程序就不会死锁了吗？

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

我觉得 4 个都有点多余了，还来第 5 个。其实可根据具体情况加无限个条件的，全看你怎么定义死锁，问题太宽泛以至于难以吊起人们的讨论欲望。

crclz

2020-07-26 21:53:43 +08:00

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

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

1. 等待一个时间Δt，累积一些任务，看看如何调度这些任务来使得死锁不发生。（你会浪费Δt，并且每个任务的响应时间至少增加Δt ）
2. 两阶段锁协议。（被 DBMS 广泛采用）
3. 单线程（ LMAX Architecture ）

ysmood

2020-07-26 23:28:05 +08:00

@gantleman 我只是想表达这个问题跟线程没有关系，单线程也可以 mutex 嵌套阻塞。很好奇单线程是如何防止我故意 mutex 嵌套阻塞的。并没有说你解决问题的过程有问题，只是觉得可能表达的方式让大家容易不太容易接受。比如你扔一个项目地址，然而我看了半天文档，却感觉很难跟你说的关联起来。

能简单介绍下 pelagia 的工作原理就好了。目前我稍微看了下，错了请指正。感觉就是把逻辑问题转嫁了而已，用户需要花更多的时间来思考如何把用锁能解决的问题转化为 job 调度问题，把问题提前解决了而已，感觉就是用库或语法辅助思考模式而已。

future0906

2020-07-27 00:03:38 +08:00

推广自己的项目总要一些吸引眼球的点，不过这样故作高深没什么用，不如直接引战说"C 语言是世界上最好的语言？"

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

这种无意义的推广帖我只回一次，恳请建议管理员移到:https://www.v2ex.com/go/ohno

gantleman

2020-07-27 04:18:44 +08:00

@ysmood 考虑对性能的榨取，阿达姆尔定律是多线程的上限，那么死锁就是多线程的下限。只有上下限都确定了，才能正确的使用多线程。死锁的问题在于其随机性无法通过简单测试就能发现，最终导致软件产品在不断升级的过程中走向不可控。pelagia 的意义在于通过一系列的规则让不可控的下限在开发过程中就能被发现。这样就把不可控变成了可控。在完全可控的前提下才能追求极致，去压榨多线程的上限效率。