HackMD
2025q1 Homework5 (assessment)
contributed by < bevmmf >
注意細節！
研讀 Linux 核心設計: 不只挑選任務的排程器
我覺得材料對 scheduler 的描述很有趣且直觀，「scheduler 就是一個數學函數，功能是映射 process 到系統資源」。單單要將此功能實現可能不難，但若是還需考慮性能規格如以下，那就不是件容易的事情。
性能規格
- fairness
若沒有公平性，priority 低的 process 長時間或誇張地說永遠不會使用到 CPU ，導致該 process starvation ，進而讓使用者有卡頓的使用體驗。具體例子是 file system 的同步任務若 starvation ，會導致 I/O blocked，間接造成 interactive processes 低效。 - low latency
針對的是 I/O-bound tasks、IRQ、interactive processes、real-time tasks 等重快速響應的 process 。玩遊戲滑鼠或鍵盤的低延遲很好為此做解釋。 - high throughput
此針對的是系統對非低響應時間任務的執行效率，追求「長期」運行的效率。 - energy efficiency
- Real-Time Support
此與 low latency 有重疊性，都是為了低響應時間任務，不同的是此規格關注的process是有明確時間限制的。特別重視 preemption 與 context switch 的效率 - Scalability
可擴展性是現代非常重要的一部分，由於目前 multi core CPU 已經是必備。如何在增加 core 數時、oversubscription 或是NUMA（Non-Uniform Memory Access）架構時，還能維持相同程度的規格( fairness ~ Real-Time Support )，即是此規格關注的。
而材料也做了一小實驗嘗試去求得scheduler之效能，也可以粗略地說是 Context switch 的效能。 本來使用 perf 出現的失真問題是因為 scheduler 可能將兩 process 在不同的 core 執行而導致跨核心通訊(透過共享記憶體或 interconnect，引發 cache coherence 延遲（cache misses 或 invalidation）)與核心間協調問題(例如 IPI，Inter-Processor Interrupts)。因此改為使用 taskset 工具將兩 process affinity 指派到同一 core 底下。最後得出結果為 。此數量級十分重要，因為scheduler 切出的 time slice 必需在此數量級 scale 以下才有意義。
最後針對 scheduler ，因為不同任務所追求的規格不同，劃分了任務種類 :
普通 process交互式行程 (interactive processs): 對延遲敏感，追求 low latency (如 GUI 應用 等 IO-bound 任務)批處理行程 (batch process): 追求 throughput (如背景執行資料處理等 CPU-bound 任務)
即時 process: 有deadline
linux scheduler
Linux Scheduler 演進的時間順序
- Linux 2.4 Scheduler (~2001-2003)：
時間：Linux 2.4 系列（約 2001 年發布，持續使用至 2003 年左右）。
特點：使用 global runqueue，O(n) 複雜度，支援 SMP 但 scalability 差，non-determinism 高。原因是因為dequeue時需要lock，同時多核競爭一lock導致開銷隨 core 數上升 (scalability 差)。再來因為將執行完一 time slice 的 process 放到 expired queue 時以 O(N) 搜尋要放置的位置造成效率隨負載量上升 (non-determinism 高)
背景：單核或少量核心系統為主，任務數較少，real-time support 需求不強。
2. Linux 2.6.0 至 2.6.22：O(1) Scheduler (2003-2007)：
時間：Linux 2.6.0（2003 年）至 2.6.22（2007 年）。
特點：引入 priority array 和 bitarrays，實現 O(1) 操作，提升 scalability 和 determinism，但 fairness 不足。而該O(1)實現設計思路分為三 :
- access
array是唯一能達到O(1)，linked-list為O(N)，tree 一般是 => 只能用 array - search
沒有任何 data structure 在最壞情況為 O(1) 。
hash table 平均是 ，但最壞情況是 ;
大部分 tree（b-tree, red-black tree）平均和最壞情況都是 ; - insert/deletion
linked-list、stack、queue 皆為 O(1)
而實作原理為以下 :
將本來的 runqueue 換成 priority queue ，同時因為搜尋下一個任務的 priority 為 O(M) 常數時間，以 bit array 作為索引達成 O(1)。而在expired array 的搜索放置也有一樣問題，因此也多維護一 expired bit array 作為索引。
運作原理為以下 :
-
- 在 active bitarray 裡，尋找 left-most bit 的位置 x;
-
- 在 active priority array（APA）中，找到對應 queue
APA[x];
- 在 active priority array（APA）中，找到對應 queue
-
- 從
APA[x]中 dequeue 一個 process，dequeue 後，如果APA[x]的 queue 為空，那麼將 active bitarray 裡第 x bit 設定為 0;
- 從
-
- 對於目前執行完的行程，重新計算其 priority，然後 enqueue 到 expired priority array（EPA）相應的 queue
EPA[priority];
- 對於目前執行完的行程，重新計算其 priority，然後 enqueue 到 expired priority array（EPA）相應的 queue
-
- 若 priority 在 expired bitarray 裡對應的 bit 為 0，將其設定 1;
-
- 如果 active bitarray 全為 0，將 active bitarray 和 expired bitarray 交換;
背景：multi-core 系統興起，伺服器負載增加，需更高效的 scheduling。
- 如果 active bitarray 全為 0，將 active bitarray 和 expired bitarray 交換;
- Linux 2.6.23 起：Completely Fair Scheduler (CFS) (2007-至今)：
時間：Linux 2.6.23（2007 年）引入，持續改進至今。
特點：採用 red-black tree，強調 fairness 和 low latency，結合 per-core runqueues 和 load balancing，提升 scalability。
背景：桌面、伺服器、行動裝置普及，需平衡 interactive 和 batch processes。 - SCHED_DEADLINE (2013 年起，逐步完善)：
時間：Linux 3.14（2013 年）正式引入 SCHED_DEADLINE，後續版本持續優化。
特點：基於 Earliest Deadline First (EDF) 和 Rate Monotonic Scheduling (RMS)，專為 real-time support，確保 strict deadlines。
背景：嵌入式系統、多媒體、工業控制等對 real-time tasks 需求增加。 - Energy-Aware Scheduling (EAS) (~2016 年起)：
時間：Linux 4.x 系列（約 2016 年）開始整合 EAS，針對行動裝置優化。
特點：根據 CPU topologies 優化 energy efficiency，適應異構 multi-core（如 big.LITTLE）。
背景：行動裝置和 IoT 設備興起，需兼顧 performance 和電池續航。
繼續 hw3 kxo
CSAPP chp2 複習
我看〈因為自動飲料機而延畢的那一年〉
這篇文章熱血的像是少年漫畫，同時也很符合現實的將真實世界遇到的種種問題反映吃來。因此讓我在看的過程能夠享受其中，跟著作者的視角看整個自動飲料機誕生，也在這個過程當中學習到很多學校教育不會告訴我們的有趣、實濟、現實與寶貴的經驗與辛苦談。
其中有幾個部分與幾句話是讓我產生共鳴與有感的。
第一個部分是作者起初做機構實驗遇到的體悟，「資工系實驗維度是數小時到數日，而機械系的實驗維度是數周到數月」。硬體的迭代週期與軟體的實驗分析維度的不同也是我最近很有感的。正好最近也面臨採購研究實驗器材的狀況，光是決定一個馬達規格其中就有許多因素要考慮，若是還要加上齒輪箱與耦合機構，涉及的不僅是尺寸，還有運動規劃、負載效應、馬達額定與最大轉速是否足夠與轉速太低不好控制等等問題。
第二部分是作者遇到設備不足時該如何解決。我認為作者的決定 : 租借設備(系所老師 -> 公家機關 -> 企業行號)，在成本限制高時是個很好的思考流程。
第三部分是作者買設備時的感悟，「花大錢買設備首要之務就是訂規格，多花錢買不需要的規格是浪費，為了省錢買性能不足的產品是更大的浪費。」，盡可能的量化需要的規格，知道需要什麼程度的規格，也是系統開發很重要得一環，畢竟成本不是無限的。系統還有一個重要的觀念就是整合，反過來說要先將系統拆分成多個子系統，在對每個子系統做模組測試成功後，再將多個子系統整合起來測試，最後才能讓系統做最後整合測試。
除了以上實務經驗之外，我認為心態層面也是不可忽視的重要能力。我認為在過程中最關鍵的點其實是中間作者因為機構問題做不出製冰機一度想放棄的那時間點。就像是學習曲線最高點一樣，是問題最關鍵的部分，只要熬過那個x點，後面的問題會越來越順利。這也呼應到老師所說的，「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」，那個失敗才是整個過程中最精華的段落。然而有時候也不應對一個問題的解決過於執著，如同文章所說「如果問題過於困難無法解決，那就重新定義問題吧！」。
看完這篇文章與經過這幾周課程，我認為老師不只想教授我們相對應的知識，更多的是素養、對抗重大問題的能力與與人有效溝通的實例。「誠實面對自己」，這句話是我目前覺得簡單但又重要也是時時刻刻提醒自己的一句話。我現在養成每次學習都會問自己有沒有誠實面對自己。有那裡是自己想偷懶又含糊帶過的。這句話給我很多主動審視自己的機會。
專案方向
- 有鑑於目前學習狀況，我想投入改進〈並行和多執行緒程式設計〉系列講座和〈Concurrency Primer〉，以做實驗與分析做為看完CSAPP理論後的實作補強對並行程式的理解
