分布式調(diào)度課件

第十章分布式調(diào)度主講陳志剛教授7/30/20231第十章分布式調(diào)度主講陳志剛教授7/25/2023110.1調(diào)度算法概述調(diào)度算法的分類Casavant和Kuhl對調(diào)度算法做了如下分類：7/30/20232中南大學(xué)信息科學(xué)與工程學(xué)院10.1調(diào)度算法概述調(diào)度算法的分類7/25/20232中南調(diào)度算法的分類

對于大量的實(shí)時(shí)調(diào)度方法而言，還存在著其他一些劃分方法：搶占式(preemptive)和非搶占(non-preemptive)調(diào)度：對搶占式調(diào)度算法，正在運(yùn)行的任務(wù)可能被其他任務(wù)所打斷。而后者一旦任務(wù)開始運(yùn)行，該任務(wù)只有在運(yùn)行完成而主動放棄CPU資源，或是因?yàn)榈却渌Y源被阻塞的情況下才會停止運(yùn)行。實(shí)時(shí)內(nèi)核大都采用了搶占式調(diào)度算法，使關(guān)鍵任務(wù)能夠打斷非關(guān)鍵任務(wù)的執(zhí)行，確保關(guān)鍵任務(wù)的截止時(shí)間能夠得到滿足。10.1調(diào)度算法概述7/30/20233中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的分類10.1調(diào)度算法概述7/25/20233中南調(diào)度算法的分類適應(yīng)性(Adaptive)和非適應(yīng)性(Non-Adaptive)調(diào)度：非適應(yīng)性調(diào)度算法只是用一種負(fù)載分配策略，不會根據(jù)系統(tǒng)的反饋而改變自己的行為。適應(yīng)性調(diào)度算法能夠根據(jù)系統(tǒng)的反饋調(diào)整自己的行為，采用不同的負(fù)載分配策略。一個(gè)適應(yīng)性調(diào)度算法是許多種調(diào)度算法的集合，根據(jù)系統(tǒng)的各種參數(shù)來選擇一種合適的算法。

10.1調(diào)度算法概述7/30/20234中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的分類10.1調(diào)度算法概述7/25/20234中南調(diào)度算法的目標(biāo)和有效性評價(jià)

分布式調(diào)度的基本目標(biāo)是盡快得到計(jì)算結(jié)果和有效地利用資源。其具體目標(biāo)有2個(gè)：負(fù)載平衡(LoadBalancing)：它的努力目標(biāo)是維持整個(gè)分布式系統(tǒng)中各個(gè)資源上的負(fù)載大致相同。負(fù)載共享(LoadSharing)：它的目標(biāo)僅僅是防止某個(gè)處理機(jī)上的負(fù)載過重。10.1調(diào)度算法概述7/30/20235中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的目標(biāo)和有效性評價(jià)10.1調(diào)度算法概述7/25/2調(diào)度算法的目標(biāo)和有效性評價(jià)

從調(diào)度算法的有效性來看，調(diào)度算法分為最優(yōu)調(diào)度算法和次優(yōu)調(diào)度算法。從理論上來說，最優(yōu)調(diào)度只有在能夠完全獲知所有任務(wù)在處理、同步和通信方面的需求，以及硬件的處理和時(shí)間特性的基礎(chǔ)上才能實(shí)現(xiàn)。實(shí)際的應(yīng)用很難實(shí)現(xiàn)，特別是需要獲知的信息處于動態(tài)變化的情況下。即使在這些需要的信息都是可以預(yù)見的情況下，常用的調(diào)度問題仍然是一個(gè)NP難題。調(diào)度的復(fù)雜性將隨調(diào)度需要考慮的任務(wù)和約束特性的數(shù)量呈現(xiàn)出指數(shù)增長。10.1調(diào)度算法概述7/30/20236中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的目標(biāo)和有效性評價(jià)10.1調(diào)度算法概述7/25/2調(diào)度算法的目標(biāo)和有效性評價(jià)選擇調(diào)度算法時(shí)，通常需要綜合考慮如下因素通信代價(jià)：這個(gè)參數(shù)考慮了向一個(gè)給定的節(jié)點(diǎn)傳送或者從一個(gè)給定節(jié)點(diǎn)接收一個(gè)報(bào)文所花費(fèi)的時(shí)間，更為重要的是必須考慮為一個(gè)進(jìn)程分配一個(gè)執(zhí)行地點(diǎn)而引起的通信代價(jià)。執(zhí)行代價(jià)：這個(gè)參數(shù)反映的是將一個(gè)進(jìn)程分配到一個(gè)指定的執(zhí)行節(jié)點(diǎn)，在這個(gè)節(jié)點(diǎn)的執(zhí)行環(huán)境下，執(zhí)行這個(gè)程序所需的額外開銷。資源利用率參數(shù)：表明基于分布式系統(tǒng)當(dāng)前各個(gè)節(jié)點(diǎn)的負(fù)載情況，給一個(gè)進(jìn)程分配的執(zhí)行節(jié)點(diǎn)是否合適。10.1調(diào)度算法概述7/30/20237中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的目標(biāo)和有效性評價(jià)10.1調(diào)度算法概述7/25/2調(diào)度算法的目標(biāo)和有效性評價(jià)次優(yōu)的調(diào)度算法分為兩類：近似的次優(yōu)調(diào)度算法：在近似次優(yōu)調(diào)度方法中，負(fù)載分配算法僅搜索一個(gè)解空間的子集，當(dāng)尋找到一個(gè)好的解時(shí)，終止執(zhí)行。使用近似的次優(yōu)調(diào)度算法必須能夠判定所得到的解是否是可以被接受的，也就是說，必須能夠確定最優(yōu)解和次優(yōu)解之間的近似程度。啟發(fā)式的次優(yōu)調(diào)度算法：使用比較簡明的規(guī)則和一些直覺的規(guī)則來進(jìn)行調(diào)度。這些啟發(fā)式的規(guī)則往往是不能證明其正確性，在特定情況下可能還是錯(cuò)誤的，但是在絕大多數(shù)的情況下是能夠被接受的。10.1調(diào)度算法概述7/30/20238中南大學(xué)信息科學(xué)與工程學(xué)院調(diào)度算法的目標(biāo)和有效性評價(jià)10.1調(diào)度算法概述7/25/2

靜態(tài)調(diào)度算法是根據(jù)系統(tǒng)的先驗(yàn)知識做出決策。運(yùn)行時(shí)負(fù)載不能重新分配。設(shè)計(jì)調(diào)度策略時(shí)要考慮的三個(gè)主要因素是處理機(jī)的互連、任務(wù)的劃分和任務(wù)的分配。通常用圖模型表示任務(wù)和處理機(jī)的結(jié)構(gòu)。我們用任務(wù)優(yōu)先圖或者任務(wù)交互作用圖對任務(wù)集合建模。任務(wù)優(yōu)先圖又稱為有向無環(huán)圖(DAG)，每個(gè)鏈接定義了任務(wù)間的優(yōu)先關(guān)系。節(jié)點(diǎn)和鏈接上的標(biāo)記表示任務(wù)執(zhí)行時(shí)間和任務(wù)完成后啟動后續(xù)任務(wù)所需的時(shí)間間隔。任務(wù)交互作用圖中，鏈接定義了兩個(gè)任務(wù)間的相互關(guān)系。每個(gè)鏈接賦予一對數(shù)，表示這兩個(gè)任務(wù)在同一個(gè)處理機(jī)上時(shí)的通信開銷和在不同處理機(jī)上時(shí)的通信開銷。10.2靜態(tài)調(diào)度7/30/20239中南大學(xué)信息科學(xué)與工程學(xué)院靜態(tài)調(diào)度算法是根據(jù)系統(tǒng)的先驗(yàn)知識做出決策。運(yùn)行時(shí)負(fù)載10.2靜態(tài)調(diào)度7/30/202310中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度7/25/202310中南大學(xué)信息科學(xué)與工任務(wù)劃分與分配

任務(wù)劃分的一個(gè)主要目標(biāo)就是盡可能消除處理器間通信引起的開銷。一個(gè)給定任務(wù)劃分的粒度被定義為任務(wù)的計(jì)算量與通信量的比值。粒度太大，就會降低并行度，因?yàn)闈撛诓⑿腥蝿?wù)可能被劃分進(jìn)同一個(gè)任務(wù)而分配給一個(gè)處理器。粒度太小，進(jìn)程切換和通信的開銷就會增加。任務(wù)聚類：在圖模型中，任務(wù)的劃分被稱作任務(wù)聚類，即在給定的圖模型中對小任務(wù)進(jìn)行分類。任務(wù)劃分把任務(wù)圖當(dāng)作一個(gè)整體，將圖中的小任務(wù)(節(jié)點(diǎn))劃分成不同的聚類，聚類中的小任務(wù)串行執(zhí)行，不同的聚類之間并行執(zhí)行。任務(wù)聚類中可以使用兩種策略：

將不相關(guān)的任務(wù)映射到一個(gè)聚類中；將DAG中一條優(yōu)先路徑上的任務(wù)映射到一個(gè)聚類中。10.2靜態(tài)調(diào)度7/30/202311中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202311中南大任務(wù)劃分與分配任務(wù)劃分的方法關(guān)鍵路徑劃分：主要思想是在給定的任務(wù)優(yōu)先圖中垂直或者水平劃分。關(guān)鍵路徑(最長路徑)的概念常常在垂直劃分中使用。水平劃分把給定的任務(wù)分成若干層，任務(wù)的優(yōu)先級由它們所在的層次決定。通信延遲最小劃分：主要思想是把通信頻繁的節(jié)點(diǎn)歸成一類。然而，這些需要通信的任務(wù)分配在一個(gè)處理器上會喪失任務(wù)間的并發(fā)性。如果減小通信延遲的好處抵銷了并行任務(wù)串行化的損失，就采用通信延遲最小劃分。任務(wù)復(fù)制：為了消除任務(wù)間的通信開銷，將任務(wù)在處理機(jī)上進(jìn)行復(fù)制有時(shí)是最有效的方法。這個(gè)方法保留了任務(wù)原有的并行性；但是存儲空間要求和同步開銷增加了?？梢岳萌蝿?wù)復(fù)制來達(dá)到容錯(cuò)性。任務(wù)復(fù)制也被用來實(shí)現(xiàn)無錯(cuò)調(diào)度，以保證處理器出現(xiàn)錯(cuò)誤時(shí)最后計(jì)算結(jié)果正確。

10.2靜態(tài)調(diào)度7/30/202312中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202312中南大任務(wù)劃分與分配10.2靜態(tài)調(diào)度消除通信延遲的劃分133112T2T3T4T5T63133312T17/30/202313中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度消除通信延遲的劃分13311任務(wù)劃分與分配任務(wù)復(fù)制：10.2靜態(tài)調(diào)度7/30/202314中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202314中南大任務(wù)劃分與分配基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度甘特圖(ganttchart)能夠最有效描述進(jìn)程對處理器的分配情況。甘特圖以處理器為縱坐標(biāo)，以時(shí)間為橫坐標(biāo)。圖中的每個(gè)方塊表示進(jìn)程在某個(gè)系統(tǒng)中的開始時(shí)間、持續(xù)時(shí)間和結(jié)束時(shí)間。處理器內(nèi)的時(shí)間延遲和處理器間的時(shí)間延遲都能夠在圖中體現(xiàn)。

10.2靜態(tài)調(diào)度7/30/202315中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202315中南大任務(wù)劃分與分配基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

10.2靜態(tài)調(diào)度7/30/202316中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202316中南大任務(wù)劃分與分配基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度通信延遲和任務(wù)復(fù)制對調(diào)度的影響：

10.2靜態(tài)調(diào)度7/30/202317中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202317中南大任務(wù)劃分與分配基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度線性聚類與非線性聚類：如果至少有一個(gè)聚類中包含兩個(gè)獨(dú)立的任務(wù)，則聚類是非線性的；否則，聚類就是線性的。

10.2靜態(tài)調(diào)度7/30/202318中南大學(xué)信息科學(xué)與工程學(xué)院任務(wù)劃分與分配10.2靜態(tài)調(diào)度7/25/202318中南大兩種最優(yōu)調(diào)度算法

多數(shù)調(diào)度算法是NP完全的。下面介紹2種有約束的調(diào)度問題，他們有多項(xiàng)式時(shí)間的執(zhí)行復(fù)雜度。兩種方法都假設(shè)通信代價(jià)可以忽略，優(yōu)先圖中每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間是一樣的，即一個(gè)時(shí)間單元。具體限制如下：在第一個(gè)有約束的調(diào)度問題中，優(yōu)先圖是一棵樹。在第二個(gè)有約束的調(diào)度問題中，只有兩個(gè)處理器可用。兩種調(diào)度算法都是最高層優(yōu)先(highest-level-first)方法，也就是說，通過節(jié)點(diǎn)的優(yōu)先級來選擇節(jié)點(diǎn)。

10.2靜態(tài)調(diào)度7/30/202319中南大學(xué)信息科學(xué)與工程學(xué)院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度7/25/202319中南兩種最優(yōu)調(diào)度算法

10.2靜態(tài)調(diào)度

T1

T2

T3

T4

T5

T6

T7

T8

T9

T10

T11

T12

T13

時(shí)間

處理器

P1

P2

P3

0

T1

T2

T3

T4

T5

T7

T6

T9

T10

T8

T12

T11

T13

(a)

樹結(jié)構(gòu)的任務(wù)優(yōu)先圖

(b)對三個(gè)處理器的調(diào)度

樹結(jié)構(gòu)任務(wù)優(yōu)先圖的最優(yōu)調(diào)度7/30/202320中南大學(xué)信息科學(xué)與工程學(xué)院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度兩種最優(yōu)調(diào)度算法

10.2靜態(tài)調(diào)度任務(wù)優(yōu)先圖對雙處理器的最優(yōu)調(diào)度7/30/202321中南大學(xué)信息科學(xué)與工程學(xué)院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度任務(wù)優(yōu)先圖對雙處理器的最優(yōu)基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度任務(wù)相互關(guān)系圖由無向圖Gt(Vt,Et)表示，Vt是進(jìn)程集合，Et是邊集合，每條邊用相關(guān)兩個(gè)進(jìn)程的通信代價(jià)標(biāo)記；處理器圖Gp(Vp,Ep)用頂點(diǎn)集Vp和邊集Ep表示，Vp中的每個(gè)元素是一個(gè)處理器，Ep中的每個(gè)元素是一個(gè)通信信道；然后進(jìn)行分配M：進(jìn)行Vt→Vp的變換和執(zhí)行時(shí)間的估計(jì)。假設(shè)w(u)和w(u,v)分別表示節(jié)點(diǎn)u和鏈接(u,v)的代價(jià)。

10.2靜態(tài)調(diào)度7/30/202322中南大學(xué)信息科學(xué)與工程學(xué)院基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度10.2靜態(tài)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度對分配M的評估：處理器p的計(jì)算負(fù)載為：處理器p的通信負(fù)載為：整個(gè)應(yīng)用程序中總的計(jì)算量是：

整個(gè)應(yīng)用程序中總的通信量是：

7/30/202323中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度對分配M的評估：程序總的執(zhí)行時(shí)間大概是：

α是依據(jù)處理器的執(zhí)行速度確定的值，β是依據(jù)每個(gè)通信信道的通信速度和通信進(jìn)程間的距離確定的值。注意如果兩個(gè)進(jìn)程u和v在Gt中鄰接，它們在Gp的映像(M的映像結(jié)果)可能鄰接也可能不鄰接。理想的情況下，所有通信進(jìn)程被分配在鄰接的處理機(jī)上，以此減少處理器間通信。(兩個(gè)進(jìn)程通常不應(yīng)該映射在一個(gè)處理器上,任務(wù)聚類時(shí),這兩個(gè)進(jìn)程應(yīng)當(dāng)聚類到同一進(jìn)程.)

7/30/202324中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度映射的勢：評估映射質(zhì)量的一個(gè)指標(biāo)是任務(wù)圖Gt中的邊映射到處理器圖Gp中的邊的數(shù)目。這個(gè)數(shù)目被稱作映射的勢(cardinality)，就是Gt中映射到Gp中鄰接處理器的通信進(jìn)程對的數(shù)目。映射的勢不會超過Gt中的鏈接數(shù)目。如果一個(gè)映射的勢最大，它就是一個(gè)理想的映射。

7/30/202325中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度圖中，映射的勢是8，任務(wù)關(guān)系圖中邊的為13條。

7/30/202326中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度嵌入：設(shè)想任務(wù)相互關(guān)系圖和處理器圖被各自看作Gt和Gp。為了通過Gt得到對Gp的有效模擬，也就是在Gp中嵌入Gt。嵌入的不同代價(jià)指標(biāo)：Gt的邊的膨脹。Gt的邊的膨脹定義為被映射成Gt里的一條邊的Gp中對應(yīng)的路徑的長度。嵌入的膨脹為Gt中的最大邊膨脹。嵌入的擴(kuò)大。嵌入的擴(kuò)大定義為Gt里的節(jié)點(diǎn)數(shù)對Gp里的節(jié)點(diǎn)數(shù)的比率。嵌入的擁塞。嵌入的擁塞定義為包含Gp中的一條邊的最大路徑數(shù)，Gp中的每條路徑表示Gt中的一條邊。嵌入的負(fù)載。嵌入的負(fù)載是Gt分配給Gp中任意處理器的進(jìn)程的最大數(shù)目。

7/30/202327中南大學(xué)信息科學(xué)與工程學(xué)院10.2靜態(tài)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度7/25/20典型的動態(tài)調(diào)度算法由以下6個(gè)策略組成：啟動策略決定誰應(yīng)該激活負(fù)載平衡活動。轉(zhuǎn)移策略決定一個(gè)節(jié)點(diǎn)是否在合適的狀態(tài)參與負(fù)載轉(zhuǎn)移。選擇策略選擇最適合轉(zhuǎn)移最能起平衡作用的任務(wù)，并發(fā)送給合適的目標(biāo)處理器。收益性策略量化系統(tǒng)中負(fù)載不平衡程度，并且作為系統(tǒng)負(fù)載平衡潛在受益的估計(jì)，評估系統(tǒng)負(fù)載平衡是否是有收益的。定位策略尋找合適的節(jié)點(diǎn)共享負(fù)載。信息策略決定收集系統(tǒng)中其他節(jié)點(diǎn)狀態(tài)信息的時(shí)機(jī)、收集的方法和收集的信息。

10.3動態(tài)調(diào)度7/30/202328中南大學(xué)信息科學(xué)與工程學(xué)院典型的動態(tài)調(diào)度算法由以下6個(gè)策略組成：10.3動態(tài)調(diào)度7/動態(tài)負(fù)載平衡算法的分類局部和全局

局部負(fù)載分配處理單個(gè)處理器上的進(jìn)程對時(shí)間片(單元)的分配。全局負(fù)載分配首先進(jìn)行進(jìn)程對處理器的分配，然后完成每個(gè)處理器內(nèi)這些進(jìn)程的局部調(diào)度。集中控制的和分散控制的(在動態(tài)類型中)在分散控制中，決策工作被分配給不同的處理器。在集中控制中，這些工作是由一個(gè)處理器完成的。10.3動態(tài)調(diào)度7/30/202329中南大學(xué)信息科學(xué)與工程學(xué)院動態(tài)負(fù)載平衡算法的分類10.3動態(tài)調(diào)度7/25/20232動態(tài)負(fù)載平衡算法的分類協(xié)作的和非協(xié)作的(對分散控制)協(xié)作的－－分布式對象間有協(xié)同操作，非協(xié)作的－－處理器獨(dú)立做出決策。非自適應(yīng)的和自適應(yīng)的非自適應(yīng)負(fù)載分配只使用一種負(fù)載分配算法，不會依據(jù)系統(tǒng)反饋而改變自己的行為。自適應(yīng)負(fù)載分配能夠根據(jù)系統(tǒng)反饋調(diào)整分配算法。典型地，一個(gè)自適應(yīng)負(fù)載分配算法是許多負(fù)載分配算法的集合，依據(jù)系統(tǒng)的各種參數(shù)來選擇一個(gè)合適的算法。10.3動態(tài)調(diào)度7/30/202330中南大學(xué)信息科學(xué)與工程學(xué)院動態(tài)負(fù)載平衡算法的分類10.3動態(tài)調(diào)度7/25/2023310.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類動態(tài)負(fù)載平衡算法的設(shè)計(jì)決策包括如下一些內(nèi)容：非搶先式的和搶先式的:搶先式的主要目的是負(fù)載共享，節(jié)點(diǎn)只分配新到達(dá)的任務(wù)，又稱為任務(wù)放置(placement)。搶先式的算法的主要目的是充分利用系統(tǒng)資源，能夠重新分配正在運(yùn)行的任務(wù)，又稱為進(jìn)程遷移(migration)。采用何種信息策略。信息策略有三種：(a)周期策略；(b)需求策略；(c)狀態(tài)變化驅(qū)動策略。集中控制算法和分散控制算法：集中控制算法有一個(gè)中心處理器從系統(tǒng)中其他處理器收集負(fù)載信息。分散控制算法是通過每個(gè)處理器發(fā)送自己負(fù)載變化情況給所有處理器或者它的鄰居來實(shí)現(xiàn)的。

7/30/202331中南大學(xué)信息科學(xué)與工程學(xué)院10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類7/25/2023310.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類動態(tài)負(fù)載平衡算法的設(shè)計(jì)決策包括如下一些內(nèi)容：采用何種啟動策略。啟動策略有三種：發(fā)送者啟動的、接收者啟動的和對稱啟動的。資源復(fù)制。任務(wù)轉(zhuǎn)移的時(shí)候，涉及到的文件和數(shù)據(jù)也必須被復(fù)制到目標(biāo)處理器。為了減少轉(zhuǎn)移的代價(jià)，常用的任務(wù)和數(shù)據(jù)可以事先被復(fù)制和分配到不同的處理器。進(jìn)程分類。依據(jù)特征來區(qū)分進(jìn)程類型。如果系統(tǒng)中運(yùn)行的進(jìn)程有很大的區(qū)別，它們就必須分在不同的類。當(dāng)系統(tǒng)中有多個(gè)進(jìn)程類型時(shí)，負(fù)載平衡算法必須考慮進(jìn)程的類型，根據(jù)不同的類型做出改變。7/30/202332中南大學(xué)信息科學(xué)與工程學(xué)院10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類7/25/2023310.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參數(shù)

負(fù)載平衡算法使用的參數(shù)：

系統(tǒng)的規(guī)模：處理器的數(shù)目是影響負(fù)載平衡決策的一個(gè)參數(shù)。系統(tǒng)負(fù)載情況：需要避免顛簸現(xiàn)象。處理器的輸入流量：進(jìn)程可以以任何隨機(jī)模式到達(dá)處理器，如果處理器能夠測定自己的輸入流量并且和其他處理器比較，它就能比較容易評估系統(tǒng)即時(shí)的負(fù)載水平，從而對任務(wù)轉(zhuǎn)移做出更好的決策。轉(zhuǎn)移的負(fù)載門限。系統(tǒng)中觸發(fā)任務(wù)轉(zhuǎn)移的負(fù)載門限是一個(gè)關(guān)鍵參數(shù)，因?yàn)檫x擇不當(dāng)會導(dǎo)致系統(tǒng)不平衡和任務(wù)轉(zhuǎn)移的連鎖反應(yīng)。

7/30/202333中南大學(xué)信息科學(xué)與工程學(xué)院10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參數(shù)

負(fù)載平衡算法使用的參數(shù)：

任務(wù)大小。一般來說，轉(zhuǎn)移一個(gè)運(yùn)行時(shí)間太短的任務(wù)是不恰當(dāng)?shù)?。類似的，太大的進(jìn)程或者涉及到大量數(shù)據(jù)和文件的進(jìn)程最好在本地處理器上執(zhí)行。管理成本。組成管理成本的主要因素是：處理器當(dāng)前負(fù)載的測量、處理器決策使用的負(fù)載信息、決策發(fā)生的位置和處理器間任務(wù)的傳送。

7/30/202334中南大學(xué)信息科學(xué)與工程學(xué)院10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參數(shù)

負(fù)載平衡算法使用的參數(shù)：

負(fù)載平衡的視界。一個(gè)節(jié)點(diǎn)能夠在其鄰接節(jié)點(diǎn)范圍內(nèi)為一個(gè)任務(wù)尋找可能的目標(biāo)節(jié)點(diǎn)，在其上運(yùn)行該任務(wù)。這個(gè)鄰接節(jié)點(diǎn)范圍的直徑稱為視界(horizon)。這個(gè)參數(shù)設(shè)置了尋找目標(biāo)節(jié)點(diǎn)過程中探查的鄰接節(jié)點(diǎn)的數(shù)量。資源要求。任務(wù)對系統(tǒng)資源的要求會影響它的轉(zhuǎn)移。需要較多資源的進(jìn)程可能會持續(xù)等待資源變得可用，這就可能影響系統(tǒng)的響應(yīng)時(shí)間。

7/30/202335中南大學(xué)信息科學(xué)與工程學(xué)院10.3動態(tài)調(diào)度動態(tài)負(fù)載平衡算法的分類、設(shè)計(jì)決策和使用的參10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題

工作站共享問題包括：對工作站使用模式的分析，設(shè)計(jì)分配遠(yuǎn)程處理能力的算法和結(jié)構(gòu)，研究遠(yuǎn)程執(zhí)行設(shè)備。

全局調(diào)度機(jī)構(gòu)的主要目標(biāo)有：性能要求：調(diào)度機(jī)構(gòu)占用整個(gè)系統(tǒng)的開銷最小，它們不應(yīng)該占用不使用此機(jī)構(gòu)的應(yīng)用程序的時(shí)間，也不應(yīng)該使被調(diào)度的應(yīng)用程序的執(zhí)行產(chǎn)生大的延遲。支持的系統(tǒng)規(guī)模：能支持幾百個(gè)甚至上千個(gè)工作站。

7/30/202336中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/2010.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題

容錯(cuò)：一個(gè)或幾個(gè)機(jī)器崩潰時(shí)，系統(tǒng)的遠(yuǎn)程執(zhí)行設(shè)備應(yīng)該在幾秒鐘之后能夠繼續(xù)工作。公平性：不管分配作業(yè)到哪個(gè)機(jī)器上，為該作業(yè)提供的性能都是同樣可接受的。自治性：工作站屬于個(gè)人所有，其他人使用不應(yīng)影響主人的工作。7/30/202337中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/210.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題

有關(guān)負(fù)載的信息是如何傳送的，使用公布的還是回答查詢的辦法？即選擇哪一種信息策略。誰主動發(fā)起遠(yuǎn)程執(zhí)行的請求，是作業(yè)進(jìn)入的顧客節(jié)點(diǎn)(源節(jié)點(diǎn))還是處理此作業(yè)的節(jié)點(diǎn)(服務(wù)員節(jié)點(diǎn))？這里所要解決的是選擇什么樣的啟動策略。誰來決策為一個(gè)作業(yè)(程序)選擇一個(gè)合適的執(zhí)行主機(jī)，請求的發(fā)起者還是一個(gè)集中的服務(wù)員節(jié)點(diǎn)？這里要解決的是定位策略的問題。這是設(shè)計(jì)全局調(diào)度設(shè)施在結(jié)構(gòu)上要解決的三個(gè)主要問題。7/30/202338中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/210.4空閑工作站的調(diào)度結(jié)構(gòu)集中式調(diào)度

集中式調(diào)度是在系統(tǒng)中有一個(gè)中央調(diào)度服務(wù)員，負(fù)責(zé)搜集狀態(tài)信息并做出全部調(diào)度決策。各機(jī)器周期性地向它發(fā)送狀態(tài)更新報(bào)文，報(bào)告它們的負(fù)載信息；顧客向它發(fā)送遠(yuǎn)程執(zhí)行請求。中央調(diào)度服務(wù)員根據(jù)負(fù)載情況，建立一個(gè)主機(jī)候選者的有序表，對顧客的遠(yuǎn)程執(zhí)行請求進(jìn)行響應(yīng)。使用中央調(diào)度服務(wù)員查詢狀態(tài)會減少報(bào)文傳送數(shù)目。但是容易產(chǎn)生狀態(tài)信息過時(shí)的問題。解決集中式調(diào)度的容錯(cuò)問題的典型方法是提供多個(gè)備用服務(wù)員。集中調(diào)度的最后一個(gè)問題是在何處運(yùn)行調(diào)度程序。調(diào)度程序沒有任何特殊要求，可放到任何空閑機(jī)器上，并可根據(jù)需要遷移。7/30/202339中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)集中式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度

在全分散方案中，每個(gè)機(jī)器自己進(jìn)行選擇活動。它必須不斷地記錄整個(gè)系統(tǒng)狀態(tài)或者當(dāng)需要時(shí)查詢系統(tǒng)狀態(tài)信息。在前一種情況下，每個(gè)機(jī)器(即使是忙碌的機(jī)器)要定期地產(chǎn)生更新報(bào)文并向其他主機(jī)廣播(公布)。而每個(gè)主機(jī)中維持一個(gè)主機(jī)狀態(tài)表。在后一種情況下只有對主機(jī)選擇有興趣的那些主機(jī)才關(guān)心狀態(tài)信息(查詢)。采用查詢方法，即每個(gè)需要獲得空閑主機(jī)的顧客機(jī)發(fā)送查詢報(bào)文請求得到當(dāng)前狀態(tài)信息，請求中包括所需資源的說明。該顧客從所有愿意成為候選主機(jī)的機(jī)器那里得到回答，并從中選取一個(gè)最合適的機(jī)器。7/30/202340中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度

兩個(gè)要解決的問題。第一是查詢者可能要求接收大量的、幾乎是同時(shí)到來的回答報(bào)文，以及N2報(bào)文的傳送要消耗網(wǎng)絡(luò)的帶寬。第二是可能產(chǎn)生沖突。

第一個(gè)問題的解決方法：一個(gè)相當(dāng)簡單的辦法是放寬選擇主機(jī)的標(biāo)準(zhǔn)，它可以不是最佳的，即不是負(fù)載最輕的，但可以是較輕的、較好的。查詢者只考慮全部回答報(bào)文中的一部分，扔掉其余部分。第二個(gè)問題解決辦法是在遷移程序前先發(fā)送一個(gè)執(zhí)行請求，被選擇機(jī)只對第一個(gè)請求回答并等待申請者傳送被執(zhí)行的程序。7/30/202341中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)混合式調(diào)度集中式方法支持的規(guī)模較大，但集中式方法可靠性較差，不易擴(kuò)充。分散式方法具有較高可靠性，實(shí)現(xiàn)簡單，容易擴(kuò)充，但效率較低?；旌鲜秸{(diào)度結(jié)構(gòu)中，每個(gè)工作站有一個(gè)局部調(diào)度程序，還有一個(gè)后臺作業(yè)隊(duì)列，用戶提交的作業(yè)和遠(yuǎn)程作業(yè)都放到此隊(duì)列中。有一個(gè)工作站除了局部調(diào)度程序和作業(yè)隊(duì)列外，還有一個(gè)協(xié)調(diào)程序(協(xié)調(diào)者)。協(xié)調(diào)者定期(例如每兩分鐘)向各個(gè)工作站查詢，看有哪些工作站可用作遠(yuǎn)程執(zhí)行的源，哪些工作站后臺作業(yè)隊(duì)列中有作業(yè)等待處理。中央?yún)f(xié)調(diào)者為有后臺作業(yè)等候的工作站上的調(diào)度程序分配空閑工作站資源。7/30/202342中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)混合式調(diào)度7/25/2023410.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法

進(jìn)程轉(zhuǎn)移是指進(jìn)程的重新定位。其目的主要是為了有效地利用系統(tǒng)資源.用戶在執(zhí)行若干相對獨(dú)立的任務(wù)時(shí)，可把它們從某些重負(fù)載工作站移到另外一些輕負(fù)載工作站上加快完成。進(jìn)程轉(zhuǎn)移的形式：通過進(jìn)程放置(placement)的非搶先(non-preemptive)方式和通過進(jìn)程遷移(migration)的搶先(preemptive)方式.7/30/202343中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法10.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法

進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的一般要求有以下兩點(diǎn)：透明性。指的是一個(gè)進(jìn)程執(zhí)行的行為及結(jié)果不應(yīng)受執(zhí)行位置的影響，應(yīng)該是位置無關(guān)的.為了轉(zhuǎn)移此進(jìn)程不必用特定方式重新編寫程序。也就是說，這些進(jìn)程轉(zhuǎn)移到遠(yuǎn)程執(zhí)行環(huán)境后必須與在原地一樣(名字、操作和數(shù)據(jù)，但不包括硬件)有效性。遷移一個(gè)進(jìn)程需要時(shí)間，支持該進(jìn)程遠(yuǎn)程執(zhí)行也需要時(shí)間，這些時(shí)間應(yīng)盡量短。7/30/202344中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法10.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法

判斷是否值得進(jìn)行進(jìn)程遷移和遠(yuǎn)程執(zhí)行有多個(gè)計(jì)算量很大的進(jìn)程在一個(gè)工作站上運(yùn)行；運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)超過在遠(yuǎn)程啟動執(zhí)行一個(gè)進(jìn)程的時(shí)間；從所選擇的遠(yuǎn)程節(jié)點(diǎn)上被驅(qū)逐的可能性很?。贿M(jìn)程剛建立不久，還未來得及使用很多地址空間。7/30/202345中南大學(xué)信息科學(xué)與工程學(xué)院10.4空閑工作站的調(diào)度結(jié)構(gòu)進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行的目的和方法10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行Sprite的進(jìn)程遷移和遠(yuǎn)程執(zhí)行設(shè)備

Sprite是對進(jìn)程遷移透明性支持較完全的一個(gè)系統(tǒng)。它將高度透明性作為進(jìn)程遷移設(shè)計(jì)的一個(gè)主要目標(biāo)，采用四種不同的技術(shù)支持這些透明性:

利用專用的文件服務(wù)器,使得一些系統(tǒng)調(diào)用(如文件操作)位置無關(guān)；利用狀態(tài)轉(zhuǎn)移(transfer)技術(shù)，將與遷移進(jìn)程有關(guān)的一些狀態(tài)轉(zhuǎn)移到目的節(jié)點(diǎn)；利用轉(zhuǎn)發(fā)(forward)技術(shù)，轉(zhuǎn)發(fā)與位置有關(guān)的系統(tǒng)調(diào)用；采用專門技術(shù)，對幾個(gè)特殊的系統(tǒng)調(diào)用(如fork、exec等)7/30/202346中南大學(xué)信息科學(xué)與工程學(xué)院10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行Sprite的進(jìn)程遷移和遠(yuǎn)程執(zhí)行10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行Sprite的進(jìn)程遷移和遠(yuǎn)程執(zhí)行設(shè)備

Sprite系統(tǒng)的進(jìn)程遷移包括以下幾個(gè)步驟：

向目的節(jié)點(diǎn)發(fā)送一個(gè)RPC，確認(rèn)是否允許遷移該進(jìn)程。當(dāng)要遷移該進(jìn)程時(shí)，使用標(biāo)準(zhǔn)信號中斷該進(jìn)程的執(zhí)行。傳送該進(jìn)程的“進(jìn)程狀態(tài)”，包括各寄存器的內(nèi)容、用戶標(biāo)識符和小組標(biāo)識符、信號處理信息、基地節(jié)點(diǎn)和該進(jìn)程標(biāo)識符。傳送虛擬地址空間。把所有重寫的頁送到文件服務(wù)器，把對應(yīng)的交換文件的頁表和說明符送到目的節(jié)點(diǎn)。將該進(jìn)程已打開的文件的說明符和當(dāng)前工作目錄打包并傳送。發(fā)送一個(gè)RPC結(jié)束遷移，允許被遷移的進(jìn)程在目的節(jié)點(diǎn)恢復(fù)執(zhí)行。最后，該進(jìn)程在目的節(jié)點(diǎn)上恢復(fù)。

7/30/202347中南大學(xué)信息科學(xué)與工程學(xué)院10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行Sprite的進(jìn)程遷移和遠(yuǎn)程執(zhí)行10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行V系統(tǒng)中的可搶先的遠(yuǎn)程執(zhí)行設(shè)備

V系統(tǒng)的可搶先遠(yuǎn)程執(zhí)行設(shè)備使用預(yù)復(fù)制方法提高性能：為了減少凍結(jié)時(shí)間，可使用預(yù)復(fù)制方法，在凍結(jié)前就多次復(fù)制全部地址空間，每次復(fù)制上次復(fù)制以來被修改的頁。多次復(fù)制后被修改的部分僅剩下很少的部分，這時(shí)再凍結(jié)，把剩余部分復(fù)制過去。這樣僅用最短時(shí)間凍結(jié)。7/30/202348中南大學(xué)信息科學(xué)與工程學(xué)院10.5進(jìn)程轉(zhuǎn)移和遠(yuǎn)程執(zhí)行V系