1 前景回顧 1.1 進程調度 記憶體中保存了對每個進程的唯一描述, 並通過若幹結構與其他進程連接起來. 調度器 面對的情形就是這樣, 其任務是在程式之間共用CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及 調度策略 , 另外一個涉及 上下文切換 . 內核必須提供一種方法, ...
1 前景回顧
1.1 進程調度
記憶體中保存了對每個進程的唯一描述, 並通過若幹結構與其他進程連接起來.
調度器面對的情形就是這樣, 其任務是在程式之間共用CPU時間, 創造並行執行的錯覺, 該任務分為兩個不同的部分, 其中一個涉及調度策略, 另外一個涉及上下文切換.
內核必須提供一種方法, 在各個進程之間儘可能公平地共用CPU時間, 而同時又要考慮不同的任務優先順序.
調度器的一個重要目標是有效地分配 CPU 時間片，同時提供很好的用戶體驗。調度器還需要面對一些互相衝突的目標，例如既要為關鍵實時任務最小化響應時間, 又要最大限度地提高 CPU 的總體利用率.
調度器的一般原理是, 按所需分配的計算能力, 向系統中每個進程提供最大的公正性, 或者從另外一個角度上說, 他試圖確保沒有進程被虧待.
1.2 進程的分類
linux把進程區分為實時進程和非實時進程, 其中非實時進程進一步劃分為互動式進程和批處理進程
| 類型 | 描述 | 示例 |
|---|---|---|
| 互動式進程(interactive process) | 此類進程經常與用戶進行交互, 因此需要花費很多時間等待鍵盤和滑鼠操作. 當接受了用戶的輸入後, 進程必須很快被喚醒, 否則用戶會感覺系統反應遲鈍 | shell, 文本編輯程式和圖形應用程式 |
| 批處理進程(batch process) | 此類進程不必與用戶交互, 因此經常在後臺運行. 因為這樣的進程不必很快相應, 因此常受到調度程式的怠慢 | 程式語言的編譯程式, 資料庫搜索引擎以及科學計算 |
| 實時進程(real-time process) | 這些進程由很強的調度需要, 這樣的進程絕不會被低優先順序的進程阻塞. 並且他們的響應時間要儘可能的短 | 視頻音頻應用程式, 機器人控製程序以及從物理感測器上收集數據的程式 |
在linux中, 調度演算法可以明確的確認所有實時進程的身份, 但是沒辦法區分互動式程式和批處理程式, linux2.6的調度程式實現了基於進程過去行為的啟髮式演算法, 以確定進程應該被當做互動式進程還是批處理進程. 當然與批處理進程相比, 調度程式有偏愛互動式進程的傾向
1.3 不同進程採用不同的調度策略
根據進程的不同分類Linux採用不同的調度策略.
對於實時進程，採用FIFO或者Round Robin的調度策略.
對於普通進程，則需要區分互動式和批處理式的不同。傳統Linux調度器提高互動式應用的優先順序，使得它們能更快地被調度。而CFS和RSDL等新的調度器的核心思想是”完全公平”。這個設計理念不僅大大簡化了調度器的代碼複雜度，還對各種調度需求的提供了更完美的支持.
註意Linux通過將進程和線程調度視為一個，同時包含二者。進程可以看做是單個線程，但是進程可以包含共用一定資源（代碼和/或數據）的多個線程。因此進程調度也包含了線程調度的功能.
目前非實時進程的調度策略比較簡單, 因為實時進程值只要求儘可能快的被響應, 基於優先順序, 每個進程根據它重要程度的不同被賦予不同的優先順序，調度器在每次調度時, 總選擇優先順序最高的進程開始執行. 低優先順序不可能搶占高優先順序, 因此FIFO或者Round Robin的調度策略即可滿足實時進程調度的需求.
但是普通進程的調度策略就比較麻煩了, 因為普通進程不能簡單的只看優先順序, 必須公平的占有CPU, 否則很容易出現進程饑餓, 這種情況下用戶會感覺操作系統很卡, 響應總是很慢，因此在linux調度器的發展歷程中經過了多次重大變動, linux總是希望尋找一個最接近於完美的調度策略來公平快速的調度進程.
1.4 linux調度器的演變
一開始的調度器是複雜度為O(n)的始調度演算法(實際上每次會遍歷所有任務，所以複雜度為O(n)), 這個演算法的缺點是當內核中有很多任務時，調度器本身就會耗費不少時間，所以，從linux2.5開始引入赫赫有名的O(1)調度器
然而，linux是集全球很多程式員的聰明才智而發展起來的超級內核，沒有最好，只有更好，在O(1)調度器風光了沒幾天就又被另一個更優秀的調度器取代了，它就是CFS調度器Completely Fair Scheduler. 這個也是在2.6內核中引入的，具體為2.6.23，即從此版本開始，內核使用CFS作為它的預設調度器，O(1)調度器被拋棄了, 其實CFS的發展也是經歷了很多階段，最早期的樓梯演算法(SD), 後來逐步對SD演算法進行改進出RSDL(Rotating Staircase Deadline Scheduler), 這個演算法已經是”完全公平”的雛形了， 直至CFS是最終被內核採納的調度器, 它從RSDL/SD中吸取了完全公平的思想，不再跟蹤進程的睡眠時間，也不再企圖區分互動式進程。它將所有的進程都統一對待，這就是公平的含義。CFS的演算法和實現都相當簡單，眾多的測試表明其性能也非常優越
| 欄位 | 版本 |
|---|---|
| O(n)的始調度演算法 | linux-0.11~2.4 |
| O(1)調度器 | linux-2.5 |
| CFS調度器 | linux-2.6~至今 |
2 Linux的調度器組成
2.1 2個調度器
可以用兩種方法來激活調度
- 一種是直接的, 比如進程打算睡眠或出於其他原因放棄CPU
- 另一種是通過周期性的機制, 以固定的頻率運行, 不時的檢測是否有必要
因此當前linux的調度程式由兩個調度器組成：主調度器，周期性調度器(兩者又統稱為通用調度器(generic scheduler)或核心調度器(core scheduler))
並且每個調度器包括兩個內容：調度框架(其實質就是兩個函數框架)及調度器類
2.2 6種調度策略
linux內核目前實現了6中調度策略(即調度演算法), 用於對不同類型的進程進行調度, 或者支持某些特殊的功能
比如SCHED_NORMAL和SCHED_BATCH調度普通的非實時進程, SCHED_FIFO和SCHED_RR和SCHED_DEADLINE則採用不同的調度策略調度實時進程, SCHED_IDLE則在系統空閑時調用idle進程.
idle的運行時機
idle 進程優先順序為MAX_PRIO，即最低優先順序。
早先版本中，idle是參與調度的，所以將其優先順序設為最低，當沒有其他進程可以運行時，才會調度執行 idle
而目前的版本中idle並不在運行隊列中參與調度，而是在cpu全局運行隊列rq中含idle指針，指向idle進程, 在調度器發現運行隊列為空的時候運行, 調入運行
| 欄位 | 描述 | 所在調度器類 |
|---|---|---|
| SCHED_NORMAL | （也叫SCHED_OTHER）用於普通進程，通過CFS調度器實現。SCHED_BATCH用於非交互的處理器消耗型進程。SCHED_IDLE是在系統負載很低時使用 | CFS |
| SCHED_BATCH | SCHED_NORMAL普通進程策略的分化版本。採用分時策略，根據動態優先順序(可用nice()API設置），分配CPU運算資源。註意：這類進程比上述兩類實時進程優先順序低，換言之，在有實時進程存在時，實時進程優先調度。但針對吞吐量優化, 除了不能搶占外與常規任務一樣，允許任務運行更長時間，更好地使用高速緩存，適合於成批處理的工作 | CFS |
| SCHED_IDLE | 優先順序最低，在系統空閑時才跑這類進程(如利用閑散電腦資源跑地外文明搜索，蛋白質結構分析等任務，是此調度策略的適用者） | CFS-IDLE |
| SCHED_FIFO | 先入先出調度演算法（實時調度策略），相同優先順序的任務先到先服務，高優先順序的任務可以搶占低優先順序的任務 | RT |
| SCHED_RR | 輪流調度演算法（實時調度策略），後者提供 Roound-Robin 語義，採用時間片，相同優先順序的任務當用完時間片會被放到隊列尾部，以保證公平性，同樣，高優先順序的任務可以搶占低優先順序的任務。不同要求的實時任務可以根據需要用sched_setscheduler() API設置策略 | RT |
| SCHED_DEADLINE | 新支持的實時進程調度策略，針對突髮型計算，且對延遲和完成時間高度敏感的任務適用。基於Earliest Deadline First (EDF) 調度演算法 | DL |
linux內核實現的6種調度策略, 前面三種策略使用的是cfs調度器類，後面兩種使用rt調度器類, 最後一個使用DL調度器類
2.3 5個調度器類
而依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.
| 調度器類 | 描述 | 對應調度策略 |
|---|---|---|
| stop_sched_class | 優先順序最高的線程，會中斷所有其他線程，且不會被其他任務打斷 作用 1. 發生在cpu_stop_cpu_callback 進行cpu之間任務migration 2. HOTPLUG_CPU的情況下關閉任務 |
無, 不需要調度普通進程 |
| dl_sched_class | 採用EDF最早截至時間優先演算法調度實時進程 | SCHED_DEADLINE |
| rt_sched_class | 採用提供 Roound-Robin演算法或者FIFO演算法調度實時進程 具體調度策略由進程的task_struct->policy指定 |
SCHED_FIFO, SCHED_RR |
| fair_sched_clas | 採用CFS演算法調度普通的非實時進程 | SCHED_NORMAL, SCHED_BATCH |
| idle_sched_class | 採用CFS演算法調度idle進程, 每個cup的第一個pid=0線程：swapper，是一個靜態線程。調度類屬於：idel_sched_class，所以在ps裡面是看不到的。一般運行在開機過程和cpu異常的時候做dump | SCHED_IDLE |
其所屬進程的優先順序順序為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class2.4 3個調度實體
調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPUI時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配.
linux中針對當前可調度的實時和非實時進程, 定義了類型為seched_entity的3個調度實體
| 調度實體 | 名稱 | 描述 | 對應調度器類 |
|---|---|---|---|
| sched_dl_entity | DEADLINE調度實體 | 採用EDF演算法調度的實時調度實體 | dl_sched_class |
| sched_rt_entity | RT調度實體 | 採用Roound-Robin或者FIFO演算法調度的實時調度實體 | rt_sched_class |
| sched_entity | CFS調度實體 | 採用CFS演算法調度的普通非實時進程的調度實體 | fair_sched_class |
2.5 調度器類的就緒隊列
另外，對於調度框架及調度器類，它們都有自己管理的運行隊列，調度框架只識別rq（其實它也不能算是運行隊列），而對於cfs調度器類它的運行隊列則是cfs_rq（內部使用紅黑樹組織調度實體），實時rt的運行隊列則為rt_rq（內部使用優先順序bitmap+雙向鏈表組織調度實體）, 此外內核對新增的dl實時調度策略也提供了運行隊列dl_rq
2.6 調度器整體框架
本質上, 通用調度器(核心調度器)是一個分配器,與其他兩個組件交互.
調度器用於判斷接下來運行哪個進程.
內核支持不同的調度策略(完全公平調度, 實時調度, 在無事可做的時候調度空閑進程,即0號進程也叫swapper進程,idle進程), 調度類使得能夠以模塊化的方法實現這些側露額, 即一個類的代碼不需要與其他類的代碼交互
當調度器被調用時, 他會查詢調度器類, 得知接下來運行哪個進程在選中將要運行的進程之後, 必須執行底層的任務切換.
這需要與CPU的緊密交互. 每個進程剛好屬於某一調度類, 各個調度類負責管理所屬的進程. 通用調度器自身不涉及進程管理, 其工作都委托給調度器類.
每個進程都屬於某個調度器類(由欄位task_struct->sched_class標識), 由調度器類採用進程對應的調度策略調度(由task_struct->policy )進行調度, task_struct也存儲了其對應的調度實體標識
linux實現了6種調度策略, 依據其調度策略的不同實現了5個調度器類, 一個調度器類可以用一種或者多種調度策略調度某一類進程, 也可以用於特殊情況或者調度特殊功能的進程.
| 調度器類 | 調度策略 | 調度策略對應的調度演算法 | 調度實體 | 調度實體對應的調度對象 |
|---|---|---|---|---|
| stop_sched_class | 無 | 無 | 無 | 特殊情況, 發生在cpu_stop_cpu_callback 進行cpu之間任務遷移migration或者HOTPLUG_CPU的情況下關閉任務 |
| dl_sched_class | SCHED_DEADLINE | Earliest-Deadline-First最早截至時間有限演算法 | sched_dl_entity | 採用DEF最早截至時間有限演算法調度實時進程 |
| rt_sched_class | SCHED_RR SCHED_FIFO |
Roound-Robin時間片輪轉演算法 FIFO先進先出演算法 |
sched_rt_entity | 採用Roound-Robin或者FIFO演算法調度的實時調度實體 |
| fair_sched_class | SCHED_NORMAL SCHED_BATCH |
CFS完全公平懂調度演算法 | sched_entity | 採用CFS演算法普通非實時進程 |
| idle_sched_class | SCHED_IDLE | 無 | 無 | 特殊進程, 用於cpu空閑時調度空閑進程idle |
它們的關係如下圖
2.7 5種調度器類為什麼只有3種調度實體?
正常來說一個調度器類應該對應一類調度實體, 但是5種調度器類卻只有了3種調度實體?
這是因為調度實體本質是一個可以被調度的對象, 要麼是一個進程(linux中線程本質上也是進程), 要麼是一個進程組, 只有dl_sched_class, rt_sched_class調度的實時進程(組)以及fair_sched_class調度的非實時進程(組)是可以被調度的實體對象, 而stop_sched_class和idle_sched_class
2.8 為什麼採用EDF實時調度需要單獨的調度器類, 調度策略和調度實體
linux針對實時進程實現了Roound-Robin, FIFO和Earliest-Deadline-First(EDF)演算法, 但是為什麼SCHED_RR和SCHED_FIFO兩種調度演算法都用rt_sched_class調度類和sched_rt_entity調度實體描述, 而EDF演算法卻需要單獨用rt_sched_class調度類和sched_dl_entity調度實體描述
為什麼採用EDF實時調度不用rt_sched_class調度類調度, 而是單獨實現調度類和調度實體?
暫時沒弄明白
3 進程調度的數據結構
調度器使用一系列數據結構來排序和管理系統中的進程. 調度器的工作方式的這些結構的涉及密切相關, 幾個組件在許多方面
3.1 task_struct中調度相關的成員
struct task_struct
{
........
/* 表示是否在運行隊列 */
int on_rq;
/* 進程優先順序
* prio: 動態優先順序，範圍為100~139，與靜態優先順序和補償(bonus)有關
* static_prio: 靜態優先順序，static_prio = 100 + nice + 20 (nice值為-20~19,所以static_prio值為100~139)
* normal_prio: 沒有受優先順序繼承影響的常規優先順序，具體見normal_prio函數，跟屬於什麼類型的進程有關
*/
int prio, static_prio, normal_prio;
/* 實時進程優先順序 */
unsigned int rt_priority;
/* 調度類，調度處理函數類 */
const struct sched_class *sched_class;
/* 調度實體(紅黑樹的一個結點) */
struct sched_entity se;
/* 調度實體(實時調度使用) */
struct sched_rt_entity rt;
struct sched_dl_entity dl;
#ifdef CONFIG_CGROUP_SCHED
/* 指向其所在進程組 */
struct task_group *sched_task_group;
#endif
........
}3.1.1 優先順序
int prio, static_prio, normal_prio;
unsigned int rt_priority;動態優先順序 靜態優先順序 實時優先順序
其中task_struct採用了三個成員表示進程的優先順序:prio和normal_prio表示動態優先順序, static_prio表示進程的靜態優先順序.
為什麼表示動態優先順序需要兩個值prio和normal_prio
調度器會考慮的優先順序則保存在prio. 由於在某些情況下內核需要暫時提高進程的優先順序, 因此需要用prio表示. 由於這些改變不是持久的, 因此靜態優先順序static_prio和普通優先順序normal_prio不受影響.
此外還用了一個欄位rt_priority保存了實時進程的優先順序
| 欄位 | 描述 |
|---|---|
| static_prio | 用於保存靜態優先順序, 是進程啟動時分配的優先順序, ，可以通過nice和sched_setscheduler系統調用來進行修改, 否則在進程運行期間會一直保持恆定 |
| prio | 保存進程的動態優先順序 |
| normal_prio | 表示基於進程的靜態優先順序static_prio和調度策略計算出的優先順序. 因此即使普通進程和實時進程具有相同的靜態優先順序, 其普通優先順序也是不同的, 進程分叉(fork)時, 子進程會繼承父進程的普通優先順序 |
| rt_priority | 用於保存實時優先順序 |
linux2.6內核將任務優先順序進行了一個劃分, 實時優先順序範圍是0到MAX_RT_PRIO-1（即99），而普通進程的靜態優先順序範圍是從MAX_RT_PRIO到MAX_PRIO-1（即100到139）。
/* http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L21 */
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
/* http://lxr.free-electrons.com/source/include/linux/sched/prio.h?v=4.6#L24 */
#define MAX_PRIO (MAX_RT_PRIO + 40)
#define DEFAULT_PRIO (MAX_RT_PRIO + 20)
| 優先順序範圍 | 描述 |
|---|---|
| 0——99 | 實時進程 |
| 100——139 | 非實時進程 |
3.1.2 調度策略
unsigned int policy;policy保存了進程的調度策略，目前主要有以下五種：
參見
http://lxr.free-electrons.com/source/include/uapi/linux/sched.h?v=4.6#L32
/*
* Scheduling policies
*/
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6| 欄位 | 描述 |
|---|---|
| sched_class | 調度類, 調度類，調度處理函數類 |
| se | 普通進程的調用實體, 每個進程都有其中之一的實體 |
| rt | 實時進程的調用實體, 每個進程都有其中之一的實體 |
| dl | deadline的調度實體 |
| cpus_allowed | 用於控制進程可以在哪裡處理器上運行 |
調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPUI時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配
cpus_allows是一個位域, 在多處理器系統上使用, 用來限制進程可以在哪些CPU上運行
| 欄位 | 描述 | 所在調度器類 |
|---|---|---|
| SCHED_NORMAL | （也叫SCHED_OTHER）用於普通進程，通過CFS調度器實現。 | 無 |
| SCHED_BATCH | SCHED_NORMAL普通進程策略的分化版本。採用分時策略，根據動態優先順序(可用nice()API設置），分配 CPU 運算資源。註意：這類進程比兩類實時進程優先順序低，換言之，在有實時進程存在時，實時進程優先調度。但針對吞吐量優化 | CFS |
| SCHED_IDLE | 優先順序最低，在系統空閑時才跑這類進程(如利用閑散電腦資源跑地外文明搜索，蛋白質結構分析等任務，是此調度策略的適用者） | CFS |
| SCHED_FIFO | 先入先出調度演算法（實時調度策略），相同優先順序的任務先到先服務，高優先順序的任務可以搶占低優先順序的任務 | rt |
| SCHED_RR | 輪流調度演算法（實時調度策略），後 者提供 Roound-Robin 語義，採用時間片，相同優先順序的任務當用完時間片會被放到隊列尾部，以保證公平性，同樣，高優先順序的任務可以搶占低優先順序的任務。不同要求的實時任務可以根據需要用sched_setscheduler()API 設置策略 | RT |
| SCHED_DEADLINE | 新支持的實時進程調度策略，針對突髮型計算，且對延遲和完成時間高度敏感的任務適用。基於Earliest Deadline First (EDF) 調度演算法 | 無 |
CHED_BATCH用於非交互的處理器消耗型進程
CHED_IDLE是在系統負載很低時使用CFS
SCHED_BATCH用於非交互, CPU使用密集型的批處理進程. 調度決策對此類進程給予”冷處理”: 他們絕不會搶占CF調度器處理的另一個進程, 因此不會幹擾互動式進程. 如果打算使用nice值降低進程的靜態優先順序, 同時又不希望該進程影響系統的交互性, 此時最適合使用該調度類.
而SCHED_LDLE進程的重要性則會進一步降低, 因此其權重總是最小的
註意：儘管名稱是SCHED_IDLE但是SCHED_IDLE不負責調度空閑進程. 空閑進程由內核提供單獨的機制來處理
SCHED_RR和SCHED_FIFO用於實現軟實時進程. SCHED_RR實現了輪流調度演算法, 一種迴圈時間片的方法, 而SCHED_FIFO實現了先進先出的機制, 這些並不是由完全貢品調度器類CFS處理的, 而是由實時調度類處理.
3.1.3 調度策略相關欄位
/* http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L1431 */
unsigned int policy;
/* http://lxr.free-electrons.com/source/include/linux/sched.h?v=4.6#L1413 */
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;
cpumask_t cpus_allowed;
| 欄位 | 描述 |
|---|---|
| sched_class | 調度類, 調度類，調度處理函數類 |
| se | 普通進程的調用實體, 每個進程都有其中之一的實體 |
| rt | 實時進程的調用實體, 每個進程都有其中之一的實體 |
| dl | deadline的調度實體 |
| cpus_allowed | 用於控制進程可以在哪裡處理器上運行 |
調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPUI時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配
cpus_allows是一個位域, 在多處理器系統上使用, 用來限制進程可以在哪些CPU上運行
3.2 調度類
sched_class結構體表示調度類, 類提供了通用調度器和各個調度器之間的關聯, 調度器類和特定數據結構中彙集地幾個函數指針表示, 全局調度器請求的各個操作都可以用一個指針表示, 這使得無需瞭解調度器類的內部工作原理即可創建通用調度器, 定義在kernel/sched/sched.h
struct sched_class {
/* 系統中多個調度類, 按照其調度的優先順序排成一個鏈表
下一優先順序的調度類
* 調度類優先順序順序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
*/
const struct sched_class *next;
/* 將進程加入到運行隊列中，即將調度實體（進程）放入紅黑樹中，並對 nr_running 變數加1 */
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
/* 從運行隊列中刪除進程，並對 nr_running 變數中減1 */
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
/* 放棄CPU，在 compat_yield sysctl 關閉的情況下，該函數實際上執行先出隊後入隊；在這種情況下，它將調度實體放在紅黑樹的最右端 */
void (*yield_task) (struct rq *rq);
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
/* 檢查當前進程是否可被新進程搶占 */
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
/*
* It is the responsibility of the pick_next_task() method that will
* return the next task to call put_prev_task() on the @prev task or
* something equivalent.
*
* May return RETRY_TASK when it finds a higher prio class has runnable
* tasks.
*/
/* 選擇下一個應該要運行的進程運行 */
struct task_struct * (*pick_next_task) (struct rq *rq,
struct task_struct *prev);
/* 將進程放回運行隊列 */
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
/* 為進程選擇一個合適的CPU */
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
/* 遷移任務到另一個CPU */
void (*migrate_task_rq)(struct task_struct *p);
/* 用於進程喚醒 */
void (*task_waking) (struct task_struct *task);
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
/* 修改進程的CPU親和力(affinity) */
void (*set_cpus_allowed)(struct task_struct *p,
const struct cpumask *newmask);
/* 啟動運行隊列 */
void (*rq_online)(struct rq *rq);
/* 禁止運行隊列 */
void (*rq_offline)(struct rq *rq);
#endif
/* 當進程改變它的調度類或進程組時被調用 */
void (*set_curr_task) (struct rq *rq);
/* 該函數通常調用自 time tick 函數；它可能引起進程切換。這將驅動運行時（running）搶占 */
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
/* 在進程創建時調用，不同調度策略的進程初始化不一樣 */
void (*task_fork) (struct task_struct *p);
/* 在進程退出時會使用 */
void (*task_dead) (struct task_struct *p);
/*
* The switched_from() call is allowed to drop rq->lock, therefore we
* cannot assume the switched_from/switched_to pair is serliazed by
* rq->lock. They are however serialized by p->pi_lock.
*/
/* 用於進程切換 */
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
/* 改變優先順序 */
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
int oldprio);
unsigned int (*get_rr_interval) (struct rq *rq,
struct task_struct *task);
void (*update_curr) (struct rq *rq);
#ifdef CONFIG_FAIR_GROUP_SCHED
void (*task_move_group) (struct task_struct *p);
#endif
};| 成員 | 描述 |
|---|---|
| enqueue_task | 向就緒隊列中添加一個進程, 某個任務進入可運行狀態時，該函數將得到調用。它將調度實體（進程）放入紅黑樹中，並對 nr_running 變數加 1 |
| dequeue_task | 將一個進程從就就緒隊列中刪除, 當某個任務退出可運行狀態時調用該函數，它將從紅黑樹中去掉對應的調度實體，並從 nr_running 變數中減 1 |
| yield_task | 在進程想要資源放棄對處理器的控制權的時, 可使用在sched_yield系統調用, 會調用內核API yield_task完成此工作. compat_yield sysctl 關閉的情況下，該函數實際上執行先出隊後入隊；在這種情況下，它將調度實體放在紅黑樹的最右端 |
| check_preempt_curr | 該函數將檢查當前運行的任務是否被搶占。在實際搶占正在運行的任務之前，CFS 調度程式模塊將執行公平性測試。這將驅動喚醒式（wakeup）搶占 |
| pick_next_task | 該函數選擇接下來要運行的最合適的進程 |
| put_prev_task | 用另一個進程代替當前運行的進程 |
| set_curr_task | 當任務修改其調度類或修改其任務組時，將調用這個函數 |
| task_tick | 在每次激活周期調度器時, 由周期性調度器調用, 該函數通常調用自 time tick 函數；它可能引起進程切換。這將驅動運行時（running）搶占 |
| task_new | 內核調度程式為調度模塊提供了管理新任務啟動的機會, 用於建立fork系統調用和調度器之間的關聯, 每次新進程建立後, 則用new_task通知調度器, CFS 調度模塊使用它進行組調度，而用於實時任務的調度模塊則不會使用這個函數 |
對於各個調度器類, 都必須提供struct sched_class的一個實例, 目前內核中有實現以下五種:
// http://lxr.free-electrons.com/source/kernel/sched/sched.h?v=4.6#L1254
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;
| 調度器類 | 定義 | 描述 |
|---|---|---|
| stop_sched_class | kernel/sched/stop_task.c, line 112 | 優先順序最高的線程，會中斷所有其他線程，且不會被其他任務打斷。作用： 1.發生在cpu_stop_cpu_callback 進行cpu之間任務migration； 2.HOTPLUG_CPU的情況下關閉任務。 |
| dl_sched_class | kernel/sched/deadline.c, line 1774 | 無 |
| rt_sched_class | kernel/sched/rt.c, line 2326 | RT，作用：實時線程 |
| idle_sched_class | kernel/sched/idle_task.c, line 81 | 每個cup的第一個pid=0線程：swapper，是一個靜態線程。調度類屬於：idel_sched_class，所以在ps裡面是看不到的。一般運行在開機過程和cpu異常的時候做dump |
| fair_sched_class | kernel/sched/fair.c, line 8521 | CFS（公平調度器），作用：一般常規線程 |
目前系統中,Scheduling Class的優先順序順序為
stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class開發者可以根據己的設計需求,來把所屬的Task配置到不同的Scheduling Class中.
用戶層應用程式無法直接與調度類交互, 他們只知道上下文定義的常量SCHED_XXX(用task_struct->policy表示), 這些常量提供了調度類之間的映射。
SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE被映射到fair_sched_class
SCHED_RR和SCHED_FIFO則與rt_schedule_class相關聯
3.3 就緒隊列
就緒隊列是核心調度器用於管理活動進程的主要數據結構。
各個·CPU都有自身的就緒隊列，各個活動進程只出現在一個就緒隊列中, 在多個CPU上同時運行一個進程是不可能的.
早期的內核中就緒隊列是全局的, 即即有全局唯一的rq, 但是 在Linux-2.6內核時代，為了更好的支持多核，Linux調度器普遍採用了per-cpu的run queue，從而剋服了多CPU系統中，全局唯一的run queue由於資源的競爭而成為了系統瓶頸的問題，因為在同一時刻，一個CPU訪問run queue時，其他的CPU即使空閑也必須等待，大大降低了整體的CPU利用率和系統性能。當使用per-CPU的run queue之後，每個CPU不再使用大內核鎖，從而大大提高了並行處理的調度能力。
參照CFS調度的總結 - （單rq vs 多rq）
就緒隊列是全局調度器許多操作的起點, 但是進程並不是由就緒隊列直接管理的, 調度管理是各個調度器的職責, 因此在各個就緒隊列中嵌入了特定調度類的子就緒隊列(cfs的頂級調度就隊列 struct cfs_rq, 實時調度類的就緒隊列struct rt_rq和deadline調度類的就緒隊列struct dl_rq
3.3.1 CPU就緒隊列struct rq
就緒隊列用struct rq來表示, 其定義在kernel/sched/sched.h, line 566
/*每個處理器都會配置一個rq*/
struct rq {
/* runqueue lock: */
spinlock_t lock;
/*
* nr_running and cpu_load should be in the same cacheline because
* remote CPUs use both these fields when doing load calculation.
*/
/*用以記錄目前處理器rq中執行task的數量*/
unsigned long nr_running;
#ifdef CONFIG_NUMA_BALANCING
unsigned int nr_numa_running;
unsigned int nr_preferred_running;
#endif
#define CPU_LOAD_IDX_MAX 5
/*用以表示處理器的負載，在每個處理器的rq中都會有對應到該處理器的cpu_load參數配置，
在每次處理器觸發scheduler tick時，都會調用函數update_cpu_load_active,進行cpu_load的更新
在系統初始化的時候會調用函數sched_init把rq的cpu_load array初始化為0.
瞭解他的更新方式最好的方式是通過函數update_cpu_load,公式如下
cpu_load[0]會直接等待rq中load.weight的值。
cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2
cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4
cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8
cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16
調用函數this_cpu_load時，所返回的cpu load值是cpu_load[0]
而在進行cpu blance或migration時，就會呼叫函數
source_load target_load取得對該處理器cpu_load index值，
來進行計算*/
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
unsigned long last_load_update_tick;
#ifdef CONFIG_NO_HZ_COMMON
u64 nohz_stamp;
unsigned long nohz_flags;
#endif
#ifdef CONFIG_NO_HZ_FULL
unsigned long last_sched_tick;
#endif
/* capture load from *all* tasks on this cpu: */
/*load->weight值，會是目前所執行的schedule entity的load->weight的總和
也就是說rq的load->weight越高，也表示所負責的排程單元load->weight總和越高
表示處理器所負荷的執行單元也越重*/
struct load_weight load;
/*在每次scheduler tick中呼叫update_cpu_load時，這個值就增加一，
可以用來反饋目前cpu load更新的次數*/
unsigned long nr_load_updates;
/*用來累加處理器進行context switch的次數，會在調用schedule時進行累加，
並可以通過函數nr_context_switches統計目前所有處理器總共的context switch次數
或是可以透過查看檔案/proc/stat中的ctxt位得知目前整個系統觸發context switch的次數*/
u64 nr_switches;
/*為cfs fair scheduling class 的rq就緒隊列 */
struct cfs_rq cfs;
/*為real-time scheduling class 的rq就緒隊列 */
struct rt_rq rt;
/* 為deadline scheduling class 的rq就緒隊列 */
/* 用以支援可以group cfs tasks的機制*/
#ifdef CONFIG_FAIR_GROUP_SCHED
/* list of leaf cfs_rq on this cpu: */
/*
在有設置fair group scheduling 的環境下，
會基於原本cfs rq中包含有若幹task的group所成的排程集合，
也就是說當有一個group a就會有自己的cfs rq用來排程自己所屬的tasks,
而屬於這group a的tasks所使用到的處理器時間就會以這group a總共所分的的時間為上限。
基於cgroup的fair group scheduling 架構，可以創造出有階層性的task組織，
根據不同task的功能群組化在配置給該群主對應的處理器資源，
讓屬於該群主下的task可以透過rq機制使用該群主下的資源。
這個變數主要是管理CFS RQ list，
操作上可以透過函數list_add_leaf_cfs_rq把一個group cfs rq加入到list中，
或透過函數list_del_leaf_cfs_rq把一個group cfs rq移除，
並可以透過for_each_leaf_cfs_rq把一個rq上得所有leaf cfs_rq走一遍
*/
struct list_head leaf_cfs_rq_list;
#endif
/*
* This is part of a global counter where only the total sum
* over all CPUs matters. A task can increase this counter on
* one CPU and if it got migrated afterwards it may decrease
* it on another CPU. Always updated under the runqueue lock:
*/
/*一般來說，linux kernel 的task狀態可以為
TASK_RUNNING, TASK_INTERRUPTIBLE(sleep), TASK_UNINTERRUPTIBLE(Deactivate Task),
此時Task會從rq中移除)或TASK_STOPPED.
透過這個變數會統計目前rq中有多少task屬於TASK_UNINTERRUPTIBLE的狀態。
當調用函數active_task時，會把nr_uninterruptible值減一，
並透過該函數enqueue_task把對應的task依據所在的scheduling class放在對應的rq中
並把目前rq中nr_running值加一 */
unsigned long nr_uninterruptible;
/*
curr:指向目前處理器正在執行的task;
idle:指向屬於idle-task scheduling class 的idle task;
stop:指向目前最高等級屬於stop-task scheduling class
的task; */
struct task_struct *curr, *idle;
/*
基於處理器的jiffies值，用以記錄下次進行處理器balancing 的時間點*/
unsigned long next_balance;
/*
用以存儲context-switch發生時，
前一個task的memory management結構並可用在函數finish_task_switch
透過函數mmdrop釋放前一個task的結構體資源 */
struct mm_struct *prev_mm;
unsigned int clock_skip_update;
/* 用以記錄目前rq的clock值，
基本上該值會等於通過sched_clock_cpu(cpu_of(rq))的返回值，
並會在每次調用scheduler_tick時通過函數update_rq_clock更新目前rq clock值。
函數sched_clock_cpu會通過sched_clock_local或ched_clock_remote取得
對應的sched_clock_data,而處理的sched_clock_data值，
會通過函數sched_clock_tick在每次調用scheduler_tick時進行更新；
*/
u64 clock;
u64 clock_task;
/*用以記錄目前rq中有多少task處於等待i/o的sleep狀態
在實際的使用上，例如當driver接受來自task的調用，
但處於等待i/o回覆的階段時，為了充分利用處理器的執行資源，
這時就可以在driver中調用函數io_schedule，
此時就會把目前rq中的nr_iowait加一，並設定目前task的io_wait為1
然後觸發scheduling 讓其他task有機會可以得到處理器執行時間*/
atomic_t nr_iowait;
#ifdef CONFIG_SMP
/*root domain是基於多核心架構下的機制，
會由rq結構記住目前採用的root domain，
其中包括了目前的cpu mask(包括span,online rt overload), reference count 跟cpupri
當root domain有被rq參考到時，refcount 就加一，反之就減一。
而cpumask span表示rq可掛上的cpu mask,noline為rq目前已經排程的
cpu mask cpu上執行real-time task.可以參考函數pull_rt_task，當一個rq中屬於
real-time的task已經執行完畢，就會透過函數pull_rt_task從該
rq中屬於rto_mask cpu mask 可以執行的處理器上，找出是否有一個處理器
有大於一個以上的real-time task，若有就會轉到目前這個執行完成
real-time task 的處理器上
而cpupri不同於Task本身有區分140個(0-139)
Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19).
CPU Priority本身有102個Priority (包括,-1為Invalid,
0為Idle,1為Normal,2-101對應到到Real-Time Priority 0-99).
參考函數convert_prio, Task Priority如果是 140就會對應到
CPU Idle,如果是>=100就會對應到CPU Normal,
若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.)
在實際的操作上,例如可以通過函數cpupri_find 傳入入一個要插入的Real-Time Task,
此時就會依據cpupri中pri_to_cpu選擇一個目前執行Real-Time Task
且該Task的優先順序比目前要插入的Task更低的處理器,
並通過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask.
可以參考kernel/sched_cpupri.c.
在初始化的過程中,通過函數sched_init調用函數init_defrootdomain,
對Root Domain和CPU Priority機制進行初始化.
*/
struct root_domain *rd;
/*Schedule Domain是基於多核心架構下的機制.
每個處理器都會有一個基礎的Scheduling Domain,
Scheduling Domain可以通過parent找到上一層的Domain,
或是通過child找到下一層的 Domain (NULL表示結尾.).
也可以通過span欄位,表示這個Domain所能覆蓋的處理器的範圍.
通常Base Domain會涵蓋系統中所有處理器的個數,
而Child Domain所能涵蓋的處理器個火速不超過它的Parent Domain.
而當進行Scheduling Domain 中的Task Balance,就會以該Domain所涵蓋的處理器為最大範圍.
同時,每個Schedule Domain都會包括一個或一個以上的
CPU Groups (結構為struct sched_group),並通過next欄位把
CPU Groups鏈接在一起(成為一個單向的Circular linked list),
每個CPU Group都會有變數cpumask來定義CPU Group
可以參考Linux Kernel文件 Documentation/scheduler/sched-domains.txt.
*/
struct sched_domain *sd;
struct callback_head *balance_callback;
unsigned char idle_balance;
/* For active balancing */
int active_balance;
int push_cpu;
struct cpu_stop_work active_balance_work;
/* cpu of this runqueue: */
int cpu;
int online;
/*當RunQueue中此值為1,表示這個RunQueue正在進行
Fair Scheduling的Load Balance,此時會調用stop_one_cpu_nowait
暫停該RunQueue所出處理器調度,
並通過函數active_load_balance_cpu_stop,
把Tasks從最忙碌的處理器移到Idle的處理器器上執行. */
int active_balance;
/*用以存儲目前進入Idle且負責進行Load Balance的處理器ID.
調用的流程為,在調用函數schedule時,
若該處理器RunQueue的nr_running為0 (也就是目前沒有
正在執行的Task),就會調用idle_balance,並觸發Load Balance */
int push_cpu;
/* cpu of this runqueue: */
/*用以存儲前運作這個RunQueue的處理器ID*/
int cpu;
/*為1表示目前此RunQueue有在對應的處理器上並執行 */
int online;
/*如果RunQueue中目前有Task正在執行,
這個值會等等於該RunQueue的Load Weight除以目前RunQueue中Task數目的均值.
(rq->avg_load_per_task = rq->load.weight / nr_running;).*/
unsigned long avg_load_per_task;
/*這個值會由Real-Time Scheduling Class調用函數update_curr_rt,
用以統計目前Real-Time Task執行時間的均值,
在這個函數中會以目前RunQueue的clock_task減去目前Task執行的起始時間,
取得執行時間的Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ).
在通過函數sched_rt_avg_update把這個Delta值跟原本RunQueue中的rt_avg值取平均值.
以運行的周期來看,這個值可反應目前系統中Real-Time Task平均被分配到的執行時間值 .*/
u64 rt_avg;
/* 這個值主要在函數sched_avg_update更新 */
u64 age_stamp;
/*這值會在處理Scheduling時,若判斷目前處理器runQueue沒有正在運行的Task,
就會通過函數idle_balance更新這個值為目前RunQueue的clock值.
可用以表示這個處理器何時進入到Idle的狀態 */
u64 idle_stamp;
/*會在有Task運行且idle_stamp不為0 (表示前一個轉檯是在Idle)時
以目前RunQueue的clock減去idle_stmp所計算出的Delta值為依據,
更新這個值， 可反應目前處理器進入Idle狀態的時間長短 */
u64 avg_idle;
/* This is used to determine avg_idle's max value */
u64 max_idle_balance_cost;
#endif
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
u64 prev_irq_time;
endif
#ifdef CONFIG_PARAVIRT
u64 prev_steal_time;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
u64 prev_steal_time_rq;
#endif
/* calc_load related fields */
/*用以記錄下一次計算CPU Load的時間,
初始值為目前的jiffies加上五秒與1次的Scheduling Tick的間隔
(=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))*
/
unsigned long calc_load_update;
/*等於RunQueue中nr_running與nr_uninterruptible的總和.
(可參考函式calc_load_fold_active).*/
long calc_load_active;
#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
int hrtick_csd_pending;
/*在函數it_rq_hrtick初始化RunQueue High-Resolution
Tick時， 此值設為0.
在函數hrtick_start中,會判斷目前觸發的RunQueue跟目前處理器所使用的RunQueue是否一致,
若是,就直接呼叫函數hrtimer_restart,反之就會依據RunQueue中hrtick_csd_pending的值,
如果hrtick_csd_pending為0,就會通過函數__smp_call_function_single讓RunQueue所在的另一個
處理器執行rq->hrtick_csd.func和函數 __hrtick_start.
並等待該處理器執行完畢後,才重新把hrtick_csd_pending設定為1.
也就是說, RunQueue的hrtick_csd_pending是用來作為SMP架構下,
由處理器A觸發處理器B執行*/
struct call_single_data hrtick_csd;
#endif
/*為gh-Resolution Tick的結構,會通過htimer_init初始化.*/
struct hrtimer hrtick_timer;
#endif
#ifdef CONFIG_SCHEDSTATS
/* latency stats */
/*為Scheduling Info.的統計結構,可以參考
include/linux/sched.h中的宣告. 例如在每次觸發
Schedule時,呼叫函式schedule_debug對上一個Task
的lock_depth進行確認(Fork一個新的Process 時,
會把此值預設為-1就是No-Lock,當呼叫
Kernel Lock時, 就會把Current Task的lock_depth加一.),
若lock_depth>=0,就會累加Scheduling Info.的bkl_count值,
用以代表Task Blocking的次數.*/
struct sched_info rq_sched_info;
/*可用以表示RunQueue中的Task所得到CPU執行
時間的累加值.
在發生Task Switch時,會透過sched_info_switch呼叫
sched_info_arrive並以目前RunQueue Clock值更新
Task 的sched_info.last_arrival時間,而在Task所分配時間
結束後,會在函式sched_info_depart中以現在的
RunQueue Clock值減去Task的sched_info.last_arrival
時間值,得到的 Delta作為變數rq_cpu_time的累
加值.*/
unsigned long long rq_cpu_time;
/* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
/* sys_sched_yield() stats */
/*用以統計呼叫System Call sys_sched_yield的次數.*/
unsigned int yld_count;
/* schedule() stats */
/*可用以統計觸發Scheduling的次數. 在每次觸發
Scheduling時,會透過函式schedule呼叫schedule_debug,
呼叫schedstat_inc對這變數進行累加.*/
unsigned int sched_count;
/*可用以統計進入到Idle Task的次數. 會在函式
pick_next_task_idle中,呼叫schedstat_inc對這變數進行
累加.*/
unsigned int sched_goidle;
/* try_to_wake_up() stats */
/*用以統計Wake Up Task的次數.*/
unsigned int ttwu_count;
/*用以統計Wake Up 同一個處理器Task的次數.*/
unsigned int ttwu_local;
/* BKL stats */
unsigned int bkl_count;
#endif
#ifdef CONFIG_SMP
struct llist_head wake_list;
#endif
#ifdef CONFIG_CPU_IDLE
/* Must be inspected within a rcu lock section */
struct cpuidle_state *idle_state;
#endif
};| 欄位 | 描述 |
|---|---|
| nr_running | 隊列上可運行進程的數目, 不考慮優先順序和調度類 |
| load | 提供了就緒隊列當前負荷的度量, 隊列的符合本質上與隊列上當前活動進程的數目成正比, 其中的各個進程又有優先順序作為權重. 每個就緒隊列的虛擬時鐘的速度等於該信息 |
| cpu_load | 用於跟蹤此前的負荷狀態 |
| cfs,rt 和dl | 嵌入的子就緒隊列, 分別用於完全公平調度器, 實時調度器和deadline調度器 |
| curr | 當前運行的進程的task_struct實例 |
| idle | 指向空閑進程的task_struct實例 |
| clock | 就緒隊列自身的時鐘 |
系統中所有的就緒隊列都在runqueues數組中, 該數組的每個元素分別對應於系統中的一個CPU, 如果是單處理器系統只有一個就緒隊列, 則數組就只有一個元素
內核中也提供了一些巨集, 用來獲取cpu上的就緒隊列的信息
// http://lxr.free-electrons.com/source/kernel/sched/sched.h?v=4.6#L716
DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() this_cpu_ptr(&runqueues)
#define task_rq(p) cpu_rq(task_cpu(p))
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
#define raw_rq() raw_cpu_ptr(&runqueues)
3.3.2 CFS公平調度器的就緒隊列cfs_rq
在系統中至少有一個CFS運行隊列，其就是根CFS運行隊列，而其他的進程組和進程都包含在此運行隊列中，不同的是進程組又有它自己的CFS運行隊列，其運行隊列中包含的是此進程組中的所有進程。當調度器從根CFS運行隊列中選擇了一個進程組進行調度時，進程組會從自己的CFS運行隊列中選擇一個調度實體進行調度(這個調度實體可能為進程，也可能又是一個子進程組)，就這樣一直深入，直到最後選出一個進程進行運行為止
對於 struct cfs_rq 結構沒有什麼好說明的，只要確定其代表著一個CFS運行隊列，並且包含有一個紅黑樹進行選擇調度進程即可。
/* CFS-related fields in a runqueue */
/* CFS調度的運行隊列，每個CPU的rq會包含一個cfs_rq，而每個組調度的sched_entity也會有自己的一個cfs_rq隊列 */
struct cfs_rq {
/* CFS運行隊列中所有進程的總負載 */
struct load_weight load;
/*
* nr_running: cfs_rq中調度實體數量
* h_nr_running: 只對進程組有效，其下所有進程組中cfs_rq的nr_running之和
*/
unsigned int nr_running, h_nr_running;
u64 exec_clock;
/*
* 當前CFS隊列上最小運行時間，單調遞增
* 兩種情況下更新該值:
* 1、更新當前運行任務的累計運行時間時
* 2、當任務從隊列刪除去，如任務睡眠或退出，這時候會查看剩下的任務的vruntime是否大於min_vruntime，如果是則更新該值。
*/
u64 min_vruntime;
#ifndef CONFIG_64BIT
u64 min_vruntime_copy;
#endif
/* 該紅黑樹的root */
struct rb_root tasks_timeline;
/* 下一個調度結點(紅黑樹最左邊結點，最左邊結點就是下個調度實體) */
struct rb_node *rb_leftmost;
/*
* 'curr' points to currently running entity on this cfs_rq.
* It is set to NULL otherwise (i.e when none are currently running).
* curr: 當前正在運行的sched_entity（對於組雖然它不會在cpu上運行，但是當它的下層有一個task在cpu上運行，那麼它所在的cfs_rq就把它當做是該cfs_rq上當前正在運行的sched_entity）
* next: 表示有些進程急需運行，即使不遵從CFS調度也必須運行它，調度時會檢查是否next需要調度，有就調度next
*
* skip: 略過進程(不會選擇skip指定的進程調度)
*/
struct sched_entity *curr, *next, *last, *skip;
#ifdef CONFIG_SCHED_DEBUG
unsigned int nr_spread_over;
#endif
#ifdef CONFIG_SMP
/*
* CFS load tracking
*/
struct sched_avg avg;
u64 runnable_load_sum;
unsigned long runnable_load_avg;
#ifdef CONFIG_FAIR_GROUP_SCHED
unsigned long tg_load_avg_contrib;
#endif
atomic_long_t removed_load_avg, removed_util_avg;
#ifndef CONFIG_64BIT
u64 load_last_update_time_copy;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
* h_load = weight * f(tg)
*
* Where f(tg) is the recursive weight fraction assigned to
* this group.
*/
unsigned long h_load;
u64 last_h_load_update;
struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */
#ifdef CONFIG_FAIR_GROUP_SCHED
/* 所屬於的CPU rq */
struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
/*
* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
* a hierarchy). Non-leaf lrqs hold other higher schedulable entities
* (like users, containers etc.)
*
* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
* list is used during load balance.
*/
int on_list;
struct list_head leaf_cfs_rq_list;
/* 擁有該CFS運行隊列的進程組 */
struct task_group *tg; /* group that "owns" this runqueue */
#ifdef CONFIG_CFS_BANDWIDTH
int runtime_enabled;
u64 runtime_expires;
s64 runtime_remaining;
u64 throttled_clock, throttled_clock_task;
u64 throttled_clock_task_time;
int throttled, throttle_count;
struct list_head throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};
3.3.3 實時進程就緒隊列rt_rq
/* Real-Time classes' related field in a runqueue: */
struct rt_rq {
struct rt_prio_array active;
unsigned int rt_nr_running;
unsigned int rr_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
struct {
int curr; /* highest queued rt task prio */
#ifdef CONFIG_SMP
int next; /* next highest */
#endif
} highest_prio;
#endif
#ifdef CONFIG_SMP
unsigned long rt_nr_migratory;
unsigned long rt_nr_total;
int overloaded;
struct plist_head pushable_tasks;
#ifdef HAVE_RT_PUSH_IPI
int push_flags;
int push_cpu;
struct irq_work push_work;
raw_spinlock_t push_lock;
#endif
#endif /* CONFIG_SMP */
int rt_queued;
int rt_throttled;
u64 rt_time;
u64 rt_runtime;
/* Nests inside the rq lock: */
raw_spinlock_t rt_runtime_lock;
#ifdef CONFIG_RT_GROUP_SCHED
unsigned long rt_nr_boosted;
struct rq *rq;
struct task_group *tg;
#endif
};
3.3.4 deadline就緒隊列dl_rq
/* Deadline class' related fields in a runqueue */
struct dl_rq {
/* runqueue is an rbtree, ordered by deadline */
struct rb_root rb_root;
struct rb_node *rb_leftmost;
unsigned long dl_nr_running;
#ifdef CONFIG_SMP
/*
* Deadline values of the currently executing and the
* earliest ready task on this rq. Caching these facilitates
* the decision wether or not a ready but not running task
* should migrate somewhere else.
*/
struct {
u64 curr;
u64 next;
} earliest_dl;
unsigned long dl_nr_migratory;
int overloaded;
/*
* Tasks on this rq that can be pushed away. They are kept in
* an rb-tree, ordered by tasks' deadlines, with caching
* of the leftmost (earliest deadline) element.
*/
struct rb_root pushable_dl_tasks_root;
struct rb_node *pushable_dl_tasks_leftmost;
#else
struct dl_bw dl_bw;
#endif
};
3.4 調度實體
我們前面提到, 調度器不限於調度進程, 還可以調度更大的實體, 比如實現組調度: 可用的CPU時間首先在一半的進程組(比如, 所有進程按照所有者分組)之間分配, 接下來分配的時間再在組內進行二次分配.
這種一般性要求調度器不直接操作進程, 而是處理可調度實體, 因此需要一個通用的數據結構描述這個調度實體,即seched_entity結構, 其實際上就代表了一個調度對象，可以為一個進程，也可以為一個進程組。對於根的紅黑樹而言，一個進程組就相當於一個調度實體，一個進程也相當於一個調度實體。
我們可以先看看sched_entity結構，其定義在include/linux/sched.h, 如下：
3.4.1 sched_entity調度實體
/* 一個調度實體(紅黑樹的一個結點)，其包含一組或一個指定的進程，包含一個自己的運行隊列，一個父親指針，一個指向需要調度的運行隊列指針 */
struct sched_entity {
/* 權重，在數組prio_to_weight[]包含優先順序轉權重的數值 */
struct load_weight load; /* for load-balancing */
/* 實體在紅黑樹對應的結點信息 */
struct rb_node run_node;
/* 實體所在的進程組 */
struct list_head group_node;
/* 實體是否處於紅黑樹運行隊列中 */
unsigned int on_rq;
/* 開始運行時間 */
u64 exec_start;
/* 總運行時間 */
u64 sum_exec_runtime;
/* 虛擬運行時間，在時間中斷或者任務狀態發生改變時會更新
* 其會不停增長，增長速度與load權重成反比，load越高，增長速度越慢，就越可能處於紅黑樹最左邊被調度
* 每次時鐘中斷都會修改其值
* 具體見calc_delta_fair()函數
*/
u64 vruntime;
/* 進程在切換進CPU時的sum_exec_runtime值 */
u64 prev_sum_exec_runtime;
/* 此調度實體中進程移到其他CPU組的數量 */
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
/* 用於統計一些數據 */
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/* 代表此進程組的深度，每個進程組都比其parent調度組深度大1 */
int depth;
/* 父親調度實體指針，如果是進程則指向其運行隊列的調度實體，如果是進程組則指向其上一個進程組的調度實體
* 在 set_task_rq 函數中設置
*/
struct sched_entity *parent;
/* 實體所處紅黑樹運行隊列 */
struct cfs_rq *cfs_rq;
/* 實體的紅黑樹運行隊列，如果為NULL表明其是一個進程，若非NULL表明其是調度組 */
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
/*
* Per entity load average tracking.
*
* Put into separate cache line so it does not
* collide with read-mostly values above.
*/
struct sched_avg avg ____cacheline_aligned_in_smp;
#endif
};在struct sched_entity結構中，值得我們註意的成員是
| 欄位 | 描述 |
|---|---|
| load | 指定了權重, 決定了各個實體占隊列總負荷的比重, 計算負荷權重是調度器的一項重任, 因為CFS所需的虛擬時鐘的速度最終依賴於負荷, 權重通過優先順序轉換而成，是vruntime計算的關鍵 |
| run_node | 調度實體在紅黑樹對應的結點信息, 使得調度實體可以在紅黑樹上排序 |
| sum_exec_runtime | 記錄程式運行所消耗的CPU時間, 以用於完全公平調度器CFS |
| on_rq | 調度實體是否在就緒隊列上接
  更多相關文章
一周排行
 所有分類
|