We study the problem of determining whether from a run of a concurrent program, we can predict alternate deadlocking executions of it. We show that if a concurrent program adopts nested locking, the problem of predicting deadlocks is efficiently solvable without exploring all interleavings.#R##N##R##N#In this work we present a fundamentally new predictive approach to detect deadlocks in concurrent programs, not based on cycle detection in lock-graphsi¾?[1]. The idea is to monitor an arbitrary run of a concurrent program, use it to predict alternate runs that could be deadlocking, and reschedule them accurately. We implement our prediction algorithm in a tool called PickLock, which is a modular extension of the Penelope frameworki¾?[32].#R##N##R##N#We show experimentally that PickLock scales well and is effective in predicting deadlocks. In particular, we evaluate it over 13 benchmark concurrent programs and find about 11 deadlocks by using only a single test run as the prediction seed for each benchmark.
['Francesco Sorrentino']
PickLock: A Deadlock Prediction Approach under Nested Locking