基于ＣＰＵ－ＭＥＭ的負載共享調度機制研究

摘要：分布式系統中調度機制對負載共享系統性能有重要影響。基于CPU－MEM的負載共享策略考慮內存資源對系統性能的作用，降低了頁失效次數，提高了資源利用率。在CPU－MEM負載共享機制基礎上，考慮任務在執行過程中的變化特性，提出了在單節點上減少任務平均內存需求的多內存需求多時間片輪詢策略（RR－MMMCS）和基于預測的多內存多時間片策略（MMMCS－P）。實驗表明，無論是對計算密集型任務還是數據密集型任務，RR－MMMCS、MMMCS－P調度機制在平均響應時間方面具有較好的性能。

關鍵詞：調度策略；負載預測； CPU－MEM負載共享

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)05-1364-04

負載共享是用來提高分布式系統性能的技術。根據一定的系統資源指標，把系統負載從較重的節點轉移到較輕的節點上，從而有效地利用系統資源，提高整個系統性能。高效的負載共享策略應該考慮的主要問題是如何通過減少任務的頁失效次數、縮短任務的排隊時間和最小化任務的遷移費用等方法來減少其平均響應時間，降低系統性能的損耗。因此，在設計負載共享策略時，不僅要考慮系統中CPU資源情況，也要考慮內存資源狀態。缺乏對內存資源問題的考慮會嚴重惡化系統性能，抵銷策略的優越性。另外，隨著CPU與內存在速度上的差距增大，由內存問題造成的時間延遲對整個系統性能的影響日益重要。如何充分有效地利用內存資源成了高效負載共享策略的重要組成部分。基于CPU－MEM的負載共享策略考慮了CPU與內存資源，獲得了較好的系統性能。

在對分布式系統的研究中，節點調度策略一般采用FCFS或RR[1]，僅考慮了任務的時間特性，而未考慮任務的內存數據特性。執行時間間隔的分布對任務的下一次執行具有一定的預言作用，該特性可以作為基于預測的調度策略的基礎。

針對CPU－MEM共享策略的特點，提出了多內存需求多時間片輪詢策略（RR－MMMCS）和基于預測的多內存多時間片策略(MMMCS－P)。它們能更有效地利用系統內存資源，提高了系統性能。

1基于CPU－MEM的負載共享策略

基于CPU－MEM負載共享策略較好地實現了內存與CPU資源的統一。基本原理描述如下：

MMMCS－P算法的目標是發揮任務執行等待時間間隔的分布對其下一次執行的預言作用，同時讓內存需求大的任務獲得更多的服務時間，用較快的速度將大內存需求任務執行完畢，減少節點中內存的平均使用量，快速縮短CPU等待隊列的長度，降低頁失效速率和任務遷移次數。

3系統和負載模型

本文擴展了Li Xiao等人開發的分布式系統模擬器[2]的功能，增加實現了FCFS、RR－MMMCS和MMMCS－P算法。實驗參數如表1所示。節點參數取自Sun SPARC-20、Sun Ultra 5和Sun Ultra 10工作站。遷移的相關代價參數根據SPARC-20工作站組成的以太網網絡服務時間設定。

系統中每一個任務只能處于以下幾種狀態中的一種：就緒、執行、頁失效、數據傳輸和完成。當在一個任務的執行過程中有頁失效發生，則在頁失效處理的過程中從就緒隊列中掛起，CPU執行其他任務。有幾個任務處于頁失效時，系統按照先進先出的順序處理。系統有以下的規定和假設：

a)每一個節點包含全局的負載指數數據（其他節點的CPU和內存負載信息），周期性地收集其他節點的負載信息并分發自己的負載信息。

b)定位策略用來決定一個任務遷移的目的地，從分布式系統中找到負載最輕的節點。

c)當一個任務到達時為其分配內存空間。任務的內存門限是其請求內存大小的40%。頁失效均勻分布在任務執行期間。當某一節點中任務的內存門限值之和等于或大于允許用戶使用的內存空間時任務以給定速率發生頁失效。

d)采用發送者觸發傳輸策略。負載較重的節點試圖將其負載傳輸給負載較輕的節點。

實驗中采用了八個日志[3]，都是在不同的時間段從工作站上收集的任務執行數據，分布在六個工作站上。內存需求量平均值為1和4 MB。構成這八個日志的任務有五項數據內容：{arrival－time，arrival－node，memory－size，service－time，task－type}。Arrival－time是任務的到達時間，精確到10 ms；Arrival－node是任務到達節點，分別以數值0~5表示；Memory－size是任務的內存需求量，系統實際分配給任務的內存量是根據節點的內存負載情況、內存門限值和內存需求量共同決定的；Ser-vice－time是任務完成需求的CPU服務時間；Task－type是任務類型，決定任務是否不可遷移。

4性能分析

基于系統模型和負載狀況，以任務的平均響應時間作為衡量系統性能的主要指標，分別討論系統在如下七種策略中的性能表現：基于CPU負載共享和輪詢調度機制策略(CPU－RR)、基于CPU負載共享和多內存多時間片輪詢調度機制策略(CPU－RR－MMMCS)、基于CPU負載共享和基于預測的多內存多時間片策略(CPU－MMMCS－P)、基于CPU－MEM負載共享和先來先服務調度機制的策略(CPU－MEM－FCFS)、基于CPU－MEM負載共享和輪詢調度機制的策略(CPU－MEM－RR)、基于CPU－MEM負載共享和多內存多時間片輪詢調度策略(CPU－MEM－RR－MMMCS)、基于CPU－MEM負載共享和基于預測的多內存多時間策略(CPU－MEM－ MMMCS－P)。

基于上述八個日志進行了模擬實驗。從圖2、3可以看出：整體上，基于CPU－MEM的負載共享策略無論是在數據密集型負載（圖3）還是在計算密集型負載（圖2）的情況下其性能總是優于基于CPU的負載共享策略；RR－MMMCS 與MMMCS－P策略無論是對基于CPU的還是基于CPU－MEM的負載共享系統，相對于FCFS和RR策略都有更好的性能；由于增加了預測機制，MMMCS－P策略無論是對于基于CPU的還是基于CPU－MEM的負載共享系統，相對于RR－MMMCS都有更好的性能。

如圖2所示，當任務的內存需求量不大時，基于CPU－MEM的負載共享策略本身能處理系統的內存負載問題，節點中的內存負載很輕，頁失效很少發生， RR－MMMCS調度策略的性能提高不大， CPU－MEM－RR－MMMCS與CPU－MEM－RR相比性能提高不大。對基于CPU的負載共享系統來說，負載共享策略本身缺少對內存資源的考慮， RR－MMMCS策略的優點得到有力體現，相對性能在最多情況下提高了22．2%。而MMMCS－P策略很好地處理單節點上的任務調度，快速縮短任務的排隊時間，減少節點上任務平均內存需求量，所以與基于CPU的、基于CPU－MEM的負載共享策略結合，任務的平均響應時間都很短。因此MMMCS－P策略的優點得到有力的體現。從實驗結果可以看出，相比于RR－MMMCS，MMMCS－P策略更加適用于計算密集型任務。

在數據密集型的負載情況下，如圖3所示， MMMCS－P和RR－MMMCS策略對系統性能均有改善。由于增加了預測機制，MMMCS－P策略對系統性能提高更大。而對基于CPU的負載共享系統來說，共享策略本身不能從整體上將節點的內存負載有效地分配到整個系統中，因此盡管RR－MMMCS可以提高單節點的內存資源利用效率，但是卻無法對整個分布式系統性能有較大提高。另外，可以看到FCFS調度策略效率相對較差。實驗表明，基于CPU－MEM的負載共享和MMMCS－P、RR－MMMCS調度策略有較好的性能。

5結束語

針對CPU－MEM共享負載策略的特點，提出了多內存需求多時間片輪詢策略。在基于任務剩余壽命分析的基礎上，進一步提出了基于預測的多內存需求多時間片策略。實驗分析得出以下結論： 

a)無論時間密集型任務系統還是數據密集型任務系統中，基于CPU－MEM共享負載策略、MMMCS－P和RR－MMMCS策略在平均響應時間方面擁有較好的性能。

b)RR－MMMCS策略無論是對于基于CPU的還是基于CPU－MEM的負載共享系統，由于能用較快的速度將大內存需求任務執行完畢，在平均響應時間方面比FCFS和RR策略都有更好的性能。

c)由于增加了預測機制，MMMCS－P策略無論是對基于CPU的還是基于CPU－MEM的負載共享系統，在平均響應時間上比RR－MMMCS策略更加優越。

參考文獻：

[1]DANDAMUDI S P. The effect of scheduling discipline on dynamic load sharing in heterogeneous distributed systems[C]//Proc of the 15th IEEE International Workshop on Modeling， Analysis， and Simulation of Computer and Telecommunications Systems(MASCOTS’97). Haifa， Israel: IEEE CNF， 1997:17-24.

[2]LI Xiao， ZHANG Xiao－dong， QU Yan－xia. Effective load sharing on heterogeneous networks of workstations[C]//Proc of International Parallel and Distributed Processing Symposium. Cancun: IEEE CNF， 2000: 1-5.

[3]ZHANG Xiao－dong， QU Yan－xia， LI Xiao. Improving distributed workload performance by sharing both CPU and memory resources[C]//Proc of the 20th International Conference on Distributed Computing Systems(ICDS’2000). Tai Pei: IEEE CNF， 2000:10－13.

[4]GLAS G， CAO P. Adaptive page replacement based on memory re-ference behavior[C]//Proc of ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems. Seattle: ACM， 1997:115－126.

[5]XIAO Li， CHEN Song－qing， ZHANG Xiao－dong. Adaptive memory allocations in clusters to handle unexpectedly large data－intensive jobs[J]. IEEE Trans on Parallel and Distributed Systems， 2004，15(7):577-592.

[6]董衛權， 范立軍， 全成斌，等. 一種負載平衡的太比特路由器調度算法[J]. 小型微型計算機系統， 2006，26(10):1724－1727.

[7]李文中， 郭勝， 許平，等. 服務組合中一種自適應的負載均衡算法[J]. 軟件學報， 2006，17(5):1068－1077.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”