面向分布式環(huán)境的信號(hào)驅(qū)動(dòng)任務(wù)調(diào)度算法

辛宇，楊靜，謝志強(qiáng)

（1. 哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；2. 哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001）

1 引言

隨著云計(jì)算技術(shù)的迅猛發(fā)展，云計(jì)算技術(shù)可將計(jì)算、存儲(chǔ)、軟件、服務(wù)等資源從分散的個(gè)人計(jì)算機(jī)或服務(wù)器移植到互聯(lián)網(wǎng)環(huán)境中，以集中管理大規(guī)模高性能計(jì)算機(jī)、個(gè)人計(jì)算機(jī)、虛擬計(jì)算機(jī)，從而方便用戶使用云資源。從層次上云計(jì)算平臺(tái)可以分為以下3種服務(wù)模型：軟件即服務(wù)(SaaS, software as a service)，平臺(tái)即服務(wù)(PaaS, platform as a service)，基礎(chǔ)架構(gòu)即服務(wù)(IaaS, infrastructure as a service)。

目前 IaaS模型是當(dāng)前最重要的云平臺(tái)模型，IaaS的意義在于，用戶可通過(guò)云接口利用IaaS云服務(wù)提供商所提供的 IT設(shè)備資源運(yùn)行所需應(yīng)用，且無(wú)需考慮硬件的維護(hù)及更新[1]。IaaS的技術(shù)核心是硬件虛擬化，通過(guò)利用虛擬化技術(shù)，把物理主機(jī)的各種硬件整合起來(lái)，屏蔽其硬件的物理細(xì)節(jié)，以資源池的概念統(tǒng)一代表物理硬件，保證資源的可定制能力和統(tǒng)一分配能力[2]。目前，有很多企業(yè)和科研機(jī)構(gòu)推出了自己的IaaS云計(jì)算平臺(tái)，面向用戶提供計(jì)算資源和存儲(chǔ)資源。最具代表性的是亞馬遜(Amazon)的彈性計(jì)算云(EC2, elastic compute cloud)[3]，它通過(guò)Web服務(wù)的方式讓用戶彈性地運(yùn)行自己的Amazon機(jī)器映像，用戶可以在自己申請(qǐng)的虛擬機(jī)鏡像上運(yùn)行任何自己所需的軟件或應(yīng)用程序。同時(shí)，還有一些開(kāi)源 IaaS云計(jì)算平臺(tái)：與EC2兼容的云平臺(tái)Eucalyptus (elastic utility computing architecture for linking your programs to useful systems)[4]，美國(guó)國(guó)家航空航天局和Rackspace合作研發(fā)的OpenStack[5]以及中科院的LingCloud[6]等。

IaaS通過(guò)虛擬設(shè)備實(shí)現(xiàn)用戶的服務(wù)，IaaS在進(jìn)行虛擬設(shè)備管理時(shí)，將一臺(tái)物理設(shè)備劃分為多臺(tái)獨(dú)立的虛擬設(shè)備，各個(gè)虛擬設(shè)備之間能進(jìn)行有效的資源隔離和數(shù)據(jù)隔離；由于多個(gè)虛擬設(shè)備共同享一臺(tái)物理設(shè)備的物理資源，能夠充分復(fù)用物理設(shè)備的計(jì)算資源，提高資源利用率。IaaS將云環(huán)境中的所有物理設(shè)備資源轉(zhuǎn)化為對(duì)用戶透明的統(tǒng)一資源池，并能按照用戶需求分配不同性能的虛擬設(shè)備。IaaS模型的框架體系如圖1所示，其中用戶的服務(wù)請(qǐng)求通過(guò)Scheduler模型進(jìn)行虛擬設(shè)備的任務(wù)分配。

圖1 IaaS的拓?fù)浣Y(jié)構(gòu)

為提高資源分配及數(shù)據(jù)處理的效率，近些年來(lái)面向IaaS的虛擬設(shè)備資源調(diào)度問(wèn)題逐漸成為學(xué)術(shù)研究的重點(diǎn)，其研究?jī)?nèi)容主要包括任務(wù)分配調(diào)度和數(shù)據(jù)傳輸調(diào)度。在任務(wù)分配調(diào)度方面，主要研究?jī)?nèi)容是處理用戶的任務(wù)分解及分配，對(duì)此Marcos等對(duì)IaaS模型的調(diào)度模塊設(shè)計(jì)了6種面向彈性計(jì)算云(EC2)的兼容策略，并提出了 cloud schedule和sub-schedule兩級(jí)調(diào)度模式，分別從宏觀和微觀角度進(jìn)行任務(wù)分配優(yōu)化[7,8]；在數(shù)據(jù)傳輸調(diào)度方面，主要研究?jī)?nèi)容是根據(jù)數(shù)據(jù)的分布式存儲(chǔ)特性建立以通信損耗化及數(shù)據(jù)時(shí)效優(yōu)化的調(diào)度策略，對(duì)此Nan等[9]提出了cost model及queuing model模型，構(gòu)建了多媒體數(shù)據(jù)的傳播評(píng)價(jià)方法，并設(shè)計(jì)了以多媒體數(shù)據(jù)傳輸QoS優(yōu)化為導(dǎo)向的云資源分布調(diào)度算法，Kllapi等[10]建立了流式數(shù)據(jù)的 split、compute和 merge過(guò)程，實(shí)現(xiàn)了分布式數(shù)據(jù)流的傳輸調(diào)度。為統(tǒng)一IaaS分配和數(shù)據(jù)傳輸?shù)恼{(diào)度模型，Lin等[11]根據(jù)虛擬機(jī)的處理能力及網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力，將功能和位置相近的虛擬機(jī)劃歸為cluster單元，從而將IaaS模型的調(diào)度問(wèn)題轉(zhuǎn)化為DAG(directed acyclic graph)調(diào)度優(yōu)化問(wèn)題，統(tǒng)一了IaaS任務(wù)調(diào)度模型。

目前可面向IaaS模型的DAG調(diào)度算法主要分為以下5類。

1) 權(quán)值選擇算法。如HEFT[12]、ACPM算法[13]等，此類算法是早期DAG調(diào)度的主要算法，其實(shí)現(xiàn)原理是根據(jù)DAG的結(jié)構(gòu)關(guān)系預(yù)先計(jì)算各個(gè)任務(wù)分片的EFT(earliest finish time)，以確定任務(wù)分片的先后關(guān)系。

2) 層次優(yōu)先選擇算法。如 PCH(path clustering heuristic)[14]、優(yōu)先工序集調(diào)度[15]等，此類算法以最大化同一層任務(wù)分片的并行處理為手段，將任務(wù)分片的層數(shù)作為優(yōu)先級(jí)，以確定任務(wù)分片的調(diào)度次序。

3) 堆棧式回退算法。如 HEFT-lookahead[16]、回退搶占算法[17]等，此類算法考慮了后續(xù)調(diào)度中空閑時(shí)段被占用的情況，當(dāng)出現(xiàn)預(yù)先計(jì)算的EFT與實(shí)際的結(jié)束時(shí)間偏差較大時(shí)，采用重定向的方式回退前續(xù)調(diào)度任務(wù)分片。

4) 路徑聚合算法。如HH(hybrid heuristic)[18]、動(dòng)態(tài)關(guān)鍵路徑法[19]等，此類算法考慮優(yōu)先調(diào)度關(guān)鍵路徑上的任務(wù)分片，增加關(guān)鍵路徑上任務(wù)分片的優(yōu)先級(jí)，從縱向角度優(yōu)化調(diào)度結(jié)果。

5) 啟發(fā)式優(yōu)化算法。如遺傳算法[20]，粒子群算法[21,22]等，此類算法通過(guò)建立代價(jià)函數(shù)對(duì)調(diào)度結(jié)果進(jìn)行局部?jī)?yōu)化，建立并利用循環(huán)選擇策略逐步保留局部?jī)?yōu)化結(jié)果，從而實(shí)現(xiàn)全局調(diào)度優(yōu)化。

為實(shí)現(xiàn)高效處理用戶IaaS任務(wù)請(qǐng)求，本文設(shè)計(jì)了一種基于信號(hào)驅(qū)動(dòng)的DAG調(diào)度算法，由于采用了信號(hào)驅(qū)動(dòng)的形式，可使算法結(jié)合權(quán)值選擇算法、層次優(yōu)先選擇算法和路徑聚合算法的特點(diǎn)，即在每一調(diào)度時(shí)刻根據(jù)任務(wù)分片的縱向權(quán)值進(jìn)行橫向并行優(yōu)化選擇，從而實(shí)現(xiàn)了DAG任務(wù)分片的縱橫雙向篩選，使調(diào)度過(guò)程更加合理化。另外，該算法由于回避了堆棧式回退算法的重定向操作，以及層次優(yōu)先選擇算法和路徑聚合算法的預(yù)調(diào)度操作，因此，算法的復(fù)雜度較低(約為O(nlog(n)))且優(yōu)于傳統(tǒng)DAG調(diào)度算法，更適于應(yīng)對(duì)云計(jì)算環(huán)境中的海量任務(wù)請(qǐng)求問(wèn)題。

2 IaaS模型的DAG調(diào)度問(wèn)題分析

根據(jù) IaaS模型的分布式特性和虛擬設(shè)備的異構(gòu)特性，IaaS任務(wù)以分片的形式進(jìn)行調(diào)度且各任務(wù)分片之間滿足以下約束[7,20,21]。

1) IaaS任務(wù)具有唯一的起始任務(wù)分片（DAG入口節(jié)點(diǎn)）和唯一的終止任務(wù)分片（DAG出口節(jié)點(diǎn)）。

2) 某一任務(wù)分片僅在滿足其要求的虛擬設(shè)備中執(zhí)行，且滿足同一任務(wù)分片要求的虛擬設(shè)備不唯一，任務(wù)分片在各虛擬設(shè)備中的執(zhí)行時(shí)間已知。

3) 任一虛擬設(shè)備在同一時(shí)刻只能執(zhí)行同一任務(wù)的一個(gè)任務(wù)分片。

4) 任務(wù)分片vi的緊后任務(wù)分片vj需要等待vi執(zhí)行完畢后的通信數(shù)據(jù)，若vi與vj在同一虛擬設(shè)備中執(zhí)行，則通信時(shí)間為0。

5) 每一任務(wù)分片必須在其前任務(wù)分片均執(zhí)行完畢，并收集到所有前序任務(wù)分片的通信數(shù)據(jù)時(shí)才可開(kāi)始執(zhí)行。

可根據(jù)IaaS模型的任務(wù)約束建立DAG調(diào)度模型，其符號(hào)描述如下。

1) DAG模型以圖G=(V,E)表示，G表示某一任務(wù)，V={v1,v2, …,vn}表示任務(wù)G的任務(wù)分片集合，其中n=|V|為任務(wù)分片的個(gè)數(shù)。

2)D={d1,d2, …,dm}表示虛擬設(shè)備的集合，其中m=|D|表示IaaS模型中虛擬設(shè)備的個(gè)數(shù)。

3)ci,j表示虛擬設(shè)備di到虛擬設(shè)備dj的通信代價(jià)。

圖2為某任務(wù)的DAG結(jié)構(gòu)模型，其中節(jié)點(diǎn)表示任務(wù)分片，節(jié)點(diǎn)1和節(jié)點(diǎn)8為起始任務(wù)分片和終止任務(wù)分片，有向邊表示任務(wù)分片的有序關(guān)系，其權(quán)值代表任務(wù)分片間的通信代價(jià)，表1為任務(wù)分片在各虛擬設(shè)備中的執(zhí)行時(shí)間。

圖2 DAG結(jié)構(gòu)模型

表1 任務(wù)分片執(zhí)行時(shí)間

3 IaaS調(diào)度系統(tǒng)設(shè)計(jì)

3.1 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)

定義1任務(wù)完畢信號(hào)(Sig_F)：NS在任務(wù)分片執(zhí)行完畢時(shí)向CS發(fā)送的反饋信號(hào)。

定義2數(shù)據(jù)傳遞信號(hào)(Sig_T)：CS在分配任務(wù)分片時(shí)向NS發(fā)送的通知信號(hào)，該信號(hào)包含通信數(shù)據(jù)的源虛擬設(shè)備ID和目標(biāo)虛擬設(shè)備ID。

定義 3任務(wù)分配信號(hào)(Sig_A)：CS在分配任務(wù)分片時(shí)向NS發(fā)送的通知信號(hào)，該信號(hào)包含被分配的任務(wù)分片ID及虛擬設(shè)備ID。

定義 4就緒信號(hào)(Sig_R)：NS在某一任務(wù)分片集齊所有所需的通信數(shù)據(jù)時(shí)向CS發(fā)送的信號(hào)。

圖3為CS和NS的信號(hào)交互過(guò)程示例，圖中CS包含了3個(gè)任務(wù)分片(vi,vj,vk)，NS包含了3個(gè)虛擬設(shè)備(d1,d2,d3)，vi、vj、vk分別在d1、d3、d2中執(zhí)行，實(shí)箭頭和虛箭頭分別表示信號(hào)交互和數(shù)據(jù)傳遞，序號(hào)標(biāo)識(shí)了CS與NS的信號(hào)先后次序，分別表示為：①任務(wù)分片vj在d3中執(zhí)行完畢時(shí)，NS向CS反饋信號(hào)；②任務(wù)分片vi在d1中執(zhí)行完畢時(shí)，NS向CS反饋信號(hào)；③CS通知d1和d3向d2傳遞數(shù)據(jù)；④NS內(nèi)部的數(shù)據(jù)傳遞；⑤d2在集齊所需的數(shù)據(jù)時(shí)向CS反饋信號(hào)；⑥CS通知NS在d2中執(zhí)行vk；⑦任務(wù)分片vk在d2中執(zhí)行完畢時(shí)，NS向 CS反饋信號(hào)。

3.2 系統(tǒng)狀態(tài)分析

每一任務(wù)分片的運(yùn)行過(guò)程中均會(huì)經(jīng)歷 4種狀態(tài)，各狀態(tài)的定義如下。

定義 5接收數(shù)據(jù)狀態(tài)：某一任務(wù)分片的任一緊前任務(wù)分片執(zhí)行完畢時(shí)所處的狀態(tài)。

圖3 CS和NS信號(hào)交互

定義 6就緒狀態(tài)：某一任務(wù)分片在接集齊所有所需的通信數(shù)據(jù)時(shí)所處的狀態(tài)。

定義 7執(zhí)行狀態(tài)：某一任務(wù)分片在開(kāi)始執(zhí)行時(shí)所處的狀態(tài)。

定義 8完畢狀態(tài)：某一任務(wù)分片執(zhí)行完畢時(shí)所處的狀態(tài)。

虛擬設(shè)備會(huì)經(jīng)歷2種狀態(tài)，其定義如下。

定義 9忙碌狀態(tài)：某一虛擬設(shè)備執(zhí)行任務(wù)分片時(shí)所處的狀態(tài)。

定義10空閑狀態(tài)：某一虛擬設(shè)備無(wú)任務(wù)分片執(zhí)行時(shí)所處的狀態(tài)。

圖4為任務(wù)分片和虛擬設(shè)備的狀態(tài)變化示例，該示例直觀表示了任務(wù)分片和虛擬設(shè)備在運(yùn)行過(guò)程中的狀態(tài)變化關(guān)系，圖中右(左)側(cè)虛框表示某一任務(wù)分片vi在某一虛擬設(shè)備dj中執(zhí)行(完畢)時(shí)，vi和dj的狀態(tài)同時(shí)變化。其中，信號(hào)起到信息傳遞及驅(qū)動(dòng)狀態(tài)轉(zhuǎn)化的作用。

3.3 調(diào)度系統(tǒng)優(yōu)化分析

由于各任務(wù)分片的執(zhí)行時(shí)間和各虛擬設(shè)備的數(shù)據(jù)傳遞時(shí)間均為已知，因此任務(wù)的尋優(yōu)過(guò)程是靜態(tài)過(guò)程，可向所有的虛擬設(shè)備發(fā)送Sig_A作尋優(yōu)假設(shè)，具體的優(yōu)化方案如下。

1) 當(dāng)某一任務(wù)分片vi的任一緊前任務(wù)分片執(zhí)行完畢時(shí)(此時(shí)變?yōu)榻邮諗?shù)據(jù)狀態(tài))，CS向NS發(fā)送m個(gè)不同目標(biāo)虛擬設(shè)備ID的信號(hào)Sig_T，為vi預(yù)分配所有m個(gè)虛擬設(shè)備。

2) CS建立任務(wù)分片就緒表(RT)，記錄任務(wù)分片在不同虛擬設(shè)備中變?yōu)榫途w狀態(tài)的時(shí)刻。

3) NS建立虛擬設(shè)備空閑表(DT)，記錄任一虛擬設(shè)備下一次變?yōu)榭臻e狀態(tài)的時(shí)刻。

4) 由于RT和DT會(huì)隨CS和NS的狀態(tài)變化而變化，當(dāng)RT或DT發(fā)生變化時(shí)利用current記錄當(dāng)前時(shí)刻，并利用下一節(jié)描述的并行優(yōu)化選擇策略進(jìn)行任務(wù)分片的選擇。

圖4 任務(wù)分片和虛擬設(shè)備的狀態(tài)轉(zhuǎn)化

4 并行優(yōu)化選擇策略

任務(wù)分片的執(zhí)行需具備 2個(gè)條件：1) 任務(wù)分片處于就緒狀態(tài)；2) 虛擬設(shè)備處于空閑狀態(tài)。為此本文所提出的并行優(yōu)化選擇策略以RT或DT的更新作為一次任務(wù)分片分配的時(shí)刻，為處于就緒狀態(tài)的任務(wù)分片分配空閑虛擬設(shè)備，將該時(shí)刻定義為調(diào)度時(shí)刻。

由于當(dāng)某一任務(wù)分片變?yōu)榻邮諗?shù)據(jù)狀態(tài)時(shí)，CS會(huì)向NS中所有的虛擬設(shè)備發(fā)送Sig_A，因此當(dāng)調(diào)度時(shí)刻來(lái)臨時(shí)，就緒的任務(wù)分片與空閑的虛擬設(shè)備間會(huì)存在多對(duì)多的關(guān)系，為實(shí)現(xiàn)任務(wù)分片與虛擬設(shè)備的一對(duì)一執(zhí)行關(guān)系，本文在調(diào)度時(shí)刻利用如下策略為空閑的虛擬設(shè)備分配執(zhí)行任務(wù)。

1) 利用 HEFT算法[12]計(jì)算就緒任務(wù)分片的rank值，rank值最大者優(yōu)先選擇空閑虛擬設(shè)備，HEFT的計(jì)算公式為

其中，succ(vi)為任務(wù)分片vi的緊后任務(wù)分片的集合，wi為vi在各虛擬設(shè)備中執(zhí)行時(shí)間的均值，當(dāng)vi為終止任務(wù)分片時(shí)ranki=wi，表2為圖2實(shí)例的rank值。

表2 圖2示例的rank值

2) 計(jì)算就緒任務(wù)分片在每個(gè)虛擬設(shè)備的執(zhí)行完畢時(shí)刻，選擇執(zhí)行完畢時(shí)刻最小者作為該任務(wù)分片的執(zhí)行虛擬設(shè)備。

3) RT和DT中的最小值為下一個(gè)調(diào)度時(shí)刻。

表3記錄了圖2示例的調(diào)度優(yōu)化過(guò)程，表中各行記錄了各調(diào)度時(shí)刻RT與DT的變化過(guò)程，2列和3列為調(diào)度之前RT與DT的內(nèi)容，4列和5列為調(diào)度之后RT與DT的內(nèi)容，第6列為預(yù)算出的下一調(diào)度時(shí)刻，如2列和3行可表示為：當(dāng)current為17 時(shí)，d1、d2、d3均空閑且v2、v3、v4、v5均只能在d1中執(zhí)行，此時(shí)利用優(yōu)化選擇策略選擇在d1中執(zhí)行v2，RT和DT中的最小值為30，即為下一個(gè)調(diào)度時(shí)刻；當(dāng)current為30時(shí)，僅d2,d3空閑且v3和v5只能在d1中執(zhí)行，因此無(wú)法調(diào)度v3和v5，又由于此時(shí)v4可在d2,d3中執(zhí)行，此時(shí)利用優(yōu)化選擇策略選擇在d2中執(zhí)行v4，并計(jì)算下一調(diào)度時(shí)刻為33。在RT表格中R表示在當(dāng)前時(shí)刻任務(wù)分片vi可在dj中執(zhí)行，即dj在當(dāng)前時(shí)刻已集齊了vi所需的數(shù)據(jù)，DT記錄了虛擬設(shè)備所執(zhí)行的任務(wù)分片及執(zhí)行結(jié)束時(shí)間。任務(wù)分片的調(diào)度結(jié)果如圖5所示。

5 算法設(shè)計(jì)及復(fù)雜性分析

5.1 調(diào)度算法設(shè)計(jì)

通過(guò)以上分析，在以下2種情況發(fā)生的時(shí)刻，可作為調(diào)度時(shí)刻：①NS在任務(wù)分片執(zhí)行完畢時(shí)，通過(guò)改變DT內(nèi)容的同時(shí)驅(qū)動(dòng)CS改變RT的內(nèi)容；②當(dāng)某一任務(wù)分片變?yōu)榫途w狀態(tài)時(shí)，CS改變RT的內(nèi)容。本節(jié)通過(guò)分析CS和NS內(nèi)部運(yùn)行機(jī)制，從全局角度設(shè)計(jì)調(diào)度算法。

1) 信號(hào)設(shè)計(jì)。根據(jù)CS和NS的運(yùn)行機(jī)制，設(shè)計(jì)了信號(hào)Sig_A、Sig_T、Sig_R和Sig_F進(jìn)行數(shù)據(jù)通信與執(zhí)行任務(wù)分片的交互，其中，Sig_T和Sig_R用于數(shù)據(jù)通信的交互，Sig_A和Sig_F用于執(zhí)行任務(wù)分片的交互，4種信號(hào)的說(shuō)明如表4所示。

2) NS內(nèi)部運(yùn)行算法。

①NS等待CS傳來(lái)的信號(hào)；

②若CS傳來(lái)的信號(hào)為信號(hào)Sig_T則轉(zhuǎn)③，若為信號(hào)Sig_A則轉(zhuǎn)④；

③此時(shí)說(shuō)明CS需求Sig_T->D_ID接受數(shù)據(jù)，NS驅(qū)動(dòng)虛擬設(shè)備Sig_T->S_ID向虛擬設(shè)備D_ID傳遞數(shù)據(jù)，并轉(zhuǎn)⑤；

④此時(shí)說(shuō)明CS需求Sig_T->D_ID執(zhí)行任務(wù)分片，任務(wù)分片Sig_A->partition在Sig_A->DB_ID中執(zhí)行，轉(zhuǎn)⑥；

⑤當(dāng)任務(wù)分片vi在虛擬設(shè)備dj中變?yōu)榫途w狀態(tài)時(shí)(即此時(shí)dj已接收到所有所需的數(shù)據(jù))，向 CS反饋信號(hào)Sig_R(Sig_R-> partition=vi, Sig_R->DB_ID=dj)，此時(shí)利用Sig_R向CS報(bào)告虛擬設(shè)備dj可執(zhí)行調(diào)度任務(wù)，轉(zhuǎn)①；

⑥當(dāng)任務(wù)分片vi在虛擬設(shè)備dj中執(zhí)行完畢時(shí)，向CS反饋信號(hào)Sig_F(Sig_F->partition=vi，Sig_F->DB_ID=dj)并更新DT，若vi為終止任務(wù)分片則轉(zhuǎn)⑦否則轉(zhuǎn)①；

⑦結(jié)束。

表3 圖2示例的rank值

圖5 圖2示例的調(diào)度結(jié)果

表4 信號(hào)說(shuō)明

3) CS內(nèi)部運(yùn)行算法。CS內(nèi)部在RT和DT的內(nèi)容變化時(shí)(收到Sig_R或Sig_F時(shí))，利用并行優(yōu)化選擇策略對(duì)就緒任務(wù)分片進(jìn)行分配，其運(yùn)行機(jī)制如下：

①等待NS傳來(lái)的信號(hào)；

②若為Sig_F則轉(zhuǎn)⑥，若為信號(hào)Sig_R轉(zhuǎn)③；

③根據(jù)Sig_R->partition和Sig_R->DB_ID更新RT；

④利用并行優(yōu)化選擇策略對(duì)處于就緒狀態(tài)的任務(wù)分片進(jìn)行調(diào)度；

⑤任務(wù)分片vi在虛擬設(shè)備dj中執(zhí)行，向NS反饋信號(hào) Sig_A(Sig_A->partition=vi，Sig_A-> DB_ID=dj)，驅(qū)動(dòng)NS執(zhí)行任務(wù)vi，若vi為終止任務(wù)分片則轉(zhuǎn)⑦否則轉(zhuǎn)①；

⑥向NS反饋信號(hào)Sig_T(Sig_T->S_ID =Sig_F->DB_ID，Sig_A-> DB_ID=所有虛擬設(shè)備ID)，對(duì)執(zhí)行完畢的任務(wù)進(jìn)行后續(xù)執(zhí)行的數(shù)據(jù)傳遞，轉(zhuǎn)①；

⑦結(jié)束。

圖6為CS與NS算法流程。其中，實(shí)線表示單一任務(wù)分片的運(yùn)行過(guò)程，虛線表示多個(gè)任務(wù)分片的實(shí)時(shí)等待過(guò)程。

5.2 復(fù)雜度分析

本算法的復(fù)雜之處在于某一調(diào)度時(shí)刻到來(lái)時(shí)，利用并行優(yōu)化選擇策略，實(shí)現(xiàn)任務(wù)分片與虛擬設(shè)備一對(duì)一的選擇，設(shè)任務(wù)分片總數(shù)為n，虛擬設(shè)備總數(shù)為m，總體復(fù)雜度分析如下。

1) NS算法復(fù)雜度分析

NS只接收信號(hào)Sig_T和Sig_A，在調(diào)度過(guò)程中CS為每一任務(wù)分片發(fā)送m個(gè)信號(hào)Sig_T和1個(gè)信號(hào) Sig_A，NS共需處理n(m+1)個(gè)信號(hào)，且 Sig_T和Sig_A的處理過(guò)程僅為常數(shù)復(fù)雜度，因此NS的復(fù)雜度為O(mn)。

2) CS算法復(fù)雜度分析

① 根據(jù)文獻(xiàn)[12]計(jì)算每個(gè)任務(wù)分片rank值的時(shí)間復(fù)雜度為O(mn)；

圖6 CS與NS算法流程

②n個(gè)任務(wù)分片按rank值進(jìn)行排序的時(shí)間復(fù)雜度為O(nlog(n))；

③ 每一調(diào)度時(shí)刻，處于空閑狀態(tài)的虛擬設(shè)備個(gè)數(shù)最大為m，因此，就緒任務(wù)分片對(duì)虛擬設(shè)備的選擇次數(shù)據(jù)最大為m，總選擇次數(shù)為mn，其時(shí)間復(fù)雜度為O(mn)。

綜上所述，本文算法的時(shí)間復(fù)雜度為O(mn+nlog(n))，由于在現(xiàn)實(shí)環(huán)境下虛擬設(shè)備總數(shù)為較小的常數(shù)，因此本文算法的復(fù)雜度可近似為O(nlog(n))，文獻(xiàn)[12～19]的復(fù)雜度分別為O(n2)、O(n2log(n))、O(n2log(n))、O(n2log(n))、O(n3)、O(n2log(n))、O(n2log(n))、O(n3)均高于本文算法。

6 實(shí)驗(yàn)分析

為驗(yàn)證本文算法的有效性，本實(shí)驗(yàn)以文獻(xiàn)[23]的DAG數(shù)據(jù)NSL(normalized schedule length)為標(biāo)準(zhǔn)隨機(jī)生成任務(wù)，以模擬IaaS云計(jì)算平臺(tái)的DAG任務(wù)分片結(jié)構(gòu)，并以 HEFT[12]、PCH[14]、HEFT-lookahead[16]和HH算法[18]作為對(duì)比算法（本文算法用 SD表示）。本實(shí)驗(yàn)平臺(tái)軟件：Win7 32位，Matlab2012；硬件：intel i3處理器，4 GB內(nèi)存，所設(shè)計(jì)的4組實(shí)驗(yàn)如下。

1) 資源占用時(shí)間分析實(shí)驗(yàn)。本組實(shí)驗(yàn)通過(guò)計(jì)算100組隨機(jī)任務(wù)的調(diào)度結(jié)果，分析任務(wù)對(duì)虛擬設(shè)備的占用時(shí)間

其中，makespanvi為任務(wù)分片vi的執(zhí)行時(shí)間，makespan越小說(shuō)明運(yùn)行結(jié)果對(duì)虛擬設(shè)備的占用率越低，算法有效性越高。由于100組隨機(jī)任務(wù)的結(jié)構(gòu)差異較大，為直觀顯示實(shí)現(xiàn)各算法的對(duì)比結(jié)果，分別按各算法的makespan對(duì)100組結(jié)果進(jìn)行排序，其結(jié)果如圖7所示，該圖分別以各算法為視角，對(duì)比各算法的資源占用時(shí)間，其中曲線越靠近底部說(shuō)明算法有效性越高，從圖7可直觀看出，在資源占用時(shí)間方面 lookahead和本文算法優(yōu)于其他算法且HEFT算法的效果最差。為消除各組隨機(jī)任務(wù)的結(jié)構(gòu)差異，本實(shí)驗(yàn)采用對(duì)每組結(jié)果進(jìn)行[0,1]區(qū)間映射的方法整理各組數(shù)據(jù)，并以各算法結(jié)果之和作為各算法的數(shù)值評(píng)價(jià)，本實(shí)驗(yàn)中各算法的計(jì)算結(jié)果分別為：84.54，76.00，18.09，60.32，10.99，數(shù)值越小表示算法有效性越高，因此在本實(shí)驗(yàn)中各算法的有效性排序?yàn)椋篠D（本文算法）、lookahead、PCH、HH、HEFT。

圖7 資源占用時(shí)間對(duì)比

圖8 總執(zhí)行時(shí)間對(duì)比

2) 任務(wù)總執(zhí)行時(shí)間分析。本實(shí)驗(yàn)以實(shí)驗(yàn)1的結(jié)果為數(shù)據(jù)集分析各算法的執(zhí)行時(shí)間，其執(zhí)行時(shí)間越短，說(shuō)明調(diào)度算法的有效性越高，本實(shí)驗(yàn)采用與實(shí)驗(yàn) 1相同的方式，分別按各算法的執(zhí)行時(shí)間對(duì)100組結(jié)果進(jìn)行排序，其結(jié)果如圖8所示，其中曲線越靠近底部說(shuō)明算法有效性越高，從圖8中可直觀看出，HEFT算法的效果最差，其他算法性能相近。本實(shí)驗(yàn)采用實(shí)驗(yàn)1的[0,1]區(qū)間映射求和方法進(jìn)行計(jì)算，結(jié)果分別為：96.57，31.59，21.98，34.63，23.39，其中數(shù)值越小表示算法有效性越高，因此各算法的有效性排序?yàn)椋簂ookahead、SD、HH、PCH、HEFT。

3) CCR(communication computation ratios)分析實(shí)驗(yàn)。CCR分析的目的在于通過(guò)改變隨機(jī)任務(wù)的通信時(shí)間以驗(yàn)證調(diào)度算法的穩(wěn)定性，本實(shí)驗(yàn)以[5,25]為隨機(jī)區(qū)間生成各任務(wù)分片的執(zhí)行時(shí)間，以[6,26]CCR(CCR=0.5～3)為隨機(jī)區(qū)間生成通信時(shí)間，創(chuàng)建6組DAG任務(wù)樣本(每組100個(gè)樣本)作為實(shí)驗(yàn)數(shù)據(jù)。圖9為各算法在執(zhí)行6組數(shù)據(jù)后的平均總執(zhí)行時(shí)間和平均資源占用時(shí)間對(duì)比，圖9的結(jié)果說(shuō)明了本文算法在不同 CCR條件下，相較于其他算法在資源占用方面的優(yōu)越性較高。

4) DAG任務(wù)頑健性實(shí)驗(yàn)。調(diào)度算法的頑健性表現(xiàn)在處理異構(gòu)DAG任務(wù)時(shí)的穩(wěn)定性，本實(shí)驗(yàn)隨機(jī)生成 6組(每組 100個(gè)樣本)層數(shù)為 5～10的異構(gòu)DAG模型，統(tǒng)計(jì)各算法執(zhí)行每組數(shù)據(jù)后的平均總執(zhí)行時(shí)間和平均資源占用時(shí)間，其對(duì)比結(jié)果如圖 10所示，從圖中本文算法與其他算法的性能對(duì)比變化可知，異構(gòu)DAG任務(wù)對(duì)SD算法影響較小。

5) 虛擬設(shè)備個(gè)數(shù)穩(wěn)定性實(shí)驗(yàn)。本實(shí)驗(yàn)生成了6組(每組 100個(gè)樣本)虛擬設(shè)備個(gè)數(shù)不同(3～8)的任務(wù)，統(tǒng)計(jì)各算法執(zhí)行每組數(shù)據(jù)后的平均執(zhí)行時(shí)間和平均資源占用時(shí)間，其對(duì)比結(jié)果如圖 11所示，從圖中本文算法與其他算法的性能對(duì)比變化可知，虛擬設(shè)備的個(gè)數(shù)變化對(duì)SD算法的影響較小。

圖9 CCR分片對(duì)比

圖10 DAG模型頑健性對(duì)比

圖11 虛擬設(shè)備個(gè)數(shù)穩(wěn)定性對(duì)比

6) 實(shí)驗(yàn)結(jié)論。本實(shí)驗(yàn)分別從5個(gè)方面實(shí)證了算法的有效性，在CCR分析實(shí)驗(yàn)、DAG任務(wù)頑健性實(shí)驗(yàn)和虛擬設(shè)備個(gè)數(shù)穩(wěn)定性實(shí)驗(yàn)方面，通過(guò)與其他算法結(jié)果的對(duì)比，驗(yàn)證了本文算法的穩(wěn)定性，說(shuō)明本文算法面對(duì)各類DAG任務(wù)調(diào)度問(wèn)題時(shí)可保持其有效性；在任務(wù)總執(zhí)行時(shí)間分析實(shí)驗(yàn)方面，本文算法執(zhí)行結(jié)果近于同類算法最優(yōu)值，在資源占用時(shí)間方面優(yōu)于其他算法。

7 結(jié)束語(yǔ)

本文根據(jù) IaaS模型中各虛擬設(shè)備離散分布的特點(diǎn)，建立控制子系統(tǒng)CS和節(jié)點(diǎn)子系統(tǒng)NS及IaaS模型的DAG任務(wù)調(diào)度模型，并利用信號(hào)驅(qū)動(dòng)的方式處理DAG任務(wù)調(diào)度問(wèn)題。由于該算法以并行計(jì)算的DAG任務(wù)調(diào)度模型為基礎(chǔ)使該算法具有普適性，可解決一般并行計(jì)算優(yōu)化問(wèn)題，本文算法的創(chuàng)新性和意義如下：所設(shè)計(jì)的利用信號(hào)交互機(jī)制進(jìn)行驅(qū)動(dòng)式調(diào)度，是面向IaaS的DAG任務(wù)調(diào)度的一次創(chuàng)新；所設(shè)計(jì)的并行優(yōu)化選擇策略，從全局角度考慮了DAG結(jié)構(gòu)，使調(diào)度結(jié)果更加合理化；算法的復(fù)雜度為O(nlog(n))，低于傳統(tǒng)DAG調(diào)度算法，使得該算法更加簡(jiǎn)單適用；算法的穩(wěn)定性高于其他算法，適用于各類異構(gòu)任務(wù)；相較于其他算法，本文算法的執(zhí)行總時(shí)間近于最優(yōu)，且對(duì)虛擬設(shè)備的占用時(shí)間最低。

因此，本文提出的算法不僅可以解決IaaS模型的調(diào)度問(wèn)題，且對(duì)深入研究并行調(diào)度優(yōu)化問(wèn)題具有一定的理論和實(shí)際意義。

[1] ZHANG J X, GU Z M, ZHENG C. Survey of research progress on cloud computing[J]. Application Research of Computers, 2010, 27(2):429-433.

[2] 謝亞龍, 丁麗萍, 林渝淇等. ICFF：一種IaaS模式下的云取證框架[J]. 通信學(xué)報(bào), 2013, 34(5): 200-206.XIE Y L, DING L P, LIN Y Q. ICFF: a cloud forensics framework under the IaaS model[J]. Journal on Communications, 2013, 34(5):200-206.

[3] AMAZON Inc. Amazon elastic compute cloud (Amazon EC2)[EB/OL].http://aws.amazon.com/ec2.

[4] NURMI D, WOLSKI R, GRZEGORCZYK C,et al. The eucalyptus open-source cloud-computing system[A]. Proceedings of the 9th IEEE/ACM Conference on International Computing and the Grid[C].Tsukuba, Japan, 2009.124-131.

[5] COMPUTING R C. Openstack open source cloud computing software[EB/OL]. http://openstaek.org.

[6] LU X Y, LIN J, ZHA L,et al. Vega LingCloud: a resource single leasing point system to support heterogeneous application modes on shared infrastructure[A]. Proceedings of the 9th IEEE Conference on Parallel and Distributed Processing with Applications[C]. Busan, Korea, 2011. 99-106.

[7] MARCOS D, COSTANZO A, BUYYA R. A cost-benefit analysis of using cloud computing to extend the capacity of clusters[J]. Cluster Computing, 2010, 13(3): 335-347.

[8] MARCOS D , COSTANZO A, BUYYA R. Evaluating the cost-benefit of using cloud computing to extend the capacity of clusters[A]. Proceedings of the 18th ACM international Conference on High Performance Distributed Computing[C]. Munich, Germany, 2009.141-150.

[9] NAN X, HE Y, GUAN L. Optimal resource allocation for multimedia cloud based on queuing model[A]. Proceedings of the 13th IEEE Conference on Multimedia Signal[C]. Hangzhou, China, 2011.1-6.

[10] KLLAPI H, SITARIDI E, TSANGARIS M M,et al. Schedule optimization for data processing flows on the cloud[A]. Proceedings of the 2011 ACM SIGMOD Conference on Management of Data[C]. Athens,Greece, 2011. 289-300.

[11] LIN C, LU S. Scheduling scientific workflows elastically for cloud computing[A]. Proceedings of the 2011 IEEE Conference on Cloud Computing[C]. Washington DC, USA, 2011. 746-747.

[12] TOPCUOGLU H, HARIRI S. Performance-effective and low- complexity task scheduling for heterogeneous computing[J]. Parallel and Distributed Systems, 2002(13):260-274.

[13] 謝志強(qiáng), 劉勝輝, 喬佩利. 基于 ACPM 和 BFSM 的動(dòng)態(tài) Job-Shop調(diào)度算法[J]. 計(jì)算研究與發(fā)展, 2003, 40(7): 977-983.XIE Z Q, LIU S H, QIAO P L. Dynamic job-shop scheduling algorithm based on ACPM and BFSM[J]. Journal of Computer Research and Development, 2003, 40(7): 977-983.

[14] LUIZ F B, EDMUNDO R M. Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing,2010, 8(3): 419-441.

[15] 謝志強(qiáng), 楊靜, 楊光. 可動(dòng)態(tài)生成具有優(yōu)先級(jí)工序集的動(dòng)態(tài)Job-Shop調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(3): 502-508.XIE Z Q, YANG J, YANG G. Dynamic Job-Shop scheduling algorithm with dynamic set of operation having priority[J]. Chinese Journal of Computers, 2008, 31(3): 502-508.

[16] LUIZ F B, RIZOS S, EDMUNDO R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[A].Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing[C]. Pisa, Italy, 2010.27-34.

[17] 謝志強(qiáng), 辛宇, 楊靜. 可回退搶占的設(shè)備驅(qū)動(dòng)綜合調(diào)度算法[J]. 自動(dòng)化學(xué)報(bào), 2011, 37(11): 1332-1343.XIE Z Q, XIN Y, YANG J. Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011,37(11): 1332-1343.

[18] RIZOS S, HENAN Z. A hybrid heuristic for DAG scheduling on heterogeneous systems[A]. Proceedings of the 18th IEEE International Parallel and Distributed Processing Symposium (IPDPS)[C]. Santa Fe,USA, 2004.266-286.

[19] 謝志強(qiáng), 楊靜, 周勇等. 基于工序集的動(dòng)態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(2): 406-412.XIE Z Q, YANG J, ZHOU Y,et al. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers, 2011, 34(2): 406-412.

[20] TAYAL S. Tasks scheduling optimization for the cloud computing systems[J]. International Journal of Advanced Engineering Sciences And Technologies, 2011, 5(2): 111-115.

[21] PANDEY S, WU L, GURU S M,et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[A]. Proceedings of the 24th IEEE Conference on Advanced Information Networking and Applications[C].Perth, Australia, 2010.400-407.

[22] WU Z, NI Z, GU L,et al. A revised discrete particle swarm optimization for cloud workflow scheduling[A]. Proceedings of the 2010 IEEE Conference on Computational Intelligence and Security[C]. Guangzhou, China, 2010.184-188.

[23] LUIZ F B, EDMUNDO R M. Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing.2010, 8(3) : 419-441.