Readers–writer lock

In computer science, a readers-writer or shared-exclusive lock (also known as the multiple readers / single-writer lock^[1] or the multi-reader lock,^[2] or by typographical variants such as readers/writers lock) is a synchronization primitive that solves one of the readers-writers problems. A readers-writer lock is like a mutex, in that it controls access to a shared resource, allowing concurrent access to multiple threads 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.^[3] 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.^[4][3] This variation is sometimes known as a "write-preferring" or "write-biased" readers-writer lock.^[5][6]

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

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.

Implementations

• The POSIX standard pthread_rwlock_t and associated operations.^[7]
• The C language Win32 multiple-reader/single-writer lock used in Hamilton C shell.^[1][4] The Hamilton lock presumes contention is low enough that writers are unlikely to be starved,^[8] prompting Jordan Zimmerman to suggest a modified version to avoid starvation.^[3]
• The ReadWriteLock^[9] interface and the ReentrantReadWriteLock^[10] locks in Java version 5 or above.
• A simple Windows API implementation by Glenn Slayden.^[11]
• The Microsoft System.Threading.ReaderWriterLockSlim lock for C# and other .NET languages.^[12]
• The boost::shared_mutex in read/write lock the Boost C++ Libraries.^[13]
• A pseudo-code implementation in the Readers-writers problem article.

See also

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

References

1. ^ ^{a b} Hamilton, Doug (Apr 21 1995). "Suggestions for multiple-reader/single-writer lock?". comp.os.ms-windows.nt.misc. (Web link). Retrieved Oct 8 2010. 
2. ^ "Practical lock-freedom" by Keir Fraser 2004
3. ^ ^{a b c} Jordan Zimmerman (Oct 21 1999). "Single-writer Multi-Reader lock for Win98". comp.programming.threads. (Web link). Retrieved May 17 2011. 
4. ^ ^{a b} Nicole Hamilton (Oct 19 1999). "Single-writer Multi-Reader lock for Win98". comp.programming.threads. (Web link). Retrieved May 17 2011. 
5. ^ "ReaderWriterLock Alternative" an open source C# implementation of a write-biased readers-writer lock
6. ^ java.util.concurrent.locks.ReentrantReadWriteLock Java readers-writer lock implementation offers a "fair" mode
7. ^ "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. Retrieved May 14 2011. 
8. ^ Ziv Caspi (Oct 20 1999). "Re: Single-writer Multi-Reader lock for Win98". comp.programming.threads. (Web link). "Forgive me for saying so, but this implementation favors readers instead of the writer. If there are many readers, the writer will never have a chance to write". Retrieved October 7, 2011. 
9. ^ java.util.concurrent.locks.ReadWriteLock
10. ^ java.util.concurrent.locks.ReentrantReadWriteLock
11. ^ Glenn Slayden. "Multiple-Reader, Single-Writer Synchronization Lock Class". http://www.glennslayden.com/code/win32/reader-writer-lock. Retrieved May 14 2011. 
12. ^ "ReaderWriteLockSlim Class (System.Threading)". Microsoft Corporation. http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx. Retrieved May 14 2011. 
13. ^ Anthony Williams. "Synchronization - Boost 1.46.1". http://www.boost.org/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex. Retrieved May 14 2011.