112 年 國立臺灣大學資訊網路與媒體研究所《計算機結構與作業系統(B)》

核心觀念

本題（試卷第 1 頁）為國立臺灣大學 112 學年度碩士班招生考試「計算機結構與作業系統(B)」之試題規範與計分機制說明。其核心考點在於考生對國立臺灣大學研究所筆試中兩種主要選擇題型規範的理解：

1. 單選題（Multiple Choices）計分機制：每一題僅有一個正確選項，答錯不實施倒扣扣分（No penalty）。
2. 複選題（Multiple Choices with at Least One Correct Choice）計分機制：每一題至少有一個選項為正確答案，採「獨立選項計分（Each choice is graded individually）」，即針對題目的每一個選項獨立判斷給分，整題未作答者以零分計算。

---

解題方法

針對考場應試說明之數學期望值推導與答題策略分析如下：

1. 單選題作答策略：
   由於單選題採不倒扣原則，若遇不確定之題目，應利用消去法排除不可能之選項後對剩餘選項進行猜測，劃記期望值必大於等於零，切勿留白。

2. 複選題得分極大化期望值推導：
   臺大研究所複選題實施「每個選項獨立劃記計分」原則。假設一題共有 $N$ 個選項（一般 $N = 5$），該題總分數為 $S$，則單一選項占分為 $s = \frac{S}{N}$。
   若考生對某一選項判斷為正確或錯誤之信心度（正確率）為 $p$，則劃記該選項之得分期望值 $\mathbb{E}[\text{Score}]$ 計算如下：
   $\mathbb{E}[\text{Score}] = p \cdot (+s) + (1 - p) \cdot (-s) = (2p - 1)s$

核心觀念

1. 資料類型與快取區塊容量（Cache Block Capacity）：
   • 單精度浮點數（float）佔用 $4 \text{ bytes}$。
   • 快取區塊大小為 $32 \text{ bytes}$，因此一個快取區塊可容納 $\frac{32}{4} = 8$ 個 float 元素。
2. 記憶體存取局部性（Locality of Reference）：
   • 空間局部性（Spatial Locality）：連續存取陣列元素時，當讀取/寫入該區塊的第一個元素會引發 1 次 Cache Miss，隨後連續 7 個元素的存取皆會 Hit。
   • 時間局部性（Temporal Locality）：在內迴圈中重複存取相同的純量或陣列元素時（如固定索引 $i$ 的元素），除了首次存取可能 Miss 外，後續存取皆會 Hit。
3. 寫入策略（Write Policy）：
   • 本題採用 Write-Allocate 策略：當寫入未命中（Write Miss）時，會先將對應的快取區塊載入（Fetch）至快取中再進行寫入。因此寫入操作的失誤率計算與讀取（Read）完全相同。
4. 平均快取失誤率（Average Cache Miss Rate）公式：
   $\text{Cache Miss Rate} = \frac{\text{總快取失誤次數 (Total Cache Misses)}}{\text{總記憶體存取次數 (Total Memory Accesses)}}$

---

解題方法

1. 計算總記憶體存取次數（Total Memory Accesses）

雙重迴圈中，$i$ 與 $j$ 的範圍皆為 $0$ 至 $N-1$（$N = 1024$），總共執行 $N \times N = N^2$ 次迭代。
每次內迴圈迭代中，程式進行了以下 5 次記憶體存取：

• 讀取（Load）x[i]（1 次）
• 讀取（Load）x[j]（1 次）
• 讀取（Load）y[i]（1 次）
• 讀取（Load）y[j]（1 次）
• 寫入（Store）distance[j + i * N]（1 次）

因此，全程式的總記憶體存取次數為：
$\text{Total Accesses} = 5 N^2$

2. 分析各變數的快取失誤次數（Total Cache Misses）

• 變數 x[i] 的存取：
  在固定的外迴圈 $i$ 下，內迴圈 $j$ 執行 $N$ 次，期間 x[i] 的記憶體位址保持不變。
  在外迴圈每次迭代開始時（$j=0$），存取 x[i] 最多引發 $1$ 次 Miss；在隨後的 $N-1$ 次內迴圈迭代中，x[i] 皆命中（Hit）。
  全程式對 x[i] 的總 Miss 次數最多為 $N$ 次，相較於 $N^2$ 數量級極小，可忽略不計（$\approx 0$）。

• 變數 y[i] 的存取：
  行為與 x[i] 相同，外迴圈每次迭代僅第 1 次可能 Miss，其餘 $N-1$ 次皆 Hit。
  全程式對 y[i] 的總 Miss 次數最多為 $N$ 次（$\approx 0$）。

• 變數 x[j] 的存取：
  內迴圈 $j$ 從 $0$ 到 $N-1$ 連續讀取 x[j] 陣列。
  因每個快取區塊可容納 8 個 float，利用空間局部性，每 8 次連續存取才會發生 1 次 Miss。
  單次內迴圈發生的 Miss 次數為 $\frac{N}{8}$。
  外迴圈執行 $N$ 次，故 x[j] 的總 Miss 次數為：
  $\text{Misses}(x[j]) = N \times \frac{N}{8} = \frac{N^2}{8}$

• 變數 y[j] 的存取：
  與 x[j] 完全相同，連續讀取 y[j] 陣列，每 8 次存取發生 1 次 Miss。
  故 y[j] 的總 Miss 次數為：
  $\text{Misses}(y[j]) = N \times \frac{N}{8} = \frac{N^2}{8}$

核心觀念

本題考查計算機結構（Computer Architecture）中**效能分析與屋頂模型（Roofline Model）**的核心指標——算術強度（Arithmetic Intensity, AI）。

算術強度的定義為程式執行期間**總執行的浮點運算次數（FLOPs）與處理器和記憶體之間總傳輸資料量（Bytes）**的比值：
$\text{Arithmetic Intensity (AI)} = \frac{\text{Total Floating-Point Operations (FLOPs)}}{\text{Total Memory Traffic (Bytes)}}$

算術強度的物理意義為「每傳輸 1 Byte 的記憶體資料，能夠支援進行多少次浮點數運算」。算術強度越低，代表程式越偏向記憶體受限（Memory-Bound）；算術強度越高，則越偏向運算受限（Compute-Bound）。

---

解題方法

距離計算函式 compute_distance 最常見的實作方式為計算空間中兩點之歐幾里得距離（Euclidean Distance）。以最常見的 3D 空間兩點距離計算進行推導（若為 2D 空間，結果趨勢完全一致）：

1. 浮點運算次數（FLOPs）分析

設兩點座標分別為 $P_1(x_1, y_1, z_1)$ 與 $P_2(x_2, y_2, z_2)$，距離公式為：
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$

各項浮點數運算分解如下：

• 減法（Subtraction）：$x_1 - x_2$、$y_1 - y_2$、$z_1 - z_2$，共 3 次 FLOPs。
• 乘法/平方（Multiplication）：$(x_1 - x_2)^2$、$(y_1 - y_2)^2$、$(z_1 - z_2)^2$，共 3 次 FLOPs。
• 加法（Addition）：將三個平方項相加，共 2 次 FLOPs。
• 開平方根（Square Root）：$\sqrt{\cdot}$，計為 1 次 FLOPs。

總浮點運算量：
$\text{FLOPs} = 3 + 3 + 2 + 1 = 9 \text{ FLOPs}$
（若開根號不納入算術運算或視為單一指令，FLOPs 為 8 次；若為 2D 距離，則為 $2 \text{ (減)} + 2 \text{ (乘)} + 1 \text{ (加)} + 1 \text{ (根號)} = 6 \text{ FLOPs}$）。

2. 記憶體傳輸量（Bytes）分析

假設座標與傳回的距離皆為標準單精度浮點數（float，每個佔據 4 Bytes）：

• 讀取輸入資料（Read Traffic）：需從記憶體載入兩點座標，即 6 個 float，共 $6 \times 4 = 24 \text{ Bytes}$。

核心觀念

1. 算術強度（Arithmetic Intensity, AI）的定義：
   在計算機結構與 Roofline 模型（Roofline Model）中，算術強度定義為程式執行時「總浮點運算次數（FLOPs）」與「處理器與主記憶體（DRAM）之間傳輸的總位元組數（Bytes）」之比值：
   $\text{Arithmetic Intensity (AI)} = \frac{\text{Total Floating-Point Operations (FLOPs)}}{\text{Total DRAM Memory Traffic (Bytes)}}$
   其單位通常表示為 $\text{FLOPs/Byte}$。

2. 快取記憶體（Cache）對算術強度的影響：

   • 算術強度的分母僅採計跨越快取邊界、實際對主記憶體（DRAM）產生的存取流量。
   • 若資料已存在於快取中（Cache Hit），處理器直接從快取讀取資料，不會對主記憶體產生 DRAM 讀取流量（DRAM Read Traffic $= 0\text{ Byte}$）。

---

解題方法

1. 未快取（Cold Cache）時的對照分析：
   若點資料 $x[]$ 與 $y[]$ 未在快取中，每次計算皆需由 DRAM 讀取。以單精度浮點數（每個數占 $4\text{ Bytes}$）為例，讀取一個 2D 點 $(x_i, y_i)$ 需傳輸 $8\text{ Bytes}$。若函數對每個點執行數個浮點運算（例如 3～6 個 FLOPs），其算術強度為：
   $\text{AI}_{\text{uncached}} = \frac{3 \sim 6 \text{ FLOPs}}{8 \text{ Bytes (輸入)} + 4 \text{ Bytes (輸出)}} \approx 0.25 \sim 0.5 \text{ FLOPs/Byte}$
   此時算術強度低於 1，系統屬於記憶體受限（Memory-bound）。

2. 本題情境推導（Cache 完全命中）：
   題目設定處理器快取容量足夠大，且在函數呼叫前，所有 2D 點資料 $x[]$ 與 $y[]$ 已完全載入快取中（Already in cache）。

   • 分子（FLOPs）：函數對所有 2D 點進行計算所需的總浮點運算量維持不變（非零正值）。
   • 分母（DRAM Bytes）：由於所有輸入陣列的存取均為快取命中（Cache Hit），對 DRAM 的讀取傳輸量降低為 $0\text{ Byte}$。
   • 即使考慮寫回（Write-back）少量計算結果至 DRAM，分母仍極小；若結果保存在暫存器或快取內，DRAM 總傳輸位元組數趨近於 $0$。

本題考查的核心觀念是如何運用 Roofline Model（屋頂線模型）來預估程式的執行時間。這需要計算程式的總浮點運算次數（Total FLOPs）、總記憶體資料傳輸量（Total Bytes Transferred），進而計算出算術強度（Arithmetic Intensity），並結合處理器的峰值浮點運算效能和記憶體頻寬來判斷程式是屬於計算密集型（compute-bound）還是記憶體密集型（memory-bound），最終得出預估的執行時間。

以下是完整的解題過程：

1. 計算總浮點運算次數 (Total FLOPs)
   觀察 compute_distance 函數的內層迴圈：

   float x_dist = x[i]-x[j];          // 1 浮點減法
   float y_dist = y[i] - y[j];         // 1 浮點減法
   distance[j + i * N] = sqrt(x_dist*x_dist + y_dist*y_dist);
                                       // x_dist*x_dist: 1 浮點乘法
                                       // y_dist*y_dist: 1 浮點乘法
                                       // ... + ...: 1 浮點加法
                                       // sqrt(...): 1 浮點平方根 (通常計為 1 浮點運算)
   

   因此，內層迴圈每次迭代執行 $1+1+1+1+1+1 = 6$ 個浮點運算。
   外層迴圈和內層迴圈都執行 $N$ 次，所以總迭代次數為 $N \times N = N^2$ 次。
   題目給定 $N=1024$。
   總浮點運算次數為：
   $\text{Total FLOPs} = 6 \times N^2 = 6 \times (1024)^2 = 6 \times 1,048,576 = 6,291,456 \text{ FLOPs}$

2. 計算總記憶體資料傳輸量 (Total Bytes Transferred)
   題目 Q1 的描述中提到：「For each iteration in the inner loop, the function loads 4 floating-point numbers and store 1 floating-point number.」
   由於題目 Q4 說明「processor cache is too small to store all the data points」，這表示大部分的記憶體存取都會導致快取失誤，資料需要從主記憶體傳輸。因此，我們將每次內層迴圈的資料存取視為記憶體傳輸。
   每個 float 佔用 4 bytes（單精度浮點數）。
   每次內層迴圈迭代的資料傳輸量為：

核心觀念

本題考查計算機結構中記憶體階層（Memory Hierarchy）效能瓶頸與記憶體延遲隱藏技術（Latency Hiding Techniques）。

在 CPU 效能方程式與平均記憶體存取時間（AMAT）的分析中：

• CPU 效能方程式：
  $\text{CPU Time} = \text{IC} \times \text{CPI} \times \text{Clock Cycle Time}$
  其中 $\text{CPI} = \text{CPI}_{\text{ideal}} + \text{Memory Stall Cycles}$。
• 平均記憶體存取時間（AMAT）：
  $\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$

當程式對記憶體進行頻繁且規律的存取時（例如陣列掃描或矩陣運算），效能瓶頸通常來自於將資料從主記憶體載入至快取所產生的高額存取延遲（Miss Penalty），導致 CPU 產生大量的記憶體停頓週期（Memory Stall Cycles）。要有效提升效能，最關鍵的方法是在 CPU 需要資料之前，先將資料準備好，從而將記憶體存取延遲與 CPU 運算時間重疊（Overlap）。

---

解題方法

延續前題對記憶體存取效能瓶頸的分析，本題切入點在於評估各項微架構技術對於「規律記憶體存取延遲」的優化效果：

1. 分析存取特性：對於具備高度空間區域性（Spatial Locality）與可預測存取規律（Regular Access Pattern / Stride）的資料存取，快取缺失主要屬於強制缺失（Compulsory Miss）或容量缺失（Capacity Miss）。
2. 評估最佳解決方案：
   • 增加連帶度僅能降低衝突缺失（Conflict Miss），無法消弭強制缺失。
   • 加深管線僅能提升時脈頻率，但會加大快取缺失時的停頓代價。
   • 增加記憶體頻寬主要提升總傳輸量，無法直接減少單次存取的 Latency。
   • 資料預取（Data Prefetching） 則可由硬體或軟體主動預測未來的記憶體位址，在 CPU 發出請求前提前將資料載入快取，徹底隱藏記憶體存取延遲（Hide Memory Latency），將原本的快取缺失轉化為快取命中，因此是提升該類情境效能最為有效的手段。

---

選項分析

• (A) Increase the associativity of the cache.（錯誤）
  增加快取的組連帶度（Associativity）主要用於減少「衝突缺失（Conflict Miss）」。若程式的主要瓶頸是連續存取的強制缺失（Compulsory Miss）或工作集過大導致的容量缺失（Capacity Miss），提高連帶度並無法降低 Miss Rate。

核心觀念

本題的核心考點為**記憶體一致性模型（Memory Consistency Models）與完全寫入排序（Total Store Ordering, TSO）**在多處理器／多執行緒架構下的行為。

在多執行緒共享記憶體系統中，硬體為了提升效能會採用寫入緩衝區（Store Buffer）與亂序執行（Out-of-Order Execution）。不同的記憶體模型對於指令重排（Reordering）有不同的規範約束：

1. TSO（Total Store Ordering）記憶體模型規範：

   • Store Buffer (FIFO)：每個 CPU／執行緒均擁有獨立且先進先出（FIFO）的 Store Buffer。寫入記憶體的操作（Store）會先進入 Store Buffer，隨後才依序寫回主記憶體（Shared Memory）。
   • 指令重排限制：
     • Store $\to$ Store：不可重排（受限於 FIFO Store Buffer，先寫入的資料必然先寫回主記憶體）。
     • Load $\to$ Load：不可重排（保持讀取的程式順序 Program Order）。
     • Load $\to$ Store：不可重排（讀取必須在隨後的寫入之前完成）。
     • Store $\to$ Load：允許重排（寫入操作先進入 Store Buffer 尚未寫回主記憶體時，後續的 Load 操作可以先讀取主記憶體或自己的 Store Buffer）。

2. 經典 Litmus Tests 彙整：
   各 Case 的程式碼結構與執行順序如下表所示：

Case	執行緒	指令 1	指令 2
Case 0	Proc0 <br> Proc1	store #1, [A]; <br> store #1, [B];	load x0, [B]; <br> load x1, [A];
Case 1	Proc0 <br> Proc1	load x0, [A]; <br> load x1, [B];	store #1, [B]; <br> store #1, [A];
Case 2	Proc0 <br> Proc1	store #1, [A]; <br> store #1, [B];	store #1, [B]; <br> load x1, [A];

---

解題方法

分析多執行緒並行執行的所有可能結果時，需分析程式順序（Program Order）、Store Buffer 的延遲寫回（Drain Timing）以及交錯執行（Interleaving）的影響。

---

選項分析

(A) 敘述正確

• 選項原文：In case 0, x0 on Proc0 and x1 on Proc1 can be either both 0 or 1.

• 詳細分析：
  在 Case 0 中，程式碼為：

  • Proc0：store #1, [A]; $\to$ load x0, [B];
  • Proc1：store #1, [B]; $\to$ load x1, [A];

  1. 情況一：$(x_0, x_1) = (0, 0)$ 是可能的

     • Proc0 將 A = 1 放入其 Store Buffer，但尚未寫回主記憶體。
     • Proc1 將 B = 1 放入其 Store Buffer，但尚未寫回主記憶體。
     • Proc0 執行 load x0, [B]，自主記憶體讀取 $B$，讀到初始值 $0$（故 $x_0 = 0$）。
     • Proc1 執行 load x1, [A]，自主記憶體讀取 $A$，讀到初始值 $0$（故 $x_1 = 0$）。
     • 隨後兩者的 Store Buffer 才將資料寫回主記憶體。此時 $x_0 = 0$ 且 $x_1 = 0$。

  2. 情況二：$(x_0, x_1) = (1, 1)$ 是可能的

     • Proc0 執行 store #1, [A] 並成功寫回主記憶體（主記憶體 $A = 1$）。
     • Proc1 執行 store #1, [B] 並成功寫回主記憶體（主記憶體 $B = 1$）。
     • Proc0 執行 load x0, [B]，讀取主記憶體得到 $1$（故 $x_0 = 1$）。
     • Proc1 執行 load x1, [A]，讀取主記憶體得到 $1$（故 $x_1 = 1$）。

  因此，在 Case 0 中，$x_0$ 與 $x_1$ 可以同時為 0，也可以同時為 1。敘述完全正確。

---

(B) 敘述錯誤

• 選項原文：In case 0, suppose the threads support total store order (TSO); x0 on Proc0 and x1 on Proc1 can never be both 0.
• 詳細分析：
  在 TSO 記憶體模型下，允許 Store $\to$ Load 重排（即 Load 操作可以在先前的 Store 寫回主記憶體前先執行）。
  如 (A) 選項分析所示，當 Proc0 的 Store A 與 Proc1 的 Store B 均暫存於各自的 Store Buffer 未寫回主記憶體時，兩邊的 Load 操作皆會讀到主記憶體的初始值 $0$，從而產生 $(x_0, x_1) = (0, 0)$ 的結果。

核心觀念

本題考查經典 RISC-V / MIPS 五階段管線（5-stage Pipeline：IF, ID, EX, MEM, WB）中**資料冒險（Data Hazard / Read-After-Write, RAW）**的處理機制。

在處理器**未實作冒險偵測單元（Hazard Detection Unit）與資料轉發（Forwarding / Bypassing）**的前提下，消除 RAW 冒險必須透過硬體插入或編譯器插入空指令 NOP（No Operation）來延遲相依指令的執行。

關鍵時序與觀念如下：

1. 暫存器檔案讀寫時序（Register File Timing）：標準管線設計採用「前半週期寫入（Write in 1st half of CC）、後半週期讀取（Read in 2nd half of CC）」。
2. 解決 RAW 所需的指令間隔距離：
   • 若指令 A 於週期 $t$ 進入 IF 階段，會在週期 $t+4$ 的第 5 階段（WB）前半週期將結果寫回暫存器。
   • 後續讀取該暫存器的指令 B 最早可在週期 $t+4$ 的第 2 階段（ID）後半週期讀到更新後的數值。
   • 因此，寫入暫存器的指令與讀取該暫存器的指令之間，必須間隔 2 條指令（即若兩指令連續執行，中間需補上 2 個 NOP）。

---

解題方法

首先分析原始指令序列中各指令對暫存器的寫入（Write）與讀取（Read）行為：

• I1: or x10, x3, x4 $\rightarrow$ 寫入 x10
• I2: ld x5, 8(x10) $\rightarrow$ 讀取 x10，寫入 x5
• I3: ld x4, 0(x2) $\rightarrow$ 讀取 x2，寫入 x4
• I4: add x5, x10, x5 $\rightarrow$ 讀取 x10、x5，寫入 x5
• I5: sd x5, 4(x10) $\rightarrow$ 讀取 x5、x10

接著依序分析資料相依性（RAW Hazard）並計算所需 NOP 數量：

1. I1 與 I2 之間的 x10 相依性：

   • I1 寫入 x10，I2 緊接著讀取 x10。
   • 原本間隔為 0 條指令，需達 2 條指令間隔，故需在 I1 與 I2 之間插入 2 個 NOP。

2. I2 與 I4 之間的 x5 相依性：

   • I2 寫入 x5，I4 讀取 x5。
   • 兩者之間原本已有 1 條獨立指令 I3（讀取 x2、寫入 x4，無相依衝突）。
   • 距離尚缺 1 條指令，故需在 I3 與 I4 之間插入 1 個 NOP。

3. I4 與 I5 之間的 x5 相依性：

   • I4 寫入 x5，I5 緊接著讀取 x5（sd 指令的來源暫存器在 ID 階段讀取）。

核心觀念

本題考驗計算機結構（Computer Architecture）中 ISA 指令集架構設計原則、CPU 效能公式 以及 快取記憶體（Cache）硬體組織與 3C 錯失模型。

1. CPU 效能公式（CPU Performance Equation）：
   $\text{CPU Time} = \text{Instruction Count (IC)} \times \text{Clock Cycles Per Instruction (CPI)} \times \text{Clock Cycle Time ($T_c$)}$
   評估任何 ISA 或硬體修改時，必須綜合考量對 $\text{IC}$、$\text{CPI}$ 與 $T_c$ 三者的折衷關係（Trade-off）。

2. 暫存器數量（Register File Size）與指令數：
   暫存器數量減少會限制編譯器的暫存器配置（Register Allocation），增加暫存器溢出（Register Spilling）現象，進而插入額外的 Load / Store 指令。

3. 快取連結度（Associativity）與命中時間（Hit Time）：
   快取連結度越高（如從 Direct-Mapped 增加至 Set-Associative），搜尋 Set 內區塊時所需的多路選擇器（Multiplexer, MUX）規模與標籤比較器（Tag Comparator）門檻延遲隨之增加，導致硬體電路的命中時間（Hit Time, $T_{hit}$）上升。

4. 3C 錯失模型（3C's Miss Model）與區塊大小（Block Size）：

   • 強制性錯失（Compulsory Miss）：首次存取資料產生的錯失。
   • 容量錯失（Capacity Miss）：快取總容量不足以涵蓋程式 Working Set 所產生的錯失。
   • 衝突錯失（Conflict Miss）：多個記憶體區塊對映至同一 Set 所產生的錯失。

---

解題方法

本題為計算機結構觀念觀念判斷題，切入點包含：

1. 區分硬體電路特性與軟體行為：硬體電路延遲（如 Hit Time）是由結構邏輯（MUX 深度、比較器門檻）決定的物理屬性，對所有程式均成立；而效能提升與否通常取決於軟體是否使用該特性。
2. 注意絕對性修飾詞（for all programs）：計算機結構設計充滿 Trade-off，幾乎沒有任何單一優化能保證對「所有程式」都帶來效能提升。

針對各選項，依據 Hennessy & Patterson 計算機結構標準理論進行嚴格審視與推導。

---

選項分析

• (A) 錯誤：
  引入新的複雜指令（Complex Instruction）並不保證改善所有程式的效能。
  1. 未重新編譯或未使用該新指令的舊程式，其指令數（IC）完全不會減少。
  2. 支援複雜指令會增加 CPU 控制邏輯與解碼器（Decoder）複雜度，可能導致整體時脈週期時間（$T_c$）拉長或提升其他指令的 CPI，反而降低未採用該指令之程式的執行效能。

核心觀念

1. 兩階段頁表轉譯（Two-Stage Memory Translation / Nested Page Tables, NPT）：
   在虛擬化環境中，記憶體管理單元（MMU）需將虛擬機（VM）內部的虛擬位址（GVA, Guest Virtual Address）轉譯為實體記憶體位址（HPA, Host Physical Address）。

   • 第一階段（Stage 1）：使用 VM 的頁表（Guest PT）將 GVA 轉譯為中間實體位址（IPA, Intermediate Physical Address）。
   • 第二階段（Stage 2）：使用主機的巢狀頁表（Host NPT / EPT）將 IPA 轉譯為最終的實體位址（HPA）。
   • 關鍵機制：Guest PT 存放在 VM 的記憶體中，其頁表項（PTE）紀錄的位址皆為 IPA。因此，硬體每次讀取 Guest PT 的任何一層頁表項時，該 IPA 都必須先通過 Host NPT 進行一次完整的 Stage 2 轉譯，才能取得該 Guest 頁表項在 Host 上的實際實體位址。

2. 頁表階層數推導：

   • 題目條件：位址長度為 $39\text{ bits}$，頁表大小為 $4\text{ KB} = 2^{12}\text{ bytes}$，每個頁表項（PTE）大小為 $8\text{ bytes} = 2^3\text{ bytes}$。
   • 每張頁表包含的條目數：$2^{12} / 2^3 = 2^9 = 512$ 個，故每一層頁表索引需使用 $9\text{ bits}$。
   • 4KB 映射（標準頁面）：
     頁內偏移量（Offset）為 $\log_2(4\text{ KB}) = 12\text{ bits}$。
     用於轉譯的位址位元數為 $39 - 12 = 27\text{ bits}$。
     頁表階層數為 $27 / 9 = 3$ 層。
   • 2MB 映射（大頁面 / Huge Page）：
     頁內偏移量（Offset）為 $\log_2(2\text{ MB}) = 21\text{ bits}$。
     用於轉譯的位址位元數為 $39 - 21 = 18\text{ bits}$。
     頁表階層數為 $18 / 9 = 2$ 層。

---

解題方法

設 Guest PT 走查階層數為 $g \in \{2, 3\}$，Host NPT 走查階層數為 $h \in \{2, 3\}$。

記憶體存取次數推導公式：
若 Guest PT 需走查 $g$ 層：

1. 讀取第 $i$ 層 Guest PT ($i = 1 \dots g$)：
   該 Guest PT 條目的位址為 IPA，硬體需先透過 Host NPT 將此 IPA 轉譯為 HPA。若該次 Host NPT 走查層數為 $h_i$，需 $h_i$ 次記憶體存取讀取 Host NPT，外加 $1$ 次記憶體存取讀取該 Guest PT 條目本身。故第 $i$ 層 Guest PT 存取共需 $(h_i + 1)$ 次記憶體存取。
2. 轉譯最終目標 IPA：
   走查完 $g$ 層 Guest PT 後取得目標頁面的 IPA。硬體需最後執行一次 Host NPT 走查將此 IPA 轉譯為最終 HPA。若最終 Host NPT 走查層數為 $h_{\text{final}}$，需 $h_{\text{final}}$ 次記憶體存取。

總轉譯記憶體存取次數 $T$ 之一般化公式為：
$T = \sum_{i=1}^{g} (h_i + 1) + h_{\text{final}}$

情況一：PT 與 NPT 皆各自採用單一頁面大小（Uniform Paging）

1. Guest 採 2MB ($g=2$)，Host NPT 採 2MB ($h=2$)：
   $T = 2 \times (2 + 1) + 2 = 8$
2. Guest 採 2MB ($g=2$)，Host NPT 採 4KB ($h=3$)：
   $T = 2 \times (3 + 1) + 3 = 11$

核心觀念

• 多處理器指令交錯與競態條件（Instruction Interleaving & Race Condition）：在缺乏同步機制（如 Lock 或 Atomic Operations）的多處理器（Multi-processor）共享記憶體環境中，各處理器發出的指令會以任意順序交錯執行（Interleaving），但每個處理器內部均遵循自身的程式順序（Program Order）。
• 共享記憶體的最終值：記憶體位址 $A$ 的最終數值，完全取決於「全域時間軸上最後一個執行的寫入指令（store）」所寫入的值。
• 各 CPU 的關鍵寫入與讀取關係：
  • CPU0：指令序列 $I_{0,1} \sim I_{0,4}$。最終寫入指令 $I_{0,4}$ 寫入的數值為 $v_{0,2} + 4$（其中 $v_{0,2}$ 為 $I_{0,2}$ 所讀取到的 $A$ 值）。
  • CPU1：指令序列 $I_{1,1} \sim I_{1,6}$。寫入指令 $I_{1,3}$ 寫入 $v_{1,1} + 1$；最終寫入指令 $I_{1,6}$ 寫入 $2 \times v_{1,4}$（其中 $v_{1,1}, v_{1,4}$ 分別為 $I_{1,1}, I_{1,4}$ 讀取到的 $A$ 值）。
  • CPU2：指令序列 $I_{2,1} \sim I_{2,4}$。寫入指令 $I_{2,1}$ 寫入 $6$；最終寫入指令 $I_{2,4}$ 寫入 $2 \times v_{2,2}$（其中 $v_{2,2}$ 為 $I_{2,2}$ 讀取到的 $A$ 值）。

---

解題方法

本題的切入點為逆向尋找全域最後一個寫入指令（Last Store）。因為各 CPU 內部的指令必須滿足 Program Order，所以全域最後執行的 store 指令必定是 CPU0 的 $I_{0,4}$、CPU1 的 $I_{1,6}$ 或 CPU2 的 $I_{2,4}$ 三者之一。

只要能構造出一組滿足 Program Order 且合法交錯的執行追蹤序列（Execution Trace），使全域最後一個 store 指令寫入該目標值，即證明該值為可能存於 $A$ 的最終結果。

---

選項分析

• (A) 8：正確（可能值）

  • 構造執行追蹤序列：
    1. CPU1 與 CPU2 先將各自所有指令執行完畢（期間對 $A$ 的寫入均會被後續指令覆蓋）。
    2. CPU0 執行 $I_{0,1}$：將 4 寫入 $A$（$A = 4$）。
    3. CPU0 執行 $I_{0,2}$：自 $A$ 讀取數值，得到 $v_{0,2} = 4$。
    4. CPU0 執行 $I_{0,3}$：計算 $\text{reg} = 4 + 4 = 8$。
    5. CPU0 執行 $I_{0,4}$：將 8 寫入 $A$（此為全域最後執行的 store 指令）。
  • 最終 $A = 8$，故選項 (A) 為可能值。

• (B) 9：正確（可能值）

  • 構造執行追蹤序列：
    1. CPU0 執行 $I_{0,1}$：將 4 寫入 $A$（$A = 4$）。
    2. CPU1 執行 $I_{1,1}$：自 $A$ 讀取數值，得到 $v_{1,1} = 4$。
    3. CPU1 執行 $I_{1,2}$ 與 $I_{1,3}$：計算 $\text{reg} = 4 + 1 = 5$，並將 5 寫入 $A$（$A = 5$）。
    4. CPU0 執行 $I_{0,2}$：自 $A$ 讀取數值，得到 $v_{0,2} = 5$。

核心觀念

位址由標籤（Tag）、索引（Index）與區塊位移（Block offset）組成：

• 區塊大小為 4 bytes，因此區塊位移需要 $\log_2 4=2$ 位。
• Cache 有 8 組，因此索引需要 $\log_2 8=3$ 位。
• 位址寬度為 13 位，因此標籤有 $13-2-3=8$ 位。

對位址 addr：

$$\text{Tag}=\left\lfloor\frac{\text{addr}}{32}\right\rfloor,\qquad \text{Index}=\left\lfloor\frac{\text{addr}}{4}\right\rfloor\bmod 8,\qquad \text{Offset}=\text{addr}\bmod 4$$

在算出的 Index 那一列中，若有一個 Valid bit 為 1 的欄位，其 Tag 與位址 Tag 相同，即為 cache hit。命中後用 Offset 選取該區塊中的位元組。

解題方法與選項分析

(A) 錯誤。 位址 0x71A 的 Tag 為 0x38、Index 為 6、Offset 為 2。Index 6 列中有一個 Valid bit 為 1、Tag 為 0x38 的區塊，所以讀取會命中。

核心觀念

本題考驗作業系統中**次級儲存空間分配策略（Secondary Storage Allocation Methods）與空閒空間管理（Free-Space Management）**的核心特性：

1. 檔案分配策略對比：

   • 連續分配（Contiguous Allocation）：檔案佔用磁碟上連續的區塊。優點是支援極快的循序與隨機存取；缺點是會產生外部碎裂（External Fragmentation），且必須在建立時預先知道檔案大小。
   • 鏈結分配（Linked Allocation）：檔案區塊以鏈結串列（Linked List）形式分散儲存。優點是完全無外部碎裂；缺點是僅適合循序存取（Sequential Access），隨機存取效能極差，且指標若損毀會影響資料完整性。
   • 檔案分配表（FAT, File-Allocation Table）：鏈結分配的重要變體，將原先分散在各區塊末端的指標集中抽離至記憶體中的 FAT 表格，藉此加速尋址並改善隨機存取的效能。
   • 索引分配（Indexed Allocation）：為每個檔案設立索引區塊（Index Block / i-node）儲存所有資料區塊的指標。優點是無外部碎裂且天生支援高效的隨機存取（Random Access / Direct Access）。

2. 空閒空間管理（Free-Space Management）：

   • 使用 Linked List 管理空閒區塊時，每個空閒區塊包含指向下一個空閒區塊的指標。

---

解題方法

評估 Secondary Storage 的分配機制時，主要從外部碎裂（External Fragmentation）、**存取模式（Sequential vs. Random Access）與結構額外開銷（Overhead）**三個面向進行剖析：

1. 碎裂問題：是否需要連續的磁碟空間？需要連續空間者（Contiguous）會有外部碎裂；非連續者（Linked、Indexed）僅有內部碎裂。
2. 隨機存取時間複雜度：存取第 $n$ 個區塊需要多少次磁碟 I/O？
   • Contiguous: $O(1)$
   • Linked: $O(n)$（效能低落）
   • Indexed: $O(1)$（若 Index Block 已載入記憶體）
3. 作業系統操作頻率：分析 OS 在執行空閒空間管理時的實際運作流程與存取需求。

---

選項分析

• (A) 正確
  連續分配要求檔案佔用連續的磁碟區塊。隨著檔案頻繁建立與刪除，磁碟空間會碎裂成許多不連續的小空閒區塊，導致雖然總空閒空間足夠，卻無法找到足夠大的連續空間來儲存新檔案，即嚴重的外部碎裂（External Fragmentation）。

參考書等級：中等

說明

• A：持續遞迴呼叫 fork() 會快速產生大量子行程，耗盡系統資源，屬於 DoS 攻擊。✓
• B：MAC 為 $F(M,K)$，只有持有共用密鑰 $K$ 的實體能產生正確 MAC，故可驗證訊息的發送者身分。✓

核心觀念

本題考查**兩階頁表（Two-Level Paging）**之位址切割與頁表大小計算。
在兩階頁表機制中，$W$ 位元的邏輯位址（Logical Address）被分割為三個欄位：

1. 外層頁表索引（Outer Page Table Index, $p_1$）：佔 $p_1$ 位元。
2. 內層頁表索引（Inner Page Table Index, $p_2$）：佔 $p_2$ 位元。
3. 頁內偏移量（Page Offset, $d$）：佔 $X$ 位元（因為頁面大小為 $2^X$ 位元組）。

相關公式與定義如下：

1. 頁內偏移量位元數：$d = X$。
2. 總頁號位元數：$p_1 + p_2 = W - X$。
3. 內層頁表設計原則：為了讓一個內層頁表恰好能容納於一個頁面（Page Frame）中，單一內層頁表包含的項目數（Entries）受限於頁面大小與內層頁表項目大小：
   $\text{內層頁表項目數} = \frac{\text{頁面大小}}{\text{內層頁表項目大小}} = \frac{2^X}{2^Z} = 2^{X - Z}$
   故內層頁表索引位元數為：$p_2 = X - Z$。
4. 外層頁表索引位元數：
   $p_1 = (W - X) - p_2 = (W - X) - (X - Z) = W - 2X + Z$
5. 外層頁表總大小（Outer Page Table Size）：
   外層頁表共有 $2^{p_1}$ 個項目，每個項目大小為 $2^Y$ 位元組，故總大小為：
   $\text{外層頁表大小} = 2^{p_1} \times 2^Y = 2^{p_1 + Y} = 2^{W - 2X + Z + Y} \text{ 位元組}$
6. 外層頁表可放進單一頁面之條件：
   外層頁表大小 $\le$ 頁面大小（$2^X$ 位元組）：
   $p_1 + Y \le X \implies W - 2X + Z + Y \le X \implies W - 3X + Y + Z \le 0$
   同時，位元分割必須符合物理合理性：$p_1 \ge 0$ 且 $p_2 \ge 0$（即 $X \ge Z$ 且 $W - X \ge X - Z$）。

---

解題方法

針對題目給定的變數組 $(W, X, Y, Z)$，依序進行以下步驟驗證：

1. 計算內層頁表位元數：$p_2 = X - Z$（檢驗是否 $p_2 \ge 0$）。
2. 計算外層頁表位元數：$p_1 = (W - X) - p_2 = W - 2X + Z$（檢驗是否 $p_1 \ge 0$）。
3. 計算外層頁表總大小：$2^{p_1 + Y}$ 位元組。
4. 比較外層頁表大小與頁面大小（$2^X$ 位元組），判斷是否能裝入單一頁面中。

---

選項分析

• 選項 (A) $(W, X, Y, Z) = (16, 8, 6, 6)$：

  • 內層頁表位元數 $p_2 = X - Z = 8 - 6 = 2$ 位元。
  • 外層頁表位元數 $p_1 = W - 2X + Z = 16 - 2(8) + 6 = 4$ 位元。
  • 外層頁表大小 $= 2^{p_1 + Y} = 2^{4 + 6} = 2^{10}$ 位元組。
  • 頁面大小 $= 2^X = 2^8$ 位元組。
  • 檢驗：$2^{10} > 2^8$（外層頁表大小大於單一頁面大小，需 4 個頁面才裝得下），故錯誤。

• 選項 (B) $(W, X, Y, Z) = (16, 12, 16, 8)$：

  • 內層頁表位元數 $p_2 = X - Z = 12 - 8 = 4$ 位元。
  • 外層頁表位元數 $p_1 = W - 2X + Z = 16 - 2(12) + 8 = 0$ 位元。

核心觀念

本題考查**機率型分頁替換演算法（Probabilistic Page Replacement Algorithm）與動態規劃／馬可夫鏈（Markov Chain）**結合的期望值計算。

1. 馬可夫轉移機率 (Transition Probabilities)：
   設第 $t$ 次存取的頁面為 $X_t \in \{P1, P2, P3\}$。當前存取頁面決定下一次存取頁面的機率分佈：

   • 若 $X_t = P1$，則 $P(X_{t+1} = P2) = 0.8$，$P(X_{t+1} = P3) = 0.2$。
   • 若 $X_t = P2$，則 $P(X_{t+1} = P1) = 0.6$，$P(X_{t+1} = P3) = 0.4$。
   • 若 $X_t = P3$，則 $P(X_{t+1} = P1) = 0.9$，$P(X_{t+1} = P2) = 0.1$。

2. 最佳分頁替換決策 (Optimal Eviction Decision)：
   系統共有 2 個 Frame。在發生 Page Fault 需進行頁面替換（Eviction）時，最佳演算法會在已知的下一次頁面出現機率下，保留下一次出現機率較高的頁面，剔除出現機率較低的頁面，以最小化未來的期望 Page Fault 次數。

3. 期望值計算 (Expected Page Faults)：
   第 $t$ 次存取的期望 Page Fault 次數定義為：
   $\mathbb{E}[\text{PF}_t] = \sum_{\text{所有可能路徑 } s} P(s) \times P(\text{在第 } t \text{ 次發生 Page Fault} \mid s)$

---

解題方法與詳細推導

題目給定初始狀態為：Frame 初始為空（$\emptyset$），共有 4 次存取（$t=1, 2, 3, 4$），且第 1 次存取 $X_1 = P1$。

第 1 次存取 ($t=1$)

• 請求：$X_1 = P1$。
• 記憶體狀態：初始為空 $\emptyset$。
• 結果：必定發生 Page Fault，將 $P1$ 載入 Frame 1。
• 記憶體集合變為 $M_1 = \{P1\}$。

---

第 2 次存取 ($t=2$)

• 請求：依據 $X_1 = P1$，下一次請求有兩種可能：
  • $X_2 = P2$（機率 $0.8$）
  • $X_2 = P3$（機率 $0.2$）
• 記憶體目前只有 $M_1 = \{P1\}$，不論 $X_2$ 是 $P2$ 或 $P3$，皆不在記憶體中。
• 結果：必定發生 Page Fault（Page Fault 機率為 $1$）。
• 記憶體更新（因為還有 1 個空 Frame，無需剔除頁面）：
  • 若 $X_2 = P2$（機率 0.8），記憶體變為 $M_2 = \{P1, P2\}$。
  • 若 $X_2 = P3$（機率 0.2），記憶體變為 $M_1 = \{P1, P3\}$。
• 第 2 次存取的期望 Page Fault 次數：
  $\mathbb{E}[\text{PF}_2] = 1$

---

第 3 次存取 ($t=3$)

根據 $t=2$ 的兩種可能分支進行分析：

1. 分支 A：$X_2 = P2$（發生機率 $0.8$），此時 $M_2 = \{P1, P2\}$
   由 $X_2 = P2$ 轉移至 $t=3$：

   • $X_3 = P1$（機率 $0.6$）：$P1 \in \{P1, P2\}$ $\implies$ Hit（Page Fault = 0）。
   • $X_3 = P3$（機率 $0.4$）：$P3 \notin \{P1, P2\}$ $\implies$ Fault（Page Fault = 1）。

2. 分支 B：$X_2 = P3$（發生機率 $0.2$），此時 $M_2 = \{P1, P3\}$
   由 $X_2 = P3$ 轉移至 $t=3$：

   • $X_3 = P1$（機率 $0.9$）：$P1 \in \{P1, P3\}$ $\implies$ Hit（Page Fault = 0）。
   • $X_3 = P2$（機率 $0.1$）：$P2 \notin \{P1, P3\}$ $\implies$ Fault（Page Fault = 1）。

• 第 3 次存取的期望 Page Fault 次數：
  $\mathbb{E}[\text{PF}_3] = 0.8 \times 0.4 + 0.2 \times 0.1 = 0.32 + 0.02 = 0.34$

---

第 4 次存取 ($t=4$)

我們需要追蹤 $t=3$ 的四種子路徑，並分析最佳演算法在發生 Page Fault 時的剔除決策：

路徑 1.1：$P1 \to P2 \to P1$（總機率 $0.8 \times 0.6 = 0.48$）

• $t=3$ 時 Hit，記憶體維持 $M_3 = \{P1, P2\}$。
• 當前頁面為 $X_3 = P1$，則 $X_4$ 的可能為：
  • $X_4 = P2$（機率 $0.8$）$\implies$ Hit（$P2 \in M_3$）。

核心觀念

1. 即時系統排程（Real-Time Scheduling）與 CPU 利用率（Utilization）：
   • 週期性任務（Periodic Process） $P_i$ 的 CPU 利用率定義為 $U_i = \frac{C_i}{T_i}$，其中 $C_i$ 為執行時間（Burst Time），$T_i$ 為週期（Period）。
   • 系統總 CPU 利用率為 $U = \sum U_i$。若總利用率 $U > 1$，代表長期要求的計算資源超過系統實質處理能力（100%），任何單處理器排程演算法都無法滿足需求。
2. 硬即時（Hard Real-Time, $S_i = 1$）與 軟度（Softness, $S_i$）：
   • 當 $S_i = 1$ 時，代表硬即時限制，每一個週期任務實例（Instance）都必須在截止時間（Deadline, $D_i$）前完成。
   • 當 $S_i = k > 1$ 時，代表連續 $k$ 個實例中至少有 1 個必須滿足 Deadline（意即允許放棄部分實例，但不可連續錯過 $k$ 個 Deadline）。
3. 截止時間限制（Constrained Deadline, $C_i \le D_i \le T_i$）：
   • 當 $D_i = T_i$（Implicit Deadline）時，在可搶佔（Preemptive）動態優先權排程（如 EDF, Earliest Deadline First）下，$U \le 1$ 為可排程（Schedulable）的充份且必要條件。
   • 當 $D_i < T_i$（Constrained Deadline）時，即使總利用率 $U \le 1$，由於任務要求在更短的時間內完成，仍可能因短期需求爆發而發生錯過 Deadline 的情況。因此 $U \le 1$ 並非可排程的充分條件。

---

解題方法

本題重點在於分析利用率的必要與充分條件，並利用反例驗證選項的正確性：

1. 必要條件檢驗：若硬即時任務（$S_i = 1$）要求的總利用率 $U > 1$，則必然無法排程（Non-schedulable）。
2. 反例法（Counterexample）檢驗充分性：題目給定條件 $C_i \le D_i \le T_i$，代表 $D_i$ 有可能嚴格小於 $T_i$（$D_i < T_i$）。當選項宣稱利用率滿足某條件就「必定可排程（must be schedulable）」時，只要舉出 $D_i < T_i$ 導致不可排程的極端反例，即可證明該選項錯誤。
3. Softness 的利用率折算：當 $S_2 = 2$ 時，$P_2$ 最多可以每隔一個實例放棄一次（即每 $2 T_2$ 時間執行一次 $C_2$），此時 $P_2$ 所需的最低平均利用率可降至 $\frac{C_2}{2 T_2}$。

---

選項分析

• (A) 正確

  • 條件：$S_1 = S_2 = 1$ 且 $\frac{C_1}{T_1} + \frac{C_2}{T_2} > 1$。
  • 分析：$S_1 = S_2 = 1$ 表示 $P_1$ 與 $P_2$ 的每一個實例都必須在 Deadline 前完成。此時系統要求的總 CPU 利用率為 $U = \frac{C_1}{T_1} + \frac{C_2}{T_2}$。若 $U > 1$，代表長期計算需求超過單處理器 100% 的負載上限，任何最佳排程演算法都無法滿足所有 Deadline。因此該問題必為不可排程（must be non-schedulable）。

• (B) 錯誤

  • 條件：$S_1 = S_2 = 1$ 且 $\frac{C_1}{T_1} + \frac{C_2}{T_2} \le 1$。
  • 分析：題目指出 $C_i \le D_i \le T_i$，即 Deadline $D_i$ 有可能小於週期 $T_i$。當 $D_i < T_i$ 時，即使長期平均利用率 $U \le 1$，仍可能因為短期內的執行時間擠壓在較短的 $D_i$ 內而無法及時完成。
  • 反例：設 $T_1 = 10, D_1 = 4, C_1 = 4$ 且 $T_2 = 10, D_2 = 4, C_2 = 4$。
    總利用率 $\frac{C_1}{T_1} + \frac{C_2}{T_2} = \frac{4}{10} + \frac{4}{10} = 0.8 \le 1$。
    但在 $t = 0$ 時，$P_1$ 與 $P_2$ 的第一個實例同時到達，兩者皆需在 $t = 4$ 前完成 $4\text{ msec}$ 的執行（共需 $8\text{ msec}$）。然而 $t = 0$ 到 $t = 4$ 只有 $4\text{ msec}$ 的 CPU 時間，故必有實例錯過 Deadline。因此該條件不能保證必定可排程。

本題考查的核心觀念是作業系統中的銀行家演算法 (Banker's Algorithm)，特別是判斷系統是否處於安全狀態 (safe state) 以及找出所有可能的安全序列 (safe sequence)。銀行家演算法是一種用於避免死鎖 (deadlock) 的演算法，它會檢查系統在分配資源後是否仍能找到一個序列，讓所有執行緒都能完成其工作，從而避免死鎖。

---

完整解題過程

1. 計算需求 (Need) 矩陣：
   首先，我們需要計算每個執行緒對每種資源的剩餘需求量 (Need)。Need[i][j] 表示執行緒 $T_i$ 對資源 $R_j$ 仍需要的最大數量。其計算公式為：
   $\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]$

   根據題目提供的 Max 和 Allocation 表格，我們可以計算出 Need 矩陣如下：

   • Max

     R0 R1 R2
     T0: 0  3  0
     T1: 3  6  5
     T2: 2  1  5
     T3: 5  6  1
     T4: 6  1  0
     T5: 4  1  3
     T6: 0  6  8
     

   • Allocation

     R0 R1 R2
     T0: 0  1  0
     T1: 1  2  2
     T2: 1  1  0
     T3: 1  2  0
     T4: 2  1  0
     T5: 1  1  1
     T6: 0  0  0
     

   • Need = Max - Allocation

     R0 R1 R2
     T0: 0  2  0  ($0-0=0, 3-1=2, 0-0=0$)
     T1: 2  4  3  ($3-1=2, 6-2=4, 5-2=3$)
     T2: 1  0  5  ($2-1=1, 1-1=0, 5-0=5$)
     T3: 4  4  1  ($5-1=4, 6-2=4, 1-0=1$)
     T4: 4  0  0  ($6-2=4, 1-1=0, 0-0=0$)
     T5: 3  0  2  ($4-1=3, 1-1=0, 3-1=2$)
     T6: 0  6  8  ($0-0=0, 6-0=6, 8-0=8$)
     

2. 初始化系統狀態：

   • Available = (3, 0, 6)
   • Work = Available
   • Finish = [false, false, false, false, false, false, false] (表示所有執行緒都尚未完成)
   • SafeSequencesCount = 0

3. 尋找所有安全序列 (使用回溯法)：
   我們需要一個回溯函數來探索所有可能的安全序列。該函數會接收當前的可用資源 work、已完成執行緒的集合 finished_mask (用位元遮罩表示，方便追蹤)，以及已完成的執行緒數量 num_finished。

   can_execute(thread_idx, work, finished_mask) 函數用於判斷執行緒 thread_idx 是否可以執行：

   • 如果 thread_idx 已經完成 ((finished_mask >> thread_idx) & 1 為真)，則不能執行。
   • 如果 Need[thread_idx] 中的所有資源需求都小於或等於 work 中的對應資源，則可以執行。
   • 否則，不能執行。

   backtrack(work, finished_mask, num_finished) 函數的邏輯如下：

   • 基本情況： 如果 num_finished == 7 (所有執行緒都已完成)，則找到一個安全序列，SafeSequencesCount 加一，並返回。
   • 遞迴步驟： 遍歷所有尚未完成的執行緒 $T_i$。
     • 如果 $T_i$ 可以執行 (can_execute(i, work, finished_mask) 為真)：
       • 更新 work：new_work = work + Allocation[i]
       • 更新 finished_mask：new_finished_mask = finished_mask | (1 << i)
       • 遞迴呼叫 backtrack(new_work, new_finished_mask, num_finished + 1)。
       • 回溯： 由於我們需要找到所有序列，在遞迴呼叫返回後，不需要恢復 work 和 finished_mask，因為它們是傳值或在遞迴中創建新的副本。
     • 如果遍歷完所有執行緒後，沒有任何執行緒可以執行，但 num_finished < 7，表示系統進入死鎖狀態，此路徑不是安全序列，直接返回。

   詳細回溯過程：

   • 初始狀態： Work = (3, 0, 6), Finished = [] (0 threads finished)
     • 可執行的執行緒：
       • $T_0$: Need=(0,2,0). $R_1$: $2 > 0$. 不可。
       • $T_1$: Need=(2,4,3). $R_1$: $4 > 0$. 不可。
       • $T_2$: Need=(1,0,5). $R_0: 1 \le 3, R_1: 0 \le 0, R_2: 5 \le 6$. 可執行。
       • $T_3$: Need=(4,4,1). $R_0: 4 > 3, R_1: 4 > 0$. 不可。
       • $T_4$: Need=(4,0,0). $R_0: 4 > 3$. 不可。
       • $T_5$: Need=(3,0,2). $R_0: 3 \le 3, R_1: 0 \le 0, R_2: 2 \le 6$. 可執行。
       • $T_6$: Need=(0,6,8). $R_1: 6 > 0, R_2: 8 > 6$. 不可。
     • 因此，第一個可以執行的執行緒可以是 $T_2$ 或 $T_5$。

   路徑 1：從 $T_2$ 開始

   • 序列：[T2]

   • Work = (3,0,6) + Allocation[T2] = (3,0,6) + (1,1,0) = (4,1,6)

   • 已完成：{T2}

   • 在 Work=(4,1,6) 狀態下，可執行的執行緒：

     • $T_0$: Need=(0,2,0). $R_1: 2 > 1$. 不可。
     • $T_1$: Need=(2,4,3). $R_1: 4 > 1$. 不可。
     • $T_3$: Need=(4,4,1). $R_1: 4 > 1$. 不可。
     • $T_4$: Need=(4,0,0). $R_0: 4 \le 4, R_1: 0 \le 1, R_2: 0 \le 6$. 可執行。
     • $T_5$: Need=(3,0,2). $R_0: 3 \le 4, R_1: 0 \le 1, R_2: 2 \le 6$. 可執行。
     • $T_6$: Need=(0,6,8). $R_1: 6 > 1, R_2: 8 > 6$. 不可。
     • 因此，接下來可以是 $T_4$ 或 $T_5$。

     路徑 1.1：$T_2 \to T_4$

     • 序列：[T2, T4]
     • Work = (4,1,6) + Allocation[T4] = (4,1,6) + (2,1,0) = (6,2,6)
     • 已完成：{T2, T4}
     • 在 Work=(6,2,6) 狀態下，可執行的執行緒：$T_0, T_5$
       • 路徑 1.1.1：$T_2 \to T_4 \to T_0$
         • 序列：[T2, T4, T0]
         • Work = (6,2,6) + Allocation[T0] = (6,2,6) + (0,1,0) = (6,3,6)
         • 已完成：{T0, T2, T4}
         • 在 Work=(6,3,6) 狀態下，可執行的執行緒：$T_5$
           • 路徑 1.1.1.1：$T_2 \to T_4 \to T_0 \to T_5$
             • 序列：[T2, T4, T0, T5]
             • Work = (6,3,6) + Allocation[T5] = (6,3,6) + (1,1,1) = (7,4,7)
             • 已完成：{T0, T2, T4, T5}
             • 在 Work=(7,4,7) 狀態下，可執行的執行緒：$T_1, T_3$
               • 路徑 1.1.1.1.1：$T_2 \to T_4 \to T_0 \to T_5 \to T_1$
                 • 序列：[T2, T4, T0, T5, T1]
                 • Work = (7,4,7) + Allocation[T1] = (7,4,7) + (1,2,2) = (8,6,9)
                 • 已完成：{T0, T1, T2, T4, T5}