DCAS-based concurrent deques

ABSTRACT

The computer industry is currently examining the use of strong synchronization operations such as double compare-and-swap (DCAS) as a means of supporting non-blocking synchronization on tomorrow's multiprocessor machines. However, before such a strong primitive will be incorporated into hardware design, its utility needs to be proven by developing a body of effective non-blocking data structures using DCAS. As part of this effort, we present two new linearizable non-blocking implementations of concurrent deques using the DCAS operation. The first uses an array representation, and improves on former algorithms by allowing uninterrupted concurrent access to both ends of the deque while correctly handling the difficult boundary cases when the deque is empty or full. The second uses a linked-list representation, and is the first non-blocking unbounded-memory deque implementation. It too allows uninterrupted concurrent access to both ends of the deque.

REFERENCES

• 1: Yehuda Afek , Michael Merritt , Gadi Taubenfeld , Dan Touitou, Disentangling multi-object operations (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.111-120, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259431]
• 2: AGESEN, O., AND CARTWRIGHT JR., R. S. Platform independent double compare and swap operation, Dec. 1998. U.S. Patent Application Express Mail Number EL092132504US Ref P3368.
• 3: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 4: Hagit Attiya , Eyal Dagan, Universal operations: unary versus binary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.223-232, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248097]
• 5: Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994 [doi>10.1145/179812.179902]
• 6: Hagit Attiya , Ophir Rachman, Atomic Snapshots in O (n log n) Operations, SIAM Journal on Computing, v.27 n.2, p.319-340, April 1998 [doi>10.1137/S0097539795279463]
• 7: 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]
• 8: BERSHAD, B. N. Practical considerations for nonblocking concurrent objects. In Proceedings 13th IEEE International Conference on Distributed Computing Systems (May 25-28 1993), IEEE Computer Society Press, pp. 264-273. Los Alamitos CA.
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 11: Michael Greenwald, Non-blocking Synchronization and System Design, Stanford University, Stanford, CA, 1999
• 12: 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
• 13: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 15: 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]
• 16: HERLIHY, M. P., AND Moss, J. Transactional memory: Architectural support for lock-free data structures. Tech. Rep. CRL 92//07, Digital Equipment Corporation, Cambridge Research Lab, 1992.
• 17: 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]
• 18: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 19: MASSALIN, H., AND PU, C. A lock-free multiprocessor OS kernel. Tech. Rep. TR CUCS-005-9, Columbia University, New York, NY, 1991.
• 20: Maged M. Michael , Michael L. Scott, Correction of a Memory Management Method for Lock-Free Data Structures, University of Rochester, Rochester, NY, 1995
• 21: CORPORATE MOTOROLA, MC68020 32-BIT microprocessor user's manual, Motorola Inc., Phoenix, AZ, 1991
• 22: MOTOROLA. MC68030 User's Manual. Prentice-Hall, 1989.
• 23: Martin C. Rinard, Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.337-371, Nov. 1999 [doi>10.1145/329466.329486]
• 24: SHAVIT, N., AND TOUITOU, D. Software transactional memory. Distributed Computing 10, 2 (February 1997), 99-116.
• 25: STEELE JR., G. L. Common Lisp. Digital Press, Digital Equipment Corporation, 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  E. Data

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Performance, Theory