Linux Kernel 排程機制介紹
hlchou@mail2000.com.tw
by loda.
2011/12/2
多核心架構(gòu)儼然是目前智慧型手機方案的新趨勢,隨著省電與效能上的考量,多核心的架構(gòu)各家方案也都有所差異.為能讓同一個Linux Kernel在不同效能的處理器上能即時運作,其中關(guān)鍵的部份便是核心的排程機制,也因此本文將以此為主題進行介紹,希望能對目前投入這領(lǐng)域的開發(fā)者有所助益.
前一段時間,看到Qualcomm關(guān)於Snapdragon S4產(chǎn)品的新聞,這產(chǎn)品最讓人印象深刻的部份在於它支援a(chǎn)SMP(Asynchronous Symmetrical Multi-Processing)的處理器架構(gòu),基於ARMv7 Dual/Quad-Core 的Krait多核心處理器架構(gòu),可讓個別處理器根據(jù)執(zhí)行時期的負荷,動態(tài)調(diào)整時脈(根據(jù)晶片型號差異,時脈最高可達 2.5Ghz)與電壓的DCVS (Dynamic Clock and Voltage Scaling)技術(shù). 每個aSMP的處理器都能獨立的調(diào)整電壓與時脈,並能夠關(guān)閉用不到的處理器,節(jié)省功耗. 由於可以根據(jù)需求個別調(diào)整主處理器的時脈,因此在aSMP架構(gòu)下,當(dāng)需要有類似Companion處理器的角色時,就可以把其中一個主處理器降頻,同時兼顧到省電與執(zhí)行低算運需求的目的 (Qualcomm採用的是28nm,省電製程.). 也因此,就無需在主處理器之外,額外提供一個運算能力較低且低功耗的處理器,用來支援待機或是背景音樂播放的需求.
在同一則新聞中也提到NvidiaTegra3支援的Quad-Core與vSMP(Variable Symmetric Multiprocessing)架構(gòu).參考Nvidia的技術(shù)文件「Variable SMP – A Multi-Core CPU Architecture for Low Power and High Performance」,我們知道 Tegra3不同於前一代Tegra2是由兩個Cortex A9搭配一個低階ARM7的架構(gòu),以NVIDIA Kal -El的vSMP方案來說,會提供五個Cortex A9處理器(組合方式為4 個高效能Cortex A9主處理器 搭配 1個效能較低但強調(diào)省電的Cortex A9 Companion處理器),其中4個Cortex A9主處理器採用標(biāo)準製程(時脈可到GHz.),以訴求較高的執(zhí)行效率,而剩下一個Companion Cortex A9處理器(時脈最高為500MHz),會採用低功耗(Low Power)的製程,可用於運算量較低的待機或背景執(zhí)行需求.
基於vSMP的架構(gòu),這五個處理器,可以根據(jù)執(zhí)行的實際狀況,選擇主處理器或是Companion處理器運作,並透過DVFS(Dynamic Voltage and Frequency Scaling) 動態(tài)調(diào)整主處理器的頻率與電壓降低功耗,進行Power Gating與利用目前Linux Kernel所支援的CPU Up/Down HotPlug機制,讓4個主處理器可以動態(tài)的 CPU-Up/Down 掛起或移出Linux Kernel Tasks的排程範(fàn)圍(ex,Task Migration),以便讓閒置的處理器關(guān)閉節(jié)省功耗.
參考Tegra的WhitePaper,vSMP並不允許Companion處理器與主處理器被同時啟用,也因此Tegra3有提供軟硬體配套的CPU Governor 與 CPU Management Logic 去監(jiān)控處理器的執(zhí)行負荷,能在系統(tǒng)繁忙時,關(guān)閉Companion CPU,把工作轉(zhuǎn)到4個主處理器上執(zhí)行,並監(jiān)控處理器執(zhí)行負載,動態(tài)調(diào)整主時脈與哪個主處理器能被卸載. 也就是說,如果是處於待機或是背景音樂播放,系統(tǒng)就只開啟Companion 處理器,但若是需要上網(wǎng)或執(zhí)行更繁重的工作,就會卸載Companion 處理器,然後根據(jù)需求開啟1個,2個或同時把4個主處理器致能. 基於這樣的設(shè)計,也能對主處理器的時脈進行調(diào)整,但不同於aSMP架構(gòu)的是,這4個主處理器的時脈會調(diào)整為一樣的時脈,要拉高就一起拉高,要降低就一起降低,因此對Linux Kernel的排程來說,並不會有參與排程的處理器運算能力不一致的問題.
相對於上述提到的aSMP或vSMP架構(gòu),我們比較跟使用一個效率高的主處理器搭配一個省電且運算能力較弱的Companion處理器的差異,例如 ARM9/ARM11 +DSP 或是一個 Cortex A9 + ARM7,由於這兩個主處理器與Compaion處理器基礎(chǔ)架構(gòu)不同,兩個處理器的Memory Management與L2 Cache並沒有共用,甚至兩者在指令集的層次就完全不同,例如ARM環(huán)境中運作的Linux Kernel配置好的記憶體分頁,或是多工環(huán)境下的Tasks,就不能直接透過排程分到DSP上運作.而是必須在設(shè)計階段,就考慮到這兩個處理器協(xié)同運作的配套機制,例如Linux Kernel,人機介面與檔案系統(tǒng)是運作在ARM端,而Audio Codec是放在DSP上執(zhí)行,此時會由ARM去處理人機介面互動並透過檔案系統(tǒng)把音樂檔案載入,讓DSP端可以播放. 兩個處理器之間,需要設(shè)計彼此溝通的介面機制,隨著應(yīng)用情境的多元化,在設(shè)計上的複雜度也會相對增加.
而aSMP與vSMP的優(yōu)點在於上面的主處理器與Companion處理器採用同樣的核心技術(shù),有一樣的指令集,共用同樣的Memory Management記憶體管理與L2 Cache共用. 以vSMP來說, Companion處理器跟主處理器有各自的L1 Cache,但共用同樣的L2 Cache與Memory Management,因此當(dāng)Linux Kernel在上面運作時,包括4GB的記憶體分頁,應(yīng)用程式的多工執(zhí)行環(huán)境,就能在有開啟Linux Kernel CPU Up/Down HotPlug的機制下無縫銜接,且上面運作的Task能跨不同的處理器進行Task Migration,無需解決跨到不同處理器與映射到不同記憶體空間的複雜問題.
談到這,不論是aSMP或是vSMP都有其擁護者,並能充分發(fā)揮Linux Kernel CPU Up/Down HotPlug的特性,也都各自具備相當(dāng)?shù)陌l(fā)展?jié)摿? 但要能讓這樣的設(shè)計充分發(fā)揮效益,還有一些在核心與排程機制上,需要優(yōu)化的空間. 以目前Linux Kernel的Tasks排程機制實作來說,並沒有考慮到每個處理器具備不同運算能力的條件,就算是對處理器有Load Weight的計算,也是以該處理器所負荷的排程單元Load Weight來做統(tǒng)計,只能反映出哪個處理器目前排程單元的負荷,但並不能根據(jù)個別處理器的效能,而給予合理的排程負荷計算參數(shù). 因此,如果有一個aSMP架構(gòu)的處理器動態(tài)把時脈降低,而這處理器又跟其他運算能力較高的處理器一起進行Tasks排程,就有可能讓重要的Task被放到運算能力較低,且當(dāng)下負荷又已經(jīng)過重的處理器上執(zhí)行,而導(dǎo)致在產(chǎn)品端的執(zhí)行效果不如預(yù)期.
本文,會把焦點放在排程機制的介紹上,有關(guān)產(chǎn)品上的實作與技術(shù)問題,開發(fā)者可以根據(jù)自己所面對的平臺與對於核心排程技術(shù)的了解,來進行設(shè)計. 本文主要參考的Linux核心有 2.6.10, 2.6.38.6 與 3.0.4,但由於Linux核心仍在持續(xù)的演進中,若你使用的版本跟筆者不同,還請以你手中的Linux Kernel Source Code為依據(jù). 最後,所有的內(nèi)容筆者會盡力確保資訊的正確性,若有不足之處,還請不吝指教.
Linux Kernel 的排程機制.
如下圖所示,在linux Kernel 2.4 時,多核心的架構(gòu)下是共用同一個Task Queue,且採用O(N)排程算法,在排程效率與對多核心的支援是相對較弱的.
在linux Kernel 2.6 時,每個處理器都有兩個Task Queue,當(dāng)位於Active Task Queue的行程執(zhí)行完畢,就會依據(jù)行程的優(yōu)先級,計算Priority與Time Slice,然後放到Expired Task Queue中,當(dāng)Active Task Queue執(zhí)行完畢後,就會Switch這兩個Task Queue,讓經(jīng)過計算後的新Active Task Queue可以立刻加入排程.
此時Linux Kernel的核心排程採用的是 O(1)排程算法,我們可以參考Linux Kernel 2.6.10的原始碼,首先,依據(jù)O(1)的概念,Task Struct(如下所示)中的run_list會以Link List方式把同一個Task Priority 的行程串起來.
struct task_struct {
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
struct thread_info *thread_info;
atomic_t usage;
unsigned long flags; /* per process flags, defined below */
unsigned long ptrace;
int lock_depth; /* Lock depth */
int prio, static_prio;
struct list_head run_list;
…..
}
而結(jié)構(gòu)list_head的宣告如下所示,
struct list_head {
struct list_head *next, *prev;
};
在每個Task被產(chǎn)生時,會透過巨集INIT_LIST_HEAD初始化Task的run_list,把Link List的頭尾 next/prev都指向自己,而在Task被排入執(zhí)行時就會透過函式enqueue_task執(zhí)行巨集list_add_tail把Task的Link List放到對應(yīng)的Priority Link List 結(jié)尾,而在Task被移出執(zhí)行時,就會透過函式dequeue_task執(zhí)行巨集list_del,把Task的Link List從對應(yīng)的Priority Link List移出. 執(zhí)行的概念如下圖所示,
對同一個Task Priority來說,被排定執(zhí)行的Task就會透過 run_list Link List串連起來,依序執(zhí)行,並且在移除執(zhí)行時,從Link List Node中移出.
參考kernel/sched.c中的原始碼, Priority Array會根據(jù)目前140個Priority層級 (MAX_PRIO=140),幫每個Task Priority都配置一個Link List的 Queue Head,並且用unsigned long針對這140個Priority層級,透過Bits為0或1,來表示該Task Priority層級是否有需要被執(zhí)行的Task在排程等待執(zhí)行中,相關(guān)代碼如下所示
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
如下圖所示,以目前140bits的Task Priroty來說,會透過五個unsigned long,來表示完整的140bits.
執(zhí)行時期,再透過巨集sched_find_first_bit （這部份會依據(jù)平臺以處理器優(yōu)化的指令集來處理）,針對這140bits,找出第一個目前有Task在其中等待執(zhí)行的Task Priority.
整體運作的概念,如下圖所示
雖然有了O(1)的實作,而且基於這實作,也確實可以很快讓排程機制很有效率的運作,然而處理器雖然是具備多工的能力,但真實的情況下,一個處理器同一時間只能執(zhí)行一個Task,也就是說,在不考慮觸發(fā)中斷與重新觸發(fā)排程機制的情況下,在當(dāng)前Task的Time Slice尚未執(zhí)行完畢前,其他的Task是沒有機會被執(zhí)行的. 也因此,在Linux Kernel 2.6.23之後,Linux核心採用了新的 CFS(Completely Fair Scheduler)排程機制(作者為Ingo Molnar),希望可以基於排程的改善,盡可能的讓每個不同等級的Task可以更公平的分配到處理器的時間,基於RB Tree的概念,可以讓越少被執(zhí)行到的Task,有更高的優(yōu)先機率被處理器執(zhí)行到,避免優(yōu)先級較低的Task,被延遲較久的時間才得到被處理器執(zhí)行的機會.
參考Linux Kernel 3.0.4中有關(guān)CFS的Design文件 (路徑在Documentation/scheduler/sched-design-CFS.txt),作者試著用一句 "CFS basically models an "ideal, precise multi-tasking CPU" on real hardware." 來簡要說明CFS 80%設(shè)計精神 .所謂理想的多工處理器,就是當(dāng)處理器有100%的能力,且系統(tǒng)中有兩個Tasks正在運作,這兩個Tasks可以各自取得處理器50%的執(zhí)行能力,並被處理器平行執(zhí)行,也就是說任意時間間隔來看(例如,隨機取10ms間隔),這兩個Tasks都是分配到處理器50%的執(zhí)行能力.
以實際的處理器運作行為來說,一個處理器同一時間只能執(zhí)行一個Task,當(dāng)這個Task Time-Slice結(jié)束後,會透過Context-Switch切換下一個Task進來執(zhí)行,當(dāng)系統(tǒng)中的Tasks個數(shù)便多時,在特定的時間間隔來看,處理器等於執(zhí)行特定Task的時間較長,而對於優(yōu)先級較低的Task,卻可能在該區(qū)間中都沒有得到執(zhí)行權(quán). 換個角度來說,Tasks有優(yōu)先級也有Time Slice長度的區(qū)別,假設(shè)Task #A Time Slice長度為10ms,以總Tasks數(shù)量與總Time Slice長度來說,會取得處理器5%的執(zhí)行時間,最理想的狀況是,我們在任意一秒的間隔來看,Task#A都可以分到處理器5%的執(zhí)行時間,但在現(xiàn)實的狀況來說,在任意一秒的間隔來看,只要有優(yōu)先級高的Task被排程到,且該Task分配到的Time Slice較長,就會讓Task#A呈現(xiàn)在一個不公平的時間分配中. 雖然,用較長的時間來看一定是公平的,但CFS希望解決的就是讓目前處理器執(zhí)行的機制上,可以盡可能的做到即時的公平.
因此,CFS導(dǎo)入了"Virtual Runtime"的概念(單位為nanosec),根據(jù)目前總共的Tasks數(shù)量,用以作為選擇下一個執(zhí)行Task Time Slice的依據(jù).例如,CFS會選擇目前p->se.vruntime值最低的Task來執(zhí)行(也就是距離上一次被執(zhí)行時間間隔最久的Task),會在每一次觸動排程機制時,盡可能的達到"理想的多工處理器"的目標(biāo).
然而,在實際Linux Kernel的Time Slice與Priority來看,CFS的概念還必須要考慮到依據(jù)每個Task的Nice Value所計算的Time Slice長度不一定每個Task都一切,而且每個Task的Real-Time Priority值也不盡相同,有關(guān)Task 計算Time Slice與Real-Time Priority的說明,會另外在下一段文章中介紹.
每次Scheduler Tick觸發(fā)時,所進行的動作
不論是O(N),O(1)與CFS,系統(tǒng)的排程都是基於固定的Scheduling Tick來觸發(fā),也因此,每一次的Scheduling Tick觸發(fā),都攸關(guān)Task執(zhí)行的週期與是否要進行Task的切換,也是排程機制核心的部分.
Linux Kernel的Scheduling機制,會根據(jù)編譯核心時配置的HZ值來決定,一般來說是每1/100秒或每1/1000秒觸發(fā)一次Scheduling Tick,讓系統(tǒng)的排程機制可以去計算每個Task執(zhí)行的時間,並藉此決定是不是要進行Task Context-Switch.
以支援CFS的Linux Kernel 2.6.38.6來說,每次觸發(fā)Scheduling Tick都會執(zhí)行下述的動作
1,取得目前的CPU ID,與目前CPU的 RunQueue指標(biāo),與目前RunQueue中正在執(zhí)行的Curr Task指標(biāo)
2,呼叫 sched_clock_tick (實作在kernel/sched_clock.c中),這函式需在有設(shè)定Unstable CPU Clock時才有作用,如果全域變數(shù)sched_clock_stable為1,這個函式就會不作用直接返回.(ARM環(huán)境中,這個變數(shù)並無作用.)
3,取得 RunQueue SpinLock
4,呼叫update_rq_clock (實作在kernel/sched.c中), 若runQueue沒有設(shè)定skip_clock_update,這函式會更新RunQueue的Clock值.並呼叫函式update_rq_clock_task, 更新RunQueue clock_task值,clock_task會把前後兩次RunQueue Clock的Delta值,減去處理器進行Soft-IRQ與Hardware-IRQ的時間差值後,對clock_task進行累加. 可用以反應(yīng)出RunQueue中Task實際被處理器執(zhí)行的時間累加值.
5,呼叫update_cpu_load_active,會透過函式update_cpu_load在每次Tick觸發(fā)時,更新RunQueue cpu_load Array,用以反應(yīng)目前RunQueue所在的處理器負載.
6,執(zhí)行目前Task 所在Class的Tick函式(ex, curr->sched_class->task_tick),若Current Task是屬於Fair Class,就會呼叫task_tick_fair (實作在kernel/sched_fair.c中). 依序若Current Task為Stop/Real-Time/Idle Scheduling Class就會呼叫函式 task_tick_stop/ task_tick_rt/ task_tick_idle.
7,釋放RunQueue SpinLock
8,呼叫perf_event_task_tick (若編譯時,沒設(shè)定CONFIG_PERF_EVENTS,這函式會是inline的空函式),主要用以支援核心處理器效能的監(jiān)聽動作.
9,在SMP架構(gòu)下,會呼叫函式idle_cpu,用以更新RunQueue的idle_at_tick值,為1表示目前CPU RunQueue執(zhí)行的是Idle Task,反之為0,則非Idle Task. 可供判斷目前這RunQueue所在處理器是否處於閒置的狀態(tài).
10,在SMP架構(gòu)下,會呼叫trigger_load_balance, 若已達到RunQueue設(shè)定下一次觸發(fā)Load Balance的jiffies時間值(next_balance),就會觸發(fā)Scheduling Softare IRQ,並在Software IRQ中透過函式rebalance_domains,執(zhí)行Scheduling Domain Load Balance動作.若未達RunQueue下一次觸發(fā)Load Balance的jiffies時間值,且在編譯核心時有設(shè)定CONFIG_NO_HZ （NO HZ可支援處理器執(zhí)行Idle Task時,停止系統(tǒng)的Scheduling Tick,可在進入pm_idle時,減少Timer中斷觸發(fā)(例如HZ=100,每秒就有一百次Tick Timer中斷觸發(fā)),減少系統(tǒng)被觸發(fā)醒來的機會.）,就會呼叫函式nohz_balancer_kick,Kick一個處理器進行No Hz Load Balance.被Kick選擇為進行No Hz Load Balance的處理器所屬RunQueue的nohz_balance_kick值會設(shè)定為1.
以上總結(jié)每次觸發(fā)Scheduling Tick時,主要進行的工作內(nèi)容.接下來我們再透過pick_next_task,看在目前系統(tǒng)支援四種Scheduling Class的排程下,一個Task是如何被撿選出來執(zhí)行的.
從pick_next_task看Scheduling Class對排程的影響
檢視CFS對不同Scheduling Class行為最好的入口就是函式pick_next_task (實作在 kernel/sched.c中),在函式pick_next_task中會執(zhí)行如下的流程找到下一個要被載入執(zhí)行的Task
1,檢查目前總Runnable Task數(shù)量是否跟放在Fair Class中的數(shù)量一致 (rq->nr_running == rq->cfs.nr_running),若成立,就執(zhí)行執(zhí)行Fair Scheduling Class的pick_next_task抓取下一個執(zhí)行的Task
2,若1不成立,就會執(zhí)行 for_each_class(class) {….}迴圈,可以參考如下define宣告
#define sched_class_highest (&stop_sched_class)
#define for_each_class(class) \
for (class = sched_class_highest; class; class = class->next)
目前優(yōu)先級最高的Scheduling Class為 Stop-Task Scheduling Class,而在函式pick_next_task中,就會依序執(zhí)行 Stop-Task, Real-Time,Fair 與 Idle-Task Scheduling Class所實作的pick_next_task函式,先找到的Task就會由函式pick_next_task回傳. 也因此,當(dāng)有Task存在 Stop-Task或是Real-Time Scheduling Class中時,這時屬於Fair Scheduling Class中的Task執(zhí)行的優(yōu)先級就會降低.
總結(jié)運作的概念,可以參考下圖所示
CSF RBTREE(Red-Black Tree) – O(Log2(N))
CFS挑選Task的機制為RB-Tree,概念如下圖所示,包括Task或是Task Group,都會是RBTree中的一個Node支點,每次選擇Task來執(zhí)行時,都會選擇左邊目前Virtual RunTime最低的Task(也就是最久沒有被執(zhí)行到的Task)來執(zhí)行,雖然Virtual RunTime會根據(jù)Task的Priority而有增長的差異,例如:Nice Priority低的Task Virutal RunTime會增長的比較快,相對佔據(jù)處理器執(zhí)行的時間就會比較短,反之,Nice Priority 高的Task會因為Virutal RunTime增長的慢,而得到相對比較多實際的處理器執(zhí)行時間. 但在理想的情況下,如果大家都是Nice 0的情況,基於CFS RBTree的機制,可以讓多數(shù)的Task能相對均勻的得到處理器的執(zhí)行時間,而避免有特定的Task等待比較久的時間沒有得到處理器的執(zhí)行機會.
對CFS與RBTree建立基本的概念後,接下來讓我們進一步的探討處理器排程RunQueue的資料結(jié)構(gòu),更清楚的掌握排程運作的內(nèi)涵.
處理器的RunQueue
在目前的Linux Kernel中,每個處理器都會配置一個RunQueue,而從了解RunQueue的資料結(jié)構(gòu)著手,我們能對排程的運作有更清楚的藍圖,進而在程式碼的閱讀上,可以更加清晰. 在本節(jié),筆者會把RunQueue的資料結(jié)構(gòu)struct rq (宣告在 kernel/sched.c中)進行介紹,讓各位可以知道核心排程是基於哪些參數(shù)進行運作,這參數(shù)的內(nèi)容比較繁瑣,建議可以先有個概念,若有興趣進一步探究的,再回到本節(jié)即可.
如下所示,處理器RunQueue主要包含以下的參數(shù)與對應(yīng)的說明
參數(shù)名稱說明
raw_spinlock_t lock用以作為RunQueue的SpinLock
unsigned long nr_running用以記錄目前處理器RunQueue中執(zhí)行的Task數(shù)量
unsigned long cpu_load[]cpu_load主要用以表示處理器的負載,目前這個Array大小為5 (定義在CPU_LOAD_IDX_MAX),在每個處理器的RunQueue中都會有對應(yīng)到該處理器的cpu_load參數(shù)配置,在每次處理器觸發(fā)Scheduler Tick時, 都會呼叫函式update_cpu_load_active,進行cpu_load的更新.
在系統(tǒng)初始化時,會呼叫函式sched_init把RunQueue的cpu_load Array初始化為0.
了解cpu_load Array更新最好的方式應(yīng)該是透過函式update_cpu_load (實作在kernel/sched.c),基於這函式的實作,我們可以把cpu_load Array每個數(shù)值公式說明如下.
cpu_load[0]會直接等於RunQueue中l(wèi)oad.weight的值.
cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0])/16
當(dāng)呼叫函式this_cpu_load時,所傳回的 CPU Load值是cpu_load[0] (也就是會等於RunQueue中的load.weight).而在進行CPU Blance或Migration時,就會呼叫函式source_load與target_load取得對應(yīng)處理器與對應(yīng)cpu_load index值,來進行計算.
unsigned long last_load_update_tick用以記錄最後一次更新CPU Load的時間值. (會把當(dāng)時的jiffies值儲存到這變數(shù)).
ifdef CONFIG_NO_HZ
u64 nohz_stamp在linux Kerel 2.6.38.6中,這個參數(shù)沒有作用.
unsigned char nohz_balance_kick初始值為0,用在當(dāng)NO Hz機制有開啟時的CFS Fair Scheduling的Load Balance機制.可參考kernel/sched_fair.c 中的函式trigger_load_balance實作.
在SMP架構(gòu)下,且有設(shè)置NO HZ時,會在每次Scheduling Tick觸發(fā)時,由函式scheduler_tick(in kernel/sched.c)呼叫trigger_load_balance,再呼叫函式nohz_balancer_kick,Kick一個處理器進行No Hz Load Balance.而被選擇進行No Hz Load Balance工作處理器的RunQueue中的nohz_balance_kick數(shù)值會設(shè)定為1.
unsigned int skip_clock_update如果skip_clock_update的值被設(shè)定為1,此時透過函式update_rq_clock要進行RunQueue Clock值的更新時,就會直接返回.(每次呼叫update_rq_clock函式,都會讓RunQueue中的Clock值等於sched_clock_cpu的返回值.
struct load_weight load參考include/linux/sched.h中struct load_weight的宣告如下
struct load_weight {
unsigned long weight, inv_weight;
};
RunQueue中的load->weight值,會是目前所執(zhí)行的schedule entity的load->weight的總和,也就是說,RunQueue的load->weight越高,也表示所負責(zé)的排程單元load->weight總合越高,表示處理器所負荷的執(zhí)行單元也越重.
unsigned long nr_load_updates在每次Scheduler Tick中呼叫update_cpu_load時,這個值都會加一,可以用來反應(yīng)目前CPU Load更新的次數(shù).
u64 nr_switches用來累加處理器進行Context Switch的次數(shù),會在函式schedule呼叫時進行累加,並可以透過函式nr_context_switches統(tǒng)計目前所有處理器總共的Context Switch次數(shù). 或是可以透過查看檔案/proc/stat中的ctxt欄位得知目前整個系統(tǒng)觸發(fā)Context Switch的總數(shù).
struct cfs_rq cfs為CFS Fair Scheduling Class的 RunQueue
struct rt_rq rt為Real-Time Scheduling Class的RunQueue
ifdef CONFIG_FAIR_GROUP_SCHED (用以支援可以Group CFS Tasks的機制.)
struct list_head leaf_cfs_rq_list在有設(shè)置Fair Group Scheduling的環(huán)境下,會基於原本CFS RunQueue與包含有若干Task的Group所成的排程集合,也就是說當(dāng)有一個Group A,其下有20個Tasks,而這Group A就會有自己的CFS RunQueue用來排程自己所屬的Tasks,而屬於這Group A的Tasks所使用到的處理器時間,就會以這Group A總體所分得的時間為上限. 基於 Cgroup的 Fair Group Scheduling架構(gòu),可以創(chuàng)造出有階層性的Tasks組織,根據(jù)不同Tasks的功能群組化,在配置給該群組對應(yīng)的處理器資源,讓屬於該群組下的Tasks可以透過RunQueue機制排程,使用屬於該群組所配置到的資源.
這個變數(shù)主要是用來管理CFS RunQueue List,操作上可以透過函式list_add_leaf_cfs_rq把一個Group CFS RunQueue加入到List中,或透過函式list_del_leaf_cfs_rq把一個Group CFS RunQueue移除. 並可透過for_each_leaf_cfs_rq把一個 RunQueue上的所有l(wèi)eaf cfs_rq走過一遍.
ifdef CONFIG_RT_GROUP_SCHED (用以支援可以Group Real-Time Tasks的機制.
struct list_head leaf_rt_rq_list類似於leaf_cfs_rq_list所扮演的角色,只是這是針對屬於Real-Time的Task,在實際操作上可以透過函式list_add_leaf_rt_rq,list_del_leaf_rt_rq或巨集for_each_leaf_rt_rq.
unsigned long nr_uninterruptible一般來說,Linux Kernel的Task狀態(tài)可以為TASK_RUNNING, TASK_INTERRUPTIBLE (Sleep) , TASK_UNINTERRUPTIBLE (Deactivate Task,此時Task會從RunQueue移除)或TASK_STOPPED. (在此先忽略Trace,Zombie,Dead..etc). 透過這個變數(shù)會統(tǒng)計目前RunQueue中有多少Task屬於TASK_UNINTERRUPTIBLE的狀態(tài).當(dāng)呼叫函式activate_task時,會把nr_uninterruptible值減一,並透過函式enqueue_task把對應(yīng)的Task依據(jù)所在的Scheduling Class放到對應(yīng)的RunQueue中,並把目前RunQueue的nr_running值加一.
struct task_struct *curr, *idle, *stop為指向三個Task的指標(biāo). (Current Task,Idle Task與最高執(zhí)行級的Stop Task).
curr : 指向目前處理器正在執(zhí)行的Task
idle: 指向?qū)凫禝dle-Task Scheduling Class的Idle Task.
stop: 指向目前最高等級屬於 Stop-Task Scheduling Class的Task
unsigned long next_balance基於處理器的jiffies值,用以記錄下次進行處理器Balancing的時間點.
struct mm_struct *prev_mm用以儲存Context-Switch發(fā)生時,前一個Task的Memory Management結(jié)構(gòu),並可用在函式finish_task_switch中,透過函式mmdrop釋放前一個Task的記憶體資源.
u64 clock用以記錄目前RunQueue的Clock值,基本上該值會等於透過sched_clock_cpu(cpu_of(rq))的回傳值,並會在每次呼叫scheduler_tick時透過函式update_rq_clock更新目前RunQueue clock值.
在實作部分,函式sched_clock_cpu會透過sched_clock_local或ched_clock_remote取得對應(yīng)的sched_clock_data,而處理器的sched_clock_data值,會透過函式sched_clock_tick在每次呼叫scheduler_tick時進行更新.
補充….
從函式update_rq_clock的實作來說,其實
delta = sched_clock_cpu(cpu_of(rq)) – rq->clock;
rq->clock += delta;
可以直接寫成
rq->clock= sched_clock_cpu(cpu_of(rq));
u64 clock_task這個值會等於從上一次更新RunQueue Clock時,到這次要更新RunQueue Clock時的時間間隔 Delta 減去在這段時間中,處理器用來進行Soft-IRQ與Hardware-IRQ的時間差值的累加.
簡要來說,這個值會透過函式update_rq_clock_task進行更新,用來反應(yīng)出RunQueue中Task實際執(zhí)行時所佔用到的處理器時間Clock累加值.
atomic_t nr_iowait用以記錄目前RunQueue中有多少Task處於等待I/O的Sleep狀態(tài).
在實際的使用上,例如當(dāng)Driver接收來自Task的調(diào)用,但處於等待I/O回覆的階段時,為了充分利用處理器的執(zhí)行資源,這時就可以在Driver中呼叫函式io_schedule,此時就會把目前RunQueue中的nr_iowait加一,並設(shè)定目前Task的in_iowait為1,然後觸發(fā)Scheduling讓其他Task有機會可以得到處理器執(zhí)行時間.
ifdef CONFIG_SMP
struct root_domain *rdRoot Domain是基於多核心架構(gòu)下的機制,會由RunQueue結(jié)構(gòu)記住目前採用的Root Domain,其中包括了目前的CPU Mask(包括 Span, Online 與 RT Overload), Reference Count 跟cpupri.
當(dāng)Root Domain有被RunQueue參考到時, refcount就會加一,反之就是減一. 而CPU Mask Span表示RunQueue可掛上的CPU Mask, Online為RunQueue目前已經(jīng)掛上排程的CPU Mask,最後的RT Overload(rto_mask)代表的是這個RunQueue可在對應(yīng)的rto_mask CPU上執(zhí)行Real-Time Task. 可以參考檔案kernel/sched_rt.c中函式pull_rt_task的實作,當(dāng)一個RunQueue中屬於Real-Time的Task已經(jīng)執(zhí)行完畢(也就是rq->rt.rt_nr_running==0),就會透過函式pull_rt_task從該RunQueue中屬於rto_mask CPU Mask可以執(zhí)行的處理器上,找出是否有一個處理器有大於一個以上的Real-Time Task,若有就會轉(zhuǎn)到目前這個執(zhí)行完畢Real-Time Task的處理器上.
而cpupri不同於Task本身有區(qū)分140個(0-139)Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19). CPU Priority本身有102個Priority (包括,-1 為Invalid,0為Idle,1為Normal,2-101對應(yīng)到Real-Time Priority 0-99).參考函式convert_prio, Task Priority如果是 140就會對應(yīng)到CPU Idle,如果是大於等於100就會對應(yīng)到CPU Normal,若是Task Priority介於0-99之間,就會對應(yīng)到CPU Real-Time Priority 101-2之間.) 在實際的操作上,例如可以透過函式cpupri_find帶入一個要插入的Real-Time Task,此時就會依據(jù)cpupri中pri_to_cpu選擇一個目前執(zhí)行Real-Time Task且該Task的優(yōu)先級比目前要插入的Task更低的處理器,並透過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.實作的部份可以參考檔案kernel/sched_cpupri.c.
在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain,對Root Domain與 CPU Priority機制進行初始化.
struct sched_domain *sdSchedule Domain是基於多核心架構(gòu)下的機制.每個處理器都會有一個基礎(chǔ)的Scheduling Domain, Scheduling Domain可以有階層性的架構(gòu),透過parent可以找到上一層的Domain,或是透過child找到下一層的 Domain (NULL表示結(jié)尾.).並可透過span欄位,表示這個Domain所能涵蓋的處理器範(fàn)圍. 通常Base Domain會涵蓋系統(tǒng)中所有處理器的個數(shù),而Child Domain所能涵蓋的處理器個數(shù)不超過它的Parent Domain. 而當(dāng)在進行Scheduling Domain 中的Task Balance時,就會以該Domain所能涵蓋的處理器為最大範(fàn)圍.
同時,每個Schedule Domain都會包括一個或一個以上的CPU Groups (結(jié)構(gòu)為struct sched_group),並透過next變數(shù)把CPU Groups串連在一起(成為一個單向的Circular linked list),每個CPU Group都會有變數(shù)cpumask來定義這個CPU Group所涵蓋的處理器範(fàn)圍.並且CPU Group所包括的處理器範(fàn)圍,必需涵蓋在所屬的Schedule Domain處理器範(fàn)圍中.
當(dāng)進行Scheduling Domain的Balancing時,會以其下的CPU Groups為單位,根據(jù)cpu_power （會是該Group所涵蓋的處理器Tasks Loading的總和）來比較不同的CPU Groups的負荷,以進行Tasks的移動,達到Balancing的目的.
在有支援SMP的架構(gòu)下,會在函式sched_init中,呼叫open_softirq,註冊 SCHED_SOFTIRQ Software IRQ與其對應(yīng)的 Callback函式 run_rebalance_domains. 並會在每次呼叫函式scheduler_tick時,透過函式trigger_load_balance確認是否目前的jiffies值已經(jīng)大於RunQueue下一次要觸發(fā)Load Balance的next_balance時間值,並透過函式raise_softirq觸發(fā)SCHED_SOFTIRQ Software IRQ. 在Software IRQ觸發(fā)後,就會呼叫函式run_rebalance_domains,並在函式rebalance_domains中,進行後續(xù)處理器上的Scheduling Domain Load Balance動作.
有關(guān)Scheduling Domain進一步的內(nèi)容,也可以參考Linux Kernel文件 Documentation/scheduler/sched-domains.txt.
unsigned long cpu_power在SMP架構(gòu)下,這值可用以表示目前RunQueue所在處理器的計算能力,在函式sched_init初始化時,會把這值設(shè)定為SCHED_LOAD_SCALE (=Nice 0的Load Weight=1024).並可透過函式update_cpu_power (in kernel/sched_fair.c)更新這個值.
處理器的CPU Power值越大,表示這個處理器有更多的計算能力,可以分擔(dān)CPU Power值越小的處理器上的Tasks任務(wù).
unsigned char idle_at_tick這值會等於函式idle_cpu的返回值,如果為1表示目前CPU RunQueue中執(zhí)行的為Idle Task. 反之為0,則表示處理器執(zhí)行的不是Idle Task (也就是說處理器正在忙碌中.).
int post_schedule若這值不為0,表示會有在Schedule排程動作結(jié)束前,要呼叫的收尾函式. (實作為inline函式post_schedule in kernel/sched.c),目前只有Real-Time Scheduling Class有支援這個機制(會呼叫函式has_pushable_tasks in kernel/sched_rt.c).
int active_balance當(dāng)RunQueue中此值為1,表示這個RunQueue正在進行Fair Scheduling的Load Balance,此時會呼叫stop_one_cpu_nowait暫停該RunQueue所屬處理器的排程,並透過函式active_load_balance_cpu_stop,把Tasks從最忙碌的處理器,移到Idle的處理器上執(zhí)行.
int push_cpu用以儲存目前進入Idle且負責(zé)進行 Load Balance流程的處理器ID. 呼叫的流程為,在呼叫函式schedule時,若該處理器RunQueue的nr_running為0 (也就是目前沒有正在執(zhí)行的Task),就會呼叫idle_balance,並觸發(fā)後續(xù)Load Balance流程.
struct cpu_stop_work active_balance_work用以儲存給Stopper Scheduling Class所要執(zhí)行的函式與其對應(yīng)參數(shù). 會作為在函式stop_one_cpu_nowait中呼叫函式cpu_stop_queue_work的參數(shù).
int cpu用以儲存目前運作這個RunQueue的處理器ID.
int online為1表示目前此RunQueue有在對應(yīng)的處理器掛上並執(zhí)行.
unsigned long avg_load_per_task如果RunQueue中目前有Task正在執(zhí)行,這個值會等於目前該RunQueue的Load Weight除以目前RunQueue中Task數(shù)目的均值. (rq->avg_load_per_task = rq->load.weight / nr_running;).
u64 rt_avg這個值會由Real-Time Scheduling Class呼叫函式update_curr_rt,用以統(tǒng)計目前Real-Time Task執(zhí)行時間的均值,在這函式中會以目前RunQueue的clock_task減去目前Task執(zhí)行的起始時間,取得執(zhí)行時間的Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ). 在透過函式sched_rt_avg_update把這Delta值跟原本RunQueue中的rt_avg值取平均值. 以運作的週期來看,這個值可反應(yīng)目前系統(tǒng)中Real-Time Task平均被分配到的執(zhí)行時間值.
u64 age_stamp這個值主要在函式sched_avg_update更新,以筆者手中的Linux Kernel 2.6.38.6的實作來說,當(dāng)RunQueue Clock減去age_stamp大於 0.5秒 (=sched_avg_period),就會把這值累加0.5秒 (單位都是nanoseconds). 從函式scale_rt_power的實作來說,age_stamp值離RunQueue Clock越遠,表示total值越大,available值也越大,而函式scale_rt_power返回的div_u64計算結(jié)果也越大,最終 RunQueue的cpu_power與Scheduling Domain中的Scheduling Group的cpu_power值也就越大. (可參考函式update_cpu_power的實作).
u64 idle_stamp這值會在觸發(fā)Scheduling時,若判斷目前處理器RunQueue沒有正在運作的Task,就會透過函式idle_balance更新這值為為目前RunQueue的clock值.可用以表示這個處理器是何時進入到Idle的狀態(tài).
u64 avg_idle會在有Task運作且idle_stamp不為0 (表示前一個狀態(tài)是在Idle)時以目前RunQueue的clock減去idle_stamp所計算出的Delta值為依據(jù),更新這個值. 可反應(yīng)目前處理器進入Idle狀態(tài)的時間長短.
ifdef CONFIG_IRQ_TIME_ACCOUNTING
u64 prev_irq_time這值會透過函式update_rq_clock_task更新,可用以代表處理器執(zhí)行Soft-IRQ與Hardware-IRQ所花的處理器Clock值的累加.s
unsigned long calc_load_update用以記錄下一次計算CPU Load的時間,初始值為目前的jiffies加上五秒與1次的Scheduling Tick的間隔 (=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))
long calc_load_active會等於RunQueue中nr_running與nr_uninterruptible的總和.（可參考函式calc_load_fold_active）.
ifdef CONFIG_SCHED_HRTICK
ifdef CONFIG_SMP
int hrtick_csd_pending在函式init_rq_hrtick初始化RunQueue High-Resolution Tick時,此值預(yù)設(shè)為0.
在函式hrtick_start中,會判斷目前觸發(fā)的RunQueue跟目前處理器所使用的RunQueue是否一致,若是,就直接呼叫函式hrtimer_restart,反之就會依據(jù)RunQueue中hrtick_csd_pending的值,如果hrtick_csd_pending為0,就會透過函式__smp_call_function_single讓RunQueue所在的另一個處理器執(zhí)行rq->hrtick_csd.func 所指到的函式 __hrtick_start. 並等待該處理器執(zhí)行完畢後,才重新把hrtick_csd_pending設(shè)定為1.
也就是說, RunQueue的hrtick_csd_pending是用來作為SMP架構(gòu)下,由處理器A觸發(fā)處理器B執(zhí)行_hrtick_start函式的一個保護機制.而有關(guān)在SMP下如何由一個處理器觸發(fā)另一個處理器執(zhí)行函式的機制,可以參考kernel/smp.c中相關(guān)smp_call_function_xxxxxxx的實作.s
struct call_single_data hrtick_csd用以儲存hrtick機制中,要跨處理器執(zhí)行的函式結(jié)構(gòu).
struct hrtimer hrtick_timer為High-Resolution Tick的結(jié)構(gòu),會透過函式hrtimer_init初始化.
ifdef CONFIG_SCHEDSTATS
struct sched_info rq_sched_info為Scheduling Info.的統(tǒng)計結(jié)構(gòu),可以參考include/linux/sched.h中的宣告. 例如在每次觸發(fā)Schedule時,呼叫函式schedule_debug對上一個Task的lock_depth進行確認(Fork一個新的Process 時,會把此值預(yù)設(shè)為-1就是No-Lock,當(dāng)呼叫Kernel Lock時, 就會把Current Task的lock_depth加一.),若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,用以代表Task Blocking的次數(shù).
unsigned long long rq_cpu_time可用以表示RunQueue中的Task所得到CPU執(zhí)行時間的累加值.
在發(fā)生Task Switch時,會透過sched_info_switch呼叫sched_info_arrive並以目前RunQueue Clock值更新Task 的sched_info.last_arrival時間,而在Task所分配時間結(jié)束後,會在函式sched_info_depart中以現(xiàn)在的RunQueue Clock值減去Task的sched_info.last_arrival時間值,得到的 Delta作為變數(shù)rq_cpu_time的累加值.
unsigned int yld_count用以統(tǒng)計呼叫System Call sys_sched_yield的次數(shù).
unsigned int sched_count可用以統(tǒng)計觸發(fā)Scheduling的次數(shù). 在每次觸發(fā)Scheduling時,會透過函式schedule呼叫schedule_debug,呼叫schedstat_inc對這變數(shù)進行累加.
unsigned int sched_goidle可用以統(tǒng)計進入到Idle Task的次數(shù). 會在函式pick_next_task_idle中,呼叫schedstat_inc對這變數(shù)進行累加.
unsigned int ttwu_count用以統(tǒng)計Wake Up Task的次數(shù).
unsigned int ttwu_local用以統(tǒng)計Wake Up 同一個處理器Task的次數(shù).
至此,有關(guān)RunQueue的結(jié)構(gòu)說明告一段落.
CFS的Scheduling Classes 與 Scheduling Policies
CFS排程機制在設(shè)計時,考慮到排程機制的彈性,定義了Scheduler Class的機制,讓排程機制可以根據(jù)設(shè)計的需求,延伸不同的排程模組進來,每個新加入的排程機制都必須要提供Scheduler Class的實作,結(jié)構(gòu)為 struct sched_class (定義在檔案include/linux/sched.h中). 舉sched_fair.c的實作來說, Scheduler Class實作的宣告如下
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.rq_online = rq_online_fair,
.rq_offline = rq_offline_fair,
.task_waking = task_waking_fair,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_fork = task_fork_fair,
.prio_changed = prio_changed_fair,
.switched_to = switched_to_fair,
.get_rr_interval = get_rr_interval_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.task_move_group = task_move_group_fair,
#endif
};
其中相關(guān)函式的行為簡述如下
函式名稱說明
next會指向下一個Scheduling Class,以筆者所採用的Linux Kernel 2.6.38.6而言,Scheduling Class的順序為
stop_sched_class->rt_sched_class->fair_sched_class->idle_sched_class
enqueue_task當(dāng)Task屬於Runnable狀態(tài)時,就會呼叫這個函式把Task配置到RunQueue RBTree中,進行排程動作,並呼叫inc_nr_running將RunQueue中nr_running的值加一.(nr_running用以代表目前RunQueue有多少Runnable Task進行排程)
dequeue_task當(dāng)Task不需要執(zhí)行時,就會呼叫這個函式把Task從RunQueue RBTree中移除,並呼叫dec_nr_running將RunQueue中nr_running的值減一.
yield_task用以暫停目前正在執(zhí)行中的Task,如果sysctl_sched_compat_yield有設(shè)定,就會找出目前RBTree中最右邊的Task(也就是vrruntime最多的Task),讓目前Task的vrruntime值等於最右邊Task值的vrruntime加一(可參考:se->vruntime = rightmost->vruntime + 1),如此在下次排程觸發(fā)時就會透過函式put_prev_task把目前的Task放到RBTree的最右邊,也就等同於暫停Task,讓該Task下次被執(zhí)行到的機會最低.
check_preempt_curr用以決定一個Task是否可以中斷目前正在運作的Task,取得執(zhí)行權(quán).以CFS本身的實作來說 (in sched_fair.c).如果想要取代目前Task的Task本身的Scheduling Policy為 Batch或是Idle時,會直接返回,不會用來取代目前正在執(zhí)行中的Task.反之,如果目前正在執(zhí)行中的Task的Scheduling Policy為Idle,就會直接由所傳入的Task取代目前正在執(zhí)行的Task.
pick_next_task用以在排程觸發(fā)時,從RunQueue RBTree中,取出符合目前Scheduling邏輯的下一個要被執(zhí)行的Task.
put_prev_task用以在排程觸發(fā)時,把上一個執(zhí)行完畢的Task放到目前RunQueue RBTree中對應(yīng)的位置.
set_curr_task這個函式用以改變Task目前所屬的Scheduling Class與改變Task Group.
task_tick這是Scheduler的 Timer Tick來源,系統(tǒng)中觸發(fā)的Scheduling Tick會呼叫這個函式 (看HZ設(shè)定多少,100就是每秒呼叫這函式100次,1000就是每秒呼叫這函式1000次),
用以讓排程機制可以決定哪些Task應(yīng)該要配執(zhí)行與哪些Task應(yīng)該要被移出RunQueue.
select_task_rq
(需在SMP架構(gòu)下)通常用在執(zhí)行一個新的程序,或是WakeUp一個Task時,會根據(jù)目前SMP下每個處理器的負荷,決定Task是否要切換到另一個處理器的RunQueue去執(zhí)行,執(zhí)行時會返回最後目標(biāo)處理器的值.
此外,在Linux Kernel SMP的架構(gòu)下,還會支援如下的函式
函式名稱說明
pull_task可用來把Task從一個RunQueue移到目前的RunQueue來,並設(shè)定Task會在目前處理器的RunQueue中執(zhí)行.
can_migrate_task可用來判斷一個Task可否從另一個RunQueue移到目前的處理器來執(zhí)行,並返回判斷值.(返回值0就是不適合移動,1則是表明適合移動).
目前有以下三種情況,會返回失敗.
1,該Task的cpus_allowed bitmap沒有設(shè)定目前的處理器 (也就是說在 CPU BitMap中該Task沒有被設(shè)定可以在目前處理器上能被同意執(zhí)行)
2,目前的Task正在該RunQueue被執(zhí)行中
3,透過函式task_hot,判斷目前的Task是否為該RunQueue與Scheduling Domain中被執(zhí)行時間較長的Task,基於對目前執(zhí)行中處理器Cache-Hot的考量,該Task也不會被同意可以移動到目前的處理器.(可以避免Cache Flush,與在新的處理器上要重新進行Cache的動作.)
有關(guān)的巨集
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() (&__get_cpu_var(runqueues))
#define task_rq(p) cpu_rq(task_cpu(p))
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
#define raw_rq() (&__raw_get_cpu_var(runqueues))
sched_class Class中宣告的Method,就是要在Linux Kernel排程中新增一個Scheduler Class所要實作的內(nèi)容,讓Linux Kernel可以根據(jù)不同行程的需求,調(diào)度這些在系統(tǒng)中有註冊的排程模組,讓系統(tǒng)可以達到預(yù)定的執(zhí)行目標(biāo)與行為.
以Linux Kernel 2.6.38來說,目前共支援4種Scheduler Class,包括
1,Fair Scheduler Class (實作在檔案 sched_fair.c中):
目前包括有
1.a, SCHED_NORMAL (也稱為SCHED_OTHER): 主要用以排程一般目的的Task.
1.b, SCHED_BATCH: 主要用以讓Task可以延長執(zhí)行的時間(Time Slice),減少被中斷發(fā)生Task Context-Switch的次數(shù).藉此可以提高 Cache的利用率 (每次Context-Switch都會導(dǎo)致Cache-Flush). 比較適合用在固定週期執(zhí)行的Batch Jobs任務(wù)主機上,而不適合用在需要使用者互動的產(chǎn)品 (會由於Task切換的延遲,而感覺到系統(tǒng)效能不佳或是反應(yīng)太慢).
2,Real-Time Scheduler Class (實作在檔案 sched_rt.c中):
支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR. (SCHED_RR task預(yù)設(shè)的 Time Slice長度為100 msecs.).
3,Idle Task Scheduler Class (實作在檔案 sched_idletask.c中):
支援SCHED_IDLE,為系統(tǒng)中的Idle Task排程.
4,Stop Scheduler Class (實作在檔案 sched_stoptask.c中):屬於 Stop-Task Scheduling Class的Task是屬於系統(tǒng)中最高權(quán)限的Task,會中斷所有任務(wù)的執(zhí)行,並且不會被其他任務(wù)所中斷.
目前系統(tǒng)中,Scheduling Class的優(yōu)先級順序為 Stop-Task > Real-Time > Fair > Idle-Task,開發(fā)者可以根據(jù)自己的設(shè)計需求,來把所屬的Task配置到不同的Scheduling Class中.
在支援Fair Group Scheduling環(huán)境下,以CGroup (Control Group) Scheduler分配Task與Group的處理器執(zhí)行時間.
Control Group 提供了Linux核心可以把Tasks進行整合/區(qū)分或是依據(jù)子Group進行分派的動作. 根據(jù)Control Group文件中的定義,一個CGroup可以關(guān)聯(lián)到屬於1或多組SubSystem中的多個Tasks. SubSystem主要是基於CGroup提供的Task Group機制,扮演類似資源管控的角色,用以設(shè)定調(diào)配每個Group使用資源的限制. 在支援Control Group的Linux Kernel中,每一個Task在系統(tǒng)中都會屬於一個CGroup與一個SubSystem,每一個SubSystem都會有一個系統(tǒng)設(shè)定的組態(tài),並配置到對應(yīng)的CGroup中. 每一個Hierarchy架構(gòu),都有一個屬於CGroup虛擬檔案系統(tǒng)的Instance參考.
在系統(tǒng)運作時,會有多個有從屬關(guān)係的Task Groups同時運作,每一個Hierarchy都會屬於這系統(tǒng)中所有Tasks的一部分. 使用者可以透過CGroup虛擬檔案系統(tǒng)中的目錄名稱產(chǎn)生或刪除對應(yīng)的CGroup,並可以查詢哪個CGroup有Task被指派,或是列出對應(yīng)CGroup中所有被指派的Task PIDs. 藉由CGroup的設(shè)計,還可支援基於使用者帳號(Account)的處理器資源調(diào)配目的.(包括可以限定能使用的處理器或是Memory Node.)
參考 include/linux/cgroup_subsys.h的實做,目前CGroup包括以下的SubSystem,
1,cpuset (CONFIG_CPUSETS):用以限定指定的Tasks使用的CPU與Memory資源,有關(guān)cpuset的使用可以透過函式sched_setaffinity,sched_getaffinity,set_mempolicy,get_mempolicy,mbind. 例如下述的例子,可以由應(yīng)用程式透過函式sched_setaffinity指定當(dāng)應(yīng)用程式執(zhí)行時,所要使用的處理器編號.
http://fred-zone.blogspot.com/2007/10/cpu.html
#include <stdio.h>
#include <stdlib.h>
#include <sched.h>
int main(void) {
cpu_set_t cmask;
unsigned long len = sizeof(cmask);
__CPU_ZERO(&cmask); /* 初始化 cmask */
__CPU_SET(0, &cmask); /* 指定第一個處理器 */
/* 設(shè)定自己由指定的處理器執(zhí)行 */
if (!sched_setaffinity(0, len, &cmask)) {
printf("Could not set cpu affinity for current process.\n");
exit(1);
}
return 0;
}
2,cpu_cgroup (CONFIG_CGROUP_SCHED):這選項會支援Tasks能被群組(Group)化與依據(jù)設(shè)定切割群組佔用的處理器執(zhí)行時間. 更進一步,還可以設(shè)定CONFIG_RT_GROUP_SCHED用以支援群組的 Real-Time排程 (支援包括 SCHED_FIFO 與 SCHED_RR). 與可以設(shè)定CONFIG_FAIR_GROUP_SCHED 用以支援群組的CFS排程機制(支援包括SCHED_NORMAL與SCHED_BATCH).
3,cpuacct (CONFIG_CGROUP_CPUACCT):這選項用以支援CPU Accounting Controller機制,透過CGroup機制群組Task,並依據(jù)使用者的帳號(Account)所產(chǎn)生的Task群組來劃分處理器的執(zhí)行時間.
4,debug (CONFIG_CGROUP_DEBUG):用以支援CGroup的Debug機制,像是Task Reference Count等統(tǒng)計資訊.
其它SubSystem還包括 ns (CONFIG_CGROUP_NS),mem_cgroup (CONFIG_CGROUP_MEM_RES_CTLR),devices (CONFIG_CGROUP_DEVICE),freezer (CONFIG_CGROUP_FREEZER),net_cls (CONFIG_NET_CLS_CGROUP),blkio (CONFIG_BLK_CGROUP).
在一個基於CGroup FileSystem的 Task-Group機制下,會統(tǒng)籌100%的處理器資源. 所有的處理器支援會根據(jù)root_task_group與所屬的子Task-Group的 Weight (=se->load.weight)基於Fair-Scheduling機制來進行處理器資源的分配工作.
舉實際的例子來說,當(dāng)root_task_group中有十個Tasks且每個Task的Weight值為1024,在root_task_group之下又有兩個子Task Groups且這兩個子Task Group的Weight也都為1024,此時這兩個子Task Group所分配到的處理資源為 1024 / (10*1024 + 1024 + 1024) = 8.33% .
我們可以參考如下操作流程,產(chǎn)生一個驗證Control Group的目錄,並在其中產(chǎn)生cpu目錄,並掛起CPU與CGroup相關(guān)的Device Node.
[root@localhost ~]# mkdir /cgroup
[root@localhost ~]# mount -t tmpfs cgroup_root /cgroup
[root@localhost ~]# mkdir /cgroup/cpu
[root@localhost ~]# mount -t cgroup -ocpu none /cgroup/cpu
[root@localhost ~]# ls /cgroup/cpu
cgroup.clone_children
cgroup.event_control
cgroup.procs
cpu.rt_period_us
cpu.rt_runtime_us
cpu.shares
notify_on_release
release_agent
tasks
[root@localhost ~]#
我們可以從tasks檔案看到目前處理器上所有執(zhí)行的Task Process ID,並從cpu.shares知道目前處理器所分擔(dān)的CPU Load基數(shù).
接下來,我們透過Control Group產(chǎn)生 GroupA與GroupB兩個Task Group群組,如下所示
[root@localhost cpu]# mkdir GroupA
[root@localhost cpu]# mkdir GroupB
然後透過設(shè)定 cpu.shares,把GroupA的cpu.shares設(shè)定為4096,GroupB的cpu.shares設(shè)定為1024,也就是說在實際執(zhí)行上,屬於GroupA的Tasks會比 GroupB的Tasks多得到約4倍的實際處理器執(zhí)行時間.
[root@localhost cpu]# echo 4096 > GroupA/cpu.shares
[root@localhost cpu]# echo 1024 > GroupB/cpu.shares
接下來我們用如下的程式碼,分別編譯為GroupA與GroupB的執(zhí)行檔名稱,兩者唯一的差異只在於讓printf顯示的字串各別表示出自己是由GroupA或 GroupB所吐出的內(nèi)容而已.
#include <stdio.h>
#define PrintThreshold 0×10000000
int main()
{
int i,vCount;
i=0;
vCount=0;
while(1)
{
i++;
if(i>PrintThreshold)
{
i=0;
vCount++;
printf("GroupA:%ld\n",vCount);
}
}
return 0;
}
執(zhí)行編譯好的GroupA與GroupB執(zhí)行檔,兩者Process ID分別為 1738與 1739,然後把這兩個Process ID分別設(shè)定給我們已經(jīng)設(shè)定好差距四倍處理器執(zhí)行時間的兩個Control Group目錄下的檔案tasks.
[root@localhost cpu]# echo 1738 > GroupA/tasks
[root@localhost cpu]# echo 1739 > GroupB/tasks
我們可以透過top 指令查看這兩個程式執(zhí)行時各自所佔的CPU比率與兩者的差距,如下所示,GroupA佔據(jù)處理器約80.6%的執(zhí)行時間而GroupB佔據(jù)處理器約19.9%的執(zhí)行時間. (兩者相加為100.5%,超過100%,但這是筆者環(huán)境中top的真實結(jié)果(或該說誤差),在此就不作討論),以比率來說兩者所佔CPU實際執(zhí)行時間差距大約也是四倍,符合我們透過Control Group對Task執(zhí)行時間比率所做的設(shè)定.
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
1738 root 20 0 3880 264 212 R 80.6 0.0 2:02.50 GroupA
1739 root 20 0 3880 264 212 R 19.9 0.0 0:41.98 GroupB
再以實際的執(zhí)行結(jié)果來看,由於GroupA比GroupB多分到四倍的處理器執(zhí)行時間,也因此在Console所顯示的結(jié)果上,GroupA大約每顯示四個字串結(jié)果後,GroupB才有機會顯示一次,如此也符合我們透過Control Group所設(shè)定分配的處理器執(zhí)行資源比率.
GroupA:27
GroupA:28
GroupA:29
GroupA:30
GroupB:21
GroupA:31
GroupA:32
GroupA:33
GroupA:34
GroupB:22
GroupA:35
GroupA:36
GroupA:37
GroupA:38
GroupB:23
GroupA:39
GroupA:40
GroupA:41
GroupA:42
GroupB:24
GroupA:43
GroupA:44
GroupA:45
在Control Group之後,我們再針對原本Linux Kernel 2.6與在支援CFS排程機制後的核心排程,進一步的加以說明.
CFS(Kernel 2.6.23)之前Linux Kernel 2.6 Time Slice與Real Time優(yōu)先級的簡要介紹
如下圖所示為CFS之前,Linux Kernel 2.6排程的優(yōu)先級機制,右邊是屬於Task Real-Time優(yōu)先權(quán)，左邊是Task的Nice Value,系統(tǒng)初始化後,一個最原始的行程產(chǎn)生時,預(yù)設(shè)的Real-Time優(yōu)先權(quán)為0,而Nice優(yōu)先權(quán)亦為0. Linux Kernel會根據(jù)Nice Value來計算該Task執(zhí)行時間Time-Slice值的大小. 當(dāng)使用者把行程的Nice Value遞減時(最低為-20),就表示該行程的優(yōu)先權(quán)提高,相對的在排程時就會取得比較多的Time-Slice. 相對的,若不斷的增加Nice值(最大為19),就表示該行程的優(yōu)先權(quán)降低,所取得的Time-Slice亦較低.
但若使用者有Real-Time的需求時，希望特定的行程可以以較高的優(yōu)先權(quán)執(zhí)行,但又不希望如同增加Nice值一般,也對應(yīng)增加了Time-Slice時,就必須要設(shè)定屬於Real-Time的優(yōu)先權(quán). 而real-Time的優(yōu)先權(quán)最小為1，最大為99，該值越大在排程時會越先被執(zhí)行到.
有關(guān)Linux Kernel 2.6.10 核心Nice Value與對應(yīng)之Time-Slice關(guān)係,可以參考下表
Nice ValueTime Slice
-20
-19
-18
-17
-16
-15
-14
-13
-12
-11
-10
-9
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19800ms (DEF_TIMESLICE * 4 * 40 /20)
780ms (DEF_TIMESLICE * 4 * 39 /20)
760ms (DEF_TIMESLICE * 4 * 38 /20)
740ms (DEF_TIMESLICE * 4 * 37 /20)
720ms (DEF_TIMESLICE * 4 * 36 /20)
700ms (DEF_TIMESLICE * 4 * 35 /20)
680ms (DEF_TIMESLICE * 4 * 34 /20)
660ms (DEF_TIMESLICE * 4 * 33 /20)
640ms (DEF_TIMESLICE * 4 * 32 /20)
620ms (DEF_TIMESLICE * 4 * 31 /20)
600ms (DEF_TIMESLICE * 4 * 30 /20)
580ms (DEF_TIMESLICE * 4 * 29 /20)
560ms (DEF_TIMESLICE * 4 * 28 /20)
540ms (DEF_TIMESLICE * 4 * 27 /20)
520ms (DEF_TIMESLICE * 4 * 26 /20)
500ms (DEF_TIMESLICE * 4 * 25 /20)
480ms (DEF_TIMESLICE * 4 * 24 /20)
460ms (DEF_TIMESLICE * 4 * 23 /20)
440ms (DEF_TIMESLICE * 4 * 22 /20)
420ms (DEF_TIMESLICE * 4 * 21 /20)
100ms (DEF_TIMESLICE * 1 * 20 /20)
95ms (DEF_TIMESLICE * 1 * 19 /20)
90ms (DEF_TIMESLICE * 1 * 18 /20)
85ms (DEF_TIMESLICE * 1 * 17 /20)
80ms (DEF_TIMESLICE * 1 * 16 /20)
75ms (DEF_TIMESLICE * 1 * 15 /20)
70ms (DEF_TIMESLICE * 1 * 14 /20)
65ms (DEF_TIMESLICE * 1 * 13 /20)
60ms (DEF_TIMESLICE * 1 * 12 /20)
55ms (DEF_TIMESLICE * 1 * 11 /20)
50ms (DEF_TIMESLICE * 1 * 10 /20)
45ms (DEF_TIMESLICE * 1 * 9 /20)
40ms (DEF_TIMESLICE * 1 * 8 /20)
35ms (DEF_TIMESLICE * 1 * 7 /20)
30ms (DEF_TIMESLICE * 1 * 6 /20)
25ms (DEF_TIMESLICE * 1 * 5 /20)
20ms (DEF_TIMESLICE * 1 * 4 /20)
15ms (DEF_TIMESLICE * 1 * 3 /20)
10ms (DEF_TIMESLICE * 1 * 2 /20)
5m (DEF_TIMESLICE * 1 * 1 /20)
如下圖所示,筆者把Nice值對應(yīng)到的Task Priority與對應(yīng)的排程機制進行對比,我們可以看到在Task Priority 100-139 (對應(yīng)為Nice -20 – 19 或 User Priority 0-39)的區(qū)間內(nèi),為一般應(yīng)用Task的排程機制,使用的Scheduling Class為Normal與Batch,而屬於Real-Time排程機制對應(yīng)到的Task Priority為0-99,使用的Scheduling Class為Round-Robin與FIFO.
CFS在Linux Kernel 2.6.23之後,參考Tasks優(yōu)先級所施行的Time Slice與Real-Time措施
基於CFS RBTree的概念,由於會一直確保Virtual RunTime值的平衡,透過抓取佔據(jù)Virtual RunTime執(zhí)行時間最短的Task來執(zhí)行,因此像是原本排程中會透過Nice值計算對應(yīng)Task可運作Time Slice的設(shè)計方式,就變的需要有所調(diào)整,也因此在CFS中會透過函式calc_delta_mine (實作在 kernel/sched.c),根據(jù)目前Task的優(yōu)先級計算在排程時每次一個Scheduling Tick要增加的Delta值,也就是說如果該Task Nice值越高(優(yōu)先級越低)該Delta值就越大,對該執(zhí)行的Task來說就是Virtual RunTime在運作時,增加的速度越快(等於縮短實際執(zhí)行的時間),反之,如果該Task Nice值越低(優(yōu)先級越高)則Delta值就越小,在每次Scheduling Tick觸發(fā)時,Virtual RunTime增加的速度越慢,能獲得處理器執(zhí)行的實際時間也就越長.
參考kernel/sched_fair.c的實作,函式calc_delta_mine的呼叫來源有兩處,
來源說明
1,從函式calc_delta_fair中呼叫
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
return delta;
}
當(dāng)目前的Scheduling Entity Load Weight不為NICE 0 的Load Weight (=1024)時,就會根據(jù)所帶入的Delta值與對應(yīng)的Load Weight,計算出新的Delta值,通常用在
1,更新目前運作的Current Task執(zhí)行的Virtual RunTime時,就會呼叫calc_delta_fair用以取得Delta時間,並累加至變數(shù)curr->sum_exec_runtime中. (有關(guān)的實作可以參考函式__update_curr).
2,用在判斷是否要中斷目前的Task讓下一個Task (Scheduling Entity)可以進來執(zhí)行,實作部分可以參考函式 wakeup_preempt_entity,首先會判斷是否要取代的Task Virtual RunTime比目前的Task大,若是就直接返回-1,再來就以 1ms (=sysctl_sched_wakeup_granularity)計算要取代Task的WakeUp Granularity,若兩個Task的Virtual RunTime差值大於WakeUp Granularity就返回1,表示可以用下一個Task取代目前的Task,反之則返回0.
3,用在取得要置入Run Queue的Task Scheduling Entity的Virtual RunTime Slice值,實作的部分可以參考函式place_entity與函式 sched_vslice.
2,從函式sched_slice中呼叫
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
for_each_sched_entity(se) {
struct load_weight *load;
struct load_weight lw;
cfs_rq = cfs_rq_of(se);
load = &cfs_rq->load;
if (unlikely(!se->on_rq)) {
lw = cfs_rq->load;
update_load_add(&lw, se->load.weight);
load = &lw;
}
slice = calc_delta_mine(slice, se->load.weight, load);
}
return slice;
}
用來取得Task Scheduling Entity的Wall-Time slice.
以筆者在 64bits處理器下,所使用的Linux Kernel 2.6.38.6來說,函式calc_delta_mine的幾個關(guān)鍵數(shù)字如下所示
1,NICE_0_LOAD 為1024 (參考kernel/sched.c原始碼 NICE_0_LOAD=SCHED_LOAD_SCALE,並參考include/linux/sched.h中 SCHED_LOAD_SCALE = (1L << SCHED_LOAD_SHIFT), 而SCHED_LOAD_SHIFT = 10)
2,LONG_MAX為9223372036854775807 (ㄟ…我是用64bits處理器驗證,所以該值為0x7FFFFFFFFFFFFFFF) (參考原始碼include/linux/kernel.h,其中LONG_MAX = ((long)(~0UL>>1)) )
3,SRR(x, y) 為 (((x) + (1UL << ((y) – 1))) >> (y)) (參考原始碼kernel/sched.c)
4,BITS_PER_LONG:64
5,WMULT_CONST:4294967296 (=0×100000000)
6,WMULT_SHIFT:32
函式calc_delta_mine宣告原型如下
static unsigned long calc_delta_mine(unsigned long delta_exec, unsigned long weight, struct load_weight *lw)
根據(jù)目前的實作,Delta的返回值會透過如下流程來計算
1,如果lw->inv_weight 為0,就會執(zhí)行下列的計算
lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1);
2,Temp-Delta值為delta_exec * weight
2-1,如果Temp-Delta > 0×100000000
2-1-1,Delta = SRR(SRR(Temp-Delta, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2);
2-2,如果Temp-Delta <= 0×100000000
2-2-1,Delta = SRR(Temp-Delta * lw->inv_weight, WMULT_SHIFT);
舉實際的例子來說,當(dāng)傳入的參數(shù)
1,delta_exec=6000000
2,weight=1024
3,lw->weight=1024
4,lw->inv_weight=0
由於 lw->inv_weight為0,因此會進行如下的計算
lw->inv_weight=1 + ( 0×100000000 – 1024/2) / (1024+1) = 4190212.
而Temp-Delta 的值 = delta_exec * weight = 6000000 * 1024 = 6144000000=0x16E360000,大於 WMULT_CONST的值 (0×100000000).
因此,最後的Delta執(zhí)會進行如下計算
Delta = SRR(SRR(Temp-Delta, WMULT_SHIFT/2) * lw->inv_weight,WMULT_SHIFT/2)
=SRR(SRR(0x16E360000, 32/2) * 4190212,32/2)
=SRR(((0x16E360000 + 1<<15)>>16)* 4190212,16)
=SRR( ( 0x16E368000 >>16)* 4190212,16)
=SRR( 0x16E36* 4190212,16)
=SRR( 392832375000,16)
= (392832375000 + 1<15) >> 16
=5994146.
對應(yīng)到不同函式參數(shù)所換算回來的Delta值,筆者整理如下表所示
delta_execweightlw->weight呼叫前的 lw->inv_weight呼叫後的 lw->inv_weight返回Delta值
units: nanoseconds
40102415862708050270805026
5021024250117173001717300206
6501024158627080502708050420
385010241586270805027080502486
410010241586270805027080502647
435110241586270805027080502809
459910241586270805027080502969
658510242501171730017173002696
1031510241586270805027080506660
1189310242501171730017173004869
1197210242501171730017173004902
2249510242501171730017173009210
27733102425011717300171730011355
53413102415862708050270805034486
54762102415862708050270805035357
55454102415862708050270805035804
60593102415862708050270805039122
118071102415862708050270805076232
127372102415862708050270805082238
7243131024158627080502708050467652
7738721024250117173001717300316851
7822071024250117173001717300320264
10000001024158627080502708050645649
10000001024250117173001717300409436
10000001024250127080502708050645649
11873651024158627080502708050766622
298495010241586270805027080501927231
600000010241024041902125994146
600000010242048020961292998537
600000010242063208089520808952976744
600000010243072013976461999349
600000010244096104832010483201499634
6000000102467060640371916058
6000000102499780430401615694
60000001586567307569561677128
6000000158662446877456877451523783
20250000250163658067468795567
21750000158644870095718768770
21750000158645432094534759261
透過上述的計算,我們可以知道影響Virtual RunTime Slice增加的Delta值最大的關(guān)鍵是在下面三個參數(shù),筆者在此也簡述這三個參數(shù)的意義.
1,delta_exec: 是目前Virtual RunTime Slice的Delta值,會用來當(dāng)作calc_delta_mine的第一個參數(shù),用以計算出新的Delta值. 根據(jù)目前的實作,這個值可以表示在呼叫函式calc_delta_mine前,該Task所執(zhí)行的時間間隔,也就是說如果該值越大,表示該Task在這次呼叫函式calc_delta_mine前,所得到的執(zhí)行時間越長,相對的再透過Weight的計算後,下一次得到的Delta值就越大,對應(yīng)到真實執(zhí)行時間就會越少 (因為Delta值變大,執(zhí)行時Virtual RunTime增加的速度就越快.).
2,weight:為目前Task的Load Weight,若Task的Nice值為 0,則此值為1024. 這個值越大,透過calc_delta_mine所計算的inv_weight 值越小,對應(yīng)該 Task所計算出來的Delta值也越小,也就表示該Task的Virtual RunTime增加的越慢,因此實際得到處理器執(zhí)行的真實時間就越長.
3,lw->weight:為目前排程單位sched_entity的Load Weight . 如果se->load.weight等於Nice 0的 Load Weight (1024),函式calc_delta_fair就會直接返回所傳入的Delta值,反之才會進入函式calc_delta_mine,重新計算新的Delta值. RunQueue的參數(shù)load->weight,會等於該RunQueue中所有Schedule Entity的load->weight總合,分別表示整個RunQueue執(zhí)行單元的負荷與個別執(zhí)行單元的負荷.
參考函式set_load_weight的實作(in kernel/sched.c),我們可以把不同的Task Priority ,Nice值與所對應(yīng)的Scheduling Entity Load Weight值對應(yīng)如下表所示
Task PriorityTask NiceScheduling Entity Load WeightScheduling Entity Load Inverse-Weight
100-208876148388
101-197175559856
102-185648376040
103-174627392818
104-1636291118348
105-1529154147320
106-1423254184698
107-1318705229616
108-1214949287308
109-1111916360437
110-109548449829
111-97620563644
112-86100704093
113-74904875809
114-639061099582
115-531211376151
116-425011717300
117-319912157191
118-215862708050
119-112773363326
120010244194304
12118205237765
12226556557202
12335268165337
124442310153587
125533512820798
126627215790321
127721519976592
128817224970740
129913731350126
1301011039045157
131118749367440
132127061356676
133135676695844
134144595443717
1351536119304647
1361629148102320
1371723186737708
1381818238609294
1391915286331153
一般來說,如果Nice值加一 (也就是優(yōu)先級降低一),大約會減少10%處理器的執(zhí)行時間,而如果是Nice值減一(也就是優(yōu)先級調(diào)升),大約就會增加10%處理器的執(zhí)行時間.而參考上表整理的結(jié)果,每個Nice值的區(qū)間所對應(yīng)的Weight大約會相差1.25倍. 例如15*1.25=18.75,18*1.25=22.5…
介紹到此,我們可以發(fā)現(xiàn)像是O(N),O(1)或是CFS (O(Log2(N))),都沒有把處理器不等速的問題考慮進來.也因此,在支援像是aSMP架構(gòu)時,這部份的排程機制改善,就是攸關(guān)能否發(fā)揮aSMP架構(gòu)優(yōu)勢的關(guān)鍵.
結(jié)語
多核心架構(gòu)肯定會是未來智慧型手機晶片的主流,要能在智慧型手機方案中發(fā)揮架構(gòu)的優(yōu)勢,了解Linux Kernel的排程機制,會是一個必要的基礎(chǔ)功課.
本文主要著重在Linux Kernel排程的介紹,從前一代的Linux核心排程機制談起,到目前基於CFS的核心排程與相關(guān)資料結(jié)構(gòu)的說明. 但要發(fā)揮多核心的優(yōu)勢,除了Linux Kernel的層次外,在Android Framework上也需有所因應(yīng),後續(xù)筆者會再進一步的加以介紹.希望能讓閱讀本文的開發(fā)者有所助益.
People who looked at this item also looked at…
Android 筆記-Linux Kernel SMP (Symmetric Multi-Processors) 開機流程解析 Part(1) Boot-Rom與UBoot.Linux Kernel Heterogeneous Multi-Processor Scheduling筆記Android 筆記-Linux Kernel SMP (Symmetric Multi-Processors) 開機流程解析 Part(2) Linux Kernel SMP zImage到start_kernel流程.如何理解Linus Torvalds的“什麼才是優(yōu)秀程式師”的話Linux 2.4/2.6 核心排程機制剖析Related items
Android/Linux Kernel 記憶體管理-入門筆記Android 4.1 Jelly Bean安全機制探討Linux Kernel Heterogeneous Multi-Processor Scheduling筆記HITCON 2012 – Hacks in Taiwan Conference 臺灣駭客年會投影片從LLVM談 Portable Native Client Software Fault Isolation技術(shù)
