读写锁

读写锁是计算机程序的并发控制的一种同步机制，也称“共享-互斥锁”、多读者-单写者锁。[1]多读者锁，[2]，“push lock”[3]) 用于解决读写问题。读操作可并发重入，写操作是互斥的。

读写锁通常用互斥锁、条件变量、信号量实现。

某些读写锁允许在读模式与写模式之间升降级。

优先级策略

读写锁可以有不同的操作模式优先级：

  • 读操作优先：允许最大并发，但写操作可能饿死。
  • 写操作优先：一旦所有已经开始的读操作完成，等待的写操作立即获得锁。[4]内部实现需要两把互斥锁。[5]
  • 未指定优先级

实现

使用两把互斥锁

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（表示正在读的个数）与布尔标志g（表示正在写）来实现读写锁。

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. . Newsgroup: comp.os.ms-windows.nt.misc. 21 April 1995 [8 October 2010]. Usenet: hamilton.798430053@BIX.com. （原始内容存档于2012-11-09）.
  2. "Practical lock-freedom" 页面存档备份，存于 by Keir Fraser 2004
  3. . Ntdebugging Blog. MSDN Blogs. 2009-09-02 [11 May 2017]. （原始内容存档于2017-10-07）.
  4. Stevens, W. Richard; Rago, Stephen A. . Addison-Wesley. 2013: 409.
  5. java.util.concurrent.locks.ReentrantReadWriteLock Java readers–writer lock implementation offers a "fair" mode
  6. Raynal, Michel. . Springer. 2012.
  7. Herlihy, Maurice; Shavit, Nir. . Elsevier. 2012: 184–185.
  8. Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline. . O'Reilly. 1996: 84–89.
  9. Butenhof, David R. . Addison-Wesley. 1997: 253–266.
  10. . The IEEE and The Open Group. [14 May 2011]. （原始内容存档于2010-12-09）.
  11. java.util.concurrent.locks.ReadWriteLock
  12. . Microsoft Corporation. [14 May 2011]. （原始内容存档于2017-07-16）.
  13. . Standard C++ Foundation. [2017-11-22]. （原始内容存档于2016-08-26）.
  14. Anthony Williams. . [31 Jan 2012].
  15. . [30 May 2015]. （原始内容存档于2018-01-03）.
  16. (PDF). [2017-11-22]. （原始内容 (PDF)存档于2017-08-10）.
  17. . [10 December 2015]. （原始内容存档于2019-07-17）.
  18. . [28 September 2016].
  19. Alessandrini, Victor. . Morgan Kaufmann. 2015.
  20. . [2017-11-23]. （原始内容存档于2015-04-16）.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.