A Dynamic Priority Assignment Technique for Streams with (m, k)-Firm Deadlines

講稿: https://hackmd.io/WZHQpQKwS0GHwiRN04lPrQ

• A Dynamic Priority Assignment Technique for Streams with (m, k)-Firm Deadlines
  • 摘要
  • I. 引言
  • II. 系統模型與定義問題
  • III. 基於距離分配優先度
  • IV. 評估 DBP 方案
    • A. Poisson Streams
    • B. Bursty Streams
    • C. No-Drop Policy (不可以丟掉 customer)
    • D. 異質系統
    • E. 與 Imprecise model 比較
    • F. Stream 數量對效能的影響
  • V. 限制優先度數量
  • VI. 總結

https://docs.google.com/presentation/d/1wwSZD0aqTqZQYbWdKj12b7Fi1LnNMoizE22vn-lUWNk/edit#slide=id.g1053627ad27_0_99

摘要

本文將會解決 scheduling multiple streams of real-time customers。首先介紹 (m, k)-firm deadlines 的概念以表達對 real-time stream 計時的限制：任何 k 個連續 customer 中至少有 m 個必須滿足他們的期限（deadline），則稱此 stream 擁有 (m, k)-firm deadlines；如果少於 m 個 meet deadline（即超過期限），則此 (m, k)-firm deadline stream 會遭遇動態故障（dynamic failure）。

接下來本論文提出一中基於優先度（priority）的策略，用以在單個 server 上排程 N 個 real-time stream，並減少動態故障的機率。基本的想法是提高 stream 中故障率較高的 customers 的優先度，以提高他們 meet deadline 的機會。本論文使用 heuristic 的方式分配優先級，並通過各種 customer arrival 與 service pattern 的模擬來評估，本論文的策略與傳統上所有 customer 都採用相同優先度、以及用不精確的計算得出的模型進行比較，評估結果表明本論文的策略可以大幅降低動態故障的機率。

I. 引言

一個實時應用（real-time application）由一組協作的 tasks 組成，這些 task 會頻繁的傳遞 message 來互動，所有 task 都期望在期限前獲得完整的服務。實時應用的例子包括：程序控制、生命維持系統、自動製造系統、機器人、航天飛機和多媒體。在某些情況下，task 或 message 未能在期限前完成會產生災難性後果，因此及時完成非常重要，此類任務被視為 hard deadline。相反的，有些實時應用不需要每個任務都 meet deadline，這類則被視為 soft deadline，如影音播放器。

傳統上我們用最大允許丟失（maximum allowable loss percentage）來表達對於未 meet deadline 的容忍度，例如在影片串流允許 10% 的丟失率。然而最大允許丟失有一個隱含的假設，就是這些未 meet deadline 的任務盡可能不連續，拿影片串流為例，如果連續好幾幀都丟失，就算整部影片的丟失率為 10%，影片品質還是會受影響。為了解決上述的弊端，我們可以用另一個方法來表達容忍度：在任意 k 個連續幀中至少有 m 個幀滿足它們的期限，即 (m, k)-firm deadline。

本論文解決的問題是調度一組 N 個 real-time customer stream ，其中每個 stream 都有自己的期限，以減少動態故障的機率，為了達成前述目標，我們給每個 customer 分配優先度。最基本的想法為 distance-based priority (DBP)，根據最近未 meet deadline 的歷史紀錄來分配優先度，如果某個 stream 中的若干個 customer 未 meet deadline，則此 stream 中的下一個 customer 將會被分配更高的優先度，server 會參考優先度與其他參數進行排程。我們將 DBP 與 single priority (SP) 進行比較，即所有 customer 都是相同的優先度。 結果表明使用 DBP，動態故障的機率大幅降低。由於本論文使用 (m, k)-Firm 來評估，與以往的論文使用最大允許丟失不同，很難互相比較，因為後者容許大量連續的丟失。

此外，(m, k)-firm 也可以套用在 imprecise computation 模型，在此類模型中，customer 被區分為強制性（mandatory）與選擇性（optional）執行，前者必須要被執行，後者則是在資源足夠的情況下被執行，並且後者可以優化前者計算的結果。我們可以規定：在任意連續 k 個 customer 中，至少有 m 個 mandatory 滿足他們的期限。雖然這種方法可以顯著降低動態失敗的機率，但代價是更高的錯過期限的總體機率。

本文的其餘部分安排如下，第二部分描述了系統模型和 (m, k)-firm 的概念，在第三節中我們描述基於距離分配優先度，在第四節提出實驗評估的結果，第五節討論了以較少的 priority levels 實施的問題，第六節總結。

II. 系統模型與定義問題

考慮一個 real-time customer stream，其中 customer 可以是 task、message 或實時應用程式中的任何其他可調度實體。stream 中的每個 customer 都有一個期限，它期望系統在期限內提供完整的服務。(m, k)-firm 的定義如引言所講的，就不多做翻譯。

傳統上期望 stream 裡的每一個 customer 都 meet deadline，可以標記為 (1, 1)-firm deadlines；而 (1, 2)-firm 則表示不可以連續兩個 customer 錯過期限；同樣的 (4, 6)-firm 表示不可以連續三個 customer 錯過期限，並且在任連續 6 個 customer 中必有 4 個 meet deadline。我們也可以注意到 (m, k)-firm 有 (k - m)/k 的最大允許丟失，例如 (4, 5)-firm 和 (8, 10)-firm 的最大允許丟失同為 20% (其中 (4, 5)-firm 比 (8, 10)-firm 更為嚴格)。

考慮一個由 N 個 stream 組成的系統

$R_1,R_2,...,R_N$，其中

$R_j$ 有

$(m_j,k_j)-\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{m}\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}$，本文解決的問題就是將 customer 調度在單個 server 上，以降低平均動態故障機率，最直接的方法就是降低 customer 超過期限的機率。

過往的排程模型大致如下：每個 stream 各自擁有 first-in first-out queue，這些 queue 保證 customer 按照到達的先後順序執行，另外會有一個 service queue 從這些 stream queue 的端點中選擇 customer 執行，如下圖：

第一種基於上述模型的排程方法為 first-in first-out policy：service queue 從所有 stream queue 的端點中選擇最早到達的 customer 執行，此方法不管每個 customer 的期限。另一種排程方法為 earliest-deadline-first policy：service queue 選擇離期限最近的 customer 先執行。

本論文提出的方法也可以應用在上述模型，為每個 stream queue 端點的 customer 分配優先度，service queue 會放入優先度高的 customer。如果優先度都一樣高，則改用前面提到的兩種 policy 排程。因為過往的研究表示 earliest-deadline-first policy 表現比較好，所以本篇論文提出的方法在優先度一樣高時會使用 earliest-deadline-first policy。

在進入 III 部分前，還有一個概念需要提點一下：在某些系統中，正在等待的 customer 是否已經錯過期限是可以被偵測的，某些應用程式會直接跳過這些遲遲未執行的 customer，又稱為 dropped customer；相反地，如果系統無法偵測 customer 是否已經錯過期限，則每個 customer 都必須被執行。我們將在第 IV 部分討論這兩種系統的可能性，而第 III 部分則不用考慮他們的差異。

III. 基於距離分配優先度

對於每個 stream，系統會記錄最近一次 met 或是 missed the deadlines 的 state。我們編號各個 streams 的 customers 依據其先後順序，分別為 1, 2, 3, …。一個 customer 可能是 serviced completely 或是 dropped prior to service。一個 serviced customer 可能 miss 或是 meet the deadline。而所有 dropped customers 則是被視為 miss the deadline。用

${\delta }_i^j$ 表示 stream

$R_j$ 的

$i$th customer 的狀態,

$i\ge 1$。用一個

$k_j$-tuple (

${\delta }_{i-k_j+1}^j$, …,

${\delta }_{i-1}^j$,

${\delta }_i^j$) 代表一個給定時間 stream

$R_j$ 的狀態。如果 stream

$R_j$ 呈現一個 meet 數量少於

$m_j$ 的狀態，則稱此狀態是

$R_j$ 的 failing state。

我們目標是防止 streams 進入 failing state，所以想法是越接近 failing state 的 stream，就給此 stream 的下一個 customer 更高的優先度。本篇論文提出的方法是，assign 一個數稱 priority value 給 customer，這個數值代表這個 stream 從 current state 到 failing state 所需最少的連續 miss 數量。而 costumer 的 priority value 越小，server 就會給其越高的優先度。

下圖是 (2, 3)-firm deadline stream 的 state transition diagram：

字母 M 和 m 分別代表 meet 和 miss，而 state 則是由 3 個字母組合的 string。比如說，MMm 代表最近 3 個 customers 分別 miss、meet、meet the deadlines。Edge 則是代表下一個 customer 的 meet/miss 情況。上色的 states 因為 less than 2 meets，表示為 failing states。如果該 stream 是在 failing state，則其下一個 customer 的 priority value 標記為 0。如果該 stream 是在 MMm、MmM state，代表距離 failing state 為 1，設 priority value 為 1。如果是在 MMM、mMM state，代表距離 failing state 為 2，設 priority value 為 2。

在一般情況下，只有少部分的 stream 會在 failing state，而這些 stream 就會受益於被賦予高 piority，同時其他 stream 不會受到嚴重的影響。因此 DBP 可以降低 dynamic failure 的機率。

DBP 也有利於一種情況，就是不同 stream 有不同的期限要求時。比如說，有兩個 streams 分別為 (3, 5)-firm deadlines 和 (9, 10)-firm deadlines，其餘因素相同 (same customer service time distribution, same customer interarrival distribution, same customer deadline distribution)。第一個 stream 在連續 5 個 customers 中可以容忍 2 misses，40% loss rate。第二個 stream 在連續 10 個 customers 種只可以容忍 1 miss，10% loss rate。在傳統的 single priority scheme 中，不會考慮到不同 streams 的 requirements，導致兩個 streams 有一樣的 loss rate。但是用 DBP 策略，第二個 stream 會比較常拿到 higher priority。在兩個 streams 都是在 miss-free states 時，第一個 stream 到 failing state 的距離是 3，第二個 stream 到 failing state 的距離是 2。因此在以上情況，(9, 10)-firm deadlines 仍然會有較高的優先度。這種方式跟靜態得給 deadline requirement 高的 stream 比較高的優先度也不一樣。DBP 在某些情況 (3, 5)-firm deadlines 也能得到比 (9, 10)-firm deadlines 高的優先度。比如說，第一個 stream 距離 failing state 只差一個 miss，而第二個 stream 處在 miss-free states。

這種策略可以簡單地用軟、硬體實現。Stream

$R_j$ 的 state 可以保存在一個

$k_j$-bit 的 shift register。分別用 bit 0 和 1 代表 miss 和 meet 的情況。當下一個 customer 被服務完後，根據是 miss 還是 meet 從右邊 shift in 0 或是 1。用

$l_j(n,s)$ 表示 stream

$R_j$ 的 state

$s$ 中，從右邊數來第 n 個 meet (or 1) 的位置。如果 state

$s$ 中少於 n 個 1，則

$l_j(n,s)=k_j+1$。舉例來說，假設 stream

$R_1$ 是 (1, 3)-firm deadlines，則

$l_1$(1, MmM) = 1,

$l_1$(2, MmM) = 3。如果 n > 2，

$l_1$(n, MmM) =

$k_1$ + 1 = 4。而 priority assigned to customer i + 1 from stream

$R_j$ is given by：

$$\begin{array}{c}{\text{priority }}_{i+1}^j=k_j-l_j(m_j,s)+1\end{array}$$

IV. 評估 DBP 方案

我們透過模擬器評估 DBP 與 single priority (SP)，在這兩種方案中，如果 customer 優先度相同則採用 earliest-deadline-first 排程。

我們使用兩種模式來生成 customer，分別為 Poisson 與 bursty。在 Poisson 模式中，customer 的 interarrival time 為指數分布；bursty 則分為 ON 與 OFF 兩種狀態，狀態為 ON 時會定期產生 customer，OFF 時則不產生 customer，ON 與 OFF 的時長為指數分布，並把 ON 與 OFF 的平均時長記為

$O{N}_{ave}$ 和

$OF{F}_{ave}$。bursty 模式常常被用來模擬談話中的聲音，人在交談時為 ON，安靜時為 OFF。

在 A、B 中，我們首先考慮系統中所有 stream 有一樣的 (m,k)-firm，我們也假定只有 meet deadline 的 customer 能夠獲得服務。在 C 中我們在一個不管有沒有 meet deadline，所有 customer 都會獲得服務的系統中，比較 DBP 與 SP。在 D，我們考慮一個異質系統，其中有些 stream 有比較嚴格的 (m,k)-firm。在 E 我們將 DBP 和 SP 與另一個基於此系統的 imprecise model 比較 (在引言倒數第二段有介紹 imprecise model)。最後在 F 我們測試了 stream 數量對 DBP 效能的影響。

A. Poisson Streams

Fig. 3 展示了 (1, 2)-firm 和 (3-4)-firm 在兩個一樣的系統中的動態故障率。系統中有 5 個 Poisson stream、所有 customer 的 service time 固定不變且期限為 service time 的 5 倍、customer 的 interarrival time 為指數分布，透過調整 interarrival time 來讓系統的平均負載介於 0.2 至 0.9。

Fig 3a 和 3b 唯一的差異在於對錯過期限的容忍度，3a 允許任 2 個連續 customer 中 1 個錯過期限，而 3b 比較嚴格，只允許任 4 個中 1 個錯過期限，也因此 3b 的動態故障率較高。

TABLE I 基於 Fig 3.，以數字表明了在各種負載下，DBP 相較 SP 少了多少動態故障的機率。在 3a 大致少了 60%、在 3b 少了 40%。

B. Bursty Streams

Fig. 4 展示了 (1, 2)-firm 和 (3-4)-firm 在兩個一樣的系統中的動態故障率。系統中有 5 個 bursty stream，

$O{N}_{ave}$ 為 50 微秒、

$OF{F}_{ave}$ 為 100 微秒，因此可以得到尖峰負載為平均負載的三倍。在 ON 狀態下，每個 stream 每 5 微秒會生成一個 customer、期限為 10 微秒、透過拉長 service time 來增加負載。一樣的，實驗結果表明 DBP 較 SP 優。

TABLE II 基於 Fig 4.，在 4a DBP 的動態故障率大致少了 95%、在 4b 減少幅度則較小。

比較 Fig 3. 及 Fig 4.，發現 bursty 模式的動態故障率要比 Poisson 高，這是因為 bursty 的尖峰負載是基於平均負載 (在此實驗中為 3 倍)，尖峰負載時常大於 1，意味著系統常常超過負荷。

C. No-Drop Policy (不可以丟掉 customer)

在 A、B 實驗中，我們都假設系統已知每個 customer 的 service time，所以可以把必定超過期限的 customer 丟掉，然而不是每一種系統都能預先知道 service time，這類系統必須執行每個 customer，不允許丟掉。

Fig 5. 展示了基於 Fig 3. 的系統，但是不允許丟掉 customer 的實驗結果。因為此實驗中，實質上獲得服務的 customer 更多了，動態故障的率也提高，雖然 DBP 相較 SP 減少超過 80% 的動態故障率，但動態故障率的數值仍然比 Fig 3. 高。

D. 異質系統

在前面的實驗中，每個 stream 的 (m,k)-firm 都相同。本實驗將每個 stream 設為不同的 (m, k)-firm。分別為 (9, 10)-firm、(3, 4)-firm、(1, 2)-firm、(1, 3)-firm、(1, 4)-firm，其餘條件則同 Fig 3.。

在 Fig 6. 中，我們單獨挑出負載為 0.5、0.7、0.9 的數據觀察，分別對應 6a、6b、6c。本次實驗除了 SP、DBP 外，還測試了 fixed priority (FP)，在 FP 方案中，時效要求越高的 stream 會被分配越高的優先度，也就是 (9, 10)-firm stream 的 customer 會被固定為最高優先度，其次 (3, 4)-firm…，(1, 4)-firm stream 的 customer 為最低優先度。FP 也符合 earliest-deadline-first policy。

觀察 Fig 6.，在 SP 中，(m, k)-firm 越嚴格則動態故障率越高；相反的，在 FP 中，優先度越高則動態故障率則通常偏低。這表明了 (m, k)-firm deadline 與優先度是影響動態故障率的兩個因素，動態故障率的高低取決於這兩者的平衡。

最後觀察 DBP 擁有最低的平均動態故障率，而且在嚴格的 (m, k)-firm 下表現遠超 SP，但是在系統負載偏低以及 (m, k)-firm 較不嚴格的 stream 表現較差。另一方面，DBP 在 (m, k)-firm 較不緊迫的 stream 表現較 FP 好。最後綜觀 5a 5b 5c，DBP 在不同的 (m, k)-firm deadline 下，似乎是較為平衡的方案。

E. 與 Imprecise model 比較

再次複習，Imprecise model 會將 customer 區分為 mandatory 與 optional。mandatory 必須獲得服務，optional 則是拿來優化 mandotary 的結果，而且在系統負載過高時可以被丟棄。

在本實驗中，將 (m, k)-firm 結合 imprecise model，令每個 stream 中，連續 k 個 customer 裡要有 m 個 mandotary customer。本次實驗的系統基於 Fig. 5b. 的由 (3, 4)-firm stream 組成的系統，並將 customer 掛上 mandotary 和 optional 的標籤。接著我們定義一個臨界點

$T$，當在 service queue 中等候的 customer 數量超過

$T$ 時，之後到達的 optional customer 會直接被丟掉。注意，當

$T=0$ 所有 optional 都會被丟棄；當

$T=\mathrm{\infty }$ 則所有 optional 都會獲得服務，排程邏輯等同於 SP。

在 Fig 7. 中，x 軸為

$T$ 的值，介於 0 到 8，左圖 y 軸為動態故障率，右圖 y 軸為 customer 錯過期限的機率。只有 IMPRECISE 會用到

$T$，而 SP 與 DBP 並不會使用到

$T$，因此我們可以看到不管

$T$ 的值為何，SP 與 DBP 的動態故障率都不變，為兩條水平線。Fig 7. 只抓取平均負載為 0.3、0.6、0.8 來觀察。

觀察發現 imprecise model 在合適的

$T$ 下，動態故障率與 DBP 差不多低，例如在負載較高且

$T=0$ 時，左圖動態故障率低。然而隨之而來的是右圖 customer 錯過期限率大幅提升，因為當

$T=0$ 時，所有 optional customer 都會被丟掉，而系統中所有 stream 都是 (3, 4)-firm，所以每四個 customer 必定會丟掉 1 個，導致錯過期限率大於等於 0.25。反觀 DBP 則可以在不拉高錯過期限率的情況下降低動態故障率。

imprecise model 還有一個問題，

$T$ 的值需要依據系統負載來調整，我們可以看到在系統負載為 0.3 時，

$T=0$ 反而對 imprecise model 造成很差的效果。

F. Stream 數量對效能的影響

從前面的實驗，我們已經確定根據 stream 的 state 來分配優先度可以降低動態故障率，因此系統中 stream 的數量會決定降低的幅度，如果系統中只有一個 stream，DBP 的效果會完全等於 SP。為了研究 stream 數量對 DBP 的影響，這次實驗，我們逐次增加 stream 的數量，並且調整 arrival rate 讓整個系統的平均負載保持相同。

在 Fig 8. 中，系統的平均負載為 0.7、interarrival time 是指數分布、所有 stream 都是 (1, 2)-firm deadline。8a 中所有 customer 都會獲得服務、8b 中只有趕得上期限的 customer 會得到服務。

我們可以觀察，當 stream 數量為 1，SP 與 DBP 的動態故障率是一樣的，隨著 stream 數量越多，DBP 的動態故障率以顯著的幅度下降，在 3a 中，3 個 stream 的狀況下 DBP 較 SP 少了 70% 的動態故障率。

V. 限制優先度數量

DBP 中可供分配的優限度是基於 (m, k)-firm，當 stream

$R_j$ 為

$(m_j,k_j)-\mathrm{f}\mathrm{i}\mathrm{r}\mathrm{m}$，則總共有

$k_j-m_j+2$ 個優先度可供分配。例如在 (2, 5)-firm 的情況下，優先度分為 0, 1, 2, 3, 4；在 (4, 5)-firm 的情況下，優先度分為 0, 1, 2。因此，在多個不同 (m, k)-firm stream 的系統，必須支援

$P=\mathrm{m}\mathrm{a}\mathrm{x}\{{\mathrm{k}}_{\mathrm{j}}-{\mathrm{m}}_{\mathrm{j}}+2:\mathrm{j}=1,2,...,\mathrm{N}\}$

個不同的優先度，其中

$N$ 為 stream 的數量。

然而現實上，一個系統通常會限制優先度的數量，將系統最大限制的優先度數量記為

$P_{max}$ (優先度介於 0 到

$P_{max}-1$)，在這個章節我們將討論

$P_{max}<P$ 的狀況。

當這個 stream 的 state 與 failing state 的距離大於

$P_{max}-1$，則還是分配

$P_{max}-1$ 給它的 customer，用以下式子表達

$R_j$ 的第

$i+1$ 個 customer 將會分配到的優先度

${\text{priority }}_{i+1}^j=\mathrm{m}\mathrm{i}\mathrm{n}\{{\mathrm{k}}_{\mathrm{j}}-{\mathrm{l}}_{\mathrm{j}}({\mathrm{m}}_{\mathrm{j}},\mathrm{s})+1,{\mathrm{P}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-1\}$

其中 s 和

$l_j$ 是我們在第 III 節提到的

$R_j$ 的 state 與右邊數來 meet 的位置。

Fig 9. 為一個全為 (2, 5)-firm deadline stream 的系統，系統負載固定為 0.8、interarrival time 為指數分布、所有 customer 的 service time 都一樣。在理想情況下，

$P=5$ 且有 0, 1, 2, 3, 4 五種優先度，但是我們透過調整

$P_{max}$ 觀察優先度的數量限制對動態故障率的影響。左圖所有 customer 都會獲得服務；右圖只有期限內可以完成的 customer 可以獲得服務，其餘則被丟掉。

當

$P_{max}=1$ 時，只有一種優先度，等同於 SP。觀察 Fig 9. 可以發現其實

$P_{max}=3$ 時，DBP 的效果就足夠好了，其中 failing state stream 中的 customer 會被分配優先度 0、近期只有 1 個 customer 錯過期限的 stream 則會分配為 1、其餘分配為 2。

Fig 10. 則展示

$P_{max}$ 對異質系統的影響，五個 stream 分別為 (9, 10)-firm、(3, 4)-firm、(1, 2)-firm、(1, 3)-firm、(1, 4)-firm，其餘條件與 fig 9. 的實驗相同。這裡我們一樣可以發現當

$P_{max}=3$ 時，DBP 就已經展現可觀的效果了。

VI. 總結

real-time customer 有其時限，根據應用不同，又分為 hard real-time (所有 customer 都要 meet deadline) 與 soft real-time (滿足 miss rate 即可)，前者過於嚴格，後者過於寬鬆。本論文介紹了一個 deadline model 概括了 hard 和 soft real-time 的概念，在這個模型裡每個 stream 有兩個參數 m 和 k，如果 k 個連續客戶中少於 m 個滿足他們的期限，就會發生動態故障，藉此更精確地表達實時應用程序的要求。

接著本論文提 Distance-Based Priority (DBP)，較接近 failing state 的 stream 會被分配更高的 priority，以提高它的 customer meet deadline 的機會。本方法與 Single Priority、Fix priority 和 IMPRESICE model 進行了比較，實驗結果表明，DBP 大幅降低了 dynamic failure 的概率，同時不會極大地影響整體的 customer miss deadline 的機率。

我們的報告到此結束，謝謝大家