分散コンピューティング / 同期

分散コンピューティング

クライアント・サーバ間通信（ブロック） †

　サーバはサービスを提供するプログラムであり，クライアントは資源を使うプログラム．

• サーバの指定方法
  
  • マシン名・プロセスID（ローカルID）による指定
    
    
  • プロセスを指定したブロードキャストによる方法
    
    
  • ネームサーバを使った検索による方法
    
    

ブロック通信 †

　クライアント・サーバ間のメッセージ送信時に同期を取るかどうか．

• ブロッキング（同期方式）
  

　　メッセージを送る間は，完全に送られるまでブロックされて次の命令は実行されない．

• ノンブロッキング（非同期方式）
  

• send with copy
  　カーネルのバッファにメッセージをコピーする方法．
  　コピーしてしまえば，またユーザプログラムに戻れる．（コピーのためのCPU処理が無駄）
  

• send with interrupt
  　送ったら，カーネルからユーザプログラムへすぐに戻るが，
  　完全にメッセージを送り終わったら割り込みをかけてユーザプログラムに知らせる．

バッファ通信 †

　クライアント・サーバ間のメッセージ送信時にバッファを取るかどうか．

• バッファ無し方式
  　サーバプロセスにメッセージを送るが，そのサーバプロセスが受信準備できていなければメッセージが失われてしまう．
  

• バッファ付き方式
  　サーバプロセス用のメールボックスにメッセージを送る．サーバプロセスは手が空いたときにメッセージを取り出す．
  

• メールボックスの管理が必要
  
• メールボックスの容量の設定（いっぱいになったらバッファ無しと同じになる）

信頼通信 †

　ベストエフォートのIPネットワークであるため，メッセージの損失に対する信頼性が問われる．

• 信頼性の無い通信
  　OSは信頼性の保証をしてくれない
  

• メッセージ毎の受領確認通信
  　相互プロセスのカーネル間において，受領確認が行われる．
  　（ブロッキング方式の送信時には，受領確認受信まではブロックしておく）
  

• 応答を受領確認の代わりとする通信
  　もともとクライアント・サーバ間通信においては，要求に対する応答があるので，受領確認が１つ省略できる．
  （ブロッキング方式の送信時は，同様に応答受信までブロックしておく）
  　応答に対してさらなる受領確認を返すかどうかはアプリケーションによる． 　

手続き呼び出し †

　プログラムの実行制御を，呼び出して実行する方法．関数呼び出しやサブルーチンコールとも呼ばれる．
　呼び出された処理が終わると，元のプログラムに戻る．

　リソースのアクセスを関数呼び出しとしてモデル化する．

RPC（Remote Procedure Call） †

　ローカルシステム上のプロセスによって，遠隔システムの手続きを呼び出す．
　遠隔にあるのに，ローカルで実行される手続き呼び出しのように見えるからProcedure Call（手続き呼び出し）．

LPC（Local Procedure Call） †

　呼び出す側と呼び出される側が同一マシンのとき
　 　呼び出す手続きで使う引数をどのように管理するかで３種類に分かれる．

• Call-by-value
  　引数の値をスタックにコピーしてから手続きに渡す．
  　だから呼ばれた手続きがいくら引数を変えようと，呼び出した側の変数には影響はない．
  

• Call-by-reference
  　引数の変数のメモリアドレスを（スタックにコピーして）渡す．
  　つまり呼ばれた手続きは直接　メモリアドレスの内容にアクセスするから，呼び出した側の変数にも影響がある．
  

• Call-by-copy/restore
  　引数の値をスタックにコピーして手続きに渡すが，手続き処理が終わると
  　更にもとの変数にコピーされる．だから呼び出した側にもしっかり影響が残る． 　
  

RPCでの手順 †

　クライアントとサーバ間で通信を行い，サーバ側の手続きにて実行され，その実行結果をクライアントへ返す手順．

• プロセス内の要素
  • 手続き（routine）
    　スタブと要求のやり取りをする．
    

• スタブ（stub）
  　遠隔にある手続きを呼び出すための引数を標準フォーマットにする（マーシャリング）
  　手続きを呼び出すメッセージを作る．
  　受信側のスタブは，標準フォーマットからシステムの内部表現に変換（アンマーシャリング）をする．
  

• カーネル（kernel） 　実際にネットワークを通してやり取りを行う．

• メッセージの引数
  　標準フォーマットの必要性．マシンが異なることによる相違
  • 文字コードの違い
  • 数値の表現方法の違い
  • クライアントとサーバで２回が必要
    　→ 相手のフォーマット情報を含めて送ることで，受信側での１回の変換で済む．
    

　Call-by-referenceの実現が難しい．参照する可能性のあるデータを遠隔ホストにコピーしてそれを参照しなくてはならない．

• 要求を受けた後のサーバ
  
  • RPC
    　クライアントは要求を送信した後，応答が返されるまで待つ．応答がないと待つのは無駄になる．
  • 非同期RPC
    　サーバは要求を受け付けるとすぐに受付メッセージを返す．
  • 一方向PRC
    　クライアントは要求を送ると応答を待たずに処理を続ける．

分散オブジェクトモデル †

　遠隔での実行を「オブジェクトのメソッド実行」としてモデル化する．
　つまり，あるマシンのオブジェクトが，他のマシンにサービスを提供するモデル．

• オブジェクト
  
  • 属性
    　データ
    

• メソッド
  　データにアクセスするための仕組み．（この集合体がインタフェース）
  

• オブジェクトの永続性
  • 一時的オブジェクト
    　そのオブジェクトを提供するサーバプロセスが存在するときだけ，存在するオブジェクト．
    

• 永続的オブジェクト
  　そのオブジェクトを提供するサーバプロセスが存在しないときでも，存在するオブジェクト．
  

• 遠隔メソッド実行
  　分散オブジェクトで，遠隔実行のためにしようするインタフェース（のメソッド）の選択で変わってくる．
  

• 静的起動
  　あらかじめ，仕様するインタフェースが分かっている場合．あらかじめクライアント側のスタブの中に必要なコードを埋め込んでおく．その中の特定のメソッドを呼べばよい．
  

  object_ref->method(parameters);

• 動的起動
  　使用するインタフェースが分かっていない場合．そのため，すべてのメソッドを呼ぶために，一般的な関数を呼び出す．
  

  invoke(object, method, input_parameters, output_parameters);

  パラメータの指定には，パラメータの「数，型，値」といった情報が含まれる．
  

• バインディング（Binding）
  　遠隔実行モデルにおける，仕様するサーバの指定方法．
  • 暗黙のバインディング
    　サーバは，RPCのプロシージャ名やインタフェース名をもとにして決まる．もし複数のサーバが該当しても，何らかの方法で１つのサーバが選ばれることになる．

• 明示的バインディング
  　サーバは，クライアントがbindという関数を自分で呼び出してサーバ情報を見つける．複数のサーバが該当すると，自分で１つのサーバを選ぶことが出来る．

ストリーム通信 †

　各メッセージが相互に依存しているメッセージの交換による通信．
　（ファイルのダウンロードや，音声・動画情報の通信）

• 非同期（Asynchronous）
  　データは１つのストリームとして順番に送信される．それ以外の時間的制限はない．
  

• 同期（Synchronous）
  　エンド・エンドの遅延に上限があり，しっかり同期を行う．
  

• 等時（Isochronous）
  　エンド・エンドの遅延に，上限と下限がある．
  

同期の問題 †

• シングルプロセッサシステムの同期問題
  　相互排他などの同期の問題は，セマフォやモニタを使って解決する．（共有メモリがあることに依存）

• セマフォ
  　オペレーション（P,V）だけでしか値を変更することができない保護された変数のこと．
  

  ・セマフォは，P()で-1，V()で+1される．
  ・Critical Section（相互排他が必要な区間）に入る前にP()を実行，出たときにV()を行．
  ・P()を実行しようとしたときに，セマフォが０だとおかしいので，P()は少し待たれる．
  ・V()を実行したときに，P()で待っているプロセスがあったときは，待ち状態を解除してあげる．

• モニタ
  　手続きとデータをひとまとめにした，特殊なモジュール． 　

  ・プロセスはモニタの手続きをいつでも呼べる．
  ・モニタ外の手続きからモニタ内のデータを直接操作することは出来ない．
  ・同時に１つのプロセスしか使うことが出来ない．（相互排他の保証）
  ・セマフォよりも抽象化レベルが高い． 

• コンピュータの時計
  　コンピュータのもつ時間を管理する回路．
  • 水晶振動子（一定の周波数で発振）
    
  • カウンタ
    
  • 保持レジスタ
    

・水晶振動子の１周期ごとに，カウンタの値を減らす．
・カウンタが０になったら割り込みを発生させる．
・割り込むと，またカウンタを元の値に再設定して戻す．（値は保持レジスタ）

　これにより，一定間隔で割り込みを発生させて，時計が出来る．

Lamportのクロック同期 †

　クロックが示す時刻を完全に合わせるんじゃんなくて，やり取りをするイベントの順序について意見を一致させることが大事だって事を示した．
　

• 論理時計
  　コンピュータの間で一致していればよくて，本当の時刻と合っている必要がない時計．
  

• 物理時計
  　本当の時刻とある一定のずれしか無いことを保証する必要がある時計． 　
• "happens-before"関係
  　イベントの順番を知るための方法．
  • 同一プロセス内で発生したイベントA，Bにおいて．

    ・AがBより以前に発生した場合，A->B．
    ・Aがメッセージを送るイベント，Bがそれを受け取るイベントなら，A->B．

• 異なるプロセスで発生したイベントX，Yにおいて．

  ・X->YもY->Xも成り立たない．X，Yは「同時」である．

• イベントAに対して，全てのプロセスが同意する時刻C(A)

  ・A->Bの場合，C(A)->C(B)でなくてはならない．
  ・Aがメッセージを送るイベント，Bがそれを受け取るイベントなら，C(A)->C(B)である．
  ・時計の値Cは常に進み続ける．（イベント間では必ず１つ進む）

クロック同期方法 †

Cristianのアルゴリズム †

　複数のマシンのうちから代表して１つのタイムサーバのクロックに，すべてのマシンが各自のクロックを合わせるやり方．（集中アルゴリズム）
　通信時間や，サーバ処理時間も考慮する．

Berkeleyアルゴリズム †

　代表のタイムサーバが，すべてのマシンに時刻を伝えてまわり，標準時刻に設定してく．（集中アルゴリズム）
　Berkeley UNIXで使われていた．

平均化アルゴリズム †

　各マシンは自分の時刻をブロードキャストする．

・各マシンは，一定期間に収集した到着時刻を平均した値でローカルクロックを再設定する．
・ブロードキャストするのは，再同期区間ごとに区切られた時刻ごとである．