Skip to content

ghc rts memo

Jump to bottom Edit New page
s50 edited this page Sep 20, 2011 · 6 revisions

本稿はHaskellや難しい理論にあまり興味の無い人間が、M:Nモデルのファンだからというだけの理由でGHCのRTS、FFI、I/O Managerについて調べた際のメモです。主な関心はforkIOにより作られるユーザスレッドがOSスレッド、I/Oのブロックとどう折り合いを付けているかで、GHCのデータ並列性サポート、それにGCについては特に触れません。間違いの指摘やアドバイスがあればtwitter:s50へ一言いただけると嬉しいです。

M:Nスレッド

概観

GHC-SMPはM:Nスレッドモデルを採用しており、RTSが複数のユーザスレッドを複数のOSスレッドへ小分けにして実行を進めます。OSスレッドは普通RTSの起動時にCPUの数だけ作られますが、FFIによりsafeな外部関数を呼ぶ場合、また結合スレッドを作る際に追加で作られることもあります。parにより作られるsparkは暗黙にユーザスレッドとして実行されることとなり、forkIOにより明示的に作られるユーザスレッドとスケジューラレベルで統合されています。

Task、OSスレッドの抽象化

RTSにおいてOSスレッドはOSThreads.cによりPosix/Win32の差異が吸収され、Task.cのタスクマネージャサブシステムによってワーカースレッドの生成、破棄、実行状態が管理されます。

Capabilityとワーカースレッド

OSスレッドがHaskellのコードを実行するために必要な構造体はCapabilityと呼ばれます。HEC(Haskell Execution Context)と呼ばれることもあります。

タスクマネージャサブシステムはOSスレッドをワーカースレッドとして生成し、ワーカーがCapabilityと結び付いてHaskellコードを実行します。

GHC-SMPではRTSが複数のCapability、ワーカーを持つことができ、あるCapabilityはその時々にいずれかのワーカーに結び付いて実行されることとなります。

各Capabilityは予備のワーカースレッドを持つことがあります。これはsafeな外部関数呼び出しを行う際、外部関数側でのブロックでCapability全体を止めないようにする為などに作られます。（後述）

誤解を恐れずに言えば、Capabilityは（可能性として複数の）OSスレッド、複数のユーザースレッド、Sparkプール、仮想マシン（STG）のステートの集合体です。

ユーザスレッドとスケジューラ

ユーザスレッドはラウンドロビンでスケジューリングされ、各Capability上でスケジューラが動作します。

スケジューラはユーザスレッドがブロックした際や終了した際、またGCやメモリチェックの際に呼び出されます。またRTSはタイマにより所定のタイムスライスを消費した際にGCの起動フラグを立てることから、コンテキストスイッチは以下のような状況で起こり得ます。

ヒープの不足
スレッドのyield
スレッドのブロック
スレッドの終了
スタックオーバーフロー
（タイムスライスの消尽）

GHCのユーザスレッドはプリエンプティブとされていますが、メモリチェックやGC、yield、ブロックを通さなければコンテキストスイッチが起こらないため、これらを必要とする操作を行わないユーザスレッドに関してはタイムスライスを消費し切っても実行を続けることがあり得ます。とは言え、そのようなスレッドは稀なものとされています。

forkIOとpar、ユーザスレッドとspark

Haskellでユーザスレッドを作成する方法にはforkIOを使った明示的な方法と、parによるそんなに明示的でもない方法があります。 parの第一引数はsparkを作り、ユーザスレッドの実行キューが空の時にsparkからユーザスレッドが作られ、実行キューへ加えられることとなります。

Spark PoolはWork-stealing Dequeを使って管理されており、Sparkをスレッドに変える際、Capability自身のSparkプールが空の場合は別のCapabilityからSparkを取り出します。

Sparkは一度ユーザスレッドになってしまえば通常のスケジューリングが適用されますが、実際にユーザスレッドになるタイミングはCapabilityの手があいている時、ということになります。

FFI

forkOSとforkIO（結合スレッドと非結合スレッド）

ユーザスレッドはRTSの起動するいずれかのOSスレッド（ワーカースレッド）上で実行されますが、いつどのユーザスレッドをどのOSスレッド上で実行するかはスケジューラにより決められます。

これはOpenGLや一部のGUIツールキット、再帰ミューテックスのような、OSスレッドに固有のデータを利用する外部関数を呼び出す際問題となります。

例えば、あるユーザスレッドがあるOSスレッド上でOpenGLの描画コンテキストを作成した後、実際の描画関数を呼び出す際にはそのユーザスレッドが別のOSスレッド上で実行されている場合があり得る、ということです。

forkOSは新たなOSスレッドを作るもので、forkOSにより作られたスレッド上での外部関数呼び出しは常に同じOSスレッドで実行されます。これを結合スレッドと呼びます。

これに対し、forkIOにより作られるものは非結合スレッドと呼ばれ、ユーザスレッドがいずれかのOSスレッドで実行されるというものです。

結合スレッドの存在により、GHCのスレッドモデルはM:N（あるいは1:N）スレッドモデルと1:1スレッドとを組み合わせた複合モデルである、と言うこともできます。

safeとunsafe

GHCのFFIの要件には公平性の保証というものがあります。これはあるユーザスレッドが外部関数を呼び出す際、他のユーザスレッドがそれと関わりなく実行を続けるという保証です。

safeとマークされたforeign importを通して外部関数を呼び出す際、コンパイラは呼び出しの前後にこれを保証するためのコードを自動挿入します。

自動挿入されたコードは外部関数呼び出しの前にユーザスレッドのステートを保存し、Capabilityを手放して予備のワーカースレッドへその所有権を譲ります。もしそのCapability用に予備のワーカースレッドが余っていなければ、新たなワーカースレッドを作成します。

これにより、たとえsafeな外部関数呼び出しがブロックする場合であっても、他のユーザスレッドは予備のワーカースレッド上で実行を続けることができます。

一方、unsafeなforeign importを通して外部関数が呼び出される場合、このようなコードの自動挿入が行われません。そのためunsafeな外部関数呼び出しはsafeなものと比べてオーバーヘッドがありませんが、外部関数がブロックする際には全てのユーザスレッドがブロックすることになり得ます。

conc-ffiの記述に従った言い方をすると、unsafeな外部関数呼び出しがブロックする場合の挙動は不定です。とにかく保証されているのは、safeな外部関数呼び出しは他のユーザスレッドの実行を妨げない、ということです。

concurrent？とreentrant？

safe/unsafeには理由あってこの名が付いている訳ですが、十分にその機能を表した名前とは言いがたいものがあります。たとえば、safe/unsafeには呼び出した外部関数がHaskell関数を呼び出すことが可能かどうか（再入可能かどうか）という別の意味もあります。

Haskell処理系の中にはGHCと同じような並列/並行処理サポートを持たないものもあるのですが、そういった処理系においてもsafe/unsafeは使われている訳です。

safe/unsafeという用語はFFIを「安全に」行うことができるかという意味を完全に表してはいるのですが、それがどういった意味での「安全」であり、どんな外部関数が「安全」に呼び出されなければならないかは、FFIや並行/並列処理の実装をあらかじめ知る者でなければ想像しづらいものとなっています。

次期Haskell標準を決めるhaskell-primeのMLログなどを見ると、nonconcurrent/nonreentrantというようなsafe/unsafeの代わりとなるアノーテーションが提案されているようです。nonconcurrentと付けられたものは処理系が公平性の保証をしなくともよく、nonreentrantと付けられたものについては再入可能かどうかを意に介さないという訳です。

変更の主な目的は処理系作者の負担を減らしつつ最低限の標準を作るということでしょうが、利用者にとっても用語の意味が明確になるように思います。

I/O Manager

さて、I/OはFFIを通しOSのAPIを呼び出して実現するのが自然です。このときM:Nスレッドモデル、結合スレッド/非結合スレッド、safe/unsafeといった仕組みはどのようにI/Oの処理に関わってくるのでしょうか？

I/O ManagerはGHCにおいて効率的なI/Oを行うためのシステムです。GHCではI/Oにおけるブロックは、safeな外部関数呼び出しを利用するだけで他のユーザスレッドの進行を妨げない無害なものとなる訳ですが、複数のユーザスレッドがI/Oを行う度にそれぞれが新たなOSスレッドを作るというのも効率上の問題があります。

RTSは1つのI/O Manager Threadを非結合スレッドとして作成します。I/O Manager Threadはsafe foreign importされたepoll_waitやkeventを繰り返し呼び出し、他のユーザスレッドから依頼されたファイルディスクリプタを監視することでI/O要求に応答します。これにより、I/Oのために作る追加のOSスレッドはepoll_waitやkeventへのsafeな外部関数呼び出しのためのものだけとなります。

何故このような仕組みをとっているのでしょう。例えば、I/O Manager Threadを結合スレッドとして作れば別のOSスレッドとして分離される訳なので、I/O Manager Thread自体がepoll_waitやkeventでブロックしたとしても同じ目的が達成できそうに見えます。

正直なところ理由は分かりませんが、結合スレッドの目的はあくまでOSスレッドに固有のデータについて一貫した扱いを保つことであり、スレッドのブロックを隔離するための機構ではない、というところにヒントがあるのかもしれません。（かなりテキトー言ってるので分かる人教えてください）

超いい加減な実装の経緯とか

GHC-SMPの並行処理の元となるConcurrent Haskellは、1つのOSスレッド上で複数のユーザスレッドを実行する1:Nモデルで実装されました。

これがFFIと組み合わさる際に結合スレッドと非結合スレッドが生まれ、Haskellコードの実行には常に1つのOSスレッド（単一のCapability）、FFIの際には別のOSスレッドが使われ得るという構造になりました。

その後OSスレッド毎に持つ構造と共有する構造とを分け、適切なロックを行い、複数のCapabilityを持てるようランタイムを拡張することでM:NモデルのGHC-SMPが生まれました。

SparkはGUMやGpHのような古めの並列Haskellから受け継がれたものと思われます。

conf-ffiを読めば分かるように、元のConcurrent Haskellはユーザスレッドを大量に作ることによる表現力を求めたもので性能は二の次であったため、当初複雑なM:Nモデルを避けていました。

SMP対応のために泥臭い実装努力が為され、実際にサーバアプリでスケールさせるよう当初selectを使っていたI/O Managerがepoll/kqueueベースとなり、イベントベースのAPIが加わるなどした末に、現在の実装に至っています。

現在のGHC-SMPのユーザスレッドは比較的単純な構造のもので、例えば優先度の仕組みがありません。これはM:Nモデルでしばしば問題となる優先度逆転のような厄介な問題を避けるためです。

参考URL

Add a custom footer
Add a custom sidebar
Clone this wiki locally