# Linux 核心專題: 排程器研究
> 執行人: YangYeh-PD
> [專題解說影片](https://youtu.be/m6ps9Z9htzM) (2024.06.29)
## 任務簡介
1. 檢閱學員對於 Linux 核心 CPU 排程器的分析，確認其內容的正確，適度提出疑惑和參與討論。
2. 重現《Demystifying the Linux CPU Scheduler》第 7 章的實驗。
## TODO: 閱讀《Demystifying the Linux CPU Scheduler》
:::info
問題紀錄
1. 我們知道在 Linux 核心要求 Source Program 在把任務交給 Scheduler 之前，一定要標示好任務的類型(比如緊急與否)。那麼把一個任務歸類在 Scheduling Class 的時候，到底是由 Source Program 本身定義出來的還是由 Scheduler 識別出來的？
2. 為何 `SCHED_IDLE` 屬於 `idle_sched_class`, 兩者差別在哪裡?
> 在 yenslife 的排程器研究當中有提到，scheduling class 和 scheduling policies 的差異在於，前者用來區分優先權，後者則是排程的方法。
3. `sleep` 在早期 Linux 核心排程器有什麼用途? 為何這項行程與 ==interactivity== 有關聯?
:::
### 第 2 章: Linux 核心的 CPU 排程器
#### 一個 CPU Scheduler 需要考慮的特性
CPU 排程器在搶占式多工和非搶占式多工系統中都扮演著重要角色。
* 在搶占式多工系統中，排程器允許作業系統強行中斷正在運行的行程，並將 CPU 分配給其他行程。這確保所有行程都能獲得公平的 CPU 時間，並提高系統的響應性。
* 在非搶占式多工系統中，當一個行程被創建時，它會被放置在 **runqueue** 中。然後排程器會從中**選擇**一個行程。
```graphviz
digraph shuffle {
rankdir = "LR"
node [shape=box, style=filled];
// Define nodes with different colors
scheduler1 [label="scheduler", fillcolor="white"];
head1 [shape=none, label="head", fillcolor=white];
tail1 [shape=none, label="tail", fillcolor=white];
node1 [label="task1", fillcolor="#ffbd19", color="black"];
node2 [label="task2", fillcolor="white", color="black"];
node3 [label="task3", fillcolor="white", color="black"];
node4 [label="task4", fillcolor="white", color="black"];
node5 [label="task5", fillcolor="white", color="black"];
// Connect the nodes
scheduler1 -> node1;
head1 -> node1;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
tail1 -> node5;
}
```
##### Interactive v.s. Throughput
為何排程器往往需要在 **interactiveness** 與 **throughput** 之間做取捨？如果想要提升作業系統的互動性 (interactive)，那就要進行搶佔式多工。而這種搶佔式多工當中的 context switch 會造成 CPU 短時間閒置，因此就會降低 throught。
##### Fairness and Liveness
**Fairness** 意指具有相同優先級的任務應該獲得==相等的 CPU 時間==。然而，僅有 fairness 是不夠的。如果一個高優先級的任務持續佔用 CPU，其他任務將無法執行。因此，**Liveness** 的設計變得至關重要。Liveness 能確保==每個任務在一定時間內獲得 CPU 資源==。通過 Liveness，即使是需要完成的低優先級任務也能得到執行。
##### Realtime (RT)
Realtime 分為兩種類型：Soft real-time 以及 Hard real-time。
* 在 Soft real-time 中，如果一個進程在超過截止時間後仍未被處理，後果並不嚴重。最常見的例子是音頻和視頻不同步。
* 在 Hard real-time 中，如果一個進程在超過截止時間後仍未被處理，可能會導致嚴重後果，甚至可能導致系統崩潰。
##### Power Efficiency
Linux CPU 會根據不同的平台採用不同的節能方法。在桌機和筆記本電腦上，主要有兩種節能策略
* **優先處理低功耗任務**，如閒置任務或低優先級任務。
* **根據工作負載調整 CPU 頻率**。當工作負載較輕時，降低頻率以節省能源。
在伺服器中，由於系統需要連續運行，因此在 Throughput 和功耗之間尋求平衡是至關重要的。
* 優先處理 **CPU 密集型任務**，以提高 cache（包括時間和空間方面）和處理器之間的效率。
##### Working Pattern
所以排程器如何知道哪些任務需要優先執行呢？Linux 核心直接要求 Source Program 在將任務交給排程器進行調度之前指定優先級。Linux 核心使用 **Scheduling Classes** 的概念來實現任務調度。現在的核心版本中，有五種不同的調度類別。
```graphviz
digraph shuffle {
rankdir = "LR"
node [shape=box, style=filled];
// Define nodes with different colors
node1 [label="Stop", fillcolor="#ffbd19", color="black"];
node2 [label="Deadline", fillcolor="white", color="black"];
node3 [label="Real-Time", fillcolor="white", color="black"];
node4 [label="Fair", fillcolor="white", color="black"];
node5 [label="Idle", fillcolor="grey", color="black"];
// Connect the nodes
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
}
```
Scheduling classes | Scheduling Policies |
|:------------------:|:---------------------------------------:|
| `stop_sched_class` | |
| `dl_sched_class` | `SCHED_DEADLINE` |
| `rt_sched_class` | `SCHED_FIFO`&`SCHED_RR` |
| `fair_sched_class` |`SCHED_NORMAL`&`SCHED_BATCH`&`SCHED_IDLE`|
| `idle_sched_class` | |
* **Stop** 是用來停止 CPU 任務的，僅適用於對稱多處理器（SMP）系統。它包括一種機制，可以停止在特定 CPU 上運行的行程並將其遷移到另一個 CPU。
* **Deadline** 類型的任務必須在規定的截止時間內完成。使用此策略的任務會定義一個截止時間，在該時間之前任務必須完成執行。
* 在 `rt_sched_class` 當中，有兩種 scheduling policy，分別是 `SCHED_FIFO` 和 `SCHED_RR`，這兩者非常相似。
* 在 `SCHED_FIFO` 中，FIFO 代表 First in First Out。因此任務按照到達的順序執行。然而，如果有更高優先級的任務需要執行，它將被優先執行。
* `SCHED_RR`（round robin）與 FIFO 相似，但區別在於 RR 有 timeslice。它使用輪轉的方法循環調度所有具有相同優先級的任務。每個任務只能運行一個最大固定時間片。這會讓排程更具有 Liveness 的特性。
* `SCHED_NORMAL` 和 `SCHED_OTHER` 是用於==普通任務==的 scheduling policy，會使用 CFS（Completely Fair Scheduler）排程。`SCHED_BATCH` 與 `SCHED_NORMAL` 相似，但它會更少地搶占 CPU 的資源。
* `SCHED_IDLE` 用於非常低優先級的任務，幾乎任何任務都可以搶占使用此策略的任務。
#### 早期的 Linux 核心排程器
在 Linux 核心的 v0.01 版本中，所有任務都通過一個 ==array== 表示。這個 array 不僅是所有任務的列表，也是 runqueue。這個 array 的長度為 `NR_TASKS`，即 64。空條目表示為 `NULL`。
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> runnable 10 </td>
<td bgcolor="skyblue"> runnable 15 </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> runnable 5 </td>
<td bgcolor="lightcoral"> sleep 12 </td>
</tr>
</table> >];
}
```
其演算法很簡單
1. 逆向走訪整個 array，調度第一個可運行且具有最大 timeslice 的行程。
2. 如果沒有這樣的進程，那就會重置所有任務的 timeslice，並將當前 timeslice 的一半==添加到休眠任務的 timeslice 中==。
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> runnable 10 </td>
<td bgcolor="skyblue"> <b>runnable 15</b> </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> runnable 5 </td>
<td bgcolor="lightcoral"> sleep 12 </td>
</tr>
</table> >];
}
```
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> <b>runnable 10</b> </td>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> runnable 5 </td>
<td bgcolor="lightcoral"> sleep 12 </td>
</tr>
</table> >];
}
```
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> <b>runnable 5</b> </td>
<td bgcolor="lightcoral"> sleep 12 </td>
</tr>
</table> >];
}
```
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> runnable 0 </td>
<td bgcolor="lightcoral"> sleep 12 </td>
</tr>
</table> >];
}
```
```graphviz
graph G{
1[shape=none,margin=0,label=<
<table BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
<tr>
<td bgcolor="skyblue"> runnable 15 </td>
<td bgcolor="skyblue"> runnable 15 </td>
<td bgcolor="grey"> NULL </td>
<td bgcolor="skyblue"> runnable 15 </td>
<td bgcolor="lightcoral"> sleep 20 </td>
</tr>
</table> >];
}
```
這個過程會不斷進行，直到任務完成時，它就會離開 array，並將該元素設置為 `NULL`。
#### O(n) 排程器
在這個階段，所有任務都存在一個==連結串列==當中。當 Linux 需要選擇一個任務進行執行時，它會走訪每個任務，並為每個任務給予一個 goodness score。得分最高的任務將會獲得 CPU 資源。當任務的執行時間耗盡時，它就會被搶占，然後 CPU 會運行另一個任務。
```graphviz
digraph shuffle {
rankdir = "LR"
node [shape=box, style=filled];
node0 [shape=none, label="", fillcolor="white", color="black"];
// Define nodes with different colors
node1 [label="task1", fillcolor="white", color="black"];
node2 [label="task2", fillcolor="grey", color="black"];
node3 [label="task3", fillcolor="white", color="black"];
node4 [label="task4", fillcolor="white", color="black"];
node5 [label="task5", fillcolor="white", color="black"];
// Connect the nodes
node0 -> node2;
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
}
```
## TODO: 檢閱學員對於 Linux 核心 CPU 排程器的分析
> 探討以下:
> * Kuanch, devarajabc $\to$ [開發紀錄](https://hackmd.io/@sysprog/rkJd7TFX0)
> * yenslife $\to$ [開發紀錄](https://hackmd.io/@sysprog/rysYj43ER)
> * ShawnXuanc $\to$ [開發紀錄](https://hackmd.io/@sysprog/SyTH65LUC)
>
> 在上方開發紀錄提出你的疑惑並參與討論。
### Linux 核心專題: CPU 排程器研究 (Kuanch, devarajabc)
* 針對《Demystifying the Linux CPU Scheduler》第 2 章排程器的 Response Time (Interactive) 與 Throughput 做補充。
> 為何 Response Time 與 Throughput 需要做取捨?
> 如果想要提升作業系統的互動性 (interactive)，那麼每當使用者輸入指令的時候，CPU 都需要立刻暫行當下執行的任務，並且切換到其他任務回饋給使用者。這是搶占式多工 (preemptive multitasking) 的例子。在 《Demystifying the Linux CPU Scheduler》34 頁有提到
>
>>Every time the scheduler determines to context switch, the CPU becomes idle and are unoccupied by any task.
>
> 因此，會降低 throughput 的原因是 context switch 當中造成 CPU 短時間閒置，任務被打斷是表面原因。
* 提出建議，比較 FIFO 與 RR 兩者 Scheduling Policy 的差異，並探討其 Fairness 與 Liveness。
> Fairness 意思是相同優先權的任務會享有==相同的 CPU 時間==。
> Liveness 意思是每個任務，無論優先權高低，最終都會得到 CPU 的資源。
>
> 由於兩者 Scheduling Policy 都是優先權高先執行，享有 CPU 的資源比較多，因此在 Fairness 上，兩者表現一樣。
>
> 而由於 RR 每隔一個 timeslice 就會切換一次任務，就能夠讓比較低優先權的任務更有機會執行， Liveness 的特性比較好。而因為 FIFO 在執行完一個任務後才會接續執行下一個任務，因此 Liveness 的特性與 RR 相比，就沒那麼好。
* 在探討 Task Migration 的時候有提到因為在 UMA 的設計裡每個 CPU Core 存取每個記憶體的時間是一樣的，因此遷移成本可能遠小於 NUMA。 但我持不同的觀點。
> NUMA 雖然會提高 migration 的成本，但因為在 NUMA 可以涵蓋到大量的處理器，每個處理器會比其他處理器更接近某些記憶體，讓記憶體存取速度比其他部分更快速，因此在高效能運算系統也很常見。因此UMA + NUMA 的混和版本是否會犧牲掉這點，也應該考慮。
### Linux 核心專題: CPU 排程器研究 (yenslife)
* 回答同學在 Stop-task 上 task migration 的疑問。
>如果今天系統負載較低，它會關閉任意 secondary CPU，以降低能源消耗。在關閉該 CPU 之前，一定會執行 Stop-Task 類別的任務。如果你關閉的那顆 CPU 上面剛好在執行其他任務，那 stop-task 就需要把上面的任務 migrate 到其他 CPU 完成，因此需要任務遷移。
## TODO: CPU 排程器實驗重現
重現《Demystifying the Linux CPU Scheduler》第 7 章的實驗。
* Same Nice v.s. Different Nice
* FIFO v.s. RR Scheduling Policy
### 開發環境
```
$ gcc --version
gcc (Ubuntu 13.2.0-4ubuntu3) 13.2.0
$ uname -mrs
Linux 6.5.0-41-generic x86_64
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU(s) scaling MHz: 36%
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
```
### 事前準備工作
1. **更新 Linux 至版本 6.1 或更高版本。**
在 `Linhoward0522` 的排程器研究中，有相關的[操作說明](https://hackmd.io/@sysprog/BJh9FdlS2#%E6%9B%B4%E6%96%B0%E8%87%B3-Linux-v61)。
2. **下載 Scheduler Analyzer**
需要前往 [sched-analyzer](https://github.com/qais-yousef/sched-analyzer) 下載。在生成 trace file 以後，我們可以將其放到 [Perfetto](https://perfetto.dev/docs/) 從而視覺化排程器的行為。
### FIFO v.s. RR Scheduling Policy
本實驗旨在展示 FIFO 和 RR 調度策略之間的差異。這兩種策略都屬於 real-time 的 scheduling class。為了詳細介紹這兩種 scheduling policy，我會進行三個實驗。
1. **展示 FIFO 和 RR 在相同優先權任務下的排程狀況**
我們預期在 FIFO 策略下，每個任務只有在前一個任務終止後才會被選擇執行；而在 RR 策略下，每個任務在前一個任務超過給定的 timeslice 以後都有機會執行。我將會使用以下 configuration file。
```c
{
"proc": [
{
"comm": "cpu_bound",
"cpus": "3",
"name": "fifo",
"policy": "fifo",
"policy_detail": "99",
"spawn_cnt": 3
},
{
"comm": "cpu_bound",
"cpus": "2",
"name": "rr",
"policy": "rr",
"policy_detail": "99",
"spawn_cnt": 3
}
]
}
```
2. **展示 FIFO 和 RR 在不同優先權任務下的排程狀況**
因為所使用的任務優先權必須不同，因此須給每個不同優先權的任務寫 configuration file。
```c
{
"proc": [
{
"comm": "cpu_bound",
"cpus": "3",
"name": "low priority (fifo)",
"policy": "fifo",
"policy_detail": "97"
},
{
"comm": "cpu_bound",
"cpus": "3",
"name": "medium priority (fifo)",
"policy": "fifo",
"policy_detail": "98",
"spawn_cnt": 2
},
{
"comm": "cpu_bound",
"cpus": "3",
"name": "high priority (fifo)",
"policy": "fifo",
"policy_detail": "99"
},
{
"comm": "cpu_bound",
"cpus": "2",
"name": "low priority (rr)",
"policy": "rr",
"policy_detail": "97"
},
{
"comm": "cpu_bound",
"cpus": "2",
"name": "medium priority (rr)",
"policy": "rr",
"policy_detail": "98",
"spawn_cnt": 2
},
{
"comm": "cpu_bound",
"cpus": "2",
"name": "high priority (rr)",
"policy": "rr",
"policy_detail": "99"
}
]
}
```
Sign in with Wallet
Connect another wallet