[發明專利]一種多用戶多隊列調度方法

有效

• 申請號: 201410302274.6
• 申請日: 2014-06-27
• 公開（公告）號: CN104079502B
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 劉欣然;沈時軍;朱春鴿
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心
• 主分類號: H04L12/865
• 分類號: H04L12/865
• 代理公司: 北京安博達知識產權代理有限公司11271
• 代理人: 徐國文

技術領域

本發明涉及一種調度方法，具體涉及一種多用戶多隊列調度方法。

背景技術

目前云計算或分布式計算領域中使用最廣泛的是Hadoop中的三類調度算法：先入先出算法FIFO(First In First Out)、公平份額調度算法(Fair Scheduler)和計算能力調度算法(Capacity Scheduler)。

1)FIFO算法的主要思想是：所有用戶的作業都被提交到一個隊列中，作業按照優先級高低、提交時間先后進行排序；若作業的優先級不同，優先級較高的作業總是優先執行；若作業的優先級相同，提交時間較早的作業總是優先執行。該方法具有如下的缺點：1)無法避免用戶間的調度搶占。若某用戶提交了大量的作業，則該用戶可以得到更多的調度時間；2)無法照顧低優先級作業的調度。在高優先級的作業存在時，低優先級的作業將一直得不到調度。

2)公平份額調度算法(Fair Scheduler)的主要思想是：為每一個用戶建立一個作業隊列，并為每個隊列分配額定的調度時間，在每個隊列內部按照上述FIFO的算法進行調度。該方法具有如下的缺點：無法保證優先級高的作業被調度的機率更高。由于用戶被分配的調度時間是確定的，當某用戶提交的作業較少時，其低優先級的作業可能比其它用戶的高優先級的作業更容易被調度。

3)計算能力調度算法(Capacity Scheduler)的主要思想是：建立多個作業隊列，并為每個隊列分配一定的調度時間；在調度時，總是優先選擇實際調度時間與預期相差最大的作業隊列；在每個隊列內部按照上述FIFO的算法進行調度。該方法具有如下的缺點：由于每個作業隊列的調度時間是額定的，當不同隊列的作業數量差別較大時，存在優先級低的作業被優先調度的情況。

發明內容

為了克服上述現有技術的不足，本發明提供一種多用戶多隊列調度方法，在任何調度場景下，它既可以避免用戶間的調度搶占，又能在兼顧作業優先級的前提下，保證低優先級作業一定的調度機率。

為了實現上述發明目的，本發明采取如下技術方案：

本發明提供一種多用戶多隊列調度方法，所述方法具體包括以下步驟：

步驟1：建立多用戶多隊列調度模型；

步驟2：調度服務器接收用戶提交的作業，并對作業進行緩存；

步驟3：調度服務器對作業進行周期性循環調度，并將作業下發給資源對應的服務器。

所述步驟1中，多用戶多隊列調度模型如下：

定義資源集合Φ＝{r_i|i＝1,2,…,n}，其中r_i表示資源集合中第i個資源，n表示資源集合中資源總數；作業集合Ψ＝{t_j|j＝1,2,…,m}，其中t_j表示作業集合中第j個作業，m表示作業集合中作業總數；函數U(t_j)表示作業t_j所屬的用戶，函數K(t_j)表示作業t_j的優先級；作業隊列Ψ_u,k＝{t_j|U(t_j)}＝u^K(t_j)＝k}表示所屬用戶為u、優先級為k的所有作業的集合，其中u∈(1,υ)，k∈(1,κ)，υ為用戶總數，κ為最高優先級；定義w_u,k表示作業集合Ψ_u,k上一次被調度的時間，p_k為優先級為k的作業的被調度概率，且有

所述步驟2包括以下步驟：

步驟2-1：當調度服務器接收到用戶提交的作業時，根據U(t_j)、K(t_j)查找作業t_j對應的作業隊列Ψ_u,k；

步驟2-2：當Ψ_u,k尚未創建，則創建該作業隊列，并設置w_u,k＝0；

步驟2-3：將作業t_j按照先入先出順序放入作業隊列Ψ_u,k。

所述步驟3包括以下步驟：

步驟3-1：記錄當前時間w；

步驟3-2：計算每個非空的作業隊列Ψ_u,k的調度權重f_u,k＝(w-w_u,k)p_k，并選出f_u,k最大的作業隊列Ψ′_u,k；