分布式系統(tǒng)中的負(fù)載分配

1、分布式系統(tǒng)中的負(fù)載分配第1頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載分配的分類（1） 通常，負(fù)載分配方法可做如下分類：局部和全局 局部負(fù)載分配處理單個(gè)處理器上的進(jìn)程對(duì)時(shí)間片(單元)的分配。全局負(fù)載分配首先進(jìn)行進(jìn)程對(duì)處理器的分配，然后完成每個(gè)處理器內(nèi)這些進(jìn)程的局部調(diào)度。靜態(tài)和動(dòng)態(tài)(在全局類中) 靜態(tài)負(fù)載分配中，進(jìn)程對(duì)處理器的分配是在進(jìn)程執(zhí)行以前的編譯階段完成的，而動(dòng)態(tài)負(fù)載分配要到進(jìn)程在系統(tǒng)中執(zhí)行時(shí)才做出分配。靜態(tài)方法又叫做確定性調(diào)度，而動(dòng)態(tài)方法叫做負(fù)載平衡。第2頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載分配的分類（2）最優(yōu)和次優(yōu)(在靜態(tài)和動(dòng)態(tài)兩種類型中)

2、如果根據(jù)標(biāo)準(zhǔn)，比如最小執(zhí)行時(shí)間和最大系統(tǒng)輸出，可以取得最優(yōu)分配，那么就可以認(rèn)為這種負(fù)載分配方法是最優(yōu)的。一般地，負(fù)載分配問題是NP完全問題。某些情況下，次優(yōu)方案也是可以接受的。有四類算法(對(duì)于最優(yōu)的和次優(yōu)的)被使用：解空間枚舉搜索、圖模型、數(shù)學(xué)編程(例如01編程)和隊(duì)列模型。近似和啟發(fā)式(在次優(yōu)類型中) 在近似方法中，負(fù)載分配算法僅搜索一個(gè)解空間的子集，當(dāng)尋找到一個(gè)好的解時(shí)，終止執(zhí)行。在啟發(fā)式方法中，調(diào)度算法使用某些特殊參數(shù)，能夠近似地對(duì)真實(shí)系統(tǒng)建模。第3頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載分配的分類（3）集中控制的和分散控制的(在動(dòng)態(tài)類型中) 在分散控制中，決策工作

3、被分配給不同的處理器。在集中控制中，這些工作是由一個(gè)處理器完成的。協(xié)作的和非協(xié)作的(對(duì)分散控制) 動(dòng)態(tài)負(fù)載分配機(jī)制可以分成：協(xié)作的分布式對(duì)象間有協(xié)同操作，非協(xié)作的處理器獨(dú)立做出決策。第4頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載分配的分類（4） 下面是另一種負(fù)載分配算法的分類方法，包括一些不能直接歸人上面分類的負(fù)載分配類型：單個(gè)和多個(gè)應(yīng)用程序 多數(shù)負(fù)載分配算法是針對(duì)單個(gè)應(yīng)用程序。多應(yīng)用程序情況可以轉(zhuǎn)換成單個(gè)應(yīng)用程序情況。然而，多應(yīng)用程序情況下的進(jìn)程分配遠(yuǎn)復(fù)雜于單個(gè)應(yīng)用程序的情況。非搶占式的和搶占式的 對(duì)非搶占式的負(fù)載分配算法，一個(gè)任務(wù)(進(jìn)程)開始執(zhí)行后就不能中斷。在搶占式負(fù)

4、載分配算法中，進(jìn)程可以中斷，并從處理器上移走，過后繼續(xù)執(zhí)行。 第5頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載分配的分類（5）非自適應(yīng)的和自適應(yīng)的 非自適應(yīng)負(fù)載分配只使用一種負(fù)載分配算法，不會(huì)依據(jù)系統(tǒng)反饋而改變自己的行為。自適應(yīng)負(fù)載分配能夠根據(jù)系統(tǒng)反饋調(diào)整分配算法。典型地，一個(gè)自適應(yīng)負(fù)載分配算法是許多負(fù)載分配算法的集合，依據(jù)系統(tǒng)的各種參數(shù)來選擇一個(gè)合適的算法。第6頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一靜態(tài)負(fù)載分配靜態(tài)負(fù)載分配算法根據(jù)系統(tǒng)的先驗(yàn)知識(shí)做出決策。運(yùn)行時(shí)負(fù)載不能夠重新分配。靜態(tài)負(fù)載分配算法的目標(biāo)是調(diào)度一個(gè)任務(wù)集合，使它們?cè)诟鱾€(gè)目標(biāo)PE上有最小的執(zhí)行

5、時(shí)間。靜態(tài)負(fù)載分配因此又稱做調(diào)度問題?？傮w上，處理器互連、任務(wù)劃分(粒度決策)和任務(wù)分配是設(shè)計(jì)調(diào)度策略時(shí)的三個(gè)主要因素。如前所述，通常的調(diào)度問題即使在簡單地對(duì)計(jì)算開銷和通信開銷做某種假設(shè)以后，依然是一個(gè)NP完全問題。因此，許多方法利用數(shù)學(xué)工具如圖、啟發(fā)式規(guī)則來得到次優(yōu)的解。 第7頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一任務(wù)圖模型通常，用圖模型表示任務(wù)和PE結(jié)構(gòu)。我們可以用任務(wù)優(yōu)先圖或者任務(wù)交互作用圖對(duì)任務(wù)集合建模。任務(wù)優(yōu)先圖又稱為有向無環(huán)圖(DAG)，每個(gè)鏈接定義了任務(wù)間的優(yōu)先關(guān)系。節(jié)點(diǎn)和鏈接上的標(biāo)記表示任務(wù)執(zhí)行時(shí)間和任務(wù)完成后啟動(dòng)后續(xù)任務(wù)所需的時(shí)間間隔。任務(wù)交互作用圖中，鏈

6、接定義了兩個(gè)任務(wù)間的相互關(guān)系。每個(gè)鏈接賦予一對(duì)數(shù)，表示這兩個(gè)任務(wù)在同一個(gè)PE上時(shí)的通信開銷和在不同PE上時(shí)的通信開銷。第8頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一處理機(jī)互連（1）互連網(wǎng)絡(luò)的拓?fù)淇梢苑譃殪o態(tài)的和動(dòng)態(tài)的。靜態(tài)網(wǎng)絡(luò)由固定的點(diǎn)到點(diǎn)直接連接組成，并且進(jìn)程執(zhí)行過程中不能改變。動(dòng)態(tài)網(wǎng)絡(luò)利用交換機(jī)實(shí)現(xiàn)動(dòng)態(tài)配置來滿足用戶程序的通信要求。 靜態(tài)互連網(wǎng)絡(luò)：16節(jié)點(diǎn)系統(tǒng)的不同連接方案（每個(gè)節(jié)點(diǎn)四個(gè)雙向鏈接）a) 依里?？司W(wǎng)格( Illiac Mesh) b) 圓環(huán)網(wǎng)第9頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一處理機(jī)互連（2）c) 超 立 方 體（4維立方體由兩個(gè)3維

7、立方體節(jié)點(diǎn)互連而成，每維兩個(gè)節(jié)點(diǎn)）d) WK層次網(wǎng)絡(luò)（n層網(wǎng)絡(luò)由四個(gè)（n-1）層網(wǎng)絡(luò)組成，每個(gè)子網(wǎng)絡(luò)是一個(gè)虛擬節(jié)點(diǎn)，1層WK網(wǎng)絡(luò)是基元） 第10頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)互連網(wǎng)絡(luò)（1）有三種類型的動(dòng)態(tài)拓?fù)洌簡渭?jí)、多級(jí)和縱橫制(見圖1-8)。通常，處理機(jī)位于網(wǎng)絡(luò)的兩側(cè)。一個(gè)單級(jí)網(wǎng)絡(luò)由一級(jí)交換單元組成。每個(gè)交換單元是一個(gè)帶兩個(gè)輸入和兩個(gè)輸出的2x2的開關(guān)，輸入和輸出的連接可以是直連或交叉，這由一個(gè)布爾變量控制。圖1-8a表示了一個(gè)完全混洗連接的例子。一個(gè)多級(jí)網(wǎng)絡(luò)包含多級(jí)的交換單元并支持從任意數(shù)量的輸入處理機(jī)到任意數(shù)量的輸出處理機(jī)的連接。在一些網(wǎng)絡(luò)中，輸入和輸出處

8、理機(jī)的同時(shí)連接可能導(dǎo)致使用網(wǎng)絡(luò)通信鏈路的沖突。這種網(wǎng)絡(luò)叫做阻塞式網(wǎng)絡(luò)(見圖1-8c所示的基線制網(wǎng)絡(luò))；否則，就叫做可重新安排的非阻塞式網(wǎng)絡(luò)(見圖1-8d所示的Benes網(wǎng)絡(luò))。在縱橫制交換機(jī)中，每個(gè)輸入可以無阻塞地和一個(gè)空閑的輸出相連(見圖1-8b)。第11頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)互連網(wǎng)絡(luò)（2）圖1-8 a) 8 8混洗交換b) 4 4縱橫制第12頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)互連網(wǎng)絡(luò)（3）c) 8 8基線制d) 8 8 Benes第13頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一任務(wù)劃分一個(gè)給定任務(wù)劃分的粒度

9、定義是任務(wù)分解中影響通信開銷的所有單元的平均尺度。算法可以分成細(xì)粒度、中粒度和粗粒度。如果數(shù)據(jù)單元(即粒度)小，這種算法就是細(xì)粒度。如果數(shù)據(jù)單元大，算法就是粗粒度。介于細(xì)粒度和粗粒度之間的就是中粒度。粒度太大，就會(huì)降低并行度，因?yàn)闈撛诓⑿腥蝿?wù)可能被劃分進(jìn)同一個(gè)任務(wù)而分配給一個(gè)處理器。粒度太小，進(jìn)程切換和通信的開銷就會(huì)增加。任務(wù)劃分的一個(gè)主要目標(biāo)就是盡可能消除處理器間通信引起的開銷。第14頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一任務(wù)劃分的方法水平或者垂直劃分。主要思想是在給定的任務(wù)優(yōu)先圖中垂直或者水平劃分。關(guān)鍵路徑(最長路徑)的概念常常在垂直劃分中使用。水平劃分把給定的任務(wù)分成

10、若干層，任務(wù)的優(yōu)先級(jí)由它們所在的層次決定。通信延遲最小劃分。 主要思想是把通信頻繁的節(jié)點(diǎn)歸成一類。然而，這些需要通信的任務(wù)分配在一個(gè)處理器上會(huì)喪失任務(wù)間的并發(fā)性。如果減小通信延遲的好處抵銷了并行任務(wù)串行化的損失，就采用通信延遲最小劃分。任務(wù)復(fù)制。這是任務(wù)劃分的一個(gè)可選方法。主要思想是通過在PE上復(fù)制任務(wù)來降低通信開銷。這個(gè)方法保留了任務(wù)原有的并行性；但是存儲(chǔ)空間要求和同步開銷增加了?？梢岳萌蝿?wù)復(fù)制來達(dá)到容錯(cuò)性。任務(wù)復(fù)制也被用來實(shí)現(xiàn)無錯(cuò)調(diào)度，以保證處理器出現(xiàn)錯(cuò)誤時(shí)最后計(jì)算結(jié)果正確。第15頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一任務(wù)分配（1）任務(wù)分配是指在多處理機(jī)系統(tǒng)中，針對(duì)某

11、一目標(biāo)，按照一定的策略，將規(guī)模為N的任務(wù)劃分并映射到P臺(tái)處理機(jī)上。在多處理機(jī)系統(tǒng)中，一個(gè)任務(wù)的執(zhí)行時(shí)間為 T f ( tcomp，tcomm，te ) 其中，tcomp為子任務(wù)的最大執(zhí)行時(shí)間，tcomm為完成子任務(wù)所需的通信時(shí)間，而te為其它開銷。一個(gè)問題劃分的子任務(wù)越多，tcomp就越小，而tcomm和te可能很大。tcomm和te的增大不僅可能抵消tcomp的減小，甚至可能使并行處理所得到的效益完全喪失。任務(wù)分配的主要目標(biāo)是尋找一種合適的算法，使T降到最低程度。任務(wù)的靜態(tài)分配又稱確定性調(diào)度，指任務(wù)在運(yùn)行前就指定運(yùn)行的處理機(jī)，并在其生命周期內(nèi)一直駐留在該處理機(jī)上。第16頁，共39頁，2022

12、年，5月20日，10點(diǎn)11分，星期一任務(wù)分配（2）任務(wù)分配就是在給定了互連網(wǎng)絡(luò)的并行系統(tǒng)或者分布式系統(tǒng)中分配顆粒(顆粒是任務(wù)劃分的結(jié)果)。如果任務(wù)圖和處理器圖的節(jié)點(diǎn)數(shù)目都是n，那么就有n!種不同的分配方法把任務(wù)圖Gt里的節(jié)點(diǎn)分配到處理器圖Gp的節(jié)點(diǎn)上。我們把每種方法稱做Gt到Gp的一個(gè)映射。在總執(zhí)行時(shí)間概念下，有些映射比較好。下面是關(guān)于Gp的典型假設(shè)： 存儲(chǔ)器容量無限。 每個(gè)PE有相同的處理能力。 忽略網(wǎng)絡(luò)擁塞，雖然通信進(jìn)程間的距離是影響通 信延遲的因素。 注意，任務(wù)調(diào)度不必要一定分兩個(gè)步驟做，即任務(wù)劃分和任務(wù)分配。分兩步的方法只是為了簡化原本是NP完全的調(diào)度過程。第17頁，共39頁，2022

13、年，5月20日，10點(diǎn)11分，星期一調(diào)度模型前面提到，絕大多數(shù)最優(yōu)調(diào)度問題是NP完全的。主要的研究努力集中在下面的方法： 對(duì)特殊情況的最優(yōu)調(diào)度，比如，帶特殊約 束的模型。 非最優(yōu)調(diào)度，可以分成局部最優(yōu)方案和次 優(yōu)方案。局部最優(yōu)方法使用有效的搜索技術(shù)確定問題解空間中的(局部)最優(yōu)調(diào)度方案。這些方案可以進(jìn)一步分成下面四種：第18頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一局部最優(yōu)方案（1） 解空間枚舉和搜索。首先構(gòu)建狀態(tài)空間，其中每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)可能的調(diào)度方案。它依靠各種搜索技巧如分支搜索和邊界搜索在解空間中尋找解。 數(shù)學(xué)編程。一個(gè)給定的調(diào)度問題轉(zhuǎn)換成一個(gè)整數(shù)、線性或者非線性編程問題

14、。有三個(gè)步驟：(a)一個(gè)目標(biāo)函數(shù)，以求目標(biāo)函數(shù)最小化，常常定義成程序執(zhí)行時(shí)間。(b)一個(gè)約束集合，例如優(yōu)先關(guān)系和通信延遲。(c)使用動(dòng)態(tài)編程技巧解決基于a和b的約束最優(yōu)問題。 模擬退火。模擬退火利用物理退火過程的特性構(gòu)建一種局部最優(yōu)方案的搜索方法。通常這樣一個(gè)過程由三部分組成：(a)對(duì)初始非最優(yōu)調(diào)度方案做小幅度的隨機(jī)的變動(dòng)。(b)評(píng)估新的調(diào)度方案。(c)繼續(xù)這一過程直到?jīng)]有更好的方案產(chǎn)生，也就是說得到了一個(gè)局部最優(yōu)方案。第19頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一局部最優(yōu)方案（2） 遺傳算法。遺傳算法是基于自然界遺傳和進(jìn)化規(guī)律的搜索算法。它結(jié)合已有結(jié)果和搜索空間的新領(lǐng)域來產(chǎn)

15、生新的結(jié)果。Kwok和Ahmad提出了一個(gè)并行遺傳調(diào)度算法。和特殊情況的最優(yōu)解一樣，局部最優(yōu)解也有極大的計(jì)算量并且極端耗費(fèi)時(shí)間。次優(yōu)解法依靠啟發(fā)式方法取得次優(yōu)解。第20頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一任務(wù)靜態(tài)分配算法第21頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一使用兩臺(tái)處理機(jī)的最佳調(diào)度圖8.3 任務(wù)圖和Gantt圖第22頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一性能分析第23頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一最早調(diào)度算法（1）最早調(diào)度算法ESA(Earliest Scheduling Algorithm)的基本

16、思想是，只要系統(tǒng)中有可用的處理機(jī)，便從任務(wù)系統(tǒng)中選出一個(gè)能滿足偏序限制條件的任務(wù)，并立即使其投入運(yùn)行，當(dāng)有多個(gè)能滿足偏序限制條件的任務(wù)時(shí)，選擇其中最早的一個(gè)任務(wù)。我們以圖8.3(a)中的任務(wù)圖為例，說明最早調(diào)度算法的調(diào)度過程。假定系統(tǒng)中有兩臺(tái)處理機(jī)，按ESA算法來分配處理機(jī)的步驟如下： (1)作業(yè)開始時(shí)，只有啟動(dòng)任務(wù)T1能滿足偏序限制條件，故調(diào)度程序?qū)⑻幚頇C(jī)P1分配給T1 ，因無任務(wù)分配給P2，故P2空閑，用表示。 (2)執(zhí)行一個(gè)單位時(shí)間后， T1已完成，T2和T3能滿足偏序限制條件，于是調(diào)度程序?qū)2和P1分別分配給T2和T3 ，使它們并行執(zhí)行。 (3)T3運(yùn)行一個(gè)單位時(shí)間后完成，調(diào)度程序立

17、即把P1分配給唯一能滿足偏序限制條件的任務(wù)T6，調(diào)度程序按ESA算法不斷地為任務(wù)分配處理機(jī)，直至該作業(yè)完成。圖84示出了按ESA算法進(jìn)行調(diào)度產(chǎn)生的Gantt表格的時(shí)間圖。第24頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一最早調(diào)度算法（2）第25頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一最早調(diào)度算法（3）第26頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一考慮通信延遲的調(diào)度算法（1）第27頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一考慮通信延遲的調(diào)度算法（2）圖9-4a顯示了一個(gè)實(shí)例的任務(wù)優(yōu)先圖，給出了處理器間的通信延遲和任務(wù)執(zhí)行時(shí)間。圖9

18、-4b是根據(jù)圖9-4a的數(shù)據(jù)給出的對(duì)處理器P1、P2的調(diào)度結(jié)果。圓圈中的數(shù)對(duì)應(yīng)任務(wù)的執(zhí)行時(shí)間。與每個(gè)鏈接相關(guān)的數(shù)對(duì)應(yīng)于處理器間的通信時(shí)間。兩個(gè)連接任務(wù)分配在不同的處理器上時(shí)就會(huì)發(fā)生通信延遲。例如，w(T1)=2和w(T1,T2)=1表示T1的執(zhí)行時(shí)間是2， T1 T2間處理器間的通信代價(jià)是1（沒有給出處理器內(nèi)的通信代價(jià)）。本例中，兩個(gè)處理器間的通信發(fā)生在有1個(gè)單位通信延遲的T2到T4和有2個(gè)單位通信延遲的T4到T5。總的執(zhí)行時(shí)間是12。第28頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一考慮通信延遲的調(diào)度算法（3）第29頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一考慮

19、通信延遲的調(diào)度算法（4）通信延遲使調(diào)度算法大大地變復(fù)雜。圖9-5a給出了三種不同調(diào)度的例子。如果通信延遲d大于任務(wù)T2的執(zhí)行時(shí)間，圖9-5c的調(diào)度就比圖9-5d的要好。可以說，若通信延遲太大的話，所有任務(wù)分配在一個(gè)處理器上是比較合適的。通常我們總是嘗試盡量增加并行度，同時(shí)盡可能降低通信延遲。然而在多數(shù)時(shí)間這兩個(gè)目標(biāo)是互相矛盾的。因此需要某種程度折衷。有時(shí)可以使用任務(wù)復(fù)制的方法減少通信需求。顯然，由于通過任務(wù)復(fù)制而避免了處理器間的通信，圖9-5b的結(jié)果是最好的。第30頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)負(fù)載分配分布式系統(tǒng)中，許多算法包含不統(tǒng)一的計(jì)算和通信代價(jià)，它們不容易

20、事先確定。某些應(yīng)用中，工作負(fù)載隨著計(jì)算進(jìn)度而變化，這意味著初始好的映射可能會(huì)變壞。動(dòng)態(tài)負(fù)載分配(又稱負(fù)載平衡、負(fù)載轉(zhuǎn)移或者負(fù)載共享)能夠用來恢復(fù)平衡。動(dòng)態(tài)負(fù)載分配算法使用系統(tǒng)狀態(tài)信息(節(jié)點(diǎn)的負(fù)載信息)，至少部分使用，來做負(fù)載分配的決策，而靜態(tài)負(fù)載分配沒有使用這些信息。靜態(tài)負(fù)載分配的限制是以一種一勞永逸的方式把任務(wù)分配給處理器，而且要求預(yù)先知道程序狀態(tài)。包含通信進(jìn)程的系統(tǒng)會(huì)產(chǎn)生沖突，同時(shí)計(jì)算進(jìn)程也可能發(fā)生加速，但是多數(shù)方法忽略這兩種影響。相反地，動(dòng)態(tài)負(fù)載平衡很少假設(shè)關(guān)于例如任務(wù)執(zhí)行時(shí)間或者通信延遲的運(yùn)行時(shí)參數(shù)的先驗(yàn)信息。動(dòng)態(tài)負(fù)載平衡延遲在運(yùn)行時(shí)重分配進(jìn)程，以達(dá)到高性能目標(biāo)。動(dòng)態(tài)負(fù)載分配更好地動(dòng)態(tài)

21、使用了全系統(tǒng)的所有資源，提高了系統(tǒng)的性能。第31頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一基本概念所謂負(fù)載是指處理機(jī)上的用戶進(jìn)程尚未完成的工作量。主要包括進(jìn)程的計(jì)算開銷和通信開銷。在多處理機(jī)系統(tǒng)中，對(duì)節(jié)點(diǎn)機(jī)上系統(tǒng)資源的負(fù)載度量，稱為負(fù)載指標(biāo)。以向量形式表示的某一節(jié)點(diǎn)機(jī)的各項(xiàng)負(fù)載指標(biāo)，稱為負(fù)載向量，它描述的是某一節(jié)點(diǎn)機(jī)的負(fù)載情況。以矩陣形式表示的各節(jié)點(diǎn)機(jī)負(fù)載向量的集合，稱為負(fù)載矩陣，用以描述整個(gè)系統(tǒng)的負(fù)載情況。負(fù)載向量所描述的內(nèi)容，是任務(wù)分配的依據(jù)，其定義必須準(zhǔn)確、完備和有效。負(fù)載向量可以包括多種負(fù)載指標(biāo)，例如：節(jié)點(diǎn)機(jī)就緒隊(duì)列的長度，局部存儲(chǔ)器空閑空間的容量，單位時(shí)間內(nèi)進(jìn)行系統(tǒng)功

22、能調(diào)用的次數(shù)，單位時(shí)間內(nèi)存儲(chǔ)器頁面的調(diào)入調(diào)出次數(shù)，單位時(shí)間內(nèi)CPU被占用的百分比，單位時(shí)間內(nèi)磁盤的讀寫次數(shù)等。大多數(shù)任務(wù)分配算法采用單個(gè)負(fù)載指標(biāo)作為負(fù)載向量，其中選擇節(jié)點(diǎn)機(jī)就緒隊(duì)列長度的頗多。第32頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一負(fù)載平衡為了描述節(jié)點(diǎn)機(jī)上負(fù)載的輕重程度，我們使用負(fù)載閥值進(jìn)行衡量。負(fù)載閥值是節(jié)點(diǎn)機(jī)負(fù)載的界限值，其下界為T1，上界為T2，且T1T2。我們有如下的定義。 輕載：當(dāng)節(jié)點(diǎn)機(jī)的負(fù)載小于T1時(shí)，該節(jié)點(diǎn)機(jī)為輕載； 重載：當(dāng)節(jié)點(diǎn)機(jī)的負(fù)載大于T2時(shí)，該節(jié)點(diǎn)機(jī)為重載； 適載：當(dāng)節(jié)點(diǎn)機(jī)負(fù)載大于T1而小于T2時(shí)，該節(jié)點(diǎn)機(jī)為適載； 空載：當(dāng)節(jié)點(diǎn)機(jī)負(fù)載為0時(shí)，該節(jié)點(diǎn)

23、機(jī)為空載。 負(fù)載平衡：是指系統(tǒng)中的所有處理機(jī)均處于適載狀態(tài)。這是一種嚴(yán)格意義下的負(fù)載平衡。更廣泛意義下的負(fù)載平衡應(yīng)是系統(tǒng)中每個(gè)節(jié)點(diǎn)機(jī)都不是空載，或者當(dāng)某個(gè)節(jié)點(diǎn)機(jī)為空載時(shí)，其它節(jié)點(diǎn)機(jī)均為空載或輕載。第33頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)負(fù)載平衡負(fù)載分配算法可以分為靜態(tài)負(fù)載分配算法和動(dòng)態(tài)負(fù)載分配算法。靜態(tài)負(fù)載分配算法是指在系統(tǒng)中進(jìn)行任務(wù)分配時(shí)，根據(jù)各節(jié)點(diǎn)的負(fù)載情況決定給任務(wù)分配處理機(jī)。動(dòng)態(tài)負(fù)載分配算法通過交換系統(tǒng)的狀態(tài)信息來決定系統(tǒng)負(fù)載的分配。動(dòng)態(tài)負(fù)載分配算法能適應(yīng)系統(tǒng)負(fù)載的變化，比靜態(tài)負(fù)載分配算法更靈活、更有效，但它以一定的系統(tǒng)開銷為代價(jià)。所謂動(dòng)態(tài)負(fù)載平衡，是指系統(tǒng)

24、根據(jù)其負(fù)載變化和進(jìn)程的執(zhí)行情況，自動(dòng)實(shí)現(xiàn)進(jìn)程從重載節(jié)點(diǎn)機(jī)到輕載節(jié)點(diǎn)機(jī)的遷移。重載節(jié)點(diǎn)機(jī)提供遷出進(jìn)程，輕載節(jié)點(diǎn)機(jī)要求遷入進(jìn)程。在分布存儲(chǔ)器結(jié)構(gòu)多處理機(jī)系統(tǒng)中，各節(jié)點(diǎn)處理機(jī)缺乏對(duì)全局信息的了解，處理機(jī)間需要經(jīng)常交換進(jìn)程狀態(tài)信息。這種交換可以按同步方式進(jìn)行，也可以按異步方式進(jìn)行。同步方式簡單，控制方便，但同步時(shí)間間隔難以確定。若間隔偏小，則節(jié)點(diǎn)之間信息交換頻繁，通信開銷大，因此可能會(huì)抵銷負(fù)載平衡所帶來的并行處理效益，若間隔偏大，則達(dá)不到動(dòng)態(tài)平衡負(fù)載的目的，在異步方式下，系統(tǒng)只有在某一事件觸發(fā)下才能引起節(jié)點(diǎn)處理機(jī)間的信息交換。這里的觸發(fā)事件較典型的有兩種：某節(jié)點(diǎn)機(jī)負(fù)載過重和某節(jié)點(diǎn)機(jī)負(fù)載過輕。第34頁，

25、共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)負(fù)載平衡的幾個(gè)策略（1）動(dòng)態(tài)負(fù)載平衡算法由以下四個(gè)策略組成： (1)遷移策略。當(dāng)一個(gè)新任務(wù)在一個(gè)節(jié)點(diǎn)上產(chǎn)生時(shí)，如果它所在的節(jié)點(diǎn)機(jī)的負(fù)載超過了負(fù)載閥值的上界，則該節(jié)點(diǎn)機(jī)就是一個(gè)發(fā)送者，另一方面，一個(gè)節(jié)點(diǎn)機(jī)上的負(fù)載降到了閥值Tl(T2)以下，那么該節(jié)點(diǎn)就被認(rèn)為是一個(gè)接收者。 (2)選擇策略。一旦遷移策略確定了發(fā)送者和接收者之后，選擇策略將用于從發(fā)送者那里選擇哪些任務(wù)作為遷移對(duì)象。最簡單的選擇策略就是選擇一個(gè)最新產(chǎn)生的任務(wù)，在它未執(zhí)行之前就遷移到接收者那里。選擇一個(gè)遷移任務(wù)時(shí)，應(yīng)考慮到由遷移所產(chǎn)生的開銷要小，被遷移的任務(wù)應(yīng)具有較長的生命期，否

26、則遷移的開銷將抵消性能的提高。被遷移的任務(wù)可以是未被啟動(dòng)執(zhí)行的任務(wù)，也可以是正在運(yùn)行的任務(wù)。第35頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)負(fù)載平衡的幾個(gè)策略（2） (3)定位策略。一旦確定了一個(gè)節(jié)點(diǎn)機(jī)是發(fā)送者(或接收者)之后，定位策略負(fù)責(zé)為其尋找合適的搭檔節(jié)點(diǎn)機(jī)。定位策略可有分布式和集中式兩種。分布式定位策略采用輪詢(Polling)方式尋找一個(gè)搭檔機(jī)，也可以采用廣播查詢方式搜索任何可以進(jìn)行分載的節(jié)點(diǎn)機(jī)。在集中式定位策略中，任何節(jié)點(diǎn)機(jī)都可向一個(gè)稱為管理者的特殊節(jié)點(diǎn)機(jī)發(fā)出請(qǐng)求，由管理者確定一個(gè)進(jìn)行分載的合適的節(jié)點(diǎn)機(jī)。第36頁，共39頁，2022年，5月20日，10點(diǎn)11分，星期一動(dòng)態(tài)負(fù)載平衡的幾個(gè)策略（3） (4)信息策略。它用于決定什么時(shí)候(When)，從什么地方