Readers–writer lock

Short description: Synchronization primitive in computing

Not to be confused with Writer's block.

In computer science, a readers–writer (single-writer lock,[1] a multi-reader lock,[2] a push lock,[3] or an MRSW lock) is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, whereas 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 and 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.

## Contents

* 1 Upgradable RW lock
* 2 Priority policies
* 3 Implementation
* 3.1 Using two mutexes
* 3.2 Using a condition variable and a mutex
* 4 Programming language support
* 4.1 Example in Rust
* 5 Alternatives
* 6 See also
* 7 Notes
* 8 References

## 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.[4] Upgrading a lock from read-mode to write-mode is prone to deadlocks, since whenever two threads holding reader locks both attempt to upgrade to writer locks, a deadlock is created that can only be broken by one of the threads releasing its reader lock. The deadlock can be avoided by allowing only one thread to acquire the lock in "read-mode with intent to upgrade to write" while there are no threads in write mode and possibly non-zero threads in 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.[5]: 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.[6] 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.[7]

## 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. This requires that a mutex acquired by one thread can be released by another. The following is pseudocode for the operations:

Initialize

Set b to 0.
r is unlocked.
g is unlocked.

Begin read

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

End read

Lock r.
Decrement b.
If b = 0, unlock g.
Unlock r.

Begin write

Lock g.

End write

Unlock g.

This implementation is read-preferring.[5]: 76

### Using a condition variable and a mutex

Alternatively an RW lock can be implemented in terms of a condition variable, cond, an ordinary (mutex) lock, g, and various counters and flags describing the threads that are currently active or waiting.[8][9][10] For a write-preferring RW lock one can use two integer counters and one Boolean flag:

num_readers_active: the number of readers that have acquired the lock (integer)
num_writers_waiting: the number of writers waiting for access (integer)
writer_active: whether a writer has acquired the lock (Boolean).

Initially num_readers_active and num_writers_waiting are zero and writer_active is false.

The lock and release operations can be implemented as

Begin read

Lock g
While num_writers_waiting > 0 or writer_active:
wait cond, g[lower-alpha 1]
Increment num_readers_active
Unlock g.

End read

Lock g
Decrement num_readers_active
If num_readers_active = 0:
Notify cond (broadcast)
Unlock g.

Begin write

Lock g
Increment num_writers_waiting
While num_readers_active > 0 or writer_active is true:
wait cond, g
Decrement num_writers_waiting
Set writer_active to true
Unlock g.

End write

Lock g
Set writer_active to false
Notify cond (broadcast)
Unlock g.

## Programming language support

* POSIX standard `pthread_rwlock_t` and associated operations[11]
* ReadWriteLock[12] interface and the ReentrantReadWriteLock[7] locks in Java version 5 or above
* Microsoft `System.Threading.ReaderWriterLockSlim` lock for C# and other .NET languages[13]
* `std::shared_mutex` read/write lock in C++17[14]
* `boost::shared_mutex` and `boost::upgrade_mutex` locks in Boost C++ Libraries[15]
* `SRWLock`, added to the Windows operating system API as of Windows Vista.[16]
* `sync.RWMutex` in Go[17]
* Phase fair reader–writer lock, which alternates between readers and writers[18]
* `std::sync::RwLock` read/write lock in Rust[19]
* Poco::RWLock in POCO C++ Libraries
* `mse::recursive_shared_timed_mutex` in the SaferCPlusPlus library is a version of `std::shared_timed_mutex` that supports the recursive ownership semantics of `std::recursive_mutex`.
* `txrwlock.ReadersWriterDeferredLock` Readers/Writer Lock for Twisted[20]
* `rw_semaphore` in the Linux kernel[21]

### Example in Rust

use std::sync::RwLock;

let lock = RwLock::new(5);

// many reader locks can be held at once

let r1 = lock.read().unwrap();
let r2 = lock.read().unwrap();
assert_eq!(*r1, 5);
assert_eq!(*r2, 5);
} // read locks are dropped at this point

// only one write lock may be held, however

let mut w = lock.write().unwrap();
*w += 1;
assert_eq!(*w, 6);
} // write lock is dropped here

## 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)
* Readers–writers problem

## Notes

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

## References

1. ↑ Hamilton, Doug (21 April 1995). "Suggestions for multiple-reader/single-writer lock?". Newsgroup: comp.os.ms-windows.nt.misc. Usenet: hamilton.798430053@BIX.com. Retrieved 8 October 2010.
2. ↑ "Practical lock-freedom" by Keir Fraser 2004
3. ↑ "Push Locks – What are they?". MSDN Blogs. 2009-09-02. https://blogs.msdn.microsoft.com/ntdebugging/2009/09/02/push-locks-what-are-they/.
4. ↑ "Synchronization § UpgradeLockable Concept – EXTENSION". http://www.boost.org/doc/html/thread/synchronization.html#thread.synchronization.mutex_concepts.upgrade_lockable.
5. ↑ 5.0 5.1 Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer.
6. ↑ Stevens, W. Richard; Rago, Stephen A. (2013). Advanced Programming in the UNIX Environment. Addison-Wesley. p. 409.
7. ↑ 7.0 7.1 `java.util.concurrent.locks.ReentrantReadWriteLock` Java readers–writer lock implementation offers a "fair" mode
8. ↑ Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming. Elsevier. pp. 184–185.
9. ↑ Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline (1996). PThreads Programming: A POSIX Standard for Better Multiprocessing. O'Reilly. pp. 84–89. ISBN 9781565921153. https://archive.org/details/pthreadsprogramm00nich.
10. ↑ Butenhof, David R. (1997). Programming with POSIX Threads. Addison-Wesley. pp. 253–266.
11. ↑ "The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy". The IEEE and The Open Group. http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_init.html.
12. ↑ `java.util.concurrent.locks.ReadWriteLock`
13. ↑ "ReaderWriteLockSlim Class (System.Threading)". Microsoft Corporation. http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx.
14. ↑ "New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm". Standard C++ Foundation. http://isocpp.org/blog/2013/04/n3659-shared-locking.
15. ↑ Anthony Williams. "Synchronization – Boost 1.52.0". http://www.boost.org/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex.
16. ↑ Alessandrini, Victor (2015). Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming. Morgan Kaufmann.
17. ↑ "The Go Programming language – Package sync". https://golang.org/pkg/sync/#RWMutex.
18. ↑ "Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems". http://www.cs.unc.edu/~anderson/papers/ecrts09b.pdf.
19. ↑ "std::sync::RwLock – Rust". https://doc.rust-lang.org/std/sync/struct.RwLock.html.
20. ↑ "Readers/Writer Lock for Twisted". https://github.com/Stibbons/txrwlock.
21. ↑ "Synchronization primitives in the Linux kernel: Reader/Writer semaphores". https://0xax.gitbooks.io/linux-insides/content/SyncPrim/linux-sync-5.html.

* v
* t
* e

Software design patterns

Creational|

* Abstract factory
* Builder
* Dependency injection
* Factory method
* Lazy initialization
* Multiton
* Object pool
* Prototype
* RAII
* Singleton

Structural|

* Adapter
* Bridge
* Composite
* Decorator
* Delegation
* Facade
* Flyweight
* Front controller
* Marker interface
* Module
* Proxy
* Twin

Behavioral|

* Blackboard
* Chain of responsibility
* Command
* Interpreter
* Iterator
* Mediator
* Memento
* Null object
* Observer
* Servant
* Specification
* State
* Strategy
* Template method
* Visitor

Functional|

* Closure
* Currying
* Function composition
* Functor
* Monad
* Generator

Concurrency|

* Active object
* Actor
* Balking
* Barrier
* Binding properties
* Coroutine
* Compute kernel
* Double-checked locking
* Event-based asynchronous
* Fiber
* Futex
* Futures and promises
* Guarded suspension
* Immutable object
* Join
* Lock
* Messaging
* Monitor
* Nuclear
* Proactor
* Reactor
* Read write lock
* Scheduler
* Thread pool
* Thread-local storage

Architectural|

* ADR
* Active record
* Broker
* Client–server
* CBD
* DAO
* DTO
* DDD
* ECB
* ECS
* EDA
* Front controller
* Identity map
* Interceptor
* Implicit invocation
* Inversion of control
* Model 2
* MOM
* Microservices
* MVA
* MVC
* MVP
* MVVM
* Monolithic
* Multitier
* Naked objects
* ORB
* P2P
* Publish–subscribe
* PAC
* REST
* SOA
* Service locator
* SN
* SBA
* Specification

Cloud
Distributed|

* Ambassador
* Anti-Corruption Layer
* Bulkhead
* Cache-Aside
* Circuit Breaker
* CQRS
* Compensating Transaction
* Competing Consumers
* Compute Resource Consolidation
* Event Sourcing
* External Configuration Store
* Federated Identity
* Gatekeeper
* Index Table
* Leader Election
* MapReduce
* Materialized View
* Pipes
* Filters
* Priority Queue
* Publisher-Subscriber
* Queue-Based Load Leveling
* Retry
* Scheduler Agent Supervisor
* Sharding
* Sidecar
* Strangler
* Throttling
* Valet Key

Other|

* Business delegate
* Composite entity
* Intercepting filter
* Lazy loading
* Mangler
* Mock object
* Type tunnel
* Method chaining

Books|

* Design Patterns
* Enterprise Integration Patterns

People|

* Christopher Alexander
* Erich Gamma
* Ralph Johnson
* John Vlissides
* Grady Booch
* Kent Beck
* Ward Cunningham
* Martin Fowler
* Robert Martin
* Jim Coplien
* Douglas Schmidt
* Linda Rising

Communities|

* The Hillside Group
* The Portland Pattern Repository

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Readers–writer lock. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Readers–writer_lock&oldid=4152416"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template