111 年 國立成功大學資訊工程系碩士班《計算機組織與系統》

核心觀念

電腦的功率消耗可分成動態功率與靜態功率：

動態功率主要來自電路切換，常用近似式表示為：

其中 $\alpha$ 是切換活動因子。低利用率通常代表處理器較少執行工作，動態功率可能下降；但靜態功率（例如電晶體漏電）仍會消耗功率，其他硬體元件也可能持續運作。

解題方法

核心觀念

指令執行時間由指令數、平均每指令週期數（CPI）及時脈頻率決定：

MIPS 表示每秒執行的百萬條指令數：

MIPS 越高不必然代表執行時間越短；比較速度時，應以完成同一程式所需的執行時間為準。

解題方法

先分別計算兩台電腦的執行時間：

核心觀念

MIPS 的條件分支指令以「下一條指令位址」$PC+4$ 為基準，將 16 位元有號立即數左移 2 位後加上去：

因此，BEQ 的位移量以指令字為單位，範圍是 $-2^{15}$ 至 $2^{15}-1$，換算成位元組後為 $-131072$ 至 $131068$。

解題方法

已知目前 $PC=0x00000600$，分支基準位址為：

從基準位址到目標位址 $0x00002000$ 的位移為：

核心觀念

IEEE 754 單精度浮點數共 32 位元，格式為：

對正規化數，實際指數為「指數欄位的無號整數值減去偏移量 127」，有效數則包含隱含的前導 $1$。因此，正規化數的值為：

解題方法

將題目位元串依欄位拆開：

符號位 $s=0$，表示正數；指數欄位 $E=1$；小數欄位全為 $0$，所以有效數為 $1.0$。其數值為：

核心觀念

IEEE 754 單精度浮點數由 32 位元組成：1 位元符號、8 位元指數、23 位元尾數。對正規化數，其值為

其中 $s$ 是符號位元，$E$ 是以偏移量 127 編碼的指數，$f$ 是尾數欄位；最前面的隱含 $1$ 不存入尾數欄位。

解題方法

先把 $0.75$ 轉成二進位：

因此負號的符號位元為 $1$，指數欄位為

有效數字為 $1.1_2$，隱含的前導 $1$ 不存入尾數，所以尾數欄位第一位是 $1$，後面補零。正確的 IEEE 754 單精度表示為

核心觀念

這題考 VIPT（Virtually Indexed, Physically Tagged，虛擬索引、實體標記）快取與 PIPT（Physically Indexed, Physically Tagged，實體索引、實體標記）快取的差異。

快取存取通常需要兩件事：用索引選出快取組別，再比對標記確認是否命中。VIPT 在虛擬位址轉譯成實體位址的同時，先用虛擬位址的索引位元讀取快取；取得實體位址後，再用實體標記進行比對。因此，它的主要優點是縮短快取命中所需時間，讓位址轉譯與快取讀取可以部分重疊。

快取的失誤率則主要取決於快取容量、組相連度、區塊大小，以及存取的位址與資料模式。只把索引改成虛擬位址，並不會直接降低失誤率。

解題方法

判斷題目所稱的「主要優點」是否正確，先區分快取的兩種效能指標：

核心觀念

快取未命中（cache miss）常分為三類：

• 強制未命中（compulsory miss）：第一次存取某個區塊時，該區塊尚未載入快取。
• 容量未命中（capacity miss）：快取容量不足，無法同時保留程式近期需要的所有區塊。
• 衝突未命中（conflict miss）：在直接對映或組合關聯快取中，不同記憶體區塊受索引限制，只能放在特定快取位置，因而互相取代。

全相聯快取允許每個記憶體區塊放入快取中的任意一條快取列，不受固定索引位置限制。

解題方法

判斷題目中的敘述是否成立，關鍵是檢查全相聯快取是否仍有「位置映射限制」：

核心觀念

GPU 的 DRAM 存取延遲很長。GPU 隱藏這段延遲的主要方法，是同時保有大量可執行的執行緒或 warp；當某個 warp 因等待記憶體資料而停滯，排程器便切換到其他就緒的 warp 執行。

深度管線主要提高指令處理的吞吐量，並不會單靠管線深度消除或隱藏 DRAM 存取延遲。要區分「提高吞吐量」與「隱藏記憶體延遲」這兩個概念。

解題方法

判斷敘述所說的機制是否為 GPU 隱藏 DRAM 延遲的主要手段：

核心觀念

Roofline 模型用「算術強度」判斷運算效能受記憶體頻寬或運算能力限制。算術強度定義為：

單位為 FLOP/Byte。效能上限為：

其中 $P_{\text{peak}}$ 為峰值浮點運算效能，$B_{\text{mem}}$ 為記憶體頻寬。斜線代表記憶體頻寬所決定的效能上限，水平線代表峰值運算效能；兩者交會的轉折點為：

解題方法

圖中橫軸為算術強度（FLOP/Byte），縱軸為可達浮點運算效能（GFLOP/s），兩軸均採對數刻度。水平屋頂約為 $16$ GFLOP/s，轉折點約在 $1$ FLOP/Byte；

核心觀念

TLB（快取式轉譯旁查緩衝器）用來快取虛擬位址到實體位址的轉譯。TLB miss 表示「TLB 中沒有找到這筆轉譯」，不代表該虛擬頁面不在主記憶體中。

Page fault（缺頁例外）則表示頁表指出該頁面目前不在主記憶體，或存取違反頁面權限等條件。

解題方法

依序檢查 TLB 與頁表即可：

1. TLB 查不到轉譯，發生 TLB miss。
2. 硬體或作業系統接著查頁表。
3. 若頁表顯示該頁面有效且在主記憶體中，便可從頁表取得轉譯並更新 TLB，不會發生 page fault。

核心觀念

五級管線 IF、ID、EX、MEM、WB。題目以「第一條指令在第 5 週期完成」為基準，也就是指令在離開 WB 時完成；分支與 SW 雖然在 MEM／WB 沒有實際工作，仍要走完五個階段，所以每條指令的完成週期都看它的 WB。

本小題條件：

• 沒有轉送：相依指令必須等前一條指令 WB 寫回暫存器後才能在 ID 讀取（暫存器檔「前半週期寫、後半週期讀」，所以 WB 與 ID 可以在同一個週期）。
• 分支在 EX 判定、沒有延遲槽、預測跳躍：分支之後先取分支目標；EX 判定為不跳時，清除錯誤路徑上的指令，下一個週期才開始取正確的下一條指令。

解題方法

依實際執行順序排表（s 表示停在 ID 等資料、· 表示停在 IF、× 表示被清除）：

核心觀念

與上一小題相同，以「第一條指令在第 5 週期完成」為基準，每條指令在離開 WB 時完成。本小題條件改為：

• 完整轉送（full forwarding）。
• 分支在 ID 判定、沒有延遲槽、預測跳躍。

分支提前到 ID 比較暫存器，代價是比較所需的資料要更早就緒（Patterson & Hennessy 的標準結論）：

• 前一條是 ALU 指令、結果要給緊接的分支比較 → 停 1 個週期（等 ALU 結果從 EX/MEM 轉送到 ID）。
• 前一條是 LW、結果要給緊接的分支比較 → 停 2 個週期（資料要到 MEM 結束才拿得到）。

預測錯誤時，分支在 ID 判定，所以只有 IF 中那一條錯誤路徑指令要清除。

解題方法

核心觀念

直接對映快取中，每個記憶體區塊只能放在唯一的一個快取列。快取共有 $8$ 個列，且每個區塊含 $1$ 個 word，因此位址 $A$ 對應的快取列索引為

標籤則為

題目給的是 word address，且區塊大小為 $1$ word，因此不需要再將位址換算成 byte address。參照時，若該列有效且標籤相同，判定為 hit；否則為 miss，並以此位址的區塊取代該列內容。

解題方法

依照原序列逐一計算索引與標籤，再與該快取列目前儲存的標籤比較。初始時快取為空，因此第一次參照必定是 miss。

核心觀念

快取總容量為 $8$ 個字、每個區塊有 $2$ 個字，因此共有

個快取區塊。採二路組合，因此共有

個組合（set），每個組合可放 $2$ 個區塊。

對字位址 $A$：

• 主記憶體區塊編號：$\left\lfloor A/2\right\rfloor$
• 組合編號：區塊編號 $\bmod 2$
• 區塊內字位移：$A\bmod 2$

同一主記憶體區塊中的兩個字會對應到同一個快取區塊。若該區塊已在對應組合中，就是命中；否則就是失誤。組合已滿時，依 LRU 淘汰最久未使用的區塊。

解題方法

逐一將位址換算成區塊編號與組合編號，再依序更新快取內容。下表中的快取狀態以「最近使用 → 最久未使用」排列；每個組合最多容納兩個區塊。

核心觀念

這題考全相聯快取的命中判定與 LRU（最近最少使用）替換。

每個區塊含 2 個 word，因此 word 位址 $A$ 所在的區塊編號為

快取總容量為 8 words，可容納

全相聯快取允許任一區塊放在任一快取位置；若快取已滿且發生 miss，就移除最久未使用的區塊。

解題方法

先將每個 word 位址換算成區塊編號，再依序追蹤快取內容。表中的快取狀態以「LRU $\rightarrow$ MRU」排列，左側是最久未使用的區塊，右側是最近使用的區塊。

核心觀念

裝置控制器透過一組暫存器與作業系統及裝置驅動程式溝通。驅動程式發出操作命令，提供傳輸所需的資料或參數；控制器執行操作後，會更新狀態資訊，供處理器查詢或透過中斷通知。

解題方法

依照「要做什麼、要傳什麼、操作結果如何」整理控制器介面：

1. 命令：指定控制器要執行的操作，例如讀取、寫入、定位，以及啟動或停止裝置。
2. 資料與參數：寫入操作時，提供要輸出的資料；讀取操作時，控制器將裝置讀入的資料交給處理器或記憶體。驅動程式也會設定資料位置、傳輸長度等參數。
3. 狀態：控制器回報操作是否完成、裝置是否忙碌，以及是否發生錯誤。

核心觀念

本題考查 CPU 與直接記憶體存取（DMA）處理 I/O 時的成本差異，並要求依照需求目標選擇方法：

• 延遲導向重視單次 I/O 從開始到完成所需的時間。
• DMA 可讓控制器在裝置與主記憶體間傳送資料，減少 CPU 逐筆搬移資料的負擔；但啟動 DMA 需要設定控制器、傳送參數，完成後也需要通知 CPU。
• CPU-based I/O 由 CPU 直接處理 I/O，適合資料量小、重視快速完成的操作。

解題方法

題目已指出資料量小，應比較兩種方法的固定管理成本：

核心觀念

DMA 控制器直接在主記憶體與 I/O 裝置之間搬移資料，因此需要使用主記憶體的實體位址。虛擬記憶體系統則以頁表將虛擬位址轉成實體位址；若每次 DMA 傳輸都由軟體逐項處理位址轉換，會增加作業系統與處理器的負擔。

解題方法

能協助裝置進行位址轉換的硬體是 I/O 記憶體管理單元（IOMMU，Input/Output Memory Management Unit）。作業系統設定 IOMMU 的映射後，DMA 裝置可使用 I/O 虛擬位址；IOMMU 會在資料傳輸時將其轉換成實體位址，並限制裝置可存取的記憶體範圍。

核心觀念

本題考辨三種作業系統 I/O 技術：緩衝（buffering）、快取（caching）與假脫機（spooling）。判斷關鍵在於資料暫存的目的：

• 緩衝：資料正在應用程式與裝置之間傳送時，先暫存在一塊記憶體區域。
• 快取：把資料副本放在較快的記憶體中，讓後續存取比讀取原始位置更有效率。
• 假脫機：先把輸出資料存放起來，讓一次只能處理一份工作的裝置依序取用。

解題方法

逐項抓描述中的功能：

核心觀念

非同步 I/O 的重點，是讓程式送出 I/O 要求後繼續執行，不必等裝置完成傳輸；作業系統在背景處理資料傳送，藉此讓 CPU 工作與 I/O 重疊。題目列出的三種技術依序是：

• i. 緩衝（buffering）：資料傳輸期間暫存資料的記憶體區域。
• ii. 快取（caching）：保存資料副本，讓後續存取副本比存取原始資料更快。
• iii. 假離線（spooling）：先將輸出資料放入佇列，再由一次只能處理一個工作、不能交錯處理多個資料流的裝置依序輸出。

解題方法

判斷一項技術能否實作非同步 I/O，要看它能否讓程式與裝置的工作分離，使程式在裝置仍忙碌時繼續執行。緩衝區可暫存尚未完成傳送的資料；假離線則能將輸出工作排隊，讓程式不必等待裝置逐一處理。快取主要是加速資料存取，單靠快取定義本身，不能保證 I/O 可在背景非同步進行。

逐項分析

核心觀念

Swap space（交換空間）是作業系統在主記憶體不足時，用來暫存被換出頁面的磁碟空間。它可以配置在一般檔案系統中的檔案，也可以配置在獨立的磁碟分割區。

本題考查兩種配置方式的實作效率差異：使用交換檔時，作業系統需要透過檔案系統管理檔案與磁碟區塊；使用獨立分割區時，作業系統可以直接管理該區域的磁碟區塊。

解題方法

判斷效率時，著眼於交換資料的磁碟存取路徑：

• 交換檔位於檔案系統內，作業系統須處理檔案系統的配置與區塊對應等管理工作，才能定位資料。

核心觀念

本題考查多重程式度與抖動（thrashing）。多重程式度是同時留在系統中、等待或使用 CPU 的程序數量。程序增加時，每個程序可分配到的實體記憶體頁框可能減少；當程序的工作集無法留在主記憶體中，就會頻繁發生缺頁。

解題方法

固定的交換空間（swap space）無法隨程序數量增加而擴充。多重程式度提高後，系統需要同時支援更多程序的記憶體內容；若主記憶體不足以容納這些程序的工作集，作業系統便會頻繁將頁面換入、換出。

換頁頻率升高會占用大量 I/O 時間，使 CPU 花更多時間等待頁面載入，實際執行程序的時間反而減少。若作業系統因 CPU 使用率下降而再引入更多程序，記憶體壓力與缺頁率會進一步升高，形成惡性循環。這種系統大部分時間都在換頁、而非執行程序的現象，就是抖動。

核心觀念

工作集模型（working-set model）用每個行程近期使用的頁面集合，估計它目前需要的實體頁框數。三個行程的總頁框需求為

當總需求超過系統可供這些行程使用的實體頁框數時，行程無法同時保有各自的工作集，缺頁率會上升，可能導致顛簸（thrashing）。作業系統可暫停一個行程，釋出其頁框，讓其他行程保有工作集。

解題方法

比較三個行程的工作集總和與可用實體頁框數。若題目中的 $d$ 代表可用實體頁框數，則暫停行程的條件是：

核心觀念

本題考磁碟排程的目標：在多個 I/O 請求同時等待時，安排磁頭服務請求的順序，以減少磁頭移動距離，進而降低尋道時間並提升 I/O 效率。

若磁頭從磁柱 $x_i$ 移至 $x_{i+1}$，總磁頭移動量為：

在磁碟轉速與資料傳輸量相同時，磁頭移動量較小，通常代表平均尋道時間較短、吞吐量較高。

解題方法

多工環境下有多個 I/O 程序並行，請求常會同時排在佇列中。排程器可依磁頭位置與請求所在磁柱調整服務順序，因此應比較各方法能否減少磁頭來回移動。

• FCFS：依請求到達順序服務。順序公平且簡單，但不考慮磁頭位置，可能使磁頭在磁碟各處反覆移動。
• SCAN：磁頭沿一個方向服務沿途請求，到達磁碟端點後反向掃描。請求可依磁柱位置批次服務，通常比 FCFS 減少移動。
• LOOK：與 SCAN 相同方向掃描並在途中服務請求，但不必走到磁碟物理端點；到該方向最遠的待服務請求後便反向。這可省下沒有請求時的空行程。

核心觀念

磁碟排程是在多個待處理 I/O 請求中，決定磁碟讀寫頭下一個服務哪一筆，以減少尋道時間、提升效能。常見方法包括 FCFS、SSTF，以及 SCAN／C-SCAN 等掃描式演算法。

當佇列中通常只有一筆待處理請求時，演算法沒有可供比較的其他請求：FCFS 依到達順序服務；SSTF 沒有其他請求可挑選；SCAN 類演算法也沒有其他排隊請求可依讀寫頭移動方向重新排序。因此，所有方法都會依請求到達順序服務，效果等同 FCFS。《作業系統概念》第 10 版

解題方法

判斷重點是「排程器每次決定下一筆工作時，有幾筆請求可選」。佇列大小為一時，每次只有唯一選擇，無從藉由重新排列請求來縮短磁碟頭移動距離。