109 年 國立暨南國際大學資訊工程學系碩士班《計算機結構與作業系統》

核心觀念

作業系統（Operating System, OS）位於應用程式與硬體之間，主要負責兩件事：

1. 提供抽象化的使用介面：將複雜且各異的硬體細節隱藏起來，提供應用程式容易使用的抽象資源。
2. 管理與分配硬體資源：有效控制 CPU、主記憶體、儲存裝置與輸入／輸出裝置，協調多個程式對資源的使用。

這兩項工作也可概括為：

• OS 是「延伸機器」（extended machine）：提供較容易使用的抽象介面。
• OS 是「資源管理者」（resource manager）：分配、保護並回收硬體資源。

解題方法

題目已明確指出 OS 是應用程式與硬體之間的中介程式，因此可從「中介者需要替哪兩方處理什麼問題」切入：

1. 隱藏硬體複雜度，提供抽象介面

應用程式不必直接操作硬碟磁區、控制記憶體晶片，也不必自行處理各種硬體控制器。OS 透過系統呼叫提供統一介面，例如：

• 檔案操作：open、read、write
• 記憶體配置
• 程序建立與終止
• 網路與輸入／輸出操作

因此，應用程式可以使用「檔案」、「程序」、「虛擬記憶體」等抽象概念，而不必知道底層硬體的實作細節。

2. 管理硬體資源

核心觀念

本題考查作業系統中虛擬記憶體（Virtual Memory）管理之請求分頁（Demand Paging）效能分析，核心概念為有效存取時間（Effective Access Time, EAT）。

在請求分頁機制下，記憶體存取過程可分為兩種情況：

1. 無分頁錯誤（Page Fault Rate = $1 - p$）：資料已存在於實體記憶體（DRAM）中，僅需執行一般的記憶體存取。
2. 發生分頁錯誤（Page Fault Rate = $p$）：所需頁面不在實體記憶體中，須觸發 CPU 中斷，由作業系統處理 Page Fault（包含 Trap 處理、將被替換的髒頁寫回外存、將所需頁面從外存讀入記憶體、更新頁表等昂貴操作）。

有效存取時間（EAT）為上述兩種情況存取時間之機率加權期望值，公式如下：
$\text{EAT} = (1 - p) \times T_{\text{hit}} + p \times T_{\text{fault}}$

其中：

• $p$：分頁錯誤率（Page Fault Rate）。
• $T_{\text{hit}}$：未發生分頁錯誤時的記憶體存取時間。
• $T_{\text{fault}}$：發生分頁錯誤時的記憶體存取時間。

解題方法

依據題目給定之已知條件：

• 未發生分頁錯誤的存取時間 $T_{\text{hit}} = 100 \text{ ns}$
• 發生分頁錯誤的存取時間 $T_{\text{fault}} = X \text{ ns}$
• 分頁錯誤率 $p = 0.000005 = 5 \times 10^{-6}$
• 有效存取時間限制條件：$\text{EAT} \le 120 \text{ ns}$

步驟一：列出 EAT 不等式

將變數帶入有效存取時間公式：
$\text{EAT} = (1 - 0.000005) \times 100 + 0.000005 \times X \le 120$

步驟二：展開並簡化數學式

$0.999995 \times 100 + 0.000005 \times X \le 120$
$99.9995 + 0.000005 \times X \le 120$

步驟三：求解 $X$ 的上限

$0.000005 \times X \le 120 - 99.9995$
$0.000005 \times X \le 20.0005$

將係數改以科學記號表示進行計算：
$5 \times 10^{-6} \times X \le 20.0005$

核心觀念

本題旨在考驗作業系統（OS）的「內文切換（Context Switch）」與計算機結構（CA）中「快取記憶體（Cache Performance & Locality）」相互影響的硬體與軟體機制。涉及的核心觀念如下：

1. 時間區域性（Temporal Locality）與工作集（Working Set）：程式近期存取過的資料在不久的將來極可能再次存取。快取記憶體仰賴保留現行行程（Process）的 Working Set 來維持高快取命中率（Hit Rate）。
2. 快取污染（Cache Pollution）與替換（Eviction）：當 CPU 執行權轉移，新行程的指令與資料會進入快取，擠出（Evict）舊行程原本佔據的快取列（Cache Lines）。
3. 冷啟動缺失（Cold-Start / Compulsory Misses）與快取暖機（Cache Warming）：當被暫停的行程重新獲得 CPU 執行權時，其 Working Set 已不在快取中，進而引發一連串強制性缺失（Cache Misses），需要時間重新將資料載入快取。
4. 定址方式與快取清洗（Cache Flush）：在虛擬定址標籤快取（如 VIVT 快取）或缺乏位址空間識別碼（ASID）支援的架構下，跨行程切換位址空間必須強制清空（Flush）快取，避免位址歧義（Homonym）錯誤。

解題方法

說明 Context Switch 對 Cache 效能的影響時，應從「記憶體區域性破壞」、「定址空間與 Flush 開銷」、「記憶體匯流排寫回壓力」三個維度進行系統化剖析：

1. 區域性破壞與快取污染（Cache Pollution）

• 行程 A 執行階段：快取的內容幾乎完全被行程 A 的工作集（Working Set A）佔據，此時快取命中率極高，執行效率最佳。
• Context Switch 發生：作業系統儲存行程 A 的暫存器狀態與 PCB，並將 CPU 控制權移交給行程 B。
• 行程 B 執行階段：行程 B 存取自身的指令與資料（Working Set B）。由於快取容量 $C$ 有限，Working Set B 會不斷將 Working Set A 替換出快取（Eviction），造成「快取污染」。
• 行程 A 重新執行：當 Context Switch 再次切回行程 A 時，行程 A 所需的資料多數已不在快取中，導致快取失效率瞬間飆升（Miss Spike）。行程 A 必須花費額外 CPU 週期重新由主記憶體載入資料，此階段稱為「快取暖機（Cache Warming）」。

2. 虛擬定址與 Cache Flush 開銷

在虛擬記憶體架構中，若快取採用 VIVT（Virtually Indexed, Virtually Tagged） 定址：

• 不同行程的相同虛擬位址（Virtual Address）會指向不同的實體記憶體位址（Homonym 問題）。
• 若硬體未配備 ASID（Address Space Identifier） 或 PCID（Process Context Identifier） 標籤，OS 在執行 Context Switch 更新頁表基底暫存器（如 x86 的 CR3）時，必須發出指令無效化（Invalidate / Flush）全數快取或 TLB。
• Flush 動作會直接使快取命中率瞬間歸零，所有後續存取皆退化為記憶體存取。

3. 寫回策略（Write-back Policy）產生的匯流排擁塞

• 當快取採用 Write-back 策略時，行程 A 寫入資料只會更新快取的 Dirty Bit，不會立即寫回主記憶體。
• 在 Context Switch 後，行程 B 擠壓快取空間時，被覆蓋的 Dirty Cache Lines 必須強制寫回（Write-back）主記憶體。
• 這會在 Context Switch 發生後的短時間內引發大量的記憶體寫入請求，擠爆記憶體匯流排（Memory Bus）頻寬，顯著拉長存取延遲。

選項分析

本題為問答題（非選擇題）。將 Context Switch 影響 Cache 效能的核心機制進行細項歸納與評估：

核心觀念

1. 雙模式運作（Dual-Mode Operation）：
   現代作業系統與 CPU 硬體架構（如 x86、ARM 等）為維護系統安全性與整體穩定性，提供至少兩種執行模式：

   • 使用者模式（User Mode）： Mode Bit 設為 $1$，供一般使用者應用程式執行。
   • 核心模式／特權模式（Kernel Mode / Supervisor Mode）： Mode Bit 設為 $0$，供作業系統核心（OS Kernel）執行，具備存取所有硬體資源與指令集的權限。

2. 特權指令（Privileged Instruction）的定義：
   僅能於核心模式（Kernel Mode）下合法執行的 CPU 指令。其設計目的在於防止使用者程式直接破壞記憶體保護機制、獨占 CPU 資源或任意操控周邊 I/O 裝置。

3. 違規觸發與處理機制（Hardware Trap / Exception）：
   若執行於使用者模式下的程式嘗試執行特權指令，CPU 硬體會立刻捕捉並引發例外／陷阱（Trap / Exception），硬體自動將 Mode Bit 切換為核心模式，並將控制權轉移給作業系統的中斷處理常式（Interrupt Handler）以終止該違規程序，確保系統不受破壞。

解題方法

本題要求列出任意兩種特權指令。答題時除列出具體指令名稱外，應說明其功能及「為何必須設為特權指令」之物理意義：

1. 關閉／啟用中斷指令（Turn Off / Turn On Interrupts，例如 x86 之 CLI / STI）

   • 功能：停止（Disable）或重新啟用（Enable）CPU 響應可屏蔽外部硬體中斷。
   • 設為特權之原因：若開放使用者程式隨意關閉中斷，惡意程式可透過關閉中斷使作業系統的時脈中斷（Timer Interrupt）失效，進而阻止作業系統進行程序搶佔（Preemption）與內文切換（Context Switch），導致該程式獨占 CPU 資源或使系統陷入死鎖。

2. CPU 停機指令（Halt Instruction，例如 x86 之 HLT）

   • 功能：使 CPU 暫停執行指令並進入休眠狀態，直到下一次外部中斷（如時脈中斷或鍵盤輸入）觸發才被喚醒。
   • 設為特權之原因：若使用者程式具備執行停機指令的權限，任何普通應用程式皆可隨時強制硬體 CPU 停止運作，造成全系統癱瘓或拒絕服務（DoS）攻擊。

3. 修改控制暫存器／分頁表基址暫存器指令（Modifying Control / Page Table Base Registers，例如 x86 之 MOV CR3, EAX）

   • 功能：變更當前 CPU 的頁表目錄基底位址，用以切換虛擬位址至實體位址的映射關係。

核心觀念

本題考查計算機結構與作業系統的兩大經典核心觀念：

1. 快取記憶體（Cache Memory）的運作原理與存在價值：
   • 快取的效益並非僅僅取決於「速度快」，更關鍵的是程式執行時具備局部性原理（Locality of Reference）（包含時間局部性與空間局部性）。若缺乏局部性，快取不僅無法提升效能，反而會因尋找 Tag 與快取未命中（Cache Miss）帶來額外延遲。此外，快取在記憶體階層（Memory Hierarchy）中亦扮演調節不同速度元件之間資料傳輸速率落差（Speed Mismatch）的緩衝角色。
2. UNIX 檔案系統（UNIX File System）的結構與 inode 職責：
   • UNIX 檔案系統採離散結構設計，將資料區塊（Data Blocks）、**中繼資料（Metadata）與目錄結構（Directory Structure）**分離。
   • inode（Index Node）：負責儲存檔案的中繼資料，包括檔案類型、存取權限（Permissions）、擁有者（Owner/Group）、檔案大小（Size）、時間戳記（Timestamps）、硬連結數（Link Count）及資料區塊指標（Block Pointers），不包含檔案名稱。
   • 目錄項（Directory Entry / dirent）：目錄在 UNIX 中亦為一種特殊檔案，目錄的資料區塊中儲存著一組組 (檔案名稱, inode 編號) 的映射對（Mapping）。

解題方法

本題為是非題（Yes / No），切入點如下：

1. 子題 (a)：分析句中的絕對化關鍵字「only（僅僅）」。評估快取發揮價值的充分與必要條件。快取速度高於主記憶體是硬體基礎，但若無程式的局部性特徵或記憶體階層的成本效益考量，快取無法發揮整體效能提升的作用，因此該敘述過於片面，判定為 No。
2. 子題 (b)：審視 UNIX 檔案系統架構中 inode 與目錄項（Directory Entry）的分工責任。判斷檔案名稱（Filename）究竟記錄於何處。因為硬連結（Hard Link）機制允許多個不同的檔案名稱指向同一個 inode，若檔案名稱存在 inode 內將無法實現多對一映射，故檔案名稱必存於目錄項而非 inode 中，判定為 No。

選項分析

(a) Cache is useful only because it is faster than memory.

• 分析結果：No（錯誤）
• 詳細說明：
  1. 局部性原理（Locality of Reference）的必要性：
     快取的硬體存取速度雖然高於主記憶體（DRAM），但快取之所以能顯著提升系統平均存取時間（Average Memory Access Time, AMAT），核心原因在於程式執行時存在時間局部性（Temporal Locality）與空間局部性（Spatial Locality）。若程式存取記憶體為完全隨機存取（無局部性），快取的未命中率（Miss Rate）將接近 $100\%$，此時每次存取除了主記憶體延遲外還需加上快取尋找（Tag Check）的時間，系統效能反而比沒有快取時更慢。

核心觀念

本題考查處理器資料路徑中的五種基本模組。作答時要清楚標示每個模組的資料輸入、資料輸出與控制訊號，並說明控制訊號如何決定模組的動作。

解題方法

先辨認模組要完成的功能，再依功能列出所需訊號：選擇資料需要選擇訊號；讀寫儲存體需要位址與讀寫控制；算術運算需要運算元與結果；多筆暫存器需要讀寫位址；解碼則把二進位輸入轉成對應的輸出線。

(a) 多工器（Multiplexor）

資料輸入 D0 ───┐
資料輸入 D1 ───┤
       ⋮        ├──► 多工器 ───► 輸出 Y
資料輸入 Dn−1 ─┘       ▲
                    選擇訊號 S

$n$ 個資料輸入由選擇訊號 $S$ 指定其中一個送至輸出。若有 $n$ 個輸入，選擇訊號至少需要 $\lceil \log_2 n \rceil$ 個位元。

例如二對一多工器的輸出為：

$S=0$ 時輸出 $D_0$；$S=1$ 時輸出 $D_1$。多工器用來在多個資料來源中選出一個，例如選擇 ALU 的運算元來源。

(b) 記憶體（Memory）

位址 Address ─────►┌──────────┐─────► 資料輸出 Data out
資料輸入 Data in ─►│ 記憶體   │
讀取控制 MemRead ─►│          │
寫入控制 MemWrite ►│          │
時脈 Clock ───────►└──────────┘

位址指定要存取的記憶體位置。讀取控制有效時，記憶體將該位址的內容送到資料輸出；寫入控制有效時，記憶體將資料輸入寫入該位址。典型的同步設計會在時脈指定的有效邊緣完成寫入。

若位址寬度為 $k$ 位元，最多可選取 $2^k$ 個位置。作答時要分清楚：位址選位置，資料輸入提供寫入內容，讀寫控制決定操作方向。

(c) 加法器（Adder）

運算元 A ─────►┌────────┐─────► 和 S
運算元 B ─────►│ 加法器 │─────► 進位輸出 Cout
進位輸入 Cin ─►└────────┘

加法器將兩個運算元及可能的進位輸入相加。對單位元全加器而言：

核心觀念

本題旨在考驗計算機系統（Computer Systems / Computer Architecture）中的「語言轉換層級」（Translation Hierarchy / Program Execution Steps）。高階語言（如 C 語言）寫成的原始碼，必須經過一連串軟體工具鏈（Toolchain）與作業系統機制的處理，轉譯並載入為硬體（CPU）能夠直接辨識與執行的二進位機械碼（Machine Code）。

主要涉及的定義與理論框架包含：

1. 語言轉換四階段：編譯器（Compiler） $\rightarrow$ 組合器（Assembler） $\rightarrow$ 鏈結器（Linker） $\rightarrow$ 載入器（Loader）。
2. 符號解析與記憶體位址重定位（Symbol Resolution & Relocation）：如何將不同模組之間的函式呼叫與變數引用進行位址關聯與修補。
3. 程序位址空間配置與執行初始化（Process Address Space & Execution Initialization）：作業系統分配記憶體區段（Text, Data, BSS, Heap, Stack）與設定 CPU 執行上下文（Registers, PC, SP）。

解題方法

本題為經典問答題，作答時採用「系統化流程與結構化剖析」切入：

1. 整體轉換架構：建立轉換鏈的先後順序概念（原始碼 $\rightarrow$ 組合語言 $\rightarrow$ 可重定位物件檔 $\rightarrow$ 可執行檔 $\rightarrow$ 記憶體中運行的程序）。
2. 分項詳細說明：針對題目要求之 Compiler、Assembler、Linker、Loader 四大元件，統一依據「定義與運作機制」、「輸入（Input）」與「輸出（Output）」三要素進行深入論述。
3. 精準使用關鍵技術術語：切入編譯器前後端、組合器兩階段掃描（Two-pass Assembly）、鏈結器符號解析／區段合併、載入器虛擬位址空間配置等閱卷評分重點。

選項分析（專有名詞與階段深度剖析）

1. 編譯器（Compiler）

• 運作機制：
  編譯器負責將人類易讀的高階語言原始碼轉譯為特定指令集架構（ISA，如 x86、RISC-V）的組合語言。其內部處理流程主要分為：
  • 前端（Front-end）：包含詞法分析（Lexical Analysis，切分為 Tokens）、語法分析（Syntax Analysis，建構抽象語法樹 AST）與語意分析（Semantic Analysis，進行型態檢查與變數宣告驗證）。
  • 中間碼產生與最佳化（IR & Optimization）：將 AST 轉為獨立於硬體的中間碼（Intermediate Representation, IR），並進行程式碼最佳化（如消除死碼 Dead Code Elimination、迴圈展開 Loop Unrolling）。
  • 後端（Back-end）：將最佳化後的 IR 轉換為目標 CPU 的組合語言指令，並執行暫存器分配（Register Allocation）。
• 輸入（Input）：高階語言原始碼檔案（High-Level Source Code，例如 main.c）。
• 輸出（Output）：組合語言程式碼檔案（Assembly Language File，例如 main.s 或 main.asm）。

2. 組合器（Assembler）

• 運作機制：
  組合器將組合語言指令一對一轉譯為 CPU 能直接執行的二進位機械碼（Machine Code），並處理虛擬指令（Pseudoinstructions，如將 RISC-V 的 li 擴充指令拆解為實際硬體指令）。經典組合器採用**兩階段掃描（Two-Pass Assembly）**機制：
  • Pass 1：掃描整個組合語言檔，建立符號表（Symbol Table），記錄所有標籤（Labels，如函式名、分支標籤）與其相對記憶體位址偏移量（Location Counter）。
  • Pass 2：參照 Pass 1 建立的符號表，將助記碼（Mnemonics）及運算元轉換為二進位機械碼，並產生重定位資訊（Relocation Information），標示出需由 Linker 後續填入真實位址的位置。
• 輸入（Input）：組合語言程式碼檔案（Assembly Language File，例如 main.s）。
• 輸出（Output）：可重定位物件檔（Relocatable Object Module，例如 main.o 或 main.obj），內含機械碼、初始資料區段、符號表與重定位表。

3. 鏈結器（Linker）

• 運作機制：
  鏈結器將多個獨立編譯產生的可重定位物件檔以及函式庫（Libraries）合併為一個單一的二進位可執行檔。其核心運作包含兩大步驟：
  • 符號解析（Symbol Resolution）：將每個物件檔中未定義的外部符號（如呼叫外部函式 printf 或引用全域變數）與其他物件檔或函式庫中的定義進行對應與綁定。
  • 重定位（Relocation）：將各物件檔中的程式碼區段（.text）、資料區段（.data）等合併至統一且連續的虛擬位址空間中，並依據重定位表修補所有機器指令中的相對／絕對記憶體位址引用。

核心觀念

本題評量計算機效能評估（CPU Performance Equation）的經典公式與影響處理器每指令週期數（Cycles Per Instruction, CPI）的架構因素，出自權威教材 Patterson & Hennessy《Computer Organization and Design》（COD）第一章：

1. 時脈週期時間（Clock Cycle Time, $T_c$）與時脈頻率（Clock Rate, $f$）的關係：

   $$T_c = \frac{1}{f}$$

2. CPU 執行時間公式（CPU Performance Equation）：

   $$\text{CPU Execution Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time} = \frac{\text{IC} \times \text{CPI}}{\text{Clock Rate}}$$

3. CPI 的架構影響因素：
   同一顆處理器在執行不同應用程式時，CPI 會因為記憶體存取行為（快取未命中率）、**分支預測成功率（管線停頓）以及指令層級平行度（ILP）**的差異而產生劇烈變化。

解題方法

(a) 計算表格中的 A、B、C 數值

已知處理器為 Intel Core i7 920，其時脈頻率 $f = 2.66\text{ GHz} = 2.66 \times 10^9\text{ Hz}$。

1. 求 $A$（時脈週期時間 Clock Cycle Time，單位為 $10^{-9}\text{ s}$）：
   由於兩項應用程式皆執行於同一台 2.66 GHz 的電腦上，其時脈週期時間相同：

   $$T_c = \frac{1}{f} = \frac{1}{2.66 \times 10^9\text{ Hz}} \approx 0.3759398 \times 10^{-9}\text{ s} \approx 0.376 \times 10^{-9}\text{ s}$$

   題目表格欄位單位為 $\text{seconds} \times 10^{-9}$，因此：

   $$A = \frac{1}{2.66} \approx 0.376 \quad (\text{或精確表示為 } 0.3759)$$

2. 求 $B$（String processing 的執行時間 Execution Time）：

   • 指令數 $\text{IC}_1 = 2252 \times 10^9$
   • $\text{CPI}_1 = 0.6$
   • 時脈頻率 $f = 2.66 \times 10^9\text{ Hz}$

   帶入 CPU 效能公式：

   $$B = \frac{\text{IC}_1 \times \text{CPI}_1}{f} = \frac{2252 \times 10^9 \times 0.6}{2.66 \times 10^9} = \frac{1351.2}{2.66} \approx 507.97\text{ 秒} \approx 508\text{ 秒}$$

3. 求 $C$（Combinational optimization 的執行時間 Execution Time）：

   • 根據 SPECINT2006 經典基準測試（即 mcf 組合最佳化程式），其 $\text{CPI}_2 = 2.66$，指令數標準值為 $\text{IC}_2 = 336 \times 10^9$。
   • 帶入 CPU 效能公式：
   $$C = \frac{\text{IC}_2 \times \text{CPI}_2}{f} = \frac{\text{IC}_2 \times 2.66}{2.66 \times 10^9} = \text{IC}_2 \times 10^{-9}\text{ 秒}$$
   • 帶入 $\text{IC}_2 = 336 \times 10^9$ 計算：
   $$C = \frac{336 \times 10^9 \times 2.66}{2.66 \times 10^9} = 336\text{ 秒}$$

核心觀念

本題考的是移位加法乘法器：將乘數逐位由低位元開始檢查；若目前最低位元是 $1$，就把目前的被乘數加到部分乘積，再將被乘數左移、乘數右移。32 位元乘數共處理 32 次。

令被乘數為 $A$、乘數為 $B$，使用 64 位元部分乘積 $P$：

• $M$：64 位元被乘數暫存器，初值為 $A$。
• $Q$：32 位元乘數暫存器，初值為 $B$。
• $P$：64 位元乘積暫存器，初值為 $0$。
• $Q_0$：$Q$ 的最低位元。

解題方法

按照圖中的資料路徑，控制單元每回合檢查 $Q_0$；若為 $1$，便透過 64 位元 ALU 將 $M$ 加到 $P$。接著 $M$ 左移一位、$Q$ 右移一位，重複 32 回合。