リーダー・ライターロック

コンピュータサイエンスにおいて、リーダー・ライター（シングルライターロック、^{[ 1 ]}マルチリーダーロック、^{[ 2 ]}プッシュロック、^{[ 3 ]}またはMRSWロック）は、リーダー・ライター問題の1つを解決する同期プリミティブです。RWロックは読み取り専用操作の同時アクセスを許可しますが、書き込み操作には排他アクセスが必要です。つまり、複数のスレッドが並行してデータを読み取ることができますが、データの書き込みまたは変更には排他ロックが必要です。ライターがデータを書き込んでいるとき、ライターが書き込みを完了するまで、他のすべてのライターとリーダーはブロックされます。一般的な使用法としては、更新が完了するまでアトミックに更新できず無効な（別のスレッドによって読み取られるべきではない）メモリ内のデータ構造へのアクセスを制御することが挙げられます。

リーダー/ライター ロックは通常、ミューテックスと条件変数、またはセマフォの上に構築されます。

アップグレード可能なRWロック

一部のRWロックでは、ロックを読み取りモードから書き込みモードへアトミックにアップグレードしたり、書き込みモードから読み取りモードへダウングレードしたりすることができます。^{[ 4 ]}読み取りモードから書き込みモードへのロックのアップグレードはデッドロックになりやすいです。これは、読み取りロックを保持している2つのスレッドが両方とも書き込みロックにアップグレードしようとすると、いずれかのスレッドが読み取りロックを解放することによってのみ解除できるデッドロックが発生するためです。デッドロックは、書き込みモードのスレッドが存在せず、読み取りモードのスレッドがゼロ以外の場合、1つのスレッドだけが「書き込みにアップグレードする意図を持つ読み取りモード」でロックを取得できるようにすることで回避できます。

優先政策

RWロックは、読み取りアクセスと書き込みアクセスに対して異なる優先度ポリシーを持つように設計できます。ロックは、常に読み取りアクセスを優先する（読み取り優先）、常に書き込みアクセスを優先する（書き込み優先）、または優先度を指定しないのいずれかに設計できます。これらのポリシーは、同時実行性とスタベーションに関して異なるトレードオフをもたらします。

• 読み取り優先 RW ロックは最大限の同時実行性を実現しますが、競合が激しい場合は書き込み不足につながる可能性があります。これは、少なくとも 1 つの読み取りスレッドがロックを保持している限り、書き込みスレッドはロックを取得できないためです。複数の読み取りスレッドが同時にロックを保持する場合があるため、新しい読み取りスレッドがロックを取得できるまで、書き込みスレッドはロックを待機し続ける可能性があります。これは、最初にロックを取得しようとしたときにロックを保持していたすべての読み取りスレッドがロックを解放した後も、書き込みスレッドが待機し続ける可能性があることを意味します。読み取りスレッドへの優先度は、前述のように弱い場合と強い場合があります。強い場合、書き込みスレッドがロックを解放すると、ブロックしている読み取りスレッドが必ず次にそのロックを取得します。^{[ 5 ] : 76}
• 書き込み優先RWロックは、書き込みキューにロック待ちの書き込みスレッドがある場合、新しい読み取りスレッドがロックを取得できないようにすることで、書き込みスレッドの枯渇の問題を回避します。書き込みスレッドは、既にロックを保持しているすべての読み取りスレッドの処理が完了するとすぐにロックを取得します。 ^{[ 6 ]}欠点は、書き込み優先ロックは、読み取り優先RWロックと比較して、書き込みスレッドが存在する場合の同時実行性が低いことです。また、読み取りまたは書き込みのロックを取得または解放する操作が複雑になり、内部的に1つではなく2つのミューテックスを取得および解放する必要があるため、ロックのパフォーマンスが低下します。このバリエーションは、「書き込みバイアス」読み取り・書き込みロックと呼ばれることもあります。^{[ 7 ]}
• 優先度未指定のRWロックは、読み取りアクセスと書き込みアクセスに関していかなる保証も提供しません。状況によっては、より効率的な実装が可能になる場合、優先度未指定の方が好ましい場合があります。

実装

リーダー/ライター ロックの実装戦略はいくつか存在し、それらを事前に存在すると想定される同期プリミティブにまで縮小します。

2つのミューテックスを使用する

Raynalは、2つのミューテックスと1つの整数カウンタを用いてR/Wロックを実装する方法を実証しています。カウンタb は、ブロックしている読み取り側の数を追跡します。一方のミューテックスrはbを保護し、読み取り側のみが使用します。もう一方のミューテックスg (「グローバル」の略) は、書き込み側の相互排他性を確保します。このため、あるスレッドが取得したミューテックスを別のスレッドが解放できる必要があります。以下は、これらの操作の 擬似コードです。

初期化

bを0に設定します。r はロック解除されます。g はロック解除されます。 

読み始める

ロックr。b を増分します。b = 1 の場合、gをロックします。r の ロックを解除します。 

読み終える

ロックr。b を減分します。b = 0 の場合、gのロックを解除します。r の ロックを解除します。 

書き始める

gをロックします。 

書き込み終了

g のロックを解除します。 

この実装は読み取り優先です。^{[ 5 ]：76}

条件変数とミューテックスの使用

あるいは、RWロックは条件変数cond、通常の（ミューテックス）ロックg、現在アクティブまたは待機中のスレッドを表すさまざまなカウンタとフラグを使用して実装することもできます。^{[ 8 ] [ 9 ] [ 10 ]}書き込み優先RWロックの場合は、2つの整数カウンタと1つのブールフラグを使用できます。

num_readers_active : ロックを取得したリーダーの数（整数）

num_writers_waiting : アクセスを待機しているライターの数（整数）

writer_active : ライターがロックを取得したかどうか (ブール値)。

最初は、num_readers_activeとnum_writers_waitingはゼロで、writer_activeは false です。

ロックとリリースの操作は次のように実装できます。

読み始める

num_writers_waiting > 0またはwriter_active の間、gをロックします。 wait cond , g [ a ] num_readers_active をインクリメントし、g をロック解除します。 

読み終える

ロックg num_readers_active を減分num_readers_active = 0 の場合: 通知条件（ブロードキャスト）g の ロックを解除します。 

書き始める

num_readers_active > 0またはwriter_activeがtrue の間、num_writers_waiting を増分します。 wait cond , g num_writers_waiting をデクリメントしますwriter_activeをtrueに 設定しますg の ロックを解除します。 

書き込み終了

ロックg writer_activeをfalseに 設定条件 を通知(ブロードキャスト)g の ロックを解除します。 

プログラミング言語のサポート

• POSIX標準pthread_rwlock_tおよび関連操作^{[ 11 ]}
• Javaバージョン5以降ではReadWriteLock ^{[ 12 ]}インターフェースとReentrantReadWriteLock ^{[ 7 ]}ロックがサポートされる。
• C#およびその他の.NET言語用のMicrosoftSystem.Threading.ReaderWriterLockSlimロック^{[ 13 ]}
• std::shared_mutexC++17の読み取り/書き込みロック^{[ 14 ]}
• boost::shared_mutexBoost C++ライブラリboost::upgrade_mutexのロック^{[ 15 ]}
• SRWLockWindows Vista以降、 WindowsオペレーティングシステムAPIに追加された。^{[ 16 ]}
• sync.RWMutex囲碁において^{[ 17 ]}
• 位相公平型リーダー・ライターロック（リーダーとライターを交互に切り替える）^{[ 18 ]}
• std::sync::RwLockRustの読み取り/書き込みロック^{[ 19 ]}
• POCO C++ ライブラリの Poco::RWLock
• mse::recursive_shared_timed_mutexSaferCPlusPlusライブラリの はstd::shared_timed_mutex、 の再帰所有権セマンティクスをサポートするのバージョンですstd::recursive_mutex。
• txrwlock.ReadersWriterDeferredLockTwistedのリーダー/ライターロック^{[ 20 ]}
• rw_semaphoreLinuxカーネル内^{[ 21 ]}

Rustの例

std :: sync :: RwLockを使用します。lock = RwLock :: new ( 5 )とします。// 一度に複数の読み取りロックを保持できます{ let r1 = lock . read (). unwrap (); let r2 = lock . read (). unwrap (); assert_eq! ( * r1 , 5 ); assert_eq! ( * r2 , 5 ); } // この時点で読み取りロックは解除されます// ただし、書き込みロックは 1 つしか保持できません{ let mut w = lock . write (). unwrap (); * w += 1 ; assert_eq! ( * w , 6 ); } // ここで書き込みロックが解除されます

代替案

読み取り・コピー・更新（RCU）アルゴリズムは、リーダー・ライター問題に対する一つの解決策です。RCUはリーダーを待機させる必要がありません。Linuxカーネルは、少数のライター向けにseqlockと呼ばれる特別な解決策を実装しています。

参照

• セマフォ（プログラミング）
• 相互排除
• スケジューラパターン
• バルキングパターン
• ファイルロック
• ロック（コンピュータサイエンス）
• 読者と書き手の問題

注記

1. これは条件変数に対する標準的な「待機」操作であり、他のアクションの中でも、ミューテックスgを解放します。

参考文献

1. Hamilton, Doug (1995年4月21日). 「マルチリーダー/シングルライターロックに関する提案?」 .ニュースグループ:  comp.os.ms-windows.nt.misc . Usenet:  [e-mail] . 2010年10月8日閲覧。
2. 「実用的なロックフリーダム」 Keir Fraser著、2004年
3. 「プッシュロックとは何か？」Ntdebuggingブログ。MSDNブログ。2009年9月2日。 2017年5月11日閲覧。
4. 「同期 § UpgradeLockable コンセプト – 拡張機能」。Boost C++ ライブラリ。
5. Raynal, Michel (2012).並行プログラミング：アルゴリズム、原則、基礎. Springer.
6. Stevens, W. Richard ; Rago, Stephen A. (2013). 『UNIX環境における高度なプログラミング』 Addison-Wesley. p. 409.
7. java.util.concurrent.locks.ReentrantReadWriteLock Javaのリーダー・ライターロック実装は「公平な」モードを提供する
8. Herlihy, Maurice; Shavit, Nir ​​(2012). 『マルチプロセッサプログラミングの技法』エルゼビア. pp.  184– 185.
9. ニコルズ, ブラッドフォード; バトラー, ディック; ファレル, ジャクリーン (1996). PThreadsプログラミング：より優れたマルチプロセッシングのためのPOSIX標準. オライリー. pp.  84–89 . ISBN 9781565921153。
10. Butenhof, David R. (1997). 『POSIXスレッドを使ったプログラミング』Addison-Wesley. pp.  253– 266.
11. 「The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy」 . IEEEおよびThe Open Group . 2011年5月14日閲覧。
12. java.util.concurrent.locks.ReadWriteLock
13. "ReaderWriteLockSlim クラス (System.Threading)" . Microsoft Corporation . 2011年5月14日閲覧。
14. 「新規採択論文：N3659、C++における共有ロック—Howard Hinnant、Detlef Vollmann、Hans Boehm」。Standard C++ Foundation。
15. Anthony Williams. 「同期 – Boost 1.52.0」 . 2012年1月31日閲覧。
16. Alessandrini, Victor (2015).共有メモリアプリケーションプログラミング：マルチコアアプリケーションプログラミングの概念と戦略. Morgan Kaufmann.
17. 「Goプログラミング言語 - パッケージ同期」 。 2015年5月30日閲覧。
18. 「共有メモリマルチプロセッサリアルタイムシステムのリーダー・ライター同期」（PDF）。
19. "std::sync::RwLock – Rust" . 2019年10月26日閲覧。
20. 「Twisted のリーダー/ライターロック」GitHub。2016年9月28日閲覧。
21. 「Linuxカーネルの同期プリミティブ：リーダー/ライターセマフォ」Linux Insides . 2023年6月8日閲覧。