楊涌 潘波 鄭建 劉光文 林小光 成亮

摘要

首先概述計算資源分配和作業調度技術現狀，然后以當前作業調度事務特點為基礎，為了解決現有作業調度方法中計算資源劃分不靈活、使用效率低等問題，提出了一種計算資源動態分配方法;另外，充分了考慮任務的類型或關系等因素，提出了一種基于業務信息判斷的作業調度方法，該方法能夠避免優先級低的作業不能及時調度的問題。通過具體測試驗證，該方法對基于高性能計算集群的各種應用有很大的參考作用。

【關鍵詞】計算資源 作業調度 動態分配

1 研究背景

隨著信息技術的飛速發展，計算機系統需要處理的事務量大幅度增長。在摩爾定律巔峰時期，一切相對簡單，計算機系統可以期待處理器指數級的性能提升。隨著摩爾定律的終結，計算機性能提升很難直接通過升級硬件獲得，信息系統已變得越來越復雜。

超算集群系統以其卓越的性能價格比和良好的可擴展性等因素成為當今高性能計算機系統的主流體系結構。如何合理高效地使用超算集群系統所包含的豐富的計算資源是非常緊迫的問題。作業調度算法是作業調度系統的核心，調度算法的優劣決定了作業調度系統本身的質量，決定了作業運行的穩定性、高效性等。在超算服務業務開展過程中，主要使用 FIFO（First In First Out，先入先出）調度機制分配任務，將所有的作業統一提交到一個隊列中，并按照提交的先后順序依次運行隊列中的作業，但隨著超算用戶、業務量、業務類型的增多，傳統的FIFO調度機制已經不能滿足目前超算業務調度的需求。另外，在只考慮作業優先級的調度方法中，由于考慮因素單一，導致優先級低的業務不能及時調度，降低了作業調度的公平性和時效性。在現有的資源分配方法中，通常只考慮將所有計算資源作為一個統一的計算資源池，用戶如果有計算需求，就分配一塊固定的計算資源，導致計算資源劃分不靈活、使用效率低。

2 算法總體框架

作業調度程序從后備作業中選取若干個作業到內存并投入運行。它為被選中作業建立進程并分配必要的資源，這時，這些被選中的作業處于執行狀態。作業調度的功能是記錄系統中各作業的狀況，從后備作業隊列中挑選一批作業進入執行狀態，以及為被選中作業分配資源建立進程和在作業執行結束后釋放所占用的資源等。其中最主要的是從后備作業隊列中選取一批作業進入執行狀態。根據不同的目標，將會有不同的調度算法。

本文提出了一種結合作業調度和計算資源動態分配的方法，旨在通過結合作業的信息對作業進行優化調度，實現其調度公平性，另外，通過資源的動態分配，實現資源的合理分配和利用，該方法的總體運行流程如下：

（1）根據用戶業務需求為用戶分配計算資源;

（2）根據用戶業務需求建立作業隊列，記錄每個作業的優先級、作業提交時間、作業要求計算完畢時間等信息，并為每個作業分配相應的計算資源;

（3）計算各隊列中各個作業預計運行時間長度;

（4）以用戶為調度范圍，采用作業的優先級、預計運行時間長度為依據進行作業調度;

（5）以作業包含的任務類型和關系為依據進行任務調度;

（6）計算完畢，釋放計算資源。

3 計算資源動態分配方法

需要針對每個用戶建立一張作業信息表，用于記錄該用戶所有作業的計算資源、作業優先級、記錄作業提交時間、作業要求計算完畢時間、當前是否占用計算資源等信息。

作業信息表示例如表1所示。

根據每個用戶的業務需求，為其分配分配計算資源Ki（i=1，2，"""n，i為用戶編號）;管理節點將分配給節點i的計算資源分成兩部分：一部份為Ki*P，作為該用戶實際的計算資源，另外一部份為Ki*（1-P），作為該用戶的預留計算資源，其中，P為該用戶實際使用的計算資源與該用戶分配的總計算資源的比值，0≤P≤1。

另外，為了保證整個系統超算業務調度的順利進行，在為每個用戶分配預留資源外，系統還將預留一部份資源備用。資源分配原理如圖1所示。

根據用戶需求建立作業隊列，并為每個作業分配計算資源，確定作業優先級、記錄作業提交時間。

4 作業調度算法分析

為了優化作業調度機制，提高作業調度的公平性和實時性，方法通過考慮計算時長估計和用戶設定的計算時長因素，提出的一種計算資源動態分配方法，具體作業調度算法如下：

（1）計算各隊列中各個作業預計運行時間;

其中，S為當前作業的計算量，S'為歷史作業的計算量，T₀為歷史作業的運行時間。

（2）進行作業調度;作業調度示意如圖2所示。

步驟1，以用戶為單位，對本用戶的所有作業優先級進行排序;

步驟2.對于每個用戶，以每個作業的預計完成時間長度為依據，判斷是否立即處理;計算作業要求計算完畢時間一當前時間的值，并判斷作業要求計算完畢時間一當前時間與作業的預計完成時間長度的關系;

步驟3，如果作業要求計算完畢時間一當前時間>作業的預計完成時間長度，則不作處理，按作業優先級順序進行調度;

步驟4，如果作業要求計算完畢時間一當前時間≤作業的預計完成時間長度，立即進行作業調度，將該作業分配到本用戶的預留計算資源進行調度;如果本用戶的預留計算資源不夠用，則申請系統獨立的計算資源進行調度。

（3）以該作業的所有任務的關系為依據進行任務調度，如圖3所示;

步驟1，在任務調度過程中，首先判斷該作業的所有任務的類型和關系;

步驟2，如果任務間是串行關系，則將任務按FIFO順序，分配該作業的全部資源進行計算;

步驟3，如果任務間是并行關系，則需要確定該并行關系的任務數M，然后將該作業的計算資源分成M份，每個任務對應其中1份計算資源，最后進行并行計算。

（4）計算資源使用完畢，釋放計算資源。

當作業使用資源完畢，更新作業信息表中占用資源信息為空，即釋放資源，并更新作業信息表中相關信息。

5 實驗與分析

通過將該算法應用到超算平臺作業調度系統中，驗證該方法在不同業務類型作業調度中的運行情況，圖4為應用了該算法的超算平臺實際作業調度情況。

通過一段時間的應用驗證，能夠保障不同優先級的業務能夠被及時調度，優化了作業調度的公平性問題，說明了該方法是實用可行的。

6 結束語

本文提出的一種作業調度和計算資源動態分配方法，將計算資源按用戶需求進行劃分，在每個用戶劃分的計算資源中預留計算資源，并在每個用戶劃分的計算資源外預留系統的計算資源：在作業調度時以用戶為單位進行作業調度，充分考慮作業的優先級、預計運行時間長度等因素進行作業調度，充分了考慮任務的類型和關系等因素進行任務調度，能夠避免優先級低的作業不能及時調度的問題，保障所有作業在規定的時間能夠完成計算，提高了作業調度的公平性和時效性。該方法在超算平臺業務調度系統中具有較強的可操作性和一定的實用價值。

參考文獻

[1]Esmaeilzadeh H，Blem E，Amant R St，etal.Dark Silicon and the End ofMulticore Scaling[C].InternationalSymposium on Computer Architecture.IEEE，2012：122-134.

[2]Corujo A，Almeida B.Dynamic loadbalancing on heteroge-neousmulticore，multi GPU systems[C].International Conference on HighPerformance Computing&Simulation;（HPCS 2010），2010.

[3]張愛科，謝翠蘭.基于公平性和負載均衡的云計算任務調度算法[J]，計算機應用與軟件，2015，32（02）：268-271.

[4]余祖峰，蔡啟先.基于工SM的動態優先級調度算法[J].計算機工程，2011，7（04）：8-9.

[5]張登銀，許揚揚.基于時延的動態優先級調度算法[J].計算機技術與發展，2011，33（02）：7-9.

[6]韓建民，鹿玲杰，王傳斌，賈莉抑.作業調度機制在計算機控制系統中的應用[J].計算機應用，1999（08）.

[7]叢龍水.動態優先級作業調度算法與實現[J].計算機工程與應用，2013，49（10）：267-270.

[8]涂剛，陽富民.基于動態優先級策略的最優軟非周期任務調度算法[J].計算機研究與發展，2004，12（11）：23-24.