異構系統中帶可用性約束的性能優化調度算法

孫健,張興軍,董小社

(西安交通大學電子與信息工程學院,710049,西安)

可用性是衡量復雜計算機系統的關鍵指標之一,特別是近年來異構系統的日益發展,伴隨系統規模以及實時應用范圍的逐步擴大,研究異構系統中多實時任務的可用性需求問題具有非常重要的理論與實際意義。該研究領域內涌現出諸多以滿足實時任務的具體可用性需求,并通過帶可用性約束的調度策略來實現系統內實時任務合理調度分配的實時任務調度算法[1-2]。

早期實時任務調度理論中對任務調度算法的最基本假設是系統內所有用于任務分配執行的處理機節點均可用[3]。該假設僅在理想狀態的多處理機系統實時任務調度中是合理的,但在復雜計算機系統特別是異構系統中,由于系統故障宕機、失效修復等情況時有發生常導致系統不可用,此時該假設便不再適用。另外,異構系統內各處理機節點的實時任務執行時間即任務響應時間也各不相同,為選取系統內任務分配的處理機節點增添了難度。為此,在設計實時任務調度算法時應充分考慮各實時任務的具體可用性需求即可用性約束,并在此基礎上權衡系統調度分配過程中的任務響應時間,保證在任務可調度性以及可用性的前提下實現異構系統中實時任務的合理調度。

針對上述問題,本文提出一種異構系統中帶可用性約束的性能優化調度算法,構建系統內處理機節點、實時任務以及帶可用性約束的實時任務調度模型,通過引入可用性成本和系統綜合開銷,考慮可用性成本與任務平均響應時間的折中,為實時任務分配系統綜合開銷最少的處理機節點,合理利用異構系統調度資源,在提升實時任務調度可用性的同時進一步優化異構系統的調度性能。

1 相關工作

目前,異構系統中可用性相關的實時任務調度算法大致可分為兩類:一類是可用性受限的實時任務調度算法,即在滿足實時任務可用性約束的前提下,對以往僅考慮任務執行時間的調度算法進行優化改進,典型算法如QoS-SAC[4]、SSAC[5]等;另一類是實時任務本身無可用性約束,而在算法設計中考慮可用性因素調度策略,旨在提升系統整體以及實時任務分配執行的可用性水平和性能,如HMSAS[6]、ADSS[7]等。

多處理機異構環境下的實時任務最優分配一直是一個難以解決的NP完全問題[8]?？紤]可用性受限的實時任務調度算法,Xie等首次提出了異構系統中帶可用性約束的多任務組調度策略(SSAC)[9],該策略的核心思想是結合任務平均響應時間和可用性約束對實時任務進行數學建模,根據任務的具體可用性約束,為其選擇系統內滿足該約束的候選處理機集合,并將任務分配至集合中任務平均響應時間最短的處理機處理執行,在提升調度性能的同時提高系統可用性。此外,Tong等考慮系統QoS以及可用性需求,在文獻[5,9]的基礎上,針對異構分布式系統設計可用性受限的實時任務調度算法(QoS-SAC)[4],以縮短實時任務的完成時間同時提高系統可用性。

本文提出的異構系統中帶可用性約束的性能優化調度算法(PO-SSAC),在實時任務調度執行時考慮任務平均響應時間與可用性成本的折中,并為其分配系統綜合開銷最少的處理機節點,與SSAC以及其他現有算法相比,進一步提升了異構系統的實時任務調度可用性以及性能,實現了系統資源的合理利用。

2 實時任務調度模型

2.1 帶可用性約束的實時任務調度框架結構

本文所需解決的具體問題是如何在可用性受限的情況下對異構系統中實時任務進行合理調度分配,并在提升系統任務調度可用性的基礎上進一步優化調度性能。根據上述問題描述,異構系統中帶可用性約束的實時任務調度框架結構如圖1所示。

圖1 帶可用性約束的實時任務調度框架結構

調度器是實時任務調度框架結構的核心,負責調度分配來自各不同用戶的任務組隊列,并實時監測異構系統內所有處理機節點的運行狀態,及時獲取各處理機節點的運行狀態信息。調度隊列負責接收來自各用戶的任務組,調度器按照先來先服務原則接收所有到達的實時任務,分配其至各處理機節點,并由處理機節點內本地隊列實現對各實時任務的并行處理。

對于每個來自用戶的實時任務,處理機定位器為其篩選一個候選處理機集合,集合包含所有滿足該任務可用性需求即可用性約束的處理機節點。若集合非空,調度器從集合內選擇系統綜合開銷最少的處理機節點,并分配任務至該處理機節點處理執行;若集合為空,說明沒有候選處理機節點滿足當前任務的可用性約束,此時可用性成本計算器計算系統內能夠滿足該任務可用性約束的處理機節點,并將其添加至候選處理機集合。負載均衡檢測器檢測候選處理機節點是否超載,超載時實時任務將被分配至負載最輕的處理機節點,否則分配至該處理機節點處理執行。

2.2 處理機和實時任務模型

對異構系統內處理機和實時任務進行如下的形式化數學描述。①處理機模型。異構系統指由一定數量內部構造不同且相互獨立的自治節點,通過高速互聯網絡相互連接所共同組成的高性能、高可用計算機系統,能夠作為一個整體為用戶提供所需的應用服務。設異構系統處理機集合H={N1,N2,…,Nj,…,Nn,j=1～n},n為處理機節點數。H中各處理機節點處理能力由每秒百萬條指令(MIPS)來衡量,同時由于是異構系統,假設各處理機節點處理能力和可用性均不相同。②實時任務模型。設實時任務集合TG={t1,t2,…,ti,…,tm,i=1～m},m為來自用戶的實時任務數。系統根據用戶的可用性需求為實時任務設定可用性約束,范圍為0～1,實時任務必須分配至能夠滿足其可用性約束的處理機節點以確保得到成功處理。

定義實時任務ti在處理機節點Nj上執行的平均響應時間

φj))

(1)

式中:sj為實時任務集合TG在處理機節點Nj上的服務時間;sj2為sj的二階矩;E(sj)為服務時間均值;E(sj2)為服務時間均方。處理機節點Nj的任務到達率為Λj,服務率為φj,假設異構系統內任務到達模式和服務率是先驗的,則Λj與φj均可通過代碼剖析和統計預測方法估算得出。

2.3 帶可用性約束的實時任務調度模型

本文異構系統中可用性均為穩態可用性,是指在某個時間段內系統維持正常運行狀態的概率。定義異構系統內處理機節點Nj的可用性為ξj,表示任意時間段內處理機節點Nj可提供持續運算處理的概率,相應的異構系統內處理機節點Nj的不可用性為θj。定義實時任務ti的可用性約束為ai,代表任務ti必須執行成功的概率,例如,當ai=0.85時,任務ti執行失敗的概率不得高于0.15。

進一步定義aij為實時任務ti在處理機節點Nj上的可用性成本

aij=pijθj/μij

(2)

式中:pij為實時任務ti分配至處理機節點Nj的概率;μij為實時任務ti分配至處理機節點Nj的服務率。

本文引入綜合性能開銷的概念,定義Cij為實時任務ti在處理機節點Nj上的系統綜合開銷,結合式(1)和式(2),得到Cij的計算公式為

(3)

結合2.2小節對處理機和實時任務模型的相關分析,將帶可用性約束的性能優化調度問題抽象為異構系統可用性與實時任務平均響應時間兩者之間的折中,則本文調度算法的設計目標可描述為:提高實時任務調度分配的可用性;合理利用資源減少系統綜合開銷,即保證較短的實時任務平均響應時間和較低的處理執行可用性成本,得到如下數學模型

(4)

系統綜合開銷約束條件為

?1≤i≤m,1≤j≤n,ai≤ξj:minCij

在該數學模型中,A為異構系統實時任務調度的系統可用性;λi為實時任務ti的到達率且符合泊松過程;λ為實時任務集合TG在異構系統中的總平均到達率。

3 帶可用性約束的性能優化調度算法

實時任務平均響應時間在很大程度上依賴于異構系統中各處理機節點所采用的具體排序策略,因此本文所提PO-SSAC算法采用文獻[10]中給出的最優排序策略以最大程度減少異構系統中實時任務集合的平均響應時間,并作如下命題。

命題1 已知m組實時任務隊列和由n個處理機節點構成的異構系統,根據最優排序策略,在處理機節點Nj上,當μij≥μkj時,實時任務ti的優先級高于tk。

上述命題說明高服務率的實時任務在調度分配時必須擁有相對較高的優先級,以達到縮短任務平均響應時間的目的。為簡化描述進一步作如下假設。

假設1 假設異構系統內實時任務集合TG按照服務率從高到低排序,即

ρ1≥ρ2≥…≥ρi…≥ρm

式中:ρi為實時任務ti分配至H的總服務率。根據該假設,調度策略可以在執行最初對所有實時任務按照服務率從高到低順序進行重新排列,以方便之后的調度分配。

在PO-SSAC算法中,執行程序首先按照命題1和假設1為高服務率的實時任務分配高優先級并按照優先級進行排序,之后進入對實時任務集合的循環處理。循環處理是PO-SSAC算法的核心部分,首先判斷候選處理機子集是否為空,若子集非空,說明子集內至少包含1個處理機節點能夠滿足實時任務ti的可用性約束,進而循環計算候選處理機子集中各候選處理機節點的系統綜合開銷Cij,選取子集中系統綜合開銷最少的處理機節點,并將該處理機節點選為任務調度的執行節點。

討論調度的特殊情況,若候選處理機子集為空,說明此時異構系統中所有處理機節點均無法滿足實時任務ti的可用性約束。在該情況下PO-SSAC算法將采取相應的措施盡可能對ti的調度執行可用性進行提升。循環計算ti在異構系統內處理機節點的可用性成本aij,并為ti分配系統內可用性成本最低的處理機節點。另外,如果系統內存在2個或2個以上可用性成本取值相同且最低的處理機節點,則ti將分配至其中平均響應時間相對較短的處理機節點上。

當某候選處理機節點Ns選定以后,PO-SSAC主函數將調用loadBalance()函數進行負載均衡檢測并最終分配實時任務ti至相應的處理機節點處理執行。loadBalance()函數首先估算H內所有處理機節點的負載指標并找到其中負載最輕的處理機節點Nnmin,令該節點負載指標為Lmin。對于所選取的處理機節點Ns,如果Ns沒有超載,系統將分配ti至該節點處理執行;如果Ns超載,系統將分配ti至H內負載最輕的處理機節點Nnmin處理執行,負載閾值為LT。

對于PO-SSAC主函數,TG按照服務率從高到低排序的時間復雜度為O(mlbm),處理機節點選取的時間復雜度為O(n),則對于實時任務集合TG,PO-SSAC主函數在最差執行情況下的時間復雜度為O(mn)。進一步分析loadBalance()函數,循環計算異構系統內所有處理機節點負載指標的時間復雜度為O(n),假設單次任務調度分配中,PO-SSAC主函數和loadBalance()函數中其他步驟執行時間復雜度為O(1),則對于實時任務集合TG,PO-SSAC算法任務分配的時間復雜度為O(m(n+1))。綜合上述分析,PO-SSAC算法在最差執行情況下的整體時間復雜度為O(mlbm)+O(mn)+O(m(n+1))≈O(2mn)。

圖2給出了PO-SSAC調度策略的一個抽象實例,假設異構系統由8個處理機節點(N1～N8)組成,其中各處理機節點可用性取值范圍為0.68～0.97,任務平均響應時間取值范圍為42～204 s,可用性成本取值范圍為0.031～0.297。假設實時任務可用性約束為0.80,則符合該可用性約束的候選處理機集合為N3、N4、N6、N7和N8,各候選處理機的系統綜合開銷取值范圍為2.94～21.42。按照PO-SSAC調度策略,調度器將最終分配實時任務至系統綜合開銷最少的處理機節點N3處理執行。

圖2 PO-SSAC調度策略實例

4 實驗分析

本文面向異構系統設計了帶可用性約束的性能優化調度算法PO-SSAC,并通過隨機實時任務集在異構系統內的調度分配對現有實時任務調度算法SSAC、MinMin、Sufferage以及PO-SSAC進行對比仿真實驗。異構系統選用GridSim仿真工具進行構建,代碼用Java通過eclipse編譯實現,仿真環境為Red Hat Enterprise Linux 7.0操作系統,CPU為Inter Core i7-6700k@4.00 GHz四核,內存為16 GB,硬盤為希捷ST3000DM001-1ER166(3 TB)。

4.1 實驗用例

實驗主要從任務總平均到達率和處理機節點數的變化情況對異構系統內PO-SSAC算法以及對比算法的調度執行情況進行分析。實驗運行200次并記錄實驗結果,去掉其中5次最大和最小結果,取剩余結果均值作為最終實驗結果。實驗參數和取值情況見表1,參數或者參照文獻[5,9]中實驗部分的參數取值,或者取自異構系統的實際評測經驗值。

異構系統處理機節點數為n,實時任務集合TG通過GridSim仿真工具隨機生成,任務平均響應時間Tij為1～500 s內隨機整數。根據對實時任務調度模型的分析可知,任務總平均到達率λ服從泊松分布,任務平均響應時間Tij、處理機節點可用性ξj以及任務可用性約束ai均服從均勻分布,負載閾值LT取固定經驗值。

實驗選取與PO-SSAC算法相近似的另外3個調度算法進行對比,包括SSAC、MinMin[11]以及Sufferage算法[12],上述算法均適用于異構系統中的實時任務調度分配,同時也適用于分布式或同構系統的任務調度情況。

實驗主要評價指標包括異構系統實時任務調度系統可用性、系統總平均響應時間以及系統綜合開銷。

4.2 實驗結果分析

首先分析任務總平均到達率λ變化情況下異構系統實時任務調度的各評價指標。λ取值范圍為0.2～1.0,增量為0.2,處理機節點數n=16。實時任務調度分配實驗結果如圖3所示。

(a)系統可用性

(b)系統平均響應時間

(c)系統綜合性能開銷圖3 任務總平均到達率不同時系統的各項性能實驗結果

由圖3a可以看出,采用可用性約束調度策略的PO-SSAC與SSAC可用性提升明顯,與MinMin算法相比,可用性提升約76.9%,與Sufferage算法相比,可用性提升約76.5%,同時PO-SSAC更優于SSAC,可用性提升約3.4%,原因在于PO-SSAC在實時任務處理機節點選取時考慮了實時任務可用性成本與平均響應時間的折中,為其分配系統綜合開銷最少的處理機節點調度執行,該策略使實時任務調度分配的可用性能夠得到進一步的提升。圖3b、圖3c中實驗結果表明,PO-SSAC在獲取較高系統可用性的同時增加了異構系統內實時任務的調度執行時間,有效降低了系統綜合開銷,與系統綜合開銷最多的Sufferage算法相比,減少近30%,優化了異構系統的性能。

進一步分析處理機節點數n變化時異構系統實時任務調度的各評價指標。n取值為16、32、64、128時,任務總平均到達率λ=1。實時任務調度分配實驗結果如圖4所示。

(a)系統可用性

(b)系統平均響應時間

(c)系統綜合開銷圖4 處理機節點數不同時系統的各項性能實驗結果

與任務到達率變化實驗結果類似,與其他3個算法相比,PO-SSAC系統可用性有所提升,但由于考慮可用性約束,增加了異構系統的實時任務調度執行時間。由圖4c中實驗結果可以看出,與其他3個算法相比,PO-SSAC系統綜合開銷最少。另外,本實驗結果也說明當異構系統規模擴大,即處理機節點數增多時,系統綜合開銷會減少,實時任務調度可用性和系統性能將得到提升。

5 結 論

本文提出了一種異構系統中帶可用性約束的性能優化調度算法,該算法對異構系統內處理機節點、實時任務以及帶可用性約束的實時任務調度進行數學建模,引入系統綜合開銷概念并考慮可用性成本與任務平均響應時間的折中,將實時任務分配給系統綜合開銷最少的處理機節點,以達到系統調度資源合理利用的目的。實驗結果表明,與現有算法相比,PO-SSAC算法提升了異構系統實時任務調度的系統可用性,系統調度性能也得到了進一步優化。

[1] FAN J, LU X W, LIU P H. Integrated scheduling of production and delivery on a single machine with availability constraint [J]. Theoretical Computer Science, 2015, 562: 581-589.

[2] BELMABROUK M, MARRAKCHI M. Optimal parallel scheduling for resolution a triangular system with availability constraints [C]∥Proceedings of the International Conference on Computer Systems and Applications. Piscataway, NJ, USA: IEEE, 2015: 1-7.

[3] SALFNER F, WOLTER K. A Petri net model for service availability in redundant computing systems [C]∥Proceedings of the 2009 Winter Simulation Conference. Piscataway, NJ, USA: IEEE, 2009: 819-826.

[4] TONG Z, LI K L, XIAO Z, et al. A Qos scheduling scheme with availability constraint in distributed systems [C]∥Proceedings of the 13th International Conference on Parallel and Distributed Computing, Applications and Technologies. Piscataway, NJ, USA: IEEE, 2012: 481-486.

[5] QIN X, XIE T. An availability-aware task scheduling for heterogeneous systems [J]. IEEE Transactions on Computers, 2008, 57(2): 188-199.

[6] KHOUDI A, BERRICHI A, YALAOUI F. Heuristics to maximize system availability on parallel machine scheduling problem [C]∥Proceedings of the International Symposium on Programming and Systems. Piscataway, NJ, USA: IEEE, 2015: 1-6.

[7] ZHU M, GUO W, XIAO S L, et al. Availability-driven scheduling for real-time directed acyclic graph applications in optical grids [J]. Journal of Optical Communications and Networking, 2010, 2(7): 469-480.

[8] 李智勇, 陳少淼, 楊波, 等. 異構云環境多目標Memetic優化任務調度方法 [J]. 計算機學報, 2016, 39(2): 377-390. LI Zhiyong, CHEN Shaomiao, YANG Bo, et al. Multi-object memetic algorithm for task scheduling on heterogeneous cloud [J]. Chinese Journal of Computers, 2016, 39(2): 377-390.

[9] XIE T, QIN X. Stochastic scheduling with availability constraints in heterogeneous clusters [C]∥Proceedings of the International Conference on Cluster Computing. Piscataway, NJ, USA: IEEE, 2006: 1-10.

[10]SETHURAMAN J, SQUILLANTE M S. Optimal stochastic scheduling in multiclass parallel queues [J]. ACM Sigmetrics Performance Evaluation Review, 1999, 27(1): 93-102.

[11]TAN M, SIEGEL H J, ANTONIO J K, et al. Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system [J]. IEEE Transactions on Parallel and Distributed Systems, 1997, 8(8): 857-871.

[12]SONG S S, HWANG K, KWOK Y K. Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling [J]. IEEE Transactions on Computers, 2006, 55(6): 703-719.