Linuxカーネルの理解:スケジューラ
Understanding the Linux Kernel: The Scheduler (internals-for-interns.com)
要約
この記事は、Linuxカーネルシリーズの第4弾として、Linuxカーネルのスケジューラに焦点を当てています。スケジューラの基本的な機能、タスクがCPUをいつ手放すのか、そしてEEVDFアルゴリズムがどのように次に実行するタスクを決定するのかを、Linux 7.1のコンテキストで詳しく解説しています。プロセスやスレッドがカーネル内部ではどのように扱われるか、また複数のスケジューリングクラスがどのように連携しているかについても説明しています。
全文翻訳
Linuxカーネルのスケジューラを理解する
前回の記事では、カーネルが各プロセスに独自のメモリ空間をどのように提供するかを説明しました。しかし、プロセスが実際に実行するために必要なのはメモリだけではありません。もう半分はCPUそのものであり、マシンには限られた数のCPUしかありませんが、通常は数百から数千もの実行したいタスクが存在します。
そのため、誰がいつ、どれくらいの時間CPUを使うかを常に決定する役割が必要です。それがスケジューラです。カーネルは、すべてのコアで数ミリ秒ごとに同じ問いを自問します。「今すぐ実行したいすべてのものの中で、次に誰を実行するか?」そして、その答えは迅速かつ公平で、コンパイルが全コアを占有している間でもテキストエディタが応答性を保てる程度に良好でなければなりません。
スケジューラには多くの可動部分があるため、一歩ずつ進めましょう。まず、スケジューラが実際に何をスケジューリングしているのか、つまりプロセスとスレッドが内部で実際には何であるかから始めます。次に、Linuxには単一のスケジューラではなく、スケジューリングクラスとしてスタックされた複数のスケジューラがあることを見ます。そこから、実行中のタスクがいつ実行を停止するのか(これは聞くより興味深い)、そしてタスクから別のタスクに切り替えるコストを見ていきます。最後に、カーネルが実際に誰を次に選ぶかを決定する方法、EEVDFと呼ばれるアルゴリズムにたどり着きます。
📌 スコープに関する注記
ここでのすべてはLinux 7.1に対するものです(スケジューラコアは
kernel/sched/にあり、主にfair.cとcore.cにあります)。そして、これは意図的な単純化です。実際のインプリメンテーションは、CPU間のロードバランシング、cgroupsを通じたグループスケジューリング、CPU帯域幅制御、NUMAアウェアネス、そして無数のエッジケースなど、はるかに多くのことを行っていますが、コアのアイデアを明確にするために省略しています。
それでは、スケジューラ自体が始まる場所から始めましょう。それは、CPUで実際にオンオフされているものです。
スケジューラが実際にスケジューリングするもの
最初の驚きはこれで、多くの混乱を解消します。カーネルは「プロセス」や「スレッド」をスケジューリングしません。それらはユーザー空間で私たちが使う言葉です。カーネルの内部では、スケジューリング可能なものはただ1種類です。それはtask_struct(include/linux/sched.h:820)であり、カーネルが実行フローの記録、CPUに乗って命令を実行できるもの一つ一つです。
あなたがプロセスと呼ぶものと、スレッドと呼ぶものは、どちらも根本的には全く同じ種類のオブジェクトです。唯一の違いは共有するものです。新しいプロセスをfork()すると、親と何も共有しない新しいtask_structが得られます。独自のメモリ、独自のファイルディスクリプタ、独自のすべてです。スレッドを作成するとき(適切なフラグを付けてclone())、も新しいtask_structが得られますが、このものはアドレス空間、開いているファイル、シグナルハンドラなどを生成したタスクと共有します。したがって、「マルチスレッドプロセス」は実際には同じメモリを指しているだけのtask_structの集まりにすぎません。
[画像: forkで作成されたプロセス(独自のメモリ、ファイル、シグナルを持つtask_struct)と、cloneで作成されたスレッド(単一のアドレス空間を共有する複数のtask_struct)を対比する図。スケジューラはすべてを単なるtask_structとして見ている]
スケジューラの立場からは、それらはどうでも関係ありません。誰が何を共有しているかを知ることも、気にかけることもありません。それはただ、実行可能なものとそうでないもののtask_structの山を見て、実行可能なものの中から選びます。CPU上で実行可能なものはすべてtask_structです。以上。
task_structは巨大で、カーネルがタスクについて知っていることのほぼすべてを保持していますが、スケジューラが気にするのはそのごく一部です。各タスクの内部には、スケジューリング状態の小さな組み込みバンドル(sched_entityと呼ばれます、include/linux/sched.h:575)があり、その巨大な構造体ではなく、その小さなバンドルこそがスケジューラが実際に推論する対象です。
vruntime、vlag、deadline、sliceといった名前の興味深い数値がそこにあります。それらの意味についてはまだ心配しないでください。それらを解き明かすことが、この記事の残りの部分のほとんどです。今のところ、その形状だけを覚えておいてください。実行可能な各タスクは、少量の会計状態を運び、スケジューラが次に誰を実行するかを決定するときに読み取る部分です。
しかし、「スケジューラ」は少し嘘です。なぜなら、スケジューラは一つではないからです。さらに進む前に、実際に誰が決定権を与えられているかを見てみましょう。
スケジューリングクラス:誰が最初に尋ねられるか
アルゴリズムに入る前に、ひねりがあります。Linuxには実際には1つのスケジューラしかありません。それは複数あり、厳格な優先順位でスタックされています。これらのスタックされたスケジューラはスケジューリングクラスと呼ばれ、それぞれが異なる種類のワークロードのための自己完結型のポリシーです。
それらが協力する方法は非常にシンプルです。CPUが何かを実行する必要があるとき、カーネルはスタックを上から下に進み、各クラスに順番に「実行可能なものはありますか?」と尋ねます。最初に「はい」と言ったクラスが勝ち、それより下のクラスは投票権さえ得られません。したがって、クラスは、それより上のすべてのクラスが何も提供できなかった場合にのみタスクを実行します。
[画像: スケジューリングクラスを、stop、deadline、rt、fair(EEVDF、ほとんどすべてが実行される場所として強調表示)、ext、idleというトップからボトムへの優先度スタックとして示す図。カーネルはスタックを下方向に歩き、各クラスに実行可能なタスクを尋ね、最初に作業があったものが勝利する]
それらのボックスには何が入っているのでしょうか?上部の3つはすべて、あるタスクに通常の作業の前に割り込む権利を与えるために存在します。一番上にはstopがあります。これはスケジューリングポリシーというよりは、カーネルがCPUで即座に緊急のタスクを実行する必要があるときに使用する「すべてを停止」レバーです。例えば、シャットダウン中のコアからタスクを移行する場合などです。その下には、deadlineがあります。これは、オーディオやロボット工学のような、厳格なタイミング要件を持つタスクを処理します。優先度を求めるのではなく保証を求めます。「このタスクは定期的にCPUを〇ミリ秒必要とする」といった具合です。そしてrtは、古典的なリアルタイム優先度です。リアルタイムタスクは好きなだけ実行でき、それより高いものだけが脇にどきます。これはレイテンシに敏感なコードには素晴らしいですが、そのようなタスクが決してスリープしない場合にマシンをフリーズさせる素晴らしい方法でもあります。
しかし、ここで重要なことがあります。通常のデスクトップやサーバーでは、これら上位3つのボックスはほとんど常に空です。これは、この記事の残りの部分で重要なもの、fairクラスにつながります。これは、あなたが実行するほぼすべてのものが実際に存在する場所です。シェル、ブラウザ、データベース、コンパイルジョブなどです。これらのタスクには特別なタイミング要求はありません。ただCPUの合理的なスライスを求めているだけで、fairクラスの仕事はそれらのスライスを公平に配分することです。上位のクラスは通常アイドル状態であるため、fairクラスがほぼ常に主導権を握っています。そのため、人々が「Linuxスケジューラ」と言うとき、彼らがほとんど常に意味するのはこのクラスです。
一番下を埋めるのは、全体像を完成させるためです。extは、スケジューリングポリシー全体をBPFプログラムとしてロードできる新しい追加機能で、カーネルを再コンパイルせずに実験するのに便利です。そしてidleは最下層で、何も実行したくない場合にのみ実行され、コアを静かにスリープさせて電力を節約する何もしないタスクです。どちらも詳しく説明しません。ここからは、すべてfairクラスについてです。
fairクラスは、威圧的な名前のアルゴリズムに基づいています。EEVDF、Earliest Eligible Virtual Deadline Firstです。名前につまずかないでください。後で一つずつ分解していきますが、かなり直感的なアイデアであることがわかります。
EEVDFがどのように選択するかに入る前に、それがいつ選択する機会を得るかを知っておくと役立ちます。実行中のタスクがCPUを手放す瞬間です。
実行中のタスクはいつ実行を停止するか?
タスクがCPUで幸せに実行されているとします。何がそれを停止させ、他のものが実行できるようにするのでしょうか?これは通常、人々が曖昧に通り過ぎる部分ですが、システム全体が実際に生きている場所です。タスクがCPUを手放す方法は、実際には2つしかありません。両方を理解することが、スケジューラを理解することのほとんどです。まず、より穏やかな方から始めましょう。
方法1:自発的にブロックする
タスクが実行を停止する最も一般的な理由は、まだ持てないものを要求することです。データがないソケットでread()を呼び出す、他の誰かが保持しているmutexを取得する、sleep()を呼び出す、条件変数で待つなど、すぐに完了できないことです。
それが起こると、ブロッキングプリミティブの奥深くで、カーネルはそのタスクの状態を「実行不可」に設定し、schedule()(kernel/sched/core.c:7273)を呼び出します。これはタスクが自発的に「今は何もすることがない、CPUを他の誰かに譲ろう」と言っているのです。スケジューラはタスクを実行キューから完全に削除し(実行不可なので考慮する意味がない)、他の誰かを選び、それに切り替えます。ブロックされたタスクは、待っていたことが発生したときに、後で実行キューに戻されます。これはウェイクアップであり、後で説明します。
これはクリーンで協力的なケースです。タスク自身がハンドオフを開始しました。しかし、すべてのタスクがそんなに丁寧なわけではありません。
方法2:プリエンプトされる
しかし、決してブロックしないタスクはどうでしょうか?数値計算を行うタイトなループ、while(1)、コアを占有するビデオエンコーダ。ブロックがCPUを手放す唯一の方法だった場合、そのタスクは永遠に実行され、他のすべてを飢えさせてしまいます。そのため、カーネルはCPUを奪うことができる必要があります。それがプリエンプションです。
ここが巧妙な部分です。プリエンプションはほとんど即時ではありません。カーネルは、命令の途中でタスクを激しく引き抜くわけではありません。代わりに、タスクをプリエンプトすべきだと判断すると、単にそのタスクにフラグを設定します。TIF_NEED_RESCHED、文字通り「このタスクはリスケジュールが必要」です(resched_curr()、kernel/sched/core.c:1212)。そして、しばらく実行を続行させます。フラグを設定するのは安価で安全です。タイマー割り込み内のような厄介な場所からタスクを実際に切り替えるのは危険なためです。フラグは単なる付箋です。「次の安全な機会にこのタスクを切り替える」というものです。
それらの安全な機会は、カーネルがフラグをチェックし、設定されていれば、実際の切り替えを行うためにschedule()を呼び出す、よく定義されたポイントです。最も一般的なのはユーザー空間への復帰です。タスクがシステムコールや割り込みの後でカーネルからコードに戻るたびに、カーネルは最初にフラグを確認します。
したがって、リズムは常に決定 → フラグ設定 → 少し実行 → 安全なポイントに到達 → 切り替えです。この遅延したフラグ駆動設計は、すべての中核です。ウェイクアップでさえタスクを直接切り替えません。それは単にタスクを実行可能にし、そのタスクがCPUに値するなら、現在実行中のタスクにフラグを設定します。実際の切り替えは、後で安全なポイントで行われます。
[画像: タスクの3つの状態(実行中(CPU上)、実行可能(実行キュー上、順番待ち)、ブロック中(スリープ中、実行キュー外))の状態遷移図。遷移ラベル付き:実行中はschedule()を呼び出してブロックする、ウェイクアップは実行可能に戻す、スケジューラはコンテキストスイッチを介して実行可能なタスクを選択する、実行中のタスクはリスケジュールフラグが安全なポイントで尊重されると実行可能に戻ってプリエンプトされる]
目的のためには、タスクは3つの主要な状態間を移動します。実行中は、自発的に何かを待つときにブロック中にドロップし、後でウェイクアップがブロック中から実行可能(順番待ち)に移動させます。実行可能からスケジューラはそれを選択して実行中に戻します。実行中のタスクは、プリエンプトされると実行可能に押し戻されます。ブロック中から実行中への直接の矢印がないことに注意してください。ウェイクアップされたタスクは常にキューに再参加し、選択されるのを待ちます。
したがって、誰がこのプリエンプションフラグを設定することを決定し、何に基づいて決定するのでしょうか?主なトリガーは2つです。周期的なティックとウェイクアップです。まずティックから始めましょう。
定期的なティック — 心臓の鼓動
各CPUには、一定の規則正しいビートで発火するタイマーがあります。これはティックと呼ばれます。発火するたびに、カーネルは小さなルーチン、sched_tick()(kernel/sched/core.c:5636)を実行します。これは2つのことを行います。現在のタスクがこれまでに使用したCPU時間を合計し、その合計がタスクに与えられた時間スライスを超えているかどうかを確認します。タスクがスライスを使い果たした場合、カーネルはそのタスクにプリエンプションフラグを設定し、タスクは次の安全なポイントで切り替えられます。
これはスケジューラの心臓の鼓動です。自らブロックしないCPUを消費するタスクが、コアを永遠に占有するのを防ぎます。
ティックは、許容時間を超えたタスクを処理します。もう一方のトリガーは、新しい競合者が突然現れたときに発火します。
ウェイクアップ — より値する誰かが現れた
もう1つのトリガーはウェイクアップです。ブロックされたタスクはスリープ中で、何かを待っていることを思い出してください。そして、ある時点でその何かが起こります。データが到着するか、望んでいたロックが解放されます。それが起こると、カーネルはそのタスクをウェイクアップし、実行可能にするために実行キューに戻します。
しかし、CPUはすでに別のタスクで忙しい可能性があります。そのため、カーネルは一時停止して質問をします(wakeup_preempt_fair()、kernel/sched/fair.c:9055)。この新しくウェイクアップされたタスクは、現在実行中のタスクよりもCPUに値するか?答えが「はい」の場合(これから学ぶEEVDFのルールによります)、現在のタスクにプリエンプションフラグを設定します。いつものように、すぐに切り替えるのではなく、フラグを設定するだけです。これがマシンが応答性を感じさせる理由です。キーを打ってエディタがウェイクアップすると、エディタはバックグラウンドで長時間実行されているコンパイルをほぼ即座に脇に追いやることができます。
切り替えは「後で、安全なポイントで行われる」と言い続けているので、曖昧な説明をやめて、実際の切り替えが何を含み、なぜカーネルがそれをそれほどやりたがらないのかを見てみましょう。
コンテキストスイッチとそのコスト
スケジューラが次のタスクを選択し、それが現在実行中のタスクと異なる場合、CPUを譲るためにcontext_switch()(kernel/sched/core.c:5328)を呼び出します。(選択が同じタスクに戻ってきた場合、これは非常に一般的です。スイッチは完全にスキップされます。最も安価なコンテキストスイッチは、行わないものです。)
この「異なる場合」という小さな条件は多くの作業を行っています。なぜなら、スワップは無料ではないからです。明白なコストは簡単な部分です。送信タスクのCPU状態(レジスタ、プログラムカウンタ、スタックポインタ)を保存し、受信タスクの状態をロードし直します。これは現実的ですが、マイクロ秒単位で安価です。
高価な部分は、スイッチの後に起こることすべてであり、それはキャッシュが冷えることに帰着します。CPUは、遅い作業を2度行わなくても済むように、最近使用されたもののいくつかのキャッシュを手元に置いていますが、コンテキストスイッチはそれらを無効にする傾向があります。
最も明確な例はTLBです。メモリマネージャの記事で見たように、プログラムが使用するすべてのメモリアドレスは実際の物理的な場所に変換される必要があり、TLBはその変換の小さなキャッシュです。これにより、CPUは毎回ルックアップをやり直す必要がなくなります。しかし、次のタスクが異なるプロセスの場合は、独自の別個のメモリレイアウトを持っているため、カーネルはアドレス空間を切り替え、通常はTLBを消去します。新しいタスクの最初のメモリアクセスは、キャッシュされたものを見つけられず、それを再充填するための完全で遅い変換を行う必要があります。
通常のCPUキャッシュ(実際のデータとコードを保持するもの)も同様のヒットを受けます。他のタスクが実行されている間、それらは私たちのタスクのデータを押し出して、それ自身のデータのために場所を作りました。そのため、私たちのタスクが再開するときは「コールド」状態で始まり、それらのキャッシュがそのデータで再び満たされる間、遅いメモリフェッチの波を支払います。(最新のCPUにはTLB部分を緩和するトリックがありますが、コストをなくすわけではありません。)
したがって、間接的なコスト、つまりスイッチの直後の瞬間に支払われるコールドキャッシュとTLBミスは、レジスタスワッピング自体をはるかに超える可能性があります。これが隠された税金であり、スケジューラがプリエンプションを無制限に行わない理由です。その設計上の選択の多くは、部分的に必要な以上には切り替えないことを目的としています。タスクを10倍頻繁に切り替えるスケジューラは、紙の上ではより公平に見え、実際には遅く実行されるでしょう。なぜなら、作業を行う代わりにキャッシュの再充填に時間を費やすことになるからです。
さて、その「次のタスクを選択する」ステップは実際にどのように選択されるのでしょうか?それがアルゴリズムです。
スケジューラはどう決定するか:EEVDF
核心的な質問にたどり着きました。fairクラスは実行キュー上に実行可能なタスクの山を持っており、1つを選択しなければなりません。使用されるアルゴリズムはEEVDF — Earliest Eligible Virtual Deadline Firstです。名前は威圧的ですが、文字通りチェックリストであり、一度に1つのアイデアを構築できます。
全体の目標は2つのことを同時に達成することです。
- 公平性 — 時間が経つにつれて、各タスクは優先度に比例したCPUシェアを得るべきです。高優先度のタスクはより多く、低優先度のタスクはより少なく得ますが、誰も飢餓状態になりません。
- 低レイテンシ — 短いバースト(キーストロークに応答するインタラクティブアプリなど)しかCPUを必要としないタスクは、長時間実行されるバッチジョブの後ろで待たされるのではなく、迅速に処理されるべきです。
EEVDFは、仮想ランタイム、適格性、そして仮想デッドラインという3つの概念でこれを達成します。これらを、すべてが実行されるクロックから始めて、1つずつ構築していきます。
アイデア1:重みと仮想ランタイム
各タスクには優先度があります。Linuxでは、niceと呼ばれる値で設定します。−20(最も「貪欲」、最高優先度)から+19(最低)まであり、0がデフォルトです。カーネルはそのnice値を重みと呼ばれる数値に変換します。高優先度のタスクはより多くの重みを得、より多くの重みはより大きなCPUシェアを意味するはずです。
マッピングは線形ではありません。各nice値のステップが約25%の重みを変更する、事前に計算されたルックアップテーブルです。デフォルトのnice 0は重み1024を持っています。優先度をnice −5に上げると3121になり、nice −20の最高値では88761になります。逆方向では、nice +5は335に下がり、nice +19はわずか15になります。(完全なテーブルはsched_prio_to_weight[]、kernel/sched/core.c:10569にあります。)したがって、差は巨大です。nice −20のタスクは、nice +19のタスクのほぼ6,000倍の重みを運びます。
では、スケジューラはそのすべての重みを実際のCPUシェアにどのように変換するのでしょうか?実際の時間を測定することではありません。重いタスクと軽いタスクが両方とも10ミリ秒実行された場合、経過時間だけではそれらは等しくなり、重い方を優遇する余地はありません。トリックは、代わりに仮想ランタイム(vruntime)をカウントすることです。これは、実際の経過時間をタスクの重みで割ったものです(変換はcalc_delta_fair()、kernel/sched/fair.c:297)。
その除算がトリック全体です。重いタスクの仮想クロックはゆっくり進むため、vruntimeはほとんど動かない間に長時間実行できます。軽いタスクのvruntimeは急上昇します。スケジューラが常に最も低いvruntimeを優先する場合、重いタスクは「遅れている」ように見え続け、選択され続けます。したがって、重みは静かに比例CPUシェアになります。(この台帳を管理するメーターはupdate_curr()、fair.c:1407です。これは、ほぼすべてのスケジューライベントで実行中のタスクに仮想時間を請求します。タイマーティックごと、他のタスクがウェイクアップしたとき、次のタスクを選択する時間になったとき、タスクが実行キューに追加または削除されたときなどです。)
各タスクのクロックがどれだけ速く進むかを知るだけでは不十分です。スケジューラは、誰が実際に遅れているかを判断する方法をまだ必要としています。
アイデア2:平均とラグ
これでタスクごとの仮想クロックができました。しかし、クロックだけではタスクが公平なシェアを得ているかどうかはわかりません。比較対象が必要です。それが、実行可能なすべてのタスクのvruntimeの平均です。スケジューラがVと呼ぶ数値です。Vを「公平な線」と考えてください。これまでのCPUが完全に均等に分割されていた場合の、すべてのタスクのクロックがどこにあるかを示すものです。(これは加重平均なので、重いタスクはより多くカウントされ、カーネルはキュー全体をスキャンすることなく効率的に更新します。それがavg_vruntime()、fair.c:780です。)
これで、任意のタスク自身のvruntimeをその公平な線と比較でき、その差がラグになります。タスクのクロックが線の後ろにある場合、それは十分なCPU時間を実行しておらず、CPU時間が割り当てられています。もし線の前にあれば、すでにそのシェア以上のCPU時間を取得しています。
ルールは単純です。タスクは、前に出ていない(公平なシェアより進んでいない)場合にのみ適格になります(entity_eligible()、fair.c:939)。それがEEVDFの「Eligible」であり、公平性の保証を一度に行います。CPUを消費するタスクは先に進み、適格でなくなり、全員が追いつくまでベンチに座ります。
適格性は実行が許可されているタスクのフィールドを絞り込みますが、それらの間のタイを破ることはありません。そして、タイを破ることが最後のアイデアが登場する場所です。
アイデア3:仮想デッドライン
適格性は誰が実行できるかを教えてくれますが、通常は複数のタスクが同時に資格を得ます。では、スケジューラはそれらのうちどれが実際に最初に実行されるかをどのように決定するのでしょうか?
各タスクにはスライスがあります。これは、一度に中断なくCPUをどれだけ使用したいかです(デフォルトは700µsですが、タスクは異なるサイズを要求できます)。そのスライスから、スケジューラはタスクの仮想デッドラインを計算します(update_deadline()、fair.c:1238)。これは基本的に、「このタスクが今実行を開始した場合、(仮想クロック上で)いつスライスを完了すべきか?」ということです。
レシピはシンプルです。タスクの仮想クロックが現在どこにあるか(そのvruntime)を取り、それにスライスを追加します。ただし、スライスは最初に仮想時間に変換される必要があります。これは、アイデア1と同様に、タスクの重みで割る必要があります。したがって、デッドラインは「現在の仮想位置、プラスこのスライスが仮想クロックをどれだけ前進させるか」となります。
重みによる除算から2つの良い結果が得られます。第一に、重いタスクはより近いデッドラインを得ます。その仮想クロックはゆっくり進むため、同じスライスでもほとんど前進しません。これは、より多くの重みがより多くのCPUを静かに購入するもう1つの方法です。第二に、そしてこれがレイテンシの話全体がかかっている詳細です。より短いスライスを要求するタスクは、より早いデッドラインを得ます。スケジューラは、最も近いデッドラインを持つタスクを実行します。
これら3つのアイデア(仮想ランタイム、適格性、デッドライン)すべてが揃ったので、ついに実際の選択に組み合わせて見ることができます。
まとめ:pick_eevdf
これで名前が解読できます。Earliest Eligible Virtual Deadline First:適格な(CPUが割り当てられている、つまり公平なシェアより進んでいない)すべてのタスクの中から、最も早い仮想デッドラインを持つタスクを選択します。それが全体の決定であり、まさにpick_eevdf()(fair.c:1136)が行うことです。
[画像: EEVDFの選択を2つのステップで示す図。実行可能なタスク(それぞれラグとデッドラインを持つ)から開始し、ステップ1では適格でない(公平なシェアより進んでいる)タスクを除外し、ステップ2では残ったタスクの中から、次に実行されるタスクとして最も早い仮想デッドラインを持つタスクを選択する]
「全員をスキャンし、適格なタスクを保持し、最も早いデッドラインを見つける」というのが、数千もの実行可能なタスクがいる場合に遅く聞こえるのではないかと心配するかもしれません。そうではありません。その理由は、データ構造の巧妙な工夫です。実行可能なタスクは、デッドラインでソートされた赤黒木に格納されているため、最も早いデッドラインは常に左端にあり、簡単に取得できます。問題は、最も左のタスクが適格でない可能性があることです。それは「平均より進んでいる」タスクの1つである可能性があるため、常にそれを選ぶわけにはいきません。それを処理するために、木は拡張されています。各ノードは、そのサブツリー内の最小vruntimeも記憶しており、その小さなヒントにより、検索は適格なタスクを保持できない可能性のあるツリー全体を枝刈りできます。その結果、EEVDFはO(log n)時間で勝者を選択し、キュー全体を歩くことはありません。
知っておくべきもう1つのガードがあります。タスクが実行を開始すると、プリエンプトされる前に短い最小時間の実行が保証されます(protect_slice()、fair.c:1106)。そのため、スケジューラは数マイクロ秒ごとにタスクを切り替えるようなスラッシングに陥ることはありません。コンテキストスイッチが実際に何を表すかを思い出してください。これは、コストを払いすぎないように静かに機能する機械のもう1つの部分です。
そしてループは閉じます。実行中のタスクの仮想クロックがついに自身のデッドラインに達すると、update_currはリスケジュールフラグを上げ、次の安全なポイントでpick_eevdfが再び実行され、次の勝者を戴冠します。これが毎秒数千回、すべてのコアで繰り返されます。
これで、すべてのピースを個別に見てきました。それらを最初から最後まで一度に実行してみましょう。
最初から最後まで:スケジューリング決定の1回のライフサイクル
通常のタスク、Tと呼びましょう、を1回の完全な周回で追ってみましょう。順を追って説明します。
-
Tが誕生する。 作成された(またはスリープからウェイクアップした)とき、fairクラスはそれをCPUの実行キューにドロップします。Tは
vruntime、仮想デッドライン(vruntimeに重みで割ったスライスを加えたもの)、そしてデッドラインでソートされたままの赤黒木内のスロットを取得します。今、Tはただそこに座っています。実行可能ですが実行されていません。他のタスクが現在CPUを保持しています。 -
現在のタスクがCPUを手放す。 Tは、実行中の誰かがCPUを手放したときにのみ順番が回ってきます。そのタスクが自らブロックするか、プリエンプトされるかです(ティックがスライスを超えたのを捉えたか、ウェイクアップがフラグを立てた)。プリエンプションは即時ではありません。単に
TIF_NEED_RESCHEDを設定し、次の安全なポイント(通常はタスクがユーザー空間に戻るとき)を待ちます。 -
スケジューラが実行される。 その安全なポイントで、カーネルは
__schedule()(kernel/sched/core.c:7017)を呼び出します。これは、最も優先度の高いクラスから最も低いクラスまでスケジューリングクラスを歩き、それぞれに実行するものを尋ねます。通常のワークロードの場合、緊急およびリアルタイムクラスは空なので、fairクラスに到達します。 -
EEVDFがTを選択する。 fairクラスは
pick_eevdfを実行します。これは、適格なタスク(公平なシェアより進んでいないタスク)で最も早い仮想デッドラインを持つタスクをO(log n)で見つけます。それがTだとしましょう。 -
コンテキストスイッチ。
context_switchはCPUを古いタスクからTに譲ります。古いタスクのレジスタを保存し、アドレス空間を切り替え、Tが実行を開始します。TLBとキャッシュはコールド状態ですが、再充填してウォームアップします。Tが実行中、update_currはデッドラインに対してvruntimeの計測を続けます。 -
TがCPUを返す。 やがてTの順番が終わります。I/Oでブロックするかもしれませんが、代わりに実行を続け、ティックがデッドラインに達したことを検知して、Tに
TIF_NEED_RESCHEDを設定するとしましょう。Tは次の安全なポイントまで実行を続けます。 -
そしてループが回る。 その安全なポイントで、ステップ3に戻ります。
__schedule()が実行され、クラスを歩き、pick_eevdfが次の勝者を戴冠します。実行可能なままのTは、単に実行キューのツリーに再配置され、次の順番を待ちます。
そしてすべてが繰り返されます。毎秒数千回、すべてのコアで。
これで、機械全体が動いている様子が見えました。すべてを1つの図にまとめましょう。
まとめ
これがスケジューラです。スケジューラが常にスケジューリングするのはtask_structだけであることを覚えておいてください。プロセスとスレッドは実際には同じオブジェクトであり、共有するものだけが異なります。各タスクはスケジューリングクラスに属し、カーネルは固定優先順位でクラスを試しますが、上位のクラスは通常空なので、fairクラスがあなたが実行することのほとんどすべてを実行します。
タスクは2つの方法のいずれかでCPUを返します。自らブロックする(schedule()を呼び出す)、またはプリエンプトされる。プリエンプションは即時ではありません。カーネルは単にTIF_NEED_RESCHEDを設定し、次の安全なポイント(通常はタスクがユーザー空間に戻るとき)を待ちます。そのフラグは、周期的なティック(タスクがスライスを使い果たした)またはウェイクアップ(より値するタスクが現れた)のいずれかによって設定されます。それに続くcontext_switchは、新しいタスクがコールドTLBとキャッシュで始まるため、見かけよりも高価です。これはまさにスケジューラがあまり頻繁に切り替えようとしない理由です。
そして、fairクラスが実際に選択するときは、EEVDFを使用します。これは実際には3つのアイデアに集約されます。仮想ランタイムは、実際の時間/重みであり、重いタスクはそれをよりゆっくりと蓄積し、より頻繁に選択されます。これが重みが優先度になる方法です。適格性とは、公平なシェアより進んでいないタスクのみが考慮されることを意味します。これにより、誰もCPUを奪い取ることができないため、公平性が保証されます。そして、適格なタスクの中で、最も短い要求スライスがより早いデッドラインを購入する仮想デッドラインに向かいます。これがレイテンシの調整ノブです。つまり、重みは優先度を与え、適格性は公平性を与え、仮想デッドラインはレイテンシを与えます。
次に、誰が実行するかからプログラムがファイルにどのように到達するかに焦点を移します。カーネルがすべてのファイルシステムの前にある共通のレイヤーであり、バイトがディスク上にあるか、メモリ上にあるか、ネットワーク共有上にあるかに関わらず、open、read、writeが同じように機能するようにします。VFS(Virtual File System)が次です。