多處理機(jī)系統(tǒng)的負(fù)載平衡模型設(shè)計(jì)

引言
    在嵌入式多處理機(jī)系統(tǒng)中，經(jīng)常出現(xiàn)這種情況：某些處理機(jī)負(fù)載過(guò)重而另外一些負(fù)載很輕，甚至空閑。這種情況無(wú)疑降低了整體系統(tǒng)的工作效率。為了提高處理機(jī)的利用率和系統(tǒng)并行計(jì)算的效率，應(yīng)該把負(fù)載過(guò)重的處理機(jī)上的一部分負(fù)載轉(zhuǎn)移到空閑或輕負(fù)載處理機(jī)上，這就出現(xiàn)了負(fù)載分配問(wèn)題的研究。
    簡(jiǎn)單的說(shuō)，負(fù)載平衡就是要盡量均勻地分配任務(wù)，并盡量減少結(jié)點(diǎn)之間的通信。解決負(fù)載平衡問(wèn)題，通常有靜態(tài)和動(dòng)態(tài)兩種調(diào)度策略：
    ①靜態(tài)負(fù)載平衡是根據(jù)系統(tǒng)的先驗(yàn)知識(shí)做出決策，運(yùn)行時(shí)負(fù)載不能重新分配。
    ②動(dòng)態(tài)負(fù)載平衡是根據(jù)計(jì)算機(jī)過(guò)程中數(shù)據(jù)項(xiàng)的變化情況，交換系統(tǒng)的狀態(tài)信息來(lái)決定系統(tǒng)負(fù)載的分配。它具有超過(guò)靜態(tài)算法的執(zhí)行潛力，能夠適應(yīng)系統(tǒng)負(fù)載變化情況，比靜態(tài)算法更靈活、有效。但是由于必須收集、存儲(chǔ)并分析狀態(tài)信息，因此動(dòng)態(tài)算法會(huì)產(chǎn)生比靜態(tài)算法更多的系統(tǒng)開(kāi)銷，不過(guò)這種開(kāi)銷和付出常是有所回報(bào)的。
    本文描述了一種有效的嵌入式多處理機(jī)系統(tǒng)的負(fù)載平衡模型，通過(guò)動(dòng)態(tài)判斷當(dāng)前系統(tǒng)的負(fù)載情況，自動(dòng)選擇負(fù)載平衡算法，從而使整個(gè)系統(tǒng)以盡可能小的附加代價(jià)來(lái)達(dá)到全局的負(fù)載平衡。最后，在卡內(nèi)基·梅隆大學(xué)的負(fù)載平衡測(cè)試框架上，搭建仿真環(huán)境進(jìn)行模擬測(cè)試。結(jié)果顯示，該模型能較好地平衡各結(jié)點(diǎn)的負(fù)載。

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

    其中，ε和ω為經(jīng)驗(yàn)調(diào)整系數(shù)，O<ε≤10，K1<ω<+∞，ω為足夠大的數(shù)；μ、L和M分別是處理機(jī)i的CPU利用率、運(yùn)行隊(duì)列長(zhǎng)度和處理機(jī)i中所有任務(wù)請(qǐng)求的內(nèi)存之和；Mem(i)為處理機(jī)i的可用內(nèi)存。
    整個(gè)系統(tǒng)的總負(fù)載為：

   
    系統(tǒng)的平均負(fù)載wavg可以簡(jiǎn)單認(rèn)為是：

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

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

   
    為達(dá)到任務(wù)的均勻分布，應(yīng)求得相關(guān)域中重載結(jié)點(diǎn)應(yīng)該傳遞給該結(jié)點(diǎn)的負(fù)載量(設(shè)為Mk)，但是必須對(duì)每個(gè)結(jié)點(diǎn)引入閾值H(j)，以避免任務(wù)從負(fù)載更輕的輕載結(jié)點(diǎn)遷移過(guò)來(lái)。若WORK(j)>Wavg′，則H(j)一WORK(j)一Wavg′；否則，H(j)=0。

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

   
    對(duì)每個(gè)結(jié)點(diǎn)引入閾值H(j)，以避免任務(wù)從負(fù)載更輕的輕載結(jié)點(diǎn)遷移過(guò)來(lái)。若WORK(j)>Wavg′，則H(j)=WORK(j)一wavg′；否則，H(j)=0。則Mk的值為：

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

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

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