分布式環(huán)境下主副版本任務(wù)可靠調(diào)度方法研究.pdf

1、隨著計算技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，以分布式計算、并行計算為基礎(chǔ)的分布式計算系統(tǒng)所構(gòu)建的數(shù)據(jù)中心和計算中心在工業(yè)、商業(yè)、科技和軍事等領(lǐng)域有著非常廣泛的應(yīng)用。在這些應(yīng)用中將大量的復(fù)雜計算任務(wù)分解成為若干個子任務(wù)并行處理，最后將計算結(jié)果進行有效合并得到最終結(jié)果?？梢钥吹皆谌蝿?wù)的分解和計算過程中，有效的任務(wù)調(diào)度機制是影響分布式計算系統(tǒng)性能和效率的關(guān)鍵因素，而不合理的任務(wù)調(diào)度方法會嚴重影響系統(tǒng)的計算能力，降低并行效率，甚至達不到并行計算應(yīng)具有的效果。

2、因此任務(wù)的調(diào)度問題一直是分布式系統(tǒng)、網(wǎng)格系統(tǒng)、云計算系統(tǒng)的核心內(nèi)容，也是人們一直研究的熱點。
　　但是，隨著分布式系統(tǒng)規(guī)模的不斷增加、計算能力不斷提高的同時，系統(tǒng)的穩(wěn)定性和可靠性已成為影響并行應(yīng)用能否順利執(zhí)行的關(guān)鍵。例如在天河二號、Google數(shù)據(jù)中心等超級計算機或是大規(guī)模集群中，由于復(fù)雜的上層應(yīng)用以及系統(tǒng)超高的功耗導(dǎo)致了系統(tǒng)極容易出現(xiàn)故障，因此設(shè)計一套完整的可靠性保障機制顯得尤為重要，而在系統(tǒng)的調(diào)度階段設(shè)計高可靠的調(diào)度算法是其中

3、重要的手段之一。
　　本文從“保障性能，提高可靠性”這一目標(biāo)出發(fā)，深入研究如何保障分布式計算系統(tǒng)可靠性與計算資源高效利用問題。論文將任務(wù)的類型分為實時周期任務(wù)和非實時任務(wù)兩種任務(wù)類型，通過主副版本調(diào)度技術(shù)，實現(xiàn)了高可靠、高性能的調(diào)度策略。具體工作為：
　?。?）針對分布式計算系統(tǒng)的實時任務(wù)的可靠調(diào)度問題，提出了一種依據(jù)計算節(jié)點和通信鏈路可靠性代價的調(diào)度算法(DRCAMD)。該方法能通過設(shè)置權(quán)值的方法來調(diào)整系統(tǒng)的目標(biāo)權(quán)重函數(shù)，

4、平衡用戶在系統(tǒng)的調(diào)度性能和可靠性的不同需求，另外，針對具有依賴關(guān)系的實時任務(wù)的調(diào)度問題，本文提出了一種不考慮主版本任務(wù)與副版本任務(wù)各種重疊狀態(tài)的可調(diào)度分析方法，實驗結(jié)果表明了在一定的計算節(jié)點和通信鏈路的故障概率條件下，算法的可靠性和性能方面具有一定的優(yōu)勢。
　?。?）針對混合關(guān)鍵任務(wù)可靠性調(diào)度的問題，基于主副版本調(diào)度策略，結(jié)合任務(wù)關(guān)鍵性等級的處理方法，提出了一種二階段可靠調(diào)度算法（MCRSS）及可調(diào)度分析方法。該算法的第一階段主要

5、是對需要調(diào)度的混合關(guān)鍵性任務(wù)按照優(yōu)先級高低進行調(diào)度，調(diào)度過程中，使用副本重疊的方法減少由于副版本任務(wù)的復(fù)制所帶來的系統(tǒng)開銷，第二個階段是對調(diào)度到目標(biāo)處理機上的任務(wù)進行可調(diào)度分析，對于不能滿足可調(diào)度需求的任務(wù)進行升級處理，直到能滿足任務(wù)對截止期的要求。仿真實驗表明了MCRSS算法能有效的處理混合關(guān)鍵任務(wù)中不同關(guān)鍵等級任務(wù)的可靠調(diào)度問題，同時保證了分布式計算系統(tǒng)具有良好的靈活性和性能。
　　（3）針對具有優(yōu)先級依賴關(guān)系的DAG任務(wù)的調(diào)

6、度問題，本文提出了一種基于副版本任務(wù)最早完成時間的調(diào)度算法（EFTBT），該方法通過分析主版本任務(wù)調(diào)度的狀態(tài)以此得到不同情況下副版本任務(wù)調(diào)度的最早為完成時間以及調(diào)度的目標(biāo)處理機的約束，并證明了該約束的合理性，該方法能夠在保障可靠調(diào)度前提下獲得較好的調(diào)度性能，另外，針對科學(xué)工作流應(yīng)用中存在的多個DAG任務(wù)同時調(diào)度的問題，為了解決不公平導(dǎo)致的多個后續(xù)DAG任務(wù)無法調(diào)度問題，提出了基于分層思想的多DAG調(diào)度策略（MDDL），實驗結(jié)果表明上述兩

7、種算法與經(jīng)典算法相比能有效提高調(diào)度的性能。
　?。?）針對大規(guī)模分布式計算系統(tǒng)的異構(gòu)性、動態(tài)性的特點，提出基于節(jié)點和鏈路故障特征分析的具有依賴關(guān)系DAG任務(wù)可靠調(diào)度策略，該策略以副版本任務(wù)最早完成時間算法EFTBT為基礎(chǔ)，給出了更符合實際應(yīng)用需求的通信模型以及副版本執(zhí)行策略，建立了分布式計算系統(tǒng)的故障特點分析方法，在此基礎(chǔ)上提出了基于通信競爭模型的容錯調(diào)度算法（ RAPA），實驗結(jié)果表明與HEFT和EFTBT相比，RAPA算法具有