# Linux 核心專題: CPU 排程器研究
> 執行人: irenesu2000

:::success
:question: 提問清單
* 請描述你閱讀過程中的疑惑並討論

* 為什麼 kernel stack 無法擴張
> 1.記憶體碎片化:由於記憶體配置需要連續配置，若擴大則會導致 memory fragmentation ，同時增加記憶體管理的複雜性
> 2.為了避免 kernel stack overflow 和其他相關的安全問題，核心會對 stack 進行保護和限制，以確保 stack 不會超出其分配的固定大小。
* 為什麼 linux kernel 是使用 doubly linked list
> 1.不用考慮邊緣問題
> 2.高效刪除
> 3.方便走訪全部(順序逆序)
> 4.穩定性
* 為什麼 kernel 中不區分 process 和 thread
> Linux核心將行程表示為task_struct，每個task_struct都包含了一個行程或執行緒的上下文資訊、調度資訊、資源分配資訊等，它們在核心中都被表示為任務控制區塊。同時在使用者空間，進程和執行緒可以通過不同的ID進行區分，但在核心它們被視為相同的實體。這種設計簡化了核心的實現和維護，提高了核心的性能和效率。
* 為什麼Completely Fair Scheduler 中是使用virtual runtime來決定排程
> 使用 vruntime 而不是使用實際運行時間來決定排程順序的好處為可以避免長時間運行之 process 佔據過多 CPU時間導致其他行程舞法公平競爭，以實現公平時間分配
* 為什麼Completely Fair Scheduler 中是使用紅黑樹來儲存任務
>CFS使用紅黑樹來儲存任務是為了實現高效的調度和管理，能夠在動態環境下快速、公平地調度任務
>1.快速的插入和刪除：由於紅黑樹的平衡性和快速插入/刪除的特性，CFS能夠高效地處理任務的插入和刪除操作，能夠很好的處理動態調度
>2.良好的平衡性：紅黑樹的自平衡性確保了樹的相對平衡，避免樹的高度過高的問題導致過高的時間複雜度，即使在面對大量任務時也能保持較低的時間複雜度
>3.有序性：可以快速找到虛擬運行時間最小的任務。這樣，CFS可以輕鬆地選擇下一個要執行的任務，以保持公平的時間片分配

:::

## 專題解說影片
[專題解說影片](https://youtu.be/Hi9EGG7VkLE)
## 任務簡述

研讀《Demystifying the Linux CPU Scheduler》，紀錄閱讀過程中的認知和相關疑惑，授課教師撰寫此書的目的，是希望能讓大部分學過電腦科學基礎科目的學員都可藉此窺見 Linux 核心之美，學員的意見回饋很重要。

## TODO: 研讀《Demystifying the Linux CPU Scheduler》

比照 [Demystifying the Linux CPU Scheduler 閱讀筆記](https://hackmd.io/@linhoward0522/HyC28W9N3) 及 [CPU 排程器研究](https://hackmd.io/@sysprog/By-Q7reB3)，紀錄閱讀過程中的問題，連同自己的推論彙整在本頁面，適時與授課教師討論。
> 提及頁碼時，要附上電子書最後更新日期，範例: `P.16 @ March 21`

至少要涵蓋第一章到第五章，採用 5 月 23 日 (或更新) 的書稿。

## Demystifying the Linux CPU Scheduler 閱讀筆記

:::warning
注意書寫規範：
* 中英文間用一個半形空白字元或全形標點符號區隔
* 以全形標點符號為主，半形的逗號和句號針對數學表示式/程式碼

:notes: jserv
:::
## 專題解說錄影
[解說錄影](https://www.youtube.com/watch?v=Hi9EGG7VkLE&ab_channel=susu)
## 1 Basics of Linux Kerel
### 1.1 operating systems
* 作業系統被視為硬體與使用者之間的協調者，可以主要分為硬體資源管理軟體與應用程式，應用程式可直接與使用者互動，占了較大部分在作業系統中。
* 為了確保硬體跟軟體之間可靠的互動，會將核心的關鍵部分存至單獨的記憶體區域，可避免被應用程式非預期的存取，此概念被稱為 *computation isolation*。
### 1.2 A general overview
* 作業系統分為 **核心模式** 以及 **使用者模式** 為了提供穩定性以及安全考量
* 核心模式為負責分配硬體資源以及必須處理來自 I/O 裝置、CPU、記憶體的請求，同時分配 CPU 資源讓多個行程共享，由於需要處理眾多請求，因此會給予作業系統核心存取所有硬體資源的所有權限，但要一個保護機制來提供系統的安全性及穩定性。
* 將定址空間區分為 **核心空間** 以及 **使用者層級空間** ，前者為一個固定空間去執行關鍵的系統任務同時也阻止使用者存取，後者為執行系統工具與使用者程式，透過這樣的分區機制確保核心和使用層級的者資料不會互相干擾，保護整個系統免於受惡意用戶程式影響。
*
#### System calls
* 每個行程可以運行在核心模式與使用者層級空間，當行程在使用者層級空間 時，可藉由 **系統呼叫** 存取特權 kernel functionalities。
* 當 user process 呼叫 system call
* 暫時地在 kernel mode 運行
* 執行較高權限之任務
* 最終會降回低權限
* system call 呼叫可以透過 user space 直接呼叫或透過 C標準函式庫 glibc 間接呼叫函式
`P.5 @ March 21`

#### file systems
除了呼叫 system call 來與 kernel 溝通，還可以透過 **virtual filesystem (VFS)** ， kernel 將其視為用戶與 file system 之間的互動介面，有利於用戶透過檔案操作來存取系統資源，所謂檔案操作如 **open(), read(), write()** 等等，為了使 file system 可以被作業系統使用 ， file system 會被掛載到指定的掛載點 ，從掛載點與 file system 連接。
* 用戶可透過 **mount** 命令來進行掛載
`mount -t <fstype> <device> $MOUNT_POINT`

#### A different kind of software
* 在linux kernel 中並未有 error checking 的機制存在，是由於所有的 kernel functions 是被假設為 error-free，當系統發生錯誤時會進入 kernel panic （之後章節會深入講解）。
* 在 linux kernel 中會使用自訂函式，如同標準C函式庫中的 **printf()** 與 **malloc()** 是以 **printk()** 與 **kmalloc()** 來代替。

#### user and kernel stacks
每個系統中的行程皆有兩個 stacks ，分別為 user stack 與 kernel stack，當權限模式更換時， stack 之指標會透過 syscall**** 來自動切換模式。
* user space stack 的大小是可以擴充的，稱為 **on-demand paging**
* kernel stack 是固定的，無法再加以擴充，在32-bit系統中大小為 8 KiB，在64-bit系統中為 16 KiB
> **Why are kernel stack so small?**

1. 希望佔用越少 kernel 記憶體，由於原先預設待在 kernel mode 的時間不長，因此希望佔用越少部分
2. 越大的 page size 會導致資料的連續配置上造成困難，導致 **memory fragmentation**

**kernel threads**
* 由 kernel 所創造，僅存在於 kernel space 中且 **不會切換到 user mode**

#### Monolithic kernel vs. Microkernel design
主要的差別為有多少的服務需要在kernel上執行
* Monolithic kernel 大部分的服務皆在 kernel 上執行， linux 為此種，此種類型問題為缺乏**模塊化**。
* Microkernel kernel
* 大部分的服務被轉移至 user space 只保留少數必要的在 kernel，服務被實作為 server， kernel 與 server 及 應用 聯絡的方式為 **message passing** 如同 client/server 方式，應用端需傳送請求至 server， server 會將其請求傳送至 kernel。
* **優點**
* 當服務 crash 只需要重新啟動，並不會影響到整個系統
* 系統設計上更加彈性，因為實際的作業系統是建立在一個小型核心之上，只需移植核心中的基本功能。
* 大部分程式碼皆在 user space 上，更方便於維護
* 缺點
* 大量的 system calls
* 大量的 context switches
-->通過大量使用 IPC 會帶來龐大的開銷，導致犧牲了性能上的表現

### 1.3 Process management

核心內部將其分為數個子系統，如下圖
`P.14 @ MAY 30`
#### 1.3.1 Processes and threads
* 在 kernel 內部不區分兩者，皆視為一樣的， kernel 中最小的單位是 thread，每個 thread 都會被分配唯一的 PID，在 multi-threaded process 中每個 thread 會有不同的 PID 彼此會共享同個 TGID (Thread Group ID)。
* Processes and threads 主要差別為 thread 會共享相同的地址空間，而 process 則不共享，每個 process 必須擁有一個獨特的地址空間，每個 thread 都擁有獨立的 CPU registers 副本和專用的 stack，其他一切都與其 Process 共享。

#### 1.3.2
每個任務由 **task_struct** 的結構來表示，並使用雙向環狀鏈結串列，藉由 PID 在 hash table 中來搜尋特定任務

#### 1.3.3 scheduling
基於 time sharing 的手法，Linux 藉由將 CPU 時間切成多個時間片段來實作多個行程的並行執行效果。一個時間片段只能執行一個行程，除了時間到期導致自動結束運行也會出現被動結束，如搶佔，因此以何種方式順序來安排，所以後續也出現多種排程的演算法，如同 FIFO, RR, EDF, SJF，演算法須滿足:
* 快速的回應時間
* 良好的吞吐量
* 避免陷入飢餓
* 需要有任務優先權區分

#### 1.3.4 Tasks lifetime
任務皆有一個生命週期 `P.30 @ MAY 30`
* 當運行中的行程進入其中一個狀態時，表示要進入睡眠，抑或是正在等待資源的可用性（例如 I/O 及 lock）。當所需資源可用時，行程返回就緒狀態，準備使用 CPU。
* 當行程等待 I/O 操作完成時，會進入 sleep state 這樣就部會浪費到處理器的時間可安排另一個任務進來，一旦 I/O 操作該行程就會變回 runnable state，當行程自願放棄 CPU 透過呼叫 `sched_yield()` 系統呼叫或是被搶佔 (preempt)，狀態會從 running state 至 runnable state，最後 process 會透過執行 exit() 來進行終止。
* 當子行程已結束會維持 **zombie process** 直到其親代行程執行 wait() 來進行終止同步。

## 2 The Linux CPU scheduler
### 2.1 Introduction

#### Response time and throughput
1. 排程器目標為將與用戶互動的行程的響應時間最小化，確保系統能夠快速回應用戶的操作。
2. 不同類型的任務存在，互動型任務（如文字編輯器）需要快速響應用戶的輸入。 排程器優先處理這些互動型任務，以提供良好的用戶體驗。
3. 在平衡互動性和吞吐量方面，排程器面臨著挑戰。增加前後文切換 (context switch) 可以提高系統的響應速度，但同時降低整體性能和吞吐量。 努力在響應能力和性能之間找到平衡，以滿足用戶期望並最大化系統效率。

#### Fairness and Liveness
1. 需要維持公平性，有相同優先權的任務應該運行相似的時間，而具有較高優先權的任務應該優先執行。
2. 確保就緒任務最終能在有限時間內獲得資源的存取來避免飢餓。
3. 在有限的執行中必須確保需要計算資源的任務將在合理的時間內存取。

#### Real-Time vs. Non-RT
* Real-Time task: 它們需要在**嚴格的時間限制**或時限內進行處理，並且準時交付計算結果。因此，排程器通常會優先處理這些任務，分為硬即時和軟即時兩個類別。
* 硬即時:任務要求必須遵守所有時限，否則可能導致系統災難性故障。
* 軟即時:錯過時限只會導致服務質量下降，但系統仍然可以繼續運行。
* Non-RT task: 是指**不具有**任何相關時限的任務，包括人機交互和批量任務。批量任務可以自主地處理大量的數據，並且不需要即時響應。因此，非即時任務的排程可以根據資源的可用性進行調整，因為它們的完成時間不是關鍵性的。

#### Power Efficiency
CPU 排程器的主要目標之一是通過減少系統的能源消耗來最大化功耗效率， 排程器達到此目標的方法之一是識別和優先執行需要較少功耗的任務，如空閒任務或優先權較低的任務，而不是資源消耗較大的任務。

#### Scheduling classes and policies in Linux
`P.35 @ MAY 30`
* stop class: 超越所有 scheduling classes
* deadline class: 實作 Earliest Deadline First
* real-time class: 遵守 POSIX 規範， 其中 POSIX 為標準規範，涵蓋排程及資源排程的即時處理
* fair class: 實作 CFS
* idle-task class: 只負責空閒任務排程

### 2.2 Prior to CFS
early scheduler $\to$ $O(n)$ scheduler $\to$ $O(1)$ scheduler $\to$ CFS

#### $O(n)$ 排程器
* 為了解決批次處理和互動任務之間的不平衡問題，排程器引入 epoch (時期)，表示系統中每個任務的生命週期
* 每個時間片開始時，排程器根據任務的行為為每個任務分配優先權，透過 **schedule()** 函式來進行排程，裡面運用 **goodness()** 函式來表示其優先權有對應數值來實作優先權
* $−1000$: 表示這輪不會選擇到此任務
* $0$: 重新計算 counter（可能仍被選中）
* 正整數數值: “goodness” value (越大優先權越高)
* $+1000$: real-time (RT) task
$\to$ 即時任務會被優先給予最高優先權

#### $O(1)$ 排程器
$O(n)$ 排程器在處理少量任務時運行良好，但在處理多任務時會出現性能問題，因此引入 $O(1)$ 排程器，可以在恆定時間內排程任務，無論系統中運行了多少個行程 。

同時 $O(n)$ 排程器在 SMP 系統中也有下列問題:
1. 一个單一的 runqueue；
2. 單個 runqueue lock: 代表當一個處理器想要修改他時，其他所有處理都必須等到他被解鎖，因此會耗費許多時間
3. 無法搶佔正在運行的行程: 低優先權的任務將繼續執行，高優先權的需繼續等待。

* $O(1)$ 排程器不用再決定運行哪個任務時檢查所有可運行的任務列表，$O(1)$ 排程器維持一個全局的排程器可以重新平衡 CPU queue
* 使用 **work stealing** 策略，當 CPU 空閒時會移動任務，worker 會先完成自己的任務才去取走 (steal) 別人任務
* $O(1)$ 排程器維護兩個優先權陣列： **Active array** 和 **Expired array**。行程根據其優先權放入相應的佇列。當一個行程的時間片用完時，它被移到過期陣列並重新分配優先權。排程從活動陣列中選擇最高優先權佇列，並以循環方式進行排程，直到活動陣列為空。然後，活動陣列和過期陣列互換位置，繼續進行排程。這種方式使得排程操作具有 $O(1)$ 的時間複雜度，提高了排程的最壞情況延遲。

:::warning
注意用語:
* real-time 是「即時」，而非「實時」
* schedule 是「排程」，而非「調度」
* deadline 是「時限」，避免講「日期」，因為時間單位往往很細緻
* call 是「呼叫」，而非「調用」
* preempt 是「搶佔」
* process 是「行程」
* access 是「存取」，而非「存取」
* address space 是「定址空間」，而非「地址空間」
* 在 Linux 核心中，一度存在 epoch 和 timeslice 並陳，應區分用語

詳見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 及 [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)。另外，中英文間用一個半形空白或者標點符號區隔。

:notes: jserv
:::

#### Rotating Staircase DeadLine Scheduler
RSDL 是基於排名以及時間片段來確保公平性和互動性，行程首先會根據其靜態優先權獲得一個時間片段，每個行程會根據其原始優先權逐一插入佇列中，排程器會挑選最高排名之行程來執行，當行程執行完時間片段後會以較低的名次重新加入陣列中，每當執行完其排名會越來越低，如同下樓梯，透過這樣重複執行至佇列的底部，此外樓梯中每個排名級別皆有執行時間限制，若達到限制該級別的所有行程皆會下降一個級別每個優先級的時間限制保證結束時間，使行程不會餓死。

### 2.3 Completely Fair Scheduler (CFS)
CFS 與 RSDL 相似，皆無固定的時間片段，由於理想的公平排程會導致過多的上下文切換，進而影響到效能，這樣的方法為 $O(n)$ 。
CFS 透過給定一個 **virtual runtime**(vrutime)代表在理想的多工處理器上的執行時間，其目標為希望每個任務的 vrutime 是接近的，因此每次會選擇最小的 vrutime 來執行。
CFS 給定每個行程 timeslice，當過期時會排程最小的 vrutime，執行完的任務會將 vrutime 加上 ${current\ time}\times{weight}$ (依據優先權)。
* 一個任務 p 所得到的 CPU 分配對應於下面公式，W 為對應權重:
$$
C_i = \frac{w_i}{\sum w W} \quad \times \sum C
$$
* Weight function

$w(n) = \frac{1024}{(1.25)^n}$
- n 為該任務的 nice value
- 1024是 nice value 為 0 的任務的權重

* Assigned time
我們定義了一個函數來為每個nice等級分配權重。一個任務在CPU上運行的時間量由以下4個值決定：
* 目標延遲(排程器週期):他是一個理想化的最小值的時間量，要求每個可運行任務只少運行過一次所需的最少時間。
* minimum granularity:分配給任務的最小時間，由於上下文切換會產生開銷，因此在最小時間內皆無法被搶佔來限制上下文切換的開銷。
* The weight of the task:由權重函式計算出來
* The total weight:佇列中所有任務的權重
$$
assigned time = target latency \frac{task weight}{total weight} \quad
$$

* Virtual runtime
表示一个行程在搶佔之前必须運行的最小時間，每個任務的絕對運行時間是根據前面討論的權重值加權的，加權後的時間被稱為虛擬運行時間。
$$
vruntime = delta exec \frac{weightofnice_0}{task weight} \quad
$$
* delta_exec :任務運行所花費的絕對時間
* weight_of_nice_0:對應於 nice 值為零的任務的權重
對於小於零的 nice 值->權重因子小於1，虛擬運行時間小於實際運行時間且增長速度較慢
nice 值為零-> vruntime 等於實際在 CPU 上運行的時間

#### Energy-Aware Scheduling (EAS)
* 能源感知排程在Android移動設備中強調低能源消耗的重要性，並將能源效率納入排程演算法中，以更節能的方式進行任務排程。
* 能源感知排程與 CPUIdle 子系統和 CPUFreq 子系統相連接，這樣排程器可以了解每個CPU的閒置模式和頻率，並在選擇 CPU 時最小化能源消耗。
* EAS策略通過對任務運行的CPU進行評估，以找到容量足夠且能源影響最小的CPU。這樣做可以平衡性能和能源效率，同時考慮任務對閒置CPU的偏好。

## 3 Implementation of the Linux scheduler
### 3.1 Structs and their role
#### task struct
每個任務皆是以 task_struct 來表示，其中包含下列資訊:
* thread_info:這個結構非常小，僅包含用於行程的基本信息，每個行程都有自己的thread_info
* state:表示現在任務 state ，-1 unrunnable, 0
runnable, > 0 stopped.
* on_rq :表示是否在佇列中
* rt_priority and normal_prio:前者為用於即時系統排程策略的優先權，如果任務是在正常的排程策略其值會被設置為0。normal_prio為核心所使用的內部表示與 user space 中的優先權不同。
* sched_entity:這個結構包含了所有排程器所需要的其他訊息。
* Pointer to sched_class: 包含這裡所有 scheduling class 的 routines
* Pointer to mm_struct:這個結構代表虛擬記憶體的片段， mm 為記憶體管理。
#### sched entity
此結構表示可排程實體，構成sched_entity包括：
* load_weight：包含實體的權重。權重的作用在第2章中討論。
* struct rb_node run_node：表示紅黑樹中的節點。
* on_rq：指示實體是否在運行隊列中。
* exec_start：任務在CPU上開始執行的時間。
* sum_exec_runtime：任務實際運行的總時間，不考慮權重。
* vruntime：任務已運行的加權總時間。
* struct sched_entity *parent：層次結構中的父節點。
* struct cfs_rq *cfs_rq：該實體排入的運行隊列。
* struct cfs_rq *my_q：如果這是一個組，則這是該組的子運行隊列。該實體的子項排入此處。
其中 runqueue 是一個紅黑樹（rb_node和cfs_rq），而時間片基於虛擬運行時間（exec_start和sum_exec_runtime用於計算vruntime）。

#### sched_class
這個結構包含了特定於排程類別的排程程序。排程器透過連結器腳本按照優先順序走訪每個排程類別，從高優先順序類別開始，直到找到可排程的任務為止。sched_class 收集了排程類別的所有方法，形成了一個表，task_struct中的指標指向該表。在不同的排程類別中，有一些常用的函數:
* enqueue_task(): 用於將任務插入紅黑樹中
* dequeue_task(): 用於從紅黑樹中移除任務
* yield_task(): 用於重新排程任務
* check_preempt_curr(): 用於檢查是否應該搶佔當前任務
* pick_next_task(): 用於選擇下一個適合運行的任務
* set_curr_task(): 用於當任務更改排程類別或任務組時進行相應處理
* task_tick(): 用於執行時期的搶佔

->Linux CPU排程器具有**模組化**的結構，並且支援多種排程類別。每個排程類別都以自己的方式實作排程函式，並運用 `sched_class` 進行管理和存取。這種設計使得開發人員可以靈活地擴展和切換不同的排程算法，並且能夠根據優先級選擇最適合的任務進行排程。

#### Red-black tree
可運行的任務儲存在一個紅黑樹 (rbtree) 中，這些行程根據執行時間的線性順序被插入其中，紅黑樹是一種自平衡的 AVL tree 。
* 在這個紅黑樹中，下一個要運行的任務是具有**最小虛擬運行時間**的任務。紅黑樹的節點按照執行時間的遞增順序排列，**最左邊**的節點代表已執行時間**最短的任務**，因此會優先進行排程。

紅黑樹具有以下特性：
* 所有節點要麼是紅色要麼是黑色。
* 葉節點是黑色（根節點的顏色）。
* 葉節點不包含數據（為NULL）。
* 所有非葉節點都有兩個子節點。
* 如果一個節點是紅色的，則它的兩個子節點都是黑色的。
* 從根節點到葉節點的每條路徑上包含相同數量的黑色節點。

這些特性確保了紅黑樹的平衡性，存取**最左邊**的節點的時間複雜度為$O(\log{n)}$，紅黑樹在 Linux 核心中被廣泛應用，用於管理可運行的任務，並確保按照執行時間的順序進行排程。它提供了高效的插入、搜索和刪除操作，並能夠快速找到具有**最小虛擬運行時間**的任務進行排程。

### 3.2 Time keeping
核心需要追踪時間來進行時間追蹤和週期性操作，如排程、系統正常運行時間等。為此，核心依賴硬體計時器，它以固定的頻率發送中斷信號。因此定義了:
* 滴答率（tick rate）: 滴答率表示每秒發送的中斷次數(單位為hz)。
* 滴答（tick）: 滴答則是兩個中斷之間的時間間隔。
#### Choice of the tick rate
改變計時器中斷的頻率對系統行為有很大影響，因此較大或較小的HZ值都有優缺點。
* 較大HZ值:
* 優點:較高的滴答率可以提高準確性，減少排程延遲，便於搶佔。
* 缺點:中斷處理程序的執行次數增加，這導致任務可用的處理器時間減少。
#### Jiffies
是系統啟動以來發生的滴答數，每當中斷處理程序執行時，jiffies的值就會增加一個單位。這意味著根據HZ的值和jiffies的值，我們可以通過計算秒數乘以HZ來將秒轉換為jiffies。
#### sched_clock()
它返回系統的運行，時間排程器使用此函數來確定當前任務的絕對、非加權運行時間（se->sum_exec_runtime）。
#### Timer interrupt handler
定時器中斷處理程序調用其他函數，最重要的兩個函數是do_timer()和update_process_times()
* do_timer():增加jiffies的值並更新系統的負載統計資訊
* update_process_times():更新各種統計數據和當前任務的運行時間

### 3.3 Scheduler routines
有兩種方式可以觸發重新排程：
* 當當前進程的時間片用盡時，系統會定期檢查 TIF_NEED_RESCHED 標誌，並在定時器中斷處理程序結束時調用排程器。
* 當一個任務被添加到運行佇列時，核心會檢查其動態優先級是否高於當前運行進程的優先級。如果是，則設置 TIF_NEED_RESCHED，並最終調用排程器以選擇另一個要運行的行程

#### Periodic reschedule
* A periodic scheduler tick:可以是定期的計時器中斷或浮動的HRTICK時鐘
* CFS的實現使用系統的硬體計時器進行定期中斷。每次中斷時，系統將CPU的控制權交給其事件處理程序tick_handle_periodic()，其主要功能是更新內部的核心時間狀態，同時調用update_process_times()，觸發重新排程的入口點scheduler_tick()。

#### Reschedule when adding a task to the runqueue
一個任務可以在兩種情況下被添加到運行佇列中：當它被**創建**時和當它被**喚醒**時，如果新添加的進程的權重小於正在運行的任務，則會進行重新排程，當一個行程調用fork()時，它的task_struct被複製，並開始一個新的行程，父行程狀態的數據結構被複製以創建子行程也會繼承其父進程的排程策略。

調用wake_up_new_task()，將新創建的task_struct作為參數，此函數將任務的狀態設置為TASK_RUNNING，並在調用activate_task()之前初始化，在任務被激活並放入運行佇列之後，wake_up_new_task()觸發sched_wakeup_new事件。最後，此函數調用check_preempt_curr()，如果有其他更應該運行的任務，則會搶佔當前任務。

假設T是這個新創建的任務，ST是其關聯的調度類別（例如，SCHED_NORMAL和SCHED_FIFO）。初始喚醒算法如下：

1. 鎖定T。
2. 調用ST的select_task_rq()函數選擇將T排入隊列的核心Cdst。
3. 鎖定Cdst。
4. 調用ST的enqueue_task()函數將T實際放入Cdst的運行佇列

#### 3.5 CFS Variants
介紹了一些關注改善響應性的CFS替代方案
#### Burst-Oriented Response Enhancer scheduler(BORE)
在BORE中，CPU繁重任務的虛擬運行時間高於CFS的虛擬運行時間，這使得互動任務更容易被排程器選中，因為虛擬運行時間的差異增加了。因此，在BORE中，較不貪婪的任務（互動工作負載）獲得更多的時間片和喚醒搶佔侵略性，而更貪婪的任務（CPU繁重工作負載）權重較低（不太可能被調度），BORE的主要實現位於排程器的update_curr函數中。

## 4 Group scheduling and cgroups
由於 CFS 其目標為在所有任務之間公平分配CPU時間，但它並未考慮到任務所屬的行程或使用者導致，在多使用者系統中，無法公平地將CPU時間分配給不同的使用者或行程，因此引入了**組排程**的概念。
* 組排程允許將任務分組，並在組之間公平分配CPU時間。
* 組排程是解決CFS在多使用者系統中公平性問題的方法，通過將任務分組並在組之間分配CPU時間，實現更公平和均衡的資源分配。

### Group scheduling and CPU bandwidth
為實現組排程功能，引入了**可排程實體**（schedulable entity）的概念，**任務或一組任務**都可以由一個實體表示，在基本的CFS實現中，所有可運行的任務都維護在一個運行佇列（runqueue）中。調度器總是選擇最有價值的任務並執行。然而，在使用組排程時，並不將每個實體都放入運行佇列中，而是創建一個層次結構。每個對應於組的實體都有自己的運行佇列，其中包含所有子實體，每個運行佇列的行為**與正常的CFS運行佇列完全相同**。
`P.135 @ MAY 30`
圖中se(1) and se(3) 為獨自的任務，se(2) 代表 group task se(A) 及 se(B) 為其小孩

#### Multiprocessor
在多處理器系統中，屬於同一組的任務可以在不同的CPU上同時運行。為了允許任務的遷移，每個CPU都為每個組維護自己的調度實體。屬於同一組的任務只能在這些調度實體的運行隊列之間進行遷移。組的所有不同實體都存儲在一個專用的結構中。

### CPU Limits
Linux具有一個稱為組帶寬限制（group bandwidth control）的功能，可以對組的CPU使用量進行限制。這個功能是基於CONFIG_FAIR_GROUP_SCHED的擴展，需要在核心編譯時啟用CONFIG_CFS_BANDWIDTH標誌。
組帶寬限制通過兩個參數來控制CPU限制：
1. cfs_period_us:定義了一個時間段
2. cfs_quota_us:定義了在該時間段內組可以運行的最大CPU時間
-->這種組帶寬限制的功能可以讓系統管理者有效地控制組的CPU使用量。
#### Multiprocessor
在多處理器系統中，對於群組限制 CPU 用量變得更加複雜，為了確保群組不超過其配額，不同處理器需要進行通信，**全局追蹤器**用於跟踪群組的剩餘配額。

### Control Groups (cgroups)
控制群組（cgroups）是一種核心機制，用於建立和控制任務的分組。
* 控制群組可以通過附加子系統來追踪和控制資源使用。
* 子系統是利用cgroups提供的功能控制任務群組對特定資源的使用的模組。
* cgroups以樹狀結構組織，子群組繼承父群組的屬性。
* 不同子系統可以在不同的層次結構中組織任務，子系統通過附加到層次結構來連接控制群組。
#### How to control cgroups
* 控制群組（cgroups）不使用系統呼叫，而是使用目錄層次結構模擬控制群組的層次結構，並通過虛擬檔案系統（VFS）進行公開，通常默認掛載在/sys/fs/cgroup。
* VFS允許核心和用戶進行通信
* cgroup的層次結構可以通過在檔案系統中創建子目錄來擴展，並且每個cgroup可以具有相應的控制檔案。通過操縱這些檔案，用戶可以控制cgroup的成員任務、屬性和行為。
* 子系統是附加到cgroup層次結構的模塊，用於控制特定資源的使用。不同的子系統可以提供不同的功能，每個子系統都有相應的控制檔案，用戶可以通過這些檔案來配置和監控子系統的行為。
#### Autogroup
* 自動分組（Autogroup）是一個功能，它根據 Session ID自動創建群組。這可以改善桌面系統的互動性能，尤其在CPU密集的工作負載下。
* Session 用於識別不同的行程群組
* 自動分組將特定的行程群組獨立出來，使其可以獲得更多的CPU時間。這對於涉及許多並行進程的CPU密集型工作負載尤其有用。透過 proc 檔案系統，用戶可以查看和調整自動分組的設置，以控制相應群組的權重和行為。
#### Core scheduling
* 核心排程（Core scheduling）允許定義的任務群組共享CPU核心，**同一群組**的任務可以同時運行在**同一核心**上，不同群組的任務則不會在同一核心上運行。
* 核心排程提供了**隔離機制**，以確保不同任務群組的安全性，可信任的任務只與相同群組的任務共享核心，避免竊取機密資料等風險。
* 核心排程可以平衡分配可信任任務群組到兄弟核心上，並在強制閒置時尋找可運行的任務進行排程，以提高系統性能。

## 5 Customization of the CPU scheduler
Linux排程器沒有一個通用的理想標準。許多對於好的效能的定義常常彼此矛盾，改善調度器的某一方面可能會損害其他方面的效能。這意味著使用者可以自訂調度器，以適應他們特定的使用需求。
### System Calls
#### Scheduling Policy Related System Calls
* Linux排程器的模塊化特性使得不同的排程算法可以在核心中共存。可以在linux/sched.h中找到sched_class數據結構。
* sched_setscheduler()和sched_getscheduler()系統調用設置和獲取行程的當前排程策略和即時優先級。通過設置排程策略，我們可以使用SCHED_DEADLINE、SCHED_FIFO或SCHED_RR分配一個進程進行調度。
#### Equivalent shell utilities
我們也可以使用chrt實用工具來更改行程的優先權，使用**chrt -p**選項來更改正在運行的行程的排程策略。
#### Scheduler Parameter Related System Calls
與排程相關的系統呼叫：sched_setscheduler()和sched_getscheduler()用於設定和獲取特定行程的排程參數，這些系統呼叫能夠在sched_get_priority_min()和sched_get_priority_max()所給定的範圍內設定rt_priority，以適應自身的排程策略。
#### Processor Affinity Related System Calls
與處理器 Affinity 相關的系統呼叫：sched_setaffinity()和sched_getaffinity()，通過設定Affinity ，可以限制任務運行的CPU子集，從而減少進程遷移的開銷和快取失效的概率，從而提高性能。

### Tweaking CFS by its parameter
CFS提供了一些可配置的參數。這些參數允許我們在啟動時或系統運行時調整調度器的行為。
要更改這些參數，我們可以：
* 與掛載在/proc/sys/kernel/的虛擬文件系統進行交互，
* 或使用sysctl工具

#### Basic Scheduling Parameters
##### Fair Scheduling Class
* `sched_tunable_scaling`
為決定排程器是否可以根據CPU核心數量來調整sched_latency_ns的參數。這些值為0、1和2，分別代表未縮放、對數縮放和線性縮放
* sched_latency_ns
是針對CPU-bound任務的目標搶佔延遲，也被稱為目標延遲（target latency）
* `sched_min_granularity_ns`
它定義了分配給每個任務的最小時間片的下限，確保每個任務在被抢占之前都被授予一定的最小運行時間，隨著任務數量的增加，時間片變得更小。
* sched_wakeup_granularity_ns
排程器只選擇 **vruntime 最小**的任務来運行，此参数在當前vruntime之前建立了一个窗口，直到两个任務的差值超過 sched_wakeup_granularity_ns ，與當前任務的 vruntime 非常接近的任務將不會進行搶佔，**以减少過度調度**。wakeup_granularity_ns的值越大，任務強制搶佔的可能性越小。
* sched_child_runs_first
是一個控制子任務或子任務的父任務先運行的參數，當我預設情況下該值為0，父任務會優先運行。
* sched_nr_migrate
是一個與CPU之間的負載平衡相關的參數，當任務集中於同一個CPU上會進行負載平衡，將任務遷移到其他閒置的CPU上。
* sched_migration_cost
是指任務在不同CPU之間遷移的成本。
* sched_cfs_bandwidth_slice_us
決定每次運行佇列請求配額時分配給每個任務組的CPU時間

:::danger
不要用機器翻譯！尊重台灣科技詞彙經典用語。
:notes: jserv
:::