Lock-free List

Lockfree List

Lockfree Listって？ • 複数のスレッドから同時に挿入・検索・削除を 行う事が可能な並行線形リストをLockfreeに したもの • 挿入・削除が立て込んでいてもロックを用い ないので検索がロックされない

挿入処理 リストの繋ぎ替え処理が一瞬で片付くように工夫 して、検索処理の邪魔をしない CompareAndSwap(以下CAS)でポインタを差し 替える A D B C

挿入処理 リストの繋ぎ替え処理が一瞬で片付くように工夫 して、検索処理の邪魔をしない CompareAndSwap(以下CAS)でポインタを差し 替える A D CAS B C

挿入処理 リストの繋ぎ替え処理が一瞬で片付くように工夫 して、検索処理の邪魔をしない CompareAndSwap(以下CAS)でポインタを差し 替える A D 成功 B C

挿入処理 CASを使う事によって、同一の場所に同時に複数 の挿入が発生しても CAS E A D CAS B C

挿入処理 片方が必ず失敗する 成功 E A D 失敗 B C

挿入処理 失敗したらもう一度接続先を改めてやりなおす E A B D 失敗したのでやりなおし C

挿入処理 失敗したらもう一度接続先を改めてやりなおす E A D CAS B C

挿入処理 これで直列化できる 成功 A D E B C

削除処理 挿入処理と同様に、ポインタをCASで繋ぎ変える 削除 A B C

削除処理 挿入処理と同様に、ポインタをCASで繋ぎ変える CAS A B C

削除処理 こうして追い出した後にBをdelete - CASのおかげで、複数のスレッドが一つのノードを取り合っても複数回 deleteせずに済む A C B delete

削除処理 こうして追い出した後にBをdelete - CASのおかげで、複数のスレッドが一つのノードを取り合っても複数回 deleteせずに済む A C

しかし問題が • BとCを同時に削除しようとするとデータ構造 が破壊される 削除 A B 削除 C D

しかし問題が • BとCを同時に削除しようとするとデータ構造 が破壊される A CAS CAS B C D

しかし問題が • BとCを同時に削除しようとするとデータ構造 が破壊される – 削除したはずのCに接続されてしまう delete A C delete B D

しかし問題が • BとCを同時に削除しようとするとデータ構造 が破壊される – 削除したはずのCに接続されてしまう – こちらを状況1と呼ぶことにします A D

しかし問題が • 削除されるノードの次に挿入する際も 削除 A B E C 挿入 D

しかし問題が • 削除されるノードの次に挿入する際も CAS A B CAS E C D

しかし問題が • 削除されるノードの次に挿入する際も – 挿入されたはずの物が孤立してしまう A B C E delete D

しかし問題が • 削除されるノードの次に挿入する際も – 挿入されたはずの物が孤立してしまう – こちらを状況2と呼ぶことにします A C E D

そこで削除を２段階操作とする • ポインタに削除マークを取り付け、削除操作 をマーキング・削除の2ステップに分割する • 削除マークとポインタは一つのCASで同時に 扱う事ができるとする – 動的に確保したオブジェクトは大体4byte程度で アラインされているのでポインタの下位bitがその ままフラグとして使える • リストを辿るスレッドは、マークされたノードを 発見したらそれを削除する

そうなると？ α：ここまでイタレーションし削除マーキング A B C D

そうなると？ α：そしてCASによる削除を試みる CAS A B C D

そうなると？ α：成功したなら良し A B D C

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：ここまでイタレーションし削除マーキング A B C β：ここまでイタレーションし削除マーキング D

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：CASを試みる A β：CASを試みる B C D

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：Bのポインタがマーキングされ ているのでCASに失敗する A C D B β：Aのポインタは変わらないのでCASに成功する

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：リストの先頭からイタレーションし直す A C D

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：削除マークを発見 A C D

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして α：CASを試みる A C D

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして • 直列化できる α：CAS成功 A D C

そうなると？ • 先ほどの状況1は • α･βの2スレッドで同時に削除するとして • 直列化できる A D

そうなると？ • 先ほどの状況2は 削除 A B E C 挿入 D

そうなると？ • 先ほどの状況2は α：削除マーキング A B C E β：CASを試みる D

そうなると？ • 先ほどの状況2は α：削除マーキング A B C D E β：マークのせいでCAS失敗

そうなると？ • 先ほどの状況2は α：CASを試みる A B E C D

そうなると？ • 先ほどの状況2は α：CAS成功 B A C E β：リストの頭から再びイタレート D

そうなると？ • 先ほどの状況2は A C E β：リストの頭から再びイタレート D

そうなると？ • 先ほどの状況2は A C E β：CASを試みる D

そうなると？ • 先ほどの状況2は – 直列化できる A E β：CAS成功 C D

ポイント • リストをイタレートするときは、削除マークが 付いていないことを常に確認する – 付いているならその場で削除させる • これにより削除済みのオブジェクトに対して操作をして しまう状況を防げる – 付いていない事を確認したはずの物にいつの間 にか削除マークが付いていたならイタレートを頭 からやり直す

問題点 • イテレータがしょっちゅうリストの先頭に戻って しまうので – コストが高い。なのでイタレートを進める度にロックを繰り 返す悲観的ロックリストや、書き換えを行う時だけロックを 行い、ロックに失敗したらリストの先頭に戻る楽観的ロッ クリストなどを状況に応じて使い分ける • 読み出し頻度が多い程、ロック粒度を細かくするほうが良い – std::list<hoge>::iterator it;のような形として個々のスレッ ドにイテレータを持たせるのは無理 – そもそもSTLのlist::iteratorも並列利用は無保証 – std::setのように挿入･検索・削除の利用のみ

話題 • このリストではABA問題には未対処 – 挿入・削除が運悪く重なって、望まない状況でCASが成 功してしまう場合がある • 対処方法は２種類ある – 運悪く同じアドレスにCASすることになってもCASが成功 しないよう、ポインタに更新スタンプを付ける • スタンプが運悪く一周してしまうとやはりABA問題 – 参照している最中のオブジェクトは削除しない事にする • 参照カウンタ？ → atomicカウンタ重いです… • ガベージコレクタ？ → マルチスレッド対応のGCが必要 • ハザードポインタ → 当店お勧め

ABA問題って？ α：ここまでイタレーションし削除マーキング A B C D

ABA問題って？ α：そのまましばらく休眠 A B C D

ABA問題って？ α：そのまましばらく休眠 A B C β：別の用事でイタレーションしてくる D

ABA問題って？ α：そのまましばらく休眠 A B C β：マークを確認したので削除 D

ABA問題って？ α：そのまましばらく休眠 A B D C β：マークを確認したので削除

ABA問題って？ α：そのまましばらく休眠 A B D C γ：Bの後に新規ノードXを挿入する

ABA問題って？ α：そのまましばらく休眠 A B X D γ：挿入時に運悪くαが参照中のノードを使いま わしてしまう

ABA問題って？ α：やっと目覚める A B X D

ABA問題って？ α：Cの削除を再開する A B X D

ABA問題って？ α：CASを発行 CAS A B X D Cが保存されていた時と同じポ インタを指してしまっている

ABA問題って？ α：アドレスが一致しているのでCAS成功 A B 削除する気の無かったXが削 除されてしまう D X

ABA問題って？ • ここに書いた状況以外にも、アドレスを使いまわす 限り、意図しないアドレス一致の危険性は付いて回 る • 更新カウンタを付ければノードが使い回された後で もカウンタの値を見る事で不一致を検出できるため 問題を回避できるが、一度にCASしなくてはならな いビット数が増えるため、DCAS命令やSTMが必要 になる – 更新カウンタに割くビット数をケチるとカウンタが一巡して一致する危 険性がある

ABA問題って？ • そもそも他のスレッドが参照している最中のも のを削除して使いまわすから悪い • じゃあ削除しなければ良い。でもどうやって？ • 参照カウンタ→カウンタをatomicに操作する必要があ る上、ノードごとにカウンタが付くためリストが肥大化 • ガベージコレクタ→GC中に全スレッドを止めるしか安 全な方法が無い • そこでハザードポインタです（次回へ