跳至內容

讀寫鎖

維基百科,自由的百科全書

讀寫鎖是電腦程式的並發控制的一種同步機制,也稱「共享-互斥鎖」、多讀者-單寫者鎖。[1]多讀者鎖[2],「push lock」[3]) 用於解決讀寫問題英語readers–writers problem。讀操作可並發重入,寫操作是互斥的。這意味着多個線程可以同時讀數據,但寫數據時需要獲得一個獨佔的鎖。當寫者寫數據時,其它寫者或讀者需要等待,直到這個寫者完成寫操作。讀寫鎖常見的用法是控制線程對內存中的某種數據結構的訪問,這種數據結構不能被原子性地更新,並且在完成更新之前都是無效的。

讀寫鎖通常用互斥鎖條件變量信號量實現。

某些讀寫鎖允許在讀模式與寫模式之間升降級。[1]

優先級策略

讀寫鎖可以有不同的操作模式優先級:

  • 讀操作優先鎖:提供了最大並發性,但在鎖競爭比較激烈的情況下,可能會導致寫操作飢餓。這是由於只要還有一個讀線程持鎖,寫線程就拿不到鎖。多個讀者可以立刻拿到鎖,這意味着一個寫者可能一直在等鎖,期間新的讀者一直可以拿到鎖。極端情況下,寫者線程可能會一直等鎖,直到所有一開始就拿到鎖的讀者釋放鎖。讀者的可以是弱優先級的,如前文所述,也可以是強優先級的,即只要寫者釋放鎖,任何等待的讀者總能先拿到。
  • 寫操作優先鎖:如果隊列中有寫者在等鎖,則阻止任何讀者拿鎖,來避免了寫操作飢餓的問題。一旦所有已經開始的讀操作完成,等待的寫操作立即獲得鎖。[4]和讀操作優先鎖相比,寫操作優先鎖的不足在於在寫者存在的情況下並發度低。內部實現需要兩把互斥鎖。[5]
  • 未指定優先級鎖:不提供任何讀/寫的優先級保證。

實現

使用兩把互斥鎖

Michel Raynal英語Michel Raynal使用兩把互斥鎖與一個整數計數器實現。計數器b跟蹤被阻塞的讀線程。互斥鎖r保護b,供讀者使用。互斥鎖g (指"global")確保寫操作互斥。偽代碼:

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.

實現是讀操作優先。[6]:76

使用條件變量與互斥鎖

可使用條件變量c與普通的互斥鎖m、整型計數器r(表示正在讀的個數)與布爾標誌w(表示正在寫)來實現讀寫鎖。

lock-for-read操作:[7][8][9]

  • Lock m (blocking).
  • While w:
  • Increment r.
  • Unlock m.

lock-for-write操作:[7][8][9]

  • Lock m (blocking).
  • While (w or r > 0):
    • wait c, m
  • Set w to true.
  • Unlock m.

lock-for-read與lock-for-write各自有自己的逆操作。unlock-for-read通過減量r並在r變為0時通知c。unlock-for-write設置w為false並通知c[7][8][9]

程序語言支持

Windows作業系統

SRWLock,見Windows作業系統API,從Windows Vista開始.[19]

讀寫鎖(Slim reader/writer,SRW, lock)用於進程內的線程間同步。 SRW既不是公平的也不是先進先出的。讀寫鎖數據結構的內部實現就是一個指針。讀寫鎖的性能較臨界區有很大的提升,這是因為讀寫鎖是基於原子操作,關鍵段是基於event內核對象的,從用戶模式到內核模式的切換佔用了大量的時鐘周期。相關API:[20]

  • InitializeSRWLock:動態初始化SRW結構。也可以直接賦值SRWLOCK_INIT常量來靜態初始化SRW結構。不需要顯式析構。
  • AcquireSRWLockShared:獲取共享讀的SRW鎖。
  • AcquireSRWLockExclusive:獲取專享寫的SRW鎖。
  • TryAcquireSRWLockShared:試圖獲取共享讀的SRW鎖。
  • TryAcquireSRWLockExclusive:試圖獲取專享寫的SRW鎖。
  • ReleaseSRWLockShared:釋放已經獲取的共享讀的SRW鎖。
  • ReleaseSRWLockExclusive:釋放已經獲取的專享寫的SRW鎖。
  • SleepConditionVariableSRW:在已經獲取SRW鎖的前提下,原子操作:在指定條件變量上睡眠並釋放SRW鎖

可選

read-copy-update (RCU)算法是讀寫鎖的一種替代實現。RCU對讀操作是無等待。Linux內核實現了很少寫操作的一種RCU叫做seqlock

參見

註釋

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

參考文獻

  1. ^ Hamilton, Doug. Suggestions for multiple-reader/single-writer lock?. Newsgroupcomp.os.ms-windows.nt.misc. 21 April 1995 [8 October 2010]. Usenet: [email protected]. (原始內容存檔於2012-11-09). 
  2. ^ "Practical lock-freedom"頁面存檔備份,存於互聯網檔案館) by Keir Fraser 2004
  3. ^ Push Locks – What are they?. Ntdebugging Blog. MSDN Blogs. 2009-09-02 [11 May 2017]. (原始內容存檔於2017-10-07). 
  4. ^ Stevens, W. Richard; Rago, Stephen A. Advanced Programming in the UNIX Environment. Addison-Wesley. 2013: 409. 
  5. ^ 5.0 5.1 java.util.concurrent.locks.ReentrantReadWriteLock Java readers–writer lock implementation offers a "fair" mode
  6. ^ Raynal, Michel. Concurrent Programming: Algorithms, Principles, and Foundations. Springer. 2012. 
  7. ^ 7.0 7.1 7.2 Herlihy, Maurice; Shavit, Nir. The Art of Multiprocessor Programming. Elsevier. 2012: 184–185. 
  8. ^ 8.0 8.1 8.2 Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline. PThreads Programming: A POSIX Standard for Better Multiprocessing. O'Reilly. 1996: 84–89. 
  9. ^ 9.0 9.1 9.2 Butenhof, David R. Programming with POSIX Threads. Addison-Wesley. 1997: 253–266. 
  10. ^ The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy. The IEEE and The Open Group. [14 May 2011]. (原始內容存檔於2010-12-09). 
  11. ^ java.util.concurrent.locks.ReadWriteLock
  12. ^ ReaderWriteLockSlim Class (System.Threading). Microsoft Corporation. [14 May 2011]. (原始內容存檔於2017-07-16). 
  13. ^ New adopted paper: N3659, Shared Locking in C++—Howard Hinnant, Detlef Vollmann, Hans Boehm. Standard C++ Foundation. [2017-11-22]. (原始內容存檔於2016-08-26). 
  14. ^ Anthony Williams. Synchronization – Boost 1.52.0. [31 Jan 2012]. 
  15. ^ The Go Programming language - Package sync. [30 May 2015]. (原始內容存檔於2018-01-03). 
  16. ^ Reader–Writer Synchronization for Shared-Memory Multiprocessor Real-Time Systems (PDF). [2017-11-22]. (原始內容 (PDF)存檔於2017-08-10). 
  17. ^ std::sync::RwLock - Rust. [10 December 2015]. (原始內容存檔於2019-07-17). 
  18. ^ Readers/Writer Lock for Twisted. [28 September 2016]. 
  19. ^ Alessandrini, Victor. Shared Memory Application Programming: Concepts and Strategies in Multicore Application Programming. Morgan Kaufmann. 2015. 
  20. ^ MSDN: Slim Reader/Writer (SRW) Locks. [2017-11-23]. (原始內容存檔於2015-04-16).