112 年 國立成功大學電機工程學系碩士班已組《計算機組織與作業系統》

核心觀念

本題考查作業系統的核心安全保護機制——雙重模式運作（Dual-Mode Operation）與特權指令（Privileged Instruction）。

1. 雙重模式運作（Dual-Mode Operation）：
   作業系統藉由硬體的支援（如 CPU 內部的 Mode Bit），將執行環境劃分為：

   • 使用者模式（User Mode）：執行一般使用者應用程式，存取權限受到嚴格限制。
   • 核心模式（Kernel Mode / Supervisor Mode / Monitor Mode / System Mode）：執行作業系統核心（Kernel），具備最高執行權限，可存取所有硬體資源與記憶體空間。

2. 特權指令（Privileged Instruction）：
   若某指令的執行會影響系統安全性、破壞記憶體保護機制、獨佔 CPU 資源或干擾其他處理序（Process），則該指令必須被指定為「特權指令」。特權指令僅允許在核心模式下執行。若使用者模式下的程式試圖執行特權指令，CPU 硬體會立刻觸發硬體例外（Trap / Exception），由作業系統接管並終止該違規程式。

3. 非特權指令（Non-privileged Instruction）：
   不影響系統安全與其他程式運作的指令（如算術運算、讀取系統時間、發出系統呼叫請求等），使用者模式與核心模式皆可安全執行。

---

解題方法

判斷一個指令是否應為特權指令，切入點為安全性與保護性法則：
「若允許使用者程式（User Program）任意執行此指令，是否可能導致系統崩潰、規避安全限制、洩漏他人資料或獨佔系統資源？」

• 是 $\rightarrow$ 必須為特權指令（Privileged Instruction）。
• 否 $\rightarrow$ 為非特權指令（Non-privileged Instruction）。

---

選項分析

• a. Set value of timer.（設定定時器數值）

  • 類別：特權指令。
  • 理由：作業系統依靠定時器（Timer）產生週期性中斷，以實作多元程式（Multiprogramming）與 CPU 時分共享排程（Time-sharing）。若使用者程式能任意修改或重置 Timer，即可將 Timer 設為永不中斷，進而獨佔 CPU 不釋放，導致其他程式與作業系統無法運作。

• b. Read the clock.（讀取時鐘）

  • 類別：非特權指令。
  • 理由：單純讀取系統當前時間（例如取得 Time Stamp）僅為資料的檢視，不會修改任何硬體狀態或核心資料結構，亦不會干擾其他處理序，因此使用者模式下可安全執行。

• c. Clear memory.（清除記憶體）

  • 類別：特權指令。
  • 理由：此處指抹除實體記憶體或系統保護區塊的資料。若允許使用者程式任意執行清除記憶體指令，該程式將可抹除作業系統核心碼（Kernel Code）或其他處理序的記憶體內容，嚴重破壞記憶體保護機制。

• d. Issue a trap instruction.（發出 Trap 指令）

  • 類別：非特權指令。

核心觀念

本題考查作業系統（Operating System）中有關 行程概念（Process Concept） 的基本定義與分類，主要涵蓋以下兩大核心內容：

1. Context Switch（內文切換 / 上下文切換）：CPU 將執行權從一個行程切換至另一個行程時，作業系統必須保存當前行程的狀態（State Save），並載入與恢復目標行程先前保存的狀態（State Restore）。
2. Process Termination（行程終止）：行程完成最後一段指令的執行後，透過呼叫 exit() 系統呼叫請求作業系統將其刪除並釋放記憶體與資源。
3. Android 行程階層（Android Process Hierarchy）：行動作業系統為了記憶體回收與管理所定義的行程優先級階層，包含：
   • Foreground Process（前景行程）
   • Visible Process（可見行程）
   • Service Process（服務行程）
   • Background Process（背景行程）
   • Empty Process（空白行程）

---

解題方法

1. 檢視選項 (a) 與 (b) 是否符合傳統作業系統中對 Context Switch 與 Process Termination 的經典教科書（Silberschatz《Operating System Concepts》）標準定義。
2. 檢視選項 (c) 與 (d) 是否符合行動作業系統對行程狀態與階層（Process Hierarchy）的精準定義，判斷其專有名詞與描述內容是否產生混淆或錯置。

---

選項分析

• (a) 正確

  • 分析：根據作業系統經典定義，當 CPU 核心要從目前運行的行程切換至另一個行程時，作業系統（Dispatcher/Scheduler）必須保存目前行程的上下文狀態（包含 PCB、暫存器內容、Program Counter 等），並恢復目標行程先前保存的狀態。此過程即稱為 Context Switch（上下文切換）。故本選項敘述完全正確。

• (b) 正確

  • 分析：當行程執行完畢其最後一道敘述（Final Statement）時，會主動呼叫 exit() 系統呼叫（System Call），要求作業系統回收其所佔用的資源（如記憶體、開啟的檔案與 I/O 緩衝區）並將其刪除。此為 Process Termination（行程正常終止） 的標準機制與教科書原版定義。故本選項敘述完全正確。

關鍵概念

• DMA 透過 DMA‑request (DRQ) 與 DMA‑acknowledge (DACK) 兩根訊號線完成與裝置控制器的握手。
• Interrupt 為硬體（外部）觸發的異常，Exception 為 CPU 執行指令時產生的內部例外。
• DMA 讓專門的控制器直接搬移資料，減少 CPU 參與，提高 I/O 同時性與效能。
• Non‑blocking 系統呼叫在返回時不會將呼叫執行緒阻塞，也不會將其從 run queue 移至 wait queue，執行緒仍保持可排程狀態。

核心觀念

本題考查計算機架構中**管線冒險（Pipeline Hazards）**的類型及其對應的硬體解決策略。管線冒險是指阻止下一條指令在下一個時脈週期順利執行的情況，主要分為三大類：

1. 結構冒險（Structural Hazard）：硬體資源不足或衝突，導致多個指令在同一週期搶用同一資源。
2. 資料冒險（Data Hazard）：後續指令需要用到先前指令尚未寫回的資料（如 RAW, Read-After-Write）。
3. 控制冒險（Control Hazard）：分支指令（Branch / Jump）結果尚未確定前，管線無法確定下一條應擷取的指令位址。

---

解題方法

針對 RISC-V 5 階經典管線（IF, ID, EX, MEM, WB）設計，檢視各項優化機制對應解決的冒險類型：

1. 分析 Harvard 架構（獨立的指令與資料記憶體）對記憶體存取衝突的影響。
2. 分析固定管線級數（Fixed Pipeline Stages）對資源調度的規範作用。
3. 區分「雙半週期暫存器存取」與「分支計算前移」各自解決何種冒險，以及計算硬體放置的正確階段。

---

選項分析

• (a) 錯誤
  當架構採用分離的指令記憶體（Instruction Memory / I-Cache）與資料記憶體（Data Memory / D-Cache）時，IF 階段僅讀取指令記憶體，MEM 階段僅存取資料記憶體。由於兩者硬體結構獨立，在同一時脈週期內同時執行指令擷取與資料寫入不會發生資源衝突，因此不會產生結構冒險。

• (b) 正確
  在 RISC-V 5 階管線設計中，強制使所有指令擁有相同的管線級數（即使不需要記憶體存取的 R-type 指令，也會在 MEM 階段停留一個週期），可確保每條指令到達特定硬體資源（如 WB 階段的暫存器寫入埠）的時間順序完全定時且可預測，從而避免因指令長短不一導致的寫入埠搶用衝突（結構冒險）。

核心觀念

虛擬記憶體（Virtual Memory, VM）為現代作業系統與計算機結構中的核心機制，主要提供三大功能：

1. 擴充記憶體空間的錯覺：將主記憶體（Main Memory, DRAM）當作次級儲存裝置（Secondary Storage, 如 SSD/HDD）的快取（Cache），讓應用程式可以使用比實際實體記憶體（Physical Memory）更大的位址空間。
2. 保護與隔離機制：透過記憶體管理單元（MMU）與頁表（Page Table）中的權限位元（如 Read/Write/Execute、User/Supervisor 模式），確保各進程（Process/Task）之間的記憶體空間相互獨立且受保護，防止非法存取。
3. 記憶體共享與動態配置：不同進程可透過各自的頁表將虛擬位址對映到相同的實體頁框（Physical Frame），實現安全的共享記憶體（Shared Memory）。

重要名詞與觀念辨析：

• TLB Miss vs. Page Fault：
  • TLB Miss：虛擬位址轉換條目不在快取轉換後援緩衝區（TLB）中，需至主記憶體進行頁表搜尋（Page Table Walk）。
  • Page Fault（缺頁中斷）：頁表條目中的 Valid Bit 為 $0$，表示目標頁面目前不在主記憶體（DRAM）中，需發起 Disk I/O 從次級儲存裝置載入頁面。
• 管理層級：虛擬記憶體是由**作業系統（OS 軟體）與記憶體管理單元（MMU 硬體）**共同管理；而 CPU Cache（如 L1/L2/L3 Cache）則完全由硬體自動管理。

---

解題方法

本題考查虛擬記憶體的運作原理、軟硬體分工、位址空間大小關係、TLB 與 Page Fault 的本質差異，以及 MMU 的保護機制。解題切入點為審視各選項敘述是否符合標準計算機組織與作業系統學理規範，逐一分析其正確性。

---

選項分析

• (a) 錯誤

  • 選項原文：Virtual memory uses main memory as a "cache" for secondary storage, which is usually managed by DRAM hardware.
  • 詳細說明：虛擬記憶體確實將主記憶體視為次級儲存裝置的快取；然而虛擬記憶體的管理與位址對映（如頁面替換、Page Fault 處理、頁表維護）是由**作業系統（OS 軟體）**主導，並配合 CPU 內部的 MMU（硬體） 輔助完成，並非由「DRAM 硬體」獨立管理。完全由純硬體管理的快取是 CPU 快取記憶體（SRAM-based Cache）。

• (b) 錯誤

  • 選項原文：Generally, virtual address space is smaller or equal to physical address space.

核心觀念

本題考查快取記憶體（Cache Memory）的**失誤分類模型（3Cs Model）**及其改善策略，包含以下核心定義與定理：

1. 快取失誤的三 C 模型（3Cs of Cache Misses）：

   • 強制失誤（Compulsory Miss / Cold-Start Miss）：首次存取某個未曾載入快取的記憶體區塊（Block）時必然發生的失誤。
   • 容量失誤（Capacity Miss）：當程式執行期間存取的區塊總量超過快取總容量時，即便採用全相聯對映也無法避免的失誤。
   • 衝突失誤（Conflict Miss / Collision Miss）：在直接對映（Direct Mapped）或組相聯對映（Set Associative）結構中，多個記憶體區塊競爭對映至同一快取組（Set）所造成的失誤。

2. 對映架構（Mapping Schemes）與衝突失誤之關係：

   • 直接對映快取（Direct Mapped Cache）：每個記憶體區塊僅能放置於唯一的快取行（Line），組競爭最嚴重，衝突失誤頻率最高。
   • 全相聯快取（Fully Associative Cache）：記憶體區塊可自由放置於快取中的任意空閒位置，完全消除了位置競爭限制，因此衝突失誤數量為零（$\text{Conflict Misses} = 0$）。

3. 降低強制失誤的機制：

   • 增大區塊大小（Block Size）：利用空間局部性（Spatial Locality），單次讀取連續位址資料，可減少對後續鄰近位址首次存取時的強制失誤。
   • 硬體與軟體預取（Hardware / Software Prefetching）：在 CPU 正式發出資料請求前，提早將資料預載至快取中。

---

解題方法

本題針對快取失誤觀念進行真偽判斷。解題切入點為依據 3Cs 模型在各種相聯度（Associativity）快取結構下的行為進行驗證：

1. 分析不同對映方式對衝突失誤（Conflict Miss）的發生機率。
2. 檢驗強制失誤（Compulsory Miss）是否普遍存在於所有快取架構。
3. 評估微處理器架構中降低強制失誤的可行手段。
4. 計算極限相聯度（Fully Associative）下的衝突失誤數值。

---

選項分析

核心觀念

本題旨在考驗計算機效能評估（Performance Assessment）的核心公式——CPU 執行時間方程式（CPU Performance Equation）。

執行一段程式所需的 CPU 執行時間（CPU Execution Time，$T_{\text{exec}}$）由三個基本要素決定：

1. 指令總數（Instruction Count, $IC$）：程式所執行指令的總數量。
2. 每指令平均時脈週期數（Cycles Per Instruction, $\text{CPI}$）：執行單一指令平均所需的時脈週期數。
3. 時脈頻率（Clock Rate, $f$）：處理器每秒產生的時脈週期數（時脈週期時間 $T_c = \frac{1}{f}$）。

計算程式執行所需的總時脈週期數（Total Clock Cycles, $C$）公式為：
$C = \sum_{i=1}^{n} (IC_i \times \text{CPI}_i)$

其中 $IC_i$ 與 $\text{CPI}_i$ 分別代表第 $i$ 種指令類別的指令數量與其相對應的 CPI。

CPU 總執行時間公式為：
$\text{CPU Execution Time} = \frac{\text{Total Clock Cycles}}{\text{Clock Rate}} = \frac{C}{f}$

---

解題方法

(a) 計算改善前的程式總執行時間

1. 計算各類指令改善前的總時脈週期數：

   • FP 指令：$C_{\text{FP}} = 70 \times 10^6 \times 1 = 70 \times 10^6 \text{ cycles}$
   • INT 指令：$C_{\text{INT}} = 90 \times 10^6 \times 1 = 90 \times 10^6 \text{ cycles}$
   • L/S 指令：$C_{\text{L/S}} = 50 \times 10^6 \times 4 = 200 \times 10^6 \text{ cycles}$
   • Branch 指令：$C_{\text{Branch}} = 8 \times 10^6 \times 2 = 16 \times 10^6 \text{ cycles}$

2. 累加求得改善前的總時脈週期數 ($C_{\text{before}}$)：
   $C_{\text{before}} = (70 + 90 + 200 + 16) \times 10^6 = 376 \times 10^6 \text{ cycles}$

3. 計算改善前的總執行時間 ($T_{\text{before}}$)：
   已知時脈頻率 $f = 2.0 \text{ GHz} = 2.0 \times 10^9 \text{ Hz}$：
   $T_{\text{before}} = \frac{C_{\text{before}}}{f} = \frac{376 \times 10^6}{2.0 \times 10^9} = \frac{376}{2000} = 0.188 \text{ 秒}$

---

(b) 計算改善後的程式總執行時間

1. 計算各類指令改善後的 CPI ($\text{CPI}_{\text{new}}$)：

   • FP 指令：$\text{CPI}_{\text{FP, new}} = 1 \times (1 - 0.50) = 0.5$
   • INT 指令：$\text{CPI}_{\text{INT, new}} = 1 \times (1 - 0.50) = 0.5$
   • L/S 指令：$\text{CPI}_{\text{L/S, new}} = 4 \times (1 - 0.10) = 3.6$
   • Branch 指令：$\text{CPI}_{\text{Branch, new}} = 2 \times (1 - 0.10) = 1.8$

2. 計算各類指令改善後的總時脈週期數：

   • FP 指令：$C_{\text{FP, new}} = 70 \times 10^6 \times 0.5 = 35 \times 10^6 \text{ cycles}$

核心觀念

本題考查**記憶體階層結構（Memory Hierarchy）與有效存取時間（Effective Access Time, EAT / Average Memory Access Time, AMAT）**的計算。

在結合快取記憶體（Cache）、主記憶體（RAM）與分頁機制（Virtual Memory / Disk）的系統中，平均存取時間由各階層的存取時間及其條件命中率（Hit Rate）決定的期望值所構成。

關鍵定義與公式如下：

1. 時間單位統一：
   • 快取存取時間 $T_c = 2 \text{ ns}$
   • 主記憶體存取時間 $T_m = 10 \text{ ns}$
   • 磁碟存取時間 $T_d = 10 \text{ ms} = 10 \times 10^6 \text{ ns} = 10,000,000 \text{ ns}$
2. 事件與條件機率：
   • 快取命中率 $H_c = 10\% = 0.1$
   • 快取未命中率 $1 - H_c = 90\% = 0.9$
   • 快取未命中後的主記憶體命中率 $H_m = 99\% = 0.99$
   • 分頁失敗率（Page Fault Rate，即主記憶體未命中率）$1 - H_m = 1\% = 0.01$
3. 平均存取時間公式（標準階層累加模型）：
   $\text{AMAT} = T_c + (1 - H_c) \times \left[ T_m + (1 - H_m) \times T_d \right]$

---

解題方法

步驟一：分析各路徑之發生機率

CPU 發起記憶體存取請求時，可能發生的三種互斥情況及其全域機率如下：

1. 情況 1：快取命中（Cache Hit）
   $P_1 = H_c = 0.1$
2. 情況 2：快取未命中，但主記憶體命中（Cache Miss & RAM Hit）
   $P_2 = (1 - H_c) \times H_m = 0.9 \times 0.99 = 0.891$
3. 情況 3：快取與主記憶體皆未命中，觸發分頁失敗並存取磁碟（Cache Miss & RAM Miss / Page Fault）
   $P_3 = (1 - H_c) \times (1 - H_m) = 0.9 \times 0.01 = 0.009$

驗證機率和：$P_1 + P_2 + P_3 = 0.1 + 0.891 + 0.009 = 1.000$。

---

步驟二：計算各路徑之存取開銷並推導平均時間

1. 標準累加模型（Sequential Memory Access）

CPU 存取時先檢查快取（耗時 $T_c$）；若未命中再讀取 RAM（額外耗時 $T_m$）；若發生 Page Fault 則再讀取 Disk（額外耗時 $T_d$）：

• 情況 1 耗時：$T_c = 2 \text{ ns}$
• 情況 2 耗時：$T_c + T_m = 2 + 10 = 12 \text{ ns}$
• 情況 3 耗時：$T_c + T_m + T_d = 2 + 10 + 10,000,000 = 10,000,012 \text{ ns}$

將機率與對應開銷相乘加總：
$\text{AMAT} = P_1 \times T_c + P_2 \times (T_c + T_m) + P_3 \times (T_c + T_m + T_d)$
$\text{AMAT} = 0.1 \times 2 + 0.891 \times 12 + 0.009 \times 10,000,012$
$\text{AMAT} = 0.2 + 10.692 + 90,000.108 = 90,011 \text{ ns}$

轉換單位：
$90,011 \text{ ns} = 90.011 \text{ }\mu\text{s} = 0.090011 \text{ ms}$

---

核心觀念

本題考查作業系統中的死結與飢餓。死結是多個程序因競爭資源而互相等待；飢餓則是某個程序長期得不到資源或處理器使用權。

解題方法

先用「程序在等什麼、等待是否形成循環、系統是否仍有進展」來界定死結，再列出死結發生所必須同時成立的四個條件，最後比較死結與飢餓的影響範圍及成因。

死結定義與四個必要條件

**死結（deadlock）**是指一組程序各自持有部分資源，並等待只能由這組程序中其他程序釋放的資源；因此每個程序都無法繼續執行，也無法釋放已持有的資源，形成無限等待。

死結發生必須同時具備以下四個必要條件：

1. 互斥（mutual exclusion）：至少有一項資源一次只能由一個程序使用；其他程序要使用時，必須等待。
2. 持有並等待（hold and wait）：程序已持有至少一項資源，同時又等待取得其他資源。
3. 不可搶先（no preemption）：資源不能由系統強行從持有者手中取走，只能由持有者自願釋放。
4. 循環等待（circular wait）：存在一串程序 $P_1, P_2, \ldots, P_n$，使得 $P_1$ 等待 $P_2$ 持有的資源、$P_2$ 等待 $P_3$ 持有的資源，依此類推，最後 $P_n$ 等待 $P_1$ 持有的資源。

核心觀念

本題考驗電腦架構（Computer Architecture）中**動態分支預測（Dynamic Branch Prediction）**機制，特別是 2-bit 動態分支預測器（2-bit Dynamic Predictor / 2-bit Branch History Table） 的狀態轉移原理與在巢狀迴圈（Nested Loops）結構下的控制行為。

1. 分支預測的目的：在流水線（Pipeline）處理器中，提前預測條件分支指令是否成立（Taken 或 Not Taken），以減少因控制冒險（Control Hazard）導致的流水線停頓（Pipeline Stall）與沖刷（Pipeline Flush）。
2. 1-bit vs. 2-bit 預測器：
   • 1-bit 預測器：只要發生一次預測錯誤（Misprediction）就會立即翻轉預測方向。在雙層巢狀迴圈中，每次跳出內層迴圈會猜錯一次；下次重新進入內層迴圈的第一個迭代時，又會因為前一次紀錄為 Not Taken 而再次猜錯（每次迴圈共猜錯 2 次）。
   • 2-bit 預測器：具備「遲滯現象（Hysteresis）」，規定必須連續猜錯兩次才會改變預測方向（Predict Taken $\leftrightarrow$ Predict Not Taken）。在迴圈結構中，能將每次迴圈執行的預測錯誤降低至僅有跳出迴圈時的 1 次。
3. 2-bit 預測器的四個狀態：
   • $11$ (Strongly Taken)：預測 Taken
   • $10$ (Weakly Taken)：預測 Taken
   • $01$ (Weakly Not Taken)：預測 Not Taken
   • $00$ (Strongly Not Taken)：預測 Not Taken

---

解題方法

(a) 繪製 2-bit Dynamic Predictor 之預測架構圖（Prediction Scheme）

2-bit 動態分支預測器可表示為四狀態有限狀態機（Finite State Machine, FSM）。圖中需清楚標示四個狀態、各自的預測輸出（Predict Taken / Predict Not Taken），以及分支實際結果為 Taken (T) 或 Not Taken (NT) 時的狀態轉移方向。

                  Branch Taken (T)
                ┌──────────────────┐
                │                  │
                ▼                  │
        ┌──────────────┐     ┌──────────────┐
        │Strongly Taken│────►│ Weakly Taken │
        │     (11)     │     │     (10)     │
        │ Predict: T   │◄────│ Predict: T   │
        └──────────────┘     └──────────────┘
               │    ▲               │
Branch Not     │    │ Branch        │ Branch Not
Taken (NT)     │    │ Taken (T)     │ Taken (NT)
               ▼    │               ▼
        ┌──────────────┐     ┌──────────────┐
        │ Weakly Not   │     │ Strongly Not │
        │  Taken (01)  │────►│  Taken (00)  │
        │ Predict: NT  │◄────│ Predict: NT  │
        └──────────────┘     └──────────────┘
                │                  ▲
                │                  │
                └──────────────────┘
                  Branch Not Taken (NT)

狀態轉換邏輯詳細說明：

• Strongly Taken (11)：預測 Taken。若實際結果為 T，維持 $11$；若實際結果為 NT，轉移至 $10$（仍預測 T）。
• Weakly Taken (10)：預測 Taken。若實際結果為 T，轉移至 $11$；若實際結果為 NT，轉移至 $00$（預測轉為 NT）。
• Strongly Not Taken (00)：預測 Not Taken。若實際結果為 NT，維持 $00$；若實際結果為 T，轉移至 $01$（仍預測 NT）。
• Weakly Not Taken (01)：預測 Not Taken。若實際結果為 NT，轉移至 $00$；若實際結果為 T，轉移至 $11$（預測轉為 T）。

---

(b) 說明 Misprediction 發生的時機（When）與原因（Why）

給定之程式碼結構為雙層巢狀迴圈：