今年読んだ面白CS論文紹介カレンダーの参加記事3日目です。ブログ的なものとか使ってなかったので Google+ あたりに直接書こうかと一瞬思ったのですが、やっぱり分量と構成のある記事は書きづらかったので、大昔にアドレスだけ取ってあったここに置いてみました。 根が OS 屋さんなのでそっち系で、同じ会社の人向けや vimpl で話したことがある SOSP 2011 からいくつかを紹介してみます。他の話題で紹介したいものもあったのですが間に合わなさそうなので、後日遅刻で追加するかもしれません ;) 1. SOSP 2011: 決定的マルチスレッド実行とか、競合 (race) 絡みの話OS 界隈ではここ数年、決定的マルチスレッド実行 (Deterministic Multi-threaded Execution) がやたら流行っているような気がします。彼らは「同じマルチスレッドプログラムに同じ入力を与えたら、同じように動作するようにする」ということがやりたい人たちで、プログラムや実行環境を「バグを発見しやすく」「デバッグしやすく」したい、というのが主なモチベーションになっているようです。 アプローチは、ものすごく大雑把に分けると 2 通りあります (私が知らないだけでここに当てはまらないのがあるかも?)
それぞれに特徴、一長一短があります。 (私見含む)
で、今回の SOSP ではこの両方のアプローチについて1件ずつ発表があったのでその2本と、競合絡みの論文をもう1本紹介します。 1-1. DTHREADS: Efficient Deterministic Multithreadingこれは決定的マルチスレッド実行の前者「ある特定のルールによって、固定されたスケジューリングをするように細工する」に分類される内容です。今の libpthread と同じインターフェースを持っているので g++ -lpthread ... を g++ -ldthread ... に変えるだけで、そのプログラムは常に決定的に実行されるようになるぜ! と言っています。 まずポイントは、この DTHREADS におけるスレッドは、実はスレッドではなくプロセスとして実装され、他のスレッド (実はプロセス; 以降略) から隔離されて実行されるという点です。普段は、各スレッドが完全に独立して並列に実行される並列フェーズ (parallel phase) で動作します。 (以降、単に「スレッド」と言ったらプロセスとして実装されている「DTHREADS におけるスレッド」を、単に「プロセス」と言ったら DHTREADS スレッドの集合 == 「DTHREADS におけるプロセス」を指すことにします) ちょい待て、データ共有できないんじゃスレッドじゃないやん。というわけで DTHREADS では一定のタイミングで全スレッドが逐次フェーズ (serial phase) に移行してデータの同期処理を行います。逐次フェーズでは、「そのプロセスが本来持つべきメモリ」を表す共有メモリ領域に各スレッドが特定の順序で commit し、全部の commit が完了したら再び並列フェーズに戻って、プロセスの実行を再開します。逐次フェーズに移行するきっかけは pthread_* 関係の同期に関わる操作です。具体的には thread creation & exit, mutex lock & unlock, condition variable wait & signal, POSIX sigwait & signal, barrier wait あたりです。これらの同期操作に入ると各スレッドはブロックし、全スレッドがこれらの操作のどれかを行うのを全スレッドが待って、逐次フェーズに入ります。 同期操作をすべて引っかけて、固定された順序でデータの commit を行うようにすれば、「実行ごとに実行結果が変わることはない」ことが保証されます。 commit のときに衝突があったら固定された順序で上書きされるので、少なくとも実行結果が実行ごとに変化することはないとわかります。 さて、ここで疑問を感じるのは以下の 3 点だと思います。
この疑問に回答する形で説明してみます。 っていうか commit するには変更された箇所を把握しなきゃダメだよね。どうやってんの?
それって pthread だった時にはありえなかった実行結果になったりしそうなんだけど...?
一度も同期命令を発行しないスレッドがいたらどうすんの? そいつのおかげで実行ストップしない?
最後にパフォーマンスについて。これは論文の Figure 4-6. あたりを見ていただくのがよさそうです。大雑把に言うと CoreDet [ASPLOS10] という既存研究よりは基本的に高速。 pthread に比べると、大抵ちょっと (最悪で4倍程度) 遅いんだけど、何故かやたら速くなるベンチマークがたまにある、というのが興味深いポイントです。 速くなる理由についても述べられていて、大雑把に言うと false sharing を除去できたことが主な理由のようです。ここでは詳細は省略します。 1-2. Efficient Deterministic Multithreading through Schedule RelaxationDTHREADS で頑張りすぎてしまったのでちょっと勢いを落とそう...。間に合わない。 [先延ばし屋08] この論文は、決定的マルチスレッド実行のもう片方「一回実行した時のスケジュールを記録しておいて、再生実行できるようにする」にあたる内容です。記録を取って同じスケジュールで再実行する、という手法は今までも割とありました。それらに対するこの論文の主な contribution は、適用対象を広く維持したままでパフォーマンスを向上させた点です。決定的マルチスレッド実行環境 PEREGRINE というものを実装しています。 スケジュールの再現をするための既存手法には、記録・再現のポイントが 2 通りありました。
この 2 つには明らかなトレードオフがあります。 (ちなみに先の DTHREADS は前者のようでありつつ copy-on-write と merge を使って無理やり後者の結果を実現している荒業と呼べると思います)
競合は大抵のプログラムにどこかしら含まれているので、せっかく速いのに Sync-schedule 使えないじゃんボケがー、というのが悲しいところでした。 さてこの競合、確かに大抵のプログラムに紛れ込んでいるのですが、プログラム中のどこもかしこもで競合している、ということは多くありません。っていうかそんなプログラムは、正直あまりメンテナンスしたくない。 あれ、それじゃ基本的には Sync-schedule でバリバリ実行して、競合してるとこだけ Mem-schedule で実行すれば結構速いんじゃね? というのがこの論文の趣旨です。 結果として Sync-schedule のみでは多くのベンチマークや実アプリケーションの決定的実行に失敗するのに対し Hybrid-schedule では全て決定的実行が可能 (論文 Table 2, 3) となりました。さらにオーバーヘッドを Sync-schedule とほとんど変わらないレベルに落として (同論文 Figure 11) います。 1-3. Pervasive Detection of Process Races in Deployed Systemsこれは決定的実行ではなく、競合の検出に関する論文です。競合と言って多くの人が考えるのはたいていスレッドなのですが、プロセス競合 (process race) というのを対象にしているあたりが面白いです。 プロセス競合?ps aux | grep pizza
のコマンドラインを実行して、その結果に 'grep pizza' 自体が含まれたり含まれなかったりする、という状況はおそらくほとんどの人が経験したことがあると思います。これは grep の実行開始が ps が /proc/.../cmdline を読むのに先んじれば grep が結果に含まれ、後になれば含まれない、という競合状態になります。 このような競合は、適切な同期無しに複数のプロセスが共有リソースにアクセスするだけで簡単に起こります。他プロセスとの競合は自プログラム内のスレッドの競合よりも気にされづらく、しかも既存の検出器では検出できないので、世の中に割とたくさん残っています。しかも割と大きな危険につながることが多いそうです。 プロセス競合の難しさとして、以下のような点があります。
このプロセス競合を一般的に検出する RACEPRO という検出器を作りましたよ、というのがこの論文です。既にデプロイされたシステムに対して適用できるのがポイントです。 この競合検出は、大きく分けると、カーネルレベル (kernel module) の実行レコーダー Scribe [SIGMETRICS10] による実行経過の記録 → 記録を解析して競合を検出 → 再生実行して検証、という 3 フェーズで実行されます。 Scribe の部分はそちらの論文を読みましょう、ということで、この論文の肝は検出と検証の部分です。 検出プロセス同士が干渉するのは、基本的にシステムコールを経由した入出力です。なので「システムコールの呼び出しログを取って、システムコールの入出力をいくつかの load / store 命令に分割・置換する。それから既存の (スレッド用の) 競合検出アルゴリズムを適用しちまえばいいんじゃね?」というアイデアです。 例えば open システムコールは以下のように置き換えられます。 (論文 Table 3. より引用)
ただし、シグナルと共有メモリアクセスはシステムコールと関係のない任意のタイミングで起こるので、システムコール同士の順番を考えるだけでは解決できません。 RACEPRO では、ログを記録する際にいくつかの工夫をしているようです。この辺りは論文にもスライドにもモヤっとしか書かれていないのですが、おそらくシグナルや共有メモリアクセスが微妙なタイミングで起こってしまう場合の検出精度を少し犠牲にして、実行時のパフォーマンスを稼いでいる感じです。 いちおう軽く紹介すると、シグナルについては、
ということをやっているようです。共有メモリの方は、
というようなことが書いてあります。 検証この検出方法で見つかった競合は、実は危険性の無いものかもしれません。たくさん見つかりすぎると困るので、危険性の無いものを自動的に捨てるための検証器が欲しい! というわけで、検証器も RACEPRO に含まれています。 ここで言う「危険性」とはだいぶ状況とユーザーにに依存した話で、例えば先の ps aux | grep pizza の例で言うと、ユーザーが打ったコマンドなら見ればわかるけど、スクリプトに食わせてたりすると致命的になりうるよね、というような話です。 さて、その検証手法ですが、大雑把に言うと、実行ログをちょっと書き換えて再実行する、という方法を用いています。 競合を起こしているかもしれないシステムコールの実行順序を入れ替える → 入れ替えたところまで決定的再実行 → そこからログを無視して赴くままに通常の実行を開始 → 何か変なことが起こったらお前が犯人じゃー! という判定をやっています。「お前が犯人じゃー!」の判定条件は RACEPRO 組み込みのものもありますが、先に挙げたとおり「危険性」の定義自体割と適当なので、判定条件をカスタムすることが可能なようです。 結果この検出器を使って実際に 10 個のバグを検出していて、うち 4 つは未発見だったバグ (tcsh, updatedb, abr2gbr) だそうです。 (論文 Table 4 参照) 記録にかかるオーバーヘッドは、論文中にはグラフがないのですが、スライドの最後から 5 ページ目にグラフがあります。 6 個のアプリケーションで実験して 0.8% 〜 14.6% のオーバーヘッドがかかっています。最も大きな 14.6% がかかったのは OpenOffice だそうです。他は 5% 前後のオーバーヘッドで収まっているようです。 2. SOSP 2011: ミーハーな話SIGGRAPH とか CHI とかと比べて地味な発表が多い OS 系とは言え、派手に演出してくれる発表もいくつかあります。論文紹介カレンダーなので発表ではなく論文の方に注目するのが筋な気がしますが、面白いのでかるーい感じで紹介してみます。 2-1. Cells: A Virtual Mobile Smartphone Architectureとりあえずこの動画の 22:30 〜 あたりから始まるデモを見てみてください。 みんな大好き Angry Birds 画質が荒くて何が起こっているかわからなかった方も多いかもしれませんが、「なんか Angry Birds が何回も始まったような」とか「ホーム画面の背景が途中で何度も変わらなかった?」とかいったあたりに気づいたのではないかと思います。 実はここでは、複数の Android 環境が Nexus S の実機上で仮想化されて切り替えられています。デモからわかる通り、ゲームもぬるぬる動きます。オーバーヘッドはほとんど感じさせません。 コンテナベース仮想化再び?ここで使われているのは FreeBSD jail や Linux VServer, OpenVZ のようなコンテナ型の仮想化技術です。 Jason Nieh 先生の研究室では昔から Zap [OSDI02] のようなコンテナ型の仮想化をやっていますので、その延長線上にあるのかなあ、という印象を受けました。 コンテナ型の仮想化とは、ざっくり言うと、カーネルの上に「色々な名前 (ID) を変換・多重化 (multiplex) するレイヤ」を作って名前空間を分けることで、他から隔離された仮想環境を作る技術です。ファイルシステムでは昔から chroot が使われていますが、それと同様の変換を pid やネットワーク、各種デバイスにも適用すると OS 環境全体を隔離することができます。 簡単な変換しかしないので、オーバーヘッドが非常に低いことが特徴です。その代わり、全仮想環境で同じカーネルしか使えない、隔離が完全ではない (特にスケジューリングとか) などの欠点もあります。前者の理由から、色々なバージョンの Android を試したい、という開発・実験用途には Cells は使えないことになります。 グラフィックスと電話 (SIM)スマートフォンで一番パフォーマンスが問題になりそうなグラフィックスについて詳しく説明されています。一つの仮想環境 (virtual phone; VP) がグラフィックスを常に占有するのは不便すぎるし、エミュレーションのレイヤを入れると遅くなりすぎる。ということで Cells はある時間にはある VP がグラフィックスを占有しつつ、適宜切り替えられるようにしています。具体的には MMU を使って VP ごとに書き込み先のフレームバッファを切り替える、という技です。表 (foreground) にいる VP のみが本物のフレームバッファに書き込み、他の VP は RAM 上に用意された偽フレームバッファに書き込みます。 電話については MMU のような便利な人がいない上に、通信会社と偽物の SIM で通信するわけにはいかないので、電話部分は VoIP をエミュレーションした偽 SIM を各 VP に見せる、という荒業をやっているそうです。 パフォーマンスパフォーマンスは論文 p.184 の Figure 3. を見ていただくのが手っ取り早いでしょう。メモリ、バッテリや I/O などは当然 VP の数に応じて負荷が上がっていますが、仮想化したこと自体によるオーバーヘッドがほとんど無いことがわかると思います。 2-2. Atlantis: Robust, Extensible Execution Environments for Web Applicationsとりあえず例だけ。 (論文 Figure 2.) <environment>
<compiler='http://a.com/compiler.syp'>
<markupParser='http://b.com/parser.js'>
<runtime='http://c.com/runtime.js'>
</environment>
たぶんこれが全てを語っている気がする。 一言で言うと「色んなブラウザあるけどみんなバグバグだし、動く部分もモノによって動作が微妙に違ったりしてめんどくせーから、もう JavaScript コンパイラとか HTML パーザとか DOM ツリーの内部実装とかレイアウトエンジンとかの定義は各ユーザ (各 Web ページ) にやらせちまおうぜ」という話です。 (長い) これだけ理解したら、あとはぜひ動画を見てください。私には彼の真似はできない。注意点として、この著者の人は Microsoft の人だ! ということは覚えておくとよいです ;) 予想通りパフォーマンスがあまり出ないのが少し残念ですね。これで速かったら超格好いいのですが。 (論文 Figure 4.) まとめもっとサラッと紹介して数で攻めるつもりだったのだが...と言うと @kinaba さんと同じ感じですが、微妙に書ききれてないあたりにガッカリ感が漂います (笑
とりあえず 1. の不足部分よりも先に、書きかけだった 2. ミーハー編を足してみました。 (Dec 18, 2011) 結局不足部分はほとんど足してない。というか意外と足すことなかった。 (Dec 31, 2011) おっと、次の人を書くのを忘れてた。次は @cocoatomo さんです! |
Note >
