2000万個のプロセスを動かすための並列モデル

# タイトルは煽りです.

今週末ドリコムさんでCometとその周辺技術（イベント処理、Erlangなどなど）に関する勉強会が行われるので,ここ最近つらつら考えたり調べたりしてたことを外に出します.yamazはErlangの文法とかにはあまり興味がなく,2000万のプロセスが並列実行できるというそのモデルに興味があるので,とりあえずそこについて.

なおいつもにも増して適当なこと書いてるので,適宜マユツバでお願いします.ツッコミ大歓迎.

Erlangは1マシンで2000万のプロセスを並列実行させることができるらしい.

http://www.atmarkit.co.jp/news/200704/27/erlang.html

私は並列言語はVHDLしか使ったことがなく,しかもVHDLはちゃんと
並列実行を行う要素が回路の形で実在するので,Erlangみたいに
1マシンで並列性を実現することに対してピンときてなかった.

その後daifuku Chatさんと上記記事について話してて,ある知見を得るにいたったので,忘れないうちにメモ代わりに書いておく.
ちゃんとしたことはそのうち書くかも.

1. プロセスを並列に扱うにあたってUnixでいうところのプロセスやスレッドモデルを使う必要はない.

2. プロセスやスレッドは並列に実行してるように見せかけるための仕組みであるが,コンテキストスイッチのコストが異様に高いのが欠点.

3. 数万を超えるようなオブジェクトの並列実行をエミュレートする仕組みとしては例えばシミュレータがある.例えばシューティングゲームは広義のシミュレータといえるが,敵機や弾の一つ一つをスレッドとかプロセスとかにしてたらOSが死んでしまうので,内部的にはデルタ時間で動作するシミュレータのような実装になっている.

4. シミュレータの実装はいろいろあるけど大体はこんな感じ.
4-1 並列実行させたいオブジェクトを動かしたい数だけ作成し,各オブジェクトが動作する時間順にスケジュールキューに入れる
4-2 スケジュールキューの一番先頭からスケジュールを取り出してオブジェクトをデルタ時間だけ動作させる.
4-3 動作が完了したら次の動作を行う時間を計算してスケジュールキューの適切な場所に挿入する.
4-4 4-2に戻る.

5. 上記はセルオートマトンのように各オブジェクトの動作がデルタ時間に固定されているときだけ有効で,IO待ちなど非同期動作が絡むようなケースは考慮されてなさそう.

6. なので非同期動作に関してはイベント駆動でスケジューラにさらに新たなスケジュールを積むようなモデルだとうまくいくかもしれない.ただ非同期動作はほんとの実時間で発生するのに対し,スケジューラ上での動作は仮想的な時間経過なので,スケジューラに積むというのが正しい方策なのかはよくわからない.

7. 上記のことは結局のところプロセスやスレッドのようにTSSベースでコンテキスト切り替えが強制的に発生するモデルと違い,コンテキスト切り替えが必要な数しかおきない&次のコンテキスト切り替えのタイミングまで待つ必要が無い分速い気がするけど,もうちょっと考える必要がありそう.

8. あとこのモデルだとOS的なプロセスは1個だけあればいいので,その点でも速いと思われる.

2000万個のプロセスが常に何かをしてるのではなく,なにかのイベントをひたすら待つような場合,このモデルは特に有効になる可能性がある.

スケジューラに積んでいくスケジュールデータというのは結局の所実際に実行しなくてはならないイベントなりなわけなので,Erlangのように関数型(=状態を持たない)であることが前提であるならIOの終了イベントなども到着順などを考慮せず,適当(適切?)にスケジューラに積むことによって実時間とのずれみたいなのは考慮しなくていいのかもしれない.

ゲームプログラミング業界ではこのあたりの話は「タスクシステム」という名前でいろいろな実装が行われている様子.

とりあえずリンクだけ.

White Paper - Programming

http://homepage3.nifty.com/moha/programming.html

タスクシステム

http://www5f.biglobe.ne.jp/~kenmo/program/task/task.html

CodeZine：本格的なシューティングゲームを実現するタスクシステム（タスクシステム，シューティング，ゲーム）

http://codezine.jp/a/article.aspx?aid=297

ゲーム・ノ・シクミ 第11回 C++によるタスクシステムの実現

今は無き C MAGAZINE 2006年1月号
http://www.cmagazine.jp/contents/200601.html

2ch タスクシステム総合スレ

http://pc11.2ch.net/test/read.cgi/gamedev/1173708588/

「タスクシステム」という単語は定義が曖昧でゲーム業界の中では一人歩きをしている印象.

サテオキ関係ありそうなURL
http://www.watch.impress.co.jp/game/docs/20070131/3dlp.htm

2chのスレを読んだ限りだと,「タスクシステム」と呼ばれるものの実装には下記のような問題がある様子.

1. タスクを格納するコンテナの実装方法
　1-1 優先度問題
　1-2 親子関係のタスクなどの特殊関係にあるタスク同士の問題
2. タスク自体のデータ構造問題
　2-1 いろんな形態のタスクを透過的に実行させる方法
　2-2 いろんな形態のタスクの状態管理をどうするか(タスク同士の相互作用とか)
3. タスクデータのメモリ管理問題(いちいちその場でメモリ確保か事前にメモリ確保か,GCを行う際の世代問題とか).
4. Blockingが発生するようなタスクの取り扱い方法
5. 割り込みとか
6. タスク全体の統括方法

これらはOSのスケジューラの実装とかで研究されている問題とほとんど同じものと思われる.

OSのスケジューラの場合,プロセスがそのコンピュータの全リソースを使えるようにするというモデルが主流のようなので,タスクの切り替え時にはレジスタ情報の退避などの処理が発生する.

ただタスクシステムは結局のところプロセス内での「俺スケジューラ」なのでいろいろはしょれる分速いとかそんな感じ.

なので本当に汎用的なシステムにしようとしたらOSのスケジューラに近づくしかない(そして遅くなる)ので,いろいろ割り切った話をしないとだめなのにそういう話に持っていこうとするとその部分をたたかれたりして話題が発散したりしなかったりしてる感じ.

また2ch内で盛り上がるオブジェクト指向とかデザインパターンとかの話は概ね上記の1とか2の問題をどうスマートに解決するか,つまりタスクシステムを便利に柔軟に使うための実装の問題なので,切り分けて考える必要がありそう.

(つづく..かも)

あわせて読みたい

http://research.microsoft.com/~simonpj/papers/stm/stm.pdf
http://www.ce-lab.net/ringo/archives/2007/05/08/#000839
http://www.ce-lab.net/ringo/events_robust.html
http://www.spa.is.uec.ac.jp/~kinuko/survey/body/events-are-bad.html

組込みマルチタスクプログラミング実践講座

2chに載っていた本.まだ読んでないので,書評は避けます.

シミュレーションによるコンピュータ・システムの性能評価―テクニックとツール

yamazが勉強したシミュレータ実装の本.今はもっといいのがあるのかも知れないけど,コレを読めば基本的なシミュレータは実装できるようになる.けど絶版...