完全に公平なスケジューラ

Completely Fair Scheduler ( CFS ) は、Linuxカーネルの 2.6.23 (2007 年 10 月) リリースに統合されたプロセス スケジューラです。これは、クラスのタスク(つまり、リアルタイム実行制約のないタスク) のデフォルト スケジューラであり、プロセス実行のCPUリソース割り当てを処理し、全体的な CPU 使用率を最大化するとともにインタラクティブなパフォーマンスも最大化することを目指していました。 SCHED_NORMAL

以前の Linux 2.6 カーネルで使用されていたO(1) スケジューラは、アクティブタスクと期限切れタスクの実行キューを維持および切り替えていましたが、CFS スケジューラの実装は CPU ごとの実行キューに基づいています。実行キューのノードは、赤黒木によってソートされた時間順に並べられたスケジュール可能なエンティティです。CFS は、優先度ごとに固定されたタイムスライスという古い概念を廃止し、代わりにタスク (または、より正確にはスケジュール可能なエンティティ) に CPU 時間を公平に分配することを目指しています。^{[1] [2]}

Linux カーネルのバージョン 6.6 以降では、EEVDFスケジューラに置き換えられました。

タスク (つまり、スレッドの同義語) は、Linux がスケジュールできる最小限のエンティティです。ただし、スレッドのグループ、マルチスレッド プロセス全体、さらには特定のユーザーのすべてのプロセスも管理できます。この設計により、スケジュール可能なエンティティの概念が生まれ、タスクはスケジューラによってグループ化され、全体として管理されます。この設計が機能するには、各task_structタスク記述子に、タスクが属するエンティティのセットを表す型のフィールドが埋め込まれますsched_entity。

タイプのCPUごとの実行キューは、時間順に構造を赤黒木（Linux用語では「rbtree」）にソートします。ここで、左端のノードは、実行時間が最も短いエンティティによって占有されます（これはエンティティのフィールドに保存されますcfs_rq） 。ノードは、プロセッサの「実行時間」によってナノ秒単位でインデックス付けされます。^[3]sched_entityvruntime

各プロセスについて「最大実行時間」も計算され、プロセスが「理想的なプロセッサ」で実行されると予想される時間を表します。これは、プロセスが実行を待機していた時間をプロセスの総数で割ったものです。

新しいプロセスを実行するためにスケジューラが呼び出されると、次のようになります。

1. スケジューリング ツリーの一番左のノードが選択され (実行時間が最も短くなるため)、実行のために送信されます。
2. プロセスが単に実行を完了すると、システムおよびスケジュール ツリーから削除されます。
3. プロセスが最大実行時間に達するか、または何らかの理由で停止された場合（自発的または割り込みにより）、そのプロセスは新たに消費された実行時間に基づいてスケジューリング ツリーに再挿入されます。
4. 次に、ツリーから新しい左端のノードが選択され、反復が繰り返されます。

プロセスがスリープ状態に多くの時間を費やしている場合、その消費時間の値が低くなり、最終的に必要になったときに自動的に優先度が上げられます。したがって、このようなタスクは、常に実行されているタスクよりもプロセッサ時間が短くなることはありません。

cfs_rqCFS スケジューラの実行キューにノードを挿入するアルゴリズムの複雑さはO ( log N ) です。ここで、Nはエンティティの合計数です。左端のノードは常にキャッシュされるため、次に実行するエンティティの選択は一定時間で行われます。

Con Kolivasのスケジューリングに関する研究、特にRotating Staircase Deadlineと名付けられた「公平なスケジューリング」の実装に触発されたIngo Molnár は、以前のO(1) スケジューラの代替として CFS を開発し、発表の中で Kolivas に功績を称えました。^{[4] CFS は、}重み付け公平キューイングと 呼ばれる、よく研究された古典的なスケジューリング アルゴリズムの実装です。^{[5]公平キューイングはもともと}パケット ネットワーク用に発明されましたが、以前はストライド スケジューリングという名前で CPU スケジューリングに適用されていました。CFS は、汎用オペレーティング システムで広く使用されている公平キューイングプロセス スケジューラの最初の実装です。 ^[5]

Linuxカーネルは、2010年11月に2.6.38カーネル用のCFSパッチを受け取り、デスクトップやワークステーションでの使用に対してスケジューラが「公平」になりました。Linus Torvaldsの提案に基づいて Mike Galbraith が開発したこのパッチは、対話型デスクトップのパフォーマンスを大幅に向上させる自動グループ化という機能を実装しています。^[6]このアルゴリズムは、親プロセスを子プロセスと同じタスクグループに配置します。^[7] (タスクグループは、setsid() システムコールによって作成されたセッションに関連付けられています。^[8] ) これにより、CPUを集中的に使用するスレッドを多数使用する他のタスクを実行しているときに、マルチコアおよびマルチCPU ( SMP ) システムで対話型の応答時間が遅くなるという問題が解決されました。簡単に説明すると、このパッチを適用すると、 Linuxカーネルのコンパイル中やビデオのエンコード中など、ビデオの視聴、電子メールの読み取り、その他の一般的なデスクトップアクティビティを、不具合や途切れなく実行できるようになります。

2016年、Linuxスケジューラは、「Linuxスケジューラ：無駄にされたコアの10年」という論文で概説された提案に基づいて、マルチコアパフォーマンスを向上させるためにパッチが適用されました。^[9]

2023年には、 CFSに代わる最も早い適格な仮想期限優先スケジューリング（EEVDF）に基づく新しいスケジューラが準備されていました。 ^[10]その動機は、CFSの「レイテンシナイス」パッチの必要性をなくすことでした。^[11]

• ブレインファックスケジューラー
• スケジュール期限

• Corbet, Jonathan (2007-04-17). 「Schedulers: The Plot Thickens」. LWN.net . 2017-09-06 にオリジナルからアーカイブ。2016-07-21に取得。
• Corbet, J. (2007-07-02). 「CFS グループ スケジューリング」. LWN.net. 2017-09-06 にオリジナルからアーカイブ。2016-07-21に取得。
• Corbet, J. (2007-10-16). 「公平なユーザー スケジューリングとその他のスケジューラ パッチ」 LWN.net。2017 年 6 月 12 日にオリジナルからアーカイブ。2016 年11 月 24 日に取得。
• Corbet, J. (2010-11-17). 「TTY ベースのグループ スケジューリング」. LWN.net. 2018-05-21 にオリジナルからアーカイブ。2016-11-24に取得。
• Corbet, J. (2010-12-06). 「グループスケジュールと代替案」 LWN.net。 2017-06-11 にオリジナルからアーカイブ。2016-11-24に取得。
• Singh Pabla, Chandandeep (2009-08-01). 「Completely Fair Scheduler」. linuxjournal.com . 2018-03-18 にオリジナルからアーカイブ。2014-11-17に取得。
• Jones, Tim (2009-12-15)。「Linux 2.6 Completely Fair Scheduler の内部」IBM。
• Lozi, Jean - Pierre (2016-04-21). 「Linux スケジューラ: 無駄にされたコアの 10 年」(PDF)。ACM。2018-02-05にオリジナル(PDF)からアーカイブ。2016-11-24に取得。