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

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

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

一部の RW ロックでは、ロックを読み取りモードから書き込みモードにアトミックにアップグレードしたり、書き込みモードから読み取りモードにダウングレードしたりできます。[1] 読み取りモードから書き込みモードへのロックのアップグレードはデッドロックになりがちです。これは、リーダー ロックを保持している 2 つのスレッドが両方ともライター ロックにアップグレードしようとすると、スレッドの 1 つがリーダー ロックを解放することによってのみ解除できるデッドロックが発生するためです。デッドロックは、書き込みモードのスレッドがなく、読み取りモードのスレッドがゼロ以外の可能性がある場合に、1 つのスレッドだけが「書き込みにアップグレードする目的で読み取りモード」でロックを取得できるようにすることで回避できます。

RW ロックは、読み取りアクセスと書き込みアクセスに対して異なる優先ポリシーを使用して設計できます。ロックは、常に読み取りを優先するように (読み取り優先)、常に書き込みを優先するように (書き込み優先)、または優先順位を指定せずに設計できます。これらのポリシーによって、同時実行性と枯渇に関して異なるトレードオフが生じます。

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

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

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

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

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

• num_readers_active : ロックを取得したリーダーの数 (整数)
• num_writers_waiting : アクセスを待機しているライターの数 (整数)
• writer_active : ライターがロックを取得したかどうか (ブール値)。

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

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

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

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

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