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

核心觀念

本題考查 $n$-way set associative cache 的組織方式，以及 32 位元記憶體位址如何分成：

1. Block offset：定位 cache line 內的位元組。
2. Set index：定位資料所在的 set。
3. Tag：辨識該 set 中的哪一個 cache line。

題目給定：

• Cache 容量：$32\text{ KB}$
• Cache line 大小：$32\text{ bytes}$
• Associativity：$4$-way
• Cacheable address space：$4\text{ GB}$

假設記憶體採用位元組定址，則 $4\text{ GB}=2^{32}$ bytes，因此記憶體位址為 32 位元。

---

解題方法

1. 計算 cache line 數量

$$32\text{ KB}=32\times 1024=2^{15}\text{ bytes}$$

每條 cache line 為：

$$32\text{ bytes}=2^5\text{ bytes}$$

因此 cache 總共有：

$$\frac{2^{15}}{2^5}=2^{10}=1024$$

條 cache line。

---

2. 計算 set 數量

4-way set associative 表示每個 set 包含 4 條 cache line，因此 set 數量為：

$$\frac{1024}{4}=256=2^8$$

也可由每個 set 的容量直接計算：

$$4\times 32\text{ bytes}=128\text{ bytes}$$ $$\frac{32\text{ KB}}{128\text{ bytes}} = \frac{2^{15}}{2^7} = 2^8 = 256$$

所以 cache 組織為：

• 256 個 sets
• 每個 set 有 4 條 cache lines
• 總共 1024 條 cache lines

---

位址欄位切割

32 位元記憶體位址可分成：

$$\boxed{\text{Tag}\ |\ \text{Set Index}\ |\ \text{Block Offset}}$$

1. Block offset 位元數

一條 cache line 有 $32=2^5$ bytes，因此需要 5 個位元指定 line 內的位元組位置：

$$\text{Block offset}=5\text{ bits}$$

2. Set index 位元數

共有 $256=2^8$ 個 sets，因此需要 8 個位元選擇 set：

$$\text{Set index}=8\text{ bits}$$

3. Tag 位元數

總位址長度為 32 位元，因此：

$$\text{Tag}=32-8-5=19\text{ bits}$$

---

Cache 位址格式

因此 32 位元位址的格式為：

$$\boxed{ \text{Tag }(19\text{ bits}) \ |\ \text{Set Index }(8\text{ bits}) \ |\ \text{Block Offset }(5\text{ bits}) }$$

對應位元位置如下：

位址欄位	位元位置	位元數
Tag	$31\sim13$	19
Set index	$12\sim5$	8
Block offset	$4\sim0$	5

---

Cache 組織圖

核心觀念

本題考查 MIPS 32 位元單一週期（Single-Cycle）資料通道（Datapath）中，執行載入字組指令 lw rt, offset(rs) 時的訊號傳遞路徑與控制訊號配置。

lw（Load Word）指令屬於 I-type 指令格式：
$\text{OPCODE (6 bits)} \mid \text{rs (5 bits)} \mid \text{rt (5 bits)} \mid \text{immediate/offset (16 bits)}$

執行 lw 指令可分為以下五個階段（Five Stages）：

1. 取指（Instruction Fetch, IF）：根據程式計數器（$\text{PC}$）的值從指令記憶體（Instruction Memory）讀出指令，同時 $\text{PC} \leftarrow \text{PC} + 4$。
2. 解碼／讀取暫存器（Instruction Decode / Register Read, ID）：根據 $rs$ 欄位讀取來源暫存器 1（$\text{Read register 1}$）的值，並將 16-bit 的 $offset$ 進行符號延伸（Sign-Extend）至 32-bit。
3. 執行／算術邏輯單元演算（Execute / ALU, EX）：$\text{ALU}$ 將 $rs$ 的值與符號延伸後的 32-bit $offset$ 相加，計算出目標記憶體的有效位址（Effective Address）。
4. 記憶體存取（Memory Access, MEM）：將 $\text{ALU}$ 計算出的有效位址傳入資料記憶體（Data Memory），讀取該位址的 32-bit 資料。
5. 寫回暫存器（Write Back, WB）：將從資料記憶體讀出的資料寫回目的地暫存器 $rt$（$\text{Write register}$）。

---

解題方法

1. 資料通道圖示（Datapath Diagram）

以下為 MIPS 單一週期架構中，執行 lw rt, offset(rs) 指令時活化的資料通道與關鍵元件連接圖：

核心觀念

本題主要考驗計算機組織與架構中的三大核心主題：

1. 組譯器與連結器的職責分工（Assembler vs. Linker）：控制轉移指令（Branch）中目標位址（Label/Symbol）的解析時間點。當標籤為外部參考（External Reference）時，組譯階段無法確定其記憶體位址，必須延後至連結階段處理。
2. 指令集架構（ISA）比較（MIPS vs. ARM）：
   • MIPS 採用「比較並跳躍（Compare and Branch）」指令，例如 beq r1, r2, L1 直接對兩個暫存器進行比較與條件跳躍。
   • ARM 採用「條件碼暫存器（Condition Code Register / Flags）」機制，透過 cmp r1, r2 指令計算 $r1 - r2$ 並更新狀態旗標（如 $N, Z, C, V$），後續的 beq L1 則根據 CPSR（Current Program Status Register）中的 $Z$ 旗標決定是否跳躍。

---

解題方法

1. 位址解析分析（選項 A、B）：

   • 當程式碼出現跳躍目標 $L_1$ 時，組譯器（Assembler）會嘗試搜尋符號表（Symbol Table）。
   • 若 $L_1$ 定義在別的目標檔案（.o 檔），即稱為外部參考（External Reference）。組譯器無法得知外部檔案編譯後的位址，因此僅會建立重定位紀錄（Relocation Entry），將 $L_1$ 的最終位址計算交由**連結器（Linker）**在將所有 .o 檔合併時補上。

2. 比較指令運作機制分析（選項 C、D）：

   • 檢視 ARM 組合語言 cmp r1, r2 的運算邏輯：其內部實質執行 $r1 - r2$ 的減法運算，但不儲存運算結果至任何通用暫存器（如 $r1$），僅用來設定狀態暫存器中的條件碼旗標（Condition Flags，例如零旗標 $Z=1$ 當 $r1 == r2$）。

核心觀念

本題旨在考驗作業系統（Operating System）中虛擬記憶體（Virtual Memory）、記憶體管理單元（MMU）、極限空間／置換空間（Swap Space）以及行程（Process）與程式（Program）關係的基本概念與定義。

1. 記憶體保護機制（Memory Protection）：
   MMU（Memory Protection Unit / Memory Management Unit）負責將虛擬位址（Virtual Address）轉譯為實體位址（Physical Address）。在轉譯過程中，MMU 會檢查存取權限（如 Read/Write/Execute 權限或 Base/Limit 範圍）。若存取違規，MMU 會硬體觸發 Trap（如 Page Fault 或 Segmentation Fault / Memory Access Violation exception），通知作業系統處理。
2. 極限空間／置換空間（Swap Space）：
   Swap space 是磁碟（Disk）或 SSD 上劃分出的特別區域，用來存放暫時被換出（Swapped out）主記憶體（RAM）的頁面（Pages）或行程資料。它是用來支援虛擬記憶體的極限機制，存放的是當前無法容納於實體 RAM 中的分頁／資料，而非保留全額實體記憶體空間。
3. 程式（Program）與行程（Process）：
   • Program：靜態儲存於磁碟上的可執行檔（Active / Passive entity）。
   • Process：執行中的程式實例（Instance of a program）。同一份程式可以被載入並執行多次，形成多個獨立的行程實例（Instances）。

---

解題方法

本題為觀念選答題（研究所考題常見複選題或單選題形式，需對每一選項進行真偽判斷）。
切入點為精準掌握作業系統專有名詞的定義：

1. 分析硬體（MMU）與作業系統在記憶體保護處理上的分工。
2. 釐清 Swap Space 的功能與使用時機（RAM 空間不足時暫存頁面，而非為全額實體記憶體預留固定空間）。
3. 區分 Program（靜態檔案）與 Process（動態執行實體）的關係。

---

選項分析

• (A) A memory protection violation is raised by the MMU unit. 【正確】
  • 原因：當 CPU 發出虛擬位址時，硬體 MMU 會檢查該存取是否符合保護屬性（如寫入唯讀分頁、執行不可執行的分頁或超越 Limit 暫存器範圍）。

核心觀念

本題旨在考驗計算機架構與作業系統中**輸入／輸出傳輸機制（I/O Data Transfer Techniques）的基本原理，特別是程式控制 I/O（Programmed I/O）與直接記憶體存取（Direct Memory Access, DMA）**的運作機制與角色分工。

1. 程式控制 I/O（Programmed I/O, PIO）：

   • CPU 直接參與資料傳輸的每一個字元或字組（word）。
   • 每一次傳輸皆由 CPU 執行特定指令（如 IN / OUT 或記憶體映射指令 MOV）來完成。
   • CPU 通常需要透過輪詢（Polling）不斷檢查狀態暫存器，直到 I/O 裝置準備就緒，會耗費大量 CPU 週期。

2. 直接記憶體存取（Direct Memory Access, DMA）：

   • 用於高速 I/O 裝置與主記憶體之間的大量資料傳輸，藉此解放 CPU。
   • 傳輸前：由主機 CPU 設定（Program）DMA 控制器的內部暫存器（例如：來源與目的記憶體位址、傳輸位元組數量、控制與狀態指令）。
   • 傳輸中：DMA 控制器作為匯流排主控者（Bus Master），直接掌握匯流排主導權，自行發送記憶體讀寫訊號並完成資料傳輸，不需 CPU 逐字處理。
   • 匯流排介面：DMA 控制器具備雙重介面：
     • Slave 介面：當 CPU 要讀寫 DMA 內部的設定暫存器時，DMA 扮演匯流排從屬者（Bus Slave）。
     • Master 介面：當 DMA 控制器在執行記憶體與裝置間的資料搬移時，DMA 扮演匯流排主控者（Bus Master）。

---

解題方法

分析此題選擇題時，需清楚區分 PIO 與 DMA 的動作主體與互動模式：

• PIO 的核心：CPU 參與每一筆資料交易（Every transaction）。
• DMA 的核心：CPU 僅負責設定（Configuration/Programming），傳輸過程由 DMA 控制器自主（By itself）作為 Bus Master 執行。

根據以上定義，逐一比對各選項敘述的正確性。

---

選項分析

• (A) 正確
  • 敘述內容：Programmed I/O 是一種在 CPU 與週邊裝置間傳輸資料的方法，其中每筆資料傳輸皆由程式中的指令發起，且 CPU 參

核心觀念

本題考驗分頁虛擬記憶體管理（Paging Virtual Memory Management）架構中，硬體快取機制 TLB（Translation Look-aside Buffer，轉譯後備緩衝區） 輔助邏輯位址（Logical Address）轉譯為實體位址（Physical Address）的運作原理與時間開銷分析。

1. 位址結構劃分：
   • 邏輯位址（Logical / Virtual Address）：由頁號 $p$（Page Number） 與頁內偏移量 $d$（Page Offset） 組成。
   • 實體位址（Physical Address）：由框號 $f$（Frame Number） 與頁內偏移量 $d$（Page Offset） 組成。
2. 記憶體存取瓶頸與 TLB 需求：
   • 若僅依賴位於主記憶體（RAM）中的分頁表（Page Table）進行轉譯，每次資料存取皆需經過「查詢分頁表」與「存取實際資料」兩次主記憶體存取（Memory Access Penalty）。
   • TLB 為位於記憶體管理單元（MMU）內部的高速相聯記憶體（Associative Cache），專門用來快取近期使用過的 $(p \rightarrow f)$ 頁號對框號之映射關係。
3. 區域性原理（Locality of Reference）：
   • 依據時間區域性（Temporal Locality）與空間區域性（Spatial Locality），程式近期重複存取相同分頁的機率極高，使小容量 TLB 能達到極高的命中率（Hit Rate $\alpha \approx 90\% \sim 99\%$）。
4. 有效存取時間（Effective Access Time, EAT）：
   $EAT = \alpha \times (\epsilon + t_m) + (1 - \alpha) \times (\epsilon + 2 t_m) = \epsilon + (2 - \alpha) t_m$
   其中 $\alpha$ 為 TLB 命中率，$\epsilon$ 為 TLB 搜尋時間，$t_m$ 為主記憶體存取時間。

---

解題方法

TLB 輔助邏輯位址轉譯至實體位址的完整步驟與處理流程如下：

1. 位址拆解與 TLB 平行搜尋（TLB Lookup）

• CPU 發出邏輯位址，MMU 將其拆解為頁號 $p$ 與偏移量 $d$。
• MMU 將頁號 $p$ 同時送入 TLB 中所有項目的 Tag 進行高速硬體平行比對（Associative Parallel Search）。

2. 情境一：TLB 命中（TLB Hit）

• 判定：在 TLB 中找到與頁號 $p$ 匹配的項目。
• 步驟：
  1. 直接從該 TLB 項目取出預先快取好的實體框號 $f$（Frame Number）。
  2. 將框號 $f$ 與原邏輯位址中的偏移量 $d$ 進行拼接（Concatenation），組成實體位址 $(f, d)$。
  3. CPU 直接持實體位址存取主記憶體中的目標資料。
• 時間代價：僅需 1 次 TLB 搜尋時間 $\epsilon$ 與 1 次主記憶體存取時間 $t_m$。

3. 情境二：TLB 未命中（TLB Miss）

• 判定：TLB 中找不到頁號 $p$ 的映射紀錄。
• 步驟：
  1. 分頁表查詢（Page Table Walk）：MMU 轉為存取位於主記憶體中的分頁表（Page Table），以頁號 $p$ 為索引查詢對應的分頁表項（Page Table Entry, PTE）。
  2. 檢查 Valid/Invalid Bit：
     • 若 Valid Bit = 1（頁面在記憶體中）：
       a. 取出分頁表項中的框號 $f$。
       b. 更新 TLB：將全新的映射關係 $(p, f)$ 載入 TLB 中。若 TLB 已滿，則依替換策略（如 LRU、FIFO）置換出一筆舊項目。
       c. 組合實體位址 $(f, d)$ 並存取主記憶體資料。
     • 若 Valid Bit = 0（Page Fault，分頁錯誤）：
       a. 觸發作業系統的中斷 Trap，進入 Page Fault Handling 流程。

核心觀念

本題旨在考驗考生對作業系統（Operating System）中**虛擬記憶體管理機制（Virtual Memory Management）與記憶體對調策略（Swapping Strategies）**的深度理解。重點包含以下核心觀念與定義：

1. 分頁與對調機制（Paging System with Swapping）：
   • 定義：在傳統結合分頁（Paging）的對調系統中，記憶體管理的搬移與對調單位為整個行程（Entire Process）。
   • 控制者：由**中期排程器（Medium-Term Scheduler / Swapper）**負責管理。在行程執行前或記憶體壓力過高時，將整個行程的所有分頁一次性 Swap In 至記憶體或 Swap Out 至次級儲存裝置（Backing Store / Swap Space）。
2. 請求分頁機制（Demand-Paging System）：
   • 定義：一種結合分頁與懶惰對調器（Lazy Swapper / Pager）的虛擬記憶體技術。頁面只有在**被 CPU 存取/請求（On Demand）**時，才會被載入至實體記憶體中。
   • 控制者：由**分頁器（Pager）與頁面錯誤中斷處理常式（Page Fault Handler）**共同管理。
3. 頁面錯誤（Page Fault）與指令重發（Instruction Restartability）：
   • Demand Paging 依賴硬體 MMU 中的有效/無效位元（Valid/Invalid Bit）檢測。若存取的頁面不在實體記憶體中，會觸發 Page Fault 中斷，由 OS 將該頁面載入後重新執行該條指令。

---

解題方法

解答此題時，應從對調單位（Unit of Transfer）、載入時機（Loading Timing）、**硬體支援需求（Hardware Support）以及系統效能與資源利用率（System Performance & Resource Utilization）**四大核心面向切入對比說明：

1. 搬移單位（Unit of Transfer）與對調器（Swapper vs. Pager）

• Paging System with Swapping：以「行程（Process）」為對調單位。Swapper 負責將整個行程包含的所有 Pages 一次性在主記憶體與磁碟 Swap Space 之間搬移。
• Demand-Paging System：以「單一頁面（Individual Page）」為對調單位。系統使用 Pager（又稱 Lazy Swapper），除非行程執行時明確存取某頁面，否則絕不將該頁面預先載入記憶體。

2. 載入時機與執行條件（Loading Timing & Execution Condition）

• Paging System with Swapping：行程在獲得 CPU 執行權之前，其**整個位址空間（All Pages）**必須已完整存在於實體記憶體中。
• Demand-Paging System：行程可以在記憶體中零頁面或僅有少數頁面的狀態下開始執行（即純粹請求分頁 Pure Demand Paging）。當執行過程中存取到未載入頁面時，才透過 Page Fault 動態載入該頁。

3. 硬體與作業系統機制支援（Hardware & OS Support）

• Paging System with Swapping：只需要基本的分頁硬體（Page Table）與中期排程器支援，不需要 mid-instruction 的 Page Fault 重複執行機制。
• Demand-Paging System：必須獲得以下強大硬體與 OS 支援：
  1. 頁表標誌（Valid/Invalid Bit）：用以標示頁面是否已在實體記憶體中。
  2. Page Fault 中斷機制：當存取 Invalid 頁面時觸發中斷陷阱（Trap）。
  3. 指令重發能力（Instruction Restartability）：CPU 必須能在 Page Fault 處理完成後，精確還原暫存器與狀態並重頭執行該條被中斷的指令。
  4. 對調空間（Swap Space Management）：專門的快速次級儲存區用於頁面讀寫。

4. 多工度與記憶體利用率（Degree of Multiprogramming & Memory Overhead）

• Paging System with Swapping：
  • 受限於實體記憶體總容量，若實體記憶體不足以放下整個行程，該行程便無法執行。
  • 多工度（Degree of Multiprogramming）較低。
  • 對調時需要大量的 I/O 時間傳輸整個行程的記憶體影像，Context Switch 成本高。
• Demand-Paging System：

核心觀念

本題考查作業系統（Operating System, OS）的基本架構與 系統呼叫（System Calls） 的定義。

• 系統呼叫（System Call）：為作業系統核心（Kernel）提供給應用程式（User Programs）使用其各種服務（例如檔案存取、行程控制、裝置管理、網路通訊等）的程式化介面（Programming Interface）。應用程式通常不能直接存取硬體或受保護的系統資源，必須透過系統呼叫從使用者模式（User Mode）切換至核心模式（Kernel Mode）來執行特權指令。

---

解題方法

本題為觀念檢索題。解題切入點在於識別「介面（Interface）」與「提供 OS 服務（services provided by an OS）」關鍵字的組合：

1. 觀察題幹關鍵字：「provide(s) an interface to the services provided by an operating system」。
2. 對照 OS 標準教科書（如 Silberschatz 的 Operating System Concepts）定義：System calls provide an interface to the services made available by an operating system.
3. 比對選項，即可確定正確答案。

---

選項分析

• (A) Shared memory（共享記憶體）
  • 錯誤。

核心觀念

本題考查**行動裝置作業系統（Mobile Operating System）**的基礎概念與常見產品歸屬。

• iOS：由 Apple 公司開發，專為其行動裝置（iPhone、iPod touch，以及早期的 iPad）設計的專屬行動作業系统。

---

解題方法

本題為基礎觀念檢視題。題目詢問「哪一個是專為 iPhone 與 iPad 設計的行動作業系統」。
解題切入點在於區分桌面作業系統（Desktop OS）與行動作業系統（Mobile OS），以及識別各作業系統對應的開發廠商與適用裝置平台。

---

選項分析

• (A) Mac OS X：錯誤。
  Mac OS X（現稱為 macOS）是 Apple 公司專為 Mac 系列個人電腦（如 MacBook、iMac 等）開發的桌面作業系統，並非專為 iPhone/iPad 設計的行動作業系統。
• (B) Android：錯誤。

核心觀念

本題考查作業系統（Operating System）中的**處理器排程與行程狀態轉移（Process State Transition & CPU Scheduling）**機制。當一個正在 CPU 上執行的行程（Running Process）被迫離開 CPU（即釋放 CPU 的控制權，導致 Context Switch）時，通常發生在以下幾種情境：

1. 主動放棄（Voluntary）：行程主動要求等待某項事件，例如提出 I/O 請求（I/O Request） 或等待子行程結束（wait()），此時行程會從 Running 狀態轉移至 Waiting (Blocked) 狀態。
2. 被動剝奪（Involuntary）：作業系統透過硬體中斷介入（例如時間中斷 / 時間片用盡 Time Slice Expired 或外設中斷 Interrupt），強制剝奪目前行程的 CPU 使用權，將其轉移回 Ready 狀態。
3. 建立新行程（Fork a child）：行程呼叫 fork() 系統呼叫建立子行程時，作業系統會執行系統呼叫處理程序，並觸發 CPU 排程器（Scheduler）來決定繼續執行父行程、執行新建立的子行程，或是切換至其他高優先權行程。在多數排程原則（如 Preemptive Scheduling）或子行程優先執行的實現中，父行程會被移出 CPU。

---

解題方法

分析題目問題：「Which of the following cases could force a process removed from the CPU?」（下列何者情況會使一個行程被迫/被移出 CPU？）

我們需要檢視每一個事件是否會引發行程狀態的切換（從 Running 轉移至 Waiting、Ready 或被 Swapped out）：

• 引發系統呼叫（System Call）或中斷（Interrupt）的事件，都會促使作業系統的 Kernel/Scheduler 接管 CPU 控制權。
• 一旦 Scheduler 接管控制權，正在執行的行程就有可能（could）被暫停並移出 CPU。

---

選項分析

核心觀念

本題考查作業系統（Operating System, OS）中 上下文切換（Context Switch） 與 程序控制區塊（Process Control Block, PCB） 的基本運作機制。

1. Context Switch（上下文切換）：當 CPU 從執行一個程序（Process）切換到執行另一個程序時，作業系統必須先將當前程序的狀態（包含暫存器內容、程式計數器 PC、堆疊指標 SP 等）儲存起來，並載入下一個即將執行程序的狀態。
2. Process Control Block (PCB)：作業系統在核心空間（Kernel Space）為每個程序維護的資料結構，用以記錄該程序的所有執行狀態與相關資訊。程序 $P_0$ 對應 $PCB_0$，$P_1$ 對應 $PCB_1$。

---

解題方法

當作業系統執行 CPU 擺渡／切換（從程序 $P_0$ 切換至程序 $P_1$）時，標準步驟如下：

1. 保存舊狀態：將當前正在執行的程序 $P_0$ 之上下文（CPU registers, PC, flags 等）保存至屬於 $P_0$ 的資料結構，即 $PCB_0$ 中。
2. 更新程序狀態：將 $P_0$ 的狀態改為 Ready 或 Blocked。
3. 載入新狀態：從目標程序 $P_1$ 的資料結構 $PCB_1$ 中，恢復／載入 $P_1$ 上次被中斷時所保存的上下文資訊。

第 8-(5) 題詳解

核心觀念

本題考查作業系統中 Producer-Consumer Problem（生產者-消費者問題） 在共享記憶體（Shared Memory）架構下，利用 Circular Array（環形陣列/環形緩衝區） 實作時的指標控制與判斷條件。

在以長度為 BUFFER_SIZE 的環形陣列實作緩衝區時：

• in 變數指向下一個可寫入資料的空位置。
• out 變數指向第一個可讀取資料的有效位置。
• 為了區分「緩衝區全空（Buffer Empty）」與「緩衝區全滿（Buffer Full）」，若不另外使用計數器（counter），標準實作通常會犧牲（浪費）一個陣列空間。
  • 緩衝區全空條件：$\text{in} == \text{out}$
  • 緩衝區全滿條件：$(\text{in} + 1) \mathbin{\%} \text{BUFFER\_SIZE} == \text{out}$

---

解題方法

1. 空間使用效率分析：
   若陣列容量為 $N$（即 BUFFER_SIZE = $N$），在不使用第三方計數變數的情況下：

   • 當陣列內有 $0$ 個元素時：$\text{in} == \text{out}$。
   • 若允許存放 $N$ 個元素，當陣列填滿時，in 繞了一圈又追上 out，此時也會滿足 $\text{in} == \text{out}$。
   • 這會導致程式無法單憑 $\text{in}$ 與 $\text{out}$ 的相對關係區分是「全空」還是「全滿」。
   • 因此，經典做法是最多只允許存放 $N - 1$ 個元素。當還剩最後一個空位時（即 $\text{in}$ 的下一個位置就是 $\text{out}$），就判定為「全滿」。

2. 邏輯條件判斷：

   • 全空（Empty）：當生產者與消費者指標重合（即 $\text{in} == \text{out}$）時，表示緩衝區內沒有任何可讀取的資料。

核心觀念

本題主要考查作業系統（Operating System）中**多執行緒伺服器架構（Multithreaded Server Architecture）與執行緒池（Thread Pool）**的運作機制。

在經典的 Web Server 或資料庫伺服器設計中，面對來自客戶端（Client）的新請求（New Request），伺服器主要有兩種服務模式：

1. Thread-per-request 模式：為每一個新到的請求動態建立一個全新的執行緒（Newly created thread）來處理，處理完畢後銷毀該執行緒。
2. Thread Pool（執行緒池）模式：伺服器啟動時預先建立一群執行緒，當新請求到達時，直接從執行緒池中選取一個**預先建立且處於閒置狀態的執行緒（Pre-created thread）**來服務該請求，而非現建立一個全新的執行緒。

在作業系統的標準教材（如 Silberschatz 所著之 Operating System Concepts）中，提及 Multithreaded Server 處理請求的標準流程與引進 Thread Pool 的原因時，特別強調：「當請求到達時，若使用傳統多執行緒架構，會建立一個新的執行緒（a newly created thread）；但若考量建立執行緒的開銷與系統資源限制，通常會採用 Thread Pool 模式。」

然而，針對本題選項敘述分析：

• 選項 (A) a new created thread 指的是「新建立的執行緒」。
• 選項 (B) a new created process 指的是「新建立的行程」（此為多行程伺服器如早期 Unix fork() 的做法，開銷極大，非 multithreaded architecture）。
• 選項 (C) the same process for prior users 指的是「先前使用者所使用的同一個行程」（行程是資源分配單位，並非直接用來 execute / service 請求的執行單位）。

若在沒有特別指定使用 Thread Pool 技術的標準 Multithreaded Server 模型下，伺服器監聽主執行緒（Master/Listener Thread）接收到新請求後，會產生一個全新的執行緒（Newly created thread）來獨立處理該請求。

---

解題方法

1. 區分 Process 與 Thread 的層級：
   • 行程（Process）是資源分配的基本單位（包含獨立的 Address Space、File Descriptors 等）。
   • 執行緒（Thread）是 CPU 排程與執行的基本單位（共享所屬 Process 的資源，但擁有獨立的 Register set 與 Stack）。
2. 分析 Multithreaded Server 運作流程：

核心觀念

本題考查作業系統中 多線程模型（Multithreading Models） 與 多對多 / 雙層模型（Many-to-Many / Two-Level Model） 下的線程管理機制——排程器啟用（Scheduler Activations） 與 上呼（Upcall） 機制。

在多對多模型或雙層模型中，使用者層級線程（User Thread）與核心層級線程（Kernel Thread）之間需要溝通協調機制，以處理阻塞型系統呼叫（Blocking System Calls）或頁面錯誤（Page Fault）等事件：

• Upcall（上呼）：核心（Kernel）向應用程式（使用者空間的排程器/線程庫）發出通知，告知特定事件的發生。
• Upcall Handler（上呼處理常式）：應用程式在使用者空間中處理該通知的函式。
• LWP (Lightweight Process)：核心與使用者空間線程庫之間進行溝通的中介資料結構（虛擬處理器）。

---

解題方法

1. 分析題目關鍵字：
   • In multithreaded programs（在多線程程式中）
   • the kernel informs an application about certain events（核心通知應用程式特定事件的發生）
   • using a procedure known as a(n) ____（透過稱為 ____ 的程序）
2. 檢索經典教科書（Silberschatz - Operating System Concepts）定義：
   根據 Silberschatz 系統概念教材，在討論 Scheduler Activations 時明確定義：

   "The kernel provides the application with a set of virtual processors (LWPs), and the application can schedule user threads onto an available virtual processor... The kernel must inform an application about certain events. This procedure is known as an upcall."

3. 對照選項與專有名詞定義：

核心觀念

本題考查作業系統（Operating System）中 CPU 排程演算法（CPU Scheduling Algorithms）的特性與缺點，特別是 先到先服務排程（First-Come, First-Served Scheduling, FCFS） 所導致的 護衛效應（Convoy Effect）。

• FCFS 排程演算法：採用先到先處理（Non-preemptive）原則，依據行程到達準備佇列（Ready Queue）的先後順序分配 CPU 時間。
• Convoy Effect（護衛效應）：當一個需執行長時間 CPU Burst（CPU 密集型/CPU-bound）的行程佔用 CPU 時，後續許多短 CPU Burst（I/O 密集型/I/O-bound）的行程都會被迫在其後方等待。這會導致 CPU 與各個 I/O 裝置的利用率顯著下降，整體系統吞吐量與平均等待時間嚴重惡化。

---

解題方法

本題為觀念定義題，解題切入點如下：

1. 分析題幹所述的情境：「當一個具有長 CPU burst 的行程佔據 CPU 時，在 FCFS 排程中會發生什麼現象（The ____ occurs in first-come-first-served scheduling when a process with a long CPU burst occupies the CPU）」。
2. 對照作業系統中排程相關名詞定義：CPU-bound 行程卡住 CPU 導致眾多 Short I/O-bound 行程等待的現象，專有名詞即為 Convoy Effect。
3. 逐一比對各選項的名詞定義以確保答案無誤。

---

選項分析

• (A) 錯誤：Dispatch Latency（分派延遲時間）
  分派延遲時間是指分派器（Dispatcher）停止當前正在執行的行程，並將 CPU 權限切換給另一個已選定的行程（即上下文切換 Context Switch）所耗費的時間。

核心觀念
本題考驗實時作業系統（Real-Time Operating System, RTOS）中的週期性任務排程演算法（Periodic Task Scheduling Algorithms）及其排程機制屬性。
在實時排程中，搶佔式排程（Preemptive Scheduling）指的是：當一個具有更高優先級（Priority）的任務準備就緒（Ready）時，系統能立即暫停目前正在執行的低優先級任務，將 CPU 執行權交給該高優先級任務。

1. Rate-Monotonic (RM) Scheduling：

   • 屬於**靜態優先級（Static Priority）**排程演算法。
   • 優先級根據任務的週期（Period, $T_i$）長短來決定：週期越短，優先級越高。
   • 由於優先級在執行前即確定且不變，當週期較短的高優先級任務抵達時，系統會搶佔（Preempt）正在執行的低優先級任務。因此 RM 屬於 Preemptive 排程。

2. Earliest-Deadline-First (EDF) Scheduling：

   • 屬於**動態優先級（Dynamic Priority）**排程演算法。
   • 優先級根據任務距離截止時間（Deadline, $D_i$）的近遠來決定：截止時間越近（Earliest Deadline），優先級越高。
   • 當新抵達任務的截止時間比當前正在執行的任務更早時，系統會立即搶佔目前執行的任務。因此 EDF 也屬於 Preemptive 排程。

---

解題方法
分析實時排程演算法的運作機制，對照 Rate-Monotonic (RM) 與 Earliest-Deadline-First (EDF) 的基本定義：

1. 檢驗 RM 是否具備 Preemptive 特性：RM 演算法在標準定義中即為 Preemptive 靜態優先級排程（若有更短週期任務抵達，立即觸發搶佔）。
2. 檢驗 EDF 是否具備 Preemptive 特性：EDF 演算法在標準定義中即為 Preemptive 動態優先級排程（若有更早截止時間的任務抵達，立即觸發搶佔）。

核心觀念

本題考查作業系統（Operating System）中**臨界區段問題（Critical-Section Problem）**的三大必要條件定義及其之間的邏輯推導關係。

根據 Abraham Silberschatz 所著之《Operating System Concepts》（恐龍書），為解決臨界區段問題，一項合格的同步機制（Synchronization Mechanism）必須滿足以下三個條件：

1. 互斥（Mutual Exclusion）：若已有進程在臨界區段中執行，則其他進程不得進入其臨界區段。
2. 進展（Progress）：當沒有進程在臨界區段中執行，且有進程想要進入臨界區段時，只有那些「不在剩餘區段（Remainder Section）執行的進程」可以參與決定下一個誰進入臨界區段，且此決定不可被無限期推遲（Cannot be postponed indefinitely）。
   • 關鍵推論：Progress 保證了系統整體不會發生死鎖（Deadlock）。若滿足 Progress，系統中至少會有一位進程能進入臨界區段繼續執行，故 Progress $\implies$ No Deadlock（不發生死鎖）。
3. 有限等待（Bounded Waiting）：在一個進程提出進入臨界區段的請求後，到該請求獲得允許之前，其他進程被允許進入其臨界區段的次數必須是有上限的（Bounded）。
   • 關鍵推論：Bounded Waiting 保證了個別進程不會遭受飢餓（Starvation）。但是，單純保證 Bounded Waiting 並不代表系統整體不會死鎖，例如：若所有進程都相互等待且完全無法進入臨界區段（死鎖狀態），進程進入臨界區段的次數上限為 $0$，此時符合 Bounded Waiting 的定義（次數受到上限約束），但系統卻陷入死鎖（無 Progress）。

因此，三大條件與系統狀態之間的邏輯關係可歸納為：
$\text{Bounded Waiting} \implies \text{No Starvation}$
$\text{Progress} \implies \text{No Deadlock}$

---

解題方法

根據上述的核心觀念與定義進行邏輯推導：

1. 檢驗「Progress $\implies$ No Deadlock」：

   • 證明：Progress 要求「下一個進入臨界區段的決定不能被無限期推遲」。這意味著只要有進程想進臨界區段，系統就一定能在有限時間內選出一個進程進入，因此不會出現所有進程相互卡死、大家都無法推進的死鎖狀態。
   • 結論：Progress 蘊含（Implies）No Deadlock。

2. 檢驗「No Deadlock $\implies$ Bounded Waiting」：

   • 反例驗證：無死鎖（No Deadlock）僅保證「系統整體持續有進程能進入臨界區段」，但無法保證「特定進程不會被無限期忽略」。例如：在嚴格優先權（Strict Priority）調度下，高優先權進程可以不斷搶先進入臨界區段，系統整體運作正常（No Deadlock），但低優先權進程可能永遠等不到（發生 Starvation，違反 Bounded Waiting）。
   • 結論：No Deadlock 無法蘊含 Bounded Waiting。

3. 檢驗「Bounded Waiting $\implies$ Progress / No Deadlock」：

   • 反例驗證：若一個系統設計讓所有進程進入臨界區段的允許次數限制為 $0$ 次（即大家都進不去），此時「其他進程進入的次數 $\le 0$」，完全符合 Bounded Waiting 的數學定義；

核心觀念

本題考查作業系統（Operating Systems）中**訊號量（Semaphore）**的實現方式及其分類。

在作業系統中，訊號量依據其實現機制主要分為兩大類：

1. 忙碌等待訊號量（Busy-waiting Semaphore / Spinlock）：

   • 當進程執行 $\text{wait()}$ 且訊號量數值 $\le 0$ 時，會進入 $\text{while}$ 無限迴圈持續測試條件。
   • 優點：無進程上下文切換（Context Switch）開銷。
   • 缺點：會浪費 CPU 時間（即 Busy Waiting 情況）。

2. 阻塞/睡眠型訊號量（Block/Sleep Semaphore / Non-busy-waiting Semaphore）：

   • 每個訊號量配有一個等待佇列（Waiting Queue）。
   • 當進程執行 $\text{wait()}$（或 $\text{P()}$）發現訊號量數值小於 0（或減一後為負）時，進程會呼叫 $\text{block()}$ 系統呼叫，將自身加入該訊號量的等待佇列中並暫停（Suspend/Block）執行，讓出 CPU。
   • 當另一個進程執行 $\text{signal()}$（或 $\text{V()}$）時，若等待佇列中有進程，會呼叫 $\text{wakeup()}$ 將受暫停的進程喚醒（Restart/Wakeup），並將其移入就緒佇列（Ready Queue）。

當教科書（如 Silberschatz 的 Operating System Concepts）未特別指定時，「標準的 Semaphore 實現」通常指帶有等待佇列、無 Busy Waiting 的阻塞型 Semaphore 實現（Overcoming Busy Waiting）。

---

解題方法與切入點

本題題目詢問：「關於 Semaphore 的實現，下列何者錯誤（NOT true）？」

切入點在於區分「帶有等待佇列的阻塞型 Semaphore 實現」與「Spinlock（Busy Waiting）實現」之間的差別。在標準的教科書定義中，為了防止 CPU 資源浪費，典型的 Semaphore 實現方式為：

1. 包含整數值（$\text{value}$）與等待佇列指標（$\text{list}$）。
2. $\text{wait()}$ 內部邏輯：當 $\text{value} < 0$ 時，將進程加入佇列並 $\text{block()}$（進入暫停狀態，排除了 Busy Waiting）。
3. $\text{signal()}$ 內部邏輯：當 $\text{value} \le 0$ 時，從佇列拿出進程並 $\text{wakeup()}$（重新啟動受暫停的進程）。

因此，標準的 Semaphore 實現克服（解決）了 busy waiting 問題。

---

選項分析

• (A) It suffers from the busy waiting problem（錯誤，本題應選此項）

  • 說明：標準的 Semaphore 實現利用作業系統提供的 $\text{block()}$ 與 $\text{wakeup()}$ 原語（Primitives），搭配等待佇列（Waiting Queue），使得無法進入臨界區的進程進入等待狀態（Waiting State）並交出 CPU 控制權，從而解決了 busy waiting 的問題。因此敘述「它遭受忙碌等待問題」是不正確的。

• (B) Semaphore has a waiting queue associated with the semaphore（正確）

核心觀念

本題考查作業系統中進程同步（Process Synchronization）經典問題——**讀者與寫者問題（Readers-Writers Problem）**的兩種主要變形及其哲學定義：

1. 第一種讀者與寫者問題（First Readers-Writers Problem, Reader Priority）：

   • 原則：除非寫者已經獲得共享資源的使用權，否則任何讀者都不應該因為寫者在等待而被阻塞（No reader should be kept waiting unless a writer has already obtained permission to use the shared object）。
   • 特性：讀者優先（Reader Priority）。當有一群讀者連續不斷進場時，後來的讀者可以直接進入 Critical Section（CS）讀取資料，導致等待中的寫者持續被推遲，因此寫者可能會飢餓（Writer Starvation）。

2. 第二種讀者與寫者問題（Second Readers-Writers Problem, Writer Priority）：

   • 原則：一旦寫者準備好寫入資料，該寫者應儘快執行寫入。若有寫者在等待，後續到達的讀者不可進入 CS（Once a writer is ready, that writer performs its write as soon as possible. No new readers can start reading if a writer is waiting）。
   • 特性：寫者優先（Writer Priority）。只要有寫者在排隊，後來的讀者就必須等待，直到所有寫者完成為止，因此讀者可能會飢餓（Reader Starvation）。

---

解題方法

核心觀念

本題考查作業系統中哲學家就餐問題（Dining-Philosophers Problem）的死鎖預防（Deadlock Prevention）機制，特別是非對稱解法（Asymmetric Solution）。

1. 死鎖的四個必要條件（Coffman Conditions）：
   • 互斥（Mutual Exclusion）
   • 持有並等待（Hold and Wait）
   • 無搶佔（No Preemption）
   • 循環等待（Circular Wait）
2. 非對稱解法（Asymmetric Solution）：
   讓哲學家在拿取筷子時打破對稱性（Symmetry）。例如：奇數號哲學家先拿左邊筷子再拿右邊筷子，而偶數號哲學家先拿右邊筷子再拿左邊筷子；或者是打破拿取筷子的順序約束。當打破對稱性後，所有哲學家不可能同時握有自己「左邊（或右邊）」的筷子並等待另一邊的筷子，從而打破了循環等待條件（Circular Wait），避免死鎖發生。

---

解題方法

本題切入點在於理解非對稱解法如何確保「當兩位相鄰的哲學家競爭中間 shared 筷子時」不會形成循環鎖死。

在非對稱解法下，相鄰哲學家拿取 chopsticks 的優先順序不同。當兩位相鄰哲學家競爭中間 shared 筷子時，必有其中一位已經先取得了他自己的另一根筷子（private/first chopstick），之後才去競爭這根共享筷子；或者競爭失敗者無法拿著半套資源形成閉環。

核心觀念

本題考查作業系統（Operating Systems）中**死結預防（Deadlock Prevention）**的定義與充要條件。

死結發生的四個**必要條件（Necessary Conditions）**分別為：

1. 互斥（Mutual Exclusion）：至少有一個資源必須處於非共享模式，一次只能由一個處理執行緒（process/thread）使用。
2. 持有並等待（Hold and Wait）：處理執行緒必須持有一個資源，並且正在等待取得其他被別的處理執行緒所持有的資源。
3. 不可搶佔（No Preemption）：資源不能被強行搶佔，只能由持有該資源的處理執行緒在完成任務後自願釋放。
4. 循環等待（Circular Wait）：存在一組等待處理執行緒 $\{P_0, P_1, \dots, P_n\}$，其中 $P_0$ 等待 $P_1$ 持有的資源，$P_1$ 等待 $P_2$ 持有的資源，……，$P_{n-1}$ 等待 $P_n$ 持有的資源，而 $P_n$ 等待 $P_0$ 持有的資源。

死結預防（Deadlock Prevention）的核心思想是：只要確保上述四個必要條件中「至少有一個不成立」（At least one condition does not hold），死結就絕對不可能發生。

---

解題方法

1. 根據邏輯學與作業系統理論：
   • 「四個條件同時成立」是「發生死結」的必要條件。
   • 逆否命題（Contrapositive）：只要破除至少一個條件（即至少有一個必要條件不成立），就能保障系統絕不發生死結（Deadlock-free）。
2. 分析題目敘述：
   • 題目詢問 "Deadlocks can be prevented only if ..."（死結只有在什麼情況下才能被預防？）。
   • 要達成 Deadlock Prevention，並不需要阻止全部四個條件發生，只要能確保打破「至少一個」條件即可。
   • 在實務與理論設計上，破除 Mutual Exclusion 通常非常困難（許多硬體資源如印表機本質上就是不可共享的），破除 Circular Wait（如資源賦予階層順序 Resource Ordering）是最常採用的手段。但無論破除哪一個，目的都是打破「至少一個必要條件」。

---

選項分析

核心觀念

本題考查作業系統中 死鎖避免（Deadlock Avoidance） 的核心演算法——銀行家演算法（Banker's Algorithm）。
關鍵定義與變數如下：

• Total Resources ($Total$)：系統擁有的資源總數。
• Allocation ($Allocation[i]$)：進程 $P_i$ 當前已持有的資源數。
• Max ($Max[i]$)：進程 $P_i$ 宣告的最大資源需求數。
• Need ($Need[i]$)：進程 $P_i$ 未來還需要的資源數，計算公式為 $Need[i] = Max[i] - Allocation[i]$。
• Available ($Available$)：系統目前剩餘可用的資源數，計算公式為 $Available = Total - \sum Allocation[i]$。

當進程發出資源請求 $Request_i$ 時，系統須依循以下規則判斷是否立即分配：

1. 合法性檢查：$Request_i \le Need[i]$ 且 $Request_i \le Available$。若不滿足則無法分配（需等待或視為錯誤）。
2. 試探性分配（Tentative Allocation）：假設滿足請求，更新狀態：
   • $Available' = Available - Request_i$
   • $Allocation[i]' = Allocation[i] + Request_i$
   • $Need[i]' = Need[i] - Request_i$
3. 安全狀態檢查（Safety Algorithm）：檢查更新後的狀態是否存在至少一個安全序列（Safe Sequence）。
   • 若存在安全序列，則系統處於安全狀態（Safe State），准許分配資源。
   • 若不存在安全序列，則系統處於不安全狀態（Unsafe State），拒絕分配資源（進程必須等待）。

---

解題方法與推導過程

第一步：分析初始狀態（Time 0）

由題目給定條件：$Total = 10$。
建立數據表格：

Process	$Max$	$Allocation$	$Need = Max - Allocation$
P0	10	4	$10 - 4 = 6$
P1	3	1	$3 - 1 = 2$
P2	5	4	$5 - 4 = 1$

計算 Time 0 的可用資源數 $Available$：
$Available = Total - (Allocation[0] + Allocation[1] + Allocation[2])$
$Available = 10 - (4 + 1 + 4) = 10 - 9 = 1$

---

第二步：分析 P1 發出請求後的狀態（Time 1）

Time 1 時，進程 $P_1$ 發出資源請求 $Request_1 = 1$。

1. 檢查請求合法性：
   • $Request_1 \le Need[1]$ ($1 \le 2$，符合)

核心觀念

本題考查作業系統中**基底暫存器與界限暫存器（Base and Limit Registers）**的記憶體保護與位址轉換機制。

1. 邏輯位址與實體位址（Logical vs. Physical Address）：
   • 使用 Base/Limit 機制時，CPU 產生的位址為邏輯位址（Logical Address / CPU offset），其範圍必須落在 $[0, \text{Limit})$。
   • 經由硬體加上 Base Register 後轉譯出的位址稱為實體位址（Physical Address），公式為：
     $\text{Physical Address} = \text{Base Address} + \text{Logical Address}$
   • 合法的實體位址範圍為：
     $[\text{Base}, \text{Base} + \text{Limit})$
2. 硬體保護檢查條件：
   • 若程式傳入的是邏輯位址 $d$，則合法條件為：
     $0 \le d < \text{Limit}$
   • 若題目問的是實體位址 $P$，則合法條件為：
     $\text{Base} \le P < \text{Base} + \text{Limit}$

---

解題方法

根據題意，已知基底暫存器 $\text{Base} = 1200$，界限暫存器 $\text{Limit} = 350$。

1. 計算合法位址範圍：
   • 邏輯位址（Logical Address）的合法範圍為：
     $0 \le \text{Logical Address} < 350$
     即位址界限為 $[0, 349]$。
   • 實體位址（Physical Address）的合法範圍為：
     $\text{Base} \le \text{Physical Address} < \text{Base} + \text{Limit}$
     代入數據求得：

核心觀念

本題考查作業系統中分頁機制（Paging System）的邏輯位址轉換（Logical Address Translation）。

在分頁記憶體管理架構下，邏輯位址（Logical Address / Virtual Address）由兩部分組成：

1. 頁碼（Page Number, $p$）：用作頁表（Page Table）的索引，指向實體記憶體中的對應頁框（Page Frame）。
2. 頁內偏移量（Page Offset, $d$）：表示資料在該頁面內的相對位置。

邏輯位址結構表示如下：
$\text{Logical Address} = (p, d)$

位址分割規則：
若分頁大小（Page Size）為 $S = 2^k$ bytes，則：

• 邏輯位址的最右邊（低位元）$k$ 個 bits 表示頁內偏移量（Page Offset, $d$）。
• 邏輯位址除偏移量外的其餘高位元表示頁碼（Page Number, $p$）。

在十六進制（Hexadecimal）表示法中，$1$ 個十六進制數位（Hex digit）恰好對應 $4$ 個二進制位元（bits）。若頁面大小正好為 $16$ 的次方數（如 $256 = 16^2$），則可以直接透過觀察或移位快速劃分頁碼與偏移量。

---

解題方法

步驟一：分析分頁大小與偏移量位元數

題目給定分頁大小（Page Size）為 $256$ bytes：
$S = 256 = 2^8 \text{ bytes}$
因此，頁內偏移量（Page Offset, $d$）佔用 $8$ 個 bits。

步驟二：分析邏輯位址與十六進制位數

題目給定邏輯位址為 $\text{0xAEF9}$。
在十六進制中：

• $1$ 個十六進制數位 $= 4$ bits。
• $8$ bits 的偏移量 $= \frac{8}{4} = 2$ 個十六進制數位。

因此，在四位的十六進位數 $\text{0xAEF9}$ 中：

• 最低位（右側）的 $2$ 個數位 $\text{F9}$ 為頁內偏移量（Page Offset, $d$）。
• 高位（左側）的其餘數位 $\text{AE}$ 即為頁碼（Page Number, $p$）。

核心觀念

本題考查作業系統中虛擬記憶體（Virtual Memory）的核心優勢與設計目的。

虛擬記憶體將程式設計師所面對的「邏輯位址空間（Logical Address Space）」與實際硬體的「實體記憶體（Physical Address Space）」進行解耦與分離。其主要優勢包含：

1. 解除記憶體大小限制：透過分頁 Swap（如將暫時不用的 Page 置換至輔助記憶體/磁碟 Secondary Storage），使邏輯位址空間可以遠大於實體記憶體空間。
2. 簡化程式設計：程式設計師撰寫程式時，不必關心實體記憶體剩餘多少、也不需手動維護 Overlay（覆蓋機制），提升開發效率。
3. 程式動態載入：配合請求分頁（Demand Paging），程式不需要將整體一次全部載入記憶體即可開始執行，大幅提升記憶體使用效率與系統多工度（Degree of Multiprogramming）。

---

解題方法

本題為觀念型單選題，切入點為比對虛擬記憶體（Virtual Memory）在教科書（如 Silberschatz 的 Operating System Concepts）中的標準定義與主要好處：

• 記憶體空間延伸：虛擬位址空間受限於 CPU 的定址位元數（如 32-bit 為 4 GB），而非實體 DRAM 大小。
• 程式開發體驗：保護與抽象化實體記憶體細節，簡化記憶體配置與管理。
• 載入與執行機制：僅將正在執行所需的 Page 載入實體記憶體（Lazy Swapper / Demand Paging），未用到的程式碼或資料留在磁碟。

經由逐一核對選項，可確認 (A)、(B)、(C) 皆屬於虛擬記憶體的經典優勢，因此應選擇綜合選項 (D)。

---

選項分析

• (A) a program can be much larger than the size of physical memory.（正確）
  • 分析：在虛擬記憶體機制下，程式的邏輯位址空間不受實體記憶體（RAM）容量限制。

核心觀念

本題考查作業系統（Operating System, OS）與計算機組織（Computer Architecture）中**分頁記憶體管理（Paged Memory Management）與虛擬記憶體（Virtual Memory）**之頁表項（Page Table Entry, PTE）標籤位元——**髒位元（Dirty bit / Modify bit）**的作用。

在虛擬記憶體架構中，記憶體分頁（Page）可能會被載入至實體記憶體（Main Memory / RAM）。當 CPU 對實體記憶體中的某個分頁執行寫入（Write / Store）操作時，該分頁的內容就會變得與次級儲存裝置（如 Disk, SSD）上的備份內容不一致。Dirty bit (Modify bit) 便是硬體（MMU）用來記錄「該分頁自從被載入至實體記憶體後，是否曾經被修改過」的標記位元。

---

解題方法

虛擬記憶體的頁替換（Page Replacement）與分頁寫回（Page Write-back）機制如下：

1. Dirty Bit 的設定：

   • 當頁面剛從磁碟載入實體記憶體時，Dirty bit 設為 0。
   • 每當 CPU 執行寫入指令對該頁面進行資料修改時，記憶體管理單元（MMU）會自動將該頁面對應的 Dirty bit 設為 1。

2. Dirty Bit 在頁替換（Page Replacement）時的作用：

   • 當系統發生分頁錯誤（Page Fault）且實體記憶體已滿時，作業系統必須選擇一個受害者頁面（Victim Page）將其換出（Swap out / Page out）：
     • Dirty bit = 0：代表該頁面內容未被修改過，與次級儲存裝置上的版本一致。作業系統可直接將其覆蓋（Overwrite），無須寫回磁碟，節省大量磁碟 I/O 時間。
     • Dirty bit = 1：代表該頁面內容已被修改，與磁碟上的版本不一致。

核心觀念

本題考查作業系統（Operating Systems）中虛擬記憶體（Virtual Memory）的分頁替換演算法（Page Replacement Algorithm）——先進先出法（FIFO, First-In, First-Out）。

1. Page Fault（分頁錯誤 / 頁面缺頁）：當 CPU 存取的 Page 目前不在主記憶體（RAM）的 Frame 中時，即觸發一次 Page Fault，此時作業系統必須從次級儲存裝置（如硬碟）將該 Page 載入至 Frame 中。
2. FIFO 替換演算法：當主記憶體空間已滿且發生 Page Fault 時，選擇**最早進入主記憶體（停留時間最久）**的 Page 將其淘汰（Victim Page）。
3. 初始狀態：在系統初始時，所有 Frame 皆為空白（Empty）。載入前幾個 Page 的過程也會觸發 Page Fault（稱為 Compulsory Fault / Cold Fault）。

---

解題方法

本題給定：

• Frame 數量：3 個
• Page Reference String（頁面參考字串）：1, 2, 3, 4, 2, 3, 4, 1, 2, 1, 1, 3, 1, 4

我們透過分頁狀態追蹤表（Page Table State Trace）逐一分析每次頁面存取的過程：

步驟	存取 Page	Frame 1	Frame 2	Frame 3	是否發生 Page Fault	說明 / 被替換的 Page
1	1	1			Page Fault (1)	載入 Page 1
2	2	1	2		Page Fault (2)	載入 Page 2
3	3	1	2	3	Page Fault (3)	載入 Page 3（Frame 已滿）
4	4	4	2	3	Page Fault (4)	淘汰最早進入的 Page 1，載入 Page 4
5	2	4	2	3	Hit（無缺頁）	Page 2 已在 Frame 2 中
6	3	4	2	3	Hit（無缺頁）	Page 3 已在 Frame 3 中