# 2025q1 Homework5 (assessment)
contributed by < `JUSTUSVMOS` >
## 6/18一對一討論
### Q1: CFS 如何確保 fairness?
CFS 會在每個 CPU core 維護一個本地 run queue，並用 virtual runtime 來決定每個任務得到的 CPU 時間。調度器會讓 virtual runtime 最小的任務先執行，並在多核心情境下進行跨核心的負載平衡，確保整個系統所有任務都能公平地獲得 CPU 資源。

在多核處理器上，CFS 是以 core 為單位維護排程佇列（run queue），但會藉由 scheduler domain 機制進行跨核心的 load balancing。這樣即使在多 core 情境下，所有任務在全系統範圍內也能達到公平執行，不會出現某一核心被塞滿、某一核心很閒的情況。

### Q2: Hyperthreading: 在單一 processor core 上同時執行多個 (hardware) thread，但是共用 ALU、FPU，於是一個 core 有幾組 pipeline？
在具有 Hyper-Threading 的 core 裡，整體只有一條pipline，HT 只是讓多條 hardware threads 輪流或交錯把指令送進同一條pipline．

如果是指 execute 區段，以 Core i7-920 為例，有６個執行 port (2ALU/FP+2 Load AGU+Store Addr+ Store Data)，每個 port 每 cycle 最多能處理1條 micro-operations．

所以Hyper-Threading 不會複製 pipeline 或 ports，只是多分一套 thread state，讓兩條 hardware threads 交錯競爭同一條 pipeline 和這 6 條通道。
### Q3: SMP 的 processor core 共用 L2 cache，為何不會有直接的安全疑慮？
在 SMT（Hyper-Threading）裡，硬體 thread 在同一 core 上同 cycle共用 pipeline、L1/L2/TLB 等所有資源，容易被利用做 fine-grained timing side-channel．

SMP 裡不同 core 之間主要共享的是 L2/L3，需經過 inter-core 連線和 coherence protocol，再加上排程在不同 core 之間切換，但因為干擾粒度粗、時序不好精準控制，相對難度較高。

:::danger
你連說話都說不好嗎？
:::

---

## 期末專題提案
希望能夠進行

[排程器研究](https://hackmd.io/@sysprog/linux2024-projects?stext=2011%3A11%3A0%3A1749083713%3Ame0VN0)，聚焦於「基於時間序列與 eBPF 的 Load Balance 與 CPU 排程優化」。
雖然現有 EEVDF 及 Energy Aware Scheduling (EAS) 已納入 Linux Kernel，現行實作大多只考慮「當下」負載，未充分利用「短期負載時間序列」協助決策。

可能的專案進行方式是：
參考近期 eBPF 應用實例，於 kernel tracepoint（如 sched\_switch、sched\_load\_balance）收集各核心 CPU 利用率、runqueue 長度、page faults、I/O wait 等指標，構建短期滑動窗口時間序列，進一步輔助 can\_migrate\_task() 或 EAS 的遷移判斷。希望藉此減少過度遷移，提升整體吞吐、延遲與能源效率。

:::danger
關於 CPU 排程器，你具備哪些背景知識呢？除了「查詢」和「複製貼上」，你真正的產出在哪？
:::
---
## 學習狀況

### 遇到的問題

在閱讀" Demystifying the Linux CPU Scheduler " 4.5 Core scheduling章節中，在Hyper-Threading 的核心上，兩個thread是在時脈週期級別交錯（interleave）執行其指令流，還是由作業系統排程器以極短的 timeslice 在它們之間保存／恢復完整上下文（暫存器、快取、TLB 等）來模擬同時執行？而在此過程中，CFS 與 Core scheduling 又分別在何時、依據何種邏輯介入，決定哪條執行緒獲得 CPU 執行權？
****
## 閱讀〈因為自動飲料機而延畢的那一年〉啟發紀錄

作為 Linux 核心設計課程的學生，閱讀〈因為自動飲料機而延畢的那一年〉，讓我對系統軟體開發者的態度有更深刻的體會。文中描述作者從一個小小的自動飲料機專題，跌跌撞撞地走到畢業遲延，不只是技術挑戰，更是態度、細節和責任感的考驗。這些心得，跟課堂上反覆強調的「誠實面對自己」、「理論結合理論與實務」、「細節決定成敗」三大點不謀而合。

### 一、系統軟體的開發態度

自動飲料機的故事讓我意識到，「做到能動」不代表「做好」。開發系統軟體時，表面上功能跑得起來，但背後如果沒有對應好異常處理、資源釋放、效能瓶頸和極端情境，很容易留下難以察覺的地雷。例如課堂介紹的**指標操作、記憶體管理**，只要一個小疏忽，就可能導致 use-after-free 或 memory leak，嚴重時甚至危害整個系統的安全性與穩定性。

這也回應了課程初週強調的「軟體缺失導致的危害」──**從小專案到波音 787 飛機系統，規模差異巨大，但只要開發態度浮躁、草率，問題就會被放大**。作業系統核心設計看似離日常很遠，但其實每個系統呼叫、資料結構、錯誤處理的背後，都是這種「誠實面對自己」的態度在支撐。

### 二、對細節的重視
:::danger
dereference 不要翻譯為生硬的「解引用」，其作用是「取值」
:::

飲料機專題裡「一行小 bug 反覆抓不到」、「硬體連接一條線忘記插，debug 半天」這些情境，我在寫 C 語言 linked list、bitwise 操作時感受很深。系統軟體沒有模糊地帶，每一個細節都必須親自確認。比方說，指標運算時漏掉一個 \* 或<s>解引用</s> 時誤用空指標，結果就天差地遠；又如 cache locality、alignment 這些「小細節」，表面上只是資料在記憶體的排列方式，實際卻會**直接決定效能與正確性**。

以課堂實作的 schedsort 舉例，bucket 合併階段如果能確保每條執行緒僅對結果陣列進行線性、連續的寫入，就能最大化 cache locality，顯著減少 cache miss 與寫入延遲。反之，如果寫入位置分散或交錯，會導致 cache thrashing 和效能瓶頸。這種差異只有在 trace memory 行為、用 perf 或 cachegrind 工具做過 profiling 才會有切身體會。

:::danger
你真的用過 cachegrind 嗎？
:::

Bloom Filter 的並行實作更讓我體會 alignment 的重要。`_Atomic uint64_t` bit array 必須正確 8-byte 對齊，否則 atomic operation 不僅可能效能劇降，甚至導致未定義行為。若多個執行緒同時操作未對齊的資料區塊，不但會出現 false sharing、cache line 汙染，還會出現極難 trace 的競爭條件，這些問題只有真正實作和壓力測試才能完全意識到。

課堂上要求用 gdb 追蹤程式執行、用 valgrind 找記憶體錯誤，其實就是把抽象的 bug 轉化為具體、可觀察的細節，這對系統軟體開發至關重要。如果對細節沒有耐心，很容易在這些環節迷失或被擊潰；唯有把每一行程式、每一個記憶體存取路徑都檢查到位，才有機會寫出穩健且高效的系統程式。

### 三、理論與實務的融會貫通

文中作者在做飲料機時，常因理論想得太簡單，實作時才發現理論和現實有差距。例如想像中的「馬達動一下就出一杯飲料」，實際上還要處理感測器、同步機制、意外中斷等情境。這呼應了我們在學 C 語言指標、資料結構、排程器演算法時，**只學理論不夠，一定要動手 trace、debug、看實際核心碼，才能真正理解設計的考量與 trade-off**。

像「為何 Linux kernel 要用 linked list，而不是一般 array？」、「為什麼排程器不只是挑下一個要跑的 process，而是要考慮 scalability、non-determinism、group scheduling？」這些問題，都是理論與實作不斷來回反覆後，才有真正的領悟。

:::danger
你想懂了嗎？闡述你的洞見。
:::
在單核時期，系統中的行程數量有限， scheduler 只需掃描一個全域隊列（O(n)）就能挑出下一個要執行的任務，負擔幾乎可忽略。如今伺服器通常具備數十到上百個實體核心。當這些任務被分配到不同的 cgroup（或 CGROUP-V2）以實現隔離時，調度流程便不再是單一地遍歷某棵大紅黑樹，而是先在「組」的層次挑出下一個可執行的 cgroup，再在該組內挑選具體的行程。此時若假設共有 c 個 cgroup，每個 cgroup 平均含有 k 個任務，則此多層結構的調度複雜度可有效控制在約 O(c + k)，遠低於單一隊列的 O(n)。這種「先挑組、再挑行程」的多層結構，要兼顧組間隔離與組內公平，同時必須避免各組之間或組內外之間的鎖競爭。

:::danger
注意用語，process 是「行程」，queue 是「佇列」，real-time 是「即時」(而非「實時」)。見 https://hackmd.io/@sysprog/it-vocabulary
你該從第一手材料學習，而非胡亂複製貼上。
:::

另外，任務行為本身難以預料。在I/O 密集、網頁伺服器或資料庫等場景，一旦請求到達，就需要盡快響應；若scheduler 只依時間片輪轉，長時間佔用 CPU 的工作就會搶走大部分時間，而那些突發的短任務反而得不到調度，延遲急速上升。由此可見，排程不僅要追求公平，也需對突發與短作業予以適度優先。

因此，現代 Linux scheduler 採用「Per-CPU 本地＋多層次調度結構」的設計。每個實體核心有自己的本地佇列，優先排程本核 (core) 任務，減少跨核鎖競爭；只有在負載嚴重不均時才會進行跨核負載平衡。每個 CPU 核心本地調度的複雜度為 O(n/m)，其中 n 是任務總數、m 是 CPU 核心數量。負載平衡操作的複雜度則約為 O(m)，因需比較不同核心間的負載差異。
同時引入「層次化組排程（Group Scheduling）」，先在 cgroup／使用者／容器層級以 fine-grained 方式分配，確保隔離域互不干擾，再於每組內部維持組內公平。最後，透過動態自適應機制，對 I/O 密集型、短作業、實時任務或有 Deadline 限制的任務優先排程，並在「突然有任務被喚醒」「負載驟增」「高優先佔用」等情況下即時調整，才能在兼顧整體吞吐的同時，也保持低延遲響應。

---