多處理機系統的負載平衡模型設計

1 負載分配問題的數學描述
負載(1oad)是對一個處理機上運行的所有任務占用資源的衡量，負載指標(1oad index)是對負載進行量化的評價標準，不同的負載指標定義會得出當前時刻處理機不同的負載程度。關于這個問題，許多學者提出了他們的看法。
參考文獻的研究表明，一般效果較好的是，將單項指標中的資源隊列長度作為負載指標。參考文獻[4]建議使用資源利用率而不是資源隊列長度作為負載指標。近年來，隨著CPU速度的快速增長。CPU和內存通信之間的瓶頸較為突出，內存空間的不足可能導致頻繁的頁面交換，這使得訪問延遲大大增加。根據參考文獻的研究，定義這樣一個負載指標：
定義1 假設系統由N個處理單元構成，記為P0，P1，…，Pn-1。處理單元之間用通信線路連接，每個處理單元的負載記為WORK(i)，0≤i≤n-1。

其中，ε和ω為經驗調整系數，Oε≤10，K1ω+∞，ω為足夠大的數；μ、L和M分別是處理機i的CPU利用率、運行隊列長度和處理機i中所有任務請求的內存之和；Mem(i)為處理機i的可用內存。
整個系統的總負載為：

系統的平均負載wavg可以簡單認為是：

Wavg=TotalWork／n
定義負載上界為W1=Wavg+ζ，負載下界為W2=Wavg-ζ。其中，參數ζ視具體系統之不同而定。
有了以上的基礎，可以再進一步對各個結點的負載進行劃分：某個處理單元的負載WORK(i)W1，則為輕載結點；W1WORK(i)W2的為適載結點；WORK(i)>W2的為重載結點；WORK(i)=0的是空載結點，如圖1所示。

2 嵌入式多處理機系統的動態負載平衡算法
一般來說，系統中每個結點上的任務是動態產生的，負載大小也是動態變化的。在完成任務的過程中，要周期性地檢查任務完成的情況，并與其他結點交互這些情況。在此基礎上，按照一定原則確定是否對任務進行遷移，以及遷移的源、目的結點和遷移量。
在動態負載平衡策略中，比較有代表性的算法是輕載結點請求算法和重載結點請求算法。在嵌入式多處理機系統中，一般情況下，根據系統當前的負載情況選用其中之一，可以有效地平衡負載；但是，當系統負載發生變化后，可能會由于原先選用的算法不合適而導致附加開銷陡增，并且無法有效地平衡負載。因此，考慮到嵌入式系統本身的特點(例如資源有限等)，輕載結點請求算法和重載結點請求算法不加改進而直接用于嵌入式多處理機系統是不合適的。綜合這兩種算法的優缺點，就有了雙向請求算法。
2．1 輕載結點請求算法
輕負載結點會嘗試向重載結點請求任務，每個結點都定義了相關域，相關域的定義是把所有與之相鄰的結點作為相關域成員。結點只與其相關域中的結點進行交互和任務傳遞。如果請求到任務，則中止請求，否則就繼續詢問下一個相鄰結點。
啟動時，所有結點幾乎都是輕載結點。經過一段時間以后，結點開始檢查自身是否仍是輕載結點，如果仍是，就試圖在相關域中找出重載結點，并請求該結點上的任務。具體來說，設該輕載結點的負載為WORK(p)，相關域中有k個結點WORK(a+1)、WORK(a+2)……WORK(a+k)，則該部分的平均負載Wavg′為：

為達到任務的均勻分布，應求得相關域中重載結點應該傳遞給該結點的負載量(設為Mk)，但是必須對每個結點引入閾值H(j)，以避免任務從負載更輕的輕載結點遷移過來。若WORK(j)>Wavg′，則H(j)一WORK(j)一Wavg′；否則，H(j)=0。

然后，該結點就可以按照計算出的Mk值，向各個相關結點發出接收任務請求。
輕載結點請求算法流程如下：
①判斷自己是否為輕載結點；
②如果是，則找出附近的重載結點，并對它發出任務請求；
③接收到請求算法的重載結點向該輕載結點發送任務。
輕載結點請求算法的優點是：不需要相互交換負載信息；當每個結點均處于忙狀態時，不會有結點啟動輕載結點請求算法，幾乎不需要額外調度開銷；處理負載平衡問題的許多工作是由空閑結點來完成的，沒有給重載結點增加太多的額外負擔。
缺點是：在開始和結束階段時任務數相對較少，大量輕載結點會不斷發出任務請求，并且這些請求中的大多數無法得到滿足，于是許多輕載結點會繼續發出請求。最終，大量的請求增加了系統的額外開銷，影響了系統整體性能，同時大量針對重載結點的任務請求會拖延它們本身任務的執行。
在系統整體負載較輕時，使用輕載結點請求算法反而會造成較大的額外開銷，不利于系統的整體性能。因此，輕載結點請求算法適合在整個系統負載較重時使用。
2．2 重載結點請求算法
重負載結點會嘗試向輕載結點發送任務，至于發送任務給哪個結點，則取決于該結點相關域中結點的負載狀態。因此，該策略需要交換處理器的負載信息。一個結點有多種方法向鄰接結點通知它的負載情況，例如定期詢問、當任務數發生變化時、接收到執行任務請求時、響應請求或者當任務數超過一定閾值時等。
啟動一段時間以后，各結點開始檢查自身是否是重載結點，如果是，就試圖在相關域中均勻地分布任務。與輕載結點請求算法類似，首先計算域內的平均負載Wavg′，然后計算所要轉移的任務量Mk。
設該重載結點的負載為WORK(p)，相關域中有k個結點WORK(a+1)、WORK(a+2)…… WORK(a+k)，則該部分的平均負載Wavg′為：

對每個結點引入閾值H(j)，以避免任務從負載更輕的輕載結點遷移過來。若WORK(j)>Wavg′，則H(j)=WORK(j)一wavg′；否則，H(j)=0。則Mk的值為：

然后該結點就可以按照計算出的Mk值向各個相關結點發送任務。
重載結點請求算法流程如下：
①判斷自己是否為重載結點；
②如果是，則找出附近的輕載結點，并對它發出任務轉移請求；
③得到同意后，重載結點向該輕載結點發送任務。
重載結點請求的優點是：如果沒有過重負載的忙結點，就不會被空閑鄰接結點所打擾。這在整個系統負載較輕時顯得尤為重要。
缺點是：負載過重的重載結點還要額外增加處理負載平衡調度的負擔。
系統整體負載較重時，如果使用重載結點請求算法，那么重載結點在自身已經高負荷的情況下，還要負擔額外的處理負載平衡調度的負擔，發出任務轉移請求。由于重載結點數目較多，多數任務轉移請求無法得到滿足，重負載結點會在將來繼續發出請求，這些請求反而會造成較大的額外開銷。因此，重載結點請求算法適合在整個系統負載較輕時采用。
2．3 雙向請求算法
綜合上面兩種算法的優缺點，就有了雙向請求算法。發送者和接收者都能轉移任務，因此該算法兼有重載結點請求算法和輕載結點請求算法的優點。在系統負載較輕時，使用重載結點請求算法；在系統負載較重時，使用輕載結點請求算法。
一個需要解決的問題是：怎么樣判斷系統負載的輕與重，即怎樣決定何時使用重載結點請求算法，何時使用輕載結點請求算法。這是非常關鍵的，如果解決得不恰當，那么雙向請求算法就不是結合重載結點請求算法與輕載結點請求算法的優點，而是結合了二者的缺點。
2．4 雙向請求算法的改進
改進算法采用自適應算法，合理地設置判斷負載的閾值，并隨著每個結點的任務負荷變化，動態地改變這個評判標準，在系統負載重時采用輕載結點請求算法，在系統負載輕時采用重載結點請求算法。
改進算法中，每個結點記錄其相關域中其他結點的狀態信息，它維護2個集合，分別是輕載集θ和重載集φ。輕載集中保存的是其相關域中輕載結點的信息，而重載集中保存的是其相關域中重載結點的信息。每當結點狀態發生變化時，發消息給相關域中的各結點，各結點相應地改變其輕載集和重載集。
比較兩個集合的大小來決定采用重載結點請求算法還是輕載結點請求算法。當系統處于重負載時，會有大量的重負載結點，因而輕載集較小，而重載集較大，那么就采用輕載結點請求算法，在輕載集中找到接收者，由接收者主動申請結點的任務；當系統處于輕負載時，會有大量的輕負載結點，因而重載集較小，而輕載集較大，那么就采用重載結點請求算法，在重載集中找到發送者，由發送者主動遷移任務給結點。
各結點的狀態分為R(輕載，即任務接收者)和S(重載，即任務發送者)，閾值記為Mk。系統剛啟動時，各結點負載都比較輕(即均為R)，因此，重載集合為空，輕載集合則等于結點全集。當產生新任務時，只要結點負載不超過閾值Mk，這個新任務就在本地運行，結點狀態仍舊是R。此時的系統處于低負載，使用重載結點請求算法。隨著一個個新任務的到來，結點負載增大，當超過閾值Mk時，結點狀態變為S，并通知其他結點改變它們所維護的重載集與輕載集。
然后，比較結點輕載集和重載集的大小：若重載集小于輕載集，則繼續采用重載結點請求算法，按重載結點請求算法遍歷其輕載集中的結點，找出最合適執行新產生任務的結點，并發送任務；若重載集大于輕載集，則改用輕載結點請求算法，按輕載結點請求算法遍歷重載集中的結點，并發送請求任務的信號。
圖2為改進的雙向請求算法流程。

在嵌入式多處理機系統中，要實現任務的再次分配，一般是采取進程遷移的方式。但是進程遷移開銷較大，而且選擇可遷移進程的標準和策略是實現動態搶先式負載平衡的關鍵問題，若選擇了不該遷移的進程進行遷移，則可能會抵消負載平衡所帶來的性能的改善。
定義2 進程從開始執行到最終結束所花費的CPU周期數稱為“進程生存周期數”，進程當前已經耗費掉的CPU周期數稱為“進程已生存周期數”。
最簡單的方法是選擇最新生成的任務，導致處理器工作負載超出門限值，這些任務相對來說遷移的代價不大。也可以選擇已運行的任務，然而，可能的結果是遷移運行任務的代價抵消了作業運行時間的減少。因此，選擇生存期長、已生存周期數較少的進程更有利，可以使遷移開銷有時間得以補償。在本模型中，選擇前一種遷移策略。
仿真測試基于卡內基梅隆大學的負載平衡測試框架，設置了5個結點。輸入具有代表性的任務集之后，分別在系統負載較輕、較重和正常的情況下進行仿真測試。每個結點的剩余負載能力不同，分別記為：20，90，30，20，40。不妨假設，在負載平衡前，負載是平均分配到5個結點上的，使用本文中的策略進行負載平衡后，剩余負載能力較強的結點將負擔更多的負載。由于篇幅所限，這里只能列出部分測試結果，分別如圖3～圖5所示。

結 語
負載平衡調度是嵌入式多處理機系統利用處理器資源的一種有效途徑，它能讓多個處理單元比較平衡地共同承擔一系列繁重的任務，從而大大提高了系統的吞吐率與性能。動態負載平衡問題是一個正在蓬勃發展的研究熱點，還有許多未知的問題有待進一步地探索和研究。仿真結果表明，本文介紹的改進算法有效地平衡了各結點的負載，提高了整個系統資源的吞吐率與性能。該算法還有待在今后的研究工作中，通過實踐的檢驗，找出該算法所需設置的參數(例如閾值Mk和H(j))的合適值。