112 年 國立成功大學工程科學系碩士班丙組《計算機概論》

核心觀念

本題考查三種參數傳遞方式：

• Call by value（傳值）：將實際參數的值複製給形式參數，函式內修改形式參數不會影響原變數。
• Call by address（傳址）：將實際參數的記憶體位址傳入，形式參數透過該位址直接存取原變數。
• Call by reference（傳參照）：形式參數成為實際參數的別名，修改形式參數即修改原變數。

呼叫函式時，test[element] 會先依照當下的 element 求值。此時：

$$element=1$$

因此實際參數是：

$$test[element]=test[1]$$

初始狀態為：

變數	數值
test[1]	1
test[2]	2
element	1

---

解題方法

函式內容如下：

test[1] := 6;
element := 2;
x := x + 3;

關鍵在於判斷最後一行的 x 是否仍連結到 test[1]。

---

Call by address（傳址）

呼叫函式時，先取得 test[1] 的位址，傳給形式參數 x。因此 x 指向 test[1]。

執行過程：

1. test[1] := 6

   test[1] = 6
   

2. element := 2

   element = 2
   

   此時雖然 element 改變，但 x 儲存的是呼叫當下取得的 test[1] 位址，仍然指向 test[1]。

3. x := x + 3

   因為 x 指向 test[1]：

   $$test[1]=6+3=9$$

最終結果：

Mode	test[1]	test[2]	element
Call by address	9	2	2

---

Call by value（傳值）

呼叫時先計算：

$$test[element]=test[1]=1$$

因此形式參數 x 得到數值 $1$ 的複本，與 test[1] 已無直接連結。

執行過程：

1. test[1] := 6

   test[1] = 6
   

2. element := 2

   element = 2
   

3. x := x + 3

   x 是區域複本：

   $$x=1+3=4$$

   這不會影響 test[1]。

最終結果：

Mode	test[1]	test[2]	element

CPU（Central Processing Unit，中央處理器）是電腦的核心組件，負責執行指令和處理數據。其基本結構通常包含三個主要部分：

1. 算術邏輯單元 (Arithmetic Logic Unit, ALU)

   • 功能：ALU 是 CPU 中負責執行算術運算（如加、減、乘、除）和邏輯運算（如 AND, OR, NOT, XOR）的部分。當 CPU 接收到指令時，ALU 會根據指令的類型，對操作數執行相應的運算，並將結果暫存於暫存器中。它是 CPU 的「計算核心」。

2. 控制單元 (Control Unit, CU)

   • 功能：CU 負責協調和管理 CPU 內部以及 CPU 與電腦其他組件（如記憶體、輸入/輸出設備）之間的數據流和操作順序。它從記憶體中提取指令，對指令進行解碼，並產生控制信號，指導 ALU、暫存器和其他硬體執行相應的操作。CU 就像是 CPU 的「指揮官」。

3. 暫存器 (Registers)

   • 功能：暫存器是 CPU 內部極少量、速度極快的記憶體單元，用於暫時存放指令、數據、位址和中間計算結果。

Register（暫存器）、Main Memory（主記憶體）和 Disk Storage（硬碟儲存）是電腦系統中用於儲存數據的三種不同層級的儲存裝置，它們在速度、容量、成本和存取方式上存在顯著差異。

以下是它們之間的比較：

特性	Register (暫存器)	Main Memory (主記憶體)	Disk Storage (硬碟儲存)
位置	位於 CPU 內部	位於 CPU 外部，透過匯流排連接	位於 CPU 外部，透過 I/O 控制器連接
速度	極快 (CPU 時脈速度等級，通常為奈秒級)	快 (約幾十到幾百奈秒)	慢 (毫秒級，遠慢於主記憶體)
容量	極小 (通常幾十到幾百位元組，GB 級別非常罕見)	小到中等 (GB 級別，例如 8GB, 16GB, 32GB)	大 (TB 級別)

此題考查浮點數在二進位表示法中的精度問題，特別是 IEEE 754 格式。電腦內部使用二進位表示浮點數時，某些十進位小數可能無法精確表示，從而產生「捨入誤差」。

核心概念：
在二進位系統中，一個分數 $\frac{N}{2^k}$ 可以被精確表示。也就是說，只有當分母是 2 的冪次方時，該分數才能在二進位中精確表示。
例如：

• $0.5_{10} = \frac{1}{2} = 0.1_2$ (精確)
• $0.25_{10} = \frac{1}{4} = 0.01_2$ (精確)
• $0.75_{10} = \frac{3}{4} = 0.11_2$ (精確)
• $0.125_{10} = \frac{1}{8} = 0.001_2$ (精確)

反之，如果分母包含除了 2 以外的質因數，則在二進位中可能無法精確表示，會產生循環小數。

分析 $0.1_{10}$：
$0.1_{10}$ 可以寫成 $\frac{1}{10}$。
分母 10 的質因數是 2 和 5。由於存在質因數 5，所以 $0.1_{10}$ 在二進位中無法精確表示，會產生循環小數。
將 $0.1_{10}$ 轉換為二進位：
$0.1 \times 2 = 0.2 \implies 0$
$0.2 \times 2 = 0.4 \implies 0$
$0.4 \times 2 = 0.8 \implies 0$
$0.8 \times 2 = 1.6 \implies 1$ (取整數部分 1，小數部分 0.6)
$0.6 \times 2 = 1.2 \implies 1$ (取整數部分 1，小數部分 0.2)
$0.2 \times 2 = 0.4 \implies 0$ (開始循環)
因此，$0.1_{10} = 0.0001100110011..._2$。這是一個無限循環的二進位小數，在 IEEE 754 格式中，由於儲存空間有限，會被截斷或捨入，從而產生誤差。

分析 $0.625_{10}$：
$0.625_{10}$ 可以寫成 $\frac{625}{1000}$。
簡化分數：$\frac{625}{1000} = \frac{125}{200} = \frac{25}{40} = \frac{5}{8}$。
分母是 8，而 $8 = 2^3$。由於分母是 2 的冪次方，所以 $0.625_{10}$ 在二進位中可以被精確表示。

此題考察作業系統中的死鎖 (Deadlock) 問題。死鎖是指在多個行程（或執行緒）之間，由於互相等待對方釋放資源而導致所有行程都無法繼續執行，形成僵局。

核心概念：
死鎖的發生需要同時滿足以下四個必要條件（Coffman conditions）：

1. 互斥 (Mutual Exclusion)：資源一次只能被一個行程使用。
2. 佔有並等待 (Hold and Wait)：一個行程至少佔有一個資源，並等待其他行程釋放它所需要的資源。
3. 非剝奪 (No Preemption)：資源不能被強制剝奪，只能由佔有它的行程主動釋放。
4. 循環等待 (Circular Wait)：存在一個行程鏈，其中每個行程都在等待鏈中下一個行程所佔有的資源。

5. (a) What is a deadlock? How to represent a deadlock?

• 死鎖的定義：死鎖 (Deadlock) 是指在多個競爭資源的行程之間，由於互相等待對方的資源而導致的一種僵局狀態。在這種狀態下，沒有任何一個行程能夠繼續執行，系統也無法恢復，除非外部干預（如終止部分行程）。

• 死鎖的表示：死鎖通常可以用「資源分配圖 (Resource Allocation Graph, RAG)」來表示。資源分配圖是一個有向圖，其中：

  • 節點：包含兩種節點：
    • 行程節點 (Process nodes)：用圓圈表示，例如 $P_1, P_2, \dots$。
    • 資源節點 (Resource nodes)：用方塊表示，例如 $R_1, R_2, \dots$。每個資源類型可以有多個實例，用方塊內的點表示。
  • 邊：包含兩種邊：
    • 請求邊 (Request edge)：從行程節點指向資源節點，表示該行程請求該資源，例如 $P_i \rightarrow R_j$。
    • 分配邊 (Assignment edge)：從資源節點指向行程節點，表示該資源的一個實例已被該行程佔有，例如 $R_j \rightarrow P_i$。

  死鎖的判斷：

  • 如果資源的每個類型只有一個實例，那麼當資源分配圖中出現循環時，就表示存在死鎖。
  • 如果資源的類型有多個實例，那麼僅有循環並不能保證死鎖。需要使用更複雜的銀行家演算法 (Banker's Algorithm) 或其變體來判斷。

5. (b) How to deteck a deadlock? And if a deadlock is detected, how to resolve the deadlock?

• 死鎖檢測 (Deadlock Detection)：
  • 方法：作業系統可以週期性地執行死鎖檢測演算法。最常見的方法是使用類似於銀行家演算法的等待圖 (Wait-for Graph, WFG) 或資源分配圖。
  • 等待圖：如果每個資源類型只有一個實例，則可以構建等待圖。等待圖是一個有向圖，其中節點是行程。如果行程 $P_i$ 正在等待行程 $P_j$ 所佔有的資源，則在等待圖中繪製一條從 $P_i$ 到 $P_j$ 的邊 ($P_i \rightarrow P_j$)。
  • 檢測條件：等待圖中出現循環，則表示存在死鎖。
  • 資源分配圖檢測 (適用於多實例資源)：
    1. 從一個沒有入邊的行程節點開始，或者從一個沒有被任何行程佔有且所有請求都能被滿足的資源節點開始。
    2. 如果能夠找到一個行程 $P_i$ 使得其所有請求的資源都能被系統滿足（即其請求邊指向的資源節點，其可用實例加上其他行程釋放的資源足夠），則可以假設 $P_i$ 執行完畢並釋放其所有資源。
    3. 重複此過程，直到所有行程都能被執行完畢。
    4. 如果所有行程都能執行完畢，則系統沒有死鎖。如果存在無法執行完畢的行程，則這些行程處於死鎖狀態。

此題要求追蹤四段 Python 程式碼片段，找出變數 count 的最終值。這主要考驗對迴圈 (for, while) 和 range() 函數的理解。

核心概念：

• range(n) 產生從 0 到 $n-1$ 的整數序列。
• range(start, stop) 產生從 start 到 stop-1 的整數序列。
• range(start, stop, step) 產生從 start 到 stop-1，以 step 為間隔的整數序列。
• 嵌套迴圈會將內層迴圈的迭代次數累加到外層迴圈的每一次迭代中。

---

6.1 (4%)

count = 0
for i in range(5):
  for j in range(5):
    count += 1
print(count)

• 外層迴圈 for i in range(5)：i 會依序取值 $0, 1, 2, 3, 4$。共迭代 5 次。
• 內層迴圈 for j in range(5)：對於外層迴圈的每一次迭代，內層迴圈的 j 都會依序取值 $0, 1, 2, 3, 4$。這意味著內層迴圈會執行 5 次。
• count += 1：這行語句位於內層迴圈內部，所以它會被執行的總次數是：(外層迴圈迭代次數) × (內層迴圈迭代次數) = $5 \times 5 = 25$ 次。
• 初始值：count 的初始值是 0。
• 最終值：$0 + 25 = 25$。

【答案】25

---

6.2 (4%)

count = 0
for i in range(5):
  for j in range(i):
    count += 1
print(count)

• 外層迴圈 for i in range(5)：i 的值為 $0, 1, 2, 3, 4$。
• 內層迴圈 for j in range(i)：內層迴圈的迭代次數取決於外層迴圈變數 i 的值。
  • 當 $i=0$ 時，range(0) 產生空序列，內層迴圈不執行 (0 次)。
  • 當 $i=1$ 時，range(1) 產生序列 0，內層迴圈執行 1 次。
  • 當 $i=2$ 時，range(2) 產生序列 0, 1，內層迴圈執行 2 次。
  • 當 $i=3$ 時，range(3) 產生序列 0, 1, 2，內層迴圈執行 3 次。
  • 當 $i=4$ 時，range(4) 產生序列 0, 1, 2, 3，內層迴圈執行 4 次。
• count += 1：這行語句執行的總次數是內層迴圈執行次數的總和：$0 + 1 + 2 + 3 + 4 = 10$ 次。
• 初始值：count 的初始值是 0。
• 最終值：$0 + 10 = 10$。
  這個總和是等差數列求和：$\frac{n(n+1)}{2}$，這裡 $n=4$ (從 0 到 4 總共 5 個數，但 range(i) 的上限是 i，所以實際上是求 $0+1+2+3+4$ 的和，這裡的 i 最大到 4，所以 range(i) 的最大值是 range(4)，即 $0,1,2,3$ 共 4 個數。所以應該是 $0+1+2+3+4=10$。
  更精確地說，當 $i=0$，迴圈執行 0 次。當 $i=1$，迴圈執行 1 次。

此題考察對 Disk Cache (硬碟快取) 和 RAM Disk (記憶體磁碟) 這兩種提升 I/O 效能技術的理解，以及它們之間的主要區別。

1. Disk Cache (硬碟快取)

• 技術原理：硬碟快取是一種利用主記憶體（RAM）的一部分空間來暫存硬碟上經常被存取或即將被寫入的數據的技術。當 CPU 需要讀取數據時，它會先檢查硬碟快取。如果數據在快取中（稱為「快取命中，cache hit」），則直接從 RAM 中讀取，速度遠快於直接從硬碟讀取。如果數據不在快取中（稱為「快取未命中，cache miss」），則需要從硬碟讀取，同時將這部分數據複製到快取中，以便未來存取。對於寫入操作，數據可以先寫入快取，然後由快取控制器在適當的時機（如系統負載較低時）批量寫入硬碟，這稱為「延遲寫入 (write-back)」或「延遲讀取 (write-through)」。

• 目的：主要目的是減少 CPU 存取硬碟的延遲，提高 I/O 效能。

• 實作方式：

  • 硬體快取 (Hardware Cache)：集成在硬碟控制器或硬碟本身中的 RAM 晶片。
  • 軟體快取 (Software Cache)：由作業系統管理，利用一部分主記憶體作為快取。例如 Windows 的 SuperFetch/Sysmain，Linux 的 page cache。

2. RAM Disk (記憶體磁碟)

• 技術原理：RAM Disk（或稱 Virtual Disk, RAM Drive）是將主記憶體（RAM）的一部分空間模擬成一個獨立的磁碟分割區或磁碟機。這個模擬出來的磁碟機的讀寫速度非常快，因為它是直接在 RAM 中進行操作，其速度僅受限於 RAM 的存取速度和 CPU 的處理能力。

• 目的：創建一個讀寫速度極快的儲存空間，用於存放對速度要求極高的應用程式、臨時文件（如瀏覽器快取、影片編輯的臨時檔）、遊戲載入等。

• 實作方式：通常需要第三方軟體或作業系統提供的功能來創建和管理。創建後，它會出現在檔案系統中，使用者可以像操作普通磁碟機一樣操作它。

3. 主要區別 (Major Difference)

| 特性 | Disk Cache (硬碟快取) | RAM Disk (記憶體磁碟) |