スケジューラアクティベーション続き。カーネルでの役割りはアドレス空間に
プロセッサ割当てることだけで、どれだけ割当てるかはユーザ層からの要求に
よって決定する。となるとユーザ層がとりたいだけプロセッサをとろうとした
時にどう対応するのか。結局はカーネルでのプロセッサ割当ても時分割にしな
いといけないのでは?そうなると時分割で横取りされたということをその度アッ
プコールでユーザ層に伝えないといけない。結構なオーバーヘッドだ。1:1なら
いくらカーネルの中で時分割してもユーザ層との通信はない。スケジューラア
クティベーションならできる限り時分割にはしたくない。逆に時分割でなけれ
ば、まだ相性はいいのかも?
Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism Thomas E.Anderson, Brian N.Bershad, Edward D.Lazowska and Henry M.Levy University of Washington ACM Transactions on Computersystems, Vol.10, No.1, February 1992,p53-79. 三つめは、ユーザ層スレッドがまったく走行していない時にユーザ層スレッド スケジューラの中で横取りやページフォルトが起きたとしても、スケジューラ アクティベーションは適切に動作するということ。この場合、スレッドスケ ジューラの状態はカーネルに退避される。その次に続くアップコールではもし ユーザ層スレッドが走行中であれば、あるやり方で(再入可能な)スレッド管理 システムを再開し、走行中でなければ別のやり方で再開する。それは新しいア クティベーションとそのスタック上で行なわれる。例えば、横取りされたプロ セッサがアイドルループだったとしたら、何もする必要がない; もしアップコー ル中に事象を処理している時であれば、ユーザ層のコンテキストスイッチは引 き続き事象を処理することができる。カーネルに追加される厄介な問題はプロ グラムのページフォルトを通知するアップコールは同じ場所でまたページフォ ルトするかもしれないことだ。カーネルはこれを調査しなくてはならなく、も しこの状態が起きたら、ページフォルトが完了するまでアップコールを遅延す る。 最後に、カーネル内でブロックされたユーザ層スレッドは、I/O完了の後、カー ネルモードでさらに実行する部分があるかもしれない。そうであれば、カーネ ルはもう一度ブロックするか、あるいはカーネルからユーザ層に戻るところま でを一時的にスレッドを再開し実行する。後者が起った場合にはカーネルはユー ザ層に通知し、ユーザ層スレッドのレジスタ状態をアップコールと一緒に受渡 す。 3.2 プロセッサ割当てに影響を与えるユーザ層の事象をカーネルに通知すること 3章の残りで述べる機構は、カーネルのアドレス空間の間でどうプロセッサを割 当てるかの方針とは独立である。しかしながら合理的な割当て方針はそれぞれ のアドレス空間で利用される並行性モデルに基づかねばならない。ここでは 走行可能なスレッドが存在しない時にはプロセッサをアイドル状態にしないこ とを保証し、優先度を大事にする方針のために、この情報が効果的に通信され ることを示す。 これらの束縛は我々の知る限り、ほとんどのカーネルスレッドシステムに存在 し、カーネルスレッドの上にユーザ層スレッドシステムを構築した場合には存 在しない。重要な点は、ユーザ層スレッドシステムはスレッド操作についてな にもカーネルに通知する必要がないだけでなく、いくつかの操作についてを(カー ネルに伝えることで)カーネルのプロセッサ割当ての決定に影響を与えることが できる点である。対照的に、カーネルスレッドを直接使った場合、次に走るス レッド(オーバーヘッドを最小化し、キャッシュを持続させる一方、優先度に従っ て選んだ)が同じアドレス空間のスレッドだったとしても、カーネルにトラップ しないといけない。 我々のシステムでは、アドレス空間は、プロセッサより多くのスレッドが必要 になったり、走行可能なスレッドよりプロセッサが存在する時のように状態が 以降する時に、カーネルに通知する。アプリケーションが実行するのに余分な スレッドを提供し、それに追加のプロセッサを割当てないのなら、システムの 全てのプロセッサは稼働中にならないとならない。さらに並行度を上げること ではの束縛を破れない。同様に、アプリケーションがアイドル中のプロセッサ があることをカーネルに通知して、カーネルがそれを取り上げない場合は、シ ステムには他に仕事がない状態でないとならない。カーネルはアイドル中のプ ロセッサが追加された通知を受ける必要がない。(このやり方の拡張で、アドレ ス空間よりはむしろスレッドが全体的な優先度をもつ状況を処理することがで きる) 表3には、これらのアドレス空間での状態の遷移によって呼び出されるカーネル 呼出しを一覧にした。例えばアドレス空間がカーネルにより多くのプロセッサ が必要だと通知した時、アイドル中のプロセッサがあると登録されたアドレス 空間から探す。もしみつからかった時は、何も起こらない。しかし、この先ど れか一つのプロセッサがアイドル状態になれば、最終的にこのアドレス空間は プロセッサを獲得する。これらの通知はヒントでしかない: もしカーネルがア ドレス空間にプロセッサを与え、その時にはもはや必要なかった場合、単純に アドレス空間は更新された情報とともにプロセッサをカーネルに返す。もちろ んその通知は順序の問題があるので、順序つけて通知しないといけない。 ---------------------------------------------------------------------- 表3 アドレス空間からカーネルへの通信 もっとプロセッサを追加せよ(追加として必要とされるプロセッサの数) カーネル→より多くのプロセッサをこのアドレス空間に割当て、スケジューラア クティベーションを実行して開始する。 このプロセッサはアイドル状態() カーネル→このプロセッサを横取りして、他のアドレス空間に割当てる。 ---------------------------------------------------------------------- このやり方の明らかな欠点は、アプリケーションのその並行度のOSへの通知が 正当でないかもかもしれないことだ。この問題はマルチプロセッサに特有の問 題ではない。正当でない、あるいは、間違ったプログラムは単一プロセッサ上 の並行処理でも不当に資源を獲得することができる。ユーザ層かカーネル層の どちらかにおいて、多層のフィードバックによってアプリケーションにプロセッ サの割当ての決定に対して正当な情報を提供するように促すことができる。プ ロセッサの割当てにおいて、少ないプロセッサを使うアドレス空間の優先度を 高くし、多く使うアドレス空間は低くする。これによって他のどこかでプロセッ サが必要な時にはアドレス空間にプロセッサを明け渡すことを促すことができ る。優先度を示すことで、プロセッサが必要な時に返ってきそうだからだ。そ の一方で、システム全体でプロセッサの数よりもスレッドの数が少ない場合に は、アイドル状態のプロセッサは近い将来使われる時のためにそのアドレス空 間に留っているべきであり、これによってプロセッサ再割当てのオーバヘッド を回避することができる。 多くの単一プロセッサOSでは、似たようなことをする。平均応答時間、とりわ け対話処理の性能は、残りの時間が最少のジョブを優先することで改善され、 それはしばしば、実行時間の合計によってジョブの優先度を減らすことで近似 される。似たような方針をマルチプロセッサ上の並行処理に使うことで、同じ 結果が得られると期待する。この方針によって簡単にアイドル状態のプロセッ サについて正しい情報を報告するようにしむけさせれる。 3.3 きわどい領域 これまでに検討していなかった問題の一つは、ユーザ層のスレッドは、ブロッ クされたり横取りされたりする時に、きわどい領域を実行していることがあり 得る。(1 ---------------------------------------------------------------------- (1 きわどい領域はwait-free同期[11]を使えば必要なくなるだろう。しかしな がら、多くの商用プロセッサでは、wait-free同期を実装するのに必要なCPU命 令がない(我々は原子的なtest-and-setだけを想定している)。さらに、 wait-free同期のオーバーヘッドはとても小さなデータ構造を保護するには大き 過ぎることになるかもしれない。 ---------------------------------------------------------------------- 二つの悪影響がある。性能の悪化(他のスレッドはその横取りされたスレッドの アプリケーションがロックしたままのスピンロックを取ろうとする)[28]、そし てデッドロック(横取りされたスレッドが実行待ち行列のロックを保持している こともあり得る。その場合、アップコールによってその割込まれたスレッドを 実行待ち行列に置こうとした時にデッドロックする)。きわどい領域がロックに よって保護されていない場合でも起きる。
