108 年 國立中正大學資訊工程學系碩士班《計算機系統》

核心觀念

本題考查檔案系統如何管理磁碟上的空閒空間。檔案系統除了要記錄檔案使用哪些磁碟區塊，也要能找出尚未配置的區塊，供新檔案使用。

**FAT（File Allocation Table，檔案配置表）**中的表格項目可表示磁碟叢集的使用狀態，也可串接同一檔案所占用的叢集，因此能同時協助管理空閒空間與檔案配置。

解題方法

圖中題目詢問哪種機制能追蹤磁碟空閒空間，並同時執行其他功能；選項依序為 FCB、Partition、FAT、Inode，以及「以上皆非」。判斷關鍵是找出能兼顧「記錄空閒叢集」與「管理檔案配置」的機制。

FAT 的表格會為每個叢集記錄狀態：未配置的叢集可標示為空閒；已配置的叢集則透過表格項目連結，記錄檔案所占用的叢集鏈。因此 FAT 不只追蹤空閒空間，也能記錄檔案資料的配置方式。

選項分析

核心觀念

本題考各種 RAID 磁碟組織如何提供冗餘，以及為了冗餘需要額外配置多少顆磁碟。比較時，應看同樣可用容量下，哪些磁碟空間用來存放鏡像或同位元資訊，而非一般資料。

解題方法

原卷第 1-(2) 題詢問哪一種磁碟組織「提供冗餘，但額外磁碟成本最高」，選項為 RAID 0、RAID 1、RAID 5、RAID 6，以及「以上都需要相同數量的磁碟」。比較各組織的冗餘方式與額外磁碟需求即可。

假設每顆磁碟容量相同，若要存放 $N$ 顆磁碟容量的資料：

• RAID 1 以鏡像複製資料，約需再配置 $N$ 顆磁碟存放副本；總磁碟數約為 $2N$。
• RAID 5 以分散式同位元資訊提供冗餘，約需相當於 $1$ 顆磁碟的容量存放同位元資訊。
• RAID 6 以雙重分散式同位元資訊提供冗餘，約需相當於 $2$ 顆磁碟的容量存放同位元資訊。
• RAID 0 沒有冗餘，不需額外磁碟存放副本或同位元資訊。

因此，RAID 1 的鏡像副本需要最多額外磁碟。

核心觀念

本題考查作業系統虛擬記憶體管理中**分頁機制（Paging）與多層頁表（Multi-Level Page Tables / Hierarchical Paging）**的設計緣由。

1. 單層線性頁表（Linear Page Table）的限制：

   • 在線性頁表中，虛擬位址中的虛擬頁號（Virtual Page Number, VPN）直接作為頁表的陣列索引（Index）。
   • 硬體記憶體管理單元（MMU）透過頁表基底暫存器（PTBR）以基底加偏移量方式定址：
     $\text{Physical Address of PTE} = \text{PTBR} + (\text{VPN} \times \text{PTE Size})$
   • 這要求整個線性頁表必須存放在大片連續的實體記憶體中。
   • 頁表大小取決於虛擬位址空間的大小，而非行程實際使用的記憶體量。

2. 外部碎裂（External Fragmentation）問題：

   • 以傳統 32 位元架構為例，若分頁大小為 $4\text{ KB}$（$2^{12}\text{ bytes}$），則虛擬位址空間包含 $2^{20}$（約 100 萬）個頁面。
   • 若每個頁表項目（Page Table Entry, PTE）佔 $4\text{ bytes}$，則單一行程的線性頁表即需佔用：
     $2^{20} \times 4\text{ bytes} = 4\text{ MB}$
   • 每個行程都必須在實體記憶體中分配連續的 $4\text{ MB}$ 空間。當系統有多個行程時，在核心或實體記憶體中頻繁尋找大片連續空間會遭遇嚴重的外部碎裂，失去分頁原本「無需連續實體空間」的美意。

3. 多層頁表的解法：

   • 透過「對頁表進行分頁（Paging the page table）」，將頁表切成頁面大小（例如每個節點 $4\text{ KB}$）的小單元。
   • 每個頁表分頁可以分散置於任意非連續的實體頁框（Frames）中，徹底消除了連續實體記憶體配置的需求，解決了外部碎裂；同時對於稀疏（Sparse）的位址空間，未使用的分頁目錄不需要配置，大幅節省記憶體。

解題方法

檢視原卷附圖 原卷第 1 大題之第 (3) 小題，題目詢問「發展多層頁表的主要原因為何？（Why were multi-level page tables developed?）」。

解題切入點為比對單層頁表與多層頁表在實體記憶體配置結構上的差異：

• 單層頁表必須以陣列形式連續排列，對實體記憶體而言是一個大型連續區塊（例如 32 位元下需連續 $4\text{ MB}$，64 位元下更為天文數字），在實體記憶體分配大型連續區塊必然會引起外部碎裂。

核心觀念

本題的核心在於作業系統虛擬記憶體（Virtual Memory, VM）管理中的效能權衡（Trade-off: CPU cycles vs. Disk I/O）與頁面置換策略（Page Replacement Policy）：

1. CPU 週期與磁碟存取之代價差距：
   在計算機系統中，CPU 執行指令的時間通常在奈秒等級（約 $0.2 \sim 1\text{ ns}$），而磁碟 I/O（特別是傳統機械硬碟的尋軌與旋轉延遲，甚至固態硬碟的存取）延遲高達數毫秒（$\text{ms}$）至數十微秒（$\mu\text{s}$），兩者差距可達數萬至數百萬倍。因此，作業系統願意花費數千甚至數萬個 CPU 週期進行複雜的演算法決策，只要能成功避免一次磁碟存取（Disk Access），對整體系統效能而言都是極具效益的時間投資（time well spent）。
2. 尋找空閒頁框（Finding a Free Frame）與置換演算法：
   當系統發生缺頁中斷（Page Fault）且缺乏空閒頁框時，必須從目前已配置的頁面中挑選犧牲頁面（Victim Page）淘汰。如果挑選了錯誤的頁面（例如不久後又會被存取的活躍頁面），將會迅速再次觸發缺頁中斷，造成代價高昂的磁碟讀取與系統顛簸（Thrashing）。
3. 基於參考計數（Reference Count）的最佳化置換：
   依據程式存取的局部性原理（Principle of Locality），參考次數較少的頁面在未來被再次存取的機率最低。若花費 CPU 週期統計並排序頁面的參考資訊（例如 LFU、LRU 近似演算法或維護活躍／非活躍計數佇列），優先淘汰冷門頁面，可最大程度降低後續再度將該頁面讀入記憶體的機率，從而達成「花費 CPU 週期以避免後續磁碟 I/O」的目的。

解題方法

由原卷頁圖（第 1 頁）第 1-(5) 題題幹可知：

「We said that we could spend lots of CPU cycles to avoid making a disk access in the VM system when we try to find a free frame. Which would be an example of time well spent in such a pursuit?」

題幹明確設定情境：在虛擬記憶體系統尋找空閒頁框時，「投入大量的 CPU 週期進行運算，目標是避免（avoid）後續的磁碟 I/O 存取」，而選項 (E) 亦補充提示「avoid a later I/O operation」。

解題切入點在於區分以下四類操作的本質：

1. 是否屬於分頁式虛擬記憶體系統在尋找頁框時的機制。
2. 該操作消耗的資源是 CPU 週期還是直接產生磁碟 I/O。
3. 該操作是否能真正「免除／避免」日後的 I/O 操作，而非僅僅是「提前執行」或「引發更多」I/O。

選項分析

• (A) Swap out processes that are in a wait state（換出處於等待狀態的行程）：錯誤
  將處於等待（等待 I/O 或事件）的行程置換出記憶體，需要將該行程所佔用的所有頁面或工作集寫入磁碟的 Swap 空間，這會立即引發大量的磁碟寫入 I/O，不但沒有避免磁碟存取，反而主動增加了磁碟負載。此外，Swapping 屬於中程排程（Mid-term Scheduling）的粗粒度記憶體調節，並非頁面層級尋找 free frame 時用來避免 I/O 的演算法。

核心觀念

本題考「死結發生的必要條件」。死結要能發生，必須同時具備四項條件：互斥、持有並等待、不可搶先，以及循環等待。少了其中任一條件，就能避免死結。

「死結避免」是作業系統處理死結的方法，不是死結發生的必要條件。

解題方法

依原卷第二頁第（6）題，題目問哪些選項不是死結發生的必要條件；選項包含 Avoidance、Hold and Wait、Circular wait、Mutual Exclusion，以及「以上皆為必要條件」。將各選項與死結四項必要條件逐一比對即可。

選項分析

• (A) Avoidance：正確。「避免」是處理死結的策略，不是死結發生所需的條件。
• **(B) Hold and Wait：錯誤。

核心觀念

SRTF（Shortest Remaining Time First，最短剩餘時間優先）是 SJF 的搶佔式版本：新行程抵達時，若其 CPU burst 比目前執行中行程的剩餘時間更短，就立刻搶佔。

它的排程特性：

• 對一組已知 burst 的行程，平均等待時間最小。
• 偏好短行程，因此長行程可能一再被後來的短行程搶佔，永遠排不到 CPU，這就是飢餓（starvation），也是這個演算法在排程行為上最典型的缺陷，通常以老化（aging）緩解。

解題方法

題目問的是演算法本身的問題，逐一檢查五個選項的說法是否是 SRTF 的排程缺陷：

• 先排除與 SRTF 行為相反的敘述（C）與不符合事實的敘述（D）。
• 再比較 (A) 與 (B)：(A) 說的是「事先不知道 burst 長度」，屬於取得輸入資訊的實作前提，所有以 burst 長度為依據的排程法（SJF、SRTF）都共有，實務上用指數平均估計；(B) 說的是排程政策運作後造成的結果，是 SRTF 本身的缺陷。題目問「problem with the algorithm」，標準答案取 (B)。

簡單範例：行程 $P_1$ 的 burst 為 100，在 $t=0$ 抵達；之後每個時間單位都有一個 burst 為 1 的新行程抵達。

核心觀念

本題考 CPU 排程中的搶先（preemption）。搶先式排程允許作業系統在程序尚未完成前，暫停目前執行的程序，改由其他程序使用 CPU。這可能改善平均等待時間，例如最短剩餘時間優先（SRTF），但切換執行程序需要額外處理成本。

解題方法

依原卷圖，第 1-(8) 題詢問：CPU 排程器允許搶先的代價為何？選項包含護送效應、飢餓、CPU 使用率下降、更多脈絡切換，以及「以上皆非」。判斷關鍵是找出搶先時直接增加的系統開銷：程序被暫停、另一程序開始執行時，系統需要進行脈絡切換（context switch）。

選項分析

• (A) 引入護送效應：錯誤。 護送效應常見於先到先服務（FCFS）這類非搶先式排程：短作業可能排在長作業後面等待。它不是允許搶先所直接帶來的代價。
• **(B) 可能發生飢餓：錯誤。

核心觀念

本題考的是作業系統核心的架構分類。**單體式核心（monolithic kernel）**把核心服務與驅動程式放在核心空間執行；Linux 的核心屬於單體式核心，並支援動態載入與卸載核心模組，因此最精確的描述是「具有可動態載入驅動程式的單體式核心」。

解題方法

依原卷圖，第 1-(9) 題詢問哪一項最能描述 Linux 的架構，選項包含 Microkernel、Monolithic、Monolithic with Dynamically Loadable Drivers、Macrokernel，以及以上皆非。判斷時先辨認 Linux 的核心服務是否主要在核心空間執行，再看它是否支援執行期間載入驅動程式模組。

Linux 的核心服務與驅動程式主要在核心空間執行，符合單體式核心的特徵；Linux 也支援以核心模組方式動態載入驅動程式。因此，選項 C 比只寫「單體式」的選項 B 更完整、精確。

選項分析

• (A) Microkernel：錯誤。 微核心架構會將許多服務移至使用者空間，核心本身盡量維持精簡；這不是 Linux 核心的主要架構分類。

核心觀念

本題考「沙箱模型」（sandbox model）：將不受信任的程式限制在隔離、受控的環境中執行，避免它任意存取主機的檔案、記憶體或其他資源。虛擬機器是建立這類受控環境的一種方式。

解題方法

依原卷頁圖，第 1-(10) 題問沙箱模型的意義；選項提到在另一台電腦、另一顆 CPU、受控環境、虛擬作業系統環境中執行不受信任的程式，或以上皆非。判斷重點是：沙箱的核心在於「受控隔離」，不要求使用獨立硬體，也不限定某一種作業系統虛擬化方式。

選項分析

核心觀念

可以。關鍵在於「死結（deadlock）」與「安全狀態（safe state）」判斷的是不同事情：

• 死結狀態：目前已有程序彼此等待資源，且沒有任何程序能繼續執行並釋放資源。
• 安全狀態：從目前配置出發，存在一個安全序列，使每個程序都能取得其最大剩餘需求、完成並釋放資源。
• 不安全狀態（unsafe state）：不存在安全序列，因此系統無法保證未來一定避免死結；但這不表示死結已經發生。

安全性檢查使用：

若存在程序 $P_i$ 滿足：

則可假設 $P_i$ 完成，完成後釋放其目前持有的資源：

依序找到所有程序，即表示系統安全。

因此，兩者的關係是：

但反向不成立：

解題方法與範例

考慮系統只有一種資源，共有 $10$ 個實例，包含兩個程序：

目前可用資源為：

核心觀念

這題考的是從記憶體存取圖辨認程式的存取行為。圖中橫軸是取樣時間，縱軸是應用程式位址空間中的記憶體頁面；不同位置的點代表程式在該時間讀取或寫入相應頁面。若存取集中在不同頁面區域，且隨時間切換，表示程式具有不同的執行階段與工作集合。

解題方法

讀圖可見，astar 位於右下方。它的存取點呈現數段明顯的垂直區塊：不同時間區段會密集存取不同的頁面範圍，中間則有存取較少或頁面範圍改變的區段。

核心觀念

這題考的是從記憶體頁面存取圖辨認程式的空間與時間存取行為。縱軸是程式位址空間中的記憶體頁面，橫軸是取樣時間；圖例中的 RD、WD 分別表示讀取與寫入的資料。

解題方法

圖中 cactusADM 位於左上方。它的圖樣由密集、反覆起伏的條紋組成，且分布涵蓋大範圍的位址空間；這表示程式會以有規律的方式，反覆觸及許多不同頁面，而非長時間只存取少數固定頁面。

核心觀念

Solaris 的 dispatch table 依執行緒的 priority 查詢排程參數；本題要讀取的是 Time Quantum 欄，代表該優先權執行緒可使用的時間量子，單位為毫秒。

解題方法

依原卷表格，Priority $10$ 的 Time Quantum 是 $160$；Priority $55$ 的 Time Quantum 是 $40$。

核心觀念

Solaris 分派表會依執行緒的狀態事件調整其優先權。執行緒用完整個時間量子而未阻塞時，應查表中的 Time Quantum Expired 欄；若是從睡眠狀態返回，才查 Return from Sleep 欄。

解題方法

核心觀念

Solaris 時間分享排程器會依執行緒的事件調整其優先權。執行緒用完整個時間片時，依「Time Quantum Expired」欄調整；若在時間片用完前因 I/O 阻塞，之後從睡眠狀態返回，則依「Return from Sleep」欄指定新優先權。

解題方法

圖中的表格列出優先權 $35$ 的執行緒，其「Time Quantum」為 $80$、「Time Quantum Expired」為 $25$、「Return from Sleep」為 $54$。

核心觀念

每個輸出位置都是 $2\times2$ 區域與 $2\times2$ 核心逐項相乘後加總，因此需要 4 次乘法、3 次二輸入加法。延遲時間取決於運算依賴鏈；可平行執行的運算不必依序累計延遲。

解題方法

圖中輸入圖為 $3\times4$，包含 $a$ 到 $l$；核心為 $2\times2$，參數為 $w,x,y,z$；輸出特徵圖為 $2\times3$。每個輸出位置都是四個乘積相加，例如左上角輸出為 $aw+bx+ey+fz$。

先將四次乘法平行執行，耗時 $D_{\mathrm{MUL}}$。四個乘積可用平衡加法樹相加：第一層同時做兩次加法，第二層再將兩個部分和相加，共需兩層加法，耗時 $2D_{\mathrm{ADD}}$。

因此，單一輸出位置的最短延遲為

核心觀念

本題考查卷積運算中的乘加數量、運算相依性，以及不同運算單元能否在同一個時脈週期平行工作。圖中輸入為 $3\times4$，核心為 $2\times2$，輸出為 $2\times3$，因此要計算 $6$ 個輸出值；每個輸出值都由 $4$ 次乘法及 $3$ 次加法組成。

題目說明輸入與核心參數已在計算前載入，因此只計算乘法與加法所需的週期。每個週期最多執行一次乘法和一次加法，兩者可以平行。

解題方法

將圖中六個輸出依序記為 $O_1$ 至 $O_6$，每個輸出都包含四個乘積。例如：

總乘法數為 $6\times4=24$ 次，總加法數為 $6\times3=18$ 次。乘法與加法可重疊執行，但加法必須等相關乘積完成後才能進行。

以下安排乘法連續執行，並在乘積備妥後穿插加法。每個輸出的四個乘法依序完成；加法採累加方式，週期表中的「前兩項相加」、「再加第三項」、「再加第四項」各代表一次加法。

核心觀念

本題考查全連接神經網路的參數數量、浮點數儲存量，以及直接對映快取的標籤與有效位元計算。直接對映快取的位址可分成區塊內位移、索引與標籤；有效位元用來標示該快取行是否存有有效資料。

解題方法

依原卷圖與題目文字，網路有 $256$ 個輸入節點、三層各 $16$ 個神經元的隱藏層，以及 $10$ 個輸出節點。每個神經元都連接前一層的所有節點；隱藏層使用 ReLU，輸出層不使用 ReLU。權重快取容量為 $1$ KiB，區塊大小為 $32$ bytes。以下計算權重與偏置，不計輸入像素。

(a) 權重、偏置與儲存量

每一層的權重數等於「前一層節點數 × 本層節點數」：

每個神經元有一個偏置，因此偏置數為：

權重與偏置皆使用 IEEE 754 單精度浮點數，每個數占 $4$ bytes，總儲存量為：

(b) 快取額外儲存需求

$1$ KiB SRAM 可容納 $1024/32=32$ 個快取區塊，因此有 $32$ 個快取行。以 $A$ 位元的 byte address 定址時，區塊內位移占 $\log_2 32=5$ 位元，索引也占 $\log_2 32=5$ 位元，故標籤占 $A-10$ 位元。每行另需 $1$ 個有效位元，總額外儲存需求為：

題目沒有指定實際位址寬度，因此額外儲存量要依 $A$ 計算。例如，若使用權重資料的 $15$ 位元相對 byte address，需求為 $32\times6=192$ bits，即 $24$ bytes；