109 一般警察特考二等 刑事警察人員數位鑑識組 計算機系統(包括計算機結構、作業系統) 考古題詳解

109 年・一般警察特考・二等・刑事警察人員數位鑑識組
試題代碼 計算機系統(包括計算機結構、作業系統)

第 一 題25 分

假設有 P1P1、P2P2、P3P3、P4P4、P5P5 五個行程，每個行程所需的 CPU 時間如下：

ProcessBurst TimePriority
P1P122
P2P211
P3P384
P4P442
P5P553

假設 P1P1、P2P2、P3P3、P4P4、P5P5 依序於時間點 0 開始等候 CPU 執行。

(一) 請根據以下四種演算法，畫出時間甘特圖，以描述 CPU 處理五個行程的使用情形：

  1. First Come First Serve（FCFS）
  2. Shortest Job First（SJF）
  3. Non-Preemptive Priority（較小的 priority number 表示較高的優先權）
  4. Round Robin（quantum = 4）

（15 分）

(二) 請計算上述四種演算法的平均等待時間為何？請列出計算過程。（10 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查四種 CPU 排程演算法，以及由執行順序計算等待時間。

行程均在時間點 00 到達，因此不必考慮到達時間差異，也不會發生行程到達後插隊的情形。各行程的等待時間可用下式計算：

等待時間=首次開始執行時間−到達時間\text{等待時間}=\text{首次開始執行時間}-\text{到達時間}

本題到達時間皆為 00，所以等待時間等於該行程首次開始執行的時間。平均等待時間為：

平均等待時間=各行程等待時間總和5\text{平均等待時間}=\frac{\text{各行程等待時間總和}}{5}
  • FCFS：依到達順序執行。
  • SJF：選擇 CPU 執行時間最短的行程；本題採非搶先方式。
  • Non-Preemptive Priority：選擇優先權數字最小的行程；同優先權時依到達順序執行。
  • Round Robin：每個行程最多連續執行一個時間片，未完成者排到就緒佇列尾端；時間片為 44。

解題方法與時間甘特圖

1. FCFS

依到達順序 P1、P2、P3、P4、P5P1、P2、P3、P4、P5 執行。各行程依序累加其 Burst Time。

0 2 3 11 15 20
| P1 | P2 | P3 | P4 | P5 |

2. SJF

所有行程同時等候，依 Burst Time 由短至長排列：

P2(1)→P1(2)→P4(4)→P5(5)→P3(8)P2(1)\rightarrow P1(2)\rightarrow P4(4)\rightarrow P5(5)\rightarrow P3(8) 
0 1 3 7 12 20
| P2 | P1 | P4 | P5 | P3 |

3. Non-Preemptive Priority

優先權數字越小，優先權越高。依序為：

P2(1)→P1(2)→P4(2)→P5(3)→P3(4)P2(1)\rightarrow P1(2)\rightarrow P4(2)\rightarrow P5(3)\rightarrow P3(4)

P1P1 與 P4P4 優先權相同，依到達順序先執行 P1P1。

0 1 3 7 12 20
| P2 | P1 | P4 | P5 | P3 |

4. Round Robin（quantum = 4）

依就緒佇列輪流執行，每次最多執行 44 個時間單位。P1P1、P2P2、P4P4 在各自輪次內完成；P3P3、P5P5 未完成者回到佇列尾端。

0 2 3 7 11 15 16 17 20
| P1 | P2 | P3 | P4 | P5 | P3 | P5 | P3 |

等待時間計算

1. FCFS

依甘特圖可得各行程開始執行時間：

行程開始時間等待時間
P1P100
P2P222
P3P333
P4P41111
P5P51515
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 二 題15 分

某多項式為 P(x)=a+bx5+cx10+dx15P(x)=a+bx^5+cx^{10}+dx^{15}，其中 aa、bb、cc、dd 均為非零整數。

給定一個 xx 值，在求 P(x)P(x) 值時，請問最少需要做多少次乘法運算？最少需要做多少次加法運算？

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

這題考多項式的**乘法鏈（addition chain）**與霍納法則。計算時可以重複使用已算出的冪次，因此不必把 x5x^5、x10x^{10}、x15x^{15} 分別從頭計算。

題目只問乘法與加法次數，以下將係數乘法也計入乘法次數；加法則是把多項式各項合併所需的加法。

解題方法

先令 y=x5y=x^5，則

P(x)=a+by+cy2+dy3.P(x)=a+by+cy^2+dy^3.

以霍納法則改寫：

P(x)=a+y(b+y(c+dy)).P(x)=a+y\bigl(b+y(c+dy)\bigr).

依序計算：

  1. t1=dyt_1=dy：一次乘法。
  2. t2=c+t1t_2=c+t_1：一次加法。
  3. t3=yt2t_3=yt_2：一次乘法。
  4. t4=b+t3t_4=b+t_3：一次加法。
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 三 題10 分

在一個分頁系統中，使用了轉譯旁觀緩衝區（translate look-aside buffer, TLB）的硬體裝置，能有效提高系統中分頁表（page table）的效能。

假設 TLB 的命中率（hit ratio）為 90%，TLB 的存取時間為 10 奈秒（nanosecond, ns），記憶體存取時間為 100 奈秒（ns）。請回答下列問題：

(一) 使用單層分頁表（single-level page table）的有效記憶體存取時間（effective memory-access time, EAT）為何？

(二) 使用雙層分頁表（two-level page table）的有效記憶體存取時間（EAT）為何？

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查轉譯旁觀緩衝區（TLB）命中與未命中時，虛擬位址轉換所需的記憶體存取次數，並據此計算有效記憶體存取時間（EAT）。

設 TLB 命中率為 hh、TLB 存取時間為 tt、記憶體存取時間為 mm。命中時，先查 TLB，再存取資料；未命中時，還須查詢分頁表，再存取資料。因此：

  • 命中所需時間：t+mt+m
  • 未命中所需時間：t+(k+1)mt+(k+1)m

其中 kk 是分頁表的層數：單層分頁表 k=1k=1，雙層分頁表 k=2k=2。故：

EAT=h(t+m)+(1−h)(t+(k+1)m)EAT=h(t+m)+(1-h)\bigl(t+(k+1)m\bigr)

解題方法

已知 h=0.9h=0.9、t=10 nst=10\text{ ns}、m=100 nsm=100\text{ ns}。命中與未命中都要先查詢 TLB，因此兩種情況均計入 10 ns10\text{ ns} 的 TLB 存取時間。

（一）單層分頁表

TLB 命中時，存取 TLB 後直接存取資料，需 10+100=110 ns10+100=110\text{ ns}。

TLB 未命中時，需存取一次分頁表，再存取資料，合計 10+100+100=210 ns10+100+100=210\text{ ns}。

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 四 題30 分

給定一個混合有不同指令集的 benchmark 測試程式，每種指令集有不同的平均每指令週期數（clock cycles per instruction, CPI），如下表。我們利用此 benchmark 來測試一個 2-GHz 的處理器。

指令集FrequencyCPI
Integer ALU30%1
Floating-point operations20%12
Load and stores35%4
Branches15%2

(一) 假設 benchmark 中所有指令數目為 5×1095\times 10^9，請問有效平均週期數（effective CPI）是多少？此 benchmark 的執行時間（execution time）為何？（10 分）

(二) 假設我們設計一個最佳化編譯器，能將 branch 指令集減少 23\frac{2}{3}，並能將 Integer ALU 指令集減少 13\frac{1}{3}，請問有效平均週期數變為多少？請問此最佳化編譯器的效能加速提升（speedup）為何？

依據 Amdahl 法則中的定義，效能加速提升為提升後的執行時間除以提升前的執行時間。（10 分）

(三) 依據原來的 benchmark 指令集表格，假設我們設計一個效能改善方法，能將 floating-point 指令集的 CPI 減少到 4，請問有效平均週期數變為多少？效能加速提升為何？（10 分）

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查有效平均週期數（effective CPI）與執行時間的計算，以及指令數或 CPI 改變時的效能比較。

各類指令的執行時間由「指令數 × 該類指令 CPI」決定。有效平均週期數是依各類指令所占比例加權的平均：

有效 CPI=∑i(指令比例i×CPIi)\text{有效 CPI}=\sum_i \left(\text{指令比例}_i\times \text{CPI}_i\right)

處理器執行時間為：

執行時間=指令總數×有效 CPI時脈頻率\text{執行時間} =\frac{\text{指令總數}\times\text{有效 CPI}}{\text{時脈頻率}}

效能加速比通常定義為改善前執行時間除以改善後執行時間。本題特別指定「提升後執行時間除以提升前執行時間」，因此依題意計算的數值是傳統加速比的倒數；數值越小代表改善越大。

（一）原始有效 CPI 與執行時間

依各指令類別的比例加權：

有效 CPI=0.30(1)+0.20(12)+0.35(4)+0.15(2)=0.30+2.40+1.40+0.30=4.40\begin{aligned} \text{有效 CPI} &=0.30(1)+0.20(12)+0.35(4)+0.15(2)\\ &=0.30+2.40+1.40+0.30\\ &=4.40 \end{aligned}

因此，有效平均週期數為 4.44.4 個週期／指令。

處理器時脈頻率為 2 GHz=2×1092\ \text{GHz}=2\times10^9 週期／秒，指令總數為 5×1095\times10^9，故：

執行時間=(5×109)(4.4)2×109=11 秒\begin{aligned} \text{執行時間} &=\frac{(5\times10^9)(4.4)}{2\times10^9}\\ &=11\ \text{秒} \end{aligned}

（二）編譯器減少 Branch 與 Integer ALU 指令

先將各類指令數換算為原始指令總數的比例。Integer ALU 指令減少 13\frac{1}{3}，Branch 指令減少 23\frac{2}{3}：

  • Integer ALU：30%×(1−13)=20%30\%\times\left(1-\frac13\right)=20\%
  • Floating-point：20%20\%
  • Load and stores：35%35\%
  • Branches：15%×(1−23)=5%15\%\times\left(1-\frac23\right)=5\%

最佳化後總指令數為原始指令數的：

20%+20%+35%+5%=80%20\%+20\%+35\%+5\%=80\%

因此，最佳化後指令總數為 0.8(5×109)=4×1090.8(5\times10^9)=4\times10^9。各類指令數都以原始指令總數為基準換算，最佳化後的總週期數為：

總週期數=(5×109)[0.20(1)+0.20(12)+0.35(4)+0.05(2)]=(5×109)(4.1)\begin{aligned} \text{總週期數} &=(5\times10^9)\left[0.20(1)+0.20(12)+0.35(4)+0.05(2)\right]\\ &=(5\times10^9)(4.1) \end{aligned}

最佳化後的有效 CPI 應以最佳化後指令總數為分母：

最佳化後有效 CPI=4.10.8=5.125\text{最佳化後有效 CPI} =\frac{4.1}{0.8} =5.125

所以有效 CPI 為 5.1255.125。雖然有效 CPI 高於原先的 4.44.4，總指令數減少後，總執行時間仍會縮短。

原始執行時間為 1111 秒；最佳化後執行時間為：

🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

第 五 題20 分

給定一個以 byte 為最小單位（byte-oriented）的記憶體分頁管理系統：

  • 邏輯位置（logical address）空間共有 128 個分頁（page）。
  • 每頁大小為 1,024 bytes。
  • 實體記憶體（physical memory）共有 512 個頁框（frame）。

請問在此記憶體分頁管理系統中：

(一) 邏輯位置最少需要多少個 bit 才能描述？

(二) 實體位置最少需要多少個 bit 才能描述？

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

分頁式記憶體位址由兩部分組成：頁號（page number）與頁內位移（offset）。邏輯位址以頁號識別分頁；實體位址以頁框號（frame number）識別頁框。頁內位移的位元數則由每頁的 byte 數決定。

解題方法

每頁大小為 1,024=2101{,}024 = 2^{10} bytes，因此頁內位移需要 1010 bit。

(一) 邏輯位置

邏輯空間有 128=27128 = 2^7 個分頁，頁號需要 77 bit。加上頁內位移：

7+10=17 bit7 + 10 = 17\text{ bit}
🔒

後續完整解題步驟與【答案】

免費註冊，享 3 天全站完整詳解閱覽。

免費註冊

其他考古題

刑事警察人員數位鑑識組《計算機系統(包括計算機結構、作業系統)》其他年度

110