110 年 國立臺灣大學資訊工程學系碩士班《計算機結構與作業系統(B)》

核心觀念

本題考查單體式作業系統（monolithic operating system）的服務配置。記憶體管理屬於作業系統核心服務；在單體式架構中，這類服務集中在核心層，而非應用程式層或硬體層。

解題方法

核心觀念

本題考作業系統分層架構中，標準輸入輸出函式庫的位置。Linux 的標準 I/O 函式庫屬於使用者空間的系統函式庫，提供如 printf、fopen 等函式，並在需要時透過系統呼叫請求核心處理 I/O。

解題方法

核心觀念

作業系統的排程器負責決定哪些處理程序或執行緒取得 CPU，以及何時執行。這是核心管理處理器資源的功能，因此排程服務位於核心層。容器共用主機的作業系統核心，並不各自帶有獨立核心。

解題方法

圖中四個虛線框依序標示：A 位於應用程式層、B 位於系統服務層、C 位於核心層、D 位於硬體層。系統服務層包含系統程式庫等服務；核心層包含核心元件。

核心觀念

本題考作業系統架構中，微核心與裝置驅動程式的配置。微核心只保留排程、行程間通訊等基本功能；裝置驅動程式則作為核心外的服務執行，降低驅動程式錯誤對核心的影響。

解題方法

核心觀念

行程的記憶體配置通常由低位址往高位址依序包含程式碼、資料區、堆積區與堆疊區。堆積區通常向高位址成長，堆疊區則由高位址向低位址成長；兩者之間的空間可供各區擴張使用。

解題方法

圖中低位址 $0x00000000$ 在底部，高位址 $0xFFFFFFFF$ 在頂部；

核心觀念

行程的記憶體配置中，**文字區段（text segment）**存放程式的機器指令，通常位於較低位址，接著是已初始化資料區段、未初始化資料區段與堆積；堆疊則靠近較高位址。

解題方法

核心觀念

行程的記憶體配置通常由低位址往高位址依序為：文字區段、已初始化資料區段、未初始化資料區段（BSS）、堆積區與堆疊區。未初始化資料區段存放未明確指定初值的全域變數與靜態變數；程式載入時，這些變數會被設為 0。

解題方法

核心觀念

行程的虛擬記憶體通常由低位址往高位址依序配置程式碼、資料與堆積；堆積向高位址成長，堆疊向低位址成長。兩者之間尚未配置的區域就是 free space（自由空間）。

解題方法

核心觀念

輪轉排程（Round Robin, RR）依就緒佇列順序輪流分配 CPU，每個行程每次最多執行一個時間片。本題時間片長度為 $3$；行程在時間片用完前完成 CPU 工作或因 I/O 阻塞時，會提早離開 CPU。I/O 在不同裝置上進行，因此可與 CPU 工作重疊。

題目指定 I/O 在行程第一次使用 CPU 一個時間單位後開始。以下將 CPU Burst 視為該行程所需的 CPU 總時間；開始 I/O 後，行程完成 I/O 再回到就緒佇列，繼續使用剩餘 CPU 時間。

解題方法

依到達時間維護就緒佇列，逐段排出 CPU 執行順序。到達的新行程及 I/O 完成的行程加入佇列尾端；若時間片用完，仍未完成且未阻塞的行程也加入佇列尾端。時間邊界若有 I/O 完成與時間片到期同時發生，採用 I/O 完成的行程先加入佇列的慣例。

排程如下：

核心觀念

非搶先式優先權排程：CPU 空閒時，從就緒佇列中選優先權最高（數值最小）的行程；行程一旦取得 CPU，就執行到這一段 CPU 工作結束或發出 I/O 請求為止，期間不會被新到的高優先權行程搶走。

依題意，有 I/O 的行程先使用 CPU 1 個時間單位，接著進行 I/O；I/O 完成後回到就緒佇列，再執行剩下的 CPU 工作。I/O 在不同裝置上進行，可與 CPU 執行重疊。同優先權時採先到先服務。

解題方法

核心觀念

搶先式最短工作優先（preemptive SJF，也稱 SRTF）每次選擇「剩餘 CPU 時間最短」的就緒程序執行。新程序到達或有程序完成 I/O 返回時，都要重新比較；若目前執行程序仍有最短剩餘時間，就繼續執行。

依題意，PID 5 先執行 1 個時間單位，接著進行 2 個時間單位的 I/O，I/O 完成後再執行剩餘的 CPU 時間。

解題方法

依 SRTF 排定 CPU 執行順序，並把 I/O 視為可與 CPU 工作重疊的等待時間：

核心觀念

LISC 是 Longest I/O burst, Shortest CPU burst：先選 I/O burst 較長的就緒行程；I/O burst 相同時，選剩餘 CPU burst 較短者。題目指定搶先式，因此有更優先的就緒行程到達時，會中斷目前行程。這題的 priority 欄不參與 LISC 排序。

各行程第一次使用 CPU 一個時間單位後，若有 I/O burst，便進入 I/O 等待；I/O 可在不同裝置上與 CPU 工作重疊。I/O 完成後，行程回到就緒佇列，繼續執行剩餘 CPU burst。

解題方法

依 LISC 規則逐段排程。相同 I/O burst 的就緒行程，以剩餘 CPU burst 較短者優先；仍相同時，採先到者優先。

核心觀念

LIF 是「最長剩餘 I/O 時間優先」（Longest I/O First）：比較就緒程序尚未完成的 I/O 時間，剩餘 I/O 時間較長者優先；採搶先式時，新到達或剛完成 I/O 的程序若有較長的剩餘 I/O 時間，就能搶占目前使用 CPU 的程序。此題的 LIF 依 I/O 時間決定順序，表中的 priority 不參與判斷。

每個有 I/O 的程序先執行 1 個時間單位，再開始 I/O；I/O 期間不占用 CPU，完成後回到就緒佇列。以下相同 LIF 順序時，依較早到達者先執行。

解題方法

逐一追蹤 CPU 執行、I/O 開始與完成，以及可能發生的搶占：

• $t=0$ 至 $2$：PID 1 執行 2 單位。$t=2$ 時 PID 2 到達，剩餘 I/O 時間為 3，搶占 PID 1。
• $t=2$ 至 $3$：PID 2 執行 1 單位後開始 I/O，於 $t=6$ 完成。
• $t=3$ 至 $4$：PID 1 恢復執行 1 單位。$t=4$ 時 PID 4 到達，其 I/O 時間為 3，開始執行。
• $t=4$ 至 $5$：PID 4 執行 1 單位後開始 I/O，於 $t=8$ 完成。
• $t=5$ 至 $6$：PID 1 執行完剩餘 1 單位，於 $t=6$ 完成。
• $t=6$ 至 $10$：PID 2 的 I/O 已完成，剩餘 CPU 時間為 4；PID 2 執行至 $t=10$ 完成。
• $t=10$ 至 $11$：PID 5 到達，CPU burst 為 8。

核心觀念

時鐘時間（clock time）是程式從開始到完成所經過的實際時間，包含程式執行時間，也包含等待 I/O 完成的時間。

write() 在一般緩衝式檔案系統中，通常可在資料複製到核心的頁面快取後返回；這不代表資料已寫入儲存裝置。fsync() 則要求核心將該檔案的資料與必要中繼資料同步到儲存裝置，呼叫者須等待同步完成。

解題方法

檔案很大且檔案系統區塊為 4 KB，因此基準設定會以 4 KB 為單位呼叫 write() 多次。加入 fsync() 後，每次寫入都要等待同步完成；大量同步等待會增加總經過時間。

核心觀念

CPU 時間分成使用者 CPU 時間與系統 CPU 時間。使用者 CPU 時間計算程式在使用者模式執行指令的時間；write()、fsync() 進入核心後執行的工作，主要計入系統 CPU 時間。等待磁碟完成 I/O 的時間則會影響實際經過時間，不等於使用者 CPU 時間。

解題方法

設檔案大小為 $S$，且可被 $8\text{ KB}$ 整除。

基準設定每次寫入 $4\text{ KB}$，約呼叫：

次 write()。

(b) 每次寫入 $8\text{ KB}$，約呼叫：

次 write()，並在每次寫入後呼叫一次 fsync()。因此，write() 與 fsync() 的呼叫總數約為：

核心觀念

系統 CPU 時間是作業系統核心替程序執行工作的時間。對檔案輸出而言，每次呼叫 write() 都有系統呼叫與核心處理開銷；寫入呼叫越頻繁，通常系統 CPU 時間越多。

基準設定每次以 write() 寫入 4KB。題目 (c) 改為逐行緩衝，使用 puts() 輸出；每輸出一行便會觸發緩衝區寫出。

解題方法

題目未提供每行資料的長度。依逐行輸出題型的通常假設，每行長度小於 4KB，且每次 puts() 輸出一行後便寫出緩衝區。

在此假設下，逐行緩衝每輸出一行就要進行一次核心寫入；基準則每累積 4KB 才呼叫一次 write()。因此，逐行緩衝的系統呼叫次數較多，系統 CPU 時間較高。

核心觀念

CPU 時間分成使用者 CPU 時間與系統 CPU 時間。使用者 CPU 時間計算程式在使用者模式執行指令的時間；write()、fsync() 進入核心後執行的工作，主要計入系統 CPU 時間。等待磁碟完成 I/O 的時間則會影響實際經過時間，不等於使用者 CPU 時間。

解題方法

設檔案大小為 $S$，且可被 $8\text{ KB}$ 整除。

基準設定每次寫入 $4\text{ KB}$，約呼叫：

次 write()。

(b) 每次寫入 $8\text{ KB}$，約呼叫：

次 write()，並在每次寫入後呼叫一次 fsync()。因此，write() 與 fsync() 的呼叫總數約為：

核心觀念

系統 CPU 時間是作業系統核心替程序執行工作的時間。對檔案輸出而言，每次呼叫 write() 都有系統呼叫與核心處理開銷；寫入呼叫越頻繁，通常系統 CPU 時間越多。

基準設定每次以 write() 寫入 4KB。題目 (c) 改為逐行緩衝，使用 puts() 輸出；每輸出一行便會觸發緩衝區寫出。

解題方法

題目未提供每行資料的長度。依逐行輸出題型的通常假設，每行長度小於 4KB，且每次 puts() 輸出一行後便寫出緩衝區。

在此假設下，逐行緩衝每輸出一行就要進行一次核心寫入；基準則每累積 4KB 才呼叫一次 write()。因此，逐行緩衝的系統呼叫次數較多，系統 CPU 時間較高。

核心觀念

sigsuspend() 會暫時以指定的訊號遮罩取代目前遮罩，接著暫停程序，直到收到未被遮罩且有處理常式的訊號。收到訊號後，執行處理常式；處理常式返回時，sigsuspend() 才返回，並恢復呼叫前的訊號遮罩。

解題方法

程式先在第 32 行以 SIG_BLOCK 封鎖 SIGINT，再於第 43 行呼叫：

核心觀念

sigprocmask 用來設定程序的訊號遮罩；被遮罩的訊號暫時不會送進訊號處理常式。sigsuspend(&waitmask) 則會暫時以 waitmask 取代目前的訊號遮罩，並讓程序等待訊號。收到一個未被遮罩、且其處理常式正常返回的訊號後，sigsuspend 會返回 -1，並將原本的訊號遮罩恢復。

本題中，程式先把 SIGINT 加入 newmask，再用 sigprocmask(SIG_BLOCK, ...) 封鎖它。進入 sigsuspend 時，臨時遮罩 waitmask 只包含 SIGUSR1，因此 SIGUSR2 沒有被封鎖。

解題方法

SIGUSR2 已透過 sigaction 設定由 sigHandling 處理。程序等待期間收到 SIGUSR2 時，會呼叫該處理常式，而非採用 SIGUSR2 的預設處置。處理常式返回後，sigsuspend 返回，程序便從該呼叫之後繼續執行。

訊號遮罩的變化如下：

核心觀念

處理訊號時，核心會暫時把「目前正在處理的訊號」加入程序的訊號遮罩；除非設定 SA_NODEFER，否則該訊號在其處理函式執行期間會被阻擋。sigaction 的 sa_mask 則指定處理函式執行期間額外阻擋的訊號。

sigsuspend(&waitmask) 會暫時以 waitmask 取代目前的訊號遮罩，直到有未被阻擋的訊號觸發處理函式。處理函式結束後，才恢復原本的訊號遮罩。

解題方法

程式設定 waitmask 只包含 SIGUSR1，而 handling.sa_mask 為空；handling.sa_flags = 0，因此沒有設定 SA_NODEFER。

當程序在 sigsuspend 期間收到 SIGUSR2：

1. sigsuspend 暫時採用 waitmask，因此 SIGUSR1 被阻擋。
2. 核心開始執行 SIGUSR2 的處理函式時，自動阻擋目前正在處理的 SIGUSR2。
3. sa_mask 為空，沒有其他額外訊號加入遮罩。

核心觀念

sigsuspend(&waitmask) 會先暫時以 waitmask 取代目前的訊號遮罩，並等待未被遮罩的訊號。當訊號被捕捉時，流程會先執行訊號處理函式；處理函式返回後，sigsuspend 恢復呼叫前的訊號遮罩，並以 -1 返回，錯誤碼為 EINTR。

解題方法

第 32 行先封鎖 SIGINT，之後第 43 行呼叫 sigsuspend(&waitmask)。

核心觀念

sigsuspend(&waitmask) 會暫時以 waitmask 取代目前的訊號遮罩，直到捕捉到訊號。此程式的 waitmask 只有 SIGUSR1，所以等待期間只有 SIGUSR1 被封鎖，SIGINT 與 SIGUSR2 都未封鎖。

訊號處理器執行期間是否自動封鎖剛捕捉到的訊號，取決於 signal() 的語意與實作；這也是本題選項判斷的關鍵。

解題方法

按傳統 System V signal() 語意解讀本題：進入處理器時，不會自動封鎖目前捕捉到的 SIGINT。因此處理器執行時沿用 sigsuspend() 設定的暫時遮罩，只有 SIGUSR1 被封鎖，SIGUSR2 和 SIGINT 未封鎖。

所以依這項傳統語意，答案是 (B) SIGUSR1。

選項分析

• (A) SIGUSR1 和 SIGUSR2：錯。 waitmask 沒有加入 SIGUSR2，程式也沒有其他操作封鎖它。
• **(B) SIGUSR1：對。

核心觀念

直接對映快取的實體位址可分成三個欄位：

標籤陣列儲存每條快取行的 Tag。快取行數由資料快取容量除以每行大小決定；每個 Tag 的位元數則由位址總位元數扣除 Index 與 Block Offset 的位元數決定。

解題方法

資料快取容量為 $4\text{ KiB}=4096$ 位元組，每條快取行為 $16$ 位元組，因此快取行數為：

直接對映快取有 $256$ 條快取行，所以 Index 需要 $8$ 位元。每條快取行包含 $16$ 位元組，Block Offset 需要：

核心觀念

提高組相連度主要用來減少衝突失誤：多個仍在使用的快取區塊若映射到同一組，直接對映快取會互相替換；增加組相連度後，同一組可同時保留更多區塊。

但快取一開始是空的，每個首次被存取的區塊仍會發生強制失誤。若程式沒有衝突失誤可消除，提高組相連度就不會降低失誤數。

解題方法

每個 int 為 4 bytes，一條快取線為 16 bytes，因此一條線可容納 4 個整數。陣列長度為 300，佔用：

三個陣列連續排列，且每個陣列起點都位於快取線邊界。相對於 A 的起點，B 與 C 分別相差 75 條、150 條快取線。

P0 存取索引 0 到 3，P1 存取索引 4 到 7。每組索引恰好涵蓋各陣列的一條快取線：

核心觀念

一致性缺失（coherence miss）是快取區塊因其他處理器的寫入而遭到失效，之後再次存取時造成的缺失。False sharing（偽共享）則是兩個處理器修改同一快取行中的不同資料，因整行一致性而互相失效。

本題每個 int 為 4 bytes，快取行為 16 bytes，因此每行可容納：

解題方法

P0 執行 $i=0,1,2,3$；P1 執行 $i=4,5,6,7$。每個陣列的長度為 $300 \times 4=1200$ bytes，而 $1200$ 可被 16 整除，因此 A、B、C 三個陣列的起始位址都落在快取行邊界上。

兩個處理器存取的資料可按快取行整理如下：

核心觀念

Write-Invalidate Snooping Cache Coherence 中，處理器要寫入某條快取線時，必須取得該線的寫入權限，並使其他處理器快取中的副本失效。若某處理器的快取副本遭到失效，之後再次讀寫該線而未命中，便會產生 coherence miss。

False sharing（偽共享）是指：不同處理器使用不同的資料字，但這些資料字落在同一條快取線上，因而引發快取線失效與一致性流量。

解題方法

每個整數占 $4$ bytes，陣列長度為 $300$，因此每個陣列占：

三個陣列的起始位址為：

• $A$：$0xA000$
• $B$：$0xA000+0x4B0=0xA4B0$
• $C$：$0xA4B0+0x4B0=0xA960$

快取線大小為 $32$ bytes，也就是每條線可容納 $8$ 個整數。兩個處理器處理的索引範圍分別為：

• $P0$：$i=0,1,2,3$
• $P1$：$i=4,5,6,7$

檢查這兩段索引分別落在哪些快取線：

• 陣列 $A$：$A[0]$ 至 $A[7]$ 都在 $0xA000$ 至 $0xA01F$，因此兩個處理器讀取同一條線。讀取共享不會造成寫入失效；這些都是初始冷快取造成的 compulsory miss，並非 coherence miss。
• 陣列 $B$：$B[0]$ 至 $B[3]$ 位於 $0xA4A0$ 至 $0xA4BF$；$B[4]$ 至 $B[7]$ 位於 $0xA4C0$ 至 $0xA4DF$。

核心觀念

管線處理器的時脈週期由最慢階段的最長組合邏輯路徑決定。計算時不只要看資料通路，也要看控制訊號何時到達；多工器（Mux）必須等資料與選擇訊號都準備好，輸出才會穩定。

依題目提供的暫存器延遲，採用：

每條路徑都須計入起點暫存器讀取、途中邏輯，以及終點暫存器寫入的延遲。

解題方法

圖中 EX 階段設有 Forwarding Unit 與兩個轉送 Mux；第二運算元通過轉送 Mux 後，還須經過 ALUSrc Mux，才進入 ALU。因此，必須把轉送控制訊號經過這兩層 Mux 的路徑納入比較。

1. 計算 EX 階段的關鍵路徑

由管線暫存器輸出的暫存器編號送入 Forwarding Unit，產生轉送選擇訊號，接著依序通過第二運算元的轉送 Mux、ALUSrc Mux 與 ALU，最後寫入 EX/MEM 暫存器：

故此路徑延遲為：

核心觀念

五階段管線每個階段通常每個時脈週期處理一條指令。若 lw 後緊接著使用其載入目的暫存器的指令，會遇到 load-use hazard：載入資料在 lw 的 MEM 階段結束後才可供後續指令使用，因此需要停一個週期，並在 EX 階段插入氣泡（NOP）。

解題方法

圖中是 IF、ID、EX、MEM、WB 五階段管線，並包含 Hazard Detection Unit 與 Forwarding Unit。#1 將資料載入 x10，而 #2 立刻讀取 x10，因此 #2 必須停在 ID 一個週期；同時 EX 階段插入氣泡。

核心觀念

本題考資料相依與轉送控制。當指令在 EX 階段需要的來源暫存器值尚未寫回暫存器檔時，轉送單元會從較新的流水線暫存器直接提供結果。常見編碼為：

圖中是五階段流水線，依序為 IF、ID、EX、MEM、WB；資料路徑包含轉送單元。題目給的指令中，#4 sub x6, x2, x6 讀取 x2 與 x6，而前面的 #3 add x2, x2, x4 會寫入 x2。

解題方法

先排出相關指令的流水線時序。#2 add 緊接在載入 x10 的 #1 lw 之後，會遇到載入使用相依，需停等一個週期：

核心觀念

控制訊號由指令類型決定。sub 是 R-type 算術指令：從暫存器讀取兩個來源運算元，由 ALU 相減，並將結果寫回目的暫存器；它不存取資料記憶體。

解題方法

圖中是包含 IF、ID、EX、MEM、WB 五級的 RISC-V 管線資料路徑。題目程式的第 4 條指令是 sub x6, x2, x6，因此目的暫存器是 x6，運算結果來自 ALU。

核心觀念

本題考查處理器效能指標、快取替換策略，以及資料平行與同時多執行緒（SMT）。

處理器執行時間可表示為：

其中 CPI 是每條指令平均所需的時脈週期數。MIPS 是每秒執行的百萬條指令數，但它只反映指令吞吐量，不能單獨代表完成工作的速度。

解題方法

逐項檢查敘述是否符合定義與適用條件：

• 比較效能時，須看完成相同工作的實際時間，不能只看 MIPS。
• 快取替換策略的「最佳」須依存取序列與評估目標判定；LRU 並非所有情況下都最優。
• 向量指令能否帶來效益，取決於工作是否具有資料平行性。
• SMT 的重點是讓多個執行緒的指令共享處理器資源，填補單一執行緒未充分利用的執行資源。

選項分析

(1) 錯誤。 MIPS 較高不代表處理器完成程式較快。不同處理器可能使用不同指令集，執行相同工作所需的指令數也可能不同；即使指令集相同，程式與資料特性也會影響 CPI。因此，MIPS 不能脫離工作負載與實際執行時間來比較效能。