P2P 技術を応用した 分散システムの排他制御機構の試作 九州工業大学 情報科学センター 山之上 卓

はじめに P2P 技術を応用した排他制御アルゴリズム とその性質 教育支援システムへの応用と性能の実測 おわりに P2P 技術を応用した 分散システムの排他制御機構の試作

1. はじめに 分散システムの遠隔操作や共同作業 → 排他制御 過去の研究 – Lamport, Ricart and Agrawala, Suzuki and Kasami, Maekawa, … – Raymond, Agrawal and El Abbadi Tree, O(log n) のメッセージ → P2P と相性が良い – 辰本 他 LOTOS コンパイラで一箇所からのブロードキャスト – 山之上 他 P2P を使った教育支援システム P2P 技術を応用した 分散システムの排他制御機構の試作

Fischer のアルゴリズム repeat await ; ; until ; critical section; p:=0 p: 共有変数、 i: ノード 番号 P2P 技術を応用した 分散システムの排他制御機構の試作

共有メモリー p を使用 – → 分散システムには利用できない。 競合 (contention) が発生した場合、 O(n) の時 間 ↓ 分散システム用に改造 競合を抑制 (Balking pattern) P2P 技術を応用 (reliable multicast) O(log n) の時間で critical section 80 台のノードで計測 P2P 技術を応用した 分散システムの排他制御機構の試作

2. P2P 技術を応用した 排他制御アルゴリズムとその性質 2.1 ノード間の結合 ( データ構造 ) 2^(h-1) ≦ n ≦ 2^h -1 メッセージ伝播時間 O(log n) h P2P 技術を応用した 分散システムの排他制御機構の試作

2. P2P 技術を応用した 排他制御アルゴリズムとその性質 2.2 アルゴリズム 対称的ではない (Dijkstra の定義からはずれ る ) Fisher のアルゴリズムを使用 node 1 – p の値を全ノードに broadcast node 1 以外 – CS に入るとき、 node 番号を node 1 に送る。 – node 1 から p の値を受け取る P2P 技術を応用した 分散システムの排他制御機構の試作

node 1 integer p:0..n initialize p:=0; P2P 技術を応用した 分散システムの排他制御機構の試作

node 1 when this request the critical section, do if p=0 then begin p:=1; broadcast 1; critical section; p:=0; broadcast 0; /* release */ end od P2P 技術を応用した 分散システムの排他制御機構の試作

node 1 when this received x, do if x=0 or p=0 then begin p:=x; broadcast x; end /* otherwise, the node p is already being to enter the critical section */ od P2P 技術を応用した 分散システムの排他制御機構の試作

node i (2 ≦ i ≦ n) integer p:0..n initialize p:=0 P2P 技術を応用した 分散システムの排他制御機構の試作

node i (2 ≦ i ≦ n) when this request the critical section, do if p=0 then begin send i to node 1; end od P2P 技術を応用した 分散システムの排他制御機構の試作

node i (2 ≦ i ≦ n) when this received x, do p:=x; if p=i then begin critical section; send 0 to node 1; /* release */ end od P2P 技術を応用した 分散システムの排他制御機構の試作

2.3 critical section に入っているノード の数は高々 1 個であることの説明 初期状態 node の集合 S 0 (p=0) node 1 Critical section(CS) に入っているノード数 0 P2P 技術を応用した 分散システムの排他制御機構の試作

状態１, node x が CS を要求 S 0 (p=0) S 1 (p=x) node x node 1 node x が S 1 の要素になった時点で、 CS のノード 1 個。 他のノードは CS に入れない P2P 技術を応用した 分散システムの排他制御機構の試作

状態 2, node x が CS から離脱 S 0 (p=0) S 2 (p=0) node 1 S 1 (p=x) node x CS に入っているノード 0 個 P2P 技術を応用した 分散システムの排他制御機構の試作

状態３, node y が CS を要求 S 0 ∪ S 1 ∪ S 2 (p=0 or p=x) S 3 (p=y) node 1 node y node y が S 3 の要素になった時点で、 CS のノード 1 個。 他のノードは CS に入れない。この後は状態２へ P2P 技術を応用した 分散システムの排他制御機構の試作

2.4 critical section に入る時間 葉から根へ :O(log n) 根から全ノードへ : O(log n) → 最大 O(log n) CS から離脱する時も同じ P2P 技術を応用した 分散システムの排他制御機構の試作

2.5 競合 (contention) の抑制 node 1 が x (≠0) を broadcast して、 O(log n) 後、 p=0 のノードは 0 個 p が 0 でなければ、 CS を要求できない。 (Balking Pattern) 同時に cs の要求があった場合、木の節で交通 整理が行われ、少ない競合で node 1 に届く。 欠点 : 根に近いノードが有利。 starvation free ではない。 FCFS ではない。 – アプリケーションによっては大きな欠点ではない。 P2P 技術を応用した 分散システムの排他制御機構の試作

教育支援システム上の共同作業に応用 Draw, プログラミング環境, Web ブラウザな どのアプリケーションを共有 複数の学生、教師がリアルタイムで共同作業 3. 教育支援システムへの応用と性能の実 測 P2P 技術を応用した 分散システムの排他制御機構の試作

P2P 技術を応用した分散システムの排他制御機構の試作

競合の無い状態において、葉のノードが Critical Section に入る時間の実測値 ( 実線は平 均値 ) P2P 技術を応用した 分散システムの排他制御機構の試作

4. おわりに P2P 技術を応用した分散システムのための排 他制御機構 教育支援システムへの応用 80 台のノードで性能測定 80 台のノードまでは、スケーラブルな性能 現在はルーティングなし。 P2P 技術を応用した 分散システムの排他制御機構の試作

今後 – 競合のある状態での性能測定 – 虫取り, その他 researches/dsr/ researches/dsr/ P2P 技術を応用した 分散システムの排他制御機構の試作