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

核心觀念

本題考核現代網際網路傳輸層與應用層通訊協定的演進。核心觀念聚焦於：

1. 傳統網路協定堆疊的效能瓶頸：傳統「$\text{HTTP/2} + \text{TLS} + \text{TCP}$」架構所面臨的連線建立延遲（Connection Latency）、傳輸層隊頭阻塞（Head-of-Line Blocking, HoL Blocking）及連線遷移成本。
2. QUIC (Quick UDP Internet Connections) 協定架構：由 Google 提出、後續由 IETF 標準化（RFC 9000），作為 HTTP/3 底層基礎的傳輸協定。其核心思想是「基於 UDP 實作可靠傳輸、內建加密與多工處理」。

---

解題方法

申論「通訊協定的發展背景與特色」題型時，最嚴謹且易拿高分的結構為**「痛點出發 $\to$ 設計背景 $\to$ 核心特色 $\to$ 總結對比」**。切入點分析如下：

1. 發展背景（Why QUIC?）：說明 TCP 與 TLS 在現代行動網路與 Web 應用下的先天缺陷。
2. 核心架構與特色（What is QUIC?）：分點闡述 QUIC 如何藉由架構變更解決前述缺陷。
3. 橫向比較：整理 QUIC 與傳統 TCP+TLS 關鍵指標對照表，呈現清晰邏輯。

---

詳細解析

一、 發展背景 (Background)

在 QUIC 出現之前，Web 資料傳輸主要依賴「$\text{HTTP/2} + \text{TLS 1.2/1.3} + \text{TCP}$」堆疊。隨著行動通訊（4G/5G、Wi-Fi 頻繁切換）與豐富多媒體應用的普及，傳統架構暴露出以下致命缺點：

1. 高昂的交握延遲（Handshake Latency）：
   • 在傳統模式下，TCP 需要三次交握（1 RTT），接著 TLS 進行安全交握（TLS 1.2 需 2 RTT；TLS 1.3 需 1 RTT）。
   • 在傳輸任何應用層資料（HTTP Request）之前，最少需耗費 $2\sim 3\text{ RTT}$，對高延遲的行動網路極不友善。
2. 傳輸層隊頭阻塞（Head-of-Line Blocking, HoL Blocking）：
   • HTTP/2 雖引入了「單一 TCP 連線內多工串流（Streams Multiplexing）」，但在底層 TCP 看來，所有串流都是同一個單一字節流（Byte Stream）。
   • 一旦其中一個串流發生封包遺失（Packet Loss），TCP 的滑動視窗機制會暫停後續所有資料的遞交，直到遺失封包重傳成功。這導致「無關的串流因單一串流丟包而被迫等待」，抵消了 HTTP/2 多工的效益。
3. 中介設備僵化（Ossification of the Internet）：
   • 網際網路中存在大量防火牆、NAT 閘道、路由器等中介設備（Middleboxes），許多設備將 TCP 標頭結構硬編碼（Hardcoded）。若欲直接升級修改 TCP 協定規格，極易被中介設備丟棄，導致新功能無法部署。
4. 連線遷移成本高（Lack of Connection Migration）：
   • TCP 連線由「四元組」（來源 IP、來源 Port、目的 IP、目的 Port）唯一識別。當使用者由 Wi-Fi 切換至行動網路（4G/5G）時，IP 位址改變，原本的 TCP 連線即刻中斷，必須重新建立連線並重新交握。

---

二、 QUIC 的核心特色 (Key Features)

針對上述問題，QUIC 選擇基於無連線且普遍被中介設備允許通過的 UDP 來構建，並在使用者空間（User Space）實作可靠傳輸與擁塞控制，具備以下五大核心特色：

1. 極低的連線建立延遲（0-RTT / 1-RTT Connection Establishment）：

   • QUIC 將傳輸交握與加密交握（內建整合 TLS 1.3）合而為一。
   • 首次連線（Initial Connection）：僅需 $1\text{ RTT}$ 即可完成傳輸參數交換與金鑰協商。
   • 再次連線（Reconnection / 0-RTT）：客戶端可快取先前的連線憑據，在發送第一個連線封包時即夾帶應用層請求資料，達到 $0\text{ RTT}$ 的瞬時傳輸。

2. 徹底解決傳輸層隊頭阻塞（No Transport HoL Blocking）：

   • QUIC 在傳輸層原生支援「獨立串流（Independent Streams）」。
   • 各串流擁有各自獨立的流量控制與序號管理。當串流 A 發生封包遺失時，僅串流 A 會等待重傳，串流 B、C 仍可正常傳輸與遞交，徹底發揮多工效益。

核心觀念

本題考核電腦網路與資訊安全領域中的**虛擬私人網路（Virtual Private Network, VPN）**技術體系。核心理論涵蓋：

1. VPN 的四大安全與傳輸服務機制：
   • 機密性（Confidentiality）：對載荷進行對稱/非對稱加密。
   • 完整性（Integrity）：使用訊息鑑別碼（MAC/HMAC）防止封包竄改。
   • 身份鑑別（Authentication）：確認傳輸端點之真實身分。
   • 穿隧技術（Tunneling）：利用封裝（Encapsulation）在公共網路上建立邏輯私有通道。
2. OSI 參考模型各層次的 VPN 實作與架構差異：
   • IPSec VPN：運作於網路層（Layer 3），提供端對端或網段對網段的透明加密。
   • SSL/TLS VPN：運作於傳輸層/應用層（Layer 4–7），透過標準瀏覽器或輕量用戶端提供細粒度存取。
   • MPLS VPN：運作於 Layer 2.5（標籤交換），仰賴電信服務商（ISP）骨幹網路進行邏輯隔離，屬於非加密的專線替代方案。

---

解題方法

本題為問答題，解題架構採「兩段式論述」：

1. 第一部分（VPN 一般功能）：從「虛擬（Virtual）」、「私人（Private）」、「網路（Network）」之本質切入，條列其四大資安功能（機密性、完整性、身分鑑別、防重送）與通道封裝特性。
2. 第二部分（三者差異比較）：從運作層級、網路架構/拓撲、用戶端需求、安全性（加密性）、服務品質（QoS）與維運成本等維度建立結構化對照表，並逐一說明各自的核心技術機制與典型應用情境。

---

詳細解析

一、VPN 的一般功能

VPN 係指在不可信或共享的公共網路（如網際網路）之上，藉由通道協議（Tunneling Protocols）與密碼學技術，建立一條邏輯上專屬、安全的虛擬通道。其核心功能包含：

1. 資料機密性（Confidentiality）：
   利用對稱式加密演算法（如 AES、3DES）對原始傳輸資料進行加密，確保即使封包在公網傳輸中被竊聽（Sniffing），未授權者亦無法解讀明文。
2. 資料完整性（Data Integrity）：
   採用雜湊演算法與訊息鑑別碼（如 HMAC-SHA-256），使接收端能驗證封包在傳輸過程中是否遭到非法竄改或損毀。
3. 來源身分鑑別（Entity / Origin Authentication）：
   透過預先共用金鑰（PSK）、數位憑證（X.509）或非對稱式金鑰交換（如 RSA、ECDSA），確認連線雙方端點之合法性，防止中間人攻擊（MITM）與身分偽冒（Spoofing）。
4. 防重送攻擊（Anti-Replay Protection）：
   藉由封包序號（Sequence Number）機制，丟棄重複接收或過期的封包，防止惡意攻擊者截獲合法封包後重複發送。
5. 穿隧與位址隱藏（Tunneling & Topology Hiding）：
   將私有 IP 封包封裝於公網 IP 標頭之內傳送，對外部網路隱蔽內部企業網路的真實 IP 架構與路由細節。

---

二、IPSec VPN、SSL VPN 與 MPLS VPN 之區別比較

1. 核心特性綜合比較表

比較維度	IPSec VPN	SSL/TLS VPN	MPLS VPN (BGP/MPLS L3/L2VPN)
OSI 運作層級	第 3 層（網路層）	第 4 至 7 層（傳輸/應用層）	第 2.5 層（介於資料鏈結與網路層）
底層承載網路	公共網際網路（Internet）	公共網際網路（Internet）	電信服務商（ISP）專屬骨幹網路
加密機制	強制原生加密（ESP 協議加密）	強制原生加密（SSL/TLS 加密）	無原生加密（依賴 ISP 標籤邏輯隔離）
用戶端需求	通常需安裝專屬 Client 軟體或具備 IPSec 硬體閘道器	無用戶端（Clientless, 瀏覽器即可） 或輕量級 Web Agent	用戶端完全免軟體（由客戶端邊界路由器 CE 對接）
存取控制粒度	粗粒度（網段對網段，接入即存取整個內部子網）	細粒度（應用程式層級，可針對特定 URL 或服務限制權限）	粗粒度（完整路由虛擬化，支援整網互連）
典型應用情境	Site-to-Site（總部與分公司總體互聯）	Remote Access（員工居家辦公、行動遠端存取特定系統）	Enterprise WAN（企業大型骨幹跨國/跨區高品質互聯）
NAT 穿越性	較差（AH 協議完全不支援 NAT；ESP 需依賴 NAT-T / UDP 4500 封裝）	極佳（預設使用 TCP 443 埠，能輕易穿透防火牆與 NAT）	不適用（於專屬骨幹路由，不涉及一般公網 NAT）
QoS / 效能保障	視公網 Internet 狀況而定，無法提供硬性 QoS 保證	視公網狀況而定，延遲與抖動無法嚴格控制	支援端對端 QoS 與 SLA 保證（利用 MPLS EXP 標籤進行流量工程）
佈建與維護成本	中等（需配置雙端防火牆/路由器）	較低（部署維護集中於企業端閘道器）	極高（需長期向電信業者租用 MPLS 專線電路）

---

2. 三者技術機制詳細分析

1. IPSec VPN：
   • 協定組：主要由 AH（Authentication Header） 提供鑑別與完整性、**ESP（Encapsulating Security Payload）

核心觀念

本題評量虛擬記憶體（Virtual Memory）管理機制的核心運算，涵蓋三大主軸：

1. TLB 觸及範圍（TLB Reach）：TLB 所能映射的記憶體總量，定義為 $\text{TLB Reach} = \text{TLB 項目數 (Entries)} \times \text{分頁大小 (Page Size)}$。
2. 實體位址空間（Physical Address Space）推導：實體位址由「框號（Frame Number）」與「頁內位移（Page Offset）」組成。分頁大小決定頁內位移所需之位元數；分頁表項目（PTE）內扣除控制位元（如 valid/invalid bit）後的欄位即為實體框號位元數。
3. 多階層分頁（Multi-level Paging）之有效存取時間（Effective Access Time, EAT）：
   • 當 TLB 命中（Hit）時：耗費 1 次 TLB 搜尋時間與 1 次實體記憶體資料存取時間。
   • 當 TLB 未命中（Miss）時：耗費 1 次 TLB 搜尋時間，隨後依序走訪 $k$ 階分頁表（共 $k$ 次記憶體存取），取得實體位址後再進行最後 1 次資料存取，合計經歷 $(k + 1)$ 次記憶體存取。

---

解題方法

甲、此系統的 TLB 觸及範圍 (TLB Reach)

1. 定義與公式：
   TLB Reach 代表所有 TLB 項目合計可覆蓋的最大虛擬記憶體範圍： $$\text{TLB Reach} = \text{TLB 大小 (Entries)} \times \text{分頁大小 (Page Size)}$$
2. 代入數值推導：
   • TLB 大小 $= 1024 = 2^{10}\text{ entries}$
   • 分頁大小 $= 512\text{ B} = 2^9\text{ B}$
   $$\text{TLB Reach} = 1024 \times 512\text{ B} = 524,288\text{ B} = 512\text{ KB}$$

---

乙、此系統的實體位址空間大小

1. 頁內位移（Page Offset, $d$）位元數：
   分頁大小為 $512\text{ B} = 2^9\text{ B}$，因此頁內位移需佔用：

   $$d = \log_2(512) = 9\text{ bits}$$

2. 實體框號（Frame Number, $f$）位元數：
   分頁表項目內存放的基底位置總共為 $11\text{ bits}$，且題意明確指出其中包含有效／無效位元（valid/invalid bit，佔 $1\text{ bit}$）。
   因此，實際用來定址實體記憶體框（Frame）的位元數為：

   $$f = 11 - 1 = 10\text{ bits}$$

3. 實體位址（Physical Address）總長度與空間大小：
   實體位址由實體框號與頁內位移組合而成，總長度為：

   $$\text{Physical Address Bits} = f + d = 10 + 9 = 19\text{ bits}$$

   因此，實體位址空間大小為：

   $$2^{19}\text{ B} = 512\text{ KB}$$

核心觀念

本題的核心考點在於作業系統中 fork() 系統呼叫的分支行為、行程樹（Process Tree）的追蹤，以及 行程（Process）與執行緒（Thread）的生命週期及結構差異。

1. fork() 的運作機制與返回值：

   • 呼叫 fork() 會建立一個與呼叫者（Parent）幾乎一模一樣的子行程（Child）。
   • 在父行程中，fork() 回傳新建立之子行程的 PID（$> 0$）。
   • 在子行程中，fork() 回傳 $0$。
   • 若發生錯誤則回傳負值（一般假設資源充足，不考慮失敗情況）。
   • 每次執行 fork()，當前存在的行程數會變為原來的 $2$ 倍。

2. 條件判斷式 if (pid == 0)：

   • 只有「第一個 fork() 所產生的子行程」其 pid 變數才會是 $0$，並進入 if 區塊內部。
   • 原父行程的 pid > 0，不會進入該區塊。

3. 行程與執行緒的關係：

   • 每個獨立行程在建立時，本身即包含一個主執行緒（Main Thread）。
   • 呼叫 thread_create(...) 會在該行程內部額外建立一個由它所屬的使用者/核心執行緒。
   • 子行程在被 fork() 出來時，如果尚未呼叫 thread_create()，則該子行程僅有自身的單一主執行緒；fork() 複製的是整個行程位址空間，已存在的執行緒不會自動跨到不相關的新分支。

---

解題方法與步驟推導

我們依程式執行順序逐步繪製行程樹，並統計行程與執行緒數量。

甲、獨立行程（Process）數量推導

令最初始執行的父行程為 $P_0$。

1. 第 3 行：pid = fork();

   • $P_0$ 呼叫 fork() 產生第一個子行程 $P_1$。
   • 此時系統中共有 $2$ 個行程：
     • $P_0$（父行程，其區域變數 pid $> 0$）
     • $P_1$（子行程，其區域變數 pid = 0）

2. 第 4 行：if (pid == 0)

   • $P_0$：pid > 0，條件不成立，跳過 if 區塊，直接到達第 8 行。
   • $P_1$：pid == 0，條件成立，進入 if 內部執行：
     • 第 5 行：fork();
       • $P_1$ 產生子行程 $P_2$。此時進入 if 內部的行程有 $P_1$ 與 $P_2$。
     • 第 6 行：thread_create(. . .);
       • $P_1$ 與 $P_2$ 皆會執行此行，在此建立執行緒（不增加新行程）。
     • 離開 if 區塊。

   至此，系統中共有 $3$ 個行程：$P_0, P_1, P_2$。

3. 第 8 行：fork();

   • 此時抵達此行的行程共有 $3$ 個（$P_0, P_1, P_2$），且每一行程各自執行一次 fork()：
     • $P_0$ 呼叫 fork() 產生 $P_3$。
     • $P_1$ 呼叫 fork() 產生 $P_4$。
     • $P_2$ 呼叫 fork() 產生 $P_5$。
   • 產生的新行程數為 $3$ 個。

4. 總獨立行程數計算：
   $3 + 3 = 6$

   • 產生的新行程總共為 $5$ 個（$P_1, P_2, P_3, P_4, P_5$）。
   • 若題目問的是「程式執行完後，系統中總共包含（存在過）多少個獨立行程」，則包含原始行程在內共有 6 個行程。
   • 若題目問的是「由原始程式所額外『產生（created/generated）』的行程數」，則為 $6 - 1 =$ 5 個行程。
   • 在台灣研究所入學考試中，「會產生多少個獨立的行程」通常指最終存在的全部行程個數（即行程樹中的總節點數），標準答案為 6 個（亦常有教授給予嚴格定義產生數 5 個）。

---

乙、獨立執行緒（Thread）數量推導

核心觀念

本題考查關聯式資料庫設計中的**正規化理論（Database Normalization Theory）**及其數學理論基礎。

關聯式資料庫正規化的主要目的是消除資料重複性（Data Redundancy）並避免資料操作異常（Insertion, Deletion, Update Anomalies）。在 Edgar F. Codd 提出的正規化層次中：

• 1NF、2NF、3NF 以及 BCNF：均是以**功能相依（Functional Dependency, FD）**為核心數學觀念發展出來的。
• 4NF 則是以**多元相依（Multivalued Dependency, MVD）**為基礎。
• 5NF（PJNF）則是以**合併相依（Join Dependency, JD）**為基礎。

---

解題方法

回答本題的關鍵在於說明**功能相依（Functional Dependency, FD）**如何貫穿並定義 1NF 至 3NF 的推展過程：

1. 功能相依的定義：
   設 $R$ 為一關聯綱要（Relation Schema），$X$ 與 $Y$ 為 $R$ 的屬性子集合。若對於關聯實例中的任兩筆記錄 $t_1, t_2$，只要 $t_1[X] = t_2[X]$，則必有 $t_1[Y] = t_2[Y]$，我們稱「$X$ 功能決定 $Y$」或「$Y$ 功能相依於 $X$」，記作：
   $X \rightarrow Y$
   其中 $X$ 稱為決定鍵（Determinant）。

2. 以功能相依為基礎推展 1NF、2NF、3NF：

   • 第一正規化（1NF）：
     要求所有屬性值皆為原子值（Atomic Values），消除重複群（Repeating Groups）。此條件為建立明確屬性間「值對值」對應的前提，使得屬性之間的功能相依關係（$X \rightarrow Y$）得以明確定義。
   • 第二正規化（2NF）：
     符合 1NF，且消除部分功能相依（Partial Functional Dependency）。
     • 即所有非鍵屬性（Non-prime Attribute）必須**完全功能相依（Full Functional Dependency）**於任何候選鍵（Candidate Key），不得僅相依於複合主鍵的其中一部分。
   • 第三正規化（3NF）：

核心觀念

本題評量 C 語言的**指標（Pointer）**基礎運作，包含以下重要觀念：

1. 取址運算子（Address-of Operator, &）：取得變數在記憶體中的位址（Address）。
2. 反參考運算子 / 間接存取運算子（Dereference Operator, *）：存取指標所指向之記憶體位址中所存放的值（Value）。
3. 指標變數的宣告與指派：指標變數用以存放記憶體位址，對 *p 指派值會直接變更該位址所對應之實體變數內容。

---

解題方法與詳細追蹤

本題雖給定變數 $a$ 與 $b$ 的記憶體位址（&a = 0X0012FF74、&b = 0X0012FF78），此為題目提供之實體記憶體配置情境，解題關鍵在於逐行追蹤各變數與指標的指向狀態：

1. int a = 11, b = 21;

   • 初始化變數：
     • $a$ 的值為 $11$，位於 0X0012FF74。
     • $b$ 的值為 $21$，位於 0X0012FF78。

2. int *p;

   • 宣告一個指向整數型態（int）的指標變數 p。此時尚未初始化。

3. p = &a;

   • 將變數 $a$ 的記憶體位址指派給指標 p。
   • 此時 p = 0X0012FF74，代表指標 p 指向變數 $a$。

4. b = *p;

   • *p 代表取出指標 p 所指向位址之內容，即取出變數 $a$ 的值（目前為 $11$）。
   • 將該值指派給變數 $b$。
   • 執行後：$b = 11$。此時變數 $a$ 與 $b$ 的值皆為 $11$。

5. *p = 0;

   • 透過指標反參考，將數值 $0$ 寫入 p 所指向的記憶體位址（即變數 $a$ 所在的 0X0012FF74）。
   • 此操作直接修改了變數 $a$ 的值。
   • 執行後：$a = 0$。

核心觀念

本題考核關聯式資料庫正規化（Relational Database Normalization）的核心理論與實務儲存空間效益分析：

1. 第一正規化（1NF）：資料表所有屬性之值皆為單一不可分割的原子值（Atomic Values）。
2. 第二正規化（2NF）：已滿足 1NF，且所有非鍵屬性（Non-prime attributes）皆「完全相依於」（Fully Functionally Dependent）候選鍵，不存在「部分相依」（Partial Dependency）。當候選鍵僅由單一屬性組成時，必定自動滿足 2NF。
3. 第三正規化（3NF）：已滿足 2NF，且所有非鍵屬性皆不得「遞移相依於」（Transitively Dependent）候選鍵。換言之，對於任何非平凡相依 $X \to Y$，$X$ 必須為超鍵（Superkey），或 $Y$ 為主屬性（Prime attribute）。
4. 異常（Anomalies）與無失真分解（Lossless-Join Decomposition）：當關聯表中存在非主鍵決定的函數相依時，會產生新增、刪除與修改異常。透過投影分解可將綱要提升至更高正規化層級（如 3NF / BCNF）。
5. 儲存空間分析：正規化透過消除資料重複（Redundancy）來節省儲存空間。極端案例（Extreme Case）指相依屬性在不同關聯組中出現最大量重複值的情境。

---

解題方法與詳細推導

甲、判斷 Table $X$ 符合的正規化層級

1. 屬性分類：
   • 候選鍵（Candidate Key）僅有主鍵 $A$。
   • 主屬性（Prime attribute）：$\{A\}$。
   • 非主屬性（Non-prime attributes）：$\{B, C, D\}$。
2. 1NF 檢查：
   • 題意中 $A, B, C, D$ 均為固定長度（8 bytes）之屬性，符合原子值特性，滿足 1NF。
3. 2NF 檢查：
   • 候選鍵為單一屬性 $A$，不存在由多個屬性組成的複合鍵（Composite Key），因此不可能存在非主屬性對候選鍵之真子集的相依（無部分相依）。故 Table $X$ 滿足 2NF。
4. 3NF 檢查：
   • 題目給定函數相依：$A \to B$ 且 $B \to D$。
   • 由於 $B$ 不是超鍵，且 $D$ 不是主屬性，因此存在遞移相依（Transitive Dependency）：
     $A \to B \to D$
   • 由於非主屬性 $D$ 遞移相依於候選鍵 $A$，違反 3NF 定義。
5. 結論：Table $X$ 滿足 1NF 與 2NF，但不滿足 3NF。

---

乙、進一步正規化以避免異常

1. 異常現象：
   • 更新異常（Update Anomaly）：若某個 $B$ 對應的 $D$ 需要修改，必須同步更新所有包含該 $B$ 的資料列，否則造成資料不一致。
   • 新增異常（Insertion Anomaly）：若要新增一組 $B \to D$ 的關聯，在尚未有實體對應的主鍵 $A$ 之前無法存入。
   • 刪除異常（Deletion Anomaly）：刪除包含某 $A$ 的資料列時，可能連帶遺失僅存的 $B \to D$ 對應資訊。
2. 分解步驟（Decomposition）：
   • 將違反 3NF 的遞移相依部分獨立成新資料表。
   • 分解為兩個關聯表：
     $X_1(A, B, C)$
     主鍵為 $A$。
     $X_2(B, D)$
     主鍵為 $B$。
3. 所得正規化層級：
   • 在 $X_1$ 中，唯一的非平凡函數相依為 $A \to B, C$，$A$ 為超鍵，滿足 3NF 與 BCNF。
   • 在 $X_2$ 中，唯一的非平凡函數相依為 $B \to D$，$B$ 為超鍵，滿足 3NF 與 BCNF。
   • 此分解同時具備無失真連接（Lossless-Join）（因為 $X_1 \cap X_2 = \{B\}$，且 $B$ 是 $X_2$ 的鍵）與**相依性保留（Dependency Preservation）**特性。

---

丙、極端情況下可節省的最大儲存空間

1. 未正規化前 Table $X$ 儲存空間：
   • 每個屬性長度為 8 bytes。
   • 一筆資料列的大小：
     $4 \times 8 = 32 \text{ bytes}$
   • 10,000 筆資料列的總空間：

核心觀念

本題評量資料庫管理系統（DBMS）在「交易處理（Transaction Processing）」中的**並行控制（Concurrency Control）**機制，核心焦點為：

1. 鎖定模式（Locking Modes）與相容性矩陣（Compatibility Matrix）：
   • 共享鎖（Shared Lock, S-lock）：又稱讀取鎖（Read Lock）。當交易僅需讀取資料項目時申請。多個交易可同時對同一資料項目持有 S-lock，彼此相容（Compatible）。
   • 互斥鎖（Exclusive Lock, X-lock）：又稱寫入鎖或獨佔鎖（Write Lock）。當交易需修改（更新、刪除、插入）資料項目時申請。一旦某交易持有 X-lock，其他交易無論申請 S-lock 或 X-lock 皆會被阻擋（Incompatible），具排他性。
2. 鎖定資料項目的粒度（Lock Granularity）：
   • 粒度指的是被鎖定資料單元的大小，由細到粗（Fine to Coarse）可分為：欄位（Attribute/Field）$\rightarrow$ 紀錄／元組（Tuple/Record）$\rightarrow$ 磁區／分頁（Disk Page/Block）$\rightarrow$ 資料表（Table）$\rightarrow$ 整個資料庫（Database）。
   • 系統在**並行度（Concurrency）與鎖定管理負擔（Locking Overhead）**之間存在根本的權衡（Trade-off）。

---

解題方法與分析

子題甲、Shared Lock 與 Exclusive Lock 之差異比較

切入點在於兩者的「存取權限（操作類型）」以及「相容性規則（Compatibility Rules）」：

1. 存取權限的差異：

   • 共享鎖（S-lock）：交易獲得 S-lock 後，**僅能讀取（Read-only）**該資料項目，不能進行任何寫入或修改操作。
   • 互斥鎖（X-lock）：交易獲得 X-lock 後，**既可讀取亦可寫入／更新（Read and Write）**該資料項目。

2. 鎖定相容性與並行性（Lock Compatibility）：

   • 設有交易 $T_1$ 與 $T_2$ 存取同一資料項目 $Q$：
     • 若 $T_1$ 持有 $Q$ 之 S-lock，則 $T_2$ 申請 S-lock 會立即被核准（S 與 S 相容）；但若 $T_2$ 申請 X-lock 則必須等待 $T_1$ 釋放鎖。
     • 若 $T_1$ 持有 $Q$ 之 X-lock，則 $T_2$ 無論申請 S-lock 或 X-lock 皆會被阻擋進入等待佇列（X 與任何鎖皆互斥）。

鎖定相容性矩陣（Lock Compatibility Matrix）：

既有鎖定 \ 申請鎖定	Shared Lock ($S$)	Exclusive Lock ($X$)
Shared Lock ($S$)	相容（True）	不相容（False）
Exclusive Lock ($X$)	不相容（False）	不相容（False）

---

子題乙、鎖定大小（Lock Granularity）之優缺點分析

針對小粒度（如 Tuple/Record）與大粒度（如 Table/Database）進行「並行度」、「系統負擔」與「死鎖機率」的全面比較：

1. 小粒度鎖定（Small-sized Granularity，如 Record / Tuple）：
   • 優點（Pros）：
     • 並行度高（High Concurrency）：資料衝突的機率大幅降低。不同的交易可以同時修改同一個資料表中的不同紀錄，顯著提升系統的整體吞吐量（Throughput）。

核心觀念

本題考核程式設計中的基本運算操作與演算法思維。常規的數值交換（Swap）通常需要引入第三個暫存變數（Temporary Variable，如 temp = a; a = b; b = temp;），但在空間受限或特定面試情境下，常要求「不使用額外變數」完成交換。

其核心運算手法主要有兩種：

1. 加減法（Arithmetic Addition and Subtraction）：利用數值差額進行疊加與還原。
2. 位元互斥或運算（Bitwise XOR, ^）：利用 XOR 的代數性質：
   • 自反性：$x \oplus x = 0$
   • 單位元素性：$x \oplus 0 = x$
   • 交換律與結合律：$a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b$

---

解題方法

方法一：位元互斥或（Bitwise XOR）法【推薦，無溢位風險】

令兩變數為 $a$ 與 $b$：

1. a = a ^ b; $\rightarrow$ 此時 $a$ 儲存了兩者的差異遮罩（$a_{\text{new}} = a \oplus b$）。
2. b = a ^ b; $\rightarrow$ 將遮罩與原 $b$ 做 XOR：$b_{\text{new}} = a_{\text{new}} \oplus b = (a \oplus b) \oplus b = a$。此時 $b$ 已成功取得 $a$ 的原始值。
3. a = a ^ b; $\rightarrow$ 將遮罩與新的 $b$（即原 $a$）做 XOR：$a_{\text{final}} = a_{\text{new}} \oplus b_{\text{new}} = (a \oplus b) \oplus a = b$。此時 $a$ 成功取得 $b$ 的原始值。

此方法適用於所有整數型別（int, long, short, byte），運算速度極快且完全不需擔心數值溢位（Overflow）。

方法二：算術加減法（Arithmetic Approach）

1. a = a + b; $\rightarrow$ $a$ 儲存兩數之和。
2. b = a - b; $\rightarrow$ $b$ 取得 $(a + b) - b = a$。
3. a = a - b; $\rightarrow$ $a$ 取得 $(a + b) - a = b$。

*注意：若兩整數極大，相加可能導致整數溢位（Integer Overflow）。

核心觀念

1. 質數（Prime Number）的定義：
   在正整數範圍中，若一個大於 $1$ 的整數除了 $1$ 與自身以外，沒有其他正因數，則稱該數為質數。小於或等於 $1$ 的整數（如 $\le 1$）均非質數；整數 $2$ 為唯一的偶數質數。
2. 因數的成對性（Divisor Pairing）：
   若正整數 $n$ 為合數，則必存在整數 $a, b > 1$ 使得 $n = a \times b$。若兩者皆大於 $\sqrt{n}$，則 $a \times b > \sqrt{n} \times \sqrt{n} = n$，產生矛盾。因此，合數必有至少一個小於或等於 $\sqrt{n}$ 的因數。檢驗質數時，因數試除上限只需到 $\lfloor\sqrt{n}\rfloor$。
3. 輪式篩法簡化版（Wheel Factorization, $6k \pm 1$ 觀念）：
   所有整數除以 $6$ 的餘數必為 $0, 1, 2, 3, 4, 5$ 之一。
   • $6k, 6k+2, 6k+4$ 為偶數（能被 $2$ 整除）。
   • $6k+3$ 為 $3$ 的倍數（能被 $3$ 整除）。
   • 因此，大於 $3$ 的所有質數必然落在 $6k+1$ 或 $6k+5$（等價於 $6k-1$）的形式上。
     排除 $2$ 和 $3$ 的倍數後，後續只需以步長 $6$ 檢查 $i$ 與 $i+2$ 兩類因數，可直接減少 $\frac{2}{3}$（約 $66.7\%$）的試除次數。

---

解題方法

本題要求不引用內建函式庫、自行設計最佳效率的質數判斷演算法，並提供標準輸入輸出。
本題採用 $6k \pm 1$ 步進試除法（Trial Division with $6k \pm 1$ Optimization）：

1. 邊界與基底條件檢查：
   • 若輸入 $n \le 1$，直接判定為非質數（False）。
   • 若 $n = 2$ 或 $n = 3$，直接判定為質數（True）。
   • 若 $n \pmod 2 == 0$ 或 $n \pmod 3 == 0$，直接判定為非質數（False）。
2. 迴圈範圍與步長設計：
   • 令迴圈變數 $i$ 從 $5$ 開始，終止條件為 $i \times i \le n$（避免重複計算浮點數開根號 Math.sqrt()，同時兼顧整數運算精準度）。
   • 每次迴圈依序檢查 $n \pmod i == 0$ 與 $n \pmod{i+2} == 0$。
   • 步長遞增設定為 i += 6（依序檢查 $5, 7, 11, 13, 17, 19, \dots$）。
3. 效率原因說明（題目明確要求闡述）：
   • 相比於暴力檢查法至 $n-1$ 的 $O(n)$，將上限壓縮至 $\sqrt{n}$ 使複雜度降為 $O(\sqrt{n})$。
   • 相比於傳統檢查所有奇數（步長為 $2$），$6k \pm 1$ 法額外濾除所有 $3$ 的倍數，試除次數由 $\frac{\sqrt{n}}{2}$ 縮減為 $\frac{\sqrt{n}}{3}$，常數項大幅優化，為單一數值確定性試除法中的最高效率解。

---

程式碼實作（Java）