# 2026-05-12/14/21 問答簡記
## 期末專題
> [專題列表](https://hackmd.io/@sysprog/linux2026-projects)
> 課程規劃在 6 月 27 日舉辦[期末成果發表](https://hackmd.io/@sysprog/linux2026-projects)，預計採用線上直播的模式
## [Open Source Summit North America](https://events.linuxfoundation.org/open-source-summit-north-america/)
## 《Demystifying the Linux CPU Scheduler》
## Krixi0828
condition variable
broadcast
fast userspace
wake wait
constract
持有資源者透過 condition variable 去通知其他 thread
沒等到的繼續 wait ，有等到的 wake
## ericlin1231
- RR : 以 timeslice 為單位排程任務
- 連續執行的假象 : 執行序執行 I/O 任務時可以交出 CPU 資源，此時 I/O 在執行，CPU 也被其他執行緒使用，所以看來有多任務在執行
- 問題 : 3 個執行緒已建立，期望執行緒 1, 2, 3 之間順序執行，如何搭配 mutex 使其可以達成
TSO (total store order) $\to$ [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
x86/Intel 64 的 memory-ordering 規則是「軟體可見行為」的規格，不等於硬體內部真的完全禁止 OoOE；Intel 文件明確說硬體可以做任何最佳化，只要不違反可見順序，甚至同一個 memory access 可執行多次，最後可見結果正確即可。TSO 的簡化模型是每個處理器核有 FIFO store buffer，load 可繞過自己較早、不同位址的 store，因此表現出 Store→Load relaxation；但 Load→Load、Load→Store、Store→Store 在架構可見層面仍維持順序。Intel 的最佳化手冊也說，處理器核允許 load/store speculative、out-of-order issue，但即將執行完畢時要保證資料正確並符合 Intel 64/IA-32 ordering rules。
machine clear 不是每個 load 在 retire 前都固定發起 bus snooping；比較準確地說，它是投機執行或 memory disambiguation 判斷失敗後的回復機制。Intel performance event 文件列出 MACHINE_CLEARS.MEMORY_ORDERING 的來源包含 memory disambiguation、external snoop，以及 cross-SMT stores hitting load buffers；若頻繁發生，確實會有顯著效能衝擊。TSO 的硬體成本存在，包括 store buffer、load buffer、store-to-load forwarding、memory disambiguation、coherence snoop、false sharing 放大的 invalidation traffic，以及錯誤投機後的 pipeline clear。硬體平常積極 speculate 執行，只有在偵測到可能破壞架構記憶體模型時才 rollback。
Apple: [Accelerating the performance of Rosetta](https://developer.apple.com/documentation/virtualization/accelerating-the-performance-of-rosetta)
ROB
## chuang0720
當每個 CPU 有自己的 runqueue 時，該如何決定誰要執行?
每個核的 runqueue 會對分配到的可執行任務追蹤並排程，而主動負載平衡會讓主排程器定期檢查整個系統的負載分佈，並在必要時重新分配任務。
核心引入 PELT (PerEntity Load Tracking)來追蹤任務所造成的負載
## CHEN-YOU-0331
問題一：Linux 現代排程器如何挑選 per-CPU 的最佳 Task？
自 Linux v6.6 (2023 年底發布) 起，預設排程器已替換為 EEVDF (Earliest Eligible Virtual Deadline First)。
CFS 雖然公平，但在處理延遲敏感 (Latency-sensitive) 任務時表現不佳。EEVDF 引入了「截止時間 (Deadline)」的概念來解決這個問題。
* Eligibility (資格審查 - 延遲計算)： 系統會計算一個任務的 Lag (落後時間)，即「任務理應獲得的 CPU 時間」減去「實際獲得的 CPU 時間」。只有當 $Lag \ge 0$ 的任務，才會被標記為 Eligible (具備排程資格)，這確保了沒有任務可以超支其應得的時間。
* Virtual Deadline (虛擬截止時間)： 每個任務都會被賦予一個虛擬截止時間（與其所需的時間片大小有關）。
* 挑選最佳 Task： 在該 CPU 的 Runqueue 中，EEVDF 會在所有 具備資格 (Eligible) 的任務裡，挑選出 虛擬截止時間最早 (Earliest Virtual Deadline) 的任務來執行。
問題二：用 C 語言計算 $e^x - 1$ (不使用 math.h 與浮點數)
```c
#include <stdio.h>
#include <stdint.h>
#define SCALE 1000000LL // 保留 6 位小數點的精確度
#define MAX_ITER 20 // 最大迭代次數 (x 越大，需要的次數越多)
/*
* 計算 e^x - 1 (x 為整數)
* 回傳值為乘以 SCALE 後的定點數
*/
int64_t exp_minus_one_int(int x) {
// 雖然 x 是整數，但展開的結果會有小數
// 所以我們在第一項就把整數 x 轉換為定點數格式 (x * SCALE)
int64_t term = (int64_t)x * SCALE;
int64_t sum = 0;
int n = 1;
// 當項次不為 0，且未達到最大迭代次數時繼續累加
while (term != 0 && n < MAX_ITER) {
sum += term;
n++;
// 核心簡化：因為 x 是純整數，直接乘 x 再除以 n 即可。
// 不需要像之前那樣再除以 SCALE 來校正！
term = (term * x) / n;
}
return sum;
}
void print_fixed(int64_t val) {
int64_t int_part = val / SCALE;
int64_t frac_part = val % SCALE;
if (frac_part < 0) {
frac_part = -frac_part;
if (int_part == 0) printf("-");
}
printf("%lld.%06lld\n", (long long)int_part, (long long)frac_part);
}
int main() {
// 測試案例: 輸入純整數 x = 1 (即 e^1 - 1)
int x1 = 1;
printf("計算 e^1 - 1: ");
print_fixed(exp_minus_one_int(x1));
// 測試案例: 輸入純整數 x = 2 (即 e^2 - 1)
int x2 = 2;
printf("計算 e^2 - 1: ");
print_fixed(exp_minus_one_int(x2));
return 0;
}
```
:::danger
缺乏對於降低誤差的探討，詳閱 [歐拉數 e: 描述連續變化的基石](https://hackmd.io/@sysprog/euler-number)
:::
* 定點數運算原理
因為不能用浮點數，我們將所有的數值放大一個常數倍數 (例如 SCALE = 1,000,000，代表保留 6 位小數)。
* 實數 $1.0$ 在程式中表示為整數 1000000。
* 兩個定點數相乘 $A \times B$ 在程式碼中必須寫成 (A * B) / SCALE，否則小數點會位移。
為什麼這段程式能用「整數」算出「小數」？
我們通常習慣用浮點數 (float) 來算 $0.5$、$1.718$ 這種小數。但在沒有浮點數的情況下，這個程式使用了「放大單位」的魔法。
舉個生活化的例子：
假設你要平分 $1.5$ 元。
如果系統規定只能用整數，你不能寫 $1.5 \div 2$。
但如果你把單位從「元」換成「分」呢？
$1.5$ 元 = $150$ 分。
$150 \div 2 = 75$ 分。
用純整數算出了 $75$，這個 $75$ 其實就代表了 $0.75$ 元！
這支程式的原理完全一樣：
程式裡的 SCALE = 1000000，就是把所有的數字都放大一百萬倍，以此來保留 6 位小數點的精確度。
真實世界的 $1.0$，在程式裡被表示為 1000000。
:::danger
缺乏 ULP 的討論
:::
## ascodeasice
> 承上一位的計算 $e^x-1$，在單精度如何應用微積分的中央極限定理、夾擠定理估算最大值
TODO: 分析誤差
---
## 校友交流
> [ReiFu Zhang](https://www.linkedin.com/in/chiwawa/)
> 彰師資管倒數第三名 $\to$ 成大工科所 $\to$ Mediatek
* 大學時因興趣開始探索 FPGA
* 碩一時開始跟 jserv 做 FPGA 相關專案
* 血統不好怎麼辦？專攻有利基的領域如 [HPC](https://en.wikipedia.org/wiki/High-performance_computing) $\to$ [以 HPC 開發者的視角，搭配 RISC-V 來理解現代處理器架構](https://hackmd.io/2BD1rr8YTo6MfVGdxnDh9A)
* 畢業前一年開始面試(六月開始），一個禮拜面兩次
* 發哥一面 二面 實體 處長找你談 準備 3 頁履歷（英文） 濃縮過往做的專案內容。會派題目，給兩個禮拜做準備，問裡面的技術細節
CPU/HW architecture
ASIC
天璣
CPU 從 Arm 授權 -> 公司
GPU (Mali) 從 Arm 授權 -> 公司 (RTL)
ARM Cortex-X2 大核 x1
3× Cortex-A710 @ 2.85 GHz
4× Cortex-A510 @ 1.8 GHz
大/中/小核的組合涉及到應用場景
gaming/AI
I/O-bound, CPU-bound
performance modeling
-> CA, OS, digital IC / RTL
CA: performance, CPU 的組成 (cache, uarch [microarch], memory, Network on Chip [NoC])
> https://fuse.wikichip.org/news/5006/the-mesh-network-for-next-generation-neoverse-chips/
Q: 現代 SoC 的 NoC 架構要留意哪些議題？
Q: 功耗與面積限制決定 PPA，技術挑戰是什麼？
Q: 如何評估 Linux 在最終處理器的表現？
PPA
https://old.chipsandcheese.com/2025/12/31/inside-nvidia-gb10s-memory-subsystem-from-the-cpu-side/
https://github.com/rigtorp/c2clat
https://developer.arm.com/Processors/CoreLink%20CMN-600
NoC (Network-on-Chip)拓撲與延遲 ==> 最佳路徑
cadence palladium
業界普遍對新人不友善，但善用 AI 的新人仍有機會
Let AI model generates testbench (TB)
CPU: I/O , memory bound, edge cases, benchmarking
ALU spec -> RTL
不要外包思考: make decisions by yourself!
GEMM
人掌握 spec
formalized prompts
學得精
shared L2 -> dedicated L2 cache
refine cache microarchitecture
思考 why (motivation/consideration)，先於真的進行
DE: develop RTL, 不能只看 PPA, prototyping for system integration
DMIPS speedup
JD (job description): 找夠廣的題目
---
## keep90ing
vruntime (virtual runtime)
CFS 的 weight function
PELT
Linux task_struct: tgid vs. pid
getpid vs. gettid
PID 重用攻擊
container_of
---
concurrency: C11 atomics 有幾種 memory order?
consume, acquire, release
適用場景？
acquire vs. obtain vs. get
ownership
---
## kevinjone25
sched_prio_to_weight 為何有 40 個單元？
* 在 nice 的 man page 裡有提及 nice value range 是從 -20 - +19，再根據 man page sched (7) 的內容，是現代 Linux 系統中的範圍是 -20 - +19，早期的 Linux Kernel (2.0 以前) 是 -inf - +15 的 (根據 §POSIX.1-2008的 NZERO 所訂定)
[sched (7)](https://man7.org/linux/man-pages/man7/sched.7.html)
CFS 的 fairness
Linux: linked list
https://www.kernel.org/doc/html/v4.14/core-api/kernel-api.html
找出第 k 大的節點 (透過 List Sort API 寫出，不能排序)
O(n)
list_sort 空間複雜度
https://hackmd.io/@sysprog/it-vocabulary
---
## [panzhipop](https://github.com/panzhipop)
### Q1. vruntime (virtual runtime)
根據 CPU book P. 87， vruntime 指 a clock that measures how much CPU time a task `has consumed`, normalized by its priority. The key insight: if we always run the task with the smallest virtual runtime, we maintain fairness over time. 因為每次都是先執行最小的 vruntime ，變向達到了公平分配 CPU time 的目的。
### Q2. O(1)
根據 CPU book P.86，明確指出 O(1) 排程器的四大缺點 : Heuristic failures 、 Gaming the system 、 Unpredictable behavior 、 Starvation risks。
在 CFS 排程器中，採用公平分配 CPU time 的想法，去避免 O(1) 中 Heuristic failures 一直猜錯造成的成本。
### Q3. the ways to calcuate / algorithm
### Q5. fairness
根據 CPU book P. 41，fairness 意思為 the ability to give each process the same timeslices of the CPU。
根據 CPU book P.86 詳細解釋 fairness。在理想多工的 CPU 中，假設 CPU 可以真正地展現 parallel 的性質。舉例來說， CPU 現在有 n 個 task ， 則每個 task 可以獲得連續 $\frac{1} {n}$ 的使用時間 (proportional share of CPU time)。
### Q6. RT prio (為什麽有 100 個)
### Q7. normal prio (nice)? 40?
### Q8. 為什麽是這個公式 $\frac{1024} {1.25 ^ {nice}}$
```c
/*
* Nice levels are multiplicative, with a gentle 10% change for every
* nice level changed. I.e. when a CPU-bound task goes from nice 0 to
* nice 1, it will get ~10% less CPU time than another CPU-bound task
* that remained on nice 0.
*
* The "10% effect" is relative and cumulative: from _any_ nice level,
* if you go up 1 level, it's -10% CPU usage, if you go down 1 level
* it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
* If a task goes up by ~10% and another task goes down by ~10% then
* the relative distance between them is ~25%.)
*/
static const int 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,
};
```
在 nice 值轉換到 weight 的公式中，因為相鄰 weight 的比值約為 1.25 倍。所以該公式以零為基準，即 nice 0 的權重 1024。當 nice 值往負數方向前進，$1024* 1.25^{abs(nice)}$，權重會變大；當 nice 值往正前進，$\frac{1024} {1.25^{abs(nice)}}$，權重會變小。
---
## Kai5088
```c
/* File include/linux/kernel.h */
#define container_of(ptr, type, member) \
({ \
void *__mptr = (void *)(ptr); \
((type *)(__mptr - offsetof(type, member))); \
})
```
是否存在 UB?
* 依 C99 §6.5.6 Additive operators，加減法的指標算術只對「指向完整物件型別(complete object type)」的指標有定義。而 C99 §6.2.5指出:The void type comprises an empty set of values; it is an incomplete type that cannot be completed.所以 void * 是指向 incomplete type 的指標,對它做 +/- 在標準 C 中是 constraint violation
https://man7.org/linux/man-pages/man3/pthread_detach.3.html
https://man7.org/linux/man-pages/man3/pthread_join.3.html
```
main
+
+---- T1 * pthread_join
+
+---- T2 *
+
+----- T3 * pthread_detach
```
pthread_join
* 依據 man7.org 敘述，這個函式會等待由 thread 參數所指定的執行緒終止;若該執行緒已經終止,pthread_join() 會立即返回,而且由 thread 所指定的執行緒必須是 joinable 的,曾經被 pthread_detach 分離過、或建立時就已被設為 detached 的執行緒,不能拿來 join。pthread_join有三個功能，同步點(等待目標執行緒終止)、結果通道(取回 pthread_exit 的回傳值或 PTHREAD_CANCELED)、以及資源回收機制(釋放目標執行緒在 pthread 實作中佔用的內部資源,避免 zombie thread)。正確的多執行緒程式設計中,每一條 joinable 執行緒在程式結束前都應恰好被 join 一次,否則就應在建立時或建立後盡早 detach。
https://hackmd.io/@sysprog/unix-fork-exec
1960s fork-join
* 依據〈UNIX 作業系統 fork/exec 系統呼叫的前世今生〉，1960 年代的 fork-join 並不是一個作業系統的具體機制,而是一個比 UNIX 早了整整六年提出的並行處理(concurrent processing)抽象模型。其意義不在於它是不是某個具體作業系統的某條系統呼叫,而在於它確立了並行運算最根本的兩個動作「分岔出獨立執行流」與「等待所有分支匯流」。Conway 把這對動作從多處理器硬體中抽象出來,讓人們得以脫離具體機器去談並行;Project Genie / BTSS 把它落實為可呼叫的原語;UNIX 則在 1969 年把它精簡為一個「無參數、雙回傳值、子行程完整繼承親代狀態」的 fork 系統呼叫,並用 exec、wait、exit 把整個生命週期補齊。現在C程式裡寫的 pthread_join 是由當時join而來。
寫程式測試觀察
* https://gist.github.com/Kai5088/b58df62df05da9de5e546eb71b99f2c1
此程式使用五個案例來測試pthread_join和detach:
1. 正常 join:pthread_create 之後 threads=2,worker 印出 pthread_exit(0xcafe0001) 後 1 ms,main thread 的 pthread_join 解除阻塞並收到完全相同的 retval,thread 數立刻回到 1。這驗證了 man page 兩件事:join 阻塞等待目標終止,以及 retval 就是目標 pthread_exit 傳出的值。
2. joinable 但不 join:創出 3 條後 threads=4,1 秒後 3 條都 pthread_exit 完畢,但你會看到 threads 並沒有立刻乾淨地降回 1——這就是 man page 警告的 zombie thread,雖然執行緒邏輯已結束,核心仍保留 task_struct 等待親代 join。情境結尾我補做 pthread_join 收尾,thread 數才回到基線。
3. detach:pthread_detach 回傳 0 表示成功,接著我故意對它 pthread_join 看會發生什麼——回傳 EINVAL (22) = "Invalid argument",印證 man page 的 EINVAL: thread is not a joinable thread。worker 在 5 秒處自然結束,thread 數自動回到 1,不需要任何手動回收。
4. 重複 join (UB):第一次 join 拿到 retval 0xcafe00c8;第二次對同一個 pthread_t 再 join,在我的 glibc 上得到 ESRCH (3) = "No such process"——但 man page 寫得很清楚這是 undefined behavior,意思是「換一台機器、換一個 libc、換一個版本,結果可能完全不一樣」,所以這個回傳值不能依賴,只是讓你看到「實作上 glibc 怎麼處理它」。
5. join 自己:回傳 EDEADLK (35) = "Resource deadlock avoided",完全對應 man page 的 EDEADLK: ... or thread specifies the calling thread。注意這個錯誤碼字面意思是「死結避免」——因為若真讓你 join 自己,呼叫端就會永久阻塞等自己終止,核心直接幫你擋掉。
## tobiichi3227
重新閱讀 https://hackmd.io/@sysprog/linux-process
跟著作實驗
設計實驗在執行時期，判定 process vs. thread
task_struct
bpftrace
Linux 核心用 TASK_RUNNING 來表示 ready 和 running 的狀態
透過實驗來確認陳述
Google Drive
Gist
Clipboard
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
