# Demystifying the Linux CPU Scheduler

# 1 Basics of the Linux Kernel
## 1.1 OS

## 1.2 A gerneral overview
### 1.2.1 System calls
- x86 code selector 用 2 bits 表示 CPL (Current Privilege Level)
- 0: kernel mode
- 3: user mode
- 每次系統呼叫都會改變這個值
- :::warning
只使用 0, 3 可能跟 hamming distance 有關?

### 1.2.2 File Systems
### 1.2.3 A different kind of software
- kernel 會使用自己實作的標準 C 函式庫中的函數
- 標準函數效率不高
- 需要特製化
- `kmalloc` 需要一段連續記憶體， `malloc` 沒有這個限制 (over commit)

### 1.2.4 User and kernel stacksmusic
- kernel 預設自己不會有問題，所以沒有 error catching
- 每個行程有兩個 stack ，分別位於 kernel space 和 user space
- user space stack 可以動態擴展 (on-demand paging)
- kernel space stack 不能自行擴展，大小固定
- 單位是 `order of the page size` ， 在 32 與 64 位元一頁都是 4KB
- 32 位元系統， `order = 1` ， stack size = (4KB << 1 = 8KB)
- 64 位元系統， `order = 2` ， stack size = (4KB << 2 = 16KB)
- 頁面需要實體記憶體連續
- 系統運行一段時間後，會隨著 stack 釋放導致記憶體變得碎片化，難以找到連續的記憶體
- 曾嘗試將 kernel stack 縮小為單一頁面，但導致許多 stack overflows
- :::warning
1. reduce the stack size to one page 這邊是指 4KB 的單一頁面？
2. hard to find two physically contiguous unallocated pages / the standard settled on two pages 這邊是特別指 32 位元?
3. 釋放 stack 會導致碎片化，但每個 stack 頁數固定，所以做好對齊其實不會有碎片化問題？還是我對分頁理解有誤?
4. 嘗試發 patch

        第九頁
        
        討論到系統長時間執行難以分配足夠的連續空間給 kernel stack 的問題
        ...hard to find two physically contiguous unallocated pages ... 
        ... the standard settled on two pages ...

        根據我對前文 order of page size的理解
        32 位元電腦應該是 2 頁
        64 位元電腦應該是 4 頁

        可判斷這邊應該是用 32 位元電腦來討論
        但沒有特別提示
        是否該特別標示這邊以 32 位元電腦為例子
        或是改成 "足夠的頁數"
        或是我理解錯誤

:::
- kernel stack overflow 可能導致損壞 thread_info 結構，讓核心無法辨識該 process ， 導致 memory leaky ，接下來會逐漸破壞鄰近核心資料，若沒發生 panic ， 最終可能導致核心發生不可預期的行為或崩壞
- VMAP_STACK ，核心配置記憶體的函式會增加保護頁面，能更好的偵測並觸發 panic
- 把 thread_info 從 stack 底部移動到 task_struct ，保護其不被破壞
- :::warning
Q: 為什麼 vmalloc 能讓 stack 可以不再需要是連續的記憶體區塊
A: vmalloc 的部份是因為 kernel 可以讓一些不連續的 physical page 映射成一段連續的 virtual 記憶體空間 by `rota1001`
:::
### 1.2.5 Monolithic kernel vs. Microkernel design

## 1.3
### 1.3.1 Processes and thread
#### process vs thread
- process
- 一個正在執行的程式實體
- 擁有唯一的位址空間，與其他 process 隔離
- 試圖存取未分配給他的記憶體會導致 segmentation fault

- thread
- 一條單一的執行流程
- 每個 process 可以包含多個 thread ，共享相同的位址空間
- TGID vs PID
- 每個 thread 會被分配獨立的編號稱為 PID (Process Identifier)
- 屬於同一 process 的所有執行序，會被歸類在同個 TGID (Thread Group ID)
- 一個 process 中，每個 thread 的 TGID 就是 thread group leader 的 PID
- `getpid()` 會取得 `TGID`
- `gettid()` 會取得 `PID`
#### task_struct
- `thread_info` 放在 `task_struct` 的開頭，可透過強制轉型成 `struct thread_info *` 解決 header dependency challenge

    /*
	 * For reasons of header soup (see current_thread_info()), this
	 * must be the first element of task_struct.
	 */

:::warning
`struct task_struct thread_group` 似乎不存在

它已經在 [Commit 8e1f385](https://github.com/torvalds/linux/commit/8e1f385104ac044f1552686ad6e1cbc71cc05a30) 被移除

kill task_struct->thread_group

The last user was removed by the previous patch.

嘗試發了 patch
:::

#### PID hash table

### 1.3.2 List implementation
lab 0 老熟了吧

### 1.3.3 Scheduling
- round-robin 會在固定時間強制 context_switch
- 未被執行完就丟進 queue 排隊
- 時間片段太長會變成 FIFO
- 排程器原理示範的就屬於 round-robin?
- thread 被稱為 LWP 就是因為不用切換地址空間，少了部份的切換成本

### 1.3.4 Task lifetime
- 等待某資源的時候可以 sleep ，可以在一定的時間或收到資源後醒來
- 主動讓出 cpu 資源可以 sched_yield
- zombie state
- process 中止之後會進入
- 在 parent process 中止或 `wait()` 前都是這個狀態
- 資源不會被立即釋放，直到 parent process 呼叫 `wait()` / `waitpid()`
- parent process 可以訪問 zombie 的一些訊息
- 若 parent process 未呼叫 `wait` 就退出，zombie 就會變成 orphan
- orphan process
- 被 init process 收養
- init process 會定期 `wait()` 來釋放這些殭屍

#### state of process
- `TASK_RUNNING`
- 可執行 / 正在執行
- `TASK_INTERRUPTIBLE/ TASK_UNINTERRUPTIBLE`
- process 在等待(時間或資源到了)
- 可 / 不可 透過訊號喚醒
- `__TASK_TRACED`
- 表示此任務正在被其他程序追蹤
- `__TASK_STOPPED`
- 表示任務已被停止且無法被排程執行。這種情況通常是因為收到停止信號，或是正在被追蹤的程序發出的某些信號
- `EXIT_ZOMBIE`
- `EXIT_DEAD`
- `EXIT_ZOMBIE` 被 `wait()` 之後的狀態

# 2
## 2.1
### 2.1.1

- response time vs throught put
- Fairness and Liveness
- fairness 代表每個任務根據其優先度，都要多少獲得一些 CPU 時間， Proportional Share Schedulers 會提供這種 fairness
- Liveness 相反是 starve ，如果長時間被高優先權霸佔 CPU 就會餓， Liveness 確保 ready 任務能在有限時間取得 CPU 資源
- :::warning
所以 fairness 強調每個任務都會獲得一定的 CPU 資源
liveness 強調等待不會太久？
:::
- Real-Time vs. Non-RT
- Power Efficiency
- 找出耗電低的任務
- 動態調整 CPU 頻率
- desktop 省電
- prioritize tasks that require less power
- :::warning
對於要增加低負載任務的原因不是很能理解
目前對它的猜測：

cpu 被降頻了，資源變少
io 變慢是不能接受的，所以為了維持原本的體驗要把佔比增加
高計算量工作變慢使用者能理解，所以就讓它佔比變少

這個理解現在最大的 bug 是為什麼低負載任務佔比都會增加

:::
- server
- 執行在電力與冷卻資源有限的地方
- :::warning

:::
- 關鍵字
- schedutil
- PELT
- DVFS
- 不只挑選任務的排程器

### 2.1.2
- 根據優先順序有不同的排程策略
#### scheduling class
1. stop
- 在關機或 cpu 熱插拔時強制中止所有其他任務
- 僅適用於 SMP
2. deadline
3. real-time
- 即時任務擁有至少 32 級的固定優先權
- 持續執行直到主動讓出或是被高優先權的搶佔
4. fair
- 使用 CFS
- default
5. idle-task
- 閒置任務

#### scheduling police
- `SCHED_DEADLINE`
- real time
- `SCHED_FIFO`
- `SCHED_RR`
- 一般任務
- `SCHED_NORMAL`/`SCHED_OTHER`
- CFS
- `SCHED_BATCH`
- preempt 較低的 `SCHED_NORMAL`
- `SCHED_IDLE`

## 2.2
### 2.2.1 Early Linux Scheduler
#### 運行流程
1. 將 c 設成 -1 ， next 設成 0
2. 遍歷所有狀態為 TASK_RINNING 的 task ， 不斷跟 c 比較，尋找 time slice 最大的當下個任務
3. 若 c 為 0 ，代表所有 TASK_RINNING 的 task time slice 都是 0 ，重新排程
- 重新排程的時候會將剩下的 time slice / 2 + priority ，因為猜測會有剩下時間的很可能是互動行任務
:::warning
c 初始化為 -1 的意義是讓真的沒有 task 的時候，不排程直接去 idle task?
:::
#### 缺點
- 足以在單核心系統上順利運作大多數工作
- 沒有設計用來處理 multiprocessor systems
- 缺乏 cache affinity, concurrency control

### 2.2.2 O(n)
#### task_struct
- has_cpu: 是否已經被分配到某 CPU
- processor: 處理該任務的 CPU
- policy
- rt_priority
- run_list: list_head 用來連接 runnable list
:::warning
1. processor 應該可以取代 has_cpu 的功能
2. >run_list : Runnable tasks belong to the runnable list, denoted by run_list,
as shown in Figure 2.4.

這邊如果直接提到 list_head 可能會更好理解？
:::

#### goodness 計算
1. SCHED_YIELD 會直接回傳 -1
2. 分成 SCHED_OTHER 和 SCHED_RT 處理
- SCHED_OTHER
- p->counter 為 0 回傳 0
- weight = p->count + 20 - nice
- 若在同個 processor 執行有 processor affinity 加分
- 與前一個任務共享記憶體空間加分 (mm)

- SCHED_RT
- weight = 1000 + p->rt_priority
#### schedule
對所有 can_schedule 任務算 goodness 然後找最大的當下個任務

#### 缺點
- 共用一個 runqueue ，會因為 lock 造成效能問題
- 每次都算 goodness 偏久
### 2.2.3 O(1)
:::warning
- 是否考慮把 Figure 2.5 放到跟 `shown in Figure 2.5` 同一頁？ 2.6 也是
:::

- 每個 cpu 都有自己的 priority array
- `MAX_PRIO = 140`
- 利用 bitmap 快速判斷各個佇列中是否有任務，利用 `sched_find_first_bit()` 快速找到第一個 1
- 維護兩個 priority array
- active
- expired
- time slice 用完被移到 expired queue 時才重新計算 timeslice
- active 沒東西， expire 和 active 交換
- work stealing
- 閒置 CPU 從別人的 priority array 拿工作
- imbalance exceeds 25% 才會工作遷移
#### priority
- static priority
- 對應於 nice 值， $[-20, 20)$
- bonus priority
- 根據互動性， $[-5, 5]$
- sleep 越久，代表互動性高，提昇優先級 (priority - 5)
- dynamic priority
- statice + bonus

#### nice 值

#### 缺點
- Interactive tasks and heuristics
- dynamic priority 根據 sleep 時間計算
- 高優先級的任務，比較容易被標記為互動性任務，而低優先級的任務則較不容易
- 可能導致非互動性任務被標記成互動性任務

- 互動性表現不佳（對使用者反應慢）
- 背景程序的處理量（throughput）較低

### 2.2.4

## 2.3 CFS
:::warning
55 頁的 "lowest virtual runtime"
與
56 頁的 "highest waiting time"

應該都是指 58 頁的
"task with the least run time"?
:::

### 2.3.1 Proportional-Share Scheduling
- 按權重比例分配佔用 cpu 的比例
- $c_i=\frac{W_i}{\Sigma_WW}\cdot\Sigma_cC$
- virtual rumtime
- 某個任務執行的虛擬時間，根據權重會有不同的成長速率
- 權重 (nice) 越大，成長速率越小
- 每次選擇已執行時間最小的執行
- 新建立的任務會被放在 runqueue 最後面，要等之前的任務執行完才換它
:::warning
Q: 這是指給它一個比原本的尾端還大一些的執行時間，讓它可以在最後面？)
Q: [簡報 47 頁](https://docs.google.com/presentation/d/1qDSFOfhGF-AX3O8CNzoAkQr_5ohr0nMVDlNfPnM9hOI/edit#slide=id.p21) 說他會被設成 minimum current vruntime(`min_vruntime`)
跟書中的敘述不太一樣
>Newly created tasks are assigned a fictitious run time clock that,
regardless of their weight, puts them at the end of the runqueue.
:::
- 被阻塞的任務會獲得一個 I/O compensation 讓它跑到 runqueue 的前面
:::warning
Q: 把該任務的 virtual runtime 減一個數值？
A: 這在 2.3.4 有寫
:::

### 2.3.3
:::warning
探討定點數運算時

:::

### 2.3.4
- 新的任務加入 runqueue 時， vruntime 會被設定
- 若是一個睡眠中的任務被喚醒， vruntime = max(self, 當前最小值)
:::warning
[簡報 52 頁](https://docs.google.com/presentation/d/1qDSFOfhGF-AX3O8CNzoAkQr_5ohr0nMVDlNfPnM9hOI/edit#slide=id.p26) 說他還會被減去一個值?
跟書中 69 頁的敘述不太一樣
>the scheduler checks that its virtual runtime is at least equal to the current minimum; if it is not, then it is set to the minimum and the task is inserted into the runqueue.
:::
- 當新的任務透過 fork() 建立並插入 runqueue 時，它會繼承父任務的 vruntime