桂兵祥,何 健

(武漢工業(yè)學(xué)院計(jì)算機(jī)與信息工程系,湖北武漢 430023)

用于虛擬計(jì)算中心的交互式作業(yè)調(diào)度策略

桂兵祥,何 健

(武漢工業(yè)學(xué)院計(jì)算機(jī)與信息工程系,湖北武漢 430023)

描述了一個(gè)用于虛擬計(jì)算中心,旨在加強(qiáng)為交互式作業(yè)及時(shí)分配資源的調(diào)度算法,該算法基于搶占式作業(yè)調(diào)度策略,能快速將資源分配給交互式作業(yè),且能使資源被搶占的作業(yè)很容易重新恢復(fù)運(yùn)行。通過(guò)模擬計(jì)算中心運(yùn)行環(huán)境測(cè)試,實(shí)驗(yàn)結(jié)果表明：這個(gè)調(diào)度算法不僅對(duì)交互式作業(yè)的資源及時(shí)分配有顯著的改善,提高了資源利用率,而且還大大縮短了批處理作業(yè)的響應(yīng)時(shí)間。

虛擬計(jì)算中心;交互式作業(yè);資源搶占;調(diào)度策略

隨著超級(jí)計(jì)算機(jī)運(yùn)算速度的不斷提高,計(jì)算機(jī)的應(yīng)用也隨之發(fā)生了相應(yīng)的變化。在下一代超級(jí)計(jì)算機(jī)中,交互式作業(yè)將扮演更為重要的角色。傳統(tǒng)的超級(jí)計(jì)算主要集中在脫機(jī)可視化及交互式批處理作業(yè),而交互式計(jì)算則尋求為用戶實(shí)時(shí)地提供資源,以實(shí)現(xiàn)計(jì)算和交互同步,這就需要為處理超級(jí)計(jì)算資源提高新的資源分配策略。

交互式超級(jí)計(jì)算要求對(duì)現(xiàn)有的調(diào)度算法、處理器管理和數(shù)據(jù)管理等進(jìn)行改進(jìn),新的調(diào)度策略極為關(guān)鍵的要求就是能實(shí)現(xiàn)交互式資源的按需分配和及時(shí)回收資源以再分配。對(duì)于數(shù)據(jù)中心和計(jì)算機(jī)集群處理器管理,這個(gè)要求是必須的,因?yàn)榕幚碜鳂I(yè)必須是資源可搶占式分配的,以確保交互式作業(yè)對(duì)資源的實(shí)時(shí)需求。數(shù)據(jù)管理也十分重要,因?yàn)橘Y源被搶占的批處理作業(yè)和交互式作業(yè)所產(chǎn)生的數(shù)據(jù),必須對(duì)其實(shí)施有效的管理。

目前,相關(guān)理論界對(duì)交互式超級(jí)計(jì)算還未引起足夠的重視,現(xiàn)有的批處理調(diào)度算法對(duì)交互式作業(yè)僅僅是事后而非實(shí)時(shí)處理。新的調(diào)度策略核心就是使用具有系統(tǒng)開(kāi)銷低的虛擬策略,以提供計(jì)算遷移和檢查點(diǎn)的結(jié)構(gòu)體系。這些特性對(duì)實(shí)現(xiàn)實(shí)時(shí)交互式計(jì)算來(lái)說(shuō)是特別重要的,同時(shí)也容許那些資源被搶占的作業(yè)恢復(fù)運(yùn)行,使其計(jì)算損失最小化。然而虛擬策略的應(yīng)用也需要有效的資源供給系統(tǒng),供給系統(tǒng)的框架結(jié)構(gòu)應(yīng)該與調(diào)度算法協(xié)作,以有效地預(yù)測(cè)作業(yè)請(qǐng)求而不提供并不需要的、多余的資源。如今很多虛擬機(jī)(VM)供應(yīng)系統(tǒng)僅僅只是簡(jiǎn)單地交換操作系統(tǒng)(OS)而沒(méi)有考慮資源使用趨勢(shì)。這導(dǎo)致了VM交換的浪費(fèi)且降低了計(jì)算機(jī)集群的利用率。

1 目前相關(guān)研究工作現(xiàn)狀

有關(guān)多處理機(jī)系統(tǒng)的任務(wù)調(diào)度已經(jīng)有了充分的研究。為了使計(jì)算機(jī)集群的總體完工時(shí)間或作業(yè)的最后完成時(shí)間最小化,有人建議使用近似算法和啟發(fā)式算法。但是,大多數(shù)算法沒(méi)有考慮資源的搶占式分配,有的忽略了在線實(shí)時(shí)系統(tǒng)中潛在的作業(yè)饑餓現(xiàn)象。下面將對(duì)上面提到的近似算法簡(jiǎn)要地加以討論。

到目前為止,大多數(shù)調(diào)度算法都集中在資源的非搶占式分配及其變種,作業(yè)被分派給眾多節(jié)點(diǎn)(或平行計(jì)算機(jī))得以運(yùn)行完成。這導(dǎo)致了大量的近似算法。在最近的調(diào)度算法研究工作中,Genetic算法獲得了特別充分的研究[1-2],其它的調(diào)度策略包括線性編程、基于嵌入式的啟發(fā)式算法、模擬退火算法等。Jin等人對(duì)眾多不同的近似調(diào)度算法做了比較性研究,結(jié)果表明大多數(shù)現(xiàn)有的算法更適合脫機(jī)非實(shí)時(shí)的作業(yè)調(diào)度[3]。研究者們也考慮過(guò)搶占式調(diào)度方案,一個(gè)常見(jiàn)的策略就是將問(wèn)題轉(zhuǎn)換為非搶占式調(diào)度問(wèn)題,這事實(shí)只不過(guò)是近似算法的改進(jìn)版本。

Sotomayor等人研究了虛擬技術(shù)的額外開(kāi)銷[4],他們特別指出,當(dāng)將虛擬技術(shù)整合到網(wǎng)格作業(yè)調(diào)度時(shí),實(shí)例化和配置操作的額外開(kāi)銷必須要正確地加于計(jì)算。本文描述的搶占式調(diào)度算法不僅考慮了這個(gè)額外開(kāi)銷,而且還計(jì)算了檢查點(diǎn)和作業(yè)遷移的額外開(kāi)銷。

Sotomayor等人進(jìn)一步研究了基于租用以提前預(yù)約資源請(qǐng)求的調(diào)度方案,其不是基于特別的作業(yè)調(diào)度決策,而是基于租用的決策,租用描述了應(yīng)用對(duì)硬件和軟件資源的請(qǐng)求。Foster等人先前對(duì)應(yīng)用于網(wǎng)格資源調(diào)度的提前預(yù)約方式進(jìn)行了研究[5]。Sotomayor等人使用了虛擬技術(shù)以提供必需的檢查點(diǎn)/恢復(fù)功能。然而,本文所描述的用以支持作業(yè)交互式技術(shù)的搶占式調(diào)度策略不是基于提前預(yù)約思想。

2 交互式調(diào)度策略的原型系統(tǒng)構(gòu)架與設(shè)計(jì)

應(yīng)用新的交互式調(diào)度算法開(kāi)發(fā)一個(gè)系統(tǒng)原型,使其能有效評(píng)估類似于生產(chǎn)環(huán)境的模型和假設(shè)。使用了虛擬的計(jì)算機(jī)集群,其通過(guò)網(wǎng)絡(luò)與一臺(tái)用于處理節(jié)點(diǎn)供應(yīng)的服務(wù)器相連接。這個(gè)框架結(jié)構(gòu)基于Torque批處理調(diào)度方案,其實(shí)現(xiàn)包含資源管理器、調(diào)度程序、可擴(kuò)展的 OS分配器和VM調(diào)用框架。

2.1 資源管理器

資源管理器負(fù)責(zé)為批處理作業(yè)和分布式計(jì)算節(jié)點(diǎn)提供控制機(jī)制,并維護(hù)一個(gè)所有計(jì)算機(jī)集群節(jié)點(diǎn)的注冊(cè)表和屬性,這些屬性影響著調(diào)度程序的節(jié)點(diǎn)供應(yīng)決策。此工作是由MOM(面向機(jī)器的微型服務(wù)器)后臺(tái)程序完成的,其定期核查計(jì)算機(jī)集群節(jié)點(diǎn),以獲得這些節(jié)點(diǎn)的狀態(tài)。

資源管理器代表性地表示為一個(gè)節(jié)點(diǎn),其包含IP地址、運(yùn)行狀態(tài)和基本的操作系統(tǒng)等屬性集合?；镜牟僮飨到y(tǒng)屬性指明了物理服務(wù)器上所運(yùn)行的操作系統(tǒng)。本例中引進(jìn)一個(gè)新的屬性——VM即虛擬機(jī),它指客戶虛擬機(jī)操作系統(tǒng)。這個(gè)節(jié)點(diǎn)屬性是動(dòng)態(tài)的,當(dāng) VM被調(diào)用時(shí),其必將發(fā)生變化。

為了容許虛擬客戶機(jī)能像傳統(tǒng)的客戶機(jī)一樣運(yùn)行,MOM后臺(tái)程序被加入到客戶端,這有效地從虛擬機(jī)創(chuàng)造了一個(gè)獨(dú)立的客戶端,容許調(diào)度程序把一個(gè)獨(dú)立的VM作為完全的客戶端來(lái)處理。

通過(guò)合并這些屬性,計(jì)算機(jī)集群能表示為一個(gè)虛擬資源池,這樣,任何含有獨(dú)特的資源集合請(qǐng)求的作業(yè)都能夠從這個(gè)資源池中得到服務(wù)。通過(guò)這種方法,計(jì)算機(jī)集群僅僅受限于其可獲得的硬件資源,而不是軟件。任何用戶都可能快速地獲得其所需的軟件資源。

2.2 調(diào)度策略

調(diào)度程序負(fù)責(zé)已進(jìn)入作業(yè)隊(duì)列的作業(yè)調(diào)度,并考慮計(jì)算機(jī)集群空閑資源的有效使用,以滿足作業(yè)的資源請(qǐng)求。當(dāng)作業(yè)進(jìn)入作業(yè)隊(duì)列時(shí),從作業(yè)屬性中計(jì)算一個(gè)初始優(yōu)先數(shù),在作業(yè)被放入調(diào)度作業(yè)隊(duì)列前,資源管理器將對(duì)該優(yōu)先級(jí)進(jìn)行分析,所采用的調(diào)度策略用以下公式示：

其中,Ttartet是用戶的期望使用時(shí)間,Tusag是用戶的實(shí)際使用時(shí)間;Qtime作業(yè)在隊(duì)列中等待耗費(fèi)的時(shí)間;Navailable OS是指可獲得的帶有給定 OS的節(jié)點(diǎn)數(shù);Nreg OS是指帶有作業(yè)所需的特定 OS的節(jié)點(diǎn)數(shù);Pn是指作業(yè)被搶占時(shí)間次數(shù);Pt是指作業(yè)被搶占的時(shí)間總數(shù);Nfree是指帶有任意 OS的空閑節(jié)點(diǎn)總數(shù);如果作業(yè)是交互的,I取值為 1,否則取 0;W1、W2…W6是權(quán)重因子,是經(jīng)驗(yàn)值;W7是提升交互作業(yè)的權(quán)重因子。

通過(guò)說(shuō)明所用的 OS和免費(fèi)的資源,減少 OS交換的次數(shù),可以改善調(diào)度效果。(Ttartet-Tusag)簡(jiǎn)單地描述了用戶的現(xiàn)實(shí)使用時(shí)間,如果用戶一直不是特別活躍,則此值將大于那些活躍的用戶。Qtime簡(jiǎn)單描述了作業(yè)在調(diào)度前耗費(fèi)在等待隊(duì)列中的時(shí)間,當(dāng)一個(gè)作業(yè)處于等待狀態(tài)時(shí),其 Qtime值將增加從而優(yōu)先級(jí)增加。Navailable OS-Nreg OS說(shuō)明了計(jì)算機(jī)集群內(nèi)OS的現(xiàn)實(shí)分配情況。如果是負(fù)值則表示正在請(qǐng)求的節(jié)點(diǎn)將要求資源供給,這降低了作業(yè)的優(yōu)先級(jí)。為了防止因資源被搶占而形成饑餓現(xiàn)象,公式 (1)中增加了 Pn值作為搶占增加的次數(shù),因而當(dāng)搶占頻繁發(fā)生時(shí),作業(yè)的優(yōu)先級(jí)增加;Pt也是如此。W1、W2…W6等權(quán)重值由模擬環(huán)境下經(jīng)驗(yàn)值決定,其具體值依賴于所采用的各式各樣的調(diào)度策略;W7也是經(jīng)驗(yàn)值,但其值可以比其它值大得多,以快速提高互動(dòng)作業(yè)的優(yōu)先級(jí)。

2.3 VM供應(yīng)框架與作業(yè)搶占機(jī)制

一旦調(diào)度程序識(shí)別了那些能為新作業(yè)提供服務(wù)的空閑節(jié)點(diǎn),則必要的OS像圖將提供給VM調(diào)用框架。查詢、檢索 OS像圖可用平衡二叉樹(shù)結(jié)構(gòu)。所有的OS像圖最初都存儲(chǔ)在頭節(jié)點(diǎn)處。當(dāng)有節(jié)點(diǎn)對(duì)某一特定的 OS像圖發(fā)出請(qǐng)求時(shí),所需的 OS像圖通過(guò)該頭節(jié)點(diǎn)的子節(jié)點(diǎn)發(fā)送到有相應(yīng)資源需求的節(jié)點(diǎn)。所有該路徑上的節(jié)點(diǎn)在其路由表中都維持著該OS像圖所達(dá)節(jié)點(diǎn)的信息,當(dāng)另一個(gè)同樣的 OS像圖請(qǐng)求發(fā)生時(shí),可重復(fù)使用此路由表中的信息。一旦空閑節(jié)點(diǎn)接收到 OS像圖和配置,并交換文件,VM將被激活,MOM后臺(tái)程序在此 VM上啟動(dòng),控制權(quán)將被遞交給調(diào)度程序,能使該節(jié)點(diǎn)為所調(diào)度的作業(yè)服務(wù)。當(dāng)高優(yōu)先級(jí)的作業(yè)缺乏資源而不能運(yùn)行時(shí),一個(gè)或更多的作業(yè)所擁有資源必須被搶占以實(shí)現(xiàn)作業(yè)的交互性。實(shí)現(xiàn)資源搶占機(jī)制,有三個(gè)關(guān)鍵問(wèn)題需要解決：作業(yè)調(diào)度、檢查點(diǎn)和重啟作業(yè)。首要且最重要的是必須考慮作業(yè)調(diào)度方案和如何選擇被搶占的作業(yè)。在數(shù)據(jù)中心有數(shù)千個(gè)節(jié)點(diǎn)和作業(yè),好的搶占方案將是改善計(jì)算機(jī)集群響應(yīng)時(shí)間的關(guān)鍵,調(diào)度策略是通過(guò)上述式 (1)計(jì)算,優(yōu)先級(jí)最低的作業(yè)首先被搶占。一旦識(shí)別出可搶占的作業(yè),為了保存該作業(yè)的狀態(tài),必須設(shè)立一個(gè)相應(yīng)的檢查點(diǎn),以實(shí)現(xiàn)作業(yè)將來(lái)重啟,而不損失計(jì)算資源。如果作業(yè)正在分布式地執(zhí)行,那分布式的狀態(tài)也必須同步保存,并設(shè)檢查點(diǎn)。一旦互動(dòng)作業(yè)執(zhí)行完畢,被搶占的作業(yè)應(yīng)該重新得以執(zhí)行。

2.4 系統(tǒng)體系結(jié)構(gòu)

從用戶的角度看,系統(tǒng)主要由三個(gè)部件組成：調(diào)度程序 /資源管理器;VM存放庫(kù)/供應(yīng)框架;檢查點(diǎn) /遷移基礎(chǔ)結(jié)構(gòu)。

作業(yè)被提交給資源管理器,在此調(diào)度程序決定作業(yè)的優(yōu)先級(jí)并將其插入隊(duì)列中。依據(jù)作業(yè)類型,分兩種方式處理：如果是標(biāo)準(zhǔn)的批處理作業(yè),則收集作業(yè)所請(qǐng)求的資源,按典型的批處理方式處理,批處理作業(yè)一般不需搶占資源,一旦被調(diào)度,其可直接在一個(gè)或多個(gè) VM上運(yùn)行,資源管理器為其提供 VM。作業(yè)可能運(yùn)行完成,也可能在完成前被交互式作業(yè)搶占資源。

如果交互式作業(yè)被提交,其將獲得較高的優(yōu)先級(jí)。如果所需求的資源處于空閑狀態(tài),交互作業(yè)將立即被調(diào)度到空閑的節(jié)點(diǎn)上運(yùn)行;如果資源不處于空閑狀態(tài),將搶占其它作業(yè)的資源以滿足需求。搶占資源分多部完成：首先,受搶占的、正在運(yùn)行著的作業(yè)必須設(shè)立檢查點(diǎn),如果作業(yè)是單個(gè)節(jié)點(diǎn)運(yùn)行,則設(shè)立檢查點(diǎn)的過(guò)程很簡(jiǎn)單,且能在虛擬機(jī)內(nèi)部得以處理。如果作業(yè)在多節(jié)點(diǎn)運(yùn)行,則在設(shè)立 VM檢查點(diǎn)前,節(jié)點(diǎn)首先必須靜默所有的消息傳遞活動(dòng)。當(dāng)VM檢查點(diǎn)設(shè)立后,供應(yīng)框架將提供 VM,互動(dòng)作業(yè)將得以運(yùn)行。當(dāng)互動(dòng)作業(yè)完成后,被搶占的作業(yè)將繼續(xù)運(yùn)行。

3 實(shí)驗(yàn)結(jié)果與分析

通過(guò)與修改版的Maui FCFS調(diào)度策略 (MMS)做模擬對(duì)照實(shí)驗(yàn),獲得了一些交互式作業(yè)調(diào)度策略(UB IS)有用的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中使用了收集來(lái)自計(jì)算研究中心的跟蹤數(shù)據(jù)和 100000份作業(yè)的模擬運(yùn)行情況。操作系統(tǒng)隨機(jī)指派,跟蹤數(shù)據(jù)假設(shè)運(yùn)行在含有 1056個(gè)節(jié)點(diǎn)的計(jì)算機(jī)集群上。互動(dòng)作業(yè)以泊松分布隨機(jī)插入到跟蹤數(shù)據(jù)中,節(jié)點(diǎn)數(shù)為 50、100、150。插入互動(dòng)作業(yè)的執(zhí)行時(shí)間統(tǒng)一分配在10—120 min之間。在做互動(dòng)作業(yè)調(diào)度策略 (UB IS)與MMS對(duì)照試驗(yàn)時(shí),計(jì)算研究中心的計(jì)算機(jī)集群資源分 10%、20%、30%三個(gè)等級(jí)投入互動(dòng)作業(yè)的運(yùn)行。優(yōu)先級(jí)計(jì)算公式 (1)中,W1=0.07,W2=0.13,W3=0.1,W4=0.1,W5=0.16,W6=0.2,W7=0.24。

實(shí)驗(yàn)結(jié)果表明,交互作業(yè)機(jī)制的引進(jìn)能顯著改善系統(tǒng)資源利用率、響應(yīng)時(shí)間和吞吐量。實(shí)驗(yàn)中,UB IS調(diào)度方案比MMS調(diào)度方案在資源利用率方面顯得更為有效,這符合預(yù)期,因?yàn)楹笳邽榭色@得的節(jié)點(diǎn)預(yù)留系統(tǒng)資源,從而阻止一些新作業(yè)的執(zhí)行,直到高優(yōu)先級(jí)作業(yè)獲得其需要的資源。隨著計(jì)算機(jī)集群中互動(dòng)作業(yè)量及其比例的增加,響應(yīng)時(shí)間也隨之增加,這是所有調(diào)度策略所有的共性。然而,實(shí)驗(yàn)數(shù)據(jù)表明,從交互機(jī)制比例 10%、20%到 30%,UBIS的響應(yīng)時(shí)間與MMS相比,一直有明顯改進(jìn),,尤其是資源利用率,能提高 100%—300%,UB IS相對(duì)MMS性能提高對(duì)照數(shù)據(jù)如表1所示 (20%交互)。

表1 UBIS相對(duì)MM S性能提高對(duì)照表(20%交互)

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

現(xiàn)有的批處理調(diào)度算法不能充分解決交互式作業(yè)對(duì)資源的實(shí)時(shí)需求,本文討論的核心問(wèn)題是調(diào)度策略及算法,但也闡明了供給系統(tǒng)將是任何基于搶占式分配調(diào)度算法的 VM所應(yīng)有的至關(guān)重要的組件;同時(shí)也介紹了關(guān)于支持交互式超級(jí)計(jì)算所特有的調(diào)度算法的設(shè)計(jì)和實(shí)現(xiàn),并描述了有關(guān)的交互式框架結(jié)構(gòu),最后對(duì)該調(diào)度算法的性能進(jìn)行了初步評(píng)估與分析。

在傳統(tǒng)的超級(jí)計(jì)算機(jī)系統(tǒng)中,如何在單純的批處理作業(yè)計(jì)算模式下引入交互作業(yè)機(jī)制,是一個(gè)值得研究的課題。實(shí)驗(yàn)表明,交互式作業(yè)機(jī)制能被引進(jìn)到現(xiàn)有的調(diào)度程序中,負(fù)面影響代價(jià)很小;而且,真實(shí)的實(shí)驗(yàn)跟蹤數(shù)據(jù)顯示,交互式作業(yè)機(jī)制的引入,系統(tǒng)性能有顯著提高。這為各式各樣的非傳統(tǒng)應(yīng)用(如限時(shí)分析等問(wèn)題)打開(kāi)了一扇大門(mén),同時(shí)還為數(shù)據(jù)計(jì)算中心或供應(yīng)商提供了一條有效途徑,以提高其計(jì)算基礎(chǔ)設(shè)施利用率,從而降低開(kāi)銷、增加收益。

[1] Cheng S C,Huang Y M.Scheduling multiprocessor tasks with resource and timing constraintusing genetic algorithm [C]//Computational Intelligence in Robotics ans Automation. Cali USA： IEEE Computer Society,2003：624-629.

[2] Correa R C,Ferreira A,Rebreyend P.Scheduling Multiprocessor Tasks with Genetic Algorithms[J]. IEEE Trans Parallel Distrib Syst.1999,10(8)：825-837.

[3] Jin S,Schiavone G,Turgut D.A Performance Study of Multi-processsor Tast Scheduling Algorithms[J].Supercompute,2008,43(1)：77-79.

[4] Sotomayor B,Keahey K,Foster I.Overhead matters：A model for virtual resource management[C]//Proceedings of the 2ndInternational Workshop on Virtrualization Technology in Distributed.Cali USA：IEEE Computer Society,2006：328-336.

[5] Foster I,Lee C,Lindell B,et al.A distributed resource management architecture that supports advance reservation and co-allocation[C]//In Proceeding of the 7thInternational Workshop on Quality of Service. Syney Australia：IEEE Computer Society,1999：258-266.

An interactive jobs schedule strategy in virtualized compute centers

GUI Bing-xiang,HE Jian
(Department of Computer and Information Engineering,Wuhan Polytechnic University,Wuhan 430023,China)

The paper describes a scheduling algorithm for the virtual computing center,which is aimed at strengthening the timely allocation of resources for the interactive tasks.The algorithm is based on preemptive scheduling strategy and can quickly allocate resources to interactive tasks,and enable tasks whose resources have been preempted easily to resume running.Through computing center testing to run simulated environment,test results show that：the scheduling algorithm have improved not only timely allocation of resources interactive operations significantly,and improved resource utilization,but also greatly shortened the response time of a batch job.

virtual computing center;interactive operations;resource preemption;scheduling strategy

TP 393

A

1009-4881(2010)03-0075-04

10.3969/j.issn.1009-4881.2010.03.018

2009-12-20.

桂兵祥 (1969-),男,副教授,E-mail：gbxhome@163.com.