任務(wù)調(diào)度算法，隨著多核處理器的發(fā)展，帶來了新的挑戰(zhàn)。如何利用高效的任務(wù)調(diào)度策略使得多核處理器充分發(fā)揮性能，是急需解決的問題。動(dòng)態(tài)任務(wù)調(diào)度是根據(jù)運(yùn)行時(shí)的情況動(dòng)態(tài)的將任務(wù)分配到對(duì)應(yīng)的資源上，但是需要實(shí)時(shí)的收集系統(tǒng)計(jì)算資源、存儲(chǔ)資源以及網(wǎng)絡(luò)資源等信息，有一定的系統(tǒng)開銷，不過相較于資源利用率的提升，動(dòng)態(tài)資源調(diào)度也是很有意義的。
經(jīng)典的調(diào)度算法有：Min-Min調(diào)度算法、Max-Min調(diào)度算法、MCT最小完成時(shí)間、MET最小執(zhí)行時(shí)間等算法。由于Max-Min算法來自于Min-Min算法，因此先介紹Min-Min算法，再介紹Max-Min算法。

Min-Min算法

Min-Min算法是一個(gè)傳統(tǒng)的任務(wù)調(diào)度算法，核心思想是以最快的時(shí)間進(jìn)行任務(wù)分配和處理，時(shí)間是唯一考慮的權(quán)重。將任務(wù)調(diào)度到處理時(shí)間最短的資源上，保證任務(wù)完成時(shí)間最短。Min-Min算法是網(wǎng)格計(jì)算中主要的任務(wù)調(diào)度策略之一。Min-Min算法主要思想如下：
假設(shè)網(wǎng)格環(huán)境是由 n個(gè)任務(wù) T={T1，T2，…，Tn}和 m個(gè)資源 R={R1，R2，…，Rm}組成。當(dāng)任務(wù)集合不為空時(shí)，通過執(zhí)行以下流程來使得任務(wù)集合為空

1. 對(duì)于任務(wù)集合中的任意一個(gè)任務(wù)Ti，計(jì)算調(diào)度到所有資源R中的任務(wù)最小完成時(shí)間。假設(shè)在第k（k <= m)個(gè)資源上任務(wù)能最早完成，那么最小完成時(shí)間就是minTime = MCT(i, k)。就得到一個(gè)含有n個(gè)元素的以為數(shù)組minTime。
2. 假設(shè)第i個(gè)元素是minTime數(shù)組中最小的，對(duì)應(yīng)的資源為h，那么就把任務(wù)Ti分配到資源h上去。
3. 從任務(wù)集合中把任務(wù)Ti刪除，再返回第1步。
4. 任務(wù)調(diào)度集合為空時(shí)，就結(jié)束調(diào)度程序。

Min-Min算法存在一個(gè)很大的缺點(diǎn)，就是算法總是優(yōu)先分配小任務(wù)、最快完成時(shí)間的任務(wù)，而忽略了網(wǎng)格資源的負(fù)載均衡，網(wǎng)格處于一個(gè)異構(gòu)的環(huán)境中時(shí)，機(jī)器的處理能力有可能會(huì)主導(dǎo)任務(wù)的調(diào)度策略，換句話說如果一個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算能力超過其他所有節(jié)點(diǎn)，那么任務(wù)就會(huì)堆砌到這一個(gè)計(jì)算節(jié)點(diǎn)上，導(dǎo)致資源利用率低下。另外一個(gè)方面，由于對(duì)于每個(gè)任務(wù)都需要計(jì)算在對(duì)應(yīng)資源下的完成時(shí)間，因此會(huì)有不小的系統(tǒng)開銷，大量任務(wù)到來的情況下調(diào)度的時(shí)延可能會(huì)很長。

Max-Min算法

Max-Min算法與Min-Min算法很類似，只是將上述Min-Min算法流程中的選擇minTime數(shù)組中最小的值改為選擇最大的值，將在minTime數(shù)組中選擇最大的值，比如說最大值對(duì)應(yīng)的是maxTime = MCT(i, k)，就將任務(wù)i分配給資源k。
Max—Min算法的目的是為了 最小化由于執(zhí)行需要長執(zhí)行時(shí)間的任務(wù)而導(dǎo)致的部分資源負(fù)載過大而部分資源空閑的極度負(fù)載不均衡的后果。因此在元任務(wù)是由許多短任務(wù)和少數(shù)長任務(wù)組成的情況下。Max—Min調(diào)度算法可以做到相對(duì)來說負(fù)載均衡。但是Max-Min算法也會(huì)造成完成時(shí)間較小的任務(wù)等待時(shí)間過長的問題，影響作業(yè)執(zhí)行的效率，也有可能導(dǎo)致負(fù)載不均衡。
最大最小算法定義如下：

1. 資源按照需求遞增的順序進(jìn)行分配
2. 不存在用戶得到的資源超過自己的需求
3. 未得到滿足的用戶等價(jià)的分享資源

考慮用戶集合 1， …， n，分別有資源需求 x1，x2，…，xn。不失一般性，令資源需求滿足 x1 <= x2 <= … <= xn。令服務(wù)器具有能力 C。那么，初始把 C/n 資源給需求最小的用戶，這可能會(huì)超過用戶 1 的需求，繼續(xù)處理。該過程結(jié)束時(shí)，每個(gè)用戶得到的沒有比自己要求更多，而且，如果其需求得不到滿足，得到的資源也不會(huì)比其他用戶得到的最多的資源還少。我們之所以稱之為最大最小公平分配是因?yàn)槲覀冏畲蠡速Y源得不到滿足的用戶最小分配的資源。
一個(gè)通俗的例子：有一四個(gè)用戶的集合，資源需求分別是 2，2.6，4，5，其資源總能力為 10，為其計(jì)算最大最小公平分配。
解決方法：通過幾輪的計(jì)算來計(jì)算最大最小公平分配。第一輪，我們暫時(shí)將資源劃分成 4 個(gè)大小為 2.5 的。由于這超過了用戶 1 的需求，這使得剩了 0.5 個(gè)均勻的分配給剩下的 3 個(gè)人資源，給予他們每個(gè) 2.66。這又超過了用戶 2 的需求，所以擁有額外的 0.066… 來分配給剩下的兩個(gè)用戶，給予每個(gè)用戶 2.5 + 0.66 … + 0.033… = 2.7。因此公平分配是：用戶 1 得到 2，用戶 2 得到 2.6，用戶 3 和用戶 4 每個(gè)都得到 2.7。

基于權(quán)重的Max-Min算法

上述假設(shè)是基于所有用戶具有相同的權(quán)限來獲取資源，有時(shí)候需要給一些用戶更大的配額。例如，可能會(huì)給不同的用戶 1, …, n 關(guān)聯(lián)權(quán)重 w1, w2, …, wn，這反映了他們間的資源配額。通過定義帶權(quán)的最大最小公平分配來擴(kuò)展最大最小公平分配的概念以使其包含這樣的權(quán)重：

1. 資源按照需求遞增的順序進(jìn)行分配，通過權(quán)重來進(jìn)行標(biāo)準(zhǔn)化
2. 不存在用戶得到超過自己需求的資源
3. 未得到滿足的用戶按照權(quán)重均分獲取資源

一個(gè)通俗的例子： 有一四個(gè)用戶的集合，資源需求分別是 4，2，10，4，權(quán)重分別是 2.5，4，0.5，1，資源總能力是 16，為其計(jì)算最大最小公平分配。
解決辦法 第一步是標(biāo)準(zhǔn)化權(quán)重，將最小的權(quán)重設(shè)置為 1。這樣權(quán)重集合更新為 5，8，1，2。這樣就假裝需要的資源不是 4 份而是 5 + 8 + 1 + 2 = 16 份。因此將資源劃分成 16 份。在資源分配的每一輪，按照權(quán)重的比例來劃分資源，因此，在第一輪，計(jì)算C/n為16/16 = 1。在這一輪，用戶分別獲得 5，8，1，2單元的資源，用戶1得到了 5 個(gè)資源，但是只需要 4，所以多了 1 個(gè)資源，同樣的，用戶 2 多了 6 個(gè)資源。用戶 3 和用戶 4 拖欠了，因?yàn)樗麄兊呐漕~低于需求?，F(xiàn)在有 7 個(gè)單元的資源可以分配給用戶 3 和用戶 4。他們的權(quán)重分別是 1 和 2，最小的權(quán)重是 1，因此不需要對(duì)權(quán)重進(jìn)行標(biāo)準(zhǔn)化。給予用戶 3 額外的 7 × 1/3 單元資源和用戶 4 額外的 7 × 2/3 單元。這會(huì)導(dǎo)致用戶 4 的配額達(dá)到了 2 + 7 × 2/3 = 6.666，超過了需求。所以將額外的 2.666 單元給用戶 3，最終獲得 1 + 7/3 + 2.666 = 6 單元。最終的分配是 4，2，6，4，這就是帶權(quán)的最大最小公平分配。
參考：https://oldtang.com/109.html文章來源地址http://www.zghlxwxcb.cn/news/detail-679418.html

到了這里，關(guān)于Max-Min算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！