Demystifying the Linux CPU Scheduler 閱讀筆記

contributed by < linhoward0522 >

返回「Linux 核心專題: CPU 排程器研究」

1 Basics of the Linux Kernel

1.1 Operating Systems

作業系統被視為使用者與底層硬體之間的協調者，其中排程器更是其核心所在。作業系統的工作包含管理硬體資源以及應用程式，作業系統的核心可以使用特權指令，讓每個程式能夠安全的獨立運行。而作業系統的實際責任是什麽？ Linus Torvalds 說：「作業系統唯一的任務是要幫助程式運行，作業系統等著程式向它請求資源。」

作業系統核心會在開機透過 boot loader 載入到記憶體中，接著再載入應用程式。事實上核心的程式碼會一直儲存於記憶體中，與一般的程式碼分開，防止其他程式對核心程式碼部分進行存取。

1.2 A general overview

作業系統核心負責管理與分配硬體資源，像是 CPU, memory hierarchy, I/O devices，並確保能夠共享 CPU 資源，因此要給核心所有資源的存取權限。所以作業系統被設計成 kernel mode 與 user mode 以滿足穩定性及安全性，實作方式為：

• 核心的二進制 image 會被載入到 RAM 中(從低或是高的位址開始)
• 該位址隔壁有一塊已經被定義保留給核心的 RAM
• 剩下的區域可以被使用者自由存取

kernel space 是專門用於關鍵任務的固定區域並同時禁止 user 存取，而 user space 是執行 user programs 的區域

System calls

每個行程可以在 uesr mode 或 kernel mode 執行，透過 system call 可以讓運行在 user mode 的行程能夠使用核心的高權限功能，也視為使用者跟核心之間的 API。當一個行程呼叫 system call：

• 會暫時運行在 kernel mode 下
• 執行需要高權限的任務
• 再切換回 user mode

例如：在 x86 架構中，code selector (cs) 暫存器中有兩個 bits，可以表示目前的權限等級 (current privilege level (CPL))
0 代表 kernel mode，3 代表 user mode
每個 system call 都會暫時更改 cs 裡面的值

system call 可以直接在 user space 呼叫，也能夠過組合語言或是用 C 標準函式庫 (glibc）包裝後的函式來間接呼叫

File Systems

另外一種與核心溝通的方式是透過 Virtual Filesystem (VFS)， VFS 是核心預設的檔案系統實作方式，核心將檔案系統視為抽象介面，而 VFS 做為抽象層，方便使用者操作不同的裝置或檔案時，可用一致的方式存取。讓使用者透過 file_operations 來存取系統資源。實際上，這種基本原則是被廣泛認可的 Unix 和 Linux 哲學的基礎，即「萬物皆檔案」。

老師上課時提過，更精確的描述： Everything is a file descriptor

A different kind of software

核心自己是沒有 error checking ，因為核心信任自己的函式並被假設為沒有錯誤的。所以核心
是使用 assertion 來確認硬體跟軟體的一致性，當有錯誤核心就會進入 kernel panic 並停止。當然程式或硬體錯誤仍有機會發生，會殺掉有問題的行程並產生名為 oops 的 memory dump

例如：對 null 指標做 dereference ，在 user space 中會產生 segmentaion fault，而在 kernel space 會產生一個 oops 或是進入 panic。這種情況下最好的做法是重新啟動以避免破壞記憶體。

核心的另外一個特性是使用 C 標準函式庫中來實作自己的函式，因為 C 標準函式庫對核心來說太大且效率不佳，而且可以根據核心的目的來實作

例如： printf() 和 malloc() 被實作為 printk() 和 kmalloc()

User and kernel stacks

行程在 kernel/user space 執行是不同的，記憶體管理也是如此。每一個行程都有兩個 stack，分別位於 kernel and user space。 x86 CPU 在特權模式切換時會自動的切換 stack pointers ，通常是和 system call 一起發生。

user space stack 被稱為 on-demand paging，也就是記憶體可能會不斷增加
kernel space stack 無法自行擴增，並且有固定順序的 page size

Monolithic kernel vs. Microkernel design

核心有兩種不同的設計方式：

• monolithic kernel
  • 每個服務都位在核心中
  • 可以直接跟底層硬體溝通
  • Linux 的設計比較偏向這個，但是缺乏模組化，可以透過 kernel modules 解決這種問題
    • 在執行期間透過 insmod 以及 rmmod 來載入跟卸載核心模組
    • kernel modules 也不能完全達到 microkernel 的功能，例如不可能在執行時期替換排程器
    • 模組並不是要實作核心功能，而是被當作核心的擴充額外功能
• microkernel
  • 目的是要將核心的大小縮小，將大部分的服務移到 user space，只在核心中留下最重要的部分
  • 透過 message passing 來溝通
    • 呼叫大量的 system call
    • 很多 context switch
  • 如果服務崩潰，則重新啟動即可，因為它只是一個 user process
  • 較容易維護，可以在不重新啟動系統的情況下進行測試，直接將要測試的服務編譯完後重啟就好了

1.3 Process management

現代電腦的重要功能之一是能夠在同一時間執行多個任務。每個行程都是獨立的，且必須與其他行程競爭共享資源。每個行程擁有自己的 address space ，當行程嘗試存取別人的 address space 時，核心會產生 segmentation fault signal 通知該行程 。

Segmentation_fault

同時行程可以交錯執行，稱為並行。而為了更好並行程式，引入了一個概念，稱為 thread 。 thread 必須共享資源才能有效的完成一項任務，因此行程中的 thread 不是獨立的。核心不區分行程跟 thread，將他們視為相同的。在 Linux kernel 中最小的排程單位為 thread 。

每個 thread 有自己的 PID (Process IDentifier)
同一個行程內的 thread 被記為 TGID (Thread Group ID)，其中有一個 thread 會被稱為 thread group leader，其 PID 等於 TGID ，因此每個 thread 的 TGID 也就是 thread group leader 的 PID

如果一個行程只有一個 thread，則 PID 等於 TGID

呼叫 getpid() 時，會回傳 TGID (group leader PID)

一個行程中有四個 thread，其對應的 PID 分別為 100～103
thread 0 為 thread group leader，所以每個 thread TGID 為 100

process 跟 thread 真正的不同在於 thread 共享相同的 address space。thread 之間可以透過 shared memory 來達成程式並行與溝通。每個 thread 都由 CPU registers 的唯一副本以及專屬的 stack 組成，所以 thread 常又稱 lightweight processes or LWP。

Processes and threads

1.3.1 第16頁問題

The flag CLONE_SIGHAND at line 13 requires that the parent process receives a SIGCHLD signal upon the termination of the created child process, with the exception that the address space, file system information (CLONE_FS), open files (CLONE_FILES) and signal handlers will be shared.

The flag CLONE_SIGHAND at line 13 => 行號是否標錯了？

已修正

核心使用 task_struct 來代表每一個任務，並且用 circular linked list 儲存。 task_struct 通常被稱為 process descriptor or PCB (process control block)

我們使用 PID hash table 來找到對應的任務。比起線性搜尋法，可以在

$O(1)$ 內找到對應的 process descriptor。可以應用在執行 kill 命令時。

有四個表，每一個 PID 類型有一個，且每一個都是 hlist_head 結構，並指向 hlist_node 的 chain
pid_list 中的 PID 是同一組中的 threads
pid_chain 是連接發生衝突的 PID

Tasks lifetime

當子行程終止時，會變成 zombie 狀態，直到親代行程執行 wait() 。接著會執行 release_task() 來完成 descriptor 的釋放。 detach_pid() 會被呼叫兩次，分別清除
PID 以及 TGID hash tables ，至此 task_struct 才釋放完成。
親代行程是清除 zombie 子行程的唯一方法，若親代行程在不用 wait() 的情況下離開，子行程會變成 orphan 行程，因此變成 init 的子行程。 init 行程會定期收集 zombie 行程並清除。

sched_yield() 使得 TASK_RUNNING 狀態的行程能夠放棄其對處理器資源的所有權
schedule() 讓目前正在等待的行程獲得 CPU 執行
try_to_wake_up() 用來喚醒行程，將行程狀態設為 TASK_RUNNING

---

2 The Linux CPU scheduler

2.1 Introduction

Linux 要求將任務提交到排程器前，必須將任務先做標記，又稱排程類別 (scheduling classes)，以提供不同的 workload 。排程器依據已提供的優先權決定執行順序。

• stop class 用於企圖關閉機器或 hot-plug a CPU 之前覆蓋所有排程類別。排程每個 CPU 上的 stop 任務。該任務會搶佔所有任務，並且不被任何任務搶佔。僅適用於 SMP 系統。
• deadline class 實作 EDF 排程
• real-time class 遵循 POSIX 規範。POSIX 中的即時任務可以在最少 32 個固定優先權上運行，直到被搶佔或讓出 CPU
• fair class 實作 CFS
• idle-task class 負責排程每個 CPU 的閒置任務( swapper 任務 )，當沒有任務可執行時就會執行該任務

• SCHED_RR 和 SCHED_FIFO 使用相同的優先權，所以共享相同的 runqueue。
• SCHED_DEADLINE 有最高的優先權。
• SCHED_NORMAL 或 SCHED_OTHER 被預設為用於定期任務以及使用 CFS 。
• SCHED_BATCH 與 SCHED_NORMAL 相似，但比較少被搶佔，適合用於批次任務。
• SCHED_IDLE 適用於優先權非常低的任務。

前幾個優先權級用於即時任務，這些任務使用 SCHED_FIFO 或 SCHED_RR 進行排程。正常任務使用 SCHED_NORMAL, SCHED_BATCH 和 SCHED_IDLE 進行排程。

2.2 Prior to CFS

最早期的排程器

$\to$

$O(n)$ 排程器

$\to$

$O(1)$ 排程器

$\to$ Completely Fair Scheduler (CFS)

Early Linux Scheduler

這個排程器不是為了針對大型多處理器系統而設計的。只有一個 queue 來存放任務，並迭代這個 queue 來選擇任務。限制任務數量最多為 64(NR_TASKS 最初被設為 64)。

方法如下：

• 以反向順序走訪 runqueue 找尋最大 timeslice 且大於 0 的可執行行程。
• 如果沒有找到，就重置所有任務的 timeslice ，並且會給目前在睡覺的任務加上一半當前 time slice 的時間。為了盡快排程被喚醒的任務進而提高互動性。

$O(n)$ Scheduler

$O(n)$ 排程器與最早期的排程器沒有太大差別，一樣要迭代整個 queue 來選擇任務。為了解決批次與交互式任務的不公平，排程器將時間切分為 epoch ，代表每個任務的 lifetime 。在每個 epoch 開始前，根據每個任務分配其優先權。即時任務的優先權最高。交互式任務根據前一個 epoch 的行為來分配動態優先權。批次任務的優先權最低。

在一個 epoch 結束後，每個任務都執行了一次。高優先權任務通常有較大的 timeslice。
當epoch 開始時或呼叫

$O(n)$ 排程器，迭代整個 queue 來選擇任務，計算任務的 goodness 並選擇 “most good” 的任務來執行。

goodness() 函式可以判斷任務的優先程度，由任務剩餘的 clock-ticks 加上基於該任務優先權的權重

• -1000：表示永遠不會選擇此任務
• 0：表示已經用完 timeslice，需要重新計算(但仍有可能被選中)
• 正整數：表示 goodness 值(值越大，優先權越高)
• +1000：表示即時任務

$O(1)$ Scheduler

被稱為

$O(1)$ 排程器就是因為可以在常數時間內新增/選擇任務，不管系統中的任務數量。由於

$O(n)$ 排程器的在 SMP 系統上存在以下問題 :

• 單一 runqueue
  • 任務可以被分配在任何處理器上(有利於 load balancing )，但是不具有 processor affinity，可能會導致大量的 cache miss 發生
• 單一 runqueue lock
  • 全部的處理器都在競爭同一個 global queue lock ，可能需要非常長的時間
• 無法搶佔執行中的行程
  • 低優先權的任務將執行，而高優先權的任務只能等待

$O(1)$ 排程器不需要迭代整個 queue 來選擇任務。

$O(1)$ 排程器維護一個 global scheduler ，可以在每個 CPU queue 中進行 load balance 。 如果某個 CPU idle，

$O(1)$ 排程器會從另一個 CPU 取出任務，稱為 work stealing 。 Workers 會先完成自己 queue 上的任務，然後才從其他 queue 上竊取任務。

核心在系統中使用 bitmap 來維護一個優先權陣列，每個優先權級別都有一個 queue (MAX_PRIO (140) 既是最高優先權又是 queue 數量)。為了能更有效率選擇在最高優先權上的任務，使用 bitmap 定義是否有任務在給定的優先權上( true 表示有任務)。有 140 個優先權，一個 word 32 位元，所以 BITMAP_SIZE 為 5。

$O(1)$ 排程器維護兩個優先權陣列：

• Active array : 儲存目前還有剩餘 timeslice 的行程
• Expired array : 儲存用完 timeslice 的行程

任務的排程會在 Active 中執行，如果一個任務在被搶佔之前沒有完成，那麼它就會回到 Active 中。若被選擇最高優先權的 queue 裡有多個任務，那就會使用 round-robin 來執行。會一路執行到 Active 裡的任務都完成並加入到 Expired 中，這時候兩個優先權陣列就會互換，再繼續執行下去。

每個任務的優先權是由 static priority 跟 bonus priority 所組成的。 static priority 也就是 nice 值，從 -20 到 +19。 bonus priority 則是從 -5 到 +5。如果行任務花費大量時間睡覺，那排程器會提高優先權 (bonus 會被設為 -5) 。如果一個任務花費較少的時間睡覺，它將受到懲罰 (bonus 會被設為 +5)。

$O(1)$ 排程器被專門設計使用最小的執行時間 jiffy 來分配 timeslice，jiffy 的大小依賴於 tick rate。因為現在的處理器都可以達到 1000 Hz，使得 jiffy 為 1ms。所以 nice 值 +19 任務的 timeslice 只有 1ms，導致排程器會頻繁重新進行排程，導致 cache thrashing 問題。

negative nice values 對任務反應不夠靈敏，對於多媒體應用程式是有影響的。因為必須選擇在 SCHED_FIFO 下運行而不是 SCHED_NORMAL。可能會有 starvation 問題發生。

Rotating Staircase DeadLine Scheduler

$O(1)$ 排程器與 RSDL 都與 Multi-level Feedback Queue 相似。Multi-level queue 對應於 CPU 有不同的 timeslice level 。最高的 queue 有最短的 timeslice ，以此類推。

雖然與 MLFQ 的的概念相似，但細節有很大不同。 RSDL 根據任務的優先權來分配執行時間額度。它的核心元素是每個 CPU 的都有一個經過排序的行程陣列（階梯）。

階梯中的每個級別都有執行時間額度。當額度到期，此階中的所有行程都會往下一階，無論它們還剩下多少 timeslice 。當任務完成每個優先權的所有額度時會被移至 expired queue ，當所有任務都完成其額度時，expired queue 變為 Active 狀態。每個優先權的時間限制保證在有限的時間內結束，不會有 starvation 問題發生。

RSDL 引入了公平性的概念，每個行程都得到了對應的 CPU 時間額度，與優先權成比例。大部分時間都在睡覺的任務將消耗其時間額度的一小部分。當它們被叫醒時，可能處於較高的優先權。

2.3 Completely Fair Scheduler (CFS)

CFS 跟 RSDL 一樣並沒有使用固定的 timeslice。CPU 使用率在每個任務之間平均分配。每個任務並行運行並消耗相等的 CPU 額度(每個任務分配

$\frac{1}{n}$處理器時間，其中

$n$ 是可運行任務的數量。)

然而真正的處理器同時只能執行一個任務，理想的公平排程會執行太多的 context switch。所以 CFS 分配 virtual runtime (vruntime)，表示在理想的多工處理器上該任務的執行時間。 CFS 透過 vruntime 來選擇下一個任務，確保每個任務的 virtual runtime 相近。所以 CFS 會選擇 vruntime 最小的任務來執行。
CFS 分配給每個 CPU 一個 timeslice ，當它到期時，排程具有最小 virtual runtime 的任務。執行完的任務會將 vruntime 加上

$currenttime\times weight$ (依據優先權)。

這種方法解決了

$O(1)$ 排程器中出現的問題 ：

• nice levels 的行為更加一致並且獨立於 tick rate
  • 無論起始值如何，將 nice 值增加 1 具有相同的效果
• 每個任務根據權重 (nice value) 分配 CPU
• 公平睡覺

Weight function

$w(n)=\frac{1024}{(1.25{)}^n}$

• n 為該任務的 nice value
• 1024是 nice value 為 0 的任務的權重

Assigned time

一個任務在 CPU 上花費的時間由下列 4 個值決定：

• target latency
  • 又稱為 scheduler period 。理想情況下每個任務打開處理器所需的最小時間。也就是每個任務執行一次的時間。
• minimum granularity
  • 可以分配給任務的最小時間量。為了限制 context switch 所產生的負擔，任何被排程到的行程在搶佔之前必須運行一小段時間
  • 這是可變動的數值，稱為 sysctl_sched_min_granularity。用於控制排程的行為
    • 較小的值更適合需要低延遲的桌面系統，較大的值適合伺服器工作
• 任務的權重
• runqueue 上所有任務的總權重

根據上述，被分配給任務的 timeslice 為：

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

virtual runtime

排程器會挑 virtual runtime 最低的任務來執行，計算公式如下：

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

• delta_exec 是任務的總執行時間
• weight_of_nice_0 是 nice 值為零的任務所對應的權重
  • 若 nice 值小於零： vruntime 小於實際執行時間
  • 若 nice 值等於零： vruntime 等於實際執行時間

高優先權任務的 virtual runtime 成長速度比低優先權任務慢，高優先權任務需要執行較長的時間

Runqueue

當任務去睡覺時，會從 runqueue 中刪除。若是在睡覺時 vruntime 不變，而其他任務繼續增加它們的 vruntime。當該任務睡醒時，與其他任務相比會有較高的優先權 ( vruntime 較小)。以及任務剛創建時，也會有類似情況，導致不公平的情況發生。

為了避免這種問題，排程器會追蹤最小 vruntime 。每次選擇任務時，都會更新最小 vruntime。當任務要排隊前，會檢查其 vruntime 是否小於最小值。若是，將其 vruntime 設為最小值並重新插入 runqueue 中。當透過 fork() 創建新任務並將其插入 runqueue 時，會繼承親代行程的 vruntime。

---

3 Implementation of the Linux scheduler

3.1 Structs and their role

task_struct 表示系統中每一個任務及其所有資訊。以下來詳細介紹：

• thread_info : 此結構包含了許多 flag ，用來追蹤任務所發出或發給任務的信號。
  • TIF_SIGPENDING 表示行程有 Pending Signals
  • TIF_MEMDIE 表示行程被殺死並回收記憶體
  • TIF_NEED_RESCHED 表示必須執行排程
  • TIF_POLLING_NRFLAG 表示 idle 行程正在 polling TIF_NEED_RESCHED flag
• state : 表示任務的狀態。
  $-1$ : 不可執行，
  $0$ : 可執行，
  $>0$ : 已停止
• on_rq : 指出行程是否在 runqueue 中
• rt_priority and normal_prio : 第一個是用於即時系統排程策略的優先權。若是使用正常排程策略，則 rt_priority 設為 0
• sched_entity : 此結構包含排程器所需要的所有其他資訊
• Pointer to sched_class : 包含這裡所有 scheduling class 的 routines
• Pointer to mm_struct : 此結構表示行程所使用的虛擬記憶體切片

sched_entity 結構表示 schedulable entity 。對於排程器來說， process 、 thread 、 group of prcesses 都視為 schedulable entity 。
可以將多個 enitity 組合在一起作為單一個 schedulable entity 來進行排程。

• enqueue_task() : 將任務插入到紅黑樹
• dequeue_task() : 將任務移出紅黑樹
• yield_task() : 先 enqueue 再 dequeue 。也就是將任務放到紅黑樹的最右邊
• check_preempt_curr() : 檢查是否要搶佔當前任務
• pick_next_task() : 選擇下一個適合執行的任務
  • 走訪所有 scheduling class 並按照優先權選擇下一個任務
• set_curr_task() : 更改任務的 scheduling class 或改變 task group
• task_tick() : 從 tick functions 呼叫，可能會讓行程切換，執行搶佔

3.5 CFS Variants

Burst-Oriented Response Enhancer scheduler

BORE 賦予互動式任務較多的權重，也就是會有更多的 timeslice 。而 CPU-bound 任務會被賦予更高的 vruntime，較不容易被排程到。

BORE 主要實作於 update_curr() 中，用來更新當前行程在 CPU 上執行所花費的實際時間以及 vruntime 。以下介紹一些可調整的參數：

• sched_burst_penalty_scale : 控制 penalty 的程度。任務的 vruntime 會成長的更快。
• sched_burst_granularity : 調整區分 burst task 的靈敏度。數值越高，短 burst task 越會被忽略
• sched_burst_reduction : 當任務 dequeue 或是自願讓出 CPU，減少其 burst time，也就是降低任務 vruntime 的成長率。