109 年國立中央大學資訊工程學系碩士班《作業系統與計算機組織》考古題與詳解

Question 1

Assume that an un-pipelined machine has $9\,\mathrm{ns}$ clock cycles. The machine uses 4 cycles for ALU operations, 5 cycles for branches, and 5 cycles for memory operations. The relative frequencies of these operations are 30%, 30%, and 40%, respectively.

Suppose that pipelining the machine adds $1\,\mathrm{ns}$ of overhead to the clock cycle time. Assume that the ideal CPI is one. Ignore any other impact.

(A) 4.5
(B) 4.6
(C) 4.7
(D) 4.8
(E) 4.9

Accepted Answer

題目說明 原卷這一題只給了條件與選項，沒有寫出問句。從選項範圍（4.5～4.9）與條件判斷，本題要問的是管線化後指令執行速率的加速比（教科書的經典題型），以下照這個題意作答，並說明各數字的來源。 核心觀念 - 未管線化機器：每道指令的平均執行時間＝平均 CPI × 時脈週期。 - 理想管線：CPI＝1，但每個時脈要多付管線暫存器的額外負擔（overhead）。 - 加速比＝未管線化平均指令時間 ÷ 管線化平均指令時間。 解題方法 1. 未管線化的平均 CPI： $$ 	ext{CPI}{	ext{unpipe}} = 0.3	imes4 + 0.3	imes5 + 0.4	imes5 = 1.2+1.5+2.0 = 4.7 $$ 2. 未管線化的平均指令時間：$4.7 	imes 9\,	ext{ns} = 42.3\,	ext{ns}$。

Question 2

For a 4K-byte direct-mapped cache whose block size is 4 bytes, if the length of the address is 32 bits, how many bits are used for tag? (A) 18 (B) 19 (C) 20 (D) 21 (E) 22

Accepted Answer

核心觀念 快取位址可分成三部分：標籤（tag）、索引（index）與區塊位移（block offset）。 - 區塊位移位元數：$\log2(	ext{區塊大小})$ - 直接對映快取的索引位元數：$\log2(	ext{快取區塊數})$ - 標籤位元數：位址總位元數減去索引與區塊位移位元數 解題方法 快取容量為 $4	ext{ KiB}=4096$ bytes，每個區塊為 $4$ bytes，因此快取共有： $$ \frac{4096}{4}=1024=2^{10}	ext{ 個區塊} $$ 直接對映快取中，每個區塊對應一個索引，所以索引需要 $10$ bits。每個區塊有 $4=2^2$ bytes，區塊位移需要 $2$ bits。

Question 3

Which of the following instructions should be sensitive in a VM executing native instructions?

(A) Set value of timer.
(B) Read the clock.
(C) Clear memory.
(D) Issue a trap instruction.
(E) Disable interrupts.

Accepted Answer

核心觀念 在虛擬機器上直接執行原生指令（trap-and-emulate）時，敏感指令（sensitive instruction）是指會讀取或改變「整台機器的資源與狀態」的指令。這些指令若讓客體作業系統直接在硬體上執行，就會影響到其他虛擬機器或 VMM 本身，因此必須設計成特權指令，在使用者模式下執行時陷入（trap）給 VMM 模擬。本題就是教科書「哪些指令應設為特權指令」的經典題。 解題方法 逐一判斷：執行這個指令會不會動到「整台機器共用」的硬體狀態，讓別的程式（或 VMM）失去控制權或資料被破壞。 選項分析 - (A) Set value of timer：應為敏感。 計時器是作業系統（VMM）收回 CPU 控制權的機制；客體若能任意改它，就能讓 VMM 永遠拿不回 CPU。 - (B) Read the clock：不必設為敏感。

Question 4

Which of the following scheduling algorithms would result in starvation? (A) First-come, first-served (B) Shortest job first (C) Round robin (D) Priority (E) Weighted fair queueing

Accepted Answer

核心觀念 飢餓（starvation）是指行程持續處於就緒狀態，卻因排程規則長期被其他行程排擠，無法取得處理器。 判斷排程是否會造成飢餓，要看它是否能讓某類工作一再被優先選中，以致另一類工作無限期等待。短工作優先與優先權排程都可能出現這種情況。 解題方法 逐一檢查各演算法的選擇規則：若新到達的工作能持續勝過已等待的工作，且規則沒有保證等待中的工作終將獲得處理器，就可能發生飢餓。 選項分析 - (A) First-come, first-served：錯。 依到達順序排程。只要每項工作都能在有限時間內完成，排在前面的工作會依序取得處理器，後到的工作不會插隊，因此不會因排程規則遭到無限期排擠。 - (B) Shortest job first：對。 每次選擇預估執行時間最短的工作。

Question 5

A counting semaphore . (A) is essentially an integer variable (B) is accessed through only one standard operation (C) can be modified simultaneously by multiple threads (D) cannot be used to control access to a thread's critical sections (E) executes as a single, uninterruptible unit

Accepted Answer

核心觀念 計數型信號量（counting semaphore）是一個整數型同步工具，用來追蹤可用資源的數量，或協調執行緒間的先後順序。它由兩個標準操作存取： - wait（也常記為 $P$）：嘗試取得資源；若資源數量不足，呼叫的執行緒會等待。 - signal（也常記為 $V$）：歸還資源，或通知其他執行緒可以繼續執行。 這兩個操作都必須具備原子性：每次操作視為不可分割的單位，避免多個執行緒同時更新信號量時造成競爭條件。 解題方法 逐一比對選項與信號量的定義：它在資料型態上是整數變數，但只能透過 wait、signal 這兩種標準操作存取；真正具不可中斷特性的，是這些操作，不是信號量本身。 選項分析 - (A) is essentially an integer variable：正確。計數型信號量本質上是整數值，代表資源計數或等待狀態；其更新須透過受同步保護的操作進行。 - (B) is accessed through only one standard operation：錯誤。

Question 6

Consider a multiprocessor system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be more than the number of processors in the system. What are the lower performance implications of the following scenarios?

(A) The number of kernel threads allocated to the program is less than the number of processors.
(B) The number of kernel threads allocated to the program is equal to the number of processors.
(C) The number of kernel threads allocated to the program is greater than the number of processors but less than the number of user-level threads.
(D) The number of kernel threads allocated to the program is equal to two.
(E) The number of kernel threads allocated to the program is greater than the number of processors and also greater than the number of user-level threads.

Accepted Answer

核心觀念

多對多（many-to-many）模型允許多個使用者層級執行緒（user-level threads, $U$ ）映射到多個核心層級執行緒（kernel threads, $K$ ），再由作業系統將核心執行緒排程到處理器（processors, $P$ ）上執行。

同一時間實際能執行的使用者執行緒數量，受三者中最小者限制：

\text{同時執行數} \leq \min(U,K,P)

題目已知 $U>P$ ，因此處理器數量少於使用者執行緒數量。判斷效能時，先看核心執行緒數是否足以讓所有處理器都有工作可做；超過處理器數的核心執行緒，通常不會讓計算密集型程式增加同時執行數。

解題方法

逐一比較 $K$ 和 $P$ ：

若 $K<P$ ，最多只有 $K$ 個使用者執行緒能同時執行，部分處理器無法被此程式充分利用。
若 $K\geq P$ ，且有足夠可執行的使用者執行緒，程式最多可同時使用 $P$ 個處理器。
當 $K>P$ 時，多出的核心執行緒可能在其他執行緒阻塞時提供調度彈性；但對計算密集型工作而言，不會突破 $P$ 個處理器的上限，還會帶來額外的排程與資源成本。

選項分析

(A) 核心執行緒數少於處理器數

此時 $K<P$ 。程式最多只能同時執行 $K$ 個使用者執行緒，因此無法用滿全部處理器。即使還有其他使用者執行緒等待執行，也可能因可用核心執行緒不足而無法及時派上用場。

效能影響： 核心執行緒數是平行度瓶頸，處理器利用率可能偏低。

(B) 核心執行緒數等於處理器數

此時 $K=P$ 。因為 $U>P$ ，使用者執行緒數足以提供工作；在核心執行緒均可執行的情況下，程式最多可同時使用全部 $P$ 個處理器。

效能影響： 可達到處理器數所允許的最大同時執行數，且沒有多配置核心執行緒的額外成本。

(C) 核心執行緒數多於處理器數，但少於使用者執行緒數

Question 7

Consider the following page reference string: $7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 1, 0, 5, 4, 6, 2, 3, 2, 3, 0, 1$ .

Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms?

LRU replacement
FIFO replacement
Optimal replacement

Select the correct answers:

(A) 18 for LRU
(B) 19 for FIFO
(C) 17 for FIFO
(D) 14 for LRU
(E) 14 for optimal replacement

Accepted Answer

核心觀念

每次參考的頁面若已在 3 個頁框中，就是命中；否則發生一次缺頁。頁框尚有空位時直接載入；頁框已滿時，依替換演算法選出一頁換出。

LRU：換出最近最久未被使用的頁面。
FIFO：換出最早載入的頁面；命中不會改變載入順序。
Optimal：換出未來最晚才會再使用的頁面；若某頁未來不再使用，就優先換出。

解題方法

依參考字串由左至右模擬。前三個不同頁面填滿頁框；之後每遇到不在頁框中的頁面，依各演算法規則換出一頁並計一次缺頁。

LRU

缺頁位置如下；位置以題目中頁面參考的先後次序編號：

1,2,3,4,6,7,8,9,10,11,12,13,14,15,16,17,20,21

命中位置為 $5,18,19$ ，因此：

\text{缺頁數}=21-3=18

頁框滿載後的換出順序，可用來核對模擬：位置 $4,6,7,8,9,10,11,12,13,14,15,16,17,20,21$ 分別換出 $7,3,1,2,5,3,4,6,7,1,0,5,4,6,2$ 。

FIFO

命中位置為 $5,7,18,19$ ；其餘位置皆缺頁：

1,2,3,4,6,8,9,10,11,12,13,14,15,16,17,20,21

因此：

\text{缺頁數}=21-4=17

例如，位置 $4$ 載入頁面 $1$ 時，最早載入的頁面 $7$ 被換出；位置 $5$ 命中頁面 $2$ ，但不會改變 FIFO 的載入先後順序。

Optimal

頁框滿載後，按未來使用時機換出的頁面為：

參考位置	載入頁面	換出頁面	判斷依據
4	1	7	7 下次出現在位置 10，比 2、3 晚

Question 8

When using computers, normal users are generally not actively aware of (A) Resource allocation (B) Interactivity (C) Continuity (D) Responsiveness (E) None of the above

Accepted Answer

核心觀念 作業系統負責管理電腦資源，並提供使用者與程式使用電腦的環境。處理器時間、記憶體、儲存空間與輸入輸出裝置，都需要由作業系統分配與管理。這些工作多半在背景進行，使用者通常只關注自己操作的程式與結果。 互動性與回應速度則直接影響使用者操作電腦的感受；系統是否能維持連續服務，也會在當機或中斷時被使用者察覺。 解題方法 判斷各選項是否屬於使用者操作時直接感受到的特性。若一項工作主要由作業系統在背景執行，且使用者無須直接介入，便符合「一般使用者通常不會主動察覺」的描述。 選項分析 - (A) Resource allocation（資源分配）— 正確。 作業系統會分配處理器時間、記憶體與裝置等資源。使用者通常不會直接管理這些分配，只會透過程式執行狀況間接感受到系統資源是否充足。

Question 9

Choose the correct statements from the multiple choices.

(A) TLBs are more beneficial with multi-level page tables than with single-level page tables.
(B) Given a constant number of bits in a virtual address, the size of a linear page table decreases with larger pages.
(C) The longer the time slice, the more a RR scheduler gives similar results to a FIFO scheduler.
(D) An SJF scheduler may preempt the currently running job.
(E) None of the above.

Accepted Answer

核心觀念 本題綜合分頁表與 CPU 排程：TLB 的效益、線性分頁表大小、RR 與 FIFO 的關係、SJF 是否搶先。 選項分析 - (A) 正確。 多層分頁表在 TLB 未命中時要逐層讀記憶體（例如兩層就要多讀兩次），一次未命中的代價比單層分頁表大得多；TLB 命中可以省下整段走表，所以 TLB 對多層分頁表的效益更大。 - (B) 正確。 線性分頁表的項目數＝$2^{	ext{VPN 位元數}}$。虛擬位址位元數固定時，頁面越大，偏移量位元越多、VPN 位元越少，分頁表項目數就越少。例如 32 位元位址：4 KB 頁需 $2^{20}$ 項，16 KB 頁只需 $2^{18}$ 項。 - (C) 正確。 Round Robin 的時間片越長，越多工作能在一個時間片內做完而不被切換；

Question 10

Choose the correct statements from the multiple choices.

(A) Multiprogramming is unnecessary on single-user systems.
(B) When an I/O operation completes, the previously blocked process moves into the RUNNING state.
(C) If a physical address is 32 bits and each page is 4KB, the top 18 bits exactly designate the physical page number.
(D) The number of virtual pages is identical to the number of physical pages.
(E) None of the above.

Accepted Answer

核心觀念 本題考查多工系統的程序狀態，以及分頁記憶體中的位址切分。 - 程序等待的 I/O 完成後，會從 阻塞狀態轉為就緒狀態；取得 CPU 後才進入執行狀態。 - 分頁位址由「頁框編號」與「頁內位移」組成。頁面大小為 $2^k$ 位元組時，位址低 $k$ 位元是頁內位移，其餘高位元是頁框編號。 - 虛擬記憶體與實體記憶體的頁數由各自的位址空間大小決定，兩者不必相同。 解題方法 逐項檢查程序狀態轉換與位址位元數。 每頁大小為 $4	ext{ KB}=4096=2^{12}$ 位元組，因此頁內位移占 $12$ 位元。實體位址共 $32$ 位元，實體頁框編號占： $$ 32-12=20	ext{ 位元} $$ 因此實體頁框編號是實體位址的高 $20$ 位元。 選項分析

Question 11

Choose the correct statements from the multiple choices.

(A) Given a 2-level page table (and no TLB), exactly 3 memory accesses are needed to fetch an instruction.
(B) In an unsafe state, the operating system is deadlocked.
(C) Banker's algorithm is a deadlock avoidance algorithm.
(D) The wait-for graph is used for deadlock detection.
(E) None of the above.

Accepted Answer

核心觀念 本題考查分頁位址轉換，以及死結預防、避免與偵測的基本概念。 在沒有快取轉譯後備緩衝器（TLB）的兩層頁表系統中，處理器需依序查詢兩層頁表，再存取指令本身。若假設頁表項目與指令都在主記憶體中，取指共需： $$ 	ext{兩次頁表存取}+	ext{一次指令存取}=3	ext{ 次記憶體存取} $$ 死結分析中，不安全狀態代表系統無法保證所有程序都能依序完成，但不表示死結已經發生。銀行家演算法用來避免進入不安全狀態；等待圖則可用來偵測死結。 解題方法 逐項對照定義判斷： 1. 先數出兩層頁表位址轉換需要的記憶體存取次數，再加上實際讀取指令的一次存取。 2. 區分「不安全狀態」與「死結狀態」。 3. 判斷銀行家演算法與等待圖分別用於哪一類死結處理。 選項分析 (A) 正確。 沒有 TLB 時，處理器須先讀取第一層頁表項目，再讀取第二層頁表項目，取得實體位址後才讀取指令。因此共需兩次頁表存取加一次指令存取，合計三次。

Question 12

Choose the correct statements from the multiple choices regarding networking.

(A) The length of IPv6 header is four times the length of IPv4 header.
(B) IPv6 does not support broadcast address type.
(C) IPsec security is mandated in the IPv6 protocol specification.
(D) IPv6 does not allow routers to fragment packets.
(E) None of the above.

Accepted Answer

核心觀念 本題考查 IPv4 與 IPv6 的標頭長度、位址類型、IPsec 規範，以及 IPv6 的封包分片方式。判斷時要區分 IPv6 固定標頭與延伸標頭，也要留意「規範曾要求」與「現行規範要求」並不相同。 解題方法 依序核對 IPv6 的固定標頭長度、位址架構、現行節點要求與分片規則，再判斷各敘述是否正確。IPv4 基本標頭最短為 20 位元組；IPv6 固定標頭為 40 位元組，因此： $$ \frac{40}{20}=2 $$ IPv4 標頭可因選項而加長，但這不會使 IPv6 固定標頭成為 IPv4 基本標頭的四倍。 選項分析 - (A) 錯誤。 IPv6 固定標頭為 40 位元組，IPv4 基本標頭為 20 位元組，前者是後者的兩倍，不是四倍。IPv6 的延伸標頭另行排列，也不算在固定標頭長度內。

Question 13

About single-cycle and multi-cycle implementation of CPU in computer organization, which of the following statements are NOT true?

(A) Single-cycle implementation of CPU is not used in the mainstream processors nowadays.
(B) For single-cycle implementation of CPU, the clock cycle is determined by the shortest possible path.
(C) Single-cycle implementation of CPU allows a functional unit to be used more than once per instruction.
(D) Compared to single-cycle implementation, multicycle implementation is more efficient.
(E) Multicycle implementation is more suitable for pipeline implementation.

Accepted Answer

核心觀念 - 單週期（single-cycle）CPU：每道指令一個時脈完成，時脈週期必須遷就最慢（最長）的指令路徑；一道指令內每個功能單元只能用一次，所以要重複配置硬體（例如另外的加法器、分開的指令與資料記憶體）。 - 多週期（multi-cycle）CPU：把指令拆成數個步驟，每步一個較短的時脈；不同指令可用不同的週期數，功能單元（ALU、記憶體）可在同一指令的不同步驟中重複使用。 本題問的是「不正確」的敘述。 選項分析 - (A) 正確敘述。 單週期設計時脈太長、效率差，現今主流處理器不採用（主流是管線化設計）。 - (B) 不正確。 單週期設計的時脈週期由最長的路徑（通常是 load 指令）決定，不是最短路徑；

Question 14

Which of the following statements are NOT true?

(A) For a cache with write-back strategy, read misses might result in writes.
(B) For a cache with write-through strategy, a write buffer is not necessary.
(C) Write after write (WAW) hazards can be resolved by register renaming.
(D) Read after write (RAW) hazards can be resolved by register renaming.
(E) Distributed shared-memory scheme will not result in non-uniform memory access time for multiprocessor machines.

Accepted Answer

核心觀念 本題考查快取寫入策略、指令相依性與多處理器記憶體架構： - 寫回式（write-back）快取：資料先寫入快取；快取區塊被替換時，若該區塊已修改，才寫回主記憶體。 - 寫入直達式（write-through）快取：每次寫入快取時，也同步更新下一層記憶體。寫入緩衝區可暫存待寫入資料，減少處理器等待，但不是維持正確性的必要條件。 - 暫存器重新命名（register renaming）可消除名稱相依造成的 WAW、WAR 假相依；RAW 是真實資料相依，不能靠重新命名消除。 - 非均勻記憶體存取（NUMA）系統中，處理器存取本地與遠端記憶體的延遲不同。分散式共享記憶體可提供共享位址空間，但不代表各記憶體位置的存取時間相同。 解題方法 逐項判斷敘述是否符合上述定義。尤其要區分兩件事：寫入緩衝區是效能設計，並非寫入直達式快取正確運作的必要條件；而暫存器重新命名只能處理假相依，不能消除 RAW 真相依。 選項分析 (A) 正確。 寫回式快取發生讀取未命中時，若需要替換的快取區塊已被修改，必須先將該區塊寫回記憶體，才能載入新區塊。因此，讀取未命中可能引發寫入。

Question 15

Which of the following statements are true?

(A) The motivation of dynamic scheduling does not include preventing out-of-order completion.
(B) Using separated instruction cache and data cache instead of a unified cache could mainly reduce data hazard.
(C) Reduced instruction set computer (RISC) has become obsolete now.
(D) Long memory latency and limits of power have limited the growth of uniprocessor performance and motivated the trend of developing multiple processors per chip in recent years.
(E) None of the above.

Accepted Answer

核心觀念

本題考查動態排程、快取組織、RISC 與單核心效能成長受限的原因。

動態排程會依運算元是否就緒來安排指令執行，藉此減少資料相依造成的停等並提升指令層級平行性。指令的執行完成順序可能不同於程式順序；若處理器要維持精確例外與正確的架構狀態，通常再以重排序緩衝區（ROB）讓指令依程式順序退休。

解題方法

逐項辨認各敘述描述的是哪種硬體機制，以及它解決的問題：

動態排程處理指令執行順序與相依問題。
分離指令快取與資料快取主要改善資源競用。
RISC 仍是現代處理器採用的重要架構。
記憶體延遲與功耗限制促使設計轉向多核心。

選項分析

(A) 正確。 動態排程的主要目的，是在不違反資料相依的前提下，讓就緒指令先執行，減少管線停等並提高平行度；它不是為了阻止指令以不同於程式順序的次序完成。若要確保架構狀態依程式順序更新，會由 ROB 等機制負責指令退休。因此要區分「執行完成」與「依序退休」。

Question 16

Which of the following statements are true regarding virtual memory?

(A) Address translation is a process to translate a virtual address to register number.
(B) Physical address is an address of the register.
(C) If translation-lookaside buffer (TLB) misses, it is possible to find the entry in page table.
(D) The number of bits for the virtual page number in virtual address has to be the same as the number of bits for the physical page number in physical address.
(E) When an OS performs context switch from P1 to P2, the OS must ensure P2 cannot get access to the page tables of P1.

Accepted Answer

核心觀念 虛擬記憶體利用頁表把程序使用的虛擬位址對應到實體記憶體中的實體位址。常見位址可拆成頁號與頁內位移： $$ 	ext{虛擬位址} = 	ext{虛擬頁號} \,\|\, 	ext{頁內位移} $$ $$ 	ext{實體位址} = 	ext{實體頁框號} \,\|\, 	ext{頁內位移} $$ 頁表保存虛擬頁號與實體頁框號的對應；TLB 則是用來快取部分頁表項目的高速記憶體。不同程序通常有各自的位址空間，作業系統必須維持程序間的記憶體隔離。 解題方法 逐項確認敘述是否符合三個基本原則： 1. 位址轉換的目的地是實體位址，不是暫存器編號。 2. TLB 未命中時，仍可查詢頁表；查詢頁表與發生缺頁是不同事件。 3. 虛擬位址與實體位址的總位元數可不同，因此虛擬頁號與實體頁框號的位元數不必相同。 4. 切換程序時，作業系統必須維持位址空間隔離，避免一個程序讀寫另一個程序的頁表。 選項分析 (A) 錯誤。 位址轉換是將虛擬位址轉換成實體位址。暫存器編號是處理器內部用來識別暫存器的資訊，不是位址轉換的目標。

Question 17

Which of the following statements are true regarding the design of a MIPS CPU?

(A) Data forwarding can be used to partially solve Read-After-Write hazard.
(B) Branch prediction helps prevent data hazard.
(C) Pipelining reduces the time it takes to complete an individual instruction.
(D) The branch target address of the beq instruction is known at the compile time.
(E) Pipelining increases the number of simultaneously executing instructions.

Accepted Answer

核心觀念

本題考查 MIPS 管線中的資料相依、分支控制，以及管線對指令吞吐量與延遲的影響。

RAW（Read-After-Write）資料相依：後一條指令要讀取前一條指令尚未寫回的結果。
資料轉送（data forwarding）：將前一條指令的結果直接送到後一條指令需要的管線階段，減少等待。
管線化（pipelining）：讓多條指令分別占用不同管線階段、重疊執行，主要提升吞吐量；單一指令完成所需的延遲不因此縮短。
分支目標位址與分支是否成立是兩件事。beq 的目標位址由指令位址及指令中的位移量計算；比較暫存器的結果才決定是否跳轉。

解題方法

逐項判斷敘述涉及的是資料相依、控制相依、單一指令延遲，還是管線吞吐量。特別注意，資料轉送處理的是資料相依；分支預測處理的是控制相依。

MIPS 的 beq 分支目標位址為：

\text{Target} = (\text{PC} + 4) + \bigl(\text{sign-extend}(\text{immediate}) \ll 2\bigr)

指令位址與位移量確定後，目標位址即可在編譯或組譯階段決定；分支是否成立則要等執行時比較暫存器。

選項分析

Question 18

Which of the following statements are true regarding MIPS ISA?

(A) The stack frame is the collection of all data on the stack associated with one subprogram call.
(B) The frame pointer is a register that stores the address to the top of the stack.
(C) Stack overflow happens when the stack pointer exceeds the stack bound.
(D) The jal instruction should be called when a procedure finishes and is ready to return to the caller.
(E) The beq instruction has three operands: two registers that are compared for equality, and a register to specify the branch target address.

Accepted Answer

核心觀念 MIPS 的程序呼叫慣例：jal 呼叫、jr $ra 返回；堆疊由 $sp 指向頂端並往低位址成長；$fp（frame pointer）指向目前程序框（stack frame）的起點。beq 是 I 格式指令。 選項分析 - (A) 正確。 堆疊框（stack frame，又稱 procedure frame / activation record）就是一次程序呼叫在堆疊上配置的所有資料：保存的暫存器、區域變數、傳遞的參數等。 - (B) 錯誤。 指向堆疊頂端的是 stack pointer（$sp）；frame pointer（

Question 19

Which of the following statements are true regarding memory and cache?

(A) Spatial locality means that if an item is referenced, it will tend to be referenced soon.
(B) Increasing the size of a cache block makes better use of the spatial locality.
(C) If we use the “write through” policy, the dirty bit is needed.
(D) When increasing cache associativity, we increase the utilization of the cache.
(E) A direct mapped cache has a lower cache miss rate than a fully associative cache.

Accepted Answer

核心觀念 - 時間區域性（temporal locality）：某個位址被存取後，近期內很可能再次被存取。 - 空間區域性（spatial locality）：某個位址被存取後，附近的位址很快也會被存取。 - 寫入策略：write-through 每次寫入都同步寫到下一層；write-back 只寫快取，需要 dirty bit 記錄哪些區塊被改過。 - 關聯度（associativity）越高，衝突未命中越少。 選項分析 - (A) 錯誤。 「被存取後很快會再被存取」描述的是時間區域性；空間區域性指的是附近的資料很快會被存取。 - (B) 正確。 區塊越大，一次未命中就把相鄰的資料一起搬進快取，之後存取附近位址時可以命中，更能利用空間區域性（但區塊過大會增加未命中代價、減少區塊數）。

Question 20

Which of the following statements are true regarding pipelining and parallelization?

(A) The purpose of loop unrolling is to decrease program code size.
(B) The purpose of register renaming is to increase readability.
(C) The VLIW (Very Long Instruction Word) is a style of instruction set architecture that launches many dependent operations in a single wide instruction.
(D) A superscalar processor can dispatch multiple instructions simultaneously.
(E) The static multiple issue is an approach to implement a multiple-issue processor where many decisions are made by the compiler.

Accepted Answer

核心觀念 本題考查處理器如何透過指令管線、指令級平行與編譯器轉換提升效能。判斷時要分清楚各技術的目的： - 迴圈展開減少迴圈控制指令與分支次數，通常會增加程式碼大小。 - 暫存器重新命名消除名稱相依造成的假相依，讓更多指令能平行執行。 - VLIW 將多個可平行執行的操作打包在一條寬指令中。 - 超純量處理器可在同一個時脈週期發出多條指令。 - 靜態多重發射主要由編譯器在執行前安排指令與發射槽。 解題方法 逐項比對敘述中的技術定義與目的，尤其留意「減少程式碼大小」、「增加可讀性」及「相依操作」等用詞是否符合技術的實際功能。 選項分析 (A) 錯誤。 迴圈展開是複製迴圈本體，讓每次迴圈處理多筆資料，藉此減少分支與迴圈控制指令的執行次數，並提升指令級平行度。複製本體會使程式碼通常變大，因此目的不是減少程式碼大小。

109 年 國立中央大學資訊工程學系碩士班《作業系統與計算機組織》

第 1 題5 分

第 2 題5 分

核心觀念

解題方法

第 3 題5 分

第 4 題5 分

核心觀念

解題方法

選項分析

第 5 題5 分

第 6 題5 分

核心觀念

解題方法

選項分析

第 7 題5 分

核心觀念

解題方法

LRU

FIFO

Optimal

第 8 題5 分

第 9 題5 分

第 10 題5 分

核心觀念

解題方法

選項分析

第 11 題5 分

核心觀念

解題方法

選項分析

第 12 題5 分

第 13 題5 分

第 14 題5 分

核心觀念

解題方法

選項分析

第 15 題5 分

核心觀念

解題方法

選項分析

第 16 題5 分

核心觀念

解題方法

選項分析

第 17 題5 分

核心觀念

解題方法

選項分析

第 18 題5 分

第 19 題5 分

第 20 題5 分

核心觀念

解題方法

選項分析

其他考古題

109 年中央大學的其他科目

中央大學《作業系統與計算機組織》其他年度

其他學校的資工系考古題

109 年國立中央大學資訊工程學系碩士班《作業系統與計算機組織》