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

核心觀念

本題考查十進位數轉二進位、IEEE 754 單精準度浮點數編碼，以及機械常數（machine epsilon）的定義。

IEEE 754 單精準度共 32 位元，欄位配置為：

• 符號位元 $S$：1 位
• 指數欄位 $E$：8 位，使用超 127（excess-127）偏移
• 尾數欄位 $F$：23 位；正規化數的最高有效位元 $1$ 不儲存，稱為隱含的前導 $1$

解題方法

1. 轉換成二進位

先將整數與小數部分分開轉換。

整數部分：

$$161=128+32+1=2^7+2^5+2^0$$

因此 $161_{10}=10100001_2$。

小數部分以 $2$ 反覆相乘，取每次乘積的整數部分：

$$\begin{aligned} 0.875\times 2&=1.75 &&\Rightarrow 1\\ 0.75\times 2&=1.5 &&\Rightarrow 1\\ 0.5\times 2&=1.0 &&\Rightarrow 1 \end{aligned}$$

因此 $0.875_{10}=0.111_2$。原數為負數，故：

$$-161.875_{10}=-10100001.111_2$$

2. 編碼為 IEEE 754 單精準度

將二進位數正規化為 $1.x\times 2^e$：

$$-10100001.111_2=-1.0100001111_2\times 2^7$$

因此符號位元為 $S=1$。實際指數 $e=7$，加上偏移量 $127$：

$$E=e+127=7+127=134=10000110_2$$

核心觀念

FIT 是故障率單位，代表每 $10^9$ 小時發生一次故障的故障率。若故障率為 $\lambda$，則：

$$\lambda=\frac{\text{FIT}}{10^9}\quad(\text{次／小時}),\qquad \text{MTBF}=\frac{1}{\lambda}$$

系統可用性（availability）以可運作時間占總時間的比例表示。若平均修復時間為 MTTR，則：

$$A=\frac{\text{MTBF}}{\text{MTBF}+\text{MTTR}}$$

解題方法

（一）單一處理器的 MTBF

處理器 A 的故障率為：

$$\lambda_A=\frac{200}{10^9}=2\times10^{-7}\quad(\text{次／小時})$$

因此：

$$\text{MTBF}_A=\frac{1}{\lambda_A} =\frac{10^9}{200} =5\times10^6\text{ 小時}$$

換算成年：

$$\frac{5\times10^6}{24\times365}\approx570.8\text{ 年}$$

（二）系統可用性

修復時間為一天，即 $\text{MTTR}=24$ 小時。代入可用性公式：

核心觀念

本題考驗銀行家演算法（Banker’s algorithm）的安全性檢查。銀行家演算法以每個行程的最大需求量預先掌握資源需求，並只在確認系統仍處於安全狀態時，才核准資源請求。

各矩陣與向量的關係如下：

$$\text{Need}=\text{Max}-\text{Allocation}$$

對某一請求向量 $\text{Request}_i$，依序檢查：

1. $\text{Request}_i\leq \text{Need}_i$：請求不得超過該行程尚未滿足的最大需求。
2. $\text{Request}_i\leq \text{Available}$：目前可用資源必須足以立即提供請求。
3. 暫時分配資源，執行安全性檢查；若能找到所有行程的安全完成順序，才核准請求。

向量比較採逐項比較，例如 $(1,1,0,0)\leq(3,3,2,1)$ 表示四種設備各自都不超過。

解題方法

（一）計算需求矩陣

逐行以 Max 減去 Allocation，設備順序皆為 $ABCD$：

行程	Max $ABCD$	Allocation $ABCD$	Need $ABCD$
$P1$	$(4,2,1,2)$	$(2,0,0,1)$	$(2,2,1,1)$
$P2$	$(5,2,5,2)$	$(3,1,2,1)$	$(2,1,3,1)$
$P3$	$(2,3,1,6)$	$(2,1,0,3)$	$(0,2,1,3)$
$P4$	$(1,4,2,4)$	$(1,3,1,2)$	$(0,1,1,2)$
$P5$	$(3,6,6,5)$	$(1,4,3,2)$	$(2,2,3,3)$

例如，$P2$ 的需求為：

$$(5,2,5,2)-(3,1,2,1)=(2,1,3,1)$$

（二）$P2$ 請求 $(1,1,0,0)$

先比較請求與 $P2$ 的 Need：

$$(1,1,0,0)\leq(2,1,3,1)$$

成立。再比較與 Available：

$$(1,1,0,0)\leq(3,3,2,1)$$

也成立，因此可以進行暫時分配，並檢查安全性。

暫時分配後：

$$\text{Available}=(3,3,2,1)-(1,1,0,0)=(2,2,2,1)$$

$P2$ 的 Allocation 更新為 $(4,2,2,1)$，Need 更新為：

$$(2,1,3,1)-(1,1,0,0)=(1,0,3,1)$$

以暫時更新後的 Available 作為 Work，反覆尋找 Need 不大於 Work 的行程；行程完成後，將其 Allocation 加回 Work。

步驟	可完成行程	完成後 Work
初始	—	$(2,2,2,1)$
1	$P1$，Need $(2,2,1,1)$	$(4,2,2,2)$
2	$P2$，Need $(1,0,3,1)$	$(8,4,4,3)$
3	$P4$，Need $(0,1,1,2)$	$(9,7,5,5)$

核心觀念

作業系統的行程排程器（scheduler）依排程層級分為三種：

• 長程排班程式（long-term scheduler，工作排班程式）：從工作池中選取工作，載入記憶體並建立行程，使其進入就緒佇列。它控制系統接受多少工作，因此會影響多元程式規劃程度（degree of multiprogramming）。
• 中程排班程式（medium-term scheduler，交換排班程式）：暫時將部分行程換出主記憶體，之後再換入，以調節記憶體負載及行程數，也會影響多元程式規劃程度。
• 短程排班程式（short-term scheduler，CPU 排班程式）：從就緒佇列選出下一個行程，分派 CPU 執行。它執行頻率最高，負責決定 CPU 的使用順序。

解題方法

核心觀念

本題考查陣列在列導向（row-oriented）儲存下的記憶體存取順序，以及 LRU 分頁替換。列導向表示同一列的元素連續存放，因此 $A[i][j]$ 與 $A[i][j+1]$ 相鄰。

每頁可容納 $200$ 個整數，而陣列共有 $100\times100=10{,}000$ 個整數，所以需要：

$$\frac{10{,}000}{200}=50\text{ 頁}$$

系統只有兩個頁框。存取的資料不在目前頁框中時，產生一次分頁錯誤；若頁框已滿，LRU 會置換最近最久未使用的頁面。

解題方法

將陣列依列導向切分成頁面。每列有 $100$ 個整數，因此每頁可容納兩列：

• 第 1 頁：第 $0、1$ 列
• 第 2 頁：第 $2、3$ 列
• 依此類推
• 第 50 頁：第 $98、99$ 列

（a）外層走列、內層走欄

程式依序存取 $A[0][0],A[0][1],\ldots,A[0][99]$，再存取下一列。由於每頁含兩列，存取順序會完整讀完一頁後才進入下一頁。

每頁第一次被存取時產生一次分頁錯誤；同一頁的其餘存取都命中。共存取 50 頁，因此：

$$50\text{ 次分頁錯誤}$$