108 年 國立中央大學資訊管理學系碩士班乙組《計算機概論》

這是一題基本名詞解釋題，主要在測試考生對計算機網路、通訊系統及作業系統基礎概念的熟悉度。

(a) DSSS (Direct Sequence Spread Spectrum)
直序展頻 (Direct Sequence Spread Spectrum, DSSS) 是一種展頻通訊技術，它將原始訊號的每一位元資訊擴展成一連串的偽隨機雜訊 (Pseudo-Random Noise, PN) 碼序列，然後將此序列與原始訊號進行乘法運算，以擴展訊號的頻寬。這樣做的好處是：

1. 抗干擾能力強：由於訊號擴展到較大的頻寬，使得單一頻率的干擾對訊號的影響相對減小。
2. 安全性高：接收端必須知道相同的 PN 碼序列才能將訊號解展回原始訊號，增加了竊聽的難度。
3. 多重使用者存取：不同的使用者可以使用不同的 PN 碼序列，在相同的頻寬內進行通訊，實現碼分多址 (CDMA)。
   常見應用於 Wi-Fi (802.11b) 和藍牙等無線通訊系統。

(b) PCM (Pulse-Code Modulation)
脈碼調變 (Pulse-Code Modulation, PCM) 是一種將類比訊號數位化的基本方法。其過程包含三個主要步驟：

1. 取樣 (Sampling)：在固定的時間間隔對類比訊號進行取樣，將連續的訊號轉換成一系列離散的幅度值。根據奈奎斯特取樣定理 (Nyquist sampling theorem)，取樣頻率必須至少是訊號最高頻率的兩倍，才能無失真地重建原始訊號。
2. 量化 (Quantization)：將取樣得到的離散幅度值映射到預先定義的離散電平。由於量化過程會將無限多個類比值壓縮到有限多個數位值，因此會引入量化誤差 (quantization error)，這是 PCM 系統中主要的訊號失真來源。量化級數越多，誤差越小，但所需的位元數也越多。
3. 編碼 (Encoding)：將量化後的離散值轉換成二進位碼。每個量化級數都對應一個特定的二進位碼。
   PCM 是數位通訊中最常見的類比訊號數位化技術，廣泛應用於電話語音、音訊 CD、數位電視廣播等。

(c) VLAN (Virtual Local Area Network)
虛擬區域網路 (Virtual Local Area Network, VLAN) 是一種邏輯上的網路分割技術，它允許網路管理員將一個實體區域網路 (LAN) 劃分成多個獨立的邏輯網路。VLAN 的主要優點包括：

1. 提高網路效能：透過將大型網路分割成較小的廣播網域 (broadcast domain)，可以減少廣播封包的數量，降低網路壅塞，提高頻寬利用率。
2. 增強安全性：不同 VLAN 的成員之間預設無法直接通訊，必須透過路由器或三層交換器才能進行跨 VLAN 的通訊，這提供了更細粒度的存取控制。

這題考的是關聯式資料庫中主鍵 (Primary Key) 的概念，以及兩種常用生成方式：自動遞增 (Auto Increment) 和通用唯一識別碼 (UUID) 的優缺點。

主鍵 (Primary Key) 的作用是唯一識別表格中的每一筆記錄，確保資料的完整性和唯一性。

1. Auto Increment (自動遞增)

   • 原理：當新增一筆記錄時，資料庫系統會自動為該欄位分配一個比前一筆記錄的值大一的整數。通常從 1 開始，也可以設定起始值和遞增步長。
   • 優點：
     • 簡單易用：由資料庫自動管理，開發者無需額外操作。
     • 效能高：整數比較和索引查找通常非常快速。
     • 空間效率高：整數類型佔用的儲存空間較小。
     • 自然排序：記錄的插入順序與主鍵值順序一致，有助於某些查詢的排序。
   • 缺點：
     • 集中式風險：在分散式系統中，要保證全局唯一性會比較困難，可能需要額外的機制來協調。
     • 可預測性：主鍵值是連續且可預測的，可能帶來安全隱患（例如，攻擊者可以猜測到下一個 ID，進而推斷出資料數量）。
     • 資料合併問題：當需要合併來自不同資料庫的資料時，可能會發生主鍵衝突。
     • 離線操作限制：如果應用程式需要離線產生記錄，則無法直接使用資料庫的 auto increment 功能。

2. UUID (Universally Unique Identifier)

   • 原理：UUID 是一種 128 位元的識別碼，理論上可以確保在空間和時間上都是唯一的。

這題考的是網路安全中常見的 SQL Injection 漏洞。

SQL Injection (SQL 注入) 是一種常見的網路攻擊技術。攻擊者利用應用程式在處理使用者輸入時的疏忽，將惡意的 SQL 語句片段注入到原本預期是普通資料的輸入欄位中。當應用程式沒有對使用者輸入進行充分的驗證或過濾，並直接將其拼接到 SQL 查詢語句時，這些惡意的 SQL 語句就會被資料庫伺服器執行。

攻擊者可以透過 SQL Injection 來達成多種目的，例如：

• 竊取敏感資料：讀取、複製或下載資料庫中的機密資訊（如使用者帳號密碼、信用卡號碼等）。

承接上一題，這題是關於如何防範 SQL Injection 攻擊。防範 SQL Injection 的核心在於確保使用者輸入不會被誤解為 SQL 指令。以下列舉並說明三個主要的方法：

1. 參數化查詢 (Parameterized Queries) / 預備陳述式 (Prepared Statements)

   • 說明：這是最推薦也最有效的防範方法。參數化查詢會將 SQL 指令的結構與要傳入的資料分開處理。在執行 SQL 語句之前，SQL 語句的結構（包含 SQL 關鍵字、表格名稱等）會先被傳送到資料庫進行解析和編譯，然後再將使用者輸入的值作為參數單獨傳送。資料庫會將這些參數值視為純粹的資料，而不是 SQL 指令的一部分，因此即使輸入包含 SQL 語法，也不會被執行。
   • 範例：
     假設原本的危險寫法是：SELECT * FROM users WHERE username = ' + userInput + ' AND password = ' + passwordInput + '
     使用參數化查詢後，類似於：
     PREPARE stmt FROM 'SELECT * FROM users WHERE username = ? AND password = ?';
EXECUTE stmt USING userInput, passwordInput;
     或者在某些語言中有類似 db.execute("SELECT * FROM users WHERE username = ? AND password = ?", [userInput, passwordInput]) 的寫法。

2. 輸入驗證 (Input Validation) 與輸入過濾 (Input Filtering)

這題考的是物件導向程式設計中的型別轉換 (Type Casting)，特別是向下轉型 (Downcasting) 的使用時機與潛在問題。

When should “downcast" be used?
向下轉型 (Downcasting) 應該在以下情況使用：

1. 當你確定一個物件的實際型別是某個子類別，但目前它被儲存在一個父類別型別的變數中時。
   例如，假設我們有一個父類別 Animal 和一個子類別 Dog。如果我們有一個 Animal 型別的變數 myAnimal，並且我們知道它實際上指向一個 Dog 物件，我們就可以將 myAnimal 向下轉型為 Dog 型別，以便存取 Dog 類別特有的方法或屬性。

   // 假設 Animal 是父類別, Dog 是子類別
   Animal myAnimal = new Dog(); // 向上轉型 (Upcasting), 這是隱式的
   // ... 程式碼執行到某處, 我們確定 myAnimal 實際上指向的是一個 Dog 物件 ...
   Dog myDog = (Dog) myAnimal; // 向下轉型 (Downcasting)
   myDog.bark(); // 現在可以呼叫 Dog 類別特有的 bark() 方法
   

2. 在處理集合 (Collections) 或泛型 (Generics) 時，有時需要將物件轉回其原始的具體型別。
   雖然現代語言的泛型可以減少這種情況，但在某些舊的 API 或沒有使用泛型的集合中，物件可能被儲存為通用型別（如 Object），需要向下轉型才能使用。

And why it may cause run-time exception if not used properly?
向下轉型可能在執行時期 (run-time) 產生例外 (exception) 的原因如下：

1. 實際型別不符 (Type Mismatch)：
   最常見的原因是，當你嘗試向下轉型時，變數實際指向的物件並不是你預期的那個子類別，而是另一個不相關的類別，甚至是父類別本身（如果父類別有多個子類別）。

核心觀念

本題主要考查：

1. 物件導向程式設計與類別設計。
2. 類別的封裝、抽象化與責任分工。
3. Gregorian calendar 的閏年規則。
4. 日期合法性檢查。
5. 日期區間天數計算，且開始日與終止日均須計入。

閏年定義

西元年份 $y$ 為閏年的條件為：

$$(y \bmod 400 = 0) \quad\text{或}\quad (y \bmod 4 = 0 \land y \bmod 100 \ne 0)$$

例如：

• 2000 年是閏年，因為可被 400 整除。
• 1900 年不是閏年，因為雖可被 100 整除，但不可被 400 整除。
• 2024 年是閏年，因為可被 4 整除且不可被 100 整除。

月份天數如下：

月份	天數
1、3、5、7、8、10、12	31
4、6、9、11	30
2 月，平年	28
2 月，閏年	29

---

解題方法

將日期區間轉換成「從固定起點開始累計的日數」。

假設固定起點為西元 1 年 1 月 1 日，定義：

• daysBeforeYear(y)：西元 $y$ 年以前的總天數。
• daysBeforeMonth(y,m)：第 $y$ 年第 $m$ 月以前的總天數。
• 日期本身的日序為：

$$\text{serial}(y,m,d) = \text{daysBeforeYear}(y) + \text{daysBeforeMonth}(y,m) + d$$

西元 $y$ 年以前共有 $y-1$ 年，其中閏年數為：

$$\left\lfloor\frac{y-1}{4}\right\rfloor - \left\lfloor\frac{y-1}{100}\right\rfloor + \left\lfloor\frac{y-1}{400}\right\rfloor$$

因此：

$$\text{daysBeforeYear}(y) = 365(y-1) + \left\lfloor\frac{y-1}{4}\right\rfloor - \left\lfloor\frac{y-1}{100}\right\rfloor + \left\lfloor\frac{y-1}{400}\right\rfloor$$

若開始日為 $S$，終止日為 $E$，因為頭尾兩天都要計算，所以答案為：

$$\text{總天數} = \text{serial}(E)-\text{serial}(S)+1$$

例如，2020 年 2 月 28 日至 2020 年 3 月 1 日：

• 2 月 28 日
• 2 月 29 日
• 3 月 1 日

共 $3$ 天，公式也會得到相同結果。

---

類別設計

1. CalendarRules

負責曆法規則：

• 判斷是否為閏年。
• 回傳指定年月的天數。
• 計算指定年份以前的累計天數。
• 計算指定月份以前的累計天數。

此類別將曆法規則集中管理，避免 Date 與 DateRange 重複撰寫相同邏輯。

2. Date

代表一個合法日期，封裝：

• 年
• 月
• 日

建立物件時立即檢查日期是否合法，並提供日期比較與序號轉換功能。

3. DateRange

代表由開始日期與終止日期形成的日期區間，負責：

• 確認開始日期不晚於終止日期。
• 計算包含頭尾兩日的總天數。

4. Main

負責程式執行流程：

• 讀取使用者輸入。
• 建立日期與日期區間物件。
• 輸出結果。
• 處理輸入格式與日期錯誤。

---

類別圖

+-------------------------+
|      CalendarRules      |
+-------------------------+
|                         |
+-------------------------+
| +isLeapYear(year): bool |
| +daysInMonth(y,m): int  |
| +daysBeforeYear(y): long|
| +daysBeforeMonth(y,m): long|
+------------+------------+
             ^
             |
+------------+------------+
|           Date          |
+-------------------------+
| -year: int              |
| -month: int             |
| -day: int               |
+-------------------------+
| +Date(y,m,d)            |
| +toSerial(): long       |
| +compareTo(other): int  |
| +toString(): String     |
+------------+------------+
             ^
             |
+------------+------------+
|         DateRange       |
+-------------------------+
| -start: Date            |
| -end: Date              |
+-------------------------+
| +DateRange(s,e)         |
| +inclusiveDays(): long  |
+-------------------------+

+-------------------------+
|          Main           |
+-------------------------+
| +main(args): void       |
+-------------------------+

---

Java 完整程式

核心觀念

• 銀河演算法（Banker’s Algorithm）用於檢驗系統在分配資源後是否仍處於安全狀態。
• 关键定义：
  • Allocation：已分配給每個程序的資源向量。
  • Max：每個程序可能需要的最大資源向量。
  • Need = Max – Allocation：每個程序尚需的資源。
  • Available：系統目前剩餘的資源向量。
• 安全性檢驗：假設把請求先暫時分配，得到新的 Work = Available'，再找出一個能逐次完成的程序順序，使得每一次 Need ≤ Work，完成後把該程序的 Allocation 加回 Work。若能讓所有程序都完成，則新狀態安全，請求可立即批准；否則不安全，必須延遲。

---

解題方法

1. 先算出每個程序的 Need。
2. 判斷請求是否 不超過 該程序的 Need 以及 Available（若超過直接拒絕）。
3. 若通過第 2 步，暫時把資源分配給該程序，更新 Available', Allocation', Need'。
4. 以 安全性演算法（Safety Algorithm）檢驗更新後的系統是否安全：
   • 設 Work = Available'，所有程序的 Finish = false。
   • 反覆尋找一個 Finish = false 且 Need ≤ Work 的程序，將其 Allocation 加回 Work，標記 Finish = true。
   • 若最終所有 Finish 均為 true，則安全；否則不安全。

---

步驟計算

程序	Allocation	Max	Need = Max – Allocation
P₀	(2,0,0,1)	(4,2,1,2)	(2,2,1,1)
P₁	(3,1,2,1)	(5,2,5,2)	(2,1,3,1)
P₂	(2,1,0,3)	(2,3,1,6)	(0,2,1,3)
P₃	(1,3,1,2)	(1,4,2,4)	(0,1,1,2)
P₄	(1,4,3,2)	(3,6,6,5)	(2,2,3,3)

系統初始 Available = (3,3,2,1)。

---

(a) P₁ 的請求 (1,1,0,0)

1. 檢查需求限制

$$\text{Request} = (1,1,0,0) \le \text{Need}_{P_1} = (2,1,3,1) \quad\text{且}\quad \text{Request} \le \text{Available} = (3,3,2,1)$$

均符合，故可暫時分配。

2. 暫時分配後的狀態

$$\begin{aligned} \text{Available}' &= (3,3,2,1) - (1,1,0,0) = (2,2,2,1)\\ \text{Allocation}'_{P_1} &= (3,1,2,1)+(1,1,0,0) = (4,2,2,1)\\ \text{Need}'_{P_1} &= (2,1,3,1)-(1,1,0,0) = (1,0,3,1) \end{aligned}$$

3. 安全性檢驗（Safety Algorithm）

   • 初始 Work = (2,2,2,1)，全部 Finish = false。

核心觀念

本題考查：

• TLB（Translation Lookaside Buffer）命中率
• 有效記憶體存取時間（Effective Memory Access Time, EAT）
• 單層與兩層頁表的記憶體存取次數

已知：

• TLB 命中率：$h=90\%=0.9$
• TLB 查找時間：$t_T=10\text{ ns}$
• 一次記憶體存取時間：$t_M=100\text{ ns}$

TLB 命中時，可直接取得實體頁框位置；TLB 未命中時，必須查詢頁表，再存取真正的資料。

---

解題方法

有效記憶體存取時間採用加權平均：

$$\text{EAT} = (\text{命中率})\times(\text{命中時間}) + (\text{未命中率})\times(\text{未命中時間})$$

TLB 未命中率為：

$$1-h=1-0.9=0.1$$

TLB 查找時間 $10\text{ ns}$ 無論命中或未命中都必須付出，因此兩種情況都包含此時間。

---

(a) 單層頁表

TLB 命中

TLB 已經找到頁框編號，只需要再存取一次真正的資料：

$$T_{\text{hit}} = 10+100 = 110\text{ ns}$$

TLB 未命中

TLB 查找失敗後，需要：

1. 查詢一次頁表：$100\text{ ns}$
2. 存取真正的資料：$100\text{ ns}$

因此：

$$T_{\text{miss}} = 10+100+100 = 210\text{ ns}$$

有效記憶體存取時間

$$\begin{aligned} \text{EAT} &= 0.9(110)+0.1(210)\\ &= 99+21\\ &= 120\text{ ns} \end{aligned}$$

因此，單層頁表的有效記憶體存取時間為：

$$\boxed{120\text{ ns}}$$

---

(b) 兩層頁表

這題考的是虛擬記憶體分頁系統中的位址轉換，要求計算邏輯位址 (Logical Address) 和實體位址 (Physical Address) 的位元數。

給定資訊：

• 邏輯位址空間 (Logical Address Space)：8 pages
• Page Size (頁大小)：1024 bytes
• Physical Memory (實體記憶體)：32 frames
• Frame Size (頁框大小)：與 Page Size 相同，即 1024 bytes

位址結構分析：
一個邏輯位址通常由兩部分組成：頁號 (Page Number) 和頁內偏移量 (Page Offset)。
一個實體位址通常由兩部分組成：頁框號 (Frame Number) 和頁內偏移量 (Page Offset)。

1. 計算頁內偏移量 (Page Offset) 的位元數：
頁內偏移量決定了在一個頁 (或頁框) 內可以尋址多少個位元組 (byte)。
頁大小 (Page Size) = 1024 bytes。
要表示 1024 個不同的位元組，我們需要 $2^n \ge 1024$ 個位元。
$2^{10} = 1024$。
所以，頁內偏移量需要 10 bits。
Page Offset bits = $\log_2(\text{Page Size}) = \log_2(1024) = 10$ bits。

2. 計算邏輯位址的位元數 (a)：
邏輯位址的位元數 = (頁號的位元數) + (頁內偏移量的位元數)。
邏輯位址空間有 8 個 pages。
要表示 8 個不同的 page，我們需要 $2^m \ge 8$ 個位元。
$2^3 = 8$。
所以，頁號需要 3 bits。

核心觀念

• 頁式記憶體系統：記憶體被分割成等大小的 page，頁框 (page frame) 為實體記憶體中可放置 page 的位置。
• 頁缺失 (page fault)：當程式存取的資料不在任何已有的頁框中時，系統必須從磁碟載入相應的 page，產生一次缺失。
• LRU 置換策略：當所有頁框已滿且需要載入新 page 時，淘汰最近最少被使用的頁框。
• 陣列的行主序 (row‑major) 與列主序 (column‑major) 存取：C/C++ 以行主序排列二維陣列，連續的 A[i][j]（同一列的各元素）在記憶體中是連續的；而 A[i][j]（同一列的不同列）則相隔 rowSize 個元素。

---

解題方法

1. 確定每個 page 能容納多少個陣列元素

   • 假設陣列元素大小為 1 個 word（題目只給予 page 大小 200），則每個 page 可容納 200 個元素。
   • 總元素數目 $100 \times 100 = 10\,000$，需要的 page 數目為
     $\frac{10\,000}{200}=50 \text{ 個 page}.$

2. 計算 (a) 逐列 (row‑major) 走訪的缺失次數

   • 走訪順序正好與記憶體排列相同：一次讀寫 200 個連續元素即跨越一次 page。
   • 初始時兩個頁框皆為空，載入第一個 page 產生 1 次缺失。之後每當需要一個尚未在任一頁框中的新 page 時，必發生缺失。
   • 走訪過程會依序接觸 page $1,2,\dots ,50$，每個新 page 必產生一次缺失。
   • 因為只有兩個頁框，當第 $k$ 個 page 被載入時，最近使用的 $k-1$ 個 page 中最古老的（$k-2$）會被淘汰，但這不影響缺失次數。
   • 缺失總次數
     $\boxed{50}$