# 2024 Finals
[toc]
### 1. EAT 計算
在一個帶有**關聯暫存器 (associative registers, TLB)** 的需求分頁系統中，服務一次**頁錯誤 (page fault)** 需要 **2 毫秒 (milliseconds)**。一次記憶體參考需要 **200 奈秒 (nanoseconds)**，在關聯暫存器中找到頁表條目需要 **20 奈秒**。如果 TLB **命中率 (hit ratio)** 是 **90%**，**頁錯誤率 (page fault ratio)** 是 **10%**，求**有效存取時間 (Effective Access Time, EAT)**。
**步驟 1: 參數轉換與定義**
* $T_{pf} = 2 \text{ ms} = 2,000,000 \text{ ns}$ (page fault times)
* $T_{mem} = 200 \text{ ns}$ (memory access time)
* $T_{tlb} = 20 \text{ ns}$ (TLB access time)
* $H = 0.90$ (TLB hit rate)
* $P = 0.10$ (page fault rate)
* $M = 2 \times T_{mem} = 400 \text{ ns}$ (TLB 不命中時，需要一次 TLB 存取 + 兩次記憶體存取：頁表和資料)
**步驟 2: 計算 EAT**
$$EAT = H \times (T_{tlb} + T_{mem}) + (1-H) \times [ (1-P) \times (T_{tlb} + 2 \times T_{mem}) + P \times T_{pf} ]$$
$$EAT = 0.90 \times (20 + 200) + 0.10 \times [ 0.90 \times (20 + 200 + 200) + 0.10 \times 2,000,000 ]$$
$$EAT = 0.90 \times (220) + 0.10 \times [ 0.90 \times (420) + 0.10 \times 2,000,020 ]$$
$$EAT = 198 + 0.10 \times [ 378 + 200,002 ]$$
$$EAT = 198 + 0.10 \times [ 200,380 ]$$
$$EAT = 198 + 20,038$$
$$EAT = 20,236 \text{ ns} \approx 20.24 \text{ }\mu\text{s}$$
**有效存取時間 (EAT) 約為 $20,236 \text{ ns}$ (或 $20.24 \text{ }\mu\text{s}$ )。**
---
### 2. 記憶體位址轉換（分段與分頁）
**題目 (Q2)：** 考慮一個 $16 \text{ 位元}$ 虛擬位址、實體記憶體 $4 \text{ KB}$、頁面大小 $256 \text{ Bytes}$、最大段大小 $1 \text{ KB}$ 的電腦系統。給定段表、頁表和 $16 \text{ bits}$ 十六進制邏輯位址 **"0C42"**，完成位址轉換圖：(a) 段表索引 (b) 線性位址 (二進制) (c.) 頁表索引 (d) 實體位址 (二進制)。
#### **基礎參數計算 (Base Parameter Calculation)**
* **虛擬位址 (邏輯位址)：** $16 \text{ bits}$
* **頁面大小：** $256 \text{ Bytes} = 2^8 \text{ Bytes}$ $\implies$ **page offset $d = 8 \text{ bits}$**
* **線性位址空間 (Segment Limit)：** $1 \text{ KB} = 1024 \text{ Bytes} = 2^{10} \text{ Bytes}$ $\implies$ **offset $d' = 10 \text{ bits}$**
* **邏輯位址 "0C42" (Hex)：** $0000 \ 1100 \ 0100 \ 0010 \text{ (Binary)}$
#### **解答 (Solution)**
---
### 3. 不同分頁機制下行程頁表所需的記憶體空間
考慮一個 **32 位元作業系統 (32-bit OS)**，運行在具有 **64MB 實體記憶體 (physical memory)** 的機器上。OS 將 32 位元邏輯位址空間劃分成頁，每頁大小為 **4KB**。假設頁表中每個條目大小為 **4 bytes**，請計算在下列四種位址轉換方法下，**一個行程的頁表**所需的記憶體空間。
#### **基礎參數計算 (Base Parameter Calculation)**
1. **邏輯位址空間大小：** $2^{32} \text{ bytes}$
2. **Page Size, $P$:** $4 \text{ KB} = 2^{12} \text{ bytes}$
3. **Offset Bits:** $\log_2P = 12 \text{ bits}$
4. **Virtual Page Number, VPN:** $32 - 12 = 20 \text{ bits}$
5. **Total Virtual Pages:** $2^{20} \text{ 頁}$
#### **解答 (Solution)**
**(a) 一級頁表 (One-level page table)**
* **所需的記憶體空間：** 頁表條目數 $\times$ 每個條目大小
$$2^{20} \times 4 \text{ bytes} = 4 \text{ MB}$$
**(b) 二級頁表 (Two-level page table)**
* **條件：** 第一級頁表有 **256 個條目** (即 $2^8$)；只需要**第一級頁表**和**第一塊第二級頁表**存於記憶體中。
* **位址分解：** 20 位 VPN 分解為：
* 第一級頁號 ($P_1$): $\log_2(256) = 8 \text{ bits}$
* 第二級頁號 ($P_2$): $20 - 8 = 12 \text{ bits}$
* **所需頁表條目數：**
* 第一級頁表：$2^8 = 256 \text{ 條}$
* 第二級頁表（只需第一塊）：$2^{12} = 4096 \text{ 條}$
* **所需的記憶體空間：** (第一級條目數 + 第二級條目數) $\times$ 每個條目大小
$$(256 + 4096) \times 4 \text{ bytes} = 4352 \times 4 \text{ bytes} = 17,408 \text{ bytes} \approx 17.0 \text{ KB}$$
**所需空間：$17,408 \text{ bytes}$ (或 $17.0 \text{ KB}$)**
**(c.) Hashed paged table**
* **條件：** 雜湊函數的範圍在 **0 到 27** 之間，即雜湊表（Hash Table）有 $28$ 個**雜湊鏈 (hash chains)**。
* **定義：** 雜湊頁表只儲存**實際使用的**虛擬頁號及其對應的頁框號。它的大小與**虛擬位址空間大小**無關，而與**實際使用的頁面數**和**雜湊表大小**有關。
* **計算：** 題目沒有給出行程實際使用的頁數，但一個簡單的估計是基於雜湊表的鏈頭數量。通常雜湊頁表空間至少包含雜湊表本身。
* **雜湊表 (鏈頭) 空間：** 雜湊鏈數量 $\times$ 每個條目大小
$$28 \times 4 \text{ bytes} = 112 \text{ bytes}$$
* *註：* 這是**雜湊表**的大小，還未計算實際的**鏈條**空間（即鏈接的頁表條目）。由於條件不足（缺少實際使用的頁面數），**最精簡且確定的回答是鏈頭的大小**。
**所需空間 (鏈頭)：$112 \text{ bytes}$**
**(d) 反向頁表 (Inverted page table)**
* **定義：** 反向頁表只有**一個**，表中的條目數量與**實體記憶體中的頁框數量 (Frame Count)** 相等，而不是與虛擬頁面數相等。
* **實體記憶體大小 (Physical Memory, $M$):** $64 \text{ MB} = 2^6 \times 2^{20} = 2^{26} \text{ bytes}$
* **實體頁框數 (Frame Count):** $M / P$
$$2^{26} \text{ bytes} / 2^{12} \text{ bytes} = 2^{14} \text{ 頁框}$$
* **所需的記憶體空間：** 實體頁框數 $\times$ 每個條目大小
$$2^{14} \times 4 \text{ bytes} = 2^{14} \times 2^2 \text{ bytes} = 2^{16} \text{ bytes} = 64 \text{ KB}$$
**所需空間：$64 \text{ KB}$**
---
### 4. Page Replacement Algorithms
考慮下表中五個頁面的狀態。在下列各演算法下，哪一頁將會被置換？
| Page | Loading time | The last reference time | R bit | M bit | Accumulated reference bit |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | 087 | 682 | 1 | 0 | 516 |
| 2 | 941 | 993 | 1 | 1 | 020 |
| 3 | 684 | 981 | 0 | 0 | 278 |
| 4 | 194 | 625 | 1 | 1 | 397 |
| 5 | 091 | 277 | 0 | 1 | 093 |
**What is the replaced page under each of following algorithm?**
(a) FIFO (b) LRU (c.) second chance (d) enhanced second chance (e) LFU
#### **解答 (Solution)**
置換原則是選擇各演算法中最小或最不符合條件的頁面。
**(a) FIFO (First-In, First-Out)**
* **原則：** 選擇**載入時間 (Loading time)** 最早的頁面。
* **判斷：** **頁面 1 (087)**, 頁面 2 (941), 頁面 3 (684), 頁面 5 (091), 頁面 4 (194)。
* **置換頁面：** **Page 1** (載入時間 087)
**(b) LRU (Least Recently Used)**
* **原則：** 選擇**上次參考時間 (The last reference time)** 最早的頁面。
* **判斷：** 頁面 1 (682), 頁面 2 (993), 頁面 3 (981), 頁面 4 (625), **頁面 5 (277)**。
* **置換頁面：** **Page 5** (上次參考時間 277)
**(c.) Second Chance (第二次機會演算法)**
* **原則：** 依 FIFO 順序，檢查 **R bit (參考位元)**。若 $R=0$，置換；若 $R=1$，給予第二次機會（設定 $R=0$ 並移到佇列尾部）。假設檢查順序為頁面 1 $\to$ 2 $\to$ 3 $\to$ 4 $\to$ 5 (根據 Loading time 的 FIFO 順序: 1, 5, 4, 3, 2)。
* **FIFO 順序：** 頁面 1 $\to$ 頁面 5 $\to$ 頁面 4 $\to$ 頁面 3 $\to$ 頁面 2
* **檢查：**
1. **Page 1 (R=1)：** 得到第二次機會，R $\to 0$，移到尾部。
2. **Page 5 (R=0)：** **置換**。
* **置換頁面：** **Page 5**
**(d) Enhanced Second Chance (增強型第二次機會/NRU)**
* **原則：** 根據 **(R, M)** 類別優先置換：**Class 1 (0, 0)** $\to$ **Class 2 (0, 1)** $\to$ **Class 3 (1, 0)** $\to$ **Class 4 (1, 1)**。在同類別中，依 FIFO 順序選擇。
* **Class (0, 0):** Page 3 (最不常用且未修改) $\to$ **首選置換**
* **置換頁面：** **Page 3**
**(e) LFU (Least Frequently Used)**
* **原則：** 選擇**參考次數 (Accumulated reference bit)** 最小的頁面。
* **判斷：** 頁面 1 (516), 頁面 2 (020), 頁面 3 (278), 頁面 4 (397), 頁面 5 (093)。
* **置換頁面：** **Page 2** (參考次數 020)
---
### 5. Deadlock 的四種處理策略
* **死鎖預防 (Deadlock Prevention)：** 透過**限制**，確保死鎖的四個**必要條件**（互斥、持有並等待、不可搶佔、循環等待）中**至少一個永遠不會成立**。
* **死鎖避免 (Deadlock Avoidance)：** 系統在每次資源申請時**動態檢查**，使用演算法（如**銀行家演算法**）確保系統**永遠不會進入不安全狀態**。
* **死鎖偵測 (Deadlock Detection)：** 允許死鎖發生，但系統會**定期執行演算法**檢查資源分配圖中是否存在**循環**。
* **死鎖恢復 (Deadlock Recovery)：** 一旦偵測到死鎖，採取措施**打破循環**。
* *方法：* **中止行程**（一次一個或一次全部），或**資源搶佔**（從受害者行程中拿走資源）。
---
### 6. 分頁與夥伴系統的定義與比較
* **Paging for User Space：**
* 將程式的**邏輯位址**和**實體記憶體**都劃分成**固定大小**的塊（page/frame）。
* **Buddy System for Kernel：**
* 一種動態記憶體分配技術，將記憶體劃分為大小為 **$2^n$** 的塊。
| 特徵 (Feature) | 分頁 (Paging) | 夥伴系統 (Buddy System) |
| :--- | :--- | :--- |
| **主要用途** | user space 程式的 virtual memory 實作 | **kernel space** 記憶體分配 |
| **分配單位** | **固定大小**的頁面 | **2 的冪次**大小的塊 |
| **主要功能** | **位址轉換** (邏輯 $\to$ 實體) | **動態記憶體分配與合併** |
| **碎片問題** | **內部碎片** | 內部碎片，外部碎片較少（合併快速） |
### 7. Definition and solutions of Thrashing
當系統的**多工度過高**，行程總頁面需求超過實體記憶體時，行程會**不斷地**發生**頁錯誤（Page Faults）**。系統將大部分時間花費在磁碟 I/O（調入/調出頁面）上，導致 **CPU utilization rate 極低**。
* **方法一：Working-Set Model**
* **機制：** 定義一個**工作集 (Working Set)**，即在一段時間 $\Delta$ 內行程存取過的頁面集合。只允許在**所有行程工作集總和**小於實體記憶體容量時，才允許執行該行程。
* **方法二：Page-Fault Frequency, PFF**
* **原理：** 監控每個行程的**頁錯誤率**。
* **機制：** 設定 PFF 上限和下限。
* 若 PFF **高於上限**：認為頁框不足，應**增加**分配給該行程的頁框數。
* 若 PFF **低於下限**：認為頁框過多，應**減少**分配給該行程的頁框數。
---
### 8. Banker's Algorithm
考慮一個系統的快照如下：
| Process | Allocation (A B C D) | Max (A B C D) | Available (A B C D) |
| :--- | :--- | :--- | :--- |
| P0 | 0 6 0 4 | 1 9 8 9 | A: 1, B: 4, C: 1, D: 3 |
| P1 | 1 0 0 1 | 2 4 2 1 | |
| P2 | 0 1 1 2 | 1 1 2 3 | |
| P3 | 0 0 2 5 | 0 5 5 9 | |
| P4 | 2 1 4 1 | 4 2 6 7 | |
(a) What is the content of the matrix **Need**? (2 points)
(b) Is the system in a **safe state**? Please list the corresponding access sequence. (5 points)
(c.) If a request from process P1 arrives for **(0, 2, 0, 0)**, can the request be granted immediately, why? If it can, please list the corresponding access sequence. (5 points)
#### **解答 (Solution)**
#### (a) 計算需求矩陣 (Need Matrix)
$\text{Need} = \text{Max} - \text{Allocation}$
| Process | Need (A B C D) |
| :--- | :--- |
| P0 | 1 3 8 5 |
| P1 | 1 4 2 0 |
| P2 | 1 0 1 1 |
| P3 | 0 5 3 4 |
| P4 | 2 1 2 6 |
#### (b) 判斷系統是否處於安全狀態 (Safe State)
**Available** $= (1, 4, 1, 3)$
| Step | Process | Need | Available $\ge$ Need? | New Available | 序列 (Sequence) |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | P0 | (1, 3, 8, 5) | False | | |
| | P1 | (1, 4, 2, 0) | False | | |
| | **P2** | **(1, 0, 1, 1)** | **True** | $(1, 4, 1, 3) + (0, 1, 1, 2) = (1, 5, 2, 5)$ | P2 |
| | P3 | (0, 5, 3, 4) | False | | |
| | P4 | (2, 1, 2, 6) | False | | |
| 2 | **P3** | **(0, 5, 3, 4)** | **False** (5 > 5) $\implies$ Need is **(0, 5, 3, 4)**. Wait, Need(P3, B) = 5. Available(B) is now 5. **True** | $(1, 5, 2, 5) + (0, 0, 2, 5) = (1, 5, 4, 10)$ | P2, P3 |
| 3 | **P0** | **(1, 3, 8, 5)** | False (8 > 4) $\implies$ Wait. Let's try P1. | | |
| | **P1** | **(1, 4, 2, 0)** | **True** | $(1, 5, 4, 10) + (1, 0, 0, 1) = (2, 5, 4, 11)$ | P2, P3, P1 |
| 4 | **P4** | **(2, 1, 2, 6)** | **True** | $(2, 5, 4, 11) + (2, 1, 4, 1) = (4, 6, 8, 12)$ | P2, P3, P1, P4 |
| 5 | **P0** | **(1, 3, 8, 5)** | **True** | $(4, 6, 8, 12) + (0, 6, 0, 4) = (4, 12, 8, 16)$ | P2, P3, P1, P4, P0 |
**結論：** **是**，系統處於安全狀態。
**安全序列：** $\langle P2, P3, P1, P4, P0 \rangle$ (或其他有效排列)
#### (c.) 處理 P1 的資源請求 Request(0, 2, 0, 0)
1. **檢查 1：Request $\le$ Need?**
* $\text{Request}(0, 2, 0, 0) \le \text{Need}(\text{P}1)(1, 4, 2, 0)$
* $(0 \le 1, 2 \le 4, 0 \le 2, 0 \le 0) \implies$ **True**
2. **檢查 2：Request $\le$ Available?**
* $\text{Request}(0, 2, 0, 0) \le \text{Available}(1, 4, 1, 3)$
* $(0 \le 1, 2 \le 4, 0 \le 1, 0 \le 3) \implies$ **True**
3. **暫時分配：**
* $\text{Available}' = \text{Available} - \text{Request} = (1, 4, 1, 3) - (0, 2, 0, 0) = (1, 2, 1, 3)$
* $\text{Allocation}'(\text{P}1) = \text{Allocation}(\text{P}1) + \text{Request} = (1, 0, 0, 1) + (0, 2, 0, 0) = (1, 2, 0, 1)$
* $\text{Need}'(\text{P}1) = \text{Need}(\text{P}1) - \text{Request} = (1, 4, 2, 0) - (0, 2, 0, 0) = (1, 2, 2, 0)$
4. **執行安全演算法 (Safety Check) - 新狀態：**
* $\text{Available}' = (1, 2, 1, 3)$
| Step | Process | Need' | Available' $\ge$ Need'? | New Available | 序列 (Sequence) |
| :--- | :--- | :--- | :--- | :--- | :--- |
| 1 | P0 | (1, 3, 8, 5) | False | | |
| | P1 | (1, 2, 2, 0) | False | | |
| | **P2** | **(1, 0, 1, 1)** | **True** | $(1, 2, 1, 3) + (0, 1, 1, 2) = (1, 3, 2, 5)$ | P2 |
| 2 | P0 | (1, 3, 8, 5) | False | | |
| | P1 | (1, 2, 2, 0) | True | $(1, 3, 2, 5) + (1, 2, 0, 1) = (2, 5, 2, 6)$ | P2, P1 | **P3** | (0, 5, 3, 4) | False (3<5) $\implies$ Wait. Let's try P4. | | |
| | **P4** | (2, 1, 2, 6) | True | $(2, 5, 2, 6) + (2, 1, 4, 1) = (4, 6, 6, 7)$ | P2, P1, P4 |
| 4 | **P0** | (1, 3, 8, 5) | False | | |
| | **P3** | (0, 5, 3, 4) | True | $(4, 6, 6, 7) + (0, 0, 2, 5) = (4, 6, 8, 12)$ | P2, P1, P4, P3 |
| 5 | **P0** | (1, 3, 8, 5) | True | $(4, 6, 8, 12) + (0, 6, 0, 4) = (4, 12, 8, 16)$ | P2, P1, P4, P3, P0 |
**結論：** **可以**立即批准請求。因為新狀態仍是安全的。
**對應的安全序列：** $\langle P2, P1, P4, P3, P0 \rangle$
---
### 9. 當 page size 增加時，下列特性如何變化，並說明原因。
* (a) Fragmentation (碎片)
* 增加，頁面越大，最後一頁未使用的空間越多，內部碎片增加。
* (b) Page table size (頁表大小)
* 減少，在相同總記憶體下，頁面數減少，因此頁表中的條目數量減少。
* (c.) Resolution (解析度/分辨度)
* 減少，記憶體被劃分為更大的塊，位址轉換和記憶體管理變得更粗略。
* (d) I/O time (輸入/輸出次數)
* 減少，每次 I/O 傳輸的資料量增加，減少了總 I/O 次數。
* (e) Number of page faults (頁錯誤次數)
* 減少，根據空間局部性，一次載入更多鄰近資料，命中率提高，減少缺頁。
* (f) Locality (區域性/局部性)
* 不相關的資料也被載入，增加「無用資料」的比例，locality 下降
* (G) TLB size and effectiveness:
*
---
### Banker's Algorithm
確保在分配資源給行程時，系統仍能找到一個**安全序列 (Safe Sequence)**，即所有行程都能在有限時間內完成執行的次序。
#### 四個關鍵數據結構
* **Available (可用資源向量):** 一個長度為 $m$ 的向量，表示每種資源類型當前有多少個可用的實例。
* *例：* $\text{Available}[j] = k$ 表示資源 $R_j$ 還有 $k$ 個實例可供分配。
* **Max (最大需求矩陣):** 一個 $n \times m$ 的矩陣，表示每個行程 $P_i$ 對每種資源 $R_j$ 的**最大需求**數量。
* **Allocation (分配矩陣):** 一個 $n \times m$ 的矩陣，表示每種資源類型當前已分配給每個行程 $P_i$ 的實例數量。
* **Need (需求矩陣):** 一個 $n \times m$ 的矩陣，表示每個行程 $P_i$ 還需要的資源實例數量。
* 計算公式：$\text{Need}[i, j] = \text{Max}[i, j] - \text{Allocation}[i, j]$。
* 目前需要的 = 最大需求量 - 已經分配的
#### 安全狀態 (Safe State) 檢查演算法
系統在分配資源前，必須執行安全檢查演算法來判斷新的狀態是否安全。
1. **初始化:** 設置兩個向量：
* **Work (工作向量):** 初始化為 $\text{Work} = \text{Available}$。
* **Finish (完成向量):** 初始化為 $n$ 個 $\text{False}$，表示所有行程尚未完成。
2. **查找:** 尋找一個滿足以下兩個條件的行程 $P_i$：
* (a) $\text{Finish}[i] == \text{False}$ (該行程尚未完成)。
* (b) $\text{Need}_i \le \text{Work}$ (目前需求 <= 系統的工作量)。
3. **執行:** 如果找到這樣的行程 $P_i$：
* 假設 $P_i$ 獲得所需資源並執行完成，釋放其已分配的資源。
* 更新 $\text{Work} = \text{Work} + \text{Allocation}_i$。
* 設置 $\text{Finish}[i] = \text{True}$。
* 返回步驟 2 繼續查找下一個行程。
4. **結束:** 如果找不到滿足步驟 2 條件的行程，檢查所有行程是否都已完成。
* 如果所有 $\text{Finish}[i]$ 都是 $\text{True}$，則系統處於**安全狀態**。
* 如果至少有一個 $\text{Finish}[i]$ 是 $\text{False}$，則系統處於**不安全狀態 (Unsafe State)**，可能導致死鎖。
#### Resource-Request Algorithm
當行程 $P_i$ 提出資源請求 $\text{Request}_i$ 時，系統會執行以下步驟來決定是否批准分配：
1. **檢查需求:** 請求的資源量是否超過其最大需求？
* 如果 $\text{Request}_i \le \text{Need}_i$，則進入下一步。
* 否則，請求出錯，因為行程要求的資源量超過了其最大聲明。(根本不用那麼多)
2. **檢查可用性:** 請求的資源量是否超過當前可用資源？
* 如果 $\text{Request}_i \le \text{Available}$，則進入下一步。
* 否則，行程必須等待，直到資源可用。(不夠用，要等)
3. **試探性分配:** 系統**假設**資源已被分配給 $P_i$，並暫時修改狀態：
* $\text{Available} = \text{Available} - \text{Request}_i$。
* $\text{Allocation}_i = \text{Allocation}_i + \text{Request}_i$。
* $\text{Need}_i = \text{Need}_i - \text{Request}_i$。
4. **安全檢查:** 執行**安全狀態檢查演算法** (步驟 2)。
* 如果新狀態是**安全**的，則**批准**分配，交易完成。
* 如果新狀態是**不安全**的，則**拒絕**分配，並**恢復**到原始狀態，行程 $P_i$ 必須等待。
---
### Pseudocode 整理 (必考)
#### 1\. Mutex Locks (互斥鎖) - Spinlock 實現
實現 **Mutual Exclusion (互斥)**，保護 **Critical Section** 。這是最簡單的同步工具 。
| 操作 (Operation) | Pseudocode (偽代碼) | 核心概念 (Key Concept) |
| :--- | :--- | :--- |
| **`acquire()`** (獲取鎖) | $$\begin{array}{l} \text{acquire() \{} \\ \quad \text{while (!available)} \\ \quad \quad \text{; /* busy wait */ }\\ \quad \text{available = false;} \\ \text{\}} \end{array}$$ | **Busy Waiting**：如果鎖不可用 (`!available`)，**Process** 會一直空轉等待 。因此這種鎖被稱為 **Spinlock** 。 |
| **`release()`** (釋放鎖) | $$\begin{array}{l} \text{release() \{} \\ \quad \text{available = true;} \\ \text{\}} \end{array}$$ | 將鎖狀態設為可用，讓其他等待的 **Process** 能夠通過 `acquire()` 。 |
| **原子性要求** | **`acquire()`** 和 **`release()`** 必須是 **Atomic (原子性)** 的 。 |
-----
### 2\. Semaphores (號誌)
**Semaphore** 是一個整數變數，只能被兩個 **Atomic (原子性)** 操作修改：`wait()` 和 `signal()` 。
#### A. Busy Waiting 實現 (原始定義)
這是最簡單的 **Semaphore** 定義，但會導致 **CPU Cycles** 浪費 。
| 操作 (Operation) | Pseudocode (偽代碼) | 核心概念 (Key Concept) |
| :--- | :--- | :--- |
| **`wait(S)`** | $$\begin{array}{l} \text{wait (S) \{} \\ \quad \text{while S } \leq 0 \\ \quad \quad \text{; // busy wait} \\ \quad \text{S--;} \\ \text{\}} \end{array}$$ | 阻塞 (Block) 直到 $S > 0$，然後將 $S$ 減一 。 |
| **`signal(S)`** | $$\begin{array}{l} \text{signal (S) \{} \\ \quad \text{S++;} \\ \text{\}} \end{array}$$ | 將 $S$ 加一 。 |
#### B. Blocking (阻塞) 實現 (避免 Busy Waiting)
為了解決 **Busy Waiting** 浪費資源的問題，現代 **Semaphore** 實作讓 Process 進入 **Waiting Queue** (等待佇列) 並 **Block (阻塞)** 自己 。
**資料結構：**
```c
typedef struct{
int value;
struct process *list; // Pointer to waiting process list
} semaphore;
```
| 操作 (Operation) | Pseudocode (偽代碼) | 核心概念 (Key Concept) |
| :--- | :--- | :--- |
| **`wait(S)`** | $$\begin{array}{l} \text{wait(semaphore *S) \{} \\ \quad \text{S->value--;} \\ \quad \text{if (S->value < 0) \{} \\ \quad \quad \text{add this process to S->list;} \\ \quad \quad \text{sleep();} \\ \quad \text{\}} \\ \text{\}} \end{array}$$ | 如果 $S \rightarrow value < 0$，表示資源被佔用或計數不足，**Process** 加入 **Waiting List** 後調用 **`sleep()`** 暫停 。 |
| **`signal(S)`** | $$\begin{array}{l} \text{signal(semaphore *S) \{} \\ \quad \text{S->value++;} \\ \quad \text{if (S->value <= 0) \{} \\ \quad \quad \text{remove a process P from S->list;} \\ \quad \quad \text{wakeup(P);} \\ \quad \text{\}} \\ \text{\}} \end{array}$$ | 如果 $S \rightarrow value \leq 0$，表示有 **Process** 正在等待，移除其中一個 **Process P**，並調用 **`wakeup(P)`** 恢復其執行 。 |
-----
### 3\. Monitors (管程)
**Monitor** 本身是一個程式語言的構造，它在語言層面保證了對 **Shared Data** 的 **Mutual Exclusion** (互斥) 。
#### A. 核心概念：Condition Variables (條件變數)
**Monitor** 內部的同步等待是通過 **Condition Variables** 實現的，它沒有值，但有兩個方法：
| 操作 (Operation) | 作用 (Function) | 核心概念 (Key Concept) |
| :--- | :--- | :--- |
| **`x.wait()`** | 暫停調用操作的 **Process**，放入該 **Condition Variable** 的 **Waiting List** 。 | **Process** 釋放 Monitor 的 **Mutual Exclusion** 鎖，並等待特定 **Event** 發生 。 |
| **`x.signal()`** | 恢復一個 (如果有的話) 正在調用 **`x.wait()`** 的 **Process** 。 | **Signal** 如果沒有 **Waiting Process** 將會被**丟失** 。 |
#### B. Monitor 的 Semaphore 實現結構
儘管 **Monitor** 本身是高級語言結構，但其內部 **Mutual Exclusion** 和 **Condition Variables** 的語義通常是用 **Semaphores** 實現的 。
| Semaphore/Counter | 初始值 (Initial Value) | 用途 (Purpose) |
| :--- | :--- | :--- |
| **`mutex`** | 1 | 確保 Monitor 內的**互斥** (只有一個 Process 在執行) 。 |
| **`next`** | 0 | 用於 **Signaling Process** 暫時等待，以便將 **Monitor** 釋放給被喚醒的 **Process** (防止互斥違規) 。 |
| **`next_count`** | 0 | 記錄有多少 **Process** 因 **Signal** 而暫時等待在 `next` **Semaphore** 上 。 |
> 由於 **Monitor** 的實作細節較為複雜且依賴於 **Semaphore** 的 `wait/signal` 邏輯，教授可能更傾向於直接測試 **Bounded-Buffer** 或 **Dining-Philosophers** 這些經典問題中 **Semaphore** 的應用程式級 **Pseudocode**。
### 必考的經典同步問題 Pseudocode
#### 1\. Bounded-Buffer Problem (有限緩衝區問題)
**Semaphore 設置：** `mutex=1` (互斥鎖), `empty=N` (空位數), `full=0` (數據數)。
| 角色 (Role) | Pseudocode (偽代碼) | 關鍵步驟|
| :--- | :--- | :--- |
| **Producer (生產者)** | $$\begin{array}{l} \text{do \{} \\ \quad \text{// produce an item in nextp} \\ \quad \mathbf{\text{wait (empty)};} \\ \quad \mathbf{\text{wait (mutex)};} \\ \quad \text{// add the item to the buffer} \\ \quad \mathbf{\text{signal (mutex)};} \\ \quad \mathbf{\text{signal (full)};} \\ \quad \text{\} while (TRUE);} \end{array}$$ | **1. `wait(empty)`**: 確保有空位可放 (數量控制) 。<br> **2. `wait(mutex)`**: 確保互斥存取 Buffer 。 |
| **Consumer (消費者)** | $$\begin{array}{l} \text{do \{} \\ \quad \mathbf{\text{wait (full)};} \\ \quad \mathbf{\text{wait (mutex)};} \\ \quad \text{// remove an item from buffer to nextc} \\ \quad \mathbf{\text{signal (mutex)};} \\ \quad \mathbf{\text{signal (empty)};} \\ \quad \text{// consume the item in nextc} \\ \quad \text{\} while (TRUE);} \end{array}$$ | **1. `wait(full)`**: 確保有數據可取 (數量控制) 。<br> **2. `wait(mutex)`**: 確保互斥存取 Buffer 。 |
> 考點：**順序**。如果 Producer 的 `wait(mutex)` 和 `wait(empty)` 順序顛倒，可能會導致 **Deadlock (死鎖)** 。
#### 2\. Dining-Philosophers Problem (哲學家進餐問題)
**Semaphore 設置：** 陣列 `chopstick[5]` (每根筷子) 初始化為 1 。
| 角色 (Role) | Pseudocode (偽代碼) | 關鍵步驟 (Critical Steps) |
| :--- | :--- | :--- |
| **Philosopher $i$** | $$\begin{array}{l} \text{While (TRUE) \{} \\ \quad \mathbf{\text{wait (chopstick[i]);}} \\ \quad \mathbf{\text{wait (chopstick[ (i+1)%5]);}} \\ \quad \text{// eat} \\ \quad \mathbf{\text{signal (chopstick[i]);}} \\ \quad \mathbf{\text{signal (chopstick[ (i+1)%5]);}} \\ \quad \text{// think} \\ \text{\}} \end{array}$$ | **Deadlock 條件**：如果所有五位 **Philosophers** 同時執行到第二個 `wait()`，將導致 **Circular Wait (循環等待)**，從而陷入 **Deadlock** 。 |
### 考古
以下為精簡版、無 emoji、只有文字與計算結果：
---
**已知條件：**
* 磁碟軌道 0–199
* 目前磁頭在 100
* 剛服務完 110，因此方向向左
* 佇列：86, 117, 91, 150, 102
---
#### (a) FCFS
順序：100 → 86 → 117 → 91 → 150 → 102
距離：
14 + 31 + 26 + 59 + 48 = **178**
**FCFS = 178**
---
#### (b) SSTF
排序過程：
100 → 102 → 91 → 86 → 117 → 150
距離：
2 + 11 + 5 + 31 + 33 = **82**
**SSTF = 82**
---
#### (c.) SCAN（方向向左）
左側：91, 86
右側：102, 117, 150
路徑：100 → 91 → 86 → 0 → 102 → 117 → 150
距離：
9 + 5 + 86 + 102 + 15 + 33 = **250**
**SCAN = 250**
---
#### (d) C-SCAN（方向向左）
路徑：100 → 91 → 86 → 0 → 199 → 150 → 117 → 102
距離：
9 + 5 + 86 + 199 + 49 + 33 + 15 = **396**
**C-SCAN = 396**
---
#### (e) LOOK（不掃到邊界）
路徑：100 → 91 → 86 → 102 → 117 → 150
距離：
9 + 5 + 16 + 15 + 33 = **78**
**LOOK = 78**
---
#### 最終答案
* FCFS = 178
* SSTF = 82
* SCAN = 250
* C-SCAN = 396
* LOOK = 78
Sign in with Wallet
Connect another wallet