完全公平排程器（CFS）與 EEVDF

排程器該如何公平地在眾多工作之間分配 CPU 時間？一個自然的想法：想像一臺理想機器，能讓全部 N 個可執行工作字面上同時跑，每個恰好得到 CPU 速度的 1/N。真實 CPU 做不到，但你可以逼近它：追蹤每個工作實際得到了多少 CPU 時間，並且總是接下來執行那個落後其公平份額最多的工作。這就是 Linux 完全公平排程器（CFS）背後的理念，它擔任 Linux 預設行程排程器逾十五年。

具體而言，CFS 給每個工作一個虛擬執行時間（virtual runtime）——大致就是它消耗了多少 CPU 時間，並依其優先順序加權（優先順序較高／nice 較低的工作，虛擬執行時間累積得較慢，所以被允許跑得更多）。排程器把可執行工作依虛擬執行時間排在一棵自我平衡的樹（紅黑樹）裡，並總是挑虛擬執行時間最小的工作——相對其權重最被餓著的那個——接下來執行。當那個工作執行時，它的虛擬執行時間攀升，最終另一個工作變成最落後的，輪到它。這自然地把更多 CPU 交給得到較少的工作，而不必為每個工作設固定時間片。2023 年 Linux 把 CFS 的核心換成 EEVDF（最早合格虛擬截止期優先），它保留公平的理念，但加入明確的延遲／截止期概念，使它能更好地服務需要快速回應的工作。

有兩件事值得記住。第一，這裡的「公平」是加權公平，而非人人時間相同——優先順序（nice）傾斜各工作的份額，所以高優先順序的工作公平地得到更多，而非均等的一份。第二，CFS 與 EEVDF 只是數個排程類別之一：核心讓即時排程類別（給有嚴格時序需求的工作）以嚴格高於一般／公平類別的優先順序執行，所以「完全公平」描述的是普通工作如何在即時工作取走所需之後，分享剩下的 CPU。教訓是：即便一個優雅的公平演算法，也是一個刻意的取捨，與服務不同種類工作的其他策略層疊在一起。