Completely Fair Scheduler

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が保証できるのは、「不公平」レベルが ${\displaystyle O(n)}$ 未満であることだけである（${\displaystyle n}$はプロセス数）。「不公平」レベルがもっと低い（例えば ${\displaystyle O(\log n)}$）、より複雑なアルゴリズムも存在する。

2010年11月、デスクトップやワークステーション向けのより「公平」なスケジューラとして 2.6.38 カーネルのCFS用パッチが受理された。これはリーナス・トーバルズの示唆に基づいてマイク・ガルブレイスが開発したもので、多くのシステムでマルチタスク性能を「劇的に」向上させると期待されている^[5]。基本的アルゴリズムの実装はマイク・ガルブレイス自身のLKMLへのポストで説明されている^[6]。

それによって解決される最大の課題は、マルチコアやマルチCPU (SMP) のシステムで、多数のスレッドで構成されるタスクが存在したときにユーザーとの対話における応答時間が長くなるという問題である。簡単に説明すれば、Linuxカーネルのコンパイルや動画のエンコーディングなどといったプロセスを実行している状態でも、動画の表示し、電子メールを読むなどといった一般的なデスクトップ的活動で応答に違和感がないようにする。ただし、これには異論もある。

このパッチではttyタスクグループのみを公平クラスのタスクとし、拡張の余地を残している。このパッチでの基本的実装だけでも、応答性能が低いと考えてLinuxをデスクトップ用途で使うことをためらっていたユーザーへの解決策を与えているという^[7]。リーナス・トーバルズはそれについて次のように述べている^[8]。

だから私はこれが確実に「本当の改良」パッチだと思っている。グッジョブ。グループスケジューリングは「特定のサーバ負荷に役立つ」ものから「キラー機能」となった。

論争

同じくLKMLでのポスト^[9]でレッドハットの Lennart Poettering はこれがポリシーを含む変更であるとし、UNIX哲学である「ポリシーをメカニズムから分離せよ」に反していると主張した。彼はまたこのパッチと同等の改良をシェルスクリプトで実装してみせ^[10]、その改造をカーネルに加える必要がないことを示した。そのスクリプトを Markus Trippelsdorf がテストし^[11]、カーネルパッチ版よりもうまく機能すると評価した。

また Lennart Poettering は次のように述べて、そのパッチの有効性に疑念を呈した^[12]。

このパッチが有効なのは、xterm から -j オプション付きで一日中カーネルをビルドしながら、同時に動画を見たいという人々だけである。

リーナス・トーバルズはこのパッチをカーネルに含めるべきだと考えているが、スケジューラのグループ化をデスクトップポリシーとして実装することの価値も理解している^[13]。

実のところ、私はデスクトップランチャーが "launch in a group"（もっとよい名称が必要だと思う）というオプションを持つことが悪いことだとは全く思わない。…だから私は自動グループ化機能によって他のグループ化の判断ができなくなるとも思っていない。

脚注

1. Molnár, Ingo (13 April 2007). "[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]". linux-kernel (Mailing list).
2. Andrews, Jeremy (2007年4月18日). “Linux: The Completely Fair Scheduler”. KernelTrap. 2012年6月29日時点のオリジナルよりアーカイブ。2012年9月12日閲覧。^{[リンク切れ]}
3. Linux カーネル 2.6 Completely Fair Scheduler の内側 ibm.com
4. Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin
5. The ~200 Line Linux Kernel Patch That Does Wonders
6. LKML
7. The Linux desktop may soon be a lot faster
8. LKML
9. LKML
10. Lennart's first implementation
11. Markus' test against Lennart's script
12. Re: [RFC/RFT PATCH v3 sched: automated per tty task groups] Lennart's interpretation of the patch
13. [1]

関連項目

• Brain Fuck Scheduler

外部リンク

• Corbet, Jonathan (2007年4月17日). “Schedulers: The Plot Thickens”. LWN.net. 2012年9月11日閲覧。
• Corbet, J. (2007年7月2日). “CFS Group Scheduling”. LWN.net. 2012年9月11日閲覧。