調度域 & 調度組

Linux調度域主要分為三層，可以理解為下一層的調度域（domain）成為新的調度組（group）合并入上一層的調度域。

簡單看一下調度域結構體里面的幾個屬性，后面會用得到：

1. parent/child ：父/子調度域

2. last_balance ：上次balance的時間

3. balance_interval ：balance時間間隔

CPU runqueue

每個cpu都會有一個運行隊列，其上存儲著在當前CPU上處于就緒和運行狀態(tài)的進程。

其上的進程包含三個種類的隊列，按照優(yōu)先級順序分別為dl，rt 和 cfs。

其余的結構體內包含信息如圖所示，只列出了和本文相關的部分變量。

負載均衡整體流程

這部分簡要介紹一下負載均衡的整體流程，不會涉及到具體代碼細節(jié)。

如果只是想知道一下流程，那么看完這一段就可以直接左上角了。

1. 調度器的初始化：會對每個cpu的runqueue內容進行初始化，包括調度域，下次調度時間等等，初始化過程中會給rq結構體的next_balance賦予初值，用于后續(xù)判斷是否需要進行負載均衡，該值在后續(xù)執(zhí)行負載均衡函數(shù)調用之后會進行更新。

2. 定時器中斷處理函數(shù)調用scheduler_tick函數(shù)，此函數(shù)是所有調度子函數(shù)的父函數(shù)，是大多數(shù)調度函數(shù)的源，在此函數(shù)內會調用trigger_load_balance函數(shù)觸發(fā)負載均衡的流程。

3. 在trigger_load_balance函數(shù)內會判斷是否已經(jīng)到達當前cpu的rq的負載均衡時間點（next_balance），如果達到就會提交一個軟中斷。處理軟中斷時會調用相應的軟中斷處理函數(shù)，當前cpu就成為負載均衡的dst_cpu。

4. 在軟中斷處理函數(shù)中會調用函數(shù)rebalance_domains，在函數(shù)內部會對當前cpu的相關調度域進行遍歷（遍歷它及它的父調度域），對比是否達到了當前調度域（domain）的負載均衡時間點，從而決定是否需要真正進行負載均衡。

5. 然后在該調度域中找到最忙的調度組，在此調度組中找到最忙的cpu隊列，此cpu即為負載均衡的src_cpu。

6. 接下來，就是將src cpu上的一部分負載拉取到dst cpu上即可。

具體代碼調用流程

這部分會詳細貼出整個負載均衡過程中函數(shù)的調用流程，對于關鍵的部分使用紅色邊框圈起來并進行了介紹。代碼的截圖基本上都保留對應的文件名稱和代碼行數(shù)，感興趣的可以去內核源碼看一看。

調度初始化：sched_init

在start_kernel中對調度器進行初始化的函數(shù)就是sched_init，初始化過程中會給next_balance賦予初值，用于后續(xù)判斷是否需要進行負載均衡，該值在后續(xù)執(zhí)行負載均衡函數(shù)調用之后會進行更新。

定時器調用scheduler_tick

scheduler_tick()是所有調度子函數(shù)的父函數(shù)，而其是由Linux時間子系統(tǒng)的tick_device調用。tick_device是一個周期性定時器，定時時間為1個tick，當觸發(fā)中斷后，會在中斷處理函數(shù)中，調用scheduler_tick()。

而打開了tickless，即動態(tài)tick后，那么就會切換至oneshot模式，并負責調用scheduler_tick()。

注：定時器運行在單觸發(fā)模式（one-shot mode），與周期模式（periodic mode）運行的定時器不同，周期模式運行的定時器，只要對它進行一次初始化操作，以后定時器就會周期的產(chǎn)生中斷，不再需要額外的對定時器進行編程操作；而當定時器運行于單觸發(fā)模式下時，每當定時器產(chǎn)生一次中斷后就不再運行，系統(tǒng)再根據(jù)當前任務對時間的要求計算出定時器下一次應該產(chǎn)生中斷的時間間隔，然后再對定時器進行編程，使它能在系統(tǒng)要求的將來某一時刻產(chǎn)生中斷。在單觸發(fā)模式下，定時器的定時精度能達到微秒級。不過需要注意的是，由于每次中斷后都要計算下一次中斷的時間，而且還要對定時器進行編程，這兩個操作會降低系統(tǒng)的性能。

scheduler_tick

scheduler_tick 是所有調度子函數(shù)的父函數(shù)，是大多數(shù)調度函數(shù)的源。

trigger_load_balance

CPU對應的運行隊列數(shù)據(jù)結構中記錄了下一次周期性負載均衡的時間，當超過這個時間點后，將觸發(fā)SCHED_SOFTIRQ軟中斷來進行負載均衡。

本質上就是判斷一下當前的jiffies是不是已經(jīng)比rq->next_balance值大，如果值大的話，會進一步調用raise_softirq提交一個軟中斷。提交的過程很簡單，就是把SCHED_SOFTIRQ對應的位置位，處理軟中斷時檢查是否位，如果置位調用相應的軟中斷處理函數(shù)。

關于 cpu_active ，我簡單查了一下，不確定正確性：

When CPU entered 1st step, i.e. the CPU_DOWN_PREPARE, the scheduler marks it as not 'active', but it's still 'online' at the moment. Scheduler could not migrate any task to it at this time. After the CPU is totally removed, it's not 'online' anymore