5.2K Views
April 12, 23
スライド概要
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スレッドが、他のスレッドや ポインターからの参照状況を確認して行う
ハザードポインタ ◼ ◼ ◼ 各スレッドに「自分が今見ているポインター」を表 すハザードポインタ領域を設ける 物理的な削除を行う際に自分以外のスレッドの ハザードポインタ領域を参照する 誰かが参照しているのなら、自分のスレッドの削 除待ちリストに投入
ハザードポインタ