分散コンピューティング / 制御

分散コンピューティング

相互排他（Mutual Exclusion）

　共有のデータ構造を他のプロセスが同時に使用しないことを保証する．

集中アルゴリズム

　複数のプロセスのうち，１つのプロセスが代表してコーディネータとなる．
　そして，各データにアクセスしているプロセスを管理する．

・あるデータにアクセスしているプロセスは「臨界領域（critical region）」に入れる．
・すでに臨界領域に入ろうとするプロセスがいたら，コーディネータは要求を待ち行列につなぐ．
・臨界領域に入っているプロセスがそこから出たら，排他制御からの開放をコーディネータに要求する．
・排他制御からの開放要求を受けると，待ち行列の最初の要求プロセスを臨界領域に入れる．

• 利点
  　・FCFS（First Come First Serve）であるので公平
  　・実装が簡単
  　・臨界領域に対して３つのメッセージのみで扱える 　　Request（要求），Grant（許可），Release（開放）
  

• 欠点
  　・コーディネータに障害が起きるとシステムがダウン
  　・臨界領域が埋まっているのか，コーディネータがダウンしているのか区別がつかない
  　・コーディネータの性能がパフォーマンスに影響（ボトルネック）

分散アルゴリズム

　RicartとAgrawalaによるアルゴリズム．データ構造を利用する全てのプロセスで，各データの臨界領域の制御をする．

・臨界領域に入ろうとすると，要求メッセージを全てのほかのプロセスに送る．
　　要求メッセージ（臨界領域の名前，プロセス番号，現在時刻）
・プロセスが要求メッセージに対し，そのデータの臨界領域の情報と比較して返信する．
・すでに臨界領域が埋まっていれば，待ち行列につなぐ．
・埋まってなくて，同じデータに対しての要求メッセージが複数ある場合は時刻によって制御する早い者勝ち
・要求元のプロセスは要求メッセージを送った後，すべてのプロセスからの応答を待つ．
・臨界領域から出たら，待ち行列にいるプロセスにOKメッセージを送る．

• 利点
  　・デッドロックやStarvation（優先度の低いプロセスがずっと待たされること）が起こらない．
  

• 欠点
  　・メッセージ数がすごく多い．（各プロセスに往復メッセージ）
  　・すべてのプロセスからの許可が必要なので，１つのプロセス障害がこわい
  　・分散アルゴリズムなのに，すべてのプロセスということから負荷が軽くなるわけじゃない．
  　

トークンリングアルゴリズム

　プロセスに順序をつけて，その付与された番号順に並べることにより仮想的なリングを作る．
　そして，そのリングの上を順々にトークン（権利）が受け渡されていくことにより，順番が回ってくる．

・リングを初期化したとき，プロセス０（番号０）にトークンが渡される
・トークンを持っているときだけ，臨界領域に入ることが出来る．
・臨界領域から出たときに，トークンを次のプロセスに渡す．
・トークンを受け取っても臨界領域に入る必要が無かったら次のプロセスに渡す．

• 利点
  　・Starvationが起こらない．（ちゃんと順番は回ってくる）
  

• 欠点
  　・トークンが無くなったら再発行しなくてはいけない．
  　・トークンがなくなった時に判断しづらい．（１周の時間の上限が分からない）
  　・プロセスがクラッシュすると，リングを作り直す必要がある．
  

選挙アルゴリズム

　複数のプロセスがあるときに，１つのプロセスに特別な役割（コーディネータなど）を割り当てる際のプロセスの選びかた．

　初めから，すべてのプロセスに個々の番号が割り当てられている（プロセス番号）
　このプロセス番号の１番大きい生きているプロセスを特定して指名する．

ガキ大将アルゴリズム

　どんどん強いやつに座を受け渡していくやり方．

・プロセスは自分より大きいプロセス番号を持つプロセスに選挙メッセージを送る．
・どんどん大きなプロセス番号にメッセージが受け渡される
・最終的な最大番号のプロセスが選ばれる

・コーディネータがいないことに，あるプロセスが気づいたところから始まる．
・選挙メッセージを受け取ったプロセスは，生きていたら確認のためOKメッセージを返す．
・選ばれたらそのプロセスは，すべてのプロセスに選ばれたことを知らせる．
・元のコーディネータが復帰した場合は，その元コーディネータがまた選挙を始める．

リングアルゴリズム

　プロセス間にすでにリングが張られていて，その順番を各プロセスは知っている．
　順々に選挙メッセージをリング上を受け渡ししていき，１周すれば全部のプロセスの番号が分かるので一番大きい番号が選べる．

・コーディネータが死んでいることに気づいたプロセスから開始．
・１周したら自分の番号があることにプロセスが気づいて１周したことを認知する．
・２周目はコーディネータメッセージに付け替えてもう１周させる．
・２周目によって，各プロセスはリング上の他のプロセスの番号を知ることが出来る．
・プロセスメッセージの中で一番大きい番号のプロセスが次のコーディネータになる．

アトミックトランザクション

　ひとまとまりの処理を，一括して扱うこと．（All or Nothing）　同期に関わる細かいところを意識することがなくなる．
　アプリケーションプログラマに使いやすい同期のための概念．

• トランザクションの開始
  

  ・１つのプロセスが，グループにする他のプロセスに対して宣言する．
  ・プロセス間で情報のやり取りをし，処理を行う．
  ・最初のプロセスは，それらのプロセスに対してコミット（処理の完了）をするように要求する．
  ・すべてのプロセスがコミットしたら，完成．
  ・１つでもプロセスがコミットしなかったら，すべてのマシンは開始する前の状態に戻される．

• バンキングシステムの例
  　お金を口座１から口座２に移すとき，

  ・引き出し（金額，口座番号１）
  ・預け入れ（金額，口座番号２）

  　の処理をするが，引き出しの時点で途切れたらお金がなくなってしまう．
  　　→ そこで，これらの２つの処理を，１つのアトミックトランザクションとする．

トランザクションの基本操作

• 前提

  ・システムは独立したプロセスからなっているが，そのプロセスはクラッシュする可能性がある．
  ・通信エラーは起こらない．（OSが再送したりして保証される）
  ・安定な記憶装置がある．（２つのディスクで常に更新・比較確認）

  

• 基本操作
  　OSあるいはプログラミング言語によって提供される．
  

  ・BEGIN_TRANSACTION：トランザクションの始まり
  ・END_TRANSACTION　：トランザクションの終わり（コミット）
  ・ABORT_TRANSACTION：トランザクション処理を中止，更新した情報は元に戻す
  ・READ　　　　　　 ：情報を読む
  ・WRITE　　　　　　：情報を更新する

  BEGINとENDに挟まれた部分がトランザクションとなる．

ACID

　トランザクションの４つの基本的な性質

• Atomic（アトミック）
  　トランザクションは１まとまりのものとする．分けられず，途中経過も見ることが出来ない．

• Consistent（一貫性）
  　システムにおける一貫性が，トランザクションの前後で保たれること．（Invariant：システムの不変性）
  

• Isolated（孤立性）
  　複数のトランザクションが同時に実行されたときは，結局順番に１つずつ実行した結果と同じであるということ．（Serializable：直列化可能，逐次処理可能性）　
  

• Durable（永続性）
  　一度トランザクションの処理が終わると，その結果はずっと残ること．障害が起こっても，無効になったり消えたりすることはない．
  

入れ子トランザクション

　トランザクションの中に，さらにサブトランザクションが含まれる．（ネストしたトランザクション）

・あるトランザクションが複数のサブトランザクションを並列して実行させる．
・１つのサブトランザクションが実行を完了しすると，その結果は親トランザクションが見られる．
・親トランザクションを中止すると，すべての状態が親トランザクションが始まる前まで戻る．
　（サブトランザクションがコミットした処理を元に戻す）
・各サブトランザクション毎に，すべての情報のプライベートなコピーを作っておけば実現できる．

実装

• 実装の条件
  • トランザクション内の処理は外部から見えない
  • 処理が完了したら見える
  • 処理が中止したらもとの状態に戻す

もとの状態に戻す方法

• プライベートワークスペース
  　各プロセスの開始時にもらうプライベートな作業環境．（アクセスするデータやファイルなどすべてのオブジェクトを含む）
  　しかし，プライベート環境に全てコピーするコストがかかる．
  • コストに対する解決法．

    ・読むだけのオブジェクトはコピーしない
    ・オブジェクトを更新するときだけにコピーする
    ・オブジェクトのインデックスだけをコピーする

  • オブジェクトを更新する方法
    

    ・オブジェクトのコピーを作る
    ・参照情報をインデックスに入れる
    ・そしてからオブジェクトの更新を行う

  • トランザクションが中止するとき
    　プライベートなオブジェクトのコピーとインデックスを破棄

• トランザクションがコミットするとき
  　親トランザクションのインデックスを，プライベートなインデックスで置き換える．

• 先書きログ（Writeahead Log）
  　トランザクションの更新の前に，安定な記憶装置にログを取る．このログが取れた後に，オブジェクトの更新を行う．
  
  • 更新ログの内容

    ・どのトランンザクションか
    ・どのオブジェクトか
    ・オブジェクトの新旧の値

• トランザクションがコミットしたとき
  

  ・ログに「コミット」が記録される
  ・オブジェクトはすでに更新済みとなっている

• トランザクションが中止のとき
  　最新のログからさかのぼりながらオブジェクトを元に戻す

• クラッシュからの回復のとき
  　再起動後，ログに書かれたオブジェクトの値とオブジェクト自体の値を比較．新しい方に

２相コミット

　完了(コミット)処理を，複数のプロセスで協力して行う方法．１つのプロセスが代表となってコーディネータとなり，他の従属プロセスとやり取りを行う．

・コーディネータはログに「準備」を書き込む
・他の従属プロセスに「準備」メッセージを送る
・すべての従属プロセスがそれに同意し応答する
・コーディネータは「完了(コミット)」をログに書き込む．
・他の従属プロセスに「完了」メッセージを送信し，処理を完了させる．

安全な記憶装置を使うことで，プロセスが死んでもちゃんと回復できる．

• 「準備」「コミット」ログを書いた後にコーディネータが死んだ場合
  　再起動後，それらのメッセージを送るところから再開
  

• 「準備完了」「コミット」ログを書いた後に従属プロセスが死んだ場合
  　再起動後，それらのメッセージを送るところから再開
  

並列処理制御

　異なるプロセスで，複数のトランザクションが同時に実行されているとき，うまく順序を制御してやるもの．トランザクションを１つずつ順番に実行するのと同じだという直列化可能性（serializability）を保証するメカニズム．

直列化可能性を保証する条件
・共有データを使う前にロックをかけ，使い終わったらロックを開放する．
・コンパティビリティ（相互性）規則に従って，ロックの制御が行われる．
・トランザクションは，１つでもロックを開放した後は新たにロックを要求しない．

ロックを使った並列処理

　あるプロセスがトランザクションの一部としてファイルの読み取りまたは書き込みを必要とするときに，初めにロックを行う方法．ロックされてるデータにアクセスするときは，待たされることになる．
　

• 制限の緩和
  　これで，他からのアクセスを排除するが，厳しすぎることから，「書き込みロック（write lock）」と「読み取りロック（read lock）」を分離することも可能．
  
  • 共有ロック
    　複数のプロセスでロックするモード．ロックされているデータは読み出しのみが可能．
    　データがロックされていないか，共有モードでロックされている場合にこのロックができる．
    

• 排他ロック
  　単一のプロセスでロックするモード．データの読み書きが共に可能．他からはデータは参照も変更も出来ない．
  　データがロックされていない場合のみ，このロックができる．
  

• ロックの単位
  　ロッキングの粒度（granularity of locking）が小さいほど精密で並列的な動作が達成できるが，多数のロックを必要とすることから，高価で，デッドロック（２つの処理で互いの処理終了を待つ状態になりプログラムが停止すること）を引き起こしやすい．
  

• ２相ロック
  　いっきに必要なプロセスにロックをするのではなく，徐々にロックする数を増やしていき（増加フェーズ），頂点（ロック点）に達したらロックを開放していく（現象フェーズ）やり方．

• 厳重２相ロック（Strict two-phase locking）
  　ロックを開放しているフェーズ中に，中止となり扱った所を元に戻さなきゃいけなくなる．
  　しかし，開放した所を既に他のトランザクションが見ていたとき，そのトランザクションも中止して，元に戻さなくてはいけないという問題．（cascading abort）
  　そのために，ロックを開放するときは，コミット後，すべてを開放するやり方

  ・BEGIN_TRANSACTION
  ・データの読み書きの前に該当するロックを取得する
  ・コミット
  ・すべてのロックを開放する
  ・END_TRANSACTION

いくつかの利点

・cascading abortが起こらない
・ロックの取得，開放をシステムでトランザクション実行の前後に自動的に行う．
　（トランザクションではロックを意識することはなくなる）

欠点 　２つのプロセスが２つの共有データを逆の順序で同時にロックしようとすると，デッドロックが起こる．

タイムスタンプを使った並列処理制御

　各トランザクションの開始（BEGIN_TRANSACTION）を実行したときにタイムスタンプを割り当てる方法．それぞれ異なるタイムスタンプを用いる必要がある（Lamportのアルゴリズム）

• タイムスタンプの種類
  • リードタイムスタンプ TRD(x)
    　最後に読まれたトランザクションのタイムスタンプ（Timestamp of Reading the Data）
    
  • ライトタイムスタンプ TWR(x)
    　最後に更新したトランザクションのタイムスタンプ（Timestamp of Writing Recently）
    

• 読み書きの条件
  タイムスタンプTを持つトランザクションがデータxを扱うとき
  • 読むとき
    　T≧TWR(x)ならば，データを読むことが出来る．
  • 更新するとき
    　T<TWR(x)であるかまたはT<TRD(x)ならば拒否される．そうでなければ更新することが出来る．

• 利点
  　デッドロックが起こり得ないこと．
• ロックの場合
  　トランザクションは待たされるか，実行し続けるかのどちらか
• タイムスタンプの場合
  　大きなタイムスタンプに出会うと，実行を中止させられる．

楽観的並行処理制御

　競合はまれにしか発生しないという仮定のもとに，常にトランザクションを最後まで実行させる．

• しくみ

  ・本物のデータにはまず更新処理をしないで，ローカルなコピーに対して行う．
  ・もし他のと競合していなかったら本物のデータに上書きする．
  ・競合してたら中止する．
  ・競合のチェックのために，使用したデータに関する情報を保持しておいて，比較する．

  　
• 特徴
  • 利点
    　待たせないので，最大限の並列実行が可能で，デッドロックも発生しない．
    

• 欠点
  　トランザクションの最後に競合してないかをチェックをするので，もし中止だとまた最初からやり直しになる．