设计一个仅在没有可能死锁的情况下才提供锁的类。

Question

我最近遇到了一个面试问题(发表在一个论坛上).看起来这是一个真正的面试问题)：

设计一个类，它只在没有可能死锁的情况下提供锁。

没有提供任何其他信息。我不太清楚如何解释这一点。假设class模型，面试官是否在寻找锁管理器类？任何想法都会有帮助。

Answer 1

只有当锁可以以循环方式保持时，锁才会出现死锁；也就是说，如果您定义了排序< on锁，只有当锁A可以与锁B同时保持时，才会出现死锁，那么<不是严格的偏序。例如，如果线程1试图获取锁A，然后锁定B，而线程2尝试获取锁B，然后锁定A，则A

要动态地检测这种情况，一种选择是维护系统中锁的有向图。每当线程试图获取锁时，从它持有的每个锁中添加一个边缘到它要获取的锁上。如果此操作形成循环，则会发生死锁，因为其他线程拥有您所指向的锁，并试图获取其他锁。这个结构是全局的，您需要采取适当的预防措施，以确保它是正确同步的。但是，它将为您提供一种非常直接的方法来检测死锁是否即将发生。

编辑：这里是一个简单实现方案的草图。我假设您有一个简单的互斥锁，它不能防止死锁，还可以在每个线程的基础上存储一些数据。

在智能锁类中，创建一个由所有锁实例共享的静态互斥锁，以保护对所有权图的访问。另外，创建一个映射，将每个锁与其具有边缘的一组锁关联起来。最后，设置该线程拥有的所有锁的每个线程集。

当线程试图获取智能锁时，首先获取静态互斥以确保对图形结构的独占访问。对于该线程拥有的每个锁，将静态图中的一个边缘从该锁添加到正在获取的锁中。现在，对图执行深度优先搜索，从当前线程持有的每个锁开始寻找周期。这需要时间线性的图形大小，在最坏的二次锁在系统中的数目(虽然这是极不可能发生，因为这将意味着很大一部分锁可以从线程的锁以某种方式到达)。如果发现了一个循环，就会出现死锁，您应该采取某种纠正措施。否则，释放静态锁以允许其他线程访问图形。

当线程实际获得一个锁时，将该锁添加到线程拥有的一组锁中。

当线程释放锁时，获取静态图锁，并删除与当前线程持有的其他锁对应的该锁的所有传入边缘，然后释放锁。

希望这能有所帮助！

Answer 2

我要说的是，所需的关键洞察力是，类能够编排的唯一方法是通过控制可能涉及到此类死锁的整个相关锁集。例如，它可以要求按照特定的顺序(例如，基于与每个锁关联的名称、源中硬编码的任意唯一整数)进行字母排序。

Answer 3

实际上，在破解编码面试时也会出现同样的问题。以下是答案：

​