111 年 國立中正大學資訊工程學系碩士班甲組《計算機系統》

核心觀念

本題考驗作業系統（Operating Systems）中**同步機制（Synchronization Primitives）與硬體原子指令（Hardware Atomic Instructions）**的特性與應用場景。

1. 硬體鎖定指令的本質：
   常見的硬體同步指令如 Test-and-Set (TSL)、Compare-and-Swap (CAS) 或 Load-Linked/Store-Conditional (LL/SC) 等，其主要特性為：

   • 原子性（Atomicity）：由硬體在匯流排（Bus）或快取一致性協定（Cache Coherence Protocol）層級保證「讀取－修改－寫入」為單一不可分割的原子操作。
   • 非特權指令（Unprivileged Instructions）：可在使用者模式（User Mode）下直接執行，無需透過系統呼叫（System Call）切換至核心模式（Kernel Mode）。

2. 忙碌等待（Busy-Waiting）與資源浪費：
   若應用程式直接在使用者空間基於硬體原子指令實作鎖定機制，通常會形成自旋鎖（Spinlock）。當一個執行緒無法取得鎖時，會在迴圈中持續輪詢（Polling）鎖狀態。這種**忙碌等待（Busy-Waiting）**在鎖被佔用時間較長或執行緒競爭激烈時，會持續佔用 CPU 執行無意義的迴圈，從而浪費寶貴的 CPU 週期（CPU Cycles）。

---

解題方法

分析應用程式不直接使用硬體鎖定指令的原因，需從「硬體自旋鎖」與「作業系統同步原語」的比較切入：

1. 自旋鎖（Spinlock）的缺陷：
   直接使用硬體指令實現鎖定時，若臨界區（Critical Section）執行時間較長，等待中的執行緒會處於 Busy-Waiting 狀態，無法將 CPU 資源讓給其他可以工作的程序，導致系統整體效能下降與 CPU 週期浪費。
2. 作業系統原語的優勢：
   高階應用程式通常偏好使用作業系統提供的同步原語（如 Mutex、Semaphore、Condition Variable、Futex 等）。

核心觀念

本題考查作業系統中**行程間通訊（Interprocess Communication, IPC）**的兩種主要機制：**共享記憶體（Shared Memory）與訊息傳遞（Message Passing）**的特性比較。

1. 共享記憶體（Shared Memory）：

   • 建立時需要核心（Kernel）建立共享區段並映射（Mapping）至各行程的虛擬位址空間。
   • 建立完成後，資料交換完全發生於使用者空間（User Space），直接經由記憶體存取（Read/Write）完成，傳輸效率極高且不需要頻繁進行系統呼叫（System Call）。
   • 主要缺點：作業系統核心不會自動提供行程間的存取保護與同步機制。若多個行程同時修改相同記憶體區塊，會產生競態條件（Race Condition），因此應用程式開發者必須自行負責同步機制（Synchronization）（例如使用 Semaphore 或 Mutex）。

2. 訊息傳遞（Message Passing）：

   • 透過系統呼叫（如 send() 與 receive()）將資料複製進出核心區。
   • 優點是作業系統自動負責同步與傳送，安全性高；缺點是每一次傳送都需要進入核心，過頻繁的模式切換（Kernel Transition）會帶來較大的負擔（Overhead）。

---

解題方法

解題切入點在於區分「通訊效率」與「同步責任」：

1. 共享記憶體的主要優點是通訊速度快（不需每次資料傳送都透過 OS 中介）。
2. 但「速度快」帶來的代價是：OS 不再干涉與維護行程存取的順序，因此當多個行程存取同一塊記憶體時，資料一致性（Data Consistency）與互斥（Mutual Exclusion）的責任完全轉移給程式開發者。
3. 若沒有加入適當的同步（Synchronization）機制，將無法保證資料的正確性。故「需要額外的同步機制」是共享記憶體最主要的缺點（Drawback）。

---

選項分析

• (A) It is limited to a small space.
  錯誤。

核心觀念

本題考驗 UNIX 作業系統中**行程控制（Process Control）與系統呼叫（System Call）**的基本機制，特別是 fork() 與 exec() 系列系統呼叫的功能差異。

在 UNIX 作業系統中，新程式的載入與執行被設計為兩個獨立的步驟：

1. 行程的建立（fork）：建立一個新的子行程（Child Process），複製父行程（Parent Process）的位址空間（Address Space）與資源。
2. 程式的載入與覆蓋（exec）：將一個新的可執行檔（Executable File）載入到**當前行程（Current Process）**的位址空間中，覆蓋原本的程式碼（Code/Text）、資料（Data）、堆疊（Stack）與堆積（Heap），並從新程式的進入點（Entry Point，如 main）開始執行。

關鍵特點在於：exec 系統呼叫不會建立新的行程，執行前後的行程識別碼（PID, Process ID）保持不變。

---

解題方法

解題時應從 UNIX 機制中「行程（Process）」與「程式（Program）」的區分切入：

• 行程（Process）：作業系統分配資源與排程的基本動態單位（包含 PID、頁表、檔案描述子等系統資源）。
• 程式（Program）：存放在磁碟上的靜態可執行檔案（包含 Code 與 Data）。

當一個行程呼叫 exec（如 execve()）時：

• 作業系統會釋放並清理該行程現有的記憶體映射（Memory Mapping）。
• 將指定的目標程式檔案載入至該行程的記憶體中。
• 保留原本行程的 PID、開啟的檔案描述子（File Descriptors，若未設定 FD_CLOEXEC）、使用者權限與父子行程關係。
• 將程式計數器（Program Counter, PC）指向新程式的開頭開始執行。

因此，exec 的本質為「在當前行程中啟動並執行一個全新的程式」，符合選項 (E) 的描述。

---

選項分析

• (A) Creates a new empty process.（建立一個新的空行程）
  • 錯誤。exec 不會建立新行程。作業系統也不會單純建立「空」的行程；若要建立新行程，UNIX 是透過 fork() 或 clone() 系統呼叫，且 fork() 建立的是複製父行程狀態的新行程，而非空的行程。

核心觀念

本題考查作業系統中**核心層級執行緒（Kernel-Level Threads, KLT）與使用者層級執行緒（User-Level Threads, ULT）**的特性比較，以及採用核心層級執行緒時的優缺點。

1. 核心層級執行緒（Kernel-Level Threads, KLT）：
   • 執行緒的建立、排程與同步管理完全由作業系統核心（Kernel）負責與維護。
   • 核心感知（Kernel-aware）每一個執行緒的存在，並以執行緒為基本排程單位。
2. 使用者層級執行緒（User-Level Threads, ULT）：
   • 執行緒管理由使用者空間的執行緒函式庫（Thread Library）維護，核心無法感知個別執行緒，僅將整個應用程式視為單一行程（Process）。

---

解題方法

要判斷何者不是核心執行緒函式庫的優勢（NOT an advantage），需對比 KLT 相較於 ULT 或單一執行緒模型所帶來的優缺點：

• KLT 的主要優勢（Advantages）：

  1. 支援多處理器平行運算：核心可將同一個行程中的不同執行緒排程至不同的 CPU／處理核心上真正平行（Parallel）執行。
  2. 單一阻塞不影響全體：當其中一個執行緒執行阻塞式系統呼叫（Blocking Call，例如等待 I/O）時，核心可以切換排程該行程中的其他執行緒，不會導致整個行程停擺。
  3. 簡化併發程式設計模型：相較於多行程（Multi-process）配對跨行程通訊（IPC）的複雜架構，多執行緒共用位址空間能提供更直覺的併發處理。

• KLT 的主要劣勢／額外開銷（Disadvantages / Overhead）：

  1. 管理開銷高：執行緒的控制操作（如建立、同步、切換）皆需經由系統呼叫（System Call）或軟體中斷（Trap/Interrupt）進入核心模式（Kernel Mode）處理，涉及使用者模式與核心模式之間的切換（Mode Switch），造成時間延遲與效能損失。

因此，「函式庫呼叫涉及中斷／模式切換（Library calls involve an interrupt）」屬於 KLT 的效能負擔與缺點，並非優勢。

---

選項分析

• (A) Threads can use multiple CPUs.（執行緒可以使用多個 CPU）
  • 說明：此為 KLT 的優勢。作業系統核心能直接感知每一個 KLT，因此能在多處理器（Multiprocessor）或多核心環境下，將同行程的不同執行緒分配至多個 CPU 同時執行。

核心觀念

本題考查作業系統（Operating System）記憶體管理（Memory Management）中指令與資料的位址綁定時期（Address Binding Times）。

在程式生命週期中，位址會經歷不同型態的轉換：原始碼中的「符號位址（Symbolic Address）」轉為「邏輯／重定位位址（Logical / Relocatable Address）」，最終轉為實際 RAM 上的「實體記憶體位址（Physical Memory Address）」。

依據經典作業系統理論（Silberschatz《Operating System Concepts》），能夠將位址綁定至**實體記憶體位址（Physical Address）**的時間點共有以下三個經典階段：

1. 編譯／程式撰寫時期（Compile Time / Coding Time）：若在編譯前或撰寫程式時已知行程載入實體記憶體的位置，可直接產生絕對程式碼（Absolute Code），在編譯／撰寫時即完成實體位址綁定。
2. 載入時期（Load Time / Loading into RAM）：若編譯時未知載入位置，編譯器會產生可重定位程式碼（Relocatable Code）。當載入器（Loader）將程式寫入實體 RAM 時，會計算實際基底位址並將位址綁定至實體記憶體位址。
3. 執行時期（Execution Time / Process Execution）：若行程在執行期間能在記憶體不同區段間移動（例如 Swapping 或 Dynamic Paging），位址綁定需延遲至執行階段，由硬體 MMU（Memory Management Unit）將邏輯位址動態轉譯為實體記憶體位址。

**連結時期（Link Time）**僅負責將多個目標檔（.o/.obj）與函式庫結合，解析跨檔案的符號並計算檔案內部的相對邏輯位址，此時程式仍在硬碟中尚未載入 RAM，無法綁定至實體記憶體位址。

---

解題方法

本題的切入點在於區分「邏輯位址計算」與「實體記憶體位址（Physical Memory Address）綁定」的時間點差異：

1. 比較各階段的記憶體分配狀態：
   • Coding / Compile Time：程式設計師或編譯器直接指定絕對實體位址（如嵌入式系統絕對定址），此時完成實體位址綁定。
   • Linking：連結器（Linker）合併多個獨立目標模組，確定符號之間的相對偏移量，此階段屬於「邏輯位址空間」的建構，不接觸物理 RAM 位址。
   • Loading into RAM：載入器（Loader）向 OS 申請實體記憶體空間，並將程式碼複製進 RAM 中，完成實體位址綁定。
   • Process execution：行程執行時，CPU 發出邏輯位址經由 MMU 重定位暫存器（$Physical = Logical + Relocation\ Register$）即時對映至實體 RAM 位址。

核心觀念

本題考查作業系統與計算機結構中的分頁（Paging）記憶體管理機制與 TLB（Translation Lookaside Buffer，轉譯後備緩衝區）硬體快取之設計目的。

1. 分頁機制下的多次記憶體存取問題（Multiple Memory Fetch Problem）

在純粹的分頁架構中，行程的邏輯位址空間分割為大小相等的頁（Page），實體記憶體則分割為對應大小的頁框（Frame）。邏輯位址由頁號（Page Number, $p$）與偏移量（Page Offset, $d$）組成。

位址轉換需透過儲存在主記憶體（Main Memory）中的頁表（Page Table）完成。在沒有額外硬體輔助的情況下，存取一個資料或指令需要兩次（或以上）的主記憶體存取：

1. 第一次記憶體存取：利用頁表基址暫存器（Page-Table Base Register, PTBR）定位主記憶體中的頁表，讀取頁號 $p$ 對應的頁表項目（Page Table Entry, PTE），取得頁框號 $f$。
2. 第二次記憶體存取：將頁框號 $f$ 與偏移量 $d$ 組成實體位址，再次存取主記憶體以讀取或寫入目標資料／指令。

若為 $n$ 階分頁（Multi-level Paging），每次位址轉換需存取主記憶體 $n$ 次查詢頁表，加上存取資料本身 1 次，總計高達 $n + 1$ 次主記憶體存取，造成極為嚴重的系統效能瓶頸。

2. 有效記憶體存取時間（Effective Memory Access Time, EMAT）

為了量化此問題與優化效果，定義 EMAT 公式如下：
設主記憶體存取時間為 $m$，TLB 存取時間為 $\epsilon$，TLB 命中率（Hit Ratio）為 $\alpha$：

• 無 TLB 時（單階分頁）：
  $\text{EMAT} = 2m$
• 有 TLB 時：
  $\text{EMAT} = \alpha \times (\epsilon + m) + (1 - \alpha) \times (\epsilon + 2m)$

當 TLB 命中率 $\alpha$ 接近 $100\%$ 時，$\text{EMAT} \approx \epsilon + m$，成功將平均記憶體存取次數從近乎 2 次（或多階下的 $n+1$ 次）降低至約 1 次。

---

解題方法

本題的切入點在於識別「作業系統演化中，為了消除分頁造成的額外主記憶體查詢開銷所加入的專用硬體」。

1. 問題起源：分頁機制將頁表放在主記憶體內，導致「存取一次資料需先存取一次記憶體查表」，即二倍存取延遲（Multiple Memory Fetch）。
2. 解決方案：硬體設計者引入特殊的高速聯想快取記憶體（Associative Cache），稱為 TLB（Translation Lookaside Buffer）。
3. 運作邏輯：
   • 當 CPU 發出邏輯位址時，硬體同時對 TLB 進行平行搜尋（Parallel Search）。
   • 若 TLB Hit：直接在少數幾納秒內取得實體頁框號 $f$，只需存取主記憶體 1 次（讀取實際資料）。
   • 若 TLB Miss：才需要走傳統流程存取主記憶體中的頁表（多一次存取），並將結果更新至 TLB 中。

因此，新增 TLB 硬體能有效解決多重記憶體存取問題。

---

選項分析

核心觀念

1. 基本分頁硬體（Basic Paging Hardware）中的有效／無效位元（Valid-Invalid Bit）

   • 在未引進虛擬記憶體前，硬體分頁表（Page Table）中的 Valid Bit 主要用於存取合法性與保護檢查。
   • Valid ($1$)：代表該頁面屬於該行程（Process）的合法邏輯位址空間（Logical Address Space）。
   • Invalid ($0$)：代表該頁面不屬於該行程的邏輯位址空間（即非法位址存取，會觸發 Addressing Error / Addressing Trap）。

2. 虛擬記憶體／需求分頁（Virtual Memory / Demand Paging）下的意義重定義

   • 在引進虛擬記憶體後，行程的邏輯位址空間允許大於實際的物理記憶體（Physical Memory）大小，頁面可能被暫存於外存（Swap Space / Disk）。
   • 作業系統重構了此位元的意義，兼具「實體存在性（Presence）」的表示：
     • Valid ($1$)：頁面不僅合法，且目前已載入至物理記憶體中（In Memory）。
     • Invalid ($0$)：頁面目前不在物理記憶體中（Not in Memory，可能在外存中或不合法）。
   • 當 CPU 存取 Invalid 的頁面時，記憶體管理單元（MMU）會引發頁面錯誤中斷（Page Fault Trap），由作業系統將所需的頁面從外存載入至主記憶體。

---

解題方法

• 題意剖析
  題目指出：在傳統分頁硬體中，Valid Bit 設為 Invalid 時原先代表「該頁面不屬於行程的邏輯位址空間」。當在其上實作虛擬記憶體（Virtual Memory）後，改變了該位元的意義，請問此位元現在代表什麼？

• 推導過程
  在需求分頁（Demand Paging）機制中，頁面不需要全部預先載入主記憶體。MMU 在進行位址轉換時，必須快速判斷該頁面是否在主記憶體內：

  • 若 Valid Bit 標示為 Invalid ($0$)，存取該頁面時將觸發 Page Fault。
  • 這表示作業系統需要處理中斷，將該頁面從外存（Disk）調入主記憶體中（Page-in）。
  • 因此，在虛擬記憶體架構下，Valid Bit 最關鍵的新功能即為反映「頁面目前是否在記憶體中（In-Memory Status）」。

---

選項分析

核心觀念

本題考查作業系統（Operating System）中**分頁記憶體管理（Paged Memory Management）**的基本架構與頁表（Page Table）配置原則。

1. 資源配置單位：程序（Process）是作業系統進行資源分配（包含記憶體空間）的基本單位。為了確保程序間的記憶體保護（Memory Protection）與獨立性，作業系統會為每個程序提供一份獨立的邏輯／虛擬位址空間（Logical/Virtual Address Space）。
2. 位址轉譯機制：將邏輯頁面（Page）對映到實體頁框（Frame）的轉譯工作由頁表（Page Table）負責。由於每個程序的虛擬位址映射關係皆不相同，作業系統必須為每一個程序維護一份獨立的頁表。
3. 執行緒共享性：執行緒（Thread）是 CPU 排程的基本單位。同一程序內的所有執行緒共享該程序的邏輯位址空間，因此共用同一份頁表。

---

解題方法

分析單階分頁（Single-level Paging）記憶體系統的運作機制：

1. 程序的獨立位址空間：
   在標準單階分頁系統中，若系統目前有 $N$ 個獨立程序正在執行，由於各程序的虛擬位址 $0 \sim 2^m-1$ 映射到的實體記憶體位置不同，作業系統必須建立 $N$ 份頁表。因此頁表數量為「每個程序一份」（One per process）。

2. CPU 與暫存器角色：
   CPU 內部設有頁表基底暫存器（Page Table Base Register, PTBR，例如 x86 架構中的 CR3 暫存器）。當 CPU 進行程序切換（Context Switch）時，作業系統會更新 PTBR 的值，使其指向「當前正在執行的程序」之頁表基底位址。這代表 PTBR 暫存器的數量與 CPU 數量相關，但儲存在主記憶體中的頁表實體數量仍隨程序數量增減。

---

選項分析

核心觀念

• 日誌型檔案系統（Log-based / Journaling File System）：
  在傳統檔案系統中，若系統在更新檔案結構（如分配磁碟區塊、修改 Inode、更新目錄項目等）時突發斷電或系統崩潰，極易造成檔案系統元資料（Metadata）的不一致（Inconsistency）。傳統解法需要於重啟時執行耗時的全磁碟檢查（如 fsck）。
• 交易與可靠性（Transaction & Reliability）：
  日誌型檔案系統引入資料庫的「交易（Transaction）」概念。在將元資料變更實際套用到磁碟資料結構前，先將這些變更按順序記錄於專門的日誌區塊（Log / Journal）中。若遭遇突發中斷，系統重啟時僅需掃描並重播（Replay）或撤銷（Undo）日誌中未完成的交易，即可在極短時間內恢復檔案系統的結構一致性，顯著提升系統的可靠性（Reliability）。

---

解題方法

本題考查作業系統（Operating Systems）中檔案系統實作與崩潰恢復機制的基本定義。

解題切入點在於區分「日誌檔案系統的核心設計目的」與「日誌記錄的涵蓋對象」：

1. 設計目的：日誌機制的核心價值在於維護檔案系統結構的一致性與可靠性（Crash Consistency / Reliability），而非用於安全稽核或存取控制。
2. 記錄對象：典型的日誌型檔案系統（如 ext3/ext4 預設的 ordered 模式、NTFS、XFS 等）主要針對**元資料更新（Metadata updates）**進行日誌交易記錄。雖然部分系統支援全資料日誌（Data Journaling），但記錄所有檔案實際內容（Data）會帶來嚴重的效能下降與儲存負擔，因此日誌檔案系統最基礎且核心的功能為「記錄元資料更新的交易」。

綜合上述，選項 (A) 的敘述最準確且符合作業系統標準教材的定義。

---

選項分析

• (A) Log transactions of file system metadata updates to increase reliability.（正確）

核心觀念

本題考查資訊安全與密碼學（Network Security & Cryptography）中**數位簽章／訊息簽署（Digital Signature / Message Signing）**的核心功能與安全目標。

數位簽章主要基於非對稱加密技術（Asymmetric Cryptography），其設計旨在達成資訊安全的以下關鍵目標：

1. 身份驗證（Sender Authentication）：確認訊息確實來自特定發送者。
2. 不可否認性（Non-repudiation）：發送者事後無法否認自己曾發送過該訊息。
3. 資料完整性（Data Integrity）：確保訊息在傳輸過程中未遭篡改（具備篡改偵測能力）。

---

解題方法

訊息簽署的運作機制如下：

• 簽署階段：發送者使用自己的**私鑰（Private Key）**對訊息摘要（Message Digest，即經雜湊函數產生的 Hash 值）進行加密計算，生成數位簽章並隨訊息一同傳送。
• 驗證階段：接收者使用發送者的**公鑰（Public Key）**解密簽章取得摘要，並與自行針對收到的訊息計算出之摘要進行比對。

由上述機制切入分析：

• 驗證發送者：公鑰解密成功即證明該簽章必定由相應私鑰持有者所產生，因此能確認發送者身份（選項 A 正確）。
• 不可否認性：由於私鑰僅由發送者獨家持有且不可洩漏，第三方無法偽造其簽章，發送者便無法事後推翻與否認（選項 B 正確）。
• 篡改保護機制：數位簽章提供的是對傳輸過程的「篡改偵測（Tamper Detection）」，而非實體上「阻止／防止修改（Prevention of Modification）」。接收者收到訊息後，簽章機制無法限制本機端對資料進行改寫，僅能確保改寫後無法通過簽章驗證（選項 C 錯誤）。

---

選項分析

• (A) It verifies the sender.
  • 正確。訊息簽署使用發送者的私鑰進行加密。

核心觀念

本題考查作業系統中**虛擬化技術（Virtualization）與虛擬機（Virtual Machines, VMs）**的基本定義與作用。

虛擬機器監視器（Virtual Machine Monitor, VMM，或稱 Hypervisor）透過將實體硬體資源（CPU、記憶體、儲存空間與 I/O 裝置）進行抽象化與隔離，建立出多個虛擬的硬體環境。這使得不同的作業系統（Guest OS）能夠同時且獨立地運行於同一台實體硬體主機（Host Machine）之上。

---

解題方法

本題屬於觀念辨析題，解題切入點在於精確對應題目給定的情境與技術定義：

1. 關鍵條件：題目尋求能「在同一台機器上（on the same machine）同時運行多個作業系統（run multiple operating systems at the same time）」的技術。
2. 邏輯推導：若要在單一硬體上運行多個作業系統，系統必須提供作業系統層級之下的硬體抽象層（VMM / Hypervisor），讓每個 Guest OS 均認為自己獨佔一套完整的硬體資源。此機制即為**虛擬機（Virtual Machines）**技術。

---

選項分析

• (A) Interrupt Vectors（中斷向量表）：錯誤。中斷向量表是記憶體中一塊連續的位址陣列，專門儲存各個中斷處理程式（Interrupt Service Routine, ISR）的進入點位址。當硬體或軟體觸發中斷時，CPU 藉由查詢中斷向量表跳轉至對應程式，其功能為處理中斷事件，與同時運行多作業系統無關。
• (B) Virtual Machines（虛擬機）：正確。

選項解析

• (A) Tagged queuing (NCQ)：允許磁碟控制器動態重排讀寫指令順序，以最小化磁頭尋道時間（Seek Time）與旋轉延遲（Rotational Latency），屬於提升磁碟 I/O 效能的機制。
• (B) Disk hardware buffering：利用硬碟控制器上的快取記憶體（Disk Cache）預讀或暫存資料，減少磁碟機件的實體讀寫次數，屬於提升效能的機制。

核心觀念

本題考查作業系統（Operating System, OS）的架構定義與**核心（Kernel）**的基本特性。

1. Kernel（核心）的定義：依據 Silberschatz 所著之經典教科書《Operating System Concepts》（俗稱恐龍書）定義：「在電腦上**始終持續執行（always running / memory-resident）**的那一個程式即為核心（Kernel）。」
2. 記憶體常駐性（Memory-Resident）：電腦開機進行自檢與載入（Bootstrapping）後，作業系統核心會載入至受保護的記憶體區段（Kernel Space）中，直到關機前都永遠常駐於記憶體內，負責存取硬體、管理系統資源（CPU、記憶體、I/O 裝置）以及提供系統呼叫（System Calls）。
3. 使用者空間與系統程式（User Space & System Programs）：非 Kernel 本身的系統軟體（如 Shell、GUI 介面、應用程式）則運作於使用者空間（User Space），僅在需要時才載入記憶體執行。

---

解題方法

本題切入點在於識別何者為作業系統開機後**「永遠常駐於記憶體（Always in memory）」**的核心主體：

1. 電腦開機後，韌體（BIOS/UEFI）會執行 Boot Loader，將作業系統的核心（Kernel）載入記憶體。
2. 核心載入完成並初始化後，便會接管整台電腦的硬體控制權，並轉為常駐狀態。
3. 題目詢問的是「開機後永遠停留在記憶體中的那一部分 OS」，完全吻合 Kernel 的標準定義。

---

選項分析

• (A) Shell（錯誤）
  Shell 是作業系統的命令直譯器（Command Interpreter），屬於使用者空間（User Space）的系統工具程式（System Utility）。

核心觀念

本題考驗作業系統（OS）與裝置控制器（Device Controller）之間的 I/O 溝通機制與參數傳遞。

當 CPU／作業系統要指示裝置控制器執行一項 I/O 操作（不論是透過程式化 I/O 或 DMA 方式）時，必須寫入裝置控制器的暫存器（如 Command Register、Data Register 等）。控制器運作時必須具備以下四大關鍵參數：

1. 操作型態（Operation Type / Control Command）：告訴控制器要執行什麼動作（例如：$Read$、$Write$、$Seek$、$Reset$）。
2. 主記憶體位址（Memory Buffer Address）：告知控制器傳輸資料的記憶體起點位址（資料讀取後要放入 RAM 的哪裡，或是要從 RAM 的哪裡抓取資料寫入裝置）。
3. 裝置儲存位址（Device Storage Address）：告知控制器在硬體裝置上的存取位置（例如：硬碟的邏輯區塊位址 LBA / Block Address 或 Sector Number）。
4. 傳輸數量（Byte / Sector Count）：指定本次 I/O 操作需要傳輸的資料大小與長度。

中斷號碼（Interrupt Number / IRQ）的角色與運作時機：
中斷號碼（IRQ / Interrupt Vector）是用於 CPU 識別中斷來源的機制。當裝置控制器完成 I/O 操作後，會向中斷控制器發起中斷訊號（Interrupt Signal），CPU 根據中斷號碼查閱中斷向量表（Interrupt Vector Table, IVT）以觸發對應的中斷處理常式（ISR）。中斷號碼屬於硬體線路連接與驅動程式初始化時的配置，並非 CPU 每次發送 I/O 命令時需要傳遞給控制器的操作參數。

---

解題方法

分析 CPU 啟動一筆 I/O 任務時所需傳遞資訊的邏輯：

1. 動詞（操作）：CPU 必須傳送命令型態（Operation control / type），否則控制器無法得知要做 Read 還是 Write。
2. 來源與目的位址（資料傳輸路徑）：
   • 裝置側：需要知道存取裝置上的哪個區塊（Device storage address）。
   • 記憶體側：需要知道資料暫存的記憶體緩衝區（Memory buffer address）。
3. 區分資訊流向：

核心觀念

本題考查計算機架構與作業系統中**記憶體階層（Memory Hierarchy）與快取機制（Caching）**運作的核心基礎理論：參考區域性（Locality of Reference）。

快取（Cache）之所以能在各種階層（如 CPU Cache、TLB、Page Cache、Web Cache 等）以極小容量獲得極高的命中率（Hit Rate），其軟硬體上的理論基礎在於程式碼在執行時對記憶體空間與時間的存取並非完全隨機，而是具備以下兩大區域性特徵：

1. 時間區域性（Temporal Locality）：若某個資料或指令被存取，則該項目在不久的將來極有可能被再次存取（例如：迴圈變數、重複呼叫的函式）。
2. 空間區域性（Spatial Locality）：若某個資料或指令被存取，則其相鄰位址的資料或指令在不久的將來極有可能被存取（例如：連續存取的陣列、順序執行的程式碼指令）。

---

解題方法

在計算機系統設計中，速度越快的儲存介面（如 SRAM）成本越高、容量越小；速度越慢的儲存介面（如 DRAM、Disk）成本越低、容量越大。為達成「接近最高速介面的存取速度」同時兼具「接近最低速介面的容量與成本」，系統採用階層式記憶體架構。

若程式的存取行為呈現完全隨機分佈，則任何小型快取的命中率都會趨近於零，引進快取不僅無法提升效能，反會因額外的快取尋找開銷（Cache Overhead）而降低效率。正因為程式普遍存在參考區域性（Locality of Reference），系統才能將近期最有可能被存取的資料預載至高速且小容量的快取中，滿足絕大部分的資料請求，進而顯著降低平均記憶體存取時間（AMAT, Average Memory Access Time）：

$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$

第 2 題

(1) Dynamic Loading 與 Dynamic Linking

核心觀念

• Dynamic Loading（動態載入）：程式執行期間，只有在某個程式模組實際被需要時，才將該模組載入記憶體。
• Dynamic Linking（動態連結）：程式執行期間才解析外部函式或共享函式庫的參照，將程式碼與共享函式庫連結起來。

解題方法

判斷重點在於：

• Dynamic loading 關心「何時把模組放入記憶體」。
• Dynamic linking 關心「何時解析外部符號並建立函式庫連結」。

兩者經常同時使用，但概念不同；動態載入可延後記憶體使用量，動態連結則可讓多個程式共享同一份函式庫。

解題技巧

看到 loading，聯想到「模組是否載入記憶體」；看到 linking，聯想到「外部符號、函式庫與位址解析」。

【答案】Dynamic loading 是程式執行期間，在模組真正需要時才將其載入記憶體；dynamic linking 則是在執行期間才解析外部函式或共享函式庫的參照並完成連結。前者重點是延後載入，後者重點是延後符號解析與函式庫連結。

---

(2) Processor Affinity 的目的

核心觀念

Processor affinity（處理器親和性）是限制行程或執行緒只能在指定的處理器集合上執行，或偏好在某一顆處理器上執行。

解題方法

行程在多核心系統中遷移到另一顆處理器時，原本處理器的快取內容可能無法直接使用，會增加 cache miss 與快取重新建立的成本。因此，設定 processor affinity 可以減少不必要的處理器遷移，提升快取區域性與執行穩定性。

此外，processor affinity 也能用於：

• 將特定工作固定在指定核心。
• 隔離高負載工作，避免影響其他工作。
• 改善即時系統的可預測性。

解題技巧

核心關鍵字是「減少 migration、提升 cache locality」，不是單純將所有工作平均分配到各核心。

【答案】Processor affinity 用來將行程或執行緒綁定至指定處理器，或使其偏好在指定處理器上執行。其主要目的為減少處理器遷移造成的快取失效與額外成本，並可提升效能、隔離負載及增加執行時間的可預測性。

---

(3) Priority Inversion

核心觀念

核心觀念

本題考查計算機架構中衡量 CPU 效能的核心指標與經典模型——CPU 效能方程式（CPU Performance Equation），以及指令集架構（ISA）設計對該方程式各參數影響的定性分析。

關鍵公式與變數定義：

1. CPU 執行時間（CPU Execution Time）：執行特定程式所消耗的 CPU 時間。
2. 指令數（Instruction Count, $IC$）：程式執行過程中所執行的總指令數量。
3. 每指令平均週期數（Clock Cycles Per Instruction, $CPI$）：執行每條指令平均所需的時脈週期數。
4. 時脈週期時間（Clock Cycle Time, $CCT$）：單一時脈週期的持續時間，為**時脈頻率（Clock Rate / Frequency, $f$）**的倒數（即 $CCT = \frac{1}{\text{Clock Rate}}$）。

CPU 效能方程式將 CPU 執行時間分解為三個關鍵項目的乘積：
$\text{CPU Execution Time} = \text{Instruction Count} \times \text{CPI} \times \text{Clock Cycle Time}$
或表示為：
$\text{CPU Execution Time} = \frac{\text{Instruction Count} \times \text{CPI}}{\text{Clock Rate}}$

---

解題方法

本題分為兩個小題：

1. 第 (1) 小題：根據提示 CPU execution time = ? * ? * ?，精確寫出 CPU 效能方程式的三個組成要素：$\text{Instruction Count}$、$\text{CPI}$ 與 $\text{Clock Cycle Time}$。
2. 第 (2) 小題：分析新增「乘加指令（Multiply-Accumulate, MAC）」（如 Rd += Rs * Rt）取代原本獨立的「乘法」與「加法」指令對方程式中三個參數 ($IC$, $CPI$, $CCT$) 的影響：
   • 指令數（Instruction Count, $IC$）：原本需要兩條指令（乘法與加法）的運算被合併為一條 MAC 指令，在 AI 矩陣運算或向量內積等頻繁使用 MAC 的情境下，動態執行的總指令數 $IC$ 會顯著下降（減少）。
   • 每指令平均週期數（$CPI$）：MAC 指令通常是較複雜的複合指令，其單一指令所需的時脈週期數往往高於單純的加法指令；且新增複雜指令可能導致流水線（Pipeline）結構變複雜、資料相依性或停頓（Stall）風險增加。因此，全程式的平均 $CPI$ 可能會上升（增加）。
   • 時脈週期時間（Clock Cycle Time, $CCT$ / 時脈頻率 Clock Rate）：新增 MAC 硬體執行單元（如硬體乘加器）可能會增加組合邏輯的最長臨界路徑（Critical Path）。若臨界路徑變長，則時脈週期時間 $CCT$ 會變長（即時脈頻率 Clock Rate 下降）；但若設計良好且臨界路徑由其他模組決定，或採用多階段流水線（Pipelined MAC），時脈週期時間亦可能保持不變（變長或不變）。

---

選項分析

本題為簡答與觀念分析題（非選擇題），針對第 (2) 小題中 CPU 效能方程式的三個核心參數受 MAC 指令引入後的影響進行深入剖析：

1. 對 Instruction Count ($IC$) 的影響：
   • 分析：降低（Decreased）。

核心觀念

1. 管線冒險（Pipeline Hazard）的定義：
   在管線化（Pipelining）處理器中，當下一條指令因為硬體資源衝突、資料相依性或控制流程改變，導致無法在預定的時脈週期（Clock Cycle）內順利執行後續階段時，稱為管線冒險。冒險會強迫管線插入停頓（Stall / Bubble）或沖刷（Flush）指令，導致平均每指令週期數 $CPI > 1$，降低處理器效能。

2. 管線冒險的三大分類：

   • 結構冒險（Structural Hazard）：多條指令在同一週期內競爭相同的實體硬體資源（如同時存取單一記憶體埠）。
   • 資料冒險（Data Hazard）：指令所需的運算元（Operand）尚未被前方的指令計算完成或寫回暫存器（如寫後讀 RAW 相依性）。
   • 控制冒險（Control Hazard）：分支（Branch）或跳躍（Jump）指令尚未確定目標位址或判斷條件前，管線已擷取了後續指令。

3. 管線深度與冒險處罰（Pipeline Depth vs. Hazard Penalty）：
   將 5 階段管線中的 ID 拆解為 ID1 與 ID2 兩階段後，管線總深度由 5 階變為 6 階（IF $\rightarrow$ ID1 $\rightarrow$ ID2 $\rightarrow$ EX $\rightarrow$ MEM $\rightarrow$ WB）。管線深化雖可提升時脈頻率，但會拉長資料產生階段與資料消費階段之間的週期距離，導致分支處罰週期與資料相依停頓週期增加。

---

解題方法

1. 第 (1) 小題：給出管線冒險的完整標準定義，並列出三大類別與其成因。
2. 第 (2) 小題：對比原 5 階段管線（IF / ID / EX / MEM / WB）與新的 6 階段管線（IF / ID1 / ID2 / EX / MEM / WB），分析 ID 拆分為兩階段後所產生的額外冒險或處罰週期增加：
   • 分析 1：控制冒險處罰增加（Control Hazard Penalty）
     假設分支目標與條件判斷位於 ID2 階段（Stage 3），當確定分支成立（Branch Taken）時，IF（Stage 1）與 ID1（Stage 2）皆已擷取錯誤指令，沖刷（Flush）數量由 1 條增至 2 條。
   • 分析 2：ALU 至 Branch 資料冒險停頓增加（ALU-to-Branch Data Hazard）
     若分支條件在 ID2 判斷，前一條 ALU 指令在 EX 算出結果，兩者相隔週期變長，需要額外的 Stall 週期等待前饋（Forwarding）。
   • 分析 3：無前饋架構下 RAW 資料冒險停頓增加（RAW Hazard without Forwarding）
     寫回階段移至 Stage 6（WB），若在 Stage 3（ID2）讀取暫存器，等待寫回所需的停頓週期從 2 個增至 3 個週期。
   • 分析 4：結構冒險隱患（Structural Hazard）
     若 ID1 解碼與 ID2 暫存器讀取 shared 匯流排或控制埠未完全解耦合，可能衍生暫存器檔案或解碼邏輯的存取衝突。

---

子題詳解與指令序列

(1) What is a pipeline hazard?

管線冒險（Pipeline Hazard）是指在管線化處理器中，下一條指令因以下三種原因之一，無法在預定的時脈週期內執行：

1. Structural Hazard（結構冒險）：硬體資源缺乏，導致多條指令在同一週期內爭奪同一個硬體元件。
2. Data Hazard（資料冒險）：指令需要的運算元尚未由前方未完成的指令寫回或前饋（例如 RAW 寫後讀相依性）。
3. Control Hazard（控制冒險）：分支或跳躍指令尚未確定下一條指令的實際目標位址。

冒險會導致管線插入「氣泡/停頓（Bubble/Stall）」或進行「沖刷（Flush）」，使得處理器無法維持理想的 $CPI = 1$。

---

(2) Additional Hazards in 6-stage Pipeline (IF / ID1 / ID2 / EX / MEM / WB)

將 ID 階段分割為 ID1（Instruction Decode）與 ID2（Register Read）後，管線變為 6 階段。額外可能發生或懲罰加重的冒險如下：

1. 控制冒險的處罰週期增加（Increased Control Hazard Penalty）

• 說明：假設分支判斷與目標位址計算在 ID2 階段（Stage 3）完成。當分支確定成立（Taken）時，管線中處於 IF（Stage 1）與 ID1（Stage 2）的 2 條指令均為錯誤擷取的指令，必須將其沖刷（Flush）。分支處罰（Branch Penalty）從原 5 階段管線的 1 個週期增加為 2 個週期。
• 指令序列（Instruction Sequence）：

  I1: beq  $s0, $s1, L1    # 分支指令 (在 ID2 決定 Taken)
  I2: add  $t0, $t1, $t2    # 錯誤擷取指令 (需在 ID1 沖刷)
  I3: sub  $t3, $t4, $t5    # 錯誤擷取指令 (需在 IF 沖刷)
  L1: lw   $s2, 0($t6)      # 正確的分支目標指令
  

• 時脈週期圖解：

核心觀念

本題考查分支預測中的 BHT（Branch History Table，分支歷史表），以及 1-bit 與 2-bit 分支預測器的更新機制。

當處理器遇到條件分支指令時，分支結果尚未真正計算完成。為了避免流水線停頓，處理器會先預測分支結果：

• Taken（T）：分支成立，跳轉至目標位址。
• Not Taken（N）：分支不成立，繼續執行下一條指令。

若預測錯誤，處理器必須清除錯誤路徑上的指令並重新取指，因而產生分支預測失誤成本。

---

(1) What is BHT?

BHT 是由許多表格項目組成的硬體結構，每個項目記錄某個分支指令最近的行為，用來預測該分支下一次會不會跳轉。

BHT 通常以分支指令的部分 PC 位址作為索引：

$$\text{BHT index} = \text{Branch PC 的部分位元}$$

查表後，處理器根據該表項目的內容預測分支結果。分支實際執行完成後，再依照正確結果更新 BHT。

1-bit BHT

最簡單的 BHT 每個表項只儲存 1 個 bit：

• $1$：預測 Taken
• $0$：預測 Not Taken

更新規則為：

$$\text{下一狀態} = \begin{cases} 1, & \text{實際結果為 Taken} \\ 0, & \text{實際結果為 Not Taken} \end{cases}$$

因此，1-bit 預測器會直接記住「上一次的分支結果」，下一次預測與上一次相同。

2-bit BHT

2-bit BHT 通常使用 2-bit 飽和計數器（saturating counter），共有四種狀態：

狀態	意義	預測
$00$	Strongly Not Taken	N
$01$	Weakly Not Taken	N
$10$	Weakly Taken	T
$11$	Strongly Taken	T

其更新方式如下：

• 實際結果為 Taken：狀態增加 1，但最高停在 $11$。
• 實際結果為 Not Taken：狀態減少 1，但最低停在 $00$。
• 預測結果由最高位決定：
  • $00$、$01$ 預測 N
  • $10$、$11$ 預測 T

2-bit BHT 的關鍵特性是：一次相反結果通常不足以改變原本的預測方向。因此，它比 1-bit BHT 更能抵抗偶發的分支結果變化。

---

(2) 為何 2-bit BHT 可能比 1-bit BHT 有較佳效能？

考慮以下迴圈：

for (i = 0; i < 3; i++) {
    body();
}

假設迴圈條件分支每次檢查的實際結果為：

$$T,\ T,\ T,\ N,\ T,\ T,\ T,\ N,\ \ldots$$

其中：

• 前三次為 $T$：繼續執行迴圈。
• 第四次為 $N$：離開迴圈。
• 下一輪迴圈重新開始後，又重複相同模式。

1-bit BHT 的情況

假設 1-bit BHT 一開始預測 N。

第一輪的預測情形如下：

次序	實際結果	預測	是否錯誤	更新後狀態
1	T	N	錯誤	T
2	T	T	正確	T
3	T	T	正確	T
4	N	T	錯誤	N

第一輪有 2 次預測錯誤。

下一輪開始時，BHT 上一次因離開迴圈而記錄為 N：

次序	實際結果	預測	是否錯誤	更新後狀態
1	T	N	錯誤	T

1. 本題測驗的核心概念

本題主要在考查 直接映射快取 (direct‑mapped cache) 的 映射規則、快取塊大小 (block size) 以及 三類快取未命中 (3C)——

1. Compulsory miss（首次存取必然未命中）
2. Capacity miss（快取容量不足，即使是全相聯也會未命中）
3. Conflict miss（映射衝突，容量足夠但因映射限制而未命中）

解題時必須先把記憶體位址轉換成 快取行號，再依序判斷每一次的未命中屬於哪一類。

---

(1) 每個快取行只能放 1 word（快取塊大小 = 1 word）

記憶體位址 (decimal)	快取行號 = 位址 mod 10	狀態說明	未命中類別
8	8	行 8 原本空，載入 block 8	Compulsory
11	1	行 1 原本空，載入 block 11	Compulsory
21	1	行 1 已存 block 11 → 被取代	Conflict
22	2	行 2 空，載入 block 22	Compulsory
17	7	行 7 空，載入 block 17	Compulsory
30	0	行 0 空，載入 block 30	Compulsory
134	4	行 4 空，載入 block 134	Compulsory
38	8	行 8 仍存 block 8 → 被取代	Conflict
43	3	行 3 空，載入 block 43	Compulsory
48	8	行 8 目前存 block 38 → 被取代	Conflict

• 總未命中次數：10 次（每一次皆未命中）
• 未命中類別分布：
  • Compulsory：7 次 (8, 11, 22, 17, 30, 134, 43)
  • Conflict：3 次 (21, 38, 48)
  • Capacity：0 次

【答案】

• 未命中總數 = 10
• Compulsory = 7，Conflict = 3，Capacity = 0

---

(2) 每個快取行可放 10 words（快取塊大小 = 10 words）

2‑1. 先將位址映射到 快取塊

快取塊編號 = $\left\lfloor \dfrac{\text{位址}}{10} \right\rfloor$
快取行號 = (快取塊編號) mod 10

記憶體位址	所屬快取塊	行號	狀態說明	未命中類別
8	0 (0‑9)	0	行 0 空 → 載入 block 0	Compulsory
11	1 (10‑19)	1	行 1 空 → 載入 block 1	Compulsory
21	2 (20‑29)	2	行 2 空 → 載入 block 2	Compulsory
22	2 (20‑29)	2	行 2 已有 block 2 → Hit
17	1 (10‑19)	1	行 1 已有 block 1 → Hit
30	3 (30‑39)	3	行 3 空 → 載入 block 3	Compulsory
134	13 (130‑139)	3	行 3 已有 block 3 → Conflict（被 block 13 取代）

核心觀念

本題旨在考驗考生對現代**計算機架構（Computer Architecture）**轉變與微架構設計趨勢的理解，涵蓋以下核心技術概念：

1. 指令集架構與能效比（ISA & Performance per Watt）：複雜指令集 CISC ($x86\text{-}64$) 與精簡指令集 RISC ($\text{ARM}$) 在解碼複雜度、邏輯電路規模及功耗控制上的本質差異。
2. 單晶片系統（SoC）與統一記憶體架構（Unified Memory Architecture, UMA）：異質運算（Heterogeneous Computing）環境下，共享實體記憶體空間相較於傳統系統匯流排（PCIe Bus）傳輸在記憶體頻寬與延遲上的技術優勢。
3. 專用硬體加速器與軟硬體協同設計（Domain-Specific Accelerators & HW/SW Co-design）：針對特定工作負載（機器學習、影音編解碼）設計專用硬體電路，突破傳統通用型 CPU（General-Purpose CPU）的效能與功耗極限。

---

解題方法

本題為經典的計算機系統架構問答題。解題切入點必須聚焦於**「技術層面（Technical Reasons）」**，而非單純的商業策略或成本考量。
答題策略應從傳統 PC 架構的技術瓶頸（如功耗散熱限制、記憶體牆 Memory Wall、通用 CPU 效能成長放緩）出發，透過「Intel $x86$ 架構痛點」與「Apple 自研 $\text{ARM}$-based SoC 優勢」進行對比，條列並深入剖析三個最具代表性的技術理由。

---

選項分析

本題要求列出 3 個技術原因，以下方針逐一針對 Apple 棄用 Intel CPU 改採自研 SoC（M1）的三大關鍵技術理由進行深度剖析與合理的技術驗證：

技術原因一：極致的能效比（Performance per Watt）與 RISC 架構優勢

• Intel $x86$ 痛點：Intel 處理器採用 CISC（複雜指令集）架構，指令長度不一且格式複雜。微架構中需要龐大且耗電的指令解碼器（Instruction Decoders）將 CISC 指令翻譯為內部微指令（$\mu\text{-ops}$），導致晶片靜態與動態功耗居高不下，在筆記型電腦散熱限制下極易引發發熱降頻（Thermal Throttling）。
• M1 自研優勢：Apple M1 採用 $\text{ARM}$ 架構（RISC），具備固定長度指令（Fixed-length 32-bit instructions）與極高平行度的微指令解碼單元，顯著降低了解碼邏輯的電路面積與功耗。配合超寬的亂序執行視窗（Wide Out-of-Order Execution Window）與先進半導體製程，M1 能在極低功耗下輸出極高的單核與多核 IPC（Instructions Per Cycle），達到遠超 Intel $x86$ 晶片的能效比（Performance per Watt）。

技術原因二：統一記憶體架構（Unified Memory Architecture, UMA）突破記憶體瓶頸

• Intel 傳統架構痛點：在 Intel 傳統主機板架構中，CPU、整合/獨立 GPU 以及外接晶片各自擁有獨立的記憶體池（DRAM / VRAM）。當 CPU 與 GPU 需要協同處理資料時，必須透過 PCIe 匯流排進行跨晶片的記憶體複製（Memory Copying），帶來極高的記憶體延遲（Latency）、頻寬限制以及額外的電力消耗，形成嚴重的「記憶體牆（Memory Wall）」瓶頸。