114 台大資工所硬體考點分析

題型與配分

科目：計算機結構與作業系統，題號 294、節次 2，全卷 100 分、11 頁、18 題。用 2B 鉛筆作答於答案卡。試題隨卷繳回。

這是台大硬體十年來第一次在卷首明文寫出「本考試科目包含兩個子科目：作業系統與計算機結構，配分各為五十分」，而且兩個子科目各自標示單選與複選。以往都要自己從題目內容推斷比重。

單選題沒有寫不倒扣，複選題明訂「錯誤選項為零分、不倒扣」。 整體仍是不倒扣的卷子，所有題目都應該作答。

配分極不平均：第 3 題只有 3 分，第 5 題有 10 分，第 17 題 8 分。OS 段的第 4、5 題合計 17 分，兩題都要做完整的數值推導。

作業系統（1–9，50 分）

單選題（1–5，30 分）

• 第 1 題（5%）｜臨界區問題——涵蓋 記憶體屏障保證的是「順序」還是「互斥」、原子指令如何防止並行更新、號誌能不能允許多於一個程序同時進入、mutex 的取得與釋放前提。第一項是全題核心：memory barrier 與 mutex 解決的是不同的問題
• 第 2 題（5%）｜RAID——涵蓋 多磁碟的平行性提高的是效能還是可靠度、RAID 5 的同位檢查如何分布、用 MTBF 與 MTTR 算鏡像系統的平均資料遺失時間（MTTDL）、RAID 10 與 RAID 01 的疊法順序。MTTDL 的公式要背，算完要換算單位才能跟選項比，數量級差一位就選錯
• 第 3 題（3%）｜fork 之後的變數值：全域變數在子程序被修改、父程序 wait() 後印出。唯一考點是 fork 之後父子的變數是什麼關係。算出兩個值之後還要逐一代進四個算式選項驗算
• 第 4 題（7%）｜把七個變數算出來再代進係數等式：頁面 2 KB、實體記憶體 64 KB；傳統單層頁表有 1024 個條目；記憶體存取 180 ns、頁表命中率 60%、頁錯誤服務時間 30,000 µs；反轉頁表；TLB 搜尋 20 ns、命中率 90%。要依序算出邏輯位址位元數 L、實體位址位元數 P、有效存取時間 X、反轉頁表條目數 N、加 TLB 後的有效存取時間 Y，以及加速比落在哪兩個整數 A、B 之間，最後代進四個等式驗證。反轉頁表的條目數由什麼決定是其中一個判斷點
• 第 5 題（10%）｜自訂的「參考可能性」置換演算法：32-bit 處理器、頁面 8 KB，給十個十六進位位址、三個空頁框、工作集視窗 W = 6。三個步驟：(1) 由頁面大小切出偏移與頁號的位元數，把十個位址轉成頁號；(2) 用滑動視窗算出工作集的最大大小；(3) 依題目自訂的規則（參考可能性最小者被換掉、平手用 LRU）逐步模擬。這是全卷最耗時的一題

複選題（6–9，20 分）

• 第 6 題（5%）｜看「開檔案」的資料結構圖判斷五個操作：使用者空間、核心記憶體、次要儲存三層，圖上標了 ①–⑤ 五個操作。要判斷哪一步是查目錄結構、哪一步回傳檔案描述子、檔案已被開啟時哪一步不會被呼叫。要知道系統層與程序層兩張開檔表各存什麼。與 111 年第 3 題是同一張圖的不同問法
• 第 7 題（5%）｜Round Robin 的平均等待時間寫成 a×10²+b×10¹+c×10⁰+d×10⁻¹：五個程序給到達時間與 burst time，畫甘特圖算出平均等待時間，再把它的百位、十位、個位、十分位拆成 a、b、c、d，驗證五個係數等式。台大近年很愛用這種「把答案拆成係數」的包裝
• 第 8 題（5%）｜Deadline-Monotonic 排程：五個週期性程序，全部在時間 0 到達，給相對期限、週期、burst time。先搞清楚 DM 依什麼指派優先權（與 RMS 不同）。選項問 DM 與 RMS 對這組工作的可排程性是否相同、某個程序的最壞反應時間、某個程序是否可排程、增加 burst 對最壞反應時間的影響、改變 burst 後是否仍全部可排程。與 111 年第 10 題（RMS）是同一條線
• 第 9 題（5%）｜綜合觀念——涵蓋 雙核心是不是「總是」兩倍加速、concurrency 與 parallelism 能不能分離、pthread_join() 屬於同步式還是非同步式執行緒、程序狀態圖上有沒有「waiting 直接到 running」這條線、在編譯期就完成的位址繫結產生的是哪一種碼。並行與平行之分和 111 年第 9 題同一個考點

計算機結構（10–18，50 分）

• 第 10 題（8%）｜從 x86-64 反組譯還原 C 結構的定義：給 C 程式與組語，要回答 CN（陣列大小）與 nt_struct 的完整宣告。關鍵線索是兩道 lea 指令：要看懂 lea (b, i, s), d 這種定址算式在做什麼乘法，由此推出每個結構元素的大小；再從某個固定偏移量的 mov 反推 CN。這是十年唯一一次考 x86-64 反組譯
• 第 11 題（5%）｜兩個編譯器的 CPI 與加速比（時脈 1 ns，各給指令數與執行時間）——先把執行時間換算成總週期數再除以指令數得 CPI，接著問 兩者執行時間相同時的時脈比、以及第三個編譯器對前兩者的加速比。與 111 年第 4 題是同一個模板
• 第 12 題（6%）｜管線延遲：給五級各自的延遲與指令組合比例。要分清管線化的時脈週期、非管線化的單指令延遲、管線化的單指令延遲，並由指令組合算出某個單元有多少比例的週期在用。與 113 年第 2 題、107 年第 12 題是同一個模板的第三次出現
• 第 13 題（5%，單選）｜load delay slot：三道指令依序算出位址、載入、再相加。要逐步追蹤暫存器內容，而且注意 lw 的位址是「暫存器內容加上位移」。題目說「忽略 load delay slot」，要想清楚這句話的意思
• 第 14–15 題（Question Group A，8%）｜VIPT 快取的容量與索引位元：2-way、write-back、完美 LRU，tag store（含 valid、dirty、LRU）需要 13 × 2⁸ bits；虛擬位址空間 1 MB、頁面 1 KB、快取區塊 8 bytes。
• 第 14 題｜由 tag store 的大小反推快取的資料區容量。要想清楚 13 bits 是「每一路」還是「每一組」的開銷，2⁸ 對應的是 set 數還是 line 數
• 第 15 題｜虛擬索引有幾個 bit 來自虛擬頁號。比較 index + offset 的位元數與頁內偏移的位元數，超出的部分就是 VIPT 別名的來源。與 107 第 9 題、111 第 14 題是同一條線的第三次出現，但這次問的是「溢出幾個 bit」
• 第 16–17 題（Question Group B，12%）｜浮點延遲下的迴圈週期數：C 迴圈 for(i=2;i<=1100;i++) A[i]=A[i-2]+A[i-2]; 對應的 RISC-V 組語，浮點延遲為 fld = 6、fadd.d = 4、fsd = 1。
• 第 16 題（4%）｜原始程式要幾個週期。迴圈本體有兩個 fld、一個 fadd.d、一個 fsd、一個 addi、一個 ble。要算出每次迭代因延遲產生的停頓再乘上迭代次數，迭代次數要算對
• 第 17 題（8%）｜加入單週期的 fmv.d（暫存器搬移）後要幾個週期。關鍵是看出這個迴圈的跨迭代資料重用關係：某一輪算出的值，在之後哪一輪會被再次讀到？能不能留在暫存器裡而不必重新載入？這是軟體管線化的思路，也是全卷設計最漂亮的一題
• 第 18 題（6%，單選）｜雙核心超純量的發射槽浪費：每核兩個功能單元、可亂序執行、單執行緒模式（每核只能跑一條執行緒）。執行緒 X 有 A1（兩週期）、A2（相依 A1）、A3（與 A1 搶功能單元）、A4（相依 A2）；執行緒 Y 有 B1、B2（與 B1 搶功能單元）、B3、B4（相依 B2）。要排出時序並數出總週期數與因危障浪費的發射槽數

這份考卷的難點

1. 第 4、5 題合計 17 分，兩題都要做完整推導才能代進係數等式。 第 5 題要把十個 32-bit 位址轉成頁號、維護滑動視窗、按自訂規則跑置換、平手再用 LRU——一步錯全錯，而且沒有相近選項可以反推。
2. 第 10 題的 x86-64 反組譯要看懂 lea 的定址算式並反推結構大小。十年唯一一次，而且是 8 分。
3. 第 17 題要自己想出最佳化後的組語長什麼樣。 題目只給提示「想想套用 fmv.d 之後組語會變成什麼樣」，要先看出跨迭代的重用關係。
4. 第 2 題的 RAID 與 MTTDL 計算是兩個獨立的陷阱：RAID 10 與 RAID 01 的疊法順序很容易記反，MTTDL 算出來的數量級也很容易差一位。

準備建議

• 「把答案拆成係數等式」是台大近年的固定包裝（112 第 17 題、114 第 4、5、7 題）。這種題型沒有部分分數也沒有相近選項，唯一的對策是算完後用第二種方法覆核
• 管線延遲表的模板連考三年（107 第 12 題、113 第 2 題、114 第 12 題），問法完全一樣，是最穩的送分題
• VIPT 連考三次（107 第 9、111 第 14、114 第 14–15 題），但每次問法不同：判斷有無別名 → 哪些關聯度可行 → 索引有幾個 bit 溢出到虛擬頁號。三種問法都要會
• 即時排程要分清 RMS 與 DM 各自依什麼指派優先權。111 第 10 題考 RMS、114 第 8 題考 DM、112 第 16 題考帶 softness 的變形
• 浮點延遲下的迴圈排程（第 16–17 題）要練「逐拍畫出停頓、再想辦法用暫存器重用消除載入」。這與 109 年第 1(e) 題的迴圈展開是同一套思路
• x86-64 的 lea 定址建議至少認得 lea (b, i, s), d 這個形式在算什麼，以及用它做乘法的慣用手法
• 全卷不倒扣，每一題每一選項都要作答