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