词条 | Readers–writer lock |
释义 |
In computer science, a readers–writer (RW) or shared-exclusive lock (also known as a multiple readers/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, 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 lockSome 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 policiesRW 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.
ImplementationSeveral implementation strategies for readers–writer locks exist, reducing them to synchronization primitives that are assumed to pre-exist. Using two mutexesRaynal 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: Begin Read{{framebox|blue}}
End Read{{framebox|blue}}
Begin Write{{framebox|blue}}
End Write{{framebox|blue}}
This implementation is read-preferring.[6]{{rp|76}} Using a condition variable and a mutexAlternatively, a write-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:[7][8][9] {{framebox|blue}}
The lock-for-write operation is similar, but slightly different (inputs are the same as for lock-for-read):{{r|herlihy}}{{r|pthreads}}{{r|butenhof}} {{framebox|blue}}
Each of lock-for-read and lock-for-write has its own inverse operation. Releasing a read lock is done by decrementing {{mvar|r}} and signalling {{mvar|c}} if {{mvar|r}} has become zero (both while holding {{mvar|m}}), so that one of the threads waiting on {{mvar|c}} can wake up and lock the R/W lock. Releasing the write lock means setting {{mvar|w}} to false and broadcasting on {{mvar|c}} (again while holding {{mvar|m}}).{{r|herlihy}}{{r|pthreads}}{{r|butenhof}} Programming language support
AlternativesThe 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
Notes{{notelist}}References1. ^{{cite newsgroup |author=Hamilton, Doug |title=Suggestions for multiple-reader/single-writer lock? |date=21 April 1995 |newsgroup=comp.os.ms-windows.nt.misc |message-id=hamilton.798430053@BIX.com |url=http://groups.google.com/group/comp.os.ms-windows.programmer.win32/msg/77533bcc6197c627?hl=en |access-date=8 October 2010}} {{Design Patterns patterns}}{{use dmy dates|date=May 2012}}{{DEFAULTSORT:Readers-writer lock}}2. ^"Practical lock-freedom" by Keir Fraser 2004 3. ^{{cite web|title=Push Locks – What are they?|url=https://blogs.msdn.microsoft.com/ntdebugging/2009/09/02/push-locks-what-are-they/|date=2009-09-02|website=Ntdebugging Blog|publisher=MSDN Blogs|accessdate=11 May 2017}} 4. ^{{cite book |title=Advanced Programming in the UNIX Environment |first1=W. Richard |last1=Stevens |authorlink=W. Richard Stevens |first2=Stephen A. |last2=Rago |publisher=Addison-Wesley |year=2013 |page=409}} 5. ^1 {{Javadoc:SE|package=java.util.concurrent.locks|java/util/concurrent/locks|ReentrantReadWriteLock}} Java readers–writer lock implementation offers a "fair" mode 6. ^{{cite book |title=Concurrent Programming: Algorithms, Principles, and Foundations |first=Michel |last=Raynal |authorlink=Michel Raynal |publisher=Springer |year=2012}} 7. ^{{Cite book |title=The Art of Multiprocessor Programming |first1=Maurice |last1=Herlihy |first2=Nir |last2=Shavit |publisher=Elsevier |year=2012 |pages=184–185}} 8. ^{{cite book |title=PThreads Programming: A POSIX Standard for Better Multiprocessing |first1=Bradford |last1=Nichols |first2=Dick |last2=Buttlar |first3=Jacqueline |last3=Farrell |publisher=O'Reilly |year=1996 |pages=84–89}} 9. ^{{cite book |title=Programming with POSIX Threads |first=David R. |last=Butenhof |publisher=Addison-Wesley |year=1997 |pages=253–266}} 10. ^{{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| accessdate =14 May 2011}} 11. ^{{Javadoc:SE|package=java.util.concurrent.locks|java/util/concurrent/locks|ReadWriteLock}} 12. ^{{Cite web| title = ReaderWriteLockSlim Class (System.Threading)| url = http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx| publisher = Microsoft Corporation| accessdate =14 May 2011}} 13. ^{{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}} 14. ^{{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| accessdate =31 Jan 2012}} 15. ^{{cite book |title=Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming |first=Victor |last=Alessandrini |publisher=Morgan Kaufmann |year=2015}} 16. ^{{Cite web| title = The Go Programming language - Package sync| url = https://golang.org/pkg/sync/#RWMutex| accessdate =30 May 2015}} 17. ^{{cite web | url = http://www.cs.unc.edu/~anderson/papers/ecrts09b.pdf | title=Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems}} 18. ^{{Cite web| title = std::sync::RwLock - Rust| url = http://doc.rust-lang.org/1.5.0/std/sync/struct.RwLock.html| accessdate =10 December 2015}} 19. ^{{Cite web| title = Readers/Writer Lock for Twisted| url=https://github.com/Stibbons/txrwlock| accessdate =28 September 2016}} 1 : Concurrency control |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。