跳轉至

批處理作業調度算法

根據作業系統的性質，作業排程演算法可以分為以下兩種：

單道批次作業排程演算法

  • 定義: 在單道批次系統中，一次只裝入並執行一個作業，作業在執行期間獨佔所有系統資源。待該作業執行完畢後，系統才會調度下一個作業。
  • 特點:
  • 作業在執行期間獨佔所有電腦資源。
  • 系統資源使用率較低，尤其在作業進行 I/O 作業時，CPU 會出現空閒等待。
  • 通常用於早期的電腦系統或資源有限的環境。

常見演算法:

先來先服務演算法 (FCFS)

  • 定義：每次調度依照作業進入「輸入井」後備作業佇列的先後次序來挑選作業，優先將最先進入佇列的作業調入主存，分配資源，建立進程，放入進程就緒隊列準備運行。
  • 特點：FCFS是一種非剝奪式調度演算法，容易實現，體現了公平，但效率不高，只考慮等候時間而不考慮作業服務時間長短。
  • 優點：簡單，易於實現，保證公平。
  • 缺點：對短作業不利，有利於長作業和CPU繁忙型作業，不利於I/O繁忙型作業。因此，FCFS作為主調度演算法不常用。

短作業優先演算法 (SJF)

  • 定義：調度時以作業運行時間長短作為標準，從後備作業佇列中選取運行時間最短的作業裝入主存運行。
  • 特點：優先選擇短作業，有助於提升系統整體回應效率。

回應比最高者優先演算法 (HRRF)

  • 定義：既考慮作業等待時間，又考慮作業運行時間，計算所有作業的回應比，選擇回應比最高的作業優先裝入主記憶體運行。
  • 回應比公式：回應比 = (作業等待時間 + 作業運行時間) / 作業運行時間
  • 特點：綜合考慮等待時間和運行時間，確保公平性和高效性。

優先數調度演算法

  • 定義：為每個作業決定一個優先數，根據優先數的不同將作業排成多個佇列，優先選取優先數最高且資源能滿足的作業裝入主記憶體運行。
  • 優先數確定原則：
  • 對於時間要求緊迫的作業賦予較高優先數。
  • 對於I/O量大的作業給予較高優先權數，CPU量大的作業給予較低優先權。

分類調度演算法 (均衡調度演算法)

  • 定義：根據系統運作狀況和作業對資源的需求，先將作業分類，然後調度程序輪流從不同的作業類別中挑選作業，盡可能使不同資源的作業同時執行，確保資源均衡利用。

多道批次作業排程演算法

  • 定義: 在多道批次系統中，系統支援多道程式設計，允許多個作業同時裝入內存，這樣可以在一個作業等待I/O 操作時，CPU 可以調度其他作業執行，從而提高系統的資源利用率。
  • 特點:
  • 透過多道程式設計，系統可以並發處理多個作業，提升資源利用率和系統吞吐量。
  • 可以同時執行多個作業，每個作業分別使用 CPU 和 I/O 資源。

  • 適用於現代多工作業系統，能夠顯著提升系統效能。

  • 常見演算法:

  • 高階排程（作業排程）:
  • 負責從後備作業佇列中選擇合適的作業裝入內存，以提高系統吞吐量。
  • 常用策略包括先來先服務、優先調度、依作業大小調度等。
  • 低階調度（進程調度）:
  • 負責在記憶體中的就緒程序佇列中選擇下一個執行的程序。
  • 常見演算法包括時間片輪轉、最短剩餘時間優先、優先調度等。
  • 中階調度（記憶體調度）:
  • 使用交換技術（Swapping），在記憶體空間不足時將部分作業移到外存，以釋放記憶體空間。
  • 負責動態調整記憶體中的作業數量，平衡系統負載。

兩者的對比

特性 單道批次作業排程演算法 多道批次作業排程演算法
並發性 不支持，單次只執行一個作業 支持，多個作業可並發性執行
資源利用率 低，CPU 經常空閒等待 高，充分利用 CPU 和 I/O
系統複雜度 簡單，調度策略較少 複雜，需要高級、中級和低級調度
適用場景 資源有限、任務量少的場景 現代多工、多使用者係統
典型演算法 先來先服務、短作業優先、回應比最高 時間片輪轉、優先權排程、作業排程

總結

  • 單道批次作業排程演算法 適合資源有限的環境，較為簡單，但資源利用率低，不適用於現代多工系統。
  • 多道批次作業排程演算法 能充分利用系統資源，提高 CPU 與 I/O 裝置的使用率，是現代作業系統的標準設計模式。