關于完全公平調度算法的研究與分析

摘要：GFS調度法是Linux最新研制的調度算法，表現出很強的有異性。GFS涉及能夠有效促進處理器資源的公平與共享。本文主要分析了GFS調度算法的特性與工作流程，從算法分析與Hackbench測試兩方面對CFS與O（1）性能進行對比分析與研究

關鍵詞：完全公平調度法；計算機技術；公平

中圖分類號：TP316.81 文獻標識碼：A 文章編號：1674-7712 (2012) 06-0159-01

一、引言

操作系統的一項核心功能表現在進程調度方面，進程調度主要是對處理器資源進行合理公平的分配。調度算法應該以實現效率與公平作為其目標，并促進周轉時間、吞吐量、響應時間等目標之間的平衡[1]。Linux從使用調度算法以來，不斷經歷了O（1）、RSDL、SD、CFS調度算法，CFS相對O（1）有了很大的進步，簡化了代碼，突出了公平的核心思想。

二、CFS概述

GPS采用virtual runtime來描述CPU上的執行時間，在調度的過程中，CFS為保證每個進程有基本相似的執行時間，會選擇執行時間最小的進程來運行，從而達到任務執行時間的相對平衡。CFS調度法相對于O（1）來講有了很大的進步，比如能夠區分交互式進程，不跟蹤睡眠時間，所以代碼思路相對簡單。另外還增加了組調度的功能，以保證組與用戶的公平。同時不再采用優先級數組，將就緒態進程插入紅黑樹，并以此來選擇下一個調度進程。一般每一個調度模塊都需要執行調度類以為其制定一組函數，以簡化需要修改進程杜奧杜算法時的程序。

三、CFS算法

（一）周期性調度函數

系統時鐘中斷調用周期性調度函數，即Scheduler-tick()，對運行隊列信息進行更新并執行相關調度操作，其主要流程表現如下：

（1）對本地CPU的運行隊列負載、時間戳等信息進行更新，之后轉入CFS調度類task_tick函數——task_tick_fair()

（2）對GFS運行隊列和執行進程相關信息進行更新，更新在update-curr()中進行。這種操作構成函數中斷處理的重要內容和核心步驟。

（3）對是否需要搶占當前進程進行有效判斷，這一過程在check_preempt_tick()中進行。

首先，需要對CFS隊列中每一進程被調度以此的時間周期period進行計算；

其次，對目前進程所允許占用的時間，即ideal_runtime進行計算，表現為：ideal_runtime=period*curr-＞load.weight/cfs_rq-＞load[2]

cfs_rq-＞load為cfs_rq的負載，這一數值的增加在進程出列時則會減小，curr-＞load.weight為nice對應的weight數值。通過上述公式能夠發現，系統負載與ideal_runtime之間呈現負相關；nice與se-＞load.weight、ideal_runtime呈現負相關。

再次，計算進程已經占用的CPU時間。

delta_exec=curr-＞sum_exec_runtime-curr-＞prev_sum_exec_runtime[3]。

式中prev_sum_exec_runtime代表進程被切換到CPU時sum_exec_runtime。

最后，比較進程占用CPU時間delta_exec是否比ideal_runtime要大。如果執行時間超過ideal_runtime則會用resched_task（）設置此進程的搶占標志位，同時在tick中斷返回過程中調用schedule（）完成調度。

（二）主調度函數

schedule（）即主調度函數，包括主動與被動兩種方式，schedule（）功能表現為在運行隊列中選擇被調度的進程，同時對調度信息進行有效更新。主調度函數如下：

（1）禁止初始化局部變量、清除調度標志位、內核搶占、執行相關鎖操作等；

（2）在put_prev_task_fair（）中將目前執行的程序放到運行隊列。

首先，對當前運行進程up-data_curr（）和cfs-rq進行有效更新；其次，在進程插入紅黑樹后，排序鍵值key在_enqueue_entity中變為：se_＞vruntime-cfs_rq-＞min_vruntime。

（3）在pick_next_task_fair（）中將CPU分配到下一個被調度的進程中。

首先，選擇結點se（紅黑樹最左側），之后進行兩次條件判斷，分別為是否被cfs_rq-＞next搶占、是否被cfs_rq-＞last搶占。之后決定下一個被調度進程。

其次，在選出下一個被調度進程之后，需要采用set_next_entity（）設置所選擇的進程的信息，在_dequeue_entity（）中實現。

四、CFS總結

從上述分析中可以發現CFS與之前的調度器有很大不同，發生了很大的改進。CFS突出完全公平的思想，以對進程執行時間的追逐來調度任務，通過以紅黑樹代替之前采用的優先級數組來決定被調度的進程，將調度類引入以有效增強代碼的可維護性與內核調度程序的擴展性。同時代碼中也將之前較難理解的公式進行去除，使得整個思路相對清楚，也提高了算法的實用性。但CFS同時也有一些負面的報告，需要在以后的研究中不斷完善。

參考文獻：

[1]朱旭，楊斌，劉海濤.完全公平調度算法分析[J].成都信息工程學院學報，2010，25(1):18-21

[2]王輝，李津生，洪佩琳.802.11WLAN中一種基于循環隊列的分布式公平隊列調度算法[J].電子與信息學報，2004，26(10):1540-1547

[3]趙旭，夏靖波.基于RTAI的Linux系統實時性研究與改進[J].計算機工程，2010，36(14):288-290