萬字長文，錘它！揭祕 Linux 進程調度器

準備知識

想深入理解操作系統的進程調度，需要先獲得一些準備知識，這樣後面就不懵圈啦：

調度的概念

科技源自生活，調度系統絕對不是計算機領域的專利，現實生活中調度無處不在：

“

調度是爲了解決資源和需求之間的不匹配問題，現實往往是資源少 & 需求多，計算機領域也是如此。

在操作系統中 CPU 資源是有限的，需要使用 CPU 的進程數量是不確定的，並且大部分情況下進程數量遠大於 CPU 數量，如何解決不匹配問題就是進程調度核心：

操作系統分類

操作系統的種類非常多，本身上是硬件層和應用層之間的中間層，對上與應用程序進行交互，對下實現硬件資源的管理。

“

批處理是指用戶將一批作業提交給操作系統後就不再幹預，由操作系統控制它們自動運行，這種採用批量處理作業任務的操作系統稱爲批處理操作系統，不具有交互性，用戶無法干預任務的運行。

“

實時系統最大的特點在於計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯，強實時系統一般應用在航空航天、導彈導航制導、核工業等領域。

“

分時系統將計算機系統資源（比如 CPU）進行時間上的分割，每個時間段稱爲一個時間片，每個用戶依次輪流使用時間片，由於時間間隔很短，每個用戶的感覺就像他獨佔計算機一樣，從而有效增加資源的使用率，提高用戶交互體驗。

Linux 屬於分時系統，是互聯網服務器的主流操作系統，重點研究它就行！

進程分類

根據進程運行時的狀態，可以分爲：

“

在進程佔用 CPU 期間頻繁有 IO 操作，出現 IO 阻塞等待情況，比如負責監聽 socket 的進程，真正使用 CPU 進行計算的時間並不多。

“

在進程佔用 CPU 期間基本都在進行計算，很少進行 IO 操作，期間對 CPU 的真實使用率很高。

進程調度器需要根據進程是 IO 密集型還是 CPU 密集型會採用不同的策略。

在調度器中往往需要對 IO 密集型進程進行獎勵來提高其調度優先級，對 CPU 密集型進程進行懲罰降低其調度優先級。

對進程的獎懲策略是調度器的一項核心工作，希望大家務必理解：

“

交互進程往往伴隨較多的 IO 操作，同時也是響應時間敏感的任務，鼠標點一下半天沒響應，想想就很糟糕，因此屬於高優先級進程。

“

非交互進程往往是純 CPU 計算，用戶是無感知的，所以對響應時間的要求並沒有那麼高，屬於低優先級進程。

進程優先級

根據進程的重要性，可以分爲：

“

在操作系統中有很多進程，實時進程是相對重要的，需要保證其 CPU 佔用優先級，普通進程並不需要額外照顧。

實時進程和普通進程的進程優先級不同，調度器都會根據優先級來確定進程的 CPU 優先權和運行時間。

在 Linux 中影響優先級的兩個因素：Nice 謙讓值和 Priority 權重值。

PR 值由內核來確定，用戶可以修改 Nice 謙讓值，進而干預 PR 值：

nice 值也被稱爲謙讓值，數值越大越謙讓，會哭的孩子有奶喫，總謙讓優先級肯定低了：

非搶佔和搶佔式

根據進程任務在佔用 CPU 時，使用權是否會被奪取分爲：

“

進程任務一旦佔用 CPU 只有當任務完成或者因爲某些原因主動釋放 CPU，除上述兩種情況外不能被其他進程奪走

“

進程任務佔用 CPU 期間可以被其他進程奪走，具體由操作系統調度器決定下一個佔用 CPU 的進程

Linux 採用搶佔式調度，其可以提高 CPU 利用率、降低進程的響應時間等，同時也增加了切換進程時的開銷，各有利弊。

調度器設計思路

設計目標

有兩個指標需要重視：

“

進程任務從開始排隊等待獲取 CPU 資源直到任務完成的時間差，就像超市排隊結賬時從開始排隊到結算完成離開的時間差。

“

進程任務從開始排隊等待獲取 CPU 資源直到開始使用 CPU 的時間差，就像超市排隊結賬時從開始排隊到輪到結算的時間差。

綜合來說：

只有做到這幾點，調度器纔可能在週轉時間和響應時間上得到一個良好的表現。

設計實現

要實現一個調度器，主要包括兩個核心部分：

算法更多是一種思想，調度器基於某種調度算法進行工程化實現，捋清楚二者的關係對於後續內容的理解將大有裨益。

本章重點

調度算法

調度算法也經歷了從簡單到複雜的演進，到目前爲止也沒有哪種調度算法是萬能的，拋開場景來評判調度算法優劣並不明智。

以下介紹的主要是調度算法的思想，工程上使用的調度算法往往是其中一種或者幾種的變形，更加複雜。

先來先服務 FCFS

先來先服務 First Come First Service 可以說是最早最簡單的調度算法，哪個進程先來就先讓它佔用 CPU，釋放 CPU 之後第二個進程再使用，依次類推。

在 FCFS 中優先被調度的進程如果耗時很長，後續進程都必須要等待這個大 CPU 消耗的進程，最終導致週轉時間直線拉昇，也就是護航效應。

最短任務優先 SJF

最短任務優先 Shortest Job First 的思想是當多個進程同時出現時，優先安排執行時間最短的任務，然後是執行時間次短，以此類推。

SJF 可以解決 FCFS 中同時到達進程執行時間不一致帶來的護航效應問題：

相比於 FCFS 可能的執行順序是 A->C->B 來說，週轉時間和響應時間都得到很大的改善。

SJF 的算法思想有些理想化，但並非一無是處，升級改進下也有用武之地：

搶佔式最短任務優先 PSJF

SJF 算法最具啓發的地方在於優先調度執行時間短的任務來解決護航效應，但是該算法屬於非搶佔式調度，對於先後到達且執行時間差別較大的場景也束手無策。

當向 SJF 算法增加搶佔調度時能力就大大增強了，這就是 PSJF(Preemptive Shortest Job First) 算法。

搶佔機制有效削弱了護航效應，週轉時間和響應時間都降低了許多，但是還遠不夠完美。

PSJF 算法對於進程 A 來說卻不友好，進程 A 在被搶佔之後只能等待 B 和 C 運行完成後，此時如果再來短任務 DEF 都會搶佔 A，就會產生飢餓效應。

PSJF 算法是基於對任務運行時間長短來進行調度的，但在調度前任務的運行時間是未知的，因此首要問題是通過歷史數據來預測運行時間。

時間片輪轉 RR

時間片輪轉 RR(Round-Robin) 將 CPU 執行時間按照時鐘脈衝進行切割稱爲時間切片 Time-Slice，一個時間切片是時鐘週期的數倍，時鐘週期和 CPU 的主頻呈倒數關係。

“

比如 CPU 的主頻是 1000hz，則時鐘週期 TimeClick=1ms， Time Slice = n*Time Click，時間切片可以是 2ms/4ms/10ms 等。

在一個時間片內 CPU 分配給一個進程，時間片耗盡則調度選擇下一個進程，如此循環。

進程往往需要多個循環獲取多次時間片才能完成任務，因此需要操作系統記錄上一次的數據，等進程下一次被分配時間片時再拿出來，這就是傳說中的上下文 Context。

進程上下文被存儲和拿出的過程被稱爲上下文切換 Context Switch，上下文切換是比較消耗資源的，因此時間片的劃分就顯得很重要：

RR 算法在保障了多個進程都能佔用 CPU，屬於公平策略的一種，但是 RR 算法將原本可以一次運行完的任務切分成多個部分來完成，從而拉昇了週轉時間。

RR 算法也非銀彈，但是響應時間和公平性得到了有效保障，是個非常有意義的算法模型。

多級反饋隊列 MLFQ

多級反饋隊列 (Multi-Level Feedback Queue) 嘗試去同時解決響應時間和週轉時間兩個問題，具體做法：

上述是 MLFQ 算法的基本規則，在實際應用中仍然會有一些問題：

針對上述問題 MLFQ 還需增加幾個補丁：

MLFQ 的算法思想在 1962 年被提出，其作者也獲得了圖靈獎，可謂是影響深遠。

在樸素 MLFQ 算法基礎上出現一些變種，通過工程實現和經驗配置最終被使用到操作系統中，成爲真正的工業級進程調度器。

Linux 進程調度器

Linux 的進程調度器是不斷演進的，先後出現過三種里程碑式的調度器：

O(n) 屬於早期版本在 pick next 過程是需要遍歷進程任務隊列來實現，O(1) 版本性能上有較大提升可以實現 O(1) 複雜度的 pick next 過程。

CFS 調度器可以說是一種 O(logn) 調度器，但是其算法思想相比前兩種有些不同，並且設計實現上也更加輕量，一直被 Linux 內核沿用至今。

調度器設計核心

要理解這些複雜的調度器設計，我們必須要有一個核心主線，再去理解精髓。

調度器需要解決的關鍵問題：

事實上，調度器在設計實現上考慮的問題還有很多，篇幅所限只列舉幾個公共問題。

O(n) 調度器

O(n) 調度器採用一個全局隊列 runqueue 作爲核心數據結構，具備以下特點：

在 Linux 中進程使用 task_struct 結構體來表示，其中有個 counter 表示進程剩餘的 CPU 時間片：

struct task_struct {
    long counter;
    long nice;
    unsigned long policy;
    int processor;
    unsigned long cpus_runnable, cpus_allowed;
}

counter 值在調度週期開始時被賦值，隨着調度的進行遞減，直至 counter=0 表示無可用 CPU 時間，等待下一個調度週期。

O(n) 調度器中調度權重是在 goodness 函數中完成計算的：

static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
        int weight;
        weight = -1;
        /*進程可以設置調度策略爲SCHED_YIELD即“禮讓”策略，這時候它的權值爲-1,權值相當低*/
        if (p->policy & SCHED_YIELD)
                goto out;

        /*
         * Non-RT process - normal case first.
         */

        /*對於調度策略爲SCHED_OTHER的進程，沒有實時性要求，它的權值僅僅取決於
         * 時間片的剩餘和它的nice值，數值上nice越小，則優先級越高，總的權值 = 時間片剩餘 + (20 - nice)
         * */
        if (p->policy == SCHED_OTHER) {
                /*
                 * Give the process a first-approximation goodness value
                 * according to the number of clock-ticks it has left.
                 *
                 * Don't do any other calculations if the time slice is
                 * over..
                 */
                weight = p->counter;
                if (!weight)
                        goto out;
                        
#ifdef CONFIG_SMP
                /* Give a largish advantage to the same processor...   */
                /* (this is equivalent to penalizing other processors) */
                if (p->processor == this_cpu)
                        weight += PROC_CHANGE_PENALTY;
#endif

                /* .. and a slight advantage to the current MM */
                if (p->mm == this_mm || !p->mm)
                        weight += 1;
                weight += 20 - p->nice;
                goto out;
        }

        /*
         *對於實時進程，也就是SCHED_FIFO或者SCHED_RR調度策略，
         *具有一個實時優先級，總的權值僅僅取決於該實時優先級，
         *總的權值 = 1000 + 實時優先級。
         * */
        weight = 1000 + p->rt_priority;
out:
        return weight;
}

從代碼可以看到：

#if HZ < 200
#define TICK_SCALE(x)        ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x)        ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x)        (x)
#elif HZ < 1600
#define TICK_SCALE(x)        ((x) << 1)
#else
#define TICK_SCALE(x)        ((x) << 2)
#endif

#define NICE_TO_TICKS(nice)        (TICK_SCALE(20-(nice))+1)

NICE_TO_TICKS 是個宏函數，根據不同的調度頻率 HZ 有對應的 TICK_SCALE 宏定義，這樣就解決了不同優先級的進程的時間片分配問題。

O(n) 調度器對實時進程和普通進程採用不同的調度策略：

在 runqueue 中搜索下一個合適的進程是基於動態優先級來實現的，動態優先級最高的就是下一個被執行的進程。

O(n) 調度器設計和實現上存在一些問題，但是其中的很多思想爲後續調度器設計指明瞭方向，意義深遠。

O(1) 調度器

O(n) 調度器在 linux 內核中大約使用了 4 年，在 Linux 2.6.0 採納了 Red Hat 公司 Ingo Molnar 設計的 O(1) 調度算法，該調度算法的核心思想基於 Corbato 等人提出的多級反饋隊列算法。

O(1) 調度器引入了多個隊列，並且增加了負載均衡機制，對新出現的進行任務分配到合適的 cpu-runqueue 中：

爲了實現 O(1) 複雜度的 pick-next 算法，內核實現代碼量增加了一倍多，其有以下幾個特點：

struct runqueue {
        spinlock_t lock;
        unsigned long nr_running;
        unsigned long long nr_switches;
        unsigned long expired_timestamp, nr_uninterruptible;
        unsigned long long timestamp_last_tick;
        task_t *curr, *idle;
        struct mm_struct *prev_mm;
        prio_array_t *active, *expired, arrays[2];
        int best_expired_prio;
        atomic_t nr_iowait;
        ......
};

prio_array_t 結構體的定義：

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

O(1) 調度器對 pick-next 的實現：

idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
array = rq->active;
if (unlikely(!array->nr_active)) {
        /*
         * Switch the active and expired arrays.
         */
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
}

O(1) 和 O(n) 調度器確定進程優先級的方法不一樣，O(1) 藉助了 sleep_avg 變量記錄進程的睡眠時間，來識別 IO 密集型進程，計算 bonus 值來調整優先級：

#define NICE_TO_PRIO(nice)        (MAX_RT_PRIO + (nice) + 20)
#define NS_TO_JIFFIES(TIME)        ((TIME) / (1000000000 / HZ))
#define CURRENT_BONUS(p) \
        (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
                MAX_SLEEP_AVG)

static int effective_prio(task_t *p)
{
        int bonus, prio;

        if (rt_task(p))
                return p->prio;

        bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

        prio = p->static_prio - bonus;
        if (prio < MAX_RT_PRIO)
                prio = MAX_RT_PRIO;
        if (prio > MAX_PRIO-1)
                prio = MAX_PRIO-1;
        return prio;
}

O(1) 調度器爲了實現複雜場景 IO 密集型任務的識別，做了大量的工作仍然無法到達 100% 的準確，但不可否認 O(1) 調度器是一款非常優秀的產品。

CFS 調度器

O(1) 調度器本質上是 MLFQ 算法的思想，隨着時間的推移也暴露除了很多問題，主要集中在 O(1) 調度器對進程交互性的判斷上積重難返。

無論是 O(n) 還是 O(1) 都需要去根據進程的運行狀況判斷它屬於 IO 密集型還是 CPU 密集型，再做優先級獎勵和懲罰，這種推測本身就會有誤差，而且場景越複雜判斷難度越大。

是繼續優化進程交互性算法，還是另闢蹊徑呢？一直困擾着 Linux 社區的大神們。

Con Kolivas 和 RSDL 調度器

在 CFS 出現之前，不得不提一位有態度 & 有實力的麻醉師 Con Kolivas，同時也是 linux 內核開發者，他在進程調度領域有自己獨到的見解。

Con Kolivas 針對 O(1) 調度器存在的維護和優化問題，提出了樓梯調度算法（Staircase Deadline Scheduler）和 基於公平策略 RSDL 調度器 (The Rotating Staircase Deadline Schedule)，遺憾的是 Linux 之父並沒有採納 RDSL 調度器。

對此 Con Kolivas 感到很憤怒，離開了 Linux 內核開發社區，但是事實上從後面 CFS 調度器幾個版本的修訂來看，Con Kolivas 的大方向是正確的，離開之後的 Con Kolivas 又開發了 BFS(Brain Fuck Scheduler) 來對抗 CFS 調度器。

“

沒錯，BFS 調度器譯爲腦殘調度器，可見 Con Kolivas 的憤怒和不滿。

Linux 之父選擇了 CFS 調度器，它借鑑了 Con Kolivas 的樓梯調度算法和 RSDL 調度器的經驗，由匈牙利人 Ingo Molnar 所提出和實現，並在 Linux kernel 2.6.23 之後取代 O(1) 調度器，名震江湖。

CFS 調度器

在 2.6.23 內核中引入 scheduling class 的概念，將調度器模塊化，系統中可以有多種調度器，使用不同策略調度不同類型的進程：

這樣一來，CFS 調度器就不關心實時進程了，專注於普通進程就可以了。

CFS(Completely Fair Scheduler) 完全公平調度器，從實現思想上和之前的 O(1)/O(n) 很不一樣。

我的腦海裏浮現了這幅漫畫，我想右邊的應該更好，按需分配 & 達成共贏。

這個世界怎麼會有絕對的公平呢？爲啥這個調度器敢說自己是完全公平呢？

這一切 CFS 是如何實現的呢？我們繼續看！

優先級和權重

O(1) 和 O(n) 都將 CPU 資源劃分爲時間片，採用了固定額度分配機制，在每個調度週期進程可使用的時間片是確定的，調度週期結束被重新分配。

CFS 摒棄了固定時間片分配，採用動態時間片分配，本次調度中進程可佔用的時間與進程總數、總 CPU 時間、進程權重等均有關係，每個調度週期的值都可能會不一樣。

CFS 調度器從進程優先級出發，它建立了優先級 prio 和權重 weight 之間的映射關係，把優先級轉換爲權重來參與後續的計算：

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,
};

“

普通進程的優先級範圍是 [100,139]，prio 整體減小 120 就和代碼左邊的註釋對上了，也就是 nice 值的範圍 [-20,19]，因此 sched_prio=0 相當於 static_prio=120。

比如現有進程 A sched_prio=0，進程 B sched_prio=-5，通過 sched_prio_to_weight 的映射：

在 CFS 中引入 sysctl_sched_latency(調度延遲) 作爲一個調度週期，真實的 CPU 時間表示爲：

顯然這樣根據權重計算後的各個進程的運行時間是不等的，也就違背了 "完全公平" 思想，於是 CFS 引入了虛擬運行時間 (virtual runtime)。

虛擬運行時間

每個進程的物理運行時間時肯定不能一樣的，CFS 調度器只要保證的就是進程的虛擬運行時間相等即可。

那虛擬運行時間該如何計算呢？

“

virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh

比如現有進程 A sched_prio=0，進程 B sched_prio=-5：

經過這樣映射，A 和 B 的虛擬時間就相等了。

上述公式涉及了除法和浮點數運算，因此需要轉換成爲乘法來保證數據準確性，再給出虛擬時間計算的變形等價公式：

“

virtual_time = (wall_time * nice_0_weight * 2^32/sched_prio_to_weigh)>>32

“

令 inv_weight = 2^32/sched_prio_to_weigh

“

則 virtual_time = (wall_time * 1024 * inv_weight)>>32

由於 sched_prio_to_weigh 的值存儲在數組中，inv_weight 同樣可以：

const u32 sched_prio_to_wmult[40] = {
/* -20 */     48388,     59856,     76040,     92818,    118348,
/* -15 */    147320,    184698,    229616,    287308,    360437,
/* -10 */    449829,    563644,    704093,    875809,   1099582,
/*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
/*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
/*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
/*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
/*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

經過一番計算，各個進程的虛擬運行時間一致了，似乎我們理解了 "完全公平" 的思想。

虛擬運行時間與優先級的衰減因子有關，也就是 inv_weight 隨着 nice 值增大而增大，同時其作爲分母也加速了低優先級進程的衰減。

“

簡言之：CFS 將物理運行時間在不同優先級進程中發生了不同的通脹。

摒棄了固定時間片機制也是 CFS 的亮點，系統負載高時大家都少用一些 CPU，系統負載低時大家都多用一些 CPU，讓調度器有了一定的自適應能力。

pick-next 和紅黑樹

那麼這些進程應該採用哪種數據結構來實現 pick-next 算法呢？

CFS 調度器採用了紅黑樹來保存活躍進程任務，紅黑樹的增刪查複雜度是 O(logn)，但是 CFS 引入了一些額外的數據結構，可以免去遍歷獲得下一個最合適的進程。

紅黑樹的 key 是進程已經使用的虛擬運行時間，並且把虛擬時間數值最小的放到最左的葉子節點，這個節點就是下一個被 pick 的進程了。

前面已經論證了，每個進程的虛擬運行時間是一樣的，數值越小表示被調度的越少，因此需要更偏愛一些，當虛擬運行時間耗盡則從紅黑樹中刪除，下個調度週期開始後再添加到紅黑樹上。

本章重點

參考資料

後端研究所 專注後端開發，記錄所思所得。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OtA6S_KWvPbbLKJvgQYukA

猜你喜歡