Scalable synchronous queues

ABSTRACT

We present two new nonblocking and contention-free implementations of synchronous queues ,concurrent transfer channels in which producers wait for consumers just as consumers wait for producers. Our implementations extend our previous work in dual queues and dual stacks to effect very high-performance handoff. We present performance results on 16-processor SPARC and 4-processor Opteron machines. We compare our algorithms to commonly used alternatives from the literature and from the Java SE 5.0 class java. util. concurrent. SynchronousQueue both directly in synthetic microbenchmarks and indirectly as the core of Java's Thread-PoolExecutor mechanism (which in turn is the core of many Java server programs).Our new algorithms consistently outperform the Java SE 5.0 SynchronousQueue by factors of three in unfair mode and 14 in fair mode; this translates to factors of two and ten for the ThreadPoolExecutor. Our synchronous queues have been adopted for inclusion in Java 6.

REFERENCES

• 1: T. E. Anderson , E. D. Lazowska , H. M. Levy, The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.38 n.12, p.1631-1644, December 1989 [doi>10.1109/12.40843]
• 2: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 3: David R. Hanson, C interfaces and implementations: techniques for creating reusable software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 4: Danny Hendler , Nir Shavit , Lena Yerushalmi, A scalable lock-free stack algorithm, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007944]
• 5: 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
• 6: 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]
• 7: 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]
• 8: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 9: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 10: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 11: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 12: D. Lea. The java.util. concurrent Synchronizer Framework. Science of Computer Programming, 58(3):293--309, Dec. 2005.
• 13: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 14: 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]
• 15: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 16: Mark Moir , Daniel Nussbaum , Ori Shalev , Nir Shavit, Using elimination to implement scalable and lock-free FIFO queues, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074013]
• 17: W.N. Scherer III and M.L. Scott. Nonblocking Concurrent Objects with Condition Synchronization. In Proc. of the 18th Intl. Symp. on Distributed Computing, Amsterdam, The Netherlands, Oct. 2004.
• 18: W.N. Scherer III, D. Lea, and M.L. Scott. A Scalable Elimination-based Exchange Channel. In Proc., Workshop on Synchronization and Concurrency in Object-Oriented Languages, San Diego, CA, Oct. 2005. In conjunction with OOPSLA'05.
• 19: W.N. Scherer III. Synchronization and Concurrency in User-level Software Systems. Ph.D. dissertation, Dept. of Computer Science, Univ. of Rochester, Jan. 2006.
• 20: Michael L. Scott , William N. Scherer, Scalable queue-based spin locks with timeout, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.44-52, June 2001, Snowbird, Utah, United States
• 21: Nir Shavit , Dan Touitou, Elimination trees and the construction of pools and stacks: preliminary version, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215419]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
contention freedom, dual data structures, dual queue, dual stack, lock freedom, nonblocking synchronization, synchronous queue