Revocable locks for non-blocking programming

ABSTRACT

In this paper we present a new form of revocable lock that streamlines the construction of higher level concurrency abstractions such as atomic multi-word heap updates. The key idea is to expose revocation by displacing the previous lock holder's execution to a safe address. This provides mutual exclusion without needing to block threads. This brings many simplifications, often removing the need for dynamic memory management and letting us strip operations from common-case execution paths. As well as streamlining algorithms' design, our results show that the technique leads to improved performance and scalability across a range of levels of contention.

REFERENCES

• 1: CORPORATE Motorola, Inc., M68000 family programmer's reference manual, Motorola Inc., Phoenix, AZ, 1991
• 2: Juan Alemany , Edward W. Felten, Performance issues in non-blocking synchronization on shared-memory multiprocessors, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.125-134, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135446]
• 3: Bershad, B. N. Practical considerations for non-blocking concurrent objects. Technical Report CMU-CS-91-116, Carnegie Mellon University, School of Computer Science, Oct. 1991.
• 4: Burrows, M. How to implement unnecessary mutexes. In Computer Systems: Theory, Technology and Applications (Dec. 2003), Springer-Verlag.
• 5: Dave Dice , Alex Garthwaite, Mostly lock-free malloc, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 6: Fraser, K. Practical lock freedom. PhD thesis, University of Cambridge Computer Laboratory, 2003.
• 7: C. Gray , D. Cheriton, Leases: an efficient fault-tolerant mechanism for distributed file cache consistency, Proceedings of the twelfth ACM symposium on Operating systems principles, p.202-210, November 1989
• 8: Michael Greenwald, Two-handed emulation: how to build non-blocking implementations of complex data-structures using DCAS, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571874]
• 9: Michael Greenwald , David Cheriton, The synergy between non-blocking synchronization and operating system structure, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.123-136, October 29-November 01, 1996, Seattle, Washington, United States
• 10: Harris, T. Exceptions and side-effects in atomic blocks. In Proceedings of the 2004 Workshop on Concurrency and Synchronization in Java programs (July 2004), pp. 46--53. Proceedings published as Memorial University of Newfoundland CS Technical Report 2004-01.
• 11: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 12: Timothy L. Harris , Keir Fraser , Ian A. Pratt, A Practical Multi-word Compare-and-Swap Operation, Proceedings of the 16th International Conference on Distributed Computing, p.265-279, October 28-30, 2002
• 13: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 14: Maurice Herlihy , Victor Luchangco , Mark Moir, The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures, Proceedings of the 16th International Conference on Distributed Computing, p.339-353, October 28-30, 2002
• 15: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 16: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 17: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 18: Prasad Jayanti , Srdjan Petrovic, Efficient and practical constructions of LL/SC variables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.285-294, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872078]
• 19: Kiyokuni Kawachiya , Akira Koseki , Tamiya Onodera, Lock reservation: Java locks can mostly do without atomic operations, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 20: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 21: Michael, M. M. ABA prevention using single-word instructions. Tech. Rep. RC-23089, IBM Research Division, Jan. 2004.
• 22: Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259442]
• 23: Pizlo, F., Prochazka, M., Jagannathan, S., and Vitek, J. Transactional lock-free objects for real-time Java. In Proceedings of the 2004 PODC Workshop on Concurrency and Synchronization in Java Programs (July 2004).
• 24: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 25: Rajwar, R., and Goodman, J. R. Transactional lock-free execution of lock-based programs. ACM SIG PLAN Notices 37, 10 (Oct. 2002), 5--17.
• 26: Shavit, N., and Touitou, D. Software transactional memory. Distributed Computing, Special Issue 10, 2 (1997), 99--116.
• 27: Adam Welc , Antony L. Hosking , Suresh Jagannathan, Preemption-Based Avoidance of Priority Inversion for Java, Proceedings of the 2004 International Conference on Parallel Processing (ICPP'04), p.529-538, August 15-18, 2004 [doi>10.1109/ICPP.2004.60]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Threads; Synchronization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
locks, non-blocking algorithms, transactional memory