115 一般警察特考二等 刑事警察人員類別數位鑑識組 計算機系統(包括計算機結構、作業系統) 考古題詳解

核心觀念

管線（pipeline）將一條指令的執行拆成數個階段，例如取指、解碼、執行、存取記憶體與寫回；處理器以重疊方式同時處理多條指令，使不同指令分別占用不同階段。管線主要提升的是指令完成率（throughput），不一定縮短單一指令從開始到完成的延遲（latency）。

若管線有 $k$ 個階段，各階段延遲相同為 $\Delta t$，且沒有停滯或其他損失，則 $n$ 條指令的理想執行時間為：

未採管線時，若每條指令依序使用全部 $k$ 個階段，執行時間為：

當指令數量很大時，管線的理想加速比趨近 $k$。實際上，管線速度受階段延遲不均、管線暫停與額外控制成本影響，通常低於此理想值。

解題方法與作答

本題依「效能提升原因 → 理想效能落差來源 → 對應改善方法」作答。第（二）、（三）題可按結構、資料、控制三類管線危障整理，並補充管線資源衝突與管線暫停成本。

（一）為什麼 pipeline 可以提升處理器的效能？（5 分）

管線把指令執行工作切分成多個階段，並讓不同指令在同一時間分別執行不同階段。當第一條指令進入後續階段時，下一條指令即可進入前一階段；管線充滿後，理想情況下每個時脈週期都能完成一條指令。

因此，管線使處理器各功能單元能更充分地並行工作，提升指令完成率與硬體利用率。它並非把單條指令的執行步驟消除，而是重疊多條指令的執行階段。

（二）有哪些因素會使 pipeline 無法達到理想上的效能？（10 分）

1. 管線階段延遲不均：時脈週期必須配合最慢的階段；較快的階段仍須等待，造成硬體使用效率下降。階段切分不平衡時，整體吞吐量受最慢階段限制。

2. 結構危障（structural hazard）：多條指令同時需要同一項硬體資源，例如指令擷取與資料存取共用同一記憶體埠，導致資源無法同時服務，必須插入停滯週期。

3. 資料危障（data hazard）：一條指令需要前一條指令尚未產生或寫回的資料。常見情況是讀取後寫入危障（RAW）；在可亂序執行或多指令發射的處理器中，也須處理寫入後讀取（WAR）與寫入後寫入（WAW）。

核心觀念

本題考查「循序乘法器」的硬體配置與移位加法演算法。

對兩個 32-bit 數字相乘，完整乘積需要：

$32+32=64\text{ bits}$

循序乘法器通常以每一個 clock cycle 處理乘數的一個位元，因此需要 32 個 clock cycles。其基本流程為：

1. 檢查乘數目前最低位元。
2. 若該位元為 1，將被乘數加入部分乘積。
3. 進行移位。
4. 重複 32 次。

圖 (a) 與圖 (b) 的設計差異

圖 (a)：基本設計

圖 (a) 使用：

• 64-bit ALU
• 64-bit Multiplicand 暫存器
• 64-bit Product 暫存器
• 32-bit Multiplier 暫存器

被乘數每次向左移位，乘數每次向右移位，部分乘積則累加在 64-bit Product 中。

圖 (b)：改善後設計

圖 (b) 將運算重新配置：

• ALU 改為 32-bit
• Multiplicand 暫存器只需保存 32-bit，且不必移位
• 64-bit Product 暫存器同時保存部分乘積與尚未處理的乘數
• Product 暫存器每次向右移位

圖 (b) 以 Product 暫存器的高 32 bits 作為部分乘積區域，低 32 bits 則保存乘數。每次若乘數最低位元為 1，就以 32-bit ALU 將 Multiplicand 加到 Product 的高 32 bits，再將整個 Product 向右移位。

因此，圖 (b) 可以用較小的 ALU 完成相同的 64-bit 乘法。

各小題分析

（一）圖 (a) 的硬體成本比較高？

答案：是。

圖 (a) 使用 64-bit ALU 進行加法，且 Multiplicand 暫存器也須具備 64-bit 寬度。

圖 (b) 使用 32-bit ALU，Multiplicand 暫存器也只需 32 bits，因此可降低：

• ALU 的硬體數量與面積
• 暫存器的位元數
• 部分資料路徑的硬體成本

所以圖 (a) 的硬體成本比較高。

（二）圖 (b) 的運算時脈週期數是圖 (a) 的兩倍？

答案：否。

兩種設計都是循序乘法器，每一個 clock cycle 處理乘數的一個位元。

輸入乘數為 32 bits，因此兩者皆需：

$32\text{ cycles}$

圖 (b) 雖然使用 32-bit ALU，但並未因此將每一個乘法位元拆成兩個 clock cycle；它只是改變資料在暫存器中的配置方式。因此週期數不是圖 (a) 的兩倍。

（三）兩者的乘法運算結果是相同的？

答案：是。

兩種設計都會依照乘數的每一個位元，將相對應的被乘數倍數加入部分乘積。

圖 (a) 是將 Multiplicand 向左移位；圖 (b) 則是將 Product 向右移位，並利用 Product 的高、低區域重新安排部分乘積與乘數的位

核心觀念

本題考查記憶體階層利用程式存取行為的局部性原理，以及直接對映快取與集合相聯快取的衝突情形；最後一小題則辨別虛擬記憶體與永久儲存的用途。

解題方法與各小題解析

（一）空間局部化（spatial locality）

空間局部化是指：程式存取某個記憶體位置後，在短時間內也很可能存取其附近位址的資料。

例如，陣列元素通常依序存取；讀取 A[i] 後，接著常會讀取相鄰的 A[i+1]。因此，快取載入某一記憶體區塊時，通常會一併載入附近的資料，以提高後續命中機會。

（二）時間局部化（temporal locality）

時間局部化是指：程式近期存取過的資料或指令，在不久後再次被存取的機率較高。

例如，迴圈反覆執行同一段指令，或程式多次使用同一個變數。快取保留近期使用的資料，可減少再次從較慢的主記憶體讀取所需時間。

（三）集合相聯快取的擊中率通常較高

在總容量相同的條件下，一般而言，集合相聯快取的擊中率較高。

直接對映快取中，每個主記憶體區塊只能放在快取中唯一指定的位置。若多個常用區塊映射到同一位置，即使快取其他位置仍有空間，也會互相替換，形成衝突失誤。

核心觀念

作業系統排程的目的，是在多個可執行的行程或執行緒競爭處理器時，決定由誰使用處理器、何時使用，以及使用多久。排程器依系統目標分配有限的 CPU 時間，以提升資源利用率與整體效能，並兼顧使用者的等待時間與回應需求。

衡量排程成效時，常見指標包括：

• 處理器利用率：處理器忙於工作的時間比例。
• 吞吐量：單位時間內完成的行程數。
• 周轉時間：行程從進入系統到完成所經過的時間。
• 等待時間：行程在就緒佇列中等待處理器的總時間。
• 回應時間：行程提出要求到首次得到回應的時間。

不同排程方法對這些指標的影響不同，因此沒有一種方法能在所有情境下都達到最佳效果。

解題方法

本題分別考查排程的必要性，以及 FCFS、SJF 的定義與優缺點。作答時，先交代排程要解決的資源分配問題，再說明兩種演算法的排序依據、是否能搶先，以及各自對等待時間、公平性與實作性的影響。

（一）為什麼需要排程？（5 分）

多工系統中，通常有多個行程同時處於就緒狀態，但處理器資源有限；單一處理器在同一時間只能執行一個行程。因此，作業系統需要排程來決定就緒行程取得 CPU 的次序與時機。

排程的主要目的如下：

1. 有效分配處理器時間：使多個行程能依一定規則輪流或依優先性使用 CPU。
2. 提高系統效率：減少 CPU 閒置，提升處理器利用率與整體吞吐量。
3. 控制行程等待與完成時間：避免行程無規則地等待，並改善周轉時間。
4. 提供良好回應與公平性：互動式系統需及時回應使用者，也須避免特定行程長期得不到 CPU。
5. 配合系統目標：批次系統重視吞吐量與周轉時間，互動式系統重視回應時間，實時系統則重視在期限內完成工作。

（二）先到先服務（FCFS）的定義與優缺點（10 分）

定義

先到先服務（First Come First Serve, FCFS）是依行程進入就緒佇列的先後順序分配 CPU：先進入就緒佇列者先執行，後到者依序等待。一般 FCFS 是非搶先式排程；行程取得 CPU 後，會執行至完成或因等待 I/O 等事件而離開 CPU，其他行程才有機會執行。

FCFS 依到達順序排隊，不會因行程所需 CPU 時間較短而優先處理。

優點

• 簡單易實作：可用先進先出的佇列管理就緒行程。
• 公平且容易理解：大致依到達順序服務，較不會讓後到行程插隊。
• 不會因排程本身造成飢餓：只要行程持續留在佇列中，前面的行程完成後便會輪到它。

缺點

• 平均等待時間可能偏高：若長工作排在短工作之前，短工作必須等待長工作完成。
• 可能產生護航效應（convoy effect）：一個 CPU 執行時間很長的行程占住處理器，許多短行程或 I/O 密集行程只能排隊等待，降低系統效率。
• 互動性與回應時間較差：新到的短行程即使很快就能完成，也不能越過隊首的長行程。