Linux CPU Scheduler Notes

contributed by < steven1lung >

Repo : https://github.com/steven1lung/cfs-visualizer-react
Website : https://steven1lung.github.io/cfs-visualizer-react/

Chapter 1 Basic of Linux Kernel

我覺得 Linus Torvalds 解釋的作業系統很精準：「作業系統唯一的任務是要幫助程式運行，作業系統一直都在等著程式向它要求資源。」作業系統可以看成是硬體跟使用者的仲介，工作包含管理硬體資源跟應用程式，而應用程式會再與使用者進行互動。而作業系統核心可以執行特權指令，讓每個任務都可以安全地被執行。

作業系統核心會在開機的時候被初始化，並且透過 boot loader 載入到記憶體中，核心從開機載入後就會一直待在記憶體中。記憶體儲存核心重要程式碼的位置也會跟一般的程式分開，防止應用程式或是其他作業系統程式對重要部分進行存取。

核心的任務是要管理硬體資源，像是操作 CPU、記憶體階層、I/O 裝置等等。為了達成這些任務，核心要有權限對所有的資源進行存取。所以將 kernel code 跟 user application code 分開。實作的方式為：

1. 核心的 image 會被存到 RAM 中低或是高的位址
2. 剛剛儲存位址隔壁有一塊已經被定義的 RAM 會被留給核心
3. 剩下的 RAM 可以被使用者自由存取

存核心的區塊稱為 kernel space，而存使用者資料的區塊稱為 user space。

因為有這個機制，user space 會被高權限的系統管理。每個行程可以運行在 user mode 或是 kernel mode。User mode 下運行的行程可以使用「System Call」來使用高權限的功能，可以將 system call 視為使用者跟核心之間的 API。當一個行程呼叫 system call：

1. 會暫時運行在 kernel mode 下
2. 執行需要高權限的動作
3. 再切換回 user mode

舉例來說，x86 架構的兩位元 code selector (cs) 會顯示現在的權限等級 (current privilege level) 。0 代表 kernel mode，3 代表 user mode，每個系統呼叫都會暫時更改 cs 裡面的值。

Linux 核心是一塊非常特別的軟體，其中一個特性是核心自己沒有 error checking，因為核心非常信任自己，核心裡的函式都會被當成是沒有錯誤的。因為錯誤偵測跟處理需要花費不少心力，所以核心裡都是使用 assertion 來確認硬體跟軟體的一致性，一旦出現錯誤核心就會暫停或 panic()。但是程式錯誤或是硬體錯誤還會有機會在核心出現的，例如：在 user space 操作 null 指標會產生一個 segmentaion fault，而在 kernel space 操作 null 指標或產生一個 oops。核心產生 oops 之後，情況嚴重點還會 panic() ，這下這個核心就不能被信任跟繼續執行，所以通常都會重啟，以免出現破壞記憶體的問題。

核心有不同的設計方式，以光譜兩端為例：一邊會是 monolithic kernel，而一邊是 microkernel。在 monolithic 的設計裡，每個核心的服務都位在核心裡，而相反的，microkernel 目的是要將核心的大小縮小，盡量將大部分的服務移到 user space，只在 kernel space 留下最重要的部分。

Linux 的設計偏向 monolithic kernel，所以許多程式都在 kernel space。

現在也有 hybrid 處在兩種概念之間的設計，像是 macOS。

Microkernel 會這樣做的原因不外乎就是將受到信任的程式碼減少，因為信任的程式碼減少，所以需要做的 assertion 就會減少，不像是 monolithic 需要考慮到許多因素。另一個原因是將服務移到 user space 比較有維護性，可以做到直接在核心上開發測試，直接將要測試的服務編譯完後重啟就好了。

但是 Monolithic 還會一直被留著是有原因的，因為 microkernel 的效率太差。Monolithic 可以直接跟底層硬體溝通，而 microkernel 因為將服務移到 user space，所以會有許多行程之間的溝通，造成這個問題有兩個主因：

1. 呼叫大量的 system call
2. 許多 context switch

Linux 核心試著解決這種可擴充性的問題是透過 kernel modules，可以在執行期間進行 insmod 跟 rmmod 載入跟移除核心模組。但因為模組是運行在 kernel space，所以在開發的時候會比較困難。

但是 kernel modules 也不能完全達到 microkernel 的功能，像是要在執行期間替換一個排程器是不允許的，除非有多個排程器可以在 kernel code 進行切換。

所以 modules 並不是要實作核心的程式，而是當一個擴充額外功能的工具。

Chapter 2 The Linux CPU scheduler

排程器的演化：

Brief History of Linux CPU Scheduler

1. 最早期的排程器
2. $O(n)$ 排程器
3. $O(1)$ 排程器
4. CFS

最早的排程器

當初這個排程器被設計出來並不是為了應付多處理器的架構，那時候使用了最簡單的設計。當初只使用了單一佇列存放任務，並迭代這個佇列來選取任務。在那時這個方法可行，是因當初有限制行程數量 (NR_TASKS 最初被設為 64)。

運作方法如下：

1. 在 runqueue 中以反向順序找尋最大 runtime 且大於 0 的行程。
2. 如果沒有找到，就重置所有行程的 runtime，並且會給目前在睡覺的行程加上一半 current time slice 的時間。

$O(n)$ 排程器

$O(n)$ 排程器跟最早的排程器其實概念差不多，會取這個名字是因為挑選任務要迭代過整個佇列，為了區隔在 Linux v2.6 出現的

$O(1)$ 排程器，這裡就命名早期的實作為

$O(n)$。不同的地方是這邊多了優先權的概念，從最高到最低為：即時行程（realtime process）、互動式行程（interactive process）、批次行程（batch process）。優先權越高的行程通常會拿到越大的 timeslice。

$O(n)$ 排程器介紹了一個新的概念：優先權，在程式碼裡使用的名字是：goodness。越「好」的行程優先權越高。

好人不長命，禍害遺千年的概念 xD。好的行程一下就被挑出來執行掉了。

要注意到這邊的 goodness 跟 nice 是不一樣的！

$O(1)$ 排程器

會取名

$O(1)$ 不外乎就是因為對任務的挑選跟加入所耗費的時間為

$O(1)$，上一個

$O(n)$ 排程器在處理數量小的行程時還不錯，但是若行程數量多起來，會浪費許多時間來迭代過如此多的行程。

並且 O(n) 排程器也在 SMP 系統有些困難：

1. 單一 runqueue

   造成行程被分配到不同處理器時會有大量的 cache miss (affinity)。

2. 單一 runqueue lock

   執行效率會因為一個 global 的 lock 而拖慢。

3. 無法搶佔正在執行的行程

   在 pre-2.6 linux 版本，搶佔是不被允許的。造成一些低優先權行正在執行時，有許多高優先權行程在等待。

在

$O(1)$ 排程器中有一個 global scheduler，會在多個處理器 runqueue 中進行 load balance（work stealing）。這個策略是透過初始化時，各自佇列上的工人會先挑選自己住列的任務，如果沒有任務可以挑選就會變成「小偷」跑去其他住列偷任務。

$O(1)$ 排程器的優先權陣列實作是透過 bitmap 來達成，每個優權權等級都會有一個住列（共 MAX_PRIO (140) 個住列），所以要使用為元表達 140 個優先權，一個 word 32 位元，所以 BITMAP_SIZE 就為 5。Bitmap 作用是要指出哪些優先權是空的（1 為有任務，0 為空的住列），來達到快速找出任務的效果。

$O(1)$ 排程器中有兩個優先權陣列：Active 跟 Expired。Active 會儲存目前還有剩餘 timeslice 的行程，Expried 會儲存用完 timeslice 的行程。任務的排程會在 Active 中執行，若優先權最高的住列裡有多個行程，那就會使用 round-robin 來執行。會一路執行到 Active 裡的行程都跑完 timeslice 並加入到 Expired 中，這時候兩個優先權陣列就會互換，再繼續執行下去。

優先權的計算在這裡會依據任務的表現，一個行程的優先權是由 static priority 跟 bonus priority 去計算的。Static 對應到 nice 值，從 -20 到 +19。Bonus 則是從 -5 到 +5，並且是被任務的行為決定的：如果行程一直都在睡覺，那 bonus 會被設為 -5 提高優先權，反之亦然。

但是

$O(1)$ 排程器依舊存在著一些問題：因為 nice 值高的行程佔用太多處理器，造成許多抗議。所以

$O(1)$ 依賴一個最小的執行時間 "jiffy" 來分配 timeslice，jiffy 的大小取決於 tick rate。但是現今處理器都可以達到 1000 Hz，使得 jiffy 只有 1ms，就造成 nice 值 19 的任務 timeslice 只有 1ms，導致排程器很快又要挑選下一個任務。

還有問題是 starvation，低優先權的任務要等到所有高優先權任務執行完，才有機會被執行，導致一些即時行程會因為遲遲等不到處理器而緊張（priority inversion）。

Completely Fair Scheduler

這邊要先知道 RSDL 排程器，可以去看老師的書 2.2.4 章，簡潔明瞭。

CFS 跟 RSDL 不同的地方在於 CFS 並沒有使用固定的 timeslice，也沒有使用任何 heuristic 函示來計算優先權，而是試著去在硬體上製作一個理想的多工 CPU。假設我們有一個很小很小的 timeslice，那我們就可以很理想地分給每個行程

$\frac{1}{n}$ 的處理器時間。

但是真正的處理器會在這種排程下做非常多的 context switch，所以現實世界不太可能會有這種完全平等的演算法。退而求其次的方法是使用 virtual runtime（vruntime），代表每個行程在理想情況下應該執行的時間。CFS 就是透過 vruntime 來選擇下一個任務，目標是維持每個任務的 vruntime ，讓每個 vruntime 都差不多大。所以 CFS 會挑選 vruntime 最小的任務來執行。

執行完的任務會將 vruntime 加上

$time\times weight$，weight 的值會依據優先權決定。CFS 會紀錄一個最小的 vruntime，也就是任務佇列中最小的 vruntime，來達到快速找到下一個執行目標。總而言之，CFS 會挑選最小 vruntime 的任務，並且 dynamic timeslice 會依據上述的理想排程方法計算。

• nice 跟實際執行時間有關
• vruntime 會被保持平衡

Chapter 3 Implementation of the Linux scheduler

參考資料：

1. 老師的書
2. https://elixir.free-electrons.com/linux/v5.10/source/include/linux/sched.h
3. https://developer.ibm.com/tutorials/l-completely-fair-scheduler/

CFS 機制介紹

跟上面

$O(n)$ 或是

$O(1)$ 排程器所不同的地方是，CFS 使用的資料結構並不是一個 queue，而是一個紅黑樹。會使用任務的 virtual runtime 來產生紅黑樹，並且每次都挑選最小的 virtual runtime 來執行，達到公平的目的（因為 vruntime 就是每個任務理想中要被執行的時間，所以最小 vruntime 的任務就會是目前為止理想執行時間最少的任務）。

紅黑樹的特性這邊就不做介紹了，網路上很多。

排程器會使用到一些參數，這些參數通常都會存在 task_struct 裡面的 sched_enitity 中，sched_enitity 裡面會有 load_weight、
struct rb_node run_node、vruntime 等等的重要資訊。

計時器會在每個 tick period 透過 do_timer() 跟 update_process_times() 去更新系統的 uptime 還有各個行程的資訊。

在 update_process_times() 裡會呼叫到 scheduler_tick()，就是排程器每次更新 task 資訊的地方。scheduler_tick() 有幾個重要的呼叫：

1. sched_clock_tick()

   更新 per_CPU sched_clock_data。

2. update_rq_clock(rq)

   更新 runqueue 裡的 clock_task，會在 update_curr() 使用到 clock_task。

3. task_tick(rq, curr, 0)

   更新每個 task 的資料。

task_tick 會依照在 sched_class 所定義好的函示執行對應的動作，這邊就以老師的書裡的例子做使用，就會是 .task_tick = task_tick_fair (p.71)，所以會執行 task_tick_fair。

task_tick_fair 會從傳入的 rq 拿到 sched_entity，並且透過一個 for 來對每一個 entity 進行更新。

for_each_sched_entity(se) {
    cfs_rq = cfs_rq_of(se);
    entity_tick(cfs_rq, se, queued);
}

真正去更變更一個 enitity 的 vruntime 是 enitity_tick() 會呼叫到的第一個函式，update_curr()。更新完 vruntime 就會檢查現在的 enitity 有沒有用完分配的時間或是有沒有其他 entity 需要被執行。

一個 enitity 的 vruntime 的更新會發生在 update_curr() 中，所執行的運算如下：

$$vruntime=vruntime+weight\mathrm{\_}of\mathrm{\_}nice\mathrm{\_}0\ast \frac{delta\mathrm{\_}exec}{task\mathrm{\_}weight}$$

其中的 delta_exec 是目前這個 enitity 所執行的時間，透過 curr->exec_start 減去現在的時間得到。而 weight 計算的公式是：

$weight=\frac{1024}{{1.25}^{nice}}$，在 linux kernel 是直接用陣列將每個 nice 值都對應到一個權重。

分配給一個任務的 timeslice 是在 entitiy_tick() 最後幾行計算的，透過呼叫 check_preempt_tick()，而 check_preempt_tick() 會呼叫 sched_slice(cfs_rq, curr) 去計算要分配給任務的 timeslice。

$$slice=target\mathrm{\_}latency\ast \frac{task\mathrm{\_}weight}{total\mathrm{\_}weight}$$

這邊要注意的是要計算出 timeslice 跟 vruntime 所呼叫的函式都是 calc_delta() 因為這兩個都差別只有傳進去的參數不同，運算是一樣的。target_latency 是每個任務執行一次所需要的最小時間。

sum_exec_runtime 會紀錄任務目前所執行的時間

模擬 CFS

這邊會列出一些等等會使用到的變數：

1. sched_latency

   排程器的週期

2. sched_min_granularity

   一個任務最少會被執行到的時間

3. sched_wakeup_granularity

   剛醒來的任務的 vruntime 如果大於現在任務的 vruntime，照理來說會選擇原本的任務繼續執行，但如果兩個任務 vruntime 之間的差距沒有超過 sched_wakeup_granularity 就會讓醒來的任務執行。

4. target_latency

   確保讓每個任務都執行到一次，所以會取

   $max(sched\mathrm{\_}latency,n\ast sched\mathrm{\_}min\mathrm{\_}granularity)$。

建立一個任務會需要三個參數，分別是：

1. Arrival Time
2. Burst Time
3. Nice value (-20~+19)

   這邊的 nice 值是在說明對系統友善的程度，nice 值越大，priority 越低。

之後會將建立的任務加入紅黑樹中，加入紅黑樹的動作是在 nr_running 被增加之前完成的，詳細程式碼在 kernel/sched/fair.c 中的 enqueue_task_fair。

當排程器需要進行排程時：

1. 挑選 vruntime 最小的任務，也就是在紅黑樹最左邊的節點。
2. 被挑選的任務會被從黑紅樹中移除。
3. 任務會被賦予 timeslice。

   $slice=target\mathrm{\_}latency\ast \frac{task\mathrm{\_}weight}{total\mathrm{\_}weight}$

當任務正在被執行時：

1. 更新被執行的時間 sum_exec_runtime += delta_exec

   delta_exec 就是現在的時間減去任務開始執行的時間：delta_exec = now - curr->exec_start。

2. 更新 vruntime
   vruntime += delta_exec/task_weight * 1024

   從上方的運算式可以看出來如果一個任務的 weight 比較大，那這個任務 vruntime 的增加速度就會比較慢，讓排程器更容易挑選到這個任務。

當一個任務的 timeslice 執行完時：

1. 如果任務還沒有完成，那他會被加回紅黑樹中。
2. 排程器進行排程。

範例

輸入：

3 11
A 1 3 0
B 2 4 -2
C 2 3 2

第一行的參數分別為任務數量跟總執行時間，接下來的每一行就是任務的名稱、開始的時間、需要執行的時間長度、nice 值。

A 會在第一個單位到達，並且總共要執行 3 個單位，nice 值是 0。以此類推…

Time = 0

Scheduler 開始，上述開頭有一些變數我們先假設為下列值：

• sched_latency = 6ms
• sched_min_granularity = 0.75ms
• sched_wakeup_granularity = 1ms
• target_latency = max(sched_latency,n * sched_min_granularity)

Time = 1

任務 A 被加入排程器（burst time = 3, nice = 0），A 的 timeslice：

$slice=target\mathrm{\_}latency\ast \frac{task\mathrm{\_}weight}{total\mathrm{\_}weight}=sched\mathrm{\_}latency\ast \frac{1024}{1024}=6$
這時候的 vruntime 是 0，因為根本沒有執行時間。

timeslice = 6, vruntime = 0

所以任務 A 會被選中，並且從紅黑樹中移除。

Time = 2

任務 B（burst time = 4, nice = -2）、C（burst time = 3, nice = 2）被加入排程器。

A 的 timeslice：

$slice=target\mathrm{\_}latency\ast \frac{task\mathrm{\_}weight}{total\mathrm{\_}weight}=6\ast \frac{1024}{1024+655+1586}=6\ast 0.31=1.86$

B 的 timeslice：

$slice=sched\mathrm{\_}latency\ast \frac{1586}{1024+655+1586}=2.91$

C 的 timeslice： = 1.2

$slice=sched\mathrm{\_}latency\ast \frac{655}{1024+655+1586}=1.2$

Time = 3

A 的 timeslice 跑完，但是 A 還沒有完成，所以會被加回紅黑樹中，新的 vruntime：

$vruntime=vruntime+\frac{delta\mathrm{\_}exec}{task\mathrm{\_}weight}\ast 1024=\frac{3-1}{1024}\ast 1024=2$

排程器會挑選任務 B 執行，給予 timeslice = 2.91。

Time = 4, 5

任務 B 還在 timeslice 內，也沒有新的任務被加入。

Time = 6

B 的 timeslice 跑完，且 B 還沒完成，所以會加回紅黑樹中，新的 vruntime：

$vruntime=\frac{6-3}{1586}\ast 1024=1.93$

排程器會挑選任務 C 並且將其從紅黑樹移除，給予 timeslice = 1.2。

Time = 7

任務 C 還在 timeslice 內，也沒有新的任務被加入。

Time = 8

C 的 timeslcie 跑完，且 C 還沒完成，所以會加回紅黑樹中，新的 vruntime：

$vruntime=\frac{8-6}{655}\ast 1024=3.12$

A: vruntime = 2
B: vruntime = 1.91
C: vruntime = 3.12

排成器會挑選任務 B（vruntime = 1.91 最小），並給予 timeslice = 2.91。

Time = 9

B 執行完成。

A 的 timeslice:

$slice=sched\mathrm{\_}latency\ast \frac{1024}{1024+655}=3.66$

C 的 timeslice:

$slice=sched\mathrm{\_}latency\ast \frac{655}{1024+655}=2.34$

A: vruntime = 2
C: vruntime = 3.12

排程器挑選任務 A，給予 timeslice = 3.66。

Time = 10

A 執行完成。

C 的 timeslice:

$slice=sched\mathrm{\_}latency\ast \frac{655}{655}=6$

排程器挑選任務 C，給予 timeslice = 6。

Time = 11

C 執行完成。

實作

使用 reactjs 來實作，詳細程式碼在這裡。目前將排程邏輯輸出在 console，可以透過 f12 看目前狀態。

Linux 紅黑樹

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

看了 rb_node 跟 list_head 之後，發現 Linux 風格的資料結構都不會包含 data，而是會將 rb_node 或是 list_head 這些資料結構包在一個更大的結構體裡面。

一個紅黑樹節點包含：父節點、左節點、右節點、顏色。而在 Linux 宣告的程式碼中，很巧妙地將父節點跟顏色一起宣告，使用 unsigned long __rb_parent_color 將指向父節點的指標跟自己的顏色合併。

透過 __attribute__((aligned(sizeof(long)))) 讓編譯器知道 struct rb_node 會對齊 sizeof(long)，這樣就會讓指標最右兩個位元是沒有使用到的，就可以把顏色的資料放進去其中一個位元中。

舉例來說，一個節點指標如果指向 0xF724315C ，這個位址轉成二進制會變成 ...1100，最右邊兩個位元會是 0，所以開發者就把這其中一個沒用到的位元拿來儲存顏色。

更詳細的內容可以去看我的紅黑樹筆記

紅黑樹

用 javascript 實作紅黑樹裡的插入跟刪除功能，節點的架構如下：

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.color = RED;
    this.parent = null;
  }
}

紅黑樹的需要考慮到的實作有：插入、刪除、平衡，插入是我花比較多時間的地方。

原本考慮想說找找看網路上有沒有現成的套件，但還是覺得自己寫會對這個資料結構更熟悉。

架構

function click_next_clock(){
    schedule_tick();
    add_tasks();
    update_new_tasks();
    schedule();
}

架構簡單來看會像上面那樣，每次點 next clock 按鈕意思是進入下一個 clock。每一個 clock 都會去呼叫 sched_tick() 更新 schedule entity 裡的一些資訊。如果有超過 timeslice 或是任務完成的話，就會呼叫 schedule() 選擇下一個任務。 如果有新的任務被加進 readyqueue 也會呼叫排程器，重新計算所有任務的 timeslice。如果有任務執行完 timeslice 但還沒有完成，就會更新 vruntime 並加回紅黑樹。

會執行的動作：

1. schedule_tick
   會更新目前正在被處理器執行的 schedule entity 的資料，例如：sum_exec_runtime。如果執行完成或是用完 timeslice 的情況會在這邊判斷等等要不要 schedule()。用完 timeslice 的任務也會需要重新計算 vruntime 並且加回紅黑樹中。
2. add_tasks
   會將這個 clock 要進入 ready queue 的任務初始化他們的 schedule entity 資料。
3. update_new_tasks
   上述所新加入 ready queue 的 schedule entity 中，我們會需要重新計算所有任務的 timeslice，並且將這些新加入的任務加入紅黑樹。
4. schedule
   如果目前任務執行完成（或是用完 timeslice），就會從紅黑樹拿最小 vruntime 的任務執行，並從紅黑樹中移除。

目前功能

• 有 3、4、5 個任務的預設任務選擇
• 紅黑樹的狀態是在每個 clock 的最後，也就是排程器挑選完任務並將其從紅黑樹移除後的紅黑樹
• 右上角會顯示目前正在執行的任務
• 左上角會顯示現在的 clock
• 左邊 clock 下方會顯示紅黑樹節點的資訊（透過滑鼠選擇要看的節點資訊）
• 每次排程邏輯會顯示在右邊 clock 下方，比如說這個 clock 有沒有觸發排程、timeslice 結束的任務加回紅黑樹的 vruntime 是多少、選擇到的任務給多少 timeslice 等等
• 每次排程的邏輯在整個模擬結束後會顯示在最下方的 result 裡

Chapter 4 Group scheduling and cgroups

普通的 CFS 會去從任務的角度去分配執行時間，比如說：使用者 A 有 49 跟任務，使用者 B 有 1 個任務，那這樣 CFS 會分配這 50 個任務各 1/50 的執行時間。但是這樣從使用者的角度來看，A 被分配到快所有的時間，這樣對 B 不公平。

這個章節介紹了 groups 的概念，可以把任務分到一個群組，對一個群組去做排程，達到從使用者角度的公平。

Linux 在 v2.6.24 加入 group scheduling，當核心被設定 CONFIG_FAIR_GROUP_SCHED 就會被使用。

其他

嘗試發 patch

在看老師的書 Demystifying the Linux CPU Scheduler 的時候，突然好奇說每一個任務的 loading 是如何運算的，畢竟排程器上的任務如此多，計算出 load 然後依據每個 CPU 的狀態去做 task migration 應該是很重要的課題。所以我就跑去 pelt.c 看了一下實際的運算是如何做到的。

pelt 全名是 Per Entity Load Tracking

在看程式碼的時候，發現有個地方的中括號打反了變成 [1002..1024[，我就想說試試看發人生第一個 patch。

結果自己在摸索如何發 patch 花了好多時間…，轉眼間就早上了。所以就記錄了一下自己發 patch 的過程來紀念逝去的時間。雖然這個 patch 最後是我誤會中括號的用法，所以並沒有被採納，但跟這些厲害的人交流讓人有點興奮><

結果發現反過來的中括號是法文的用法，是我自己搞錯 xD

我發的 patch 在這裡。

記錄我發 patch 的過程可以點這裡，就不放在排程器筆記這裡了，佔空間。