CFS
Linux 2.6.23から採用されたCFS(Completely Fair Scheduler)はLinux 6.6（2023年10月30日リリース）からEEVDF(Earliest eligible virtual deadline first)に置き換えられました。 ここには記録のため、以前のCFSの説明で使った内容をそのまま乗せておきます。
CFS
Linux 2.6.23からCFS(Completely Fair Scheduler) [1] は、O(1) スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。 ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジューリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。 それに比べCFSは公平にスケジューリングされます。
それまでの Linux のスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である
赤黒木
[2]
というデータ構造を使いタスクを管理します。タスクは仮想実行時間という値を持ち、タスクが実行されるとこの値は増えます。タスク管理のツリーに戻される時、この仮想実行時間の値によってツリー中の適切な位置に置かれます。このツリーの中で最も値の小さいものが次に実行されるべきタスクとなります。こうすることによってCFSは計算量はO(log n)で、適切なタスクを選ぶという操作が可能になっています。
今後もある意味オペレーティングシステムの心臓部ともいえるスケジューラが色々な要件を満たすため、あるいはさらなる効率化のために変更される可能性は十分にあります。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。
スケジューラのチューニング
スケジューラのチューニングに関しては下記の情報が参考になります。
- SUSE タスクスケジューラのチューニング
- Red Hat Enterprise Linux 9 第30章 スケジューリングポリシーの調整
- ↑ Inside the Linux 2.6 Completely Fair Scheduler https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ (リンク切れ) Linux カーネル 2.6 Completely Fair Scheduler の内側 http://www.ibm.com/developerworks/jp/linux/library/l-completely-fair-scheduler/
- ↑ 赤黒木がどう生成され管理されるかビジュアルで示してくれるサイトです。挿入(insert)、削除(delete)、検索(find)の操作をすると、どうRed/Black Treeが作られるか/操作されるかがビジュアルでわかります。 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html