並列分散プログラミング

続き 共有メモリ 1アドレスに対する不可分なread-modify-write 複数アドレスに跨る不可分な更新/読み出し 排他制御 versioning + indirection Lamportのconcurrent reading and writing

Lamportのconcurrent reading and writing 問題設定 共有変数 a1, …, an (最初は 0) writer一人: a1++; …; an++; reader複数: a1 = … = an = 0またはa1 = … = an = 1のどちらかだけを読みたい 排他制御をしない(readerにwriterがblockされない)

手法 v1, v2 : 新たな共有変数(最初は0) writer () { v1++; update(a1, …, an); v2++; } reader () { while (1) { t2 = v2; read(a1, …, an); t1 = v1; if (t1 == t2) break; }}

なぜ正しいか? W1; W2; R2; R1; W1; R2; W2; R1; W1; R2; R1; W2; R2; W1; W2; R1; R2; W1; R1; W2; R2; R1; W1; W2;

メッセージパッシング 基本的モデル 名前(例えば0, 1, …, P–1)のついた固定台数のプロセス+ローカルメモリ メッセージ: (大きくても良い)バイト列 send(p, M); M = recv(); M = poll();

通信 send/recv

順序制約 (1) 2ノード間の順序制約 p: result := 100; send(q, “done”): q : if (recv() == “done”) { result@p == 100のはずダナ… } result := 100 p: ここではresult == 100 q:

順序制約 (2) q : if (recv() == “done”) { result@r == 100 ??? } p: send(r, “do result := 100;”); send(q, “done”): q : if (recv() == “done”) { result@r == 100 ??? } r: if (recv() == “do result := 100”) { result := 100; } result := 100; r: p: result@r == 100??? q:

不可分・原子性(1) 1ノードのメモリに対するread-modify-writeはno problem

不可分・原子性(2) 複数ノードにまたがる不可分・原子性の保証はややこしい 例題: 値交換プロトコル

値交換プロトコル 問題 二つのノードの値を「不可分に」更新できればこんなに単純な話はない 各ノードが一つずつ値を持っている 時々各ノードは他の人と値を交換したくなる 値が永遠に消滅したり重複したりしてはならない 二つのノードの値を「不可分に」更新できればこんなに単純な話はない t = vp; vp = vq; vq = t;

簡単? if (feel-like-so) send(any, ask(v, id)); while (1) { received(ok(x))  v = x; received(ask(u, q))  { send(q, v); v = u; } } p q ask(Vp) ok(Vq)

ダメな例 r (10) p (20) q (30) ask(20) ask(10) ok(30) ok(20) 20 30 20

次の試み Q = {}; if (feel-like-so) { send(any, ask(v, id)); asking = true; } while (1) { received(ok(x))  { v = x; asking = false; } received(ask(u, q))  Q.enq(ask(u, q)); !Q.empty() && !asking  { ask(u, q) = Q.deq(); send(ok(q, v)); v = u; } }

またダメ p (20) q (30) ask(20) ask(30)

まとめ 並列プログラムの難しさの根源 すでに観測した具体例 「次におこること」を神様が決める 神様の選択肢はあまりにも多い どの選択をされても動くようにプログラムを書かなくてはならない すでに観測した具体例 順序の保証(X must happen before Y) 複数の場所に跨る不可分(原子的)操作

並列プログラムのモデル化: 基本アイデア プログラム: 状態の集合と各ノードが起こしうる状態遷移を規定している 系全体: プログラムを複数，通信手段(メッセージ配送手段，共有メモリ)で組み合わせたもの 可能な状態遷移の中から(神様が)次の状態を決める

メッセージパッシング メッセージ = M (可能な全てのメッセージ) ノードプログラム = < Z, I, |-I, |-s, |-r > メッセージ配送システム = Mのマルチ集合(送られて，まだ到着していないメッセージ) 系全体: 多数のノードプログラム+配送システム

メッセージパッシングプログラムの表記法 ガード  コマンド | ガード  コマンド | … コマンド ::= … | send(p, M); | … ガード ::= … | received(パターン); | …

共有メモリ