max*_*yne 9 mutex deadlock pthreads
我最近遇到了这个面试问题(在一个论坛上发布了一些......看起来这是一个真实的面试问题):
设计一个只有在没有可能的死锁时才提供锁的类.
没有提供其他信息.我不太清楚如何解释这一点.假设pthreads模型,面试官是否正在寻找锁定经理类？任何想法都会有所帮助
只有当锁可以以圆形方式保持时,锁才会发生死锁; 也就是说,如果你定义了一个排序<on lock这样A <B只有当锁A可以用锁B保持时,那么<不是严格的部分排序.例如,如果线程1尝试获取锁A然后锁定B,而线程2尝试获取锁B然后锁定A,则A <B且B <A,因此<不是严格的部分排序.实际上,如果线程1和2分别获得锁A和B,则会发生死锁,然后尝试获取另一个锁.
要动态检测这种情况,一种选择是维护系统中锁的有向图.每当一个线程试图获取一个锁时,从它所持有的每个锁中添加一条边到它试图获取的锁.如果此操作形成一个循环,则即将发生死锁,因为某些其他线程拥有您指向的锁并且正在尝试获取其他锁.这种结构是全局的,您需要采取适当的预防措施,以确保它正确同步.但是,它会为您提供一种非常直接的方法来检测是否即将发生死锁.
编辑:这是一个简单的实现方案的草图.我假设你有一个原始的天真互斥锁,它不会阻止死锁,并且能够在每个线程的基础上存储一些数据.
在智能锁类的内部,创建一个由锁的所有实例共享的静态互斥锁,以保护对所有权图的访问.此外,创建一个映射,将每个锁与它具有边的锁定集相关联.最后,设置该线程拥有的所有锁的每线程集.
当线程尝试获取智能锁时,首先获取静态互斥锁以确保对图结构的独占访问.对于该线程拥有的每个锁,将静态图中的边从该锁添加到正在获取的锁.现在,从当前线程持有的每个锁定开始,在图形上运行深度优先搜索,以查找周期.这需要时间线性的图形大小,这是系统中锁定数量最差的二次方(尽管这种情况极不可能发生,因为这意味着很大一部分锁可以从线程中以某种方式到达锁).如果发现一个循环,即将发生死锁,你应该采取某种纠正措施.否则,释放静态锁以允许其他线程访问图形.
当线程实际获取锁时,将该锁添加到线程的拥有锁集.
当线程释放锁时,获取静态图形锁并删除该锁的节点的所有传入边,该边对应于当前线程持有的其他锁,然后释放锁.
希望这可以帮助!