114 台大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 100 分、11 頁、18 題，用 2B 鉛筆作答於答案卡。試題隨卷繳回。

卷首寫明「本考試科目包含兩個子科目：作業系統與計算機結構，配分各為五十分」，兩個子科目各自標示單選與複選。

單選題沒有寫不倒扣，複選題明訂「錯誤選項為零分、不倒扣」。

配分不平均：第 3 題 3 分，第 5 題 10 分，第 17 題 8 分。

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

單選題（1–5，30 分）

• 第 1 題（5%）｜critical section 問題：記憶體屏障保證的是順序還是 mutual exclusion、atomic instruction 如何防止並行更新、semaphore 能不能允許多於一個 process 同時進入、mutex 的取得與釋放前提
• 第 2 題（5%）｜RAID：多磁碟的平行性提高的是效能還是可靠度、RAID 5 的同位檢查如何分布、用 MTBF 與 MTTR 算鏡像系統的平均資料遺失時間（MTTDL）、RAID 10 與 RAID 01 的疊法順序
• 第 3 題（3%）｜fork 之後的變數值：全域變數在 child process 被修改、parent process wait() 後印出，選項是四個算式
• 第 4 題（7%）｜把七個變數算出來再代進係數等式：頁面 2 KB、physical memory 64 KB；傳統單層 page table 有 1024 個 entry；記憶體存取 180 ns、page table hit rate 60%、page fault 服務時間 30,000 µs；inverted page table；TLB 搜尋 20 ns、hit rate 90%。依序算 logical address 位元數 L、physical address 位元數 P、effective access time X、inverted page table entry 數 N、加 TLB 後的 effective access time Y，以及 speedup 落在哪兩個整數 A、B 之間，最後代進四個等式驗證
• 第 5 題（10%）｜自訂的「參考可能性」replacement algorithm：32-bit 處理器、頁面 8 KB，給十個十六進位位址、三個空 frame、working set 視窗 W = 6。依題目自訂的規則（參考可能性最小者被換掉、平手用 LRU）模擬

複選題（6–9，20 分）

• 第 6 題（5%）｜看「開檔案」的資料結構圖判斷五個操作：使用者空間、kernel 記憶體、次要儲存三層，圖上標了 ①–⑤ 五個操作。哪一步是查目錄結構、哪一步回傳檔案描述子、檔案已被開啟時哪一步不會被呼叫。與 111 年第 3 題是同一張圖的不同問法
• 第 7 題（5%）｜Round Robin 的平均 waiting time 寫成 a×10²+b×10¹+c×10⁰+d×10⁻¹：五個 process 給到達時間與 burst time，算出平均 waiting time，再把它的百位、十位、個位、十分位拆成 a、b、c、d，驗證五個係數等式
• 第 8 題（5%）｜Deadline-Monotonic scheduling：五個週期性 process，全部在時間 0 到達，給相對期限、週期、burst time。選項問 DM 與 RMS 對這組工作的 schedulability 是否相同、某個 process 的最壞反應時間、某個 process 是否 schedulable、增加 burst 對最壞反應時間的影響、改變 burst 後是否仍全部 schedulable。111 年第 10 題考的是 RMS
• 第 9 題（5%）｜綜合觀念：雙核心是不是總是兩倍加速、concurrency 與 parallelism 能不能分離、pthread_join() 屬於 synchronous 還是 asynchronous thread、process state diagram 上有沒有「waiting 直接到 running」這條線、在編譯期就完成的 address binding 產生的是哪一種碼。concurrency 與 parallelism 之分與 111 年第 9 題是同一個考點

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

• 第 10 題（8%）｜從 x86-64 反組譯還原 C 結構的定義：給 C 程式與 assembly，要回答 CN（array 大小）與 nt_struct 的完整宣告。assembly 裡有兩道 lea 指令
• 第 11 題（5%）｜兩個編譯器的 CPI 與 speedup（clock 1 ns，各給指令數與執行時間），接著問兩者執行時間相同時的 clock 比，以及第三個編譯器對前兩者的 speedup。與 111 年第 4 題是同一個模板
• 第 12 題（6%）｜pipeline 延遲：給五級各自的延遲與指令組合比例。問 pipelining 的 clock cycle、非 pipelining 的單指令延遲、pipelining 的單指令延遲，以及某個單元有多少比例的週期在用。與 113 年第 2 題是同一個模板
• 第 13 題（5%，單選）｜load delay slot：三道指令依序算出位址、載入、再相加。題目說「忽略 load delay slot」，lw 的位址是 register 內容加上 offset
• 第 14 題（Question Group A，第 14、15 題共 8%）｜VIPT cache：2-way、write-back、完美 LRU，tag store（含 valid、dirty、LRU）需要 13 × 2⁸ bits；virtual address space 1 MB、頁面 1 KB、cache block 8 bytes。由 tag store 的大小反推 cache 的資料區容量
• 第 15 題（Question Group A）｜同上題組：虛擬索引有幾個 bit 來自 virtual page number。與 107 第 9 題、111 第 14 題同樣考 VIPT，這次問的是溢出幾個 bit
• 第 16 題（Question Group B，共 12%，本題 4%）｜floating point 延遲下的迴圈週期數：C 迴圈 for(i=2;i<=1100;i++) A[i]=A[i-2]+A[i-2]; 對應的 RISC-V assembly，floating point 延遲為 fld = 6、fadd.d = 4、fsd = 1。迴圈本體有兩個 fld、一個 fadd.d、一個 fsd、一個 addi、一個 ble，問原始程式要幾個週期
• 第 17 題（Question Group B，本題 8%）｜同上題組：加入 single-cycle 的 fmv.d（register 搬移）後要幾個週期。題目只給提示「想想套用 fmv.d 之後組語會變成什麼樣」
• 第 18 題（6%，單選）｜雙核心 superscalar 的 issue slot 浪費：每核兩個功能單元、可 out-of-order execution、單 thread 模式（每核只能跑一條 thread）。thread X 有 A1（兩週期）、A2（相依 A1）、A3（與 A1 搶功能單元）、A4（相依 A2）；thread Y 有 B1、B2（與 B1 搶功能單元）、B3、B4（相依 B2）。問總週期數與因 hazard 浪費的 issue slot 數

作答時要注意的地方

1. 第 4、5 題合計 17 分，第 4 題要代進係數等式，沒有相近選項可以反推。
2. 第 10 題是台大硬體 106–115 唯一一次考 x86-64 反組譯，8 分。
3. 單選題沒有寫不倒扣，複選題明訂錯誤選項零分、不倒扣。

準備方向

• 「把答案拆成係數等式」的包裝在 112 第 17 題、114 第 3、4、5、7 題都出現，沒有部分分數。
• pipeline 延遲表的模板 113 第 2 題、114 第 12 題連兩年出現。
• VIPT 在 107 第 9 題、111 第 14 題、114 第 14、15 題三種問法：判斷有無別名、哪些 associativity 可行、索引溢出幾個 bit。
• 即時 scheduling 要分清 RMS 與 DM 各自依什麼指派 priority。111 第 10 題考 RMS，114 第 8 題考 DM，112 第 16 題考帶 softness 的變形。
• floating point 延遲下的迴圈 scheduling（第 16、17 題），與 109 第 1(e) 題的 loop unrolling 有關。
• x86-64 的 lea 定址。
• 複選題每一選項都要作答。