113 年 國立中山大學資訊工程學系碩士班甲組《作業系統與資料結構》

核心觀念

本題主要考察 C 語言中的運算子優先順序（Operator Precedence）、負數的二補數表示法（Two's Complement Representation）以及逐位元運算（Bitwise Operation）。

1. 二補數運算：在現代計算機架構中，有號整數採用二補數系統，$-d$ 等價於 $\sim d + 1$（位元反轉後加 1）。
2. 運算子優先順序：
   • 單元負號 -（優先級第 2 級）高於算術加法 +（優先級第 4 級）。
   • 括號內的算術加法 + 優先於逐位元與運算 &（優先級第 8 級）。
   • 因此，運算式 (-d+1) 是先計算負數 -d，再加上 $1$。

---

解題方法與步驟推導

題目要求計算以下敘述的輸出結果：

int d = 48;
printf("%d \n", (d & (-d + 1)) + 3);

步驟 1：寫出 $d = 48$ 的二進位表示

將十進位 $48$ 轉換為二進位（以 8 位元呈現即可清楚觀察低位元狀態，高位元均為 0 或符合符號擴展）：
$48 = 32 + 16 = (00110000)_2$

步驟 2：計算 $-d$ 與 $(-d + 1)$ 的值

在二補數表示法中，$-48$ 為位元反轉後加 1：
$\sim 48 = (11001111)_2$
$-48 = \sim 48 + 1 = (11010000)_2$

接著計算 $-d + 1$：
$-d + 1 = -48 + 1 = -47$
以二進位表示即為：
$(11010000)_2 + 1 = (11010001)_2$

核心觀念

本題的核心為分治法（Divide and Conquer）遞迴追蹤、遞迴樹後序遍歷（Post-order Traversal），以及具副作用（Side Effect）的重複函式呼叫陷阱。

1. 分治策略與遞迴基底：
   函式 max(left, right) 欲找出陣列區間 $[left, right]$ 內的最大值。當 $left = right$ 時觸發終止條件（Base Case），直接回傳 $x[mid]$；否則切分為左右兩半遞迴求解。
2. 後序輸出時機：
   輸出指令 cout << b << endl; 位於函式回傳前，因此子呼叫的結果必然先於父呼叫輸出（類似樹的後序遍歷）。
3. 重複呼叫的程式缺陷（陷阱關鍵）：
   在 else 分支中：

   if (c > max(mid+1, right))
       b = c;
   else
       b = max(mid+1, right);
   

   若條件 c > max(mid+1, right) 不成立（即左半部最大值不大於右半部），程式會進入 else 區塊，導致 max(mid+1, right) 被再次呼叫執行。每一次呼叫都會觸發其內部的 cout，產生重複輸出的副作用。

---

解題方法：詳細追蹤步驟

全域陣列之索引與數值對照如下：

• $x[0] = 8$
• $x[1] = 5$
• $x[2] = 3$
• $x[3] = 9$
• $x[4] = 7$
• $x[5] = 4$
• $x[6] = 6$
• $x[7] = 2$

主程式自 max(1, 5) 開始執行，以下依時間序列詳細推導遞迴呼叫與輸出歷程：

1. 執行 max(1, 5)

• 計算 $mid = \lfloor (1+5)/2 \rfloor = 3$。
• 進入 c = max(1, 3);。

2. 執行 max(1, 3)

• 計算 $mid = \lfloor (1+3)/2 \rfloor = 2$。
• 進入 c = max(1, 2);。

3. 執行 max(1, 2)

• 計算 $mid = \lfloor (1+2)/2 \rfloor = 1$。
• 進入 c = max(1, 1);。

4. 執行 max(1, 1)（第 1 次輸出）

• 觸發終止條件 $left == right$：$b = x[1] = 5$。
• 輸出：5，回傳 $5$。

5. 回到 max(1, 2) 評估條件式

• 此時 $c = 5$。
• 評估 if (c > max(2, 2))，呼叫 max(2, 2)。

6. 執行 max(2, 2)（第 2 次輸出）

• 觸發終止條件 $left == right$：$b = x[2] = 3$。
• 輸出：3，回傳 $3$。

7. 完成 max(1, 2)（第 3 次輸出）

• 條件判斷：$c > 3 \implies 5 > 3$ 成立（True）。
• 執行 $b = c = 5$。
• 輸出：5，回傳 $5$。

8. 回到 max(1, 3) 評估條件式

• 此時 $c = 5$。
• 評估 if (c > max(3, 3))，呼叫 max(3, 3)。

9. 第 1 次執行 max(3, 3)（第 4 次輸出）

• 觸發終止條件 $left == right$：$b = x[3] = 9$。
• 輸出：9，回傳 $9$。

10. max(1, 3) 條件不成立，進入 else 區塊

• 條件判斷：$c > 9 \implies 5 > 9$ 不成立（False）。
• 進入 else 區塊，執行 $b = \text{max}(mid+1, right)$，即再次呼叫 max(3, 3)。

11. 第 2 次執行 max(3, 3)（第 5 次輸出）

• 觸發終止條件 $left == right$：$b = x[3] = 9$。
• 輸出：9，回傳 $9$。

12. 完成 max(1, 3)（第 6 次輸出）

• 取得 $b = 9$。
• 輸出：9，回傳 $9$。

核心觀念
此題考查二維陣列的填充規則與數學歸納/分層概念。

• 觀察可得每一個元素所在的「層」(layer) 只與 $\max(i,j)$ 有關。
• 第 $k$ 層 (即 $\max(i,j)=k$) 包含 $2k+1$ 個格子，且這些格子依序沿 底列從左至右 再 右欄從下至上 填入遞增的非負整數。

解題方法

1. 確定層數

$L=\max(i,j)$

2. 計算前層的總格子數
   前 $L$ 層的格子數為

$1+3+5+\dots+(2L-1)=L^{2},$

因為奇數之和等於平方。因此在層 $L$ 的第一個格子之前已填入 $L^{2}$ 個數字，編號從 $0$ 開始，故層 $L$ 的起始值為 $L^{2}$。
3. 在層內定位

• 若 位於底列（$i=L$），則在底列的第 $j$ 個位置（$0\le j\le L$）填入

$N[i][j]=L^{2}+j.$

• 若 位於右欄（$j=L$，且 $i<L$），則在右欄從下往上第 $(L-i)$ 個位置填入

核心觀念
排序演算法的 穩定性 (stability) 指的是：若兩筆資料的關鍵字相等，演算法執行完畢後，它們在輸出序列中的相對次序必須與原始序列相同。判斷一個演算法是否穩定，須檢視在 比較與交換 的過程中是否會改變等值元素的相對順序。

---

解題方法

1. 回顧每個演算法的主要步驟，確認在什麼情況下會發生「交換」或「移動」相等鍵值的元素。
2. 判斷交換是否受鍵值相等影響：
   • 若交換僅依賴「鍵值大小」且不特別保護等值元素的相對次序，則可能不穩定。
   • 若演算法透過 相鄰比較（如 bubble）或 合併時保留左側先出（如 merge）等機制，則穩定。
3. 特別注意基數排序 (radix sort)：它是多輪“計數排序 (counting sort)”的組合，只在每一位上使用 穩定 的子排序，故整體亦為穩定。

---

選項分析

演算法	是否穩定	為什麼穩定 / 為什麼不穩定
Bubble Sort	穩定	每一次比較只涉及相鄰兩個元素，交換僅在左元素 > 右元素時發生。若相等則不交換，等值元素的相對順序不會改變。
Heap Sort	不穩定	建立 max‑heap 時，會把任意節點與其子節點交換，以維持堆的結構。交換的對象與鍵值大小無關，等值元素可能被搬到完全不同的子樹，導致相對次序改變。

核心觀念

每個 $2\times3$ 方塊共有 $6$ 個單位格。每種分解都由若干個 L 形三格拼塊與剩下的單格正方形組成；只要決定 L 形拼塊的位置，未被覆蓋的格子就只能各自放一個正方形。

解題方法

先計算 L 形拼塊的放法，再檢查拼塊之間是否重疊。

$2\times3$ 方塊有兩個相鄰的 $2\times2$ 區域，每個區域各有 $4$ 種 L 形拼法，所以單放一個 L 形拼塊共有

$$2\times4=8$$

種分解；每種拼法剩下的 $3$ 格都放正方形。

核心觀念

這題考的是用狀態分類推導遞迴式。每次先看最左側一欄，再依該欄被填滿的方式，追蹤下一欄是否已有格子被先前的 L 形骨牌占用。

解題方法

令 $A(m)$ 表示最左欄已有一格被占用時的填法數，令 $B(m)$ 表示最左欄兩格都已被占用時的填法數。最左欄已有一格被占用時，剩下的格子可用單格填滿，或放一塊延伸至下一欄的 L 形骨牌，因此

$$A(m)=d(m-1)+B(m-1).$$

若最左欄兩格都已占用，直接接上剩餘長度的排列方式：

$$B(m)=d(m-1).$$

對完整的 $2\times m$ 方塊，最左欄可先用兩個單格填滿；也可以放一塊 L 形骨牌，使下一欄留下部分已占用的格子。依留下的狀態分類：

核心觀念
在即時系統 (real‑time system, RTS) 中，邏輯位址 (logical address) 必須在可接受的最壞情況執行時間內被映射成實體位址 (physical address)。因此，位址翻譯方法除了要提供記憶體保護與分割，亦必須保證 確定性 (determinism)。常見的三種翻譯方式如下：

方法	主要硬體/軟體支援	翻譯流程	決定性特性
1. 靜態直接映射 (Static Direct Mapping)	無 MMU，僅使用固定映射表或編譯期決定	編譯器在產生程式碼時即把每個邏輯位址寫成實體位址；執行時不需要額外運算	完全確定，翻譯時間為 0 (或常數的指令取指時間)
2. 基底/界限寄存器 (Base‑and‑Limit Register)	基底 (Base) 與界限 (Limit) 暫存器，硬體檢查	1. 取出指令/資料的 邏輯位址 $L$。<br>2. 若 $L < \text{Limit}$，則物理位址 $P = L + \text{Base}$；否則產生保護錯誤。	翻譯僅涉及一次加法與一次比較，最大執行時間為 常數，可精確預估
3. 分段/分頁 (Segmentation / Paging)	MMU (Memory Management Unit) 配合段表或頁表	分段：邏輯位址 = $(s, o)$（段號 $s$、段內偏移 $o$）<br> → 由段表得到段基底 $B_s$，物理位址 $P = B_s + o$。<br>分頁：邏輯位址 = $(p, d)$（頁號 $p$、頁內位移 $d$）<br> → 由頁表得到頁框號 $F_p$，物理位址 $P = F_p \times \text{頁大小} + d$。<br>若採用 段頁式，先由段表取得對應的頁表基底，再行頁表查找。	雖然涉及表查找，RTS 為保證最壞情況時間會 預先鎖定 表項於快取或 TLB，或使用 固定大小的頁表，使查找步驟可被上界化。最壞執行時間 = 查表次數 $\times$ 單次存取時間，常以常數上限表示。

---

1. 靜態直接映射 (Static Direct Mapping)

概念

• 編譯期或載入期就決定每個程式變數、指令的實體位址。
• 常見於裸機 (bare‑metal) 系統或限制式 MCU，沒有 MMU。

翻譯步驟

1. 編譯器產生的指令已是絕對位址 (例如 0x2000_1000)。
2. 執行階段直接以該位址存取，CPU 無需額外硬體協助。

優缺點

• 優點：零翻譯開銷，符合最嚴格的即時需求。
• 缺點：無法提供記憶體保護、動態載入或多程式共享記憶體。

即時系統適用情形

• 固定功能的控制器、單一任務或非常小的程式碼基底 (≤ 32 KB)。

---

2. 基底/界限寄存器 (Base‑and‑Limit Register)

概念

• 每個任務 (Task) 配置一對寄存器：Base (基底) 與 Limit (界限)。
• 邏輯位址 $L$ 必須在 $[0,\text{Limit})$ 內，否則觸發保護例外。

翻譯流程

$\text{若 } L < \text{Limit} \quad \Rightarrow \quad P = L + \text{Base}$

$\text{否則 } \quad \text{產生存取違例 (Access Violation)}$

硬體需求

• 兩個通用暫存器 (Base, Limit)。
• 加法器與比較器，於每次存取指令或資料時自動執行。

核心觀念

• 中斷（Interrupt）：由外部或內部事件觸發，暫停 CPU 正在執行的指令流，轉而執行相應的中斷服務例程（ISR）。
• 可遮蔽中斷（Maskable Interrupt, MI）：其中斷請求可以被 CPU 透過中斷屏蔽位（Interrupt Mask）暫時忽略。
• 不可遮蔽中斷（Non‑Maskable Interrupt, NMI）：其請求不能被任何軟體或硬體的遮蔽機制阻止，必須立即被處理。

解題方法

1. 先說明 中斷屏蔽（Interrupt Masking） 的實作方式：
   • 大多數 CPU 內部有一組 中斷允許旗標（Interrupt Enable, IE） 或 中斷屏蔽寄存器（Interrupt Mask Register, IMR）。當 IE 為 0 或對應位元在 IMR 中被設為 1 時，該類型的中斷會被「遮蔽」(mask)，CPU 仍會繼續執行當前指令序列。
2. 再比較 NMI 與 MI 的屬性：
   • 觸發時機：NMI 通常用於緊急、必須立即回應的硬體故障（如記憶體錯誤、看門狗超時、電源失效）。MI 用於一般 I/O、計時器、鍵盤等常規事件。
   • 屏蔽能力：
     • MI：可被程式執行 cli/sei（在 x86）或寫入 IMR（在 ARM）等指令暫時關閉。
     • NMI：硬體直接把訊號送到特殊的 NMI 線，CPU 不檢查 IE/IMR，必定產生中斷。

核心觀念

• 等待時間 (Waiting Time)：$WT_i = C_i - BT_i$，其中 $C_i$ 為第 $i$ 個行程的完成時間，$BT_i$ 為其 CPU 執行時間。所有行程同時於時間 0 到達，故 $WT_i = C_i - BT_i$。
• 排程演算法：
  • Round‑Robin (RR)：時間片（quantum）為 1，循環輪流執行，每次執行 1 時間單位，直至行程完成。
  • Shortest Job First (SJF) – 非搶先：一次選取尚未執行且執行時間最短的行程執行，執行期間不被中斷。若有相同長度，依到達順序（FCFS）決定。
  • Priority Scheduling – 非搶先：優先權數字越小表示優先等級越高。一次選取當前優先權最高（數字最小）的行程執行，若優先權相同則依到達順序（FCFS）。

---

解題方法與計算步驟

1. Round‑Robin（量子 = 1）

時間區間	執行行程	剩餘時間 (執行後)
0‑1	P1	9
1‑2	P2	0 → 完成 (完成時間 2)
2‑3	P3	1
3‑4	P4	0 → 完成 (完成時間 4)
4‑5	P5	4
5‑6	P1	8
6‑7	P3	0 → 完成 (完成時間 7)
7‑8	P5	3
8‑9	P1	7
9‑10	P5	2
10‑11	P1	6
11‑12	P5	1
12‑13	P1	5
13‑14	P5	0 → 完成 (完成時間 14)
14‑19	P1 連續 5 次執行直至完成 (完成時間 19)

完成時間：

• $C_{P1}=19,\ C_{P2}=2,\ C_{P3}=7,\ C_{P4}=4,\ C_{P5}=14$

等待時間：

$$\begin{aligned} WT_{P1}&=19-10=9\\ WT_{P2}&=2-1=1\\ WT_{P3}&=7-2=5\\ WT_{P4}&=4-1=3\\ WT_{P5}&=14-5=9 \end{aligned}$$

平均等待時間

$\overline{WT}_{RR}= \frac{9+1+5+3+9}{5}= \frac{27}{5}=5.4$

---

2. Shortest Job First（非搶先）

所有行程同時到達，先挑選執行時間最短者。若相等則依 PID 順序（FCFS）。

執行順序與時間段：

行程	執行起始	執行結束	完成時間
P2 (BT = 1)	0	1	1

核心觀念

• 有效存取時間 (Effective Access Time, EAT)：在需求分頁系統中，實際的記憶體存取時間會因為頁面錯誤 (page fault) 而增加。
• 公式：
  $\text{EAT}= (1-p)\times t_{\text{mem}} + p \times t_{\text{pf}}$
  其中
  • $p$ 為頁面錯誤率 (page‑fault rate)。
  • $t_{\text{mem}}$ 為普通記憶體存取時間。
  • $t_{\text{pf}}$ 為一次頁面錯誤的處理時間（包含換頁、磁碟 I/O、復原等）。

解題方法

1. 列出已知參數

   • $t_{\text{mem}} = 150\ \text{ns}$
   • $t_{\text{pf}} = 60{,}000\ \text{ns}$
   • 想要的上限：$\text{EAT} < 175\ \text{ns}$

2. 代入公式並設立不等式
   $(1-p)\times150 + p \times 60{,}000 < 175$

3. 展開並整理 $p$：

核心觀念

• 時間戳記 (Timestamp)：每個交易 $T_i$ 在系統中被賦予唯一且遞增的時間戳 $TS(T_i)$。
• 資料項目 Q 的時間戳：
  • $W\text{-}timestamp(Q)$：已成功執行 write$(Q)$ 的交易中，時間戳最大的那筆。
  • $R\text{-}timestamp(Q)$：已成功執行 read$(Q)$ 的交易中，時間戳最大的那筆。
• 時間戳順序協定 (Timestamp Ordering Protocol)：每一次讀寫操作都以 $TS(T_i)$ 與 $W\text{-}timestamp(Q)$、$R\text{-}timestamp(Q)$ 之比較來決定是否允許，從而保證產生的排程必然是衝突可序列化的。

---

解題方法

1. 操作規則

   • read$(Q)$（交易 $T_i$）

     • 若 $TS(T_i) < W\text{-}timestamp(Q)$，則 $T_i$ 試圖讀取已被較新交易寫入的 $Q$，會產生 讀寫衝突。依協定 中止 $T_i$（回滾），因為若允許將導致不可序列化。
     • 否則允許讀取，並更新 $R\text{-}timestamp(Q) \leftarrow \max(R\text{-}timestamp(Q), TS(T_i))$。

   • write$(Q)$（交易 $T_i$）

     • 若 $TS(T_i) < R\text{-}timestamp(Q)$，則 $T_i$ 試圖寫入已被較新交易讀過的 $Q$，會產生 寫讀衝突，必須 中止 $T_i$。
     • 若 $TS(T_i) < W\text{-}timestamp(Q)$，則 $T_i$ 試圖寫入已被較新交易寫過的 $Q$，會產生 寫寫衝突，亦須 中止 $T_i$。
     • 否則允許寫入，並更新 $W\text{-}timestamp(Q) \leftarrow \max(W\text{-}timestamp(Q), TS(T_i))$。

核心觀念
每條執行緒在執行時都必須保存自己的執行狀態（thread context），其中最重要的欄位之一是程式計數器（Program Counter，簡稱 PC）。PC 用於記錄下一條指令的記憶體位址，使得在切換執行緒或發生中斷時，CPU 能夠從正確的位置繼續執行。

解題方法
此題屬於填空題，要求填入描述「指向下一條即將執行之指令位址」的概念。根據作業系統教材，唯一符合此描述的欄位即為「program counter」。直接填入即可。

選項分析
題目未提供選項，僅需判斷填入的詞彙。以下列出常見的相似詞彙並說明為何不適合作答：

• 指令暫存器 (Instruction Register, IR)：僅保存當前正執行的指令本身，並不指向下一條指令的位址。

核心觀念
本題測試對 臨界區（critical‑section）問題 三大必要條件的熟悉度。
臨界區問題是指在多程序或多執行緒環境中，如何保證對共享資源的互斥存取，同時避免程式因等待而陷入無限停滯。
必須同時滿足的三個條件為：

1. Mutual Exclusion（互斥）
   任一時間內只能有 至多一個 程序位於臨界區。

2. Progress（進展）
   若沒有任何程序在臨界區，且有多個程序欲進入臨界區，則不會永遠阻塞，必須有機制讓其中一個程序能夠進入。

3. Bounded Waiting（有限等待）
   任一欲進入臨界區的程序，在其他程序連續使用臨界區的情況下，其等待次數必須被上限，也就是說不會因為其他程序無限次重複進入而被無限延遲。

本題的空格即要求填入 「bounded waiting」（有限等待）。

---

解題方法

1. 確認題目問的是哪一項缺失：題幹已列出「mutual exclusion」與「progress」兩項，依照臨界區的標準定義，唯一尚未提及的條件即是「bounded waiting」。
2. 直接填入正確術語：

   Any solution to the critical-section problem has to meet three requirements,
   including mutual exclusion, progress, and bounded waiting.
   

---

核心觀念

• 虛擬記憶體與頁表：作業系統使用頁表將虛擬位址映射到實體位址。每次存取記憶體時，CPU 必須根據頁表查找對應的實體框架。
• 快取 (Cache) 概念：快取是為了減少對較慢層級（如主記憶體或磁碟）的存取次數，透過暫存最近使用或常被使用的資料來提升效能。
• Translation Lookaside Buffer (TLB)：TLB 是一種小型、高速的快取，用於暫存最近查詢過的 頁表項 (page‑table entry, PTE)。TLB 直接存放虛擬頁號 → 實體框架的映射，若命中即可省去完整的頁表走查。

解題方法

1. 讀題目：空格前的詞彙「____ buffer」暗示要填入一種特定的緩衝區 (buffer)。
2. 依據題目說明「can be viewed as a cache for a page table」直覺是指 快取頁表 的結構。
3. 在作業系統教材中，唯一符合「快取頁表」功能且名稱內含 buffer 的概念就是 TLB。
4. 因此答案填入 Translation Lookaside Buffer，常簡寫為 TLB。

核心觀念
本題測驗的是虛擬記憶體的分頁機制中，邏輯頁 (logical page) 與實體頁框 (physical page frame) 之間的映射負責單元。
在現代電腦系統裡，映射工作由記憶體管理單元 (Memory Management Unit, MMU) 完成；MMU 透過頁表 (page table) 取得對應關係，將程式使用的虛擬位址轉換為實際的實體位址。

解題方法

1. 先回想作業系統的記憶體管理層次：
   • 程式層使用邏輯位址（由作業系統產生的虛擬位址）。
   • 硬體層的 MMU 需要把這些邏輯位址映射到 實體位址。
2. MMU 內建的位址轉譯快取 (Translation Lookaside Buffer, TLB) 以及頁表共同完成此任務。題目問的是「_____ unit」，顯然指的是硬體單元，即 Memory Management Unit。
3. 因此在空格處填入 Memory Management Unit（或其縮寫 MMU）即為正確答案。

選項分析
本題為填空題，未提供選項。若列出常見的相關名詞，可作如下比較：

核心觀念
本題測驗的是作業系統中記憶體管理的效能概念，特別是 paging（分頁） 造成的系統行為。

• 分頁（paging）：將虛擬記憶體切割成固定大小的頁面，讓缺頁時產生 page fault，由作業系統將所需頁面從次要儲存體（如硬碟）載入實體記憶體。
• thrashing（抖動）：當系統中大量的 page fault 發生，導致 CPU 大部分時間花在處理這些缺頁與頁面交換（paging）上，實際執行程式的時間極少。此現象常出現在多程式佔用的記憶體總量超過實體記憶體可容納的上限，或是工作集（working set）頻繁變動的情況。

解題方法
本題為填空題，只需填入描述「process spends more time paging than executing」的專有名詞。

1. 先回想作業系統教材中，哪一個術語明確指出「執行時間被分頁活動支配」；
2. 該術語在教材與考古題中通常配合「大量 page fault」或「工作集頻繁失效」的描述出現；
3. 直接填入 thrashing（抖動） 即可。

選項分析（若題目提供常見備選詞）

可能選項	為何正確 / 為何錯誤
thrashing（抖動）	正確。

核心觀念
此題測試對檔案系統（file system）之上層抽象概念的認識。

• 檔案系統是負責管理磁碟、SSD、磁帶等儲存媒介上檔案與目錄結構的軟體模組。
• 包含檔案系統的實體在作業系統層次上被稱為 「檔案系統實體」，其最常見的名稱是 「檔案系統容器」（file‑system container）或 「檔案系統宿主」。在教材與業界慣例中，最常用的單一詞彙是 「檔案系統」本身的容器，即 file system 的「domain」。

解題方法

1. 先辨識題目所問的概念：「包含檔案系統的任何實體」。
2. 回想 OS 教科書中對此概念的正式名稱：常見的描述包括 "file system host"、"file system container"、或 *"file s

核心觀念
RAID（Redundant Array of Independent Disks）是一種利用多顆硬碟組成陣列，以提供容錯與效能的技術。
在 RAID 系列中，冗餘（redundancy）方案指的是用什麼方式在磁碟上寫入額外的校驗資訊，以便在磁碟故障時仍能重建資料。

• RAID 5：單一奇偶校驗（single parity），即在每個 stripe 中儲存一組 XOR 校驗。
• RAID 6：必須能容忍 同時兩顆磁碟故障，因此需要兩組獨立的校驗資訊。

解題方法
本題屬於填空題，只要辨識 RAID 6 所採用的冗餘方式即可。

1. 回顧 RAID 系列的容錯能力：
   • RAID 5 → 容忍 1 磁碟故障 → 單奇偶校驗。
   • RAID 6 → 容忍 2 磁碟故障 → 需要 雙重奇偶校驗。
2. 雙重奇偶校驗的實作常見兩種寫法：
   • P + Q：P 為 XOR 奇偶校驗，Q 為 Reed‑Solomon（或類似的糾錯碼）校驗。
   • 兩層奇偶校驗（dual parity），本質上即「兩組獨立的校驗」。

核心觀念
在角色式存取控制（Role‑Based Access Control, RBAC）中，授權的基本單位包括 role（角色）、permission（權限）以及 privilege（特權）。

• Permission：對某個 object（資源）執行特定 operation（動作，如 read、write、execute）的授權。
• Privilege：對系統層面的 system call（系統呼叫）或該呼叫的 option（參數）擁有執行權限。
  因此，權限（permission）是 object‑operation 的結合，而特權（privilege）則是對 OS 提供的 system call 本身的使用權。

解題方法
題目要求填入描述「執行系統呼叫或使用該系統呼叫之選項的權利」的術語。

1. 先回想 RBAC 的定義層級：
   • User → Role → Permission → (Operation, Object)
   • 在此階層之下，system call 是操作系統提供的最底層「操作」；對它的使用權稱為 privilege。
2. 與「permission」相較，permission 通常指對檔案、資料庫等 object 的存取；而題目明確提到 system call，屬於系統層面的特權。

核心觀念
AES（Advanced Encryption Standard）是美國國家標準與技術研究院（NIST）於 2001 年正式採用的對稱式區塊密碼。

• 金鑰長度：AES 定義了三種金鑰長度，分別為 128、192、256 位元。金鑰長度決定了輪數（rounds）的多少，進而影響演算的安全度與效能。
• 區塊大小：AES 固定使用 128 位元（16 位元組）作為資料區塊大小，無論金鑰長度為何，區塊大小皆不變。

此題測試的概念即是「AES 的金鑰長度與區塊大小」的基本規格。

---

解題方法

1. 先回想 AES 的標準規範（FIPS‑197）：
   • 金鑰長度 $k$ 可為 128、192、256 位元。
   • 區塊大小 $b$ 為 128 位元。
2. 題目敘述已給出「AES can use key lengths of 128, ____, and 256 bits」。空格處即要求填入缺少的金鑰長度。
3. 依照標準唯一缺少的金鑰長度為 192 位元。

核心觀念

• 病毒分類：作業系統與資訊安全領域常將電腦病毒依其行為特徵分為 boot‑sector、file‑infector、macro、polymorphic、metamorphic、stealth 等類型。
• Stealth（隱形）病毒：此類病毒的主要手法是修改系統用來偵測病毒的資料結構或訊息（例如磁碟的 FAT、目錄資訊、系統呼叫返回值），使得防毒軟體或系統工具在檢查時看不到被感染的檔案或程式碼。
• 偵測機制：防毒軟體通常依賴簽名比對、檔案完整性檢查、系統呼叫監控等方式。Stealth 病毒透過偽裝或遮蔽，破壞這些檢查點的正確性，從而避免被發現。

---

解題方法

1. 觀察題目描述：「attempts to avoid detection by modifying parts of the system that could be used to detect it」——關鍵在於「修改系統用來偵測的部份」以隱蔽自身。
2. 回想課本或參考書中常見的病毒類型與其特徵：
   • Polymorphic / Metamorphic 病毒：透過改變自身程式碼結構來規避簽名偵測，並不會主動改變系統檢測機制。
   • Rootkit：多用於長期隱蔽控制權，會修改核心或驅動程式，但在作業系統課程裡常被歸類為 惡意軟體，而非「病毒」的子類。
   • Stealth 病毒：正是利用改寫磁碟分割表、目錄結構、系統呼叫返回值等方式，使防毒程式無法正確取得檔案資訊。
3. 依上述對照，只剩 Stealth 能完整符合「修改系統偵測部份」的描述。