Hazard Pointers

概要

ロックフリーで実装できる、リソースを使い終わるまで破棄を遅延させる仕組み (deferred reclamation)
- 要らなくなったポインタを一旦回収し、使い終わったことを確認してから破棄する
- ポインタの寿命を管理する単一のWriterとポインタを使用する複数のReaderから成る
参照カウント方式と比べて、読み出し偏重のアルゴリズムで有利な特性を持つ
- カウントの増減を行わないので、構造をトラバースするさいのオーバーヘッドが少ない
- スレッドローカルにできるので、Reader同士が競合しない
参照カウント方式と比べて、メモリのフットプリントが大きくなる可能性がある
- 参照者数を管理しないので、使用者がいなくなった段階で即破棄とならず、後始末(reclamation)を明示的に行う必要がある

オブジェクト：
- src：管理されるポインタを格納するatomic<T*>型の共有領域
- RetiredList：使い終わったポインタのリスト
  - Writerからのみ読み書きされる
- ProtectedList：使用中のポインタのリスト
  - Readerから書き込まれ、Writerから読み出される
  - Readerからはスレッドローカルにできる
  - Writerからは全体にアクセスできる
Writer
- retire：使い終わったポインタをsrcから取り出し、RetiredListに入れる
- 後始末：RetiredListからポインタを取り出し、それがProtectedListに含まれるかを調べる
  - 含まれていたら、使用中のReaderがいるので、何もせずRetiredListに戻す
  - 含まれていなければ、使用しているReaderがおらず、srcから取り出されたために今後Readerが増えることもないため、そのポインタを解放する
Reader
- protect：srcからポインタを読み出し、ProtectedListに入れる
  - ProtectedListに入れている最中にsrcの中身が変更された場合、以前のポインタが解放されてしまった可能性があるため、操作をやり直す
  - srcの中身に変更がなければ、読み出したポインタがretireする前にProtectedListに入れられたことがわかるので、それを使う
  - ポインタを使い終わったら、ProtectedListから取り除く