- 相關(guān)推薦
淺析網(wǎng)格環(huán)境中的任務(wù)調(diào)度算法的問題和策略
每年的5、6月都是大學(xué)畢業(yè)生最為忙碌的日子，畢業(yè)論文往往令大多數(shù)學(xué)生頭痛不已，不單是論文內(nèi)容所涉及到的專業(yè)性知識，連論文格式都需要反復(fù)修改!未免到時候無法顧及過來，所以畢業(yè)生們一開始就要抱著認(rèn)真的態(tài)度去寫畢業(yè)論文。下面是YJBYS為大家整理的信息安全畢業(yè)論文，供大家閱讀參考!
【摘 要】 網(wǎng)格系統(tǒng)由大量異構(gòu)資源組成，具有復(fù)雜、動態(tài)和自治等特點。高效的調(diào)度算法可以充分利用網(wǎng)格系統(tǒng)和處理能力，從而提高應(yīng)用程序的性能。本文提出Segment Qos Min-Min RR任務(wù)調(diào)度算法，平衡了負(fù)載，提高了任務(wù)的完成時間和平均等待時間。
【關(guān)鍵詞】 網(wǎng)格;調(diào)度算法;Qos;平衡負(fù)載
1 引言
網(wǎng)格是以資源共享為目的，利用互聯(lián)網(wǎng)將分散與不同地域的計算機組織起來，成為一個虛擬的“超級計算機” 。每臺參與的計算機就是一個“節(jié)點”，成千上萬的節(jié)點組合起來，成為一張“網(wǎng)格”。從而能夠充分地利用網(wǎng)絡(luò)中的空閑計算能力，實現(xiàn)計算資源、存儲資源、數(shù)據(jù)資源、信息資源、知識資源、專家資源等全面的共享。
隨著Internet的發(fā)展，網(wǎng)格計算技術(shù)逐漸成為新的研究領(lǐng)域。網(wǎng)格系統(tǒng)由大量異構(gòu)資源組成，具有復(fù)雜、動態(tài)和自治等特點。高效的調(diào)度算法可以充分利用網(wǎng)格系統(tǒng)和處理能力，從而提高應(yīng)用程序的性能。為了實現(xiàn)網(wǎng)格資源的優(yōu)化配置，并為網(wǎng)格用戶提供較為滿意的服務(wù)質(zhì)量，任務(wù)調(diào)度技術(shù)一直以來成為人們研究的熱點。
文獻[1]對當(dāng)前現(xiàn)有的網(wǎng)格任務(wù)調(diào)度算法進行了深入而詳細(xì)的討論。文獻[2]提出了一種基于任務(wù)池模型的分級調(diào)度方法，保持了系統(tǒng)資源之間的共享關(guān)系和高度可控性。文獻[3]提出基于Min一Min算法的最小完成時間偏差調(diào)度算法(Dev_Min一Min)，解決了任務(wù)調(diào)度的負(fù)載均衡和吞吐率高的問題。文獻[4]提出了MD一sufferage算法，縮短調(diào)度跨度的同時保證較小的任務(wù)等待時間。文獻[5]提出了同時考慮任務(wù)帶寬要求和負(fù)載均衡要求的改進算法，設(shè)計了一種有依賴關(guān)系的任務(wù)調(diào)度算法。本文提出Segment Qos Min-Min RR任務(wù)調(diào)度算法，平衡了負(fù)載，提高了任務(wù)的完成時間和平均等待時間，達(dá)到算法簡單并且效率較高的要求。
2 RR算法
RR算法是一種動態(tài)調(diào)度算法。首先將網(wǎng)格任務(wù)以任意的順序被提交到可用的處理單元(PE)上，直到所有的網(wǎng)格任務(wù)都提交完。然后把未執(zhí)行完的任務(wù)連接成一個環(huán)，一旦此時有執(zhí)行完的任務(wù)，立即從環(huán)中把一個還沒有執(zhí)行完的網(wǎng)格任務(wù)調(diào)度在此可用的處理單元上，即此時有多個處理單元同時在運行同一個網(wǎng)格任務(wù)。只要其中一個處理單元上的網(wǎng)格任務(wù)執(zhí)行完，立即殺死所有的任務(wù)。重復(fù)上述過程，直到所有的任務(wù)執(zhí)行完。如果此時動態(tài)有新的任務(wù)加入，就立即開始執(zhí)行。
設(shè)T是一個大小為L的n個任務(wù)的集合，m為一個計算網(wǎng)格上處理器的數(shù)目，定義T的調(diào)度如下：
T的一個在具有m個處理器的網(wǎng)格上的調(diào)度S是一個三元組的集合，它們滿足R1和R2規(guī)則，v∈T，1≤p≤m，t是任務(wù)v的起始時間，∈S，意味著處理器p在時間間隔t～t+d執(zhí)行任務(wù)v，d是通過p的處理能力和v的L計算出來的，所以稱t+d為任務(wù)v的完成時間。
R1：對每一個v∈T，至少有一個∈S。
R2：不存在這樣的兩個三元組，∈S; t≤t'≤t+d，t+d為任務(wù)v的完成時間。上述功能可以描述如下：
R1保證每一個任務(wù)v至少執(zhí)行一次，R2是說每一個處理器在任何一個時刻最多只能執(zhí)行一個任務(wù)，∈S稱為一個任務(wù)實體。
用下列公式來計算處理器的代價：
RR算法確定可以提高資源的利用率，但同時也造成了資源的浪費，另外，同一時刻有多個處理單元在運行同一個任務(wù)也是一種浪費。
改進的RR算法：就是所有的任務(wù)對處理單元都是共享的，只要有到來的任務(wù)想讓它立即執(zhí)行就可以。根據(jù)任務(wù)分配的處理速度(MIPS)，定義了最大處理速度(MaxMIPS)、最小處理速度(MinMIPS)和最大任務(wù)數(shù)(Maxcount)，所有的任務(wù)可以同時執(zhí)行，所以任務(wù)的狀態(tài)只有停止和運行，沒有等待狀態(tài)。此改進和算法大大提高了任務(wù)的完成時間，提高了系統(tǒng)的性能。
3 Min-Min算法
在Min-Min算法中，首先分別計算每個任務(wù)在所有機器上的最小執(zhí)行時間，執(zhí)行時間最短的那個任務(wù)被選出來并被分配到相應(yīng)的機器上，然后把這個最近被映射的任務(wù)從集合中刪除，重復(fù)執(zhí)行這個過程直到所有的任務(wù)都被映射。文獻[3]研究表明，在不同的ETC矩陣下，Min一Min比OLB、MET、MCT、Max一min等算法均有更好的調(diào)度性能。但還存在局限性：(1)潛在的負(fù)載不均衡，使得資源利用率低;(2)沒有考濾網(wǎng)格任務(wù)的服務(wù)要求。
對于一個由n個元任務(wù)構(gòu)成的集合T，以及m個主機集合M，Min一Min算法的執(zhí)行過程如下：
(l)對主機的就緒時間向量R進行初始化，使得對于任意Mj∈M有R(j)=0，然后根據(jù)預(yù)測執(zhí)行時間矩陣ETC計算出每個任務(wù)Ti在每個主機Mj上的預(yù)測完成時間，根據(jù)預(yù)測完成時間定義，有CT(i，j)=ETC(i，j)+R(j);
(2)當(dāng)任務(wù)集合T不為空時，反復(fù)執(zhí)行以下操作直至任務(wù)集合為空：
a.對集合中的每個任務(wù)Ti(i=1，2，…，n)，計算它在所有主機上的最小預(yù)測完成時間，若它在主機Mj上的預(yù)測完成時間最小，記minCT(i)=CT(i，j)，并記錄minCT(i)所對應(yīng)的主機編號host_minCT(i)=j;
b.找出minCT矩陣中的最小值，即找出具有最小的最小完成時間的任務(wù)，并將它分配給對應(yīng)的主機執(zhí)行。例如，若任務(wù)Ta對應(yīng)的minCT(a)最小，則將編號為host_minCT(a)的主機分配給任務(wù)Ta;
c.從任務(wù)集合T中刪除任務(wù)Ta，更新主機Mk(k=host_minCT(a))的就緒時間R(k)=minCT(a)，并更新預(yù)測完成時間矩陣CT。
4 QoS Guided Min-Min算法
這種算法是讓高服務(wù)質(zhì)量的任務(wù)先執(zhí)行，低服務(wù)質(zhì)量的后執(zhí)行，并且不讓高的服務(wù)質(zhì)量的任務(wù)長期處于等待狀態(tài)，從而減少了等待時間。
5 Segmented Min-Min算法
每一個任務(wù)在每一臺機器上都有一個期望時間ETC(Expected Time to Comput)，如果這里有t個任務(wù)和m臺機器，就獲得一個t X m的ETC矩陣，ETC(i，j)表示任務(wù)i在機器j上的執(zhí)行時間。
Segmented Min-Min算法根據(jù)ETC來對這些任務(wù)進行排序。根據(jù)平均ETC(keyi=ETC(i，j)/m、最小ETC(keyi=ETC(i，j))或最大ETC(keyi=ETC(i，j))來把這些任務(wù)按序排成鏈表。然后這些鏈表中的每一個任務(wù)分成同樣大小的片，并且大任務(wù)的所有片先調(diào)度。每一個任務(wù)中的片均采用Min-Min算法來調(diào)度。
6 Segment Qos Min-Min RR算法
這種算法是在改進的RR算法的基礎(chǔ)上，一是先加入Min-Min算法的思想，讓完成時間最短的任務(wù)先執(zhí)行，讓盡可能多的任務(wù)找到合適的機器來執(zhí)行;二是加入Qos Guided Min-Min算法的思想，對任務(wù)和資源分別設(shè)定服務(wù)質(zhì)量級別，有某個服務(wù)質(zhì)量級別的任務(wù)只能在同等級別或高于此級別的任務(wù)和資源之間達(dá)到最合理的匹配;三是利用Segmented Min-Min算法的思想，讓大的任務(wù)先執(zhí)行并且考慮到任務(wù)的分解，這樣不但平衡了負(fù)載，也同時在任務(wù)的完成時間和平均等待時間上得到了提高。
以上算法得到了幾種實現(xiàn)。
(1)實現(xiàn)RR算法和改進和RR算法(RR1)。由于原始的任務(wù)提交是任意順序的，因此在這里采用先來先服務(wù)的方式，即先到達(dá)的任務(wù)先被提交，后來的只能等待前面的都提交了才能被調(diào)度。
(2)實現(xiàn)Min-Min算法。由于要讓最小完成時間的任務(wù)先提交，因此就要有一個衡量標(biāo)準(zhǔn)，即評價任務(wù)的完成時間。在這里只考慮任務(wù)的大小，而不考慮其他因素的影響，那任務(wù)越小，完成時間越短，也就意味著要先調(diào)度小的任務(wù)。
(3)實現(xiàn)Qos Min-Min算法。為了定義任務(wù)和資源的服務(wù)質(zhì)量級別，這里增加了一個參數(shù)Qos。
(4)實現(xiàn)Segment Qos Min-Min RR算法。為了實現(xiàn)任務(wù)的分解，可以編寫一個任務(wù)分解函數(shù)segmentgridlet()，把任務(wù)分成幾個子任務(wù)片來調(diào)度。
7 實驗仿真
常用的模擬器有Bricks、MicroGrid、SimGrid、GridSim、ChicSim、EDGSim等，其中重點SimGrid。表1中的數(shù)據(jù)就是用SimGrid模擬器仿真的。表1中記錄了在任務(wù)數(shù)分別取200、300、400、500時，不同算法的任務(wù)最終完成時間。
8 結(jié)束語
網(wǎng)格環(huán)境里如何有效地管理資源和進行任務(wù)調(diào)度是影響網(wǎng)格計算是否成功的重要因素之一。由于網(wǎng)格體系結(jié)構(gòu)以及拓?fù)浣Y(jié)構(gòu)比較復(fù)雜，因此在網(wǎng)格調(diào)度研究領(lǐng)域，很多調(diào)度算法的研究往往是側(cè)重某一方，以使其在這方面的性能有所提高，如Segment Min-Min調(diào)度算法側(cè)重于各個主機之間的負(fù)載的均衡，Qos Guided Min-Min啟發(fā)式調(diào)度算法側(cè)重于鏈路帶寬對任務(wù)調(diào)度的影響，而Segment Qos Min-Min RR不僅考慮到了服務(wù)質(zhì)量，而且也考慮到了負(fù)載平衡和動態(tài)性，并且適用對任務(wù)數(shù)量大的任務(wù)進行調(diào)度。網(wǎng)格計算對信息化進程具有相當(dāng)重要的作用，憑借其固有的資源共享和協(xié)同工作能力，網(wǎng)格不僅可以實現(xiàn)計算資源的最大化共享和應(yīng)用，避免資源浪費，更能夠降低應(yīng)用人才的門檻、應(yīng)用開發(fā)難度和應(yīng)用運行成本，促使信息化實現(xiàn)本質(zhì)上的飛躍。
【淺析網(wǎng)格環(huán)境中的任務(wù)調(diào)度算法的問題和策略】相關(guān)文章：
面試中回答問題的策略和技巧10-12
淺析電力企業(yè)在檔案管理中存在的問題及其應(yīng)對策略10-26
淺析當(dāng)前企業(yè)管理面臨的問題及創(chuàng)新策略10-26
淺析消防通訊在火場上應(yīng)用遇到的問題及應(yīng)對策略10-26
淺析企業(yè)物流管理的問題和對策10-26
淺析企業(yè)并購中的整合問題論文范文10-08
淺析高職院校人事檔案管理問題及策略論文10-10