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

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

Akiyu

2020-07-26 10:51:51 +08:00

是的, 按照你说的, 的确可以规避死锁.
极端情况, 比如说只有两个线程执行两个任务, 当冲突的时候, 将两个任务放到一个线程中.
这当然可以规避死锁(都只有一个任务了!).

但显而易见有些缺陷和矛盾, 一是和本身多线程的想法有点冲突, 二是任务的粒度加大, 并发性进一步降低.
多线程是串行转并行, 为了提高效率. 但按你这么说, 反而并行转回串行(虽然是部分, 但的确有).
和本身引入多线程技术的想法冲突了. 而且, 将两个任务合并为一个任务, 这样任务的粒度就会变大. 并发性再次减少.
考虑一下这种情况: A 和 B 冲突, AB 合并(合并后, 该任务执行时间必定加长), 如果一种比较糟糕的情况出现了, 比如出现了 C 任务, 他和 AB 冲突了. 这种情况怎么办? 再次合并么?

jinliming2

2020-07-26 12:46:11 +08:00

我的理解，你自己加的这个“隐含假设的条件”不对，多线程并不是死锁的条件，单线程下依旧会出现死锁。
只不过实际开发在单线程条件下，因为通常不会出现资源访问冲突，所以单线程开发是不会加锁的，也就不会死锁。
但是，如果在单线程下使用了锁，那么如果资源获取、释放的顺序不对，也会产生死锁。也就是条件中的循环依赖，自己依赖自己。
最简单的例子就是，对一个资源进行加锁访问，在没有释放的时候，再对其进行加锁。这符合四个条件。

真实的情况可能会复杂一些，就是在多线程环境下，其中某一个线程出现了加锁、释放顺序不对的情况。