云環(huán)境下基于強(qiáng)化學(xué)習(xí)的多目標(biāo)任務(wù)調(diào)度算法

童 釗，鄧小妹，陳洪劍，梅 晶，葉 鋒

(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410012)(高性能計(jì)算與隨機(jī)信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)室(湖南師范大學(xué))，長(zhǎng)沙 410012)

1 引 言

隨著計(jì)算機(jī)科學(xué)和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，云計(jì)算作為一種新的并行與分布式計(jì)算技術(shù)的發(fā)展方向被提出來(lái)[1].云計(jì)算平臺(tái)上的所有數(shù)據(jù)計(jì)算和存儲(chǔ)都在云端進(jìn)行，可以通過(guò)使用最少的代價(jià)來(lái)充分利用互聯(lián)網(wǎng)上的資源，以實(shí)現(xiàn)資源利用率最大化的目的[2].通常，根據(jù)用戶所需要的服務(wù)模式的不同，云計(jì)算可以分為三種類型：基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)和軟件即服務(wù)(SaaS)[3].在云計(jì)算平臺(tái)上，如何將用戶提交的請(qǐng)求合理的分配給云計(jì)算節(jié)點(diǎn)進(jìn)行處理，是影響云用戶的服務(wù)體驗(yàn)和云服務(wù)提供商的利潤(rùn)率的重要因素，也是任務(wù)調(diào)度要解決的核心問(wèn)題.云計(jì)算中的任務(wù)調(diào)度是一個(gè)NP難問(wèn)題，根據(jù)所要解決的云用戶需求的不同，任務(wù)調(diào)度算法往往側(cè)重于不同的優(yōu)化目標(biāo)，主要包括：調(diào)度長(zhǎng)度(makespan)、負(fù)載均衡(load balance)、服務(wù)質(zhì)量(Quality of Service,QoS)和經(jīng)濟(jì)原則(economical principle)等[4].

目前，大多數(shù)對(duì)于任務(wù)調(diào)度的研究只側(cè)重了對(duì)單目標(biāo)問(wèn)題的優(yōu)化，對(duì)于多目標(biāo)調(diào)度問(wèn)題由于其復(fù)雜性，研究相對(duì)較少.但在現(xiàn)實(shí)問(wèn)題中，只做到對(duì)任務(wù)調(diào)度問(wèn)題進(jìn)行單目標(biāo)的優(yōu)化通常是不夠的，多數(shù)情況下需要同時(shí)考量云用戶的用戶體驗(yàn)和云服務(wù)提供商的消耗成本等多方面的因素進(jìn)行決策.因此，本文考慮同時(shí)對(duì)任務(wù)的完成時(shí)間和虛擬機(jī)的執(zhí)行成本這兩個(gè)有重要意義并且相互沖突的目標(biāo)進(jìn)行優(yōu)化，擬解決在滿足云用戶對(duì)減少makespan的需求的基礎(chǔ)上，同時(shí)保證對(duì)云服務(wù)提供商的成本消耗的控制.

針對(duì)云環(huán)境下的任務(wù)調(diào)度算法的研究，Topcuouglu等[5]提出了優(yōu)化makespan的異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time,HEFT)算法.HEFT算法在小規(guī)模的有向無(wú)環(huán)圖(Directed Acyclic Graph,DAG)上可以得到較好的性能，但是隨著任務(wù)規(guī)模的增大，DAG任務(wù)的復(fù)雜性增加，導(dǎo)致HEFT算法的性能隨之下降；并且該算法只考慮了對(duì)單目標(biāo)makespan的優(yōu)化，沒(méi)有考慮其他影響任務(wù)調(diào)度性能的因素，使得該算法在實(shí)際應(yīng)用當(dāng)中具有一定的局限性.李君等[6]提出一種綜合時(shí)間能耗成本的任務(wù)調(diào)度算法(Time and Energy Consumption Cost Scheduling,TECCS)，通過(guò)引入通信因子和計(jì)算因子綜合時(shí)間與能耗成本來(lái)決定任務(wù)的調(diào)度順序，在期望完成時(shí)間條件下節(jié)省更多任務(wù)執(zhí)行成本；但是該算法考慮的是在期望完成時(shí)間的條件下實(shí)現(xiàn)對(duì)能耗成本的優(yōu)化，沒(méi)有實(shí)現(xiàn)對(duì)雙目標(biāo)的同時(shí)優(yōu)化.可以得知，傳統(tǒng)的任務(wù)調(diào)度算法存在著對(duì)不同的任務(wù)類型適應(yīng)度低、搜索時(shí)間長(zhǎng)以及容易陷入局部最優(yōu)解等不足.

目前，機(jī)器學(xué)習(xí)已經(jīng)開(kāi)始被用于有效的解決任務(wù)調(diào)度這類組合優(yōu)化問(wèn)題[7-9].機(jī)器學(xué)習(xí)的研究最早從Samuel發(fā)明的下棋程序開(kāi)始，發(fā)展至今已經(jīng)被廣泛用于解決諸多領(lǐng)域的研究問(wèn)題，是指機(jī)器通過(guò)學(xué)習(xí)數(shù)據(jù)的內(nèi)在信息，獲得自身的經(jīng)驗(yàn)信息來(lái)指導(dǎo)其完成智能行為[10].強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)是建立在馬爾科夫決策過(guò)程(Markov Decision Process,MDP)上的一種重要的機(jī)器學(xué)習(xí)算法，它是指在無(wú)外界監(jiān)督指導(dǎo)的情況下通過(guò)與不確定的外部環(huán)境進(jìn)行交互，從而獲得最優(yōu)解的一種學(xué)習(xí)過(guò)程[11,12].經(jīng)典的RL算法包括Q-learning、SARSA和策略梯度(Policy Gradients)，其中，Q-learning算法在解決任務(wù)調(diào)度問(wèn)題上具有較好的效果.Q-learning算法是指通過(guò)引入期望延遲反饋來(lái)解決無(wú)完整信息的MDP問(wèn)題的一種方法，它不需要提前獲取環(huán)境模型，主體(Agent)是Q-learning中的一個(gè)重要組成元素，它可以根據(jù)歷史經(jīng)驗(yàn)來(lái)學(xué)習(xí)并且選擇一個(gè)最優(yōu)的動(dòng)作，最終被選擇的一系列動(dòng)作組成一個(gè)最優(yōu)策略[13].

Siar等[14]提出了一種將RL和智能技術(shù)結(jié)合的方法用于解決并行系統(tǒng)中的任務(wù)調(diào)度問(wèn)題，Agent通過(guò)Q-learning方法來(lái)學(xué)習(xí)如何將效率最大化，并且使用一種新的協(xié)作Q-learning算法來(lái)促進(jìn)Agent之間的交互，從而提高整個(gè)系統(tǒng)的效率.Cui 等[15]提出一種新的基于Q-learning的任務(wù)調(diào)度算法，在一定數(shù)量的虛擬機(jī)資源下最小化makespan和平均等待時(shí)間.Wei等[16]提出一種基于Q-learning和共享值函數(shù)的任務(wù)調(diào)度算法，以解決現(xiàn)有合作學(xué)習(xí)算法中信息頻繁交換的問(wèn)題，該算法設(shè)計(jì)了任務(wù)模型和Q-learning模型，在約束條件下降低了協(xié)作信息的切換頻率，具有良好的學(xué)習(xí)效果.

本文針對(duì)HEFT算法只適合解決小規(guī)模DAG任務(wù)的調(diào)度問(wèn)題以及只考慮了對(duì)單目標(biāo)makespan的優(yōu)化，提出一種基于Q-learning的多目標(biāo)任務(wù)調(diào)度算法(Multi-objective Task Scheduling Algorithm based onQ-learning，QMTS).在QMTS算法中，首先利用Q-learning算法指導(dǎo)任務(wù)進(jìn)行優(yōu)先級(jí)排序，其中使用HEFT算法的Upward Rank值(式(9))作為Q-learning更新過(guò)程中的立即獎(jiǎng)勵(lì)值，可以得到比HEFT算法更小的makespan；其次針對(duì)HEFT算法在處理機(jī)分配階段只考慮將任務(wù)的最早完成時(shí)間作為影響分配的因素，從而導(dǎo)致云服務(wù)提供商的消耗成本沒(méi)有得到有效的控制.本文使用線性加權(quán)法將最早完成時(shí)間和消耗成本綜合考慮作為虛擬機(jī)的分配依據(jù).實(shí)驗(yàn)結(jié)果表明，本文所提出的QMTS算法得到了比HEFT及其他經(jīng)典的調(diào)度算法更好的多目標(biāo)優(yōu)化結(jié)果.

2 問(wèn)題描述

2.1 云任務(wù)調(diào)度問(wèn)題

虛擬化是云計(jì)算中的核心，云計(jì)算平臺(tái)上的每個(gè)計(jì)算節(jié)點(diǎn)代表了具有不同處理能力的虛擬機(jī)，定義如下：

V={V1,V2,…,Vm}

(1)

在本文中，擬實(shí)現(xiàn)在云計(jì)算環(huán)境下任務(wù)之間有依賴關(guān)系的多目標(biāo)靜態(tài)任務(wù)調(diào)度算法，有依賴關(guān)系的任務(wù)類型通常使用DAG任務(wù)來(lái)表示，定義如下：

G=(T,E,C,W)

(2)

一個(gè)簡(jiǎn)單的DAG任務(wù)模型如圖1所示，圖中共有8個(gè)任務(wù)節(jié)點(diǎn)，每個(gè)任務(wù)節(jié)點(diǎn)由兩個(gè)部分組成：任務(wù)節(jié)點(diǎn)編號(hào)和該任務(wù)在所有虛擬機(jī)上的平均計(jì)算時(shí)間.任務(wù)圖中有向邊上的數(shù)值代表兩個(gè)任務(wù)之間的通信時(shí)間.

圖1 一個(gè)8個(gè)任務(wù)的簡(jiǎn)單DAG模型Fig.1 A simple DAG model with 8 tasks

2.2 優(yōu)化目標(biāo)模型

在本文中，擬實(shí)現(xiàn)同時(shí)減少任務(wù)的makespan和虛擬機(jī)消耗總成本的多目標(biāo)任務(wù)調(diào)度算法(QMTS).

2.2.1 makespan模型

在云環(huán)境下任務(wù)調(diào)度問(wèn)題的研究中，makespan一直是一個(gè)重要的評(píng)價(jià)指標(biāo).對(duì)于給定的任務(wù)集合，最后一個(gè)任務(wù)的完成時(shí)間即為整個(gè)任務(wù)調(diào)度的makespan結(jié)果.任務(wù)Ti在虛擬機(jī)Vk上的最早開(kāi)始執(zhí)行時(shí)間定義為：

(3)

其中：pred(Ti)是任務(wù)Ti的所有直接前驅(qū)任務(wù)節(jié)點(diǎn)的集合，F(xiàn)T(Tq)是任務(wù)Tq的完成時(shí)間；ST(Vk)是虛擬機(jī)Vk最早可開(kāi)始執(zhí)行任務(wù)Ti的時(shí)間.根據(jù)定義，DAG任務(wù)中入口任務(wù)的最早開(kāi)始執(zhí)行時(shí)間為0.

任務(wù)Ti在虛擬機(jī)Vk上的最早完成時(shí)間定義為：

EFT(Ti,Vk)=wi,k+EST(Ti,Vk)

(4)

可以得知，最后一個(gè)任務(wù)的最早完成時(shí)間即為整個(gè)DAG任務(wù)調(diào)度的makespan，表示為：

(5)

2.2.2 總成本模型

總成本(total cost)是指完成所有任務(wù)之后，在所有虛擬機(jī)上所耗費(fèi)成本的總和.定義如下：

(6)

其中：pricek是虛擬機(jī)Vk在計(jì)算單位時(shí)長(zhǎng)的任務(wù)上的執(zhí)行費(fèi)用.通常，計(jì)算速度越快的虛擬機(jī)所需的單位執(zhí)行費(fèi)用越高；timek是分配到虛擬機(jī)Vk上的任務(wù)的總執(zhí)行時(shí)長(zhǎng).對(duì)于pricek的定義有多種方式，如線性定價(jià)方式和指數(shù)定價(jià)方式[17]，本文給出一種定價(jià)方式如下所示：

(7)

式(7)的推導(dǎo)思路為：首先給出不同計(jì)算速度的虛擬機(jī)之間的單位執(zhí)行費(fèi)用的線性關(guān)系為pricek=priceh×(sk/sh),k=h+1≤m，這里將所有虛擬機(jī)按照計(jì)算速度從小到大進(jìn)行排序，priceh是虛擬機(jī)Vh的單位執(zhí)行費(fèi)用，sk和sh分別是虛擬機(jī)Vk和Vh的計(jì)算速度；其次由于在線性關(guān)系中不同虛擬機(jī)處理相同的任務(wù)實(shí)際上消耗的成本是相同的，因此引入相關(guān)的函數(shù)來(lái)解決這個(gè)問(wèn)題；最后考慮到在指數(shù)定價(jià)方式中虛擬機(jī)的計(jì)算速度加快時(shí)，其單位執(zhí)行費(fèi)用的增長(zhǎng)過(guò)快.于是引入對(duì)數(shù)函數(shù)來(lái)避開(kāi)現(xiàn)有的兩種定價(jià)方式的不足，由于虛擬機(jī)Vk的計(jì)算速度大于Vh，因此(sk/sh)>1，得到ln(sk/sh)>0，即1+ln(sk/sh)>1，使得虛擬機(jī)價(jià)格增加速度與對(duì)數(shù)函數(shù)相似，更符合實(shí)際生活中的定價(jià)模式.由此可知，單個(gè)任務(wù)Ti在虛擬機(jī)Vk上的執(zhí)行成本表示為：costTi=wi,k×pricek.

2.2.3 優(yōu)化目標(biāo)函數(shù)

本文提出的算法試圖對(duì)makespan和總成本(total cost)同時(shí)進(jìn)行優(yōu)化，可將目標(biāo)函數(shù)定義為：

min:{makespan,totalcost}
s.t.makespan≤makespanmin
totalcost≤totalcostmin

(8)

其中，makespanmin和totalcostmin分別是在本文其他3種對(duì)比算法中產(chǎn)生的最小的makespan結(jié)果和最小的總成本結(jié)果.

3 多目標(biāo)調(diào)度算法設(shè)計(jì)

本章結(jié)合HEFT算法與Q-learning算法提出了同時(shí)實(shí)現(xiàn)最小化makespan和總成本的多目標(biāo)任務(wù)調(diào)度算法QMTS，達(dá)到用戶體驗(yàn)最優(yōu)和云服務(wù)提供商總成本最小的目的.

3.1 HEFT算法

HEFT是靜態(tài)DAG任務(wù)調(diào)度中的經(jīng)典算法之一，對(duì)于減少整個(gè)任務(wù)執(zhí)行過(guò)程的makespan有著較好的表現(xiàn).算法在任務(wù)排序階段，使用Upward Rank值(式(9))作為任務(wù)優(yōu)先級(jí)值，充分考慮到了任務(wù)的計(jì)算時(shí)間、任務(wù)間的通信時(shí)間以及子任務(wù)的優(yōu)先級(jí)對(duì)父任務(wù)優(yōu)先級(jí)的影響；在分配處理機(jī)階段，HEFT算法使用最早完成時(shí)間策略(式(4))，即將每個(gè)任務(wù)都分配到能使其最早完成的處理機(jī)上執(zhí)行.

Upward Rank值的定義如下所示：

(9)

HEFT算法的執(zhí)行過(guò)程如圖2所示.

圖2 HEFT算法流程圖Fig.2 Flow chart of the HEFT algorithm

HEFT算法雖然在任務(wù)排序和處理機(jī)分配階段都有著較充分的考慮，但是由于其只依據(jù)Upward Rank值進(jìn)行了一次性的排序，導(dǎo)致在任務(wù)節(jié)點(diǎn)多且結(jié)構(gòu)較復(fù)雜的DAG任務(wù)上往往得不到合理的任務(wù)執(zhí)行順序，以至于在產(chǎn)生最優(yōu)makespan上的性能下降；并且在處理機(jī)分配階段只考慮了優(yōu)化單目標(biāo)makespan，沒(méi)有受到任務(wù)完成后處理機(jī)所消耗成本的約束，而在現(xiàn)實(shí)問(wèn)題中，成本也是很重要的考慮因素.

3.2 Q-learning算法

Q-learning是強(qiáng)化學(xué)習(xí)中經(jīng)典的無(wú)監(jiān)督、自學(xué)習(xí)方法，在學(xué)習(xí)過(guò)程中不需要外界環(huán)境對(duì)它進(jìn)行指導(dǎo)，依據(jù)與環(huán)境“試錯(cuò)”交互得到的歷史經(jīng)驗(yàn)來(lái)指導(dǎo)學(xué)習(xí)方向.Q-learning有五個(gè)重要組成部分：主體(Agent)、環(huán)境/狀態(tài)(s)、動(dòng)作(a)、獎(jiǎng)勵(lì)值(r)以及一個(gè)用于存儲(chǔ)Q值的Q表(Q-table).在進(jìn)行一次學(xué)習(xí)之前，首先將Q表初始化(一般初始化為0)，表的橫向和縱向分別代表動(dòng)作和狀態(tài)，表中元素即為Q值，表示為Q(s,a).在每一步的學(xué)習(xí)更新過(guò)程中，Agent通過(guò)隨機(jī)選擇一個(gè)可行動(dòng)作a從當(dāng)前狀態(tài)s轉(zhuǎn)移到下一個(gè)狀態(tài)s′，并且新的環(huán)境會(huì)反饋一個(gè)正的或者負(fù)的獎(jiǎng)勵(lì)值r給Agent用來(lái)更新Q值.Q-learning算法簡(jiǎn)化模型如圖3所示.

Q-learning算法的更新公式如下：

(10)

其中：Qt(s,a)表示更新前的Q值，Qt+1(s,a)表示更新后的Q值；(0 <≤ 1)是學(xué)習(xí)率(learning rate)，表示Agent在學(xué)習(xí)過(guò)程中對(duì)未來(lái)收益的重視程度.值越小，表示Agent越重視當(dāng)前已經(jīng)獲得的收益；反之，表示越重視遠(yuǎn)期獲得的收益；(0 <≤ 1)是折扣因子(discount rate)，表示對(duì)未來(lái)獎(jiǎng)勵(lì)值的重視程度，值越小表示越重視立即獎(jiǎng)勵(lì)；反之，表示越重視未來(lái)獎(jiǎng)勵(lì).

圖3 Q-learning算法簡(jiǎn)化模型Fig.3 Simplified model of Q-learning algorithm

3.3 QMTS算法設(shè)計(jì)

針對(duì)所要解決的任務(wù)調(diào)度中的makespan和總成本多目標(biāo)優(yōu)化問(wèn)題，本文將算法設(shè)計(jì)分為任務(wù)排序和虛擬機(jī)分配兩個(gè)主要階段，QMTS算法的偽代碼如算法1所示.

算法1.QMTS算法

輸入：DAG任務(wù)中的所有任務(wù).

輸出：makespan和總成本的結(jié)果.

初始化Q表的所有元素為0

初始化參數(shù)

計(jì)算立即獎(jiǎng)勵(lì)值r

repeatfor each episode

隨機(jī)選擇一個(gè)入口任務(wù)作為當(dāng)前任務(wù)Tcurrent

repeatfor each step of episode

隨機(jī)選擇一個(gè)合法任務(wù)(不包括已經(jīng)被選擇過(guò)的任務(wù))作為

下一個(gè)任務(wù)Tnext

根據(jù)式(10)更新Q(Tcurrent,Tnext)

TcurrentTnext

untilTnextisterminal

根據(jù)更新后的Q表獲得任務(wù)排序

根據(jù)式(11)給每個(gè)任務(wù)分配一個(gè)虛擬機(jī)

得到makespan和總成本結(jié)果

untilconvergence(makespan和總成本的結(jié)果不再改變)

3.3.1 任務(wù)排序階段

在本文中，使用Q-learning算法對(duì)任務(wù)進(jìn)行排序，將任務(wù)視為Q-learning中的狀態(tài)和動(dòng)作，從當(dāng)前任務(wù)到下一個(gè)任務(wù)的排序過(guò)程看作Agent在當(dāng)前狀態(tài)選擇一個(gè)可行動(dòng)作后轉(zhuǎn)移到下一個(gè)狀態(tài)的過(guò)程.在Q表的更新過(guò)程中，將每個(gè)任務(wù)的Upward Rank值作為該任務(wù)對(duì)應(yīng)狀態(tài)的立即獎(jiǎng)勵(lì)值，經(jīng)過(guò)一定次數(shù)的迭代，Q表最終會(huì)收斂到固定不變.根據(jù)收斂的Q表，使用最大Q值優(yōu)先原則對(duì)任務(wù)進(jìn)行排序，即每次都選擇符合DAG任務(wù)的依賴關(guān)系中的Q值最大的任務(wù)作為下一個(gè)執(zhí)行任務(wù)，直至所有任務(wù)都完成排序過(guò)程.由于Q-learning算法在尋優(yōu)問(wèn)題上具有很好的學(xué)習(xí)效果，上述排序方法可以得到一個(gè)比HEFT算法更加合理的任務(wù)執(zhí)行順序，從而產(chǎn)生更小的makespan.

3.3.2 虛擬機(jī)分配階段

在得到任務(wù)執(zhí)行順序之后，使用分配策略將每個(gè)任務(wù)映射到虛擬機(jī)上執(zhí)行.本文將任務(wù)在每個(gè)虛擬機(jī)上的最早完成時(shí)間和虛擬機(jī)的消耗成本通過(guò)線性加權(quán)的方式進(jìn)行綜合考慮，每次將任務(wù)分配到加權(quán)和最小的虛擬機(jī)上執(zhí)行，使得在產(chǎn)生更小的makespan的同時(shí)做到總成本的下降，具體公式定義如下所示：

(11)

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)概述及參數(shù)設(shè)置

本文中的所有實(shí)驗(yàn)都在云計(jì)算仿真平臺(tái)WorkflowSim上進(jìn)行[18].首先通過(guò)實(shí)驗(yàn)證明了在任務(wù)優(yōu)先級(jí)排序階段結(jié)合Q-learning算法對(duì)產(chǎn)生更小的makespan結(jié)果是有顯著效果的，這是由于在Q-learning算法中Agent的自我學(xué)習(xí)調(diào)節(jié)過(guò)程產(chǎn)生了一個(gè)更好的任務(wù)執(zhí)行順序；其次，根據(jù)式(11)中權(quán)重系數(shù)的變化，分析了其對(duì)makespan和總成本兩個(gè)目標(biāo)的影響；再次，分別測(cè)試了在不同虛擬機(jī)數(shù)量下4種算法的性能，得到QMTS算法性能最好；最后，對(duì)不同節(jié)點(diǎn)數(shù)量的DAG任務(wù)進(jìn)行實(shí)驗(yàn)，測(cè)試了QMTS算法在小任務(wù)圖和大任務(wù)圖上都有較好的表現(xiàn)，尤其是在處理規(guī)模較大的任務(wù)集時(shí)有著突出的性能優(yōu)勢(shì).

表1 實(shí)驗(yàn)參數(shù)設(shè)置
Table 1 Experimental parameter settings

4.2 基于Q-learning算法的任務(wù)排序?qū)嶒?yàn)

在云計(jì)算環(huán)境下的任務(wù)調(diào)度問(wèn)題中，如何以更加合理有效的順序?qū)⑷蝿?wù)提交給處理機(jī)執(zhí)行是調(diào)度器首先要解決的一個(gè)問(wèn)題，對(duì)虛擬機(jī)最終完成任務(wù)的makespan大小起著至關(guān)重要的影響.本文使用Q-learning算法對(duì)任務(wù)進(jìn)行優(yōu)先級(jí)排序，并且本實(shí)驗(yàn)在分配任務(wù)給虛擬機(jī)時(shí)使用與HEFT算法一致的分配方式，測(cè)試了在16和32個(gè)虛擬機(jī)數(shù)量下的makespan結(jié)果，并與文獻(xiàn)[5]中的基于Upward Rank的異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time based on Upward Rank，HEFT_U)算法、基于Downward Rank的異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time based on Downward Rank，HEFT_D)算法和處理器上的關(guān)鍵路徑(Critical Path on a Processor，CPOP)算法進(jìn)行比較.HEFT_U、HEFT_D和CPOP算法是經(jīng)典并且性能較好的靜態(tài)DAG任務(wù)調(diào)度算法，在優(yōu)化makespan上有著較好的表現(xiàn)，在很多靜態(tài)任務(wù)調(diào)度的研究中都被作為對(duì)比算法.

從圖4的實(shí)驗(yàn)結(jié)果可以得知，任務(wù)集在使用了Q-learning算法對(duì)其進(jìn)行執(zhí)行順序的排序后，得到了比其他3種算法更好的makespan結(jié)果，表明本文所提出的QMTS算法使用Q-learning算法對(duì)任務(wù)進(jìn)行優(yōu)先級(jí)排序?qū)τ跍p少makespan有著顯著的效果.

圖4 在16和32個(gè)虛擬機(jī)數(shù)量下的makespan結(jié)果Fig.4 Makespan with 16 and 32 virtual machines

4.3 權(quán)重系數(shù)實(shí)驗(yàn)

在對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行線性加權(quán)求解時(shí)，目標(biāo)函數(shù)中每個(gè)目標(biāo)對(duì)象所占的權(quán)重大小情況直接影響了目標(biāo)優(yōu)化結(jié)果的好壞.通常情況下，當(dāng)某個(gè)目標(biāo)所占的權(quán)重值越大，則表示該目標(biāo)越受重視，相應(yīng)的目標(biāo)函數(shù)會(huì)更偏向于對(duì)它的優(yōu)化，并可能會(huì)直接導(dǎo)致其他目標(biāo)產(chǎn)生不理想的結(jié)果.在本實(shí)驗(yàn)中，首先通過(guò)大量的實(shí)驗(yàn)，選取了在不同權(quán)重系數(shù)情況下兩個(gè)目標(biāo)的實(shí)驗(yàn)結(jié)果，權(quán)重變化對(duì)makespan和總成本的影響趨勢(shì)如圖5所示.

圖5 權(quán)重變化對(duì)makespan和總成本的影響Fig.5 Impact of weight changes on makespan and total cost

從圖5中可以得知，隨著EFT的權(quán)重從小到大(成本權(quán)重由大到小)的變化，makespan產(chǎn)生從大到小的變化趨勢(shì)，而總成本產(chǎn)生從小到大的變化趨勢(shì).可知，在對(duì)makespan和總成本同時(shí)進(jìn)行優(yōu)化時(shí)，如果對(duì)其中一個(gè)目標(biāo)賦予相對(duì)過(guò)大的權(quán)重，則另一個(gè)目標(biāo)會(huì)因此產(chǎn)生劣解，表明makespan和總成本是一對(duì)相沖突解.因此，在實(shí)驗(yàn)中需要選擇合適的權(quán)重組合對(duì)makespan和總成本進(jìn)行同時(shí)優(yōu)化.在本文中，首先根據(jù)makespan和總成本結(jié)果隨權(quán)重變化的大致趨勢(shì)將不可能達(dá)到雙目標(biāo)優(yōu)化目的，即會(huì)產(chǎn)生過(guò)差的單個(gè)目標(biāo)解的權(quán)重組合剔除掉，剩下的權(quán)重組合組成一個(gè)區(qū)間，然后對(duì)這個(gè)區(qū)間內(nèi)的權(quán)重組合進(jìn)行大量實(shí)驗(yàn)，最后找到相對(duì)最優(yōu)的多目標(biāo)實(shí)驗(yàn)結(jié)果.

4.4 Inspiral_100測(cè)試集實(shí)驗(yàn)

本實(shí)驗(yàn)使用Inspiral_100測(cè)試集分別在4種不同虛擬機(jī)數(shù)量下測(cè)試了QMTS算法對(duì)makespan和總成本同時(shí)進(jìn)行優(yōu)化的性能，并與其它3種經(jīng)典的任務(wù)調(diào)度算法進(jìn)行比較.

圖6(a)至圖6(d)分別是在4VM、8VM、16VM、32VM情況下四種算法優(yōu)化makespan和總成本的結(jié)果.圖中橫坐標(biāo)表示4種任務(wù)調(diào)度算法，左縱坐標(biāo)表示makespan結(jié)果，右縱坐標(biāo)表示總成本結(jié)果.從圖6可以得知，除了在32VM下，CPOP算法產(chǎn)生的總成本結(jié)果有略微的優(yōu)勢(shì)之外.在余下情況中，本文提出的QMTS算法都得到了比其他3種算法更小的makespan和總成本結(jié)果.這是因?yàn)椋菏紫?，QMTS算法在任務(wù)排序階段使用Q-learning算法找到了一個(gè)比其他3種算法更加合理的任務(wù)執(zhí)行順序，從而產(chǎn)生了比其他算法更小的makespan結(jié)果；其次，又在虛擬機(jī)分配階段綜合考慮了任務(wù)最早完成時(shí)間和虛擬機(jī)執(zhí)行成本兩個(gè)影響因素，避免了在虛擬機(jī)分配過(guò)程中只重視對(duì)makespan的減少而忽略了對(duì)總成本消耗的控制.

圖6 不同虛擬機(jī)數(shù)量下4種算法的makespan和總成本結(jié)果Fig.6 Makespan and total cost of four algorithms under different numbers of virtual machines

4.5 Inspiral_100測(cè)試集下不同任務(wù)數(shù)量實(shí)驗(yàn)

最后，本文還對(duì)其他任務(wù)數(shù)量不同的Inspiral測(cè)試集在32個(gè)虛擬機(jī)環(huán)境下進(jìn)行實(shí)驗(yàn)，表明QMTS算法在不同規(guī)模的DAG任務(wù)上的可擴(kuò)展性.不同任務(wù)數(shù)量下4種算法優(yōu)化makespan和總成本的結(jié)果如圖7所示.

圖7(a)和圖7(b)分別展示了在30、50、150、200以及300個(gè)任務(wù)數(shù)量下4種算法的makespan和總成本優(yōu)化結(jié)果，可以得知隨著任務(wù)數(shù)量的增多，相應(yīng)的makespan和總成本結(jié)果也隨之增大.在30和50個(gè)任務(wù)數(shù)量下，HEFT_D算法的總成本結(jié)果相對(duì)最好，其次是QMTS算法總成本結(jié)果優(yōu)于其他2種算法；但是QMTS算法的makespan結(jié)果遠(yuǎn)小于HEFT_D算法，并且和其他2種算法差不多，因此QMTS算法在小規(guī)模任務(wù)上對(duì)兩個(gè)目標(biāo)的優(yōu)化結(jié)果是最好的.在150～300個(gè)任務(wù)的規(guī)模較大的DAG任務(wù)上，隨著任務(wù)數(shù)量的增多，QMTS算法產(chǎn)生的makespan結(jié)果和總成本結(jié)果明顯小于其他算法，說(shuō)明QMTS算法隨著任務(wù)數(shù)量的增多，優(yōu)化性能越好.因此，本文提出的QMTS算法在不同規(guī)模的DAG任務(wù)上都能得到最好的makespan和總成本的多目標(biāo)優(yōu)化結(jié)果.但是由于Q-learning算法中的Q表在本文中是一個(gè)二維數(shù)組，隨著任務(wù)數(shù)量和虛擬機(jī)數(shù)量的增多，相應(yīng)的Q-learning中的狀態(tài)s和動(dòng)作a的數(shù)量也會(huì)增多，導(dǎo)致Q表空間增長(zhǎng)快速，內(nèi)存開(kāi)銷(xiāo)大；并且遍歷整張Q表需要的時(shí)間較長(zhǎng)，CPU計(jì)算速度隨之變慢.

圖7 不同任務(wù)數(shù)量下4種算法的makespan和總成本結(jié)果Fig.7 Makespan and total cost of four algorithms under different task numbers

5 結(jié) 語(yǔ)

本文針對(duì)在云計(jì)算環(huán)境下任務(wù)調(diào)度問(wèn)題中的兩個(gè)重要評(píng)價(jià)指標(biāo)：makespan和總成本，提出同時(shí)優(yōu)化這兩個(gè)目標(biāo)的基于Q-learning算法的靜態(tài)任務(wù)調(diào)度算法QMTS.該算法首先使用Q-learning算法對(duì)任務(wù)進(jìn)行優(yōu)先級(jí)排序，并將HEFT算法的Upward Rank值作為Q-learning更新過(guò)程中的立即獎(jiǎng)勵(lì)值，得到一個(gè)更加合理有效的任務(wù)執(zhí)行順序；待所有任務(wù)完成排序之后，任務(wù)依次進(jìn)入虛擬機(jī)分配階段，計(jì)算任務(wù)在每個(gè)虛擬機(jī)上的最早完成時(shí)間和執(zhí)行成本的線性加權(quán)和，并將任務(wù)分配給加權(quán)和最小的虛擬機(jī)執(zhí)行.實(shí)驗(yàn)結(jié)果表明，QMTS算法在任務(wù)調(diào)度的多目標(biāo)優(yōu)化問(wèn)題上性能有著突出的表現(xiàn)，說(shuō)明該算法是有效的.在以后的工作中，我們將考慮使用深度神經(jīng)網(wǎng)絡(luò)擬合Q值的方法解決在Q-learning算法更新過(guò)程中Q表過(guò)大導(dǎo)致收斂過(guò)慢的問(wèn)題；并且在優(yōu)化makespan和總成本兩個(gè)目標(biāo)的基礎(chǔ)上考慮對(duì)其他有重要價(jià)值意義的目標(biāo)進(jìn)行優(yōu)化.