Concurrent programming without locks

ABSTRACT

Mutual exclusion locks remain the de facto mechanism for concurrency control on shared-memory data structures. However, their apparent simplicity is deceptive: It is hard to design scalable locking strategies because locks can harbor problems such as priority inversion, deadlock, and convoying. Furthermore, scalable lock-based systems are not readily composable when building compound operations. In looking for solutions to these problems, interest has developed in nonblocking systems which have promised scalability and robustness by eschewing mutual exclusion while still ensuring safety. However, existing techniques for building nonblocking systems are rarely suitable for practical use, imposing substantial storage overheads, serializing nonconflicting operations, or requiring instructions not readily available on today's CPUs.

In this article we present three APIs which make it easier to develop nonblocking implementations of arbitrary data structures. The first API is a multiword compare-and-swap operation (MCAS) which atomically updates a set of memory locations. This can be used to advance a data structure from one consistent state to another. The second API is a word-based software transactional memory (WSTM) which can allow sequential code to be reused more directly than with MCAS and which provides better scalability when locations are being read rather than being updated. The third API is an object-based software transactional memory (OSTM). OSTM allows a simpler implementation than WSTM, but at the cost of reengineering the code to use OSTM objects.

We present practical implementations of all three of these APIs, built from operations available across all of today's major CPU families. We illustrate the use of these APIs by using them to build highly concurrent skip lists and red-black trees. We compare the performance of the resulting implementations against one another and against high-performance lock-based systems. These results demonstrate that it is possible to build useful nonblocking data structures with performance comparable to, or better than, sophisticated lock-based designs.

REFERENCES

• 1: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 2: James H. Anderson , Mark Moir, Universal constructions for multi-object operations, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.184-193, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224985]
• 3: James H. Anderson , Srikanth Ramamurthy , Rohit Jain, Implementing wait-free objects on priority-based systems, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.229-238, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259443]
• 4: Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165265]
• 5: Dice, D., Shalev, O., and Shavit, N. 2006. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC).
• 6: Fich, F., Luchangco, V., Moir, M., and Shavit, N. 2005. Obstruction-Free algorithms can be practically wait-free. In Distributed Algorithms, P. Fraigniaud, Ed. Lecture Notes in Computer Science, vol. 3724. Springer Verlag, Berlin. 78--92.
• 7: Fraser, K. 2003. Practical lock freedom. Ph.D. thesis, Computer Laboratory, University of Cambridge. Also available as Tech. Rep. UCAM-CL-TR-639, Cambridge University.
• 8: Michael Greenwald, Non-blocking Synchronization and System Design, Stanford University, Stanford, CA, 1999
• 9: 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]
• 10: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 11: Sabine Hanke, The Performance of Concurrent Red-Black Tree Algorithms, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.286-300, July 19-21, 1999
• 12: Sabine Hanke , Thomas Ottmann , Eljas Soisalon-Soininen, Relaxed Balanced Red-Black Trees, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.193-204, March 12-14, 1997
• 13: Timothy L. Harris, A Pragmatic Implementation of Non-blocking Linked-Lists, Proceedings of the 15th International Conference on Distributed Computing, p.300-314, October 03-05, 2001
• 14: Harris, T. 2004. Exceptions and side-effects in atomic blocks. In Proceedings of the PODC Workshop on Synchronization in Java Programs. 46--53. Proceedings published as Memorial University of Newfoundland CS Tech. Rep. 2004-01.
• 15: 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
• 16: Tim Harris , Keir Fraser, Revocable locks for non-blocking programming, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065954]
• 17: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 18: Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer, B., and Shavit, N. 2005. A lazy concurrent list-based set algorithm. In 9th International Conference on Principles of Distributed Systems (OPODIS).
• 19: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 20: 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]
• 21: Herlihy, M. 2005. SXM1.1: Software transactional memory package for C#. Tech. Rep., Brown University and Microsoft Research. May.
• 22: Maurice Herlihy , Victor Luchangco , Paul Martin , Mark Moir, Nonblocking memory management support for dynamic-sized data structures, ACM Transactions on Computer Systems (TOCS), v.23 n.2, p.146-196, May 2005 [doi>10.1145/1062247.1062249]
• 23: 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
• 24: 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]
• 25: 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
• 26: 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]
• 27: Hoare, C. A. R. 1972. Towards a theory of parallel programming. In Operating Systems Techniques. A.P.I.C. Studies in Data Processing, vol. 9. Academic Press, 61--71.
• 28: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 29: 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]
• 30: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 31: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 32: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 33: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 34: Austen McDonald , JaeWoong Chung , Hassan Chafi , Chi Cao Minh , Brian D. Carlstrom , Lance Hammond , Christos Kozyrakis , Kunle Olukotun, Characterization of TCC on Chip-Multiprocessors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.63-74, September 17-21, 2005 [doi>10.1109/PACT.2005.11]
• 35: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 36: John M. Mellor-Crummey , Michael L. Scott, Scalable reader-writer synchronization for shared-memory multiprocessors, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.106-113, April 21-24, 1991, Williamsburg, Virginia, United States
• 37: 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]
• 38: Maged M. Michael , Michael L. Scott, Correction of a Memory Management Method for Lock-Free Data Structures, University of Rochester, Rochester, NY, 1995
• 39: Mark Moir, Transparent Support for Wait-Free Transactions, Proceedings of the 11th International Workshop on Distributed Algorithms, p.305-319, September 24-26, 1997
• 40: Moir, M. 2002. Personal communication.
• 41: Moore, K. E., Hill, M. D., and Wood, D. A. 2005. Thread-Level transactional memory. Tech. Rep.: CS-TR-2005-1524, Deptartment of Computer Sciences, University of Wisconsin, Motorola Inc., Phoenix, AZ. 1--11.
• 42: CORPORATE MOTOROLA, MC68020 32-BIT microprocessor user's manual, Motorola Inc., Phoenix, AZ, 1991
• 43: William Pugh, Concurrent maintenance of skip lists, University of Maryland at College Park, College Park, MD, 1990
• 44: Rajwar, R. and Goodman, J. R. 2002. Transactional lock-free execution of lock-based programs. ACM SIGPLAN Not. 37, 10 (Oct.), 5--17.
• 45: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 46: Riegel, T., Felber, P., and Fetzer, C. 2006. A lazy snapshot algorithm with eager validation. In Proceedings of the 20th International Symposium on Distributed Computing (DISC).
• 47: Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 48: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 49: Ori Shalev , Nir Shavit, Split-ordered lists: lock-free extensible hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.102-111, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872049]
• 50: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 51: Håkan Sundell , Philippas Tsigas, Scalable and lock-free concurrent dictionaries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968188]
• 52: John Turek , Dennis Shasha , Sundeep Prakash, Locking without blocking: making lock based concurrent data structure algorithms nonblocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.212-222, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137873]
• 53: Welc, A., Jagannathan, S., and Hosking, T. 2004. Transactional monitors for concurrent objects. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP). 519--542.
• 54: Jeannette M. Wing , Chun Gong, Testing and verifying concurrent objects, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.164-182, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1015]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization; Mutual exclusion

Keywords:
Concurrency, lock-free systems, transactional memory