高性能コンピューティング論Ⅰ ほんだ ひろき 本多 弘樹

Presentation on theme: "高性能コンピューティング論Ⅰ ほんだ ひろき 本多 弘樹"— Presentation transcript:

1 高性能コンピューティング論Ⅰ ほんだ ひろき 本多 弘樹
高性能コンピューティング論Ⅰ ほんだ ひろき 本多 弘樹

2 コンピュータシステムの並列化・分散化

3 並列・分散コンピュータシステム 並列・分散コンピュータシステム 「分散された多数のコンピュータ(プロセッサ)が， 相互通信網を用いて互いに密に通信し， 協調しながら並列に動作する」

4 集中と並列・分散 並列・分散の形態 機能並列・分散 業務並列・分散 地理的並列・分散 例)計算センター
　　計算専用マシンとグラフィックス専用マシン 　　研究用と事務用 　　センターと研究室

5 集中と並列・分散 並列・分散化の動機 処理性能 専用化による高性能化 並列処理による高性能化 処理の局所性による高性能化
処理性能 　　専用化による高性能化 　　並列処理による高性能化 　　処理の局所性による高性能化 拡張性(スケーラビリティ)の向上 耐故障性・信頼性・可用性の向上 etc.

6 並列・分散システムの性質 並行・並列性 拡張性 開放性　 耐故障性・信頼性・可用性 資源共有 透過性

7 並列・分散システムの性質：並行・並列性 並行・並列性 異なるジョブの同時処理 単一ジョブの分割同時処理

8 並列・分散システムの性質：並行・並列性 並行・並列性 異なるジョブの同時処理 単一ジョブの分割同時処理

9 並列・分散システムの性質：拡張性 拡張性（スケーラビリティ） システム規模拡大の容易性 ボトルネックやホットスポットを作らない

10 並列・分散システムの性質：開放性 開放性 既存機能の利用や機能追加の容易性 インターフェースの公開・標準化
開放性　 既存機能の利用や機能追加の容易性 　　インターフェースの公開・標準化 高い拡張性，マルチベンダ，インターオペラビリティ

11 並列・分散システムの性質：耐故障性 耐故障性・信頼性・可用性 ハードウェア冗長性 ソフトウェア回復性

12 並列・分散システムの性質：耐故障性 耐故障性・信頼性・可用性 ハードウェア冗長性 ソフトウェア回復性

13 並列・分散システムの性質：資源共有 資源共有
資源共有　 例：資源管理プロセス(サーバ)と資源利用プロセス(クライアント)の明確化 →　クライアント/サーバモデル サーバ サーバ クライアント クライアント

14 並列・分散システムの性質：透過性 透過性 シングルシステムイメージの提供 アクセス透過性 近くの対象と遠隔の対象を同じ操作でアクセス可能
位置透過性 対象物がどこに存在しているかを意識しなくてよい % cp /home/user1/file myfile % rcp remotehost:/home/user1/file myfile ネットワーク透過性

15 並列・分散システムの性質：透過性 透過性 並行透過性 操作を同時並行に行っても問題が起きない 複製透過性 情報などを複製しても問題が起きない

16 並列・分散システムの性質：透過性 透過性 故障透過性 故障が生じてもシステムが稼動し続ける 移動透過性 情報を移動させても影響を受けない

17 並列・分散システムの性質：透過性 透過性 故障透過性 故障が生じてもシステムが稼動し続ける 移動透過性 情報を移動させても影響を受けない

18 並列・分散システムの性質：透過性 透過性 性能透過性 性能向上のためにシステムの再構築が可能 規模透過性 システムの規模を簡単に拡張できる

19 並列・分散システムの課題 並列・分散システム構築の際の代表的な課題 高性能・高信頼な通信・同期 負荷の適切な分割・配置(負荷分散)
資源の位置透過な名前付け 大域的な名前から通信に必要な識別子への変換 ソフトウェア構造の開放性 一貫性の維持 資源の分散と処理の並行性により矛盾が生じないようにする

20 並列・分散システムの構成

21 並列・分散システムの種類 マルチプロセッサ(SMP)/マルチコアプロセッサ プロセッサを複数備えた(単体の)コンピュータ/チップ
バスやスイッチなど高速の結合網 単一のOS クラスタシステム(分散メモリマルチプロセッサ) LAN(Gbps)で結合されたコンピュータ群 個別のOS グリッド/クラウド WAN(インターネット)に接続された(地理的に離れた)コンピュータ群 ヘテロジニアスな環境

22 並列・分散システムの分類 主記憶(メインメモリ)の形態(メモリモデル) ＝プロセッサの結合形態から3つに分類 共有メモリ型 分散メモリ型
主記憶(メインメモリ)の形態(メモリモデル) 　＝プロセッサの結合形態から3つに分類 共有メモリ型 分散メモリ型 分散共有メモリ型

23 共有メモリ型 主記憶：単一 （シェアードメモリ） →全てのプロセッサが相互結合ネットワーク 経由で同一主記憶にアクセスする
主記憶：単一　（シェアードメモリ） 　　　　　→全てのプロセッサが相互結合ネットワーク 　　　　　 経由で同一主記憶にアクセスする SMP(Symmetrical Multi-Processor) 　　　(Shared Memory Multi-Processor) 密結合マルチプロセッサ UMA(Uniform Memory Access) マルチコアプロセッサ 主記憶ｱｸｾｽ遅延が一定 CPU CPU CPU CPU 相互結合ネットワーク 主記憶

24 共有メモリ型 通信時間：短い メモリモデル： (物理)単一アドレス空間 → プログラムしやすい
メモリモデル： (物理)単一アドレス空間 　　　　　　　　　→ プログラムしやすい 通信：メモリ書込み・読出しで実現 　　　　v.s. 「明示的」な通信 主記憶や相互結合網の混雑(ｱｸｾｽ競合） → スケーラビリティ：低い 　　プロセッサ数：数十程度 主記憶がCPUボードに 分散されている構成も CPU CPU CPU CPU store load 相互結合ネットワーク 主記憶

25 共有メモリ型 a(),sum0,sum1,sum2,sum CPU0: sum0=a(0)+a(1)+a(2);
レーシングが発生するため 実際には同期が必要 CPU CPU CPU CPU 相互結合ネットワーク a(),sum0,sum1,sum2,sum 主記憶

26 分散メモリ型 主記憶：各プロセッサに分散(ローカルメモリ) →他プロセッサから直接アクセス不可 入出力チャネルや通信ポートを介してアクセス
主記憶：各プロセッサに分散(ローカルメモリ) 　　　　　 →他プロセッサから直接アクセス不可 入出力チャネルや通信ポートを介してアクセス データ通信：相手プロセッサの介在が必要 データ分散の適切化(アクセスの局所性の利用) 　⇒主記憶アクセス競合の低減 高スケーラビリティ→大規模システム構築可能 Grid，PCクラスタ など 主記憶 主記憶 主記憶 主記憶 send receive CPU CPU CPU CPU 相互結合ネットワーク

27 分散メモリ型 通信：OSやミドルウェア，ライブラリ経由 通信：メッセージパッシングモデル →プログラミングが複雑
通信：メッセージパッシングモデル 　　　　→プログラミングが複雑 ソフトウェアで共有メモリ(仮想単一アドレス空間)を提供するアプローチもある ソフトウェア分散共有メモリ 主記憶 主記憶 主記憶 主記憶 CPU CPU CPU CPU 相互結合ネットワーク

28 分散メモリ型 CPU0: sum0=a(0)+a(1)+a(2); send(CPU2, sum0);
receive(CPU0,tmp0); receive(CPU1,tmp1); sum=tmp0+tmp1+sum2; 主記憶 主記憶 主記憶 主記憶 CPU CPU CPU CPU 相互結合ネットワーク

29 分散共有メモリ型 主記憶：各プロセッサに分散 →他プロセッサからもアクセスが可能 主記憶アクセス遅延：不均一(ﾛｰｶﾙv.s.ﾘﾓｰﾄ)
主記憶：各プロセッサに分散 　　　　　→他プロセッサからもアクセスが可能 主記憶アクセス遅延：不均一(ﾛｰｶﾙv.s.ﾘﾓｰﾄ) NUMA(Nonuniform Memory Access) ccNUMA(cache-coherent NUMA) 分散メモリ型との境は不明確 CPU CPU CPU CPU write 主記憶 主記憶 主記憶 主記憶 相互結合ネットワーク

30 分散共有メモリ型 高スケーラビリティ→大規模システム構築可能 ハードウェアによるリモートアドレス変換で単一アドレス空間を提供するものもある
CPU CPU CPU CPU 主記憶 主記憶 主記憶 主記憶 相互結合ネットワーク

31 分散共有メモリ型 CPU0: sum0=a(0)+a(1)+a(2); write(CPU2:tmp0,sum0);
sum=tmp0+tmp1+sum2; 実際には同期が必要 CPU CPU CPU CPU 主記憶 主記憶 主記憶 主記憶 相互結合ネットワーク

32 通信機構

33 通信機構 共有メモリによる通信機構 同一メモリロケーションへの同時アクセス： ハードウェアで排他制御
同一メモリロケーションへの同時アクセス： 　　ハードウェアで排他制御 同一プロセッサでのリード命令/ライト命令： 　記載された順序で実行されると仮定 　⇒メモリコンシステンシモデル　　

34 通信機構 メッセージパッシングによる通信機構 send/receive send: 送信データの格納場所と受信者の指定 receive
送信者と受信データの格納場所の指定

35 send/receive通信機構 send/receive機構 同期通信 blocking send blocking receive
送信側　　　　　受信側 send receive

36 send/receive通信機構 send/receive機構 同期通信 blocking send blocking receive
送信側　　　　　受信側 send receive

37 send/receive通信機構 send/receive機構 送信側システムバッファ有 同期通信
blocking send blocking receive send先行 送信側　　　　　受信側 send receive

38 send/receive通信機構 send/receive機構 送信側システムバッファ有 同期通信
blocking send blocking receive receive先行 送信側　　　　　受信側 send receive

39 send/receive通信機構 send/receive機構 送信側システムバッファ有 非同期通信
non-blocking send blocking receive send先行 送信側　　　　　受信側 send receive

40 send/receive通信機構 send/receive機構 送信側システムバッファ有 非同期通信
non-blocking send blocking receive receive先行 送信側　　　　　受信側 send receive

41 send/receive通信機構 send/receive機構 受信側システムバッファ有 非同期通信
non-blocking send non-blocking receive receive先行 送信側　　　　　受信側 send receive

42 メッセージパッシングの集団通信 集団通信： マルチキャスト ブロードキャスト v.s. ユニキャスト

43 メッセージパッシングの集団通信 アトミシティの保障 全受け手にメッセージが届くかもしくは全受け手にメッセージが届かないかのいずれかとなる
メッセージ到着順一貫性の保障 全受け手でのメッセージ到着順が同一となる

44 Remote Procedure Call 遠隔手続き呼出(RPC)
要求応答の手順を手続呼出として実装 　→データ抽象化とプログラム部品化が向上 クライアント/サーバ間通信の要求応答 クライアント：サーバに要求メッセージ送信 　　　　　　　応答メッセージを待つ サーバ：要求された操作を実行 　　　　応答メッセージを返送 サーバ上の手続きを遠隔呼出，戻り値を待つ 手続きを実行し戻り値を返送

45 RPCの機構 クライアントスタブ手続 クライアントでの手続呼出をサーバに対する遠隔手続呼出に変換 引数をメッセージに詰める(マーシャリング)
応答メッセージから結果を得る(ｱﾝﾏｰｼｬﾘﾝｸﾞ) サーバスタブ手続 遠隔呼出に対応する手続きを呼出す 引数のアンマーシャリング 戻り値のマーシャリング

46 RPCの機構 RPCの例 クライアントマシン サーバマシン クライアントプロセス サーバプロセス sum 2 5 sum 2 5
クライアントスタブ サーバスタブ sum sum 2 5 sum 2 5 n=sum(2,5) 7=2+5 n=7 7 7 7 カーネル カーネル

47 同期機構

48 同期 複数プログラム(プロセス)が「互いに密に通信し，協調しながら」動作し正しい結果を得る →プロセス間での実行順序の調整が必要 同期
条件同期 (point-to-point event) バリア同期 (global event) 相互排除 同期を実現する基本要素 許可の獲得 許可の譲渡 許可の獲得待ち (busy waiting vs. blocking)

49 条件同期 条件同期 他プロセスでの特定条件成立まで待つように制御 p0 p1 p0 p1 post(p1) wait(p0)

50 条件同期 フラグ変数のセットとテストでの単純な実現 (共有変数型) flag0=0; flag1=0;
フラグ変数のセットとテストでの単純な実現 　　　(共有変数型) 　　　　　flag0=0; flag1=0; CPU0: sum0=a(0)+a(1)+a(2); 　　　 flag0=1; CPU1: sum1=a(3)+a(4)+a(5); 　 　flag1=1; CPU2: sum2=a(6)+a(7)+a(8); 　　　 while(flag0==0) ; 　　　　　while(flag1==0) ; 　　　　　sum=sum0+sum1+sum2;

51 バリア同期 バリア同期 ある地点(バリアポイント)に全プロセスが到達するまで待つように制御 p0 p1 p2 p3 barrier

52 バリア同期 フラグ変数のセットとテストによる単純な実現 flag0=0; flag1=0; flag2=0;
CPU0: … 　　　flag0=1; 　while(flag0*flag1*flag2==0) ; CPU1: … flag1=1; 　while(flag0*flag1*flag2==0) ; CPU2: … 　flag2=1; 　while(flag0*flag1*flag2==0) ; 実際にはバリアを繰返す際の再初期化が必要

53 バリア同期 効率よいバリア同期の実現 フラグやカウンタによる単純な方法では変数アクセスが集中しボトルネックとなる 変数へのアクセスの分散化
コンバイニング・ツリー方式 トーナメント方式 ツリー方式

54 相互排除同期 相互排除(mutual exclusion)
複数プロセスが共有資源(変数/ハードウェア)にアクセスする際，同時アクセス可能なプロセス数を制御 クリティカルセクション：相互排除が必要となる処理

55 相互排除同期 相互排除(mutual exclusion) p0 p1 p2 Enter CS Enter Enter Exit CS

56 相互排除同期 相互排除(mutual exclusion) p0 p1 p2 Enter CS Enter Exit Enter CS

57 相互排除同期 相互排除(mutual exclusion) p0 p1 p2 Enter CS Enter Enter Exit CS

58 相互排除同期 相互排除(mutual exclusion) p0 p1 p2 Enter CS Enter Exit Enter CS

59 相互排除同期の必要性 CPU0: sum0=a(0)+a(1)+a(2); CPU1: sum1=a(3)+a(4)+a(5);
CPU2: sum2=a(6)+a(7)+a(8); 　　　sum=sum0+sum1+sum2; CPU0: sum0=a(0)+a(1)+a(2); 　　　sum=sum+sum0; CPU1: sum1=a(3)+a(4)+a(5); 　　　sum=sum+sum1; CPU2: sum2=a(6)+a(7)+a(8); 　　　sum=sum+sum2; 各プロセッサがsumを更新するよう変更 sumの更新は 相互排除して 行う必要がある (なぜか?)

60 相互排除の基本要件 安全性： クリティカルセクションに入れるプロセスはひとつだけ
活動性： クリティカルセクションに入ることを要求するプロセスはいずれその権利を得る 順序性 クリティカルセクションに入る順序は要求発行順序とする

61 lock/unlockによる相互排除の実現
lockの状態でなければlock状態とし次命令に移る さもなければlock状態解除まで待機 複数のプロセスが同時にlock命令発行場合 　ひとつのプロセスのみlockに成功 　他プロセスは lock状態解除まで待機 unlock命令： lock状態を解除する ロック変数(同期変数)と共にlock(v)/unlock(v)とする ∵複数のlock/unlockを区別するため

62 lock/unlockによる相互排除の実現
CPU0: sum0=a(0)+a(1)+a(2); lock(v); 　　 sum=sum+sum0; unlock(v); CPU1: sum1=a(3)+a(4)+a(5); lock(v); sum=sum+sum1; unlock(v); CPU2: sum2=a(6)+a(7)+a(8); lock(v); sum=sum+sum2; unlock(v);

63 ハードウェア同期機構による相互排除の実現
共有変数flagをロック変数としてlockを実現してみる flagを0に初期化 lock-loop: ld $r1, flag bne $r1,$zero,lock-loop st $one, flag クリティカルセクション unlock: st $zero, flag これでちゃんと動作する?

64 ハードウェア同期機構 lock-loop: ld $r1, flag bne $r1,$zero,lock-loop st $one, flag ldの実行後stの完了までに他プロセスがldを実行してしまう可能性 $r1 $r1 ld $r1, flag ld $r1, flag bne $r1, $zero,... bne $r1, $zero,... st $one, flag st $one, flag flag 1

65 ハードウェア同期機構 ldとstが不可分に実行されなければならない read-modify-write命令の必要性
lock-loop: ld $r1, flag 不可分命令 　　　　　　st $one, flag 　　　　　　bne $r1,$zero,lock-loop $r1 $r1 1 ld $r1, flag ld $r1, flag st $one, flag st $one, flag bne $r1, $zero,... bne $r1, $zero,... ld $r1, flag st $one, flag flag 1

66 ハードウェア同期機構 Test & Set Test & Set命令 　lock-loop: ts $r1, flag {$r1←flag; flag←1} 　　　　　　　bne $r1,$zero,lock-loop busy waiting busy waitingによるロックの実現：spin lock spin lockでは スピンしている間プロセッサは実行時間を浪費 相互結合網や共有メモリへのアクセスが増加 ts命令では毎回書き込みもある 対策 back off：tsの頻度を下げる test and Test&Set

67 ハードウェア同期機構 Test & Set サスペンドロック(suspend lock),ブロック lock獲得に失敗 → unlockされるまで実行を中断(スリープ)して待機 Test&Setから派生した命令 swap fetch&op fetch&increment fetch&decrement fetch&add compare&swap Load-Locked, Sotre-Conditional etc.

68 ハードウェア同期機構Compare & Swap
Compare & Swap命令 　cs $r1, $r2, flag {temp←flag; 　　　　　　　　　　　　if temp == $r1 then 　　　　　　　　　　　　{flag←$r2; $cc←1} 　　　　　　　　　　　　　　else 　　　　　　　　　　　　{$r1←temp; $cc←0}　} $r1 10 == temp 10 $r2 20 flag 20 10 $cc 1 cs $r1,$r2,flag

69 ハードウェア同期機構Compare & Swap
Compare & Swap命令 　cs $r1, $r2, flag {temp←flag; 　　　　　　　　　　　　if temp == $r1 then 　　　　　　　　　　　　{flag←$r2; $cc←1} 　　　　　　　　　　　　　　else 　　　　　　　　　　　　{$r1←temp; $cc←0}　} $r1 30 10 <> temp 10 $r2 20 flag 10 $cc cs $r1,$r2,flag メモリ書込がない

70 ハードウェア同期機構Compare & Swap
カウンタ更新の例 変数sumを複数のプロセスが更新 Test & Setで実現すると lock-loop: ts $r1, flag 　　　　　　bne $r1,$zero,lock-loop 　　　　　　 　　ld $r1, sum 　add $r2, $r1, $sum 　st $r2, sum st $zero, flag

71 ハードウェア同期機構Compare & Swap
カウンタ更新の例 Compare & Swapで実現 　　　 ld $r1, sum loop: add $r2, $r1, $sum0 　　　 cs $r1, $r2, sum 　　　 be $cc, $zero, loop Compare & Swap命令 　cs $r1, $r2, sum {temp←sum; 　　　　　　　　　　　　if temp == $r1 then 　　　　　　　　　　　　{sum←$r2; $cc←1} 　　　　　　　　　　　　　　else 　　　　　　　　　　　　{$r1←temp; $cc←0}　} ldの時のsumの値は そのままかな? そのままなら$r2を， 変更されてたら$r1を sumにストア

72 ハードウェア同期機構Compare & Swap
カウンタ更新の例 Compare & Swapで実現 　　　 ld $r1, sum loop: add $r2, $r1, $sum0 　　　 cs $r1, $r2, sum 　　　 be $cc, $zero, loop ldの時のsumの値は そのままかな? そのままなら$r2を、 変更されてたら$r1を sumにストア $r1 10 == temp 10 $r2 15 sum 15 10 $cc 1 $sum0 5 add $r2, $r1, $sum0 be $cc, $zero, loop cs $r1,$r2,sum ld $r1, sum メモリ書込は最後の一回だけ

73 ハードウェア同期機構Compare & Swap
カウンタ更新の例 Compare & Swapで実現 　　　 ld $r1, sum loop: add $r2, $r1, $sum0 　　　 cs $r1, $r2, sum 　　　 be $cc, $zero, loop ldの時のsumの値は そのままかな? そのままなら$r2をの値をsumにストア 変更されてたらsumの値を$r1にロード $r1 10 30 <> temp 30 $r2 35 15 sum 10 30 $cc $sum0 5 add $r2, $r1, $sum0 be $cc, $zero, loop cs $r1,$r2,sum ld $r1, sum

74 Load-Locked, Sotre-Conditional
カウンタ更新の例 LL & SCで実現 　　　　 loop: ll $r1, sum add $r1, $sum0 　　　sc $r1, sum 　　　bez $cc, loop sumにll以降書き込みはされてないかな? されてなければ$r1の値を、sumにストア($cc=1) されてたら($cc=0) lock-loop: ll $r1, flag bnez $r1, lock-loop sc $one, flag beq $cc, lock-loop unlock: st $zero, flag 無駄なストアを削減

75 理解度確認レポート 来週５月１９日（月） 各自A4レポート用紙を用意してください．

76 セマフォによる相互排除 lock/unlockに相当する二つの操作 P(s)操作/V(s)操作：sはセマフォ変数
T.H.E.オペレーティングシステム by ダイクストラで提案されたプロセス間同期機構 semaphore：のろしや腕木信号 P:オランダ語のpasseren(パスする)またはproberen(試す)とverlagen(減らす)の造語prolagenから V:verhogen(増加させる)あるいはvrygeven(開放する)から と言われている． [1]E.W. Dijkstra, Solution of a Problem in Concurrent Programming Control, Communications of the ACM, Vol.8, Sep. pp , 1965.

77 セマフォによる相互排除 P(s)操作 loop: if s>0 then s=s-1としてCSに入る; else goto loop;
V(s)操作 s=s+1としCSから出る; sは同時にCSに入れるプロセス数に初期化 sに対する操作自体も相互排除が必要

78 セマフォによる相互排除 サスペンドロックとする場合
P(s)操作 if s>0 then s=s-1; else このプロセスを休止状態にし, 　　　　　　 sに対応するキューに入れる； V(s)操作 if (sに対応するキューにプロセスがある)　 then プロセスのひとつを実行可能状態にする; 　　　　　 else s=s+1;

79 セマフォによる相互排除 P(s)操作/ V(s)操作 p0 p1 p2 P(s) s 1 P(s) queue p0 p2 p2 P(s)
1 P(s) queue p0 p2 p2 P(s) V(s) V(s) V(s)

80 セマフォによる相互排除 P(s)操作/ V(s)操作による条件同期 p0 生産者 p1 消費者 s 1 P(s) queue p1 V(s)
1 P(s) queue p1 V(s) V(s) P(s)

81 相互排除のオーバーヘッド ロックが空いている場合に低レイテンシでロックが獲得できるほうが望ましい
busy waitしている際にトラフィックを増やさないほうが望ましい ロックが解除されたらすぐに待っていたプロセスがロックを獲得できるほうが望ましい ロック獲得が公平であることが必要 クリティカルセクションはできるだけ小さくする

82 相互排除（共有メモリなし） サーバによる集中方式 合意による分散方式 トークンリング方式 相互排除での基本的な動作
クリティカルセクション(CS)に入りたいという要求発行 CSに入る許可を得る（与える） CSに入る CSから出る CSから出たことを通知する

83 相互排除：サーバによる集中方式 CSへ入る権利の要求の受付とCSへ入る許可の発行をサーバが一括管理
サーバが性能ボトルネックやsingle point of failureになる危険 要求キュー サーバ 4 4 3 1 4 3 2 2

84 相互排除：合意による分散方式 プロセス間で合意を形成しながら順次CSに入る CSへ入ろうとするプロセスPiの動作：
タイムスタンプTiを付加した要求メッセージ(Pi, Ti)を他の全プロセスに送信 他の全プロセスからOKが返送されるまで待ち，返送されたらCSに入る CSから出る際キューの全要求に対してOKを返送

85 相互排除：合意による分散方式 プロセスPjが要求メッセージを受信したした際の動作： CSの外であり入る要求もしていない： OKを返送
CSの外で入る要求をしている： Tj>TiならOKを返送，そうでないなら返事せず受信要求をキューに入れる

86 相互排除：合意による分散方式 プロセス間で合意を形成しながら順次CSに入る 動作例 １ 0/8 OK 0/8 0/8 OK 2/9 OK
OK 0/8 0/8 OK 2/9 OK 2/9 1 2 2 2/9 OK

87 相互排除：合意による分散方式 プロセス間で合意を形成しながら順次CSに入る 動作例 2 0/8 OK 0/8 0/8 2/12 OK OK
OK 0/8 0/8 2/12 OK OK 2/12 1 2 2 2/12 OK

88 相互排除：合意による分散方式 メッセージが多い，すべてのプロセスが関与しなくてはならないなどの理由からサーバによる一括管理と同程度の性能しか得られない 故障によって返事をしない場合にCS内にいるのと区別がつかない

89 相互排除：トークンリングによる分散方式 プロセス間にひとつのトークンを巡回させる CSに入るつもりがなければ次のプロセスにトークンをまわす
CSに入る要求があるプロセスはトークンが回ってきたときのみにトークンを保持したままCSに入る CSから出たらトークンを次のプロセスにまわす トークンを持ったまま故障した場合に検出できない CSに入ることが無くてもトークンを回さなくてはならない

90 選出 サーバなど特定の役割のプロセスが障害を起こした際に残ったプロセスから新たにサーバを選出する仕組み 前提：
各プロセスは一意のIDを持っている どのプロセスが稼動していてどのプロセスが障害を起こしているかは知らない 課題： 稼動しているプロセスの中でもっとも大きなIDを持つものを選出する

91 選出：ブリーアルゴリズム (bully) 各プロセスは他のプロセスのIDを知っているとする
サーバ障害を検知したプロセスは選出動作を行う： [選出動作] 自分より高いIDのプロセスに選出メッセージを送付し応答メッセージを待つ もし誰も応答しないならば自分がサーバとなり調整者メッセージをすべてのプロセスに送付する ひとつでも応答があれば調整者メッセージを待つ

92 選出：ブリーアルゴリズム 選出メッセージを受信したプロセス 応答メッセージを送付する 選出動作を行う 調整者メッセージを受信したプロセス
送信元を新たなサーバとする 2 1 4 選出メッセージ 5 応答メッセージ 応答メッセージ 選出メッセージ 6 6 7 3 調整者メッセージ

93 選出：リングアルゴリズム 各プロセスは他のプロセスのIDを知らない 全プロセスはメッセージを巡回させる順番を知っている
サーバ障害を検知したプロセス 選出メッセージに自IDを付加し下流のプロセス(無反応のプロセスはスキップ）に送付 戻ってきた選出メッセージよりID最大の物をサーバに選出し，選出済みメッセージとして再度巡回させる 選出メッセージを受信したプロセス 選出メッセージに自IDを付加し下流プロセスに送付 選出済みメッセージを受信したプロセス 選出されたサーバを知る

94 選出：リングアルゴリズム リングアルゴリズム 4 13 11 4 13 13 11 4 15 4 9 10 15 15 17 3
選出メッセージ 選出済みメッセージ 13 11 4 15 4 9 10 15 15 17 3

95 時計合わせ（同期） 共有メモリ無し＋共有時計無し 異なるコンピュータ上でのイベントAとBの生起の時刻や生起の順序関係を知ることも容易ではない
時計の「同期」(時刻あわせ)：一定精の度内で それぞれの時計は時刻がずれている 時刻の進むペースもずれている 外部同期：システム外部の時計(例：UTC)との同期 内部同期：システム内のマシンがお互いに同期 物理時計と論理時計

96 時計合わせ 物理時計を同期させる方式 クリスチャンのアルゴリズム(外部・内部同期) バークレイアルゴリズム（内部同期)
NTP(Network Time Protocol) クリスチャン(Cristian)のアルゴリズム マシンA マシンB 時刻要求 Ts t 時刻回答 t Tr 時計をt+(Tr-Ts)/2に設定

97 時計合わせ バークレイアルゴリズム（内部同期)
特定のコンピュータ(マスタ)が他のコンピュータ(スレーブ)の時刻を問い合わせ(クリスチャンの方法) 全コンピュータの時刻の平均値をスレーブに通達 NTP(Network Time Protocol) 広域ネットワークに時刻情報を配布する 木構造のサーバ間で互いに時刻合わせ マルチキャストモード，手続き呼出モード，対称モード

98 論理時計 論理時計 物理時計を完全に同期させるのは不可能 イベント間の順序関係さえわかればよい
　　⇒ 関連するイベント生起の順序づけを可能とする 先行生起(happened-before)の概念 同一プロセス内で生起した二つのイベント(a,b) 順序付け可能(a→b) プロセス間でのメッセージ通信イベント 送信イベント(a)は受信イベント(b)より先に生起(a→b) a→bかつb→cならばa→c

99 論理時計 Lamportの論理時計方式 先行生起順序を簡単な数値で表現
各プロセスは 　>論理時計(増加カウンタC)を持つ 　>イベント生起ごとにタイムスタンプ(C=C+1)を イベントに付与 メッセージ送信プロセス：送信イベントのタイプスタンプ(Tt)を付加して送信 メッセージ受信プロセス：C=max(C,Tt)+1を受信イベントのタイムスタンプとする 全イベントはタイムスタンプにより半順序関係を与えることができる

100 論理時計 Lamportの論理時計方式 P0 P1 P2 31 44 10 time X：共有変数 排他ｱｸｾｽ P0がﾎｰﾑ X++ 32
45 X/33 33 46 11 34 47 X++ 48 12 49 X/49 P1でのXの更新(49)より後に更新されたものであることがわかる 35 36 50 50 51 X++ X/52 52 53

101 理解度確認レポート 来週５月１９日（月） 各自A4レポート用紙を用意してください．