Note‎ > ‎

面白CS論文2011

今年読んだ面白CS論文紹介カレンダーの参加記事3日目です。ブログ的なものとか使ってなかったので Google+ あたりに直接書こうかと一瞬思ったのですが、やっぱり分量と構成のある記事は書きづらかったので、大昔にアドレスだけ取ってあったここに置いてみました。

根が OS 屋さんなのでそっち系で、同じ会社の人向けや vimpl で話したことがある SOSP 2011 からいくつかを紹介してみます。他の話題で紹介したいものもあったのですが間に合わなさそうなので、後日遅刻で追加するかもしれません ;)


1. SOSP 2011: 決定的マルチスレッド実行とか、競合 (race) 絡みの話

OS 界隈ではここ数年、決定的マルチスレッド実行 (Deterministic Multi-threaded Execution) がやたら流行っているような気がします。彼らは「同じマルチスレッドプログラムに同じ入力を与えたら、同じように動作するようにする」ということがやりたい人たちで、プログラムや実行環境を「バグを発見しやすく」「デバッグしやすく」したい、というのが主なモチベーションになっているようです。

アプローチは、ものすごく大雑把に分けると 2 通りあります (私が知らないだけでここに当てはまらないのがあるかも?)

  1. ある特定のルールによって、固定されたスケジューリングをするように細工する。何回実行してもそれ以外の結果にならない。
  2. 一回実行した時のスケジュールを記録しておいて、再生実行できるようにする。記録を削除して実行すると違う結果になるかも。

それぞれに特徴、一長一短があります。 (私見含む)

  1. そのプログラムを実運用する時にも常に有効にしておくことが期待される。
    • 無効にすると、固定されてた以外のスケジュール (十分にテストしていないスケジュール) で動いちゃって困る。
    • 多少のオーバーヘッドはかかるが、ログを取ったり参照したりしないので、常に有効にしてもそれなりに速く動く余地がある (ような気がする)
  2. 基本的にテスト・デバッグするとき用になる。
    • テストを何回も回して、変な動きをした時のログを掘り起こして、再検証 → デバッグ、という使い方ができる。確率的にではあるがカバレッジが上がる。
    • 「これでもう充分テストしたぜ!」と思えれば記録しないようにして運用できる。ただしバグ入りスケジュールに迷い込む可能性を 0 にできたわけではない。

で、今回の 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 点だと思います。

  1. っていうか commit するには変更された箇所を把握しなきゃダメだよね。どうやってんの?
  2. それって pthread だった時にはありえなかった実行結果になったりしそうなんだけど...?
  3. 一度も同期命令を発行しないスレッドがいたらどうすんの? そいつのおかげで実行ストップしない?

この疑問に回答する形で説明してみます。

っていうか commit するには変更された箇所を把握しなきゃダメだよね。どうやってんの?

OS の copy-on-write 機構バンザイです (キリッ

並列フェーズでは、各スレッドは自分の private memory として共有メモリの内容を read-only map して実行を開始するようになっています。そこに書き込みが起こると fault が発生するのでそれをキャッチしてページに変更が起こったことを確認、後のことは copy-on-write に任せて実行を再開します。

その後のデータ同期処理は論文 p.329 の Figure 2. を参照してもらうのがよいと思います。 (図をコピーして引用したかったけど一応控えておきます) 単純に言うと、変更があったページについて共有メモリとの diff を取り、変更があった byte だけ書き込む、という merge 処理を各スレッドについて行います。

それって pthread だった時にはありえなかった実行結果になったりしそうなんだけど...?

「理論上は」 pthread でありえる実行結果になっています。

ただし、逐次フェーズに入る同期操作と同期操作の間がやたら離れていたりすると「いやいやこんなスケジュールには普通ならんでしょ (´Д`) 」という結果にはなりそうです。例えば pthread で実行していた場合に「しばらく同期してない間にあるスレッドだけやたら遅れを取ってしまったとき」などを再現したような結果になると思われます。

一度も同期命令を発行しないスレッドがいたらどうすんの? そいつのおかげで実行ストップしない?

結構気になったので、著者の人に聞いてみました。

「今のところその通りなんだよねー」

まじか (゚д゚)

「ただ実用的には、そういうスレッドを逐次フェーズ待ちのキューから外せば対応できるよ。今のところ、スレッドの中身に関して何も仮定しないようにしているからやってないけど」とのことでした。

最後にパフォーマンスについて。

これは論文の Figure 4-6. あたりを見ていただくのがよさそうです。大雑把に言うと CoreDet [ASPLOS10] という既存研究よりは基本的に高速。 pthread に比べると、大抵ちょっと (最悪で4倍程度) 遅いんだけど、何故かやたら速くなるベンチマークがたまにある、というのが興味深いポイントです。

速くなる理由についても述べられていて、大雑把に言うと false sharing を除去できたことが主な理由のようです。ここでは詳細は省略します。


1-2. Efficient Deterministic Multithreading through Schedule Relaxation

DTHREADS で頑張りすぎてしまったのでちょっと勢いを落とそう...。間に合わない。 [先延ばし屋08]

この論文は、決定的マルチスレッド実行のもう片方「一回実行した時のスケジュールを記録しておいて、再生実行できるようにする」にあたる内容です。記録を取って同じスケジュールで再実行する、という手法は今までも割とありました。それらに対するこの論文の主な contribution は、適用対象を広く維持したままでパフォーマンスを向上させた点です。決定的マルチスレッド実行環境 PEREGRINE というものを実装しています。

スケジュールの再現をするための既存手法には、記録・再現のポイントが 2 通りありました。

  • Sync-schedule: 同期操作を決定的に実行する (e.g. lock / unlock)
  • Mem-schedule: 共有メモリアクセスを全て決定的に実行する (load / store)

この 2 つには明らかなトレードオフがあります。 (ちなみに先の DTHREADS は前者のようでありつつ copy-on-write と merge を使って無理やり後者の結果を実現している荒業と呼べると思います)

  • Sync-schedule: 速い。けど競合 (race) があったときに決定的にスケジュールを再現できなくなることがある。
  • Mem-schedule: 競合があっても正しく決定的にスケジュールを再現できる。しかし遅い。

競合は大抵のプログラムにどこかしら含まれているので、せっかく速いのに 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. より引用)

  1. store to file-table
  2. load from inodes of path components
  3. store to inode of directory, if O_CREAT
  4. load from inode of file, if no O_CREAT
  5. store to data of file (range), if O_TRUNC

ただし、シグナルと共有メモリアクセスはシステムコールと関係のない任意のタイミングで起こるので、システムコール同士の順番を考えるだけでは解決できません。 RACEPRO では、ログを記録する際にいくつかの工夫をしているようです。この辺りは論文にもスライドにもモヤっとしか書かれていないのですが、おそらくシグナルや共有メモリアクセスが微妙なタイミングで起こってしまう場合の検出精度を少し犠牲にして、実行時のパフォーマンスを稼いでいる感じです。

いちおう軽く紹介すると、シグナルについては、

  • 同期可能な特定のポイント (システムコール) までシグナルの到達を遅らせる。

ということをやっているようです。共有メモリの方は、

  • ページごとに、一定時間有効な「所有プロセス・スレッド」が設定され、所有者は自由にそのページに書き込める。
  • 所有者以外が書き込もうとすると page fault が発生、所有プロセスがアクセスをブロックして同期ポイント (システムコール) まで待たせる。
  • 所有権の移行は、やはり同期ポイントで CREW (concurrent read, exclusive write) プロトコルに従って行われる。

というようなことが書いてあります。

検証

この検出方法で見つかった競合は、実は危険性の無いものかもしれません。たくさん見つかりすぎると困るので、危険性の無いものを自動的に捨てるための検証器が欲しい! というわけで、検証器も 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 さんと同じ感じですが、微妙に書ききれてないあたりにガッカリ感が漂います (笑

後ほど、不足部分を追記しつつ、ホントは書こうと思っていた SOSP のミーハーセレクションを 2 本ほど軽いノリで追加しようかと思っています :)

(※ 各章に "1-" とか付いてるあたりに予定していた心境が現れています)

とりあえず 1. の不足部分よりも先に、書きかけだった 2. ミーハー編を足してみました。 (Dec 18, 2011)

結局不足部分はほとんど足してない。というか意外と足すことなかった。 (Dec 31, 2011)

おっと、次の人を書くのを忘れてた。次は @cocoatomo さんです!

ą
Cells1.png
(172k)
Dai MIKURUBE,
2011/12/15 9:15
Comments