一種基于多維聚類預(yù)處理的云計(jì)算任務(wù)調(diào)度算法

邵雯娟

摘要：文章主要介紹了一種基于多維聚類預(yù)處理的云計(jì)算任務(wù)調(diào)度算法，根據(jù)預(yù)先分類好的資源特征向量進(jìn)行分類依據(jù)，將云計(jì)算資源與特征向量間的相似度距離作為測(cè)度函數(shù)，將資源劃分到預(yù)先定義好的類別中。本調(diào)度算法對(duì)資源進(jìn)行分類預(yù)處理，能有效縮小任務(wù)對(duì)于資源搜索的范圍，從而提高任務(wù)調(diào)度的速度。關(guān)鍵詞：特征向量；相似度測(cè)度；任務(wù)調(diào)度

1 研究背景

云計(jì)算主要采用虛擬化技術(shù)將數(shù)據(jù)中心的物理資源虛擬化為資源節(jié)點(diǎn)后，進(jìn)行統(tǒng)一管理和對(duì)外服務(wù)。用戶享受的服務(wù)質(zhì)量水平將會(huì)和所需支付的費(fèi)用成正比。正是由于用戶的不同需求，云任務(wù)調(diào)度器需要為用戶任務(wù)選擇合適的資源，最大限度地滿足用戶對(duì)于服務(wù)質(zhì)量的需求，提高資源利用率，維持資源負(fù)載均衡。因此，研究云環(huán)境下的任務(wù)調(diào)度算法意義重大。

2 聚類分析法原理

聚類分析是根據(jù)樣本自身的屬性，用數(shù)學(xué)方法按照某種相似性或差異性指標(biāo)，定量地確定樣本之間的親疏關(guān)系，并按這種親疏關(guān)系程度對(duì)樣本進(jìn)行聚類。通常是用樣本間的相似系數(shù)來(lái)描述其親疏程度。有了相似系數(shù)就可定量地對(duì)樣本進(jìn)行分組，根據(jù)分類函數(shù)將差異最小的歸為一組，組與組之間再按分類函數(shù)進(jìn)一步歸類，直到所有樣本歸為一類為止。

3 算法描述

本算法的目標(biāo)是找到對(duì)資源集的一個(gè)劃分，使資源性能相近或相似的節(jié)點(diǎn)聚在一起共同構(gòu)成一個(gè)分類類別。算法的主要思想是：

（1）對(duì)訓(xùn)練集中的云系統(tǒng)資源向量事先進(jìn)行手工粗分類，分為：計(jì)算型，轉(zhuǎn)發(fā)型，存儲(chǔ)型，計(jì)算出每一類的特征向量F（x_i）={x₁，x₂，x₃，…，x_n）。

（2）對(duì)測(cè)試集中的云系統(tǒng)資源向量建立初始樣本矩陣：S（y_t）=（y₁，y₂，y₃，…，y_n）。

（3）用類間的相似系數(shù)來(lái)描述其親疏程度，計(jì)算每個(gè)資源向量與各個(gè)大類的特征向量間的相似性測(cè)度函數(shù)。

M_j=（F（x₁），S（y_j））=（m₁，m₂，m₃）

相關(guān)性系數(shù)定義為向量的單位化內(nèi)積：

根據(jù)相似性測(cè)度函數(shù)M_j=（F（x₁），S（y_j））的值，根據(jù)模式分類的原則：

C（z）=ArgM_iaxM_j（F（x₁），S（y_j））

（4）比較和S_i最相似的類，從而確定該資源向量的分類，將該資源和大類歸并為一個(gè)類別。

（5）重復(fù)執(zhí)行上述操作，直到資源池中所有資源向量都只屬于同一個(gè)分類類別為止，即所有資源節(jié)點(diǎn)都有明確的分類類別。

（6）在每個(gè)大類中，將資源按照綜合性能進(jìn)行降序排序，性能較好的資源將優(yōu)先被調(diào)度。

（7）對(duì)資源進(jìn)行分類預(yù)處理后，在已有的分類類別中選擇性能最優(yōu)的資源，最大限度地體現(xiàn)了任務(wù)調(diào)度的公平性。

4 算法性能分析

在任務(wù)調(diào)度系統(tǒng)中，用戶提交任務(wù)的最終完成時(shí)間取決于該任務(wù)集中所有任務(wù)的完成時(shí)間，也就是任務(wù)完成時(shí)時(shí)間最大的任務(wù)。

任務(wù)i預(yù)期完成時(shí)間L主要由隊(duì)列等候時(shí)間、處理和存儲(chǔ)時(shí)間、轉(zhuǎn)發(fā)延遲時(shí)間組成。

隊(duì)列等候時(shí)間可用公式（1）計(jì)算得出：（1）

Q（i）表示任務(wù)T_i在分類類別中在任務(wù)隊(duì)列中等待調(diào)度的時(shí)間，n表示任務(wù)i前面的任務(wù)數(shù)，T_j表示第j個(gè)任務(wù)的預(yù)期完成時(shí)間。

處理和存儲(chǔ)時(shí)間可用公式（2）計(jì)算得出：（2）

S（i，k）表示任務(wù)T_i使用資源k時(shí)，所需的計(jì)算執(zhí)行時(shí)間，t_ci表示任務(wù)計(jì)算量，r_calk表示資源K的計(jì)算能力，t_si表示所需存儲(chǔ)的任務(wù)量，r_stork表示資源K的存儲(chǔ)能力。

轉(zhuǎn)發(fā)延遲時(shí)間可由公式（3）計(jì)算得出：（3）

F（i，k）表示任務(wù)i使用K源后，轉(zhuǎn)發(fā)任務(wù)結(jié)果所需的傳輸時(shí)間，t_datai指任務(wù)輸出數(shù)據(jù)量，r_comk表示資源K的通信帶寬能力。

因此，任務(wù)預(yù)期完成時(shí)間可以表示為：

T_i=Q（i，k）+S（i，k）+F（i，k） （4）

使用CloudSim仿真平臺(tái)，將本調(diào)度算法（以下簡(jiǎn)稱GCCTS）與Min-Min和Max-Min算法進(jìn)行模擬實(shí)驗(yàn)調(diào)度，數(shù)據(jù)取自模擬20次取得的平均值。從調(diào)度策略的平均完成時(shí)間對(duì)3種算法進(jìn)行性能比較。圖1所示為資源數(shù)為20時(shí)，3種算法任務(wù)平均完成時(shí)間的比較圖。圖2所示為資源數(shù)為50時(shí)，3種算法任務(wù)平均完成時(shí)的比較圖。

由以上分析可以看出，Min-Min算法由于每次優(yōu)先選擇任務(wù)完成時(shí)間最小的任務(wù)執(zhí)行，因而任務(wù)最終完成時(shí)間小于Max-Min算法，但次于GCCTS算法。

5 結(jié)語(yǔ)

文章主要介紹一種基于多維聚類預(yù)處理的云計(jì)算任務(wù)調(diào)度算法。首先介紹了聚類分析方法，論述分類方法的具體實(shí)現(xiàn)步驟，利用該方法將資源劃分到預(yù)先定義好的分類類別中。然后詳細(xì)介紹算法的主要思想、偽代碼實(shí)現(xiàn)，并經(jīng)過對(duì)模擬環(huán)境下的實(shí)驗(yàn)數(shù)據(jù)分析，本調(diào)度算法對(duì)資源進(jìn)行分類預(yù)處理，能有效縮小任務(wù)對(duì)于資源搜索的范圍，從而提高任務(wù)調(diào)度的速度。

該調(diào)度策略仍然存在很多可改進(jìn)的地方：

（1）在聚類分割時(shí)，可進(jìn)一步考慮總體的資源統(tǒng)計(jì)特性，考慮采用馬哈拉諾比距離，代替相似度度量值。

（2）云環(huán)境下的資源節(jié)點(diǎn)具有動(dòng)態(tài)變化性，需考慮基于隨機(jī)優(yōu)化的動(dòng)態(tài)資源分類。

（3）本文將資源劃分為計(jì)算型，轉(zhuǎn)發(fā)型以及存儲(chǔ)型3個(gè)維度，可結(jié)合實(shí)際用戶需求，提出多維Qos優(yōu)化的云任務(wù)調(diào)度優(yōu)化算法。