多級佇列排程 (MLQ)

---

---

在大多數系統中，程序組合多種多樣，沒有單一的排程演算法能夠提供最佳解決方案。通常，可以將程序分為不同的型別，以便為每種型別分配優先順序值，併為每種型別定義適當的排程策略。

解決方案是引入多個佇列而不是單個就緒佇列，並在其上執行排程。處理多個佇列的排程策略稱為多級佇列排程。上述的修改版本稱為多級反饋佇列排程。

多級佇列排程 (MLQ)

在多級佇列排程中，程序被分為不同的類別，每個類別都有其獨特的特性。在大多數系統中，有三種類型的程序：系統程序、前臺程序和後臺程序。

系統程序具有最高優先順序，需要立即處理。前臺程序是互動式的使用者程序；而後臺程序是批處理程序。由於不同的類別需要不同的響應時間和優先順序，因此它們需要不同的排程演算法。這些程序被分配到不同的佇列，如下圖所示：

根據系統的性質，可能還有許多其他類別的佇列，其優先順序介於這些廣泛的程序類別之間，例如即時程序佇列、互動式編輯佇列等。

多級佇列

從上圖可以看出，就緒佇列被劃分成幾個獨立的佇列，每個佇列都有其自身的特性和排程技術。當程序進入系統時，它將根據其優先順序、記憶體大小或響應時間永久分配到其中一個佇列。這個被劃分的就緒佇列稱為多級佇列。

多級佇列中的每個佇列都有不同的排程演算法。通常，系統佇列使用搶佔式優先順序排程；前臺佇列使用輪轉排程；後臺佇列使用先來先服務排程。

多級佇列 (MLQ) 排程的執行原理

執行原理如下：

假設有n個佇列，編號從1到n，優先順序從1到n。每個程序永久分配到這些佇列中的一個。一個佇列對優先順序較低的佇列具有絕對優先權。每個佇列都有自己的排程策略。首先，檢查優先順序為1的佇列1。如果其中有程序，則根據佇列1的排程策略執行它們。

如果佇列1中沒有程序，則檢查佇列2。如果佇列2有程序，則根據其排程演算法進行排程。以此類推，直到佇列n。因此，佇列x中的程序只有在佇列1到佇列(x-1)為空時才能訪問CPU。如果佇列x中的程序P5正在執行，並且一個新的程序P16到達一個具有更高優先順序的佇列，則P16會立即搶佔P5並開始執行。

藉助以下示例可以更好地理解其工作原理：

多級佇列 (MLQ) 排程的示例

讓我們考慮一個具有3個佇列的系統，優先順序為1到3，程序為P1到P5，如下表所示：

讓我們執行MLQ排程並繪製程序的甘特圖。

時間 = 0ms

事件：Q3中的P5到達

系統中的程序：Q3中的P5。

由於P5是唯一的程序，因此它立即被排程。

時間 = 2ms

事件：Q3中的P4到達

系統中的程序：Q3中的P4和P5。

由於P4和P5都在Q3中，並且Q3遵循先來先服務排程，因此P5繼續執行。

到2ms的甘特圖：

時間 = 4ms

事件：程序P2和P3到達。

系統中的程序：Q2中的P2和P3；Q3中的P4和P5。

由於P2和P3都在Q2中，而正在執行的程序P5在Q3中，P5被搶佔。在P2和P3中，P3被分配給CPU，因為Q2遵循最短剩餘時間優先排程。

到4ms的甘特圖：

時間 = 7ms

事件：程序P1到達。

系統中的程序：Q1中的P1；Q2中的P2、P3；Q3中的P4、P5。

由於P1在Q1中，而正在執行的程序P3在Q2中，P3被搶佔，P1開始執行。

到7ms的甘特圖：

時間 = 9ms

事件：程序P1完成執行。

系統中的程序：Q2中的P2、P3；Q3中的P4、P5。

由於P2和P3在Q2中，其優先順序高於P4和P5，因此它們競爭CPU時間。P3被分配給CPU，因為Q2使用SRTN排程，P2和P3的剩餘時間分別為6和1。

到9ms的甘特圖：

時間 = 10ms

事件：程序P3完成執行。

系統中的程序：Q2中的P2；Q3中的P4、P5。

由於P2在Q2中，其優先順序高於P4和P5，因此P2被分配給CPU。

到10ms的甘特圖：

時間 = 16ms

事件：程序P2完成執行。

系統中的程序：Q3中的P4、P5。

由於P5先到達，並且Q3遵循FCFS排程，因此P5被分配給CPU。

到16ms的甘特圖：

時間 = 24ms

事件：程序P5完成執行。

系統中的程序：Q3中的P4。

由於P4是系統中唯一的程序，因此它被分配給CPU。

到24ms的甘特圖：

時間 = 27ms

事件：程序P4完成執行。

系統中的程序：無

到27ms的最終甘特圖：

多級佇列排程的特點

• 多級佇列 - MLQ排程的核心是多個佇列，每個佇列都有自己的優先順序和響應時間。
• 佇列間的搶佔 - 在MLQ中，當高優先順序佇列中的程序進入系統時，它可以搶佔屬於低優先順序佇列的正在執行的程序。
• 不同佇列的不同調度策略 - 不同的佇列與不同的排程策略相關聯，這取決於其中程序的特性。
• 定製化排程 - 關於要包含的佇列數量及其相對優先順序的分配沒有硬性規定。這為根據系統需求進行定製化排程鋪平了道路。
• 新策略的開發 - MLQ基本上是一個概念，可以從中開發新的排程策略。這允許對排程進行研究。隨著程序管理不斷變化以及新作業系統的開發，排程策略需要更新。此外，沒有單一的排程演算法能夠滿足所有程序的需求。MLQ為在新系統中組合不同演算法提供了基礎。

多級佇列排程的優點

• MLQ的主要優點是它允許設定程序間的優先順序，這是實際應用中必不可少的。
• MLQ能夠有效地分配系統資源到不同的程序之間。
• MLQ大大縮短了高優先順序程序的響應時間。這使得整個系統更具響應性。
• MLQ根據系統需求具有高度的可定製性。
• MLQ提高了系統性能並增加了吞吐量。
• 在程序組合多樣化的系統中，它具有較低的排程開銷。

多級佇列排程的侷限性

• 如果許多高優先順序佇列都擁有穩定的程序流，則低優先順序佇列中的程序可能會面臨無限期飢餓。這是MLQ的主要缺點。
• MLQ的實現本身就很複雜。它需要正確的設計和開發，否則整個排程機制可能會崩潰。
• 為程序分配固定的優先順序使得MLQ成為一種不靈活的策略。
• 排程過於依賴於固定的優先順序，這些優先順序是在程序進入系統時立即分配的。程序優先順序的錯誤分配會嚴重影響效能。

多級反饋佇列排程

多級反饋佇列排程是對多級佇列排程的改進，它成功地克服了飢餓問題。它根據程序的執行行為動態地為程序分配優先順序。最初，所有程序都被分配到最高優先順序佇列。如果程序花費的時間超過所需的時間片，則將其降級到下一個優先順序佇列。相反，如果程序在低優先順序佇列中停留時間過長，則將其提升到更高的優先順序佇列。