Readers–writer lock

In computer science, a readers–writer (RW) or shared-exclusive lock (also known as a multiple readers/single-writer lock^[1] or multi-reader lock^[2]) is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing. A common use might be to control access to a data structure in memory that cannot be updated atomically and is invalid (and should not be read by another thread) until the update is complete.

Readers–writer locks are usually constructed on top of mutexes and condition variables, or on top of semaphores.

Upgradable RW lock

Some RW locks allow the lock to be atomically upgraded from being locked in read-mode to write-mode, as well as being downgraded from write-mode to read-mode.

Priority policies

RW locks can be designed with different priority policies for reader vs. writer access. The lock can either be designed to always give priority to readers (read-preferring), to always give priority to writers (write-preferring) or be unspecified with regards to priority. These policies lead to different tradeoffs with regards to concurrency and starvation.

• Read-preferring RW locks allow for maximum concurrency, but can lead to write-starvation if contention is high. This is because writer threads will not be able to acquire the lock as long as at least one reading thread holds it. Since multiple reader threads may hold the lock at once, this means that a writer thread may continue waiting for the lock while new reader threads are able to acquire the lock, even to the point where the writer may still be waiting after all of the readers which were holding the lock when it first attempted to acquire it have released the lock. Priority to readers may be weak, as just described, or strong, meaning that whenever a writer releases the lock, any blocking readers always acquire it next.^[3]:76
• Write-preferring RW locks avoid the problem of writer starvation by preventing any new readers from acquiring the lock if there is a writer queued and waiting for the lock; the writer will acquire the lock as soon as all readers which were already holding the lock have completed.^[4] The downside is that write-preferring locks allows for less concurrency in the presence of writer threads, compared to read-preferring RW locks. Also the lock is less performant because each operation, taking or releasing the lock for either read or write, is more complex, internally requiring taking and releasing two mutexes instead of one. This variation is sometimes also known as "write-biased" readers–writer lock.^[5]
• Unspecified priority RW locks does not provide any guarantees with regards read vs. write access. Unspecified priority can in some situations be preferable if it allows for a more efficient implementation.

Implementation

Several implementation strategies for readers–writer locks exist, reducing them to synchronization primitives that are assumed to pre-exist.

Using two mutexes

Raynal demonstrates how to implement an R/W lock using two mutexes and a single integer counter. The counter, b, tracks the number of blocking readers. One mutex, r, protects b and is only used by readers; the other, g (for "global") ensures mutual exclusion of writers. The following is pseudocode for the lock-for-read operation:

• Lock r.
• Increment b.
• If b = 1, lock g.
• Unlock r.

Readers use a similar operation for unlocking, that, while holding the lock r, decrements b and unlocks g if this causes b to become equal to zero. Writers simply lock and unlock g directly. This implementation strategy gives weak priority to readers.^[3]:76

Using a condition variable and a mutex

Alternatively, a read-preferring R/W lock can be implemented in terms of a condition variable and an ordinary (mutex) lock, in addition to an integer counter and a boolean flag. The lock-for-read operation in this setup is:^[6][7][8]

• Input: mutex m, condition variable c, integer r (number of readers waiting), flag w (writer waiting).
• Lock m (blocking).
• While w:
  • wait c, m^{[lower-alpha 1]}
• Increment r.
• Unlock m.

The lock-for-write operation is similar, but slightly different (inputs are the same as for lock-for-read):^[6][7][8]

• Lock m (blocking).
• While (w or r > 0):
  • wait c, m
• Set w to true.
• Unlock m.

Each of lock-for-read and lock-for-write has its own inverse operation. Releasing a read lock is done by decrementing r and signalling c if r has become zero (both while holding m), so that one of the threads waiting on c can wake up and lock the R/W lock. Releasing the write lock means setting w to false and broadcasting on c (again while holding m).^[6][7][8]

Programming language support

• POSIX standard pthread_rwlock_t and associated operations^[9]
• ReadWriteLock^[10] interface and the ReentrantReadWriteLock^[11] locks in Java version 5 or above
• Microsoft System.Threading.ReaderWriterLockSlim lock for C# and other .NET languages^[12]
• std::shared_mutex read/write lock in C++14^[13]
• boost::shared_mutex and boost::upgrade_mutex locks in Boost C++ Libraries^[14]
• SRWLock, added to the Windows operating system API as of Windows Vista.^[15]
• sync.RWMutex in Go^[16]
• Phase fair reader–writer lock, which alternates between readers and writers^[17]
• std::sync::RwLock read/write lock in Rust^[18]

Alternatives

The read-copy-update (RCU) algorithm is one solution to the readers–writers problem. RCU is wait-free for readers. The Linux kernel implements a special solution for few writers called seqlock.

See also

• Semaphore (programming)
• Mutual exclusion
• Scheduler pattern
• Balking pattern
• File locking
• Lock (computer science)

Notes

1. This is the standard "wait" operation on condition variables, which, among other actions, releases the mutex m.

References

1. Hamilton, Doug (21 April 1995). "Suggestions for multiple-reader/single-writer lock?". Newsgroup: comp.os.ms-windows.nt.misc. Usenet: [e-mail]. Retrieved 8 October 2010.
2. "Practical lock-freedom" by Keir Fraser 2004
3. Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer.
4. Stevens, W. Richard; Rago, Stephen A. (2013). Advanced Programming in the UNIX Environment. Addison-Wesley. p. 409.
5. java.util.concurrent.locks.ReentrantReadWriteLock Java readers–writer lock implementation offers a "fair" mode
6. Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. pp. 184–185.
7. Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline (1996). PThreads Programming: A POSIX Standard for Better Multiprocessing. O'Reilly. pp. 84–89.
8. Butenhof, David R. (1997). Programming with POSIX Threads. Addison-Wesley. pp. 253–266.
9. "The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy". The IEEE and The Open Group. Retrieved 14 May 2011.
10. java.util.concurrent.locks.ReadWriteLock
11. java.util.concurrent.locks.ReentrantReadWriteLock
12. "ReaderWriteLockSlim Class (System.Threading)". Microsoft Corporation. Retrieved 14 May 2011.
13. "New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm". Standard C++ Foundation.
14. Anthony Williams. "Synchronization – Boost 1.52.0". Retrieved 31 Jan 2012.
15. Alessandrini, Victor (2015). Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming. Morgan Kaufmann.
16. "The Go Programming language - Package sync". Retrieved 30 May 2015.
17. "Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems" (PDF).
18. "std::sync::RwLock - Rust". Retrieved 10 December 2015.