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

(1)

• 核心觀念：作業系統架構（OS Structures）、微核心（Microkernel）定義、自旋鎖（Spin Lock）機制與即時排程（EDF Scheduling）。
• 解題方法：檢視各項描述是否符合作業系統經典理論教材（如 Silberschatz OS Concepts）之標準定義。敘述 (a) 將「微核心 (Microkernel)」的定義誤植為「微服務 (Microservice)」，故為錯誤選項。
• 選項分析：
  • (a) 錯誤：將非核心組件由 Kernel 移至 User Space 實現的架構稱為微核心（Microkernel），而非微服務（Microservice）。微服務屬於軟體應用系統的系統架構範疇。
  • (b) 正確：微核心設計目標為提供最極簡化（Minimal）的處理器管理、記憶體管理與處理器間通訊（IPC）機制。
  • (c) 正確：自旋鎖（Spin Lock）是一種忙碌等待（Busy-waiting）的鎖定機制，當進程無法取得臨界區鎖定時，會在呼叫處持續執行迴圈檢查。
  • (d) 正確：EDF（Earliest Deadline First）排程依據截止時間決定優先權，截止時間（Deadline）越早，優先權越高。
• 解題技巧：注意名詞混淆陷阱，「Microkernel」與「Microservice」字首相同但層級不同，前者為作業系統核心架構，後者為分散式應用系統架構。

【答案】(a)

---

(2)

• 核心觀念：系統啟動流程（System Booting）、引導載入程式（Bootstrap Loader/Boot Manager）與儲存層級結構。
• 解題方法：電腦開機時，韌體（ROM/NVRAM 中的 BIOS/UEFI）執行 Bootstrap Loader，由次級儲存裝置（Storage，如硬碟或固態硬碟）中搜尋作業系統核心（OS Kernel），並將其載入至主記憶體（RAM/Memory）中開始執行。
• 選項分析：
  • (a) 錯誤：作業系統核心儲存於次級儲存裝置（Storage），而非固定存放於 ROM 中。
  • (b) 錯誤：方向顛倒，開機是將 OS 從 Storage 載入至 Memory，而非從 Memory 載入至 Storage。
  • (c) 正確：精確描述系統開機過程——電腦從儲存裝置（Storage）中尋找作業系統並載入至主記憶體（Memory）執行。
  • (d) 錯誤：ROM 中存放的是 Bootstrap Loader / Boot Manager 的初始化碼，但 Boot Manager 本身的作用是去 Storage 找 OS 載入 RAM，本選項並未提及 OS 載入的主體。
• 解題技巧：牢記開機核心動作：「ROM 執行 Bootstrap Loader $\rightarrow$ 從 Storage 尋找 OS $\rightarrow$ 載入 RAM 執行」。

【答案】(c)

---

(3)

• 核心觀念：虛擬記憶體（Virtual Memory）之實現機制。
• 解題方法：虛擬記憶體的實現旨在將邏輯位址空間與實體位址空間分離，經典的實現機制包括請求分頁（Demand Paging）、請求分段（Demand Segmentation）以及兩者結合的分段分頁制（Segmentation with Paging）。
• 選項分析：
  • (a) 正確但不完整：分頁（Paging）可搭配 Demand Paging 機制實現虛擬記憶體。
  • (b) 正確但不完整：分段（Segmentation）可搭配 Demand Segmentation 機制實現虛擬記憶體。
  • (c) 正確但不完整：分段結合分頁（Segmentation with Paging）亦可實現虛擬記憶體。
  • (d) 正確：上述三種記憶體管理機制均可用於實現虛擬記憶體。
• 解題技巧：題目詢問「何者可用於實現」，由於 Paging、Segmentation 與 Hybrid 方案均在虛擬記憶體發展史中被提出過，故應選擇涵蓋全部的 (d)。

【答案】(d)

---

(4)

• 核心觀念：多工（Multitasking）與分時系統（Time-Sharing System）之演進定義。
• 解題方法：根據作業系統發展史，分時系統（Time-Sharing）即為多工（Multitasking）支援多使用者（Multiple-User）互動式操作的延伸版本，利用 CPU 快速切換（Multiplexing）讓多個使用者感覺同時獨佔電腦資源。
• 選項分析：
  • (a) 錯誤：Multiprogramming（多道程式設計）旨在保持 CPU 忙碌（提高利用率），早期多為單使用者批次處理系統。
  • (b) 錯誤：Multiprocessing（多處理系統）指硬體配備多個 CPU/Core 進行平行運算。
  • (c) 正確：Time-Sharing（分時系統）正是多使用者版本的 Multitasking（多工系統）。
  • (d) 錯誤：Multi-user tasking 為非標準作業系統專有名詞。
• 解題技巧：記住定義對應：「Multiprogramming（提高 CPU 利用率） $\rightarrow$ Multitasking/Time-Sharing（提供多使用者互動回應）」。

【答案】(c)

---

(5)

• 核心觀念：多使用者環境下程式併發執行（Concurrent Execution）之系統類型。
• 解題方法：在多使用者（Multi-user）系統中，能透過 CPU 資源時間交錯切換，達到多個使用者之多個程式同時（Concurrent）處於執行狀態的機制即為分時系統（Time-sharing）。
• 選項分析：
  • (a) 錯誤：Multiprogramming 僅代表記憶體中同時載入多個程式輪流使用 CPU，不必然具備多使用者互動性。
  • (b) 錯誤：Multiprocesssing 著重於硬體具備多顆處理器進行平行（Parallel）執行。
  • (c) 正確：Time-sharing（分時系統）專指在多使用者系統中，同時併發（Concurrent）執行多個使用者程式。
  • (d) 錯誤：Multi-user tasking 非標準 OS 名詞。
• 解題技巧：關鍵字為「multi-user system」加上「concurrent execution」，此為 Time-Sharing 的典型教科書定義。

【答案】(c)

---

(6)

• 核心觀念：CPU 排程演算法與飢餓現象（Starvation / Indefinite Blocking）。
• 解題方法：飢餓現象指低優先權或長執行時間的進程，因高優先權或短執行時間進程持續進入佇列，導致長期無法獲得 CPU 執行。檢視各排程演算法的派發特性即可判斷。
• 選項分析：
  • (a) 錯誤：FCFS（First-Come, First-Served）為先進先出佇列，雖然可能產生護衛效應（Convoy Effect），但每個進程最終定能執行，不會產生飢餓。
  • (b) 正確：SJF（Shortest Job First）優先執行 CPU burst 最短的進程。若短任務源源不絕地到達，長任務將永遠無法被執行，會造成飢餓。
  • (c) 錯誤：Round-Robin（RR）採用時間片（Time Quantum）循環派發，每個進程在一定時間內必定能獲得 CPU 執行，不會產生飢餓。
  • (d) 錯誤：因 (b) 會造成飢餓，故此項錯誤。
• 解題技巧：具備「優先權排程」性質的演算法（如 SJF、Priority Scheduling）若無引進老化（Aging）機制，均存在飢餓風險。

【答案】(b)

---

(7)

• 核心觀念：進程狀態轉移圖（Process State Transition Diagram）。
• 解題方法：標準五狀態進程模型包括：New、Ready、Running、Waiting、Terminated。進程必須先進入 Ready Queue 經由 Scheduler Dispatch 才能取得 CPU 進入 Running 狀態；正在執行的進程若等待 I/O 或事件會進入 Waiting，I/O 完成後必須先回到 Ready 佇列，不能直接跳回 Running。
• 選項分析：
  • (a) 正確轉移：Running $\rightarrow$ Waiting（執行中進程因請求 I/O 或等待事件進入等待狀態）。
  • (b) 不正確轉移：Waiting $\rightarrow$ Running（等待事件完成後，必須先回到 Ready 狀態等待排程，不可直接轉為 Running）。
  • (c) 正確轉移：Waiting $\rightarrow$ Ready（I/O 或事件完成後，進程轉回就緒狀態等待 CPU）。
  • (d) 正確轉移：Ready $\rightarrow$ Running（CPU 排程器選定並派發 CPU 給就緒進程）。
• 解題技巧：牢記狀態轉移鐵律：「任何進入 Running 狀態的進程，唯一入口只有 Ready 狀態（透過 Dispatcher）。」

【答案】(b)

---

(8)

• 核心觀念：磁碟陣列（RAID）架構與容錯能力（Fault Tolerance）。
• 解題方法：比較各 RAID 層級在面對硬體磁碟損壞時的資料保護與恢復能力。無任何備份或同位素（Parity）保護機制者，容錯能力最差。
• 選項分析：
  • (a) 錯誤：RAID 1 為鏡像（Mirroring），資料百分之百複製，可承受至少 1 顆磁碟損壞，容錯能力高。
  • (b) 正確：RAID 0 為資料條帶化（Striping），完全無資料冗餘與同位檢查。只要陣列中任意 1 顆磁碟損毀，全部資料即告遺失，容錯能力最差（容錯度為 0）。
  • (c) 錯誤：RAID 5 具備分散式同位元（Distributed Parity），可承受任意 1 顆磁碟損壞而不遺失資料。
  • (d) 錯誤：RAID 0+1 為先 Striping 再 Mirroring，具備鏡像保護，容錯能力遠優於 RAID 0。
• 解題技巧：RAID 0 唯一的優點是讀寫效能與儲存空間利用率最大化（100%），代價是容錯能力為零。

【答案】(b)

---

(9)

• 核心觀念：硬即時系統（Hard Real-Time System）與軟即時系統（Soft Real-Time System）之差異。
• 解題方法：即時系統（Real-Time System）均強調任務的時間約束（Deadline）。硬即時與軟即時的根本界線在於「若錯過 Deadline（Missed Deadline）所產生的後果嚴重度」。
• 選項分析：
  • (a) 錯誤：無論是 Hard 還是 Soft Real-Time 系統，每個任務皆具有截止時間（Deadline）。
  • (b) 錯誤：兩者皆需要依據 Deadline 進行排程（如 EDF）。
  • (c) 正確：在 Hard Real-Time 系統中，未能在 Deadline 前完成任務將導致整個系統的致命失敗（Failure）；而 Soft Real-Time 系統錯過 Deadline 僅會造成服務品質（QoS）下降（例如影片掉幀），系統不會因此崩潰。

核心觀念

本題考驗作業系統（Operating System）中**分頁機制（Paging Mechanism）與多層頁表（Multi-level Paging）**的頁表記憶體空間開銷計算。關鍵觀念與相關公式如下：

1. 位址劃分（Address Partitioning）：

   • 虛擬位址長度為 $m$ bits，定址空間大小為 $2^m$ bytes。
   • 頁面大小（Page Size）為 $P = 2^n$ bytes，則頁內偏移量（Page Offset）占 $n$ bits。
   • 虛擬頁號（Virtual Page Number, VPN）占 $m - n$ bits，全域虛擬頁面總數為 $2^{m-n}$ 個。

2. 單一頁面頁表容量（Entries per Page Table Page）：

   • 若一個頁表項（Page Table Entry, PTE）大小為 $e$ bytes，則單一頁面大小的頁表最多可容納的 PTE 數量為：
     $\text{Entries per Page} = \frac{\text{Page Size}}{\text{PTE Size}} = \frac{2^n}{e}$

3. 單層頁表（One-level Paging）開銷：

   • 單層頁表為連續陣列結構，必須涵蓋整個虛擬位址空間的所有虛擬頁號（包含未使用的區域），因此 PTE 總數固定為 $2^{m-n}$ 個。

4. 兩層頁表（Two-level Paging）開銷：

   • 將 VPN 拆分為外層頁表索引（Outer Page Table Index, $p_1$）與內層頁表索引（Inner Page Table Index, $p_2$）。
   • 外層頁表（Outer Page Table / Page Directory）必須隨時存在，占用固定數量的頁面。
   • 內層頁表（Inner Page Table）採動態配置，僅當進程（Process）實際使用到對應的虛擬記憶體區段時，作業系統才會為該區段配置內層頁表頁面。

---

解題方法

基本參數計算

• 虛擬位址長度：$32\text{ bits}$，總虛擬記憶體空間 $2^{32}\text{ bytes} = 4\text{ GB}$。
• 頁面大小（Page Size）：$4\text{ KB} = 4 \times 1024\text{ bytes} = 2^{12}\text{ bytes}$。
  • 頁內偏移量（Offset）位元數：$\log_2(2^{12}) = 12\text{ bits}$。
  • 虛擬頁號（VPN）位元數：$32 - 12 = 20\text{ bits}$。
• 頁表項大小（PTE Size）：$4\text{ bytes} = 2^2\text{ bytes}$。
• 單一頁面可容納的 PTE 數量：
  $\frac{4\text{ KB}}{4\text{ bytes}} = \frac{4096}{4} = 1024 = 2^{10}\text{ 個}$
• 進程大小（Process Size）：$12\text{ MB} = 12 \times 1024\text{ KB}$。
  • 該進程實際佔用的虛擬頁面數量：
    $\text{Process Pages} = \frac{12\text{ MB}}{4\text{ KB}} = \frac{12 \times 1024\text{ KB}}{4\text{ KB}} = 3000\text{ 個頁面}$

---

選項分析

(1) 單層頁表（One-level Paging）

• 機制分析：單層頁表採用線性索引陣列，必須為 $32\text{ bits}$ 定址空間中的每一個潛在虛擬頁號建立 PTE。

核心觀念

本題測試作業系統（Operating Systems）五個關鍵核心概念的定義、運作機制與應用情境，涵蓋：

1. 核心介面與特權保護：使用者空間與核心空間的互動通道（System call）。
2. 記憶體管理與效能瓶頸：虛擬分頁系統中因過度 Swap 導致效能劇降的現象（Thrashing）。
3. 處理器調度與狀態管理：處理器執行狀態保存與恢復的純系統開銷過程（Context switch）。
4. 資訊安全與信任模型：維護系統安全性防線的最小硬體/韌體/軟體集合（TCB - Trusted Computer Base）。
5. 系統虛擬化技術：管理與隔離客體作業系統的虛擬機器監控程式（Hypervisor）。

---

解題方法

名詞解釋題在研究所考試中應採用結構化答題法，針對每個名詞提供：

1. 精確定義：一句話點出該名詞的核心身分與功能。
2. 運作機制與技術細節：說明其涉及的硬/軟體狀態轉換、資料結構或關鍵元件。
3. 系統影響或應用分類：補充其開銷分析、極限情境或架構分類（如 Type-1/Type-2、PCB/TCB 保存等）。

以下針對各子題提供滿分標準答題內容：

---

各名詞精確詳解

(1) System call（系統呼叫）

• 精確定義：系統呼叫是作業系統核心（Kernel）提供給使用者空間（User Space）應用程式的程式化介面（API），允許應用程式請求執行特權操作或存取受保護的硬體資源。
• 運作機制：
  1. 模式切換：應用程式執行特殊指令（如 x86 的 syscall / int 0x80）引發軟體中斷（Software Interrupt）或陷阱（Trap）。
  2. 保護級別轉換：CPU 控制權由使用者模式（User Mode / Ring 3）切換至核心模式（Kernel Mode / Ring 0）。
  3. 查表執行：系統根據系統呼叫號碼（System Call Number）查閱系統呼叫表（System Call Table），跳轉至對應的核心服務常式（Kernel Service Routine）執行任務（如檔案 I/O、行程建立等）。
  4. 結果傳回：執行完畢後，將傳回值放入指定暫存器，並將 CPU 模式恢復為使用者模式。
• 主要類別：行程控制（Process Control）、檔案管理（File Management）、裝置管理（Device Management）、資訊維護（Information Maintenance）、通訊（Communication）與保護（Protection）。

(2) Thrashing（顛簸 / 劇烈分頁）

• 精確定義：在虛擬記憶體（Virtual Memory）系統中，當系統忙於處理分頁換入/換出（Page In / Page Out）的時間遠大於實際執行 CPU 指令的時間時，所發生的系統效能嚴重崩潰現象。
• 觸發過程與機制：
  1. 若多重程式設計程度（Degree of Multiprogramming, DOM）過高，分配給每個行程的頁框數（Frames）不足以容納其目前執行的工作集（Working Set）。
  2. 各行程頻繁產生缺頁（Page Fault），導致磁碟 I/O 隊列充斥分頁請求。
  3. 磁碟 I/O 阻塞使 CPU 利用率（CPU Utilization）驟降，作業系統的排程器誤判為系統負載不足，進一步引進更多行程（增加 DOM）。
  4. 實體記憶體競爭更趨劇烈，最終使系統幾乎無法進行任何實質運算。
• 數學條件與解決方案：
  • 當各行程工作集大小總和超過實體頁框總數，即 $\sum WSS_i > \text{Total Available Frames}$ 時爆發。
  • 解決方案：採用工作集模型（Working Set Model）動態控制 DOM；或使用分頁錯誤率（Page-Fault Frequency, PFF）策略適時暫停（Suspend）部分行程。

(3) Context switch（內文切換 / 上下文切換）

• 精確定義：當 CPU 控制權從目前執行的行程/執行緒轉移給另一個行程/執行緒時，作業系統保存舊行程的執行狀態（Context），並載入新行程先前保存之狀態的過程。
• 保存與載入內容：
  • 暫存器內容（通用暫存器、程式計數器 PC、堆疊指標 SP 等）。
  • 記憶體管理資訊（如頁表指標 Page Table Pointer / CR3 暫存器）。
  • 狀態儲存於軟體資料結構中：行程切換儲存於 PCB（Process Control Block）；執行緒切換儲存於 TCB（Thread Control Block）。
• 開銷與影響：
  • 純系統額外負擔（Pure Overhead）：切換期間 CPU 未執行任何使用者有效指令。

核心觀念

1. 中間人攻擊（Man-in-the-Middle Attack, MITM）定義：
   中間人攻擊是一種網路安全與作業系統網路通訊層面的攻擊模式。攻擊者（Attacker / Mallory）秘密地位於通訊雙方（如客戶端 Client / Alice 與伺服器 Server / Bob）之間，成功攔截並掌控雙方的通訊管道。攻擊者不僅能主動**竊聽（Eavesdrop）傳輸的私密資料，還能篡改（Alter / Inject）傳輸內容或偽造（Spoof）**身份，而通訊雙方卻誤以為彼此正在進行直接且安全的連線。

2. 核心問題與威脅分析：

   • 根本原因：通訊雙方在建立連線或交換金鑰時缺乏有效的身份鑑別機制（Lack of Authentication）。
   • 資安三要素破壞：
     • 機密性（Confidentiality）：攻擊者可解密並讀取敏感資訊（如密碼、信用卡號、Session Token）。
     • 完整性（Integrity）：攻擊者可隨意修改傳輸封包的內容。
     • 身份鑑別性（Authentication）：攻擊者可雙向偽裝成通訊對方。

---

解題方法

本題為「名詞解釋與圖解題」，解題關鍵在於繪製清晰的網路通訊對比圖（正常通訊 vs. MITM 攻擊路徑），並分階段說明攻擊運作流程與防禦機制。

1. 攻擊架構圖解（Diagram）

(a) 正常通訊狀況（Expected Communication）：

+------------------+     Direct & Secure Link      +------------------+
|  客戶端 (Client)  | <--------------------------> |  伺服器 (Server)  |
+------------------+                               +------------------+

(b) 中間人攻擊狀況（MITM Attack Scenario）：

                    +-------------------+
                    |   攻擊者 (MITM)   |
                    | (Attacker / Eve)  |
                    +-------------------+
                       ^             ^
     偽裝成 Server     |             | 偽裝成 Client
     (Intercept/Alter) |             | (Intercept/Alter)
                       v             v
+------------------+                     +------------------+
|  客戶端 (Client)  |                     |  伺服器 (Server)  |
|  (以為連到 Server)|                     |  (以為連到 Client)|
+------------------+                     +------------------+

2. MITM 攻擊運作四階段推導：

1. 連線攔截（Interception）：
   攻擊者透過網路層／資料鏈結層漏洞（例如 ARP 毒化/欺騙 (ARP Spoofing)、DNS 欺騙 (DNS Spoofing) 或建立偽造 Wi-Fi 熱點 (Rogue AP)），將客戶端導向伺服器的封包強制重導向（Reroute）至攻擊者的設備。
2. 金鑰劫持與雙向建立（Key Exchange Interception）：
   在未經身分驗證的 Diffie-Hellman 金鑰交換或未驗證憑證的 TLS 握手過程中：
   • 攻擊者截獲 Client 的公鑰 request，生成攻擊者的公鑰 $PK_A$ 傳給 Client。
   • 攻擊者另向 Server 發起連線，生成攻擊者的公鑰 $PK_B$ 傳給 Server。
   • Client 與 Server 分別與攻擊者建立了獨立的加密通道（通道 1: Client $\leftrightarrow$ MITM；通道 2: MITM $\leftrightarrow$ Server）。
3. 竊聽與數據篡改（Eavesdropping & Tampering）：
   • 當 Client 傳送加密資料時，MITM 用與 Client 共享的金鑰解密取得明文（竊聽）。
   • MITM 視需要篡改明文內容後，再用與 Server 共享的金鑰加密並傳送給 Server。

核心觀念

本題旨在考驗作業系統中**使用二元號誌（Binary Semaphore）實作記錄號誌（Counting Semaphore）**的經典同步問題，核心觀念包含：

1. 二元號誌與記錄號誌之定義：
   • 二元號誌（Binary Semaphore）：數值僅能為 $0$ 或 $1$，常用於實現臨界區段（Critical Section）之互斥控制（Mutual Exclusion）。
   • 記錄號誌（Counting Semaphore）：允許數值為任意整數 $C$，用於管理有限數量的同質資源。
2. 臨界區段保護與等待佇列分工：
   • $S_1$（初始值 $1$）：作為保護共享變數 $C$ 存取與修改的互斥鎖。
   • $S_2$（初始值 $0$）：作為資源不足時，將行程阻塞（Sleep）與喚醒（Wakeup）的等待佇列號誌。
3. 避免死鎖（Deadlock Avoidance）與原子性：
   • 行程在因資源不足而進入阻塞狀態（執行 wait(S2)）前，必須先釋放互斥鎖 $S_1$。否則其他行程將無法進入 wait 或 signal 操作，導致系統陷入死鎖。

---

解題方法

分析題目所給予的 wait 與 signal 演算法，可發現其中存在 3 個主要問題：

1. 死鎖問題（Deadlock in wait operation）

• 問題分析：在 wait 操作中，當 $C \le 0$ 時，行程在已取得互斥鎖 $S_1$ 的狀態下直接執行 wait(S2)。
• 推導過程：
  由於 $S_1$ 被當前行程佔用（$S_1 = 0$），任何其他行程若欲呼叫 wait 或 signal，都會被卡在開頭的 wait(S1)。這導致沒有任何行程能夠執行到 signal 操作中的 signal(S2) 來喚醒被阻塞的行程，最終引發死鎖（Deadlock）。
• 修正方法：在呼叫 wait(S2) 阻塞之前，必須先執行 signal(S1) 釋放互斥鎖。

2. wait 判斷條件錯誤（Erroneous Condition in wait）

• 問題分析：原程式碼寫為 if (C <= 0) wait(S2);。
• 推導過程：
  假設當前可用資源數 $C = 1$，行程執行 C-- 後 $C$ 變為 $0$。$C = 0$ 代表該行程成功取得最後一份可用資源，此時資源剛好分配完畢，行程不應該被阻塞。然而原條件 C <= 0 在 $C = 0$ 時判定為真（True），導致行程錯誤地執行 wait(S2) 被阻塞。
• 修正方法：將判斷條件修正為 if (C < 0)。當 $C < 0$ 時，才代表資源不足而需要阻塞。

3. signal 判斷條件錯誤（Erroneous Condition in signal）

• 問題分析：原程式碼寫為 if (C < 0) { signal(S2); }。
• 推導過程：
  假設當前有 $1$ 個行程正在等待資源（此時 $C = -1$）。當另一個行程歸還資源執行 C++ 後，$C$ 變為 $0$。此時 $C = 0$ 表示剛好有一位等待者需要被喚醒。然而原條件 if (C < 0) 在 $C = 0$ 時判定為假（False，$0 < 0$ 為假），導致 signal(S2) 未被執行，原本被阻塞的行程將永遠無法被喚醒（無窮等待）。
• 修正方法：將判斷條件修正為 if (C <= 0)。只要 $C \le 0$，就代表先前有行程在等待資源，必須呼叫 signal(S2) 喚醒一個佇列中的行程。

---

選項分析

本題為程式片段除錯題，以下針對原程式碼的 wait 與 signal 各行敘述進行逐項檢驗：

1. wait 操作片段分析

• wait(S1);：正確。用於取得互斥鎖，保護共享計數器 $C$。
• C--;：正確。