109 年 國立臺灣大學醫療器材與醫學影像研究所《計算機結構與作業系統(B)》

核心觀念

本題把一維卷積串接到處理器效能分析，重點包括：

• 卷積索引：$g[m]$ 的數學索引為 $-M,\ldots,M$，C 陣列必須轉成非負索引。
• 管線相依性：無 forwarding 時，相依指令必須等到前一指令的 WB 階段才能讀取結果。
• 快取區域性與映射衝突：工作集合小於快取容量，仍會發生直接對映衝突。
• 平行化與 roofline：增加運算能力能否加速，取決於資料相依性與記憶體頻寬。

解題方法

原卷的處理器圖為 IF、ID、EX、MEM、WB 五階段管線；roofline 圖的橫軸為 FLOPs/Byte，縱軸為 GFLOPS，水平運算上限是 $16$ GFLOPS，斜線通過 $(1/2,8)$，因此記憶體頻寬為 $16$ GB/s。

令卷積核長度為 $K=2M+1$。題目未指定邊界處理，以下採用零補齊，輸出長度仍為 $N$；快取分析另外明列所需假設。

(a) C 程式：零補齊的一維卷積

將數學索引 $m$ 改成陣列索引 $j=m+M$，則

$$g_{\mathrm{array}}[j]=g[j-M],\qquad 0\le j<K.$$

建立補齊陣列 $p$，令 $p[M+n]=f[n]$，其餘位置為零。原公式轉為

$$y[n]=\sum_{j=0}^{K-1}p[n+K-1-j]g_{\mathrm{array}}[j].$$

#include <stdlib.h>

/*
 * p：已在左右各補 M 個零，長度為 N + 2M
 * g[j]：數學上的 g[j-M]，長度為 K = 2M+1
 * y：輸出陣列，長度為 N
 */
void convolve_padded(const float *p, const float *g,
                     float *y, int N, int M)
{
    int K = 2 * M + 1;

    for (int n = 0; n < N; ++n) {
        float sum = 0.0f;

        for (int j = 0; j < K; ++j) {
            /* 反向走訪輸入，以實作題目的卷積定義 */
            sum += p[n + K - 1 - j] * g[j];
        }

        y[n] = sum;
    }
}

/*
 * 前提：N > 0、M >= 0，索引與配置大小均在有效範圍內；
 * f、g、y 指向足夠大的陣列，y 不與輸入重疊。
 * 成功回傳 0，配置失敗回傳 -1。
 */
int convolution(const float *f, const float *g,
                float *y, int N, int M)
{
    size_t length = (size_t)N + 2 * (size_t)M;
    float *p = calloc(length, sizeof(float));
    if (p == NULL)
        return -1;

    /* calloc 已將左右邊界設為零 */
    for (int n = 0; n < N; ++n)
        p[M + n] = f[n];

    convolve_padded(p, g, y, N, M);

    free(p);
    return 0;
}

時間複雜度為 $O(NK)$；零補齊陣列的額外空間為 $O(N+K)$。以下效能分析只計算卷積核心，不計配置及補齊成本。

(b) 組合語言

採用 RV32IF，下列函式對應 convolve_padded。參數 a0～a4 分別放入 p、g、y、N、M；浮點乘法與加法分開執行。

# void convolve_padded(p, g, y, N, M)
# a0=p，a1=g，a2=y，a3=N，a4=M

convolve_padded:
    slli t1, a4, 1          # t1 = 2M = K-1
    addi t6, t1, 1         # t6 = K
    li   t0, 0             # t0 = n
    beqz a3, done

outer_loop:
    fmv.w.x ft0, zero      # sum = 0.0f
    li   t2, 0             # t2 = j

inner_loop:
    add  t3, t0, t1
    sub  t3, t3, t2        # t3 = n + K - 1 - j
    slli t3, t3, 2         # 每個 float 佔 4 bytes
    add  t4, a0, t3        # t4 = &p[n+K-1-j]

    slli a5, t2, 2
    add  t5, a1, a5        # t5 = &g[j]

    flw  ft1, 0(t4)        # 載入輸入值
    flw  ft2, 0(t5)        # 載入卷積核係數
    fmul.s ft3, ft1, ft2   # product = p[...] * g[j]
    fadd.s ft0, ft0, ft3   # sum += product

    addi t2, t2, 1         # ++j
    blt  t2, t6, inner_loop

    slli a6, t0, 2
    add  a6, a2, a6
    fsw  ft0, 0(a6)        # y[n] = sum

    addi t0, t0, 1         # ++n
    blt  t0, a3, outer_loop

done:
    ret

時間複雜度仍為 $O(NK)$；核心使用固定數量暫存器，額外空間為 $O(1)$。

(c) 無 forwarding 的管線 hazards

依題目的理想五階段模型，假設浮點運算也使用此管線；另採用常見的「同週期先 WB 寫入、再 ID 讀取」規則。

1. RAW 資料冒險

相依來源包括：

• 位址計算：add → sub → slli → add。
• 載入後使用：flw → fmul.s。
• 乘積累加：fmul.s → fadd.s。
• 迴圈計數：addi t2 → blt t2。
• 累加結果寫回：fadd.s → fsw，是否停頓取決於中間指令間隔。

相鄰相依指令的時序如下：

指令	週期 1	週期 2	週期 3	週期 4	週期 5	週期 6
生產者	IF	ID	EX	MEM	WB
消費者		IF	ID 等待	ID 等待	ID 讀取	EX

因此，相鄰 RAW 相依需要 2 個停頓週期；中間有一條獨立指令時需要 1 個，至少兩條時可避開此停頓。不同相依的等待時間會互相重疊，不能將所有相依對的停頓直接相加。

2. 控制冒險

分支到 EX 才確定方向。若持續抓取預測路徑上的指令，預測錯誤時須清除 IF、ID 中的兩條指令，基本代價為 2 個週期。分支比較值尚未寫回時，還會先受到 RAW 停頓影響。

3. 其他冒險

依序發射、依序執行及寫回，不會產生需要停頓的 WAR、WAW 冒險。圖中指令與資料記憶體分離，加上題目假定快取命中，不計 IF、MEM 的記憶體停頓。

(d) 分支預測

在 IF 階段預測分支方向，並透過 BTB 提供預測目標位址，使處理器能立即抓取下一條指令。

迴圈分支大多會跳回迴圈，可採用：

• 靜態的向後分支預測 taken。
• 動態的二位元飽和計數器；單次迴圈退出不會立刻翻轉長期預測方向。

預測正確時可消除基本控制停頓；錯誤時在 EX 清除錯誤路徑。令分支比例為 $f_b$、錯誤率為 $p_m$，則

$$\mathrm{CPI}\approx 1+\frac{\text{資料冒險停頓週期}}{\text{動態指令數}} +2f_bp_m.$$

分支預測降低控制冒險成本，分支操作數的 RAW 相依仍須處理。

(e) 迴圈展開

將內層迴圈展開，例如一次處理四個係數，並使用四個獨立累加器：

float s0 = 0, s1 = 0, s2 = 0, s3 = 0;
int j = 0;

for (; j + 3 < K; j += 4) {
    s0 += p[n + K - 1 - j]     * g[j];
    s1 += p[n + K - 2 - j]     * g[j + 1];
    s2 += p[n + K - 3 - j]     * g[j + 2];
    s3 += p[n + K - 4 - j]     * g[j + 3];
}

float sum = (s0 + s1) + (s2 + s3);

for (; j < K; ++j)
    sum += p[n + K - 1 - j] * g[j];

y[n] = sum;

組合語言排程時，可先安排多組載入，再安排乘法與各自的累加，使相依指令之間出現獨立工作。

效益為：

• 減少迴圈計數及分支指令。
• 打散單一累加器的相依鏈。
• 提供更多指令排程空間，以填補無 forwarding 的等待時間。

時間複雜度仍為 $O(NK)$，額外空間為 $O(1)$。代價是程式碼與暫存器需求增加；浮點加法順序改變後，末位捨入結果不保證完全相同。

(f) 快取未命中率

快取容量為

$$16\times16=256\text{ bytes},$$

每個區塊可容納

$$16/4=4$$

個浮點數。直接對映的索引為

$$\operatorname{index}(a)= \left\lfloor\frac{a}{16}\right\rfloor\bmod16.$$

題目未提供 $N$、陣列位址及對齊、寫入策略，實際未命中率不能由 $M$ 單獨決定；以下先給出忽略映射衝突的理想估算。

核心觀念

本題為作業系統（Operating Systems）綜合觀念題，涵蓋以下核心單元：

1. 執行緒與多處理器（Threads & Multiprocessing）：多執行緒開銷、阿姆達爾定律（Amdahl's Law）與系統吞吐量（Throughput）。
2. 虛擬記憶體（Virtual Memory）：分頁替換演算法（Page Replacement Algorithms）與貝萊迪異常（Belady's Anomaly）。
3. CPU 排程（CPU Scheduling）：輪轉排程法（Round-Robin, RR）的時間切片（Time Quantum）與平均周轉時間（Average Turnaround Time）之關係，以及即時排程（Real-Time Scheduling）的定義。
4. 行程合作與死鎖（Process Cooperation & Deadlock）：行程合作理由（Modularity 等）、銀行家演算法（Banker's Algorithm）中的安全狀態（Safe State）與死鎖（Deadlock）的集合關係。
5. 檔案系統與韌體（File Systems & Firmware）：UNIX 檔案共享語意（UNIX Semantics）、ROM/Flash 與 RAM 之執行速度差異。
6. 併行控制（Concurrency Control）：資料庫兩階段鎖定協定（Two-Phase Locking, 2PL）的串列化（Serializability）與死鎖（Deadlock）特性。

---

解題方法

針對觀念是非題，採用以下切入點判斷：

1. 反例驗證法（Counterexample Verification）：若敘述包含絕對化或單調性假設（例如「越多越好」、「切片越大周轉時間越小」），尋找經典反例（如 FIFO 分頁替換導致的 Belady's Anomaly、RR 時間切片過大退化為 FCFS 產生的 Convoy Effect、過多執行緒引發的 Context Switch 開銷），即可判定為 No。
2. 權威定義比對法（Definition Matching）：依據 Silberschatz 作業系統經典教科書與資料庫系統理論之標準定義，檢視語意是否準確（例如 Safe State 必無死鎖、2PL 能保證 Conflict Serializability 但不保證無死鎖、RTOS 排程的核心在於 Deadline 時限而非單純追求極速）。

---

選項分析

(a) The more threading, the more performance.

• 分析：No。過多的執行緒會帶來額外的系統開銷，包含執行緒建立與銷毀成本、頻繁的內文切換（Context Switch）、同步鎖競爭（Lock Contention）以及快取失效（Cache Thrashing）。此外，根據阿姆達爾定律（Amdahl's Law），程式中不可平行化的串行部分限制了加速比的上限。當執行緒數量遠超物理 CPU 核心負載時，效能反而會急遽下降。

(b) The more frames, the less page fault rates.

• 分析：No。在某些分頁替換演算法（如先到先出法 FIFO）中，增加分配給行程的實體記憶體框架數（Frames），在特定參考序列下反而會導致分頁錯失次數增加，此現象稱為貝萊迪異常（Belady's Anomaly）。只有堆疊演算法（Stack Algorithms，如 LRU、OPT）才能確保框架增加時分頁錯失率不上升。

(c) The bigger time quantum, the less average turnaround time.

• 分析：No。在輪轉排程（Round-Robin, RR）中，時間切片（Time Quantum $q$）與平均周轉時間（Average Turnaround Time）並非單調遞減關係。若時間切片過大（例如 $q \to \infty$），RR 會退化為先到先服務（FCFS），長工作會阻塞短工作（護衛效應 Convoy Effect），導致平均周轉時間增加；若時間切片過小，過多的內文切換也會拉長周轉時間。因此時間切片變大不必然降低平均周轉時間。

(d) Multiprocessor system increases throughput.

• 分析：Yes。多處理器系統透過多個實體 CPU 或處理核心同時平行執行多個行程／執行緒，能在單位時間內完成更多的工作量，從而提升系統整體的吞吐量（Throughput）。

(e) Firmware can be executed faster in RAM.

• 分析：Yes。韌體（Firmware）原始存放於 ROM 或 Flash Memory 等非揮發性記憶體中，其讀取速度與頻寬遠低於主記憶體（DRAM/RAM）。將韌體載入（Shadowing）至 RAM 中執行，可顯著降低指令讀取延遲，因此執行速度更快。

(f) Modularity is one of the reasons to support process cooperation.

核心觀念

本題考查作業系統與儲存系統中的**壞軌管理（Bad Block Management）機制，以及底層物理重對映（Remapping）對上層磁碟排程（Disk Scheduling）**效能的影響。關鍵觀念與定義如下：

1. 磁區備用（Sector Sparing / Forwarding / Redirection）：當磁碟控制器發現壞軌時，將該邏輯磁區映射（Map）至預留的備用磁區（Spare Sector）。
2. 磁區滑移（Sector Slipping）：當發現壞軌時，將壞軌之後的所有磁區依次向後順移一個物理位置，並佔用最後的備用磁區，以維持邏輯位址與物理位址的連續性。
3. 磁碟排程影響（Impact on Disk Scheduling）：磁碟排程演算法（如 SSTF、SCAN、C-SCAN）基於「邏輯磁區位址相近則物理尋道時間（Seek Time）與旋轉延遲（Rotational Latency）較短」的假設。物理連續性的破壞會影響排程演算法的預估效能。

---

解題方法

一、 Sector Sparing 與 Sector Slipping 之差異比較

1. 磁區備用（Sector Sparing）

   • 運作機制：磁碟控制器在每個磁軌（Track）或磁柱（Cylinder）末端預留少量的備用磁區。若磁區 $i$ 損壞，控制器將對磁區 $i$ 的讀寫請求重新轉向（Forward）至備用磁區 $S$。
   • 發生時機：通常用於動態執行階段（Run-time）。當磁碟在運作過程中出現新的軟性/硬性壞軌時，可即時進行替換。
   • 物理連續性：破壞連續性。邏輯上連續的磁區（例如 $i-1, i, i+1$），其物理位置變成在備用磁區區域，導致存取磁區 $i$ 時需要額外的磁頭移動或旋轉等待。

2. 磁區滑移（Sector Slipping）

   • 運作機制：若物理磁區 $i$ 損壞，控制器將邏輯磁區 $i$ 映射至物理磁區 $i+1$，邏輯磁區 $i+1$ 映射至物理磁區 $i+2$，依此類推，所有後續磁區整體向後「滑移」一個位置，最終佔用磁軌末端的備用磁區。
   • 發生時機：通常在**低階格式化（Low-level Formatting）**或離線磁碟維護階段進行，因為滑移過程需要重新寫入該磁軌上受影響區域的所有資料。
   • 物理連續性：保持連續性。邏輯位址連續的磁區，其實體物理位置依然保持緊密相鄰。

比較項目	磁區備用 (Sector Sparing)	磁區滑移 (Sector Slipping)
映射方式	單一壞軌直接重新指派至備用磁區	壞軌後方所有磁區依序向後順移一位
處理時機	系統執行階段（Run-time）即時處理	低階格式化或建置維護階段處理
物理連續性	破壞物理連續性（磁區位址離散）	維持物理連續性（磁區位址連續）
資料搬移量	僅需設定控制器映射表	需搬移該磁軌上壞軌後方的所有資料
效能影響	存取備用磁區時產生額外旋轉延遲/尋道	存取效能完全不受影響

---

二、 對磁碟排程（Disk Scheduling）的影響

磁碟排程演算法（如 SSTF、SCAN、C-SCAN）的核心目標是透過調整 I/O 請求順序來最小化磁頭尋道時間（Seek Time）與旋轉延遲（Rotational Latency）。兩者對磁碟排程的具體影響如下：

1. 受 Sector Sparing 的影響：
   • 預期失效與效能下降：排程器根據邏輯塊位址（LBA）排序請求，假設 $LBA_k$ 與 $LBA_{k+1}$ 物理相鄰。

核心觀念

本題的核心在於**工作集模型（Working-Set Model）**在記憶體管理與資源調配上的延伸應用。

工作集模型由 Peter J. Denning 提出，其理論基礎為程序的存取局部性（Locality of Reference），包含時間局部性（Temporal Locality）與空間局部性（Spatial Locality）。模型的主要定義與運算公式如下：

1. 工作集視窗（Working-Set Window, $\Delta$）：設定一個固定數量的記憶體存取參考次數（或時間區段）作為滑動視窗。
2. 工作集（Working Set, $WS_i$）與工作集大小（Working-Set Size, $WSS_i$）：程序 $P_i$ 在最近 $\Delta$ 次記憶體參考過程中所存取的獨立分頁（Page）集合為 $WS_i$，其分頁總數稱為 $WSS_i = |WS_i|$。
3. 系統總記憶體需求量（Total Demand, $D$）：
   $D = \sum_{i=1}^{n} WSS_i$
4. 臨界判斷與防抖動機制：設實體記憶體總頁框數為 $M$。
   • 若 $D > M$：代表實體記憶體無法滿足所有執行程序的最小工作集，系統將發生抖動（Thrashing）。此時 OS 必須暫停（Swap out）部分程序，釋放頁框。
   • 若 $D < M$：代表實體記憶體尚有空閒，OS 可提高多元程式化程度（Degree of Multiprogramming, DOM），引入新程序以最大化資源利用率。

---

解題方法

工作集模型的抽象本質為：「利用最近滑動時間視窗 $\Delta$ 內的行為特徵，動態預估各單元的需求量，以防止資源過載驟降（Thrashing），同時達成最大化資源吞吐量」。

除了作業系統虛擬記憶體的分頁管理外，只要滿足**「資源容量有限」與「存取具局部性變化」**的系統環境，皆可有效導入該模型。最主要且經典的延伸應用領域為：

1. 雲端虛擬化管理（Hypervisor / 虛擬機器動態記憶體配置）
2. 資料庫與快取系統（Database Buffer Pool 及 CDN 快取管理）
3. CPU 快取管理與預取機制（CPU Cache Partitioning & Prefetching）

解答時應先說明工作集模型的共通運作架構，再針對特定應用詳細描述其對應的 $\Delta$、資源標的、防抖動與調控作法。

---

選項分析

本題為研究所入學考試之論述簡答題（非選擇題），針對三大主要適用領域進行詳細分析與運作機制說明：

應用領域一：虛擬化與雲端運算（Hypervisor VM Dynamic Memory Allocation）

• 適用性分析：極佳。在雲端環境（如 VMware ESXi、KVM、Xen）中，實體主機（Host）需同時執行多台虛擬機器（VM）。若為每台 VM 靜態保留最大記憶體，會造成極大的資源浪費；若配置過少，則 Guest OS 內部會頻繁引發 Page Fault 與 Disk I/O。
• 運作機制（How）：
  1. Hypervisor 在滑動視窗 $\Delta$ 內動態監控每台 VM 的記憶體存取頁面，估算出該 VM 當前的 $WSS_{VM}$。
  2. 當特定 VM 進入閒置狀態（$WSS_{VM}$ 縮小）時，Hypervisor 透過 Memory Ballooning 機制收回空閒實體頁框。
  3. 當另一台 VM 負載激增（$WSS_{VM}$ 擴大）時，即時將釋放出的實體頁框動態配置給該 VM。
  4. 效益：確保實體主機總需求 $\sum WSS_{VM} \le M_{Host}$，在完全避免主機層級抖動的前提下，達成最高的虛擬機器集約度與記憶體超賣（Oversubscription）效率。

應用領域二：資料庫緩衝池與儲存快取管理（Database Buffer Pool & Storage Cache Management）

• 適用性分析：極佳。

觀念解析

1. 異步 I/O（Asynchronous I/O）：網路延遲為無界限（Unbounded Network Delay），各節點封包到達時間與順序不固定。採用非阻塞（Non-blocking）異步接收機制，避免因等待特定節點傳輸而阻塞整個收集系統。
2. 同步 I/O（Synchronous I/O Timer）：設定每 10 秒觸發一次的同步計時器執行緒，專責將當前已收集封包中傳輸時間戳記（Transmission Timestamp, $t_{tx}$）最早者輸出至螢幕，以爭取最高積分。
3. 資料結構與執行緒同步：使用以 $t_{tx}$ 為鍵值的**最小堆積（Min-Heap / Min-Priority Queue）存放暫存封包，並透過互斥鎖（Mutex）**保護共享緩衝區，確保多執行緒並行讀寫之安全性。

---

精簡關鍵程式碼 (Pseudo Code)