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

核心觀念

本題考查作業系統中的容器技術（Container Technology，如 Docker）與傳統虛擬化技術（Virtualization）的架構差異及其關鍵底層元件。

容器是一種「作業系統層級的虛擬化（OS-level Virtualization）」技術，它共享宿主作業系統（Host OS）的核心（Kernel），並透過 Linux 核心提供的機制實現資源隔離與限制：

• cgroups (Control Groups)：負責資源限制與配額（如 CPU、記憶體、I/O 頻寬）。
• Namespaces：負責資源隔離（如 PID、Network、Mount、User 等視圖隔離）。
• Volume：負責資料持久化與共享（將宿主機的檔案系統目錄掛載至容器內）。

相對地，**Hypervisor（虛擬機器監視器）**是「硬體層級虛擬化（Hardware-level Virtualization，即傳統虛擬機器 VM）」的核心技術，負責管理與調配實體硬體資源，並在之上運行完整的 guest OS。

---

解題方法

區分「容器（Container）」與「虛擬機器（Virtual Machine, VM）」的關鍵切入點在於是否包含 Hypervisor 以及是否運行獨立的 Guest OS：

1. 容器直接運行在宿主機的 Kernel 之上，依賴 cgroups、namespaces 與 volume 等技術運作。
2. 虛擬機器則必須透過 Hypervisor（如 KVM、ESXi、Hyper-V）來模擬硬體，並在獨立的 Guest OS 上運行應用程式。

因此，尋找「不屬於容器相關技術」的選項，即為找出屬於傳統虛擬機器（VM）架構的核心元件。

---

選項分析

核心觀念

本題考查**行程狀態轉移（Process State Transition）與等待隊列（Wait Queue / Blocked Queue）**的觸發時機。

在作業系統中，行程在執行期間會在不同狀態間轉換：

1. Running（執行態）：行程目前佔據 CPU 並執行指令。
2. Ready（就緒態）：行程已準備好執行，等待 CPU 調度器（Scheduler）指派 CPU 時間。
3. Waiting / Blocked（等待態／阻塞態）：行程因等待某個事件（如 I/O 完成、子行程結束、等待中斷信號）發生而無法繼續執行，此時行程會被移出 CPU 並放入等待隊列（Wait Queue）。

當行程被切換出 CPU（Switched out of CPU / Preempted / Yielded）時，其去向（放入 Ready Queue 或 Wait Queue）取決於引發切換的原因。

---

解題方法

判斷行程被切換出 CPU 後會被加入 Ready Queue 還是 Wait Queue，關鍵在於：行程是否具備立即繼續執行的能力。

• 若行程不需要等待外部事件發生，隨時可以繼續執行 $\Rightarrow$ 進入 Ready Queue（等待 CPU 調度）。
• 若行程必須等待外部事件（如 I/O 裝置回應、子行程執行完畢、中斷觸發）才能繼續執行 $\Rightarrow$ 進入 Wait Queue（等待事件發生）。

題目詢問哪一個狀況**不會（does not）**使行程被加入至 Wait Queue，意即尋找會將行程加入 Ready Queue 的選項。

---

選項分析

• (A) I/O request（錯誤，該狀況會加入 Wait Queue）
  行程發出 I/O 請求（如讀寫磁碟、網路傳輸）後，由於 I/O 裝置處理速度慢於 CPU，行程無法繼續執行後續指令，必須主動放棄 CPU 並進入 Wait Queue，直到 I/O 控制器發出完成中斷（I/O Interrupt）才移回 Ready Queue。

核心觀念

本題考驗分散式作業系統（Distributed Operating System, DOS）的基本功能與資源/任務遷移機制（Migration Mechanisms）。

分散式作業系統的主要目標是透過網路連結多台獨立計算機，提供使用者「單一系統影像」（Single-System Image, SSI）。為了達到負載平衡（Load Balancing）、資源共享（Resource Sharing）與提升效能，分散式作業系統通常提供以下三種核心遷移功能：

1. 資料遷移（Data Migration）：將資料或檔案傳輸至存取該資料的節點，或透過快取機制減少跨網路存取延遲。
2. 計算遷移（Computation Migration）：將計算任務（例如 RPC、Agent 或查詢請求）傳送至資料所在或具備特定運算資源的節點執行，以減少大筆資料在網路上傳輸的開銷（即「將計算移至資料」）。
3. 行程遷移（Process Migration）：將整個正在執行的行程（包含 PCB、記憶體位址空間、暫存器狀態等）從一個節點搬移至另一個節點繼續執行。

相較之下，「核心（Kernel）」是作業系統中最基本、管理硬體與提供核心服務的底層軟體架構，每個節點各自運行或共享其核心介面，並不具備所謂將整個運行中 kernel 進行動態搬移的「kernel migration」一般性功能。

---

解題方法

解題切入點在於區分「分散式系統中哪些資源/物件可以在節點間遷移（Migratable Entities）」。
在分散式作業系統中，發揮平行與分散式處理綜效的核心在於對 Data（資料）、Computation（計算指令/服務請求）與 Process（完整執行中的行程）進行跨節點調度。

由於每個分散式節點均需維持各自的核心運作或透過微核心（Microkernel）進行基本通訊與資源管理，作業系統並不提供在運行中將整個 Kernel 動態搬移至另一台機器運行的機制（KernelMigration

核心觀念

本題考查作業系統與資訊安全章節中惡意軟體（Malicious Software / Malware）的分類與定義。

• 勒索軟體（Ransomware）：一種惡意軟體，會對受害者的檔案進行加密或鎖定系統存取權限，並要求受害者支付贖金（通常為加密貨幣）以換取解密金鑰或還原系統。
• ** WannaCry（WannaCrypt）**：2017 年起大規模爆發的知名勒索軟體，利用 Windows 系統的 Server Message Block (SMBv1) 漏洞（EternalBlue 永恆之藍）進行自動網路蔓延與檔案加密。2018 年 8 月台積電（TSMC）因新設備安裝過程未先消毒掃毒，導致受 WannaCry 變種病毒感染而多個晶圓廠暫時停工。

---

解題方法

切入點在於識別 WannaCry (WannaCrypt) 惡意軟體的運作特徵與分類：

1. 新聞背景與軟體特性：WannaCry 的主要行為是強制加密電腦內的文件與檔案，畫面會跳出勒索視窗要求支付比特幣（Bitcoin）贖金，因此屬於典型的勒索軟體。
2. 對比各選項定義：對照作業系統安全章節中常見的各類惡意程式（Spyware、Ransomware、Logic Bomb、Trap Door/Backdoor）定義，即可快速鎖定正確選項。

---

選項分析

• (A) spyware（間諜軟體）：錯誤。
  間諜軟體是指在使用者不知情的情況下，秘密收集使用者個人資訊、監控鍵盤輸入（Keylogger）或瀏覽習慣並傳送給第三方的惡意程式。

核心觀念

本題考查非揮發性記憶體（NVM / Non-Volatile Memory，如 Flash-based SSD）的 I/O 排程與物理特性。

• NVM 物理特性：NVM 裝置（如 SSD）缺乏傳統機械硬碟（HDD）的磁頭與旋轉磁碟片結構，因此沒有 Seek Time（尋道時間）與 Rotary Latency（旋轉延遲）。
• 讀寫不對稱性（Asymmetry）：SSD 的讀取（Read）通常非常快速且均勻；但寫入（Write）受到 Flash Memory「先擦除再寫入（Erase-before-write）」及 Garbage Collection（垃圾回收/GC）、Wear Leveling（損耗平均）等機制影響，寫入時間不均勻且耗時較長。
• NVM I/O 排程：由於 NVM 支援隨機存取且無尋道開銷，傳統為 HDD 設計的磁碟排程演算法（如 FCFS, SSTF, SCAN, C-SCAN 等）在 NVM 上失去其物理優勢。SSD 內部通常採用 NVM 專屬排程或直接按 FIFO / FCFS 處理，並依靠內部的 FTL（Flash Translation Layer）處理請求佇列。
• 效能衡量與空間飽和度：NVM/SSD 的效能指標通常使用 IOPS（Input/Output Operations Per Second）與 Read/Write Latency；當 SSD 空間逐漸變滿時，可用空白 Block 減少，觸發 GC 的頻率大幅增加，導致寫入效能（Write Performance）明顯下降。

---

解題方法

1. 分析 NVM（SSD）與傳統 HDD 的根本差異（有無機械移動件）。
2. 檢視傳統 Disk Scheduling 演算法（如 C-SCAN）存在的目的：C-SCAN 旨在減少機械磁頭移動距離。對於隨機存取時間接近常數的 NVM 而言，C-SCAN 並無必要，甚至可能增加不必要的排程負擔。
3. 逐一比對各選項敘述之正確性，找出敘述錯誤（Wrong）的選項。

---

選項分析

• (A) in NVM, write time is usually not uniform whereas read is usually uniform
  • 正確。NVM 的讀取時間基本上是 uniform（均勻且快速的隨機存取）；

核心觀念

本題旨在考驗**行程的記憶體佈局（Process Memory Layout）**中各個區段（Segment）的功能與用途。在典型的作業系統與系統程式概念中，一個執行中的行程在虛擬記憶體空間通常會劃分為以下主要區段：

1. 文字區段（Text Segment / Code Segment）：儲存程式的可執行機器指令（Machine Instructions），通常為唯讀（Read-Only）與可共享。
2. 資料區段（Data Segment）：
   • 已初值化資料區（Initialized Data Segment）：儲存已賦予初始值的全域變數（Global Variables）與靜態變數（Static Variables）。
   • 未初值化資料區（Uninitialized Data Segment / BSS Segment）：BSS 為 Block Started by Symbol 的縮寫，儲存未初值化（或初始值為 0）的全域變數與靜態變數。
3. 堆積區（Heap Segment）：用於動態記憶體配置（例如 C 語言的 malloc() / free()，C++ 的 new / delete），由低位址向高位址成長。
4. 堆疊區（Stack Segment）：用於維護函式呼叫的狀態與區域變數。每次呼叫函式時，系統會在 Stack 上建立一個啟動紀錄（Activation Record，或稱 Function Frame / Stack Frame），由高位址向低位址成長。

---

解題方法

根據題意，需找出對行程記憶體佈局描述**錯誤（wrong）**的選項。
切入點為比對每個選項敘述的記憶體區段名稱（Stack, Heap, BSS）與其所儲存的資料類型，特別留意 Activation Records（啟動紀錄）在作業系統與編譯器原理中的嚴格定義。

---

選項分析

• (A) the parameter values and the return address store in the stack area（正確）
  • 說明：當程式執行函式呼叫時，系統會在 Stack 區段壓入（Push）一個新的 Stack Frame（即 Activation Record）。該區段主要用來儲存傳遞給函式的參數值（Parameter Values）、函式執行完畢後需返回的返回位址（Return Address），以及 CPU 暫存器的狀態保護資訊。因此此敘述正確。

核心觀念

本題考查 UNIX/Linux 作業系統中的**行程間通訊（Inter-Process Communication, IPC）機制，特別是無名管道（Anonymous Pipe）**的 C 語言系統呼叫（System Call）寫法與運作特性。

1. 管道（Pipe）的建立與檔案描述子（File Descriptor）：
   在 UNIX/Linux 系統中，呼叫 pipe(int fd[2]) 會建立一組單向資料流的管道，並回傳兩個檔案描述子於陣列 fd 中：
   • fd[0]：管道的讀取端（Read end）。
   • fd[1]：管道的寫入端（Write end）。
2. 通訊模式：
   Pipe 屬於半雙工（Half-duplex）或單向通訊。標準使用習慣為：若行程僅需寫入資料至管道，會先關閉不使用的讀取端 close(fd[0])，再透過寫入端 write(fd[1], ...) 寫入資料，最後於寫入完畢後關閉寫入端 close(fd[1])。

---

解題方法

由程式碼片段進行分析：

1. close(fd[0]);：關閉陣列索引為 0 的檔案描述子，即關閉管道的讀取端（Read End）。
2. write(fd[1], "test", 5);：對陣列索引為 1 的檔案描述子進行寫入操作，將字串 "test"（含結尾字符 \0 共 5 位元組）寫入管道中。
3. close(fd[1]);：寫入完畢後關閉管道的寫入端（Write End）。

上述使用 fd[0] 為讀取端、fd[1] 為寫入端，配合 write() 與 close() 的呼叫模式，為 UNIX System V / POSIX 標準中 Pipe（管道） 最典型的操作範例。

---

選項分析

• (A) shared memory（錯誤）
  共享記憶體（Shared Memory）是將同一區段的實體記憶體映射（Map）到不同行程的虛擬位址空間。

核心觀念

本題主要考驗**執行緒取消（Thread Cancellation）**的機制與 POSIX Threads (Pthreads) 以及 Java 在執行緒取消實作上的差異。

1. 執行緒取消機制（Thread Cancellation）：
   • 非同步取消（Asynchronous Cancellation）：一收到取消請求，作業系統或執行緒庫便立刻強制終止目標執行緒。此模式可能導致執行緒在持有共享資源（如 Lock）或動態配置記憶體時被中途終止，造成資源洩漏（Resource Leak）或死鎖（Deadlock）。
   • 延遲取消（Deferred Cancellation）：收到取消請求後，目標執行緒不會立刻終止，而是會繼續執行，直到抵達特定的**取消點（Cancellation Point）**時才安全地退出。這是 POSIX 預設且推薦的取消方式。
2. POSIX 阻塞系統呼叫：POSIX 標準中，絕大多數會阻塞（Blocking）執行緒的系統呼叫（如 read()、write()、pthread_cond_wait()、sleep() 等）都被設計為取消點。
3. Java 的執行緒取消機制：Java 早期在 Thread 類別中提供過 stop()、suspend()、resume() 等方法，但因安全隱患已被標示為不推薦使用（Deprecated）。Java 並未提供名為 defer() 的方法來處理延遲取消；Java 處理執行緒中斷與取消，使用的是 interrupt() 機制與 isInterrupted() / Thread.interrupted() 狀態檢查。

---

解題方法

此題為單選題，目標是找出敘述**錯誤（False）**的選項：

1. 檢視 (A) 是否符合非同步取消（Asynchronous Cancellation）的定義。
2. 檢視 (B) 是否符合 POSIX 標準中對阻塞系統呼叫與 cancellation point 的規範。
3. 檢視 (C) 在 Pthreads 程式設計中，非同步取消是否因資源安全問題而不被推薦。

核心觀念

本題考查作業系統（Operating Systems）記憶體管理中**顛簸（Thrashing）與頁面錯誤頻率（Page Fault Frequency, PFF）**控制策略的機制。

當一個行程（Process）配給到的實體頁框數（Page Frames）不足時，會頻繁發生頁面錯誤（Page Fault），導致系統花費大量時間進行頁面換入換出（Paging I/O），CPUs 使用率急遽下降，此現象稱為顛簸（Thrashing）。

為防範顛簸，作業系統主要採用以下兩種控制策略：

1. 工作集模型（Working Set Model）：定義行程在一段滑動時間區間 $\Delta$（Working-Set Window）內所參考到的頁面集合。利用頁面參考軌跡（Page Reference String）動態計算 $WSS_i$（行程 $i$ 的工作集大小）。若總需求量 $\sum WSS_i > D$（可用頁框總數），則將部分行程掛起（Suspend）。
2. 頁面錯誤頻率策略（Page Fault Frequency, PFF Strategy）：採用更直接的主動控制方法。預先設定頁面錯誤率的上界 $Upper\_Bound$ 與下界 $Lower\_Bound$：
   • 當行程的 PFF 超過 $Upper\_Bound$ 時，代表分配給該行程的頁框不足，系統需**額外分配頁框（Allocate Page）**給該行程。
   • 當行程的 PFF 低於 $Lower\_Bound$ 時，代表該行程擁有過多的頁框，系統會從該行程回收／釋放頁框（Deallocate Page）。

---

解題方法

本題要求判斷關於 PFF 策略的敘述何者正確。解題切入點如下：

1. 根據 PFF 機制的定義，檢驗當 PFF 太高（超過上限）與太低（低於下限）時，系統對頁框配置的調整動作是否符合 (A) 與 (B)。
2. 將 PFF 策略與 Working Set 策略的實作複雜度進行比較：Working Set 需要為每一次記憶體存取維護參考軌跡與計數器／時間戳記，實作成本極高；

核心觀念
本題考查記憶體管理（Memory Management）與虛擬記憶體（Virtual Memory）架構中，用於快取轉譯後備緩衝區（Translation Lookaside Buffer, TLB）或分頁表項目（Page Table Entries, PTEs）的軟硬體架構名詞。

在現代處理器與作業系統（特別是 UltraSPARC / Solaris 架構）中：

• TLB 是一種硬體快取，用於加速「虛擬位址（Virtual Address）」到「實體位址（Physical Address）」的轉譯。
• 當發生 TLB 錯失（TLB Miss）時，若採軟體處理方式（Software-managed TLB），系統需要迅速在記憶體中尋找對應的分頁表項目（PTE）。
• 為了解決軟體處理 TLB Miss 速度較慢的問題，Solaris/UltraSPARC 架構設計了一種軟體快取結構，稱為 TSB (Translation Storage Buffer)。TSB 扮演著記憶體中「TLB 錯失後的第一線快取（Direct-mapped Memory Cache for PTEs）」，協助快速補滿 TLB。

---

解題方法
本題雖然題幹寫成 "The cache that holds TLB in a CPU is called"，實質上是在考查「用於快取 TLB/PTE 資料結構的專有名詞」。在標準作業系統學科及 UltraSPARC/Solaris 系統記憶體架構中：

1. TLB Entry (TTE) 是 TLB 內儲存的單一項目。
2. TSB (Translation Storage Buffer) 則是位於記憶體中、用來快取頁面轉譯項目（PTEs/TTEs）以避免昂貴的分頁表走訪（Page Table Walk）的快取區。
3. 比對各選項縮寫之定義後，即可確定正確名稱為 TSB。

---

核心觀念

本題考查**大位址空間下的頁表結構（Page Table Structures for Large Address Spaces）**設計與選擇。

在現代作業系統中，分頁（Paging）機制需要維護虛擬位址到實體位址的映射關係。

• 分層頁表（Hierarchical Page Tables / Two-Level Paging）：將位址劃分為多個頁表層級。在 32-bit 系統中，傳統的雙層分頁（Two-Level Paging）十分高效；然而在 64-bit 系統中，若採用分層頁表，為了控制單一頁表的大小不超過一個頁面（例如 $4\text{ KB}$），所需的層數會大幅增加（例如需要 4 到 7 層），導致每次記憶體存取需要多次查表，帶來極高的記憶體存取延遲與龐大的頁表樹狀結構開銷。
• 叢集頁表（Clustered Page Tables）：為雜湊頁表（Hashed Page Table）的變型，適用於位址空間大於 32-bit 的系統（如 64-bit）。在叢集頁表中，雜湊表的每一個 Hash Entry 指向多個連續頁面（例如 16 個頁面）的頁框映射，能顯著減少雜湊表本身的項目數與指標開銷，適合處理稀疏位址空間（Sparse Address Space）。
• 倒置頁表（Inverted Page Table）：以實體記憶體（Frame）數量為基準建立單一表格，而非按每個進程的虛擬位址空間建立。雖然它成功限制了頁表的大小，但由於每次尋找都需要對實體頁框進行搜尋（通常需要配合 Hash Table），在多元程式規劃（Multiprogramming）及共享記憶體（Shared Memory）的實作上極為困難與複雜。

因此，對於 64-bit 計算機系統，為了解決分層頁表層數過多及雜湊碰撞過高的問題，叢集頁表（Clustered Page Tables） 是 Silberschatz 所著權威教材《Operating System Concepts》中明文指出的最合適方案之一。

---

解題方法

1. 評估 64-bit 位址空間的特性：
   64-bit 系統的虛擬位址空間極其龐大（$2^{64}\text{ bytes}$）。若採用傳統分頁，頁表項（PTE）的數量與層級數會急遽增加。
2. 分析各種頁表架構在 64-bit 系統中的可行性與限制：
   • Hierarchical / Two-Level Paging：32-bit 系統常採用 2 層頁表。若將 2 層分頁直接用於 64-bit 系統，單一 Outer Page Table 會變得無比巨大；若增加層數（如 64-bit x86-64 實作 4-Level 或 5-Level），存取效能負擔重。
   • Inverted Page Table：雖然大小與實體記憶體成正比，但處理共享頁面（Shared Pages）與虛擬位址映射的實現過於複雜。

核心觀念
本題考查作業系統中**死鎖（Deadlock）與活鎖（Livelock）**的核心概念，包含：

1. Banker's Algorithm（銀行家演算法）：死鎖避免（Deadlock Avoidance）演算法，適用於每種資源類型有多個實例（Multiple instances）的系統，當然也涵蓋單一實例（Single-instance）的特例。
2. Resource-Allocation Graph (RAG) Algorithm（資源分配圖演算法）：適用於單一實例資源系統的死鎖避免演算法，藉由檢查需求邊（Claim edge）形成的環（Cycle）來避免死鎖。
3. Deadlock Prevention（死鎖預防）：透過打破死鎖四個必要條件之一來預防死鎖，但因代價過高（降低系統吞吐量與資源利用率），大多數通用作業系統（如 UNIX, Linux, Windows）並不採用死鎖預防或死鎖避免，而是採用死鎖忽略（Ostrich algorithm，鴕鳥演算法），將死鎖處理交給使用者或應用程式。
4. Livelock（活鎖）：執行緒未被阻塞（State 為 Ready/Running），但因持續嘗試失敗的操作而陷入無法取得進展的無窮迴圈。

---

解題方法
檢視各選項陳述是否符合作業系統理論與實際作業系統實作機制，特別注意實務上作業系統（Operating Systems）處理死鎖的真實策略，找出敘述錯誤（False）的選項。

---

選項分析

• (A) Banker's algorithm is applicable in a single-instance system（正確）

  • 分析：Banker's algorithm 設計之初可用於處理每種資源類型有多個實例（Multiple instances）的系統。當每種資源實例數為 $1$（Single-instance）時，Banker's algorithm 依然適用（退化為特例，退化後的計算複雜度相當於尋找安全序列），因此此敘述正確。

• (B) the drawback of using RAG algorithm is low resource utilization（正確）

  • 分析：在死鎖避免（Deadlock Avoidance）機制中，RAG 演算法要求處理執行前必須事先宣告最大資源需求（Claim edges）。

=== 第 1-(13) 題 ===

核心觀念

本題考驗作業系統中**號誌（Semaphore）**的實現方式（Implementation）及其在單核心與多核心系統下的同步機制差異。

1. Busy Waiting（忙碌等待 / Spinlock） vs. Non-Busy Waiting（非忙碌等待 / Block & Sleep）：
   • Busy Waiting（如 Spinlock）：進程/執行緒在等待 Lock 或 Semaphore 時，持續執行 while 迴圈佔用 CPU。優點是避免了上下文切換（Context Switch）的開銷（Overhead）；缺點是會浪費 CPU 資源（CPU cycles）。在多核心（Multi-core）系統中，若臨界區（Critical Section）非常短暫，Spinlock 是非常有效率的實現方式。
   • Non-Busy Waiting：當 Semaphore 無法取得時，將該進程放入等待佇列（Waiting Queue），並呼叫 block() / sleep() 將其狀態轉為 Waiting/Blocked 狀態，釋放 CPU 供其他進程使用；當資源釋放時，再呼叫 wakeup() 喚醒它。
2. 單核心與多核心系統的臨界區保護（Critical Section Protection）：
   • 單核心系統（Single-core System）：可透過**關閉中斷（Disable Interrupts）**來保證原子性（Atomicity），因為單核心下搶佔（Preemption）完全依賴中斷（如 Timer Interrupt）。關閉中斷後，當前進程即可安全且原子地修改 Semaphore 的計數器（value）與佇列。
   • 多核心系統（Multi-core System）：僅關閉單一核心的中斷無法阻止其他核心同時存取共享記憶體，因此必須使用硬體原子指令（如 Test-and-Set、Compare-and-Swap）配合 Spinlock 來保護 Semaphore 內部的資料結構。

---

解題方法

題目要求選出關於 Semaphore 實現方式中**錯誤（wrong）**的敘述：

1. 分析 Non-busy waiting 是否能在多核心系統使用。非忙碌等待機制（Block/Sleep 佇列）在現代單核心與多核心 OS（如 Linux、Windows、Java 虛擬機）中被廣泛採用。
2. 分析 Spinlock 與 Disable Interrupt 分別適用的系統架構（單核 vs. 多核）。
3. 分析 Java Semaphore 的 acquireUninterruptibly() 的實作機制。

---

選項分析

• (A) The acquireUninterruptibly() method in the Java semaphore is a non-busy waiting implementation：正確。
  Java java.util.concurrent.Semaphore 底層基於 AQS（AbstractQueuedSynchronizer）實現。

核心觀念

本題旨在考查雲端原生（Cloud Native）架構與技術生態系的核心定義及其代表性技術。

根據 Cloud Native Computing Foundation (CNCF) 的官方定義，雲端原生（Cloud Native）技術旨在使用戶能在公有雲、私有雲和混合雲等動態環境中，建構並執行具可擴充性（Scalable）的應用程式。其代表性技術與實踐包括：

1. 容器化（Containers）與容器編排（Container Orchestration）
2. 微服務架構（Microservices）
3. 服務網格（Service Mesh）與不可變基礎設施（Immutable Infrastructure）
4. 可觀測性與軟體遙測（Observability & Software Telemetry）
5. **聲明式 API（Declarative APIs）**與雲端原生設計模式（如 CQRS）

---

解題方法

1. 切入點：判斷各選項所代表的技術、架構模式或通訊協定，是否屬於雲端原生系統（Cloud Native System）的核心元件或常見技術生態。
2. 分析步驟：
   • (A) Kubernetes：微服務與容器編排的雲端原生核心標準。
   • (B) Software Telemetry：雲端原生中實現可觀測性（Observability）不可或缺的技術。
   • (C) MQTT：針對邊緣裝置、資源受限環境（IoT）設計的高效能 Publish/Subscribe 通訊協定，並非專門針對雲端原生系統而設計的技術。
   • (D) CQRS：微服務與分散式資料庫常見的架構設計模式。

---

選項分析

• (A) Kubernetes —— 屬於 Cloud Native 技術

題目解析

題目：
Which of the following is not part of the middleware provided by the OS?
(A) Threading service
(B) Database service
(C) Graphics service
(D) Multimedia service

---

核心觀念

本題考查作業系統架構與**中間軟體（Middleware）**的層級定義。

1. 作業系統核心與服務（OS Kernel & Core Services）：直接管理硬體資源（如 CPU、記憶體、I/O 裝置），並向應用程式提供基礎底層服務。執行緒管理與調度（Threading service）屬於作業系統核心或系統程式庫（System Libraries，如 POSIX Pthreads）的基本功能。
2. 中間軟體（Middleware）：位於作業系統（OS）與應用軟體（Application Software）之間的軟體層。Middleware 的主要作用是提供高階、跨平台的共通服務，協助應用程式開發者處理分散式通訊、資料庫存取、圖形渲染介面、多媒體處理等，而無需從零開發現成的高階功能。

---

解題方法

切入點在於區分「作業系統核心/基礎層服務」與「高階中間軟體服務（Middleware）」：

• 核心/基礎服務：直接處理最底層資源控制（例如 CPU 執行緒排程、記憶體分配）。
• Middleware 服務：建立在 OS 之上，提供特定應用領域的高階抽象服務（如資料庫管理、高階圖形 API、多媒體串流與編解碼）。

經由比較各選項所屬的層級，即可找出「不屬於 Middleware」的選項。

---

選項分析

核心觀念

本題考查作業系統中**中斷處置機制（Interrupt Handling Architecture）與中斷向量表（Interrupt Vector Table, IVT）**的設計初衷與優勢。

當硬體設備或軟體觸發中斷時，CPU 需要知道對應的中斷服務程式（Interrupt Service Routine, ISR）在記憶體中的起始位址。作業系統會在記憶體中維護一張表格（即中斷向量表 IVT），表中每個 entry 存放特定 ISR 的位址。

中斷向量（Interrupt Vector）是以**整數索引（Index / Vector Number）**來標示不同的中斷來源。CPU 收到中斷信號及中斷號碼 $i$ 時，可直接透過簡單的地址加法與乘法偏移計算：
$\text{ISR 位址} = \text{IVT 基底位址} + i \times \text{Entry 大小}$
此機制能在常數時間 $\mathcal{O}(1)$ 內直接查表定位 ISR，而不需進行複雜的字串比對或線性搜尋。

---

解題方法

切入點在於比較「數字索引（Vector Number/Index Offset）」與其他可能的定址機制（如名稱搜尋、串列搜尋等）：

1. 直接定址與常數時間查找：CPU 透過硬體內部暫存器與邏輯電路，取得中斷號碼 $i$ 後即可在幾個 CPU clock cycles 內算出現場位址並跳轉。
2. 硬體處理的時效性需求：中斷發生時通常伴隨著緊急的 I/O 需求或系統例外（Exception），處置過程必須極度迅速以減少中斷延遲（Interrupt Latency）。因此，使用整數索引的最核心目的就是追求速度（Speed）。

---

選項分析

核心觀念

本題考查現代作業系統中**多處理器/多處理程序架構（Multi-process Architecture）**在網頁瀏覽器（以 Google Chrome 為例）的實際應用與各處理程序（Process）的角色分工。

傳統瀏覽器採用單一處理程序架構（Single-process Architecture），若其中一個分頁的 JavaScript 當掉或記憶體洩漏，會導致整個瀏覽器崩潰。現代瀏覽器如 Chrome 改採多處理程序架構，將不同的功能模組拆分至不同的處理程序中，以達到隔離（Isolation）、安全性（Security）與穩定性（Fault Tolerance）的目的。

---

解題方法

切入點在於識別 Chrome 瀏覽器中三大主要處理程序（Process）的職責分工：

1. Browser Process（瀏覽器主處理程序）：負責 UI 介面顯示（如網址列、上一頁/下一頁按鈕）、書籤管理、網路請求（Network I/O）及檔案存取等。
2. Renderer Process（渲染處理程序）：負責解析 HTML、CSS、執行 JavaScript，並將網頁內容繪製/渲染成像素圖像呈現在螢幕上。為了安全性，Renderer Process 會運行在沙盒（Sandbox）環境中，受限制存取系統資源。
3. Plugin Process（外掛處理程序）：負責運行網頁嵌入的外掛程式（例如早期的 Flash、Java Applet 等）。

題目問「哪一種處理程序負責渲染網頁（renders web pages）、處理 HTML 與 JavaScript」，對照上述職責定義即可選出正確答案。

---

核心觀念

本題考查的是 Android 作業系統的處理程序生命週期與重要性階層（Process Importance Hierarchy）。

在 Android 系統中，當系統記憶體（RAM）不足時，Low Memory Killer (LMK) 機制會根據處理程序的重要性階層來決定終止（Kill）處理程序的順序。系統會優先保留與使用者目前互動最密切、最直接相關的處理程序，並優先終止對使用者影響最小的處理程序。

Android 官方將處理程序的重要性由高到低分為以下四個主要階層：

1. Foreground Process（前景處理程序）：使用者目前正在互動的應用程式（如正在操作的畫面、前端正在執行的服務）。
2. Visible Process（可見處理程序）：使用者眼見為憑但未直接互動的處理程序（如被半透明 Activity 覆蓋但仍可看見的畫面，或綁定到可見 Activity 的 Service）。
3. Service Process（服務處理程序）：沒有直觀介面但正在背景執行重要任務的處理程序（如背景播放音樂、背景下載檔案）。
4. Background Process（背景處理程序）：使用者完全看不到且未執行核心服務的處理程序（如按下 Home 鍵後被隱藏的 Activity，保存在 LRU Cache 中）。

---

解題方法

本題要求將四個類別按照 「最重要（The Most Important）到最不重要（The Least Important）」 進行排序。

根據 Android 的重要性階層關係：
$\text{Foreground} > \text{Visible} > \text{Service} > \text{Background}$

將題目給予的編號代入：

• 3. Foreground（最重要）
• 4. Visible
• 2. Service
• 1. Background（最不重要）

核心觀念

本題考查作業系統（Operating System）中記憶體管理（Memory Management）的分頁替換演算法（Page Replacement Algorithm）。

在虛擬記憶體系統中，當 CPU 欲存取的頁面（Page）不在實體記憶體的頁框（Page Frame）中時，會觸發分頁錯誤（Page Fault）。若此時頁框已滿，系統必須根據頁替換演算法選擇一個頁框進行淘汰。

最近最少使用演算法（Least Recently Used, LRU）：

• 核心原則：選擇**最久未被存取（Least Recently Used）**的頁面淘汰。
• 基本原理：基於時間局部性（Temporal Locality），假設最近被存取過的頁面在不久的將來會再度被存取，反之最久未存取的頁面短期內被存取的機率最低。

---

解題方法

我們採用**狀態追蹤表（Page Frame Status Table）**逐一追蹤每個存取步驟。

• 頁框數量：4 個（4-page frame），初始狀態皆為空（Empty）。
• 參考序列（Reference String）：4, 3, 2, 1, 4, 3, 5, 4, 2, 1

逐步推導過程：

1. 存取 Page 4：

   • 頁框內容：[4]
   • 狀態：不在頁框內 $\rightarrow$ Page Fault (1)

2. 存取 Page 3：

   • 頁框內容：[4, 3]
   • 狀態：不在頁框內 $\rightarrow$ Page Fault (2)

3. 存取 Page 2：

   • 頁框內容：[4, 3, 2]
   • 狀態：不在頁框內 $\rightarrow$ Page Fault (3)

4. 存取 Page 1：

   • 頁框內容：[4, 3, 2, 1]
   • 狀態：不在頁框內 $\rightarrow$ Page Fault (4)（此時頁框已滿）

5. 存取 Page 4：

   • 頁框內容：[4, 3, 2, 1]（更新 4 的最近存取時間，最新存取排序為 4, 1, 2, 3）
   • 狀態：已在頁框內 $\rightarrow$ Hit（無 Page Fault）

6. 存取 Page 3：

   • 頁框內容：[4, 3, 2, 1]（更新 3 的最近存取時間，最新存取排序為 3, 4, 1, 2）
   • 狀態：已在頁框內 $\rightarrow$ Hit（無 Page Fault）

7. 存取 Page 5：

   • 目前存取歷史（由舊到新排序）：2, 1, 4, 3。最久未存取者為 Page 2。
   • 將 Page 2 替換為 Page 5。
   • 頁框內容：[4, 3, 5, 1]

核心觀念

本題主要考察**快閃記憶體固態硬碟（Solid-State Disk, SSD）**的物理特性、結構與運作機制。主要包含以下四大關鍵概念：

1. 非揮發性記憶體（Nonvolatile Memory, NVM）：斷電後資料不會遺失的記憶體媒介。
2. 閃存轉換層（Flash Translation Layer, FTL）：位於 SSD 控制器中的軟韌體層，負責邏輯區塊位址（Logical Block Address, LBA）與實體區塊位址（Physical Block Address, PBA）之間的位址映射（Address Mapping）、垃圾回收（Garbage Collection, GC）及損耗平均（Wear Leveling）等管理。
3. 預留空間（Over-provisioning, OP）：SSD 內部預留不受使用者定址的實體儲存空間，專門用於 GC、Wear Leveling 以及 Bad Block 管理，主要目的是提昇寫入效能（Write Performance）與耐用度（Endurance），而非讀取效能。
4. 損耗平均（Wear Leveling）：NAND Flash 區塊的抹除次數有物理上限（P/E cycle count）。Wear Leveling 演算法會將寫入與抹除動作均勻分配到各個實體區塊，防止特定區塊因重複抹除（Repeatedly Erased）過度而提早損壞。

---

解題方法

此題為單選題（Multiple-Choice Question），切入點為檢視關於 SSD 的物理特性、FTL 功能、Over-provisioning 目的以及 Wear Leveling 運作機制的敘述。解題時需特別留意敘述中的關鍵字（如：read/write performance、valid/invalid data、prevent repeated erasure 等），精準找出正確與錯誤的選項。

---

選項分析

• (A) SSD is a kind of nonvolatile memory device

  • 正確。SSD 是由 NAND Flash（快閃記憶體）等非揮發性記憶體晶片組成，即使在電源中斷後，儲存在裡面的資料也不會消失，屬於典型的非揮發性記憶體裝置（Nonvolatile Memory Device）。

• (B) FTL (Flash translation layer) is used to track logical blocks that contain valid data

核心觀念

本題考查 UNIX/Linux 作業系統中的行程生命週期與狀態（Process Life Cycle and States），特別是父子行程（Parent-Child Process）在終止過程中的狀態變化與資源回收機制。

• Orphan Process（孤兒行程）：父行程在子行程尚未結束前就先終止（Parent terminated without calling wait()），導致子行程失去父行程。在 UNIX/Linux 系統中，這些孤兒行程會被 init 行程（PID 為 1，或現代系統中的 systemd）所收養（Adopted），並由 init 代為執行 wait() 以確保資源釋放。
• Zombie Process（殭屍行程）：子行程已經執行完畢終止（Terminated），但其父行程尚未呼叫 wait() 來讀取子行程的離開狀態碼（Exit Status）。此時子行程已釋放記憶體與大部分資源，僅在行程表（Process Table）中留有一個紀錄項（PCB）。
• Daemon Process（守護行程）：在背景執行且獨立於終端機（Terminal）控制之外的長效型系統服務行程。

---

解題方法

根據題意說明：「父行程終止且未呼叫 wait()，留下子行程獨自執行（Parent terminated without calling wait(), leaving the child alone）」。

1. 子行程仍在運行，但失去父行程，此狀況符合「孤兒（Orphan）」的定義。

核心觀念

本題考驗作業系統中 用戶級執行緒（User-Level Thread, ULT） 與 核心級執行緒（Kernel-Level Thread, KLT） 之間的對應模型（Multithreading Models），以及常見系統與語言執行環境（如 Java Virtual Machine, JVM）的實作方式。

主要對應模型包含：

1. 多對一模型（Many-to-One Model）：多個用戶級執行緒對應到一個核心級執行緒。
   • 優點：執行緒管理由用戶空間的程式庫完成，切換與建立速度快，開銷小。
   • 缺點：若有一個執行緒發起系統呼叫而阻塞（Blocking System Call），整個行程都會被阻塞；且無法利用多核心 CPU 進行真正的平行運算（Parallelism）。
2. 一對一模型（One-to-One Model）：每一個用戶級執行緒對應到一個獨立的核心級執行緒。
   • 優點：允許其他執行緒在某個執行緒阻塞時繼續執行；可在多核心系統上實現真正的平行處理。
   • 缺點：建立用戶執行緒時必須同時建立相應的核心執行緒，會產生較大開銷，限制了可建立的執行緒數量。現代作業系統（Linux, Windows）絕大多數均採用此模型。
3. 多對多模型（Many-to-Many Model）：將多個用戶級執行緒多工對應（Multiplex）到小於或等於其數量的核心級執行緒上。
   • 特點：結合上述兩者優點，彈性最高，但實作與排程管理極為複雜。
4. 隱式執行緒（Implicit Threading）：將執行緒的建立與管理交由編譯器或執行階段程式庫（Runtime Library）負責，程式員僅需定義任務（Tasks）。常見技術包括 OpenMP、Grand Central Dispatch (GCD)、Java Fork/Join 框架以及執行緒池（Thread Pools）。隱式執行緒底層通常採用執行緒池機制，將任務指派給有限數量的執行緒執行，常見的基礎執行緒模型依然是現代作業系統預設的 一對一模型（One-to-One），而非複雜的多對多模型。

---

解題方法

本題要求選出「敘述錯誤（false）」的選項。

切入點在於：

1. 辨識現代通用作業系統（如 Windows、Linux）主流採用的執行緒模型。
2. 理解隱式執行緒（Implicit Threading）的本質（通常基於執行緒池，底層為 OS 提供的 One-to-One 執行緒）。
3. 掌握 JVM 在主流作業系統（如 Windows）上的執行緒對應實作。

根據上述觀念逐一檢視各選項敘述之真偽即可找出錯誤選項。

---

選項分析

• (A) One-to-One threading is rarely used in current systems（錯誤，即本題答案）
  • 分析：此敘述與事實完全相反。現代主流作業系統（例如 Windows、Linux、macOS）絕大多數均採用 一對一模型（One-to-One Model） 作為預設的執行緒實作。

核心觀念

本題考查作業系統中中斷處理機制（Interrupt Handling Architecture）、中斷線（Interrupt Lines）、可屏蔽與不可屏蔽中斷（Maskable vs. Non-Maskable Interrupts），以及 x86 體系架構中的常見中斷向量號碼（Interrupt Vector Number）。

1. Interrupt Request Lines (IRQ)：硬體裝置（如 I/O 控制器）透過 CPU 或中斷控制器（如 APIC/8259A）上的專用實體信號線發送中斷請求。
2. Maskable Interrupt (INTR) vs. Non-Maskable Interrupt (NMI)：
   • Maskable Interrupt：CPU 可透過設定中斷旗標（如 x86 的 IF flag，開啟指令 sti，關閉指令 cli）來暫時屏蔽（屏蔽時不立即響應）。
   • Non-Maskable Interrupt (NMI)：用於緊急事件（如記憶體 ECC 錯誤、硬體故障），CPU 無法屏蔽，收到後必須立即處理。
3. Critical Section（臨界區）：臨界區關閉中斷時，僅能 disable 屏蔽中斷（Maskable Interrupts），無法關閉 NMI。
4. x86 保留中斷號碼（x86 Reserved Interrupts）：
   • Interrupt 0：Division by Zero Exception
   • Interrupt 1：Debug Exception / Single Step Exception（硬體單步除錯，非可屏蔽硬體中斷）
   • Interrupt 2：NMI (Non-Maskable Interrupt)

---

解題方法

逐一針對中斷發送機制、中斷關閉權限、臨界區實作原則，以及 x86 架構中斷號碼定義進行觀念判斷：

• 確認硬體與 CPU 之間傳達 I/O 中斷信號的實體介面名稱。
• 判斷 CPU 收到中斷信號後是否受到旗標暫存器設定的影響。
• 分析臨界區保護關閉中斷的範疇（NMI 能否被關閉）。
• 查驗 Intel 處理器的中斷號碼分配表（Interrupt Vector Table / IDT）。

---

選項分析

核心觀念

本題考查分頁替換演算法（Page Replacement Algorithms）與實務作業系統（Linux Kernel）記憶體管理機制的結合。

在理論上，LRU（Least Recently Used） 演算法能有效防止「Belady 悖論」，且在命中率表現上非常優異。然而，嚴格實現 LRU 需要在每次記憶體存取時更新 timestamp 或移動雙向鏈結串列，開銷過高，因此現代作業系統（如 Linux）在實務上採用 LRU 的近似演算法。

Linux 核心使用 雙鏈串列法（Active/Inactive 雙鏈表機制，簡稱 Two-List Strategy 或 Clock/Second-Chance 演算法的延伸變體） 來模擬 LRU 頁面替換行為。

---

解題方法

1. 分析 Linux 記憶體管理實務：
   Linux kernel 將實體頁面劃分為兩個主要列表：Active list（活躍頁面）與 Inactive list（不活躍頁面）。
   • 新讀取或頻繁存取的頁面會留在 Active list。
   • 隨著時間推移未被存取的頁面會降級移至 Inactive list。
   • 當系統發生 Page Fault 且缺乏可用記憶體時，Linux 會從 Inactive list 的末端挑選頁面進行回收／替換。
2. 對照理論演算法：
   這種基於 Active/Inactive 列表與 reference bit（參照位元）的機制，本質上是為了在低維護成本下達到最接近 LRU（Least Recently Used） 的替換效果。

核心觀念

本題考驗作業系統中經典同步問題——**讀者與寫者問題（Readers-Writers Problem）**的變體機制。

讀者與寫者問題主要規範對共享資源（如資料庫、檔案）的存取規則：

1. 多個讀者（Readers）：可同時讀取資源，彼此之間不互斥。
2. 單一寫者（Writers）：寫入時必須獨佔資源，與其他寫者及讀者皆互斥。

根據優先權（Priority）的不同，分為以下兩種主要型態：

• First Readers-Writers Problem（讀者優先）：只要已有讀者在臨界區（Critical Section），後續到達的讀者皆可直接進入，除非沒有讀者在讀取，否則寫者必須持續等待。此型態可能導致寫者飢餓（Writer Starvation）。
• Second Readers-Writers Problem（寫者優先）：一旦有寫者準備好寫入（Ready/Waiting），後續到達的讀者均不得開始讀取，必須等待該寫者完成。此型態可防止寫者飢餓，但可能導致讀者飢餓（Reader Starvation）。

---

解題方法

解答本題時，需掌握 Second Readers-Writers Problem（寫者優先）的鎖（Lock）與訊號量（Semaphore）運作機制：

1. 讀者間的互斥鎖控制：

   • 第一個進入臨界區的讀者負責獲取保護共享資源的資源鎖（例如 rw_mutex 或 wrt）。
   • 後續進入的讀者僅需遞增讀者計數器（read_count），不需要也不應該讓每個讀者都持有獨立阻擋寫者的鎖。
   • 最後一個離開臨界區的讀者才負責釋放該資源鎖，讓等待中的寫者有機會進入。
   • 每個讀者在更新 read_count 時，會短暫取得一個互斥鎖（mutex），但在更新完成後會立即釋放 mutex，絕非「直到所有讀者離開才釋放 mutex」。

2. 寫者優先的排隊機制：

   • 當寫者準備好時，會鎖住讀者進入的通道（例如透過 queue 或 readTry 機制），使得新到的讀者被阻擋在臨界區之外。

根據上述機制逐一核對各選項敘述的正確性。

---

選項分析

• (A) Only one writer can enter the critical section（敘述正確）

核心觀念

本題考驗作業系統中「進程/執行緒同步（Process/Thread Synchronization）」的高階機制：監視器（Monitor） 與 條件變數（Condition Variables, CV） 的設計動機與協同運作原理。

1. Monitor 的基本定義與優點：
   Monitor 是一種高階同步結構（Abstract Data Type / Programming Language Construct），其內部包含共享資料與操作這些資料的函數。Monitor 具備**隱式互斥（Implicit Mutual Exclusion）**特性，保證同一時間最多只有一個進程（Process）能在 Monitor 內部執行函數，從而自動消除競爭條件（Race Condition）。

2. 純 Monitor 的局限性：
   光有「互斥」僅能保證資料存取的安全性，無法解決「條件同步（Condition Synchronization）」問題。當進入 Monitor 的進程發現所需的邏輯條件未滿足（例如：生產者/消費者問題中緩衝區已滿或已空、特定資源暫時不足）時，純 Monitor 機制無法讓該進程妥善等待。

3. Condition Variable 的定位：
   條件變數（Condition Variables）是專門嵌入在 Monitor 內部、用於實現「條件同步」的輔助機制。每個條件變數代表一種等待條件（例如 not_full 或 not_empty），提供 x.wait() 與 x.signal() 兩種核心原子操作。

---

解題方法

回答「在 Monitor 中使用 Condition Variables 的動機與目的」時，應從 Monitor 缺乏條件等待的困境切入，並歸納出以下三大核心目的與運作機制：

1. 解決「互斥」與「等待」的衝突（允許釋放 Monitor 控制權）

• 問題：若進程進入 Monitor 後發現執行條件不成立，它不能在 Monitor 內部以迴圈（Busy Waiting）等待條件改變。因為 Monitor 具有互斥鎖，若該進程佔據 Monitor 不放，其他進程（能夠修改狀態並使條件成立者）將永遠無法進入 Monitor，進而造成死鎖（Deadlock）。
• 機制：當進程呼叫 x.wait() 時，Monitor 會原子性（Atomically）地釋放 Monitor 的互斥鎖，並將該進程放入與條件變數 $x$ 關聯的等待佇列（Waiting Queue）中進入休眠（Blocked）狀態。這允許其他進程進入 Monitor 來改變狀態。

2. 提供「事件觸發與喚醒」機制（Notification Signaling）

• 機制：當另一個進程進入 Monitor 並執行了會使條件成立的操作後，可呼叫 x.signal()。此操作會喚醒一個排隊在條件變數 $x$ 佇列上的阻塞進程，使其重新獲得爭取 Monitor 執行權的資格。
• 語意差別：
  • Hoare 語意（Signal-and-Wait）：發訊者（Signaler）立即釋放 Monitor 鎖並暫停，讓被喚醒者（Wait-ee）立刻執行。
  • Mesa 語意（Signal-and-Continue）：發訊者繼續執行完 Monitor 內的程式碼，被喚醒者則移至 Monitor 入口佇列等待鎖被釋放（此為現代 OS 與 Pthreads 普遍採用的語意）。

3. 避免 Busy Waiting 並提升 CPU 利用率

• 透過 Condition Variables，無法繼續執行的進程會被置入等待佇列並讓出 CPU（Sleep/Block），直到條件被觸發才被喚醒。這完全消除了自旋等待（Spin Waiting/Busy Waiting）帶來的 CPU 資源浪費。

---

選項分析

核心觀念

本題考驗作業系統在**多層分頁記憶體系統（Multi-level Paging System）架構下的有效記憶體存取時間（Effective Memory Access Time, EMAT）**推導與計算。

1. TLB（Translation Lookaside Buffer，轉譯後備緩衝區）存取機制：

   • 虛擬位址轉譯為實體位址時，系統會先查詢 TLB。
   • 若 TLB 命中（Hit）：直接取得實體頁框號碼（PFN），隨後存取一次實體記憶體即可取得目標資料。
   • 若 TLB 未命中（Miss）：必須存取記憶體中的分頁表進行位址轉譯（Page Table Walk），完成轉譯後才能存取實體記憶體取得目標資料。

2. $L$ 層分頁表（$L$-level Page Table）之記憶體存取次數：

   • 當 TLB 未命中時，需要由上而下尋訪 $L$ 層分頁表，每一層分頁表均需存取一次記憶體，故頁表尋訪需花費 $L \times t_{mem}$ 的時間。
   • 完成位址轉譯後，讀取目標資料本身需要額外 $1$ 次記憶體存取（$1 \times t_{mem}$）。
   • 因此，TLB 未命中時的總記憶體存取次數為 $(L + 1)$ 次。

---

解題方法

1. 已知條件定義

• 分頁表層數 $L = 7$
• TLB 命中率 $\alpha = 90\% = 0.9$
• TLB 未命中率 $1 - \alpha = 10\% = 0.1$
• TLB 存取時間 $t_{TLB} = 50\text{ ns}$
• 記憶體存取時間 $t_{mem} = 600\text{ ns}$

2. 通用公式推導

EMAT 為 TLB 命中與 TLB 未命中兩種狀況下存取時間的期望值（加權平均）：

$$\text{EMAT} = \alpha \times \text{Time}_{\text{Hit}} + (1 - \alpha) \times \text{Time}_{\text{Miss}}$$

其中：

• TLB 命中時的總時間 $\text{Time}_{\text{Hit}}$：
  $\text{Time}_{\text{Hit}} = t_{TLB} + t_{mem}$
  （存取 TLB 取得 PFN，再存取實體記憶體讀取資料）

• TLB 未命中時的總時間 $\text{Time}_{\text{Miss}}$：
  $\text{Time}_{\text{Miss}} = t_{TLB} + (L + 1) \times t_{mem}$
  （存取 TLB 確定未命中，經由 $L$ 次分頁表完成位址轉譯，最後進行 $1$ 次實體記憶體資料讀取）

將上述兩式代入 EMAT 公式並化簡：

核心觀念

本題考查分頁系統中的「堆疊演算法」（stack algorithm）與 Belady anomaly。

對同一個 page reference string，若某頁面置換演算法在配置 $n$ 個 page frames 時所保留的頁面集合為 $S_n$，配置 $n+1$ 個 frames 時所保留的頁面集合為 $S_{n+1}$，若永遠滿足：

$$S_n \subseteq S_{n+1}$$

則稱此演算法具有堆疊性，稱為堆疊演算法。

此處的「stack」不是指程式執行時的呼叫堆疊，而是指不同 frame 數量下，記憶體內頁面集合具有巢狀包含關係。

以 LRU（Least Recently Used）為例，將頁面依最近使用時間排序：

$$\text{最近使用} \rightarrow \text{最久未使用}$$

配置 $n$ 個 frames 時，保留排序前 $n$ 頁；配置 $n+1$ 個 frames 時，保留排序前 $n+1$ 頁。因此前者必定是後者的子集合，符合：

$$S_n \subseteq S_{n+1}$$

常見的堆疊演算法包括：

• LRU
• OPT／MIN（最佳置換演算法）

FIFO 通常不是堆疊演算法，因為增加 frame 數量後，頁面淘汰順序可能改變，導致 page fault 反而增加。

解題方法

判斷某 page replacement algorithm 是否為 stack algorithm，可依序檢查：

1. 固定一段 page reference string。
2. 分別模擬配置 $n$ 個與 $n+1$ 個 frames 的情況。
3. 比較兩種情況下記憶體中的頁面集合。
4. 若對所有 reference strings 與所有 $n$ 都有：

$$S_n \subseteq S_{n+1}$$

則該演算法為 stack algorithm。

堆疊演算法的核心性質是「增加 frames 不會淘汰原本仍在較小記憶體配置中的頁面」。因此其 page fault 數量具有單調性：

$$F(n+1) \leq F(n)$$

其中 $F(n)$ 表示配置 $n$ 個 frames 時的 page fault 次數。

也就是說，增加可用記憶體後，page fault 次數只會減少或維持不變，不會增加。

堆疊演算法的效益

1. 避免 Belady anomaly

Belady anomaly 指的是：

增加 page frames 後，page fault 次數反而增加。

FIFO 可能發生此現象；堆疊演算法則不會發生。

對堆疊演算法而言，因為：

$$S_n \subseteq S_{n+1}$$

核心觀念

本題考查**網路安全與網際網路結構（Web Architecture & Network Security）**中關於網路層級劃分的定義。
網際網路（Internet）在資訊檢索與存取權限的層面上，通常劃分為三個層次：

1. 表層網（Surface Web）：能被標準搜尋引擎（如 Google、Bing）索引並公開存取的網頁。
2. 深網（Deep Web）：無法被標準搜尋引擎索引的網路內容（例如：需要登入的電子郵件、銀行帳戶頁面、付費資料庫、醫療紀錄等）。
3. 暗網（Dark Web）：屬於「深網」的一個特定子集（Subset），採用非標準的重疊網路（Overlay Network），必須透過特定軟體、特殊設定或授權（例如 Tor、I2P）才能存取的隱密網路服務。

---

解題方法

本題為問答題，切入點應明確界定暗網（Dark Web）的技術定義、運作機制、網路特性以及與深網（Deep Web）的關係。

評分關鍵說明步驟如下：

1. 精準定義：說明 Dark Web 屬於 Deep Web 的一部分，無法被一般搜尋引擎搜尋。
2. 核心技術機制：說明其建立於重疊網路（Overlay Network）之上，需使用專用加密瀏覽器與通訊協定（如 Tor 瀏覽器的洋蔥路由 Onion Routing Protocol、.onion 虛擬頂級網域）。
3. 主要特性：
   • 高匿名性（High Anonymity）：隱藏使用者與伺服器端（Hidden Services）的真實 IP 位址與地理位置。

核心觀念

本題旨在考驗考生對現代雲端運算與系統管理領域中**架構即程式碼（Infrastructure as Code, IaC）**的定義、核心精神及其所帶來效益的理解。

1. Infrastructure as Code (IaC) 的定義：
   IaC 是一種利用**描述性程式語言或設定檔（Declarative/Imperative Code）**來自動化管理與組態電腦基礎設施（如伺服器、虛擬機、網路、儲存設備、負載平衡器等）的技術手段。它取代了傳統透過手動點擊 GUI GUI 或手動執行命令列（CLI）指令來設定伺服器的方式。
2. 核心範式（Paradigm）：
   • 版本控制（Version Control）：基礎設施設定檔可存放於 Git 等版本控制系統，達成歷史追蹤與團隊協同作業。
   • 可重複性與一致性（Idempotency & Reproducibility）：確保每次部署產生的環境都是完全一致的，避免「環境漂移（Configuration Drift）」。

---

解題方法

本題為敘述型觀念題，解題切入點應分為兩大部分清晰說明：

1. What is IaC?（定義與運作模式）

• 基本定義：IaC 是將 IT 基礎設施的建立、修改與維運過程程式碼化。管理者只需編寫描述目標狀態的檔案（例如 Terraform 的 .tf 檔、Ansible 的 .yml 檔、CloudFormation 範本），再由 IaC 工具自動執行部署。
• 兩種主要模式：
  • 宣告式（Declarative）：定義「最終狀態（Desired State）」，由工具自動計算現狀與目標的差異並執行更新（如 Terraform）。
  • 命令式（Imperative）：定義「執行步驟（How to achieve standard）」，明確指示工具依序執行的命令（如 Bash 腳本、Chef）。

2. Benefits of IaC（IaC 的效益）

答題時建議將效益歸納為以下關鍵構面，切中評分重點：

• 速度與效率（Speed & Efficiency）：透過自動化腳本幾分鐘內即可完成複雜基礎設施的建置，遠勝手動設定。