114 專技高考高等考試 資訊技師 計算機系統 考古題詳解

核心觀念

本題考查快取記憶體的命中與失誤，以及 Direct-Mapped Cache 中區塊大小對失誤率、空間利用與失誤代價的影響。

• Cache Hit（快取命中）：處理器要存取的資料或指令已在 Cache 中，因此可直接由 Cache 提供。
• Cache Miss（快取失誤）：要存取的資料或指令不在 Cache 中，系統必須向下一層記憶體（通常是主記憶體）取得。
• Miss Penalty（失誤代價）：發生 Cache Miss 後，為取得所需區塊、更新 Cache 並讓處理器繼續執行所增加的時間或成本。Miss Penalty 越高，Cache Miss 對效能的影響越大。

Cache 的目的在於利用小而快的記憶體，保存近期或常用的資料，降低平均存取時間。常見的平均記憶體存取時間模型為：

其中，Miss Rate 為存取中發生 Cache Miss 的比例。即使命中時間很短，只要 Miss Rate 或 Miss Penalty 偏高，平均存取時間仍會增加。

解題方法：區塊大小與 Miss Rate

設 Cache 容量固定為 $C$，每個區塊大小為 $B$，則 Cache 的區塊數為：

因此，區塊越大，Cache 中可容納的區塊數越少。在 Direct-Mapped Cache 中，每個主記憶體區塊只能映射至 Cache 中唯一的一個位置；區塊數減少時，不同主記憶體區塊映射到同一 Cache 位置的機會增加，可能提高衝突失誤（conflict miss）。

不過，較大的區塊一次會帶入更多相鄰資料。若程式會連續存取相鄰位址，之後的存取可能直接命中，降低強制失誤（compulsory miss）。所以，Block Size 與 Miss Rate 沒有在所有情況下都單調增減的固定關係：區塊變大可能因空間區域性而降低 Miss Rate，也可能因 Cache 區塊數減少、有效資料被擠出而提高 Miss Rate。

較大區塊的優點與缺點

優點

• 利用空間區域性：程式存取某位址後，常會接著存取附近位址；較大的區塊可一次帶入這些相鄰資料，提高後續存取命中率。

核心觀念

本題考查作業系統如何用 行程控制區塊（Process Control Block, PCB） 保存行程的執行資訊，以及行程在 三狀態模型（Three-State Process Model） 中如何轉換。

PCB 是作業系統管理行程時使用的資料結構；三狀態模型則以「執行、可執行、等待」描述行程是否正在使用 CPU、是否具備執行條件，或是否正等待某項事件。

（一）PCB 的功用與基本資訊

PCB 的功用

作業系統為每個行程維護一個 PCB，作為該行程的管理紀錄。行程被中斷或切換時，作業系統會把當下的處理器狀態等資訊保存到該行程的 PCB；之後排程器再次選中該行程時，便可依據 PCB 恢復其執行環境。

因此，PCB 支援行程的建立、排程、暫停、恢復、資源管理與結束。**內容切換（context switch）**的核心工作之一，就是保存目前行程的狀態並載入下一個行程的狀態。

PCB 的基本資訊

不同作業系統的 PCB 欄位名稱與細節可能不同，基本上可分為下列類別：

1. 行程識別資訊：例如行程識別碼（PID）、父行程識別碼，以及使用者或擁有者識別資訊，用來辨認行程及其關係。

2. 行程狀態：記錄行程目前是新建、可執行、執行中、等待，或已結束等狀態，以供核心管理及排程使用。

3. 處理器執行環境：包括程式計數器（Program Counter）、處理器暫存器、堆疊指標，以及處理器狀態字等。行程切換時，這些資訊用來保存及恢復行程的執行位置與處理器狀態。

4. CPU 排程資訊：例如優先權、排程佇列連結、時間片或其他排程參數，供排程器決定行程何時取得 CPU。

5. 記憶體管理資訊：例如頁表或區段表指標、記憶體配置資訊，以及程式碼、資料與堆疊區域的相關資訊，供作業系統管理行程的位址空間。

6. 輸入／輸出與檔案資訊：例如已配置的 I/O 裝置、開啟檔案、未完成的 I/O 操作或相關狀態，協助作業系統追蹤行程所使用的資源。

7. 會計與使用統計資訊：例如 CPU 使用時間、執行時間、建立時間、資源使用量或限制，用於統計、管理與資源控管。

作答時應掌握兩個重點：PCB 必須能保存行程被切換時所需的執行環境，也必須提供排程器與資源管理機制所需的管理資料。

（二）Three-State Process Model 與三類狀態轉移

三狀態模型

三狀態行程模型將行程分為：

核心觀念

本題分成兩部分：第一部分考 Virtualization、Virtual Machine 與 Hypervisor 的定義及彼此關係；第二部分考平行化的工作量分析，以及核心數增加對加速比與成本效益的影響。

虛擬化是透過抽象化或分割實體資源，建立多個彼此隔離的虛擬資源環境。Virtual Machine（VM，虛擬機器）是以軟體呈現的計算環境，具有虛擬的處理器、記憶體、儲存裝置等，可執行自己的作業系統與應用程式。Hypervisor（虛擬機器監視器）則負責建立及管理 VM，並分配、隔離與仲介 VM 對實體硬體的存取。

本題的加速比以單核心執行時間除以多核心執行時間計算。若工作可完全平行化，使用 $P$ 個核心時，加速比等於平行工作量除以 $P$，再加上不能平行化的工作量。

解題方法

（一）Virtualization、VM 與 Hypervisor

三者的關係是：Virtualization 是技術與概念，Hypervisor 是實作及管理此技術的軟體層，VM 是 Hypervisor 建立並管理的虛擬執行環境。

例如，一台實體伺服器可透過 Hypervisor 建立數個 VM。每個 VM 都能執行自己的作業系統與應用程式；Hypervisor 則負責分配實體 CPU、記憶體與儲存資源，並隔離各 VM，使其中一台 VM 的作業不會直接干擾其他 VM。

（二）核心數、加速比與成本效益

依題意，將兩項工作視為可完全平行化，且每個核心每單位時間可完成一個純量加法：

• 加總 $N$ 個純量，需 $N-1$ 次加法。
• 兩個 $N\times N$ 矩陣相加，每個元素各需一次加法，共 $N^2$ 次加法。

因此，單核心總工作量為

若使用 $P$ 個核心，平行執行時間與 $W/P$ 成正比，故加速比為

但兩項工作中，矩陣相加有 $N^2$ 個可平行處理的元素；純量加總若只按題目給定的單一加總工作視為不可分割部分，則需要 $N-1$ 個單位時間。依此工作模型，方案 A、B 的時間分別為

因此，方案 A 的加速比為

核心觀念

本題考兩個觀念：輸入／輸出介面（I/O interface）如何協調 CPU 與周邊設備，以及編譯器如何分階段處理高階語言程式。

周邊設備在速度、資料格式、控制方式與電氣特性上各不相同，CPU 則依照自己的指令與匯流排規格運作，因此需要 I/O 介面作為兩者之間的橋接與控制單元。編譯器處理原始程式時，常見的四個主要階段依序為：詞彙分析、語法分析、語意分析、程式碼產生。各階段處理不同層次的程式結構，也會檢查相應類型的錯誤。

（一）I/O Interface 的理由與功用

為什麼需要 I/O Interface

CPU 與輸入／輸出設備直接互通時，會遇到下列差異：

1. 速度不同：CPU 執行速度遠快於鍵盤、印表機等設備，需有暫存或緩衝機制，配合設備速度傳送資料。
2. 資料格式不同：CPU 通常處理固定寬度的二進位資料；周邊設備可能使用不同的資料格式或資料寬度，需由介面轉換。
3. 控制與狀態不同：設備有自己的操作命令與狀態，例如「忙碌」、「就緒」、「傳輸完成」或「發生錯誤」，CPU 需透過介面下達命令並讀取狀態。
4. 電氣與傳輸規格不同：CPU 匯流排與外部設備的訊號電壓、時序或傳輸方式可能不同，需由介面配合與轉換。

I/O Interface 的功用與例子

I/O 介面可提供資料暫存、格式或訊號轉換、設備控制、狀態回報，以及中斷或 DMA 傳輸協調等功能。

以鍵盤介面為例：使用者按下按鍵後，介面取得按鍵訊號，將它轉成可供系統處理的資料碼，暫存資料並通知 CPU 有新輸入。CPU 可讀取介面中的資料，也可查看設備狀態。

以磁碟控制器為例：CPU 對控制器下達讀取命令並指定位置，控制器負責與磁碟裝置溝通、回報忙碌或完成狀態，也可透過 DMA 將資料直接傳送到主記憶體，減少 CPU 逐字搬移資料的負擔。

（二）編譯器的四個主要步驟

解題方法

依照編譯器處理程式的層次，由小到大排列：

1. 先辨認原始程式中的字元組合，形成記號。
2. 再檢查記號是否符合文法規則，形成語法結構。
3. 接著檢查結構在語言規則與型別上是否合理。
4. 最後將程式轉換為目標機器可執行的程式碼。

1. 詞彙分析（Lexical Analysis）

詞彙分析器讀取原始程式字元，依語言規則組成記號（token），例如關鍵字、識別字、運算子、常數與分隔符號，並略過空白及註解。識別字也可能在此階段建立或查詢符號表。

可偵測的問題是無法構成合法記號的字元或字元組合。例如：

int @count;

若 @ 不屬於該語言允許的符號，詞彙分析器會回報非法字元。字串常數未正確結束，也可能在此階段被發現。

2. 語法分析（Syntax Analysis）