マルチプロセッサプログラミングではハードを意識する必要あり。 ハードが与えるパフォーマンスの影響を考慮し、効率的な並行プログラミングに活用しましょう。
排他制御プロトコルの問題：ロックが取得できなかった時どうする？
- 再挑戦（spin, busy wait）
- 遅延が短いときは良い
- 諦めてスケジューラに任せる（ブロッキング）
- 遅延が長い時は良い（スイッチングのコストは高い）
多くのシステムは２つの組み合わせる。 両方大事だけど、この章ではスピンロックを扱う。
lock() と unlock() を持つ Lock のインスタンス (mutex) の典型的な使い方。
Lock の実装に Chapter 2 で扱った Filter や Bakery ロックは使えない？
- アクセススレッド数に比例した Ω(n) の空間計算量が問題
Chapter 2 の Peterson lock (Fig. 7-1) を復習。
- Peterson lock は starvation-free。
Peterson lock の取り合いを 50 万回も繰り返せば、同時にクリティカルセクションに入ってしまうことあり。
- 読み書きが Atomic であることを仮定 ➡ sequential consistency なメモリを期待
- モダンなマルチプロセッサは sequential consistency なメモリを提供してくれないし、 プログラム順に実行してくれる分けでもない
- 高速化のために、コンパイラの最適化が走ったり、メモリのキャッシュ (Appendix B) があるため
どうやって、メモリの一貫性を保証するか？
- メモリバリア（メモリフェンス）命令
- プログラマが自分でバリアを入れないといけない（Peterson lock の場合は read の前をバリアする）
- getAndSet/compareAndSet などの synchronization と同様に高コストだから、使用は最小限にしたい
- read/write よりコンセンサス数が大きいのを利用した直接的な手法が使える
testAndSet(getAndSet) はコンセンサス数が 2 で、初期のマルチプロセッサの主要な命令。
- spin lock に使えそう ➡ TASLock (test-and-set)
unlock されるまで待ってから testAndSet をする改良 ➡ TTASLock (test-and-test-and-set)
どちらも deadlock-free で、アルゴリズムに差はない。 実際にマルチプロセッサで、短いクリティカルセクションに n 並列で同時に入ろうとするテストをした。
こうなる理由は、モダンなマルチプロセッサのアーキテクチャから説明できる。
- 典型的なモデルとして、メモリとプロセッサ間がバスでつながっているケースを考える
- ブロードキャストで通信し、同時には送信できない
- 各プロセッサはメモリキャッシュを持っていて、メモリアクセスより高速
- キャッシュミスした場合、バスにブロードキャストして、他のプロセッサかメモリから値を取得する
このバスアーキテクチャで TASLock を再考してみる。
- それぞれの getAndSet() はバスにブロードキャストされる
- 全スレッドがバスでメモリの内容をやりとりしようとして遅延する
- さらに、他のスレッドのキャッシュを無効にしてしまい、ほぼ毎回キャッシュミスしてしまう
- それでバスの通信が入ってくるが、実際のところ値は変わっていない
- さらに、ロックのリリースでバスを使う時に、スピンのやりとりが占有しているので遅延してしまう
次に、TTASLock を見る。
- スレッド A がロックを保持していて、B がロックを取る場合
- 最初はキャッシュミスするけど、A がロックを持っている間は B の get() はキャッシュミスしない
- 従って、バスの通信がなくなり、A がロックをリリースする時もスピンによる遅延はなくなる
- ただ、ロックを解放した後は、他のスレッドがキャッシュミスが発生し、ストームが発生
TTASLock の問題は、複数のスレッドが同時にロックを取得しようとして競合状態になってしまう点。
- ロックが解放された直後に全スレッドが一斉に getAndSet(true) を実行するため競合状態になる
- 一定時間 back off させることで、一斉にロックを取得するのを防ぐ
- 連続して失敗する時は、競合状態が多い時なので、back off を長くする（2倍）
- 一斉に失敗する時も考慮して、ランダムな時間 back off する
- 最大の待ち時間は決めておく
BackoffLock は実装が簡単で、多くのアーキテクチャで TASLock よりパフォーマンスはすごく良い。 ただ minDelay と maxDelay を適切な値を選ぶ必要があるが、環境に影響されるので portable にできない。
BackoffLock より複雑だけど portable なロックを検討する。
問題点
- Cache-coherence Traffic
- 全スレッドが共有領域でスピンしているため (TASLock よりマシだが)
- Critical Section Underutilization
- スレッドが必要以上に遅延するので、クリティカルセクションを十分に活用できていない
Queue で解決。
- 先行のスレッドが終わったかどうかだけをチェックすればいい
- それぞれのスレッドが異なる領域でスピンしているので、Cache-coherence traffic は減る
- 先行のスレッドが終わったら、クリティカルセクションに入れば良い
- いつ入るかは考えなくていいので、クリティカルセクションも有効利用される
- FIFO なので公平
ALock は配列ベースの Queue Lock。
- スレッド間で tail (AtomicInteger) を共有
- 各スレッドは mySlotIndex に位置を保持（共有されない）
- lock()
- tail の位置を mySlotIndex に入れて、tail を進める
- 自分の番になるのを（flag[slot] == true）を待つ
- unlock()
- 自分のロックを解放（flag[slot] = false）
- 次のスレッドにロックを渡す（flag[(slot + 1) % size] = true）
flag 配列が共有されているけど、各スレッドは別々の位置でスピンしているからストームは競合は最小限。
- キャッシュが同一ライン（ブロック）で共有する場合（false sharing）に競合が発生するかもしれない。
- キャッシュラインの一カ所を変えるとライン全体が無効になる
- Fig. 7.8 はキャッシュラインが 4-word の例
- (a) は隣り合う 4 つが競合している
- (b) は pad を入れて、競合をなくす対策をしている
ALock は BackoffLock より効率がよく starvation-free だが、空間効率が悪い。
- 最大スレッド数 n 、ロック数 L で O(Ln) の空間計算量
- ロック毎に n 個分の領域が必要
CLHLock の登場。
- QNode にスレッドの状態を保持
- predecessor の locked フィールドが false になるのを待つ
- それぞれが predecessor を見ているので仮想的なリンクリスト構造になる
- tail は、最後に入って来たノードを参照する
- 新しいノードは getAndSet を使うことで、tail を pred にし、自分を tail にできる
- ロックがリリースされた pred ノードは誰からも参照されていないので、再利用する
- 最大スレッド数 n 、オブジェクト数（ロック数） L で O(L + n) の空間計算量
- スレッド毎に myNode が n 個あり、ロック毎に tail が参照するノードが L 個ある
- 最大スレッド数 n 、オブジェクト数（ロック数） L で O(L + n) の空間計算量
利点
- ALock 同様に、各スレッドが別の位置でスピンしているの
- ロックのリリースは、successor のキャッシュにしか影響がでない
- 必要な領域も少ない
- FIFO の公正さも維持
欠点
- キャッシュレスの NUMA (Non-Uniform Memory Access) アーキテクチャで効率が悪い
- predecessor のロックでスピンしているけど、リモートメモリだとコストが高くなる
NUMA 問題は MCSLock が解決。
- リンクリストの構造は一緒だが next を持つので仮想的ではなくなった
- ロック時に tail のノードを pred として pred.next 自分を設定し、tail も自分に向ける
- 自分のメモリにある myPred の locked でスピンする
- アンロックする時に next の locked を false にする
- tail が変わっているけど、next がまだセットされていない状態（スピン直前のスレッド）がある
- next がセットされるまで待つ（Line 34）
利点
- CLHLock の利点は同じ
- 各スレッドが自分のメモリでスピンしているので NUMA でも大丈夫
- O(L + n)
欠点
- ロックのリリース時にスピンが必要な場合がある
- reads, write, compareAndSet の命令数は増える