朱永華，沈熠，劉玲

1.上海大學(xué)計算中心，上海 200444

2.上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院，上海 200444

Linux內(nèi)核完全公平調(diào)度器改進(jìn)的研究

朱永華1，沈熠2，劉玲1

1.上海大學(xué)計算中心，上海 200444

2.上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院，上海 200444

針對現(xiàn)有Linux內(nèi)核使用的完全公平調(diào)度器無法有效解決貪婪線程問題，提出一種改進(jìn)的調(diào)度算法和該算法的高效實(shí)現(xiàn)，該算法通過懲罰貪婪線程的方法提升調(diào)度器的公平性。實(shí)驗(yàn)結(jié)果證實(shí)，貪婪線程問題存在；改進(jìn)后的調(diào)度算法有效減少了存在貪婪線程問題的程序?qū)档拖到y(tǒng)整體性能的影響。

Linux內(nèi)核；任務(wù)調(diào)度；完全公平調(diào)度

1 引言

隨著Linux內(nèi)核[1]的不斷改進(jìn)，功能的不斷完善，其性能越來越強(qiáng)。其中，任務(wù)調(diào)度算法經(jīng)歷了許多版本的改進(jìn)：Linux 2.4內(nèi)核的O(n)算法和Linux 2.6早期版本的O(1)算法都是基于Linux早期版本的調(diào)度思想，但存在著代碼結(jié)構(gòu)復(fù)雜、進(jìn)程饑餓、大量經(jīng)驗(yàn)公式等問題[2-4]；自Linux 2.6.23內(nèi)核使用了新的完全公平調(diào)度器（Completely Fair Scheduler，CFS）[5-6]，該調(diào)度器以公平思想為調(diào)度原則。

2 Linux調(diào)度器現(xiàn)狀

2.1 CFS

CFS由Ingo Molnar提出，它從Con Kolivas的SD（Staircase Scheduler）與其改進(jìn)版本RSDL（Rotating Staircase Deadline Scheduler）中吸取了完全公平的思想，將所有進(jìn)程都統(tǒng)一對待，不再區(qū)別對待交互進(jìn)程與普通進(jìn)程。“80%的CFS算法的設(shè)計可以總結(jié)為一句話：CFS在真實(shí)硬件上模擬了一個‘理想的、精準(zhǔn)的多任務(wù)CPU’”[7]。該調(diào)度器的思想是，兩個性質(zhì)、優(yōu)先級、運(yùn)算量相同的進(jìn)程同時運(yùn)行，其運(yùn)行結(jié)束時間應(yīng)該是近乎一致的。

Linux的非實(shí)時調(diào)度器是以優(yōu)先級為計算基礎(chǔ)的，設(shè)置了static_prio，normal_prio，prio三個優(yōu)先級參數(shù)。由于CFS的對象是普通非實(shí)時的調(diào)度實(shí)體（sched_entity），故三者的值相等，均為static_prio。該參數(shù)由nice值給出，nice值的值域[-20，19]映射到優(yōu)先級數(shù)值區(qū)間[100，139]。調(diào)度實(shí)體的重要性不僅由優(yōu)先級指定，還需考慮該調(diào)度實(shí)體在就緒隊(duì)列（CFS中使用紅黑樹[8]）中的權(quán)重。調(diào)度實(shí)體的優(yōu)先級影響其權(quán)重，其權(quán)重影響了每次累計的vruntime，其在紅黑樹中位置由虛擬運(yùn)行時間(vruntime)決定。通過sched.c中定義的prio_to_weight[]數(shù)組維護(hù)優(yōu)先級至權(quán)重的轉(zhuǎn)換關(guān)系。調(diào)度實(shí)體每提升一個優(yōu)先級，則多獲得10%的CPU時間。CFS通過平衡紅黑樹中每個調(diào)度實(shí)體的vruntime達(dá)到公平調(diào)度的目的。不同優(yōu)先級實(shí)際運(yùn)行時間與虛擬運(yùn)行時間的比值是不同的，通過以下公式累積vruntime：

vruntime越小，就越靠近紅黑樹的左側(cè)，也就會被更早調(diào)度。nice值為0的虛擬運(yùn)行時間與實(shí)際運(yùn)行時間是相同的。

2.2 CFS的問題

雖然完全公平的調(diào)度策略思想先進(jìn)，且在大部分的實(shí)際情況下達(dá)到了公平調(diào)度的目的，但存在一些額外情況。如用戶可以通過fork（）調(diào)用創(chuàng)建多個子進(jìn)程，這樣可以使自己任務(wù)得到更多的CPU時間已達(dá)到更快處理的目的，CFS為了解決該問題，引入了組調(diào)度。

假設(shè)用戶A有2個進(jìn)程，用戶B有8個進(jìn)程。若此時調(diào)度粒度為進(jìn)程，那么調(diào)度結(jié)果會對用戶A不公平。組調(diào)度的目的就是讓用戶A與B各自得到50%的CPU資源。通過調(diào)用Sched_autogroup.c中定義的系統(tǒng)調(diào)用，將多個進(jìn)程打包為組，達(dá)到公平的目的。

類似的問題會出現(xiàn)在多線程的程序調(diào)度中，用戶仍可以通過創(chuàng)建多個線程獲得更多的CPU時間。假設(shè)某情形（例1）：有三個進(jìn)程A，B，C，分別擁有1，2，2個線程，此時CPU的資源分配情況如圖1所示。其中period為調(diào)度延遲值，即每個可運(yùn)行的調(diào)度實(shí)體至少運(yùn)行一次的時間。如圖1所示，似乎CFS公平地為三個進(jìn)程分配CPU資源，然而換一種情形（例2）：同樣有三個進(jìn)程A，B，C，分別擁有1，1，8個線程，此時CPU的資源分配情況如圖2所示。

圖1 例1中CPU資源分配圖

圖2 例2中CPU資源分配圖

如圖2所示，進(jìn)程A，B的運(yùn)行時間大大被壓縮，系統(tǒng)大部分計算資源被分配給進(jìn)程C，這樣就違背了公平原則。

3 改進(jìn)算法研究

3.1 現(xiàn)有改進(jìn)算法及其不足

已有提出并實(shí)現(xiàn)了一種解決方案PFS（Process Fair Scheduler）[9]，該方案借用組調(diào)度的思想，將調(diào)度粒度提升至進(jìn)程，即對于之前的例子將如下分配CPU時間。其權(quán)重計算公式為：

其中α為進(jìn)程的線程數(shù)。根據(jù)新的權(quán)重計算方式，在例2描述的情形中CPU的資源分配情況如圖3所示。

圖3 例2中使用PFS調(diào)度策略后CPU資源分配圖

如圖3所示，進(jìn)程A，B，C之間被“公平”地對待，各自享有均等的計算資源。但上述算法也并非完全合理，有以下兩個問題：

（1）經(jīng)過合理多線程優(yōu)化（well-threaded）的程序并沒有得到合理的對待，它與其單線程版本程序相比并沒有得到應(yīng)有的優(yōu)待，相反會因?yàn)榫€程切換帶來的性能開銷而造成其運(yùn)行效率反不如單線程版本程序。

（2）若不友好（greedy-threaded）的進(jìn)程嘗試創(chuàng)建多個線程以獲得CPU運(yùn)行時間，那么其切換頻率會非常頻繁，造成大量CPU和I/O開銷，最終導(dǎo)致調(diào)度器選擇下一個調(diào)度實(shí)體的次數(shù)增多，嚴(yán)重影響整體性能。

3.2 改進(jìn)策略分析

現(xiàn)有Linux內(nèi)核CFS的調(diào)度粒度為線程，PFS的調(diào)度粒度為進(jìn)程。所要尋找的調(diào)度算法其粒度應(yīng)設(shè)定為兩者之間，通過對擁有不同線程數(shù)的程序的線程權(quán)重調(diào)節(jié)，達(dá)到算法改進(jìn)的目的。改進(jìn)后的算法需要滿足以下幾點(diǎn)：

（1）避免復(fù)雜計算。調(diào)度器的運(yùn)行頻率為毫秒級，若其本身就需要占有系統(tǒng)很大一部分的計算資源，那將本末倒置，系統(tǒng)整體性能也將下降。CFS很好地避免了檢測交互式進(jìn)程與“懲罰”非交互式進(jìn)程所需要的大量的啟發(fā)式計算（由__normal_prio（）完成），不應(yīng)引入過于復(fù)雜的公式計算。

（2）優(yōu)待多線程程序。通過將串行算法改變?yōu)椴⑿兴惴ㄒ赃_(dá)到提升性能的程序應(yīng)優(yōu)先得到計算資源。在文獻(xiàn)[2]中提出的PFS并沒有給多線程應(yīng)用應(yīng)有的優(yōu)待，然而應(yīng)給予并行算法優(yōu)待。但需要在一定線程數(shù)限制下，提高其運(yùn)行權(quán)重。

（3）顧全大局。在多線程程序優(yōu)先獲得計算資源的同時，不能因?yàn)檫^于優(yōu)先以至于搶占了其他程序應(yīng)獲得的計算資源。對于貪婪地創(chuàng)建線程的程序，應(yīng)對其進(jìn)行“懲罰”，減少運(yùn)行權(quán)重。

3.3 DW-CFS（Dynamic Weight Complete Fair Scheduler）

為了描述該算法，需要對以下概念進(jìn)行定義：

定義1（在線核心數(shù)）當(dāng)前工作的處理器核心數(shù)，即可用邏輯計算核心數(shù)（用No表示）。一般情況下系統(tǒng)的計算核心數(shù)從內(nèi)核啟動后不發(fā)生變化；但若開啟熱插拔后，在線核心數(shù)（online_cpu）可以發(fā)生變化。

定義2（程序線程數(shù)）當(dāng)前調(diào)度實(shí)體共享內(nèi)存空間的線程數(shù)（用Nt表示）。一個程序的線程數(shù)是設(shè)定線程初始權(quán)重的依據(jù)，創(chuàng)建一定數(shù)據(jù)量的線程會提升程序的總優(yōu)先級，但過度數(shù)量的線程則會被“懲罰”。每當(dāng)新的線程被創(chuàng)建時，通過對copy_signal（）函數(shù)中signal結(jié)構(gòu)體的count累加來計數(shù)，并更新nr_thread的計數(shù)，實(shí)現(xiàn)記錄線程數(shù)的目的。

為了實(shí)現(xiàn)改進(jìn)，現(xiàn)提出DW-CFS算法。該改進(jìn)算法改變了調(diào)度實(shí)體的權(quán)重計算方式，公式如下：

其中權(quán)重調(diào)節(jié)因子β是一個常數(shù)，用以表示可獲得額外權(quán)重的最大值，改進(jìn)后的權(quán)重W'與三個參數(shù)需要滿足一下條件：

（1）當(dāng)Nt≤No時，若Nt越大，則W'越大，反之越小。

（2）當(dāng)Nt＞No時，若Nt越大，則W'越小，反之越大。

（3）當(dāng)Nt=1時，W'=W。

在DW-CFS算法中，原有累計vruntime的公式（1）變?yōu)槿缦鹿剑?/p>

滿足以上條件的α函數(shù)有很多，本文提出一個計算量小，與實(shí)際需求擬合度較高的計算公式：

其中β已用一個確定的值替代，其值表示當(dāng)Nt=No時，該線程可獲得10%權(quán)重提升。該函數(shù)以No為分界，當(dāng)Nt≤No時，函數(shù)單調(diào)遞增；當(dāng)Nt＞No時，函數(shù)單調(diào)遞減，且函數(shù)值收斂于0。當(dāng)No=4時該函數(shù)曲線如圖4所示。

為了優(yōu)化公式計算，以減少調(diào)度器在計算權(quán)重時的開銷，該公式的實(shí)現(xiàn)算法可由如下偽代碼表示。

圖4 權(quán)重調(diào)節(jié)函數(shù)(No=4，β=1.1)

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)平臺說明如表1所示。

表1 實(shí)驗(yàn)平臺配置

4.2 實(shí)驗(yàn)方法

相比于使用仿真軟件[10]，真實(shí)平臺所能反映的結(jié)果更準(zhǔn)確。本實(shí)驗(yàn)使用圓周率Π的計算[11]為測試程序，其算法復(fù)雜度為O(n)，n為精度。實(shí)驗(yàn)中同時啟動兩個進(jìn)程，進(jìn)程A為單線程版本的算法實(shí)現(xiàn)；進(jìn)程B為多線程版本的算法實(shí)現(xiàn)，線程數(shù)為m，其中m∈{1，2，3，4，5，6，7，8，16，32}。根據(jù)公平原則，兩者的結(jié)束時間應(yīng)接近一致。其中單線程版本程序A與多線程版本程序B同時運(yùn)行的流程圖如圖5所示。

圖5 測試程序流程圖

圖6 （a）改進(jìn)前測試結(jié)果

圖6 （b）進(jìn)程A（單線程）改進(jìn)前后對比

圖6 （c）進(jìn)程B（多線程）改進(jìn)前后對比

4.3 實(shí)驗(yàn)結(jié)果及分析

圖6（a）與圖6（b）描述了改進(jìn)前后單線程與多線程算法在不同線程數(shù)下的運(yùn)行情況。

根據(jù)圖6所示實(shí)驗(yàn)結(jié)果可得出以下結(jié)論：

（1）由圖6（a）中進(jìn)程B的運(yùn)行結(jié)果得知，多線程任務(wù)確實(shí)可以減少運(yùn)行時間。由于測試使用平臺為雙核四線程，當(dāng)程序達(dá)到四線程后，進(jìn)程B運(yùn)行時間減少效果開始不明顯，但運(yùn)行時間仍然繼續(xù)減少，其原因?yàn)樵撨M(jìn)程由于線程數(shù)量的優(yōu)勢增大了該進(jìn)程被調(diào)度的整體幾率，即搶占了系統(tǒng)其他程序運(yùn)行機(jī)會，證實(shí)了CFS存在調(diào)度不公平的問題。

（2）由圖6（a）中進(jìn)程A運(yùn)行結(jié)果得知，單線程版本的程序的運(yùn)行時間隨著同時運(yùn)行的多線程版本程序的線程數(shù)的增加而增加，表明過多的線程搶占了系統(tǒng)其他程序的運(yùn)行機(jī)會從而使單線程版本的程序運(yùn)行時間增加，進(jìn)一步證實(shí)了CFS存在調(diào)度不公平的問題；進(jìn)程A在與其同時運(yùn)行的進(jìn)程B達(dá)到四線程前仍能減少運(yùn)行時間，是因?yàn)镃PU使用了Turbo Boost特性，可以提升單任務(wù)的執(zhí)行效率。

（3）由圖6（b）與圖6（c）中運(yùn)行結(jié)果（線程數(shù)[1，3]區(qū)間）得知，在進(jìn)程A與進(jìn)程B線程數(shù)總和達(dá)到最優(yōu)線程數(shù)（實(shí)驗(yàn)中No=4）之前，進(jìn)程B因?yàn)榈玫礁叩臋?quán)重，其vruntime累計得更少，更靠近紅黑樹的左側(cè)，更快被調(diào)度，最終比CFS改進(jìn)前更快完成。同時進(jìn)程A由于進(jìn)程B的更快完成，受益于CPU的Turbo Boost特性，也降低了運(yùn)行時間。

（4）由圖6（b）與圖6（c）中運(yùn)行結(jié)果（線程數(shù)[4，7]區(qū)間）得知，由于進(jìn)程A與進(jìn)程B線程數(shù)總和超出最優(yōu)線程數(shù)，需要更多的調(diào)度，使其運(yùn)行時間均有增長。在此區(qū)間范圍內(nèi)，進(jìn)程B的“優(yōu)待”減少（Nt=8時，α=0.99，開始“懲罰”該進(jìn)程），獲得相對于其在Nt=4時較少的調(diào)度機(jī)會。如圖6（c）所示，進(jìn)程B在線程數(shù)超過No值后的提速效果較區(qū)間[1，3]中的效果小。

（5）由圖6（b）與圖6（c）中運(yùn)行結(jié)果（線程數(shù)[8，32]區(qū)間）得知，由于對進(jìn)程B過多線程數(shù)的“懲罰”力度不斷增大，其執(zhí)行時間比CFS改進(jìn)前不斷增大；同時進(jìn)程A由于能夠被更快地調(diào)度，其運(yùn)行時間也相比CFS改進(jìn)前有所減少。DW-CFS改進(jìn)效果得以說明。但是因?yàn)榫€程切換開銷和無法使用Turbo Boost特性，改進(jìn)效果被一定程度地抵消。

5 結(jié)束語

本文從Linux內(nèi)核的CFS研究出發(fā)，討論了完全公平調(diào)度策略與該調(diào)度器的不足，介紹了研究改進(jìn)的現(xiàn)狀。在此基礎(chǔ)上提出了DW-CFS，該算法基于對程序線程數(shù)的檢測，通過程序線程數(shù)與在線核心數(shù)的比較，調(diào)整其權(quán)重，改變調(diào)度結(jié)果，使得良好優(yōu)化的多線程程序得到調(diào)度的優(yōu)先；同時避免了程序利用CFS在貪婪線程問題上的處理不足，搶占系統(tǒng)大量資源。實(shí)驗(yàn)表明DW-CFS有效減少貪婪線程對降低系統(tǒng)整體性能影響。

[1]The Linux kernel archives[EB/OL].[2012-03-15].http：//www. kernel.org/.

[2]Mauerer W.Professional Linux kernel architecture[M].[S.l.]：Wiley Publishing，Inc，2008.

[3]Daniel P B，Marco C.Understanding the Linux kernel[M]. [S.l.]：O’Reilly Press，2005.

[4]Love R.Linux kernel development[M].[S.l.]：Noval Press，2010.

[5]Molnar I.Modular scheduler core and completely fair scheduler[EB/OL].（2007-05-11）.http：//lwn.net/Articles/230501/.

[6]Molnar I.CFS updates[EB/OL].[2012-04-10].http：//kerneltrap.org/Linux/CFS_Updates/.

[7]Andrew J.Interview：Ingo Molnar[EB/OL].[2012-04-17].http：// kerneltrap.org/?q=node/517.

[8]Thomas H C.Introduction to algorithms[M].[S.l.]：The MIT Press，2009.

[9]Chee S W，Ian T，Rosalind D K，et al.Towards achievingfairnessintheLinuxscheduler[J].OperatingSystems Review（ACM），2008，42（5）：34-43.

[10]John M C，Dan P B，Tong L，et al.LinSched：the Linux scheduler simulator[C]//ISCA PDCCS，2008：171-176.

[11]Pi[EB/OL].[2012-04-20].http：//en.wikipedia.org/wiki/Pi.

ZHU Yonghua1,SHEN Yi2,LIU Ling1

1.Computing Center,Shanghai University,Shanghai 200444,China
2.School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China

Fairness issue of the Completely Fair Scheduler（CFS）used in Linux kernel comes up due to the fact that programs with higher number of threads are favored by the scheduler,which are based on the number of thread in the system. A novel algorithm as well as its implementation through optimized procedure is proposed as a solution to achieve better fairness by punishing greedy-threaded programs.Several tests are conducted to illustrate fairness issue and to examine the effect of the proposed algorithm.

Linux kernel;process scheduling;complete fair scheduler

A

TP312

10.3778/j.issn.1002-8331.1211-0036

ZHU Yonghua,SHEN Yi,LIU Ling.Research on improving Linux completely fair scheduler.Computer Engineering and Applications,2014,50（21）：59-62.

國家高技術(shù)研究發(fā)展計劃（863）重點(diǎn)項(xiàng)目（No.2009AA012201）。

朱永華（1967—），男，博士，副教授，主要研究領(lǐng)域?yàn)楦咝阅苡嬎?、通信與信息工程；沈熠（1989—），男，碩士研究生，主要研究領(lǐng)域?yàn)楦咝阅苡嬎闩c系統(tǒng)算法；劉玲（1977—），女，助理實(shí)驗(yàn)師。E-mail：shenyi0828@gmail.com

2012-11-05

2013-01-25

1002-8331（2014）21-0059-04

CNKI出版日期：2013-03-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1040.005.html