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

核心觀念

本題考查兩種 CPU 排程：

• 非搶占式優先權排程（nonpreemptive priority scheduling）：優先權數字越小，優先權越高。程序一旦取得 CPU，必須執行至完成。
• 最短工作優先（Shortest-Job-First, SJF）：優先選擇 CPU burst time 最短的程序。

相關公式如下：

$$\text{Completion Time}=\text{Start Time}+\text{Burst Time}$$ $$\text{Waiting Time}=\text{Start Time}-\text{Arrival Time}$$

本題所有程序均於時間 $0$ 到達，因此：

$$\text{Waiting Time}=\text{Start Time}$$

---

（a）非搶占式優先權排程下，$P_1$ 的完成時間

優先權數字越小代表優先權越高，因此排程順序為：

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

甘特圖如下：

時間區間	執行程序
$0\sim1$	$P_2$
$1\sim6$	$P_5$
$6\sim16$	$P_1$
$16\sim18$	$P_3$
$18\sim19$	$P_4$

$P_1$ 在時間 $6$ 開始執行，CPU burst time 為 $10$，所以：

$$\text{Completion Time}_{P_1}=6+10=16$$

---

（b）SJF 排程下的平均等待時間

依照 CPU burst time 由短至長排序：

核心觀念

頁表的每一個 entry 對應一個虛擬頁，內容通常記錄該虛擬頁所對應的實體頁框，以及有效位、存取權限等控制資訊。

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

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

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

解題方法

64 位元虛擬位址可表示的虛擬位址空間共有：

$$2^{64}\text{ bytes}$$

每頁大小為 $2^{15}$ bytes，所以虛擬頁數為：

$$\frac{2^{64}}{2^{15}}=2^{49}$$

每個虛擬頁需要一個頁表 entry，因此頁表需要：

$$\boxed{2^{49}\text{ entries}}$$

約為 $5.63\times 10^{14}$ 個 entries。

題目給出的 32 位元實體位址用來決定實體頁框數：

核心觀念

本題結合下列概念：

• 分頁系統：頁面大小為 $200$ bytes。
• 每個 double 佔 $8$ bytes，因此一頁可容納
  $\frac{200}{8}=25$
  個 double。
• LRU（Least Recently Used）頁面置換。
• 陣列的儲存順序會決定連續存取是否落在相鄰頁面。
• 程式指令位於 page 0，且每次指令擷取都會存取 page 0，因此 page 0 會持續留在 frame 0。實際可供陣列資料使用的只有另外兩個 frame。

解題方法與頁面配置

a[0][0] 位於 location $200$，正好是 page 1 的起始位置。

因為陣列採用 column-major 儲存，元素 a[i][j] 前面共有 $250j+i$ 個元素，因此其位址為

$$\operatorname{addr}(a[i][j]) =200+8(250j+i).$$

每頁可放 $25$ 個元素，所以 a[i][j] 所在的頁面為

$$P(i,j) =1+\left\lfloor \frac{250j+i}{25}\right\rfloor.$$

由於 $250=10\times25$，可化為

$$P(i,j)=1+10j+\left\lfloor\frac{i}{25}\right\rfloor.$$

因此，每一個 column 佔有：

$$\frac{250\times8}{200}=10$$

個頁面，而且每一頁包含該 column 中連續的 $25$ 個元素。

---

（a）先固定 $i$，再掃描 $j$

for (int i = 0; i < 250; i++)
    for (int j = 0; j < 250; j++)
        a[i][j] = 0;

固定某個 $i$ 時，$j$ 由 $0$ 增加至 $249$。此時

$$P(i,j)=1+10j+\left\lfloor\frac{i}{25}\right\rfloor.$$

當 $j$ 每增加 $1$，頁面號碼增加 $10$，所以同一個內層迴圈會依序存取 $250$ 個不同頁面：

核心觀念

1. fork() 行程複製：呼叫 fork() 會建立獨立的子行程（Child Process），複製獨立的記憶體位址空間（Address Space），子行程對變數的修改不會影響父行程。
2. pthread_create() 執行緒共享：同一個行程內的執行緒（Thread）共享相同的記憶體位址空間，因此 runner 執行緒對 value 的修改會反映在該行程的 value 上。
3. waitpid() 同步順序：父行程呼叫 waitpid(-1, &status, 0) 會暫停執行直到子行程結束，因此輸出順序由最深層的子行程開始由內向外執行。

---

各行程推導過程

初始主行程設為 $P_0$，變數 $value = 11$。

1. 行程 $P_0$（最外層父行程）

• 執行第 17 行 fork() 產生子行程 $P_1$。
• 進入 if (pid > 0)（第 18 行），呼叫 waitpid 阻塞等待 $P_1$ 結束。
• $P_1$ 結束後，執行第 21 行 printf("A=%d\n", value--)。
• 由於 $P_0$ 的 $value$ 未受子行程影響仍為 11，後綴遞減 value-- 印出 A=11。

2. 行程 $P_1$（$P_0$ 之子行程）

• 繼承 $value = 11$。
• 執行第 25 行 fork() 產生子行程 $P_2$。
• 進入 if (pid > 0)（第 26 行），呼叫 waitpid 阻塞等待 $P_2$ 結束。
• $P_2$ 結束後，執行第 30 行 printf("B=%d\n", --value)。
• 前綴遞減 --value 將 $value$ 由 11 減至 10，印出 B=10。

核心觀念

i-node 以不同層級的指標指向檔案資料區塊：

• 直接指標：直接指向資料區塊。
• 單重間接指標：指向一個存放指標的區塊。
• 雙重間接指標：指向「存放單重間接指標的區塊」。
• 三重間接指標：再多一層指標區塊。

檔案的邏輯大小只計算資料內容，不計算間接指標區塊所占的額外空間。

基本計算

區塊大小為

$$B=4\text{ KB}=4\times1024=4096\text{ bytes}$$

每個間接區塊可存放的指標數為

$$P=\frac{4096}{8}=512$$

(a) 最小檔案大小

UNIX 允許建立空檔案。空檔案不需要配置任何資料區塊，其檔案長度可為

$$0\text{ bytes}$$

若限定為非空檔案，最小邏輯長度是 $1$ byte，但磁碟配置空間會使用一個 $4096$-byte 資料區塊。本題以檔案的邏輯大小為準。

(b) 最大檔案大小

各種指標所能涵蓋的資料區塊數如下：

指標類型	可指向的資料區塊數	可存放資料量
10 個直接指標	$10$	$10\times4096$

核心觀念

本題考查磁碟排程演算法，以及磁頭移動距離的計算。

磁頭總移動距離為每一段移動距離的總和：

$$D=\sum_{i=1}^{n}\left|p_i-p_{i-1}\right|$$

其中 $p_0=200$ 為目前磁頭位置。

目前位置為 $200$，前一個服務位置為 $125$，因此磁頭原本是往柱面編號增加的方向移動。故 SCAN、LOOK、C-SCAN、C-LOOK 的初始方向皆為由小柱面往大柱面。

待處理請求排序如下：

$$50,\ 100,\ 250,\ 350,\ 400,\ 500,\ 550,\ 600,\ 800$$

題目雖以 FIFO 順序列出請求，但本題所問的五種演算法都不依照 FIFO 服務。

---

(a) SSTF

SSTF（Shortest Seek Time First）每次選擇距離目前磁頭位置最近的請求。

服務順序如下：

$$200\rightarrow250\rightarrow350\rightarrow400\rightarrow500 \rightarrow550\rightarrow600\rightarrow800\rightarrow100\rightarrow50$$

各段移動距離為：

$$\begin{aligned} D &=(250-200)+(350-250)+(400-350)+(500-400)\\ &\quad +(550-500)+(600-550)+(800-600)+(800-100)+(100-50)\\ &=50+100+50+100+50+50+200+700+50\\ &=\boxed{1350} \end{aligned}$$

因此：

$$\boxed{\text{SSTF}=1350\text{ cylinders}}$$

---

(b) SCAN

SCAN 又稱電梯演算法。磁頭先沿目前方向移動，直到磁碟實體端點 $1023$，再反向服務請求。

服務順序為：

$$200\rightarrow250\rightarrow350\rightarrow400\rightarrow500 \rightarrow550\rightarrow600\rightarrow800\rightarrow1023 \rightarrow100\rightarrow50$$

磁頭先由 $200$ 移動到最右端 $1023$：

$$1023-200=823$$

再由 $1023$ 反向移動至最左側尚未處理的請求 $50$：

$$1023-50=973$$

因此：

$$D=(1023-200)+(1023-50)=823+973=\boxed{1796}$$

所以：

$$\boxed{\text{SCAN}=1796\text{ cylinders}}$$

---

(c) LOOK

LOOK 與 SCAN 的服務方向相同，但不會特別移動到磁碟實體端點；當目前方向已沒有請求時，立即反向。

磁頭往增加方向服務至最大請求 $800$，再反向服務 $100$ 與 $50$：

$$200\rightarrow250\rightarrow350\rightarrow400\rightarrow500 \rightarrow550\rightarrow600\rightarrow800\rightarrow100\rightarrow50$$

向右移動距離：

$$800-200=600$$

反向由 $800$ 移動至 $50$：

$$800-50=750$$

總距離為：

$$D=(800-200)+(800-50)=600+750=\boxed{1350}$$

因此：

核心觀念

Kruskal 演算法用來求最小生成樹（Minimum Spanning Tree, MST），核心規則如下：

1. 將所有邊依權重由小到大排序。
2. 依序考慮每條邊。
3. 若加入該邊不會形成環，便加入生成樹。
4. 若會形成環，便捨棄該邊。
5. 若圖有 $|V|$ 個頂點，生成樹最後必須包含 $|V|-1$ 條邊。

題圖文字化後缺少部分頂點端點標示，以下依原圖為六個頂點 $A$–$F$ 解讀。

解題方法

圖中所有邊的權重排序為

$$1,\ 2,\ 3,\ 4,\ 5,\ 5,\ 6,\ 7,\ 9$$

依 Kruskal 演算法處理：

核心觀念

Huffman 演算法使用貪婪法建立最佳前綴碼：

1. 將每個原始節點依權重放入最小優先佇列。
2. 每次取出權重最小的兩個節點合併。
3. 合併節點的權重為兩子節點權重總和，再放回優先佇列。
4. 持續合併至只剩根節點。

題面文字版未保留字母與權重的逐項對齊，以下採常見配對：

$$A=6,\ B=9,\ C=12,\ D=14,\ E=18,\ F=24,\ G=27,\ H=29,\ I=35,\ J=45$$

解題方法

依序合併最小的兩個節點：

步驟	合併	新節點權重	合併後的優先佇列
1	$A(6)+B(9)$	$AB(15)$	$12,14,15,18,24,27,29,35,45$
2	$C(12)+D(14)$	$CD(26)$	$15,18,24,26,27,29,35,45$
3	$AB(15)+E(18)$	$ABE(33)$	$24,26,27,29,33,35,45$
4	$F(24)+CD(26)$	$FCD(50)$	$27,29,33,35,45,50$
5	$G(27)+H(29)$	$GH(56)$	$33,35,45,50,56$
6	$ABE(33)+I(35)$	$ABEI(68)$	$45,50,56,68$
7	$J(45)+FCD(50)$	$JFCD(95)$	$56,68,95$
8	$GH(56)+ABEI(68)$	$GHABEI(124)$	$95,124$
9	$JFCD(95)+GHABEI(124)$	$219$	完成

固定左子樹標記為 $0$、右子樹標記為 $1$，且每次將較小權重放在左側，得到 Huffman 樹：

核心觀念

本題比較五種排序法的平均時間複雜度。判斷時要掌握：

• 是否需要比較元素大小。
• 每一輪或每一層處理的元素數量。
• 遞迴層數或重複掃描次數。
• 非比較排序是否依賴位數 $k_1$ 與桶數 $k_2$。

其中：

• $n$：輸入資料筆數。
• $k_1$：每個鍵值的最大位數。
• $k_2$：桶的數量。

---

解題方法與各排序法分析

(a) Selection Sort：$O(n^2)$

Selection sort 每一輪從尚未排序的部分尋找最小值。

第 $i$ 輪需要比較約 $n-i$ 次，因此總比較次數為

$$(n-1)+(n-2)+\cdots+1 = \frac{n(n-1)}{2}$$

所以不論輸入資料原本是否接近排序完成，主要成本都來自完整掃描未排序區域，平均時間複雜度為

$$\boxed{O(n^2)}$$

---

(b) Merge Sort：$O(n\log n)$

Merge sort 將資料不斷分成兩半，直到每個子陣列只剩一個元素，再逐層合併。

• 分割深度：約為 $\log n$ 層。
• 每一層合併所有元素一次，成本為 $O(n)$。

因此總時間為

$$O(n)\times O(\log n) = \boxed{O(n\log n)}$$

合併時的比較次數會因輸入內容略有不同，但每層仍須處理全部元素，因此平均複雜度不變。

---

(c) Heap Sort：$O(n\log n)$

Heap sort 通常分成兩階段：

1. 建立 max-heap，成本為 $O(n)$。
2. 重複移除堆頂元素並重新調整 heap。

第 $i$ 次移除元素時，heap 的高度最多為 $O(\log n)$，共需移除 $n-1$ 次，因此：

$$O(n)+ (n-1)O(\log n) = O(n\log n)$$

所以平均時間複雜度為

$$\boxed{O(n\log n)}$$

Heap sort 的最好、平均、最壞時間複雜度皆為 $O(n\log n)$。

---

(d) Radix Sort：$O(k_1(n+k_2))$

Radix sort 依序處理每一個位數。若每一位使用 counting sort 或類似穩定的桶式排序，處理一位的成本為

$$O(n+k_2)$$

原因是：

• 掃描 $n$ 筆資料：$O(n)$。
• 處理 $k_2$ 個桶或計數位置：$O(k_2)$。

核心觀念

本題考查遞迴函數的展開與分層計算。Ackermann 函數依照 $m$ 的值逐層成長，計算時可先推導較低層的通式：

$$A(0,n)=n+1$$

再利用遞迴定義計算 $A(1,n)$、$A(2,n)$，最後求得 $A(3,2)$ 與 $A(2,4)$。

---

解題方法

1. 推導 $A(1,n)$

當 $n=0$ 時：

$$A(1,0)=A(0,1)=2$$

當 $n>0$ 時：

$$A(1,n)=A(0,A(1,n-1))$$

由 $A(0,x)=x+1$ 可得：

$$A(1,n)=A(1,n-1)+1$$

因此：

$$A(1,n)=n+2$$

---

2. 推導 $A(2,n)$

當 $n=0$ 時：

$$A(2,0)=A(1,1)=1+2=3$$

當 $n>0$ 時：

$$A(2,n)=A(1,A(2,n-1))$$

代入 $A(1,x)=x+2$：

$$A(2,n)=A(2,n-1)+2$$

所以：

$$A(2,n)=2n+3$$

因此：

$$A(2,4)=2(4)+3=11$$

---

3. 計算 $A(3,2)$

先求 $A(3,0)$：