113 中興資工所考古題詳解｜硬體考點分析

題型與配分

全卷 8 頁，簡章規定不可使用計算機。在合併的 113 年試題冊裡是第 3–10 頁，第 1–2 頁是離散數學與線性代數。

第 1–11 題（一、二大題共 50 分）是作業系統，第 12–17 題與兩題問答（三、四大題共 50 分）是計算機組織。

第一大題：複選題（第 1–5 題，每題 4 分）

• 第 1 題｜五個敘述：同一 process 內 thread 共用的資源、atomic transaction 的 two-phase locking、process 與 program 的主動與被動、multithreading process 的 program counter、ready 狀態的 process 能否做 I/O
• 第 2 題｜user thread 相對於 kernel thread 的優點：context switch 效率、thread 建立效率、message passing 效率、回應性、善用多處理器
• 第 3 題｜4 個同時到達的 CPU burst（P1 = 4、P2 = 10、P3 = 8、P4 = 2，到達順序為 P1、P2、P3、P4），判斷哪些 scheduling 演算法的總 turnaround time 不大於 65：FCFS、SJF、time quantum 8 的 Round-Robin、time quantum 4 的 Round-Robin、time quantum 無限大的 Round-Robin
• 第 4 題｜value 初值為 10，child process 執行 value += 15，parent process wait 之後執行 value += 3，求 LINE A 與 LINE B 的輸出
• 第 5 題｜FIFO、LRU、OPT 三種 page replacement 演算法，哪些情況是可能的：FIFO 優於 LRU、LRU 優於 FIFO、三者 page fault 數相同、LRU 的 frame 變多反而 page fault 變多、在真實作業系統實作 OPT

第二大題：單選題（第 6–11 題，每題 5 分，答錯 −3）

• 第 6 題｜Banker's Algorithm：五個 process P0–P4、四種資源 A–D，給 T₀ 的 Allocation、Max、Available，判斷兩條 safe sequence 與兩個資源請求的敘述哪個不正確
• 第 7 題｜頁面參考串 1 2 3 4 2 3 4 1 2 1 1 3 1 4、三個 frame，LRU 的 page fault 次數
• 第 8 題｜兩個 process 用兩個 semaphore 控制（S 初值 1、M 初值 0），哪個輸出序列不可能發生
• 第 9 題｜關於 synchronization，哪個敘述不正確：wait 與 signal 的 atomicity、deadlock 四條件、spinlock 在單處理器上、ostrich algorithm、semaphore 與 conditional critical region 是否等價
• 第 10 題｜關於 deadlock，哪個敘述不正確：四個必要條件、單一實例 resource allocation graph 有 cycle、多實例 resource allocation graph 有 cycle、safe state 與 deadlock、判定為 unsafe 之後仍批准資源請求
• 第 11 題｜inode 結構的 combined scheme：磁碟 block 8 KB、pointer 4 bytes，primary index block 有 12 個 pointer（9 個 direct pointer，單層、雙層、三層 indirect pointer 各一），其他間接 index block 完全用來存 pointer，存取檔案第 1 到第 5120 個邏輯 block，共要從磁碟讀幾個實體 block，題目提示要算進 primary index block

第三大題：單選題（第 12–17 題，每題 5 分，答錯 −3）

• 第 12 題｜用 6 個處理器要達到 4 倍加速，原始計算中最多有百分之幾是循序執行
• 第 13 題｜pipeline 各級延遲 IF 190 ps、ID 120 ps、EX 150 ps、MEM 180 ps、WB 100 ps、pipeline register 10 ps，把所有 load／store 改成 register 定址（無 offset）並讓記憶體存取與 ALU 平行，求把 single-cycle datapath 做 pipelining 的 speedup
• 第 14 題｜關於 GPU，哪個敘述是錯的
• 第 15 題｜關於 hardware multithreading，哪個敘述是錯的：fine-grained、coarse-grained
• 第 16 題｜clock 5 GHz、所有參考在 primary cache hit 時 base CPI 為 1.0，main memory 存取時間 60 ns（含所有 miss 處理），primary cache 每指令 miss rate 2%，求總 CPI
• 第 17 題｜RAID 4 的 small write 更新：給 D0、D1、D2、D3 與 P 的值與新的 D0，求新的 parity P′

第四大題：問答題（每題 10 分，寫在答案卷）

• 問答 1｜給一個 4 位元 adder，從 NOT、OR、AND、XOR 四種邏輯閘中選擇，修改成 sub = 0 時做 A + B、sub = 1 時做 A − B，sub 同時作為最低位元的 carry-in
• 問答 2｜指令序列 lw $2, 20($1)、add $3, $5, $6、sub $4, $2, $3 有 data hazard，用五級 pipeline 圖說明如何以 forwarding 消除，forwarding path 要標上 register 編號

作答時要注意的地方

1. 第一大題複選題要全對才給分，答錯不倒扣。
2. 第二、三大題答錯倒扣 3 分，最多扣到該大題 0 分為止；第二大題是五個選項，第三大題是四個選項。
3. 第 3 題問的是總 turnaround time，不是平均 turnaround time。
4. 第 7 題的參考串有連續兩個相同的頁號。
5. 第 11 題題目附有提示，要把 primary index block 算進去。
6. 問答 1 的邏輯閘只能從 NOT、OR、AND、XOR 中選擇。
7. 問答 2 明訂 forwarding path 要標上 register 編號。

準備方向

• page replacement：113 第 5、7 題，112 第 1、2 題、114 第 12、14 題與問答第 2 題、115 第 9 題也有。
• Belady 異常與 stack algorithm：113 第 5 題，110 第 2-C 題、114 第 12 題也有。
• Banker's Algorithm：113 第 6 題，115 第 8 題也有。
• user thread 與 kernel thread：113 第 2 題，111 第 7-I 題、114 第 11 題也有。
• fork 的 process 追蹤：113 第 4 題，110 第 2-A 題、112 第 13、21–23 題、115 第 13 題也有。
• deadlock：113 第 9、10 題，110 第 2-B 題、114 第 7、8 題也有。
• synchronization 與 semaphore：113 第 8、9 題，111 第 5-III 題、112 第 10 題、114 第 13 題也有。
• file system 與 inode：113 第 11 題，114 第 3、10 題也有檔案管理。
• Amdahl's law：113 第 12 題。
• pipeline speedup 與 forwarding：113 第 13 題與問答 2，110 第 5-A 題、111 第 7-II 題、115 第 1 題也有。
• 含 cache miss 的總 CPI：113 第 16 題，108 第 (5) 題、114 第 18 題也有。
• GPU、hardware multithreading 與 RAID：113 第 14、15、17 題。
• adder-subtractor：113 問答 1，109 第 4(b) 題也有 full adder。