# 《Demystifying the Linux CPU Scheduler》重點提示
先備知識：
[Linux 核心設計: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)
[UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)
[Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process)
[Linux 核心設計: 記憶體管理](https://hackmd.io/@sysprog/linux-memory)
## 2. The Linux CPU scheduler
Linux CPU 排程器從 1990 年誕生以來，便隨著科技的進步不斷演化，這是令當初的開發者們始料未及的
>延伸閱讀 ： [Linux 核心設計: 發展動態回顧](https://hackmd.io/@sysprog/linux-dev-review)
### Early scheduler
>Linux v0.01 ~ Linux v1.2
與排程有關的 fields :
- priority :
靜態權重，其的意義是該任務的在 Round Robin 中的 timeslice ，越重要的任務分的越多的 timeslice.
- counter :
動態權重，其的意義是該任務剩餘的 timeslice ，會隨著時間減少，當任務的 conter 小於零時，排程器便會選擇下一個任務。
當要挑選下一個任務時，排程器會走訪陣列並找出可執行且 counter 最大的任務。
```c
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
```
若所有陣列中所有可執行的任務的 counter 皆為零，排程器便會重新計算其 counter
```c
(*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](https://www.iitk.ac.in/LDP/LDP/lki/lki.pdf)
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。
```c
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
```c
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 或低優先權的任務跑的不亦樂乎，高優先權的任務卻在苦等](https://people.ece.ubc.ca/sasha/papers/eurosys16-final29.pdf)」的情況發生，當一任務被加入 runqueue 時，會由 `reschedule_idle()` 來決定是否要搶佔。
`reschedule_idle()` 藉由將欲搶佔的任務的 `need_resched` 類別設為 `1` ，使其所在的 CPU 呼叫排程器，重新排程：
1. 該任務上一次使用的 CPU (p->process)剛好 為Idle
2. 其他 Idle 的CPU
3. 正在運行 Goodness value 相較於該任務最低的任務 的CPU
>參考 [令人詬病的 Linux 2.4 排程器](https://hackmd.io/@sysprog/linux-scheduler#%E4%BB%A4%E4%BA%BA%E8%A9%AC%E7%97%85%E7%9A%84-Linux-24-%E6%8E%92%E7%A8%8B%E5%99%A8:~:text=the%20Linux%20Kernel-,%E4%BB%A4%E4%BA%BA%E8%A9%AC%E7%97%85%E7%9A%84%20Linux%202.4%20%E6%8E%92%E7%A8%8B%E5%99%A8,-%E5%9B%9E%E9%A1%A7%20Linux%202.4)
### O(1) scheduler
Linux v2.6 ~ Linux v2.6.22
### CFS
Linux v2.6.23 ~ Linux v6.5
### EEVDF
Linux v6.6 ~
Sign in with Wallet
Connect another wallet