112 中正資工所考古題詳解｜硬體考點分析

題型與配分

全卷 4 頁、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。卷面沒有倒扣規定。

I. 單一選擇題（25%）

• 第 I-1 題｜五個含 CPU burst 與 I/O burst 的 process（P1–P5，有到達時間），用能讓平均 waiting time 最小的最佳 scheduling 演算法，在時間 23 時執行的是哪個 process
• 第 I-2 題｜unified virtual memory 用哪一種機制同時 cache process 頁面與檔案資料
• 第 I-3 題｜關於 MIPS（每秒百萬指令）的敘述，哪一項為真
• 第 I-4 題｜關於 floating point 加法、右移、乘除法硬體、Booth 演算法與 overflow 的敘述，哪一項為真
• 第 I-5 題｜關於 RISC 與 CISC 的敘述，哪一項為假

II. 多重選擇題（25%）

• 第 II-1 題｜哪些敘述不正確：檔名存放位置、mounting 點、重複使用資料的暫存技術、DMA 控制器、作業系統是否知道磁碟幾何
• 第 II-2 題｜哪些是硬體式的 synchronization 工具（CAS 指令、Peterson 解法、DMA、Banker's algorithm、MMU）
• 第 II-3 題｜哪些情況一定會引發 context switch
• 第 II-4 題｜一段含 lw、add 的 MIPS 程式（圖 1），五級 pipeline 中有哪些 dependence 或 hazard（structural、data、data dependency、output dependency、control）
• 第 II-5 題｜哪些技術可以解決圖 1 的 hazard（forwarding、code interchanging、delayed branch、register renaming、loop unrolling）

III. 填空題（50%）

• 第 III-1 題｜過去 IBM PC 的磁碟用 24 位元 CHS 位址定址（10 位元 cylinder、8 位元磁頭、6 位元 sector），每個 sector 512 bytes。(a) 磁碟的最大容量。(b) 給定七個以十六進位 CHS 位址表示的 I/O 請求（1AC320、A2F5BC、7A182D、EF6714、F0D76、C0F1D1、FF2236），用 C-SCAN scheduling 時的 seek distance（cylinder 數，十進位）
• 第 III-2 題｜給一段 Linux kernel（/mm/filemap.c）說明鎖順序（lock ordering）的註解，事先規定鎖的順序主要是為了破除 deadlock 的哪個條件。(c)
• 第 III-3 題｜給五個工作（T0–T4）、四種資源（A–D，各有 6、7、6、10 個實例）的 Allocation 與 Max Required 表。(d) OS 能立即批准 T0 要求的各資源最大數量
• 第 III-4 題｜(e) 用多顆磁碟來解決儲存系統效能與可靠度問題的技術
• 第 III-5 題｜(f) 某個 IEEE 754 single precision 表示（符號 1、指數 01111110、尾數 11000000000000000…）的十進位值
• 第 III-6 題｜指令 cache miss rate 3%、資料 cache miss rate 5%，沒有 stall 時 CPI 為 2，miss penalty 100 週期，35% 的指令存取資料 cache。(g) 與永遠 hit 的完美 cache 相比的 speedup
• 第 III-7 題｜5 GHz 機器、CPI 為 1.0、cache miss rate 2%、DRAM 存取時間 100 ns。(h) 平均記憶體存取時間。(i) 加入存取時間 5 ns 的 L2 cache 並使整體 main memory miss rate 降到 0.5% 後的平均記憶體存取時間
• 第 III-8 題｜要做兩個加總，一個是兩個純量變數相加，一個是兩個 1000×1000 2D array 的矩陣相加。(j) 使用 1000 個處理器時的 speedup

作答時要注意的地方

1. 第 II 部分每題所有答案都符合才算分，卷面沒有倒扣規定。
2. 第 III 部分不需要作答過程，每個答案要標明題號與空格編號，每格 5 分。
3. 第 III-1 題的 I/O 請求是以十六進位 CHS 位址表示，答案要寫十進位數字。
4. 第 III-7 題兩個空格分別問加入 L2 前後的平均記憶體存取時間。

準備方向

• 含 I/O burst 的 scheduling（112 第 I-1 題），114 填空第 4 題也有。
• unified virtual memory 用 page cache（112 第 I-2 題），110 第 1(3) 題、成大 112 第 1(4) 題也有。
• Banker's algorithm（112 填空第 3 題），109 第 4 題、110 第 4 題也有。
• IEEE 754（112 填空第 5 題），108 第 8 題、109 第 9 題、110 第 10 題也有。
• RAID（112 填空第 4 題），108 第 1(2) 題、114 填空第 8 題也有。
• pipeline hazard（112 多選第 4、5 題），111 第 4 題、113 第 6 題、114 填空第 3 題也有。
• CPU 效能方程式與 cache miss 的 CPI（112 填空第 6 題），109 第 8 題、111 第 3 題、113 第 5 題也有。
• 平均記憶體存取時間與多層 cache（112 填空第 7 題），114 填空第 1、2 題也考 cache。
• RISC 與 CISC（112 單選第 5 題）、平行處理的 speedup（112 填空第 8 題）。
• 磁碟 CHS 定址與 C-SCAN（112 填空第 1 題）、Linux kernel 鎖順序（112 填空第 2 題）。