Skip to content

Instantly share code, notes, and snippets.

@wm3

wm3/gist:4463523

Last active December 10, 2015 16:48
Show Gist options
  • Save wm3/4463523 to your computer and use it in GitHub Desktop.
Save wm3/4463523 to your computer and use it in GitHub Desktop.
Download ZIP
The Art of Multiprocessor Programming 読書会 第五回 九章
Raw
gistfile1.md

Linked Lists: The Role of Locking

9.1 Introduction

データ構造への各処理をロックでラップした並列化対応

  • coarse-grained synchronization (粗い同期)と呼んでいる
  • スケーラビリティがあまり良くない

更に進んだ同期

  • fine-grained synchronization (細かい同期)
  • optimistic synchronization (楽観的な同期)
  • lazy synchronization (遅延同期)
    • 削除を論理的な物と物理的な物に分離
  • nonblocking synchronization (ブロッキング無しの同期)

本章では linked list を使った set (図9.1)に対する同期を例にして紹介

  • 様々なデータ構造に対して応用できる(らしいが…)

9.2 List-Based Sets

今回使う Set の実装

  • ソートされた linked list
  • 各ノードには item(値)/next(次のノード) の他に key という属性がある
    • key は item の hash 値 (int)
    • set は key でソート
    • key は重複しないと想定
  • head / tail という特殊なノードを用意
    • head の key には hash の最小値、tail には hash の最大値を入れる
  • 図9.3 に追加と削除の例

9.3 Concurrent Reasoning

並列のデータ構造の正しさの証明は一見難しいが、習得できるスキル

考え方

データ構造が満たす不変条件を定義し、各操作で違反しないかどうかを考える

freedom from interference (干渉からの自由?) 特性

  • 定義された操作以外で内部を書き換える事が無いという特性
  • リストから削除されたノードに対しても必要
  • リンクが切れたノードを他のスレッドが使っている時があるから

representation invariant (表現の不変条件、クラス不変条件?)

  • ( http://en.wikipedia.org/wiki/Class_invariant )
  • (オブジェクト指向関係で使われる?)
  • クラスが常に持つべき不変条件の事
  • set の invariant
    • head/tail の追加や削除を行わない
    • ノードはキーでソートされる、キーは一意

abstraction map (抽象化マップ?)

  • データ構造としての状態と内部構造のマッピングの事
  • (set で言えば contains() の中身と言えば良いのか…? )

各特性について

safety と liveness

  • linearization point を見つける事で証明

実装方法によってprogress guarantee (進行の保証具合?)が異なる

  • wait-free … 全ての処理が固定ステップで終了する
  • lock-free … いずれかの処理は固定ステップで終了する

その他、章の流れについて

  • set に対して順に(より洗練されて複雑な)同期処理に作り変えていく
  • 厳密な証明は行わない
  • 説明に curr, pred という名前のローカル変数を共通で使う。
    • pred は curr の一つ前の要素

9.4 Coarse-Grained Synchronization

各処理を lock/unlock でラップしただけ。(図9.4、図9.5)

9.5 Fine-Grained Synchronization

各処理ではなく、参照や修正している要素だけをロックするアプローチ

実装方法について

lock coupling という手法を使う

  • pred のロックを保持している場合にのみ curr をロックする (head 以外)
    • curr が削除される (pred.next が curr を参照していない) 可能性があるため

実装: FineList (図9.6、図9.7)

  • remove() での削除時は pred と curr の両方をロックしなければいけない
    • pred だけロックした場合に、削除漏れが生じる (図9.8)
  • ロックの取得順は統一する必要がある
    • デッドロックが生じる (図9.10)

特性について

  • representation invariant を満たす
  • abstraction map は同じ

linearization point

  • add(a)

    • a がない場合は、a.key より大きい key を持つ最小のノードがロックされた時
    • a がある場合は、aのノードがロックされた時
      • (誤植あり?)

  • remove(a)

    • a がある場合は、a の pred がロックされた時
    • a がない場合は、a.key より大きい key を持つ最小のノードがロックされた時

  • contains(a) は exercise

    • (curr.key >= a.key になった時?)

  • starvation free

    • ただし証明は難しい

  • deadlock free

    • どの処理でもロックの取得順序が同じなので

9.6 Optimistic Synchronization

Fine-Grained Synchronization の欠点

  • ロックの取得と解放の連続
  • 離れた場所のロックが発生する可能性がある

Optimistic なアプローチ

  • 検索する時にロックしない
  • 代わりに、検索完了時にバリデーションを行う
    • バリデーションに失敗すればやり直す
  • (9.6～9.8は、FineList のロックを消していく作業)

実装: OptimisticList (図9.11、図9.12、図9.13)

  • バリデーション (図9.14)
    • pred/curr の組が正しいかをチェック
    • pred/curr がリストに存在することと、pred.nextがcurrである事
    • (pred.next じゃなくても curr がリストにあれば良いような気も…?)
      • (ロックの状態が崩れるからダメか…)
  • contains() 時にもロックとバリデーションを行う
    • (理由が分かっていない…)

バリデーションが必要な理由 (図9.15)

  • 検索とロックの間にノードが削除される可能性があるから

検索時にはロックしないので削除されたノードを参照する事がある

  • ただし、すぐに元のリストに戻る事になる

starvation free でない

9.7 Lazy Synchronization

Optimistic Synchronization の欠点の解消

  • contains() でロックをしない
  • validate() でリストの走査を行わない

ノードの論理削除を表す mark フィールドを付ける

  • mark が false な時はリストに存在し true なら存在しない事を保証する

実装方法について

実装: LazyList (図9.16、図9.17、図9.18、図9.19)

  • add() と remove() の処理はほぼ前回と一緒
  • validate() では mark と pred.next だけをチェックする。各ノードのループをしない。
  • contains() ではロックをしない

バリデーションが必要な理由 (図9.20)

  • ロック取得前に削除されるケース
  • ロック取得前に追加されるケース

特性について

abstraction map が変更される

  • marked の条件を追加

linearization point

  • add(a)
    • OptimisticList から変更無し
      • (OptimisticList の linearization pointは書かれてないが…)
  • remove(a)
    • a がある場合は、mark がセットされた時
    • a がない場合は、OptimisticList から変更無し
  • contains(a)
    • a がある場合は、unmarked なノードが見つかった時
    • a がない場合は、状況による(図9.21)
      • (a) 削除された場合
      • (b) 削除された後で a が再度追加された場合
        • ノードが検索された時点と、aが追加された時点の早い方

論理的な削除と物理的な削除の分離はメリット

  • 物理的な削除はいつ行っても良い

add()とremove()がブロックしているのが欠点

9.8 Non-Blocking Synchronization

Lazy Synchronization の欠点の解消

  • add()/remove() でロックをしない

基本的なアイデア

ノードの物理的な削除のタイミングを変更

  • 検索時に行う。
  • ロックしていないので、remove()時にcurrのmarkとpred.next の更新を同時に行えなくなっているため??

実装: LockFreeList (図9.24、図9.25、図9.26、図9.27)

  • pred/curr の組を Window クラスにくくりだし
  • find()
    • add()/remove() での検索処理を共通化
    • mark されたノードを削除
    • ノードの削除に失敗した場合はやり直し
    • benevolent side effect: 状態は変更せず、内部の構造だけ変更する
  • add()
    • find()への置き換えとcompareAndSetの使用
  • remove()
    • find()への置き換えとcompareAndSetの使用
    • 物理削除は試すが、失敗しても放置する
  • contains()
    • 実質的な変更は無し

abstract map は LazyList と同じ

9.9 Discussion

LazyList と LockFreeList はトレードオフ

  • LockFreeList の制約
    • reference と boolean のアトミックな同時修正にコストがかかる
      • (これはどの程度?)
    • 物理削除が遅れて実施されるので、意図しない場所での競合が発生する
  • LazyList の制約
    • add()/remove() のブロック
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment