Dreadlocks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dreadlocks: efficient deadlock detection

Full text

Pdf (440 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures table of contents

Munich, Germany

SESSION: Special track -- STM design and locks table of contents

Pages 297-303

Year of Publication: 2008

ISBN:978-1-59593-973-9

Authors

Eric Koskinen	Brown University, Providence, RI, USA
Maurice Herlihy	Brown University, Providence, RI, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 125, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1378533.1378585 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
	2	Broder, A., and Mitzenmacher, M. Network Applications of Bloom Filters: A Survey. Internet Mathematics 1, 4 (2004), 485--509.
	3	James C. Corbett, Evaluating Deadlock Detection Methods for Concurrent Software, IEEE Transactions on Software Engineering, v.22 n.3, p.161-180, March 1996 [doi>10.1109/32.489078]
	4	Claudio DeMartini , Radu Iosif , Riccardo Sisto, A deadlock detection tool for concurrent Java programs, Software—Practice & Experience, v.29 n.7, p.577-603, June 1999 [doi>10.1002/(SICI)1097-024X(199906)29:7<577::AID-SPE246>3.0.CO;2-V]
	5	Dice, D., Shalev, O., and Shavit, N. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC'06)(September 2006).
	6	Dice, D., and Shavit, N. What really makes transactions fast. ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June(2006).
	7	Ennals, R. Software transactional memory should not be obstruction-free. Unpublished manuscript, Intel Research Cambridge(2005).
	8	Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345237]
	9	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	10	Holzmann, G. The Spin Model Checker: Primer and Reference Manual. Addison-Wesley, 2004.
	11	Nima Kaveh , Wolfgang Emmerich, Deadlock detection in distribution object systems, ACM SIGSOFT Software Engineering Notes, v.26 n.5, Sept. 2001
	12	Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987 [doi>10.1145/45075.46163]
	13	Tong Li , Carla S. Ellis , Alvin R. Lebeck , Daniel J. Sorin, Pulse: a dynamic deadlock detection mechanism using speculative execution, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, April 10-15, 2005, Anaheim, CA
	14	Luecke, G., Zou, Y., Coyle, J., Hoekstra, J., and Kraeva, M. Deadlock detection in MPI programs. Concurrency and Computation: Practice and Experience 14, 11 (2002), 911--932.
	15	Erich Mikk , Yassine Lakhnech , Michael Siegel , Gerard J. Holzmann, Implementing Statecharts in PROMELA/SPIN, Proceedings of the Second IEEE Workshop on Industrial Strength Formal Specification Techniques, p.90, October 20-23, 1998
	16	Tadao Murata , Sol M. Shatz , Boris Shenker, Detection of Ada Static Deadlocks Using Petri Net Invariants, IEEE Transactions on Software Engineering, v.15 n.3, p.314-326, March 1989 [doi>10.1109/32.21759]
	17	Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
	18	Michael L. Scott, Non-blocking timeout in scalable queue-based spin locks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571830]
	19	M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989 [doi>10.1109/2.43525]
	20	Jeffrey S. Vetter , Bronis R. de Supinski, Dynamic software testing of MPI applications with umpire, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.51-es, November 04-10, 2000, Dallas, Texas, United States