生成式 AI 角度學資工所考題：從 0 開始的系統思維

TL;DR：這些看似「傳統」的 OS/架構/演算法考題，其實就是讓生成式 AI 真的跑得動的底層工法：記憶體如何分頁、CPU 怎麼排隊、檔案怎麼開、資源怎麼分配、序列如何比對、效能怎麼估。懂它們，才能把 AI 從 demo 帶到上線。

🎯 資工所在學什麼

• Paging/位址轉換：把「看得見的虛擬位址」翻成「硬體能用的實體位址」；TLB/反向頁表是在追求更快。
• 排程/等待時間：CPU 如何把時間切片給多個程序，Round-Robin 是公平取號叫號。
• 檔案開啟流程：open() 從使用者空間一路到核心、目錄、FCB 的索引關聯。
• 背包/動態規劃：有限容量下的最佳選擇組合（資源配置的母題）。
• 最大流/淘汰賽建模：把限制條件轉成「流量」上限，下結論靠 max-flow。
• 序列比對/DP：match/mismatch/gap 的表格遞迴，等價於「對齊」問題。
• 時間複雜度：比較成長率，預估跑不跑得動。

🤖 為什麼生成式 AI 需要懂這些

🧠 從 0 開始的學習路線（3 週速成）

Week 1：作業系統 × 記憶體

1. 位址空間觀念：邏輯位址 vs. 物理位址
2. Paging 三件事：頁大小、頁表階層、TLB 命中率
3. I/O 與檔案：open → dir entry → FCB → open file table
4. 小專案：寫一個「模擬 TLB 命中率」的 script，觀察 hit ratio 與 AMAT（平均存取時間）變化

Week 2：排程 × 併發

1. 排程指標：等待時間、周轉時間、時間片
2. 模擬 RR/FCFS/SJF：比較多用戶推論的延遲分佈
3. 小專案：用一個工作佇列模擬 1000 個推論請求，調不同時間片觀察 p95 latency

Week 3：演算法 × 最佳化

1. DP 兩面向：背包（資源配置）與序列比對（對齊）
2. 圖論做決策：把限制變容量、用 max-flow 下結論
3. 小專案：把一個多 Agent 任務分派問題轉成 max-flow，求可行最大吞吐

🧩 題目 → AI 心智模型（How to Think）

1) Paging 與效能（含 TLB）

• 思考框架：
  1. 定位「頁大小」→ 算 offset 位元數
  2. 定位「實體記憶體大小」→ 算 frame 數與實體位址位元數
  3. 估 EMAT：EMAT = hit_ratio*(TLB_time+mem_time) + (1-hit)*(TLB_time + mem_time + mem_time)
  4. 反向推：反向頁表/多層頁表何時更划算？
• AI 連結：大模型分片＋參數熱度（熱權重放快取、冷權重放慢層）

2) Round-Robin 平均等待時間

• 思考框架：
  1. 先畫甘特圖（時間線）
  2. 每輪扣時間片，記錄完成時間 → 等待 = 完成 – 抵達 – 執行
  3. 求平均
• AI 連結：多租戶推論的公平性與 p95/p99 延遲

3) open() 的資料結構

• 思考框架：
  1. 目錄中有沒有？（避免重複）
  2. 系統範圍 open file table 是否已有 entry？
  3. FCB/INODE 是否需新建？
• AI 連結：DataLoader「快取命中/檔案重複/索引」設計

4) 背包（Unbounded 版本）

• 思考框架：
  1. 明確：是否可重複拿？（本題：可重複）
  2. DP 轉移：dp[w] = max(dp[w], dp[w-size[i]] + value[i])
  3. 找出最大值與組合
• AI 連結：在固定 GPU RAM 與時間內，選擇 batch/seq/精度的最優組合

5) Max-Flow 淘汰賽

• 思考框架：
  1. 建圖：source→比賽節點→隊伍節點→sink
  2. 容量 = 規則上限（最多能再拿的勝場）
  3. 最大流 = 能否分配不超限
• AI 連結：多 Agent 併行任務的最大可行吞吐量

6) 序列比對 DP（Global Alignment）

• 思考框架：
  1. 定義 match/mismatch/gap 分數與初始化
  2. 狀態轉移：左、上、左上三擇一 + 分數
  3. Traceback：由右下回溯
• AI 連結：理解 Attention/Alignment、對齊評估與懲罰（gap 類比為缺詞或省略）

7) 演算法成長率（Big-O）

• 思考框架：
  1. 先比指數、再比多項式、最後比對數與常數
  2. 有 n^{log n}、2^{log^c n} 這類混合型時，先取 log 化簡
• AI 連結：推論路徑（如 beam size/解碼策略）與時間預算

🛠️ 現學現用：三個迷你實驗

1. TLB 命中對 EMAT 的影響

   • 改 hit ratio：0.6→0.9，觀察 EMAT 下降幅度
   • 問題：何時值得多放快取？（成本 vs. 效益）

2. RR 時間片對延遲尾端的影響

   • 固定 5 種 burst time，時間片從 2→20
   • 觀察 p95 latency 與吞吐量變化

3. Unbounded Knapsack for GPU 設定

   • 物品=（精度、batch、seq）三種「花費/價值」組合
   • 讓 dp 幫你在 24GB RAM 下找最大吞吐配置

✅ 檢核清單（考前一天）

• [ ] 我能算出：頁大小、offset 位元數、實體位址位元數
• [ ] 我知道：TLB hit/miss 下 EMAT 如何組合
• [ ] 我會畫：RR 甘特圖，能手算平均等待時間
• [ ] 我能描述：open() 牽涉的三種表（目錄、開檔表、FCB/inode）
• [ ] 我能寫出：Unbounded Knapsack 的 1D DP 轉移式
• [ ] 我會建：淘汰賽的 max-flow 圖，說出每條邊容量意義
• [ ] 我能推：序列比對 DP 的遞迴與 traceback 規則
• [ ] 我分得出：多項式 vs 指數 vs 對數成長，能口算大略關係

📌 一句話帶走

生成式 AI 不只要「會模型」，更要「懂系統」。這份考題就是把「AI 能不能上線」的關鍵螺絲一顆顆鎖緊的清單。

進一步延伸（關鍵詞）

• AMAT / locality / huge page / NUMA
• MLFQ / cgroup / token bucket / rate limiting
• Memory-mapped I/O / async dataloader / prefetch
• Min-cost max-flow / bipartite matching（分派）
• CTC/DTW vs. Needleman–Wunsch（對齊家族）
• 推論複雜度：KV cache、長序列的次二次化技巧