リストから外すことと、解放すること
共有スタックの先頭ノードAを読み取ったスレッドが、一時停止したとします。別のスレッドがAを先頭から外しても、最初のスレッドはまだAの参照を持っています。リストから到達できなくなったことだけを理由にAを解放すると、再開した読者が既に無効な領域へ触れる危険があります。データ構造の論理的な削除と、保存領域を再利用できる時点は別です。この二つを分けることから回収方式を考えます。
lock-freeの更新で全体の進行を確保したつもりでも、回収の側が長く停止した読者を待つ場合や、大量の退役ノードを残す場合があります。更新操作の進行保証だけで、寿命とメモリ量まで片付いたとは言えません。ここでは危険な解放後参照を実際に起こすコードを提供せず、ノードID、保護中の印、退役集合を使う決定的な模型で状態を追います。実用の並行アロケータを実装したという説明にはしません。
ABAと解放後参照を分ける
Aのアドレスが一度先頭から消え、別のノードに同じアドレスが再利用されて先頭へ戻ると、CASで見た数値は以前と同じでも意味が変わる場合があります。これがABAの一つの状況です。一方、再利用される前でも、既に解放したAを読めば寿命違反です。同じアドレスを比べる話と、参照先へ安全にアクセスできる話を別の条件として扱います。
世代番号を付ける工夫は、比較で古い状態を見分ける助けになる場合がありますが、その番号だけで古い参照先の寿命まで延びるわけではありません。逆にGCのある環境で物理的な解放が遅れても、論理的な状態の変化が全て消えるとは限りません。既存のABAの記事を前提とし、このガイドでは「比較の同一性」「ノードの所属」「保存領域の寿命」を図の別の行へ置きます。何を解決した方式かを正確に述べるためです。
| 段階 | 意味 | まだ言えないこと |
|---|---|---|
| 保護 | 読者が参照を使う意図を公開 | 単独で取得が完了したとは限らない |
| 退役 | 構造から切り離す | 全読者が手放したとは限らない |
| 回収 | 方式の安全条件を確認して解放 | 切離し直後に常に可能とは限らない |
hazard pointerは保護してから再確認する
読者は先頭を読み、そのノードを参照中だと共有の保護記録へ公開し、先頭がまだ同じかを再確認します。再確認で変わっていれば、保護と読取りをやり直します。先頭を読んだ直後に止まり、削除と回収が先に進む窓を考える必要があるためです。単に「読んだので保護したつもり」と説明するだけでは、読取りと保護の間の競合を扱えていません。
削除側はノードを直ちに解放せず、退役集合へ入れます。保護記録を調べ、誰も参照中としていないノードを回収候補へ移します。どのメモリ順序で記録を公開し、走査と再確認の関係を作るかは実装の核心です。ここでは逐次に並べた状態模型へ限定し、Pythonの辞書を共有しただけで正しいhazard pointer実装ができたとはしません。対象言語の規則に従う実装を利用する場合も、APIが要求する保護と解除の範囲を守ります。
小さな模型で退役と回収を区別する
掲載コードでは読者Aがノード1を保護し、先頭がまだ1だと確認します。次に削除側が先頭を2へ進め、1を退役集合へ入れます。最初のscanでは1が保護記録にあるので回収されません。読者Aが保護を解除した後のscanで初めて回収集合へ移ります。assertはこの二段階を検査し、先頭から外した瞬間に解放したかのような履歴を作りません。
この模型はメタデータの集合演算であり、実際の並行読者やメモリの解放を起こしていません。退役集合と保護集合がどのように関係するかを学ぶ目的です。実行記録と本文へこの区別を付けます。条件変更の課題では保護中の読者を一つ増やし、一人だけが解除したときには残る保護のため回収できないことを確認できます。参照数のような値と、どの読者が何を保護したかという集合を混同しないようにします。
head=1;hazards={};retired=set();freed=set()
# Reader publishes protection, then validates that head still matches.
read=head;hazards['A']=read;assert read==head
head=2;retired.add(1)
def scan():
reclaim=retired-set(hazards.values());freed.update(reclaim);retired.difference_update(reclaim)
scan();assert retired=={1} and freed==set()
del hazards['A'];scan();assert retired==set() and freed=={1}
print('protected node retained; released node reclaimed')
print('deterministic metadata model; not a concurrent allocator implementation')
epochでは読者の期間を追う
epoch方式では、読者がどの期間に入っているかを記録し、古い期間の読者が通過したと判断できるまで退役した領域を残す考え方を使います。各ノードを直接保護するhazard pointerと、読む区間をまとめて追う方式では、記録の費用と停止した読者の影響が違います。名前だけで一方が必ず優れているとは順位付けしません。読取りの長さ、更新量、停止やスレッド終了の扱いが選択へ関係します。
一人が読取り区間へ入ったまま長時間止まる場合、他の操作が進んでも回収できる時点が遅れ、退役領域が増えることがあります。これを物理メモリの無限の余裕へ押し込まず、保持量の監視や区間の長さの契約を考えます。hazard pointerでも保護を解除し忘れれば特定のノードが残ります。どちらも、読者の参加、終了、例外時の解除を含む寿命管理が必要です。更新の正しさだけで運用上の容量が足りると判断しないでください。
進行保証と回収の費用を別に評価する
スタックのpushやpopがlock-freeと説明されても、実際に使うメモリ確保や回収の経路へロックが含まれる場合があります。操作のどこまでを対象にした進行保証かを確認します。回収走査を一回の操作へ大量に載せれば、全体が進む性質があっても一要求の待ち時間は長くなり得ます。スループット、尾の遅延、保持する退役領域は別の評価項目です。
実用へ進む際は、対象ライブラリが要求するメモリ順序、スレッドの登録、入れ子の保護、例外時の解除、スレッド終了時の回収を確認します。独自の短い例を、その契約を持つ完成したライブラリの代わりにしません。ベンチマークでは、実行を速く見せるために回収を全く行わず、終わった後に残った領域を無視することも避けます。測定した区間で何を確保し、いつ何を回収したかを保存し、目的へ合う条件で比較します。
保護記録を解除する責任を決める
読者が例外で処理を抜けても、保護記録が残り続けないようにします。保護を所有する範囲を明確にし、スコープ終了の解放やライブラリのガードを使う設計を検討します。ただし解除を早めすぎると、まだ参照先を使う読者を保護できません。保護の開始と終了は、単なる関数の行数でなく最後に参照する時点へ対応させます。
スレッドを登録する方式なら、終了したスレッドの記録を誰が片付けるかも必要です。停止と終了は違い、動かないから保護を勝手に消してよいとは判断できません。再開する読者があり得るからです。今回の模型はAが明示的に解除する一経路を検査しています。例外、強制終了、登録の失敗などを追加する場合は、その新しい寿命の履歴を別に用意し、回収と進行の条件が維持されることを確認します。
回収の遅れを容量として見積もる
更新が毎秒多くのノードを退役させるのに、長い読取りで回収が遅れるなら、正しい実装でも保持量が増えます。退役の速度と、最も長く保護が残る時間を観測し、どの程度の余裕が必要かを見積もります。単純な積は初期の目安で、複数読者の重なりや走査の周期、バッチでの解放も関係します。測定した条件の外へ厳密な容量保証を広げません。
GCのある実装でも、古い版や参照を長く保持すれば領域が残る点では似た問題があります。ただし回収の機構と保証は別なので、同じモデルで全て説明したとはしません。安全に保持している領域と、参照の解除漏れで永久に残る領域も区別します。更新回数の速さだけを測るより、退役中の個数、最大保持期間、回収に使った時間を別々に残すと、目的へ合う方式を比較しやすくなります。
保護が残る履歴を答える課題
課題はAとBが両方ノード1を保護し、削除側が1を退役させた後、Aだけが解除した場合に回収できるかです。解答はできません。Bの保護記録に1が残るためです。次にBが解除し、走査で他の保護がないと確認できた段階で回収候補になります。先頭が既に2だから1は不要、という説明では、先頭外から持っている参照を見落とします。
追加課題はノード1を指すアドレスへ世代番号を付けたら、直ちに解放してよいかという問いです。解答は、比較で状態を見分ける工夫と、読者が参照する領域の寿命は別なので、それだけでは言えません。最後に、今回の模型が確認したことを限定します。保護中の退役ノードが残り、解除後に回収される状態遷移は検査しましたが、実メモリ上の並行実装やその進行保証は検証していません。この範囲を正確に述べられることが到達点です。