基於反饋機制的網格任務調度方法
2023-06-03 11:40:01 1
專利名稱：基於反饋機制的網格任務調度方法
技術領域：
本發明屬於計算機系統結構領域的分布式計算技術，具體涉及一種基於反饋機制的網格任務調度方法(Feedback Based Grid Scheduling，FBGS)。
背景技術：
網格的根本目標是協調資源的共享。在網格環境中存在眾多資源，這些資源的特性及資源所處的環境各不相同。如何從紛繁複雜的資源中，選擇合適的資源供任務執行是網格計算著力解決的問題之一。該問題也就是所謂的任務調度問題。任務調度的目的是在包含大量不同資源的網格環境中，考慮各網格節點的狀態、網絡通信性能等參數，把不同的任務以合理的方式分配到相應的網格結點上去完成。但由於網格環境的特性，使得網格環境下的任務調度具有不同於傳統調度的特徵。首先，在網格環境中資源節點具有相當大的自治性，各節點自行決定本地的調度策略。網格平臺既不能象傳統調度一樣對資源進行完全控制，如暫停其上正在運行的任務，也不能對其調度策略進行規定。其次，網格各資源的性能及負載等狀態是動態變化的，網格平臺很難準確了解網格資源的狀態。第三，同類型的網格資源可能存在多個，這就使得網格環境下可以有多種選擇。最後，網格資源分布在網絡上，網絡通信的延遲會對任務調度的性能造成影響。特別是隨著網格資源互聯互通的發展，網格資源都以服務的形式表現，出現了基於服務的網格標準，這進一步增加了網格任務調度的延遲。基於此分析，網格環境下的任務調度同傳統環境下的任務調度相比有著多方面不同，網格環境下的任務調度是一個非常困難的問題。
目前，圍繞著網格中的任務調度問題，國內外已經做了大量的研究工作，先後提出了各種調度算法。這些算法按調度策略可以分為在線模式和批模式兩種。在線模式是任務一到來就加以映射，而批模式則是把任務收集起來等映射事件到來後才對這些任務進行集中映射。相對而言，批模式得到了大量的資源信息，從而可以做出更合理的任務映射策略。但批模式算法需要花費大量時間計算任務調度表，算法缺少靈活性；任何變化，如任務添加、刪除或任務特徵改變等，都需要重新計算調度表。而且批模式算法每隔一定周期進行一次調度，因此越早到達的任務，等待時間越長，從而使得任務的響應時間過長。在線調度算法的環境適應性好，在多種環境下操作性能良好，算法靈活，因此在線模式更適合於網格環境。許多網格中間件，如ChinaGrid支撐平臺CGSP、VEGA和CROWN，均採用的是在線調度模式。但目前的在線調度算法在如下幾個方面未作有效考慮首先，網格環境下資源的性能與可用性均處於變化之中。目前的網格調度系統需要訪問信息服務獲取資源的信息。但是信息服務中的服務信息更新周期長，而且訪問信息服務會產生延遲。如果網格調度器單純根據信息服務的信息進行調度，可能導致某些服務負載過大，而另外一些服務利用率不高。之所以存在這些問題，主要是由於網格調度器沒有有效地根據資源節點的狀態信息，而是根據信息服務中的非實時服務信息來進行任務調度。其次，目前網格調度系統通常假設知道或能夠獲取網格上所有節點的狀態，而且能夠獲知節點上的調度策略。最後，大多數網格調度算法未考慮網絡通信延遲。在網格環境中資源節點是自治的，網格調度器不能夠對資源節點實現完全控制。由於網絡通信的開銷，如果網格調度器將一子任務調度到一性能下降的資源節點上執行，那么子任務可能會等待很長時間才能得到處理。極端情況下，延遲過大，網格調度器認為該服務不可用，從而不得不重新調度該子任務到新的資源節點上。這兩種情況都會使得任務的響應時間增大。這些都使得現有的網格任務調度算法在調度時效性、適用性方面存在一定的缺陷。
發明內容
本發明的目的就是針對現有技術的不足，提供一種基於反饋機制的網格任務調度方法，該方法能夠很好地適應網格環境的動態性，提高網格平臺的吞吐率，降低任務的平均完成時間，提高網格的響應速度。
本發明提供的基於反饋機制的網格任務調度方法，其步驟包括(1)網格調度器設置本地緩存，並利用緩存定時檢測操作清理緩存中長期不用的資源記錄信息；(2)當請求到達網格調度器時，將其放入網格調度器的請求隊列中；(3)從上述請求隊列中取出一個請求，並從該請求中提取可執行任務；(4)從緩存中選取與該任務所請求資源相匹配的資源集合R；(5)判斷該任務獲取的資源集合R是否為空，是則跳轉至步驟(6)，否則跳轉至步驟(7)；(6)根據任務所請求資源及緩存更新操作對緩存中的資源記錄信息進行更新，然後返回步驟(4)；(7)對獲得的資源集合R，根據資源記錄的最近響應時間TR由小到大進行排序，獲取排序後的資源集合中的排頭資源，即最近響應時間TR最小的資源r，並將其作為候選資源；(8)根據候選資源r，按照下述過程從資源集合R中選取最優的資源作最終選定資源rs(C1)判斷當前候選資源r的資源利用權值 是否在權值變動範圍 之內，其中r=TRrTVr-1,]]>TVr為最近一次提交任務到資源r的相鄰提交時間間隔，TRr為最近一次資源r的響應時間，RCr為等待資源r提供服務的任務個數，是則將資源r作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C2)；(C2)構建未檢測隊列，將資源集合中除候選資源外的其他資源放入未檢測隊列；(C3)取未檢測隊列的隊首資源為待檢測資源i，並在未檢測隊列中刪除資源i；(C4)計算候選資源r與待檢資源i最近響應時間差ΔTRn，候選資源r響應時間波動差ΔTRjr，待檢資源i響應時間波動差ΔTRji，如果(TRri-TRjr+TRji)0,]]>即待檢資源i提交後的響應時間小於候選資源r提交後的響應時間，則跳轉到(C5)，否則跳轉到(C3)；(C5)判斷資源i的資源利用權值 是否在權值變動範圍 之內，其中，i=TRiTVi-1,]]>TVi為最近一次提交任務到資源I的相鄰提交時間間隔，TRi為最近一次資源i的響應時間，RCi為等待資源i提供服務的任務個數，是則將資源i作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C3)；(C6)將最終選定資源rs返回網格任務調度方法；(9)將該任務提交給最終選定資源rs，資源提供服務的任務計數器RCrs加1；(10)資源處理完請求後返回到網格調度器，計算緩存中相應資源的平均響應時間ART，該資源提供服務的任務計數器RCrs減1，並更新資源最近響應時間LRT及最近一次更新資源時間RUT；(11)判斷請求隊列是否仍有請求或者有新請求到來，是則返回步驟(2)，直到網格調度器關閉。
本發明針對當前網格環境下任務調度方法所存在的缺陷，提出了一種基於反饋機制的網格任務調度方法。該調度方法收集最近訪問到的資源信息，如資源名、資源性能、資源前一次響應時間、資源平均響應時間及最近一次更新時間等信息，並將其放入緩存中來輔助網格調度器進行調度決策(這裡所提到的緩存是指本地一塊存儲區域，它既可以是內存，也可以是其它存儲設備)。與現有的網格調度方案相比，本發明方法主要有如下特點(1)該方法以網格調度器實際收集的資源狀態數據為依據，利用資源節點處理任務的歷史數據來推斷資源節點的狀態，不需要每隔一段時間採集資源的狀態，具有相當的實時性和準確性；(2)該方法不會對資源的性能產生額外影響，而且不會額外增加網絡通信負擔；
(3)該方法減少了同信息服務交互所導致的網絡延遲，使得任務的響應時間縮短。
圖1為本網格任務調度方法流程示意圖；圖2為緩存定時檢測操作的流程示意圖；圖3為緩存更新操作的流程示意圖；圖4為資源檢測操作的流程示意圖。
具體實施例方式
本方法對硬體環境沒有特殊要求，軟體環境為網格平臺。基於反饋機制的網格任務調度方法中最重要的是緩存更新和反饋調度。
緩存更新的基本原理是網格調度器在調度任務時設置緩存，緩存中存放最近訪問過的服務信息，如資源名、資源最近響應時間LRT(Last Response Time)、資源平均響應時間ART(Average Response Time)、上一次提交任務時間等信息。這些信息是網格任務調度的依據，可幫助網格調度器正確地決策將任務提交給哪些資源來完成。資源性能可能會隨配置、程序升級等方面的變化而改變，新的資源也有可能加入到網格環境中，這都使得網格資源處於動態變化之中。因此網格調度器需要及時更新緩存中的資源信息，使其能夠反映網格資源的最新變化。緩存中的信息更新包括兩個方面一方面是緩存中已有資源信息的更新，這部分通常可以根據最近一次資源執行任務的情況來完成更新；另一方面是將新的性能更優的網格資源信息加入到緩存中或根據信息服務中的信息更新緩存中的信息，這部分通常需要與緩存中已有資源的性能進行比較後才能確定新資源能否加入緩存中。為了防止用過時的信息更新緩存，每次更新都需要記載最近一次更新資源時間RUT(Recent Update Time)。更新後的緩存中的資源需要根據性能及最近訪問時間進行排序，以便網格調度器能夠有效地選取資源。如果緩存空間不夠，需要刪除緩存中那些在一定時間內未使用的資源信息。
反饋調度的基本原理是假設網格調度器提交任務到同一資源的相鄰提交時間間隔為TV，資源的最近響應時間為TR。如果服務的執行時間大於TV，那麼後續到達該服務的任務將會形成隊列。此時請求需在隊列中等待一段時間，以便服務處理完前面的任務後再來響應該任務。如果服務的執行時間小於TV，那麼服務處理完所有任務後就一直處在間斷空閒狀態，直到下一任務的到來。理想情況下應是一個服務處理完一個任務以後，後面一個任務此時恰恰到達，這時任務的等待時間最短，服務利用率也最高。但等待時間最短，並不能說明處理時間最短，調度任務時不但要考慮等待時間，也要考慮處理時間。因此反饋調度主要依據提交任務到資源的時間間隔以及資源的響應時間來推斷資源的當前狀態，以決定是否能夠向該資源提交任務。
下面結合附圖對本發明作進一步詳細的說明。
首先，我們將r=TRrTVr-1]]>作為判斷資源狀態的指標，其中 表示到目前為止資源r的平均響應時間， 表示到目前為止網格調度器提交任務到資源r的平均相鄰提交時間間隔。如圖1所示，本發明調度方法包括以下步驟(1)網格調度器設置本地緩存，並定時檢測操作清理緩存中長期不用的資源記錄信息；緩存定時檢測操作的具體過程如圖2所示，包括(A1)設置計時器中斷時間間隔t，推薦值為60秒；(A2)計時器計時；(A3)判斷計時器是否到時，是則跳轉到(A4)，否則跳轉到(A2)；(A4)判斷緩存是否有剩餘空間，是則跳轉到(A2)，否則跳轉到(A5)；(A5)讀取緩存中未檢測的資源記錄信息；(A6)判斷該記錄信息所記錄資源是否在2t時間間隔內未使用過，是則刪除該資源；(A7)判斷緩存中是否還有未檢測的資源記錄，是則跳轉到(A5)，否則跳轉到(A8)；
(A8)判斷網格調度器是否要關閉，是則結束緩存定時檢測操作，否則跳轉到(A2)。
(2)當請求到達網格調度器時，將其放入網格調度器的請求隊列中；(3)從上述請求隊列中取出一個請求，並從該請求中提取可執行任務；(4)從緩存中選取與該任務所請求資源相匹配的資源集合R；(5)判斷該任務獲取的資源集合R是否為空，是則跳轉至步驟(6)，否則跳轉至步驟(7)；(6)根據任務所請求資源及緩存更新操作對緩存中的資源記錄信息進行更新，然後返回步驟(4)；緩存更新操作的具體過程如圖3所示，包括(B1)判斷緩存中是否有剩餘空間，是則跳轉到(B5)，否則跳轉到(B2)；(B2)讀取緩存中未檢測的資源記錄信息；(B3)判斷該記錄信息所記錄資源是否在2t時間間隔內未使用過，t的推薦值為120秒，是則刪除該資源；(B4)判斷緩存中是否還有未檢測的資源記錄，是則跳轉(B2)，否則跳轉到(B5)；(B5)訪問信息伺服器，獲取任務所請求資源的同一類資源，將其加入到緩存中並計算最近響應時間TR，返回網格任務調度方法。
(7)對獲得的資源集合R，根據資源記錄的最近響應時間TR由小到大進行排序，獲取排序後的資源集合中的排頭資源，即最近響應時間TR最小的資源r，並將其作為候選資源；(8)根據候選資源r和資源檢測操作從資源集合R中選取最終選定資源rs；資源檢測操作的具體過程如圖4所示，包括(C1)判斷當前候選資源r的資源利用權值 是否在權值變動範圍 之內，其中TVr為最近一次提交任務到資源r的相鄰提交時間間隔，TRr為最近一次資源r的響應時間，RCr為等待資源r提供服務的任務個數，是則將資源r作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C2)；(C2)構建未檢測隊列，將資源集合中除候選資源外的其他資源放入未檢測隊列；(C3)取未檢測隊列的隊首資源為待檢測資源i，並在未檢測隊列中刪除資源i；(C4)計算候選資源r與待檢資源i最近響應時間差ΔTRri，候選資源r響應時間波動差ΔTRjr，待檢資源i響應時間波動差ΔTRji，如果(TRri-TRjr+TRji)0,]]>即待檢資源i提交後的響應時間小於候選資源r提交後的響應時間，則跳轉到(C5)，否則跳轉到(C3)；(C5)判斷資源i的資源利用權值 是否在權值變動範圍 之內，其中TVi為最近一次提交任務到資源i的相鄰提交時間間隔，TRi為最近一次資源i的響應時間，RCi為等待資源i提供服務的任務個數，是則將資源i作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C3)；(C6)將最終選定資源rs返回網格任務調度方法。
(9)將該任務提交給最終選定資源rs，資源提供服務的任務計數器RCrs加1；(10)資源處理完請求後返回到網格調度器，計算緩存中相應資源的平均響應時間ART，該資源提供服務的任務計數器RCrs減1，並更新資源最近響應時間LRT及最近一次更新資源時間RUT；(11)判斷請求隊列是否仍有請求或者有新請求到來，是則返回步驟(2)，直到網格調度器關閉。
實例為了驗證基於反饋機制的網格任務調度方法的有效性，我們在分布式仿真網格支撐平臺GCDSP上實現了FBGS，並同無FBGS的GCDSP進行比較。本實驗共採用了12臺計算機，，其性能指標如表1，其中2臺分別作為調度伺服器和信息伺服器，剩餘10臺作為網格服務的提供者。測試所使用的服務是之前已經開發好的用於仿真物流運輸情況的網格服務，包括Production服務，Consumption服務，Transport服務，Manager服務和Viewer服務。我們在這10臺機器上都部署了這5種網格服務。由於10臺機器的性能不同，並且5種網格服務的處理時間也不相同，因此共形成了50種性能彼此不同的網格服務。
表1實驗機器性能列表
為了全面測試性能，我們共進行了四次實驗。四次實驗中提交給調度器進行處理的請求數分別為50，100，200和400。測試結果如表2所示，其中性能提升比的計算公式為
與GCDSP默認的網格任務調度器相比，採用FBGS的網格任務調度器性能更高，並且這種趨勢隨著提交給調度器進行處理的請求數的增加而更顯突出。
表2總的調度性能比較
權利要求
1.一種基於反饋機制的網格任務調度方法，其步驟包括(1)網格調度器設置本地緩存，並利用緩存定時檢測操作清理緩存中長期不用的資源記錄信息；(2)當請求到達網格調度器時，將其放入網格調度器的請求隊列中；(3)從上述請求隊列中取出一個請求，並從該請求中提取可執行任務；(4)從緩存中選取與該任務所請求資源相匹配的資源集合R；(5)判斷該任務獲取的資源集合R是否為空，是則跳轉至步驟(6)，否則跳轉至步驟(7)；(6)根據任務所請求資源及緩存更新操作對緩存中的資源記錄信息進行更新，然後返回步驟(4)；(7)對獲得的資源集合R，根據資源記錄的最近響應時間TR由小到大進行排序，獲取排序後的資源集合中的排頭資源，即最近響應時間TR最小的資源r，並將其作為候選資源；(8)根據候選資源r，按照下述過程從資源集合R中選取最優的資源作最終選定資源rs(C1)判斷當前候選資源r的資源利用權值 是否在權值變動範圍 之內，其中r=TRrTVr-1]]>，TVr為最近一次提交任務到資源r的相鄰提交時間間隔，TRr為最近一次資源r的響應時間，RCr為等待資源r提供服務的任務個數，是則將資源r作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C2)；(C2)構建未檢測隊列，將資源集合中除候選資源外的其他資源放入未檢測隊列；(C3)取未檢測隊列的隊首資源為待檢測資源i，並在未檢測隊列中刪除資源i；(C4)計算候選資源r與待檢資源i最近響應時間差ΔTRri，候選資源r響應時間波動差ΔTRjr，待檢資源i響應時間波動差ΔTRji，如果(TRri-TRjr+TRji)0,]]>即待檢資源i提交後的響應時間小於候選資源r提交後的響應時間，則跳轉到(C5)，否則跳轉到(C3)；(C5)判斷資源i的資源利用權值 是否在權值變動範圍 之內，其中i=TRiTVi-1,]]>TVi為最近一次提交任務到資源i的相鄰提交時間間隔，TRi為最近一次資源i的響應時間，RCi為等待資源i提供服務的任務個數，是則將資源i作為最終選定資源rs並跳轉至(C6)，否則跳轉到(C3)；(C6)將最終選定資源rs返回網格任務調度方法；(9)將該任務提交給最終選定資源rs，資源提供服務的任務計數器RCrs加1；(10)資源處理完請求後返回到網格調度器，計算緩存中相應資源的平均響應時間ART，該資源提供服務的任務計數器RCrs減1，並更新資源最近響應時間LRT及最近一次更新資源時間RUT；(11)判斷請求隊列是否仍有請求或者有新請求到來，是則返回步驟(2)，直到網格調度器關閉。
2.根據權利要求1所述的調度方法，其特徵在於所述步驟(1)採用下述步驟進行定時檢測(A1)設置計時器中斷時間間隔t；(A2)計時器計時；(A3)判斷計時器是否到時，是則跳轉到(A4)，否則跳轉到(A2)；(A4)判斷緩存是否有剩餘空間，是則跳轉到(A2)，否則跳轉到(A5)；(A5)讀取緩存中未檢測的資源記錄信息；(A6)判斷該記錄信息所記錄資源是否在2t時間間隔內未使用過，是則刪除該資源；(A7)判斷緩存中是否還有未檢測的資源記錄，是則跳轉到(A5)，否則跳轉到(A8)；(A8)判斷網格調度器是否要關閉，是則結束緩存定時檢測操作，否則跳轉到(A2)。
3.根據權利要求1所述的調度方法，其特徵在於步驟(6)包括以下過程(B1)判斷緩存中是否有剩餘空間，是則跳轉到(B5)，否則跳轉到(B2)；(B2)讀取緩存中未檢測的資源記錄信息；(B3)判斷該記錄信息所記錄資源是否在2t時間間隔內未使用過，是則刪除該資源；(B4)判斷緩存中是否還有未檢測的資源記錄，是則跳轉(B2)，否則跳轉到(B5)；(B5)訪問信息伺服器，獲取任務所請求資源的同一類資源，將其加入到緩存中並計算最近響應時間TR，返回網格任務調度方法。
全文摘要
本發明公開了一種基於反饋機制的網格任務調度方法。該方法以網格調度器實際收集的資源狀態數據為依據，利用資源節點處理任務的歷史數據來推斷資源節點的狀態，從而實現對網格任務的調度。具體步驟為①開啟網格調度器，設置本地緩存；②從請求隊列中取一請求，並從該請求中提取可執行任務；③從緩存中選取與該任務相匹配的資源集合R；④在資源集合R中選取最優資源；⑤將該任務提交給資源，並記錄提交時間；⑥返回步驟①。該方法不需要每隔一段時間採集資源的狀態，具有相當的實時性和準確性。該方法不會對資源的性能產生額外影響，而且不會額外增加網絡通信負擔。同時，該方法減少了同信息服務交互所導致的網絡延遲，使得任務的響應時間縮短。
文檔編號G06F9/50GK101013386SQ20071005149
公開日2007年8月8日 申請日期2007年2月6日 優先權日2007年2月6日
發明者金海 , 袁平鵬, 曹文治, 侯東暉, 鄺坪, 何亨 申請人:華中科技大學