靜態(tài)負(fù)載分配

靜態(tài)負(fù)載分配《分布式系統(tǒng)》(九20112負(fù)載分配分布式系統(tǒng)的資源管理模塊，主要實(shí)現(xiàn)合理和透明地在處理器之間重新分配系統(tǒng)負(fù)載，以達(dá)到系統(tǒng)的綜合性能最優(yōu)。（最小的總體系統(tǒng)執(zhí)行時(shí)間最大的總體系統(tǒng)輸出）大致分為靜態(tài)負(fù)載分配和動(dòng)態(tài)負(fù)載分配2大類情況。靜態(tài)負(fù)載分配：進(jìn)程運(yùn)行前進(jìn)行處理器分配，運(yùn)行中不作調(diào)整，直到運(yùn)行結(jié)束；（確定性分配）動(dòng)態(tài)負(fù)載分配：進(jìn)程運(yùn)行中動(dòng)態(tài)進(jìn)行處理器分配，且可以不斷調(diào)整；（負(fù)載均衡）第2頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20113負(fù)載分配分類進(jìn)程和處理器在負(fù)載分配時(shí)是M:N（多對(duì)多）的關(guān)系。有多種負(fù)載分配算法分類：負(fù)載分配局部全局靜態(tài)動(dòng)態(tài)分散式控制集中式控制協(xié)作非協(xié)作最優(yōu)次優(yōu)近似啟發(fā)式單個(gè)處理器上多個(gè)進(jìn)程對(duì)時(shí)間片的分配。先完成全局進(jìn)程對(duì)處理器的分配，再在處理器內(nèi)進(jìn)行局部分配。進(jìn)程執(zhí)行以前的編譯階段完成進(jìn)程對(duì)處理器的分配。進(jìn)程在系統(tǒng)中執(zhí)行時(shí)才作分配。得到一個(gè)最優(yōu)的結(jié)果。得到一個(gè)次優(yōu)的結(jié)果。搜索一個(gè)解空間的子集，尋找到一個(gè)較好的解。使用某些特殊參數(shù)，近似地對(duì)真實(shí)系統(tǒng)建模。決策工作被分配給不同的處理器。決策工作由一個(gè)處理器完成。不同處理器間有協(xié)同操作。各處理器獨(dú)立做出決策。第3頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20114負(fù)載分配分類其它的負(fù)載分配算法分類：?jiǎn)蝹€(gè)和多個(gè)應(yīng)用程序搶占式的和非搶占式的自適應(yīng)的和非自適應(yīng)的第4頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20115靜態(tài)負(fù)載分配根據(jù)先驗(yàn)知識(shí)在執(zhí)行前調(diào)度一個(gè)任務(wù)（進(jìn)程）集合，使它們總體上在各個(gè)目標(biāo)PE上有最小的執(zhí)行時(shí)間（代價(jià)）。靜態(tài)負(fù)載分配問題也稱為任務(wù)調(diào)度問題，它涉及到3方面的要素：處理器互連、任務(wù)劃分和任務(wù)分配。負(fù)載分配有時(shí)即使加入執(zhí)行開銷和通信開銷等假設(shè)仍然是一個(gè)NP完全問題，很難求得一個(gè)明確的最優(yōu)解，我們總是用各種方法試圖求得一個(gè)次優(yōu)的解，或者加入一些特殊的約束以求得最優(yōu)解。第5頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20116任務(wù)（進(jìn)程）的圖模型表示－任務(wù)優(yōu)先圖任務(wù)優(yōu)先圖G是一個(gè)有向無環(huán)圖（DAG）xy任務(wù)優(yōu)先順序x：任務(wù)在處理器上的執(zhí)行代價(jià)y：在不同處理器上啟動(dòng)后續(xù)任務(wù)所需的時(shí)間（處理器間通信代價(jià)）第6頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20117任務(wù)的圖模型表示－任務(wù)相互關(guān)系圖2個(gè)處理器的情況x,yz,z’任務(wù)通信x,y：任務(wù)在不同的處理器上的執(zhí)行代價(jià)z,z’：在不同處理器上和在相同處理器上的任務(wù)間通信代價(jià)（通常z’可忽略）第7頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20118處理器互連a)Illiac網(wǎng)格方案（16個(gè)PE的系統(tǒng)）

2維節(jié)點(diǎn)度數(shù)：4

網(wǎng)絡(luò)直徑：n-1（n元）（常規(guī)2維網(wǎng)格的一半）第8頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20119處理器互連b)圓環(huán)方案（16個(gè)PE的系統(tǒng)）

2維節(jié)點(diǎn)度數(shù)：4

網(wǎng)絡(luò)直徑：2n/2第9頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201110處理器互連c)超立方體方案（16個(gè)PE的系統(tǒng)）節(jié)點(diǎn)度數(shù)：n

網(wǎng)絡(luò)直徑：nn維，每維2個(gè)節(jié)點(diǎn)

n維立方體是2個(gè)n-1維立方體互連而成。第10頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201111處理器互連d)WK網(wǎng)絡(luò)方案（16個(gè)PE的系統(tǒng)）1層WK網(wǎng)絡(luò)2層WK網(wǎng)絡(luò)節(jié)點(diǎn)度數(shù)：4

網(wǎng)絡(luò)直徑：

n-1n層的WK網(wǎng)絡(luò)由4個(gè)(n-1)層的WK子網(wǎng)絡(luò)組成，每個(gè)子網(wǎng)絡(luò)是一個(gè)虛擬節(jié)點(diǎn)。第11頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201112任務(wù)劃分將一個(gè)大的任務(wù)（應(yīng)用程序）分解成一些小的子任務(wù)類，每個(gè)子任務(wù)類作為分配給同一個(gè)PE執(zhí)行。也稱任務(wù)聚類。根據(jù)子任務(wù)類中基本任務(wù)單元（粒度）的大小，任務(wù)劃分算法可分成：細(xì)粒度、中粒度、和粗粒度。粒度太大，會(huì)降低并行度；粒度太小，子任務(wù)進(jìn)程的切換和它們間的通信代價(jià)會(huì)增加。任務(wù)劃分的主要目標(biāo)是盡可能地增加并行度和降低通信代價(jià)（尋找一個(gè)適中的粒度）。第12頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201113任務(wù)劃分大體上有三種方法的任務(wù)劃分：水平或垂直劃分：根據(jù)任務(wù)優(yōu)先圖的關(guān)鍵路徑（最長路徑）垂直進(jìn)行或任務(wù)分層水平進(jìn)行；通信延遲最小劃分：將通信頻繁的基本任務(wù)節(jié)點(diǎn)歸成一類，讓其在同一個(gè)PE上執(zhí)行，以最大限度地降低通信代價(jià)。此方法需要顧及并行任務(wù)串行化所帶來的損失。任務(wù)復(fù)制：通過在PE上復(fù)制任務(wù)來降低通信代價(jià)，同時(shí)保留任務(wù)的并行性。此方法會(huì)增加PE的儲(chǔ)存空間開銷和PE間同步的開銷。通常任務(wù)劃分的子任務(wù)類數(shù)目等于PE的個(gè)數(shù)，以簡(jiǎn)化后續(xù)的任務(wù)分配。第13頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201114任務(wù)劃分－線性和非線性任務(wù)劃分后，如果至少有一個(gè)子任務(wù)類中包含兩個(gè)獨(dú)立的任務(wù)，則劃分是非線性的；否則劃分是線性的（所有獨(dú)立的任務(wù)被劃分在不同的任務(wù)類中）。如：T1T2T3d1d2a)線性劃分T1T2T3d1d2b)非線性劃分第14頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201115任務(wù)劃分－衡量劃分任務(wù)優(yōu)先圖可以認(rèn)為是許多分叉和合并操作的集合：a)分叉c1xv1l1b)合并c2v2l2cnvnln…c1v1l1c2v2l2cnvnln…x分叉x（或合并x）的粒度是：g(x)=min{ck}/max{lk} 0

kn0

kn任務(wù)優(yōu)先圖G的粒度是：g(G)=min{g(x)}

xG第15頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201116任務(wù)劃分－衡量劃分如果g(x)>1（g(G)>1），合并或分叉（或圖G）就是粗粒度的，否則操作或圖就是細(xì)粒度的。如下圖的非線性劃分是粗粒度的（g(x)=2）。432T1T2T311第16頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201117任務(wù)劃分－衡量劃分可以證明，如果任務(wù)優(yōu)先圖G是粗粒度的，則其任何非線性的子任務(wù)類都可以轉(zhuǎn)換（再劃分）成具有更少或相等執(zhí)行時(shí)間的線性分類。即：粗粒度的任務(wù)優(yōu)先圖其線性劃分性能優(yōu)于任何非線性劃分。然而，如果任務(wù)優(yōu)先圖G是細(xì)粒度的，可能存在，也可能不存在一個(gè)非線性劃分優(yōu)于線性劃分。第17頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201118任務(wù)劃分－衡量劃分例：432T1T2T311a)線性劃分432T1T2T311b)非線性劃分b)是粗粒度的，其非線性劃分b)的執(zhí)行時(shí)間是9，線性劃分a)的執(zhí)行時(shí)間是7；若將通信代價(jià)1變?yōu)?，則b)是細(xì)粒度的，其非線性劃分b)的執(zhí)行時(shí)間是9，線性劃分a)的執(zhí)行時(shí)間是10。4444第18頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201119任務(wù)分配將任務(wù)劃分后的子任務(wù)類分配給PE的過程。在n個(gè)子任務(wù)類和n個(gè)PE間作映射分配，共有Cnn=n!種分配方法，根據(jù)PE的存儲(chǔ)容量、處理能力和PE間的通信距離各映射分配方法會(huì)產(chǎn)生較大差異的效果。為了減少任務(wù)分配的復(fù)雜性，可以作一些假設(shè)：PE的存儲(chǔ)容量無限每個(gè)PE有相同的處理能力忽略通信距離所造成的網(wǎng)絡(luò)擁塞等。第19頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201120任務(wù)調(diào)度（靜態(tài)負(fù)載分配）方法基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度算法（算法1）任務(wù)優(yōu)先圖是一棵樹（算法2）只有兩個(gè)處理器基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度任務(wù)調(diào)度評(píng)測(cè)使用其它模型和技術(shù)的任務(wù)調(diào)度Stone網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度算法實(shí)時(shí)定期任務(wù)調(diào)度速率單調(diào)優(yōu)先調(diào)度期限驅(qū)動(dòng)調(diào)度第20頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201121基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度對(duì)任務(wù)優(yōu)先圖，可以用G=(V，A)來描述，其中V是節(jié)點(diǎn)的集合，表示任務(wù)集；A是弧線的集合，表示任務(wù)間的優(yōu)先關(guān)系。如：u、v是V中的節(jié)點(diǎn)（任務(wù)），(u,v)是A中的弧線鏈接。對(duì)于每個(gè)節(jié)點(diǎn)（任務(wù)）和鏈接都定義了代價(jià)函數(shù)w，其中w(u)(0,)表示任務(wù)u在處理器上執(zhí)行的時(shí)間代價(jià)（所有處理器是相同的），w(u,v)=(l,l’)是鏈接的代價(jià)，其中l(wèi)’是在同一處理器內(nèi)的通信時(shí)間代價(jià)，l是處理器間的通信時(shí)間代價(jià)（u和v分配在不同處理器）。w(u)w(u,v)uv第21頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201122基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度幾點(diǎn)約束：處理器的處理能力是相同的。不考慮處理器互連，即忽略網(wǎng)絡(luò)擁塞，也即處理器間的通信代價(jià)對(duì)所有處理器是一樣的。相對(duì)l，l’是非常小的，可以忽略，因此w(u,v)=l。w(u)w(u,v)uv第22頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201123基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度甘特圖（GanttChart）任務(wù)分配表示：橫坐標(biāo)是處理器，縱坐標(biāo)是時(shí)間，方塊是任務(wù)的開始、持續(xù)和結(jié)束時(shí)間。T1T2T3T4T5時(shí)間0第23頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201124基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度任務(wù)優(yōu)先圖的甘特圖（GanttChart）任務(wù)分配表示例：T1T3時(shí)間1221T11424T2T3T4T51122T2T5T412a)任務(wù)優(yōu)先圖b)2個(gè)處理器的甘特圖第24頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201125基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度 在不同處理器上分配任務(wù)時(shí)，通信的開銷對(duì)任務(wù)調(diào)度有較大影響，如：T1T2T3ddT1da)任務(wù)優(yōu)先圖b)調(diào)度結(jié)果1T2T3T1T2T3c)調(diào)度結(jié)果2T1T1T2T3d)調(diào)度結(jié)果3第25頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201126基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度只有當(dāng)通信代價(jià)較小時(shí)，將任務(wù)分配到不同的處理器是比較合適的（圖c）；任務(wù)調(diào)度總是盡量將任務(wù)分配到不同的處理器以增加并行度，同時(shí)盡量降低通信的開銷，然而二者有時(shí)是無法滿足的矛盾，需要某種程度的折中；有時(shí)采用任務(wù)復(fù)制的方法實(shí)現(xiàn)可以得到一個(gè)很好的效果（圖d）。第26頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201127基于任務(wù)優(yōu)先圖的兩個(gè)最優(yōu)調(diào)度算法為了實(shí)現(xiàn)最優(yōu)，兩個(gè)算法各自有約束條件：（算法1）任務(wù)優(yōu)先圖是一棵樹。（算法2）只有兩個(gè)處理器。 而且兩個(gè)算法都假設(shè)通信代價(jià)可以忽略和優(yōu)先圖中每個(gè)任務(wù)節(jié)點(diǎn)的執(zhí)行時(shí)間是一樣的。兩個(gè)算法都是最高級(jí)優(yōu)先方法，即根據(jù)任務(wù)節(jié)點(diǎn)的等級(jí)來選擇分配節(jié)點(diǎn)。第27頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201128最優(yōu)調(diào)度算法1具體算法：任務(wù)節(jié)點(diǎn)的等級(jí)等于它到根節(jié)點(diǎn)的距離加1，等級(jí)越高，優(yōu)先級(jí)就越高；相同等級(jí)的節(jié)點(diǎn)中，所有先導(dǎo)節(jié)點(diǎn)都已執(zhí)行的節(jié)點(diǎn)先被選中；若有多個(gè)節(jié)點(diǎn)符合條件2，則隨機(jī)選擇。T1T2T3T4T5T6T7T8T9T10T11T12T13第28頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201129最優(yōu)調(diào)度算法1在3個(gè)處理器上實(shí)現(xiàn)的例：T1T2T3T4T5T6T7T8T9T10T11T12T13T1T4T6T8T11T13T2T5T9T12T3T7T10時(shí)間0a)任務(wù)優(yōu)先圖b)算法實(shí)現(xiàn)的甘特圖第29頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201130最優(yōu)調(diào)度算法1使用一個(gè)就緒隊(duì)列實(shí)現(xiàn)算法：就緒隊(duì)列按優(yōu)先級(jí)排列那些可以被選擇分配給處理器的任務(wù)節(jié)點(diǎn)。T1T2T3T4T5T6T7T8T9T10T11T12T13就緒隊(duì)列狀態(tài)：(T1,T2,T3,T4,T5,T7,T9,T10,T12)

(T4,T5,T7,T9,T10,T12)

(T6,T9,T10,T12)

(T8,T12)

(T11)

(T13)等級(jí)54321第30頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201131最優(yōu)調(diào)度算法2具體算法：將k個(gè)終止節(jié)點(diǎn)依次標(biāo)記為1~k（標(biāo)記越大，優(yōu)先級(jí)越高）；尋找所有后續(xù)節(jié)點(diǎn)均被標(biāo)記的節(jié)點(diǎn)；根據(jù)這些節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)排列的字典升序依次標(biāo)記這些節(jié)點(diǎn)；重復(fù)2、3直到所有節(jié)點(diǎn)標(biāo)記完畢；根據(jù)優(yōu)先級(jí)的高低順序依次將任務(wù)分配給2個(gè)處理器。11T9910T107T116T6T78T84T45T521T1T23T3第31頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201132最優(yōu)調(diào)度算法2例的標(biāo)記結(jié)果：T1,T2,T3,T4,T5,T6,T11,T8,T7,

T10,T9

11T9910T107T116T6T78T84T45T521T1T23T3T9T7T11T5T3T1T10T8T6T4T2a)任務(wù)優(yōu)先圖b)算法實(shí)現(xiàn)的甘特圖(2個(gè)處理器)時(shí)間0第32頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201133最優(yōu)調(diào)度算法2本算法有問題的！思考為什么需要是2個(gè)處理器的限制？還需要加入什么限制，算法才沒有問題？提示比如：任務(wù)優(yōu)先圖中，去掉T10，算法會(huì)出現(xiàn)錯(cuò)誤。第33頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201134基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度假設(shè)任務(wù)關(guān)系圖由無向圖Gt=(Vt，Et)表示，其中Vt是任務(wù)節(jié)點(diǎn)集合，Et是邊集合。處理器關(guān)系圖由無向圖Gp=(Vp，Ep)表示，其中Vp是處理器集合，Ep是邊集合（處理器間的通信通道）。一般來說，如果任務(wù)劃分已經(jīng)完成，則|Vt|

|Vp|，我們進(jìn)行映射分配M：Vt

Vp及執(zhí)行時(shí)間估計(jì)： 設(shè)w(u)和w(u,v)分別是節(jié)點(diǎn)u和連接(u,v)的代價(jià)。 處理器p

Vp的計(jì)算負(fù)載：Comp(p)=w(u)|M(u)=p uVt

通信負(fù)載：Commp(p)=w(u,v)|M(u)=pM(v) (u,v)Et第34頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201135基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度一個(gè)應(yīng)用程序總的計(jì)算和通信負(fù)載：Comp=

Comp(p)=

w(u)|M(u)=p pVp pVpuVtComm=1/2

Comm(p)=1/2

w(u,v)|M(u)=pM(v) pVp pVp(u,v)Et總的程序執(zhí)行時(shí)間估計(jì)：T＝max{Comp(p)+Comm(p)},pVp

是依據(jù)每個(gè)PE的執(zhí)行速度設(shè)定的調(diào)節(jié)比例；是依據(jù)每個(gè)通信信道的通信速度和通信進(jìn)程間的距離設(shè)定的調(diào)節(jié)比例。第35頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201136基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度理想情況下，任務(wù)關(guān)系圖中相鄰的節(jié)點(diǎn)應(yīng)被分配在相鄰的處理器上，以減少處理器間長距離的通信。因此，評(píng)估映射質(zhì)量的一個(gè)指標(biāo)是任務(wù)關(guān)系圖Gt的邊映射到處理器圖Gp的邊的數(shù)目，這個(gè)數(shù)目稱為映射的勢(shì)，映射的勢(shì)

Gt的邊數(shù)，映射的勢(shì)越大則越理想。第36頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201137基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度下例中，映射的勢(shì)是8（共13條邊）映射的勢(shì)并不能完全反映出映射的質(zhì)量，這主要表現(xiàn)在勢(shì)以外的邊所對(duì)應(yīng)的處理器的距離。（圖中虛線的距離）134562789123456798第37頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201138基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度P203使用嵌入技巧來衡量利用任務(wù)相互關(guān)系圖分配任務(wù)到處理器關(guān)系圖時(shí)的理想程度。其目標(biāo)：發(fā)現(xiàn)一個(gè)嵌入，有最小膨脹、最大擴(kuò)大和最小擁塞。即上圖中，虛線的數(shù)目最少，且最短；任務(wù)節(jié)點(diǎn)到處理器節(jié)點(diǎn)的數(shù)目最多；經(jīng)過一個(gè)處理器邊（通信鏈路）的任務(wù)邊數(shù)最小。*書中錯(cuò)誤：（P203,第8行）嵌入的負(fù)載，是Gt分配給Gp中任意……第38頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201139網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度Stone網(wǎng)絡(luò)流量算法：一個(gè)在雙處理器且處理器有不同處理能力的系統(tǒng)中對(duì)任務(wù)相互關(guān)系圖的最優(yōu)調(diào)度算法。圖的分割、帶權(quán)分割：tsd分割為圖中邊的子集：1)刪除這些邊后使圖不連通；2)這些邊的任何子集都不滿足上一點(diǎn)。帶權(quán)圖的分割為帶權(quán)分割。分割后的2部分中各包含s和t的分割，稱為s-t分割或s-t帶權(quán)分割。第39頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201140網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度網(wǎng)絡(luò)的分割、帶權(quán)分割：邊的流量不能超過邊的容量，網(wǎng)絡(luò)的流量不能超過分割的容量；除起始節(jié)點(diǎn)和終止節(jié)點(diǎn)，節(jié)點(diǎn)的流入流量等于節(jié)點(diǎn)的流出流量；起始節(jié)點(diǎn)只有流出，終止節(jié)點(diǎn)只有流入。ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第40頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201141網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度Ford-Fulkerson最大流-最小割理論：最小的帶權(quán)分割就是最大的網(wǎng)絡(luò)流量。（根據(jù)容量圖）ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第41頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201142網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度確定了最大的網(wǎng)絡(luò)流量就確定了最小的帶權(quán)分割。確定網(wǎng)絡(luò)最大流量的算法：使網(wǎng)絡(luò)流量最大化的進(jìn)程方法。從任意一種流開始，尋找可能存在的增加路徑（augmentingpath），在該路徑上：對(duì)于前向鏈接，它有富余的容量；對(duì)于后向鏈接，它有反向的流量。消除這些增加路徑：對(duì)于前向鏈接，增大實(shí)際的流量；對(duì)于后向鏈接，減少反向的流量。直到網(wǎng)絡(luò)中沒有增加路徑為止。此時(shí)，網(wǎng)絡(luò)的流量最大，它的一個(gè)分割（其各鏈接邊的容量等于實(shí)際流量）就是最小帶權(quán)分割。第42頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201143網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度利用網(wǎng)絡(luò)最大流量就是圖的最小帶權(quán)分割技術(shù)，實(shí)現(xiàn)對(duì)2個(gè)處理器的最優(yōu)任務(wù)分配。任務(wù)相互關(guān)系圖T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893在2個(gè)處理器上的執(zhí)行代價(jià)，-表示不能在該處理器上執(zhí)行。在不同處理器上的通信代價(jià)。第43頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201144網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度分別將2個(gè)處理器作為s和t加入任務(wù)關(guān)系圖中，增加s和t到各任務(wù)的邊（共2n條），邊的權(quán)值為任務(wù)在該處理器上的執(zhí)行代價(jià)，形成任務(wù)分配圖。T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893T2T1T44892tT3s3445-773任務(wù)相互關(guān)系圖任務(wù)分配圖第44頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201145網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度利用網(wǎng)絡(luò)最大流量算法在網(wǎng)絡(luò)流量圖中尋找最大網(wǎng)絡(luò)流量（以s為起點(diǎn)、t為終點(diǎn)，初始實(shí)際流量設(shè)為0）。T2T1T44,08,09,02,0tT3s3,04,04,05,0-,07,07,03,0第45頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201146網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度得到的最大網(wǎng)絡(luò)流量，就是最小網(wǎng)絡(luò)分割，也即任務(wù)的最優(yōu)分配。最小分割的權(quán)重（各分割邊的權(quán)之和）即任務(wù)分配后的最小代價(jià)（執(zhí)行代價(jià)和通信代價(jià)）之和。T2T1T44,08,39,02,2tT3s3,34,44,45,4-,67,27,73,0如圖的最小代價(jià)是16，分配方案是T1、T2、T3、T4均在一個(gè)處理器s上執(zhí)行。最小分割第46頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201147網(wǎng)絡(luò)流量技術(shù)實(shí)現(xiàn)最優(yōu)任務(wù)調(diào)度前述是一個(gè)利用網(wǎng)絡(luò)最大流算法得到最小分割的方法，適合在計(jì)算機(jī)環(huán)境下編程實(shí)現(xiàn)。人工計(jì)算相當(dāng)麻煩?。?！一個(gè)可行的人工計(jì)算方法：（“笨”的、窮盡的方法）T1T2T44892tT3s4345-773(34)(38)(33)(16)可能的分割(分配)：T1*T1T2*T1T3T1T4T1T2T3T1T2T4*T1T3T4T1T2T3T4*比較各種分割的權(quán)重。第47頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201148實(shí)時(shí)定期任務(wù)調(diào)度實(shí)時(shí)定期任務(wù)（Ti）定期（間隔周期ti）出現(xiàn)，每次運(yùn)行時(shí)間為ci，在下一次出現(xiàn)前（期限，即n*ti），前一次任務(wù)必須運(yùn)行結(jié)束（實(shí)時(shí)）。處理器的整體利用率：

n

ci/ti

i=0第48頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201149實(shí)時(shí)定期任務(wù)調(diào)度實(shí)時(shí)定期任務(wù)調(diào)度2個(gè)算法（單處理器，多個(gè)獨(dú)立實(shí)時(shí)定期任務(wù)）速率單調(diào)優(yōu)先調(diào)度有高速率（間隔周期小）要求的任務(wù)有高優(yōu)先權(quán)；優(yōu)先權(quán)是固定分配的。期限驅(qū)動(dòng)調(diào)度離結(jié)束期限最近的任務(wù)有高優(yōu)先權(quán)；優(yōu)先權(quán)是動(dòng)態(tài)分配的。2個(gè)算法都是基于優(yōu)先權(quán)和搶占式的。第49頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201150實(shí)時(shí)定期任務(wù)調(diào)度一個(gè)實(shí)時(shí)定期任務(wù)集合是可調(diào)度的，說明任務(wù)集中所有任務(wù)的期限要求都可以滿足。在不同的實(shí)時(shí)定期任務(wù)調(diào)度算法下，一個(gè)實(shí)時(shí)定期任務(wù)集可能可調(diào)度，可能不可調(diào)度?？梢宰C明：對(duì)期限驅(qū)動(dòng)算法，一個(gè)任務(wù)集可調(diào)度的充分條件是：

n

處理器的整體利用率

ci/ti1

i=0對(duì)速率單調(diào)算法，一個(gè)任務(wù)集可調(diào)度的充分條件是：

n

處理器的整體利用率

ci/tin(21/n-1)

i=0

n為任務(wù)個(gè)數(shù)：如n=1時(shí)，限度為1；n=2時(shí)，限度為0.828，n=3時(shí)，限度為0.779。第50頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201151實(shí)時(shí)定期任務(wù)調(diào)度如：2個(gè)實(shí)時(shí)定期任務(wù)開始于同一時(shí)間

T1：c1=3,t1=5 T2：c2=3,t2=8

整體利用率是0.975，如下圖：T1T200c1c2510858調(diào)度點(diǎn)t1t2

對(duì)速率單調(diào)算法，系統(tǒng)是不可調(diào)度的；對(duì)期限驅(qū)動(dòng)算法，系統(tǒng)是可調(diào)度的。225第51頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201152實(shí)時(shí)定期任務(wù)調(diào)度但前述條件是充分條件，而非必要條件，如

T1：c1=3,t1=5 T2：c2=2,t2=7

整體利用率是0.887，高于0.828，但對(duì)速率單調(diào)算法，系統(tǒng)仍是可調(diào)度的。如下圖：T1T200c1c2510757t1t2第52頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201153實(shí)時(shí)定期任務(wù)調(diào)度所有任務(wù)的期限點(diǎn)組成系統(tǒng)的調(diào)度點(diǎn)（但在最長的第一個(gè)期限內(nèi)）。在不同的調(diào)度點(diǎn)，任務(wù)集可能可以調(diào)度，可能不可以調(diào)度。只要有一個(gè)調(diào)度點(diǎn)，任務(wù)集可以調(diào)度，則整個(gè)任務(wù)集就是可以調(diào)度的。（例）3個(gè)任務(wù)的任務(wù)集：

T1：c1=40,t1=100 T2：c2=50,t2=150