Linux內核完全公平調度器改進的研究

朱永華，沈熠，劉玲

1.上海大學計算中心，上海 200444

2.上海大學計算機工程與科學學院，上海 200444

Linux內核完全公平調度器改進的研究

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

1.上海大學計算中心，上海 200444

2.上海大學計算機工程與科學學院，上海 200444

針對現有Linux內核使用的完全公平調度器無法有效解決貪婪線程問題，提出一種改進的調度算法和該算法的高效實現，該算法通過懲罰貪婪線程的方法提升調度器的公平性。實驗結果證實，貪婪線程問題存在；改進后的調度算法有效減少了存在貪婪線程問題的程序對降低系統整體性能的影響。

Linux內核；任務調度；完全公平調度

1 引言

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

2 Linux調度器現狀

2.1 CFS

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

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

vruntime越小，就越靠近紅黑樹的左側，也就會被更早調度。nice值為0的虛擬運行時間與實際運行時間是相同的。

2.2 CFS的問題

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

假設用戶A有2個進程，用戶B有8個進程。若此時調度粒度為進程，那么調度結果會對用戶A不公平。組調度的目的就是讓用戶A與B各自得到50%的CPU資源。通過調用Sched_autogroup.c中定義的系統調用，將多個進程打包為組，達到公平的目的。

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

圖1 例1中CPU資源分配圖

圖2 例2中CPU資源分配圖

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

3 改進算法研究

3.1 現有改進算法及其不足

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

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

圖3 例2中使用PFS調度策略后CPU資源分配圖

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

（1）經過合理多線程優化（well-threaded）的程序并沒有得到合理的對待，它與其單線程版本程序相比并沒有得到應有的優待，相反會因為線程切換帶來的性能開銷而造成其運行效率反不如單線程版本程序。

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

3.2 改進策略分析

現有Linux內核CFS的調度粒度為線程，PFS的調度粒度為進程。所要尋找的調度算法其粒度應設定為兩者之間，通過對擁有不同線程數的程序的線程權重調節，達到算法改進的目的。改進后的算法需要滿足以下幾點：

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

（2）優待多線程程序。通過將串行算法改變為并行算法以達到提升性能的程序應優先得到計算資源。在文獻[2]中提出的PFS并沒有給多線程應用應有的優待，然而應給予并行算法優待。但需要在一定線程數限制下，提高其運行權重。

（3）顧全大局。在多線程程序優先獲得計算資源的同時，不能因為過于優先以至于搶占了其他程序應獲得的計算資源。對于貪婪地創建線程的程序，應對其進行“懲罰”，減少運行權重。

3.3 DW-CFS（Dynamic Weight Complete Fair Scheduler）

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

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

定義2（程序線程數）當前調度實體共享內存空間的線程數（用Nt表示）。一個程序的線程數是設定線程初始權重的依據，創建一定數據量的線程會提升程序的總優先級，但過度數量的線程則會被“懲罰”。每當新的線程被創建時，通過對copy_signal（）函數中signal結構體的count累加來計數，并更新nr_thread的計數，實現記錄線程數的目的。

為了實現改進，現提出DW-CFS算法。該改進算法改變了調度實體的權重計算方式，公式如下：

其中權重調節因子β是一個常數，用以表示可獲得額外權重的最大值，改進后的權重W'與三個參數需要滿足一下條件：

（1）當Nt≤No時，若Nt越大，則W'越大，反之越小。

（2）當Nt＞No時，若Nt越大，則W'越小，反之越大。

（3）當Nt=1時，W'=W。

在DW-CFS算法中，原有累計vruntime的公式（1）變為如下公式：

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

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

為了優化公式計算，以減少調度器在計算權重時的開銷，該公式的實現算法可由如下偽代碼表示。

圖4 權重調節函數(No=4，β=1.1)

4 實驗結果及分析

4.1 實驗環境

實驗平臺說明如表1所示。

表1 實驗平臺配置

4.2 實驗方法

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

圖5 測試程序流程圖

圖6 （a）改進前測試結果

圖6 （b）進程A（單線程）改進前后對比

圖6 （c）進程B（多線程）改進前后對比

4.3 實驗結果及分析

圖6（a）與圖6（b）描述了改進前后單線程與多線程算法在不同線程數下的運行情況。

根據圖6所示實驗結果可得出以下結論：

（1）由圖6（a）中進程B的運行結果得知，多線程任務確實可以減少運行時間。由于測試使用平臺為雙核四線程，當程序達到四線程后，進程B運行時間減少效果開始不明顯，但運行時間仍然繼續減少，其原因為該進程由于線程數量的優勢增大了該進程被調度的整體幾率，即搶占了系統其他程序運行機會，證實了CFS存在調度不公平的問題。

（2）由圖6（a）中進程A運行結果得知，單線程版本的程序的運行時間隨著同時運行的多線程版本程序的線程數的增加而增加，表明過多的線程搶占了系統其他程序的運行機會從而使單線程版本的程序運行時間增加，進一步證實了CFS存在調度不公平的問題；進程A在與其同時運行的進程B達到四線程前仍能減少運行時間，是因為CPU使用了Turbo Boost特性，可以提升單任務的執行效率。

（3）由圖6（b）與圖6（c）中運行結果（線程數[1，3]區間）得知，在進程A與進程B線程數總和達到最優線程數（實驗中No=4）之前，進程B因為得到更高的權重，其vruntime累計得更少，更靠近紅黑樹的左側，更快被調度，最終比CFS改進前更快完成。同時進程A由于進程B的更快完成，受益于CPU的Turbo Boost特性，也降低了運行時間。

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

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

5 結束語

本文從Linux內核的CFS研究出發，討論了完全公平調度策略與該調度器的不足，介紹了研究改進的現狀。在此基礎上提出了DW-CFS，該算法基于對程序線程數的檢測，通過程序線程數與在線核心數的比較，調整其權重，改變調度結果，使得良好優化的多線程程序得到調度的優先；同時避免了程序利用CFS在貪婪線程問題上的處理不足，搶占系統大量資源。實驗表明DW-CFS有效減少貪婪線程對降低系統整體性能影響。

[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.

國家高技術研究發展計劃（863）重點項目（No.2009AA012201）。

朱永華（1967—），男，博士，副教授，主要研究領域為高性能計算、通信與信息工程；沈熠（1989—），男，碩士研究生，主要研究領域為高性能計算與系統算法；劉玲（1977—），女，助理實驗師。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