Non-blocking timeout in scalable queue-based spin locks

ABSTRACT

Queue-based spin locks allow programs with busy-wait synchronization to scale to very large multiprocessors, without fear of starvation or performance-destroying contention. Timeout-capable spin locks allow a thread to abandon its attempt to acquire a lock; they are used widely in real-time systems to avoid overshooting a deadline, and in database systems to recover from transaction deadlock and to tolerate preemption of the thread that holds a lock.In previous work we showed how to incorporate timeout in scalable queue-based locks. Technological trends suggest that this combination will be of increasing commercial importance. Our previous solutions, however, require a thread that is timing out to handshake with its neighbors in the queue, a requirement that may lead to indefinite delay in a preemptively multiprogrammed system.In the current paper we present new queue-based locks in which the timeout code is non-blocking. These locks sacrifice the constant worst-case space per thread of our previous algorithms, but allow us to bound the time that a thread may be delayed by preemption of its peers. We present empirical results indicating that space needs are modest in practice, and that performance scales well to large machines. We also conjecture that constant per-thread space cannot be guaranteed together with non-blocking timeout in a queue-based lock.

REFERENCES

• 1: Anant Agarwal , Ricardo Bianchini , David Chaiken , Kirk L. Johnson , David Kranz , John Kubiatowicz , Beng-Hong Lim , Kenneth Mackenzie , Donald Yeung, The MIT Alewife machine: architecture and performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.2-13, June 22-24, 1995, S. Margherita Ligure, Italy
• 2: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 3: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.53-79, Feb. 1992 [doi>10.1145/146941.146944]
• 4: David L. Black, Scheduling Support for Concurrency and Parallelism in the Mach Operating System, Computer, v.23 n.5, p.35-43, May 1990 [doi>10.1109/2.53353]
• 5: T. S. Craig. Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, Department of Computer Science, University of Washington, Feb. 1993.
• 6: J. Edler, J. Lipkis, and E. Schonberg. Process management for highly parallel UNIX systems. In USENIX Workshop on Unix and Supercomputers, pages 1-17, Pittsburgh, PA, Sep. 1988.
• 7: Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501]
• 8: M. Herlihy. Personal communication, Oct. 2001.
• 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: Leonidas I. Kontothanassis , Robert W. Wisniewski , Michael L. Scott, Scheduler-conscious synchronization, ACM Transactions on Computer Systems (TOCS), v.15 n.1, p.3-40, Feb. 1997 [doi>10.1145/244764.244765]
• 11: Sanjeev Kumar , Dongming Jiang , Rohit Chandra , Jaswinder Pal Singh, Evaluating synchronization on shared address space multiprocessors: methodology and performance, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.23-34, May 01-04, 1999, Atlanta, Georgia, United States
• 12: Beng-Hong Lim , Anant Agarwal, Reactive synchronization algorithms for multiprocessors, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.25-35, October 05-07, 1994, San Jose, California, United States
• 13: V. Luchangco. Personal communication, Jan. 2002.
• 14: Peter S. Magnusson , Anders Landin , Erik Hagersten, Queue Locks on Cache Coherent Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.165-171, April 01, 1994
• 15: Brian D. Marsh , Michael L. Scott , Thomas J. LeBlanc , Evangelos P. Markatos, First-class user-level threads, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.110-121, October 13-16, 1991, Pacific Grove, California, United States
• 16: 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]
• 17: J. K. Ousterhout. Scheduling techniques for concurrent systems. In 3rd Intl. Conf. on Distributed Computing Systems, pages 22-30, Miami/Ft. Lauderdale, FL, Oct. 1982.
• 18: M. L. Scott, Non-Blocking Timeout in Scalable Queue-Based Spin Locks, University of Rochester, Rochester, NY, 2002
• 19: 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
• 20: Ronald C. Unrau , Orran Krieger , Benjamin Gamsa , Michael Stumm, Hierarchical clustering: a structure for scalable multiprocessor operating system design, The Journal of Supercomputing, v.9 n.1-2, p.105-134, 1995 [doi>10.1007/BF01245400]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
scalability, spin locks, synchronization, timeout