學習目標

  • 理解多元程式處理的概念
  • 掌握多元程式處理與其他相關概念的區別
  • 理解多元程式處理的優點和實現方式
  • 了解行程排程的基本概念

1. 什麼是多元程式處理？

1.1 定義

多元程式處理 (Multiprogramming) 是指作業系統同時將多個程式載入記憶體中，當一個程式因為等待 I/O 操作而暫停時，CPU 可以切換到另一個程式繼續執行，從而提高 CPU 的利用率。

1.2 核心思想

目標: 讓 CPU 永遠保持忙碌，避免 CPU 閒置。

方法: 當一個程式在等待 I/O（如讀取磁碟、等待使用者輸入）時，CPU 不應該閒置，而是去執行其他已經準備好的程式。

1.3 生活化例子

想像一個圖書館管理員（CPU）： - 單程式系統: 管理員一次只服務一個讀者，即使讀者在找書（等待 I/O），管理員也只能等待 - 多元程式系統: 管理員同時服務多個讀者，當一個讀者在找書時，管理員去服務其他讀者

2. 為什麼需要多元程式處理？

2.1 CPU 與 I/O 的速度差異

  • CPU 速度: 非常快（納秒級）
  • I/O 速度: 相對很慢（毫秒級，甚至秒級）

問題: 如果 CPU 在等待 I/O 完成時閒置，會造成巨大的資源浪費。

2.2 範例

假設執行一個程式需要： - CPU 計算時間: 1 秒 - I/O 等待時間: 9 秒 - 總時間: 10 秒

單程式系統: - CPU 利用率 = 1/10 = 10% - 大部分時間 CPU 都在等待 I/O

多元程式系統（假設有 10 個程式）: - 當程式 A 在等待 I/O 時，CPU 執行程式 B - 當程式 B 在等待 I/O 時，CPU 執行程式 C - ... - CPU 利用率接近 100%

3. 相關概念區別

3.1 多元程式處理 (Multiprogramming)

定義: 多個程式同時在記憶體中，CPU 在它們之間切換執行。

特點: - 多個程式在記憶體中 - 只有一個 CPU - CPU 在程式間切換 - 不強調回應時間，注重吞吐量 (Throughput)

時間軸範例:

時間: 0    1    2    3    4    5
程式A: [CPU][I/O等待]
程式B:      [CPU][I/O等待]
程式C:           [CPU][I/O等待]

3.2 多工處理 (Multitasking)

定義: 多個任務（可能是同一程式的不同部分）同時執行。

特點: - 可以是多個程式，也可以是單一程式的多個執行緒 - 強調快速切換，給使用者「同時執行」的感覺 - 注重回應時間

與多元程式處理的關係: - 多工處理是多元程式處理的延伸 - 多工處理通常指分時系統 (Time-sharing)，強調快速回應

3.3 多處理 (Multiprocessing)

定義: 系統有多個 CPU 或處理器核心，可以真正同時執行多個程式。

特點: - 多個 CPU/核心 - 可以真正並行執行（不是切換） - 需要硬體支援

與多元程式處理的區別: - 多元程式處理: 一個 CPU，多個程式輪流使用 - 多處理: 多個 CPU，多個程式真正同時執行

3.4 比較表

特性 多元程式處理 多工處理 多處理
CPU 數量 1 個 1 個 多個
程式數量 多個在記憶體中 多個任務 多個程式
執行方式 切換執行 快速切換 真正並行
重點 提高 CPU 利用率 快速回應 真正並行
時間單位 較長（秒級） 很短（毫秒級） 同時

4. 多元程式處理的實現

4.1 基本要求

  1. 記憶體管理: 能夠同時將多個程式載入記憶體
  2. CPU 排程: 決定下一個要執行的程式
  3. I/O 管理: 管理多個程式的 I/O 請求
  4. 保護機制: 防止程式互相干擾

4.2 CPU 排程 (CPU Scheduling)

當 CPU 需要切換到另一個程式時，需要決定： - 何時切換: 什麼時候進行上下文切換 (Context Switch) - 切換到誰: 選擇哪個程式來執行

排程時機

  1. 自願放棄 CPU: - 程式執行 I/O 操作 - 程式主動等待某個事件

  2. 非自願放棄 CPU: - 時間片用盡（分時系統） - 更高優先權的程式到達 - 程式執行完畢

排程演算法

先來先服務 (FCFS - First Come First Served): - 簡單，但可能導致短程式等待長程式

最短工作優先 (SJF - Shortest Job First): - 理論上最優，但需要知道執行時間

輪詢 (Round Robin): - 每個程式分配固定時間片，公平但可能效率較低

優先權排程 (Priority Scheduling): - 根據優先權決定執行順序

4.3 上下文切換 (Context Switch)

當 CPU 從一個程式切換到另一個程式時，需要：

  1. 保存當前程式狀態: - 程式計數器 (PC) - 暫存器內容 - 程式狀態字 (PSW)

  2. 載入新程式狀態: - 載入新程式的 PC - 載入新程式的暫存器 - 載入新程式的 PSW

  3. 切換記憶體空間: - 切換到新程式的記憶體空間

開銷: 上下文切換需要時間，這是多元程式處理的成本。

5. 多元程式處理的優點

5.1 提高 CPU 利用率

  • CPU 不會因為等待 I/O 而閒置
  • 可以達到接近 100% 的 CPU 利用率

5.2 提高系統吞吐量

  • 單位時間內可以完成更多工作
  • 系統整體效率提升

5.3 資源共享

  • 多個程式可以共享系統資源
  • 提高資源利用率

6. 多元程式處理的缺點

6.1 記憶體需求增加

  • 需要同時載入多個程式
  • 需要更多的記憶體空間

6.2 複雜度增加

  • 需要複雜的記憶體管理
  • 需要 CPU 排程機制
  • 需要保護機制防止程式互相干擾

6.3 上下文切換開銷

  • 切換程式需要時間
  • 如果切換太頻繁，開銷可能很大

6.4 可能的問題

  • 死結 (Deadlock): 多個程式互相等待資源
  • 競爭條件 (Race Condition): 多個程式競爭共享資源
  • 記憶體保護: 需要防止程式存取其他程式的記憶體

7. 實際例子

7.1 早期批次系統

1960 年代: - 多個工作批次載入記憶體 - 當一個工作在等待 I/O 時，CPU 執行另一個工作 - 這是多元程式處理的早期應用

7.2 現代作業系統

Windows, Linux, macOS: - 同時執行多個應用程式 - 當一個程式在等待網路回應時，CPU 執行其他程式 - 這是多元程式處理的現代實現

8. 練習題

練習題 1

請說明多元程式處理的核心思想。

參考答案： 多元程式處理的核心思想是讓 CPU 永遠保持忙碌。當一個程式因為等待 I/O 操作而暫停時，CPU 不應該閒置，而是切換到另一個已經準備好的程式繼續執行，從而提高 CPU 的利用率。

練習題 2

請比較多元程式處理、多工處理和多處理的差異。

參考答案： - 多元程式處理: 一個 CPU，多個程式在記憶體中輪流執行，注重提高 CPU 利用率 - 多工處理: 一個 CPU，快速切換多個任務，注重快速回應 - 多處理: 多個 CPU，多個程式真正並行執行

練習題 3

為什麼需要 CPU 排程？

參考答案： 當 CPU 需要切換到另一個程式時，需要決定何時切換以及切換到哪個程式。CPU 排程就是這個決策機制，它決定了程式的執行順序，影響系統的效能和公平性。

9. 考試重點提醒

  1. 核心概念: 理解多元程式處理是為了提高 CPU 利用率
  2. 與其他概念的區別: 要能清楚區分多元程式處理、多工處理、多處理
  3. 實現機制: 理解需要記憶體管理、CPU 排程、I/O 管理等機制
  4. 優缺點: 要能說明多元程式處理的優點和缺點
  5. 上下文切換: 理解切換程式的過程和開銷