Elixir試飲録 (7) – Erlangの軽量プロセスはどのように実現されているのか?

Elixir/Erlang の最重要コンセプトは「並行指向プログラミング」である、というのは既に書いた通りなのだが、この並行指向プログラミングを可能にする、いわゆる「軽量プロセス」がどのように実現されているのかという情報については、Erlang VM のソースコード以外にまとまった情報はなかなか無いようである。

The Erlang Runtime System』という書籍が来年発売予定らしいので、そこで体系的に解説される事になると思うが、とりあえず今回は筆者がWebで見つけた情報を簡単にまとめておきたいと思う。それぞれのコンセプトには分かる範囲で対応するソースコードへのリンクも貼っておいたので、興味のある方はそちらから詳細を追って頂ければと思う。

ちなみにこの情報の主な元ネタはredditに投稿された以下のコメントである。

 

Everything is a term

Erlangでは、全ての値が Term と呼ばれる固定長データ(32あるいは64bitの整数)の組み合わせで表現されている。

ソースコード上で見ると、Term は単にC言語の unsigned long 型へのエイリアスであることが分かる。

typedef unsigned long Eterm;

 
Term にはタグと呼ばれるメタ情報が含まれていて、そこを見れば Term に含まれるデータの種類が分かるようになっている。

term

ヒープやスタックといったデータ構造も内部的には Term の配列として実現されている。

 

A process is a C structure

軽量プロセスの正体は、process という名前の C の構造体である。

この構造体は以下のようなデータで構成されている。

  • ヒープ領域
  • スタック(Term の配列としてヒープ領域の末尾に配置されている
  • レジスタ(関数の引数)
  • インストラクション・ポインタ
  • メッセージ・キュー(受信したメッセージ本体はヒープ領域内にコピーされ、キューには本体へのポインタが格納される)
  • 親プロセスのPID

Erlangでプロセスを生成するとき、内部で行われているのは、メモリ領域を確保してこの構造体を初期化することと、その構造体へのポインタをスケジューリングのための実行キュー(Run Queue)に登録することだけである。そして、この時に必要なメモリ領域は、たったの 309 ワード(32ビット環境では1ワード4バイト)である。これが「Elixir/Erlangで一つのプロセスを作るのは一つのオブジェクトを作るのと同じぐらいの感覚」と言われる所以だ。

プロセスを生成するのに必要なメモリ 309 ワードの内、初期のヒープとして確保されている領域は 233 ワードである。このようにヒープの初期サイズを小さくしている理由は「Erlangのシステムが何十万、何百万というプロセス数をサポートをするために、極めて保守的に設定されているから」だと説明されている。

erlang-process-memory

 

Scheduler

Erlang が他の言語環境と比較して本当にユニークなのは、並行タスクを処理するプリエンプティブなスケジューリングシステムを、OSに頼るのではなくて、言語環境内に独自に持っているところである。

ここで言うスケジューリングとは、コンピュータ資源を複数のプロセスに割り当てる仕組みのことを言う。スケジューリングは OS などでマルチタスクを実現する際のコアとなる部品で、以下の二種類に分類される事が多い。

  1. プリエンプティブ(Preemptive)
    • スケジューラの側で資源の割り当てをコントロールする。制御を強制的に横取りするので「プリエンプション (preemption, 横取り) 」と呼ばれる。
  2. 協調的(Cooperative)
    • 各プロセスが資源の管理に責任を持つ。スケジューラの実装は楽だが、割り当ての公平性を保つのが難しく、素行の悪いプロセスがシステム全体を道連れにする恐れあり。

Erlang は、その出自上、高度なリアルタイム性と並行性が要求されていたので、より堅牢なマルチタスクを実現出来るプリエンプティブなスケジューリングを選択している。

Erlang におけるスケジューラは、内部的には一つのCPUコアに割り当てられた OS のスレッドである。そのスレッドの中でループ処理が走り、予め設定されたルールに基づいてプロセスを実行する。

scheduler

上図のように、スケジューラはキューからプロセスを一つ取り出し、インストラクション・ポインタが指している箇所から処理を再開させる。

プリエンプティブなスケジューリングで重要なのは、限られた資源をいかに公平に分配するかということである。Erlang では、計算コストに reduction という仮想の単位を導入してこの割り当てを行っている。例えば、一つの関数を呼び出すのは大体 1 reduction ぐらいのコストになる。プロセスには一度に消費出来る reduction 数の上限が設定されていて(バージョン R12B では 2000)、この上限に達する度に、スケジューラは実行するプロセスを切り替えて行く。

R11B より前の Erlang だと SMP(マルチコア)サポートがないために、Erlangランタイム全体で一つのスケジューラ(メインスレッド)しかなかったのだが、R11B 以降では、複数のスレッドを別々のCPUコアに割り当てることによって、複数のスケジューラが同時に動くようになった。

R11B から R13B にかけて、スケジューリングの仕組みは以下のように進化したようである。

1) 全体で一つのスケジューラ

scheduler

2) 複数のスケジューラが同じ実行キューを参照

scheduler2

3) 複数のスケジューラがそれぞれの実行キューを持つ

scheduler3

2) の方式だと一つの実行キューがボトルネックになってしまうということで、スケジューラごとにキューを持たせたのが 3) であるが、この方式でも複数のキューの間でサイズや負荷の偏りが出たらどうするのかという問題がある。今の Erlang ではこの偏りを均すために Migration Logic という仕組みを導入している。

一つ一つのスケジューラは、他のスケジューラを定期的にチェックして、自分より大きなサイズのキューを抱えているようだったら、そこからいくつか実行待ちのプロセスを自分のキューに移動してしまう。これが Migration Logic の仕組みである。

 

Message Passing

Erlang並行処理の要であるプロセス間のメッセージ送信はとてもシンプルな仕組みで実現されている。

  1. 名前あるいはPIDを指定して、送信先のプロセス構造体をレジストリから取得する
  2. プロセス構造体にあるメッセージ・キュー(mailboxと呼ばれる)をロックする
  3. 送信元プロセスのヒープ領域にあるメッセージ(Term)を送信先プロセスのヒープ領域にコピーする
  4. コピーしたメッセージへのポインタをメッセージ・キューに追加する
  5. メッセージ・キューのロックを解除する

もし、あるプロセスがメッセージ待ち(receive)状態になっているときは、新しいメッセージを受け取るまで実行キューから除外される。現実には多くのプロセスがこのメッセージ待ちの状態であることがほとんどである。つまり、この仕組みによって、何百万のプロセスを同時に立ち上げてもそれほどCPUを消費せずに済ませる事が出来るというわけだ。


[2016/09/29追記]

Erlang VM の仕組みについて、以下のような素晴らしいサイトが立ち上がっていた。


[2016/10/31追記]

Elixir/Erlang プロセスについての解説。コンパクトにまとまっていて分かりやすい。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中