115 年國立成功大學人工智慧科技碩士學位學程《計算機組織與系統（計算機組織及作業系統）》考古題與詳解

Question 1

問題1: Core Mechanisms (25 points)

Column A: Mechanism

Pipelining
L2 Cache
Cache Block (Line)
MESI Protocol
PC-relative Addressing

Column B: Characteristics & Distractors
(A) Primarily increases Throughput; single instruction Latency slightly increases due to register overhead.
(B) Splits execution to reduce single instruction Latency to exactly 1/N.
(C) Hardware guarantees zero Data Hazards between any instructions.
(D) Designed to intercept L1 Misses and reduce Global Miss Rate to DRAM.
(E) Designed to be smaller than L1 to achieve higher speeds.
(F) Uses block transfers to exploit Spatial Locality.
(G) Optimizes access for non-contiguous structures like Linked Lists.
(H) Requires 'Invalidate' signal before writing to Shared data.
(I) Managed by OS; triggers Context Switch on write.
(J) Used for conditional branches with limited range (e.g., ±4KB).
(K) Allows jumping to any address without bit-width limits.

Accepted Answer

本題考查計算機組織中的核心機制，包含流水線 (Pipelining)、快取記憶體層級 (L2 Cache)、快取線 (Cache Block)、快取一致性協定 (MESI Protocol) 以及 PC-relative Addressing。需要將 Column A 的機制與 Column B 中最適合的特性或敘述配對。

核心觀念：

Pipelining (流水線)：將一條指令的執行分解為多個階段，並讓多條指令同時處於不同的執行階段，以提高整體吞吐量 (Throughput)。然而，由於流水線暫存器 (pipeline registers) 的引入，單一指令的延遲 (Latency) 可能會略微增加。
L2 Cache (第二層快取)：L1 快取主要優化命中時間 (Hit Time)，而 L2 快取則主要用於降低整體快取未命中率 (Global Miss Rate)，防止過多的未命中事件傳遞到較慢的 DRAM。L2 快取通常比 L1 快取更大，但速度也較慢。
Cache Block (Line) (快取線)：快取記憶體是以固定大小的區塊 (block) 或稱快取線 (line) 為單位進行傳輸的。當 CPU 需要讀取或寫入資料時，會將整個快取線從主記憶體或較低層級的快取載入到較高層級的快取中。這利用了空間局部性 (Spatial Locality)，因為程式通常會連續存取相鄰的資料。
MESI Protocol (MESI 協定)：這是一種基於硬體的快取一致性協定，用於在多核心系統中維護各個私有快取之間的資料一致性。它為每個快取線定義四種狀態：Modified (M)、Exclusive (E)、Shared (S)、Invalid (I)。當核心要寫入處於 Shared 狀態的資料時，必須先廣播 Invalidate 訊號，使其他核心的複本失效，然後才能獲得獨佔權並進入 Modified 狀態。
PC-relative Addressing (PC 相對定址)：這種定址模式是相對於程式計數器 (Program Counter, PC) 的值來計算記憶體位址。

Question 2

問題2: Scenario Analysis (25 points)

Column A: Scenario
6. Convert Single-cycle to 5-stage Pipeline
7. Accessing 2D array via A[j][i] (Strided)
8. Core A writes to 'Shared' (S) data
9. Branch target is 1MB away
10. L1 Miss but L2 Hit

Column B: Behavior & Distractors
(A) Total program execution time instantly becomes 1/5th.
(B) Individual instruction Latency may slightly increase due to overhead.
(C) Destroys Spatial Locality; Miss Rate increases significantly.
(D) Spatial locality remains excellent regardless of access order.
(E) Can write directly since it is Shared; no need to signal.
(F) Must acquire Bus Exclusivity and Invalidate Core B's copy.
(G) Hardware auto-extends 12-bit offset to 32-bit.
(H) Compiler uses 'Invert Branch + Unconditional Jump' combination.
(I) Access latency is faster than DRAM but slower than L1.
(J) L2 speed is identical to L1, zero latency difference.
(K) Triggers Write-Through to HDD directly.

Accepted Answer

核心觀念 本題是「情境與計算機組織行為配對」，涵蓋五個觀念： 1. 單週期處理器改為五級管線後，主要提升的是吞吐量，不是每一條指令的延遲。 2. 二維陣列的存放順序會影響快取的空間區域性。 3. 快取一致性協定中，處於 Shared 狀態的資料不可直接寫入。 4. 條件分支的 PC-relative 位移欄位有範圍限制，超出範圍需改寫指令序列。 5. 快取階層中，L1 Miss, L2 Hit 的延遲介於 L1 命中與主記憶體存取之間。 解題方法與逐題推導 6. Convert Single-cycle to 5-stage Pipeline 五級管線通常分為： $$ IF ightarrow ID ightarrow EX ightarrow MEM ightarrow WB $$ 單週期處理器中，每條指令都必須在一個很長的時脈週期內完成，因此： $$ T{	ext{single}} = N 	imes T{	ext{single-cycle}} $$ 五級管線在沒有停滯時，$N$ 條指令約需： $$ T{	ext{pipeline}}=(N+4)	imes T{	ext{pipeline-cycle}} $$ 其中額外的 $4$ 個週期是管線填充時間；實際上還可能受到資料相依、分支錯誤預測與管線暫存器負擔影響。因此，總執行時間不會立即變成原本的 $1/5$。 管線的主要優勢是提高吞吐量。單一指令必須經過五個管線階段，且每級之間需要管線暫存器，因此個別指令的完成延遲可能略增。 配對：(B)。 7. Accessing 2D array via A[j][i]（Strided） 以 C 語言常見的 row-major 排列為例，若每列有 $C$ 個元素、每個元素佔 $w$ bytes，則： $$ \operatorname{Address}(A[j][i]) = \operatorname{Base} + (jC+i)w $$ 題目已標示為 Strided，表示存取時沿著跨列方向移動。例如固定 $i$、讓 $j$ 連續增加時，相鄰兩次存取的位址差為： $$ \Delta = Cw $$ 這通常大於同一 cache line 中相鄰元素的距離，導致每次存取都可能載入新的 cache line，空間區域性降低，快取未命中率顯著上升。 配對：(C)。 8. Core A writes to Shared（S）data 在 MESI 快取一致性協定中，Shared 表示多個核心可能同時持有相同且乾淨的快取副本。 若 Core A 要寫入處於 Shared 狀態的資料，必須先取得寫入權限，通常透過 BusUpgr 或 Read For Ownership 類似的匯流排交易，使其他核心的副本失效： $$ S{	ext{Core A}} …

Question 3

11. (2%) On a traditional HDD (mechanical disk), which statement about common I/O schedulers and latency is correct? (a). SCAN (elevator) can reduce average seek distance versus FCFS, but it may still cause long waits for some requests depending on direction and queueing, so fairness improves compared with SSTF but tail latency is not necessarily minimized. (b). SSTF always provides the best tail latency because it minimizes seek distance for every request, which prevents starvation by construction. (c). FCFS minimizes variance in response time because it preserves arrival order, which avoids reordering induced latency spikes. (d). The same scheduler conclusions apply unchanged to NVMe SSDs because both HDDs and SSDs are dominated by seek time.

Accepted Answer

本題考查傳統硬碟 (HDD) 的 I/O 排程器 (I/O Schedulers) 的特性，以及它們對延遲 (Latency) 和公平性 (Fairness) 的影響。

核心觀念：

I/O Schedulers：目的是優化磁碟 I/O 操作，常見的排程器有 FCFS (First-Come, First-Served)、SSTF (Shortest Seek Time First)、SCAN (Elevator Algorithm) 等。
Seek Time：在 HDD 中，磁頭需要移動到正確的磁軌才能讀取或寫入資料，這個移動時間稱為尋道時間 (Seek Time)。這是 HDD 存取時間的主要組成部分。
Rotational Latency：磁碟片需要旋轉，使目標扇區到達磁頭下方，這個旋轉時間稱為旋轉延遲 (Rotational Latency)。
Transfer Time：資料實際傳輸所需的時間。
Latency：總的 I/O 操作時間，通常是 Seek Time + Rotational Latency + Transfer Time。
Tail Latency：指最差情況下的延遲，即 95% 或 99% 的請求完成時間。
Fairness：確保所有請求都有機會被處理，避免某些請求被無限期延遲 (starvation)。

排程器比較：

FCFS (First-Come, First-Served)：按照請求到達的順序處理。簡單，公平，但尋道時間可能很長，導致整體效能較差。
SSTF (Shortest Seek Time First)：總是選擇離當前磁頭位置最近的請求來服務。這能最小化尋道時間，提高吞吐量，但可能導致離磁頭較遠的請求長時間等待 (starvation)。
SCAN (Elevator Algorithm)：磁頭從磁碟的一端開始，向另一端移動，處理沿途的請求。到達另一端後，反向移動，再次處理沿途的請求。這避免了 SSTF 的 starvation 問題，並且通常比 FCFS 有更好的吞吐量。然而，在 SCAN 的過程中，位於磁頭反向移動方向上的請求可能會等待較長時間。
C-SCAN (Circular SCAN)：類似 SCAN，但磁頭到達另一端後會立即回到起始端，然後再開始下一次掃描。這提供了更均勻的延遲分佈。

選項分析：
(a) SCAN (elevator) can reduce average seek distance versus FCFS, but it may still cause long waits for some requests depending on direction and queueing, so fairness improves compared with SSTF but tail latency is not necessarily minimized.

Question 4

13. (2%) Three periodic tasks have deadlines equal to periods: T1: C1 = 1 ms, P1 = 4 ms T2: C2 = 1.5 ms, P2 = 6 ms T3: C3 = 2 ms, P3 = 12 ms Assume the standard theoretical model: independent periodic tasks, preemptive uniprocessor, deadline equals period, negligible overhead. Which statement is correct when applying utilization-based schedulability tests? (a). The total utilization is U=1/4+1.5/6+2/12 = 2/3. Therefore the task set is schedulable under EDF (since U ≤ 1), and it is also guaranteed schedulable under RM bound for n = 3, U ≤ 3 (2^(1/3)-1) ≈ 0.779. (b). The task set is not schedulable under EDF because EDF requires U < 1. (c). The task set is not guaranteed schedulable under RM because RM's utilization bound is U ≤ ln 2 ≈ 0.693 for three tasks. (d). The task set is guaranteed s…

Accepted Answer

核心觀念 每個週期性工作的利用率為 $$ Ui=\frac{Ci}{Pi} $$ 總利用率為 $$ U=\sumi Ui $$ 本題採用的是標準模型：單一處理器、可搶先、工作彼此獨立，且相對截止期限 $Di=Pi$。 - EDF（Earliest Deadline First）：對於截止期限等於週期的工作集合，在理想條件下，$U\leq 1$ 即可保證可排程。 - RM（Rate Monotonic）：週期越短者優先權越高。$n$ 個工作的 Liu–Layland 利用率保證界限為 $$ U\leq n\left(2^{1/n}-1\right) $$ 此界限是充分條件，不是必要條件。 --- 解題方法與計算 各工作的利用率為 $$ U1=\frac{1}{4}=\frac14 $$ $$ U2=\frac{1.5}{6}=\frac14 $$ $$ U3=\frac{2}{12}=\frac16 $$ 因此總利用率為 $$ U=\frac14+\frac14+\frac16 =\frac12+\frac16 =\frac23 \approx 0.6667 $$ 套用 EDF 測試 $$ U=\frac23\leq 1 $$ 因此，此工作集合在 EDF 下可排程。 套用 RM 利用率界限 本題有 $n=3$ 個工作，因此 $$ U{\mathrm{RM}}=3\left(2^{1/3}-1\right) $$ $$ \approx 3(1.2599-1) \approx 0.7798 $$ 比較可得 $$ \frac23\approx 0.6667\leq 0.7798 $$ 因此，此工作集合也符合 RM 的利用率保證條件。 RM 的優先權順序為 $$ T1T2T3 $$ 因為週期依序為 $4$ ms、$6$ ms、$12$ ms。 --- 選項分析 (a) 正確。 總利用率計算為

Question 5

15. (2%) In a system with a non-coherent CPU data cache, a device performs DMA writes into a memory buffer that the CPU later reads. Which action is correct for the CPU/driver to ensure it reads the newly DMA-written data? (a). Before starting the DMA write, the CPU must invalidate the cache lines of the destination buffer; after DMA completion, no cache maintenance is needed because DMA writes update memory directly. (b). The CPU should clean (write back) the cache lines after DMA completion, because writing back ensures the cache and memory match the device output. (c). No cache maintenance is required as long as the buffer is aligned to cache-line boundaries and the DMA length is a multiple of the cache-line size. (d). After DMA completion, the CPU must invalidate (or otherwise ensure i…

Accepted Answer

核心觀念 本題考查「非一致性快取（non-coherent cache）」與 DMA 的資料同步。 在非一致性快取系統中： - CPU 讀取資料時，可能先從自己的 data cache 取得資料。 - DMA 裝置直接寫入主記憶體，不會自動通知或更新 CPU cache。 - 因此，CPU cache 可能保留 DMA 寫入前的舊資料，形成 stale cache data。 DMA 寫入、CPU 讀取的正確同步方向是： 1. DMA 完成後，讓 CPU cache 中涵蓋該 buffer 的 cache line 失效。 2. CPU 再次讀取時，便會從主記憶體取得 DMA 寫入的新資料。 其中： - Clean／Write back：將 cache 中的資料寫回主記憶體，適合 CPU 修改資料後交給裝置讀取。 - Invalidate：丟棄 cache 中的副本，使後續讀取重新從主記憶體取得資料，適合裝置寫入後交給 CPU 讀取。 解題方法 題目流程為： $$ 	ext{DMA 裝置} ightarrow 	ext{主記憶體 buffer} ightarrow 	ext{CPU 讀取} $$ DMA 寫入主記憶體後，CPU cache 可能仍保存舊資料： $$ 	ext{CPU cache} = 	ext{舊資料}, \qquad 	ext{主記憶體} = 	ext{DMA 寫入的新資料} $$ 若 CPU 直接讀取，可能命中 cache，得到舊資料。因此 DMA 完成後，CPU 或 driver 必須對涵蓋該 buffer 的 cache lines 執行 invalidate，或使用等效的同步機制： $$ 	ext{DMA 完成} ightarrow 	ext{Invalidate CPU cache lines} ightarrow 	ext{CPU 讀取新資料} $$ 所以正確答案是 (d)。 選項分析 (a) 錯誤。 DMA 開始前使目的 buffer 的 cache lines 失效，在某些系統上可避免 CPU cache 中的舊資料或髒資料影響 DMA；但這個動作不足以保證 DMA 完成後 CPU 讀到新資料。

Question 6

12. (2%) Which situation is most likely to increase write amplification in an SSD using an FTL with garbage collection? (a). Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection. (b). Using overprovisioning, because extra spare area reduces available user space and forces the SSD to copy more data on every write. (c). Placing hot and cold data together in the same physical blocks, because it reduces metadata overhead and lowers the frequency of garbage collection. (d). Small random overwrites to a nearly full drive, especially without TRIM, because many blocks contain a mix of valid and invalid pages, increasing copying during garbage collection.

Accepted Answer

本題考查 SSD (Solid State Drive) 中的寫入放大 (Write Amplification) 現象，特別是與 FTL (Flash Translation Layer) 和垃圾回收 (Garbage Collection) 相關的情境。

核心觀念：

SSD 的寫入特性: SSD 的 NAND Flash 儲存單元是以頁 (page) 為單位讀取和寫入，但以塊 (block) 為單位擦除。一次擦除操作會擦除整個塊中的所有頁。
FTL (Flash Translation Layer): FTL 是 SSD 內部的一個韌體層，負責將邏輯區塊位址 (Logical Block Address, LBA) 映射到物理 Flash 位址 (Physical Block Address, PBA)。它也負責管理 Flash 的磨損均衡 (wear leveling) 和垃圾回收。
Garbage Collection (GC): 由於 Flash 不支援原地更新 (in-place update)，當需要修改一個頁的資料時，SSD 控制器不能直接覆蓋舊資料。它必須將該頁所在的整個塊中的有效 (valid) 資料讀取出來，然後將修改後的資料寫入到一個新的、已擦除的塊中，最後再擦除包含舊資料的塊。這個過程稱為垃圾回收。
Write Amplification (WA): 指 SSD 實際寫入到 NAND Flash 的資料量與主機寫入 SSD 的資料量之比。WA > 1 表示寫入放大。WA 的增加會加速 Flash 的磨損，並降低寫入效能。
- $WA = \frac{\text{Data written to NAND Flash}}{\text{Data written by Host}}$
原因: 寫入放大主要發生在：
1. GC 過程: 為了擦除一個塊，需要先讀取並重寫該塊中的有效資料。
2. Over-provisioning: SSD 預留的額外空間，用於 GC 和磨損均衡，但這意味著主機寫入的資料量相對較少，而 SSD 內部需要複製的資料量相對較多。
3. 小的隨機寫入: 尤其是在硬碟快滿時，許多塊包含部分有效和部分無效頁，GC 時需要複製的有效資料比例較高。
4. TRIM 命令: TRIM 命令通知 SSD 控制器哪些邏輯區塊不再被使用，SSD 控制器可以標記這些頁為無效，減少 GC 時需要複製的資料量。

選項分析：
(a) Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection.
* 大型連續寫入到一個「大部分為空」的媒體時，新的資料會寫入到新的、已擦除的塊中。此時，GC 的負擔較小，因為不需要從舊塊中複製太多有效資料。
* 「sequentiality maximizes valid page copying during garbage collection」是錯誤的。連續寫入到空媒體時，GC 複製的有效頁最少。
* 此情況通常 WA 較低。

(b) **Using overprovisioning, because extra spare area reduces available user space a

Question 7

14. (2%) Which statement about priority inversion and its mitigation is correct? (a). Priority inheritance ensures that a high-priority task can never be blocked by a lower-priority task, since the lower-priority task is immediately boosted above all others and runs to completion. (b). Priority inversion occurs only with non-preemptive kernels; in a fully preemptive RTOS it cannot happen because the scheduler always runs the highest-priority task. (c). Replacing mutexes with spinlocks eliminates priority inversion because spinlocks never block; they only busy-wait. (d). Priority ceiling protocols can prevent deadlock and bound blocking time by restricting which tasks may lock a resource based on a preassigned ceiling, but they may reduce parallelism by being conservative.

Accepted Answer

正確敘述： (d) Priority ceiling 協議能透過事先設定資源的「上限優先權」限制哪些任務可取得鎖，從而避免死結並對阻塞時間提供上界；但因必須保守地提升取得鎖的任務優先權，會犧牲一定的平行度。 為何其他選項錯誤

Question 8

13. (2%) Three periodic tasks have deadlines equal to periods: T1: C1 = 1 ms, P1 = 4 ms T2: C2 = 1.5 ms, P2 = 6 ms T3: C3 = 2 ms, P3 = 12 ms Assume the standard theoretical model: independent periodic tasks, preemptive uniprocessor, deadline equals period, negligible overhead. Which statement is correct when applying utilization-based schedulability tests? (a). The total utilization is U=1/4+1.5/6+2/12 = 2/3. Therefore the task set is schedulable under EDF (since U ≤ 1), and it is also guaranteed schedulable under RM bound for n = 3, U ≤ 3 (2^(1/3)-1) ≈ 0.779. (b). The task set is not schedulable under EDF because EDF requires U < 1. (c). The task set is not guaranteed schedulable under RM because RM's utilization bound is U ≤ ln 2 ≈ 0.693 for three tasks. (d). The task set is guaranteed s…

Accepted Answer

核心觀念 每個週期性工作的利用率為 $$ Ui=\frac{Ci}{Pi} $$ 總利用率為 $$ U=\sumi Ui $$ 本題採用的是標準模型：單一處理器、可搶先、工作彼此獨立，且相對截止期限 $Di=Pi$。 - EDF（Earliest Deadline First）：對於截止期限等於週期的工作集合，在理想條件下，$U\leq 1$ 即可保證可排程。 - RM（Rate Monotonic）：週期越短者優先權越高。$n$ 個工作的 Liu–Layland 利用率保證界限為 $$ U\leq n\left(2^{1/n}-1\right) $$ 此界限是充分條件，不是必要條件。 --- 解題方法與計算 各工作的利用率為 $$ U1=\frac{1}{4}=\frac14 $$ $$ U2=\frac{1.5}{6}=\frac14 $$ $$ U3=\frac{2}{12}=\frac16 $$ 因此總利用率為 $$ U=\frac14+\frac14+\frac16 =\frac12+\frac16 =\frac23 \approx 0.6667 $$ 套用 EDF 測試 $$ U=\frac23\leq 1 $$ 因此，此工作集合在 EDF 下可排程。 套用 RM 利用率界限 本題有 $n=3$ 個工作，因此 $$ U{\mathrm{RM}}=3\left(2^{1/3}-1\right) $$ $$ \approx 3(1.2599-1) \approx 0.7798 $$ 比較可得 $$ \frac23\approx 0.6667\leq 0.7798 $$ 因此，此工作集合也符合 RM 的利用率保證條件。 RM 的優先權順序為 $$ T1T2T3 $$ 因為週期依序為 $4$ ms、$6$ ms、$12$ ms。 --- 選項分析 (a) 正確。 總利用率計算為

Question 9

9. (2%) Assume a demand-paged system with 3 physical frames and an LRU replacement policy. The page reference string is: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How many page faults occur? (a). 8 (b). 9 (c). 10 (d). 11

Accepted Answer

頁框數 $=3$，採用 LRU。逐次檢視參照字串，列出缺頁與置換情形： | 參照 | 框內容 (最舊→最新) | 缺頁? | 累計缺頁 | |------|-------------------|------|----------| | 1 | ① | ✓ | 1 | | 2 | ① ② | ✓ | 2 | | 3 | ① ② ③ | ✓ | 3 | | 4 | 1 ② ③ → ④ | ✓ | 4 |

Question 10

10. (2%) Consider enabling huge pages for a workload that scans large arrays with strong spatial locality. Which statement is correct? (a). Huge pages can reduce TLB misses by increasing TLB reach, but they can increase internal fragmentation and can make some operations, such as copy on write and page migration, more expensive because the unit of management is larger. (b). Huge pages primarily improve performance by eliminating page faults, since huge pages prevent the kernel from needing demand paging for that region. (c). Huge pages reduce page table walk overhead only if the CPU has a larger TLB, otherwise the miss rate cannot change. (d). Huge pages always reduce memory usage because fewer page table entries are needed, so fragmentation cannot increase.

Accepted Answer

本題考查「Huge Pages」的優缺點，以及它們對效能的影響，特別是對於具有良好空間局部性 (spatial locality) 的工作負載。

核心觀念：

Paging (分頁): 作業系統將記憶體劃分為固定大小的頁 (pages)，通常為 4KB。
Page Table (頁表): 用於將虛擬頁面映射到物理頁框。每個進程都有自己的頁表。
TLB (Translation Lookaside Buffer): 一個快取，用於儲存最近使用的虛擬頁面到物理頁框的映射，以加速頁表查找。
Page Table Walk: 當 TLB 未命中時，CPU 需要訪問頁表來查找映射。這個過程稱為頁表行走 (page table walk)，它涉及多次記憶體訪問，開銷較大。
Huge Pages: 允許系統使用比標準頁面更大的頁面大小，例如 2MB 或 1GB。
Spatial Locality: 程式傾向於存取在時間或空間上相鄰的記憶體位置。

Huge Pages 的優點：

減少 TLB Miss: 由於頁面更大，一個 TLB 條目可以覆蓋更大的記憶體區域，從而減少 TLB 未命中率，降低頁表行走的需求。
減少頁表大小: 總體所需的頁表條目數量會減少。

Huge Pages 的缺點：

增加內部碎片 (Internal Fragmentation): 如果一個應用程式只需要使用 Huge Page 中的一小部分，其餘部分將被浪費，因為 Huge Page 是不可分割的。
增加某些操作的開銷: 像頁面遷移 (page migration)、寫時複製 (copy-on-write) 等操作，由於處理的記憶體單元更大，開銷可能會增加。
記憶體分配的靈活性降低: 系統可能難以分配大塊連續的記憶體來滿足 Huge Page 的需求。

選項分析：
(a) Huge pages can reduce TLB misses by increasing TLB reach, but they can increase internal fragmentation and can make some operations, such as copy on write and page migration, more expensive because the unit of management is larger.
* 「reduce TLB misses by increasing TLB reach」：正確。更大的頁面意味著一個 TLB 條目可以覆蓋更大的地址空間。
* 「increase internal fragmentation」：正確。

Question 11

12. (2%) Which situation is most likely to increase write amplification in an SSD using an FTL with garbage collection? (a). Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection. (b). Using overprovisioning, because extra spare area reduces available user space and forces the SSD to copy more data on every write. (c). Placing hot and cold data together in the same physical blocks, because it reduces metadata overhead and lowers the frequency of garbage collection. (d). Small random overwrites to a nearly full drive, especially without TRIM, because many blocks contain a mix of valid and invalid pages, increasing copying during garbage collection.

Accepted Answer

本題考查 SSD (Solid State Drive) 中的寫入放大 (Write Amplification) 現象，特別是與 FTL (Flash Translation Layer) 和垃圾回收 (Garbage Collection) 相關的情境。

核心觀念：

SSD 的寫入特性: SSD 的 NAND Flash 儲存單元是以頁 (page) 為單位讀取和寫入，但以塊 (block) 為單位擦除。一次擦除操作會擦除整個塊中的所有頁。
FTL (Flash Translation Layer): FTL 是 SSD 內部的一個韌體層，負責將邏輯區塊位址 (Logical Block Address, LBA) 映射到物理 Flash 位址 (Physical Block Address, PBA)。它也負責管理 Flash 的磨損均衡 (wear leveling) 和垃圾回收。
Garbage Collection (GC): 由於 Flash 不支援原地更新 (in-place update)，當需要修改一個頁的資料時，SSD 控制器不能直接覆蓋舊資料。它必須將該頁所在的整個塊中的有效 (valid) 資料讀取出來，然後將修改後的資料寫入到一個新的、已擦除的塊中，最後再擦除包含舊資料的塊。這個過程稱為垃圾回收。
Write Amplification (WA): 指 SSD 實際寫入到 NAND Flash 的資料量與主機寫入 SSD 的資料量之比。WA > 1 表示寫入放大。WA 的增加會加速 Flash 的磨損，並降低寫入效能。
- $WA = \frac{\text{Data written to NAND Flash}}{\text{Data written by Host}}$
原因: 寫入放大主要發生在：
1. GC 過程: 為了擦除一個塊，需要先讀取並重寫該塊中的有效資料。
2. Over-provisioning: SSD 預留的額外空間，用於 GC 和磨損均衡，但這意味著主機寫入的資料量相對較少，而 SSD 內部需要複製的資料量相對較多。
3. 小的隨機寫入: 尤其是在硬碟快滿時，許多塊包含部分有效和部分無效頁，GC 時需要複製的有效資料比例較高。
4. TRIM 命令: TRIM 命令通知 SSD 控制器哪些邏輯區塊不再被使用，SSD 控制器可以標記這些頁為無效，減少 GC 時需要複製的資料量。

選項分析：
(a) Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection.
* 大型連續寫入到一個「大部分為空」的媒體時，新的資料會寫入到新的、已擦除的塊中。此時，GC 的負擔較小，因為不需要從舊塊中複製太多有效資料。
* 「sequentiality maximizes valid page copying during garbage collection」是錯誤的。連續寫入到空媒體時，GC 複製的有效頁最少。
* 此情況通常 WA 較低。

(b) **Using overprovisioning, because extra spare area reduces available user space a

Question 12

12. (2%) Which situation is most likely to increase write amplification in an SSD using an FTL with garbage collection? (a). Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection. (b). Using overprovisioning, because extra spare area reduces available user space and forces the SSD to copy more data on every write. (c). Placing hot and cold data together in the same physical blocks, because it reduces metadata overhead and lowers the frequency of garbage collection. (d). Small random overwrites to a nearly full drive, especially without TRIM, because many blocks contain a mix of valid and invalid pages, increasing copying during garbage collection.

Accepted Answer

本題考查 SSD (Solid State Drive) 中的寫入放大 (Write Amplification) 現象，特別是與 FTL (Flash Translation Layer) 和垃圾回收 (Garbage Collection) 相關的情境。

核心觀念：

SSD 的寫入特性: SSD 的 NAND Flash 儲存單元是以頁 (page) 為單位讀取和寫入，但以塊 (block) 為單位擦除。一次擦除操作會擦除整個塊中的所有頁。
FTL (Flash Translation Layer): FTL 是 SSD 內部的一個韌體層，負責將邏輯區塊位址 (Logical Block Address, LBA) 映射到物理 Flash 位址 (Physical Block Address, PBA)。它也負責管理 Flash 的磨損均衡 (wear leveling) 和垃圾回收。
Garbage Collection (GC): 由於 Flash 不支援原地更新 (in-place update)，當需要修改一個頁的資料時，SSD 控制器不能直接覆蓋舊資料。它必須將該頁所在的整個塊中的有效 (valid) 資料讀取出來，然後將修改後的資料寫入到一個新的、已擦除的塊中，最後再擦除包含舊資料的塊。這個過程稱為垃圾回收。
Write Amplification (WA): 指 SSD 實際寫入到 NAND Flash 的資料量與主機寫入 SSD 的資料量之比。WA > 1 表示寫入放大。WA 的增加會加速 Flash 的磨損，並降低寫入效能。
- $WA = \frac{\text{Data written to NAND Flash}}{\text{Data written by Host}}$
原因: 寫入放大主要發生在：
1. GC 過程: 為了擦除一個塊，需要先讀取並重寫該塊中的有效資料。
2. Over-provisioning: SSD 預留的額外空間，用於 GC 和磨損均衡，但這意味著主機寫入的資料量相對較少，而 SSD 內部需要複製的資料量相對較多。
3. 小的隨機寫入: 尤其是在硬碟快滿時，許多塊包含部分有效和部分無效頁，GC 時需要複製的有效資料比例較高。
4. TRIM 命令: TRIM 命令通知 SSD 控制器哪些邏輯區塊不再被使用，SSD 控制器可以標記這些頁為無效，減少 GC 時需要複製的資料量。

選項分析：
(a) Large sequential writes to mostly empty media, because sequentiality maximizes valid page copying during garbage collection.
* 大型連續寫入到一個「大部分為空」的媒體時，新的資料會寫入到新的、已擦除的塊中。此時，GC 的負擔較小，因為不需要從舊塊中複製太多有效資料。
* 「sequentiality maximizes valid page copying during garbage collection」是錯誤的。連續寫入到空媒體時，GC 複製的有效頁最少。
* 此情況通常 WA 較低。

(b) **Using overprovisioning, because extra spare area reduces available user space a

Question 13

13. (2%) Three periodic tasks have deadlines equal to periods: T1: C1 = 1 ms, P1 = 4 ms T2: C2 = 1.5 ms, P2 = 6 ms T3: C3 = 2 ms, P3 = 12 ms Assume the standard theoretical model: independent periodic tasks, preemptive uniprocessor, deadline equals period, negligible overhead. Which statement is correct when applying utilization-based schedulability tests? (a). The total utilization is U=1/4+1.5/6+2/12 = 2/3. Therefore the task set is schedulable under EDF (since U ≤ 1), and it is also guaranteed schedulable under RM bound for n = 3, U ≤ 3 (2^(1/3)-1) ≈ 0.779. (b). The task set is not schedulable under EDF because EDF requires U < 1. (c). The task set is not guaranteed schedulable under RM because RM's utilization bound is U ≤ ln 2 ≈ 0.693 for three tasks. (d). The task set is guaranteed s…

Accepted Answer

核心觀念 每個週期性工作的利用率為 $$ Ui=\frac{Ci}{Pi} $$ 總利用率為 $$ U=\sumi Ui $$ 本題採用的是標準模型：單一處理器、可搶先、工作彼此獨立，且相對截止期限 $Di=Pi$。 - EDF（Earliest Deadline First）：對於截止期限等於週期的工作集合，在理想條件下，$U\leq 1$ 即可保證可排程。 - RM（Rate Monotonic）：週期越短者優先權越高。$n$ 個工作的 Liu–Layland 利用率保證界限為 $$ U\leq n\left(2^{1/n}-1\right) $$ 此界限是充分條件，不是必要條件。 --- 解題方法與計算 各工作的利用率為 $$ U1=\frac{1}{4}=\frac14 $$ $$ U2=\frac{1.5}{6}=\frac14 $$ $$ U3=\frac{2}{12}=\frac16 $$ 因此總利用率為 $$ U=\frac14+\frac14+\frac16 =\frac12+\frac16 =\frac23 \approx 0.6667 $$ 套用 EDF 測試 $$ U=\frac23\leq 1 $$ 因此，此工作集合在 EDF 下可排程。 套用 RM 利用率界限 本題有 $n=3$ 個工作，因此 $$ U{\mathrm{RM}}=3\left(2^{1/3}-1\right) $$ $$ \approx 3(1.2599-1) \approx 0.7798 $$ 比較可得 $$ \frac23\approx 0.6667\leq 0.7798 $$ 因此，此工作集合也符合 RM 的利用率保證條件。 RM 的優先權順序為 $$ T1T2T3 $$ 因為週期依序為 $4$ ms、$6$ ms、$12$ ms。 --- 選項分析 (a) 正確。 總利用率計算為

Question 14

14. (2%) Which statement about priority inversion and its mitigation is correct? (a). Priority inheritance ensures that a high-priority task can never be blocked by a lower-priority task, since the lower-priority task is immediately boosted above all others and runs to completion. (b). Priority inversion occurs only with non-preemptive kernels; in a fully preemptive RTOS it cannot happen because the scheduler always runs the highest-priority task. (c). Replacing mutexes with spinlocks eliminates priority inversion because spinlocks never block; they only busy-wait. (d). Priority ceiling protocols can prevent deadlock and bound blocking time by restricting which tasks may lock a resource based on a preassigned ceiling, but they may reduce parallelism by being conservative.

Accepted Answer

正確敘述： (d) Priority ceiling 協議能透過事先設定資源的「上限優先權」限制哪些任務可取得鎖，從而避免死結並對阻塞時間提供上界；但因必須保守地提升取得鎖的任務優先權，會犧牲一定的平行度。 為何其他選項錯誤

Question 15

15. (2%) In a system with a non-coherent CPU data cache, a device performs DMA writes into a memory buffer that the CPU later reads. Which action is correct for the CPU/driver to ensure it reads the newly DMA-written data? (a). Before starting the DMA write, the CPU must invalidate the cache lines of the destination buffer; after DMA completion, no cache maintenance is needed because DMA writes update memory directly. (b). The CPU should clean (write back) the cache lines after DMA completion, because writing back ensures the cache and memory match the device output. (c). No cache maintenance is required as long as the buffer is aligned to cache-line boundaries and the DMA length is a multiple of the cache-line size. (d). After DMA completion, the CPU must invalidate (or otherwise ensure i…

Accepted Answer

核心觀念 本題考查「非一致性快取（non-coherent cache）」與 DMA 的資料同步。 在非一致性快取系統中： - CPU 讀取資料時，可能先從自己的 data cache 取得資料。 - DMA 裝置直接寫入主記憶體，不會自動通知或更新 CPU cache。 - 因此，CPU cache 可能保留 DMA 寫入前的舊資料，形成 stale cache data。 DMA 寫入、CPU 讀取的正確同步方向是： 1. DMA 完成後，讓 CPU cache 中涵蓋該 buffer 的 cache line 失效。 2. CPU 再次讀取時，便會從主記憶體取得 DMA 寫入的新資料。 其中： - Clean／Write back：將 cache 中的資料寫回主記憶體，適合 CPU 修改資料後交給裝置讀取。 - Invalidate：丟棄 cache 中的副本，使後續讀取重新從主記憶體取得資料，適合裝置寫入後交給 CPU 讀取。 解題方法 題目流程為： $$ 	ext{DMA 裝置} ightarrow 	ext{主記憶體 buffer} ightarrow 	ext{CPU 讀取} $$ DMA 寫入主記憶體後，CPU cache 可能仍保存舊資料： $$ 	ext{CPU cache} = 	ext{舊資料}, \qquad 	ext{主記憶體} = 	ext{DMA 寫入的新資料} $$ 若 CPU 直接讀取，可能命中 cache，得到舊資料。因此 DMA 完成後，CPU 或 driver 必須對涵蓋該 buffer 的 cache lines 執行 invalidate，或使用等效的同步機制： $$ 	ext{DMA 完成} ightarrow 	ext{Invalidate CPU cache lines} ightarrow 	ext{CPU 讀取新資料} $$ 所以正確答案是 (d)。 選項分析 (a) 錯誤。 DMA 開始前使目的 buffer 的 cache lines 失效，在某些系統上可避免 CPU cache 中的舊資料或髒資料影響 DMA；但這個動作不足以保證 DMA 完成後 CPU 讀到新資料。

Question 16

1. (8%) An orphan process is a process whose parent process no longer exists, i.e., either it has finished or terminated without waiting for its child processes to terminate. Please finish the following code within the box, which can create an orphan process. #include <sys/types.h #include <unistd.h #include <stdio.h #include <stdlib.h int main () { int pid = fork(); if (pid 0) { // this is parent process } else if (pid == 0) { // this is child process } return 0; }

Accepted Answer

核心觀念 本題考查 Unix/Linux 的 fork() 與 orphan process（孤兒程序）。 呼叫 fork() 後，原程序會分裂成兩個獨立程序： - 父程序：fork() 回傳子程序的 PID，故 pid 0。 - 子程序：fork() 回傳 $0$，故 pid == 0。 - 建立失敗：回傳 $-1$。 孤兒程序的成立條件是： 1. 子程序仍在執行。 2. 父程序先行結束。 3. 父程序沒有等候子程序完成。 父程序結束後，作業系統會將子程序重新指定給 PID 1 的系統程序，或指定給負責收養孤兒程序的 subreaper。因此，子程序仍能繼續執行，只是其父程序已經改變。 解題方法 在父程序分支中立即結束父程序；在子程序分支中先暫停一段時間，確保父程序有機會先結束，再由子程序印出自己的 PID 與父 PID。 關鍵安排如下： $$ 	ext{父程序先結束} \quad \Longrightarrow \quad 	ext{子程序繼續執行並成為孤兒程序} $$ sleep(1) 的作用是讓子程序延後執行，方便觀察父程序已結束以及子程序已被重新收養。 完成後的程式碼

Question 17

2. (12%) Read the following description about the LSM tree and answer the questions. An LSM-tree is a disk-oriented data structure that improves write efficiency by buffering updates in memory and flushing them to disk in batches. By doing so, it turns many small random writes into fewer sequential writes, which is especially beneficial for write-heavy workloads. LevelDB is a popular open-source LSM-tree based key-value store. New updates are first appended to a write-ahead log (WAL) for crash recovery, then inserted into an in-memory MemTable (typically a skip list). When the MemTable becomes full, it is frozen as an Immutable MemTable, and a new MemTable is created for incoming writes. The Immutable MemTable is then flushed to disk as an SSTable, where keys are stored in sorted order. On…

Accepted Answer

(a) Write Amplification 寫入時資料會經歷以下階段： 1. 先寫入 WAL → 1 次寫入。 2. 插入 MemTable → 內存寫入，仍需在 flush 時寫入磁碟。 3. MemTable 滿了被凍結成 Immutable MemTable，整個表一次 flush 成 SSTable 放入 L0 → 2 次磁碟寫入。 4. L0 超過門檻後觸發 compaction，將 L0 與 L1、L2… 的 SSTable 以 merge‑sort 合併，產生新的 SSTable 再寫回磁碟。一次資料可能在每層 compaction 中被重新寫入多次。 因此，寫放大=原始寫入 + 多次因 flush 及跨層 compaction 產生的重寫次數。 (b) Read Amplification 讀取時依序檢查：MemTable → Immutable MemTable → L0 → L1 → … → deepest level。 L0 的 SSTable 允許 key 範圍重疊，一個 key 可能同時存在於多個 L0 檔案，必須逐一檔案搜尋。 從 L1 起每層檔案不重疊，但仍需檢查每層的至少一個檔案。 所以讀放大來源於需要在多個資料結構與多個檔案中搜尋同一筆 key，特別是 L0 重疊檔案會使搜尋檔案數量大幅增加。

115 年國立成功大學人工智慧科技碩士學位學程《計算機組織與系統（計算機組織及作業系統）》

第 1 題

第 2 題

第 3 題

第 4 題

套用 EDF 測試

套用 RM 利用率界限

第 5 題

第 6 題

第 7 題

第 8 題

套用 EDF 測試

套用 RM 利用率界限

第 9 題

第 10 題

第 11 題

第 12 題

第 13 題

套用 EDF 測試

套用 RM 利用率界限

第 14 題

第 15 題

第 16 題

第 17 題

其他考古題

115 年成功大學的其他科目

成功大學《計算機組織與系統》其他年度

115 年 國立成功大學人工智慧科技碩士學位學程《計算機組織與系統（計算機組織及作業系統）》

第 1 題

第 2 題

第 3 題

第 4 題

套用 EDF 測試

套用 RM 利用率界限

第 5 題

第 6 題

第 7 題

第 8 題

套用 EDF 測試

套用 RM 利用率界限

第 9 題

第 10 題

第 11 題

第 12 題

第 13 題

套用 EDF 測試

套用 RM 利用率界限

第 14 題

第 15 題

第 16 題

第 17 題

其他考古題

115 年成功大學的其他科目

成功大學《計算機組織與系統》其他年度

115 年國立成功大學人工智慧科技碩士學位學程《計算機組織與系統（計算機組織及作業系統）》