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