Linuxカーネルの理解：スケジューラ

📚 Linuxカーネルの理解 (4部作中4) ▼1. Linuxカーネルの起動 2. システムコール 3. メモリマネージャ 4. スケジューラ ここが現在の記事です 前回の記事では、カーネルが各プロセスに独自のメモリビューをどのように提供するかを見ました。しかし、メモリはプロセスが実際に動作するために必要なものの一部に過ぎません。もう半分はCPUそのものです — そして、マシンには限られた数のCPUしかありませんが、それらで実行したいものは通常、数百または数千にも及びます。 したがって、誰かが常に、誰がCPUをどのくらいの期間使用するかを決定しなければなりません。その誰かがスケジューラです。数ミリ秒ごとに、すべてのコア上で、カーネルは同じ質問を自問します — 今すぐ実行したいものの中で、次に誰が実行されるのか？ — そしてその答えは、高速で、公平で、コンパイルがすべてのコアを占有している間でもテキストエディタが応答性を維持するのに十分なものでなければなりません。 スケジューラには多くの可動部品があるため、一歩ずつ見ていきましょう。まず、スケジューラが何をスケジューリングしているのか、つまりプロセスとスレッドが内部で実際に何であるかから始めます。次に、Linuxが1つのスケジューラだけでなく、いくつかのスケジューラをスケジューリングクラスとしてスタックしていることを見ていきます。そこから、実行中のタスクがいつ実行を停止するのか（これは思ったよりも興味深い）、そしてあるタスクから別のタスクに切り替えるコストを見ていきます。そして最後に、その核心に迫ります：EEVDFと呼ばれるアルゴリズムを使って、カーネルが実際に次に誰を決定するのか。 📌 範囲に関する注意 ここでの内容はすべてLinux 7.1に基づいています（スケジューラのコアはkernel/sched/にあり、主にfair.cとcore.cにあります）。そして、これは意図的な単純化です：実際の実装には、CPU間のロードバランシング、cgroupを介したグループスケジューリング、CPU帯域幅制御、NUMA認識、無数のエッジケースなど、はるかに多くのことが行われています。これらは主要なアイデアを明確に保つために省略しています。 それでは、スケジューラ自体が始まる場所から始めましょう：CPU上で実際にシャッフルしているものから。 スケジューラが実際にスケジューリングするもの これが最初の驚きであり、多くの混乱を解消します：カーネルは「プロセス」や「スレッド」をスケジューリングしません。これらはユーザー空間で私たちが使う言葉です。カーネル内部には、スケジューリング可能なものが1種類しかありません — task_struct (include/linux/sched.h:820) であり、これはカーネルが1つの実行フロー、つまりCPU上に座って命令を実行できる1つのものを記録したものです。 あなたがプロセスと呼ぶものと、あなたがスレッドと呼ぶものは、どちらも内部的には全く同じ種類のオブジェクトです。唯一の違いは、それらが何を共有するかです。新しいプロセスをfork()すると、親と何も共有しない新しいtask_structが得られます — 独自のメモリ、独自のファイルディスクリプタ、独自のすべてです。スレッドを作成する（clone()と適切なフラグを使って）場合も、新しいtask_structが得られますが、こちらはアドレス空間、開いているファイル、シグナルハンドラなどを、それを生成したタスクと共有します。したがって、「マルチスレッドプロセス」は、実際には同じメモリを指している多数のtask_structsに過ぎません。 スケジューラの視点から見ると、それらのどれも関係ありません — 誰が何を共有しているかを知ることも気にすることもないのです。ただ、実行可能なものとそうでないもののtask_structsの山を見て、実行可能なものの中から選択します。CPU上で実行可能なものはすべてtask_structです、それだけです。 さて、task_structは巨大です — カーネルがタスクについて知っているほとんどすべてを保持しています — しかし、スケジューラはごく一部しか気にしません。すべてのタスクの内部には、スケジューリング状態の小さな埋め込みバンドル（sched_entity、include/linux/sched.h:575と呼ばれます）があり、その小さなバンドル — 周りの巨大な構造体ではなく — が、スケジューラが実際に推論するものです。 そこに興味深い数値、vruntime、vlag、deadline、sliceのような名前のものが存在します。これらが何を意味するかについてはまだ心配しないでください — それらを解明することが、この記事の残りの部分のほとんどです。今のところ、その形状だけを覚えておいてください：各実行可能なタスクは、少量の会計状態を保持しており、それがスケジューラが次に誰を実行するかを決定するときに読み取る部分です。 しかし、「スケジューラ」というのは少し嘘です。なぜなら、1つだけでなく複数存在するからです — ですから、さらに進む前に、誰が実際に決定を下すのかを見ていきましょう。 スケジューリングクラス：誰が最初に尋ねられるのか アルゴリズムに入る前に、少しひねりがあります：Linuxには実際には1つのスケジューラがありません。いくつかあり、厳密な優先順位で積み重ねられています。これらの積み重ねられたスケジューラはスケジューリングクラスと呼ばれ、それぞれが異なる種類のワークロードのための自己完結型のポリシーです。 それらが協力する方法は非常に単純です。CPUが何かを実行する必要があるとき、カーネルはスタックの上から順番に各クラスに尋ねます、「実行可能なものがあるか？」最初に「はい」と答えたものが勝ち、それ以下のものは投票権すらありません。したがって、クラスは、それより上のすべてのクラスが何も提供しなかった場合にのみタスクを実行します。 では、それらの箱には何が入っているのでしょうか？一番上の3つは、いくつかのタスクに通常の作業よりも優先される権利を与えるために存在します。一番上にはstopがあり、これはスケジューリングポリシーというよりも、カーネルが即座に緊急なことをする必要があるときに（例えば、シャットダウンされるコアからタスクを移行させるなど）「すべてを中止する」レバーを引くようなものです。その下にはdeadlineがあり、厳密なタイミング要件を持つタスク（オーディオやロボット工学を想像してください）を処理します。ここでは優先度を要求するのではなく、「このタスクはこれだけのCPUをこれくらいの頻度で必要とする」という保証を求めます。そしてrtは古典的なリアルタイム優先度です — リアルタイムタスクは好きなだけ実行され、さらに高いものにしか道を譲りません。これは低遅延が重要なコードには素晴らしいですが、そのようなタスクがスリープしない場合、マシンをフリーズさせる良い方法でもあります。 ただし、ここが重要な点です：通常のデスクトップやサーバーでは、これらの上位3つの箱はほとんど常に空です。これがこの記事の残りの部分で重要になるものにつながります：fair。これは基本的にあなたが実行するすべてのものが実際に存在するところです — あなたのシェル、あなたのブラウザ、あなたのデータベース、そのコンパイルジョブ。これらのタスクのどれも特別なタイミング要件を持っていません。ただ合理的なCPUの割り当てを望んでおり、fairクラスの仕事はそれらの割り当てを公平に分配することです。それより上のクラスは通常アイドル状態であるため、fairクラスがほとんど常に主導権を握っています — ですから、人々が「Linuxスケジューラ」と言うとき、彼らがほとんど常に意味するのはこれです。 下位を補完するために、全体像を完成させるためだけに：extは、BPFプログラムとしてスケジューリングポリシー全体をロードできる新しい追加機能であり、カーネルを再コンパイルせずに実験するのに便利です。そしてidleは最低限の、何もすることのないタスクであり、他にCPUを必要とするものが何もないときにのみ実行され、静かにコアをスリープさせて電力を節約します。これらについては詳しく触れません — ここからはすべてfairについてです。 fairクラスは、EEVDF（Earliest Eligible Virtual Deadline First）という威圧的な名前のアルゴリズムに基づいています。その名前に怖がらないでください — 後で一つずつ分解していきますが、かなり直感的なアイデアであることがわかります。 EEVDFがどのように選択するかに進む前に、それがいつ機会を得るのか、つまり実行中のタスクがCPUを手放す瞬間を知っておくと役立ちます。 実行中のタスクはいつ実行を停止するのか？ あるタスクがCPU上で happily 実行されているとしましょう。何がそれを停止させ、他のものが実行できるようにするのでしょうか？これは人々が通常簡単に流してしまう部分ですが、システム全体が実際に機能する場所です。タスクがCPUを手放す方法は本当に2つしかなく、その両方を理解することがスケジューラを理解する上でのほとんどです。まず、より穏やかな方から見ていきましょう。 方法1：自発的にブロックする タスクが実行を停止する最も一般的な理由は、まだ持てないものを要求するためです。データのないソケットに対してread()を呼び出す、誰かが保持しているミューテックスを取得する、sleep()を呼び出す、条件変数で待機する — すぐに完了できないことなら何でもです。 そのようなことが起こると、ブロッキングプリミティブの奥深くで、カーネルはタスクの状態を「実行不可能」に設定し、schedule()を呼び出します (kernel/sched/core.c:7273)。これは、タスクが自発的に「今は何もすることがないので、CPUを誰か他の人に譲ります」と言っているのです。スケジューラはタスクを実行キューから完全に削除します（実行不可能なので、存在しません）。