TY - GEN
T1 - Dreadlocks
T2 - 20th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'08
AU - Koskinen, Eric
AU - Herlihy, Maurice
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Bloom filters
KW - Concurrency
KW - Deadlock
KW - Deadlock detection
KW - Parallel programming
KW - Transactional memory
UR - http://www.scopus.com/inward/record.url?scp=57349141427&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57349141427&partnerID=8YFLogxK
U2 - 10.1145/1378533.1378585
DO - 10.1145/1378533.1378585
M3 - Conference contribution
AN - SCOPUS:57349141427
SN - 9781595939739
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 297
EP - 303
BT - SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures
Y2 - 14 June 2008 through 16 June 2008
ER -