2013 | OriginalPaper | Buchkapitel
Dynamic Livelock Analysis of Multi-threaded Programs
verfasst von : Malay K. Ganai
Erschienen in: Runtime Verification
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Compared to deadlocks, where one or more threads are blocked forever, livelocks are harder to detect as it is not easy to distinguish between a long and an infinite busy wait (i.e., no progress) cycle. We propose a dynamic livelock analysis for a multi-threaded program by examining its execution trace. From the observed trace events, our approach uncovers livelock potentials due to infinite executions where one or more threads in a group are acquiring and releasing resources in busy-wait cycles to avoid deadlocks. Furthermore, to confirm a livelock potential, we orchestrate a partial-order schedule to induce a livelock during a program re-execution. We implemented our proposed approach in a prototype tool
CBuster
, comprising a light-weight binary instrumentation framework for
C/C++
programs to record events, and to replay partial-order schedules. We applied our approach to identify and confirm livelocks in a case study based on SQLite, a widely used embedded multi-threaded database engine.