この記事はGMOペパボ Advent Calendar 2018 12月16日の記事です。

OPERATING SYSTEM CONCEPTSを読んで面白かった章の一つ process synchronization についてちょっと深めてみました。

まずクリティカルセクションについてちょっと触れておく

クリティカルセクション(CS)は、その名の通り"危険な部分“で実態はコードの集まりです。プロセスはそれぞれCSを所有し、CSで作成したり更新したり色々なことをします。また、システムはCSに1つのプロセスのみが入るように制御しなければいけません。なぜなら、あるCSを共有する複数のプロセスが、そのCSに同時に入り、何かを作成したり更新したりすると、共有のデータに不整合が生じ、そのデータは破壊され、システムとして破綻をきたすためです。

以下、本題に入ります。

概要

分散システムのプロセス同期において、クリティカルセクションのMutual Exclusion(ME、相互排他)を実現するアルゴリズムの一つであるRicart-Agrawala’s(RA) Algorithmについてまとめます。

分散システムにおいてMEを満たすには以下の３つの基本的な手法があります。

  1. non-token-based approach
  2. token-based approach
  3. quorum-based approach

RA Algorithmは1に属するものですが、とりあえずそれぞれ軽く触れておきます。

  1. ノントークンベース手法：複数プロセスがメッセージ交換を行う。
  2. トークンベース手法：複数プロセスがトークンの授受を行う。
  3. コーラムベース手法：CSの占有権を求めるプロセスが、CSを実行するために他のプロセスの部分集合から許可を得る。わかりにくいですが、コーラムについてはこちらのQiitaの記事が大変参考になりました。最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった(またブロックチェーン界隈では、こんなのもあるようです。Quorum Advancing Blockchain Technology)

それぞれの手法によって、複数プロセスが相互に通信を行いCSの占有権の授受を行っています。

排他制御アルゴリズム色々

ノントークンベース手法において、RA AlgorithmはLamport’s Algorithmを修正したアルゴリズムです。また、Lodha-Kshemkalyani’s AlgorithmはそのRAを修正したものとなっています。他にもトークンベース手法においては、Raymond’s Algorithmやそれを修正したKanrar-Chiaki Algorithm、Suzuki-Kasami Algorithmなどがあり、コーラムベース手法ではMaekawa’s Algorithmなどがあります。こういったように系譜を少したどるだけでも有名な様々なアルゴリズムが存在することがわかります。

最近でもこれらのアルゴリズムを組み合わせたり、拡張することによっていくつかのアルゴリズムが論文で発表されています。最新のもので面白いものがあったのでそれについて書こうかと思っていたのですが、一般には有料の論文であったためここでは留めておきます(興味のある方は話しましょう!)。が、代わりに論文にあたっていた際に偶然ヒットしたこちらのスライド（大学図書館における電子ジャーナル契約の現状と課題 〜ビッグディールの光と影〜）がちょっと古いものですが、へーといった感じだったので紹介しておきます。

Ricart-Agrawala’s Algorithmについて

これは1981年に発表された古典的なアルゴリズムの一つで、以下内容をまとめます。

  1. あるプロセスPiがCSの占有権を求めるとします。この時、Piは他のすべてのプロセスに対して、< Ti, i>の形のリクエストをキャストします（マルチキャストを行う）。ここでTiはランポートの論理時計による現在のタイムスタンプを表しており、これは端的にいうとただの時刻です。分散システムでは共通の物理時計がないため、これがその代役を担います。時間を事象発生の前後関係に基づく因果律によって論理的に定義しています。こちらの資料分散アルゴリズム入門に設計・実装などが載っていました。
  2. Piは他のすべてのプロセスがこのリクエストに対してOKのレスポンスを返してくれるまで待ちます。すべてのOKの返事が集まれば、PiはCSを占有できるようになります。
  3. もし他のプロセスPj< Tj, j>(Tj>Ti)がCSを占有していたり、CSの占有権を要求していたとすると、< Ti, i>のリクエストはキューに入り自分に占有権が廻ってくるのを待ちます。

以上がそのロジックなのですが、言葉ではわかりにくいので、具体的にして今、{P1, P2, P3, P4, P5, P6}の6つのプロセスがあるとし、P2とP5がT2=13、T5=7でリクエストを送り、その時P3がCSにアクセスしている状況を考えます。

まず、P5はT5=7で、P2はT2=13で、すべてのプロセスに対してリクエストを送信します。 RAImage001

P1、P4、P6に関してはどれもすぐにOKの返事をします。これらはどれもCSを占有してはいないし、要求してもいないので。 RAImage002

残りのプロセスはCSを占有していたり、要求しているものなので、無思慮に処理は進みませんが、すべてランポートの論理時計によるタイムスタンプに従って処理されていきます。今回、T5< T2なのでP3へのリクエストにおいて、まずP5がキューに入ります。 RAImage003

P2とP5の通信においても、同様の理由でP5が優先され、P5のキューにP2が入ります。 RAImage004

これでP3のリリースメッセージを受け取ると、キューによりまずP5がCSを占有し、 RAImage005

P5のリリースメッセージを受けるとP2がCSを占有します。 RAImage006

これでRAではMEが達成でき、プロセスのCS占有権リクエストはレスポンスやキューに入るなど、どんな形であれ処理されるので、リクエスト元クライアントの同期遅延は O(1)のオーダーとかなり小さくなるのですが、一方、リクエストはマルチキャストを伴っており、さらに言うと、CS開放の際のリリースメッセージも実はマルチキャストを伴っていたりするので、そのデータ通信量（Bandwidth??）は O(n)のオーダーに膨らみ、nが増えればかなりつらいことになります。一長一短ですね。アルゴリズムの比較系の論文はたくさんあるので（比較指標がほぼ決まっているので書きやすいのかもしれません）、単純な頭の体操が好きな人は暇な時に調べてみるとちょっと幸せになるかもしれません。ex/A Comparative Study of Ricart-Agrawala and Maekawa Distributed Mutual Exclusion Algorithm

コードがないのも味気ないのですが、興味がある方は他をあたってくださいmm ロジックとしては単純ですが、実装は大変です。（僕が調べた限りでは、Java, C, C++, Pythonで実装されたものが見つかりました ex/ Write a C program to implement Ricart-Agrawala algorithm for distributed mutual exclusion - Distributed Computing Assignment - BITS -WILP）。

最後に

僕はプログラミングにおいて形にすることから入りましたが、それは私服で山登りを始めたようなものでした。それでは山登りはできてもせいぜい高尾山とか飯野山くらいで、直ぐ頭打ちになってしまいます。浅い技術の習得が目的化し、プログラミングという行為自体が形骸化していきます。そんな状況を打開すべくCSに関する理論書を漁りはじめ、最初に読んだのがこれだったのですが、まさに効果覿面でした。例えば、言語に対する理解も深まり、的外れの見当が減りデバッグの質が向上するなど、日々のプログラミングにおける様々な局面で良好な変化が起こりました。長い本なので僕のようにある程度の強度で全ページを読むなどと勧めるのはミスリードだと思いますが、僕はOSについて理解したい非理情のエンジニアがいれば、 computing の世界に入る何らかのきっかけには必ずなると思うのでこのOPERATING SYSTEM CONCEPTSをおすすめします。

以下駄文

目の前の大木を見てその山の概形をつかむのが難しいように、数行のコードからそれを支える分野を把握するのは普通の人には不可能だ。実際何らかの理論書を読んだところで目に見える変化はないし、やる意義を問われればないときっぱりないと答えると思う。当人は森の一端を垣間みたことで、何か想像以上に大きなものに触れてしまったように感じ、それ以上奥に進むのを躊躇してしまうかもしれない。しかし、呑気な学習者とは愚かなもので、ひと度そんなよくわからないものに触れてしまうと、好奇心の赴くままに突き進もうとしてしまうものだ。学生時代くらいそんな遊びとも言える、一見無駄な活動に時間を使ってもいいだろう。

かなり厳しいだろうが、まだなんとかなる。一度は森を感じてみたい。

明日の担当は@tsumichanさんです、お願いいたします。