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

核心觀念

Log-structured file system（LFS）將資料與檔案系統中繼資料依序追加到 log，並定期寫入一致的 checkpoint。發生 crash 後，復原流程通常是：

1. 讀取最近一次有效的 checkpoint。
2. 從 checkpoint 之後開始掃描 log。
3. 重做已完整寫入、狀態有效的更新。
4. 捨棄 crash 時尚未完整寫入的尾端紀錄或未提交交易。

因此，LFS 的正常復原依靠的是 checkpoint 與 roll-forward recovery，而不是傳統檔案系統的完整一致性檢查。

解題方法

逐一判斷各選項所描述的事件是否符合 LFS 的 crash recovery：

• 已提交且完整的交易：保留或重做。
• 未提交、已取消或寫入不完整的交易：捨棄。
• 不需要將所有 log 內容一律視為有效或無效。
• 不需要每次 crash 都執行完整的 file consistency checking。

選項分析

A. Only aborted transactions must be completed.

錯誤。aborted transaction 已被取消，不應完成或重做；復原時應捨棄它。需要保留的是已完整寫入且有效的交易。

B. All transactions in the log must be completed.

核心觀念：行程 (process) 間的記憶體共享與 Copy-on-Write (COW) 機制。

當一個父行程 (parent process) 建立一個子行程 (child process) 時，為了效率，通常會讓子行程繼承父行程的資源，包括記憶體空間。在現代作業系統中，為了避免立即複製整個記憶體空間（這非常耗時且浪費資源），會採用一些共享機制。

選項分析：
A. Copy-on-write (COW)：這是一種資源管理技術。當父行程建立子行程時，兩個行程會共享相同的記憶體頁面。只有當其中一個行程試圖修改共享頁面時，系統才會為該頁面創建一個副本，然後修改副本。這樣就實現了初始的記憶體共享，以及在需要時才進行實際的複製。這完美符合題目的描述。
B. Zero-fill-on-demand：這是一種記憶體管理技術，用於在分配新的記憶體頁面時，將其內容初始化為零。這與父子行程共享頁面的情境無關。
C. Memory-mapped：這是一種將檔案或裝置映射到行程的虛擬位址空間的技術。

觀念剖析

依據作業系統資源分配與死鎖（Deadlock）理論，系統狀態間的關係如下：

1. 安全狀態（Safe State）：存在至少一個安全序列（Safe Sequence），系統保證絕對不會發生死鎖。
2. 不安全狀態（Unsafe State）：不存在安全序列，代表系統有可能發生死鎖，但不等於已經死鎖（死鎖狀態僅為不安全狀態的子集合）。

---

核心觀念

本題考查檔案配置（file allocation）的基本方法。常見方式包括：

• Contiguous allocation：檔案所有資料區塊連續存放。
• Linked allocation：檔案區塊以鏈結串列連接，每個區塊記錄下一個區塊的位置。
• Indexed allocation：另設索引區塊，集中記錄檔案所有資料區塊的位置。
• Multilevel index：使用多層索引區塊管理大型檔案。
• Extent-based allocation：以多個連續區段（extent）描述檔案位置。

FAT（File Allocation Table）的每個表格項目記錄「下一個配置區塊」的位置。例如：

$$\text{FAT}[7]=19,\quad \text{FAT}[19]=4,\quad \text{FAT}[4]=\text{EOF}$$

若檔案的起始區塊為 $7$，其配置鏈結就是：

$$7\rightarrow 19\rightarrow 4\rightarrow \text{EOF}$$

因此，FAT 的本質是以表格集中保存鏈結配置所需的下一區塊指標。

解題方法

判斷檔案配置方式時，觀察「檔案的下一個區塊位置如何取得」：

1. 目錄項目記錄檔案的起始區塊。
2. 由該區塊編號查詢 FAT。
3. FAT 項目提供下一個區塊編號。
4. 持續查詢，直到遇到 EOF（End of File）標記。

檔案不必連續存放，系統透過 FAT 中的指標將分散的區塊串成一條鏈。因此，FAT 是以集中式表格實作的鏈結配置。

選項分析

• A. contiguous allocation：錯誤

  連續配置要求檔案的所有區塊位於連續磁碟位置，例如：

  $$20,21,22,23$$

  FAT 中的檔案區塊可以分散在磁碟各處，例如：

核心觀念

本題考查作業系統中的「臨界區問題（critical-section problem）」及其三項標準要求。

一個行程通常具有以下結構：

$$\text{entry section} \rightarrow \text{critical section} \rightarrow \text{exit section} \rightarrow \text{remainder section}$$

其中，臨界區會存取共享資料。合格的臨界區解法必須滿足：

1. Mutual exclusion（互斥）
2. Progress（進度）
3. Bounded waiting（有限等待）

**Atomicity（原子性）**雖然常用於實作同步機制，但不是臨界區問題所列出的三項標準要求。

解題方法

直接對照臨界區問題的標準定義：

• 若選項屬於三項必要要求，則不能選。
• 不在三項必要要求中的性質，才是本題答案。

三項必要要求為：

1. Mutual exclusion

任一時刻最多只能有一個行程位於臨界區：

$$\left|\{\text{位於 critical section 的行程}\}\right| \leq 1$$

若無法滿足互斥，兩個行程可能同時修改共享資料，造成競爭條件。

2. Progress

當目前沒有行程位於臨界區，且有行程希望進入時，系統必須在有限時間內決定下一個進入者。

不能讓不想進入臨界區的行程影響決策，也不能讓所有等待行程無限期停滯。

3. Bounded waiting

行程提出進入臨界區的請求後，其他行程可以插隊進入臨界區的次數必須有上限。

此要求用來避免 starvation（飢餓），確保等待中的行程最終能夠進入。

因此，標準要求中沒有 atomicity，答案為 C。

選項分析

核心觀念

本題考查「使用者模式（user mode）」與「核心模式（kernel mode）」的權限區分。

作業系統會將可能影響整台電腦、其他程序或系統控制流程的指令，列為特權操作（privileged operations）。使用者模式中的應用程式若直接執行此類指令，CPU 會觸發例外並轉交作業系統處理；應用程式必須透過系統呼叫，請求核心代為完成。

本題四項操作都會直接影響系統的中斷控制或硬體資源，因此不能由使用者模式中的應用程式直接完成。

解題方法

逐一判斷各操作是否會影響全域系統狀態：

1. 若操作會改變 CPU 的中斷處理方式，屬於核心權限。
2. 若操作會改變系統時脈或排程依據，屬於核心權限。
3. 若操作會改變中斷處理程序的入口位置，屬於核心權限。
4. 若操作會直接存取 I/O 裝置，屬於核心權限。

四者皆非使用者模式可直接執行的操作，因此選擇 E。

選項分析

• A. Disarm Interrupts

  關閉或禁止中斷會使 CPU 暫時不接受外部中斷。若應用程式能任意關閉中斷，便可能阻止作業系統取得 CPU 控制權，造成系統無法排程、處理裝置事件，甚至整個系統停止運作。

  因此，禁止中斷屬於特權操作。例如 x86 的 CLI 指令便不能由一般使用者模式直接執行，否則會產生例外。

  A 錯誤。

• B. Set the system timer

  系統計時器通常用來產生週期性中斷，讓作業系統進行時間管理與搶先式排程。若應用程式能自行設定系統計時器，便可能任意改變排程頻率、干擾其他程序，甚至阻止排程器正常運作。

  因此，設定系統計時器必須由核心執行，使用者程式只能透過系統呼叫提出請求。

  B 錯誤。

核心觀念

本題考查作業系統的**記憶體保護（memory protection）**與 trap／exception。

每個行程都有合法的虛擬位址範圍。CPU 執行記憶體存取指令時，會由記憶體管理單元（MMU）檢查位址是否：

• 落在行程允許的位址範圍內；
• 對應到有效的頁面；
• 符合存取權限，例如可讀、可寫或可執行。

若位址不合法，指令不會正常完成，硬體會同步產生記憶體保護例外，將控制權轉交作業系統的例外處理程式。

在簡化的基底暫存器與界限暫存器模型中，合法位址可表示為：

$$\text{base} \leq \text{address} < \text{base}+\text{limit}$$

若不符合此條件，就會觸發保護例外。

解題方法

題目問的是「immediate result」，也就是非法位址產生後的立即結果，不是作業系統後續如何處置該行程。

判斷流程如下：

1. 行程產生一個虛擬位址。
2. MMU 檢查位址範圍、頁表有效位元與存取權限。
3. 檢查失敗，硬體產生同步的 trap／exception。
4. CPU 轉入核心模式，執行作業系統的處理常式。
5. 作業系統後續可能終止行程，或回報存取違規。

因此，立即結果是發生硬體 trap。

選項分析

• A. Blue Screen of Death

  錯誤。藍色畫面是某些作業系統在發生核心層級嚴重錯誤時的錯誤呈現，不是一般使用者行程存取非法位址的必然立即結果。使用者行程通常只會被終止或收到存取違規訊號，不會直接造成整個系統藍屏。

• B. Deadlock

核心觀念

本題考的是 Linux 的行程（process）建立與程式映像置換：

• fork()：建立目前行程的子行程。子行程一開始是父行程的複製品，具有新的 PID。
• exec() 家族：將目前行程的程式碼、資料區與堆疊替換成另一個可執行檔，但 PID 不變。

因此，Linux 中啟動另一個程式的典型流程是：

$$\texttt{fork()} \rightarrow \texttt{exec()}$$

fork() 負責「建立另一個行程」，exec() 負責「讓子行程執行指定程式」。

解題方法

題幹的關鍵是「start another copy」：

1. 需要產生新的行程，先使用 fork()。
2. 若子行程要執行另一個程式，再呼叫 exec()。
3. Linux shell 執行命令時，通常也是採用此流程。

簡化程式碼如下：

pid_t pid = fork();

if (pid == 0) {
    execlp("program", "program", (char *)NULL);
    _exit(127);  // exec 失敗時離開
} else {
    waitpid(pid, NULL, 0);
}

其中，fork() 成功後會同時存在父、子兩個行程；子行程再透過 exec() 載入指定程式。

若只是單純建立目前程式的副本，fork() 本身已足夠；在一般「建立子行程並執行另一個程式」的考試語境中，標準答案寫作 fork/exec。

選項分析

• A. clone：錯誤

  clone() 是 Linux 提供的低階行程／執行緒建立系統呼叫，可透過 flags 指定父子行程是否共享記憶體、檔案描述元等資源。

核心觀念

多層回饋佇列（Multilevel Feedback Queue, MLFQ）將 ready queue 分成多個優先層級，例如 $Q_0$、$Q_1$、$Q_2$，通常 $Q_0$ 的優先權最高。

跨佇列的 CPU 分配比例是排程政策事先設定的參數。若第 $i$ 層分配比例為 $p_i$，則必須滿足：

$$\sum_i p_i=100\%$$

在觀察期間 $T$ 內，第 $i$ 層預期取得的 CPU 時間約為：

$$T_i=p_iT$$

取得 CPU 時間後，各佇列內部再使用 Round Robin、FCFS 等演算法安排其中的行程。

「回饋」指的是行程會依 CPU 使用行為在不同佇列間移動。常見規則是：耗盡時間片的 CPU-bound 行程降到較低層；經常進行 I/O 或主動讓出 CPU 的行程維持較高優先權；長時間等待的行程則可透過 aging 或 priority boost 提升，以避免 starvation。這種調整主要改變行程所屬的佇列，不代表每個佇列的 CPU 百分比會隨意變動。

解題方法

題目問的是「各佇列之間如何分配 CPU 時間」，不是問「同一佇列內如何排程」。

MLFQ 的典型描述是由系統預先指定各層佇列的 CPU 份額，例如：

• $Q_0$：$50\%$
• $Q_1$：$30\%$
• $Q_2$：$20\%$

核心觀念

本題考查頁式記憶體與虛擬記憶體中，頁表項目（Page Table Entry, PTE）之 valid bit 的意義變化。

在一般頁式記憶體中，valid bit 用來表示該頁是否屬於此行程的合法邏輯位址空間：

• valid = 1：此頁是合法頁面。
• valid = 0：此頁不屬於該行程，存取時會產生例外。

加入虛擬記憶體後，行程的合法位址空間可能大於實體記憶體容量。因此，一個頁面即使屬於行程的合法位址空間，也不一定目前存放在主記憶體中。

此時，valid bit 的意義改為表示：

• valid = 1：該頁目前位於主記憶體。
• valid = 0：該頁目前不在主記憶體，通常位於磁碟等後備儲存空間。

若 CPU 存取 valid = 0 的頁面，硬體會產生 page fault，由作業系統將該頁載入主記憶體，再更新頁表後重新執行指令。

解題方法

判斷關鍵在於區分兩種不同問題：

1. 這個頁面是否屬於行程的合法位址空間？
2. 這個合法頁面目前是否位於主記憶體？

沒有虛擬記憶體時，頁表通常直接描述合法位址與實體頁框的對應，因此 valid bit 可表示「此頁是否合法」。

有了虛擬記憶體後，合法頁面可能暫時被換出到磁碟。此時需要利用同一個位元表示「目前是否有有效的實體頁框對應」，也就是「是否在主記憶體中」。

因此正確選項是 B。

選項分析

• A. The page had not been referenced lately.

  錯誤。這是 reference bit、accessed bit 的用途，用來記錄頁面近期是否曾被 CPU 存取，常用於頁面置換演算法，例如 Second-Chance。

關鍵參數計算

1. 區塊大小：$8 \text{ KB} = 8192 \text{ bytes} = 2^{13} \text{ bytes}$
2. 指標大小：$4 \text{ bytes}$
3. 單一指標區塊可容納的指標數量 ($N$)：
   $N = \frac{8192 \text{ bytes}}{4 \text{ bytes}} = 2048 = 2^{11}$

---

各層級容量定址推導

1. 直接區塊（Direct Blocks）（12 個）：
   $\text{容量}_1 = 12 \times 8 \text{ KB} = 96 \text{ KB}$

2. 單層間接區塊（Single Indirect Block）（1 個）：
   $\text{容量}_2 = 1 \times 2048 \times 8 \text{ KB} = 16,384 \text{ KB} = 16 \text{ MB}$

核心觀念

本題考查 NAND Flash SSD 中 Flash Translation Layer（FTL）的三項核心功能：

• Address Translator：將主機的邏輯區塊位址（LBA）轉換為 NAND Flash 的實體位址。
• Garbage Collector（GC）：回收含有無效資料的區塊，重新產生可寫入的空間。
• Wear Leveler（WL）：平均分散各區塊的擦除次數，避免少數區塊過度磨損。

NAND Flash 的重要特性是：

1. 資料不能直接覆寫，必須先擦除。
2. 寫入以 page 為單位，但擦除以 block 為單位。
3. 每個 block 的 Program/Erase（P/E）次數有限。

因此，SSD 必須透過 FTL 管理邏輯位址、資料搬移、區塊回收與磨耗分散。

解題方法

作答時可依照「限制 → 對應管理機制 → 額外空間效益」的順序：

1. 先指出 NAND Flash 的兩個根本限制。
2. 說明 GC 如何解決「無法直接覆寫」造成的空間回收問題。
3. 說明 WL 如何解決「P/E 次數有限且容易分布不均」的問題。
4. 最後解釋 OP space 如何增加 GC 與 WL 的操作彈性。

（1）NAND Flash Memory 的兩項先天限制

限制一：不能直接覆寫，且寫入與擦除的粒度不同

NAND Flash 的 page 一旦寫入資料，不能像磁碟或記憶體一樣直接將原內容覆寫。若要更新資料，通常必須：

1. 將新資料寫入另一個尚未使用的 page。
2. 將原 page 標記為無效（invalid）。
3. 待整個 block 中累積足夠無效 page 後，再由 GC 搬移仍有效的 page。
4. 擦除整個 block，重新取得可用空間。

其中，資料寫入以 page 為單位，但擦除必須以較大的 block 為單位。因此，即使只更新一個 page，也可能需要搬移同一 block 中其他仍有效的資料，造成額外成本。

限制二：每個 block 的 P/E 次數有限

NAND Flash 的儲存單元經過反覆的 Program 與 Erase 後會逐漸劣化。每個 block 可承受的 P/E 次數有限，超過耐久度後可能出現：

• 資料保存時間縮短；
• 位元錯誤增加；
• ECC 修正負擔增加；
• 最終形成壞 block，無法可靠使用。

因此，SSD 不能讓少數熱門區塊反覆被擦除，而必須透過 wear leveling 將擦除次數分散到不同 block。

可補充的相關特性

NAND Flash 的讀取、寫入與擦除速度也不對稱，通常擦除操作特別慢；此外，MLC、TLC、QLC 等多位元儲存單元對錯誤與磨耗更加敏感。這些特性會進一步增加 FTL 管理的必要性。

（2）Garbage Collector 與 Wear Leveler 的功能

A. Garbage Collector

GC 的主要功能是回收 NAND Flash 中的無效空間，重新建立可寫入的 free blocks。

當主機更新資料時，FTL 不會覆寫原 page，而是將新版本寫到其他 page，舊 page 則成為 invalid。GC 的基本流程如下：

1. 從已使用的 block 中選擇一個回收對象，通常稱為 victim block。
2. 找出其中仍然有效的 pages。
3. 將有效資料搬移至其他 free block。
4. 更新 FTL 的邏輯位址到實體位址對映。
5. 擦除原本的 victim block。
6. 將擦除後的 block 放回 free-block pool，供後續寫入使用。

若 victim block 中有效 page 很少，所需搬移的資料量較少，GC 成本也較低。因此常見的選擇策略是優先回收「無效 page 比例高」的 block。

GC 會造成額外的實體寫入。其寫入放大率可表示為：

$$\text{WA} = \frac{\text{NAND 實際寫入量}} {\text{主機要求寫入量}}$$

GC 搬移的有效資料越多，NAND 實際寫入量越大，寫入放大率越高，效能與 Flash 壽命也越差。

B. Wear Leveler

WL 的主要功能是平均分配各 block 的 P/E 次數，避免部分 block 過度磨損。

假設某些 block 儲存作業系統或長期不變的資料，其他 block 則持續承受頻繁更新。若沒有 WL，寫入密集的 block 會很快達到耐久度上限，即使其他 block 幾乎沒有被使用，整顆 SSD 仍可能因少數壞 block 而降低可用性。

常見的 WL 分為兩種：

動態磨耗平均（Dynamic Wear Leveling）

新資料寫入時，優先選擇 P/E 次數較低的可用 block，讓新的寫入工作分散到不同 block。

其優點是成本較低；缺點是長期不變的資料可能一直留在原本的低磨耗 block，造成整體磨耗仍不完全平均。

靜態磨耗平均（Static Wear Leveling）

除了安排新的資料寫入低磨耗 block，也會定期搬移長期不變的資料，讓原本很少使用的 block 能夠被納入擦除與重新配置。

核心觀念

本題使用 Banker’s algorithm（銀行家演算法） 判斷系統是否處於安全狀態。

各欄位意義如下：

• Allocation：程序目前已占用的資源量。
• Max：程序完成工作所需的最大資源總量。
• Need：程序尚需的資源量。

$$\text{Need}=\text{Max}-\text{Allocation}$$

若目前可用資源為 Available，則令：

$$\text{Work}=\text{Available}$$

若某程序 $P_i$ 滿足：

$$\text{Need}_i \leq \text{Work}$$

則可假設該程序取得所需資源並完成工作；完成後釋放原本占用的資源：

$$\text{Work}\leftarrow \text{Work}+\text{Allocation}_i$$

若所有程序都能依序完成，系統即為安全狀態，該順序稱為 安全序列（safe sequence）。

---

計算 Need 矩陣

逐列計算 $\text{Need}=\text{Max}-\text{Allocation}$：

程序	Allocation $(A,B,C,D)$	Max $(A,B,C,D)$	Need $(A,B,C,D)$
$P_0$	$(3,0,1,4)$	$(6,2,2,8)$	$(3,2,1,4)$
$P_1$	$(2,2,1,0)$	$(4,3,2,2)$	$(2,1,1,2)$
$P_2$	$(3,1,2,1)$	$(4,4,3,2)$	$(1,3,1,1)$
$P_3$	$(0,5,1,0)$	$(5,7,2,3)$	$(5,2,1,3)$
$P_4$	$(4,2,1,2)$	$(7,4,3,6)$	$(3,2,2,4)$

因此，題目提供的資料可確定為：

$$\begin{aligned} \text{Need}_{P_0}&=(3,2,1,4)\\ \text{Need}_{P_1}&=(2,1,1,2)\\ \text{Need}_{P_2}&=(1,3,1,1)\\ \text{Need}_{P_3}&=(5,2,1,3)\\ \text{Need}_{P_4}&=(3,2,2,4) \end{aligned}$$

---

解題方法

目前所有程序已配置的資源總量為：

$$\sum \text{Allocation}=(12,10,6,7)$$

若系統總資源為 $(R_A,R_B,R_C,R_D)$，則：

$$\text{Available}=(R_A-12,\ R_B-10,\ R_C-6,\ R_D-7)$$

Banker’s algorithm 的判斷流程如下：

1. 將 Work 設為 Available。

2. 找出尚未完成且滿足 $\text{Need}_i\leq\text{Work}$ 的程序。

3. 假設該程序完成，更新：

   $$\text{Work}\leftarrow\text{Work}+\text{Allocation}_i$$

4. 重複上述步驟，直到所有程序完成，或找不到任何可完成的程序。

---

合理假設下的完整計算

題目未提供 Available 或各資源的總量，因此無法僅由表格唯一判定安全性。以下採用一組合理的示範假設：

$$\text{Available}=(2,1,1,4)$$

初始時：

$$\text{Work}=(2,1,1,4)$$

第一步：完成 $P_1$

$$\text{Need}_{P_1}=(2,1,1,2)\leq(2,1,1,4)$$

因此 $P_1$ 可以完成。釋放其配置資源：

$$\begin{aligned} \text{Work} &=(2,1,1,4)+(2,2,1,0)\\ &=(4,3,2,4) \end{aligned}$$

第二步：完成 $P_0$

$$\text{Need}_{P_0}=(3,2,1,4)\leq(4,3,2,4)$$

完成後：

核心觀念

本題考查 demand paging、page fault 與 thrashing。

在 demand paging 中，若行程存取的頁面不在實體記憶體，便會產生 page fault。作業系統必須從 paging disk 載入頁面，行程在磁碟 I/O 完成前會被阻塞，CPU 因而無法執行有效工作。

有效存取時間可表示為：

$$EAT=(1-p)t_m+p(t_f+t_m) \approx t_m+p t_f$$

其中：

• $p$：page fault 發生機率
• $t_m$：一般記憶體存取時間
• $t_f$：處理 page fault 所需時間，主要包含磁碟 I/O

由於 $t_f$ 遠大於 $t_m$，只要 page fault 頻繁發生，CPU 就會長時間等待 paging disk。

本題中 CPU utilization 僅為 $20\%$，paging disk utilization 卻高達 $97.7\%$，而其他 I/O 裝置僅 $5\%$，表示瓶頸在分頁 I/O，系統正處於典型的 thrashing：大部分時間都在換入、換出頁面，而非執行程式。

解題方法

設實體記憶體可提供 $m$ 個 frame。對第 $i$ 個行程，在最近 $\Delta$ 次記憶體參考中所使用的頁面集合大小稱為 working-set size：

$$WSS_i(\Delta)$$

所有執行中行程的總記憶體需求為：

$$D=\sum_{i=1}^{n}WSS_i(\Delta)$$

當：

$$D>m$$

所有行程就無法同時保留其主要工作集合，page fault 會大量增加，形成 thrashing。因此改善 CPU utilization 的方向，是降低 page fault，讓更多行程保持 ready 狀態。

題目沒有提供 page fault rate 與磁碟服務時間，因此無法計算改善後的精確 CPU utilization；本題應根據裝置利用率判斷系統瓶頸並提出改善方法。

三種改善方式

1. 降低多道程度（degree of multiprogramming）

   暫停或 swap out 部分行程，使記憶體中的行程數減少。此時：

核心觀念

本題考查 CPU 執行時間與效能的比較。

CPU 執行時間公式為：

$$T_{\text{CPU}}=\text{Instruction Count}\times \text{CPI}\times \text{Clock Cycle Time}$$

也可寫成：

$$T_{\text{CPU}}=\frac{\text{Instruction Count}\times \text{CPI}}{\text{Clock Rate}}$$

同一 ISA 下，執行相同程式時所需的指令數相同，設為 $I$。機器效能與執行時間成反比：

$$\text{Performance}=\frac{1}{T_{\text{CPU}}}$$

解題方法

先將兩部機器的時脈資訊統一成「每條指令的平均執行時間」。

機器 P 的 clock cycle time 為 $250\text{ ps}$，因此其 clock rate 為：

$$f_P=\frac{1}{250\text{ ps}} =\frac{1}{250\times 10^{-12}} =4\times 10^9\text{ Hz} =4.0\text{ GHz}$$

機器 Q 的 clock rate 為 $2.0\text{ GHz}$，因此其 clock cycle time 為：

$$t_Q=\frac{1}{2.0\times 10^9} =500\text{ ps}$$

對相同程式，指令數皆為 $I$。

機器 P 的執行時間：

核心觀念

本題考查管線處理器的：

• 管線時脈週期：由所有階段中延遲最大的階段決定。
• 管線填充時間：第一筆指令必須依序通過全部 $5$ 個階段。
• 穩態吞吐量：管線填滿後，每一個時脈週期可完成一筆指令。

假設管線暫存器延遲忽略不計，且沒有任何 pipeline stall。

解題方法

五個管線階段的延遲分別為：

$$5\text{ ns},\ 4\text{ ns},\ 6\text{ ns},\ 10\text{ ns},\ 5\text{ ns}$$

每一個階段必須在同一個時脈週期內完成，因此時脈週期至少要等於最慢階段的延遲：

$$T_{\text{cycle}}=\max(5,4,6,10,5)=10\text{ ns}$$

共有 $5$ 個階段。對 $N$ 筆連續指令而言：

• 第一筆指令需要 $5$ 個週期完成；
• 之後每增加一筆指令，只需再增加 $1$ 個週期；
• 因此總共需要

$$5+(N-1)=N+4$$

個週期。

所以最小執行時間為：

核心觀念

本題考查 Cache miss 對 CPI 的影響。實際 CPI 可表示為：

$$\text{實際 CPI} = \text{命中時 CPI} + \text{每指令平均 Cache miss 次數} \times \text{Miss penalty（以 cycle 計）}$$

由於指令快取與資料快取分離：

• 每一條指令都需存取一次 instruction cache。
• 只有 20% 的指令會存取 data cache。
• 題目給定的 CPI $=2$ 已包含 Cache 命中時的正常成本，因此只需額外加入 miss penalty。

解題方法

先將 miss penalty 的時間換算成處理器週期。

處理器頻率為 $2.5\text{ GHz}$，每個 cycle 的時間為：

$$T=\frac{1}{2.5\times 10^9} =0.4\text{ ns}$$

因此，$20\text{ ns}$ 相當於：

$$\text{Miss penalty} = \frac{20\text{ ns}}{0.4\text{ ns/cycle}} =50\text{ cycles}$$

接著分別計算兩種 Cache 造成的額外 CPI。

指令快取方面，每條指令都會存取 instruction cache，miss rate 為 $2\%$：

$$\text{I-cache 額外 CPI} = 1\times 0.02\times 50 =1$$

核心觀念

本題考查：

1. CNN 的二維卷積運算。
2. IEEE 754 單精度浮點數格式。
3. 十六進位位元表示與十進位浮點數的轉換。

輸入特徵圖為 $3\times4$，卷積核為 $2\times2$，採用 stride $=1$、不補零的 valid convolution，因此輸出大小為：

$$(3-2+1)\times(4-2+1)=2\times3$$

每個輸出元素都是輸入的 $2\times2$ 區塊與卷積核逐元素相乘後相加。

IEEE 754 數值轉換

輸入值

所有輸入 $a$ 到 $l$ 的位元表示為：

$$\texttt{0xC0800000}$$

此數的 IEEE 754 欄位為：

• sign bit：$1$，表示負數
• exponent：$10000001_2=129$，實際指數為 $129-127=2$
• fraction：$0$

因此：

$$\texttt{0xC0800000}=-(1.0)\times 2^2=-4.0$$

卷積核參數

$w,x,y,z$ 的位元表示為：

$$\texttt{0x40000000}$$

其 IEEE 754 欄位為：

• sign bit：$0$
• exponent：$10000000_2=128$，實際指數為 $128-127=1$
• fraction：$0$

因此：

$$\texttt{0x40000000}=(1.0)\times2^1=2.0$$

解題方法

輸入特徵圖可表示為：

$$\begin{bmatrix} a & b & c & d\\ e & f & g & h\\ i & j & k & l \end{bmatrix}$$

卷積核為：

$$\begin{bmatrix} w & x\\ y & z \end{bmatrix}$$

核心觀念

本題涵蓋數位邏輯設計（Digital Logic Design）與計算機結構（Computer Architecture）的兩個核心主題：

1. 正反器（Flip-Flop）之動態時序約束（Timing Constraints）：
   邊緣觸發正反器的關鍵動態參數包含：建立時間（Setup Time, $T_{\text{setup}}$）、時脈到輸出延遲（Clock-to-Q Delay, $T_{\text{c2Q}}$）與保持時間（Hold Time, $T_{\text{hold}}$）。同步順序電路必須滿足建立時間約束以避免產生亞穩態（Metastability），這決定了系統的最高運作頻率與最小時脈週期 $T_{\text{clk, min}}$。
2. 流水線（Pipelining）效能與阿姆達爾定律（Amdahl's Law）：
   將組合邏輯 Datapath 切分為 $N$ 個階段（Stages）時，理想加速比（Speedup）為 $N$。然而在實際系統中，受到流水線暫存器開銷（Pipeline Register Overhead）、階段不平衡（Unbalanced Stages）與流水線冒險（Pipeline Hazards）引起的停頓（Stalls）影響，存在無法隨 $N$ 縮小的非可改善部分，因此可透過阿姆達爾定律證明其實際加速比必然小於 $N$。

---

解題方法

1. 子題 (1)：繪製標準邊緣觸發正反器的時序圖，標示時脈信號（$CLK$）、輸入信號（$D$）與輸出信號（$Q$），並分別針對 $T_{\text{setup}}$、$T_{\text{c2Q}}$ 與 $T_{\text{hold}}$ 給出嚴謹的定義。
2. 子題 (2)：考慮兩個前後相連的暫存器 $R_1$ 與 $R_2$ 及其間的關鍵路徑組合邏輯（延遲為 $T_{\text{cp}}$）。自時脈觸發邊緣起算，分析資料由 $R_1$ 傳播至 $R_2$ 必須滿足的時間下限約束，導出 $T_{\text{clk, min}}$，並說明 $T_{\text{hold}}$ 不納入最小時脈週期公式的原因。
3. 子題 (3)：建立阿姆達爾定律數學模型：
   $\text{Speedup} = \frac{1}{(1 - f) + \frac{f}{S}}$
   將流水線化過程中的固定時間開銷（暫存器延遲、階段不平衡、Hazard Stalls）映射至不可改善的比例 $(1-f)$，證明當加速倍數 $S = N$ 時，總加速比無法達到理想值 $N$。

---

子題詳解

(1) 正反器時序圖與參數定義

• (a) 建立時間（Setup Time, $T_{\text{setup}}$）：在時脈觸發邊緣（Active Clock Edge）之前，輸入資料信號 $D$ 必須保持穩定不變的最短時間。若資料在此區間內發生變動，正反器將無法正確鎖存資料並可能陷入亞穩態。
• (b) 時脈到輸出延遲（Clock-to-Q Delay, $T_{\text{c2Q}}$）：在時脈觸發邊緣發生之後，輸出端 $Q$ 產生對應的穩定新資料所需的時間延遲（即正反器自身的傳播延遲）。
• (c) 保持時間（Hold Time, $T_{\text{hold}}$）：在時脈觸發邊緣發生之後，輸入資料信號 $D$ 仍必須繼續保持穩定不變的最短時間，以防止新資料過早變化而破壞當前的採樣。

時序圖（Timing Diagram）：

CLK       : ___________/¯¯¯¯¯¯¯¯¯¯¯¯¯\___________
                       ^
                 Active Edge
                       |<--Tsetup-->|<--Thold-->|
D (Input) : ------------<   Stable Data   >------------
                             Valid Window

Q (Output): ------------------------<   New Output   >
                       |<-  Tc2Q  ->|

---

(2) 同步電路最小時脈週期推導

考慮由暫存器 $R_1$、關鍵路徑組合邏輯電路（延遲為 $T_{\text{cp}}$）與暫存器 $R_2$ 組成的同步路徑：

1. 傳播時間分析：
   • 在第一個時脈觸發邊緣 $t_1$，$R_1$ 採樣輸入。經過 $T_{\text{c2Q}}$ 時間後，$R_1$ 的輸出 $Q_1$ 更新為穩定新資料。
   • 新資料經組合邏輯運算傳播，經過關鍵路徑延遲 $T_{\text{cp}}$ 後抵達 $R_2$ 的輸入端 $D_2$。
   • 資料到達 $D_2$ 並穩定所需的最短時間點為：$t_1 + T_{\text{c2Q}} + T_{\text{cp}}$。
2. Setup Time 約束條件：
   • 下一個時脈觸發邊緣發生於 $t_2 = t_1 + T_{\text{clk}}$。
   • 為使 $R_2$ 正確採樣，資料必須在 $t_2$ 發生前的 $T_{\text{setup}}$ 時間即抵達並保持穩定：
     $t_1 + T_{\text{c2Q}} + T_{\text{cp}} \le t_1 + T_{\text{clk}} - T_{\text{setup}}$
   • 消去 $t_1$ 後整理可得：
     $T_{\text{clk}} \ge T_{\text{c2Q}} + T_{\text{cp}} + T_{\text{setup}}$
     $\therefore T_{\text{clk, min}} = T_{\text{c2Q}} + T_{\text{cp}} + T_{\text{setup}}$
3. $T_{\text{hold}}$ 之作用說明：
   • $T_{\text{hold}}$ 用於規範「最短路徑延遲（Contamination Delay, $T_{\text{cd}}$）」之限制條件：$T_{\text{c2Q}} + T_{\text{cd}} \ge T_{\text{hold}}$。

核心觀念

移位暫存器由 D 正反器串接而成，相鄰兩級之間的路徑須同時滿足：

$T_{\text{clk}}\ \ge\ T_{\text{C2Q}}+T_{\text{comb}}+T_{\text{setup}}\qquad(\text{setup})$

$T_{\text{C2Q}}+T_{\text{comb}}\ \ge\ T_{\text{hold}}\qquad(\text{hold，假設無時脈偏移})$

其中 $T_{\text{comb}}$ 是兩級之間的延遲（這裡只有反相器）。

解題方法

(1) 正反器數量。 4 位元需要儲存 4 個位元，最少 4 個 D 正反器，串成 $\mathrm{FF}_0\to\mathrm{FF}_1\to\mathrm{FF}_2\to\mathrm{FF}_3$。

(2) 是否需要反相器：檢查 hold。 若 $Q_i$ 直接接到 $D_{i+1}$，$T_{\text{comb}}=0$：

$T_{\text{C2Q}}+0=10\ \text{ps}<T_{\text{hold}}=30\ \text{ps}$

hold time 不足，必須在級間加入延遲，題目提供的延遲元件就是反相器。

(3) 每級最少幾個反相器。 設級間有 $n$ 個反相器：

$10+50n\ \ge\ 30\ \Rightarrow\ n\ge 1$

1 個反相器（延遲 $50\ \text{ps}$）就能滿足，此時 hold 餘裕為 $10+50-30=30\ \text{ps}$。3 條級間路徑共需 3 個反相器。每經過一個反相器，資料極性會翻轉一次，因此相鄰各級儲存的是交替極性的資料（這在讀出時可以由已知的極性對應處理）。

(4) 邏輯圖。