Linux 核心專題: 排程器研究

# Linux 核心專題: 排程器研究 > 執行人: ShawnXuanc > [專題解說影片](https://youtu.be/6f-ZzgVOEWU) ### Reviewed by `SimonLee0316` $O(n)$ 排程器相對於 $O(1) 和 O(logn)$的排程器有他的優點嗎? > O(n) 的排程器最大的缺點在於其 scalabilty 當任務數量增加時會導致搜尋時間增加導致效率不好，對於 O(1) 的排程器會使用到啟發式的方式判斷任務的 Interactivity ，存在較為困難的運算，所以在嵌入式任務數量較少較簡單不需要複雜的判斷任務類型的環境下使用 O(n) 排程器在排程上可能更加適合 [name=Shawn] ### Reviewed by `Ackerman666` 想問在 RTOS 中比較適合用哪種 Scheduler ( CFS vs EEVDF ) > 我認為 EEVDF 更加適合 RTOS ，當任務執行需求時可以較快速的回應並對於 CFS 過於注重在比例分配所造成的延遲問題有了改善 [name=Shawn] ### Reviewed by `yy214123` 在影片的 [1:26](https://youtu.be/6f-ZzgVOEWU?si=rbWY1LAeg4wXPV0p&t=86) 處提到，CFS 在挑選任務上，會以最小 virtual runtime 為準則，而 virtual runtime 是以實際時間乘上某個加權值，我的問題是該如何知道某個任務的實際時間？ > 在書中的 p.66 2.3.3 Assigned time and virtual runtime 有做詳細說明，在 CFS 中任務所運行的時間為 $assigned\_time=target\_latency\frac{task\_weight}{total\_weight}$ 來決定 > * target latency 指的是每個活動中的任務都可以執行一次的時間 > > 為由 target_latency 與權重的比例相乘獲得，而任務的權重會根據 nice 值經由 $w(nice)$ 權重函式得到，也為了方便計算內部會先將與 nice 值對應的權重事先計算起來在每次需要時用查表的方式得到，因此當任務的優先權越高獲得更多的運行時間 > > 而在第三章 p.114 有介紹關於當前運行任務 (struct sched_entity *curr) 的總執行時間由 entity_tick() 中的 update_curr() 進行計算 ## TODO: 《Demystifying the Linux CPU Scheduler》閱讀摘要和提問 > 紀錄問題和你的認知 ## CH1 Basics of the Linux Kernel #### 1.3.1 Processes and threads 對於每個 process 而言其皆為獨立的，彼此之間不能存取彼此的資料，對於 thread 而言可以執行同一個任務並共享資料，在 linux 核心中不特別區分 process 以及 thread，其中最小的排程單位為一個 thread 而每一個 thread 都有一個獨特的 pid 屬於相同 process 的 thread 會有一個 TGID，若只有一個 thread 的情況下其 PID 以及 TGID 相等，而在 multithread 之下每個 thread 有不同的 pid 但是共享同一個 TGID thread 跟 process 真正的區別在於 thread 共享相同的記憶體位址，使用共享記憶體並行處理並進行溝通在 process 之間進行切換需要藉由排程器進行 context switch 過程為 cpu 停止 process 的執行，切換到排程器的運行，由排程器紀錄 process 目前執行到的位置，並喚醒其他 process，而對於不同 process 的 thread 切換必須要進行 TLB 內容切換所以是一個龐大的消耗在 linux 核心中使用 `task_struct` 來表示每個任務也可以稱為 process descriptor 跟 pcb，用來儲任務的資訊 ## CH2 The Linux CPU Scheduler #### 2.1.2 Handling various workload patterns 由於排程器沒有辦法知道接下來的任務是屬於何種類型的，對於每種平台上面的任務而言任務需求也不盡相同，並沒有一種通用的排成器可以應對全部任務種類，因此 linux 上面採用不同的方法，所以 linux 在每種任務進行排程前會先對任務進行標記即為就是 sched_class 應付不同的工作負載在 linux 中是使用了 scheduling hierarchy 的方式決定執行順序，當較高的優先權中沒有任務之後才會選擇較低優先權階層的任務去進行排程包括 stop_sched_class, dl_sched_class, rt_sched_class, fair_sched_class, idle_sched_ lass 這些不同的 class，每個對應不同的策略，對應其不同的排程的方式包含 SCHED_DEADLINE, SCHED_FIFO, SCHED_RR, SCHED_NORNAL, SCHED_BATCH, SCHED_IDLE 這些不同的策略優先權順序如下 stop-task->Deadline->Real-Time->Fair->Idle-task 1. stop class 會在將 cpu 關掉或是熱拔插之前 (為了節省功耗) 覆蓋所有任務，擁有最高優先權只能在 SMP 使用，確保穩定性執行關鍵任務 2. Deadline 使用 EDF 的策略 3. real-time 4. fair 使用 CFS 5. Idle-task 負責空閒任務 ### 2.2 Prior to CFS * v0.01 為最早期的排程器版本使用 array (good code) * v1.2 整合環狀鏈結串列結構 * v2.0 支援 SMP * v2.2 scheduling classes * v2.4 O(n) 排程器 * v2.6.0 O(1) 排程器 * v2.6.23 CFS * v6.6 EEVDF ### 2.3 Completely Fair Scheduler (CFS) CFS 不使用固定的 timeslice 以及不使用 heuristic 的方式來計算任務的優先權，並想要設計一個理想的多任務處理器，也就是當有 n 個任務而這 n 個任務都可以平均的分配到 $\frac{1}{n}$ 的 cpu 時間，即 cpu 的使用被平均的分配給每個任務，每個任務都可以平行共享 cpu 資源對於現實的處理器，一次只能執行一個任務，所以理想的排程會有太多的 context switch ，也因為在受限於離散時間的緣故，真實世界的排程器沒辦法達到真正得平衡，因此 CFS 對每一個可執行的任務都分配了一個 vruntime 來表示任務在理想排程器上的執行時間，最後在排程時 CFS 即是藉由 vruntime 來進行任務的挑選，並維持 vruntime 可以越接近越好，最理想的的狀態就是全部的 vruntime 皆為相等對於公平的多任務處理器排程而言，有一種方法就是讓任務可以不斷的交錯在 cpu 執行但是這樣會導致過多的 context switch 的負擔，而 CFS 解決了此問題的方式為會先分配一個時間片段給每個任務，當這個時間片段用完之後分配一個 vruntime 給任務而當任務執行了時間 t 過後將這個 vruntime 進行嚴格遞增的動作即 t * weight，所以 CFS 在進行任務挑選時即是藉由挑選 runqueue 中 vruntime 最小的任務 linux 2.6.23 之後使用 RT-mutex 來解決優先權反轉問題，並且讓 preemptive time 變為可變動的，並加入了 sleep fairness 的概念讓等待的任務可以獲得更多的時間，並解決了在 O(1) 排程器上的問題 CFS 中會分配 nice value 來決定任務的友善程度，並使用 sleeper fairness 的概念讓正在等待的任務可以再恢復活動時可以拿到足夠的 cpu 使用 CFS 中不使用傳統的時間片段概念，即分配一定時間給 process 等用完之後再重新分配，而是只考慮 process 的在 runqueue 中的等待時間對於公平的定義即任務可以平均的被分配到均等的 cpu 使用，但是在多工的環境下，當一個 process 在執行時，就一定會有等待執行的 process 這樣就造成了不公平的情況，為了解決這樣的狀況即藉由挑選等待時間最長的任務來解決，來讓不公平的情況分散出去 #### 2.3.1 Proportional-Share Scheduling CFS 中使用了按比例分配 cpu 使用的方式，來取代給予任務一個最佳的時間，以讓每個任務都可以獲得特定比例的 cpu 時間，並只專注對 runnable 的任務進行分配在 CFS 中使用 nice 值來控制任務可以拿到 cpu 的比例，將 nice 化做權重做使用在計算時使用由 nice 值所轉化的權重來作為可以拿到 cpu 的配額，當 nice 值相等時不管大小多少都可以拿到一樣比例的 cpu 使用當任務執行的時間越多之後拿到的時間會越來越少，取得 cpu 時間較少的任務會在 runqueue 的前端，新進的任務不管優先權都會被放置到 runqueue 的尾端，就算是較高優先權的任務也需要等待低優先權的，對於等待的任務會有回饋機制讓他們恢復時會在 runqueue 較前端的位置 CFS 在 cpu 時間上的分配是依照 nice 值相對的百分比的差異進行分配不單單只是靠著 nice 值來決定，CFS 會選擇 virtual runtime 最少的 process 來作為下一個排程的對象，若總是挑選落後的 process 會導致一直周旋在不同的 process 之中，所以在 CFS 中會給予每個 process 一個最小的 virtual runtime 讓 process 至少完成這個時間，用這樣的方式讓 process 的 virtual runtime 可以趨近平衡 :::info > The big idea is keeping track of how much total running each task has done, measured in units that are scaled in accordance with the task’s weight. i.e., a nice=0 task is credited with 1 ms of running for each millisecond of time that elapses with the task running, but a nice=5 task would be credited with approximately 3 ms of running for each millisecond it actually runs 因為 nice=5 的優先權比較低所以 vruntime 成長的幅度會比較大的意思讓 vruntime 變大使得被選擇的機會變小？在 CFS 中會選擇 vruntime 較小的任務，所以讓 nice 值較高的任務有較高的 vruntime 成長幅度，降低其被選擇的可能 ::: CFS 會在兩種情況下進行任務的轉換，包含 timeslice 結束，另一種為新任務進入到 runqueue 中 #### 2.3.2 weight function 在 CFS 中權重的公式大致與 $w(n)=\frac{1024}{(1.25)^n}$ 相等， n 為 n 個 process，1024 為由 nice 0 所對應的任務權重 nice 值介於 -20 ~ 19 當其值越高代表對其他 process 越友善，也就是優先權越低，其在 CFS 中的值也會越低，並且在 linux 核心中為了要節省計算的成本所以將權重的值建立成權重表，來進行查找而當每降低一個 nice 值的等級都會多獲得 10% 的 cpu 時間 ```c const int sched_prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, } ``` 每個任務會分配到一定比例的 cpu 使用其公式會與權重相關以 n 個任務為例即 $CPU\%$$_a=\frac{w(n_a)}{\sum_{i=1}^{n}w(n_i)}$ #### 2.3.3 Assigned time and virtual runtime 在 CFS 中會決定任務可以得到多少的 cpu 使用取決於 4 個值包含 target latency、minimum granularity、前面提到的任務權重以及在 runqueue 中所有任務的權重 target latency 又可以稱為 scheduler period 也就是每個任務取得 cpu 後至少都執行一次的時間，有 4 個任務四個都執行一次的時間 minimum granularity 指的是系統最短可以分配給任務的時間，每次分配的時間太短會造成 context switch 的 overhead 所以必須確保一定長度鑑於上述的內容對於任務被分配的 timeslice 即為 $assign\_time = target\_latency\\\ \frac{task\_weight}{total\_weight}$ #### virtual runtime 為了要選擇下一次運行的任務，會追蹤任務運行的時間藉此知道其運行的時間，但是如果只用運行總時間來作決定會忽略掉任務的優先權，因此 CFS 藉由將真實時間與權重進行相乘得到一個相對的時間即為 virtual runtime $vruntime = delta\_exec* \frac{nice\_0}{task\_weight}$ 若 nice = 0 代表真實時間等於虛擬時間，較高優先權的任務 vruntime 成長較慢，可以使用更多的時間最後在任務的挑選上即挑選擁有最小 vruntme 的任務作為下一個運行的任務，最少的就是最應該被補償的任務 #### 2.3.4 Runqueue 排程器在挑選任務時會從 CPU 的 runqueue 中進行挑選，任務進入 sleep 狀態時會維持一樣的 vruntime ，其他任務則會持續增加，當任務從 sleep 狀態醒來重新加入到 runqueue 時，vruntime 不變就會造成優先權相對於其他任務而言來的更高，除此之外新任務被加入時也會有類似的狀況發生為了避免不公平的情況發生，排程器會追蹤當前 runqueue 中的 min vruntime，當新任務加入時，進行 vruntime 的更新，當任務從 sleep 狀態醒來時則會確認其 vruntime 是否小於等於目前最小的 vruntime ，若沒有則將其設定為最小並加入到 runqueue 的尾端進行等待，用這樣的方式來將 runqueue 中任務的 vruntime 維持在一定的範圍內，防止不公平得情況發生若任務是由 fork 的方式產生則會繼承親代的 vruntime 防止相同任務藉由不斷 fork 不斷持有 cpu 的情況發生 ### 2.4 EEVDF CFS 排程器強調在任務之間的公平性以及在 cpu 之間的穩定，但是存在著 latency 的問題，EEVDF 除了可以公平的分配 cpu 的使用還解決了前面 CFS 的 latency 問題，EEVDF 不僅是依需求分配，還會監控任務的行為，舉例來說當有一個比較快可以結束的任務可執行時 EEVDF 會調整其優先權，以這樣的方式來對應不同種類的任務型態 CFS 中根據 nice 來給予 cpu 相對應的使用比例，當任務的 nice 值較低時會得到比較多的使用，但是大多數任務其實不需要那麼多的使用時間而 EEVDF 提出了一項新的方式會根據 process 的數目以及 process 們的 nice 值進行調整，依造 latency-nice 來動態分配時間，latency-nice 即用來表達任務對時間的敏感度，當 latency-nice 較低時會得到比較頻繁但是較少的 cpu 使用，而當較高時會得到較少但是較長的分配，不同於 CFS 排程器，EEVDF 還提出了 eligible time 的概念來強調公平性在 EEVDF 中使用了增強的紅黑樹結構來作為 runqueue ，與 CFS 不同的還有 EEDVF 使用了 **virtual deadline** 作為選擇標準，搭配 **eligible value** 來做選擇，其中還有會影響 deadline 的 **Lag** 值代表預先配置給任務的時間與任務真的消耗的時間的差值，當 lag 為正時代表任務被服務不足要給多一點優先權，而負的代表任務被服務過度，要進行推遲直到其恢復資格 :::info 這裡的 latency 是指像是在 time keeping 提到的 scheduling leatency 的問題嗎？當 HZ 設置大小不一時導致任務執行完畢之後會有一段空的時間？而比較快完成的任務會有比較長的時間來等待下一個中斷 ::: ### 2.5 Multiprocrssor 在 linux 2.0 時就有提出多處理器的概念，但轉換到多處理器上需要考慮到更多的因素，包含同步的問題以及排程方式的改變，如何平衡在多個核心的工作負載充滿了挑戰性在多核處理器上同步存取會需要花費大量的效能以及會有 context switch 的負擔使得讓 per-core runqueues 這樣的架構成為了一個好的決定，讓每一個 core 都有自己的 runqueue 讓其可進行排程，並週期性的進行負載平衡在現今處理器的頻率有著物理上的限制，因此要增加效能的的方式變成增加更多的處理器，讓 process 可以平行處理，但是資源共享的問題以及彼此之間的溝通也成為了一個限制最為困難的問題即為 lock ，至少要保護 runqueue 的運行多核還要考慮 load balance 其中 migrate ### 2.5.1 load 造成 load 的原因包含系統資源分配包含 cpu 容量、I/O 頻寬以及任務資源利用的評估等等 **Per-Entity Load Tracking** 只用 weight 決定 tasks 的負載會導致沒有考量到 cpu bound 以及 I/O bound 的問題，可能會導致 cpu bound 的任務都被安排到同一個處理器上，要監控任務對於 cpu 的使用時間，所以對於任務的負載要同時給予一個權重並搭配 cpu 的使用率才能進行評斷，而 cpu 的負載即可以用任務的負載總和來進行評斷鑑於上述的原因，所以在 linux 核心中使用了 PerEntity Load Tracking (PELT) 來進行任務的負載追蹤，其作用在於紀錄任務的統計資料，方法為將時間由過去到現在藉由時間線切分成多個固定的 time slot，每個 slot 中有貢獻值分成負的以及正的，當任務在 cpu上執行時其貢獻值會為正的，而統計的資料為提供當前 cpu 的負載程度所以對於舊的值會進行衰退的計算 $load\_t=u_t +u_{t-1}*y^1+...$ t 代表當前時間而 t-1 代表前一個 y 代表衰退率 #### 2.5.2 Load balance 對於多核心而言最好的狀況是讓工作負載可以被平均的分派到各個核心上，沒有任何一個核心的負載是少於其他核心的多核處理器上要將任務收集起來的較為直覺的方式就是使用一條 global 鏈結串列當核心變得空閒時會去進行新任務的取得，但是使用這樣的方式會使得要對共享的鏈結串列進行互斥存取而一次只能有一個核心去存取鏈結串列的資料，其他的核心要進行等待，這樣會導致整體效率不佳，除此之外還需要考慮 cache coherence 的議題因此 kernel 讓每一個核心都有自己的專屬資料，藉此減少互斥的負擔以及 cache 存取議題，負載平衡也成為了一個重要的機制，讓任務可以均衡的在各個處理器上執行在 CFS 中包含了三種不同的負載平衡方式包含 1. Regular balance 為標準的週期性執行， 2. Idle balance 為當核心處於 idle 時會收尋新的任務， 3. Wakeup balance 為將喚醒的任務放置到負載較低較近的核心 **Migrating tasks** Linux 會週期性的確認每個處理器的負載分配任務給各個 cpu，與排程的精神類似藉由將 cpu 的時間讓每個任務都可以平均的拿到 cpu 的使用排程器可以隨意的將任務在 cpu 之間進行移動，來維持 cpu 之間的負載，此部分為排程器中的 load balancer 進行，其中包含兩個演算法 * 分別為 pull migration 當自己較為空閒時將任務從附近的 cpu 移動到自己這邊 * 以及 push migration 為 kernel 的任務藉由尋找核心中負載不平衡的情況，一找到就將負載較重 cpu 的任務轉移到負載較輕的 cpu cpu 的記憶體存取在任務轉移上是一個重大的成本，在 uniform memory acess (UMA) 架構上各個 core 存取同個記憶體但一次只能一個 core 存取導致效率不佳，使用讓每個 core 都有自己的記憶體來進行解決但這樣會導致每個 core 的記憶體存取以及頻寬不一致，所以記憶體會有分成 core 自己的以及其他 core 的記憶體，對於任務移動的成本也不一樣，導致有時就算負載不平衡但是在同一個 core 上反而更有效率 **Scheduling Domains** Scheduling Domain 為 CPUs 的集合，cpu group 為 Domain 中的一群 cpu，一般來說 cpu 不能為多個 group 的成員，但是在 NUMA 中可能會發生，而排程器進行負載平衡的對象從各個 cpu 變成以 cpu group 為單位進行調整 :::info 會存在 cpu 是在不同 domain 的狀況嗎？ ::: 為了讓任務可以在各個 domain 中移轉，因此在這之上有著更高層次的 domain 進行管理 :::info > To enable tasks to migrate between domains, a higher-level domain encom- passes all the CPUs. This domain is divided into two CPU groups, one for each pair. Although the two groups are balanced, the scheduler does not attempt to balance the load within a group. 這邊是指將更高層次的 domain 在分割成小的 domain 嗎 ::: **CFS Load Balancing** CFS 也利用了 scheduling domain 的概念，不是對於單個 core 進行負載的平衡，因為這樣的方式會忽略掉記憶體的 locality 議題以及 NUMA 的特性，而是將核心組成一個拓樸階層的概念由多個 core 組合成一個 domain 在內部有著環狀鏈結串列的組別，並對 domain 進行負載平衡 #### 2.5.3 CPU isolation 造成 jitter 最大的來源在於進行排程以及外部中斷時，任務的切換引發 jitter 會造成在對於性能關鍵任務上進行 CFS 排成被 preempte 時造成影響，解決方法為將一些不重要得任務移動到別的 cpu 上，或是讓重要的任務可以在以 real-time 的方式運行負載平衡對於系統的 throughput 有好的幫助，但是會影響到 real-time 任務的效能，若是把一般的任務移轉到 real-time 的系統就會造成問題，因此可以藉由 cgroup 的 cpusets 來進行資源的管理，防止上述的情況發生 #### 2.5.4 Unintended Side Effects 可運行任務的等待導致了 cpu idle ，而對於負載平衡的進行，不應該直接從負載最高的 cpu 將任務移動到負載最低的 cpu 這樣的話會忽略掉 UNMA 架構以及 locality 的議題，負載平衡使用了 hierarchical 的概念對於 cpu 而言在上層的單位為 scheduling domain，負載平衡一次只會發生在 domain 中的一個 cpu core 上來避免重複的任務發生 Group Imbalance Bug 即如果當進行負載平衡時導致者 cpu 的平均負載低於要進行對象 cpu 的平均負載可能會發生問題，不能只依賴平均值而是選擇使用 groups 中最小的負載或是負載最低的 cpu 來作為標準 Scheduling Group Construction 為可以使用特定命令將任務固定到核心上面，如果 group 之間相差距離為兩個 hop 則就算可以從其進行任務竊取也會選擇不進行 :::info > The load balancing task might be able to avoid stealing the groups if they are two hops apart two hops part 意思 ::: Overload on Wakeup 當任務在 group 中被喚醒時就算其他 group 為空閒得也會將任務安排在喚醒 group 的 core 上 Missing Scheduling Domains 重構錯誤導致所有執行緒都在同一個核心上運行 :::info > The last bug seems to have resulted from a refactoring error. Such changes could cause all threads of an application to run on a single core, instead of being distributed among all available cores, if a core was removed and later reintroduced. refactoring error 重構錯誤是什麼意思 ::: ### 2.6 Energy-Aware Scheduling (EAS) 低功耗在一些小型行動設備上是一個重要的議題，所以將排程與 cpu 的管理系統進行結合，所以會以較為節能的方式進行任務得安排，而單單將任務安排在空閒的 cpu 上並不是一個節能的方式因此 EAS 將排程更加適應 big.LITTLE 系統在 EAS 中有一個 cpuIDLE 的子系統會在 cpu 沒有任務時選擇低電耗或是 idle 模式，大多數的 cpu 都有多個不同的 idle 模式，因此 cpu 的 CPUIdle 需要收集 cpu 的使用率資料，來挑選適合得模式，對此在排程器上面也需要這樣的資料就造成了重複的作業流程，因此將 CPUdle 以及排程器進行結合，藉此讓排程器可以意識到 idle 的 cpu ，讓排程藉此進行挑選另外整合到 EAS 中的子系統 CPUFreq ，對 cpu 而言較高的頻率會使得 cpu 消耗較高的能源，CPUFreq 允許對頻率進行調節 **Arm big.LITTLE architecture** 為非對稱的核心架構，在發現行動設備上需要結合高計算跟低計算的要求，使用較為耗能但功能較強的 big core 以及較為省電但功能較弱的 LITTLE core，並在必要時才使用 big core，也因為這樣的設計什麼時候該將任務安排到何種 core 上也是一個重要的議題 **Dynamic Voltage and Frequency Scaling** 在過去 cpu 為固定頻率，但到了現在有了動態調節頻率的能力而 DVFS 是一種可以藉由變化頻率以及電壓來調節頻率的技術，在 linux 核心中使用 cpufreq 以及 frequency governors 來進行頻率的調節並可以在 ARM 上面使用來搭配 big.LITTLE 的設計 **Scheduling in Asymmetric Multi-Cores** 也為了在非對稱的 core 上運行還需考慮， * 任務需在何種核心上運行 big LITTLE * 任務是否值得在不同核心進行 migration，或是不同種類(big, LITTLE)的核心上 migration * 以及是否值得在全力的 cpu 上運行或是，需要在會影響性能上來調節頻率對於現有的 CFS 以 throughput 為重點考量，當有任務到來時會將其配置在空閒的 cpu 上，但這樣並沒有考量到耗能，所以 EAS 被設計來進行搭配 #### System Pressure and CPU Capacity [system pressure on CPUs capacity and feedback to scheduler - Vincent Guittot](https://www.youtube.com/watch?v=Nls5F6BS6Vw&t=601s) [CPUfreq](https://www.kernel.org/doc/Documentation/cpu-freq/user-guide.txt). 時脈調節允許使用者可以即時的調整時脈的速度，藉由這樣的方式可以更加省電，較低的時脈可以減少 cpu 的能耗支持頻率調節的 cpu 可以即時的在頻率以及電壓之間切換，確保在需要高性能時切換到較高的頻率，而在不需要時切換到低頻來節省能源的消耗 policy. 在系統中可以選擇較高或是較低的頻率限制，以及傾向更加省電或是處理能力優先 Governor. 在 confreq 中使用 governor 進行 cpu 頻率的調節，來決定 cpu 在調節時的限制，其中有多種不同的 governor 可供選擇，並可以藉由寫入 /sys/devices/system/cpu/cpu[number]/cpufreq/scaling_governor 來選擇所需的 governor [Operating Performance Points (OPP)](https://docs.kernel.org/power/opp.html). 現今的 SoCs 中會有多個 [subsystem](https://www.kernel.org/doc/html/next/process/maintainer-soc.html) 相互運行，並且不是所有的模組都要經常用到最高的頻率，因此為了組織這樣的問題將不同的子模組分成不同的 domain ，允許一些 doamin 可以在低電壓、頻率下運行，而一些 domain 可以在較高的電壓頻率下運行 [Cpu performance scaling](https://www.kernel.org/doc/html/v4.14/admin-guide/pm/cpufreq.html). 大多數現今的處理器可以在不同頻率以及電壓下運行，即上述提到的 OPP ，較高的頻率以即電壓下可以一次執行更多的指令，但會消耗更多的能量因此需要在這兩者之間作抉擇 [Qualcomm LMh (Limits Management Hardware)](https://lwn.net/Articles/865752/). 為 Qualcomm SoCs 上的基礎架構，可以藉由軟體的方式來控制硬體的能力像是溫度以及電流等 [DTPM (dynamic thermal and power management)](https://lore.kernel.org/linux-pm/5679624.lOV4Wx5bFT@pce/T/). 動態調整不同裝置的功耗確保熱能的限制的技術，在需要性能時調高頻率以及電壓，反之 [Energy Model](https://docs.kernel.org/power/energy-model.html). 能源模型框架作為 kernel 子系統與 driver 之間的 interface 讓子系統可以知道關於設備能耗的資訊藉此來進行決策能耗值以微瓦 micro-Watts 或是 abstract scale 來表示，不同的 subsystem 有不同的表示方式 [Energy Aware Scheduling](https://docs.kernel.org/scheduler/sched-energy.html). 讓 cpu 有能力去預期其決定對 cpu 能耗的影響，EAS 使用 EM 來選擇能耗高的 cpu，並且只能在 big.Little 的架構使用 ### 2.7 Miscellaneous CPU Schedulers 介紹其他系統排程器之差異 ## CH3 Implementation of the Linux scheduler ### 3.1 Structs and their role >Low-level programming is good for the programmer’s soul [name=John Carmack] ### task_struct 在 linux 中每個任務都會以 task_struct 來表示，其包含了任務的所有資訊，對於不同的架構會有不同存取 tack_struct 的方式，而巨集 current 以及函式 get_current 可以用來存取目前任務的 task_struct **thread_info** 其中存在一個 thread_info 的結構成員，其原先存放在 kernel stack 的底部，但為了防止因為 kernel stack 發生 overflow 所發生的問題，以及當任務結束之後可以快速的將其釋放而移動到 task_struct 中，將 thread_info 嵌入在 task_struct 的結構使用需要事先定義 CONFIG_THREAD_INFO_IN_TASK 才可使用 ```c struct thread_info { unsigned long flags; /* low level flags */ u32 status; /* thread synchronous flags */ }; ``` flag 為 TIF_NEED_RESCHED 被設置得地方，當其被設置時即代表可以進行排程，會去呼叫 scheduler()來進行排程 **sched_entity** 對於排程器而言，不管是 process 、 thread 或是一組的 process 在排程器看來皆為 sched_entity，所以當排程器進行排程時是對 sched_entity 進行排程而不是 task_struct 而且在 runqueue 中存放的也是 sched_entity 的結構 >By organizing the entities in hierarchies, we can group together the tasks and schedule them as a single schedulable entity. sched_entity 可以被組織成 hierarchy 的 entity 來達成 group scheduling 的排程方式，這樣的功能是可以自由選擇是否要使用，將 entities 階層化進行 group scheduling 可以讓多個 task 被看作程單一的 entity，也就是在一般情況下多個任務會依序在 runqueue 中各自被進行排程，而使用階層化的 entity 就可以將任務們看成單一 entity :::info >The scheduler decides which of the two entities to schedule, as if there were only two tasks running, and then repeats the process for the sub-queue. As stated earlier, a sched_entity does not always correspond to a process; only the leaves of this structure correspond to a task. 這邊的意思為把 entity 作為一個 group 的代表之後，就不把他作為一個 task entity，而是作為一個代表的 group 並使用這個 group entity 中 subrunqueue 中的任務來作為排程的對象？而這個 group 中的各個 sub runqueue 會形成像是樹狀的結構 ::: 舉例來說假設有兩個使用者任務進行排程其中一個使用者有 19 個任務而另外一個使用者有 1 個任務，對於 CFS 而言如果有 20 個任務，每個任務都會獲得 cpu 的 1/20 也就是 5 % 的使用，對於排程器來看會是公平的但對於使用者來說就不公平，因此當使用 scheduler entities 之後會先將 cpu 的使用分成各 50% 給兩位使用者，再去進行分配而第一個使用者的 19 個任務就會平均去分配這 50% 的 cpu 使用也就是其每個任務會獲得 50 / 19 = 2.6% 的使用 **sched_entity** 中成員包含 * load_weight. 為 entity 的權重 * struct rb_node run_node. 作為紅黑樹的節點 * on_rq. 看 entity 是否在 runqueue 中 * exec_start. 任務在 cpu 中開始的時間 * sum_exec_runtime. 在給予權重之前任務實際在 cpu 上運行的總時間 * vruntime. 任務的 weighted time，即權重比例*時間 * struct cfs_rq *cfs_rq. entity 被放置的 runqueue * struct cfs_rq *my_q. 如果為一個 group 的 entity 此即為 subrunqueue 其中存放著 group 的任務在 sched_entity 中的 rb_node 以及 cfs_rq 皆為紅黑樹結構，藉由 exec_start 跟 sum_exec_runtime 來計算 vruntime ### sched_class 在 commit 中描述移除 next 指標使用陣列來放置 sched_class 維持不同的優先權，而藉由將 sched_class 放置在自己的資料區域來優化排程函式，使用這樣的方式就不用比較類別而是可以比較指標來取得相對得優先權排程器會選擇較高優先權的類別中的任務進行排程，在高優先的類別中沒有任務之後才會到低優先權類別中進行選擇 :::info > To guarantee the order of scheduling classes, each of them would be placed in their own data section 將這些類別放置在特定的記憶體區域使用特定函式去存取 ::: 而在 sched_class 中大量使用了函式指標來將每個排程器類別建構成多型的方式，而這樣的方式就是使用了物件導向的程式設計，即存取 interface 但是其內部實作是不同的概念，即代表就算 c 語言不支持物件導向類別的使用，還是可以使用物件導向的概念進行實作 sched_class 中包含了 scheduling class 中所有的 method，並隱藏了內部的實作，這樣得設計讓開發者可以更有彈性的去增加新的排程類別這樣的設計也代表可以實作各種不同的排成方法，而 CFS 即是其中一部份，搭配 96 頁函式說明 :::info > sched_class collects all the methods of a scheduling class, which forms a table, what is the pointer in task_struct points to. > forms a table 意思是指像是 c++ 使用 virtual 時會建立一個 virtual table 的意思嗎 ::: 在進行排程器類別的走訪時藉由多型的方式以降序選擇下一個任務 **mm_struct** 可執行映像檔：為 2 進制文件，包含了可執行機器指令以及資料為 process 虛擬記憶體的抽象介面，包含了可執行映像檔的資訊、以及指向分頁表的指標跟映照的虛擬記憶體位址，當排程時在進行 context switch 也會需要對其進行更改 :::info 為什麼要將 mm 設定為 NULL kernel thread 可以存取 kernel 的所有區域？ p.223 ::: mmap 包含了一個鏈結串列內容為虛擬記憶體區域，其包含了 excution code、資料以及 libraries 的內容，這些虛擬記憶體的區域皆為在執行時才會進行分配在 linux 中使用了 on demand paging 的方式不是直接分配實體記憶體而是創建 vm_area_struct 的結構，而對於 process 對虛擬記憶體進行存取時，會引發 page fault 要當 linux 確認寫入的位址為目前 process 的虛擬記憶體區域才可以若成功 linux 會創建一個 page table entries 來分派實體的記憶體頁面給此 process，最後 process 可以從發生 page fault 的地方恢復執行 profs 為特別的檔案系統其包含了所有 process 的 kernel 資訊，讓 user space 可以簡單查看內容，內容中的 se 為 sched_entity ```shell $ cat /proc/1/sched ``` [Red-black Tree](https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/tree/lib/rbtree.c) 當任務為可執行時會被以紅黑樹的形式進行儲存，其插入、刪除以及搜尋皆為 O(h) 與其樹高息息相關，由於 CFS 會搜尋 vrutime 最小的任務，因此會挑選紅黑樹中的 leftmost node 即為樹中最小，也就是下一個會進行排程的任務在 linux 核心中的紅黑樹分成 cache 版本以及 non-cached 版本差異在於 root 會有一個額外的指標指向最左節點，藉由這樣的方式就可以在 O(1) 的時間取得 vrutime 最小的任務當任務被 blocked 時不會重新回到佇列，而當 timeslice 結束時或是被 preempted 時會根據新的執行時間被重新插入回紅黑樹之中，這時就需要花費 O(logn) 的插入時間紅黑樹的基本性質 1. 所有的節點皆為紅或黑 2. 葉節點以及皆為黑 3. 葉節點為空 4. 非葉節點有兩個子節點 5. 若節點為紅，其子節點必為黑 6. 從 root 到任意葉節點其黑色節點數相同紅黑樹有著在插入以及刪除需要兩次的旋轉以及維持著 O(logn) 的搜尋時間，以及跟 AVL tree 得差異在於 AVL 有著更多的高度平衡操作讓高度差不超過 2 ，也因為這樣的原因使得其比紅黑樹來的慢，對於空間的使用紅黑樹需要用額外的位元儲存節點的顏色，而 AVL 樹要整數儲存高度差，對於進行節點的搜尋使用 AVL tree 會有較好的效果，而如果是較為頻繁的插入刪除則使用紅黑樹因為有著比較少的高度平衡即旋轉的操作在 linux 核心中，除了排程器之外在其他地方也有著紅黑樹的使用包含了 deadline 跟 CFQ I/O schedulers 使用紅黑樹追蹤要求以及虛擬記憶體的追蹤也是使用紅黑樹讓 rb_node 對齊 long 因此可以將未使用的位元用來儲存節點的顏色 ### Red-black tree runqueue representation [hardware thread 與 soft thread 差異](https://stackoverflow.com/questions/5593328/software-threads-vs-hardware-threads) 每個 cpu core 都有自己的 runqueue，並用 `struct rq` 表示，但是 struct rq 不像字面上的 queue ，而是作為一個 scheduler context (這裡的 context 即任務的資料、資訊) 使用包含了 `struct cfs_rq cfs (CFS runcqueue)`, `struct task_struct __rcu *curr (當前任務)`, `unsigned long next_balance (jiffies value, 下一次可以嘗試進行 load balance 的時間)`, `struct sched_domain __rcu *sd (此 runqueue 所屬的 scheduler domain , 第二章提到由多個 scheduler group 組成)`, 除此之外在 per-CPU 的 runqueue 之中也包含了不同的 scheduling classes 像是 cfs, rt 以及 dl 等等，而在 runqueue 中的節點是使用 sched_entity 結構中的 run_node 使用方式與 kernel lists 類似完整版本 [struct rq](https://elixir.bootlin.com/linux/latest/source/kernel/sched/sched.h#L985) ```c struct rq { // ... struct cfs_rq cfs; struct rt_rq rt; struct dl_rq dl; // ... }; ``` ```c struct sched_entity { // ... struct rb_node run_node; // ... }; ``` :::info struct sched_domain __rcu *sd ::: 在不同的 sched_class 中以 cfs_rq 為例，使用 tasks_timeline 存取紅黑樹的資料這邊是以 cached 版本也就是會紀錄最左節點來做使用，而在 cfs_rq 中會紀錄最小的 vruntime 在任務加入以及被移轉時到此 rq 時會對新進節點的 min_vruntime 進行更新 ```c // File include/linux/sched.h struct cfs_rq { // ... u64 min_vruntime; struct rb_root_cached tasks_timeline; // ... }; // File include/linux/rbtree.h struct rb_root_cached { struct rb_root rb_root; struct rb_node *rb_leftmost; }; struct rb_root { struct rb_node *rb_node; }; ``` 對於 real-time 類別的 runqueue 而言是使用 array 來實作，並搭配優先權的鏈結串列，每個優先權用鏈結串列來維持，而當優先權至少有一個任務時對應優先權號碼的 bitmap 就會被設置為 1 ```c // File kernel/sched/sched.h struct rt_prio_array { DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_RT_PRIO]; }; // File kernel/sched/sched.h struct rt_rq { struct rt_prio_array active; ... } ``` ### 3.2 Time keeping (scheduling latency) 排程器需要知道任務執行的時間來確保下一次的 preempt，因此 kernel 需要一個硬體的 timer 來達到上述要求，timer 會以固定的頻率發送中斷，藉由這樣的方式可以以 **兩個中斷之間的時間** 來作為一個 **tick** 的單位，而其頻率為 tick rate，在內部被定義為 HZ 舉例當 HZ 為 100 時每秒會有 100 tick 也就是 1 秒有幾個 tick 不同的 HZ 會對系統造成重大的影響，有較大 HZ 的 timer 具有較細致的顆粒度的特性即 1000 代表每秒會有 1000 tick，可以減少 scheduling latency 也就是當外部事件發生時與執行相關執行緒的時間，好處是可以更精確地控制任務的發生以及更為準確的追蹤時間，缺點是會有更多的中斷進而導致 interrupt handler 的執行，讓任務執行時間變得更少，造成了處理器的負擔 :::info HZ 為 100 為例，即在任務剩下 2 ms 時離開，但是下一次的中斷在 10ms 後，這樣任務會獲得額外的 8ms 導致其他任務必須等待更多的時間，但若是 HZ 設置太大，則會造成延遲變得很小使得 interrupt handler 要一直執行會造成 processor 的使用率變低 ::: > scheduling latency (or wakeup latency) is the time between the firing of an external event and the execution of the relevant thread. **Jiffies** 為自系統開始所累積的 tick 數即 tick 總數，每當 interrupt handler 執行其值就會進行累加，將 seconds * HZ (每秒有幾個 tick ) 來得到 jiffies 的值， jiffies (tick 總數) / HZ (每秒有幾個 tick) 得到秒數 sched clock() 會返回系統運行的時間單位為 nanosecond，用此計算出沒有權重化的絕對時間 se->sum_exec_runtime ```c unsigned long long __weak sched_clock(void) { return (unsigned long long)(jiffies - INITIAL_JIFFIES) * (NSER_PER_SEC / HZ) } ``` :::info INITIAL_JIFFIES 作用 ::: 對於不同的架構而言會有不同的 interrupt handler 其會執行 tick_periodic，內部會進行 jiffies 值得更新，並統計任務的 runtime 以及當任務的 timeslice 完成時，會觸發排程 **sched clock()** 回傳系統時間 (ns) **Timer interrupt handler** 執行時由 tick_periodic() 使用兩個重要函式進行資料更新以及重新排程，包含 do_timer() 以及 update_process_times()這兩個函式前者增加 jiffies 的值以及負載統計資料，後者更新統計資料以及任務的 runtime 而當任務的 tmeslice 用完會重新進行排程在 `update_process_times()` 中會有 `scheduler_tick()` 做為排程的進入點 ### 3.3 Scheduler routines 基本觸發排程的時機 * 第一種為目前任務的 timeslice 結束時為定週期性得進行確認也就是每個 tick 會進行一次 * 第二種為當任務被放進 runqueue 之中確認，即任務被喚醒或是建立時 * 除此之外也有其他觸發排程的方式像是直接呼叫 schedule() 但是這樣的方式較少會發生 ### 3.3.1 Periodic reschedule CFS 使用硬體的 timer 週期性的發出中斷，在中斷時會將系統控制權交給 handler 執行 tick_handle_periodic() 來更新 kernel 的計時狀態並呼叫 update_process_times() 中的 `scheduler_tick()` 進行排程執行順序由 `tick_handle_periodic()`->`update_process_times()`->`scheduler_tick()` schedule() 流程圖： * 先 disable preemption 將 runqueue 上鎖 * 先處理原先的任務包含將其從 runqueue 中移除或是重新放回 runqueue * 判斷 runqueue 是否為空若為空則進行 idle balance 從其他 cpu 上轉移任務過來並到下一步挑選下一個任務，若不為空則直接挑選下一個任務 * 挑選任務時會先從高優先權的 sched class 中挑選是否有可用的任務 * 挑選完後確認挑選到的任務是否與原先的任務相同，若不相同則進行 context switch 切換任務並解開 runqueue 的鎖允許 preemption，若挑選到的任務與原先相同解開 runqueue 的鎖允許 preemption --- ```c // File kernel/sched/core.c void scheduler_tick(void) { int cpu = smp_processor_id(); struct rq *rq = cpu_rq(cpu); struct task_struct *curr = rq->curr; struct rq_flags rf; sched_clock_tick();// 1 rq_lock(rq, &rf); update_rq_clock(rq); // 2 curr->sched_class->task_tick(rq, curr, 0); // 3 cpu_load_update_active(rq); calc_global_load_tick(rq); psi_task_tick(rq); rq_unlock(rq, &rf); perf_event_task_tick(); #ifdef CONFIG_SMP rq->idle_balance = idle_cpu(cpu); trigger_load_balance(rq); #endif } ``` **scheduler tick()** 中的 1. `sched_clock_tick()` 用來更新 per-cpu 中 sched_clock_data 的結構內部會使用 sched_clock()， 2. `update_rq_clock()` 更新目前 cpu runqueue (cpu_rq(cpu))的 clock_task，內部使用 update_curr()用途為更新目前運行任務的 task_struct 的資料 3. 使用 task_tick() 根據目前執行任務的 sched_class 更新統計資料，也就是說目前任務為 fair class tick 就會對應執行 task_tick_fair() ```c static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) { struct cfs_rq *cfs_rq; struct sched_entity *se = &curr->se; for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); entity_tick(cfs_rq, se, queued); } if (static_branch_unlikely(&sched_numa_balancing)) task_tick_numa(rq, curr); update_misfit_status(curr, rq); } ``` **task_tick_fair()** 找到當前任務的 sched_entity 並更新其內容 scheduling group: 如果找到的 entity 是一個 shceduler group 此 entity 會是 group 的代表會有一個 my_q 指標不為空為 subrunqueue 指向 group 中的 entity，也就是當其為 my_q 不為空時會一直往下尋找直到找到一個 my_q 為空的 leaf entity * 由 cfs_rq_of(se) 找到 shced entity 被排程的 runqueue (此為止有單一任務無 group 的情況) * 並由 entity_tick(cfs, se, queued) 更新 entity 的統計資料，並決定是否要換別的任務執行 :::info 對 scheduler group 的 my_q 概念較無法理解 > This is going to be a leaf of the hierarchy, and if the task is not part of a group, it is also the root. shceduling group 架構 > 1. If a process inside a group still deserves more time, > 2. but the entire group has finished its time, > 3. and another group deserves the CPU 三點疑惑 ::: **entity_tick()** ```c static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) { /* * Update run-time statistics of the 'current'. */ update_curr(cfs_rq); /* * Ensure that runnable average is periodically updated. */ update_load_avg(cfs_rq, curr, UPDATE_TG); update_cfs_group(curr); #ifdef CONFIG_SCHED_HRTICK /* * queued ticks are scheduled to match the slice, so don't bother * validating it and just reschedule. */ if (queued) { resched_curr(rq_of(cfs_rq)); return; } /* * don't let the period tick interfere with the hrtick preemption */ if (!sched_feat(DOUBLE_TICK) && hrtimer_active(&rq_of(cfs_rq)->hrtick_timer)) return; #endif if (cfs_rq->nr_running > 1) check_preempt_tick(cfs_rq, curr); } ``` **entity_tick()** 中的 **update_curr()** ，用來更新 runtime 的統計資料，並指使用了 cfs_rq 即當前任務的 runqueue，關於 `virtual clock` 的結果都會用此函式計算，即代表在 periodic schduling 中的多個地方會使用到 update_curr() 也因為 kernel 需要計算負載資料的時間差所以必須更新 process 在 cpu 上執行的實體時間以及虛擬時間 ```c static void update_curr(struct cfs_rq *cfs_rq) { struct sched_entity *curr = cfs_rq->curr; u64 now = rq_clock_task(rq_of(cfs_rq)); u64 delta_exec; if (unlikely(!curr)) return; delta_exec = now - curr->exec_start; if (unlikely((s64)delta_exec <= 0)) return; curr->exec_start = now; schedstat_set(curr->statistics.exec_max, max(delta_exec, curr->statistics.exec_max)); curr->sum_exec_runtime += delta_exec; schedstat_add(cfs_rq->exec_clock, delta_exec); curr->vruntime += calc_delta_fair(delta_exec, curr); // vruntime update_min_vruntime(cfs_rq); if (entity_is_task(curr)) { struct task_struct *curtask = task_of(curr); trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime); cgroup_account_cputime(curtask, delta_exec); account_group_exec_runtime(curtask, delta_exec); } account_cfs_rq_runtime(cfs_rq, delta_exec); } ``` curr->exec_start 為當 entity 被排程器選擇並執行的時間，與目前的時間相減得到任務運行的時間 delta_exec，並用 delta_exec 更新 sum_exec_runtime 即 entity 總運行時間 virtual runtime 是經過權重化的時間經由 calc_delta_fair() 進行更新計算，若計算出來之後的結果是 runqueue 中最小的，會更新 min_vruntime sched_stat_runtime 當 process vrumtime 更新時會發 signal ，account_cfs_rq_runtime() 是 schedule group 專用的，更新 cfs_rq->remaining_runtime，如果剩餘為 0 時會觸發重新排程 --- entity_tick 的最後呼叫 **check_preempt_tick()** 來查看任務是否要被　preempt，cfs 的 timeslice 會動態調整，所以會計算 ideal_runtime ，並確認任務的執行時間是否超過 ideal_runtime 如果超過會呼叫 resched_curr() 進行 preempt　並重新排程對於 ideal_runtime 的計算會使用 sched_slice() 計算的概念是藉由任務在 cpu 中被分配的比例去進行計算 CFS 不使用傳統的固定 timeslice，而是會進行動態調整， **sched slice()** 會先計算 target latency (任務在處理器上至少運行一次的最短時間也稱 scheduler period) 計算方式為使用 __sched_perio() 裡面會確認正在運行的任務是否超過 sched_nr_latency，如果超過了會讓時間變多避免 slice 太短的問題 * sysctl_sched_min_granularity 任務在被 preempt 之前在 cpu 上被允許運行的最短時間 * sysctl_sched_latency targeted scheduler latency. * sched_nr_latency 有機會在時間內執行一次 targeted scheduler latency 的任務數量 ```c static u64 __sched_period(unsigned long nr_running) { if (unlikely(nr_running > sched_nr_latency)) return nr_running * sysctl_sched_min_granularity; else return sysctl_sched_latency; } ``` :::info > If this entity is part of a task group, the process moves up the hierarchy, and se now points to the parent, which is a representative entity for a runqueue in the task group on a specific CPU. parent 指標會直接指向 representative entity，是指如果是三層的階層結構，最後一層的 parent 會直接指向第一層的 represent entity 嗎 ::: ```c static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) { u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); for_each_sched_entity(se) { struct load_weight *load; struct load_weight lw; cfs_rq = cfs_rq_of(se); load = &cfs_rq->load; if (unlikely(!se->on_rq)) { lw = cfs_rq->load; update_load_add(&lw, se->load.weight); load = &lw; } slice = __calc_delta(slice, se->load.weight, load); } return slice; } ``` 在 sched_sloce 中使用 for_each_sched_entity 由子到親代走訪 entity 的階層結構，會先從低層的 entity 計算其 timeslice，如果目前走訪到的 entity 是屬於 group 的 entity，則會往此 entity 的 parent 走訪即往上層走，並將計算出來的 slice 向上傳遞直到最上層最後再經由 __calc_delta() 計算真實的 timeslice，也因為 timeslice 以及 vruntime 的公式一樣差異在於帶入的數值，所以都是使用 __calc_delta() 進行計算 check_preempt_tick() 最後的 resched curr() 會設定 TIF_NEED_RESCHED flag 代表此任務需要被重新排程，若被設置時會啟用 schedule() :::info > Initially, the lower-level entity’s slice within its runqueue is calculated. If this entity is part of a task group, the process moves up the hierarchy, and se now points to the parent, which is a representative entity for a runqueue in the task group on a specific CPU > 這個階層結構的走訪，以及 represent entity 釐清 > The previous slice calculation is then effectively projected onto a higher-level runqueue 此處 project onto 意思 ::: **Tracing with** ftrace 可以用 ftrace 追蹤 kernel 中運行的特定函式，會提供 kernel 函式的詳細執行流程，並可以藉由這些資訊來評估其執行時間 #### 3.3.2 Reschedule when adding a task to the runqueue 任務被加入到 runqueue 的時機包含 * 當任務被創建 * 以及當任務 wake up 時從 blocked 或是 sleep 改變經由這些狀態改變時需要馬上重新被加入到排程，其原因在於使用者的互動性舉例來說當按下文字編輯器的按鈕時，會需要相對應的 process 可以 wake up 然後立即回應，因此重新排程會很常會發生 **A new process is created** 當 process 被 fork 時其 task_struct, fd, page table address 等資料皆為其親代 process 的複製，並繼承親代的 scheduling policy 當被建立時會呼叫 wake_up_new_task 並將 process 的狀態改成 TASK_RUNNING 並初始化排程的值其步驟為當任務被建立時會將任務鎖住，並且選擇一個核心的runqueue ，將此核心鎖住並任任務加入完成之後解開任務以及 runqueue 對於前面提到的 check_preempt_tick 會週期性的發生，對於新建立的任務而言會呼叫 check_preempt_curr 在一開始時會確認 sched class 優先權教低的 sched class 不能對高優先權的 class 進行 preempt，若確認有教高的優先權之後才會呼叫 resche_curr 重新進行排程對於相同的 class 會呼叫對應的 sched 函式，比較新任務的 vruntime 並更新 vrutime 的值，若目前正在執行的任務有比較小的 vrumtime 則不會被 preempt ，但是在決定是否 preempt 時會確保超過一定比例的 vruntime 才會進行 preempt 來避免過於頻繁的排程對於 SCHED_IDLE 類別則有不同的方式因為 batch 以及 idle 任務不能 preempt non-dile 任務 #### A task is woken up 當任務 wake up 時其操作與建立新的任務相似，任務被喚醒時其 sched_waking 會被觸發並將任務狀態改成 TASK_WAKING，插入到 runqueue 中，task_struct->on_rq 被設定成 TASK_ON_RQ_QUEUED，然後系統會在執行的任務進行確認是否要進行 reschedule (執行check_preempt_curr)，並將任務狀態改成 TASK_RUNNING 最後才觸發 sched_wakeup ### 3.4 Per-Entity Load Tracking #### 3.4.1 Structures 在第二章提及 PELT 用來幫助 kernel 進行負載資料的追蹤，其中使用 struct sched_avg 作為結構體 (在 sched_entity 中)，內部的 load, runnable, util 這三個資料中每個又可以再分成 sum 以及 avg 也就是 load 可以分成 long_sum 以及 long_avg 以此類推 * last_update_time. 最後一次 PERLT 發生的時間 * period_contrib. 從上一次更新後留下的資料尚未貢獻給 PELT :::info >The part of the raw record that remained from the last update and did not contribute to PELT yet, which should be collected in the current update cycle. 是指尚未追蹤的意思嗎 ::: **Scheduling Entity: Task** 對於 task 上面提到的三個統計資料的意義 * Load 代表任務目前為可排程的，其 contributing unit 為正 * Runnable 意思與 Load 差不多 * Util 代表任務真正執行的時間對於 task group 與 task 大致相同即將 task 改成 task of task group 對 runqueue 而言這三個值代表， Load 代表任務在 runqueue 中的總負載，Runnable 代表在給定時間上多少個任務在 runqueue 中為可以執行的，util 代表 runqueue 的 cpu 使用率還包含 RT Runqueue and DL Runqueue 以及 Thermal 跟 IRQ 的負載 #### 3.4.2 Update Path 第二章提到 PELT 會收集每個 time slot 的 contributing unit 進行運算，即為在 time slot 結束後都會進行一次，但實際上只針對正在執行任務進行 PELT 的計算，而其他未執行的任務只會在需要時才執行 PELT ### 3.4.3 Core Update Progres 更新 progress 的方式有兩種分別為 Update sum 以及 Update average，分別藉由 __update_load_sum() 以及 __update_load_avg() 來進行更新 > [accumulate_sum](https://elixir.bootlin.com/linux/latest/source/kernel/sched/pelt.c#L102) ### 3.5 CFS Variants Burst-Oriented Response Enhancer (BORE) 為 CFS 的修改版本，以互動性為考量犧牲了一些公平性，在 BORE cpu-bound 的任務會有比較高的 vruntime 藉由這樣的方式讓互動式的任務可以更容易被選擇，對於互動式得任務會有比較多的 timeslice 以及被喚醒的機會，對於 cpu-bound 的任務則會有比較低的權重，BORE 在 cpu-bound 、 batch 任務以及 I/O-bound interactive 任務之間取得公平性，讓用戶可以獲得更多更快的回應 sched_burst_penalty_scale 調節任務的懲罰的幅度，值越高代表懲罰越高 sched_burst_granularity 調節對 bursty task 的辨識，越高時間短的任務會容易被忽略 sched_burst_reduction 當任務被 dequeue 或讓出 cpu 時，藉由減少任務的 burst time 來降低 vruntime 的成長使任務更容易被選擇 ## CH4 Group scheduling and cgroups ### 4.1 Introduction 第二章的 CFS 介紹了將 cpu 平均分配給所有任務，但是對於若兩個執行緒是屬於同一個 process 或是使用者的情況較少討論以 50 個任務為例， userA 有 49 個任務而 userB 有 1 個任務而每個任務都獲得 cpu 平均分配的時間也就是各得到 $\frac{1}{50}$ 的 cpu 使用，這樣的話 userA 就會獲得 98％的 cpu 使用而 userB 只能獲得 2% 的 cpu 使用，這樣的分配只代表對於各 cpu 公平不代表對 process 或是使用者公平對於 CFS 而言需要考慮到將 cpu 使用分配給使用者的公平性，因此提出了 group scheduling 的概念，對於單一 group 而言可以是其他 group 的成員，也因這樣的概念讓整個 group 的結構形成一種階層，藉由這樣的方式將 cpu 時間分配給 group 中的成員對於 group scheduling 不保證 group 會在有限的時間運行，因為 cpu 只會分配給有在運行的使用者，若 group 中的任務沒有準備好開始執行，則其他 group 就會盡可能的競爭更多 cpu 使用當配置 CONFIG_FAIR_GROUP_SCHED 時使用 group > Above that the group scheduling feature does not guarantee that a group will last for a limited period. > 可能拿不到因為處於 passive ### 4.2 Group scheduling and CPU bandwidth ### 4.2.1 Group/Entity Hierarchy 在前面有提到排程器在對任務進行排程時是對 entity 進行，也不會因為是單一任務或是 group 有所差別，都被表示為 entity，所有可執行的任務在 CFS 排程器中會被放置在 runqueue 之中，而當使用 group scheduling 時就不是所有的 entity 都會被放置到 runqueue 之中，CFS 會建立 hierarchy ，如果任務是 group 的一部分則會被擺放到階層中 child 的部分，當使用 group 結構時只有當不為 child 的任務也就是沒有親代的任務(階層最上層)會被插入到 cpu 的 runqueue 之中 group 中的 entity 會有一個自己的 runqueue 其中裝著所有的 child entity 而這個 runqueue 就跟一般的 CFS runqueue 一樣，任務的 grouop 中可以有其他的任務 group 這些 group 中 runqueue 的 entity 會跟 parent group 的 cpu 相同 :::info > Every entity that corresponds to a group has its runqueue that contains all the child entities, and each of the runqueue behaves precisely like a nor- mal CFS runqueue. 對於 hierachy 彼此之間概念不清楚， group 中 entity 與 cpu 之間的關係，因為前面有提到同個 group 的 entity 會在不同的 cpu 上，想知道 group 的 entity 什麼狀況下會在不同的 cpu 上，這樣不會造成不同的 cpu 的 runqueue 混再一起嗎？想知道 my_q 是作爲子 runqueue 使用嗎，排程器會對 my_q 進行排程嗎，這樣的話系統不是會變得很複雜同一個 cpu 要同時維護很多個 runqueue，亦或是 my_q 的部分其用途為 cpu runqueue 的延伸？ > Task groups can be nested within other task groups, with each nested CFS runqueue having a separate sched entity enqueued into the parent group’s run-queue for the same CPU. ::: 任務的 group 可以嵌套在另外一個任務的 group 之中，在嵌套的 cfs runqueue 中會有一個 sched entity 代表整個整個任務的 group，最上層代表 group 的 sched entity，會稱為 representative entity 為整個 group 中作為 CFS 計算結果的代表將 scheduling slices 跟 vruntime 的結果放置在此 entity 中 :::info >These red entities, known as “representative” entities, allow CFS to compute scheduling slices and weighted vruntimes for the general case. 對於如何 CFS 如何維護 representative entity 的權重以及 vruntime 不明白 ::: entity hierarchy 中的 entity 都有自己的 virtual rumtime，排程器在選擇任務時會選擇當前最值得被執行的任務，選到的 entity 是代表任務則直接選擇進行排程，若選到的 entity 是代表 group 則會從這個 group entity 的 my_q (sub-runqueue)往下去尋找其他的任務，重複這個動作直到到達底端，並持續到找到值得被執行任務為止 :::info 找到最底層後回到最上層 runqueue 其方式是藉由 task group 的 parent 一直往上找嗎 ::: 計算 group entity 的 virtual runtime 時使用將 group 中全部 entity 的 vruntime 相加起來，會使得結果不準確因為每個任務都有不同的權重，取而代之應該要加總所有 child entity 的 wall time (實際運行時間) 並用 group entity 的 weight 相乘計算結果 :::info >Instead, it is calculated by taking the cumulative (non-weighted) wall-clock runtime of the children, and weighting it by the weight of the group entity. 想知道 group 的權重是如何決定的 ::: **multiprocessor** 在多處理器系統的 scheduling group 的任務可以在不同的 cpu 上面運行，也允許進行 migration，各個 cpu 會維護不同的 group 在自身運行的任務，對於同一個 group 中的任務也只能在內部 entity 被分派到的不同 cpu 中進行移轉 ### 4.2.2 CPU Limits 可以調整系統授予 group 的最大 cpu 頻寬也就是 group 可以獲得的最大時間，要開啟這個功能需要在編譯時期先設定 CONFIG_CFS_BANDWIDTH flag，並可以藉由 cgroup 進行 cfs_period_us 與 cfs_quota_us 的調整當 group 的配額減少到 0 時會被進行 throttled，這時會被從 runqueue 中移除，並防止馬上被加回到 runqueue 中，要直到配額恢復才能回到 runqueue 中 **Multiporcessor** 在多處理器系統中，各 cpu 需要彼此溝通來確定 group 沒有超過其配額，剩餘的配額需要以全域的方式進行追蹤，這樣會需要進行存取的限制，所以使用讓 group 自己儲存一份，並讓 cpu 存有其複製，來避免互斥 :::info > Instead, the group’s entity stores a portion of the quota. And each CPU maintains its copy of each entity to avoid any locking. 這邊是指 cpu 會存有 group 中在此 cpu 運行的 entity 的配額嗎，對於 cpu 保存 quota 的方式待釐清 ::: :::info > At each scheduler tick, the remaining quota of the current group is updated. If the local quota has expired, the system tries to get more quota from the global tracker. If there is still more quota available, it is transferred to the entity, and the group can be scheduled again 不清楚這邊的 local quota 以及 global quota 的存放方式 ::: ### 4.2.3 Implementation of group scheduling and CPU bandwidth control 系統中使用此結構來代表 task_group ```c struct task_group { #ifdef CONFIG_FAIR_GROUP_SCHED /* schedulable entities of this group on each CPU */ struct sched_entity **se; /* runqueue "owned" by this group on each CPU */ struct cfs_rq **cfs_rq; unsigned long shares; #endif // ... struct cfs_bandwidth cfs_bandwidth; }; ``` * sched_entity **se. 指向 entity 的 list，每一個節點代表一個 cpu 所對應的 entity，整個鏈結串列代表的就是一個 group * cfs_rq **cfs_rq. 為 entities 所屬的 runqueues * shares group 的權重可以用 cgroup 進行調整 * struct cfs_bandwidth. 存取 cpu 頻寬控制的資訊像是 quota, period 或是 throttled_time 以及 nr_throttled 等資訊 :::info 整個 group 中 entity 的權重皆是以 group 的權重計算嗎 ::: **scheduling** 此為與 group scheduling 相關的內容 ```c struct sched_entity { // ... #ifdef CONFIG_FAIR_GROUP_SCHED int depth; struct sched_entity *parent; /* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq; /* rq "owned" by this entity/group: */ struct cfs_rq *my_q; #endif }; ``` * depth. 為此 entity 被擺在階層的第幾層，若為 group 代表則為 0，子從為 1 開始 * sched_entity *parent. 指向階層中的親代 entity * cfs_rq *cfs_rq. 指向 runqueue 的指標 * cfs_rq *my_q. 在 group 結構中指向子的 runqueue ，即 subrunqueue ，若此 entity 為任務或是沒有子 entity 則為 empty :::info > cfs_rq *my_q: if this entity represents a group, this is the runqueue on which the 'entities' belonging to this group will run. If this entity has no children, or it is a task, this runqueue will be empty. > ::: group 中的 entities 應該要有專屬的 virtual runtime 來讓排程器挑選 **Updating virtual runtime** 若為 group 結構當 entity 的 virtual runtime 進行更新時其親代任務的 virtual runtime 也需要進行更新，系統中斷時會走訪階層結構，進行親代 entity 的 virtual runtime 更新時會根據 entity 的權重進行更新，所以每個 entity 更新的值會不同，而 group 的權重會根據所有子 entity '計算' :::info group 階層對 entity 的 virtual runtime 進行更新的方式，即對親代 entity 進行 virtual time 更新的作法以及 group 權重如何決定 ::: **Choosing the next task** 排程器會挑選最值得運行的任務，若當前 entity 的 my_q 為空即代表為一個任務可以直接挑選，若 my_q 為一個集合則代表是屬於 group 的結構則會對 my_q 進行走訪，並重複這個步驟 **CPU Bandwidth** 在 task_group 中的 cfs_bandwidth 結構中，包含了 global quota 的資訊，以及每個 cpu 都擁有自己一個獨有的 cfs_bandwidth 資訊 group entity 在被排程的 runqueue 上運行，而一個 group 中會有 entity 位於不同的 runqueue 上運行，每個 runqueue 會有自己的 cpu 配額，會根據系統的運行在每個 tick 時逐漸減少在 cfs_rq 中控制 cpu bandwidth 的成員有 * int runtime_enabled. 確認當前 runqueue 是否有頻寬限制 * runtime_remaining. cpu 目前分配給 cpu 的剩餘配額 * throttled. 確認 runqueue 是否為 throttle 狀態 local quota 的計算使用由 update_curr 呼叫的 __account_cfs_rq_runtime(), 在 [v6.9 kernel/sched/fair](https://elixir.bootlin.com/linux/v6.9.2/source/kernel/sched/fair.c) 多了一個 cfs_rq->throttled 的判斷當 group 的 cpu bandwidth 超過 local 的頻寬限制時，會試著從 global pool 中去取得更多的時間配額，但若沒有更多可以取得，就會重新進行排程 :::info > In case the group has exceeded its local bandwidth limit, it tries to get more time from the global pool. global pool 觀念釐清 ::: global 配額會由 task_group 中的 cpu_bandwidth 進行管理，但需要經由 lock 保護，防止多個 cpu 同時存取 :::info > The global quota is managed by the field task_group->cfs_bandwidth of the struct task_group. Note that the access to this struct is protected by a lock since multiple CPUs could try to access it at the same time. 這邊是指位於不同 cpu 上 group 中的 entity 成員會需要進行 global 配額的取得嗎 ::: **Throttling** 當 group 的配額用完之後，會重新進行排程而不是直接進行 throttle，當 entity 離開 runqueue ， put_prev_entity 會被呼叫更新統計資料，並判斷 cfs_rq->runtime_remaining 是否小於等於 0，最後任務會經由 throttle_cfs_rq 判斷是不是要進行 throttle **Refresh runtime** timer 會在每個週期結束時被觸發，此時sched_cfs_period_timer() 會被呼叫用來補充 task_group 的配額以及解除 runqueue 的 throttle 狀態 ### 4.3 Control Groups Control Groups (cgroups) 為 linux kernel 中的一個機制，允許用來建立以及管理一群任務，並提供對任務進行分組以及對 group 的參數進行管理，但不會對排程有任何影響，**cgroup 為任務的集合並包含與 group 相關的參數** cgroups 有兩個版本， cgroups-v1 以及 linux 4.5 之後推出的 cgroups-v2，兩種版本可以同時使用但是會有些許限制，在追蹤以及控制 cgroup 時會需要附加 subsystem 也稱作 resource controller，為功能模組，其作用為使用 cgroup 所提供的功能來控制任務資源 :::info 為什麼 cgroup-v2 出來後還要讓 v1 可以繼續使用，其共存意義何在？ ::: 舉例來說 cpu subsystem 可以控制 cpu 的使用，除此之外還有其他的 subsystem 可以使用，總共有 12 種不同的 subsystem 在 cgroup-v1 中 cgroups 為一樹狀結構，每個節點都代表一個 cgroup 有自己的屬性，並且 child group 會繼承親代的屬性，藉由這樣的階層結構可以方便的進行資源計算每個任務都包含在 cgroups 的階層結構中，但並不是每個 subsytem 都會被這個階層結構所使用，也就是說不同的階層結構可以使用不同種的 subsystem 進行資源的控管，所以一個 cgroups 中可能會有多個不同的階層結構 (樹狀結構) :::info 這邊的意思是代表說 cgroups 為 cgroup 所組成的樹狀結構，而這個樹狀結構需要包含所有的任務，並且可以搭配不同的 subsystem ， cgroups 中會包含多個階層結構？ ::: subsystem 並不會直接依附在 cgroups 上，而是會依附在 cgroups 中的階層結構 (樹狀結構) 上，且依附多個 subsystem 在階層結構上面，但是不能依附相同 subsystem 在不同的階層結構上上述提到的在 cgroups 中存在多個階層結構可以更加有彈性的管理資源但必須去追蹤 subsystem 以及在階層結構中的是處於哪個 cgroup 節點位置，在 cgroups-v1 中這樣複雜的使用在 cgroups-v2 有改善，使用較為統一的方式即 subsystem 皆依附在階層的最頂端也就是 root 的地方 #### 4.3.1 How to control cgroups cgroups 是以跟檔案管理一樣的方式使用虛擬檔案系統 (VFS) 來模擬 cgroups 的階層結構，VFS 可以讓 kernel 以及使用者互相溝通 cgroups 的階層結構被建立時，一開始時只會有 root cgroup 內部會包含所有的任務，此時若想在建立新的 cpgroup 就如同建立子目錄一般使用 mkdir 完成後即為一個新的 cgroup，若要對 cgroup 進行移除使用 rmdir 來達成，但是要確保階層下沒有任務以及其他的子 groups 才能進行移除在 cgroup 被建立時，cgroups 的 interface 檔案以及 subsystem 檔案會一起被建立，用來管理 cgroup，其中有一個 tasks 的檔案可以管理 cgroup 中的任務， tasks 檔案讓使用者可以藉由將 PID 的新增以及刪除到此檔案中達到讓 process 在 cgroup 中移動，也可以以寫入 PID 到 cgroup.proc 來達成，tasks 在 v2 中不存在 #### 4.3.2 implementation 對於 cgroups 的階層結構最多 12 個階層每一個階層對應一個 subsystem ，當一個 process 被建立其會跟親代放置在同一個 cgroup :::info > When a process is created, it is placed in the same cgroup as its parent. As a consequence, many cgroups across hierarchies have the same members. This characteristic can be used to simplify the linkage between tasks and cgroups. 觀念釐清 ::: * css_set struct. cgroup subsystem state set 的縮寫，用來辨識橫跨階層結構的特定集合，當任務只在一個階層中，當此任務從 group 中被移除時，新的 css_set 會被建立來辨識這個 cgrups，此時任務會指向這個新的 css_set，但此時還是會有其他任務使用舊的 css_set * cgrp_cset_link struct. 用來連結 cgroups 與 css_set * The cgroup_subsystem_state struct. 每個 css_sry 會有 cgroup_subsystem_state struct (css) 的 list 包含了 subsystem-cgroup 的配對資訊，當任務要存取特定階層中的 cgroup 資訊即可使用 css 中的指標找到 cgroup **The cgroup_subsys struct** 用此結構定義一個 subsystem，其中包含了 subsystem 的重要資訊以及功能 #### 4.3.3 Autogroup cgroup 需要由使用者手動設置，但是對於一般的桌面使用者而言是不太方便的，Autogroup 允許 groups 依造 session ID 自動建立，來改善與使用者的互動性 **session** session 用來辨認不同的 process groups ，每一個 session 使用 setsid 建立 session 若是用 fork 建立新的 process 時其會繼承親代 process 的 session，而前面提到的 autogroup 若被開啟時，當擁有一樣 session ID 的 process 或被配置到相同的 group 中 autogroup 功能的一大優點在於，當有 10 個運算密集型任務平行處理與一個需要較長 cpu 時間的影音任務時，若沒有 autogroup 則會導致 cpu 被分散在這 11 個任務之中而若有 autogroup 時則會會建立 group 將前面 10 個任務與後面的影音任務分開，各自讓他們得到 50% 的 cpu 使用來提昇個別體驗 #### 4.4 Core schedulingCore scheduling core scheduling 為 kernel 的功能允許 userspace 定義一群任務共享 cpu core，只有相同 group 的任務可以在同一個 core 上進行排程，並保證不同 group 的任務不會在同一個 core 上運行，也就是說會將信任的任務組織在一起方便尋找，當運行不信任的任務時，其附近的 cpu * 同樣運行在不信任的群組中的任務 * 如果沒有找到信任的任務則不強制運行任務 :::info Hyperthread HT 觀念釐清 Hardware thread，可以開啟硬體的執行緒若沒開啟 HT cpu 的核只能執行一個執行緒，其目的在於讓 pipeline 一次可以執行更多 thread ::: 此時 load balance 會觸發使得信任的任務會移轉到 sibling cpu 上運行，也就是當 cpu idle 會找可信任的任務將其移轉到自身運行 core scheduling 問題通常都與安全議題有關，也就是當惡意的任務被安排到有機密資料的 core 上時可能會偷取機密資料，以及 realtime 任務有效能上的考量會對 HT 進行 diasble 防止資源競爭，因此會避免任務被安排到相同的 core ## CH5 Customization of the CPU scheduler 前面的章節討論了排程器的設計，Linux 支援多種的的電腦架構，每一種架構都有自己評估效能的定義，並沒有一種理想的排程方式可能在某些系統是理想的狀況但是在其他系統又可能造成效能問題，Linux 排程器希望可以在不同的情況下都達到良好的表現，因此也顯示了使用者可以對排程器進行調整達到期望的結果 ### 5.1.1 System Calls Linux 提供了控制排程相關的系統呼叫，包含了策略， affinity, 優先權等等 **nice and Priority-Related System Calls** 每個任務都有對應的 sched_class 優先權，對於一般的排程策略 SCHED_OHTER 而言， nice() 可以用來調整任務的 nice 值，對於非特權的 process 只提供負值進行調整，越低的 nice 對應到越高的優先權，使用 setpriority() 跟 getpriority() 進行優先權調整以及獲得對於 group scheduling 而言，調整單一任務的 nice 只會影響到 group 之中的任務，要對 autograph 的 nice 值進行調整才會對 session 中的 processes 產生影響可以使用命令 nice 以及 renice 進行優先權的調整 :::info RLIMIT_NICE 用途 ::: **Scheduling Policy Related System Calls** 在 linux 中有不同的 sched_class 對應不同的優先權，會依造高優先權的類別尋找任務在往低優先權尋找直到沒有可運行的任務可以使用 sched_setscheduler() 與 sched_getscheduler() 這兩個系統呼叫來獲得以及設定任務的排程策略以及 real-time 優先權使用命令 chrt -p 改變 process 的排程策略 **Processor Affinity Related System Calls** 任務會有 cpu affinity 若任務在 cpu 移轉會有 cache miss 以及效能上的負擔，在效能評估時些許的雜訊會使得準確度更加正確 sched_setaffinity() 以及 sched_getaffinity() 可以設定任務的 affinity 讓任務待在指定的 cpu 使用命令 taskset -p 改變運行 process 的 cpu affinity ### 5.1.2 Customization with cgroups **cgroups-v1 basic operations** :::info > In Chapter 4, we discussed how cgroups associate some parameters to a grouping of tasks. By tuning the [scheduler parameters], specifically the parameters of the subsystems, cgroups controls how the scheduler schedules the group of tasks. 這裡指的是 cgroup 的參數嗎? ::: ![截圖 2024-06-03 晚上10.41.47](https://hackmd.io/_uploads/B1LV8LjVC.png) 圖中為 cgroup-v1 的基本結構，為一個 cgroup 的目錄中附著了多個 subsystem，可以將這些 subsystem 看作為多個子目錄即一個 /sys/fs/cgroup 這個目錄裡面，可以在建立多個 subsystem 的子目錄，而這些 subsystem 在 cgroup 包含 memory, blkio, cupset, cpuacct....等等有各別的功用先建立環境變數 MOUNT_POINT 為 cgroup 中的子目錄再將 subsystem 附著上去 ```shell # Mount cgroupfs $ mkdir -p $MOUNT_POINT $ mount -t cgroup -o cpu,cpuacct none $MOUNT_POINT ``` cgroup 為階層式目錄，管理者可以將任務組成 group 的形式放置到其他 group 之中 tree 命令需要另外安裝，可以使用 tree 查看目錄的階層結構 ```shell $ tree --charset=ascii ``` 藉由 echo $PID > $MOUNT_POINT/task 將任務寫入 ```shell $ echo $PID > $MOUNT_POINT/tasks ``` 使用下方命令創建任務模擬系統負載，任務 pid 以 [1] pid 呈現 ```shell $ cat /dev/urandom > /dev/null 2>&1 & [1] 12092 $ cat /dev/urandom > /dev/null 2>&1 & [2] 12163 ``` 建立兩個 group 的子目錄，並將模擬建立出來的任務加入到 group1 的 tasks 中 ```shell $ mkdir -p $MOUNT_POINT/{group1,group2} echo [task pid 1] > [mygroups]/group1/tasks echo [task pid 2] > [mygroups]/group2/tasks ``` 使用下方命令可以看到任務以 group 的形式呈現在 /procs 中 ```shell $ cat /proc/[task pid 1]/cgroup | grep cpu,cpuacct 9:cpu,cpuacct:/mygroups/group1 $ cat /proc/[task pid 2]/cgroup | grep cpu,cpuacct 9:cpu,cpuacct:/mygroups/group2 ``` 使用下方命令可以查看 cpu 使用率，建立了兩個 group 使得 group1 以及 group2 的使用率個使用了將近 50% 的使用率，使用 4 個 cpu 核心電腦時總計 400% 兩個 group 分別得到接近 200% 的使用 ```shell $ systemd-cgtop ``` 將 group2 的 cpu.shares 寫入 512 會使得其 cpu 使用率減半 ``` $ echo 512 > [mygroups]/group2/cpu.shares ``` 也就是 mygroups 的 cpu 使用率為 94 而 group1 以及 group2 的 cpu 使用率從原本的兩個 group2 平分這 94 %變成 group1 為 62.8% 以及 group2 為 31.2% 以我的電腦而言總共 399.6 % cpu 使用率而 group1 拿到 265.% 與 group2 拿到 135.4% 因此計算方式為 $100\%(\frac{512}{1024+512})$ 大約為 $33%$ 所以 group2 可以拿到約 $33%$ 的 cpu 使用而 group1 可以拿到 $66%$ cpu.shares 不會限制各 groups 的頻寬，每一個任務都會盡可能的從 parent group 獲得更多的 cpu 時間， **cgroups-v2 basic operations** 在 cgroup-v2 的版本中只有單一層的階層結構，包含最上層的 cgroup 控制介面，包含了 cgroup.controllers, cgroup.freeze 等等，這些介面檔案為所有 control group 所共用使用命令查看 ```shell $ cat /sys/fs/cgroup/cgroup.controllers cpuset cpu io memory hugetlb pids rdma misc $ cat /sys/fs/cgroup/cgroup.subtree_control memory pids ``` 與 cgroup-v1 相似在 cgroup-v2 中子 group 繼承了所有親代 cgroup 的屬性，在 cgroup.procs 中包含了在 cgroup 中所有 processes 的 pid，在第一次 mount cgroup 檔案系統時 cgorup.procs 中會包含系統中所有 process 的 pid 在 cgroup.controller 中會顯示所有 cgroup 使用的 susystem ， cgroup.subtree_control 會顯示子 group 中所使用的 subsystem 對於 cgroup-v2 三個核心檔案包含 cgroup.procs, cgroup.controllers, cgroup.subtree control 在每一次建立新的 cgroups 時都會被都會被建立，使用下方命令建立 cgroup-v2 ```shell $ mount -t cgroup2 none $MOUNT_POINT ``` 可以看到在一開始時在 group 中建立一個 child 的子目錄，並查看 group 中的 controllers，此時查看 group 的 cgroup.subtree_control 為空，查看子目錄 child 的 cgroup.controllers 為空，要先加入 controllers 到 group 中的 cgroup.subtree_control 此時 child 的 controllers 中才會存在 cpuset cpu **此處要特別注意在進行下方命令時若親代目錄中的 cgroup.subtree_control 中沒有要寫入的控制器則會出現錯誤 echo: write error: No such file or directory 因此要確保親代目錄中 cgroup.subtree_control 存在 cpu, cpuset** ```shell # mkdir -p $MOUNT_POINT/mygroup/child # cat $MOUNT_POINT/mygroup/cgroup.controllers cpuset cpu io memory hugetlb pids misc # cat $MOUNT_POINT/mygroup/cgroup.subtree_control # cat $MOUNT_POINT/mygroup/child/cgroup.controllers # echo "+cpuset +cpu" >> $MOUNT_POINT/mygroup/cgroup.subtree_control # cat $MOUNT_POINT/mygroup/cgroup.subtree_control cpuset cpu #cat $MOUNT_POINT/mygroup/child/cgroup.controllers cpuset cpu ``` 在 cgroup-v2 中使用 cpu.weight 與 cgroup-v1 中的 cpu.shares 不同，但使用方式相似進行任務模擬，先創建兩個任務再將其寫入到 group1, group2 之中，並調整 group1 的 cpu.weight (預設 cpu.weight 中為 100)，此時 group1 會得到 $\frac{50}{100+50}$ 的 cpu 使用 ```shell # mkdir -p $MOUNT_POINT/mygroup/{group1,group2} # cat /dev/urandom > /dev/null 2>&1 & [1] 7337 # cat /dev/urandom > /dev/null 2>&1 & [2] 7343 # echo 7337 > $MOUNT_POINT/group1/cgroup.procs # echo 7343 > $MOUNT_POINT/group2/cgroup.procs # echo 50 > $MOUNT_POINT/group1/cpu.weight # systemd-cgtop ``` **cgroups and CPU Scheduler** 排程器是一個分配資源的模組，模擬任務在真實硬體上的執行，cgroup 是 kernel 的機制，允許 group scheduler 以 task group 或是 task 為單位分配公平的 cpu 時間給任務，並提供介面讓使用者可以控制 group sheduling **CPU Affinity** Linux cpu 排程器可以將任務綁定在單個或多個特定的處理器上，此為 cpu affinity 又稱 cpu pining 下方進行 cpu affinity 的例子，將任務綁定在特定的 cpu 先模擬建立一個任務，此時這個任務不屬於任何的 group 可以使用命令 taskset 查看任務可移轉的 cpu，以group1 為範例將其 cpuset.cpus 寫入 0，並將任務 7814 寫入到 group1 時可以發現任務 7814 被綁定在 cpu 0 ```shell # cat /dev/urandom > /dev/null 2>&1 & [1] 7814 # taskset -pc $PID pid 7814's current affinity list: 0-3 # echo "0" > $MOUNT_POINT/mygroup/group1/cpuset.cpus # echo 7814 >> $MOUNT_POINT/mygroup/group1/cgroup.procs # taskset -pc $PID pid 7814's current affinity list: 0 ``` 此時使用下方命令查看任務狀況，可以看到任務在 group1 之中使用了將近 10% 的 cpu 使用，在使用 top -1 會發現因為目前模擬任務位於 cpu 0，排程器並沒有將任務轉移到 idle cpu 上，所以除了 cpu0 之外其他 cpu 的被佔用比例皆趨近於 0 ```shell $ systemd-cgtop $ top -1 ``` **CPU Bandwidth** 如果有其他 cpu 處於 idle 狀態，排程器會將剩餘的資源分配給任務或 group ，此時就算是有設定 cpu.weight (v1 cpu.shares)，任務依然可以使用超過預期的時間，而 cgroup 允許使用者設定一個 upper bound ，來限制 cpu 頻寬的使用這樣的限制對於 pay-per-user 系統十分有用，可以藉由 cgroup 對客戶的資源設限，避免超過其所付費的使用量對 cpu.max 進行調整來進行 cpu 頻寬限制，cpu.max 有兩個值組成，前者顯示 max 為 cfs_quota_us，代表不會對 cpu 頻寬進行限制，排程器會盡可能分配資源給 group ，後者 100000 為 cfs_period_us， ```shell # cat $MOUNT_POINT/mygroup/group1/cpu.max max 100000 ``` 藉由改寫第一個值 cfs_quota_us 來進行頻寬限制 ```shell # echo 50000 100000 > $MOUNT_POINT/mygroup/group1/cpu.max ``` **cpu bandwidth and cpu shares** cpu.wieght 以及 cpu.max 會一起影響排程器分配 cpu 時間，若兩個任務皆在同一個 core 上運行，並且 cfs_period_us 皆為預設的 100000 若兩個任務的 quota 皆設定為超過 period 的時間則會依造 cpu.weight 來決定兩者可以獲得的時間若兩個任務設定的 quota 時間少於 period 則會依造在 cpu.max 中設定的 upper bound 來決定若兩者的 quota 不同，但其中一個任務有較大的 quota，即使兩者的cpu.weight 皆為相同，但設定較大 quota 的任務仍然會獲得較多的時間 #### 5.2.1 sysctl utilities :::warning p.166 書中範例 5.21 sysctl utilities 所使用 kernel.sched_min_granularity_ns 在 linux **v5.13** 中被移至 /sys/kernel/debug/sched，對應 commit [8a99b68](https://github.com/torvalds/linux/commit/8a99b6833c884fa0e7919030d93fecedc69fc625#diff-0cde65256909335643b2a29a3813834c19d22b2c83436f6891a14a50d3532748)，因此書中範例無法使用 **/sys/kernel/debug/sched** 包含， debug, latency_warn_ms, ***nr_migrate***, verbose, features, latency_warn_once, numa_balancing, ***wakeup_granularity_ns***, idle_min_granularity_ns, ***migration_cost_ns***, preempt, ***latency_ns***, ***min_granularity_ns***, ***tunable_scaling*** > TODO: 提交一項 patch，用 footnote 的形式，說明目錄的變更和 Linux 核心開發者的考量。善用 `\commit`，例如 `See commit \commit 8a99b6833c884fa0e7919030d93fecedc69fc625` ::: #### 5.2.2 Basic Scheduling Parameters **Fair Scheduling Class** **sched_tunable_scaling** 為決定排程器是否可調整 sched_latency_ns 以配合 core 數量，當值為 0 時為不調整，為 1 時以 $1+ilog(n\_cpus)$ 進行調整，當為 2 時為線性調整，預設為 1 **sched_latency_ns** 每個 cpu-bound 任務至少都執行一次的基本時間，在 cfs 中任務的時間片段為變動的 **sched_min_granularity_ns** cpu-bound 任務執行一次的最短時間，其確保每個任務在被 preempted 之前可以執行的最短時間當任務太多時會導致大量的任務沒辦法在一次的 period 執行完，因此 period 的時間需要被加長進行對應調整公式為: $nr\_running=$ number of running tasks $sched\_nr\_latency=\frac{sched\_latency\_ns}{sched\_min\_granularity\_ns}$ 當任務太多時 $nr\_running > sched\_nr\_latency$，對 period 進行調整 $period=nr\_running*sched\_min\_granularity\_ns$ 否則 $period = sched\_latency\_nr$ **sched_wakeup_granularity_ns** 此參數延遲了當前任務在喚醒其他任務之後被 preempt 的時間，CFS 排程器會挑選最小 vruntime 的任務，此參數制定一個 vruntime 範圍，排程器忽略這個範圍內的 vruntime，使 vruntime 非常接近的任務不會 preempt 當前任務直到超過 sched_wakeup_granularity_ns，其值越大 preempt 的可能性越低 **sched_child_run_first** 控制親代任務還是子任務先運行，預設 0 即為親代任務先嘗試運行 **sched_nr_migrate** 控制一次可以移轉的 cpu 量，預設為 32 即一次移轉 32 個任務 **sched_migration_cost** 任務在 cpu 中移轉的成本，幫助排程器進行任務移轉的決策，會設置一個任務在 cpu 上運行到被移轉的下限時間，此值增加時會減少任務移轉的機率，而在 NUMA 中存取 local 的記憶體遠比存取其他 cpu 的記憶體來得快速所以在 NUMA 上進行移轉要更加小心 **sched_cfs_bandwidth_slice_us** 此參數控制了 quota 從 global pool 被消耗的配額多寡 ## TODO: 針對書本內容提出貢獻 > 用電子郵件提交 LaTeX 修改的 patch，要有完整的 git commit 已收錄: * commit 43817dd83a793a2c963cc3c3d60b03a40f85cb83 * commit 94c631d753a9be7d15871f8c3580956c4a7e852a * commit 01b42b105ed9571a50e3703bd5d3db2dab376ac6 * commit 8447f69f56c3bf7e7f8624589b2b132b65919798 ## TODO: EEVDF 的研究和量化分析 > 善用 schbench 和 Schedgraph ### 開發環境 ```shell $ uname -mrs Linux 6.9.3 x86_64 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 43 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 16 On-line CPU(s) list: 0-15 Vendor ID: AuthenticAMD Model name: AMD Ryzen 7 3700X 8-Core Processor CPU family: 23 Model: 113 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 Stepping: 0 Frequency boost: enabled CPU max MHz: 4426.1709 CPU min MHz: 2200.0000 BogoMIPS: 7200.15 Caches (sum of all): L1d: 256 KiB (8 instances) L1i: 256 KiB (8 instances) L2: 4 MiB (8 instances) L3: 32 MiB (2 instances) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-15 ``` ### Assumption 對於每個任務而言制定一個 weight 來決定其可分配到的資源，即為所有任務權重分之當前任務的權重 $f_t(t)=\frac{w_i}{\sum_{\in\\A(\tau)}{w_j}}$ 並制定一個在時間區間內 [t, △t] 預期可以得到的時間，以積分代表意義為在理想狀態下的時間可將其切分至趨近於無限小的 $S_i(t_0,t_1)=\int_{t_0}^{t_i}f_t(t)d\tau$ 也因離散時間得限制導致任務沒辦法總是將預期拿到的時間全部用完，因此制定 $s_i({t^i}_0,t)$ 作為任務實際拿到的時間，公式 $lag_i(t)$ 來表示預期與實際的差值，也可作為任務 throughput 的準確度以及系統的準確度 $lag_i(t)=S_i({t^i}_0,t)-s_i({t^i}_0,t)$ ### EEVDF Algo 在演算法中假設每個任務皆會進行 request，request 達成時可能會重新發請求或是改變狀態為 passive 而對於任務 request 有高度彈性並沒有限制請求大小，並對 period 制定為固定的 interval 將前面公式帶入得到下方公式一樣作為任務應該得到的時間 $S_i(t_0,t_1)=\int_{t_0}^{t_1}\frac{w_i}{\sum_{\in\\A(\tau)}{w_j}}d\tau$ 並制定 virtual time ，這邊 EEVDF 的 virtual time 跟 CFS 的 virtual 不同的在於 CFS 是將 vurtual time 作為權重化的任務執行時間，每個任務都會有一個獨有的 vruntime，作為其運行時間而在論文 model 中 EEVDF 是將 virtual runtime 作為共用的時間線，也就是除了現實時間外另外還維持了一個系統中的時間當任務越多成長越緩慢，也代表由所有活動中任務所共用 $V(t)=\int_{0}^{t}\frac{1}{\sum_{j\in\\A(\tau)}w_j}d\tau.$ 並對 $S_i(t_0,t_1)=\int_{t_0}^{t_i}\frac{w_i}{\sum_{\in\\A(\tau)}{w_j}}d\tau$ 進行展開並將上面虛擬時間公式帶入得到 $S_i(t_0,t_1)=w_i(V(t_0)-V(t_1))$ 在 EEVDF 中使用 `eligible time` e 以及 `deadline` d 作為判定任務是否有資格可以運行任務為 eligible 的條件為 $S_i(t^i_0,e)=s_i(t^i_0,t)$ 即到 eligible time 的應得時間等於任務變成 active 的時間到其 request 的時間 t 的實際獲得時間可以藉由前面的 lag 值來做判斷當 lag 值為負時代表任務實際的到時間超過了應得的時間就需要等待，而當其為正代表實際拿到的時間太少可以有馬上取得資源的資格將前面的 $S_i(t^i_0,e)=s_i(t^i_0,t)$ 由 $w_i(V(t^i_0)-V(e))$ 帶入移項得到 eligible time $V(e)=V(t^i_0)+\frac{s_i(t^i_0,t)}{w_i}$ deadline 即為 eligble 到 dealine 的時間 $S_i(e,d)=r$ 得到 $V(d)=V(e)+\frac{r}{w_i}$ **所以最後 EEVDF 決定任務是否可以得到資源的條件即為當其為 eligible 並且為 deadline 最早的任務** 作者有提到實際上不用得到一個真的 e 以及 d，因 e 沒辦法實際得到當 e 超過 t 很多的情況下沒辦法得到 e ![截圖 2024-06-27 晚上11.43.24](https://hackmd.io/_uploads/B1VTObo8R.png) 並舉了例子可以看到所有任務共享一虛擬時間，並且最下方有一個真實時間，()中代表 $(V_e,V_d)$ eligible time 以及 dealine 皆為計算得到以兩個任務權重皆為 2，任務 1 的請求為 2 、任務 2 的請求為 1 時， c1 在真實時間為 0 時變成 active, c2 在１變成 active 此時計算 $V_e$ 藉由 $Ve$ 公式可以得到任務 1 的 $Ve =V(t^i_0)$ 因為這時候任務 1 還沒實際運行，而 $V_d=0+2/2$，此時 $virtual time = Ve$ 因此 eligible 有得到資源的機會，也因為只有任務 1 其得到資源，其 virtual time 的計算為 $V(1)=\int_{0}^{1}\frac{1}{w_1}d{\tau}=0.5$ 到真實時間 1 時任務 2 變成 active 加入到競爭中，此時任務 1 的因為 period 到了被 preempt 因此現在為任務 1 以及任務 2 皆有請求，此時兩者的 $V_d$ 相同由任務 2 運行，此時 $V(t)=0.5 + (\frac{1}{(w_1+w_2)}=0.25)$ 為 0.75 在 $virtual\ \ time = 0.75$，此時一樣為兩個請求任務 1 以及任務 2 分別為 (0,1) 以及 (1,1.5) 這時任務 2 的 eligible time 大於 virtual time 0.75 由任務 1 取得資源 ### Fairness in Dynamic Systems 任務在系統中的公平性問題，在理想情況下每個任務都可以得到 lag 值為 0 的時間，也就是應得的與實際得到的一樣，但現實上會有一些狀況導致沒辦法總是讓 lag 值為 0，論文中討論了下面內容 1. 當任務是在 lag 不等於 0 的狀況下離開、加入或是改變權重對其他任務的影響 2. 當 lag 不等於 0 的任務離開競爭在他重新回到競爭時他的 lag 值應該為多少以第一種情況而言當執行中的任務在離開時其 lag 值為負也就是拿到了比預期還要更多的時間，這時候會對其他也同樣運行的任務造成損失解決這樣的情形，方法為將這個任務所獲得的作為其他任務的損失平均分配下去，但是如何將損失分配下去並取得公平，提出以動態操作的方式，將損失依比例分配的方均攤給所有活動中的任務，而這個方法可以藉由更新 virtue runtime 的方式來達成 (在 EEVDF 中 virtual runtime 為被所有活動中任務共同使用) ![Screenshot from 2024-06-18 21-00-24](https://hackmd.io/_uploads/r1j-HbkUC.png) 三個任務在 $t_0$ 變成 active 且為 lag 值為 0 ，在時間 t 時任務 3 離開了競爭，這樣的情況會對任務 1 以及任務 2　造成影響，考慮到在時間 $[t_0, t)$ 這段之間，仍然為 3 個任務因此虛擬時間的計算為 $\frac{1}{w_1+w_2+w_3}$，將 $S_i(t_0,t_1)=w_i(V(t_2)-V(t_1))$ 帶入 $lag$ 的公式中得到 $lag_i(t)=w_i\frac{t-t_0}{w_1+w_2+w_3}-s_i(t_0,t)$ 也就是任務的應得時間與實際獲得時間的差，來計算每個任務的 lag 值下面討論任務 3 離開之後任務 1 以及任務 2 ，在 [t_0,t) 這段時間中任務 1, 2 會獲得的時間為 $t-t_0-s_3(t_0,t)$ 並設 $t^+$ 為任務 3 離開的時間，忽略掉 $t^+->t$ 這段時間差直覺上會想到即將 $t-t_0-s_3(t_0,t)$ 依照任務的權重分散給剩餘的兩個任務，任務 1 以及任務 2 的應得時間為 $S_i(t_0,t^+)= (t-t_0-s_3(t_0,t))\frac{w_i}{w_1+w_2}$ 在 $lag_3(t)$ != 0 的情況下任務 1 以及任務 2 的應得時間就會發生改變，因為當任務 3 離開時剩餘的任務需要分散掉任務 3 造成的影響也就是任務 3 多用的時間或是少拿的時間，在將上面 $lag_i(t)$ 帶入到上面的 $S_i(t_0,t)$ 中得到 $S_i(t_0, t^+) = w_i(V(t)-V(t_0))+w_i\frac{lag_3(t)}{w_1+w_2}$ 並將 $S_i(t_0,t^+)=w_i(V(t^+)-V(t_0))$ 帶入上面公式移項得到 $V(t^+)=V(t)+\frac{lag(t)}{w_1+w_2}$ 也因為 $t^+$ 與 $t$ 的幾近相等所以 $t^+$ 可以用 $t$ 代替在將上述公式一般化後得在任務離開、加入以及改變權重時對於虛擬時間的更新公式得到下列三個分別為離開 $V(t)=V(t)+\frac{lag_i(t)}{\sum_{\in\\A(t^+)}{w_i}}$ 加入 $V(t)=V(t)-\frac{lag_i(t)}{\sum_{\in\\A(t^+)}{w_i}}$ 改變權重用任務離開後以及離開後馬上加入來表示 $V(t)=V(t)+\frac{lag_j(t)}{(\sum_{\in\\A(t^+)}{w_i})-w_j}-\frac{lag_j(t)}{(\sum_{\in\\A(t^+)}{w_i})-w_i+{w'}_j}$ 對於第二種情況來說並沒有簡單的方式可以解決，若不補償會造成損失一直累積，而補償了反倒可能對其他任務造成影響作者提了一個例子在於目前有兩個任務分別為任務 1 以及任務 2，當任務 2 離開時為 lag 大於 0 也就是應得時間大於實際獲得時間這時任務 2 又加入回競爭此時任務 3 進來，那這時如果補償任務 2 的損失這樣反倒是對任務 3 造成了影響，這樣也造成了不公平的情況發生 ### Algorithm Implementation 作者在這邊提出了三個 EEVDF 的策略策略 1: 任務可以在任何狀況下離開、加入，任務在重新加入競爭時會藉由 lag 值來判斷是否要受到處罰或是補償，策略 1 會記住任務的 lag 值然後在重新加入時 lag 會跟原本的一樣並且使用上面提到公式 1, 2 ,3 來進行虛擬時間的更新策略 2: 第二種方式則不會紀錄當任務離開競爭時的 lag 值，當任務重新加入競爭時其 lag 值為 0 策略 3: 當任務的 lag 值等於 0 時才允許離開、加入或是改變其權重，在這樣的情況下就不用動態改變虛擬時間，但相對困難的在於如何確保任務的 lag 值在狀態改變時真的為 0 ，這樣的話就需要在確切的時間更新虛擬時間 ### Addressing the latency problem 在 EEVDF 中引入了 latency-nice 解決了 CFS 中 latency 問題針對相同 nice 值的兩個任務而言若任務具有較低的 latency-nice 與較高 latency-nice 值的任務相比會獲得相同的 cpu 使用為較多但是較短的 timeslice #### tunables [sched/base_sclice_ns](https://lore.kernel.org/lkml/20230824080342.543396-1-sshegde@linux.vnet.ibm.com/T/) 取代 sched/min_granularity_ns 也就是 paper 中的 quantum 使用 sched_attr.sched_runtime 作為 paper 中的 request 任務請求的時間也就是 r 在 cfs 已經有追蹤 virtaul time 的功能所以在 EEVDF 中不用作太多的修改，並使用增強的紅黑數來儲存 eligible 以及 deadline，在此紅黑樹中使用 virtual deadline 對節點進行排序 ### Jitterdebugger **Jitterdebugger 的原理在於會在每個 cpu 上面設置一個 thread 藉由這個 thread 進行 timer 的設置，計算 timer 到期到重新設置的這段期間** 在書中提到在 CFS 有著延遲上面的議題，對於需要較快回應的任務會因為公平性的關係忽略掉即時響應的部份，使用 jitterdebugger 針對排程器延遲比較 CFS 以及 EEVDF 的差異下方為 jitterdebugger 會顯示結果並關注 scheduling latency (wakeup latency) 的部份 T: Thread id (PID) A: CPU affinity C: Number of measurement cycles Min: Smallest wake up latency observed Max: Biggest wake up latency observed Avg: Arithmetic average of all observed wake up latencies. 使用命令搭配建立 80 個 cpu-bound 任務分別以 EEVDF 以及 CFS 排程器運行 ```shell $ sudo ./jitterdebugger -D 10m -v -c 'stress-ng -c 80' -o [filename] ``` ### CFS latency ``` affinity: 0-15 = 16 [0xFFFF] start background workload: stress-ng -c 80 stress-ng: info: [2780] defaulting to a 86400 second (1 day, 0.00 secs) run per stressor stress-ng: info: [2780] dispatching hogs: 80 cpu T: 0 ( 2781) A: 0 C: 599981 Min: 3 Avg: 4.50 Max: 199 T: 1 ( 2782) A: 1 C: 599981 Min: 2 Avg: 3.95 Max: 185 T: 2 ( 2783) A: 2 C: 599978 Min: 2 Avg: 4.05 Max: 32 T: 3 ( 2784) A: 3 C: 599975 Min: 3 Avg: 4.00 Max: 17 T: 4 ( 2785) A: 4 C: 599972 Min: 3 Avg: 4.16 Max: 187 T: 5 ( 2786) A: 5 C: 599969 Min: 3 Avg: 4.06 Max: 252 T: 6 ( 2794) A: 6 C: 599966 Min: 3 Avg: 4.14 Max: 27 T: 7 ( 2807) A: 7 C: 599963 Min: 3 Avg: 4.33 Max: 13 T: 8 ( 2821) A: 8 C: 599960 Min: 3 Avg: 4.36 Max: 198 T: 9 ( 2835) A: 9 C: 599957 Min: 3 Avg: 4.11 Max: 16 T:10 ( 2845) A:10 C: 599948 Min: 3 Avg: 4.26 Max: 12 T:11 ( 2860) A:11 C: 599937 Min: 3 Avg: 4.26 Max: 21 T:12 ( 2873) A:12 C: 599917 Min: 3 Avg: 4.60 Max: 1134 T:13 ( 2874) A:13 C: 599899 Min: 3 Avg: 4.03 Max: 13 T:14 ( 2875) A:14 C: 599880 Min: 3 Avg: 4.38 Max: 11 T:15 ( 2876) A:15 C: 599857 Min: 3 Avg: 4.28 Max: 11 ``` ![CFS](https://hackmd.io/_uploads/rJMIS-sS0.png) 可以看到藉由各個 cpu 的延遲狀態，會發現在 cfs 進行排程時會傾向選擇已經使用過得 cpu 再次進行使用，某些尚未使用的 cpu 則會呈現使用率較低的狀況，並在圖中可以看到 cpu12 最常被使用其最高的延遲狀況高達 1134 ### EEVDF latency ``` start background workload: stress-ng -c 80 stress-ng: info: [2795] defaulting to a 86400 second (1 day, 0.00 secs) run per stressor stress-ng: info: [2795] dispatching hogs: 80 cpu T: 0 ( 2796) A: 0 C: 599936 Min: 3 Avg: 4.38 Max: 16 T: 1 ( 2797) A: 1 C: 599933 Min: 3 Avg: 4.36 Max: 203 T: 2 ( 2798) A: 2 C: 599930 Min: 3 Avg: 4.27 Max: 15 T: 3 ( 2799) A: 3 C: 599926 Min: 3 Avg: 4.50 Max: 20 T: 4 ( 2805) A: 4 C: 599923 Min: 3 Avg: 4.43 Max: 209 T: 5 ( 2821) A: 5 C: 599920 Min: 3 Avg: 4.17 Max: 14 T: 6 ( 2824) A: 6 C: 599916 Min: 3 Avg: 4.41 Max: 10 T: 7 ( 2825) A: 7 C: 599913 Min: 3 Avg: 4.42 Max: 244 T: 8 ( 2835) A: 8 C: 599909 Min: 3 Avg: 4.41 Max: 194 T: 9 ( 2848) A: 9 C: 599901 Min: 3 Avg: 4.13 Max: 190 T:10 ( 2864) A:10 C: 599889 Min: 3 Avg: 4.43 Max: 185 T:11 ( 2874) A:11 C: 599870 Min: 3 Avg: 4.07 Max: 186 T:12 ( 2883) A:12 C: 599852 Min: 3 Avg: 4.68 Max: 743 T:13 ( 2889) A:13 C: 599823 Min: 3 Avg: 4.25 Max: 188 T:14 ( 2890) A:14 C: 599797 Min: 3 Avg: 4.04 Max: 12 T:15 ( 2891) A:15 C: 599766 Min: 3 Avg: 4.34 Max: 132 ``` ![eevdf](https://hackmd.io/_uploads/r1QsSZsSA.jpg) EEVDF 在 cpu 使用上則會較為平均的把任務負載分配到各個 cpu 上，可以看到在途中有較多的 cpu 在最大延遲上是超過 100 的可見 EEVDF 在分配任務時將負載更為廣泛的分配到了不同的 cpu 上做運行，但可以發現在 cpu12 時其延遲高達了 743，所以仍會傾向使用特定 cpu ## Schbench 在 schbench 中主要由 messaging thread 進行工作分配並等待結果，由 worker thread 執行請求，數量的設定分別為 -m [num] 以及 -t [num] 其中 schbench 主要紀錄了三個指標包含: * wakeup latency: 由 messaging thread 分派任務給 worker 的時間到 worker 開始工作的這段時間的差也就是 scheduler latency * Request latency: 完成請求的時間 * Requests per second: threads 可以完成多少請求 **schbench 判斷 wakeup latency 的方式是藉由 worker 被分派任務到真正開始工作這段閒置的時間來判斷** 使用 schbench 進行不同應用規模下 (scalability) 的分析，使用 2 個 message thread 分別搭配 2 個以及 40 個 woker thread 使用命令 -F -n -r 為預設值分別為 cache_footprint, operations, runtime ```shell $ ./schbench -F 256 -n 5 -m 2 -t [2 ,40] -r 30 ``` ### EEVDF Max loading all the CPUs 使用 2 個 message thread 以即 2 個 worker thread 進行測試，運行時間為預設 30 秒 ``` Wakeup Latencies percentiles (usec) runtime 30 (s) (35592 total samples) 50.0th: 4 (12462 samples) 90.0th: 6 (12873 samples) * 99.0th: 7 (767 samples) 99.9th: 14 (142 samples) min=1, max=33 Request Latencies percentiles (usec) runtime 30 (s) (35596 total samples) 50.0th: 3348 (14806 samples) 90.0th: 3372 (10140 samples) * 99.0th: 3420 (2753 samples) 99.9th: 6424 (280 samples) min=3188, max=6960 RPS percentiles (requests) runtime 30 (s) (31 total samples) 20.0th: 1182 (10 samples) * 50.0th: 1186 (13 samples) 90.0th: 1194 (7 samples) min=1175, max=1196 average rps: 1186.53 ``` 使用 2 個 message thread 以即 40 個 worker thread 進行測試，運行時間為預設 30 秒 ``` Wakeup Latencies percentiles (usec) runtime 30 (s) (24342 total samples) 50.0th: 10576 (7278 samples) 90.0th: 25632 (9740 samples) * 99.0th: 32736 (2198 samples) 99.9th: 40000 (206 samples) min=1, max=47976 Request Latencies percentiles (usec) runtime 30 (s) (24346 total samples) 50.0th: 60224 (7298 samples) 90.0th: 181504 (9743 samples) * 99.0th: 385536 (2185 samples) 99.9th: 599040 (218 samples) min=5054, max=949763 RPS percentiles (requests) runtime 30 (s) (31 total samples) 20.0th: 799 (7 samples) * 50.0th: 807 (9 samples) 90.0th: 821 (12 samples) min=765, max=834 average rps: 811.53 ``` ### CFS Max loading all the CPUs 使用 2 個 message thread 以即 2 個 worker thread 進行測試，運行時間為預設 30 秒 ``` Wakeup Latencies percentiles (usec) runtime 30 (s) (35937 total samples) 50.0th: 4 (12110 samples) 90.0th: 6 (13233 samples) * 99.0th: 8 (1132 samples) 99.9th: 9 (62 samples) min=1, max=31 Request Latencies percentiles (usec) runtime 30 (s) (35942 total samples) 50.0th: 3316 (10009 samples) 90.0th: 3348 (11397 samples) * 99.0th: 3380 (2380 samples) 99.9th: 4984 (305 samples) min=3190, max=6494 RPS percentiles (requests) runtime 30 (s) (31 total samples) 20.0th: 1194 (7 samples) * 50.0th: 1198 (14 samples) 90.0th: 1202 (10 samples) min=1173, max=1203 average rps: 1198.07 ``` 使用 2 個 message thread 以即 40 個 worker thread 進行測試，運行時間為預設 30 秒 ``` Wakeup Latencies percentiles (usec) runtime 30 (s) (28092 total samples) 50.0th: 11792 (8426 samples) 90.0th: 28640 (11228 samples) * 99.0th: 37440 (2510 samples) 99.9th: 48064 (248 samples) min=1, max=69849 Request Latencies percentiles (usec) runtime 30 (s) (28098 total samples) 50.0th: 54080 (8430 samples) 90.0th: 155392 (11247 samples) * 99.0th: 318976 (2522 samples) 99.9th: 515584 (251 samples) min=4949, max=750644 RPS percentiles (requests) runtime 30 (s) (31 total samples) 20.0th: 915 (7 samples) * 50.0th: 939 (9 samples) 90.0th: 961 (12 samples) min=824, max=975 average rps: 936.60 ``` #### wakeup latency 在觀察 schbench 的結果後發現，在 worker thread 數量為 2 時， EEVDF 與 CFS 在收集到的 wakeup latency 中大部分的情況下都沒有顯著的差異接近 99% 都是小於等於 7 、 8，兩者的最大 wakeup latency 也非常接近分別為 33 以及 31 當 worker thread 的數量上升到 40 時可以發現在 EEVDF 中有 99% 的任務其 wakeup latency 是在小於等於 32736，99.9% 是小於等於 40000 對比於 CFS 中 99% 的 wakeup latency 小於等於 37440 ，99.9% 低於 48064 可以發現相較於 EEVDF 其 wakeup latency 明顯較高對於兩者最高的 wakeup latency 發現當任務數量較多時 EEVDF 以及 CFS 分別為 47976 以及 69849，也可以看出兩者在較高負載環境下的差異 ## Schedgraph 參照 [linhoward0522](https://hackmd.io/@sysprog/BJh9FdlS2) 同學進行 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 的安裝，其特點在可以針對<s>核心</s> 處理器核數量較多的裝置進行追蹤 :::danger 注意用語： * (OS) kernel: 核心 * (processor) core: 核本處應採後者。 > 收到會注意用語 ::: 目前 schedgraph 在先前有進行調整並且有對 makefile 進行修改，直接進行編譯時會出現下方錯誤 ```ocaml ocamlc -g -o dat2graph2 str.cma unix.cma -I +str -I +unix options.mli options.ml parse_line.mli parse_line.ml manage_runqueues.mli manage_runqueues.ml machines.mli machines.ml util.mli util.ml printer.mli printer.ml dat2graph2.ml File "machines.mli", line 2, characters 50-63: 2 | type color_table = int * (int * int * int * int * Printer.color) list ^^^^^^^^^^^^^ Error: Unbound module Printer Hint: Did you mean Printexc or Printf? ``` 經過測試後發現為編譯時需要將 Makefile 中的 util.mli util.ml printer.mli printer.ml 進行位置調整將其調整自 machines.mli machines.ml 前面，最後更改結果為 ```ocaml LIB=options.mli options.ml parse_line.mli parse_line.ml manage_runqueues.mli manage_runqueues.ml util.mli util.ml printer.mli printer.ml machines.mli machines.ml ``` 在近期的 Schedgraph 中 ocaml 可以使用 default 版本不用進行版本轉換即可使用 ```shell $ which ocaml ~/.opam/default/bin/ocaml $ ocaml -version The OCaml toplevel, version 5.1.1 ``` 參考書中實驗使用 isolcpus 將特定 cpu 進行隔離使實驗時可以將特定任務在上面運行不會被其他任務干擾，並將任務運行在 cpu3 上面使用 dat2graph2 命令時添加 -\-forked，在繪圖後僅會保留在 trace-cmd 之後執行的任務，可以更清楚的聚焦在感興趣的任務上 #### 使用 stress-ng 搭配 chrt 建立各排程策略包含 SCHED_FIFO, SCHED_RR, SCHED_OTHER 進行繪圖觀察不同處理器核對不同排程策略的呈現，可以看到在處理器核 4 上面使用 SCHED_FIFO 會佔據大量的時間片段等到被 preempt 掉之前都會持有資源，在處理器核 3 上使用 SCHED_RR 三個任務會在持有的時間內交替運行，在處理器核 2 的是 SHCED_OTHER 會執行預設的排程器策略即 EEVDF (or CFS) ![Screenshot from 2024-07-02 21-43-05](https://hackmd.io/_uploads/SyPZD5bv0.png) 下方使用 stress-ng 建立不同數量的任務觀察任務在處理器核的行為 ### 4 cpu-bound task 使用 4 個 cpu-bound 任務，當任務的數量較少時，可以發現 EEVDF 對任務移轉的次數更高， CFS 更傾向於在相同的 CPU 上運行，以紅色任務為例，可以看到在 CFS 中運行的任務長時間待在處理器核 11 上運行，而在 EEVDF 明顯更為頻繁的在處理器核 1 以及處理器核 9 上面進行移轉 ![e4_](https://hackmd.io/_uploads/SJ_xIRJwC.png) ![c4_](https://hackmd.io/_uploads/ByAbI0yDA.png) ### 16 cpu-bound task 使用 16 個 cpu-bound 運行時會發現 EEVDF 以及 CFS 在任務數量與處理器核數量相同時，皆會將各個任務放置到固定的核心上運行，讓每個任務皆可以持有資源並持續運行 ![16](https://hackmd.io/_uploads/Bybjf6kv0.png) ![c16](https://hackmd.io/_uploads/ry3sDpJvR.png) ### 48 cpu-bound task 使用 48 個 cpu-bound 任務運行使用 EEVDF 以及 CFS 進行對比，可以發現兩者在 [10, 11] 區間時都是頻繁的交替運行，但是當將區間放大到 [10, 10.4] 時可以明顯的看出在 EEVDF 上任務的交替更為頻繁，所獲得的時間片段更少，在 CFS 的中可以明顯的看到一些較長的時間片段，更可以明顯看到在 10 秒一開始時處理核 2 上的任務長時間持有資源，也會因為這樣的原因而導致任務待在 runqueue 的時間變長，使得延遲變高 **EEVDF** ![Screenshot from 2024-07-01 16-05-00](https://hackmd.io/_uploads/SkohNklP0.png) ![Screenshot from 2024-07-01 21-31-10](https://hackmd.io/_uploads/ryJn1VePC.png) **CFS** ![Screenshot from 2024-07-01 16-09-42](https://hackmd.io/_uploads/Bk8JBklw0.png) ![Screenshot from 2024-07-01 21-28-29](https://hackmd.io/_uploads/Hk1vkEgP0.png) :::danger TODO: 找出更好展現圖例的方式，避免過多的空白。 ::: --- 使用命令指定 nice value 以及 cpu 並讓任務在後台運行 ```shell $ nice -n [nice_value] taskset -c [cpu_num] ./[task] & ``` #### EEVDF same nice color-by-command 搭配使用 color-by-command 以及使用矩陣相乘任務使其在後台運行並設定相同 nice 值以及不同 nice 值來進行，最後在將 trace-cmd 的結果儲存，將任務 wake_up 的時間以及出現次數繪製成圖表與 schedgraph 的結果進行比對可以看到三個任務具有相同 nice 值的矩陣相乘任務同時運行取 0.2~0.3 秒這個區間即在 0.1 的時間內會頻繁的進行交替，在交替過程中可以發現每個任務在運行時間上都接近相等，在將 wake_up 時間跟次數記錄下來可以發現每個任務的次數幾近相等 ![Screenshot from 2024-06-16 12-49-48](https://hackmd.io/_uploads/SkU8yehSC.png) ![eevdf](https://hackmd.io/_uploads/SJCrS3FI0.png) #### EEVDF different nice color-by-command 此處設定將三個任務的 nice 值分別為 task_a 使用 nice 值為 5, task_b 使用 nice 值為 0, task_c 使用 nice 值為 -5 在 schedgraph 的繪圖中看到在 0.2 以及 0.3 的這個區間中任務一樣頻繁的交替運行，但是可以發現其中 nice 值為 -5 的任務有著較高的優先權，其使用的時間明顯的高過於另外兩個任務，在觀察 nice 值為 0 的任務 b 可以發現其使用時間與任務 a 看起來差異非常小，但是若仔細觀察會發現任務 2 出現次數較任務 a 更多將各個任務的出現次數以及 wakeup 的頻率記錄下來可以發現很明顯的任務 c 隨著時間推近期出現次數為三者中最多，而任務 b 在出現次數上較任務 a 來的更多，最後 nice 值最高的任務 a 獲得了最少的使用次數 ![Screenshot from 2024-06-16 13-54-36](https://hackmd.io/_uploads/B1AS0ghBR.png) ![eevdfdifn](https://hackmd.io/_uploads/BkhqOnYU0.png) #### CFS same nice color-by-command 下方為對 CFS 進行繪圖的結果，可以明顯看到在同樣的 0.1 的時間區間中很明顯的 CFS 排程器所分配給任務的時間較長，所以在同樣時間區間中任務之間的交替次數較少，在相同的 nice 值下每個任務都獲得了幾近相等的時間而將各個任務的 wakeup 時間以及出現次紀錄並繪圖，可以發現三個任務的出現次數趨近相等 ![Screenshot from 2024-06-30 19-40-35](https://hackmd.io/_uploads/HJ1YEpRIC.png) ![cfss](https://hackmd.io/_uploads/rJ3gHKU8R.png) #### CFS different nice color-by-command 而在 CFS 中對不同 nice 值任務進行繪圖，可以看到 CFS 在對任務分配時間會依造 nice 值也就是書中提到的公式，來去分配時間給任務，所以很明顯的 nice 值較低的任務其優先權較高獲得了較多的時間，相反的 nice 值較高的任務對其他任務較友善，會獲得較少的時間除此之外也可以發現將 wakeup 時間以及出現次數繪圖，會發現相較於 EEVDF 任務之間的交錯次數較少， nice 值較高的任務的任務除了獲得更長的時間之外，還獲得了更多得出現次數 ![Screenshot from 2024-06-17 20-26-09](https://hackmd.io/_uploads/Hy5diopHA.png) ![cfs_dn](https://hackmd.io/_uploads/rJqA4tIUR.png) #### EEVDF task_cpu vs task_io_block ![Screenshot from 2024-06-30 18-38-50](https://hackmd.io/_uploads/HkE0r2RLR.png) #### CFS task_cpu vs task_io_block ![Screenshot from 2024-06-30 19-46-00](https://hackmd.io/_uploads/Sk5YHpCLC.png) ![Screenshot from 2024-07-01 23-24-16](https://hackmd.io/_uploads/S10r9BevA.png) ![Screenshot from 2024-07-01 23-48-26](https://hackmd.io/_uploads/Hk6yl8evC.png) 兩個任務分別為進行矩陣運算的任務 (task_cpu) 以及另一個任務 (task_io) 再進行矩陣運算之後會去進行 IO 的讀寫對於 EEVDF 任務會頻繁的切換，在進行短暫 IO 任務結束後會馬上獲得資源，在運行一段時間後，會再短暫的切換回 io 任務，而 CFS 在任務進行 IO 讀寫時會迅速的將資源分配給另一個任務藉此確保 cpu 的利用率，當任務結束完 IO 讀寫後同樣會再次獲得 CPU 資源，也可以看到將時間拉長後會發現 CFS 在長時間規律的排程後，會補給 IO 任務一段時間來確保公平性，最後以上方呈現的模式運行直到最後會剩 task_io 獨自運行因為 CPU 任務已經做完離開了參考資訊: * [淺談排程器演進的思考，從 CFS 到 EEVDF 有感](https://github.com/rsy56640/triviality/tree/master/content/sched-eevdf) / [討論](https://zhuanlan.zhihu.com/p/680182553) * [CPU 排程器測試工具](https://hackmd.io/@RinHizakura/H1Eh3clIp) * [Deep dive in the scheduler](https://static.linaro.org/connect/san19/presentations/san19-220.pdf), Vincent Guittot (2019) * [System pressure and CPU capacity](https://lpc.events/event/17/contributions/1490/attachments/1182/2434/System%20pressure,%20compute%20capacity%20and%20scheduler.pdf), Vincent Guittot (2023)