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

關(guān)鍵詞：完全公平調(diào)度法；計(jì)算機(jī)技術(shù)；公平

中圖分類號(hào)：TP316.81 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-7712 (2012) 06-0159-01

一、引言

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

二、CFS概述

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

三、CFS算法

（一）周期性調(diào)度函數(shù)

系統(tǒng)時(shí)鐘中斷調(diào)用周期性調(diào)度函數(shù)，即Scheduler-tick()，對運(yùn)行隊(duì)列信息進(jìn)行更新并執(zhí)行相關(guān)調(diào)度操作，其主要流程表現(xiàn)如下：

（1）對本地CPU的運(yùn)行隊(duì)列負(fù)載、時(shí)間戳等信息進(jìn)行更新，之后轉(zhuǎn)入CFS調(diào)度類task_tick函數(shù)——task_tick_fair()

（2）對GFS運(yùn)行隊(duì)列和執(zhí)行進(jìn)程相關(guān)信息進(jìn)行更新，更新在update-curr()中進(jìn)行。這種操作構(gòu)成函數(shù)中斷處理的重要內(nèi)容和核心步驟。

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

首先，需要對CFS隊(duì)列中每一進(jìn)程被調(diào)度以此的時(shí)間周期period進(jìn)行計(jì)算；

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

cfs_rq-＞load為cfs_rq的負(fù)載，這一數(shù)值的增加在進(jìn)程出列時(shí)則會(huì)減小，curr-＞load.weight為nice對應(yīng)的weight數(shù)值。通過上述公式能夠發(fā)現(xiàn)，系統(tǒng)負(fù)載與ideal_runtime之間呈現(xiàn)負(fù)相關(guān)；nice與se-＞load.weight、ideal_runtime呈現(xiàn)負(fù)相關(guān)。

再次，計(jì)算進(jìn)程已經(jīng)占用的CPU時(shí)間。

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

式中prev_sum_exec_runtime代表進(jìn)程被切換到CPU時(shí)sum_exec_runtime。

最后，比較進(jìn)程占用CPU時(shí)間delta_exec是否比ideal_runtime要大。如果執(zhí)行時(shí)間超過ideal_runtime則會(huì)用resched_task（）設(shè)置此進(jìn)程的搶占標(biāo)志位，同時(shí)在tick中斷返回過程中調(diào)用schedule（）完成調(diào)度。

（二）主調(diào)度函數(shù)

schedule（）即主調(diào)度函數(shù)，包括主動(dòng)與被動(dòng)兩種方式，schedule（）功能表現(xiàn)為在運(yùn)行隊(duì)列中選擇被調(diào)度的進(jìn)程，同時(shí)對調(diào)度信息進(jìn)行有效更新。主調(diào)度函數(shù)如下：

（1）禁止初始化局部變量、清除調(diào)度標(biāo)志位、內(nèi)核搶占、執(zhí)行相關(guān)鎖操作等；

（2）在put_prev_task_fair（）中將目前執(zhí)行的程序放到運(yùn)行隊(duì)列。

首先，對當(dāng)前運(yùn)行進(jìn)程up-data_curr（）和cfs-rq進(jìn)行有效更新；其次，在進(jìn)程插入紅黑樹后，排序鍵值key在_enqueue_entity中變?yōu)椋簊e_＞vruntime-cfs_rq-＞min_vruntime。

（3）在pick_next_task_fair（）中將CPU分配到下一個(gè)被調(diào)度的進(jìn)程中。

首先，選擇結(jié)點(diǎn)se（紅黑樹最左側(cè)），之后進(jìn)行兩次條件判斷，分別為是否被cfs_rq-＞next搶占、是否被cfs_rq-＞last搶占。之后決定下一個(gè)被調(diào)度進(jìn)程。

其次，在選出下一個(gè)被調(diào)度進(jìn)程之后，需要采用set_next_entity（）設(shè)置所選擇的進(jìn)程的信息，在_dequeue_entity（）中實(shí)現(xiàn)。

四、CFS總結(jié)

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

參考文獻(xiàn)：

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

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

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