hlchou@mail2000.com.tw
by loda
一， 前言
Linux 在嵌入式作業系統的發展一直以來都是備受矚目的，以往Linux 2.4核心由於系統Clock Interrupt的限制為1/100秒，以致於核心排程的即時性，受到壓抑，然而隨著Linux 2.6核心的推出，Clock Interrupt預設為1/1000秒，相對使得原本的即時排程(First-In-First-Out與Round-Robin)與一般行程排程應用上得以滿足更多樣化之需求。
同時，以往2.4核心並不支援Preempt，因此若有一Kernel Thread或系統呼叫進入無窮回圈或是其它死結，極易導致核心停擺。2.6核心中，針對Kernel Thread提供了Preempt機制，使得Kernel Thread的撰寫上更有彈性，即便透過核心排程後取得執行權的Kernel Thread不主動釋放處理器資源，亦會被核心排程依據其所分配到的Time-Slice時間，而置換出去，減輕對核心造成影響。同時新版:2.6核心的O(1)演算法，亦大幅提高了核心排程與行程切換的效率。
整體而言，目前2.6 版本的核心已能滿足Soft Real-time 應用上的需求，但在Hard Real-time之應用，Linux 2.6核心仍有相當大的進步空間，以目前而言MontaVista 極有機會進一步針對核心的Hard Real-time支援進一步投入發展，並在未來成核心的一部份。
在新版的核心上，針對每一個行程的處理彈性更為提高，以往2.4核心對於行程提早釋放處理器資源，所造成的Time-Slice不斷累加，進而影響系統效能，與父程序開啟大量快速結束的子行程，所造成父程序執行時間不公平的問題，都逐一在2.6的核心上獲得解決。
很明顯的，2.6版本的核心比起以往的Linux 核心有長足之進步，並足以應付更為艱鉅與多樣性之應用與開發，對於國內產業而言導入與進一步發揮Linux 2.6 核心的特性，將是一必要且刻不容緩之趨勢，期待本文可以讓各位在選擇與進一步瞭解2.6核心運作上有所幫助。
(本篇文章主要依據 Linux Kernel 2.4.19與2.6.10，所舉出的原始碼亦出自這兩個版本的核心)
二， 系統架構
首先，在看到Linux 核心排程機制前最重要的一點就是要先解析核心支援的不同優先權設定機制，如下圖(一)所示，右邊所代表為屬於Real-Time的行程優先權，左邊代表的是一般行程的優先權。系統初始化後，一個最原始的行程產生時，預設的Real-Time優先權為0，而Nice優先權亦為0，系統再決定該行程所分配的Time-Slice長短時就是依據Nice值，當使用者把行程的Nice值遞減時，就表示該行程的優先權提高，相對的在排程時就會取得比較多的Time-Slice，相對的，若不斷的增加Nice值，就表示該行程的優先權降低，所取得的Time-Slice亦較低。但若使用者有Real-Time的需求時，希望特定的行程可以以較高的優先權執行，但又不希望如同增加Nice值一般，也對應增加了Time-Slice時，就必須要設定屬於Real-Time的優先權。而Real-Time的優先權最小為1，最大為99，該值越大在排程時會越先被執行到。
因此，筆者舉出以下的例子加以說明
(1) 有兩個行程A與B，兩者Real-Time與Nice初始值均為0，在執行後行程A把Nice值降低了，此時行程A隨著Nice值的降低可以取得比較多的Time-Slice時間，由於兩者Real-Time優先權均為0，因此在排程時行程A可以被優先排程，並執行較久的時間。
(2) 此時，行程B希望可以優先執行，但又不希望增加Time-Slice，因此行程B將Real-Time的優先權由0設為1，但不改變Nice值，依舊為0。在排程時，行程B將會優先被執行到，之後才會執行行程A，然而行程A可以佔據比較久的處理器執行時間。
依據這樣的原則，我們在設計系統與產品時，就可以將比較緊急的工作拉高Real-Time優先權，使其優先處理，而較不緊急但需要長時間運算的行程，就可以透過僅降低Nice值的方式，提高其在Nice上的優先權，取得更多的處理器時間用來運算，以達到符合產品化需求之系統設計。
由於使用者可設定的Nice優先權值最小為19(表示等級最低)。因此Linux 2.4核心針對閒置時間時執行的 Idle 行程，將其Nice優先權值設定為20，使得沒有一個使用者的行程可以將Nice優先權值設定的比Idle行程等級更低。
圖(一)，Linux環境下支援的兩類Priority設定機制
2.4/2.6核心除了原本預設的RTC (Real Time Clock) Timer觸發由1/100改為1/1000外，包括執行程序的Time-Slice計算方式也有所不同，而Linux核心的Time-Slice計算方式主要以每個行程的Nice值決定。每個行程在產生時預設的Nice值均為0，然而若該行程是透過父程式所產生的(例如: 透過 thread_create 函式所生成的子程序)，該子程序就會繼承父程序預設的Real-Time與Nice優先權值，也就是說子程序與父程序會擁有同樣的Real-Time與Nice優先權值，並且在下一次排程重新計算每個行程的Time-Slice前，父程序會先將一半的Time-Slice分給子程序，也就是 父程序只擁有產生子程序前一半的Time-Slice，另一半則分給子程序，直到下一次重新計算Time-Slice後，子程序與父程序才各自依據自己的Nice值取得對應的Time-Slice。
如下所示為2.4核心計算行程Time-Slice的運算函式，其中HZ值筆者取的是2.4核心預設的RTC Timer中斷觸發頻率1/100秒，因此之後的運算中HZ為100。
|
#if HZ < 200 #define TICK_SCALE(x) ((x) << 1) #define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1) |
基於這組函式，我們依據不同行程所設定的Nice值差異透過公式NICE_TO_TICKS 得到如下表(一)的結果
表(一)， 2.4 核心 Nice Value與對應之Time-Slice
Nice Value |
Time Slice |
|
-20 |
110ms (TICK_SCALE(40)+1) |
|
1 |
50ms (TICK_SCALE(19)+1) |
由此我們可以知道，在2.4的核心中，每個行程Time-Slice最小單位為10ms，最大可為110ms。
在我們介紹完2.4核心如何計算Time-Slice之後，接下來讓我們檢視在2.6核心下是如何計算每一個行程的Time-Slice。
如下所示為2.6核心計算行程Time-Slice的運算函式，同樣的由於2.6核心的RTC Timer預設中斷觸發頻率為1/1000秒，因此在之後的運算中HZ為1000。
|
//In kernel/sched.c * can work with better when scaling various scheduler parameters, * it’s a [ 0 ... 39 ] range. */ #define USER_PRIO(p) ((p)-MAX_RT_PRIO) #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio) #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) //it will be 40 ……… * * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger), * default timeslice is 100 msecs, maximum timeslice is 800 msecs. * Timeslices get refilled after they expire. */ #define MIN_TIMESLICE max(5 * HZ / 1000, 1) #define DEF_TIMESLICE (100 * HZ / 1000) |
每當核心排程機制要計算一個行程的Time-Slice值時，就會呼叫函式task_timeslice 用來計算各別行程的Time-Slice。基於這組函式，我們依據不同行程所設定的Nice值差異，得到如下表(二)的結果
表(二)， 2.6 核心 Nice Value與對應之Time-Slice
Nice Value |
Time Slice |
|
-20 |
800ms (DEF_TIMESLICE * 4 * 40 /20) |
|
1 |
95ms (DEF_TIMESLICE * 1 * 19 /20) |
由此我們可以知道，在2.6的核心中，每個行程Time-Slice最小單位為5ms，最大可為800ms，明顯的比起原本2.4核心的行程Time-Slice計算方式顯得更有彈性，與不同Nice優先權間的差異化表現。
接下來，在我們正式比較2.4/2.6核心排程原理以前，筆者先將兩者主要用來描述每一個行程狀態的 ”task_struct” 與 在2.6核心內用來描述屬於每一個處理器排程運作的 “runsqueue” 資料結構，加以說明，作為後續進一步討論核心排程原理的基礎。
以2.4核心而言，描述每個行程的task_struct 主要變數如下所示
|
變數名稱 |
說明 |
|
state |
用以表示目前行程運作狀態，包括有TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、TASK_ZOMBIE |
|
need_resched |
用以表示行程是否需要被置換掉 (當行程time-slice為0時，此變數就會被設為1) |
|
policy |
用以表示行程支援的排程原則SCHED_FIFO 、SCHED_RR 、SCHED_OTHER 、SCHED_YIELD |
|
rt_priority |
用以儲存行程的Real-Time等級1-99，預設為0 |
|
counter |
用以儲存行程目前剩餘的Time-Slice(以RTC 中斷頻率為單位，1/100秒) |
|
nice |
用以儲存行程的nice值(-20至19)，預設為0 |
|
cpus_allowed |
透過Bit-Mask方式來表示該行程被允許在那個處理器上執行(1=允許) |
|
cpus_runnable |
透過Bit-Mask方式來表示該行程正在那個處理器上執行(1=正在執行中的處理器，cpus_runnable = 1 << cpu |
|
processor |
儲存目前行程使用處理器的編號 |
以2.6核心而言，用以描述每個處理器執行行程與排程資訊之runqueue如下所示 (可參考核心程式碼 kernel/sched.c)
|
變數名稱 |
說明 |
|
lock |
每個處理器都有一個runqueue，而runqueue則是透過這一個變數作為locker，用來防止同一個處理器對自己的runqueue發生重複進入(re-entry)的問題 |
|
nr_running |
目前正在該處理器上執行行程的數目 |
|
nr_switches |
該處理器上行程切換的次數 |
|
nr_uninterruptible |
該處理器上 state為TASK_UNINTERRUPTIBLE 的行程數目 |
|
expired_timestamp |
用以儲存當Active-Task-Queue第一次將執行完畢的行程切換到Expired-Task-Queue的時間點
如下程式碼
核心會呼叫EXPIRED_STARVING(rq)確認目前runqueue已有多久沒有進行Active-Task-Queue與Expired-Task-Queue置換，以避免已被切換到Expired-Task-Queue的行程等待太久而沒有機會被執行到，EXPIRED_STARVING(rq)會進行以下步驟 (1)將目前系統的時間(jiffies)減去(rq)->expired_timestamp，若大於STARVATION_LIMIT * ((rq)->nr_running) + 1) (2)比對目前正在執行行程的優先權是否小於以被置換到Expired-Task-Queue中行程優先權最高優先權(((rq)->curr->static_prio > (rq)->best_expired_prio))
|
|
timestamp_last_tick |
用來儲存最後一次核心排程更新的tick值
rq->timestamp_last_tick = sched_clock(); |
|
*curr, *idle |
curr 儲存目前正在執行的行程，idle 儲存目前處理器預設的idle行程 |
|
*active, *expired, arrays[2] |
每個處理器都會有一獨立的runqueue用來管理其執行的行程，而每個runqueue都會有兩個prio_array arrays，主要透過兩個記憶體指標active與expired來動態的切換目前runqueue正在執行中的Active-Task-Queue與Exipred-Task-Queue |
|
best_expired_prio |
用來紀錄目前Exipred-Task-Queue中所有行程優先權最高值(也就是取所有行程 static_prio 數字最低者) |
以2.4核心而言，描述每個行程的task_struct 主要變數如下所示 (可參考核心程式碼 include/linux/sched.h)
|
變數名稱 |
說明 |
|
State |
用以表示目前行程運作狀態，包括有TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、TASK_TRACED、EXIT_ZOMBIE與EXIT_DEAD |
|
Policy |
用以表示行程支援的排程原則SCHED_FIFO 、SCHED_RR 、SCHED_OTHER 、SCHED_YIELD |
|
*thread_info |
指向目前行程的thread_info，thread_info包含每一個行程最重要的資料，包括preempt_count(若大於0，則此行程不可被Preempt) 、flags(Thread Information Flags)與cpu(目前行程使用的處理器)…etc，在x86平台上thread_info會被置於esp目前所指位置偏移8kbytes的位置
核心可透過函式current_thread_info 取得目前執行中的行程thread_info位址 (實作於核心程式碼 arch/arm-i386/thread_info.h) static inline struct thread_info *current_thread_info(void) { struct thread_info *ti; return ti; }// THREAD_SIZE=8192 |
|
prio, static_prio |
Prio值介於0-139之間 (MAX_PRIO-1) 其中Real-Time優先權等級介於1-99之間 (MAX_RT_PRIO-1) |
|
*array |
指向目前的Active-Task-Queue |
|
run_list |
被目前對應優先權等級的Task-Queue-List連結，用來讓排程可以很快的透過 run_list偏移固定的Offset，定位到行程task_struct的記憶體起始點 |
|
sleep_avg |
用來儲存行程有多久時間沒被處理器使用到的平均值，最大不超過NS_MAX_SLEEP_AVG (1000000000 ns)，該值會被核心函式effective_prio使用來調整非Real-Time行程的優先權。 |
|
interactive_credit |
用來記錄行程屬於INTERACTIVE的比重，通常主要適用於GUI或等待硬體裝置完成狀態之應用程式，介於-100-101(CREDIT_LIMIT+1) 之間。通常這類程式會有相當多的時間等待使用者輸入資訊，因而往往也未能充分利用該等級所分配到的time-slice，因此隨著該值的提高與sleep_avg的增加，將可適度的調高其優先權，並增加這類程式在使用者有輸入動作或硬體裝置回應時，可以憑藉較高優先權快速的取得處理器執行權，並回應後續動作 |
|
timestamp, last_ran |
Timestamp儲存上一回被排程的處理的時間 (包括被核心排程切換出/入處理器與被Activated的時間點，單位為nanosecond) |
|
activated |
用以表示行程被activate前的狀態，例如在activate_task與try_to_wake_up函式中，若行程被置入runqueue前為Interruptible的行程，且目前正有一發生中斷尚未結束中斷處理，則行程activated設定為2，反之若未在中斷區間內，行程activated設定為1，若該行程原task_struct-> state為TASK_UNINTERRUPTIBLE，則設定為-1。最後到了核心排程函式schedule()中，會將確定要切換執行的新行程activated設定為0(TASK_RUNNING) |
|
cpus_allowed |
透過Bit-Mask方式來表示該行程被允許在那個處理器上執行(1=允許) |
|
time_slice, first_time_slice |
time_slice值記錄了每個行程被分派到與目前所剩下的處理器執行時間 |
|
nvcsw, nivcsw |
nvcsw值儲存目前行程stat不為TASK_RUNNING並且未取消Preempt機制行程的Context-Switch次數 |
|
exit_state |
用以表示行程結束狀態，包括有EXIT_ZOMBIE與EXIT_DEAD |
thread_info->flags 中，因此若在2.6核心下有一行程的time-slice用盡，需要排程時就需要將此flags設為 3(TIF_NEED_RESCHED)。更進一步，由於2.6的核心支援Preemp的能力，因此對核心行程而言，如要避免執行過程中被Preempt，則可以透過核心支援的函式preempt_disable暫時取消Preempt功能，該函式每呼叫一次會將目前行程的 thread_info-> preempt_count加一，只要該值大於0，則此行程就不能被Preempt，除非其主動放棄執行時間或是該值重新降為0。
接下來，讓我們開始正式討論2.4/2.6核心排程原理的概念與差異。
首先如下圖(二)所示，在2.4的核心中所有的處理器共用同一個Task Qeueu，每當一個行程結束後，就會透過呼叫goodness函式計算所有行程的Weight值，並取出Weight值最高的行程放到處理器去執行，直到所有行程經由goodness函式計算的Weight值均為0為止。
這樣排程有一主要的問題，在於每次要選擇一個行程至處理器運作時，都要透過goodness計算選擇Weight值最高的行程，也就是說每次選擇行程執行時，都要有一額外運算透過goodness計算每個行程的Weight，並透過比較選出最高值的行程。除此之外，另一問題則為由於2.4核心每個行程的Time-Slice重新計算是在所有Task Queue行程Weight值均為0之後，也就是說要等到Task Queue中沒有任何一個行程可供執行時，才重新計算所有行程的Time-Slice，進行下一輪的排程動作，因此當Task Queue中有N個行程時，每當要重新計算Time Slice時就要進行O(N)的運算成本，如此對於有即時性需求或是要求行程切換高效率的環境時，顯然將遇到瓶頸。
而2.4核心為了使核心排程運作得以順利進行，包括在使用者透過0×80號中斷呼叫System Call返回時，如下所示
|
//In arch/i386/kernel/entry.S ENTRY(ret_from_sys_call) cli cmpl $0,need_resched(%ebx) jne reschedule e將跳至核心排程schedule()函式 cmpl $0,sigpending(%ebx) jne signal_return restore_all: RESTORE_ALL |
或是在核心其它運作機制中都加入了呼叫核心排程 schedule() 函式的動作，使得2.4的核心排程機制得以順利運作。
目前2.6核心排程有兩個主要的特性，是此次更新最受矚目的，首先就是由Ingo Molnar 所設計的 “New ultra-scalable O(1) schedule”，O(1)演算法的特色在於每當有一個行程結束時，就會立刻重新根據目前行程的優先權算出新的的Time-Slice，並放到Expired-Task-Queue 對應的行程優先權 Queue中，也因此每一次行程結束要切換到下一個新的行程時，固定運算Time-Slice的成本為O(1)，相對於原本2.4核心計算Time-Slice 的O(N)演算法而言，2.6的核心排程有效的把重新計算Time-Slice的動作隨著時間與行程的運作分擔出去，讓行程的切換所造成的效率影響降低。
另一個受矚目的特性就是由Robert Love 所設計的 ”Preemptible kernel bits”，原本的2.4核心由於核心排程在切換行程時，是無法在中斷發生期間運作的，因此例如當使用者應用程式透過0×80號中斷呼叫System Call時，如果該System Call沒有返回User-Mode，就算系統的RTC Timer中斷能持續的觸發，但也只是讓目前執行中的行程Time-Slice減到0為止，但核心排程由於目前中斷尚未結束，因此並無法順利運作切換行程，因此會導致2.4核心排程的運作終止。進一步來說這樣的結果亦會導致若系統中有一行程每次呼叫系統呼叫後，都會延遲至超過它所能執行的Time-Slice，進而使得其它行程無法及時使用分配到Time-Slice的不公平現象。另一個問題就是，當Kernel Thread陷入無窮迴圈或其它死結時，系統將無法透過其它機制觸發核心排程使其運作正常。但在核心加入了Preempt特性後，不論是在系統呼叫中斷期間，或是遇到Kernel Thread陷入無窮迴圈的情況，系統都能夠即時有效的觸發系統核心排程schedule()函式的運作，其中有一關鍵點則在於現在的2.6核心排程schedule()函式是允許在中斷呼叫期間岔斷的，也就是說即使是在0×80號中斷的執行區間中，核心排程都可以公平的把目前Time-Slice用完的行程切換出去，讓其它行程可以公平的分享到處理器的運算資源。
如下圖(三)所示，目前2.6核心排程機制是每一個處理器都會分配到一個runqueue，在這個runqueue中會包括兩個使用者的Task Queue，分別為Active-Task-Queue與Expired-Task-Queue，每個處理器正在執行與準備要執行的行程都會存在Active-Task-Queue中，一但行程執行完畢後，就會立刻重新依據行程目前的Nice優先權計算Time-Slice，並根據它的Real-Time與Nice優先權移到Expired-Task-Queue中。一旦Active-Task-Queue中沒有任何行程需要執行時，就只要將只向兩個Queue的Array 記憶體指標互換即可，使得該處理器將剛剛的Expired-Task-Queue當成全新的Active-Task-Queue使用，而剛剛使用完畢的Active-Task-Queue則當做新的Expired-Task-Queue，用來存放這一階段執行完畢的行程。
圖(三)，2.6核心排程Run-Queue 示意圖
如下圖(四)所示，每個Active-Task-Queue與Expired-Task-Queue都會包括140個等級的Task-Queue-List，依據每個行程Real-Time與Nice值的不同儲存到不同的Task-Queue-List，而每個Task-Queue的資料結構如下所示，會包括
(1)nr_activee用來紀錄目前Task-Queue中有多少等待執行的行程
(2)bitmape透過Bitmap方式用來快速對應所有行程等級中，是否有等待執行的行程
(3)queuee透過Linux Kernel支援的Link List函式，用來將同一等級的行程連結在一起，目前一開始建立140個list_head的Array，用來代表140個等級優先權行程Link List起點.
|
(MAX_PRIO = 140) #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)) (BITMAP_SIZE=5) struct prio_array {
|
接下來我們舉幾個例子，作為如何依據不同Real-Time與Nice值配置到不同Task Queue List的範例
(1) Real-Time優先權為99，Nice優先權為0就會放到Queue 0 (以Real-Time等級為主)
(2) Real-Time優先權為0，Nice優先權為-20就會放到Queue 100 (不為Real-Time等級，但Nice優先權等級最高)
(3) Real-Time優先權為0，Nice優先權為19就會放到Queue 139 (不為Real-Time等級，但Nice優先權等級最低)
每個等級的行程要加入時，都會加到該等級Task Queue List的最後面 (透過核心函式list_add_tail)。
圖(四)，2.6核心依據140個優先權等及所劃分出的Task Queue List
如下圖(五)所示，為了加速核心排程快速從高至低等級中(Queue0 -> Queue 139)找到目前Task Queue List中有需要執行的行程，因此在2.6核心中支援了透過Bitmap對應的機制，讓核心排程可以透過比對該Bit是否為1判斷哪一個Task-Queue-List中有需要執行的行程，而對應到2.6核心中支援的140個等級，因此需要五個32-bits整數(BITMAP_SIZE=5)來儲存這些資訊。
圖(五)，140行程等級對應的Bits Array
然而，如何快速透過這五個32-bits整數對應找到目前哪一個Task-Queue-List有需要執行的行程，也是一個攸關效能執行的要素。在x86的平台上，2.6核心透過函式sched_find_first_bit快速搜尋為1的bit相對位置，其中並呼叫函式__ffs，該函式主要透過x86指令集bsfl提供快速搜尋32-bits整數Bit值設定相對位置的能力。
|
//in include/linux/compiler.h: * @word: The word to search * * Undefined if no bit exists, so code should check against 0 first. */ static inline unsigned long __ffs(unsigned long word) { __asm__("bsfl %1,%0″ :"=r" (word) :"rm" (word)); return word; } * way of searching a 140-bit bitmap where the first 100 bits are * unlikely to be set. It’s guaranteed that at least one of the 140 * bits is cleared. */ static inline int sched_find_first_bit(const unsigned long *b) { if (unlikely(b[0])) return __ffs(b[0]); if (unlikely(b[1])) return __ffs(b[1]) + 32; if (unlikely(b[2])) return __ffs(b[2]) + 64; if (b[3]) return __ffs(b[3]) + 96; return __ffs(b[4]) + 128; } |
如下圖所示(六)，目前每個等級的Task Queue List都是透過struct list_head來串聯每個該優先權等級行程，而目前2.6核心為了透過Link List的使用，加速行程task_struct的查訪，因此每個在Task-Queue-List中的行程都是透過task_struct中的 “run_list” 來串聯的，對核心排程來說只要找到”run_list”再偏移固定的相對位置，就可以找到該行程task_struct的起始位址了。
圖(六)，Task Queue List中透過 run_list去查訪 task_struct的起始位置
因此如下圖(七)所示，綜合以上的描述我們可以得知在2.6核心下，不論是Kernel Thread或是一般使用者行程的產生(包括fork 或 thread)，都會被核心排程當成一個行程處理，只是所對應的記憶體空間是否共用或是牽涉到切換使用者行程資源的問題(例如是否需要切換 TLB (Translation Look-aside Buffer))。
舉個例子來說，如果今天有一個使用者行程產生了五個Thread，對核心排程來說就會有五個新增的行程產生，包括原本的使用者行程，核心排程就需要針對這六個行程在核心排程中依據它們的優先權排定執行等級與個別的Time-Slice。在經過核心排程運算後，這六個行程的Time-Slice是各自獨立的，各自依據自己使用的處理器執行時間而遞減Time-Slice。
圖(七)，在2.6核心下包括Kernel Thread, Process與User-Mode Thread都會透過核心排程
在介紹了2.4/2.6核心的排程原理與相關資料結構後，接下來要介紹的就是維繫核心排程運作中最重要的Timer，透過一個穩定的硬體Timer中斷觸發，核心排程才能準確的估量每一個行程所耗用的Time-Slice，並在正確的時間點觸發行程的切換，使得每一個行程都可以依據所配置的行程優先權等級，分配到公平的執行時間，以維繫系統的正常運作。
而Linux核心的Timer中斷觸發基本上分為兩個部分，以x86為例，Timer中斷Top-half 的部分主要實做是在檔案 “arch/i386/kernel/time.c” 中，這部分主要放置了時間急迫性比較高的中斷處理程式，而另一部分時間急迫性較低的Timer中斷Bottom-half 部分則實做在檔案 “kernel/timer.c” 中。
如下圖(八)所示，為2.4核心的 Bottom-half 部分Timer運作示意圖，我們可以發現透過Bottom-half 部分的do_timer函式，會持續的透過呼叫update_process_times函式，並由該函式依序遞減目前正在執行行程task_struct中的counter值，直到它為0後，就設定task_struct中的need_resched為1，表示該行程Time-Slice已使用完畢，需要被切換出去。
圖(八)，2.4核心Timer中斷遞減行程Time-Slice示意圖
如下圖(九)所示，為2.6核心的 Top-half 部分Timer運作示意圖，其中timer_interrupt為IRQ觸發時直接處理中斷動作的函式，在依序呼叫過相關Top-Half Timer相關處理函式後，最後會呼叫函式update_process_times，並透過該函式呼叫函式scheduler_tick進行目前執行中行程Time-Slice遞減，並在該行程Time-Slice用盡時，設定task_struct->thread_info->flags為TIF_NEED_RESCHED(=3)，用以表示開行程需要被切換，並進一步觸發行程切換。
圖(九)，2.6核心Timer中斷透過呼叫scheduler_tick運算行程Time-Slice示意圖
由此可知，2.6核心對於行程處理的時間較為嚴謹，並且由於是透過Top-Half Timer中斷來實現時程與時間行為的控制，因此對於Real-Time反應的需求可以提供更高程度的準確性。
三， 深入探索
接下來，讓我們更進一步針對2.4/2.6核心排程的細部行為做進一步的介紹，針對相關的細節加以說明後，相信可以對於有興趣進一步探索核心排程原理的人，一個Hack Kernel Source Code的基礎。
如下所示，為2.4核心中核心排程函式schedule()運作的基本概念，筆者主要以文字描述流程
|
(1)把目前的行程儲存至prev (prev = current;)，並檢查目前行程排程機制是否為Round-Robin (SCHED_RR)，如果為真並且目前行程的counter (Time-Slice)為0，就將該行程的 counter 重新計算 (prev->counter = NICE_TO_TICKS(prev->nice);)，並將行程移至runqueue的尾端。 (2)確認目前行程的state，如果為 TASK_INTERRUPTIBLE, 就會呼叫signal_pending ，一但確認資源得到滿足，就會設定行程state為TASK_RUNNING。反之，若行程的state原本為TASK_RUNNING，就不作任何事情。若以上皆非的話，就將行程從runqueue中移除，而移除後的行程在未來將不會參與排程，除非該行程又被加入runqueue中。 (3)設定目前行程的 need_resched 為 0 (4)呼叫“list_for_each”函式去瀏覽目前runqueue中所有的行程，如果 ((p)->cpus_runnable & (p)->cpus_allowed & (1 << cpu)) 為真 ，就表示目前行程可在目前的處理器上被排程運作，並透過函式goodness()去重新計算每一個行程的weight值，透過逐一比較選擇目前最大weight值的行程，並將該行程儲存至變數next (next = p;)，作為要與目前行程切換運作的下一個行程。 (5)如果目前所有在runqueue中的行程weight都為0，就表示所有的行程都已執行完畢，如此則需要重新排程並計算所有行程新的Time-Slice，若行程有剩餘的Time-Slice值，就將該值的一半加入下一階段新取得的Time-Slice中 (p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);) (6)設定新的行程 next 至目前指定的處理器 (task_set_cpu(next, this_cpu);) (7)如果 prev 等於next，就表示目前的行程與新的行程是同一個行程，則無須進行Context-Switch (例如: 這樣的情況可能會發生在行程A執行完畢後，觸發排程重新執行，並且行程A成為該次排程中第一個被取出的行程) (8)接下來若next->mm為0的話，就表示新的行程為一kernel thread，因為kernel thread所對應的記憶體空間為核心模式，且核心記憶體空間並不會隨著行程的切換而受到影響，因此kernel thread的mm為0，並且切換行程時無須更新TLB (Translation Look-aside Buffer，虛擬記憶體分頁) 。反之若prev->active_mm->context.segments == next->mm->context.segments成立，則表示目前行程與新的行程共同對應到同一個行程空間中(例如為一行程中的多個執行緒)，則需要更新TLB (Translation Look-aside Buffer，虛擬記憶體分頁)。 (9)呼叫函式 “mmdrop” 釋放目前行程對應的記憶體空間 (10)呼叫函式“switch_to” 對目前行程與新的行程進行切換 |
如下所示為2.4核心中goodness()函式的原始碼，此goodness()函式是在2.4核心排程中最為關鍵的演算法，用來在每一輪選擇行程執行時，根據該行程目前的優先權、行程切換成本與剩餘的Time-Slice值，計算出的weight 值，作為選擇目前首先應該被執行行程的依據。
|
goodness() sources in kernel/sched.c
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
|
如下所示為goodness演算法的流程
|
‧goodness() algorithm (1)比對該行程的演算法policy是否為SCHED_OTHER (1-1)若是，則將目前行程剩餘的Time-Slice加入weight (weight = p->counter;) (1-2)若是在SMP架構下，則比較目前行程執行的處理器與要被切換過去的處理器是否為同一個，若是則可避免行程切換的成本，因此增加weight (weight += PROC_CHANGE_PENALTY;) (1-3)如果目前行程與新的行程無須進行記憶體重新切換的動作則增加weight (weight += 1;) (1-4)加目前行程的Nice值加入weight中 (weight += 20 – p->nice;)
(2)若非，則表示為 SCHED_FIFO 或 SCHED_RR排程演算法之行程，因此則將weight加上1000與目前的Real-Time優先權等級 (weight = 1000 + p->rt_priority;)，使得為SCHED_FIFO 或SCHED_RR之行程得以產生大於SCHED_OTHER行程的weight值，並確保可以優先被執行。
|
如下所示，為2.6核心中核心排程函式schedule()運作的基本概念，筆者主要以文字描述流程
|
(1) 首先，核心排程會呼叫函式preempt_disable關閉核心preempt能力，把目前的行程儲存至prev (prev = current;)，並呼叫函式this_rq取得目前處理器使用的runqueue (2) 計算行程前次經過排程處理過至目前為止的時間間隔 (now – prev->timestamp)至run_time中，並且run_time值<=NS_MAX_SLEEP_AVG (3)若行程interactive_credit大於CREDIT_LIMIT(=100)，則減少 run_time值 (4) 確認目前是否有行程在runqueue中 (!rq->nr_running)，如果沒有任何行程在runqueue中，則下一個行程設定為idle行程，並進行context-switch。 (5)檢查目前Active-Task-Queue中是否有行程等待執行 (if (unlikely(!array->nr_active)))，若無則將Active-Task-Queue與Expired-Task-Queue對調，如下程式碼
if (unlikely(!array->nr_active)) { ………. rq->active = rq->expired; rq->expired = array; array = rq->active; }…… (6) 透過bitmap尋找在Active-Task-Queue中有行程等待執行的優先權等級 (idx = sched_find_first_bit(array->bitmap);) (7) 用上一步取得的bitmap index，取得目前Task-Queue-List 的Queue位址 (queue = array->queue + idx;) (8) 從Task-Queue-List 中取出新的行程至next變數中 (9) 若新的行程非Real-Time優先權並且 activated值為 TASK_INTERRUPTIBLE，就計算新的行程上次排程至今的時間間隔(“current time – previous scheduling time”)，並將該行程移出task queue，呼叫函式recalc_task_prio重新計算該行程之 sleep_avg值，並透過函式effective_prio依據新的sleep_avg值更新行程之優先權，並將此行程重新置入task queue中 (10) 設定新的行程之 activated 為 0 (TASK_RUNNING) (11) 開始準備進行行程切換 (12)取消目前行程 flags 之TIF_NEED_RESCHED設定 (13)將目前行程sleep_avg減去run_time，若行程之sleep_avg<=0×00，則檢驗目前行程之interactive_credit，若介於(-CREDIT_LIMIT 與CREDIT_LIMIT)之間，則將interactive_credit 減一，降低其INTERACTIVE之屬性 (14) 更新目前行程 “timestamp” 與 “last_ran” 為目前的時間 (prev->timestamp = prev->last_ran =now) (15) 呼叫函式sched_info_switch去切換目前行程、新行程之runqueue相關資訊(包括runqueue等待時間(run_delay)、處理器執行之 time-slice數目(pcnt)與上一個行程分配至處理器的時間點(last_arrival) …等 (16)比對prev是否next相等，若是就表示目前的行程與新的行程是同一個行程，則無須進行 Context-Switch (17)呼叫Context-Switch - 若next->mm為0的話，就表示新的行程為一kernel thread，則切換行程時無須更新TLB (Translation Look-aside Buffer，虛擬記憶體分頁) 。反之若新行程的mm與目前行程active_mm不一致，則更新TLB (Translation Look-aside Buffer，虛擬記憶體分頁)，並檢查在x86平台下的行程LDT是否一致(if (unlikely(prev->context.ldt != next->context.ldt)))，若非則進行LDT之切換。(LDT相等表示為同一個使用者模式行程空間) - 最後呼叫switch_to()，進行行程切換 (18)重新開啟核心preempt能力 |
主要來說，2.4與2.6核心的差異還包括了
(1) 對於新產生的行程處理
在2.4核心中，一旦行程產生一個子行程，子行程的Real-Time與Nice優先權值也會等同於父行程，父行程並會將自己所剩執行時間Time-Slice加一除二後的值當作子行程的Time-Slice，而父行程本身所剩的Time-Slice也會除二，直到在下一次排程後，彼此才會依據目前的Nice值分配到各自對應的Time-Slice。
|
//Linux kernel 2.4 //Will share parent’s remaining time-slice (1/2) current->counter >>= 1;e 設定父行程 time-slice if (!current->counter) current->need_resched = 1;
|
如下所示，同樣的在2.6核心中，子行程的Real-Time與Nice優先權值也會等同於父行程，父行程並會將自己所剩執行時間Time-Slice加一除二後的值當作子行程的Time-Slice，而父行程本身所剩的Time-Slice也會除二，直到在下一次排程後，彼此才會依據目前的Nice值分配到各自對應的Time-Slice。
但與2.4核心最大的差異在於，2.4核心每個子行程在進入下一輪核心排程計算Time-Slice前，如果子行程結束運作，並不會把剩餘的Time-Slice還給父行程，如此造成的原因是一但父行程開啟過多的子行程，而每個子行程都很快就結束了，那會造成在那一輪執行時，父行程分配到的時間變的很短，而且也無法回收子行程時間。相對的，2.6核心在父行程產生子行程時會設定子行程的first_time_slice值為1，如此表示當子行程在重新排程計算Time-Slice前，如果有尚未用完的Time-Slice就會還給父行程，進一步避免了在短時間內父行程開啟大量快速結束的子行程所造成的運算資源不公平的問題。
|
//Linux kernel 2.6 //Will share parent’s remaining time-slice (1/2)
/** The remainder of the first timeslice might be recovered by * the parent if the child exits early enough. */ p->first_time_slice = 1;
|
(2) 對於time-slice過長的行程處理
在2.4核心中，在每一輪排程過的行程結束後，如果有行程有尚未使用完畢的Time-Slice(例如 等待一個Event，所以先放棄Time-Slice…etc，等到下一輪運作時再確認該Event是否成立)，在排程會透過呼叫NICE_TO_TICKS取得新一輪的Time-Slice，並將前一輪尚未用完的Time-Slice除二後加入新一輪的Time-Slice，如此造成的問題就是隨著時間的增加，這樣的行程可能會等造有一個行程的Time-Slice變的很大，進一步在某一點上，該行程取得處理器執行權後，會應佔據極長的時間，影響系統與核心排程的順暢運作。
|
//Linux kernel 2.4 // Waiting process will ? remaining time-slice,,,but it will be added repeatly every re-scheduling…. // couldn’t represent the actual world status…… p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
|
而在2.6核心中，也如同2.4核心般，會把上一輪行程尚未使用完畢的Time-Slice的一半加入到新一輪取得的Time-Slice中，因此在2.6的核心中也是會發生Time-Slice變長的問題，但2.6核心提出的解決之道就是透過一個TIMESLICE_GRANULARITY值表示系統可接受行程在一個排程區間中最大執行時間長度，若該行程所具備的Time-Slice長度超過TIMESLICE_GRANULARITY ，並且目前在該排程區間內已執行了TIMESLICE_GRANULARITY 長度了，就會強制切換該行程，使其在下一輪排程中排入，並讓其它行程可以藉此取得處理器執行的機會(此行為實做在scheduler_tick函式裡)。
|
//Linux kernel 2.6 // Process will be divided into multiple small time-slice to run on processor, and let other processes
|
由於目前核心支援Preemptive的能力，因此如何妥善的保護每一個核心行程或是相關核心函式重要的變數資料，也是在系統程式設計與安全性的考量之一，在目前的2.6核心下若使用者透過spin_lock或呼叫local_irq_disable相關函式將中斷取消，核心Preempt的能力將會被取消，但除此之外核心還支援相關更有彈性的作法，如以下函式
|
preempt_enable() |
Decrement the preempt counter |
|
preempt_disable() |
Increment the preempt counter |
|
preempt_enable_no_resched() |
Decrement, but do not immediately preempt |
|
preempt_check_resched() |
If needed, reschedule |
|
preempt_count() |
Return the preempt counter |
使用者在撰寫驅動程式或是核心函式時，如果所存取的資料結構要避免被Preempt後其它核心程式所誤改，導致其它錯誤，就可以透過如下方式，呼叫preempt_disable函式增加preempt counter值，只要preempt counter大於0，核心的Preempt排程能力就會被禁止。
|
preempt_disable(); ….….. ….….. ….….. preempt_enable(); |
四，Real-Time 程式設計支援
目前 2.4/2.6核心已支援以下的函式，可以用來提供對時間要求比較高的程式設計需求，其中每個函式之後對應的編號指的就是其所對應的Linux核心的System Call編號。
|
//User could check arch/i386/kernel/entry.S .long sys_nice /* 34 */ .long sys_getpriority /* 96 */ .long sys_setpriority /* 97 */ .long sys_sched_setparam /* 154 */ .long sys_sched_getparam /* 155 */ .long sys_sched_setscheduler /* 156 */ .long sys_sched_getscheduler /* 157 */ .long sys_sched_yield /* 158 */ .long sys_sched_get_priority_max /* 159 */ .long sys_sched_get_priority_min /* 160 */ .long sys_sched_rr_get_interval /* 161 */
|
而每個行程可供選擇的Scheduling Policy 主要包括SCHED_NORMAL(=0)、SCHED_FIFO(=1)與SCHED_RR (=2)，其中行程產生時預設的Scheduling Policy就是SCHED_NORMAL(Real-Time優先權為0)，除非該行程的父行程在產生子行程前有作其它Real-Time或是Nice值的調整。當使用者呼叫函式Nice與setpriority 所調整的就是Nice值。若目前使用者程式希望程式可以優先被執行，並在在執行完畢以前即使被分配到的Time-Slice用盡，也不放棄處理器資源，此時就可以把行程Scheduling Policy設定為SCHED_FIFO，在此設定下除非該行程主動呼叫sched_yield、呼叫其它sleep相關函式或終止執行，否則該行程是不會被置換下來的。相對的，若使用者希望行程可以優先被執行，並且該行程依據自己的Nice值分配到的Time-Slice執行即可，並無持續佔住處理器資源之需求，就可以把行程Scheduling Policy設定為SCHED_RR，如此則會依據Real-Time的優先權等級排程，並執行完透過Nice值分配到的Time-Slice後，即被置換將處理器資源給予其它行程執行。
接下來筆者使用以上的函式，舉幾個實際的例子以供參考
(1) 透過設定Nice值調整行程優先權
|
#include <stdio.h> #include <sys/resource.h> /*Nice value is from -20 to 19*/ int main() int pid=getpid(); /*Initial nice value is 0*/ printf("Current pid:%xh Pri:%ld\n",pid,getpriority(PRIO_PROCESS,pid)); setpriority(PRIO_PROCESS,pid,-20); printf("Current pid:%xh Pri:%ld\n",pid,getpriority(PRIO_PROCESS,pid)); printf("nice:%ld\n",nice(5)); printf("Current pid:%xh Pri:%ld\n",pid,getpriority(PRIO_PROCESS,pid)); ….. …… } |
(2) 設定行程採用FIFO排程與調整Real-Time優先權為50
|
#include <stdio.h> #include <sys/resource.h> #include <sched.h> /*RT Priority is from 1 to 99*/ int main() struct sched_param schedparam; int pid=getpid(); printf("pid:%xh sched_getscheduler:%ld\n",pid,sched_getscheduler(pid)); printf("sched_get_priority_max:%ld sched_get_priority_min:%ld\n",sched_get_priority_max(SCHED_FIFO),sched_get_priority_min(SCHED_FIFO)); if (sched_getparam(pid, &schedparam) < 0) { printf("Scheduler getparam failed…\n"); return 0×00; } schedparam.sched_priority=50; if (sched_setscheduler(pid,SCHED_FIFO ,&schedparam)<0) { printf("Scheduler set failed…\n"); return 0×00; } if (sched_getparam(pid, &schedparam) < 0) { printf("Scheduler getparam failed…\n"); return 0×00; } printf("schedparam.sched_priority:%ld\n",schedparam.sched_priority); printf("Current pid:%xh Pri:%ld\n",pid,getpriority(PRIO_PROCESS,pid)); . ….. …… } |
(3) 設定行程採用RR(round-robin) 排程與調整Real-Time優先權為70
|
#include <stdio.h> #include <time.h> #include <sys/resource.h> #include <sched.h> /*RT Priority is from 1 to 99*/ int main() struct sched_param schedparam; struct timespec tp; int pid=getpid(); printf("sched_get_priority_max:%ld sched_get_priority_min:%ld\n",sched_get_priority_max(SCHED_RR),sched_get_priority_min(SCHED_RR)); schedparam.sched_priority=70; if (sched_setscheduler(pid,SCHED_RR ,&schedparam)<0) { printf("Scheduler set failed…\n"); return 0×00; } sched_rr_get_interval(pid,&tp); printf("tv_sec: %ld tv_nsec:%ld\n",tp.tv_sec,tp.tv_nsec); nice(-3); sched_rr_get_interval(pid,&tp); printf("tv_sec: %ld tv_nsec:%ld\n",tp.tv_sec,tp.tv_nsec); ….. …… } |
(4) 產生User-Mode Thread，並調整其優先權
|
#include <stdio.h> #include <time.h> #include <sys/resource.h> #include <sched.h> #include <pthread.h> #include <sys/types.h> #include <linux/unistd.h> _syscall0(pid_t,gettid) eSystem call number #224 pthread_t dthread;
void *test_thread(void *num) { if((int)num==1) |
同樣的，包括kernel_thread一樣也可以調整Real-Time與Nice優先權的值，這些端賴使用者在設計系統時的需求而定。
除了2.4/2.6核心所共同支援的函式外，2.6 的核心又支援了以下兩個函式，用來在多處理器環境下提供使用者設定行程所允許執行的處理器
.long sys_sched_setaffinity /* 241 */
.long sys_sched_getaffinity /* 242 */
其中sys_sched_setaffinity 最後會透過System Call呼叫核心函式函式 sched_setaffinity (存在於kernel/sched.c)，設定指定行程的task_struct->cpus_allowed，藉由這樣的功能可以在多處理器環境下提供使用者更有彈性的應用程式與處理器資源分配。
四， 結語
對於國內大多數業者來說，許多產品早已導入2.4核心的技術了，隨著2.6核心的推出，是否導入2.6核心也成為許多產品研發人員與主管所關切的課題，從筆者的角度來說，如果目前使用的平台所執行的應用程式數量並不多，例如: 精簡型嵌入式的閘道器或執行單一功能的掌上型裝置，對於2.6核心所提供的排程與更複雜架構的支援(例如:NUMA或是High Precision Event Timer)，使用需求並不高，這類的產品切換到2.6的急迫性相對也較低。
然而或是針對，需要核心內建IPSec、多樣化的應用程式同時運作或是大型網頁伺服器而言，2.6核心內建的安全性模組與高效能的核心排程機制，都將遠勝過2.4核心在同樣環境下的效能與對於安全性支援的完整。
整體而言，是否導入2.6核心與其急迫性，端賴產品所需面對的市場與具備的功能作一考量，2.6核心的傑出成就使得許多Linux的開發者得以架構在不同以往的高效能作業系統基礎上，進一步的透過它來實現更多的應用。
最後，筆者在撰寫本文時，有幸拜讀了中國作家楊沙洲的文章，其在相關領域的知識深度非常值得一讀，並使筆者在整理核心程式碼時，能有一快速的知識背景建立，在文末參考資料中，也將其列入。
若各位對於我的文章有任何問題，都歡迎隨時與筆者聯繫。
我的E-Mail: hlchou@mail2000.com.tw
五， 參考資料
1，Linux Kernel 2.4.19與2.6.10 核心程式碼
2，Linux Kernel Development by Robert Love
3，
Linux 2.6 調度系統分析，楊沙洲，IBM Developer-works ，http://www-128.ibm.com/developerworks/cn/linux/kernel/l-kn26sch/index.html
4，Linux 2.4 調度系統分析，楊沙洲，IBM Developer-works ，http://www-128.ibm.com/developerworks/cn/linux/kernel/l-k24sch/index.html
