計算機系統　申論題歷屆試題與參考架構

有關處理器之架構，請回答下列問題：

（一）為什麼 pipeline（管線）可以提升處理器的效能？（5 分）

（二）有那些因素會使得 pipeline 無法達到理想上的效能？（10 分）

（三）有那些方法可以解決上述問題？（10 分）

（25 分）

下圖(a)是一個循序乘法器（sequential multiplier）（inputs 32 bits, output 64。下圖(b)是它改善後的設計。請比較它們的異同並以「是」或「否」bits）來回答下列問題：（每小題 5 分，共 25 分）(a)基本設計 (b)改善的設計

（一）圖(a)的硬體成本比較高？（是或否）

（二）圖(b)的運算時脈週期（clock cycle）數是圖(a)的兩倍？（是或否）

（三）兩者的乘法運算結果是相同的？（是或否）

（四）圖(b)最後產生的乘法結果（Product, 積）是 32 bits？（是或否）

（五）圖(b)的 Multiplicand 暫存器的內容不需要移位（shift）？（是或否）

（25 分）

有關電腦的記憶體系統，請回答下列問題：

（一）何謂空間局部化（spatial locality）？（5 分）

（二）何謂時間局部化（temporal locality）？（5 分）

（三）快取記憶體（cache）有兩種主要設計方式：直接對映快取（direct mapped cache）及集合相聯快取（set associative cache）。在相同總容量的條件下，一般說來何者的快取擊中率（cache hit ratio）會比較高？為什麼？（10 分）

（四）虛擬記憶體（virtual memory）系統的主要目的是保持資料的永久儲存性？（是或否） （5 分）

（25 分）

有關作業系統的排程（scheduling）議題，請回答下列問題：

（一）為什麼需要排程？（5 分）

（二）何謂先到先服務（First Come First Serve, FCFS）？它有什麼優缺點？（10 分）

（三）何謂最短時間需求優先（Shortest Job First, SJF）？它有什麼優缺點？（10 分）

（25 分）

有一個 4 位元的算術邏輯運算（ALU）之硬體架構設計如圖（一），可以執行如圖（二）的無號數（Unsigned Number）4 位元乘法運算，請回答下列問題：

（一）請寫出 Control Test 的演算法（或是流程圖）。（10 分）

（二）給定兩個十進位數字被乘數（Multiplicand）5 和乘數（Multiplier）12，請用上述（一）所寫出之 Control Test 的演算法（或流程圖）完成圖（一） ALU的運算，需寫出執行的過程。（10 分）

（三）若要將圖（一）擴展成 32 位元的 ALU，且可以執行無號數和有號數（Signed Number）的乘法運算，請說明可以如何擴展或是設計？（5 分）Multiplicand Register (4-bit) 4-bit ×‫ﺪ‬ 1001 ALU Shift Right 0000 Product Control Write Register (8-bit) Test圖（一） 圖（二）

（25 分）

有一個 32 位元的 CPU 執行有號數（Signed Number）的加法運算或是減法運算，運算結果有可能發生滿溢（Overflow）的情況，請回答下列問題：

（一）請說明加法運算與減法運算會發生滿溢的情形為何？（15 分）

（二）請設計一個電路（或演算法）來檢查運算結果是否發生滿溢？（10 分）

（25 分）

假設有一個程式在某單一處理器（CPU）上執行的指令中有 2.5 × 109 行（道）算術類指令，1.2 × 109 行（道）load/store 類指令，2.0 × 108 行（道）分支（Branch）類指令，此處理器對算術類指令的 CPI（Clock Cycles Per Instruction）為 1，load/store 類指令的 CPI 為 10，分支類指令的 CPI 為5，且處理器的時脈頻率是 2 GHz，請回答下列問題：

（一）請問此程式的執行時間和平均 CPI 是多少（若有小數計算到小數點二位）？（10 分）

（二）如果程式平行化後分別在 4 個和 8 個處理器核心上執行，每個處理器的時脈頻率依舊是 2 GHz，每個處理器上執行分支類指令數維持不變，但於 4 個核心上執行算術類指令數以及 load/store 類指令數為原該指令數除以 2.8，於 8 個核心上執行算術類指令數以及 load/store 類指令數為原該指令數除以 5.6，請問平行化後對於單處理器執行結果分別提升多少（若有小數計算到小數點二位）？（15 分）

（25 分）

虛擬記憶體（Virtual Memory）的功能可以使多個程式間有效及安全地分享主記憶體，同時虛擬記憶體也必須和快取記憶體（Cache Memory）系統階層式的共同工作，所以除非資料已經存在於主記憶體中，否則不能存在於快取記憶體中。設計上虛擬記憶體會使用頁（Page）表和轉譯側查緩衝器（Translation-Lookaside Buffer, TLB）對應到主記憶體，請回答下列問題：

（一）記憶體階層存取效能（Performance）兩個常用的衡量指標命中（Hit）和錯失（Miss），請說明何謂命中？何謂錯失？以及如何影響記憶體效能？（10 分）

（二）在記憶體階層的整體運作上，主記憶體存取可能會遇到三種錯失：TLB錯失、頁錯失和快取（Cache）錯失。設想這三種錯失，有一種或是多種發生，可以組合成七種可能性。請對每一種可能性，說明是否真的會發生且在什麼情況下會發生？（15 分）

（25 分）

有一 DMA（direct memory access）模組正在使用循環偷竊（cycle stealing），企圖從 9600 bps 傳輸速率的設備將字元（characters）傳輸到記憶體中。若 CPU 正在以每秒一百萬個指令（MIPS）的速率擷取（fetch）指令，則此 DMA 模組將使得處理器減慢多少速度？（假設 CPU 只擷取指令未處理資料的讀寫）（20 分）

（20 分）

有一計算機系統（computer system）包含 32K 16-bit 單字（word）的主記憶體（main memory） ，同時具有 4K-word 快取記憶體（cache memory） ，此快取記憶體分割以每組（set）有 4 個槽（slot）為單位，每個槽包含 64 個 單 字 。 假 設 快 取 記 憶 體 最 初 是 空 的 ， CPU 開 始 從 位 置（locations）30、31、32、…、4300 依序擷取（fetch）單字。若使用快取記憶體重複執行前述的依序擷取 5 次，則 估 計 可 改 善執 行時 間多 少 ？ 假 設 快 取 記 憶 體 的 速 度 比 主 記 憶 體 快 10 倍 ， 區 塊 替 換（block replacement）使用 LRU（least recently used）策略。（20 分）

（20 分）

如果單獨執行 I/O 綁定的程式（I/O-bound program），其花費在等待I/O 時 間 會 比 使 用 處 理 器 （ processor） 多 ， 而 處 理 器 綁 定 的 程 式（ processor-bound program ） 剛 好 相 反 。 假 設 短 期 排 程 演 算 法（short-term scheduling algorithm）適合最近使用較少處理器時間的程式。請說明為什麼此演算法偏好 I/O 綁定程式，卻沒有永久性地拒絕處理器時間（processor time）限制於處理器綁定程式。（20 分）

（20 分）

請說明快取系統（cache system）中直接映射（direct mapping）、關聯映射（associative mapping）和集關聯映射（set-associative mapping）之間有何不同？（20 分）

（20 分）

有一管線機（pipeline machine）分四個階段執行一個指令，第 1 階段需要 80 奈秒（nanosecond, ns），第 2 階段需要 50 奈秒，第 3 階段需要 90 奈秒，第 4 階段需要 40 奈秒，該管線如下所示： （假設沒有其他延遲）若以此管線來完成 10 個指令需要多少時間？（ 20 分 ）Stage 1 Stage 2 Stage 3 Stage 4 80 ns 50 ns 90 ns 40 ns

（20 分）

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

（一）請根據以下的四種演算法：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 分）

（25 分）

某多項式 P(x)= a + bx5 + cx10 + dx15，a, b, c, d 均為非零整數。給定一 x值，在求 P(x)值時，請問最少需要做多少次乘法運算？最少需要做多少次加法運算？（15 分）

（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 分）

（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 分）

（30 分）

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

（20 分）

假設電腦公司 A 決定生産兩款具備 16 位元浮點運算的電腦，其中電腦機型 A-1 的浮點格式為一個正負號位元，7 個位元超-63（excess-63）的指數及 8 位元的尾數（mantissa），電腦機型 A-2 的浮點格式為一個正負號位元，5 個位元超-15 的指數及 10 位元的尾數，兩者皆採用 2 為基數（radix）。

（一）請問兩款電腦的十進位精度（precision）各為多少？（10 分）

（二）如果希望電腦能處理多種應用，你會選擇那一個機型的電腦？理由為何？（5 分）

（15 分）

假設某一個正在執行的行程（process）之分頁表（page table）如下表所示，所有數值均以十進制表示，而任何編號均自 0 開始，且所有記憶位址均以位元組來定位（byte address）。Virtual page number Valid bit … Page frame number 0 0 … - 1 1 … 8 2 0 … - 3 1 … 2 4 0 … - 5 1 … 0 6 1 … 4

（一）請說明如何將 CPU 產生的虛擬位址（virtual address）轉換成主記憶體的實際位址（physical address）。（10 分）

（二）請問以下各個虛擬位址所對應的實際位址是否存在？如果存在，實際位址為何？（每小題 5 分，共 15 分）

⑴ 1068

⑵ 5500

⑶ 2233

（15 分）

一個電腦以快取記憶體（cache）、主記憶體及硬碟來建構虛擬記憶體。假設 CPU 要存取的一個字組（word）係存放在快取記憶體中，則需要15 ns 完成存取。如果那個字組在主記憶體中，但是不在快取記憶體中，則需要先花 50 ns 將字組載入快取記憶體，才能開始對快取記憶體存取該字組。又假如該字組不在主記憶體中，則需要花 10 ms 先將字組從硬碟載入主記憶體，然後再花 50 ns 將該字組從主記憶體載入快取記憶體，最後才開始對快取記憶體存取該字組。假設快取記憶體的命中率（hit ratio）為 0.9，而主記憶體的命中率為 0.6，請問此系統存取一個字組所花的平均時間為何？請以 ns 表示。（10 分）

（10 分）

假設 α 為一個程式碼可以同時被一個電腦中 n 個處理器執行的比例，而其餘的程式碼只能在一個處理器中依序執行。如果每個處理器執行速率為 x MIPS。（每小題 5 分，共 10 分）

（一）試推導出一個式子以 n、α、x 來表示此程式在該系統執行的有效 MIPS數。假設該系統只執行此一個程式。

（二）若 n = 16，x = 8 MIPS，試問 α 的值為多少時可以使程式的執行速率達到 80 MIPS。

（10 分）

某一個微程式控制的處理器的微指令格式包含 9 組個別的控制域（control field）C0 – C8，每一組控制域 Ci 可以啓動 n i 條不同控制線中的任何一條，其中 n i 指定如下：（每小題 5 分，共 15 分）i = 0 1 2 3 4 5 6 7 8 ni = 4 5 3 2 11 9 16 7 22

（一）要能完整表示這 9 個控制域的最小控制位元數為何？

（二）最多可以同時發出多少控制訊號？

（三）若採用純粹水平（purely horizontal）格式來表示全部的控制資訊，則所需要的最大控制位元數為何？

（15 分）

請問行程（process）和程式（program）有何不同？（10 分）

（10 分）

請問作業系統有幾種主要的排程？請分別闡述其用途為何。（15 分）

（15 分）

在計算機正常運作的情況之下，請分別就執行整數的加法與執行浮點數的加法說明是否一定滿足結合律（associativity）？若可能不滿足結合律，請用一個例子說明不滿足的情況。（20 分）

（20 分）

假設你可以提升浮點運算的速率變成 10 倍快，其他的部分都沒有改變就使你的程式執行時間變成原來的 1/4。在還沒有提升運算的速率之前，執行浮點運算的時間應該是占了多少百分比？（20 分）

（20 分）

管線化（pipelining）及多重派發（multiple issue）是提高指令層平行性（instruction-level parallelism）的兩個方法。請說明這兩個方法的意義，並討論這兩者的最高平行程度（degree of parallelism）。（20 分）

（20 分）

安裝虛擬機器管理程式（virtual machine manager）在個人電腦上面有什麼用處？請分別針對應用程式的使用者以及發展應用程式的程式設計師，說明其用處。 （20 分）

（20 分）

在一台只有一個處理器的計算機，耗費很長的時間同時執行 10 個應用程式，其中 2個程式不需輸入與輸出。另外 8 個程式都有相當多的輸入或輸出，而且處理器每執行 1 毫秒（ms）就要耗時 10 毫秒（ms）執行一次輸入或輸出。假設每一次程式切換的時間（context-switching overhead）是 0.1 毫秒，請計算使用輪流排程（round-robin scheduling）的方式在下面兩個情況之下的處理器利用率（CPU utilization）：（一）時間量（time quantum）為 2 毫秒（ms）；（10 分）（二）時間量為 10 毫秒（ms）。（10 分）

（20 分）

令 F(a, b, c, d)= a’ b’ c’ d’ + a’ b’ c d’ + a’ b c’ d + a’ b c d + a b c’ d + a b c d + a b’ c’ d’ + a b’ c d’為一具有四個輸入的布林函數。

（一）應用卡蹃圖（Karnaugh Map），化簡 F(a, b, c, d)。（5 分）

（二）利用反及閘（NAND）來製作此化簡後的邏輯電路。（10 分）

（15 分）

導管式計算機（Pipeline Computer）可以增加計算機執行指令的吞吐量（Instruction Throughput），但會形成三種障礙（Hazard），如結構障礙（Structure Hazard）、控制障礙（Control Hazard）和資料障礙（Data Hazard）。

（一）發生控制障礙時如何解決？（10 分）

（二）一個典型的導管式計算機如圖一，由五個元件（Component）組成，如指令記憶體（IM）、記錄器（Reg）讀取、運算單元（ALU）、資料記憶體（DM）、記錄器（Reg）寫入。每個元件在一個時序（Clock Cycle）完成，其中記錄器（Reg）讀取在時序的後半週完成而記錄器（Reg）寫入在時序的前半週完成。另一方面，元件之間有記錄器用來傳遞控制訊號和相關訊息，如指令讀取/指令解碼（IF/ID），指令解碼/指令執行（ID/EX），指令執行/資料存取（EX/M）和資料存取/記錄器寫入（M/WB）。ID/ EX/ M/ IM IF/ID Reg ALU DM Reg EX M WB圖一：五個元件的導管式計算機當此計算機執行下面的程式時，說明它產生資料障礙的原因和解決方法。 （15 分）sub $7, $1, $3 // Register 7= Register 1 – Register 3 // and $13, $7, $5 // Register 13= Register 7 and Register 5 // or $14, $6, $7 // Register 14= Register 6 or Register 7 // add $15, $7, $7 // Register 15= Register 7 + Register 7 // sw $16, 168($7)// Put the content of Register 16 back to memory based on Register 7 // 106年公務人員特種考試警察人員、一般警察人員考試及106年特種考試交通事業鐵路 代號：20140全一張考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員數位鑑識組

（25 分）

詳述多執行序程式（Multithreaded Programming）的好處。（10 分）

（10 分）

為減少下載用不到的分頁至主記憶體（Physical Memory）和降低交換時間（Swap Time），在虛擬記憶體管理（Virtual Memory Management）中，利用要求分頁（Demand Paging）技術來達成此目的。

（一）詳述虛擬記憶體管理（Virtual Memory Management）中，當要求分頁（Demand Paging）時發生了頁面錯誤（Page Fault），作業系統如何處理？（15 分）

（二）令 p（0≤ p ≤ 1）為發生頁面錯誤的機率，ma 為記憶體存取時間，pft 為頁面錯誤處理時間，pft= 40000ma，則要求分頁的性能其有效的記憶體存取時間（efa）為何？（5 分）

（三）當分頁的性能只能小於 10%時（efa=1.1ma），則 p 應小於多少？（5 分）

（25 分）

由於資源（Resources）有限，多個程序（Processes）在執行中會因競爭資源而造成死結（Deadlock）。

（一）詳述發生死結的四個必要條件。（10 分）

（二）銀行家的算法（Banker’s Algorithm）可以避免死結發生，令 Max[i][j]=k，表示程序 Pi 要求（Request）至多 k 個 Rj 類型的資源；Allocation[i][j]=k，表示程序 Pi 分配到 k 個 Rj 類型的資源；Available[j]=k，表示 Rj 類型的資源有 k 個；Need[i][j]=k，表示程序 Pi 需要 k 個 Rj 類型的資源才可以完成工作。假設目前有 5 個行程分別為P0、P1、P2、P3、P4，和 3 種不同類型的資源分別為 A、B、C，其中 A 類型的有12 個、B 類型的有 5 個、C 類型的有 7 個。假設時間 T0 時，系統資源分配如表一，詳述一程序序列（A Sequence of Processes）是當前分配狀態的安全序列（Safety。當時間 T1 時，程序 P1 額外要求 1 個 A、2 個 C，詳述在這個情況下系Sequence）統是否同意分配？（15 分）表一：分配狀態表Allocation Max Available A B C A B C A B C P0 1 1 0 8 5 6 4 3 2 P1 2 0 0 3 2 4 P2 3 0 2 10 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 5

（25 分）

一計算機、特別是其處理器也許會被稱為具有 32 位元的架構，其中最為人熟知者如Intel 的 IA-32 架構。

（一）32 位元架構所指的意義究竟為何？請具體說明之。（10 分）

（二）若計算問題中需處理的各種數值其分布範圍（含大小及精確度）已超過 32 個位元所可表示者，則是否該等計算機已無法應用？若是，則該如何解決？若否，則該如何處理？（10 分）

（20 分）

一般計算機中均具有以下四種階層式的記憶體：硬碟、快取記憶體、暫存器（檔）、主記憶體。

（一）試由距離中央處理器最近者開始，將以上四者依序寫出；同時每一項之後以括號說明其一般是以何種科技技術（例：SRAM 的 IC 製作技術）製作。（8 分）

（二）試指出以現今習知的科技技術而言，四者中應屬必不可或缺者為何？並說明其為何應該不可或缺。（12 分）

（20 分）

考慮二進位的數值表示法：

（一）在定點表示法中，以 2 的補數表示法為例，假想的小數點應位於何處？能表示的數字其值域（以數學式表示之）為何？（10 分）

（二）在浮點表示法中，以 IEEE 754 單精確度標準為例（符號／指數／分數欄位分別占用 1/8/23 個位元），能表示的不同數值其個數是否多於 232 個？為何如此？（10 分）

（20 分）

設有一系統內含同類型的資源（resources）16 件，並有 5 個程序（processes）共享該等資源，且每一程序會用到的資源其個數至多 4 個。則該系統是否可免於死結的發生（即是否為 deadlock-free）？試具體說明、推論之。（20 分）

（20 分）

假設三個程序的到達時間以及所需的執行時間如下所示：程序 到達時間 執行時間p1 0.0 5.0 p2 0.3 7.0 p3 0.7 1.0另假設排程的方式是不可搶先式（nonpreemptive）且程序的到達時間無法預知。又假設排程工作所需時間可以忽略。則在以下排程方法及條件下，三個程序的平均周轉時間（turnaround time，指從收到需求到完成工作之間的時間）各為若干？各小題均應詳列推導計算過程，並需算出正確答案，否則扣分或不予給分。

（一）先到先接受服務（First-Come-First-Served）。（6 分）

（二）最短的工作優先（Shortest-Job-First）。（7 分）

（三）排程器先等待到時間 1.0，再開始排程並令系統執行各程序。（7 分）

（20 分）

試以卡諾圖（Karnaugh map）化簡下列布林式。（10 分）

（10 分）

試解釋何謂重要區塊（critical section）？（5 分）並說明解決重要區塊問題（the critical section problem）時須滿足那些要求？（15 分）

（20 分）

CPU 排程為作業系統中重要的議題之一。今給定三程序 P1、P2 與 P3，其所需之CPU 時間分別為 24、4、3 單位時間；假設此三程序依照 P1 →P2 →P3 之順序分別於時間單位 0、1、2 時刻產生，並假設此時 CPU 已為可用狀態且僅需用於處理這三個程序。試以甘特圖（Gantt chart）表示先到先處理（first-come first-served）以及最短工作先處理（shortest-job-first）兩排程的結果，並分別計算兩排程下的平均等待時間（average waiting time）。（20 分）

（20 分）

在死結（deadlock）發生時，一定會有循環等待（circular wait）的情形，試提出一解決循環等待的方法，並證明該方法之正確性。（20 分）

（20 分）

虛擬記憶體（virtual memory）的技術允許我們執行一未完全載入於主記憶體中的程序；但此技術可能會造成猛移現象（thrashing）。試解釋猛移現象一詞，並作適當的說明。（10 分）

（10 分）

在多工作業系統中，本文交換（context switch）為 CPU 頻繁執行的動作之一。試解釋本文交換一詞，並作適當的說明。（10 分）

（10 分）

今欲存取磁碟上位於磁柱編號 98, 183, 37, 122, 14, 124, 65, 67 上的資料，試寫下SCAN 演算法（也稱為電梯演算法）對上述各磁柱的存取順序（假設磁碟讀寫頭目前位於編號 53 的磁柱，並往編號 0 的磁柱移動；且上述磁柱編號即代表目前已發生的存取請求，且不會再有其他請求發生）。（10 分）

（10 分）

討論計算機指令集架構（instruction set architecture, ISA）設計時，有所謂零個運算元（zero-operand）、一個運算元、二個運算元、三個運算元、四個運算元的分類方法。試問：（每小題 5 分，共 20 分）

（一）一般而言，零個運算元指令集架構的加法運算指令應分別自何處、取得幾個運算元？運算結果應儲存於何處？

（二）一般而言，一個運算元指令集架構的加法運算指令應分別自何處、取得幾個運算元？運算結果應儲存於何處？

（三）一般而言，二個運算元指令集架構的加法運算指令應分別自何處、取得幾個運算元？運算結果應儲存於何處？

（四）一般而言，四個運算元指令集架構的加法運算指令其第四個運算元的作用為何？

（20 分）

假設系統中有四個行程（processes）P1 至 P4，其所需 CPU 時間分別為{6, 2, 13, 5}，到達系統時間順序依序為 P1 至 P4，本文切換（context switch）所需時間為 1。試問：（每小題 5 分，共 20 分）

（一）採用先到先做法（first come first served）排程時，四個行程完成的順序為何？

（二）採用最少 CPU 時間工作優先法（shortest job first）排程時，四個行程完成的順序為何？

（三）採用循環式排班演算法（round robin）排程，並假設每次時間配額（time quantum）為 3 時，四個行程完成的順序為何？

（四）以上三個方法所得到的平均等待時間（average waiting time）大小順序依序為何？

（20 分）

某計算機其記憶空間為 232 個位址，每個位址可存放一位元組（byte）；其虛擬記憶體系統（virtual memory system）之頁（page）大小為 4KB（kilo bytes），主記憶體（main memory）的容量為 2GB（giga bytes）。試問此記憶體系統的：（每小題 5 分，共 20 分）

（一）主記憶體內的頁框（page frames）數為何？

（二）頁表（page table）內的項目（entries）數為何？（假設此頁表為單層的結構，並基於完整的頁表來回答本題。）

（三）此頁表應如何存取？亦即，應如何決定需要的項目何在？

（四）何謂頁錯誤（page fault）？發生時，一般將由系統中那一個機制來處理？102年公務人員特種考試警察人員考試、全一張102年公務人員特種考試一般警察人員考試及 代號：20140（背面）102年特種考試交通事業鐵路人員考試試題等 別： 二等一般警察人員考試類 科： 刑事警察人員數位鑑識組

（20 分）

某機器碼（machine code）在一個精簡指令集計算機（reduced instruction set computer, RISC）的管線式執行（pipelined execution）下，共使用了 x 個機器時脈週期（machine clock cycles）且 x 遠大於一般的管線深度。試問：（每小題 5 分，共 20 分）

（一）若機器時脈速率為 4GHz，則執行此機器碼耗時若干？

（二）經重新設計，機器時脈速率提升為 6GHz，然而此機器碼需使用 1.8x 個機器時脈週期。則此機器碼耗時又為若干？

（三）為了提升執行速度，我們先分析此機器碼，發現其可同時派發來執行（issue for execution）的指令數平均為 3。於是我們重新設計此機器使其能於一個機器時脈週期內同時派發二道指令。則此情形下，是否可預期新設計對此機器碼的執行速度可達 2 倍？並詳細說明之。

（四）為了充分發揮指令平行度以求機器對此機器碼的執行速度達到 3 倍，則此機器應能於一個機器時脈週期內同時派發多少道指令方足以保證達成？並詳細說明之。

（20 分）

在快取記憶體（cache memory）的設計中，其效能評估的數學式是AMAT(average memory access time)=HT(hit time)+MR(miss rate)×MP(miss penalty)下列六種優化技術中：選擇恰當快取區塊（cache block 或稱 line）大小；使用較大的快取；使用較高的關聯度（associativity)；使用多層的快取；給予讀取較寫入較高的優先度；避免在索引（indexing）時需要作位址轉換（address translation)試問：

（一）何者有助於降低 hit time？（6 分)

（二）何者有助於降低 miss rate？（8 分)

（三）何者有助於降低 miss penalty？（6 分)

（20 分）