基于Torque的新型作業(yè)調(diào)度策略的研究

周 凱，林 明

（江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003）

0 引言

集群的使用在高性能計(jì)算中并不鮮見。在高性能計(jì)算中，大部分是并行批處理作業(yè)，對于集群的高效運(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和PBSpro是商業(yè)軟件，而Torque是開源項(xiàng)目。它們各有特點(diǎn)[3]，Cordor比較全面地實(shí)現(xiàn)了檢查點(diǎn)的操作；LSF和PBS pro雖然較為完備，但是使用它們需要購買昂貴的license；而Torque由于是開源項(xiàng)目，正如Linux系統(tǒng)一樣，有全球數(shù)量眾多的Linux系統(tǒng)愛好者的強(qiáng)大支持，并且它提供靈活的作業(yè)調(diào)度策略和用戶身份認(rèn)證機(jī)制，所以本文采用Torque作為作業(yè)調(diào)度軟件來研究。與此同時，由于文中的測試作業(yè)對運(yùn)行時間和IO吞吐率有較高的要求，因此還需要對Torque進(jìn)行二次開發(fā)，加入新提出的調(diào)度策略，并通過與自帶的調(diào)度策略進(jìn)行對比，體現(xiàn)該調(diào)度策略的優(yōu)越性。

1 Torque的基本架構(gòu)和工作原理

Torque原名為PBS（Portable Batch System），是由美國國家宇航局（NASA）Ames研究中心、勞倫斯利物莫國家 實(shí) 驗(yàn) 室 （Lawrence Livermore National Laboratory）以 及墨綠信息解決公司（Veridian Information Solutions，Inc）牽頭發(fā)起的一項(xiàng)針對高并發(fā)、大數(shù)據(jù)量作業(yè)調(diào)度的科研項(xiàng)目[4]。該作業(yè)調(diào)度軟件自帶FIFO類型的作業(yè)調(diào)度器pbs_sched，同時也支持其他調(diào)度器，本文就是采用目前較為流行的Maui調(diào)度器。目前PBS分為兩部分：由Altair公司經(jīng)營的商業(yè)版PBS pro和由Adapting Computing公司運(yùn)營的Torque，后者開源，并支持使用其他調(diào)度器替換自帶的pbs_sched，更適宜用來研究，而且也支持復(fù)雜的自定義調(diào)度策略，能滿足本課題的需求。

1.1 Torque的體系結(jié)構(gòu)

如圖1所示，Torque使用一個主主機(jī)、任意多的執(zhí)行主機(jī)以及作業(yè)提交主機(jī)，主主機(jī)是Torque集群的中央管理者。一臺主機(jī)既可以被設(shè)置成主主機(jī)，也可以被設(shè)置成執(zhí)行主機(jī)。通常情況下將提交主機(jī)與主主機(jī)合并。

圖1 PBS集群的體系架構(gòu)

1.2 Torque的工作原理

Torque能正常調(diào)度作業(yè)，需要啟動pbs_server、psb_mom和pbs_sched（本文采用Maui調(diào)度器mauid）三個守護(hù)進(jìn)程。

1.2.1 pbs_server進(jìn)程

psb_server是在主主機(jī)上執(zhí)行的進(jìn)程，是批處理系統(tǒng)的核心，在集群中只有一個，它的主要功能有：提供一些基本的批處理服務(wù)，接收/創(chuàng)建一個批處理作業(yè)、修改作業(yè)，在系統(tǒng)崩潰時保護(hù)作業(yè)，將用戶請求送達(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)程的指令下啟動、監(jiān)控和終止作業(yè)。

1.2.3 pbs_sched進(jìn)程

pbs_sched運(yùn)行在主主機(jī)上，它的作用是決定什么時候在什么地方運(yùn)行作業(yè)。它從psb_server進(jìn)程請求作業(yè)狀態(tài)信息，從pbs_mom進(jìn)程請求資源狀態(tài)信息，然后決定如何調(diào)度作業(yè)。Maui調(diào)度器的進(jìn)程mauid與pbs_sched類似，不再贅述。

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

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

圖2 Torque作業(yè)調(diào)度過程圖

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

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

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

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

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

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

（6）Server通過Socket通知首節(jié)點(diǎn)Mom Superior去執(zhí)行批處理作業(yè)腳本的命令；

（7）作業(yè)執(zhí)行完成后，Mom將結(jié)果信息返回給Server端；

（8）Server端根據(jù)預(yù)先設(shè)定的方法將作業(yè)結(jié)果返回給用戶。

2 Torque默認(rèn)的調(diào)度器

Torque自身集成一個簡單的基于C語言的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è)請求，執(zhí)行集群現(xiàn)有資源能滿足的第一個作業(yè)[6]。該策略可能會使大作業(yè)（需求資源較多）遲遲得不到運(yùn)行，因此會產(chǎn)生饑餓現(xiàn)象。為了克服此問題，F(xiàn)IFO引入了饑餓作業(yè)調(diào)度方法，當(dāng)某一作業(yè)在隊(duì)列中等待時間超過一定閾值 （默認(rèn)是24小時）時，會對所需資源進(jìn)行預(yù)約，故能解決大作業(yè)的饑餓等待。但同時出現(xiàn)一個問題，被預(yù)約的資源不能被別的作業(yè)使用，這樣就喪失了集群的整體公平性，作業(yè)間的時間空隙沒有得到有效利用?？梢?，Torque自帶的調(diào)度器功能有限，因此，集成其他更優(yōu)秀的調(diào)度器以及采用更為優(yōu)化的調(diào)度策略顯得尤為重要。

圖3 Torque自帶調(diào)度器調(diào)度流程圖

3 基于節(jié)點(diǎn)負(fù)載情況自定義優(yōu)先級回填策略

給提交的作業(yè)預(yù)先設(shè)定優(yōu)先級，并根據(jù)優(yōu)先級對提交的作業(yè)進(jìn)行排隊(duì)，然后再按照隊(duì)列中的作業(yè)順序依據(jù)FCFS的方式執(zhí)行作業(yè)[1]。這種方法有一個弊端，即優(yōu)先級在作業(yè)提交時就已經(jīng)被設(shè)定了，如果high priority的作業(yè)的需求資源遠(yuǎn)高于集群現(xiàn)有可用資源，該作業(yè)就會長時間處于等待狀態(tài)。為解決此問題，提出了新的策略約定，當(dāng)某一大作業(yè)的等待時間超過預(yù)設(shè)的閾值時，就對需求資源進(jìn)行預(yù)約，同時，計(jì)算出多個預(yù)約作業(yè)之間的時間空隙，將隊(duì)列中一些資源需求小的作業(yè)插入到其中執(zhí)行。該策略總體的執(zhí)行過程如圖4所示。

圖4 作業(yè)策略執(zhí)行流程圖

3.1 節(jié)點(diǎn)負(fù)載情況的計(jì)算

節(jié)點(diǎn)的負(fù)載情況很大程度上影響作業(yè)調(diào)度系統(tǒng)對資源的選取，負(fù)載大的節(jié)點(diǎn)計(jì)算出的資源評估值應(yīng)該較小，表示越不容易被選中執(zhí)行作業(yè)。資源選擇是一個作業(yè)從資源列表（Rselected）中選擇資源的過程，因此，就需要給出一個算法，幫助調(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值。

下面給出一個實(shí)際的例子，根據(jù)上面給出的負(fù)載計(jì)算公式從三組候選的資源中選擇一種資源，假設(shè)每種資源的相關(guān)參數(shù)如表1所示。

表1 資源負(fù)載情況列表

假設(shè)該算法中整個權(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)先級的確定

提交作業(yè)的優(yōu)先級不僅與作業(yè)類型、作業(yè)所需資源類型及多少有關(guān)，還與作業(yè)提交后等待執(zhí)行所花的時間有關(guān)，等待時間越長，作業(yè)在隊(duì)列中的優(yōu)先級應(yīng)該越高，表示該作業(yè)越易被執(zhí)行。當(dāng)然，還需要設(shè)定一個優(yōu)先級閾值，當(dāng)優(yōu)先級超過這個閾值后，系統(tǒng)將對該作業(yè)所需資源進(jìn)行預(yù)約。

定義 提交作業(yè)的優(yōu)先級公式為：

其中，YPi是提交者與管理員共同商議的作業(yè)預(yù)設(shè)優(yōu)先級，k為常數(shù)權(quán)重因子，twait為作業(yè)等待的時間 （以min計(jì)），Eresource為資源負(fù)載情況，Pth為預(yù)設(shè)優(yōu)先級閾值。 由式（4）可知，等待時間越長，負(fù)載估值越大，作業(yè)優(yōu)先級越大，表示該作業(yè)越易被執(zhí)行。作業(yè)的實(shí)際優(yōu)先級需要將式（4）中前半部分與預(yù)設(shè)的優(yōu)先級進(jìn)行比較，取較小者，如果計(jì)算值大于閾值，則系統(tǒng)對所需資源進(jìn)行預(yù)約。

假設(shè)目前集群中可用資源為資源1，現(xiàn)在有作業(yè)1、作業(yè)2、作業(yè)3共三個作業(yè)提交，預(yù)設(shè)優(yōu)先級為10、15、8，預(yù)設(shè)的優(yōu)先級閾值為55，權(quán)重因子k=1，等待時間為120 s、100 s、238 s，根據(jù)式（4）可計(jì)算出三個作業(yè)的優(yōu)先級分別為P1=12.500，P2=17.083，P3=12.958，三者均小于預(yù)設(shè)優(yōu)先級閾值，不需對資源進(jìn)行預(yù)約，故根據(jù)前述定義可知，三個作業(yè)的執(zhí)行順序?yàn)樽鳂I(yè)2→作業(yè)3→作業(yè)1。

3.3 回填策略的設(shè)計(jì)

上節(jié)提到的案例中，三個作業(yè)經(jīng)過計(jì)算得出的優(yōu)先級都沒有超過優(yōu)先級閾值，故沒有對資源進(jìn)行預(yù)約。如果超過了閾值，就需要對集群資源進(jìn)行預(yù)約，被預(yù)約的資源不能再分配給別的作業(yè)使用，這種要求就容易造成多個作業(yè)間時間空隙被浪費(fèi)的現(xiàn)象，而通過引入回填策略，就能很好地解決這個問題，這里主要介紹一下回填策略的設(shè)計(jì)。

假設(shè)集群里的資源（處理器數(shù)目）有限，目前有三個大小不等的作業(yè)在運(yùn)行，隊(duì)列中還有兩個作業(yè)在排隊(duì)，默認(rèn)的FCFS策略，排隊(duì)的作業(yè)會等待前三個作業(yè)都運(yùn)行結(jié)束后再進(jìn)入集群執(zhí)行，但如果引入了回填策略，則系統(tǒng)會先掃描集群中運(yùn)行的作業(yè)之間是否存在時間間隙，然后再據(jù)排隊(duì)作業(yè)所需資源的多少和預(yù)估時間，將排隊(duì)的作業(yè)插到空閑周期中運(yùn)行，這樣能充分利用資源，提高集群吞吐率。具體過程示意圖如圖5所示。

圖5 采用回填策略前后的對比

由圖5可知，加入回填策略后，當(dāng)作業(yè)等待時間超過一定值（可以設(shè)定一個等待時間閾值）后，系統(tǒng)會掃描全部隊(duì)列，選擇作業(yè)預(yù)估時間小于空閑周期時間的作業(yè)插入空閑周期執(zhí)行，充分利用了集群的空閑周期，減少作業(yè)等待時間。

3.4 新型調(diào)度策略與默認(rèn)調(diào)度策略對比

上文已經(jīng)提過，Torque自帶的FIFO調(diào)度器實(shí)際上原理與FirstFit策略類似，即在隊(duì)列中選擇當(dāng)前系統(tǒng)資源能滿足的第一個作業(yè)執(zhí)行。測試集群環(huán)境為4臺IBM PureFlex X240刀片式服務(wù)器，1臺作為主主機(jī)，其他3臺作為執(zhí)行主機(jī)，所有機(jī)器上都裝好了Torque和Maui，在Maui的配置文件maui.cfg中添加新策略設(shè)置。對比測試中，將作業(yè)響應(yīng)時間作為衡量指標(biāo)，它代表從作業(yè)提交到作業(yè)開始執(zhí)行所花時間。測試時，構(gòu)建了三個測試作業(yè)集，分別有1 000、1 500、2 000個作業(yè)，為了方便，統(tǒng)一設(shè)定預(yù)設(shè)優(yōu)先級為0，常數(shù)權(quán)重因子為1，預(yù)設(shè)優(yōu)先級閾值為55。不同策略的作業(yè)響應(yīng)時間對比如圖6所示。因?yàn)榛诠?jié)點(diǎn)負(fù)載情況自定義優(yōu)先級回填策略兼顧了公平性和高效性，既有優(yōu)先級設(shè)置，也有回填策略考慮，所以相比于FirstFit的調(diào)度策略，在排隊(duì)作業(yè)較多時，作業(yè)響應(yīng)時間有明顯的提升，由圖6可知，作業(yè)數(shù)目為1 000、1 500、2 000時，作業(yè)響應(yīng)時間分別減少了26.1%、13.2%和12.5%。

4 結(jié)論

圖6 不同策略的作業(yè)響應(yīng)時間對比

本文提出了一種基于節(jié)點(diǎn)負(fù)載自定義優(yōu)先級回填策略，它能根據(jù)節(jié)點(diǎn)負(fù)載計(jì)算出資源評估參數(shù)，結(jié)合作業(yè)的預(yù)設(shè)優(yōu)先級及等待時間，得出相應(yīng)優(yōu)先級參數(shù)，將各作業(yè)按照此優(yōu)先級排序，逐個執(zhí)行。當(dāng)作業(yè)優(yōu)先級超過閾值時，系統(tǒng)將對作業(yè)所需資源進(jìn)行預(yù)約，在預(yù)約過程中，已運(yùn)行的作業(yè)之間可能會產(chǎn)生時間空隙，這時根據(jù)回填策略設(shè)置，系統(tǒng)掃描作業(yè)間隙，將作業(yè)預(yù)估時間小于時間間隙的作業(yè)投入到集群中執(zhí)行，以達(dá)到充分利用集群資源、增大集群吞吐率的目的。通過作業(yè)響應(yīng)時間的對比可以看到，基于節(jié)點(diǎn)負(fù)載情況自定義優(yōu)先級回填策略比默認(rèn)的調(diào)度策略在作業(yè)響應(yīng)時間上有較好的提升。

[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]王陽，周智力，盧康.高性能計(jì)算集群調(diào)度策略優(yōu)化及應(yīng)用程序并行效率研究[J].高科技產(chǎn)品研發(fā)，2013，20（2）：31-32.