OS 109年歷屆詳解

# OS 109年歷屆詳解 ## **1. 當發生頁的來回動盪 (Page Thrashing) 時，請選出正確的敘述？** ✅ a. 減少多重程序 (Multiprogramming) 之程度 (degree) 可緩解此現象 ✅ b. CPU 使用率會急速下降 ✅ c. IO 裝置會異常忙碌 ✅ d. 處理程序在頁錯誤的處理時間，遠大於正常執行時間 --- 這題主要討論「頁面置換過度（Page Thrashing）」的現象與解決方案。當發生頁面置換過度時，系統的資源會大量耗費在頁面交換（Page Swapping）上，導致整體性能下降。以下是各選項的分析： ### 題目選項分析： 1. **a. 減少多重程序（Multiprogramming）之程度（Degree）可緩解此現象** **正確**：減少多重程序的數量（也就是降低同時執行的程序數量），可以減少內存的壓力，從而降低頁面置換過度的情況。 2. **b. CPU 使用率會急速下降** **正確**：當系統處於頁面置換過度時，CPU會等待大量的I/O操作完成，無法有效執行程序，導致CPU使用率急劇下降。 3. **c. I/O裝置會異常忙碌** **正確**：由於頁面頻繁置換，I/O裝置（例如硬碟）將變得極為忙碌，以處理這些頁面的交換。 4. **d. 處理程序在頁錯誤的處理時間，遠大於正常執行時間** **正確**：頁面置換過度會導致處理程序花費大量時間處理頁錯（Page Fault），甚至超過正常執行所需的時間。 --- ## **2. 有關作業系統之分層結構 (Layer Approach)，請選出正確的敘述？** 🔲 a. 內層可以呼叫外層 ✅ b. 外層可以一層一層往內層呼叫 🔲 c. 外層可以一箭穿心直接呼叫深層 ✅ d. 可以將某一層抽離替新，而不會影響其他層以下是對這道題的詳盡解析，並用 **✅** 和 **🔲** 來標示正確與錯誤的選項： --- 🔲 **a. 內層可以呼叫外層** **解析：** 錯誤，分層結構的基本原則是「內層提供服務給外層使用」，內層不能主動呼叫外層，否則會破壞層次結構的封裝性和模組化特性。內層的功能應該對外層完全透明。 --- ✅ **b. 外層可以一層一層往內層呼叫** **解析：** 正確，分層結構的核心特性就是外層只能透過一層一層地向內層發出請求，而不能跳過中間層直接進行操作。這樣的設計提高了模組化，使每一層的責任劃分更加清晰。 --- 🔲 **c. 外層可以一箭穿心直接呼叫深層** **解析：** 錯誤，分層結構不允許外層跳過中間層直接呼叫更深層，這樣會破壞分層設計的封裝性，導致設計混亂，耦合度升高，進而難以維護。正確的方式應是逐層傳遞請求。 --- ✅ **d. 可以將某一層抽離替新，而不會影響其他層** **解析：** 正確，分層結構的一大優勢是每層彼此獨立，只要接口（Interface）保持不變，便可以替換某一層的實現，而不影響其他層的功能。這大大提高了系統的靈活性和可維護性。 --- ## **3. 有關作業系統的說明，請選出正確的敘述？** a. ✅ 分散式系統 (Distributed System) 是一種鬆散性系統 (Loosely Coupled System) b. 🔲 多重程序 (Multiprogramming) 系統一定提供分時 (Time Sharing) 的功能 c. ✅ 週邊設備線上同時工作 (Spooling) 是一種可用來解決共用專屬設備的機制 d. ✅ 硬性即時 (Hard Real Time) 系統必須在限制的時效內，即時反應並完成所有處理工作 --- ### **題目解析** #### **a. 分散式系統 (Distributed System) 是一種鬆散性系統 (Loosely Coupled System)** **正確 ✅** 分散式系統由多個獨立計算機系統組成，這些系統通過網路連接來協調工作，形成一個鬆散耦合的系統。這種設計可以提高系統的可靠性與擴展性，因為每個節點是獨立的，即使某些節點發生故障，系統仍可繼續運作。 --- #### **b. 多重程序 (Multiprogramming) 系統一定提供分時 (Time Sharing) 的功能** **錯誤 🔲** 多重程序是一種允許多個程序同時駐留在內存中的技術，用於提高CPU利用率，但它不一定會提供分時功能。分時系統是一種特定的多重程序系統，允許多個使用者共享CPU時間，因此不是所有多重程序系統都必須支持分時功能。 --- #### **c. 週邊設備線上同時工作 (Spooling) 是一種可用來解決共用專屬設備的機制** **正確 ✅** Spooling（Simultaneous Peripheral Operation On-line）是一種緩存機制，常用於解決多個程序同時訪問同一設備（如印表機）時的競爭問題。數據先被暫存到磁碟或內存中，然後設備依序處理，從而提高效率並避免衝突。 --- #### **d. 硬性即時 (Hard Real Time) 系統必須在限制的時效內，即時反應並完成所有處理工作** **正確 ✅** 硬性即時系統對時效性要求極高，任何處理任務都必須在規定的期限內完成，否則會導致系統故障（如醫療設備或飛機導航系統）。這種系統的可靠性和準確性極為重要。 --- ## **4. 有關邏輯地址 (Logical Address) 與實體地址 (Physical Address) 之轉換，假設某電腦系統的邏輯地址共有 32 bits，頁的大小 (Page Size) 為 4KB，最大主記憶體 (Main Memory) 的大小為 16GB，且系統以 Byte 為定址基本單位。請選出正確的推算？** a. 🔲 實體地址共占用 32 bits b. ✅ Page offset 會佔用 12 bits c. ✅ 主記憶體總共可以切割出 2 的 22 次方 (2^22) 個頁框 (Page Frame) d. ✅ 頁表格 (Page Table) 總共可以有 2 的 20 次方 (2^20) 筆記錄 (Entry) --- ### **解析：** #### **a. 實體地址共占用 32 bits** **錯誤 🔲** 主記憶體大小為 16GB，計算所需實體地址的位元數如下： $16GB = 16 \times 2^{30} \, \text{Bytes} = 2^{34} \, \text{Bytes}$ 因此，實體地址需要 **34 bits**，而不是 32 bits。 --- #### **b. Page offset 會佔用 12 bits** **正確 ✅** 頁的大小為 4KB，即$2^{12} \, \text{Bytes}$。Page offset 用於定位頁內的偏移量，因此需要 **12 bits** 表示。 --- #### **c. 主記憶體總共可以切割出 2 的 22 次方 (2^22) 個頁框 (Page Frame)** **正確 ✅** 主記憶體大小為 16GB，頁的大小為 4KB，因此主記憶體可以被分割為： $\frac{\text{16GB}}{\text{4KB}} = \frac{2^{34}}{2^{12}} = 2^{22} \, \text{頁框 (Page Frame)}$ 因此，主記憶體可以分割出 **2 的 22 次方頁框**。 --- #### **d. 頁表格 (Page Table) 總共可以有 2 的 20 次方 (2^20) 筆記錄 (Entry)** **正確 ✅** 邏輯地址共有 32 bits，其中 Page offset 佔用 12 bits，剩餘的 $32 - 12 = 20 \, \text{bits}$ 用於頁的編號（Page Number）。因此，頁表格需要記錄 $2^{20} \, \text{筆 Entry}$ 對應的實體頁框。 --- ## **5. 根據處理程序 (Process) 的狀態變化圖，請選出會發生環境切換 (Context Switch) 的情況？** a. ✅ 時間片段 (Time Slice) 用盡時 b. ✅ 須執行 I/O 而進入隱置狀態 (Blocked State) 時 c. 🔲 等待事件已完成而進入備妥狀態 (Ready State) 時 d. ✅ 某工作執行結束而 CPU 要換下一個工作執行時 --- ### **解析** #### **a. 時間片段 (Time Slice) 用盡時** **正確 ✅** 當處理程序執行時間片 (Time Slice) 用盡時，CPU 將停止當前程序的執行，進行 **Context Switch (環境切換)**，將 CPU 分配給其他處於 Ready 狀態的程序。 --- #### **b. 須執行 I/O 而進入隱置狀態 (Blocked State) 時** **正確 ✅** 當前程序需要執行 I/O 時，會進入 Blocked 狀態以等待 I/O 完成。此時，CPU 將進行 Context Switch，切換到其他程序執行，避免資源閒置。 --- #### **c. 等待事件已完成而進入備妥狀態 (Ready State) 時** **錯誤 🔲** 當程序從 Blocked 狀態轉為 Ready 狀態時，它只是回到準備執行的狀態，但並不需要立即進行 Context Switch。CPU 會根據排程策略決定何時切換到該程序。 --- #### **d. 某工作執行結束而 CPU 要換下一個工作執行時** **正確 ✅** 當一個程序執行完畢後，CPU 需要選擇另一個 Ready 狀態的程序來執行，這會觸發 Context Switch。 --- ### **補充說明：環境切換 (Context Switch) 的定義** Context Switch 是指當 CPU 需要從一個進程切換到另一個進程時，保存當前進程的執行狀態，並加載新進程的執行狀態的過程。以下是常見觸發情況： 1. **時間片用盡：** 在分時系統中，CPU 時間片到期，需要切換到其他程序。 2. **I/O 請求：** 當程序需要執行 I/O 操作而進入 Blocked 狀態時，CPU 會切換到其他程序執行。 3. **程序結束：** 當前程序執行完畢後，CPU 需要執行其他程序。 4. **優先級調度：** 當有更高優先級的程序需要執行時，系統會進行 Context Switch。 --- ## **6. 有關記憶體管理方法，請選出正確的敘述？** a. ✅ 分頁法 (Paging) 可消除外部支離破碎 (External Fragmentation) b. 🔲 分頁法 (Paging) 可消除內部支離破碎 (Internal Fragmentation) c. 🔲 分段法 (Segmentation) 可消除內部支離破碎 (Internal Fragmentation) d. ✅ 可重定位分割法 (Relocatable Partition) 可消除外部支離破碎 (External Fragmentation) --- ### **解析** #### **a. 分頁法 (Paging) 可消除外部支離破碎 (External Fragmentation)** **正確 ✅** 分頁法將內存劃分為固定大小的頁框 (Page Frames)，程序被切割為固定大小的頁 (Pages)，並動態分配到頁框中，這樣可以充分利用內存，消除外部支離破碎。 --- #### **b. 分頁法 (Paging) 可消除內部支離破碎 (Internal Fragmentation)** **錯誤 🔲** 雖然分頁法可以解決外部支離破碎，但可能會導致內部支離破碎。當程序大小不是頁大小的整數倍時，最後一頁的部分空間會被浪費，這是內部支離破碎的一種形式。 --- #### **c. 分段法 (Segmentation) 可消除內部支離破碎 (Internal Fragmentation)** **錯誤 🔲** 分段法 (Segmentation) 根據程序的邏輯分段來分配內存（如代碼段、數據段等）。由於每個段的大小可變，這會導致內部支離破碎（因為段之間可能會出現空隙）。分段法無法完全消除內部支離破碎。 --- #### **d. 可重定位分割法 (Relocatable Partition) 可消除外部支離破碎 (External Fragmentation)** **正確 ✅** 可重定位分割法允許作業系統動態壓縮記憶體，將所有程序重新定位到連續的內存區域，從而消除外部支離破碎。這種方法需要硬體支援（如基址暫存器和界限暫存器）。 --- ### **支離破碎的補充說明** 1. **外部支離破碎 (External Fragmentation)：** - 因為內存分配不連續，導致無法使用的空間分散於內存中。 - 分頁法可以解決外部支離破碎。 2. **內部支離破碎 (Internal Fragmentation)：** - 因為分配的內存空間比實際需求大，導致分配的空間內有未使用的部分被浪費。 - 分段法和分頁法可能都會出現內部支離破碎。 ### **內部支離破碎 vs. 外部支離破碎** | **類型** | **描述** | **如何發生** | **解決方法** | |-----------------------|---------------------------------------------------------------|------------------------------------------------|-----------------------| | **內部支離破碎** | 分配的內存空間大於實際需求，未使用部分浪費。 | 程序大小無法整除分配單位大小（如頁框大小）。 | 動態分配、更小的單位。 | | **外部支離破碎** | 記憶體雖然有足夠空間，但因不連續無法分配給需要連續內存的程序。 | 動態分配和釋放內存導致出現分散小塊。 | 分頁法、壓縮記憶體等。 | <table border="1"> <thead> <tr> <th>支離破碎問題</th> <th>發生情況</th> <th>解決方式</th> </tr> </thead> <tbody> <tr> <td><b>外部 (External)</b></td> <td>單一分割 (Single Partition)<br> 固定分割 (Fixed Partition)<br> 動態分割法無緊縮 (Variable Partition w/o Compaction)</td> <td>動態分割法 + 緊縮 (Variable Partition with Compaction)<br> 虛擬記憶體 (Virtual Memory)</td> </tr> <tr> <td><b>內部 (Internal)</b></td> <td>分頁法 (Paging)<br> 分割法 (Partition)</td> <td><br> 分段法(Segmentation) 可重定位分割法 (Relocatable Partition)</td> </tr> </tbody> </table> --- ## **7. 有關直接記憶體存取 (Direct Memory Access, DMA)，請選出正確的敘述？** a. 🔲 DMA 發生時，必須儲存 CPU 狀態 b. 🔲 DMA 執行過程，CPU 必須負責 I/O 裝置與記憶體之間的資料傳輸 c. ✅ 適用於一次傳送大量資料 d. ✅ 有助於減少 CPU 被中斷的次數 --- ### **解析** #### **a. DMA 發生時，必須儲存 CPU 狀態** **錯誤 🔲** DMA 的目的是讓 I/O 裝置能直接與記憶體交互，而無需經過 CPU。這過程不會涉及 CPU 狀態的保存，因為 DMA 控制器負責處理數據傳輸。 --- #### **b. DMA 執行過程，CPU 必須負責 I/O 裝置與記憶體之間的資料傳輸** **錯誤 🔲** 在 DMA 傳輸中，CPU 不參與具體的數據傳輸工作。DMA 控制器直接負責 I/O 裝置與記憶體之間的數據交換，這也是 DMA 減少 CPU 負擔的關鍵功能。 --- #### **c. 適用於一次傳送大量資料** **正確 ✅** DMA 非常適合用於傳輸大量數據，例如硬碟到記憶體、記憶體到網卡等，因為它可以繞過 CPU，直接執行數據交換，提高效率。 --- #### **d. 有助於減少 CPU 被中斷的次數** **正確 ✅** DMA 的優勢在於可以減少 CPU 的中斷處理次數。傳統的數據傳輸需要 CPU 持續處理 I/O 中斷，而 DMA 僅需在傳輸完成或發生錯誤時通知 CPU，顯著降低中斷頻率。 --- ### **補充：DMA 的作用與優勢** 1. **作用：** - DMA 是一種記憶體存取方式，允許外部裝置（如硬碟、網卡）繞過 CPU，直接與記憶體交換數據。 - 這由 DMA 控制器 (DMA Controller) 負責操作，CPU 僅需初始化 DMA 控制器，設定傳輸參數（如源地址、目標地址和數據大小）。 2. **優勢：** - **減少 CPU 負擔：** CPU 不再參與具體的數據傳輸，提升系統整體效率。 - **降低中斷頻率：** 僅在必要時通知 CPU，而不是每次數據傳輸都中斷。 - **提升傳輸速度：** DMA 適用於大量數據的高效傳輸。 --- ## **8. 有關處理程序 (Process) 內的執行緒 (Thread)，請選出正確的敘述？** a. ✅ 執行緒各自擁有其專屬 Register、Stack、Program Counter b. ✅ CPU 以處理程序為單元進行排程及環境切換 c. ✅ 處理程序會將分配到的 CPU 時間，分享給它的執行緒使用 d. 🔲 處理程序內的多個執行緒不會共用相同的地址空間 (Address Space) --- ### **解析** #### **a. 執行緒各自擁有其專屬 Register、Stack、Program Counter** **正確 ✅** 每個執行緒都有自己獨立的執行狀態，包括： - **暫存器 (Registers)**：保存執行緒的執行上下文。 - **堆疊 (Stack)**：用於儲存函數呼叫、局部變數和返回地址。 - **程序計數器 (Program Counter, PC)**：記錄執行緒當前執行的指令地址。這些資源確保執行緒能夠單獨執行而不影響其他執行緒。 --- #### **b. CPU 以處理程序為單元進行排程及環境切換** **正確 ✅** 操作系統通常以處理程序為單位進行排程和環境切換。當分配到處理程序後，該程序內的執行緒會共享該 CPU 時間，並由程序內部管理執行緒的切換。 --- #### **c. 處理程序會將分配到的 CPU 時間，分享給它的執行緒使用** **正確 ✅** 處理程序內的多個執行緒共享該程序的 CPU 時間。例如，在多執行緒的程序中，CPU 時間會由程序內的執行緒協作使用，這樣每個執行緒可以同時執行部分任務。 --- #### **d. 處理程序內的多個執行緒不會共用相同的地址空間 (Address Space)** **錯誤 🔲** 處理程序內的多個執行緒會共享相同的地址空間，包括代碼段、資料段和堆區（Code, Data, Heap）。 - **共享資源：** 內存地址空間、全域變數和靜態變數。 - **專屬資源：** 每個執行緒有自己獨立的堆疊和暫存器。共享地址空間是執行緒通信高效的原因，但也需要進行同步以避免競態條件。 --- ### **補充：執行緒與處理程序的對比** | **特性** | **處理程序 (Process)** | **執行緒 (Thread)** | |------------------------|----------------------------------------|---------------------------------------------| | **定義** | 資源分配的基本單位 | 程序內部的執行單元 | | **地址空間** | 各處理程序獨立，彼此不共享 | 同一程序內的執行緒共享地址空間 | | **切換成本** | 高，需保存和切換完整程序的執行狀態 | 低，僅需切換堆疊和暫存器 | | **通信成本** | 高，需通過 IPC (訊息佇列、管道等) | 低，共享內存直接通信 | --- ## **9. 關於死結 (Deadlock) 的說明，請選出正確的敘述？** a. 🔲 只要產生擁有和等待 (Hold & Wait) 發生時，表示一定產生死結 b. ✅ 資源配置圖中若沒有形成循環圈 (Cycle)，表示一定沒有發生死結 c. 🔲 資源配置圖中只要有循環圈 (Cycle) 存在，表示一定發生死結 d. ✅ 發生死結，表示資源配置圖中一定有產生循環圈 (Cycle) --- ### **解析** #### **a. 只要產生擁有和等待 (Hold & Wait) 發生時，表示一定產生死結** **錯誤 🔲** 雖然「擁有並等待」是死結發生的必要條件之一，但並不是單憑這一條件就能判斷一定會發生死結，還需要滿足其他三個條件（互斥、不可剝奪、循環等待）。 --- #### **b. 資源配置圖中若沒有形成循環圈 (Cycle)，表示一定沒有發生死結** **正確 ✅** **循環圈 (Cycle)** 是死結發生的充分條件，如果資源配置圖中不存在循環圈，那麼就不可能發生死結。因此，若沒有循環圈，則可以肯定沒有死結。 --- #### **c. 資源配置圖中只要有循環圈 (Cycle) 存在，表示一定發生死結** **錯誤 🔲** **有循環圈不一定代表有死結**，因為有些系統可能是可搶佔的（Preemptive），在某些情況下，系統可以打破循環圈。例如： - 資源可以被強制釋放（可搶佔）。 - 有些程序可能在等待資源時自動超時並釋放已占有的資源。 --- #### **d. 發生死結，表示資源配置圖中一定有產生循環圈 (Cycle)** **正確 ✅** 死結發生的必要條件之一是「循環等待」，這意味著資源配置圖中一定有循環圈。因此，如果發生了死結，循環圈必然存在。 --- ### **補充：死結的四個必要條件** 1. **互斥 (Mutual Exclusion)：** 每個資源在同一時間只能被一個進程使用。 2. **擁有並等待 (Hold & Wait)：** 進程已經擁有某些資源，並在等待其他進程釋放其所需的資源時，不會釋放已占有的資源。 3. **不可剝奪 (No Preemption)：** 已分配的資源不能被強制剝奪，只有當進程釋放資源時，資源才能被重新分配給其他進程。 4. **循環等待 (Circular Wait)：** 存在一組進程，每個進程都在等待另一個進程持有的資源，形成一個閉環。 --- ## **10. 有關檔案系統的管理，請選出正確的敘述？** a. ✅ 連續配置法 (Contiguous Allocation) 會有外部支離破碎 (External Fragmentation) 問題 b. ✅ 連結配置法 (Linked Allocation) 會有內部支離破碎 (Internal Fragmentation) 問題 c. 🔲 索引配置法 (Indexed Allocation) 會有內部支離破碎 (Internal Fragmentation) 問題 d. 🔲 索引配置法 (Indexed Allocation) 只能進行循序存取，無法作直接存取 --- ### **解析** #### **a. 連續配置法 (Contiguous Allocation) 會有外部支離破碎 (External Fragmentation) 問題** **正確 ✅** 連續配置法要求檔案在磁碟上分配一塊連續的區域。如果新的檔案需要的空間大於現有連續空閒區域，則無法分配，即使總空間足夠，這就是外部支離破碎問題的來源。 --- #### **b. 連結配置法 (Linked Allocation) 會有內部支離破碎 (Internal Fragmentation) 問題** **正確 ✅** 連結配置法將檔案分成多個區塊，每個區塊包含一部分數據並指向下一個區塊。由於每個區塊大小固定，檔案可能會填不滿最後一個區塊，造成內部支離破碎。 --- #### **c. 索引配置法 (Indexed Allocation) 會有內部支離破碎 (Internal Fragmentation) 問題** **錯誤 🔲** 索引配置法將檔案的所有區塊索引存放在一個索引表中，每個區塊都可單獨分配。由於區塊分配完全不依賴固定大小，因此不會造成內部支離破碎。 --- #### **d. 索引配置法 (Indexed Allocation) 只能進行循序存取，無法作直接存取** **錯誤 🔲** 索引配置法支援**隨機存取**，因為索引表記錄了每個區塊的位置，系統可以直接從索引表中找到所需區塊，而不需要依序遍歷其他區塊。 --- ### **補充：三種檔案配置方法的比較** | **配置方法** | **特性** | **問題** | |-------------------------|------------------------------------------------------------------------|------------------------------------------| | **連續配置法 (Contiguous Allocation)** | 檔案存放在磁碟上一塊連續的空間，支援高效的直接存取和循序存取。 | 外部支離破碎；分配新檔案困難；需事先確定檔案大小。 | | **連結配置法 (Linked Allocation)** | 檔案由許多區塊組成，每個區塊包含指向下一個區塊的指標，適合循序存取。 | 指標佔用額外空間；不支援高效的隨機存取。 | | **索引配置法 (Indexed Allocation)** | 建立一個索引表，記錄檔案的所有區塊位置，支援高效的直接存取和循序存取。 | 索引表佔用額外空間；小檔案可能導致索引表浪費。 | --- ## **11. 在一個作業系統內，若出現 I/O Bound Processes 比 CPU Bound Processes 多，請選出正確的敘述？** a. 🔲 CPU 所作事請較多 b. ✅ CPU 所作事請較少 c. 🔲 I/O 所作事請較少 d. ✅ I/O 所作事請較多 --- ### **解析** #### **關鍵概念：I/O Bound Process 和 CPU Bound Process** 1. **I/O Bound Process：** - **特徵：** 這類程序執行的多數時間都在等待 I/O 操作完成（如讀寫磁碟或網絡操作）。 - **CPU 使用：** 極少需要 CPU 處理，I/O 操作是性能的主要瓶頸。 2. **CPU Bound Process：** - **特徵：** 這類程序執行的多數時間都在進行計算，需要大量 CPU 運算。 - **I/O 使用：** 很少進行 I/O 操作。 --- ### **選項解析** #### **a. CPU 所作事請較多** **錯誤 🔲** 若系統內 I/O Bound Processes 比 CPU Bound Processes 多，大部分程序的時間都花在等待 I/O 操作，而不是使用 CPU，因此 CPU 所作的事請會減少。 --- #### **b. CPU 所作事請較少** **正確 ✅** 因為 I/O Bound Processes 比 CPU Bound Processes 多，CPU 的使用需求減少，CPU 處於閒置狀態的時間增加，因此 CPU 所作事請較少。 --- #### **c. I/O 所作事請較少** **錯誤 🔲** I/O Bound Processes 比例增加，意味著系統的大部分程序都在進行 I/O 操作，因此 I/O 所作事請會明顯增加，而不是減少。 --- #### **d. I/O 所作事請較多** **正確 ✅** 由於 I/O Bound Processes 比例更高，系統中大量的程序依賴於 I/O 操作，因此 I/O 所作的事請會顯著增加。 --- ### **補充：系統平衡的重要性** 1. **理想情況：** - 系統內的 I/O Bound 和 CPU Bound Processes 數量應該平衡，這樣可以同時高效地利用 CPU 和 I/O 設備。 2. **極端情況的影響：** - 如果大多數是 **CPU Bound Processes**：CPU 高負載，但 I/O 設備閒置。 - 如果大多數是 **I/O Bound Processes**：I/O 設備高負載，但 CPU 閒置。 --- ## **12. 有關頁錯誤 (Page Fault) 與頁置換 (Page Replacement) 的說明，請選出正確的敘述？** a. ✅ 頁錯誤是指要使用的該頁不存在於主記憶體內 b. 🔲 發生頁錯誤就必須進行頁置換 c. ✅ 使用較大的頁可以減少頁錯誤 d. 🔲 增加頁框 (Page Frame) 數目就一定會減少頁錯誤發生 --- ### **解析** #### **a. 頁錯誤是指要使用的該頁不存在於主記憶體內** **正確 ✅** 頁錯誤的定義是：當程序試圖訪問一個頁時，發現該頁不在主記憶體中（RAM），此時會觸發頁錯誤。作業系統會根據頁錯誤處理程序，將所需頁從磁碟載入到主記憶體中。 --- #### **b. 發生頁錯誤就必須進行頁置換** **錯誤 🔲** 並非所有頁錯誤都需要頁置換。如果主記憶體中仍有空閒的頁框（Page Frame），系統只需要將缺失的頁載入空閒頁框即可，無需進行頁置換。只有當頁框已滿時，才需要使用頁置換算法替換掉現有的頁。 --- #### **c. 使用較大的頁可以減少頁錯誤** **正確 ✅** 使用較大的頁可能減少頁錯誤的發生，因為： - 每個頁框能容納更多數據，因此程序需要載入的頁數減少。 - 如果程序具有良好的空間區域性，較大的頁可以容納更多相關數據，從而減少頁錯誤的發生。但需要注意的是，較大的頁也會增加內部支離破碎（Internal Fragmentation），這是一個需要平衡的設計考量。 --- #### **d. 增加頁框 (Page Frame) 數目就一定會減少頁錯誤發生** **錯誤 🔲** 增加頁框數量通常可以減少頁錯誤，但並非總是如此。在某些情況下（例如使用 **FIFO 頁置換算法**），頁框數量的增加可能會導致頁錯誤數增加，這被稱為「**Belady's Anomaly（貝雷迪異象）**」。 --- **13. 有關 CPU 排程法的特性，請選出正確的敘述？** a. 🔲 先到先服務 (First Come First Served) 是一種可搶取 (Preemptive) 的排程法 b. ✅ 最短作業優先 (Shortest Job First) 排程法有最小的平均等待時間 c. ✅ 知更鳥式循環 (Round Robin) 是一種不會造成飢餓的排程法 d. 🔲 越公平的 CPU 排程法，平均等待時間就一定越小 --- ### **解析** #### **a. 先到先服務 (First Come First Served) 是一種可搶取 (Preemptive) 的排程法** **錯誤 🔲** - **先到先服務 (First Come First Served, FCFS)** 是一種**不可搶取 (Non-Preemptive)** 排程法。 - 一旦 CPU 分配給某個進程，該進程必須執行完畢後，CPU 才能被分配給下一個進程。 --- #### **b. 最短作業優先 (Shortest Job First) 排程法有最小的平均等待時間** **正確 ✅** - **最短作業優先 (Shortest Job First, SJF)** 排程法會優先執行執行時間最短的進程，從而**最小化平均等待時間**。 - 缺點：這種方法可能導致長作業的進程被長時間推遲（即「飢餓」問題）。 --- #### **c. 知更鳥式循環 (Round Robin) 是一種不會造成飢餓的排程法** **正確 ✅** - **知更鳥式循環 (Round Robin, RR)** 是一種可搶取 (Preemptive) 的排程法，所有進程按照時間片循環執行，確保每個進程都有機會執行，從而避免「飢餓」現象。 - 這種方法特別適合於分時系統。 --- #### **d. 越公平的 CPU 排程法，平均等待時間就一定越小** **錯誤 🔲** - 公平的排程不一定會最小化平均等待時間。例如： - **Round Robin (RR)** 非常公平，但平均等待時間可能比 **Shortest Job First (SJF)** 更長。 - 「公平」與「最小化等待時間」之間常常需要平衡。 --- ### **補充：各種 CPU 排程法的特性** | **排程法** | **特性** | **優點** | **缺點** | |--------------------------|-----------------------------------------------------------------------------------------|--------------------------------------------|-------------------------------------------| | **先到先服務 (FCFS)** | 不可搶取，按到達順序排程。 | 簡單、容易實現 | 可能導致「短作業等待長作業」的問題（即「車隊效應」）。 | | **最短作業優先 (SJF)** | 優先執行執行時間最短的作業，可分為可搶取與不可搶取兩種。 | 平均等待時間最小 | 容易導致長作業飢餓。 | | **知更鳥式循環 (RR)** | 每個進程分配固定時間片，時間片到則切換到下一個進程。 | 公平、適合分時系統 | 平均等待時間可能較長。 | | **優先級排程 (Priority)** | 根據優先級分配 CPU，可分為可搶取與不可搶取。 | 高優先級的進程能快速執行 | 低優先級的進程可能飢餓。 | --- ## **1.請根據哲學家用餐的問題，舉出至少二種可解決飢餓 (Starvation) 的方法？並說明理由？** 哲學家問題會造成飢餓是因為產生死結，而要消除死結則必須使產生死結的 4 大條件任一不符合即可。 **四大條件為：** 互斥、hold and wait、循環等待、不可搶取 1. 只要哲學家在執行中未拿到全部資源就釋放手上所有資源，意即要去拿筷子時沒有成功拿到兩隻筷子的話就必須釋放手上的筷子。此為消除 hold and wait。 2. 將哲學家編號，並以一定順序編號吃飯，例如哲學家餓了時可以搶別人的筷子，但在搶的時候會比對一下紀錄讓相餓之下餓久沒有吃到飯的哲學家不會被略過。此為消除不可搶取，並提供 Aging 的機制以防飢餓。 --- ### **Aging (老化機制) 的簡單介紹** **Aging (老化)** 是一種用於解決作業系統中 **飢餓 (Starvation)** 問題的機制。它的主要目的是確保所有進程或資源請求都能在合理時間內得到服務。 --- ### **核心概念** 1. **目的：** - 防止低優先級的進程長期得不到 CPU 或資源，解決因優先級排程而導致的飢餓問題。 2. **原理：** - 隨著時間的推移，系統會動態增加等待進程的優先級。 - 等待時間越長，優先級提升越高，最終確保該進程能夠被執行。 --- ### **如何運作？** #### **例子：** 假設系統使用優先級排程，進程優先級的範圍是 1（最高）到 10（最低）： 1. 有一個低優先級的進程 $ P1 $，其初始優先級為 9。 2. 每隔一段固定時間，系統檢查等待中的進程： - 如果 $ P1 $ 還沒有被執行，則將其優先級減少（如從 9 減到 8，再到 7）。 3. 當 $ P1 $ 的優先級達到比其他進程高時，系統會選擇執行 $ P1 $。 --- ### **Aging 的應用場景** 1. **作業系統排程：** - 避免低優先級進程因高優先級進程持續佔用 CPU 而陷入飢餓。 - 例如，在優先級排程和多級隊列排程中常用。 2. **資源分配：** - 用於銀行家演算法中，解決某些進程長期得不到資源的問題。 --- ### **優點與缺點** #### **優點：** - 簡單有效，解決飢餓問題。 - 不改變系統的排程原則，只是增加了一個動態優先級調整機制。 #### **缺點：** - 如果 Aging 設計不當，可能會導致**不公平性**： - 高優先級進程可能因不斷等待的低優先級進程被頻繁打斷。 - 優先級頻繁變動可能增加排程的計算開銷。 ## **2.請舉例說明使用號誌 (Semaphore) 及 WAIT(S)、SIGNAL(S) 是否會發生時間相依錯誤 (Time Dependent Error) 的問題？並分析其無法滿足什麼條件和理由？** 會發生時間相依錯誤。若將臨界區間的上一行指令分別為 signal(S) 與 wait(S) 的話，因為一進入 signal(S)，將 S+1 並不會叫醒任何正在等待的 process，也無法判斷是否有 process 正在使用關鍵區間而阻擋前進，因此無法滿足互斥，此為時間相依錯誤。 ![image](https://hackmd.io/_uploads/ry_2IKDUJe.png) ![螢幕快照 2025-01-05 12-09-01](https://hackmd.io/_uploads/rJ3MUKPLyg.png) ![image](https://hackmd.io/_uploads/H1XCIFwIyg.png) --- ## **3.假設關聯記憶體 (Associative Memory) 之每次存取時間為 20ns，主記憶體 (Main Memory) 之每次存取時間為 100ns。若採用混合式關聯記憶體及主記憶體的頁表格 (Page Table) 架構，假設在關聯記憶體內的命中比率 (Hit Ratio) 為 80%，且頁表格在主記憶體中採用二層分頁法 (Two-level Paging) 進行查找。請計算平均查找一頁要花多少時間？並說明計算過程：** --- **計算過程：** 1. **Cache (命中率 80%)：** $(20 + 100) \times 0.8 = 96 \, \text{ns}$ 2. **Main Memory (未命中率 20%)：** $(20 + 100(第一層) + 100(第二層) + 100 ) \times 0.2 = 64 \, \text{ns}$ 3. **平均存取時間：** $96 + 64 = 160 \, \text{ns}$ --- ### **基本概念補充** #### **1. 關聯記憶體 (Associative Memory)** - **用途：** 關聯記憶體 (又稱 TLB，Translation Lookaside Buffer) 用於加速頁表查找。 - **特性：** - 查詢速度非常快。 - 當找到目標頁表項時稱為「命中 (Hit)」。 - 未命中 (Miss) 時需要進一步查詢主記憶體中的頁表。 #### **2. 二層分頁 (Two-Level Paging)** - **頁表分為兩層：** - 第一層存放指向第二層頁表的指標。 - 第二層存放實際的頁框 (Page Frame) 資訊。 - **額外的存取成本：** 每次查找一頁時，需要兩次主記憶體存取：一次讀取第一層頁表，另一次讀取第二層頁表。 #### **3. 平均存取時間公式 (Memory Access Time Formula)** **公式：** $\text{平均存取時間 (AMAT)} = \text{命中時間 (Hit Time)} \times \text{命中率 (Hit Ratio)} + \text{未命中時間 (Miss Time)} \times (1 - \text{命中率})$ - **命中時間：** 關聯記憶體存取時間。 - **未命中時間：** 關聯記憶體存取失敗後，還需要進行額外的主記憶體查找。 ## **4. 假設系統目前處於安全狀態，且已知資源配置狀態 (Resource Allocation State) 如圖所示。若此時 P1 提出資源需求為 $ 1A, 2B, 2C $，請利用 Banker's 演算法推論是否可以接受？如果可以接受，請推論出一組確保系統是在安全狀態的執行次序；否則，請說明不能接受的原因？** ![image](https://hackmd.io/_uploads/ByUkvCLLye.png) 可接受，因為 P1 所請求的資源小於 Need，也就是它所需要的資源，所以是合理的請求。而且請求的資源也小於系統目前的可用資源。 **P1 → P3 → P2 → P0 → P4** **過程：** - **P1 執行：** 為安全狀態，執行完後系統目前可用資源為 $ 5A, 3B, 2C $。 - **P3 執行：** 為安全狀態，執行完後系統目前可用資源為 $ 7A, 4B, 3C $。 - **P2 執行：** 為安全狀態，執行完後系統目前可用資源為 $ 10A, 4B, 5C $。 - **P0 執行：** 為安全狀態，執行完後系統目前可用資源為 $ 10A, 5B, 5C $。 - **P4 執行：** 為安全狀態，執行完後系統目前可用資源為 $ 10A, 5B, 7C $。 --- ### **安全狀態 (Safe State)** - **定義：** 當系統可以找到一個進程執行順序，使所有進程在有限時間內完成所需資源的分配並執行完畢，則系統處於安全狀態。 - **特徵：** - 存在至少一個**安全序列 (Safe Sequence)**，能確保系統不進入死結 (Deadlock)。 - **Banker's 演算法**可以用來判斷是否處於安全狀態。 --- ### **不安全狀態 (Unsafe State)** - **定義：** 當系統無法保證有一個進程執行順序使所有進程完成所需資源分配，系統處於不安全狀態。 - **特徵：** - 不一定會發生死結，但有可能導致死結。 - 系統可能因資源分配不當而陷入無限等待或死結。 --- ### **總結：** - **安全狀態 ≠ 死結發生，但一定能避免死結。** - **不安全狀態 ≠ 一定發生死結，但系統風險增加。** --- ## **5.** **阿宅工程師嘗試寫出 Bakery 演算法如下列虛擬碼 (pseudocode)，但似乎出了一點問題，請分析此程式是否能滿足進入臨界區間 (Critical Section) 的條件？並具體說明其原因為何？** --- **虛擬碼 (Pseudocode)：** ```plaintext choosing[i] = true; number[i] = max(number[0], number[1], ..., number[n-1]) + 1; for j = 0 to n-1 { while choosing[j] do no-op; while (number[j] ≠ 0 and compare(number[j], number[i])) do no-op; } CRITICAL SECTION number[i] = 0; ``` --- **解答：** 無法滿足進入臨界區間的條件。因為第 3 行應該要將 choosing[i] 設為 false 以記錄該 process 已拿到號碼牌，意即有屬於自己的 number，因為若沒有該紀錄的話在第 5 行的迴圈 (該迴圈會等待所有要進入的 process 拿 number) 會因為每一個都是 true (認為都還沒有拿到屬於自己的 number) 而卡在迴圈中，這就沒有 process 可以進入臨界區間，因而違反了行進及有限等待。 --- ### Bakery演算法 **Bakery演算法**模擬了銀行或商店中的取號系統，用於多處理程序進入臨界區間時的同步控制，能滿足 **互斥**、**行進** 和 **有限等待** 的條件。 --- #### **基本概念** 1. **取號牌機制**: - 每個處理程序必須先取一個號碼，才能嘗試進入臨界區間。 - 若多個處理程序同時取號，則按以下順序進入臨界區： 1. **號碼小者優先**。 2. 若號碼相同，則根據處理程序的 ID（PID）排序。 2. **條件保證**: - 互斥：確保同一時間只有一個處理程序進入臨界區間。 - 行進：處理程序會按號碼順序輪到。 - 有限等待：每個處理程序的等待次數是有限的。 --- #### **程式結構** ```cpp choosing[i] = true; number[i] = max(number[0], number[1], ..., number[n-1]) + 1; // 取號 choosing[i] = false; //表示已經拿到號碼牌 for (int j = 0; j < n; j++) { while (choosing[j]); // 等待其他程序完成取號 while (number[j] != 0 && compare(number[j], number[i])); // 比較號碼與程序ID } // 進入臨界區 Critical Section number[i] = 0; // 離開臨界區 ``` --- #### **細節說明** 1. **取號階段**: - 當程序 `i` 想進入臨界區，設置 `choosing[i] = true` 表示取號中。 - 它會取得一個大於當前所有號碼的值 `number[i] = max(...) + 1`。 2. **等待階段**: - 每個程序都需確認： - 是否有其他程序還在取號 (`choosing[j]`)。 - 比較號碼和程序 ID (`compare(number[j], number[i])`)。 3. **進入臨界區**: - 若程序 `i` 的號碼最小或符合條件，則進入臨界區。 - 完成臨界區工作後，將 `number[i]` 設為 0，釋放號碼。 4. **比較邏輯 (`compare`)**: - 若 `number[j] < number[i]`，返回 `true`（程序 `j` 優先）。 - 若 `number[j] == number[i]` 且 `j < i`，返回 `true`（程序 ID 小者優先）。 - 否則，返回 `false`。 ### **進入臨界區間的三個核心條件：** #### **1. 互斥 (Mutual Exclusion)** - **定義：** 當一個進程進入臨界區時，其他進程必須被阻止進入該臨界區。這確保了同一時間內，只有一個進程可以訪問共享資源。 - **原因：** 防止多個進程同時修改共享數據，導致數據不一致或系統錯誤。 --- #### **2. 行進 (Progress)** - **定義：** 如果沒有進程在臨界區內，則只有那些準備進入臨界區的進程可以參與決定誰可以進入臨界區，並且這個決定不能無限延遲。 - **解釋：** - 不應該由無關的進程（例如那些在非臨界區或處於空閒狀態的進程）干擾進程進入臨界區的決策。 - 確保當資源可用時，系統不會陷入僵持狀態（例如，所有進程都在等待但沒有人進入）。 --- #### **3. 有限等待 (Bounded Waiting)** - **定義：** 確保每個進程在有限次嘗試後能夠進入臨界區，而不會無限期等待。 - **解釋：** - 防止進程因為某些其他進程反覆進入臨界區而被永遠阻止進入（飢餓問題）。 - 提升系統的公平性。