《Demystifying the Linux CPU Scheduler》重點提示

先備知識：
Linux 核心設計: 作業系統術語及概念
 UNIX 作業系統 fork/exec 系統呼叫的前世今生
 並行程式設計: 排程器原理
 Linux 核心設計: 不僅是個執行單元的 Process
Linux 核心設計: 記憶體管理

2. The Linux CPU scheduler

Linux CPU 排程器從 1990 年誕生以來，便隨著科技的進步不斷演化，這是令當初的開發者們始料未及的

延伸閱讀： Linux 核心設計: 發展動態回顧

Early scheduler

Linux v0.01 ~ Linux v1.2

與排程有關的 fields :

priority :
靜態權重，其的意義是該任務的在 Round Robin 中的 timeslice ，越重要的任務分的越多的 timeslice.
counter :
動態權重，其的意義是該任務剩餘的 timeslice ，會隨著時間減少，當任務的 conter 小於零時，排程器便會選擇下一個任務。

當要挑選下一個任務時，排程器會走訪陣列並找出可執行且 counter 最大的任務。

while (--i) {
    if (!*--p)
	    continue;
	if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
	    c = (*p)->counter, next = i;
}

若所有陣列中所有可執行的任務的 counter 皆為零，排程器便會重新計算其 counter

(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;

其他狀態的任務有剩餘的 counter 則會除以二後加入新的 counter 中。
此舉可以確保 I/O bound 的任務能被優先選到。

Early Scheduler 可以處理大多數的情況，但不支援多核處理，因排程器無法顧慮 cache affinity 以及多執行序的同步問題 (Synchronization)，改變勢在必行。

O(n) scheduler

參考:Linux Kernel 2.4 Internals
Linux v2.0~ Linux v2.4

O(n) scheduler 的演算法跟 Early scheduler 並無太大的差異，皆是在走訪 runqueue 後選出「最適合」的任務來執行。
差異在於 O(n) scheduler 是由 goodness function.

goodness fuction 會依據任務的 cache affinity, 權重以及是否為即時任務來決定其「適合」的程度。

任務會依照其權重大小被分成不同的類別，而不同的類別的任務則會對應到不同的排程策略 (policy)

SCHED_OTHER (traditional UNIX process)
SCHED_FIFO (POSIX.1b FIFO realtime process)
SCHED_RR (POSIX round−robin realtime process)
當任務的 conter 耗盡時，排程器會立刻賦予其新的 timeslice 並將其放到 runqueue 的末端，如此一來若有相同權重的任務便會被輪流執行到
SCHED_YIELD

其他有關排程的 fiels:

rt_priority:
即時任務的權重，排程器會依此為任務類別為 SCHED_RR 或 SCHED_FIFO 的任務排序
has_cpu :
用來表示任務是否有被指派到特定的 CPU
processor :
用來表示最近一次執行此任務的 CPU

開始正式支援 SMP，使得處理器能處理的任務規模不同日而語，
o(n) scheduler 的基本架構跟 Early scheduler 一樣，都是先走訪整個 runqueue 並找出最「適合」的任務進行排程，兩者的差異在於 o(n) scheduler 支援 SMP

Linux scheduler behavior has two paths involved in it they are :

在多核處理的架構中，每個核（core）個自(exclusively)從 global runqueue 中挑選「最適合」該核的任務。
在挑選的過程中，schedule()會逐一比較 runqueue 中所有任務的 goodness value 來決定是否要切換當前任務。

goodness function

與單核處理不同，在多核處理的架構下，排程器需考慮的不僅有任務的權重，還需考慮 cache affinity
一個任務的 goodness value 是由 goodness function 所計算，一個任務的 goodness value 愈高代表該任務越適合當前的核。

即時行程與普通行程的 goodness value 在計算的方法上大不相同：

在計算即時任務的 goodness value 時只考慮其 rt_priority 而不考慮其剩餘的 timeslice，並額外加上 1000 以確保即時行程的 goodness value 會永遠大於普通行程的 goodness value.
相較於即時行程，普通行程更在乎 fairness ，即任務得到的 CPU 時間需要與其 nice value 成比例。
因此 goodness value 的計算方式為該任務
剩餘的 timeslic 加上其 nice value (20 - p->nice)

此外考量到 cache affinity 對效能的影響，若當前 core 為該普通任務上一次運行的 core（哇！真巧），則其 goodness value 會再加上額外的常數 PROC_CHANGE_PENALTY ，即相較於其他同樣 goodness value 的任務「更適合」當前的 core。

static inline int goodness(struct task_struct *p, int this_cpu,
                           struct mm_struct *this_mm)
{
    int weight = -1;
    if (p->policy & SCHED_YIELD)
        goto out;

    /* Non-RT process - normal case first. */
    if (p->policy == SCHED_OTHER) {
        weight = p->counter;
        if (!weight)
            goto out;

#ifdef CONFIG_SMP
        /* Give a largish advantage to the same processor. */
        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;
    }

    /* Realtime process */
    weight = 1000 + p->rt_priority;
out:
    return weight;
}

倘若 runqueue 中所有任務的 goodness value 皆小於等於零，則代表所有任務都消耗完各自的 timeslice 。

此時 schedule() 會重新賦予每個任務新的 timeslice 。
要注意即時任務一但耗盡其 timeslice ， schedule() 便會為重新賦予其新的 timeslice ，
並將其移動至 runqueue 的底部，確保相同優先權的的任務會被輪流執行到。
反之普通任務只有在 runqueue 中所有任務皆耗盡其 timeslice 時才會重新得到 timesice.

scheduler

asmlinkage void schedule(void)
{
    /* process descriptors: prev: currently running; p: currently iterating */
    struct task_struct *prev, *p;
    int this_cpu;
    // ...skip...
    /* move an exhausted RR process to be last.. */
	if (unlikely(prev->policy == SCHED_RR))
		if (!prev->counter) {
			prev->counter = NICE_TO_TICKS(prev->nice);
			move_last_runqueue(prev);
		}s
repeat_schedule:
    /* Default process to select.. */
    next = idle_task(this_cpu);
    c = -1000;
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) {
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c)
                c = weight, next = p;
        }
    }

    if (unlikely(!c)) {
        struct task_struct *p;

        spin_unlock_irq(&runqueue_lock);
        read_lock(&tasklist_lock);
        for_each_task(p)
            p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
        read_unlock(&tasklist_lock);
        spin_lock_irq(&runqueue_lock);
        goto repeat_schedule;
    }
    // ...skip...
}

reschedule_idle

the function determines whether the process should preempt the current process of some CPU

為了避免「idle task 或低優先權的任務跑的不亦樂乎，高優先權的任務卻在苦等」的情況發生，當一任務被加入 runqueue 時，會由 reschedule_idle() 來決定是否要搶佔。

reschedule_idle() 藉由將欲搶佔的任務的 need_resched 類別設為 1 ，使其所在的 CPU 呼叫排程器，重新排程：

該任務上一次使用的 CPU (p->process)剛好為Idle
其他 Idle 的CPU
正在運行 Goodness value 相較於該任務最低的任務的CPU

參考令人詬病的 Linux 2.4 排程器

O(1) scheduler

Linux v2.6 ~ Linux v2.6.22

CFS

Linux v2.6.23 ~ Linux v6.5

EEVDF

Linux v6.6 ~