使用锁分配图动态检测混合死锁

发布时间：2018-04-10 03:38

本文选题：动态分析　切入点：软件测试　出处：《计算机研究与发展》2017年07期

【摘要】：死锁难以暴露、重演和调试.一旦发生,将导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃.现有死锁检测技术每次只能检测一个互斥锁死锁.为一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁,首先提出混合锁分配图的概念和构建方法,然后提出一种利用混合锁分配图动态检测混合死锁的方法.通过劫持所有互斥锁和读写锁的加锁解锁操作,以动态构建和实时更新一个反映目标程序同步状态的混合锁分配图.通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁.当检测到死锁时,输出死锁信息来辅助调试.死锁检测实验、性能影响实验和可扩展性实验结果表明:该方法成功检测出所有13个共5种类型的死锁缺陷,检测能力强;给openldap-2.2.20带来至多10.15%的性能下降幅度,对目标程序造成的性能影响较小;性能开销随线程数目指数级增大而平缓增长,扩展性良好.
[Abstract]:Deadlocks are difficult to expose, repeat and debug.Once that happens, the multithread program response time increases, throughput drops and even crashes.Existing deadlock detection techniques can detect only one mutex lock at a time.In order to detect all types of deadlocks caused by multiple threads and mutex locks or read and write locks at one time, the concept of mixed lock allocation graph and its construction method are proposed first, and then a method to dynamically detect hybrid deadlock by using mixed lock allocation graph is proposed.By hijacking lock unlocking operations of all mutex and read / write locks, a hybrid lock allocation graph reflecting the synchronization state of the target program is constructed and updated in real time.The deadlock is detected by detecting the ring on the lock allocation diagram and determining whether the ring is a deadlock ring.When a deadlock is detected, the deadlock information is output to assist debugging.The results of deadlock detection experiment, performance impact experiment and extensibility experiment show that the proposed method successfully detects all 13 deadlock defects of 5 types and has strong detection ability, and brings up to 10.15% performance degradation to openldap-2.2.20.It has little effect on the performance of the target program, and the performance overhead increases slowly with the increase of the number of threads exponentially, and the expansibility is good.
【作者单位】：哈尔滨工业大学计算机科学与技术学院;
【基金】：国家自然科学基金项目(61173021,61672191)~~
【分类号】：TP311.53

【参考文献】