ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (2): 428-445.doi: 10.7544/issn1000-1239.2017.20150701

• 软件技术 • 上一篇    下一篇

基于未来锁集的死锁规避

禹振,苏小红,齐鹏,马培军   

  1. (哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) (yuzhen_3301@aliyun.com)
  • 出版日期: 2017-02-01
  • 基金资助: 
    国家自然科学基金项目(61173021)

Deadlock Avoiding Based on Future Lockset

Yu Zhen, Su Xiaohong, Qi Peng, Ma Peijun   

  1. (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Online: 2017-02-01

摘要: 针对现有动态死锁规避方法存在能力有限、被动盲目、开销较大和影响目标程序正确性等问题,提出一种基于未来锁集的动静结合死锁规避方案Flider.基本思想是,对于一个加锁操作,若其未来锁集中的所有锁都是空闲的,则执行该加锁操作不会导致死锁.一个加锁操作的未来锁集包括当前要加锁的锁和从该加锁操作到与之相对应的解锁操作过程中遇到的所有加锁操作所要加的锁.通过静态分析,计算锁效应信息并插桩到相应的加锁操作和函数调用操作前后.通过动态分析,劫持加锁操作,根据其锁效应信息为之计算未来锁集,只有当未来锁集中的所有锁都未被锁定才执行该加锁操作,否则等待.测评实验和对比实验表明Flider能智能主动地规避多种类型死锁,开销较小,扩展性好,不影响程序正确性.

关键词: 并发缺陷, 并发测试, 死锁, 死锁检测, 死锁规避, 未来锁集

Abstract: Existing dynamic methods for deadlock avoidance have four main drawbacks: limited capability, passive or blind avoiding algorithm, large performance overhead and no guarantee of correctness of target programs. In order to solve these problems, a combined static and dynamic avoiding method based on future lockset is proposed and named as Flider. The key idea is that, for a lock operation, if none of its future locks are occupied, then it makes sure that executing this lock operation won't lead the current thread to trap into a deadlock state. The future lockset for a lock operation is a set of locks that will be requested by the current thread before the corresponding unlock operation is reached. Firstly, Flider statically computes lock effects for lock operations and function call operations, and inserts them before and after the corresponding operations. Secondly, Flider dynamically intercepts lock operations and computes its future lockset using lock effects inserted by static analysis. Flider permits a lock operation to be executed if and only if all locks of its lockset are not held by any other threads. Otherwise, the lock operation waits until the condition is satisfied. Evaluation and comparison experiments verify that this method can efficiently avoid multi-type deadlocks in an active, intelligent, scalable and correctness-guaranteed way.

Key words: concurrency bugs, concurrent testing, deadlock bugs, deadlock detection, deadlock avoidance, future lockset

中图分类号: