113 成大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 4 頁、6 大題、100 分，不可使用計算機，於本試題紙上作答者不予計分。

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

• 第 1(1) 題｜關於 privileged instruction 哪個敘述是錯的
• 第 1(2) 題｜message passing 模型的特性
• 第 1(3) 題｜分層式 OS 設計的主要困難
• 第 1(4) 題｜boot block 的職責
• 第 1(5) 題｜什麼機制讓 OS 服務可以 dynamic loading，與中正 113 第 1(3) 題的 Linux 架構同一組觀念
• 第 1(6) 題｜resource allocation graph 中的 cycle 代表什麼
• 第 1(7) 題｜absolute code 在哪一種 address binding 下產生
• 第 1(8) 題｜dynamic linking 函式庫的實作機制
• 第 1(9) 題｜UNIX 的 vfork() 與 fork() 有何不同，與台大 108 第 7(b4) 題同一考點
• 第 1(10) 題｜Belady's anomaly 的定義

第 2 題：十個是非（10%）

十個敘述涵蓋的主題：

• 第 2(1) 題｜SSD 的 volatility
• 第 2(2) 題｜process 的 effective UID 在執行期間會不會改變
• 第 2(3) 題｜Mac OS X 的 kernel 架構
• 第 2(4) 題｜許多 OS 把 I/O 裝置與檔案合併成統一抽象
• 第 2(5) 題｜named pipe 的通訊需不需要父子關係
• 第 2(6) 題｜對 POSIX shared memory 的每次存取是否都需要 system call
• 第 2(7) 題｜典型 Linux 系統的第一個 process
• 第 2(8) 題｜one-to-one 與 many-to-one 模型的並行性比較
• 第 2(9) 題｜平行應用開發的趨勢（implicit threading）
• 第 2(10) 題｜Grand Central Dispatch 的 thread 模型

第 3 題：銀行家演算法（5%）

五個 process P0–P4、三種資源 A/B/C，給 Allocation、Max 與 Available (2,1,2)。題目提示先建出 Need 矩陣，再判斷是否存在 safe sequence。

第 4 題：需求分頁的指令重啟與最少 frame（15%）

• 第 4(1) 題（5%）｜執行 Add A, B, C（即 C = A + B）時，最多可能重啟幾次指令（假設含指令的那一頁已在記憶體中）
• 第 4(2) 題（5%）｜若考慮 indirect addressing ADD (A), (B), (C)，執行這道指令至少需要幾個 frame
• 第 4(3) 題（5%）｜現代系統傾向使用更大的頁面（因為 CPU 與記憶體容量成長遠快於磁碟速度），請提出採用 huge page 的三個優點與兩個缺點

第 5 題：十個是非（20%）

十個敘述涵蓋的主題：

• 第 5(1) 題｜cache 是用哪一種記憶體技術建造的
• 第 5(2) 題｜執行時間、CPU 時間、MIPS、clock cycle 數是否全都是良好的跨處理器比較指標
• 第 5(3) 題｜general-purpose register 架構的例子
• 第 5(4) 題｜對整數有效的平行執行策略是否對 floating point 也有效
• 第 5(5) 題｜delayed branch 對長 pipeline 處理器是否有用
• 第 5(6) 題｜高階語言的抽象能不能讓程式設計師完全不考慮記憶體行為
• 第 5(7) 題｜OS 是不是 schedule 磁碟存取的最佳位置，與 112 第 1(7) 題呼應
• 第 5(8) 題｜指令數與 CPI 是否互相獨立
• 第 5(9) 題｜處理器效能通常靠降低 clock rate 來改善
• 第 5(10) 題｜1 GHz 是否一定比 800 MHz 快

第 6 題：迴圈最佳化與平行加速（30%）

程式為 for(i=0;i<1000;i++) for(j=0;j<1000;j++) A[i][j] = B[i][j]*100+20;，array 元素是 32-bit 整數。

• 第 6(1) 題（10%）｜編譯器常用什麼最佳化技術減輕分支懲罰，請寫出最佳化後的程式碼
• 第 6(2) 題（10%）｜雙核處理器上平行執行相對於循序執行的理想 speedup，為什麼（無 control hazard、記憶體 miss 開銷可忽略）
• 第 6(3) 題（10%）｜單核加上 128-bit SIMD 引擎的效能比，為什麼

作答時要注意的地方

1. 於試題紙上作答不予計分。
2. 第 1、2、5 題的單選與是非題合計 50 分。
3. 第 4(1) 題假設含指令的那一頁已在記憶體中。
4. 第 6(2)(3) 題都要寫出理由。
5. 第 4(3) 題要求三個優點與兩個缺點。

準備方向

• demand paging 的 instruction restart 與最少 frame：113 第 4 題，含 indirect addressing。
• huge page 的優缺點：113 第 4(3) 題、108 第 4(4) 題；中央 115 第 6、13 題也考 huge page。
• 編譯器的迴圈最佳化、多核平行與 SIMD：108 第 2 題、110 第 1 題、113 第 6 題。
• Banker's algorithm：106 第 6 題、113 第 3 題。
• vfork 與 fork：113 第 1(9) 題，台大 108 也考。
• 計組基本觀念的是非題：cache 技術、MIPS 指標、floating point 結合律、delayed branch 與 pipeline 長度（113 第 5 題）。
• OS 與計組基本觀念的細節題（113 第 1、2、5 題）。