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