計算機系統考古題｜歷屆國考試題彙整

有一個4 位元的算術邏輯運算（ALU）之硬體架構設計如圖，可以執 行如圖的無號數（Unsigned Number）4 位元乘法運算，請回答下列問 題： 請寫出Control Test 的演算法（或是流程圖）。（10 分） 給定兩個十進位數字被乘數（Multiplicand）5 和乘數（Multiplier）12， 請用上述所寫出之Control Test 的演算法（或流程圖）完成圖ALU 的運算，需寫出執行的過程。（10 分） 若要將圖擴展成32 位元的ALU，且可以執行無號數和有號數（Signed Number）的乘法運算，請說明可以如何擴展或是設計？（5 分） 圖 圖 1 0 0 0 1 0 0 1ﺪ 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 ×

有一個32 位元的CPU 執行有號數（Signed Number）的加法運算或是減 法運算，運算結果有可能發生滿溢（Overflow）的情況，請回答下列問題： 請說明加法運算與減法運算會發生滿溢的情形為何？（15 分） 請設計一個電路（或演算法）來檢查運算結果是否發生滿溢？（10 分）

假設有一個程式在某單一處理器（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 分）

虛擬記憶體（Virtual Memory）的功能可以使多個程式間有效及安全地分 享主記憶體，同時虛擬記憶體也必須和快取記憶體（Cache Memory）系 統階層式的共同工作，所以除非資料已經存在於主記憶體中，否則不能 存在於快取記憶體中。設計上虛擬記憶體會使用頁（Page）表和轉譯側 查緩衝器（Translation-Lookaside Buffer, TLB）對應到主記憶體，請回答 下列問題： 記憶體階層存取效能（Performance）兩個常用的衡量指標命中（Hit） 和錯失（Miss），請說明何謂命中？何謂錯失？以及如何影響記憶體效 能？（10 分） 在記憶體階層的整體運作上，主記憶體存取可能會遇到三種錯失：TLB 錯失、頁錯失和快取（Cache）錯失。設想這三種錯失，有一種或是多 種發生，可以組合成七種可能性。請對每一種可能性，說明是否真的 會發生且在什麼情況下會發生？（15 分）

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

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

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

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

假設有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 分）

1 … 8

0 … -

1 … 2

0 … -

1 … 0

1 … 4 一、假設電腦公司A 決定生産兩款具備16 位元浮點運算的電腦，其中電腦 機型A-1 的浮點格式為一個正負號位元，7 個位元超-63（excess-63）的 指數及8 位元的尾數（mantissa），電腦機型A-2 的浮點格式為一個正負 號位元，5 個位元超-15 的指數及10 位元的尾數，兩者皆採用2 為基數 （radix）。 請問兩款電腦的十進位精度（precision）各為多少？（10 分） 如果希望電腦能處理多種應用，你會選擇那一個機型的電腦？理由為 何？（5 分） 二、假設某一個正在執行的行程（process）之分頁表（page table）如下表所 示，所有數值均以十進制表示，而任何編號均自0 開始，且所有記憶位 址均以位元組來定位（byte address）。 請說明如何將CPU 產生的虛擬位址（virtual address）轉換成主記憶體 的實際位址（physical address）。（10 分） 請問以下各個虛擬位址所對應的實際位址是否存在？如果存在，實際 位址為何？（每小題5 分，共15 分） ⑴ 1068 ⑵ 5500 ⑶ 2233 三、一個電腦以快取記憶體（cache）、主記憶體及硬碟來建構虛擬記憶體。 假設CPU 要存取的一個字組（word）係存放在快取記憶體中，則需要 15 ns 完成存取。如果那個字組在主記憶體中，但是不在快取記憶體中， 則需要先花50 ns 將字組載入快取記憶體，才能開始對快取記憶體存取 該字組。又假如該字組不在主記憶體中，則需要花10 ms 先將字組從硬 碟載入主記憶體，然後再花50 ns 將該字組從主記憶體載入快取記憶體， 最後才開始對快取記憶體存取該字組。假設快取記憶體的命中率（hit ratio）為0.9，而主記憶體的命中率為0.6，請問此系統存取一個字組所 花的平均時間為何？請以ns 表示。（10 分） 四、假設α 為一個程式碼可以同時被一個電腦中n 個處理器執行的比例，而 其餘的程式碼只能在一個處理器中依序執行。如果每個處理器執行速率 為x MIPS。（每小題5 分，共10 分） 試推導出一個式子以n、α、x 來表示此程式在該系統執行的有效MIPS 數。假設該系統只執行此一個程式。 若n = 16，x = 8 MIPS，試問α 的值為多少時可以使程式的執行速率達 到80 MIPS。 五、某一個微程式控制的處理器的微指令格式包含9 組個別的控制域 （control field）C0 – C8，每一組控制域Ci 可以啓動n i 條不同控制線中的 任何一條，其中n i 指定如下：（每小題5 分，共15 分） 要能完整表示這9 個控制域的最小控制位元數為何？ 最多可以同時發出多少控制訊號？ 若採用純粹水平（purely horizontal）格式來表示全部的控制資訊，則 所需要的最大控制位元數為何？ 六、請問行程（process）和程式（program）有何不同？（10 分）

請問作業系統有幾種主要的排程？請分別闡述其用途為何。（15 分） i = 0 1 2 3 4 5 6 7

n i = 4 5 3 2 11 9 16 7 22

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

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

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

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

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

導管式計算機（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）。 圖一：五個元件的導管式計算機 當此計算機執行下面的程式時，說明它產生資料障礙的原因和解決方法。（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 // ALU IF/ID ID/ EX EX/ M M/ WB IM Reg Reg DM 106年公務人員特種考試警察人員、一般警察 人員考試及106年特種考試交通事業鐵路 人員、退除役軍人轉任公務人員考試試題 全一張 （背面） 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員數位鑑識組 科 目： 計算機系統（包括計算機結構、作業系統）

詳述多執行序程式（Multithreaded Programming）的好處。（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 分）

由於資源（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 Sequence）。當時間T1 時，程序P1 額外要求1 個A、2 個C，詳述在這個情況下系 統是否同意分配？（15 分） 表一：分配狀態表 Allocation Max Available A B C A B C A B C P0 1 1 0 8 5

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

一計算機、特別是其處理器也許會被稱為具有32 位元的架構，其中最為人熟知者如 Intel 的IA-32 架構。 32  位元架構所指的意義究竟為何？請具體說明之。（10 分） 若計算問題中需處理的各種數值其分布範圍（含大小及精確度）已超過32 個位元 所可表示者，則是否該等計算機已無法應用？若是，則該如何解決？若否，則該 如何處理？（10 分）

一般計算機中均具有以下四種階層式的記憶體：硬碟、快取記憶體、暫存器（檔）、 主記憶體。 試由距離中央處理器最近者開始，將以上四者依序寫出；同時每一項之後以括號 說明其一般是以何種科技技術（例：SRAM 的IC 製作技術）製作。（8 分） 試指出以現今習知的科技技術而言，四者中應屬必不可或缺者為何？並說明其為 何應該不可或缺。（12 分）

考慮二進位的數值表示法： 在定點表示法中，以2 的補數表示法為例，假想的小數點應位於何處？能表示的 數字其值域（以數學式表示之）為何？（10 分） 在浮點表示法中，以IEEE 754 單精確度標準為例（符號／指數／分數欄位分別占 用1/8/23 個位元），能表示的不同數值其個數是否多於232個？為何如此？（10 分）

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

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

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

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

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

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

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

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

討論計算機指令集架構（instruction set architecture, ISA）設計時，有所謂零個運算 元（zero-operand）、一個運算元、二個運算元、三個運算元、四個運算元的分類方 法。試問：（每小題5 分，共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）大小順序依序為何？

某計算機其記憶空間為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年公務人員特種考試一般警察人員考試及 102年特種考試交通事業鐵路人員考試試題 類 科： 刑事警察人員數位鑑識組 全一張 （背面）

某機器碼（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 倍，則此機器 應能於一個機器時脈週期內同時派發多少道指令方足以保證達成？並詳細說明之。

在快取記憶體（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 分)

計算機中之算術運算會有溢位（overflow）之現象發生，何謂溢位（overflow）？試 說明以2 的補數（2’s complement）表示之兩個二進制數目相加時，如何判斷其是否 溢位？（20 分）

在多重程式（Multiprogramming）作業系統中，常以狀態圖表示一行程（process） 在系統中之狀態。一般可將其分為行程產生（New）、準備執行（Ready）、執行 （Running）、等待（Waiting）、完成（Complete）等五個狀態。試繪出此狀態圖， 並說明各狀態之意義及各狀態間轉換之條件。（20 分）

一個具有6 級之管線式處理器（pipelined processor），欲執行1000 個指令。若X 代表程式中之指令為跳躍（Branch）指令之機率，而遇到跳躍指令時，將使執行時 間多出4 個時脈週期（clock cycle）。試問： 當X = 0.2 時，平均每一指令週期（instruction cycle）可執行之指令數為何？（10 分） 若欲使每一指令週期可執行之指令數至少為4，則容許最大之X 值應為何？（10 分）

在具有快取（cache）之計算機系統中，快取與主記憶體之間的映照方式一般使用直 接（direct ）映照、集合關聯式（set-associative ）映照、或全關聯式（fully associative）映照等三種方式。假設計算機中有64 MB 主記憶體及64 KB 之快取， 而每一對應區塊（block）之大小為16 B，試就此數據分別說明此三種映照方式。 （20 分）

在計算機系統中，處理器與輸出入裝置間之溝通，可採用輪詢（polling）、中斷驅 動（interrupt driven）以及直接記憶體存取（DMA）等方式。試分別說明此三種作 業方式，並指出各作業方式所適用之輸出入裝置。（20 分）

試將下列十進制數目轉換成32 位元之二進制數目，並以十六進制碼表示出。注意：整 數以2 的補數（2’s complement）表示，浮點數則以IEEE 754 標準表示。（20 分）  -126  0.5  -17.875  -∞

作業系統中以優先權為主（priority based）之排程，常會有優先權反轉（priority inversion）之現象發生，何謂優先權反轉？為何會有優先權反轉之現象發生？優先 權反轉會造成什麼問題？如何解決優先權反轉所造成的問題？（20 分）

一計算機具有快取（cache）、主記憶體以及硬碟等儲存裝置，其使用虛擬記憶 （virtual memory）技術，並有轉換搜尋緩衝器（TLB）及分頁表（page table）。試 說明當CPU 欲以一虛擬位址讀取資料時，其動作之流程。（20 分）

試說明專屬輸出入（dedicated I/O）與記憶體映照式輸出入（memory-mapped I/O） 之區別，並說明使用記憶體映照式輸出入之優缺點。（20 分）

在管線式處理器（pipelined processor）中會有三種類型的危障（hazard）產生，即 結構危障（structural hazard）、資料危障（data hazard）以及控制危障（control hazard），試分別說明此三種危障之成因及其解決方案。（20 分）

程序管理（Process Management）中程序排程（Process Scheduling）的功能為何？比 較三種程序排程的方法：先到先做法（First Come First Serve）、最少CPU 時間工 作優先（Shortest Job First）與循環帶（Round Robin）之優缺點。（20 分）

何謂工作集（Working Set）？它在記憶體管理（Memory Management）的功用為何？ （20 分）

何謂關鍵區段（Critical Section）？監視器（Monitor）是關鍵區段的一種解決方案， 監視器如何運作？請詳述。（20 分）

設備驅動器（Device Driver）通常在設計上包括兩個部分：同步（Synchronous）與 非同步（Asynchronous）。詳述此二部分各自之功能。（20 分）

等值位元（Parity bit）之功能為何？偶等值（Even Parity）與奇等值（Odd Parity） 有何不同？等值位元之缺點為何？（20 分）

請說明電腦系統使用磁碟陣列RAID（Redundant Array of Independent Disks）較硬 碟一般使用方式有何好處？對電腦系統而言RAID 被視為甚麼？（10 分）請繪圖 說明RAID 5 的主要架構與特性（提示：例如須使用多少顆硬碟？分別用RAID 0 與RAID 1 等來說明RAID 5 的特點）。（20 分）

在電腦系統安全管理原則（policy）常見的有帳戶原則、使用者權利原則、稽核原 則，請分別重點說明其用途或特性？（20 分）

請扼要說明電腦作業系統中對Resource 與Resource Abstraction 的定義。（10 分）

請說明為何驅動程式必須是電腦系統程式核心（Kernel）的一部分？（10 分） 在撰寫裝置的驅動程式應包含那些部分？（10 分）

磁碟分割是使用新硬碟的重要處理步驟之一，請說明磁碟分割的用途（10 分）， 以及繪圖說明磁碟分割與磁區、實際硬碟的關係（提示：利用FDisk, Format 命令 來輔助說明）？（10 分）

虛擬機器（virtual machine）的一個實例是VMware。試說明其主作業系統（host operating system）與客作業系統（guest operating system）之間的關係。（20 分）

為了達到記憶體的需用分頁（demand paging），需要什麼硬體？為什麼？（20 分）

說明直接記憶體存取（direct memory access）的運作情形。（20 分）

使用岔斷（interrupt）的目的為何？（20 分）

使用多處理機（multiprocessor）有什麼優缺點？試詳述之。（20 分）

作業系統中之程序（process），在其被產生至執行結束的過程中會經過五種可能的狀態： 產生（new）、執行（running）、等待（waiting）、就緒（ready）、終止（terminated）。 試畫出此五種狀態之關係圖，並標明狀態轉換時的可能原因。（20 分）

說明內容轉換（context switch） 發生的時機及其過程。（10 分）

記憶體配置時，常常會發生碎片（fragmentation） 問題。依據其產生的原因，碎片又 可分為內部碎片（internal fragmentation） 及外部碎片（external fragmentation） 兩種。 試說明內部碎片及外部碎片的相異處。（20 分）

為了增進處理器（CPU） 的執行效率，我們使用了生產線技術（pipelining）。 在應用此技術的同時，也產生了某些危險（hazard），如資料危險（data hazard）、 結構危險（structural hazard） 以及控制危險（control hazard）。試說明資料危 險產生的原因。（20 分）

以二補數表示法將（-40）10 轉成八位元的二進位數值。（10 分） 六、為了加快程式的執行速度，我們在記憶體層級（memory hierarchy）中加入了 快取（cache）的機制，試說明快取利用了程式的何種特性以達到加速的效果。 此特性又可細分為那兩種？並說明快取如何利用此二特性。（20 分）