[發明專利]任務調度方法、裝置及系統

在審

• 申請號: 201610940106.9
• 申請日: 2016-11-01
• 公開（公告）號: CN107741878A
• 公開（公告）日: 2018-02-27
• 發明（設計）人: 徐逸塵;王玉章;方小明
• 申請（專利權）人: 研祥智能科技股份有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京匯澤知識產權代理有限公司11228
• 代理人: 張瑾

技術領域

本發明涉及計算機應用技術領域，尤其涉及一種任務調度方法、裝置及系統。

背景技術

在傳統的服務器集群系統中，通常由中央調度器(中央調度器是指服務器集群的任務調度器，是單獨的一個硬件調度器)使用JSQ(最短隊列優先)算法將任務分配到具有最短任務隊列的處理器中。同時中央調度器管理所有到達的任務分配，所以可以自行追蹤各個處理器上的任務隊列，不需要額外的通訊開銷。

隨著所需計算服務越來越多，傳統的服務器集群處理能力需要進行大規模擴展才能滿足現今計算能力需求。但是，對于大規模的服務器集群數據中心，中央調度器已不再適用于做任務調度。當服務器集群規模達到上千臺設備時，此時所需要的中央調度器價格昂貴并且增加了擴展粒度(擴展粒度是指調度器可以掛載服務器的臺數，)大小。對于中央調度器，在實際應用中還有以下缺點：當系統處于低使用率時，要求關閉部分前端服務器，而此時還需要對中央硬件調度器進行重新配置；單個中央硬件調度器容易造成服務器系統的單點失敗，喪失系統健壯性。因此，中央調度器已在服務器集群系統中失去了競爭力，迫切需要一種新的技術來取代它。

因此，使用分布式調度器是必然的發展趨勢。但是在分布式調度器系統中，單個調度器只知道部分流經自身的任務，而對于JSQ算法，在任務調度前，需要知道全局的系統任務分配情況，JSQ算法不再適用分布式調度器系統。

目前，適用于分布式調度器系統的算法有PoN(n)(隨機N負載均衡)算法和WS(Work Stealing&Work Sharing，任務竊取和任務共享)算法。

對于PoN(n)算法，在任務到來時，隨機選取n個處理器，分析他們的任務隊列，將任務交給n個處理器中任務隊列最短的處理器處理。PoN(n)算法相對樸素隨機算法大大提高了響應時間并減小了通訊開銷，但是PoN(n)算法性能卻比JSQ算法差很多。而且在任務到達時還是需要調度器和處理器直接的通訊開銷，更主要的是這個通訊開銷處于響應時間的關鍵路徑之上。

對于WS算法，空閑的處理器會隨機選取其他處理器，并接過其任務隊列中的任務來處理；同時一個重度負載的處理器會隨機選取其他處理器，將自己任務隊列中的任務交給其他處理器來處理。但是，多核共享內存結構和服務器集群的任務到達和調度方式不一樣。在多核系統中，新的任務線程在每個核心上獨立生成；而在分布式調度器中，任務是從外部網絡到達調度器。對于分布式調度器，在將每個任務分配到處理器之后，如果在允許處理器直接再次重新根據整個系統和各個核心的負載情況調度任務的情形下，又會引入新的額外開銷；而且在多核系統中遷移一個線程是相對容易的，但是在面向網絡的任務遷移時，還需要遷移TCP連接以及一些子任務的同步問題。因此，WS算法還不能直接移植到云服務器集群中使用。

在實現本發明的過程中，發明人發現現有技術中至少存在如下技術問題：

在大規模服務器集群和高負載系統環境下，現有的任務調度方法的效率較低，響應時間較長。

發明內容

本發明提供的任務調度方法、裝置及系統，能夠在大規模服務器集群和高負載系統環境下更加高效地進行任務調度，合理利用系統資源，響應時間較短。

第一方面，本發明提供一種任務調度方法，包括：

調度器接收路由器分配的任務；

所述調度器將所述任務分配到自身的空閑處理器隊列中的首個處理器ID對應的空閑處理器，其中，所述空閑處理器隊列中包括各空閑處理器上報的處理器ID；

所述調度器將所述空閑處理器隊列中的首個處理器ID移除。

可選地，在所述調度器接收路由器分配的任務之前，所述方法還包括：

所述調度器接收空閑處理器上報的處理器ID；

所述調度器根據空閑處理器上報處理器ID的先后順序，將處理器ID從前到后依次排列，建立空閑處理器隊列。

可選地，所述方法還包括：

當所有調度器的空閑處理器隊列均為空時，所述調度器接收任務隊列長度低于預定閾值的低負載處理器上報的處理器ID；

所述調度器將所述低負載處理器上報的處理器ID添加到所述空閑處理器隊列中；

當所述調度器接收到路由器分配的任務時，將所述任務分配到所述空閑處理器隊列中的處理器ID對應的低負載處理器。

第二方面，本發明提供一種任務調度裝置，所述任務調度裝置位于調度器中，所述裝置包括：

第一接收單元，用于接收路由器分配的任務；