高級(jí)操作系統(tǒng)課件

高級(jí)操作系統(tǒng)

AdvancedOperatingSystemxxx中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院1感謝你的觀看2019年7月19高級(jí)操作系統(tǒng)

AdvancedOperatingSyst第四章分布式進(jìn)程和處理機(jī)管理分布式系統(tǒng)模型分布式處理機(jī)分配算法分布式進(jìn)程調(diào)度分布式系統(tǒng)容錯(cuò)實(shí)時(shí)分布式系統(tǒng)2感謝你的觀看2019年7月19第四章分布式進(jìn)程和處理機(jī)管理分布式系統(tǒng)模型2感謝你的觀看24.2分布式處理機(jī)分配算法處理機(jī)分配的理由:分布式系統(tǒng)包括多個(gè)處理機(jī)，具有較大的分布處理能力。一個(gè)作業(yè)將產(chǎn)生多個(gè)任務(wù)或進(jìn)程，它們需要分配在多個(gè)處理機(jī)上并行執(zhí)行，以充分利用分布式系統(tǒng)提供的巨大處理能力。因此，分布式系統(tǒng)需要一個(gè)良好的處理機(jī)分配算法來(lái)決定每個(gè)進(jìn)程或任務(wù)應(yīng)分配到哪一個(gè)處理機(jī)上執(zhí)行，通常，這個(gè)算法被稱為處理機(jī)分配算法或任務(wù)分配算法（而不稱作進(jìn)程分配算法，盡管但兩者的意思完全相同）。3感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法處理機(jī)分配的理由:3感謝你的觀看4.2分布式處理機(jī)分配算法

處理機(jī)分配的基本模型、假定和目標(biāo)：

1）關(guān)于處理器：假定所有的機(jī)器都是相同的，至少是代碼兼容的，不同的只是運(yùn)行速度。有些還假定系統(tǒng)具有多個(gè)互不相關(guān)的處理機(jī)池，每一個(gè)處理機(jī)池都是相同的。

4感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法處理機(jī)分配的基本模4.2分布式處理機(jī)分配算法 2）關(guān)于互連拓?fù)洌杭俣ㄏ到y(tǒng)是完全互連的，即每一個(gè)處理機(jī)都可以與其它任意一個(gè)處理機(jī)通信。這并不表示每一個(gè)機(jī)器與其它任意一臺(tái)機(jī)器之間都有線路直接連接，這個(gè)假定只是意味著每一對(duì)機(jī)器都可以互相通信。至于消息是如何從一臺(tái)機(jī)器到達(dá)另一臺(tái)機(jī)器的問(wèn)題只是低層通信軟件的事，處理機(jī)分配算法無(wú)需考慮。但有一些處理機(jī)分配算法利用了網(wǎng)絡(luò)的廣播或者多播的特性。5感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法 2）關(guān)于互連拓?fù)洌?感謝你的觀看4.2分布式處理機(jī)分配算法新進(jìn)程的產(chǎn)生和處理機(jī)的分配：當(dāng)一個(gè)運(yùn)行中的進(jìn)程決定創(chuàng)建一個(gè)子進(jìn)程時(shí)，產(chǎn)生了下列工作：在有些情況下，創(chuàng)建進(jìn)程是由系統(tǒng)的命令解釋程序（即shell）來(lái)完成的。它為用戶執(zhí)行其指定的命令所對(duì)應(yīng)的程序。而在另一些情況下，用戶進(jìn)程本身也可以創(chuàng)建一個(gè)或者多個(gè)子進(jìn)程，以獲得較高的系統(tǒng)性能。對(duì)新進(jìn)程必須考慮分配到哪個(gè)處理器上運(yùn)行6感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法新進(jìn)程的產(chǎn)生和處理機(jī)的分配：6感謝4.2分布式處理機(jī)分配算法

處理機(jī)分配策略可以分為兩大類：

1）非遷移的

2）可遷移的第一類是非遷移的（nonmigratory）在非遷移策略中，當(dāng)創(chuàng)建一個(gè)進(jìn)程時(shí)，系統(tǒng)就決定它被分配到哪臺(tái)處理機(jī)上。一旦一個(gè)進(jìn)程被分配到一臺(tái)機(jī)器上，那么，它就在那臺(tái)機(jī)器上運(yùn)行，一直到終止，不管這臺(tái)處理機(jī)的負(fù)載是多么的重，而別的處理機(jī)是多么的空閑，它都不能遷移到別的處理機(jī)上運(yùn)行。7感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法處理機(jī)分配策略可以分為兩大類4.2分布式處理機(jī)分配算法第二類是可遷移的（migratory）對(duì)于可遷移策略來(lái)說(shuō)，一個(gè)進(jìn)程即使已經(jīng)被分配到一臺(tái)處理機(jī)上并已經(jīng)運(yùn)行了一段時(shí)間，如果其負(fù)載變重了,它也可以動(dòng)態(tài)地遷移到其它輕負(fù)載的處理機(jī)上繼續(xù)運(yùn)行。雖然可遷移策略可以使系統(tǒng)達(dá)到良好的負(fù)載平衡，但實(shí)現(xiàn)起來(lái)卻異常復(fù)雜。8感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法第二類是可遷移的（migrator4.2分布式處理機(jī)分配算法處理機(jī)分配算法必須盡可能優(yōu)化。否則，我們完全可以隨機(jī)地或按數(shù)字順序來(lái)分配處理機(jī)。不同系統(tǒng)的優(yōu)化內(nèi)容是不一樣的優(yōu)化目標(biāo)1：提高處理機(jī)利用率優(yōu)化目標(biāo)2：最小化平均響應(yīng)時(shí)間9感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法處理機(jī)分配算法必須盡可能優(yōu)化。否則4.2分布式處理機(jī)分配算法第一個(gè)優(yōu)化目標(biāo)就是：

盡量提高處理機(jī)的利用率讓處理機(jī)在每個(gè)小時(shí)內(nèi)執(zhí)行用戶工作的周期數(shù)盡可能地多。換句話說(shuō)，要盡量減少空閑處理機(jī)周期數(shù)。10感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法第一個(gè)優(yōu)化目標(biāo)就是：

盡量提高處理4.2分布式處理機(jī)分配算法第二個(gè)有價(jià)值的優(yōu)化目標(biāo)就是：

使平均響應(yīng)時(shí)間最小化11感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法第二個(gè)有價(jià)值的優(yōu)化目標(biāo)就是：

使平4.2分布式處理機(jī)分配算法

舉例:假設(shè)有兩個(gè)處理機(jī)。 處理機(jī)1以10MIPS的速度運(yùn)行，

處理機(jī)2以100MIPS的速度運(yùn)行，其中等待隊(duì)列中的進(jìn)程需要5秒才能完成。有兩個(gè)進(jìn)程。 進(jìn)程A有1億條指令，執(zhí)行時(shí)間分別為10秒（在處理機(jī)1上）和1秒（在處理機(jī)2上）

進(jìn)程B有3億條指令，執(zhí)行時(shí)間分別為30秒和3秒12感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法 舉例:12感謝你的觀看24.2分布式處理機(jī)分配算法這兩個(gè)進(jìn)程在每一個(gè)處理機(jī)上的響應(yīng)時(shí)間（包括等待時(shí)間）如圖所示。5+1=5+3=13感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法這兩個(gè)進(jìn)程在每一個(gè)處理機(jī)上的響應(yīng)時(shí)4.2分布式處理機(jī)分配算法平均響應(yīng)時(shí)間：如果把進(jìn)程A和B分別分配給處理機(jī)1和2，那么平均響應(yīng)時(shí)間是(10+8)/2=9秒。若反向分配，那么平均響應(yīng)時(shí)間就是(30+6)/2=18秒。顯然，前者的平均響應(yīng)時(shí)間要比后者小。14感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法平均響應(yīng)時(shí)間：14感謝你的觀看204.2分布式處理機(jī)分配算法

最小響應(yīng)時(shí)間的另一種形式就是最小響應(yīng)率。響應(yīng)率定義為：在一臺(tái)機(jī)器上運(yùn)行一個(gè)進(jìn)程所需的時(shí)間除以該進(jìn)程在無(wú)負(fù)載的標(biāo)準(zhǔn)處理機(jī)上運(yùn)行所需的時(shí)間。15感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法最小響應(yīng)時(shí)間的另一種形式就4.2分布式處理機(jī)分配算法

對(duì)于大多數(shù)用戶來(lái)說(shuō)，響應(yīng)率比響應(yīng)時(shí)間更重要。

其原因是：

考慮了大任務(wù)要比小任務(wù)花費(fèi)更多時(shí)間這一情況。例如：一個(gè)1秒的任務(wù)花了5秒，而一個(gè)1分鐘的任務(wù)花了70秒，從響應(yīng)時(shí)間上看，前者好，但從響應(yīng)率上看，后者更好，因?yàn)?/1>>70/60。16感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法對(duì)于大多數(shù)用戶來(lái)說(shuō)，響應(yīng)率4.2分布式處理機(jī)分配算法

考慮負(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ù)載平衡。17感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法考慮負(fù)載的分配方法：17感謝4.2分布式處理機(jī)分配算法最優(yōu)和次優(yōu)（在靜態(tài)和動(dòng)態(tài)兩種類型中）

如果根據(jù)某種標(biāo)準(zhǔn)（例如，最小執(zhí)行時(shí)間和最大系統(tǒng)輸出）可以取得最優(yōu)分配，那么就可以認(rèn)為這種負(fù)載分配方法是最優(yōu)的。

一般地，負(fù)載分配問(wèn)題是NP完全問(wèn)題。某些情況下，次優(yōu)方案（神經(jīng)網(wǎng)絡(luò)方法）也是可以接受的。有四類算法（對(duì)于最優(yōu)的和次優(yōu)的）被使用：

1）解空間枚舉搜索、

2）圖模型、

3）數(shù)學(xué)編程（例如0/1規(guī)劃）

4）隊(duì)列模型18感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法最優(yōu)和次優(yōu)（在靜態(tài)和動(dòng)態(tài)兩種類型中4.2分布式處理機(jī)分配算法近似和啟發(fā)式（在次優(yōu)類型中）

在近似方法中，負(fù)載分配算法僅搜索一個(gè)解空間的子集，當(dāng)尋找到一個(gè)好的解時(shí)，終止執(zhí)行

在啟發(fā)式方法中，調(diào)度算法使用某些特殊參數(shù)，能夠近似地對(duì)真實(shí)系統(tǒng)建模。19感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法近似和啟發(fā)式（在次優(yōu)類型中）

4.2分布式處理機(jī)分配算法集中控制的和分散控制的（在動(dòng)態(tài)類型中）

在分散控制中，分配決策工作被分配給不同的處理器。在集中控制中，分配決策工作由一個(gè)處理器完成。協(xié)作的和非協(xié)作的（對(duì)分散控制）

動(dòng)態(tài)負(fù)載分配機(jī)制可以分成：協(xié)作的（分布式對(duì)象間有協(xié)同操作）和非協(xié)作的（處理器獨(dú)立做出決策）。20感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法集中控制的和分散控制的（在動(dòng)態(tài)類型4.2分布式處理機(jī)分配算法下圖顯示了上述負(fù)載分配算法的分類情況21感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法下圖顯示了上述負(fù)載分配算法的分類情4.2分布式處理機(jī)分配算法其他負(fù)載分配算法的分類方法：?jiǎn)蝹€(gè)和多個(gè)應(yīng)用程序

多數(shù)負(fù)載分配算法是針對(duì)單個(gè)應(yīng)用程序。

多應(yīng)用程序情況可以轉(zhuǎn)換成單個(gè)應(yīng)用程序情況。例如，應(yīng)用圖模型時(shí)．對(duì)多應(yīng)用程序的多個(gè)圖可以認(rèn)為是一張圖。

然而，多應(yīng)用程序情況下的進(jìn)程分配遠(yuǎn)復(fù)雜于單個(gè)應(yīng)用程序的情況。多應(yīng)用程序情況下用平均子圖完成時(shí)間作為衡量指標(biāo)，單個(gè)應(yīng)用程序情況下用最小完成時(shí)間作為衡量指標(biāo)。22感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法其他負(fù)載分配算法的分類方法：22感4.2分布式處理機(jī)分配算法非搶占式的和搶占式的

對(duì)非搶占式的負(fù)載分配算法，一個(gè)任務(wù)（進(jìn)程）開(kāi)始執(zhí)行后就不能中斷。在搶占式負(fù)載分配算法中，進(jìn)程可以中斷，并從處理器上移走，以后繼續(xù)執(zhí)行。非自適應(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ù)來(lái)選擇一個(gè)合適的算法。23感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法非搶占式的和搶占式的

對(duì)非搶占式4.2分布式處理機(jī)分配算法

一般來(lái)說(shuō)，設(shè)計(jì)者在設(shè)計(jì)算法時(shí)，需要考慮以下五個(gè)方面的情況：算法是確定式還是啟發(fā)式的。算法是集中式的還是分布式的。算法是最優(yōu)的還是次優(yōu)的。算法是局部的還是全局的。算法是過(guò)載者啟動(dòng)的還是欠載者啟動(dòng)的。24感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法一般來(lái)說(shuō)，設(shè)計(jì)4.2分布式處理機(jī)分配算法確定式算法需要預(yù)先知道進(jìn)程所有的信息:一般，進(jìn)程的信息包括：進(jìn)程的計(jì)算需求文件需求通訊需求等等如果設(shè)計(jì)者能夠獲得所有進(jìn)程的信息，那就可以設(shè)計(jì)出一個(gè)完美的分配方案，并獲得最佳的分配結(jié)果。但只有極少的一些系統(tǒng)可以事先獲得所有進(jìn)程的信息。25感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法確定式算法需要預(yù)先知道進(jìn)程所有的信4.2分布式處理機(jī)分配算法可預(yù)測(cè)系統(tǒng)vs不可預(yù)測(cè)系統(tǒng)在可預(yù)測(cè)系統(tǒng)中，可以通過(guò)合理的近似來(lái)事先得到所有進(jìn)程的信息。例如，在銀行業(yè)、保險(xiǎn)業(yè)、民航定票系統(tǒng)中，每天的情況都基本相似，民航根據(jù)經(jīng)驗(yàn)可以預(yù)測(cè)到早春第一周周一的清晨大約有多少人要從紐約去芝加哥，這樣就保證了確定式算法的可行性。與可預(yù)測(cè)系統(tǒng)相反，有些系統(tǒng)的負(fù)載是完全無(wú)法預(yù)測(cè)的。用戶所做的工作每一個(gè)小時(shí)，甚至每一分鐘都在動(dòng)態(tài)地改變。在這種系統(tǒng)中的處理機(jī)分配不能用一種在數(shù)學(xué)上確定的算法實(shí)現(xiàn)，而需要26感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法可預(yù)測(cè)系統(tǒng)vs不可預(yù)測(cè)系統(tǒng)264.2分布式處理機(jī)分配算法

使用一種稱之為啟發(fā)式的算法。集中式算法需要將系統(tǒng)中所有的信息都收集到某個(gè)機(jī)器上，這會(huì)造成系統(tǒng)不夠魯棒，并且該機(jī)器負(fù)載過(guò)于沉重。因此，一般都采用分布式算法來(lái)實(shí)現(xiàn)處理機(jī)分配。然而，一些集中式算法仍然被采用，原因是沒(méi)有相應(yīng)的分布式算法來(lái)取代它。27感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法使用一種稱之為啟發(fā)式的算法。24.2分布式處理機(jī)分配算法

第三個(gè)設(shè)計(jì)問(wèn)題與前兩個(gè)問(wèn)題有關(guān)，是獲得一個(gè)最優(yōu)解？還是一個(gè)可行的次優(yōu)解？一般來(lái)說(shuō)，采用集中式和分布式算法都能夠得到最優(yōu)解，但得到最優(yōu)解所花費(fèi)的代價(jià)要比得到次優(yōu)解復(fù)雜得多。此外，最優(yōu)解需要收集更多的信息以及進(jìn)行全面復(fù)雜的處理。對(duì)于大多數(shù)分布式系統(tǒng)來(lái)說(shuō)，只要有一個(gè)啟發(fā)、分布、次優(yōu)的處理機(jī)分配算法就可以了。因?yàn)?，要獲得最優(yōu)解實(shí)在是太難了。28感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法第三個(gè)設(shè)計(jì)問(wèn)題與前兩個(gè)問(wèn)題有4.2分布式處理機(jī)分配算法

第四個(gè)設(shè)計(jì)問(wèn)題與遷移策略有關(guān)：當(dāng)一個(gè)新進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)需要決定它是否在創(chuàng)建它的機(jī)器上運(yùn)行。若該機(jī)器繁忙，那這個(gè)新進(jìn)程就必須遷移到其它機(jī)器上去運(yùn)行。對(duì)于是根據(jù)本機(jī)局部信息還是全局信息來(lái)決定新進(jìn)程是否遷移，目前存在著兩種學(xué)派。

1）一種學(xué)派主張簡(jiǎn)單的局部算法：若機(jī)器的負(fù)載低于某個(gè)閥值，那新進(jìn)程就在本地機(jī)器上運(yùn)行；否則，就不允許該進(jìn)程在本地上運(yùn)行。

2）另一種學(xué)派認(rèn)為局部算法太武斷了。最好在決定新進(jìn)程是否在本地機(jī)器上執(zhí)行之前，先收集29感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法第四個(gè)設(shè)計(jì)問(wèn)題與遷移策略有關(guān)4.2分布式處理機(jī)分配算法

其它一些機(jī)器上的負(fù)載信息。比較：

局部算法簡(jiǎn)單，但遠(yuǎn)遠(yuǎn)達(dá)不到最優(yōu)；

而全局算法需要付出巨大的代價(jià)來(lái)?yè)Q取一個(gè)性能稍微好一點(diǎn)的結(jié)果。30感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法其它一些機(jī)器上的負(fù)載4.2分布式處理機(jī)分配算法

最后一個(gè)設(shè)計(jì)問(wèn)題與遷移的目的機(jī)器有關(guān)。一旦決定不允許一個(gè)進(jìn)程在本地機(jī)器上運(yùn)行，那么，遷移算法就必須決定將該進(jìn)程應(yīng)該遷移到一臺(tái)目的機(jī)器上。顯然，遷移算法不能是本地的。它需要通過(guò)獲得其它機(jī)器上的負(fù)載信息來(lái)決定遷移的目的機(jī)器。這些負(fù)載信息可以通過(guò)兩種途徑來(lái)獲得。過(guò)載者啟動(dòng)。欠載者啟動(dòng)。31感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法最后一個(gè)設(shè)計(jì)問(wèn)題與遷移的目的4.2分布式處理機(jī)分配算法過(guò)載者啟動(dòng)：由過(guò)載者來(lái)尋找遷移的目的機(jī)器如圖：一個(gè)機(jī)器超載時(shí)，它向其它機(jī)器發(fā)送求助請(qǐng)求，希望將自己的一些新進(jìn)程遷移到其它機(jī)器上運(yùn)行。欠載者啟動(dòng)：當(dāng)一個(gè)機(jī)器處于空閑狀態(tài)即欠載狀態(tài)時(shí)，由這臺(tái)欠載機(jī)器來(lái)宣布自己可以接收外來(lái)的工作。其的目的就是尋找一臺(tái)可以給自己增加一些額外工作的機(jī)器32感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法過(guò)載者啟動(dòng)：由過(guò)載者來(lái)尋找遷移的目4.2分布式處理機(jī)分配算法不管是過(guò)載者啟動(dòng)的算法還是欠載者啟動(dòng)的算法，不同的算法要采用不同的策略來(lái)決定誰(shuí)收集信息、收集時(shí)間多長(zhǎng)以及如何處理收集的信息。通常，所有的算法都假定每一臺(tái)機(jī)器都知道它自己的負(fù)載，也就是說(shuō)，它可以判斷自己是超載還是欠載，并且能夠告訴其它機(jī)器自己的負(fù)載。然而，度量一臺(tái)機(jī)器是否超載并不象它看上去那樣簡(jiǎn)單。

33感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法不管是過(guò)載者啟動(dòng)的算法還是欠載者啟4.2分布式處理機(jī)分配算法

負(fù)載度量方法1：

以機(jī)器上的進(jìn)程數(shù)量作為機(jī)器的負(fù)載。優(yōu)點(diǎn)：簡(jiǎn)單

原因：只需要計(jì)算機(jī)器上的進(jìn)程數(shù)量缺點(diǎn)：用進(jìn)程數(shù)量的多少來(lái)表示機(jī)器的負(fù)載是不確切的，它幾乎說(shuō)明不了什么問(wèn)題。

原因：即使在一臺(tái)空閑機(jī)器上，仍然會(huì)有一些后臺(tái)監(jiān)視進(jìn)程在運(yùn)行，例如，郵件、新聞、守護(hù)進(jìn)程、窗口管理程序以及其它一些進(jìn)程。因此，34感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法負(fù)載度量方法1：34感謝你的觀4.2分布式處理機(jī)分配算法

對(duì)度量方法1進(jìn)行如下改進(jìn)：

只計(jì)算正在運(yùn)行或已經(jīng)就緒進(jìn)程的數(shù)量。

原因：每一個(gè)正在運(yùn)行或處于就緒狀態(tài)的進(jìn)程都會(huì)給系統(tǒng)增加一定的負(fù)載，即便它是一個(gè)后臺(tái)進(jìn)程。 存在的問(wèn)題：許多后臺(tái)守護(hù)進(jìn)程只是定時(shí)被喚醒，檢查所感興趣的事件是否發(fā)生，如果沒(méi)有，則重新進(jìn)入睡眠狀態(tài)。因此，這類進(jìn)程只給系統(tǒng)帶來(lái)很小的負(fù)載。

35感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法對(duì)度量方法1進(jìn)行如下改進(jìn)：4.2分布式處理機(jī)分配算法

直接使用處理機(jī)利用率：

處理機(jī)繁忙時(shí)間在全部時(shí)間中（繁忙時(shí)間+空閑時(shí)間）所占的比例。一個(gè)利用率為20%的處理機(jī)負(fù)載要比利用率為10%的處理機(jī)大。優(yōu)點(diǎn)：比較合理。原因：兼顧了用戶進(jìn)程和守護(hù)進(jìn)程。36感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法直接使用處理機(jī)利用率：

4.2分布式處理機(jī)分配算法利用率的測(cè)量：設(shè)置一個(gè)定時(shí)器，它周期地中斷處理機(jī)，每次都檢查處理機(jī)的狀態(tài)。并按照上述公式計(jì)算處理機(jī)利用率。它存在的問(wèn)題：

使用定時(shí)器中斷所產(chǎn)生的一個(gè)問(wèn)題就是當(dāng)處理機(jī)內(nèi)核正在執(zhí)行原語(yǔ)時(shí)，它屏蔽了包括定時(shí)器中斷在內(nèi)的所有中斷。當(dāng)原語(yǔ)執(zhí)行時(shí)發(fā)生定時(shí)器中斷，中斷就會(huì)在原語(yǔ)執(zhí)行完畢才能得到響應(yīng)。如果該原語(yǔ)正阻塞前一個(gè)活動(dòng)進(jìn)程，那么，計(jì)算出的處理機(jī)利用率就會(huì)比實(shí)際情況要低得多。

37感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法利用率的測(cè)量：37感謝你的觀看204.2分布式處理機(jī)分配算法

許多理論上的處理機(jī)分配算法都忽略了收集負(fù)載信息以及傳送進(jìn)程的額外開(kāi)銷：若一個(gè)算法將一個(gè)新創(chuàng)建的進(jìn)程傳送到遠(yuǎn)程機(jī)器上運(yùn)行僅使系統(tǒng)性能提高10%左右，那它最好不要這樣做，原因是傳送進(jìn)程的開(kāi)銷足以抵消所提高的性能。一個(gè)好的算法應(yīng)該考慮算法本身所消耗的處理機(jī)時(shí)間、內(nèi)存使用、以及網(wǎng)絡(luò)帶寬等。但很少有算法能做到這一點(diǎn)，因?yàn)樗y了。38感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法許多理論上的處理機(jī)分配算法4.2分布式處理機(jī)分配算法

在處理機(jī)分配算法實(shí)現(xiàn)中還必須考慮復(fù)雜性：事實(shí)上，所有的研究者只分析、模擬或計(jì)算處理機(jī)的利用率、網(wǎng)絡(luò)的使用情況以及響應(yīng)時(shí)間，以此來(lái)衡量他們所提出算法的好壞。很少有人考慮軟件的復(fù)雜性對(duì)系統(tǒng)的性能、正確性和魯棒性所產(chǎn)生的影響。也不會(huì)有人提出了一個(gè)新算法并宣稱它的性能非常好，然后，得出結(jié)論說(shuō)這個(gè)算法不值得使用，因?yàn)樗乃惴ㄐ阅苡锌赡苤皇潜痊F(xiàn)有的算法稍好一點(diǎn)，但在實(shí)現(xiàn)上卻復(fù)雜得多。

39感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法在處理機(jī)分配算法實(shí)現(xiàn)中還必4.2分布式處理機(jī)分配算法

然而，Eager等人在1986年所做的研究使追求低復(fù)雜和最優(yōu)的人們看到了希望。他們研究了三個(gè)算法。在這三個(gè)算法中，所有的機(jī)器都測(cè)量自己的負(fù)載以判斷它是否超載。當(dāng)一個(gè)新進(jìn)程創(chuàng)建時(shí)，創(chuàng)建該進(jìn)程的機(jī)器就會(huì)檢查自己是否超載，如果是，則它就尋找一臺(tái)欠載的遠(yuǎn)程機(jī)器去運(yùn)行該進(jìn)程。這三個(gè)算法的不同之處在于尋找遠(yuǎn)程機(jī)器的方法。

40感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法然而，Eager4.2分布式處理機(jī)分配算法算法1

隨機(jī)地選擇一臺(tái)機(jī)器，并把新創(chuàng)建的進(jìn)程傳送到該機(jī)器上。如果該接收機(jī)器本身也超載，它也同樣隨機(jī)地選擇一臺(tái)機(jī)器并把該進(jìn)程傳送過(guò)去。這個(gè)過(guò)程一直持續(xù)到有一臺(tái)欠載的機(jī)器接收它為止，或者指定計(jì)數(shù)器溢出停止該進(jìn)程的傳送。41感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法算法1

隨機(jī)地選擇一4.2分布式處理機(jī)分配算法算法2

隨機(jī)地選擇一臺(tái)機(jī)器，然后發(fā)送一個(gè)信息給該機(jī)器詢問(wèn)該機(jī)器是超載還是欠載。如果該機(jī)器欠載，它就接收新創(chuàng)建的進(jìn)程；否則，新進(jìn)程的創(chuàng)建機(jī)器繼續(xù)隨機(jī)地選擇一臺(tái)機(jī)器并向其發(fā)送一個(gè)詢問(wèn)消息。這個(gè)過(guò)程一直持續(xù)到找到一臺(tái)欠載機(jī)器為止，或超過(guò)了一定的詢問(wèn)次數(shù)，如果找不到欠載機(jī)器，該新創(chuàng)建的進(jìn)程就只好留在本地機(jī)器上運(yùn)行。

42感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法算法2

隨機(jī)地選擇一4.2分布式處理機(jī)分配算法算法3

給k臺(tái)機(jī)器發(fā)送詢問(wèn)消息，接收這k臺(tái)回送的負(fù)載消息。這個(gè)新進(jìn)程將發(fā)送給負(fù)載最小的機(jī)器，并在它上面運(yùn)行。顯然，如果我們不考慮所有發(fā)送詢問(wèn)負(fù)載消息和傳送進(jìn)程的額外開(kāi)銷，那么，人們會(huì)認(rèn)為算法3的性能最好。事實(shí)上也確實(shí)如此。盡管算法3的性能只比算法2的性能稍好一點(diǎn)，但其復(fù)雜性以及額外開(kāi)銷卻比算法2要大的多。Eager等人認(rèn)為，如果一個(gè)簡(jiǎn)單算法只比復(fù)雜算法在性能上略低一點(diǎn)的話，那么，最好使用簡(jiǎn)單算法。43感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法算法3

給k臺(tái)機(jī)器發(fā)4.2分布式處理機(jī)分配算法

最后一個(gè)實(shí)現(xiàn)問(wèn)題就是穩(wěn)定性:

由于不同的機(jī)器都在異步地運(yùn)行各自的計(jì)算，所以，整個(gè)系統(tǒng)的負(fù)載很少能夠達(dá)到平衡。因此，有時(shí)候會(huì)發(fā)生這樣一種情況：在某個(gè)時(shí)刻，機(jī)器A得到的信息是機(jī)器B的負(fù)載較輕，因而，它就將新創(chuàng)建的進(jìn)程傳送給機(jī)器B。機(jī)器B在收到該進(jìn)程之前負(fù)載又增加了，所以，收到該進(jìn)程后，它發(fā)現(xiàn)機(jī)器A的負(fù)載較輕，于是，它就將該進(jìn)程又傳送給機(jī)器A。這樣造成了某個(gè)可憐的進(jìn)程被來(lái)回傳送的情況。原因是：每一個(gè)機(jī)器上的負(fù)載每時(shí)每刻都在變化。44感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法最后一個(gè)實(shí)現(xiàn)問(wèn)題就是穩(wěn)定性4.2分布式處理機(jī)分配算法靜態(tài)分配算法根據(jù)系統(tǒng)的先驗(yàn)知識(shí)做出決策:運(yùn)行時(shí)負(fù)載不能夠重新分配。算法目標(biāo)：

調(diào)度一個(gè)任務(wù)集合，使它們?cè)诟鱾€(gè)目標(biāo)PE上有最小的執(zhí)行時(shí)間。設(shè)計(jì)算法時(shí)的三個(gè)主要的因素：處理器互連任務(wù)劃分（粒度決策）任務(wù)分配45感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法靜態(tài)分配算法根據(jù)系統(tǒng)的先驗(yàn)知識(shí)做出4.2分布式處理機(jī)分配算法

靜態(tài)分配問(wèn)題即便在簡(jiǎn)單地對(duì)計(jì)算開(kāi)銷和通信開(kāi)銷做某種假設(shè)以后，依然是一個(gè)NP完全問(wèn)題。因此，可以利用數(shù)學(xué)工具如圖、啟發(fā)式規(guī)則來(lái)得到次優(yōu)的解。通常，用圖模型表示任務(wù)和PE結(jié)構(gòu)?？梢杂萌蝿?wù)優(yōu)先圖或者任務(wù)交互作用圖對(duì)任務(wù)集合建模。46感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法靜態(tài)分配問(wèn)題4.2分布式處理機(jī)分配算法

任務(wù)優(yōu)先圖又稱為有向無(wú)環(huán)圖（DAG）：

如圖，每個(gè)鏈接：定義任務(wù)間的優(yōu)先關(guān)系節(jié)點(diǎn)上的標(biāo)記：表示任務(wù)執(zhí)行時(shí)間鏈接上的標(biāo)記：表示任務(wù)完成后啟動(dòng)后續(xù)任務(wù)所需的時(shí)間間隔47感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)優(yōu)先圖又稱為有向無(wú)環(huán)圖（4.2分布式處理機(jī)分配算法

任務(wù)交互作用圖：如圖：鏈接：定義兩個(gè)任務(wù)間的相互關(guān)系每個(gè)鏈接賦予一對(duì)數(shù)：表示這兩個(gè)任務(wù)在同一個(gè)PE上時(shí)的通信開(kāi)銷和在不同PE上時(shí)的通信開(kāi)銷。48感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)交互作用圖：48感謝你的4.2分布式處理機(jī)分配算法

任務(wù)劃分的粒度：

一個(gè)給定任務(wù)劃分的粒度定義是任務(wù)分解中影響通信開(kāi)銷的所有單元的平均尺度。根據(jù)數(shù)據(jù)單元的大小，算法可以分成。細(xì)粒度：數(shù)據(jù)單元小粗粒度：數(shù)據(jù)單元大中粒度：介于上述兩者之間粒度的大?。?/p>

1）若太大，會(huì)降低并行度，因?yàn)闈撛诘牟⑿腥蝿?wù)可能被劃分進(jìn)同一個(gè)任務(wù)而分配給一個(gè)處理器。

2）若太小，進(jìn)程切換和通信的開(kāi)銷就會(huì)增加。49感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)劃分的粒度：

4.2分布式處理機(jī)分配算法

任務(wù)劃分的一個(gè)主要目標(biāo)：

盡可能消除處理器間通信引起的開(kāi)銷。可以使用三種方法：水平或者垂直劃分。

主要思想是在給定的任務(wù)優(yōu)先圖中垂直或者水平劃分。關(guān)鍵路徑（最長(zhǎng)路徑）的概念常常在垂直劃分中使用。水平劃分把給定的任務(wù)分成若干層，任務(wù)的優(yōu)先級(jí)由它們所在的層次決定50感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)劃分的一個(gè)主要目標(biāo)：

4.2分布式處理機(jī)分配算法通信延遲最小劃分：

主要思想是把通信頻繁的節(jié)點(diǎn)歸成一類。然而，這些需要通信的任務(wù)分配在一個(gè)處理器上會(huì)喪失任務(wù)間的并發(fā)性。

有的研究者認(rèn)為：如果減小通信延遲的好處抵銷了并行任務(wù)串行化的損失，就采用通信延遲最小劃分。

可以把一個(gè)劃分問(wèn)題轉(zhuǎn)換成一個(gè)網(wǎng)絡(luò)流問(wèn)題，將在后面的小節(jié)中討論。51感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法通信延遲最小劃分：

主4.2分布式處理機(jī)分配算法任務(wù)復(fù)制，這是任務(wù)劃分的一個(gè)可選方法：

主要思想是通過(guò)在PE上復(fù)制任務(wù)來(lái)降低通信開(kāi)銷。這個(gè)方法保留了任務(wù)原有的并行性；但是存儲(chǔ)空間要求和同步開(kāi)銷增加了。

可以利用任務(wù)復(fù)制來(lái)達(dá)到容錯(cuò)性，可以實(shí)現(xiàn)無(wú)錯(cuò)調(diào)度以保證處理器出現(xiàn)錯(cuò)誤時(shí)最后計(jì)算結(jié)果正確。52感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)復(fù)制，這是任務(wù)劃分的一個(gè)可選方4.2分布式處理機(jī)分配算法

任務(wù)劃分被稱做任務(wù)聚類，它強(qiáng)調(diào)在給定的圖模型中對(duì)小任務(wù)分類。任務(wù)劃分把圖當(dāng)做一個(gè)整體，劃分成不同的類（顆粒）。不論任務(wù)劃分還是任務(wù)聚類，都生成一個(gè)顆粒集合。通常顆粒的數(shù)目等于處理器的個(gè)數(shù)，以此簡(jiǎn)化下一步的任務(wù)分配程序。

53感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)劃分被稱做4.2分布式處理機(jī)分配算法

任務(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í)間概念下，有些映射比較好。54感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)分配就是4.2分布式處理機(jī)分配算法關(guān)于Gp的典型假設(shè)：

存儲(chǔ)器容量無(wú)限。每個(gè)PE有相同的處理能力。忽略網(wǎng)絡(luò)擁塞，雖然通信進(jìn)程間的距離是影響通信延遲的因素。注意：任務(wù)調(diào)度不必要一定分兩個(gè)步驟做，即任務(wù)劃分和任務(wù)分配。分兩步的方法只是為了簡(jiǎn)化原本是NP完全的調(diào)度過(guò)程。

55感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法關(guān)于Gp的典型假設(shè)：55感謝你的4.2分布式處理機(jī)分配算法

假定一個(gè)進(jìn)程集合P={P1,P2,P3,…Pn}，在一系列同樣的處理器上執(zhí)行。任務(wù)優(yōu)先圖：定義P上的偏序＜關(guān)系，構(gòu)成(P,<)關(guān)系集，并用G=(V,A)描述，其中，V是頂點(diǎn)的集合，表示進(jìn)程集；A是弧集合，表示進(jìn)程間的優(yōu)先關(guān)系。A中的一個(gè)鏈接表示為(u,v),u和v是V中的兩個(gè)連接進(jìn)程（節(jié)點(diǎn)）。56感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法假定一個(gè)進(jìn)程集合4.2分布式處理機(jī)分配算法對(duì)每個(gè)節(jié)點(diǎn)和鏈接都定義有代價(jià)函數(shù)w：W(u)∈(0,∞)是節(jié)點(diǎn)u的代價(jià)，u屬于V;W(u,v)=(l,l’)是鏈接(u,v)的代價(jià)，其中

l’：同一處理器內(nèi)的通信代價(jià)（若u和v被分配在同一個(gè)處理器上）

l：處理器間的通信代價(jià)（若u和v被分配在不同處理器上）。

57感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法對(duì)每個(gè)節(jié)點(diǎn)和鏈接都定義有代價(jià)函數(shù)w4.2分布式處理機(jī)分配算法任務(wù)優(yōu)先關(guān)系圖模型中不考慮處理器互連：假設(shè)每對(duì)處理器間的通信延遲是一個(gè)固定數(shù)值事實(shí)上，處理器通信延遲在l中得到了體現(xiàn)。通常，處理器內(nèi)部通信代價(jià)l’相對(duì)于處理器間通信代價(jià)l要小。因此可以忽略，

記做W(u,v)=l。58感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法任務(wù)優(yōu)先關(guān)系圖模型中不考慮處理器互4.2分布式處理機(jī)分配算法甘特圖能夠最有效描述進(jìn)程對(duì)處理器的分配情況:甘特圖以處理器為縱坐標(biāo)，時(shí)間為橫坐標(biāo)。圖中的每個(gè)方塊表示進(jìn)程在某個(gè)系統(tǒng)中的開(kāi)始時(shí)間，持續(xù)時(shí)間和結(jié)束時(shí)間。處理器內(nèi)的時(shí)間延遲和處理器間的時(shí)間延遲都能夠在圖中體現(xiàn)。59感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法甘特圖能夠最有效描述進(jìn)程對(duì)處理器的4.2分布式處理機(jī)分配算法圖a顯示了一個(gè)實(shí)例的任務(wù)優(yōu)先圖圓圈中的數(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（沒(méi)有給出處理器內(nèi)的通信代價(jià)）。圖b是對(duì)處理器P1,P2的一個(gè)調(diào)度結(jié)果。本例中，兩個(gè)處理器間的通信發(fā)生在有1個(gè)單位通信延遲的T2

T4和有2個(gè)單位通信延遲的T4

T5。總的執(zhí)行時(shí)間是12。(a)(b)60感謝你的觀看2019年7月194.2分布式處理機(jī)分配算法圖a顯示了一個(gè)實(shí)例的任務(wù)優(yōu)先圖(a基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

通信延遲的影響通信延遲使調(diào)度算法大大地變復(fù)雜。例：圖b,c,d給出了針對(duì)a中任務(wù)優(yōu)先圖的三種不同的調(diào)度對(duì)于c和d，若通信延遲d大于T2的執(zhí)行時(shí)間，圖c的調(diào)度就比圖d要好?？梢哉f(shuō)，若通信延遲太大的話，所有任務(wù)分配在一個(gè)處理器上是比較合適的。(a)(b)(c)(d)61感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

通信延遲的影響通信延遲使調(diào)度算法大(a)(b)(c)(d)基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

通信延遲的影響通常總是嘗試盡量增加并行度，同時(shí)盡可能降低通信延遲。然而在多數(shù)時(shí)間這兩個(gè)目標(biāo)是互相矛盾的。因此需要某種程度折衷。

有時(shí)可以使用任務(wù)復(fù)制的方法減少通信需求。顯然，由于通過(guò)任務(wù)復(fù)制而避免了處理器間的通信，圖b的結(jié)果是最好的。62感謝你的觀看2019年7月19(a)(b)(c)(d)基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

通信延遲的基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性與非線性調(diào)度前面提到了任務(wù)劃分（又稱做任務(wù)聚類）中的粒度問(wèn)題，是把指定應(yīng)用程序的任務(wù)分成一個(gè)個(gè)任務(wù)類。通常類的數(shù)目應(yīng)等于處理器個(gè)數(shù)若至少有一個(gè)類中包含兩個(gè)獨(dú)立的任務(wù)，則分類是非線性的；否則，分類就是線性的。右圖分別是三個(gè)進(jìn)程的線性調(diào)度和非線性調(diào)度。63感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性與非線性調(diào)度前面提到了任務(wù)劃分基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

粒度的定義一個(gè)任務(wù)優(yōu)先圖可以認(rèn)為是許多分叉和合并操作的集合，如右圖所示為了判別好的分類算法，引入了對(duì)每個(gè)分叉或者合并的粒度的概念。右圖中，分叉x（合并x）的粒度是：=最小的進(jìn)程代價(jià)/最大的連接代價(jià)給定任務(wù)優(yōu)先圖G的粒度是：64感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

粒度的定義一個(gè)任務(wù)優(yōu)先圖可以認(rèn)為是基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

粒度的定義如果

合并或分叉x就是粗粒度的；

否則，就是細(xì)粒度的。下圖中的任務(wù)劃分是粗粒度，因?yàn)樽钚〉倪M(jìn)程代價(jià)大于最大的連接代價(jià)(g(x)=2/1=2)。65感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

粒度的定義如果

合并或分叉x就是粗基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性分類與非線性分類的比較例中圖a的線性分類的執(zhí)行時(shí)間是7。圖b中非線性分類的執(zhí)行時(shí)間是9。66感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性分類與非線性分類的比較例中圖a基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性分類與非線性分類的比較如果把W(T1,T3)和W(T1,T2)改成4，相應(yīng)的圖變成細(xì)粒度分叉，非線性分類的執(zhí)行時(shí)間是9，優(yōu)于執(zhí)行時(shí)間是10的線性分類。67感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

線性分類與非線性分類的比較如果把W基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

算法實(shí)例：兩種最優(yōu)調(diào)度算法兩種有約束的調(diào)度問(wèn)題，它們有多項(xiàng)式時(shí)間的執(zhí)行復(fù)雜度。兩種方法都假設(shè)通信代價(jià)可以忽略和優(yōu)先圖中每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間是一樣的（一個(gè)時(shí)間單元）。具體限制如下：在第一個(gè)有約束的調(diào)度問(wèn)題中，優(yōu)先圖是一棵樹(shù)。在第二個(gè)有約束的調(diào)度問(wèn)題中，只有兩個(gè)處理器可用兩種調(diào)度算法都是最高優(yōu)先級(jí)優(yōu)先的方法，也就是說(shuō)，通過(guò)節(jié)點(diǎn)的等級(jí)（優(yōu)先級(jí)）來(lái)選擇節(jié)點(diǎn)。68感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

算法實(shí)例：兩種最優(yōu)調(diào)度算法兩種有基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

案例1：優(yōu)先級(jí)定義案例1中節(jié)點(diǎn)u的等級(jí)是它到根節(jié)點(diǎn)的距離加1注意：節(jié)點(diǎn)的等級(jí)越高，它的優(yōu)先級(jí)就越高。當(dāng)若干個(gè)節(jié)點(diǎn)有相同的等級(jí)時(shí)，所有先導(dǎo)節(jié)點(diǎn)都已執(zhí)行的節(jié)點(diǎn)被第一個(gè)選中；如果還有若干個(gè)節(jié)點(diǎn)符合上述條件，則做隨機(jī)選擇。69感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

案例1：優(yōu)先級(jí)定義案例1中節(jié)點(diǎn)u的

優(yōu)先圖舉例右圖顯示了一個(gè)樹(shù)結(jié)構(gòu)的優(yōu)先圖T1,T2,T3和T4在等級(jí)5T5,T6和T7在等級(jí)4T8和T9在等級(jí)3T10,T11和T12在等級(jí)2T13在等級(jí)1等級(jí)5的任務(wù)有最高優(yōu)先級(jí)，

等級(jí)1的任務(wù)優(yōu)先級(jí)最低。

同一等級(jí)的任務(wù)有相同優(yōu)先級(jí)。70感謝你的觀看2019年7月19

優(yōu)先圖舉例右圖顯示了一個(gè)樹(shù)結(jié)構(gòu)的優(yōu)先圖70感謝你的觀看20算法案例1：

任務(wù)分配舉例三個(gè)處理器上的最優(yōu)調(diào)度，如右下圖所示從第一個(gè)時(shí)間槽開(kāi)始根據(jù)優(yōu)先級(jí)進(jìn)行分配。有先后關(guān)系的任務(wù)不能分配在同一個(gè)時(shí)問(wèn)槽中。例如T6必須被分配在T4后面的時(shí)間槽中。71感謝你的觀看2019年7月19算法案例1：

任務(wù)分配舉例三個(gè)處理器上的最優(yōu)調(diào)度，如右下圖所算法案例1：

分配算法的實(shí)現(xiàn)：就緒隊(duì)列定義就緒隊(duì)列被用來(lái)高效的實(shí)現(xiàn)上述調(diào)度算法就緒隊(duì)列包括所有節(jié)點(diǎn)，它們的先導(dǎo)節(jié)點(diǎn)都已經(jīng)執(zhí)行完畢根據(jù)優(yōu)先級(jí)從就緒隊(duì)列中選擇后續(xù)節(jié)點(diǎn)執(zhí)行。注意，一個(gè)節(jié)點(diǎn)被調(diào)度時(shí)，就緒隊(duì)列就必須更新。72感謝你的觀看2019年7月19算法案例1：

分配算法的實(shí)現(xiàn)：就緒隊(duì)列定義就緒隊(duì)列被用來(lái)高效算法案例1：

就緒隊(duì)列舉例：圖9-8中，

為方便起見(jiàn)，隊(duì)列中的任務(wù)按優(yōu)先級(jí)排序初始就緒隊(duì)列是{T1,T2,T3,T4,T5,T7,T9,T10,T12}

隊(duì)列中的前三個(gè)任務(wù)分配在第一

個(gè)時(shí)間槽就緒隊(duì)列變成{T4,T5,T7,T9,T10,

T12}。

T4,T5和T7分配在時(shí)間槽273感謝你的觀看2019年7月19算法案例1：

就緒隊(duì)列舉例：圖9-8中，

為方便起見(jiàn)，隊(duì)算法案例1：

就緒隊(duì)列舉例：T6加入就緒隊(duì)列{T6,T9,T10,T12}。

再將隊(duì)列中前三個(gè)任務(wù)分配給下一個(gè)時(shí)間槽T8加入就緒隊(duì)列{T8,T12}。

T8和T12都分配在時(shí)間槽4，T11加入就緒隊(duì)列。

T11分配在時(shí)間槽5，T13加入就緒隊(duì)列，

并在時(shí)間槽6執(zhí)行。74感謝你的觀看2019年7月19算法案例1：

就緒隊(duì)列舉例：T6加入就緒隊(duì)列{T6,T9,T基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

案例2：優(yōu)先級(jí)定義案例2假定有兩個(gè)處理器。優(yōu)先圖中不同節(jié)點(diǎn)的等級(jí)不相同。下面的算法生成一個(gè)優(yōu)先圖：假定有k個(gè)終止節(jié)點(diǎn)（無(wú)后續(xù)節(jié)點(diǎn)），從1到k依次標(biāo)記這些節(jié)點(diǎn)。令S是沒(méi)有被分配（未被標(biāo)記）的節(jié)點(diǎn)的集合，并且其中每個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)都已被標(biāo)記，從中選一個(gè)標(biāo)記成i。方法如下：令lex(u)是u的所有直接后續(xù)節(jié)點(diǎn)的標(biāo)記的升序排列。

若對(duì)S中所有u’(u’≠u),lex(u)<lex(u’)（字典序），那么u可以賦予i。75感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

案例2：優(yōu)先級(jí)定義案例2假定有兩個(gè)案例2：

優(yōu)先圖舉例圖9-9表示一個(gè)優(yōu)先圖，每個(gè)節(jié)點(diǎn)都用上面的方法進(jìn)行了標(biāo)記。節(jié)點(diǎn)的標(biāo)記可以當(dāng)做它的優(yōu)先級(jí)任務(wù)按照優(yōu)先級(jí)升序排序?yàn)椋?/p>

T1,T2,T3,T4,T5,T6,T11,T8,T7,T10,T9注意終止任務(wù)T1,T2,T3的順序是隨機(jī)選

擇的，例中它們的優(yōu)先級(jí)分別是1,2,3

T4的直接后續(xù)節(jié)點(diǎn)是T1和T2，

因此lex(T4)=(1,2)。

顯然lex(T4)<Iex(T5)

所以T4的標(biāo)記是4，T5的標(biāo)記是5。76感謝你的觀看2019年7月19案例2：

優(yōu)先圖舉例圖9-9表示一個(gè)優(yōu)先圖，每個(gè)節(jié)點(diǎn)都用上案例2：

任務(wù)分配舉例圖9-6b是甘特圖表示的最優(yōu)調(diào)度。77感謝你的觀看2019年7月19案例2：

任務(wù)分配舉例圖9-6b是甘特圖表示的最優(yōu)調(diào)度。7基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

任務(wù)圖定義第二個(gè)任務(wù)調(diào)度模型是利用任務(wù)相互關(guān)系圖和進(jìn)程的集合來(lái)表示應(yīng)用程序。任務(wù)相互關(guān)系圖由無(wú)向圖Gt(Vt,Et)表示

Vt：是進(jìn)程的集合

Et：是邊的集合， 其中每條邊表示兩個(gè)通信進(jìn)程間的相互作用關(guān)系，用相關(guān)兩個(gè)進(jìn)程的通信代價(jià)標(biāo)記（不是優(yōu)先關(guān)系）78感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

任務(wù)圖定義第二個(gè)任務(wù)調(diào)度模型基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

處理器圖定義與任務(wù)優(yōu)先圖模型不同的是處理器間通信在任務(wù)相互關(guān)系圖調(diào)度模型中有重要作用。特別地，處理器圖由Gp(Vp,Ep)表示 頂點(diǎn)集Vp中每個(gè)元素是一個(gè)處理器

邊集Ep中每個(gè)元素是一個(gè)通信信道一般來(lái)說(shuō)，|Vt|<=|Vp|，因此可以假設(shè)任務(wù)劃分已經(jīng)完成。然后，進(jìn)行分配M:Vt

Vp以及執(zhí)行時(shí)間的估計(jì)。注意，w(u)和w(u,v)分別表示節(jié)點(diǎn)u和鏈接(u,v)的代價(jià)。79感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

處理器圖定義與任務(wù)優(yōu)先圖模型不基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

負(fù)載定義處理器p的計(jì)算負(fù)載，p∈Vp:通信負(fù)載：在一個(gè)應(yīng)用程序中總的計(jì)算和通信量是：80感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

負(fù)載定義處理器p的計(jì)算負(fù)載，p基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

負(fù)載定義程序總的執(zhí)行時(shí)間大概是：其中，α依據(jù)每個(gè)PE的執(zhí)行速度，β依據(jù)每個(gè)通信信道的通信速度和通信進(jìn)程間的距離。注意如果兩個(gè)進(jìn)程u和v在Gt鄰接，它們?cè)贕p的映像（M的映像結(jié)果）可能鄰接也可能不鄰接。理想的情況下，所有通信進(jìn)程被分配在鄰接的處理器上，以此減少處理器間通信。81感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

負(fù)載定義程序總的執(zhí)行時(shí)間大概是基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)注意通常兩個(gè)進(jìn)程不應(yīng)該映射在一個(gè)處理器上。任務(wù)分類時(shí)這兩個(gè)進(jìn)程應(yīng)當(dāng)分類進(jìn)同一個(gè)類。評(píng)估映射質(zhì)量的一個(gè)指標(biāo)是

映射的勢(shì)，即

任務(wù)圖Gt中的邊映射到處理器圖Gp的邊的數(shù)目。也是Gt中映射到Gp中鄰接處理器的通信進(jìn)程對(duì)的數(shù)目。映射的勢(shì)不能超過(guò)Gt中的鏈接數(shù)。如果一個(gè)映射的勢(shì)最大，它就是一個(gè)理想映射82感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)注意通常兩個(gè)進(jìn)程不應(yīng)該基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)舉例下圖中，左邊是一個(gè)任務(wù)相互關(guān)系圖，右邊是一個(gè)具有9個(gè)處理器的處理器圖。右圖顯示了任務(wù)與處理器的映射關(guān)系，該映射的勢(shì)是8（13條邊）。13-5條虛邊=883感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)舉例下圖中，左邊是一個(gè)基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)有時(shí)映射的勢(shì)可能不能準(zhǔn)確地反映映射的質(zhì)量。比如，它不能區(qū)分下面兩種情況：a）兩個(gè)通信進(jìn)程被映射到兩個(gè)處理器上，這兩個(gè)處理器在處理器圖中的距離是k(k>2)，b）兩個(gè)通信進(jìn)程被映射到兩個(gè)處理器上，這兩個(gè)處理器在處理器圖中的距離是2。需要圖嵌入技巧來(lái)區(qū)分上面兩種情況。84感謝你的觀看2019年7月19基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

映射的勢(shì)有時(shí)映射的勢(shì)可能不能準(zhǔn)4.2.5處理機(jī)分配算法舉例

基于圖論的確定性分配算法假定：每個(gè)進(jìn)程都知道

1）所需的處理機(jī)

2）所要求的內(nèi)存

3）知道系統(tǒng)中任意一對(duì)進(jìn)程間的平均通信量 若系統(tǒng)中處理機(jī)的數(shù)目k比進(jìn)程數(shù)少，那系統(tǒng)中的一些處理機(jī)就必須被分配多個(gè)進(jìn)程。基于圖論的確定性算法

保證在系統(tǒng)網(wǎng)絡(luò)通信量最小的條件下對(duì)處理機(jī)進(jìn)行分配。85感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

基于圖論的確定性分配算法假基于圖論的確定性分配算法

系統(tǒng)的帶權(quán)圖表示系統(tǒng)的帶權(quán)圖表示：

系統(tǒng)可以被表示圖G(V,E)，

V中的每個(gè)節(jié)點(diǎn)表示一個(gè)進(jìn)程

E中的每條邊表示兩個(gè)進(jìn)程需要通信，

邊上面的數(shù)字表示兩個(gè)進(jìn)程之間的通信量。從數(shù)學(xué)角度看，處理機(jī)分配問(wèn)題已經(jīng)被簡(jiǎn)化為：

在一定的約束條件下（例如，每一個(gè)子圖總的處理機(jī)和內(nèi)存需求量不超過(guò)某一個(gè)閥值）將圖分割成k個(gè)不相連的子圖。

算法的目標(biāo)就是在滿足所有限制條件下，找到一個(gè)分割方法，使得分割后各子圖之間的通信量之和最小。86感謝你的觀看2019年7月19基于圖論的確定性分配算法

系統(tǒng)的帶權(quán)圖表示系統(tǒng)的帶權(quán)圖表示：基于圖論的確定性分配算法

分割舉例下圖表示了一個(gè)圖的兩種不同的分割方法，并得到了兩個(gè)不同的通信量。CPU1CPU2CPU3CPU1CPU2CPU387感謝你的觀看2019年7月19基于圖論的確定性分配算法

分割舉例下圖表示了一個(gè)圖的兩種不同基于圖論的確定性分配算法

分割舉例a中，系統(tǒng)圖被分割為：A,E,G在處理機(jī)1上B,F,H在處理機(jī)2上C,D,I在處理機(jī)3上整個(gè)網(wǎng)絡(luò)通信量

= 被虛線分割開(kāi)的邊上

的權(quán)值之和

= 30。3+2+4+4=132+8+5+2=1788感謝你的觀看2019年7月19基于圖論的確定性分配算法

分割舉例a中，系統(tǒng)圖被分割為：3+基于圖論的確定性分配算法

分割舉例b中顯示的分割得到的通信量之和為28如果它滿足所有對(duì)內(nèi)存和處理機(jī)的限制，那它就是一個(gè)比較好的分割，因?yàn)樗蟮?/p>

網(wǎng)絡(luò)通信量之和較小。3+2+4+4=133+5+5+2=1589感謝你的觀看2019年7月19基于圖論的確定性分配算法

分割舉例b中顯示的分割得到的通信量4.2.5處理機(jī)分配算法舉例

集中式分配算法：up-down圖論算法的局限性在于：

需要預(yù)先知道所有信息，這在一般情況下是辦不到的下面介紹一個(gè)不需要預(yù)先知道所有信息的集中式啟發(fā)式算法?！吧仙?下降”(up-down)算法

MutkaandLivny在1987年提出的。90感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

集中式分配算法：up-dow4.2.5處理機(jī)分配算法舉例

上升-下降算法的基本思想上升-下降算法的基本思想是

1）由一個(gè)協(xié)調(diào)器來(lái)維護(hù)一張使用情況表每個(gè)工作站在表中都對(duì)應(yīng)著一項(xiàng)（初始值為零）當(dāng)發(fā)生一個(gè)重要事件時(shí)，就給協(xié)調(diào)器發(fā)送一個(gè)消息來(lái)更新使用情況表。

2）協(xié)調(diào)器根據(jù)使用情況表來(lái)分配處理機(jī)。分配時(shí)機(jī)：調(diào)度事件發(fā)生時(shí)典型的調(diào)度事件：申請(qǐng)?zhí)幚頇C(jī)

處理機(jī)進(jìn)入空閑狀態(tài)

發(fā)生時(shí)鐘中斷91感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法的基本思想上升4.2.5處理機(jī)分配算法舉例

上升-下降算法的目標(biāo)集中式分配算法的目標(biāo)：

讓每個(gè)工作站公平地使用系統(tǒng)處理機(jī)的計(jì)算能力,而不是盡可能地提高處理機(jī)的利用率。

原因：

其它算法有可能在給一個(gè)用戶分配處理機(jī)時(shí)，為了讓每一臺(tái)處理機(jī)都繁忙起來(lái)而將所有處理機(jī)都分配給該用戶。本集中式算法能夠避免這種情況的發(fā)生。92感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法的目標(biāo)集中式4.2.5處理機(jī)分配算法舉例

上升-下降算法：新進(jìn)程當(dāng)創(chuàng)建一個(gè)進(jìn)程時(shí)，如果創(chuàng)建該進(jìn)程的機(jī)器認(rèn)為該進(jìn)程應(yīng)該在其它機(jī)器上運(yùn)行，它就向協(xié)調(diào)器申請(qǐng)分配處理機(jī)。如果有可分配的處理機(jī)時(shí)，協(xié)調(diào)器就分配一個(gè)處理機(jī)，否則，協(xié)調(diào)器就暫時(shí)拒絕該處理機(jī)的申請(qǐng)，并記錄這個(gè)請(qǐng)求。93感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法：新進(jìn)程當(dāng)創(chuàng)建4.2.5處理機(jī)分配算法舉例

上升-下降算法：罰分的變化增加：

當(dāng)一個(gè)工作站上的進(jìn)程正在其它機(jī)器上運(yùn)行時(shí)，它的罰分每秒鐘增加一個(gè)固定值。這個(gè)罰分將加在使用情況表中該工作站所對(duì)應(yīng)的項(xiàng)上。減少情況1：每當(dāng)工作站上的進(jìn)程需要在其它機(jī)器上運(yùn)行的請(qǐng)求被拒絕時(shí)，該工作站在使用情況表中所對(duì)應(yīng)項(xiàng)上的罰分就會(huì)減少一個(gè)固定值。減少情況2：當(dāng)沒(méi)有等待的處理機(jī)分配請(qǐng)求，并且處理機(jī)也未被使用時(shí)，使用情況表中該處理機(jī)所對(duì)應(yīng)項(xiàng)上的罰分就會(huì)每秒鐘減去一個(gè)值，直到為0。94感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法：罰分的變化增4.2.5處理機(jī)分配算法舉例

上升-下降算法：罰分的取值如圖，由于罰分一會(huì)兒上升，一會(huì)兒下降，算法由此得名。使用情況表中的罰分可以為正數(shù)、零和負(fù)數(shù)。正數(shù)表示對(duì)應(yīng)工作站上的

用戶是在使用系統(tǒng)資源負(fù)數(shù)表示該工作站需

要系統(tǒng)資源。零表示介于兩者之間。95感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法：罰分的取值如4.2.5處理機(jī)分配算法舉例

上升-下降算法分析集中式分配算法的啟發(fā)性在于當(dāng)一個(gè)處理機(jī)變成空閑狀態(tài)時(shí)，首先分配給罰分最低正在等待處理機(jī)的申請(qǐng)。因此，等待時(shí)間最長(zhǎng)，沒(méi)有使用處理機(jī)的請(qǐng)求將優(yōu)先得到響應(yīng)。實(shí)際上，若一個(gè)用戶已使用了一段時(shí)間的系統(tǒng)資源，另一個(gè)用戶剛開(kāi)始申請(qǐng)一個(gè)進(jìn)程的運(yùn)行，那負(fù)載較輕的后者要比負(fù)載較重的前者要優(yōu)先得到資源集中式啟發(fā)式算法的特征即公平地分配系統(tǒng)處理機(jī)。模擬研究表明，在各種情況下，該算法都具有較好的性能。96感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

上升-下降算法分析集中式分配4.2.5處理機(jī)分配算法舉例

層次分配算法“上升-下降”作為一個(gè)集中式算法無(wú)法適用于大型分布式系統(tǒng)。原因：

協(xié)調(diào)器將成為整個(gè)系統(tǒng)的瓶頸口，此外，協(xié)調(diào)器的崩潰將造成整個(gè)系統(tǒng)無(wú)法進(jìn)行處理機(jī)的分配。上述問(wèn)題可以通過(guò)使用層次分配算法來(lái)解決。層次分配算法既保持了集中式分配算法的簡(jiǎn)單性，又能更好地適應(yīng)于大型分布式系統(tǒng)。97感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法“上升-下降”4.2.5處理機(jī)分配算法舉例

層次分配算法層次分配算法將所有處理機(jī)以一種與物理拓?fù)浣Y(jié)構(gòu)無(wú)關(guān)的方式組織成一個(gè)邏輯分層結(jié)構(gòu)。這種邏輯分層結(jié)構(gòu)與公司、軍隊(duì)、大學(xué)等現(xiàn)實(shí)世界中人的層次組成結(jié)構(gòu)一樣。例如，可以將一些機(jī)器看作為工人，而將另一些機(jī)器看作為工頭。98感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法層次分配算法將所4.2.5處理機(jī)分配算法舉例

層次分配算法例如：對(duì)于每一組k個(gè)教師來(lái)說(shuō)，分配給一個(gè)系主任的任務(wù)是檢查觀察誰(shuí)正忙碌，誰(shuí)正空閑。如果系統(tǒng)很大，那就需要更多的管理者。于是，有些機(jī)器將作為院長(zhǎng)。每一個(gè)院長(zhǎng)管理若干個(gè)系主任。如果院長(zhǎng)較多，則設(shè)置一個(gè)校長(zhǎng)來(lái)管理院長(zhǎng)。這種層次關(guān)系可以進(jìn)一步擴(kuò)展下去，并且所需要的層次隨著教師的數(shù)目成對(duì)數(shù)級(jí)增長(zhǎng)。由于每一個(gè)處理機(jī)只需要與一個(gè)上級(jí)和若干個(gè)下屬進(jìn)行通信，所以就可以對(duì)系統(tǒng)的信息流進(jìn)行管理。99感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法例如：99感謝你4.2.5處理機(jī)分配算法舉例

層次分配算法：崩潰的解決方法1當(dāng)一個(gè)系主任，或者更嚴(yán)重地，一個(gè)院長(zhǎng)停止了工作（即崩潰了），系統(tǒng)將怎么辦？一種方法就是 由崩潰院長(zhǎng)所管轄的一個(gè)系主任來(lái)接替該院長(zhǎng)職位

這個(gè)院長(zhǎng)職位

1）可以由它下級(jí)選舉產(chǎn)生

2）也可以由同級(jí)院長(zhǎng)們選舉產(chǎn)生

3）還可以由它的上級(jí)來(lái)任命。100感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法：崩潰的解決方法4.2.5處理機(jī)分配算法舉例

層次分配算法：最高委員會(huì)為了避免單個(gè)管理者在層次樹(shù)的最頂層（造成系統(tǒng)不堅(jiān)定），可以象下圖那樣 去掉樹(shù)的根節(jié)點(diǎn)，最上層組成一個(gè)委員會(huì)來(lái)作為最高決策機(jī)構(gòu)。 當(dāng)委員會(huì)中的一個(gè)成員不工作了，其他人員將在下一層中選出某一個(gè)成員來(lái)代替。院長(zhǎng)委員會(huì)院長(zhǎng)系主任

教師101感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法：最高委員會(huì)為了4.2.5處理機(jī)分配算法舉例

層次分配算法：結(jié)構(gòu)分析結(jié)構(gòu)分析：可行性：

盡管這種層次結(jié)構(gòu)并不是真正分布式的，但它卻是可行的，并且實(shí)踐證明它是一個(gè)較好的結(jié)構(gòu)。自重構(gòu)性：

特別的是，這種系統(tǒng)可以自重構(gòu)，并能夠容忍被管理者或管理者的突發(fā)性崩潰，而不會(huì)產(chǎn)生任何長(zhǎng)期的影響。102感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法：結(jié)構(gòu)分析結(jié)構(gòu)分4.2.5處理機(jī)分配算法舉例

層次分配算法：處理器預(yù)定算法中，一個(gè)處理機(jī)只能分配一個(gè)進(jìn)程。若一個(gè)作業(yè)產(chǎn)生S個(gè)進(jìn)程，系統(tǒng)必須為它分配S個(gè)處理機(jī)。作業(yè)可以在層次樹(shù)上的任何一層次上創(chuàng)建。每一個(gè)管理者跟蹤并記錄它轄區(qū)內(nèi)有多少個(gè)處理機(jī)可用。如果有足夠的處理機(jī)可供使用，那它將預(yù)定R個(gè)處理機(jī)，但R≥S必須成立，因?yàn)檫@種估計(jì)不一定準(zhǔn)確，有些機(jī)器可能已經(jīng)關(guān)機(jī)。103感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法：處理器預(yù)定算法4.2.5處理機(jī)分配算法舉例

層次分配算法：處理器預(yù)定如果沒(méi)有足夠的處理機(jī)可供分配，那就把這個(gè)申請(qǐng)請(qǐng)求（逐級(jí)）向上傳遞，直到到達(dá)某個(gè)能夠滿足該請(qǐng)求的層次。在這一層次上，管理者把這個(gè)請(qǐng)求分解成多個(gè)申請(qǐng)并向下傳遞給下級(jí)的管理者，一直傳遞到樹(shù)的底層。在最低層，被分配的處理機(jī)被標(biāo)為“繁忙”，并把實(shí)際分配到的處理機(jī)數(shù)沿著樹(shù)向上逐級(jí)報(bào)告。

104感謝你的觀看2019年7月194.2.5處理機(jī)分配算法舉例

層次分配算法：處理器預(yù)定如果4.2.5處理機(jī)分配算法舉例

層次分配算法：R的取值 1）R必須足夠的大以便確保有足夠數(shù)量的處理機(jī)可供分配。否則，請(qǐng)求將沿著樹(shù)向上傳遞。這樣將會(huì)浪費(fèi)了大量的時(shí)間。

2）另一方面，如果R太大，那么將有過(guò)多的處理機(jī)被標(biāo)為“繁忙”，這將浪費(fèi)一些計(jì)算能力，直到分配消息返回底層，這些處理機(jī)才會(huì)被釋放。105感謝你的觀看2019年7月194.2.5處理機(jī)分配算法