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

(a)
觀念：記憶體中同時存在的程序（process）數量稱為多工度（degree of multiprogramming）。

【答案】multiprogramming

---

(b)
觀念：分頁系統中，若頁面內容被修改，頁表中的 modify bit 會被設為 1，該位元又稱為髒位元（dirty bit），用於分頁替換時判斷是否需要寫回次級儲存設備。

【答案】dirty

---

(c)
觀念：分派器（dispatcher）是 CPU 排程功能中的模組，負責將 CPU 控制權交給被 CPU 排程器選中的程序，並執行上下文切換（context switch）與切換至使用者模式。

【答案】dispatcher

---

(d)
觀念：解決臨界區段問題（critical-section problem）的演算法必須同時滿足三大條件：互斥（mutual exclusion）、進行（progress）與有限等待（bounded waiting）。

【答案】critical-section（或 critical section）

---

核心觀念

「非自願交出 CPU」指的是 preemption（搶占）：執行中的 process 並未主動呼叫 yield、等待 I/O 或結束，而是被時鐘中斷、排程器或核心管理機制強制暫停。

若該 process 仍可繼續執行，狀態轉移為：

$$\text{Running} \rightarrow \text{Ready}$$

作業系統會先將暫存器、程式計數器等執行環境存入 PCB，再把它放入 Ready Queue（就緒佇列）；多核心系統通常是放入某一 CPU 的 per-CPU run queue。

(a) 解題方法與三種案例

案例	觸發原因	目前 process 的狀態轉移	放入的佇列
1. 時間片耗盡	Timer interrupt 發生，Round Robin 等搶占式排程的 time quantum 用完	$\text{Running}\rightarrow\text{Ready}$	Ready Queue
2. 更高優先權的 process 變成可執行	新 process 到達、建立，或其他事件使高優先權 process 進入就緒狀態	$\text{Running}\rightarrow\text{Ready}$	Ready Queue
3. 多核心排程器強制重新分配 CPU	負載平衡、CPU core 被停用、強制 task migration 等	$\text{Running}\rightarrow\text{Ready}$	原 CPU 或目標 CPU 的 Ready Queue

第 2 種情況常由 I/O 完成中斷引起。被喚醒的 process 會從等待佇列進入 Ready Queue；若其優先權高於目前執行中的 process，排程器便會搶占目前 process。此時：

• 被喚醒的 process：等待佇列 $\rightarrow$ Ready Queue
• 原本正在執行的 process：Running $\rightarrow$ Ready Queue

常見陷阱

目前 process 主動提出 I/O、等待 semaphore、呼叫 sleep，屬於阻塞：

$$\text{Running}\rightarrow\text{Blocked}$$

此時應放入相應的 I/O 或事件等待佇列，不是非自願搶占。若 process 已執行完畢，則進入 Terminated 狀態，也不會放入任何就緒佇列。

第 3 題

(a) 處理死結問題的三種常見方法

核心觀念

死結（deadlock）是指一組行程彼此等待對方所持有的資源，導致所有行程都無法繼續執行。

死結成立時，通常同時具備以下四個必要條件：

1. 互斥（mutual exclusion）：資源一次只能由一個行程使用。
2. 持有並等待（hold and wait）：行程持有部分資源，同時等待其他資源。
3. 不可剝奪（no preemption）：資源不能被系統強制取回，只能由行程主動釋放。
4. 循環等待（circular wait）：存在行程等待鏈，形成環狀依賴。

處理死結的三種標準方法如下。

1. 死結預防（deadlock prevention）

預先設計資源分配規則，使上述四個必要條件至少有一個不成立，從根本上避免死結。

常見做法包括：

• 要求行程一次取得所有需要的資源，破壞「持有並等待」。
• 允許系統剝奪行程已持有的資源，破壞「不可剝奪」。
• 對所有資源訂定全域順序，行程只能依固定順序取得資源，破壞「循環等待」。
• 將不可共享的資源改為可共享，破壞「互斥」，但並非所有資源都能如此處理。

優點是保證不發生死結；缺點是資源使用效率可能降低，且可能造成長時間等待。

2. 死結避免（deadlock avoidance）

允許系統具備形成死結的可能性，但每次分配資源前，先判斷分配後是否仍處於安全狀態（safe state）。

安全狀態表示：存在某種行程執行順序，使所有行程都能取得所需資源並順利完成。若某次資源請求會使系統進入不安全狀態，系統便暫緩該請求。

典型方法是 銀行家演算法（Banker’s algorithm）。它需要事先知道各行程的最大資源需求，再根據：

• Available：目前可用資源
• Max：各行程的最大需求
• Allocation：目前已分配資源
• Need = Max - Allocation：尚需資源

判斷資源分配後是否仍存在安全序列。

優點是資源利用率通常比預防法高；缺點是需要知道最大需求，且每次分配前都要進行額外檢查。

3. 死結偵測與復原（deadlock detection and recovery）

系統先允許資源自由分配，不事先阻止死結；當系統定期執行死結偵測演算法，確認已形成死結後，再採取復原措施。

偵測方式包括：

• 單一實例資源：可利用等待圖（wait-for graph）檢查是否存在循環。
• 多重實例資源：可使用類似銀行家演算法的死結偵測程序。

發現死結後，可採取：

• 終止一個或多個行程。
• 強制剝奪部分資源。
• 回復行程至先前的檢查點。
• 依優先權、已執行時間、剩餘需求等條件選擇犧牲行程。

優點是平時不需支付大量預防或避免成本；缺點是死結發生後才處理，可能造成資料遺失、行程終止與復原成本。

解題技巧

題目要求「三種常見方法」時，最標準的三項是：

1. Deadlock prevention
2. Deadlock avoidance
3. Deadlock detection and recovery

「忽略死結（ignore the problem）」也是部分作業系統採用的實務策略，但通常不列入這題要求的標準三大類。作答時應優先寫出上述三項，並為每項補上核心作法與優缺點。

---

(b) Copy-on-write

核心觀念

本題考查磁碟壞區（bad block／bad sector）的處理方式。磁碟在低階格式化時會保留部分備用區塊（spare sectors），並由磁碟控制器維護壞區清單。當某個實體磁區損壞時，控制器將原本的邏輯區塊重新導向至備用磁區，此機制稱為 sector sparing，也稱為 sector forwarding。作業系統仍使用原本的邏輯區塊編號，無須知道實際的實體位置。Bad Blocks 教材內容

解題方法

題目要求列出交易流程，因此依照「發出讀取要求 → 偵測錯誤 → 建立替代 → 後續重新導向」的時間順序作答。以邏輯區塊 $87$ 為例，五個步驟如下：

1. 作業系統要求讀取邏輯區塊 $87$

   作業系統發出讀取請求，指定要存取邏輯區塊 $87$。此時作業系統只使用邏輯位址，不直接處理磁碟的實體磁區位置。

2. 控制器計算 ECC，偵測出磁區損壞

   磁碟控制器讀取該磁區後，重新計算錯誤更正碼（Error-Correcting Code, ECC），並與磁區中原本儲存的 ECC 比對。若比對結果顯示資料已損壞，控制器便判定該磁區為壞區。

3. 控制器將壞區資訊回報給作業系統

(a) 題目詳解

核心觀念

本題測驗 C 語言的**運算子優先順序（Operator Precedence）與結合性（Associativity）以及位元運算子（Bitwise Operators）**的二進位數值計算。

在 C 語言中，相關運算子的優先順序由高至低依序為：

1. 一元位元 NOT（Bitwise NOT）：~（單目運算子，優先權最高）
2. 位移運算子（Bitwise Shift）：<<、>>
3. 位元 AND（Bitwise AND）：&
4. 位元 XOR（Bitwise XOR）：^
5. 位元 OR（Bitwise OR）：|（優先權最低）

運算式 x ^ y & ~x | y << 2 依優先權加上括號後的實際執行順序為：
$(x \oplus (y \ \& \ (\sim x))) \mid (y \ll 2)$

---

解題方法與逐步推導

給定變數初始值：

• $x = 12 = (0000\,1100)_2$
• $y = 25 = (0001\,1001)_2$

步驟 1：計算優先權最高的子運算式 ~x 與 y << 2

• y << 2：將 $25$ 左移 $2$ 位元（相當於 $25 \times 2^2$）：
  $25 \ll 2 = 100 = (0110\,0100)_2$
• ~x：對 $x$ 進行逐位元取反。在 32 位元有號整數中：
  $\sim (0000\,0000\dots 0000\,1100)_2 = (1111\,1111\dots 1111\,0011)_2$

步驟 2：計算位元 AND 運算 y & ~x

• $y \ \& \ (\sim x)$ 的本質為「保留 $y$ 中 $x$ 對應位元為 $0$ 的位元，清除 $x$ 對應位元為 $1$ 的位元」：

$$\begin{aligned} y &= (0001\,1001)_2 \\ \sim x &= (\dots 1111\,0011)_2 \\ \hline y \ \& \ (\sim x) &= (0001\,0001)_2 = 16 + 1 = 17 \end{aligned}$$

步驟 3：計算位元 XOR 運算 x ^ (y & ~x)

• 將 $x = 12$ 與 $17$ 進行互斥或（XOR）運算（相同為 0，相異為 1）：

$$\begin{aligned} x &= (0000\,1100)_2 \\ y \ \& \ (\sim x) &= (0001\,0001)_2 \\ \hline x \oplus (y \ \& \ (\sim x)) &= (0001\,1101)_2 = 16 + 8 + 4 + 1 = 29 \end{aligned}$$

步驟 4：計算位元 OR 運算 29 | 100

• 將步驟 3 的結果 $29$ 與步驟 1 的結果 $100$ 進行位元 OR 運算：

$$\begin{aligned} 29 &= (0001\,1101)_2 \\ 100 &= (0110\,0100)_2 \\ \hline 29 \mid 100 &= (0111\,1101)_2 = 64 + 32 + 16 + 8 + 4 + 1 = 125 \end{aligned}$$

因此，printf 印出之數值為 125。

---

解題技巧與常見陷阱

1. 優先順序口訣：位元邏輯運算子的優先權為 「AND 先於 XOR，XOR 先於 OR」（記憶法：類似邏輯/代數運算中「乘法先於加法」，& $\to$ ^ $\to$ |）。

核心觀念

二元樹三種走訪順序定義如下：

• Inorder（中序）：左子樹 $\rightarrow$ 根 $\rightarrow$ 右子樹
• Postorder（後序）：左子樹 $\rightarrow$ 右子樹 $\rightarrow$ 根
• Preorder（前序）：根 $\rightarrow$ 左子樹 $\rightarrow$ 右子樹

後序走訪的最後一個節點必為整棵樹的根。利用根在中序序列中的位置，可將左右子樹分開，再遞迴判斷各子樹的根。

解題方法

已知：

$$\text{Inorder}=ABCDEFGHIJ$$ $$\text{Postorder}=ABDCGIHJFE$$

1. 找出整棵樹的根

後序序列最後一個節點為 $E$，因此整棵樹的根是 $E$。

在中序序列中，$E$ 將節點分成：

• 左子樹：$ABCD$
• 右子樹：$FGHIJ$

因此後序序列可分成：

• 左子樹後序：$ABDC$
• 右子樹後序：$GIHJF$
• 根：$E$

2. 建立左子樹

左子樹的中序與後序分別為：

$$\text{Inorder}=ABCD$$ $$\text{Postorder}=ABDC$$

後序最後一個節點為 $C$，所以左子樹的根是 $C$。

在中序 $ABCD$ 中，$C$ 左側為 $AB$，右側為 $D$：

• $C$ 的左子樹：中序 $AB$，後序 $AB$
• $C$ 的右子樹：節點 $D$

對於中序 $AB$、後序 $AB$：

• 後序最後一個節點 $B$ 為根
• $A$ 為 $B$ 的左子節點

所以左子樹的前序為：

$$C \rightarrow B \rightarrow A \rightarrow D$$

3. 建立右子樹

右子樹的中序與後序分別為：

$$\text{Inorder}=FGHIJ$$

核心觀念

本題考查雜湊表的「雙重雜湊」（double hashing）碰撞處理法。

對每個鍵值 $k$，第 $i$ 次探測的位置為：

$$H_i(k)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod M,\qquad i=0,1,2,\ldots$$

其中：

$$h_1(k)=k\bmod 11$$ $$h_2(k)=7-(k\bmod 7)$$

第 $0$ 次探測先檢查主要雜湊位置 $h_1(k)$；若發生碰撞，便依照 $h_2(k)$ 的步距繼續探測。

---

解題方法與逐一插入

1. 插入鍵值 $11$

$$h_1(11)=11\bmod 11=0$$ $$h_2(11)=7-(11\bmod 7)=7-4=3$$

第 $0$ 次探測位置：

$$H_0(11)=0$$

位置 $0$ 為空，因此將 $11$ 放入位置 $0$。

---

2. 插入鍵值 $33$

$$h_1(33)=33\bmod 11=0$$ $$h_2(33)=7-(33\bmod 7)=7-5=2$$

第 $0$ 次探測：

$$H_0(33)=0$$

位置 $0$ 已有 $11$，發生碰撞。

第 $1$ 次探測：

$$H_1(33)=(0+1\cdot 2)\bmod 11=2$$

位置 $2$ 為空，因此將 $33$ 放入位置 $2$。

---

3. 插入鍵值 $66$

$$h_1(66)=66\bmod 11=0$$ $$h_2(66)=7-(66\bmod 7)=7-3=4$$

第 $0$ 次探測：

$$H_0(66)=0$$

位置 $0$ 已被 $11$ 佔用。

第 $1$ 次探測：

$$H_1(66)=(0+1\cdot 4)\bmod 11=4$$

位置 $4$ 為空，因此將 $66$ 放入位置 $4$。

---

4. 插入鍵值 $7$

$$h_1(7)=7\bmod 11=7$$

核心觀念

本題考查以 Prim's algorithm 求無向加權圖的 minimum spanning tree（MST）。

• 鄰接矩陣中的非零非對角線元素代表一條邊及其權重；$0$ 代表沒有邊。
• Prim's algorithm 維護一個已加入樹中的頂點集合 $S$。
• 每一步都從所有「一端在 $S$、另一端不在 $S$」的邊中，選擇權重最小者加入 MST。
• 這是利用 minimum cut property：跨越切割 $(S,V-S)$ 的最小權重邊，可安全加入某棵 MST。
• 本圖有 $6$ 個頂點，因此 MST 必須包含 $6-1=5$ 條邊。

解題方法

由鄰接矩陣可得：

$$AB=2,\ AC=4,\ AE=5,\ BC=1,\ BD=9,$$ $$BF=7,\ CE=6,\ CF=10,\ DF=8,\ EF=3$$

從 $A$ 開始，令初始集合為 $S=\{A\}$。

步驟	當前頂點集合 $S$	可選的跨集合邊	選入 MST 的邊
1	$\{A\}$	$AB(2), AC(4), AE(5)$	$AB(2)$
2	$\{A,B\}$	$BC(1), AC(4), AE(5), BF(7), BD(9)$	$BC(1)$
3	$\{A,B,C\}$	$AE(5), CE(6), BF(7), BD(9), CF(10)$	$AE(5)$
4	$\{A,B,C,E\}$	$EF(3), BF(7), CF(10), BD(9)$	$EF(3)$
5	$\{A,B,C,E,F\}$	$DF(8), BD(9)$	$DF(8)$

因此，邊加入 MST 的順序為：

$$AB(2)\ \rightarrow\ BC(1)\ \rightarrow\ AE(5)\ \rightarrow\ EF(3)\ \rightarrow\ DF(8)$$

若只以權重表示，順序為：

核心觀念

題目要求的是各排序法在「最壞情況」下的時間複雜度。對輸入規模為 $n$ 的資料，最壞情況表示在所有可能輸入中，執行時間最長的情形。

分析重點是：

• 每一輪或每一層需要處理多少元素。
• 演算法總共需要執行多少輪。
• 分治法可用遞迴式表示：
  $T(n)=aT\left(\frac{n}{b}\right)+f(n)$

---

解題方法與各小題分析

(a) Bubble sort

Bubble sort 會反覆比較相鄰元素，將較大的元素逐步交換至右側。

最壞情況通常是資料完全反向排列。第 1 輪約需比較 $n-1$ 次，第 2 輪約需比較 $n-2$ 次，依此類推，因此總比較次數為

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

即使實作中加入「本輪沒有交換便提前結束」的最佳化，反向排列仍會發生大量交換，因此最壞情況不變。

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

---

(b) Insertion sort

Insertion sort 依序將目前元素插入前方已排序的區段。

在最壞情況下，資料完全反向排列。處理第 $i$ 個元素時，最多需要與前方 $i$ 個元素比較，並將這些元素向右移動，因此總操作次數約為

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

所以最壞情況時間複雜度為

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

---

(c) Quick sort

Quick sort 每次選擇一個 pivot，進行 partition。一次 partition 需要掃描目前區段中的元素，因此成本為 $\Theta(n)$。

最壞情況發生在每次 pivot 都是目前區段的最小值或最大值，使得分割後一邊有 $n-1$ 個元素，另一邊為空集合。遞迴式為

$$T(n)=T(n-1)+\Theta(n)$$

展開後：

$$T(n)=\Theta(n)+\Theta(n-1)+\cdots+\Theta(1) =\Theta(n^2)$$

因此：

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

Quick sort 平均情況通常為 $O(n\log n)$，但題目問的是最壞情況，答案仍為 $O(n^2)$。

---

(d) Merge sort