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

2020-07-26 09:13:39 +08:00
 gantleman

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

9988 次点击
所在节点    程序员
84 条回复
cmqwan
2020-07-26 09:22:26 +08:00
总结下:

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

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

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

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

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

听起来是不是正确的废话?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/693150

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX