面向系統(tǒng)應用模式的資源調(diào)度優(yōu)化算法

白鴻武

（咸陽師范學院 咸陽 712000）

1 引言

互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，導致了產(chǎn)品商品化競爭越來越激烈，用戶體驗對于企業(yè)成敗至關(guān)重要［1］。業(yè)務能否高效運行直接關(guān)系到企業(yè)利潤、業(yè)務流量增長［2］。面對網(wǎng)絡復雜性、異構(gòu)性和分布性的增強，網(wǎng)絡環(huán)境日趨復雜，涉及的組件日趨廣泛，如服務器、存儲、網(wǎng)絡、中間件和數(shù)據(jù)庫等［3～5］，任何一個環(huán)節(jié)的短板都可能是整個系統(tǒng)的性能瓶頸，如何有效提高系統(tǒng)業(yè)務能力，是每個系統(tǒng)在發(fā)展過程中可能不得不面對的問題。

隨著硬件性能的提升和高性能計算的發(fā)展，高性能計算機越來越普遍，給計算機應用帶來了更多發(fā)展空間，計算機性能向著智能化、網(wǎng)絡化等方向發(fā)展［6～8］，完成某項復雜功能的應用可能有大量完成部分功能的作業(yè)組成，或者完成某項功能希望同時運行幾個應用，而服務器資源是有限的，由此產(chǎn)生一種資源管理問題，即資源受限項目調(diào)度問題（Resource Constrained Project Scheduling Problem，RCPSP）［9］，在滿足應用資源需求及技術(shù)上需要的應用前后約束的前提下，對應用進行合理調(diào)度，尋找項目最短工期。為描述方便，論文將上述包含一系列作業(yè)的復雜應用或需要很多應用配合的復雜系統(tǒng)表述為系統(tǒng)，將其包含的作業(yè)或應用表述為應用。

在服務器中，系統(tǒng)包含的應用的調(diào)度大多是混亂的，由運維人員通過自身經(jīng)驗決定，沒有科學的參考依據(jù)，如果能夠通過對應用特征進行分析，獲得應用的性能模式，根據(jù)應用性能模式為應用選擇調(diào)度策略尋找一種更好的綜合調(diào)度方案，不僅能提高服務器資源利用率，也能節(jié)省系統(tǒng)整體運行時間，對提升系統(tǒng)性能有很大價值。因此論文提出一種基于系統(tǒng)應用模式的資源調(diào)度優(yōu)化算法。

2 算法概述

常用于解決資源受限項目調(diào)度問題的算法主要是將所有應用加入一個資源池，根據(jù)應用資源需求尋找調(diào)度方案［10］。而本文提出的基于系統(tǒng)應用模式的資源調(diào)度優(yōu)化算法，從應用的行為模式出發(fā)，首先根據(jù)應用資源需求特征判斷應用的行為模式，然后再從行為模式出發(fā)，選擇不同調(diào)度策略尋找調(diào)度方案。

即使應用實現(xiàn)的功能千差萬別，各不相同，但是對資源的需求卻總是有模式可循的，偏計算功能的應用一般需要的CPU資源多一些，偏交互功能的應用可能需要的IO資源多一些。調(diào)度應用時，雖然不關(guān)心其功能，但是其資源需求卻至關(guān)重要。設想將兩個CPU資源需求都很高，但是內(nèi)存需求卻很低的應用一起調(diào)度，雖然可行，但是服務器的內(nèi)存資源沒有充分利用，CPU資源卻存在強的競爭，可能造成應用性能瓶頸，影響用戶體驗。而如果將一個CPU資源需求高，內(nèi)存需求低的應用和一個CPU資源需求低，而內(nèi)存需求高的應用一起調(diào)度，不僅可以減少應用競爭，而且能夠提高服務器資源利用率［11］。因此通過聚類的方法對應用資源需求特征進行挖掘，得到其行為模式，來指導調(diào)度算法可以優(yōu)化調(diào)度方案。

本文采用的調(diào)度算法，首先通過人工干預的方式，根據(jù)系統(tǒng)應用模式為其選擇調(diào)度策略，調(diào)度策略分兩種：策略A，行為模式表明應用各種資源需求達到一種平衡，沒有明顯偏向，則此種模式應用內(nèi)通過調(diào)度算法尋找調(diào)度方案；策略B，模式一和模式二兩種模式表明這兩種應用資源需求存在互補關(guān)系，比如模式一需要CPU資源多內(nèi)存少，模式二需要CPU資源少內(nèi)存多，則在兩種應用內(nèi)通過調(diào)度算法尋找調(diào)度方案。

綜上，基于系統(tǒng)應用模式的資源調(diào)度優(yōu)化算法分為兩個步驟：一是系統(tǒng)應用模式挖掘，二是應用調(diào)度優(yōu)化。

3 算法設計

3.1 基于聚類算法的系統(tǒng)應用模式挖掘算法設計

通過數(shù)據(jù)采集系統(tǒng)采集到的應用運行期間的數(shù)據(jù)是時間序列數(shù)據(jù)，因此，系統(tǒng)應用模式挖掘就是時間序列挖掘。因為時間序列數(shù)據(jù)具備高維性、復雜性、動態(tài)性及高噪聲等特性，而且與時間相關(guān)聯(lián)，數(shù)據(jù)量非常龐大，所以直接聚類分析有很大復雜性，因此采用基于特征的聚類方法，提取每類資源需求的最大值作為其資源需求特征，然后進行聚類分析。

基于聚類算法［12］的系統(tǒng)應用模式挖掘算法將k-means算法和層次聚類算法相結(jié)合［13］。首先根據(jù)開發(fā)人員的經(jīng)驗對數(shù)據(jù)初步分析，估計一個k值，k大于最終類別數(shù)，且遠小于樣本數(shù)目，然后通過k-means算法進行初步聚類，得到k個聚類中心點。再通過層次聚類算法對k個中心點再次聚類，得到層次聚類樹，最后通過對層次聚類每次聚類情況的分析，對層次聚類樹剪枝，得到最終的聚類結(jié)果。這樣結(jié)合不僅解決了k-means算法k值難以確定的問題，也避免了層次聚類算法計算量過大，效率低下的問題。

基于聚類算法的系統(tǒng)應用模式挖掘算法流程如圖1所示。

圖1 基于聚類算法的系統(tǒng)應用模式挖掘算法流程圖

3.2 基于系統(tǒng)應用模式的資源調(diào)度算法優(yōu)化設計

根據(jù)多維資源綜合調(diào)度算法［14］實現(xiàn)基于系統(tǒng)應用模式的調(diào)度算法。

服務器的資源容量抽象為一個m維向量，R={r1,..,rm}，ri表示資源Ri的總量。假設服務器有n個應用需要調(diào)度，應用 j由資源需求向量wj={w1,j,..,wm,j}，對資源Ri的需求記做wi,j。

定義Pj表示調(diào)度應用 j的收益，如下面式（1）所示。問題最終目的是最大化總收益：

定義αi，表明各種資源維度之間的稀缺程度，如式（2）所示，其中，uj和rj是沒有調(diào)度的應用數(shù)量和資源限制。

定義效率度量標準ej，用來動態(tài)調(diào)整優(yōu)先選擇那些需要較少的稀缺資源的應用，如式（3）所示。

在基于系統(tǒng)應用模式的調(diào)度算法中，主要分為兩步：一是通過人工干預的方式，根據(jù)系統(tǒng)應用模式，選擇調(diào)度策略；二是根據(jù)不同調(diào)度策略對不同模式的應用進行調(diào)度。最后將所有模式的調(diào)度方案合并，得到系統(tǒng)完整調(diào)度方案。

根據(jù)系統(tǒng)應用模式，可以判斷哪些模式對于資源的需求達到了一種平衡，采用調(diào)度策略A，此種模式的應用加入一個資源池進行調(diào)度；哪些模式對于資源需求是具有互補關(guān)系，采用調(diào)度策略B，這兩種模式的應用加入一個資源池進行調(diào)度。具體調(diào)度過程如下：

步驟1：計算每種資源稀缺程度α，每個應用的收益P和效率e；

步驟2：按照e遞減，P遞減的方式對等待調(diào)度的應用進行排序；

步驟3：調(diào)度策略A，從等待調(diào)度的應用隊列中選擇可以滿足資源需求且可以調(diào)度的應用進行調(diào)度；

步驟4：調(diào)度策略B，從等待調(diào)度的應用隊列中優(yōu)先選擇正在運行的應用中模式較少的一方的可調(diào)度應用進行調(diào)度，比如正在運行的應用中模式一數(shù)量多，則優(yōu)先選擇模式二的應用，反之亦然；

步驟5：從正在運行的應用隊列中選擇運行結(jié)束的應用移除隊列，釋放資源；

步驟6：重復上述過程，直到等待調(diào)度的應用隊列為空，得到調(diào)度方案。

基于系統(tǒng)應用模式的調(diào)度算法的偽代碼如算法1所示。

算法1：基于系統(tǒng)應用模式的調(diào)度算法輸入：服務器資源容量res，應用信息jobInfos輸出：調(diào)度方案BEGIN:strategys=SelectStrategyByPattern(jobInfos)res=initRes()jobs_wait=initJobsWait(jobInfos)while(jobs_wait.length＞0):jobs_wait.compute(p,α,p)jobs_wait.sortDESC(e,p)if(strategy==‘A’):jobs_choosed=jobs_wait.choose()else:jobs_choosed=jobs_wait.chooseTheLessPattern()end if jobs_wait.pop(jobs_choosed)jobs_run.append(jobs_choosed)res.subtract(jobs_choosed.need)jobs_finish=jobs_run.finish()jobs_run.pop(jobs_finish)res.add(jobs_finish.need)jobs_finish.append(jobs_finish)end while return jobs_finish END

4 實驗驗證

選擇90個應用，取其CPU、內(nèi)存和網(wǎng)絡需求，作為數(shù)據(jù)樣本。首先通過k-means對數(shù)據(jù)樣本進行初步聚類，取k為30。然后對中心點層次聚類。計算每次合并時，所有樣本的距離和，如圖2所示，可以看出6是一個明顯拐點，因此最終將90個應用聚成6類。

圖2 層次聚類距離圖

應用聚成6類時，數(shù)據(jù)中心即系統(tǒng)應用模式如表1所示。從數(shù)據(jù)中心可以看出，應用1和應用2，應用5和應用6在資源需求上存在互補關(guān)系，應用3在資源需求上處于一種自平衡的狀態(tài)，應用4資源占用與應用2比較接近，歸入應用2。

表1 系統(tǒng)應用模式表

本文對應用1和應用2（包含應用4），應用5和應用6運用基于系統(tǒng)應用模式調(diào)度算法的策略B，對3應用策略A。選擇其中30個應用進行調(diào)度，通過多種算法比較進行可行性分析。不同算法情況如表2所示。

表2 不同算法生成的調(diào)度方案情況表

從表2中數(shù)據(jù)可以看出，任何一種調(diào)度算法給出的調(diào)度方案都可以對調(diào)度結(jié)果產(chǎn)生優(yōu)化，不僅可以縮短整體調(diào)度時間，還可以提高數(shù)據(jù)中心資源利用率。同時，我們也可以從表中數(shù)據(jù)看出，不同調(diào)度算法的優(yōu)化效果存在很大差距。

粒子群算法［15］由于位置、速度初始化以及中間調(diào)整過程都具有隨機性，產(chǎn)生的結(jié)果并不理想。多維資源綜合調(diào)度算法，表現(xiàn)比較好，程序運行時間很短，整體調(diào)度時間縮短了一半，各類資源利用率也有很大提高。遺傳算法生成的調(diào)度方案效果最好，但是程序運行時間很長，時間復雜度太高?；谙到y(tǒng)應用模式的調(diào)度算法，不僅運行時間短，且整體調(diào)度時間最短，各類資源平均利用率也是大幅度提高，綜合來看，表現(xiàn)最好。

5 結(jié)語

本文提出的基于系統(tǒng)應用模式的資源調(diào)度優(yōu)化算法，通過聚類算法挖掘系統(tǒng)應用模式，然后根據(jù)系統(tǒng)應用模式選擇合適調(diào)度策略對應用進行調(diào)度，對于提高服務器資源利用率，平衡各種資源綜合利用，縮短應用整體運行時間具有重大意義，并且算法時間效率高，適用于真實生產(chǎn)環(huán)境。