云環(huán)境下基于碎片影響度的提前預(yù)定資源調(diào)度策略

李 晨， 劉 博， 李 云

（揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225127）

提前預(yù)定調(diào)度策略［1－2］使調(diào)度程序可以保證資源在未來(lái)一段特定時(shí)間內(nèi)的有效性，增加了系統(tǒng)的可預(yù)測(cè)性。提前預(yù)定調(diào)度策略通常會(huì)產(chǎn)生大量的資源碎片，針對(duì)目前主要的資源調(diào)度模式存在的缺陷，本文提出了一種基于資源碎片影響度的提前預(yù)定資源（fragment－based advance reservations，F(xiàn)BAR）調(diào)度算法，利用計(jì)算幾何的相關(guān)知識(shí)［3］以及一種特定結(jié)構(gòu)的改進(jìn)的平衡搜索樹(shù)來(lái)有效管理資源碎片，同時(shí)根據(jù)各個(gè)計(jì)算節(jié)點(diǎn)的負(fù)載情況、長(zhǎng)碎片閾值和本文提出的碎片影響度函數(shù)制定一種改進(jìn)的提前預(yù)定資源調(diào)度策略，可有效解決因提前預(yù)定而造成的資源碎片問(wèn)題，在大規(guī)模數(shù)據(jù)下提高了資源利用率和任務(wù)命中率。

1 相關(guān)知識(shí)

定義1（提前預(yù)定任務(wù)） 提前預(yù)定任務(wù)用一個(gè)三元組ti＝（ri，li，di）來(lái)表示，其中，ri為最早開(kāi)始時(shí)間，長(zhǎng)度li為執(zhí)行時(shí)間，截止期限di為任務(wù)的最晚完成時(shí)間（di≥ri＋li）。

有2個(gè)計(jì)算節(jié)點(diǎn)的調(diào)度表如圖1所示，在當(dāng)前時(shí)間（t＝0），節(jié)點(diǎn)1上有3個(gè)已被分配的任務(wù)，即當(dāng)前正在執(zhí)行并且將在t1時(shí)間結(jié)束的任務(wù)、已被預(yù)訂在t3執(zhí)行并在t5結(jié)束的任務(wù)A和t9～t11時(shí)間段的任務(wù)D。同樣在節(jié)點(diǎn)2上也有3個(gè)已被分配的任務(wù)：任務(wù)B、C以及當(dāng)前正在執(zhí)行的任務(wù)，并且有一個(gè)新任務(wù)分配的服務(wù)請(qǐng)求為：準(zhǔn)備時(shí)間ri＝t6，執(zhí)行長(zhǎng)度li＝t8－t6。

調(diào)度機(jī)按照一定的資源調(diào)度算法將新提交的任務(wù)分配到合理的計(jì)算節(jié)點(diǎn)上執(zhí)行，更新調(diào)度表并將調(diào)度引用反饋給提交用戶(hù)，否則拒絕執(zhí)行該任務(wù)并反饋用戶(hù)。

圖1 簡(jiǎn)單的有2個(gè)節(jié)點(diǎn)的調(diào)度表

2 基于碎片影響度的提前預(yù)定策略

2.1 基于計(jì)算幾何的資源調(diào)度模型

本文采用計(jì)算幾何的概念［3］，用平面上的1個(gè)點(diǎn)表示1個(gè)相應(yīng)的資源碎片，圖1的計(jì)算幾何表示如圖2所示，x軸為結(jié)束時(shí)間ET，y軸為起始時(shí)間ST，因?yàn)樗匈Y源碎片的ET＞ST，所以全部碎片的計(jì)算幾何表示的點(diǎn)均分布在對(duì)角線(xiàn)的上部，由于碎片X的開(kāi)始時(shí)間為t2，結(jié)束時(shí)間為t4，因此在平面上被表示為坐標(biāo)X＝（t2，t4）上的點(diǎn)。

定義2（完全包含｜?｜） 對(duì)于2個(gè)平面上的點(diǎn)p1＝（x1，y1）、p2＝（x2，y2），若x1≤x2且y1≥y2，則稱(chēng)點(diǎn)p1｜?｜p2。

圖2 圖1的計(jì)算幾何表示

2.2 基于碎片影響度的改進(jìn)的資源調(diào)度策略

2.2.1 平面劃分區(qū)域搜索策略

本文將通過(guò)計(jì)算幾何的相關(guān)概念來(lái)描述帶有截止期限的提前預(yù)定任務(wù)的資源調(diào)度問(wèn)題［4］，如圖3所示。

圖3 帶有截止期限的提前預(yù)定任務(wù)及計(jì)算幾何表示

定義3（可行區(qū)域） 對(duì)于平面上的某一區(qū)域Ri以及任務(wù)tj＝PP′，若有資源碎片所對(duì)應(yīng)的點(diǎn)?Pk∈Ri，且?Pm∈PP′使得Pk｜?｜Pm，則稱(chēng)Ri為任務(wù)tj的可行區(qū)域。

為了使算法更加高效，把平面對(duì)角線(xiàn)的上半?yún)^(qū)域水平分割成多個(gè)子區(qū)域，每個(gè)子區(qū)域的高度為2×lmin，其中l(wèi)min代表系統(tǒng)估計(jì)請(qǐng)求任務(wù)的最小執(zhí)行時(shí)間單元，如圖3所示，如此分割可以使所有K個(gè)碎片點(diǎn)被分類(lèi)成H個(gè)子集合，每一個(gè)h∈H包含了在平面上屬于第h個(gè)水平切割區(qū)域的資源碎片點(diǎn)。

與維護(hù)一個(gè)單一的樹(shù)［5］不同，在構(gòu)建的H棵平衡搜索樹(shù)中每個(gè)樹(shù)結(jié)構(gòu)對(duì)應(yīng)一個(gè)水平區(qū)間，通過(guò)忽略長(zhǎng)度小于最小執(zhí)行時(shí)間單元的碎片點(diǎn)Pi（ETPi－STPi＜lmin），致使每個(gè)資源碎片的長(zhǎng)度不小于lmin，并且每個(gè)計(jì)算節(jié)點(diǎn)中2個(gè)連續(xù)的資源碎片之間的距離（兩者所夾任務(wù)的執(zhí)行時(shí)間）li≥lmin，因此各個(gè)計(jì)算節(jié)點(diǎn)上的任意2個(gè)資源碎片Pi、Pj的開(kāi)始時(shí)間以及結(jié)束時(shí)間之間的距離至少為2個(gè)最小執(zhí)行時(shí)間單元（STPj－STPi，ETPj－ETPi≥2lmin），所以每個(gè)水平區(qū)域所對(duì)應(yīng)的平衡搜索樹(shù)中的資源碎片所對(duì)應(yīng)的點(diǎn)的數(shù)量不會(huì)超過(guò)計(jì)算節(jié)點(diǎn)的總數(shù)目n，并且其中屬于同一計(jì)算節(jié)點(diǎn)的碎片數(shù)目最多為1，在選取某個(gè)資源碎片進(jìn)行任務(wù)分配調(diào)度后所做的更新操作時(shí)間復(fù)雜度大大降低（n?K）。

2.2.2 改進(jìn)的平衡搜索樹(shù)和資源調(diào)度策略

步驟3 將所有訓(xùn)練樣本集XTrain(i)(i=1,2,3)分別向各自所對(duì)應(yīng)標(biāo)準(zhǔn)樣本集Wi(i=1,2,3)進(jìn)行投影,得到每一副圖像對(duì)應(yīng)的系數(shù)向量,這些向量共同形成降維后的樣本集HTrain(i)(i=1,2,3).

每個(gè)水平區(qū)域h＝｛1，…，H｝包含了所有開(kāi)始時(shí)間STPi在［2（h－1）lmin，2hlmin）內(nèi)的資源碎片點(diǎn)，h內(nèi)的所有點(diǎn)用一棵改進(jìn)的平衡搜索樹(shù)Th來(lái)存儲(chǔ)，調(diào)度算法通過(guò)遍歷Th對(duì)水平區(qū)間h內(nèi)的資源碎片按要求進(jìn)行搜索。

在每棵改進(jìn)的平衡搜索樹(shù)Th中，資源碎片點(diǎn)Pi按開(kāi)始時(shí)間STPi升序存儲(chǔ)在Th的葉結(jié)點(diǎn)上，并由一個(gè)三元組（STPi，ETPi，RPi）來(lái)表示，其中RPi為輔助數(shù)據(jù)，包括Pi所處的計(jì)算節(jié)點(diǎn)編號(hào)以及該節(jié)點(diǎn)的負(fù)載情況和傳輸帶寬等。

一個(gè)簡(jiǎn)單的帶有截止期限的提前預(yù)定任務(wù)的資源調(diào)度計(jì)算幾何模型以及h＝2時(shí)的水平分割區(qū)域中資源碎片點(diǎn)的改進(jìn)平衡搜索樹(shù)結(jié)構(gòu)Th＝2如圖4所示。

圖4 計(jì)算幾何模型以及平衡搜索樹(shù)

圖4中，s為開(kāi)始時(shí)間；e為結(jié)束時(shí)間，該水平分割區(qū)域有X＝（s1，e1）、Y＝（s3，e2）、Z＝（s3，e5）以及V＝（s4，e4）4個(gè)資源碎片點(diǎn)。由于s1＜s3＜s4，則按照X→Y→Z→V的升序排列葉結(jié)點(diǎn)。非葉結(jié)點(diǎn)B存儲(chǔ)其子樹(shù)的葉子結(jié)點(diǎn)X、Y的開(kāi)始時(shí)間STX、STY的最小值s1與最大值s3、最晚的結(jié)束時(shí)間e2以及最大碎片長(zhǎng)度e1－s1，相應(yīng)地，根A＝（s1，s4，e5，e5－s3）以及非葉結(jié)點(diǎn)C＝（s3，s4，e5，e5－s3）。

在實(shí)時(shí)調(diào)度下隨著時(shí)間的推移，過(guò)期的資源碎片點(diǎn)將被丟棄，將平面水平分割成若干部分，并分別獨(dú)立維護(hù)每個(gè)水平分割區(qū)域所對(duì)應(yīng)的改進(jìn)的平衡搜索樹(shù)，每隔2lmin個(gè)時(shí)間單位丟棄h＝1所對(duì)應(yīng)的樹(shù)Th＝1，并對(duì)剩下的樹(shù)重新標(biāo)號(hào)h′＝h－1，用一個(gè)循環(huán)隊(duì)列記錄樹(shù)標(biāo)號(hào)并將每棵樹(shù)用哈希索引進(jìn)行映射，比單樹(shù)結(jié)構(gòu)［6］在實(shí)時(shí)系統(tǒng)環(huán)境下具有更高的執(zhí)行效率。

定義4（資源碎片 RF） 假設(shè)Pj＝（STPj，ETPj）為提交的帶有截止期限的任務(wù)ti＝（ri，li，di）所對(duì)應(yīng)的計(jì)算幾何平面模型中PP′上的一點(diǎn)，若存在空閑資源點(diǎn)Px＝（STPx，ETPx），并且有Px｜?｜Pj，則將任務(wù)ti調(diào)度在Px上執(zhí)行時(shí)所產(chǎn)生的資源碎片 RF（ti，Px）＝（STPj－STPx）∪（ETPx－ETPj），其中Pj為ti在Px上可以最早開(kāi)始執(zhí)行的時(shí)間所對(duì)應(yīng)的點(diǎn)。

用戶(hù)提交的任務(wù)規(guī)模大小服從正態(tài)分布N（μ，σ2），申請(qǐng)時(shí)間服從冪函數(shù)分布Xn（n＜0），3種S型曲線(xiàn)函數(shù)如圖5所示。

圖5 3種S型曲線(xiàn)函數(shù)

本文通過(guò)對(duì)這3種S型曲線(xiàn)函數(shù)進(jìn)行實(shí)驗(yàn)分析后選取實(shí)驗(yàn)結(jié)果為最平滑的sigmoid函數(shù)并對(duì)其進(jìn)行改進(jìn)。

定義5（碎片影響度FID） 假設(shè)存在定義4中所產(chǎn)生的資源碎片RF（ti，Px），則碎片影響度FID（ti，Px）定義如下：

其中，β為相應(yīng)的計(jì)算節(jié)點(diǎn)的負(fù)載程度；δ為RPx中所記錄的當(dāng)前計(jì)算節(jié)點(diǎn)中碎片長(zhǎng)度不小于長(zhǎng)資源碎片的碎片總長(zhǎng)度；ε為調(diào)整參數(shù)，是由提交的任務(wù)集合的執(zhí)行時(shí)間長(zhǎng)度范圍σ所決定的；lmax、lmin、分別為提交任務(wù)的最大、最小執(zhí)行長(zhǎng)度以及平均執(zhí)行長(zhǎng)度。

任務(wù)ti在點(diǎn)Px上的碎片影響度FID（ti，Px）越小，說(shuō)明ti在Px上有著更加優(yōu)先的選擇性，在大規(guī)模任務(wù)集合下考慮到各個(gè)計(jì)算節(jié)點(diǎn)的負(fù)載均衡β可以更加有效地充分合理利用資源，增加系統(tǒng)的整體性能。

為了更加高效地對(duì)所有有效資源碎片進(jìn)行掃描分析，將整體搜索策略分為以下步驟。

（1）掃描區(qū)域R1（除水平分割邊界區(qū)域，h＝1，2）。因?yàn)閰^(qū)域R1中所有資源碎片點(diǎn)的開(kāi)始時(shí)間都小于任務(wù)ti的最早開(kāi)始時(shí)間ri，所以在R1區(qū)域內(nèi)的水平分割區(qū)域所對(duì)應(yīng)的改進(jìn)的平衡搜索樹(shù)中所有葉結(jié)點(diǎn)的STPi＜ri。從根結(jié)點(diǎn)開(kāi)始按照深度優(yōu)先搜索依次遍歷：若某一非葉結(jié)點(diǎn)的子樹(shù)最晚結(jié)束時(shí)間小于ri＋li，則表示該非葉結(jié)點(diǎn)的所有葉結(jié)點(diǎn)代表的資源碎片均不能執(zhí)行完成任務(wù)ti，深度遍歷返回上一層繼續(xù)執(zhí)行。

（2）掃描區(qū)域R2（除水平分割邊界區(qū)域，h＝4）。由于區(qū)域R2內(nèi)所有資源碎片點(diǎn)的開(kāi)始時(shí)間都在任務(wù)ti的允許開(kāi)始時(shí)間內(nèi)，所以Th∈（R2＝4）中所有葉結(jié)點(diǎn)的ri＜STPi＜di－li。從根結(jié)點(diǎn)開(kāi)始按照深度優(yōu)先搜索依次遍歷：若某一非葉結(jié)點(diǎn)的子樹(shù)的最大資源碎片長(zhǎng)度小于li，則表示該非葉結(jié)點(diǎn)的所有葉結(jié)點(diǎn)代表的碎片的長(zhǎng)度均不夠完成任務(wù)ti，深度遍歷返回上一層繼續(xù)執(zhí)行。

（3）掃描水平分割邊界區(qū)域（P、P′所在的水平分割區(qū)域，h＝3，5）。從根結(jié)點(diǎn)開(kāi)始按照深度優(yōu)先搜索依次遍歷：若某一非葉結(jié)點(diǎn)的子樹(shù)的資源碎片點(diǎn)的最大開(kāi)始時(shí)間小于ri，則以該結(jié)點(diǎn)為根的子樹(shù)，跳轉(zhuǎn)至步驟（1），按照R1的搜索方式進(jìn)行遍歷，當(dāng)該子樹(shù)遍歷完畢后返回上一層時(shí)，跳轉(zhuǎn)回本步驟中的搜索方式進(jìn)行遍歷；若該結(jié)點(diǎn)的子樹(shù)的資源碎片點(diǎn)的最小開(kāi)始時(shí)間大于ri，且最大開(kāi)始時(shí)間小于di－li，則以該結(jié)點(diǎn)為根的子樹(shù)，跳轉(zhuǎn)至步驟（2），按照R2的搜索方式進(jìn)行遍歷，當(dāng)該子樹(shù)遍歷完畢后返回上一層時(shí)，跳轉(zhuǎn)回本步驟中的搜索方式繼續(xù)進(jìn)行遍歷；若該結(jié)點(diǎn)的子樹(shù)的資源碎片點(diǎn)的最小開(kāi)始時(shí)間大于di－li，則表明以該結(jié)點(diǎn)為根的子樹(shù)的所有葉子結(jié)點(diǎn)所代表的碎片點(diǎn)均不滿(mǎn)足任務(wù)ti的執(zhí)行要求，該樹(shù)遍歷結(jié)束。

（4）在步驟（1）、（2）、（3）中當(dāng)遍歷到葉結(jié)點(diǎn)Px時(shí)，根據(jù)RPx中所記錄的計(jì)算節(jié)點(diǎn)的負(fù)載參數(shù)β、傳輸帶寬以及實(shí)際執(zhí)行時(shí)間計(jì)算該葉結(jié)點(diǎn)所代表的資源碎片Px、調(diào)度任務(wù)ti時(shí)所造成的碎片影響度FID（ti，Px），當(dāng)Px不能滿(mǎn)足ti的截止期限要求時(shí)，該P(yáng)x將不予考慮。根據(jù)以上搜索策略得到λ＝ （di－li）／（2lmin）個(gè)水平分割區(qū)域所對(duì)應(yīng)的改進(jìn)的平衡搜索樹(shù)中的λ個(gè)局部最優(yōu)資源碎片Ph＝1，…，λ使得FID（ti，P1，…，λ）分別在Th＝1，…，λ中最小，最 后 求 得 FID （ti，P1，…，λ）中 的 最 小 值FID（ti，Pk∈｛1，…，λ｝）即為全局最優(yōu)解，使得任務(wù)ti在資源碎片Pk上被調(diào)度時(shí)有著最高的全局系統(tǒng)性能以及任務(wù)命中率。

3 實(shí)驗(yàn)驗(yàn)證及分析

為了驗(yàn)證FBAR調(diào)度算法的有效性，將其與文獻(xiàn) ［7－9］中 提 出 的 HAR（heterogeneous advance reservation）調(diào)度算法進(jìn)行比較，其結(jié)果如圖6所示。實(shí)驗(yàn)環(huán)境包括10個(gè)性能不同的虛擬機(jī)節(jié)點(diǎn)，各計(jì)算節(jié)點(diǎn)間的平均帶寬為20Mb／s。

圖6 不同任務(wù)密度下的任務(wù)丟失率及資源利用率

由圖6可以看出，HAR調(diào)度算法的任務(wù)丟失率隨任務(wù)密度增加迅速變大，顯著影響著系統(tǒng)的利用率；FBAR調(diào)度算法的任務(wù)丟失率基本保持平穩(wěn)增長(zhǎng)，可增加系統(tǒng)資源的利用率。

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

本文提出了一種基于碎片影響度的提前預(yù)定任務(wù)的資源調(diào)度策略，以計(jì)算幾何的形式對(duì)系統(tǒng)資源進(jìn)行平面表示，并將平面水平分割后采用改進(jìn)的平衡搜索樹(shù)結(jié)構(gòu)存儲(chǔ)資源信息，結(jié)合調(diào)度所產(chǎn)生的資源碎片大小和碎片影響時(shí)間長(zhǎng)短，提出碎片影響度來(lái)計(jì)算各個(gè)資源碎片的性能指標(biāo)，選取最優(yōu)資源碎片在滿(mǎn)足任務(wù)需求的情況下對(duì)其進(jìn)行調(diào)度，以獲得比傳統(tǒng)的調(diào)度策略更高的資源利用率和任務(wù)命中率。

［1］ Min R，Maheswaran M.Scheduling advance reservations with priorities in grid computing systems［C］／／Proceedings of PDCS’01，2001：172－176.

［2］ 王景華，張建軍，徐 娟，等.基于分布式Agent的網(wǎng)格任務(wù)調(diào)度模型研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（2）：179－181，225.

［3］ de Berg M，van Krefeld M，Overmars M，et al.Computational geometry：algorithms and applications［M］.2ed.New York：Springer－Verlag，2000：13－32.

［4］ Castillo C，Rouskas G N，Harfoush K.Online algorithms for advance resource reservations［J］.Journal of Parallel and Distributed Computing，2011，71（7）：963－973.

［5］ McCreight E.Priority search trees［J］.SIAM Journal of Computing，1985，14（2）：257－276.

［6］ Xu J，Qiao C，Li J，et al.Efficient burst scheduling algorithms in optical burstswitched networks using geometric techniques［J］.IEEE Journal on Selected Areas in Communications，2004，22（9）：1796－1811.

［7］ Figueiredo R J，Boykin P O，Juste P S，et al.Social VPNs：integrating overlay and social networks for seamless P2P networking［C］／／IEEE WETICE／COPS，2008：93－98.

［8］ Sotomayor B，Keahey K，F(xiàn)oster I.Combining batch execution and leasing using virtual machines［C］／／HPDC′08 Proceedings of the 17th International Symposium on High Performance Distributed Computing，2008：87－96.

［9］ Matsunaga A，Tsugawa M，F(xiàn)ortes J.CloudBLAST：combining mapreduce and virtualization on distributed resources for bioinformatics applications［C］／／IEEE Fourth International Conference，2008：222－229.