完全公平排程器

维基百科,自由的百科全书
跳转至: 导航搜索

完全公平排程英语completely fair schedule,縮寫為CFS),Linux內核的一部份,負責行程排程,由匈牙利程式員英格·蒙內(Ingo Molnar)所提出,在Linux kernel 2.6.23採用,成為系統預設的排程器。它負責將CPU資源,分配給正在執行中的行程,目標在於最大化程式互動效能的同時,最小化整體CPU的運用。

CFS排程器參與先前Con Kolivas 所開發的楼梯调度算法(staircase scheduler)與RSDL(The Rotating Staircase Deadline Schedule)的經驗[1] ,選取花費CPU執行時間最少的行程來進行排程。CFS主要由sched_entity 內含的 vruntime所決定,不再跟踪process的sleep time,並揚棄active/expire的概念, runqueue裡面所有的进程都平等对待,CFS使用“虚拟运行时”(virtual running time)來表示某个任务的时间量。

CFS改使用紅黑樹演算法,將執行時間越少的工作(即 sched_entity)排列在紅黑樹的左邊[2],时间复杂度是O(log N),節點(即rb_node)的安插工作則由dequeue_entity()和enqueue_entity()來完成。当前執行的task通过呼叫 put_prev_task 返回红黑树,下一個待執行的task則由pick_next_task來呼叫。蒙內表示, CFS在百分之八十時間都在確實模拟处理器的處理時間。由於CFS的優異排程, 使得Linux 2.6.23 决定将CFS 合并到mainline 而放弃了RSDL。為此, Con Kolivas一度宣布脫離Linux開發團隊。

數年後, Con Kolivas 捲土重來, 重新開發腦殘排程器來對決 CFS, Jens Axboe 寫了一個名为 Latt.c 的程序進行比對,Jens 發現BFS 確時稍稍優於 CFS[3],而且CFS 的 sleeper fairness 在某些情況下會出現調度延遲。[4]Ingo不得不暫時關閉該特性,很快的在一周內提出新的 Gentle Fairness,徹底解決該問題。

背景[编辑]

CFS 是首支以公平佇列(fair queuing)的排程器可應用於一般用途作業系統(general-purpose operating system).[5]

注釋[编辑]