異構(gòu)集群系統(tǒng)中實(shí)時任務(wù)若干調(diào)度問題研究.pdf

1、異構(gòu)集群系統(tǒng)由于其卓越的性能價格比、良好的可擴(kuò)展性和高可用性,逐漸成為當(dāng)今計(jì)算機(jī)體系結(jié)構(gòu)和并行處理研究的熱點(diǎn)和主題。與此同時,實(shí)時應(yīng)用范圍在不斷擴(kuò)大,系統(tǒng)復(fù)雜性不斷提高,集群計(jì)算技術(shù)已經(jīng)成為解決計(jì)算密集型和數(shù)據(jù)密集型實(shí)時應(yīng)用的有效手段。在集群系統(tǒng)的設(shè)計(jì)中,性能是一個關(guān)鍵問題,而調(diào)度又是性能之根本所在。本文致力于研究異構(gòu)集群系統(tǒng)中實(shí)時任務(wù)的若干調(diào)度問題以滿足某些重要實(shí)時應(yīng)用的需求,提高系統(tǒng)的性能。具體地講,本文在如下3個方面進(jìn)行了深入的研

2、究:
　　1.研究了異構(gòu)集群系統(tǒng)中安全關(guān)鍵實(shí)時任務(wù)的調(diào)度問題。在集群系統(tǒng)中,為具有安全需求的實(shí)時應(yīng)用提供安全服務(wù)得到了廣泛的關(guān)注,但將實(shí)用應(yīng)用的安全需求與調(diào)度算法相結(jié)合的研究并不多。本文提出一種2階段的調(diào)度策略TPSS。該策略在任務(wù)的調(diào)度過程中綜合考慮了任務(wù)的安全需求與時間限制。在TPSS的第1階段,提出了一種自適應(yīng)調(diào)度算法DSRF,當(dāng)系統(tǒng)負(fù)載較重時,DSRF算法能在保證系統(tǒng)具有基本安全保證的基礎(chǔ)上,通過降低新到任務(wù)和等待隊(duì)列中任

3、務(wù)的安全級別來提高任務(wù)的調(diào)度成功率。相反,當(dāng)系統(tǒng)負(fù)載較輕時,DSRF算法能在保證系統(tǒng)具有較高調(diào)度成功率的基礎(chǔ)上充分利用任務(wù)在截止期前的空閑時間提高新任務(wù)的安全級別。在TPSS的第2階段,提出一種新的算法FMSL用來為所接收任務(wù)提供公平的安全服務(wù),同時進(jìn)一步提高任務(wù)的整體安全級別。文中通過大量的模擬實(shí)驗(yàn)對TPSS策略與DSRF算法、SAEDF算法和RF算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明,TPSS策略優(yōu)于其它方法,具有很強(qiáng)的靈活性和可靠性。

4、>　　2.研究了異構(gòu)集群系統(tǒng)中實(shí)時任務(wù)的多目標(biāo)調(diào)度問題。目前,很多實(shí)時系統(tǒng)如多媒體數(shù)據(jù)處理系統(tǒng)、信號處理系統(tǒng)等除了需要滿足時間限制外,還需要有多種性能得到保證。但是,大多數(shù)傳統(tǒng)的調(diào)度算法通常只考慮實(shí)時任務(wù)的調(diào)度成功率,而忽略了許多其它方面的需求,本文提出了一種異構(gòu)集群系統(tǒng)中為軟實(shí)時任務(wù)提供多個性能保證的動態(tài)調(diào)度策略MDSS。該策略綜合考慮了任務(wù)的實(shí)時性、服務(wù)質(zhì)量、系統(tǒng)吞吐率、負(fù)載均衡和服務(wù)的公平性。通過將實(shí)時控制器、QoS控制器和均衡控

5、制器整合在調(diào)度器模型中,實(shí)現(xiàn)了多個性能的保證。MDSS包括3個步驟。第1步可以采用任何已有或新提出調(diào)度算法以滿足任務(wù)的時間要求,這極大的提高了系統(tǒng)的靈活性和可擴(kuò)展性。本文在MDSS的第1步采用了Qin等人提出的DASAP算法。另外,本文提出了2種啟發(fā)式算法MQFQ和ITLB,分別用在MDSS策略的第2步和第3步中。MQFQ是一種采用公平策略的算法,使得所有分配在同一個節(jié)點(diǎn)上的任務(wù)具有較高的QoS級別,同時QoS級別的差異較小。此外,本文

6、提出了QoS收益的概念,所采用的QoS級別提升方法有效地避免了局部極值問題。ITLB算法通過最小化節(jié)點(diǎn)完成時間的標(biāo)準(zhǔn)差來達(dá)到系統(tǒng)的負(fù)載均衡,提高系統(tǒng)的吞吐率。文中通過大量的模擬實(shí)驗(yàn)對MDSS、MDSR、DASAP和DALAP算法進(jìn)行了比較,實(shí)驗(yàn)結(jié)果表明MDSS的性能優(yōu)于其它方法,具有很強(qiáng)的適應(yīng)性。
　　3.研究了異構(gòu)集群系統(tǒng)中具有QoS需求的實(shí)時任務(wù)容錯調(diào)度問題。容錯調(diào)度是調(diào)度問題中一個重要的研究內(nèi)容,是提高系統(tǒng)可靠性的有效手段。

7、目前已有很多集群系統(tǒng)中實(shí)時任務(wù)的容錯調(diào)度算法,但是這些算法都沒有考慮到任務(wù)的QoS需求問題。本文提出了一種異構(gòu)集群系統(tǒng)中具有QoS需求的實(shí)時任務(wù)容錯調(diào)度算法FTQ。該算法采用主版本/副版本(Primary/Backup,PB)模型,綜合考慮了任務(wù)的時間限制、任務(wù)的QoS需求、系統(tǒng)的可靠性和系統(tǒng)資源的利用率,能夠自適應(yīng)地根據(jù)系統(tǒng)負(fù)載情況動態(tài)地調(diào)整任務(wù)的QoS級別和副版本的執(zhí)行模式,從而提高了系統(tǒng)的靈活性、可靠性、可調(diào)度性和資源的利用率。本

8、文對系統(tǒng)的可靠性進(jìn)行了定量的分析并將其引入到容錯調(diào)度算法中,提高了系統(tǒng)的可靠性。同時在調(diào)度過程中,盡量提前主版本的開始時間,推遲副版本的開始時間,以使任務(wù)的副版本采用被動執(zhí)行模式或者任務(wù)的主版本和副版本的重疊部分盡量少,以提高了資源的利用率。此外,本文采用了副版本重疊技術(shù),并分析了副版本的最晚開始時間和其約束條件,提高了任務(wù)的調(diào)度成功率。文中通過大量的模擬實(shí)驗(yàn)對FTQ、NOFTQ和DYFARS算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明FTQ算法的性能