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

題型與配分

全卷 5 頁、8 題、100 分。卷面沒有倒扣規定。

第 1 題：十個單選（20%）

• 第 1(1) 題｜interrupt 處理程式處理完 interrupt 之後會發生什麼事
• 第 1(2) 題｜現代機器上 process 產生合法範圍以外的位址，立即的結果是什麼
• 第 1(3) 題｜FCFS CPU scheduling 最大的問題
• 第 1(4) 題｜Shortest Run Time First scheduling 的問題
• 第 1(5) 題｜fork system call 要求作業系統做什麼
• 第 1(6) 題｜Linux 工作通常用哪個 system call 啟動自己的另一份副本（fork/exec、shell、clone、dispatch）
• 第 1(7) 題｜下列哪些技術可以預防某些 deadlock
• 第 1(8) 題｜shared memory 的主要缺點
• 第 1(9) 題｜page table 項目中的 valid 位元在實作 virtual memory 之後改變了什麼意義
• 第 1(10) 題｜哪一項不是 I/O 採用 block 傳輸的理由

第 2 題至第 8 題

• 第 2 題（5%）｜inode file system，磁碟 block 8 KB，指向 block 的 pointer 4 bytes，12 個 direct block 加上單層、雙層與三層 indirect block，問最大檔案大小
• 第 3 題（10%）｜四個即時 process P1（處理時間 10、週期 50）、P2（20、100）、P3（50、150）、P4（80、300），deadline 等於週期，時間 0 全部就緒。(a) 5 分：用 RMS 能否讓所有 process 都不誤期。(b) 5 分：用 EDF 能否讓所有 process 都不誤期
• 第 4 題（15%）｜64 位元 virtual address、48 位元 physical address，以字組定址（1 word = 2 bytes），page table 項目 8 bytes，頁面 8 KB，每小題 5 分。(a) 一個 process 最多擁有幾個頁面。(b) 使用多層 paging 時有幾層。(c) 改用 inverted page table、每個項目 8 bytes 時，整個 inverted page table 要多少 DRAM
• 第 5 題（10%）｜K 個輸入 a₁–a_K、K 個權重 w₁–w_K 與 bias b，z = Σ a_iw_i + b，σ(z) 以二次多項式 D + Ez + Fz² 近似，權重在計算前已載入，D_ADD = 0.1 × D_MUL，乘法與加法可以平行，K = 16 時求最小延遲（以 D_MUL 表示）
• 第 6 題（10%）｜同一個網路改用 CPU 計算，每個 clock cycle 只能同時做一次乘法與一次加法，求輸入改變後算出輸出最少要幾個 clock cycle。卷面寫「problem 1」，從題意看是指第 5 題的網路
• 第 7 題（5%）｜hit time、miss rate、miss penalty 是 cache 最佳化的三個指標，各舉一種最佳化方法
• 第 8 題（25%）｜記憶體以位元組定址，CPU 依序存取 8, 20, 182, 88, 39, 40, 98, 182, 57, 32, 66, 88（十進位），每小題 5 分。(a) 以這些位址讀 12 個 32 位元變數，第一個沒有對齊的存取是哪一個。(b) 讀 12 個 8 位元變數，direct-mapped cache 有 10 個 block、每個 block 1 byte，第一次 hit 是哪一次存取。(c) (b) 的 12 次存取共幾次 hit。(d) 每個 block 改成 10 bytes，第一次 hit 是哪一次存取。(e) (d) 的 12 次存取共幾次 hit

作答時要注意的地方

1. 全卷沒有倒扣規定，第 1 題每題 2 分。
2. 第 3 題 (a)、(b) 都要回答能不能，題目指定 deadline 等於週期。
3. 第 4 題是以字組定址，1 word = 2 bytes。
4. 第 5 題指定 K = 16，權重在計算前已載入。
5. 第 6 題卷面寫「problem 1」，指的是第 5 題的網路。
6. 第 8 題的 cache 有 10 個 block，(b)(c) 與 (d)(e) 的 block size 不同。

準備方向

• 單選題在之後的年度重複出現：非法位址（107 第 1(2) 題）在 109 第 1(7) 題、113 第 1(1) 題，FCFS 的問題（107 第 1(3) 題）在 113 第 1(5) 題，SRTF 的問題（107 第 1(4) 題）在 108 第 1(7) 題、113 第 1(6) 題，Linux 啟動自己的副本（107 第 1(6) 題）在 109 第 1(8) 題，shared memory 的缺點（107 第 1(8) 題）在 111 第 1(2) 題，valid 位元（107 第 1(9) 題）在 109 第 1(10) 題、111 第 1(7) 題。
• inode 的最大檔案大小（107 第 2 題），109 第 2 題的數據完全相同，110 第 5 題改成 4 KB block 與 8 bytes pointer。
• RMS 與 EDF（107 第 3 題），110 第 2 題也有，改成三個 process。
• 多層 paging 的層數（107 第 4(b) 題），110 第 3(a) 題也有；114 填空第 5 題考三層 page table 的位址計算。
• cache 追蹤：同一組位址跑兩種 block size（107 第 8 題），111 第 6 題、113 第 4 題也用 10 個 block、兩種 block size，115 第 1 題同一組位址跑三種組態。
• cache 最佳化的三個指標（107 第 7 題），110 第 11 題用同一段開頭，改問提高 cache bandwidth 的方法。
• neural network 的延遲與週期數（107 第 5、6 題），106 第 5、6 題、108 第 6、7 題也有。
• deadlock prevention（107 第 1(7) 題），106 第 1(6)(7) 題、108 第 1(6) 題也考 deadlock。