CSAPP 速查表 (Quick Reference)

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

資訊表示與程式翻譯 → 資訊表示與程式翻譯

概念	重點
一切都是 bits	資料物件的意義由 context 決定;同一串 bytes 可為整數、浮點數、字串或指令
編譯系統四階段	Preprocessing (cpp) → Compilation (cc1) → Assembly (as) → Linking (ld);gcc 為 compiler driver
副檔名鏈	.c → .i → .s(text)→ .o → executable(binary);text/binary 分界在 assembler
relocatable object	.o 不能直接執行,必須經 linking 成 executable object file
理解編譯系統三理由	最佳化效能、理解 link-time 錯誤、避免 buffer overflow 安全漏洞

(本筆記無公式)

硬體組織與程式執行 → 硬體組織與程式執行

概念	重點
四大硬體	buses、I/O devices、main memory (DRAM)、processor(含 PC、register file、ALU)
CPU 四種基本操作	Load、Store、Operate、Jump;PC 存下一條指令位址,CPU 不斷「執行、更新 PC」
DMA	磁碟資料直達主記憶體、不經 CPU;系統大量時間花在搬移資料
cache 與 locality	SRAM cache 靠 locality 兼得大記憶體與快記憶體;懂 cache 可提升一個數量級
memory hierarchy	L0=registers、L1~L3=SRAM、L4=main memory、L5=disk、L6=remote;每層是下層的 cache

(本筆記無公式)

作業系統抽象與網路 → 作業系統抽象與網路

概念	重點
三大抽象	files → I/O devices;virtual memory → main memory + disk;processes → CPU+記憶體+I/O
Context switch	Context = PC + register file + 記憶體內容;三步驟:save 舊 → restore 新 → 交出控制權
Kernel	不是 process,是常駐記憶體的 code 與資料結構;應用程式經 system call 進入
位址空間五區	code/data → heap → shared libraries → user stack → kernel(user 不可讀寫)
File	就是位元組序列;所有 I/O 裝置(含網路)都建模成 file

公式

$T_{n e w} = (1 - α) T_{o l d} + \frac{α T_{o l d}}{k} = T_{o l d} [(1 - α) + α / k]$
$S = T_{o l d} / T_{n e w} = \frac{1}{(1 - α) + α / k}$ (Amdahl's law, Eq. 1.1)
例: $α = 0.6, k = 3 \Rightarrow S = 1 / [0.4 + 0.6 / 3] = 1.67 \times$

Amdahl 定律與並行主題 → Amdahl 定律與並行主題

概念	重點
Amdahl's Law	整體加速受改善部分佔比 α 與局部加速 k 共同限制;未改善的 (1−α) 是不可逾越瓶頸
Concurrency vs Parallelism	concurrency = 多個同時活動;parallelism = 利用 concurrency 讓系統更快
平行三層次	thread-level → instruction-level(pipelining/superscalar)→ SIMD
Hyperthreading	複製 PC、register file 等,不複製浮點單元;逐週期切換 thread
四大抽象	ISA 抽象處理器、files 抽象 I/O、virtual memory 抽象記憶體、processes 抽象執行中程式

公式

$T_{n e w} = (1 - α) T_{o l d} + \frac{α T_{o l d}}{k} = T_{o l d} [(1 - α) + α / k]$
$S = T_{o l d} / T_{n e w} = \frac{1}{(1 - α) + α / k}$ (Equation 1.1)
$S_{\infty} = \frac{1}{1 - α}$ (Equation 1.2, $k \to \infty$ )
已知 S、α 反解 k:如 $S = 4, α = 0.9 \Rightarrow 0.4 + 3.6 / k = 1 \Rightarrow k = 6$

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

資訊儲存與位元運算 → 資訊儲存與位元運算

概念	重點
byte 與 hex	最小可定址單位是 byte;1 hex digit = 4 bits;C 以 0x 前綴表示
endianness	little endian 低位 byte 在低位址(Intel/ARM);big endian 高位在前
位元 vs 邏輯運算	& \| ~ ^ 逐位運算;&& \|\| ! 只回傳 0/1 且短路求值
移位	左移補 0;右移分 logical(補 0)與 arithmetic(補 MSB);unsigned 必為 logical
C 字串	ASCII 字元陣列 + null 結尾;文字資料與 endianness/word size 無關,最可攜

公式

w-bit word size 的 virtual address 範圍: $0 \sim 2^{w} - 1$ ,可定址 $2^{w}$ bytes
2 的冪轉 hex: $x = 2^{n}, n = i + 4 j (0 \leq i \leq 3)$ → 前導 hex digit $2^{i}$ 後接 $j$ 個 0
decimal → hex:反覆分解 $x = q \cdot 16 + r$ ,餘數由低位往高位排
hex → decimal:各 digit 乘 16 的冪加總,例 $0 x 7 A F = 7 \cdot 16^{2} + 10 \cdot 16 + 15 = 1967$
bit vector 運算定義: $(a & b)_{i} = a_{i} & b_{i}, 0 \leq i < w$ (|、^、~ 同理)
分配律:a & (b | c) = (a & b) | (a & c);a | (b & c) = (a | b) & (a | c)
Boolean ring: $a \oplus a = 0$ ; $(a \oplus b) \oplus a = b$
集合編碼: $A \subseteq {0, \dots, w - 1} \leftrightarrow$ bit vector, $a_{i} = 1 ⟺ i \in A$ ;| = ∪、& = ∩、~ = 補集
左移: $x ≪ k = [x_{w - k - 1}, \dots, x_{0}, 0, \dots, 0]$ (右端補 k 個 0)
邏輯右移: $x ≫ k = [0, \dots, 0, x_{w - 1}, \dots, x_{k}]$ ;算術右移: $x ≫ k = [x_{w - 1}, \dots, x_{w - 1}, x_{w - 1}, \dots, x_{k}]$
許多機器的實際移位量 = $k mod w$ (取移位量低 $\log_{2} w$ bits;C 未保證)
x == y 等價於 !(x ^ y)
bis(x, m) = x | m;bic(x, m) = x & ~m;x ^ y = bis(bic(x,y), bic(y,x))

整數表示 → 整數表示

概念	重點
B2U / B2T	無號每 bit 權重 $2^{i}$ ;二補數 sign bit 權重 $- 2^{w - 1}$ ;皆為雙射
cast 不變位元	signed/unsigned cast 位元樣式不變、只改解讀;混合運算時 signed 隱式轉 unsigned
擴展	unsigned 用 zero extension;two's complement 用 sign extension;先改大小再改型別
截斷	丟高位 = overflow:unsigned 為 $x mod 2^{k}$ ;signed 為 $U 2 T_{k} (x mod 2^{k})$
經典 bug	`i <= length-1`(length=0 wrap 成 UMax)、`strlen(s)-strlen(t) > 0` 永非負

公式

$B 2 U_{w} (x) = \sum_{i = 0}^{w - 1} x_{i} \cdot 2^{i}$ (式 2.1)
$B 2 T_{w} (x) = - x_{w - 1} \cdot 2^{w - 1} + \sum_{i = 0}^{w - 2} x_{i} \cdot 2^{i}$ (式 2.3)
$U M a x_{w} = 2^{w} - 1$ ; $T M i n_{w} = - 2^{w - 1}$ ; $T M a x_{w} = 2^{w - 1} - 1$
$U M a x = 2 \cdot T M a x + 1$ ; $| T M i n | = | T M a x | + 1$
$T 2 U_{w} (x) = x + x_{w - 1} \cdot 2^{w} = {x + 2^{w} (x < 0); x (x \geq 0)}$ (式 2.5, 2.6)
$U 2 T_{w} (u) = - u_{w - 1} \cdot 2^{w} + u = {u (u \leq T M a x_{w}); u - 2^{w} (u > T M a x_{w})}$ (式 2.7, 2.8)
截斷 (unsigned): $B 2 U_{k} ([x_{k - 1}, \dots, x_{0}]) = B 2 U_{w} (x) mod 2^{k}$ (式 2.9)
截斷 (two's complement): $B 2 T_{k} ([x_{k - 1}, \dots, x_{0}]) = U 2 T_{k} (B 2 U_{w} (x) mod 2^{k})$ (式 2.10)
$B 2 O_{w} (x) = - x_{w - 1} (2^{w - 1} - 1) + \sum_{i = 0}^{w - 2} x_{i} \cdot 2^{i}$ (ones' complement)
$B 2 S_{w} (x) = (- 1)^{x_{w - 1}} \cdot \sum_{i = 0}^{w - 2} x_{i} \cdot 2^{i}$ (sign magnitude)
sign extension 保值關鍵: $2^{w} - 2^{w - 1} = 2^{w - 1}$

整數算術 → 整數算術

概念	重點
modular arithmetic	w-bit 運算結果一律截斷為 mod $2^{w}$ ;C 對 overflow 不發任何訊號
溢位偵測	unsigned:s < x 即溢位;signed:兩正得非正 / 兩負得非負
位元層級相同	加減乘與左移在 unsigned 與 two's complement 位元層級完全相同
乘除最佳化	乘常數改寫成 shift+add/sub;除以 $2^{k}$ signed 須加 bias 才是向零捨入
安全漏洞	FreeBSD getpeername(負長度轉 size_t)、Sun XDR(malloc 乘法溢位)

公式

$x +_{w}^{u} y = x + y$ (若 $x + y < 2^{w}$ ,Normal); $x + y - 2^{w}$ (若 $2^{w} \leq x + y < 2^{w + 1}$ ,Overflow)— Eq. 2.11
unsigned 溢位偵測: $s = x +_{w}^{u} y$ 溢位 $⟺ s < x$
unsigned 取負: $-_{w}^{u} x = x (x = 0); 2^{w} - x (x > 0)$ — Eq. 2.12
$x +_{w}^{t} y = x + y - 2^{w}$ (正溢位)/ $x + y$ (Normal)/ $x + y + 2^{w}$ (負溢位)— Eq. 2.13
$x +_{w}^{t} y = U 2 T_{w} (T 2 U_{w} (x) +_{w}^{u} T 2 U_{w} (y))$ — Eq. 2.14
two's complement 取負: $-_{w}^{t} x = T M i n_{w} (x = T M i n_{w}); - x (x > T M i n_{w})$ — Eq. 2.15;且 -x == ~x + 1
$x *_{w}^{u} y = (x \cdot y) mod 2^{w}$ — Eq. 2.16
$x *_{w}^{t} y = U 2 T_{w} ((x \cdot y) mod 2^{w})$ — Eq. 2.17
乘法位元等價: $T 2 B_{w} (x *_{w}^{t} y) = U 2 B_{w} (x^{'} *_{w}^{u} y^{'})$
$x ≪ k = x *_{w} 2^{k}$ (unsigned 與 two's complement 皆成立, $0 \leq k < w$ )
乘常數 Form A:(x<<n)+(x<<(n-1))+...+(x<<m);Form B:(x<<(n+1))-(x<<m)
unsigned 除法:x >> k(logical) $= ⌊ x / 2^{k} ⌋$
signed 直接算術右移:x >> k(arithmetic) $= ⌊ x / 2^{k} ⌋$ (向下捨入)
$⌈ x / y ⌉ = ⌊ (x + y - 1) / y ⌋$ ( $y > 0$ );故 (x + (1<<k) - 1) >> k $= ⌈ x / 2^{k} ⌉$
signed 向零捨入除法:(x<0 ? x+(1<<k)-1 : x) >> k $= x / 2^{k}$

浮點數 → 浮點數

概念	重點
IEEE 754 三欄位	sign / exp(k bits)/ frac(n bits);float: k=8, n=23;double: k=11, n=52
三類值	normalized(implied leading 1)、denormalized(exp 全 0,±0 與 gradual underflow)、特殊值(∞ / NaN)
捨入	預設 round-to-even:僅 halfway 時取偶數 LSB;另有 toward-zero / down / up
運算性質	加法與乘法可交換但不可結合、不可分配;具單調性(NaN 除外)→ 編譯器最佳化必須保守
C 轉型	float/double→int 向零截斷,溢位得 TMin;int→float 可能捨入;double→float 可能成 ±∞

公式

$b = \sum_{i = - n}^{m} 2^{i} \times b_{i}$ (式 2.19,fractional binary)
$V = (- 1)^{s} \times M \times 2^{E}$
$B i a s = 2^{k - 1} - 1$
Normalized: $E = e - B i a s, M = 1 + f$
Denormalized: $E = 1 - B i a s, M = f$
最小正 denormalized: $V = 2^{- n} \times 2^{- 2^{k - 1} + 2}$
最大 denormalized: $V = (1 - 2^{- n}) \times 2^{- 2^{k - 1} + 2}$
最小正 normalized: $V = 2^{- 2^{k - 1} + 2}$
最大 normalized: $V = (2 - 2^{- n}) \times 2^{2^{k - 1} - 1}$
最小無法精確表示正整數 $= 2^{n + 1} + 1$
$x +_{f} y = R o u n d (x + y)$ ; $x *_{f} y = R o u n d (x \times y)$
加法單調性: $a \geq b \Rightarrow x +_{f} a \geq x +_{f} b$ (除 NaN)
乘法單調性: $a \geq b$ 且 $c \geq 0 \Rightarrow a *_{f} c \geq b *_{f} c$ ; $a \geq b$ 且 $c \leq 0 \Rightarrow a *_{f} c \leq b *_{f} c$ ; $a \neq N a N \Rightarrow a *_{f} a \geq 0$

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

程式編碼與資料格式 → 程式編碼與資料格式

概念	重點
x86-64 演進	每代 backward compatible;AMD 率先推 x86-64,Intel 實作稱 EM64T
可見狀態	PC (%rip)、16 個 64-bit 整數暫存器、condition codes、vector registers
指令編碼	長 1–15 bytes;固定起點有唯一解碼;objdump -d 反組譯只靠位元組序列
尾碼	b/w/l/q 對應 1/2/4/8 bytes;int=4 (l)、long 與指標=8 (q)
-Og	產生貼近原始 C 結構的機器碼,學習用;-O1/-O2 效能較佳但難對映

公式

32-bit 定址上限 $= 2^{32}$ bytes $= 4$ GB
x86-64 現行實作記憶體上限 $= 2^{48}$ bytes $= 256$ TB;架構上限 $= 2^{64}$ bytes $= 16$ EB
x86-64 虛擬位址:64-bit word 且高 16 bits = 0 → 可定址 $2^{48}$ bytes = 256 TB
Moore's Law:電晶體數約每 18 個月翻倍(x86 實測年增約 37%,約每 26 個月翻倍)
8086 位址寬 20 bits → 可定址 $2^{20} = 1,048,576$ bytes

資料搬移與算術運算 → 資料搬移與算術運算

概念	重點
暫存器規則	產生 4-byte 結果時高 4 bytes 清 0;1/2-byte 結果其餘 bytes 不變
mov 限制	兩 operand 不可同為 memory;movq immediate 限 32-bit(符號延伸),64-bit 用 movabsq
延伸	movz 零延伸、movs 符號延伸;無 movzlq(直接用 movl);cltq ≡ movslq %eax,%rax
leaq	只算 effective address 不碰記憶體,常用於乘加運算 a + b*s + Imm
右移分兩種	sar 算術右移補符號位、shr 邏輯右移補 0;唯一需區分 signed/unsigned 的運算

公式

Effective address: $E A = I m m + R [r_{b}] + R [r_{i}] \cdot s$ , $s \in {1, 2, 4, 8}$
pushq S: $R [% r s p] \leftarrow R [% r s p] - 8; M [R [% r s p]] \leftarrow S$
popq D: $D \leftarrow M [R [% r s p]]; R [% r s p] \leftarrow R [% r s p] + 8$
leaq S, D: $D \leftarrow & S$
移位量 = %cl 的低 m 位,其中 $2^{m} = w$ (w 為 operand 位元數)
imulq/mulq S(單運算元): $R [% r d x] : R [% r a x] \leftarrow S \times R [% r a x]$
cqto: $R [% r d x] : R [% r a x] \leftarrow S i g n E x t e n d (R [% r a x])$
idivq/divq S: $R [% r a x] \leftarrow R [% r d x] : R [% r a x] \div S; R [% r d x] \leftarrow R [% r d x] : R [% r a x] mod S$
movz: $R \leftarrow Z e r o E x t e n d (S)$ ;movs: $R \leftarrow S i g n E x t e n d (S)$

控制流 → 控制流

概念	重點
Condition codes	CF(unsigned overflow)、ZF(零)、SF(負)、OF(signed overflow);leaq 不改旗標
cmp / test	cmp 依 S2−S1 設旗標(同 sub 不寫回);test 依 S1&S2(同 and 不寫回)
cmov	兩邊都求值再選,免 branch prediction;有副作用或可能出錯時不可用
迴圈翻譯	-Og 用 jump-to-middle;-O1 用 guarded-do(初始測試 + do-while)
switch	jump table,執行時間與 case 數無關;範圍檢查以 unsigned 一條 ja 攔截兩邊

公式

CF = (unsigned) t < (unsigned) a
ZF = (t == 0)
SF = (t < 0)
OF = (a < 0 == b < 0) && (t < 0 != a < 0)
setl/jl/cmovl 條件 = SF ^ OF
setle 條件 = (SF ^ OF) | ZF
setg 條件 = ~(SF ^ OF) & ~ZF
setge 條件 = ~(SF ^ OF)
setb 條件 = CF;setbe = CF | ZF;seta = ~CF & ~ZF;setae = ~CF
PC-relative:target = addr(下一條指令) + offset(二補數)
$T_{a v g} (p) = (1 - p) T_{O K} + p (T_{O K} + T_{M P}) = T_{O K} + p \cdot T_{M P}$
$T_{M P} = 2 (T_{r a n} - T_{O K})$

程序與執行時堆疊 → 程序與執行時堆疊

概念	重點
三機制	passing control、passing data、allocating/deallocating memory;用不到的一律省略
stack 成長	向低位址成長,%rsp 指 stack top;return address 屬 caller 的 frame
傳參	前 6 個整數引數:%rdi %rsi %rdx %rcx %r8 %r9;回傳值 %rax;第 7 個起放 stack
callee-saved	%rbx %rbp %r12–%r15 共 6 個,callee 須 push 保存、反序 pop 還原
遞迴	每次呼叫有私有 stack frame,LIFO 天然匹配 call-return;leaf procedure 免 frame

公式

call: $R [% r s p] \leftarrow R [% r s p] - 8; M [R [% r s p]] \leftarrow A_{r e t u r n}$ (call 下一條指令位址); $P C \leftarrow A_{t a r g e t}$
ret: $P C \leftarrow M [R [% r s p]]; R [% r s p] \leftarrow R [% r s p] + 8$
Stack 傳參大小 = 向上取整至 8 bytes 倍數(rounded up to multiples of eight)
Callee 端 stack 引數位移:引數 7 在 8(%rsp)、引數 8 在 16(%rsp)(return address 佔 0(%rsp))
整數引數暫存器順序:%rdi, %rsi, %rdx, %rcx, %r8, %r9(最多 6 個);回傳值在 %rax

陣列與異質資料結構 → 陣列與異質資料結構

概念	重點
陣列定址	T A[N] 連續 LN bytes;A[i] ≡(A+i);指標運算自動依型別大小縮放
二維陣列	row-major;VLA 需 imulq、固定大小只用 leaq/shift-add(組語判別法)
struct	欄位以編譯期 byte offset 定位;機器碼不含欄位名稱
union	所有欄位 offset 皆 0;可重新詮釋位元樣式;不同大小欄位有 endianness 陷阱
對齊	K-byte 物件位址須為 K 倍數;struct 插 gap、尾端 padding;SSE 強制 16-byte

公式

$& A [i] = x_{A} + L \cdot i$ (一維陣列元素位址,L = sizeof(T))
p+i 的值 $= x_{p} + L \cdot i$ (指標運算自動縮放)
$& E [i] - E = (位址差) / L = i$ (指標相減,型別 long)
Equation 3.1: $& D [i] [j] = x_{D} + L (C \cdot i + j)$ (T D[R][C],row-major)
二維陣列總大小 $= L \cdot R \cdot C$ (如 int A[5][3] = 453 = 60 bytes)
VLA: $& A [i] [j] = x_{A} + 4 (n \cdot i + j)$ (n 為執行期值,需 imulq)
對角線步幅 $= L (C + 1)$ ;走訪終點 $= L \cdot R \cdot (C + 1)$ (如 417=68、416*17=1088)
union 大小 = max(各欄位大小)(加對齊 padding)
對齊規則:K-byte 物件位址 $\equiv 0 (\mod K)$ ;struct 對齊 = max(欄位 K);struct 總大小為其對齊的倍數
tagged union 大小 = 4(tag) + 4(padding) + 16(union) = 24 bytes(node_t 例)

緩衝區溢位與指標安全 → 緩衝區溢位與指標安全

概念	重點
buffer overflow	C 無邊界檢查,區域緩衝區與 return address 同在 stack,越界寫可覆寫返回位址
危險函式	gets/strcpy/strcat/sprintf 不知目標大小;應改用 fgets
防線一 ASLR	stack 位址隨機化;可被 nop sled + 暴力破解
防線二 canary	buf 與 saved state 間放隨機 canary(%fs:40),失敗呼叫 __stack_chk_fail
防線三 NX bit	stack 可讀寫但不可執行,硬體檢查無效能代價

公式

指標算術:運算式 p+i 的位址 $= p + L \cdot i$ (L 為所指型別大小)
(int *) p + 7 = p + 28(縮放 4,cast 優先)
(int *) (p + 7) = p + 7
32 位元 stack 位址隨機化範圍 $\approx 2^{23}$ ;64 位元 $\approx 2^{32}$
256-byte nop sled 對 $n = 2^{23}$ 需列舉 $2^{15} = 32768$ 個起始位址
s2 對齊:andq $-16 → 向下對齊 16 的倍數;p:leaq 7(%rsp) 後 shrq $3 再 *8 → 向上對齊 8 的倍數

浮點程式碼 → 浮點程式碼

概念	重點
暫存器	%xmm0–%xmm7 依序傳最多 8 個浮點參數(與整數分開計數);回傳值 %xmm0;全部 caller-saved
轉換	FP→整數 vcvttss2si 一律截斷;整數→FP vcvtsi2ss 三運算元格式
常數	AVX 浮點不能用 immediate;常數以 label(%rip) PC-relative 讀取
位元運算	vxorps 自 xor 得 0.0、and 遮罩做 fabs、xor sign bit 取負
比較	ucomiss/ucomisd 設 CF/ZF/PF;PF=1 表 unordered(NaN);搭配 ja/jb 而非 jg/jl

公式

IEEE 754: $V = (- 1)^{s} \times M \times 2^{E}$ ;normalized 時 $E = e - B i a s, M = 1 + f$
$B i a s = 2^{k - 1} - 1$ (single: 127,double: 1023)
vaddss/vaddsd:D ← S2 + S1;vsubss/vsubsd:D ← S2 − S1
vmulss/vmulsd:D ← S2 × S1;vdivss/vdivsd:D ← S2 / S1
vmaxss/vmaxsd:D ← max(S2, S1);vminss/vminsd:D ← min(S2, S1)
sqrtss/sqrtsd:D ← √S1
vxorps/xorpd:D ← S2 ^ S1;vandps/andpd:D ← S2 & S1
fabs(x) = x AND 0x7fffffffffffffff(清 sign bit);−x = x XOR 0x8000000000000000(翻 sign bit);x XOR x = 0.0
ucomis[s|d] S1, S2 依 S2 − S1 設 flag:unordered→CF=ZF=PF=1;S2<S1→CF=1;S2=S1→ZF=1;S2>S1→全 0
1.8 解碼:0x3ffccccccccccccd → e=0x3ff=1023, E=0, f=0xccccccccccccd(=0.8), M=1.8
32.0 解碼:0x4040000000000000 → e=0x404=1028, E=5, M=1.0 → $1.0 \times 2^{5}$

4. 處理器架構(Processor Architecture)

Y86-64 指令集架構 → Y86-64 指令集架構

概念	重點
可見狀態	15 個 64-bit registers(無 %r15)+ ZF/SF/OF + PC + memory + Stat
movq 四拆	irmovq/rrmovq/mrmovq/rmmovq;不允許 memory-to-memory 與 immediate-to-memory
OPq	addq/subq/andq/xorq 只能 register-register,且是唯一設 condition codes 的指令
Stat 狀態碼	AOK=1、HLT=2、ADR=3、INS=4;非 AOK 即停機
CISC/RISC 混血	變長編碼、CC、stack 返回位址(CISC)+ load/store、register 傳參(RISC)

公式

指令總長 = 1 (code:fn byte) + [0|1] (rA:rB byte) + [0|8] (constant word) = 1~10 bytes
編碼步驟:首 byte(code:fn)→ register byte(單 operand 補 F)→ 常數補足 8 bytes 後 byte-reverse(little-endian)
範例:rmmovq %rsp,0x123456789abcd(%rdx) → 4042cdab896745230100
pushq %rsp: $M [R [% r s p] - 8] \leftarrow$ 原 %rsp 值; $R [% r s p] \leftarrow R [% r s p] - 8$
popq %rsp ≡ mrmovq (%rsp),%rsp( $% r s p \leftarrow M [R [% r s p]]$ ,遞增結果被覆蓋)

邏輯設計與 HCL → 邏輯設計與 HCL

概念	重點
三要素	combinational logic 計算、memory elements 儲存、clock 控制更新時機
組合電路限制	每個閘輸入恰接一個來源、輸出不可相接、網路必須 acyclic;無短路求值
clocked register	只在 clock 上升緣載入新狀態,是組合邏輯區塊間的屏障
register file	2 讀取埠 + 1 寫入埠;讀取像組合邏輯、寫入由 clock 控制;0xF 表不寫入
case expression	依序求值取第一個為 1 的 case;選擇條件不需互斥

公式

bool eq = (a && b) || (!a && !b);
bool xor = (!a && b) || (a && !b);(xor 與 eq 互為補數)
bool out = (s && a) || (!s && b);(bit MUX)
bool Eq = (A == B);(word-level equality)
case expression 一般形式:[ select_1 : expr_1; ... select_k : expr_k; ]
word Out = [ s: A; 1: B; ];(word-level MUX)
word Out4 = [ !s1 && !s0 : A; !s1 : B; !s0 : C; 1 : D; ];(4-way MUX)
word Min3 = [ A <= B && A <= C : A; B <= A && B <= C : B; 1 : C; ];(化簡:第二條 B <= C : B;)
集合成員測試:iexpr in { iexpr_1, iexpr_2, ..., iexpr_k }
bool s1 = code in { 2, 3 }; bool s0 = code in { 1, 3 };

循序 SEQ 實作 → 循序 SEQ 實作

概念	重點
六階段	Fetch → Decode → Execute → Memory → Write back → PC update;每 cycle 一整條指令
new PC 三來源	valP(循序)、valC(call 與 taken jXX)、valM(ret)
No reading back	指令永不讀回自己剛更新的狀態;pushq 以 valE 同時當寫回資料與寫入位址
時序	只有 PC、CC、data memory、register file 需時序控制,由單一 clock 驅動
缺點	cycle time 由最長路徑決定(如 ret 四次串聯存取),引出 pipelining

公式

$v a l P = p + 1 + r + 8 i$ (p=PC 值,r=need_regids,i=need_valC;涵蓋 1/2/9/10 bytes 指令長度)
OPq:valE ← valB OP valA(如 subq 為 valB − valA)
rrmovq:valE ← 0 + valA;irmovq:valE ← 0 + valC
rmmovq/mrmovq 有效位址:valE ← valB + valC
pushq/call:valE ← valB + (−8);popq/ret:valE ← valB + 8
jXX:Cnd ← Cond(CC, ifun);PC ← Cnd ? valC : valP
call:PC ← valC;ret:PC ← valM;其他:PC ← valP
need_regids = icode in {IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ}
srcA = [icode in {IRRMOVQ,IRMMOVQ,IOPQ,IPUSHQ}: rA; icode in {IPOPQ,IRET}: RESP; 1: RNONE]
dstE(未含 cmov)= [icode in {IRRMOVQ}: rB; icode in {IIRMOVQ,IOPQ}: rB; icode in {IPUSHQ,IPOPQ,ICALL,IRET}: RESP; 1: RNONE]
aluA = [icode in {IRRMOVQ,IOPQ}: valA; icode in {IIRMOVQ,IRMMOVQ,IMRMOVQ}: valC; icode in {ICALL,IPUSHQ}: −8; icode in {IRET,IPOPQ}: 8]
alufun = [icode == IOPQ: ifun; 1: ALUADD];set_cc = icode in {IOPQ}
mem_addr = [icode in {IRMMOVQ,IPUSHQ,ICALL,IMRMOVQ}: valE; icode in {IPOPQ,IRET}: valA];mem_read = icode in {IMRMOVQ,IPOPQ,IRET}
new_pc = [icode==ICALL: valC; icode==IJXX && Cnd: valC; icode==IRET: valM; 1: valP]

管線化原理 → 管線化原理

概念	重點
pipelining	切多個 stage、以 pipeline register 分隔;提高 throughput 但略增 latency
不均勻切割	週期被最慢 stage 綁死;ALU / 記憶體往往不可再細分
深管線遞減	register 延遲是固定 overhead;現代處理器 15+ stage 拉高時脈
feedback path	天真管線化會改變行為,違反 ISA 模型不可接受
SEQ+	把 PC 計算移到週期開頭,用 pIcode/pCnd 等暫存器保存上一指令訊號

公式

Throughput = 1 instruction / clock period;GIPS = 1000 / 週期(ps)
Clock period = max(stage delay) + pipeline register delay
未管線化:Latency = 1/Throughput(例:300+20 = 320 ps → 3.12 GIPS)
管線化:Latency = stage 數 × clock period(例:3 × 120 = 360 ps)
k 段均勻切割(邏輯 300 ps、register 20 ps):Latency = 300 + 20k (ps)
k 段均勻切割:Throughput = 1000k/(300+20k) GIPS
深管線極限: $k \to \infty$ 時 Throughput → 1000/20 = 50 GIPS(由 register 延遲決定)

PIPE 管線實作與冒險 → PIPE 管線實作與冒險

概念	重點
分支預測	call/jmp 用 valC、條件 jXX always taken(~60%)、ret 不預測直接 stall
forwarding	5 來源 (e_valE, m_valM, M_valE, W_valM, W_valE) → 2 目的地;execute > memory > write-back
load/use hazard	m_valM 太晚,需 load interlock = stall 1 cycle + forwarding
control hazard	ret 注入 3 bubbles;mispredicted branch squash 2 條誤抓指令
exception	stat 隨指令流至 write-back 才生效;管線最深者優先;被 squash 者一併取消

公式

$C P I = (C_{i} + C_{b}) / C_{i} = 1.0 + C_{b} / C_{i}$
$C P I = 1.0 + l p + m p + r p$
penalty(每項)= 指令頻率 × 條件頻率 × bubble 數
書例:lp = 0.25×0.20×1 = 0.05;mp = 0.20×0.40×2 = 0.16;rp = 0.02×1.00×3 = 0.06;CPI = 1.27
bubble 數:load/use = 1、mispredicted branch = 2、ret = 3
load/use 偵測:E_icode ∈ {IMRMOVQ, IPOPQ} && E_dstM ∈ {d_srcA, d_srcB}
mispredict 偵測:E_icode == IJXX && !e_Cnd
ret 偵測:IRET ∈ {D_icode, E_icode, M_icode}
exception 偵測:m_stat ∈ {SADR,SINS,SHLT} || W_stat ∈ {SADR,SINS,SHLT}
$I P C = 1 / C P I$

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

最佳化編譯器與其限制 → 最佳化編譯器與其限制

概念	重點
safe optimization	最佳化後在所有情況下行為必須相同,編譯器只能假設最壞情況
兩大 blockers	memory aliasing(指標可能同址)與函式呼叫 side effects
code motion	把不變計算(vec_length、strlen)移出迴圈;編譯器不敢自動做
區域變數累加	combine4 用 acc 常駐暫存器,記憶體操作 2 讀 1 寫降為 1 讀
O(n²) 陷阱	lower1 在迴圈條件呼叫 strlen;移出後成線性,快逾 50 萬倍

公式

$T = O v e r h e a d + C P E \times n$ (迭代程式執行時間模型;CPE 為線性項斜率)
clock period = 1 / clock frequency(4 GHz → 0.25 ns = 250 ps)
prefix sum(式 5.1): $p_{0} = a_{0}$ ; $p_{i} = p_{i - 1} + a_{i}, 1 \leq i < n$
psum1 ≈ 368 + 9.0n;psum2 ≈ 368 + 6.0n(CPE 分別為 9.0、6.0)
least squares fit:最小化 $E (m, b) = \sum_{i = 1. . n} (m x_{i} + b - y_{i})^{2}$
func1 inline 合併結果:t = 4*counter + 6; counter += 4

現代處理器運作 → 現代處理器運作

概念	重點
兩個下界	latency bound(嚴格循序相依)與 throughput bound(功能單元算力極限)
superscalar + OoO	ICU 產生 micro-ops、EU 平行執行,retirement unit 保證循序語意
register renaming	tag 轉發取值免經 register file,支撐 speculative execution
功能單元三參數	latency、issue time、capacity;issue=1 稱 fully pipelined;除法不 pipeline
critical path	跨迭代相依鏈決定效能下界;直接法勝 Horner 法的原因

公式

最大吞吐量 = C/I ops/cycle(C = capacity,I = issue time)
總執行時間 $T \approx L \cdot n + K$ (L = 合併運算 latency)→ CPE = L
Latency bound(Haswell):int + = 1.00, int = 3.00, FP + = 3.00, FP = 5.00
Throughput bound(Haswell):int + = 0.50, int = 1.00, FP + = 1.00, FP = 0.50
combine4 critical path = 5n cycles(FP mul 鏈),右側 add 鏈僅 n cycles
多項式: $a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n}$ (直接法 CPE 5.00)
Horner 法: $a_{0} + x (a_{1} + x (a_{2} + \dots + x (a_{n - 1} + x \cdot a_{n}) \dots))$ (CPE 8.00 = mul 5 + add 3 串聯)

迴圈展開與平行度 → 迴圈展開與平行度

概念	重點
k × 1 展開	只減 loop overhead;critical path 仍 n 個運算,卡在 latency bound
k × k 多累加器	拆 k 組獨立累加,critical path 剩 n/k → CPE ≈ L/k,首次突破 latency bound
reassociation	k × 1a 只改括號,元素互乘不在相依鏈 → CPE ≈ L/2
浮點注意	二補數加乘溢位仍 associative;浮點不可結合,重排可能改變結果
register spilling	展開因子過大 accumulator 溢到 stack,20×20 反比 10×10 慢

公式

k × 1 展開主迴圈條件: $i < n - k + 1$ (保證最大索引 $i + k - 1 < n$ )
Latency bound:CPE ≥ L(串列相依鏈時)
Throughput bound:總 cycles ≥ N·I/C(N 個運算、C 個功能單元、issue time I);CPE ≥ I/C
$P_{n} = \prod_{i = 0}^{n - 1} a_{i} = P E_{n} \times P O_{n}$ ; $P E_{n} = \prod a_{2 i}$ ; $P O_{n} = \prod a_{2 i + 1}$
k × k 展開:CPE ≈ L/k(k 條 critical path,各 n/k 個運算)
填滿 pipeline 達 throughput bound 的條件: $k \geq C \times L$
Horner CPE = L(mul) + L(add) = 5 + 3 = 8(Practice 5.6)

限制因素與記憶體效能 → 限制因素與記憶體效能

概念	重點
分支	可預測分支幾乎零成本;不可預測分支改 functional style 促成 cmov
load	2 個 load units → CPE ≥ k/2;位址相依鏈(linked list)使 CPE = load latency
store	fully pipelined;write/read dependency 同址時須等 store buffer 轉發
gprof	-pg 編譯 → 執行 → gprof;interval counting <1 秒不準,呼叫計數可靠
優化三層次	高階設計(演算法)→ 基本編碼原則 → 低階優化(unrolling、cmov)

公式

Latency bound:相依鏈延遲總和 T → 至少 T cycles
Throughput bound:N 次運算、C 個 units、issue time I → 至少 N·I/C cycles
每元素 k 次 load、2 個 load units → CPE ≥ k/2
list_len CPE = load latency = L1 存取時間 = 4 cycles
write_read(src==dst, cnt=n)淨效果:該位置 = n−1;critical path s_data→load→add ≈ 7 cycles
misprediction penalty ≈ 隨機資料 CPE − 可預測資料 CPE(minmax1:13.5 − 3.5 ≈ 20 cycles)
hash 平均負載 = entries/buckets(363,039/1,021 = 355.6)
加總式 hash 值域上限 ≤ 122n(n 為字串長度)
Amdahl's law: $S = 1 / ((1 - α) + α / k)$ ;瓶頸完全消除時 $S_{m a x} = 1 / (1 - α)$
$α = 203.7 / 209.0 = 0.974 \Rightarrow S_{m a x} \approx 39.0$ (實測 38.5)

6. 記憶體階層(The Memory Hierarchy)

儲存技術 → 儲存技術

概念	重點
SRAM vs DRAM	SRAM 六電晶體、免 refresh、快 ~10 倍貴 ~1000 倍(cache);DRAM 1 電容 1 電晶體(主記憶體)
DRAM 讀取	RAS 送列位址複製整列進 row buffer → CAS 送行位址取 supercell
磁碟存取	seek + rotational latency 支配;首 byte 貴、其餘幾乎免費
DMA + interrupt	CPU 下命令 → disk controller DMA 直寫記憶體 → 完成後 interrupt
SSD	flash + FTL;寫入須整 block 先抹除;wear leveling 延長壽命

公式

d×w DRAM 總容量 = d·w bits,supercell 陣列滿足 r·c = d,位址腳位需求 = max( $b_{r}$ , $b_{c}$ )
Capacity = (#bytes/sector) × (average #sectors/track) × (#tracks/surface) × (#surfaces/platter) × (#platters/disk)
$T_{m a x r o t a t i o n}$ = (1/RPM) × (60 secs/1 min)
$T_{a v g r o t a t i o n}$ = (1/2) × $T_{m a x r o t a t i o n}$
$T_{a v g t r a n s f e r}$ = (1/RPM) × (1/(average #sectors/track)) × (60 secs/1 min)
$T_{a c c e s s} = T_{a v g s e e k} + T_{a v g r o t a t i o n} + T_{a v g t r a n s f e r}$
磁碟存取時間粗估: $T_{a c c e s s} \approx 2 \times T_{a v g s e e k}$
Areal density (bits/in²) = recording density (bits/in) × track density (tracks/in)
SSD 壽命 ≈ 保證總寫入量(如 128 PB)÷ 持續寫入速率
Effective cycle time = 單顆 CPU cycle time ÷ processor cores 數
單位換算:DRAM/SRAM 容量 K/M/G/T = $2^{10} / 2^{20} / 2^{30} / 2^{40}$ ;disk 與 I/O K/M/G/T = $10^{3} / 10^{6} / 10^{9} / 10^{12}$ (相對差僅 ~7-10%)

區域性與記憶體階層 → 區域性與記憶體階層

概念	重點
兩種 locality	temporal(剛用過很快再用)與 spatial(鄰近位址很快被用)
stride	stride-1 空間區域性最佳;C 陣列 row-major,依列掃描才是 stride-1
階層中心思想	第 k 層是第 k+1 層的 cache,以 block 為傳輸單位;離 CPU 愈遠 block 愈大
三種 miss	cold(空 cache 必 miss)、conflict(映射同位置)、capacity(working set 過大)
管理者	registers 由 compiler、L1-L3 由硬體、virtual memory 由 OS + 硬體

公式

$P = f C V^{2}$ (功耗:f 時脈頻率、C 電容、V 電壓;power wall 與多核心的由來)
stride-k reference pattern:每隔 k 個元素存取一次;k=1 為 sequential,k 愈大 spatial locality 愈差
限制性 placement policy 範例:level k+1 的 block i → level k 的 block (i mod 4)
Practice 6.6 外推:2005-2015 磁碟單價降 166 倍 ≈ 每 18 個月減半;$30,000/PB (2015) 經約 8 次減半 → 約 2027 年降至 $200

快取記憶體 → 快取記憶體

概念	重點
(S, E, B, m)	S 個 set、每 set E 條 line、每 line B bytes block;位址切 tag / set index / offset
三種組織	E=1 direct-mapped;1<E<C/B set associative;E=C/B fully associative(TLB)
conflict miss	2 的冪陣列交替存取互逐(thrashing);解法陣列尾端 padding B bytes
寫入策略	write-through + no-write-allocate 或 write-back + write-allocate(假設後者)
Core i7	L1 i/d 各 32KB 8-way(4 cy)、L2 256KB(10 cy)、L3 8MB 共享(40-75 cy);block 64B

公式

$C = S \times E \times B$
$S = 2^{s}, B = 2^{b}, M = 2^{m}$
$s = \log_{2} S, b = \log_{2} B, m = \log_{2} M$
$t = m - (s + b)$
$S = C / (E \times B)$
miss rate = #misses / #references
hit rate = 1 − miss rate
direct-mapped:E = 1;E-way set associative:1 < E < C/B;fully associative:E = C/B

快取友善程式碼與記憶體山 → 快取友善程式碼與記憶體山

概念	重點
兩原則	讓 common case 快(專注 inner loop)+ 最小化 inner loop 的 cache miss
memory mountain	throughput 對 size(temporal)與 stride(spatial)的 2D 函數;四條稜線 = L1/L2/L3/Mem
prefetching	stride-1 平坦稜線來自 hardware prefetch,自動辨識循序模式
矩陣乘法	六版本分 AB(1.25)/ AC(2.00)/ BC(0.50)misses/iter;BC 最快近 40 倍
三守則	專注 inner loops、stride-1 循序讀、資料重複使用最大化 temporal locality

公式

misses per iteration = min(1, (word_size × k) / B)(stride-k 參照)
read throughput = n / s(讀 n bytes 花 s 秒,MB/s 以 $10^{6}$ bytes/s 計)
MB/s = (size / stride) / (cycles / MHz)(run 函式的轉換式)
$C = S \times E \times B$ (快取容量 = set 數 × 每 set line 數 × block 大小)
L1 讀取延遲估計:cycles ≈ (MHz / MB/s) × bytes = 2100/12000 × 16 ≈ 2.8 ≈ 3 cycles(P6.21)
矩陣乘法 misses/iter:class AB = 1.25、class AC = 2.00、class BC = 0.50
miss rate = misses / references(如 P6.18:1024/2048 = 50%)

7. 連結(Linking)

靜態連結與目的檔 → 靜態連結與目的檔

概念	重點
linker 兩大任務	symbol resolution(參照對應恰好一個定義)+ relocation(指派位址並修補參照)
目的檔三形式	relocatable / executable / shared;Linux 用 ELF 格式
section 分配	已初始化全域 → .data;未初始化全域 → COMMON;static 未初始化與初始化為 0 → .bss(不占檔案空間)
符號三類	global(本模組定義)、external(他模組定義)、local(static 僅模組內可見)
偽節	ABS、UNDEF、COMMON 只存在於 relocatable object file

(本筆記無公式)

符號解析與重定位 → 符號解析與重定位

概念	重點
強弱符號	函式與已初始化全域 = strong;未初始化全域 = weak
三規則	Rule 1 多強 → 錯誤;Rule 2 一強多弱 → 選強(無提示!);Rule 3 多弱 → 任選
靜態函式庫	archive (.a);linker 只複製被參照的 member;命令列順序有意義,函式庫放尾端
E/U/D 三集合	E 併入執行檔、U 未解析、D 已定義;掃描完 U 非空即報錯
relocation entry	Elf64_Rela = {offset, type, symbol, addend};放 .rel.text / .rel.data

公式

R_X86_64_PC32(PC 相對):*refptr = (unsigned)(ADDR(r.symbol) + r.addend − refaddr),其中 refaddr = ADDR(s) + r.offset
R_X86_64_32(絕對):*refptr = (unsigned)(ADDR(r.symbol) + r.addend)
執行期驗證:PC(call 下一條指令位址)+ 編碼位移 = 目標位址;addend = −4 補償參照起點與 PC 的 4-byte 差
small code model 假設:code + data 總大小 < 2 GB(gcc 預設,32 位元定址即足夠)

可執行檔載入與動態連結 → 可執行檔載入與動態連結

概念	重點
可執行檔差異	多 entry point、program header table、.init;少 .rel sections(已完全重定位)
啟動流程	execve → loader → entry point `_start`(crt1.o)→ `__libc_start_main` → main
shared library	.so 兩層共享:檔案系統僅一份、記憶體 .text 單一複本;gcc -shared -fpic
dynamic linker	loader 見 .interp section 先執行 ld-linux.so 完成三項 relocation
PIC	資料引用經 GOT(data segment、8-byte entry);函式呼叫用 PLT + lazy binding

公式

segment 對齊條件: $v a d d r mod a l i g n = o f f mod a l i g n$ (align = $2^{21}$ = 0x200000)
.bss 大小 = memsz − filesz(執行時清零、不佔檔案空間)
code segment 起始於 0x400000;stack 自 $2^{48} - 1$ 向下成長; $2^{48}$ 以上為 kernel
lazy binding:第一次呼叫 PLT[2] → GOT[4](指回 PLT[2] 第二條指令)→ push ID → PLT[0] → dynamic linker 覆寫 GOT[4];之後 PLT[2] → GOT[4] 直達函式(僅多 1 條指令 + 1 次記憶體間接引用)

函式庫插入與目的檔工具 → 函式庫插入與目的檔工具

概念	重點
interpositioning	攔截 shared library 函式呼叫,改執行同 prototype 的 wrapper
三種時機	compile-time(巨集 + -I.)、link-time(--wrap f)、run-time(LD_PRELOAD)
dlsym	run-time wrapper 用 dlsym(RTLD_NEXT, "malloc") 取真版本,否則無限遞迴
binutils	ar、strings、strip、nm、size、readelf、objdump(反組譯);ldd 列 shared libraries

公式

--wrap f:reference to f → __wrap_f;reference to __real_f → f
#define malloc(size) mymalloc(size);#define free(ptr) myfree(ptr)
-Wl,--wrap,malloc → 傳給 linker 的內容為 --wrap malloc(逗號換空格)
mallocp = dlsym(RTLD_NEXT, "malloc")(取得搜尋順序中下一個 malloc 的位址)
gcc -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl(建 run-time wrapper shared library)

8. 例外控制流(Exceptional Control Flow)

例外 → 例外

概念	重點
exception	對 processor state 變化的回應;經 exception table 呼叫 handler;結果:回 I_curr / I_next / abort
四大類	Interrupt(async,回 I_next)、Trap(蓄意,回 I_next)、Fault(可能重執行 I_curr)、Abort(永不返回)
system call	trap 是 user 進入 kernel mode 的受控入口;跑 kernel mode、用 kernel stack
常考編號	divide error=0、GPF=13、page fault=14、machine check=18;syscall:read=0, write=1, fork=57, execve=59, _exit=60

公式

handler 位址 = exception table base register + k × 8(k 為 exception number)
syscall 錯誤判斷:回傳值 r 滿足 $- 4095 \leq r \leq - 1$ ⇒ 錯誤,errno = −r
syscall 參數順序:%rax=編號;arg1..arg6 = %rdi, %rsi, %rdx, %r10, %r8, %r9;回傳值在 %rax

行程與上下文切換 → 行程與上下文切換

概念	重點
process 定義	執行中程式的實例,在 context 中執行;兩大抽象:獨立邏輯控制流 + 私有位址空間
concurrent vs parallel	兩流時間區間重疊即 concurrent(與核心數無關);parallel 是其真子集(不同 core/機器)
user/kernel mode	mode bit 控制;唯一升權途徑是例外(interrupt/fault/trap);違規 → fatal protection fault
context switch	三步驟:save 舊 context → restore 新 context → pass control;由 scheduler 決策
kernel 非行程	kernel 永遠「代表某行程」執行,切換中只是代表的對象改變

公式

n-bit 機器 address space = $2^{n}$ 個位址: $0 \sim 2^{n} - 1$
x86-64 Linux code segment 固定起始於 0x400000;kernel 佔 $2^{48}$ 以上
concurrent 判斷:X 與 Y 並行 ⟺ 兩者執行時間區間重疊

Unix 錯誤處理 → Unix 錯誤處理

概念	重點
Unix-style	回傳 −1 + 設 errno;strerror(errno) 轉文字;錯誤碼與有用結果重載同一回傳值
Posix-style	回傳 0 成功 / 非零即錯誤碼;結果由參考引數帶回;用 strerror(retcode)
GAI-style	getaddrinfo 系:非零 + gai_strerror(retcode),不能用 strerror
wrapper 慣例	首字母大寫 Foo:失敗印訊息後 exit,成功行為與基底完全相同(csapp.c/h)

(本筆記無公式)

行程控制 → 行程控制

概念	重點
fork	call once, return twice:子得 0、父得子 PID;位址空間相同但獨立副本;共享 open file descriptors
回收	終止未被 reap = zombie;init(PID 1)收養孤兒;wait(&s) ≡ waitpid(-1, &s, 0)
waitpid	pid>0 等單一子、pid=-1 等全部;WNOHANG 不阻塞回 0;WIFEXITED/WEXITSTATUS 判讀 status
execve	call once, never return(成功);覆寫位址空間但 PID 不變、file descriptor 保留
shell	eval:parseline → builtin? → Fork + execve;前景 waitpid、背景不等(需 SIGCHLD 回收)

公式

n 個連續 fork 產生 $2^{n}$ 個行程;可行輸出 = process graph 的 topological sort
wait(&status) ≡ waitpid(-1, &status, 0)
waitpid 錯誤:無子行程 → −1 且 errno=ECHILD;被 signal 中斷 → −1 且 errno=EINTR
sleep 回傳剩餘未睡足秒數(0 = 睡足);pause 永遠回傳 −1
main 三引數暫存器:argc → %rdi、argv → %rsi、envp → %rdx
新檔權限判讀巨集:WIFEXITED → WEXITSTATUS;WIFSIGNALED → WTERMSIG;WIFSTOPPED → WSTOPSIG

訊號 → 訊號

概念	重點
pending 不排隊	同型別至多一個 pending,多的直接丟棄;訊號不能計數事件;SIGCHLD handler 須 while(waitpid(...)>0)
不可攔截	SIGKILL (9) 與 SIGSTOP (19) 不能 catch/ignore
傳送	kill(pid,sig):pid=0 送自己群組全部、pid<0 送群組 \|pid\|;Ctrl+C/Ctrl+Z 送前景 process group
handler 準則	G0 簡單、G1 只用 async-signal-safe(printf 不安全,用 write/Sio)、G2 保存 errno、G3 阻擋訊號、G4 volatile、G5 sig_atomic_t
race 消除	fork 前阻擋 SIGCHLD、addjob 後解除;子行程先解除再 execve;等訊號用 sigsuspend

公式

接收時機:kernel → user mode 時檢查 pending & ~blocked,非空則接收(通常最小編號 k)
sigprocmask:SIG_BLOCK → blocked = blocked | set;SIG_UNBLOCK → blocked = blocked & ~set;SIG_SETMASK → blocked = set
sigsuspend(&mask) ≡ 原子版 sigprocmask(SIG_BLOCK,&mask,&prev); pause(); sigprocmask(SIG_SETMASK,&prev,NULL);
alarm(secs) 回傳前一個 pending alarm 的剩餘秒數(並取消它);無則 0
標準旗標宣告:volatile sig_atomic_t flag;(僅單次讀寫是原子,flag++ 不是)

非區域跳轉 → 非區域跳轉

概念	重點
setjmp/longjmp	setjmp 呼叫一次、回傳多次(初次 0);longjmp 呼叫一次、永不回傳
應用	深層巢狀錯誤直接跳回集中 handler(小心 memory leak);signal handler 內 soft restart 用 sigsetjmp/siglongjmp
限制	`rc = setjmp(env)` 是錯誤寫法;siglongjmp 可達的程式碼只能呼叫 async-signal-safe 函式
對應	C++/Java 的 try-catch ≈ setjmp、throw ≈ longjmp;ECF 四層:硬體 exceptions → OS processes → signals → nonlocal jumps

公式

setjmp 保存 calling environment(PC、stack pointer、general-purpose registers);初次回 0、經 longjmp 回非零 retval
sigsetjmp(buf, savesigs):savesigs 非零時另存 signal context(pending / blocked vectors)
工具對照:strace(system call trace)、ps(含 zombies)、top、pmap(memory map)、/proc

9. 虛擬記憶體(Virtual Memory)

位址空間與 VM 快取機制 → 位址空間與 VM 快取機制

概念	重點
虛擬定址	CPU 產生 VA,MMU 即時翻譯成 PA;page table 存主記憶體、由 OS 維護
VM = disk 的 DRAM cache	巨大 miss 成本 → fully associative + write-back + 大 page(4 KB–2 MB)
PTE 判讀	valid=1 → Cached;valid=0 + null → Unallocated;valid=0 + disk 位址 → Uncached
page fault	DRAM cache miss;handler 換頁後重新執行 faulting instruction;demand paging
working set	放得進實體記憶體就高效;放不下 → thrashing

公式

$N = 2^{n}$ (虛擬位址空間大小);最大虛擬位址 $= N - 1 = 2^{n} - 1$
$M = 2^{m}$ (實體位址空間,簡化假設); $P = 2^{p}$ (頁大小)
$# V P = N / P = 2^{n - p}$ = PTE 數量; $# P P = M / P = 2^{m - p}$

VM 記憶體管理與保護 → VM 記憶體管理與保護

概念	重點
每行程一張表	一個 process = 一張 page table = 一個獨立虛擬位址空間;隔離是預設、共享是例外
簡化四事	linking(統一映像、code 起於 0x400000)、loading(零複製,demand paging)、sharing(多 VP 映同一 PP)、allocation(連續虛擬頁映任意實體頁)
權限位元	PTE 加 SUP / READ / WRITE,每次轉譯時硬體順路檢查,零額外成本
違規流程	general protection fault → kernel handler → SIGSEGV → "segmentation fault"

公式

權限判斷:user mode 只能存取 SUP=No 的頁;kernel mode 可存取任何頁;再依 READ / WRITE 各自判定
loader 載入零複製:只建 PTE 指向目的檔並標 invalid,首次參照才 page fault 換入

位址轉譯與 TLB → 位址轉譯與 TLB

概念	重點
轉譯機制	PTBR 找 page table,VPN 索引 PTE,PPN 串接 VPO 得 PA;PPO = VPO 免轉譯
TLB	MMU 內小型 virtually addressed PTE cache;hit 全在晶片內完成
多層 page table	null 上層 PTE → 子表不存在;只有 level 1 須常駐;TLB cache 各層 PTE
Core i7	48-bit VA、52-bit PA;4 層表;CR3 存 L1 表基底(屬行程 context);A/D bit 由 MMU 設、kernel 清
Linux VM	task_struct → mm_struct(pgd, mmap)→ vm_area_struct 串列;page fault 三段檢查:area? → 權限? → 正常換頁

公式

$MAP : VAS \to PAS \cup \emptyset$
VA = VPN + VPO;PA = PPN + PPO;VPO = PPO = $\log_{2} P$ ;VPN = $n - p$ bits;PPN = $m - p$ bits
TLB 有 $T = 2^{t}$ 個 set:TLBI = VPN 最低 t 位;TLBT = VPN 其餘高位
單層表大小例:32-bit、4 KB 頁、4B PTE → $2^{32} / 2^{12} \times 4 B = 4$ MB(多層化的動機)
Core i7:36-bit VPN 切 4 × 9 bits、VPO = 12 bits;PA 切 CT(40) | CI(6) | CO(6)
End-to-end 例(n=14, m=12, P=64):VPN=8、VPO=PPO=6、PPN=6;TLBI=2、TLBT=6;CO=2、CI=4、CT=6

記憶體映射 → 記憶體映射

概念	重點
兩種來源	regular file 與 anonymous file(demand-zero pages,無實際磁碟傳輸)
shared vs private	shared object 實體僅一份、寫入可見並回寫;private 用 copy-on-write,只複製被寫的那頁
fork	複製 mm_struct/area/page tables,雙方頁標 read-only + private COW,不立即複製
execve 四步	刪舊 user areas → 映射 private areas → 映射 shared areas → 設 PC 指 entry point

公式

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset) — 成功回傳映射區指標,失敗回傳 MAP_FAILED (−1)
int munmap(void *start, size_t length) — 成功回傳 0,失敗回傳 −1
bufp = Mmap(NULL, size, PROT_READ, MAP_PRIVATE|MAP_ANON, 0, 0) — 建立唯讀、私有、demand-zero 區域

動態記憶體配置 → 動態記憶體配置

概念	重點
heap	demand-zero 區域,brk 指標記錄頂端;allocator 分 explicit(malloc/free)與 implicit(GC)
碎片化	internal(block > payload)易量化;external(總量夠但無單一夠大 free block)難量化
implicit free list	header = size \| alloc;prologue/epilogue 消除邊界條件;搜尋線性
boundary tags	footer 為 header 複本,使合併前一 block 為常數時間(四種 case)
進階組織	explicit free list(pred/succ)、segregated fits(GNU malloc)、buddy system

公式

$U_{k} = max_{i \leq k} P_{i} / H_{k}$ (peak utilization; $P_{k}$ = aggregate payload, $H_{k}$ = heap 大小)
header = block_size | alloc_bit(例:0x18 | 0x1 = 0x19;0x28 | 0x0 = 0x28)
GET_SIZE(p) = GET(p) & ~0x7;GET_ALLOC(p) = GET(p) & 0x1
HDRP(bp) = bp - WSIZE;FTRP(bp) = bp + GET_SIZE(HDRP(bp)) - DSIZE
NEXT_BLKP(bp) = bp + GET_SIZE(bp - WSIZE);PREV_BLKP(bp) = bp - GET_SIZE(bp - DSIZE)
asize = (size <= DSIZE) ? 2*DSIZE : DSIZE * ((size + DSIZE + (DSIZE-1)) / DSIZE)
extend_heap 對齊:size = (words % 2) ? (words+1)*WSIZE : words*WSIZE
extendsize = MAX(asize, CHUNKSIZE),CHUNKSIZE = 1<<12
internal fragmentation = Σ(block size − payload)
buddy 位址:size $2^{k}$ 、位址 xxx...x00000 → buddy 在 xxx...x10000(恰差一個 bit)

垃圾回收與記憶體錯誤 → 垃圾回收與記憶體錯誤

概念	重點
可達圖	root nodes(暫存器、stack、全域)指向 heap nodes;不可達的已配置區塊 = garbage
Mark&Sweep	mark 遞迴標記可達;sweep 線性掃 heap free 未標記者;works in place 適合 C
conservative GC	C 記憶體不帶型別,int 可偽裝成指標 → 只能保守標記,可能漏收
經典 bug	scanf 忘 &、heap 不清零、sizeof 誤用、*size--、指標算術單位、回傳區域變數位址、memory leak

公式

node p is reachable ⟺ 存在從任一 root node 到 p 的有向路徑;garbage = unreachable 的已配置區塊
mark 後:已配置且未標記 ⇒ 不可達 ⇒ garbage(sweep 階段 free)
buddy system:buddy 位址 = addr XOR size,與原區塊位址恰差一個 bit( $2^{k}$ 區塊,heap 為 $2^{m}$ 字組,每個 size class $2^{k}$ 、 $0 \leq k \leq m$ )

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

Unix I/O 與檔案 → Unix I/O 與檔案

概念	重點
統一模型	所有裝置皆檔案(位元組序列),open/read/write/close 統一操作
descriptor	open 回傳目前未開啟的最小非負整數;0=stdin、1=stdout、2=stderr
file position	kernel 維護 k;k ≥ m 時 read 回 0 = EOF(無 EOF 字元)
short count	不是錯誤;成因:EOF、終端機逐行、socket/pipe 緩衝;網路程式須反覆 read/write
open flags	O_RDONLY/O_WRONLY/O_RDWR 三選一,可 OR O_CREAT/O_TRUNC/O_APPEND

公式

檔案 = 位元組序列 $B_{0}, B_{1}, \dots, B_{k}, \dots, B_{m - 1}$ (大小 m bytes)
EOF 條件:file position k ≥ m 時執行 read
新檔權限 permission = mode & ~umask
read 回傳值語意:> 0 實際位元組數;0 = EOF;−1 = error
write 回傳值語意:> 0 實際寫入位元組數;−1 = error

RIO 套件與檔案中繼資料 → RIO 套件與檔案中繼資料

概念	重點
RIO	自動處理 short count 與 EINTR 重啟;rio_readn/rio_writen 無緩衝、rio_readlineb/rio_readnb 緩衝
混用限制	緩衝函式可互相交錯,但不可與無緩衝 rio_readn 混用同一 descriptor
stat/fstat	填 struct stat;重點 st_mode(權限+類型)與 st_size
readdir	錯誤與 end-of-stream 都回 NULL:呼叫前 errno=0、結束後檢查 errno

公式

rio_readn 回傳值 = n − nleft(≥0;EOF 時為 short count)
rio_readlineb 最多讀 maxlen−1 bytes(保留 1 byte 給結尾 NULL)
rio_read 複製量 cnt = min(n, rp->rio_cnt)
RIO_BUFSIZE = 8192 bytes
檔案類型判斷:S_ISREG(m) / S_ISDIR(m) / S_ISSOCK(m)
擁有者讀取權限檢查:st_mode & S_IRUSR

概念	重點
三張表	descriptor table(每 process)、open file table(共享,含 position 與 refcnt)、v-node table
fork	子複製 descriptor table,父子共享 file table entry(共享 position),refcnt 加倍
dup2	複製 oldfd → newfd;shell 的 > 重導向即靠此
三守則	G1 磁碟/終端機用 standard I/O;G2 binary 檔勿用 scanf/rio_readlineb;G3 socket 一律用 RIO(lseek 非法)

公式

int dup2(int oldfd, int newfd) — 成功回傳非負 descriptor,錯誤 −1;複製方向 oldfd → newfd
重導向 stdin 到 fd 5:dup2(5, 0) 即 dup2(5, STDIN_FILENO)
file table entry 刪除條件:refcnt == 0(close 一次 refcnt 減 1)

11. 網路程式設計(Network Programming)

主從式模型與網路 → 主從式模型與網路

概念	重點
transaction 四步	client 送 request → server 處理 → server 回 response → client 處理
process 而非機器	client/server 是 process;一台 host 可同時跑多個;網路對 host 只是另一個 I/O device
網路階層	Ethernet segment(hub)→ bridged LAN → WAN → internet(router)
encapsulation	LAN frame 的 payload 是 internet packet,packet 的 payload 才是使用者資料

公式

frame = frame header (source addr + dest addr + frame length) + payload
packet = packet header (packet size + source/dest internet addresses) + payload
LAN frame payload = internet packet;internet packet payload = user data(encapsulation)

全球 IP 網際網路 → 全球 IP 網際網路

概念	重點
TCP/IP 分層	IP 不可靠 host-to-host;UDP 擴到 process(仍不可靠);TCP 可靠 full-duplex 連線
IP address	unsigned 32-bit,network byte order(big-endian);htonl/ntohl、htons/ntohs 轉換
DNS	分散式資料庫,域名 ↔ IP 多對多;localhost → 127.0.0.1
connection	point-to-point、full duplex、reliable;client 用 ephemeral port、server 用 well-known port

公式

socket address = address:port
socket pair = (cliaddr:cliport, servaddr:servport) 唯一識別一條 connection
dotted-decimal 轉換:每 byte 十進位,如 128.2.194.242 = 0x8002c2f2
uint32_t htonl(uint32_t) / uint32_t ntohl(uint32_t);uint16_t htons(uint16_t) / uint16_t ntohs(uint16_t)
int inet_pton(AF_INET, const char *src, void *dst) → 1 OK / 0 非法 / −1 錯誤
const char *inet_ntop(AF_INET, const void *src, char *dst, socklen_t size) → 字串指標或 NULL

Socket 介面 → Socket 介面

概念	重點
建線流程	client:socket → connect;server:socket → bind → listen → accept
兩種 descriptor	listening(活整個生命期)vs connected(每次 accept 建立)——支援 concurrent server
getaddrinfo	字串 → addrinfo linked list,走訪至成功;protocol-independent、reentrant;錯誤用 gai_strerror
open_listenfd	setsockopt(SO_REUSEADDR) 消除 Address already in use
EOF	不是字元,是 kernel 偵測的條件;read/rio_readlineb 回 0 得知

公式

socket pair:(x:y, addr.sin_addr:addr.sin_port) — x 為 client IP,y 為 ephemeral port
clientfd = Socket(AF_INET, SOCK_STREAM, 0)
addrlen = sizeof(sockaddr_in)(IPv4);server 端 accept 用 sizeof(struct sockaddr_storage)
EOF 判斷式:read()/rio_readlineb() 回傳 0
hints.ai_flags = AI_NUMERICSERV | AI_ADDRCONFIG(client);AI_PASSIVE | AI_ADDRCONFIG | AI_NUMERICSERV(server)

Web 伺服器與 Tiny → Web 伺服器與 Tiny

概念	重點
HTTP	文字式協定,每行以 CRLF 結尾;request line = method URI version
內容	static 讀磁碟檔;dynamic 執行 CGI 程式:fork → setenv QUERY_STRING → dup2 → execve
status codes	200 OK / 301 Moved / 400 Bad request / 403 Forbidden / 404 Not found / 501 Not implemented / 505 Version not supported
Tiny	~250 行 iterative HTTP/1.0,只支援 GET;serve_static 用 mmap + Close + Rio_writen + Munmap
SIGPIPE	對已關閉連線第二次 write 觸發 SIGPIPE;忽略後 write 回 −1 且 errno=EPIPE

(本筆記無公式)

12. 並行程式設計(Concurrent Programming)

行程與事件驅動並行 → 行程與事件驅動並行

概念	重點
三種途徑	processes(kernel 排程、私有空間)、I/O multiplexing(自行排程、單行程)、threads(混合)
process-based	accept 後 fork;child close listenfd、parent close connfd;SIGCHLD 用 while 迴圈收割
select	阻塞至 read set 有描述子 ready;有副作用,每輪前須 ready_set = read_set
event-driven	每邏輯流是狀態機;優點:排程控制、共享易、可 gdb;缺點:複雜、難用多核

公式

descriptor set 位元向量: $b_{n - 1}, \dots, b_{1}, b_{0}$ ,描述子 k ∈ 集合 ⟺ $b_{k} = 1$
int select(int n, fd_set *fdset, NULL, NULL, NULL) → 回傳 ready 描述子個數,−1 為錯誤;n 慣用 maxfd+1
描述子 k ready for reading ⟺ 讀取 1 byte 的請求不會阻塞
connfd refcount 追蹤:accept 0→1;fork 1→2;parent close 2→1;child 端關閉 1→0(連線終止)

執行緒 → 執行緒

概念	重點
thread context	TID、stack、SP、PC、暫存器、condition codes;code/data/heap/open files 全共享
pool of peers	無父子階層,任何 peer 可 kill/join 任何 peer;context switch 比 process 快
終止四途徑	routine return、pthread_exit、exit(殺整個 process)、pthread_cancel
detach	預設 joinable 須 reap;伺服器慣用 pthread_detach(pthread_self()) 自我分離
傳 connfd	必須各自 Malloc,傳區域變數位址會與下一次 accept race

(本筆記無公式)

共享變數與號誌 → 共享變數與號誌

概念	重點
shared 定義	變數的某個 instance 被多於一個 thread 參考;registers 永不共享、VM 永遠共享
cnt++ 三步	Load-Update-Store;交錯造成 lost update;progress graph 的 unsafe region
semaphore	非負整數;P 為零則掛起、非零原子遞減;V 遞增並重啟一個等待者
mutex / sbuf	mutex 初始 1(P=lock、V=unlock);bounded buffer:mutex=1、slots=n、items=0
prethreading	master producer accept + sbuf_insert;worker pool consumer sbuf_remove

公式

shared(v) ⟺ ∃ instance of v referenced by > 1 thread
badcnt 預期值:cnt = 2 × niters
cnt++ 分解: $H_{i} \to L_{i} \to U_{i} \to S_{i} \to T_{i}$ (僅 L,U,S 操作共享變數)
Semaphore invariant: $s \geq 0$ (正確初始化的 semaphore 永不為負)
P(s):s>0 → s←s−1 立即返回;s=0 → 掛起直到 V 重啟後 s←s−1
V(s):s←s+1,並恰好重啟一個阻塞於 P 的 thread
Mutex 初始值 = 1;Sbuf:slots 初始 = n,items 初始 = 0
sbuf 空判斷:front == rear;insert:buf[(++rear)%n]=item;remove:item=buf[(++front)%n]
forbidden region = {states : s < 0} ⊇ unsafe region

平行化與執行緒安全 → 平行化與執行緒安全

概念	重點
psum 教訓	同步開銷極貴:psum-mutex 災難 → psum-array 免鎖 → psum-local 區域累加最快
四類 unsafe	(1) 不保護共享變數 (2) 跨呼叫 static state(rand/strtok)(3) 回傳 static 指標(ctime)(4) 呼叫 unsafe 者
reentrant	不引用 shared data,是 thread-safe 的真子集;Linux 提供 _r 版本
deadlock	mutex lock ordering rule:依 total ordering acquire、反序 release 即 deadlock-free
threads 數	超過核心數後 context switch 開銷微升 → 每核恰好一條 thread

公式

Speedup: $S_{p} = T_{1} / T_{p}$ (strong scaling;p 為核心數, $T_{k}$ 為 k 核執行時間)
Efficiency: $E_{p} = S_{p} / p = T_{1} / (p \cdot T_{p})$ ,百分比範圍 (0, 100]
平行加總驗證閉式解: $0 + 1 + \dots + (n - 1) = n (n - 1) / 2$
工作切分:nelems_per_thread = n / t;start = myid × nelems_per_thread;end = start + nelems_per_thread
Amdahl's Law(關聯): $S = 1 / ((1 - α) + α / k)$ ,上限 $1 / (1 - α)$

必背公式與判斷式

公式 / 判斷式	出處
$S = \frac{1}{(1 - α) + α / k}$ , $S_{\infty} = \frac{1}{1 - α}$ (Amdahl)	→ Amdahl 定律與並行主題
$U M a x = 2^{w} - 1$ ; $T M i n = - 2^{w - 1}$ ; $T M a x = 2^{w - 1} - 1$ ; $U M a x = 2 \cdot T M a x + 1$	→ 整數表示
$T 2 U_{w} (x) = x + 2^{w} (x < 0)$ ; $U 2 T_{w} (u) = u - 2^{w} (u > T M a x)$	→ 整數表示
unsigned 溢位: $s < x$ ;signed 溢位:兩正得非正 / 兩負得非負;`-x == ~x + 1`	→ 整數算術
signed 向零除法:`(x<0 ? x+(1<<k)-1 : x) >> k`; $⌈ x / y ⌉ = ⌊ (x + y - 1) / y ⌋$	→ 整數算術
$V = (- 1)^{s} M \cdot 2^{E}$ ; $B i a s = 2^{k - 1} - 1$ ;norm: $E = e - B i a s, M = 1 + f$ ;denorm: $E = 1 - B i a s, M = f$	→ 浮點數
$E A = I m m + R [r_{b}] + R [r_{i}] \cdot s$ , $s \in {1, 2, 4, 8}$	→ 資料搬移與算術運算
push:%rsp −= 8 再寫;pop:先讀再 %rsp += 8;call/ret 對 return address 同理	→ 程序與執行時堆疊
signed 比較用 `SF ^ OF` 組合;unsigned 用 CF/ZF;PC-relative target = 下一指令位址 + offset	→ 控制流
$& D [i] [j] = x_{D} + L (C \cdot i + j)$ (row-major,Eq. 3.1);對齊:K-byte 物件位址 ≡ 0 (mod K)	→ 陣列與異質資料結構
傳參順序:%rdi %rsi %rdx %rcx %r8 %r9;回傳 %rax;浮點走 %xmm0–7	→ 程序與執行時堆疊
Clock period = max(stage delay) + register delay;Throughput = 1/period	→ 管線化原理
$C P I = 1.0 + l p + m p + r p$ ;bubbles:load/use=1、mispredict=2、ret=3	→ PIPE 管線實作與冒險
$T = O v e r h e a d + C P E \times n$ ;latency bound CPE ≥ L、throughput bound CPE ≥ I/C	→ 現代處理器運作
k × k 展開 CPE ≈ L/k;達 throughput bound 需 $k \geq C \times L$	→ 迴圈展開與平行度
$C = S \times E \times B$ ; $t = m - (s + b)$ ;miss rate = misses/references	→ 快取記憶體
$T_{a c c e s s} = T_{s e e k} + T_{r o t a t i o n} + T_{t r a n s f e r} \approx 2 \times T_{a v g s e e k}$	→ 儲存技術
misses/iter = min(1, word_size × k / B)(stride-k)	→ 快取友善程式碼與記憶體山
強弱符號三規則:多強錯誤、一強多弱選強、多弱任選	→ 符號解析與重定位
PC32 重定位:`*refptr = ADDR(sym) + addend − (ADDR(s) + offset)`;絕對:`ADDR(sym) + addend`	→ 符號解析與重定位
$v a d d r mod a l i g n = o f f mod a l i g n$ ;.bss = memsz − filesz	→ 可執行檔載入與動態連結
handler 位址 = exception table base + k × 8;syscall 錯誤: $- 4095 \leq r \leq - 1$	→ 例外
n 個 fork → $2^{n}$ 個行程;可行輸出 = process graph 的 topological sort	→ 行程控制
接收檢查 `pending & ~blocked`;訊號不排隊;sigsuspend = 原子版 block+pause+restore	→ 訊號
setjmp 呼叫一次回傳多次(初次 0);longjmp 永不回傳	→ 非區域跳轉
#PTE = $2^{n - p}$ ;PA = PPN ‖ VPO;PPO = VPO;TLBI = VPN 低 t 位	→ 位址轉譯與 TLB
page fault:換頁後重新執行 faulting instruction;權限違規 → SIGSEGV	→ VM 記憶體管理與保護
$U_{k} = max_{i \leq k} P_{i} / H_{k}$ ;header = size \| alloc;asize 向上取整 16	→ 動態記憶體配置
permission = mode & ~umask;read 回 0 = EOF、−1 = error	→ Unix I/O 與檔案
dup2(oldfd, newfd);file table entry 刪除條件 refcnt == 0	→ 檔案共享、重導向與標準 I/O
socket pair (cliaddr:cliport, servaddr:servport) 唯一識別連線;htonl/ntohl 轉 byte order	→ 全球 IP 網際網路
P(s)/V(s) 語意與 semaphore invariant $s \geq 0$ ;sbuf:mutex=1、slots=n、items=0	→ 共享變數與號誌
$S_{p} = T_{1} / T_{p}$ ; $E_{p} = S_{p} / p$ ;lock ordering rule 免 deadlock	→ 平行化與執行緒安全

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

資訊表示與程式翻譯 → 資訊表示與程式翻譯

硬體組織與程式執行 → 硬體組織與程式執行

作業系統抽象與網路 → 作業系統抽象與網路

Amdahl 定律與並行主題 → Amdahl 定律與並行主題

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

資訊儲存與位元運算 → 資訊儲存與位元運算

整數表示 → 整數表示

整數算術 → 整數算術

浮點數 → 浮點數

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

程式編碼與資料格式 → 程式編碼與資料格式

資料搬移與算術運算 → 資料搬移與算術運算

控制流 → 控制流

程序與執行時堆疊 → 程序與執行時堆疊

陣列與異質資料結構 → 陣列與異質資料結構

緩衝區溢位與指標安全 → 緩衝區溢位與指標安全

浮點程式碼 → 浮點程式碼

4. 處理器架構(Processor Architecture)

Y86-64 指令集架構 → Y86-64 指令集架構

邏輯設計與 HCL → 邏輯設計與 HCL

循序 SEQ 實作 → 循序 SEQ 實作

管線化原理 → 管線化原理

PIPE 管線實作與冒險 → PIPE 管線實作與冒險

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

最佳化編譯器與其限制 → 最佳化編譯器與其限制

現代處理器運作 → 現代處理器運作

迴圈展開與平行度 → 迴圈展開與平行度

限制因素與記憶體效能 → 限制因素與記憶體效能

6. 記憶體階層(The Memory Hierarchy)

儲存技術 → 儲存技術

區域性與記憶體階層 → 區域性與記憶體階層

快取記憶體 → 快取記憶體

快取友善程式碼與記憶體山 → 快取友善程式碼與記憶體山

7. 連結(Linking)

靜態連結與目的檔 → 靜態連結與目的檔

符號解析與重定位 → 符號解析與重定位

可執行檔載入與動態連結 → 可執行檔載入與動態連結

函式庫插入與目的檔工具 → 函式庫插入與目的檔工具

8. 例外控制流(Exceptional Control Flow)

例外 → 例外

行程與上下文切換 → 行程與上下文切換

Unix 錯誤處理 → Unix 錯誤處理

行程控制 → 行程控制

訊號 → 訊號

非區域跳轉 → 非區域跳轉

9. 虛擬記憶體(Virtual Memory)

位址空間與 VM 快取機制 → 位址空間與 VM 快取機制

VM 記憶體管理與保護 → VM 記憶體管理與保護

位址轉譯與 TLB → 位址轉譯與 TLB

記憶體映射 → 記憶體映射

動態記憶體配置 → 動態記憶體配置

垃圾回收與記憶體錯誤 → 垃圾回收與記憶體錯誤

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

Unix I/O 與檔案 → Unix I/O 與檔案

RIO 套件與檔案中繼資料 → RIO 套件與檔案中繼資料

檔案共享、重導向與標準 I/O → 檔案共享、重導向與標準 I/O

11. 網路程式設計(Network Programming)

主從式模型與網路 → 主從式模型與網路

全球 IP 網際網路 → 全球 IP 網際網路

Socket 介面 → Socket 介面

Web 伺服器與 Tiny → Web 伺服器與 Tiny

12. 並行程式設計(Concurrent Programming)

行程與事件驅動並行 → 行程與事件驅動並行

執行緒 → 執行緒

共享變數與號誌 → 共享變數與號誌

平行化與執行緒安全 → 平行化與執行緒安全

必背公式與判斷式