113 年 國立成功大學資訊工程系碩士班《計算機組織與系統（計算機組織及作業系統）》

核心觀念

本題測驗作業系統（Operating System）中**雙重模式運作（Dual-Mode Operation）與特權指令（Privileged Instructions）**的保護機制：

1. 雙重模式（Dual-Mode Operation）：現代作業系統透過硬體的 Mode Bit 區分 使用者模式（User Mode，Mode Bit = 1） 與 核心／系統模式（Kernel / Supervisor / Monitor Mode，Mode Bit = 0）。
2. 特權指令（Privileged Instructions）：指具有潛在危險性、可能破壞系統穩定或危害其他行程（Process）執行的機器指令（如：直接操作硬體 I/O、修改基底／界限暫存器以保護記憶體、停用中斷、切換模式位元等）。
3. 特權指令的執行與防護：
   • 特權指令只能在核心模式下順利執行完成。
   • 若使用者模式下的程式**試圖（attempt）**執行特權指令，CPU 硬體會偵測到模式不符，並不會讓指令成功執行，而是立即觸發一個內部中斷／陷阱（Trap / Exception），將控制權交由作業系統核心的例行程式處置（通常會終止該違規程式，如印出 Illegal Instruction 或 Segmentation Fault）。

解題方法

判斷題目的核心問句「What statement concerning privileged instructions is considered false?」：
從 CPU 保護架構與指令執行流程著手，審視各選項關於特權指令的危害性、執行模式、硬體檢查機制與典型用途之敘述。關鍵切入點在於區分「指令被成功執行（executed）」與「嘗試發出指令（attempted）」。

選項分析

• (a) They may cause harm to the system.（敘述正確）
  特權指令涉及系統底層資源控制（例如直接存取實體記憶體、關閉中斷、直接寫入硬體暫存器等），若允許未授權程式隨意執行，極易導致系統崩潰、資料外洩或整個系統癱瘓，因此

核心觀念

本題測驗作業系統中**行程間通訊（Interprocess Communication, IPC）**的兩種基本架構：

1. 共享記憶體模型（Shared-Memory Model）：多個行程共享一塊實體記憶體空間，行程間可直接讀寫該區域以交換資料。
2. 訊息傳遞模型（Message-Passing Model）：行程間透過系統呼叫（如 send() 與 receive()）由作業系統核心或網路協定堆疊協助傳遞訊息封包。

在**單一電腦系統（Intracomputer）中，共享記憶體速度極快，但在多電腦／分散式系統（Intercomputer / Distributed Systems）**中，不同主機之間不具備實體共享的記憶體匯流排，若硬要在軟體層實作分散式共享記憶體（DSM），實作與快取一致性（Cache Coherence）的維護成本極高；相對而言，訊息傳遞模型天然對應到網路封包交換架構，更易於在分散式環境下實作。

解題方法

本題切入點在於**「單一主機（Intra-system）」與「跨主機（Inter-system / Intercomputer）」通訊特性的對比**：

• 速度比較（Speed）：在單一主機內，共享記憶體的速度快於訊息傳遞（因為訊息傳遞需要頻繁進行系統呼叫與核心空間介入），因此訊息傳遞並非比共享記憶體快。
• 跨電腦實作難度（Implementation for Intercomputer Communication）：在跨電腦環境（Intercomputer）中，實體記憶體彼此獨立，訊息傳遞模型天然吻合網路協定的工作機制，比分散式共享記憶體（Distributed Shared Memory）簡單得多。
• 應用範疇（Scope）：訊息傳遞是作業系統中標準且極為廣泛使用的 IPC 原語（如 Microkernel、Pipes、Sockets、MPI 等），非僅限於小型系統，亦非單純的網路協定。

選項分析

• (a) 正確：
  在跨電腦通訊（Intercomputer communication，即分散式系統）中，訊息傳遞模型直接透過網路封包（如 Socket）發送與接收，實作結構簡單且直觀；

核心觀念

本題測驗作業系統架構設計中的**階層式架構（Layered Approach）**之設計難題與特性。
在經典作業系統恐龍書（Silberschatz 等著之 Operating System Concepts）中，階層式架構將作業系統劃分為若干層（$Layer\ 0$ 至 $Layer\ N$）：

• 最底層（$Layer\ 0$）為硬體（Hardware）。
• 最高層（$Layer\ N$）為使用者介面（User Interface）。
• 每一層僅能使用其底層（Lower-level layers）所提供的功能與服務，並對上層隱藏其內部資料結構與實作細節。

階層式架構最大的設計挑戰在於如何適當地定義各個階層的職責與相依順序（Appropriately defining the various layers），因為各子系統間常有循環依賴或複雜的呼叫關係（例如：虛擬記憶體管理與磁碟驅動程式之間的依賴關係），極難做到嚴格的單向依賴劃分。

解題方法

直接對照經典教科書對階層式架構優缺點之標準定義：

1. 主要優點（Advantages）：
   • 模組化與資訊隱藏（Modularity and Information Hiding）：每一層隱藏硬體與資料結構。
   • 簡化建構與除錯（Simplicity of Construction and Debugging）：由下而上依序測試與除錯，除錯時若出現錯誤，必為當前該層所致。
2. 主要困難與缺點（Difficulties / Disadvantages）：
   • 適當劃分各階層的順序與邊界極為困難（Appropriately defining the various layers）：各元件功能互有依賴，要決定誰在誰之上極度棘手。
   • 執行效能較差（Efficiency overhead）：跨層呼叫需經過層層封裝與參數傳遞，系統負擔大。

因此，題目所問的「主要困難（major difficulty）」即為適當定義各個階層。

選項分析

核心觀念

本題測驗作業系統中的**系統啟動流程（System Boot Process）與開機區塊（Boot Block / Boot Sector）**的角色與限制。

1. Bootstrap Loader 的兩階段啟動（Two-step Process）：
   • 完整載入作業系統核心（OS Kernel）需要具備讀取檔案系統（File System）、解析路徑等複雜功能。
   • 電腦剛開機時，硬體重設指標指向唯讀記憶體（ROM / Flash memory）中的極簡啟動程式（如 BIOS 或 UEFI 韌體初始常式）。
   • 由於硬體限制與成本考量，ROM 通常只具備最基礎的載入功能，且硬碟上的開機磁區（如 MBR 或 VBR）大小非常有限（經典結構僅 512 位元組，扣除分區表與魔術數字後，程式碼僅有 446 位元組左右）。
2. Boot Block 的主要職責：
   • 在傳統磁碟結構中，位於固定位置（通常是磁區 0）的 Boot Block 容量極小，**不足以（not sophisticated enough）**包含完整的檔案系統驅動程式與作業系統載入器。
   • 因此，Boot Block 通常只包含一個非常精簡的第二階段載入器片段，其功能通常僅限於知道磁碟上後續更完整的引導程式（The rest of the bootstrap program / Second-stage bootloader，如 GRUB、NTLDR/BOOTMGR）所在的實體區塊位置與長度，並將其讀入記憶體執行。

解題方法

依據作業系統經典教科書（如 Operating System Concepts by Silberschatz et al.，俗稱「恐龍書」）中〈Mass-Storage Structure〉章節對「Boot Block」的標準定義進行比對：

"A tiny bootstrap loader program in boot-ROM has only one duty: to bring into memory a full bootstrap program that is stored on the disk... The full bootstrap program is stored on a partition called the boot blocks... Typically, the program in the boot block only knows the location and length of the rest of the bootstrap program, which is sophisticated enough to load the entire operating system."

由此可知，Boot Block 本身結構極小且功能單一，僅負責銜接並載入後續完整的引導載入程式。

選項分析

核心觀念

本題出自作業系統聖經本（Silberschatz 等著之 Operating System Concepts，俗稱「恐龍本」）第二章「作業系統結構」（Operating System Structures）中的可載入核心模組（Loadable Kernel Modules, LKMs）。

作業系統核心的架構設計主要有單核心（Monolithic Kernel）、微核心（Microkernel）、分層架構（Layered Approach）以及模組化架構（Modular Approach）。當代多數主流作業系統（如 Linux、macOS、Solaris）採用模組化單核心架構：

• 核心僅保留最基本、核心的服務。
• 其他功能與服務（如硬體驅動程式、特殊檔案系統、網路協定）則以「模組（Modules）」的形式存在。
• 動態載入（Dynamically Loaded）：核心能夠在系統執行時期（Runtime/Boot time），依需求動態將模組載入到核心空間執行，或在不使用時卸載，完全不需重新編譯（Recompile）或重新開機（Reboot）整個核心。

解題方法

題幹描述：「____ allow operating system services to be loaded dynamically.」（____ 允許作業系統服務被動態載入）。

從作業系統核心擴充機制切入：

1. 分析題幹關鍵字 "loaded dynamically"（動態載入）與 "operating system services"（作業系統服務）。
2. 在核心結構中，專門用於在執行時動態載入與卸載作業系統服務的技術即為 Loadable Kernel Modules（模組）。因此直接對應選項 (b) Modules。

選項分析

• (a) Virtual machines（虛擬機器）：錯誤。
  虛擬機器是藉由虛擬化技術（如 Hypervisor/VMM）在單一實體硬體上模擬出多套獨立的虛擬硬體環境，讓多個客體作業系統（Guest OS）能同時並行運作，其主要目的為環境隔離與資源抽象化，並非用來讓作業系統核心服務動態載入的機制。

核心觀念

本題測驗作業系統中**死結（Deadlock）**的圖形化描述工具——**資源分配圖（Resource-Allocation Graph, RAG）**與死結存在性之間的邏輯關係（充要條件 vs. 必要條件）。

在作業系統（Silberschatz 等著《Operating System Concepts》）的標準定義中：

1. 單一實例（Single instance of each resource type）：
   • 若系統中每一種資源類型皆恰好只有一個實例（Each resource type has exactly one instance），則資源分配圖中存在環（Cycle）是系統發生死結的充分且必要條件（Necessary and Sufficient Condition）。
   • 存在環 $\iff$ 系統發生死結。
2. 多個實例（Multiple instances per resource type）：
   • 若系統中資源類型包含多個實例（Multiple instances），則存在環只是死結的必要條件（Necessary condition），而非充分條件（Not a sufficient condition）。
   • 換言之：死結必定包含環，但圖中有環不一定保證死結（因為環外的 Process 可能釋放資源，使環內的 Process 得以推進）。

解題方法

由死結理論的判定定理切入：

• 題目討論的是「資源分配圖中的環（A cycle in a resource-allocation graph）」在不同資源實例數量下的等價性與蘊含性。
• 當每個資源類型僅有 1 個實例時，等待與持有的依賴關係是確定且封閉的，因此檢測出環就代表必定死結，無環則必定無死結。這構成了充分且必要條件。
• 比對選項中資源實例數量與邏輯條件的對應關係，即可直接選出正確敘述。

選項分析

核心觀念

本題考查作業系統中**記憶體管理（Memory Management）**的經典基礎觀念：指令與資料繫結至記憶體位址的時機（Address Binding of Instructions and Data to Memory Addresses）。

根據作業系統教科書（如 Silberschatz 的 Operating System Concepts），位址繫結依發生的時機可分為三個階段：

1. 編譯時期繫結（Compile-Time Binding）：若在編譯時就已預先知道行程將常駐於記憶體的哪個起始位置，編譯器便能直接產生絕對碼（Absolute Code），即程式中的記憶體參照皆直接對應到實體位址。若日後起始位址改變，程式碼必須重新編譯（Recompile）。
2. 載入時期繫結（Load-Time Binding）：若在編譯時期不知道行程將被載入何處，編譯器必須產生可重定位碼（Relocatable Code）。實際的位址繫結延遲至載入器（Loader）將程式載入記憶體時才決定。若起始位址改變，只需重新載入（Reload）程式碼即可。
3. 執行時期繫結（Execution-Time / Run-Time Binding）：若行程在執行期間可能在不同的記憶體區段間搬移（如搭配分頁、分段或動態交換機制），繫結時機將延遲至執行該指令存取記憶體當下才動態決定。此時需要硬體支援（如 MMU 與重定位暫存器 Relocation Register）。

解題方法

題幹明確詢問：「Absolute code（絕對碼）是在哪一個 binding 階段產生的？」

從編譯器與載入器的運作機制切入：

• 絕對碼（Absolute Code）的特徵在於程式內部的跳躍與資料位址都是寫死的（Hard-coded），這意味著在將原始碼轉譯成機器碼的「編譯時期（Compile time）」就已經決定了實體記憶體配置。
• 只有當 address binding 發生在 Compile time 時，產生的程式碼才會是 Absolute code。

選項分析

• (a) compile-time binding：正確。
  在編譯時期已知程式將載入之記憶體實體位址（例如早期的 MS-DOS .COM 檔固定從位址 `0x010

核心觀念

本題出自作業系統經典教科書（如 Silberschatz 的 Operating System Concepts，俗稱「恐龍書」）中關於**記憶體管理（Memory Management）與程式連結／載入（Linking & Loading）的章節，主要考察動態連結程式庫（Dynamically Linked Libraries, DLLs）與靜態連結（Static Linking）**的機制差異。

關鍵定義如下：

1. 動態連結（Dynamic Linking）：將程式庫（Libraries）的連結延後至執行時期（Execution time）。執行檔中並不包含完整的函式庫二進位程式碼，而是包含一段稱為 stub（存根程式）的小段程式碼。
2. Stub 的運作：
   • 當呼叫到該程式庫函式時，stub 會先檢查該常式（routine）是否已存在於記憶體中。
   • 若不在，則由作業系統將該函式庫常式載入記憶體。
   • 隨後 stub 將自己替換為該常式的實際進入點記憶體位址，並執行該常式。
3. 靜態連結（Static Linking）：在編譯／連結時期，系統語言程式庫（system language libraries）與其他 object module 一樣，直接將完整的函式庫程式碼複製合併進最終的可執行檔（executable binary image）。

解題方法

比對恐龍書原文書對動態連結的標準敘述：

"With dynamic linking, a stub is included in the image for each library-routine reference. The stub is a small piece of code that indicates how to locate the appropriate memory-resident library routine or how to load the library if the routine is not already present."

依據上述機制與定義，逐一比對題目中的四個選項：

• 檢查各選項所描述的行為屬於靜態連結、動態載入（Dynamic Loading），還是動態連結（Dynamic Linking）。

選項分析

核心觀念

本題測驗 UNIX 系統中行程建立機制：fork() 與 vfork() 系統呼叫（system call）的差異與設計目的。

1. fork() 的傳統代價：傳統 fork() 會完整複製父行程的位址空間（Address Space），開銷極大。現代作業系統雖引入寫入時複製（Copy-on-Write, COW）技術來延遲並減少頁面複製，但在 COW 普及之前，行程建立後若立即呼叫 exec() 載入新程式，複製頁面的動作依然造成不必要的資源浪費。
2. vfork() 的設計機制：
   • vfork() 是早期 BSD UNIX 為了解決「建立子行程後立刻執行 exec()」效能低下而設計的系統呼叫。
   • 子行程不複製父行程的位址空間，而是直接共享（使用）父行程的位址空間與記憶體頁面。
   • 呼叫 vfork() 後，父行程會被暫停（suspend），直到子行程呼叫 exec() 載入新程式，或呼叫 _exit() 結束為止。
   • 子行程若修改任何資料或堆疊，會直接影響父行程。

解題方法

由題幹關鍵字 vfork() 切入，直接檢視其核心定義與運作行為：

1. 空間共享性：vfork() 讓子行程直接共用父行程的位址空間（address space），不配置新的虛擬記憶體結構。
2. 使用情境：vfork() 的唯一主要設計目的就是為了配合子行程立即呼叫 exec()。
3. COW 關聯性：寫入時複製（Copy-on-Write）是現代 fork() 的最佳化機制，而非 vfork() 的機制。vfork() 連頁面複製（含 COW）都不做。

據此比對各選項敘述的正確性。

選項分析

• (a) allows the child process to use the address space of the parent（正確）：
  vfork() 建立子行程時不會複製虛擬記憶體頁面，子行程直接共用（使用）父行程的位址空間，且父行程暫停執行，直到子行程執行 exec() 或 _exit()。此敘述完全符合 vfork() 的核心運作機制。

核心觀念

本題考查作業系統虛擬記憶體（Virtual Memory）管理中的經典現象——貝拉迪異常（Bélady's Anomaly）。

1. 直覺預期：在虛擬記憶體系統中，直觀上若替一個行程（process）分配更多的實體頁框（allocated frames），該行程所發生的分頁錯誤次數（page faults）或分頁錯誤率（page-fault rate）理應減少或至少持平。
2. 貝拉迪異常的定義：對於某些分頁置換演算法（最典型的為先進先出 FIFO 演算法），當配置給行程的頁框數量增加時，分頁錯誤的次數（或分頁錯誤率）反而**不減反增（increase）**的反直覺異常現象。
3. 堆疊演算法（Stack Algorithms）：能保證不會發生貝拉迪異常的演算法稱為堆疊演算法（例如 LRU、Optimal），其特性是：在 $n$ 個頁框配置下存在記憶體中的分頁集合，永遠是 $n+1$ 個頁框配置下分頁集合的子集（即 $S_n \subseteq S_{n+1}$）。未滿足此特性的演算法（如 FIFO、Second-chance）則可能引發貝拉迪異常。

解題方法

從題幹關鍵字「Belady's anomaly states that ____」切入：

• 關鍵在於**「異常（anomaly）」**意味著違反一般認知（配置更多頁框應該降低 page-fault rate）。
• 異常的具體表現為：增加頁框數量（allocated frames increases），分頁錯誤率反而增加（page-fault rate may increase）。
• 且此現象僅適用於部分演算法（for some page replacement algorithms），並非所有演算法都會發生。

選項分析

核心觀念

本題測驗作業系統與計算機組織中「儲存裝置階層（Storage Hierarchy）」與「記憶體特性（Memory Characteristics）」的基本定義：

1. 揮發性儲存（Volatile Storage）：斷電後儲存之資料即會遺失的儲存媒介，例如暫存器（Registers）、快取記憶體（Cache）、主記憶體（RAM，包含 SRAM 與 DRAM）。
2. 非揮發性儲存（Nonvolatile Storage）：斷電後仍能長久保留資料的儲存媒介，例如固態硬碟（Solid-State Disks, SSDs）、傳統機械式硬碟（Hard-Disk Drives, HDDs）、光碟（Optical Disks）與磁帶（Magnetic Tapes）。
3. 固態硬碟（SSD）：主要由快閃記憶體（NAND Flash Memory）構成，作為二級儲存設備（Secondary Storage），本質上屬於非揮發性儲存。

解題方法

從電腦儲存體系之功能與物理本質切入判斷：

1. 檢視題目主體：固態硬碟（SSD）是用來安裝作業系統、儲存使用者檔案與應用程式的二級儲存設備。若其具有揮發性，則電腦每次關機或重新啟動後，所有資料將全部消失，這顯然違反二級儲存設備的功能需求。

核心觀念

本題測驗作業系統（UNIX / Linux 體系）中的行程憑證與權限管理機制（Process Credentials & Privilege Management），重點在於區分下列幾種 User ID（UID）：

1. Real UID（RUID，真實使用者 ID）：識別建立或啟動該行程的實際使用者（帳號擁有者）。
2. Effective UID（EUID，有效使用者 ID）：核心（Kernel）用來進行存取控制與權限檢查（Access Control Check）的依據。行程當前能讀寫哪些檔案、執行哪些系統資源，皆由此值決定。
3. Saved Set-User-ID（SUID / SSUID，保存的使用者 ID）：在執行具有 Set-UID 位元的二進位檔時，核心會將執行當下的 EUID 備份於此。
4. 權限動態調整（Privilege Dropping & Escalation）：行程在執行生命週期中，可藉由系統呼叫（如 seteuid()、setuid()、setresuid()）動態改變其 Effective UID。

解題方法

分析題幹敘述：「The process runs with effective UID all the time until the process is stopped.」

• 切入點 1：語意檢驗
  • 行程在執行期間，核心隨時隨地都維護著一個 Effective UID（用以做權限比對），但該 Effective UID 的值並非固定不變（not static）。
  • 更重要的是，題幹意指「行程一旦啟動，其 EUID 就必須一路維持到行程終止為止」，這違背了安全程式設計中的最小權限原則（Principle of Least Privilege）。
• 切入點 2：系統機制與特權降級（Privilege Dropping）

核心觀念

本題測驗作業系統架構中的「混合核心（Hybrid System / Hybrid Kernel）」架構，特別是 Apple macOS（舊稱 Mac OS X）的核心設計。

作業系統核心架構主要分為四類：

1. 單核心架構（Monolithic Kernel）：所有作業系統核心服務（行程管理、記憶體管理、檔案系統、裝置驅動等）皆執行於同一個核心位址空間（Kernel Space），效率高但容錯性與擴充性較差（如傳統 UNIX、Linux）。
2. 微核心架構（Microkernel）：核心只保留最基本的功能（如行程間通訊 IPC、基本的虛擬記憶體管理與排程），其餘服務（檔案系統、驅動程式等）移至使用者空間（User Space）以伺服器（Server）行程運作，穩定性與模組化佳但 IPC 負擔造成效能較低（如 Mach、QNX）。
3. 分層與模組化架構（Layered / Modular Kernel）：以模組（Kernel Modules）動態載入擴展功能。
4. 混合核心架構（Hybrid Kernel）：結合單核心的高效能與微核心的模組化結構。Mac OS X 採用的核心稱為 XNU（X is Not Unix），其架構本質上就是結合了 Mach 微核心 與 BSD UNIX，兩者整合在同一個核心位址空間內運作。

解題方法

從作業系統經典教科書（Silberschatz 作業系統恐龍本《Operating System Concepts》）對 Mac OS X 架構的定義進行檢驗：

1. Mac OS X 的架構組成：
   • 使用者介面層：Aqua、Cocoa、Carbon。
   • 核心環境（Darwin / XNU）：XNU 核心主要由兩大核心組件構成：
     • Mach 微核心：負責處理執行緒管理（Threads）、CPU 排程（Scheduling）、行程間通訊（Mach IPC）、記憶體管理（VM）。
     • BSD UNIX：提供 POSIX API、BSD 行程模型（Process model）、訊號處理（Signals）、BSD 網路協定堆疊（Networking / Sockets）及 VFS 檔案系統。

核心觀念

本題考查作業系統中**檔案系統介面（File-System Interface）與I/O 裝置管理（Device Management）**的統一抽象化設計。

在現代作業系統（尤其是 UNIX / Linux 體系，即「Everything is a file」哲學）中，作業系統常將硬體 I/O 裝置（如終端機、磁碟、音訊設備等）映射為特殊檔案（Device Files，通常位於 /dev 目錄下）。這是因為對檔案的存取操作（開啟、讀取、寫入、關閉）與對 I/O 裝置的操作本質上具有高度相似性，因此作業系統將兩者整合成統一的檔案介面，以簡化系統架構並提高擴充性。

解題方法

從作業系統教科書（如 Silberschatz《Operating System Concepts》，俗稱恐龍本）的系統架構與系統呼叫（System Calls）設計切入分析：

1. 系統呼叫的共通性：
   對一般常規檔案（Regular File）的基本系統呼叫包括 open()、read()、write()、close() 以及 ioctl()。而多數 I/O 裝置（如序列埠、終端機）的資料流傳輸行為，與讀寫循序檔案完全一致。
2. 統一介面的好處（Uniform Interface）：
   若將檔案與裝置分立，應用程式在存取裝置時必須使用另一套專屬的系統呼叫（如專門的裝置讀寫指令），這會增加使用者程式與編譯器的複雜度。作業系統透過統一檔案抽象（VFS / Device File），讓程式設計師可用同一套系統呼叫與介面同時操作檔案與周邊設備。
3. 題意檢驗：

核心觀念

本題測驗作業系統中**行程間通訊（Interprocess Communication, IPC）的管線（Pipes）機制，特別是匿名管線（Ordinary / Anonymous Pipes）與具名管線（Named Pipes，在 UNIX 系統中稱為 FIFO）**的特性差異。

• 普通／匿名管線（Ordinary / Anonymous Pipes）：
  • 通訊雙方必須具有親屬關係（Relationship），通常是父子行程（Parent-Child Relationship）或兄弟行程（Sibling Processes）。因為匿名管線沒有檔案系統路徑名稱，子行程必須透過 fork() 繼承父行程開啟的檔案描述子（File Descriptors）。
  • 生命週期隨建立它的行程結束而消失。
• 具名管線（Named Pipes / FIFOs）：
  • 在檔案系統中擁有明確的實體檔名（Node/Pathname）。
  • 任何行程只要具備適當的存取權限，皆可藉由管線名稱開啟並進行通訊，不需要具備父子行程或任何親屬關係（No parent-child relationship is required），亦可用於不相關的行程（Unrelated Processes）之間。
  • 生命週期獨立於行程，除非主動刪除，否則管線檔案會持續存在於檔案系統中。

解題方法

1. 鎖定題目關鍵字：題目探討的主體是 Named pipes（具名管線），條件為 requires parent-child relationship（需要父子關係）。
2. 對照標準定義：
   • 根據恐龍本（Silberschatz et al., Operating System Concepts）第 3 章規範：

核心觀念

本題測驗作業系統中**行程間通訊（Inter-process Communication, IPC）**的兩種基本模型：**訊息傳遞（Message Passing）與共用記憶體（Shared Memory）**的運作機制與系統呼叫（System Call）之差異。

1. 建立階段（Setup Phase）：

   • 行程使用 shm_open() 建立或開啟 POSIX 共用記憶體物件，透過 ftruncate() 設定大小，並使用 mmap() 將該共用記憶體區塊映射（map）至行程本身的虛擬位址空間（Virtual Address Space）。
   • 這些步驟牽涉到作業系統核心的記憶體管理與虛擬記憶體分頁表配置，因此必須透過系統呼叫完成。

2. 存取階段（Access / Read / Write Phase）：

   • 一旦共用記憶體完成映射，它就成為該行程位址空間的一部分。
   • 後續行程對該區塊的所有資料存取（讀取、寫入、修改），本質上就是一般的記憶體存取指令（如組合語言中的 MOV、LOAD、STORE 等），直接透過指標（Pointer）操作記憶體，完全不需要陷入核心（Trap to Kernel），即不需要執行任何系統呼叫。

解題方法

從作業系統「使用者模式（User Mode）與核心模式（Kernel Mode）的切換成本」切入分析：

• 訊息傳遞（如管道 Pipe、訊息佇列 Message Queue）：每次傳送（write / send）與接收（read / receive）資料，都必須呼叫系統呼叫介入並切換至核心模式，涉及資料在「使用者空間」與「核心空間」之間的複製。
• 共用記憶體（Shared Memory）：
  • 設計的最大優勢在於存取速度快。

核心觀念

本題測驗 Linux 作業系統的開機程序（Boot Process）與行程階層架構（Process Hierarchy / Process Tree）：

1. PID 0（swapper / idle process）：核心空間（Kernel Space）最早建立的行程，為靜態配置，負責系統初始化與 CPU 閒置時的排程，不屬於一般使用者空間行程。
2. PID 1（init 或其現代替代者如 systemd）：當 Linux 核心載入並完成硬體初始化後，由核心透過 kernel_thread() 或 kernel_init() 啟動的第一個使用者空間（User Space）行程。所有其他使用者空間行程皆為其直接或間接衍生的子行程，形成一棵以 init（PID 1）為根節點的行程樹（Process Tree）。

在作業系統標準教科書（如 Silberschatz 的《Operating System Concepts》）的定義中，init 是典型 UNIX/Linux 系統中行程樹的祖先（Ancestor of all processes），也是系統載入後第一個建立的使用者行程（The very first user process / The first process created during boot）。

解題方法

從 Linux 核心啟動流程切入判斷：

1. 當電腦開機完成 POST、Bootloader（如 GRUB）載入 Linux 核心（vmlinuz）並將控制權交給核心後，核心會初始化記憶體管理、驅動程式等子系統。
2. 核心完成內部初始化後，會執行位於 /sbin/init（或現代 Linux 中的 /lib/systemd/systemd，但向後相容符號連結至 /sbin/init）的程式。
3. 此時產生的行程被賦予 PID = 1，名為 init。它是典型 Linux 系統中所有行程的母行程（Parent of all user processes）。
4. 在作業系統經典考試標準語意下，「init 是典型 Linux 系統中的第一個行程」敘述完全符合教材標準陳述。

核心觀念

本題測驗作業系統中的**多執行緒模型（Multithreading Models）**之特性與比較，主要涵蓋以下觀念：

1. 多對一模型（Many-to-One Model）：將多個使用者層級執行緒（User Threads）映射到單一個核心層級執行緒（Kernel Thread）。由於作業系統核心僅看見單一執行緒，一旦其中任一個使用者執行緒執行了阻斷式系統呼叫（Blocking System Call），整個行程（Process）皆會被阻斷（Block）；此外，因為只有一個核心執行緒，多個執行緒無法在多處理器（Multiprocessor）系統上同時平行執行。
2. 一對一模型（One-to-One Model）：將每一個使用者層級執行緒映射到一個獨立的核心層級執行緒。核心完全知曉每個執行緒的存在，當某個執行緒因阻斷式系統呼叫而暫停時，核心可立即排班同一個行程中的其他執行緒繼續執行，因此提供更高的並行度（Concurrency）。

解題方法

從執行緒模型對**「阻斷式系統呼叫（Blocking System Call）」**的處理機制切入分析：

• 題目敘述：「One-to-one model provides more concurrency than the many-to-one model by allowing another thread to run when a thread makes a blocking system call.」
• 對照經典教材（Silberschatz 作業系統恐龍書）定義：
  • 在 Many-to-One 模型中，執行緒管理完全由使用者空間的 Thread Library 處理。當某個執行緒呼叫 Blocking System Call（例如讀取檔案或網路 I/O），核心阻斷該核心執行緒，導致整個 Process 停擺，造成並行度低。
  • 在 One-to-One 模型中，每個使用者執行緒皆對應一個核心執行緒。

核心觀念

本題測驗作業系統中「多執行緒程式設計」（Multithreaded Programming）的演進趨勢，特別是**顯式執行緒（Explicit Threading）與隱式執行緒（Implicit Threading）**的差異：

1. 顯式執行緒（Explicit Threading）：由程式設計師直接在程式碼中明確呼叫 API 負責執行緒的建立（Creation）與管理（Management）。常見技術如 POSIX Pthreads、Windows Threads、Java Thread 類別等。
2. 隱式執行緒（Implicit Threading）：將執行緒的建立與管理責任，由應用程式設計師轉移給編譯器（Compiler）與執行時期函式庫（Run-time Libraries）。程式設計師僅需識別並定義平行任務（Tasks），底層系統會自動進行執行緒分配與排程。
3. 發展背景：隨著多核心處理器（Multicore Processors）普及，系統常需並行處理成百上千個執行緒。程式設計師若手動管理大量執行緒，容易陷入競爭條件（Race Conditions）、死鎖（Deadlocks）及快取效能低落等瓶頸，因此由系統架構自動管理的隱式執行緒成為主流。

解題方法

本題出自經典作業系統教科書（Silberschatz, Galvin, and Gagne 所著之 Operating System Concepts，俗稱「恐龍書」）第四章 Threads & Concurrency 的原文書核心敘述。解題切入點如下：

• 開發複雜度分析：傳統顯式執行緒要求開發者手動維護執行緒生命週期與負載平衡，在大型平行應用中維護成本極高且不具良好的硬體擴展彈性。
• 現代解決方案：隱式執行緒技術（如 Thread Pools、OpenMP、Grand Central Dispatch、Fork-Join 框架、Intel TBB 等）能讓開發者專注於任務的演算法邏輯，將底層執行細節交由最佳化的執行時期環境排程，能更有效率地利用多核心資源。
• 根據教科書定義，隱式執行緒正是當前平行應用程式開發日益顯著且被廣泛採納的趨勢（an increasingly popular trend）。

核心觀念

本題測驗作業系統中「隱式執行緒（Implicit Threading）」架構下 Grand Central Dispatch (GCD) 的運作原理與分派佇列（Dispatch Queues）的本質。

• Grand Central Dispatch (GCD)：由 Apple 開發並整合於 macOS 與 iOS 核心的技術，旨在簡化多核心系統上的平行程式設計。程式設計師只需將工作切割成區塊（Blocks 或 Closures），並將其置入**分派佇列（Dispatch Queue）**中，由作業系統底層的執行緒池（Thread Pool）負責排程與執行。
• 分派佇列的分類：
  1. 序列佇列（Serial Queue）：依先進先出（FIFO）順序執行工作。在任一時間點，同一序列佇列只會執行一個工作。因此，序列佇列可以在**單一執行緒（Single Thread）**上依序執行所有工作，完全不需要多執行緒（Multiple Threads）。例如每個行程預設具備的「主佇列（Main Queue）」即為序列佇列，且僅運行於單一主執行緒上。
  2. 並行佇列（Concurrent Queue）：同樣以 FIFO 順序取出工作，但可同時執行多個工作，底層由 GCD 視系統負載動態指派多個執行緒執行。

解題方法

切入點在於檢視題目敘述中的絕對限制詞 "requires"（需要／必須）：

• 題目敘述為「Grand Central Dispatch requires multiple threads」（GCD 必須具備多執行緒）。
• 檢驗反例：若存在 GCD 僅使用單一執行緒即可正確運作的情境，則該全稱命題即為錯誤（False）。

核心觀念

本題考的是銀行家演算法的安全性檢查。先計算每個行程尚需的資源：

若存在一個行程，其 Need 不超過目前的 Work，就能假設該行程完成，並把它已占用的資源歸還：

若所有行程都能依序完成，系統便存在安全序列；若檢查途中無行程可執行，則不存在安全序列。

解題方法

逐列計算 Need：

核心觀念

本題評量作業系統在**需求分頁（Demand Paging）機制下的指令重新執行（Instruction Restart）**與分頁錯誤（Page Fault）處理流程。

1. 指令重新執行（Instruction Restart）機制：
   • 當 CPU 執行指令過程中存取記憶體，若該分頁不在實體記憶體（DRAM）中，硬體會觸發 Page Fault 陷阱（Trap）。
   • 作業系統的 Page Fault Handler 會將缺失的分頁從次級儲存體（如 SSD/HDD）載入 DRAM，更新 Page Table 中的 Valid-Invalid bit。
   • 處理完成後，必須將程式計數器（PC）重設回該指令的位址，並復原暫存器狀態，將整道指令重新執行（Restart）一次。
2. 指令記憶體存取階段：
   三位址指令（Three-address instruction）Add A, B, C（語意為 $C = A + B$）的執行步驟如下：
   • Fetch Instruction：擷取並解碼指令。
   • Operand Fetch (Read)：依序讀取運算元 $A$ 與運算元 $B$。
   • Execution：計算 $A + B$。
   • Operand Store (Write)：將運算結果寫入運算元 $C$ 的位址。
3. 分頁分佈狀況：
   題目已明定「包含該指令的分頁已經在 DRAM 中（Suppose the page which contains the instruction is already in the DRAM）」，因此擷取指令（Instruction Fetch）階段保證不會發生 Page Fault。

解題方法

計算「最大指令重新執行次數（Maximum number of instruction restarts）」，等價於計算「執行此指令最多可能引發幾次 Page Fault」。每次發生 Page Fault 都會中斷指令並在處理後重新啟動該指令。

需針對運算元是否跨越分頁邊界（Page Boundary）進行完整分類分析：

情況一：運算元未跨越分頁邊界（標準假設 / 每個運算元各佔 1 個 Page）

若每個運算元（$A, B, C$）的資料長度均未跨越分頁邊界，且各自位於相異的虛擬分頁中：

• 第一次執行嘗試：
  1. Fetch Instruction：命中（已在 DRAM）。
  2. 存取運算元 $A$：發生第 1 次 Page Fault。
  3. OS 載入 $A$ 所在的分頁，更新頁表，第 1 次 Restart 指令。
• 第二次執行嘗試：
  1. Fetch Instruction：命中。
  2. 存取運算元 $A$：命中（已載入）。
  3. 存取運算元 $B$：發生第 2 次 Page Fault。

核心觀念

本題的核心觀念為作業系統中需求分頁（Demand Paging）架構下，指令執行所需的最少訊框數（Minimum Number of Frames），並結合計算機組織中的間接定址（Indirect Addressing）與三運算元指令格式（Three-address Instruction）。

1. 需求分頁的最少訊框數原則：

   • 當單一指令在執行過程中發生分頁錯誤（Page Fault）時，CPU 必須將該分頁載入記憶體並重新啟動指令（Restart Instruction）。
   • 為了保證指令在重新啟動後能夠順利執行完畢而不陷入無窮的分頁錯誤迴圈，系統分配給該行程的實體訊框數（Frames），至少必須足以同時容納單一指令在最糟情況下同時間所需參照的所有分頁。

2. 指令跨頁與間接定址的記憶體存取：

   • 指令擷取（Instruction Fetch）：若指令本身跨越了兩個分頁的邊界（Boundary Crossing），需要 $2$ 個分頁。
   • 間接定址（Indirect Addressing）：語法 (X) 代表間接定址，即記憶體位址 $X$ 存放的不是資料本身，而是資料的有效位址（Effective Address, $EA$），實際運算元儲存在位址 $EA$ 處。因此，存取一個間接定址運算元需要兩次記憶體存取：
     1. 讀取指標位址（Pointer Address）。
     2. 讀取／寫入目標資料（Target Data）。
   • 若運算元或指標跨越分頁邊界，每次記憶體存取在最糟情況下皆可能跨越 $2$ 個分頁。

解題方法

本題指令為 ADD (A), (B), (C)，語意通常為將位址 (B) 與 (C) 的內容相加後存入位址 (A)，共包含 1 個指令自身與 3 個間接定址運算元。在計算「最少訊框數（Minimum Frames）」時，依據考試標準分類與假設情境進行分析：

情況一：標準假設（假設指令與運算元皆不跨越分頁邊界，為多數教科書基本情境）

1. 指令自身擷取（Instruction Fetch）：
   • 需要 $1$ 個訊框容納該指令。
2. 三個間接定址運算元（Operands）：

核心觀念

本題的核心觀念為作業系統虛擬記憶體（Virtual Memory）中的分頁大小（Page Size）權衡取捨（Trade-offs）。

在需求分頁（Demand Paging）與虛擬記憶體架構中，分頁大小 $S$ 直接影響以下系統指標：

1. 分頁表大小（Page Table Size）：若虛擬位址空間大小為 $V$，分頁大小為 $S$，則分頁表項目（PTE）數量為 $N = \frac{V}{S}$。當 $S$ 增大，$N$ 呈反比減少，節省分頁表所佔用的實體記憶體空間。
2. TLB 覆蓋率（TLB Reach）：$\text{TLB Reach} = (\text{TLB Entries}) \times S$。在 TLB 項目數固定下，增大 $S$ 可大幅提升 TLB 能夠涵蓋的記憶體範圍，降低 TLB Miss 率。
3. 次級儲存裝置（磁碟）傳輸效率：磁碟 I/O 的延遲主要是尋軌時間（Seek Time）與旋轉延遲（Rotational Latency），傳輸時間（Transfer Time）相對極小。較大的分頁可藉由一次 I/O 傳輸更多資料，摊平磁碟存取開銷，提升有效傳輸率。
4. 內部碎裂（Internal Fragmentation）：平均每個行程的最後一個分頁會浪費 $\frac{S}{2}$ 的空間。當 $S$ 增大，內部碎裂程度加劇。
5. 程式局部性與記憶體利用率（Locality of Reference）：若程式缺乏良好的空間局部性，載入過大的分頁會將大量不常使用的資料帶入記憶體，導致 page-in 許多無用資料，增加分頁置換（Page Fault/I/O）負擔。

解題方法

題目要求列出三項優點（Advantages）與兩項缺點（Disadvantages），並附上簡要說明。解題切入點應分別針對「硬體與記憶體管理效率（TLB、分頁表）」、「儲存裝置 I/O 特性」，以及「空間浪費與局部性匹配」進行系統性論述。

試題詳解

一、採用較大分頁大小的三項優點（Advantages）

1. 減少分頁表大小（Smaller Page Table Size）

   • 說明：分頁表項目（PTE）的數量與分頁大小成反比（$N = \frac{V}{S}$）。使用較大的分頁大小能顯著減少虛擬位址空間所需對應的分頁表筆數，進而降低儲存分頁表所需的實體記憶體開銷（Memory Overhead）。

2. 提高 TLB 覆蓋率並降低 TLB Miss 率（Increased TLB Reach / Better TLB Performance）

   • 說明：$\text{TLB Reach} = \text{TLB Entries} \times \text{Page Size}$。在硬體 TLB 項目容量有限的情況下，增大分頁大小可大幅提升單一 TLB 項目所能對應的位址範圍（例如使用 Huge Pages），顯著減少 TLB Miss 次數，加速位址轉譯速度。

3. 提升磁碟 I/O 傳輸效率（More Efficient Disk I/O Transfer）

核心觀念

1. 記憶體高牆（Memory Wall）：
   • 指處理器（CPU）的運算速度與主記憶體（Main Memory）的存取延遲（Latency）與頻寬之間的效能差距隨時間呈現指數級擴大。
   • 為了解決此瓶頸，計算機架構利用記憶體階層（Memory Hierarchy）與存取區域性（Locality of Reference），在 CPU 與主記憶體之間加入容量小但速度極快的快取記憶體（Cache Memory）。
2. 半導體記憶體技術特性比較：
   • SRAM（Static RAM，靜態隨機存取記憶體）：
     • 結構：每個 cell 通常由 6 個電晶體（6T）組成雙穩態正反器（Bistable Latch）。
     • 特性：速度極快（存取時間約數個 CPU cycles 或小於 1 ns）、不需週期性更新（Refresh）、電路面積大且單位成本高。
     • 主要應用：處理器晶片內部（On-chip）的各級快取記憶體（L1, L2, L3 Cache）。
   • DRAM（Dynamic RAM，動態隨機存取記憶體）：
     • 結構：每個 cell 由 1 個電晶體與 1 個電容（1T-1C）組成。
     • 特性：電容隨時間會漏電，必須週期性進行充電更新（Refresh）；密度高、單位成本低，但存取延遲遠高於 SRAM（通常在數十至百奈秒等級）。
     • 主要應用：系統的主記憶體（Main Memory）。

解題方法

本題為是非題，解題切入點在於檢視題目敘述中的每一項技術定義是否精確：

1. 快取記憶體（Cache Memory）是否用來緩解 Memory Wall？$\rightarrow$ 是，利用局部性原理減少存取主記憶體的平均時間（AMAT）。
2. 快取記憶體（Cache Memory）是否由 DRAM 技術製造？$\rightarrow$ 否。現代處理器內部的快取記憶體是採用 SRAM 技術製造，而非 DRAM。

選項分析

核心觀念

本題測驗計算機效能評估（Performance Measurement）的經典基本觀念：

1. 唯有執行時間（Execution Time）才是可靠的效能指標：評估不同處理器之間的效能表現，唯一客觀且不受指令集架構（ISA）差異影響的標準是「程式實際完成任務所需的真實時間」（Execution Time 或 CPU Time）。
2. CPU 基本效能方程式（Classic CPU Performance Equation）：
   $\text{CPU Execution Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time}$
   $\text{CPU Execution Time} = \frac{\text{Instruction Count} \times \text{CPI}}{\text{Clock Rate}}$
3. MIPS 與 CPU Clock Cycles 的局限性：
   • $\text{MIPS} = \frac{\text{Instruction Count}}{\text{Execution Time} \times 10^6} = \frac{\text{Clock Rate}}{\text{CPI} \times 10^6}$
   • MIPS（每秒執行百萬指令數）與 Clock Cycles（週期數）均忽略了指令集架構（ISA）、每指令所需週期數（CPI）以及時脈頻率（Clock Rate）的差異。跨不同處理器比較時，指令豐富度不同（例如 CISC vs. RISC），執行相同工作所需的指令數（IC）截然不同，因此高 MIPS 或較少 Clock Cycles 並不代表較快的執行時間。

解題方法

題幹陳述：「有很多指標，而且它們都很適合（are good for）用來衡量並比較不同處理器之間的效能（measuring and comparing the performance delivered by different processors），包括 execution time、CPU time、MIPS 以及 CPU clock cycles。」

解題切入點在於判斷題中所列的各項指標是否皆屬於「良好且適合跨處理器比較的效能度量（Good metrics for comparing different processors）」：

1. 檢驗 Execution Time 與 CPU Time：這兩者直接反映程式完成任務耗費的真實時間，屬於標準且可靠的效能指標。
2. 檢驗 MIPS 與 CPU Clock Cycles：

核心觀念

本題測驗計算機指令集架構（ISA）中的內部儲存結構分類——**通用暫存器架構（General-Purpose Register Architecture, GPR Architecture）**之定義與實例。

1. 內部暫存器架構分類：
   依據 CPU 內部運算元（operands）的存放方式，運算指令集結構主要可分為三大類：
   • 堆疊架構（Stack architecture）：運算元隱含於頂端堆疊（Stack）。
   • 累加器架構（Accumulator architecture）：運算元之一隱含在累加器（Accumulator）中。
   • 通用暫存器架構（General-Purpose Register architecture）：運算元明確指定為 GPRs 或記憶體位址。
2. GPR 架構定義與功能：
   • 通用暫存器（GPRs）可供指令自由運用，用來存放運算資料（Data）或記憶體位址（Addresses，如指標、基底位址、索引等）。
   • 目前主流的現代架構（無論是 CISC 還是 RISC）幾乎全數採用 GPR 架構。

解題方法

針對題目敘述進行拆解與驗證：

1. 定義驗證：檢查「A general-purpose register (GPR) architecture provides the GPRs for storing addresses or data for instructions」是否符合計算機結構標準定義。
   • GPR 既能容納整數等資料運算元，也能存放指標或作為定址（addressing modes）的基底暫存器（base/index registers），定義完全正確。
2. 實例驗證：檢查題目列舉之處理器是否皆為 GPR 架構：
   • Intel 8086：經典 CISC 處理器，擁有 8 個 16 位元暫存器（AX, BX, CX, DX, SI, DI, BP, SP），雖有特定隱含功能，但在架構分類上屬於典型的 Extended Accumulator / Register-Memory 形態之 GPR 架構。

核心觀念

本題評量計算機組織中浮點數運算（Floating-Point Arithmetic）與平行計算（Parallel Execution）的數值特性，核心概念源自 Patterson & Hennessy《Computer Organization and Design》第 3 章：

1. 結合律（Associativity）的差異：
   • 整數加法：在無溢位（Overflow）的情況下滿足結合律，即 $(A + B) + C = A + (B + C)$。
   • 浮點數加法：由於表示精度有限（Mantissa 截斷／捨入）以及對齊階數（Alignment of Exponents）的過程，浮點數加法不具備結合律（Floating-point addition is NOT associative），即： $$(A + B) + C \neq A + (B + C)$$
2. 平行化對運算順序的改變：
   • 循序執行（Sequential Execution）通常依陣列順序累加：$(((x_0 + x_1) + x_2) + x_3)$。
   • 平行執行（Parallel Execution，如樹狀歸約 Tree Reduction）會改變累加括號的結合方式：$((x_0 + x_1) + (x_2 + x_3))$。
   • 因為結合律不成立，這種運算順序的改變會直接導致浮點數產生不同的捨入誤差（Rounding Error），因此平行執行的數值結果往往與循序執行不同。

解題方法

1. 檢驗敘述前提：「適用於整數資料的平行執行策略也適用於浮點數資料」（Parallel execution strategies that work great for integer data also work for floating-point data）。
   • 樹狀加總（Tree Reduction）在整數上能保證結果完全一致（假設未溢位）；但在浮點數上，改變結合順序會改變運算精度與捨入結果，不能直接假設具備相同的數值一致性行為。
2. 檢驗結論陳述：「這代表電腦算術從循序轉移至平行時會產生相同的結果」（This means that computer arithmetic generates the same results when going from sequential to parallel）。
   • 給定一組具代表性的浮點數反例：
     設 $A = -1.0 \times 10^{30}$、$B = 1.0 \times 10^{30}$、$C = 1.0$。
     • 循序運算順序 $(A + B) + C$： $$(-1.0 \times 10^{30} + 1.0 \times 10^{30}) + 1.0 = 0.0 + 1.0 = 1.0$$
     • 平行運算可能產生的順序 $A + (B + C)$：

核心觀念

本題的核心概念圍繞在管線化技術（Pipelining）之限制與控制危障（Control Hazard / Branch Hazard）的處理機制：

1. 管線化與製程技術（Process Technology）的相依性：
   管線化雖然主要是一種微架構（Microarchitecture）設計技術，但管線時脈頻率、時鐘偏移（Clock Skew）、管線暫存器延遲（Latching Overhead）以及功耗等實體限制，皆與底層半導體製程技術息息相關。更關鍵的是，管線切得越細（Deeper Pipeline），每階邏輯延遲佔比下降，暫存器負擔（Overhead）與製程變異對時脈的影響越大。

2. 延遲分支（Delayed Branch）的特性與局限性：

   • 機制：分支指令後面緊跟著一個或多個「分支延遲槽（Branch Delay Slot）」，無論分支是否發生跳躍（Taken or Not Taken），位於延遲槽中的指令必定會被執行。
   • 適用範圍：延遲分支僅在短管線（Short Pipeline）（如經典 MIPS 5 階管線，分支延遲槽通常僅需 1 個週期）時有效且易於排程。
   • 長管線（Longer/Deeper Pipeline）下的失效：當管線加深時，分支目標與分支結果的判定可能需要 $3 \sim 8$ 個週期以上才能確定，這意味著需要填入大量（多個）延遲槽。編譯器很難找到足夠多無資料相依（Data Dependency）的有效指令來填滿多個延遲槽，多數時候只能填入 NOP（No Operation），失去延遲分支的意義。因此，現代長管線處理器早已棄用延遲分支，改採**動態分支預測（Dynamic Branch Prediction）**配合投機執行（Speculative Execution）。

解題方法

判定此題 True/False 的切入點有二：

1. 分析前半句：「Pipelining techniques can be implemented independent of process technology.」
   • 管線化的實作無法完全脫離製程技術（Physical Constraints / Clock Skew / Wire Delay / Thermal Issues）。
2. 分析後半句：「the delayed branch is ... very useful for processors with longer pipelines.」
   • 延遲分支技術在現代長管線（Longer/Deeper Pipelines）中是無效且不適用的（Not useful / Obsolete），長管線對延遲槽數量的需求過高，導致編譯器無法填補，必須改用動態分支預測。

後半句為極為明確且經典的計算機組織觀念錯誤，因此整段敘述為 False。

選項分析（命題細部剖析）

核心觀念

本題測驗計算機組織中**「記憶體階層架構（Memory Hierarchy）」與「軟體效能最佳化（Software Performance Optimization / Locality）」**的關聯性。

在現代計算機架構中，處理器（CPU）的運算速度遠快於主記憶體（DRAM）的存取速度（即所謂的 Memory Wall）。為了彌補此延遲落差，架構上引入了多層快取記憶體（Cache）。高階語言（如 C/C++）雖然提供了指針、陣列、結構體等抽象機制，讓程式員無需手動管理實體記憶體位址，但編譯器（Compiler）的能力有限，無法完全推斷複雜資料結構與控制流的存取模式。若程式員在撰寫程式時忽視了記憶體系統的特性（例如時間區域性 Temporal Locality 與 空間區域性 Spatial Locality），會導致大量的 Cache Miss，造成嚴重的效能低落。

解題方法

切入點在於檢視題目敘述中的全稱主張：「without considering memory system behavior of a computer（不需要考慮電腦的記憶體系統行為）是否仍能產生高效能程式碼？」。

1. 記憶體存取模式的影響：
   以 C 語言中的二維陣列走訪（Row-major order）為例：
   • Row-major 走訪（具空間區域性）：
     連續走訪鄰近位址，快取行（Cache Line）命中率高，效能極佳。
   • Column-major 走訪（跨 stride 走訪）：
     每次存取都跨越整列，破壞空間區域性，引發連續的 Cache Miss，執行速度可能慢數倍甚至數十倍。
2. 編譯器最佳化的極限：
   現代編譯器（如 GCC、Clang）雖具備一定程度的迴圈轉換（Loop Interchange、Loop Tiling/Blocking）與自動向量化能力，但受限於指標別名（Pointer Aliasing）、動態配置大小、間接定址（如 Graph/Tree 結構走訪）等因素，編譯器無法在靜態分析時替所有演算法做出最佳排程。

核心觀念

本題考查磁碟排程（Disk Scheduling）的實作層次與磁碟幾何抽象化（Logical Block Addressing, LBA）。

1. OS 的角色：作業系統確實負責接收來自使用者空間（User-space）程式的 I/O 請求，並透過驅動程式（Device Driver）將請求發送給儲存裝置。
2. 現代磁碟控制器（Disk Controller）的優勢：
   • 現代硬碟普遍採用邏輯區塊定址（Logical Block Addressing, LBA），向作業系統隱藏了實體的磁軌（Track）、磁區（Sector）、磁頭位置（Head Position）、壞軌重組（Bad Block Remapping）以及磁軌交錯（Track Skew）等實體幾何細節。
   • 作業系統僅能得知邏輯區塊號碼，因此 OS 只能根據 LBA 號碼進行簡化的排程（如 SSTF、SCAN、LOOK 等，主要針對尋道時間 Seek Time 最佳化），但無法得知當前磁頭的實際旋轉角度與旋轉延遲（Rotational Latency）。
   • 現代硬碟控制器內部具備微處理器與板載快取，並支援 NCQ（Native Command Queuing） 或 TCQ（Tagged Command Queuing） 等技術。控制器擁有硬體的精準即時狀態，能實施同時考量尋道時間與旋轉延遲的演算法（如 SATF, Shortest Access Time First），因此在「提升純粹的磁碟存取效能」上，磁碟控制器（硬體端）比作業系統更有優勢。

解題方法

分析題幹的兩段陳述與因果推論：

1. 前半句：Operating Systems (OS) is responsible for serving the disk accesses requested by user-space programs.
   • 敘述正確。使用者程式無法直接存取硬體，必須透過系統呼叫（System Calls）由作業系統內核處理與轉發 I/O 請求。

核心觀念

本題的核心觀念為**處理器效能方程式（CPU Performance Equation）**中各項因子的相依性（Dependency）。

程式的 CPU 執行時間（CPU Execution Time）基本公式為：

或以時脈頻率 $f$（Clock Rate）表示：

其中各參數定義如下：

1. Instruction Count（IC，即題目之 Instruction number）：執行該程式所需的指令總數。
2. CPI（Clock Cycles Per Instruction，即題目之 Clock cycles required for each instruction）：平均每條指令執行所需的時脈週期數。
3. Clock Cycle Time（$T_c$）：單一時脈週期的時間長度。

這三者並非彼此獨立（Not Independent），而是高度互相影響與制約的。

解題方法

從**編譯器最佳化技術（Compiler Optimization）與指令集架構設計（ISA Trade-offs）**切入分析：

1. 編譯器最佳化層面：
   • 當編譯器進行迴圈展開（Loop Unrolling）或函式內聯（Function Inlining）時，程式的靜態與動態指令數量（Instruction Count）會改變；同時，這類最佳化通常消除了條件分支指令（Branch），而分支指令在流水線（Pipeline）中往往具有較高的週期代價（因 Branch Misprediction 造成流水線停頓），因此平均每條指令的週期數（CPI）也會跟著改變。
   • 若編譯器為了縮短整體執行時間，將多條簡單指令代換為一條複雜指令（例如使用複雜的定址模式或向量指令），Instruction Count 會減少，但該複合指令往往需要耗費更多的執行週期，導致平均 CPI 上升。

核心觀念

本題評量計算機效能評估中的基本公式——CPU 效能方程式（CPU Performance Equation）。

1. CPU 執行時間（CPU Execution Time）：
   衡量處理器效能（Performance）的黃金準則（Iron Law）為完成特定程式所需的 CPU 執行時間：

   $$\text{CPU Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time}$$

   由於時脈頻率（Clock Rate, $f$）與時脈週期（Clock Cycle Time, $T_c$）互為倒數（$T_c = \frac{1}{f}$），公式可改寫為：

   $$\text{CPU Time} = \frac{\text{IC} \times \text{CPI}}{\text{Clock Rate}}$$
   • $\text{IC}$（Instruction Count）：程式執行的指令總數。
   • $\text{CPI}$（Cycles Per Instruction）：每個指令平均所需的時脈週期數。
   • $\text{Clock Rate}$：處理器的時脈頻率（通常以 $\text{MHz}$ 或 $\text{GHz}$ 為單位）。

2. 效能（Performance）與執行時間的關係：
   計算機系統中，效能定義為執行時間的倒數：

   $$\text{Performance} = \frac{1}{\text{Execution Time}} \propto \text{Clock Rate}$$

   在指令總數（$\text{IC}$）與 $\text{CPI}$ 維持不變的情況下，處理器的效能與時脈頻率（Clock Rate）成正比。

解題方法

從 CPU 效能方程式切入：

1. 觀察時脈頻率對 CPU 執行時間的直接影響：當降低時脈頻率（Lowering the Clock Rate, 即 $f$ 變小），時脈週期時間（$T_c = \frac{1}{f}$）將會拉長。

核心觀念

本題評量計算機效能評估的基本定律：CPU 效能公式（CPU Performance Equation / Iron Law of Processor Performance）。

一支程式在處理器上的 CPU 執行時間（CPU Execution Time, $T_{\text{CPU}}$）由三個基本要素共同決定：

1. 指令數（Instruction Count, $IC$）：執行該程式所需的總機器指令數量，取決於演算法、原始碼、編譯器最佳化技術與指令集架構（ISA）。
2. 平均每條指令時脈週期數（Cycles Per Instruction, $CPI$）：執行平均一條指令所需的時脈週期數，取決於處理器的微架構（如管線深度、超純量發射寬度、快取架構、分支預測等）及 ISA。
3. 時脈週期時間（Clock Cycle Time, $T_{\text{clk}}$） 或 時脈頻率（Clock Frequency / Rate, $f$）：硬體時脈震盪週期，兩者互為倒數關係（$T_{\text{clk}} = \frac{1}{f}$）。

完整的 CPU 效能評估公式為：

效能（Performance） 定義為執行時間的倒數（$\text{Performance} = \frac{1}{T_{\text{CPU}}}$）。因此，單一時脈頻率 $f$ 的高低並不能直接等同於整體效能。

解題方法

由 CPU 效能公式切入分析：

題幹陳述：「計算密集型（compute-intensive）程式的效能完全由處理器的運作頻率主導，因此在 1 GHz 的處理器上執行必定比在 800 MHz 的另一顆處理器上更快。」

若要使「1 GHz 處理器一定比 800 MHz 處理器快（即 $T_{\text{CPU, 1GHz}} < T_{\text{CPU, 800MHz}}$）」成立，必須存在前提條件：兩顆處理器在執行該程式時的 總時脈週期數（Total Clock Cycles $= IC \times CPI$）必須相同或差距極小（例如為同一款微架構與相同 ISA）。

然而，題目明確指出是 「another processor（另一款處理器）」：

• 兩款不同的處理器可能具備不同的 ISA（導致 $IC$ 不同）。
• 即使具備相同 ISA，不同的微架構設計（例如多發射 Out-of-Order 架構對比單發射 In-Order 架構）會使 $CPI$ 產生巨大差異。
• 舉例而言：

核心觀念

本題的核心觀念為編譯器針對管線架構中**控制危障（Control Hazard）與分支懲罰（Branch Penalty）**所採用的程式代碼最佳化技術：迴圈展開（Loop Unrolling）。

1. 分支懲罰（Branch Penalty）的來源：
   在管線化處理器（Pipelined Processor）中，迴圈每次迭代的末端皆包含條件跳躍指令（Conditional Branch），用於檢查終止條件並跳回迴圈開頭。若處理器發生分支預測錯誤（Branch Misprediction），管線必須沖刷（Flush）已抓取的錯誤指令，造成數個週期的停頓（Stall）。
2. Loop Unrolling 的原理：
   • 複製迴圈本體多次（稱為展開因子，Unrolling Factor，如 $k = 2, 4$）。
   • 迴圈的迭代次數縮減為原來的 $1/k$ 倍。
   • 顯著減少條件分支判斷與計數器更新指令（如 j++ 或 addi）的總執行數，從而降低分支處罰發生的頻率。
   • 同時擴大基本區塊（Basic Block），為編譯器提供更大的指令排程（Instruction Scheduling）空間以隱藏記憶體存取延遲，提升指令層次平行度（ILP）。

解題方法

題目明確詢問「減輕執行時分支懲罰（alleviate branch penalties）」的常用編譯器最佳化技術，並要求給出編譯器產生的最佳化程式碼。

1. 技術名稱：
   此編譯技術為 Loop Unrolling（迴圈展開）。
2. 展開策略：
   • 題目中的內層迴圈邊界為 $1000$，可被常見的展開因子（如 $2, 4$）整除，無須額外撰寫迴圈清理尾段（Cleanup/Epilogue loop）。
   • 內層迴圈通常是熱點路徑（Hot Path），分支跳躍最頻繁（每執行 $1$ 次外層迴圈，內層就要進行 $1000$ 次分支判斷），因此優先展開內層迴圈 j。
   • 以 $4$ 步展開（Unrolling Factor = 4）為例，將原本每次迭代處理 $1$ 個元素，改為每次迭代循序處理 $4$ 個元素（$j, j+1, j+2, j+3$），步進量（Step）由 $+1$ 改為 $+4$。

最佳化程式碼（以 4-way Loop Unrolling 為例）

核心觀念

本題評估雙核心處理器（Dual-core Processor）執行巢狀迴圈並行化（Parallelization）時所能達到的「理想加速比（Ideal Speedup）」，核心觀念包含：

1. 迴圈資料相依性（Loop Data Dependency）：

   • 檢查迴圈疊代（Iterations）之間是否存在迴圈攜帶相依（Loop-carried Dependency）。
   • 在本迴圈中，寫入目標為陣列 $A$（$A[i][j]$），讀取來源為陣列 $B$（$B[j][i]$），兩者配置於不同記憶體空間（非同一陣列）。對於任意一組不同的 $(i, j)$，寫入的 $A[i][j]$ 位址均不重疊，且計算只讀取 $B$，完全沒有跨疊代的讀寫（RAW, WAR, WAW）相依關係。因此該迴圈屬於完全可平行化（Embarrassingly Parallel / Fully Parallel）的迴圈。

2. 阿姆達爾定律（Amdahl's Law）與理想加速比：

   • 加速比公式為： $$\text{Speedup} = \frac{T_{\text{seq}}}{T_{\text{parallel}}}$$
   • 當程式可 $100\%$ 平行化（平行化比例 $f = 1$），且無任何循序執行開銷、控制阻障（Control Hazard）、快取失誤懲罰（Memory Miss Overhead 題目已假設忽略）或執行緒同步/通訊負擔時，加速比的理論上限（理想加速比）即等於處理器核心數 $p$。

解題方法與詳細推導

1. 檢查平行化可行性（資料相依分析）：

   for (i = 0; i < 1000; i++)
       for (j = 0; j < 1000; j++)
           A[i][j] = B[j][i] * 100 + 20;
   

   • 總疊代次數共 $1000 \times 1000 = 10^6$ 次。
   • 每一次運算皆為獨立的純量運算，寫入唯一的 $A[i][j]$，讀取已初始化的 $B[j][i]$。
   • 各疊代之間完全無資料相依（No loop-carried dependency），故程式碼的平行化比例 $f = 100\% = 1$。

2. 工作負載分配（Workload Distribution）：

   • 在具備 2 個實體核心的雙核心處理器 $\alpha$ 上，可將外層迴圈平均分配給兩個核心：
     • Core 0 執行：$i = 0 \sim 499$（共 $5 \times 10^5$ 次運算）
     • Core 1 執行：$i = 500 \sim 999$（共 $5 \times 10^5$ 次運算）
   • 兩核心工作量完全對稱且均衡（Load Balanced）。

核心觀念

1. SIMD（單指令多資料流，Single Instruction, Multiple Data）：

   • SIMD 是一種資料層級平行（Data-Level Parallelism, DLP）架構。
   • 藉由將多個純量（Scalar）資料打包放入寬暫存器（Vector/SIMD Register）中，一條 SIMD 指令即可同時對多組運算元並行執行相同操作。

2. SIMD 平行度（Degree of Parallelism / Vector Lanes）：

   • 設 SIMD 暫存器寬度為 $W_{\text{reg}}$ 位元，每個陣列元素資料寬度為 $W_{\text{elem}}$ 位元。
   • 單一暫存器可容納的資料元素個數（平行通道數）為： $$N_{\text{lanes}} = \frac{W_{\text{reg}}}{W_{\text{elem}}}$$

3. 效能比（Performance Ratio / Speedup）公式：

   • 效能與執行時間成反比： $$\text{Performance Ratio} = \frac{\text{Performance}_{\text{with SIMD}}}{\text{Performance}_{\text{without SIMD}}} = \frac{\text{Execution Time}_{\text{without SIMD}}}{\text{Execution Time}_{\text{with SIMD}}}$$
   • 題目假設無控制危障（No control hazard）且記憶體遺失代價可忽略（Memory miss overhead is negligible），因此執行時間正比於所需執行的算術與資料處理週期／指令批次數。

解題方法

1. 確定元素尺寸與暫存器容量：

   • 陣列元素均為 32-bit 整數（即 4 bytes），故 $W_{\text{elem}} = 32\text{ bits}$。
   • 機器 $\beta$ 的 SIMD 暫存器寬度為 128-bit，故 $W_{\text{reg}} = 128\text{ bits}$。
   • 單一 SIMD 暫存器可同時並行處理的元素數量為： $$N_{\text{lanes}} = \frac{128\text{ bits}}{32\text{ bits}} = 4$$

2. 迴圈資料相依性與可向量化評估：

   • 內層核心運算式為：A[i][j] = B[j][i] * 100 + 20;。