Linuxは、さまざまなアルゴリズムを使用してさまざまなプロセスタイプをスケジュールできるという点で、プロセッサのスケジューリングにモジュール式のアプローチを採用しています。スケジューリングクラスは、どのスケジューリングポリシーがどのタイプのプロセスに適用されるかを指定します。 2007年にLinux2.6.23カーネルの一部となったCompletefairScheduling（CFS）は、通常の（リアルタイムではなく）プロセスのスケジューリングクラスであるため、 SCHED_NORMALという名前が付けられています。 。
CFSは、デスクトップ環境で一般的なインタラクティブアプリケーションを対象としていますが、 SCHED_BATCHとして構成できます。 たとえば、大容量のWebサーバーで一般的なバッチワークロードを優先します。いずれにせよ、CFSは、「従来のプリエンプティブスケジューリング」と呼ばれるもので劇的に機能しなくなります。また、「完全に公正な」主張は技術的な目で見なければなりません。そうしないと、主張は空虚な自慢のように見えるかもしれません。
CFSを他のプロセススケジューラと区別するもの（実際、上記）の詳細を掘り下げてみましょう。いくつかの主要な技術用語の簡単なレビューから始めましょう。
LinuxはプロセスのUnixビューを継承します 実行中のプログラムとして。そのため、プロセスは共有システムリソースの他のプロセスと競合する必要があります：メモリ 命令とデータを保持するために、少なくとも1つのプロセッサ 命令を実行するため、および I/Oデバイス 外界と相互作用する。プロセスのスケジューリングは、オペレーティングシステム（OS）がタスク（たとえば、いくつかの数値の処理、ファイルのコピー）をプロセッサに割り当てる方法です。実行中のプロセスがタスクを実行します。プロセスには1つ以上の実行スレッドがあります 、マシンレベルの命令のシーケンスです。プロセスをスケジュールすることは、プロセッサ上でそのスレッドの1つをスケジュールすることです。
Linuxターミナル
- Linux用の上位7つのターミナルエミュレータ
- Linuxでのデータ分析のための10個のコマンドラインツール
- 今すぐダウンロード：SSHチートシート
- 高度なLinuxコマンドのチートシート
- Linuxコマンドラインチュートリアル
単純化した動きで、Linuxは、スケジュールされたプロセスをシングルスレッドであるかのように扱うことにより、プロセススケジューリングをスレッドスケジューリングに変えます。プロセスがNでマルチスレッド化されている場合 スレッド、次に N スレッドをカバーするには、スケジューリングアクションが必要になります。マルチスレッドプロセス内のスレッドは、メモリアドレス空間などのリソースを共有するという点で関連性があります。 Linuxスレッドは、軽量を使用して、軽量プロセスとして説明されることがあります。 プロセス内のスレッド間でのリソースの共有を強調します。
プロセスはさまざまな状態にある可能性がありますが、スケジューリングでは2つが特に重要です。 ブロックされた プロセスは、I/Oイベントなどのイベントの完了を待っています。プロセスは、イベントが完了した後にのみ実行を再開できます。 実行可能 プロセスは現在ブロックされていないプロセスです。
プロセスはプロセッサにバインドされています （別名コンピューティングバウンド ）I / Oリソースではなく、主にプロセッサを消費し、 I/Oバウンドの場合 反対の場合;したがって、プロセッサにバインドされたプロセスはほとんど実行可能ですが、I/Oバウンドのプロセスはほとんどブロックされます。例として、数値の処理はプロセッサに依存し、ファイルへのアクセスはI/Oに依存します。プロセス全体は、プロセッサバウンドまたはI / Oバウンドのいずれかとして特徴付けられる場合がありますが、特定のプロセスは、その実行のさまざまな段階でどちらか一方になる場合があります。ブラウザなどのインタラクティブなデスクトップアプリケーションは、I/Oバウンドになる傾向があります。
優れたプロセススケジューラは、プロセッサバウンドタスクとI / Oバウンドタスクのニーズのバランスをとる必要があります。特に、デスクトップマシン、組み込みデバイス、モバイルデバイス、サーバークラスタ、スーパーコンピュータなどの非常に多くのハードウェアプラットフォームで動作するLinuxなどのオペレーティングシステムでは、など。
Unixは古典的なプリエンプティブスケジューリングを普及させ、VAX / VMS、Windows NT、Linuxなどの他のオペレーティングシステムが後に採用しました。このスケジューリングモデルの中心は、固定タイムスライスです。 、他のタスクを優先してプリエンプトされるまで、タスクがプロセッサを保持できる時間（たとえば、50ミリ秒）。プリエンプションされたプロセスがその作業を終了していない場合は、プロセスを再スケジュールする必要があります。このモデルは、過去のシングルCPUマシンでも、プロセッサのタイムシェアリングによるマルチタスク（同時実行）をサポートするという点で強力です。
従来のモデルには通常、プロセスの優先度ごとに1つずつ、複数のスケジューリングキューが含まれます。優先度の高いキューのすべてのプロセスは、優先度の低いキューのプロセスの前にスケジュールされます。例として、VAX/VMSはスケジューリングに32の優先度キューを使用します。
CFSは、固定のタイムスライスと明示的な優先順位を省略します。プロセッサ上の特定のタスクの時間は、システムの存続期間中にスケジューリングコンテキストが変化するときに動的に計算されます。やる気を起こさせるアイデアと技術的な詳細のスケッチは次のとおりです。
-
複数のタスクを同時に実行できるという点で理想化されているプロセッサPを想像してみてください。 。たとえば、タスクT1とT2はPで同時に実行でき、それぞれがPの魔法の処理能力の50％を受け取ります。この理想化は、完璧なマルチタスクを表しています。 、CFSは、理想化されたプロセッサではなく、実際に達成しようと努めています。 CFSは、ほぼ完璧なマルチタスクを実現するように設計されています。
-
CFSスケジューラにはターゲットレイテンシがあります 、これは、実行可能なすべてのタスクがプロセッサを少なくとも1回オンにするために必要な最小時間であり、無限に短い期間に理想的です。そのような期間が無限に短い可能性がある場合、実行可能な各タスクは、任意の期間（たとえば、10ms、5nsなど）にプロセッサをオンにします。もちろん、理想化された無限に短い期間は、現実の世界で概算する必要があり、デフォルトの概算は20msです。次に、実行可能な各タスクは1 / Nを取得します。 ターゲットレイテンシのスライス。N タスクの数です。たとえば、ターゲットレイテンシが20ミリ秒で、競合するタスクが4つある場合、各タスクは5ミリ秒のタイムスライスを取得します。ちなみに、スケジューリングイベント中にタスクが1つしかない場合、このラッキータスクはターゲットレイテンシ全体をスライスとして取得します。 フェア CFSでは1/ Nで前面に出てきます プロセッサをめぐって競合する各タスクに与えられるスライス。
-
1 / N スライスは確かにタイムスライスですが、そのようなスライスは N に依存しているため、固定されたものではありません。 、プロセッサをめぐって現在競合しているタスクの数。システムは時間とともに変化します。一部のプロセスが終了し、新しいプロセスが生成されます。実行可能プロセスはブロックされ、ブロックされたプロセスは実行可能になります。 Nの値 は動的であるため、1 / N プロセッサをめぐって競合する実行可能なタスクごとに計算されたタイムスライス。伝統的な素敵な 値は1/ Nの重みに使用されます スライス：優先度の低い良い 値は、1 / Nのごく一部のみを意味します スライスはタスクに与えられますが、優先度の高いいい 値は、1 / Nの比例して大きい割合を意味します スライスはタスクに与えられます。要約すると、いい 値はスライスを決定しませんが、1 / Nのみを変更します 競合するタスク間の公平性を表すスライス。
-
コンテキストスイッチのたびに、オペレーティングシステムでオーバーヘッドが発生します 発生します。つまり、あるプロセスが別のプロセスに取って代わられる場合です。このオーバーヘッドが過度に大きくなるのを防ぐために、スケジュールされたプロセスがプリエンプションされる前に実行する必要がある最小時間（通常は1msから4msの設定）があります。この最小値は、最小粒度と呼ばれます。 。多くのタスク（たとえば、20）がプロセッサをめぐって競合している場合、最小粒度（4msと想定）はより多くになる可能性があります。 1 / Nより スライス（この場合は1ms）。最小粒度が1/ Nよりも大きいことが判明した場合 スライスすると、プロセッサをめぐって競合するタスクが多すぎるため、システムが過負荷になり、公平性が失われます。
-
プリエンプションはいつ発生しますか？ CFSは、オーバーヘッドを考慮して、コンテキストスイッチを最小限に抑えようとします。コンテキストスイッチに費やされた時間は、他のタスクに使用できない時間です。したがって、タスクがプロセッサを取得すると、そのタスクは重み付けされた1 / N全体で実行されます。 他のタスクを優先してプリエンプションされる前にスライスします。タスクT1が重み付けされた1/ Nに対して実行されたとします。 スライス、および実行可能なタスクT2は、現在、仮想ランタイムが最も低くなっています。 （vruntime）プロセッサをめぐって競合するタスクの中で。 vruntimeは、タスクがプロセッサ上で実行された時間をナノ秒単位で記録します。この場合、T1はT2を優先してプリエンプトされます。
-
スケジューラーは、実行可能およびブロックされたすべてのタスクのvruntimeを追跡します。タスクのvruntimeが低いほど、プロセッサでの時間に適したタスクになります。したがって、CFSは、低実行時間のタスクをスケジューリングラインの前に移動します。 line のため、詳細は近日公開されます リストではなく、ツリーとして実装されます。
-
CFSスケジューラはどのくらいの頻度でスケジュールを変更する必要がありますか？ スケジュール期間を決定する簡単な方法があります 。ターゲットレイテンシ（TL）が20ミリ秒で、最小粒度（MG）が4ミリ秒であるとします。
TL / MG = (20 / 4) = 5 ## five or fewer tasks are okこの場合、5つ以下のタスクで、各タスクがターゲットレイテンシー中にプロセッサーをオンにすることができます。たとえば、タスク番号が5の場合、実行可能な各タスクには1 / Nがあります。 最小粒度に等しい4msのスライス。タスク番号が3の場合、各タスクは1 / Nを取得します ほぼ7msのスライス。いずれの場合も、スケジューラーは、ターゲットレイテンシーの期間である20msで再スケジュールします。
タスクの数（たとえば、10）がTL / MGを超えると、問題が発生します。これは、各タスクが、計算された1 / Nではなく4msの最小時間を取得する必要があるためです。 スライス、2msです。この場合、スケジューラーは40msで再スケジュールします：
(number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms
CFSより前のLinuxスケジューラーは、ヒューリスティックを使用して、スケジューリングに関して対話型タスクの公正な処理を促進します。 CFSは、vruntimeの事実をほとんど自分自身で語らせることで、まったく異なるアプローチを取ります。これは、たまたま眠る人の公平性をサポートします。 。対話型タスクは、その性質上、ユーザー入力を待機するという意味で多くのスリープ状態になる傾向があるため、I/Oバウンドになります。したがって、このようなタスクのvruntimeは比較的短くなる傾向があり、タスクはスケジューリングラインの前に移動する傾向があります。
CFSは、任意のプロセス（カーネルまたはユーザー）が任意のプロセッサーで実行できる対称型マルチプロセッシング（SMP）をサポートします。まだ構成可能なスケジューリングドメイン 負荷分散または分離のためにプロセッサをグループ化するために使用できます。複数のプロセッサが同じスケジューリングポリシーを共有している場合、それらの間の負荷分散はオプションです。特定のプロセッサが他のプロセッサとは異なるスケジューリングポリシーを持っている場合、このプロセッサはスケジューリングに関して他のプロセッサから分離されます。
構成可能なスケジューリンググループ もう1つのCFS機能です。例として、デスクトップマシンで実行されているNginxウェブサーバーについて考えてみます。起動時に、このサーバーにはマスタープロセスと4つのワーカープロセスがあり、HTTPリクエストハンドラーとして機能します。 HTTPリクエストの場合、リクエストを処理する特定のワーカーは関係ありません。リクエストがタイムリーに処理されることだけが重要であるため、4人のワーカーが一緒になって、リクエストが届いたときにタスクハンドラーを引き出すためのプールを提供します。したがって、4人のNginxワーカーをグループとして扱うのではなく、グループとして扱うのが妥当と思われます。スケジューリングの目的で個人として、そしてスケジューリンググループはまさにそれを行うために使用することができます。 4つのNginxワーカーは、個々のvruntimeではなく、それらの間に単一のvruntimeを持つように構成できます。構成は、ファイルを介して従来のLinuxの方法で行われます。 vruntime-sharingの場合、 cpuという名前のファイル .shares 、おなじみのシェルコマンドで詳細を入力すると、作成されます。
前述のように、Linuxはクラスのスケジューリングをサポートしています。 異なるスケジューリングポリシーとそれらの実装アルゴリズムが同じプラットフォーム上で共存できるようにします。スケジューリングクラスは、Cのコードモジュールとして実装されます。これまでに説明したスケジューリングクラスであるCFSは、 SCHED_NORMALです。 。リアルタイムタスク専用のスケジューリングクラス、 SCHED_FIFO もあります （先入れ先出し）および SCHED_RR （ラウンドロビン）。 SCHED_FIFOの下 、タスクは完了するまで実行されます。 SCHED_RRの下 、タスクは、固定されたタイムスライスを使い果たしてプリエンプトされるまで実行されます。
CFSの実装
CFSでは、タスク情報を追跡するための効率的なデータ構造と、スケジュールを生成するための高性能コードが必要です。スケジューリングの中心的な用語であるrunqueueから始めましょう。 。これは、スケジュールされたタスクのタイムラインを表すデータ構造です。名前にもかかわらず、ランキューはFIFOリストとして従来の方法で実装する必要はありません。 CFSは、時系列の赤黒木をランキューとして使用することにより、伝統を打ち破ります。データ構造は、効率的な挿入を備えた自己平衡二分探索木であるため、この仕事に最適です。 および削除 O（log N）で実行される操作 時間、ここで N ツリー内のノードの数です。また、ツリーは、特定のプロパティ（この場合はvruntime）に基づいてエンティティを階層に編成するための優れたデータ構造です。
CFSでは、ツリーの内部ノードはスケジュールされるタスクを表し、ツリー全体は、他のランキューと同様に、タスク実行のタイムラインを表します。赤黒木は、スケジュールを超えて広く使用されています。たとえば、Javaはこのデータ構造を使用して TreeMapを実装します 。
CFSでは、すべてのプロセッサに特定のタスクのランキューがあり、複数のランキューで同時にタスクが発生することはありません。各ランキューは赤黒木です。ツリーの内部ノードはタスクまたはタスクグループを表し、これらのノードはvruntime値によってインデックスが付けられるため、（ツリー全体または任意のサブツリーで）左側の内部ノードのvruntime値は右側のノードよりも低くなります。
25 ## 25 is a task vruntime
/\
17 29 ## 17 roots the left subtree, 29 the right one
/\ ...
5 19 ## and so on
... \
nil ## leaf nodes are nil
要約すると、vruntimeが最も低く、したがってプロセッサの必要性が最も高いタスクは、左側のサブツリーのどこかにあります。実行時間が比較的長いタスクは、右側のサブツリーに集まります。プリエンプトされたタスクは右側のサブツリーに入り、他のタスクにツリー内を左に移動する機会を与えます。 vruntimeが最小のタスクは、ツリーの左端（内部）ノードに配置されます。つまり、ランキューの先頭になります。
CFSスケジューラには、C task_structというインスタンスがあります。 、スケジュールする各タスクに関する詳細情報を追跡します。この構造体には、 sched_entityが埋め込まれています。 構造。これには、スケジューリング固有の情報、特にタスクまたはタスクグループごとのvruntimeが含まれます。
struct task_struct { /** info on a task **/
...
struct sched_entity se; /** vruntime, etc. **/
...
}; 赤黒木はおなじみのC方式で実装されており、効率を高めるためにポインターが重視されています。 cfs_rq 構造体インスタンスはrb_rootを埋め込みます tasks_timelineという名前のフィールド 、赤黒木の根を指します。ツリーの各内部ノードには、親ノードと2つの子ノードへのポインターがあります。リーフノードにはnil それらの価値として。
CFSは、単純なアイデア（すべてのタスクにプロセッサーリソースの公平なシェアを与える）を、手間をかけずに非常に効率的な方法で実装する方法を示しています。 CFSは、固定タイムスライスや明示的なタスク優先順位などの従来のアーティファクトなしで、公平で効率的なスケジューリングを実現することを繰り返す価値があります。もちろん、さらに優れたスケジューラーの追求は続いています。ただし、現時点では、CFSは汎用プロセッサのスケジューリングと同じくらい優れています。