死锁检测的成本有多高？

Question

我想知道Lock检测周期有多复杂，它有多大的开销。实际上，我认为它应该相当简单，但Java中没有它，这让我不确定。

有an answer推荐使用tryLock，但这种检测是该语言应该提供的开箱即用的功能(作为一个选项)。

我发现的唯一类似的东西是Guava的CycleDetectingLockFactory，但它有一些很重要的开销和doesn't try来捕获所有死锁。

Answer 1

我相信它可能是O(N**3)，因为你可以在对象上持有X个锁，每个对象都被Y个其他线程等待，每个线程可以持有Z个锁。然后，你必须对它们进行拓扑排序，以检测循环。