本文選題：并行分布式系統(tǒng)　切入點：任務(wù)調(diào)度　出處：《湖南大學(xué)》2013年博士論文

【摘要】：隨著社會經(jīng)濟與信息技術(shù)的飛速發(fā)展,以網(wǎng)絡(luò)計算和并行計算為基礎(chǔ)的分布式計算已成為IT技術(shù)的重要發(fā)展方向,特別是異構(gòu)并行分布式系統(tǒng)因其低成本高性能而受到企業(yè)界和學(xué)術(shù)界的廣泛關(guān)注。但系統(tǒng)規(guī)模持續(xù)擴大的同時,系統(tǒng)平均無故障時間卻越來越低,任務(wù)執(zhí)行行為可靠性已成為保證并行應(yīng)用成功的關(guān)鍵。其次,分布式系統(tǒng)為實現(xiàn)信息保密性、數(shù)據(jù)完整性和邊界安全保護而面臨大量安全威脅,這些威脅主要源于網(wǎng)絡(luò)環(huán)境下資源與用戶行為的不可控性和不確定性。另一方面,并行應(yīng)用實踐表明任務(wù)實際執(zhí)行時間往往受輸入數(shù)據(jù)、系統(tǒng)環(huán)境和任務(wù)本身If分支的影響而具有隨機性。面對由可靠性、安全性、任務(wù)計算量隨機性等導(dǎo)致的分布式系統(tǒng)可信性,提出了考慮可信性的任務(wù)調(diào)度理論與方法,以期對對提高分布式系統(tǒng)應(yīng)用性能具有重要意義的資源管理展開深入研究與探索,力圖解決其中的部分關(guān)鍵理論與技術(shù)問題。 本文首先建立由任務(wù)DAG模型構(gòu)建器、任務(wù)計算量評估、任務(wù)調(diào)度器、任務(wù)分配、信任管理、信任值計算、可靠性分析、安全開銷計算、任務(wù)可信評估等模塊構(gòu)成的可信調(diào)度體系結(jié)構(gòu)。針對異構(gòu)計算系統(tǒng)任務(wù)在不同處理機上執(zhí)行時其計算成本不同的特點,克服以任務(wù)執(zhí)行平均值、中間值、最好值或最壞值等方法給任務(wù)調(diào)度帶來的困惑,提出異構(gòu)計算系統(tǒng)計算能力異構(gòu)因子α,并依此實現(xiàn)任務(wù)優(yōu)先級計算和處理機選擇。在此基礎(chǔ)上,提出基于任務(wù)復(fù)制的表調(diào)度算法(HEFD)。模擬實驗結(jié)果表明任務(wù)調(diào)度算法HEFD優(yōu)于HEFT、HLD和HCPFD算法。 其次,針對大規(guī)模分布式計算系統(tǒng)的異構(gòu)性、動態(tài)性和廣域性等特點,提出可靠性驅(qū)動的層次調(diào)度體系。分析任務(wù)在處理機上執(zhí)行的可靠性、數(shù)據(jù)在通信網(wǎng)絡(luò)上通信的可靠性及相互關(guān)系,建立應(yīng)用程序任務(wù)執(zhí)行行為可靠性模型。在此基礎(chǔ)上提出可靠性驅(qū)動的分層任務(wù)調(diào)度算法(HRDS)。其中,全局任務(wù)調(diào)度器負責(zé)把應(yīng)用程序分配給虛擬節(jié)點,局部調(diào)度器則在虛擬節(jié)點內(nèi)實現(xiàn)基于DAG模型的任務(wù)調(diào)度與分配。實驗結(jié)果表明相對于經(jīng)典調(diào)度算法MCMS和HEFT,HRDS具有較好的性能。 針對分布式計算系統(tǒng)面臨的安全威脅,受經(jīng)濟學(xué)品牌形象實踐與心理學(xué)理論啟發(fā),在研究分布式信任表現(xiàn)形式與特點基礎(chǔ)上提出基于博弈論微分對策技術(shù)的信任值動態(tài)量化計算方法。依據(jù)用戶任務(wù)安全需求和分布式系統(tǒng)提供的安全信任保障,提出任務(wù)執(zhí)行行為安全性開銷計算方法和安全性風(fēng)險評估技術(shù)。最后,提出考慮任務(wù)執(zhí)行行為安全開銷的調(diào)度模型和調(diào)度算法SDS。實驗結(jié)果表明SDS算法不僅能有效提高系統(tǒng)安全性,還具有較好的調(diào)度性能。 經(jīng)典任務(wù)調(diào)度算法一般假定任務(wù)計算量通過軟件工程配置技術(shù)或預(yù)測技術(shù)獲得,且是確定不變值。而并行應(yīng)用計算實踐卻表明任務(wù)計算量具有隨機性,這種不精確性將明顯影響調(diào)度算法性能。因而針對此問題,本文首先證明基于DAG模型隨機任務(wù)調(diào)度長度的下限是以任務(wù)期望構(gòu)成的確定型任務(wù)調(diào)度長度。然后,研究任務(wù)計算量服從正態(tài)分布的應(yīng)用程序,利用Clark方程實現(xiàn)并行任務(wù)完成時間期望與方差的計算,在此基礎(chǔ)上提出隨機sb_level近似計算算法。受確定型表調(diào)度算法DLS啟發(fā),提出針對隨機任務(wù)調(diào)度問題的隨機動態(tài)級調(diào)度算法(SDLS)。實驗結(jié)果表明隨機動態(tài)級調(diào)度算法具有較好的調(diào)度性能。
[Abstract]:With the rapid development of social economy and information technology , distributed computing based on network computing and parallel computing has become the important development direction of IT technology , especially heterogeneous parallel distributed system , which is the key to guarantee the success of concurrent application .

This paper first establishes a trusted scheduling architecture consisting of task DAG model builder , task computation quantity evaluation , task scheduler , task assignment , trust management , trust value calculation , reliability analysis , security cost calculation , task confidence assessment , etc .

Secondly , based on the characteristics of heterogeneous , dynamic and wide - domain characteristics of large - scale distributed computing systems , a hierarchical scheduling system of reliability driven is proposed . The reliability and mutual relation of communication between tasks on the communication network are analyzed , and the reliability model of the application task execution behavior is established . The task scheduling and allocation based on DAG model are realized in the virtual nodes . The results show that the performance of the distributed computing system is better than the classical scheduling algorithm MCMS and HEFT .

In view of the security threats faced by distributed computing systems , inspired by economics brand image practice and psychology theory , a dynamic quantitative method based on game theory differential game technique is proposed based on the research of distributed trust expression and characteristics . Finally , a scheduling model and a scheduling algorithm SDS are presented . The results show that the SDS algorithm not only can effectively improve the system security , but also has better scheduling performance .

The classical task scheduling algorithm generally assumes that the task computation amount is obtained by software engineering configuration technology or prediction technology , and is a fixed value .

【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP338.8

【參考文獻】

相關(guān)期刊論文 前10條

1 王 X,喬 穎,王宏安,方 亭,鄒 冰,戴國忠;實時異構(gòu)系統(tǒng)的動態(tài)調(diào)度算法研究[J];計算機研究與發(fā)展;2002年06期

2 王意潔,肖儂,任浩,盧錫城;數(shù)據(jù)網(wǎng)格及其關(guān)鍵技術(shù)研究[J];計算機研究與發(fā)展;2002年08期

3 金海,陳剛,趙美平;容錯計算網(wǎng)格作業(yè)調(diào)度模型的研究[J];計算機研究與發(fā)展;2004年08期

4 劉東;張春元;李瑞;黃影;李毅;;軟件容錯模型中的容錯實時調(diào)度算法[J];計算機研究與發(fā)展;2007年09期

5 姜建錦;楊廣文;;數(shù)據(jù)網(wǎng)格中請求呈現(xiàn)分組特性的副本管理策略研究[J];計算機研究與發(fā)展;2009年02期

6 丁萬夫;郭銳鋒;秦承剛;郭鳳釗;;硬實時系統(tǒng)中基于軟件容錯模型的容錯調(diào)度算法[J];計算機研究與發(fā)展;2011年04期

7 秦嘯,龐麗萍,韓宗芬,李勝利;分布式實時系統(tǒng)的容錯調(diào)度算法[J];計算機學(xué)報;2000年10期

8 秦嘯,韓宗芬,龐麗萍;基于異構(gòu)分布式系統(tǒng)的實時容錯調(diào)度算法[J];計算機學(xué)報;2002年01期

9 王濟勇,趙海,林濤,王小英,王金東,韓光潔;定時器驅(qū)動的RM調(diào)度機制建模及其性能優(yōu)化[J];計算機學(xué)報;2005年02期

10 林闖;汪洋;李泉林;;網(wǎng)絡(luò)安全的隨機模型方法與評價技術(shù)[J];計算機學(xué)報;2005年12期

相關(guān)博士學(xué)位論文 前2條

1 田澤安;液態(tài)金屬銀凝固過程及微觀結(jié)構(gòu)演變特征的模擬研究[D];湖南大學(xué);2009年

2 盧宇彤;面向高效能計算的大規(guī)模資源管理技術(shù)研究與實現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2009年

，

本文編號：1706192