プロンプトとユースケース
スレッドセーフな読み書きロックを実装してください。複数のリーダーが同時に保持できますが、ライターは排他的に保持する必要があります。待機ポリシー、ウェイクアップ規則、リエントランシー、およびライターの無期限の飢餓を防ぐ方法を説明してください。ミューテックスと条件変数を使用できますが、組み込みの読み書きロックは使用できません。
この質問は、バックエンド、インフラストラクチャ、および並行処理の役割に適しています。特定のプログラミング言語ではなく、同期の不変条件とトレードオフをテストします。
面接官が評価するポイント
- 最初に不変条件を定義しているか：アクティブなライターは最大1つであり、ライターがロックを保持している間はアクティブなリーダーが存在しないこと。
- 「公平性（Fairness）」を実行可能な入場ルールに落とし込んでいるか。
- 偽ウェイクアップ（spurious wakeups）、例外パス、再帰的取得、およびアップグレードによるデッドロックを処理しているか。
- 計算量、テスト、および本番環境の標準ライブラリを再利用するための境界を提供しているか。
回答前の確認事項
取得が中断可能かタイムアウト付きか、スレッドが再入可能か、読み取りから書き込みへのアップグレードが必要か、公平性が厳密なFIFOを意味するのか最終的なライターの進行を意味するのかを確認します。指定がない場合は、再入不可、アップグレード不可、ライター優先の最小限の設計を提案し、その境界を明示的に述べてください。
30秒での回答
状態の名前を定義します：activeReaders、activeWriter、およびwaitingWriters。リーダーは、ライターも待機中のライターも存在しない場合にのみ入場します。ライターは、両方のアクティブカウントが0の場合にのみ入場します。すべての状態変更を1つのミューテックスで保護し、解放時に1つのライターまたはリーダーグループをウェイクアップします。条件変数のウェイクアップ後は、必ずwhileループ内で述語を再チェックします。APIが明示的なプロトコルを定義していない限り、読み取りから書き込みへのアップグレードは禁止します。
ステップバイステップの解決策
状態と不変条件
activeWriterはブール値、activeReadersは非負のカウント、waitingWritersはキューイングされたライターの数をカウントします。重要な不変条件は、activeWriter == trueがactiveReaders == 0を意味することです。ライターは両方が空の場合にのみ入場できます。待機カウントはポリシーを制御するものであり、ロックが保持されていることを意味するものではありません。
取得と解放
リーダーは!activeWriter && waitingWriters == 0を待ち、ライターは!activeWriter && activeReaders == 0を待ちます。偽ウェイクアップを処理するために、条件変数が戻るたびに再チェックします。ライターの解放時、キューにライターが存在する場合は1つのライターにシグナルを送信し、そうでない場合はリーダーにブロードキャストします。最後のリーダーが退出するときに、ライターにシグナルを送信します。
~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()
writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()
writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~
公平性とスループット
| ポリシー | リーダーの入場条件 | メリット | リスク |
|---|---|---|---|
| ライター優先 | アクティブなライターがなく、waitingWriters == 0 | ライターの飢餓を抑制 | ライターのバースト中にリーダーのレイテンシが上昇 |
| リーダー優先 | アクティブなライターがない | 高い読み取りスループット | ライターが飢餓に陥る可能性がある |
| 近似FIFO | キュー順に入場 | より予測可能なレイテンシ | 状態とキューイングの複雑さが増加 |
Oracleのドキュメントには、非公平モードではリーダーまたはライターが無期限に延期される可能性がある一方、公平モードはおおよそ到着順のポリシーを使用し、通常はスループットを犠牲にすることが記載されています。面接では「飢餓がないこと」と厳密なFIFOを区別してください。
模範回答
再入不可でライター優先の実装から始めます。1つのミューテックスがすべてのカウンターを保護します。リーダーは、アクティブまたは待機中のライターがいない場合にのみインクリメントします。ライターは、両方のアクティブカウントが0になるまで待機します。条件変数から戻るたびに、whileループでその述語を再チェックします。解放時には、キューにライターがある場合はライターにシグナルを送信し、それ以外の場合はリーダーにブロードキャストします。これにより排他不変条件が維持され、新しいリーダーの絶え間ないストリームがライターに割り込むのを防ぎます。
読み取りから書き込みへのアップグレードは明示的に拒否します。書き込みロックを待機しているリーダーが他のリーダーの解放を妨げ、デッドロックを引き起こす可能性があるためです。呼び出し側は読み取りロックを解放して再度競合するか、別個のキューイングされたアップグレードプロトコルを使用する必要があります。中断、タイムアウト、リエントランシー、診断、または厳密な公平性については、不完全なロックをビジネスコードにコピーするのではなく、ドキュメント化されたプラットフォームプリミティブを使用し、そのセマンティクスをテストします。
よくある間違い
whileをifに置き換えてしまい、偽ウェイクアップによって述語がバイパスされることを許してしまう。- キューイングされたライターを無視して、リーダーを永久に入場させてしまう。
- ライター解放後に1つのリーダーしかウェイクアップしない、または無条件にブロードキャストして群発覚醒（thundering herd）を引き起こす。
- アップグレードキューなしでアップグレードを許可し、2つのリーダーが互いに待機し合う状態になる。
tryLockを公平性の保証として扱うこと。Oracleは、ノンブロッキングのtryLockが割り込み（barge）可能であることを明記しています。
フォローアップの質問と回答
不変条件をどのようにテストしますか？
アトミックなテストスナップショットを保持します。ライター入場時にリーダーがゼロであること、リーダー入場時にライターが存在しないことをアサートします。ランダム化されたリーダーおよびライタースレッドを実行し、アサーションが失敗した場合は常時イベントシーケンスを記録します。
ライターの飢餓をどのようにテストしますか？
1つのライターが待機している間に、リーダーを継続的に生成します。ライターのキュー登録から入場までの時間と最大待機カウントを記録します。目標は、任意の固定ミリ秒の保証ではなく、最終的な進行です。
通常のミューテックスを1つ使わないのはなぜですか？
通常のミューテックスの方が単純であり、多くの場合レイテンシが安定しています。読み書きロックは、読み取りが支配的であり、読み取りのクリティカルセクションが重複するほど十分に長い場合にのみ役立ちます。直感ではなくベンチマークで選択してください。
再入可能にすることはできますか？
ライタースレッドと保持カウント、さらにスレッドごとの読み取りカウントを追跡します。これにより、アップグレードと解放のルールが大幅に拡張されます。リエントランシーが必要ない場合は、それを禁止することで状態空間を小さく保つことができます。
POSIXはこの議論に何をもたらしますか？
POSIXは、定義されたエラー戻り値を持つ個別の読み取りロックおよび書き込みロック操作を公開します。実装は、優先順位と再帰的動作に関するプラットフォームのルールを引き続き尊重する必要があります。カスタムポリシーをPOSIXの保証として提示すべきではありません。
独自実装（手書き）をやめるべきタイミングは？
中断、タイムアウト、診断、リエントランシー、または移植性が重要な場合は、JavaのReentrantReadWriteLockやPOSIXのpthread_rwlock_*など、検証済みのプリミティブを優先し、レビューで公平性の選択を記録してください。