速率單調排程

---

速率單調排程用於即時作業系統，它是一種優先順序分配，提供優先順序排程類。該演算法將為具有最小週期的任務分配更高的優先順序。因此，該演算法被稱為固定優先順序演算法，分配給任務的時間不會改變，這反過來也不會改變優先順序。所有這些優先順序在執行過程開始之前就已經確定，因此不會隨著時間的推移而改變。它是一個搶佔式演算法，當另一個具有更高優先順序的程序到達時，當前程序會被搶佔。這種搶佔是基於分配給每個程序組的優先順序級別進行的。

速率單調程序

此排程具有一個分析過程，其中包含一些執行緒假設，其屬性如下：

• 優先順序被設定為靜態的，以便更高優先順序的任務立即執行，搶佔其他剩餘的任務。

• 這些優先順序是根據速率單調約定分配的。

• 不允許共享資源，例如訊號量的阻塞或解除阻塞、任何硬體資源等。

• 執行緒函式和上下文切換週期沒有限制，並且不會受到為執行而設計的模型的影響。

如果該演算法滿足給定的截止期限，則認為它是最佳的，這適用於任何靜態優先順序演算法。如果給定的截止期限小於週期，則截止期限單調演算法也被認為是最佳的。

下面給出的公式應該由分配的排程滿足，並且應該滿足其截止期限。CPU 利用率低於給定下限由用於可排程性測試的最小上限公式給出：

$$\mathrm{U\:=\:\displaystyle\sum\limits_{i=1}^n\:(\frac{Ci}{Ti})\:\leq\:n\:(2^{\frac{1}{n}}\:−\:1)}$$

在上式中：

Ci - 程序計算時間

Ti - 程序執行週期（釋放週期）

N - 程序數

U - 處理器利用率。

當 n>=10 時，進行粗略的數值計算，則速率單調演算法將在 CPU 利用率 <70% 的情況下滿足所有給定的截止期限，剩餘的 30% 可用於較低優先順序的任務。

已經為較短週期的倍數任務推匯出上限，並且劉和萊蘭設計了這個諧波任務。它可以表示為 k 個諧波任務或鏈，上述公式可以改寫為：

$$\mathrm{U\:=\:\displaystyle\sum\limits_{i=1}^n\:(\frac{Ci}{Ti})\:\leq\:n\:(2^{\frac{1}{k}}\:−\:1)}$$

當 k=1 時，上限達到 1.0，這得出了 CPU 的完全利用率。

劉和萊蘭處理了另一個界限以獲得更嚴格的可排程條件，這被稱為雙曲線界限，其公式如下：

$$\mathrm{U\:=\:\prod_{i=1}^{n}\:(Ui\:+\:1)\:\leq\:2}$$

其中 Ui 是處理器利用率。

例如

考慮三個程序及其在下面表格中給出的執行時間和週期，在這裡我們計算滿足計劃截止期限的最小上限。

程序列表	執行率	時間
P1	2	5
P2	1	7
P3	2	10

在給定的表中，P1 與其他程序 P2 和 P3 相比具有最短的週期 5。因此，P1 將首先執行，然後是 P2，最後是 P3。

最小上限是根據所有給定程序的週期/執行率計算的，並將它們全部加在一起以獲得利用率值。

$$\mathrm{U\:=\:\frac{2}{5}\:+\:\frac{1}{7}\:+\:\frac{2}{10}\:=\:0.742}$$

對於給定的三個程序，我們使用以下公式推匯出計劃系統：

$\mathrm{U\:=\:3\:(2^{\frac{1}{3}}\:−\:1)\:=\:0.7796\:\gt\:0.742}$ 由於滿足此條件，系統可以使用最小上限值進行排程。

由於 P1 和 P3 被認為是諧波子集（因為 P3 是 P1 的 2 倍），因此可以對上述任務進行諧波分析。

$\mathrm{U_{harmonic}\:=\:K\:(2^{(\frac{1}{K})}\:−\:1)}$, k =2，所以 U 值將為 0.82

根據計算的總利用率 U，將其與 U 諧波 0.742 < 0.82 進行比較，因為匯出的諧波值越高，任務可以使用諧波子集值進行排程。

結論

如上所述，如果靜態優先順序演算法滿足目標截止期限，則速率單調演算法也執行相同的操作，並且它被稱為最佳的。儘管速率單調排程在滿足截止期限時被認為是最佳的，但它並沒有滿足 CPU 資源的最大利用率。當計劃任務週期和截止期限彼此不同時，它可能不是最佳的。優先順序旨在保持靜態，並且在執行期間不能更改，因為它們是預先定義的，這可能會導致另一個程序等待更長時間。