一句话：提出首个低开销死锁预测器 AirLock，通过小锁可达图与按环分析，将平均开销降至 3.5%。
多线程程序即使部署后仍可能发生死锁，因此用户希望在已部署程序上运行死锁检测工具。但现有预测器 MagicLock 和 UnDead 由于在大执行轨迹上运行指数时间算法，开销过高，仅适合开发阶段。本文提出首个低开销死锁预测器 AirLock，它维护一个较小的预测性锁可达图，在图中搜索环，并仅对每个环运行指数时间算法。由于实际中环的数量很少，AirLock 能在发现与 MagicLock 和 UnDead 相同死锁的同时大幅降低开销。在真实基准上的实验表明，AirLock 的平均时间开销为 3.5%，比 MagicLock 和 UnDead 低三个数量级，适用于 AFL 等模糊测试器以及部署后的在线使用。
Multithreaded programs can have deadlocks, even after deployment, so users may want to run deadlock tools on deployed programs. However, current deadlock predictors such as MagicLock and UnDead have large overheads that make them impractical for end-user deployment and confine their use to development time. Such overhead stems from running an exponential-time algorithm on a large execution trace. In this paper, we present the first low-overhead deadlock predictor, called AirLock, that is fit for both in-house testing and deployed programs. AirLock maintains a small predictive lock reachability graph, searches the graph for cycles, and runs an exponential-time algorithm only for each cycle. This approach lets AirLock find the same deadlocks as MagicLock and UnDead but with much less overhead because the number of cycles is small in practice. Our experiments with real-world benchmarks show that the average time overhead of AirLock is 3.5%, which is three orders of magnitude less than that of MagicLock and UnDead. AirLock's low overhead makes it suitable for use with fuzz testers like AFL and on-the-fly after deployment.
DOI 原文 ·
@inproceedings{paperbot5657,
title = {Low-overhead deadlock prediction},
author = {Yan Cai and Ruijie Meng and Jens Palsberg},
booktitle = {ICSE},
year = {2020},
doi = {10.1145/3377811.3380367}
}