Lock-free Queue

Lockfree queue

Lockfreeって？ • 線形リスト・スタック・キュー・木といったデータ構造 はシングルスレッドでの利用が前提 • 複数スレッドで共有する場合はmutexなどでロック するのが一般的 • 共有出来るデータ構造を並行データ構造と呼ぶ

Lockfreeって？ • 線形リスト・スタック・キュー・木といったデータ構造 はシングルスレッドでの利用が前提 • 複数スレッドで共有する場合はmutexなどでロック するのが一般的 • 共有出来るデータ構造を並行データ構造と呼ぶ ロックを用いない並列データ構造を Lockfreeデータ構造と言う

Lockfree queueは？ • 共有するためにロックを用いないキュー (FIFOバッファともいう)の事 • Atomic操作はTestAndSet命令に依存 – 比較して一致した場合に代入 を一気に行う命令 – 比較して一致しなかった場合は何も行わない – CompareAndSetとも言う(以後CASと表記) • バッファが空の時にdeque操作がブロックす るかどうかの話とは無関係

基本戦略(1/3) • 線形リストのqueueを実装 • 節点のポインタをCASで一息に差し替える • 複数の同時enqueもCASによって直列化 CAS C1 CAS C2 C3 B CAS A

基本戦略(2/3) • 結果的に一つのenqueだけ成功する • 複数のスレッドが同時に同一の場所を書き換 えようとしても破綻しない C1 成功 C2 失敗 C3 失敗 B A

基本戦略(3/3) • 失敗した残りのenqueは更新された末尾ノー ドをターゲットに再びCASを実行する • 以後繰り返し • deque側の手続きも基本的に同じ戦略 CAS C2 C1 CAS C3 B A

初期状態 • HeadとTailが同一のダミーノードを指す Tail NULL Head Dummy

キューへの挿入(1/5) • ① Tailのnextに新規ノードを繋げる • ② Tailを更新する Tail Head New CAS Dummy ①

キューへの挿入(2/5) • 1ステップ目は更新出来るまで繰り返す • しかしTailの更新は失敗しても放置 • Tailが誰かによって先に更新された場合に失敗 Tail CAS Head ② ←失敗するかも New Dummy

キューへの挿入(3/5) • ①だけ終わった状態では下記のようになる • ここで別のスレッドがenque,dequeしにきた 場合が問題 Tail New Head Dummy

キューへの挿入(4/5) • この場合は後続のenque,dequeが訂正操作を行う (遅延メソッド) • ①を行ったスレッドによるTail更新はその代わり失敗 するが、前述の通り放置 Tail Head CAS New Dummy

キューへの挿入(5/5) • 1ステップ目の操作のみを線形化ポイントとす る事で並列性を高めている Tail New Head Dummy

キューからの取り出し(1/5) ① Headの指している物のNext(つまりA)を確保 ② HeadをCASですげ替える(失敗したら①から) ③ 確保しておいた物を結果として返す Tail Head ① A B A Dummy

キューからの取り出し(2/5) ① Headの指している物のNext(つまりA)を確保 ② HeadをCASですげ替える(失敗したら①から) ③ 確保しておいた物を結果として返す Tail Aがdequeされる A B A ③ Head ② CAS

キューからの取り出し(3/5) Aを保持していたノードが次のDummyになる （自動的にそうなる Tail Head B Dummy

キューからの取り出し(4/5) 保持するノードが1つだけになった場合にHeadとTail が同一のノードを指す場合がある。 具体的にはenque操作の①のCASが完了した瞬間 Tail Head A Dummy

キューからの取り出し(5/5) その場合はTailをCASにて更新させてからやり直す よってHeadがTailを追い越すことは起こり得ない Tail Head CAS A Dummy

まとめ • CompareAndSetを使って複数のスレッドが共有す るFIFOを作る事ができます • ソースコードはgithubに上げました • デュアルコア環境(AthlonX2 5000+)ではmutexで ロックして共有したstd::queueより遅かったです… • ABA問題とリソースのプールとGCが登場する LockfreeQueueの話は希望が有れば