網(wǎng)格即一個(gè)集成的計(jì)算與資源環(huán)境，能夠充分吸納各種計(jì)算資源，并將它們轉(zhuǎn)化成一種隨處可得、可靠、標(biāo)準(zhǔn)且經(jīng)濟(jì)的計(jì)算能力。所謂計(jì)算資源，除了各種類型的計(jì)算機(jī)，還包括網(wǎng)絡(luò)通信能力、數(shù)據(jù)資料、儀器設(shè)備、甚至人等各種相關(guān)的資源^[1]。網(wǎng)格計(jì)算(Grid Computing)，則是基于網(wǎng)格的問題求解，實(shí)現(xiàn)對(duì)豐富的網(wǎng)絡(luò)資源和繁多的網(wǎng)絡(luò)節(jié)點(diǎn)的管理，讓它們形成一個(gè)有機(jī)整體，從而發(fā)揮最大效益。
　　網(wǎng)格的出現(xiàn)，代表了一種先進(jìn)的技術(shù)和基礎(chǔ)設(shè)施，最終給使用者帶來了與地理位置無關(guān)、與具體的計(jì)算設(shè)施無關(guān)的通用計(jì)算能力。因此，網(wǎng)格堪稱Internet之后網(wǎng)絡(luò)領(lǐng)域又一次重大的科技進(jìn)步。
　　當(dāng)前，高性能任務(wù)調(diào)度技術(shù)、高吞吐率管理技術(shù)、數(shù)據(jù)收集分析、可視化技術(shù)以及安全技術(shù)，是網(wǎng)格的核心服務(wù)技術(shù)。核心服務(wù)是連接網(wǎng)格底層與高層功能的紐帶，是協(xié)調(diào)整個(gè)網(wǎng)格系統(tǒng)有效運(yùn)轉(zhuǎn)的中樞。因此對(duì)核心服務(wù)技術(shù)的研究具有非常重要的意義。
　　本文通過深入研究任務(wù)調(diào)度技術(shù)和算法，在常用任務(wù)調(diào)度算法的基礎(chǔ)上提出另外一種算法，稱為近視眼算法" title="近視眼算法">近視眼算法。與普通算法相比，對(duì)于給定完成期限和資源需求的任務(wù)調(diào)度具有相同的結(jié)果，但在計(jì)算花銷上有明顯提高。
1 任務(wù)調(diào)度
　　通常情況下，網(wǎng)格系統(tǒng)中運(yùn)行著大量的應(yīng)用，這些應(yīng)用共享網(wǎng)格的各種資源。如何才能使并行運(yùn)行、共享資源的應(yīng)用獲得最大效能，這正是任務(wù)調(diào)度需要解決的問題。
　　任務(wù)調(diào)度的目的是在包含大量不同資源的網(wǎng)格環(huán)境" title="網(wǎng)格環(huán)境">網(wǎng)格環(huán)境中，把不同的任務(wù)以最合理的方式分配到相應(yīng)的網(wǎng)格節(jié)點(diǎn)上去完成。為了對(duì)網(wǎng)格計(jì)算環(huán)境中的資源充分利用和優(yōu)化，需要合理、透明地在處理機(jī)之間分配任務(wù)，以使系統(tǒng)的綜合性能最高。任務(wù)調(diào)度應(yīng)用到的幾個(gè)概念具體解釋如下：
　　(1)節(jié)點(diǎn)：表示網(wǎng)格環(huán)境中具有計(jì)算能力的實(shí)體，擁有處理器(Processor)和其他資源(Resource)，這些資源可以是除處理器外的任何資源。
　　(2)任務(wù)：可以被分配到計(jì)算節(jié)點(diǎn)上的實(shí)體，可以是進(jìn)程、子函數(shù)或線程等。
　　(3)任務(wù)集合：所有需要調(diào)度的任務(wù)。
　　(4)任務(wù)調(diào)度算法：任務(wù)調(diào)度的實(shí)現(xiàn)算法，就是找到一種從任務(wù)到節(jié)點(diǎn)的映射。
　　調(diào)度問題一般可分為兩大步驟：第一步是在空間上對(duì)計(jì)算和數(shù)據(jù)進(jìn)行分配，包括選取給定任務(wù)所需要的資源組合，將任務(wù)交給這些資源去執(zhí)行，并分配相關(guān)的數(shù)據(jù)和計(jì)算等；第二步就是在時(shí)間上為計(jì)算和通信進(jìn)行排序，包括在計(jì)算資源上為不同的任務(wù)進(jìn)行排序，同時(shí)為不同任務(wù)之間的通信進(jìn)行排序等。
　　與傳統(tǒng)高性能計(jì)算的調(diào)度策略和技術(shù)相比，網(wǎng)格調(diào)度更加復(fù)雜，任何一個(gè)網(wǎng)格調(diào)度器都無法對(duì)所有的網(wǎng)格資源進(jìn)行管理，而且網(wǎng)格資源是不斷動(dòng)態(tài)變化的。因此，網(wǎng)格的調(diào)度需建立隨時(shí)間變化的性能預(yù)測(cè)模型，充分利用網(wǎng)格的動(dòng)態(tài)信息來表示網(wǎng)格性能的波動(dòng)。由于網(wǎng)格還具有異構(gòu)性和多樣性特征，所以網(wǎng)格的調(diào)度還必須考慮到多種多樣的環(huán)境和條件。
　　目前，網(wǎng)格計(jì)算中的任務(wù)調(diào)度算法主要有局部和全局、最優(yōu)和近優(yōu)、靜態(tài)和動(dòng)態(tài)、自適應(yīng)算法等幾種。
　　由于絕大多數(shù)最優(yōu)調(diào)度問題都是NP完全問題，所以實(shí)際的解決方案往往是進(jìn)行非最優(yōu)調(diào)度，即近優(yōu)方案，相關(guān)算法有解空間枚舉和搜索算法等，但它們具有很大的計(jì)算量。依靠啟發(fā)式方法尋求近優(yōu)解是更加優(yōu)化的方法。所謂啟發(fā)式方法，是指能夠根據(jù)系統(tǒng)反饋動(dòng)態(tài)調(diào)整調(diào)度，向優(yōu)化的方向調(diào)整調(diào)度行為。本文提出的近視眼算法正是結(jié)合啟發(fā)式函數(shù)的近優(yōu)任務(wù)調(diào)度算法。
2 近視眼算法的任務(wù)調(diào)度模型
　　任務(wù)調(diào)度問題的實(shí)質(zhì)是，在一個(gè)有N個(gè)需要調(diào)度的任務(wù)、M個(gè)可用的任務(wù)執(zhí)行單元(網(wǎng)格節(jié)點(diǎn))和i個(gè)數(shù)據(jù)儲(chǔ)存單元構(gòu)成的網(wǎng)格環(huán)境下，把N個(gè)任務(wù)Task＝{T₁，T₂，…，T_n}以合理的方式調(diào)度到M個(gè)節(jié)點(diǎn)Host={h₁，h₂，…，h_m}上去執(zhí)行，目的是通過調(diào)度使執(zhí)行時(shí)間盡可能短。
2.1 術(shù)語
　　(1)可行（feasible）：在調(diào)度中一個(gè)任務(wù)是可行的，表示調(diào)度算法可以滿足此任務(wù)所需的時(shí)間限制和資源需求，即可以調(diào)度。一個(gè)任務(wù)集合是可行的，表示任務(wù)集合中所有任務(wù)都是可行的。
　　(2)部分調(diào)度（partial schedule）：部分調(diào)度是指任務(wù)集合的一個(gè)子集是可行的。
　　(3)強(qiáng)可行（strongly feasible）：稱一個(gè)部分調(diào)度是強(qiáng)可行的，是指從任務(wù)集合的未調(diào)度任務(wù)中任取一個(gè)，對(duì)部分調(diào)度進(jìn)行擴(kuò)展，得到的部分調(diào)度都是可行的。
　　(4)最早有效時(shí)間EAT（Earliest Available Time）：某個(gè)資源可以共享使用或排他使用的最早時(shí)間。
2.2 條件
　　近視眼算法所在的任務(wù)調(diào)度模型通過以下屬性來標(biāo)志一個(gè)任務(wù)：
　　最早到達(dá)時(shí)間：Ta(Task arrival time)
　　最早開始時(shí)間：Test(Task earliest start time)
　　處理時(shí)間：Tp(Task processing time)(處理任務(wù)所需要的時(shí)間間隔)
　　任務(wù)資源需求：Tr(Task resource requirements)
　　任務(wù)完成時(shí)限：Td(Task deadline)
　　調(diào)度過程中，算法通過任務(wù)的最早到達(dá)時(shí)間Ta和網(wǎng)格環(huán)境中的資源信息決定任務(wù)的最早開始時(shí)間Test。對(duì)于一個(gè)可行的調(diào)度來說，每個(gè)任務(wù)都應(yīng)該滿足如下條件：
　　0≤Ta≤Test≤Td-Tp
　　一個(gè)任務(wù)在運(yùn)行時(shí)需要諸如文件、外設(shè)、數(shù)據(jù)結(jié)構(gòu)、變量、通信緩沖等不同資源。對(duì)任意一種資源可以有兩種訪問方式：
　　(1)排他使用，不允許其他任務(wù)和此任務(wù)共同使用同一資源。
　　(2)共享使用，如存在其他任務(wù)需要共享使用同一資源，則允許其共同使用。
　　如果同時(shí)存在任務(wù)TASKi和TASKj，并且排他使用同一資源，就會(huì)發(fā)生資源沖突，這時(shí)某一任務(wù)必須等待，直到資源可用。本調(diào)度模型規(guī)定，任務(wù)是不可剝奪的，即任務(wù)被調(diào)度算法分配到某一節(jié)點(diǎn)后，將一直運(yùn)行到完成為止。
3 近視眼算法描述
3.1 術(shù)語
　　給出算法描述之前，先定義幾個(gè)術(shù)語：
　　(1){剩余任務(wù)}：還沒有被調(diào)度的任務(wù)，可按照任務(wù)的某種屬性順序存放，以方便調(diào)度。
　　(2)N_r：{剩余任務(wù)}中的任務(wù)個(gè)數(shù)。
　　(3){應(yīng)調(diào)度任務(wù)}：{剩余任務(wù)}中的前k個(gè)任務(wù)，又稱為可行性檢測(cè)窗口。
　　(4)k：用于調(diào)度算法的任務(wù)最大數(shù)，也就是擴(kuò)展部分調(diào)度時(shí)，對(duì)剩余任務(wù)隊(duì)列中的k個(gè)任務(wù)進(jìn)行比較，得到具有最小啟發(fā)函數(shù)" title="啟發(fā)函數(shù)">啟發(fā)函數(shù)值的任務(wù)。也可稱為可行性檢測(cè)窗口的大小。
　　(5)N_k：檢測(cè)窗口中實(shí)際的任務(wù)個(gè)數(shù)，大多數(shù)情況下等于k，當(dāng)剩余任務(wù)個(gè)數(shù)小于檢測(cè)窗口時(shí)N_k=N_r，即N_k=min(k，N_r)。
3.2 啟發(fā)函數(shù)
　　近視眼調(diào)度算法使用啟發(fā)函數(shù)Ｈ集成任務(wù)的各種屬性。通過控制啟發(fā)函數(shù)，達(dá)到根據(jù)任務(wù)的不同屬性要求進(jìn)行調(diào)度的目的，從而更加切合實(shí)際。
　　例如，有的調(diào)度要求調(diào)度時(shí)間嚴(yán)格一些，有的調(diào)度要求資源需求重要一些等等。當(dāng)對(duì)未調(diào)度任務(wù)進(jìn)行調(diào)度擴(kuò)展時(shí)，將啟發(fā)函數(shù)應(yīng)用到這些將要進(jìn)行調(diào)度的任務(wù)上，并且選取啟發(fā)函數(shù)值最小的任務(wù)進(jìn)行擴(kuò)展。
　　下面是幾個(gè)常用的啟發(fā)函數(shù)：
　　最小完成時(shí)限優(yōu)先(minimum deadline first：Min_D)：H(T)=Td；
　　最小處理時(shí)間優(yōu)先(minimum processing time first：Min_P)：H(T)=Tp；
　　最小最早開始時(shí)間優(yōu)先(minimum EST first：Min_S)：H(T)=Test；
　　最小松弛優(yōu)先(minimum laxity first：Min_L)：H(T)=Td-(Test+Tp)；
　　Min_D+Min_P：H(T)=Td+W*Tp；
　　Min_D+Min_S：H(T)=Td+W*Test；
　　前四個(gè)是簡(jiǎn)單啟發(fā)函數(shù)，后兩個(gè)是復(fù)合啟發(fā)函數(shù)。其中，Min_D+Min_P綜合考慮完成時(shí)限和處理時(shí)間的因素，Min_D+Min_S 綜合考慮完成時(shí)限和任務(wù)所需要的資源。W是復(fù)合函數(shù)中組合兩個(gè)簡(jiǎn)單啟發(fā)函數(shù)的權(quán)重，通過修改權(quán)重可以根據(jù)任務(wù)的不同需求進(jìn)行調(diào)度。
　　因?yàn)樽钚⊥瓿蓵r(shí)限優(yōu)先和最小處理時(shí)間優(yōu)先沒有考慮到任務(wù)的資源需求，所以近視眼調(diào)度算法中采用Min_D+Min_S作為啟發(fā)函數(shù)。這樣，既考慮了任務(wù)本身的特征，又考慮了任務(wù)的資源需求。
3.3 算法描述
　　對(duì)任務(wù)集合進(jìn)行調(diào)度從而發(fā)現(xiàn)一種可行性調(diào)度的過程類似于一個(gè)查找的過程。任務(wù)集合中的任務(wù)構(gòu)成一棵查找樹，從查找樹頂點(diǎn)開始的子樹對(duì)應(yīng)部分調(diào)度，整棵樹對(duì)應(yīng)完全調(diào)度。要找到一個(gè)可行性調(diào)度，最基本的方法是窮舉遍歷，例如深度優(yōu)先、廣度優(yōu)先等，但計(jì)算復(fù)雜度太高。在很多實(shí)際應(yīng)用中，時(shí)間要求是很嚴(yán)格的，因此需要一種更快的調(diào)度算法。
　　近視眼算法使用如下方法確定一個(gè)任務(wù)集合的可行性調(diào)度。從查找樹的根結(jié)點(diǎn)開始，將根結(jié)點(diǎn)從查找樹中移出擴(kuò)展調(diào)度，依次對(duì)所有任務(wù)進(jìn)行擴(kuò)展，直到發(fā)現(xiàn)完全可行性調(diào)度。
　　在調(diào)度過程中，對(duì)部分調(diào)度進(jìn)行擴(kuò)展前，首先判斷部分調(diào)度是否是強(qiáng)可行的，若使用任務(wù)Ｔ對(duì)部分調(diào)度進(jìn)行擴(kuò)展不是強(qiáng)可行的，說明這種情況下完全調(diào)度不可行。這時(shí)，可以采用回退的方法，返回到上一次任務(wù)調(diào)度，繼而使用另外一個(gè)任務(wù)而不是使用任務(wù)Ｔ對(duì)調(diào)度進(jìn)行擴(kuò)展。
　　第二次被選擇的任務(wù)應(yīng)該是具有次大啟發(fā)函數(shù)值的任務(wù)。雖然算法中允許回退操作，但對(duì)回退次數(shù)應(yīng)該限制，以保證算法的效率?；赝讼拗瓶梢酝ㄟ^設(shè)置最大回退次數(shù)，或者設(shè)置啟發(fā)函數(shù)值限制來實(shí)現(xiàn)。
　　總結(jié)上述思想，得出近視眼算法的工作步驟如下：
　　第一步：按照某一屬性將任務(wù)插入到任務(wù)隊(duì)列中，初始化部分調(diào)度，例如可以按照任務(wù)的完成期限Td升序存放集合中的任務(wù)。
　　第二步：根據(jù)可行性檢測(cè)窗口(任務(wù)隊(duì)列的前k個(gè)任務(wù))，判斷調(diào)度算法當(dāng)前步驟中部分調(diào)度是否是強(qiáng)可行的。
　　第三步：如果是強(qiáng)可行的，則對(duì)檢測(cè)窗口中的任務(wù)應(yīng)用啟發(fā)函數(shù)H(T)=Td+W*Test得到每個(gè)任務(wù)的啟發(fā)函數(shù)值，選取具有最小值的任務(wù)對(duì)部分調(diào)度進(jìn)行擴(kuò)展；否則，將算法回退到上一步驟，選取啟發(fā)函數(shù)值次大的任務(wù)對(duì)部分調(diào)度進(jìn)行擴(kuò)展。
　　第四步：重復(fù)第二步和第三步，直到以下情況出現(xiàn)：
　　(1)發(fā)現(xiàn)完全可行性調(diào)度；
　　(2)到達(dá)最大回退次數(shù)或者到達(dá)啟發(fā)函數(shù)限制值；
　　(3)不能再回退。
4 近視眼調(diào)度算法性能分析
4.1 任務(wù)調(diào)度仿真系統(tǒng)
　　通過對(duì)任務(wù)調(diào)度系統(tǒng)進(jìn)行仿真，實(shí)現(xiàn)啟發(fā)式函數(shù)和近視眼調(diào)度算法，從而對(duì)算法進(jìn)行性能分析。仿真系統(tǒng)主要包括任務(wù)生成器、資源生成器和任務(wù)調(diào)度器三個(gè)部分：
　　(1)任務(wù)生成器：按照用戶輸入的參數(shù)產(chǎn)生任務(wù)集合。
　　(2)資源生成器：生成調(diào)度所需要的資源。
　　(3)任務(wù)調(diào)度器：利用任務(wù)生成器產(chǎn)生的任務(wù)和資源生成器產(chǎn)生的資源進(jìn)行調(diào)度，從而發(fā)現(xiàn)一個(gè)完全可行性調(diào)度。
　　仿真系統(tǒng)的參數(shù)設(shè)置界面如圖1所示。