以下是為您提取的國立中央大學 111 學年度碩士班考試入學試題(科目:作業系統與計算機組織)全份考卷文字內容:


# 一、單選題(每題 5 分,答錯倒扣 2 分,倒扣至單選題 0 分為止)

  1. We define the speedup of a system by the execution time before improvement divides the execution time after improvement. Suppose a module accounts for 40% computation time of the entire system. We enhance the module to be 10 times faster. What is the overall speedup after the enhancement (approximate to two decimal places)?
    • 1.40
    • 2.17
    • 1.56
    • 1.10
    • None of the above
詳解

根據阿姆達爾定律(Amdahl’s Law),整體加速比公式為:

Soverall=1(1−f)+fSenhancedS_{\text{overall}} = \frac{1}{(1 - f) + \frac{f}{S_{\text{enhanced}}}}

代入題目數值(受影響比例 f=0.4f = 0.4,局部加速比 Senhanced=10S_{\text{enhanced}} = 10):

  • 不受影響比例:1−f=1−0.4=0.61 - f = 1 - 0.4 = 0.6
  • 受影響部分改善後的時間比例:0.410=0.04\frac{0.4}{10} = 0.04
  • 整體加速比:S_{\text{overall}} = \frac{1}{0.6 + 0.04} = \frac{1}{0.64} = 1.5625 \approx \mathbf
  1. For a 16K-byte two-way set associative cache whose block size is 4 bytes, if the length of the address is 32 bits, how many bits are used for tag?
    • 15
    • 16
    • 17
    • 18
    • 19
詳解

在 32-bit 位址中,位址切分為 [ Tag | Index | Offset ] 三部分:

  1. Offset(塊內偏移量):Block size = 4 bytes=22 bytes  ⟹  Offset=2 bits4 \text{ bytes} = 2^2 \text{ bytes} \implies \text{Offset} = 2 \text{ bits}。
  2. Index(組索引):
    • Cache 總容量 = 16 KB=214 bytes16\text{ KB} = 2^{14} \text{ bytes}。
    • 總組數(Number of Sets) = Cache 總容量Block size×Associativity=2144×2=21423=211  ⟹  Index=11 bits\frac{\text{Cache 總容量}}{\text{Block size} \times \text{Associativity}} = \frac{2^{14}}{4 \times 2} = \frac{2^{14}}{2^3} = 2^{11} \implies \text{Index} = 11 \text{ bits}。
  3. Tag(標籤位元數):
    • Tag=32−(Index+Offset)=32−(11+2)=19 bits\text{Tag} = 32 - (\text{Index} + \text{Offset}) = 32 - (11 + 2) = \mathbf{19 \text{ bits}}。
  1. Assume that an un-pipelined machine has 8ns clock cycles. The machine uses four cycles for ALU operations, five cycles for branches, and five cycles for memory operations. The relative frequencies of these operations are 30%, 30%, and 40%, respectively. Suppose that pipelining the machines adds 1ns of overhead to the clock cycle time. Assume that the ideal CPI is one after pipelining. Ignore any other impact. What is the speedup in the instruction execution rate gained from pipelining the machine?
    • 4.07
    • 4.18
    • 4.29
    • 4.33
    • 4.51
詳解
  1. 未管線化(Un-pipelined)平均每條指令執行時間:
    • 平均 \text{CPI}_{\text{unpipe}} = (0.3 \times 4) + (0.3 \times 5) + (0.4 \times 5) = 1.2 + 1.5 + 2.0 = 4.7 \text
    • 平均指令執行時間 = 4.7 \times 8\text{ ns} = 37.6\text
  2. 管線化(Pipelined)平均每條指令執行時間:
    • 時脈週期 =8 ns+1 ns=9 ns= 8\text{ ns} + 1\text{ ns} = 9\text{ ns},理想 CPIpipe=1\text{CPI}_{\text{pipe}} = 1
    • 平均指令執行時間 = 1 \times 9\text{ ns} = 9\text
  3. 加速比(Speedup):

    Speedup=37.6 ns9 ns≈4.1777≈4.18\text{Speedup} = \frac{37.6\text{ ns}}{9\text{ ns}} \approx 4.1777 \approx \mathbf{4.18}

  1. Consider the C code below. A user executes the executable of the code on a Linux shell. Assume it executed successfully. How many processes have been created by executing the C code, including the original process that executes main() ?
1
2
3
4
5
6
7
8
9
10
11
12
int main() {
pid_t pid;
int i=0;
for (i=0; i<4; i++) {
pid = fork();
if (pid < 0) {
fprintf(stderr, "fork error\n");
exit(-1);
}
}
return 0;
}

{.quiz .single}
- 4
- 5
- 16{.correct}
- 17
- 33

詳解

每執行一次 fork() ,當前的行程數量就會變為原本的 2 倍(父行程與新建立的子行程)。

  • for 迴圈共執行 n=4n = 4 次(i=0,1,2,3i = 0, 1, 2, 3)。
  • 包括原始執行 main() 的父行程在內,總行程數為 2n=24=162^n = 2^4 = \mathbf{16} 個。
  1. Consider the CPU burst timeline of four processes, as shown below. The processes need to share one CPU, and the OS uses the round-robin algorithm with time quantum = 5 for scheduling. Let the context switch time be very close to 0. Let the average waiting time of the processes be tt. Which of the following is true?
Process Arrival Time Burst Time
P1 0 10
P2 1 6
P3 12 2
P4 13 3
詳解

甘特圖(Gantt Chart)執行時序追蹤(Time Quantum = 5):

  • t=0∼5t = 0 \sim 5:P1P_1 執行 5 單位(剩餘 5)。
  • t=5∼10t = 5 \sim 10:P2P_2 於 t=1t=1 到達,執行 5 單位(剩餘 1)。
  • t=10∼15t = 10 \sim 15:P1P_1 執行剩餘 5 單位,P1P_1 完成(Completion = 15)。
  • t=15∼16t = 15 \sim 16:P2P_2 執行剩餘 1 單位,P2P_2 完成(Completion = 16)。
  • t=16∼18t = 16 \sim 18:P3P_3 於 t=12t=12 已到達,執行 2 單位,P3P_3 完成(Completion = 18)。
  • t=18∼21t = 18 \sim 21:P4P_4 於 t=13t=13 已到達,執行 3 單位,P4P_4 完成(Completion = 21)。

計算各行程等待時間(Waiting Time=Completion−Arrival−Burst\text{Waiting Time} = \text{Completion} - \text{Arrival} - \text{Burst}):

  • P1=15−0−10=5P_1 = 15 - 0 - 10 = 5
  • P2=16−1−6=9P_2 = 16 - 1 - 6 = 9
  • P3=18−12−2=4P_3 = 18 - 12 - 2 = 4
  • P4=21−13−3=5P_4 = 21 - 13 - 3 = 5

平均等待時間:

t=5+9+4+54=234=5.75t = \frac{5 + 9 + 4 + 5}{4} = \frac{23}{4} = \mathbf{5.75}

落在 6≥t≥56 \ge t \ge 5 的區間內。

  1. Memory page-replacement algorithms may have different page fault rates. Given the reference string "1 5 4 6 4 1 5 4 1 6 2 3 1 6" and the number of page frames 3, which of the following is true?
    • The number of page faults is 8 when the FIFO algorithm is used.
    • The number of page faults is 8 when the stack-based LRU algorithm is used.
    • The number of page faults is 8 when the optimal algorithm is used
    • The optimal algorithm has the best performance among all the page replacement algorithms, and thus modern OSes usually use this algorithm to implement memory page replacement.
    • None of the above.
詳解

針對參考字串 1, 5, 4, 6, 4, 1, 5, 4, 1, 6, 2, 3, 1, 6 與 3 個 Page Frames:

  • (A) FIFO 演算法追蹤結果共產生 12 次 Page Faults(非 8 次)。
  • (B) LRU 演算法追蹤結果共產生 11 次 Page Faults(非 8 次)。
  • © Optimal 演算法追蹤結果共產生 11 次 Page Faults(非 8 次)。
  • (D) Optimal 演算法需要預知未來的頁面參考序列,無法在實際作業系統中實作,僅作為理論效能評估基準。
    因此以上皆非,選 (E)。
  1. Which of the following is not true?
    • Kubernetes, also known as K8s, is a system for automating deployment, scaling, and management of containerized applications.
    • Docker is a system that virtualizes hardware.
    • Para-virtualization is the technique in which the guest operating system is modified to work in cooperation with the VMM to optimize performance.
    • Para-virtualization allows virtualization of older x86 CPUs (and others) without binary translation.
    • Java virtual machine includes garbage collection to automatically reclaim memory (Java objects) no longer in use.
詳解
  • (B) Docker 是作業系統層級的虛擬化(OS-level virtualization / 容器化技術),它直接共用主機作業系統的核心(Host OS Kernel),並不是模擬整台實體機器的「硬體虛擬化(Hardware virtualization)」。
  • 其餘 (A)、©、(D)、(E) 皆為正確敘述。
  1. The right side shows a solution to the producer-consumer problem with nn buffers using three semaphores, where empty=n , mutex=1 , and full=0 at the initial state. Some variables are missing in the consumer program. What are they?
1
2
3
4
5
6
7
8
9
// Consumer process
do {
wait(V1);
wait(V2);
// remove an item
signal(...);
signal(...);
// consume the item
} while (TRUE);

{.quiz .single}
- V1=mutex, V2=empty
- V1=mutex, V2=full
- V1=empty, V2=mutex
- V1=full, V2=empty
- V1=full, V2=mutex

詳解
  • 消費者(Consumer)必須先確認緩衝區內有資料可拿(即執行 wait(full) ),接著才取得互斥鎖進入臨界區間(執行 wait(mutex) )。
  • 若順序顛倒(先 wait(mutex) 再 wait(full) ),當緩衝區全空時消費者會抱著 mutex 進入睡眠,導致生產者無法進入緩衝區放入資料而引發死結(Deadlock)。
  • 因此 V1=full , V2=mutex 。

# 二、多選題(每題 5 分,每個選項單獨計分,答錯一個選項倒扣 1 分,倒扣至多選題 0 分為止)

  1. The architecture of a single cycle CPU is shown in the Figure. Select the correct statements based on the Figure.
    • Sending the value of PC register to an adder can determine the register number for rd (the register destination operand).
    • Performing “Sign extend” to the Instruction[15-0] produces an signed integer with 32 bits.
    • Sending the Zero signal from the ALU to the AND gate determines whether Instruction[31-26] represents Branch operator or not.
    • The Mux before the “Write register” determines whether to write new data to the destination register or not.
    • None of the above.
詳解
  • (A) PC 暫存器送入加法器是為了計算 PC + 4 或分支目標位址,目的暫存器 rd 的編號直接來自指令欄位 Instruction[15-11] 。
  • (B) 將 I-type 指令中的 16 位元立即數( Instruction[15-0] )經過符號擴展(Sign extend),會產生具備相同正負號數值的 32 位元有號整數。
  • © Instruction[31-26] 是 Opcode,由 Control Unit 解碼來判斷是否為 Branch 指令;ALU 的 Zero 訊號送入 AND 閘是用來判斷分支條件是否成立(決定 PCSrc 是否跳躍)。
  • (D) Write register 前面的多工器(由 RegDst 控制)是用來選擇寫入的目的地暫存器編號為 rt ( Instruction[20-16] )或 rd ( Instruction[15-11] );決定「是否寫入」的是 RegWrite 控制訊號。
  1. The IEEE 754 standard specifies a binary16 as sign bit (1 bit), exponent (5 bits), and significand (10 bits). The exponent bias is 15. We define a new format by increasing the exponent to 8 bits and decreasing significand to 7 bits. We set the exponent bias in the new format as 127. Which of the following statements are true?
    • The new format has a larger dynamic range.
    • The new format has a lower precision.
    • Based on IEEE 754, a 16-digit binary number 0100 0010 0000 0000 represents the decimal number 3.
    • Based on the new format, a 16-digit binary number 0100 0010 0000 0000 represents the decimal number 32.
    • None of the above.
詳解
  • (A) 指數位元由 5 bits 增加為 8 bits(與 IEEE 754 single precision 相同指數寬度,即 Google bfloat16 格式),能表達的數值上下限大幅擴張,因此具有更大的動態範圍(Larger dynamic range)。
  • (B) 尾數位元由 10 bits 縮減為 7 bits,有效數位減少,因此具有較低的精度(Lower precision)。
  • © 以標準 binary16(1 位符號、5 位指數 Bias=15、10 位尾數)拆解 0 10000 1000000000 :
    • Sign=0\text{Sign} = 0(正數)
    • Exponent=100002=16  ⟹  e=16−15=1\text{Exponent} = 10000_2 = 16 \implies e = 16 - 15 = 1
    • Significand=1.12=1.5\text{Significand} = 1.1_2 = 1.5
    • 數值 =1.5×21=3= 1.5 \times 2^1 = \mathbf{3}。
  • (D) 以新格式(1 位符號、8 位指數 Bias=127、7 位尾數)拆解 0 10000100 0000000 :
    • Sign=0\text{Sign} = 0(正數)
    • Exponent=100001002=128+4=132  ⟹  e=132−127=5\text{Exponent} = 10000100_2 = 128 + 4 = 132 \implies e = 132 - 127 = 5
    • Significand=1.02=1.0\text{Significand} = 1.0_2 = 1.0
    • 數值 =1.0×25=32= 1.0 \times 2^5 = \mathbf{32}。
  1. Which of the following statements are true regarding inclusive cache?
    • The top-level cache is a subset of the bottom-level cache.
    • If a block A is presented in both L1 and L2 cache where L2 is inclusive of L1, evicting the block A from L1 will cause L2 to evict block A.
    • Inclusive cache utilizes the available cache space more efficiently.
    • Inclusive cache ensures data consistency in the bottom-level cache.
    • None of the above.
詳解
  • (A) ** 包容性快取(Inclusive cache)** 的定義即為底層快取(如 L2)包含所有頂層快取(如 L1)中的資料區塊,故 L1 是 L2 的子集(Subset)。
  • (B) 因果顛倒:當 L2 驅逐區塊 A 時,為維持包容性必須強迫 L1 也跟著驅逐(Invalidate)A;但當 L1 驅逐 A 時,L2 不需要跟著驅逐 A。
  • © Inclusive cache 因為 L2 必須重複儲存 L1 已經有的資料,空間利用率反而不如 Exclusive cache。
  • (D) Inclusive cache 主要用於簡化多核心架構下的快取一致性探測(Snooping filter),並非直接確保底層快取的資料一致性。
  1. Which of the following statements are true regarding Instruction cache (I-cache) and Data cache (D-cache) in L1 cache?
    • Compared with the original I-cached miss rate, the L1 cache miss rate will increase when I-cache and D-cache are merged.
    • The L1 cache miss rate will decrease when I-cache and D-cache are merged, compared with the original D-cache miss rate.
    • We can use different path to access instruction and data at the same time.
    • Using separated I-cache and D-cache instead of a unified cache can reduce structural hazard.
    • None of the above.
詳解
  • (A)(B) 根據經典計算機組織教材(Hennessy & Patterson)數據,原始 I-cache 的 Miss rate 極低(如 0.4%),原始 D-cache 的 Miss rate 較高(如 11.4%)。當兩者合併為相同總容量的 Unified L1 Cache 時,整體 Miss rate(約 3.18%)會高於原本的 I-cache Miss rate,但低於原本的 D-cache Miss rate。
  • ©(D) 分離式快取(Split Cache / 哈佛架構)提供兩條獨立匯流排路徑,允許 CPU 在同一個週期同時進行指令擷取(IF)與資料記憶體存取(MEM),有效消除合併式快取所造成的結構危障(Structural Hazard)。
  1. Which of the following statements are NOT true for instruction set design and CPU implementation?
    • The advantages of dynamic scheduling include memory latency hiding and resolving real dependence which is unknown at compile time.
    • For single-cycle implementation of CPU, the clock cycle is determined by the longest possible path.
    • Compared to Memory-Memory architecture or Register-Memory architecture, Register-Register architecture has the advantage of having larger variation in Clock Cycle Per Instruction (CPI).
    • Reduced Instruction Set Computer (RISC) has become mainstream products.
    • Single-cycle implementation of CPU is more suitable for pipeline implementation compared with multi-cycle implementation.
詳解

本題要求選出 NOT true(錯誤) 的敘述:

  • (A) 為真:動態排程(Dynamic scheduling)能透過亂序執行隱藏記憶體存取延遲,並動態處理編譯期未知的相依性。
  • (B) 為真:單週期 CPU 的時脈週期取決於執行時間最長的指令路徑(如 lw )。
  • © 為假(應選):Register-Register(Load-Store)架構的指令格式整齊,各指令執行時間相近,其優勢在於擁有更小且更一致的 CPI 變異量(Smaller variation in CPI),而非較大的變異量。
  • (D) 為真:RISC 架構已成為現代處理器設計主流。
  • (E) 為假(應選):管線化(Pipeline)將指令執行拆分為多個獨立階段,是以 ** 多週期(Multi-cycle)** 切分階段的思想為基礎發展而來,而非單週期實作。
  1. Which of the following statements are true for pipeline hazards?
    • Compliers can schedule the instructions to avoid some pipeline hazards.
    • Using separated instruction cache and data cache instead of a unified cache could mainly reduce structural hazard.
    • Write after read (WAR) hazards can be resolved by register renaming.
    • Read after write (RAW) hazards can be resolved by register renaming.
    • None of the above.
詳解
  • (A) 編譯器可透過靜態指令排程(Instruction scheduling / Code reordering)重排指令順序以減少資料危障與控制危障停頓。
  • (B) 分離 I-cache 與 D-cache 主要是為了解決 IF 階段與 MEM 階段同時存取記憶體所產生的結構危障(Structural hazard)。
  • © **WAR(反相依性)與 WAW(輸出相依性)屬於名稱相依(Name dependence),可透過硬體的暫存器更名(Register renaming)** 完全消除。
  • (D) **RAW(真資料相依性)** 代表後方指令必須等待前方指令算出的真實數值,無法靠更改暫存器名稱消除(需靠 Forwarding 或 Stall 解決)。
  1. Which of the following statements are true?
    • Increasing associativity of a cache would usually reduce the miss rate and the hit time.
    • The branch offset field in the MIPS instruction is specified as a multiple of 4, i.e. a branch offset of 1 means 4 bytes. This enables a much larger range of branch offsets than if the offset were specified in bytes.
    • We can always increase the hit rate by increasing the size of a cache.
    • Pipeline registers between stages are necessary when performing pipelining.
    • MIPS instructions are 32 bits.
詳解
  • (A) 提高關聯度(Associativity)通常會降低 Miss rate,但因為需要比對更多 Tag 並經過多工器選擇,Hit time 反而會增加(變慢)。
  • (B) 因為 MIPS 指令長度固定為 4 bytes(Word-aligned),分支偏移量以 Word(4 bytes)為單位(硬體自動左移 2 位元),能將跳躍定址範圍擴大為以 byte 計算的 4 倍。
  • © 加大快取容量並不「總是(always)」能提升命中率(例如在循序存取大於快取的陣列或特定存取模式下)。
  • (D) 管線化必須在各個階段之間設置管線暫存器(Pipeline registers),才能在每個時脈邊緣保存並傳遞不同指令的中間狀態與控制訊號。
  • (E) 標準 MIPS 指令集(MIPS32)所有指令皆固定為 32 bits 長度。
  1. Choose the correct statements from the multiple choices regarding contention scope
    • Kernel thread scheduled onto available CPU is SCS.
    • Linux allows only PTHREAD_SCOPE_PROCESS.
    • Systems using the one-to-one model schedule threads using only SCS.
    • In Pthread scheduling API, PTHREAD_SCOPE_SYSTEM schedules threads using PCS scheduling.
    • None of the above
詳解
  • (A) 系統競爭範圍(System-Contention Scope, SCS)是指作業系統核心將核心執行緒排程到實體 CPU 上執行,競爭對象為全系統的所有執行緒。
  • (B) Linux 採用一對一(One-to-One)執行緒模型,僅支援 PTHREAD_SCOPE_SYSTEM ,不支援 PTHREAD_SCOPE_PROCESS 。
  • © 一對一模型(如 Linux、Windows)中,每個使用者執行緒皆直接對應一個核心執行緒,因此完全由核心採用 SCS 進行排班。
  • (D) PTHREAD_SCOPE_SYSTEM 使用的是 SCS 排班; PTHREAD_SCOPE_PROCESS 才是使用 PCS 排班。
  1. Choose the correct statements from the multiple choices regarding processor affinity
    • Linux supports hard affinity only.
    • Load balancing often counteracts the benefits of processor affinity.
    • The main-memory architecture of a system can affect processor affinity.
    • Soft affinity means that the process may require software that is available at only a particular site.
    • None of the above
詳解
  • (A) Linux 預設支援 Soft affinity(盡力維持行程在原 CPU 執行),同時也提供 sched_setaffinity() 系統呼叫支援 Hard affinity。
  • (B) 負載平衡(Load balancing)會將行程從忙碌的 CPU 遷移到閒置的 CPU,但這會導致原本留在舊 CPU 快取中的熱資料失效(Cache invalidation),進而抵銷處理器親和性帶來的效能優勢。
  • © 在 **NUMA(非均勻記憶體存取)** 架構下,CPU 存取本地記憶體(Local memory)遠快於存取其他節點的遠端記憶體(Remote memory),因此主記憶體架構會顯著影響處理器親和性的設計考量。
  • (D) Soft affinity 是指作業系統「盡力(Attempt)」讓行程留在同一個處理器上執行,但不做強制保證。
  1. Choose the correct statements from the multiple choices regarding network protocols
    • The BGP protocol is an intra-AS routing protocol.
    • HTTP adopts TLS to encrypt messages.
    • ARP requests are broadcast packets.
    • The ARP spoofing attack is to associate IP addresses to the wrong MAC address.
    • None of the above
詳解
  • (註:本題依官方標準題庫解答標記為 A、C)
  • © ARP Request 封包是以廣播(Broadcast,目標 MAC 為 FF:FF:FF:FF:FF:FF )方式在區域網路中發送,以查詢目標 IP 對應的 MAC 位址。
  • (B) 嚴格定義上 HTTP 為明文協定,是透過結合 TLS 升級為 HTTPS 協定來加密訊息。
  1. Choose the correct statements from the multiple choices
    • Threads that are part of the same process share the same stack
    • Threads that are part of the same process can access the same TLB entries.
    • A process is trashing if it is spending more time executing than paging.
    • Thrashing can be entirely solved by using a local replacement algorithm.
    • None of the above
詳解
  • (A) 同一行程底下的多個執行緒共享 Code、Data 與 Heap,但 ** 各自擁有獨立的堆疊(Stack)** 與暫存器狀態。
  • (B) 同一行程的執行緒共享相同的虛擬記憶體位址空間與分頁表(Page Table),因此可以存取相同的 TLB(Translation Lookaside Buffer)項目。
  • © 當發生 ** 磁碟擾動(Thrashing)** 時,行程花費在「分頁置換(Paging)」的時間遠大於實際執行(Executing)的時間。
  • (D) 區域置換演算法(Local replacement algorithm)只能限制 Thrashing 的擴散範圍(避免搶佔其他行程的頁框),並無法完全根治 Thrashing(需透過 Working Set Model 或 PFF 調整頁框配置)。
  1. Choose the correct statements from the multiple choices
    • Data access is one of reasons for process migration.
    • The standard UNIX pipe mechanism allows process migration.
    • Modularity is one of reasons for process cooperation.
    • Shared memory is one of models for interprocess communications among cooperating processes.
    • None of the above
詳解
  • (A) 行程遷移(Process migration)的常見動機包括負載平衡、運算加速與資料存取(Data access)—— 將行程移至龐大資料所在的節點以降低網路傳輸成本。
  • (B) 標準 UNIX Pipe 是用於單機內部具有親子關係行程間的通訊機制,與跨節點的行程遷移無關。
  • © 行程合作(Process cooperation)的四大理由:資訊共享(Information sharing)、計算加速(Computation speedup)、** 模組化(Modularity)** 與方便性(Convenience)。
  • (D) 行程間通訊(IPC)的兩大基礎模型為 ** 共享記憶體(Shared memory)** 與訊息傳遞(Message passing)。
更新於