周期性調度器由scheduler_tick()函數實現，在每個時鐘中斷中都會調用該函數來更新一些統計量，並且會激活當前進程所屬調度類的周期性處理接口，代碼流程如下所示：
具體來說，scheduler_tick()做了以下工作：
1）更新就緒隊列的實際時鐘時間，不是虛擬時鐘時間。
2）更新就緒隊列權重數組cpu_load中的權重值
3）調用當前CPU上正在執行的進程所屬調度類的task_tick接口，更新調度類相關的統計信息，並檢查是否需要重新調度
4）如果是多處理器系統，檢查當前CPU是否處於IDLE狀態，並調用trigger_load_balance()來檢查是否需要對CPU之間的負載進行均衡，如果需要，則觸發SCHEDULE_SOFTIRQ軟中斷來遷移進程。
下面來看一看內核中是如何來完成這些操作的。
1.就緒隊列時鐘的更新
就緒隊列的時鐘由update_rq_clock()函數來更新，如果在編譯內核的時候啟用了CONFIG_HAVE_UNSTABLE_SCHED_CLOCK選項（CentOS的內核是默認開啟的），sched_clock_stable變量的值為1，這種情況下會調用sched_clock()函數來獲取當前的CPU時間。sched_clock()函數中會調用rdstc指令來讀取CPU的周期數，然後調用__cycles_2_ns()將周期數轉換為納秒。rdstc指令在多處理器下會有問題，關於這個問題的描述和解決辦法，參見 《多核時代不宜再用 x86 的 RDTSC 指令測試指令周期和時間》 ，較新的內核中已使用同步算法來fix這個問題。
2.權重數組的更新
就緒隊列中的cpu_load數組用來跟蹤此前的CPU負荷狀態，在sched_init()中初始化為0，在CPU間遷移進程時會用到這個數組中記錄的權重。cpu_load數組由update_cpu_load()函數更新，在每個tick周期裏都會調用該函數，代碼如下所示：
static void update_cpu_load( struct rq * this_rq)
{
unsigned long this_load = this_rq - > load.weight;
int i, scale;
this_rq - > nr_load_updates ++ ;
/* Update our load: */
for (i = 0 , scale = 1 ; i < CPU_LOAD_IDX_MAX; i ++ , scale += scale) {
unsigned long old_load, new_load;
/* scale is effectively 1 << i now, and >> i divides by scale */
old_load = this_rq - > cpu_load[i];
new_load = this_load;
/*
* Round up the averaging division if load is increasing. This
* prevents us from getting stuck on 9 if the load is 10, for
* example.
*/
if (new_load > old_load)
new_load += scale - 1 ;
this_rq - > cpu_load[i] = (old_load * (scale - 1 ) + new_load) >> i;
}
if (time_after_eq(jiffies, this_rq - > calc_load_update)) {
this_rq - > calc_load_update += LOAD_FREQ;
calc_load_account_active(this_rq);
}
}
在向就緒隊列添加調度實體時，都會將調度實體的權重值添加到就緒隊列的當前負荷的統計成員load中。在這裏，this_load保存了當前就緒隊列中的權重負荷。在更新cpu_load數組前要累加nr_load_updates成員，該成員記錄了更新cpu_load數組的次數，只在輸出/proc/sched_debug文件時使用，用於調試調度系統。
在for循環中，根據老的權重值和當前的權重值來進行更新。為了便於理解，我們可以進行下面的轉換：
this_rq - > cpu_load[i] = (old_load * (scale - 1 ) + new_load) >> i
= (old_load * ( 2 ^ i - 1 ) + new_load) / ( 2 ^ i)
= old_load * ( 1 - 1 / ( 2 ^ i)) + new_load / ( 2 ^ i)
= old_load + (new_load - old_load) / ( 2 ^ i)
通過轉換，我們可以清晰地看到cpu_load數組中的元素是如何更新的。如果i等於0，則2^i的值為1，所以this_rq->cpu_load[0]保存的就是更新時當前就緒隊列的權重值。如果當前隊列的權重值是增加的，會將new_load(保存的就是當前的權重值)加上(scale-1)，向上取整。
update_cpu_load()中除了更新cpu_load數組的內容後，還會檢查是否要更新系統平均負載的統計信息，這些信息每隔5秒鐘才更新一次，主要是統計在系統中處於active狀態的進程的個數，包括進程狀態是TASK_RUNNING和TASK_UNINTERRUPTIBLE的進程。系統的平均負載可以通過top或w命令查看。
3.CFS的周期性處理
CFS調度系統的調度類實例由全局變量fair_sched_class表示，設置的周期性處理接口是task_tick_fair()。在2.6.24中引入了組調度的概念，所以在task_tick_fair()中通過for_each_sched_entity宏來遍歷處理當前進程所在的調度層級。這裏為了簡化，我們假設當前進程的parent為NULL，即當前進程處在就緒隊列中的紅黑樹中。對當前進程的周期性處理主要由entity_tick()函數來完成，主要代碼流程如下所示：
static void
entity_tick( struct cfs_rq * cfs_rq, struct sched_entity * curr, int queued)
{
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
......
if (cfs_rq - > nr_running > 1 || ! sched_feat(WAKEUP_PREEMPT))
check_preempt_tick(cfs_rq, curr);
}
update_curr()根據現在的實際時鐘時間和進程的權重計算本次運行的虛擬時鐘時間，並更新進程和CFS就緒隊列相關的統計信息。update_curr()使用CPU就緒隊列的實際時鐘時間減去當前進程的開始運行時間(由sched_entity結構的exec_start成員描述），得到當前進程實際的運行時間，然後調用__update_curr()來將實際的運行時間轉換為虛擬時鐘時間，並且加到當前進程總的運行的虛擬時鐘時間(由sched_entity的sum_exec_runtime成員描述)。實際時鐘時間和虛擬時鐘時間的轉換公式為：
在update_curr()中更新當前進程的虛擬運行時間後，需要重新計算CFS就緒隊列中最小的虛擬運行時間。假設cfs_rq(結構類型為cfs_rq)為當前CPU就緒隊列中的CFS就緒隊列，最小的虛擬運行時間在CFS就緒隊列當前的最小運行時間(即cfs_rq->min_vruntime)、正在執行的進程的虛擬運行時間(即cfs_rq->curr->vruntime,更新後的值)和CFS就緒隊列中最左邊節點(管理調度實體的紅黑樹中最左邊的節點)的虛擬運行時間(cfs_rq->leftmost->vruntime)這三個值之間選擇一個最小值。如果選出來的值大於當前CFS就緒隊列的最小虛擬運行時間，則使用選出來的值來作為新的最小虛擬運行時間，並設置到cfs_rq-> min_vruntime上，否則維持原來的值不變。通過這樣的策略，可以保證CFS就緒隊列中的最小虛擬運行時間總是單調遞增的，防止時鐘倒流。由於最小虛擬運行時間總是單調遞增的，所以就緒隊列中最左邊節點的運行時間有可能小於cfs_rq->min_vruntime。
完成更新操作後，檢查CFS就緒隊列中可運行進程的數目是否大於1，如果大於1，則調用check_preempt_tick()檢查是否要重新調度正在執行的進程，檢查主要分以下幾個步驟：
1）調用sched_slice()計算當前進程在調度延遲內期望的運行時間。如果系統中可運行進程的數量小於sched_nr_latency（其值為 sysctl_sched_latency/ sysctl_sched_min_granularity ），調度延遲由系統參數sysctl_sched_latency的值確定；如果可運行進程的數量大於sched_nr_latency，調度延遲的值為（ sysctl_sched_latency * (nr_running / sched_nr_latency)），其中nr_running為CFS就緒隊列中可運行進程的數量。而當前進程在調度延遲中分得的時間（實際時鐘時間）根據下面的公式來計算(period為調度延遲，weight為當前進程的權重，cfs_rq->load.weight為CFS就緒隊列的權重)：
2）如果當前進程本次已經執行的時間（實際時鐘時間）超過期望的運行時間，說明當前進程運行的時間已經足夠了，這種情況下要重新調度當前進程，並調用clear_buddies()確保當前進程不在CFS就緒隊列中的next或last中，避免當前進程在下次選擇執行進程時又被優先調度到。
3）如果當前進程本次已經執行的時間小於進程的最小運行時間（保存在sysctl_sched_min_granularity中），也不能重新調度，避免進程切換的太過頻繁。
4）如果就緒隊列中可運行進程的數量超過1，比較當前進程和就緒隊列中最左邊進程的運行時間來確定是否要重新調度。如果當前進程的虛擬運行時間減去就緒隊列中最左邊進程的虛擬運行時間的差值大於當前進程的期望運行時間，則重新調度當前進程。
4.負載均衡
多處理器系統中，內核必須要保證不同CPU間的負載要均衡，避免某些CPU的負載已經很高了，而某些CPU卻很空閑，充分利用CPU資源。但是，遷移進程會導致CPU高速緩存失效，嚴重影響性能，所以在創建進程時，內核已經開始在CPU間負載均衡。
在SMP系統上，周期性調度器函數scheduler_tick()完成前面的任務後，會調用 trigger_load_balance()來檢查是否要發起CPU間的負載均衡。這裏我們不考慮啟用動態時鐘（即設置了CONFIG_NO_HZ選項）下的處理。如果當前的時間已經超過就緒隊列中保存的下次均衡的時間，並且當前CPU在某個調度域內，則觸發SCHED_SOFTIRQ軟中斷，適當的時候內核會調用run_rebalance_domains()函數在CPU間進行負載均衡。
調度域是一個CPU的集合，是負載均衡的單位，進程的遷移是在調度域內各CPU間進行，所以只有在當前CPU屬於某個調度域的時候才發起進程遷移。通過調度域可以將鄰近或共享高速緩存的CPU群集起來，優先選擇在這些CPU之間遷移進程，這樣可以降低遷移進程導致的性能損失。在普通的SMP系統上，所有的處理器都包含在一個調度域中。
留言列表
