講稿: https://hackmd.io/WZHQpQKwS0GHwiRN04lPrQ
本文將會解決 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 都採用相同優先度、以及用不精確的計算得出的模型進行比較,評估結果表明本論文的策略可以大幅降低動態故障的機率。
一個實時應用(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 實施的問題,第六節總結。
考慮一個 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 組成的系統
過往的排程模型大致如下:每個 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 部分則不用考慮他們的差異。
對於每個 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。用
我們目標是防止 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
我們透過模擬器評估 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 的平均時長記為
在 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 效能的影響。
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%。
Fig. 4 展示了 (1, 2)-firm 和 (3-4)-firm 在兩個一樣的系統中的動態故障率。系統中有 5 個 bursty stream,
TABLE II 基於 Fig 4.,在 4a DBP 的動態故障率大致少了 95%、在 4b 減少幅度則較小。
比較 Fig 3. 及 Fig 4.,發現 bursty 模式的動態故障率要比 Poisson 高,這是因為 bursty 的尖峰負載是基於平均負載 (在此實驗中為 3 倍),尖峰負載時常大於 1,意味著系統常常超過負荷。
在 A、B 實驗中,我們都假設系統已知每個 customer 的 service time,所以可以把必定超過期限的 customer 丟掉,然而不是每一種系統都能預先知道 service time,這類系統必須執行每個 customer,不允許丟掉。
Fig 5. 展示了基於 Fig 3. 的系統,但是不允許丟掉 customer 的實驗結果。因為此實驗中,實質上獲得服務的 customer 更多了,動態故障的率也提高,雖然 DBP 相較 SP 減少超過 80% 的動態故障率,但動態故障率的數值仍然比 Fig 3. 高。
在前面的實驗中,每個 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 下,似乎是較為平衡的方案。
再次複習,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 的標籤。接著我們定義一個臨界點
在 Fig 7. 中,x 軸為
觀察發現 imprecise model 在合適的
imprecise model 還有一個問題,
從前面的實驗,我們已經確定根據 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% 的動態故障率。
DBP 中可供分配的優限度是基於 (m, k)-firm,當 stream
個不同的優先度,其中
然而現實上,一個系統通常會限制優先度的數量,將系統最大限制的優先度數量記為
當這個 stream 的 state 與 failing state 的距離大於
其中 s 和
Fig 9. 為一個全為 (2, 5)-firm deadline stream 的系統,系統負載固定為 0.8、interarrival time 為指數分布、所有 customer 的 service time 都一樣。在理想情況下,
當
Fig 10. 則展示
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 的機率。
我們的報告到此結束,謝謝大家