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

第 1. 題 (1)

核心觀念

**動態載入（Dynamic Loading）與動態連結（Dynamic Linking）**是記憶體管理中用於優化資源利用與程式彈性的兩大技術：

1. 動態載入（Dynamic Loading）：程式的常式（Routine）在被呼叫前不會被載入至記憶體。其主要目的為避免載入極少使用的程式碼（如例外處理常式或特定選單）。主要由程式設計師透過程式碼與函式庫呼叫實現，不需要作業系統提供額外的特殊支援。
2. 動態連結（Dynamic Linking）：將連結（Linking）延遲至程式執行階段。程式檔中僅包含存根（Stub），執行時由作業系統的動態連結器（Dynamic Linker/Loader，如 Windows 的 DLL 或 Linux 的 .so）定位並載入共享函式庫，主要效益在於避免記憶體中出現重複的程式碼（Prevent Duplicated Code）。

解題方法

對比動態載入與動態連結在「作業系統支援度」、「執行階段行為」及「設計效益」的定義，逐一檢驗各選項敘述。

選項分析

• (a) 正確：根據 Silberschatz《Operating System Concepts》經典教科書，動態載入的實現主要依賴程式設計師妥善設計程式結構並透過 API 呼叫，作業系統只需提供基礎的記憶體分配與載入函式，不需要作業系統額外提供特殊的硬體或核心機制支援。
• (b) 錯誤：描述的是「動態載入（Dynamic Loading）」而非動態連結。動態載入是在需要某段程式碼時才將其載入記憶體；動態連結則是在程式執行呼叫函式時，將共享函式庫連結至程序的位址空間。
• (c) 錯誤：此描述為「動態載入（Dynamic Loading）」的核心優勢。當程式包含大量極少使用的程式碼（如錯誤處理子程式）時，動態載入可顯著節省記憶體空間。
• (d) 錯誤：防止重複程式碼（Prevent Duplicated Code / Shared Libraries）是「動態連結（Dynamic Linking）」的核心優勢，因為多個不同的程序可以共用記憶體中同一份共享函式庫程式碼。動態載入無法跨程序共享程式碼。

解題技巧

口訣快速判斷：

• Dynamic Loading $\rightarrow$ 「用到了才載入」（不需 OS 特殊支援，適用於罕見程式碼以節省記憶體）。
• Dynamic Linking $\rightarrow$ 「跨程序共用函式庫」（需 OS 動態連結器支援，防止記憶體中存在重複程式碼）。

【答案】(a)

---

第 1. 題 (2)

核心觀念

Windows 作業系統在管理程序（Process）與執行緒（Thread）時，分別在使用者空間（User Mode）與核心空間（Kernel Mode）維護特定的內部資料結構：

1. TEB（Thread Environment Block）：存在於使用者空間，儲存與單一執行緒相關的使用者模式資訊，包含**執行緒區域儲存（Thread Local Storage, TLS）**陣列、堆疊邊界（Stack Limits）、例外處理鏈（SEH Frame）及 TEB 自我參考指標等。
2. PEB（Process Environment Block）：存在於使用者空間，儲存與整個程序相關的資訊（如已載入的模組列表、程序堆疊、命令列參數等）。
3. KTHREAD（Kernel Thread）：存在於核心空間，為 NT 核心調度器的核心執行緒控制區塊，包含執行緒狀態、排程優先級、核心堆疊與同步物件等。
4. ETHREAD（Executive Thread）：存在於核心空間，包裹了 KTHREAD，並包含執行緒 ID、所屬程序指標（EPROCESS）、I/O 資訊等高階核心管理資料。

解題方法

根據題目要求找出「執行緒區域變數（Thread Local variables / TLS）」的儲存位置。該資料屬於使用者模式下個別執行緒的私有資料，對應 Windows 的使用者模式執行緒控制結構 TEB。

選項分析

• (a) 正確：TEB（Thread Environment Block）包含 TLS 陣列（Thread Local Storage Array），用於存取與管理執行緒區域變數。
• (b) 錯誤：PEB（Process Environment Block）屬於程序等級（Process-level）的資料結構，維護整個程序共用的資源與狀態，而非單一執行緒的區域變數。
• (c) 錯誤：KTHREAD（Kernel Thread Block）位於核心模式，專門負責執行緒的低階排程與硬體 Context 切換，不儲存使用者模式的 Thread Local 變數。
• (d) 錯誤：ETHREAD（Executive Thread Block）位於核心模式，屬於高階核心物件，管理執行緒生命週期與資源，不直接存取使用者空間的 Thread Local 變數。

解題技巧

區分 Windows 系統資料結構歸屬層級：

• 使用者模式 (User Mode)：PEB（Process 級別）、TEB（Thread 級別，包含 TLS）。
• 核心模式 (Kernel Mode)：EPROCESS / ETHREAD（高階 Executive 物件）、KPROCESS / KTHREAD（低階 Kernel 排程物件）。
  關鍵對應：TLS / Thread Local Variables $\rightarrow$ TEB。

【答案】(a)

---

第 1. 題 (3)

核心觀念

系統軟體層級架構通常分為：

1. 作業系統核心與基礎中介軟體服務（OS Middleware & Services）：系統提供的通用 API 與框架服務，提供應用程式開發所需的核心基礎功能，如執行緒服務（Threading）、圖形繪製與視窗服務（Graphics / GUI System）、多媒體處理解碼服務（Multimedia Services）及網路通訊服務。
2. 應用層服務（Application-level Services）：建立在作業系統之上，由獨立軟體廠商或應用程式提供的專業服務，例如資料庫管理系統（Database Management System, DBMS）。

解題方法

分析各項服務在作業系統層級中的角色，辨識何者屬於應用層軟體（Application/Server Level）而非 OS 隨附提供的標準中介軟體服務。

選項分析

• (a) 錯誤（屬於 OS Middleware）：執行緒服務（Threading service，如 POSIX Pthreads、Win32 Threads API）為 OS 提供程序與執行緒控管的標準中介軟體 API。
• (b) 正確（不屬於 OS Middleware）：資料庫服務（Database service，如 Oracle、MySQL、PostgreSQL、MS SQL）屬於獨立的應用層服務軟體（Database System），並非作業系統原生提供的中介軟體層服務。
• (c) 錯誤（屬於 OS Middleware）：圖形服務（Graphics service，如 DirectX、OpenGL/Vulkan 框架、Win32 GDI、X11/Wayland）是 OS 提供的標準圖形與 GUI 中介軟體。
• (d) 錯誤（屬於 OS Middleware）：多媒體服務（Multimedia service，如 DirectShow、CoreAudio、Android Stagefright）是 OS 提供的標準音視訊處理與播放中介軟體。

解題技巧

劃分服務邊界：OS 中介軟體負責提供「系統基礎建設」（Threading, Graphics, Sound, Network sockets），而大型特定業務邏輯軟體（如 Database E

核心觀念

本題旨在考驗作業系統在硬體保護機制（Hardware Protection Mechanisms）與系統架構上的基礎概念，涵蓋以下核心重點：

1. 雙重模式運作（Dual-Mode Operation）：作業系統藉由硬體提供的 Mode Bit（模式位元）區分 Kernel Mode（核心模式／特權模式）與 User Mode（使用者模式），用以隔離保護系統資源。
2. 特權指令（Privileged Instructions）：可能損害系統或影響其他程式執行的指令（如直接存取 I/O、修改記憶體保護暫存器、關閉中斷等），規定只能在 Kernel Mode 下執行。
3. PSW（Program Status Word，程式狀態字元）：CPU 內部存放執行狀態與控制旗標的暫存器（Register），包含條件碼（Condition Code）、中斷啟用旗標（Interrupt Enable Bit）以及模式位元（Mode Bit）等資訊。
4. 虛擬化（Virtualization, VM & VMM）：VMM（Virtual Machine Monitor / Hypervisor）的介入打破了傳統單一 OS 對雙模式的直接控制，衍生出額外的特權層級（如 Root / Non-root Mode 或 Ring $-1$），會干涉並複雜化傳統多重模式的運作。

---

解題方法

本題為觀念判斷型選擇題，解題切入點為精確釐清作業系統與 CPU 硬體專有名詞的定義與角色：

1. 檢視保護機制的運作規範（特權指令的執行權限、雙重模式的保護目的）。
2. 辨析硬體元件的屬性（判斷 PSW 屬於暫存器還是控制器）。
3. 評估虛擬化技術對 OS 多模式機制的影響（VMM 對多重模式的交疊與干擾）。

---

選項分析

• (a) Privileged instructions executed only in kernel mode（敘述正確）

  • 分析：特權指令（Privileged Instructions）包含直接存取硬體 I/O、變更記憶體保護暫存器（如 Base/Limit Registers）、停用中斷（Disable Interrupts）等敏感操作。為維護系統安全，硬體強制規定特權指令只能在 Kernel Mode 下執行。若使用者程式在 User Mode 下企圖執行特權指令，CPU 硬體會立刻觸發 Trap（例外／內部中斷），將控制權交還給作業系統終止該程式。因此本敘述正確。

• (b) PSW is the controller used to support dual mode operations（敘述錯誤）

核心觀念

本題測驗作業系統架構中關於 Apple macOS / iOS 核心（Darwin 與 XNU 核心架構） 的經典觀念，主要包含以下面向：

1. Darwin 作業系統：Apple 所開發的開放原始碼作業系統核心基礎，為 macOS 與 iOS 的底層架構。
2. XNU 混合核心（Hybrid Kernel）：XNU（X is Not Unix）結合了 Mach 微核心（Microkernel）、FreeBSD / BSD 系統介面與 I/O Kit 物件導向驅動程式框架。
3. 微核心 vs. 混合核心（Microkernel vs. Hybrid Kernel）：純微核心（Pure Microkernel）僅保留最基本的服務（如 IPC、記憶體管理與基本排程）於核心空間（Kernel Space），將其他服務（如檔案系統、網路、驅動程式）移至使用者空間（User Space）；而 macOS 的 XNU 為了追求系統效能，將 Mach 與 BSD 組件整合在同一個核心位址空間內執行，屬於混合核心而非純粹的微核心。
4. Mach 訊息傳遞機制（Mach IPC & Copy-on-Write）：Mach 的訊息傳遞透過虛擬記憶體管理技術（如頁面映射重定向與寫入時複製 Copy-on-Write），避免大型訊息在記憶體間進行實體資料複製（Data Copying）。

---

解題方法

解題關鍵在於辨別 macOS 核心（XNU）的實際架構類型：

1. 檢視 macOS / iOS 的歷史與系統架構設計：雖然 Mach 最初設計為微核心，但 Apple 在開發 XNU 時，若將 BSD 服務與驅動程式完全放在使用者空間，會因為頻繁的 IPC（Inter-Process Communication）與上下文切換（Context Switch）導致嚴重的效能瓶頸。
2. 因此，Apple 選擇將 Mach 微核心組件與 BSD 層共同放入核心空間中執行，使 macOS 成為典型的混合核心架構（Hybrid Architecture）。
3. 據此直接判斷「macOS 採用純微核心架構」的敘述為錯誤（False），即為本題所求。

---

選項分析

• (a) Darwin is a layered system that serves as the foundation of Mac OS and iOS（正確）
  Darwin 是 Apple 開發的開放原始碼作業系統，採用分層（Layered）與模組化的設計，包含 Mach 核心、BSD 系統層與驅動程式層，作為 macOS 和 iOS 系統運作的基石。

核心觀念
本題考驗 UNIX/Linux 作業系統中的**行程生命週期（Process Lifecycle）與行程終結（Process Termination）機制，特別是殭屍行程（Zombie Process）與孤兒行程（Orphan Process）**的定義與差異。

在 UNIX 系統中，當一個子行程（Child Process）執行結束（呼叫 exit()）時，作業系統不會立刻將其行程控制區塊（PCB, Process Control Block）與行程表（Process Table）中的條目徹底刪除，而是會保留該子行程的結束狀態碼（Exit Status）與 PID 等資訊。此時，若父行程（Parent Process）尚未呼叫 wait() 或 waitpid() 來讀取其結束狀態碼，該子行程就處於「殭屍（Zombie）」狀態。

---

解題方法
解題切入點在於區分「子行程結束」與「父行程結束／呼叫 wait()」的時間順序：

1. 子行程先結束，父行程尚未 wait() $\rightarrow$ 子行程已釋放記憶體等主要資源，但 PCB 仍留在行程表中等待父行程讀取狀態，此狀態稱為 殭屍行程（Zombie Process）。
2. 父行程先結束，子行程仍在執行 $\rightarrow$ 子行程失去父行程，此狀態稱為 孤兒行程（Orphan Process）。孤兒行程會被 init 行程（PID 1，或系統的 subreaper）收養，並由 init 自動對其呼叫 wait() 以進行善後回收。

題目明確指出「子行程在父行程呼叫 wait() 之前就已結束（A child process ends before the parent calls wait()）」，完

核心觀念

本題考驗作業系統中**行程控制區塊（Process Control Block, PCB）**的基本觀念，以及 Linux 核心實作中的核心資料結構與虛擬檔案系統架構。

1. PCB（Process Control Block）定義與角色：
   PCB 是作業系統核心維護行程（Process）狀態與資源管理的最核心資料結構。每個行程在創建時，核心都會為其分配一個獨立的 PCB，記錄包含行程狀態（Process State）、行程識別碼（PID）、程式計數器（PC）、CPU 暫存器（Registers）、CPU 排程資訊、記憶體管理資訊與開啟檔案表（Open File Table）等上下文。

2. Linux 核心資料結構分工：
   在 Linux 核心中，PCB 的實作即為 struct task_struct（定義於 <linux/sched.h>）。為避免單一結構過於龐大，task_struct 採用模組化設計，內部透過指標指向各子系統的專用資料結構：

   • 行程關係與 CPU 上下文：直接儲存於 task_struct 內部（例如指向父行程的 parent 指標、記錄子行程串列的 children，以及儲存 CPU 暫存器架構狀態的 thread_struct thread）。
   • 記憶體管理資訊：由 struct mm_struct *mm 指向，負責管理該行程的虛擬位址空間（Virtual Address Space）、分頁表（Page Table Directory, pgd）以及各記憶體區段（vm_area_struct，如程式碼段、資料段、堆疊段、堆積段）。
   • 開啟檔案資訊：由 struct files_struct *files 指向，維護開啟檔案描述元表（Open File Descriptor Table）。

3. /proc 虛擬檔案系統（Procfs）：
   /proc 是一個位在使用者空間的虛擬/偽檔案系統（Pseudo Filesystem），不佔用實際硬碟空間。核心動態透過 /proc 檔案介面（例如 /proc/[pid]）將核心內部 PCB（即 task_struct）的資訊導出呈現給使用者空間的工具（如 ps、top）檢視。

---

解題方法

1. 分析 PCB 職責與 Linux 實作細節：
   對照通用作業系統理論與 Linux 核心實作，檢視行程父子階層關係、CPU 暫存器值、開啟檔案指標以及記憶體管理的具體存放位置。
2. 鎖定關鍵資料結構權責（task_struct vs mm_struct）：
   • mm_struct 為 Memory Descriptor，僅專門用於管理記憶體分配與分頁表。
   • 父子關係（parent / children）與 CPU 暫存器狀態（Hardware Context / Registers）屬於行程的控制與執行上下文，直接存放在 task_struct（或其中的 thread_struct），完全不屬於 mm_struct 的管理範疇。
3. 判定各選項之正確性：
   透過理論定義與實體架構的比對，逐一判定選項觀念的精準度與正確性。

---

選項分析

• (a) Each process is associated with a PCB：【正確】
  根據作業系統核心設計原理，核心必須為每一個存在於系統中的行程建立並維護一個專屬的 PCB。行程與 PCB 為一對一對應關係，當行程終止並被回收時，其對應的 PCB 才會被核心釋放。

核心觀念
本題考查**行程狀態轉移（Process State Transitions）與排程佇列（Scheduling Queues）**的關係。
在作業系統（如 Silberschatz 所著之《Operating System Concepts》）的標準模型中，行程在 CPU 上執行（Running 狀態）時，若因故離開 CPU（被換出，Switched out），會根據其離開的原因被置入不同的排程佇列：

1. 就緒佇列（Ready Queue）：存放已準備好執行、僅等待獲取 CPU 執行時間的行程（處於 Ready 狀態）。
2. 等待佇列（Wait Queue / Device Queue）：存放因等待特定外部事件（如 I/O 完成、子行程結束、訊號/中斷觸發）發生而無法繼續執行的行程（處於 Waiting 狀態）。

---

解題方法
切入點為分析行程從 Running 狀態 被換出 CPU 時的狀態轉移方向：

• 若行程是主動請求資源或等待特定事件發生（如 I/O 請求、建立子行程並等待其完成、等待中斷/訊號），該行程在事件發生前無法繼續執行，因此會轉移至 Waiting 狀態，並被加入對應的 Wait Queue 中。
• 若行程是**非自願性因時間片用盡（Time slice expired）**而被搶佔（Preemption），該行程本身不需要等待任何資源或外部事件，隨時具備繼續運算的能力，因此會轉移至 Ready 狀態，並被重新放回 Ready Queue 中等待下一次排程，而非進入 Wait Queue。

---

選項分析

• (a) I/O request（I/O 請求）：不選（會加入 Wait Queue）。行程在執行期間發出 I/O 系統呼叫（如讀寫檔案或網路傳輸），在 I/O 裝置處理完成前無法繼續執行。行程會從 Running 轉移至 Waiting 狀態，並被放入該 I/O 裝置的 Wait Queue（或 Device Queue）中。

核心觀念

本題考查作業系統中**執行緒模型（Multithreading Models）**的分類、映射機制與現代作業系統的實作現狀。

在作業系統中，執行緒分為使用者層級執行緒（User Threads）與核心層級執行緒（Kernel Threads），兩者之間的映射關係主要分為以下三種模型：

1. 多對一模型（Many-to-One Model）：
   • 多個使用者層級執行緒映射至單一核心層級執行緒。
   • 執行緒的管理完全在使用者空間（User Space）由執行緒函式庫處理，作業系統核心無法感知多執行緒的存在。
   • 缺點：若其中一個執行緒發起阻塞式系統呼叫（Blocking System Call），整個行程（Process）都會被阻塞；且無法利用多核心（Multi-core）處理器進行物理上的平行運算（Parallelism）。
2. 一對一模型（One-to-One Model）：
   • 每一個使用者層級執行緒皆映射至一個獨立的核心層級執行緒。
   • 具備高併發性（Concurrency），單一執行緒阻塞不會影響其他執行緒，且能充分利用多核心 CPU 達到真正的平行執行。
   • 缺點：每建立一個使用者執行緒就需要建立一個對應的核心執行緒，會產生較大的系統開銷。
3. 多對多模型（Many-to-Many Model）：
   • 將 $m$ 個使用者層級執行緒多工映射（Multiplex）至 $n$ 個核心層級執行緒（其中 $m \ge n$）。
   • 兼具彈性與資源控制能力，解決了多對一無法平行與一對一開銷過大的問題。

---

解題方法

本題切入點在於檢驗各大作業系統與技術規範所採用的執行緒映射模型：

1. 歷史與特定語言實作：Green Threads 屬於早期 Java VM 的純使用者層級執行緒實作，屬於多對一模型。
2. 現代主流作業系統：檢驗 Linux 與 Windows 的作業系統核心架構。為了滿足現代電腦多核心硬體架構的平行計算需求，現代通用 OS 均採用一對一模型（One-to-One Model）。因此選項 (b) 聲稱 Linux 與 Windows 典型為多對一模型，顯然屬於錯誤敘述。
3. 理論與實務落差：評估多對多模型（Many-to-Many Model）雖然在理論上最為彈性，但因排程器激活（Scheduler Activations）與狀態同步機制極為複雜，實務上難以完善實作。
4. 程式設計範式：隱式執行緒（Implicit Threading）將執行緒的建立與排程管理交由編譯器或執行期函式庫（Runtime Library）處理，在機制上利用任務池將多個任務分派給多個執行緒執行，屬於廣義的多對多觀念延伸。

---

選項分析

• (a) the Green thread is a Many-to-One threading model（正確敘述）
  • 說明：綠色執行緒（Green Threads）是早期 Java 虛擬機（JVM）與 Solaris 系統所採用的執行緒實作。由於當時許多作業系統核心尚未提供完善的多執行緒支援，Green Threads 完全在使用者空間由 JVM 或執行緒函式庫進行管理與排程， OS 核心僅能視其為單一排程實體。

核心觀念

本題考查作業系統（Operating Systems）中 CPU 排程機制（CPU Scheduling）、搶佔式與合作式排程之差異（Preemptive vs. Cooperative Scheduling）、現代核心架構（Preemptive Kernel） 以及 中斷處理與關鍵區段保護（Interrupt Handling & Critical Section Protection） 的核心觀念。

關鍵定義與概念如下：

1. 合作式排程（Cooperative / Non-preemptive Scheduling）：行程（Process）一旦獲得 CPU 控制權，就會持續執行，直到其主動放棄 CPU（如發起 I/O 請求、呼叫 yield()）或行程終止。作業系統不會強制中斷正在執行的行程。
2. 搶佔式排程（Preemptive Scheduling）：作業系統可依據時脈中斷（Timer Interrupt）或行程優先權（Priority），隨時強制剝奪正在執行中行程的 CPU 控制權，並將 CPU 分配給其他行程。
3. 搶佔式核心（Preemptive Kernel）：允許處於核心模式（Kernel Mode）執行的行程在執行過程中被其他行程搶佔。現代作業系統普遍採用搶佔式核心以降低系統延遲並提升回應速度。
4. 非同步中斷與競態條件（Asynchronous Interrupts & Race Condition）：中斷可在任何指令執行間隙非同步發生。若中斷服務常式（ISR）與核心程式碼存取共用資料結構，若未施加保護機制，共時存取（Concurrent Access）將引發資料不一致或競態條件。

---

解題方法

解題切入點為比對作業系統經典教科書（如 Silberschatz 之《Operating System Concepts》）對排程特性與核心同步的標準定義：

1. 比對 CPU 控制權轉移時機：釐清搶佔（Preemptive）與合作（Cooperative）的主動/被動切換機制。
2. 檢視現代 OS 核心設計發展：確認 Kernel Mode 下的搶佔特性趨勢。
3. 評估中斷對臨界區段的影響：分析非同步中斷存取共用變數時防護（Guard）的必要性。

---

選項分析

• (a) cooperative scheduling can result in race condition（錯誤）
  • 分析：在單處理器（Single-processor）環境下，合作式排程（Cooperative Scheduling）保證行程在未主動釋放 CPU 之前不會被作業系統強制搶佔。因此行程在執行關鍵區段（Critical Section）更新共用資料時，不會因作業系統突發的上下文切換（Context Switch）而產生競態條件（Race Condition）。

核心觀念

本題考驗作業系統在連續記憶體配置（Contiguous Memory Allocation）下的硬體記憶體保護機制（Hardware Address Protection）與暫存器權限管理。

1. 基址暫存器（Base Register）：儲存行程（Process）於實體記憶體中的起始實體位址（Smallest legal physical memory address）。
2. 界限暫存器（Limit Register）：儲存行程的記憶體空間大小／範圍（Size of the process / Range of logical address space）。
3. 記憶體存取檢查（Address Protection Check）：
   • 當 CPU 產生邏輯位址（Logical Address）$L$ 時，硬體會先比較 $L < \text{Limit}$。
   • 若 $L < \text{Limit}$，則合法，經由加法器轉換為實體位址 $P = \text{Base} + L$ 進行存取。
   • 若 $L \ge \text{Limit}$，表示非法越界存取（Out of bounds），硬體會引發中斷陷阱（Trap to OS: Addressing Error / Segmentation Fault）。
4. 特權指令（Privileged Instructions）：修改或載入 Base 與 Limit 暫存器的指令屬於特權指令，僅能在**核心模式（Kernel Mode）**下執行，以防使用者行程任意更改記憶體保護邊界。

---

解題方法

從記憶體保護的基本定義與硬體存取邏輯著手：

1. 釐清 Base Register 與 Limit Register 分別代表「起始位址」與「行程大小」。
2. 檢視位址檢查條件：存取位址必須落於 $[\text{Base}, \text{Base} + \text{Limit})$ 區間內。若位址高於 Base 但小於 $\text{Base} + \text{Limit}$，為正常存取行為。
3. 判定暫存器設定之權限級別：變更控制記憶體劃分的暫存器必須受 OS 保護，僅限 Kernel Mode 載入。
4. 逐一比對各選項敘述的正確性。

---

選項分析

核心觀念

本題考查 CPU 排程演算法（CPU Scheduling Algorithms） 中 優先權排程（Priority Scheduling） 的缺點及其延伸對應的演算法瓶頸。

1. 優先權排程（Priority Scheduling）：
   • 定義：每一個行程（Process）會被賦予一個優先權數值（Priority Number），CPU 會優先分配給目前準備佇列（Ready Queue）中優先權最高的行程執行。
   • 核心瓶頸：無限期等待（Indefinite Blocking） 或稱 飢餓現象（Starvation）。若系統中不斷有高優先權行程到達，低優先權行程將可能永遠無法獲得 CPU 資源。
   • 對策：通常採用 老化機制（Aging），即隨著時間推移逐漸提高在 Ready Queue 中等待過久的行程之優先權。

---

解題方法

本題為經典的觀念對比選擇題。解題切入點在於精準掌握各著名 CPU 排程演算法（Priority Scheduling、SJF、Round-Robin）的最主要技術瓶頸與致命缺點：

1. 找出 Priority Scheduling 獨有的代表性缺點（Starvation）。
2. 將選項中干擾項所對應的其他演算法（如 SJF 的 CPU Burst 預測問題、RR 的 Time Quantum 設定問題）進行排除。

---

選項分析

• (a) complexity（錯誤）
  優先權排程的實作相對直覺，僅需依據優先權維護優先佇列（Priority Queue），在演算法時間與空間複雜度上並非其最具代表性的核心瓶頸或主要缺點。

• (b) starvation（正確）
  優先權排程最顯著的問題即為飢餓現象（Starvation）或無限期等待（Indefinite Blocking）。當高優先權行程持續湧入時，佇列中的低優先權行程會長時間甚至永遠無法獲得 CPU 執行時間。

核心觀念

本題考查作業系統記憶體管理中的**分頁機制（Paging System）**與定址空間轉換原理。解題需掌握以下核心公式與定義：

1. 位元組定址與空間大小關係：
   在位元組定址（Byte-addressed）架構下，若定址位元數為 $n\text{ bits}$，則其定址空間的最大容量為 $2^n\text{ Bytes}$。
2. 單階分頁之邏輯位址結構（Logical Address Structure）：
   邏輯位址可拆分為「頁碼（Page Number, $p$）」與「頁偏移量（Page Offset, $d$）」兩部分：
   $\text{Logical Address Bits} = p + d$
   • 頁偏移量位元數 $d = \log_2(\text{Page Size})$
   • 頁碼位元數 $p = \text{Logical Address Bits} - d$
   • 單一程序可擁有的最大分頁數 $= 2^p$
3. 實體記憶體與頁框（Physical Memory and Frames）：
   • 頁框大小（Frame Size）恆等於分頁大小（Page Size）。
   • 實體位址位元數 $= \log_2(\text{Physical Memory Size})$
   • 實體記憶體最大頁框數 $= \frac{\text{Physical Memory Size}}{\text{Frame Size}}$

---

解題方法

1. 已知條件數值化

• 邏輯位址寬度（Logical Address）：$64\text{ bits}$
• 分頁大小（Page Size）：$4\text{ MB} = 4 \times 2^{20}\text{ Bytes} = 2^{22}\text{ Bytes}$
• 實體記憶體容量（Physical Memory）：$32\text{ GB} = 32 \times 2^{30}\text{ Bytes} = 2^{35}\text{ Bytes}$
• 定址單位：Byte-addressed（$1\text{ 位址} = 1\text{ Byte}$）

2. 詳細推導步驟

第 (1) 小題：計算單一程序最大可擁有的分頁數

1. 計算頁偏移量位元數 $d$：
   分頁大小為 $2^{22}\text{ Bytes}$，故頁內定址需要：
   $d = \log_2(2^{22}) = 22\text{ bits}$
2. 計算頁碼位元數 $p$：
   邏輯位址共 $64\text{ bits}$，扣除頁偏移量位元數後，頁碼位元數為：
   $p = 64 - 22 = 42\text{ bits}$
3. 計算最大分頁數：
   頁碼位元數為 $42\text{ bits}$，故單一程序最多可定址的分頁數量為：
   $\text{Maximum Pages} = 2^{42}$

第 (2) 小題：計算實體記憶體所需的位址位元數

1. 將實體記憶體容量轉換為 Byte 為單位的二次方數：
   $\text{Physical Memory Size} = 32\text{ GB} = 2^5 \times 2^{30}\text{ Bytes} = 2^{35}\text{ Bytes}$
2. 在位元組定址條件下，定址 $2^{35}\text{ Bytes}$ 所需的實體位址位元數為：
   $\text{Physical Address Bits} = \log_2(2^{35}) = 35\text{ bits}$

核心觀念

本題旨在考驗作業系統中**記憶體管理（Memory Management）與分頁機制（Paging System）**的核心硬體輔助元件——**TLB（Translation Look-aside Buffer，轉譯後照緩衝區）**的運作機制與優化策略。

解題時需掌握以下核心定義與系統概念：

1. TLB 的本質：TLB 為位於 CPU 內部的相聯記憶體（Associative Cache），專門用於快取「虛擬頁號（Virtual Page Number, VPN）至物理頁框號（Physical Frame Number, PFN）」的定址轉譯紀錄。
2. 有效記憶體存取時間（EMAT）：若未命中 TLB，CPU 存取一次記憶體需先走 $n$ 階頁表（Page Table）查詢實體位址，再存取目標資料，共花費 $(n+1)$ 次記憶體存取。設 TLB 命中率為 $\alpha$，存取時間為 $\epsilon$，記憶體存取時間為 $m$，則：
   $\text{EMAT} = \alpha \cdot (\epsilon + m) + (1 - \alpha) \cdot (\epsilon + (n + 1)m)$
3. TLB 鎖定（TLB Pinning / Wired-down Entries）：將特定臨界（Critical）記憶體區域的轉譯紀錄永久固定於 TLB 中，排除於置換演算法（如 LRU）之外。
4. 位址空間識別碼（Address-Space Identifier, ASID）：標記該轉譯紀錄屬於哪一個進程（Process）的識別碼，使得 TLB 可同時儲存多個進程的轉譯紀錄。

---

解題方法

本題為敘述型觀念題，解題切入點應從硬體架構設計、作業系統核心運作安全性與系統效能優化三個維度逐一論破：

1. 第 (1) 小題（核心功能）：從「頁表查詢時間開銷」切入，說明 TLB 如何透過快取轉譯結果來避免每次記憶體存取都必須先查詢位於 RAM 的頁表，進而顯著降低 EMAT。
2. 第 (2) 小題（Wired-down 原因）：從「異常處理與死鎖防範（Double Fault / Infinite Recursion Prevent）」切入。分析若作業系統核心（Kernel）、中斷處理常式（ISR）或 TLB 缺頁處理程式（TLB Miss Handler）自身發生 TLB Miss 時會面臨的系統崩潰風險。
3. 第 (3) 小題（ASID 作用與 Context Switch 加速）：
   • 定義：對比 PID 的概念，說明 ASID 如何區分不同進程重疊的虛擬位址空間。
   • 加速原理：對比「傳統 Context Switch 必須 Flush（清空）整張 TLB」與「具備 ASID 機制只需切換硬體 ASID 暫存器」之差異，分析其如何消除 Context Switch 後的冷啟動（Cold Start）TLB 快取失效負擔。

---

子題深入解析

(1) TLB 的核心功能（Core Function of TLB）

• 運作機制與功能：
  在虛擬記憶體架構下，CPU 發出的位址皆為虛擬位址（Virtual Address）。為了將虛擬頁號（VPN）轉換為實體頁框號（PFN），CPU 必須存取記憶體中的頁表（Page Table）。由於主記憶體（RAM）的存取速度遠慢於 CPU 暫存器，每次記憶體存取都額外查詢頁表會造成嚴重的效能瓶頸。

  TLB 的核心功能即為**「作為虛擬位址至實體位址轉譯（VA-to-PA Translation）的高速硬體快取」**。當 CPU 發出虛擬位址時，硬體會同時（Parallel Look-up）比對 TLB 中的項目：

  • TLB Hit（命中）：直接回傳對應的 PFN，CPU 只需花費 $1$ 次記憶體存取時間即可取得目標資料。
  • TLB Miss（未命中）：CPU 必須存取主記憶體中的頁表進行定址轉譯，並將該次轉譯結果寫回 TLB 以供後續使用。

---

(2) 特定 TLB 項目固定不動（Wired-down Entries）的原因

• 安全性與無窮遞迴防範（Infinite Recursion Prevention）：
  在採用軟體處理 TLB Miss（Software-managed TLB，如 MIPS 架構）或系統執行臨界任務時，若 TLB Miss Handler（TLB 未命中中斷常式）或 Interrupt Service Routine (ISR) 所在的虛擬位址被踢出 TLB，當 TLB Miss 發生時，硬體跳轉至 Miss Handler 執行，卻又再次引發 TLB Miss。這會導致無窮遞迴 TLB 缺頁（Recursive TLB Fault），最終導致 CPU 死鎖或系統崩潰（System Panic）。
• 重要核心資料結構防護：

核心觀念

本題考查作業系統中頁表（Page Table）的硬體實作機制與設計權衡（Trade-offs）。

在分頁（Paging）記憶體管理機制中，CPU 發出的虛擬位址需要透過頁表轉譯為實體位址。將頁表置於不同的硬體介面時，系統會面臨速度、容量與維護成本的權衡：

1. 主記憶體實作（Main Memory）：
   頁表存於 RAM 中。每次進行資料存取需要 2 次記憶體存取（第一次存取頁表取得實體頁框號 $PFN$，第二次存取目標資料），導致記憶體存取時間加倍（Double Access Time）。
2. 高速暫存器實作（Dedicated High-Speed Registers）：
   將頁表直接儲存在 CPU 內部的專用暫存器。存取暫存器的速度極快（通常可在 1 個 CPU 週期內完成），能解決記憶體存取延遲問題。

---

解題方法

分析將「完整頁表」儲存在專用高速暫存器時，系統所面臨的核心問題：

1. 硬體容量限制與成本過高（Capacity Limitation & High Cost）：
   • CPU 內部的暫存器晶片面積大、成本極高且數量極其有限。
   • 現代作業系統的虛擬位址空間巨大（例如 32-bit 系統最多需要 $2^{20}$ 個頁表項；64-bit 系統更為龐大）。若將整張頁表存於暫存器中，硬體架構上根本無法提供足夠數量的暫存器來容納龐大的頁表內容。
2. 上下文切換開銷過大（Context Switch Overhead）：
   • 在多工（Multitasking）作業系統中，每個進程（Process）都擁有自己獨立的頁表。
   • 當 CPU 進行進程切換（Context Switch）時，必須將暫存器中舊進程的頁表內容全部寫回記憶體的進程控制區塊（PCB），並將新進程的頁表內容重新載入至暫存器中。
   • 若頁表包含數百或數千個暫存器，每次切換都必須執行大量的暫存器讀寫作業，會造成嚴重的系統延遲（Context Switch Latency）。

---

選項分析

本題為問答題（非選擇題），以下針對「不同頁表實作架構」之特性進行綜合評估與對比：

核心觀念

本題考查作業系統（以現代 Linux/Unix 系統為代表）的**開機流程（System Boot Sequence）**與階段性任務分割。完整的開機流程可劃分為以下 5 個主要階段：

1. 韌體階段（Firmware Phase）：電腦通電後，BIOS/UEFI 進行 POST（Power-on Self Test），並載入開機載入程式（Boot Loader）。
2. 開機載入程式階段（Boot Loader Phase）：Boot Loader（如 GRUB）自儲存裝置尋找並將作業系統核心映像檔（Kernel Image）載入記憶體中執行。
3. 核心初始化階段（Kernel Initialization Phase）：核心接管控制權，建立記憶體管理、中斷表，並初始化各項硬體設備與驅動程式（Drivers）。
4. 掛載根檔案系統階段（Root Filesystem Mounting Phase）：核心掛載根檔案系統（Root Filesystem, /），以取得系統執行檔與設定檔。
5. 使用者空間初始化階段（User-space Initialization Phase）：核心啟動第一個使用者空間進程（PID 1），即 systemd（或傳統的 init），完成後續系統服務與使用者環境的建立。

---

解題方法

解題時應依據「控制權轉移」與「系統元件依賴性」的順序進行邏輯排列：

1. 硬體與韌體先行：電腦電源開啟後最先由 BIOS 或韌體控制，負責尋找開機載入程式，因此 b 為開機起點。
2. 載入作業系統核心：BIOS 交付控制權給 Boot Loader，Boot Loader 負責將作業系統核心載入記憶體並啟動它，故接著為 d。
3. 核心與驅動程式初始化：核心接管控制權後，必須先初始化底層硬體與驅動程式，否則無法與磁碟等儲存設備溝通，故接著為 e。
4. 掛載根檔案系統：驅動程式準備就緒後，核心具備存取儲存裝置的能力，進而掛載根檔案系統，故接著為 c。
5. 啟動第一個使用者進程：根檔案系統掛載成功後，核心才能讀取該檔案系統中的執行檔（如 /lib/systemd/systemd），啟動 systemd 進程（PID 1），故最後為 a。

綜上推導，正確順序為：b $\rightarrow$ d $\rightarrow$ e $\rightarrow$ c $\rightarrow$ a。

---

選項分析

按正確的執行時間軸順序，逐一分析各步驟的功能與相依關係：

• 步驟 b (第 1 順位)：The machine's BIOS or boot firmware loads and runs a boot loader.
  • 說明：正確。

核心觀念

本題考查多執行緒程式設計（Multithreaded Programming）中的進階架構與排程機制，核心概念包含：

1. 執行緒池（Thread Pool）：預先建立並維護一組工作執行緒（Worker Threads），達成執行緒重用（Reuse）與資源控制。
2. Fork-Join 模式：採用分治法（Divide-and-Conquer）將大任務遞迴分割為小任務（Fork），最終再合併結果（Join）。
3. 工作竊取演算法（Work-Stealing Algorithm）：解決分治遞迴過程中所產生的執行緒負載不均問題，實現動態負載平衡（Dynamic Load Balancing）。

---

解題方法

本題為觀念問答題，解題切入點如下：

1. 第 (1) 小題：從「定義」與「運作機制」兩方面說明 Thread Pool 的概念，強調「工作執行緒」與「任務佇列（Task Queue）」的配合。
2. 第 (2) 小題：從「效能（降低建立/銷毀開銷）」、「資源管控（防止系統崩潰與過度 Context Switch）」以及「管理彈性（任務排程與解耦）」三個維度完整分析效益。
3. 第 (3) 小題：先點出 Fork-Join 模型的特質（遞迴分治導致各執行緒工作量不均），再詳細說明 Work-Stealing 演算法的「主要目的」（動態負載平衡、提高 CPU 利用率）及其「雙端佇列（Deque）運作機制」（LIFO 與 FIFO 搭配以降低 Lock 競爭與優化快取）。

---

選項分析（小題剖析）

(1) What is a thread pool?

**執行緒池（Thread Pool）**是一種用於多執行緒併發執行的設計模式（Concurrency Design Pattern）。其核心架構與運作機制如下：

• 概念定義：在應用程式啟動或初始化時，系統預先建立一定數量的**工作執行緒（Worker Threads）**並置於池中等待任務。
• 運作流程：當應用程式有新任務（Task）需要執行時，不會直接建立新的執行緒，而是將任務提交至一個**任務佇列（Task Queue）**中。池中的空閒工作執行緒會自動從佇列中取出任務並執行；任務完成後，該執行緒不會銷毀，而是重新回到池中繼續等待處理下一個任務。

---

(2) What are the benefits of the thread pool?

使用執行緒池的主要優點可歸納為以下三大層面：

1. 降低系統開銷與回應延遲（Reduced Overhead & Latency）：
   • 建立與銷毀執行緒需要向作業系統申請資源（如分配 TCB、使用者/核心堆疊、初始化暫存器等），頻繁建立/銷毀會產生龐大的系統開銷。
   • 執行緒池透過「重用（Reuse）」既有執行緒，省去頻繁建立與銷毀的負擔，大幅縮短任務的反應時間（Response Time）。
2. 資源管控與系統穩定度（Resource Management & System Stability）：
   • 限制併發執行的最大執行緒數量。若大量請求同時湧入，未受控地建立無窮多執行緒會耗盡記憶體，並引發極為嚴重的**內文切換（Context Switching）**開銷與 CPU 競爭。
   • 執行緒池能確保系統在極高負載下仍保持穩定，不致因資源耗盡而崩潰。
3. 解耦任務與執行機制並提高排程彈性（Decoupling & Scheduling Flexibility）：
   • 將「任務的提交（Task Submission）」與「任務的執行（Task Execution）」解耦，使程式架構更加清晰。
   • 方便擴充進階任務管理功能，例如定時執行（Scheduled Execution）、延遲執行（Periodic Tasks）以及任務優先權控制。

---

(3) What is the purpose of the "work stealing algorithm" used in the Fork-Join pool?

Fork-Join Pool 專為「分治法（Divide-and-Conquer）」的遞迴任務所設計。

核心觀念

本題考察作業系統（Operating System）中**記憶體管理（Memory Management）**的「反轉頁表（Inverted Page Table, IPT）」機制，包含以下核心理論：

1. 反轉頁表（Inverted Page Table）之結構與設計動機：
   傳統頁表（Traditional Page Table）是以邏輯位址的「頁號（Page Number, $p$）」作為索引，每個行程（Process）皆需維護各自獨立的頁表。當虛擬位址空間極大（例如 64-bit 系統）時，頁表本身會佔用龐大的實體記憶體。反轉頁表改以「實體頁框號（Physical Frame Number, $f$）」作為陣列索引，整個系統僅需維護唯一一張全域頁表，其表項總數等於實體記憶體的頁框數量。
2. 定址轉換（Address Translation）邏輯：
   CPU 產生的虛擬位址格式包含 $\langle pid, p, d \rangle$（行程識別碼、邏輯頁號、頁內位移）。定址時需在 IPT 中搜尋相符的 $\langle pid, p \rangle$，若在第 $i$ 個表項找到匹配，則實體頁框號 $f = i$，實體位址即為 $\langle i, d \rangle$。
3. 共享記憶體／函式庫（Shared Memory / Shared Library）之限制：
   多個行程共享實體頁框時，本質上是不同的邏輯頁面映射至相同的實體頁框（多對一映射）。然而 IPT 的每個實體頁框索引在表中嚴格僅能儲存單一組 $\langle pid, p \rangle$，因而產生結構上的衝突。

---

解題方法

(1) 反轉頁表（Inverted Page Table）之架構與運作原理

架構示意圖（Diagram of Inverted Page Table Structure）：

                     CPU 虛擬位址 (Logical Address)
                    +---------+---------+---------+
                    |   pid   |    p    |    d    |
                    +---------+---------+---------+
                         |         |         |
                         +----+----+         |
                              |              |
                              v              |
                       [ 搜尋 / 雜湊表 ]     |
                              |              |
                              v              |
                     反轉頁表 (IPT)           |
                   +-------+-------+         |
         索引 (i)  |  pid  |   p   |         |
         +-------+ +-------+-------+         |
         |   0   | |  pid0 |  p0   |         |
         |  ...  | |  ...  |  ...  |         |
         |   i   | |  pid  |   p   | <---+ 匹配成功 (Match found at index i)
         |  ...  | |  ...  |  ...  |     |
         |  N-1  | | pidN-1| pN-1  |     | (實體頁框號 f = i)
         +-------+ +-------+-------+     |
                                         v
                                  實體記憶體 (Physical Memory)
                                 +--------------------+
                                 |     Frame 0        |
                                 |       ...          |
                        f = i -> |+------------------+|
                                 || Page Data (d)    ||
                                 |+------------------+|
                                 |       ...          |
                                 |     Frame N-1      |
                                 +--------------------+
                                  實體位址: < i, d >

定址轉換步驟解析：

1. 虛擬位址拆解：
   CPU 產生的虛擬位址分為三部分：

   • $pid$ (Process ID)：請求存取記憶體的行程識別碼。
   • $p$ (Logical Page Number)：虛擬頁號。
   • $d$ (Offset)：頁內位移量。

2. 頁表搜尋與頁框判定：

   • 系統以組合鍵 $\langle pid, p \rangle$ 作為查詢目標，搜尋全域的反轉頁表（IPT）。
   • 若在 IPT 的第 $i$ 個 entry（列）找到完全相符的 $\langle pid, p \rangle$，代表該虛擬頁面目前載入於實體記憶體的第 $i$ 個頁框（Frame $i$）。
   • 故轉譯出的實體頁框號即為 $f = i$。