111 年 國立成功大學電機資訊學院碩士班─資訊聯招《計算機組織與系統》

a. T 低利用率時動態功耗減少，總功耗仍有靜態部份，但仍顯著較低。

b. T 執行時間 = Instruction Count × CPI / Clock Rate
 A: 10 × 10⁹ × 1 / 4 GHz = 2.5 s
 B: 8 × 10⁹ × 1.2 / 4 GHz = 2.4 s，故 B 較快，儘管 A 的 MIPS 較高。

c. T beq 偏移 = (target − PC − 4)/4 = 0x1FAFC/4 = 0x7BF，落於 16 位元有符號範圍 ±2¹⁵，故可用單一 beq 到 0x00020000。

d. T 單精度最小正規化數為 $2^{-126}$，其 IEEE 754 位元為
 $0\;00000001\;000\ldots0$，即題示二進位字串。

核心觀念

本題考查五級管線中的：

• 管線階段：IF → ID → EX → MEM → WB
• 資料相依與停滯（stall）
• Forwarding 對資料相依的改善
• 分支預測與錯誤路徑指令清除（flush）
• 分支決定階段不同所造成的分支處罰

本題採用以下時序假設：

1. 一個 clock cycle 內，一條指令只能位於一個管線階段。
2. 指令在進入 WB 階段時視為完成。
3. 沒有 delay slot。
4. 分支預測為 predict-taken：
   • 第一次 BEQ R2, R0, Label2 實際上 not taken，因此預測錯誤。
   • BEQ R3, R0, Label1 實際 taken，預測正確。
   • 第二次執行 BEQ R2, R0, Label2 實際 taken，預測正確。
5. 分支預測錯誤時，錯誤路徑上的指令必須清除。

實際執行的六條動態指令為：

$$\text{ADD} \rightarrow \text{BEQ}_1 \rightarrow \text{LW} \rightarrow \text{BEQ}_2 \rightarrow \text{BEQ}_1' \rightarrow \text{SW}$$

其中 $\text{BEQ}_1'$ 是回到 Label1 後，第二次執行的第一個 BEQ。

---

a. 無 forwarding，分支在 EX 階段決定

解題方法

無 forwarding 時，後續指令只能等前一條指令將結果寫入暫存器後，才能在 ID 階段讀取。

1. ADD 與第一個 BEQ 的相依

ADD 在 cycle 5 的 WB 階段寫入 R2：

指令	1	2	3	4	5	6
ADD	IF	ID	EX	MEM	WB
BEQ₁	IF	ID	stall	stall	ID	EX

因此第一個 BEQ 必須等到 cycle 5 讀到 R2，並在 cycle 6 進入 EX 判斷分支。

由於該分支預測 taken，但實際為 not taken，預測路徑上的指令被 flush，正確的 LW 從 cycle 7 開始取指。

2. LW 與第二個 BEQ 的相依

LW 在 cycle 11 的 WB 階段寫入 R3：

指令	7	8	9	10	11	12
LW	IF	ID	EX	MEM	WB
BEQ₂		IF	ID	stall	ID	EX

因此第二個 BEQ 在 cycle 12 的 EX 階段判斷為 taken。

預測方向正確，目標指令為回到 Label1 的 $\text{BEQ}_1'$。因為管線中仍有停滯，$\text{BEQ}_1'$ 在 cycle 13 進入 ID、cycle 14 進入 EX。

最後，$\text{BEQ}_1'$ 預測 taken 且實際 taken，SW 可沿著正確的預測路徑執行。

管線時序

指令	IF	ID	EX	MEM	WB
ADD	1	2	3	4	5
BEQ₁（第一次）	2	3–5	6	7	8
LW	7	8	9	10	11
BEQ₂	8	9–11	12	13	14
BEQ₁'（第二次）	9–12	13	14	15	16
SW	13	14–15	16	17	18

其中錯誤預測的 SW 不列入實際執行順序，因為它會在第一個 BEQ 判定 not taken 後被清除。

a 小題答案

Execution Order	Completed at cycle
ADD R2, R1, R3	5
BEQ R2, R0, Label2（第一次）	8
LW R3, 0(R2)	11
BEQ R3, R0, Label1	14
BEQ R2, R0, Label2（第二次）	16

a. 直接映射、1‑word 直行、大小 8 words

Addr	3	180	2	43	191	88	190	14	181	88
H/M	Miss	Miss	Miss	Miss	Miss	Miss	Miss	Miss	Miss	Hit

• Index = address mod 8
• Tag = ⌊address / 8⌋

Hit 1 / 10 → 10 %

b. 2‑路組合、2‑word 直行、大小 8 words（LRU）

Addr	3	180	2	43	191	88	190	14	181	88

第 4 題 (a) [5%]

• 核心觀念
  設備驅動程式（Device Driver）與設備控制器（Device Controller）之間的通訊介面暫存器（Control, Status, Data-in, Data-out Registers）、Port-Mapped I/O 與 Memory-Mapped I/O 指令。

• 解題方法
  Device Driver 執行於 CPU 上，為完成一次 I/O 轉移（I/O transfer），會透過特定指令將 指令（Commands） 與 資料（Data） 寫入或讀取 Device Controller 內部的核心介面暫存器：

  1. Control Register（控制暫存器）：驅動程式寫入控制位元（Control bits）以發送操作指令。
  2. Data-out Register（資料輸出暫存器）：驅動程式寫入主機欲輸出至設備的數據。
  3. Data-in Register（資料輸入暫存器）：驅動程式讀取由設備輸入至主機的數據。
  4. Status Register（狀態暫存器）：驅動程式讀取設備目前的運作狀態標誌（如 Busy, Ready, Error 等）。

  在處理器指令層級，CPU 透過以下兩類指令進行傳遞：

  • Special I/O Instructions（專用 I/O 指令）：利用獨立的 I/O Port 位址空間（Port-mapped I/O），透過如 x86 架構的 IN / OUT 特殊指令。
  • Standard Memory Instructions（標準記憶體指令）：採用記憶體映射（Memory-mapped I/O），將控制器的暫存器映射至主記憶體位址空間，利用標準的數據傳輸指令（如 MOV, LDR, STR）進行讀寫。

• 選項與項目分析

  • 指令（Commands）內容：包含操作碼（如 Read、Write、Seek、Reset）與運作模式設定參數。
  • 資料（Data）內容：包含實際傳送的數據區塊（Data payload）以及控制參數（如記憶體緩衝區位址、傳輸 Byte/Sector 數量）。

• 解題技巧
  記憶 Controller 四大暫存器「Control / Status / Data-in / Data-out」，並連結軟體層發出的「指令/資料」與硬體執行的「Port I/O / Memory-Mapped I/O」，即可完整涵蓋配分要點。

【答案】
發送的指令與資料類型：

1. Commands（指令）：包含 Read（讀取）、Write（寫入）、Seek（尋軌）、Reset（重置）與控制模式設定指令，寫入至 Controller 的 Control Register。
2. Data（資料）：包含待寫入設備的數據（寫入 Data-out Register）、由設備讀取的數據（讀自 Data-in Register）以及傳輸長度與位址參數。

傳遞之指令形式：透過 Special I/O Instructions（如 IN/OUT 存取 Port I/O）或 Standard Memory Instructions（如 MOV 存取 Memory-mapped I/O）。

---

第 4 題 (b) [5%]

• 核心觀念
  Programmed I/O / Interrupt-driven I/O（CPU-based）與 Direct Memory Access（DMA-based）的適用場景與初始化開銷（Setup Overhead）。

• 解題方法
  針對 Latency-oriented I/O（低延遲導向、小資料量傳輸，例如鍵盤輸入、滑鼠點擊或少量感測器訊號），CPU-based（Programmed I/O 或 Interrupt-driven I/O） 方法更為合適。

  詳細分析：

  1. DMA 初始化開銷（Setup Cost）過高：在啟動一次 DMA 傳輸前，CPU 必須先透過多個匯流排週期設定 DMA 控制器的暫存器（如來源位址、目的位址、傳輸長度與控制字組）。傳輸結束後尚需進行匯流排仲裁（Bus Arbitration）並觸發中斷。
  2. 對於小尺寸資料（Small-size data），DMA 的初始化與前置設定開銷（Setup time）往往大於實際傳輸資料所花費的時間。
  3. CPU-based 方法不需前置設定 DMA 控制器，CPU 可直接對 I/O 暫存器進行存取完成傳輸，反應更即時，能獲得更低的傳輸延遲。

• 項目分析

  • CPU-based (Programmed/Interrupt I/O)：無 DMA 初始開銷，適合 Small-size, Latency-oriented 傳輸。
  • DMA-based：適合 Bulk-size, Throughput/Bandwidth-oriented 大區塊傳輸（如硬碟讀寫、網路封包）。

• 解題技巧
  評估 DMA 效能時應考量「Setup Cost vs. Transfer Cost」。當資料量小到 Setup Cost 佔據主要比例時，使用 DMA 反而會增加延遲。

【答案】
CPU-based 方式適合 Latency-oriented I/O。
原因：DMA 在傳輸前需要 CPU 進行暫存器初始化設定（如設定源/目的位址與計數器），此前置設定開銷（Setup Overhead）對於少量資料而言佔比過高。CPU-based（如 Interrupt-driven I/O）能跳過 DMA 設置程序，獲得更低的回應延遲。

---

第 4 題 (c) [5%]

• 核心觀念
  虛擬記憶體（Virtual Memory）環境下 DMA 的實體位址需求與 IOMMU (Input-Output Memory Management Unit)。

• 解題方法
  傳統 DMA 控制器直接對實體記憶體（Physical Memory）進行存取。在支援虛擬記憶體的系統中，若完全由作業系統軟體將虛擬位址（Virtual Address）轉換為實體位址（Physical Address）並鎖定分頁（Page Pinning），會造成極高的軟體處理開銷與延遲。

  能在硬體層級協助並加速此位址映射過程的裝置為 IOMMU (Input-Output Memory Management Unit，輸入輸出記憶體管理單元)。

  IOMMU 的核心功能：

  1. 硬體級位址翻譯：自動將設備發出的裝置虛擬位址（Device Virtual Address）即時翻譯為實體記憶體位址。
  2. 支援分散-聚集（Scatter-Gather）I/O：使物理上不連續的分頁在虛擬位址空間中展現為連續區塊，無須進行繁重的記憶體重新整理。
  3. 記憶體保護：防止惡意或錯誤的設備存取未授權的實體記憶體區域。

• 項目分析

  • MMU (Memory Management Unit)：服務 CPU 的虛擬位址翻譯裝置。
  • IOMMU (Input-Output Memory Management Unit)：專門服務 I/O 設備與 DMA 控制器的位址翻譯硬體裝置。

• 解題技巧
  分清 CPU 端與 I/O 端的記憶體管理單元：CPU 對應 MMU，DMA/I/O 設備對應 IOMMU。

【答案】
IOMMU (Input-Output Memory Management Unit，輸入輸出記憶體管理單元)。

---

第 4 題 (d) [6%]

• 核心觀念
  作業系統 I/O 子系統三大核心服務：Buffering（緩衝）、Caching（快取）與 Spooling（假脫機）。

• 解題方法
  依據題目敘述精確比對定義：
  i. 「當資料從應用程式傳輸至設備時，用來暫存資料的記憶體區域」$\rightarrow$ Buffering（緩衝）。
  ii. 「儲存資料複本的高速記憶體區域，存取複本比存取原始資料更有效率」$\rightarrow$ Caching（快取）。
  iii. 「為無法接收交錯資料流的專屬 I/O 設備（每次僅能服務一個工作）保存輸出的記憶體區域」$\rightarrow$ Spooling（假脫機）。

• 項目分析

  • i. Buffering：為了解決傳輸兩端速度不匹配、資料區塊大小不匹配以及維護 Copy Semantics。
  • ii. Caching：利用局部性原理（Locality of Reference）存放資料複本，以提升重複讀寫的效能。
  • iii. Spooling：全名為 Simultaneous Peripheral Operations On-Line，用於印表機等獨佔性設備（Exclusive device），將多個任務排隊暫存於磁碟或記憶體佇列中。

• 解題技巧
  關鍵字快速記憶法：

  • Temporary store during transfer $\rightarrow$ Buffering
  • Fast memory holding copies $\rightarrow$ Caching
  • Cannot accept interleaved data / serve one job at a time $\rightarrow$ Spooling

【答案】
i. Buffering
ii. Caching
iii. Spooling

---

第 4 題 (e) [4%]

• 核心觀念
  非同步 I/O（Asynchronous I/O）機制與複製語意（Copy Semantics）之實作。

• 解題方法
  用以實作高效能 Asynchronous I/O 的核心技術是 Buffering（緩衝技術）。

  詳細說明：

  1. 在非同步 I/O 中，應用程式發起非同步 I/O 請求（如非同步寫入）後，系統呼叫會立即返回，應用程式不會被阻塞（Non-blocking）並可繼續執行後續作業。
  2. 為了保證 Copy Semantics（複製語意），應用程式在系統呼叫返回後即可安全地修改或釋放其原有的用戶空間記憶體（User-space buffer）。
  3. 作業系統會在發起非同步傳輸時，立即將資料複製到核心空間的 Buffer 中。之後 I/O 控制器或 DMA 便能在背景異步地從 Kernel Buffer 將資料寫入設備；非同步讀取同理，OS 先將設備資料讀入 Kernel Buffer，完成後再通知應用程式。因此 Buffering 是實作非同步解耦與維護資料一致性的關鍵。

• 項目分析

  • Buffering：提供異步解耦與 Copy Semantics 支援，為非同步 I/O 的核心基礎。

第 5 題 (i)、(ii)、(iii)

核心觀念

作業系統 I/O 子系統（I/O Subsystem）提供三種核心記憶體管理與傳輸服務：

1. 緩衝區（Buffer）：於資料傳輸過程中的臨時記憶體儲存區，用以解耦發送端與接收端的傳輸速率與資料單位差異。
2. 快取（Cache）：利用局部性原理（Locality of Reference），在高速記憶體中存放慢速主存區資料的副本，提升重複存取效率。
3. 假離線佇列區（Spool, Simultaneous Peripheral Operations On-Line）：用於管理無法交錯（Non-interleaved）接收資料流的獨佔性裝置（Exclusive Device，例如印表機），將各進程的輸出先存入磁碟佇列，再依序獨佔服務。

解題方法與分析

• 子題 (i) 分析：題目描述「在資料從應用程式傳輸至裝置時暫存資料的記憶體區域」，此即為 Buffer（緩衝區）。其功能包括解決裝置間的速率不匹配（Speed Mismatch）、資料傳輸尺寸不一致（Transfer Size Mismatch）以及維護非同步 I/O 的複製語意（Copy Semantics）。
• 子題 (ii) 分析：題目描述「存放資料副本的高速記憶體區域，存取副本效率優於原始資料」，此即為 Cache（快取）。其主要目的在於降低平均存取延遲（Average Access Latency）。
• 子題 (iii) 分析：題目描述「為無法接受交錯資料流的 I/O 裝置保存輸出的記憶體區域，該裝置一次只能服務一個作業」，此即為 Spool / Spooling（假離線技術）。獨佔性裝置若允許交錯寫入會導致列印或傳輸內容混亂，因此必須透過 Spooling 機制維護佇列管理。

解題技巧

• Buffer vs. Cache 快速區分：Buffer 解決的是「兩端傳輸速率或資料規格不匹配」的問題；Cache 解決的是「存取慢速介質延遲過高」的問題。
• Spooling 關鍵字：只要看到「不可交錯（Cannot accept interleaved data）」或「一次僅能處理一個 Job（One job at a time）」，必指定 Spool / Spooling。

【答案】

i. Buffer (或 Buffering)
ii. Cache (或 Caching)
iii. Spool (或 Spooling)

---

第 5 題 (e)

核心觀念

非同步 I/O（Asynchronous I/O）允許應用程式在發出 I/O 請求後，不需等待硬體完成傳輸即可立即返回並繼續執行後續 CPU 指令。為確保非同步傳輸期間資料的一致性與獨立性，作業系統必須依賴 Buffering（緩衝技術）。

解題方法與分析

實作高效非同步 I/O 最關鍵的技術為 Buffering（配合 Spooling 與 Caching 的輔助）：

1. 複製語意（Copy Semantics）與解耦：若應用程式發起非同步寫入（如 aio_write()），若直接從應用程式的記憶體空間進行 DMA 傳輸，應用程式後續修改該區段記憶體將導致資料寫入錯誤。OS 透過將資料複製到核心層級的 Buffer 中，應用程式即可安全解除鎖定並繼續執行，硬體控制器則非同步地將 Buffer 中的資料寫入裝置。
2. 速率與頻寬調整：Buffer 提供緩衝空間，使得非同步 I/O 請求得以批次化（Batching）或透過 DMA 進行高速區塊傳輸，極大地提升系統的 I/O 吞吐量（Throughput）。

解題技巧

回答本題時需精準點出「Buffer 如何協助非同步傳輸解耦應用程式控制權與硬體傳輸」，結合複製語意（Copy Semantics）與記憶體隔離說明即可獲得滿分。

【答案】

Buffering（或搭配 Spooling 與 Caching）。因為在非同步 I/O 運作下，應用程式發起請求後便立即返回執行。作業系統必須利用 Buffer 儲存資料副本（維護 Copy Semantics），使應用程式能安全地繼續修改其記憶體空間，同時由 DMA 控制器非同步將 Buffer 內的資料傳輸至裝置，進而解耦 CPU 運作與 I/O 傳輸，顯著提升 I/O 吞吐量。

---

第 5 題 (f)

核心觀念

虛擬記憶體中的 Swap Space（置換空間）管理方式主要有兩大類：

1. File System 方式：在現有的檔案系統內建立大檔案（例如 Windows 的 pagefile.sys）。
2. Raw Disk Partition 方式：劃分獨立的磁碟分割區，不套用檔案系統（例如 Linux Swap Partition）。

解題方法與分析

當目標為極致的「實作效率（Implementation Efficiency / Access Speed）」時，應採用 Raw Disk Partition（獨立磁碟分割區）。

其原因分析如下：

• 免除檔案系統額外開銷（No File System Overhead）：傳統檔案系統在進行 Disk I/O 時，需要處理檔頭解析、目錄搜尋、索引節點（Inode）讀寫、間接區塊指標查詢（Indirect Block Pointers）、檔案鎖定與日誌記錄（Journaling）。獨立 Swap 分割區繞過整個檔案系統層級（Bypass File System Layer），直接存取磁碟區塊。
• 專用空間管理演算法：Swap 分割區採用極簡化的位元圖（Bitmap）或頁面地圖（Swap Map）管理區塊分配，強調速度而非目錄結構，且置換空間通常會預先分配連續區塊（Contiguous Blocks），顯著減少磁碟尋道時間（Seek Time）。
• 檔案系統方式的缺點：將 Swap 建立於檔案系統內會受磁碟碎片化（Fragmentation）影響，且每次 Page In / Page Out 都需更新檔案系統 Meta-data，造成嚴重性能損失。

解題技巧

比較效能題型時，核心邏輯為「減少抽象層級」。分割區（Partition）比檔案系統（File System）少了一層 Meta-data 管理與檔案系統索引開銷，因此效率勝出。

【答案】

應採用 Separate disk partition（獨立磁碟分割區） 方式。因為獨立分割區繞過了檔案系統層級，無需進行目錄查詢、Inode 解析、檔案鎖定與日誌記錄等 Meta-data 額外開銷；且 Swap 分割區使用專為頁面置換設計的高效管理演算法與連續區塊分配，能極大化磁碟 I/O 存取效率。

---

第 5 題 (g)

核心觀念

當系統分配固定大小的 Swap Space / 實體記憶體框架時，若不斷引入新進程以提高多重程式化程度（Degree of Multiprogramming, DOM），系統會遭遇 Thrashing（系統翻騰 / 顛簸） 現象。

解題方法與分析

1. 發生過程：
   • 當 DOM 增加，分配給每個進程的實體頁框（Page Frame）數量逐漸減少。