公平共享 CPU 排程

---

簡介

公平共享 CPU 排程是一種在作業系統中使用的排程演算法，旨在公平地分配 CPU 資源給不同的使用者或程序組。公平共享排程器根據每個程序或組的歷史使用情況為其分配權重，並根據這些權重分配 CPU 資源，確保沒有任何組長時間被剝奪資源。這可以實現更好的資源利用率，併為所有組提供平等的機會訪問 CPU。公平共享排程通常用於多使用者系統和虛擬化環境，在這些環境中，多個使用者或虛擬機器共享單個物理 CPU。

公平共享排程演算法

作業系統中可以使用多種公平共享排程演算法，包括：

• 加權公平佇列 (WFQ) − 該演算法根據每個程序或流的流量特徵為其分配權重，並確保每個流獲得其公平的 CPU 時間份額。

• 廣義處理器共享 (GPS) − GPS 是 WFQ 的更通用版本，並提供對 CPU 資源分配的更精確控制。它基於流體建模的概念，併為每個程序或流分配一個虛擬處理器。

• 隨機公平佇列 (SFQ) − 該演算法將可用頻寬劃分為大小相等的時間段，並根據其雜湊值將每個流分配到特定的時間段。這確保了每個流獲得公平的 CPU 時間份額。

• 公平佇列 (FQ) − FQ 為每個流分配一個佇列，並以迴圈方式服務這些佇列，確保每個佇列獲得其公平的 CPU 時間份額。

• 虛擬迴圈輪詢 (VRR) − VRR 為每個程序或流分配一個虛擬時間片，並以迴圈方式服務它們，確保每個程序或流獲得其公平的 CPU 時間份額。

公平共享排程的實現

公平共享排程可以透過多種方式實現，包括核心或使用者級軟體。

• 核心級實現 − 在核心中實現公平共享排程涉及以下步驟：

• 識別程序組 − 核心根據程序的所有權識別程序組。每個組根據其歷史 CPU 使用情況分配一個權重。

• 計算公平份額 − 核心根據每個程序組的權重計算其公平的 CPU 資源份額。

• 分配 CPU 資源 − 核心根據其公平份額向每個程序組分配 CPU 資源。如果程序組未使用其公平份額，則允許其累積未使用的資源以備將來使用。

• 調整權重 − 核心定期根據每個程序組最近的 CPU 使用情況調整其權重，以確保公平的資源分配。

• 使用者級實現 − 在使用者級實現公平共享排程需要以下步驟：

• 識別程序組 − 根據其資源需求或所有權將程序分組。每個組都被視為資源分配的單元。

• 分配權重 − 根據其資源需求或歷史使用情況為每個程序組分配權重。權重表示該組對 CPU 資源的權利。

• 計算公平份額 − 根據其權重計算每個程序組的公平 CPU 資源份額。公平份額表示該組在所有可用 CPU 資源中的份額。

• 分配 CPU 資源 − 根據其公平份額向每個程序組分配 CPU 資源。如果程序組未使用其公平份額，則允許其累積未使用的資源以備將來使用。

• 監控和調整權重 − 監控每個程序組的 CPU 使用情況，並根據其使用情況定期調整其權重。這確保了每個組隨著時間的推移都能獲得其公平的 CPU 資源份額。

• 在程式碼中實現 − 使用程式語言或庫在使用者級軟體中實現公平共享 CPU 排程演算法。程式碼應能夠對程序進行分組、分配權重、計算公平份額，並根據公平份額分配資源。

公平共享 CPU 排程的優點

以下是該演算法提供的一些優點：

• 公平性 − 公平共享排程確保 CPU 資源公平分配給不同的程序組，而不管其優先順序或資源需求如何。

• 資源利用率 − 公平共享排程透過根據歷史使用情況和權利分配 CPU 資源來最佳化資源利用率，而不是基於固定的優先順序方案。

• 防止飢餓 − 公平共享排程透過根據程序組的權利和未使用的資源分配 CPU 資源來防止資源飢餓。

• 可預測性 − 公平共享排程為每個程序組提供可預測的 CPU 資源分配，這可以提高系統穩定性和效能。

• 可擴充套件性 − 公平共享排程具有可擴充套件性，可以應用於具有大量程序或程序組的系統，確保每個組獲得其公平的 CPU 資源份額。

• 靈活性 − 公平共享排程允許使用者根據其資源需求和使用模式調整每個程序組的權重，從而在資源分配方面提供靈活性。

• 提高響應能力 − 公平共享排程可以透過確保 CPU 資源公平分配給不同的程序組來提高系統響應能力，從而降低 CPU 密集型程序獨佔資源的可能性。

公平共享 CPU 排程的侷限性

總的來說，雖然公平共享 CPU 排程可以提供一種平衡的資源分配方法，但它可能不適合所有系統或應用程式，並且需要仔細配置和管理才能確保正常執行。

• 開銷 − 公平共享 CPU 排程在計算上可能代價高昂，並且需要額外的開銷來跟蹤 CPU 使用情況和計算公平份額權重。

• 複雜性 − 公平共享排程比其他排程演算法更復雜，並且需要額外的配置和管理才能確保正常執行。

• 缺乏靈活性 − 公平共享排程可能不適合具有硬即時要求的系統或需要固定分配 CPU 資源的應用程式。

• 依賴於使用者級實現 − 公平共享排程的使用者級實現可能不如核心級實現高效，並且可能會引入額外的開銷和複雜性。

• 難以調整 − 調整公平份額權重可能很困難，因為它需要了解每個程序組的資源需求和使用模式。

• 有效性有限 − 在具有大量短暫程序的系統或資源需求變化很大的系統中，公平共享排程可能無效。

與其他排程演算法的整合

公平共享排程可以與其他排程演算法整合，以提高系統的整體效率和公平性。以下是公平共享排程可以與其他排程演算法整合的一些方法：

• 多級反饋佇列 − 公平共享排程可以與多級反饋佇列 (MLFQ) 演算法整合，以提供更平衡的資源分配方法。MLFQ 演算法可用於根據優先順序分配 CPU 資源，而公平共享排程可用於確保每個程序組獲得其公平的 CPU 資源份額。

• 基於優先順序的排程 − 公平共享排程可以與基於優先順序的排程演算法整合，以提供更平衡的資源分配方法。基於優先順序的演算法可用於根據優先順序分配 CPU 資源，而公平共享排程可用於確保每個程序組獲得其公平的 CPU 資源份額。

• 即時排程 − 公平共享排程可以與即時排程演算法整合，以提供更平衡的資源分配方法。即時排程演算法可用於根據截止日期分配 CPU 資源，而公平共享排程可用於確保每個程序組獲得其公平的 CPU 資源份額。

公平共享的計算

在公平共享 CPU 排程中，公平共享權重的計算基於授權和使用量的概念。程序組的公平共享權重計算如下：

• 確定程序組在最近一段時間內的歷史使用情況（例如，最近一分鐘、最近一小時等）。

• 根據可用的總 CPU 資源和程序組的數量，計算程序組的授權量。

• 將程序組的歷史使用量與授權量之比計算為程序組的公平共享權重。

例如，假設系統中有三個程序組，其歷史 CPU 使用情況如下：

• 組 A：10 秒

• 組 B：20 秒

• 組 C：30 秒

假設可用的總 CPU 時間為 60 秒，則每個程序組的授權量為 20 秒（即 60 / 3）。每個程序組的公平共享權重可以計算如下：

• 組 A：10 / 20 = 0.5

• 組 B：20 / 20 = 1

• 組 C：30 / 20 = 1.5

因此，組 A 有權使用 50% 的 CPU 資源，組 B 有權使用 100% 的 CPU 資源，組 C 有權使用 150% 的 CPU 資源。公平共享排程程式將根據其公平共享權重為每個程序組分配 CPU 資源，確保每個程序組隨著時間的推移獲得其公平份額的 CPU 資源。

結論

總的來說，公平共享 CPU 排程是一種有用的技術，可以確保 CPU 資源在不同的程序組之間公平有效地分配，並且可以成為任何作業系統排程程式的有價值的補充。