Linux進(jìn)程O(1)調(diào)度算法，面試必考哦

進(jìn)程調(diào)度有很多方法，這里只討論Linux下的進(jìn)程調(diào)度，先說下，這個(gè)是高端面試必考題，既然我發(fā)文了，大家最好看看，而且目前看到的寫得最好的文章，推薦給大家。

====

Linux是一個(gè)支持多任務(wù)的操作系統(tǒng)，而多個(gè)任務(wù)之間的切換是通過 調(diào)度器 來完成，調(diào)度器 使用不同的調(diào)度算法會(huì)有不同的效果。

Linux2.4版本使用的調(diào)度算法的時(shí)間復(fù)雜度為O(n)，其主要原理是通過輪詢所有可運(yùn)行任務(wù)列表，然后挑選一個(gè)最合適的任務(wù)運(yùn)行，所以其時(shí)間復(fù)雜度與可運(yùn)行任務(wù)隊(duì)列的長度成正比。

而Linux2.6開始替換成名為 O(1)調(diào)度算法，顧名思義，其時(shí)間復(fù)雜度為O(1)。雖然在后面的版本開始使用 CFS調(diào)度算法（完全公平調(diào)度算法），但了解 O(1)調(diào)度算法 對(duì)學(xué)習(xí)Linux調(diào)度器還是有很大幫助的，所以本文主要介紹 O(1)調(diào)度算法 的原理與實(shí)現(xiàn)。

由于在 Linux 內(nèi)核中，任務(wù)和進(jìn)程是相同的概念，所以在本文混用了任務(wù)和進(jìn)程這兩個(gè)名詞。

O(1)調(diào)度算法原理

prio_array 結(jié)構(gòu)

O(1)調(diào)度算法 通過優(yōu)先級(jí)來對(duì)任務(wù)進(jìn)行分組，可分為140個(gè)優(yōu)先級(jí)（0 ~ 139，數(shù)值越小優(yōu)先級(jí)越高），每個(gè)優(yōu)先級(jí)的任務(wù)由一個(gè)隊(duì)列來維護(hù)。prio_array 結(jié)構(gòu)就是用來維護(hù)這些任務(wù)隊(duì)列，如下代碼：

#define MAX_USER_RT_PRIO    100
#define MAX_RT_PRIO         MAX_USER_RT_PRIO
#define MAX_PRIO            (MAX_RT_PRIO + 40)

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

struct prio_array {
    int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

下面介紹 prio_array 結(jié)構(gòu)各個(gè)字段的作用：

1. nr_active: 所有優(yōu)先級(jí)隊(duì)列中的總?cè)蝿?wù)數(shù)。

2. bitmap: 位圖，每個(gè)位對(duì)應(yīng)一個(gè)優(yōu)先級(jí)的任務(wù)隊(duì)列，用于記錄哪個(gè)任務(wù)隊(duì)列不為空，能通過 bitmap 夠快速找到不為空的任務(wù)隊(duì)列。

3. queue: 優(yōu)先級(jí)隊(duì)列數(shù)組，每個(gè)元素維護(hù)一個(gè)優(yōu)先級(jí)隊(duì)列，比如索引為0的元素維護(hù)著優(yōu)先級(jí)為0的任務(wù)隊(duì)列。

下圖更直觀地展示了 prio_array 結(jié)構(gòu)各個(gè)字段的關(guān)系：

如上圖所述，bitmap 的第2位和第6位為1（紅色代表為1，白色代表為0），表示優(yōu)先級(jí)為2和6的任務(wù)隊(duì)列不為空，也就是說 queue 數(shù)組的第2個(gè)元素和第6個(gè)元素的隊(duì)列不為空。

runqueue 結(jié)構(gòu)

另外，為了減少多核CPU之間的競爭，所以每個(gè)CPU都需要維護(hù)一份本地的優(yōu)先隊(duì)列。因?yàn)槿绻褂萌值膬?yōu)先隊(duì)列，那么多核CPU就需要對(duì)全局優(yōu)先隊(duì)列進(jìn)行上鎖，從而導(dǎo)致性能下降。

每個(gè)CPU都需要維護(hù)一個(gè) runqueue 結(jié)構(gòu)，runqueue 結(jié)構(gòu)主要維護(hù)任務(wù)調(diào)度相關(guān)的信息，比如優(yōu)先隊(duì)列、調(diào)度次數(shù)、CPU負(fù)載信息等。其定義如下：

struct runqueue {
    spinlock_t lock;
    unsigned long nr_running,
                  nr_switches,
                  expired_timestamp,
                  nr_uninterruptible;
    task_t *curr, *idle;
    struct mm_struct *prev_mm;
    prio_array_t *active, *expired, arrays[2];
    int prev_cpu_load[NR_CPUS];
    task_t *migration_thread;
    struct list_head migration_queue;
    atomic_t nr_iowait;
};

runqueue 結(jié)構(gòu)有兩個(gè)重要的字段：active 和 expired，這兩個(gè)字段在 O(1)調(diào)度算法 中起著至關(guān)重要的作用。我們先來了解一下 O(1)調(diào)度算法 的大概原理。

我們注意到 active 和 expired 字段的類型為 prio_array，指向任務(wù)優(yōu)先隊(duì)列。active 代表可以調(diào)度的任務(wù)隊(duì)列，而 expired 字段代表時(shí)間片已經(jīng)用完的任務(wù)隊(duì)列。active 和 expired 會(huì)進(jìn)行以下兩個(gè)過程：

1. 當(dāng) active 中的任務(wù)時(shí)間片用完，那么就會(huì)被移動(dòng)到 expired 中。

2. 當(dāng) active 中已經(jīng)沒有任務(wù)可以運(yùn)行，就把 expired 與 active 交換，從而 expired 中的任務(wù)可以重新被調(diào)度。

如下圖所示：

O(1)調(diào)度算法 把140個(gè)優(yōu)先級(jí)的前100個(gè)（0 ~ 99）作為 實(shí)時(shí)進(jìn)程優(yōu)先級(jí)，而后40個(gè)（100 ~ 139）作為 普通進(jìn)程優(yōu)先級(jí)。實(shí)時(shí)進(jìn)程被放置到實(shí)時(shí)進(jìn)程優(yōu)先級(jí)的隊(duì)列中，而普通進(jìn)程放置到普通進(jìn)程優(yōu)先級(jí)的隊(duì)列中。

實(shí)時(shí)進(jìn)程調(diào)度

實(shí)時(shí)進(jìn)程分為 FIFO（先進(jìn)先出） 和 RR（時(shí)間輪詢） 兩種，其調(diào)度算法比較簡單，如下：

1. 先進(jìn)先出的實(shí)時(shí)進(jìn)程調(diào)度：如果調(diào)度器在執(zhí)行某個(gè)先進(jìn)先出的實(shí)時(shí)進(jìn)程，那么調(diào)度器會(huì)一直運(yùn)行這個(gè)進(jìn)程，直至其主動(dòng)放棄運(yùn)行權(quán)（退出進(jìn)程或者sleep等）。

2. 時(shí)間輪詢的實(shí)時(shí)進(jìn)程調(diào)度：如果調(diào)度器在執(zhí)行某個(gè)時(shí)間輪詢的實(shí)時(shí)進(jìn)程，那么調(diào)度器會(huì)判斷當(dāng)前進(jìn)程的時(shí)間片是否用完，如果用完的話，那么重新分配時(shí)間片給它，并且重新放置回 active 隊(duì)列中，然后調(diào)度到其他同優(yōu)先級(jí)或者優(yōu)先級(jí)更高的實(shí)時(shí)進(jìn)程進(jìn)行運(yùn)行。

普通進(jìn)程調(diào)度

每個(gè)進(jìn)程都要一個(gè)動(dòng)態(tài)優(yōu)先級(jí)和靜態(tài)優(yōu)先級(jí)，靜態(tài)優(yōu)先級(jí)不會(huì)變化（進(jìn)程創(chuàng)建時(shí)被設(shè)置），而動(dòng)態(tài)優(yōu)先級(jí)會(huì)隨著進(jìn)程的睡眠時(shí)間而發(fā)生變化。動(dòng)態(tài)優(yōu)先級(jí)可以通過以下公式進(jìn)行計(jì)算：

動(dòng)態(tài)優(yōu)先級(jí) = max(100, min(靜態(tài)優(yōu)先級(jí) – bonus + 5), 139))

上面公式的 bonus（獎(jiǎng)勵(lì)或懲罰） 是通過進(jìn)程的睡眠時(shí)間計(jì)算出來，進(jìn)程的睡眠時(shí)間越大，bonus 的值就越大，那么動(dòng)態(tài)優(yōu)先級(jí)就越高（前面說過優(yōu)先級(jí)的值越小，優(yōu)先級(jí)越高）。

另外要說明一下，實(shí)時(shí)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)與靜態(tài)優(yōu)先級(jí)相同。

當(dāng)一個(gè)普通進(jìn)程被添加到運(yùn)行隊(duì)列時(shí)，會(huì)先計(jì)算其動(dòng)態(tài)優(yōu)先級(jí)，然后按照動(dòng)態(tài)優(yōu)先級(jí)的值來添加到對(duì)應(yīng)優(yōu)先級(jí)的隊(duì)列中。而調(diào)度器調(diào)度進(jìn)程時(shí)，會(huì)先選擇優(yōu)先級(jí)最高的任務(wù)隊(duì)列中的進(jìn)程進(jìn)行調(diào)度運(yùn)行。

運(yùn)行時(shí)間片計(jì)算

當(dāng)進(jìn)程的時(shí)間用完后，就需要重新進(jìn)行計(jì)算。進(jìn)程的運(yùn)行時(shí)間片與靜態(tài)優(yōu)先級(jí)有關(guān)，可以通過以下公式進(jìn)行計(jì)算：

靜態(tài)優(yōu)先級(jí) < 120，運(yùn)行時(shí)間片 = max((140-靜態(tài)優(yōu)先級(jí))*20, MIN_TIMESLICE)
靜態(tài)優(yōu)先級(jí) >= 120，運(yùn)行時(shí)間片 = max((140-靜態(tài)優(yōu)先級(jí))*5, MIN_TIMESLICE)

O(1)調(diào)度算法實(shí)現(xiàn)

接下來我們分析一下 O(1)調(diào)度算法 在內(nèi)核中的實(shí)現(xiàn)。

時(shí)鐘中斷

時(shí)鐘中斷是由硬件觸發(fā)的，可以通過編程來設(shè)置其頻率，Linux內(nèi)核一般設(shè)置為每秒產(chǎn)生100 ~ 1000次。時(shí)鐘中斷會(huì)觸發(fā)調(diào)用 scheduler_tick() 內(nèi)核函數(shù)，其主要工作是：減少進(jìn)程的可運(yùn)行時(shí)間片，如果時(shí)間片用完，那么把進(jìn)程從 active 隊(duì)列移動(dòng)到 expired 隊(duì)列中。代碼如下：

void scheduler_tick(int user_ticks, int sys_ticks)
{
    runqueue_t *rq = this_rq();
    task_t *p = current;

    ...

    // 處理普通進(jìn)程
    if (!--p->time_slice) {                // 減少時(shí)間片, 如果時(shí)間片用完
        dequeue_task(p, rq->active);       // 把進(jìn)程從運(yùn)行隊(duì)列中刪除
        set_tsk_need_resched(p);           // 設(shè)置要重新調(diào)度標(biāo)志
        p->prio = effective_prio(p);       // 重新計(jì)算動(dòng)態(tài)優(yōu)先級(jí)
        p->time_slice = task_timeslice(p); // 重新計(jì)算時(shí)間片
        p->first_time_slice = 0;

        if (!rq->expired_timestamp)
            rq->expired_timestamp = jiffies;

        // 如果不是交互進(jìn)程或者沒有出來饑餓狀態(tài)
        if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
            enqueue_task(p, rq->expired); // 移動(dòng)到expired隊(duì)列
        } else
            enqueue_task(p, rq->active);  // 重新放置到active隊(duì)列
    }
    ...
}

上面代碼主要完成以下幾個(gè)工作：

1. 減少進(jìn)程的時(shí)間片，并且判斷時(shí)間片是否已經(jīng)使用完。

2. 如果時(shí)間片使用完，那么把進(jìn)程從 active 隊(duì)列中刪除。

3. 調(diào)用 set_tsk_need_resched() 函數(shù)設(shè) TIF_NEED_RESCHED 標(biāo)志，表示當(dāng)前進(jìn)程需要重新調(diào)度。

4. 調(diào)用 effective_prio() 函數(shù)重新計(jì)算進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。

5. 調(diào)用 task_timeslice() 函數(shù)重新計(jì)算進(jìn)程的可運(yùn)行時(shí)間片。

6. 如果當(dāng)前進(jìn)程是交互進(jìn)程或者出來饑餓狀態(tài)，那么重新加入到 active 隊(duì)列。

7. 否則把今天移動(dòng)到 expired 隊(duì)列。

任務(wù)調(diào)度

如果進(jìn)程設(shè)置了 TIF_NEED_RESCHED 標(biāo)志，那么當(dāng)從時(shí)鐘中斷返回到用戶空間時(shí)，會(huì)調(diào)用 schedule() 函數(shù)進(jìn)行任務(wù)調(diào)度。schedule() 函數(shù)代碼如下：

void schedule(void)
{
    ...
    prev = current;  // 當(dāng)前需要被調(diào)度的進(jìn)程
    rq = this_rq();  // 獲取當(dāng)前CPU的runqueue

    array = rq->active; // active隊(duì)列

    // 如果active隊(duì)列中沒有進(jìn)程, 那么替換成expired隊(duì)列
    if (unlikely(!array->nr_active)) {
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
    }

    idx = sched_find_first_bit(array->bitmap); // 找到最高優(yōu)先級(jí)的任務(wù)隊(duì)列
    queue = array->queue + idx;
    next = list_entry(queue->next, task_t, run_list); // 獲取到下一個(gè)將要運(yùn)行的進(jìn)程

    ...
    prev->sleep_avg -= run_time; // 減少當(dāng)前進(jìn)程的睡眠時(shí)間
    ...

    if (likely(prev != next)) {
        ...
        prev = context_switch(rq, prev, next); // 切換到next進(jìn)程進(jìn)行運(yùn)行
        ...
    }
    ...
}

上面代碼主要完成以下幾個(gè)步驟：

1. 如果當(dāng)前 runqueue 的 active 隊(duì)列為空，那么把 active 隊(duì)列與 expired 隊(duì)列進(jìn)行交換。

2. 調(diào)用 sched_find_first_bit() 函數(shù)在 bitmap 中找到優(yōu)先級(jí)最高并且不為空的任務(wù)隊(duì)列索引。

3. 減少當(dāng)前進(jìn)程的睡眠時(shí)間。

4. 調(diào)用 context_switch() 函數(shù)切換到next進(jìn)程進(jìn)行運(yùn)行。