[Scheduler] The Overview

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

Linux schedules tasks的過程中會依據task_struct中紀錄¹的schedule scheme決定如何操作²runqueue，每個task所屬的schedule scheme不是fair_sched_class就是rt_sched_class。Fair schedule class用於schedule所有一般的tasks，rt schedule class用於schedule所有real-time tasks³。我們先看看fair_sched_class與rt_sched_class兩個struct的內容：

static const struct sched_class fair_sched_class = {
        .next                   = &idle_sched_class,
        .enqueue_task           = enqueue_task_fair,
        .dequeue_task           = dequeue_task_fair,
        .yield_task             = yield_task_fair,

        .check_preempt_curr     = check_preempt_wakeup,

        .pick_next_task         = pick_next_task_fair,
        .put_prev_task          = put_prev_task_fair,

#ifdef CONFIG_SMP
        .load_balance           = load_balance_fair,
        .move_one_task          = move_one_task_fair,
#endif

        .set_curr_task          = set_curr_task_fair,
        .task_tick              = task_tick_fair,
        .task_new               = task_new_fair,
};

const struct sched_class rt_sched_class = {
        .next                   = &fair_sched_class,
        .enqueue_task           = enqueue_task_rt,
        .dequeue_task           = dequeue_task_rt,
        .yield_task             = yield_task_rt,

        .check_preempt_curr     = check_preempt_curr_rt,

        .pick_next_task         = pick_next_task_rt,
        .put_prev_task          = put_prev_task_rt,

#ifdef CONFIG_SMP
        .load_balance           = load_balance_rt,
        .move_one_task          = move_one_task_rt,
#endif

        .set_curr_task          = set_curr_task_rt,
        .task_tick              = task_tick_rt,
};

再來看看取自schedule函式的範例：

prev->sched_class->put_prev_task(rq, prev);

若prev為一般task，則實際呼叫的函式為put_prev_task_fair，否則呼叫put_prev_task_rt函式。
改版後的schedule函式將schedule scheme切成兩個部分，一般task與real-time task，一般task使用紅黑樹的方式排序，real-time task則延續使用2.6.22版本以前的O(1)方式排序，code與之前的版本相比也更為精簡，由2.6.22的158行減少為2.6.24的63 行。新版schedule函式的重點落在下面幾行code上：

prev->sched_class->put_prev_task(rq, prev);
next = pick_next_task(rq, prev);

sched_info_switch(prev, next);

if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        context_switch(rq, prev, next); /* unlocks the rq */
} else
        spin_unlock_irq(&rq->lock);

1 紀錄於task_struct的sched_class欄位中。
2 在runqueue中新增移除task，或者改變task在runqueue中的位置（優先順序）。
3 PC環境中很難做到真的real-time，因此這裡的real-time task指的是擁有高執行優先權要儘早執行完畢的task。