Linux進程調度之

Linux是一個支持多任務的操作系統，而多個任務之間的切換是通過 調度器 來完成，調度器 使用不同的調度算法會有不同的效果。

Linux2.4版本使用的調度算法的時間複雜度為O(n)，其主要原理是通過輪詢所有可運行任務列表，然後挑選一個最合適的任務運行，所以其時間複雜度與可運行任務隊列的長度成正比。

而Linux2.6開始替換成名為 O(1)調度算法，顧名思義，其時間複雜度為O(1)。雖然在後面的版本開始使用 CFS調度算法（完全公平調度算法），但瞭解 O(1)調度算法 對學習Linux調度器還是有很大幫助的，所以本文主要介紹 O(1)調度算法 的原理與實現。

由於在 Linux 內核中，任務和進程是相同的概念，所以在本文混用了任務和進程這兩個名詞。

O(1)調度算法原理

prio_array 結構

O(1)調度算法 通過優先級來對任務進行分組，可分為140個優先級（0 ~ 139，數值越小優先級越高），每個優先級的任務由一個隊列來維護。prio_array 結構就是用來維護這些任務隊列，如下代碼：

<code>#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];
};/<code>

下面介紹 prio_array 結構各個字段的作用：

1. nr_active: 所有優先級隊列中的總任務數。
2. bitmap: 位圖，每個位對應一個優先級的任務隊列，用於記錄哪個任務隊列不為空，能通過 bitmap 夠快速找到不為空的任務隊列。
3. queue: 優先級隊列數組，每個元素維護一個優先級隊列，比如索引為0的元素維護著優先級為0的任務隊列。

下圖更直觀地展示了 prio_array 結構各個字段的關係：

如上圖所述，bitmap 的第2位和第6位為1（紅色代表為1，白色代表為0），表示優先級為2和6的任務隊列不為空，也就是說 queue 數組的第2個元素和第6個元素的隊列不為空。

runqueue 結構

另外，為了減少多核CPU之間的競爭，所以每個CPU都需要維護一份本地的優先隊列。因為如果使用全局的優先隊列，那麼多核CPU就需要對全局優先隊列進行上鎖，從而導致性能下降。

每個CPU都需要維護一個 runqueue 結構，runqueue 結構主要維護任務調度相關的信息，比如優先隊列、調度次數、CPU負載信息等。其定義如下：

<code>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;
};/<code>

runqueue 結構有兩個重要的字段：active 和 expired，這兩個字段在 O(1)調度算法 中起著至關重要的作用。我們先來了解一下 O(1)調度算法 的大概原理。

我們注意到 active 和 expired 字段的類型為 prio_array，指向任務優先隊列。active 代表可以調度的任務隊列，而 expired 字段代表時間片已經用完的任務隊列。active 和 expired 會進行以下兩個過程：

1. 當 active 中的任務時間片用完，那麼就會被移動到 expired 中。
2. 當 active 中已經沒有任務可以運行，就把 expired 與 active 交換，從而 expired 中的任務可以重新被調度。

如下圖所示：

O(1)調度算法 把140個優先級的前100個（0 ~ 99）作為 實時進程優先級，而後40個（100 ~ 139）作為 普通進程優先級。實時進程被放置到實時進程優先級的隊列中，而普通進程放置到普通進程優先級的隊列中。

實時進程調度

實時進程分為 FIFO（先進先出） 和 RR（時間輪詢） 兩種，其調度算法比較簡單，如下：

1. 先進先出的實時進程調度：如果調度器在執行某個先進先出的實時進程，那麼調度器會一直運行這個進程，直至其主動放棄運行權（退出進程或者sleep等）。
2. 時間輪詢的實時進程調度：如果調度器在執行某個時間輪詢的實時進程，那麼調度器會判斷當前進程的時間片是否用完，如果用完的話，那麼重新分配時間片給它，並且重新放置回 active 隊列中，然後調度到其他同優先級或者優先級更高的實時進程進行運行。

普通進程調度

每個進程都要一個動態優先級和靜態優先級，靜態優先級不會變化（進程創建時被設置），而動態優先級會隨著進程的睡眠時間而發生變化。動態優先級可以通過以下公式進行計算：

<code>動態優先級 = max(100, min(靜態優先級 – bonus + 5), 139))/<code>

上面公式的 bonus（獎勵或懲罰） 是通過進程的睡眠時間計算出來，進程的睡眠時間越大，bonus 的值就越大，那麼動態優先級就越高（前面說過優先級的值越小，優先級越高）。

另外要說明一下，實時進程的動態優先級與靜態優先級相同。

當一個普通進程被添加到運行隊列時，會先計算其動態優先級，然後按照動態優先級的值來添加到對應優先級的隊列中。而調度器調度進程時，會先選擇優先級最高的任務隊列中的進程進行調度運行。

運行時間片計算

當進程的時間用完後，就需要重新進行計算。進程的運行時間片與靜態優先級有關，可以通過以下公式進行計算：

<code>靜態優先級 < 120，運行時間片 = max((140-靜態優先級)*20, MIN_TIMESLICE)
靜態優先級 >= 120，運行時間片 = max((140-靜態優先級)*5, MIN_TIMESLICE)/<code>

O(1)調度算法實現

接下來我們分析一下 O(1)調度算法 在內核中的實現。

時鐘中斷

時鐘中斷是由硬件觸發的，可以通過編程來設置其頻率，Linux內核一般設置為每秒產生100 ~ 1000次。時鐘中斷會觸發調用 scheduler_tick() 內核函數，其主要工作是：減少進程的可運行時間片，如果時間片用完，那麼把進程從 active 隊列移動到 expired 隊列中。代碼如下：

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

    ...

    // 處理普通進程
    if (!--p->time_slice) {                // 減少時間片, 如果時間片用完
        dequeue_task(p, rq->active);       // 把進程從運行隊列中刪除
        set_tsk_need_resched(p);           // 設置要重新調度標誌
        p->prio = effective_prio(p);       // 重新計算動態優先級
        p->time_slice = task_timeslice(p); // 重新計算時間片
        p->first_time_slice = 0;

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

        // 如果不是交互進程或者沒有出來飢餓狀態
        if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
            enqueue_task(p, rq->expired); // 移動到expired隊列
        } else
            enqueue_task(p, rq->active);  // 重新放置到active隊列
    }
    ...
}/<code>

上面代碼主要完成以下幾個工作：

1. 減少進程的時間片，並且判斷時間片是否已經使用完。
2. 如果時間片使用完，那麼把進程從 active 隊列中刪除。
3. 調用 set_tsk_need_resched() 函數設 TIF_NEED_RESCHED 標誌，表示當前進程需要重新調度。
4. 調用 effective_prio() 函數重新計算進程的動態優先級。
5. 調用 task_timeslice() 函數重新計算進程的可運行時間片。
6. 如果當前進程是交互進程或者出來飢餓狀態，那麼重新加入到 active 隊列。
7. 否則把今天移動到 expired 隊列。

任務調度

如果進程設置了 TIF_NEED_RESCHED 標誌，那麼當從時鐘中斷返回到用戶空間時，會調用 schedule() 函數進行任務調度。schedule() 函數代碼如下：

<code>void schedule(void)
{
    ...
    prev = current;  // 當前需要被調度的進程
    rq = this_rq();  // 獲取當前CPU的runqueue
 

    array = rq->active; // active隊列

    // 如果active隊列中沒有進程, 那麼替換成expired隊列
    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); // 找到最高優先級的任務隊列
    queue = array->queue + idx;
    next = list_entry(queue->next, task_t, run_list); // 獲取到下一個將要運行的進程

    ...
    prev->sleep_avg -= run_time; // 減少當前進程的睡眠時間
    ...

    if (likely(prev != next)) {
        ...
        prev = context_switch(rq, prev, next); // 切換到next進程進行運行
        ...
    }
    ...
}/<code>

上面代碼主要完成以下幾個步驟：

1. 如果當前 runqueue 的 active 隊列為空，那麼把 active 隊列與 expired 隊列進行交換。
2. 調用 sched_find_first_bit() 函數在 bitmap 中找到優先級最高並且不為空的任務隊列索引。
3. 減少當前進程的睡眠時間。
4. 調用 context_switch() 函數切換到next進程進行運行。

閱讀更多 linux內核 的文章

關鍵字: 中央處理器 調度 算法