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

(1)
運算與轉換步驟
前序運算式為：+ + 18 * 17 16 * + * 15 14 13 12

1. 由右至左掃描並依運算符號結合運算元：

   • * 15 14 $\rightarrow (15 \times 14) = 210$
   • + (* 15 14) 13 $\rightarrow (15 \times 14 + 13) = 223$
   • * (+ ...) 12 $\rightarrow ((15 \times 14 + 13) \times 12) = 2676$
   • * 17 16 $\rightarrow (17 \times 16) = 272$
   • + 18 (* 17 16) $\rightarrow (18 + 17 \times 16) = 290$
   • + (+ ...) (* ...) $\rightarrow (18 + 17 \times 16) + ((15 \times 14 + 13) \times 12)$

2. 計算結果：

   • $290 + 2676 = 2966$

【答案】

• 中序運算式：$18 + 17 \times 16 + (15 \times 14 + 13) \times 12$ （或可寫為 $(18 + (17 \times 16)) + (((15 \times 14) + 13) \times 12)$）
• 計算結果：$2966$

---

(2)
觀念與時間複雜度推導

1. 簡單均勻雜湊（Simple Uniform Hashing）：指任何給定的元素被等概率（$\frac{1}{m}$）獨立雜湊到雜湊表 $m$ 個槽（slots）中任何一個槽的假設，且各元素的雜湊映射彼此獨立。
2. 不成功搜尋之期望時間：採用鏈結法（Chaining）處理碰撞時，不成功搜尋必須尋訪該槽位整個串列至末端。
   • 定義負載因子（Load Factor）為 $\alpha = \frac{n}{m}$，即每個槽位的平均鏈結長度。
   • 搜尋所需時間包含：計算雜湊值與存取槽位的常數時間 $O(1)$，以及尋訪平均長度為 $\alpha$ 的串列時間。

【答案】

• 簡單均勻雜湊定義：任何元素映射至雜湊表 $m$ 個槽中任意槽位的機率皆相等（均為 $\frac{1}{m}$），且個別元素的雜湊結果互相獨立。
• 不成功搜尋之期望時間：$\Theta(1 + \alpha)$ 或 $\Theta\left(1 + \frac{n}{m}\right)$

---

(3)
紅黑樹性質需求
除了「每個節點非紅即黑」之外，二元搜尋樹必須同時滿足以下 4 項紅黑樹性質：

1. 根節點性質（Root Property）：根節點（Root）必須為黑色。
2. 葉節點性質（Leaf Property）：所有外部節點（NIL 葉節點）必須為黑色。
3. 紅節點性質（Red Property）：若一節點為紅色，則其兩個子節點必須均為黑色（即不可有連續相連的紅色節點）。

核心觀念

本題考查強連通分量、B-tree 的磁碟存取效率、B⁺-tree 與 B*-tree 的差異、binomial heap 的性質，以及 Fibonacci heap 的 decrease-key 操作。

• 強連通分量：有向圖中一個極大的頂點集合，集合內任兩頂點都能彼此到達。極大表示無法再加入其他頂點而仍維持此性質。
• B-tree 與磁碟存取：B-tree 的節點可設計成與磁碟區塊大小相近，且每個節點能存放許多鍵值，因此分支度高、樹高低。查詢時走訪較少節點，便能減少磁碟區塊讀取次數。
• B⁺-tree 與 B-tree*：B⁺-tree 的資料記錄或記錄指標集中在葉節點，內部節點主要存索引鍵，葉節點通常彼此連結。B*-tree 的重點是提高節點占用率：插入造成節點溢位時，先嘗試與兄弟節點重新分配；若兄弟節點也滿了，通常將兩個節點的內容分成三個節點，使節點至少約有三分之二滿。
• Binomial heap：由多棵 binomial tree 組成；每棵樹符合 heap-order，且每種階數至多有一棵樹。
• Fibonacci heap 的減鍵：若節點減鍵後小於父節點，就將該節點切下並加入根串列。非根父節點第一次失去孩子時標記；已標記的父節點再次失去孩子時，自己也切下並繼續向上處理。

解題方法與推導

(1) 強連通分量

若頂點 $u$ 與 $v$ 同屬一個強連通分量，必須同時存在從 $u$ 到 $v$ 的路徑，以及從 $v$ 到 $u$ 的路徑。強連通分量是符合此條件的極大頂點集合。

(2) B-tree 為何能減少磁碟存取成本

磁碟存取通常比記憶體操作慢。B-tree 的每個節點可放入多個鍵值，並有許多子節點，因此樹的分支度高。對相同數量的資料，樹高較低，搜尋所需讀取的節點較少；當一個節點對應一個磁碟區塊時，讀取次數也隨之減少。

(3) B⁺-tree 與 B*-tree

兩者著重的性質不同：

• B⁺-tree著重索引與資料的配置：內部節點作為索引，資料記錄或記錄指標放在葉節點；葉節點通常相連，方便範圍查詢。
• *B-tree**著重節點的空間利用率：溢位時先向兄弟節點分配鍵值；若無法重新分配，再將兩個滿節點分成三個節點，通常可維持節點至少約三分之二滿。

(4) Binomial heap 的兩項性質

1. 每棵 binomial tree 都符合 heap-order；以最小堆為例，父節點鍵值不大於子節點。

核心觀念

本題涵蓋程序同步、死結處理、執行緒取消與程序終止。作答時，先給出各名詞的定義，再指出它們解決的問題或發生時機。

解題方法與各小題詳解

(1) 什麼是競爭情況？如何解決？（4%）

**競爭情況（race condition）**是指多個執行緒或程序同時存取、修改共享資料，而執行結果取決於它們的執行先後順序。若存取順序不同會產生不同結果，便可能造成資料不一致。

例如，兩個執行緒同時執行 count = count + 1。這通常包含讀取、加一、寫回等步驟；若兩個執行緒都先讀到相同舊值，就可能只寫回一次加一的結果，造成更新遺失。

解決方式是在存取共享資料的程式區段建立互斥與同步，確保同一時間只有一個執行緒執行相關操作。常見工具包括互斥鎖（mutex）、信號量（semaphore）、監視器（monitor）及原子操作。保護共享資料的程式區段稱為臨界區（critical section）。

(2) 死結預防與死結避免有何不同？（4%）

兩者都用來防止死結，但採取的方法不同。

• 死結預防（deadlock prevention）：事先限制資源配置規則，使死結的必要條件至少有一項不成立。死結四項必要條件為互斥、持有並等待、不可搶先及循環等待。例如，規定程序必須一次取得所有所需資源，可破壞「持有並等待」條件。此法規則較嚴格，可能降低資源使用效率。
• 死結避免（deadlock avoidance）：不必固定禁止某項必要條件，而是在每次資源請求時檢查配置結果；只有在系統仍處於**安全狀態（safe state）**時才核准請求。銀行家演算法是典型方法。此法需要事先知道程序的最大資源需求。

簡言之，預防是藉由限制規則排除死結條件；避免是依據當下資源狀況，只接受能維持安全狀態的請求。

(3) 何時需要使用條件變數？（4%）

當執行緒必須等待某個共享狀態條件成立才能繼續工作時，使用條件變數（condition variable）。例如，消費者執行緒在緩衝區為空時等待，直到生產者加入資料。

條件變數通常搭配互斥鎖使用。執行緒呼叫 wait 時，會原子地釋放互斥鎖並進入等待；收到 signal 或 broadcast 通知後，會重新取得互斥鎖，再檢查條件是否成立。

第 4 題詳解

核心觀念

本題整合兩大主題：

• 記憶體管理：paging、working set、thrashing、fragmentation。
• I/O 系統：同步／非同步 I/O，以及 I/O device controller 的基本暫存器。

作答時應採「先下定義，再說明運作方式與影響」的方式；比較題則明確指出差異所在。

(1) 使用 Paging 的兩項好處

Paging 將虛擬記憶體切成固定大小的 page，將實體記憶體切成相同大小的 frame，再透過 page table 進行對映。

1. 允許非連續配置，消除外部碎裂

   程式的各個 page 不必放在連續的實體記憶體中，只要有足夠數量的空閒 frame 即可配置。因此，空閒空間即使分散在各處，也能被利用。

   Paging 可消除因連續配置所產生的 external fragmentation，也減少搬移記憶體進行 compaction 的需要。

2. 支援虛擬記憶體與 demand paging

   程式不必一次將全部內容載入實體記憶體，只需將目前使用到的 page 載入。如此一來：

   • 程式的虛擬位址空間可以大於實體記憶體。
   • 同一時間可容納較多程式，提高多工程度。
   • 未使用的 page 不必佔用實體記憶體。

   Paging 的代價是 page table 的額外空間，以及最後一個 page 未完全使用時所造成的 internal fragmentation。

(2) Working Set 與 Thrashing

Working Set

Working set 是程式在最近一段記憶體參考範圍內實際使用過的 page 集合。

以最近 $\Delta$ 次記憶體參考為視窗，可表示為：

$$W(t,\Delta)=\{p\mid p\text{ 在最近 }\Delta\text{ 次記憶體參考中曾被使用}\}$$

其中：

• $t$：目前的參考位置。
• $\Delta$：working-set window 的大小。
• $|W(t,\Delta)|$：程式近期運作所需的 frame 數量估計。

Working set 反映程式目前的 locality。例如程式正在執行某個迴圈時，迴圈中的指令與資料 page 會反覆被參考，形成一個相對穩定的 working set。

Thrashing

Thrashing 是系統花費大量時間處理 page fault、page-in 與 page-out，實際執行程式的時間反而很少的現象。

當多個程式的 working set 所需 frame 總數超過可用 frame 數量時：

$$\sum_i |W_i(t,\Delta)| > F$$

其中 $F$ 是可用的實體 frame 數量。此時程式載入一個 page 後，常會因另一個 page 被淘汰而再次發生 page fault，形成頻繁換頁。

典型現象包括：

• page fault rate 很高。
• 磁碟 I/O 頻繁。
• CPU utilization 下降。
• 系統反覆在記憶體與磁碟間搬移 page。

常見處理方式是增加可用 frame、降低 multiprogramming degree，或利用 working-set model 與 page-fault frequency 來控制配置。

(3) External Fragmentation 與 Internal Fragmentation

類型	定義	常見成因	典型例子
External fragmentation	空閒記憶體分散在已配置區塊之外，總空間足夠但沒有足夠大的連續區塊	可變大小的連續配置	剩餘 $10$ MB 空間分散成多個小洞，無法配置一個 $6$ MB 的連續區塊
Internal fragmentation	已配置給某區塊的空間內部有未使用部分，這些空間不能有效提供給其他配置	固定大小的配置單位	配置一個 page 後，page 尾端尚有未使用空間

以 page 大小為 $4$ KiB、程式需求為 $6$ KiB 為例，需要配置兩個 page：

$$2\times4-6=2\text{ KiB}$$

第 5 題 Protection and Security（20%）

核心觀念

本題涵蓋五個安全核心：

1. 以最小權限限制程序受到攻擊後的損害範圍。
2. 區分病毒與蠕蟲的複製方式。
3. 理解 UNIX setuid 所造成的權限提升風險。
4. 分辨身分冒充與訊息重送攻擊。
5. 區分身分驗證、授權與不可否認性。

---

（1）最小權限原則與 Solaris 10 的實作

解題方法

先寫出最小權限原則的定義，再說明傳統 UNIX 的 root／setuid 模型為何違反此原則，最後指出 Solaris 10 以細粒度權限與 RBAC 改善此問題。

作答

**最小權限原則（principle of least privilege）**是指：每個使用者、程序或程式，只能取得完成目前工作所需的最少權限，而且權限只在必要的時間與範圍內有效。

其安全效果包括：

• 減少程式被入侵後可造成的損害。
• 降低攻擊面與權限提升機會。
• 避免不必要的檔案、程序或系統資源遭到存取。

傳統 UNIX 中，root 擁有幾乎所有系統權限。若程式設定 setuid 為 root，整個程式通常會以高權限執行；只要程式存在緩衝區溢位、輸入驗證、環境變數或檔案路徑漏洞，攻擊者就可能取得完整的 root 權限。

Solaris 10 主要透過以下方式實作最小權限：

1. 細粒度的 process privileges

   Solaris 將超級使用者權限拆成許多獨立權限，例如：

   • file_dac_write：繞過一般檔案寫入限制。
   • sys_time：修改系統時間。
   • net_privaddr：使用低於 1024 的特權埠。

   程式只需取得完成工作的特定權限，不必整體變成 root。

2. RBAC（Role-Based Access Control）

   Solaris 10 以角色、授權（authorization）與權限設定檔（rights profile）分配管理能力。使用者只在執行特定工作時取得對應角色的權限，不必直接使用全能的 root 身分。

3. 程序權限集合

   每個程序具有四種主要權限集合：

   • Effective set（E）：目前正在生效的權限。
   • Permitted set（P）：程序可以啟用的權限。
   • Inheritable set（I）：執行 exec 後可傳給子程序的權限。
   • Limit set（L）：程序及其子程序可擁有的權限上限。

   權限感知程式（privilege-aware program）可在不需要某項權限時將其關閉，完成特權操作後立即放棄權限。

因此，Solaris 10 以「細粒度程序權限＋RBAC＋權限集合」取代單純的全能超級使用者模型。Oracle Solaris 10 官方文件

解題技巧

答題關鍵字必須包含：

最小必要權限、細粒度 privileges、RBAC、降低對 root 與 setuid 的依賴。

只寫「Solaris 10 使用 RBAC」尚未完整，應補上 privileges 是由核心逐項檢查的細粒度權限。

---

（2）Computer Virus 與 Computer Worm 的差異

核心觀念

兩者都是具有自我複製能力的惡意程式，但最大差異在於：

• 病毒是否需要依附宿主程式或檔案。
• 蠕蟲是否能獨立執行並自行傳播。

作答

比較項目	電腦病毒（virus）	電腦蠕蟲（worm）
是否需要宿主	依附於可執行檔、文件、開機磁區等宿主	可獨立執行，不需依附其他程式
複製方式	感染其他檔案或程式	自行複製完整程式
傳播方式	常透過使用者執行、分享或開啟受感染檔案	常透過網路掃描漏洞並自動傳送
使用者參與	通常需要使用者執行受感染檔案	通常不需使用者直接操作
主要影響	破壞或修改檔案、程式	快速消耗網路、CPU、記憶體及頻寬

病毒必須寄生在其他檔案或程式中，當宿主被執行時，病毒程式才有機會啟動並感染更多對象。

蠕蟲本身就是完整的可執行程式，能透過網路掃描其他主機的漏洞，複製自身並繼續擴散。

解題技巧

判斷重點是「是否需要宿主」，不是單純看「是否使用網路」。病毒也能透過網路上的檔案傳播，但它仍須依附宿主；蠕蟲則能獨立複製與執行。

---

（3）UNIX setuid-on 問題與兩種處理方式

核心觀念

當可執行檔的 setuid 位元開啟時，使用者執行該程式後，程序的有效使用者識別碼（effective UID）會變成檔案擁有者的 UID。

例如，一般使用者執行由 root 擁有且開啟 setuid 的程式：

• Real UID：仍是一般使用者。
• Effective UID：變成 root。
• 核心進行檔案權限檢查時，主要依據 effective UID。

因此，若 setuid-root 程式有漏洞，攻擊者便可能利用該程式取得完整的 root 權限。

兩種常見解法

解法一：集中並保護特權程式

將所有需要特權的程式放在由 root 擁有、一般使用者不可寫入的系統目錄中，並採取以下限制：

• 一般使用者不得建立、修改或替換其中的檔案。
• 只有經審查的二進位程式可設定 setuid。
• 移除不必要程式的 setuid 位元。
• 對使用者可寫入的檔案系統停用 setuid 效果。
• 定期稽核系統內的 setuid 檔案。