111 年 國立中央大學資訊工程學系碩士班《作業系統與計算機組織》

核心觀念
本題測驗 Amdahl 定律（Amdahl’s Law），其核心公式：

$\text{Overall Speedup}= \frac{1}{(1-f)+\frac{f}{S}}$

• $f$：欲加速部份在原始系統中佔的執行比例（0 ≤ $f$ ≤ 1）。
• $S$：該部份被提升的速度倍率。
• 分母的 $(1-f)$ 代表未受提升的其餘部份仍以原速執行。

解題方法

1. 讀題得知
   • 模組佔系統執行時間的 40%，即 $f = 0.40$。
   • 模組提升 10 倍，即 $S = 10$。
2. 直接套入 Amdahl 公式：

四捨五入至小數點後兩位，得到 1.56。

選項分析

核心觀念

• 快取 (cache) 位址分為 Tag、Index、Offset 三段。
• Offset 位元數 = $\log_2(\text{block size})$，表示在一個快取區塊內的位址位移。
• Index 位元數 = $\log_2(\text{set 數目})$，決定資料放在哪一組 (set)。
• Tag 位元數 = 總位址長度 $-$ (Offset + Index)。

解題方法

1. 計算快取總區塊數：

2. 兩路組合快取 (2‑way set associative) 中，每組有 2 個區塊，故組數 (sets) 為

$\text{Set count}= \frac{4096}{2}=2048$

3. 計算 Offset、Index 位元數：

$\text{Offset bits}= \log_2 4 = 2$

$\text{Index bits}= \log_2 2048 = 11$

核心觀念

• CPI（Cycles Per Instruction）：每條指令在平均上需要的時脈週期數。
• 時脈週期時間 (Clock‑cycle time)：硬體時鐘的長度，單位為 ns。
• 流水線 (Pipelining) 的加速公式

• 理想 CPI = 1：在完整流水線且無阻塞的情況下，每個時脈週期正好完成一條指令。
• 流水線時脈額外開銷：每個時脈週期會因為分割與控制電路而多出 1 ns。

解題方法

1. 計算非流水線平均 CPI

$\text{CPI}_{\text{avg}} =0.30\cdot4+0.30\cdot5+0.40\cdot5=1.2+1.5+2.0 =4.7$

2. 求出非流水線每條指令的平均執行時間
   時脈週期 = 8 ns

$T_{\text{unpipe}} = \text{CPI}_{\text{avg}}\times 8\text{ ns}=4.7\times8=37.6\text{ ns}$

3. 流水線時脈週期
   原來 8 ns 加上 1 ns 的額外開銷 →

核心觀念

• fork() 的行為：呼叫 fork() 時，父行程會得到子行程的 PID（>0），而子行程會得到 0。父、子兩個行程皆會繼續執行 fork() 後面的程式碼。
• 進程數的遞增規則：每一次成功的 fork() 都會把現有的行程數 倍增。若在第 $k$ 次迴圈前已有 $N$ 個行程，執行一次成功的 fork() 後會變成 $2N$ 個行程。

解題方法

1. 初始狀態：執行 main() 的原始行程算作 1 個行程。
2. 迴圈次數：for (i=0;i<4;i++) 會執行 4 次。
3. 每次迴圈的行程數
   • 第 0 次迴圈前：$1$ 個行程 → fork() 後成 $2$ 個。
   • 第 1 次迴圈前：$2$ 個行程 → fork() 後成 $4$ 個。
   • 第 2 次迴圈前：$4$ 個行程 → fork() 後成 $8$ 個。
   • 第 3 次迴圈前：$8$ 個行程 → fork() 後成 $16$ 個。
4. 最終結果：迴圈結束後，系統中共 $2^{4}=16$ 個行程。

核心觀念

• 輪轉排程 (Round‑Robin, RR)：每個就緒程序在就緒佇列中依序取得固定長度的 時間片 (time quantum)。執行完時間片後若仍有剩餘 CPU 時間，程序會被重新放回佇列尾端。
• 等待時間 (Waiting Time)：$W_i = \text{完成時間}_i - \text{到達時間}_i - \text{CPU burst}_i$。即進程在就緒佇列中累積的等待長度。
• 平均等待時間：$t = \dfrac{\sum_i W_i}{n}$（$n$ 為流程數）。
• 上下文切換時間：題目假設接近 0，故可忽略不計。

解題方法

1. 依照到達時間建立就緒佇列，模擬每一次時間片的執行情況。
2. 記錄每個進程 開始執行的時間 與 最終完成的時間，計算個別等待時間。
3. 把四個等待時間加總除以 4，得到平均等待時間 $t$。

以下列出模擬過程（時間單位 = 秒）：

觀念與演算推導

頁面引用序列（共 14 次存取）：
$1, 5, 4, 6, 4, 1, 5, 4, 1, 6, 2, 3, 1, 6$
頁框數（Page Frames）$N = 3$，初始狀態皆為空。

1. FIFO (First-In, First-Out)

按頁面進入記憶體的先後順序淘汰最先進入者：

• 1, 5, 4：填入 $[1]$, $[1, 5]$, $[1, 5, 4]$ $\rightarrow$ 3 次 Page Fault
• 6：淘汰 $1 \rightarrow [5, 4, 6]$ $\rightarrow$ 1 次 Page Fault
• 4：命中 $[5, 4, 6]$
• 1：淘汰 $5 \rightarrow [4, 6, 1]$ $\rightarrow$ 1 次 Page Fault
• 5：淘汰 $4 \rightarrow [6, 1, 5]$ $\rightarrow$ 1 次 Page Fault
• 4：淘汰 $6 \rightarrow [1, 5, 4]$ $\rightarrow$ 1 次 Page Fault
• 1：命中 $[1, 5, 4]$
• 6：淘汰 $1 \rightarrow [5, 4, 6]$ $\rightarrow$ 1 次 Page Fault
• 2：淘汰 $5 \rightarrow [4, 6, 2]$ $\rightarrow$ 1 次 Page Fault
• 3：淘汰 $4 \rightarrow [6, 2, 3]$ $\rightarrow$ 1 次 Page Fault
• 1：淘汰 $6 \rightarrow [2, 3, 1]$ $\rightarrow$ 1 次 Page Fault
• 6：淘汰 $2 \rightarrow [3, 1, 6]$ $\rightarrow$ 1 次 Page Fault

FIFO 的 Page Fault 總數 $= 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 12$ 次（(a) 選項錯誤）。

2. Stack-based LRU (Least Recently Used)

淘汰最久未被使用的頁面：

• 1, 5, 4：填入 $[1]$, $[1, 5]$, $[1, 5, 4]$ $\rightarrow$ 3 次 Page Fault
• 6：最久未用者為 $1 \rightarrow$ 淘汰 $1 \rightarrow [5, 4, 6]$ $\rightarrow$ 1 次 Page Fault
• 4：命中 $\rightarrow$ 更新最近使用順序 $[5, 6, 4]$
• 1：最久未用者為 $5 \rightarrow$ 淘汰 $5 \rightarrow [6, 4, 1]$ $\rightarrow$ 1 次 Page Fault
• 5：最久未用者為 $6 \rightarrow$ 淘汰 $6 \rightarrow [4, 1, 5]$ $\rightarrow$ 1 次 Page Fault

核心觀念
本題測試對於虛擬化技術與執行環境的基本認識，涵蓋以下概念：

1. Kubernetes (K8s)：容器編排系統，負責自動化部署、伸縮與管理容器化應用。
2. Docker：提供 OS‑level container（容器）技術，利用 Linux namespaces 與 cgroups 進行資源隔離，並非硬體虛擬化。
3. Para‑virtualization（半虛擬化）：客體 OS 必須改寫，以配合 VMM（Virtual Machine Monitor）直接呼叫特權指令，進而提升效能，且可在不支援硬體虛擬化的舊型 x86 CPU 上運行，無需 binary translation。
4. Java Virtual Machine (JVM)：執行 Java bytecode 的抽象機，內建垃圾回收 (Garbage Collection) 機制，自動釋放不再使用的物件記憶體。

解題方法
逐一驗證每個選項的描述是否符合上述概念。若描述與概念相符則為真，若與概念相左則為偽。此類題目屬於概念辨識型，多數可直接以知識點對照判斷，不涉及計算或推導。

選項分析

• a) Kubernetes, also known as K8s, is a system for automating deployment, scaling, and management of containerized applications.
  ✔ 正確。Kubernetes 旨在提供容器的自動部署、水平伸縮、負載平衡與生命週期管理，與題述相符。

• b) Docker is a system that virtualizes hardware.
  ❌ 錯誤。Docker 採用 OS‑level container，僅在同一作業系統核心上提供資源隔離，並未虛擬化 CPU、記憶體或 I/O 等硬體層級。硬體虛擬化屬於如 VMware、KVM、Hyper‑V 等全虛擬化技術。

核心觀念

• 生產者─消費者問題：多個生產者與多個消費者共享 n 個緩衝區，需保證不會同時寫入或讀取同一緩衝區，且不會在緩衝區滿時寫入或在緩衝區空時讀取。
• 信號量（semaphore）：
  • empty 表示可供寫入的緩衝區數，初始值 = n。
  • full 表示已填滿的緩衝區數，初始值 = 0。
  • mutex 為二元信號量（互斎鎖），確保對緩衝區的 臨界區 只被一個執行緒同時存取。
• PV 操作：wait(S)（P）使信號量值減 1，若結果為負則阻塞；signal(S)（V）使值加 1，若有阻塞的執行緒則喚醒。

解題方法

1. 觀察 生產者程式 的 PV 操作順序：

   // produce item → nextp
   wait(empty);   // 必須有空緩衝區
   wait(mutex);   // 取得互斎鎖
   // 把 nextp 放入緩衝區
   signal(mutex); // 釋放互斎鎖
   signal(full);  // 增加已滿緩衝區計數
   

   • 先檢查 empty，再取得 mutex，寫入緩衝區，最後釋放 mutex 並通知 full。

2. 消費者 必須執行與之相反的動作，以避免競爭與死鎖：

   • 必須先確認 已有已滿的緩衝區（full），才能安全讀取。
   • 讀取前仍需取得 互斎鎖（mutex）保護臨界區。
   • 讀走一個項目後，釋放 互斎鎖，再告知 空緩衝區（empty）可供生產者使用。

3. 依照上述邏輯，將 wait 與 signal 依序映射到題目中缺少的兩個變數 V1、V2：

   • wait(V1) → 應為 wait(full)（檢查已滿緩衝區）。
   • wait(V2) → 應為 wait(mutex)（取得互斎鎖）。

這題考驗對單週期 CPU 資料路徑 (Datapath) 的理解，特別是其中各個元件的功能和連接。

分析圖示:
該圖展示了一個單週期 CPU 的資料路徑。我們需要逐一分析選項。

選項 a) Sending the value of PC register to an adder can determine the register number for rd (the register destination operand).

• PC (Program Counter) 暫存器儲存的是下一條指令的位址。
• PC 的值通常會傳送到一個加法器 (Add) 中，與分支位移量 (Branch offset) 相加，以計算出分支目標位址 (Branch Target Address)。
• rd (Register Destination) 是指令中用來指定目標暫存器的欄位，通常位於指令的 [15-11] 位元。
• PC 的值與 rd 是兩個不同的資訊來源，PC 的值不會用來直接決定 rd 的暫存器號碼。rd 的號碼直接從指令的特定欄位取出。
• 因此，選項 a) 是錯誤的。

選項 b) Performing "Sign extend" to the Instruction [15-0] produces an signed integer with 32 bits.

• 圖示中，Instruction [15-0] 被傳送到一個名為 "Sign extend" 的元件。
• "Sign extend" 的作用是將一個較短的有號整數擴展到一個較長的表示。通常，對於 16 位元的立即數 (immediate value)，如果最高位是 1，則前面會補上 1；如果最高位是 0，則前面補上 0。
• 指令的位址長度是 32 位元。Instruction [15-0] 是指指令的低 16 位元。
• "Sign extend" 元件的輸出是 32 位元。這個 32 位元的結果是將 16 位元的 Instruction [15-0] 進行符號擴展。
• 因此，選項 b) 是正確的。

**選項 c) Sending the Zero signal from the ALU to the AND gate determines whether Instruction[31

核心觀念

• IEEE‑754 二進位浮點格式由 符號位、指數位、尾數(又稱有效位或 significand) 組成。

• 真正的數值為

  $(-1)^{\text{sign}} \times 2^{\,E - \text{bias}} \times (1.\text{fraction})$

  其中 $E$ 為指數欄位的「未偏移」值，bias 為指數偏移量。

• 動態範圍 受指數位數決定：指數位越多，最大/最小指數的絕對值越大，範圍越寬。

• 精度 受有效位長度決定：有效位越多，二進位小數位的表示能力越高，精度越好。

解題方法

1. 先比較原 IEEE‑754 binary16（1‑5‑10）與新格式（1‑8‑7）的指數與有效位長度。
2. 計算兩者的指數範圍：
   • binary16：指數位 5，bias = 15，正常指數範圍 $E\in[1,30]$（$2^{E-15}$），最大正規化指數 $2^{15}$，最小正規化指數 $2^{-14}$。
   • 新格式：指數位 8，bias = 127，正常指數範圍 $E\in[1,254]$，最大 $2^{127}$，最小 $2^{-126}$。
3. 比較有效位長度：
   • binary16 有 10 位尾數 (隱含前導 1)，等效於 11 位二進位有效位。
   • 新格式只有 7 位尾數 (隱含前導 1)，等效於 8 位二進位有效位。
4. 依據 IEEE‑754 標準，將給定的 16 位二進位序列解讀為 binary16 與 新格式，分別計算其十進位值。

逐項選項分析

a) 新格式具有較大的動態範圍

• 如上計算，new format 的指數可達 $2^{127}$（正值）與 $2^{-126}$（負值），遠大於 binary16 的 $2^{15}$ 與 $2^{-14}$。
• 因此選項 a 正確。

核心觀念

• IEEE‑754 二進位浮點格式由 符號位、指數位、尾數(又稱有效位或 significand) 組成。

• 真正的數值為

  $(-1)^{\text{sign}} \times 2^{\,E - \text{bias}} \times (1.\text{fraction})$

  其中 $E$ 為指數欄位的「未偏移」值，bias 為指數偏移量。

• 動態範圍 受指數位數決定：指數位越多，最大/最小指數的絕對值越大，範圍越寬。

• 精度 受有效位長度決定：有效位越多，二進位小數位的表示能力越高，精度越好。

解題方法

1. 先比較原 IEEE‑754 binary16（1‑5‑10）與新格式（1‑8‑7）的指數與有效位長度。
2. 計算兩者的指數範圍：
   • binary16：指數位 5，bias = 15，正常指數範圍 $E\in[1,30]$（$2^{E-15}$），最大正規化指數 $2^{15}$，最小正規化指數 $2^{-14}$。
   • 新格式：指數位 8，bias = 127，正常指數範圍 $E\in[1,254]$，最大 $2^{127}$，最小 $2^{-126}$。
3. 比較有效位長度：
   • binary16 有 10 位尾數 (隱含前導 1)，等效於 11 位二進位有效位。
   • 新格式只有 7 位尾數 (隱含前導 1)，等效於 8 位二進位有效位。
4. 依據 IEEE‑754 標準，將給定的 16 位二進位序列解讀為 binary16 與 新格式，分別計算其十進位值。

逐項選項分析

a) 新格式具有較大的動態範圍

• 如上計算，new format 的指數可達 $2^{127}$（正值）與 $2^{-126}$（負值），遠大於 binary16 的 $2^{15}$ 與 $2^{-14}$。
• 因此選項 a 正確。

選項解析與觀念推導

• (a) 正確：包含性快取（Inclusive Cache）的定義即為高階快取（Top-level Cache，如 L1）內的所有資料區塊，皆必須同時存在於低階快取（Bottom-level Cache，如 L2/L3）中，亦即 $L1 \subseteq L2$。
• (b) 錯誤：當區塊 $A$ 自 L1 被驅逐（evict）時，L2 仍會保留該區塊。

核心觀念

1. 指令快取 (I‑cache) 與資料快取 (D‑cache) 的組織

   • 分離式 (Harvard)：I‑cache 與 D‑cache 各自佔有獨立的容量與存取埠，CPU 同時可以在同一個時脈週期取得指令與資料，避免結構衝突 (structural hazard)。
   • 統一式 (von Neumann)：指令與資料共用同一個 L1 快取，稱為 Unified Cache。兩類存取必須競爭同一個存取埠，且共享相同的容量。

2. 快取失效率 (miss rate)

   • 容量衝突 (capacity conflict)：當指令與資料同時佔用統一快取的容量時，彼此的快取行可能相互取代，導致原本在分離快取中較低的失率上升。
   • 結構危險 (structural hazard)：指令與資料同時發出存取需求但只有單一埠可供使用，必須排隊或延遲。

3. 合併與分離的影響

   • 合併 → 共享容量 ⇒ 失率可能上升（尤其是原本較低的 I‑cache 失率）。
   • 合併 → 單埠存取 ⇒ 結構危險增加。
   • 分離 → 各自擁有獨立埠與容量 ⇒ 減少結構危險，並允許 同時取指與取資料。

解題方法

• 先釐清題目所問的比較基準：

  • a、b 皆在比較「合併前」的 原始 I‑cache / D‑cache 失率 與「合併後」的 統一 L1 失率。
  • c、d 探討 存取路徑與結構危險，與快取是否分離直接相關。

• 依照上述核心概念判斷每個敘述的真偽：

  1. 容量衝突：合併後指令會被資料快取行取代，或相反，故 原本較低的 I‑cache 失率會變高。
  2. 資料失率：資料同樣受到指令佔用的干擾，不會降低，通常會升高。
  3. 存取路徑：分離的 I‑cache、D‑cache 各有獨立的讀取埠，可在同一週期同時存取。
  4. 結構危險：分離的兩個快取消除單埠衝突，確實可 降低 structural hazard。

選項分析

核心觀念

• 指令集設計與 CPU 實作：須理解不同指令類型（Memory‑Memory、Register‑Memory、Register‑Register）對硬體複雜度、CPI（Cycles Per Instruction）與實作方式的影響。
• 單循環 (single‑cycle) 與多循環 (multi‑cycle) CPU：單循環讓所有指令在同一個時脈內完成，時脈長度受最長路徑限制；多循環把指令分割成多個階段，可針對每個階段設較短時脈。
• 流水線 (pipeline)：將指令的不同階段交錯執行，前提是每個階段的時脈週期相對均衡，通常以多循環或 分段 設計為基礎。
• 動態排程 (dynamic scheduling)：硬體在執行期間解決資料相依與資源衝突，能隱藏記憶體延遲與處理編譯期無法預知的真實相依 (RAW)。

解題方法
本題為「哪一選項 不 正確」的多選題。逐一檢視每個敘述是否符合上述概念：

1. 判斷 動態排程 是否真的能隱藏 memory latency 與即時解決相依。
2. 確認 單循環 CPU 的時脈長度是否由「最長可能路徑」決定。
3. 比較 Register‑Register 與 Memory‑Memory / Register‑Memory 架構在 CPI 變異度 上的差異。
4. 判斷 RISC 是否已成為主流產品。
5. 評估 單循環 與 多循環 在實作流水線時的適用性。

只要找出與概念相左之處，即為「不正確」的選項。

選項分析

核心觀念

• Pipeline hazard（流水線危害）：在 CPU 流水線中，同時執行多條指令時因資源、資料相依或分支等因素而產生的衝突。主要分為三類

  1. Structural hazard（結構性危害） – 兩條指令同時需求相同硬體資源。
  2. Data hazard（資料相依危害） – 包括 RAW（Read‑After‑Write）、WAR（Write‑After‑Read）、WAW（Write‑After‑Write）。
  3. Control hazard（控制危害） – 分支指令的目標未知所致的流水線停頓。

• 編譯器排程（Instruction scheduling）：在編譯期重新排列指令順序，以避免或減少資料與結構性危害。

• 分離指令快取與資料快取：將 Instruction Cache（I‑cache）與 Data Cache（D‑cache）分開，可同時提供取指與存取資料的需求，降低因同時存取快取而產生的結構性危害。

• 暫存器重新命名（Register renaming）：在硬體層面將「邏輯暫存器」映射到較多的「實體暫存器」，消除 WAR 與 WAW 這類偽相依（false dependence），但 RAW（真相依）仍必須靠轉送（forwarding）或停頓解決。

解題方法

1. 釐清每個選項描述的危害類型與解決機制。
2. 逐一比對實務上常見的處理方式：
   • 編譯器排程 能避免 部分 結構/資料危害（如將相依指令間插入無相依指令）。
   • 分離快取 能減少因同時存取快取導致的 結構性危害。
   • 暫存器重新命名 能消除 WAR、WAW，但 RAW 仍需其他機制（forwarding、stall）。
3. 判斷每個敘述的真偽，並確認「None of the above」不成立（因為至少有正確選項）。

選項分析

核心觀念

• 快取 (Cache) 之組合度 (Associativity)：組合度越高，對同一組 (set) 的容納路徑越多，降低衝突失誤 (conflict miss)。但每一次查找必須比較更多個別路徑，會增加找命中時間 (hit time)。
• MIPS 分支指令之偏移量 (Branch Offset)：MIPS 使用 16 位元的 immediate 欄位，代表 指令位元組 (word) 的位移，左移兩位相當於乘以 4，因為每條指令長 4 位元組。這樣的編碼能在 16 位元的範圍內提供 $±2^{15}$ 個指令位移，即 $±2^{15}\times4$ 位元組的跳躍距離。
• 快取容量與命中率 (Hit Rate)：增大快取容量可容納更多資料區塊，理論上能減少容量失誤 (capacity miss)。但若工作集大小已小於原快取，或失誤主要來自衝突與壓縮失誤，單純擴大容量未必提升命中率。
• 流水線暫存寄存器 (Pipeline Registers)：每個流水線階段的輸入與輸出必須以暫存寄存器隔離，確保階段之間的時序獨立，避免資料競爭與冒險 (hazard)。
• MIPS 指令長度：所有 MIPS 指令固定為 32 位元 (4 位元組)，屬於 RISC 架構的特性，使解碼與指令對齊簡單。

解題方法
針對每個敘述逐一檢驗其正確性。檢查的依據包括：

1. 快取結構與組合度對失誤與存取時間的影響。
2. MIPS 指令編碼規則與分支偏移量的單位。
3. 快取容量變化對命中率的限制條件。
4. 流水線的硬體需求：是否必須有暫存寄存器。
5. MIPS 指令格式的固定長度。

選項分析

a) Increasing associativity of a cache would usually reduce the miss rate and the hit time.

• 失誤率：提升組合度確實能減少衝突失誤，因同一組可容納更多路徑，故 miss rate 多半下降。
• 命中時間：組合度提升意味每次查找必須同時檢查多個路徑，查找硬體 (如 CAM) 的比較次數增加，故 hit time 會上升，而非下降。
• 結論：此敘述的 hit time 部分錯誤，故 錯誤。

核心觀念

• Contention Scope (爭用範圍)：指當執行緒競爭 CPU 時所在的層級。
  • System Contention Scope (SCS)：執行緒由作業系統核心排程，所有核心層面的執行緒皆在同一個排程池中競爭。
  • Process Contention Scope (PCS)：執行緒在使用者層面排程，僅在同一個程序內的執行緒相互競爭，最終映射到少數（可能僅一個）核心執行緒。
• POSIX Pthreads 中的兩個範圍常量
  • PTHREAD_SCOPE_SYSTEM → SCS
  • PTHREAD_SCOPE_PROCESS → PCS
• 執行緒模型
  • One‑to‑One：每個使用者執行緒對應一個內核執行緒，排程全由核心完成 → 只使用 SCS。
  • Many‑to‑One：多個使用者執行緒映射到同一個內核執行緒，排程在使用者層完成 → 只使用 PCS。
  • Many‑to‑Many：同時支援兩種爭用範圍，可依需求混合使用。

解題方法

1. 依照題目關鍵字「contention scope」辨識每個敘述所描述的層級。
2. 依據 POSIX 定義與 Linux 實作檢視 PTHREAD_SCOPE_* 常量的支援情況。
3. 針對「one‑to‑one model」判斷其排程機制屬於哪個爭用範圍。
4. 逐一驗證選項的真假，若全部錯誤則選 e，否則列出正確的選項。

核心觀念 – Processor Affinity（CPU 親和性）
Processor affinity（亦稱 CPU affinity）是作業系統允許將行程或執行緒「綁定」到特定的 CPU（或 CPU 群組），使其在執行時盡量在同一顆處理器上跑。

• 硬（hard）affinity：對 CPU 的限制是「必須」的，作業系統不允許把行程排到 mask 以外的 CPU。
• 軟（soft）affinity：只是一種偏好（preference），系統會盡量安排在指定 CPU 上執行，但在需要平衡負載或資源不足時仍可搬移。
• 在多處理器、NUMA（Non‑Uniform Memory Access）架構中，CPU 與記憶體的距離不一致；將行程與其常用的記憶體區域所在的 CPU 綁定，可減少遠端存取延遲、提升快取命中率，這是 affinity 的主要效益之一。

解題方法
本題屬於多選題，要求判斷每個敘述的正確性。解題步驟：

1. 釐清「hard」與「soft」affinity 的定義與作業系統支援情形。
2. 思考 load balancing（負載平衡）機制的行為：在多核心系統中，OS 會自動將工作重新分配，以避免某些 CPU 過載，這會削弱 affinity 所帶來的局部性好處。
3. 考慮 記憶體架構（SMP、UMA、NUMA）與 affinity 的關係：在 NUMA 系統，CPU 與其本地記憶體的存取速度差異極大，affinity 可讓行程使用最近的記憶體，故架構會直接影響 affinity 的效益。
4. 檢視選項 d 的敘述，確認「soft affinity」是否與「軟體僅在特定站點可用」相關——這是對概念的誤解。

依上述步驟逐一驗證每一選項，即可得出正確答案。

選項分析

核心觀念

• 路由協定的分類：依照自治系統（AS）之間或之內的路由決策，可分為 iBGP（內部 BGP）與 eBGP（外部 BGP）。iBGP 用於同一個 AS 內部的路由器之間傳遞路由資訊；eBGP 則在不同 AS 之間交換路由。
• HTTPS／TLS：HTTP（HyperText Transfer Protocol）本身是明文傳輸，若要提供加密與認證，需要在其上層加上 TLS（Transport Layer Security），形成 HTTPS。TLS 為通訊協定，與 HTTP 本身的語意無關。
• ARP（Address Resolution Protocol）：ARP 用於在同一個局部網路 (LAN) 內，根據已知的 IP 位址查詢對應的 MAC 位址。ARP 需求在同一個網段內廣播請求（broadcast）給所有節點，接收方若匹配則回覆單播（unicast）其 MAC。
• ARP Spoofing（ARP 欺騙）：攻擊者偽造 ARP 回覆，將目標主機的 IP 位址對應到攻擊者自己的 MAC 位址，從而攔截或偽造流量。其本質即是 把 IP 地址錯誤地綁定到錯誤的 MAC 位址。

解題方法

1. 針對每個選項陳述的協定或機制，直接對照正式定義與常見實作。
2. 檢驗描述是否符合標準（如 BGP 的「intra‑AS」與「inter‑AS」屬性、HTTP 是否自行加密、ARP 請求的傳播方式、ARP spoofing 的攻擊流程）。
3. 若描述與標準不符，即為錯誤；若完全符合，則為正確。
4. 由於題目為「Choose the correct statements」，只要有至少一個正確選項即不須選 e) 「None of the above」。

選項分析

• a) The BGP protocol is an intra‑AS routing protocol.
  • BGP（Border Gateway Protocol）設計的目的正是 在不同自治系統之間交換路由資訊，屬於 外部路由協定（eBGP）。雖然同一 AS 內部也會使用 BGP（稱為 iBGP），但其本質仍是 跨 AS 的協定，不能稱為「intra‑AS routing protocol」。
  • 結論：錯誤。

核心觀念
本題考查作業系統中 執行緒 (thread)、行程 (process)、快取記憶體 (TLB) 以及 換頁 (paging) 與抖動 (thrashing) 的概念與相互關係。

• 執行緒與堆疊：同一行程中的每條執行緒都有各自的 stack（用於儲存函式呼叫的返回位址、區域變數等），但會共享行程的 程式碼段、資料段、堆積 (heap)。
• TLB (Translation Lookaside Buffer)：CPU 用於快取最近的虛擬頁面到實體頁面的映射，屬於每個 CPU 核心 的私有快取。若多個執行緒在同一行程上執行，只要它們在同一核心上，便可能共用同一組 TLB 條目；若在不同核心，則不會共享。
• 換頁與抖動：
  • Paging：系統將不活躍的頁面寫入磁碟，並在需要時重新載入。
  • Thrashing：當系統大部分時間花費在 頁面置換（paging）而非實際執行指令上時，稱為 thrashing。因此，thrashing 的判定是 執行時間大部分被 paging 所佔，而非「執行時間較多」的情形。
• 置換演算法：全域 (global) replacement 允許任何行程的頁面被淘汰，而 局部 (local) replacement 只在同一行程的頁面集合中挑選淘汰對象。局部演算法只能降低 內部 換頁率，無法根除因系統整體記憶體不足而產生的 thrashing。

解題方法
逐一檢驗每個選項的敘述是否符合上述概念。若敘述與定義直接矛盾，即為錯誤；若描述符合正確概念，則為正確。此題為多選題，允許一個或多個選項正確。

選項分析

• a) Threads that are part of the same process share the same stack
  錯誤。同一行程的執行緒必須擁有 獨立的 stack，以防止呼叫序列與局部變數互相干擾。行程內共享的是程式碼段、資料段與 heap，堆疊是執行緒私有資源。

核心觀念

1. 行程遷移（Process Migration）
   • 行程遷移是將執行中的行程從一台主機搬到另一台主機。常見的動機包括
     • 負載平衡：避免某台機器過載。
     • 資料存取局部性：將行程搬到靠近其需要頻繁存取的資料位置，以減少 I/O 延遲。
     • 容錯與資源回收：當原主機故障或需要釋放資源時。
2. UNIX Pipe 機制
   • Pipe 是一種 單向字節流 的進程間通信（IPC）方式，只能在已建立的父子或兄弟關係的兩個進程之間傳遞資料，並不提供將整個行程搬移至另一台機器的功能。
3. 模組化（Modularity）與行程合作
   • 模組化是系統設計的原則，將系統切割成功能獨立、界面明確的模組。若每個模組以獨立的行程實作，則必須 行程合作（cooperation）才能完成整體任務。因而模組化是促使行程合作的主要原因之一。
4. 共享記憶體（Shared Memory）
   • 共享記憶體是 直接在多個行程間映射同一段實體記憶體 的 IPC 模型，屬於 “訊息傳遞模型” 之外的 資料共享模型，常用於需要高效大量資料交換的合作行程。

解題方法

1. 先釐清每個選項所涉及的概念是否正確描述上述核心觀念。
2. 逐條驗證：
   • a → 資料存取是否為行程遷移的動機？ → 正確。
   • b → UNIX pipe 是否提供行程遷移機制？ → 錯誤。
   • c → 模組化是否是行程合作的原因？ → 正確。
   • d → 共享記憶體是否屬於 IPC 模型之一？ → 正確。
   • e → 若已找到正確選項，則 “None of the above” 只能在全部錯誤時成立，故必為錯。

選項分析