113 年 國立中央大學資訊工程學系軟體工程碩士班《作業系統與計算機組織》

核心觀念
本題考查 快取記憶體的存取時間模型、讀寫比例、命中率 (hit ratio)，以及 寫直通 (write‑through) 快取策略 如何影響平均記憶體存取時間 (AMAT)。必須先分別計算讀取與寫入的期望成本，再依比例加權求總體平均。

---

(a) 讀取與寫入的成本分析

操作	情況	成本 (ns)	發生機率
Read	命中 (hit)	只需要 L1 存取 → $C$	$H$
	未命中 (miss)	必須先檢查 L1 再到 L2 → $C + M$	$1-H$
Write (寫直通)	依題目，寫入皆為命中 ($\text{write hit ratio}=1$)	必須同時寫入 L1 與 L2 → $C + M$	$1$

• 讀取的期望成本

$$\text{Read\_cost}= H\cdot C + (1-H)\cdot (C+M) = C + (1-H)M$$

• 寫入的期望成本（寫直通）

$\text{Write\_cost}= C + M$

(b) 計算整體 AMAT

系統中 80% 為讀取、20% 為寫入：

核心觀念

本題考查計算機組織中**記憶體階層（Memory Hierarchy）與快取記憶體效能（Cache Effectiveness）**的決定因素。

快取記憶體的核心目標是利用資料存取的時間區域性（Temporal Locality）與空間區域性（Spatial Locality），彌補 CPU 處理速度與主記憶體（DRAM）存取速度之間的龐大差距（Processor-Memory Performance Gap）。

快取的有效性與整體效能通常透過**平均記憶體存取時間（Average Memory Access Time, AMAT）**與對系統執行時間的影響來衡量：

$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$

各項指標定義如下：

1. $\text{Hit Time}$（命中時間）：CPU 在快取中成功存取資料所需的時脈週期或時間。
2. $\text{Miss Rate}$（失誤率）：未命中快取的存取比例，主要由 3C 模型（Compulsory, Capacity, Conflict Misses）決定。
3. $\text{Miss Penalty}$（失誤懲罰）：發生快取失誤時，自下一階記憶體讀取資料填補至快取並傳回 CPU 所需的額外時間（通常以 CPU 時脈週期數算）。

---

解題方法

判斷各因素是否會影響快取效能，需檢視該變數是否會改變 AMAT 公式中的 $\text{Hit Time}$、$\text{Miss Rate}$ 或 $\text{Miss Penalty}$（以 CPU 時脈週期表示的代價）：

1. 快取容量（Cache Size）：容量越大，可容納資料越多，直接減少容量失誤（Capacity Misses），改變 $\text{Miss Rate}$ 與 $\text{Hit Time}$。
2. 組關聯度（Associativity）：關聯度越高，映射彈性越大，直接減少衝突失誤（Conflict Misses），改變 $\text{Miss Rate}$ 與多路選擇器的延遲（$\text{Hit Time}$）。
3. 快取行大小（Cache Line Size）：區塊越大，空間區域性利用越好，減少強制失誤（Compulsory Misses），但過大會增加傳輸時間（$\text{Miss Penalty}$）並增加衝突失誤。
4. CPU 時脈頻率（Clock Frequency of the CPU）：CPU 時脈頻率決定了時脈週期時間 $T_{\text{CLK}} = \frac{1}{f}$。主記憶體（DRAM）的存取延遲主要由物理特性決定（如 50 ns 固定的實體時間）。當 CPU 時脈頻率提升時，每一次快取失誤所消耗的 CPU 時脈週期數（$\text{Miss Penalty}_{\text{cycles}} = \text{DRAM Latency} \times f$）隨之增加，從而擴大了處理器與記憶體的速度鴻溝，直接影響快取失誤對整體效能的衝擊程度。

因此，A、B、C、D 四者皆為影響快取有效性與整體效能的關鍵因素。

---

選項分析

• (A) Cache size（快取容量）—— 正確
  快取總容量越大，可儲存的指令與資料區塊越多，能顯著降低**容量失誤（Capacity Misses）**並提升命中率（Hit Rate）。但過大的容量會增加解碼線路的繁複度，微幅增加命中時間（Hit Time）。因此，Cache size 直接決定快取效能。

本題在考察非揮發性儲存 (Non-Volatile Storage) 在記憶體層級結構中的特性。非揮發性儲存的關鍵特點是即使在斷電後仍能保持資料。

核心觀念：
記憶體層級結構 (Memory Hierarchy) 通常包含不同速度、容量和成本的儲存裝置。這些裝置可以分為揮發性 (Volatile) 和非揮發性 (Non-Volatile) 兩大類。

• 揮發性儲存 (Volatile Storage)：斷電後資料會遺失。例如：DRAM (主記憶體), SRAM (快取記憶體)。
• 非揮發性儲存 (Non-Volatile Storage)：斷電後資料不會遺失。例如：硬碟 (HDD), 固態硬碟 (SSD), 快閃記憶體 (Flash Memory), ROM (Read-Only Memory)。

選項分析：

(A) Non-volatile storage retains data even when power is lost
* 這是非揮發性儲存的定義性特徵。斷電後資料不會消失。此敘述正確。

(B) It is primarily used for temporary data storage
* 「臨時資料儲存」通常是指揮發性儲存（如 DRAM），因為它們存取速度快，適合暫存 CPU 正在處理的資料。

本題在考察記憶體管理單元 (MMU) 的功能。MMU 是現代處理器中負責虛擬記憶體管理的重要硬體單元，它在 CPU 和實體記憶體之間扮演著關鍵角色。

核心觀念：
MMU 主要負責將 CPU 產生的虛擬位址 (Virtual Address) 轉換為實體記憶體位址 (Physical Address)。這個轉換過程涉及到：

1. 位址轉換 (Address Translation)：

   • CPU 運作在虛擬位址空間，作業系統和 MMU 負責將這些虛擬位址映射到實際的實體記憶體位址。
   • 這個轉換通常是透過查閱頁表 (Page Table) 或段表 (Segment Table) 來完成的。MMU 包含一個快取，稱為轉換快取緩衝區 (Translation Lookaside Buffer, TLB)，用於加速這個位址轉換過程。

2. 記憶體保護 (Memory Protection)：

   • 在位址轉換的同時，MMU 也會檢查存取權限（讀取、寫入、執行），確保一個行程 (process) 不會存取到不屬於它的記憶體區域，從而提供記憶體保護。

3. 分頁與分段 (Paging and Segmentation)：

   • MMU 支援作業系統實現分頁或分段機制，將虛擬記憶體劃分為固定大小的頁 (pages) 或變動大小的段 (segments)，並在虛擬空間和實體空間之間進行映射。

選項分析：

(A) Manage data stored in cache
* 快取記憶體 (Cache Memory) 的管理（如決定何時載入、何時替換資料）主要由快取控制器 (Cache Controller) 負責，而不是 MMU。

本題在考察不同快取映對方式（Direct-mapped, Set-associative, Fully-associative）的特性。這些映對方式決定了主記憶體中的一個資料區塊 (block) 可以被放置在快取記憶體 (Cache Memory) 中的哪些位置，進而影響快取的命中率 (Hit Rate) 和硬體複雜度。

核心觀念：
快取記憶體將主記憶體分割成區塊 (blocks)，並將這些區塊載入到快取中的快取行 (cache lines)。映對方式決定了主記憶體區塊與快取行之間的對應關係。

1. 直接映射快取 (Direct-Mapped Cache)：

   • 主記憶體中的每個區塊只能對應到快取中的一個特定快取行。
   • 如果有多個主記憶體區塊映射到同一個快取行，就會發生衝突衝突 (conflict miss)，即使快取中還有其他空閒的快取行。
   • 這種方式硬體實現最簡單，但命中率通常較低，因為容易產生衝突衝突。

2. 全關聯快取 (Fully-Associative Cache)：

   • 主記憶體中的任何一個區塊都可以被放置在快取中的任何一個快取行。
   • 這提供了最大的彈性，可以最大限度地減少衝突衝突。
   • 然而，硬體實現最複雜，因為需要硬體在所有快取行中搜尋目標區塊，這通常需要更多的硬體電路（如比較器）和較長的存取時間。

3. 組關聯快取 (Set-Associative Cache)：

   • 這是介於直接映射和全關聯之間的一種折衷方案。
   • 快取被劃分成多個「組」(sets)。
   • 主記憶體中的一個區塊會被映射到快取中的一個特定組。
   • 在該組內，該區塊可以放置在該組內的任何一個快取行。
   • 例如，2-way set-associative cache 表示每個組有 2 個快取行。
   • 組關聯快取在命中率和硬體複雜度之間取得了較好的平衡。

選項分析：

本題在考察 CPU 流水線 (Pipelining) 的相關知識。流水線是一種 CPU 設計技術，旨在提高指令執行的吞吐量 (Throughput)。

核心觀念：
CPU 流水線將指令的執行分解為多個階段（如取指令 IF, 解碼 ID, 執行 EX, 記憶體存取 MEM, 回寫 WB）。這些階段可以並行處理不同指令的不同部分，從而讓 CPU 在每個時脈週期（理想情況下）完成一個指令，極大地提高了吞吐量。

選項分析：

(A) Increases CPU throughput by executing multiple instructions simultaneously.
* 流水線的主要目標就是提高吞吐量。雖然「同時執行」 (simultaneously) 可能有點誤導，因為同一時間點 CPU 的不同階段在處理不同的指令，但總體效果是讓多條指令的部分在流水線中並行處理。這確實提高了 CPU 的整體吞吐量（單位時間內完成的指令數）。此敘述正確。

(B) Eliminates all control hazards.
* 控制風險 (Control Hazards)，也稱為分支風險 (Branch Hazards)，發生在分支指令（如跳轉、條件分支）的目標位址或結果不確定時，導致流水線可能取錯指令。
* 流水線技術本身不會消除控制風險，而是需要額外的技術來處理，例如分支預測 (Branch Prediction)、延遲分支 (Delayed Branch)、分支目標緩衝區 (Branch Target Buffer, BTB) 等。這些技術旨在減輕控制風險的影響，但無法完全消除。此敘述錯誤。

(C) Data hazards can occur due to instruction overlap.
* 資料風險 (Data Hazards) 發生在後續指令依賴於前面尚未完成的指令所產生的結果時。例如，指令 B 需要指令 A 計算出的結果，但指令 B 在指令 A 的執行階段完成之前就進入了流水線。
* 由於流水線的指令重疊 (instruction overlap)，指令會按順序進入流水線，但它們的執行階段是錯開的。如果後續指令的讀取操作發生在先前指令的寫入操作之前，就會產生資料風險。
* 例如：

本題在考察虛擬記憶體 (Virtual Memory) 的相關概念。虛擬記憶體是一種記憶體管理技術，它為每個程序提供一個獨立且連續的虛擬位址空間，並將其映射到實體記憶體和磁碟空間。

核心觀念：
虛擬記憶體透過分頁 (Paging) 或分段 (Segmentation) 技術，將較小的實體記憶體擴展成一個更大的邏輯記憶體空間。它利用磁碟作為實體記憶體的補充，以容納超出實體記憶體容量的程式和資料。

選項分析：

(A) Virtual memory allows physical memory to be treated as a cache for the disk.
* 這個說法是正確的，而且是虛擬記憶體的核心思想之一。實體記憶體 (RAM) 被用來存放當前正在執行的程式和資料的「熱」部分 (hot pages)，而磁碟 (Disk) 則用於存放「冷」部分 (cold pages) 或不常用的資料。當 CPU 需要的資料不在實體記憶體中時（發生頁錯誤，Page Fault），就需要從磁碟載入到實體記憶體。因此，實體記憶體實際上扮演了磁碟內容的快取角色。

(B) TLB (Translation Lookaside Buffer) is used to reduce page table access time.
* 這是 TLB 的主要功能。虛擬位址到實體位址的轉換需要查閱頁表 (Page Table)，而頁表通常儲存在主記憶體中。為了加速這個過程，MMU (Memory Management Unit) 內建了一個快取，稱為 TLB，用於存放最近使用過的虛擬頁面到實體頁面的映射。當發生 TLB Hit 時，位址轉換可以在硬體中快速完成，避免了多次主記憶體存取。此敘述正確。

本題在考察快取記憶體 (Cache Memory) 在記憶體層級結構中的特性。快取記憶體是位於 CPU 和主記憶體之間的高速緩衝記憶體，旨在縮短 CPU 存取資料的平均時間。

核心觀念：
記憶體層級結構的設計目標是利用不同儲存技術的優缺點，在速度、容量和成本之間取得平衡。快取記憶體扮演著關鍵角色，它利用了程式執行的局部性原理 (Locality of Reference)。

選項分析：

(A) Cache memory has a lower latency than main memory.
* 這是快取記憶體最基本的特性。快取使用 SRAM 技術，其存取延遲 (latency) 通常遠低於使用 DRAM 技術的主記憶體。這也是快取能有效提升效能的原因。此敘述正確。

(B) Typically uses SRAM (Static RAM) technology.
* 快取記憶體為了達到高速存取，通常採用 SRAM (Static Random-Access Memory) 技術。SRAM 的存取速度比 DRAM 快，但成本較高，單位容量的功耗也較大。此敘述正確。

(C) Larger in size compared to main memory.
* 在記憶體層級結構中，越靠近 CPU 的儲存層級，其容量通常越小，而越遠的層級容量越大。

本題在考察 MIPS (Microprocessor without Interlocked Pipeline Stages) 指令集架構 (ISA) 的特性。MIPS 是一個經典的 RISC (Reduced Instruction Set Computer) 架構。

核心觀念：
RISC 架構的設計哲學是使用一套簡單、固定格式、執行速度快的指令集，並將複雜的操作分解為多條簡單指令來完成。這與 CISC (Complex Instruction Set Computer) 架構形成對比。

MIPS 的主要特性包括：

• 精簡指令集 (Reduced Instruction Set)：指令數量相對較少，且指令功能單一。
• 固定長度指令 (Fixed-length Instructions)：所有指令通常具有相同的長度（例如 32 位元），這簡化了指令的擷取和解碼。
• 暫存器對暫存器操作 (Register-to-Register Operations)：大多數算術和邏輯運算都在暫存器之間進行，而不是直接操作記憶體。記憶體存取通常僅限於 Load 和 Store 指令。
• 延遲分支 (Delayed Branch)：為了提高流水線效率，MIPS 採用了延遲分支技術。分支指令的延遲槽 (delay slot) 中的指令會被無條件執行，即使分支指令改變了程式流程。這使得編譯器有機會將有用的指令填入延遲槽，以減少分支造成的流水線停頓。
• 載入/儲存架構 (Load/Store Architecture)：只有 Load 指令可以將資料從記憶體載入到暫存器，只有 Store 指令可以將資料從暫存器寫回記憶體。

選項分析：

本題在考察 SIMD (Single Instruction, Multiple Data) 並行處理的特性。SIMD 是一種電腦架構，允許在單一指令週期內對多個資料點執行相同的操作。

核心觀念：
SIMD 是一種資料級並行 (Data-Level Parallelism, DLP) 的模型。它包含一個指令單元和多個資料處理單元。指令單元發出一個指令，該指令會被同時應用到所有資料處理單元所處理的數據上。

選項分析：

(A) Executes different instructions on multiple data points.
* 這是 MIMD (Multiple Instruction, Multiple Data) 的特徵，而不是 SIMD。SIMD 的核心是「單一指令」應用於「多個資料」。此敘述錯誤。

(B) Well-suited for tasks with regular data patterns.
* SIMD 的設計非常適合處理具有規則數據模式的任務，例如向量運算、矩陣運算、圖像處理、信號處理等。在這些任務中，相同的操作需要應用到大量相似結構的數據上。此敘述正確。

(C) Commonly used in vector processors.
* 向量處理器 (Vector Processors) 是 SIMD 的典型實現。它們擁有能夠處理向量（即一系列數據）的指令和硬體單元。此敘述正確。

(D) Typically involves multiple processors working on the same task.

本題在考察在沒有硬體支援的特權模式 (Privileged Mode) 的系統中，作業系統如何維持對系統的控制權（例如，在 monitor mode 下運行）。

核心觀念：
在大多數現代作業系統中，CPU 具有兩種操作模式：

1. 特權模式 (Privileged Mode / Kernel Mode / Supervisor Mode)：作業系統核心運行在此模式，擁有對硬體和所有記憶體的完全存取權限。
2. 使用者模式 (User Mode)：使用者程式運行在此模式，其權限受到限制，無法直接存取敏感的硬體資源或執行特權指令。

當使用者程式需要執行特權操作（如 I/O、記憶體管理）時，必須透過系統呼叫 (System Call) 的方式，觸發從使用者模式切換到核心模式，由作業系統來處理。

題目描述的情況是「沒有硬體支援的特權模式」。這意味著 CPU 總是運行在一個單一的模式下，沒有明確區分核心模式和使用者模式。在這種情況下，作業系統必須找到其他方法來確保其控制權和系統的穩定性，防止使用者程式破壞系統。

選項分析：

(A) Software interpretation of all user programs.
* 這是一種可行的方法。如果所有使用者程式都是透過一個「軟體解釋器」(software interpreter) 來執行的，那麼這個解釋器本身就可以被設計成一個受控的環境。解釋器可以攔截所有潛在的危險操作（例如，試圖直接存取硬體），並在必要時拒絕執行或模擬特權操作（透過系統呼叫的方式，如果系統有辦法模擬的話）。這樣，解釋器就扮演了保護者的角色，即使底層硬體沒有特權模式。此方法在某些模擬環境或早期系統中可能被使用。此敘述正確。

核心觀念

頁面大小會同時影響記憶體管理的空間成本與存取效能。選擇頁面大小時，通常要考慮頁表大小、內部碎裂、磁碟 I/O 成本，以及缺頁次數等因素；這些因素彼此牽制，沒有適用所有系統的單一最佳值。

解題方法

逐一判斷頁面大小對各項成本的影響：

• 若虛擬位址空間大小為 $V$、頁面大小為 $P$，頁表項目數約為 $\lceil V/P\rceil$。頁面越大，所需頁表項目通常越少，頁表也較小。
• 頁面越大，程式最後一頁未使用的空間可能越多，造成較大的內部碎裂。
• 缺頁時通常要從後備儲存裝置載入頁面。頁面大小會影響每次 I/O 傳輸的資料量，也會影響傳輸次數及 I/O 成本。
• 頁面大小會改變程式執行時的缺頁行為。較大的頁面可能一次載入更多鄰近資料，也可能載入未使用的資料，因此缺頁次數會受工作負載與區域性影響。

選項分析

核心觀念

本題考驗作業系統中**需求分頁（Demand Paging）機制下的頁面替換演算法（Page Replacement Algorithms）**與頁面錯誤（Page Fault）次數計算。

當系統分配給行程的頁框數量（Number of Frames）有限（本題 $N = 3$ 且初始為空），而存取的頁面不在主記憶體中時，便會觸發頁面錯誤（Page Fault），此時需依據指定的頁面替換演算法選擇一個頁框進行淘汰：

1. LRU (Least Recently Used) 替換演算法：淘汰過去「最長時間未被存取/使用」的頁面（看過去）。
2. FIFO (First-In, First-Out) 替換演算法：淘汰「最早進入主記憶體」的頁面（看進入時間）。
3. Optimal (OPT / MIN) 替換演算法：淘汰未來「最長時間不會被使用」或「未來不再被使用」的頁面（看未來，為理論最佳上限）。

題目給定的頁面參考序列（Page Reference String）長度為 $20$：
$7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1$

---

解題方法

配置 $3$ 個頁框（Frame 1, Frame 2, Frame 3），初始均為空。我們針對三種演算法分別進行逐步追蹤與 Page Fault 統計。

---

一、 LRU (Least Recently Used) 演算法推導

LRU 依據「過去最後一次存取的時間戳記」進行淘汰，時間戳記最舊者優先淘汰。

時間 $t$	參考頁面	頁框狀態 (Frame 1, 2, 3)	狀態與動作	淘汰頁面
$1$	7	$[7, -, -]$	Page Fault #1	無
$2$	2	$[7, 2, -]$	Page Fault #2	無
$3$	3	$[7, 2, 3]$	Page Fault #3	無
$4$	1	$[1, 2, 3]$	Page Fault #4 (最久未使用者為 7)	7
$5$	2	$[1, 2, 3]$	Hit (更新 2 的最新存取時間)	無
$6$	5	$[1, 2, 5]$	Page Fault #5 (最久未使用者為 3)	3
$7$	3	$[3, 2, 5]$	Page Fault #6 (最久未使用者為 1)	1
$8$	4	$[3, 4, 5]$	Page Fault #7 (最久未使用者為 2)	2
$9$	6	$[3, 4, 6]$	Page Fault #8 (最久未使用者為 5)	5
$10$	7	$[7, 4, 6]$	Page Fault #9 (最久未使用者為 3)	3
$11$	7	$[7, 4, 6]$	Hit (更新 7 的最新存取時間)	無
$12$	1	$[7, 1, 6]$	Page Fault #10 (最久未使用者為 4)	4
$13$	0	$[7, 1, 0]$	Page Fault #11 (最久未使用者為 6)	6
$14$	5	$[5, 1, 0]$	Page Fault #12 (最久未使用者為 7)	7
$15$	4	$[5, 4, 0]$	Page Fault #13 (最久未使用者為 1)	1
$16$	6	$[5, 4, 6]$	Page Fault #14 (最久未使用者為 0)	0
$17$	2	$[2, 4, 6]$	Page Fault #15 (最久未使用者為 5)	5
$18$	3	$[2, 3, 6]$	Page Fault #16 (最久未使用者為 4)	4
$19$	0	$[2, 3, 0]$	Page Fault #17 (最久未使用者為 6)	6
$20$	1	$[1, 3, 0]$	Page Fault #18 (最久未使用者為 2)	2

• LRU 命中次數（Hit）：$2$ 次（分別在 $t=5, 11$）
• LRU 頁面錯誤次數（Page Fault）：$20 - 2 = 18$ 次。

---

二、 FIFO (First-In, First-Out) 演算法推導

FIFO 依據頁面「進入記憶體的順序」進行淘汰，與後續是否有被再次讀取無關。

時間 $t$	參考頁面	頁框狀態 (Frame 1, 2, 3)	佇列先進先出順序 (Oldest $\rightarrow$ Newest)	狀態與動作	淘汰頁面
$1$	7	$[7, -, -]$	$7$	Page Fault #1	無
$2$	2	$[7, 2, -]$	$7, 2$	Page Fault #2	無
$3$	3	$[7, 2, 3]$	$7, 2, 3$	Page Fault #3	無
$4$	1	$[1, 2, 3]$	$2, 3, 1$	Page Fault #4	7
$5$	2	$[1, 2, 3]$	$2, 3, 1$	Hit (佇列順序不變)	無
$6$	5	$[1, 5, 3]$	$3, 1, 5$	Page Fault #5	2
$7$	3	$[1, 5, 3]$	$3, 1, 5$	Hit (佇列順序不變)	無
$8$	4	$[1, 5, 4]$	$1, 5, 4$	Page Fault #6	3
$9$	6	$[6, 5, 4]$	$5, 4, 6$	Page Fault #7	1
$10$	7	$[6, 7, 4]$	$4, 6, 7$	Page Fault #8	5
$11$	7	$[6, 7, 4]$	$4, 6, 7$	Hit (佇列順序不變)	無
$12$	1	$[6, 7, 1]$	$6, 7, 1$	Page Fault #9	4
$13$	0	$[0, 7, 1]$	$7, 1, 0$	Page Fault #10	6

本題在考察容器 (Containers) 與虛擬機器 (Virtual Machines, VMs) 的概念與特性。

核心觀念：

• 虛擬機器 (Virtual Machines, VMs)：透過硬體虛擬化層 (Hypervisor) 在物理硬體上模擬出一個完整的電腦系統，包括虛擬化的 CPU、記憶體、儲存和網路設備。每個 VM 運行一個完整的作業系統 (Guest OS)，與主機作業系統 (Host OS) 和其他 VM 隔離。
• 容器 (Containers)：運行在主機作業系統之上，共享主機作業系統的 Linux 核心。容器之間隔離的是使用者空間的行程和檔案系統，而不是整個作業系統。

選項分析：

(A) Each container includes the application, the necessary binaries and libraries and an entire guest operating system
* 這是虛擬機器的描述，而不是容器。容器不包含整個 Guest OS，它們共享主機 OS 的核心。此敘述錯誤。

(B) Containers running on a single machine all share the same operating system kernel
* 這是容器的核心特徵。所有在同一台主機上運行的容器都共享該主機作業系統的 Linux 核心。這使得容器比虛擬機器更輕量級。此敘述正確。

本題在考察「機制與策略分離」(Separation of Mechanism and Policy) 的目的。這是在作業系統設計中一個重要的原則。

核心觀念：

• 機制 (Mechanism)：指實現某種功能的低階方法或工具。它定義了「如何做」(how)。例如，在記憶體管理中，分頁 (paging) 和分段 (segmentation) 是實現位址轉換和記憶體保護的機制。
• 策略 (Policy)：指決定如何使用機制的規則或決策。它定義了「何時做」(when) 和「為何做」(why)。例如，在記憶體管理中，決定何時進行頁面替換（例如 LRU, FIFO）或分配多少記憶體給一個行程，就是策略。

將機制與策略分離，意味著將實現功能的低階方法與決定如何應用這些方法的決策分開。

選項分析：

(A) Easy to programming
* 分離機制與策略本身不一定使「程式編寫」更容易。編寫應用程式的難易度主要取決於 API 的設計和語言本身。雖然分離後，系統的設計更清晰，可能有利於開發者理解和使用系統功能，但這不是其主要目的。

(B) Systems are easy to modify
* 當機制與策略分離時，如果需要改變策略（例如，更換一種頁面替換演算法），可以只修改策略部分，而不需要改動底層的機制實現。反之，如果底層機制需要更新或替換，只要其介面（API）不變，策略部分通常也不需要修改。

本題考察 RAID 結構、倒排頁表 (Inverted Page Table) 等電腦組織和作業系統中的概念。

核心觀念：

• RAID (Redundant Array of Independent Disks)：一種將多個硬碟組合成一個邏輯單位的技術，旨在提高效能、可靠性或兩者兼具。
• 倒排頁表 (Inverted Page Table)：一種用於虛擬記憶體管理的頁表結構，與傳統的「Forward Page Table」相對。

選項分析：

(A) The RAID structure is used to address the performance and reliability issues of disk organization
* RAID 的主要目標就是透過冗餘 (Redundancy) 和/或條帶化 (Striping) 來解決傳統單一硬碟在效能（讀寫速度）和可靠性（容錯能力）方面的不足。例如，RAID 0 提升效能，RAID 1, 5, 6, 10 提升可靠性。此敘述正確。

(B) RAID level 5 can tolerate two disk failures
* RAID 5 使用分散式奇偶校驗 (Distributed Parity)，可以容忍一個磁碟故障。當一個磁碟損壞時，系統可以利用剩餘磁碟上的資料和奇偶校驗資訊來重建損壞磁碟的資料。

本題考察作業系統中關於行程 (Process) 和執行緒 (Thread) 的排程、同步和保護機制。

核心觀念：

• 行程競爭範圍 (Process Contention Scope, PCS) vs 執行緒競爭範圍 (Thread Contention Scope, TCS)：
  • PCS：行程級別的排程，決定哪個行程在 CPU 上運行。通常由作業系統核心負責。
  • TCS：執行緒級別的排程，決定哪個執行緒在行程的 LWP (Light Weight Process) 或 CPU 上運行。可以由使用者空間的執行緒庫或核心負責。
• 優先級搶佔 (Priority Preemption)：高優先級的任務會打斷低優先級任務的執行。
• 優先級反轉 (Priority Inversion)：低優先級任務持有某個資源（如鎖），而一個高優先級任務需要該資源，但低優先級任務無法及時釋放資源，導致高優先級任務被延遲，這違反了預期的優先級順序。
• 競賽條件 (Race Condition)：當多個執行緒或行程同時存取共享資源，並且它們的執行順序影響最終結果時，就會發生競賽條件。

選項分析：

(A) Process-contention scope involves the decision of which kernel thread to schedule
onto which CPU
* 行程競爭範圍 (PCS) 主要處理行程之間的競爭，即哪個行程獲得 CPU 的執行權。而「哪一個核心執行緒 (kernel thread) 被排程到哪個 CPU 上」通常是執行緒競爭範圍 (TCS) 的一部分，特別是在多核心系統中，核心排程器 (Kernel Scheduler) 負責將核心執行緒映射到可用的 CPU 上。PCS 更側重於在多行程環境中，行程之間的 CPU 分配。此敘述不準確，或至少不是 PCS 的主要職責。PCS 更多是關於行程之間的 CPU 分配，而 TCS 則涉及行程內部執行緒的調度。

(B) PCS will typically preempt the thread currently running in favor of a higher-
priority thread
* PCS 是指行程級別的排程。如果 PCS 決定將 CPU 分配給一個高優先級的行程，那麼該行程可能會搶佔 (preempt) 當前正在 CPU 上運行的低優先級行程。
* 但是，這裡提到了「thread」，這可能指的是核心執行緒 (kernel thread)。如果 PCS 是指核心排程器，那麼它確實會基於行程（或核心執行緒）的優先級來進行搶佔。
* 然而，問題是問 PCS 本身，PCS 通常是指行程之間的競爭。

本題考察 CPU 排程演算法 (Scheduling Algorithms) 和虛擬記憶體分頁相關概念。

核心觀念：

• 排程演算法：決定行程或執行緒在 CPU 上執行的順序和時間。常見的有 FIFO, SJF, RR, Priority Scheduling, Multilevel Queue Scheduling。
• 周轉時間 (Turnaround Time)：一個行程從提交到完成所經過的總時間。平均周轉時間是衡量排程演算法效能的重要指標。
• SJF (Shortest Job First)：優先執行預期執行時間最短的行程。可以是搶佔式 (Preemptive) 或非搶佔式 (Non-preemptive)。
• RR (Round Robin)：時間片輪轉，每個行程輪流獲得一個固定時間片。
• 多層次佇列排程 (Multilevel Queue Scheduling)：將行程分為多個獨立的佇列，每個佇列有自己的排程演算法。
• 虛擬記憶體分頁：頁表大小與分頁大小、虛擬位址空間大小相關。

選項分析：

(A) If all jobs have the same run length and the round-robin (RR) scheduler's time
quantum is much shorter than the jobs' run length, the RR scheduler provides
better average turnaround time than FIFO
* FIFO (First-In, First-Out)：按到達順序執行。
* RR (Round Robin)：時間片輪轉。
* 當所有任務運行時間相同 (run length) 且遠大於時間片 (time quantum) 時：
* FIFO 的周轉時間會比較長，因為後來的任務必須等待前面的任務全部完成。
* RR 的任務會被不斷切換，每個任務都會在每個時間片結束後重新進入就緒佇列。這會引入上下文切換的開銷。
* 然而，如果運行時間遠大於時間片，RR 會使得每個任務都能在相對較短的時間內獲得 CPU 的執行機會，這有助於降低平均等待時間 (Average Waiting Time)。
* 對於平均周轉時間 (Average Turnaround Time)，RR 的情況比較複雜。如果上下文切換開銷很小，RR 由於能讓所有任務更快地開始執行並獲得 CPU 輪流使用，通常能提供比 FIFO 更好的平均周轉時間，因為它避免了長任務阻塞短任務的情況。

本題考察作業系統中的幾個重要概念：分頁 (Paging)、監視器 (Monitor)、死結 (Deadlock) 和行程建立 (Process Creation)。

核心觀念：

• 有效/無效位元 (Valid/Invalid Bit)：在頁表條目 (Page Table Entry, PTE) 中，用來指示該頁面是否有效（即是否在實體記憶體中）。
• 監視器 (Monitor)：一種同步機制，提供一種結構化的方法來確保對共享資源的互斥存取，並可以包含條件變數 (Condition Variables) 來實現行程間的協調。
• 死結 (Deadlock)：發生在多個行程互相等待對方釋放資源，形成循環等待，導致所有行程都無法繼續執行。
• 銀行家演算法 (Banker's Algorithm)：一種用於死結預防 (Deadlock Prevention) 或死結避免 (Deadlock Avoidance) 的演算法。
• 寫時複製 (Copy-on-Write, COW)：一種資源管理技術，當多個行程共享同一資源的唯讀副本時，只有在其中一個行程嘗試修改該資源時，才會為該行程創建一個獨立的副本。

選項分析：

(A) The valid-invalid bit is adopted to reduce the overhead of page transfers
* 有效/無效位元 (Valid/Invalid Bit) 在頁表條目中，用於指示該頁面是否在實體記憶體中。
* 當 CPU 嘗試存取一個頁面時，MMU 會檢查該位元。如果為「無效」(Invalid)，則會觸發頁錯誤 (Page Fault)，作業系統需要將該頁面從磁碟載入到實體記憶體。
* 這個位元本身不直接用於減少頁面傳輸的開銷。它的主要目的是實現虛擬記憶體管理，標識頁面的有效性，並觸發必要的頁錯誤處理。頁面傳輸的開銷（讀寫磁碟）是固定的，該位元的作用是判斷是否需要傳輸。
* 減少頁面傳輸開銷通常透過優化替換演算法、使用更快的儲存介質等方式實現。
* 此敘述錯誤。

(B) Only one process may be active within the monitor at a time

本題考察資訊安全和網路相關的知識，包括標準、攻擊類型、安全協定和網路工具。

核心觀念：

• ISO/IEC 27001：資訊安全管理系統 (Information Security Management System, ISMS) 的國際標準。
• DoS (Denial of Service) Attack：阻斷服務攻擊，旨在使目標服務不可用。
• Man-in-the-Middle (MitM) Attack：中間人攻擊，攻擊者秘密地在通信雙方之間傳遞和可能修改訊息。
• TLS (Transport Layer Security)：用於在網路應用程式之間提供通訊加密和身份驗證的協定。
• IPSec (Internet Protocol Security)：用於保護 IP 網路通訊的協定套件，提供身份驗證、資料完整性和資料機密性。
• DNS (Domain Name System)：將人類可讀的網域名稱解析為機器可讀的 IP 位址的系統。
• nslookup：一個用於查詢 DNS 伺服器的命令列工具。

選項分析：

(A) ISO/IEC 27001 is an international standard to manage information security
* ISO/IEC 27001 是國際標準化組織 (ISO) 和國際電工委員會 (IEC) 發布的一項標準，用於建立、實施、維護和持續改進資訊安全管理系統 (ISMS)。它提供了組織管理資訊安全風險的框架。此敘述正確。

(B) The DOS attack is a kind of the man-in-the-middle attacks.
* DoS (Denial of Service) Attack 的目標是癱瘓目標服務，使其無法響應合法用戶的請求。常見的 DoS 攻擊包括發送大量請求、利用服務的漏洞耗盡資源等。