文章說明：

• Linux內核版本：5.0

• 架構：ARM64

• 參考資料及圖片來源：《奔跑吧Linux內核》

• Linux 5.0內核源碼注釋倉庫地址：

  zhangzihengya/LinuxSourceCode_v5.0_study (github.com)

進程調度的概念比較簡單，假設在一個單核處理器的系統中，同一時刻只有一個進程可以擁有處理器資源，那么其他的進程只能在就緒隊列（runqueue）中等待，等到處理器空閑了之后才有機會獲取處理器資源來運行。在這種場景下，操作系統就需要從眾多的就緒進程中選擇—個最合適的進程來運行，這個就是進程調度器（scheduler）要做的事情。調度器產生的最主要原因是提高處理器的利用率（CPUutilization）

1. 進程優先級和權重

Linux操作系統最早采用nice值來調整進程的優先級。nice值的思想是要對其他進程友好，降低優先級來支持其他進程消耗更多的處理器時間，它的范圍是-20~+19，默認值是0。nice值越大，優先級反而越低; nice值越低，優先級越高。nice值-20表示這個進程是非常重要的，優先級最高；而nice值19則表示允許其他進程比這個線程優先享有寶貴的CPU時間，這也是nice值的由來。

內核使用0~139的數值表示進程的優先級，數值越小，優先級越高。優先級0-99給實時進程使用， 100-139給普通進程使用。另外，在用戶空間中有一個傳統的變量nice，它用于映射普通進程的優先級，即100-139。

優先級在Linux內核中的劃分方式如下：

• 普通進程的優先級：100~139
• 實時進程的優先級：0~99
• deadline進程的優先級：-1

task_struct 數據結構中使用4個成員描述進程的優先級：

struct task_struct {...// 動態優先級，是調度類考慮的優先級// 0~139，值越小優先級越高int				prio;// 靜態優先級，在進程啟動時分配。內核不存儲 nice 值，取而代之的是 static_prio// NICE_TO_PRIO 宏可以把nice值轉換成 static_prio// static_prio 不會隨著時間而改變，用戶可以通過 nice 或 sched_setscheduler 等系統調用來修改該值// 100~139，值越小優先級越高int				static_prio;// 基于 static_prio 和調度策略計算出來的優先級，在創建進程時會繼承父進程的 normal_prio// 對于普通進程，normal_prio 等同于 static_prio// 對于實時進程，會根據 rt_priority 重新計算 normal_prio，詳見 effective_prio 函數// 0~139，值越小優先級越高int				normal_prio;// 實時進程的優先級// 0~99，值越大越高unsigned int			rt_priority;...
}

在Linux內核中除了使用優先級來表示進程的輕重緩急之外，在實際調度器里還使用權重的概念來表示進程的優先級。為了計算方便，內核約定nice值為0的進程的權重值為1024，其他nice值對應的進程的權重值可以通過查表的方式來獲取，內核預先計算好了一個表 sched_prio_to_weight[40]，表中下標對應nice值[-20~19]。

const int sched_prio_to_weight[40] = {/* -20 */     88761,     71755,     56483,     46273,     36291,/* -15 */     29154,     23254,     18705,     14949,     11916,/* -10 */      9548,      7620,      6100,      4904,      3906,/*  -5 */      3121,      2501,      1991,      1586,      1277,/*   0 */      1024,       820,       655,       526,       423,/*   5 */       335,       272,       215,       172,       137,/*  10 */       110,        87,        70,        56,        45,/*  15 */        36,        29,        23,        18,        15,
};

2. 調度策略

進程調度依賴于調度策略（schedule policy），Linux內核把相同類型的調度策略抽象成調度類 （schedule class）。不同類型的進程采用不同的調度策略，目前Linux內核中默認實現了5種調度類，分別是stop、deadline、realtime、CFS和idle，它們分別使用sched_class來定義，并且通過next指針串聯在—起，如下圖所示：

Linux內核支持的5個調度類的異同如下表所示：

相應的源碼定義如下：

// 調度策略
// 分時調度策略，非實時進程的默認調度策略，Linux內核沒有實現這類調度策略
#define SCHED_NORMAL		0
// 先進先出調度策略
#define SCHED_FIFO		1
// 循環調度策略，表示優先級相同的進程以循環分享時間的方式來運行
#define SCHED_RR		2
// 批處理調度，這個調度策略表示讓調度器認為該進程是 CPU 消耗型的，因此，調度器對這類進程的喚醒懲罰比較小。
// 在 Linux 內核里，該類調度策略表示使用 CFS
#define SCHED_BATCH		3
/* SCHED_ISO: reserved but not implemented yet */
// 空閑調度策略，用于運行低優先級的任務
#define SCHED_IDLE		5
// 用于調度有嚴格時間要求的實時進程
#define SCHED_DEADLINE		6

3. 調度算法

調度算法	時間復雜度	算法思想	缺點
基于優先級的調度算法	O(n)	分配給進程時間片，時間片表示進程調度進來與調度出去之間所能持續運行的時間長度	分配多長的時間片是一個需要考慮的問題，時間片過長的話會導致交互型的進程得 不到及時響應，時間片過短的話會增大進程切換帶來的處理器消耗
多級反饋隊列算法	O(1)	把進程按照優先級分成多個隊列，相同優先級的進程在同一個隊列中	參數如何確定和優化。如系統需要設計多少個優先級隊列? 時間片應該設置成多少?
基于多級反饋隊列的調度算法	O(1)	每個CPU各自維護一個屬于自己的就緒隊列，這樣減少了鎖的爭用。就緒隊列由兩個優先級數組組成，即活躍（active）優先級數組和過期（expired）優先級數組，每個優先級數組包含MAX_PRIO（140）個優先級隊列，也就是每個優先級對應一個隊列，活躍優先級數組中所有進程用完了時間片之后，活躍優先級數組和過期優先級數組會進行互換
CFS	O(1)	CFS拋棄以前固定時間片和固定調度周期的算法，而采用進程權重值的比例來量化和計算實際運行時間。引入虛擬時間（vmntime）的概念，每個進程的虛擬時間是實際運行時間相對于nice值為0的進程的權重的比值。CFS總是選擇虛擬時間最短的進程