114 年 國立臺灣大學資訊工程學系碩士班《計算機結構與作業系統》

核心觀念

本題旨在考驗作業系統（Operating Systems）中**臨界區段問題（Critical-Section Problem）與同步機制（Synchronization Primitives）**的核心觀念與運作機制。

解決臨界區段問題必須同時滿足以下三個條件：

1. 互斥（Mutual Exclusion）：若有行程在臨界區段內執行，則其他行程皆不得進入其臨界區段。
2. 進展（Progress）：若沒有行程在臨界區段內執行，且有行程想要進入，則只有不在剩餘區段（Remainder Section）執行的行程可以參與決定誰下一個進入臨界區段，且此決定不可無限期延遲。
3. 有限等待（Bounded Waiting）：行程提出進入臨界區段的請求後，在該請求被允許之前，其他行程進入臨界區段的次數必須有上限。

為達成互斥並保護共享記憶體變數免於併發更新（Concurrent Updates）導致的競態條件（Race Condition），常見的硬體與軟體同步工具包括：

• 記憶體屏障（Memory Barriers / Fences）：強制記憶體操作的執行順序，避免編譯器或 CPU 亂序執行（Out-of-Order Execution），確保記憶體可見性與一致性。
• 原子指令（Atomic Instructions）：硬體提供的不可中斷操作（如 TestAndSet、CompareAndSwap），作為建立高階同步工具的基礎構造塊（Building Blocks）。
• 號誌（Semaphores）：提供 wait()（或 $P$）與 signal()（或 $V$）操作。分為二元號誌（Binary Semaphore）與計數號誌（Counting Semaphore）。
• 互斥鎖（Mutex Locks）：專門用於實現互斥鎖定的高階同步機制，擁有者（Owner）在進入臨界區段前取得鎖（Acquire），離開後釋放鎖（Release）。

---

解題方法

本題為單選題，解題切入點為比對各選項所述同步工具的功能定義與運作邏輯，確認何者能正確描述保護共享記憶體併發更新的互斥機制。

在標準的臨界區段程式結構中：

do {
    // 1. 進入區段 (Entry Section)：取得存取權/鎖
    /* acquire lock / wait(mutex) */

    // 2. 臨界區段 (Critical Section)：更新共享記憶體
    /* Update shared memory variables */

    // 3. 退出區段 (Exit Section)：釋放存取權/鎖
    /* release lock / signal(mutex) */

    // 4. 剩餘區段 (Remainder Section)
    /* Other operations */
} while (true);

當使用鎖定機制保障互斥性時，行程必須在進入臨界區段更新共享記憶體前取得鎖定，並於更新完成離開時釋放鎖定。

---

選項分析

核心觀念

本題旨在考驗對**獨立磁碟冗餘陣列（RAID, Redundant Array of Inexpensive Disks）的定義、各等級（RAID Levels）架構特性、嵌套式 RAID 組合順序，以及儲存系統可靠度（Reliability）與平均資料遺失時間（MTTDL, Mean Time to Data Loss）**的數學推導。

1. RAID 等級定義：

   • RAID 0：區塊拆分條帶化（Striping），提升效能但無冗餘（No Redundancy）。
   • RAID 1：磁碟鏡像（Mirroring），提供完全備份。
   • RAID 4：區塊級條帶化 + 獨立奇偶校驗碼磁碟（Block-interleaved dedicated parity）。
   • RAID 5：區塊級分散式奇偶校驗碼（Block-interleaved distributed parity），將 Parity 區塊均勻分散於陣列中各磁碟，解決 RAID 4 的 Parity 磁碟寫入瓶頸。
   • RAID 01 vs. RAID 10：嵌套式 RAID 架構。RAID 01 (RAID 0+1) 為先條帶化再鏡像（Striped first, mirrored later）；RAID 10 (RAID 1+0) 為先鏡像再條帶化（Mirrored first, striped later）。

2. 可靠度與 MTTDL 計算：

   • 平行處理（Parallelism）若無容錯機制，會隨磁碟數量增加而降低系統可靠度。
   • 在雙磁碟鏡像系統（RAID 1）中，平均資料遺失時間 $MTTDL$ 的公式為：
     $MTTDL = \frac{MTTF_{\text{single}}^2}{2 \times MTTR}$
     其中 $MTTF_{\text{single}}$ 為單一磁碟的平均無故障時間（Mean Time To Failure），$MTTR$ 為平均修復時間（Mean Time To Repair）。

---

解題方法

本題為標準的觀念辨析與數值驗算題，解題切入點如下：

1. 檢視 RAID 各等級之標準語義定義，比對 RAID 5 的區塊層級與 parity 配置方式。
2. 代入 RAID 1 的 $MTTDL$ 算式，進行精確的時間單位換算與數值驗算。
3. 區分 RAID 10 與 RAID 01 在子陣列組合順序上的結構差異。
4. 釐清「平行處理（Parallelism）」與「冗餘（Redundancy）」對系統故障率的根本影響。

---

選項分析

• a. 錯誤。
  單純多磁碟平行處理（Parallelism，如 RAID 0 的條帶化）僅能提升讀寫效能（Performance），反而會因為參與的硬碟數量增加而降低系統整體的可靠度（$MTTF_{\text{system}} = MTTF_{\text{single}} / N$）。系統可靠度的提升來自於「冗餘（Redundancy）」（如鏡像或偶數檢查碼），而非「平行處理」。

核心觀念

1. 行程創建與獨立位址空間（Process Creation & Separate Address Space）
   在 POSIX 標準作業系統中，執行 fork() 系統呼叫會建立一個全新的子行程（Child Process）。子行程會完整複製父行程（Parent Process）的位址空間（包含 Code Segment、Data Segment、Heap 與 Stack）。在邏輯上，父行程與子行程擁有各自獨立的記憶體空間，因此子行程對全域變數或區域變數所發生的任何數值修改，完全不會影響父行程中的變數數值。現代作業系統大多採用寫入時複製（Copy-on-Write, COW）技術優化記憶體，但語意上仍嚴格保證記憶體空間的隔離性。

2. 行程同步與印出順序（Process Synchronization & Execution Order）
   wait(NULL) 系統呼叫會將父行程掛起（Block），直到其子行程執行完畢並終止（Terminate）為止。此機制不僅能防止子行程變成殭屍行程（Zombie Process），更能確保子行程的輸出必定早於父行程的輸出。

---

解題方法

本題需透過追蹤 fork() 呼叫後的父子行程執行流程與記憶體狀態變化來分析輸出結果：

// 關鍵程式碼片段與執行流追蹤
int value = 10; // 全域變數，位於 Data Segment

int main() {
    pid_t pid = fork();

    if (pid == 0) { // 子行程分支
        value = value + 10; // 修改子行程獨立的 Data Segment (value 變為 20)
        printf("A = %d\n", value); // 印出 A = 20
        return 0;
    } else if (pid > 0) { // 父行程分支
        wait(NULL); // 父行程阻塞，等待子行程結束
        printf("B = %d\n", value); // 印出 B = 10 (父行程的 value 仍為 10)
        return 0;
    }
}

1. 初始狀態：
   全域變數 value 初始值為 $10$。

2. 執行 fork() 後的分支評估：

   • 子行程（Child Process）：fork() 回傳值 pid == 0。
     • 子行程複製父行程的 value（初始值為 $10$）。
     • 執行 value = value + 10;，此時子行程記憶體中的 value 更新為 $20$。
     • 執行 printf("A = %d\n", value);，在標準輸出印出 A = 20。
     • 子行程執行 return 0; 結束行程。

頁面大小 $2\text{KB}=2^{11}$ 位元組，實體記憶體 $64\text{KB}=2^{16}$ 位元組。

• 偏移位元 $=11$。
• 實體頁框數 $=64\text{KB}/2\text{KB}=32$，框號需 $\log_2 32=5$ 位。
• 因此實體位址位元 $P=5+11=16$。

單層頁表有 $1024$ 個項目 ⇒ 邏輯頁數 $2^{10}$，頁號需 $10$ 位。

• 邏輯位址位元 $L=10+11=21$。

傳統單層頁表

• 命中時需兩次記憶體存取：$180\text{ns}$ (讀頁表) + $180\text{ns}$ (讀資料) = $360\text{ns}$。
• 命中率 $0.6$，缺頁服務時間 $30{,}000\ \mu\text{s}=30{,}000{,}000\text{ns}$。
• 平均有效存取時間

$$X =0.6\cdot360 +0.4\cdot30{,}000{,}000 =216 +12{,}000{,}072 =12{,}000{,}288\text{ns}\;(≈12\text{ms})$$

倒置頁表
倒置表每一實體框一項 ⇒ $N=32$。
TLB 檢查時間 $30\text{ns}$，命中率 $0.9$。

• 命中：$30\text{ns}$ (TLB) + $180\text{ns}$ (資料) = $210\text{ns}$。

步驟與計算

1. 位元分割

   • 頁面大小 $8\text{KB}=2^{13}$，故頁位元 $D=\log_2 8192=13$。
   • 處理器位址長度 $32$ 位元，故頁號位元 $P=32-D=19$。

2. 頁號求得
   頁號 = 位址右移 $13$ 位 (即除以 $2^{13}=8192$)。

$$\begin{aligned} 0x4DF6BC24 &\rightarrow 159\,669\\ 0x1CA54523 &\rightarrow 3\,666\\ 0x4DF6AC24 &\rightarrow 159\,669\\ 0x1CA55523 &\rightarrow 3\,666\\ 0x23A22260 &\rightarrow 4\,561 \end{aligned}$$

3. 工作集大小 $M$
   工作集視窗 $W=6$，因總參考次數 $5<6$，每一步的工作集即已出現的不同頁號數量：

   • 1, 2, 2, 2, 3 → 最大工作集大小 $M=3$。

4. 頁錯誤次數 $F$

   • 初始 3 個空框架。
   • 依序載入 159669、3666、4561，只有在第一次、第二次、第五次參考時缺頁。
   • 故 $F=3$。

本題考查作業系統中檔案開啟與管理的流程，特別是檔案描述符、系統開檔表、目錄結構和檔案控制區塊 (FCB) 等概念。題目附圖顯示了一個從使用者空間到核心、再到次級儲存的檔案開啟流程圖，其中標註了編號的操作。

首先解析圖中標號的意義：
圖中顯示了從 "user space" 發起 "Opening file" 的操作。

1. Operation 1: 看起來是檢查目錄結構 (Directory Structure) 中的檔案是否存在或進行查找。
2. Operation 2: 看起來是建立一個 "system-wide open-file table" 的條目。
3. Operation 3: 看起來是建立一個 "per-process open-file table" 的條目，並返回一個 "file descriptor" 給使用者空間。
4. Operation 4: 看起來是從次級儲存 (Secondary Storage) 載入檔案資訊到核心記憶體中的檔案控制區塊 (File Control Block, FCB)。FCB 包含了檔案的所有元數據。

現在分析各個選項：

(A) Operation 1 will be conducted to ensure that there is no duplicated file in the same directory.
- Operation 1 是在目錄結構中查找檔案。檔案系統通常不允許在同一個目錄下存在同名的檔案。當嘗試創建一個新檔案時，Operation 1 會檢查是否存在同名檔案以防止重複。但是，僅僅是「開啟 (opening)」檔案時，Operation 1 的主要目的是查找檔案是否存在並獲取其元數據，而不是確保沒有重複檔案。確保沒有重複檔案是在檔案「創建 (creation)」時的檢查。因此，這個敘述不完全精確。

(B) Operation 3 refers to the file descriptor to the system-wide open-file table to create an entry.
- Operation 3 是在「per-process open-file table」中創建一個條目，並將其索引（即檔案描述符，file descriptor）返回給使用者行程。它指向的是系統級開檔表 (system-wide open-file table) 中的一個條目，而不是直接在系統級開檔表「創建」條目。系統級開檔表的條目是由 Operation 2 創建的。因此，這個敘述不正確。

核心觀念

本題考驗作業系統（Operating System）中 CPU 排程演算法（CPU Scheduling Algorithms）的 輪轉排程法（Round-Robin Scheduling, RR），以及行程時間指標的推導與代數系統化簡。

1. 輪轉排程法（Round-Robin Scheduling, RR）

• 機制：RR 排程為搶佔式（Preemptive）排程演算法，系統將 CPU 時間劃分為固定長度的時間區段，稱為時間切片（Time Quantum / Time Slice, $q$）。
• 佇列管理：系統維護一個先進先出（FIFO）的 Ready Queue。當新行程抵達或被搶佔時，會被放入佇列尾端；CPU 總是挑選佇列前端的行程執行。
• 搶佔規則：若行程在單次時間切片 $q$ 內未執行完畢，系統會觸發定時器中斷（Timer Interrupt），將該行程搶佔並移至 Ready Queue 尾端，再由下一個行程接續執行。

2. 行程時間指標與計算公式

• 完成時間（Completion Time, $C_i$）：行程 $P_i$ 結束執行的時間點。
• 轉返時間（Turnaround Time, $TAT_i$）：行程從抵達到執行完成的總時間差：
  $TAT_i = C_i - A[i]$
• 等待時間（Waiting Time, $W_i$）：行程在 Ready Queue 中等待 CPU 的累計時間：
  $W_i = TAT_i - B[i] = C_i - A[i] - B[i]$
• 平均等待時間（Average Waiting Time, $\text{AWT}$）：所有行程等待時間的算術平均值：
  $\text{AWT} = \frac{1}{n} \sum_{i=1}^{n} W_i$

---

解題方法

步驟一：分析題目資訊與甘特圖（Gantt Chart）推導

題目給定 5 個行程，抵達時間皆為 $A[i] = 0$，Burst Time 分別為 $B[1]=10, B[2]=3, B[3]=5, B[4]=4, B[5]=2$。

在完整題目規範中，進行輪轉排程必須指定時間切片 $q$。若以常規時間切片 $q = 1$ 為例，行程初始佇列順序為 $[P_1, P_2, P_3, P_4, P_5]$，執行甘特圖如下：

• $t = 0 \to 5$：$P_1, P_2, P_3, P_4, P_5$ 依序各執行 $1$ 單位時間。
  • 各行程剩餘 Burst Time：$P_1(9), P_2(2), P_3(4), P_4(3), P_5(1)$。
• $t = 5 \to 10$：$P_1, P_2, P_3, P_4, P_5$ 依序各執行 $1$ 單位時間。
  • 行程 $P_5$ 於 $t = 10$ 執行完畢，完成時間 $C_5 = 10$。
  • 剩餘行程 Burst Time：$P_1(8), P_2(1), P_3(3), P_4(2)$。
• $t = 10 \to 14$：$P_1, P_2, P_3, P_4$ 依序各執行 $1$ 單位時間。
  • 行程 $P_2$ 於 $t = 12$ 執行完畢，完成時間 $C_2 = 12$。
  • 剩餘行程 Burst Time：$P_1(7), P_3(2), P_4(1)$。
• $t = 14 \to 17$：$P_1, P_3, P_4$ 依序各執行 $1$ 單位時間。
  • 行程 $P_4$ 於 $t = 17$ 執行完畢，完成時間 $C_4 = 17$。
  • 剩餘行程 Burst Time：$P_1(6), P_3(1)$。
• $t = 17 \to 19$：$P_1, P_3$ 依序各執行 $1$ 單位時間。
  • 行程 $P_3$ 於 $t = 19$ 執行完畢，完成時間 $C_3 = 19$。
  • 剩餘行程 Burst Time：$P_1(5)$。
• $t = 19 \to 24$：$P_1$ 獨佔執行剩餘的 $5$ 單位時間。
  • 行程 $P_1$ 於 $t = 24$ 執行完畢，完成時間 $C_1 = 24$。

步驟二：計算等待時間與平均等待時間

根據 $W_i = C_i - A[i] - B[i]$，計算各行程等待時間：

• $W_1 = 24 - 0 - 10 = 14$

核心觀念

1. 即時系統排程（Real-Time Scheduling）：
   • Deadline-Monotonic (DM) 排程演算法：屬於靜態優先級（Static Priority / Fixed Priority）搶佔式排程。優先級分配原則為相對截止時間（Relative Deadline, $D_i$）越短者，優先級越高。
   • Rate-Monotonic (RM) 排程演算法：優先級分配原則為週期（Period, $T_i$）越短者，優先級越高。當任務的相對截止時間等於週期（$D_i = T_i$）時，DM 與 RM 等價；但若 $D_i \le T_i$，DM 為最佳靜態優先級排程演算法（Optimal Static Priority Scheduling Algorithm）。
2. 最差回應時間分析（Worst-Case Response Time, WCRT Analysis）：
   • 任務 $P_i$ 的回應時間 $R_i$ 為從到達時間（Arrival Time）至執行完成時間（Completion Time）的時間差。
   • 當所有任務同時於 $t=0$ 到達時（Critical Instant），$P_i$ 的最差回應時間公式為迭代式：
     $R_i^{(k+1)} = C_i + \sum_{j \in HP(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$
     其中 $C_i$ 為任務 $P_i$ 的 Burst Time（執行時間），$HP(i)$ 表示優先級高於 $P_i$ 的任務集合（Higher-Priority Tasks）。
3. 可排程性（Schedulability）：
   • 任務 $P_i$ 為可排程（Schedulable），若且唯若其最差回應時間不超過相對截止時間，即 $R_i \le D_i$。
   • 若任務集中存在至少一個任務滿足 $R_i > D_i$，則該任務集不可排程（Unschedulable）。

---

解題方法

Step 1: 確定 DM 與 RM 下的優先級排序

整理題目所給定之各任務參數：

• $P_1: D_1 = 10, T_1 = 50, C_1 = 10$

• $P_2: D_2 = 10, T_2 = 120, C_2 = 5$

• $P_3: D_3 = 5, T_3 = 800, C_3 = 10$

• $P_4: D_4 = 10, T_4 = 20, C_4 = 10$

• $P_5: D_5 = 10, T_5 = 40, C_5 = 10$

• DM 優先級（依 $D_i$ 由小到大排序）：
  $D_3 = 5 < D_1 = D_2 = D_4 = D_5 = 10$。
  $P_3$ 擁有嚴格最小的相對截止時間，故 $P_3$ 具有最高優先級。

• RM 優先級（依 $T_i$ 由小到大排序）：
  $T_4 (20) < T_5 (40) < T_1 (50) < T_2 (120) < T_3 (800)$。
  優先級順序為 $P_4 > P_5 > P_1 > P_2 > P_3$。

Step 2: 驗證關鍵任務之 WCRT 與可排程性

1. $P_3$ 在 DM 下的 WCRT：
   由於 $P_3$ 為最高優先級任務，$HP(P_3) = \emptyset$，不受任何其他任務搶佔：
   $R_3 = C_3 = 10$
   因為 $R_3 = 10 > D_3 = 5$，$P_3$ 錯過截止時間。因此，$P_3$ 不可排程，整個任務集在 DM 下為不可排程（Unschedulable）。

核心觀念

本題涵蓋作業系統（Operating Systems）與計算機結構（Computer Architecture）的四大核心主題：

1. 平行度與性能分析（Parallelism and Amdahl's Law）：系統核心數與加速比（Speedup）的非線性關係，以及硬體開銷與不可平行化程式碼對效能的限制。
2. 併行與平行（Concurrency vs. Parallelism）：兩者的定義區別。併行是指多個任務在重疊的時間區段內皆能取得進展（可透過單核心時分複用實現）；平行則是指多個任務在同一實體時間點同時執行（必須具備多核心或多處理器硬體）。
3. 執行緒模型與同步（Threading API and Synchronization）：POSIX Threads (pthread) 中的同步執行緒（Synchronous threading，如使用 pthread_join() 等待子執行緒）與非同步執行緒（Asynchronous threading）之定義差別。
4. 行程狀態轉移模型（Process State Transitions）：標準五態模型（New, Ready, Running, Waiting, Terminated）中各狀態間的轉移條件（Waiting 狀態完成 I/O 或事件後應轉入 Ready 狀態，再由排程器派發至 Running 狀態）。
5. 記憶體位址綁定（Address Binding）：編譯時期（Compile time）、載入時期（Load time）與執行時期（Execution / Run time）綁定之分類。編譯時期與載入時期位址綁定屬於靜態綁定（Static binding）；僅有執行時期位址綁定才稱為動態綁定（Dynamic binding）。

---

解題方法

針對觀念選錯／選對題，切入點為比對作業系統權威教材（如 Silberschatz 之 Operating System Concepts）之定義與邏輯推論：

1. 分析 (A)：檢視關鍵字「always」，代入阿姆達爾定律（Amdahl's Law）公式 $S = \frac{1}{(1-P) + \frac{P}{N}}$ 與系統實際維護開銷（通訊、同步、排程），判斷是否能達成絕對的雙倍加速。
2. 分析 (B)：釐清 Concurrency（併行）與 Parallelism（平行）的層次差異，驗證單核心系統交錯執行行程是否符合「Concurrent without Parallel」。
3. 分析 (C)：核對 Pthreads API 之行為與觀念定義，pthread_join() 係使父執行緒進入阻塞狀態直到子執行緒結束，此行為定義為 Synchronous Threading（同步執行緒）。
4. 分析 (D)：繪製五態行程轉移圖（Process State Diagram），確認 Waiting 狀態發生事件完成時的正確轉移方向（ Waiting $\rightarrow$ Ready $\rightarrow$ Running）。
5. 分析 (E)：比對記憶體管理中編譯時期位址綁定（Compile-time address binding）對應的是 Static binding 還是 Dynamic binding。

---

選項分析

• (A) 錯誤
  根據阿姆達爾定律（Amdahl's Law），若程式中存在不可平行化的序列區段（比例為 $1-P$），其加速比上限為 $S = \frac{1}{(1-P) + \frac{P}{N}}$ 其中 $N=2$ 為核心數。即便 $P=1$（完全可平行化），在實際系統中亦會因執行緒建立開銷、同步鎖定競爭、快取一致性（Cache Coherence）開銷及記憶體頻寬瓶頸，導致加速比小於 $2$。因此「總是能獲得雙倍加速（always get a double speedup）」之敘述完全不成立。

解題重點

1. mov 0x120(%rsi),%ecx 取得位於 %rsi+0x120 的 32‑bit 整數，記為 cnt。
2. add %ecx,%ecx 使 cnt 變為 2·cnt。
3. lea (%rsi,%rcx,8),%rdx 等價於 %rdx = %rsi + (2·cnt)·8 = %rsi + cnt·16，可視為 以 16 為元素大小的陣列索引。
4. mov (%rdx),%r8 取該元素的 第 0 個 8‑byte 欄位。
5. mov 0x8(%rdx),%rax 取 第 1 個 8‑byte 欄位。

核心觀念

本題的核心為計算機結構中最基礎且最重要的 CPU 效能公式（CPU Performance Equation） 與 效能加速比（Speedup）：

1. CPU 執行時間公式：

   $$\text{CPU Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time } (T_c) = \frac{\text{IC} \times \text{CPI}}{\text{Clock Rate } (f)}$$
   • $\text{IC}$：程式執行的總指令數（Instruction Count）
   • $\text{CPI}$：每條指令所需的平均時脈週期數（Cycles Per Instruction）
   • $T_c$：時脈週期時間（Clock Cycle Time），單位為秒（$\text{s}$）
   • $f$：時脈頻率／速率（Clock Rate），$f = \frac{1}{T_c}$，單位為赫茲（$\text{Hz}$）

2. 加速比（Speedup）公式：

   $$\text{Speedup} = \frac{\text{Execution Time}_{\text{old}}}{\text{Execution Time}_{\text{new}}} = \frac{\text{CPU Time}_{\text{base}}}{\text{CPU Time}_{\text{target}}}$$

---

解題方法

根據題意整理基準處理器與各編譯器的已知條件：

• 處理器時脈週期時間：$T_c = 1\text{ ns} = 1.0 \times 10^{-9}\text{ s}$（時脈頻率 $f = 1\text{ GHz} = 1.0 \times 10^9\text{ Hz}$）
• 編譯器 A（Compiler A）：
  • 指令數 $\text{IC}_A = 1.0 \times 10^9$
  • 執行時間 $\text{CPU Time}_A = 1.5\text{ s}$
• 編譯器 B（Compiler B）：
  • 指令數 $\text{IC}_B = 1.5 \times 10^9$
  • 執行時間 $\text{CPU Time}_B = 1.8\text{ s}$

---

選項分析

選項 (A)

由效能公式推導編譯器 A 的平均 CPI：

$$\text{CPU Time}_A = \text{IC}_A \times \text{CPI}_A \times T_c$$ $$1.5 = 1.0 \times 10^9 \times \text{CPI}_A \times 10^{-9} \implies \text{CPI}_A = 1.5$$

因此編譯器 A 的平均 CPI 為 $1.5$。
此選項正確。

---

選項 (B)

由效能公式推導編譯器 B 的平均 CPI：

$$\text{CPU Time}_B = \text{IC}_B \times \text{CPI}_B \times T_c$$ $$1.8 = 1.5 \times 10^9 \times \text{CPI}_B \times 10^{-9} \implies \text{CPI}_B = \frac{1.8}{1.5} = 1.2$$

因此編譯器 B 的平均 CPI 應為 $1.2$，而非 $1.5$。
此選項錯誤。

---

選項 (C)

設執行編譯器 A 程式碼的處理器為 Processor A（時脈頻率為 $f_A$），執行編譯器 B 程式碼的處理器為 Processor B（時脈頻率為 $f_B$）。

兩者所消耗的總時脈週期數（Clock Cycles）分別為：

• $\text{Cycles}_A = \text{IC}_A \times \text{CPI}_A = 1.0 \times 10^9 \times 1.5 = 1.5 \times 10^9\text{ cycles}$

核心觀念

1. 流水線時脈週期（Pipelined Clock Cycle Time）：
   在流水線架構中，時脈週期取決於延遲最長（最慢）的階段（Bottleneck Stage）：
   $T_{\text{clock, pipelined}} = \max(T_{\text{IF}}, T_{\text{ID}}, T_{\text{EX}}, T_{\text{MEM}}, T_{\text{WB}})$

2. 非流水線指令總延遲（Non-pipelined Instruction Latency）：
   在非流水線單週期處理器中，指令的總延遲為該指令所需經過的所有階段延遲之和：
   $\text{Latency}_{\text{non-pipelined}} = \sum T_{\text{required stages}}$

3. 流水線指令總延遲（Pipelined Instruction Latency）：
   在流水線處理器中，指令經過所有階段所需的總時間，為「階段數 $\times$ 時脈週期」：
   $\text{Latency}_{\text{pipelined}} = N_{\text{stages}} \times T_{\text{clock, pipelined}}$

4. 資料記憶體使用率（Data Memory Utilization）：
   資料記憶體僅在 MEM 階段被存取。因此，使用率為執行記憶體存取指令（LW 與 SW）的比例總和：
   $\text{Utilization}_{\text{Data Memory}} = P_{\text{LW}} + P_{\text{SW}}$

---

解題方法

已知各階段延遲：
$T_{\text{IF}} = 150 \text{ ps}$, $T_{\text{ID}} = 250 \text{ ps}$, $T_{\text{EX}} = 50 \text{ ps}$, $T_{\text{MEM}} = 200 \text{ ps}$, $T_{\text{WB}} = 100 \text{ ps}$

指令混合比例：
$\text{ALU} = 45\%$, $\text{BEQ} = 20\%$, $\text{LW} = 20\%$, $\text{SW} = 15\%$

關鍵推導步驟：

1. 求流水線時脈週期 $T_{\text{clock, pipelined}}$：
   $T_{\text{clock, pipelined}} = \max(150, 250, 50, 200, 100) = 250 \text{ ps}$

2. 求 LW 指令在非流水線處理器中的總延遲：
   LW 指令需要經過完整 5 個階段（IF, ID, EX, MEM, WB）：
   $\text{Latency}_{\text{LW, non-pipelined}} = 150 + 250 + 50 + 200 + 100 = 750 \text{ ps}$

步驟

1. 第 1 條 addi x3, x0, 0x18 → x3 = 0x18 = 24。
2. 第 2 條 lw x4, 0(x3) 以 x3 為基址取記憶體位址 24 的字，得到 x4 = MEM[24]。
3. 第 3 條 addi x3, x0, 0x18 再次把 x3 設為 24（與第 1 條相同）。

解題步驟

1. 設快取有 $S$ 個集合（set），每組 2 個快取列（way）。
2. 每列需儲存

• valid 位元 1
• dirty 位元 1
• LRU 追蹤：對 2‑way 只需 1 位元每組，等效於每列 0.5 位元，於計算上取整為每列 1 位元（最保守估計）。
  因此每列至少需 3 位元（V、D、LRU）作為「標籤儲存」的最小需求。

3. 標籤儲存總位元數給定為 $2^{24}=16\,777\,216$ 位元。
   每列 3 位元 → 列數

$\text{列數}= \frac{2^{24}}{3}=5\,592\,405\ \text{列}$

計算步驟：

1. 位元組大小

   • 每個快取區塊 = 8 B → 區塊位元組位元 (block offset) = $\log_2 8 = 3$ bit。
   • 每頁大小 = 1 KB = $2^{10}$ B → 頁面位元組位元 = $10$ bit。

2. 虛擬位址結構（20 bit）

$$\underbrace{\text{VPN}}_{10\text{bit}}\; \underbrace{\text{PO}}_{10\text{bit}}= \underbrace{\text{VPN}}_{10\text{bit}}\; \underbrace{\text{block\ offset}}_{3\text{bit}}\; \underbrace{\text{page\ offset (剩餘)}}_{7\text{bit}}$$

3. 采用 virtual‑index / physical‑tag，因此索引位元只能取自虛擬位址的低位，且必須落在同一頁內。
   • 低 $7$ bit（頁面位元組位元中去掉區塊位元）必然屬於索引。

步驟概覽

1. 迴圈次數
   起始位址 : x11 ← x11 + 16
   每次遞增 : x11 ← x11 + 8
   結束位址 : x12 = x10 + x5

   迴圈執行次數

$N = \frac{x5-16}{8}+1=\frac{x5}{8}-1$

2. 指令排程（使用 fmv.d）

   • 第一輪 必須從記憶體載入兩個浮點值：
     fld f0, -16(x11)、fld f1, 0(x11)
   • 之後每輪 只需載入一個新值 (fld f1) 並用 fmv.d 把前一次的結果搬到 f0。

   各指令延遲（cycle）

$$\begin{aligned} &\text{fmv.d}=1,\quad \text{fld}=6,\quad \text{fadd.d}=4,\\ &\text{fsd}=1,\quad \text{addiu}=1,\quad \text{ble}=1 \end{aligned}$$

核心觀念

本題考兩核心處理器的排程與功能單元衝突。每個核心每週期有兩個功能單元，因此最多可同時執行兩個操作；兩個核心分別執行執行緒 X、Y。

排程時要遵守：

• 資料相依：後續操作必須等前一操作完成，才能執行。
• 功能單元衝突：兩個操作需要同一功能單元時，不能重疊執行。
• 超純量與亂序執行：每週期最多執行兩個操作；若操作彼此獨立且功能單元可用，可以同時執行。
• 浪費的槽位：在四週期的總執行期間，每個核心每週期有兩個功能單元槽位。未執行操作的槽位計為浪費；執行兩週期的 A1 在第二週期仍占用一個功能單元槽位。

解題方法與排程

先分別排程兩條執行緒，再以較長的執行緒決定總週期數。

週期	核心 1：執行緒 X	核心 2：執行緒 Y
1	A1（執行中）、空槽	B1、B3
2	A1（續行）、空槽	B2、空槽
3	A2、A3	B4、空槽
4	A4、空槽	空槽、空槽

X 的 A1 需兩週期，因此 A2 必須等 A1 完成後才能執行。A3 與 A1 有功能單元衝突，也要等 A1 完成；第 3 週期 A2、A3 可同時執行。A4 依賴 A2，因此在第 4 週期執行。X 共需 4 週期。

Y 的 B1、B3 沒有相依，可在第 1 週期同時執行。B2 與 B1 有功能單元衝突，排在第 2 週期；B4 依賴 B2，排在第 3 週期。Y 共需 3 週期。