Dreadlocks: Efficient deadlock detection

Eric Koskinen, Maurice Herlihy

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Scopus citations

Abstract

We present Dreadlocks, an efficient new shared-memory spin lock that actively detects deadlocks. Instead of spinning on a Boolean value, each thread spins on the lock owner's per-thread digest, a compact representation of a portion of the lock's waits-for graph. Digests can be implemented either as bit vectors (for small numbers of threads) or as Bloom filters (for larger numbers of threads). Updates to digests are propagated dynamically as locks are acquired and released. Dreadlocks can be applied to any spin lock algorithm that allows threads to time out. Experimental results show that Dreadlocks outperform timeouts under many circumstances, and almost never do worse.

Original languageEnglish
Title of host publicationSPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures
Pages297-303
Number of pages7
DOIs
StatePublished - 2008
Event20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08 - Munich, Germany
Duration: 14 Jun 200816 Jun 2008

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08
Country/TerritoryGermany
CityMunich
Period14/06/0816/06/08

Keywords

  • Bloom filters
  • Concurrency
  • Deadlock
  • Deadlock detection
  • Parallel programming
  • Transactional memory

Fingerprint

Dive into the research topics of 'Dreadlocks: Efficient deadlock detection'. Together they form a unique fingerprint.

Cite this