Linuxカーネル4.1のプロセススケジューラ(ドラフト)

はじめに

本記事は昔書いたlinuxカーネル4.1のプロセススケジューラの実装について途中まで書いたけど諸事情により二年くらい放置していたドラフトです。死蔵するのももったいないので公開しておきます。今現在のカーネルに比べてずいぶんと変わっていること、未稿の部分がかなりあること、誤字脱字や「てにをは」は気にしていないこと、などにご注意ください。

このドキュメントを積極的に更新する予定は(少なくともこの場では)いまのところありません。

プロセススケジューラ

ある瞬間にCPU1で動作できる処理は1つだけです。この限りあるCPU資源をシステムに存在する プロセス間で分配するのがプロセススケジューラです。プロセススケジューラは大きく分けて 次のことをします。

  • 全プロセスの間で平等にCPUを分配する
  • スループットの最大化
  • レイテンシ(応答時間、ターンアラウンドタイム)の最短化

個々のコアのことであり、かつ、ハイパースレッドが有効化されていれば個々のハイパースレッドの ことです。

まずは簡単のため、1CPUの場合に絞って記載します。その後マルチプロセッサの場合について記載します。

1CPUの場合

プロセススケジューラはユーザに対して複数のプロセスが同時並列的に動作しているように見せかけます。 それには、複数の動作可能なプロセッサを交互に動かす時分割(タイムシェアリング)という仕組みを用います。 たとえば2つの実行可能なプロセスp0, p1が同時に存在している場合、CPUの上で動作するプロセスは次の ように遷移します。

f:id:satoru_takeuchi:20200329055139j:plain

とくにnice値によって優先度に差をつけていない場合はp0, p1に対してCPU時間を均等に割り当てます2。 このp0, p1を順番に動作させることをラウンドロビン形式と呼びます。

具体的にはそれぞれのプロセスは、たとえば 10 ms というレイテンシと呼ばれる期間を 2 等分した 10/2 = 5 ms という期間だけ 一度に動作できます。動作中の全てのプロセスがレイテンシに定められた期間に一度は必ず CPU 時間を使える ためにこの名前がついています。

実行可能なプロセスが3つ以上になっても話は同じです。

f:id:satoru_takeuchi:20200329055152j:plain

この場合は各プロセスは1回あたり 10 / 3 ~= 3.3 ms という期間 CPU を使えます。

ここで min_guranurarity について書く

プロセスは常にCPU時間を使おうとしているわけではありません。write(2)の延長でストレージのI/O待ちを している時や、sleep(3)によって自ら待ちに入るような場合もあります。次に示すのはCPU上で唯一動作可能な p0というプロセスが1秒間動作した後にスリープした後に再び起床して動き出すという図です。

p0 -> アイドルプロセス ... というような図

p0が動作していない間は、より正確に言うと、CPU上に動作可能プロセスが存在していない場合は、スケジューラが CPU上でアイドルプロセスという特殊なプロセスを動作させます。アイドルプロセスの最も単純な実装は、無限ループに よってCPU資源を消費し続けるというものです。しかし、通常は1つ以上のプロセスが動作可能になるまでCPUの電力消費を 極力抑えた状態待つような動作をします。

スリープしていたプロセスが起床した場合はどうなるでしょうか。次に示すのはp0, p1がCPU上で動作している ときに、p2が新たに起床して動作可能になった図です。

f:id:satoru_takeuchi:20200329055208j:plain

ここではp2の起床タイミングがわかりやすかったですが、もちろん、より複雑な場合もあります。 そのようなパターンについては後述します。起床してきたプロセスは通常早く動きたいので、 優先的に動作させる仕組みがあります。これについても詳細は後述します。

これまでは、時系列に沿ってCPU上でどのような処理が動作しているかという観点で見てきましたが、それに加えて 各プロセスが時系列に沿ってどのような状態になるかを見てみましょう。

f:id:satoru_takeuchi:20200329055217j:plain

複数CPUの場合

複数CPUの場合、ある瞬間にCPU上で同時に動作できるプロセスの数がCPU数に応じて増えます。 2CPUなら2個、10CPUなら10のプロセスが同時に動作できます。例えば2CPUシステムで動作可能プロセスが 2つ存在する場合は次のようになります。

f:id:satoru_takeuchi:20200329055228j:plain

2CPUで4プロセスp0〜p3が同時に実行可能であれば、図の場合と似た、次のような遷移をします。 次に図を示します。

f:id:satoru_takeuchi:20200329055240j:plain

では、どのプロセスがどのCPU上で動作するかはどのように決まるのでしょうか。実はこれもプロセス スケジューラの役割です。プロセススケジューラは、上述のように1CPU内で複数プロセスにCPU時間を 平等に割り当てる機能に加えて、CPU間で均等にプロセスの負荷を分散する機能もあります。この機能の ことをロードバランサやグローバルスケジューラと呼びます(本書では前者の表記をします)。

次に示すのは、2CPUシステムにおいてCPU0上で唯一のプロセスp0が動作している状態から、スリープしていたp1, p2, p3 がそれぞれ時間差で起床する図です。

f:id:satoru_takeuchi:20200329055254j:plain

複数CPUの場合はレイテンシの値が次の式に従って増加します。

レイテンシ = 1 + <1CPU時のレイテンシ * log2(<CPU数>)>

のちほどロードバランサの節で詳しく述べますが、あるCPU上でプロセスが実行待ちのときに他にアイドルCPUがあれば、そのプロセスはアイドルCPU上に移動して即座に実行開始できます。それに加えて、CPU数が多いほどアイドルCPUが存在する可能性も高まります。このため、CPU数が増加するとユーザの体感レイテンシはスケジューラが定めた体感レイテンシよりも短くなります。このため、上記の式によってレイテンシの値を決めることによって、CPU数が多いときにユーザの体感レイテンシを損なうことなくスループット性能を向上させられます。

nice値と優先度

これまでプロセススケジューラは動作可能なプロセスに平等にCPU時間を割り当てると言ってきましたが、 それには例外があります。ユーザから見て重要なプロセスには優先的にCPU時間を割当てたいときがあります。 このようなときには nice システムコールやnice コマンド、renice コマンドなどを使います。 nice 値は-19から20の値が存在し、ややこしいのですが-19が最高優先度でデフォルトが0,最低優先度が20です3

nice値が変化することによってレイテンシは変化しませんが、nice値の低い(優先度の高い)プロセスは nice値の高い(優先度が低い)プロセスよりもCPU時間を多くの比率だけもらえます。

スケジューリングポリシー

スケジュールするにあたって、優先度以外にももう一つ、プロセススケジューリングの挙動を変更する スケジューリングポリシーという要因があります。これには主に次のような種類があります。

  • SCHED_OTHER(デフォルト)
  • SCHED_FIFO
  • SCHED_RR

SCHED_OTHERは本章でこれまでに述べてきたような動きをします。

SCHED_FIFO はリアルタイム性の強いプロセス、たとえば定期的に起床してシステムの生存確認を するようなハートビート用プロセスなどに用います4。1つでも実行可能なSCHED_FIFO プロセス が 存在すると、当該プロセスがブロックするまで SCHED_OTHER プロセスは動作できません。実行可能な SCHED_FIFOプロセスが複数存在する場合は、ブロックするか、あるいはsched_yield()によって自発的に CPUを明け渡さなければ次のプロセスにCPU時間を明け渡しません。

ことを保証できるわけではないのでロボット制御のような処理には適しません。

SCHED_RR は、ほとんどSCHED_FIFOと同じですが、1 つだけ違いがあります。SCHED_RR プロセスが 複数存在する場合は 100 ms ごとにラウンドロビン形式でCPU実行権がプロセス間で遷移します。

スケジューリングポリシーは他にも次のようなものがありますが、これらについては重要度が低いため、本書では触れません。

  • SCHED_BATCH
  • SCHED_DEADLINE
  • SCHED_IDLE

コアスケジューラの実装

モジュール構造

プロセススケジューラには前述のスケジューリングポリシーに対応する様々なスケジューリングアルゴリズムが存在します。具体的には次のように、1つないし複数のスケジューリングポリシーに対して、スケジューリングクラスと呼ばれるstruct sched_class構造体によってアルゴリズムが分かれています。

スケジューリングポリシー スケジューリングクラス
SCHED_OTHER, SCHED_BATCH, SCHED_IDLE fair_sched_class
SCHED_FIFO, SCHED_RR rt_sched_class
SCHED_DEADLINE dl_sched_class

これ以外に、例外的にアイドルプロセスに対してはidle_sched_classという特別なスケジューリングクラスが割り当てられています。

プロセススケジューラは、あらゆるスケジューリングクラスに共通するコア部分のコードが、それぞれ別コードに まとめられているスケジューリングクラスを呼び出すようなモジュール構造なっています。これによって、コア部分の コードにif文やswitch文などによって各スケジューリングポリシーのコードを書く場合に比べて、ソースの見通しが よくなると共に、将来的に新しいスケジューリングクラスの追加が楽になっています。

プロセススケジューラのコードのうち、ソース上では次のような構成になっています。

kernel/sched
+--- core.c: プロセススケジューリングのコア部分コード。ここを起点に他のファイル内のコードを呼び出す
+--- fair.c: スケジューリングポリシー SCHED_OTHER, SCHED_BATCH, SCHED_IDLE に関するコード
+--- rt.c: スケジューリングポリシー SCHED_FIFO, SCHED_RR に関するコード
+--- idle.c: アイドルプロセス用の特殊なスケジューリングクラス(SCHED_IDLEとは無関係)に関するコード
+--- idle.c: アイドルプロセスに関するコード
+--- wait.c: プロセスの実行待ちに関するコード

データ構造

代表的なデータ構造は次の通りです。

struct task_struct: 個々のプロセス、スレッドを表します。

フィールド名 意味
state プロセス管理の章で述べたスレッドの実行状態
policy スケジューリングポリシー
prio 優先度(後述)
on_rq スレッドがランキューに乗っていれば1以上(詳細は後述)。乗っていなければ0
on_cpu スレッドがCPU上で実行中なら1(このときstateは必ずTASK_RUNNING)、そうでなければ0

Linuxカーネルにおいてはプロセス内の個々のスレッドに対して1つの struct task_struct を持ちます。 Linuxのプロセススケジューラのスケジューリング単位はプロセスではなくスレッドです。例えば あるプロセスが5個のスレッドを持つ場合、Linuxカーネル内では5つのスレッドそれぞれに対して1つづつ、task_structが存在します。

struct rq: 各CPU上で実行可能になっているスレッドの一覧を管理するデータ構造。現在CPU上で実行中のカレントスレッドの次以降にスケジュールされる順に並んでいる優先度付きキュー構造をしている。CPU毎に存在する。

フィールド名 意味
nr_running CPU上で動作中、あるいは動作待ちのスレッドの数
clock スケジューラの処理で現在時刻として使用する値。単位はナノ秒。現在時刻を知るために毎回ハードアクセスするとコストがかかりすぎるので、ここにキャッシュしている
dl dl_sched_classに属するタスクが繋がるランキュー
rt rt_sched_classに属するタスクが繋がるランキュー
cfs fair_sched_classに属するタスクが繋がるランキュー

struct sched_class: 各スケジューリングクラスに対応。プロセススケジューラの処理中に呼び出されるスケジューリングクラス固有のコールバックのリスト

フィールド名 意味
enqueue_task スレッドがTASK_RUNNINGになったときに、スレッドをランキューに挿入する
dequeue_task スレッドがTASK_RUNNINGでなくなったときに、スレッドをランキューから外す
check_preempt_curr 指定したタスクが現在実行中のスレッドにプリエンプションできるかどうかを判定する。内部でプリエンプションが成功すれば後述のresched_curr()を呼ぶ必要がある
pick_next_task ランキューから次にCPU上で実行するスレッドを選択する。内部で必ずput_prev_taskハンドラを呼ぶ必要がある
put_prev_task 現在CPU上で実行中のスレッドをランキューに戻す
task_tick タイムスライス切れを監視するために定期的に発生するタイマー割り込みの処理中に必要な処理
task_waking スレッドが起床中に必要な処理
task_woken スレッドが起床し終えた時に必要な処理
select_task_rq 後述のロードバランス用あるスレッドについて、所属しているCPUより負荷の高いCPUを探す
migrate_task_rq 後述のロードバランス用。スレッドが現在所属するCPUから別のCPUに移動する直前に呼ばれる

タイムスライス切れの監視

スケジューラはcurrentのタイムスライス切れを次のようなタイミングで監視しています。

  • タイマーサブシステム定期的5に発生させるタイマー割り込みの延長。精度はカーネルビルドの設定によるが最高でも1ミリ秒。処理の入り口はscheduler_tick()
  • プロセススケジューラが必要に応じて(後述)発生させる高精度タイマーの延長。 精度はナノ秒。処理の入り口はhrtick()。

これ以外にもスケジューラのコードの中では、ランキュー操作など、随所でupdate_rq_clock()を呼び出すことによって、currentのタイムスライス切れを細かく監視しています。

上記2つの関数は次のようなことをします。

  1. update_rq_clock(): rq->clockを更新
  2. current->sched_class->task_tick()ハンドラを呼ぶ。このハンドラは、タイムスライスが切れていたら、currentを切り替えるようにスケジューラに通知する
  3. (scheduler_tick()のみ) trigger_load_balance(): 必要ならばロードバランサを起動(後述)

プロセス切り替え

カーネルの中でスケジューリングが必要になったときにはschedule()が呼ばれます。この関数は次のような契機で呼ばれます。

  • 現在CPUで実行中のスレッドが、IO待ちやカーネル内の資源待ちによってブロックされた
  • タスク生成時/起床時のpreemptionやタイムスライス切れなどの理由によって、起床時のカーネル内の別の処理からスケジューリング要求があった(need_resched()がtrueになった)

この関数の中では、スケジューリング要求がある限り(need_resched()がtrueである限り)、スケジューリング処理の本体であるschedule()を呼び出し続けます。なぜこういうことをするかというと、schedule()の実行中にカーネル内の別の処理から再度スケジューリング要求が来ることがあるからです。再度のスケジュール要求を後回しにせずに、ここで処理することによって、スケジュール処理の実行タイミングが遅れないようにしています。

スケジューリング処理の本体である__schedule()について述べます。

__schedule():

rcu_note_context_switch: RCUサブシステムに、pが所属するCPUコンテキストスイッチ処理に入ったことを知らせる(RCUについては別の章で述べる)
sched_feat(HRTICK)は通常falseを返すのでhrtick_clear()は気にしなくて良い
if カレントスレッドはスリープ状態?(prev->stateがTASK_RUNNING(=0)以外)
  if シグナルがpending?
    カレントスレッドを再度実行可能状態にする -> 4に進む
  else
    deactivate_task(): カレントスレッドをランキューから外す
      dequeue_task() -> カレントスレッド->sched_class->dequeue_task()を(登録されていれば)
pick_next_task(): 次に動作するスレッド(next)を選ぶ
clear_tsk_need_resched(): スケジューリングの必要が必要なNEED_RESCHEDフラグを落とす
if 次に動作するタスクがカレントスレッドと同じ(prev == nextが同じ)?
  context_switch(): カレントスレッドprevからnextに切り返る => 終わり

スケジューリングクラスごとにキューを持つことを図示する

pick_next_task(): 次に動作するスレッド(next)を選ぶ

通常ほぼ全てのスレッドのスケジューリングクラスはデフォルトのfair_sched_classであることを利用した最適化処理。次に動かすスレッドの候補となる、現在ランキューに存在する全スレッドのスケジューリングクラスがfair_sched_classなら、fair_sched_class->pick_next_taskを呼び出して次に動かすスレッドを決める

if 次に動かすスレッドが見つかった?
  当該タスクを次に動かすスレッドとして返して、終了
  idle_sched_class.pick_next_task()を呼び出して、アイドルプロセスを次に動かすスレッドとして返して、終了
優先度の高いスケジューリングクラスのキューから順番にclass->pick_next_task()を呼び出して、次に動作させるスレッドを決める。pick_next_taskは、当該クラス用のランキューが空ならば、NULLを返す。この場合は次に優先度が高いスケジューリングクラスのpick_next_task()を呼ぶ。最低優先度であるidle_sched_classのpick_next_task()は、このスケジューリングクラスに属する唯一のスレッドであるアイドルプロセスを必ず返します

スケジューリングクラスの優先度 1. stop_sched_class: カーネル内の 2. dl_sched_class: SCHED_DEADLINE用 3. rt_sched_class: SCHED_RR|SCHED_FIFO用 4. fair_sched_class: SCHED_OTHER|SCHED_IDLE|SCHED_BATCHに対応 5. idle_sched_class: アイドルプロセス用

context_switch()

parepare_task_switch(): コンテキストスイッチ前に必要な各種サブシステム用、及びアーキテクチャ用の処理
arch_start_context_switch(): 準仮想化環境においてコンテキストスイッチ前に必要な処理
メモリ空間(mm)の切り替え。次に動くスレッドがカーネルスレッドなら(mm == NULL)、カレントスレッドのメモリ空間をそのまま使う
switch_to(): アーキテクチャ固有の、実際にコンテキストスイッチをする処理。

switch_to()

このマクロそのものと内部で呼び出す__switch_to()関数を用いて、CPUのレジスタの値を現在のprevのものから、以前にnextのthread_infoに退避しておいた next のものに順次入れ替えます。その過程で、現在のレジスタの値をprevのthread_info に退避します。この関数から復帰するときには、nextが動作中のプロセスに切り替わります。

レジスタの値が入れ替わる様子の概念図

スレッドを待ち状態にする処理

スレッドを待ち状態にするには待ちキューという仕組みを使います。待ちキューを使用する流れは次の通りです。

prepare_to_wait(): 実行中のスレッドを待ちキューに登録した上で、当該スレッドを待ち状態にする(対応するstruct task_structのstateをTASK_INTERRUPTIBLE|TASK_UNINTERRUPTIBLEにする)。
schedule()によって、スレッドからCPUを手放させて、ランキューから外す。ここで一旦スレッドは待ち状態になる。

(別のスレッドから非同期に呼び出される) wake_up(): 別のスレッドによって待ちキューから外され、実行可能状態になる
finish_wait()によって、待ち状態終了後の後処理をする。

データ構造

wait_queue_head_t: 所定のイベントを待つスレッドを繋げるためのキュー

フィールド名 意味
task_list キューに繋がっているスレッドのリスト。後述のwait_queue_tを介してスレッドを繋げる

wait_queue_t: 待ちキューに繋がるスレッドを表す

フィールド名 意味
task_list wait_queue_head_t->task_listに繋がる
func 待ちが状態解けた際に呼ばれる。デフォルトはautoremove_wake_function()
private func()を呼び出す時に引数として渡される。デフォルトはcurrent

prepare_to_wait()

void
prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)

待ちキューqに、currentに対応するwaitを繋ぎ、current->stateをstateに設定します。

wake_up(q)

待ちキューqで待っているスレッドのうち、キューの先頭に繋がっているスレッドに対応するwait_queue_tのfunc()ハンドラを呼び出して、qから当該スレッドを登録解除します。

wake_up()には、指定した数のスレッドを起床させるwake_up_nr()やwake_up_all()などの多くの変種があります。

autoremove_wake_function()

int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
default_wake_function(): 後述するtry_to_wake_up()を呼び出して、スレッドを起床させる
waitを待ちキューから外す

finish_wait()

void finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
current->stateをTASK_RUNNINGする。デフォルトではここに来る前にtry_to_wake_up()の延長で既にTASK_RUNNINGになっている。
waitを待ちキューqから外す。デフォルトではここに来る前にautoremove_wake_functionの中で既にqから外れているので何もしない。

スレッドを起床させる処理

待ち状態のスレッドを起床させる処理の本体がtry_to_wake_up()です。

static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)

この関数は、スレッドがスリープしていれば、起床させてランキューに挿入します。成功すれば1を、失敗すれば0を返します。引数の意味は次の通りです。

  • p: 起床させようとするスレッド
  • state: p->stateがこの引数で指定したマスクに入っていたときのみ起床させる
  • wake_flags: この関数の挙動を制御するための種々のフラグ。後述

処理の流れは次の通りです。

f:id:satoru_takeuchi:20200329055317j:plain

1. p->state & stateが真なら先に進む。そうでなければ終了
if pはスリープ状態だがまだランキュー上にいるか?
  ttwu_remote(): pを実行可能状態にする。失敗すれば2.2へ
    ttwu_do_wakeup(): pを実行可能状態にする
      pのCPU上で実行中のスレッドへのpreemptを試行(check_preempt_curr())
      pを実行可能状態にする(p->stateをTASK_RUNNINGにする)
      p->sched_class->task_woken()ハンドラを(登録されていれば)呼ぶ
else
 p->stateをTASK_WAKINGにする
 p->sched_class->task_waking()ハンドラを(登録されていれば)呼ぶ
 必要ならばロードバランスによってpを別のCPUに移動させる
 ttwu_queue()を呼んでタスクを起床させる
   ttwu_do_active(): 内部でp>sched_class->enqueue_task()ハンドラを呼ぶことによって、pが所属するcpuのランキューに挿入して実行可能状態にする。
     ttwu_activate: pを、pが所属するcpuのランキューに挿入する
     ttwu_do_wakeup():

プリエンプション

スレッドがfork()によって生成されたときや、スリープ状態から起床した際などには、実際にCPUを使えるようになるまでランキュー内で待機します。ただし、所定の条件を満たせば、CPU上で現在動作中のスレッドに取って代わって、当該スレッドが即座に動作開始できることがあります。これをプリエンプションと呼びます。

check_preempt_curr()

この関数は、指定したスレッドから、当該スレッドが所属するCPU上で現在実行中のスレッドへのプリエンプショを試行します。この関数の挙動は次の通りです。

条件 挙動
pのスケジューリングクラスとpが所属するCPU上のカレントスレッドのそれが同じ 当該スケジューリングクラスのcheck_preempt_curr()ハンドラを呼び出す。ハンドラ内ではプリエンプションが成功すればresched_curr()を呼ぶ
前者よりも後者のほうが優先度が高い 必ずプリエンプションしない
前者のほうが後者よりも優先度が高い 必ずプリエンプションする。resched_curr()を呼び出す

resched_curr()

if 処理を実行中のCPUは、プリエンプションするスレッドが属するCPUと同じか?
  NEED_RESCHEDを立てる
else
  NEED_RESCHEDを立てる
  if アイドルプロセスがNEED_RESCHEDを監視しているか?
    exit
   else
     プリエンプションしたスレッドにIPIを飛ばしてNEED_RESCHEDが立ったことを通知

プリエンプトした後にコンテキストスイッチが起きるタイミング

次のようなタイミングで発生します。

  • システムコールや割り込みからの復帰時
  • カーネル処理の中でschedule()やcond_resched()によって明にスケジュール要求が出た時

cond_resched()は、NEED_RESCHEDが立っている場合のみschedule()を呼びます

fairクラスの実装

データ構造

ランキュー(struct cfs_rq)

フィールド名 意味
load ロードバランスに使用する、このランキューの負荷
nr_running このランキュー上のTASK_RUNNINGなスレッドの数
tasks_timeline fair_sched_classを使ってスケジューリングする実行可能スレッドが繋がるランキュー本体(データ構造は赤黒木)
rb_leftmost ランキュー内から次回選択されるスレッドに対応するノード
curr 当該ランキューが担当するCPUで現在実行中のスレッド
min_vruntime このランキューに属する全スレッドの中での最小のvruntime

スケジューリング対象(sched_entitry)

CFSにおけるスケジューリング対象です。別の章で説明するcgropuについて考えなければtask_structと1対1対応していると考えてもらっていいです。

フィールド名 意味
load ロードバランスに使用する、entityが持つ負荷(後述)
vruntime ナノ秒単位の仮想的な実行時間(後述)
cfs_rq 自分が所属するCFSランキュー

vruntime

CFSで管理されるスレッド(正確にはそれに対応するsched_entity)は、上記のように各自vruntimeという値を持っています。この値は、スレッドの仮想的な累計実行時間を指しており、次のような特徴があります。

  • 各スレッドのvruntimeは、レイテンシターゲットの間にスレッドが与えられたタイムスライスだけ動作すると、レイテンシの長さだけ動作したように増加する値である。
  • 上記の理由により、レイテンシの倍数の実時間において、ランキュー上の全てのスレッドのvruntimeは等しい
  • vruntimeは、当該スレッドがCPU上で動作している間に、スケジューラ処理の各所において、随時現在時刻に更新される
  • CFSはvruntimeが小さいスレッドから順番にCPUを割り当てる

以下に具体例を出します。

  • latencyは20ミリ秒
  • T0,T1という2つのスレッドが存在する(つまりタイムスライスは"20/2=10"ミリ秒)
  • T0,T1は常に実行可能状態(スリープしない)
  • T0,T1の実行時間はt0,t1
  • T0,T1のvruntimeはv0,v1。初期値はそれぞれ0ミリ秒

この場合、実時間の経過と共に、2つのスレッドの実実行時間及びvruntimeは以下の表のように変化します。表の中の数値の単位はすべてミリ秒です。 v0,v1が同じ値の場合はどちらが先に動いてもいいのですが、ここでは仮にt0が先に動くものとします。

実時間 t0 t1 v0 v1
0 0 0 0 0
10 10 0 20 0
20 10 10 20 20
30 20 10 40 20
40 20 20 40 40

ここで、latencyの倍数の時間において(0,20,40ミリ秒時点)は次のことが言えます。

  • それぞれのタスクが平等に動作している(t0,t1が等しい)
  • vruntime(v0,v1)は現在時刻に等しい
  • vruntimeはタイムスライスを使い切った段階で、latencyの倍数になるように調整されている。言い方を変えると、与えられたタイムスライスだけ動作すると、latencyだけ動いたように調整される。

t1が実時間でいう0ミリ秒から20ミリ秒まで待ち状態だった、あるいは20ミリ秒時点で新規生成された場合はどうなるでしょうか。この場合は、当該スレッドがランキューに挿入された時点で、スレッドのvruntimeがランキューのmin_vruntimeまで切り上げられます。こうしておかないと、このようなスレッドが起床/生成直後に大量にCPUを独占してしまいます。具体的には次のような挙動になります。

実時間 v0 v1
0 0 0|0|0
10 10 0|10|0
20 20 0|20|20| <- ここでT1が起床
30 30 00|40|20
40 30 10|40|40

この場合も、latencyの倍数の時間において(0,20,40ミリ秒時点)、次のことが言えます。

  • 1回のレイテンシの範囲では全スレッドが実時間的に平等に動作している、および、
  • vruntimeが全て実時間に等しい値になっている

上述したCFSのスケジューリングの仕組みをそのまま使うと、実行可能なタスクが大量に存在する場合に、コンテキスト スイッチによるオーバーヘッドが無制限に大きくなってしまいます。例えば latencyが100ミリ秒でスレッドが1,000個あった場合、各スレッドは一度に"100/1,000=0.1"ミリ秒、つまり100マイクロ秒しか 動けません。仮にコンテキストスイッチのコストを10マイクロ秒とすると(もちろん実際の値はシステムによって異なります)、 コンテキストスイッチだけでCPUリソースの10%を食い潰してしまいます。これを防ぐためにmin_granularityという値が存在します。 "latency/実行可能タスク数 < min_granularity"の場合、実際のlatencyも"min_granularity*スレッド数"になる(sysctlパラメタの値は変わらない)と共に、 各スレッドのタイムスライスはmin_granularityになります。

スリープ状態から起床したスレッドは、動作直後に短時間だけCPUを使ってまたスリープするという傾向にあります。それが顕著なのが shellなどの対話型のスレッドです。システムの応答性を上げるためには、これらスレッドの応答性を上げる必要があります。そのためにCFSは、 スリープ状態から起床したスレッドのvruntimeが現在実行中のスレッドのそれより少なければ、前者は後者をpreemptできるという仕組みになっています。

ただし、この仕組みをそのまま使ってしまうと、スリープと起床を繰り返すようなスレッドが大量に存在する場合に、preemptによるコンテキストスイッチが 大量に発生すると共に、そのオーバーヘッドも大きくなってしまいます。本パラメタはそれを防ぐために存在します。latencyで定められた期間の中で、 起床したスレッドの実行時間が現在実行中のタスクのそれよりもwakeup_granularityだけ少ない場合のみpreemptできるようになっています。

vruntimeの型は符号なし64ビット型(u64)かつ単位がナノ秒なので、(264)/(109)/60/60/24/365~=586年後にオーバーフローします。これだけあればまず問題ありません、かつ、vruntimeの各種計算はオーバーフローを考慮したものになっています。

fair_sched_classのハンドラ

スケジューラのコアコードから呼び出されるfair_sched_classのハンドラの定義を次に述べます。

enqueue_task_fair(fair_sched_class.enqueue_task)

static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)

cgroupが無い場合は、2つあるfor_each_sched_entity()のループは、一つ目のループが冒頭で"&p->se"に設定したseに対して一回呼び出されるだけで、2つ目のループは実行しません。

enqueue_entity(): 
  update_curr():
    currentが最後にCPU時間を得てから現在までの時間をvruntimeの単位に変換したもの(calc_delta_fair(delta_exec,curr))をcurrentのvruntimeに加算する
    update_min_vruntime(): cfs_rq->min_vruntimeを、currentおよびcfs_rqに入っているスレッドすべての中の最小値に設定
  if (スレッド起床時のenqueueか)
    place_entity: pのvruntimeを更新。
  if (スレッドがカレントスレッドではない)
    __enqueue_entity: p->seをcfs_rq->tasks_timelineキューに挿入
  1. hrtick_update(): currentのスケジューリングクラスがfair_sched_classであれば、スレッドpのランキューrqへの更新に伴うcurrentのタイムスライス変化に応じて、高精度タイマーの起動時期を早める。

dequeue_task_fair(fair_sched_class.dequeue_task)

check_preempt_wakeup(fair_sched_class.chech_preempt_curr)

update_curr()
if (wakeup_preempt_entity: current->se->vruntime > sched_wakeup_granularityをvruntimeに変換した値(calc_delta_fair(sysctl_sched_wakeup_granularity)))
  プリエンプション成功。resched_curr()を呼ぶ

pick_next_task_fair(fair_sched_class.pick_next_task)

update_curr():
pick_next_entity(): ランキューから次に動作させるスレッドを選択する
put_prev_entity(): prevをランキューに戻す
set_next_entity(): pick_next_entity()で選択したタスクをcurrentにする
hrtick_start_fair(): currentのタイムスライスを計算して、その時刻に高精度タイマーが動作させるよう設定する
put_prev_task(): 内部でprev->sched_class->put_prev_task()ハンドラを呼び出す

put_prev_task_fair(fair_sched_class.put_prev_task)

if (prevは実行可能状態)
  update_curr()
  __enqueue_entity(): ランキューにprevを挿入
  update_entity_load_avg: ロードバランスに用いるprevの負荷の再計算

task_tick_fair(fair_sched_class.task_tick

entity_tick()
  update_curr()
  update_entity_load_avg()
  if (hrtick()から呼ばれた)
    resched_curr()
    exit
  if current以外にRUNNABLEなタスクがいる)
    check_preempt_tick: タイムスライス切れによるプリエンプションを試行
      if (currentのタイムスライスが切れた || currentのタイムスライスがmin_guranularity以上、かつ、vruntimeがランキュー先頭のタスクのvruntime以上)
        resched_curr()

select_task_rq_fair(fair_sched_class.select_task_rq)

migrate_task_rq_fair(fair_sched_class.migrate_task_rq)

rtクラスの実装

データ構造

ランキュー(struct rt_rq)

エンティティ(sched_rt_entitry)

クラス関数

idle_sched_classのハンドラ

dequeue_task_idle(idle_sched_class,dequeue_task)

アイドルプロセスが待ち状態になることはありえないので、警告メッセージ及びスタックトレースを出す。

check_preempt_curr_idle(idle_sched_class.check_preempt_curr)

resched_curr()

アイドルプロセスは他のあらゆるスレッドより優先度が低いので、必ずプリエンプションが成功する

pick_next_task_idle(idle_sched_class.pick_next_task)

put_prev_task()

仕様に定められていることをするだけ

task_tick_idle(idle_sched_class.task_tick)

アイドルプロセスにはタイムスライスの概念が無いため、何もしない

select_task_rq_idle(idle_sched_class.select_task_rq)

TBD

アイドルプロセスの処理

cpu_idle_loop():

while (true)
  __current_set_polling(): スケジュール要求をidleがポーリングする設定にする
  while (!need_resched())
    if (アイドルプロセスがポーリングモードか(上記のスケジュール要求についてのポーリングとは別物)
      cpu_idle_poll()
    else
      cpuidle_idle_call()
  __current_clr_polling(): スケジュール要求をidleがポーリングする設定を解除する

大きく分けて2つの処理のどちらかを実行している。どちらを呼ぶかは設定可能

cpuidle_idle_call(): スリープ状態で他のタスクが起床するのを待つ。消費電力小

ocpuidle_get_cpu_driver(): 目的別に定義されているアイドル処理のドライバを選択する
if (スケジュール要求がある(NEED_RESCHEDが立っている)
  exit
CPUをどのようなstateに落とすか設定する(x86でいうとCステート)
if (current_clr_poloing_and_test()
  スケジュール要求をpollingする設定になっており、かつ、スケジュール要求が来ていれば、
cpuidle_enter(): CPUを、上記処理で設定したstateに設定してスリープさせる
__current_set_polling():

cpu_idle_poll(): スリープ状態に入らないまま他のタスクが起床するのを待つ。消費電力大

while (!need_resched())
  cpu_relax();

概要

CPU間の負荷が偏っていると、同じ優先度のスレッドが動作できる量が減って不平等が発生します。 これを避けるために、後述する様々な契機でタスクをCPU間移動させることによって、CPU間の 負荷分散をします。

どのような契機でどこのCPUに移動できるかは struct sched_domain という構造体の ツリーによって表現されます。

フィールド名 意味
parent ドメイン
child ドメイン
groups ドメイン内に所属するグループ(後述)のリスト
flags どの契機でタスクをCPU間移動させるかを示す
balance_interval 定期てきに動作するロードバランス処理の動作周期(可変)
min_interval 上記処理の最短動作周期
max_interval 上記処理の最長動作周期

sched_domainには次のような種類があります。

  • NUMAノード間のロードバランスをするもの
  • NUMAノード内のCPUソケット間でロードバランスするもの
  • CPUソケット内のコア間でロードバランスするもの
  • コア内のスレッド間でロードバランスするもの

例えば非NUMA環境で2ソケット、2コア,ハイパースレッド無しの場合は次のような構造になります。

f:id:satoru_takeuchi:20200329055338j:plain

それぞれのドメインについて、flagsフィールド内の各フラグに示される契機でロードバランスが 発生します。

フラグ 意味
SD_LOAD_BALANCE 定期的なロードバランス処理を動かす
SD_BALANCE_NEWIDLE CPUがアイドルになる瞬間
SD_BALANCE_EXEC プロセスのexec時
SD_BALANCE_FORK プロセスのfork時
SD_BALANCE_WAKE プロセスの起床時

同一コア内のハイパースレッド間のスレッドの移動はコストが小さいため、フラグはたくさん立っています。 その一方NUMA ノード間のスレッドの移動は、移動後にスレッドはリモートメモリを使わなくてはならなくなるなど、 コストが高いので、少ししかフラグが立っていません。 # 後でもっと具体的に書く

各CPUのスケジューラドメインを管理するために、struct rqには次のようなフィールドがあります。

struct rq:

フィールド名 意味
rd rootスケジューラドメイン
sd このランキューが属するスケジューラドメイン(後述)

定期的に動作するロードバランサ

softirq処理の延長で、定期的にドメイン内のロードバランスをする処理が動作します。 基本的には下層のドメインのロードバランス処理のほうが、上層のドメインのロードバランス処理より 頻繁に動作します。

ここでドメイン内のグループ(struct sched_group)という概念が登場します。

フィールド名 意味
next 同じドメイン内のグループを接続する単方向循環リスト
cpumask グループに属するCPUの一覧を示すビットマスク

たとえば、最近のPCやスマートフォンでよくある、非NUMA, 1CPU、4コア、1スレッドの環境で、4つのCPU(0-3)という構成では、次のようなドメイン/グループの構造ができます。

f:id:satoru_takeuchi:20200329055353j:plain

2ノード、ノードあたり2CPU、2コア、2スレッドというような高価サーバマシンでは次のようになります(最近の実際のサーバマシン用CPUは通常もっとコア数が多いですが)。

f:id:satoru_takeuchi:20200329055404j:plain

このドメイン内をバランスする処理は、

  1. ドメイン内の一番負荷が高いグループを見つける
  2. ドメイン内の一番負荷が低いグループを見つける
  3. 一番負荷が高いグループから一番低いグループに1つないし複数のスレッドを移動させる

ここでいう負荷とは、nice値などによって色々修正されますが、基本的にはタスクの数だと思って下さい。 なお、グループ間の負荷が 1 スレッド分程度であれば、移動はさせません。なぜかというと、この程度の 負荷の差で移動させると、負荷の差が小さいような場合は頻繁にスレッドがCPU間を移動してコストが高く なってしまうからです。このため、ある程度のしきい値を超える負荷の差が無いと移動はさせません。

deadlineクラスの実装

データ構造

ランキュー(struct dl_rq)

エンティティ(sched_dl_entitry)

クラス関数

スケジューリング関連システムコール

sched_getattr, sched_setattr

nice

(affinityの概念も) sched_getaffinity, sched_setaffinity

sched_yield

sched_rr_get_interval


  1. ここでいうCPUとは論理CPUのことですマルチコアであれば(最近はほとんどそうですが)

  2. 正確にはこの間に定期的にカーネルが動作しますが、煩雑になるのでここでは省略します。詳細は後述。

  3. 遠慮して人にCPU時間を譲ってくれる「良い奴」だからniceという名前が付いているようです

  4. リアルタイムという名前がついていますが確実に期待した時刻に動作して、デッドライン内に処理が完了する

  5. 現在は省電力の観点から、時刻の更新が必要無いとわかっている時はタイマー割り込みを一時的に停止します