スケジューラ (scheduler) とはカーネルの構成要素で、 次に CPU で実行される実行可能なスレッドを決定するものである。 各々のスレッドには、スケジューリングポリシーと 「静的」なスケジューリング優先度 sched_priority が対応付けられる。 スケジューラは、システム上の全スレッドのスケジューリングポリシーと 静的優先度に関する知識に基づいて決定を行う。
通常のスケジューリングポリシー (SCHED_OTHER, SCHED_IDLE, SCHED_BATCH) の下でスケジューリングされるスレッドでは、 sched_priority はスケジューリングの決定に使用されない (sched_priority には 0 を指定しなければならない)。
リアルタイムスケジューリングポリシー (SCHED_FIFO, SCHED_RR) の下でスケジューリングされるスレッドは、 sched_priority の値は 1 (最低) から 99 (最高) の範囲となる (数字から分かるように、リアルタイムスレッドは常に通常のスレッドよりも 高い優先度を持つ)。 ここで注意すべきなのは、POSIX.1-2001 が要求しているのは、 リアルタイムポリシーの実装において最低 32 種類の異なる優先度レベルが サポートされることだけであり、いくつかのシステムではこの最低限の数の 優先度しか提供されていない、ということである。 移植性が必要なプログラムでは、 sched_get_priority_min(2) と sched_get_priority_max(2) を使って、あるポリシーがサポートする優先度の範囲を調べるべきである。
概念としては、 スケジューラはその sched_priority の値それぞれに対して 実行可能なスレッドのリストを管理している。 どのスレッドを次に実行するかを決定するために、 スケジューラは静的優先度の最も高い空でないリストを探して、 そのリストの先頭のスレッドを選択する。
各スレッドのスケジューリングポリシーは、 そのスレッドが同じ静的優先度を持つスレッドのリストの中のどこに挿入され、 このリストの中をどのように移動するかを決定する。
全てのスケジューリングはプリエンプティブ (preemptive) である: より高い優先度のスレッドが実行可能になると、現在実行中のスレッドは実行権を 取り上げられ (preempted)、そのスレッドの静的優先度レベルの待ちリストに 戻される。スケジューリングポリシーは同じ静的優先度を持つ実行可能な スレッドのリストの中で順番のみを決定する。
SCHED_FIFO は 0 より大きな静的優先度でのみ使用できる。このポリシーでは、 SCHED_FIFO スレッドが実行可能になった場合、 そのポリシーが SCHED_OTHER、 SCHED_BATCH、 SCHED_IDLE の 現在実行中のスレッドは直ちに実行権を取り上げられる。 SCHED_FIFO は時分割のない単純なスケジューリングアルゴリズムである。 SCHED_FIFO ポリシーでスケジューリングされているスレッドには以下の ルールが適用される:
- より高い優先度の他のスレッドによって取って代わられた SCHED_FIFO スレッドはその優先度のリストの先頭に留まり続け、 より高い優先度のスレッド全てが停止 (block) した場合に実行を再開する。
- SCHED_FIFO スレッドが実行可能になった時、その優先度のリストの最後 に挿入される。
- sched_setscheduler(2), sched_setparam(2), sched_setattr(2) は pid で指定された SCHED_FIFO (または SCHED_RR) スレッドが 実行可能な場合、リストの最初に置く。 結果として、もし優先度が同じだった場合、 現在実行中のスレッドに先んじるかもしれない。 (POSIX.1-2001 ではスレッドはリストの最後に行くべきと規定されている。)
- sched_yield(2) を呼び出したスレッドはリストの最後に置かれる。
その他のイベントによって SCHED_FIFO ポリシーでスケジューリングされるスレッドが同じ優先度の実行可能なスレッドの待ちリストの中を移動することはない。
SCHED_FIFO スレッドは I/O 要求によって停止するか、 より高い優先度のスレッドによって置きかえられるか、 sched_yield(2) を呼び出すまで実行を続ける。
SCHED_RR は SCHED_FIFO の単純な拡張である。 上述された SCHED_FIFO に関する記述は全て SCHED_RR に 適用できる。異なるのは それぞれのスレッドは最大時間単位までしか実行できない ということである。 SCHED_RR スレッドが時間単位と同じかそれより 長い時間実行されると、 その優先度のリストの最後に置かれる。 より高い優先度のスレッドによって 置きかえられ、その後実行を再開した SCHED_RR スレッドは、そのラウンド ロビン時間単位を完全に使い切る まで実行される。その時間単位の長さは sched_rr_get_interval(2) を使って取得できる。
バージョン 3.14 以降では、 Linux はデッドラインスケジューリングポリシー (SCHED_DEADLINE) が提供される。 現在のところ、 このポリシーは GEDF (Global Earliest Deadline First) を使って CBS (Constant Bandwidth Server) との組み合わせで実装されている。 このポリシーと関連する属性の設定、取得を行うには、 Linux 固有のシステムコール sched_setattr(2) と sched_getattr(2) を使用する必要がある。
散発タスク (sporadic task) はジョブ列を持つタスクで、 各ジョブは期間 (period) あたり多くとも 1 回だけ有効化される。 各ジョブには relative deadline (相対デッドライン) と computation time (計算時間) がある。 相対デッドラインは、そのジョブがそのデッドラインより前に実行が終了すべきであることを示す。 計算時間は、このジョブを実行するのに必要な CPU 時間である。 新しいジョブを実行する必要が出てタスクが起こされる時点は arrival time (到着時刻) と呼ばれる (要求時刻 (request time) や解放時刻 (release time) と呼ばれることもある)。 start time はタスクが実行を開始する時刻である。 したがって、 absolute deadline (絶対デッドライン) は到着時刻に相対デッドラインを加算することで求められる。
以下の図はこれらの用語をまとめたものである。
arrival/wakeup absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<- comp. time ->|
|<------- relative deadline ------>|
|<-------------- period ------------------->|
sched_setattr(2) を使ってスレッドに SCHED_DEADLINE ポリシーを設定する際、 Runtime, Deadline, Period の 3 つのパラメーターを指定することができる。 これらのパラメーターは必ずしも上で述べた用語に対応しているわけではない。 よくある方法としては、 Runtime に平均計算時間 (もしくはハードリアルタイムタスクの場合は最悪ケースの実行時間) よりも大きな値を、 Deadline に相対デッドラインを、 Period にタスクの期間 (period) を設定する。 したがって、 SCHED_DEADLINE スケジューリングでは、 以下のようになる。
arrival/wakeup absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<-- Runtime ------->|
|<----------- Deadline ----------->|
|<-------------- Period ------------------->|
3 つのデッドラインスケジューリングパラメーターは sched_attr 構造体の sched_runtime, sched_deadline, sched_period フィールドに対応する。 これらのフィールドはナノ秒単位の値である。 sched_period に 0 が指定された場合 sched_deadline と同じ値になる。
カーネルでは以下の関係が成り立つことが求められる。
sched_runtime <= sched_deadline <= sched_period
これに加えて、 現在の実装では、 すべてのパラメーター値は少なくとも 1024 (実装の粒度である 1 マイクロ秒よりも少しだけ大きな値) で 2^63 よりも小さくなければならない。 これらのチェックのいずれかが失敗すると、 sched_setattr(2) はエラー EINVAL で失敗する。
CBS によりタスク間の干渉がないことが保証される。 指定された Runtime を超えて実行しようとしたスレッドは絞り込まれることになる。
デッドラインスケジューリングの保証がきちんと機能するためには、 カーネルは SCHEDULING スレッドの集合が指定された制約条件におさまらない (スケジューリングできない) 状況を防止しなければならない。 そのため、カーネルは SCHED_DEADLINE ポリシーと属性を設定、変更する際に、受け入れチェック (admittance test) を実行する。 この受け入れチェックは、変更が実行可能かを計算し、もし実行できないようであれば sched_setattr(2) はエラー EBUSY で失敗する。
例えば、 使用率の合計が利用可能な合計 CPU 数以下である必要がある (ただし、必ずしも十分というわけではない)。 なお、 各スレッドは最大で Period あたり Runtime だけ実行されることがあるので、 そのスレッドの使用率は Runtime を Period で割ったものとなる。
スレッドが SCHED_DEADLINE ポリシーに受け入れられた場合に保証を実現するため、 SCHED_DEADLINE スレッドはシステムで (ユーザーが制御可能な) 最高優先度のスレッドとなる。 いずれかの SCHED_DEADLINE スレッドが実行可能であれば、 他のポリシーでスケジューリングされているスレッドはすべて横取りされる。
SCHED_DEADLINE ポリシーでスケジューリングされているスレッドが fork(2) を呼び出すと、 そのスレッドで reset-on-fork フラグがセットされている場合 (下記参照) を除き、 エラー EAGAIN で失敗する。
SCHED_DEADLINE スレッドが sched_yield(2) を呼び出すと、 現在のジョブが CPU を明け渡し、新しい期間が開始するのを待つ。
SCHED_OTHER は静的優先度 0 でのみ使用できる。 SCHED_OTHER は Linux 標準の時分割スケジューラで、 特別なリアルタイム機構を必要としていない全てのスレッドで使用される。 実行するスレッドは、静的優先度 0 のリストから、このリストの中だけで 決定される「動的な」優先度 (dynamic priority) に基いて決定される。 動的な優先度は (nice(2), setpriority(2), sched_setattr(2) により設定される) nice 値に基づいて決定されるもので、 単位時間毎に、スレッドが実行可能だが、スケジューラにより実行が拒否された 場合にインクリメントされる。 これにより、全ての SCHED_OTHER スレッドでの公平性が保証される。
(Linux 2.6.16 以降) SCHED_BATCH は静的優先度 0 でのみ使用できる。 このポリシーは (nice 値に基づく) 動的な優先度にしたがってスレッドの スケジューリングが行われるという点で、SCHED_OTHER に似ている。 異なるのは、このポリシーでは、スレッドが常に CPU に負荷のかかる (CPU-intensive) 処理を行うと、スケジューラが仮定する点である。 スケジューラはスレッドを呼び起こす毎にそのスレッドにスケジューリング上の ペナルティを少し課し、その結果、このスレッドはスケジューリングの決定で 若干冷遇されるようになる。
このポリシーは、非対話的な処理だがその nice 値を下げたくない処理や、 (処理のタスク間で) 余計なタスクの置き換えの原因とある対話的な処理なしで 確定的な (deterministic) スケジューリングポリシーを適用したい処理に 対して有効である。
(Linux 2.6.23 以降) SCHED_IDLE は静的優先度 0 でのみ使用できる。 このポリシーではプロセスの nice 値はスケジューリングに影響を与えない。
非常に低い優先度でのジョブの実行を目的としたものである (非常に低い優先度とは、ポリシー SCHED_OTHER か SCHED_BATCH での nice 値 +19 よりさらに低い優先度である)。
各スレッドには reset-on-fork スケジューリングフラグがある。 このフラグがセットされると、 fork(2) で作成される子プロセスは特権スケジューリングポリシーを継承しない。 reset-on-fork フラグは以下のいずれかの方法でセットできる。
これらの 2 つの API で使用される定数は名前が違っている点に注意すること。 同様に reset-on-fork フラグの状態は sched_getscheduler(2) と sched_getattr(2) を使って取得できる。
reset-on-fork 機能はメディア再生アプリケーションでの利用を意図したものである。 複数の子プロセスを作成することで、 アプリケーションは RLIMIT_RTTIME リソース上限 (getrlimit(2) を参照) を避けることができる。
より正確には、 reset-on-fork フラグがセットされた場合、それ以降に作成される子プロセスに以下のルールが適用される。
- 呼び出したスレッドのスケジューリングポリシーが SCHED_FIFO か SCHED_RR の場合、子プロセスのポリシーは SCHED_OTHER にリセットされる。
- 子プロセスが負の nice 値を持っている場合、子プロセスの nice 値は 0 にリセットされる。
一度 reset-on-fork フラグが有効にされた後は、このフラグをリセットできるのは、スレッドが CAP_SYS_NICE ケーパビリティを持つ場合だけである。このフラグは fork(2) で作成された子プロセスでは無効になる。
2.6.12 より前のバージョンの Linux カーネルでは、 特権スレッド (CAP_SYS_NICE ケーパビリティを持つスレッド) だけが 0 以外の静的優先度を設定する (すなわち、リアルタイムスケジューリングポリシーを設定する) ことができる。 非特権スレッドができる変更は SCHED_OTHER ポリシーを設定することだけであり、さらに、 この変更を行えるのは、 呼び出し元の実効ユーザー ID がポリシーの変更対象スレッド (pid で指定されたスレッド) の実ユーザー ID か実効ユーザー ID と 一致する場合だけである。
SCHED_DEADLINE ポリシーを設定、変更するには、スレッドが特権 (CAP_SYS_NICE) を持っていなければならない。
Linux 2.6.12 以降では、リソース制限 RLIMIT_RTPRIO が定義されており、 スケジューリングポリシーが SCHED_RR と SCHED_FIFO の場合の、非特権スレッドの静的優先度の上限を定めている。 スケジューリングポリシーと優先度を変更する際のルールは以下の通りである。
- 非特権スレッドに 0 以外の RLIMIT_RTPRIO ソフトリミットが設定されている場合、 非特権スレッドはそのスレッドのスケジューリングポリシーと優先度を 変更できるが、優先度を現在の自身の優先度と RLIMIT_RTPRIO ソフトリミットの大きい方よりも高い値に設定できないという制限が課される。
- RLIMIT_RTPRIO ソフトリミットが 0 の場合、優先度を下げるか、 リアルタイムでないポリシーへ切り替えるかの変更だけが許可される。
- ある非特権スレッドが別のスレッドに対してこれらの変更を行う際にも、 同じルールが適用される。変更を行えるのは、変更を行おうとするスレッド の実効ユーザー ID が変更対象のスレッドの実ユーザー ID か実効ユーザー ID と 一致している場合に限られる。
- SCHED_IDLE ポリシーの場合には特別なルールが適用される。 2.6.39 より前の Linux カーネルでは、このポリシーで動作する非特権スレッドは、 RLIMIT_RTPRIO リソース上限の値に関わらず、自分のポリシーを変更することができない。 2.6.39 以降の Linux カーネルでは、非特権スレッドは、自分の nice 値が RLIMIT_NICE リソース上限 (getrlimit(2) 参照) で許可された範囲である限りは、自分のスケジューリングポリシーを SCHED_BATCH か SCHED_NORMAL ポリシーに切り替えることができる。
特権スレッド (CAP_SYS_NICE ケーパビリティを持つスレッド) の場合、 RLIMIT_RTPRIO の制限は無視される; 古いカーネルと同じように、スケジューリングポリシーと優先度に対し 任意の変更を行うことができる。 RLIMIT_RTPRIO に関するもっと詳しい情報は getrlimit(2) を参照のこと。
SCHED_FIFO, SCHED_RR, SCHED_DEADLINE でスケジューリングされる スレッドが停止せずに無限ループに陥ると、 他の全てのより低い優先度のスレッドを永久に停止 (block) させてしまう。 Linux 2.6.25 より前では、 リアルタイムプロセスが暴走してしまい、システムが止まってしまうのを防止する唯一の方法は、 (コンソールで) シェルをテスト対象のアプリケーションよりも高い静的優先度で実行することだけであった。 これによって期待通りに停止したり終了したりしないリアルタイム アプリケーションを緊急終了させることが可能になる。
Linux 2.6.25 以降では、 暴走したリアルタイムプロセスやデッドラインプロセスを扱う別の方法が提供されている。 一つは RLIMIT_RTTIME リソース上限を使ってリアルタイムプロセスが消費できる CPU 時間の上限を設定する方法である。 詳細は getrlimit(2) を参照。
Linux 2.6.25 以降では、 2 つの /proc ファイルを使って、リアルタイムでないプロセスが使用できる CPU 時間を一定量予約することができる。 この方法で CPU 時間をいくらか予約しておくことで、 CPU 時間が (例えば) root シェルに割り当てられ、このシェルから暴走したプロセスを殺すことができる。 これらのファイルでは両方ともマイクロ秒で時間を指定する。
- /proc/sys/kernel/sched_rt_period_us
- このファイルは、 CPU 時間 100% にあたるスケジューリング間隔を指定する。 このファイルの値として 1 から INT_MAX を指定できる。 この値は実際の時間としては 1 マイクロ秒から約 35 分に相当する。 このファイルのデフォルト値は 1,000,000 (1 秒) である。
- /proc/sys/kernel/sched_rt_runtime_us
- このファイルの値は、 システム上のリアルタイムスケジューリングやデッドラインスケジューリングの全プロセスが使用できる「期間」を指定する。 このファイルの値として -1 から INT_MAX-1 を指定できる。 -1 を指定すると、実行時間 (runtime) はスケジューリング間隔 (period) と同じになる。 つまり、 CPU 時間はリアルタイムでないプロセスには確保されない (カーネル 2.6.25 より前の Linux の動作である)。 このファイルのデフォルト値は 950,000 (0.95 秒) である。 これは CPU 時間の 5% がリアルタイムやデッドラインスケジューリングポリシー以外で動作するプロセスに確保されるという意味する。
I/O 待ちで停止したより高い優先度のスレッドは再びスケジューリングされる 前にいくらかの応答時間がかかる。デバイスドライバーを書く場合には "slow interrupt" 割り込みハンドラーを使用することで この応答時間を劇的に減少させることができる。
chrt(1)EN, taskset(1)EN, getpriority(2), mlock(2), mlockall(2), munlock(2), munlockall(2), nice(2), sched_get_priority_max(2), sched_get_priority_min(2), sched_getscheduler(2), sched_getaffinity(2), sched_getparam(2), sched_rr_get_interval(2), sched_setaffinity(2), sched_setscheduler(2), sched_setparam(2), sched_yield(2), setpriority(2), pthread_getaffinity_np(3), pthread_setaffinity_np(3), sched_getcpu(3), capabilities(7), cpuset(7)EN
Programming for the real world - POSIX.4 by Bill O. Gallmeister, O'Reilly & Associates, Inc., ISBN 1-56592-074-0.
Linux カーネルソースのファイル Documentation/scheduler/sched-deadline.txt, Documentation/scheduler/sched-rt-group.txt, Documentation/scheduler/sched-design-CFS.txt, Documentation/scheduler/sched-nice-design.txt