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

題型與配分

全卷 7 頁、20 題、100 分，禁用計算器，作答於答案卷（卡）。

卷面沒有寫倒扣下限。單選第 16–19 題的答案都是數值取 mod 5，第 20 題直接選數值。

作業系統考點（1–10）

• 第 1 題（5%）｜fork system call：新 process 是否含原 process address space 的複本、copy-on-write 的作用、fork() 對原 process 的回傳值、execl 做什麼
• 第 2 題（5%）｜atomic transaction：不可 interrupt 的單位是否稱為 atomic、整數遞增是否「總是」能 atomically 執行、TestAndSet 是否 atomically 執行、critical section 的 mutual exclusion 是否確保 critical section atomically 執行
• 第 3 題（5%）｜網路：IPv4 的 32 位元 address space 是否使連網電腦數不可能超過 2³²、socket 能否用在同一台機器的兩個 process、ICMP 是否用來查本地裝置的硬體位址、跨網路送封包時要對應成 physical address 的是目的 IP 還是其他位址
• 第 4 題（5%）｜paging 的控制位元：dirty／modify bit 的用途與它對處理 page fault 時間的影響、valid-invalid bit 由誰設定、valid 時該頁是否在系統的 physical address space
• 第 5 題（5%）｜paging 與 spinlock：頁面被換出時 process 能否執行、dynamic loading 是否需要 OS 特別支援、鎖只持有很短時間時 spinlock 是否浪費、spinlock 是否避免 context switch 的開銷
• 第 6 題（5%）｜程式執行時要求動態配置記憶體（如 heap），在 contiguous allocation、純 segmentation、純 paging、paged segmentation 下各需要什麼支援
• 第 7 題（5%）｜demand paging 系統的使用率：CPU 20%、paging 磁碟 97.7%、其他 I/O 裝置 5%，問哪些做法可能提升 CPU 使用率：換更快的 CPU、換更大的 paging 磁碟、增加 degree of multiprogramming、減少 degree of multiprogramming、增加 main memory
• 第 8 題（5%）｜哪些程式技術與結構適合 demand paging 環境：stack、hashed symbol table、sequential search、binary search、pure code
• 第 9 題（5%）｜分離 mechanism 與 policy 的目的：易於程式設計、系統易於修改、彈性、提高使用率、快速回應
• 第 10 題（5%）｜硬體沒有 privileged mode 時，如何確保 OS 隨時掌控：協同處理器、網路伺服器、全部以高階語言撰寫並由編譯器檢查、叢集運算、軟體詮釋所有使用者程式

計算機組織考點（11–20）

• 第 11 題（5%）｜布林運算式 E1、E2 是否等價，共五組，其中兩組分別以 Σ（minterm 和）與 Π（maxterm 積）表示，如 E1(A,B,C,D) = AC+BC+A'B'C+B'C'D' 與 E2 = C+B'D'
• 第 12 題（5%）｜datapath 五級延遲 IF 300、ID 150、EX 250、MEM 350、WB 200 ps：非 pipelining 與 pipelining 的 clock cycle，以及單一 LW 指令的總延遲
• 第 13 題（5%）｜無 forwarding 的 pipeline，OR R1,R2,R3、AND R2,R1,R4、XOR R1,R1,R2 三道指令，週期 300 ps：各 RAW hazard、需要插入幾個 NOP、總執行時間
• 第 14 題（5%）｜pipeline 為什麼能提升 throughput：降低 clock rate、所有級同時使用、減少指令數、縮短單一指令的 response time
• 第 15 題（5%）｜branch prediction：是否防止 data hazard、static prediction 是否用執行期資訊、dynamic prediction 由誰決定、static 與 dynamic prediction 誰表現較佳
• 第 16 題（5%）｜2-way set associative、128 KB cache、32 位元 virtual address、block 64 bytes，tag 欄位為 A 位元。系統重置後依序存取 0x1D34B2BE、0x1D34B2CF、0x1D34B286、0x1D34B2E8、0x1D38B2D9、0x1D38C2DA、0x1D3DB2E7、0x1D34B2E6，採 LRU，miss 次數為 B，求 mod(A + B, 5)
• 第 17 題（5%）｜兩台機器共用同一個 ISA，P 機 2.4 GHz、W 機 2 GHz，編譯器 LP 與 LW 分別產生 17.6 百萬與 1.2 百萬道指令，三類指令 IA、IB、IC 在兩機上的 CPI 與指令比例都不同。求 T_P 與 T_W，再算 mod(round(T_W / T_P × 110), 5)
• 第 18 題（5%）｜1000 次記憶體存取，L1 miss 100 次、L2 miss 20 次、L3 miss 5 次，L3 的 miss penalty 100 cycles，hit time 為 L1 1、L2 5、L3 10 cycles，平均存取時間為 T，求 mod(round(T × 13), 5)
• 第 19 題（5%）｜32 位元 IEEE 754 single precision，最大 normalized number K 與最大 denormalized number J 中 0 位元的個數分別為 ZK 與 ZJ，求 mod(ZK + ZJ, 5)
• 第 20 題（5%）｜40 億道指令，4 級 pipeline，2 GHz，平均每道指令造成 1.2 個 stall 週期，問執行時間，選項有 2、2.4、4.4、4.8、5.2 秒

作答時要注意的地方

1. 75 分在逐選項倒扣的多選題上，卷面沒有寫倒扣下限。
2. 第 15 題有「None of above」選項。
3. 第 16、17、18、19 題禁用計算器，答案取 mod 5。
4. 第 12 題的四個敘述同時涉及 clock cycle 與單一 LW 指令的延遲。

準備方向

• 無 privileged mode 如何做出安全的 OS（107 第 10 題），106 第 7 題、108 第 12 題、112 第 20 題、113 第 11 題也有。
• policy 與 mechanism 的目的（107 第 9 題），106 第 12 題、113 第 15 題、114 第 17 題也有。
• thrashing（107 第 7 題），111 第 19 題、113 第 7 題也有。
• pipeline 改善的是 throughput 還是 latency（107 第 14 題），112 第 4 題、113 第 6 題也有。
• pipeline hazard 與 forwarding（107 第 13 題），106、108、109、110、111、114、115 也有。
• branch prediction（107 第 15 題），106、108、110、115 也有。
• cache 位址拆解（107 第 16 題），108 第 4 題、109 第 2 題、110 第 1 題、111 第 2 題也有。
• IEEE 754 floating point（107 第 19 題），108、111、114 也有。
• Boolean algebra 與 Karnaugh map（107 第 11 題），106 第 1、15、16 題也有。
• fork system call（107 第 1 題），106 第 19 題、111 第 4 題也有 fork。
• spinlock（107 第 5 題），115 第 19 題也有。