分布式叢集任務排程概述

分布式叢集任務排程

在以往單機的任務執行中，任務都在一台機器上執行，所有任務都需要有序排隊等待執行，多個任務執行的時間大緻為每個任務在單機上執行的時間。但是當執行任務的機器數量變多之後，就需要将任務有序合理的配置設定到不同的機器上去執行，這也催生了一些分布式叢集中任務排程的算法。

叢集任務排程算法

目前較為主流的經典算法有如下兩個，Min-Min算法和Max-Min算法，這兩種算法計算過程相對簡單并且不複雜，但是缺點也很明顯就是對任務的負載均衡，長短任務的配置設定效果會差點。

Min-Min算法

1.假設網格任務集為Tasks={T1，T2，T3，．．．，Tn}，集合内有n個待排程的獨立任務。

2.網格資源集為Hosts={H1，H2，H3，．．．，Hm}，該資源集合内有n1個資源。設資源Hi的就緒時間(即資源最早的可以使用的時間)為R(i)。

3.任務Ti在資源Hj上的完成時間定義為ECT(i，i)，定義任務在資源上的執行時間為ETC(i，j)。

4.從上面定義得出，一個任務Ti在資源Hj上的完成時間計算公式如下： ECT(i，j)=ETC(i，j)+R(j) 。

5.n個任務在m個資源上的ETC可以用一個nxm的矩 陣來表示，矩陣元素ETC(i．i)表示第i個任務在第j個資源上 的執行時間，該矩陣的一行表示任務Ti在資源集合Hosts中 所有資源的執行時間，一清單示在同一資源上n個任務的執行時間。

Min-Min算法的思想是：

首先，計算出任務清單中所有任 務在所有資源上的最小完成時間。其次，從這些最小完成時間中找出一個值最小的，把這個最小時間對應的任務資源對找出來，把該任務送出給該資源執行，從任務清單中删除這個任務。最後，更新最小完成時間矩陣。重複以上步驟，直到任務清單為空。該算法的目的是将任務指派給不僅完成它最早的，而且執行它最快的機器，使得全部的任務完成時間最小。

該算 法的執行過程如下：

1.計算任務集合中的任務Ti在m個資源上的完成時間，得到n*m的ECT矩陣。 如果任務集合Tasks不為空時，重複以下步驟直到任務全部排程。

2.得出每個任務的最小完成時間即ECT(i，j)，把這些最小完成時間放入一個集合M内，然後找出這個集合内最小的值，根據最小值所對應的任務資源對(i，j)，這就是任務到資源的映射。

3.把該任務Ti送出到對應的資源Hi上執行，同時還要更新此ECT矩陣。

該算法容易将性能較好的機器配置設定更多的任務，有時會造成負載不均衡導緻部分資源浪費。

Max-Min算法

Max-Mim算法，非常類似Mim—Mim算法，同樣需要計算待派發任務的最小期望完成時間。與Min-Min算法的差別是，Max-Mim算法首先排程最大期望完成時間的任務到 其對應的機器上。由于Mim-Mim算法，每次都是講最小期望完成時間的任務派發到性能高的執行機上，這樣會使得性能高的執行機上會源源不斷的被配置設定任務過來，導緻系統中執行機的負載不均衡。 而Max-Mim算法，首先排程期望時間大的任務，這樣執行效率高的機器在第一次被派發任務後，其他未派發的任務更新任務的最小期望時間後，已經被派發任務的機器上的最小期望時間就會增大， 再次派發任務時，一般會派發到其他機器上，這樣在一定程度上保證了負載均衡。Max-Mim算法與 Mim-Mim算法有相同的時間複雜度，但是在系統處理多數小任務時，Max-Mm算法要比Mm—Min算法性能高。

改進算法分析

目前有些算法基于Min-Min算法進行優化，嘗試優化該算法的配置設定效率，分别了解如下兩種優化思路。

資源分級的Min-Min算法

分布式計算中基于資源分級的自适應 Min-Min 算法

該方案是基于将資源進行設定評級，因為每個計算資源有可能對于的cpu、記憶體或者帶寬都不同，進而可能會适合執行不同的任務，此時類似與通過輸入這些資源的屬性然後再Min-Min算法中配置不同的門檻值進而完成任務的适應性分級進而快速排程。

算法流程概述

從任務長短因素角度考慮，将其長度具體化，設定自适應門檻值，調解長短任務的排程優先級。本文将重點參考長任務在所有子任務中的比例，設定自适應門檻值的大小，然後通過自适應門檻值重新劃分長任務的優先級，進而得到改進的自适 應 Min-Min 任務排程算法(SMM)。

首先建立需要計算的子任務序列，将子任務在所有資源上的執行時間與資源等級作乘積運算，即 t=t×δ，進而得到基于資源分級後的 RETC 矩陣和向量 W;初始化MCT，以及總體任務分解後的子任務集 T，任務集 T映射到待配置設定任務集 S，MCT 矩陣中的每個元素為對應作業任務在各機器上的預測執行時間與資源就緒時間之和，即 MCT[e,f]=RETC[e,f]+r[f]，其中 r[f]為資源就緒時間。

1. 循環取值從 1行到第 n 行，計算 RETC矩陣中每行的均值，将均值結果存儲到向量 W中，即 w[i]表示任務 s[i]的平均預測執行時間。
2. 判斷:如果待配置設定任務集S不為空，完成步驟2-9;否則任務排程結束。
3. 從向量W找出最大值Wmax、最小值Wmin，并計算出均值w和向量元素數量 p。
4. 參考定義，從子任務集找出長任務，并确定數量q。判斷:如果存在長任務，即 q>0，則跳轉到步驟 5;如果不存在長任務，即 q=0，則跳轉到步驟 7。
5. 計算得到長任務占整個任務集的比例 K=q/p。
6. 得到自适應門檻值ζ=kI，在MCT矩陣中對長任務所占的行作乘ζ的運算。
7. 周遊矩陣MTC找出最小完成時間矩陣MMCT;
8. 周遊矩陣MMCT确認目前最短執行時間的任務，記錄該任務并将其 排程到指定的機器上完成計算任務。
9. 将該任務從未配置設定的子任務集中删除，更新資源就緒時間r[f]、W和MCT。跳轉到步驟2。

其中，W是指該任務所有的執行的曆史時間的集合，Wmax值執行時間的最大值，Wmin值執行時間的最小值，w是指執行任務的平均值；長短任務的定義如下，記T1=Wmax-w>0，T2=w-Wmin>0，當T1>T2時，令A=T1,B=T2，當T1<T2時，令B=T1，A=T2，此時M=A/B，如果任務的時間大于M*任務的平均時間則為長任務，否則為短任務。I定義為q/p，即長任務除以短任務的數量；δ=o×P×n+p×V+q×B+R×y其中CPU處理能力為P，CPU數量n，記憶體性能R，磁盤容量V，通信帶寬B。

算法的整個流程中，引入了長短任務的概念，并且引入了長短任務的比值，如果都是短任務則直接調用性能最好的即可執行更合适，如果遇到了長任務則可以通過資源等級不同來選擇不同的資源。該算法缺點就是需要先調試好參數，任務資源需要定義合适，适用範圍有一定的局限。

Min-Min添加資源屬性

Review on Max-Min Task scheduling Algorithm for Cloud Computing

Step 1: Start
Step 2: for all submitted tasks in meta-task Ti
Step 3: for all resource Rj
Step 4: compute Cij = Eij + rj
Step 5: While meta-task is not empty
Step 6: Sort all the tasks in descending order as per Burst Time.
Step 7: Give priority to tasks which have highest and lowest
        priority.
Step 8: Consider remaining tasks as normal priority tasks.
Step 9: Consider three groups according to priority:
        (1)Highest priority group
        (2)Normal priority group
        (3)Lowest priority group
Step 10: First load the tasks of highest priority group and
         arrange task in descending order according to their
         burst time.
Step11: Arrange Vm list in descending order on the basis of Resource Cost as
        Resource cost = (RAM of Virtual machine * Cost/memory )
         +(Size of Virtual machine*Cost/storage)
        (1) For all tasks in highest priority group Ti,
        (2) Select resource from resource list sequentially
        (3) Select task sequentially and schedule on selected resource
        (4) Remove Task Tk from Meta-tasks set.
        (5) Update ready time rj for select Rj
        Update Cij for all Ti
Step 10: Repeat above steps till the each and every task executed
         completely in highest priority group.
Step 11: Repeat above step 9 first for Normal priority group and
         at last for lowest priority group until each and every
         task executed completely.
Step 12: End
           

該算法将任務進行分級，可以嘗試分成三個等級即高優先級、中優先級和低優先級三個等級，然後優先排程高優先級的任務，然後周遊所有的資源并通過考慮資源的消耗如記憶體硬碟等代價再選擇一個資源去執行。然後從高優先級一直處理到低優先級直到任務執行完成。

總結

本文都是主要都是整理自網上相關論文文獻，主要是了解在分布式叢集下對任務的相關排程的一些基礎方式，最要是兩個經典的Min-Min和Max-Min算法，後續也有許多基于該算法改進而成的排程算法，在現實的開源的軟體的排程算法中，常用的方式還是輪訓、權重和hash等，因為這些方式相對簡單穩定，從算法的整理來看，實作本文的算法需要考慮的因為較多，并且通用性相對不強，進而難以滿足大家普遍的使用場景，如果大家有興趣可自行實作一下，本文隻做摘錄學習。由于本人才疏學淺，如有錯誤請批評指正。