分布式系統(tǒng)中的處理機管理課件

1、1 1 進程調度進程調度1.1.進程的狀態(tài)與切換進程的狀態(tài)與切換 進程的狀態(tài)可以分為活躍態(tài)與非活躍態(tài)兩大類。進程的狀態(tài)可以分為活躍態(tài)與非活躍態(tài)兩大類。 運行態(tài)：所屬線程正在占用運行態(tài)：所屬線程正在占用cpucpu運行運行 就緒態(tài)：具備運行條件，但未占有就緒態(tài)：具備運行條件，但未占有cpucpu運行運行 等待態(tài)：由于自身原因不能運行，但傳輸尚未結束等待態(tài)：由于自身原因不能運行，但傳輸尚未結束 掛起態(tài)：由于自身原因不能運行，放棄所占用的資源掛起態(tài)：由于自身原因不能運行，放棄所占用的資源 原則上，統(tǒng)一進程的線程應該在同一原則上，統(tǒng)一進程的線程應該在同一cpucpu上運行。上運行。 現(xiàn)在，線程是系統(tǒng)中

2、的調度單位。現(xiàn)在，線程是系統(tǒng)中的調度單位。 線程調度管理的方式線程調度管理的方式 核心管理模式：核心管理模式： 對每一個進程。核心為其建立一個線程調度表。同一個對每一個進程。核心為其建立一個線程調度表。同一個進程的線程可以并行。進程的線程可以并行。線線程程線線程程線線程程線線程程核核 心心 進程管理模式：進程管理模式： 在用戶區(qū)內進程創(chuàng)建一個虛擬處理器（又稱為進程在用戶區(qū)內進程創(chuàng)建一個虛擬處理器（又稱為進程的運行系統(tǒng)），對應一個物理的運行系統(tǒng)），對應一個物理cpu。線程可以在阻塞時調線程可以在阻塞時調用運行系統(tǒng)保留現(xiàn)場和掛起，運行系統(tǒng)負責調度線程運行。用運行系統(tǒng)保留現(xiàn)場和掛起，運行系統(tǒng)負責調度

3、線程運行。這樣進程可以設定自己的調度策略，但效率較低。這樣進程可以設定自己的調度策略，但效率較低。 現(xiàn)代分布式系統(tǒng)中，線程是獨立的運行單位和調度單現(xiàn)代分布式系統(tǒng)中，線程是獨立的運行單位和調度單位。位。2. 線程組織模型線程組織模型 線程工作的組織方式分為三種：派遣工作模型（在進程線程工作的組織方式分為三種：派遣工作模型（在進程中設立派遣進程負責選擇工作線程運行）、小組模型（線中設立派遣進程負責選擇工作線程運行）、小組模型（線程平等工作）和管道模型（流水線方式）。程平等工作）和管道模型（流水線方式）。 派遣模型派遣模型 派遣線程派遣線程工作線程工作線程郵郵 箱箱核核 心心共享共享cache進進

4、程程工作請求工作請求工作請求工作請求 小組模型小組模型 郵郵 箱箱核核 心心工作請求工作請求進進 程程共享共享cache工作請求工作請求 管道模型管道模型 郵郵 箱箱工作請求工作請求核核 心心進進 程程共享共享cache工作請求工作請求 動態(tài)模型動態(tài)模型 進程初啟時只有一個線程，稱為服務線程，向核心輸進程初啟時只有一個線程，稱為服務線程，向核心輸入進程的接口。入進程的接口。 核心準備調用數(shù)據(jù)借口，例如數(shù)據(jù)棧，供服務線程和核心準備調用數(shù)據(jù)借口，例如數(shù)據(jù)棧，供服務線程和客戶線成共享。客戶線成共享。 客戶線程初啟后，從核心輸入這些接口。客戶線程初啟后，從核心輸入這些接口。 客戶線程調用過程時，將參數(shù)

5、入棧，將過程名存入指客戶線程調用過程時，將參數(shù)入棧，將過程名存入指定寄存器，通過定寄存器，通過trap進入核心。進入核心。 核心查看知道是本地調用，將客戶線程內存映射到服核心查看知道是本地調用，將客戶線程內存映射到服務線程地址空間，啟動服務進程，執(zhí)行過程調用。務線程地址空間，啟動服務進程，執(zhí)行過程調用。 遠程調用到來時，核心創(chuàng)建一個線程，將遠程請求消遠程調用到來時，核心創(chuàng)建一個線程，將遠程請求消息映射到它的地址空間，線程相應服務請求，執(zhí)行過程調息映射到它的地址空間，線程相應服務請求，執(zhí)行過程調用，結束后自動消亡。用，結束后自動消亡。2 2 負載平衡與系統(tǒng)模型負載平衡與系統(tǒng)模型工作站模型工作站模

6、型 屬于對稱型模型，各結點是平等的。屬于對稱型模型，各結點是平等的。 負載平衡的要點負載平衡的要點之一是如何發(fā)現(xiàn)空載結點（潛在的計算服務器）。涉及三個之一是如何發(fā)現(xiàn)空載結點（潛在的計算服務器）。涉及三個問題：問題： 如何發(fā)現(xiàn)空載結點如何發(fā)現(xiàn)空載結點 遠程進程如何透明地運行遠程進程如何透明地運行 當本地進程需要運行時，如何處理當本地進程需要運行時，如何處理 服務器驅動服務器驅動 每個結點裝備空載監(jiān)測程序，監(jiān)測自身。每個結點裝備空載監(jiān)測程序，監(jiān)測自身。 設管理者，維護空載注冊表，記錄空載結點地址。設管理者，維護空載注冊表，記錄空載結點地址。 每個結點發(fā)現(xiàn)自己空載時，發(fā)消息給管理者，后者將其每個結點

7、發(fā)現(xiàn)自己空載時，發(fā)消息給管理者，后者將其地址記入空載注冊表。地址記入空載注冊表。 a結點需要分散計算負載，發(fā)遠程命令詢問管理者，后結點需要分散計算負載，發(fā)遠程命令詢問管理者，后者給它發(fā)送空載結點地址者給它發(fā)送空載結點地址b，a結點向結點向b發(fā)送遠程任務，發(fā)送遠程任務，b執(zhí)行遠程任務，負載增加，發(fā)消息要求管理者刪去自己。執(zhí)行遠程任務，負載增加，發(fā)消息要求管理者刪去自己。 為避免幾個結點同時發(fā)現(xiàn)某空載結點引起沖突，可引入二為避免幾個結點同時發(fā)現(xiàn)某空載結點引起沖突，可引入二次確認：請求者向空載結點發(fā)送請求確認消息，空載結點次確認：請求者向空載結點發(fā)送請求確認消息，空載結點選擇其中一個結點為雇主，要求

8、管理者從空載表中刪去自選擇其中一個結點為雇主，要求管理者從空載表中刪去自己，向雇主發(fā)回確認消息。未接到確認的結點只好再次向己，向雇主發(fā)回確認消息。未接到確認的結點只好再次向管理者詢問。管理者詢問。管理者管理者注冊程序注冊程序空載注空載注冊表冊表請求者請求者空載結點空載結點遠程過程遠程過程遠程過程遠程過程1. 空載注冊空載注冊2. 請求空載結點請求空載結點3. 回復空載結點回復空載結點4. 要求確認要求確認5. 注銷空載注銷空載6. 確認確認7. 設置運行環(huán)境設置運行環(huán)境8. 啟動遠程進程啟動遠程進程9. 進程運行進程運行10. 進程結束進程結束11. 返回結果返回結果 客戶驅動客戶驅動 結點需

9、要分散負載時，廣播請求，指明具體要求。結點需要分散負載時，廣播請求，指明具體要求。 其他結點收到后，根據(jù)情況自行判斷，同意者回復。其他結點收到后，根據(jù)情況自行判斷，同意者回復。 收到所有回復后，選取負載最小者，分散計算負載。收到所有回復后，選取負載最小者，分散計算負載。請求者請求者其他結點其他結點其他結點其他結點其他結點其他結點其他結點其他結點11112341廣播分散負載請求廣播分散負載請求234應答：負載空應答：負載空發(fā)送運行環(huán)境發(fā)送運行環(huán)境 分散負載注意問題分散負載注意問題 遠程進程的運行環(huán)境必須與本地環(huán)境一樣遠程進程的運行環(huán)境必須與本地環(huán)境一樣 遠程進程運行中的某些系統(tǒng)調用必須發(fā)回本地執(zhí)

10、行，遠程進程運行中的某些系統(tǒng)調用必須發(fā)回本地執(zhí)行，如鍵盤、鼠標操作等人機交互工作如鍵盤、鼠標操作等人機交互工作 涉及時間處理要十分慎重，因為機器時間可能不同涉及時間處理要十分慎重，因為機器時間可能不同 空載結點本地進程要求運行時的策略空載結點本地進程要求運行時的策略 不理，等遠程進程完成：簡單但不友好不理，等遠程進程完成：簡單但不友好 立即殺死遠程進程，讓位于本地進程：簡單但造成計立即殺死遠程進程，讓位于本地進程：簡單但造成計算浪費，有時會產生完整性問題（如文件），需要額外維算浪費，有時會產生完整性問題（如文件），需要額外維護工作護工作 先給警告，留一段善后處理時間，然后殺死遠程進程先給警告，

11、留一段善后處理時間，然后殺死遠程進程 注意：遠程進程執(zhí)行完成以后，接點必須恢復到空載時注意：遠程進程執(zhí)行完成以后，接點必須恢復到空載時的狀況。的狀況。 包括：包括： 清除所有遠程進程及其子進程清除所有遠程進程及其子進程 清除這期間的郵箱內容、網絡連接以及其它系統(tǒng)級數(shù)據(jù)清除這期間的郵箱內容、網絡連接以及其它系統(tǒng)級數(shù)據(jù) 清除這期間的臨時文件清除這期間的臨時文件 清理清理cache 做好以后可能到來的與遠程進程有關的消息的拒絕預防做好以后可能到來的與遠程進程有關的消息的拒絕預防工作工作 處理器池模型處理器池模型 單服務器基本排隊模型單服務器基本排隊模型 令用戶產生請求令用戶產生請求 /秒，處理機能處

12、理請求秒，處理機能處理請求 /秒，平均周轉時間秒，平均周轉時間t 1/( - )如果服務器處理能力加大，有如果服務器處理能力加大，有n個個cpu，處理能力將為處理能力將為n ，而請求率同步，而請求率同步擴大為擴大為n ，平均周轉時間將為，平均周轉時間將為1/(n -n ) = t/n 原因：減少了原因：減少了cpu的空閑率的空閑率 排隊論的結論是反對分布式計算的重要論據(jù)，但分布式的潛在好處（代排隊論的結論是反對分布式計算的重要論據(jù)，但分布式的潛在好處（代價、靈活、方便、堅固價、靈活、方便、堅固）也是不可替代的。）也是不可替代的。m1m2m3m4m5s用用 戶戶用用 戶戶用用 戶戶 分布式系統(tǒng)任

13、務分配示意分布式系統(tǒng)任務分配示意 假定：所有機器兼容，全連通。假定：所有機器兼容，全連通。 優(yōu)化目標：平均相應時間最小化，響應率最小化優(yōu)化目標：平均相應時間最小化，響應率最小化 響應率響應率 = 進程實際運行時間進程實際運行時間/在無負載標準在無負載標準cpu上的運行時間上的運行時間 實際運行時間包括排隊、調度、通信、計算的花費的時間實際運行時間包括排隊、調度、通信、計算的花費的時間 任務類型：可遷移任務，不可遷移任務任務類型：可遷移任務，不可遷移任務 考慮：考慮： 任務間的通信開銷（任務間的通信開銷（itc）問題問題 m1m2m3m4m5sp1p2pn 基于圖論的任務分配策略基于圖論的任務分

14、配策略 通信圖通信圖 圖中：圓圈表示任務，旁邊的數(shù)字表示計算工作量；連線表示有通圖中：圓圈表示任務，旁邊的數(shù)字表示計算工作量；連線表示有通信，連線的權（可以是信，連線的權（可以是 ，顯然兩個任務不能異地計算），顯然兩個任務不能異地計算）表示開銷。表示開銷。 假定同一個結點上的兩個任務的通信量為零。任務優(yōu)化的目標是處假定同一個結點上的兩個任務的通信量為零。任務優(yōu)化的目標是處理開銷和理開銷和itc之和最小。之和最小。abcd512 863639 數(shù)據(jù)結構定義數(shù)據(jù)結構定義 分配矩陣分配矩陣 x 1 若任務若任務mi分配給處理機分配給處理機pk xik = 0 若任務若任務mi不在處理機不在處理機pk

15、上上 處理開銷矩陣處理開銷矩陣q qik表示任務表示任務mi在處理機在處理機pk上的處理開銷，若為上的處理開銷，若為 ，表示，表示mi不不能在能在pk上運行上運行 itc開銷矩陣開銷矩陣c cij表示任務表示任務mi和和mj之間的之間的itc開銷，若為開銷，若為0，表示兩個任務，表示兩個任務在同一處理機上在同一處理機上 于是，于是，itc總開銷總開銷t = qkixik + cijxikxjhkihkji 其中，第一項是每個任務在其分配的處理機上的運行開銷，第二其中，第一項是每個任務在其分配的處理機上的運行開銷，第二項代表不同處理機上任務間的項代表不同處理機上任務間的itcitc開銷。開銷。

16、以上圖為例，任務以上圖為例，任務c和和d之間通信量為無窮大，顯然應該分配在一之間通信量為無窮大，顯然應該分配在一個結點上。如有兩個結點，那么分配將是個結點上。如有兩個結點，那么分配將是 itc itc開銷：開銷： a b c d 處理開銷：處理開銷： a b c d a 0 0 8 6 0 8 6 處理機處理機1 3 9 6 3 1 3 9 6 3 b 0 0 12 0 12 0 處理機處理機2 3 9 6 3 2 3 9 6 3 c 8 12 0 0 0 d 6 0 0 0 a，bc，d 顯然，優(yōu)化的方向是力求使得目標函數(shù)顯然，優(yōu)化的方向是力求使得目標函數(shù)x最小。最小。 例：例： 一張完全圖

17、一張完全圖利用最小分割算法得到分配結果為利用最小分割算法得到分配結果為 p1：a，b，c，d，e； p2：f； 計算復雜性為計算復雜性為o(m2n2)p1p2afcbed6124115812354102465443分割線分割線815 評論：評論： 最小分割法以圖論為基礎，可以作為分配負載的一種方最小分割法以圖論為基礎，可以作為分配負載的一種方法。通過對目標函數(shù)求極小值的方法進行。法。通過對目標函數(shù)求極小值的方法進行。優(yōu)點：簡明優(yōu)點：簡明缺點：計算復雜性較大，只能處理缺點：計算復雜性較大，只能處理2、3個處理機的情形個處理機的情形 不能考慮處理機負載平衡問題以及由此帶來的排隊延不能考慮處理機負載

18、平衡問題以及由此帶來的排隊延遲、存儲限制、實時（即時）要求等問題。遲、存儲限制、實時（即時）要求等問題。 0 01 1策略策略 指導思想：將任務分配概括為一個優(yōu)化問題。指導思想：將任務分配概括為一個優(yōu)化問題。 數(shù)據(jù)結構數(shù)據(jù)結構 分配矩陣分配矩陣x，處理開銷矩陣處理開銷矩陣q， 引入卷宗矩陣引入卷宗矩陣v，vij表示表示mi向向mj發(fā)送的數(shù)據(jù)卷宗發(fā)送的數(shù)據(jù)卷宗 引入距離矩陣引入距離矩陣d，dij表示處理機表示處理機pi與與pj的距離，代表的距離，代表互連狀況（交通條件），為互連狀況（交通條件），為則表示不連通，于是則表示不連通，于是dij vij就是就是兩個任務的兩個任務的itc開銷了。開銷了。

19、 目標函數(shù)目標函數(shù) t = qkixik + w vijdijxikxjh kihk j0，用隨機方法在用隨機方法在pj上選取一個任務遷移到上選取一個任務遷移到pj+1上，否則上，否則不做任何動作。重復進行，直到所有的不做任何動作。重復進行，直到所有的dj都不大于都不大于0；必要時可對合一的；必要時可對合一的任務進行分解。任務進行分解。 若若dm大于大于0，失??！，失敗！評論：評論： 算法以追求次優(yōu)解為目標，合一時采用算法以追求次優(yōu)解為目標，合一時采用“貪心貪心”策略，不一定會實策略，不一定會實現(xiàn)最佳分配；現(xiàn)最佳分配； 調整過程采用隨機遷移，有盲目性；調整過程采用隨機遷移，有盲目性； 成功的合

20、一可以減少通信開銷，成功的調整可使負載基本平衡，有成功的合一可以減少通信開銷，成功的調整可使負載基本平衡，有利于提高系統(tǒng)吞吐量；利于提高系統(tǒng)吞吐量； 合一階段計算復雜性合一階段計算復雜性o(n3)，調整階段調整階段o(m2) ，可以忍受；可以忍受； 合一結束后，任務數(shù)目可能大于處理機數(shù)，需將多余任務分配給各合一結束后，任務數(shù)目可能大于處理機數(shù)，需將多余任務分配給各處理機，甚至需要分解任務，這時尋找通信量最大的任務對工作量大；處理機，甚至需要分解任務，這時尋找通信量最大的任務對工作量大； 在特殊情況，如存在附屬任務（某個任務必須分給特定的一個或數(shù)在特殊情況，如存在附屬任務（某個任務必須分給特定的

21、一個或數(shù)個處理機），合一時以附屬任務為中心形成組合任務，先分配對處理機個處理機），合一時以附屬任務為中心形成組合任務，先分配對處理機有特殊要求的組合任務，再分配包含其他附屬任務的組合任務，最后分有特殊要求的組合任務，再分配包含其他附屬任務的組合任務，最后分配不含附屬任務的組合任務。調整階段先排除負載平衡的處理機，在輕配不含附屬任務的組合任務。調整階段先排除負載平衡的處理機，在輕載和重載處理機之間進行調整。載和重載處理機之間進行調整。 改進后的啟發(fā)式算法改進后的啟發(fā)式算法 數(shù)據(jù)結構定義數(shù)據(jù)結構定義 系統(tǒng)中有系統(tǒng)中有n個處理機，個處理機，m個計算任務（個計算任務（mn）。）。 任務間通信開銷矩陣任

22、務間通信開銷矩陣cmm： cmm = cij | 1im，1jm ，為任務為任務ti，tj之間的通信開銷之間的通信開銷 任務執(zhí)行開銷矩陣任務執(zhí)行開銷矩陣qmn： qmn = qij | 1im，1jn ，為為ti在在pj上的運行開銷上的運行開銷 任務優(yōu)先矩陣任務優(yōu)先矩陣amn： aij = 1 表示任務表示任務ti不能分配給處理機不能分配給處理機pj，否則為否則為0 任務互斥矩陣任務互斥矩陣emm： eij = 1 表示任務表示任務ti與與tj不能分配給同一臺處理機，否則為不能分配給同一臺處理機，否則為0 任務分配矩陣任務分配矩陣xmn： xij = 1 表示任務表示任務ti已經分配給處理機已

23、經分配給處理機pj ，否則為，否則為0 處理機處理機pk上的負載：上的負載： lk = w qikxik，其中常數(shù)其中常數(shù)w w用來調整執(zhí)行開銷與通信開銷的量綱用來調整執(zhí)行開銷與通信開銷的量綱 某個任務與組合任務中的任一分任務互斥，即為與該組合任務互某個任務與組合任務中的任一分任務互斥，即為與該組合任務互斥。斥。 算法算法 將附屬于同一處理機的任務合一，得到壓縮后的矩陣將附屬于同一處理機的任務合一，得到壓縮后的矩陣a和和e, ,a的行數(shù)為的行數(shù)為m，e的行列數(shù)均為的行列數(shù)均為m，記為，記為am n和和em m。同樣，。同樣，q和和c也變?yōu)橐沧優(yōu)閝m n，cm m，它們的元素值也會相應改變。，它

24、們的元素值也會相應改變。 對對cm m的每一行進行排序，查找最大通信量的任務對的每一行進行排序，查找最大通信量的任務對 對處理機按現(xiàn)有負載建棧，棧頂為負載最輕的對處理機按現(xiàn)有負載建棧，棧頂為負載最輕的p pk k。若棧非空，。若棧非空，選選p pk k，否則轉，否則轉。i=1m 若所有任務已分配完，轉若所有任務已分配完，轉，否則，若，否則，若pk有附屬任務，記該任有附屬任務，記該任務為務為t,若若pk無附屬任務，任選一個未分配任務為無附屬任務，任選一個未分配任務為t。 尋找與尋找與t由最大通信量的未分配任務由最大通信量的未分配任務tj，若加入后仍滿足：，若加入后仍滿足： 實時限制實時限制rk，

25、存儲限制，存儲限制sk； aij = 0= 0，即，即tj可以分配到可以分配到pk上；上； tj不與任何已分配到不與任何已分配到pk上的任務互斥；上的任務互斥； 將將tj分配到分配到pk上。否則選下一個與上。否則選下一個與t有最大通信量的未分配任務有最大通信量的未分配任務tj，重復，重復。若無法找到這樣的。若無法找到這樣的tj，若可分配就將，若可分配就將t分配給分配給pk。 若沒有這樣的任務若沒有這樣的任務t和和tj能分配給能分配給pk，將，將pk從棧中刪去。否則從棧中刪去。否則修改修改pk的負載，轉的負載，轉 。 檢查剩余任務，如有，設當前任務為檢查剩余任務，如有，設當前任務為ti，其優(yōu)先任

26、務為，其優(yōu)先任務為tj，若，若tj已經分配給已經分配給pk，則從，則從pk中取出中取出tj，將，將ti分配給分配給pk，并尋找可以接收，并尋找可以接收tj的的處理機。若剩余任務不能分配給任何處理機，分配失敗，退出。處理機。若剩余任務不能分配給任何處理機，分配失敗，退出。 計算處理機計算處理機pk（k=1,2,，n）的負載）的負載lk并求出平均負載并求出平均負載l，定，定義義rk = lk/l。 若若1-drk1+d ，pk為平衡；為平衡； 若若rk 1-d，pk為輕載；為輕載； 若若rk 1+d，pk為超載；為超載； 去掉分配給平衡處理機的任務，將輕載處理機上的任務合一為一去掉分配給平衡處理機

27、的任務，將輕載處理機上的任務合一為一個組合任務。以輕載、超載處理機上的任務集合為對象，轉個組合任務。以輕載、超載處理機上的任務集合為對象，轉重新建重新建棧。若此次分配未引起負載變化，算法終止。棧。若此次分配未引起負載變化，算法終止。 基于遺傳算法和模擬退火算法的任務分配算法基于遺傳算法和模擬退火算法的任務分配算法 數(shù)據(jù)結構數(shù)據(jù)結構 建立一個五元組建立一個五元組 = =（ t， ，q，c，x ） 其中其中t為任務集合；為任務集合；“ ”為為t上的優(yōu)先關系，上的優(yōu)先關系，ti tj 表示表示ti必須在必須在tj執(zhí)行之前完成；執(zhí)行之前完成；q為為mm矩陣，矩陣，qij表示任務表示任務ti在處理機在處

28、理機pj上的執(zhí)行時上的執(zhí)行時間；間；c是一個是一個mn矩陣，矩陣，cij表示任務表示任務ti與任務與任務tj的通信開銷；的通信開銷；x是一個是一個mn的任務分配矩陣，的任務分配矩陣，xij=1=1表示表示ti分配到處理機分配到處理機pj上，否則為上，否則為0 0。 設計目標函數(shù)設計目標函數(shù)cost，例如，例如 cost = (qik xik+w ckr xik xjr) 其中常數(shù)其中常數(shù)w w用來調節(jié)量綱差異用來調節(jié)量綱差異 i=1 k=1mnr=1 j=1k-1 i-1 迭代過程迭代過程 進行初始化，隨機生成一個初始任務分配集合。例如：進行初始化，隨機生成一個初始任務分配集合。例如：處理機處

29、理機任務任務p0p1p1t1t2t3t4t5t6t7110000000110000000111 描述與生成一個初始任務分配集合描述與生成一個初始任務分配集合ta。 其中，特定的任務分配方案用（其中，特定的任務分配方案用（s，r1.n）表示。其中，）表示。其中，s 是一個是一個 log2n m 的二進制串，每個的二進制串，每個 log2n 位稱為一節(jié)，自左到右的第位稱為一節(jié)，自左到右的第i節(jié)就表節(jié)就表示任務示任務ti所在的處理機號碼。上例中，所在的處理機號碼。上例中，s = 00 00 01 01 10 10 10。r是一個是一個有有n個分量的鏈表數(shù)組，每個分量的類型為個分量的鏈表數(shù)組，每個分量

30、的類型為m元整數(shù)數(shù)組，自左向右表示元整數(shù)數(shù)組，自左向右表示任務執(zhí)行的順序。假定上例中的優(yōu)先次序為任務執(zhí)行的順序。假定上例中的優(yōu)先次序為t1 t2，t4 t5，t6 t7，這樣，這樣r為：為：r0：12，r1：34，r2：567（或（或675，或，或657，因為只有，因為只有6、7有次序有次序關系）。關系）。 這樣，這樣，ta1.s = 00 00 01 01 10 10 10； ta1,r =（ 12 34 567） ta2.s = 00 00 01 01 10 10 10; ta2.r =（ 12 34 675） ta3.s = 00 00 01 01 10 10 10; ta3.r =（

31、12 34 657） 于是，可以選取若干分配方案，形成初始任務分配集合：于是，可以選取若干分配方案，形成初始任務分配集合： ta = s，r1.n 設置退火算法中的初始溫度設置退火算法中的初始溫度temp0和收斂率和收斂率 （0 1），溫度），溫度tempi+1 = tempi，逐步降低。這里，逐步降低。這里，i既代表第既代表第i次迭代，也代表遺傳次迭代，也代表遺傳算法中的地算法中的地i代個體。代個體。 一般在任務量較大的情形，一般在任務量較大的情形，temp0可以取可以取1000， temp 取為取為1， 取取0.9，效果較好。，效果較好。 進行迭代循環(huán)。對初始任務分配集合中的方案采用交叉繁

32、殖、變進行迭代循環(huán)。對初始任務分配集合中的方案采用交叉繁殖、變異等方法，形成新一代分配方案集合，不斷進行。異等方法，形成新一代分配方案集合，不斷進行。 交叉繁殖交叉繁殖 對父代的兩個分配方案中對父代的兩個分配方案中s的某些節(jié)進行替換，選取其中的優(yōu)的某些節(jié)進行替換，選取其中的優(yōu)良者（良者（cost較小）插入分配集合，形成第二代分配集合。較?。┎迦敕峙浼?，形成第二代分配集合。 例例 兩個父代方案：兩個父代方案： ta1.s = 00 00 01 01 10 10 10； ta1.r =（12 34 567） ta2.s = 01 01 01 00 10 00 10； ta2.r =（46 123

33、 57 ） 用用ta1.s中的中的1、3、6節(jié)替換節(jié)替換ta2.s中的相應節(jié)，形成新方案：中的相應節(jié)，形成新方案： ta3.s = 00 01 01 00 10 10 10； ta3.r = （ 14 23 567） 計算計算 cost = cost(ta3) cost(ta2)： 0 表示新方案優(yōu)于原方案，將表示新方案優(yōu)于原方案，將ta3插入新的分配集合；插入新的分配集合； 0表示原方案優(yōu)于新方案，計算概率值：表示原方案優(yōu)于新方案，計算概率值： prob = exp | cost/k temp | ，式中，式中k為波爾茲曼常數(shù)，為波爾茲曼常數(shù)，temp為為當前溫度；當前溫度； 由系統(tǒng)產生（由

34、系統(tǒng)產生（0，1）之間的隨機數(shù)）之間的隨機數(shù)rand，若，若probrand，將，將新方案加入分配集合，反之舍棄。新方案加入分配集合，反之舍棄。 變異變異 對某些方案作變異處理，形成新方案。如對對某些方案作變異處理，形成新方案。如對ta.s某些節(jié)求反、某些節(jié)求反、互換處理任務等。變異不會造成個體數(shù)量的變化。每次變異后，對一互換處理任務等。變異不會造成個體數(shù)量的變化。每次變異后，對一個原方案只保留一種有效的變異方案。個原方案只保留一種有效的變異方案。 通過這種方法，可以得到比較理想的分配方案。通過這種方法，可以得到比較理想的分配方案。 基于有向任務圖的調度策略基于有向任務圖的調度策略 假定：已知

35、每個任務的執(zhí)行時間，任務之間的時序假定：已知每個任務的執(zhí)行時間，任務之間的時序關系、任務間的通信量、可使用計算機的數(shù)目；關系、任務間的通信量、可使用計算機的數(shù)目；分布式系分布式系統(tǒng)中有統(tǒng)一的時鐘、結點同構（從而保證每個任務在不同統(tǒng)中有統(tǒng)一的時鐘、結點同構（從而保證每個任務在不同計算機上的處理時間相同、通信開銷固定）計算機上的處理時間相同、通信開銷固定）；計算任務除；計算任務除通信以外的資源都可以從本機上獲得。通信以外的資源都可以從本機上獲得。 步驟步驟 生成非循環(huán)的任務有向圖生成非循環(huán)的任務有向圖 g = v，e，e，c t14t23t37t492522 上圖中，上圖中， 結點集合結點集合 v

36、 = t1，t2，t3，t4 有向邊集合有向邊集合 e = (t1,t2)，(t1,t3)，(t2,t4)，(t3,t4) 運行開銷集合運行開銷集合 e = 4，3，7，9 通信開銷集合通信開銷集合 c = 2，5，2，2 任務復制任務復制 使任務在兩個以上的計算機上有執(zhí)行副本。使任務在兩個以上的計算機上有執(zhí)行副本。t13t27t3276 上圖中，三個任務在兩個計算機上有三種分配方案（未復制）：上圖中，三個任務在兩個計算機上有三種分配方案（未復制）： t1t1t1t2t2t2t3t3t367 第一種情況：總時間第一種情況：總時間11 第二種情況：總時間第二種情況：總時間17 第三種情況：總時間

37、第三種情況：總時間12（在一個計算機上）（在一個計算機上） 如果進行任務復制：如果進行任務復制：t1t1t3t2總時間：總時間：10任務復制將帶來好處任務復制將帶來好處 計算最早開始時間計算最早開始時間 貪心函數(shù)貪心函數(shù)f：假定假定c是包含結點是包含結點v以及它的父結點以及它的父結點 1， 2， 3， k 的聚集。定義的聚集。定義 f ( 1， 2， 3， k )為全部完成為全部完成 1， 2， 3， k 的最早可能結束時間。的最早可能結束時間。定義定義s ( v )為結點為結點 v 的開始執(zhí)行時間。顯然：的開始執(zhí)行時間。顯然： s ( v ) f ( 1， 2， 3， k ) = f ( c

38、 v ) 考慮：考慮：t14t22t32t44貪心函數(shù)貪心函數(shù) f ( c t4 ) = 0 + 4 + 2 = 6只有只有t1，t3，t4分配在同一個計算機分配在同一個計算機上才能達到：上才能達到：868 最大弦值函數(shù)最大弦值函數(shù)maxg：非循環(huán)優(yōu)先圖中的邊非循環(huán)優(yōu)先圖中的邊( u,w ) e，定義弦值函數(shù)定義弦值函數(shù) g ( u,w ) = s ( u ) + e ( u ) + c ( u,w )； 這里這里 s (u) 是結點是結點u u的最早開始時間，的最早開始時間，e(u)e(u)是是 u的運行時間，的運行時間，c ( u,w )是是u，w的通信開銷。的通信開銷。 最大弦值函數(shù)最大

39、弦值函數(shù)macg(c)定義為由不屬于定義為由不屬于c的節(jié)點到的節(jié)點到c中中節(jié)點的最大弦值。節(jié)點的最大弦值。 t14t22t32t4451令令 c = t3，t4，maxg（c）= 9 在一個給定的分配方案里，節(jié)點在一個給定的分配方案里，節(jié)點v的最早開始時間的最早開始時間 sv f（cv）；）； 在上例中，在上例中，t4的最早開始時間為的最早開始時間為11。 計算聚集的算法計算聚集的算法 令結點集合令結點集合g，剛開始時，所有結點均未作標記。剛開始時，所有結點均未作標記。 取取g中未標記結點中未標記結點v； 若若v未根結點，作標記后轉未根結點，作標記后轉 ； 令令c為空，為空，v加入加入c，計算

40、計算 s = maxg ( c )； 選擇具有最大弦值的選擇具有最大弦值的( u,w )，其中其中u c，且且u為第一次被選擇，為第一次被選擇， w c，c = c + u ，若無轉若無轉 ； 若若maxg 、f ( c-v )均不大于均不大于s， 則則s = max( maxg(c) , f( c v)），），否則否則c = c u ，轉轉 ； c = c u 輸出輸出c和和v，對對v做標記，若做標記，若g中為全部標記轉中為全部標記轉 ，否則結束。，否則結束。 評述：評述： 總思路：對任一非根結點，計算其最大聚集弦值，找出滿總思路：對任一非根結點，計算其最大聚集弦值，找出滿足該弦值得一對結點

41、。嘗試將聚集外的結點加入該聚集，足該弦值得一對結點。嘗試將聚集外的結點加入該聚集，看能否降低其最大弦值，若能則繼續(xù)，否則去掉加入的結看能否降低其最大弦值，若能則繼續(xù)，否則去掉加入的結點，輸出聚集。點，輸出聚集。例例t110t35t29t45t55t661412643起始，起始，c中有中有t6，這時，這時maxg(c) = 41；第一次循環(huán)結束，第一次循環(huán)結束，c = t5,t6 , maxg(c) = 33；第二次循環(huán)開始，第二次循環(huán)開始，u = t4，取，取u = t4， 則則f ( c t4 ) = 27，送入，送入s；加入加入t4，則，則maxg(c) 21 該算法對每一個非根結點都會輸

42、出一個聚集，若某一聚該算法對每一個非根結點都會輸出一個聚集，若某一聚集為另一個聚集的子集，則刪去，最后得到若干相互沒有集為另一個聚集的子集，則刪去，最后得到若干相互沒有包含的狙擊。若聚集的數(shù)目不大于計算機的數(shù)目，為每一包含的狙擊。若聚集的數(shù)目不大于計算機的數(shù)目，為每一個聚集分配一個計算機，否則根據(jù)情況再進行調整。個聚集分配一個計算機，否則根據(jù)情況再進行調整。 在上例中，如果有兩臺計算機，那么分配方案：在上例中，如果有兩臺計算機，那么分配方案： t2t4t5t6t1t3若有三臺計算機，分配方案改為：若有三臺計算機，分配方案改為：t2t4t1t3t5t63. 調度問題調度問題 正常情況下，分布式系

43、統(tǒng)中的各結點機有自己的本地調正常情況下，分布式系統(tǒng)中的各結點機有自己的本地調度程序，負責調度本機上的任務進程。度程序，負責調度本機上的任務進程。 問題：問題： 在需要進行遠程通信時，各自計算機上的獨立調度可能在需要進行遠程通信時，各自計算機上的獨立調度可能會影響系統(tǒng)的性能。會影響系統(tǒng)的性能。 例例 兩個節(jié)點的系統(tǒng)，每個結點各有兩個進程，結點兩個節(jié)點的系統(tǒng)，每個結點各有兩個進程，結點1有進程有進程a，b：結點：結點2有進程有進程c，d。兩個結點各自采用分時。兩個結點各自采用分時方式調度方式調度，時間片為方式調度方式調度，時間片為100ms。 時間片時間片處處 理理 機機0 1012345acbd

44、cacabddb 在時間片在時間片0 0，a a啟動后立即向啟動后立即向d d發(fā)出遠發(fā)出遠程調用，自己等待結果；但處理機程調用，自己等待結果；但處理機1 1上上c c正在運行。到第二個時間片，正在運行。到第二個時間片，d d立即立即處理遠程調用并返回結果，但此時處理遠程調用并返回結果，但此時a a已已經不在運行狀態(tài)（經不在運行狀態(tài)（b b在運行）在運行） 由于通信與運行不同步，將導致處由于通信與運行不同步，將導致處理機無謂等待。理機無謂等待。 解決辦法解決辦法1： 處理機采用時間片輪轉方法時，將進程按通信關系編組，盡可能處理機采用時間片輪轉方法時，將進程按通信關系編組，盡可能將處于同一通信組的

45、進程安排在相同時間片里運行。將處于同一通信組的進程安排在相同時間片里運行。 問題：遠程調用發(fā)生的時機是隨機的，很難做到準確問題：遠程調用發(fā)生的時機是隨機的，很難做到準確。 解決辦法解決辦法2： 處理機調度采用分時和可搶占方法相結合。當一個遠程調用到來時，處理機調度采用分時和可搶占方法相結合。當一個遠程調用到來時，被調用進程所在的處理機將當前運行進程掛起，調度相應進程運行；被調用進程所在的處理機將當前運行進程掛起，調度相應進程運行；調用結束后再恢復原進程運行完剩余的時間片。處理遠程調用不占進調用結束后再恢復原進程運行完剩余的時間片。處理遠程調用不占進程的時間片。程的時間片。 好處：通信量較大的進

46、程可以在運行時間上有所優(yōu)待，以保證與其好處：通信量較大的進程可以在運行時間上有所優(yōu)待，以保證與其通信的它機進程正常運行。通信的它機進程正常運行。 缺點：進程間切換可能過于頻繁，影響處理機的有效利用率。缺點：進程間切換可能過于頻繁，影響處理機的有效利用率。3 3 系統(tǒng)容錯系統(tǒng)容錯1.1.需要討論的問題需要討論的問題 設備故障的兩種情況設備故障的兩種情況 fail and stop byzantine 容錯的通常做法容錯的通常做法 冗余技術，包括信息冗余、時間冗余和物理設備的冗冗余技術，包括信息冗余、時間冗余和物理設備的冗余。余。 信息冗余：增加效驗碼、鏡像存放、多副本等信息冗余：增加效驗碼、鏡像

47、存放、多副本等 時間冗余：必要的重復執(zhí)行，如原子事務技術等時間冗余：必要的重復執(zhí)行，如原子事務技術等 物理冗余：增加設備，包括主動備份、被動備份物理冗余：增加設備，包括主動備份、被動備份 2. 主動備份主動備份 對對fail and stop類型故障比較有效類型故障比較有效 容錯級別：容錯級別： 系統(tǒng)稱為系統(tǒng)稱為k級容錯，是指級容錯，是指k個部件出現(xiàn)故障，系統(tǒng)仍能個部件出現(xiàn)故障，系統(tǒng)仍能正常工作，需要配備正常工作，需要配備k+1套設施。套設施。 對服務器，設置對服務器，設置k+1個，要求每個個，要求每個clientclient的請求按照的請求按照相同的（服務器）次序執(zhí)行并應答，稱為原子廣播。但

48、在相同的（服務器）次序執(zhí)行并應答，稱為原子廣播。但在網絡環(huán)境很難實現(xiàn)。網絡環(huán)境很難實現(xiàn)。 方法方法1 1：對遠程請求實行全局編號，需要一臺編號服務器實現(xiàn)編號：對遠程請求實行全局編號，需要一臺編號服務器實現(xiàn)編號與分發(fā)，集中式弊病。與分發(fā)，集中式弊病。 方法方法2 2：使用邏輯時鐘，請求加蓋時間郵戳。但有麻煩：如何知道：使用邏輯時鐘，請求加蓋時間郵戳。但有麻煩：如何知道 還有沒有更早的請求正在路上？還有沒有更早的請求正在路上？ 2. 被動備份被動備份 指定一臺設備為主設備，處理一切有關的事務，其它同指定一臺設備為主設備，處理一切有關的事務，其它同類設備為備份設備。只有當主設備故障時，才由備份機接類

49、設備為備份設備。只有當主設備故障時，才由備份機接替工作。替工作。 正常情況下，運行策略簡單：消息秩序相主服務器發(fā)送，正常情況下，運行策略簡單：消息秩序相主服務器發(fā)送，不必向整個服務器群發(fā)送，次序問題基本上不存在。而且不必向整個服務器群發(fā)送，次序問題基本上不存在。而且備份機也比較節(jié)省。備份機也比較節(jié)省。 clientprimaryserverbackupserver 發(fā)送請求發(fā)送請求 工作，完成請求任務工作，完成請求任務 發(fā)送更新要求發(fā)送更新要求 工作，完成更新工作，完成更新 確認，完成更新確認，完成更新 返回結果返回結果 在執(zhí)行一個在執(zhí)行一個rpc過程中，服務器故障時刻分析：過程中，服務器故障時刻分析： 在在以前，不會有影響，以前，不會有影響，client發(fā)現(xiàn)響應超時重新請求，再三請求未發(fā)現(xiàn)響應超時重新請求，再三請求未果，確認服務器故障，轉向備份服務器；果，確認服務器故障，轉向備份服務器； 在在、階段，同上面情況，備份機接替工作，完成服務；階段，同上面情況，備份機接替工作，完成服務； 在在以后，以后，完成前，備份機接替工作。完成前，備份機接替工作。 系統(tǒng)運行過程中，備份機與主機不斷通信，詢問是否正常。系統(tǒng)運行過程中，備份機與主機不斷通信，詢問是否正常。 改進方法：主機與備份機共享磁盤，采用磁盤鏡像或交改進方法：主機與備份機共享磁盤，采用磁盤鏡像或交換式磁盤兩種方法。