110 一般警察特考二等 刑事警察人員數位鑑識組 計算機系統(包括計算機結構、作業系統) 考古題詳解
第 一 題20 分
有一 DMA（direct memory access）模組正在使用循環偷竊（cycle stealing），企圖從 傳輸速率的設備將字元（characters）傳輸到記憶體中。若 CPU 正在以每秒一百萬個指令（MIPS）的速率擷取（fetch）指令，則此 DMA 模組將使得處理器減慢多少速度？（假設 CPU 只擷取指令，未處理資料的讀寫。）
登入後即可作答並保存紀錄。
核心觀念
本題考查 DMA（直接記憶體存取）的循環偷竊（cycle stealing）對 CPU 指令擷取速率的影響。循環偷竊是指 DMA 每傳輸一個字元，就占用一個記憶體週期；該週期原本可供 CPU 擷取指令，因此 CPU 的指令擷取速率會依 DMA 占用的週期比例下降。
題目未提供每個字元的位元數，因此依此類題型的標準假設，一個字元為 位元。
解題方法
設備傳輸速率為 ，換算成每秒傳輸的字元數：
第 二 題20 分
有一計算機系統（computer system）包含 個 -bit 單字（word）的主記憶體（main memory），同時具有 -word 快取記憶體（cache memory）。此快取記憶體分割以每組（set）有 個槽（slot）為單位，每個槽包含 個單字。
假設快取記憶體最初是空的，CPU 開始從位置（locations）、、、、 依序擷取（fetch）單字。若使用快取記憶體重複執行前述的依序擷取 次，則估計可改善執行時間多少？假設快取記憶體的速度比主記憶體快 倍，區塊替換（block replacement）使用 LRU（least recently used）策略。
登入後即可作答並保存紀錄。
核心觀念
本題考查組合關聯式快取記憶體的位址映射、區塊命中與失誤，以及 LRU 替換策略對重複循序存取的影響。
主記憶體每區塊有 個字，因此共有
快取有 個字，每槽可存一個區塊，因此共有 個槽。每組有 個槽，故快取共有 組。主記憶體區塊編號 映射至第 組；每組最多容納 個區塊。
解題方法
CPU 每次循序擷取位置 至 ，含首尾，共擷取
範圍涵蓋主記憶體區塊 至 ：
因此每次循序擷取會碰到 個區塊，重複 次的總字數擷取次數為
第一次擷取時，快取為空，碰到的 個區塊各發生一次區塊失誤。其後，區塊 至 映射到 組：其中第 至第 組各有 個不同區塊競爭，但每組只能容納 個；其餘 組各有 個區塊，可全部留在快取中。
每次循序掃描時，同一組的區塊會依固定順序被存取。對前 組而言， 個區塊競爭 個槽，套用 LRU 後，下一輪再次存取時仍會逐一失誤。
第 三 題20 分
如果單獨執行 I/O 綁定的程式（I/O-bound program），其花費在等待 I/O 的時間會比使用處理器（processor）多，而處理器綁定的程式（processor-bound program）剛好相反。假設短期排程演算法（short-term scheduling algorithm）適合最近使用較少處理器時間的程式。請說明為什麼此演算法偏好 I/O 綁定程式，卻沒有永久性地拒絕處理器時間（processor time）給處理器綁定程式。
登入後即可作答並保存紀錄。
核心觀念
本題考查短期排程的偏好與**飢餓（starvation）**的差別。I/O 綁定程式大多在等待 I/O，短暫使用處理器後便會離開執行狀態；處理器綁定程式則會連續使用處理器較長時間。
短期排程器從就緒佇列選擇下一個取得處理器的程式。若排程演算法偏好最近使用較少處理器時間的程式，I/O 綁定程式通常較容易被選中；但「較受偏好」不等於「其他程式永遠無法被選中」。
解題方法
以兩類程式的處理器使用型態，說明排程器如何在偏好 I/O 綁定程式的同時，仍讓處理器綁定程式取得處理器時間：
- I/O 綁定程式執行一小段處理器工作後，通常便提出 I/O 要求並等待。它離開就緒狀態後，短期排程器便能選擇其他就緒程式。
- 處理器綁定程式即使因近期使用較多處理器時間而較不受偏好，只要持續留在就緒佇列，仍會參與後續排程。
第 四 題20 分
請說明快取系統（cache system）中直接映射（direct mapping）、關聯映射（associative mapping）和集關聯映射（set-associative mapping）之間有何不同？
登入後即可作答並保存紀錄。
核心觀念
本題考查快取記憶體如何將主記憶體區塊放入快取，以及如何依記憶體位址查找資料。三種映射方式的主要差異是：區塊可放置的位置有多少、查找時如何比對標籤，以及替換策略的複雜度。
快取位址通常可分為「標籤（tag）」、「索引（index）」及「區塊內位移（block offset）」。快取命中時，索引先選出快取行或集合，再比對標籤；區塊內位移則指定要讀取區塊中的哪個位元組或字。
解題方法
比較三種映射時，先看主記憶體中的一個區塊能放進快取的哪些位置，再看查找和替換方式：
| 映射方式 | 區塊可放置位置 | 查找方式 | 替換方式 |
|---|---|---|---|
| 直接映射（direct mapping） | 唯一的一條快取行 | 依索引選定一行，再比對標籤 | 若該行被新區塊占用，直接覆蓋 |
| 全關聯映射（fully associative mapping） | 快取中的任意一行 | 同時比對各行標籤 | 從整個快取中選一行替換 |
| 集關聯映射（set-associative mapping） | 指定集合內的任意一行 | 依索引選集合，再比對集合內各行標籤 | 從該集合內選一行替換 |
設快取共有 條行， 路集關聯的集合數為 。主記憶體區塊編號為 時：
第 五 題20 分
有一管線機（pipeline machine）分四個階段執行一個指令，第 1 階段需要 （nanosecond, ns），第 2 階段需要 ，第 3 階段需要 ，第 4 階段需要 。該管線如下所示（假設沒有其他延遲）：
| 階段 | Stage 1 | Stage 2 | Stage 3 | Stage 4 |
|---|---|---|---|---|
| 時間 |
若以此管線來完成 個指令需要多少時間？
登入後即可作答並保存紀錄。
核心觀念
管線處理器會讓不同指令同時位於不同階段。管線時脈週期須配合最慢的階段，因此週期時間為：
解題方法
完成第一個指令需要先填滿 4 個階段；管線填滿後，每個週期可再完成 1 個指令。完成 個指令所需週期數為：