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

分布式系統(tǒng)中的負載分配第一頁，共三十九頁，2022年，8月28日負載分配的分類（1）

通常，負載分配方法可做如下分類：局部和全局局部負載分配處理單個處理器上的進程對時間片(單元)的分配。全局負載分配首先進行進程對處理器的分配，然后完成每個處理器內(nèi)這些進程的局部調(diào)度。靜態(tài)和動態(tài)(在全局類中)

靜態(tài)負載分配中，進程對處理器的分配是在進程執(zhí)行以前的編譯階段完成的，而動態(tài)負載分配要到進程在系統(tǒng)中執(zhí)行時才做出分配。靜態(tài)方法又叫做確定性調(diào)度，而動態(tài)方法叫做負載平衡。第二頁，共三十九頁，2022年，8月28日負載分配的分類（2）最優(yōu)和次優(yōu)(在靜態(tài)和動態(tài)兩種類型中)

如果根據(jù)標準，比如最小執(zhí)行時間和最大系統(tǒng)輸出，可以取得最優(yōu)分配，那么就可以認為這種負載分配方法是最優(yōu)的。一般地，負載分配問題是NP完全問題。某些情況下，次優(yōu)方案也是可以接受的。有四類算法(對于最優(yōu)的和次優(yōu)的)被使用：解空間枚舉搜索、圖模型、數(shù)學(xué)編程(例如0／1編程)和隊列模型。近似和啟發(fā)式(在次優(yōu)類型中)

在近似方法中，負載分配算法僅搜索一個解空間的子集，當(dāng)尋找到一個好的解時，終止執(zhí)行。在啟發(fā)式方法中，調(diào)度算法使用某些特殊參數(shù)，能夠近似地對真實系統(tǒng)建模。第三頁，共三十九頁，2022年，8月28日負載分配的分類（3）集中控制的和分散控制的(在動態(tài)類型中)

在分散控制中，決策工作被分配給不同的處理器。在集中控制中，這些工作是由一個處理器完成的。協(xié)作的和非協(xié)作的(對分散控制)

動態(tài)負載分配機制可以分成：協(xié)作的－－分布式對象間有協(xié)同操作，非協(xié)作的－－處理器獨立做出決策。第四頁，共三十九頁，2022年，8月28日負載分配的分類（4）

下面是另一種負載分配算法的分類方法，包括一些不能直接歸人上面分類的負載分配類型：單個和多個應(yīng)用程序多數(shù)負載分配算法是針對單個應(yīng)用程序。多應(yīng)用程序情況可以轉(zhuǎn)換成單個應(yīng)用程序情況。然而，多應(yīng)用程序情況下的進程分配遠復(fù)雜于單個應(yīng)用程序的情況。非搶占式的和搶占式的對非搶占式的負載分配算法，一個任務(wù)(進程)開始執(zhí)行后就不能中斷。在搶占式負載分配算法中，進程可以中斷，并從處理器上移走，過后繼續(xù)執(zhí)行。

第五頁，共三十九頁，2022年，8月28日負載分配的分類（5）非自適應(yīng)的和自適應(yīng)的非自適應(yīng)負載分配只使用一種負載分配算法，不會依據(jù)系統(tǒng)反饋而改變自己的行為。自適應(yīng)負載分配能夠根據(jù)系統(tǒng)反饋調(diào)整分配算法。典型地，一個自適應(yīng)負載分配算法是許多負載分配算法的集合，依據(jù)系統(tǒng)的各種參數(shù)來選擇一個合適的算法。第六頁，共三十九頁，2022年，8月28日靜態(tài)負載分配靜態(tài)負載分配算法根據(jù)系統(tǒng)的先驗知識做出決策。運行時負載不能夠重新分配。靜態(tài)負載分配算法的目標是調(diào)度一個任務(wù)集合，使它們在各個目標PE上有最小的執(zhí)行時間。靜態(tài)負載分配因此又稱做調(diào)度問題?？傮w上，處理器互連、任務(wù)劃分(粒度決策)和任務(wù)分配是設(shè)計調(diào)度策略時的三個主要因素。如前所述，通常的調(diào)度問題即使在簡單地對計算開銷和通信開銷做某種假設(shè)以后，依然是一個NP完全問題。因此，許多方法利用數(shù)學(xué)工具如圖、啟發(fā)式規(guī)則來得到次優(yōu)的解。

第七頁，共三十九頁，2022年，8月28日任務(wù)圖模型通常，用圖模型表示任務(wù)和PE結(jié)構(gòu)。我們可以用任務(wù)優(yōu)先圖或者任務(wù)交互作用圖對任務(wù)集合建模。任務(wù)優(yōu)先圖又稱為有向無環(huán)圖(DAG)，每個鏈接定義了任務(wù)間的優(yōu)先關(guān)系。節(jié)點和鏈接上的標記表示任務(wù)執(zhí)行時間和任務(wù)完成后啟動后續(xù)任務(wù)所需的時間間隔。任務(wù)交互作用圖中，鏈接定義了兩個任務(wù)間的相互關(guān)系。每個鏈接賦予一對數(shù)，表示這兩個任務(wù)在同一個PE上時的通信開銷和在不同PE上時的通信開銷。第八頁，共三十九頁，2022年，8月28日處理機互連（1）互連網(wǎng)絡(luò)的拓撲可以分為靜態(tài)的和動態(tài)的。靜態(tài)網(wǎng)絡(luò)由固定的點到點直接連接組成，并且進程執(zhí)行過程中不能改變。動態(tài)網(wǎng)絡(luò)利用交換機實現(xiàn)動態(tài)配置來滿足用戶程序的通信要求。

靜態(tài)互連網(wǎng)絡(luò)：16節(jié)點系統(tǒng)的不同連接方案（每個節(jié)點四個雙向鏈接）a)依里埃克網(wǎng)格(IlliacMesh)b)圓環(huán)網(wǎng)第九頁，共三十九頁，2022年，8月28日處理機互連（2）c)超

立

方

體（4維立方體由兩個3維立方體節(jié)點互連而成，每維兩個節(jié)點）d)WK層次網(wǎng)絡(luò)（n層網(wǎng)絡(luò)由四個（n-1）層網(wǎng)絡(luò)組成，每個子網(wǎng)絡(luò)是一個虛擬節(jié)點，1層WK網(wǎng)絡(luò)是基元）

第十頁，共三十九頁，2022年，8月28日動態(tài)互連網(wǎng)絡(luò)（1）有三種類型的動態(tài)拓撲：單級、多級和縱橫制(見圖1-8)。通常，處理機位于網(wǎng)絡(luò)的兩側(cè)。一個單級網(wǎng)絡(luò)由一級交換單元組成。每個交換單元是一個帶兩個輸入和兩個輸出的2x2的開關(guān)，輸入和輸出的連接可以是直連或交叉，這由一個布爾變量控制。圖1-8a表示了一個完全混洗連接的例子。一個多級網(wǎng)絡(luò)包含多級的交換單元并支持從任意數(shù)量的輸入處理機到任意數(shù)量的輸出處理機的連接。在一些網(wǎng)絡(luò)中，輸入和輸出處理機的同時連接可能導(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ò))。在縱橫制交換機中，每個輸入可以無阻塞地和一個空閑的輸出相連(見圖1-8b)。第十一頁，共三十九頁，2022年，8月28日動態(tài)互連網(wǎng)絡(luò)（2）圖1-8a)8╳

8混洗交換b)4╳4縱橫制第十二頁，共三十九頁，2022年，8月28日動態(tài)互連網(wǎng)絡(luò)（3）c)8╳

8基線制d)8╳

8Benes第十三頁，共三十九頁，2022年，8月28日任務(wù)劃分一個給定任務(wù)劃分的粒度定義是任務(wù)分解中影響通信開銷的所有單元的平均尺度。算法可以分成細粒度、中粒度和粗粒度。如果數(shù)據(jù)單元(即粒度)小，這種算法就是細粒度。如果數(shù)據(jù)單元大，算法就是粗粒度。介于細粒度和粗粒度之間的就是中粒度。粒度太大，就會降低并行度，因為潛在并行任務(wù)可能被劃分進同一個任務(wù)而分配給一個處理器。粒度太小，進程切換和通信的開銷就會增加。任務(wù)劃分的一個主要目標就是盡可能消除處理器間通信引起的開銷。第十四頁，共三十九頁，2022年，8月28日任務(wù)劃分的方法水平或者垂直劃分。主要思想是在給定的任務(wù)優(yōu)先圖中垂直或者水平劃分。關(guān)鍵路徑(最長路徑)的概念常常在垂直劃分中使用。水平劃分把給定的任務(wù)分成若干層，任務(wù)的優(yōu)先級由它們所在的層次決定。通信延遲最小劃分。主要思想是把通信頻繁的節(jié)點歸成一類。然而，這些需要通信的任務(wù)分配在一個處理器上會喪失任務(wù)間的并發(fā)性。如果減小通信延遲的好處抵銷了并行任務(wù)串行化的損失，就采用通信延遲最小劃分。任務(wù)復(fù)制。這是任務(wù)劃分的一個可選方法。主要思想是通過在PE上復(fù)制任務(wù)來降低通信開銷。這個方法保留了任務(wù)原有的并行性；但是存儲空間要求和同步開銷增加了?？梢岳萌蝿?wù)復(fù)制來達到容錯性。任務(wù)復(fù)制也被用來實現(xiàn)無錯調(diào)度，以保證處理器出現(xiàn)錯誤時最后計算結(jié)果正確。第十五頁，共三十九頁，2022年，8月28日任務(wù)分配（1）任務(wù)分配是指在多處理機系統(tǒng)中，針對某一目標，按照一定的策略，將規(guī)模為N的任務(wù)劃分并映射到P臺處理機上。在多處理機系統(tǒng)中，一個任務(wù)的執(zhí)行時間為

T＝f(tcomp，tcomm，te)

其中，tcomp為子任務(wù)的最大執(zhí)行時間，tcomm為完成子任務(wù)所需的通信時間，而te為其它開銷。一個問題劃分的子任務(wù)越多，tcomp就越小，而tcomm和te可能很大。tcomm和te的增大不僅可能抵消tcomp的減小，甚至可能使并行處理所得到的效益完全喪失。任務(wù)分配的主要目標是尋找一種合適的算法，使T降到最低程度。任務(wù)的靜態(tài)分配又稱確定性調(diào)度，指任務(wù)在運行前就指定運行的處理機，并在其生命周期內(nèi)一直駐留在該處理機上。第十六頁，共三十九頁，2022年，8月28日任務(wù)分配（2）任務(wù)分配就是在給定了互連網(wǎng)絡(luò)的并行系統(tǒng)或者分布式系統(tǒng)中分配顆粒(顆粒是任務(wù)劃分的結(jié)果)。如果任務(wù)圖和處理器圖的節(jié)點數(shù)目都是n，那么就有n!種不同的分配方法把任務(wù)圖Gt里的節(jié)點分配到處理器圖Gp的節(jié)點上。我們把每種方法稱做Gt到Gp的一個映射。在總執(zhí)行時間概念下，有些映射比較好。下面是關(guān)于Gp的典型假設(shè)：

－存儲器容量無限。

－每個PE有相同的處理能力。

－忽略網(wǎng)絡(luò)擁塞，雖然通信進程間的距離是影響通信延遲的因素。

注意，任務(wù)調(diào)度不必要一定分兩個步驟做，即任務(wù)劃分和任務(wù)分配。分兩步的方法只是為了簡化原本是NP完全的調(diào)度過程。第十七頁，共三十九頁，2022年，8月28日調(diào)度模型前面提到，絕大多數(shù)最優(yōu)調(diào)度問題是NP完全的。主要的研究努力集中在下面的方法：

?

對特殊情況的最優(yōu)調(diào)度，比如，帶特殊約束的模型。

?

非最優(yōu)調(diào)度，可以分成局部最優(yōu)方案和次優(yōu)方案。局部最優(yōu)方法使用有效的搜索技術(shù)確定問題解空間中的(局部)最優(yōu)調(diào)度方案。這些方案可以進一步分成下面四種：第十八頁，共三十九頁，2022年，8月28日局部最優(yōu)方案（1）?

解空間枚舉和搜索。首先構(gòu)建狀態(tài)空間，其中每個狀態(tài)對應(yīng)一個可能的調(diào)度方案。它依靠各種搜索技巧如分支搜索和邊界搜索在解空間中尋找解。?

數(shù)學(xué)編程。一個給定的調(diào)度問題轉(zhuǎn)換成一個整數(shù)、線性或者非線性編程問題。有三個步驟：(a)一個目標函數(shù)，以求目標函數(shù)最小化，常常定義成程序執(zhí)行時間。(b)一個約束集合，例如優(yōu)先關(guān)系和通信延遲。(c)使用動態(tài)編程技巧解決基于a和b的約束最優(yōu)問題。?

模擬退火。模擬退火利用物理退火過程的特性構(gòu)建一種局部最優(yōu)方案的搜索方法。通常這樣一個過程由三部分組成：(a)對初始非最優(yōu)調(diào)度方案做小幅度的隨機的變動。(b)評估新的調(diào)度方案。(c)繼續(xù)這一過程直到?jīng)]有更好的方案產(chǎn)生，也就是說得到了一個局部最優(yōu)方案。第十九頁，共三十九頁，2022年，8月28日局部最優(yōu)方案（2）?

遺傳算法。遺傳算法是基于自然界遺傳和進化規(guī)律的搜索算法。它結(jié)合已有結(jié)果和搜索空間的新領(lǐng)域來產(chǎn)生新的結(jié)果。Kwok和Ahmad提出了一個并行遺傳調(diào)度算法。和特殊情況的最優(yōu)解一樣，局部最優(yōu)解也有極大的計算量并且極端耗費時間。次優(yōu)解法依靠啟發(fā)式方法取得次優(yōu)解。第二十頁，共三十九頁，2022年，8月28日任務(wù)靜態(tài)分配算法第二十一頁，共三十九頁，2022年，8月28日使用兩臺處理機的最佳調(diào)度圖8.3任務(wù)圖和Gantt圖第二十二頁，共三十九頁，2022年，8月28日性能分析第二十三頁，共三十九頁，2022年，8月28日最早調(diào)度算法（1）最早調(diào)度算法ESA(EarliestSchedulingAlgorithm)的基本思想是，只要系統(tǒng)中有可用的處理機，便從任務(wù)系統(tǒng)中選出一個能滿足偏序限制條件的任務(wù)，并立即使其投入運行，當(dāng)有多個能滿足偏序限制條件的任務(wù)時，選擇其中最早的一個任務(wù)。我們以圖8.3(a)中的任務(wù)圖為例，說明最早調(diào)度算法的調(diào)度過程。假定系統(tǒng)中有兩臺處理機，按ESA算法來分配處理機的步驟如下：

(1)作業(yè)開始時，只有啟動任務(wù)T1能滿足偏序限制條件，故調(diào)度程序?qū)⑻幚頇CP1分配給T1

，因無任務(wù)分配給P2，故P2空閑，用表示。

(2)執(zhí)行一個單位時間后，T1已完成，T2和T3能滿足偏序限制條件，于是調(diào)度程序?qū)2和P1分別分配給T2和T3

，使它們并行執(zhí)行。

(3)T3運行一個單位時間后完成，調(diào)度程序立即把P1分配給唯一能滿足偏序限制條件的任務(wù)T6，調(diào)度程序按ESA算法不斷地為任務(wù)分配處理機，直至該作業(yè)完成。圖8．4示出了按ESA算法進行調(diào)度產(chǎn)生的Gantt表格的時間圖。第二十四頁，共三十九頁，2022年，8月28日最早調(diào)度算法（2）第二十五頁，共三十九頁，2022年，8月28日最早調(diào)度算法（3）第二十六頁，共三十九頁，2022年，8月28日考慮通信延遲的調(diào)度算法（1）第二十七頁，共三十九頁，2022年，8月28日考慮通信延遲的調(diào)度算法（2）圖9-4a顯示了一個實例的任務(wù)優(yōu)先圖，給出了處理器間的通信延遲和任務(wù)執(zhí)行時間。圖9-4b是根據(jù)圖9-4a的數(shù)據(jù)給出的對處理器P1、P2的調(diào)度結(jié)果。圓圈中的數(shù)對應(yīng)任務(wù)的執(zhí)行時間。與每個鏈接相關(guān)的數(shù)對應(yīng)于處理器間的通信時間。兩個連接任務(wù)分配在不同的處理器上時就會發(fā)生通信延遲。例如，w(T1)=2和w(T1,T2)=1表示T1的執(zhí)行時間是2，T1T2間處理器間的通信代價是1（沒有給出處理器內(nèi)的通信代價）。本例中，兩個處理器間的通信發(fā)生在有1個單位通信延遲的T2到T4和有2個單位通信延遲的T4到T5?？偟膱?zhí)行時間是12。第二十八頁，共三十九頁，2022年，8月28日考慮通信延遲的調(diào)度算法（3）第二十九頁，共三十九頁，2022年，8月28日考慮通信延遲的調(diào)度算法（4）通信延遲使調(diào)度算法大大地變復(fù)雜。圖9-5a給出了三種不同調(diào)度的例子。如果通信延遲d大于任務(wù)T2的執(zhí)行時間，圖9-5c的調(diào)度就比圖9-5d的要好?？梢哉f，若通信延遲太大的話，所有任務(wù)分配在一個處理器上是比較合適的。通常我們總是嘗試盡量增加并行度，同時盡可能降低通信延遲。然而在多數(shù)時間這兩個目標是互相矛盾的。因此需要某種程度折衷。有時可以使用任務(wù)復(fù)制的方法減少通信需求。顯然，由于通過任務(wù)復(fù)制而避免了處理器間的通信，圖9-5b的結(jié)果是最好的。第三十頁，共三十九頁，2022年，8月28日動態(tài)負載分配分布式系統(tǒng)中，許多算法包含不統(tǒng)一的計算和通信代價，它們不容易事先確定。某些應(yīng)用中，工作負載隨著計算進度而變化，這意味著初始好的映射可能會變壞。動態(tài)負載分配(又稱負載平衡、負載轉(zhuǎn)移或者負載共享)能夠用來恢復(fù)平衡。動態(tài)負載分配算法使用系統(tǒng)狀態(tài)信息(節(jié)點的負載信息)，至少部分使用，來做負載分配的決策，而靜態(tài)負載分配沒有使用這些信息。靜態(tài)負載分配的限制是以一種一勞永逸的方式把任務(wù)分配給處理器，而且要求預(yù)先知道程序狀態(tài)。包含通信進程的系統(tǒng)會產(chǎn)生沖突，同時計算進程也可能發(fā)生加速，但是多數(shù)方法忽略這兩種影響。相反地，動態(tài)負載平衡很少假設(shè)關(guān)于例如任務(wù)執(zhí)行時間或者通信延遲的運行時參數(shù)的先驗信息。動態(tài)負載平衡延遲在運行時重分配進程，以達到高性能目標。動態(tài)負載分配更好地動態(tài)使用了全系統(tǒng)的所有資源，提高了系統(tǒng)的性能。第三十一頁，共三十九頁，2022年，8月28日基本概念所謂負載是指處理機上的用戶進程尚未完成的工作量。主要包括進程的計算開銷和通信開銷。在多處理機系統(tǒng)中，對節(jié)點機上系統(tǒng)資源的負載度量，稱為負載指標。以向量形式表示的某一節(jié)點機的各項負載指標，稱為負載向量，它描述的是某一節(jié)點機的負載情況。以矩陣形式表示的各節(jié)點機負載向量的集合，稱為負載矩陣，用以描述整個系統(tǒng)的負載情況。負載向量所描述的內(nèi)容，是任務(wù)分配的依據(jù)，其定義必須準確、完備和有效。負載向量可以包括多種負載指標，例如：節(jié)點機就緒隊列的長度，局部存儲器空閑空間的容量，單位時間內(nèi)進行系統(tǒng)功能調(diào)用的次數(shù)，單位時間內(nèi)存儲器頁面的調(diào)入／調(diào)出次數(shù)，單位時間內(nèi)CPU被占用的百分比，單位時間內(nèi)磁盤的讀／寫次數(shù)等。大多數(shù)任務(wù)分配算法采用單個負載指標作為負載向量，其中選擇節(jié)點機就緒隊列長度的頗多。第三十二頁，共三十九頁，2022年，8月28日負載平衡

為了描述節(jié)點機上負載的輕重程度，我們使用負載閥值進行衡量。負載閥值是節(jié)點機負載的界限值，其下界為T1，上界為T2，且T1≤T2。我們有如下的定義。

輕載：當(dāng)節(jié)點機的負載小于T1時，該節(jié)點機為輕載；

重載：當(dāng)節(jié)點機的負載大于T2時，該節(jié)點機為重載；

適載：當(dāng)節(jié)點機負載大于T1而小于T2時，該節(jié)點機為適載；

空載：當(dāng)節(jié)點機負載為0時，該節(jié)點機為空載。

負載平衡：是指系統(tǒng)中的所有處理機均處于適載狀態(tài)。這是一種嚴格意義下的負載平衡。更廣泛意義下的負載平衡應(yīng)是系統(tǒng)中每個節(jié)點機都不是空載，或者當(dāng)某個節(jié)點機為空載時，其它節(jié)點機均為空載或輕載。第三十三頁，共三十九頁，2022年，8月28日動態(tài)負載平衡

負載分配算法可以分為靜態(tài)負載分配算法和動態(tài)負載分配算法。靜態(tài)負載分配算法是指在系統(tǒng)中進行任務(wù)分配時，根據(jù)各節(jié)點的負載情況決定給任務(wù)分配處理機。動態(tài)負載分配算法通過交換系統(tǒng)的狀態(tài)信息來決定系統(tǒng)負載的分配。動態(tài)負載分配算法能適應(yīng)系統(tǒng)負載的變化，比靜態(tài)負載分配算法更靈活、更有效，但它以一定的系統(tǒng)開銷為代價。所謂動態(tài)負載平衡，是指系統(tǒng)根據(jù)其負載變化和進程的執(zhí)行情況，自動實現(xiàn)進程從重載節(jié)點機到輕載節(jié)點機的遷移。重載節(jié)點機提供遷出進程，輕載節(jié)點機要求遷入進程。在分布存儲器結(jié)構(gòu)多處理機系統(tǒng)中，各節(jié)點處理機缺乏對全局信息的了解，處理機間需要經(jīng)常交換進程狀態(tài)信息。這種交換可以按同步方式進行，也可以按異步方式進行。同步方式簡單，控制方便，但同步時間間隔難以確定。若間隔偏小，則節(jié)點之間信息交換頻繁，通信開銷大，因此可能會抵銷負載平衡所帶來的并行處理效益，若間隔偏大，則達不到動態(tài)平衡負載的目的，在異步方式下，系統(tǒng)只有在某一事件觸發(fā)下才能引起節(jié)點處理機間的信息交換。這里的觸發(fā)事件較典型的有兩種：某節(jié)點機負載過重和某節(jié)點機負載過輕。第三十四頁，共三十九頁，2022年，8月28日動態(tài)負載平衡的幾個策略（1）動態(tài)負載平衡算法由以下四個策略組成：

(1)遷移策略。當(dāng)一個新任務(wù)在一個節(jié)點上產(chǎn)生時，如果它所在的節(jié)點機的負載超過了負載閥值的上界，則該節(jié)點機就是一個發(fā)送者，另一方面，一個節(jié)點機上的負載降到了閥值Tl(<T2)以下，那么該節(jié)點就被認為是一個接收者。

(2)選擇策略。一旦遷移策略確定了發(fā)送者和接收者之后，選擇策略將用于從發(fā)送者那里選擇哪些任務(wù)作為遷移對象。最簡單的選擇策略就是選擇一個最新產(chǎn)生的任務(wù)，在它未執(zhí)行之前就遷移到接收者那里。選擇一個遷移任務(wù)時，應(yīng)考慮到由遷移所產(chǎn)生的開銷要小，被遷移的任務(wù)應(yīng)具有較長的生命期，否則遷移的開銷將抵消性能的提高。被遷移的任務(wù)可以是未被啟動執(zhí)行的任務(wù)，也可以是正在運行的任務(wù)。第三十五頁，共三十九頁，2022年，8月28日動態(tài)負載平衡的幾個策略（2）

(3)定位策略。一旦確定了一個節(jié)點機是發(fā)送者(或接收者)之后，定位策略負責(zé)為其尋找合適的搭檔節(jié)點機。定位策略可有分布式和集中式兩種。分布式定位策略采用輪詢(Polling)方式尋找一個搭檔機，也可以采用廣播查詢方式搜索任何可以進行分載的節(jié)點機。在集中式定位策略中，任何節(jié)點機都可向一個稱為管理者的特殊節(jié)點機發(fā)出請求，由管理者確定一個進行分載的合適的節(jié)點機。第三十六頁，共三十九頁，2022年，8月28日動態(tài)負載平衡的幾個策略（3）(4)信息策略。它用于決定什么時候(Wh