《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 基于Torque的新型作業(yè)調度策略的研究
基于Torque的新型作業(yè)調度策略的研究
2014年微型機與應用第22期
周 凱,林 明
(江蘇科技大學 電子信息學院,,江蘇 鎮(zhèn)江 212003)
摘要: 在高性能計算集群中,,優(yōu)秀的作業(yè)調度軟件和作業(yè)調度策略對系統(tǒng)的高效運行起著至關重要的作用,目前針對作業(yè)調度策略的研究多集中在單個策略的深入挖掘,,少有整合多個策略考慮的文章,。針對集群作業(yè)的運行特點,提出了一種基于節(jié)點負載情況自定義優(yōu)先級回填的調度策略,,可以有效提高性能和計算集群的運行效率,。
Abstract:
Key words :

  摘  要: 在高性能計算集群中,,優(yōu)秀的作業(yè)調度軟件和作業(yè)調度策略對系統(tǒng)的高效運行起著至關重要的作用,目前針對作業(yè)調度策略的研究多集中在單個策略的深入挖掘,,少有整合多個策略考慮的文章,。針對集群作業(yè)的運行特點,提出了一種基于節(jié)點負載情況自定義優(yōu)先級回填的調度策略,,可以有效提高性能和計算集群的運行效率,。

  關鍵詞: 作業(yè)調度;自定義優(yōu)先級,;回填策略,;Torque FCFS

0 引言

  集群的使用在高性能計算中并不鮮見。在高性能計算中,,大部分是并行批處理作業(yè),,對于集群的高效運轉,優(yōu)良的作業(yè)調度軟件以及調度策略顯得至關重要[1-2],。目前已有很多集群作業(yè)管理系統(tǒng),,具有代表性的有Wisconsin-Madison大學的Cordor、IBM公司的Platform LSF,、Altair公司的PBS pro以及開源軟件Torque,,其中,Cordor是科研項目,,LSF和PBS pro是商業(yè)軟件,,而Torque是開源項目。它們各有特點[3],,Cordor比較全面地實現了檢查點的操作,;LSF和PBS pro雖然較為完備,但是使用它們需要購買昂貴的license,;而Torque由于是開源項目,,正如Linux系統(tǒng)一樣,有全球數量眾多的Linux系統(tǒng)愛好者的強大支持,,并且它提供靈活的作業(yè)調度策略和用戶身份認證機制,,所以本文采用Torque作為作業(yè)調度軟件來研究。與此同時,,由于文中的測試作業(yè)對運行時間和IO吞吐率有較高的要求,,因此還需要對Torque進行二次開發(fā),加入新提出的調度策略,,并通過與自帶的調度策略進行對比,,體現該調度策略的優(yōu)越性。

1 Torque的基本架構和工作原理

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

  1.1 Torque的體系結構


001.jpg

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

  1.2 Torque的工作原理

  Torque能正常調度作業(yè),需要啟動pbs_server,、psb_mom和pbs_sched(本文采用Maui調度器mauid)三個守護進程,。

  1.2.1 pbs_server進程

  psb_server是在主主機上執(zhí)行的進程,是批處理系統(tǒng)的核心,,在集群中只有一個,,它的主要功能有:提供一些基本的批處理服務,,接收/創(chuàng)建一個批處理作業(yè),、修改作業(yè),在系統(tǒng)崩潰時保護作業(yè),,將用戶請求送達pbs_mom進程并進行交互等,。

  1.2.2 pbs_mom進程

  pbs_mom是在執(zhí)行主機上運行的進程,如果需要主主機也進行計算操作,,則主主機上也需要運行該進程,,它負責收集執(zhí)行主機上的系統(tǒng)資源。pbs_mom的主要作用是在pbs_server進程的指令下啟動,、監(jiān)控和終止作業(yè),。

  1.2.3 pbs_sched進程

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

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

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

002.jpg

  整個作業(yè)調度的過程分析如下:

  (1)用戶提交作業(yè)請求到Torque的Server端,;

 ?。?)Server端根據作業(yè)需求向調度器Scheduler發(fā)起詢問;

 ?。?)調度器通過Socket與執(zhí)行器Mom通信以獲取節(jié)點資源信息,;

  (4)執(zhí)行器中的首節(jié)點Mom Superior向Scheduler返回集群節(jié)點資源信息,,包括可用內存量,、CPU負載信息等;

 ?。?)Scheduler檢查作業(yè)隊列并為作業(yè)分配資源,,同時將作業(yè)ID傳遞給Server;

 ?。?)Server通過Socket通知首節(jié)點Mom Superior去執(zhí)行批處理作業(yè)腳本的命令,;

  (7)作業(yè)執(zhí)行完成后,,Mom將結果信息返回給Server端,;

  (8)Server端根據預先設定的方法將作業(yè)結果返回給用戶,。

2 Torque默認的調度器

  Torque自身集成一個簡單的基于C語言的FIFO調度器,,并且提供源代碼,實際應用當中Torque大都另外集成了別的調度器,,本文采用的是常用的Maui調度器,。

003.jpg

  Torque自帶調度器調度流程圖如圖3所示。Torque自帶的FIFO調度器其實并不是真正意義上的先進先出,,它是追求CPU的最大利用率[5],。實際上它的原理與FirstFit策略類似,即掃描作業(yè)請求,執(zhí)行集群現有資源能滿足的第一個作業(yè)[6],。該策略可能會使大作業(yè)(需求資源較多)遲遲得不到運行,,因此會產生饑餓現象。為了克服此問題,,FIFO引入了饑餓作業(yè)調度方法,,當某一作業(yè)在隊列中等待時間超過一定閾值(默認是24小時)時,會對所需資源進行預約,,故能解決大作業(yè)的饑餓等待,。但同時出現一個問題,被預約的資源不能被別的作業(yè)使用,,這樣就喪失了集群的整體公平性,,作業(yè)間的時間空隙沒有得到有效利用??梢?,Torque自帶的調度器功能有限,因此,,集成其他更優(yōu)秀的調度器以及采用更為優(yōu)化的調度策略顯得尤為重要,。

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

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

004.jpg

  3.1 節(jié)點負載情況的計算

  節(jié)點的負載情況很大程度上影響作業(yè)調度系統(tǒng)對資源的選取,負載大的節(jié)點計算出的資源評估值應該較小,,表示越不容易被選中執(zhí)行作業(yè)。資源選擇是一個作業(yè)從資源列表(Rselected)中選擇資源的過程,,因此,,就需要給出一個算法,幫助調度系統(tǒng)選擇執(zhí)行某一作業(yè)的最優(yōu)資源。資源選擇所使用的算法應能從目前的資源狀態(tài)考慮,,并能根據一定的計算公式來算出最適宜的資源,。由于現實中選擇作業(yè)運行資源最關注的往往是CPU和內存的利用率,因此本文提出的選擇資源的算法主要考慮節(jié)點的CPU和RAM,,計算公式定義如下:

  123.jpg

  其中,,WCPU代表分配給CPU速率的權重,CPUload代表目前CPU的負載,,CPUspeed代表CPU的實際速率,,CPUmin是CPU的速率最小值,WRAM是分配給RAM的權重,,RAMusage是當前RAM使用率,,RAMsize是RAM的原始容量,RAMmin是最小的RAM值,。

  下面給出一個實際的例子,,根據上面給出的負載計算公式從三組候選的資源中選擇一種資源,假設每種資源的相關參數如表1所示,。

007.jpg

  假設該算法中整個權重為10,,其中CPU權重為6,RAM的權重為4,。設定CPU速率最小值為1 GHz,,RAM最小值為1 024 MB,將值代入式(1)~(3),,可得資源負載估計值如下:

  RV%YO_{41%AK]%CWRS}YI0P.png

  從負載估計值來看,,資源3為最優(yōu)執(zhí)行資源。

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

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

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

  4.png

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

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

  3.3 回填策略的設計

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

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

005.jpg

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

  3.4 新型調度策略與默認調度策略對比

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

006.jpg

4 結論

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

參考文獻

  [1] 劉萍.作業(yè)調度算法研究[J].現代計算機,,2012,10(1):15-17.

  [2] 蘭文富,,羅江華,,程克非.集群系統(tǒng)的資源調度管理實現[J].科技創(chuàng)新導報,2011,,24(4):43-44.

  [3] 童瑞,,董小社,李紀云,,等.基于OpenPBS的機群作業(yè)管理系統(tǒng)的設計與實現[J].計算機工程與應用,,2004,,13(2):123-125.

  [4] 張麗曉,袁立強,,徐煒民.基于任務類型的集群調度策略[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ōu)化及應用程序并行效率研究[J].高科技產品研發(fā),,2013,20(2):31-32.


此內容為AET網站原創(chuàng),,未經授權禁止轉載,。