【摘要】：隨著信息技術(shù)的發(fā)展,互聯(lián)網(wǎng)作為一種服務(wù)越來越深遠(yuǎn)地影響人類的生活。在信息爆炸的背景下,海量信息處理成為計算機(jī)科學(xué)的新挑戰(zhàn)。MapReduce是一個并行分布式數(shù)據(jù)處理編程模型,它的優(yōu)勢在于簡化傳統(tǒng)分布式程序的開發(fā),使得開發(fā)人員只需專注于業(yè)務(wù)邏輯程序的編寫無需考慮分布式的實(shí)現(xiàn)細(xì)節(jié)。Hadoop是MapReduce的開源實(shí)現(xiàn),它是眾多的海量數(shù)據(jù)處理企業(yè)、研究機(jī)構(gòu)提供數(shù)據(jù)處理的基礎(chǔ)平臺。MapReduce調(diào)度算法主要解決的是集群共享,集群資源的利用,作業(yè)的響應(yīng)時間等問題。同時,隨著用戶的實(shí)時性要求的增加關(guān)于MapReduce的實(shí)時調(diào)度的研究也越來越多。MapReduce的實(shí)時調(diào)度的難點(diǎn)在于作業(yè)實(shí)時調(diào)度的模型,同時又要考慮到集群的異構(gòu)性和數(shù)據(jù)的本地性。任務(wù)剩余時間預(yù)測是實(shí)時調(diào)度的重要部分,剩余時間的預(yù)測往往易受到集群的異構(gòu)性特點(diǎn)的影響。 通過研究Hadoop作業(yè)運(yùn)行時機(jī)制,本文提出了一種自適應(yīng)的Reduce任務(wù)調(diào)度算法(Self-Adaptive Reduce Scheduling, SARS)。在現(xiàn)有的MapReduce調(diào)度算法研究中,Reduce任務(wù)的調(diào)度時間過于簡單。Reduce任務(wù)的調(diào)度時間直接影響Reduce的完成時間和集群資源的利用率。SARS調(diào)度算法能夠根據(jù)作業(yè)自身的特性決定Reduce任務(wù)的調(diào)度時間。實(shí)驗(yàn)結(jié)果表明SARS調(diào)度算法減少了Reduce的完成時間和集群作業(yè)的平均響應(yīng)時間,進(jìn)一步提高了集群資源的利用率。 通過研究集群的異構(gòu)性,本文提出了一種基于計算能力的節(jié)點(diǎn)分類算法,用于劃分集群中不同計算能力的節(jié)點(diǎn)。在節(jié)點(diǎn)分類算法的基礎(chǔ)上,提出了一種基于時間約束的實(shí)時調(diào)度算法(MapReduce Task Scheduling for Deadline constraints, MTSD)。MTSD提出了一種任務(wù)剩余時間評估模型,進(jìn)而推導(dǎo)出實(shí)時作業(yè)調(diào)度時資源的需求模型。通過實(shí)驗(yàn)表明MTSD提高了MapReduce作業(yè)的數(shù)據(jù)本地性,并能夠完成實(shí)時調(diào)度需求。
[Abstract]:With the development of information technology, the Internet, as a service, has a profound impact on human life. Under the background of information explosion, mass information processing has become a new challenge in computer science. MapReduce is a parallel distributed data processing programming model, which has the advantage of simplifying the development of traditional distributed programs. Hadoop is an open source implementation of MapReduce, which is a large number of massive data processing enterprises. MapReduce scheduling algorithm mainly solves the problems of cluster sharing, utilization of cluster resources, response time of jobs and so on. At the same time, with the increase of real-time requirements of users, there are more and more researches on real-time scheduling of MapReduce. The difficulty of real-time scheduling of MapReduce lies in the model of real-time job scheduling, and the heterogeneity of cluster and the locality of data must be considered at the same time. Task residual time prediction is an important part of real-time scheduling, and the prediction of remaining time is often affected by the heterogeneity of cluster. This paper proposes an adaptive Reduce task scheduling algorithm (Self-Adaptive Reduce Scheduling, SARS).) by studying the mechanism of Hadoop job runtime. In the existing MapReduce scheduling algorithm research, The scheduling time of Reduce task is too simple. The scheduling time of Reduce task directly affects the completion time of Reduce and the utilization of cluster resources. SARS scheduling algorithm can decide the scheduling time of Reduce task according to the characteristics of the job itself. Experimental results show that the SARS scheduling algorithm reduces the completion time of Reduce and the average response time of cluster jobs, and further improves the utilization of cluster resources. By studying the heterogeneity of cluster, this paper proposes a node classification algorithm based on computing power, which is used to divide the nodes with different computing power in the cluster. On the basis of node classification algorithm, a real-time scheduling algorithm based on time constraint, (MapReduce Task Scheduling for Deadline constraints, MTSD). MTSD, is proposed, and a task residual time evaluation model is proposed. Then the resource requirement model of real-time job scheduling is derived. Experiments show that MTSD improves the data localization of MapReduce jobs and can fulfill the real-time scheduling requirements.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP338.8

【相似文獻(xiàn)】

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

1 李云濤;崔少輝;;一種基于UUTs模型的并行測試任務(wù)調(diào)度算法[J];電子測量技術(shù);2009年07期

2 周建中;王樹宗;石章松;王成飛;;基于遺傳算法的網(wǎng)格任務(wù)調(diào)度方法研究[J];艦船科學(xué)技術(shù);2009年11期

3 鄧定蘭;于炯;譚亞麗;呂良干;;網(wǎng)格工作流的動態(tài)貪心調(diào)度算法[J];計算機(jī)工程;2010年03期

4 鄧萬濤,彭德純,林子禹,陳天雄;BALANCE-II:一個基于Internet環(huán)境的負(fù)載平衡系統(tǒng)[J];小型微型計算機(jī)系統(tǒng);2000年07期

5 黃鯤;王知衍;翁小雄;;樹形異構(gòu)網(wǎng)格的啟發(fā)任務(wù)調(diào)度算法[J];微電子學(xué)與計算機(jī);2007年10期

6 薛桂香;趙政;史偉;孟和;宋建材;;基于OPNET的局部網(wǎng)格任務(wù)調(diào)度平臺設(shè)計[J];計算機(jī)工程;2008年03期

7 于洋;楊愚魯;楊學(xué)剛;賀銘;;分布式網(wǎng)格系統(tǒng)的任務(wù)調(diào)度算法DE Scheduling[J];計算機(jī)工程;2008年14期

8 馬景奕;隋兵;舒萬能;;基于Min-Min遺傳算法的網(wǎng)格任務(wù)調(diào)度方法[J];計算機(jī)工程與應(yīng)用;2008年23期

9 劉先剛;廖述劍;;網(wǎng)格任務(wù)調(diào)度算法的研究[J];機(jī)械工程與自動化;2011年01期

10 王祖析;;基于QoS Guided Min-min任務(wù)調(diào)度算法局部優(yōu)化[J];電腦編程技巧與維護(hù);2011年10期

相關(guān)會議論文 前9條

1 杜琳;石慧;劉曉平;;一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究[A];全國第20屆計算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

2 張佳寶;周斌;吳泉源;;基于Hadoop的并行化命名實(shí)體識別技術(shù)研究與實(shí)現(xiàn)[A];全國計算機(jī)安全學(xué)術(shù)交流會論文集·第二十五卷[C];2010年

3 金松昌;方濱興;楊樹強(qiáng);賈焰;;基于Hadoop的網(wǎng)絡(luò)安全日志分析系統(tǒng)的設(shè)計與實(shí)現(xiàn)[A];全國計算機(jī)安全學(xué)術(shù)交流會論文集·第二十五卷[C];2010年

4 丁輝;張大華;羅志明;;基于Hadoop的海量數(shù)據(jù)處理平臺研究[A];2011電力通信管理暨智能電網(wǎng)通信技術(shù)論壇論文集[C];2011年

5 陳平;王柏;徐六通;吳斌;王艷輝;;電信社群網(wǎng)絡(luò)中介度的網(wǎng)格并行算法及調(diào)度算法[A];2006年全國通信軟件學(xué)術(shù)會議論文集[C];2006年

6 林佳燁;;云計算在電信行業(yè)數(shù)據(jù)分析領(lǐng)域的應(yīng)用[A];廣東通信2010青年論壇優(yōu)秀論文集[C];2010年

7 呂默威;韓世杰;張曉彤;何杰;余美強(qiáng);;一種兼有語音通信功能的實(shí)時定位系統(tǒng)的設(shè)計與實(shí)現(xiàn)[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會議（NCMT2010）、第6屆全國人機(jī)交互學(xué)術(shù)會議（CHCI2010）、第5屆全國普適計算學(xué)術(shù)會議（PCC2010）論文集[C];2010年

8 王益;邢春曉;周立柱;;海量信息系統(tǒng)中服務(wù)器機(jī)群和客戶機(jī)結(jié)合的分布式虛擬現(xiàn)實(shí)計算[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2002年

9 劉懷;黃建新;曹弋;;基于令牌總線的網(wǎng)絡(luò)控制系統(tǒng)中信息的優(yōu)化調(diào)度[A];第二十六屆中國控制會議論文集[C];2007年

相關(guān)重要報紙文章 前3條

1 孫定;云計算、大數(shù)據(jù)與Hadoop[N];計算機(jī)世界;2011年

2 本報記者 馬文方;Hadoop：云中起舞的小象[N];中國計算機(jī)報;2010年

3 本報記者 劉洪宇;Hadoop的中國前途[N];中國計算機(jī)報;2009年

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

1 巴巍;實(shí)時系統(tǒng)動態(tài)優(yōu)先級任務(wù)調(diào)度算法的研究[D];大連理工大學(xué);2010年

2 楊志邦;一類異構(gòu)多處理器片上系統(tǒng)任務(wù)調(diào)度算法研究與應(yīng)用[D];湖南大學(xué);2012年

3 馬丹;任務(wù)間相互依賴的并行作業(yè)調(diào)度算法研究[D];華中科技大學(xué);2007年

4 賀小川;單芯片系統(tǒng)（SoC）中的實(shí)時任務(wù)調(diào)度算法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

5 康俊鋒;云計算環(huán)境下高分辨率遙感影像存儲與高效管理技術(shù)研究[D];浙江大學(xué);2011年

6 史恒亮;云計算任務(wù)調(diào)度研究[D];南京理工大學(xué);2012年

7 霍旭光;基于云計算的大規(guī)模地形數(shù)據(jù)處理方法的研究[D];中國地質(zhì)大學(xué)（北京）;2013年

8 鐘鋒;基于網(wǎng)格的煤炭企業(yè)信息化關(guān)鍵技術(shù)研究[D];中國礦業(yè)大學(xué)（北京）;2009年

9 張宏巍;現(xiàn)代控制局域網(wǎng)技術(shù)在飛行器控制系統(tǒng)中的研究[D];中國科學(xué)院研究生院（長春光學(xué)精密機(jī)械與物理研究所）;2011年

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

1 李坤;云環(huán)境下的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D];吉林大學(xué);2012年

2 張希翔;云計算環(huán)境下任務(wù)調(diào)度算法的研究[D];廣西大學(xué);2012年

3 周俊;基于頭型沖擊器的行人頭部保護(hù)研究及其局限性探討[D];湖南大學(xué);2012年

4 周俊清;基于Hadoop平臺的分布式任務(wù)調(diào)度算法研究[D];湖南大學(xué);2012年

5 封良良;云計算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[D];新疆大學(xué);2013年

6 朱雪慶;基于反饋機(jī)制的實(shí)時彈性任務(wù)調(diào)度算法研究[D];湖南大學(xué);2011年

7 高鳴;云計算環(huán)境下基于時間富余度的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D];云南大學(xué);2011年

8 鄒偉明;云計算環(huán)境下基于MapReduce模型的任務(wù)調(diào)度算法研究[D];新疆大學(xué);2013年

9 鐘英姿;QoS約束下的網(wǎng)格任務(wù)調(diào)度算法研究[D];中南大學(xué);2010年

10 范國昌;網(wǎng)格計算的Online-Min-Min任務(wù)調(diào)度算法研究[D];北京郵電大學(xué);2010年

，

本文編號：2300703