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

(a)

核心觀念

此程式使用「平方倍增」計算次方：

• b % 2 == 1：判斷 $b$ 的最低位元是否為 $1$。
• b = b >> 1：對正整數右移一位，相當於整數除以 $2$。
• 每次將 a 平方，使其依序代表 $2^1,2^2,2^4,2^8,\ldots$。
• 當 $b$ 的某一位元為 $1$ 時，就將對應的 a 乘入 c。

因為

$$13=(1101)_2=8+4+1，$$

所以最後計算的是

$$2^{13}=2^8\cdot 2^4\cdot 2^1。$$

解題方法

逐次追蹤變數：

迴圈開始時 b	迴圈開始時 a	b 是否為奇數	c 更新後	a=a*a 後	右移後的 b
13	2	是	$1\times2=2$	4	6
6	4	否	2	16	3
3	16	是	$2\times16=32$	256	1
1	256	是	$32\times256=8192$	65536	0

當 b 變成 $0$ 時，迴圈結束，因此輸出：

$$c=8192。$$

解題技巧與複雜度

看到「判斷奇偶、右移、底數平方」時，可直接視為二進位次方分解。此題只需將 $13$ 寫成 $1101_2$，即可快速得到：

$$c=2^1\cdot2^4\cdot2^8=2^{13}=8192。$$

迴圈執行次數為 $O(\log b)$，額外使用的變數空間為 $O(1)$。

---

(b)

核心觀念

陣列宣告為：

int a[64]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

因此：

$$a[0]\sim a[15]=0\sim15，$$

而

$$a[16]\sim a[63]=0。$$

三次外層迴圈中，c 依序為：

$$1,\ 2,\ 4。$$

每次內層迴圈執行：

a[j] = a[j] + a[j+c];

基數排序（Radix Sort）採用最低有效位數（LSD）優先原則，每一階段（Pass）對指定位數進行穩定排序（Stable Sort）。將輸入元素看作三位數：$642, 374, 073, 029, 284, 252$。

---

(a) 第一階段 Pass 1（對個位數進行穩定排序）

提取各元素的個位數：

• $642 \rightarrow 2$
• $374 \rightarrow 4$
• $073 \rightarrow 3$
• $029 \rightarrow 9$
• $284 \rightarrow 4$
• $252 \rightarrow 2$

按個位數 $0 \sim 9$ 放入桶中並保持相對順序：

• 桶 2：$642, 252$
• 桶 3：$73$
• 桶 4：$374, 284$
• 桶 9：$29$

將桶內元素依序合併，得到 Pass 1 完成後的序列：
$642, 252, 73, 374, 284, 29$

---

核心觀念

本題考查 AVL tree 的插入與平衡調整。

對每個節點定義平衡因子：

$$BF(v)=h(\text{left}(v))-h(\text{right}(v))$$

AVL tree 必須滿足：

$$BF(v)\in\{-1,0,1\}$$

插入新元素後，先依二元搜尋樹規則放入，再由插入位置向根節點回溯；若某節點的平衡因子變成 $2$ 或 $-2$，便需進行旋轉。

解題方法

插入流程如下：

1. 依二元搜尋樹規則比較鍵值，將新元素插入葉節點。
2. 更新插入路徑上各節點的高度。
3. 計算各節點的平衡因子。
4. 找到第一個失衡節點後，依插入方向判斷旋轉類型：
   • 左左（LL）：右旋。
   • 右右（RR）：左旋。
   • 左右（LR）：先左旋左子樹，再右旋。
   • 右左（RL）：先右旋右子樹，再左旋。

(a) 插入元素 $1$

將 $1$ 插入原 AVL tree 的適當葉節點後，沿路往根節點檢查平衡因子：

• 若形成 LL 型，對失衡節點進行右旋。
• 若形成 LR 型，先對失衡節點的左子樹左旋，再對失衡節點右旋。

核心觀念

本題考查合法括號序列與 Catalan 數（Catalan numbers）。

一個含有 $n$ 對括號的合法序列必須滿足：

1. 左括號與右括號總數相等；
2. 從左至右掃描任一前綴時，左括號數不得少於右括號數；
3. 每個左括號都能與後方唯一的右括號配對。

令最前面的左括號與其配對的右括號之間，包含 $i$ 對括號；這兩個括號之後剩下 $n-1-i$ 對括號。因此，合法序列可分解為：

$$(\ A\ )\ B$$

其中：

• $A$ 是含有 $i$ 對括號的合法序列，共有 $p(i)$ 種；
• $B$ 是含有 $n-1-i$ 對括號的合法序列，共有 $p(n-1-i)$ 種。

兩部分可獨立組合，因此固定 $i$ 時共有：

$$p(i)p(n-1-i)$$

種。

---

解題方法

（a）計算 $p(3)$

第一對括號的內部可能包含 $i=0,1,2$ 對括號，分別計算：

$$p(3) = p(0)p(2)+p(1)p(1)+p(2)p(0)$$

代入已知值 $p(0)=1,\ p(1)=1,\ p(2)=2$：

$$\begin{aligned} p(3) &=1\cdot 2+1\cdot 1+2\cdot 1\\ &=2+1+2\\ &=5 \end{aligned}$$

五個合法括號序列為：

$$()()(),\quad ()(()),\quad (())(),\quad (()()),\quad ((()))$$

所以：

$$\boxed{p(3)=5}$$

（b）遞迴關係

(a) 檔案的六項常見屬性

核心觀念

檔案除了供使用者辨識的名稱（name）之外，作業系統還會維護一組描述檔案的中繼資料（metadata），用來定位檔案、判斷檔案類型、控制存取權限，以及記錄檔案使用狀況。

六項屬性

1. 識別碼（identifier）
   作業系統為檔案配置的唯一識別資訊，例如 Unix 檔案系統中的 inode number。它與檔案名稱不同，即使檔案重新命名，識別碼通常仍維持不變。

2. 檔案類型（type）
   表示檔案的種類，例如一般檔案（regular file）、目錄（directory）、字元裝置檔案、區塊裝置檔案或符號連結。檔案類型會影響作業系統對該檔案可執行的操作。

3. 位置（location）
   記錄檔案在儲存裝置上的位置資訊，例如所在磁碟裝置，以及資料所使用的磁碟區塊或索引區塊。檔案路徑是尋找檔案的方式，位置屬性則是檔案實際儲存位置的描述。

4. 大小（size）
   表示檔案目前包含的資料量，通常以 byte 為單位。它通常指邏輯檔案大小，與檔案在磁碟上實際配置的區塊數量不一定相同。

5. 保護資訊（protection）
   記錄哪些使用者或群組可以對檔案進行讀取、寫入、執行、刪除等操作。常見形式包括 owner、group、read/write/execute 權限，以及 ACL（Access Control List）。

6. 時間、日期與使用者識別（time, date, and user identification）
   記錄檔案的建立時間、最近修改時間、最近存取時間，以及擁有者或建立者的 user ID。這些資訊可用於檔案稽核、備份、權限管理與判斷檔案是否被更新。

---

(b) Interrupt Chaining 的運作方式

核心觀念

Interrupt chaining 用於多個裝置共用同一條 interrupt request line，或多個裝置共用同一個 interrupt vector 的情況。

同一個 interrupt vector 不再只對應一個中斷服務程式（Interrupt Service Routine, ISR），而是對應一串依序連結的 ISR。每個 ISR 必須檢查裝置狀態，判斷該中斷是否由自己負責的裝置所產生。

解題方法與運作流程

假設裝置 A、B、C 共用 interrupt number $k$：

$$\text{IRQ}_k \rightarrow \text{Interrupt Vector}[k] \rightarrow \text{ISR}_A \rightarrow \text{ISR}_B \rightarrow \text{ISR}_C$$

其運作流程如下：

核心觀念

本題分為兩個主題：

• (a) 考查硬體如何提供「原子性」與「記憶體存取順序」，以實作臨界區的互斥。
• (b) 考查行程間通訊（Inter-Process Communication, IPC）的兩種基本模型：共享記憶體與訊息傳遞。

臨界區問題的完整解法應滿足：

1. 互斥（mutual exclusion）：同一時間至多一個行程位於臨界區。
2. 進度（progress）：臨界區沒有人使用時，想進入的行程不能被無限期延後。
3. 有限等待（bounded waiting）：行程提出進入要求後，等待時間必須有上限。

---

解題方法

(a) 依照硬體提供的功能分類：

1. 強制記憶體存取順序：記憶體屏障。
2. 將讀取、修改、寫回合併成不可分割操作：硬體原子指令。
3. 對特定變數提供不可分割的存取與更新：原子變數。

(b) 先判斷行程交換資料時是否使用共同的位址空間：

• 使用共同資料區域：共享記憶體模型。
• 透過作業系統提供的 send、receive 傳送資料：訊息傳遞模型。

---

(a) 三種硬體支援

1. 記憶體屏障（memory barriers）

現代處理器與編譯器為提升效能，可能重新排列記憶體讀寫順序。記憶體屏障會要求屏障前的記憶體操作，在屏障後的操作執行前完成適當的排序與可見性處理：

$$\text{屏障前的記憶體操作} \prec \text{屏障後的記憶體操作}$$

例如生產者先寫入資料，再設定旗標：

buffer[i] = item;
memory_barrier();
ready = true;

消費者看到 ready == true 後，再經過對應的讀取屏障，才能正確讀到 buffer[i] 的內容：

while (ready == false) {
    // 等待
}
memory_barrier();
item = buffer[i];

記憶體屏障主要解決的是操作順序與資料可見性，本身不等於互斥鎖，也不能單獨保證兩個行程不會同時進入臨界區，通常要搭配原子變數或原子指令使用。

---

2. 硬體原子指令（hardware atomic instructions）

硬體提供不可被分割的「讀取—修改—寫回」指令，使多核心同時存取鎖定變數時，仍能正確決定哪一個行程取得鎖。

Test-and-Set

test_and_set 會在一次不可分割的操作中：

1. 讀取目標變數的舊值。
2. 將目標變數設為 true。
3. 回傳舊值。

其語意如下：

$$\operatorname{TestAndSet}(target): \begin{cases} old \leftarrow target \\ target \leftarrow true \\ return\ old \end{cases}$$

以自旋鎖實作臨界區：

lock = false;

while (TestAndSet(&lock) == true) {
    // 持續自旋
}

/* 臨界區 */

lock = false;

若回傳 false，代表原本沒有上鎖，該行程取得鎖；若回傳 true，代表已有其他行程持有鎖，該行程繼續等待。

Compare-and-Swap（CAS）

CAS 只有在變數目前值等於預期值時，才會將它更新成新值：

$$\operatorname{CAS}(address, expected, new): \begin{cases} *address \leftarrow new,\ return\ true, & \text{若 } *address=expected \\ return\ false, & \text{否則} \end{cases}$$

CAS 可用來實作互斥鎖、無鎖資料結構與原子計數器。

硬體原子指令能有效達成互斥，但自旋鎖會消耗 CPU 時間，而且未必保證公平性，因此可能發生某個行程長時間得不到鎖的情況。

---

3. 原子變數（atomic variables）

原子變數是由硬體與作業系統支援的特殊資料型態。對該變數的特定操作，例如讀取、寫入、遞增、遞減，會以不可分割方式完成。

例如：

atomic<int> counter;
counter.fetch_add(1);

fetch_add(1) 會保證多個執行緒同時更新 counter 時，每次更新都不會遺失。

但必須注意，單一原子操作不代表整段複合操作都是原子的。下列操作仍可能產生競爭：

if (counter < limit) {
    counter = counter + 1;
}

核心觀念

TLB（Translation Look-aside Buffer）是 MMU（Memory Management Unit）內部用來快取「虛擬頁號」與「實體頁框號」對應關係的高速記憶體。它的目的，是避免每次存取記憶體都必須先查詢頁表。

虛擬位址可表示為：

$$VA=(p,d)$$

其中：

• $p$：虛擬頁號（page number）
• $d$：頁內位移（offset）

若 TLB 或頁表找到虛擬頁號 $p$ 對應的實體頁框號 $f$，則實體位址為：

$$PA=(f,d)$$

頁內位移 $d$ 在位址轉換過程中不會改變。

解題方法：TLB 操作的五個步驟

1. CPU 產生虛擬位址

   CPU 執行載入、儲存或取指令時，產生一個虛擬位址 $VA$。MMU 將它拆成虛擬頁號 $p$ 與頁內位移 $d$。

2. 以虛擬頁號搜尋 TLB

   MMU 將 $p$ 傳給 TLB，以關聯式搜尋（associative lookup）比對 TLB 中的所有項目，尋找是否存在 $p\rightarrow f$ 的有效對應。

   TLB 項目通常也包含 valid bit、存取權限與 dirty bit 等資訊，因此不只要比對頁號，也要檢查該項目是否有效且允許目前的存取操作。

3. TLB 命中時取得頁框號

   若找到有效的對應，稱為 TLB hit。TLB 直接回傳實體頁框號 $f$，不必再存取主記憶體中的頁表。

   MMU 將 $f$ 與原本的頁內位移 $d$ 組合：

   $$PA=(f,d)$$

   接著使用此實體位址存取指令或資料。

4. TLB 未命中時查詢頁表

   若 TLB 中找不到 $p$，稱為 TLB miss。MMU 必須到主記憶體中的頁表查詢該虛擬頁號。

   以單層頁表為例，頁表項目位址可表示為：

   $$\text{PTE address}=\text{PTBR}+p\times\text{PTE size}$$

   查得頁表項目後：

(a)
當裝置透過纜線依次串接（裝置 A 接 B、B 接 C，最終 C 接至電腦連接埠），此種序列連接架構稱為雛菊鏈（daisy chain）。

【答案】daisy (或 daisy-chain)

---

(b)
進程（process）在記憶體中的虛擬位址空間配置主要包含四個主要區域：程式碼區（text section）、資料區（data section）、堆積區（heap section）與堆疊區（stack section）。

【答案】heap

---

(c)
當多個進程同時存取與操作相同資料，且執行結果取決於存取發生的特定先後順序時，此現象稱為競態條件（race condition）。

【答案】race

---

(d)
死鎖（deadlock）發生的四個必要條件為：互相排斥（mutual exclusion）、持有並等待（hold and wait）、不可預奪（no preemption）以及循環等待（circular wait）。

【答案】hold and wait (或 hold-and-wait)

---

(e)
可重入程式碼（reentrant code，又稱 pure code）為非自我修改的程式碼（non-self-modifying code），在執行期間絕不改變自身內容，可供多個進程安全地共享執行。

【答案】reentrant (或 pure)

---