以工作重要性或選擇性為基礎之分散式嚴密即時排程

Abstract

於分散式環境中，工作具有截止時間限制的嚴密即時排程是一個著名的NP-hard 問題 。我們發展對系統狀態變動而能迅速應變的動態嚴密即時排程方法，我們考慮的工作 有下列屬性：抵達時間、執行時間、截止時間與重要程度。由於根基於最早截止時間 優先之排程，於低負載情況下，皆有近於最佳之排程。因此，我們的方法亦根基於最 早截止時間優先排程。但是當一新工作抵達系統，局部節點無法保證此新抵達工作於 截止時間內執行完畢時，我們並非無條件轉移新抵達的工作，考量於此局部節點已獲 保證的工作與此新抵達工作之屬性，決定轉移的工作。 當新工作抵達系統時，若局部節點無法滿足此新抵達工作之截止的時間時，無條件保 證方式的，可能造成系統的打滾現象，因而造成系統效能的不可預期。我們發展了多 個明顯考慮工作截止時間、執行時間與重要程度的有條件方式排程方法。藉由模擬方 式，檢視各種系統參數 (包括系統負載、系統負載分佈、工作彈性時間) ，對這些策 略的效能之影響。我們發現，這種將工作之排程力與服務力予以區分的有條件保證方 式排程，於低負載的與無條件保證方式排程有相近的保證比率與加權保證比率；但是 於超負載時，其效能皆比無條件保證方式提昇許多。 另外，基於容錯之可選擇性軟體的發展，我們探討可選擇性工作於即時系統之可行性 。實驗結果顯示，此類可選擇性工作排程對系統狀態之改變，尤其對負載的變動，有 較佳的反應，因此隨著系統負載的增加，其效能降低速度較無選擇性工作排程緩慢了 許多。