ふわっと理解するプロセススケジューラ実装のコンセプト
OS のプロセススケジューラの実装について調べました。
UNIX や Linux のような洗練された OS のスケジューラの実装はとても複雑で理解するのが大変ですが、スケジューラ実装の根本的なコンセプト自体は、少し単純化して表現できそうに思いました。
今回は、実装のコンセプトをつかむために、大幅に単純化した 60 行程の疑似コードを書いてみました。これからスケジューラのコードを読もうとされる方の参考になれば幸いです。
導入
汎用 OS は複数のプロセス（プログラム）を並列で実行することができます。この機能のおかげで、１つのパソコンで、音楽プレイヤーソフトで音楽を聞きながら、オフィスソフトで仕事ができます。
並列実行は、１つの CPU で実行するプログラムを高速に切り替えることで実現されます。この切り替えは、OS のプロセススケジューラが行っています。
不思議なこと
通常、プログラムは概ね以下のように、そのプログラムのロジックだけを記述し、ループを回していると思います。
while (1) { // application logic }
上のプログラムの中に、プロセススケジューラや、別のプログラムへ処理を移行する処理は記述されていません。
にもかかわらず、不思議なことに、OS はプロセススケジューラの処理を実行し、プロセスを適宜切り替えることができます。
タイマ割り込み
上記のような、閉じたループから、スケジューラの処理へ移行するためには、CPU に備わるタイマ割り込みの機能を使います。
ソフトウェアは、CPU に対して、タイマ割り込みハンドラと呼ばれる関数を設定できます。
タイマ割り込みが設定された場合、CPU は一定時間ごとに、現在実行されているプログラムの処理を停止して、タイマ割り込みハンドラへ処理をジャンプさせます。
多くの OS では、タイマ割り込みハンドラにプロセスの切り替え処理の入り口を実装します。
プロセス切り替え以外の仕事
スケジューラは、プロセスを切り替えるだけではなく、プロセスを、いつ、どれだけ実行するかを決定します。
疑似コード
上記のような、タイマ割り込みを入り口にして、プロセスの切り替えを行うスケジューラの実装を、簡略化した疑似コードにしてみました。
- 疑似コードでは、１CPU のみで実行されることを想定しています。
- 各プロセスは、一定時間実行されたら次のプロセスへ切り替えられるような実装を意図しています。
- 疑似コードなので、厳密ではないことに注意してください。
struct task { struct list_head _l; // キュー用のリストに紐付けるための構造体 uint64_t sum_exec_time; // 実行された合計時間を保存 }; struct runqueue { struct task *curr; // 現在実行中のプロセス struct list_head queue; // キュー用のリスト }; struct runqueue *rq; void enqueue_task(struct task *p) { list_add_tail(&p->_l, &rq->queue); // プロセス構造体をキューの最後へ入れる } void dequeue_task(struct task *p) { list_remove(&p->_l); // プロセス構造体をキューから取り外す } struct task *pick_next_task(struct task *prev) { struct task *next = list_first_entry(&rq->queue); // キューの先頭を取得 enqueue_task(prev); dequeue_task(next); } void switch_to(struct task *prev, struct task *next) { // architecture dependent } void schedule(void) { struct task *prev, *next; prev = rq->curr; next = pick_next_task(prev); rq->curr = next; switch_to(prev, next); } static uint64_t prev_interrupt; void timer_interrupt_handler(void) // 定期的に実行される { struct task *curr = rq->curr; uint64_t now, delta_exec; now = TIMER_NOW(); // 現在時刻を取得 delta_exec = now - prev_interrupt; // 経過時間を取得 prev_interrupt = now; // 次回のために現在時刻を保存 curr->sum_exec_time += delta_exec; // 経過時間を加算 if (curr->sum_exec_time > IDEAL_RUNTIME) schedule(); }
データ構造
スケジューラが扱うデータ構造は主に２種類で、プロセスに対応する構造体と、実行キューに対応する構造体です。
疑似コードの中では、プロセスに対応する構造体は、struct task で、キューに対応するのは、struct runqueue です。
実行キューは、プロセスのキューとなっており、enqueue_task、dequeue_task でそれぞれエンキュー、デキューを実装しています。
プロセスに対応する構造体は、fork システムコールが実行されたときに生成され、実行キューにエンキューされます。また、プロセスが終了した場合と、スリープや入力待ちのために待機する場合に、対応するプロセス構造体は実行キューから取り外されます。プロセスが待機状態から、イベントを受け取って実行可能状態に戻ると、再度、実行キューに入れられます。
処理の流れ
1. プロセスの実行時間を計測
タイマ割り込みハンドラ（ timer_interrupt_handler）の中で、現在実行中のプロセスが、どれだけの間実行されているかを計測します。以下のように、前回の割り込みからの経過時間を、プロセス構造体に紐付いた変数に足していきます。
now = TIMER_NOW(); // 現在時刻を取得 delta_exec = now - prev_interrupt; // 経過時間を取得 prev_interrupt = now; // 次回のために現在時刻を保存 curr->sum_exec_time += delta_exec; // 経過時間を加算
2. プロセスが実行された時間が、意図した時間を超過したか確認する
この前のステップで、プロセスの実行時間が更新されました。次に、その実行時間が意図した時間を経過したかを確認します。疑似コードの中では、意図した時間は IDEAL_RUNTIME という値で表現されています。
もし、プロセスが、意図した時間より長く実行されていた場合、プロセスの切り替えを行うために schedule 関数を実行します。もし、そうでない場合は、そのままプロセスを切り替えずにリターンします。
if (curr->sum_exec_time > IDEAL_RUNTIME)
schedule();
IDEAL_RUNTIME の設定に関する実装次第で、プロセスの切り替え頻度やタイミングが調整できます。
3. プロセスの切り替え
プロセスの実行時間が意図した長さを超過し、プロセスの切り替えが開始される場合を見ていきます。 以下の schedule 関数へ入ったコードパスです。
void schedule(void) { struct task *prev, *next; prev = rq->curr; next = pick_next_task(prev); rq->curr = next; switch_to(prev, next); }
3.1. 次に実行すべきプロセスを選択する
疑似コードでは、次に実行すべきプロセスは、pick_next_task という関数で取得します。
この関数はシンプルで、実行キューの先頭のプロセス構造体を返します。
struct task *pick_next_task(struct task *prev) { struct task *next = list_first_entry(&rq->queue);
3.2. これまで実行していたプロセスを実行キューに戻す
これまで実行していたプロセスを、実行キューの一番最後に入れます。これにより、各プロセスが順番に実行されるようになります。
struct task *pick_next_task(struct task *prev) { struct task *next = list_first_entry(&rq->queue); enqueue_task(prev); // prev を queue の最後に入れる
もし、ここで、これまで実行していたプロセスだけを、実行キューの最後ではなく、先頭に近いところに入れると、このプロセスは他のプロセスよりも頻繁に実行のチャンスを得られるようになります。
3.3. 次に実行するプロセスを実行キューから外す
これから実行するプロセスが prev になってこの処理に戻ってくるときのために実行キューから外しておきます。
struct task *pick_next_task(struct task *prev) { struct task *next = list_first_entry(&rq->queue); enqueue_task(prev); dequeue_task(next); // next をキューから外す }
実行中のプロセスをキューから外すかは実装次第で、実行中のプロセスはキューの先頭に置いておいたまま、プロセス切替時に後ろへ移動するという実装もあります。
3.4. CPU コンテキストスイッチ
pick_next_task から、次に実行するプロセスのプロセス構造体を取得しました。次に、switch_to 関数を実行して、CPU の状態を切り替えます。switch_to 関数の詳細は複雑なので、今回は割愛しますが、CPU の実行環境がそれまで実行していたプロセスのものから、次に実行されるプロセスのものに切り替わったと思ってください。
void schedule(void) { struct task *prev, *next; prev = rq->curr; next = pick_next_task(prev); rq->curr = next; switch_to(prev, next); // prev から next へコンテキストスイッチ }
ここまでが、タイマ割り込みに起因したプロセス切り替えの一連の流れです。
タイマ割り込み以外からのプロセス切り替え
上記の処理が、スケジューラの主な流れですが、タイマ割り込み以外からもプロセス切り替えが発生することがあります。
例えば、プロセスが read や poll のようなシステムコールを実行し、入力を待機する場合には、そのプロセスは実行の機会を手放し、そのプロセスが利用可能だったはずの実行時間は、他の CPU を利用したいプロセスに割り当てられます。
Linux のプロセススケジューラ実装との比較
Linux のプロセススケジューラの実装は、ソースコードの中で、linux/kernel/sched 以下にあります。
以下は、今回の疑似コードとの簡易な機能面での対応表です。対象の Linux のバージョンは 5.3 です。詳細な箇所の実装の意図は、疑似コードと大きく異なる場合があるため注意してください。
| 疑似コード | Linux | Linux での実装ファイル |
|---|---|---|
| struct task | struct task_struct | include/linux/sched.h |
| struct runqueue | struct rq | kernel/sched/sched.h |
| enqueue_task | enqueue_task | kernel/sched/core.c |
| enqueue_task | enqueue_task_fair=>rb_insert_color_cached | kernel/sched/fair.c |
| dequeue_task | dequeue_task | kernel/sched/core.c |
| dequeue_task | dequeue_task_fair=>rb_erase_cached | kernel/sched/fair.c |
| pick_next_task | pick_next_task | kernel/sched/core.c |
| pick_next_task | pick_next_task_fair=>rb_first_cached | kernel/sched/fair.c |
| switch_to | __switch_to_asm | arch/x86/entry/entry_64.S |
| schedule | schedule | kernel/sched/core.c |
| timer_interrupt_handler | scheduler_tick | kernel/sched/core.c |
| timer_interrupt_handler | task_tick_fair=>entity_tick=>check_preempt_tick | kernel/sched/fair.c |
- 疑似コードは、Completely Fair Scheduling (CFS) スケジューラを参考にしました。
- CFS の実装では、キューがリストではなく、ツリーになっています。
- Linux のキューの実装では、CFS には struct cfs_rq が用意されており、struct rq のメンバとなっているものを利用します。
- Linux ではキューの対象のプロセス構造体は、直接的には task_struct ではなくて、CFS 用には、そのメンバの struct sched_entity が使われます。
- 実際の実装における実行時間の計測はさらに複雑です。
- CFS の check_preempt_tick では、直接 schedule 関数を呼ばずに、resched_curr で schedule が必要であることを示すフラグだけを立てて、以降の切り替え処理は割り込みコンテキストからのリターン前に行われます。
- wate や wake のような、タイマ割り込み以外からのプロセスの切り替えについては、activate_task、deactivate_task のような関数の実装について見ていくと良さそうに見えます。
