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

核心觀念

現代作業系統會限制每個行程可存取的合法位址範圍。處理器透過記憶體管理單元（MMU）及保護機制檢查記憶體存取；當行程存取超出權限或合法範圍的位址時，硬體會立即產生同步例外，交由作業系統核心處理。此例外常稱為保護錯誤（protection fault），也屬於陷阱（trap）。

解題方法

題目問的是「立即結果」，因此要判斷處理器偵測到非法位址時最先發生什麼事。硬體的位址保護檢查會先觸發例外，作業系統再依錯誤類型處理，例如終止行程或回報記憶體存取錯誤。

選項分析

• (A) Blue Screen of Death：錯誤。 藍畫面是特定系統發生嚴重核心錯誤時可能出現的結果，不是行程產生非法位址的立即且通用結果。
• **(B) A hardware interrupt (trap) will occur：正確。

核心觀念

本題考查硬體中斷的控制流程。裝置控制器提出中斷後，處理器在適當的指令邊界接受中斷，保存目前執行狀態，再依中斷向量轉入對應的中斷處理常式（interrupt handler）。

中斷向量可視為「中斷種類到處理常式入口位址」的對應表。由硬體啟動這項轉移，作業系統的中斷處理程式接手後，再處理中斷原因與後續工作。

解題方法

判斷時先分清楚中斷的偵測與控制轉移由誰負責：不是作業系統逐條指令輪詢，也不是正在執行的應用程式主動呼叫作業系統；控制器提出中斷後，硬體依中斷向量將處理器導向對應的處理常式。因此正確選項為 (C)。

選項分析

• (A) 錯誤。 作業系統不會在每條指令之間逐一檢查是否有中斷。處理器硬體會在指令邊界等可接受中斷的時機檢查中斷訊號。
• **(B) 錯誤。

核心觀念

本題考作業系統核心的架構分類。判斷重點是：核心服務與裝置驅動程式主要在哪裡執行，以及核心是否支援動態載入模組。

Linux 採用單體式核心（monolithic kernel）：程序管理、記憶體管理、檔案系統、網路堆疊與裝置驅動程式等核心服務，主要都在核心空間執行。Linux 也支援可動態載入的核心模組（loadable kernel modules），可在系統運作時載入或卸載部分功能。

解題方法

先辨認 Linux 的核心服務與驅動程式主要在核心空間執行，因此屬於單體式核心；再確認 Linux 支援動態載入核心模組。兩項特徵合併後，對應到「具備可動態載入驅動程式的單體式核心」。

選項分析

• (A) Microkernel（微核心）：錯誤。微核心會將核心維持精簡，許多服務與驅動程式移至使用者空間執行；這不是 Linux 的典型架構。
• (B) Microkernel with Dynamically Loadable Drivers（具可動態載入驅動程式的微核心）：錯誤。

核心觀念

本題考查多執行緒如何利用多處理器系統的平行能力。執行緒是程序中的執行單位，共用同一程序的程式碼與資料，但各自保有執行狀態，例如程式計數器與暫存器。

在單處理器系統中，多個執行緒由 CPU 快速交替執行，形成併行的效果；在對稱式多處理器系統（SMP）中，多個執行緒可分派到不同處理器核心，同時執行，形成真正的平行。因此，程式以多執行緒組織工作，便能在 SMP 系統上利用多個處理器。

解題方法

判斷關鍵在於題目問的是哪種技術能讓程式設計者利用多處理器的平行執行能力。多執行緒可把工作拆成多個執行流程；單處理器能交錯執行這些流程，SMP 則能讓它們同時執行。因此選擇 Multithreading。

選項分析

• (A) Memory mapped files（記憶體映射檔案）：將檔案內容映射到程序的位址空間，方便以記憶體操作存取檔案；它不是用來建立多個執行流程的平行化技術。

核心觀念

FCFS（First-Come, First-Served，先到先服務）依照行程抵達就緒佇列的先後順序安排 CPU。它採用非搶先式排程：行程一旦取得 CPU，通常會執行到完成或主動讓出 CPU，後到的行程必須等待。

FCFS 的主要缺點是護航效應（convoy effect）：若長行程排在短行程之前，短行程即使只需少量 CPU 時間，也得等長行程執行完畢，導致平均等待時間與周轉時間增加。

解題方法

判斷「最大的問題」時，先檢視 FCFS 的排程規則，再看它可能造成的結果。FCFS 的規則簡單，且按抵達順序服務；但它不考慮行程所需的 CPU 時間，因此長行程可能讓後面的短行程長時間等待。這正是護航效應，也是本題要辨認的主要缺點。

選項分析

核心觀念

SRTF（Shortest Remaining Time First，最短剩餘時間優先）是搶先式的 SJF（Shortest Job First）排程。每當新行程抵達，或目前行程的 CPU burst 結束，作業系統會比較各行程的預估剩餘 CPU burst 時間，讓剩餘時間最短的行程先執行；若新抵達行程的剩餘時間更短，便會搶先目前正在執行的行程。

此演算法有兩項主要限制：

1. CPU burst 長度無法事先精確得知，實務上只能根據過去的 burst 長度估算。
2. 可能造成飢餓：若短行程持續抵達，長行程會不斷被延後，等待時間可能非常長。

解題方法

判斷各選項是否描述 SRTF 的限制。由於 SRTF 的選擇依賴行程剩餘 CPU burst 時間，而實際的下一段 burst 長度事前未知，因此需要估算；此外，短行程持續插隊時，長行程可能長期得不到 CPU。

選項分析

• (A) We don’t know the next CPU burst length.
  正確。

核心觀念

多層回饋佇列（Multilevel Feedback Queue, MLFQ）把就緒行程分成多個優先權不同的佇列：新行程進入最高層，用完時間片仍未結束就降到下一層；長時間等待的行程可以升級（aging）避免飢餓。佇列之間的排程方式，教科書（Silberschatz）描述的 MLFQ 採固定優先權：

排程器先執行最上層佇列中的所有行程；只有上層佇列是空的，才會執行下一層的行程；而且上層有新行程到達時，會搶先下層正在執行的行程。

選項分析

• (A) 錯誤。 「每層分得預先設定的 CPU 時間比例」是**多層佇列（multilevel queue）**的另一種可能作法（佇列之間時間切片，例如前景 80%、背景 20%），不是 MLFQ 的佇列間

核心觀念

單層分頁表的大小與「虛擬位址空間」成正比，而不是與實際使用量成正比。以 32 位元位址、4 KB 頁、每項 4 bytes 計算，每個行程需要 $2^{20}\times4=4$ MB 的頁表，而且必須是一整塊連續的實體記憶體。

解題方法

多層分頁表把頁表本身也切成頁（頁表的頁表）：

1. 外層頁表只記錄內層頁表放在哪些實體頁框，內層頁表可以分散放在任意頁框，不再需要大塊連續記憶體——解決了巨大頁表難以配置、造成外部碎裂的問題。
2. 虛擬位址空間中沒用到的區段，對應的內層頁表根本不必配置，大幅節省記憶體。

核心觀念

一次磁碟存取（數毫秒）相當於數百萬個 CPU 週期。需要空閒頁框時，若挑錯了犧牲頁（把馬上又要用的頁換出去），之後就得再從磁碟讀回來。所以在選擇犧牲頁這件事上多花 CPU 運算、做出更好的判斷，是值得的——這正是頁面置換演算法盡量逼近最佳置換（OPT，換掉「最久之後才會再被使用」的頁）的原因。

選項分析

• (A) 錯誤。 把處於等待狀態的行程整個換出去，本身就是大量的磁碟寫入，與「花 CPU 時間避免磁碟存取」相反。
• (B) 錯誤。 對記憶體空洞做垃圾收集／緊縮（compaction）處理的是連續配置的外部碎裂；分頁系統沒有外部碎裂，這樣做無助於避免換頁的磁碟存取。
• **(C) 錯誤。

核心觀念

Buddy system（夥伴系統）是一種動態記憶體配置方法，用來管理可用的連續記憶體區塊。系統通常將記憶體分成大小為 $2^k$ 的區塊，並以相同大小的空閒區塊清單分別管理。

解題方法

辨認 buddy system 的關鍵，是看它如何管理空閒記憶體：

• 申請時先把大小向上取到 2 的次方；若該大小的空閒串列是空的，就從更大的空閒區塊對半切分（切出的兩塊互為 buddy），直到得到剛好的大小。
• 釋放區塊時，若其同大小的夥伴區塊也空閒，兩者會合併成較大的區塊。

因此，這套方法的特色是：依區塊大小分類記錄空閒記憶體，並透過分割與合併管理區塊。

選項分析

核心觀念

身分驗證常見的三種因素為：

• 你知道的事（something you know）：例如密碼、PIN 碼。
• 你持有的物品（something you have）：例如智慧卡、手機上的驗證器。
• 你本身的特徵（something you are）：例如指紋、虹膜或臉部特徵。

題目要找的是「不屬於上述身分驗證因素」的選項。

解題方法

逐一比對選項與三種常見驗證因素。「你看到的事物」不是標準的身分驗證因素，因此選 (B)。

選項分析

• (A) Something you have：錯誤選項。 持有的物品可以用來驗證身分，例如安全金鑰或已註冊的手機。
• **(B) Something you see：正確答案。

核心觀念

「沙箱模型」（sandbox model）是一種安全隔離機制：將不可信任的程式放在受限制、受監控的環境中執行，限制它能存取的資源與執行的操作，降低程式出錯或惡意行為對主機系統造成的影響。

虛擬機器（virtual machine）是實作沙箱的一種方式，但沙箱不限定必須使用虛擬機器；作業系統層級的容器、受限的執行環境等也可以達成隔離目的。

解題方法

抓住「沙箱」的核心定義：重點在於建立一個受控制的執行環境，而不是另外準備一台電腦、一顆處理器或一個網路。選項 (E) 以「受控制的環境」描述沙箱，並以虛擬機器作為例子，因此符合定義。

選項分析

核心觀念

檔案系統通常以固定大小的區塊配置磁碟空間。若一個檔案最後需要的空間不到一個完整區塊，系統仍須配置整個區塊；已配置區塊中未被檔案使用的部分，就是內部碎裂（internal fragmentation）。

若配置單位大小為 $B$，檔案大小為 $S$，則配置空間為 $\lceil S/B\rceil B$，內部碎裂量為：

解題方法

辨認碎裂發生的位置：內部碎裂是已配置的空間內部有未使用部分，通常來自配置單位無法精確配合需求。若可用空間散落成許多零碎區段，則屬於外部碎裂。

選項分析

核心觀念

本題考磁碟排程的效能指標與公平性取捨。磁碟讀寫頭移動到指定磁軌所花的時間稱為尋道時間；排程器安排服務順序，會影響總尋道時間，也會影響各請求等待時間是否公平。

LOOK 排程讓讀寫頭沿目前方向服務請求，直到該方向最遠的待處理請求，再反向移動。這樣可避免像 SCAN 一樣走到磁碟邊界才折返，因此通常能降低讀寫頭移動距離。

解題方法

題幹已指出 LOOK 的尋道延遲最低，其他演算法卻有較長的尋道時間。關鍵在於辨認：若演算法的目標是速度或減少尋道時間，就不會刻意接受更長的尋道時間；排程器也可能為了讓不同位置的請求獲得較公平的服務，而犧牲部分尋道效率。

因此，這些演算法的設計目的在於提升排程公平性，例如避免某些請求長時間等待，或使等待時間較可預期。

選項分析

• (A) We wanted the scheduler to be fairer. 正確。
  排程策略可在尋道效率與公平性間取捨。接受較長的尋道時間，換取請求較公平地獲得服務，符合題意。

• (B) We wanted the scheduler to be faster. 錯誤。
  題幹已說其他演算法的尋道時間較長，這與「更快」的目標相反。

核心觀念

本題考查網路分層中的應用層協定。應用層協定定義網路應用程式如何交換資料，常見服務包括瀏覽網頁、傳送檔案及收發電子郵件。HTTP、FTP、SMTP 與 POP3 都是網際網路中使用的應用層協定。

解題方法

逐一辨認各協定的用途與所屬層級：

• HTTP 用於網頁與 Web 服務的資料交換。
• FTP 用於檔案傳輸。
• SMTP 用於傳送電子郵件。
• POP3 用於從郵件伺服器接收電子郵件。

四者都屬於應用層協定，因此選擇涵蓋全部敘述的選項。

選項分析

核心觀念

fork() 會複製呼叫它的行程，建立一個新行程；fork() 成功後，父行程與子行程都會從呼叫後的位置繼續執行。thread_create(...) 建立的是執行緒，不會建立新行程。

解題方法

依程式執行順序追蹤行程數：

1. 起初有原始行程 $P_0$。第一次 fork() 建立子行程 $P_1$，此時共有 $2$ 個行程。
2. if (pid == 0) 只有第一次 fork() 建立的子行程 $P_1$ 會進入區塊。區塊內的 fork() 再建立 $P_2$，此時共有 $3$ 個行程。
3. $P_1$ 與 $P_2$ 都會執行 thread_create(...)，但這只建立執行緒，不增加行程數。

題目程式

pid_t pid;
pid = fork();
if (pid == 0) {      /* 子行程 */
    fork();
    thread_create(...);
}
fork();

（本題是 Silberschatz《Operating System Concepts》第 4 章習題：(a) 建立了幾個不同的行程？(b) 建立了幾個不同的執行緒？）

核心觀念

• fork() 複製出一個新行程，父子都從 fork() 之後繼續執行；fork() 在子行程回傳 0。
• 在多執行緒程式中呼叫 fork()（POSIX 語意）只複製呼叫它的那條執行緒。
• 題目問「created」的執行緒，指的是由 thread_create() 新建立的執行緒；每個行程本來就有的主執行緒是隨行程而來，不是另外建立的執行緒。

解題方法

令原始行程為 P0。

核心觀念

有效存取時間（EAT）是每次記憶體參考的平均耗時。若頁面錯誤率為 $p$，沒有頁面錯誤時需一次記憶體存取；發生頁面錯誤時，需先完成錯誤處理，再重新執行原本的記憶體存取。

題目指出頁表存放於暫存器，因此不需額外計入存取記憶體頁表的時間。頁面錯誤處理時間則依被替換頁是否修改而不同。

解題方法

被替換頁有 $70\%$ 的機率已修改，處理時間為 $20\ \text{ms}$；有 $30\%$ 的機率可直接處理，時間為 $8\ \text{ms}$。因此，平均頁面錯誤處理時間為

換算成奈秒：

無錯誤時，存取時間為 $100\ \text{ns}$；錯誤處理完成後，還要重新執行該次存取。故有效存取時間為

核心觀念

這題考查直接對映快取的位址對映，以及三種快取失誤分類：

• 強制失誤（compulsory miss）：該記憶體區塊第一次被存取，快取中尚未載入過。
• 衝突失誤（conflict miss）：該區塊先前存取過，但因直接對映時與其他區塊競爭同一快取區塊而被替換。
• 容量失誤（capacity miss）：即使改用相同總容量的全相聯快取，採用 LRU 替換仍無法留住該區塊。
• 命中（hit）：所需記憶體區塊已在對應快取區塊中。

若快取有 $10$ 個區塊，記憶體區塊編號為 $B$，則直接對映的快取索引為：

同一索引可由不同記憶體區塊映射而來；必須比對標籤，才能判斷是否命中。

解題方法

逐一處理位址，先換算它所屬的記憶體區塊，再計算快取索引，並依照存取順序追蹤快取內容。第一次讀取某區塊時，分類為強制失誤；再次讀取時，若仍在快取則為命中，若已被映射到同一索引的其他區塊取代則為衝突失誤。

(a) 每個快取區塊含 $1$ 個字

記憶體區塊編號就是字位址本身。題目給的 $10$ 個位址彼此不同，因此每個位址都是第一次存取該區塊，全部屬於強制失誤。

即使部分區塊映射到相同索引，也不影響本小題的分類：這些區塊都只出現一次，沒有再次存取可判為衝突或容量失誤。

(b) 每個快取區塊含 $10$ 個字

每個記憶體區塊包含連續 $10$ 個字，因此字位址 $A$ 所屬的記憶體區塊編號為：

核心觀念

處理器執行時間為

流水線把一條指令的工作拆成多個階段，讓不同指令能同時處於不同階段。理想情況下，流水線填滿後每個時脈週期完成一條指令，因此理想 $\,\text{CPI}=1$；效能提升主要來自縮短時脈週期時間。指令數 IC 不因流水線本身改變。

解題方法

比較流水線與非流水線處理器時，分別檢查 CPI 與時脈週期時間。理想 $N$ 階流水線可把原本較長的工作分段，在各階段延遲均等且沒有額外成本時，時脈週期時間約縮短為原來的 $1/N$，所以理想速度提升 $N$ 倍。實際速度提升則會受到停滯週期與硬體時序限制。

(a) 流水線對 CPI 與時脈週期時間的影響

• **CPI：**理想流水線填滿後，每個週期完成一條指令，故 CPI 約為 $1$。實際上，資料相依、分支或硬體資源衝突可能讓流水線停滯，使 CPI 高於 $1$。若比較對象是多週期、每條指令需走完 $N$ 個階段的非流水線處理器，流水線可把 CPI 從約 $N$ 降至約 $1$；若比較對象是單週期處理器，兩者 CPI 都可能是 $1$。
• **時脈週期時間：**非流水線設計必須在一個週期內完成整條指令的工作；流水線將工作分段後，每個週期只需容納最慢階段的工作，因此週期時間理想上約縮短為原來的 $1/N$。

(b) 阻止 CPI 隨 $N=\infty$ 而達到理想值的因素

核心觀念

五階段 MIPS 管線依序為 IF、ID、EXE、MEM、WB。沒有 forwarding 時，讀取暫存器的指令必須等到前一條寫入該暫存器的指令進入 WB，才能在 ID 正確讀到新值。以下採用常見假設：暫存器檔在 WB 前半週期寫入、ID 後半週期讀取，因此同一週期的 WB 與 ID 可以安全銜接。

分支在 EXE 階段才確定是否跳轉，所以需要處理分支控制危險。由於題目指定沒有分支預測，分支後的兩個管線位置以 NOP 填補。

(a) 管線危險

1. 資料危險：lw 到 sw 的 RAW

   lw 寫入 $t0，緊接的 sw 要讀取 $t0 作為儲存資料。沒有 forwarding 時，sw 的 ID 必須等到 lw 的 WB，因此需要在兩者之間插入 2 個 NOP。

2. 資料危險：addi 到 bne 的 RAW

   addi 更新 $s0，接著的 bne 讀取 $s0 判斷是否跳轉。沒有 forwarding 時，bne 的 ID 必須等到 addi 的 WB，因此需要在兩者之間插入 2 個 NOP。

3. 迴圈跨迭代的資料危險：addi 到下一輪的 lw、sw

   addi 更新 $s0 後，下一輪的 lw 與 sw 都會用 $s0 計算記憶體位址。下一輪必須讀到更新後的 `