KSE(2)

名称
kse - ユーザスレッドのためのカーネルサポート

ライブラリ
libc

書式
<sys/types.h> <sys/kse.h> int kse_create(struct kse_mailbox *mbx, int newgroup) int kse_exit(void) int kse_release(struct timespec *timeout) int kse_switchin(mcontext_t *mcp, long val, long *loc) int kse_thr_interrupt(struct kse_thr_mailbox *tmbx) int kse_wakeup(struct kse_mailbox *mbx)

解説
これらのシステムコールはマルチスレッド化されたプロセスのための カーネルサポートを実装しています。

  概要
伝統的にユーザスレッディングは、次の 2 つの方法の 1 つで実装されてきました。 全てのスレッドはユーザ空間で管理され、カーネルは全てのスレッディングを 認識しない方法 “(N 対 1” としても知られています)。 または、個々のスレッドのために共通のメモリ空間を分け合う 分離したプロセスを作成する方法 “(N 対 N” としても知られています)。 これらのアプローチは長所と短所を持っています:
ユーザスレッディング | カーネルスレッディング
+ 軽量 | - 重量
+ ユーザ制御スケジューリング | - カーネル制御スケジューリング
- システムコールのラッピング必須 | + システムコールのラッピング不要
- マルチ CPU の有効活用不可 | + マルチ CPU の有効活用可能

KSE システムはユーザスレッディングおよびカーネルスレッディングの両方の 長所を成し遂げる混成のアプローチです。 KSE システムの根本的な哲学は、スケジューリングを決定するための ユーザスレッディングライブラリの能力を全く取り除くことなく、 ユーザスレッディングのためのカーネルサポートを与えることです。 カーネルからユーザスレッドへの upcall 機構は、スケジューリングの決定が 必要とされるときにはいつでも、ユーザスレッディングライブラリに制御を 移すために使用されます。 任意の数のユーザスレッドは、カーネルによって供給される固定数の仮想 CPU 上に 多重化されます。 これは “N 対 M” スレッディング機構と考えることができます。

このアプローチのいくつかの一般的な裏の意味は以下を含みます:

•   ユーザプロセスはマルチプロセッサマシン上で複数のスレッドを 同時に実行することが可能です。 カーネルは、プロセス仮想 CPU がそれが望むようにスケジュールすることを 承諾します。これらは、実際の複数の CPU 上で同時に実行されることができます。

•   スレッドがブロックされたときにユーザプロセスが他のスレッドをスケジュール できるように、カーネル内でブロックする全ての操作は非同期になります。

•   同じプロセス内の複数のスレッドスケジューラが可能で、それらは互いに独立して 操作することができます。

  定義
KSE はユーザプロセスが実際に同時の複数の スレッド の実行を可能にします。 これらの幾つかは、その他のスレッドが実行中またはユーザ空間で ブッロクされている間に、カーネルの中でブロックされることが可能です。 カーネルスケジューリングの実体 (kernel scheduling entity, KSE) はスレッドの実行のためにプロセスに承諾された “仮想 CPU” です。 現在実行されているスレッドは常に、厳密に 1 つのユーザ空間または カーネルの中で動作しているどちらかの KSE に関連付けられています。 その KSE はそのスレッドに 割り当てられている と言われます。

その KSE が関連付けられた メールボックス (下記参照) を持っていて、そのスレッドが関連付けられた スレッドメールボックス (これも下記参照) を持っていて、さらに以下のどれかが発生したときに、その KSE が 割り当てられていない 状態になり、関連付けられたスレッドは停止されます:

•   そのスレッドがブロックを伴うシステムコールを実行する。

•   スレッドが、カーネルがすぐには満たすことが可能ではない他の全ての要求を行う。 例えばディスクからデータを読み出すために必要なメモリページに アクセスすることでページフォルト発生させることです。

•   カーネル内で先にブロックされていた他のスレッドが、カーネル内のその作業を 完了し (または 割り込まれ) 、ユーザ空間へ戻る準備ができ、さらに現在のスレッドがユーザ空間に 戻ろうとしている。

•   シグナルがプロセスに配信され、この KSE がそのシグナルを配信するために 選択される。

言い換えると、スケジューリングの決定が行われなければならなくなるとすぐに、 その KSE は割り当てられていない状態になります。 なぜならば、カーネルはそのプロセスの他のどの実行可能なスレッドを スケジュールするべきかを推定しないからです。 割り当てられていない KSE は常に可能な限り早く、 ユーザプロセスが次に利用するべき KSE をどのように決定するかを可能にする upcall 機構 (下記に記述されています) を介してユーザ空間に戻ります。 KSE は常に、割り当てが解除される前に、カーネル内で可能な限り多くの作業を 完了させます。

KSE グループ は均等にスケジュールされ、その KSE グループに関連付けられた同一のスレッドの プールへのアクセスを共有する KSE の集合です。 KSE グループはカーネルスケジューリングの優先度が割り当てられることができる 最小の実体です。 プロセスのスケジューリングとアカウンティングのため、それぞれの KSE グループは 伝統的なスレッド化されていないプロセスと同様にカウントします。 KSE グループの中の個々の KSE は実際上、見分けがつきません。 また、KSE グループの中のあらゆる KSE は、その KSE グループに 関連付けられた (カーネル内の) あらゆる実行可能なスレッドに、 カーネルによって割り当てられることができます。 実際問題として、カーネルはキャッシュの動作を最適化するために、スレッドと 実際の CPU との密接な関係を保存しようと試みますが、 これはユーザプロセスには不可視です。 (密接な関係はまだ実装されていません)

それぞれの KSE はユーザプロセスによって供給された唯一の KSE メールボックス を持っています。 メールボックスは upcall 関数 へのポインタを含む制御構造体とユーザスタックで構成されています。 KSE は割り当てを解除されると必ずこの関数を実行します。 カーネルはこの構造体を、実行可能になっているスレッド、およびそれぞれの upcall の前に配信されたシグナルについての情報を更新します。 upcall はクリティカルセクションの間は、ユーザスレッドの スケジューリングコードによって一時的にブロックされることがあります。

同様にそれぞれのユーザスレッドは唯一の スレッドメールボックス を持っています。 カーネルとユーザスレッドスケジューラが通信するときに、 スレッドはこれらのメールボックスへのポインタを使用して参照されます。 それぞれの KSE のメールボックスは、その KSE が現在実行している ユーザスレッドのメールボックスへのポインタを含んでいます。 このポインタはカーネル内でスレッドがブロックするときに、保存されます。

カーネル内でブロックされていたスレッドがユーザ空間に戻る準備ができたときには 必ず、そのスレッドは KSE グループの 完了した スレッドのリストに追加されます。 このリストはスレッドメールボックスのリンクされたリストとして、 次の upcall でユーザコードに公開されます。

カーネルの中で同時にブロックされることができる KSE グループの中の スレッド数には、カーネルに起因する制限があります (現在、この数はユーザには 不可視です)。 この制限に達したときには、スレッドの 1 つが完了するまでの間 (または シグナルが配信されるまでの間)、upcall はブロックされ、 その KSE グループのための作業は何も実行されません。

  KSE の管理
マルチスレッド化するためには、プロセスは初めに kse_create() を実行しなければなりません。 kse_create() システムコールは新しい KSE を 作成します (本当に最初の実行を除く、下記を参照してください)。 その KSE は mbx によって指されるメールボックスと関連付けられます。 newgroup が 0 ではない場合には、その KSE を含む新しい KSE グループも作成されます。 そうでない場合には、その新しい KSE は現在の KSE グループに追加されます。 新しく作成される KSE は最初は割り当てられていません。 そのため、それらの KSE は直ちに upcall します。

それぞれのプロセスは初めは 1 つのユーザスレッドを 実行する 1 つの KSE グループの中の 1 つの KSE を持っています。 その KSE は関連付けられたメールボックスを持っていないため、そのスレッドに 割り当てられたままでなければならず、upcall を全く実行しません。 この結果は伝統的で、スレッド化されていない様式の操作です。 そのため、特別な場合として、 newgroup を 0 にしたこの最初のスレッドによる kse_create() の最初の呼び出しは、新しい KSE を作成しません。 代わりに、単に現在の KSE を与えられた KSE メールボックスに関連付け、 直ちに upcall しない結果となります。 しかしながら、次にそのスレッドがブロックし、要求された条件になったときに、 upcall がトリガされます。

カーネルは 1 つの KSE グループの中にシステムの物理的な CPU の数 (この数は sysctl(3) 変数の hw.ncpu として利用可能です) より多い KSE の存在を許可しません。 CPU より多い KSE を持つことは、その追加の KSE が単に その他の KSE と実 CPU へのアクセスを競合するだけであるため、 ユーザプロセスにとって全く価値を増やさないでしょう。 そのため、余分な KSE は常に脇に追いやられ、その結果アプリケーションは まさにより少ない KSE を持っていることと同じになるでしょう。 どんなに多くの任意のユーザスレッドが存在することになっても、 利用可能な KSE へのアプリケーションのユーザスレッドの割り当てを取り扱う ためのユーザスレッドスケジューラに渡ります。

kse_exit() システムコールは、現在実行しているスレッドに割り当てられている KSE を 破壊させます。 この KSE がこの KSE グループの中の最後の 1 つの場合には、その KSE グループに 関連付けられているスレッドがカーネル内でブロックされたまま残ってはなりません。 このシステムコールはエラーが無い場合には、戻りません。

特別な場合として、最後に残っている KSE グループの中の最後に残っている KSE が このシステムコールを実行する場合には、その KSE は破壊されません。 代わりに、その KSE はそのメールボックスとの関連付けを失うだけで、 kse_exit() は正常に戻ります。 これはそのプロセスを元に、つまりスレッド化されていない状態に戻します。

kse_release() システムコールは、必要でなくなったときに、現在実行しているスレッドに 関連付けられている KSE を “一時保管” するために使用されます。 例えば、実行可能なユーザスレッドよりも利用可能な KSE の方が多いときです。 そのスレッドは upcall に変化しますが、そのようにするための新しい理由が 発生するまでの間スケジュールされることはありません。 例えば、以前にブロックされていたスレッドが実行可能になる、または タイムアウトが発生するなどです。 成功の場合には、 kse_release() は呼び出し側に戻りません。

kse_switchin() システムコールは、新しいスレッドがそのスレッドのコンテキストに 切り替わるために、UTS によって使用されることが可能です。 kse_switchin() の使用はマシンに依存します。 あるプラットフォームでは新しいコンテキストに切り替わるためのシステムコールを 必要としません。 一方、他のプラットフォームでは同様の場合に要求されます。

kse_wakeup() システムコールは kse_release() の反対です。 mbx によって指されているメールボックスに関連付けられた (一時保管された) KSE を upcall にすることで起こします。 その KSE がすでに他の理由で起こされていた場合には、このシステムコールは 何も起こりません。 mbx 引数は “現在の KSE グループの中の全ての KSE” を指定するために NULL にすることができます。

kse_thr_interrupt() システムコールは、現在ブロックされているスレッドに 割り込むために使用されます。 そのスレッドはカーネルの中でブロックされているか、 KSE に割り当てられて (例えば、実行中) いなければなりません。 そのスレッドはその後、割り込まれたという印を付けられます。 スレッドが割り込みを発生させるシステムコールを実行するとできるだけ 早く (または、スレッドがカーネルの中ですでにブロックされてると直ちに)、 カーネル操作が完了していないかもしれないのにもかかわらず、 そのスレッドは再度実行可能にされます。 割り込まれたシステムコール上のこの効果は、すでにシグナルによって 割り込まれていた場合と同様です。 通常、これは errno に EINTR が設定されてエラーが返されたことを意味します。

  シグナル

現在の実装は特別のシグナルスレッドを作成します。 プロセス内のカーネルスレッド (KSE) はすべてのシグナルをマスクし、 シグナルスレッドだけがプロセスへ配信されるシグナルを待ちます。 シグナルスレッドはユーザスレッドへのシグナルの ディスパッチに対して責任があります。

この弱点は、多重スレッドが execve() システムコールを呼び出すなら、そのシグナルマスクとペンディングシグナルは カーネルで利用可能でないかもしれないことです。 それらはユーザランドで格納され、カーネルはどこでそれらが得られるか知りません。 しかしながら、 POSIX ではそれらは復元され、新しいプロセスに渡す必要があります。 execve() 呼び出しの前のスレッドのマスク設定は、 古いプロセスがブロックされている状態かもしれない任意のペンディングシグナルを カーネルに再配信されないとき、問題に近似しています。 そして、新しいシグナルがマスクの設定と execve() の間のプロセスに配信されるかもしれないウィンドウを許可します。

当分、この問題は特別の組み合わせ kse_thr_interrupt()/execve() モードを kse_thr_interrupt() システムコールに追加することによって解決されています。 kse_thr_interrupt() システムコールはサブコマンド KSE_INTR_EXECVE があり、それは kse_execv_args 構造体を受け付けることができ、シグナルを調整して、次に不可分に execve()() 呼び出しに変換できます。 追加のペンディングシグナルと正しいシグナルマスクは このようにしてカーネルに渡すことができます。 スレッドライブラリは、 execve() スステムコールをくつがえして、それを kse_intr_interrupt() 呼び出しに変換し、多重スレッドを exec() を行なう前にペンディングシグナルと正しいシグナルマスクに 復元できるようにします。 この問題の解決法は変更するかもしれません。

  KSE メールボックス
それぞれの KSE は <sys/kse.h> で定義されたユーザとカーネルの通信のための唯一のメールボックスがあります。 そのフィールドのいくつかは次の通りです:

km_version はこの構造体のバージョンを表し、 KSE_VER_0 でなければなりません。 km_udata はカーネルによって無視される不透明なポインタです。

km_func はその KSE の upcall 関数を指します。 これは、その KSE が存在している間は有効であり続けなければならない km_stack を使用して実行されます。

km_curthread は常に、もしあれば現在この KSE に割り当てられているスレッドを、または そうでなければ NULL を指しています。 このフィールドは、カーネルとユーザプロセスの両方によって以下のように 更新されます。

km_curthread が NULL ではないときには、 それは現在実行中のスレッドのメールボックスを指しているものとみなされ、 割り当て解除されることができます。 例えば、スレッドがカーネル内でブロックする場合です。 それから、カーネルはブロックされたスレッドの km_curthread の内容を保存して km_curthread を NULL に設定し、 km_func() を実行するために upcall します。

km_curthread が NULL のときには、カーネルはこの KSE の upcall を決して実行しません。 言い換えると、KSE はたとえブロックしたとしても、そのスレッドに 割り当てられたままとなります。 その KSE が間に入り込む upcall によって混乱するであろうクリティカルな ユーザスレッドスケジューラのコードを実行している間、特に km_func() それ自身を実行している間は、 km_curthread は NULL でなければなりません。

全ての upcall の中で km_func() を実行する前に、カーネルは常に km_curthread を NULL に設定します。 一度、ユーザスレッドスケジューラが実行するべき新しいスレッドを選んだら、 そのスレッドのメールボックスの km_curthread を指すようにし、upcall を再度有効化し、それからそのスレッドを再開するべきです。 注意: ユーザスレッドスケジューラによる km_curthread の変更は、 新しいスレッドのコンテキストのロードについて不可分でなければなりません。 依然として有効な情報がそこから読み出されるべき時に、 ブロッキング非同期操作によってスレッドのコンテキスト領域が 変更されるかもしれない状況を避けるためです。

km_completed は最近の upcall 以降にカーネル内での処理を終えたユーザスレッドの リンクされたリストを指しています。 そのユーザスレッドスケジューラは、これらのスレッドを スケジューラが所有する実行可能キューに戻すべきです。 upcall に帰着する (同期または非同期に) カーネル操作を 完了した KSE グループ内の各々のスレッドは、確実に 1 つの KSE の km_completed にリンクされることが保証されます。 しかしながら、そのグループの中のどの KSE かは不定です。 その上、その完了はたった 1 つの upcall でしか報告されません。

km_sigscaught はその前のプロセス内の全ての KSE への upcall 以降に、 このプロセスによって捕まえられたシグナルのリストが含まれています。 そのユーザプロセスの中に、 メールボックスに関連付けられた KSE が 1 つ以上存在する限りは、 シグナルは伝統的な方法ではなくこの方法で配信されます。 (これはまだ実装されておらず、変更されるかもしれません)

km_timeofday は、それぞれの upcall の前にカーネルによって現在のシステム時刻に設定されます。

km_flags は以下の全てのビット毎の OR を含むことができます:

KMF_NOUPCALL
    upcalls が起きないようにブロックします。 スレッドは何らかのクリティカルセクション (危険域) にあります。

KMF_NOCOMPLETED, KMF_DONE, KMF_BOUND
    このスレッドは、永久に KSE に結びつけられると考えられるべきで、 スレッド化されていないプロセスとそっくりに扱われます。 それはある意味では KMF_NOUPCALL の “長期” バージョンです。

KMF_WAITSIGEVENT
    シグナル配信スレッドに必要な特性を実装します。

  スレッドメールボックス
それぞれのユーザスレッドはそれに関連付けられた <sys/kse.h> で定義された唯一の struct kse_thr_mailbox がなければなりません。 それは次のフィールドを含んでいます:

tm_udata はカーネルによって無視された不明瞭なポインタです。

tm_context はユーザ空間内でスレッドがブロックされた時に、そのスレッドのための コンテキストを保存します。 このフィールドは完了したスレッドが km_completed を介してユーザスレッドスケジューラに戻る前に、カーネルによっても更新されます。

tm_next はカーネルの upcall により戻った時に、 km_completed スレッドにリンクします。 このリストの最後は NULL でマークされます。

tm_uticks および tm_sticks はそれぞれ、ユーザモードおよびカーネルモードの実行のための時間カウンタです。 これらのカウンタは統計クロック ((clocks) 7 を参照してください) の刻みをカウントします。 カーネル内でいずれかのスレッドがアクティブに実行中の間は、対応する tm_sticks カウンタがインクリメントされます。 ユーザ空間でいずれかの KSE 実行中で、その KSE の km_curthread ポインタが NULL と等しくない間は、対応する tm_uticks カウンタがインクリメントされます。

tm_flags は以下の全てのビット毎の OR を含むことができます:

TMF_NOUPCALL
    KMF_NOUPCALL と同様です。 このフラグはクリティカルセクション (危険域) への upcall を禁止します。 いくつかのアーキテクチャは、ある場所ともう片方でいくつかにあることを 必要とします。

戻り値
成功の場合には kse_create(), kse_wakeup() および kse_thr_interrupt() システムコールは 0 を返します。 成功の場合には kse_exit() および kse_release() システムコールは戻りません。

エラーの場合には、これら全てのシステムコールは 0 ではない エラーコードを返します。

エラー
kse_create() システムコールは次の場合に失敗します:

[ENXIO]
    既に KSE グループの中にハードウェアプロセッサと同じ数の KSE が存在しています。

[EAGAIN]
    実行下の KSE グループのトータル数についてのシステムに課せられた制限を 超過します。 この制限は sysctl(3) MIB 変数 KERN_MAXPROC によって与えられます。 (この制限はスーパユーザのためを除き、実際にはこれより 10 小さい値です)

[EAGAIN]
    ユーザがスーパユーザではなく、1 ユーザによる実行下の KSE グループの トータル数についてのシステムに課せられた制限を超過します。 この制限は sysctl(3) MIB 変数 KERN_MAXPROCPERUID によって与えられます。

[EAGAIN]
    ユーザがスーパユーザではなく、 resource 引数 RLIMIT_NPROC に対応するソフトリソース制限を超過します ((getrlimit) 2 を参照してください)。

[EFAULT]
    mbx 引数がプロセスのアドレス空間の有効ではない部分のアドレスを指しています。

kse_exit() システムコールは次の場合に失敗します:

[EDEADLK]
    現在の KSE はその KSE グループ内の最後であり、 カーネル内でブロックされたその KSE グループに関連付けられたスレッドが 依然として 1 つ以上存在しています。

[ESRCH]
    現在の KSE は関連付けられたメールボックスを持っていません。 例えば、そのプロセスが伝統的なスレッド化されていないモードで、 実行しています (この場合はプロセスを終了するために _exit(2) を使用します)。

kse_release() システムコールは次の場合に失敗します:

[ESRCH]
    現在の KSE は関連付けられたメールボックスを持っていません。 例えば、そのプロセスが伝統的なスレッド化されていないモードで、 実行しています。

kse_wakeup() システムコールは次の場合に失敗します:

[ESRCH]
    mbx 引数が NULL ではなく、 mbx によって指されるメールボックスそのメールボックスが、そのプロセス内の いずれの KSE にも関連付けられていません。

[ESRCH]
    mbx 引数が NULL で、現在の KSE が関連付けられたメールボックスを持っていません。 例えば、そのプロセスが伝統的なスレッド化されていないモードで、 実行しています。

kse_thr_interrupt() システムコールは次の場合に失敗します:

[ESRCH]
    tmbx に対応するスレッドが、現在プロセス内のいずれの KSE にも割り当てられていないか、 カーネル内でブロックされています。

関連項目
rfork(2), pthread(3), ucontext(3) Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, ACM Transactions on Computer Systems, Issue 1, Volume 10, February 1992, ACM Press, pp. 53-79, Scheduler activations: effective kernel support for the user-level management of parallelism.

歴史
KSE システムコール群は FreeBSD 5.0 ではじめて登場しました。

作者
KSE は初めに -nosplit Julian Elischer <julian@FreeBSD.org> が実装し、 Jonathan Mini <mini@FreeBSD.org>, Daniel Eischen <deischen@FreeBSD.org> および David Xu <davidxu@FreeBSD.org> が追加の貢献をしました。

このマニュアルページは Archie Cobbs <archie@FreeBSD.org> によって書かれました。

バグ
KSE のコードは開発中です。