# 2024q1 Homework5 (assessment) contributed by < `ShawnXuanc` > ## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發 :::spoiler 筆記 (7) 因為硬體的問題所以很多事情都要藉由實驗才能發現，不管是液體跟氣體之間的關係或是接頭因使用時間而漏氣，以及冰塊大鐵盒冰塊卡住 (8) 硬體的問題要等較長的時間，而電腦會告訴你哪裡出錯 (9) 冰塊掉落問題 (10) 彈簧問題，成本超高，拉開困難度極高 (11) 缺乏設備導致無法發揮、機構知識，導致成效不佳，最後因為冰塊問題爆氣 (12) 與夥伴的期望不同，真實世界熱血無用 * 你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已 * 你最大的問題在太害怕失敗了 * 你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大 (13) 藉由畫出冰塊使用量的觀察，改變了方向選擇了一台無製冰功能把水槽冰塊送出的機器，機器下訂 (14) 紘銘介紹，點出問題者且很有義氣 * 創業就是在一連串情況不明朗的情況下做決定，而且金錢有限、時間更貴，你必須很清楚自己要什麼、不要什麼 (15) 買了泵發現效果不佳，藉由食品展認識一位廠長，了解到糖機的內部使用，並帶回去改造 (16) 用 stm32F429 但效率太慢改用intel Galileo 2，並搭配 python django 但是網頁回應太慢，後來用 js 在一開始遇到程式碼難維護得問題後來學習 Promise 來解決，程式撰寫上的複雜 (17) 冰塊分配器來了，解決一半問題 (18) 找出問題分析排除變因，反覆實驗 * 事情如果太順利代表絕對有問題，而問題永遠會從意想不到的地方冒出來 (19) 發現爸爸以前做機械相關，訂做不鏽鋼桌子失敗 (20) 將前面所得到的設備組合，漸漸完善 (21) 一些看似理所當然的東西，但背後卻需要很多的設計以及有很多的困難，最後更加完善前面的結果 (22) 焊接開始，發現基本看起來不難的東西，但動起手來就知道有很多細節 (23) 成功使用自動飲料機做出不用搖的紅茶，最後的結果是藉由每個人的分工來完成，如果要得到什麼，就必須付出同等的代價，雖然最後結果不如預期，但是沒有這個過程，就沒有14個月過後現在的作者 * 沒有一件事情是容易的 * 這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少 * 你的付出並不見得會有結果，但是加上許多人的幫助，可能一切就不一樣 * 對你而言真正重要的事物，會比你想得到的事物更早出現在路邊 ::: ### 閱讀心得 在閱讀因為自動飲料機而延畢的那一年時，總是可以感受到作者提到的因為這是真實世界啊這句話所帶的無奈感，從一開始對於硬體一竅不通的資工系學生為了想要解決問題，發現一個看似簡單的東西其中所包含的往往不是眼前所看到的那麼簡單，在過程中雖然想要放棄但是堅持了下來，到最後有成功的喝到自動飲料機所製作的飲料 最令我印象深刻的就是作者在處理冰塊的問題，在這途中因為先備知識的不足而導致前面的不順遂，從這邊也可以看到，在開始進行一件事情之前，如果沒有事先穩固基本，就會導致因為一些對於該領域或許是基礎但就是不知道而造成的阻礙，以及不是憑空幻想而是藉由實驗的方式來找到問題，所以老師才這麼強調前面六週的補強，就是為了讓我們之後在進行專題時可以更加順利，而不是因為基礎不足而做不下去 而在中間作者的無力感，在閱讀的過程也可以感同身受，尤其是看到「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大」這句話時，在遇到困難時往往都會有想要逃避的心情，但是逃避過後問題還是存在，而如果選擇面對過了之後下次再遇到時感覺就不一樣了，勉勵自己在往後的過程中都可以用這樣的心態來面對挑戰 在最後看到作者使用自動飲料機將飲料製作出來時，也非常為他開心，經過這麼長的時間犧牲了許多，在最後到手的那杯飲料在影片中完全可以感受到他們的興奮感，或許最後的結果不是最完美的，但是在過程中所獲得的，所經歷的才是最重要的如同作者說的「這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少」 不要去羨慕為什麼別人可以做到某些事情，因為在這個過程你不知道他背後做了多少努力，才有今天的結果，再次勉勵自己可以用同樣的心態面對往後的挑戰 ### 課程心得 記得剛開始參與課程時在了解作業內容跟熟悉 list 巨集用法、 queue 的操作花了一大段時間，在第二周考試時也因為來不及看當週的教材且對 bitwise 操作不熟悉，所以只答對了一題，當下在面對沒看過且一長串的程式碼整個人都非常慌張，後來去補看了當週內容才發現題目是將操作進行了一系列包裝，在問題上如果有事先看過教材不至於回答不出來，也更了解了自己的不足 剛開始進行開發紀錄時在文字表達方面，都覺得不太順暢，第一次被批改時還在每個地方都被打上了使用清晰明確的漢語書寫，也才發現用了這麼久的中文，在要將想法呈現出來時竟然會是這個樣子，經過這次也讓我更加重視了表達問題，在看文章時也會特別留意其他人的表達方式以及風格，雖然到現在還是會有問題，但我覺得跟一開始相比有了很多的改善，尤其是在進行3、4次考試檢討時，就感到明顯有了進步 對於老師提到上課拿到了分數卻沒辦法當下寫出來這部份也是我一直以來的問題之一，在以前學東西時常常會有把題目答出來之後就不再去理會問題，導致學習的過程中對於某些內容會有一種敷衍略過的感覺，而在經過課程的洗禮之後發現面對不會的內容都會更加盡力的去了解，因為如果這次不會不解決下次又會遇到導致越累積越多 到了目前經由作業以及考試的檢討都有感覺自己慢慢在成長，包含在其他課上看到了某個資料結構，就反應到這個跟課程中學到的概念有重複可以如何使用等等，以及對於巨集的了解，在修課之前通常看到巨集都會覺得很陌生，但是到了現在就有了很大的改善，對於閱讀方面之前常常會沒辦法靜下心閱讀較長的內容，會想找可以快速了解的，而到了現在也慢慢的培養更多的耐心讓自己可以閱讀第一手的資料 對於課程到現在學到的不僅僅是電腦科學的內容，還有對於問題的思考不單是全然接受，而是要抱著懷疑的想法，以及對於學習心態上的改變，該用什麼樣的心態去學習，而不是敷衍自己，很開心沒有因為害怕難度而逃避，而是選擇參與補上不足，並享受跟著課程的成長 ## 課程教材 ### [你所不知道的 c 語言](https://hackmd.io/@sysprog/c-prog/%2F%40sysprog%2Fc-programming)：指標篇 object 為在執行時間資料儲存的區域 lvalue 定義為 locator value 為一個物件的表示式不可為 void，對於 int *E = &a 而言 E 的 lvalue 為 E object 的位址，對於 *E 而言也就是 int object `&` 稱為 address of ，`*` 稱為 value of 以及 dereference *(int32_t * const) (0x67a9) = 0xaa6; 若去掉轉型就不能取值，因無法對整數進行 dereference 的操作 應用範例如 container_of 藉由 (size_t)&((TYPE *)0)->member 找到位移量，並藉由 member 的位置扣掉位移量找到開始的位址 void * 的使用需要強制轉型才能存取 object 因為沒有 object 為 void 對於 char str[10] 而言 str == &str 兩邊的形態不同但是的值相同左邊為 point to char 右邊為 pointer to an array，== 的判斷為相等除了兩邊都是空指標或是兩邊都是指向相同的 object 對函式指標進行操作時除了 & 或是 sizeof 皆會變轉成 pointer to function 函式指標 function designator 對其進行 dereference 過後仍然為 function designator，且不管進行幾次 dereference 皆為同樣結果，皆式 function designator ### [Linux 核心設計](https://beta.hackfoldr.org/linux/)：不僅是個執行單元的 process 對於每個 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，用來儲任務的資訊 reentrancy 可再進入即當程式被中斷之後可以回到中斷之前的執行區域，須避免使用共享記憶體 ### [Linux 核心設計](https://beta.hackfoldr.org/linux/)：不只挑選任務的排程器 以數學的觀點來思考排程就是個需要考慮公平，優先權以及搶佔效率跟擴充性的函數將任務映射到資源上，而在 linux 中就是排程器即把 process 映射到 cpu core 上，對於排程器在系統中分派任務時需要滿足，公平、快速的反應、吞吐量以及低功耗這些要求，對於不同得任務又得在細分 最早期版本的 64 個任務的排程器使用陣列來作為資料結構隨後使用鏈結串列搭配 epochs 的概念來作為任務的生命週期並藉由 goodness 來選擇任務其中還加入了對記憶體的考量，前面兩者皆為 O(n) 的排程器有著時間上的不確定性，之後新的的版本因考量在 SMP 上任務的增加因此重新設計了在 O(1) 時間進行排程的方法 O(1) 的排程器使用優先權佇列的相互切換搭配 bitmap 藉由第一個位元來找到所要任務，以這樣的方式查找任務的時間變成依優先權 (140) 的多寡來決定而不是任務的數量，藉此達到 O(1) 的任務查找，但是在任務的時間片段優先權處理還存在問題 隨後引進新的 CFS 機制不使用傳統的時間片段機制，而是使用等待時間，並使用紅黑樹來讓達到更高的公平性，其理念在於想在硬體上模擬理想的 multitasking cpu，也就是 cpu 可以被平均的分派各個任務，而且每個任務都可以並行在運行並平等的共享 cpu 讓每個任務獲得相同的 cpu 執行時間 對於排程器選擇在決定優先權上有包括 Rate Monotonic 以及 Earliest Deadline First 兩種前者以週期短為優先但是需要先藉由所有排程任務的執行時間與週期的比值做相加判斷是否大於 1 來判斷合理性才能進行排程 對於 EDF 而言是藉由 deadline 來作為選擇依據但是只能在單核上面進行以及對於即時的任務而言也無法使用 搭配閱讀〈Demystifying The Linux CPU Scheduler〉第二章詳細內容 ### [並行程式設計](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts): Atomics 操作 何為 race condition 即為執行緒相續競爭對資料做修改，也因為執行順序的不同導致不可預期的錯誤結果，在矗立這個問題上會使用互斥鎖來對資料進行保護，防止上述問題，但是大量的使用會成為導致效能上的瓶頸，因此藉由使用 atomic 來改善上述問題 atomic operation 為一個最小操作，即不可分割要一器呵成的完成，只有全部成功以及全部失敗兩種情形，以atomic_fetch_add_explicit 為例的 atomic 操作被歸類為 read-modify-write 操作 在 single core 可以藉由關閉中斷來防止 cpu 被搶走，藉此確保 atomic 但是在 multi core 環境下就要使用別種方法，通常是藉由 cpu 所提供的特殊指令，包含 compare-and-swap、load link、test-and-set...等等 其中 CAS 指令是藉由判斷舊值是否與記憶體內的值相同，如果相同就將新值寫入來完成值的修改 在多核心的架構中，每個 cpu 都會有自己的 cache，而當資料不在 cache 中時需要到 memory 中存取資料將資料搬到 cache 上，也因為 cache 的資料只有專屬的 cpu 可以存取，所以擁有相同資料的其他 cpu 的 cache 中所存放的就會是舊的資料，因此造成資料不一致的問題 cache coherence 即為防止這樣的狀況，即將資料寫入到自己的 cache 時將其他 cpu 的 cache 中相同的資料位址藉由廣播的方式進行 invalid，而這個廣播的方式是藉由 system bus 來讓各個不同的 cpu 可以彼此進行溝通 MESI protocol 為支援 write-back cache 在cache coherence 時的協議其包含四種不同的狀態，各自對應 MESI 的 4 個英文並用 3 個 bits 組合不同的狀態，在此協議下會有多種不同的請求依造 cpu 與 cache 之間的狀況來定義 * Modified * Exclusive * Shared * Invalid 當狀態為 Modified 的 cache block 被讀取到時需將其寫回主記憶體會花費大量時間 因此修改版本 MOESI 多了 Owner 的狀態即被資料 modified 後以及其他的 cpu 進行讀取過後將 cacheline 改成 shared 時原先擁有這份資料的 cpu 上cacheline 的狀態變成 Owner，藉由這個狀態當他的 cpu 對修改過後的資料再次進行讀取時就會直接將資料提供而不用重新寫回主記憶體中 在上述情況下為了確保資料的一致性需要讓其他 cpu 的 cache 對資料進行 invalid 而因為 cpu 跟 cache 之間的速度差異會使得 cpu 閒置，所以引入 store buffer 來縮短閒置的時間，即將資料更新在 store buffer 中 而使用上述方式時會因為進行資料廣播的數度較慢導致資料不一致的問題所以需要用 write memory barrier 來確保資料從 store buffer 更新到 cache 才能更新 barrier 之後資料 而當 cpu 的 store buffer 滿了之後 cpu 還是得要等待所以引入 invalidate queue，引入之後又使得 cpu 之間的關係更加複雜，smp_mb 就是用來約束 store buffer 以及 invalidate queue 之間 --- bh softirq "soft" -> 可由軟體控制的事物 -> 可排程 soft interrupt (k)softirqd 用來排程 softirq -> 綁定 CPU (確保服務品質) Linux 的中斷「不支援」nested interrupt tasklet 建構在 softirq CMWQ TODO: CPU sched book => 至少讀到 Chap 4 => 紀錄問題 [Demystifying The Linux Cpu Scheduler 筆記以及問題](https://hackmd.io/IalT8A_EQ_6L_Rj963PAKg?both) ## CH1 Basics of the Linux Kerne #### 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.02 整合環狀鏈結串列結構 * 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 被設計來進行搭配 ### 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 > 這個階層結構的走訪，以及 repesent 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. 是指尚未追蹤的意思嗎 ::: :::warning p.125 修正為 period_contrib > period_cont[ir]b. 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. p.129 修正為 period_contrib > As present in Figure 3.12, the period_cont[ir]b, the remaining contributing units from the previous update, is considered as well while calculating the number of passed time slots. p.130 修正為 period_contrib > And the period_cont[ir]b is updated as well. ::: **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 如何維護 repesentative 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 :::warning p.151 Task attachment 描述中 It if 修正為 If it > Task attachment Before moving a task from a cgroup to another, the can_attach method is called. [It if] returns an error, the operation is aborted. ::: **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 個核心總計 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 不會限制各 grpups 的頻寬，每一個任務都會盡可能的從 parent group 獲得更多的 cpu 時間， :::warning P.160 範例將兩個任務寫入同一個 group，修正後為 1588 寫入 group1，1589 寫入 group2，下方為範例對應文字以及範例 > The two tasks are grouped to two separate cgroups by creating subdirectories in the mountpoint, then writing their PID to task interface file. >#mkdir -p $MOUNT_POINT/{group1,group2} #echo 1588 > mygroups/group1/tasks #echo 1589 > mygroups/group1/tasks ::: :::warning p.161 圖 5.2 /system.slice 為 1024 以及 /user.slice 1024，下方說明為 /user.slice 獲得 512/(1024+512)，修正過後修將原本圖片 /user.slice 中 cpu.shares 修改由 1024 修改為 512 > CPU time allocation for each groups are illustrated by Figure 5.2, each groups are allocated CPU time from their parents weighted by their cpu.shares. /user.slice would get $100\%(\frac{512}{1024+512})$ ≈ 33% of the total CPU. ![截圖 2024-06-08 上午11.42.53](https://hackmd.io/_uploads/r1iH78bBA.png) ::: **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*** ::: #### 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 被消耗的配額多寡 :::warning p.167 sched latency ns 描述中重複字 called called 修正為 called > **sched_latency_ns** is the targeted preemption latency for CPU-bound tasks, which is [called called] target latency in Equation (2.4) of Section 3.3.2. It is the initial value of scheduler period, and scheduler period is essentially timeslices of each task to run once. In CFS, timeslices are of variable length and have no persistent notion unlike traditional, time-slice based scheduling concepts. The default value of this latency value is 6ms, with nanoseconds as its unit and scaled by sched_tunable_scaling. ::: :::warning p.169 sched_rr_timeslice_ms 描述句尾缺少句號，修正後新增 . > **sched_rr_timeslice_ms** is a parameter that tunes the behaviors of real-time tasks belonging to SCHED_RR scheduling class. SCHED_RR is identical to SCHED_FIFO except that each tasks are allotted a predetermined timeslices, all tasks can only run until they completely used up the timeslices. The length of said timeslices are controlled by sched_rr_timeslice_ms[] ::: :::warning p.170 GENTLE_FAIR_SLEEPERS描述中句尾 , 修正為 . >**GENTLE_FAIR_SLEEPERS** dampens the credit given to tasks sleepers (tasks that tends to sleeps for a long time). This feature tries to reduce run time of sleepers, the reduced run time will then be distributed to active tasks[,] ::: :::warning p.170 NEXT BUDDY 句尾 .. 修正為 . >**NEXT BUDDY** is a feature that works after WAKEUP_PREEMPTION failed to make the waking task (wakee) preempt the currently running task. This feature gives the scheduler a preference to preempt the running task with the wakee[..] ::: TODO: EEVDF (since Linux v6.6) ### Assumption 對於每個任務而言制定一個 weight 來決定其可分配到的資源，即為所有任務權重分之當前任務的權重 $f_t(t)=\frac{w_i}{\sum_{\in\\A(\tau)}{w_j}}$ $(1)$ 並制定一個在時間區間內 [t, △t] 預期可以得到的時間，以積分代表意義為在理想狀態下的時間可將其切分至趨近於無限小的 $S_i(t_0,t_1)=\int_{t_0}^{t_i}f_t(t)d\tau$ $(2)$ 也因離散時間得限制導致任務沒辦法總是將預期拿到的時間全部用完，因此制定 $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)$ $(3)$ ### EEVDF Algo 在演算法中假設每個任務皆會進行 request，request 達成時可能會重新發請求或是改變狀態為 passive 而對於任務 request 有高度彈性並沒有限制請求大小，並對 period 制定為固定的 interval 將前面公式帶入得到下方公式一樣作為任務應該得到的時間 $S_i(t_0,t_1)=\int_{t_0}^{t_i}\frac{w_i}{\sum_{\in\\A(\tau)}{w_j}}d\tau$ 並制定 virtual time ，這邊 EEVDF 的 virtual time 跟 CFS 的 virtual 不同的在於 CFS 是將 vurtual time 作為權重化的任務執行時間，每個任務都會有一個獨有的 vruntime，作為其運行時間 而在 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_2)-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))$ 帶入移項得到 $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-11 中午12.56.35](https://hackmd.io/_uploads/SkAbtIrHR.png) 並舉了例子可以看到所有任務共享一虛擬時間，並且最下方有一個真實時間，()中代表 $(V_e,V_d)$ eligible time 以及 dealine 皆為計算得到 以兩個任務權重皆為 2，任務 1 的請求為 2 、任務 2 的請求為 1 時， c1 在真實時間為 0 時變成 active, c2 在 １變成 active 此時計算 $Ve$ 藉由 $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 值的兩個任務而言若任務具有較低的 latenct-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 對節點進行排序 在上述有看到 eevdf 中使用 ### 開發環境 ```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 ``` 參照 [linhoward0522](https://hackmd.io/@sysprog/BJh9FdlS2) 以及 [chun61205](https://hackmd.io/@sysprog/By-Q7reB3) 所執行的實驗在 linux 6.9.3 對 EEVDF 排程器進行並將結果視覺化 ### Jitterdebugger 在書中提到在 cfs 中有著對於延遲上面的議題，對於需要教快進行回應的任務會因為公平性的關係忽略掉即時響應的部份，使用 jitterdebugger 針對排程器延遲比較 CFS 以及 EEVDF 的差異 下方為 jitterdebugger 會顯示結果並關注 scheduling latency (wake up 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 任務分別以 CFS 以及 EEVDF 排程器運行 ```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 ### Schedgraph 參照 [linhoward0522](https://hackmd.io/@sysprog/BJh9FdlS2) 同學進行 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 的安裝，其特點在可以針對核心數量較多的裝置進行跟蹤 目前 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 /home/username/.opam/default/bin/ocaml $ ocaml -version The OCaml toplevel, version 5.1.1 ``` 針對書中實驗使用 isolcpus 將特定 cpu 進行隔離使實驗時可以將特定任務在上面運行不會被其他任務干擾，並將任務運行在 cpu3 上面 #### EEVDF same nice 在此處使用 3 個任務進行測試取 0.1 到 0.4 這段區間可以看到任務交替運行的狀況 ![Screenshot from 2024-06-15 21-42-30](https://hackmd.io/_uploads/BJ_XjMoBA.png) 拉近查看三個任務在 EEVDF 排程下的狀況 ![Screenshot from 2024-06-15 21-48-04](https://hackmd.io/_uploads/BkEaiGiHA.png) #### EEVDF different nice 使用 stress-ng 搭配建立三個不同 nice 值的 cpu-bound 任務分別為 5, 0, -5 ![Screenshot from 2024-06-15 22-14-07](https://hackmd.io/_uploads/SkzyM7iHA.png) 並將結果拉近查看 0.5 到 0.6 之間任務交替，明顯可以看到其中一個任務一次行使用了較長的時間 ![Screenshot from 2024-06-15 22-27-44](https://hackmd.io/_uploads/S1dWBXoHC.png) 使用命令指定 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) ![task_wakeup_times_same](https://hackmd.io/_uploads/H1AN3oaSC.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) ![task_wakeup_times_dif](https://hackmd.io/_uploads/Skoz2jarR.png) ![task_wakeup_times](https://hackmd.io/_uploads/HJ_m2o6SR.png) #### CFS same nice color-by-command 下方為對 CFS 進行繪圖的結果，可以明顯看到在同樣的 0.1 的時間區間中 很明顯的 CFS 排程器所分配給任務的時間較長，所以在同樣時間區間中任務之間的交替次數較少，在相同的 nice 值下每個任務都獲得了幾近相等的時間 而將各個任務的 wakeup 時間以及出現次紀錄並繪圖，可以發現三個任務的出現次數趨近相等 ![Screenshot from 2024-06-17 20-12-01](https://hackmd.io/_uploads/rk6Q_o6r0.png) ![task_wakeup_times_dif](https://hackmd.io/_uploads/S1cv1nTBA.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) ![task_wakeup_times_dif](https://hackmd.io/_uploads/HyOtpoTSA.png) ## 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[num]/cpufreq/scaling_governor 來選擇所需的 governor [Operating Performance Points (OPP)](https://docs.kernel.org/power/opp.html). 現今的 SoCs 中會有多個[子模組](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 上的基礎架構，可以藉由軟體的方式來控制硬體的能力像是溫度以及電流等 [Energy Model](https://docs.kernel.org/power/energy-model.html) ### What does impact the computer capacity of CPU 著重在 system pressure 以及 [CPU capacity](https://www.kernel.org/doc/Documentation/devicetree/bindings/arm/cpu-capacity.txt) ，影響 cpu capacity 的因素可以分為兩部分， * 減少 cpu cycle * 通過 cpu 的頻率影響 cpu 的效能 主要內容著重在 cpu performance 的部份，影響 cpu performance 的因素中跟頻率相關的重要部份包含 1. High Frequency Scaling: 跟硬體相關，cpu 會以 kHz 調節頻率，也因為頻率調節快速，所以排程器沒辦法獲得特定時間頻率 2. Thermal and Power Capping: 在 kernel 中熱能管理框架以及功率限制會因為熱能限制以及電力管理的關係而限制 cpu 的最大頻率 3. User Space Controls: 在 user space 有可以調整 cpu 頻率的界面，通常被用來進行電源得管理，而這些限制的時間取決於用戶需求 為了滿足這些需求，Vincent Guittot 著手設計了新的排程器相關 interface 目前有的包含 * arch_scale_cpu_capacity() 作用為返回特定 cpu 的最大 capacity 初值為 1024 * 以及 arch_scale_thermal_pressure() 為系統受到的熱壓力對 cpu capacity 的影響，也可以讓硬體以及韌體使用控制頻率的上限 此外可以利用當前的頻率來得知目前的 cpu capacity，當此訊息不正確時還可以利用硬體 counter 來得知最後一個 tick 的 cpu 頻率，並使用 arch_scaling_cpu_freq 追蹤當前頻率下的最大計算能力，以及最大 capacity 不總是等於最大頻率 (cpuinfo_max_freq)，因為會受到熱能的影響，無法一直保持最大頻率的運算，因此要定義一個在排程時可以使用的最大頻率 ### Userspace Pressure on CPU capacity [cpu governor](https://www.kernel.org/doc/Documentation/cpu-freq/governors.txt):檢測當前負載狀況，並根據當前的負載給出可供使用的工作頻率，即可以動態調節頻率，在 linux kernel 中的 cpufreq governor 包括 * Performance. 以性能為優先，會將 cpu 頻率調整為最大值 * wersave. 功耗為優先，會將 cpu 頻率調節為最小值 * Userspace. 允許 userspace 藉由 sysfs 中的 scaling_setspeed 設置 cpu 的頻率 * Ondemand. 根據當前系統負載設置 cpu 的頻率 * Conservative. 與上述的 Ondemand 相似會根據 cpu 的利用率進行調節 * Schedutil. 整合到排程器之中，根據排程器的 PELT 進行負載評估，目前僅對 CFS 排程的任務進行頻率調整，RT、DL 兩個不同的排程策略的任務則總是在高頻率的狀況下運行 [Load Average vs CPU Utilization](https://serverfault.com/questions/667078/high-cpu-utilization-but-low-load-average?_gl=1*jxhd3o*_ga*MTEyNzk5NDIxMi4xNzE3NTA3NjIz*_ga_S812YQPLT2*MTcxOTAzNDQ5My44LjAuMTcxOTAzNDQ5NC4wLjAuMA..). Load Average. 在時間內有多少任務在 per-CPU runqueue 中等待，為一個瞬間的量測，當前時間點對 cpu 造成的壓力 CPU Utilization. 為 cpu 當前忙碌程度，為累積量 兩者相關聯但是不能視為相同，可以想像 1. 在 runqueue 中有多個 IO 任務處於等待，這樣會導致 cpu 的負載很高，但是其利用率很低， 2. 以及 runqueue 中只有一個任務但是其不斷使用 cpu 導致其利用率很高這樣不同的情境 以 Usespace 為例根據使用電源與否調節筆記型電腦的 cpu 頻率，排程器也會根據當前的任務來進行適當調節，如 MP3 的播放使用較低的頻率，其目的在於獲得 max_freq_request ，並將資訊提供給排程器使用 不能重複使用 arch_scale_cpu_capacity 的原因 1. 包括在使用負載追蹤時會需要調節 cpu 的利用率才能獲得較為準確的負載情況 2. 以及在 bit.little system 時使用 EAS 會有 CPUfraq Governor 進行頻率調節 Vincent Guittot 提出新的 interface 稱為 arch_scale_cpu_capping ，用來指未來幾秒的持續計算能力 (考慮當前的熱能以及功耗)，藉此可以結合 [scaling_max_freq](https://www.kernel.org/doc/Documentation/cpu-freq/user-guide.txt) 來對任務的分配達到更好的抉擇 提到 pathch 的完成，以及去調查各個使用 arch_scale_cpu_capacity 的例子來決定什麼時候要使用最大 capacity　或是新提出的 current sustainable capacity 也解釋說在某些情況下會想使用 maximum available compute capacity 像是 deadline-workloads 以及在分配任務時能知道在接下來時間的可用資源所以會需要新的指標也就是 arch_scale_cpu_capping，最後提到如果引入後還有一個需要考量的問題在 Misfit task detection (用來檢測被分配到不適合的 core 的任務) 的部分 ### Firmware/kernel pressure on CPU capacity 要處理不同類型的壓力像是韌體方面以及 kernel 上的，並讓 cpu 可以負荷最糟的情況，可以用像是 [FREQ_QOS_MAX](https://elixir.bootlin.com/linux/latest/source/include/linux/pm_qos.h#L82) (在系統中會根據傳進來的是 `FREQ_QOS_MAX` 還是 `FREQ_QOS_MIN` 決定返回的值) 的方式來獲得各個請求的 最大值，根據多個請求來挑選最適合的就不用另外設計新的框架來做使用，並提到使用這個方式會有 blocking 通知的問題，可能對排程造成問題，應該使用 non-blocking 的方式來防止對排程造成問題 [DTPM](https://lore.kernel.org/linux-pm/5679624.lOV4Wx5bFT@pce/T/) The dynamic thermal and power management is a technique to dynamically adjust the power consumption of different devices in order to ensure a global thermal constraint. 提到要考慮到 arch_scale_thermal_pressure ，並表示應該要將重新命名為 [arch_scale_hw_pressure](https://lore.kernel.org/lkml/20240130003303.glyz5vhrnhydgd4x@airbuntu/)，即要考慮到硬體再過熱或是頻率過高時會有降低能耗的措施，而藉由新提供的函式來獲得上述情況提到的降能時的最小壓力資訊，來確保任務排程時來幫助排程確保系統在高效和穩定的狀態下運行