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

　　關鍵詞： 作業調度；自定義優先級；回填策略；Torque FCFS

0 引言

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

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

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

　　1.1 Torque的體系結構

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

　　1.2 Torque的工作原理

　　Torque能正常調度作業，需要啟動pbs_server、psb_mom和pbs_sched（本文采用Maui調度器mauid）三個守護進程。

　　1.2.1 pbs_server進程

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

　　1.2.2 pbs_mom進程

　　pbs_mom是在執行主機上運行的進程，如果需要主主機也進行計算操作，則主主機上也需要運行該進程，它負責收集執行主機上的系統資源。pbs_mom的主要作用是在pbs_server進程的指令下啟動、監控和終止作業。

　　1.2.3 pbs_sched進程

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

　　1.2.4 Torque處理批作業的過程

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

　　整個作業調度的過程分析如下：

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

　?。?）Server端根據作業需求向調度器Scheduler發起詢問；

　?。?）調度器通過Socket與執行器Mom通信以獲取節點資源信息；

　?。?）執行器中的首節點Mom Superior向Scheduler返回集群節點資源信息，包括可用內存量、CPU負載信息等；

　?。?）Scheduler檢查作業隊列并為作業分配資源，同時將作業ID傳遞給Server；

　?。?）Server通過Socket通知首節點Mom Superior去執行批處理作業腳本的命令；

　　（7）作業執行完成后，Mom將結果信息返回給Server端；

　　（8）Server端根據預先設定的方法將作業結果返回給用戶。

2 Torque默認的調度器

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

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

3 基于節點負載情況自定義優先級回填策略

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

　　3.1 節點負載情況的計算

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

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

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

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

　　從負載估計值來看，資源3為最優執行資源。

　　3.2 作業優先級的確定

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

　　定義 提交作業的優先級公式為：

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

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

　 3.3 回填策略的設計

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

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

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

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

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

4 結論

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

參考文獻

　　[1] 劉萍.作業調度算法研究[J].現代計算機，2012，10（1）：15-17.

　　[2] 蘭文富，羅江華，程克非.集群系統的資源調度管理實現[J].科技創新導報，2011，24（4）：43-44.

　　[3] 童瑞，董小社，李紀云，等.基于OpenPBS的機群作業管理系統的設計與實現[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] 王陽，周智力，盧康.高性能計算集群調度策略優化及應用程序并行效率研究[J].高科技產品研發，2013，20（2）：31-32.