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

1、 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 線程調(diào)度管理的方式線程調(diào)度管理的方式 核心管理模式：核心管理模式： 對(duì)每一個(gè)進(jìn)程。核心為其建立一個(gè)線程調(diào)度表。同一個(gè)進(jìn)程的線程可對(duì)每一個(gè)進(jìn)程。核心為其建立一個(gè)線程調(diào)度表。同一個(gè)進(jìn)程的線程可以并行。以并行。線線程程線線程程線線程程線線程程核核 心心第1頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 進(jìn)程管理模式：進(jìn)程管理模式： 在用戶區(qū)內(nèi)進(jìn)程創(chuàng)建一個(gè)虛擬處理器（又稱為進(jìn)程的運(yùn)行系在用戶區(qū)內(nèi)進(jìn)程創(chuàng)建一個(gè)虛擬處理器（又稱為進(jìn)程的運(yùn)行系統(tǒng)），對(duì)應(yīng)一個(gè)物理統(tǒng)），對(duì)應(yīng)一個(gè)物理CPU。線程可以在阻塞時(shí)調(diào)用運(yùn)行系統(tǒng)保留現(xiàn)場(chǎng)和線程可以在阻塞時(shí)調(diào)

2、用運(yùn)行系統(tǒng)保留現(xiàn)場(chǎng)和掛起，運(yùn)行系統(tǒng)負(fù)責(zé)調(diào)度線程運(yùn)行。這樣進(jìn)程可以設(shè)定自己的調(diào)度策略，掛起，運(yùn)行系統(tǒng)負(fù)責(zé)調(diào)度線程運(yùn)行。這樣進(jìn)程可以設(shè)定自己的調(diào)度策略，但效率較低。但效率較低。 現(xiàn)代分布式系統(tǒng)中，線程是獨(dú)立的運(yùn)行單位和調(diào)度單位?，F(xiàn)代分布式系統(tǒng)中，線程是獨(dú)立的運(yùn)行單位和調(diào)度單位。2. 線程組織模型線程組織模型 線程工作的組織方式分為三種：派遣工作模型（在進(jìn)程中設(shè)立派遣進(jìn)程線程工作的組織方式分為三種：派遣工作模型（在進(jìn)程中設(shè)立派遣進(jìn)程負(fù)責(zé)選擇工作線程運(yùn)行）、小組模型（線程平等工作）和管道模型（流水負(fù)責(zé)選擇工作線程運(yùn)行）、小組模型（線程平等工作）和管道模型（流水線方式）。線方式）。 第2頁/共56頁 分

3、布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 派遣模型派遣模型 派遣線程派遣線程工作線程工作線程郵郵 箱箱核核 心心共享cache進(jìn)進(jìn) 程程工作請(qǐng)求工作請(qǐng)求工作請(qǐng)求工作請(qǐng)求第3頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 小組模型小組模型 郵郵 箱箱核核 心心工作請(qǐng)求工作請(qǐng)求進(jìn)進(jìn) 程程共享cache工作請(qǐng)求工作請(qǐng)求第4頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 管道模型管道模型 郵郵 箱箱工作請(qǐng)求工作請(qǐng)求核核 心心進(jìn)進(jìn) 程程共享cache工作請(qǐng)求工作請(qǐng)求第5頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 動(dòng)態(tài)模型動(dòng)態(tài)模型 進(jìn)程初啟時(shí)只有一

4、個(gè)線程，稱為服務(wù)線程，向核進(jìn)程初啟時(shí)只有一個(gè)線程，稱為服務(wù)線程，向核心輸入進(jìn)程的接口。心輸入進(jìn)程的接口。 核心準(zhǔn)備調(diào)用數(shù)據(jù)借口，例如數(shù)據(jù)棧，供服務(wù)線核心準(zhǔn)備調(diào)用數(shù)據(jù)借口，例如數(shù)據(jù)棧，供服務(wù)線程和客戶線成共享。程和客戶線成共享。 客戶線程初啟后，從核心輸入這些接口?？蛻艟€程初啟后，從核心輸入這些接口。 客戶線程調(diào)用過程時(shí)，將參數(shù)入棧，將過程名存客戶線程調(diào)用過程時(shí)，將參數(shù)入棧，將過程名存入指定寄存器，通過入指定寄存器，通過trap進(jìn)入核心。進(jìn)入核心。 核心查看知道是本地調(diào)用，將客戶線程內(nèi)存映射核心查看知道是本地調(diào)用，將客戶線程內(nèi)存映射到服務(wù)線程地址空間，啟動(dòng)服務(wù)進(jìn)程，執(zhí)行過程調(diào)用。到服務(wù)線程地址空

5、間，啟動(dòng)服務(wù)進(jìn)程，執(zhí)行過程調(diào)用。 遠(yuǎn)程調(diào)用到來時(shí)，核心創(chuàng)建一個(gè)線程，將遠(yuǎn)程請(qǐng)遠(yuǎn)程調(diào)用到來時(shí)，核心創(chuàng)建一個(gè)線程，將遠(yuǎn)程請(qǐng)求消息映射到它的地址空間，線程相應(yīng)服務(wù)請(qǐng)求，執(zhí)行求消息映射到它的地址空間，線程相應(yīng)服務(wù)請(qǐng)求，執(zhí)行過程調(diào)用，結(jié)束后自動(dòng)消亡。過程調(diào)用，結(jié)束后自動(dòng)消亡。第6頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理2 2 負(fù)載平衡與系統(tǒng)模型負(fù)載平衡與系統(tǒng)模型工作站模型工作站模型 屬于對(duì)稱型模型，各結(jié)點(diǎn)是平等的。屬于對(duì)稱型模型，各結(jié)點(diǎn)是平等的。 負(fù)載平衡的要點(diǎn)之一是如何發(fā)負(fù)載平衡的要點(diǎn)之一是如何發(fā)現(xiàn)空載結(jié)點(diǎn)（潛在的計(jì)算服務(wù)器）。涉及三個(gè)問題：現(xiàn)空載結(jié)點(diǎn)（潛在的計(jì)算服務(wù)器）。涉及三

6、個(gè)問題： 如何發(fā)現(xiàn)空載結(jié)點(diǎn)如何發(fā)現(xiàn)空載結(jié)點(diǎn) 遠(yuǎn)程進(jìn)程如何透明地運(yùn)行遠(yuǎn)程進(jìn)程如何透明地運(yùn)行1.1. 當(dāng)本地進(jìn)程需要運(yùn)行時(shí)，如何處理當(dāng)本地進(jìn)程需要運(yùn)行時(shí)，如何處理第7頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 服務(wù)器驅(qū)動(dòng)服務(wù)器驅(qū)動(dòng) 每個(gè)結(jié)點(diǎn)裝備空載監(jiān)測(cè)程序，監(jiān)測(cè)自身。每個(gè)結(jié)點(diǎn)裝備空載監(jiān)測(cè)程序，監(jiān)測(cè)自身。 設(shè)管理者，維護(hù)空載注冊(cè)表，記錄空載結(jié)點(diǎn)地址。設(shè)管理者，維護(hù)空載注冊(cè)表，記錄空載結(jié)點(diǎn)地址。 每個(gè)結(jié)點(diǎn)發(fā)現(xiàn)自己空載時(shí)，發(fā)消息給管理者，后者每個(gè)結(jié)點(diǎn)發(fā)現(xiàn)自己空載時(shí)，發(fā)消息給管理者，后者將其地址記入空載注冊(cè)表。將其地址記入空載注冊(cè)表。 A結(jié)點(diǎn)需要分散計(jì)算負(fù)載，發(fā)遠(yuǎn)程命令詢問管理者，結(jié)點(diǎn)

7、需要分散計(jì)算負(fù)載，發(fā)遠(yuǎn)程命令詢問管理者，后者給它發(fā)送空載結(jié)點(diǎn)地址后者給它發(fā)送空載結(jié)點(diǎn)地址B，A結(jié)點(diǎn)向結(jié)點(diǎn)向B發(fā)送遠(yuǎn)程任發(fā)送遠(yuǎn)程任務(wù)，務(wù)，B執(zhí)行遠(yuǎn)程任務(wù)，負(fù)載增加，發(fā)消息要求管理者刪執(zhí)行遠(yuǎn)程任務(wù)，負(fù)載增加，發(fā)消息要求管理者刪去自己。去自己。 為避免幾個(gè)結(jié)點(diǎn)同時(shí)發(fā)現(xiàn)某空載結(jié)點(diǎn)引起沖突，可引為避免幾個(gè)結(jié)點(diǎn)同時(shí)發(fā)現(xiàn)某空載結(jié)點(diǎn)引起沖突，可引入二次確認(rèn)：請(qǐng)求者向空載結(jié)點(diǎn)發(fā)送請(qǐng)求確認(rèn)消息，空入二次確認(rèn)：請(qǐng)求者向空載結(jié)點(diǎn)發(fā)送請(qǐng)求確認(rèn)消息，空載結(jié)點(diǎn)選擇其中一個(gè)結(jié)點(diǎn)為雇主，要求管理者從空載表載結(jié)點(diǎn)選擇其中一個(gè)結(jié)點(diǎn)為雇主，要求管理者從空載表中刪去自己，向雇主發(fā)回確認(rèn)消息。未接到確認(rèn)的結(jié)點(diǎn)中刪去自己，向雇主發(fā)回確認(rèn)消

8、息。未接到確認(rèn)的結(jié)點(diǎn)只好再次向管理者詢問。只好再次向管理者詢問。第8頁/共56頁管理者管理者注冊(cè)程序注冊(cè)程序空載注空載注冊(cè)表冊(cè)表請(qǐng)求者請(qǐng)求者空載結(jié)點(diǎn)空載結(jié)點(diǎn)遠(yuǎn)程過程遠(yuǎn)程過程遠(yuǎn)程過程遠(yuǎn)程過程1. 空載注冊(cè)空載注冊(cè)2. 請(qǐng)求空載結(jié)點(diǎn)請(qǐng)求空載結(jié)點(diǎn)3. 回復(fù)空載結(jié)點(diǎn)回復(fù)空載結(jié)點(diǎn)4. 要求確認(rèn)要求確認(rèn)5. 注銷空載注銷空載6. 確認(rèn)確認(rèn)7. 設(shè)置運(yùn)行環(huán)境設(shè)置運(yùn)行環(huán)境8. 啟動(dòng)遠(yuǎn)程進(jìn)程啟動(dòng)遠(yuǎn)程進(jìn)程9. 進(jìn)程運(yùn)行進(jìn)程運(yùn)行10. 進(jìn)程結(jié)束進(jìn)程結(jié)束11. 返回結(jié)果返回結(jié)果第9頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 客戶驅(qū)動(dòng)客戶驅(qū)動(dòng) 結(jié)點(diǎn)需要分散負(fù)載時(shí)，廣播請(qǐng)求，指明具體要求。結(jié)點(diǎn)需要分散

9、負(fù)載時(shí)，廣播請(qǐng)求，指明具體要求。 其他結(jié)點(diǎn)收到后，根據(jù)情況自行判斷，同意者回其他結(jié)點(diǎn)收到后，根據(jù)情況自行判斷，同意者回復(fù)。復(fù)。 收到所有回復(fù)后，選取負(fù)載最小者，分散計(jì)算負(fù)收到所有回復(fù)后，選取負(fù)載最小者，分散計(jì)算負(fù)載。載。請(qǐng)求者請(qǐng)求者其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)其他結(jié)點(diǎn)11112341廣播分散負(fù)載請(qǐng)求廣播分散負(fù)載請(qǐng)求234應(yīng)答：負(fù)載空應(yīng)答：負(fù)載空發(fā)送運(yùn)行環(huán)境發(fā)送運(yùn)行環(huán)境第10頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 分散負(fù)載注意問題分散負(fù)載注意問題 遠(yuǎn)程進(jìn)程的運(yùn)行環(huán)境必須與本地環(huán)境一樣遠(yuǎn)程進(jìn)程的運(yùn)行環(huán)境必須與本地環(huán)境一樣 遠(yuǎn)程進(jìn)程運(yùn)行中的某些系統(tǒng)

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

11、遠(yuǎn)程先給警告，留一段善后處理時(shí)間，然后殺死遠(yuǎn)程進(jìn)程進(jìn)程 第11頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 注意：遠(yuǎn)程進(jìn)程執(zhí)行完成以后，接點(diǎn)必須恢復(fù)到空載時(shí)的狀況。注意：遠(yuǎn)程進(jìn)程執(zhí)行完成以后，接點(diǎn)必須恢復(fù)到空載時(shí)的狀況。 包括：包括： 清除所有遠(yuǎn)程進(jìn)程及其子進(jìn)程清除所有遠(yuǎn)程進(jìn)程及其子進(jìn)程 清除這期間的郵箱內(nèi)容、網(wǎng)絡(luò)連接以及其它系統(tǒng)級(jí)數(shù)據(jù)清除這期間的郵箱內(nèi)容、網(wǎng)絡(luò)連接以及其它系統(tǒng)級(jí)數(shù)據(jù) 清除這期間的臨時(shí)文件清除這期間的臨時(shí)文件 清理清理Cache 做好以后可能到來的與遠(yuǎn)程進(jìn)程有關(guān)的消息的拒絕預(yù)防工作做好以后可能到來的與遠(yuǎn)程進(jìn)程有關(guān)的消息的拒絕預(yù)防工作第12頁/共56頁 分布式系

12、統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 處理器池模型處理器池模型 單服務(wù)器基本排隊(duì)模型單服務(wù)器基本排隊(duì)模型 令用戶產(chǎn)生請(qǐng)求令用戶產(chǎn)生請(qǐng)求 /秒，處理機(jī)能處理請(qǐng)求秒，處理機(jī)能處理請(qǐng)求 /秒，平均周轉(zhuǎn)時(shí)間秒，平均周轉(zhuǎn)時(shí)間T 1/( - )如果服務(wù)器處理能力加大，有如果服務(wù)器處理能力加大，有n個(gè)個(gè)CPU，處理能力將為處理能力將為n ，而請(qǐng)求，而請(qǐng)求率同步擴(kuò)大為率同步擴(kuò)大為n ，平均周轉(zhuǎn)時(shí)間將為，平均周轉(zhuǎn)時(shí)間將為1/(n -n ) = T/n 原因：減少了原因：減少了CPU的空閑率的空閑率 排隊(duì)論的結(jié)論是反對(duì)分布式計(jì)算的重要論據(jù)，但分布式的潛在好處排隊(duì)論的結(jié)論是反對(duì)分布式計(jì)算的重要論據(jù)，但分布式的潛

13、在好處（代價(jià)、靈活、方便、堅(jiān)固（代價(jià)、靈活、方便、堅(jiān)固）也是不可替代的。）也是不可替代的。M1M2M3M4M5S用用 戶戶用用 戶戶用用 戶戶第13頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 分布式系統(tǒng)任務(wù)分配示意分布式系統(tǒng)任務(wù)分配示意 假定：所有機(jī)器兼容，全連通。假定：所有機(jī)器兼容，全連通。 優(yōu)化目標(biāo)：平均相應(yīng)時(shí)間最小化，響應(yīng)率最小化優(yōu)化目標(biāo)：平均相應(yīng)時(shí)間最小化，響應(yīng)率最小化 響應(yīng)率響應(yīng)率 = 進(jìn)程實(shí)際運(yùn)行時(shí)間進(jìn)程實(shí)際運(yùn)行時(shí)間/在無負(fù)載標(biāo)準(zhǔn)在無負(fù)載標(biāo)準(zhǔn)CPU上的運(yùn)行上的運(yùn)行時(shí)間時(shí)間 實(shí)際運(yùn)行時(shí)間包括排隊(duì)、調(diào)度、通信、計(jì)算的花費(fèi)的實(shí)際運(yùn)行時(shí)間包括排隊(duì)、調(diào)度、通信、計(jì)算的花費(fèi)

14、的時(shí)間時(shí)間 任務(wù)類型：可遷移任務(wù)，不可遷移任務(wù)任務(wù)類型：可遷移任務(wù)，不可遷移任務(wù) 考慮：考慮： 任務(wù)間的通信開銷（任務(wù)間的通信開銷（ITC）問題問題 m1m2m3m4m5SP1P2Pn第14頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 基于圖論的任務(wù)分配策略基于圖論的任務(wù)分配策略 通信圖通信圖 圖中：圓圈表示任務(wù)，旁邊的數(shù)字表示計(jì)算工作量；連線表示有通信，連線的權(quán)圖中：圓圈表示任務(wù)，旁邊的數(shù)字表示計(jì)算工作量；連線表示有通信，連線的權(quán)（可以是（可以是 ，顯然兩個(gè)任務(wù)不能異地計(jì)算），顯然兩個(gè)任務(wù)不能異地計(jì)算）表示開銷。表示開銷。 假定同一個(gè)結(jié)點(diǎn)上的兩個(gè)任務(wù)的通信量為零。任務(wù)優(yōu)化的

15、目標(biāo)是處理開銷和假定同一個(gè)結(jié)點(diǎn)上的兩個(gè)任務(wù)的通信量為零。任務(wù)優(yōu)化的目標(biāo)是處理開銷和ITC之之和最小。和最小。ABCD512 863639第15頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義 分配矩陣分配矩陣 X 1 若任務(wù)若任務(wù)mi分配給處理機(jī)分配給處理機(jī)Pk xik = 0 若任務(wù)若任務(wù)mi不在處理機(jī)不在處理機(jī)Pk上上 處理開銷矩陣處理開銷矩陣Q qik表示任務(wù)表示任務(wù)mi在處理機(jī)在處理機(jī)Pk上的處理開銷，若為上的處理開銷，若為 ，表示表示mi不能在不能在Pk上運(yùn)行上運(yùn)行 ITC開銷矩陣開銷矩陣C cij表示任務(wù)表示任務(wù)mi和和mj之間的之間的ITC

16、開銷，若為開銷，若為0，表示，表示兩個(gè)任務(wù)在同一處理機(jī)上兩個(gè)任務(wù)在同一處理機(jī)上 于是，于是，ITC總開銷總開銷T = qkixik + cijxikxjhkihkji第16頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 其中，第一項(xiàng)是每個(gè)任務(wù)在其分配的處理機(jī)上的運(yùn)行開銷，第二項(xiàng)代表不同處理其中，第一項(xiàng)是每個(gè)任務(wù)在其分配的處理機(jī)上的運(yùn)行開銷，第二項(xiàng)代表不同處理機(jī)上任務(wù)間的機(jī)上任務(wù)間的ITCITC開銷。開銷。 以上圖為例，任務(wù)以上圖為例，任務(wù)C和和D之間通信量為無窮大，顯然應(yīng)該分配在一個(gè)結(jié)點(diǎn)上。如有之間通信量為無窮大，顯然應(yīng)該分配在一個(gè)結(jié)點(diǎn)上。如有兩個(gè)結(jié)點(diǎn)，那么分配將是兩個(gè)結(jié)點(diǎn)，那

17、么分配將是 ITC ITC開銷：開銷： A B C D 處理開銷：處理開銷： A B C D A 0 0 8 6 0 8 6 處理機(jī)處理機(jī)1 3 9 6 3 1 3 9 6 3 B 0 0 12 0 12 0 處理機(jī)處理機(jī)2 3 9 6 3 2 3 9 6 3 C 8 12 0 0 0 D 6 0 0 0 A，BC，D第17頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 顯然，優(yōu)化的方向是力求使得目標(biāo)函數(shù)顯然，優(yōu)化的方向是力求使得目標(biāo)函數(shù)X最小。最小。 例：例： 一張完全圖一張完全圖利用最小分割算法得到分配結(jié)果為利用最小分割算法得到分配結(jié)果為 P1：A，B，C，D，E； P2：

18、F； 計(jì)算復(fù)雜性為計(jì)算復(fù)雜性為O(m2n2)P1P2AFCBED6124115812354102465443分割線分割線815第18頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 評(píng)論：評(píng)論： 最小分割法以圖論為基礎(chǔ)，可以作為分配負(fù)載的一種方法。通過對(duì)目標(biāo)最小分割法以圖論為基礎(chǔ)，可以作為分配負(fù)載的一種方法。通過對(duì)目標(biāo)函數(shù)求極小值的方法進(jìn)行。函數(shù)求極小值的方法進(jìn)行。優(yōu)點(diǎn)：簡明優(yōu)點(diǎn)：簡明缺點(diǎn)：計(jì)算復(fù)雜性較大，只能處理缺點(diǎn)：計(jì)算復(fù)雜性較大，只能處理2、3個(gè)處理機(jī)的情形個(gè)處理機(jī)的情形 不能考慮處理機(jī)負(fù)載平衡問題以及由此帶來的排隊(duì)延遲、存儲(chǔ)限制、不能考慮處理機(jī)負(fù)載平衡問題以及由此帶來的排

19、隊(duì)延遲、存儲(chǔ)限制、實(shí)時(shí)（即時(shí)）要求等問題。實(shí)時(shí)（即時(shí)）要求等問題。第19頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 0 01 1策略策略 指導(dǎo)思想：將任務(wù)分配概括為一個(gè)優(yōu)化問題。指導(dǎo)思想：將任務(wù)分配概括為一個(gè)優(yōu)化問題。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 分配矩陣分配矩陣X，處理開銷矩陣處理開銷矩陣Q， 引入卷宗矩陣引入卷宗矩陣V，vij表示表示mi向向mj發(fā)送的數(shù)據(jù)卷宗發(fā)送的數(shù)據(jù)卷宗 引入距離矩陣引入距離矩陣D，dij表示處理機(jī)表示處理機(jī)Pi與與Pj的距離，的距離，代表互連狀況（交通條件），為代表互連狀況（交通條件），為則表示不連通，于是則表示不連通，于是dij vij就是兩個(gè)任務(wù)的就是兩

20、個(gè)任務(wù)的ITC開銷了。開銷了。 目標(biāo)函數(shù)目標(biāo)函數(shù) T = qkixik + w vijdijxikxjh kihk j0，用隨機(jī)方法在用隨機(jī)方法在Pj上選取一個(gè)任務(wù)遷移到上選取一個(gè)任務(wù)遷移到Pj+1上，否則不做任何動(dòng)作。上，否則不做任何動(dòng)作。重復(fù)進(jìn)行，直到所有的重復(fù)進(jìn)行，直到所有的Dj都不大于都不大于0；必要時(shí)可對(duì)合一的任務(wù)進(jìn)行分解。；必要時(shí)可對(duì)合一的任務(wù)進(jìn)行分解。 若若Dm大于大于0，失??！，失?。〉?4頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理評(píng)論：評(píng)論： 算法以追求次優(yōu)解為目標(biāo)，合一時(shí)采用算法以追求次優(yōu)解為目標(biāo)，合一時(shí)采用“貪心貪心”策略，不一定策略，不一定會(huì)實(shí)現(xiàn)最佳

21、分配；會(huì)實(shí)現(xiàn)最佳分配； 調(diào)整過程采用隨機(jī)遷移，有盲目性；調(diào)整過程采用隨機(jī)遷移，有盲目性； 成功的合一可以減少通信開銷，成功的調(diào)整可使負(fù)載基本平衡，成功的合一可以減少通信開銷，成功的調(diào)整可使負(fù)載基本平衡，有利于提高系統(tǒng)吞吐量；有利于提高系統(tǒng)吞吐量； 合一階段計(jì)算復(fù)雜性合一階段計(jì)算復(fù)雜性O(shè)(n3)，調(diào)整階段調(diào)整階段O(m2) ，可以忍受；可以忍受； 合一結(jié)束后，任務(wù)數(shù)目可能大于處理機(jī)數(shù)，需將多余任務(wù)分配合一結(jié)束后，任務(wù)數(shù)目可能大于處理機(jī)數(shù)，需將多余任務(wù)分配給各處理機(jī)，甚至需要分解任務(wù)，這時(shí)尋找通信量最大的任務(wù)對(duì)工給各處理機(jī)，甚至需要分解任務(wù)，這時(shí)尋找通信量最大的任務(wù)對(duì)工作量大；作量大； 在特殊情況

22、，如存在附屬任務(wù)（某個(gè)任務(wù)必須分給特定的一個(gè)在特殊情況，如存在附屬任務(wù)（某個(gè)任務(wù)必須分給特定的一個(gè)或數(shù)或數(shù)個(gè)處理機(jī)），合一時(shí)以附屬任務(wù)為中心形成組合任務(wù)，先分配對(duì)處個(gè)處理機(jī)），合一時(shí)以附屬任務(wù)為中心形成組合任務(wù)，先分配對(duì)處理機(jī)有特殊要求的組合任務(wù)，再分配包含其他附屬任務(wù)的組合任務(wù)，理機(jī)有特殊要求的組合任務(wù)，再分配包含其他附屬任務(wù)的組合任務(wù)，最后分配不含附屬任務(wù)的組合任務(wù)。調(diào)整階段先排除負(fù)載平衡的處最后分配不含附屬任務(wù)的組合任務(wù)。調(diào)整階段先排除負(fù)載平衡的處理機(jī)，在輕載和重載處理機(jī)之間進(jìn)行調(diào)整。理機(jī)，在輕載和重載處理機(jī)之間進(jìn)行調(diào)整。第25頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管

23、理 改進(jìn)后的啟發(fā)式算法改進(jìn)后的啟發(fā)式算法 數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義 系統(tǒng)中有系統(tǒng)中有n個(gè)處理機(jī)，個(gè)處理機(jī)，m個(gè)計(jì)算任務(wù)（個(gè)計(jì)算任務(wù)（mn）。）。 任務(wù)間通信開銷矩陣任務(wù)間通信開銷矩陣Cmm： Cmm = cij | 1im，1jm ，為任務(wù)為任務(wù)ti，tj之間的通信開銷之間的通信開銷 任務(wù)執(zhí)行開銷矩陣任務(wù)執(zhí)行開銷矩陣Qmn： Qmn = qij | 1im，1jn ，為為ti在在Pj上的運(yùn)行開銷上的運(yùn)行開銷 任務(wù)優(yōu)先矩陣任務(wù)優(yōu)先矩陣Amn： aij = 1 表示任務(wù)表示任務(wù)ti不能分配給處理機(jī)不能分配給處理機(jī)Pj，否則為否則為0 任務(wù)互斥矩陣任務(wù)互斥矩陣Emm： eij = 1 表示任務(wù)表示任

24、務(wù)ti與與tj不能分配給同一臺(tái)處理機(jī)，否則為不能分配給同一臺(tái)處理機(jī)，否則為0第26頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 任務(wù)分配矩陣任務(wù)分配矩陣Xmn： xij = 1 表示任務(wù)表示任務(wù)ti已經(jīng)分配給處理機(jī)已經(jīng)分配給處理機(jī)Pj ，否則為，否則為0 處理機(jī)處理機(jī)Pk上的負(fù)載：上的負(fù)載： Lk = w qikxik，其中常數(shù)其中常數(shù)w w用來調(diào)整執(zhí)行開銷與通信開銷的量綱用來調(diào)整執(zhí)行開銷與通信開銷的量綱 某個(gè)任務(wù)與組合任務(wù)中的任一分任務(wù)互斥，即為與該組合任務(wù)互斥。某個(gè)任務(wù)與組合任務(wù)中的任一分任務(wù)互斥，即為與該組合任務(wù)互斥。 算法算法 將附屬于同一處理機(jī)的任務(wù)合一，得到壓縮后

25、的矩陣將附屬于同一處理機(jī)的任務(wù)合一，得到壓縮后的矩陣A和和E, ,A的行數(shù)為的行數(shù)為m，E的行列數(shù)均為的行列數(shù)均為m，記為，記為Am n和和Em m。同樣，。同樣，Q和和C也變?yōu)橐沧優(yōu)镼m n，Cm m，它們的元，它們的元素值也會(huì)相應(yīng)改變。素值也會(huì)相應(yīng)改變。 對(duì)對(duì)Cm m的每一行進(jìn)行排序，查找最大通信量的任務(wù)對(duì)的每一行進(jìn)行排序，查找最大通信量的任務(wù)對(duì) 對(duì)處理機(jī)按現(xiàn)有負(fù)載建棧，棧頂為負(fù)載最輕的對(duì)處理機(jī)按現(xiàn)有負(fù)載建棧，棧頂為負(fù)載最輕的P Pk k。若棧非空，選。若棧非空，選P Pk k，否則，否則轉(zhuǎn)轉(zhuǎn)。i=1m第27頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 若所有任務(wù)已分配完

26、，轉(zhuǎn)若所有任務(wù)已分配完，轉(zhuǎn)，否則，若，否則，若Pk有附屬任務(wù)，記該任務(wù)為有附屬任務(wù)，記該任務(wù)為t,若若Pk無無附屬任務(wù)，任選一個(gè)未分配任務(wù)為附屬任務(wù)，任選一個(gè)未分配任務(wù)為t。 尋找與尋找與t由最大通信量的未分配任務(wù)由最大通信量的未分配任務(wù)tj，若加入后仍滿足：，若加入后仍滿足： 實(shí)時(shí)限制實(shí)時(shí)限制Rk，存儲(chǔ)限制，存儲(chǔ)限制Sk； aij = 0= 0，即，即tj可以分配到可以分配到Pk上；上； tj不與任何已分配到不與任何已分配到Pk上的任務(wù)互斥；上的任務(wù)互斥； 將將tj分配到分配到Pk上。否則選下一個(gè)與上。否則選下一個(gè)與t有最大通信量的未分配任務(wù)有最大通信量的未分配任務(wù)tj，重復(fù)，重復(fù)。若。若無

27、法找到這樣的無法找到這樣的tj，若可分配就將，若可分配就將t分配給分配給Pk。 若沒有這樣的任務(wù)若沒有這樣的任務(wù)t和和tj能分配給能分配給Pk，將，將Pk從棧中刪去。否則修改從棧中刪去。否則修改Pk的負(fù)載，的負(fù)載，轉(zhuǎn)轉(zhuǎn) 。 檢查剩余任務(wù)，如有，設(shè)當(dāng)前任務(wù)為檢查剩余任務(wù)，如有，設(shè)當(dāng)前任務(wù)為ti，其優(yōu)先任務(wù)為，其優(yōu)先任務(wù)為tj，若，若tj已經(jīng)分配給已經(jīng)分配給Pk，則從則從Pk中取出中取出tj，將，將ti分配給分配給Pk，并尋找可以接收，并尋找可以接收tj的處理機(jī)。若剩余任務(wù)不能分配給任的處理機(jī)。若剩余任務(wù)不能分配給任何處理機(jī)，分配失敗，退出。何處理機(jī)，分配失敗，退出。第28頁/共56頁 分布式系統(tǒng)

28、中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 計(jì)算處理機(jī)計(jì)算處理機(jī)Pk（k=1,2,，n）的負(fù)載）的負(fù)載Lk并求出平均負(fù)載并求出平均負(fù)載L，定義，定義rk = Lk/L。 若若1-drk1+d ，Pk為平衡；為平衡； 若若rk 1-d，Pk為輕載；為輕載； 若若rk 1+d，Pk為超載；為超載； 去掉分配給平衡處理機(jī)的任務(wù)，將輕載處理機(jī)上的任務(wù)合一為一個(gè)組合任務(wù)。以去掉分配給平衡處理機(jī)的任務(wù)，將輕載處理機(jī)上的任務(wù)合一為一個(gè)組合任務(wù)。以輕載、超載處理機(jī)上的任務(wù)集合為對(duì)象，轉(zhuǎn)輕載、超載處理機(jī)上的任務(wù)集合為對(duì)象，轉(zhuǎn)重新建棧。若此次分配未引起負(fù)載變化，重新建棧。若此次分配未引起負(fù)載變化，算法終止。算法終止。

29、第29頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 基于遺傳算法和模擬退火算法的任務(wù)分配算法基于遺傳算法和模擬退火算法的任務(wù)分配算法 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 建立一個(gè)五元組建立一個(gè)五元組 = =（ T， ，Q，C，X ） 其中其中T為任務(wù)集合；為任務(wù)集合；“ ”為為T上的優(yōu)先關(guān)系，上的優(yōu)先關(guān)系，ti tj 表示表示ti必須在必須在tj執(zhí)行之前完成；執(zhí)行之前完成；Q為為mm矩陣，矩陣，qij表示任務(wù)表示任務(wù)ti在處理機(jī)在處理機(jī)Pj上的執(zhí)行時(shí)間；上的執(zhí)行時(shí)間；C是一個(gè)是一個(gè)mn矩陣，矩陣，Cij表示表示任務(wù)任務(wù)ti與任務(wù)與任務(wù)tj的通信開銷；的通信開銷；X是一個(gè)是一個(gè)mn的任務(wù)分配矩陣

30、，的任務(wù)分配矩陣，xij=1=1表示表示ti分配到處理機(jī)分配到處理機(jī)Pj上，否則為上，否則為0 0。 設(shè)計(jì)目標(biāo)函數(shù)設(shè)計(jì)目標(biāo)函數(shù)cost，例如，例如 cost = (qik xik+w ckr xik xjr) 其中常數(shù)其中常數(shù)w w用來調(diào)節(jié)量綱差異用來調(diào)節(jié)量綱差異 i=1 k=1mnr=1 j=1K-1 i-1第30頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 迭代過程迭代過程 進(jìn)行初始化，隨機(jī)生成一個(gè)初始任務(wù)分配集合。例如：進(jìn)行初始化，隨機(jī)生成一個(gè)初始任務(wù)分配集合。例如：處理機(jī)處理機(jī)任務(wù)任務(wù)P0P1P1t1t2t3t4t5t6t7110000000110000000111第

31、31頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 描述與生成一個(gè)初始任務(wù)分配集合描述與生成一個(gè)初始任務(wù)分配集合TA。 其中，特定的任務(wù)分配方案用（其中，特定的任務(wù)分配方案用（S，R1.n）表示。其中，）表示。其中，S 是一個(gè)是一個(gè) log2n m 的二的二進(jìn)制串，每個(gè)進(jìn)制串，每個(gè) log2n 位稱為一節(jié)，自左到右的第位稱為一節(jié)，自左到右的第i節(jié)就表示任務(wù)節(jié)就表示任務(wù)ti所在的處理機(jī)號(hào)碼。上所在的處理機(jī)號(hào)碼。上例中，例中，S = 00 00 01 01 10 10 10。R是一個(gè)有是一個(gè)有n個(gè)分量的鏈表數(shù)組，每個(gè)分量的類型為個(gè)分量的鏈表數(shù)組，每個(gè)分量的類型為m元整數(shù)數(shù)組，自左向

32、右表示任務(wù)執(zhí)行的順序。假定上例中的優(yōu)先次序?yàn)樵麛?shù)數(shù)組，自左向右表示任務(wù)執(zhí)行的順序。假定上例中的優(yōu)先次序?yàn)閠1 t2，t4 t5，t6 t7，這樣，這樣R為：為：R0：12，R1：34，R2：567（或（或675，或，或657，因?yàn)橹挥?，因?yàn)橹挥?、7有次有次序關(guān)系）。序關(guān)系）。 這樣，這樣，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 =（ 12 34 657） 于是，

33、可以選取若干分配方案，形成初始任務(wù)分配集合：于是，可以選取若干分配方案，形成初始任務(wù)分配集合： TA = S，R1.n 第32頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 設(shè)置退火算法中的初始溫度設(shè)置退火算法中的初始溫度temp0和收斂率和收斂率 （0 1），溫度），溫度tempi+1 = tempi，逐步降低。這里，逐步降低。這里，i既代表第既代表第i次迭代，也代表遺傳算法中的地次迭代，也代表遺傳算法中的地i代個(gè)體。代個(gè)體。 一般在任務(wù)量較大的情形，一般在任務(wù)量較大的情形，temp0可以取可以取1000， temp 取為取為1， 取取，效果較好。，效果較好。 進(jìn)行迭代循環(huán)。

34、對(duì)初始任務(wù)分配集合中的方案采用交叉繁殖、變異等方法，形進(jìn)行迭代循環(huán)。對(duì)初始任務(wù)分配集合中的方案采用交叉繁殖、變異等方法，形成新一代分配方案集合，不斷進(jìn)行。成新一代分配方案集合，不斷進(jìn)行。 交叉繁殖交叉繁殖 對(duì)父代的兩個(gè)分配方案中對(duì)父代的兩個(gè)分配方案中S的某些節(jié)進(jìn)行替換，選取其中的優(yōu)良者（的某些節(jié)進(jìn)行替換，選取其中的優(yōu)良者（cost較?。┹^小）插入分配集合，形成第二代分配集合。插入分配集合，形成第二代分配集合。 例例 兩個(gè)父代方案：兩個(gè)父代方案： TA1.S = 00 00 01 01 10 10 10； TA1.R =（12 34 567） TA2.S = 01 01 01 00 10 00

35、10； TA2.R =（46 123 57 ） 第33頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 用用TA1.S中的中的1、3、6節(jié)替換節(jié)替換TA2.S中的相應(yīng)節(jié)，形成新方案：中的相應(yīng)節(jié)，形成新方案： TA3.S = 00 01 01 00 10 10 10； TA3.R = （ 14 23 567） 計(jì)算計(jì)算 cost = cost(TA3) cost(TA2)： 0 表示新方案優(yōu)于原方案，將表示新方案優(yōu)于原方案，將TA3插入新的分配集合；插入新的分配集合； 0表示原方案優(yōu)于新方案，計(jì)算概率值：表示原方案優(yōu)于新方案，計(jì)算概率值： prob = exp | cost/k t

36、emp | ，式中，式中k為波爾茲曼常數(shù)，為波爾茲曼常數(shù)，temp為當(dāng)前溫度；為當(dāng)前溫度； 由系統(tǒng)產(chǎn)生（由系統(tǒng)產(chǎn)生（0，1）之間的隨機(jī)數(shù)）之間的隨機(jī)數(shù)rand，若，若probrand，將新方案加入分，將新方案加入分配集合，反之舍棄。配集合，反之舍棄。 變異變異 對(duì)某些方案作變異處理，形成新方案。如對(duì)對(duì)某些方案作變異處理，形成新方案。如對(duì)某些節(jié)求反、互換處理任務(wù)等。變某些節(jié)求反、互換處理任務(wù)等。變異不會(huì)造成個(gè)體數(shù)量的變化。每次變異后，對(duì)一個(gè)原方案只保留一種有效的變異方案。異不會(huì)造成個(gè)體數(shù)量的變化。每次變異后，對(duì)一個(gè)原方案只保留一種有效的變異方案。 通過這種方法，可以得到比較理想的分配方案。通過這

37、種方法，可以得到比較理想的分配方案。第34頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 基于有向任務(wù)圖的調(diào)度策略基于有向任務(wù)圖的調(diào)度策略 假定：已知每個(gè)任務(wù)的執(zhí)行時(shí)間，任務(wù)之間的時(shí)序關(guān)系、任務(wù)假定：已知每個(gè)任務(wù)的執(zhí)行時(shí)間，任務(wù)之間的時(shí)序關(guān)系、任務(wù)間的通信量、可使用計(jì)算機(jī)的數(shù)目；間的通信量、可使用計(jì)算機(jī)的數(shù)目；分布式系統(tǒng)中有統(tǒng)一的時(shí)鐘、結(jié)點(diǎn)同分布式系統(tǒng)中有統(tǒng)一的時(shí)鐘、結(jié)點(diǎn)同構(gòu)（從而保證每個(gè)任務(wù)在不同計(jì)算機(jī)上的處理時(shí)間相同、通信開銷固定）構(gòu)（從而保證每個(gè)任務(wù)在不同計(jì)算機(jī)上的處理時(shí)間相同、通信開銷固定）；計(jì)算任務(wù)除通信以外的資源都可以從本機(jī)上獲得。計(jì)算任務(wù)除通信以外的資源都可以從本

38、機(jī)上獲得。 步驟步驟 生成非循環(huán)的任務(wù)有向圖生成非循環(huán)的任務(wù)有向圖 G = V，E，e，c T14T23T37T492522第35頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 上圖中，上圖中， 結(jié)點(diǎn)集合結(jié)點(diǎn)集合 V = T1，T2，T3，T4 有向邊集合有向邊集合 E = (T1,T2)，(T1,T3)，(T2,T4)，(T3,T4) 運(yùn)行開銷集合運(yùn)行開銷集合 e = 4，3，7，9 通信開銷集合通信開銷集合 c = 2，5，2，2 任務(wù)復(fù)制任務(wù)復(fù)制 使任務(wù)在兩個(gè)以上的計(jì)算機(jī)上有執(zhí)行副本。使任務(wù)在兩個(gè)以上的計(jì)算機(jī)上有執(zhí)行副本。T13T27T3276第36頁/共56頁 分布式系

39、統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 上圖中，三個(gè)任務(wù)在兩個(gè)計(jì)算機(jī)上有三種分配方案（未復(fù)制）：上圖中，三個(gè)任務(wù)在兩個(gè)計(jì)算機(jī)上有三種分配方案（未復(fù)制）： T1T1T1T2T2T2T3T3T367第37頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 第一種情況：總時(shí)間第一種情況：總時(shí)間11 第二種情況：總時(shí)間第二種情況：總時(shí)間17 第三種情況：總時(shí)間第三種情況：總時(shí)間12（在一個(gè)計(jì)算機(jī)上）（在一個(gè)計(jì)算機(jī)上） 如果進(jìn)行任務(wù)復(fù)制：如果進(jìn)行任務(wù)復(fù)制：T1T1T3T2總時(shí)間：總時(shí)間：10任務(wù)復(fù)制將帶來好處任務(wù)復(fù)制將帶來好處第38頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)

40、管理 計(jì)算最早開始時(shí)間計(jì)算最早開始時(shí)間 貪心函數(shù)貪心函數(shù)f：假定假定C是包含結(jié)點(diǎn)是包含結(jié)點(diǎn)v以及它的父結(jié)以及它的父結(jié)點(diǎn)點(diǎn) 1， 2， 3， k 的聚集。定義的聚集。定義 f ( 1， 2， 3， k )為全部完成為全部完成 1， 2， 3， k 的最的最早可能結(jié)束時(shí)間。定義早可能結(jié)束時(shí)間。定義s ( v )為結(jié)點(diǎn)為結(jié)點(diǎn) v 的開始執(zhí)行時(shí)間。的開始執(zhí)行時(shí)間。顯然：顯然： s ( v ) f ( 1， 2， 3， k ) = f ( C v ) 考慮：考慮：T14T22T32T44貪心函數(shù)貪心函數(shù) f ( C T4 ) = 0 + 4 + 2 = 6只有只有T1，T3，T4分配在同一個(gè)計(jì)算機(jī)分配在

41、同一個(gè)計(jì)算機(jī)上才能達(dá)到：上才能達(dá)到：868第39頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 最大弦值函數(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) 是結(jié)點(diǎn)是結(jié)點(diǎn)u u的最早開始時(shí)間，的最早開始時(shí)間，e(u)e(u)是是 u的運(yùn)行時(shí)的運(yùn)行時(shí)間，間，c ( u,w )是是u，w的通信開銷。的通信開銷。 最大弦值函數(shù)最大弦值函數(shù)macg(C)定義為由不屬于定義為由不屬于C的節(jié)點(diǎn)到的節(jié)點(diǎn)到C中節(jié)點(diǎn)的最大弦值。中節(jié)點(diǎn)的

42、最大弦值。 T14T22T32T4451令令 C = T3，T4，maxg（C）= 9 第40頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 在一個(gè)給定的分配方案里，節(jié)點(diǎn)在一個(gè)給定的分配方案里，節(jié)點(diǎn)v的最早開始時(shí)間的最早開始時(shí)間 sv f（Cv）；）； 在上例中，在上例中，T4的最早開始時(shí)間為的最早開始時(shí)間為11。 計(jì)算聚集的算法計(jì)算聚集的算法 令結(jié)點(diǎn)集合令結(jié)點(diǎn)集合G，剛開始時(shí)，所有結(jié)點(diǎn)均未作標(biāo)記。剛開始時(shí)，所有結(jié)點(diǎn)均未作標(biāo)記。 取取G中未標(biāo)記結(jié)點(diǎn)中未標(biāo)記結(jié)點(diǎn)v； 若若v未根結(jié)點(diǎn)，作標(biāo)記后轉(zhuǎn)未根結(jié)點(diǎn)，作標(biāo)記后轉(zhuǎn) ； 令令C為空，為空，v加入加入C，計(jì)算計(jì)算 s = maxg (

43、 C )； 選擇具有最大弦值的選擇具有最大弦值的( u,w )，其中其中u C，且且u為第一次被選為第一次被選擇，擇， w C，C = C + u ，若無轉(zhuǎn)若無轉(zhuǎn) ； 若若maxg 、f ( C-v )均不大于均不大于S， 則則S = max( maxg(C) , f( C v)），），否則否則C = C u ，轉(zhuǎn)轉(zhuǎn) ； C = C u 輸出輸出C和和v，對(duì)對(duì)v做標(biāo)記，若做標(biāo)記，若G中為全部標(biāo)記轉(zhuǎn)中為全部標(biāo)記轉(zhuǎn) ，否則結(jié)，否則結(jié)束。束。 第41頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理評(píng)述：評(píng)述： 總思路：對(duì)任一非根結(jié)點(diǎn)，計(jì)算其最大聚集弦值，找出滿足該弦值得一總思路：對(duì)任一

44、非根結(jié)點(diǎn)，計(jì)算其最大聚集弦值，找出滿足該弦值得一對(duì)結(jié)點(diǎn)。嘗試將聚集外的結(jié)點(diǎn)加入該聚集，看能否降低其最大弦值，若能對(duì)結(jié)點(diǎn)。嘗試將聚集外的結(jié)點(diǎn)加入該聚集，看能否降低其最大弦值，若能則繼續(xù)，否則去掉加入的結(jié)點(diǎn)，輸出聚集。則繼續(xù)，否則去掉加入的結(jié)點(diǎn)，輸出聚集。例例T110T35T29T45T55T661412643起始，起始，C中有中有T6，這時(shí)，這時(shí)maxg(C) = 41；第一次循環(huán)結(jié)束，第一次循環(huán)結(jié)束，C = T5,T6 , maxg(C) = 33；第二次循環(huán)開始，第二次循環(huán)開始，u = T4，取，取u = T4， 則則f ( C T4 ) = 27，送入，送入s；加入加入T4，則，則maxg

45、(C) 21第42頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 該算法對(duì)每一個(gè)非根結(jié)點(diǎn)都會(huì)輸出一個(gè)聚集，若某一聚集為另一個(gè)聚該算法對(duì)每一個(gè)非根結(jié)點(diǎn)都會(huì)輸出一個(gè)聚集，若某一聚集為另一個(gè)聚集的子集，則刪去，最后得到若干相互沒有包含的狙擊。若聚集的數(shù)目不集的子集，則刪去，最后得到若干相互沒有包含的狙擊。若聚集的數(shù)目不大于計(jì)算機(jī)的數(shù)目，為每一個(gè)聚集分配一個(gè)計(jì)算機(jī)，否則根據(jù)情況再進(jìn)行大于計(jì)算機(jī)的數(shù)目，為每一個(gè)聚集分配一個(gè)計(jì)算機(jī)，否則根據(jù)情況再進(jìn)行調(diào)整。調(diào)整。 在上例中，如果有兩臺(tái)計(jì)算機(jī)，那么分配方案：在上例中，如果有兩臺(tái)計(jì)算機(jī)，那么分配方案： T2T4T5T6T1T3若有三臺(tái)計(jì)算機(jī)，分

46、配方案改為：若有三臺(tái)計(jì)算機(jī)，分配方案改為：T2T4T1T3T5T6第43頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理3. 調(diào)度問題調(diào)度問題 正常情況下，分布式系統(tǒng)中的各結(jié)點(diǎn)機(jī)有自己的本地調(diào)度程序，負(fù)責(zé)正常情況下，分布式系統(tǒng)中的各結(jié)點(diǎn)機(jī)有自己的本地調(diào)度程序，負(fù)責(zé)調(diào)度本機(jī)上的任務(wù)進(jìn)程。調(diào)度本機(jī)上的任務(wù)進(jìn)程。 問題：問題： 在需要進(jìn)行遠(yuǎn)程通信時(shí)，各自計(jì)算機(jī)上的獨(dú)立調(diào)度可能會(huì)影響系統(tǒng)的在需要進(jìn)行遠(yuǎn)程通信時(shí)，各自計(jì)算機(jī)上的獨(dú)立調(diào)度可能會(huì)影響系統(tǒng)的性能。性能。 例例 兩個(gè)節(jié)點(diǎn)的系統(tǒng)，每個(gè)結(jié)點(diǎn)各有兩個(gè)進(jìn)程，結(jié)點(diǎn)兩個(gè)節(jié)點(diǎn)的系統(tǒng)，每個(gè)結(jié)點(diǎn)各有兩個(gè)進(jìn)程，結(jié)點(diǎn)1有進(jìn)程有進(jìn)程A，B：結(jié)點(diǎn)結(jié)點(diǎn)2有進(jìn)程

47、有進(jìn)程C，D。兩個(gè)結(jié)點(diǎn)各自采用分時(shí)方式調(diào)度方式調(diào)度，時(shí)間片為。兩個(gè)結(jié)點(diǎn)各自采用分時(shí)方式調(diào)度方式調(diào)度，時(shí)間片為100ms。 第44頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理時(shí)間片時(shí)間片處處 理理 機(jī)機(jī)0 1012345ACBDCACABDDB 在時(shí)間片在時(shí)間片0 0，A A啟動(dòng)后立即向啟動(dòng)后立即向D D發(fā)出遠(yuǎn)發(fā)出遠(yuǎn)程調(diào)用，自己等待結(jié)果；但處理機(jī)程調(diào)用，自己等待結(jié)果；但處理機(jī)1 1上上C C正在運(yùn)行。到第二個(gè)時(shí)間片，正在運(yùn)行。到第二個(gè)時(shí)間片，D D立即立即處理遠(yuǎn)程調(diào)用并返回結(jié)果，但此時(shí)處理遠(yuǎn)程調(diào)用并返回結(jié)果，但此時(shí)A A已已經(jīng)不在運(yùn)行狀態(tài)（經(jīng)不在運(yùn)行狀態(tài)（B B在運(yùn)行）在運(yùn)行）

48、 由于通信與運(yùn)行不同步，將導(dǎo)致處由于通信與運(yùn)行不同步，將導(dǎo)致處理機(jī)無謂等待。理機(jī)無謂等待。 第45頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 解決辦法解決辦法1： 處理機(jī)采用時(shí)間片輪轉(zhuǎn)方法時(shí)，將進(jìn)程按通信關(guān)系編組，盡可能將處于同一通信處理機(jī)采用時(shí)間片輪轉(zhuǎn)方法時(shí)，將進(jìn)程按通信關(guān)系編組，盡可能將處于同一通信組的進(jìn)程安排在相同時(shí)間片里運(yùn)行。組的進(jìn)程安排在相同時(shí)間片里運(yùn)行。 問題：遠(yuǎn)程調(diào)用發(fā)生的時(shí)機(jī)是隨機(jī)的，很難做到準(zhǔn)確問題：遠(yuǎn)程調(diào)用發(fā)生的時(shí)機(jī)是隨機(jī)的，很難做到準(zhǔn)確。 解決辦法解決辦法2： 處理機(jī)調(diào)度采用分時(shí)和可搶占方法相結(jié)合。當(dāng)一個(gè)遠(yuǎn)程調(diào)用到來時(shí)，被調(diào)用進(jìn)程所處理機(jī)調(diào)度采用分時(shí)和

49、可搶占方法相結(jié)合。當(dāng)一個(gè)遠(yuǎn)程調(diào)用到來時(shí)，被調(diào)用進(jìn)程所在的處理機(jī)將當(dāng)前運(yùn)行進(jìn)程掛起，調(diào)度相應(yīng)進(jìn)程運(yùn)行；調(diào)用結(jié)束后再恢復(fù)原進(jìn)程運(yùn)行完在的處理機(jī)將當(dāng)前運(yùn)行進(jìn)程掛起，調(diào)度相應(yīng)進(jìn)程運(yùn)行；調(diào)用結(jié)束后再恢復(fù)原進(jìn)程運(yùn)行完剩余的時(shí)間片。處理遠(yuǎn)程調(diào)用不占進(jìn)程的時(shí)間片。剩余的時(shí)間片。處理遠(yuǎn)程調(diào)用不占進(jìn)程的時(shí)間片。 好處：通信量較大的進(jìn)程可以在運(yùn)行時(shí)間上有所優(yōu)待，以保證與其通信的它機(jī)進(jìn)程好處：通信量較大的進(jìn)程可以在運(yùn)行時(shí)間上有所優(yōu)待，以保證與其通信的它機(jī)進(jìn)程正常運(yùn)行。正常運(yùn)行。 缺點(diǎn)：進(jìn)程間切換可能過于頻繁，影響處理機(jī)的有效利用率。缺點(diǎn)：進(jìn)程間切換可能過于頻繁，影響處理機(jī)的有效利用率。第46頁/共56頁 分布式系統(tǒng)中

50、的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理3 3 系統(tǒng)容錯(cuò)系統(tǒng)容錯(cuò)1.1.需要討論的問題需要討論的問題 設(shè)備故障的兩種情況設(shè)備故障的兩種情況 fail and stop Byzantine 容錯(cuò)的通常做法容錯(cuò)的通常做法 冗余技術(shù)，包括信息冗余、時(shí)間冗余和物理設(shè)備的冗余。冗余技術(shù)，包括信息冗余、時(shí)間冗余和物理設(shè)備的冗余。 信息冗余：增加效驗(yàn)碼、鏡像存放、多副本等信息冗余：增加效驗(yàn)碼、鏡像存放、多副本等 時(shí)間冗余：必要的重復(fù)執(zhí)行，如原子事務(wù)技術(shù)等時(shí)間冗余：必要的重復(fù)執(zhí)行，如原子事務(wù)技術(shù)等 物理冗余：增加設(shè)備，包括主動(dòng)備份、被動(dòng)備份物理冗余：增加設(shè)備，包括主動(dòng)備份、被動(dòng)備份 第47頁/共56頁 分布式系統(tǒng)

51、中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 2. 主動(dòng)備份主動(dòng)備份 對(duì)對(duì)fail and stop類型故障比較有效類型故障比較有效 容錯(cuò)級(jí)別：容錯(cuò)級(jí)別： 系統(tǒng)稱為系統(tǒng)稱為K級(jí)容錯(cuò)，是指級(jí)容錯(cuò)，是指k個(gè)部件出現(xiàn)故障，系統(tǒng)個(gè)部件出現(xiàn)故障，系統(tǒng)仍能正常工作，需要配備仍能正常工作，需要配備K+1套設(shè)施。套設(shè)施。 對(duì)服務(wù)器，設(shè)置對(duì)服務(wù)器，設(shè)置K+1個(gè)，要求每個(gè)個(gè)，要求每個(gè)ClientClient的請(qǐng)求的請(qǐng)求按照相同的（服務(wù)器）次序執(zhí)行并應(yīng)答，稱為原子廣播。按照相同的（服務(wù)器）次序執(zhí)行并應(yīng)答，稱為原子廣播。但在網(wǎng)絡(luò)環(huán)境很難實(shí)現(xiàn)。但在網(wǎng)絡(luò)環(huán)境很難實(shí)現(xiàn)。 方法方法1 1：對(duì)遠(yuǎn)程請(qǐng)求實(shí)行全局編號(hào)，需要一臺(tái)編號(hào)服務(wù)器

52、實(shí)現(xiàn)：對(duì)遠(yuǎn)程請(qǐng)求實(shí)行全局編號(hào)，需要一臺(tái)編號(hào)服務(wù)器實(shí)現(xiàn)編號(hào)與分發(fā)，集中式弊病。編號(hào)與分發(fā)，集中式弊病。 方法方法2 2：使用邏輯時(shí)鐘，請(qǐng)求加蓋時(shí)間郵戳。但有麻煩：如何：使用邏輯時(shí)鐘，請(qǐng)求加蓋時(shí)間郵戳。但有麻煩：如何知道知道 還有沒有更早的請(qǐng)求正在路上？還有沒有更早的請(qǐng)求正在路上？ 第48頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 2. 被動(dòng)備份被動(dòng)備份 指定一臺(tái)設(shè)備為主設(shè)備，處理一切有關(guān)的事務(wù)，其指定一臺(tái)設(shè)備為主設(shè)備，處理一切有關(guān)的事務(wù)，其它同類設(shè)備為備份設(shè)備。只有當(dāng)主設(shè)備故障時(shí)，才由備它同類設(shè)備為備份設(shè)備。只有當(dāng)主設(shè)備故障時(shí)，才由備份機(jī)接替工作。份機(jī)接替工作。 正常情況下，

53、運(yùn)行策略簡單：消息秩序相主服務(wù)器正常情況下，運(yùn)行策略簡單：消息秩序相主服務(wù)器發(fā)送，不必向整個(gè)服務(wù)器群發(fā)送，次序問題基本上不存發(fā)送，不必向整個(gè)服務(wù)器群發(fā)送，次序問題基本上不存在。而且備份機(jī)也比較節(jié)省。在。而且備份機(jī)也比較節(jié)省。 clientPrimaryserverbackupserver 發(fā)送請(qǐng)求發(fā)送請(qǐng)求 工作，完成請(qǐng)求任務(wù)工作，完成請(qǐng)求任務(wù) 發(fā)送更新要求發(fā)送更新要求 工作，完成更新工作，完成更新 確認(rèn)，完成更新確認(rèn)，完成更新 返回結(jié)果返回結(jié)果第49頁/共56頁 分布式系統(tǒng)中的處理機(jī)管理分布式系統(tǒng)中的處理機(jī)管理 在執(zhí)行一個(gè)在執(zhí)行一個(gè)RPC過程中，服務(wù)器故障時(shí)刻分析：過程中，服務(wù)器故障時(shí)刻分析：

54、 在在以前，不會(huì)有影響，以前，不會(huì)有影響，client發(fā)現(xiàn)響應(yīng)超時(shí)重新請(qǐng)求，再三發(fā)現(xiàn)響應(yīng)超時(shí)重新請(qǐng)求，再三請(qǐng)求未果，確認(rèn)服務(wù)器故障，轉(zhuǎn)向備份服務(wù)器；請(qǐng)求未果，確認(rèn)服務(wù)器故障，轉(zhuǎn)向備份服務(wù)器； 在在、階段，同上面情況，備份機(jī)接替工作，完成服務(wù)；階段，同上面情況，備份機(jī)接替工作，完成服務(wù)； 在在以后，以后，完成前，備份機(jī)接替工作。完成前，備份機(jī)接替工作。 系統(tǒng)運(yùn)行過程中，備份機(jī)與主機(jī)不斷通信，詢問是否正系統(tǒng)運(yùn)行過程中，備份機(jī)與主機(jī)不斷通信，詢問是否正常。常。 改進(jìn)方法：主機(jī)與備份機(jī)共享磁盤，采用磁盤鏡像改進(jìn)方法：主機(jī)與備份機(jī)共享磁盤，采用磁盤鏡像或交換式磁盤兩種方法。平時(shí)備份機(jī)不必進(jìn)行或交換式磁盤兩種方法。平時(shí)備份機(jī)不必進(jìn)行RPC的計(jì)的計(jì)算工作，直到主機(jī)故障才接替工作。算工作，直到主