一種多策略要素的數(shù)據(jù)訪問(wèn)調(diào)度算法

馮 徑 徐 攀 王錦洲 黃 偉

(解放軍理工大學(xué)氣象學(xué)院，南京211101)

我國(guó)的氣象水文數(shù)據(jù)庫(kù)分別部署在中央、流域、省級(jí)等水利部門(mén)，具有分布式特點(diǎn)，通?？沙橄鬄槿?jí)節(jié)點(diǎn).就實(shí)時(shí)水雨情而言，一級(jí)節(jié)點(diǎn)主要存儲(chǔ)國(guó)家級(jí)測(cè)站的數(shù)據(jù)信息，二級(jí)節(jié)點(diǎn)用于存儲(chǔ)流域內(nèi)國(guó)家和地方測(cè)站數(shù)據(jù)信息，三級(jí)節(jié)點(diǎn)僅存儲(chǔ)本區(qū)域內(nèi)的測(cè)站陸地水文數(shù)據(jù)信息.因此，在設(shè)計(jì)大量用戶(hù)并發(fā)的透明數(shù)據(jù)訪問(wèn)服務(wù)時(shí)，會(huì)遇到多個(gè)服務(wù)器擁有相同數(shù)據(jù)或在同一服務(wù)器中訪問(wèn)不同數(shù)據(jù)的情況，此時(shí)不僅需要滿(mǎn)足高優(yōu)先級(jí)任務(wù)，更應(yīng)當(dāng)考慮公平性.在單純考慮優(yōu)先級(jí)的調(diào)度系統(tǒng)中，特別是當(dāng)系統(tǒng)負(fù)荷較高時(shí)，低優(yōu)先級(jí)隊(duì)列的平均等待時(shí)間趨于無(wú)限大，必然造成這部分任務(wù)由于超過(guò)任務(wù)時(shí)限而被拋棄的結(jié)果［1］.因此，在研究數(shù)據(jù)訪問(wèn)調(diào)度算法時(shí)，除了考慮傳統(tǒng)的截止時(shí)間、優(yōu)先級(jí)等任務(wù)調(diào)度約束條件外，還應(yīng)根據(jù)應(yīng)用場(chǎng)景，考慮公平性、數(shù)據(jù)映射代價(jià)、安全性、負(fù)荷均衡等其他策略要素.

本文以我國(guó)的陸地水文分布式數(shù)據(jù)庫(kù)系統(tǒng)為背景，針對(duì)各類(lèi)應(yīng)用對(duì)不同區(qū)域的數(shù)據(jù)共享問(wèn)題，綜合考慮多種策略要素，設(shè)計(jì)了一種多策略要素的調(diào)度算法(multi-policy elementsscheduling，MPES).該算法對(duì)分布式數(shù)據(jù)庫(kù)訪問(wèn)任務(wù)進(jìn)行調(diào)度，對(duì)不同優(yōu)先級(jí)任務(wù)設(shè)置不同的調(diào)度窗口.在保證安全的基礎(chǔ)上，將n個(gè)相互獨(dú)立的任務(wù)分配到m個(gè)可用的資源節(jié)點(diǎn)上，使得總服務(wù)時(shí)間最小且資源得到充分利用.

1 預(yù)備定義

MPES算法由調(diào)度預(yù)處理等待、調(diào)度窗口計(jì)算、安全級(jí)別映射、節(jié)點(diǎn)數(shù)據(jù)映射、節(jié)點(diǎn)分配和非正常狀態(tài)的判斷與處理等6部分組成.在保證安全的基礎(chǔ)上，將n個(gè)相互獨(dú)立的任務(wù)分配到m個(gè)可用的資源節(jié)點(diǎn)上.

定義1任務(wù)集合 J={ω1，ω2，…，ωn}，其中ωi∈J 為一個(gè)多元組，且 ωi=(ci，sei，tyi，pri，di，eti，hi)，ci為任務(wù)分配的節(jié)點(diǎn)，sei為任務(wù)的安全級(jí)別要求，tyi為任務(wù)請(qǐng)求的數(shù)據(jù)內(nèi)容，pri為任務(wù)的優(yōu)先級(jí)，di為任務(wù)截止時(shí)間相對(duì)值，eti為任務(wù)的執(zhí)行時(shí)間，hi為任務(wù)循環(huán)跳數(shù)(初始值為0).其中，sei，tyi，pri，di，eti已知，且 eti={ti1，ti2，…，tim}為多元組，tim為不同任務(wù)在不同節(jié)點(diǎn)上的執(zhí)行時(shí)間.

定義2節(jié)點(diǎn)可以被描述為一個(gè)集合C={c1，c2，…，cm}，其中 m≥2;ci∈C 為一個(gè)多元組，且 ci={pei，sei，tyi，li}，pei，sei，tyi和 li分別為節(jié)點(diǎn)的性能參數(shù)、安全級(jí)別、數(shù)據(jù)內(nèi)容和最大可連接訪問(wèn)任務(wù)數(shù).其中sei和tyi均已知，且tyi為一個(gè)集合.

定義3等待調(diào)度隊(duì)列集合 Qw={q1，q2，q3}，其中q1，q2和q3分別為高優(yōu)先級(jí)隊(duì)列、中等優(yōu)先級(jí)隊(duì)列和普通優(yōu)先級(jí)隊(duì)列，且 q1={ω11，ω12，…，ω1x}，q2={ω21，ω22，…，ω2y}，q3={ω31，ω32，…，ω3z}.

根據(jù)上述定義，設(shè) Q={ω1，ω2，…，ωl}為當(dāng)前需要進(jìn)行調(diào)度的任務(wù)集合，Qe={ω'1，ω'2，…，ω'k}為當(dāng)前正在執(zhí)行的任務(wù)集合.

不失一般性，設(shè)置3個(gè)優(yōu)先級(jí)，即當(dāng)pri=1，2，3時(shí)分別代表高優(yōu)先級(jí)、中等優(yōu)先級(jí)和普通優(yōu)先級(jí).

2 算法設(shè)計(jì)

2.1 等待調(diào)度預(yù)處理

根據(jù)任務(wù)優(yōu)先級(jí)的不同可將等待調(diào)度隊(duì)列分為不同的優(yōu)先級(jí)隊(duì)列.本文設(shè)計(jì)了3種優(yōu)先級(jí)隊(duì)列q1，q2和q3.預(yù)處理的工作主要包含以下內(nèi)容:①對(duì)到來(lái)的任務(wù)根據(jù)優(yōu)先級(jí)不同進(jìn)行隊(duì)列分配，同一優(yōu)先級(jí)的任務(wù)分配給同一隊(duì)列;②在每個(gè)隊(duì)列中，采用最小松弛度優(yōu)先調(diào)度(modified least laxity first，MLLF)策略決定任務(wù)進(jìn)入調(diào)度窗口的先后次序.

MLLF策略以任務(wù)的松弛度Li為任務(wù)的優(yōu)先級(jí)，且 Li=di(t)-t-ei(t)=Di-Ci.其中，Di=di(t)-t為任務(wù)調(diào)度優(yōu)先級(jí)，di(t)為任務(wù)的時(shí)限，t為當(dāng)前時(shí)間;Ci=ei(t)為任務(wù)的運(yùn)行時(shí)間.松弛度Li的值越小，任務(wù)的優(yōu)先級(jí)越高;反之則越低.具有最小Li值的任務(wù)最先執(zhí)行［2］.

設(shè) q1的排序結(jié)果為 ω11，ω12，ω13，ω14，…;q2的排序結(jié)果為 ω21，ω22，ω23，ω24，…;q3的排序結(jié)果為 ω31，ω32，ω33，ω34，….

2.2 調(diào)度窗口計(jì)算

調(diào)度窗口可理解為允許某類(lèi)任務(wù)被分配的時(shí)間，以一個(gè)標(biāo)準(zhǔn)時(shí)間T為單位.等待調(diào)度任務(wù)經(jīng)過(guò)等待調(diào)度預(yù)處理后，進(jìn)入不同的優(yōu)先級(jí)隊(duì)列，然后進(jìn)行內(nèi)部排序.標(biāo)準(zhǔn)時(shí)間值T以q3中首要任務(wù)的期望執(zhí)行時(shí)間為參考.

定義4任務(wù)ωi的期望執(zhí)行時(shí)間Ti為該任務(wù)在所有節(jié)點(diǎn)上的預(yù)期執(zhí)行時(shí)間的平均值，即

在同時(shí)考慮隊(duì)列公平和隊(duì)列優(yōu)先級(jí)的情況下，計(jì)算得調(diào)度窗口W約為6T.根據(jù)優(yōu)先級(jí)對(duì)每個(gè)隊(duì)列分配不同的調(diào)度窗口時(shí)間:普通優(yōu)先級(jí)隊(duì)列的窗口W3≈T;中等優(yōu)先級(jí)隊(duì)列的窗口W2≈2T;高優(yōu)先級(jí)隊(duì)列的窗口W1≈3T.

對(duì)于普通優(yōu)先級(jí)隊(duì)列q3，能夠進(jìn)入調(diào)度窗口的任務(wù)共l3個(gè)，滿(mǎn)足條件，即

對(duì)于中等優(yōu)先級(jí)隊(duì)列q2，進(jìn)入調(diào)度窗口的任務(wù)共 l2個(gè)，滿(mǎn)足條件，即由此可知，前l(fā)2－1個(gè)任務(wù)的期望執(zhí)行時(shí)間之和小于2T，而 l2個(gè)任務(wù)的期望執(zhí)行時(shí)間之和大于等于2T.

對(duì)于高優(yōu)先級(jí)隊(duì)列q1，進(jìn)入調(diào)度窗口的任務(wù)共l1個(gè)，滿(mǎn)足條件即由此可知，前l(fā)1－1個(gè)任務(wù)的期望執(zhí)行時(shí)間之和小于3T，而 l1個(gè)任務(wù)的期望執(zhí)行時(shí)間之和大于等于3T.

圖1為調(diào)度窗口示例，以每個(gè)任務(wù)的長(zhǎng)度代表該任務(wù)的期望執(zhí)行時(shí)間.由圖可知，對(duì)于普通優(yōu)先級(jí)隊(duì)列q3，進(jìn)入調(diào)度窗口的元素為ω31;對(duì)于中等優(yōu)先級(jí)隊(duì)列q2，進(jìn)入調(diào)度窗口的任務(wù)共5個(gè)，分別為 ω21，ω22，ω23，ω24，ω25;對(duì)于高優(yōu)先級(jí)隊(duì)列 q1，進(jìn)入調(diào)度窗口的元素共 6 個(gè)，分別為 ω11，ω12，ω13，ω14，ω15，ω16.

圖1 調(diào)度窗口示例

2.3 安全級(jí)別映射

假設(shè)3種安全級(jí)別:sei=1表示高安全級(jí)別;sei=2表示中等安全級(jí)別;sei=3表示低安全級(jí)別.

安全級(jí)別映射是指對(duì)于調(diào)度隊(duì)列內(nèi)的任務(wù)而言，根據(jù)任務(wù)的安全級(jí)別條件，在全局的資源節(jié)點(diǎn)內(nèi)確定能夠執(zhí)行該任務(wù)的節(jié)點(diǎn)子集.在本算法中，只允許該任務(wù)在安全級(jí)別高于或等于任務(wù)安全級(jí)別的節(jié)點(diǎn)上執(zhí)行.

2.4 節(jié)點(diǎn)數(shù)據(jù)映射

若以三級(jí)節(jié)點(diǎn)的存儲(chǔ)內(nèi)容為一個(gè)單元數(shù)據(jù)，則可將整個(gè)系統(tǒng)中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)內(nèi)容ty表示如下:① 對(duì)于三級(jí)節(jié)點(diǎn)ci而言，數(shù)據(jù)內(nèi)容為si，即tyi={si};② 對(duì)于二級(jí)節(jié)點(diǎn)ck而言，若該節(jié)點(diǎn)包含三級(jí)節(jié)點(diǎn) ch，ci，cj的數(shù)據(jù)，則其數(shù)據(jù)內(nèi)容為 tyk={sh，si，sj};③對(duì)于一級(jí)節(jié)點(diǎn)而言，其數(shù)據(jù)內(nèi)容為系統(tǒng)內(nèi)所有單元數(shù)據(jù)的集合.

數(shù)據(jù)內(nèi)容映射需要在安全級(jí)別映射已經(jīng)確定的節(jié)點(diǎn)子集內(nèi)進(jìn)行，根據(jù)任務(wù)要求訪問(wèn)的內(nèi)容來(lái)對(duì)節(jié)點(diǎn)子集進(jìn)行匹配，查找適合的節(jié)點(diǎn)以完成任務(wù).當(dāng)數(shù)據(jù)內(nèi)容映射的集合為空集時(shí)，處理同2.3節(jié).

2.5 節(jié)點(diǎn)分配

節(jié)點(diǎn)分配要綜合考慮節(jié)點(diǎn)性能和實(shí)時(shí)負(fù)荷.節(jié)點(diǎn)性能表示該節(jié)點(diǎn)執(zhí)行任務(wù)速度的快慢.采用比值法為每一個(gè)節(jié)點(diǎn)確定性能參數(shù)，以避免需要根據(jù)節(jié)點(diǎn)CPU型號(hào)、數(shù)量、內(nèi)存、存儲(chǔ)方式等參數(shù)進(jìn)行建模的復(fù)雜性.

定義5在節(jié)點(diǎn)集合中，令某節(jié)點(diǎn)ch為標(biāo)準(zhǔn)服務(wù)器，其性能參數(shù)peh為1，則節(jié)點(diǎn)cj的性能參數(shù)pej為任務(wù)ωi在節(jié)點(diǎn)ch和cj上執(zhí)行時(shí)間的比值，即pej=eth/etj=tih/tij.pej越大，則性能越好.

節(jié)點(diǎn)的負(fù)荷會(huì)影響動(dòng)態(tài)性能.負(fù)荷越大，則其運(yùn)行時(shí)間越長(zhǎng).衡量節(jié)點(diǎn)的負(fù)荷參數(shù)主要涉及任務(wù)到達(dá)數(shù)、任務(wù)離開(kāi)數(shù)、瞬時(shí)隊(duì)列長(zhǎng)度、平均隊(duì)列長(zhǎng)度、平均響應(yīng)時(shí)間、平均伸展系數(shù)、CPU利用率、未完成的工作量、可用資源情況、交付任務(wù)的要求等［3］.

考慮到本文算法是面向數(shù)據(jù)庫(kù)系統(tǒng)的任務(wù)調(diào)度問(wèn)題，可以將每個(gè)節(jié)點(diǎn)的當(dāng)前數(shù)據(jù)庫(kù)連接數(shù)作為單一負(fù)荷指標(biāo).過(guò)多的數(shù)據(jù)庫(kù)連接會(huì)耗費(fèi)大量的節(jié)點(diǎn)內(nèi)存，占用大量的節(jié)點(diǎn)資源，導(dǎo)致節(jié)點(diǎn)處理速度變慢［4］.故采用數(shù)據(jù)庫(kù)當(dāng)前剩余的任務(wù)連接數(shù)liai(ai為節(jié)點(diǎn)ci上當(dāng)前數(shù)據(jù)庫(kù)連接數(shù))和理論最大連接數(shù)li的比值以及節(jié)點(diǎn)的性能參數(shù)pei來(lái)表示節(jié)點(diǎn)當(dāng)前的實(shí)時(shí)性能 ri，即 ri=pei(li-ai)/li.ri越大，則該節(jié)點(diǎn)當(dāng)前的實(shí)時(shí)性能越好.

“著力解決問(wèn)題最突出、矛盾最集中、群眾要求最緊迫的水利問(wèn)題，增強(qiáng)民生水利保障能力，擴(kuò)大民生水利成果，使水利更好地惠澤民生，造福人民群眾?！彼坎块L(zhǎng)陳雷的話(huà)語(yǔ)擲地有聲，在代表們心中產(chǎn)生強(qiáng)烈共鳴。

2.6 非正常狀態(tài)的判斷和處理

為確保本文算法在執(zhí)行時(shí)能從非正常狀態(tài)中恢復(fù)，或不進(jìn)入非正常狀態(tài)，MPES算法設(shè)置了狀態(tài)判斷與處理.若節(jié)點(diǎn)集合C為空集，則當(dāng)前系統(tǒng)沒(méi)有資源，處于無(wú)可用資源狀態(tài)，即等待狀態(tài).若在設(shè)定的調(diào)度窗口中，僅有一部分任務(wù)進(jìn)入調(diào)度窗口，而這部分任務(wù)正好暫時(shí)沒(méi)有可分配的資源，系統(tǒng)將長(zhǎng)時(shí)間等待節(jié)點(diǎn)資源，此時(shí)系統(tǒng)處于假死狀態(tài).解決方法是重新設(shè)定調(diào)度窗口，允許更多的任務(wù)進(jìn)入調(diào)度隊(duì)列.可通過(guò)任務(wù)屬性元素的循環(huán)跳數(shù)hi是否達(dá)到閾值來(lái)判斷當(dāng)前系統(tǒng)是否為假死狀態(tài)，每當(dāng)調(diào)度系統(tǒng)對(duì)任務(wù)ωi調(diào)度未成功一次，則hi加1.

當(dāng)調(diào)度隊(duì)列中所有任務(wù)的循環(huán)跳數(shù)均大于某一數(shù)值b時(shí)，則認(rèn)為調(diào)度隊(duì)列中所有任務(wù)在經(jīng)過(guò)b次調(diào)度后均未成功，可以判斷系統(tǒng)進(jìn)入了假死狀況.本文中設(shè)定b=5.

確定系統(tǒng)進(jìn)入假死狀況后，需要重新設(shè)定調(diào)度窗口.將調(diào)度隊(duì)列集合Q中的任務(wù)再次進(jìn)行預(yù)處理，根據(jù)優(yōu)先級(jí)進(jìn)行排隊(duì)分別為q'1，q'2，q'3，其任務(wù)數(shù)分別為x，y，z.這3個(gè)隊(duì)列的期望執(zhí)行時(shí)間的最大值Temax可表示為

將q'1，q'2，q'3加入到等待調(diào)度隊(duì)列的隊(duì)首，即q1=q'1+q1，q2=q'2+q2，q3=q'3+q3，Qw=Q+Qw.重新根據(jù)MLLF策略進(jìn)行排序，并對(duì)任務(wù)調(diào)度窗口重新設(shè)定.

如果期望執(zhí)行時(shí)間的最大值Temax為普通優(yōu)先級(jí)隊(duì)列q'3的期望執(zhí)行時(shí)間，即Temax=E(q'3)，則重新設(shè)定的調(diào)度窗口的標(biāo)準(zhǔn)時(shí)間值T=2Temax.根據(jù)2.2節(jié)所述，總調(diào)度窗口大小約為6T≈12Temax.

如果期望執(zhí)行時(shí)間的最大值Temax為中等優(yōu)先級(jí)隊(duì)列q'2的期望執(zhí)行時(shí)間，即Temax=E(q'2)，則重新設(shè)定的調(diào)度窗口的標(biāo)準(zhǔn)時(shí)間值T=Temax，總調(diào)度窗口大小為6T≈6Temax.

如果期望執(zhí)行時(shí)間的最大值Temax為高優(yōu)先級(jí)隊(duì)列q'1的期望執(zhí)行時(shí)間，即Temax=E(q'1)，則重新設(shè)定的調(diào)度窗口的標(biāo)準(zhǔn)時(shí)間值T=2Temax/3，總調(diào)度窗口大小為6T≈4Temax.

3 仿真試驗(yàn)

3.1 試驗(yàn)設(shè)計(jì)

試驗(yàn)在 GridSim工具包［5-7］下使用 Java語(yǔ)言實(shí)現(xiàn)，開(kāi)發(fā)工具為NetBeans IDE 6.8.試驗(yàn)數(shù)據(jù)采用標(biāo)準(zhǔn)性能評(píng)估公司提供的2006年MetaCentrum集群的低負(fù)荷數(shù)據(jù)包和高負(fù)荷數(shù)據(jù)包.前者是MetaCentrum集群環(huán)境下17 d內(nèi)476個(gè)節(jié)點(diǎn)資源和6×103個(gè)任務(wù)資源的集合，模擬了系統(tǒng)到達(dá)時(shí)任務(wù)數(shù)始終未超系統(tǒng)負(fù)荷的情況;后者是Meta-Centrum集群環(huán)境下50 d內(nèi)1 152個(gè)節(jié)點(diǎn)資源和1.2×104個(gè)任務(wù)資源的集合，模擬了大量任務(wù)到達(dá)系統(tǒng)時(shí)系統(tǒng)始終處于超負(fù)荷運(yùn)行的特殊情況.初始化GridSim的模擬環(huán)境和創(chuàng)建各種能力數(shù)據(jù)庫(kù)資源后，得到的試驗(yàn)配置見(jiàn)表1和表2.按照本文算法開(kāi)始調(diào)度，算法實(shí)現(xiàn)代碼略.

表1 各類(lèi)屬性節(jié)點(diǎn)數(shù)

表2 各類(lèi)屬性任務(wù)數(shù)

3.2 結(jié)果分析

選擇總服務(wù)時(shí)間Ts和公平度作為比較指標(biāo).總服務(wù)時(shí)間為所有任務(wù)的請(qǐng)求等待時(shí)間Tw與實(shí)際服務(wù)時(shí)間 Tss之和.不同負(fù)荷情況下，MCT算法［8］、Min-Min 算法［9］和 MPES 算法的等待時(shí)間、執(zhí)行時(shí)間和服務(wù)時(shí)間比較見(jiàn)表3和表4.

表3 低負(fù)荷情況下服務(wù)時(shí)間比較 s

表4 高負(fù)荷情況下服務(wù)時(shí)間比較 s

3.2.1 服務(wù)時(shí)間的比較

要想提高任務(wù)計(jì)算效率，需要降低總服務(wù)時(shí)間，包括請(qǐng)求等待時(shí)間和實(shí)際服務(wù)時(shí)間(即執(zhí)行時(shí)間).表3展示了低負(fù)荷數(shù)據(jù)包情況下3種時(shí)間的比較.由表可知，MPES算法的等待時(shí)間最短，這是因?yàn)镸PES算法對(duì)任務(wù)進(jìn)行排序，減少了運(yùn)行時(shí)等待時(shí)間，且所得效果優(yōu)于Min-Min算法.MCT算法和Min-Min算法都是選擇將任務(wù)調(diào)度給執(zhí)行最快的節(jié)點(diǎn)，而MPES算法則綜合考慮節(jié)點(diǎn)性能和負(fù)荷，因此 MPES算法的執(zhí)行時(shí)間較長(zhǎng).此外，MPES算法的總服務(wù)時(shí)間最長(zhǎng)，較Min-Min算法多130 s，較MCT算法多96 s.MPES算法沒(méi)有將任務(wù)調(diào)度給執(zhí)行最快的節(jié)點(diǎn)，因此其執(zhí)行時(shí)間較長(zhǎng);但與總服務(wù)時(shí)間相比，這是可以忽略不計(jì)的.

表4展示了高負(fù)荷數(shù)據(jù)包情況下3種時(shí)間的比較.由表可知，高負(fù)荷情況下的等待時(shí)間均遠(yuǎn)大于低負(fù)荷情況，且MPES算法的等待時(shí)間仍最短，因?yàn)槠淇紤]了公平性和負(fù)荷均衡，減少了整體等待時(shí)間.MPES算法的總服務(wù)時(shí)間最少，分別比MCT算法和Min-Min算法減少了12.3%和11.4%，這是在減少了大量等待時(shí)間的情況下獲得的.

3.2.2 調(diào)度成功率和公平度比較

高負(fù)荷下，MCT算法、Min-Min算法和MPES算法的調(diào)度成功率分別為94.03%，95.18%和96.23%;低負(fù)荷下則分別為 99.75%，99.75% 和99.80%.可見(jiàn)，MPES算法調(diào)度成功率是最高的，這是因?yàn)樵撍惴ㄊ窃诰C合考慮任務(wù)所需資源的滿(mǎn)意度的基礎(chǔ)上選擇節(jié)點(diǎn)的.

隊(duì)列之間的公平度可表示為［10］

f值越接近0，表明各隊(duì)列之間的資源分配差異越小，公平性越好;反之，則表明各隊(duì)列之間的資源分配差異越大，公平性越差.將表3和表4中的執(zhí)行時(shí)間代入式(1)，可計(jì)算出MCT算法、Min-Min算法和MPES算法的公平度.在高負(fù)荷下，這3種算法的公平度分別為 0.051 90，0.051 89 和0.043 23;在低負(fù)荷下，3種算法的公平度基本相同，約為 0.008 14.

4 結(jié)語(yǔ)

調(diào)度算法的好壞直接影響著一個(gè)任務(wù)的運(yùn)行時(shí)間和所耗資源.一個(gè)好的任務(wù)調(diào)度算法應(yīng)該能夠充分合理地利用網(wǎng)絡(luò)環(huán)境中各種可用資源，并讓這些資源以最高效的方式協(xié)同工作.MPES算法以氣象水文分布式數(shù)據(jù)庫(kù)應(yīng)用環(huán)境為研究背景，綜合優(yōu)先級(jí)、公平性、資源映射代價(jià)、安全性和負(fù)荷均衡等策略要素，在任務(wù)調(diào)度成功率、服務(wù)效率和公平性上較已有的MCT算法和Min-Min算法有顯著提高，特別是在高負(fù)荷情況下其總服務(wù)時(shí)間明顯減少.

References)

［1］朱海，王宇平.多目標(biāo)約束的網(wǎng)格任務(wù)安全調(diào)度模型及算法研究［J］.電子與信息學(xué)報(bào)，2010，32(4):988-992.Zhu Hai，Wang Yuping.Constrained multi-objective grid task security scheduling model and algorithm［J］.Journal of Electronics ＆ Information Technology，2010，32(4):988-992.(in Chinese)

［2］Laplante P A.Real-time system design and analysis［M］.3rd ed.London:Prentice Hall，2004:147-156.

［3］Henderson J，Lemon O，Georgila K.Hybrid reinforcement/supervised learning of dialogue policies from fixed data sets［J］.Computational Linguistics，2008，34(4):487-511.

［4］楊忠明，秦勇，黃翰，等.復(fù)雜網(wǎng)格的演化及其在Internet負(fù)荷平衡中的應(yīng)用研究［J］.計(jì)算機(jī)工程與科學(xué)，2011，33(2):37-41.Yang Zhongming，Qin Yong，Huang Han，et al.Research on the evolution of complex and their application in Internet balancing［J］.Computer Engineering ＆ Science，2011，33(2):37-41.(in Chinese)

［5］Sulistio A，Poduval G，Buyya R，et al.On incorporating differentiated levels of networks service into Grid-Sim［J］.Future Generation Computer Systems，2007，23(4):606-615.

［6］Sulistio A，Cibej U，Venugopal S，et al.A toolkit for modelling and simulating data grids:an extension to GridSim［J］.Concurrency and Computation:Practice and Experience，2008，20(13):1591-1096.

［7］Qureshi K，Rehman A，Manuel P.Enhanced GridSim architecture with load balancing［J］.The Journal of Supercomputing，2011，57(3):265-275.

［8］Fidanova S.Simulated annealing for grid scheduling problem［C］//Proceedings of IEEE John Vincent Atanasoff 2006 International Symposium on Modern Computing.Sofia，Bulgaria，2006:41-45.

［9］Chauhan S S，Joshi R C.A weighted mean time Min-Min Max-Min selective scheduling strategy for independent tasks on grid［C］//Proceedings of the 2nd IEEE International Advance Computing Conference.Patiala，India，2010:4-9.

［10］彭娜，王運(yùn)送，聶思舉，等.我國(guó)民族地區(qū)城鄉(xiāng)收入差異程度的實(shí)證分析［J］.中央民族大學(xué)學(xué)報(bào):自然科學(xué)版，2011，20(4):74-77.Peng Na，Wang Yunsong，Nie Siju，et al.The empirical analysis of urban-rural income gaps in ethnic areas of China［J］.Journal of Central University for Nationalities:Natural Sciences Edition，2011，20(4):74-77.(in Chinese)