摘  要： 在高性能計(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ì)算中并不鮮見(jiàn),。在高性能計(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以及開(kāi)源軟件Torque，其中,，Cordor是科研項(xiàng)目,，LSF和PBS pro是商業(yè)軟件，而Torque是開(kāi)源項(xiàng)目,。它們各有特點(diǎn)[3],，Cordor比較全面地實(shí)現(xiàn)了檢查點(diǎn)的操作；LSF和PBS pro雖然較為完備,，但是使用它們需要購(gòu)買(mǎi)昂貴的license,；而Torque由于是開(kāi)源項(xiàng)目，正如Linux系統(tǒng)一樣,，有全球數(shù)量眾多的Linux系統(tǒng)愛(ài)好者的強(qiáng)大支持,，并且它提供靈活的作業(yè)調(diào)度策略和用戶身份認(rèn)證機(jī)制，所以本文采用Torque作為作業(yè)調(diào)度軟件來(lái)研究,。與此同時(shí),，由于文中的測(cè)試作業(yè)對(duì)運(yùn)行時(shí)間和IO吞吐率有較高的要求，因此還需要對(duì)Torque進(jìn)行二次開(kāi)發(fā),，加入新提出的調(diào)度策略,，并通過(guò)與自帶的調(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類(lèi)型的作業(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，后者開(kāi)源,，并支持使用其他調(diào)度器替換自帶的pbs_sched,，更適宜用來(lái)研究，而且也支持復(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類(lèi)似,，不再贅述,。

　　1.2.4 Torque處理批作業(yè)的過(guò)程

　　在Torque中，三個(gè)進(jìn)程分工明確,，三者通過(guò)Socket彼此通信,，一方面能使主主機(jī)快速將用戶作業(yè)需求分派下去，另一方面也能實(shí)時(shí)監(jiān)控集群系統(tǒng)信息,。圖2展示了Torque的內(nèi)部結(jié)構(gòu)原理,。

　　整個(gè)作業(yè)調(diào)度的過(guò)程分析如下：

　　（1）用戶提交作業(yè)請(qǐng)求到Torque的Server端,；

　　（2）Server端根據(jù)作業(yè)需求向調(diào)度器Scheduler發(fā)起詢問(wèn),；

　?。?）調(diào)度器通過(guò)Socket與執(zhí)行器Mom通信以獲取節(jié)點(diǎn)資源信息；

　?。?）執(zhí)行器中的首節(jié)點(diǎn)Mom Superior向Scheduler返回集群節(jié)點(diǎn)資源信息,，包括可用內(nèi)存量、CPU負(fù)載信息等,；

　?。?）Scheduler檢查作業(yè)隊(duì)列并為作業(yè)分配資源，同時(shí)將作業(yè)ID傳遞給Server,；

　?。?）Server通過(guò)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策略類(lèi)似,，即掃描作業(yè)請(qǐng)求,，執(zhí)行集群現(xiàn)有資源能滿足的第一個(gè)作業(yè)[6],。該策略可能會(huì)使大作業(yè)（需求資源較多）遲遲得不到運(yùn)行，因此會(huì)產(chǎn)生饑餓現(xiàn)象,。為了克服此問(wèn)題,，F(xiàn)IFO引入了饑餓作業(yè)調(diào)度方法，當(dāng)某一作業(yè)在隊(duì)列中等待時(shí)間超過(guò)一定閾值（默認(rèn)是24小時(shí)）時(shí),，會(huì)對(duì)所需資源進(jìn)行預(yù)約,，故能解決大作業(yè)的饑餓等待。但同時(shí)出現(xiàn)一個(gè)問(wèn)題,，被預(yù)約的資源不能被別的作業(yè)使用,，這樣就喪失了集群的整體公平性，作業(yè)間的時(shí)間空隙沒(méi)有得到有效利用,?？梢?jiàn)，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),。為解決此問(wèn)題,，提出了新的策略約定，當(dāng)某一大作業(yè)的等待時(shí)間超過(guò)預(yù)設(shè)的閾值時(shí),，就對(duì)需求資源進(jìn)行預(yù)約,，同時(shí)，計(jì)算出多個(gè)預(yù)約作業(yè)之間的時(shí)間空隙,，將隊(duì)列中一些資源需求小的作業(yè)插入到其中執(zhí)行,。該策略總體的執(zhí)行過(guò)程如圖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）中選擇資源的過(guò)程,，因此,，就需要給出一個(gè)算法，幫助調(diào)度系統(tǒng)選擇執(zhí)行某一作業(yè)的最優(yōu)資源,。資源選擇所使用的算法應(yīng)能從目前的資源狀態(tài)考慮,，并能根據(jù)一定的計(jì)算公式來(lái)算出最適宜的資源,。由于現(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ì)值來(lái)看，資源3為最優(yōu)執(zhí)行資源,。

　　3.2 作業(yè)優(yōu)先級(jí)的確定

　　提交作業(yè)的優(yōu)先級(jí)不僅與作業(yè)類(lèi)型,、作業(yè)所需資源類(lèi)型及多少有關(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í)超過(guò)這個(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)過(guò)計(jì)算得出的優(yōu)先級(jí)都沒(méi)有超過(guò)優(yōu)先級(jí)閾值,，故沒(méi)有對(duì)資源進(jìn)行預(yù)約,。如果超過(guò)了閾值，就需要對(duì)集群資源進(jìn)行預(yù)約,，被預(yù)約的資源不能再分配給別的作業(yè)使用,，這種要求就容易造成多個(gè)作業(yè)間時(shí)間空隙被浪費(fèi)的現(xiàn)象，而通過(guò)引入回填策略,，就能很好地解決這個(gè)問(wèn)題,，這里主要介紹一下回填策略的設(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)行,，這樣能充分利用資源，提高集群吞吐率,。具體過(guò)程示意圖如圖5所示,。

　　由圖5可知，加入回填策略后,，當(dāng)作業(yè)等待時(shí)間超過(guò)一定值（可以設(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)提過(guò),，Torque自帶的FIFO調(diào)度器實(shí)際上原理與FirstFit策略類(lèi)似,，即在隊(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è)開(kāi)始執(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í)超過(guò)閾值時(shí),，系統(tǒng)將對(duì)作業(yè)所需資源進(jìn)行預(yù)約,，在預(yù)約過(guò)程中，已運(yùn)行的作業(yè)之間可能會(huì)產(chǎn)生時(shí)間空隙,，這時(shí)根據(jù)回填策略設(shè)置,，系統(tǒng)掃描作業(yè)間隙，將作業(yè)預(yù)估時(shí)間小于時(shí)間間隙的作業(yè)投入到集群中執(zhí)行,，以達(dá)到充分利用集群資源,、增大集群吞吐率的目的。通過(guò)作業(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ù)類(lèi)型的集群調(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.