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

核心觀念

程式的 CPU 執行時間可用下式計算：

$$\text{CPU 執行時間} = \text{執行的時脈週期數} \times \text{時脈週期時間}$$

時脈週期時間是時脈頻率的倒數：

$$\text{時脈週期時間} = \frac{1}{\text{時脈頻率}}$$

因此，執行時間也可寫成「時脈週期數 ÷ 時脈頻率」。衡量效能時，執行時間越短，效能越好；評估系統則應盡量使用真實應用程式。

解題方法

逐項檢查敘述是否符合效能評估原則。關鍵在於分辨「時脈頻率較高」與「程式執行時間較短」並不等價：執行時間還受到程式所需週期數影響。

選項分析

核心觀念

本題考查記憶體階層中各類儲存資源的實作方式，以及由誰管理或配置。判斷時要區分硬體實作與軟體管理：

• **快取記憶體（Cache）**容量小、速度快，通常以 SRAM 實作。
• **主記憶體（Main memory）**容量較大，通常以 DRAM 實作。
• **虛擬記憶體（Virtual memory）**由作業系統管理，利用主記憶體與次級儲存裝置共同提供較大的位址空間。
• **暫存器（Registers）**位於處理器內，指令會指定使用哪些暫存器；實際的暫存器配置通常由編譯器負責。

解題方法

逐一核對各選項的「通常實作材料」或「通常管理者」。前三種記憶體資源的描述都符合一般計算機組織觀念；再檢查暫存器的配置工作，判斷是否通常由程式設計師直接負責。

選項分析

核心觀念

編譯器的程式碼生成，會把中間表示式轉成目標機器指令，並安排暫存器、運算指令與資料存取方式。架構若提供較多可用暫存器、足夠的運算指令與彈性的定址方式，通常能讓編譯器更容易產生有效率的機器碼。

本題將 (C) 的「Variable instructions」解讀為指令長度或指令格式可變。指令長度可變並不直接提供有利於編譯器的運算或資料操作能力，反而會增加指令位置與分支位移的計算複雜度。

解題方法

逐一判斷各架構特性是否能幫助編譯器把運算映射到機器指令，或減少暫存器不足、資料存取等程式碼生成負擔。若某特性主要讓指令編碼或程式布局更複雜，卻沒有直接改善程式碼生成能力，就是題目要找的選項。

選項分析

• (A) More registers：錯誤。 可用暫存器較多時，編譯器能把更多變數與中間結果留在暫存器中，減少將資料暫存到記憶體再載回的次數，通常有助於產生更有效

核心觀念

分散式檔案系統（DFS）讓使用者透過一致的檔案介面，存取分散在多台網路節點上的檔案。其核心目標是提供位置透明性：使用者不必知道檔案實際存在哪一台伺服器，也能以一致的方式查找與使用檔案。

快取、複製與網路最佳化也可能是 DFS 的功能，但它們分別著重於效能、可靠性與通訊效率，並非 DFS 的主要目的。

解題方法

先辨認題目詢問的是 DFS 的「主要功能」，再區分系統的核心抽象與實作上的附加機制。若選項描述的是讓分散各處的檔案看起來像能透過同一套檔案服務管理與存取，便符合 DFS 的核心目的；若只談快取、複製或降低通訊成本，則是在描述可能採用的改善手段。

選項分析

核心觀念

本題考互斥（mutual exclusion）：當多個執行緒需要存取同一個共享資源時，必須限制同一時間只有一個執行緒進入臨界區（critical section），避免競爭條件與資料不一致。

**互斥鎖（mutex）**用來達成這項限制。執行緒取得鎖後才能進入臨界區；其他執行緒若嘗試取得同一把鎖，會被阻塞，直到持鎖執行緒釋放鎖。

解題方法

先找出題目的兩個關鍵條件：同一時間只能有一個執行緒存取，以及其他執行緒會等到資源釋放。這描述的是互斥鎖的行為。

操作流程如下：

1. 執行緒進入臨界區前呼叫 lock。
2. 若鎖目前未被持有，該執行緒取得鎖並進入臨界區。
3. 若鎖已被持有，其他執行緒會等待。
4. 持鎖執行緒離開臨界區後呼叫 unlock，等待中的執行緒才有機會取得鎖。

選項分析

核心觀念

DMA（Direct Memory Access，直接記憶體存取）讓 I/O 裝置與主記憶體之間直接傳送資料，不必由 CPU 逐筆讀取裝置資料，再逐筆寫入記憶體。

傳輸前，CPU 仍須設定 DMA 控制器，例如資料來源、目的位址與傳輸長度；傳輸完成後，DMA 控制器通常會以中斷通知 CPU。DMA 的核心目的，是減少 CPU 參與資料搬移的工作，讓 CPU 能在傳輸期間執行其他工作。

解題方法

判斷題目問的是 DMA 的「關鍵目的」，應先辨認它的主要機制：由 DMA 控制器負責裝置與主記憶體之間的資料傳輸，避免 CPU 逐筆搬移資料。

因此，直接描述這項機制的選項最符合題意。CPU 可在 I/O 傳輸期間處理其他工作，是 DMA 帶來的效益；校驗和與即時監控則不是 DMA 的核心功能。

選項分析

核心觀念

分支預測器在條件分支尚未確定結果時，先預測分支是否成立及下一個程式計數器（PC），讓處理器能繼續取指與執行。預測正確可減少控制冒險造成的停頓；預測錯誤則須清除錯誤路徑上的指令並重新取指。

• 1-bit 預測器：記錄該分支上一次的結果，預測本次結果與上次相同。
• 2-bit 飽和計數器預測器：以四種狀態表示偏向「不跳」或「跳」，通常需連續兩次相反結果才會改變預測方向，因此較不容易被單次例外翻轉。

解題方法

逐項檢查敘述是否適用於所有情況。特別是含有「always」的敘述，需確認是否存在能推翻它的反例。另須區分預測器的準確率與分支指令的執行頻率：減少分支次數能改善效能，但不一定提高每次預測的準確率。

選項分析

(A) 正確。
分支預測可讓處理器在分支結果尚未確定前，先沿預測路徑執行，減少等待分支判定的時間，因此有助於緩解控制冒險。

核心觀念

本題考查負數的二進位表示、位元擴展，以及以較小位元寬度的 ALU 組成較大位元寬度的 ALU。

對 $n$ 位元數值：

• 反碼（一補數）：負數由正數逐位反轉得到。它有正零與負零兩種表示。
• 補數（二補數）：負數由正數逐位反轉後再加 $1$ 得到；零只有一種表示，是現代電腦常用的有號整數表示法。
• 零擴展：在高位補 $0$，適用於保留無號數值。
• ALU 位元切片：可將多個較窄的 ALU 串接，組成較寬的 ALU；低位切片產生的進位會傳給高位切片。

解題方法

逐項判斷敘述是否符合上述定義。特別留意兩個容易混淆的地方：一補數有兩個零；零擴展適用於無號數，若要保留有號二補數的負值，應使用符號擴展。

選項分析

(A) About negative numbers, one’s complement representation is better than two’s complement.

錯。一補數表示負數時，需處理正零與負零兩種表示；二補數則只有一種零，且可直接使用一般加法器完成加減運算，因此二補數通常較適合電腦中的整數運算。一補數並沒有比二補數更好的普遍優勢。

(B) One’s complement has only one zero.

錯。一補數有兩種零。以 4 位元為例：

$$+0 = 0000,\qquad -0 = 1111$$

因此，一補數不是只有一個零；只有二補數具備唯一的零表示。

核心觀念

本題考查現代檔案系統常見的管理功能。檔案系統負責組織檔案與目錄、管理檔案中繼資料，並在系統異常時維護資料一致性。不同檔案系統的功能有所差異；判斷時應區分檔案系統的基本功能、常見擴充功能，以及分散式儲存系統才特別需要的功能。

解題方法

逐項檢視各敘述是否屬於一般現代檔案系統常見的功能。目錄階層是檔案組織的基本方式；日誌則是常見的當機復原機制。檔案版本管理與跨節點複寫都不是一般檔案系統必備的通用功能。

選項分析

• (A) Journaling（日誌）— 正確。
  日誌式檔案系統會先把即將進行的中繼資料變更記錄到日誌，再套用至檔案系統。若系統在更新途中當機，復原時可依日誌完成或回復操作，降低檔案系統損毀的風險。這是現代檔案系統常見的功能。

核心觀念

本題考作業系統使用**中斷（interrupt）**處理 I/O 的優點。裝置完成 I/O、需要服務時，會送出中斷訊號；CPU 暫停目前工作，保存必要狀態，轉去執行中斷服務程式，處理完後再回到原工作。

輪詢（polling）需要 CPU 反覆檢查裝置狀態；中斷則讓裝置在事件發生時通知 CPU。因此，中斷能減少等待期間的無效檢查，也支援非同步事件通知。

解題方法

判斷各選項時，檢查它是否符合中斷的作用：事件發生時通知 CPU、讓 CPU 不必持續等待，並能及時處理 I/O 事件。中斷機制本身不會保證延遲為零，也不必然簡化裝置驅動程式。

選項分析

(A) 正確。 相較於輪詢，中斷可在 I/O 事件發生時通知 CPU，不必等到下一次輪詢才發現事件，因此有助於降低事件回應延遲。

核心觀念

快取記憶體與主記憶體之間以「區塊」為單位對應。主記憶體會被切分成固定大小的區塊，快取則切分成相同大小的快取列；每個主記憶體區塊載入快取後，存放在其中一個快取列。

解題方法

題目問的是快取與主記憶體之間的 mapping unit（對應單位）。

核心觀念

直接對映快取中，每個區塊除了儲存資料，還需要儲存標籤（tag）與有效位元（valid bit）。總位元數為：

$$\text{總位元數} = \text{資料位元數} + \text{標籤位元數} + \text{有效位元數}$$

本題未另外指定字組大小，依常見假設，每個 word 為 32 位元，也就是 4 bytes。

解題方法

快取資料容量為 $128\text{ K bytes}=2^{17}$ bytes；每個區塊有 4 個 word，每個 word 為 4 bytes，因此區塊大小為 $16$ bytes。快取區塊數為：

$$\frac{2^{17}\text{ bytes}}{4\times 4\text{ bytes}} = 2^{13}\text{ blocks}$$

位址分成標籤、區塊索引與區塊內位移：

核心觀念

本題考查五級管線中的資料相依與 RAW（Read After Write，先寫後讀）危障。五個階段依序為：

$$\text{IF} \rightarrow \text{ID} \rightarrow \text{EXE} \rightarrow \text{MEM} \rightarrow \text{WB}$$

若後續指令要讀取的暫存器，尚未由前一指令寫回，就會發生 RAW 危障。可用資料轉送（forwarding，也稱 bypassing），把運算結果直接送到後續指令的執行階段，避免等待寫回暫存器。

以下採用標準假設：指令依序執行、沒有資料轉送；暫存器在 WB 階段前半寫入、ID 階段後半讀取。

解題方法

第一條 add 將結果寫入 $2，後面三條指令都會讀取 $2：

• and $12, $2, $5：讀取 $2
• sub $13, $6, $2：讀取 $2
• or $14, $2, $2：讀取 $2

因此，三條指令都對第一條 add 有 RAW 相依。沒有資料轉送時，最早的讀取者是第二條 and。它在 ID 階段需要讀取 `

核心觀念

本題考查可搶先式最短剩餘時間優先排程（SRTF）。每當新行程抵達或有行程完成 I/O 返回就緒佇列時，CPU 會執行「目前 CPU burst 剩餘時間最短」的行程；若較短的行程進入就緒佇列，便會搶先執行。

等待時間只計算行程在就緒佇列中等待 CPU的時間，不包含 CPU 執行時間，也不包含 I/O 時間。可用下式驗算：

$$等待時間 = 完成時間 - 抵達時間 - CPU\ 執行時間總和 - I/O\ 時間總和$$

解題方法

逐一追蹤 CPU burst 的剩餘時間，以及行程完成第一段 CPU burst 後的 I/O 與返回就緒時間：

• $0$–$5$：只有 $P1$ 就緒，執行第一段 CPU burst。$P2$ 在 $t=2$ 抵達時，$P1$ 剩餘 $3$ ms，短於 $P2$ 的 $6$ ms；$P3$ 在 $t=4$ 抵達時，$P1$ 剩餘 $1$ ms，也短於 $P3$ 的 $8$ ms，因此 $P1$ 持續執行。$P1$ 於 $t=5$ 進入 I/O，至 $t=9$ 返回。
• $5$–$11$：$P2$ 的第一段 burst 為 $6$ ms，短於 $P3$ 的 $8$ ms，因此執行至完成。$P2$ 於 $t=11$ 進入 I/O，至 $t=14$ 返回。
• $11$–$18$：此時 $P1$ 返回後的第二段 burst 為 $7$ ms，$P3$ 尚有第一段 burst $8$ ms，因此先執行 $P1$。$P2$ 在 $t=14$ 返回時有 $5$ ms，但當時 $P1$ 剩餘 $4$ ms，故 $P1$ 繼續執行至 $t=18$。
• $18$–$23$：$P2$ 的第二段 burst 為 $5$ ms，短於 $P3$ 尚未執行的 $8$ ms，因此先執行 $P2$。

核心觀念

多層頁表會將虛擬位址切成各層索引與頁內位移。每層索引用來選出該層頁表中的一個頁表項目（PTE）；若每個 PTE 為 4 bytes，索引為 $i$ 的 PTE 位址為：

$$\text{PTE 位址}=\text{該層頁表基底位址}+i\times 4$$

本題的位址欄位依序為第一層索引 10 bits、第二層索引 10 bits、第三層索引 6 bits，以及位移 6 bits。題目給的位址以 32-bit 表示時，前面補上兩個十六進位的 $0$：$0x001A3F5C$。

解題方法

依欄位位置取出各層索引：

• 第一層索引是位元 $[31:22]$。$0x001A3F5C$ 的這 10 bits 為 $0$。
• 第二層索引是位元 $[21:12]$：

$$(0x001A3F5C \gg 12)\ \&\ 0x3FF=0x1A3$$

• 第三層索引是位元 $[11:6]$：

$$(0x001A3F5C \gg 6)\ \&\ 0x3F=0x3D$$

核心觀念

這題考計數型 semaphore（counting semaphore）如何表示可用資源數量。資料庫連線池最多有 4 個連線，因此 semaphore 初值為 $4$。

每個執行緒成功取得一個連線時，執行一次 wait（或 P）操作，計數值減 $1$；釋放一個連線時，執行一次 signal（或 V）操作，計數值加 $1$。

解題方法

先從初值 $4$ 開始計算：

核心觀念

LRU（Least Recently Used，最近最少使用）會在頁框已滿且發生缺頁時，淘汰「距離現在最久沒有被使用」的頁面。

每次參考一個頁面時：

• 若頁面已在頁框中，稱為命中；不增加缺頁次數，但要更新該頁面的最近使用時間。
• 若頁面不在頁框中，稱為缺頁；若頁框已滿，就淘汰最近最少使用的頁面，再載入新頁面。

解題方法

依序處理參考字串，逐次記錄三個頁框中的頁面。發生缺頁時，若頁框已滿，就比較各頁面最近一次出現的位置，淘汰最早出現的那一頁。

次序	參考頁面	頁框 A	頁框 B	頁框 C	結果
1	7	7	—	—	缺頁
2	0	7	0	—	缺頁
3	1	7	0	1	缺頁
4	2	2	0	1	缺頁，淘汰 7
5	0	2	0	1	命中

核心觀念

RAID 0+1（mirror of stripes）：先把硬碟分成兩組做條帶化（RAID 0），再把兩組互為鏡像（RAID 1）。8 顆硬碟就是兩組各 4 顆的條帶組，資料在兩組各存一份。

• 一組條帶組（RAID 0）中任一顆硬碟故障，整組就失效。
• 只要還有一組條帶組完好，就能從它讀到全部資料。

題目所說「provided that no entire striped set fails」，意思是故障不能讓兩組條帶組都失效（至少保留一組完整的條帶組）。

解題方法