分布式系統中基于非合作博弈的調度算法

童釗+肖正+李肯立+劉宏+李俊

摘 要：針對分布式系統中任務調度問題，根據分布式環境下的任務調度特性，建立了一個非合作博弈的多角色任務調度框架，在此基礎上提出了一種基于納什均衡聯合調度策略的分布式強化學習算法.相比于靜態調度算法，該算法需要更少的系統知識.能使調度器主動學習任務到達和執行的相關先驗知識，以適應相鄰調度器的分配策略，目標是使得調度器的策略趨向納什均衡.模擬實驗結果表明：所提出的算法在任務的預期時間和公平性上相對于OLB（機會主義負載均衡）、MET（最小執行時間）、MCT（最小完成時間）等同類調度算法具有更好的調度性能.

關鍵詞：分布式計算；強化學習；任務調度；負載均衡

中圖分類號：TP301.6 文獻標識碼：A

文章編號：1674-2974（2016）10-0139-09

Abstract：To address the task scheduling problem in distributed systems， based on an important feature of task scheduling in distributed computing environment， we have established a non-cooperative game framework for multi-layer multi-role， and put forward a distributed reinforcement learning algorithm of the joint scheduling strategy of Nash equilibrium. Compared with static scheduling algorithm， the proposed algorithm needs less system information. It enables the scheduler to actively learn task arrival， perform related knowledge and adapt to the adjacent scheduler allocation policy. The target is to move the schedulers strategy toward Nash equilibrium. Simulation experiments show that the proposed algorithm achieves excellent performance in expected response time of tasks and fairness， compared with classical scheduling algorithms such as OLB， MET and MCT.

Key words：distributed computing； reinforcement learning； task scheduling； load balance

隨著科技的發展，基于Internet的計算方式發展迅速.如今云計算試圖對線上資源進行虛擬化整合并使得需求更加透明[1-2].可以得知，當今的計算方式從獨立的計算模式向網絡化方向發展.云計算作為目前廣泛部署的分布式系統，該系統可以提供巨大的計算能力滿足并發請求，使得云計算在日常生活中變得更加重要.而在云計算系統中，任務的負載均衡是發揮其巨大潛力的關鍵因素[3].

在分布式系統中，存在大量的不確定性.由于網絡不穩定的通信消耗以及計算能力的波動，導致任務的執行時間是隨機的，這些參數取決于系統的當前狀態.基于歷史記錄或工作負載建模的預測用來評估工作的執行時間[4].精度差和復雜度高是這類方法的缺點.此外，由于任務隨機到達，其大小和CCR（Computation to Communication Ratio，計算通信比）是無法預測的.因此，在分布式系統中動態算法受到廣泛研究.在分布式計算系統中，批處理模式是一類動態調度方法.Min-Min，Max-Min和Suffrage是三個典型的啟發式批處理算法，這種算法為了獲得任務到達和執行信息，很多時間用于等待和評估，缺乏實時性.相反，在線模式中，任務到達后被立即調度，如機會主義負載均衡（OLB， Opportunistic Load Balancing）的算法，最小執行時間（MET， Minimum Execution Time），最小完成時間（MCT， Minimum Completion Time）等調度算法[5-6].然而它們忽略了后續任務的到達和對整體性能的影響.為了獲得全局優化，諸多學者提出了新的動態算法來適應任務的到達和執行過程，Kwok提供一個資源計劃系統來存儲下面工作的資源[7].Yang提出一種基于應用程序級和系統級的性能預測任務調度方案[8-9].

在分布式系統中，負載均衡涉及眾多的調度器之間的協作.據統計，這類問題研究較少.就合作型調度而言，幾個決策者合作決策以使整個系統性能最佳，Mashayekhy等基于合作博弈理論研究了該調度問題[10-11]；Peter提出基于經濟學中競標概念的合同網協議[12-13]；Subrata等將網格負載均衡問題建立為一個非合作博弈模型[14].在上述研究中，博弈論是一個建立協同問題模型的主要工具.對于該類問題，現有大多數研究使用全局方法，目標是最小化所有任務的平均響應時間.實際上，這些算法在非馬爾科夫環境下可能會導致失敗[15].Subrata等人研究非馬爾科夫環境下任務調度算法的執行性能[13-15].

由于分布式系統存在的諸多不確定性，越來越多的研究人員將“強化學習”這種方法引入到該研究領域.通常，將“強化學習”定義為智能系統從環境到行為映射的學習，使得獎勵信號（即，強化信號）的函數值最大，在強化學習中由環境提供的強化信號是對產生動作好壞的一種評價（通常為標量信號），而不是告訴強化學習系統RLS（Reinforcement Learning System）如何去產生正確的動作.由于外部環境提供的信息資源較少，使得RLS必須靠自身的經歷進行學習.通過這種方式，強化學習系統在行動評價的環境中獲得知識，改進行動方案以適合當前環境[15].

分布式環境中的處理機，在本文中稱為處理單元PEs（Process Elements）.在分布式環境中，一個高效的任務調度算法是必要的.而在分布式環境的調度中，一個調度器可以將任務分配給其管理的處理單元，或其他相鄰調度器.因此，調度器之間存在合作的關系，相對于集中式調度，分布式調度有兩個重要的問題需要解決：1）調度器之間，尤其是來自不同域的調度器之間，如何調度.2）調度器之間是如何相互作用.

在本文中，針對自利型調度引入強化學習方法，使得在多個調度器之間進行協同調度時考慮環境具有的不確定性，同時還能適應其他的調度器的策略，達到最優調度的目的.

1 分布式系統調度框架

企業或者是科研機構中的所有資源通過互聯網連接在一起，但他們可能屬于不同的管理域.每一個域中都有一個或者多個調度器來處理到達的任務.由于缺少必要的資源或是計算效率低，任務可能會被轉送到其他域.以分布式計算為例，用戶并不關心任務請求是在何地處理的.圖1是一個分布式計算系統，資源以管理域分割開，系統中有多個調度器.用戶提交任務給這些調度器，并且由后臺的調度器分派相應的計算單元去執行.

面對如此多的調度器，首先是怎樣將它們組織起來.Rao等提出了一個分布式資源共享框架[16]，它提供了兩個調度器之間詳細的相互關系.因此，本

本文提出了一個分層調度模型（圖2）.在更高層次中的調度器具有更廣闊的視野，所以這種分層設計可以減少通信和提高效率.在圖2中，所有的PE都位于資源層，最終是由處理器分配任務給它們.一個PE屬于一個或多個自治域并且在多個調度器中管理，一個調度器可以和其管理的PEs進行通信.換而言之，調度器可以知道它管理的每一個PE的狀態，在同一層的調度器管理下一層的元素.調度器之間通過細線連接起來，這些細線代表它們是相鄰并且可以進行通信，當在調度時，任務可以被分配給調度器直接管理的PE或由其相鄰的調度器

對應管理的PE中，如果任務仍然不能被合理分配，則調度器將其移交給更高一層的調度器.

在分布式計算系統的資源可以分為3種角色：

1）PE（Process Element）：用于計算.

2）協作型調度器：和其它的在相同組的協作型調度器共同去處理接收的任務.

共享相同的利益，在執行任務時又充分合作的調度器被稱作協作型調度.通常一個域形成一個組，本文不做討論.

3）自利型調度器：能夠自主接受或拒絕任務以達到自身利益最大化；其所代表的組之間通過達成一個聯合戰略，實現利益的雙贏.

圖2顯示了調度器的組織結構和角色之間可能的關系，PE由一個或多個調度器負責.在中間層，四邊形代表一個域，協作型調度器以組的方式劃分，他們分配任務給在同一個組內的其它調度器或附屬于它的PE.

一個重要的問題是，這樣一個可能由成千上萬的資源組成的分布式計算平臺是怎樣協同進行工作的，各角色之間的各種協議使之成為一個松散耦合的系統.

1）站內分配協議：適用于PE和協作型調度器之間.Min-Min，MET，MCT等調度算法屬于該協議；

2）站內合作協議：適用于協作型調度器之間.在一個組的協作型調度器互相幫助來優化整個組的性能，再調度和合作型博弈使用這樣的協議；

3）站間合作協議：適用于自利型調度器之間.在其所代表的組之間通過達成一個聯合戰略，實現利益的共贏.這個協議的研究相對較少，是本文的研究重點.

這個框架來自于Sakellariou， R.提出的分層semi-selfish網格模型[17].但本文所提出的模型更普遍，是Hanna H中的模型成為一個特例[18].這個框架具有大規模的分布式計算環境的管理特性.

2 博弈型調度

在分布式系統中，任務的到達是一個服從一定概率分布的隨機事件[19]，每一個調度器將這些到達的任務作為一個序列緩存起來.假設分布式計算系統可以處理m種不同的任務，集合T={t1，t2，…，tm}代表了所有可能的任務類型，PE集合定義為PE={PE1，PE2，…，PEn}，其中n代表PE的數目.調度器的集合形式為S={S1，S2，…，S|S|}，其中|S|為調度器數目，τji（k）定義為在時間點k，到達調度器Sj類型為ti的任務，調度器Sj中的所有任務根據它們到達的時間定義為任務流，用TFj代表調度器Sj上的任務流，每一個獨立的任務流可能會有不同的到達過程，一個任務τji（k）可以被分配到相鄰的調度器或者是附屬于該調度器的PE.本文用一個元組τji（k），b>（b∈PE∪S）代表一個任務分配，任務的響應時間是指：從被調度到達完成的時間間隔，以此作為任務調度的目標.

2.1 博弈模型

在圖2的基礎上，假設頂部調度層有n個自利型調度器，則自利型調度模型如圖3所示.

從式（5）～式（7）中可以得知，一個調度器的決策受到其它調度器調度策略的影響，自利型調度可以看作是一個博弈過程，通過競爭，慢慢形成一個沒有調度器愿意改變它當前的調度策略的狀態.換而言之，沒有調度器可以由單方面調整他們的策略來進一步減小他們的響應時間，這種狀態在博弈論中稱為納什均衡.事實上，自利調度器的協作旨在找到促成納什平衡的聯合策略.

根據博弈理論，本文使用下面的博弈來定義所研究的負載平衡問題.

定義1（自利型調度器的負載平衡）：自利型調度器的負載平衡問題由以下幾個部分組成：

選手：n個自利型調度器.

策略：聯合策略s{s1，...，sn}，由每一個調度器的接受率和拒絕率組成.

偏好：每個選手的偏好由它的期望響應時間RTi（s）來表示.當且僅當RTi（s）RTi（s'），則相比于策略s'更偏好s.

由于期望響應時間是連續、遞增的凸函數，則上述博弈存在唯一的納什平衡.Abdallah提出了兩種基于排隊理論的算法來得到博弈的均衡解[20].但是需要預測對象的到達率和服務率等參數.此外，這些算法在Non-Markovian環境下可能失敗.所以接下來本文提出了一種基于在線學習的算法，它不再需要預測參數或使用受Markov限制的式（6），式（7）.

2.2 基于學習的博弈調度算法

本文需要通過解決上述的博弈，實現負載均衡.一個解是指納什均衡對應的聯合策略，但滿足式

當解決定義1，2的問題時，每一個調度器需要知道任務到達過程和處理過程以及其它調度器的策略和網絡性能等，這使問題變得非常復雜.在本文中，使用機器學習方法去學習這個非合作博弈過程，機器學習是一門研究通過樣本自動挖掘知識的各種方法的學科.

強化學習是一種在線學習方法，它對比較有利的行為進行強化，樣本是歷史的分配.這種方法的顯著優勢就是與模型無關，這就意味著不需要得到像任務到達過程以及網絡性能等任何背景信息.本文使用強化學習算法中最常用的Q學習求解上述博弈調度問題.

在Q學習中Q函數代表累積響應時間，當任務被分配并完成后，根據任務的響應時間，更新該分配的Q值.式（9）表示一個任務被分配到j的時候調度器i的更新操作：

式（9）～式（11）給出了尋找最少響應時間的調度策略的算法，但是還存在兩個問題：

1）當使用這個算法時，調度器難以穩定在均衡狀態，因為每一個調度器的策略是擺動、不斷調整的.所以必須設立一個機制去測試是否達到均衡并引導策略的調整.

當達到均衡時，沒有一個調度器愿意違反他們當前的策略.當調度器企圖從它的老策略βoldi變成新策略βnewi前，觀察其它調度器的性能，如果m個調度器的性能由于上述策略的調整而得到提高，那么就表示m個調度器受益于改變，然后調度器i的策略根據式（12）的概率被更新.

在式（12）中，如果m=0，則沒有調度器性能提高，則βnewi以概率一的方式被接受.如果m=n，則說明離均衡存在較大的偏差，βoldi被保留.如果所有的調度器停止更新，那么當前的策略就認為是一個納什均衡的聯合策略.

2）任務轉發循環.由于轉發增加了任務的響應時間和浪費了網絡帶寬，所以多次轉發的概率很小，但仍然存在這種可能性，任務一直被轉發，形成了循環.為了避免這種異常情況的發生，一個任務在被調度器接受之前允許最多轉發3次.由于不超過3次的轉發限制，最終所有的到達任務都被接受，因此，式（2）得到滿足.

單個調度器的算法如下所示.它是一種分布式算法，每個調度器獨立運行這個算法，最后停止到唯一的均衡策略.

3 實驗及結果分析

本節通過模擬實驗研究在不同系統利用率、異構性下所提出方法的性能.實驗中使用的系統參數類似于Abdallah中的設置[20].有32個完全連接的候選調度器.表1給出了參數配置.調度器i的任務到達率根據到達比例因子qi計算：λi=qi×λ，這里λ為全部到達率之和∑iλi.平均通信時間t被假設成0.001 s，即傳輸一個任務平均花費t s.

下面將展示并分析實驗的相關結果.

3.1 最佳響應策略的收斂性

每個調度器i的初始策略是元素1/n組成的向量.然后每個調度器在每一次迭代中改進和更新其策略.在第一組實驗中，本文研究最佳響應策略的收斂性，即當其余的調度器保持策略不變時的最好調度策略.實驗模擬一個32個調度器的異構系統以及設置系統利用率為60%，即整個系統的到達率λ是2 316.初始調度策略在滿足式（1）～式（3）的條件下隨機產生，并且在其它調度器保持他們初始策略時讓一個調度器運行該算法.

上述實驗重復20次，每一次調度器的初始策略是隨機生成的，取20次實驗的平均響應時間.圖4顯示了當系統利用率為60%時，調度器的最后兩個策略的期望響應時間的差.大約200次迭代之后絕對差下降到10-4，被認為達到收斂.算法的收斂速度是F. Noriguki[22]和N. N. Dang[23]靜態算法的10倍，這是因為算法需要更多的時間用于學習.但本文認為較慢速度是可以容忍，因為在分布式系統處理的數以千計的任務中只有數百個任務受到收斂時間的影響[24-25].

圖5顯示了在不同的系統利用率下收斂時的迭代次數.隨著系統的利用率越來越高，本文的算法需要更多的迭代來獲得最佳響應策略.這是因為系統只有在大量的任務到來之后才會達到穩定的狀態.對于利用率為90%時，收斂速度增加到大約460次迭代.

3.2 系統利用率的影響

模擬一個異構系統用于研究系統利用率的影響.這個系統由32個調度器（見表1）組成.用ρ表示系統利用率.它由公式λ/∑iμi及條件0<ρ≤1計算而得.且ρ越大，系統負載越大.

圖6，圖7是當ρ從10%提高到90%時對應的計算結果.其中圖6是不同系統利用率下期望響應時間.隨著系統的利用率升高，期望響應時間變得更長.PROP_M算法效果較差，因為對于性能較差的調度器負載過大.而GOS算法效果最好，它提供了最優系統解決方案.我們的算法有一個次優的性能，例如，當系統利用率為60%時，響應時間比PROP_M算法少25%左右，比GOS多10%左右.

圖7顯示了3種算法的公平指數.PROP_M算法和我們算法的公平指數在1左右，對所有的調度器都很公平.GOS算法的公平指數介于1和重負載情況下的0.935之間.圖7也說明了調度器特性：由于自利性而缺乏充分的合作.

3.3 異構性的影響

在本節中，研究異構性對負載均衡性能的影響.處理器的速率是描述系統異構性一種簡單的方法.速度偏斜度（speed skewness）常用于表征異構性，其定義為系統中計算機的最大處理速率與最小處理速率之比.通過改變速度偏斜度研究負載均衡方案的有效性.

實驗模擬了一個包含32個調度器的系統，調度器分為3組，如表2所示.調度器1～8代表快速組，9～24代表中速組，25～32代表慢速組.起初，模擬一個同構系統，通過改變速度偏斜度進行了6個實驗，系統利用率均設為60%.總的達到速率如表2所示，任務到達比例qi如表1所示.

實驗結果如圖8，圖9所示，隨著偏斜度的增加，系統的計算能力增強，進而期望響應時間減少.對于同構系統而言，這3個算法有相同的性能.當系統資源性能存在差異時，本文的算法和GOS期望響應時間減少的更快.當偏斜度超過50，本文的算法與GOS算法接近.這意味著在高度異構系統下，本文所提出的算法是有效的.

從圖9中的公平指數可知：增加速度偏斜度時，本文所提出的算法和PROP_M算法公平指數幾乎為1.GOS公平指數從低偏斜度時的1下降到高偏斜度時的0.82.GOS算法的分配并不能保證平等的期望響應時間，尤其在高偏斜度情況下.均衡的負載和接近最優的性能是本文提出算法的主要優勢.

4 結 論

本文研究并行分布式系統中調度問題.在這種情形下，調度器不僅適應任務到達的隨機性和系統負載的多變性，而且適應其他調度器的分配策略.本文基于強化學習提出了相應的調度算法.調度器主動學習任務到達和執行以及與之相鄰的調度器行為知識，通過這種方法，在一定程度上實現了調度器之間的協作并且降低了平均響應時間.模擬實驗證明，該算法相比于幾個經典的調度算法在任務的預期時間和公平性上具有更好的性能.

參考文獻

[1] XU Yu-ming， LI Ken-li， HE Li-gang， et al. A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems[J]. IEEE Transactions on Parallel & Distributed Systems， 2014，26（12）：3208-3222.

[2] 鄭明玲，蔣句平，袁遠，等.一種面向大規模計算機的監控管理系統[J].湖南大學學報：自然科學版，2015，42（4）：107-113.

ZHENG Ming-ling， JIANG Ju-ping， YUAN Yuan， et al. A monitoring and management system for the large-scale computer[J]. Journal of Hunan University： Natural Sciences， 2015，42（4）：107-113.（In Chinese）

[3] 林闖， 蘇文博， 孟坤， 等. 云計算安全：架構、機制與模型評價[J]. 計算機學報， 2013，36（9）：1765-1784.

LIN Chuang， SU Wen-bo， MENG Kun， et al. Cloud computing security： architecture， mechanism and modeling[J]. Chinese Journal of Computers， 2013，36（9）：1765-1784. （In Chinese）

[4] GUTIERREZ-GARCIA J O， RAMIREZ-NAFARRATE A. Collaborative agents for distributed load management in cloud data centers using live migration of virtual machines[J]. IEEE Transactions on Services Computing， 2015，8（6）：916-929.

[5] BRAUN T D， SIEGEL H J， BECK N， et al. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J]. Journal of Parallel and Distributed Systems，2011，61（6）：810-837.

[6] LI Ken-li， TANG Xiao-yong， LI Ke-qin. Energy-efficient stochastic task scheduling on heterogeneous computing systems[J]. IEEE Transactions on Parallel and Distributed System， 2014， 25（11）： 2867-2876.

[7] KWOK Y K， HWANG K， SONG S S. Selfish grids： game-theoretic modeling and NAS/PSA benchmark evaluation[J]. IEEE Transactions on Parallel and Distributed Systems， 2007，18（5）：621-636.

[8] YANG L， SCHOPF J M， FOSTER I. Conservative scheduling： using predicted variance to improve scheduling decisions in dynamic environments[C]//International Conference on Supercomputing. Leipzig， Germany： IEEE Computer Society， 2003： 15-21.

[9] ZHANG Long-xin， LI Ken-li， ZHANG Fan， et al. Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous cluster[J]. Information Science， 2015，319（20）：113-131.

[10]朱夏， 宋愛波， 東方， 等. 云計算環境下基于協同過濾的個性化推薦機制[J]. 計算機研究與發展， 2014， 51（10）：2255-2269.

ZHU Xia， SONG Ai-bo， DONG Fang， et al. A collaborative filter recommendation mechanism for cloud computing[J]. Journal of Computer Research and Development， 2014，51（10）：2255-2269.（In Chinese）

[11]MASHAYWKHY L， NEJAD M M， GROSU D， et al. Energy-aware scheduling of MapReduce jobs for big data applications[J]. IEEE Transactions on Parallel and Distributed Systems， 2015，26（10）：2720-2733.

[12]TANG Zhuo， MO Yan-qing， LI Ken-li， et al. Dynamic forecast schedule algorithm for virtual machine placement in cloud computing environment[J]. Journal of Super Computing，2014，70（3）：1279-1296.

[13]PETER S， GIVARGIS T. Component-based synthesis of embedded systems using satisfiability modulo theories[J]. ACM Transactions on Design Automation of Electronic Systems， 2015，20（4）：1-27.

[14]SUBRATA R， ZOMAYA A Y， LANDFELDT B. Cooperative power-aware scheduling in grid computing environments[J]. Journal of Parallel and Distributed Computing， 2010，70（2）：84-91.

[15]LIU Chu-bo， LI Ken-li， LI Ke-qin. Strategy configurations of multiple users competition for cloud service reservation[J]. IEEE Transactions on Parallel and Distributed Systems， 2016，27（2）：508-520.

[16]RAO I， HUH E N， LEE S Y， et al. Distributed， scalable and reconfigurable inter-grid resource sharing framework[C]// Computational Science and Its Applications. Glasgow， UK： Springer， 2006： 390-399.

[17]SAKELLARIOU R， ZHAO H. A low-cost rescheduling policy for efficient mapping of workflows on grid systems[J]. Scientific Programming， 2004，12（4）：253-262.

[18]HANNA H， MOUADDIB A I. Task selection problem under uncertainty as decision-making[C]//First International Joint Conference on Autonomous Agents and Multiagent Systems： Part I. Bologna， Italy： ACM， 2002： 1303-1308.

[19]陳康， 鄭緯民. 云計算：系統實例與研究現狀[J]. 軟件學報， 2009，20（5）：1337-1348.

CHEN Kang， ZHENG Wei-ming. Cloud computing： system instances and current research[J]. Journal of Software， 2009，20（5）：1337-1348.（In Chinese）

[20]GROSU D， CHEONOPOULOS A T， LEUNG M Y. Noncooperative load balancing in distributed systems[J]. Concurrency & Computation Practice & Experience， 2008，20（16）：1953-1976.

[21]ABDALLAH S， LESSER V. Learning task allocation via multi-level policy gradient algorithm with dynamic learning rate[C] //International Joint Conference on Artificial Intelligence. Sydney， Australia： Springer， 2005： 76-82.

[22]KIM S， WEISSMAN J B. A genetic algorithm based approach for scheduling decomposable data grid applications[C]//International Conference on Parallel Processing. Dresden， Germany： ACM， 2004： 406-413.

[23]FUJIMOTO N， HAGIHAEA K. A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks[C]//International Symposium on Applications and the Internet Workshops. Tokyo， Japan： IEEE Computer Society， 2004： 674.

[24]N N DANG， S HWANG， S B LIM. Improvement of data grid's performance by combining job scheduling with dynamic replication strategy[C]//the 6th International Conference on Grid and Cooperative Computing. Xinjiang ， China： IEEE Computer Society， 2007： 513-520.

[25]費長江， 吳純青， 趙寶康， 等. 一種衛星移動通信語音業務半持續調度機制[J]. 湖南大學學報：自然科學版， 2015，42（8）：108-115.

FEI Chang-jiang， WU Chun-qing， ZHAO Bao-kang， et al. A semi-persistent scheduling mechanism for voice service in satellite mobile communication[J]. Journal of Hunan University： Natural Sciences， 2015，42（8）：108-115.（In Chinese）