Hazard Pointer

Hazard Pointer

Lockfreeデータ構造の問題点 ◼ ◼ CompareAndSet命令が直列化を行ってくれる ため、mutexのない排他操作ができていた そのCompareAndSetにはABA問題が付きまと う ❑ ❑ Aだった物がBとなり、紆余曲折を経てAへ戻った場 面へCASが直面してしまう CASは物理的には正しいんだけど理論的に間違っ た操作をしてしまう ◼ ・・・分かりにくいですね

LockfreeQueueを例に Deque操作を行うとします 操作のステップをおさらい ◼ ◼ 先頭ノードが保持するデータを複製 HeadをCASによって次のポインタへ次ぎ替え ❑ ❑ – – – – 成功したら複製したデータを返す 失敗したらHeadが更新されてるので再読み込みしてやり なおし この3ステップでDequeされることに注意 3ステップ目はCASの結果に依存している

LockfreeQueueを例に スレッドα,βが出演 ノードに付いている色はメモリ上での位置を表す Tail A リソースプール B C 先頭ノード Head Dummy

LockfreeQueueを例に スレッドα,βが出演します αのローカルバッファ Head: Tail A リソースプール B C Head Dummy α：先頭ノードをデキュー開始

LockfreeQueueを例に スレッドα,βが出演します αのローカルバッファ Head: Tail A リソースプール B C Head Dummy α：Cを複製 deque:C

LockfreeQueueを例に スレッドα,βが出演します αのローカルバッファ Head: Tail A B C deque:C Head Dummy β：デキュー x 3実行 リソースプール α：Headが黄色であること を前提にCASしようとする

LockfreeQueueを例に スレッドα,βが出演します αのローカルバッファ Head: Tail A B deque:C Head 旧C β：登場&デキュー x 3開始 リソースプール α：何らかの理由で休止

LockfreeQueueを例に スレッドα,βが出演します αのローカルバッファ Head: Tail A B Head 旧C β：デキュー x 3実行 リソースプール deque:C α：休眠中・・・ C出力

LockfreeQueueを例に スレッドα,βが出演します Tail A Head 旧B β：デキュー x 3実行 リソースプール α：休眠中・・・ B出力

LockfreeQueueを例に スレッドα,βが出演します Tail Head 旧A β：デキュー x 3実行→成功 リソースプール α：休眠中・・・ A出力

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: ここで削除済みデータ領域 を使い回してしまう Tail X Head 旧A β：更にエンキュー x 1 実行→成功 リソースプール α：休眠中・・・ deque:C

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail Head 旧X β：デキュー x 1 実行→成功 リソースプール deque:C α：休眠中・・・ X出力

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail deque:C Head 旧X β：仕事終了 リソースプール α：今になって復帰・再開

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail deque:C Head 旧X リソースプール α：Headが同じ黄色を差してる のでCAS成功

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail Head 旧X リソースプール deque:C C出力 α：そして吐き出すのはローカ ルバッファのC

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail deque:C Head C出力 リソースプール α：そして手順通りに消去を行う

LockfreeQueueを例に スレッドα,βが出演します Αのローカルバッファ Head: Tail Head データ構造が破綻！ リソースプール deque:C

どうしてこうなった！ ◼ ◼ ◼ CASではアドレスが一致するかどうかだけを確 認しているため、リソースを再利用すると運悪く 一致してしまう状況が起こりうる LL/SC命令という解決策もあるけれど alpha,MIPS,PowerPC等限定でx86はダメ ポインタに更新カウンタを付ければ一致の可能 性は下がるけれどコストが高い

そもそも！ ◼ 参照中のデータを他のスレッドが勝手に消すか ら悪い！ ❑ ◼ 勝手に消えなければ使い回すこともない 手段は複数あり得る ❑ ❑ ❑ 参照カウンタ ガベージコレクタ ハザードポインタ←オススメ！

参照カウンタ ◼ 誰かが参照しているノードは削除しない ❑ ◼ ◼ カウンタに触れる機会を最小限にするべき CASを行う直前にノードのカウンタを増加 ❑ ◼ ◼ shared_ptrに似てるけどそれをそのまま使うのは重 すぎて論外 その時点でカウンタが0なら触れるのを止める CASの成功・失敗に関わらずカウンタを減少 減少の結果0になったのならそれを確認したス レッドが責任を持って削除

参照カウンタ ◼ ◼ ◼ ◼ ノードにマークの代わりにカウンタを設置 CASを行う前後でそれぞれカウンタに fetch_and_addやfetch_and_subを発行 CAS1回で済んでいた物が、同期命令3回必要 パフォーマンスは検定していません… A 1 B 1 C 1 D 1

ガベージコレクタ ◼ ◼ 各スレッドはメモリからの物理的な削除を行わな い（論理的な削除にとどめる 物理的な削除はGCスレッドが、他のスレッドや ポインターからの参照状況を確認して行う

ハザードポインタ ◼ ◼ ◼ 各スレッドに「自分が今見ているポインター」を表 すハザードポインタ領域を設ける 物理的な削除を行う際に自分以外のスレッドの ハザードポインタ領域を参照する 誰かが参照しているのなら、自分のスレッドの削 除待ちリストに投入

ハザードポインタ