陳 超，李柏巖，劉曉強(qiáng)，馮珍妮

(東華大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620)

0 引言

近年來，隨著云計算技術(shù)的日益成熟，越來越越多的應(yīng)用系統(tǒng)被以各種方式部署到云平臺。云服務(wù)器一般按實際使用資源來計費，可動態(tài)擴(kuò)展和縮減，為充分利用購買的計算資源，節(jié)省計算成本，需要對應(yīng)用系統(tǒng)的任務(wù)進(jìn)行合理調(diào)度，使服務(wù)器負(fù)載均衡，并對應(yīng)用系統(tǒng)隨著應(yīng)用規(guī)模擴(kuò)展對使用云資源的需求進(jìn)行預(yù)測。

開放網(wǎng)絡(luò)環(huán)境下的分布式系統(tǒng)往往采用松耦合的面向服務(wù)的（Service-Oriented Architecture，SOA）架構(gòu)，將復(fù)雜應(yīng)用按照功能特點劃分為不同的服務(wù)，這些服務(wù)是一些粗粒度并且可以被調(diào)用的軟件實體，具有高可用性、擴(kuò)展性和重用性特征。這樣的結(jié)構(gòu)允許系統(tǒng)的組件按需部署。在大型系統(tǒng)中，隨著系統(tǒng)業(yè)務(wù)和用戶的不斷增加，系統(tǒng)的任務(wù)數(shù)量也會增多，分布式的任務(wù)處理架構(gòu)在使系統(tǒng)提高并發(fā)性、可擴(kuò)展性、容錯性的同時，也會產(chǎn)生因負(fù)載不均而導(dǎo)致的資源浪費問題。為保證系統(tǒng)的工作效率，最大限度地利用計算機(jī)資源，應(yīng)用系統(tǒng)自身也需根據(jù)實際情況進(jìn)行合理的任務(wù)調(diào)度。

任務(wù)調(diào)度是分布式系統(tǒng)的一個基本問題，而且一般形式下的任務(wù)調(diào)度是一個 NP完全問題（Non-deterministic Polynomial，NP），學(xué)者對此進(jìn)行過大量的研究工作。參考文獻(xiàn)[1]使用改進(jìn)蟻群算法對Storm任務(wù)調(diào)度進(jìn)行優(yōu)化，并通過實驗證明改進(jìn)后的調(diào)度方法在算法效率上相比 Storm默認(rèn)的輪詢調(diào)度算法得到了大幅的提高；參考文獻(xiàn)[2]采用隨機(jī)森林分類器將任務(wù)按照執(zhí)行時長進(jìn)行分類，再使用粒子群優(yōu)化算法對問題進(jìn)行優(yōu)化，不僅均衡了計算節(jié)點的CPU和內(nèi)存的利用率，還對任務(wù)完成時間進(jìn)行了優(yōu)化，減少了任務(wù)完成的總體時間；參考文獻(xiàn)[3]針對定時任務(wù)在未來一段時間內(nèi)產(chǎn)生的負(fù)載，提出了靜態(tài)調(diào)度的可行性，并基于遺傳算法設(shè)計了一種適用于定時任務(wù)的負(fù)載均衡算法；參考文獻(xiàn)[4]針對蟻群算法在進(jìn)行任務(wù)調(diào)度時，存在收斂速度慢，局部搜索能力差以及容易陷入局部最優(yōu)等問題，結(jié)合了模擬退火算法，利用模擬退火算法較強(qiáng)的局部搜索能力，實現(xiàn)一種能有效減少任務(wù)完成時間以及保證資源負(fù)載均衡的任務(wù)調(diào)度算法；參考文獻(xiàn)[5]先用模糊 C均值聚類將任務(wù)分類，再用min-min算法進(jìn)行任務(wù)調(diào)度，減少了任務(wù)完成時間；參考文獻(xiàn)[6]采用粒子群優(yōu)化算法結(jié)合遺傳算法，實現(xiàn)了粒子群優(yōu)化算法對離散問題的求解能力，并通過離散改進(jìn)后的粒子群算法求解模糊柔性作業(yè)車間的多目標(biāo)調(diào)度，在保留調(diào)度算法多樣性的同時，降低了算法后期陷入局部最優(yōu)解的概率。

本文研究一個分布式網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)的任務(wù)調(diào)度優(yōu)化問題，針對系統(tǒng)任務(wù)完成時間的實時性約束，提出了一種改進(jìn)粒子群優(yōu)化算法并結(jié)合遺傳算法解決了系統(tǒng)任務(wù)調(diào)度優(yōu)化問題，并通過實驗證實所提出的調(diào)度策略有較好的負(fù)載均衡度及較短的優(yōu)化完成時間。

1 網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)的任務(wù)調(diào)度問題

網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)是一個部署在云平臺上，為目標(biāo)網(wǎng)站群提供實時安全監(jiān)測服務(wù)的分布式應(yīng)用系統(tǒng)。它定時掃描目標(biāo)客戶網(wǎng)站，對網(wǎng)站中所有網(wǎng)頁進(jìn)行分析，檢測網(wǎng)頁是否可用，是否被篡改，以及是否出現(xiàn)違規(guī)詞、敏感詞、敏感圖片等，并對網(wǎng)站出現(xiàn)的異常情況進(jìn)行預(yù)警提示[7]。系統(tǒng)的監(jiān)測分析任務(wù)如圖1所示，主要包括網(wǎng)站存活監(jiān)測、網(wǎng)站爬蟲、網(wǎng)站解析、網(wǎng)頁變更監(jiān)測、違規(guī)詞監(jiān)測、違規(guī)圖片監(jiān)測、敏感信息監(jiān)測以及預(yù)警處理等。除了爬蟲任務(wù)要稍微提前外，系統(tǒng)中的每項任務(wù)基本上互不影響，獨立工作。

圖1 網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)任務(wù)調(diào)度示意圖Fig.1 Schematic diagram of task scheduling of web content security monitoring system

網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)的幾乎所有的監(jiān)測任務(wù)都是定時觸發(fā)的，任務(wù)的啟動頻率由客戶自行選擇。由于客戶較多，而且每個客戶一般有多個網(wǎng)站需要監(jiān)測，因此系統(tǒng)同時監(jiān)測的目標(biāo)網(wǎng)站數(shù)量很大，網(wǎng)頁數(shù)量十分龐大。隨著監(jiān)測網(wǎng)站數(shù)量的增加，系統(tǒng)并發(fā)運行的任務(wù)數(shù)會急劇增長。為了能夠在第一時間發(fā)現(xiàn)網(wǎng)站的問題，及時進(jìn)行處理，監(jiān)測系統(tǒng)必須在限定時間內(nèi)完成每個網(wǎng)站的監(jiān)測任務(wù)，對發(fā)現(xiàn)的問題及時進(jìn)行報告。因此，對系統(tǒng)進(jìn)行合理的任務(wù)調(diào)度，不同的任務(wù)負(fù)載均衡地分配到現(xiàn)有的服務(wù)器，保障現(xiàn)有資源能夠被充分利用。

2 監(jiān)測系統(tǒng)的任務(wù)調(diào)度解決方案

2.1 監(jiān)測任務(wù)整合

由于監(jiān)測系統(tǒng)的核心任務(wù)都是周期性定時觸發(fā)的，在運行環(huán)境和監(jiān)測目標(biāo)不變的情況下，產(chǎn)生的任務(wù)數(shù)量與執(zhí)行時間基本穩(wěn)定。為減少開銷，本文采用靜態(tài)調(diào)度策略對系統(tǒng)中的任務(wù)進(jìn)行調(diào)度。為了掌握任務(wù)的基本信息，本文首先對各種任務(wù)的資源占用情況進(jìn)行了多次測量，并計算出各任務(wù)平均用時，如表1所示。其中，違規(guī)詞監(jiān)測、違規(guī)詞監(jiān)測、敏感詞監(jiān)測、網(wǎng)站爬蟲以及網(wǎng)頁變更監(jiān)測是針對網(wǎng)站所有頁面，故處理時間為處理每個頁面所需的平均時間，網(wǎng)站存活檢測和網(wǎng)站信息獲取只針對主頁。測量在多個相同參數(shù)配置的租用服務(wù)器上進(jìn)行，得到相近的結(jié)果。

表1 任務(wù)平均資源消耗表Tab.1 Task average resource consumption table

對于監(jiān)測系統(tǒng)中的每個目標(biāo)網(wǎng)站，系統(tǒng)每次檢測都會產(chǎn)生7個任務(wù)（見表1）。由于要監(jiān)測網(wǎng)站數(shù)量龐大，每日要監(jiān)測多次，所以產(chǎn)生的任務(wù)數(shù)量十分巨大，調(diào)度算法進(jìn)行優(yōu)化時所需的計算量也會很大。為此，本文將一段時間內(nèi)的同一種類任務(wù)合并，不但能簡化調(diào)度的難度，還能減少調(diào)度的次數(shù)。這里之所以能進(jìn)行“歸并”是因為同一種任務(wù)即便針對不同網(wǎng)站，其所需的計算資源也大致相同，歸并之后可以將它們看成一個任務(wù)在時間上的拉長。

對每類業(yè)務(wù)做“歸并”，將同類任務(wù)按時間段分段歸并，稱為“歸并任務(wù)”，記為 Task。第 j個歸并任務(wù)taskj用向量表示為：

2.2 監(jiān)測任務(wù)調(diào)度

2.2.1 監(jiān)測任務(wù)調(diào)度定義

任務(wù)調(diào)度就是將系統(tǒng)任務(wù)集里的任務(wù)以某種策略合理地分配到各分布式計算節(jié)點上進(jìn)行處理，并以任務(wù)資源利用率、可靠性和負(fù)載均衡等指標(biāo)作為調(diào)度目標(biāo)[8]。本調(diào)度問題有以下具體約束：

①每臺服務(wù)器所有并發(fā)Task所需 CPU資源總和不大于服務(wù)器CPU資源上限。

②每臺服務(wù)器所有并Task所需內(nèi)存資源總和不大于服務(wù)器內(nèi)存資源上限。

③每臺服務(wù)器所有Task完成時間不大于Φ。

對于系統(tǒng)中的m個Task，其調(diào)度向量可表示為：

D=[s1,s2,…,sm]

其中sj(j=1,2,…,m)為服務(wù)器編號。如D=[1，3，1，2]表示為task1分配給服務(wù)器1，task2分配給服務(wù)器 3，task3分配給服務(wù)器 1，task4分配給服務(wù)器 2。有了任務(wù)調(diào)度向量，下面定義評價指標(biāo)，建立調(diào)度優(yōu)劣的評價標(biāo)準(zhǔn)。

定義2.n臺服務(wù)器機(jī)組的平均資源利用率：

定義3.服務(wù)器機(jī)組的負(fù)載均衡度：

當(dāng) LD越大時，服務(wù)器機(jī)組的負(fù)載均衡度越高，調(diào)度策略越優(yōu)秀。

2.2.2 監(jiān)測任務(wù)調(diào)度算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種優(yōu)化計算的技術(shù)[9-11]，它通過模擬鳥群合作尋找食物的過程，快速地搜索最優(yōu)解，常用來優(yōu)化調(diào)度策略。PSO算法參數(shù)簡單、收斂速度快。算法隨機(jī)生成初始化粒子群，粒子有兩個屬性：速度和位置，每個粒子代表了一種解的可能并對應(yīng)一個適應(yīng)值。在搜尋過程中每個粒子有著個體最優(yōu)化位置，粒子群有全局最優(yōu)位置，每個粒子根據(jù)個體最優(yōu)位置和全局最優(yōu)位置更新自己的速度和位置。其更新公式如下：

由式（4）及（5）可知PSO算法可用于求解連續(xù)優(yōu)化問題，而本文調(diào)度問題明顯是一離散優(yōu)化問題，需對算法進(jìn)行離散化改進(jìn)，使其能夠解決離散型問題。

本文的調(diào)度算法是為求解調(diào)度向量 D，由于廣義的PSO算法并不合適解決離散問題，故將遺傳（Genetic Algorithm，GA）算法中的交叉和變異操作引入PSO算法來重構(gòu)其速度和位置的更新算法[12-14]，不但能解決不適合應(yīng)用于離散優(yōu)化的問題，同時利用GA算法提高了算法迭代到后期的多樣性[15]。改進(jìn)離散PSO算法如下所示：

離散PSO算法更新過程如下：

輸入：迭代次數(shù)G，參數(shù)c1,c2，粒子群數(shù)N

輸出：全部迭代完成后的全局最優(yōu)位置gg

2.3 算法步驟

本文任務(wù)調(diào)度算法的具體步驟如下：

①進(jìn)行任務(wù)“歸并”，得到任務(wù)集合。

②設(shè)置PSO算法所需參數(shù)：迭代次數(shù)G，參數(shù)c1,c2，粒子群個數(shù)N，服務(wù)器數(shù)量（即PSO算法位置邊界）。

③初始化N個粒子位置xi，粒子速度v，計算每個粒子對應(yīng)的適應(yīng)值，更新個體歷史最優(yōu)位置以及全局最優(yōu)位置。

④根據(jù)粒子群更新算法更新每個粒子的位置與速度，重新計算每個粒子對應(yīng)的適應(yīng)值，更新個體歷史最優(yōu)位置以及全局最優(yōu)位置。

⑤達(dá)到最大迭代次數(shù)，返回全局最優(yōu)位置，否則回到步驟④。

⑥對得到的最優(yōu)位置進(jìn)行評價，符合約束，輸出調(diào)度策略，否則，服務(wù)器數(shù)量+1，返回步驟③。

3 實驗與分析

3.1 任務(wù)調(diào)度算法實驗

本文通過開源仿真平臺Cloudsim進(jìn)行仿真實驗，對比了 GA算法以及蟻群（Ant Colony Optimization，ACO）算法，就任務(wù)調(diào)度算法完成時間，調(diào)度策略的負(fù)載均衡度兩方面，分析了三種任務(wù)調(diào)度算法的優(yōu)劣。PSO-GA算法、GA算法、ACO算法的相關(guān)參數(shù)設(shè)置分別如表2、表3以及表4所示。

表2 PSO-GA 相關(guān)參數(shù)Tab.2 PSO-GA related parameters

表3 GA 相關(guān)參數(shù)Tab.3 GA related parameters

表4 ACO 相關(guān)參數(shù)Tab.4 ACO related parameters

實驗中設(shè)定的任務(wù)數(shù)從20個逐漸遞增到160個，每種情況實驗20次，取測試結(jié)果的平均值?；赑SO-GA算法，GA算法以及ACO算法對任務(wù)調(diào)度優(yōu)化完成所需時間以及任務(wù)調(diào)度負(fù)載均衡度分別如圖2，圖3所示。

圖2 任務(wù)調(diào)度所需時間Fig.2 Time required for task scheduling

圖3 任務(wù)調(diào)度負(fù)載均衡度Fig.3 Task scheduling load balance

從圖2可知，三種算法中，GA算法所需計算時間最多，本文算法和 ACO算法則相差不多，GA算法所需時間遠(yuǎn)超其他兩者因在實現(xiàn)時，該算法有對基因DNA有編碼和解碼過程，增加了計算量。三種算法所需時間大體與任務(wù)數(shù)量成正比。

從圖3可知，隨著任務(wù)數(shù)從20個逐步增加到160個，三種算法的負(fù)載均衡度波動最大不超過0.15，其中ACO算法結(jié)果最不理想，而本文離散改進(jìn)的PSO算法最優(yōu)，最大波動僅為0.02。在有限的迭代次數(shù)中，本文提出算法相較于其他兩種算法有著更為優(yōu)秀的收斂速度以及尋優(yōu)能力。

3.2 服務(wù)器需求分析

本文網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)的業(yè)務(wù)針對的是用戶指定的某個網(wǎng)站，然而不同的網(wǎng)站所包含的網(wǎng)頁數(shù)量各不相同，系統(tǒng)運行時需對每個頁面進(jìn)行監(jiān)測，這也導(dǎo)致了同樣的業(yè)務(wù)對不同網(wǎng)站所消耗的計算資源截然不同。對國內(nèi)三十余所211高校的主站進(jìn)行3層爬取所獲取的網(wǎng)頁數(shù)量進(jìn)行統(tǒng)計，將數(shù)據(jù)進(jìn)行ks檢驗，計算出其D值為0.16，P值為 0.33，故而可知高校網(wǎng)站的網(wǎng)頁數(shù)量服從均值131.59，標(biāo)準(zhǔn)差44.21的正態(tài)分布。結(jié)合表1的任務(wù)平均資源消耗表和本文提出的算法，根據(jù)正態(tài)分布規(guī)律模擬出網(wǎng)站情況。觀察在網(wǎng)站數(shù)不斷增加時，所需服務(wù)器數(shù)量的變化，記錄每次服務(wù)器增加時網(wǎng)站數(shù)量的臨界點。網(wǎng)站數(shù)量與所需服務(wù)器的關(guān)系如下圖4所示。從圖中可知，本網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)，大約每增加495個監(jiān)測網(wǎng)站，就需增加一臺服務(wù)器以滿足系統(tǒng)監(jiān)測的實時性要求。

圖4 監(jiān)測網(wǎng)站數(shù)與服務(wù)器數(shù)關(guān)系圖Fig.4 The relationship between the number of monitored websites and the number of servers

4 總結(jié)

本文為了使大規(guī)模分布式網(wǎng)頁內(nèi)容安全監(jiān)測系統(tǒng)能夠充分利用現(xiàn)有資源，高效穩(wěn)定地運行，提出了一種可行調(diào)度方案，即采用粒子群優(yōu)化算法結(jié)合遺傳算法，在綜合考慮系統(tǒng)負(fù)載均衡和任務(wù)完成時間的實時性約束后進(jìn)行系統(tǒng)任務(wù)調(diào)度優(yōu)化。通過實驗對比了傳統(tǒng)的遺傳算法以及蟻群算法，實驗表明改進(jìn)的粒子群優(yōu)化算法的執(zhí)行時間短，調(diào)度方案負(fù)載均衡度更高。本文的任務(wù)調(diào)度策略現(xiàn)已應(yīng)用到系統(tǒng)當(dāng)中，并在實際工作中取得了良好的效果，但本方案尚有不足之處有待改進(jìn)：其任務(wù)調(diào)度對象針對的是系統(tǒng)的定時任務(wù)，而實際情況中系統(tǒng)還有一些非定時任務(wù)，最后得到的調(diào)度策略只是近似最優(yōu)解。