跳转到内容

读写锁

维基百科,自由的百科全书

读写锁是计算机程序的并发控制的一种同步机制,也称“共享-互斥锁”、多读者-单写者锁。[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).