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

題型與配分

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

這一年複選題計分有兩處和 106–109 年不同：

1. 答錯一個選項從倒扣 2 分變成倒扣 1 分。
2. 倒扣下限從該題 0 分改成本科目計算機系統 0 分，一題可以扣成負分，整科不會低於 0。

這個規則沿用到 114 年，115 年改回答錯 −2、扣至該題 0 分。

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

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜目錄結構：四個選項橫跨樹狀、acyclic graph、一般圖形三種目錄，分別問能不能用 symbolic link 共享、會不會出現 dangling pointer、reference count 可不可靠、什麼時候才需要 garbage collection
• 第 2 題（4%）｜四個 frame 的 page replacement：參考串 50, 40, 80, 20, 50, 10, 80, 40，要分別算 LRU 與 Optimal 的 page fault 數。另外兩個選項問 LRU 會不會出現 Belady's anomaly、要限制 thrashing 的擴散該用 global replacement 還是 local replacement
• 第 3 題（4%）｜indexed allocation 的最大檔案大小：index block 與資料 block 都是 1 KB、每個 index entry 4 bytes，單層與兩層各算一次。另外兩個選項問 linked 與 indexed allocation 有沒有 external fragmentation、需要直接存取的應用該用哪一種
• 第 4 題（4%）｜Buddy system 與 slab allocation：四個選項分別問「物件事先建好所以能快速滿足請求」是哪一種的特性、一個 slab 內能不能同時有已用與空閒物件、buddy system 會用多大的 block 來滿足一個非 2 的冪的請求、slab 是否完全沒有 fragmentation
• 第 5 題（4%）｜disk scheduling：請求序列 120, 25, 5, 11, 80, 185, 90, 85，磁頭初始在 88 且正往上移動。要判斷 SSTF 與 C-SCAN 的服務順序、SSTF 會不會造成 starvation、C-SCAN 相對 SCAN 改善的是什麼
• 第 6 題（4%）｜system call：四個選項涵蓋 system call 是不是也走 interrupt 機制、有沒有向量表項、參數太多時的傳遞方式、kernel 與使用者空間之間的複製能不能卸載給 DMA
• 第 7 題（4%）｜執行中的 process 遇到各種事件會轉到哪個狀態：與自己無關的裝置 interrupt、clock interrupt、I/O system call、非 I/O 的 system call
• 第 8 題（4%）｜send 與 receive 的 blocking 與 non-blocking 組合：四個選項排列出兩種組合與 receive 早於或晚於 send 兩種時序
• 第 9 題（4%）｜user thread 與 kernel thread 各自擁有哪些 stack 與控制結構
• 第 10 題（4%）｜現代 OS 調整 priority 的常見策略：四個選項分別是 I/O 頻繁的 process、從長時間睡眠醒來的 process、前景 process、用完 time quantum 的 process 各該往哪個方向調

計算機結構（11–20）

• 第 11 題（4%）｜CPU 效能：四個選項涵蓋多核加上 load balancing 能不能縮短 response time、跨 ISA 比較時 CPI 小的是不是一定比較快、CPU 時間由哪三個因子決定、由「比較快但 MIPS 較低」反推是 RISC 還是 CISC
• 第 12 題（4%）｜看 Fibonacci sequence 遞迴的 MIPS assembly：四個選項涵蓋為何只有 32 個 register、編譯器的 register 配置策略、MIPS 為何不提供 blt 與 bgt、prologue 存的那幾個 register 是不是每一個都必要
• 第 13 題（4%）｜MIPS 的 floating point 與常數載入：四個選項涵蓋 floating point 有沒有獨立的 register 組、lui + ori 組出來的 32 位元常數是多少、floating point 加法滿不滿足結合律、給定 PC 時 j 能到達的最高位址
• 第 14 題（4%）｜assembler 展開、IEEE754 與 LL/SC：四個選項涵蓋 assembler 為何要把 beq 改寫成 bne + j、最小正 single precision denormalized number、sticky bit 有幾位且記錄什麼、ll 與 sc 這對指令保護的是什麼
• 第 15 題（4%）｜乘除法硬體與 carry lookahead：四個選項涵蓋乘除法合併硬體中各 register 在乘法時扮演什麼角色、Booth 演算法的效能來源、用 NRDA 與 RDA 做一次除法各需幾次加減、多層 carry lookahead adder 帶來的好處
• 第 16 題（4%）｜single-cycle、multicycle、pipeline 各自的硬體需求：四個選項涵蓋 clock 訊號能不能拿來控制 combinational circuit、single-cycle 為何至少需要兩個獨立的記憶體單元、哪一種設計的硬體最便宜、pipelining 需不需要同樣的兩個記憶體單元
• 第 17 題（4%）｜看指令格式表與 datapath 做 machine code 編碼：四個選項分別要編碼一道 R-type 指令、編碼一道帶負 offset 的 sw、判斷 beq 的下一個 PC 怎麼算、列出 sub 的 control signal 值
• 第 18 題（4%）｜pipeline hazard：四個選項涵蓋 structural hazard 是不是必須靠複製硬體來解、單一 pipeline 循序取指能保證什麼、真 data dependence 靠 forwarding 能解決到什麼程度、in-order issue 與 antidependence 的關係以及 loop unrolling 為何要重新命名
• 第 19 題（4%）｜memory hierarchy：四個選項涵蓋階層式設計是不是對任何應用都比較快、L1 cache 該優先最佳化 hit time 還是 hit rate、位址拆出來的三個欄位裡哪些需要真的存在 cache line 中、AMAT 的式子對不對
• 第 20 題（4%）｜問哪些敘述不正確：四個選項涵蓋 cache 與 virtual memory 兩層階層各基於哪幾種 locality、cache 控制器與 virtual memory 管理器各由硬體還是軟體實作、cache miss 時 CPU 會不會切換去跑別的工作

題組（21–33，20 分）

• 題組 A（21–23，5%）｜兩層 paging 的索引拆解：32-bit logical address、4 KB 頁、physical memory 256 MB、每個 page table entry 4 bytes
• 第 21 題｜單層 page table 時 0xabcdef12 用來索引 page table 的值
• 第 22 題｜兩層且外層有 256 個 entry 時，外層與內層的索引各是多少
• 第 23 題｜每個 process 的 page table 最多需要多少記憶體
• 題組 B（24–26，5%）｜用 monitor 解餐哲問題：卷上給完整的 DiningPhilosophers monitor 程式
• 第 24 題｜指出哲學家用餐程式中寫錯的那一行
• 第 25 題｜test(i) 的目的
• 第 26 題｜test((i+4)%5) 的目的，題目說 index 是逆時針遞增
• 題組 C（27–29，5%）｜1-bit ALU 的 control signal：給最低位與最高位兩種 1-bit ALU 的電路圖
• 第 27 題｜slt 的實現概念，要說明最高位 ALU 的哪個輸出接回最低位的 Less 輸入
• 第 28 題｜slt 與 sub 的 control signal 組合
• 第 29 題｜bne、nor、lw、sw 各自的 ALU control signal 組合
• 題組 D（30–33，5%）｜用符號參數表示各種容量與位元數：記憶體空間 32-bit 位元組定址、main memory 2^mm bytes、frame 2^pf bytes、cache 2^cache bytes、cache block 2^cb bytes。要用這些符號寫出程式可用空間、frame 數、cache line 數與 tag 位元數，不給具體數字

作答時要注意的地方

1. 複選題答錯每個選項倒扣 1 分，下限是整科 0 分，一題可以扣成負分。
2. 題組 B 第 24 題要在一段 monitor 程式中指出寫錯的那一行。
3. 第 5 題的條件包含磁頭初始在 88 且正往上移動。
4. 題組 D 全部用符號推導。

準備方向

• 110–114 年複選題答錯 −1、扣至整科 0 分，115 年改回答錯 −2、扣至該題 0 分，進場前要先看當年度的計分說明。
• 1-bit ALU：109 題組 C 考 propagation delay，110 題組 C 考 control signal。
• 兩層 paging 的索引拆解（110 題組 A）。
• 餐哲問題的 monitor 解法（110 題組 B）。
• Buddy system 的配置規則（110 第 4 題）。
• j 指令的跳躍範圍（110 第 13 題）。