前言

上次講完了過去 Linux 的排程器，今天就來講講

CFS (complete fair scheduler)

在 Linux 核心的文件 CFS Scheduler，嘗試以一句話說明原理:

80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.
CFS 使用的資料結構並不是一個 queue，而是一個紅黑樹。會使用任務的 virtual runtime 來產生紅黑樹，並且每次都挑選最小的 virtual runtime 來執行，達到公平的目的（vruntime 就是每個任務理想中會被執行的時間，最小 vruntime 的任務就會是目前理想執行時間最少的任務）。

在CFS中，對於每個行程的運行時間的紀錄，是放在每個task中的 p->se.vruntime，每次CFS選取任務時就是選曲整個紅黑樹中，p->se.vruntime最小的行程