差分
プロセスにCPU資源をどのように与えるかの順番を決めるスケジュール (schedule)ことを行うことがスケジューリング(scheduling)です。それを司るのがスケジュラです。それを司るのがスケジューラ(scheduler)です。
==== 基本的なスケジュリング方式 ====
Linux 2.6系におけるスケジューラは以前2.4系で使われていたスケジューラからみると画期的に性能がいいO(1)スケジュラスケジューラ(Order one scheduler)に変更されました。さらにLinux 2.6.23からO(1)スケジュラからCFSスケジューラからCFS(Completely Fair Scheduler)に変更されました。
その後 Linux 3.14 (2014/3/20リリース) からリアルタイム指向の処理に必要なデットラインを処理するための [https://core.ac.uk/download/pdf/14699805.pdf SCHED_DEADLINE] がスケジュラ がスケジューラ <ref> デフォルトで使えるかどうかはディストリビューションによります。</ref> に加わっています。Linux 3.14ではデットライン・スケジュラーのアルゴリズムはEarliest 14ではデットライン・スケジューラのアルゴリズムはEarliest Deadline First (EDF)を採用していましたが、Linux 4.13 (2017/9/5リリース)からはEDFを改良しさらに Constant Bandwidth Server ( CBS ) 加えた [https://uc2.h2np.net/src/deadline_c.html#N1 ( と、カーネルのコメントでは表現している ）] アルゴリズムを採用しています。
</ref>
は、
O(1)スケジュラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS スケジューラがヒューリスティック（発見的）にスケジューリングしていたのに対し、CFS のスケジューリングは（数学的な意味で）数値を計算してスケジューリングを決めます。
ヒューリスティックな方法では、ある種の特定の条件に嵌まってしまいスケジューリングが公平に処理できなくなったり、あるいは偶然に有利な条件になったり不利な条件になったりとする可能性があります。
それに比べCFSは公平にスケジューリングされます。
それまでの Linux のスケジューラーは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種であるのスケジューラは、タスクを管理するキューをもち、その中で処理をしていました。CFSでは平衡2分探索木の一種である
赤黒木
<ref>
あるいはさらなる効率化のために変更される可能性は十分にあります。
これからも、あちらこちらの腕利きのカーネルハッカーがどんどん新しい提案をしてくることでしょう。
