Sound Dynamic Deadlock Prediction in Linear Time
summary
Introduces a new class called sync-preserving deadlocks and two algorithms SPDOffline and SPDOnline that detect only those deadlocks but do so with overall linear time dependence on trace length. Proves full predictive deadlock detection is intractable, gives linear-per-pattern offline detection and a strictly online linear-time two-thread predictor, matches SEcheck on benchmarks while running much faster, reports only one missed real deadlock in the suite, and produces more online finds than a fuzzing baseline.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:21Dynamic analysis for concurrency bugs
- 2:45Dynamic deadlock prediction problem
- 4:29Identifying potential deadlocks
- 6:14Abstract lock graph for efficiency
- 7:58Checking deadlocks with witness traces
- 8:43Sync-preserving deadlocks
- 10:08Combining abstractions for linear time
- 11:33Offline evaluation results
- 12:37Online algorithm and randomized testing
- 13:39Conclusion
related talks
19mSound Deadlock Prediction
37mMore Effective Approach To Detecting Potential Deadlocks, DEPT(DEPendency Tracker)
48mMore Effective Approach to Detecting Potential Deadlocks, DEPT(DEPendency Track...
28mEnd-to-end Deadlock Debugging Tools at Facebook
47mDeadlocks: The Dark Side of Concurrency
35mPredictable Latency
01h 38mLock-free Programming is Dead - Long Live Lock-free Programming!
01h 08mSimplifying Concurrent Programming via Synchronization Synthesis