Skip to content

Instantly share code, notes, and snippets.

@sile

sile/AMP-CH7-a.md

Last active June 30, 2019 20:34
Show Gist options
  • Save sile/6a0fd3da6fb2f02ef163 to your computer and use it in GitHub Desktop.
Save sile/6a0fd3da6fb2f02ef163 to your computer and use it in GitHub Desktop.
Download ZIP
The Art of Multiprocessor Programming - 第七章前半
Raw
AMP-CH7-a.md

七章 スピンロックと競合

目的:

  • 現時点では、効率的な並列プログラムを書くには、基盤となるマシンアーキテクチャを把握している必要がある
  • この章の目的は、
    • アーキテクチャが、並列プログラミングの実行性能にどのような影響を与えるかを理解する
    • そのうえで効率的なプログラムの書き方を学ぶ
  • 皆がなじみのある相互排他(ロック)の現在のマルチプロセッサ上での効率的な実装の話から始める

全ての相互排他プログラムに共通の疑問:

  • Q. ロックを獲得できなかった場合にどうする？
  • A-1. 再試行 => スピンロック
    • 定期的にロック獲得を試すことは spinning or busy-waiting という
    • Filter や Bakery アルゴリズムは、スピンロック
    • ロックの遅延が短いと予測されるならスピンロックは適切
    • シングルプロセッサ環境では無意味
  • A-2. 自らの実行を待機 => ブロッキング
    • OSのスケジューラには、他のスレッドの処理を担当させる
    • コンテキストスイッチは効果なので、ブロッキングはロックの遅延が長いと予測される場合にのみ効果的
  • 多くのOSでは、両方の戦略を組み合わせたものが使用されている
    • ex. 短期間スピンロックして、その後ブロッキングに移行
  • どっちも重要な技術だが、この章ではスピンロックに焦点を当てる

7.1 現実世界へようこそ

  • java.util.concurrent.locks.Lock インタフェースを使います
    • lock(), unlock()
    • 典型的な使用例 (lock -> try -> body -> finally -> unlock)

効率的なロックアルゴリズムが欲しいなら第二章で学んだものを使えば良いのでは？

  • たとえば、FilterロックやBakeryロック
  • 空間性能の問題があるので厳しい
  • read/write命令を使って実装されているロックは、想定利用スレッド数に線形の空間が必要

さらに、第二章のコードは、現実世界ではそもそも適切に動作しない

  • 図7.1にPetersonロックを再掲
    • 相互排他を保証する上では、7-9行目が重要
  • この実装(ロック)を使って、二スレッドが延々と共有カウンタを増加するプログラムを書いてみると、最終結果は期待とは少し異なる値になるでしょう
    • 二章で正当性を頑張って証明したにも関わらず
    • シャーロックホームズの台詞を引用

では、図7.1のコードはどこが悪いのか？

  • ロジックは間違っていない
  • 現実世界に対する仮定が間違っている
    • マルチプロセッサ上でのプログラミングを行う時に、普通はread/write命令はアトミックだと想定する
      • メモリへのread/write命令はsequential consistentだと想定
      • 全スレッドに共通のグローバルな、プログラム順に即した実行順序を有する
      • この仮定の元であれば、Petersonロックは適切に動く
        • これが崩れると 7-9行目が上手く動かない
    • 不運なことに、現在のマルチプロッセは典型的には、sequential consistent memoryを提供していない
      • 加えて単一スレッドでのread/write命令がプログラム順に従うことも保証されない

なぜsequential consistencyが保証されないのか？

犯人は二人。

  1. コンパイラ
  • 性能を向上させるために、勝手に命令の実行順序を並べ替える
  • 大抵のプログラミング言語は、単一の変数に対する命令の実行順序は保証する
    • ただし、(依存関係のない?)複数変数に渡っては保証しない
    • 図7.1の7行目と8行目をコンパイラが入れ替えることも可能 (Eq.2.3.9が崩れる)
  1. マルチプロセッサハードウェア
  • メモリへの書き込み命令は即時に反映される必要がない
    • ハードウェアベンダーは公言している
    • 実際のプログラムでもwrite命令と共有メモリが、常に即時に同期することは要求されない
  • 多くのマルチプロセッサアーキテクチャでは、共有メモリへのwrite命令は write buffer(or store buffer) と呼ばれるローカル領域にバッファされる
    • 必要とされて始めて、共有メモリに書き出される
    • 図7.1の8行目(victimへの書き込み)がバッファされると Eq.2.3.11 が崩れる

ではsequential consistencyが必要な時はどうする？

  • 現代のアーキテクチャでは memory barrier(or memory fence) という命令が大抵提供されている
    • outstandingな命令が即時に反映されるように強制でき、write bufferの使用による命令の順序変更を防げる
    • どこにメモリバリアを入れるかを判断するのは、プログラマの責任
      • Petersonロックなら、各読み込み命令の前に入れれば、ちゃんと動くようになる
  • ただし、メモリバリアはコスト高
    • CAS命令がコスト高なのと同様 (CASやvalatileフィールドへの読み書きは、内部でメモリバリアを使っている)
    • 効率的なマルチプロセッサプログラムを実装したいなら、使用は最低限に留めたいので、ロック実装でもいろいろ工夫する

7.2 Test-And-Setロック

TASLock

  • testAndSet()命令を使ったロック
    • testAndSet()のコンセンサス数は2
    • 対象メモリ領域の値がfalseなら、trueを書き込む (返り値は古い値)
    • 一件、スピンロックの実装には最適に見える
    • 図7.2がその実装: 実装ではgetAndSet(true)を代わりに使っている

TTASLock

  • 図7.3
  • TASのalternative
  • testAndSet()の前に、一回単純なreadチェックを挟んでいる以外は同様

TASLockとTTASLockの違い

  • TASLockとTTASLockは、正当性の観点では、全く同一
  • 実際のマルチプロセッサ上で雨後各と、性能が全く異なる
    • 図7.4
    • TASLockはかなり非効率(スケールしない)

現代のマルチプロセッサアーキテクチャの観点から説明可能:

  • 注意: アーキテクチャは多岐に渡るので、過度な一般化には気をつける必要がある
  • キャッシュ(caching)と局所性(locality)に関しては、詳細は違えと、大抵のアーキテクチャが似たような性質を備えている
  • 簡単のために典型的なマルチプロセッサアーキテクチャを対象とする
    • プロセッサ同士は bus と呼ばれる共有ブロードキャスト媒体を使って通信(communicate)する
      • プロセッサとメモリコントローラはbus上にブロードキャストが可能
        • ただし、一度にbusを使えるのは一つのプロセッサ(or メモリコントローラ)のみ
      • busバースのアーキテクチャは良く使われているけどスケールが難しい
    • 各プロセッサは cache と呼ばれる高速かつ小さなメモリを備える
      • cacheへのアクセスは、メモリへのアクセスに比べて桁違いに高速
      • 近い将来にメモリアクセス速度が、キャッシュアクセス速度に追いつくことは無さそう
        • マルチプロセッサアーキテクチャの全体性能をあげるためにはキャッシュ性能が重要
    • プロセッサが特定のメモリアドレスからデータを読み込む際には、まず自分のキャッシュがチェックされる
      • キャッシュに存在する場合は cache hit と呼ばれる
      • 存在しない場合は cache miss と呼ばれる
        • cache missした場合は、共有メモリないし他のプロセッサのキャッシュからデータを探す必要がある
            1. 対象アドレスをbus上にブロードキャスト
            1. bus上を snoop している他のプロセッサが、対応するデータを自分のキャッシュ内に保持している場合は、それをブロードキャストする
            1. どのプロセッサのキャッシュ内にも存在しない場合は、メモリが応答する
            • メモリが応答するタイミングはどうやって決定する？

7.3 TASベーススピンロック再考

以上を踏まえて、TASLockが共有バスアーキテクチャ上でどのように振る舞うのかを見てみる:

  • 各getAndSet()呼び出しは、bus上にブロードキャストされる
  • 全てのスレッドはメモリと通信するために、busを使う必要があるので、getAndSet()呼び出しは全てのスレッドを遅延させる
    • ロック待ちではないスレッドも含めて
  • さらに悪いことに、getAndSet()呼び出しは、他のプロセッサに、自分のキャッシュ内のロックオブジェクトのコピーを破棄することを強制する
    • 各スピニング毎にキャッシュミスが発生し、(ほぼ毎回前回と同じ値を取得するために)bus経由で値をfetchする必要がある
  • またさらに悪いことに、spinner達によってbusが占有されているため、ロックを獲得しているスレッドのロック解放が遅らされてしまう
  • よってTASLockはとてもpoorlyです

TTASLockの場合はどうか:

  • スレッドAがロックを獲得している場合:
    • スレッドBは、以下のspinningループに入る:
      1. ロックオブジェクトをチェック => 初回はcache miss
      2. 二回目以降のロックオブジェクトチェック => プロセッサのキャッシュから読み込み
        • 二回目以降はbusトラフィックは発生しないので、他のスレッドのメモリアクセス等を遅延させない
  • スレッドAがロックを解放した場合:
    • ロック保持者がlockを解放する
    • spinner達のキャッシュコピーは破棄される
    • それぞれでcache missが発生し、busを経由した再読み込みが走る
    • 各spinnerがgetAndSet()を呼び出し、最初の一つだけがロック獲得に成功する
    • 再度、spinner達のキャッシュコピーが破棄され、bus経由での再読み込みが行われる
    • その後は local spinning に落ち着く

local spinning は効率的なスピンロックをデザインする上で重要な原則。

7.4 指数的バックオフ

TTASLockをどうすれば改良できるか考える。

用語:

  • contention: 複数スレッドが同時にロックを獲得しようとしている状況
    • high contention <=> low contention

TTASLockはlockが解放されたタイミングで競合が高くなってしまう可能性がある。

getAndSet(true)の同時呼び出しは、バストラフィックを圧迫するので好ましくない。

バックオフを挟んで他のスレッドにロック獲得の機会を譲った方が得策。

ではロック獲得を再試行するまでにどれくらいの感覚のバックオフを取るのが良いのか？

  • 良いルール: ロック獲得失敗回数が多い => 競合が高そう => より長い期間バックオフすべき
  • 簡単な方法:
    1. ロック獲得に失敗
    2. ある範囲内でランダムな時間だけバックオフ
    3. さらに失敗したら、範囲を倍に広げて 2 から繰り返す
    • ただしバックオフの範囲はあらかじめ定めた上限値を超えないようにする

バックオフはいくつかのロックアルゴリズムで共通で使用されるものなので 図7.5 でBackoffクラスとして定義しておく。

図7.6はBackoffクラスを使ったロックアルゴリズム(BackoffLockクラス)。

重要なのは、スレッドがバックオフするのは「ロックが空いているようにみえて」かつ「その直後のロック獲得に失敗した」場合のみ。

他のスレッドによって獲得されているロックを観察することは、競合度に関してらなんらの情報を与えることはない。

BackoffLockは実装簡単かつ多くのアーキテクチャでTASLockに比べて顕著な性能改善をもたらす。

ただ残念なことに、その性能はminDelayとmaxDelayに何を選択するかによって大きく左右されてしまう。

特定のアーキテクチャに最適化するのは簡単だが、(例えばプロセッサの数や速度が異なる)異なる環境でも最適となるような可搬な値を前ももって設定するのは難しい。

7.5 キューロック

スケーラブルなスピンロックを実装するために別のアプローチを探ってみる。
(そしてバックオフロックよりは複雑だが、その性質からしてより可搬なロックを構築する)

BackoffLockアルゴリズムには二つの問題点があった:

  1. Cache-coherence Traffic: 全てのスレッドが同じ共有オブジェクト上でスピンしていた
  2. Critical Section Underutilization: スレッド群は必要以上に長い間遅延させられていた

スレッド群をキューを使って保持することでこれらの欠点を克服することが可能:

  • 各スレッドは自分の番になったかどうかを、その前のスレッドが完了しているかどうかをチェックすることで判断できる
  • Cache-coherence trafficは、それぞれが異なる位置でスピンすることで緩和できる
  • 自分の番が来たことを前の人に教えて貰うことで、(次にいつ試行するかを無駄に推測する必要がなく)クリティカルセクションをより活用できる
  • first-come-first-served fairnessも提供される

この後の節で、いくつかの異なる実装のqueue locksを見ていく。

7.5.1 配列ベースのロック

図7.7はシンプルな配列ベースのキューロック(ALock)の実装。

// 図7.7

public class ALock implements Lock {
  // スレッドローカル変数。
  // スレッドをまたいで値は共有されない。
  // 値の取得はget(), 設定はset() メソッドをよびだす。
  ThreadLocal<Integer> mySlotIndex = new ThreadLocal<Integer>() {
    protected Integer initialValue() {
      return 0;
    }
  }

  AtomicInteger tail;       // スレッド間で共通のユニークな採番を行うための変数
  volatile boolean[] flag;  // この配列の中でtrueになっているインデックスに対応するスレッドがロックを獲得できる
  int size;                 // 最大スレッド数
  
  public ALock(int capacity) {
    size = capacity;
    tail = new AtomicInteger(0);
    flag = new boolean[capacity];
    flag[0] = true;
  }
  public void lock() {
    int slot = tail.getAndIncrement() % size; // 各スレッドにユニークなインデックスが割り振られるようにする
    mySlotIndex.set(slot);   // 自分のインデックスを保存しておく
    while (! flag[slot]) {}; // 図7.8にあるようにflagの各要素がキャッシュラインをずらして配置されていれば別スレッドによる値変更時のfalse invalidationを軽減できる
  }
  public void unlock() {
    int slot = mySlotIndex.get();
    flag[slot] = false;             // 自分のロックを解放
    flag[(slot + 1) % size] = true; // 次のスレッドに権利を移す
  }
}
  • flag配列は共有されているけど、それぞれのスレッドは配列の異なる領域(要素)でスピンするのでcontentionは最小化される
    • spins on locally cached copy of a single array location, greatly reducing invalidation traffic
  • ただしfalse sharingというものがあるので、まだ競合は発生する
    • 配列の要素群のように、隣接するデータアイテムが同じ単一のキャッシュラインを共有する場合に起こり得る
        1. 特定のアイテムへの書き込み
        1. キャッシュラインのinvalidate
        1. 隣接する(更新がない)アイテム群のキャッシュも一緒にinvalidate
        1. 隣接するアイテム上でspinしていたCPUでもバストラフィックが発生してしまう！
    • 図7.8: 要素の間にpaddingを入れればfalse sharingを回避できる

7.5.2 CLHキューロック

ALockはBackoffLockの改良となっている:

  • キャッシュのinvalidationを削減 (reduce invalidations to a minimum)
  • ある人によって解放されたロックを、別の人が取得するまでの間隔は最小
  • TASLockやBackoffLockと違って、飢餓が起こらないことも保証できる
  • first-come-first-served fairnessも提供する

ただし空間効率は悪い:

  • 想定される総スレッド(n)に比例した空間が必要
  • L個の異なるオブジェクトを同期したいなら O(Ln) の空間が要求される

別のスタイルのキューロックを見てみる。

図7.9 and 図7.10: CLHLockの実装

// 図7.9: フィールドとコンストラクタ
public class CLHLock implements Lock {
  AtomicReference<Qnode> tail;  // 初期値は null
  ThreadLocal<QNode> myPred;    // 初期値は null
  ThreadLocal<QNode> myNode;    // 初期値は QNode(): myPredとmyNodeを合わせて"virtual" linked-list
  public CLHLock() {
    tail = new AtomicReference<QNode>(null);
    myNode = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return new QNode();
      }
    };
    myPred = new ThreadLocal<QNode>() {
      protected QNode initialValue() {
        return null;
      }
    }
  }
  
  // 図 7.10: lock and unlock
  public void lock() {
    QNode qnode = myNode.get();
    qnode.locked = true;                // 自分のノードにロックマークを付ける
    QNode pred = tail.getAndSet(qnode); // キューの末尾に自ノードを追加
    myPred.set(pred);       // 一つ前のノードを保存(後で再利用するため。保存は必須ではない)
    while (pred.locked) {}  // 一つ前のノードが解放されるまで(ローカルキャッシュ)スピン
  }
  public void unlock() {
    QNode qnode = myNode.get();
    qnode.locked = false;     // 獲得していたロックを解放
    myNode.set(myPred.get()); // ノードを再利用する (性能を考えないなら new QNode() でも良いはず)
  }

  // QNode の定義(推測)
  class QNode {
    boolean locked = false;
  }
}

CLHLock(でのノードのrecycle)を工夫すればO(L + n)まで空間使用量を落とせます。(L=ロックオブジェクト数, n＝最大スレッド数)。

図7.11は CLHLock の実行例

CLHLockの利点:

  • ALockと同様に、各スレッドは異なる領域に対してスピンする
  • ロックが解放された時には、その次のスレッドがスピンしている領域だけがinvalidateされる
  • ALockに比べて要求される空間が大幅に少なく、事前に最大スレッド数を知っている必要がない
  • first-come-first-served fairnessを提供する

CLHLockの(唯一の)欠点:

  • NUMAアーキテクチャでは性能が伸びない
  • 各スレッドは、その前のノードのlockedフィールドを監視するが、もしそのメモリ領域がリモートにあると性能が悪化する。
  • cache-coherentアーキテクチャなら、このアプローチは上手くいくでしょう

7.5.3 MCSキューロック

図7.12 and 図7.13: MCSLockの実装

// 図7.12: フィールドとコンストラクタ
public class MCSLock implements Lock {
  AtomicReference<QNode> tail;  // 初期値は null
  ThreadLocal<QNode> myNode;    // 初期値は new QNode()
  
  public MCSLock() {
    tail = new AtomicReference<QNode>(null);
    myNode = new TheadLocal<QNode>() {
      protected QNode initialValue() {
        return new QNode();
      }
    };
  }
  
  // QNodeクラス: リンクリスト
  class QNode {
    boolean locked = false;
    QNode next = null;
  }
  
  // 図7.13: lock and unlock
  public void lock() {
    QNode qnode = myNode.get();
    QNode pred = tail.getAndSet(qnode); // 自ノードをキューの末尾に追加する
    if (pred != null) {
      // 既にロック保持者がいるかどうか
      qnode.locked = true;  // 自分がロック待ちであることをマークする 
      pred.next = qnode;    // 一つ前の順番にノードの後ろに自ノードをつける
      // wait until predecessor gives up the lock
      while (qnode.locked) {}  // スピンするのは自ノードのフィールドなのでremote領域ではないことが保障される
    }
  }
  public void unlock() {
    QNode qnode = myNode.get();
    if (qnode.next == null) {
      if (tail.compareAndSet(qnode, null))
        return; // ロック待ちの人はいない
        
      // wait until successor fills in the next field
      whlie (qnode.next == null) {}  // 次のスレッドが21行～22行にいる場合は待機
    }
    qnode.next.locked = false; // 次のスレッドにロックが解放されたことを通知
    qnode.next = null;
  }
}

図7.14はMCSLockの実行例

  • MCSLockはCLHLockの利点を共有している。
    • in particular, the property that each lock release invalidates only the successor's cache entry
  • 各スレッドがスピンする場所を制御可能なので、cache-less NUMAアーキテクチャとも相性が良い
  • 空間使用量も O(L + n)

欠点:

  • ロック解放でspinningは必要
  • CLHLockよりも単純なオーバヘッドは大きい: it requres more reads, writes, and compareAndSet() calls
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment