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

核心觀念

本題考查兩種 CPU 排程：

• Nonpreemptive Priority Scheduling（非搶先式優先權排程）：優先權數字越小，優先權越高；程序一旦開始執行，就會持續到 CPU burst 完成。
• Shortest-Job-First, SJF（最短工作優先）：每次選擇 CPU burst time 最短的程序執行。本題所有程序皆在時間 $0$ 到達，因此可直接依 burst time 排序。

相關定義如下：

• Completion time：
  $C_i=\text{程序完成執行的時間}$
• Waiting time：
  $W_i=\text{開始執行時間}-\text{到達時間}$

由於所有程序皆在時間 $0$ 到達，因此某程序的等待時間就是它開始執行前，前面所有程序 burst time 的總和。

---

(a) 非搶先式優先權排程中，$P_1$ 的完成時間

優先權表如下：

程序	Burst Time	Priority
$P_1$	10	3
$P_2$	1	1
$P_3$	2	4
$P_4$	1	5
$P_5$	5	2

優先權數字越小越優先，因此執行順序為：

$P_2 \rightarrow P_5 \rightarrow P_1 \rightarrow P_3 \rightarrow P_4$

甘特圖：

$$0 \quad\ \ 1 \quad\ \ 6 \quad\ \ \ 16 \quad\ \ 18 \quad\ \ 19$$ $$\left[P_2\right]\left[P_5\right]\quad [P_1]\quad\ [P_3]\ [P_4]$$

$P_1$ 在 $P_2$ 與 $P_5$ 完成後才開始：

$$S_1=1+5=6$$

因此：

$$C_1=S_1+\text{Burst Time}(P_1)$$ $$C_1=6+10=16\text{ ms}$$

核心觀念

頁表的每一筆 Page Table Entry（PTE） 對應一個虛擬頁。因此，頁表所需的 entries 數量為：

$$\text{頁表 entries 數量} = \frac{\text{虛擬位址空間大小}}{\text{頁面大小}}$$

虛擬位址可分為：

• 虛擬頁號（Virtual Page Number, VPN）
• 頁內位移（Page Offset）

頁面大小決定位移欄位的位元數；剩餘的虛擬位址位元則用來表示虛擬頁號。

解題方法

依一般考題的位元組定址假設：

1. 求頁內位移位元數

頁面大小為 $32\text{ KB}$：

$$32\text{ KB}=32\times 1024\text{ bytes}=2^{15}\text{ bytes}$$

因此，頁內位移需要 $15$ bits。

2. 求虛擬頁號位元數

虛擬位址長度為 $64$ bits，所以：

$$\text{VPN bits}=64-15=49\text{ bits}$$

3. 求頁表 entries 數量

$49$ bits 的虛擬頁號可表示：

$$2^{49}$$

個不同的虛擬頁，因此單層頁表需要：

基礎設定與記憶體配置

• 矩陣規格：$250 \times 250 = 62,500$ 個 double 元素，每個占 8 bytes。
• 頁面容量：每頁大小 200 bytes，可容納 $\frac{200}{8} = 25$ 個元素。
• 起始頁面：a[0][0] 位址為 200，恰好為 Page 1 的起始位置。陣列整體占據 Page 1 至 Page 2500。
• 資料排列：以欄為主（Column-major）。每一欄有 250 個元素，連續占據 $\frac{250}{25} = 10$ 個頁面。
• 可用框頁：共 3 個 Page Frame。Frame 0 固定存放 Page 0（程式碼），僅剩 2 個 Frame 可供資料頁面做 LRU 置換。

---

(a) 詳解

1. 存取順序：外層為列 index $i$，內層為欄 index $j$。存取順序為 a[0][0], a[0][1], a[0][2], ...。
2. 頁面跳躍：因為陣列為 Column-major 儲存，固定 $i$ 時，相鄰 $j$ 的元素在記憶體中相隔一整欄（250 個元素 = 10 個頁面）。內迴圈每前進一步，存取的頁面號碼即增加 10。

核心觀念

本題綜合考查 fork()、Pthreads、程序記憶體隔離，以及程序間同步。

• fork() 會複製目前程序的位址空間。一般變數 value 在各程序中各自擁有一份，後續修改不會互相影響。
• Pthreads 建立的執行緒與原程序共享同一份位址空間，因此執行緒修改 value，同一程序的主執行緒可看見修改結果。
• pthread_join() 確保 runner 執行完畢後，主執行緒才繼續印出 value。
• waitpid() 只負責等待指定子程序結束，不會把子程序的變數值傳回父程序。
• 第一次 fork() 後，只有原始父程序會執行第二次 fork()，因此總共是 $3$ 個程序，不是 $4$ 個。

解題方法

程序流程如下：

原始父程序 P0：value = 11
├── 第一次 fork 的子程序 P1：value = 11
│   └── 執行緒將 value 減為 10，輸出 A: 10
└── 原始父程序 P0：value = 11
    ├── 第二次 fork 的子程序 P2：value = 11
    │   └── 執行緒將 value 減為 10，輸出 C: 10
    └── 原始父程序 P0：value = 11
        └── 等待 P1、P2 結束後，輸出 B: D: 11

逐一分析：

程序	執行緒操作	最後的 value	輸出
P1：第一次 fork() 的子程序	$11 \to 10$	$10$	A: 10
P2：第二次 fork() 的子程序	$11 \to 10$	$10$	C: 10
P0：原始父程序	沒有建立執行緒修改 value	$11$	B: D: 11

第一個子程序在第 10 行透過 &value 修改的是自己的 value：

$$value_{P1}: 11 \longrightarrow 10$$

原始父程序之後執行第二次 fork()，第二個子程序取得的是父程序當時的副本：

$$value_{P0}=11,\qquad value_{P2}=11$$

第二個子程序的執行緒只修改自己的副本：

$$value_{P2}: 11 \longrightarrow 10$$

因此不會改變原始父程序的 value：

$$value_{P0}=11$$

父程序最後先等待兩個子程序結束，再執行第 48 行，所以父程序輸出的數字一定是 $11$，且位於兩個子程序完成之後。

輸出順序

題目沒有指定 stdout 的緩衝模式與程序排程，因此完整字串的排列不唯一。

若採用考題常見的抽象方式，將同一程序的輸出視為一筆記錄，則兩個子程序的先後順序不受保證：

A: 10
C: 10
B: D: 11

或：

題幹前提

完整題幹給定：UNIX i-node 有 10 個直接區塊，以及 single、double、triple 三層間接區塊；指標大小為 8 bytes、區塊大小為 4 Kbytes。官方試題 PDF

以下採用 $1\text{ Kbyte}=1024\text{ bytes}$。

核心觀念

每個間接區塊只能存放區塊指標，因此一個間接區塊可容納的指標數為

$$N=\frac{\text{區塊大小}}{\text{指標大小}} =\frac{4096}{8}=512=2^9$$

因此：

• 直接區塊：直接指向資料區塊。
• single indirect：可指向 $N$ 個資料區塊。
• double indirect：可指向 $N^2$ 個資料區塊。
• triple indirect：可指向 $N^3$ 個資料區塊。

需區分「檔案的邏輯大小」與「實際配置的磁碟空間」：

• 邏輯大小是檔案實際包含的資料 bytes。
• 磁碟配置以區塊為單位；非空檔案即使只有 1 byte，也至少配置 1 個 4096-byte 區塊。

(a) 最小檔案大小

UNIX 允許建立空檔案。空檔案只需要 inode，不需要配置任何資料區塊，因此其邏輯檔案大小為

$$\boxed{0\text{ bytes}}$$

若題意限定「非空檔案」，則最小邏輯大小為 1 byte；但其實際配置空間為

$$\left\lceil\frac{1}{4096}\right\rceil\times4096 =4096\text{ bytes}$$

(b) 最大檔案大小

各層可容納的資料量如下：

核心觀念

本題評量作業系統中**磁碟排程演算法（Disk Scheduling Algorithms）**的運作機制與尋軌距離（Seek Distance / Total Head Movement）計算。

1. 基本參數設定：

   • 磁柱（Cylinders）範圍：$0 \sim 1023$（共 1024 個磁柱）。
   • 目前磁頭位置（Current Position）：$200$。
   • 前一次服務位置（Previous Position）：$125$。
   • 磁頭移動方向：由 $125 \to 200$，表示磁頭目前正朝**磁柱編號增加（往大號碼／向外/向內依定義，即遞增方向）**移動。
   • 待處理請求佇列（Pending Requests）：$50, 250, 800, 350, 400, 100, 600$。
   • 請求排序後為：$\{50, 100, 250, 350, 400, 600, 800\}$。

2. 各排程演算法定義：

   • FIFO (First-In, First-Out / FCFS)：按照請求抵達佇列的先後順序依序服務。
   • SSTF (Shortest Seek Time First)：每次挑選與當前磁頭位置距離最近（尋軌距離最小）的請求優先服務；若距離相同則依約定方向或抵達先後處理。
   • SCAN（電梯演算法）：磁頭沿目前方向持續移動並服務沿途請求，**必須移動至該方向的最外端邊界（$0$ 或 $1023$）**後，才反向移動並服務反向沿途的請求。
   • C-SCAN (Circular SCAN)：磁頭沿目前方向服務至最外端邊界（$1023$）後，直接折返至另一端邊界（$0$）（折返過程不服務請求），再沿原方向繼續服務其餘請求。
   • C-LOOK (Circular LOOK)：C-SCAN 的改良版，磁頭只需移動到該方向的最遠請求即可折返，折返時直接跳至另一端的最遠請求（不走到邊界 $0$ 與 $1023$）。

---

解題方法與步驟推導

(a) FIFO (First-In, First-Out)

服務順序即為題目給定佇列順序：
$200 \to 50 \to 250 \to 800 \to 350 \to 400 \to 100 \to 600$

各段移動距離計算：

1. $|50 - 200| = 150$
2. $|250 - 50| = 200$
3. $|800 - 250| = 550$
4. $|350 - 800| = 450$
5. $|400 - 350| = 50$
6. $|100 - 400| = 300$
7. $|600 - 100| = 500$

總移動距離：
$\text{Total Distance} = 150 + 200 + 550 + 450 + 50 + 300 + 500 = 2200\text{ 磁柱}$

---

(b) SSTF (Shortest Seek Time First)

從磁頭位置 $200$ 開始，每次選擇最近的請求：

1. 目前在 $200$，候選點距離：$|250-200|=50$ 最近 $\to$ 移至 $250$
2. 目前在 $250$，候選點距離：$|350-250|=100$ 最近 $\to$ 移至 $350$
3. 目前在 $350$，候選點距離：$|400-350|=50$ 最近 $\to$ 移至 $400$
4. 目前在 $400$，候選點距離：$|600-400|=200$（比較 $|100-400|=300$）$\to$ 移至 $600$
5. 目前在 $600$，候選點距離：$|800-600|=200$（比較 $|100-600|=500$）$\to$ 移至 $800$
6. 目前在 $800$，剩餘 $\{50, 100\}$，距離：$|100-800|=700$ 最近 $\to$ 移至 $100$
7. 目前在 $100$，剩餘 $\{50\}$ $\to$ 移至 $50$

服務路徑：
$200 \to 250 \to 350 \to 400 \to 600 \to 800 \to 100 \to 50$

總移動距離：
$\text{Total Distance} = (800 - 200) + (800 - 50) = 600 + 750 = 1350\text{ 磁柱}$

---

核心觀念

本題考查死結（deadlock）發生的四個必要條件，又稱 Coffman 四條件。死結是指一組行程彼此永久等待，導致任何行程都無法繼續執行。

死結發生必須同時滿足：

1. 互斥（Mutual Exclusion）
2. 持有並等待（Hold and Wait）
3. 不可剝奪（No Preemption）
4. 循環等待（Circular Wait）

可表示為：

$$\text{Deadlock} \Rightarrow M \land H \land N \land C$$

只要破壞其中任一條件，就能避免死結發生。

解題方法

題目問的是「死結發生的必要條件」，直接套用 Coffman 四條件，逐一說明其意義即可。

1. 互斥

至少有一項資源屬於不可共享資源，同一時間只能由一個行程使用。

例如：

• 印表機
• 磁帶機
• 某些鎖定中的檔案
• 互斥鎖

若所有資源都能被多個行程同時使用，行程便不會因資源被占用而互相阻塞，因此不會形成死結。

2. 持有並等待

一個行程已經持有至少一項資源，同時又等待取得其他資源。

例如，行程 $P_1$ 已持有資源 $R_1$，但還需要 $R_2$ 才能繼續執行：

$$P_1 \text{ 持有 } R_1,\qquad P_1 \text{ 等待 } R_2$$

若系統規定行程必須一次取得所有所需資源，或在要求新資源前先釋放手上的資源，就能破壞此條件。

3. 不可剝奪

行程已取得的資源不能被系統強制收回，只能由持有該資源的行程自行使用完畢後釋放。

例如，若行程 $P_1$ 持有 $R_1$，系統不能直接將 $R_1$ 剝奪並交給其他行程，$P_1$ 就可能一直占用 $R_1$。

(a) Confidentiality, Integrity, and Availability

觀念說明：
CIA 為資訊安全的三大核心目標（CIA Triad）：

1. 機密性（Confidentiality）：確保敏感資料僅能被經授權的使用者存取，防止資料洩漏給未授權的第三方。
2. 完整性（Integrity）：確保資料與系統在儲存與傳輸過程中未被未授權地篡改、刪除或偽造，維護資料的正確性與一致性。
3. 可用性（Availability）：確保經授權的使用者在需要時，能夠及時且可靠地存取系統、網路與資料服務，防止服務中斷（如抵禦 DDoS 攻擊）。

【答案】

• Confidentiality（機密性）：僅允許授權使用者讀取資料，防止未授權洩密。
• Integrity（完整性）：確保資料未經未授權的變更或破壞，維護資料正確性。
• Availability（可用性）：確保授權使用者隨時可順暢存取與使用系統服務。

---

(b) Botnet and Malware

觀念說明：

1. 惡意軟體（Malware）：為 Malicious Software 的簡稱，泛指任何旨在對電腦、伺服器、用戶端或網路造成損害、破壞、竊密或取得未授權存取的程式碼（如病毒 Virus、蠕蟲 Worm、木馬 Trojan、勒索軟體 Ransomware）。
2. 殭屍網路（Botnet）：由眾多受惡意軟體感染並受駭客（Botmaster）遠端控制的裝置（Bots/Zombies）所組成的網路，常被用於發動大規模 DDoS 攻擊或發送垃圾郵件。

【答案】

• Malware：旨在破壞、竊密或非法存取系統的所有惡意程式總稱。
• Botnet：由受駭客遠端操控的廣大受感染裝置（殭屍電腦）所構成的網路，常用於發動分散式阻斷服務（DDoS）攻擊。

---

(c) Digital Envelope

觀念說明：
**數位信封（Digital Envelope）**是一種結合「對稱式加密」的高效能與「非對稱式加密」金鑰管理優點的混合加密技術（Hybrid Encryption）。

運作機制：

1. 傳送端加密：
   • 傳送方產生一把一次性的對稱金鑰（Session Key）。
   • 使用 Session Key 對明文（Plaintext）進行對稱加密，生成密文（Ciphertext）。