分布式系統(tǒng)中基于非合作博弈的調(diào)度算法

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

摘 要：針對(duì)分布式系統(tǒng)中任務(wù)調(diào)度問(wèn)題，根據(jù)分布式環(huán)境下的任務(wù)調(diào)度特性，建立了一個(gè)非合作博弈的多角色任務(wù)調(diào)度框架，在此基礎(chǔ)上提出了一種基于納什均衡聯(lián)合調(diào)度策略的分布式強(qiáng)化學(xué)習(xí)算法.相比于靜態(tài)調(diào)度算法，該算法需要更少的系統(tǒng)知識(shí).能使調(diào)度器主動(dòng)學(xué)習(xí)任務(wù)到達(dá)和執(zhí)行的相關(guān)先驗(yàn)知識(shí)，以適應(yīng)相鄰調(diào)度器的分配策略，目標(biāo)是使得調(diào)度器的策略趨向納什均衡.模擬實(shí)驗(yàn)結(jié)果表明：所提出的算法在任務(wù)的預(yù)期時(shí)間和公平性上相對(duì)于OLB（機(jī)會(huì)主義負(fù)載均衡）、MET（最小執(zhí)行時(shí)間）、MCT（最小完成時(shí)間）等同類調(diào)度算法具有更好的調(diào)度性能.

關(guān)鍵詞：分布式計(jì)算；強(qiáng)化學(xué)習(xí)；任務(wù)調(diào)度；負(fù)載均衡

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

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

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

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

由于分布式系統(tǒng)存在的諸多不確定性，越來(lái)越多的研究人員將“強(qiáng)化學(xué)習(xí)”這種方法引入到該研究領(lǐng)域.通常，將“強(qiáng)化學(xué)習(xí)”定義為智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，使得獎(jiǎng)勵(lì)信號(hào)（即，強(qiáng)化信號(hào)）的函數(shù)值最大，在強(qiáng)化學(xué)習(xí)中由環(huán)境提供的強(qiáng)化信號(hào)是對(duì)產(chǎn)生動(dòng)作好壞的一種評(píng)價(jià)（通常為標(biāo)量信號(hào)），而不是告訴強(qiáng)化學(xué)習(xí)系統(tǒng)RLS（Reinforcement Learning System）如何去產(chǎn)生正確的動(dòng)作.由于外部環(huán)境提供的信息資源較少，使得RLS必須靠自身的經(jīng)歷進(jìn)行學(xué)習(xí).通過(guò)這種方式，強(qiáng)化學(xué)習(xí)系統(tǒng)在行動(dòng)評(píng)價(jià)的環(huán)境中獲得知識(shí)，改進(jìn)行動(dòng)方案以適合當(dāng)前環(huán)境[15].

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

在本文中，針對(duì)自利型調(diào)度引入強(qiáng)化學(xué)習(xí)方法，使得在多個(gè)調(diào)度器之間進(jìn)行協(xié)同調(diào)度時(shí)考慮環(huán)境具有的不確定性，同時(shí)還能適應(yīng)其他的調(diào)度器的策略，達(dá)到最優(yōu)調(diào)度的目的.

1 分布式系統(tǒng)調(diào)度框架

企業(yè)或者是科研機(jī)構(gòu)中的所有資源通過(guò)互聯(lián)網(wǎng)連接在一起，但他們可能屬于不同的管理域.每一個(gè)域中都有一個(gè)或者多個(gè)調(diào)度器來(lái)處理到達(dá)的任務(wù).由于缺少必要的資源或是計(jì)算效率低，任務(wù)可能會(huì)被轉(zhuǎn)送到其他域.以分布式計(jì)算為例，用戶并不關(guān)心任務(wù)請(qǐng)求是在何地處理的.圖1是一個(gè)分布式計(jì)算系統(tǒng)，資源以管理域分割開，系統(tǒng)中有多個(gè)調(diào)度器.用戶提交任務(wù)給這些調(diào)度器，并且由后臺(tái)的調(diào)度器分派相應(yīng)的計(jì)算單元去執(zhí)行.

面對(duì)如此多的調(diào)度器，首先是怎樣將它們組織起來(lái).Rao等提出了一個(gè)分布式資源共享框架[16]，它提供了兩個(gè)調(diào)度器之間詳細(xì)的相互關(guān)系.因此，本

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

對(duì)應(yīng)管理的PE中，如果任務(wù)仍然不能被合理分配，則調(diào)度器將其移交給更高一層的調(diào)度器.

在分布式計(jì)算系統(tǒng)的資源可以分為3種角色：

1）PE（Process Element）：用于計(jì)算.

2）協(xié)作型調(diào)度器：和其它的在相同組的協(xié)作型調(diào)度器共同去處理接收的任務(wù).

共享相同的利益，在執(zhí)行任務(wù)時(shí)又充分合作的調(diào)度器被稱作協(xié)作型調(diào)度.通常一個(gè)域形成一個(gè)組，本文不做討論.

3）自利型調(diào)度器：能夠自主接受或拒絕任務(wù)以達(dá)到自身利益最大化；其所代表的組之間通過(guò)達(dá)成一個(gè)聯(lián)合戰(zhàn)略，實(shí)現(xiàn)利益的雙贏.

圖2顯示了調(diào)度器的組織結(jié)構(gòu)和角色之間可能的關(guān)系，PE由一個(gè)或多個(gè)調(diào)度器負(fù)責(zé).在中間層，四邊形代表一個(gè)域，協(xié)作型調(diào)度器以組的方式劃分，他們分配任務(wù)給在同一個(gè)組內(nèi)的其它調(diào)度器或附屬于它的PE.

一個(gè)重要的問(wèn)題是，這樣一個(gè)可能由成千上萬(wàn)的資源組成的分布式計(jì)算平臺(tái)是怎樣協(xié)同進(jìn)行工作的，各角色之間的各種協(xié)議使之成為一個(gè)松散耦合的系統(tǒng).

1）站內(nèi)分配協(xié)議：適用于PE和協(xié)作型調(diào)度器之間.Min-Min，MET，MCT等調(diào)度算法屬于該協(xié)議；

2）站內(nèi)合作協(xié)議：適用于協(xié)作型調(diào)度器之間.在一個(gè)組的協(xié)作型調(diào)度器互相幫助來(lái)優(yōu)化整個(gè)組的性能，再調(diào)度和合作型博弈使用這樣的協(xié)議；

3）站間合作協(xié)議：適用于自利型調(diào)度器之間.在其所代表的組之間通過(guò)達(dá)成一個(gè)聯(lián)合戰(zhàn)略，實(shí)現(xiàn)利益的共贏.這個(gè)協(xié)議的研究相對(duì)較少，是本文的研究重點(diǎn).

這個(gè)框架來(lái)自于Sakellariou， R.提出的分層semi-selfish網(wǎng)格模型[17].但本文所提出的模型更普遍，是Hanna H中的模型成為一個(gè)特例[18].這個(gè)框架具有大規(guī)模的分布式計(jì)算環(huán)境的管理特性.

2 博弈型調(diào)度

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

2.1 博弈模型

在圖2的基礎(chǔ)上，假設(shè)頂部調(diào)度層有n個(gè)自利型調(diào)度器，則自利型調(diào)度模型如圖3所示.

從式（5）～式（7）中可以得知，一個(gè)調(diào)度器的決策受到其它調(diào)度器調(diào)度策略的影響，自利型調(diào)度可以看作是一個(gè)博弈過(guò)程，通過(guò)競(jìng)爭(zhēng)，慢慢形成一個(gè)沒有調(diào)度器愿意改變它當(dāng)前的調(diào)度策略的狀態(tài).換而言之，沒有調(diào)度器可以由單方面調(diào)整他們的策略來(lái)進(jìn)一步減小他們的響應(yīng)時(shí)間，這種狀態(tài)在博弈論中稱為納什均衡.事實(shí)上，自利調(diào)度器的協(xié)作旨在找到促成納什平衡的聯(lián)合策略.

根據(jù)博弈理論，本文使用下面的博弈來(lái)定義所研究的負(fù)載平衡問(wèn)題.

定義1（自利型調(diào)度器的負(fù)載平衡）：自利型調(diào)度器的負(fù)載平衡問(wèn)題由以下幾個(gè)部分組成：

選手：n個(gè)自利型調(diào)度器.

策略：聯(lián)合策略s{s1，...，sn}，由每一個(gè)調(diào)度器的接受率和拒絕率組成.

偏好：每個(gè)選手的偏好由它的期望響應(yīng)時(shí)間RTi（s）來(lái)表示.當(dāng)且僅當(dāng)RTi（s）RTi（s'），則相比于策略s'更偏好s.

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

2.2 基于學(xué)習(xí)的博弈調(diào)度算法

本文需要通過(guò)解決上述的博弈，實(shí)現(xiàn)負(fù)載均衡.一個(gè)解是指納什均衡對(duì)應(yīng)的聯(lián)合策略，但滿足式

當(dāng)解決定義1，2的問(wèn)題時(shí)，每一個(gè)調(diào)度器需要知道任務(wù)到達(dá)過(guò)程和處理過(guò)程以及其它調(diào)度器的策略和網(wǎng)絡(luò)性能等，這使問(wèn)題變得非常復(fù)雜.在本文中，使用機(jī)器學(xué)習(xí)方法去學(xué)習(xí)這個(gè)非合作博弈過(guò)程，機(jī)器學(xué)習(xí)是一門研究通過(guò)樣本自動(dòng)挖掘知識(shí)的各種方法的學(xué)科.

強(qiáng)化學(xué)習(xí)是一種在線學(xué)習(xí)方法，它對(duì)比較有利的行為進(jìn)行強(qiáng)化，樣本是歷史的分配.這種方法的顯著優(yōu)勢(shì)就是與模型無(wú)關(guān)，這就意味著不需要得到像任務(wù)到達(dá)過(guò)程以及網(wǎng)絡(luò)性能等任何背景信息.本文使用強(qiáng)化學(xué)習(xí)算法中最常用的Q學(xué)習(xí)求解上述博弈調(diào)度問(wèn)題.

在Q學(xué)習(xí)中Q函數(shù)代表累積響應(yīng)時(shí)間，當(dāng)任務(wù)被分配并完成后，根據(jù)任務(wù)的響應(yīng)時(shí)間，更新該分配的Q值.式（9）表示一個(gè)任務(wù)被分配到j(luò)的時(shí)候調(diào)度器i的更新操作：

式（9）～式（11）給出了尋找最少響應(yīng)時(shí)間的調(diào)度策略的算法，但是還存在兩個(gè)問(wèn)題：

1）當(dāng)使用這個(gè)算法時(shí)，調(diào)度器難以穩(wěn)定在均衡狀態(tài)，因?yàn)槊恳粋€(gè)調(diào)度器的策略是擺動(dòng)、不斷調(diào)整的.所以必須設(shè)立一個(gè)機(jī)制去測(cè)試是否達(dá)到均衡并引導(dǎo)策略的調(diào)整.

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

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

2）任務(wù)轉(zhuǎn)發(fā)循環(huán).由于轉(zhuǎn)發(fā)增加了任務(wù)的響應(yīng)時(shí)間和浪費(fèi)了網(wǎng)絡(luò)帶寬，所以多次轉(zhuǎn)發(fā)的概率很小，但仍然存在這種可能性，任務(wù)一直被轉(zhuǎn)發(fā)，形成了循環(huán).為了避免這種異常情況的發(fā)生，一個(gè)任務(wù)在被調(diào)度器接受之前允許最多轉(zhuǎn)發(fā)3次.由于不超過(guò)3次的轉(zhuǎn)發(fā)限制，最終所有的到達(dá)任務(wù)都被接受，因此，式（2）得到滿足.

單個(gè)調(diào)度器的算法如下所示.它是一種分布式算法，每個(gè)調(diào)度器獨(dú)立運(yùn)行這個(gè)算法，最后停止到唯一的均衡策略.

3 實(shí)驗(yàn)及結(jié)果分析

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

下面將展示并分析實(shí)驗(yàn)的相關(guān)結(jié)果.

3.1 最佳響應(yīng)策略的收斂性

每個(gè)調(diào)度器i的初始策略是元素1/n組成的向量.然后每個(gè)調(diào)度器在每一次迭代中改進(jìn)和更新其策略.在第一組實(shí)驗(yàn)中，本文研究最佳響應(yīng)策略的收斂性，即當(dāng)其余的調(diào)度器保持策略不變時(shí)的最好調(diào)度策略.實(shí)驗(yàn)?zāi)M一個(gè)32個(gè)調(diào)度器的異構(gòu)系統(tǒng)以及設(shè)置系統(tǒng)利用率為60%，即整個(gè)系統(tǒng)的到達(dá)率λ是2 316.初始調(diào)度策略在滿足式（1）～式（3）的條件下隨機(jī)產(chǎn)生，并且在其它調(diào)度器保持他們初始策略時(shí)讓一個(gè)調(diào)度器運(yùn)行該算法.

上述實(shí)驗(yàn)重復(fù)20次，每一次調(diào)度器的初始策略是隨機(jī)生成的，取20次實(shí)驗(yàn)的平均響應(yīng)時(shí)間.圖4顯示了當(dāng)系統(tǒng)利用率為60%時(shí)，調(diào)度器的最后兩個(gè)策略的期望響應(yīng)時(shí)間的差.大約200次迭代之后絕對(duì)差下降到10-4，被認(rèn)為達(dá)到收斂.算法的收斂速度是F. Noriguki[22]和N. N. Dang[23]靜態(tài)算法的10倍，這是因?yàn)樗惴ㄐ枰嗟臅r(shí)間用于學(xué)習(xí).但本文認(rèn)為較慢速度是可以容忍，因?yàn)樵诜植际较到y(tǒng)處理的數(shù)以千計(jì)的任務(wù)中只有數(shù)百個(gè)任務(wù)受到收斂時(shí)間的影響[24-25].

圖5顯示了在不同的系統(tǒng)利用率下收斂時(shí)的迭代次數(shù).隨著系統(tǒng)的利用率越來(lái)越高，本文的算法需要更多的迭代來(lái)獲得最佳響應(yīng)策略.這是因?yàn)橄到y(tǒng)只有在大量的任務(wù)到來(lái)之后才會(huì)達(dá)到穩(wěn)定的狀態(tài).對(duì)于利用率為90%時(shí)，收斂速度增加到大約460次迭代.

3.2 系統(tǒng)利用率的影響

模擬一個(gè)異構(gòu)系統(tǒng)用于研究系統(tǒng)利用率的影響.這個(gè)系統(tǒng)由32個(gè)調(diào)度器（見表1）組成.用ρ表示系統(tǒng)利用率.它由公式λ/∑iμi及條件0<ρ≤1計(jì)算而得.且ρ越大，系統(tǒng)負(fù)載越大.

圖6，圖7是當(dāng)ρ從10%提高到90%時(shí)對(duì)應(yīng)的計(jì)算結(jié)果.其中圖6是不同系統(tǒng)利用率下期望響應(yīng)時(shí)間.隨著系統(tǒng)的利用率升高，期望響應(yīng)時(shí)間變得更長(zhǎng).PROP_M算法效果較差，因?yàn)閷?duì)于性能較差的調(diào)度器負(fù)載過(guò)大.而GOS算法效果最好，它提供了最優(yōu)系統(tǒng)解決方案.我們的算法有一個(gè)次優(yōu)的性能，例如，當(dāng)系統(tǒng)利用率為60%時(shí)，響應(yīng)時(shí)間比PROP_M算法少25%左右，比GOS多10%左右.

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

3.3 異構(gòu)性的影響

在本節(jié)中，研究異構(gòu)性對(duì)負(fù)載均衡性能的影響.處理器的速率是描述系統(tǒng)異構(gòu)性一種簡(jiǎn)單的方法.速度偏斜度（speed skewness）常用于表征異構(gòu)性，其定義為系統(tǒng)中計(jì)算機(jī)的最大處理速率與最小處理速率之比.通過(guò)改變速度偏斜度研究負(fù)載均衡方案的有效性.

實(shí)驗(yàn)?zāi)M了一個(gè)包含32個(gè)調(diào)度器的系統(tǒng)，調(diào)度器分為3組，如表2所示.調(diào)度器1～8代表快速組，9～24代表中速組，25～32代表慢速組.起初，模擬一個(gè)同構(gòu)系統(tǒng)，通過(guò)改變速度偏斜度進(jìn)行了6個(gè)實(shí)驗(yàn)，系統(tǒng)利用率均設(shè)為60%.總的達(dá)到速率如表2所示，任務(wù)到達(dá)比例qi如表1所示.

實(shí)驗(yàn)結(jié)果如圖8，圖9所示，隨著偏斜度的增加，系統(tǒng)的計(jì)算能力增強(qiáng)，進(jìn)而期望響應(yīng)時(shí)間減少.對(duì)于同構(gòu)系統(tǒng)而言，這3個(gè)算法有相同的性能.當(dāng)系統(tǒng)資源性能存在差異時(shí)，本文的算法和GOS期望響應(yīng)時(shí)間減少的更快.當(dāng)偏斜度超過(guò)50，本文的算法與GOS算法接近.這意味著在高度異構(gòu)系統(tǒng)下，本文所提出的算法是有效的.

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

4 結(jié) 論

本文研究并行分布式系統(tǒng)中調(diào)度問(wèn)題.在這種情形下，調(diào)度器不僅適應(yīng)任務(wù)到達(dá)的隨機(jī)性和系統(tǒng)負(fù)載的多變性，而且適應(yīng)其他調(diào)度器的分配策略.本文基于強(qiáng)化學(xué)習(xí)提出了相應(yīng)的調(diào)度算法.調(diào)度器主動(dòng)學(xué)習(xí)任務(wù)到達(dá)和執(zhí)行以及與之相鄰的調(diào)度器行為知識(shí)，通過(guò)這種方法，在一定程度上實(shí)現(xiàn)了調(diào)度器之間的協(xié)作并且降低了平均響應(yīng)時(shí)間.模擬實(shí)驗(yàn)證明，該算法相比于幾個(gè)經(jīng)典的調(diào)度算法在任務(wù)的預(yù)期時(shí)間和公平性上具有更好的性能.

參考文獻(xiàn)

[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] 鄭明玲，蔣句平，袁遠(yuǎn)，等.一種面向大規(guī)模計(jì)算機(jī)的監(jiān)控管理系統(tǒng)[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，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ì)算安全：架構(gòu)、機(jī)制與模型評(píng)價(jià)[J]. 計(jì)算機(jī)學(xué)報(bào)， 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ì)算環(huán)境下基于協(xié)同過(guò)濾的個(gè)性化推薦機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展， 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ì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. 軟件學(xué)報(bào)， 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]費(fèi)長(zhǎng)江， 吳純青， 趙寶康， 等. 一種衛(wèi)星移動(dòng)通信語(yǔ)音業(yè)務(wù)半持續(xù)調(diào)度機(jī)制[J]. 湖南大學(xué)學(xué)報(bào)：自然科學(xué)版， 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）