112 交大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 9 頁、34 題、100 分，不可使用計算機，請用答案卡作答。

這一年的題組明文寫出各題組下的小題為單選。計分沿用 110 年起的答錯 −1、扣至整科 0 分。

OS 出現在第 1–10 題與題組 A、B，計組出現在第 11–20 題與題組 C、D。

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜page replacement：四個選項涵蓋 Belady's anomaly 在 FIFO 與 LRU 上的可能性、哪一種演算法的 page fault 數最少、加大 TLB 對 replacement 次數有沒有影響
• 第 2 題（4%）｜64 MB shared memory：四個選項涵蓋兩個 process 必不必須用相同的 virtual address 範圍、一方設成唯讀會不會限制另一方、shared memory 能不能被換出、實際配置的 physical memory 會不會少於宣告的大小
• 第 3 題（4%）｜DMA：四個選項涵蓋 DMA 讓誰直接存取 main memory、它會不會拖慢 CPU 密集程式、與 DMA 完成同步的兩種方式
• 第 4 題（4%）｜把檔案從 /x/f 搬到 /y/f 哪些步驟不能省。選項有在 y 建立項目、刪除 x 中的項目、重新配置資料 block、複製內容等
• 第 5 題（4%）｜要讓 file system 產生非連續資料 block，哪些操作是必要的
• 第 6 題（4%）｜process：四個選項涵蓋建立 child process 後 parent process 的兩種選擇、產生太多 child process 會耗盡什麼資源、同 process 的 thread 能不能在不同 core 同時跑、深度遞迴消耗的是 heap 還是 stack
• 第 7 題（4%）｜看 Gantt chart 反推 scheduling 演算法：五個 process 在 18 ms 內完成。要檢驗 RR、non-preemptive SJF、preemptive SJF 三者能不能產生這張圖。最後一小題再問某個 process 的 waiting time
• 第 8 題（4%）｜兩條 thread 各累加 10000 次而沒有鎖：四個選項涵蓋輸出是不是總是等於兩者之和、有沒有可能只差一、調換 pthread_join 的順序有沒有用
• 第 9 題（4%）｜condition variable：四個選項涵蓋 pthread_cond_wait() 是 busy waiting 還是睡眠等待、它的參數裡為什麼要帶一個 mutex、pthread_cond_signal() 喚醒幾條 thread、呼叫 signal 之後呼叫者會不會立刻讓出 CPU
• 第 10 題（4%）｜用不等式判斷 deadlock 與 safe state：m 個資源、4 條 thread，x_i 是最大需求、y_i 是目前持有。要判斷四個不等式各自能否推出 deadlock 或安全

計算機結構（11–20）

• 第 11 題（4%）｜single-cycle 對五級 pipeline：四個選項涵蓋兩者的執行時間比較、pipeline 的 critical path 是不是總是比較短、硬體資源的多寡、兩者的 CPI 高低
• 第 12 題（4%）｜哪些去除 hazard 的技術需要編譯器協助：選項涵蓋 delayed branch、load-use hazard 的消除、動態 branch prediction、forwarding
• 第 13 題（4%）｜ll 與 sc 這對指令：四個選項涵蓋 ll 到底有沒有鎖住記憶體格、什麼情況會讓 sc 失敗、給的程式片段有沒有 bug、它與 atomic swap 指令的效率比較
• 第 14 題（4%）｜看簡化的 MIPS datapath 圖：四個選項涵蓋一段程式碼能不能測出某條 control signal stuck-at-0 的故障、這個實作會不會有 load-use hazard、指令記憶體與 register file 各自需不需要是 synchronous 元件
• 第 15 題（4%）｜無 forwarding、無 branch prediction、分支在 ID 級解析的五級 pipeline：程式是一個迴圈（addi → lw → subi → sw → bne）。要判斷哪些 bubble 加上 forwarding 就能消除、哪些不行、$t3 = 100 時 CPI 是否大於 2.5、除了 PC 的 adder 外至少還要幾個 adder、加上靜態 branch predictor 會讓 CPI 變好還是變差
• 第 16 題（4%）｜cache：四個選項涵蓋 virtually addressed 與 physically addressed cache 的速度比較、高 associativity 減少的是哪一種 miss、處理器變快之後 cache 效能是更重要還是更不重要、加大 block 利用的是哪一種 locality
• 第 17 題（4%）｜指令組合的執行時間與加速上限：2 GHz，四類指令各給指令數與 CPI。後續小題問只改善其中一類指令能不能快兩倍、綜合改善後的執行時間
• 第 18 題（4%）｜記憶體 stall 對 CPI 的影響：給 miss penalty、I-cache 與 D-cache 的 miss rate、lw/sw 比例與無 stall CPI，並有 clock 加倍但記憶體時間不變的情境。最後一小題問只給 I-cache 加 L2 之後的 CPI
• 第 19 題（4%）｜循序 traverse int A[256] 的 miss 數與 hit rate（direct-mapped、總資料 8192 bytes、block 16 bytes）。最後一小題問 block size 加倍後 miss 數與 miss rate 各往哪個方向走
• 第 20 題（4%）｜兩個處理器對 a、b 的讀改寫：P1 做 a++; b++;、P2 做 a=2; b=b+2;，初值皆 0。要分別判斷有、沒有 cache coherence 下 a、b 的可能值

題組（21–34，20 分）

• 題組 A（21–23，5%）｜四顆 1 TB 磁碟組成 RAID 5
• 第 21 題｜最大容量
• 第 22 題｜最多容忍幾顆磁碟故障
• 第 23 題｜最壞情況下寫入單一位元組會牽涉幾顆磁碟
• 題組 B（24–27，5%）｜三個 process P、Q、R 的 message passing：P 送給 Q、Q 送給 R、R 送給 P，而接收端分別是 R、P、Q
• 第 24 題｜這是哪一種命名方式
• 第 25 題｜支援這種通訊需要什麼資料結構
• 第 26 題｜哪種條件會造成 deadlock
• 第 27 題｜哪個條件能確保每個 process 都在收到訊息後才繼續
• 題組 C（28–30，5%）｜從 MIPS assembly 反推 C 函式：assembly 中 move $s1,$a2、move $s0,$a3、兩次 jal func、中間 move $a0,$v0 與 add $a1,$s0,$s1
• 第 28 題｜由 assembly 推斷 my_call() 有幾個參數
• 第 29 題｜函式體是哪一段 C
• 第 30 題｜尾呼叫最佳化能省幾道指令
• 題組 D（31–34，5%）｜2-way、四字 block、LRU 的 cache：總資料 32 words、24-bit 位元組位址
• 第 31 題｜tag 位元數
• 第 32 題｜cache 總大小（資料加上每個 block 的 tag 與 valid）
• 第 33 題｜字位址序列 24, 8, 25, 10, 41 的 hit 與 miss
• 第 34 題｜其中幾次是 compulsory miss

作答時要注意的地方

1. 題組各小題為單選，但仍是組內全對才給 5 分。
2. 複選題答錯 −1，下限是整科 0 分。
3. 第 18 題有 clock 加倍但記憶體時間不變的情境，並要算 speedup。
4. 題組 C 給的 assembly 中有兩層巢狀呼叫。

準備方向

• RAID 5 的容量、容錯與 small write（112 題組 A）。
• message passing 的 blocking 與 non-blocking 組合與 deadlock（112 題組 B）。
• 從 assembly 反推 C（112 題組 C），要用到 MIPS 的呼叫慣例。
• cache 位址拆解與序列追蹤（112 題組 D）。
• 記憶體 stall 的 CPI 計算（112 第 18 題）。
• Amdahl's law（112 第 17 題）。