基于隨機(jī)模型的動(dòng)態(tài)調(diào)度算法研究_肖逸飛.pdf

《基于隨機(jī)模型的動(dòng)態(tài)調(diào)度算法研究_肖逸飛.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、第卷增刊系統(tǒng)工程理論與實(shí)踐，年月一文章編號(hào)：中圖分類號(hào)：文獻(xiàn)標(biāo)志碼：基于隨機(jī)模型的動(dòng)態(tài)調(diào)度算法研究肖逸飛，彭艦，黎紅友四川大學(xué)計(jì)算機(jī)學(xué)院都，成一摘要針對(duì)多資源云環(huán)境中虛擬機(jī)放置問(wèn)題，提出了種在隨機(jī)模型下綜合利用率較高的動(dòng)態(tài)調(diào)一個(gè)虛擬的中度算法首先，在調(diào)度中心建立央隊(duì)列緩存用戶任務(wù)，然后利用隨機(jī)路由算法對(duì)用戶任務(wù)進(jìn)行服務(wù)器快速選擇，最后在服務(wù)器上建立虛擬等待隊(duì)列并利用算法進(jìn)行虛擬機(jī)配置仿真實(shí)驗(yàn)結(jié)果表明法在保證的情，該算況下現(xiàn)了一，并可，實(shí)定程度上的負(fù)載均衡較大提高系統(tǒng)的綜合利用率關(guān)鍵詞調(diào)度云計(jì)算利用率隨機(jī)負(fù)載均衡；；；引言隨著云計(jì)算的迅速發(fā)展以及虛擬機(jī)（的廣泛使用，將有限的資源按需合理地分配給不

2、同的應(yīng)用變得至關(guān)重要然而，云計(jì)算環(huán)境下內(nèi)在的動(dòng)態(tài)性、復(fù)雜性和異構(gòu)性使得合理利用各種資源成為云服務(wù)提供商的一個(gè)主要挑戰(zhàn)雖然，幾大云計(jì)算系統(tǒng)，包括亞馬遜的谷歌的還有微軟的都已經(jīng)實(shí)現(xiàn)了云計(jì)算的商業(yè)化，但是其多維資源的綜合利用率普遍較低導(dǎo)致浪費(fèi)資源問(wèn)題嚴(yán)重運(yùn)營(yíng)成本此環(huán)境下的放置問(wèn)題亟待解決，產(chǎn)生了較高的，因，多資源為了模擬真實(shí)的云環(huán)境，本文著重研究隨機(jī)模型下的動(dòng)態(tài)調(diào)度算法，以保證任務(wù)的隨機(jī)到達(dá)以及請(qǐng)求的快速響應(yīng)在進(jìn)行任務(wù)調(diào)度時(shí)，本文以服務(wù)質(zhì)量和負(fù)載均衡為前提，通過(guò)改進(jìn)巳有的調(diào)度算法，提高服務(wù)器的綜合利用率，進(jìn)而達(dá)到高效利用多維資源的效果本文的貢獻(xiàn)總結(jié)如下：，模擬真實(shí)的云環(huán)境從實(shí)際的角度出發(fā)，在保證負(fù)載

3、均衡和的前提下，考慮高效地利用多維資源將多維資源的放置問(wèn)題轉(zhuǎn)化成可解決的線性問(wèn)題，并給出相應(yīng)的算法通過(guò)實(shí)驗(yàn)證明了本文提出的算法不僅能夠提供之間的負(fù)載均衡，保證任務(wù)的，而且能夠達(dá)到較高的綜合利用率收稿日期：基金項(xiàng)目：國(guó)家自然科學(xué)基金川省科技支撐計(jì)劃（，四：云計(jì)算：肖逸飛，作者簡(jiǎn)介（男漢四川成都人碩士研究生，研究方向166系統(tǒng)工程理論與實(shí)踐第卷本文第節(jié)介紹相關(guān)工作，并，并對(duì)已有算法的不足作出總結(jié)第節(jié)描述云計(jì)算模型進(jìn)行問(wèn)題陳述第節(jié)闡述算法并與算法進(jìn)行分析比較第節(jié)進(jìn)行仿真實(shí)驗(yàn)與分析第節(jié)總結(jié)全文一，并提出下步工作相關(guān)工作近來(lái)于大規(guī)模數(shù)據(jù)中心的放置問(wèn)題針對(duì)對(duì)，許多研究關(guān)注，和進(jìn)行放置一’，對(duì)單資源放置算法

4、進(jìn)行誠(chéng)然而，沒(méi)有考慮多維資源為了響應(yīng)各種資源需求，，多維背，放置問(wèn)題已在文獻(xiàn)中被研究頻繁使用的技術(shù)包括裝箱問(wèn)題包問(wèn)題閬等等研究了放置問(wèn)題，目標(biāo)是最大化滿足需求的數(shù)量針對(duì)在大規(guī)模企業(yè)數(shù)據(jù)中心中的動(dòng)態(tài)資源配置提出了一個(gè)可擴(kuò)展的應(yīng)用放置算法然而以上研究只是分開考慮了種資源的調(diào)度，并沒(méi)有聯(lián)合起來(lái)考慮考慮負(fù)載均衡，利用多維資源的不平衡度進(jìn)行放置，然而該文獻(xiàn)并沒(méi)有考慮選中的剩余資源是否可容納文獻(xiàn)則考慮多維資源的共同調(diào)度一，并利用內(nèi)存轉(zhuǎn)化技術(shù)消除單資源的瓶頸，一部分用于計(jì)算內(nèi)存壓縮然而在真實(shí)的云環(huán)境下，將資源舍棄，其可操作性和實(shí)時(shí)性不得而知文獻(xiàn)計(jì)對(duì)放置問(wèn)題提出了非搶占式的調(diào)度算法—該算法能夠?qū)θ蝿?wù)負(fù)載變化進(jìn)

5、行相應(yīng)的處理，能夠長(zhǎng)期將平均等待，以達(dá)到平衡各類任務(wù)負(fù)載的目的并且在上表現(xiàn)良好積而任務(wù)可放入數(shù)量越時(shí)延保持在較低水平但是，該算法考慮的是等待隊(duì)列長(zhǎng)度與任務(wù)可放入數(shù)量的乘，高對(duì)資源的需求則越低因此利用率一（放入數(shù)量對(duì)資源的需求資源總數(shù)）不定高而還是有很多不足本由此可見，然，雖然國(guó)內(nèi)外研究成果特別是解決問(wèn)題的方法有許多可供借鑒之處置文在現(xiàn)有研究的基礎(chǔ)上，以可操作性和實(shí)時(shí)性為前提’對(duì)算法進(jìn)行優(yōu)化放’在保證和負(fù)載均衡的條件下，提高系統(tǒng)的綜合利用率，以達(dá)到高效利用多維資源的目的模型資源模型一一個(gè)數(shù)據(jù)中心本文的云系統(tǒng)包括個(gè)調(diào)度中心和（由一…個(gè)聯(lián)網(wǎng)的異構(gòu)組成，單個(gè)用表示，，，個(gè)上資源維數(shù)為中資源…的數(shù)量用表

6、示’’，絲模型“”與文獻(xiàn)類似一一個(gè)，本文設(shè)定云用戶根據(jù)資源請(qǐng)求每個(gè)請(qǐng)求被稱為任務(wù)，任務(wù)均不可一定時(shí)間內(nèi)完成搶占并可在，任務(wù)的類型決定了用戶希望使用的類型和配置任務(wù)的大小決定了請(qǐng)求的時(shí)間每個(gè)任務(wù)都是分時(shí)間片執(zhí)行，時(shí)間片用表示一一種虛擬機(jī)…個(gè)需要本文設(shè)定配置種類有種，，則某資源的數(shù)量為調(diào)度模型當(dāng)任務(wù)由用戶提交給之后，有個(gè)虛擬的中央隊(duì)列，根據(jù)任務(wù)的類型采用一一一丨算法將任務(wù)隨機(jī)分配給在上，每種任務(wù)（即都有個(gè)唯與之對(duì)應(yīng)的虛擬等待隊(duì)歹種任務(wù)組成了一個(gè)等待隊(duì)列集任務(wù)到達(dá)之后首先進(jìn)入相應(yīng)的，根據(jù)本文算法完成創(chuàng)建并執(zhí)行，等待時(shí)間片到達(dá)之后一一定義若給定個(gè)該可以同時(shí)接受，個(gè)，，的數(shù)量為即用一…維的向量表示個(gè)上的

7、可行配置，，則有〉：此時(shí)例如，分，，在本文實(shí)驗(yàn)中，需要種資源類型和存儲(chǔ)空間另表示一一例若個(gè)云系統(tǒng)中只有種，的配置為（若的種類和配置如表所示一個(gè)向，此時(shí)，則利用公式⑴可計(jì)算出所有可行配置集中的每增刊肖逸飛：基于隨機(jī)模型的動(dòng)態(tài)調(diào)度算法研究，等量從左到右依次為標(biāo)準(zhǔn)，密集，密集可放表中畫實(shí)例的數(shù)量°標(biāo)準(zhǔn)占、，定義右向量滿足密集密集則為中的一個(gè)最大配置在例中，，，，，，，均滿，而，，因?yàn)樗?，所包含由（（?/p>