Linux Kernel 排程機制介紹 hlchou@mail2000.com.tw by loda. 2011/12/2 多核心架構儼然是目前智慧型手機方案的新趨勢,隨著省電與效能上的考量,多核心的架構各家方案也都有所差異.為能讓同一個Linux Kernel在不同效能的處理器上能即時運作,其中關鍵的部份便是核心的排程機制,也因此本文將以此為主題進行介紹,希望能對目前投入這領域的開發者有所助益. 前一段時間,看到Qualcomm關於Snapdragon S4產品的新聞,這產品最讓人印象深刻的部份在於它支援aSMP(Asynchronous Symmetrical Multi-Processing)的處理器架構,基於ARMv7 Dual/Quad-Core 的Krait多核心處理器架構,可讓個別處理器根據執行時期的負荷,動態調整時脈(根據晶片型號差異,時脈最高可達 2.5Ghz)與電壓的DCVS (Dynamic Clock and Voltage Scaling)技術. 每個aSMP的處理器都能獨立的調整電壓與時脈,並能夠關閉用不到的處理器,節省功耗. 由於可以根據需求個別調整主處理器的時脈,因此在aSMP架構下,當需要有類似Companion處理器的角色時,就可以把其中一個主處理器降頻,同時兼顧到省電與執行低算運需求的目的 (Qualcomm採用的是28nm,省電製程.). 也因此,就無需在主處理器之外,額外提供一個運算能力較低且低功耗的處理器,用來支援待機或是背景音樂播放的需求. 在同一則新聞中也提到NvidiaTegra3支援的Quad-Core與vSMP(Variable Symmetric Multiprocessing)架構.參考Nvidia的技術文件「Variable SMP – A Multi-Core CPU Architecture for Low Power and High Performance」,我們知道 Tegra3不同於前一代Tegra2是由兩個Cortex A9搭配一個低階ARM7的架構,以NVIDIA Kal -El的vSMP方案來說,會提供五個Cortex A9處理器(組合方式為4 個高效能Cortex A9主處理器 搭配 1個效能較低但強調省電的Cortex A9 Companion處理器),其中4個Cortex A9主處理器採用標準製程(時脈可到GHz.),以訴求較高的執行效率,而剩下一個Companion Cortex A9處理器(時脈最高為500MHz),會採用低功耗(Low Power)的製程,可用於運算量較低的待機或背景執行需求. 基於vSMP的架構,這五個處理器,可以根據執行的實際狀況,選擇主處理器或是Companion處理器運作,並透過DVFS(Dynamic Voltage and Frequency Scaling) 動態調整主處理器的頻率與電壓降低功耗,進行Power Gating與利用目前Linux Kernel所支援的CPU Up/Down HotPlug機制,讓4個主處理器可以動態的 CPU-Up/Down 掛起或移出Linux Kernel Tasks的排程範圍(ex,Task Migration),以便讓閒置的處理器關閉節省功耗. 參考Tegra的WhitePaper,vSMP並不允許Companion處理器與主處理器被同時啟用,也因此Tegra3有提供軟硬體配套的CPU Governor 與 CPU Management Logic 去監控處理器的執行負荷,能在系統繁忙時,關閉Companion CPU,把工作轉到4個主處理器上執行,並監控處理器執行負載,動態調整主時脈與哪個主處理器能被卸載. 也就是說,如果是處於待機或是背景音樂播放,系統就只開啟Companion 處理器,但若是需要上網或執行更繁重的工作,就會卸載Companion 處理器,然後根據需求開啟1個,2個或同時把4個主處理器致能. 基於這樣的設計,也能對主處理器的時脈進行調整,但不同於aSMP架構的是,這4個主處理器的時脈會調整為一樣的時脈,要拉高就一起拉高,要降低就一起降低,因此對Linux Kernel的排程來說,並不會有參與排程的處理器運算能力不一致的問題. 相對於上述提到的aSMP或vSMP架構,我們比較跟使用一個效率高的主處理器搭配一個省電且運算能力較弱的Companion處理器的差異,例如 ARM9/ARM11 +DSP 或是一個 Cortex A9 + ARM7,由於這兩個主處理器與Compaion處理器基礎架構不同,兩個處理器的Memory Management與L2 Cache並沒有共用,甚至兩者在指令集的層次就完全不同,例如ARM環境中運作的Linux Kernel配置好的記憶體分頁,或是多工環境下的Tasks,就不能直接透過排程分到DSP上運作.而是必須在設計階段,就考慮到這兩個處理器協同運作的配套機制,例如Linux Kernel,人機介面與檔案系統是運作在ARM端,而Audio Codec是放在DSP上執行,此時會由ARM去處理人機介面互動並透過檔案系統把音樂檔案載入,讓DSP端可以播放. 兩個處理器之間,需要設計彼此溝通的介面機制,隨著應用情境的多元化,在設計上的複雜度也會相對增加. 而aSMP與vSMP的優點在於上面的主處理器與Companion處理器採用同樣的核心技術,有一樣的指令集,共用同樣的Memory Management記憶體管理與L2 Cache共用. 以vSMP來說, Companion處理器跟主處理器有各自的L1 Cache,但共用同樣的L2 Cache與Memory Management,因此當Linux Kernel在上面運作時,包括4GB的記憶體分頁,應用程式的多工執行環境,就能在有開啟Linux Kernel CPU Up/Down HotPlug的機制下無縫銜接,且上面運作的Task能跨不同的處理器進行Task Migration,無需解決跨到不同處理器與映射到不同記憶體空間的複雜問題. 談到這,不論是aSMP或是vSMP都有其擁護者,並能充分發揮Linux Kernel CPU Up/Down HotPlug的特性,也都各自具備相當的發展潛力. 但要能讓這樣的設計充分發揮效益,還有一些在核心與排程機制上,需要優化的空間. 以目前Linux Kernel的Tasks排程機制實作來說,並沒有考慮到每個處理器具備不同運算能力的條件,就算是對處理器有Load Weight的計算,也是以該處理器所負荷的排程單元Load Weight來做統計,只能反映出哪個處理器目前排程單元的負荷,但並不能根據個別處理器的效能,而給予合理的排程負荷計算參數. 因此,如果有一個aSMP架構的處理器動態把時脈降低,而這處理器又跟其他運算能力較高的處理器一起進行Tasks排程,就有可能讓重要的Task被放到運算能力較低,且當下負荷又已經過重的處理器上執行,而導致在產品端的執行效果不如預期. 本文,會把焦點放在排程機制的介紹上,有關產品上的實作與技術問題,開發者可以根據自己所面對的平台與對於核心排程技術的了解,來進行設計. 本文主要參考的Linux核心有 2.6.10, 2.6.38.6 與 3.0.4,但由於Linux核心仍在持續的演進中,若你使用的版本跟筆者不同,還請以你手中的Linux Kernel Source Code為依據. 最後,所有的內容筆者會盡力確保資訊的正確性,若有不足之處,還請不吝指教. Linux Kernel 的排程機制. 如下圖所示,在linux Kernel 2.4 時,多核心的架構下是共用同一個Task Queue,且採用O(N)排程算法,在排程效率與對多核心的支援是相對較弱的. 在linux Kernel 2.6 時,每個處理器都有兩個Task Queue,當位於Active Task Queue的行程執行完畢,就會依據行程的優先級,計算Priority與Time Slice,然後放到Expired Task Queue中,當Active Task Queue執行完畢後,就會Switch這兩個Task Queue,讓經過計算後的新Active Task Queue可以立刻加入排程.
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; ….. } 而結構list_head的宣告如下所示, struct list_head { struct list_head *next, *prev; }; 在每個Task被產生時,會透過巨集INIT_LIST_HEAD初始化Task的run_list,把Link List的頭尾 next/prev都指向自己,而在Task被排入執行時就會透過函式enqueue_task執行巨集list_add_tail把Task的Link List放到對應的Priority Link List 結尾,而在Task被移出執行時,就會透過函式dequeue_task執行巨集list_del,把Task的Link List從對應的Priority Link List移出. 執行的概念如下圖所示, 對同一個Task Priority來說,被排定執行的Task就會透過 run_list Link List串連起來,依序執行,並且在移除執行時,從Link List Node中移出. 參考kernel/sched.c中的原始碼, Priority Array會根據目前140個Priority層級 (MAX_PRIO=140),幫每個Task Priority都配置一個Link List的 Queue Head,並且用unsigned long針對這140個Priority層級,透過Bits為0或1,來表示該Task Priority層級是否有需要被執行的Task在排程等待執行中,相關代碼如下所示 #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. 執行時期,再透過巨集sched_find_first_bit (這部份會依據平台以處理器優化的指令集來處理),針對這140bits,找出第一個目前有Task在其中等待執行的Task Priority. 整體運作的概念,如下圖所示 雖然有了O(1)的實作,而且基於這實作,也確實可以很快讓排程機制很有效率的運作,然而處理器雖然是具備多工的能力,但真實的情況下,一個處理器同一時間只能執行一個Task,也就是說,在不考慮觸發中斷與重新觸發排程機制的情況下,在當前Task的Time Slice尚未執行完畢前,其他的Task是沒有機會被執行的. 也因此,在Linux Kernel 2.6.23之後,Linux核心採用了新的 CFS(Completely Fair Scheduler)排程機制(作者為Ingo Molnar),希望可以基於排程的改善,盡可能的讓每個不同等級的Task可以更公平的分配到處理器的時間,基於RB Tree的概念,可以讓越少被執行到的Task,有更高的優先機率被處理器執行到,避免優先級較低的Task,被延遲較久的時間才得到被處理器執行的機會. 參考Linux Kernel 3.0.4中有關CFS的Design文件 (路徑在Documentation/scheduler/sched-design-CFS.txt),作者試著用一句 "CFS basically models an "ideal, precise multi-tasking CPU" on real hardware." 來簡要說明CFS 80%設計精神 .所謂理想的多工處理器,就是當處理器有100%的能力,且系統中有兩個Tasks正在運作,這兩個Tasks可以各自取得處理器50%的執行能力,並被處理器平行執行,也就是說任意時間間隔來看(例如,隨機取10ms間隔),這兩個Tasks都是分配到處理器50%的執行能力. 以實際的處理器運作行為來說,一個處理器同一時間只能執行一個Task,當這個Task Time-Slice結束後,會透過Context-Switch切換下一個Task進來執行,當系統中的Tasks個數便多時,在特定的時間間隔來看,處理器等於執行特定Task的時間較長,而對於優先級較低的Task,卻可能在該區間中都沒有得到執行權. 換個角度來說,Tasks有優先級也有Time Slice長度的區別,假設Task #A Time Slice長度為10ms,以總Tasks數量與總Time Slice長度來說,會取得處理器5%的執行時間,最理想的狀況是,我們在任意一秒的間隔來看,Task#A都可以分到處理器5%的執行時間,但在現實的狀況來說,在任意一秒的間隔來看,只要有優先級高的Task被排程到,且該Task分配到的Time Slice較長,就會讓Task#A呈現在一個不公平的時間分配中. 雖然,用較長的時間來看一定是公平的,但CFS希望解決的就是讓目前處理器執行的機制上,可以盡可能的做到即時的公平. 因此,CFS導入了"Virtual Runtime"的概念(單位為nanosec),根據目前總共的Tasks數量,用以作為選擇下一個執行Task Time Slice的依據.例如,CFS會選擇目前p->se.vruntime值最低的Task來執行(也就是距離上一次被執行時間間隔最久的Task),會在每一次觸動排程機制時,盡可能的達到"理想的多工處理器"的目標. 然而,在實際Linux Kernel的Time Slice與Priority來看,CFS的概念還必須要考慮到依據每個Task的Nice Value所計算的Time Slice長度不一定每個Task都一切,而且每個Task的Real-Time Priority值也不盡相同,有關Task 計算Time Slice與Real-Time Priority的說明,會另外在下一段文章中介紹. 每次Scheduler Tick觸發時,所進行的動作 不論是O(N),O(1)與CFS,系統的排程都是基於固定的Scheduling Tick來觸發,也因此,每一次的Scheduling Tick觸發,都攸關Task執行的週期與是否要進行Task的切換,也是排程機制核心的部分. Linux Kernel的Scheduling機制,會根據編譯核心時配置的HZ值來決定,一般來說是每1/100秒或每1/1000秒觸發一次Scheduling Tick,讓系統的排程機制可以去計算每個Task執行的時間,並藉此決定是不是要進行Task Context-Switch. 以支援CFS的Linux Kernel 2.6.38.6來說,每次觸發Scheduling Tick都會執行下述的動作 1,取得目前的CPU ID,與目前CPU的 RunQueue指標,與目前RunQueue中正在執行的Curr Task指標 2,呼叫 sched_clock_tick (實作在kernel/sched_clock.c中),這函式需在有設定Unstable CPU Clock時才有作用,如果全域變數sched_clock_stable為1,這個函式就會不作用直接返回.(ARM環境中,這個變數並無作用.) 3,取得 RunQueue SpinLock 4,呼叫update_rq_clock (實作在kernel/sched.c中), 若runQueue沒有設定skip_clock_update,這函式會更新RunQueue的Clock值.並呼叫函式update_rq_clock_task, 更新RunQueue clock_task值,clock_task會把前後兩次RunQueue Clock的Delta值,減去處理器進行Soft-IRQ與Hardware-IRQ的時間差值後,對clock_task進行累加. 可用以反應出RunQueue中Task實際被處理器執行的時間累加值. 5,呼叫update_cpu_load_active,會透過函式update_cpu_load在每次Tick觸發時,更新RunQueue cpu_load Array,用以反應目前RunQueue所在的處理器負載. 6,執行目前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 (若編譯時,沒設定CONFIG_PERF_EVENTS,這函式會是inline的空函式),主要用以支援核心處理器效能的監聽動作. 9,在SMP架構下,會呼叫函式idle_cpu,用以更新RunQueue的idle_at_tick值,為1表示目前CPU RunQueue執行的是Idle Task,反之為0,則非Idle Task. 可供判斷目前這RunQueue所在處理器是否處於閒置的狀態. 10,在SMP架構下,會呼叫trigger_load_balance, 若已達到RunQueue設定下一次觸發Load Balance的jiffies時間值(next_balance),就會觸發Scheduling Softare IRQ,並在Software IRQ中透過函式rebalance_domains,執行Scheduling Domain Load Balance動作.若未達RunQueue下一次觸發Load Balance的jiffies時間值,且在編譯核心時有設定CONFIG_NO_HZ (NO HZ可支援處理器執行Idle Task時,停止系統的Scheduling Tick,可在進入pm_idle時,減少Timer中斷觸發(例如HZ=100,每秒就有一百次Tick Timer中斷觸發),減少系統被觸發醒來的機會.),就會呼叫函式nohz_balancer_kick,Kick一個處理器進行No Hz Load Balance.被Kick選擇為進行No Hz Load Balance的處理器所屬RunQueue的nohz_balance_kick值會設定為1. 以上總結每次觸發Scheduling Tick時,主要進行的工作內容.接下來我們再透過pick_next_task,看在目前系統支援四種Scheduling Class的排程下,一個Task是如何被撿選出來執行的. 從pick_next_task看Scheduling Class對排程的影響 檢視CFS對不同Scheduling Class行為最好的入口就是函式pick_next_task (實作在 kernel/sched.c中),在函式pick_next_task中會執行如下的流程找到下一個要被載入執行的Task 1,檢查目前總Runnable Task數量是否跟放在Fair Class中的數量一致 (rq->nr_running == rq->cfs.nr_running),若成立,就執行執行Fair Scheduling Class的pick_next_task抓取下一個執行的Task 2,若1不成立,就會執行 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) 目前優先級最高的Scheduling Class為 Stop-Task Scheduling Class,而在函式pick_next_task中,就會依序執行 Stop-Task, Real-Time,Fair 與 Idle-Task Scheduling Class所實作的pick_next_task函式,先找到的Task就會由函式pick_next_task回傳. 也因此,當有Task存在 Stop-Task或是Real-Time Scheduling Class中時,這時屬於Fair Scheduling Class中的Task執行的優先級就會降低. 總結運作的概念,可以參考下圖所示 CSF RBTREE(Red-Black Tree) – O(Log2(N)) CFS挑選Task的機制為RB-Tree,概念如下圖所示,包括Task或是Task Group,都會是RBTree中的一個Node支點,每次選擇Task來執行時,都會選擇左邊目前Virtual RunTime最低的Task(也就是最久沒有被執行到的Task)來執行,雖然Virtual RunTime會根據Task的Priority而有增長的差異,例如:Nice Priority低的Task Virutal RunTime會增長的比較快,相對佔據處理器執行的時間就會比較短,反之,Nice Priority 高的Task會因為Virutal RunTime增長的慢,而得到相對比較多實際的處理器執行時間. 但在理想的情況下,如果大家都是Nice 0的情況,基於CFS RBTree的機制,可以讓多數的Task能相對均勻的得到處理器的執行時間,而避免有特定的Task等待比較久的時間沒有得到處理器的執行機會. 對CFS與RBTree建立基本的概念後,接下來讓我們進一步的探討處理器排程RunQueue的資料結構,更清楚的掌握排程運作的內涵. 處理器的RunQueue 在目前的Linux Kernel中,每個處理器都會配置一個RunQueue,而從了解RunQueue的資料結構著手,我們能對排程的運作有更清楚的藍圖,進而在程式碼的閱讀上,可以更加清晰. 在本節,筆者會把RunQueue的資料結構struct rq (宣告在 kernel/sched.c中)進行介紹,讓各位可以知道核心排程是基於哪些參數進行運作,這參數的內容比較繁瑣,建議可以先有個概念,若有興趣進一步探究的,再回到本節即可. 如下所示,處理器RunQueue主要包含以下的參數與對應的說明
至此,有關RunQueue的結構說明告一段落. CFS的Scheduling Classes 與 Scheduling Policies CFS排程機制在設計時,考慮到排程機制的彈性,定義了Scheduler Class的機制,讓排程機制可以根據設計的需求,延伸不同的排程模組進來,每個新加入的排程機制都必須要提供Scheduler Class的實作,結構為 struct sched_class (定義在檔案include/linux/sched.h中). 舉sched_fair.c的實作來說, Scheduler Class實作的宣告如下
其中相關函式的行為簡述如下
此外,在Linux Kernel SMP的架構下,還會支援如下的函式
有關的巨集 #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所要實作的內容,讓Linux Kernel可以根據不同行程的需求,調度這些在系統中有註冊的排程模組,讓系統可以達到預定的執行目標與行為. 以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可以延長執行的時間(Time Slice),減少被中斷發生Task Context-Switch的次數.藉此可以提高 Cache的利用率 (每次Context-Switch都會導致Cache-Flush). 比較適合用在固定週期執行的Batch Jobs任務主機上,而不適合用在需要使用者互動的產品 (會由於Task切換的延遲,而感覺到系統效能不佳或是反應太慢). 2,Real-Time Scheduler Class (實作在檔案 sched_rt.c中): 支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR. (SCHED_RR task預設的 Time Slice長度為100 msecs.). 3,Idle Task Scheduler Class (實作在檔案 sched_idletask.c中): 支援SCHED_IDLE,為系統中的Idle Task排程. 4,Stop Scheduler Class (實作在檔案 sched_stoptask.c中):屬於 Stop-Task Scheduling Class的Task是屬於系統中最高權限的Task,會中斷所有任務的執行,並且不會被其他任務所中斷. 目前系統中,Scheduling Class的優先級順序為 Stop-Task > Real-Time > Fair > Idle-Task,開發者可以根據自己的設計需求,來把所屬的Task配置到不同的Scheduling Class中. 在支援Fair Group Scheduling環境下,以CGroup (Control Group) Scheduler分配Task與Group的處理器執行時間. Control Group 提供了Linux核心可以把Tasks進行整合/區分或是依據子Group進行分派的動作. 根據Control Group文件中的定義,一個CGroup可以關聯到屬於1或多組SubSystem中的多個Tasks. SubSystem主要是基於CGroup提供的Task Group機制,扮演類似資源管控的角色,用以設定調配每個Group使用資源的限制. 在支援Control Group的Linux Kernel中,每一個Task在系統中都會屬於一個CGroup與一個SubSystem,每一個SubSystem都會有一個系統設定的組態,並配置到對應的CGroup中. 每一個Hierarchy架構,都有一個屬於CGroup虛擬檔案系統的Instance參考. 在系統運作時,會有多個有從屬關係的Task Groups同時運作,每一個Hierarchy都會屬於這系統中所有Tasks的一部分. 使用者可以透過CGroup虛擬檔案系統中的目錄名稱產生或刪除對應的CGroup,並可以查詢哪個CGroup有Task被指派,或是列出對應CGroup中所有被指派的Task PIDs. 藉由CGroup的設計,還可支援基於使用者帳號(Account)的處理器資源調配目的.(包括可以限定能使用的處理器或是Memory Node.) 參考 include/linux/cgroup_subsys.h的實做,目前CGroup包括以下的SubSystem, 1,cpuset (CONFIG_CPUSETS):用以限定指定的Tasks使用的CPU與Memory資源,有關cpuset的使用可以透過函式sched_setaffinity,sched_getaffinity,set_mempolicy,get_mempolicy,mbind. 例如下述的例子,可以由應用程式透過函式sched_setaffinity指定當應用程式執行時,所要使用的處理器編號.
2,cpu_cgroup (CONFIG_CGROUP_SCHED):這選項會支援Tasks能被群組(Group)化與依據設定切割群組佔用的處理器執行時間. 更進一步,還可以設定CONFIG_RT_GROUP_SCHED用以支援群組的 Real-Time排程 (支援包括 SCHED_FIFO 與 SCHED_RR). 與可以設定CONFIG_FAIR_GROUP_SCHED 用以支援群組的CFS排程機制(支援包括SCHED_NORMAL與SCHED_BATCH). 3,cpuacct (CONFIG_CGROUP_CPUACCT):這選項用以支援CPU Accounting Controller機制,透過CGroup機制群組Task,並依據使用者的帳號(Account)所產生的Task群組來劃分處理器的執行時間. 4,debug (CONFIG_CGROUP_DEBUG):用以支援CGroup的Debug機制,像是Task Reference Count等統計資訊. 其它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機制下,會統籌100%的處理器資源. 所有的處理器支援會根據root_task_group與所屬的子Task-Group的 Weight (=se->load.weight)基於Fair-Scheduling機制來進行處理器資源的分配工作. 舉實際的例子來說,當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% . 我們可以參考如下操作流程,產生一個驗證Control Group的目錄,並在其中產生cpu目錄,並掛起CPU與CGroup相關的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檔案看到目前處理器上所有執行的Task Process ID,並從cpu.shares知道目前處理器所分擔的CPU Load基數. 接下來,我們透過Control Group產生 GroupA與GroupB兩個Task Group群組,如下所示 [root@localhost cpu]# mkdir GroupA [root@localhost cpu]# mkdir GroupB 然後透過設定 cpu.shares,把GroupA的cpu.shares設定為4096,GroupB的cpu.shares設定為1024,也就是說在實際執行上,屬於GroupA的Tasks會比 GroupB的Tasks多得到約4倍的實際處理器執行時間. [root@localhost cpu]# echo 4096 > GroupA/cpu.shares [root@localhost cpu]# echo 1024 > GroupB/cpu.shares 接下來我們用如下的程式碼,分別編譯為GroupA與GroupB的執行檔名稱,兩者唯一的差異只在於讓printf顯示的字串各別表示出自己是由GroupA或 GroupB所吐出的內容而已. #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; } 執行編譯好的GroupA與GroupB執行檔,兩者Process ID分別為 1738與 1739,然後把這兩個Process ID分別設定給我們已經設定好差距四倍處理器執行時間的兩個Control Group目錄下的檔案tasks. [root@localhost cpu]# echo 1738 > GroupA/tasks [root@localhost cpu]# echo 1739 > GroupB/tasks 我們可以透過top 指令查看這兩個程式執行時各自所佔的CPU比率與兩者的差距,如下所示,GroupA佔據處理器約80.6%的執行時間而GroupB佔據處理器約19.9%的執行時間. (兩者相加為100.5%,超過100%,但這是筆者環境中top的真實結果(或該說誤差),在此就不作討論),以比率來說兩者所佔CPU實際執行時間差距大約也是四倍,符合我們透過Control Group對Task執行時間比率所做的設定. 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 再以實際的執行結果來看,由於GroupA比GroupB多分到四倍的處理器執行時間,也因此在Console所顯示的結果上,GroupA大約每顯示四個字串結果後,GroupB才有機會顯示一次,如此也符合我們透過Control Group所設定分配的處理器執行資源比率. 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優先級的簡要介紹 如下圖所示為CFS之前,Linux Kernel 2.6排程的優先級機制,右邊是屬於Task Real-Time優先權,左邊是Task的Nice Value,系統初始化後,一個最原始的行程產生時,預設的Real-Time優先權為0,而Nice優先權亦為0. Linux Kernel會根據Nice Value來計算該Task執行時間Time-Slice值的大小. 當使用者把行程的Nice Value遞減時(最低為-20),就表示該行程的優先權提高,相對的在排程時就會取得比較多的Time-Slice. 相對的,若不斷的增加Nice值(最大為19),就表示該行程的優先權降低,所取得的Time-Slice亦較低. 但若使用者有Real-Time的需求時,希望特定的行程可以以較高的優先權執行,但又不希望如同增加Nice值一般,也對應增加了Time-Slice時,就必須要設定屬於Real-Time的優先權. 而real-Time的優先權最小為1,最大為99,該值越大在排程時會越先被執行到. 有關Linux Kernel 2.6.10 核心Nice Value與對應之Time-Slice關係,可以參考下表
如下圖所示,筆者把Nice值對應到的Task Priority與對應的排程機制進行對比,我們可以看到在Task Priority 100-139 (對應為Nice -20 – 19 或 User Priority 0-39)的區間內,為一般應用Task的排程機制,使用的Scheduling Class為Normal與Batch,而屬於Real-Time排程機制對應到的Task Priority為0-99,使用的Scheduling Class為Round-Robin與FIFO.
CFS在Linux Kernel 2.6.23之後,參考Tasks優先級所施行的Time Slice與Real-Time措施 基於CFS RBTree的概念,由於會一直確保Virtual RunTime值的平衡,透過抓取佔據Virtual RunTime執行時間最短的Task來執行,因此像是原本排程中會透過Nice值計算對應Task可運作Time Slice的設計方式,就變的需要有所調整,也因此在CFS中會透過函式calc_delta_mine (實作在 kernel/sched.c),根據目前Task的優先級計算在排程時每次一個Scheduling Tick要增加的Delta值,也就是說如果該Task Nice值越高(優先級越低)該Delta值就越大,對該執行的Task來說就是Virtual RunTime在運作時,增加的速度越快(等於縮短實際執行的時間),反之,如果該Task Nice值越低(優先級越高)則Delta值就越小,在每次Scheduling Tick觸發時,Virtual RunTime增加的速度越慢,能獲得處理器執行的實際時間也就越長. 參考kernel/sched_fair.c的實作,函式calc_delta_mine的呼叫來源有兩處,
以筆者在 64bits處理器下,所使用的Linux Kernel 2.6.38.6來說,函式calc_delta_mine的幾個關鍵數字如下所示 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) 根據目前的實作,Delta的返回值會透過如下流程來計算 1,如果lw->inv_weight 為0,就會執行下列的計算 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); 舉實際的例子來說,當傳入的參數 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執會進行如下計算 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. 對應到不同函式參數所換算回來的Delta值,筆者整理如下表所示
透過上述的計算,我們可以知道影響Virtual RunTime Slice增加的Delta值最大的關鍵是在下面三個參數,筆者在此也簡述這三個參數的意義. 1,delta_exec: 是目前Virtual RunTime Slice的Delta值,會用來當作calc_delta_mine的第一個參數,用以計算出新的Delta值. 根據目前的實作,這個值可以表示在呼叫函式calc_delta_mine前,該Task所執行的時間間隔,也就是說如果該值越大,表示該Task在這次呼叫函式calc_delta_mine前,所得到的執行時間越長,相對的再透過Weight的計算後,下一次得到的Delta值就越大,對應到真實執行時間就會越少 (因為Delta值變大,執行時Virtual RunTime增加的速度就越快.). 2,weight:為目前Task的Load Weight,若Task的Nice值為 0,則此值為1024. 這個值越大,透過calc_delta_mine所計算的inv_weight 值越小,對應該 Task所計算出來的Delta值也越小,也就表示該Task的Virtual RunTime增加的越慢,因此實際得到處理器執行的真實時間就越長. 3,lw->weight:為目前排程單位sched_entity的Load Weight . 如果se->load.weight等於Nice 0的 Load Weight (1024),函式calc_delta_fair就會直接返回所傳入的Delta值,反之才會進入函式calc_delta_mine,重新計算新的Delta值. RunQueue的參數load->weight,會等於該RunQueue中所有Schedule Entity的load->weight總合,分別表示整個RunQueue執行單元的負荷與個別執行單元的負荷. 參考函式set_load_weight的實作(in kernel/sched.c),我們可以把不同的Task Priority ,Nice值與所對應的Scheduling Entity Load Weight值對應如下表所示
一般來說,如果Nice值加一 (也就是優先級降低一),大約會減少10%處理器的執行時間,而如果是Nice值減一(也就是優先級調升),大約就會增加10%處理器的執行時間.而參考上表整理的結果,每個Nice值的區間所對應的Weight大約會相差1.25倍. 例如15*1.25=18.75,18*1.25=22.5… 介紹到此,我們可以發現像是O(N),O(1)或是CFS (O(Log2(N))),都沒有把處理器不等速的問題考慮進來.也因此,在支援像是aSMP架構時,這部份的排程機制改善,就是攸關能否發揮aSMP架構優勢的關鍵. 結語 多核心架構肯定會是未來智慧型手機晶片的主流,要能在智慧型手機方案中發揮架構的優勢,了解Linux Kernel的排程機制,會是一個必要的基礎功課. 本文主要著重在Linux Kernel排程的介紹,從前一代的Linux核心排程機制談起,到目前基於CFS的核心排程與相關資料結構的說明. 但要發揮多核心的優勢,除了Linux Kernel的層次外,在Android Framework上也需有所因應,後續筆者會再進一步的加以介紹.希望能讓閱讀本文的開發者有所助益.
People who looked at this item also looked at…
Related items |
|