深入Linux內核架構——行程管理和調度（二）

一、調度器的實作

調度器的任務是在程式之間共享CPU時間，創造并行執行的錯覺，該任務可分為調度策略和背景關系切換兩個不同部分，

1、概觀
暫時不考慮實時行程，只考慮CFS調度器，經典的調度器對系統中的行程分別計算時間片，使行程運行直至時間片用盡，所有行程的所有時間片用完時，需要重新計算，相比之下，CFS只考慮行程等待時間，即行程在就緒佇列（run_queue）中已等待的時間，對CPU時間需求最嚴格的行程被調度執行，每次調度器會挑選具有最高等待時間的行程提供CPU，如此行程的不公平等待不會被積累，而會均勻分布到系統所有行程，

下圖是CFS調度器的作業原理，所有可運行行程都按等待時間在一個紅黑樹中排序，等待CPU時間最長的行程是最左側的項，調度器下一次會考慮該行程，等待時間稍短的行程在該樹上從左至右排序，（調度器時間復雜度為O(logn)）

除了紅黑樹外，就緒佇列還裝備了虛擬時鐘，該時鐘的時間流逝速度慢于實際的時鐘，精確的速度依賴于當前等待調度器挑選的行程數目（如4個行程，那么虛擬時鐘將以實際時鐘的四分之一的速度運行，如果以完全公平的方式分享計算能力，那么該時鐘是判斷等待行程將獲得多少CPU時間的基準），

就緒佇列的虛擬時間由fair_clock給出，行程的等待時間保存在wait_runtime中，為排序紅黑樹上的行程，內核使用差值fair_clock - wait_runtime的絕對值，fair_clock是完全公平調度的情況下行程將會得到的CPU時間的度量，而wait_runtime直接度量了實際系統的不足造成的不公平，

在行程允許運行時，將從wait_runtime減去它已經運行的時間，這樣，在按時間排序的樹中它會向右移動到某一點，另一個行程將成為最左邊，下一次會被調度器選擇，

當前該調度策略還受到的影響因素：

• 行程的不同優先級（即，nice值）必須考慮，更重要的行程必須比次要行程更多的CPU時間份額，
• 行程不能切換得太頻繁，因為背景關系切換，即從一個行程改變到另一個，是有一定開銷的，另一方面，兩次相鄰的任務切換之間，時間也不能太長，否則會累積比較大的不公平值，

2、資料結構
調度器使用一系列資料結構排序和管理系統中的行程，調度器的作業方式與這些結構的設計密切相關，幾個組件在許多方面彼此互動，如圖2所示，
激活調度器方法：

• 直接的，行程打算睡眠或其他因素放棄cpu，（通用調度器，generic scheduler，本質上是分配器）
• 周期性的，以固定頻率運行，不時檢查是否有必要進行行程切換，（核心調度器，core scheduler）

調度類：用于判斷接下來運行哪個行程，內核支持不同的調度策略（完全公平調度、實時調度、在無事可做時調度空閑行程），調度類使得能夠以模塊化方法實作這些策略，即一個類的代碼不需要與其他類的代碼互動，

行程切換：在選中將執行的程式之后，要執行底層的任務切換，（需要與CPU緊密互動）

注：每個行程都剛好屬于某一調度類，各個調度類負責管理所屬的行程，通用調度器自身完全不涉及行程管理，其作業都委托給調度器類，

（1）task_struct成員

各行程的task_struct有幾個成員與調度相關：

struct task_struct {
...
    int prio, static_prio, normal_prio; // prio和normal_prio表示動態優先級，static_prio表示行程的靜態優先級，靜態優先級是行程啟動時分配的優先級，它可以用nice和sched_setscheduler系統呼叫修改，否則在行程運行期間會一直保持恒定，normal_priority表示基于行程的靜態優先級和調度策略計算出的優先級，調度器考慮的優先級則保存在prio，由于在某些情況下內核需要暫時提高行程的優先級，因此需要第3個成員來表示，
    
    unsigned int rt_priority; //表示實時行程的優先級，該值不會代替先前討論的那些值，最低的實時優先級為0，最高的是99，值越大，優先級越高，這里使用的慣例不同于nice值，
    
    struct list_head run_list; //是回圈實時調度器所需要的，但不用于完全公平調度器，run_list是一個表頭，用于維護包含各行程的一個運行表
    
    const struct sched_class *sched_class; //表示該行程所屬的調度器類
    
    struct sched_entity se; //由于調度器設計為處理可調度的物體，在調度器看來各個行程必須也像是這樣的物體，因此se在task_struct中內嵌了一個sched_entity實體，調度器可據此操作各個task struct，
    
    unsigned int policy; //保存了對該行程應用的調度策略，（SCHED_NORMAL用于普通行程，SCHED_BATCH用于非互動、CPU使用密集的批處理行程，SCHED_IDLE是空閑行程，SCHED_RR和SCHED_FIFO用于實作軟實時行程，）
    
    cpumask_t cpus_allowed; //是一個位域，在多處理器系統上用來限制行程可以在哪些CPU上運行
    
    unsigned int time_slice; // 是回圈實時調度器所需要的，但不用于完全公平調度器，time_slice則指定行程可使用CPU的剩余時間段
...
}

（2）調度器類

調度器類由特定資料結構中匯集的幾個函式指標表示，全域調度器請求的各個操作都可以由一個指標表示，這使得無需了解不同調度器類的內部作業原理，即可創建通用調度器，

對各個調度類，都必須提供struct sched_class的一個實體，調度類之間的層次結構是平坦的：實時行程最重要，在完全公平行程之前處理；而完全公平行程則優先于空閑行程；空閑行程只有CPU無事可做時才處于活動狀態，next成員將不同調度類的sched_class實體，按上述順序連接起來，要注意這個層次結構在編譯時已經建立，

用戶層應用程式無法直接與調度類互動，它們只知道上文定義的常量SCHED_…，在這些常量和可用的調度類之間提供適當的映射，這是內核的作業，SCHED_NORMAL、SCHED_BATCH和SCHED_IDLE映射到fair_sched_class，而SCHED_RR和SCHED_FIFO與rt_sched_class關聯，fair_sched_class和rt_sched_class都是struct sched_class的實體，分別表示完全公平調度器和實時調度器，

（3）就緒佇列

就緒佇列：核心調度器用于管理活動行程的主要資料結構，各個CPU都有自身的就緒佇列，各個活動行程只出現在一個就緒佇列中，行程不是由就緒佇列的成員直接管理的，而是有調度類管理，就緒佇列中嵌入了特定于調度器類的子就緒佇列，

就緒佇列核心成員及解釋：

struct rq {
    unsigned long nr_running; //指定了佇列上可運行行程的數目，不考慮其優先級或調度類
    
#define CPU_LOAD_IDX_MAX 5

    unsigned long cpu_load[CPU_LOAD_IDX_MAX]; //用于跟蹤此前的負荷狀態
...
    struct load_weight load; //提供了就緒佇列當前負荷的度量
    
    struct cfs_rq cfs;  //嵌入的子就緒佇列，用于完全公平調度器
    
    struct rt_rq rt;  //嵌入的子就緒佇列，用于和實時調度器
    
    struct task_struct *curr, *idle; //指向idle行程的task_struct實體，該行程亦稱為idle執行緒
    
    u64 clock; //用于實作就緒佇列自身的時鐘，每次呼叫周期性調度器時，都會更新clock的值，
...
};

系統的所有就緒佇列都在runqueues陣列中，該陣列的每個元素分別對應于系統中的一個CPU，在單處理器系統中，由于只需要一個就緒佇列，陣列只有一個元素，

（4）調度物體

由于調度器可以操作比行程更一般的物體，因此需要一個適當的資料結構來描述此類物體，其定義為：

struct sched_entity {

    struct load_weight load;  //指定了權重，用于負載均衡
    
    struct rb_node run_node; //是標準的樹結點，使得物體可以在紅黑樹上排序
    
    unsigned int on_rq; //表示該物體當前是否在就緒佇列上接受調度
    
    u64 exec_start; //新行程加入就緒佇列時，或者周期性調度器中，每次呼叫時，會計算當前時間和exec_start之間的差值，exec_start則更新到當前時間，差值則被加到sum_exec_runtime，
    
    u64 sum_exec_runtime; //用于記錄消耗的CPU時間
    
    u64 vruntime; //統計行程執行期間虛擬時鐘上流逝的時間數量
    
    u64 prev_sum_exec_runtime; //行程被撤銷CPU時，保存當前sum_exec_runtime
...
}

3、處理優先級

（1）優先級的內核表示

在用戶空間可以通過nice命令設定行程的靜態優先級，這在內部會呼叫nice系統呼叫，行程的nice值在-20和+19之間（包含），值越低，表明優先級越高，

內核使用一個簡單些的數值范圍，從0到139（包含），用來表示內部優先級，同樣是值越低，優先級越高，從0到99的范圍專供實時行程使用，nice值[-20, +19]映射到范圍100到139，

（2）計算優先級

行程的優先級計算需要考慮動態優先級(prio)，普通優先級(normal_prio)和靜態優先級(static_prio)，呼叫相關函式計算結果，（完成設定到優先級內核表示的轉換）

圖3綜述了針對不同型別行程的計算結果，

在行程分支出子行程時，子行程的靜態優先級繼承自父行程，子行程的動態優先級，即task_struct->prio，則設定為父行程的普通優先級，這確保了實時互斥量引起的優先級提高不會傳遞到子行程，

（3）計算負荷權重

行程的重要性由優先級和保存在task_struct->se.load的負荷權重同時決定，行程每降低一個nice值，則多獲得10%的CPU時間，每升高一個nice值，則放棄10%的CPU時間，

4、核心調度器

調度器的實作基于兩個函式：周期性調度器函式和主調度器函式，

（1）周期性調度器

在scheduler_tick中實作，如果系統正在活動中，內核會按照頻率HZ自動呼叫該函式，
沒行程等待時，供電不足情況下，可以關閉周期性調度器以減少電能消耗，
主要任務是管理內核中與系統和每個行程的調度相關的統計量和激活負責當前行程的調度類的周期性調度方法，

void scheduler_tick(void)
{
    int cpu = smp_processor_id();
    
    struct rq *rq = cpu_rq(cpu);
    
    struct task_struct *curr = rq->curr;
...

    __update_rq_clock(rq);  //更新struct rq當前實體的時鐘時間戳
    
    update_cpu_load(rq);   //更新rq->cup_load[]陣列
    
    if (curr != rq->idle)
    
    curr->sched_class->task_tick(rq, curr);
}

如果當前行程應該被重新調度，那么調度器類方法會在task_struct中設定TIF_NEED_RESCHED標志，以表示該請求，而內核會在接下來的適當時機完成該請求，

（2）主調度器

將當前cpu分配給另一個行程需要呼叫主調度器函式(schedule)，從該系統呼叫回傳后也要檢查當前行程是否設定了重調度標志TIF_NEED_RESCHEDULE，如果有，內核會呼叫schedule，

__sched前綴的用處：有該前綴的函式，都是可能呼叫schedule的函式，包括schedule自身，該前綴目的在于將相關代碼的函式編譯后，放到目標檔案的特定段中，.sched.text中，該資訊使內核在現實堆疊轉儲或類似資訊時，忽略所有與調度有關的呼叫，由于調度器函式呼叫不是普通代碼流程的部分，因此這種情況下是無意義的，

asmlinkage void __sched schedule( void );該函式的程序：

首先確定當前就緒佇列，并在prev中保存一個指向（當前）活動行程的task_struct的指標，
更新就緒佇列的時鐘，清除當前行程task_struct的重調度標志TIF_NEED_RESCHED，
判斷當前行程是否在可中斷睡眠狀態，而且現在接收到信號，那么它將再次提升為可運行，否則，用deactivate_task講行程停止，
用put_prev_task通知調度類，當前行程要被另一行程代替，pick_next_task，選擇下一個要執行的行程，
只有1個行程，是不要切換的，還讓它留在cpu，如果已經選擇了一個新行程，就用context_switch進行背景關系切換，
當前行程，被重新調度回來時，檢測是否要重新調度，如果要，就又重復前面(1)至(5)的步驟了，
（3）與fork的互動

用fork或其變體新建行程時，調度器有機會用sched_fork函式掛鉤到該行程，

單處理器中，sched_fork執行如下:

• 初始化新行程與調度相關的欄位，
• 建立資料結構（相當簡單直接），
• 確定行程的動態優先級，

通過使用父行程的普通優先級作為子行程的動態優先級，內核確保父行程優先級的臨時提高不會被子行程繼承，在用wake_up_new_task喚醒行程時，內核呼叫調度類的task_new將新行程加入相應類的就緒佇列中，

（4）背景關系切換

內核選擇新行程之后，必須處理與多任務相關的技術細節，這些細節總稱為背景關系切換（context switching），

• context_switch是個分配器，它會呼叫所需的特定于體系結構的方法，主要進行如下操作：
• prepare_task_switch，執行特定于體系結構的代碼，為切換做準備，
• switch_mm更換task_struct->mm描述的記憶體管理背景關系，
• switch_to切換處理器暫存器和內核堆疊（虛擬地址空間的用戶部分在第一步已經變更，其中也包括了用戶狀態下的堆疊，因此用戶堆疊就不需要顯式變更了），
• 切換前，用戶空間行程的暫存器進入和心態時保存在內核堆疊上，在背景關系切換時，內核堆疊的值自動回復暫存器資料，再回傳用戶空間，

內核執行緒沒有自身的用戶空間記憶體背景關系，可能在某個隨機行程地址空間的上部執行，其task_struct->mm為NULL，從當前行程“借來”的地址空間記錄在active_mm中，

此外，由于背景關系切換的速度對系統性能的影響舉足輕重，所以內核使用了一種技巧來減少所需的CPU時間，浮點暫存器（及其他內核未使用的擴充暫存器，例如IA-32平臺上的SSE2暫存器）除非有應用程式實際使用，否則不會保存，此外，除非有應用程式需要，否則這些暫存器也不會恢復，這稱之為惰性FPU技術，由于使用了匯編語言代碼，因此其實作依平臺而有所不同，但基本原理總是同樣的，

小編推薦自己的Linux、C/C++技術交流群:【960994558】整理了一些個人覺得比較好的學習書籍、視頻資料共享在里面（包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK等等.），有需要的可以自行添加哦！~

二、完全公平調度類

1、資料結構
CFS的就緒佇列cfs_rq:

struct cfs_rq {
    struct load_weight load;        //維護了所有這些行程的累積負荷值
    unsigned long nr_running;    //計算了佇列上可運行行程的數目
    u64 min_vruntime;        //跟蹤記錄佇列上所有行程的最小虛擬運行時間
    struct rb_root tasks_timeline;        //用于在按時間排序的紅黑樹中管理所有行程
    struct rb_node *rb_leftmost;        //總是設定為指向樹最左邊的結點，即最需要被調度的行程
    struct sched_entity *curr;    //指向當前執行行程的可調度物體
}

2、CFS操作
（1）虛擬時鐘

完全公平調度演算法依賴于虛擬時鐘，用以度量等待行程在完全公平系統中所能得到的CPU時間，資料結構中，可以根據現存的實際時鐘與每個行程相關的負荷權重推算出來，所有與虛擬時鐘有關的計算都在update_curr中執行，該函式在系統中各個不同地方呼叫，包括周期性調度器之內，

首先，該函式確定就緒佇列的當前執行行程，并獲取主調度器就緒佇列的實際時鐘值（每個調度周期都會更新），如果就緒佇列上當前沒有行程正在執行，則無事可做，否則，內核會計算當前和上一次更新負荷統計量時兩次的時間差，并將其余的作業委托給__update_curr，

然后，__update_curr需要更新當前行程在CPU上執行花費的物理時間和虛擬時間，物理時間的更新只要將時間差加到先前統計的時間即可；對于虛擬時間，對于運行在nice級別0的行程來說，定義虛擬時間和物理時間是相等的，nice值不為0時，必須根據行程的負荷權重重新衡定時間，

最后，內核需要設定min_vruntime（min_vruntime是單調遞增的），

CFS調度器真正關鍵點：紅黑樹根據鍵值進行排序（se->vruntime -cfs_rq->min_vruntime），鍵值較小的結點，排序位置就更靠左（被更快調度），由此，內核實作了以下兩種對立機制：

• 在行程運行時，其vruntime穩定地增加，它在紅黑樹中總是向右移動的，
• 如果行程進入睡眠，則其vruntime保持不變（行程再被喚醒后，在紅黑樹的位置會更靠左），

（2）延遲跟蹤

良好的調度延遲是 保證每個可運行的行程都應該至少運行一次的某個時間間隔（它在sysctl_sched_latency給出），一個延遲周期中處理的最大活動數目為sched_nr_latency，超出該上限，則延遲周期也成比例線性擴展，

通過考慮各個行程的相對權重，將一個延遲周期的時間在活動行程之間進行分配，

3、佇列操作
enqueue_task_fair和dequeue_task_fair分別用來增刪就緒佇列的成員，圖5為enqueue_task_fair代碼流程圖，

如果通過struct sched_entity的on_rq成員判斷行程已經在就緒佇列上，則無事可做，否則，具體的作業委托給enqueue_entity，

進入enqueue_entity后，首先用updater_curr更新統計量，然后若行程此前在睡眠，那么在place_entity中首先會調整行程的虛擬運行時間；如果行程最近在運行，其虛擬運行時間仍然有效，那么（除非它當前在執行中）它可以直接用__enqueue_entity加入紅黑樹中，

4、選擇下一個行程
選擇下一個將要運行的行程由pick_next_task_fair執行，pick_next_task_fair的代碼流程圖如圖6所示，

如果nr_running計數器為0，即當前佇列上沒有可運行行程，則無事可做，函式可以立即回傳，否則將具體作業委托給pick_next_entity，

如果樹中最左邊的行程可用，可以使用輔助函式first_fair立即確定，然后用__pick_next_entity從紅黑樹中提取出sched_entity實體，

完成了選擇作業之后，通過set_next_entity函式將該行程標記為運行行程，當前執行行程不保存在就緒佇列上，因此使用__dequeue_entity將其從樹中移除，如果當前行程是最左邊的結點，則將leftmost指標設定到下一個最左邊的行程，

5、處理周期性調度器
在處理周期調度時，差值sum_exec_runtime - prev_sum_exec_runtime（表示行程在CPU上執行所花時間）很重要，這個差值形式上由函式task_tick_fair負責，但實際作業由entity_tick完成，

首先，使用update_curr更新統計量，

然后判斷nr_running計數器表明佇列上可運行的行程數，如果少于兩個，則無事可做；否則由由check_preempt_tick作出決策（確保沒有哪個行程能夠比延遲周期中確定的份額運行得更長），如果行程運行時間比期望的時間間隔長，那么通過resched_task發出重調度請求，這會在task_struct中設定TIF_NEED_RESCHED標志，核心調度器會在下一個適當時機發起重調度，

6、喚醒搶占
當在try_to_wake_up和wake_up_new_task中喚醒行程時，內核使用check_preempt_curr看看是否新行程可以搶占當前運行的行程（該程序不涉及核心調度器），

新喚醒的行程不必一定由完全公平調度器處理，如果新行程是一個實時行程，則會立即請求重調度，因為實時行程總是會搶占CFS行程，

當運行行程被新行程搶占時，內核確保被搶占者至少已經運行了某一最小時間限額（sysctl_sched_wakeup_granularity），如果新行程的虛擬運行時間，加上最小時間限額，仍然小于當前執行行程的虛擬運行時間（由其調度物體se表示），則請求重調度，

7、處理新行程
CFS在創建新行程時呼叫的掛鉤函式：task_new_fair，該函式的行為可用sysctl_sched_child_runs_first控制，用于判斷新建子行程是否需要在父行程之前運行，如果父行程的虛擬運行時間（由curr表示）小于子行程的虛擬運行時間，則意味著父行程將在子行程之前調度運行，如果子行程應該在父行程之前運行，則二者的虛擬運算時間需要換過來，然后子行程按常規加入就緒佇列，并請求重調度，

三、實時調度類

1、性質
按照POSIX標準的要求，除了“普通”行程之外，Linux還支持兩種實時調度類，調度器結構使得實時行程可以平滑地集成到內核中，而無需修改核心調度器，

實時行程與普通行程有一個根本的不同之處：如果系統中有一個實時行程且可運行，那么調度器總是會選中它運行，除非有另一個優先級更高的實時行程，

現有的兩種實時類：

• 回圈行程（SCHED_RR）有時間片，其值在行程運行時會減少，就像是普通行程，在所有的時間段都到期后，則該值重置為初始值，而行程則置于佇列的末尾，
• 先進先出行程（SCHED_FIFO）沒有時間片，在被調度器選擇執行后，可以運行任意長時間，

2、資料結構
實時行程的調度類定義：

const struct sched_class rt_sched_class = {
    .next = &fair_sched_class,
    .enqueue_task = enqueue_task_rt,
    .dequeue_task = dequeue_task_rt,
    .yield_task = yield_task_rt,
    .check_preempt_curr = check_preempt_curr_rt,
    .pick_next_task = pick_next_task_rt,
    .put_prev_task = put_prev_task_rt,
    .set_curr_task = set_curr_task_rt,
    .task_tick = task_tick_rt,
};

實時調度器類的實作比完全公平調度器簡單（核心調度器的就緒佇列也包含了用于實時行程的子就緒佇列，是一個嵌入的struct rt_rq實體）

圖8是時調度類就緒佇列示意圖，一個鏈表中，表頭為active.queue[prio]，而active.bitmap位圖中的每個位元位對應于一個鏈表，凡包含了行程的鏈表，對應的位元位則置位，如果鏈表中沒有行程，則對應的位元位不置位，

sched_find_first_bit是一個標準函式，可以找到active.bitmap中第一個置位的位元位（高優先級），取出所選鏈表的第一個行程，并將se.exec_start設定為就緒佇列的當前實際時鐘值，

對于周期調度：SCHED_FIFO行程可以運行任意長的時間，而且必須使用yield系統呼叫將控制權顯式傳遞給另一個行程，對回圈行程（SCHED_RR），則減少其時間片，在尚未超出時間段時，行程可以繼續執行，計數器歸0后，其值重置為DEF_TIMESLICE，即100 * HZ / 1000（ 100毫秒），如果該行程不是鏈表中唯一的行程，則重新排隊到末尾，通過用set_tsk_need_resched設定TIF_NEED_RESCHED標志，照常請求重調度，

為將行程轉換為實時行程，必須使用sched_setscheduler系統呼叫，該系統呼叫完成了以下幾個任務：

• 使用deactivate_task將行程從當前佇列移除，
• 在task_struct中設定實時優先級和調度類，
• 重新激活行程，

只有具有root權限（或等價于CAP_SYS_NICE）的行程執行了sched_setscheduler系統呼叫，才能修改調度器類或優先級，否則，調度類只能從SCHED_NORMAL改為SCHED_BATCH，只有目標行程的UID或EUID與呼叫者行程的EUID相同時，才能修改目標行程的優先級，此外，優先級只能降低，不能提升，

四、調度器增強

1、SMP調度
對于多處理器系統，CPU負荷必須盡可能公平地在所有的處理器上共享；行程與系統中某些處理器的親合性（affinity）必須是可設定的；內核必須能夠將行程從一個CPU遷移到另一個，

行程對特定CPU 的親合性， 定義在task_struct 的cpus_allowed成員中，可以通過sched_setaffinity系統呼叫修改行程與CPU的現有分配關系，

（1）資料結構的擴展

每當內核認為有必要重新均衡時，核心調度器就會呼叫load_balance和move_one_task函式，特定于調度器類的函式建立一個迭代器，使核心調度器能遍歷所有可能遷移到另一個佇列的備選行程，load_balance函式指標采用了一般性的函式load_balance，允許從最忙的就緒佇列分配多個行程到當前CPU，但移動的負荷不能比max_load_move更多；move_one_task使用了iter_move_one_task，從最忙碌的就緒佇列移出一個行程，遷移到當前CPU的就緒佇列，

負載均衡發起程序：在SMP系統上，周期性調度器函式scheduler_tick按上文所述完成所有系統都需要的任務之后，會呼叫trigger_load_balance函式，這會引發SCHEDULE_SOFTIRQ軟中斷softIRQ（確保會在適當的時機執行run_rebalance_domains），該函式最終對當前CPU呼叫rebalance_domains，實作負載均衡，

就緒佇列是特定于CPU的，內核為每個就緒佇列提供了一個遷移執行緒，可以接收遷移請求，這些請求保存在鏈表migration_queue中，這樣的請求通常發源于調度器自身，但如果行程被限制在某一特定的CPU集合上，而不能在當前執行的CPU上繼續運行時，也可能出現這樣的請求，內核試圖周期性地均衡就緒佇列，但如果對某個就緒佇列效果不佳，則必須使用主動均衡（active balancing），

所有的就緒佇列組織為調度域（scheduling domain），這可以將物理上鄰近或共享高速快取的CPU群集起來，應優先選擇在這些CPU之間遷移行程，

對于load_balance函式，它會檢測在上一次重新均衡操作之后是否已經過去了足夠多的時間，在必要的情況下，它會發起一輪新的均衡操作，首先該函式通過find_busiest_queue標識出哪個佇列作業量最大，如果至少有一個行程在該佇列上執行，則使用move_tasks將該佇列中適當數目的行程遷移到當前佇列，move_tasks函式接下來會呼叫特定于調度器類的load_balance方法，如果均衡操作失敗，那么將喚醒負責最忙的就緒佇列的遷移執行緒，

（2）遷移執行緒

遷移執行緒是一個執行migration_thread的內核執行緒（如圖10所示），用于兩個目的：

• 完成發自調度器的遷移請求；
• 實作主動均衡，
  
  migration_thread內部是一個無限回圈，在無事可做時進入睡眠狀態，

首先，該函式檢測是否需要主動均衡，如果需要，則呼叫active_load_balance滿足該請求，該函式試圖從當前就緒佇列移出一個行程，且移至發起主動均衡請求CPU的就緒佇列，它使用move_one_task完成該作業，后者又對所有的調度器類，分別呼叫特定于調度器類的move_one_task函式，直至其中一個成功，

完成主動負載均衡之后，遷移執行緒會檢測migrate_req鏈表中是否有來自調度器的待決遷移請求，如果沒有，則執行緒發出重調度請求，否則，用__migrate_task完成相關請求，該函式會直接移出所要求的行程，而不再與調度器類進一步互動，

（3）核心調度器的改變

SMP系統與單處理器系統相比的主要差別：

• 在用exec系統呼叫啟動一個新行程時，由于行程尚未執行，這時是調度器跨越CPU移動該行程的一個良好的時機，
• 完全公平調度器的調度粒度與CPU的數目是成比例的，系統中處理器越多，可以采用的調度粒度就越大，

2、調度域和控制組
對于組調度，行程置于不同的組中，調度器首先在這些組之間保證公平，然后在組中的所有行程之間保證公平（比如系統可以向每個用戶授予相同的CPU時間份額），

把行程按用戶分組不是唯一可能的做法，內核還提供了控制組（control group），該特性使得通過特殊檔案系統cgroups可以創建任意的行程集合，甚至可以分為多個層次，

3、內核搶占和低延遲相關作業
（1）內核搶占

在系統呼叫時回傳用戶狀態之前，或者是內核中某些指定的點上，都會呼叫調度器，這確保除了一些明確指定的情況之外，內核是無法中斷的，這不同于用戶行程，如果內核處于相對耗時較長的操作中，這種行為可能會帶來問題，啟用了搶占特性的內核能夠比普通內核更快速地用緊急行程替代當前行程，

在編譯內核時啟用對內核搶占的支持，如果高優先級行程有事情需要完成，那么在啟用內核搶占（與用戶空間程式被其他行程搶占不同）的情況下，不僅用戶空間應用程式可以被中斷，內核也可以被中斷，

為了避免競態條件使系統不一致，內核不能在任意點上被中斷，大多數不能中斷的點已被SMP實作標識，并且實作內核搶占時可以重用這些資訊，內核的某些易于出現問題（臨界區）的部分每次只能由一個處理器訪問，這些部分使用自旋鎖保護，每次內核進入臨界區時，我們必須停用內核搶占，

系統中的每個行程都有一個特定于體系結構的struct thread_info實體，該結構包含了一個搶占計數器，

struct thread_info {
 ...
     int preempt_count; /* 0 => 可搶占， <0 => BUG */
 ...
 }

preempt_count的值（該值通過輔助函式dec_preempt_count和inc_preempt_count分別進行減1和加1操作）確定了內核當前是否處于一個可被中斷的位置，在內核再次啟用搶占之前，必須確認已經離開所有的臨界區，

搶占機制中主要的函式是preempt_schedule，設定了TIF_NEED_RESCHED標志，它不能保證一定可以搶占內核（內核有可能正處于臨界區中），可以通過preempt_reschedule檢查是否可搶占，

激活搶占的兩種方法（本質區別在于，preempt_schedule_irq呼叫時停用了中斷，防止中斷造成遞回呼叫）：

• 使用preempt_schedule，如果調度是由搶占機制發起的（查看搶占計數器中是否設定了PREEMPT_ACTIVE），無需停止當前行程的活動（跳過使用deactivate_task停止不處于可運行狀態行程的活動），盡可能快速選擇下一個行程，
• 是通過preempt_schedule_irq，處理中斷請求后回傳和心態，會檢查搶占技術企的值和是否設定了重調度標志，若都滿足，則呼叫調度器，

（2）低延遲

內核中耗時長的操作（比如繁重的IO操作）不應該完全占據整個系統，相反，它們應該不時地檢測是否有另一個行程變為可運行，并在必要的情況下呼叫調度器選擇相應的行程運行，該機制不依賴于內核搶占，即使內核聯編時未指定支持搶占，也能夠降低延遲，發起有條件重調度的函式是cond_resched，內核代碼中，長時間運行的函式都在適當之處插入了對cond_resched的呼叫，保證較高的相應速度，