Readers-writer lock
Encyclopedia
In computer science
, a readers-writer or shared-exclusive lock (also known as the multiple readers / single-writer lock or the multi-reader lock,
or by typographical variants such as readers/writers lock) is a synchronization
primitive that solves one of the readers-writers problem
s. A readers-writer lock is like a mutex, in that it controls access to a shared resource, allowing concurrent access to multiple thread
s for reading but restricting access to a single thread for writes (or other changes) to the resource. A common use might be to control access to a data structure in memory that can't be updated atomically but isn't valid (and shouldn't be read by another thread) until the update is complete.
One potential problem with a conventional RW lock is that it can lead to write-starvation if contention is high enough, meaning that as long as at least one reading thread holds the lock, no writer thread will be able to acquire 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 finished their work in the shared area and released the lock. To avoid writer starvation, a variant on a readers-writer lock can be constructed which prevents any new readers from acquiring the lock if there is a writer queued and waiting for the lock, so that the writer will acquire the lock as soon as the readers which were already holding the lock are finished with it. The downside is that it's 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 known as a "write-preferring" or "write-biased" readers-writer lock.
Readers-writer locks are usually constructed on top of mutexes and condition variables, or on top of semaphore
s.
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
.
A read/write lock pattern or simply RWL is a software design pattern that allows concurrent
read access to an object
but requires exclusive access for write operations.
In this pattern, multiple readers can read the data in parallel but an exclusive lock
is needed while writing the data. When a writer is writing the data, readers will be blocked until the writer is finished writing.
Note that operations(either read or write) which you want to allow in parallel should grab the lock in read mode, and operations(either read or write) that you want to be exclusive should grab the lock in write mode.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a readers-writer or shared-exclusive lock (also known as the multiple readers / single-writer lock or the multi-reader lock,
or by typographical variants such as readers/writers lock) is a synchronization
Synchronization (computer science)
In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
primitive that solves one of the readers-writers problem
Readers-writers problem
In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that...
s. A readers-writer lock is like a mutex, in that it controls access to a shared resource, allowing concurrent access to multiple thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
s for reading but restricting access to a single thread for writes (or other changes) to the resource. A common use might be to control access to a data structure in memory that can't be updated atomically but isn't valid (and shouldn't be read by another thread) until the update is complete.
One potential problem with a conventional RW lock is that it can lead to write-starvation if contention is high enough, meaning that as long as at least one reading thread holds the lock, no writer thread will be able to acquire 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 finished their work in the shared area and released the lock. To avoid writer starvation, a variant on a readers-writer lock can be constructed which prevents any new readers from acquiring the lock if there is a writer queued and waiting for the lock, so that the writer will acquire the lock as soon as the readers which were already holding the lock are finished with it. The downside is that it's 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 known as a "write-preferring" or "write-biased" readers-writer lock.
Readers-writer locks are usually constructed on top of mutexes and condition variables, or on top of semaphore
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
s.
The read-copy-update
Read-copy-update
In computer operating systems, read-copy-update is a synchronization mechanism implementing a kind of mutual exclusionPlease note that RCU does not implement mutual exclusion in the conventional sense: RCU readers can and do run concurrently with RCU updates...
(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
Seqlock
A seqlock is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines. The semantics stabilized as of version 2.5.59, and they are present in the 2.6.x stable kernel series...
.
A read/write lock pattern or simply RWL is a software design pattern that allows concurrent
Concurrency control
In information technology and computer science, especially in the fields of computer programming , operating systems , multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.Computer...
read access to an object
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
but requires exclusive access for write operations.
In this pattern, multiple readers can read the data in parallel but an exclusive lock
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
is needed while writing the data. When a writer is writing the data, readers will be blocked until the writer is finished writing.
Note that operations(either read or write) which you want to allow in parallel should grab the lock in read mode, and operations(either read or write) that you want to be exclusive should grab the lock in write mode.
Implementations
- The POSIXPOSIXPOSIX , an acronym for "Portable Operating System Interface", is a family of standards specified by the IEEE for maintaining compatibility between operating systems...
standardpthread_rwlock_tand associated operations. - The C languageC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
Win32 multiple-reader/single-writer lock used in Hamilton C shellHamilton C shellHamilton C shell is a clone of the Unix C shell and utilities for Microsoft Windows created by Nicole Hamilton at Hamilton Laboratories. It was first released on OS/2 on December 12 1988 and on Windows NT in July 1992...
. The Hamilton lock presumes contention is low enough that writers are unlikely to be starved, prompting Jordan Zimmerman to suggest a modified version to avoid starvation. - The ReadWriteLock interface and the ReentrantReadWriteLock locks in JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
version 5 or above. - A simple Windows API implementation by Glenn Slayden.
- The Microsoft
System.Threading.ReaderWriterLockSlimlock for C# and other .NET.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
languages. - The
boost::shared_mutexin read/write lock the Boost C++ Libraries. - A pseudo-code implementation in the Readers-writers problemReaders-writers problemIn computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that...
article.
See also
- Semaphore (programming)Semaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
- Mutual exclusionMutual exclusionMutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
- Scheduler patternScheduler patternIn computer programming, the scheduler pattern is a software design pattern. It is a concurrency pattern used to explicitly control when threads may execute single-threaded code, like write operation to a file....
- Balking patternBalking patternThe balking pattern is a software design pattern that only executes an action on an object when the object is in a particular state. For example, if an object reads ZIP files and a calling method invokes a get method on the object when the ZIP file is not open, the object would "balk" at the request...
- File lockingFile lockingFile locking is a mechanism that restricts access to a computer file by allowing only one user or process access at any specific time. Systems implement locking to prevent the classic interceding update scenario ....
- Lock (computer science)Lock (computer science)In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...