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

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

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

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

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

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

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

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

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