Hazard Pointer

5.2K Views

April 12, 23

スライド概要

profile-image

分散システムとかデータベースとかロックフリーとかが好きです。

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

Hazard Pointer

2.

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

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

ハザードポインタ