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

題型與配分

全卷 8 頁，簡章規定不可使用計算機，另有 1 頁考生注意事項。單選題畫在答案卡，計算問答題寫在答案卷，卷面註明未依規定作答不予計分。

第 1–16 題（一、二大題共 38 分）加問答第 1、2 題（12 分）是作業系統，共 50 分；第 17–22 題（30 分）加問答第 3、4 題（20 分）是計算機組織，共 50 分。

第一大題：作業系統觀念題（第 1–13 題，每題 2 分，答錯 −1）

• 第 1 題｜哪一項功能是把 main memory 當成資源，配置給多個活躍 process 共享：Partition management、Memory management、Disk management、Direct Memory Access
• 第 2 題｜兩句 True/False：multi-threading 適用於執行多個彼此獨立、不必序列化的工作的應用；資料庫伺服器同時處理大量用戶端請求是 multi-threading 的例子
• 第 3 題｜哪些是作業系統的檔案管理功能：檔案的建立與刪除、disk scheduling、目錄的建立、把檔案對映到輔助儲存體
• 第 4 題｜配對 Interrupt、Trap、Supervisor Call 與三種用途：呼叫作業系統功能、對 asynchronous 外部事件的反應、處理錯誤或 exception 狀況
• 第 5 題｜決定頁面何時被帶入 main memory 的是：fetch policy、placement policy、replacement policy、resident set management
• 第 6 題｜哪些是 micro-kernel 的功能：檔案管理、低階記憶體管理、process 間通訊、I/O interrupt 管理
• 第 7 題｜配對 Mutual exclusion、Hold and wait、No preemption 與三段描述
• 第 8 題｜deadlock prevention 的直接方法是防止哪個條件發生：Mutual exclusion、Circular waits、Hold and wait、No preemption
• 第 9 題｜兩句 True/False：paging 把 process 切成固定大小的頁、segmentation 使用大小不一的片段
• 第 10 題｜固定 block size 的 file system 中，block 愈大對磁碟 throughput 與磁碟空間利用率的影響
• 第 11 題｜user level thread 與 kernel level thread 的四個敘述，找出錯誤的：context switch 時間、硬體支援、在多處理器上 scheduling、blocking 一條 kernel level thread
• 第 12 題｜FIFO page replacement、固定 frame 數：增加 frame 數有時會提高 page fault rate、有些程式沒有 locality of reference，判斷兩句敘述及其因果關係
• 第 13 題｜以 test-and-set 實作 enter_CS 與 leave_CS，X 初值為 0，判斷四個敘述：是否 deadlock-free、是否 starvation-free、process 是否依 FIFO 順序進入 critical section、是否可能多個 process 同時進入

第二大題：頁面置換與排程（第 14–16 題，每題 4 分，答錯 −2）

• 第 14 題｜FIFO page replacement、4 個 frame、起初沒有載入任何頁面，先依序存取 100 個不同的頁面，再以相反的順序存取同樣的 100 頁，共發生幾次 page fault
• 第 15 題｜三個 process id 為 0、1、2，CPU burst 分別為 2、4、8，同時在時間 0 到達，採 longest remaining time first（LRTF），平手時 id 小的優先，求平均 turnaround time
• 第 16 題｜三個 CPU 密集的 process 分別需要 10、20、30 個時間單位，到達時間為 0、2、6，採 shortest remaining time first，需要幾次 context switch，不計時間 0 與最後一次

第三大題：計算機組織（第 17–22 題，每題 5 分，答錯 −3）

• 第 17 題｜superscalar 架構的主要好處
• 第 18 題｜程式 P 有 N 道指令，load 與 store 佔 35%，指令 cache miss rate 2%、資料 cache miss rate 5%，miss penalty 分別為 80 與 100 個週期，求記憶體 stall 週期總數
• 第 19 題｜DRAM 為什麼需要週期性 refresh：用 flip-flop 儲存資料、volatile 記憶體、non-volatile 記憶體、電容會漏電
• 第 20 題｜關於 out-of-order execution 用的 reorder buffer（ROB）哪個敘述是錯的
• 第 21 題｜100 道指令的程式，25% 的指令遇到 data hazard，每次 stall 2 個週期，有效 CPI 為 1.8，求不含 data hazard 的 base CPI
• 第 22 題｜8 KB、8-way set-associative cache，block size 8 bytes，位址 32 位元，tag 欄位需要幾個位元

第四大題：計算問答題（32%，寫在答案卷）

• 問答 1（6%）｜三個 process 同時在時間 0 到達，總執行時間為 10、20、30，各自前 20% 的時間做 I/O、接著 70% 做計算、最後 10% 再做 I/O，作業系統採 shortest remaining compute time first，在執行中的 process 因 I/O 而 block 或計算結束時才 scheduling，所有 I/O 可以盡量重疊，求 CPU 閒置的時間百分比
• 問答 2（6%）｜頁面參考串 1, 2, 3, 2, 4, 1, 3, 2, 4, 1、main memory 3 個 frame、起初為空，求 LRU、FIFO、OPTIMAL 三種 replacement policy 的 page fault 次數
• 問答 3（8%）｜(C1600000)₁₆ 是 IEEE 754 single precision floating point，求它的十進位值
• 問答 4（12%）｜MESI cache coherence 協定，依 cache line 是 clean 或 dirty、對單一 cache 可見或對多個 cache 可見，填完 M、E、S、I 四個狀態的表格（全名、clean/dirty、single/multiple 三欄）

作答時要注意的地方

1. 三個大題各有不同的倒扣規則，每個大題開頭都註明沒作答不給分。
2. 單選題畫在答案卡，計算問答題寫在答案卷。
3. 第 14 題的第二輪存取與第一輪相反的順序。
4. 第 15 題平手時由 id 小的 process 優先。
5. 第 16 題不計時間 0 與最後的 context switch。
6. 問答 1 假設所有 I/O 可以盡量重疊。

準備方向

• page replacement：114 第 12、14 題與問答第 2 題，112 第 1、2 題、113 第 5、7 題、115 第 9 題也有。
• Belady 異常：114 第 12 題，110 第 2-C 題、113 第 5 題也有。
• scheduling：114 第 15、16 題與問答第 1 題，110 第 1 題、111 第 6-III 題、113 第 3 題、115 第 14 題也有。
• deadlock：114 第 7、8 題，110 第 2-B 題、113 第 9、10 題也有。
• user level 與 kernel level thread：114 第 11 題，111 第 7-I 題、113 第 2 題也有。
• synchronization 與 test-and-set：114 第 13 題，111 第 5-III 題、112 第 10 題、113 第 8、9 題也有。
• trap 與 interrupt：114 第 4 題，112 第 9 題、115 第 7 題也有。
• 檔案管理與 block size：114 第 3、10 題，113 第 11 題也有。
• 含 cache miss 的 CPI 與 stall 週期：114 第 18、21 題，108 第 (5) 題、113 第 16 題也有。
• ROB：114 第 20 題，108 第 (6) 題、111 第 5-II 題、115 第 4 題也有。
• tag 位元數：114 第 22 題，108 第 (7) 題、110 第 3-B 題、111 第 8-III 題也有。
• IEEE 754：114 問答第 3 題，112 第 17 題有 two's complement。
• MESI：114 問答第 4 題，115 第 6 題也有。