資源描述：
《linux內核之cfs調度和組調度》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、Linux內核之CFS調度和組調度作者：harveywang郵箱：harvey.perfect@gmail.com新浪博客地址：http://blog.sina.com.cn/harveyperfect，有關于減肥和學習英語相關的博文，歡迎交流Linux支持三種進程調度策略，分別是SCHED_FIFO、SCHED_RR和SCHED_NORMAL。Linux支持兩種類型的進程，實時進程和普通進程。實時進程可以采用SCHED_FIFO和SCHED_RR調度策略；普通進程采用SCHED_NORMAL調度策
2、略。本文主要討論普通進程的調度算法，為了描述方便，后面章節(jié)中的“進程”指“普通進程”。從Linux2.6.23內核到目前最新的Linux3.3.5內核的普通進程（采用調度策略SCHED_NORMAL）采用了絕對公平調度算法，CFS(completelyfairschedule)。CFS從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再區(qū)分交互式進程。它將所有的進程都統(tǒng)一對待，這就是公平的含義。CFS調度中，進程數據結構中的動態(tài)優(yōu)先級成員prio還繼續(xù)有效，只是內核不再動態(tài)調整進程
3、的動態(tài)優(yōu)先級了。進程的優(yōu)先級為100—139，對應的nice值為-20—19。和之前版本的優(yōu)先級規(guī)定相同。Nice和優(yōu)先級對應關系如下如何實現公平調度的？內核給每個進程維護了一個虛擬運行時間vruntime，每個進程運行一段時間后，虛擬運行時間會增加，但是運行同樣的實際時間每個進程增加的數值是不同的。比如nice值為0的進程運行了10ms，其虛擬運行時間增加了1vms（vms為1虛擬毫秒，為了描述方便而定義）；nice為19的進程運行10ms，其虛擬運行時間增加了1000vms。進程在其生命周期中，
4、其虛擬運行時間一直都是在增加的。內核把虛擬運行時間看做實際運行時間，為了公平起見要選擇運行時間短的進程進行運行。所以內核在調度中總是選擇虛擬運行時間小的進程。對內核來說，這樣就很公平了，O(∩_∩)O同樣運行10ms，如何確定一個進程該增加多少vms？增加的虛擬運行時間和進程的優(yōu)先級nice數值有關，每個nice數值對應一個權重數值，見下圖。每個進程虛擬運行時間增加的時間量和（NICE_0_LOAD/nice_n_weight）成正比。其中NICE_0_LOAD為1024，即nice數值為0的權重，
5、nice_n_weight即為nice數值為n的進程的權重，如nice為-20（優(yōu)先級最高的普通進程）的權重為88761。從這種算法也可以看出，優(yōu)先級高的進程的虛擬運行時間增加的慢，其實際運行時間累計數值也就長。同樣，這種算法能保證優(yōu)先級低的進程也有運行機會，只是實際運行的時間比較短。內核要把所有running狀態(tài)的進程放到一起，在需要調度時從中取出一個虛擬運行時間短的進程。因為發(fā)生調度的頻率非常高，查找合適進程的算法就變的很重要了。在CFS調度中，內核采用了以進程虛擬運行時間為key值的紅黑樹數據
6、結構掛接各個running的進程。有關紅黑樹請參考《linux內核之紅黑樹》。先要引入一個重要概念，調度實體(schedentiy)：就是調度的對象。每個進程的task_struct包含了調度實體成員變量se。為何要引入調度實體，而不是直接使用進程的task_struct？是因為在CFS中支持CFS組調度，一個組中可能包含1個或多個進程。不能通過組中任何進程的task_struct來調度組，所以引入了調度實體的概念。為了統(tǒng)一起見，進程組和進程都使用調度實體保存調度相關的信息。后面會介紹CFS組調度。
7、在多核系統(tǒng)中，每個CPU（此處指一個核心）對應一個全局變量per_cpu_runqueues，其數據結構為structrq，該變量為調度的最頂層的數據結構。在該數據結構中包含了cfs，其數據結構為structcfs_rq。cfs就是在該cpu上CFS調度的頂級結構，或者說是CFS調度的入口點。其實rq中還包括了rt成員變量，rt是實時進程調度的頂級結構。structcfs_rq{為了說明方便，只保留部分成員變量structrb_roottasks_timeline;structrb_node*rb_
8、leftmost;structsched_entity*curr,*next,*last,*skip;}其中成員變量tasks_timeline指向了紅黑樹的根，所有的進程都掛到這棵紅黑樹上（有些是間接掛接的）。如下圖中的單個進程，進程數據結構task_struct中包含了成員變量se，即調度實體。調度實體se中包含了run_node節(jié)點，se通過該節(jié)點掛接到紅黑樹上。在選擇需要調度的進程時，內核將搜索這個紅黑樹，找到虛擬運行時間小的進程，并把該進程從樹上摘下。同時會
