readers–writer 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. [http://www.boost.org/doc/html/thread/synchronization.html#thread.synchronization.mutex_concepts.upgrade_lockable] 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.

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.{{r|raynal}}{{rp|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.{{cite book |title=Advanced Programming in the UNIX Environment |first1=W. Richard |last1=Stevens |author-link=W. Richard Stevens |first2=Stephen A. |last2=Rago |publisher=Addison-Wesley |year=2013 |page=409}} 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.{{Citation needed|date=November 2015}} This variation is sometimes also known as "write-biased" readers–writer lock.{{Javadoc:SE|package=java.util.concurrent.locks|java/util/concurrent/locks|ReentrantReadWriteLock}} Java readers–writer lock implementation offers a "fair" mode
• 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.{{citation needed|date=April 2015}}

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

Raynal demonstrates how to implement an R/W lock using two mutexes and a single integer counter. The counter, {{mvar|b}}, tracks the number of blocking readers. One mutex, {{mvar|r}}, protects {{mvar|b}} and is only used by readers; the other, {{mvar|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:

This implementation is read-preferring.{{cite book |title=Concurrent Programming: Algorithms, Principles, and Foundations |first=Michel |last=Raynal |author-link=Michel Raynal |publisher=Springer |year=2012}}{{rp|76}}

Alternatively an RW lock can be implemented in terms of a condition variable, {{mvar|cond}}, an ordinary (mutex) lock, {{mvar|g}}, and various counters and flags describing the threads that are currently active or waiting.{{Cite book |title=The Art of Multiprocessor Programming |first1=Maurice |last1=Herlihy |first2=Nir |last2=Shavit |publisher=Elsevier |year=2012 |pages=184–185}}{{cite book |title=PThreads Programming: A POSIX Standard for Better Multiprocessing |url=https://archive.org/details/pthreadsprogramm00nich |url-access=registration |first1=Bradford |last1=Nichols |first2=Dick |last2=Buttlar |first3=Jacqueline |last3=Farrell |publisher=O'Reilly |year=1996 |pages=[https://archive.org/details/pthreadsprogramm00nich/page/84 84–89]|isbn=9781565921153 }}{{cite book |title=Programming with POSIX Threads |first=David R. |last=Butenhof |publisher=Addison-Wesley |year=1997 |pages=253–266}} For a write-preferring RW lock one can use two integer counters and one Boolean flag:

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

Initially {{mvar|num_readers_active}} and {{mvar|num_writers_waiting}} are zero and {{mvar|writer_active}} is false.

The lock and release operations can be implemented as

• POSIX standard pthread_rwlock_t and associated operations

{{cite web

| title = The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy

| url = http://www.opengroup.org/onlinepubs/009695399/functions/pthread_rwlock_init.html

| publisher = The IEEE and The Open Group

| access-date =14 May 2011

}}

• ReadWriteLock{{Javadoc:SE|package=java.util.concurrent.locks|java/util/concurrent/locks|ReadWriteLock}} interface and the ReentrantReadWriteLock locks in Java version 5 or above
• Microsoft System.Threading.ReaderWriterLockSlim lock for C# and other .NET languages

{{Cite web

| title = ReaderWriteLockSlim Class (System.Threading)

| url = http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx

| publisher = Microsoft Corporation

| access-date =14 May 2011

}}

• std::shared_mutex read/write lock in C++17

{{Cite web

| title = New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm

| url = http://isocpp.org/blog/2013/04/n3659-shared-locking

| publisher = Standard C++ Foundation

}}

• boost::shared_mutex and boost::upgrade_mutex locks in Boost C++ Libraries

{{Cite web

| title = Synchronization – Boost 1.52.0

| url = http://www.boost.org/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex

| author = Anthony Williams

| access-date =31 January 2012

}}

• SRWLock, added to the Windows operating system API as of Windows Vista.{{cite book |title=Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming |first=Victor |last=Alessandrini |publisher=Morgan Kaufmann |year=2015}}
• sync.RWMutex in Go

{{Cite web

| title = The Go Programming language – Package sync

| url = https://golang.org/pkg/sync/#RWMutex

| access-date =30 May 2015

}}

• Phase fair reader–writer lock, which alternates between readers and writers{{cite web | url = http://www.cs.unc.edu/~anderson/papers/ecrts09b.pdf | title=Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems}}
• std::sync::RwLock read/write lock in Rust

{{Cite web

| title = std::sync::RwLock – Rust

| url = https://doc.rust-lang.org/std/sync/struct.RwLock.html

| access-date =26 October 2019

}}

• Poco::RWLock in POCO C++ Libraries
• mse::recursive_shared_timed_mutex in the [//github.com/duneroadrunner/SaferCPlusPlus SaferCPlusPlus] library is a version of [http://en.cppreference.com/w/cpp/thread/shared_timed_mutex std::shared_timed_mutex] that supports the recursive ownership semantics of [http://en.cppreference.com/w/cpp/thread/recursive_mutex std::recursive_mutex].
• txrwlock.ReadersWriterDeferredLock Readers/Writer Lock for Twisted

{{Cite web

| title = Readers/Writer Lock for Twisted

| website=GitHub

| url=https://github.com/Stibbons/txrwlock

| access-date =28 September 2016

}}

• rw_semaphore in the Linux kernel

{{Cite web

| title = Synchronization primitives in the Linux kernel: Reader/Writer semaphores

| website=Linux Insides

| url=https://0xax.gitbooks.io/linux-insides/content/SyncPrim/linux-sync-5.html

| access-date = 8 June 2023

}}

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

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.

• Semaphore (programming)
• Mutual exclusion
• Scheduler pattern
• Balking pattern
• File locking
• Lock (computer science)
• Readers–writers problem

{{notelist}}

{{reflist}}

{{Design Patterns patterns}}

{{DEFAULTSORT:Readers-writer lock}}

Category:Concurrency control

Category:Software design patterns