刑事警察人員 109 年計算機系統考古題

假設有P1, P2, P3, P4, P5 五個行程，每個行程所需的CPU 時間如圖所 示。假設P1, P2, P3, P4, P5 依序於時間點0 時開始等CPU 執行。 Process Burst Time Priority P1

2 P2 1 1 P3 8 4 P4 4 2 P5 5

請根據以下的四種演算法：First Come First Serve（FCFS）、Shortest Job First（SJF）、Non-Preemptive Priority（a smaller priority number implies a higher priority）、Round Robin（quantum = 4），畫出時間甘特圖來描 述CPU 處理五個行程的使用情形。（15 分） 請計算出四種演算法的平均等待時間為何？（請列出計算過程）（10 分） 二、某多項式P(x)= a + bx5 + cx10 + dx15，a, b, c, d 均為非零整數。給定一x 值，在求P(x)值時，請問最少需要做多少次乘法運算？最少需要做多少 次加法運算？（15 分） 三、在一個分頁系統中，使用了轉譯旁觀緩衝區（translate look-aside buffer, TLB）的硬體裝置能有效提高其系統中分頁表（page table）的效能，假 設TLB 的命中率（hit ratio）為90%，TLB 的存取時間為10 奈秒（nano second, ns），記憶體存取時間為100 奈秒（ns）。請問使用單層分頁表 （single-level page table）的有效記憶體存取時間（effective memory-access time, EAT）為何？使用雙層分頁表（two-level page table）的有效記憶體 存取時間（EAT）為何？（10 分）

給定一個混合有不同指令集的benchmark 測試程式，每種指令集有不同 的平均週期數（clock per instruction, CPI），如下表，我們利用此benchmark 來測試一個2-GHz 的處理器。 指令集 Frequency CPI Integer ALU 30% 1 Floating-point options 20% 12 Load and stores 35% 4 Branches 15% 2 假設benchmark 中所有指令數目為5109，請問有效平均週期數 （effective CPI）是多少？此benchmark 的執行時間（execution time） 為何？（10 分） 假設我們設計了一個最佳化編譯器能將branch 指令集減少2/3，能將 Integer ALU 指令集減少1/3，請問有效平均週期數變為多少？請問此 最佳化編譯器的效能加速提升（speedup）為何？（依據Amdahl 法則 中的定義，效能加速提升為提升後的執行時間除以提升前的執行時 間）（10 分） 依據原來的benchmark 指令集表格，假設我們設計了一個效能改善的 方法，能將float-point 指令集的CPI 減少到4，請問有效平均週期數 變為多少？效能加速提升為何？（10 分）

給定一個以byte 為最小單位（byte-oriented）的記憶體分頁管理系統，邏輯 位置（logical address）空間共有128 個分頁（page），每頁大小1,024 bytes， 實體記憶體（physical memory）共有512 個欄（frame）。請問在此記憶體 分頁管理系統中，邏輯位置最少需要多少個bit 才能描述？實體位置最 少需要多少個bit 才能描述？（20 分）