12月16日の記事です。ついてちょっと深めてみました。まずクリティカルセクションについてちょっと触れておくクリティカルセクション(CS)は、その名の通り”危険な部分“で実態はコードの集まりです。プロセスはそれぞれCSを所有し、CSで作成したり更新したり色々なことをします。システムはCSに1つのプロセスのみが入るように制御しなければいけません。あるCSを共有する複数のプロセスが、そのCSに同時に入り、何かを作成したり更新したりすると、共有のデータに不整合が生じ、そのデータは破壊され、システムとして破綻をきたすためです。以下、本題に入ります。Algorithmについてまとめます。分散システムにおいてMEを満たすには以下の3つの基本的な手法があります。Algorithmは1に属するものですが、とりあえずそれぞれ軽く触れておきます。ノントークンベース手法:複数プロセスがメッセージ交換を行う。トークンベース手法:複数プロセスがトークンの授受を行う。コーラムベース手法:CSの占有権を求めるプロセスが、CSを実行するために他のプロセスの部分集合から許可を得る。わかりにくいですが、コーラムについてはこちらのQiitaの記事が大変参考になりました。最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった(またブロックチェーン界隈では、こんなのもあるようです。Technology)それぞれの手法によって、複数プロセスが相互に通信を行いCSの占有権の授受を行っています。Algorithmを修正したアルゴリズムです。AlgorithmはそのRAを修正したものとなっています。Algorithmなどがあります。いったように系譜を少したどるだけでも有名な様々なアルゴリズムが存在することがわかります。最近でもこれらのアルゴリズムを組み合わせたり、拡張することによっていくつかのアルゴリズムが論文で発表されています。最新のもので面白いものがあったのでそれについて書こうかと思っていたのですが、一般には有料の論文であったためここでは留めておきます(興味のある方は話しましょう!)。〜ビッグディールの光と影〜)がちょっと古いものですが、へーといった感じだったので紹介しておきます。Algorithmについてこれは1981年に発表された古典的なアルゴリズムの一つで、以下内容をまとめます。あるプロセスPiがCSの占有権を求めるとします。i>の形のリクエストをキャストします(マルチキャストを行う)。ここでTiはランポートの論理時計による現在のタイムスタンプを表しており、これは端的にいうとただの時刻です。分散システムでは共通の物理時計がないため、これがその代役を担います。時間を事象発生の前後関係に基づく因果律によって論理的に定義しています。こちらの資料分散アルゴリズム入門に設計・実装などが載っていました。Piは他のすべてのプロセスがこのリクエストに対してOKのレスポンスを返してくれるまで待ちます。すべてのOKの返事が集まれば、PiはCSを占有できるようになります。i>のリクエストはキューに入り自分に占有権が廻ってくるのを待ちます。P6}の6つのプロセスがあるとし、P2とP5がT2=13、T5=7でリクエストを送り、その時P3がCSにアクセスしている状況を考えます。P5はT5=7で、P2はT2=13で、すべてのプロセスに対してリクエストを送信します。P1、P4、P6に関してはどれもすぐにOKの返事をします。これらはどれもCSを占有してはいないし、要求してもいないので。残りのプロセスはCSを占有していたり、要求しているものなので、無思慮に処理は進みませんが、すべてランポートの論理時計によるタイムスタンプに従って処理されていきます。T2なのでP3へのリクエストにおいて、まずP5がキューに入ります。P2とP5の通信においても、同様の理由でP5が優先され、P5のキューにP2が入ります。P5のリリースメッセージを受けるとP2がCSを占有します。O(n)のオーダーに膨らみ、nが増えればかなりつらいことになります。アルゴリズムの比較系の論文はたくさんあるので(比較指標がほぼ決まっているので書きやすいのかもしれません)、単純な頭の体操が好きな人は暇な時に調べてみるとちょっと幸せになるかもしれません。ロジックとしては単純ですが、実装は大変です。最後に僕はプログラミングにおいて形にすることから入りましたが、それは私服で山登りを始めたようなものでした。それでは山登りはできてもせいぜい高尾山とか飯野山くらいで、直ぐ頭打ちになってしまいます。浅い技術の習得が目的化し、プログラミングという行為自体が形骸化していきます。そんな状況を打開すべくCSに関する理論書を漁りはじめ、最初に読んだのがこれだったのですが、まさに効果覿面でした。言語に対する理解も深まり、的外れの見当が減りデバッグの質が向上するなど、日々のプログラミングにおける様々な局面で良好な変化が起こりました。CONCEPTSをおすすめします。目の前の大木を見てその山の概形をつかむのが難しいように、数行のコードからそれを支える分野を把握するのは普通の人には不可能だ。実際何らかの理論書を読んだところで目に見える変化はないし、やる意義を問われればないときっぱりないと答えると思う。当人は森の一端を垣間みたことで、何か想像以上に大きなものに触れてしまったように感じ、それ以上奥に進むのを躊躇してしまうかもしれない。呑気な学習者とは愚かなもので、ひと度そんなよくわからないものに触れてしまうと、好奇心の赴くままに突き進もうとしてしまうものだ。学生時代くらいそんな遊びとも言える、一見無駄な活動に時間を使ってもいいだろう。厳しいだろうが、まだなんとかなる。一度は森を感じてみたい。明日の担当は@tsumichanさんです、お願いいたします。12月16日の記事です。ついてちょっと深めてみました。クリティカルセクション(CS)は、その名の通り”危険な部分“で実態はコードの集まりです。プロセスはそれぞれCSを所有し、CSで作成したり更新したり色々なことをします。システムはCSに1つのプロセスのみが入るように制御しなければいけません。あるCSを共有する複数のプロセスが、そのCSに同時に入り、何かを作成したり更新したりすると、共有のデータに不整合が生じ、そのデータは破壊され、システムとして破綻をきたすためです。以下、本題に入ります。Algorithmについてまとめます。分散システムにおいてMEを満たすには以下の3つの基本的な手法があります。Algorithmは1に属するものですが、とりあえずそれぞれ軽く触れておきます。ノントークンベース手法:複数プロセスがメッセージ交換を行う。トークンベース手法:複数プロセスがトークンの授受を行う。コーラムベース手法:CSの占有権を求めるプロセスが、CSを実行するために他のプロセスの部分集合から許可を得る。わかりにくいですが、コーラムについてはこちらのQiitaの記事が大変参考になりました。最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった(またブロックチェーン界隈では、こんなのもあるようです。それぞれの手法によって、複数プロセスが相互に通信を行いCSの占有権の授受を行っています。Algorithmを修正したアルゴリズムです。AlgorithmはそのRAを修正したものとなっています。Algorithmなどがあります。いったように系譜を少したどるだけでも有名な様々なアルゴリズムが存在することがわかります。最近でもこれらのアルゴリズムを組み合わせたり、拡張することによっていくつかのアルゴリズムが論文で発表されています。最新のもので面白いものがあったのでそれについて書こうかと思っていたのですが、一般には有料の論文であったためここでは留めておきます(興味のある方は話しましょう!)。〜ビッグディールの光と影〜)がちょっと古いものですが、へーといった感じだったので紹介しておきます。これは1981年に発表された古典的なアルゴリズムの一つで、以下内容をまとめます。あるプロセスPiがCSの占有権を求めるとします。i>の形のリクエストをキャストします(マルチキャストを行う)。ここでTiはランポートの論理時計による現在のタイムスタンプを表しており、これは端的にいうとただの時刻です。分散システムでは共通の物理時計がないため、これがその代役を担います。時間を事象発生の前後関係に基づく因果律によって論理的に定義しています。こちらの資料分散アルゴリズム入門に設計・実装などが載っていました。Piは他のすべてのプロセスがこのリクエストに対してOKのレスポンスを返してくれるまで待ちます。すべてのOKの返事が集まれば、PiはCSを占有できるようになります。i>のリクエストはキューに入り自分に占有権が廻ってくるのを待ちます。P6}の6つのプロセスがあるとし、P2とP5がT2=13、T5=7でリクエストを送り、その時P3がCSにアクセスしている状況を考えます。