# Second Semester of 2023 PhD Qualifying Exam

## Subject: Operating Systems

### 1. [Process: 20%]

**(1) Explain three conditions a solution to the critical-section problem must meet. (6%)**

**題目 1.1：解釋解決臨界區問題必須滿足的三個條件。**

**答案：**

解決臨界區問題的方案必須滿足以下三個條件：

1. **互斥（Mutual Exclusion）**：如果一個進程在臨界區內執行，則其他進程不能進入臨界區。
2. **進程（進入）和進程（退出）的進程限制（Progress）**：如果沒有進程在臨界區內且有進程希望進入臨界區，則允許進入臨界區的決策不能無限期地推遲。
3. **有限等待（Bounded Waiting）**：每個進程在請求進入臨界區後，最終都能夠進入臨界區，即確保進程不會遭受饑餓。

**(2) What are the four principal events which cause processes to be created? (4%)**

**題目 1.2：造成進程創建的四個主要事件是什麼？**

**答案：**

造成進程創建的四個主要事件是：

1. **系統初始化**：操作系統啟動時創建進程。
2. **運行時創建進程**：進程執行創建子進程的系統調用，如 `fork`。
3. **用戶請求**：用戶請求運行一個新的程序。
4. **啟動批處理作業**：批處理系統中提交的作業需要創建進程來執行。

**(3) Explain five metrics used to evaluate a process scheduling algorithm. (10%)**

**題目 1.3：解釋評估進程調度算法的五個指標。**

**答案：**

評估進程調度算法的五個指標如下：

1. **CPU利用率（CPU Utilization）**：CPU被實際使用的時間比例。
2. **吞吐量（Throughput）**：在單位時間內完成的進程數量。
3. **周轉時間（Turnaround Time）**：從進程提交到完成所需的總時間。
4. **等待時間（Waiting Time）**：進程在就緒隊列中等待的總時間。
5. **響應時間（Response Time）**：從進程提交到第一次獲得CPU執行的時間。

### 2. [Memory Management: 20%]

**(1) Explain how dynamic linking (for library routines) works? (10%)**

**題目 2.1：解釋動態連結（對於庫例程）的工作原理。**

**答案：**

動態連結是在運行時而不是編譯時將程序與庫例程連接在一起。這意味著程序在執行時，動態鏈接器（Loader）會將需要的庫代碼加載到內存中，並更新程序的地址空間，使其能夠引用這些庫函數。動態連結的優點是節省內存空間和提高程序的可移植性。

**(2) What is Belady’s anomaly in page replacement? Why can stack algorithms never exhibit Belady’s anomaly? (6%)**

**題目 2.2：什麼是頁替換中的Belady異常？為什麼棧算法從不會出現Belady異常？**

**答案：**

Belady異常是指在某些頁替換算法中，增加分配給進程的頁框數量反而會導致頁故障數增加的現象。棧算法（如LRU和OPT）永不會出現Belady異常，因為這些算法保證了在更多頁框下的頁集合是其在更少頁框下的超集，因此不會出現頁故障增加的情況。

**(3) When will the dirty bit and the reference bit of a page be set? (4%)**

**題目 2.3：在什麼情況下頁的髒位和參考位會被設置？**

**答案：**

- **髒位（Dirty Bit）**：當頁中的數據被修改時，髒位被設置。
- **參考位（Reference Bit）**：當頁被訪問（讀取或寫入）時，參考位被設置。

### 3. [File System and I/O: 20%]

**(1) Explain how incremental, physical, and logical dump work. (9%)**

**題目 3.1：解釋增量轉儲、物理轉儲和邏輯轉儲的工作原理。**

**答案：**

- **增量轉儲（Incremental Dump）**：只備份自上次備份以來修改過的數據。
- **物理轉儲（Physical Dump）**：按數據在磁盤上的物理布局進行備份，包括所有數據塊。
- **邏輯轉儲（Logical Dump）**：按文件系統的邏輯結構進行備份，包括文件和目錄結構。

**(2) Explain memory-mapped I/O and programmed I/O. (6%)**

**題目 3.2：解釋內存映射I/O和編程I/O。**

**答案：**

- **內存映射I/O（Memory-Mapped I/O）**：將I/O設備的寄存器映射到內存地址空間，通過內存地址訪問I/O設備。
- **編程I/O（Programmed I/O）**：使用CPU指令直接控制I/O設備，CPU不斷輪詢設備狀態以完成I/O操作。

**(3) Explain how to carry out a direct memory access (DMA) transfer? (5%)**

**題目 3.3：解釋如何執行直接內存存取（DMA）傳輸。**

**答案：**

執行DMA傳輸的步驟如下：

1. **設置DMA控制器**：CPU設置DMA控制器，包括源地址、目標地址、傳輸大小等參數。
2. **發起DMA傳輸**：DMA控制器向I/O設備發出讀取或寫入請求，開始數據傳輸。
3. **數據傳輸**：DMA控制器直接在內存和I/O設備之間傳輸數據，不經過CPU。
4. **傳輸完成**：DMA控制器發送中斷信號給CPU，通知傳輸完成。

### 4. [Distributed Systems: 20%]

**(1) Explain five reasons to perform process migration in a distributed system. (10%)**

**題目 4.1：解釋在分佈式系統中執行進程遷移的五個原因。**

**答案：**

在分佈式系統中執行進程遷移的原因包括：

1. **負載均衡（Load Balancing）**：將進程從負載過重的節點遷移到負載較輕的節點。
2. **性能提升（Performance Improvement）**：將進程遷移到具有更高性能資源的節點。
3. **資源共享（Resource Sharing）**：允許進程訪問其他節點的特殊硬件或軟件資源。
4. **故障恢復（Fault Tolerance）**：在節點故障時將進程遷移到其他可用節點，確保系統連續性。
5. **節能（Energy Saving）**：將進程集中到少數節點運行，允許其他節點進入低功耗模式。

**(2) Explain both location transparency and location independence. (4%)**

**題目 4.2：解釋位置透明性和位置獨立性。**

**答案：**

- **位置透明性（Location Transparency）**：用戶或進程不需要知道資源的物理位置即可訪問資源。
- **位置獨立性（Location Independence）**：資源的位置可以變動，而不影響用戶或進程對資源的訪問方式。

**(3) What are the three guidelines in the happened-before relation? (6%)**

**題目 4.3：在發生-先於關係中有哪三個準則？**

**答案：**

在發生-先於關係中的三個準則：

1. **局部性（Locality）**：在同一進程內，事件的發生順序是確定的。
2. **發送和接收（Send and Receive）**：在不同進程間，如果事件A是消息的發送，事件B是消息的接收，則A發生在B之前。
3. **傳遞性（Transitivity）**：如果事件A發生在事件B之前，事件B發生在事件C之前，則事件A發生在事件C之前。

### 5. [Explanation of Glossary: 20%]

**(1) Address-space identifier**

**題目 5.1：地址空間標識符**

**答案：**

地址空間標識符（ASID）是一個唯一標識處理器內部的不同地址空間的標識符，用於區分不同進程的地址空間，以便在虛擬內存系統中進行有效的地址轉換。

**(2) Conflict serializable**

**題目 5.2：衝突可串行化**

**答案：**

衝突可串行化是指一個並發調度的結果與某個串行調度的結果相同，且該串行調度的順序可以通過交換不衝突的操作來達到。

**(3) Trap door**

**題目 5.3：陷阱門**

**答案：**

陷阱門是一個軟件或系統中預先設置的秘密入口，允許未經授權的用戶繞過正常的安全控制，直接訪問系統。

**(4) Fault-tolerant system**

**題目 5.4：容錯系統**

**答案：**

容錯系統是一個能夠在部分組件故障的情況下，仍然保持正常運行的系統。它通過冗餘、備份和故障恢復機制來實現高可用性。

**(5) Firm real-time system**

**題目 5.5：硬實時系統**

**答案：**

硬實時系統是一種對時間要求嚴格的系統，必須在特定的時間限制內完成任務，否則任務結果將失去價值或系統將無法正常運行。

---

# First Semester of 2023 PhD Qualifying Exam

## Subject: Operating Systems

### 1. [Process Management and Coordination: 20%]

**(1) Explain five common criteria used to evaluate process scheduling algorithms. (10%)**

**題目 1.1：解釋評估進程調度算法的五個常見標準。**

**答案：**

評估進程調度算法的五個常見標準如下：

1. **CPU利用率（CPU Utilization）**：CPU被實際使用的時間比例。
2. **吞吐量（Throughput）**：在單位時間內完成的進程數量。
3. **周轉時間（Turnaround Time）**：從進程提交到完成所需的總時間。
4. **等待時間（Waiting Time）**：進程在就緒隊列中等待的總時間。
5. **響應時間（Response Time）**：從進程提交到第一次獲得CPU執行的時間。

**(2) Explain three requirements for any solution to the critical-section problem. (3%)**

**題目 1.2：解釋解決臨界區問題的三個要求。**

**答案：**

解決臨界區問題的方案必須滿足以下三個要求：

1. **互斥（Mutual Exclusion）**：如果一個進程在臨界區內執行，則其他進程不能進入臨界區。
2. **進程（進入）和進程（退出）的進程限制（Progress）**：如果沒有進程在臨界區內且有進程希望進入臨界區，則允許進入臨界區的決策不能無限期地推遲。
3. **有限等待（Bounded Waiting）**：每個進程在請求進入臨界區後，最終都能夠進入臨界區，即確保進程不會遭受饑餓。

**(3) Explain how a deadlock avoidance scheme works. (2%)**

**題目 1.3：解釋死鎖避免方案如何工作。**

**答案：**

死鎖避免方案通過動態地檢查系統資源分配情況，確保系統不會進入死鎖狀態。最常見的死鎖避免算法是銀行家算法，它通過檢查每個進程的最大需求和可用資源，判斷是否可以安全地分配資源，從而避免系統進入不安全狀態。

**(4) Explain how the multilevel queue scheduling algorithm works. (3%)**

**題目 1.4：解釋多級隊列調度算法如何工作。**

**答案：**

多級隊列調度算法將進程分成多個隊列，每個隊列具有不同的優先級和調度策略。常見的配置包括前台交互進程的高優先級隊列和後台批處理進程的低優先級隊列。進程在各自的隊列內進行調度，高優先級隊列的進程優先執行。

**(5) What are conflicting operations? (2%)**

**題目 1.5：什麼是衝突操作？**

**答案：**

衝突操作是指兩個操作同時訪問相同數據且至少有一個是寫操作，這些操作無法同時安全地進行。衝突操作包括讀-寫衝突和寫-寫衝突。

### 2. [Memory Management: 20%]

**(1) What is the difference between external and internal fragmentation? (4%)**

**題目 2.1：外部碎片和內部碎片的區別是什麼？**

**答案：**

- **外部碎片（External Fragmentation）**：由於內存中分散的小空間無法被分配給進程，導致內存浪費。
- **內部碎片（Internal Fragmentation）**：分配的內存塊比進程實際需要的內存多，導致分配給進程但未使用的內存浪費。

**(2) How does vfork() work? When will it be used? (3%)**

**題目 2.2：vfork()如何工作？何時使用？**

**答案：**

vfork() 創建一個子進程，該子進程與父進程共享地址空間，直到子進程調用exec或exit。vfork() 通常用於子進程立即調用exec的情況，以提高性能和節省內存。

**(3) What is the difference between static and dynamic linking to libraries? (4%)**

**題目 2.3：靜態連結和動態連結庫的區別是什麼？**

**答案：**

- **靜態連結（Static Linking）**：在編譯時將庫的代碼直接嵌入可執行文件中。優點是執行時不需要外部庫文件，缺點是可執行文件較大。
- **動態連結（Dynamic Linking）**：在運行時將庫的代碼加載到內存中並連結。優點是節省內存和磁盤空間，缺點是需要在運行時提供動態庫。

**(4) What is swap space? What are the two major features of swap space? (3%)**

**題目 2.4：什麼是交換空間？交換空間的兩個主要特徵是什麼？**

**答案：**

交換空間是硬盤上的一部分，用於存儲當前內存中不活躍的頁面。其兩個主要特徵是：

1. **虛擬內存的擴展**：提供比物理內存更大的虛擬內存空間。
2. **內存管理的靈活性**：允許系統在內存不足時將部分內存頁面交換到磁盤上，以釋放物理內存。

**(5) Please give the four steps in the page replacement routine. (4%)**

**題目 2.5：請給出頁替換程序的四個步驟。**

**答案：**

頁替換程序的四個步驟如下：

1. **選擇要替換的頁（Select a page to replace）**：使用頁替換算法（如LRU或FIFO）選擇要替換的頁。
2. **檢查髒位（Check the dirty bit）**：如果被選中的頁已經修改過，則需要將其寫回到磁盤。
3. **更新頁表（Update the page table）**：將被替換頁的頁表條目設為無效，並設置新頁的頁表條目。
4. **加載新頁（Load the new page）**：將新頁從磁盤讀入內存，並更新頁表。

**(6) How does the page-fault frequency solution work? (2%)**

**題目 2.6：頁故障頻率解決方案如何工作？**

**答案：**

頁故障頻率解決方案通過調整分配給進程的頁框數量來控制頁故障頻率。如果頁故障頻率過高，則分配更多的頁框；如果頁故障頻率過低，則回收一些頁框，以實現內存利用率和性能的平衡。

### 3. [Storage Management: 20%]

**(1) Explain the two interrupt request lines for a CPU. (4%)**

**題目 3.1：解釋CPU的兩條中斷請求線。**

**答案：**

CPU的兩條中斷請求線是：

1. **IRQ（Interrupt Request Line）**：用於外部設備向CPU發送中斷請求，通知CPU處理事件。
2. **NMI（Non-Maskable Interrupt Line）**：一種不可屏蔽的中斷線，用於處理緊急和高優先級的事件，如硬件故障。

**(2) Explain the following terms: (10%)**

**題目 3.2：解釋以下術語。**

- (a) **mount point**：掛載點，用於將外部文件系統整合到當前文件系統樹中的位置。
- (b) **seek time**：尋道時間，指磁盤讀寫頭移動到目標磁道所需的時間。
- (c) **rotational latency**：旋轉延遲，指磁盤旋轉將目標扇區移動到讀寫頭下方所需的時間。
- (d) **vectored I/O**：矢量I/O，指一次系統調用操作多個I/O設備或文件的技術。
- (e) **spool**：假脱机，指將數據從一個設備或程序臨時存儲到中間設備（如磁盤），以便稍後處理。

**(3) What is the major job of a device adapter? (2%)**

**題目 3.3：設備適配器的主要工作是什麼？**

**答案：**

設備適配器的主要工作是提供接口，將I/O設備連接到計算機系統的總線，並管理數據傳輸和設備控制。

**(4) What does uniform naming mean in I/O software? (2%)**

**題目 3.4：I/O軟件中的統一命名是什麼意思？**

**答案：**

統一命名指在I/O軟件中使用一致的命名約定來標識和訪問所有I/O設備和文件，從而簡化程序設計和系統管理。

**(5) How will BIOS do for implementing Plug’n Play? (2%)**

**題目 3.5：BIOS如何實現即插即用？**

**答案：**

BIOS通過即插即用擴展（PnP BIOS）來識別和配置新硬件設備，包括分配系統資源（如IRQ、DMA通道和I/O端口地址），使操作系統能夠自動檢測並使用新設備。

### 4. [Distributed and Special Systems: 20%]

**(1) Explain how the two-phase locking method works. (5%)**

**題目 4.1：解釋兩階段鎖定方法如何工作。**

**答案：**

兩階段鎖定方法（2PL）分為兩個階段：

1. **增長階段（Growing Phase）**：事務可以獲取鎖，但不能釋放鎖。
2. **收縮階段（Shrinking Phase）**：事務可以釋放鎖，但不能獲取新鎖。

通過這種方式，確保了事務執行過程中的鎖請求和釋放的順序，從而避免了死鎖。

**(2) Suppose that processes P1, P2, and P3 have timestamps 35, 50, and 65, respectively. P2 is holding a resource that P1 and P3 want to access. Please show the behavior of these processes in the wait-die and wound-wait schemes. (5%)**

**題目 4.2：假設進程P1、P2和P3的時間戳分別是35、50和65。P2持有一個P1和P3想要訪問的資源。請展示這些進程在等待-死亡和傷害-等待方案中的行為。**

**答案：**

- **等待-死亡（Wait-Die）方案**：
- P1（35）請求P2（50）持有的資源：P1的時間戳小於P2，因此P1等待。
- P3（65）請求P2（50）持有的資源：P3的時間戳大於P2，因此P3死亡並重新嘗試。

- **傷害-等待（Wound-Wait）方案**：
- P1（35）請求P2（50）持有的資源：P1的時間戳小於P2，因此P1傷害P2並獲取資源，P2死亡並重新嘗試。
- P3（65）請求P2（50）持有的資源：P3的時間戳大於P2，因此P3等待。

**(3) Explain real-time, safety-critical, and embedded systems. (6%)**

**題目 4.3：解釋實時系統、安全關鍵系統和嵌入式系統。**

**答案：**

- **實時系統（Real-Time Systems）**：需要在嚴格的時間限制內完成任務的系統，分為硬實時系統和軟實時系統。
- **安全關鍵系統（Safety-Critical Systems）**：系統故障可能導致嚴重後果（如生命危險或重大經濟損失）的系統，要求高可靠性和安全性。
- **嵌入式系統（Embedded Systems）**：專門設計用於特定功能的計算機系統，通常內嵌於更大的系統中，具有資源限制和高效能要求。

**(4) Explain the four commands defined in the real time streaming protocol. (4%)**

**題目 4.4：解釋實時流協議中定義的四個命令。**

**答案：**

實時流協議（RTSP）中定義的四個主要命令是：

1. **SETUP**：初始化傳輸會話，分配資源並設置傳輸參數。
2. **PLAY**：開始或恢復媒體流的播放。
3. **PAUSE**：暫停媒體流的播放。
4. **TEARDOWN**：終止傳輸會話，釋放資源。

### 5. [Protection and Security: 20%]

**(1) Give four benefits of using language-based protection. (4%)**

**題目 5.1：給出使用基於語言的保護的四個好處。**

**答案：**

使用基於語言的保護的四個好處：

1. **細粒度控制**：能夠精確控制對象的訪問權限。
2. **可移植性**：保護機制與操作系統無關，可以在不同平台上使用。
3. **提高安全性**：通過編譯時檢查和運行時檢查，提高系統的安全性。
4. **簡化開發**：提供高層次的抽象，簡化安全性和保護機制的實現。

**(2) Explain the least privilege principle and need-to-know principle. (4%)**

**題目 5.2：解釋最小特權原則和需要知道原則。**

**答案：**

- **最小特權原則（Least Privilege Principle）**：每個用戶或進程應該只擁有完成其任務所需的最小權限，從而減少濫用權限和安全漏洞的風險。
- **需要知道原則（Need-to-Know Principle）**：用戶或進程只應該訪問其工作所需的信息和資源，防止不必要的數據泄露和濫用。

**(3) Give three methods to carry out a protection domain and explain when domain switch occurs. (6%)**

**題目 5.3：給出實現保護域的三種方法，並解釋何時發生域切換。**

**答案：**

實現保護域的三種方法：

1. **基於進程的保護域**：每個進程有自己的保護域，進程切換時發生域切換。
2. **基於用戶的保護域**：每個用戶有自己的保護域，用戶登錄和切換時發生域切換。
3. **基於資源的保護域**：每個資源有自己的保護域，資源分配和釋放時發生域切換。

**(4) Explain Trojan horse, trap door, and stack & buffer overflow. (6%)**

**題目 5.4：解釋特洛伊木馬、陷阱門和堆棧與緩衝區溢出。**

**答案：**

- **特洛伊木馬（Trojan Horse）**：一種惡意軟件，偽裝成有用的程序，一旦執行就會造成破壞或竊取信息。
- **陷阱門（Trap Door）**：在程序或系統中預設的一個秘密入口，允許未經授權的訪問。
- **堆棧與緩衝區溢出（Stack & Buffer Overflow）**：當程序向緩衝區寫入數據超過其邊界時，會覆蓋相鄰內存，可能導致系統崩潰或被攻擊者利用執行任意代碼。

---

# Second Semester of 2022 PhD Qualifying Exam

## Subject: Operating Systems

### 1. [Process: 20%]

**(1) What are the seven major components of a process control block? (7%)**

**題目 1.1：進程控制塊的七個主要組成部分是什麼？**

**答案：**

進程控制塊（PCB）的七個主要組成部分包括：

1. **進程狀態（Process State）**：進程當前的狀態，如運行、就緒、等待等。
2. **程序計數器（Program Counter）**：指示進程下一條將要執行的指令的地址。
3. **CPU寄存器（CPU Registers）**：保存進程運行時使用的各種寄存器的內容。
4. **內存管理信息（Memory Management Information）**：包括基址寄存器、限長寄存器、頁表等內存管理相關的信息。
5. **帳戶信息（Accounting Information）**：包括CPU使用時間、用戶ID、進程優先級等。
6. **I/O狀態信息（I/O Status Information）**：包括分配給進程的I/O設備列表、打開文件列表等。
7. **進程識別符（Process Identifier, PID）**：唯一標識進程的ID。

**(2) What is the priority inversion problem? How to solve it? (3%)**

**題目 1.2：什麼是優先級反轉問題？如何解決？**

**答案：**

優先級反轉問題是指低優先級進程持有資源而阻塞高優先級進程，導致高優先級進程被低優先級進程間接阻塞。解決方法包括：

1. **優先級繼承（Priority Inheritance）**：當高優先級進程被低優先級進程阻塞時，低優先級進程臨時繼承高優先級進程的優先級，直到釋放資源。
2. **優先級天花板協議（Priority Ceiling Protocol）**：在進程獲取資源時，其優先級被提升到高於所有可能使用該資源的進程的優先級。

**(3) What is a critical section? Explain three necessary requirements for any solution to the critical-section problem. (5%)**

**題目 1.3：什麼是臨界區？解釋解決臨界區問題的三個必要條件。**

**答案：**

臨界區是指一段代碼，當一個進程在執行該段代碼時，其他進程不能進入該段代碼執行。解決臨界區問題的三個必要條件是：

1. **互斥（Mutual Exclusion）**：如果一個進程在臨界區內執行，則其他進程不能進入臨界區。
2. **進程（進入）和進程（退出）的進程限制（Progress）**：如果沒有進程在臨界區內且有進程希望進入臨界區，則允許進入臨界區的決策不能無限期地推遲。
3. **有限等待（Bounded Waiting）**：每個進程在請求進入臨界區後，最終都能夠進入臨界區，即確保進程不會遭受饑餓。

**(4) Except CPU’s utilization and throughput, please explain the three criteria to measure the performance of a process scheduling algorithm. (3%)**

**題目 1.4：除了CPU的利用率和吞吐量，請解釋評估進程調度算法性能的三個標準。**

**答案：**

除了CPU的利用率和吞吐量，評估進程調度算法性能的三個標準是：

1. **周轉時間（Turnaround Time）**：從進程提交到完成所需的總時間。
2. **等待時間（Waiting Time）**：進程在就緒隊列中等待的總時間。
3. **響應時間（Response Time）**：從進程提交到第一次獲得CPU執行的時間。

**(5) Is it safe to terminate a thread by invoking the exit() procedure in a multi-threading program? Why or why not? (2%)**

**題目 1.5：在多線程程序中通過調用exit()程序來終止線程是否安全？為什麼？**

**答案：**

在多線程程序中通過調用exit()程序來終止線程是不安全的，因為exit()會終止整個進程，包括所有線程。如果只想終止一個特定的線程，應使用pthread_exit()等線程專用的退出函數。

### 2. [Memory: 20%]

**(1) Please explain three common solutions to the dynamic storage allocation problem in memory. (6%)**

**題目 2.1：請解釋內存動態存儲分配問題的三種常見解決方案。**

**答案：**

內存動態存儲分配問題的三種常見解決方案是：

1. **首次適配（First-Fit）**：從頭開始掃描空閒列表，找到第一個足夠大的空閒塊進行分配。
2. **最佳適配（Best-Fit）**：掃描整個空閒列表，找到最小的足夠大的空閒塊進行分配。
3. **最差適配（Worst-Fit）**：掃描整個空閒列表，找到最大的空閒塊進行分配，以保留大的空閒塊。

**(2) What are the purposes of base and limit registers? (4%)**

**題目 2.2：基址寄存器和限長寄存器的用途是什麼？**

**答案：**

基址寄存器和限長寄存器用於內存保護：

1. **基址寄存器（Base Register）**：存儲進程內存區域的起始地址，所有內存訪問地址必須加上基址寄存器的值。
2. **限長寄存器（Limit Register）**：存儲進程內存區域的大小，用於檢查內存訪問是否越界。

**(3) Please explain how a page-buffering algorithm works. (3%)**

**題目 2.3：請解釋頁緩衝算法如何工作。**

**答案：**

頁緩衝算法在頁替換過程中使用一個緩衝池來存儲被替換的頁。當需要替換一個頁時，首先將其存儲在緩衝池中，而不是立即寫回磁盤。如果稍後需要再次訪問該頁，則可以從緩衝池中快速恢復，減少磁盤I/O。

**(4) What is swap space? What are the two major features of swap space? (3%)**

**題目 2.4：什麼是交換空間？交換空間的兩個主要特徵是什麼？**

**答案：**

交換空間是硬盤上的一部分，用於存儲當前內存中不活躍的頁面。其兩個主要特徵是：

1. **虛擬內存的擴展**：提供比物理內存更大的虛擬內存空間。
2. **內存管理的靈活性**：允許系統在內存不足時將部分內存頁面交換到磁盤上，以釋放物理內存。

**(5) Let memory access time be 200ns and average page fault time be 80μs. If you want EAT below 220ns, what is the expected page fault rate? List your calculation. (4%)**

**題目 2.5：假設內存訪問時間為200ns，平均頁故障時間為80μs。如果你希望EAT低於220ns，預期的頁故障率是多少？列出你的計算過程。**

**答案：**

設頁故障率為 $p$，EAT公式為：
$$
EAT = (1 - p) * Memory Access Time + p * Page Fault Time
$$

代入數據：
$$
220ns = (1 - p) * 200ns + p * 80000ns
$$

解方程：
$$
220 = 200 + p * 79800
$$
$$
20 = p * 79800
$$
$$
p = \frac{20}{79800} \approx 0.0002506
$$

因此，預期的頁故障率約為0.0002506。

### 3. [Storage and I/O: 20%]

**(1) Please explain the two interrupt request lines for a CPU. (4%)**

**題目 3.1：解釋CPU的兩條中斷請求線。**

**答案：**

CPU的兩條中斷請求線是：

1. **IRQ（Interrupt Request Line）**：用於外部設備向CPU發送中斷請求，通知CPU處理事件。
2. **NMI（Non-Maskable Interrupt Line）**：一種不可屏蔽的中斷線，用於處理緊急和高優先級的事件，如硬件故障。

**(2) Consider a disk queue with requests for I/O to blocks on cylinders 110, 175, 48, 120, 31, 138, 75, and 88. Let the disk head currently stay at cylinder 65, and the maximum cylinder be 250. Give the results of SSTF and C-LOOK scheduling methods. (6%)**

**題目 3.2：考慮一個磁盤隊列，請求I/O的磁道號分別為110、175、48、120、31、138、75和88。假設磁頭當前位於磁道65，最大磁道號為250。給出SSTF和C-LOOK調度方法的結果。**

**答案：**

- **SSTF（Shortest Seek Time First）** 調度方法：
1. 65 -> 75
2. 75 -> 88
3. 88 -> 110
4. 110 -> 120
5. 120 -> 138
6. 138 -> 175
7. 175 -> 48
8. 48 -> 31

訪問順序：65, 75, 88, 110, 120, 138, 175, 48, 31

- **C-LOOK（Circular LOOK）** 調度方法：
1. 65 -> 75
2. 75 -> 88
3. 88 -> 110
4. 110 -> 120
5. 120 -> 138
6. 138 -> 175
7. 175 -> 250
8. 31 -> 48

訪問順序：65, 75, 88, 110, 120, 138, 175, 250, 31, 48

**(3) Please explain the following terms: (10%)**

**題目 3.3：解釋以下術語。**

- (a) **mount point**：用於將外部文件系統整合到當前文件系統樹中的位置。
- (b) **seek time**：指磁盤讀寫頭移動到目標磁道所需的時間。
- (c) **rotational latency**：指磁盤旋轉將目標扇區移動到讀寫頭下方所需的時間。
- (d) **vectored I/O**：指一次系統調用操作多個I/O設備或文件的技術。
- (e) **spool**：指將數據從一個設備或程序臨時存儲到中間設備（如磁盤），以便稍後處理。

### 4. [Distributed and Special Systems: 20%]

**(1) Please explain how the deadlock prevention scheme works. (4%)**

**題目 4.1：解釋死鎖預防方案如何工作。**

**答案：**

死鎖預防方案通過破壞死鎖的必要條件來避免死鎖的發生。常見的方法包括：

1. **避免循環等待（Avoid Circular Wait）**：資源按順序編號，進程必須按升序請求資源。
2. **剝奪（Preemption）**：允許高優先級進程剝奪低優先級進程的資源。
3. **限制資源持有（Hold and Wait）**：要求進程在請求資源前釋放所有已持有的資源。
4. **單一資源分配（Single Resource Allocation）**：每個進程一次只能請求一個資源，減少資源衝突的可能性。

**(2) Suppose that processes P1, P2, and P3 have timestamps 29, 40, and 75, respectively. P2 is holding a resource that P1 and P3 want to access. Please show the behavior of these processes in the wait-die and wound-wait schemes. (5%)**

**題目 4.2：假設進程P1、P2和P3的時間戳分別是29、40和75。P2持有一個P1和P3想要訪問的資源。請展示這些進程在等待-死亡和傷害-等待方案中的行為。**

**答案：**

- **等待-死亡（Wait-Die）方案**：
- P1（29）請求P2（40）持有的資源：P1的時間戳小於P2，因此P1等待。
- P3（75）請求P2（40）持有的資源：P3的時間戳大於P2，因此P3死亡並重新嘗試。

- **傷害-等待（Wound-Wait）方案**：
- P1（29）請求P2（40）持有的資源：P1的時間戳小於P2，因此P1傷害P2並獲取資源，P2死亡並重新嘗試。
- P3（75）請求P2（40）持有的資源：P3的時間戳大於P2，因此P3等待。

**(3) What is the difference between stateful and stateless services? (2%)**

**題目 4.3：有狀態服務和無狀態服務的區別是什麼？**

**答案：**

- **有狀態服務（Stateful Services）**：服務器在會話期間維護客戶端的狀態信息，後續的請求可以基於之前的會話上下文進行處理。
- **無狀態服務（Stateless Services）**：服務器不維護客戶端的狀態信息，每個請求都是獨立的，服務器不需要知道之前的請求。

**(4) Please give three requirements of designing a real-time OS. (3%)**

**題目 4.4：請給出設計實時操作系統的三個要求。**

**答案：**

設計實時操作系統的三個要求：

1. **確定性（Determinism）**：系統能夠在預測的時間內完成任務，保證任務在規定的時間限制內執行。
2. **響應性（Responsiveness）**：系統能夠快速響應外部事件，保證低延遲。
3. **可靠性（Reliability）**：系統能夠在長時間運行中保持穩定，確保任務的準確執行。

**(5) Please explain three QoS levels. (6%)**

**題目 4.5：請解釋三個QoS級別。**

**答案：**

三個QoS（服務質量）級別：

1. **最佳努力（Best Effort）**：不保證服務質量，盡最大努力傳輸數據，適用於對延遲和帶寬要求不高的應用。
2. **差分服務（Differentiated Services, DiffServ）**：根據優先級標籤對數據包進行分類和處理，提供不同等級的服務質量保證。
3. **綜合服務（Integrated Services, IntServ）**：通過資源預留和流量控制，為每個數據流提供端到端的服務質量保證，適用於對延遲和帶寬有嚴格要求的應用。

### 5. [Protection & Security: 20%]

**(1) Please give four benefits of using language-based protection. (4%)**

**題目 5.1：給出使用基於語言的保護的四個好處。**

**答案：**

使用基於語言的保護的四個好處：

1. **細粒度控制**：能夠精確控制對象的訪問權限。
2. **可移植性**：保護機制與操作系統無關，可以在不同平台上使用。
3. **提高安全性**：通過編譯時檢查和運行時檢查，提高系統的安全性。
4. **簡化開發**：提供高層次的抽象，簡化安全性和保護機制的實現。

**(2) How do UNIX and Windows NT systems defend against fake login programs? (4%)**

**題目 5.2：UNIX和Windows NT系統如何防禦假登錄程序？**

**答案：**

- **UNIX系統**：通過限制對系統文件（如 /etc/passwd 和 /etc/shadow）的訪問權限，防止未經授權的修改；並使用 su 和 sudo 命令，提供受控的特權提升機制。
- **Windows NT系統**：使用安全登錄屏幕（Ctrl+Alt+Del）來防止假登錄程序，並通過安全識別（Secure Identification）和驗證機制來驗證用戶身份。

**(3) How does message-authentication code work? (4%)**

**題目 5.3：消息認證碼如何工作？**

**答案：**

消息認證碼（MAC）通過將消息和一個秘密密鑰一起輸入到MAC算法中，生成一個固定長度的認證碼。這個認證碼用於驗證消息的完整性和真實性。只有持有相同密鑰的接收方才能生成和驗證該認證碼，從而確保消息未被篡改。

**(4) Please explain the two capabilities defined in the Cambridge CAP system. (4%)**

**題目 5.4：請解釋劍橋CAP系統中定義的兩個能力。**

**答案：**

劍橋CAP系統中定義的兩個能力是：

1. **數據能力（Data Capability）**：允許持有者訪問特定的數據對象，如文件或數據塊。數據能力包括對象的標識符和訪問權限。
2. **軟件能力（Software Capability）**：允許持有者調用特定的程序或服務。軟件能力包括程序的入口點和執行權限。

**(5) How do tunneling and armored viruses avoid detection by an antivirus scanner? (4%)**

**題目 5.5：隧道病毒和裝甲病毒如何避開殺毒軟件的檢測？**

**答案：**

- **隧道病毒（Tunneling Virus）**：通過攔截和修改操作系統的中斷向量表或系統調用表，避開殺毒軟件的檢測。
- **裝甲病毒（Armored Virus）**：使用代碼混淆、加密和反調試技術，增加逆向工程和分析的難度，從而避開殺毒軟件的檢測。

---

# First Semester of 2022 PhD Qualifying Exam

## Subject: Operating Systems

### 1. (10%)

**What are the necessary conditions for a deadlock to occur in a system?**

**題目 1：系統發生死鎖的必要條件是什麼？**

**答案：**

死鎖發生的四個必要條件是：

1. **互斥（Mutual Exclusion）**：資源是獨占的，即每個資源在同一時間只能被一個進程使用。
2. **保持和等待（Hold and Wait）**：進程已經持有至少一個資源，並且在等待額外的資源。
3. **不可剝奪（No Preemption）**：資源不能被強制剝奪，必須由持有該資源的進程顯式釋放。
4. **循環等待（Circular Wait）**：存在一個進程集合，集合中的每個進程都在等待下一個進程所持有的資源，形成一個環路。

### 2. (20%; 10% each)

**Suppose that a scheduler has $k$ ready processes at time 0 and that no new processes are created after time 0. Process $i (0 < i \leq k)$ requires $i$ units of computing time. Answer each of the following questions.**

**(a) For a preemptive, round-robin scheduler with a scheduling quantum of one time unit, what is the mean turnaround time for these processes, assuming that process $k$ is at the front of the ready queue and that other processes appear in decreasing order of required computing time?**

**(b) For a non-preemptive, shortest-job-first scheduler, what is the mean turnaround time for these processes?**

**題目 2：假設調度程序在時間0有$k$個準備好的進程，且在時間0之後沒有新進程創建。進程$i (0 < i \leq k)$需要$i$個計算時間。回答以下每個問題。**

**(a) 對於具有一個時間單位調度量的搶占式、輪轉調度程序，這些進程的平均周轉時間是多少，假設進程$k$在準備隊列的前面，其他進程按所需計算時間遞減的順序出現？**

**(b) 對於非搶占式、最短作業優先調度程序，這些進程的平均周轉時間是多少？**

**答案：**

(a) 對於搶占式輪轉調度，平均周轉時間計算如下：

$$
T_{i} = \left( i + \left\lfloor \frac{k-1}{k} \right\rfloor + (i-1) \cdot q \right)
$$

$$
T = \frac{1}{k} \sum_{i=1}^{k} T_{i}
$$

(b) 對於非搶占式最短作業優先調度，平均周轉時間計算如下：

$$
T_{i} = \sum_{j=1}^{i} j
$$

$$
T = \frac{1}{k} \sum_{i=1}^{k} T_{i} = \frac{1}{k} \left( \frac{k(k+1)(k+2)}{6} \right)
$$

### 3. (10%; 5% each)

**Consider the two-dimensional array $a$:**
**題目 3：考慮二維數組$a$：**

double a[][] = new double[250][250];

**where each double occupies 8 bytes and $a[0][0]$ is at location 200,
in a paged system with pages of size 200 bytes.
A small process is in page 0 (locations 0 to 199) for manipulating the matrix;
thus, every instruction fetch will be from page 0. For three page frames,
how many page faults are generated by the following array initialization loops,
using LRU replacement and assuming
(1) page frame 0 has the process in it,
(2) the other two are initially empty,
(3) the array is stored in memory column-major.
Justify your answer for full credit.**

**每個double佔8字節，且$a[0][0]$位於地址200，在頁大小為200字節的頁系統中。
小進程在頁0（地址0到199）中操作矩陣；因此，每次指令獲取都來自頁0。
對於三個頁框，使用LRU替換和假設
（1）頁框0中有進程，
（2）其他兩個初始為空，
（3）數組按列主存儲，
以下數組初始化循環會產生多少頁故障。**

(a) for (int i = 0; i < 250; i++)
        for (int j = 0; j < 250; j++)
            a[i][j] = 0;

(b) for (int j = 0; j < 250; j++)
        for (int i = 0; i < 250; i++)
        a[i][j] = 0;

**答案：**

(a) 列主存儲，按行遍歷會導致大量頁故障。每一列的元素跨越多個頁，所以每次訪問新行時都會引起頁故障。總共會產生62,500次頁故障。

(b) 由於遍歷順序與存儲順序匹配，僅在第一次訪問新頁時產生頁故障。總共會產生250次頁故障。

### 4. (20%; 4% each)

**Consider a file currently consisting of 150 blocks. Assume that the file control block is already in memory. Calculate how many disk I/O operations are required for contiguous and linked allocation strategies, if, for one block, the following conditions hold. In the contiguous allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.**

**(a) The block is removed from the beginning.**

**(b) The block is removed from the end.**

**(c) The block is added at the beginning.**

**(d) The block is added in the middle.**

**(e) The block is added at the end.**

**題目 4：考慮當前由150個塊組成的文件。假設文件控制塊已在內存中。計算連續和鏈接分配策略下，需要多少磁盤I/O操作來處理一個塊，假設以下條件成立。在連續分配情況下，假設開始時沒有空間增長，但結束時有空間增長。假設要添加的塊信息存儲在內存中。**

**(a) 塊從開頭移除。**

**(b) 塊從結尾移除。**

**(c) 塊在開頭添加。**

**(d) 塊在中間添加。**

**(e) 塊在結尾添加。**

**答案：**

(a) **連續分配：** 需要重新安排所有後續塊，總共需要150次I/O操作。**鏈接分配：** 只需要修改控制信息，需要1次I/O操作。

(b) **連續分配：** 只需修改文件控制塊即可，總共需要1次I/O操作。**鏈接分配：** 只需要修改控制信息，需要1次I/O操作。

(c) **連續分配：** 需要重新安排所有後續塊，總共需要150次I/O操作。**鏈接分配：** 只需要修改控制信息，需要1次I/O操作。

(d) **連續分配：** 需要重新安排所有後續塊，總共需要150次I/O操作。**鏈接分配：** 只需要修改控制信息，需要1次I/O操作。

(e) **連續分配：** 只需修改文件控制塊即可，總共需要1次I/O操作。**鏈接分配：** 只需要修改控制信息，需要1次I/O操作。

### 5. (10%)

**What is the purpose of the volatile keyword in C?**

**題目 5：C語言中的volatile關鍵字的作用是什麼？**

**答案：**

`volatile`關鍵字告訴編譯器該變量的值可能在任何時刻被其他進程或硬件修改，因此編譯器不應對該變量進行優化。這確保了每次訪問該變量時都會讀取最新的值，而不是使用緩存的值。

### 6. (20%; 5% each)

**Given an i-node with ten direct blocks and three levels of indirect blocks and assuming that the sizes of a pointer and a block are, respectively, 4 bytes and 4 Kbytes, answer the following questions. Justify your answer for full credit.**

**(a) What would be the size of the smallest file allowed in bytes?**

**(b) What would be the size of the largest file allowed in bytes?**

**(c) How many blocks are needed for a file of size 2138112 bytes?**

**(d) How many blocks are needed for a file of size 4239360 bytes?**

**題目 6：給定一個具有十個直接塊和三個級別的間接塊的i-node，並假設指針和塊的大小分別為4字節和4 Kbytes，回答以下問題。**

**(a) 允許的最小文件大小是多少字節？**

**(b) 允許的最大文件大小是多少字節？**

**(c) 需要多少個塊來存儲大小為2138112字節的文件？**

**(d) 需要多少個塊來存儲大小為4239360字節的文件？**

**答案：**

(a) **最小文件大小**：一個塊的大小，即4KB。

(b) **最大文件大小**：
$$
\text{Direct blocks} = 10 \times 4 \text{KB} = 40 \text{KB} \\
$$
$$
\text{Single indirect blocks}
= 4 \text{KB} \times \frac{4 \text{KB}}{4 \text{bytes}} = 4 \text{KB} \times 1024 = 4 \text{MB} \\
$$
$$
\text{Double indirect blocks}
= 4 \text{KB} \times \left( \frac{4 \text{KB}}{4 \text{bytes}} \right)^2 = 4 \text{KB} \times 1024^2 = 4 \text{GB} \\
$$
$$
\text{Triple indirect blocks}
= 4 \text{KB} \times \left( \frac{4 \text{KB}}{4 \text{bytes}} \right)^3 = 4 \text{KB} \times 1024^3 = 4 \text{TB} \\
$$
$$
\text{Total}
= 40 \text{KB} + 4 \text{MB} + 4 \text{GB} + 4 \text{TB}
$$

(c) **2138112字節文件需要的塊數**：
$$
2138112 \text{bytes} = 523 \text{blocks}
$$

(d) **4239360字節文件需要的塊數**：
$$
4239360 \text{bytes} = 1036 \text{blocks}
$$

### 7. (10%)

**What would be the output of the following C program? (Note that the line numbers are for reference only.) Justify your answer for full credit.**

**題目 7：以下C程序的輸出是什麼？（注意：行號僅供參考。）**

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main() {
    int status, fd[2];
    pipe(fd);
    pid_t pid = fork();
    if (pid > 0) {
        close(fd[1]);
        close(0);
        dup(fd[0]);
        close(fd[0]);
        waitpid(-1, &status, 0);
        char buf[128];
        int n = scanf("%s", buf);
        printf("%d:%s\n", n, buf);
    } else if (pid == 0) {
        close(fd[0]);
        close(1);
        dup(fd[1]);
        close(fd[1]);
        execl("/bin/echo", "echo", "how", "are", "you?", (void *)0);
    } else {
        return 1;
    }
    return 0;
}

**答案：**

程序的輸出將是

1:how

父進程從管道中讀取子進程的輸出，
而子進程使用execl執行echo命令並將"how are you?"寫入管道。
父進程使用scanf從管道中讀取一個單詞"how"並打印出來。