所謂的運(yùn)行隊列到底長什么樣子、新進(jìn)程是如何被加入進(jìn)來的、調(diào)度是如何選擇一個新進(jìn)程的、新進(jìn)程又如何被切換到 CPU 上運(yùn)行的，這些細(xì)節(jié)咱們都沒提到。今天就來展開看看這些進(jìn)程運(yùn)行背后的原理。

通過今天的文章，你將對以下兩個問題有個更深入的理解。

• 進(jìn)程不主動釋放 CPU 的話，每次調(diào)度最少能運(yùn)行多久？

• 進(jìn)程的 nice 值代表的是優(yōu)先級嗎，高優(yōu)先級是否能搶占低優(yōu)先級的 CPU ？

一、CPU 核的運(yùn)行隊列

進(jìn)程創(chuàng)建完后需要被添加到運(yùn)行隊列中，那我們就來看看這個運(yùn)行隊列究竟是長啥樣子的。

關(guān)于運(yùn)行隊列，我們得先從 CPU 的物理結(jié)構(gòu)講起。現(xiàn)代主流的服務(wù)器都是多 CPU 架構(gòu)，每顆 CPU 又會包含多個物理核，每個物理核又可以超線程出多個邏輯核來供操作系統(tǒng)管理和使用。

拿某臺線上的服務(wù)器 32 核的服務(wù)器來舉例，該服務(wù)器實際上是有 2 顆 CPU，每顆 CPU 包含了 8 個物理核心。這樣總共包含的是 16 個物理核。

因為該服務(wù)器每個物理核心又可以當(dāng)成兩個超線程來用，所以通過 top 命令可以看到有 32 “核”，這里看到的核其實是邏輯核。

為了讓每個 CPU 核(邏輯核)都能更好地參與進(jìn)程任務(wù)處理，不需要考慮和其他處理器競爭的問題，也能充分利用本地硬件 Cache 來對訪問加速。Linux 內(nèi)核會為每個 CPU 核都分配一個運(yùn)行隊列，也就是 struct rq 內(nèi)核對象。

內(nèi)核定義是通過 DEFINE_PER_CPU 來定義 Per CPU 變量的。其中運(yùn)行隊列使用的是 DEFINE_PER_CPU_SHARED_ALIGNED 宏。

DEFINE_PER_CPU_SHARED_ALIGNED 宏接收兩個參數(shù)，第一參數(shù)可以理解為是數(shù)組類型，第二個參數(shù)可以理解為數(shù)組名。

這個宏執(zhí)行后的效果是初始化出來一個 runqueues 數(shù)組，在該數(shù)組中為每一個 CPU 核都配置了一個運(yùn)行隊列（struct rq）對象。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??

那么這個運(yùn)行隊列 struct rq 又是如何實現(xiàn)的呢？Linux 操作系統(tǒng)進(jìn)程調(diào)度有多種多樣的需求。例如有的需要按優(yōu)先級來實時調(diào)度，只要高優(yōu)先級的進(jìn)程一就緒，就需要立即搶占 CPU 資源。有的不需要搶占這么頻繁，對實時性要求沒那么高，但需要進(jìn)程公平地被分配 CPU 資源就可以了。

為了滿足各種復(fù)雜的調(diào)度策略，內(nèi)核在 struct rq 中實現(xiàn)了不同的調(diào)度類（Scheduling Class）。不同的調(diào)度需求的進(jìn)程放在不同的調(diào)度類中。

2.1 實時調(diào)度器

在實時類調(diào)度需求中，一般內(nèi)核線程如 migration 一般對實時性的要求比較高，這類進(jìn)程需要及時調(diào)度分配 CPU。

在這種調(diào)度算法中，優(yōu)先級是最主要考慮的因素。高優(yōu)先級的進(jìn)程可以搶占低優(yōu)先級進(jìn)程 CPU 資源來運(yùn)行。同一個優(yōu)先級的進(jìn)程按照先到先服務(wù)（SCHED_FIFO）或者時間片輪轉(zhuǎn)（SCHED_RR）。

這種調(diào)度方式實現(xiàn)起來比較簡單，只需要定義一些優(yōu)先級，并為每個優(yōu)先級各分配一個鏈表當(dāng)隊列即可，也叫多優(yōu)先級隊列。

我們來看下代碼實現(xiàn)：

其中 rt_prio_array 就是多優(yōu)先級隊列的實現(xiàn)，我們來看下它的定義。

其中 MAX_RT_PRIO 定義在 include/linux/sched/rt.h 文件中，它的值為 100。也就是說有 100 個對應(yīng)不同優(yōu)先級的隊列。

2.2 完全公平調(diào)度器

Linux 主要是用來運(yùn)行用戶進(jìn)程的。對于絕大部分的用戶進(jìn)程來說，對實時性的要求沒那么高。如果因為優(yōu)先級的問題頻繁地發(fā)生搶占，進(jìn)而導(dǎo)致過多的進(jìn)程上下文切換的開銷，對系統(tǒng)整體的性能是有不利的影響的。

所以用戶進(jìn)程采用的是不同的調(diào)度算法。Linux 2.6.23 之后采用了完全公平調(diào)度器（Completely Fair Scheduler，CFS）作為對用戶進(jìn)程的調(diào)度算法。CFS 調(diào)度器的核心思想是強(qiáng)調(diào)讓每個進(jìn)程盡量公平地分配到 CPU 時間即可，而不是實時搶占。。

舉個例子，假設(shè)一個 CPU 上有兩個任務(wù)需要執(zhí)行，那么每個任務(wù)都將分配 50% 的 CPU 時間，以保障公平性。假如有 N 個任務(wù)，CPU 盡可能分配給每個進(jìn)程 1/N 的處理時間。

公平調(diào)度算法在實現(xiàn)上引入了一個虛擬時間的概念。一旦進(jìn)程運(yùn)行虛擬時間就會增加。盡量讓虛擬時間最小的進(jìn)程運(yùn)行，誰小了就要多運(yùn)行，誰大了就要少獲得 CPU。最后盡量保證所有進(jìn)程的虛擬時間相等，動態(tài)地達(dá)到公平分配 CPU 的目的。

但是在數(shù)據(jù)結(jié)構(gòu)的組織上，有一個小小的難點要解決。那就是當(dāng)所有程序運(yùn)行起來后，每一個進(jìn)程的虛擬時間是不斷地在變化的。如何動態(tài)管理這些虛擬時間不斷在變化的進(jìn)程，快速把虛擬時間最少的進(jìn)程找出來。

在 CFS 調(diào)度器中采用的解決辦法是使用的是紅黑樹來管理任務(wù)。紅黑樹把進(jìn)程按虛擬運(yùn)行時間從小到大排序。越靠樹的左側(cè)，進(jìn)程的運(yùn)行虛擬時間越小。越靠樹的右側(cè)，進(jìn)程的運(yùn)行虛擬時間就越大。這樣每當(dāng)想挑選可運(yùn)行進(jìn)程時，直接從樹的最左側(cè)選擇節(jié)點就可以了。

以下是 cfs_rq 對象的定義，其中的 rb_xx 就是紅黑樹相關(guān)的定義。

另外完全公平調(diào)度器實現(xiàn)上考慮到的兩個細(xì)節(jié)這里我和大家提一下。

第一個就是照顧性能開銷。

前面我們說過，進(jìn)程上下文切換會導(dǎo)致額外的 CPU 浪費。假如被選中的進(jìn)程剛運(yùn)行沒多久，它的虛擬時間時間就比另一個進(jìn)程小了。這時候難道要馬上換另一個進(jìn)程處理么？出于減少頻繁切換進(jìn)程所帶來的成本考慮，顯然并不應(yīng)該這樣。

所以，Linux 會保證選擇到的進(jìn)程一個最短的運(yùn)行時間，這個時間由 sched_min_granularity_ns 這個內(nèi)核參數(shù)來控制。

上面是飛哥阿里云服務(wù)器的默認(rèn)配置。這表示進(jìn)程至少會運(yùn)行 10 ms。當(dāng)然了，如果進(jìn)程因為等待網(wǎng)絡(luò)、磁盤等資源時主動放棄那另算。

第二個就是權(quán)重考量。

在實踐中可能確實有進(jìn)程需要多分配一點運(yùn)行時間。Linux 采用的做法在是上述絕對公平算法基礎(chǔ)上再為進(jìn)程引入一個權(quán)重。

通過給每個進(jìn)程設(shè)置一定的權(quán)重，各個進(jìn)程按權(quán)重的比例公平地來分配 CPU 時間。如果進(jìn)程的權(quán)重高，那就按比例多獲得一點 CPU，權(quán)重低獲得的比例就低。

這個權(quán)重就是 Linux 進(jìn)程的 nice 值，也就是我們平時 top 命令結(jié)果中看到的 ni 這一列。nice 范圍為 -20（最高權(quán)重）到 19（最低權(quán)重）。

現(xiàn)在有很多人都把 nice 理解成了優(yōu)先級，這是不太恰當(dāng)?shù)?。?yōu)先級強(qiáng)調(diào)的是搶占，高優(yōu)先級比低優(yōu)先級有優(yōu)先獲得 CPU 的權(quán)利。而用戶進(jìn)程中的 nice 值強(qiáng)調(diào)的是獲取到 CPU 運(yùn)行時間的比例，理解成權(quán)重更合適。

三、新進(jìn)程之初始化

fork 創(chuàng)建時主要是調(diào)用了 copy_process 對新進(jìn)程的 task_struct 進(jìn)行各種初始化。在初始化的過程中，也涉及到幾個進(jìn)程調(diào)度相關(guān)的變量的初始化，這里我們專門來看一下。

在創(chuàng)建進(jìn)程 copy_process 時會調(diào)用 sched_fork 來完成調(diào)度相關(guān)的初始化。

在上面代碼中最重要的一行是 p->sched_class = &fair_sched_class。這一行表示這個進(jìn)程將會被完全公平調(diào)取策略進(jìn)行調(diào)度。其中 fair_sched_class 是一個全局對象，代表完全公平調(diào)度器。它實現(xiàn)了調(diào)取器類中要求的添加任務(wù)隊列、刪除任務(wù)隊列、從隊列中選擇進(jìn)程等方法。

另外就是把進(jìn)程的虛擬運(yùn)行時間初始化為 0，遷移次數(shù)初始化為 0 。

文章篇幅過長，下文繼續(xù)講解

原文作者：開發(fā)內(nèi)功修煉