111 年 國立政治大學資訊科學系碩士班《作業系統》

(1) Bare‑Metal VM 直接在硬體上執行，較少抽象層，效率高；Hosted VM 需透過宿主 OS，較低效，故 (a) 為真。CP/CMS 為 IBM 360/370 首套支援全虛擬化的作業系統，屬真。VMM（Virtual Machine Monitor）與 hypervisor 本質上同義，亦為真。大多數 VMM 皆針對特定指令集或平台實作，無法於所有硬體平台上執行，故 (d) 為偽。
【答案】 (d)

(2) 作業系統為每個行程維護 PCB、頁表與 PTBR（每行程的頁表基址暫存器值），但 TLB 為每顆 CPU 的快取，不屬於 OS 為行程保存的資料結構。
【答案】 (a)

(3) 近似 Working Set 的常用演算法是「Page‑Fault‑Frequency (PFF)」法，其透過觀測缺頁頻率估算工作集大小。
【答案】 (b)

(4) SSD 相較於磁性硬碟的唯一顯著優勢是存取速度遠快於旋轉磁片。
【答案】 (a)

(5) 正確的開機流程：
b. 開機韌體載入並執行 boot loader
d. boot loader 讀取 kernel 映像檔至記憶體並啟動
e. kernel 初始化裝置與驅動程式
c. kernel 掛載根檔案系統

核心觀念

本題考查作業系統（Operating Systems）五個核心領域的基本觀念與定義：

1. Copy on write：記憶體管理（Memory Management）與行程建立（Process Creation, 如 fork()）之記憶體空間優化機制。
2. Reentrant Lock：執行緒同步（Synchronization）機制中防範執行緒自我死鎖（Self-Deadlock）之互斥鎖設計。
3. Orphan：行程管理（Process Management）中父子行程生命週期不對稱與資源回收機制。
4. Windows ALPC：Windows 作業系統微核心架構下用戶端／伺服器端高效能跨行程通訊（Inter-Process Communication, IPC）機制。
5. Safe State：死鎖避免（Deadlock Avoidance）理論中資源分配狀態（Resource-Allocation State）判定定理。

---

解題方法與名詞詳細解析

針對題目要求的五個專有名詞，分別提供標準定義、運作流程與系統機制說明：

1. Copy on write (for process creation)

• 核心定義：
  在傳統 UNIX/Linux 系統中，當父行程呼叫 fork() 建立子行程時，若立即完整複製父行程的實體記憶體位址空間（Address Space），會產生極高的時空開銷。寫入時複製（Copy-on-Write, COW） 是一種延遲記憶體配置與複製的優化技術。
• 運作步驟與機制：
  1. 頁面共享：在 fork() 執行瞬間，子行程直接與父行程共享相同的實體記憶體頁面（Physical Frames），暫不進行實體頁面的複製。
  2. 唯讀標記：作業系統將父子行程頁表項（Page Table Entry, PTE）中的寫入權限皆設為「唯讀（Read-Only）」。
  3. 頁面錯誤（Page Fault）：當父行程或子行程任一方試圖修改共享頁面的內容時，硬體 MMU 觸發保護違規例外。
  4. 實體複製與更新：作業系統的 Page Fault Handler 捕獲例外後，於實體記憶體中配置一個全新的 Frame，將舊頁面內容複製過去，並將寫入者的頁表項重新指向新 Frame 並改標為「可讀寫（Read-Write）」。另一方則繼續使用原 Frame。
• 效能優勢：若子行程建立後隨即呼叫 exec() 載入全新程式，COW 可完全避免無謂的記憶體複製開銷。

2. Reentrant Lock（可重入鎖）

• 核心定義：
  可重入鎖（Reentrant Lock，亦稱 Recursive Lock）是一種同步互斥鎖機制，允許已成功持有該鎖的執行緒（Thread），在未釋放鎖的情況下，能夠再次（重複）獲取同一個鎖而不會引發自我死鎖（Self-Deadlock）。
• 運作步驟與機制：
  1. 內部狀態變數：鎖內部維護了「持有者執行緒標示（Owner Thread ID）」與「重入計數器（Hold Count）」 $C$。
  2. 加鎖流程（Acquire）：
     • 若鎖未被佔用，設定 Owner 為當前執行緒，且計數器 $C \leftarrow 1$。
     • 若鎖已被當前執行緒持有，允許直接通過，並更新計數器 $C \leftarrow C + 1$。
     • 若鎖被其他執行緒持有，則當前執行緒進入等待狀態（Blocked）。
  3. 解鎖流程（Release）：
     • 持有者解鎖時，計數器 $C \leftarrow C - 1$。
     • 僅當計數器降低至 $C = 0$ 時，鎖才真正解鎖並釋放 Owner，同時喚醒等待佇列中的其他執行緒。
• 應用情境：常用於遞迴函數（Recursive Functions）對共享資源的保護，或同一個執行緒在多個互相呼叫的類別方法中均設有同步區塊（Synchronized Blocks）的情境。

3. Orphan Process（孤兒行程）

• 核心定義：
  在 UNIX/Linux 系統的行程階層（Process Hierarchy）架構中，當父行程（Parent Process）已經終止（Terminated）或異常結束，但其建立的子行程（Child Process）仍在繼續執行時，該子行程即稱為孤兒行程（Orphan Process）。
• 系統處理機制：
  1. 領養（Adoption）：作業系統核心不會允許孤兒行程長期無主。當父行程終止時，系統核心會自動將該孤兒行程的父行程重新指定（Adopt）為系統根行程 init（PID = 1）或現代 Linux 中的 Reaping 行程（如 systemd）。
  2. 資源回收：當孤兒行程最終執行結束時，init 行程會呼叫 wait() / waitpid() 收集其退出狀態（Exit Status），並釋放其在系統行程表（Process Table）中佔用的 PID 與 PCB（Process Control Block）資源，防止其變成無法回收資源的殭屍行程（Zombie Process）。

4. Windows ALPC (Advanced Local Procedure Call)

• 核心定義：
  進階本地程序呼叫（ALPC） 是 Windows 作業系統（自 Windows Vista / Server 2008 起引進，取代舊版 LPC）內部用於同台機器上行程之間進行高效能通訊的高級 IPC 機制。常用於用戶模式行程（User-Mode Processes）與作業系統核心服務/子系統（如 csrss.exe、lsass.exe）之間的訊息交換。
• 傳輸模式與機制：

核心觀念

本題考查作業系統與軟體系統設計中「狀態管理（State Management）與資料結構設計」的抽象核心哲學。這四大技術雖然應用領域不同（版本控制、檔案系統、分散式帳本、軟體架構），但均捨棄了傳統的「原處更新（In-place Update）」模式，轉而採用以下核心設計原理：

1. 不可變性（Immutability）與唯增日誌（Append-Only Storage）：歷史資料一旦寫入即不可修改或刪除，新的變更僅能以新增（Append）方式疊加。
2. 寫入時複製（Copy-on-Write, CoW）與結構共享（Structural Sharing）：修改資料時不直接覆蓋舊版本，而是建立新版本並共享未修改的歷史資料區塊。
3. 由歷史導向狀態推導（State Derived from History）：系統當前狀態（Current State）並非直接儲存的主體，而是由歷史變更紀錄疊加或重播（Replay）推導出的結果，數學關係可表示為：
   $\text{Current State} = \text{Initial State} + \sum_{i=1}^{n} \Delta_i$
4. 回溯鏈結結構（Parent-Pointer / Hash-Linked Structure）：利用指標或加密雜湊值將新舊狀態串接，提供歷史可稽核性（Auditability）與版本時間旅行（Time-Travel）能力。

---

解題方法

解題切入點在於將四大技術進行抽象化歸納。解題時應先統整出跨技術的核心設計理念（Core Commonalities），再將 Git、Union FS、Blockchain 與 Event Sourcing 逐一對映至該理念中，展現對作業系統與系統架構的深刻理解。

解題架構分為兩大部分：

1. 共通核心理念摘要：歸納 Immutability、Append-Only、Copy-on-Write/Layering 與 State Replay 四大要素。
2. 個別技術落地分析：說明各技術如何實作上述理念及其獲得的系統優勢（如高並行、歷史復原、免鎖定存取等）。

---

技術分析

1. Git（版本控制系統）

• 設計機制：採用基於內容定址（Content-Addressable Storage）的 DAG（有向無環圖）資料結構。每一次提交（Commit）均為包含父節點雜湊值（Parent Hash）的不可變物件。
• 共性對映：Git 物件一旦寫入檔案庫即不可變（Immutable）。當修改程式碼時，Git 不會覆蓋舊檔案，而是產生新的 Blob/Tree 物件並共享未變更的物件（Structural Sharing）。專案當前狀態即為沿著 DAG 鏈結推導出的 snapshot。

2. Union FS（分層檔案系統）

• 設計機制：將多個實體目錄重疊掛載為單一虛擬檔案系統（例如 Docker 容器鏡像）。下方層級均為唯讀層（Read-Only Layers），最上層為可寫層（Writable Layer）。
• 共性對映：底層鏡像具備不可變性（Immutable）。當嘗試修改下層檔案時，系統觸發「寫入時複製（Copy-on-Write, CoW）」，將檔案複製一份至最上層可寫層進行修改。

核心觀念

1. DMA（Direct Memory Access，直接記憶體存取）定義：
   DMA 是一種硬體機制，允許高速輸入/輸出（I/O）裝置與主記憶體（Main Memory）之間直接傳輸資料，而無需 CPU 逐字元或逐位元組（Byte-by-Byte）參與或透過 CPU 內部的暫存器進行中轉。

2. 傳統 I/O 傳輸模式的瓶頸：

   • 程式化 I/O（Programmed I/O）：CPU 必須透過忙碌等待（Busy-waiting / Polling）輪詢 I/O 裝置狀態，並親自搬移每一個 Byte，導致 CPU 利用率極低。
   • 中斷驅動 I/O（Interrupt-driven I/O）：雖解決了輪詢等待的問題，但傳輸大量資料時，每傳輸一個 Byte 就要觸發一次硬體中斷（Hardware Interrupt），引發頻繁的上下文切換（Context Switch）與中斷服務程式（ISR）執行開銷，造成「中斷風暴（Interrupt Storm）」。

3. DMA 控制器（DMA Controller, DMAC）的運作角色：
   DMAC 扮演專用協同處理器的角色。當 CPU 完成 DMA 初始化設定後，DMAC 接管記憶體匯流排（Bus）控制權，直接進行記憶體與 I/O 裝置間的整區塊傳輸（Block Transfer），僅在傳輸完全結束時發送一次中斷通知 CPU。

---

解題方法

作答時需明確針對題目兩大問（「What is DMA?」與「How does it help the I/O tasks?」）進行切入：

1. 第一部分：說明「What is DMA?」

   • 定義 DMA 及硬體核心組件 DMA 控制器（DMAC）。
   • 說明傳輸流向：I/O 裝置 <---> DMAC <---> 主記憶體（繞過 CPU）。
   • 說明完整運作流程：
     1. 初始化：CPU 將傳輸指令（讀/寫）、裝置位址、記憶體起始位址及傳輸位元組數寫入 DMAC 的暫存器。
     2. 傳輸中：DMAC 請求匯流排控制權，利用週期竊取（Cycle Stealing）或爆發模式（Burst Mode）在裝置與記憶體間直接傳送資料。
     3. 傳輸完成：DMAC 向 CPU 發送一個中斷訊號（Interrupt Signal），宣告傳輸完畢。

2. 第二部分：說明「How does it help the I/O tasks?」

   • 解放 CPU 運算資源（CPU Offloading）：將繁重的位元組級資料搬移工作交給 DMAC，CPU 在資料傳輸期間可繼續執行其他 CPU-bound 進程（Process），大幅提高系統整體 CPU 利用率。
   • 降低中斷頻率（Reducing Interrupt Overhead）：將中斷觸發單位從「每 Byte 一次」降低為「每 Block（區塊）一次」，極大化減少 Context Switch 及保護/恢復暫存器現場的系統額外負擔（Overhead）。
   • 極大化 I/O 吞吐量（Maximizing I/O Throughput）：對於高速裝置（如 NVMe SSD、千兆/萬兆網卡 NIC、顯示卡），DMA 能充分發揮匯流排頻寬極限，並實現 I/O 傳輸與 CPU 運算高度平行重疊（Overlap）。

---

選項分析

核心觀念

本題旨在考驗作業系統記憶體管理機制中，**單階頁表（One-Level Page Table）**的頁面劃分與頁表項（Page Table Entry, PTE）配置數量的計算。

解題需掌握以下基本定義與公式：

1. 邏輯位址空間劃分：
   若邏輯位址（Logical Address）長度為 $m \text{ bits}$，頁大小（Page Size）為 $2^n \text{ Bytes}$，則：

   • 頁內偏移量（Page Offset, $d$）：$d = n \text{ bits}$
   • 虛擬頁號（Virtual Page Number, $p$ 或 VPN）：$p = m - n \text{ bits}$
   • 整個系統最大可支援的虛擬頁面總數為 $2^p \text{ 個}$。

2. 行程（Process）所需頁面數：
   大小為 $S$ 的行程，在頁大小為 $P$ 的系統中所占用的頁面數為：
   $\text{頁面數} = \left\lceil \frac{S}{P} \right\rceil$

3. 單階頁表的配置機制：
   在單階頁表架構下，作業系統通常搭配**頁表長度暫存器（Page-Table Length Register, PTLR）**記錄行程頁表的大小。當行程占用連續的邏輯位址空間時，OS 僅需為該行程實際使用（或涵蓋的最大虛擬頁號）配置對應數量的頁表項；若為支援全範圍直接索引的靜態頁表陣列，則需配置涵蓋整體位址空間的頁表項。

---

解題方法

步驟一：計算虛擬頁號（VPN）位元數與全空間頁數

• 邏輯位址長度 $m = 36 \text{ bits}$。
• 頁大小 $P = 8\text{ KB} = 8 \times 1024 \text{ Bytes} = 8192 \text{ Bytes} = 2^{13} \text{ Bytes}$。
• 頁內偏移量位元數 $d = 13 \text{ bits}$。
• 虛擬頁號位元數 $p = 36 - 13 = 23 \text{ bits}$。
• 系統最大邏輯位址空間涵蓋 $2^{23} = 8,388,608 \text{ 個頁面}$。

步驟二：計算 $116\text{ MB}$ 行程實際占用的頁面數

• 行程大小 $S = 116\text{ MB} = 116 \times 2^{20} \text{ Bytes}$。
• 頁大小 $P = 8\text{ KB} = 8 \times 2^{10} \text{ Bytes}$。
• 行程所需頁面數量 $N$ 為：

核心觀念

本題考查 Linux 核心之**頁面置換機制（Page Replacement Mechanism）與記憶體回收（Page Reclaim）**策略。

1. 傳統 LRU 之困境與掃描污染（Scan Resistance）：
   • 完美的 LRU（Least Recently Used）演算法需要在每次記憶體存取時更新鏈表指標或時間戳記，開銷極高，不適用於現代作業系統。
   • 傳統 1-bit 二次機會演算法（Clock / Second-Chance Algorithm）在面對「大型檔案順序讀取（Sequential Scan）」時，大量只讀取一次的頁面會沖刷掉原先高頻率存取的頁面，造成頁面快取污染（Page Cache Pollution）。
2. Linux 雙鏈表 LRU 近似演算法（Two-List LRU Strategy）：
   • Linux 採用雙雙向鏈表機制，將頁面分為 活躍鏈表（active_list） 與 不活躍鏈表（inactive_list）。
   • 配合頁面結構體（struct page）中的兩個核心狀態標誌（Flags）：
     • PG_active：標示頁面位於 active_list ($1$) 或 inactive_list ($0$)。
     • PG_referenced：標示頁面在不活躍期間或滑動過程是否被存取過。
   • 此機制以極低負載達成 LRU 近似，並具備**掃描抵抗（Scan Resistance）**能力。

---

解題方法

1. 雙鏈表架構圖（Sketch）

                     [ 新頁面配給 (New Page Allocation) ]
                                      │
                                      ▼ (插入至 Head, PG_active=0, PG_referenced=0)
                            ┌───────────────────┐
      ┌────────────────────>│   inactive_list   │
      │  降級 (Demotion)    │   (PG_active = 0) │
      │  PG_active 1 -> 0   └─────────┬─────────┘
      │                               │
   (Head)                           (Tail)
    [P] <═══> [P] <═══> [P] <═══>    [P] ───────► [ 挑選為受害者頁面 (Victim) ]
     ▲                                                │ (回收 / 寫回磁碟)
     │                                                ▼
     │ 升級 (Promotion)                          [ 記憶體釋放 (Freed) ]
     │ (二次存取: PG_referenced = 1)
     │
┌────┴──────────────┐
│    active_list    │
│   (PG_active = 1) │
└─────────┬─────────┘
        (Tail) ───────► 觸發平衡掃描 (Rebalance Scan)

2. 核心運作機制說明（Mechanism Explanation）

1. 新頁面分配（Page Allocation）：

   • 當系統讀取新頁面時，預設將其插入至 inactive_list 的頭部（Head），並設定標誌位元為：
     $\text{PG\_active} = 0, \quad \text{PG\_referenced} = 0$
   • 設計目的：只存取一次的大檔案頁面（例如順序讀取大檔）會停留在 inactive_list 並直接從 Tail 被淘汰，不會沖刷掉 active_list 中的熱頁面，達到掃描抵抗。

2. 頁面升級（Promotion: Inactive $\to$ Active）：

   • 當位於 inactive_list 中的頁面被存取時：
     • 若原先 $\text{PG\_referenced} = 0$，則設定 $\text{PG\_referenced} = 1$。
     • 若再次被存取且發現 $\text{PG\_referenced} = 1$，則觸發升級：將頁面從 inactive_list 移除，移動至 active_list 的頭部（Head），並更新標誌位元為：
       $\text{PG\_active} = 1, \quad \text{PG\_referenced} = 0$

3. 頁面降級與平衡（Demotion & Rebalancing: Active $\to$ Inactive）：

   • 當 inactive_list 的頁面數量低於系統門檻值（Watermark），或系統發生記憶體壓力時，核心（kswapd）會掃描 active_list 的尾部（Tail）：
     • 若尾部頁面的 $\text{PG\_referenced} = 0$（代表近期未被存取），將其降級並移動至 inactive_list 的頭部（Head），更新為：
       $\text{PG\_active} = 0, \quad \text{PG\_referenced} = 0$