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

高級操作系統(tǒng)

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

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

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

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

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

處理機分配策略可以分為兩大類：

1）非遷移的

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

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

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

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

使平4.2分布式處理機分配算法

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

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

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

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

對于大多數(shù)用戶來說，響應(yīng)率比響應(yīng)時間更重要。

其原因是：

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

考慮負(fù)載的分配方法：局部和全局

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

靜態(tài)負(fù)載分配中，進程對處理器的分配是在進程執(zhí)行以前的編譯階段完成的，而動態(tài)負(fù)載分配要到進程在系統(tǒng)中執(zhí)行時才做出分配。靜態(tài)方法又叫做確定性調(diào)度，而動態(tài)方法叫做負(fù)載平衡。17感謝你的觀看2019年7月194.2分布式處理機分配算法考慮負(fù)載的分配方法：17感謝4.2分布式處理機分配算法最優(yōu)和次優(yōu)（在靜態(tài)和動態(tài)兩種類型中）

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

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

1）解空間枚舉搜索、

2）圖模型、

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

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

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

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

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

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

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

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

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

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

對非搶占式的負(fù)載分配算法，一個任務(wù)（進程）開始執(zhí)行后就不能中斷。在搶占式負(fù)載分配算法中，進程可以中斷，并從處理器上移走，以后繼續(xù)執(zhí)行。非自適應(yīng)的和自適應(yīng)的

非自適應(yīng)負(fù)載分配只使用一種負(fù)載分配算法，不會依據(jù)系統(tǒng)反饋而改變白己的行為。自適應(yīng)負(fù)載分配能夠根據(jù)系統(tǒng)反饋調(diào)整分配算法。典型地，一個自適應(yīng)負(fù)載分配算法是許多負(fù)載分配算法的集合，依據(jù)系統(tǒng)的各種參數(shù)來選擇一個合適的算法。23感謝你的觀看2019年7月194.2分布式處理機分配算法非搶占式的和搶占式的

對非搶占式4.2分布式處理機分配算法

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

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

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

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

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

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

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

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

而全局算法需要付出巨大的代價來換取一個性能稍微好一點的結(jié)果。30感謝你的觀看2019年7月194.2分布式處理機分配算法其它一些機器上的負(fù)載4.2分布式處理機分配算法

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

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

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

以機器上的進程數(shù)量作為機器的負(fù)載。優(yōu)點：簡單

原因：只需要計算機器上的進程數(shù)量缺點：用進程數(shù)量的多少來表示機器的負(fù)載是不確切的，它幾乎說明不了什么問題。

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

對度量方法1進行如下改進：

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

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

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

直接使用處理機利用率：

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

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

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

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

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

在處理機分配算法實現(xiàn)中還必須考慮復(fù)雜性：事實上，所有的研究者只分析、模擬或計算處理機的利用率、網(wǎng)絡(luò)的使用情況以及響應(yīng)時間，以此來衡量他們所提出算法的好壞。很少有人考慮軟件的復(fù)雜性對系統(tǒng)的性能、正確性和魯棒性所產(chǎn)生的影響。也不會有人提出了一個新算法并宣稱它的性能非常好，然后，得出結(jié)論說這個算法不值得使用，因為它的算法性能有可能只是比現(xiàn)有的算法稍好一點，但在實現(xiàn)上卻復(fù)雜得多。

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

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

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

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

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

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

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

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

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

給k臺機器發(fā)4.2分布式處理機分配算法

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

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

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

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

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

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

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

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

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

1）若太大，會降低并行度，因為潛在的并行任務(wù)可能被劃分進同一個任務(wù)而分配給一個處理器。

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

4.2分布式處理機分配算法

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

盡可能消除處理器間通信引起的開銷?？梢允褂萌N方法：水平或者垂直劃分。

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

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

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

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

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

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

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

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

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

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

任務(wù)分配就是在給定了互連網(wǎng)絡(luò)的并行系統(tǒng)或者分布式系統(tǒng)中分配顆粒（顆粒是任務(wù)劃分的結(jié)果）。若任務(wù)圖和處理器圖的節(jié)點數(shù)目都是n，那么就有n!種不同的分配方法把任務(wù)圖Gt里的節(jié)點分配到處理器圖Gp的節(jié)點上。通常把每種方法稱做Gt到Gp的一個映射。在總執(zhí)行時間概念下，有些映射比較好。54感謝你的觀看2019年7月194.2分布式處理機分配算法任務(wù)分配就是4.2分布式處理機分配算法關(guān)于Gp的典型假設(shè)：

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

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

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

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

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

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

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

T4和有2個單位通信延遲的T4

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

通信延遲的影響通信延遲使調(diào)度算法大大地變復(fù)雜。例：圖b,c,d給出了針對a中任務(wù)優(yōu)先圖的三種不同的調(diào)度對于c和d，若通信延遲d大于T2的執(zhí)行時間，圖c的調(diào)度就比圖d要好?？梢哉f，若通信延遲太大的話，所有任務(wù)分配在一個處理器上是比較合適的。(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)度

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

有時可以使用任務(wù)復(fù)制的方法減少通信需求。顯然，由于通過任務(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ù)聚類）中的粒度問題，是把指定應(yīng)用程序的任務(wù)分成一個個任務(wù)類。通常類的數(shù)目應(yīng)等于處理器個數(shù)若至少有一個類中包含兩個獨立的任務(wù)，則分類是非線性的；否則，分類就是線性的。右圖分別是三個進程的線性調(diào)度和非線性調(diào)度。63感謝你的觀看2019年7月19基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度

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

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

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

粒度的定義如果

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

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

粒度的定義如果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

分配算法的實現(xiàn)：就緒隊列定義就緒隊列被用來高效算法案例1：

就緒隊列舉例：圖9-8中，

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

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

個時間槽就緒隊列變成{T4,T5,T7,T9,T10,

T12}。

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

就緒隊列舉例：圖9-8中，

為方便起見，隊算法案例1：

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

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

T8和T12都分配在時間槽4，T11加入就緒隊列。

T11分配在時間槽5，T13加入就緒隊列，

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

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

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

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

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

優(yōu)先圖舉例圖9-9表示一個優(yōu)先圖，每個節(jié)點都用上面的方法進行了標(biāo)記。節(jié)點的標(biāo)記可以當(dāng)做它的優(yōu)先級任務(wù)按照優(yōu)先級升序排序為：

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

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

T4的直接后續(xù)節(jié)點是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表示一個優(yōu)先圖，每個節(jié)點都用上案例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ù)圖定義第二個任務(wù)調(diào)度模型是利用任務(wù)相互關(guān)系圖和進程的集合來表示應(yīng)用程序。任務(wù)相互關(guān)系圖由無向圖Gt(Vt,Et)表示

Vt：是進程的集合

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

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

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

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

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

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

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

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

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

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

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

映射的勢，即

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

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

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

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

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

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

基于圖論的確定性分配算法假定：每個進程都知道

1）所需的處理機

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

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

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

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

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

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

V中的每個節(jié)點表示一個進程

E中的每條邊表示兩個進程需要通信，

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

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

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

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

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

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

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

= 被虛線分割開的邊上

的權(quán)值之和

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

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

分割舉例b中顯示的分割得到的通信量之和為28如果它滿足所有對內(nèi)存和處理機的限制，那它就是一個比較好的分割，因為它要求的

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

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

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

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

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

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

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

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

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

處理機進入空閑狀態(tài)

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

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

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

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

原因：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

層次分配算法層次分配算法將所4.2.5處理機分配算法舉例

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

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

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

這個院長職位

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

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

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

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

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

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

層次分配算法：最高委員會為了4.2.5處理機分配算法舉例

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

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

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

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

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

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

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

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

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

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

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