資源管理（HL 擴充課程）溫習筆記

哈囉各位電腦科學學生！歡迎來到第 6 單元：資源管理。這一章對於了解作業系統（OS）的真正運作方式至關重要——它是電腦背後的「大腦」，負責決定誰能獲得資源、什麼時候獲得資源。

你可以將作業系統想像成一間繁忙工廠（電腦）的經理。工廠裡有有限的機器（資源）和許多要求使用機器的工人（行程/處理序）。如果經理不能高效且公平地分配資源，工廠就會陷入混亂！

我們將剖析作業系統如何管理 CPU（排程）、記憶體（RAM），以及如何預防嚴重的問題（例如死鎖）。如果一開始覺得有些複雜，請別擔心；我們會透過簡單易懂的例子來解釋這些複雜的系統。

1. 作業系統（OS）在資源管理中的角色

資源（Resource）是指行程在執行時所需的任何硬體或軟體組件。由於系統通常會同時執行多個行程，因此作業系統必須管理這些資源，以確保系統的穩定性、效率和公平性。

資源類型
  • 處理器（CPU）：中央運算單元。
  • 記憶體（RAM）：程式和數據在執行時儲存的地方。
  • 輸入/輸出裝置（I/O Devices）：印表機、硬碟、網絡卡、螢幕。
  • 檔案/數據：共享資訊或資料庫存取。
資源管理的目標

作業系統試圖同時實現三個主要目標：

  1. 效率（Efficiency）：確保資源被充分利用（例如保持 CPU 的使用率）。
  2. 公平性（Fairness）：確保每個行程都能獲得合理的執行時間和資源份額。
  3. 安全性/保護（Security/Protection）：防止一個行程干擾另一個行程（例如讀取或寫入其他行程的記憶體空間）。
快速複習：作業系統是中央交通指揮官，目標是在不發生崩潰或資源飢餓（starvation）的情況下，達到高效率的使用率。

2. 處理器管理：排程演算法

CPU 排程（CPU Scheduling）是一項決定「就緒佇列」中哪個行程將獲得 CPU，以及獲得多久時間的機制。其主要目標是優化系統效能指標，例如輸送量（Throughput，單位時間內完成的工作量）和回應時間（Response Time，系統對輸入反應的速度）。

排程演算法分類

我們將排程分為兩類：

  • 非搶佔式（Non-preemptive）：一旦行程開始執行，它就會一直執行直到完成，或主動放棄 CPU（就像一場不能被中斷的演講）。
  • 搶佔式（Preemptive）：作業系統可以中斷正在執行的行程，並將 CPU 指派給更高優先級的任務（就像主管中斷員工的工作）。
a) 先到先服務（FCFS - First Come, First Served）

這是最簡單的非搶佔式演算法。

  • 運作方式：行程嚴格按照到達順序進行服務，是一個基本的先進先出（FIFO）佇列。
  • 類比：超級市場收銀台的簡單排隊。
  • 缺點：會出現護航效應（Convoy Effect）。如果一個非常耗時的工作先到達，所有隨後的小工作都必須等待很長時間，導致整體效率低下且平均等待時間過長。
b) 最短工作優先（SJN/SJF - Shortest Job Next/First）

這是將平均等待時間降至最低的最佳演算法。

  • 運作方式：排程器選擇估計執行時間（Burst time）最短的工作。它可以是非搶佔式，也可以是搶佔式（稱為「最短剩餘時間優先」，即 SRTF）。
  • 類比：在開始 3 小時的大專案前，先完成所有 5 分鐘的小任務。
  • 缺點：它需要「預測未來」（預先知道準確的執行時間），這在現實系統中是不可能的。它還存在飢餓（Starvation）風險（如果不斷有小工作進來，一個非常大的工作可能永遠無法執行）。
c) 優先級排程（Priority Scheduling）

根據分配的重要性等級來執行工作。

  • 運作方式：每個行程被分配一個優先級數字（數字越小通常代表優先級越高）。CPU 分配給準備就緒且優先級最高的行程。
  • 危險：飢餓（Starvation）。如果高優先級工作不斷進入，低優先級行程可能會無限期等待。
  • 解決方案：老化（Aging）。這項技術會逐漸增加在佇列中等待時間過長的行程之優先級。就像給排隊排了很久的人一張「快速通關券」。
d) 輪替排程（RR - Round Robin）

這是一種專為分時系統設計的搶佔式演算法，旨在提供快速的回應時間。

  • 運作方式：每個行程獲得一小段 CPU 時間，稱為時間量子（Time quantum）或時間片（例如 10 毫秒）。如果行程未在該時間內完成，它會被搶佔並移到就緒佇列的末尾。
  • 類比：紅綠燈在不同車道間快速切換。每個人都有機會通行，儘管每次時間都很短。
  • 關鍵考慮因素：時間量子的大小至關重要。如果太大，RR 就會像 FCFS；如果太小，則會因為頻繁切換行程（Context switching）而浪費過多時間。
排程重點摘要：FCFS 簡單但效率低。SJF 最優但難以實踐。RR 利用時間量子提供了公平性和快速的回應時間。

3. 記憶體管理技術

作業系統負責管理主記憶體（RAM）。它必須追蹤哪些記憶體區塊正在使用中，為行程分配空間，並保護各個行程的記憶體不受干擾。

a) 分頁（Paging）

分頁是一種避免外部碎片（External fragmentation，已分配記憶體區塊之間的浪費空間）的記憶體管理方案。

  • 運作方式：實體記憶體（RAM）被劃分為固定大小的區塊，稱為頁框（Frames）。邏輯記憶體（行程位址空間）則劃分為相同大小的區塊，稱為頁（Pages）。
  • 當行程執行時，其頁面會被映射到 RAM 中可用的頁框。關鍵在於，這些頁框不需要是連續的（不必挨在一起）。
  • 位址轉換：作業系統使用頁表（Page Table）將行程的邏輯位址（頁號 + 位移量）轉換為實體位址（頁框號 + 位移量）。
b) 分段（Segmentation）

分段是一種根據程式的邏輯結構來映射記憶體的管理方案。

  • 運作方式：程式被劃分為大小不一的邏輯單元（段），對應如主程式碼、數據區、堆疊或副程式等組件。
  • 這對程式設計師來說更容易管理，但可能會導致外部碎片，因為各段大小不同，當它們執行結束後會在記憶體中產生不均勻的空洞。
c) 虛擬記憶體（Virtual Memory）

虛擬記憶體是一項革命性技術，即使程式只有一部分載入到實體記憶體中，它仍然可以執行。它創造了一種「電腦擁有比物理容量更多 RAM」的假象。

  • 運作方式：它利用次級儲存裝置（磁碟空間）來保存當前未使用的程式部分。磁碟上的這個儲存區域通常稱為置換空間（Swap space）。
  • 置換（Swapping）：當行程請求的頁面/分段不在記憶體中時，作業系統會觸發頁面錯誤（Page fault），將 RAM 中未使用的頁面移回磁碟，並將請求的頁面載入到 RAM。這個過程稱為置換。
  • 類比：你的桌面（RAM）只能放這麼多書（頁面）。虛擬記憶體就像旁邊有一個巨大的檔案櫃（磁碟），你可以隨時取出或放回書本。這讓你的桌面看起來有無限大的空間，但置換書本的速度比較慢！
  • 小知識：如果系統花費過多時間在移動頁面而不是執行指令，這種現象稱為顛簸（Thrashing），這會導致電腦速度極度緩慢。
記憶體重點摘要：分頁和分段是分配記憶體的方法。虛擬記憶體透過 RAM 和磁碟空間之間的置換，增加了實體記憶體的可用容量。

4. 並行與死鎖（Concurrency and Deadlock）

當多個行程同時執行（並行）時，它們通常需要共享資源。這種共享存取會產生作業系統必須處理的潛在問題。

a) 競爭條件與臨界區（Race Conditions and Critical Sections）

當行程執行的結果取決於兩個或多個獨立行程對共享資源存取的順序或時機時，就會發生競爭條件（Race condition）。

  • 範例：行程 A 和 B 同時嘗試增加一個共享變數 $X$。如果順序是 A 讀取、B 讀取、A 加 1、B 加 1，最終結果將會錯誤（只增加了 1 次而不是 2 次）。
  • 為了防止競爭條件，必須將存取共享資源的程式碼區段視為臨界區（Critical section）。

互斥（Mutual exclusion）是解決競爭條件的方法。它確保如果一個行程正在其臨界區執行，其他任何使用相同共享資源的行程都不能同時在它們的臨界區內執行。

b) 死鎖（Deadlock）

死鎖（Deadlock）是一種永久性的等待狀態，其中兩個或多個競爭行程都在等待被其他等待行程所持有的資源。沒有一個行程可以繼續執行。

  • 類比：經典的「交通大塞車」，車輛困在環形路口，每輛車都在等待前方的車移動。
死鎖發生的四個必要條件

只有當這四個條件同時成立時，才會發生死鎖。打破其中任何一個條件就能防止死鎖。

記憶口訣（M-H-N-C）：

  1. M: 互斥（Mutual Exclusion）：資源必須是非共享的（一次只能有一個行程使用）。（例如：印表機，而非唯讀數據）。
  2. H: 佔有並等待（Hold and Wait）：一個行程必須至少佔有一個資源，同時等待獲取其他被其他行程持有的資源。
  3. N: 不可搶佔（No Preemption）：資源不能被強行從佔有它的行程中剝奪；它們必須由行程主動釋放。
  4. C: 循環等待（Circular Wait）：必須存在一組行程 \(\{P_0, P_1, ..., P_n\}\)，使得 \(P_0\) 等待 \(P_1\) 持有的資源，\(P_1\) 等待 \(P_2\) 持有的資源，依此類推，而 \(P_n\) 等待 \(P_0\) 持有的資源。
死鎖處理策略

作業系統使用不同的方法來管理死鎖：

  1. 死鎖預防（Prevention）：從結構上確保四個必要條件中至少有一個永遠無法成立。（範例：要求行程一次過請求所有需要的資源，從而打破「佔有並等待」條件。）
  2. 死鎖避免（Avoidance）：作業系統動態檢查資源分配狀態，以確保系統保持在安全狀態（Safe state）（即系統能按某種順序為每個行程分配資源而不會導致死鎖）。（最著名的演算法是銀行家演算法 - Banker’s Algorithm。）
  3. 死鎖偵測與復原（Detection and Recovery）：允許死鎖發生，偵測到死鎖（使用資源分配圖），然後進行復原。復原通常涉及搶佔（Preemption）（強行收回資源）或終止行程（Process termination）（殺掉一個或多個行程來打破循環）。
並行重點摘要：競爭條件透過互斥來解決。死鎖需要四個特定條件（M-H-N-C）同時滿足，可透過預防、避免或偵測/復原來處理。

你已經完成資源管理的學習了！理解這些概念對於真正體會現代作業系統的複雜性和強健性至關重要。繼續練習那些排程演算法，並背好死鎖的四個條件吧！