设计一个类，仅当不存在可能的死锁时才提供锁
我最近遇到了这个面试问题（发布在某个论坛上......看起来这是一个真正的面试问题）：
设计一个类，仅当不存在可能的死锁时才提供锁。
没有提供其他信息。我不太确定如何解释这一点。假设pthreads模型，面试官是在寻找锁管理器类吗？任何想法都会有帮助。
I recently came across this interview question (posted in a forum somehwere... looks like this was a real interview question):
Design a class which provides a lock only if there are no possible deadlocks.
No other information is given. I am not quite sure how to interpret this. Assuming pthreads model, is the interviewer looking for a lock manager class? Any ideas will help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
仅当锁可以以循环方式持有时，锁才会发生死锁；也就是说，如果您定义排序 <在锁上，使得 A <仅当锁 A 可以被持有且锁 B 也被持有时，B 才成立。不是严格的偏序。例如，如果线程1尝试获取锁A然后锁B，而线程2尝试获取锁B然后锁A，则A＜0。 B和B＜ A、所以<不是严格的偏序。事实上，如果线程 1 和 2 分别获取锁 A 和 B，然后尝试获取另一个锁，则可能会发生死锁。
要动态检测这种情况，一种选择是维护系统中锁的有向图。每当线程尝试获取锁时，请将其持有的每个锁的边添加到它尝试获取的锁。如果此操作形成一个循环，则即将发生死锁，因为其他某个线程拥有您所指向的锁，并且正在尝试获取其他锁。该结构将是全局的，您需要采取适当的预防措施以确保其正确同步。但是，它将为您提供一种非常直接的方法来检测是否即将发生死锁。
编辑：这是一个简单实施方案的草图。我假设您有一个原始的互斥锁，它不能防止死锁，并且能够在每个线程的基础上存储一些数据。
在智能锁类内部，创建一个由锁的所有实例共享的静态互斥锁，以保护对所有权图的访问。另外，创建一个映射，将每个锁与其有边的锁集相关联。最后，设置该线程拥有的所有锁的每个线程集。
当线程尝试获取智能锁时，首先获取静态互斥体以确保对图结构的独占访问。对于该线程拥有的每个锁，在静态图中添加一条从该锁到正在获取的锁的边。现在，从当前线程持有的每个锁开始，对图运行深度优先搜索，以查找循环。这花费的时间与图的大小成线性关系，最坏的情况下是系统中锁数量的二次方（尽管这种情况极不可能发生，因为这意味着大部分锁可以通过某种方式从线程的锁）。如果发现循环，则即将发生死锁，您应该采取某种纠正措施。否则，释放静态锁以允许其他线程访问该图。
当线程实际获取锁时，将该锁添加到该线程拥有的锁集中。
当线程释放锁时，获取静态图锁并删除该锁对应于当前线程持有的其他锁的节点的所有传入边，然后释放锁。
希望这有帮助！
Deadlock will occur with a lock only if the locks can be held in a circular fashion; that is, if you define an ordering < on locks such that A < B only if lock A can be held with lock B also held, then < is not a strict partial ordering. For example, if thread 1 tries to acquire lock A and then lock B, while thread 2 tries to acquire lock B and then lock A, then A < B and B < A, so < is not a strict partial ordering. Indeed, deadlock can occur if threads 1 and 2 each get locks A and B, respectively, then try to acquire the other lock.
To detect this sort of condition dynamically, one option is to maintain a directed graph of the locks in the system. Whenever a thread tries to acquire a lock, add an edge from each lock that it holds to the lock it's trying to acquire. If this action forms a cycle, then deadlock is about to occur because some other thread owns the lock you're pointing at and is trying to acquire some other lock. This structure would be global and you'd need to take the appropriate precautions to ensure that it was synchronized correctly. However, it would give you a very direct way of detecting whether or not deadlock was about to occur.
EDIT: Here's a sketch of a simple implementation scheme. I assume that you have as a primitive a naive mutex lock that does not prevent deadlock, along with the ability to store some data on a per-thread basis.
Inside of the smart lock class, create a static mutex shared by all instances of the lock that guards access to the ownership graph. Also, create a map associating each lock with the set of locks it has edges to. Finally, set up a per-thread set of all the locks owned by that thread.
When a thread tries to acquire a smart lock, first acquire the static mutex to ensure exclusive access to the graph structure. For each of the locks owned by that thread, add an edge in the static graph from that lock to the lock being acquired. Now, run a depth-first search over the graph starting from each of the locks held by the current thread looking for cycles. This takes time linear in the size of the graph, which is at worst quadratic in the number of locks in the system (though this is extremely unlikely to occur, since it would mean that a large fraction of the locks are somehow reachable from the thread's locks). If a cycle is found, deadlock is about to occur and you should take some sort of corrective action. Otherwise, release the static lock to allow other threads access to the graph.
When a thread actually acquires a lock, add that lock to the thread's set of owned locks.
When a thread releases a lock, acquire the static graph lock and remove all incoming edges to the node for that lock that correspond to other locks held by the current thread, then release the lock.
Hope this helps!
好吧，我想说，所需的关键洞察力是，类可以编排这种情况的唯一方法是控制可能涉及此类死锁的整套相关锁。例如，它可以要求它们按某种特定的顺序（例如，基于与每个锁关联的名称的字母顺序、源中硬编码的任意唯一整数）。
Well, I'd say the key insight required is that the only way a class can orchestrate that is by having control of the entire set of related locks that might be involved in such deadlocks. It can then, for example, require they be taken in some specific order (e.g. alphabetic ordering based on a name associated with each lock, arbitrary unique integers hardcoded in the source).
实际上，同样的问题也出现在《破解编码面试》中。
答案如下：
Actually the same question appears in Cracking the coding interview.
Here is the answer: