Scalable reader-writer locks

ABSTRACT

We present three new reader-writer lock algorithms that scale under high read-only contention. Many previous reader-writer locks suffer significant degradation when many readers attempt to acquire the lock concurrently, even though they are all allowed to hold the lock at the same time. In contrast, our locks scale almost perfectly when there is only read contention on a 4-chip system with a total of 256 hardware threads.

Two of the algorithms extend the MCS queue mutex to provide reader-writer synchronization with low overhead, and can be used when busy-waiting synchronization is appropriate. The third algorithm is an improvement on a production-quality reader-writer lock used in the SolarisTM kernel, which provides robust priority and flexible fairness guarantees.

A key tool we developed to implement our reader-writer locks is the closable scalable nonzero indicator (C-SNZI), a variation on the SNZI object. C-SNZI objects allow us to significantly reduce the contention among reads when many readers try to acquire the lock concurrently, but keeps the acquisition overhead small in the absence of read contention. We present an algorithm for C-SNZI that achieves this goal, and show how it can be used by each of our lock algorithms to provide scalable reader-writer locks with different fairness guarantees.

REFERENCES

• 1: Source code for kernel reader-writer lock in Open Solaris. Open Solaris OpenGrok, 2009. {online} http: //src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/rwlock.c.
• 2: Bryan Cantrill , Jeff Bonwick, Real-world concurrency, Communications of the ACM, v.51 n.11, November 2008 [doi>10.1145/1400214.1400227]
• 3: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 4: D. Dice and N. Shavit. TLRW: Return of the read-write lock. In TRANSACT '09: Proceedings of the Fourth ACM SIGPLAN Workshop on Transactional Computing, 2009.
• 5: Faith Ellen , Yossi Lev , Victor Luchangco , Mark Moir, SNZI: scalable NonZero indicators, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281106]
• 6: G. Grohoski. Niagara-2: A highly threaded server-on-a-chip. In HotChips 18: Proceedings of the Eighteenth IEEE HotChips Symposium on High-Performance Chips, 2006.
• 7: Wilson C. Hsieh , William E. Weihl, Scalable Reader-Writer Locks for Parallel Systems, Proceedings of the 6th International Parallel Processing Symposium, p.656-659, March 01, 1992
• 8: Orran Krieger , Michael Stumm , Ron Unrau , Jonathan Hanna, A Fair Fast Scalable Rea,der-Writer Lock, Proceedings of the 1993 International Conference on Parallel Processing, p.201-204, August 16-20, 1993 [doi>10.1109/ICPP.1993.21]
• 9: Y. Lev, V. Luchangco, V. Marathe, M. Moir, D. Nussbaum, and M. Olszewski. Anatomy of a scalable software transactional memory. In TRANSACT '09: Proceedings of the Fourth ACM SIGPLAN Workshop on Transactional Computing, 2009.
• 10: 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]
• 11: 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
• 12: John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.269-278, April 08-11, 1991, Santa Clara, California, United States

INDEX TERMS

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

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

General Terms:
Algorithms, Performance

Keywords:
reader-writer lock, scalable, snzi, synchronization