面試陷阱題 (Exam Traps)

#csapp #dashboard #exam-traps

Purpose

本檔收集 CSAPP 3e 全書各章的常見錯誤與易混淆點:面試與考試中最容易誘答的陷阱、其易錯原因與正確答案。每個陷阱均為摺疊 callout,建議先自答再展開對照;弱點章節可搭配學習地圖的 Weak Areas 追蹤。

計算機系統漫遊 (A Tour of Computer Systems)

Trap: gcc 不是狹義的 compiler

考題問「哪個程式把 hello.i 翻成 hello.s」,很多人答 gcc。
gcc 是 compiler driver,依序驅動 cpp/cc1/as/ld 四個階段;狹義的 compiler 是 cc1(.i → .s)。
正確答案:cc1;另記 .c/.i/.s 是 text file,.o 與 executable 是 binary,轉 binary 的階段是 Assembly (as)。
資訊表示與程式翻譯

Trap: 對 α 部分加速 k 倍,整體 speedup 遠小於 k

α=0.6 的部分加速 3 倍,整體只有 1.67×;考題常誘導直接答 k。
直覺忽略了未改善部分仍佔固定時間。
必須代入 Amdahl 公式;且 k = ∞ 時上限是 1/(1−α)(α=0.6 → 只有 2.5×)。
Amdahl 定律與並行主題

Trap: concurrency 與 parallelism 混為一談

「單核上兩個交錯執行的行程是 concurrent 嗎?」答「不是」就錯了。
concurrent 只看兩流的時間區間是否重疊,與核心數無關;uniprocessor 靠 context switching 也能並行。
parallel 是 concurrent 的真子集,才要求同時跑在不同 core / 機器上。
Amdahl 定律與並行主題

Trap: 把 kernel 當成一個獨立 process

kernel 不是單獨的 process,而是常駐記憶體、被系統用來管理所有 process 的 code 與 data structures 集合。
因為 kernel「一直在跑」的直覺,容易誤想成背景行程。
應用程式以 system call 將控制權轉給 kernel;kernel 永遠「代表某個行程」執行。
作業系統抽象與網路

Trap: 三大抽象的涵蓋範圍配對錯誤

process、virtual memory、files 各抽象了哪些硬體?考題常考反向配對。
三者範圍層層縮小,容易記反。
process 最廣(processor + main memory + I/O devices)、virtual memory 次之(main memory + disk)、files 最小(僅 I/O devices)。
作業系統抽象與網路

Trap: context 內容漏答 main memory

問「context 包含什麼」時只答 PC 與暫存器。
記憶體內容不像暫存器那樣直觀屬於「CPU 狀態」,常被漏掉。
context = PC 目前值 + register file + main memory 內容三項。
作業系統抽象與網路

Trap: multi-core cache 共用層級與 hyperthreading 複製範圍

誤以為 L1/L2 由所有核共用,或 hyperthreading 複製整顆 CPU。
L1、L2 是每核私有(L1 還分 i-cache/d-cache),只有 L3 由所有核共用;hyperthreading 只複製 PC、register file 等部分硬體,浮點單元仍是單份。
且多處理器不會自動加速單一程式——要變快必須寫成可平行的多執行緒。
Amdahl 定律與並行主題

Trap: 下一條指令不一定在相鄰位址

CPU 更新 PC 指向下一條指令,但該指令不一定與剛執行的指令在記憶體中連續(如 jump)。
把「循序執行」誤解成「循序位址」。
另記:載入 hello 時 code/data 走 DMA 不經 CPU;cache 是 SRAM、主記憶體是 DRAM。
硬體組織與程式執行

資訊的表示與處理 (Representing and Manipulating Information)

Trap: signed/unsigned 混合比較的隱式轉換

-1 < 0U 為 false;2147483647U > -2147483647-1 也是 false。
一個運算元為 unsigned 時,signed 運算元被隱式轉為 unsigned 再比較,-1 變成 UMax。
判斷「恆真」題先檢查是否有 unsigned 運算元;避免混用 signed/unsigned 比較。
整數表示

Trap: unsigned 迴圈條件 i <= length-1 造成越界

length 為 unsigned 且等於 0 時,length−1 wrap 成 UMax,條件永真。
size_t 相減永非負:strlen(s)-strlen(t) > 0 除相等外永遠成立。
改寫為 i < length;比較長度用 strlen(s) > strlen(t)。
整數表示

Trap: TMin 的三個特例

C 中不能直接寫 -2147483648(是「對 2147483648 取負」,常數超出 int 正範圍);limits.h 用 (-INT_MAX - 1)。
TMin 取負仍是 TMin(無正對應),故 tadd_ok(x,-y) 在 y=TMin 時出錯、-x <= 0 在 x=TMin 仍成立。
涉及取負與絕對值的判斷題,一律先驗 x=TMin。
整數算術

Trap: 用 (x+y)-x == y 檢查加法溢位永遠失敗

Two's-complement 加法構成 abelian group,溢位效果在減回時完全抵銷,該檢查對所有輸入回傳 1。
直覺以為「溢位後值變了,減回來對不上」。
正解檢查符號模式:x>0 && y>0 && s<=0(正溢位)等;對比考點:乘法反而可以用 p/x == y 驗證。
整數算術

Trap: 負數算術右移不等於 C 的除法

arithmetic right shift 向下捨入(floor),C 整數除法向零捨入;−12340 >> 4 = −772,但 −12340/16 = −771。
兩者只在整除或非負時相同,常被當成完全等價。
負數除以 2^k 須先加 bias:(x + (1<<k) - 1) >> k。
整數算術

Trap: 移位量 ≥ w 與移位優先權

k ≥ w 時 C 為未定義行為;許多機器實際取 k mod w,但不可依賴。
1 << 2 + 3 << 4 解析為 (1 << (2+3)) << 4 = 512 而非 52——移位優先權低於加減法。
移位量務必 < w;不確定優先權就加括號。另記 signed 右移用算術或邏輯移位也是 C 未定義(實務上皆算術)。
資訊儲存與位元運算

Trap: Denormalized 的 E 是 1 − Bias 而非 −Bias

exp 全 0 時 E = 1 − Bias 且 M = f(無 implied leading 1)。
誤用 −Bias 或誤加 leading 1 是解碼題最常見錯誤。
1 − Bias 的設計使最大 denorm 與最小 norm 平滑銜接;round-to-even 也只在真正 halfway(捨去部分為 100...0)時才取偶。
浮點數

Trap: 浮點運算不可套用實數代數律,轉換也不保值

(3.14+1e10)−1e10 = 0.0 但 3.14+(1e10−1e10) = 3.14;加乘不可結合、乘法不可分配。
x == (int)(float) x 不恆真(float 只有 24 bits 有效位),x == (int)(double) x 對 32-bit int 恆真;float/double → int 溢位在 Intel 產生 TMin,(int)+1e10 = −2147483648。
判斷「恆真」題逐一驗證極端值(大整數、∞、NaN、±0.0);NaN 連 x == x 都是 false。
浮點數

程式的機器層級表示 (Machine-Level Representation of Programs)

Trap: ATT 格式非交換運算的運算元順序反著讀

subq %rax,%rdx 是 %rdx = %rdx − %rax;cmpq %rsi,%rdi 依 %rdi−%rsi 設旗標。
ATT 是 src, dst(Intel 相反為 dst, src),sub/cmp/sar 這類非交換運算最易讀反方向。
口訣:從第二個運算元減去第一個;cmp 判斷的是「第二運算元相對第一運算元」的關係。
資料搬移與算術運算

Trap: movl 會清高 4 bytes,movb/movw 不會

任何產生 32-bit 結果寫入暫存器的指令(movl、andl、xorl 等)把高 4 bytes 設為 0;1/2-byte 指令保留其餘 bytes。
判斷 %rax 最終值的追蹤題最容易在此出錯。
另記:mov 與 binary 運算禁止兩個 memory operand,必須先 load 進暫存器。
資料搬移與算術運算

Trap: leaq 只算位址、不讀記憶體

leaq 7(%rdx,%rdx,4),%rax 只是計算 5x+7 存入 %rax,完全不做記憶體存取。
把它當成 load 指令解讀會答錯所有反推 C 程式碼的題目。
leaq 對應 C 的 & 取址(8-byte 結果);帶括號的 mov 才對應 * 解參考。
陣列與異質資料結構

Trap: return address 是 call 的下一條指令位址

push 上 stack 的是緊接在 call 之後那條指令的位址,不是 call 本身或被呼叫函式的位址。
追蹤題(PP 3.32)最常錯;且 return address 算在 caller 的 stack frame 內,不是 callee 的。
另記:caller 放在 0(%rsp)/8(%rsp) 的 stack 引數,call 之後在 callee 端變成 8(%rsp)/16(%rsp)(差 8)。
程序與執行時堆疊

Trap: cmov 兩邊都會執行

return xp ? *xp : 0 若編成 cmov,即使 xp 為 NULL 也會先執行 movq (%rdi),%rax 造成 null pointer dereference。
conditional move 沒有短路語意,兩個分支的值都先算出來。
有副作用或可能出錯的條件式必須用分支版;PC-relative 跳轉目標 = 下一條指令位址 + offset。
控制流

Trap: 溢位覆寫 return address 的門檻算錯

char buf[8] 配 24 bytes 時,0–7 字元安全,9–23 只毀未用空間,要 24–31 字元才覆寫 return address。
誤以為超過宣告大小 8 就毀返回位址。
先看組語實際配置的 frame 大小再算偏移;canary 由 movq %fs:40 取得、返回前 xorq 比對。
緩衝區溢位與指標安全

Trap: struct 尾端 padding 與 Equation 3.1 的維度

struct {int i; int j; char c;} 總大小是 12 不是 9——必須向上取整到最大對齊需求 K 的倍數,否則陣列元素會違規。
&D[i][j] = xD + L*(C*i + j) 乘的是每列元素數 C,不是列數 R;逆向工程時縮放係數 ÷ L = 每列元素數。
算 struct 大小最後一步必做「補齊到 K 的倍數」;指標陣列元素一律 8 bytes,與所指型別無關。
陣列與異質資料結構

Trap: 浮點參數分開計數且 XMM 全部 caller-saved

double f(int x, double y, long z) 中 y 在 %xmm0(不是 %xmm1)、x 在 %edi、z 在 %rsi——整數與浮點各自獨立排序。
XMM 沒有任何 callee-saved 暫存器,跨呼叫保留浮點值只能存 stack;誤以為高編號 XMM 是 callee-saved。
另記 vsubsd S1,S2,D 是 D = S2 − S1;NaN 比較後 CF=ZF=PF=1,要用 ja/jb 系跳躍不能用 jg/jl。
浮點程式碼

處理器架構 (Processor Architecture)

Trap: 反解 Y86-64 byte 序列忘記 little-endian

8-byte 常數(V/D/Dest)在編碼中是 byte-reversed:cdab896745230100 → 0x000123456789abcd。
直接照抄 byte 順序解出錯誤的立即值/位址。
還原時務必反轉 byte 順序;另記 Y86-64 的 jXX/call 用 8-byte 絕對位址,不是 x86-64 的 PC-relative。
Y86-64 指令集架構

Trap: OPq 不能用 immediate/memory operand,且只有 OPq 設 CC

addq $8,%rdi 在 Y86-64 非法,須先 irmovq $8,%r8 再 addq;memory 值須先 mrmovq 載入。
ALU 每次運作都產生旗標訊號,但 set_cc 只在 icode==IOPQ 時為真——rrmovq、irmovq、pushq 等一律不改 CC。
迴圈若以 jne 開頭測試,進入前須先用 andq %rsi,%rsi 之類設定 CC。
循序 SEQ 實作

Trap: pushq %rsp 推舊值、popq %rsp 得記憶體值

valA 在 Decode 階段就讀好,%rsp 更新要到 clock 上升緣,所以 pushq %rsp 推入未遞減的舊值;popq %rsp 因 M port 優先於 E port,最終 %rsp = 記憶體讀出的 valM。
直覺以為 push 先減 8 再推、pop 的加 8 生效。
記「No reading back」原則:pushq 寫入位址用遞減後的 valE,popq 讀取位址用未遞增的 valA。
循序 SEQ 實作

Trap: 管線化提高 throughput 但 latency 反而略增

3-stage 管線化後 latency 從 320 ps 變 360 ps(每 stage 多付一次 pipeline register 延遲)。
誤以為管線化「什麼都變快」;latency = 1/throughput 只在未管線化系統成立。
時脈週期 = 最慢 stage 延遲 + register 延遲(不是平均值);stage 加倍 throughput 也不會加倍,極限受 register overhead 與最大不可分割區塊限制。
管線化原理

Trap: 轉發優先序寫反

必須 execute > memory > write-back:最早的 stage 持有程式順序上最新的指令。
順序顛倒時連續兩條寫同一暫存器的指令會轉發到舊值。
同 stage 內 valM 須優先於 valE(只影響 popq %rsp);且 forwarding 解不了 load/use hazard,必須 load interlock stall 1 cycle。
PIPE 管線實作與冒險

Trap: 誤抓指令的例外不能立即生效

分支預測錯而抓到的指令(如 SINS)在 decode 偵測到例外時,不能馬上報例外。
stat 隨指令走到 write-back 才生效,指令被 squash 時例外一併消失。
偵測例外要用小寫 m_stat(含 memory stage 剛發生的 dmem_error),用 M_stat 會漏;例外後方的 OPq 須以 bubble 禁止改 CC 與寫記憶體。
PIPE 管線實作與冒險

Trap: HCL case expression 不要求條件互斥

與 C 的 switch 不同,HCL case 依序求值、取第一個為 1 的 case,後面的選擇運算式可以化簡。
用 C 的心智模型會誤以為每條件必須完整互斥。
另記 HCL 用 &&/||/!(不是 &/|/~);組合邏輯沒有短路求值;register file 讀取像組合邏輯、寫入由 clock 上升緣控制。
邏輯設計與 HCL

程式效能最佳化 (Optimizing Program Performance)

Trap: 把「看似等價」的改寫當成編譯器會自動做

twiddle1→twiddle2、func1→func2 都不是 safe optimization:aliasing(xp==yp 時 ×4 vs ×3)與 side effect(counter++)使行為不同。
直覺認為「數學上等價編譯器就會做」。
編譯器一律假設最壞情況;memory aliasing 與函式副作用是兩大 optimization blocker。
最佳化編譯器與其限制

Trap: 迴圈測試條件中的 strlen 每迭代都執行

for (i=0; i<strlen(s); i++) 使 strlen 被呼叫 n 次,總時間 O(n²)。
以為編譯器會把「明顯不變」的呼叫提出迴圈——但它無法證明無副作用。
手動把 strlen 移到迴圈外;判斷訊號:輸入加倍、時間變 4 倍即 quadratic。
最佳化編譯器與其限制

Trap: k × 1 迴圈展開不能突破 latency bound

單一累加器造成跨迭代串列相依,展開後 critical path 長度不變。
「展開 = 變快」的直覺只對 loop overhead 受限的情況成立。
要突破 latency bound 需多重累加器(k × k)或 reassociation(k × 1a);達 throughput bound 需 k ≥ C × L(double * 需 k ≥ 10,不是 2 就夠)。
迴圈展開與平行度

Trap: 浮點 reassociation/多重累加器可能改變結果

浮點加乘不可結合:偶數索引極大、奇數索引接近 0 時,分組累加可能 overflow/underflow,即使循序計算正常。
這正是編譯器不自動對浮點做這些轉換的原因。
整數(二補數)即使 overflow 也保證結果相同,可放心展開;浮點需自行確認可接受誤差。
迴圈展開與平行度

Trap: 展開因子越大越好?register spilling 反噬

平行度 P 超過可用暫存器數(16 整數 + 16 YMM)時,累加器被 spill 到 stack,20 × 20 的 int + CPE 從 0.55 退化到 0.83。
以為展開沒有上限成本。
展開到逼近 throughput bound 即止。
限制因素與記憶體效能

Trap: 運算次數少不等於更快(Horner 法反而慢)

Horner 法只做 n 次乘法卻比 2n 次運算的直接法慢(CPE 8.00 vs 5.00)。
只數運算次數、忽略相依鏈:Horner 跨迭代鏈是 mul+add 串聯,直接法只有單一 mul,多出的乘法與相依鏈平行執行不佔 critical path。
分析效能看 critical path(latency bound)與功能單元(throughput bound),不是運算總數。
現代處理器運作

Trap: throughput bound 不能只看算術單元數

整數加法有 4 個功能單元,直覺 CPE 下界 0.25,但每元素須經記憶體讀入且僅 2 個 load unit → 實際 bound 0.50。
忽略 load/store 頻寬同樣構成上限。
另記:store 本身可 fully pipeline(CPE 1.0),慢的是 load 位址與 pending store 相同時的 write/read dependency。
現代處理器運作

Trap: 可預測分支幾乎免費,不需消除所有檢查

loop-closing branch 只在最後一輪錯一次;恆成立的 bounds check 可與運算平行、不進 critical path。
「消除所有分支就變快」是誤解;只有依資料任意特性的不可預測分支需改寫成 cmov 形式。
且 cmov 不是萬靈丹:兩邊都被求值,有副作用或可能出錯時編譯器不會用;優化必須實驗驗證(遞迴改迭代也可能反而變慢)。
限制因素與記憶體效能

記憶體階層 (The Memory Hierarchy)

Trap: 磁碟容量與旋轉延遲的兩個固定失分點

題目給 platters 數必須乘 2 得 surfaces;平均旋轉延遲是整圈時間的一半(1/2 × 60/RPM)。
漏乘 2 或套整圈時間是計算題最常見錯誤。
磁碟 GB 用 10^9(DRAM/SRAM 才用 2 的冪);循序讀只付一次 seek + rotation,隨機讀每塊都要付。
儲存技術

Trap: SSD 讀寫單位與抹除單位不同

讀寫以 page 為單位,抹除以 block(32–128 pages)為單位;page 只能在整個 block 抹除後寫一次。
隨機寫慢是因抹除耗 ~1 ms 加上須先複製同 block 的有用 pages,不是 flash 讀取本身慢。
問「SSD 為何隨機寫慢」時答對機制而非「flash 就是慢」。
儲存技術

Trap: 交換迴圈順序不是無害小改動

sumarrayrows 與 sumarraycols 結果相同,但 row-major 下後者從 stride-1 變 stride-N,空間區域性劇烈惡化。
「結果一樣所以效能一樣」的直覺錯誤。
判斷準則:最右邊的索引必須在最內層迴圈變動最快;scalar 變數只問 temporal locality,沒有空間區域性議題。
區域性與記憶體階層

Trap: conflict miss 不是容量不足

cache 容量足以容納所有參考資料,但限制性 placement policy 使它們映射到同一 set 而反覆互相逐出(thrashing),即使其他 set 全空。
與 working set > cache 的 capacity miss 成因不同,考試常混淆。
典型情境:2 的冪次大小陣列交替存取(dotprod 的 x[i]、y[i]);解法是尾端 padding。
區域性與記憶體階層

Trap: valid=1 就以為 hit,容量 C 誤含 tag 開銷

命中需 valid bit 設定「且」tag 相符兩條件同時成立;valid=1 但 tag 不符仍是 miss。
C = S × E × B 只計資料 block,tag/valid/dirty bits 都是額外開銷不計入容量。
位址切法由低到高:block offset(b)→ set index(s)→ tag(t);set index 在中間不是高位。
快取記憶體

Trap: 以為 B 或 E 越大效能越好

B 變大:C 固定時 line 數減少,傷時間局部性且 miss penalty 上升;E 變大:減少 conflict miss 但 hit time 與 miss penalty 都可能上升。
「加大就是好」忽略了取捨,所以 L1 傳統上關聯度較低、下層較高。
write 策略典型配對:write-through + no-write-allocate;write-back + write-allocate(需 dirty bit)。
快取記憶體

Trap: 加大快取不一定提升 hit rate

stride-1 掃描只剩 cold miss(hit rate 75%),快取再大 hit rate 都不變——cold miss 不可避免。
只有存在 capacity/conflict miss 時加大快取才有效。
同理 column 掃描不一定全 miss:整個陣列放得進快取時 miss rate 與 row 掃描相同;答題前先比較 working set 與快取容量。
快取友善程式碼與記憶體山

Trap: miss rate 才是效能預測指標,不是存取總數

矩陣乘法 class BC 每迭代比 class AB 多一次記憶體操作,但 miss 只有 0.5 vs 1.25,實測反而快得多。
用 load/store 數量直接推效能會答反。
比較迴圈順序版本時算 per-iteration miss;另記 block 是資料封包、line 是含 valid/tag 的容器、set 是 line 的集合。
快取友善程式碼與記憶體山

連結 (Linking)

Trap: 初始化為 0 的全域變數放 .bss,未初始化的放 COMMON

int x = 0; 被視同未初始化放 .bss;int x = 9; 才放 .data;「未初始化全域變數」在現代 gcc 放 COMMON 偽節。
原因:compiler 遇 weak 符號無法預測 linker 選哪個定義,把決定權推遲給 linker(COMMON);初始化為 0 者是 strong、必唯一,可放心放 .bss。
另記 ABS/UNDEF/COMMON 偽節只在 relocatable 檔存在,executable 沒有。
靜態連結與目的檔

Trap: Rule 2/3 的重複符號 linker 悄悄選定、不報錯

int x = 15213; vs int x; → 選 strong 且無任何訊息;兩個 weak → 任選、不可預測;int x(strong)配 double x(weak)時寫 8-byte double 會覆寫相鄰變數。
症狀常在離錯誤點很遠的執行後期才顯現,極難除錯。
防禦:gcc -fno-common 讓多重定義直接報錯;只有多個 strong 定義(Rule 1)才是 link error。
符號解析與重定位

Trap: 靜態函式庫放在命令列前面會連結失敗

gcc -static ./libvector.a main2.c 失敗:掃到 archive 時未解析集合 U 是空的,不取任何 member,之後的 addvec 參照永遠無解。
linker 由左至右單趟掃描,不回頭。
函式庫一律放命令列尾端;循環相依可重複列出(libx.a liby.a libx.a);linker 只複製被參照到的 member。
符號解析與重定位

Trap: PC-relative 重定位以「下一條指令」為基準

call 執行時 PC 是緊接在 call 之後那條指令的位址;重定位公式 ADDR(symbol) + addend − refaddr 中 addend = −4 就是補償參照位址與 PC 的 4-byte 差。
用 call 指令本身位址計算會差 5 bytes。
驗證法:PC(下一指令位址)+ 重定位值 = 目標位址;R_X86_64_32 則直接填絕對位址。
符號解析與重定位

Trap: loading 並沒有真的複製檔案到記憶體

loader 只把 code/data segments 映射到可執行檔的 page-size 區塊,除 header 外載入時沒有任何磁碟到記憶體的資料複製。
「loader 把程式複製進記憶體」只是概念性說法。
複製延遲到 CPU 第一次觸及該頁時由 paging 搬入;entry point 是 _start(crt1.o),不是 main。
可執行檔載入與動態連結

Trap: GOT/PLT 與 lazy binding 的初始指向

函式用的 GOT entry 初始值指向對應 PLT entry 的「第二條指令」——第一次呼叫看似跳回原地,實為觸發 dynamic linker 解析並覆寫 GOT。
誤以為 GOT 一開始就存函式位址,或以為每次呼叫都經 dynamic linker。
GOT 在 data segment(8-byte 位址)、PLT 在 code segment(16-byte 程式碼);之後每次呼叫只多一條間接跳轉。不能用一般 relocation 是因為那會修改 code segment、違反 PIC。
可執行檔載入與動態連結

Trap: run-time wrapper 直接呼叫同名函式造成無限遞迴

LD_PRELOAD 的 malloc wrapper 裡直接寫 malloc(size) 會呼叫到自己。
wrapper 本身就叫 malloc,符號解析回到自己。
必須用 dlsym(RTLD_NEXT, "malloc") 取得 libc 真品;--wrap 方向:對 f 的參考 → wrap_f,對real_f 的參考 → f。
函式庫插入與目的檔工具

Trap: 三種插入機制的存取需求

compile-time 需要原始碼、link-time 需要 .o 檔、run-time 只需要可執行檔。
題目給定「只有 binary」時誤選 link-time。
只有 binary → LD_PRELOAD run-time 插入;另記 -Wl,--wrap,malloc 的逗號會被替換成空格。
函式庫插入與目的檔工具

例外控制流 (Exceptional Control Flow)

Trap: 四類例外的同步性與返回行為

只有 interrupt 是非同步(來自外部 I/O 裝置);trap/fault/abort 都是執行當前指令的同步結果。
interrupt/trap 返回 I_next;fault 可能返回 I_curr(重新執行 faulting instruction)否則 abort;page fault 返回 I_curr 而非 I_next,最易答錯。
另記:syscall 第 4 參數用 %r10 不是 %rcx;例外的返回位址與狀態壓在 kernel stack,不是 user stack。
例外

Trap: 沒有獨立的 kernel process

context switch 期間 kernel 不是自己的行程,永遠「代表某個行程」執行;切換中途只是代表的對象從 A 變成 B。
「kernel 在跑」的說法容易誤導成 kernel 是行程。
user → kernel mode 的唯一途徑是例外(interrupt、fault、trapping syscall);應用程式無法主動設 mode bit。
行程與上下文切換

Trap: fork 呼叫一次回傳兩次,execve 成功永不回傳

fork:子得 0、父得子的 PID;n 個連續 fork 產生 2^n 個行程。execve 覆寫位址空間但不建新行程——PID 不變、file descriptor 保留。
兩者的呼叫/回傳不對稱最常被混淆。
fork 後父子位址空間是「相同但獨立的副本」(改變數互不影響),但 file descriptor 共享同一 open file table entry;判斷輸出序列用 process graph 的 topological sort。
行程控制

Trap: 未回收的子行程變 zombie,長駐程式不能靠 init

行程終止後 kernel 保持其狀態直到被父 reap;zombie 雖不執行仍佔記憶體。
以為「行程結束資源就自動釋放」。
shell/server 必須自行回收;父先死時 init(PID 1)才收養代收。waitpid 回 −1 的兩種 errno:無子 ECHILD、被 signal 中斷 EINTR。
行程控制

Trap: 訊號不排隊,不能用來計數事件

pending bit vector 每型只有 1 bit;handler 執行期間同型訊號被隱式阻擋,重複送達者直接丟棄。
送 N 個同型訊號,handler 可能只收到少於 N 個;SIGCHLD handler 只呼叫一次 waitpid 會殘留 zombie。
handler 必須 while (waitpid(-1, NULL, WNOHANG) > 0) 迴圈盡量回收;pending 訊號只表示「至少來過一個」。
訊號

Trap: handler 內用 printf 與非原子的旗標操作

printf/sprintf/malloc/exit 皆非 async-signal-safe,handler 內只能用 write / Sio 套件。
共享旗標要宣告 volatile sig_atomic_t,但其原子性只保證單次讀或寫——flag++ 不是原子操作。
另記 SIGKILL 與 SIGSTOP 不能被 catch/ignore;Ctrl+C/Ctrl+Z 送給前景 process group 的每個 process。
訊號

Trap: while (!pid) pause(); 有 race,正解是 sigsuspend

訊號若在 while 判斷後、pause 前被接收,pause 將永遠沉睡;sleep(1) 版正確但太慢。
sigsuspend(&mask) 是「block + pause + restore」三步的原子版本,消除中間插入訊號的 race。
同類 race:fork 前須先阻擋 SIGCHLD、addjob 後才解除,否則 deletejob 可能先於 addjob;子行程繼承 blocked set,execve 前要自行解除。
訊號

Trap: setjmp 呼叫一次、回傳多次;回傳值不可指定給變數

setjmp 初次回 0,之後每次對應的 longjmp 都讓它再回傳一次(非零 retval);longjmp 本身永不回傳。
rc = setjmp(env); 是錯誤寫法,回傳值只能用在 switch 或條件測試。
longjmp 跳過中間函式的釋放程式碼會造成 memory leak;signal handler 內要用 sigsetjmp/siglongjmp(額外保存 signal context),且 handler 必須在 sigsetjmp 之後才安裝以避免 race。
非區域跳轉

虛擬記憶體 (Virtual Memory)

Trap: page fault handler 返回後重新執行原指令

fault 類例外的語意是 re-execute faulting instruction,不是接續下一條;該次存取變成 hit。
與 interrupt/trap 返回 I_next 混淆。
PTE 數量公式 #PTE = N/P = 2^(n−p);valid=0 且位址 null → Unallocated、非 null → Uncached。
位址空間與 VM 快取機制

Trap: DRAM cache 的組織完全由巨大 miss 成本驅動

fully associative + write-back + 大頁(4 KB–2 MB)+ OS 軟體替換策略——與 SRAM cache 的設計全然不同。
用 L1/L2 的 set-associative、write-through 直覺回答會錯。
原因:miss 由 disk 服務、代價約 100,000 倍,一切設計為極小化 miss 率;disk 太慢故不可能 write-through。
位址空間與 VM 快取機制

Trap: protection fault 與 page fault 語意完全不同

兩者都由 MMU 讀 PTE 時發現、都以例外進入 kernel,但 page fault(valid=0)由 kernel 換頁後重跑指令、對程式透明;權限違規(general protection fault)導致 SIGSEGV、預設終止。
Linux handler 三段檢查:位址落在某 area 內?→ 存取合法?→ 才是正常 page fault。
PTE 權限位:SUP(須 kernel mode)、READ、WRITE;保護檢查搭載在轉譯上、零額外成本。
VM 記憶體管理與保護

Trap: TLB miss 不等於 page fault,TLBI 切的是 VPN

TLB miss 只是去記憶體讀 PTE;PTE valid 就沒有 fault(之後還可能 cache miss)。
TLBI = VPN 的最低 t 位、TLBT = VPN 其餘高位——切的是 VPN,不是整個 VA。
手算套路:VA → VPN/VPO → TLBT/TLBI → 查 TLB → PPN‖VPO 得 PA → CT/CI/CO → 查 cache;PPO 恆等於 VPO 不需轉譯。
位址轉譯與 TLB

Trap: fork 不會立即複製物理頁,COW 只複製單一頁

fork 只複製 mm_struct、area structs、page tables 等 metadata,並把父子雙方的頁標為 read-only private COW;任一方(包括父)先寫入都觸發複製。
誤以為 fork 當下整份位址空間被複製,或只有子行程寫入才 COW。
protection fault handler 只複製被寫入的那一頁、更新 PTE、恢復寫權後重跑寫入指令;demand-zero 頁首次 touch 也沒有磁碟 I/O。
記憶體映射

Trap: header 的 size 是整個 block 而非 payload

block size 包含 header、payload 與 padding;malloc(2) 在雙字對齊 header-only 格式下是 8-byte block(header 0x9)。
直接把要求大小當 block size 填 header 會錯。
先取整到對齊需求再 OR alloc bit;省 footer 最佳化只適用 allocated block,free block 仍須 footer 供 coalescing。
動態記憶體配置

Trap: external fragmentation 無法靠搬動解決

allocator 不允許修改或搬動已配置 block(禁止 compaction),總 free 量足夠仍可能配置失敗。
從 GC 語言的經驗誤以為可以 compact。
且 external fragmentation 取決於未來 request 模式、無法量化預測;best fit 不一定最好(implicit list 需徹底搜尋)、next fit utilization 比 first fit 差。
動態記憶體配置

Trap: Conservative GC 的「保守」方向與經典指標 bug

保守是「不可達的可能被誤標為可達(漏收 garbage)」,絕不是提早 free 使用中的區塊;漏收只造成 fragmentation、不影響正確性。
*size-- 實為 *(size--)(遞減指標);p += sizeof(int) 前進 4 個 int 不是 1 個元素;64 位下 Malloc(n*sizeof(int)) 配指標陣列只有一半空間,越界砸到 boundary tag、錯誤延遲到 free 才爆。
記住:malloc 的 heap 記憶體不清零(.bss 才由 loader 清零),要零初始化用 calloc。
垃圾回收與記憶體錯誤

系統層級 I/O (System-Level I/O)

Trap: read 回傳 0 是 EOF 不是錯誤,short count 也不是錯誤

−1 才是錯誤;EOF 是 k ≥ m 時由 kernel 偵測的「條件」,檔案裡沒有 EOF 字元。
read/write 傳輸少於要求的 n bytes 可能來自 EOF、終端機一次一行、socket 緩衝與延遲——把 short count 當錯誤處理是網路程式經典 bug。
網路程式必須迴圈重試直到傳完(或用 RIO);唯讀寫磁碟檔案時(除 EOF 外)不會 short count。
Unix I/O 與檔案

Trap: open 回傳最小未用描述子

0/1/2 已被 stdin/stdout/stderr 占用,第一次 open 得 3;close 後描述子回到可用池,再 open 仍得 3。
誤以為描述子遞增不重用。
另記:O_APPEND 是每次 write 前都移到檔尾(不是只在 open 時一次);新檔實際權限是 mode & ~umask。
Unix I/O 與檔案

Trap: dup2 參數順序記反

dup2(oldfd, newfd) 是把 oldfd 複製到 newfd(覆蓋 newfd);重導向 stdin 到 fd 5 是 dup2(5,0) 不是 dup2(0,5)。
兩個參數名稱直覺上都像「目標」。
記口訣:「讓 newfd 也指向 oldfd 指的東西」。
檔案共享、重導向與標準 I/O

Trap: open 兩次 vs fork 的 file position 共享判斷

同檔 open 兩次 → 不同 open file table entry → 獨立 position;fork 或 dup2 → 同一 entry → 共享 position。
追蹤題(Problem 10.2/10.3)輸出 c = f 或 c = o 全看這一點。
唯一判準:是否指向同一個 open file table entry;descriptor table 每 process 一張,open file table 與 v-node table 全系統共享;fork 後 refcnt=2,雙方都 close 才釋放 entry。
檔案共享、重導向與標準 I/O

Trap: 緩衝與無緩衝 RIO 函式不可混用

rio_readlineb/rio_readnb 可在同一 descriptor 任意交錯,但不可與無緩衝的 rio_readn 交錯使用。
已被讀進 rio_t 內部緩衝區的資料會遺失。
rio_readn 回傳 0 到 n 之間是提早 EOF 的 short count、非錯誤;rio_writen 保證寫滿 n 或回 −1。
RIO 套件與檔案中繼資料

Trap: readdir 的 NULL 語意雙關與 st_mode 判型

readdir 出錯與讀完 stream 都回傳 NULL,無法從回傳值區分——必須迴圈前設 errno=0、迴圈後檢查 errno。
st_mode 的檔案類型是編碼欄位而非單一 bit,必須用 S_ISREG/S_ISDIR 巨集;只有權限位元才用 & 遮罩。
兩者都是「回傳值/位元直覺」造成的誤用。
RIO 套件與檔案中繼資料

Trap: 在 socket 上使用 standard I/O

stream 的輸入/輸出交替限制需要 lseek,但 socket 上 lseek 非法;開讀寫兩個 stream 的繞法會兩次 fclose 同一 descriptor,第二次失敗。
以為 stdio 對所有 descriptor 通用。
網路 I/O 改用 Rio;也不要用 scanf/rio_readlineb 讀 binary 檔(0xa bytes 會造成不可預測失敗)。
檔案共享、重導向與標準 I/O

網路程式設計 (Network Programming)

Trap: client 與 server 是 process 不是機器

一台 host 可同時執行多個 client 與 server,transaction 甚至可發生在同一台 host 上。
日常語言把「server」當機器名稱。
另記:client-server transaction 與 database transaction 無關,不具 atomicity。
主從式模型與網路

Trap: frame 與 packet、hub/bridge/router 的層次混淆

frame 是 LAN 層單位(header 含 48-bit adapter 位址),packet 是 internet 層單位;frame 的 payload 是 packet,不是反過來。
hub 盲目複製每個 bit 到所有 port;bridge 學習 host↔port 對應選擇性轉送;只有 router 讀 internet address 查 routing table 並換 frame header。
考題常問「誰懂 internet address」——答案只有 router。
主從式模型與網路

Trap: in_addr 永遠是 network byte order(big-endian)

即使 host 是 little-endian,struct in_addr 中的位址也以 big-endian 存放;不經 htonl/ntohl 直接使用會得到 byte 反轉的位址。
且 byte order 函式沒有 64-bit 版本——問 64-bit 轉換函式時答案是「不存在」。
inet_pton 回傳值有三種:1 成功、0 非法字串(不設 errno)、−1 其他錯誤。
全球 IP 網際網路

Trap: 混淆 listening 與 connected descriptor

accept 不是在 listenfd 上通訊,而是回傳全新的 connfd;listenfd 活整個 server 生命期,connfd 每次連線建立、服務完就 close。
書中明言這是最容易混淆學生的點。
socket() 回傳的 fd 只是部分開啟:client 要 connect、server 要走完 bind/listen/accept 才能讀寫。
Socket 介面

Trap: getaddrinfo 的錯誤碼與資源管理

錯誤碼要用 gai_strerror(retcode) 轉字串,不是 errno/strerror;回傳的 linked list 必須 freeaddrinfo 釋放。
connect/bind 失敗換下一個節點前必須先 close 該 socket descriptor,否則洩漏。
另記:重啟 server 約 30 秒內 bind 被拒(Address already in use),需 setsockopt SO_REUSEADDR。
Socket 介面

Trap: EOF 不是一個字元

EOF 是 kernel 偵測的條件;連線上的 EOF 發生於對端 process 關閉其連線端,本端 read 回傳 0 才得知。
從「文字檔有 EOF 記號」的誤解延伸而來。
對已關閉的連線,第一次 write 正常返回、第二次才觸發 SIGPIPE(預設終止 process);捕捉後改為 errno=EPIPE。
Web 伺服器與 Tiny

Trap: 動態內容的 HTTP headers 由 CGI child 產生

parent(server)不知道 CGI 輸出的型別與大小,Content-type、Content-length 與終止空行必須由 CGI 程式自己輸出。
誤以為 server 統一產生所有 headers。
Tiny 的 parent 只送 response line 與 Server header;serve_static 在 Mmap 後必須 Close(srcfd)、傳完必須 Munmap,否則長駐 server 洩漏。
Web 伺服器與 Tiny

並行程式設計 (Concurrent Programming)

Trap: select 前忘記重設 ready_set = read_set

select 有副作用,就地把傳入的 fdset 改寫成 ready set。
不在每次呼叫前重新複製 read set,下一輪只會監看上輪 ready 的描述子,新事件永遠偵測不到。
每輪迴圈開頭 ready_set = read_set; 再呼叫 select。
行程與事件驅動並行

Trap: process-based server 的 parent 忘記 close connfd

fork 後父子的 connfd 指向同一 file table entry(refcount=2);child exit 由 kernel 收,但長駐 parent 不終止,不手動 Close 則 refcount 永不歸零。
file table entry 永不釋放,最終耗盡記憶體;且連線要雙方副本都關閉才真正終止。
parent fork 後立即 Close(connfd);SIGCHLD handler 用 while + WNOHANG 迴圈收割 zombie(訊號不排隊)。
行程與事件驅動並行

Trap: 傳 &connfd(區域變數位址)給 pthread_create 的 race

peer thread 解參考 vargp 與 main thread 下一次 accept 之間有 race;accept 先發生則兩 threads 對同一 descriptor 做 I/O。
「在某台機器上碰巧正確」讓 bug 潛伏,換排程就錯。
每個 connfd 各自 Malloc 專屬記憶體,peer 讀取後 Free,並 Pthread_detach 避免 memory leak;main 建立後立刻 free 則變 use-after-free。
執行緒

Trap: main thread 的 pthread_exit 與 exit 行為不同

main thread 呼叫 pthread_exit 會先等所有 peer threads 終止再結束 process;任一 thread 呼叫 exit 則立即終止 process 與所有 threads。
兩者都「結束 main」但語意天差地遠。
joinable thread 未 join 也未 detach 會漏記憶體(thread 終止不像 process 由 kernel 全面回收);pthread_join 只能等特定 tid,不像 wait 可等任一子行程。
執行緒

Trap: thread context 不包含 heap 或 open files;threads 無父子階層

thread 私有的只有 TID、stack、stack pointer、PC、通用暫存器、condition codes;code、data、heap、shared libraries、open files 全 process 共享。
從 process 的觀念套過來會答錯共享範圍;threads 是 pool of peers,任何 peer 都可 kill/join 任何其他 peer。
共享與否看 instance 被幾個 threads 參考,不看 storage class——main stack 上的區域變數被 global 指標間接參考時也是 shared。
共享變數與號誌

Trap: Sbuf 中兩個 P 的順序不可對調

sbuf_insert 必須先 P(&slots) 再 P(&mutex);先鎖 mutex 再等 slot,buffer 滿時 producer 持鎖睡眠,consumer 拿不到 mutex → deadlock。
「先保護再等待」的直覺順序恰好是錯的。
口訣:先等資源、再取鎖;防 deadlock 靠 mutex lock ordering rule(依序取鎖、反序放鎖)。V 重啟哪個等待 thread 不可預測,readers-writers 兩型解皆可能 starvation。
共享變數與號誌

Trap: reentrant 不是 thread-safe 的同義詞

reentrant 是 thread-safe 的 proper subset;implicitly reentrant 函式(如 rand_r)還取決於 caller 是否傳入非共享資料的指標。
lock-and-copy 只對 Class 1/3 有效;rand、strtok 這類依賴跨呼叫 static state 的 Class 2 函式,唯一解法是改寫成 reentrant。
relative speedup 會灌水(T1 用平行版單核時間、分子含同步開銷);absolute speedup 才是真實效益。
平行化與執行緒安全

Trap: 多執行緒不保證更快

psum-mutex 在 4 核上跑 2 threads 比 1 thread 慢 6 倍以上(68s→432s):P/V 成本遠高於一次記憶體更新。
「加 threads 就變快」忽略同步成本;threads 超過核心數後 context switch 也使時間回升。
讓每 thread 累加到私有變數、最後才合併;deadlock 不可預測且難重現,同一程式千次沒事、下次死結。
平行化與執行緒安全

學習地圖 — 搭配 Weak Areas 追蹤易錯章節,針對性複習
速查表 — 陷阱對應的公式、指令與 API 速查