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

核心觀念

本題考查「最短工作優先」（Shortest Job First, SJF）排程。

• CPU 與 I/O 可並行；程序進行 I/O 時不占用 CPU，I/O 完成後才重新進入就緒佇列。

• 等待時間是程序在就緒佇列中等待 CPU 的時間，不包含 I/O 時間：

  $W_i=\sum(\text{各 CPU burst 的開始時間}-\text{該 burst 進入就緒佇列的時間})$

• SJF 每次 CPU 空閒時，從目前就緒佇列選擇「下一個 CPU burst 最短」的程序。

• 題目未指定相同 CPU burst 的平手規則，依標準作法以 FCFS（先進先出）處理平手；SJF 本身採非搶先式，因此 CPU burst 開始後不會被新到達的程序中斷。

SJF 能降低平均等待時間的原因是：若兩個可執行的 CPU burst 長度為 $a>b$，先執行 $b$ 會讓總等待時間比先執行 $a$ 少 $a-b$。

---

解題方法：建立 CPU 排程時間軸

$t=0$

就緒程序：

• P1：CPU burst $3$
• P3：CPU burst $5$

選擇 P1：

$0\sim3:\text{P1}$

P1 之後進行 $6$ 單位 I/O，於 $t=9$ 完成。

---

$t=3$

P2、P4 已於 $t=2$ 到達。就緒程序的下一個 CPU burst：

• P2：$5$
• P3：$5$
• P4：$3$

選擇 P4：

$3\sim6:\text{P4}$

P4 接著進行 $4$ 單位 I/O。

---

$t=6$

P2 與 P3 的 CPU burst 都是 $5$，依 FCFS 平手規則，P3 到達時間較早，因此選擇 P3：

$6\sim11:\text{P3}$

P3 接著進行 $2$ 單位 I/O，於 $t=13$ 重新進入就緒佇列。

P5 雖於 $t=7$ 到達，但目前 CPU 正執行 P3；SJF 為非搶先式，因此 P5 必須等待。

---

$t=11$

此時就緒程序的下一個 CPU burst：

• P1：$3$，於 $t=9$ 完成 I/O
• P2：$5$
• P5：$1$，於 $t=7$ 到達
• P4 的後續工作長度為 $8$，不會優先於較短 burst

選擇 P5：

$11\sim12:\text{P5}$

P5 接著進行 $2$ 單位 I/O，於 $t=14$ 完成。

---

$t=12$

就緒程序中：

• P1：$3$
• P2：$5$

選擇 P1：

$12\sim15:\text{P1}$

P1 的下一個 CPU burst 為 $5$；中間沒有額外 I/O，因此於 $t=15$ 進入就緒佇列。

核心觀念

Unified virtual memory 的重點，是將程序記憶體頁面與檔案資料統一納入以「頁（page）」為單位的快取與記憶體管理機制。

當檔案資料被讀入主記憶體，或檔案以 memory-mapped file 方式映射到程序位址空間時，作業系統可讓兩者共用同一份 page cache，避免同一份檔案內容同時存在於 page cache 與 buffer cache 中，形成重複快取（double caching）。

解題方法

題目中的關鍵字是：

• Unified：表示使用同一套快取機制。
• virtual memory：基本管理單位是 page。
• cache both process page and file data：要找能同時管理程序頁面與檔案資料的 page-level cache。

因此，正確填空為 page cache。

選項分析

• (a) page cache：正確。
  Page cache 以頁為單位保存檔案資料，並可與程序的虛擬記憶體頁面共用同一份實體頁框，是 unified virtual memory 所使用的快取概念。

各選項分析與觀念推導

1. 選項 (a) 與 (c) 錯誤：
   同一台電腦在執行不同程式時，其指令組合（Instruction Mix）與平均每指令週期數 $CPI$ 皆不同。由公式 $\text{MIPS} = \frac{\text{Clock Rate}}{CPI \times 10^6}$ 可知，同一台機器執行不同程式的 MIPS 通常不相同。

2. 選項 (b) 錯誤：
   MIPS（Million Instructions Per Second）忽略了指令總數（Instruction Count, $IC$）與指令集架構（ISA）的差異。例如編譯器優化可能減少指令數但使平均 $CPI$ 增加，導致 MIPS 下降卻使執行時間變短。因此 MIPS 不是衡量效能的良好指標。

各選項解析

(a) 錯誤
浮點數加法不符合結合律（即 $(a + b) + c \neq a + (b + c)$）。由於浮點數受限於有限位元精度，計算過程中會產生捨入誤差（Rounding Error）。
例如：$(10^{20} + -10^{20}) + 1.0 = 1.0$，但 $10^{20} + (-10^{20} + 1.0) = 0.0$。

(b) 錯誤
右移指令不完全等同於 2 的次方整數除法：

• 邏輯右移（Logical Right Shift）僅適用於無符號整數除法。
• 算術右移（Arithmetic Right Shift）對負數採用向 $-\infty$ 取整（Floor），而整數除法則是向 $0$ 取整（Truncate toward zero）。

核心觀念

本題考查 RISC 與 CISC 的指令集架構差異，以及「指令集複雜度」與效能、功耗之間的關係。

特性	RISC	CISC
指令種類	較少	較多
定址模式	較少	較多
指令格式	通常固定長度	常為可變長度
硬體解碼	較簡單	較複雜
功耗趨勢	通常較低	通常較高
典型應用	行動裝置、嵌入式系統	個人電腦、伺服器

處理器效能不能只由 RISC 或 CISC 的名稱決定，常用的 CPU 執行時間公式為

$$T_{\text{CPU}}=IC \times CPI \times T_{\text{cycle}} =\frac{IC \times CPI}{f}$$

其中：

• $IC$：執行的指令數量
• $CPI$：每條指令平均所需的週期數
• $f$：時脈頻率

RISC 雖然指令種類較少、指令較簡單，但完成同一工作時可能需要較多指令；CISC 雖然可能用較少指令完成工作，卻可能具有較高的解碼複雜度與 CPI。因此，兩者沒有絕對的效能優劣。

解題方法

逐項檢查各敘述是否符合 RISC 與 CISC 的基本定義，特別注意「always」這類絕對化用語。凡是宣稱某一架構在所有情況下都必然較快，通常不成立，因為實際效能還取決於編譯器、程式特性、微架構、快取、管線與時脈等因素。

選項分析

(a) RISC has fewer instructions than CISC.

正確。

RISC 的設計理念是使用較精簡的指令集，因此指令種類通常少於 CISC。這裡的「fewer instructions」是指指令集中的指令種類較少，不是指執行某個程式時所需的指令總數一定較少。

(b) RISC has fewer addressing modes than CISC.

正確。

RISC 通常只保留少數常用的定址模式，例如暫存器定址與立即定址，藉此簡化指令解碼與硬體設計。CISC 則通常支援較多定址模式，例如直接定址、間接定址、基底加位移定址等。

(c) CISC always has better performance than RISC.

錯誤，這是本題答案。

核心觀念

本題綜合考查檔案系統、掛載、I/O 效能技術，以及現代磁碟的抽象化方式：

• 目錄（directory）：通常以特殊檔案形式存在，內含「檔名 → 檔案控制資訊」的對應，例如 Unix-like 系統中的 inode 編號。
• 掛載點（mount point）：掛載檔案系統時，作為接合位置的目錄。
• Buffering：以暫存區吸收生產者與消費者之間的速度差異。
• Caching：暫存經常重複使用的資料副本，以減少再次存取 I/O 的成本。
• DMA（Direct Memory Access）：由 DMA 控制器協助裝置與主記憶體直接交換大量資料，減少 CPU 逐筆搬移資料的負擔。
• 磁碟幾何（disk geometry）：傳統上指磁柱（cylinder）、磁頭（head）、磁區（sector）等實體結構；現代磁碟通常透過 LBA 隱藏實體幾何。

解題方法

題目問的是「不正確」的敘述，因此逐項判斷其定義是否符合作業系統中的標準概念：

1. 檔名是否存在目錄資料中。
2. 掛載點的檔案類型。
3. 「暫存重複使用資料」應稱為 buffering 還是 caching。
4. DMA 適合的 I/O 資料量。
5. 現代作業系統是否掌握磁碟的實體幾何。

選項分析

(a) Filenames are usually stored in directory files.

正確。

目錄通常是特殊檔案，其內容包含目錄項目（directory entries）。每個目錄項目至少會記錄檔名，以及對應的 inode 或檔案控制區塊編號。因此，檔名通常儲存在目錄檔案中，而不是直接儲存在一般檔案的資料內容裡。

---

(b) Mounting points are usually regular files.

錯誤。

掛載點通常是目錄，而不是一般檔案。掛載操作會將某個檔案系統的根目錄接到既有目錄樹中的某個目錄，例如：

/mnt
/home
/media

掛載完成後，存取 /mnt 時，實際上會進入被掛載檔案系統的內容。

一般檔案（regular file）主要存放使用者資料；目錄則負責組織檔名與檔案的階層關係。因此「掛載點通常是一般檔案」不符合標準定義。

---

(c) The technique used to improve I/O efficiency by temporarily storing repeatedly-used data is called buffering.

錯誤。

核心觀念

本題考查「程序同步（process synchronization）」與「硬體式同步原語（hardware-based synchronization primitive）」的區別。

當多個執行緒同時存取共享資料時，若至少一個執行緒會修改資料，便可能發生競爭條件（race condition）。同步工具需能保護臨界區，使其滿足：

• 互斥（mutual exclusion）：同一時間最多一個執行緒進入臨界區。
• 進度（progress）：沒有執行緒在臨界區時，等待中的執行緒能繼續競爭。
• 有限等待（bounded waiting）：執行緒不會無限期等待。

硬體式同步通常利用處理器提供的「不可分割原子指令」，例如 Test-and-Set、Swap、Fetch-and-Add 與 Compare-and-Swap。

解題方法

判斷每個選項是否同時符合以下兩點：

1. 用於處理多執行緒或多程序間的同步問題。
2. 由硬體提供原子操作支援。

CAS 的語意為：

$$\operatorname{CAS}(x, expected, new)$$

處理器會以不可分割的方式完成：

1. 讀取記憶體位置 $x$ 的原值。
2. 比較原值是否等於 $expected$。
3. 若相等，將 $x$ 更新為 $new$。
4. 回傳更新前的原值。

概念上的表示如下，實際上整個比較與寫入動作由硬體以原子方式完成：

CAS(address, expected, new_value):
    old ← *address
    if old = expected:
        *address ← new_value
    return old

例如以 0 表示未上鎖、1 表示已上鎖：

while CAS(lock, 0, 1) ≠ 0:
    持續等待

執行臨界區

lock ← 0

只有成功將 lock 從 $0$ 改成 $1$ 的執行緒能進入臨界區，因此 CAS instruction 正是硬體式同步工具。

選項分析

(a) CAS instruction：正確

CAS 是處理器提供的原子硬體指令，能同時完成比較與更新，避免其他執行緒在兩個動作之間插入。它可用來實作：

核心觀念

Context switch（內容切換）是指 CPU 從目前執行的程序切換至另一個可執行程序。作業系統必須先保存原程序的程式計數器、暫存器、堆疊指標等內容，再載入下一個程序的執行內容。

判斷重點是：目前執行中的程序是否仍能繼續使用 CPU。

• running → waiting：目前程序被阻塞，不能繼續執行。
• running → terminated：目前程序已結束，不能再執行。
• waiting → ready：程序被喚醒，但不代表立即取得 CPU。
• ready → running：排程器選定程序執行時，才會發生內容切換。

中斷或系統呼叫首先造成的是 user mode 與 kernel mode 之間的 mode switch，不必然造成不同程序之間的 context switch。

解題方法

逐一判斷事件發生後，原本正在執行的程序是否必須離開 CPU：

1. 若原程序已無法繼續執行，必須切換至其他程序或 idle 程序。
2. 若原程序仍可繼續執行，核心處理完事件後可返回原程序，不一定需要內容切換。

選項分析

(a) When a process is complete.——正確

程序完成後會進入 terminated 狀態，不能再回到 CPU 繼續執行。因此作業系統必須停止使用該程序的執行內容，改執行另一個可執行程序；若沒有其他程序，則切換至 idle 程序。

(b) When an interrupt occurs.——錯誤

中斷發生時，CPU 會進入核心的中斷處理常式，但處理完畢後可以繼續執行原本的程序。例如網路封包到達所產生的中斷，不必然需要更換目前的程序。

只有在中斷處理完後，排程器決定改執行另一個程序時，才會發生 context switch。因此中斷本身不一定造成內容切換。

核心觀念

本題旨在測驗計算機組織中**管線化（Pipelining）**的兩大核心概念：**程式相依性（Dependencies）與管線冒險（Hazards）**的分類與判斷。

1. 相依性（Dependencies，程式碼本身的資料流與名稱特性）：

   • 真資料相依／資料相依（True Data Dependency / RAW - Read After Write）：後續指令需要讀取前一指令所寫入的暫存器資料（$I_j$ 讀取 $I_i$ 寫入的暫存器，且 $i < j$）。
   • 輸出相依（Output Dependency / WAW - Write After Write）：兩道指令寫入同一個目標暫存器（$I_i$ 與 $I_j$ 寫入相同的暫存器，且 $i < j$）。
   • 反相依（Anti-dependency / WAR - Write After Read）：後續指令覆寫前一指令所需讀取的暫存器（$I_j$ 寫入 $I_i$ 讀取的暫存器，且 $i < j$）。

2. 管線冒險（Pipeline Hazards，管線執行時可能造成延遲或錯誤的硬體情況）：

   • 結構冒險（Structural Hazard）：硬體資源不足，導致多道指令在同一個週期爭奪同一硬體單元（例如指令記憶體與資料記憶體共用）。
   • 資料冒險（Data Hazard）：指令在管線中重疊執行時，後續指令所需的資料尚未由先前指令產生並寫回（如 RAW 引起的資料衝突，最典型的例子為 Load-Use Hazard）。
   • 控制冒險（Control Hazard）：由分支（Branch）或跳躍（Jump）指令決定下一道 PC 位址所引起的管線延遲。

---

解題方法

先分析給定程式碼各指令的「讀取集合（Read Set, $R$）」與「寫入集合（Write Set, $W$）」：

• $I_1$: lw $1, 10($0) $\implies W(I_1) = \{$$$1\}, R(I_1) = \{$$$0\}$
• $I_2$: lw $2, 20($0) $\implies W(I_2) = \{$$$2\}, R(I_2) = \{$$$0\}$
• $I_3$: add $3, $2, $4 $\implies W(I_3) = \{$$$3\}, R(I_3) = \{$$2, $$4\}$
• $I_4$: lw $1, 30($0) $\implies W(I_4) = \{$$$1\}, R(I_4) = \{$$$0\}$
• $I_5$: lw $1, 40($0) $\implies W(I_5) = \{$$$1\}, R(I_5) = \{$$$0\}$

逐步檢驗相依性與冒險狀況：

1. 資料相依（Data Dependency / RAW）：

   • $I_2$ 寫入 $2（$W(I_2) = \{$$$2\}$），$I_3$ 隨後讀取 $2（$R(I_3) = \{$$2, $$4\}$），滿足 $W(I_2) \cap R(I_3) \neq \emptyset$。
   • 存在 $I_2 \rightarrow I_3$ 的 Data Dependency。

2. 資料冒險（Data Hazard）：

   • $I_2

因本題未提供 Figure 1 之具體圖示與程式碼，假設 Figure 1 包含處理器管線中的資料冒險 (Data Hazard) 與控制冒險 (Control Hazard)。

各選項技術解決管道冒險 (Pipeline Hazards) 之原理如下：

1. (a) Forwarding（前傳/旁路）：硬體技術。將執行階段 (EX) 或記憶體階段 (MEM) 產生的結果直接傳遞給後續指令的 ALU 輸入端，用以解決 RAW（寫後讀）資料冒險。
2. (b) Code interchanging（代碼交換/指令重排）：編譯器優化技術。透過調整指令順序，將無相依關係的指令填入相依指令之間，藉此掩蓋資料冒險與控制冒險造成的停頓 (Stall)。

(a) 磁碟最大容量計算

觀念與推導：
24-bit CHS 定址空間位元分配如下：

• Cylinder (柱面)：$10\text{ bits} \Rightarrow 2^{10} = 1024$ 個柱面
• Head (磁頭)：$8\text{ bits} \Rightarrow 2^8 = 256$ 個磁頭
• Sector (磁區)：$6\text{ bits} \Rightarrow 2^6 = 64$ 個磁區/軌

單一磁區容量為 $512\text{ Bytes}$，磁碟最大尋址容量為：
$\text{Capacity} = 2^{10} \times 2^8 \times 2^6 \times 512\text{ Bytes} = 2^{33}\text{ Bytes} = 8,589,934,592\text{ Bytes}$

---

(b) C-SCAN 磁頭移動距離計算

1. 解析 16 進位 CHS 位址之柱面編號 (Cylinder)：
24-bit 位址的高 10 位元（bits 23～14）為柱面編號 $C$，即 $C = \text{HexValue} \gg 14$：

• 1AC320 $\rightarrow 1753888 \gg 14 = 107$（第一個請求，作為初始磁頭位置）
• A2F5BC $\rightarrow 10679740 \gg 14 = 651$

核心觀念

本題考查作業系統的死結（deadlock）必要條件，以及「鎖順序（lock ordering）」如何避免死結。

死結成立通常必須同時具備以下四項條件：

1. 互斥（Mutual Exclusion）：資源同一時間只能由一個執行緒持有。
2. 持有並等待（Hold and Wait）：執行緒持有部分資源，同時等待其他資源。
3. 不可剝奪（No Preemption）：資源不能被強制從持有者手中取走。
4. 循環等待（Circular Wait）：存在一個循環，使每個執行緒都等待下一個執行緒所持有的資源。

四項條件必須同時存在才會形成死結；只要破壞其中一項，即可避免死結。

解題方法

預先規定所有鎖的取得順序，例如：

$$L_1 \prec L_2 \prec L_3$$

所有執行緒都必須依照由小到大的順序取得鎖：

lock(L1)
lock(L2)

禁止另一個執行緒採取相反順序：

lock(L2)
lock(L1)

若不限制順序，可能發生：

• 執行緒 $T_1$ 持有 $L_1$，等待 $L_2$；
• 執行緒 $T_2$ 持有 $L_2$，等待 $L_1$。

其等待關係為：

在銀行家演算法（Banker's Algorithm）中，作業系統（OS）能立即批准任務 $T_0$ 的最大資源請求向量 $\text{Request}_0 = (r_A, r_B, r_C, r_D)$，必須同時滿足以下三項條件：

1. 不可超過任務的剩餘需求：
   $\text{Request}_0 \le \text{Need}_0 = \text{Max}_0 - \text{Allocation}_0$
2. 不可超過系統當前可用資源：
   $\text{Request}_0 \le \text{Available} = \text{Total} - \sum_{i=0}^{4} \text{Allocation}_i$
3. 分配後系統必須處於安全狀態（Safe State）：

核心觀念

本題考查儲存系統中的 RAID 技術：

**RAID（Redundant Array of Independent Disks，獨立磁碟冗餘陣列）**是將多個實體磁碟組合成一個邏輯儲存單元，透過資料分割、複製或同位元檢查碼，同時改善：

• 效能：利用資料分條（striping）將資料分散至多顆磁碟，增加平行讀寫能力。
• 可靠性：利用鏡像（mirroring）或同位元檢查碼（parity），在磁碟故障時重建遺失資料。

常見 RAID 等級如下：

• RAID 0：資料分條，效能佳，但沒有容錯能力。
• RAID 1：資料鏡像，可靠性高，但可用容量約為原始容量的一半。
• RAID 5：資料分條搭配分散式同位元檢查碼，可容許一顆磁碟故障。
• RAID 6：使用雙重同位元檢查碼，可容許兩顆磁碟同時故障。

因此，題幹所描述的「使用多顆磁碟以改善儲存系統效能與可靠性」正是 RAID 的定義。

解題方法

依照題幹中的關鍵描述判斷：

1. using multiple disks：表示將多顆磁碟整合使用。
2. performance issues：對應資料分條與平行存取。
3. reliability issues：對應鏡像或同位元檢查碼所提供的容錯能力。

核心觀念

IEEE 754 單精度浮點數由三部分組成：

• 符號位元 $S$：決定正負。
• 指數欄位 $E$：使用偏移值 $127$。
• fraction 欄位 $F$：有效數字為隱含的 $1.F$。

當指數欄位不是全 $0$、也不是全 $1$ 時，使用正規化數公式：

$$x=(-1)^S(1.F)_2\times 2^{E-127}$$

題目列出的 fraction 為 $11000000000000000$，共有 $17$ 位；IEEE 754 單精度的 fraction 欄應有 $23$ 位，因此依通常題意將省略的尾端 $6$ 位視為 $0$。

解題方法

題目各欄位為：

$$S=1,\qquad E=01111110_2,\qquad F=11000000000000000000000_2$$

首先，符號位元為 $1$，所以數值為負數：

$$(-1)^S=(-1)^1=-1$$

接著計算實際指數：

$$E=01111110_2=126$$

因此：

$$e=E-127=126-127=-1$$

fraction 欄代表小數：

$$F=(0.11000000000000000000000)_2$$

只有前兩個位元為 $1$，所以：

核心觀念

CPU 的實際執行效率受到記憶體停頓週期（Memory Stall Cycles）影響。實際 $CPI$ 等於理想 $CPI$ 加上每指令因指令快取（I-Cache）與資料快取（D-Cache）缺失所產生的停頓週期。

---

推導步驟

1. 計算每指令之記憶體停頓週期（Memory Stall Cycles per Instruction）：
   • 指令快取停頓週期：
     $\text{I-Cache Stall} = 3\% \times 100 = 3 \text{ cycles}$
   • 資料快取停頓週期：
     $\text{D-Cache Stall} = 35\% \times 5\% \times 100 = 1.75 \text{ cycles}$
   • 總記憶體停頓週期：
     $\text{Total Stall Cycles} = 3 + 1.75 = 4.75 \text{ cycles}$

觀念與公式

1. CPU 時脈週期 ($T_{clk}$)：
   $T_{clk} = \frac{1}{\text{Clock Rate}} = \frac{1}{5 \text{ GHz}} = 0.2 \text{ ns}$
   在流水線架構下，$L1$ 快取的命中時間 ($\text{Hit Time}_{L1}$) 預設為 $1 \text{ cycle} = 0.2 \text{ ns}$。

2. 平均記憶體存取時間 (AMAT) 公式：

   • 單層 Cache：
     $\text{AMAT} = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Miss Penalty}_{L1}$
   • 兩層 Cache (L1 + L2)：
     $\text{AMAT} = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Hit Time}_{L2} + \text{Global Miss Rate}_{\text{DRAM}} \times \text{Access Time}_{\text{DRAM}}$

---

計算步驟

1. 求解 (h)：未加入 L2 Cache 前的 AMAT

• $\text{Hit Time}_{L1} = 0.2 \text{ ns}$
• $\text{Miss Rate}_{L1} = 2\% = 0.02$
• $\text{Miss Penalty}_{L1} = \text{Access Time}_{\text{DRAM}} = 100 \text{ ns}$

核心觀念

本題考查平行計算的加速比（speedup）與 Amdahl 定律：

$$S_p=\frac{T_1}{T_p}$$

其中 $T_1$ 是使用一個處理器的執行時間，$T_p$ 是使用 $p$ 個處理器的執行時間。以下假設每次加法耗時相同，且忽略通訊、同步與分工成本。

解題方法

純量相加只需執行一次加法：

$$s=x+y$$

因此工作量為 $1$。

矩陣相加的每個元素可獨立計算：

$$C_{ij}=A_{ij}+B_{ij}$$

矩陣大小為 $1000\times1000$，所以需要的加法次數為：

$$1000\times1000=1,000,000$$

使用一個處理器時：

$$T_1=1+1,000,000=1,000,001$$

使用 $1000$ 個處理器時，矩陣加法可平均分配，每個處理器計算：

$$\frac{1,000,000}{1,000}=1,000$$

次加法；純量相加仍是無法分割的單一加法，因此：