摘 要: 在高性能計(jì)算集群中,,優(yōu)秀的作業(yè)調(diào)度軟件和作業(yè)調(diào)度策略對(duì)系統(tǒng)的高效運(yùn)行起著至關(guān)重要的作用,,目前針對(duì)作業(yè)調(diào)度策略的研究多集中在單個(gè)策略的深入挖掘,少有整合多個(gè)策略考慮的文章,。針對(duì)集群作業(yè)的運(yùn)行特點(diǎn),,提出了一種基于節(jié)點(diǎn)負(fù)載情況自定義優(yōu)先級(jí)回填的調(diào)度策略,可以有效提高性能和計(jì)算集群的運(yùn)行效率,。
關(guān)鍵詞: 作業(yè)調(diào)度,;自定義優(yōu)先級(jí);回填策略,;Torque FCFS
0 引言
集群的使用在高性能計(jì)算中并不鮮見,。在高性能計(jì)算中,大部分是并行批處理作業(yè),,對(duì)于集群的高效運(yùn)轉(zhuǎn),,優(yōu)良的作業(yè)調(diào)度軟件以及調(diào)度策略顯得至關(guān)重要[1-2]。目前已有很多集群作業(yè)管理系統(tǒng),,具有代表性的有Wisconsin-Madison大學(xué)的Cordor,、IBM公司的Platform LSF、Altair公司的PBS pro以及開源軟件Torque,,其中,,Cordor是科研項(xiàng)目,LSF和PBS pro是商業(yè)軟件,,而Torque是開源項(xiàng)目,。它們各有特點(diǎn)[3],Cordor比較全面地實(shí)現(xiàn)了檢查點(diǎn)的操作,;LSF和PBS pro雖然較為完備,,但是使用它們需要購(gòu)買昂貴的license;而Torque由于是開源項(xiàng)目,正如Linux系統(tǒng)一樣,,有全球數(shù)量眾多的Linux系統(tǒng)愛好者的強(qiáng)大支持,,并且它提供靈活的作業(yè)調(diào)度策略和用戶身份認(rèn)證機(jī)制,所以本文采用Torque作為作業(yè)調(diào)度軟件來研究,。與此同時(shí),,由于文中的測(cè)試作業(yè)對(duì)運(yùn)行時(shí)間和IO吞吐率有較高的要求,因此還需要對(duì)Torque進(jìn)行二次開發(fā),,加入新提出的調(diào)度策略,,并通過與自帶的調(diào)度策略進(jìn)行對(duì)比,體現(xiàn)該調(diào)度策略的優(yōu)越性,。
1 Torque的基本架構(gòu)和工作原理
Torque原名為PBS(Portable Batch System),,是由美國(guó)國(guó)家宇航局(NASA)Ames研究中心、勞倫斯利物莫國(guó)家實(shí)驗(yàn)室(Lawrence Livermore National Laboratory)以及墨綠信息解決公司(Veridian Information Solutions,,Inc)牽頭發(fā)起的一項(xiàng)針對(duì)高并發(fā),、大數(shù)據(jù)量作業(yè)調(diào)度的科研項(xiàng)目[4]。該作業(yè)調(diào)度軟件自帶FIFO類型的作業(yè)調(diào)度器pbs_sched,,同時(shí)也支持其他調(diào)度器,,本文就是采用目前較為流行的Maui調(diào)度器。目前PBS分為兩部分:由Altair公司經(jīng)營(yíng)的商業(yè)版PBS pro和由Adapting Computing公司運(yùn)營(yíng)的Torque,,后者開源,,并支持使用其他調(diào)度器替換自帶的pbs_sched,更適宜用來研究,,而且也支持復(fù)雜的自定義調(diào)度策略,,能滿足本課題的需求。
1.1 Torque的體系結(jié)構(gòu)
如圖1所示,,Torque使用一個(gè)主主機(jī),、任意多的執(zhí)行主機(jī)以及作業(yè)提交主機(jī),,主主機(jī)是Torque集群的中央管理者,。一臺(tái)主機(jī)既可以被設(shè)置成主主機(jī),也可以被設(shè)置成執(zhí)行主機(jī),。通常情況下將提交主機(jī)與主主機(jī)合并,。
1.2 Torque的工作原理
Torque能正常調(diào)度作業(yè),需要啟動(dòng)pbs_server,、psb_mom和pbs_sched(本文采用Maui調(diào)度器mauid)三個(gè)守護(hù)進(jìn)程,。
1.2.1 pbs_server進(jìn)程
psb_server是在主主機(jī)上執(zhí)行的進(jìn)程,是批處理系統(tǒng)的核心,,在集群中只有一個(gè),,它的主要功能有:提供一些基本的批處理服務(wù),接收/創(chuàng)建一個(gè)批處理作業(yè)、修改作業(yè),,在系統(tǒng)崩潰時(shí)保護(hù)作業(yè),,將用戶請(qǐng)求送達(dá)pbs_mom進(jìn)程并進(jìn)行交互等。
1.2.2 pbs_mom進(jìn)程
pbs_mom是在執(zhí)行主機(jī)上運(yùn)行的進(jìn)程,,如果需要主主機(jī)也進(jìn)行計(jì)算操作,,則主主機(jī)上也需要運(yùn)行該進(jìn)程,它負(fù)責(zé)收集執(zhí)行主機(jī)上的系統(tǒng)資源,。pbs_mom的主要作用是在pbs_server進(jìn)程的指令下啟動(dòng),、監(jiān)控和終止作業(yè)。
1.2.3 pbs_sched進(jìn)程
pbs_sched運(yùn)行在主主機(jī)上,,它的作用是決定什么時(shí)候在什么地方運(yùn)行作業(yè),。它從psb_server進(jìn)程請(qǐng)求作業(yè)狀態(tài)信息,從pbs_mom進(jìn)程請(qǐng)求資源狀態(tài)信息,,然后決定如何調(diào)度作業(yè),。Maui調(diào)度器的進(jìn)程mauid與pbs_sched類似,不再贅述,。
1.2.4 Torque處理批作業(yè)的過程
在Torque中,,三個(gè)進(jìn)程分工明確,三者通過Socket彼此通信,,一方面能使主主機(jī)快速將用戶作業(yè)需求分派下去,,另一方面也能實(shí)時(shí)監(jiān)控集群系統(tǒng)信息。圖2展示了Torque的內(nèi)部結(jié)構(gòu)原理,。
整個(gè)作業(yè)調(diào)度的過程分析如下:
?。?)用戶提交作業(yè)請(qǐng)求到Torque的Server端;
?。?)Server端根據(jù)作業(yè)需求向調(diào)度器Scheduler發(fā)起詢問,;
(3)調(diào)度器通過Socket與執(zhí)行器Mom通信以獲取節(jié)點(diǎn)資源信息,;
?。?)執(zhí)行器中的首節(jié)點(diǎn)Mom Superior向Scheduler返回集群節(jié)點(diǎn)資源信息,包括可用內(nèi)存量,、CPU負(fù)載信息等,;
(5)Scheduler檢查作業(yè)隊(duì)列并為作業(yè)分配資源,,同時(shí)將作業(yè)ID傳遞給Server,;
(6)Server通過Socket通知首節(jié)點(diǎn)Mom Superior去執(zhí)行批處理作業(yè)腳本的命令,;
?。?)作業(yè)執(zhí)行完成后,Mom將結(jié)果信息返回給Server端;
?。?)Server端根據(jù)預(yù)先設(shè)定的方法將作業(yè)結(jié)果返回給用戶,。
2 Torque默認(rèn)的調(diào)度器
Torque自身集成一個(gè)簡(jiǎn)單的基于C語(yǔ)言的FIFO調(diào)度器,并且提供源代碼,,實(shí)際應(yīng)用當(dāng)中Torque大都另外集成了別的調(diào)度器,,本文采用的是常用的Maui調(diào)度器。
Torque自帶調(diào)度器調(diào)度流程圖如圖3所示,。Torque自帶的FIFO調(diào)度器其實(shí)并不是真正意義上的先進(jìn)先出,,它是追求CPU的最大利用率[5]。實(shí)際上它的原理與FirstFit策略類似,,即掃描作業(yè)請(qǐng)求,,執(zhí)行集群現(xiàn)有資源能滿足的第一個(gè)作業(yè)[6]。該策略可能會(huì)使大作業(yè)(需求資源較多)遲遲得不到運(yùn)行,,因此會(huì)產(chǎn)生饑餓現(xiàn)象,。為了克服此問題,F(xiàn)IFO引入了饑餓作業(yè)調(diào)度方法,,當(dāng)某一作業(yè)在隊(duì)列中等待時(shí)間超過一定閾值(默認(rèn)是24小時(shí))時(shí),,會(huì)對(duì)所需資源進(jìn)行預(yù)約,故能解決大作業(yè)的饑餓等待,。但同時(shí)出現(xiàn)一個(gè)問題,,被預(yù)約的資源不能被別的作業(yè)使用,這樣就喪失了集群的整體公平性,,作業(yè)間的時(shí)間空隙沒有得到有效利用,。可見,,Torque自帶的調(diào)度器功能有限,,因此,集成其他更優(yōu)秀的調(diào)度器以及采用更為優(yōu)化的調(diào)度策略顯得尤為重要,。
3 基于節(jié)點(diǎn)負(fù)載情況自定義優(yōu)先級(jí)回填策略
給提交的作業(yè)預(yù)先設(shè)定優(yōu)先級(jí),,并根據(jù)優(yōu)先級(jí)對(duì)提交的作業(yè)進(jìn)行排隊(duì),然后再按照隊(duì)列中的作業(yè)順序依據(jù)FCFS的方式執(zhí)行作業(yè)[1],。這種方法有一個(gè)弊端,,即優(yōu)先級(jí)在作業(yè)提交時(shí)就已經(jīng)被設(shè)定了,,如果high priority的作業(yè)的需求資源遠(yuǎn)高于集群現(xiàn)有可用資源,,該作業(yè)就會(huì)長(zhǎng)時(shí)間處于等待狀態(tài)。為解決此問題,,提出了新的策略約定,,當(dāng)某一大作業(yè)的等待時(shí)間超過預(yù)設(shè)的閾值時(shí),就對(duì)需求資源進(jìn)行預(yù)約,同時(shí),,計(jì)算出多個(gè)預(yù)約作業(yè)之間的時(shí)間空隙,,將隊(duì)列中一些資源需求小的作業(yè)插入到其中執(zhí)行。該策略總體的執(zhí)行過程如圖4所示,。
3.1 節(jié)點(diǎn)負(fù)載情況的計(jì)算
節(jié)點(diǎn)的負(fù)載情況很大程度上影響作業(yè)調(diào)度系統(tǒng)對(duì)資源的選取,,負(fù)載大的節(jié)點(diǎn)計(jì)算出的資源評(píng)估值應(yīng)該較小,表示越不容易被選中執(zhí)行作業(yè),。資源選擇是一個(gè)作業(yè)從資源列表(Rselected)中選擇資源的過程,,因此,就需要給出一個(gè)算法,,幫助調(diào)度系統(tǒng)選擇執(zhí)行某一作業(yè)的最優(yōu)資源,。資源選擇所使用的算法應(yīng)能從目前的資源狀態(tài)考慮,并能根據(jù)一定的計(jì)算公式來算出最適宜的資源,。由于現(xiàn)實(shí)中選擇作業(yè)運(yùn)行資源最關(guān)注的往往是CPU和內(nèi)存的利用率,,因此本文提出的選擇資源的算法主要考慮節(jié)點(diǎn)的CPU和RAM,計(jì)算公式定義如下:
其中,,WCPU代表分配給CPU速率的權(quán)重,,CPUload代表目前CPU的負(fù)載,CPUspeed代表CPU的實(shí)際速率,,CPUmin是CPU的速率最小值,,WRAM是分配給RAM的權(quán)重,RAMusage是當(dāng)前RAM使用率,,RAMsize是RAM的原始容量,,RAMmin是最小的RAM值。
下面給出一個(gè)實(shí)際的例子,,根據(jù)上面給出的負(fù)載計(jì)算公式從三組候選的資源中選擇一種資源,,假設(shè)每種資源的相關(guān)參數(shù)如表1所示。
假設(shè)該算法中整個(gè)權(quán)重為10,,其中CPU權(quán)重為6,,RAM的權(quán)重為4。設(shè)定CPU速率最小值為1 GHz,,RAM最小值為1 024 MB,,將值代入式(1)~(3),可得資源負(fù)載估計(jì)值如下:
從負(fù)載估計(jì)值來看,,資源3為最優(yōu)執(zhí)行資源,。
3.2 作業(yè)優(yōu)先級(jí)的確定
提交作業(yè)的優(yōu)先級(jí)不僅與作業(yè)類型、作業(yè)所需資源類型及多少有關(guān),,還與作業(yè)提交后等待執(zhí)行所花的時(shí)間有關(guān),,等待時(shí)間越長(zhǎng),,作業(yè)在隊(duì)列中的優(yōu)先級(jí)應(yīng)該越高,表示該作業(yè)越易被執(zhí)行,。當(dāng)然,,還需要設(shè)定一個(gè)優(yōu)先級(jí)閾值,當(dāng)優(yōu)先級(jí)超過這個(gè)閾值后,,系統(tǒng)將對(duì)該作業(yè)所需資源進(jìn)行預(yù)約,。
定義 提交作業(yè)的優(yōu)先級(jí)公式為:
其中,Y是提交者與管理員共同商議的作業(yè)預(yù)設(shè)優(yōu)先級(jí),,k為常數(shù)權(quán)重因子,,twait為作業(yè)等待的時(shí)間(以min計(jì)),Eresource為資源負(fù)載情況,,Pth為預(yù)設(shè)優(yōu)先級(jí)閾值,。由式(4)可知,等待時(shí)間越長(zhǎng),,負(fù)載估值越大,,作業(yè)優(yōu)先級(jí)越大,表示該作業(yè)越易被執(zhí)行,。作業(yè)的實(shí)際優(yōu)先級(jí)需要將式(4)中前半部分與預(yù)設(shè)的優(yōu)先級(jí)進(jìn)行比較,,取較小者,如果計(jì)算值大于閾值,,則系統(tǒng)對(duì)所需資源進(jìn)行預(yù)約,。
假設(shè)目前集群中可用資源為資源1,現(xiàn)在有作業(yè)1,、作業(yè)2,、作業(yè)3共三個(gè)作業(yè)提交,預(yù)設(shè)優(yōu)先級(jí)為10,、15,、8,預(yù)設(shè)的優(yōu)先級(jí)閾值為55,,權(quán)重因子k=1,,等待時(shí)間為120 s、100 s,、238 s,,根據(jù)式(4)可計(jì)算出三個(gè)作業(yè)的優(yōu)先級(jí)分別為P1=12.500,P2=17.083,,P3=12.958,,三者均小于預(yù)設(shè)優(yōu)先級(jí)閾值,不需對(duì)資源進(jìn)行預(yù)約,,故根據(jù)前述定義可知,,三個(gè)作業(yè)的執(zhí)行順序?yàn)樽鳂I(yè)2→作業(yè)3→作業(yè)1,。
3.3 回填策略的設(shè)計(jì)
上節(jié)提到的案例中,,三個(gè)作業(yè)經(jīng)過計(jì)算得出的優(yōu)先級(jí)都沒有超過優(yōu)先級(jí)閾值,,故沒有對(duì)資源進(jìn)行預(yù)約。如果超過了閾值,,就需要對(duì)集群資源進(jìn)行預(yù)約,,被預(yù)約的資源不能再分配給別的作業(yè)使用,這種要求就容易造成多個(gè)作業(yè)間時(shí)間空隙被浪費(fèi)的現(xiàn)象,,而通過引入回填策略,,就能很好地解決這個(gè)問題,這里主要介紹一下回填策略的設(shè)計(jì),。
假設(shè)集群里的資源(處理器數(shù)目)有限,,目前有三個(gè)大小不等的作業(yè)在運(yùn)行,隊(duì)列中還有兩個(gè)作業(yè)在排隊(duì),,默認(rèn)的FCFS策略,,排隊(duì)的作業(yè)會(huì)等待前三個(gè)作業(yè)都運(yùn)行結(jié)束后再進(jìn)入集群執(zhí)行,但如果引入了回填策略,,則系統(tǒng)會(huì)先掃描集群中運(yùn)行的作業(yè)之間是否存在時(shí)間間隙,,然后再據(jù)排隊(duì)作業(yè)所需資源的多少和預(yù)估時(shí)間,將排隊(duì)的作業(yè)插到空閑周期中運(yùn)行,,這樣能充分利用資源,,提高集群吞吐率。具體過程示意圖如圖5所示,。
由圖5可知,,加入回填策略后,當(dāng)作業(yè)等待時(shí)間超過一定值(可以設(shè)定一個(gè)等待時(shí)間閾值)后,,系統(tǒng)會(huì)掃描全部隊(duì)列,,選擇作業(yè)預(yù)估時(shí)間小于空閑周期時(shí)間的作業(yè)插入空閑周期執(zhí)行,充分利用了集群的空閑周期,,減少作業(yè)等待時(shí)間,。
3.4 新型調(diào)度策略與默認(rèn)調(diào)度策略對(duì)比
上文已經(jīng)提過,Torque自帶的FIFO調(diào)度器實(shí)際上原理與FirstFit策略類似,,即在隊(duì)列中選擇當(dāng)前系統(tǒng)資源能滿足的第一個(gè)作業(yè)執(zhí)行,。測(cè)試集群環(huán)境為4臺(tái)IBM PureFlex X240刀片式服務(wù)器,1臺(tái)作為主主機(jī),,其他3臺(tái)作為執(zhí)行主機(jī),,所有機(jī)器上都裝好了Torque和Maui,在Maui的配置文件maui.cfg中添加新策略設(shè)置,。對(duì)比測(cè)試中,,將作業(yè)響應(yīng)時(shí)間作為衡量指標(biāo),,它代表從作業(yè)提交到作業(yè)開始執(zhí)行所花時(shí)間。測(cè)試時(shí),,構(gòu)建了三個(gè)測(cè)試作業(yè)集,,分別有1 000、1 500,、2 000個(gè)作業(yè),,為了方便,統(tǒng)一設(shè)定預(yù)設(shè)優(yōu)先級(jí)為0,,常數(shù)權(quán)重因子為1,,預(yù)設(shè)優(yōu)先級(jí)閾值為55。不同策略的作業(yè)響應(yīng)時(shí)間對(duì)比如圖6所示,。因?yàn)榛诠?jié)點(diǎn)負(fù)載情況自定義優(yōu)先級(jí)回填策略兼顧了公平性和高效性,,既有優(yōu)先級(jí)設(shè)置,也有回填策略考慮,,所以相比于FirstFit的調(diào)度策略,,在排隊(duì)作業(yè)較多時(shí),作業(yè)響應(yīng)時(shí)間有明顯的提升,,由圖6可知,,作業(yè)數(shù)目為1 000、1 500,、2 000時(shí),,作業(yè)響應(yīng)時(shí)間分別減少了26.1%、13.2%和12.5%,。
4 結(jié)論
本文提出了一種基于節(jié)點(diǎn)負(fù)載自定義優(yōu)先級(jí)回填策略,,它能根據(jù)節(jié)點(diǎn)負(fù)載計(jì)算出資源評(píng)估參數(shù),結(jié)合作業(yè)的預(yù)設(shè)優(yōu)先級(jí)及等待時(shí)間,,得出相應(yīng)優(yōu)先級(jí)參數(shù),,將各作業(yè)按照此優(yōu)先級(jí)排序,逐個(gè)執(zhí)行,。當(dāng)作業(yè)優(yōu)先級(jí)超過閾值時(shí),,系統(tǒng)將對(duì)作業(yè)所需資源進(jìn)行預(yù)約,在預(yù)約過程中,,已運(yùn)行的作業(yè)之間可能會(huì)產(chǎn)生時(shí)間空隙,,這時(shí)根據(jù)回填策略設(shè)置,系統(tǒng)掃描作業(yè)間隙,,將作業(yè)預(yù)估時(shí)間小于時(shí)間間隙的作業(yè)投入到集群中執(zhí)行,,以達(dá)到充分利用集群資源、增大集群吞吐率的目的,。通過作業(yè)響應(yīng)時(shí)間的對(duì)比可以看到,,基于節(jié)點(diǎn)負(fù)載情況自定義優(yōu)先級(jí)回填策略比默認(rèn)的調(diào)度策略在作業(yè)響應(yīng)時(shí)間上有較好的提升,。
參考文獻(xiàn)
[1] 劉萍.作業(yè)調(diào)度算法研究[J].現(xiàn)代計(jì)算機(jī),2012,,10(1):15-17.
[2] 蘭文富,,羅江華,程克非.集群系統(tǒng)的資源調(diào)度管理實(shí)現(xiàn)[J].科技創(chuàng)新導(dǎo)報(bào),,2011,,24(4):43-44.
[3] 童瑞,,董小社,,李紀(jì)云,等.基于OpenPBS的機(jī)群作業(yè)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,,2004,,13(2):123-125.
[4] 張麗曉,袁立強(qiáng),,徐煒民.基于任務(wù)類型的集群調(diào)度策略[J].計(jì)算機(jī)工程,,2004,7(30):63-64.
[5] BRIM M,,GEIST A,, LUETHKE B, et al. M3C: managing and monitoring multiple cluster[C]. Proceedings of the First IEEE/ACM International Symposium on Cluster Computing and the Grid,, 2001:386-393.
[6] 王陽(yáng),,周智力,盧康.高性能計(jì)算集群調(diào)度策略優(yōu)化及應(yīng)用程序并行效率研究[J].高科技產(chǎn)品研發(fā),,2013,,20(2):31-32.