Completely_Fair_Schedulerとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Completely_Fair_Schedulerの意味・解説 

Completely Fair Scheduler

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/02/15 17:00 UTC 版)

Completely Fair Scheduler (CFS) は、Linuxカーネル 2.6.23 にマージされたタスクスケジューラである。プロセス実行に必要なCPUリソース割り当てを行い、全体としてCPU利用効率を最大化しつつ対話的性能も最大化する。

コン・コリバス英語版CPUスケジューリングに関する業績、特に Rotating Staircase Deadline と名付けたフェア・シェア・スケジューリング英語版の実装に強く影響され、インゴ・モルナー英語版が従来のO(1)スケジューラ英語版の代替としてCFSを開発した[1]

それまでの Linux 2.6 カーネルで使われていたO(1)スケジューラ英語版とは対照的に、CFSスケジューラの実装はランキュー英語版を採用していない。代わりに赤黒木で将来のタスク実行の予定表を実装している。さらにこのスケジューラはナノ秒単位の実行時間計測を行い、ナノ秒単位で個々のプロセスにCPUを割り当てる(したがって、それまでのタイムスライスの観念より細かい)。このように正確な知識を使うことで例えば、プロセスが対話的か否かを判定するのに特別なヒューリスティクスを使う必要がなくなる[2]

従来のO(1)スケジューラと同様、CFSは "sleeper fairness" という概念を採用している。これは、スリープまたはウェイトしているタスクとランキュー上で待っているタスクを公平に扱うという方針である。したがって時間の大部分をユーザーの入力などのイベントを待つことに費やしている対話型タスクであっても、必要ならそれなりのCPU時間を得ることができる。

アルゴリズム

このスケジューラはタスク実行計画を赤黒木に記録しており、各タスクはそれまでに消費したプロセッサ時間をキーとして赤黒木に入れられる[3]。それにより、消費したCPU時間が最も短いプロセスが効率的に選択できる(木の左端ノードに格納されている)。選択したプロセスを木から除去し、実行後は実行時間を更新して木構造上の適切な位置(通常は前とは別の位置)に戻す。そして新たな木の左端ノードを選択し、同様に繰り返す。

タスクが長時間スリープしている場合、実行時間の値が小さいため、スリープ状態から起きてきたときに自動的に優先度が上がる。したがってそのようなプロセスに割り当てられるプロセッサ時間が定常的に動作しているタスクより小さくなることはない。

背景

CFSのもとになったとされる均等化キューイング英語版は元々はパケット通信用に考案されたもので、stride scheduling という名称でCPUスケジューリングに適用されたことがあった。しかしCFSは均等化キューイングでの一般的用語を採用していない。"service error"(プロセスが実際に得たCPU時間と予期されていたCPU時間の差)はLinuxでの実装では "wait_runtime" と呼ばれ、"queue virtual time" (QVT) という用語は "fair_clock" とされている。

CFSスケジューラのスケジューリング複雑性は O(log N) で、N はランキュー英語版内のタスク数である。実行すべきタスクの選択は一定時間で可能だが、赤黒木でランキューを実装しているため、実行後のタスクを木に戻すには O(log N) 回の操作を必要とする。

汎用OSで均等化キューイングをスケジューラとして実装したのはCFSが最初である[4]

より公平なアルゴリズム

技術的には "Completely Fair Scheduler"(完全に公平なスケジューラ)という名称は正しくない。CFSが保証できるのは、「不公平」レベルが




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Completely_Fair_Scheduler」の関連用語

Completely_Fair_Schedulerのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Completely_Fair_Schedulerのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのCompletely Fair Scheduler (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS