multithreading - 如何判断加锁顺序是否冲突

Question

如果我有关于哪个线程和代码行以什么顺序获取了哪些锁的经验数据，那么我如何使用该数据来确定锁定顺序是否有死锁的可能性？

l = 锁u = 解锁

例如:这些有冲突，可能会死锁

thread 1: l1, l2, u2, u1
thread 2: l2, l1, u1, u2

甚至这个单线程也会与自身发生冲突，因为我真的不知道序列的后半部分不会在不同的用例中在单独的线程上运行。

thread 1: l1, l2, u2, u1, l2, l1, u1, u2

是否有合适的算法可用于从数据中确定这一点？

请注意，我问的不是要查找什么(不同的锁获取顺序)，而是在给定一组经验数据的情况下使用什么算法或数据结构来查找它们。

Answer 1

您需要构建一个锁排序图，并检查循环。

每当获取一个锁而另一个锁被持有时，从持有的锁添加一条边到获取的锁。

你的例子:

thread A: lock 1, lock 2, unlock 2, unlock 1
thread B: lock 2, lock 1, unlock 1, unlock 2

因为线程 A 在持有 1 的同时锁定了 2，而线程 B 在持有 2 的同时锁定了 1，所以你有这些边缘:

1 -> 2
2 -> 1

Making this graph :

其中有循环，所以有潜在的死锁。

参见:directed cycle detection algorithm

警告

技术上，完全由来自一个线程的边缘组成的循环不会导致死锁(因为您可能正在使用 re-entrant locks )。所以这些循环并不是真正的僵局……它们是定时炸弹。 future 对线程的一些看似无害的更改会引发它们，将它们变成死锁，并毁掉你的一天。

您可以优化此算法以避免出现这种情况，但我不会费心，因为您忽略的内容也很糟糕。