114 年 國立成功大學電機工程學系碩士班已組《計算機組織與作業系統》

核心觀念

本題考查計算機效能評估指標 MIPS (Millions of Instructions Per Second) 的定義、影響因素及其作為效能指標的局限性與常見陷阱。

主要定義與計算公式：

1. MIPS 定義：每秒執行的百萬條指令數。
   $\text{MIPS} = \frac{\text{Instruction Count}}{\text{Execution Time} \times 10^6} = \frac{\text{Clock Frequency}}{CPI \times 10^6}$
   其中：

   • $\text{Instruction Count}$ ($IC$)：程式執行的總指令數。
   • $\text{Execution Time}$ ($CPU\text{ Time}$)：程式運行的 CPU 時間。
   • $\text{Clock Frequency}$ ($f$)：CPU 的時脈頻率（Clock Rate）。
   • $CPI$ (Clock cycles Per Instruction)：執行每條指令所需的平均時脈週期數。

2. CPU 時間推導公式：
   $\text{CPU Time} = IC \times CPI \times \text{Clock Cycle Time} = \frac{IC \times CPI}{f}$

3. MIPS 作為效能指標的三大主要缺陷：

   • 無法跨 ISA 比較：不同指令集架構（ISA）完成相同任務所需的指令數（$IC$）不同。
   • 同一硬體上隨程式而異：不同程式的指令組合（Instruction Mix）不同，導致平均 $CPI$ 不同。
   • 與實際執行時間可能反向變動：編譯器優化可能減少指令數但拉高平均 $CPI$，導致 MIPS 降低但執行時間反而變短（即著名的 MIPS 異象 / MIPS Anomaly）。

---

解題方法

評估 MIPS 相關敘述的真偽時，應直接基於公式 $\text{MIPS} = \frac{f}{CPI \times 10^6}$ 進行分析：

1. 檢視 MIPS 是否依賴於變數 $IC$、$CPI$ 與 $f$。
2. 釐清 $CPI$ 受「指令組合（Instruction Mix）」與「記憶體存取延遲（Memory Latency）」影響的機制。
3. 區分「MIPS 提高」與「程式執行速度變快（效能提升）」之間的非必然關係。

---

選項分析

• (a) MIPS is a completely reliable performance metric that remains consistent across different instruction sets.（錯誤）
  • 原因：MIPS 不可靠，且無法跨不同的指令集架構（ISA）進行比較。不同的 ISA（例如 RISC 與 CISC）執行同一個程式所需的指令總數（$IC$）大不相同。CISC 可能只需較少的指令即可完成任務，而 RISC 則需要較多的簡單指令。因此，即便 RISC 機器的 MIPS 較高，其實際執行時間不一定比 CISC 機器短。

核心觀念

本題考驗經典 5 階段 MIPS/RISC-V 順序執行（In-order）管線 CPU（包含 IF、ID、EX、MEM、WB）之管線危害（Pipeline Hazards）與停頓機制（Stalls / Bubbles）。

1. 資料危害（Data Hazards）與前傳（Forwarding / Bypassing）：

   • RAW (Read-After-Write)：後續指令需要讀取前方指令寫入的暫存器資料。若資料已在 ALU 計算完成（EX 階段結束），可透過 EX/MEM 或 MEM/WB 管線暫存器直接前傳至 EX 階段的 ALU 輸入端，達成 0 Stall。
   • Load-Use Hazard：若前方指令為 lw（Load），資料必須到 MEM 階段結束（或讀出記憶體後）才能取得。若緊接的下一筆指令在 EX 階段就要使用該資料，由於時間序無法逆向傳輸（無法從未完成的 MEM 階段前傳回同時間的 EX 階段），因此必須強制插入 1 個 Stall（Bubble）。
   • RAR (Read-After-Read)、WAR (Write-After-Read)、WAW (Write-After-Write)：在傳統順序執行（In-Order Execution）與順序寫回（In-Order Write-Back）的 5 階段管線中，寫回階段固定依指令順序於 WB 階段完成，因此 WAR 與 WAW 都不會造成資料不一致，亦不需要任何 Stall；RAR 則完全不構成危害。

2. 控制危害（Control Hazards / Branch Hazards）：

   • 若分支指令在 EX 階段進行條件判斷與目標位址計算（且無分支預測），則當分支指令於 EX 階段確定跳躍與否時，管線中位於其後方的 ID 與 IF 階段已預抓（Prefetch）了 2 筆指令。若確定發生分支跳躍，必須將此 2 階段的指令清除（Flush），其懲罰（Penalty）為 2 個 Pipeline Cycles。

---

解題方法

針對各選項提出的管線情境，依據 5 階段管線的時間軸與資料流路徑進行逐一邏輯分析與判斷：

1. 載入-使用時間差分析：比較 Load 指令資料產出時間點（MEM 階段結束）與 Consume 指令資料需求時間點（EX 階段開始）。
2. 前傳路徑可行性分析：檢查是否能透過 EX/MEM $\rightarrow$ EX 或 MEM/WB $\rightarrow$ EX 前傳路徑消除 Stall。
3. 控制轉折懲罰計算：分析分支指令解出結果之階段與管線中被影響的指令數量。
4. 指令暫存器讀寫屬性分析：釐清指令為 Read、Write 或兼具，並確認在順序管線中是否會引發真正的依賴性衝突。

---

選項分析

• (a) 正確。

  • 說明：Load 指令（如 lw x1, 0(x2)）的記憶體資料要在 MEM 階段結束時才能由記憶體讀出並存入 MEM/WB 管線暫存器。若緊接著的下一筆指令（如 add x3, x1, x4）需要使用 x1，該指令在同一個時脈週期正處於 EX 階段（需要 ALU 輸入）。由於 Load 的資料此時尚未讀出，無法前傳回同一個時脈週期的 EX 階段，故硬體必須強制暫停（Stall）1 個時脈週期，將 add 留在 ID 階段。待下一個週期 Load 進入 WB 階段時，再由 MEM/WB 管線暫存器前傳至 add 的 EX 階段。因此，Load-use hazard 即使在完整前傳架構下仍必須至少 Stall 1 個週期。

• (b) 錯誤。

  • 說明：R-type 指令（如 add x5, x1, x2）在 EX 階段結束時即已由 ALU 計算出結果並暫存在 EX/MEM 管線暫存器中。

核心觀念

本題考查計算機組織與結構中「32 位元二補數（2's Complement）整數表示法」與「加法溢位（Overflow）判斷機制」。
關鍵觀念與公式如下：

1. $N$ 位元二補數表示法範圍：
   對於 $N$ 位元二補數整數，最高有效位元（MSB）為符號位元（Sign Bit），權值為 $-2^{N-1}$，其餘 $N-1$ 個位元權值為正。
   可表示的數值範圍為 $[-2^{N-1}, 2^{N-1} - 1]$。
   當 $N = 32$ 時，範圍為 $[-2^{31}, 2^{31} - 1]$，即 $[-2147483648, 2147483647]$。
2. 特殊數值的十六進位表示：
   • 最小值（最負數 $-2^{31}$）：位元模式為 1000 0000 0000 0000 0000 0000 0000 0000，對應十六進位 0x80000000。
   • 最大值（最大正數 $2^{31} - 1$）：位元模式為 0111 1111 1111 1111 1111 1111 1111 1111，對應十六進位 0x7FFFFFFF。
3. 有符號溢位（Signed Overflow）檢測機制：
   • 二補數加法的有符號溢位發生在「兩個同符號數相加，結果卻呈現相反符號」時。
   • 硬體判定公式：檢測最高有效位元（MSB）的「進位輸入（Carry-in, $C_{in}$）」與「進位輸出（Carry-out, $C_{out}$）」是否不同，即：
     $\text{Overflow} = C_{in} \oplus C_{out}$
   • 若僅檢查 MSB 的進位輸出 $C_{out} = 1$，此條件僅適用於**無符號整數（Unsigned Integer）**的溢位判斷，無法正確判斷有符號整數的溢位。

---

解題方法

針對題目要求尋找「敘述錯誤（FALSE）」的選項，採以下步驟逐一驗證：

1. 比對二補數極值（最負數與最大正數）之位元編碼與十進位數值範圍公式。
2. 計算最大正數加上 $1$ 時的二元算術結果與位元變化。
3. 分析硬體判定「有符號溢位（Signed Overflow）」與「無符號進位（Unsigned Carry-out）」的邏輯條件差異。

---

選項分析

• (a) 正確（TRUE）：
  在 32 位元二補數中，最小值（最負數）發生在 MSB 為 1 且其餘位元皆為 0 時。其位元表示法為 1000...0000，轉為十六進位即為 0x80000000，對應的十進位數值為 $-2^{31} = -2147483648$。故此敘述正確。

• (b) 正確（TRUE）：
  在 32 位元二補數中，最大正數發生在 MSB 為 0 且其餘 31 個位元皆為 1 時。其位元表示法為 0111...1111，轉為十六進位即為 0x7FFFFFFF，對應的十進位數值為 $2^{31} - 1 = 2147483647$。故此敘述正確。

核心觀念

本題旨在考驗作業系統（Operating Systems, OS）中「記憶體管理機制」（Memory Management Scheme）與計算機結構（Computer Architecture）中「CPU 硬體處理器設計技術」（Pipelining）的範疇區隔。

在作業系統中，記憶體管理的主要目的為分配、管理與抽象化實體記憶體（Physical Memory）與邏輯記憶體（Logical Memory），常見的機制包含：

1. 分頁機制（Paging）：將邏輯記憶體分割為固定大小的「頁面」（Pages），實體記憶體分割為相同大小的「頁框」（Frames），藉由頁表（Page Table）進行位址轉換，用以消除外部分碎（External Fragmentation）。
2. 分段機制（Segmentation）：依據程式碼與資料的邏輯單元（如子程式、全域變數、堆疊等）進行非連續記憶體分配，符合使用者檢視記憶體的邏輯結構。
3. 虛擬記憶體（Virtual Memory）：將邏輯定址空間與實體記憶體分離的整體架構技術，允許執行大於實體記憶體容量的進程。
4. 請求分頁（Demand Paging）：虛擬記憶體最主要的實作方式，僅在程式執行期間被存取且發生頁面錯失（Page Fault）時，作業系統才將對應頁面從輔助記憶體（如硬碟/SSD）載入實體記憶體。

而**流水線技術（Pipelining）**則是計算機組織與結構層面的 CPU 指令級平行（Instruction-Level Parallelism, ILP）硬體優化技術，將指令執行過程拆解為多個獨立階段（如 IF, ID, EX, MEM, WB），使多條指令能在時間上重疊執行，用以提升 CPU 的指令吞吐量（Throughput），並不屬於作業系統的記憶體管理軟體機制。

---

解題方法

1. 問題判定：題目要求選出不屬於作業系統常見記憶體管理機制（NOT a memory management scheme）的選項。
2. 領域歸屬分析：
   • 審視選項 (a) 至 (d)：均為作業系統教科書（如 Silberschatz 之 Operating System Concepts）中記憶體管理（Memory Management）與虛擬記憶體（Virtual Memory）章節的核心機制。

核心觀念

本題考查作業系統中同步機制（Synchronization Mechanism）的核心工具——信號量（Semaphore）。關鍵理論與定義如下：

1. 信號量定義與原子性：信號量 $S$ 為一整數變數，除初始化外，僅能透過兩個不可分割的原子操作（Atomic Operations）存取：wait(S)（亦稱 $P(S)$，源自荷蘭文 Proberen，意為測試/等待）與 signal(S)（亦稱 $V(S)$，源自荷蘭文 Verhogen，意為增加/發信號）。
2. 信號量分類與功能：
   • 二元信號量（Binary Semaphore）：數值範圍僅為 $0$ 與 $1$，常用於實現互斥鎖（Mutex Lock）。
   • 計數信號量（Counting Semaphore）：數值範圍可為任意非負整數，用於管理擁有多個實例的資源池，或用於行程間的同步通知（Signaling）。
3. 阻塞佇列與解鎖機制：在非忙碌等待（Non-busy-waiting）實作中，信號量內部包含一等待佇列（Wait Queue）。當行程執行 wait() 發現資源不足時進入阻塞狀態；當其他行程執行 signal() 時，會將等待佇列中的一個行程喚醒（Unblock）並移至就緒佇列（Ready Queue）。
4. 使用風險：信號量缺乏語法結構約束，若程式設計不當（如漏呼叫 signal() 或順序顛倒），會導致死結（Deadlock）或行程飢餓（Starvation）。

---

解題方法

針對題目中關於信號量特性的五個敘述（(a) 至 (e)），對照作業系統標準理論進行逐一評判：

1. 分析 (a)：依據信號量的標準定義，核對存取介面與原子操作名稱。
2. 分析 (b)：核對信號量在互斥（Mutex）與資源計數／行程通知（Signaling）上的應用。
3. 分析 (c)：比較二元信號量與計數信號量在各類併發場景下是否具備完全相同的機能。
4. 分析 (d)：根據阻塞與喚醒（Block-Wakeup）實作模型，確認單次 signal() 所喚醒的實體數量。
5. 分析 (e)：評估信號量誤用對系統安全性（Deadlock / Starvation）造成的影響。

---

選項分析

• (a) 正確
  原因：依據戴克斯特拉（Dijkstra）提出的信號量標準定義，信號量 $S$ 為一個整數變數，且對該變數的存取嚴格限制只能透過 wait(S)（即 $P(S)$）與 signal(S)（即 $V(S)$）兩個原子操作完成。原子性確保了多個行程或執行緒同時呼叫時不會發生競態條件（Race Condition）。

• (b) 正確
  原因：信號量具備兩種主要用途：

  1. 互斥鎖（Mutex）：使用初始值為 $1$ 的二元信號量，行程進入臨界區段前呼叫 wait()，離開後呼叫 signal()，可達成臨界區段的互斥存取。
  2. 計數與通知（Counting / Signaling）：使用計數信號量管理 $N$ 個可用資源實例；

核心觀念

本題考查作業系統中檔案系統的三大主要磁碟區塊配置方法（Disk Block Allocation Methods）之特性與運作機制：

1. 連續分配（Contiguous Allocation）

   • 每個檔案在磁碟上必須佔據一組連續的區塊（Blocks）。
   • 特性：存取效能極佳，支援高效的隨機存取（Random Access），直接透過公式算出區塊位址：$\text{Address} = \text{Start} + \text{Offset}$。
   • 缺點：產生嚴重的外部碎裂（External Fragmentation）；檔案在執行時期動態擴充極為困難（若緊鄰的後續區塊已被佔用，則必須搬移整個檔案至更大的連續空間）。

2. 連結分配（Linked Allocation）

   • 檔案資料以鏈結串列（Linked List）形式分散儲存於任意空閒區塊中，每個區塊包含指向下一個區塊的指標。
   • 特性：完全消除外部碎裂，檔案擴充非常容易。
   • 缺點：不支援常數時間的隨機存取，存取第 $N$ 個區塊需從頭走訪串列，時間複雜度為 $O(N)$。
   • FAT（File Allocation Table）：屬於連結分配的變體，將原先分散於各區塊的指標集中抽取至記憶體中的表格（FAT Table）維護，資料區塊在磁碟上仍為非連續分佈。

3. 索引分配（Indexed Allocation）

   • 每個檔案維護一個（或多個）索引區塊（Index Block），集中記錄該檔案所有資料區塊的指標陣列。
   • 特性：兼具無外部碎裂與支援常數時間 $O(1)$ 隨機存取的優點。
   • 大檔案處理：若單一索引區塊容量不足以儲存大檔案的所有指標，可擴充為連結索引（Linked Scheme）、多層索引（Multi-level Indexing，如兩層索引）或混合索引（如 UNIX Inode 的直接與間接指標）。

---

解題方法

針對選擇題，逐項對照三大分配方法在「存取速度與時間複雜度」、「外部碎裂」、「動態擴充性」及「實作架構」上的基本定義：

1. 檢視連續分配是否允許任意位置擴充與是否產生外部碎裂。
2. 檢視連結分配的時間複雜度與隨機存取能力。
3. 檢視索引分配對隨機存取的支援度及大檔案多層索引結構。
4. 檢視 FAT 檔案系統的架構本質（為 Linked 分配變體而非 Contiguous）。

---

選項分析

• (a) 錯誤
  連續分配要求檔案的區塊必須在磁碟上連續相鄰。

核心觀念

本題考查作業系統中兩大主記憶體管理機制：**分頁（Paging）與分段（Segmentation）**的基本概念、邏輯位址結構、記憶體分割方式、碎片問題（Fragmentation）以及位址轉譯（Address Translation）機制的差異。

1. 分頁（Paging）：

   • 記憶體切割方式：將邏輯記憶體分割成**固定大小（Fixed-sized）**的「頁（Pages）」，將實體記憶體分割成相同大小的「頁框（Frames）」。
   • 邏輯位址結構：邏輯位址分為兩部分：頁碼 $p$（Page Number） 與 頁內偏移量 $d$（Page Offset）。即：
     $\text{Logical Address} = (p, d)$
   • 碎片現象：無外部碎片（External Fragmentation），但最後一頁可能無法填滿，會產生內部碎片（Internal Fragmentation）。

2. 分段（Segmentation）：

   • 記憶體切割方式：依據程式的邏輯結構（如主程式、函式、堆疊、陣列等），將記憶體分割成**可變大小（Variable-sized）**的「段（Segments）」。
   • 邏輯位址結構：邏輯位址分為兩部分：段碼 $s$（Segment Number） 與 段內偏移量 $d$（Segment Offset）。即：
     $\text{Logical Address} = (s, d)$
   • 碎片現象：由於各段長度不一且動態載入／釋放，無內部碎片，但會產生外部碎片（External Fragmentation）。

---

解題方法

解題關鍵在於掌握「分頁（Paging）與分段（Segmentation）對照表」，從切割單位、碎片類型與邏輯位址表示法三個維度精確比對選項敘述：

1. 切割單位：Paging 為固定大小（Fixed-size），Segmentation 為可變大小（Variable-size）。
2. 碎片現象：Paging 只有內部碎片，Segmentation 只有外部碎片。
3. 位址轉譯：
   • Paging 位址由 $(p, d)$ 組成，透過頁表（Page Table）查出對應頁框號 $f$（Frame Number），組合成實體位址 $(f, d)$。
   • Segmentation 位址由 $(s, d)$ 組成，透過段表（Segment Table）查出基底位址（Base）與界限長度（Limit），並檢查 $d < \text{Limit}$ 後算出實體位址 $\text{Base} + d$。

---

選項分析

• (a) 錯誤
  • 原因：敘述完全顛倒。分頁（Paging）是將記憶體分割為**固定大小（Fixed-sized）**的區塊（Pages / Frames）；

關鍵概念

• 5 階段流水線：IF → ID → EX → MEM → WB
• 允許的轉發路徑：MEM → EX、WB → EX（僅限於 EX 階段使用）
• 讀取暫存器的階段：ID（一般指令的來源暫存器）
• Load‑use（lw 後立刻使用載入值）仍需 1 個氣泡，因為資料在 MEM 結束才取得，EX 需要在同一週期開始時就取得運算元，無法靠 MEM→EX 轉發即時供給。

---

各組指令對照流水線時序

指令對	需求的資料來源	取得資料的階段	需要的轉發路徑	是否必須插入氣泡
(a) lw x5,0(x6) → add x7,x5,x8	add 需要 x5（lw 的載入值）	lw 在 MEM 完成讀取<br>add 於 EX 需要運算元	需要 MEM→EX；但 lw 的資料在 MEM 結束 才可得，add 的 EX 與 lw 的 MEM 同時發生，無法即時取得	是（至少 1 個氣泡）

AMAT（Average Memory Access Time）計算如下：

1. L1 快取命中率

$\text{L1 hit}=0.95 \quad\Rightarrow\quad \text{L1 miss}=1-0.95=0.05$

2. L2 快取在 L1 未命中時的命中率

$\text{L2 hit}=0.90 \quad\Rightarrow\quad \text{L2 miss}=1-0.90=0.10$

3. 每次未命中 L1 的平均懲罰時間

核心觀念

本題考查作業系統中 CPU 排程（CPU Scheduling） 的四大基本演算法及其平均等待時間（Average Waiting Time, $AWT$）之計算。

1. 排程演算法分類與機制

• FCFS（First-Come, First-Served）：非搶占式（Non-preemptive）。依行程到達 Ready Queue 的時間先後順序進行排程。
• Non-preemptive SJF（Shortest Job First）：非搶占式。當 CPU 空閒時，從 Ready Queue 中選擇 CPU Burst Time 最短的行程優先執行；一旦行程開始執行，即不允許被搶占直至完成。
• Round Robin（RR, $q = 2\text{ ms}$）：搶占式（Preemptive）。採用時間分割（Time-sharing）機制，將 CPU 時間劃分為固定長度的時間量子（Time Quantum $q$）。行程按 FIFO 佇列輪流執行，若在量子結束前尚未執行完畢，則會被搶占並放回 Ready Queue 尾端。
• SRTF（Shortest Remaining Time First）：搶占式 SJF。在任何時間點（特別是有新行程到達時），若新到達行程的「剩餘 CPU Burst Time」小於當前正在執行的行程，當前行程會立即被搶占。

2. 重要計算公式

對於每個行程 $P_i$：

• 完成時間（Completion Time, $C_i$）：行程執行完畢離開 CPU 的時間點。
• 轉返時間（Turnaround Time, $TAT_i$）：行程從到達至完成所需的總時間。
  $TAT_i = C_i - A_i$
• 等待時間（Waiting Time, $W_i$）：行程在 Ready Queue 中等待 CPU 的累積時間。
  $W_i = TAT_i - B_i = C_i - A_i - B_i$
• 平均等待時間（Average Waiting Time, $AWT$）：
  $AWT = \frac{\sum_{i=1}^{n} W_i}{n}$
  其中 $n$ 為行程總數（本題 $n = 4$），$A_i$ 為到達時間（Arrival Time），$B_i$ 為 CPU 執行時間（Burst Time）。

---

解題方法

解題關鍵步驟為：

1. 構建甘特圖（Gantt Chart）：依據各排程演算法的規則與行程到達時間，精確推算各時間區段的 CPU 占用行程。
2. 統計完成時間 $C_i$：由甘特圖找出每個行程最終完成的時間點。
3. 計算等待時間 $W_i$：帶入 $W_i = C_i - A_i - B_i$，求出每個行程的等待時間。
4. 求解平均值 $AWT$：將 4 個行程的等待時間相加後除以 4。

基本資料整理如下表：

行程	到達時間 $A_i$	Burst Time $B_i$
$P_1$	0	5
$P_2$	1	3
$P_3$	2	6
$P_4$	4	2

---

填空項分析與推導

1. FCFS (First-Come, First-Served)

行程依到達時間 $A_i$ 順序依次執行（$P_1 \to P_2 \to P_3 \to P_4$）。

• 甘特圖推導：

  • $t=0 \sim 5$：$P_1$ 執行（完成時間 $C_1 = 5$）
  • $t=5 \sim 8$：$P_2$ 執行（完成時間 $C_2 = 8$）
  • $t=8 \sim 14$：$P_3$ 執行（完成時間 $C_3 = 14$）
  • $t=14 \sim 16$：$P_4$ 執行（完成時間 $C_4 = 16$）

• 行程等待時間：

  • $W_1 = C_1 - A_1 - B_1 = 5 - 0 - 5 = 0\text{ ms}$
  • $W_2 = C_2 - A_2 - B_2 = 8 - 1 - 3 = 4\text{ ms}$
  • $W_3 = C_3 - A_3 - B_3 = 14 - 2 - 6 = 6\text{ ms}$
  • $W_4 = C_4 - A_4 - B_4 = 16 - 4 - 2 = 10\text{ ms}$

• 平均等待時間：
  $AWT_{\text{FCFS}} = \frac{0 + 4 + 6 + 10}{4} = \frac{20}{4} = 5\text{ ms}$

---

2. Non-preemptive SJF (Shortest Job First)

當 CPU 空閒時，選擇 Ready Queue 中 Burst Time 最短的行程。

• 甘特圖推導：

  • $t=0$：僅 $P_1$ 到達，故 $P_1$ 開始執行至 $t=5$ 完成（$C_1 = 5$）。
  • $t=5$：Ready Queue 包含 $\{P_2(3), P_3(6), P_4(2)\}$。最短者為 $P_4(2)$，故 $P_4$ 執行至 $t=7$ 完成（$C_4 = 7$）。
  • $t=7$：Ready Queue 包含 $\{P_2(3), P_3(6)\}$。最短者為 $P_2(3)$，故 $P_2$ 執行至 $t=10$ 完成（$C_2 = 10$）。
  • $t=10$：Ready Queue 僅剩 $P_3(6)$，故 $P_3$ 執行至 $t=16$ 完成（$C_3 = 16$）。

• 行程等待時間：

  • $W_1 = 5 - 0 - 5 = 0\text{ ms}$
  • $W_2 = 10 - 1 - 3 = 6\text{ ms}$
  • $W_3 = 16 - 2 - 6 = 8\text{ ms}$
  • $W_4 = 7 - 4 - 2 = 1\text{ ms}$

• 平均等待時間：
  $AWT_{\text{SJF}} = \frac{0 + 6 + 8 + 1}{4} = \frac{15}{4} = 3.75\text{ ms}$

---

3. Round Robin (time quantum = 2 ms)

採用經典作業系統教科書（Silberschatz）之 Ready Queue 規範：**當行程時間量子用完與新行程到達時間重疊時，新到達的行程優先排入 Ready Queue