110 年 國立中正大學資訊工程學系碩士班甲組《計算機系統》

核心觀念

本題比較行動裝置與筆記型、桌上型電腦的資源限制與功能差異，重點包括電池供電、感測功能、儲存容量及處理器核心數。判斷時要分清楚「行動裝置容量通常較小」與「容量差距正在縮小」是兩種不同的主張；前者描述現況，後者描述趨勢。

解題方法

逐項檢查敘述是否符合一般行動裝置的特性。行動裝置仰賴電池，常有筆電或桌機沒有內建的感測與通訊功能；在題目的典型比較中，行動裝置的儲存容量仍遠小於筆電，因此不能據此認定兩者的容量差距正在縮小。

選項分析

• (A) 正確。 行動裝置主要使用電池供電，處理器、螢幕、無線通訊等元件的耗電會影響續航力，因此設計時必須重視功耗。

核心觀念

檔案鎖定用來協調多個行程對同一檔案的存取，避免同時操作造成資料不一致。獨佔鎖（exclusive lock）代表取得鎖的行程獨占該檔案的使用權；其他遵守鎖定規則的行程不能同時讀取或寫入。相對地，共享鎖通常允許多個行程同時讀取，但會阻擋寫入。

解題方法

判斷關鍵在於「獨佔」：同一時間只能有一個行程取得該檔案的存取權，因此選出描述「只有一個行程能使用檔案」的選項。

選項分析

核心觀念

統一虛擬記憶體（Unified Virtual Memory）讓檔案資料與程序的虛擬記憶體頁面共用同一套快取機制。作業系統以**頁面快取（page cache）**將檔案內容載入記憶體；程序讀取檔案時，這些資料也能以記憶體頁面的形式使用，減少重複存放與資料複製。

解題方法

題目問的是：統一虛擬記憶體用什麼機制，同時快取程序頁面與檔案資料？關鍵是「統一」代表兩類資料共用同一套頁面快取，因此答案是 page caching。

選項分析

• (A) disk block caching：錯誤。 磁碟區塊快取以磁碟區塊為單位快取資料，著重於區塊層級，未指出程序頁面與檔案資料共用同一套頁面快取。

核心觀念

處理器與 I/O 裝置溝通有兩種方式：

• 記憶體對映 I/O（memory-mapped I/O）：把裝置的控制暫存器、資料暫存器配置在處理器的位址空間中的一段位址上，CPU 用一般的 load／store 指令（標準指令）讀寫這些位址，就等於讀寫裝置。
• 隔離式 I/O（port-mapped / isolated I/O）：裝置有獨立的 I/O 位址空間，必須用特殊的 I/O 指令（如 x86 的 in、out）存取。

選項分析

• (A) 錯誤。 記憶體對映 I/O 使用的是位址空間中保留給裝置的位址，並不是佔用主記憶體（RAM）本身來與裝置溝通；那些位址對應到裝置暫存器，而不是記憶體晶片。

核心觀念

磁碟存取時間主要包含三部分：

其中，尋道時間 $T_{\text{seek}}$ 是讀寫頭移至目標磁軌所需的時間；旋轉延遲 $T_{\text{rotational}}$ 是等待目標磁區轉到讀寫頭下方所需的時間；傳輸時間 $T_{\text{transfer}}$ 則是實際傳送資料所需的時間。

傳統作業系統磁碟排程常以請求間的尋道距離為依據，嘗試減少讀寫頭移動。要精確安排旋轉延遲，必須知道目標磁區在磁碟上的實際位置與當前旋轉狀態；但現代磁碟會將作業系統看到的邏輯區塊位址（LBA）轉換成實體位置，並可能進行內部重映射，因此作業系統通常無法直接取得這些資訊。

解題方法

題目問的是「為什麼排程演算法只考慮尋道距離」。判斷關鍵在於：作業系統是否能取得足夠資訊來預測旋轉延遲。

核心觀念

本題考查磁碟裝置的格式化、分割區與磁碟區之間的關係。

• 低階格式化由製造商或相關工具建立磁碟的實體磁區結構。
• 邏輯格式化由作業系統建立檔案系統所需的資料結構，例如目錄與空間管理資訊。
• 磁碟可切分成多個分割區。分割區若建立了檔案系統，就稱為磁碟區（volume）；也可以保留為未格式化或供其他用途。

解題方法

逐項對照「裝置製造商負責實體格式化」與「作業系統負責建立檔案系統」的分工。若選項把檔案系統資料結構歸給裝置製造商，即與格式化流程不符。

選項分析

核心觀念

Linux 核心的 spinlock（依 Silberschatz《Operating System Concepts》對 Linux 同步機制的說明）：

• 在**對稱多處理（SMP）**機器上，spinlock 是基本的鎖定機制；
• 在單處理器機器上，自旋等待沒有意義（持有鎖的執行緒不可能同時在另一顆 CPU 上執行並釋放鎖），所以 spinlock 不適用，改以**停用／啟用核心搶先（preempt_disable / preempt_enable）**取代；
• Linux spinlock 不可遞迴取得；
• 核心設計成只在短時間內持有 spinlock，需要長時間持有時改用 semaphore 或 mutex。

核心觀念

POSIX 條件變數用來讓執行緒等待某個條件成立。條件本身通常由共享變數表示，並由互斥鎖保護。

呼叫 pthread_cond_wait(&cond, &mutex) 前，呼叫執行緒必須已持有 mutex。此函式會原子地釋放互斥鎖並進入等待；被喚醒後，函式會先重新取得該鎖，再返回。因此，等待執行緒返回時仍持有互斥鎖。

pthread_cond_signal(&cond) 則不要求呼叫端持有關聯的互斥鎖，也不會自動解鎖互斥鎖。

解題方法

分別判斷兩件事：

1. 呼叫 pthread_cond_wait() 前是否必須持有互斥鎖？ 必須，否則無法正確保護共享條件，也不符合 POSIX 條件變數的使用要求。
2. 呼叫 pthread_cond_signal() 後是否必須解鎖互斥鎖？ 條件變數介面沒有這項要求。訊號執行緒可以不持有該鎖就呼叫 pthread_cond_signal()；若它先前自行取得了鎖，仍須依一般互斥鎖規則在適當時機釋放。

核心觀念

臨界區問題的正確解法通常必須滿足三項要求：

• 互斥（mutual exclusion）：同一時間最多只有一個程序在臨界區內。
• 進展（progress）：若臨界區目前沒有人，而有程序想進入，選擇下一個進入者的決定不能無限期延遲；只有想進入臨界區的程序能影響這項決定。
• 有限等待（bounded waiting）：程序提出進入臨界區的請求後，其他程序在它獲准前進入臨界區的次數有上限。

其中，進展關注「有程序想進入時，能否在有限時間內選出進入者」；有限等待則進一步保證「特定請求不會一直被其他程序超過」。因此，有限等待比進展提供更強的保障。

解題方法

判斷各項性質之間的蘊含關係：

1. 若滿足有限等待，請求進入的程序不會被其他程序無限次超過，因此等待中的程序終將有機會進入；這也保證了進展。
2. 若滿足進展，當臨界區空閒且有程序請求進入時，不能無限期不讓任何程序進入，因此不會發生死結。
3. 反方向不一定成立：沒有死結只表示不會所有相關程序都卡住，不能保證請求一定會獲准；進展也不限制某個程序被其他程序超過的次數，因此不能保證有限等待。

可記為：

核心觀念

三種執行緒函式庫的資料共享（Silberschatz《Operating System Concepts》）：

• Pthreads、Win32：在函式外宣告的全域資料，自然由同一行程的所有執行緒共享。
• Java：純物件導向語言，沒有全域資料的概念；兩個以上的執行緒要共享資料，必須明確把共享物件的參考傳給各個執行緒，共享不是自動提供的。

選項分析

• (A) 錯誤（本題答案）。 Java 執行緒的資料共享不是自動提供的；必須把同一個物件的參考交給需要共享的執行緒（例如在建構 Runnable 物件時傳入共享物件）。
• **(B) 正確。

核心觀念

率單調排程（RMS）是固定優先權排程：週期越短，優先權越高。因此本題優先順序為 $P1>P2>P3$。題目給定每個工作的截止期限等於週期，且所有工作在時間 $0$ 同時就緒。

可用響應時間分析檢查每個工作的最壞完成時間。對低優先權處理程序 $P_i$，響應時間反覆計算：

其中 $C_i$ 是處理時間，$T_j$ 是較高優先權處理程序的週期，$hp(i)$ 是所有優先權高於 $P_i$ 的處理程序集合。若計算收斂後 $R_i\leq T_i$，該處理程序便能在截止期限前完成。

解題方法

依 RMS 排序為 $P1>P2>P3$，逐一計算響應時間。

對 $P1$，沒有更高優先權處理程序干擾：

對 $P2$，只有 $P1$ 會造成干擾。從 $R_2^{(0)}=30$ 開始迭代：

再代入 $50$：

響應時間收斂為 $R_2=50\leq 100$。

對 $P3$，較高優先權處理程序為 $P1$ 和 $P2$。從 $R_3^{(0)}=90$ 開始迭代：

核心觀念

本題考查單一處理器上的最早期限優先排程（EDF）可排程性。每個工作的相對期限等於其週期，屬於「隱含期限」工作集合。

對可搶先、獨立且週期性工作的單一處理器，在此條件下，EDF 可排程的充要條件是總處理器利用率不超過 $1$：

其中 $C_i$ 是處理時間，$T_i$ 是週期。$U$ 表示處理器長期必須用於執行工作的比例。

解題方法

代入三個工作的處理時間與週期：

因此，工作集合恰好使用處理器的全部容量，沒有空閒時間；但因為 $U=1$ 仍符合 EDF 的可排程條件，所以所有工作都能在期限前完成。

也可用超週期 $H=\operatorname{lcm}(50,100,300)=300$ 驗證。以下是一種 EDF 執行排程，區間右端點即為各段執行結束時間：

核心觀念

多層頁表的層數取決於虛擬頁號需要多少位元，以及每一層頁表可用多少位元來索引。頁面大小決定頁內位移位數；每個頁表項目占用的大小則決定一個頁表頁面能容納多少個項目。

解題方法

頁面大小為 $32\text{ KB}=2^{15}$ 位元組，且系統以位元組定址，因此頁內位移占 $15$ 位元。虛擬位址為 $64$ 位元，虛擬頁號便占：

每個頁表項目為 $4$ 位元組，一個頁面可容納的頁表項目數為：

核心觀念

TLB 命中時，處理器可直接取得頁面到實體框架的對應，只需一次實際的記憶體存取。TLB 未命中時，必須先逐層查詢頁表取得位址轉換，再存取目標資料。

解題方法

頁面大小為 $32\text{ KB}=2^{15}$ bytes，因此位移欄位占 $15$ 位元。虛擬頁號占：

每個頁表項目為 $4$ bytes，一個頁表頁面可容納：

個頁表項目，因此每層可索引 $13$ 位元。$49$ 位元的虛擬頁號需要 $4$ 層頁表，例如索引位元數分配為 $13+13+13+10=49$。

核心觀念

本題考 **Banker’s algorithm（銀行家演算法）**的安全性檢查。對每個行程計算尚需資源量：

若某行程的 Need 每種資源都不超過目前可用量，就能先完成該行程；完成後，它會釋放已分配的資源，使其他行程有機會完成。若所有行程都能依序完成，該順序就是安全序列。

解題方法

圖中表格的 Available 為 $(A,B,C,D)=(0,1,1,1)$。各行程的 Allocation 與 Max 如題表所示；計算 Max 減 Allocation 後，Need 為：

從可用量 $(0,1,1,1)$ 開始，P3 的 Need $(0,1,1,1)$ 不超過可用量，因此 P3 可以先完成。完成後釋放其 Allocation $(2,1,0,1)$，可用量更新為：

核心觀念

inode 透過不同層級的索引區塊，記錄檔案資料區塊的位置：

• 直接指標：每個指標直接指向一個資料區塊。
• 單重間接指標：指向一個索引區塊，該索引區塊內的指標都指向資料區塊。
• 雙重間接指標：經過兩層索引區塊後，指向資料區塊。
• 三重間接指標：經過三層索引區塊後，指向資料區塊。

每個索引區塊可存放的指標數為：

計算檔案大小時，統計這些指標最多能對應到多少個資料區塊，再乘上每個資料區塊的大小。

解題方法

題目給定區塊大小為 $4\text{ KB}=4096$ bytes，區塊指標大小為 $8$ bytes。因此，一個索引區塊可容納：

各層級可指向的資料區塊數如下：

核心觀念

時序電路由組合邏輯與 D 型正反器組成。D 型正反器在時脈觸發時，將 $D$ 端的值存入狀態，因此下一狀態函數為 $Q^{+}=D$；輸出函數則由輸出端所連接的組合邏輯決定。

解題方法

圖中有兩個反相器、一個 NAND 閘與一個 D 型正反器。令輸入為 $x$、正反器目前狀態為 $q$：輸入 $x$ 經一個反相器後接到 $D$ 端；$x$ 與回授的目前狀態 $q$ 接到 NAND 閘，而 NAND 輸出再經另一個反相器形成輸出 $y$。

因此，下一狀態由 $D$ 端訊號決定：

核心觀念

這題考同步循序電路的狀態轉移與輸出函數。D 型正反器在時脈觸發時，將 $D$ 端的值存入狀態，因此下一狀態為 $Q^{+}=D$；輸出則由當下的輸入與現態決定。

解題方法

圖中輸入 $x$ 分成兩路：一路經反相器接到正反器的 $D$ 端；另一路與回授的現態 $Q$ 接至 NAND 閘，NAND 輸出再經反相器形成輸出 $y$。因此：

每一個週期先用該週期開始時的現態和輸入計算輸出，再在時脈觸發後更新狀態。初始現態為 $Q=0$：

核心觀念

同步電路的最高時脈頻率由暫存器到暫存器的最長組合路徑決定。若路徑存在，時脈週期至少要滿足：

其中 $t_{\text{cq}}$ 是時脈至輸出延遲，$t_{\text{comb,max}}$ 是組合邏輯最大延遲，$t_{\text{setup}}$ 是建立時間。

解題方法

圖中 D 端接的是輸入訊號經一個反相器後的 next_state；Q 端的 present_state 則接至 NAND 閘，NAND 輸出再經另一個反相器形成電路輸出。依照圖示，Q 到輸出有組合邏輯，但這條路徑沒有接回 D 端；D 端的路徑則由外部輸入開始。

因此，圖中沒有可用來套用上述公式的暫存器到暫存器路徑。題目也沒有提供輸入相對於時脈的到達時間，或輸出端的時序限制，所以無法從所給資料算出此電路的最高操作頻率。題目提供的保持時間也無法補足這項缺失；

核心觀念

本題比較兩種揮發性記憶體的實作方式與硬體成本：

• SRAM（靜態隨機存取記憶體）：每個位元通常以 6 個電晶體組成鎖存器儲存資料；只要供電，資料便能維持，不需定期刷新。
• DRAM（動態隨機存取記憶體）：每個位元通常以 1 個電晶體搭配 1 個電容儲存電荷；電荷會逐漸漏失，因此必須定期刷新。

解題方法

比較時，先看每個位元所需的儲存元件數量，再推論晶片面積、成本與存取速度。SRAM 的單位元電路較複雜，占用面積較大，但讀寫不必等待刷新，存取速度較快；DRAM 的單位元電路較簡單，可在相同晶片面積中放入更多位元，成本較低，但刷新與讀取程序使存取較慢。

核心觀念

比較兩台機器的效能，不能只看時脈頻率，還要同時考慮每條指令平均需要的時脈週期數（CPI）。對相同的指令數 $I$：

雙埠記憶體可在同一週期內處理指令擷取與資料存取；單埠記憶體同一時間只能處理一項存取，因此載入指令若與指令擷取衝突，就需要停等。

解題方法

假設兩種機器都採用單一記憶體供指令擷取與資料存取，且機器 B 的每次載入衝突會多花一個週期。

機器 A 使用雙埠記憶體，不需因載入指令增加停等週期，因此實際 CPI 為 $1$。

機器 B 的載入指令占指令總數 $40\%$。每條載入指令平均增加一個停等週期，所以：

令機器 A 的時脈頻率為 $f$，則機器 B 的時脈頻率為 $1.05f$。比較每秒可執行的指令數：

核心觀念

此題考查 C 語言條件運算子 ?: 如何轉成 MIPS 的條件分支。原式

表示：若 $i=j$，令 $f=g+h$；否則令 $f=g-h$。MIPS 可用 beq 比較兩個暫存器，並依比較結果跳到對應的指令區段。

解題方法

假設各變數的整數值已存入下列暫存器：

先用 beq 判斷 $i$ 是否等於 $j

核心觀念

IEEE 754 binary16（半精度）由 16 位元組成：

對於非零正規化數，數值為

其中 5 位元指數的偏移量為

尾數欄位只存小數點後的位元；正規化數的小數點前首位 $1$ 不另外儲存。

解題方法

先將絕對值改寫成二進位正規化形式，再依序填入符號位元、偏移後的指數，以及尾數欄位。

$-5.0$

核心觀念

快取頻寬（cache bandwidth）是快取在單位時間內能提供的資料量，可概念化為：

題目提到的命中時間（hit time）、失誤率（miss rate）與失誤代價（miss penalty），分別描述命中時的存取時間、存取未命中快取的機率，以及未命中後取回資料所需的額外時間。這題聚焦在提高資料傳輸速率；降低命中時間或失誤率不等於直接增加快取頻寬。

解題方法

從「每次能傳多少資料」與「能否同時進行多筆傳輸」兩個方向，各提出一種快取最佳化方式：