108 年 國立中山大學資訊工程學系碩士班甲組《作業系統》

(1) 行程的五種狀態 (Five Process States)

行程在生命週期中會在以下五種狀態之間轉換：

1. New (新建)：行程正在被建立中。
2. Ready (就緒)：行程已配備所需資源並進入記憶體，等待 CPU 派發 (Dispatch) 執行。
3. Running (執行)：行程的指令正在 CPU 上執行。
4. Waiting / Blocked (等待)：行程因等待某事件發生（如 I/O 完成或接收訊號）而暫停執行。
5. Terminated (終止)：行程已結束執行，等待系統回收資源。

---

(2) 兩種常見的行程間通訊模型 (IPC Models)

1. Shared Memory (共享記憶體模型)：

   • 機制：通訊行程間建立一塊共同可存取的記憶體區域，資料交換直接讀寫該區域。
   • 特性：建置完成後不需作業系統核心介入，傳輸速度最快；但須由使用者行程自行處理同步與互斥問題（如使用 Semaphore）。

2. Message Passing (訊息傳遞模型)：

   • 機制：行程間透過作業系統 Kernel 提供的原語（如 send() 與 receive()）傳遞封包或訊息。
   • 特性：不需共享記憶體，適合分散式系統或多機通訊；但每次訊息傳輸皆需切換至 Kernel 模式，系統開銷較大。

---

(3) 排程演算法之周轉時間 (Turnaround Time, TAT) 計算

周轉時間定義為 $TAT = \text{Completion Time} - \text{Arrival Time}$。因所有行程皆於 $t = 0$ 到達，故 $TAT = \text{Completion Time}$。

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

• 執行順序：$P_1(10) \rightarrow P_2(1) \rightarrow P_3(2) \rightarrow P_4(1) \rightarrow P_5(5)$
• 完成時間：$P_1 = 10,\ P_2 = 11,\ P_3 = 13,\ P_4 = 14,\ P_5 = 19$

2. Round Robin (RR, Quantum = 1)

• Ready Queue 變化：
  • $t=0\sim5$ 依次執行 $P_1, P_2, P_3, P_4, P_5$：$P_2, P_4$ 完工（完成時間 $P_2 = 2, P_4 = 4$）。
  • 剩餘行程隊列循環執行，至 $t=7$ 時 $P_3$ 完工（完成時間 $P_3 = 7$）。
  • 剩餘 $P_1, P_5$ 交替執行，至 $t=14$ 時 $P_5$ 完工（完成時間 $P_5 = 14$）。
  • 最後由 $P_1$ 執行完畢（完成時間 $P_1 = 19$）。

核心觀念

本題涵蓋四個記憶體管理重點：

• base register 與 limit register：負責位址重定位與記憶體保護。
• page fault：當所需頁面不在主記憶體時，由作業系統處理例外。
• 有效存取時間（Effective Access Time, EAT）：依 page-fault rate 加權平均。
• TLB：利用快取的頁表項目，降低位址轉換所需時間。

解題方法與詳解

（1）Base register 與 limit register 的用途

設 CPU 產生的邏輯位址為 $d$。

• base register：儲存該程序在主記憶體中的起始實體位址。
• limit register：儲存該程序可使用的位址空間大小。

硬體先檢查：

$$0 \leq d < \text{limit}$$

若合法，實體位址為：

$$\text{physical address}=\text{base}+d$$

因此兩者用途如下：

1. 位址重定位：程序可載入主記憶體的不同位置，只要修改 base register。
2. 記憶體保護：透過 limit register 限制程序只能存取自己的位址範圍，避免存取作業系統或其他程序的記憶體。

常見陷阱是把 limit register 誤認為「最後一個合法位址」；它代表的是位址空間大小，合法條件為嚴格小於 limit。

---

（2）處理 Page Fault 的六個步驟

1. 產生 page-fault trap
   CPU 存取某頁時，發現頁表項目的 valid bit 為 $0$，表示該頁目前不在主記憶體，硬體產生 page-fault trap，並保存被中斷程序的執行狀態。

2. 檢查位址是否合法
   作業系統檢查此次記憶體參考是否屬於該程序合法的位址空間。若為非法存取，便終止程序或產生記憶體保護例外。

3. 找出頁面所在位置
   若位址合法，作業系統依頁表或程序的管理資訊，找出該頁在 backing store（通常為磁碟或交換區）中的位置。

4. 取得可用的 page frame
   從 free-frame list 取得空閒 frame。若沒有空閒 frame，便執行 page replacement，選出 victim page；若 victim page 被修改過，須先寫回磁碟。

5. 將所需頁面載入主記憶體
   排程磁碟 I/O，將所需頁面讀入選定的 page frame。讀取期間，發生 page fault 的程序會被阻塞，CPU 可執行其他可執行程序。

6. 更新頁表並重新執行指令
   磁碟讀取完成後，更新頁表中的 frame number，將 valid bit 設為 $1$，並更新相關管理資訊。接著恢復程序狀態，重新執行造成 page fault 的那一條指令。

重新執行原指令是必要的，因為該指令尚未完成原本的記憶體存取。

---

（3）求可接受的 Page-Fault Rate

第 3 題：Storage and I/O Management

核心觀念

本題涵蓋四個重點：

1. VFS 如何統一不同檔案系統的操作介面。
2. SSTF 與 C-LOOK 磁碟排程的選擇規則。
3. 磁碟存取時間的三個組成部分。
4. 裝置暫存器在 CPU 位址空間中的配置方式。

---

（1）VFS 的兩項功能

核心觀念

VFS 位於系統呼叫介面與實際檔案系統實作之間，將檔案操作的共同部分抽象化。

解題方法與答案

VFS 主要提供以下兩項功能：

1. 分離一般檔案操作與實際實作

   VFS 定義統一且乾淨的介面，使 open、read、write、close 等一般檔案操作不必知道底層是 ext4、FAT、NFS 或其他檔案系統。

   因此，上層程式透過相同介面操作不同檔案系統，底層再由對應的檔案系統實作完成實際工作。

2. 提供檔案的一致且唯一表示

   VFS 提供一套統一的檔案表示方式，使本機檔案系統與遠端檔案系統中的檔案，都能在整個系統或網路中被一致識別與操作。

   這使多種檔案系統可以同時掛載、共存，並由核心以相同方式管理。

解題技巧

VFS 的兩個關鍵詞是：

• 統一介面：隔離一般操作與底層實作。
• 一致表示：讓不同檔案系統，尤其遠端檔案系統，也能被統一識別。

---

（2）SSTF 與 C-LOOK 磁碟排程

待處理請求為：

$$103,\ 188,\ 42,\ 120,\ 7,\ 138,\ 76,\ 87$$

目前磁頭位於柱號 $65$。

先排序：

$$7,\ 42,\ 76,\ 87,\ 103,\ 120,\ 138,\ 188$$

---

A. SSTF

核心觀念

SSTF（Shortest Seek Time First）每一步都選擇距離目前磁頭位置最近的待處理請求。

解題方法與計算

目前位置	最近的待處理請求	移動距離
$65$	$76$	$
$76$	$87$	$
$87$	$103$	$
$103$	$120$	$
$120$	$138$	$
$138$	$188$	$
$188$	$42$	$
$42$	$7$	$

因此，SSTF 的服務順序為：

$$65\rightarrow76\rightarrow87\rightarrow103\rightarrow120\rightarrow138\rightarrow188\rightarrow42\rightarrow7$$

總磁頭移動量為：

$$11+11+16+17+18+50+146+35=304$$

所以：

$$\boxed{\text{SSTF 總移動量}=304\text{ cylinders}}$$

解題技巧

SSTF 必須在每一步重新計算距離，不能只依照一開始排序後的順序服務。磁頭移動到 $188$ 後，剩餘請求為 $42$ 與 $7$，其中 $42$ 距離較近，因此先服務 $42$。

---

B. C-LOOK

核心觀念

C-LOOK 只沿一個方向服務請求，抵達該方向最後一個請求後，直接跳回另一端尚未服務請求的最外側位置，再繼續同方向服務。

C-LOOK 不會特別移動到磁碟實際端點，因此不必走到柱號 $200$。

初始方向假設

題目未指定 C-LOOK 的初始移動方向；以下採用磁頭由柱號 $65$ 向較大柱號移動的假設。

向大柱號服務：

$$76,\ 87,\ 103,\ 120,\ 138,\ 188$$

之後跳回最小的未服務請求 $7$，再服務 $42$。

服務順序為：

$$65\rightarrow76\rightarrow87\rightarrow103\rightarrow120\rightarrow138\rightarrow188\rightarrow7\rightarrow42$$

總磁頭移動量為：

$$\begin{aligned} T &=(76-65)+(87-76)+(103-87)+(120-103)\\ &\quad +(138-120)+(188-138)+(188-7)+(42-7)\\ &=11+11+16+17+18+50+181+35\\ &=339 \end{aligned}$$

因此：

$$\boxed{\text{C-LOOK 總移動量}=339\text{ cylinders}}$$

其中 $188\rightarrow7$ 是回繞移動，距離為：

$$188-7=181$$

若初始方向指定為向較小柱號移動，服務順序則為：

$$65\rightarrow42\rightarrow7\rightarrow188\rightarrow138\rightarrow120\rightarrow103\rightarrow87\rightarrow76$$

其總移動量為：

$$23+35+181+50+18+17+16+11=351$$

解題技巧

• SSTF：每一步找最近的請求。
• C-LOOK：先決定方向，再排序；服務到該方向最後一個請求後回繞。
• C-LOOK 與 C-SCAN 的差異是：C-LOOK 不必走到柱號 $200$ 或 $0$，只走到最後一個實際請求。

---

（3）Seek time、Rotational latency 與 Random-access time

1. Seek time

**Seek time（尋道時間）**是磁碟磁頭從目前柱號移動到目標柱號所需的時間。

磁頭需要經過：

1. 致動器啟動；
2. 移動到目標磁柱；
3. 停止並穩定在正確磁軌上。

(1) 死鎖預防（Deadlock Prevention）運作機制

死鎖預防（Deadlock Prevention） 的核心機制為：破壞形成死鎖（Deadlock）的四個必要條件之一，確保系統永遠不會進入死鎖狀態。

1. 破壞 Mutual Exclusion（互斥）：
   • 儘可能將資源設為可共用（Shared），例如唯讀檔案。惟多數不可共用資源（如印表機）無法破壞此條件。
2. 破壞 Hold and Wait（持有並等待）：
   • 要求 Process 在執行前必須一次申請並取得所需的全部資源；或規定 Process 在申請新資源前，必須先釋放當前持有的所有資源。
3. 破壞 No Preemption（不可強佔）：
   • 當 Process 持有部分資源並申請新資源失敗時，必須強制釋放（Preempt）其目前持有的所有資源；或允許高優先權 Process 強佔低優先權 Process 的資源。
4. 破壞 Circular Wait（循環等待）：
   • 給予系統中所有資源類型一個唯一的全域遞增編號，並規定 Process 必須嚴格按照資源編號**由小到大的遞增順序（Increasing Order）**提出資源申請。

---

(2) 臨界區段問題（Critical-Section Problem）的三大條件

解出臨界區段問題的任何演算法必須滿足以下三個要求：

1. Mutual Exclusion（互斥性）：
   • 若 Process $P_i$ 正在其 Critical Section 內執行，則其他任何 Process 皆不可在其 Critical Section 內執行。
2. Progress（進展性）：
   • 當沒有 Process 在 Critical Section 內執行，且有 Process 想要進入 Critical Section 時，只有那些「不在 Reminder Section 執行」的 Processes 可以參與決定下一個誰進入，且該決定不可被無限制延遲。
3. Bounded Waiting（有限等待性）：

第 5 題　Security

（1）Stack／Buffer Overflow Attack（6%）

核心觀念

緩衝區溢位（buffer overflow）是程式將超過緩衝區容量的資料寫入記憶體，造成界限外寫入。若緩衝區位於堆疊（stack）中，便稱為堆疊型緩衝區溢位（stack-based buffer overflow）。

典型函式呼叫的堆疊框架可概念化為：

$$\text{區域緩衝區} \rightarrow \text{saved frame pointer} \rightarrow \text{return address} \rightarrow \text{呼叫端資料}$$

若程式使用沒有長度檢查的輸入函式，例如 gets、strcpy、錯誤使用的 sprintf，攻擊者輸入過長資料後，超出緩衝區的部分便會覆寫後方的控制資訊。

解題方法

攻擊流程可分為：

1. 找出會接收外部輸入，且未正確檢查長度的程式。
2. 建立超過緩衝區大小的輸入資料：

$$\text{輸入資料} = \text{填充資料} + \text{被覆寫的控制資料} + \text{後續資料}$$

3. 使輸入內容覆寫函式的返回位址、函式指標，或其他控制流程資料。
4. 當函式執行 return 時，處理器會從堆疊取出被竄改的返回位址，將控制權轉移至攻擊者指定的位置。
5. 早期攻擊可跳入緩衝區內的惡意機器碼；現代攻擊常利用既有程式碼片段組成 ROP（Return-Oriented Programming）鏈，以繞過不可執行堆疊保護。

攻擊結果包括任意程式碼執行、權限提升、竄改資料，以及使程式崩潰形成阻斷服務。

嚴格而言，「stack overflow」也可指無窮遞迴或過深函式呼叫造成堆疊空間耗盡：

$$f(n)\rightarrow f(n+1)\rightarrow f(n+2)\rightarrow\cdots$$

本題的 Security 脈絡主要考查的是「堆疊型緩衝區溢位」所造成的控制流程劫持。

解題技巧

看到「固定大小陣列、外部輸入、缺乏長度檢查、返回位址被覆寫」時，便應聯想到 stack-based buffer overflow。防禦方式包括邊界檢查、stack canary、ASLR、NX／DEP、CFI，以及最小權限原則。

---

（2）對稱式加密的兩大類型（4%）

核心觀念

對稱式加密（symmetric encryption）使用同一把秘密金鑰進行加密與解密：

$$C=E_K(P),\qquad P=D_K(C)$$

其中 $P$ 為明文、$C$ 為密文、$K$ 為共享金鑰。

兩大類型是區塊加密與串流加密。

類型	運作方式	常見特性與例子
區塊加密（block cipher）	將明文切成固定大小區塊，逐區塊進行轉換	AES、DES；常搭配 CBC、CTR、GCM 等模式
串流加密（stream cipher）	產生金鑰串流，逐位元或逐位元組與明文 XOR	ChaCha20、RC4

區塊加密

若每個明文區塊為 $P_i$，加密可寫為：

$$C_i=E_K(P_i)$$

實際使用時需搭配操作模式與 IV／nonce。ECB 模式會使相同明文區塊產生相同密文區塊，容易洩漏資料結構，因此不適合直接加密一般文件。需要整個區塊輸入的模式還需使用 padding。

串流加密

串流加密先依據金鑰與 nonce 產生金鑰串流 $S_i$：

$$C_i=P_i\oplus S_i$$

解密時使用相同的 XOR：

$$P_i=C_i\oplus S_i$$

同一把金鑰下不可重複使用相同 nonce，否則：

$$C_1\oplus C_2 = (P_1\oplus S)\oplus(P_2\oplus S) = P_1\oplus P_2$$

攻擊者便能取得兩份明文的關係。

解題技巧

判斷兩類型的關鍵是「處理單位」：固定大小資料塊屬於 block cipher，連續位元或位元組屬於 stream cipher。

---

（3）RSA 演算法（5%）

核心觀念

RSA 是公開金鑰密碼系統，安全性建立在大整數分解的困難性。它使用一組公開金鑰與一組私密金鑰：

• 公開金鑰：$(e,n)$
• 私密金鑰：$(d,n)$

解題方法與推導

1. 選擇兩個大型且不同的質數 $p,q$。

2. 計算：

   $n=pq$

   $\varphi(n)=(p-1)(q-1)$

3. 選擇 $e$，使得：

   $1<e<\varphi(n),\qquad \gcd(e,\varphi(n))=1$

4. 計算 $e$ 在模 $\varphi(n)$ 下的乘法反元素 $d$：

   $ed\equiv 1\pmod{\varphi(n)}$