




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
第十章分布式調(diào)度主講陳志剛教授7/30/20231第十章分布式調(diào)度主講陳志剛教授7/25/2023110.1調(diào)度算法概述調(diào)度算法的分類Casavant和Kuhl對調(diào)度算法做了如下分類:7/30/20232中南大學信息科學與工程學院10.1調(diào)度算法概述調(diào)度算法的分類7/25/20232中南調(diào)度算法的分類
對于大量的實時調(diào)度方法而言,還存在著其他一些劃分方法:搶占式(preemptive)和非搶占(non-preemptive)調(diào)度:對搶占式調(diào)度算法,正在運行的任務可能被其他任務所打斷。而后者一旦任務開始運行,該任務只有在運行完成而主動放棄CPU資源,或是因為等待其他資源被阻塞的情況下才會停止運行。實時內(nèi)核大都采用了搶占式調(diào)度算法,使關鍵任務能夠打斷非關鍵任務的執(zhí)行,確保關鍵任務的截止時間能夠得到滿足。10.1調(diào)度算法概述7/30/20233中南大學信息科學與工程學院調(diào)度算法的分類10.1調(diào)度算法概述7/25/20233中南調(diào)度算法的分類適應性(Adaptive)和非適應性(Non-Adaptive)調(diào)度:非適應性調(diào)度算法只是用一種負載分配策略,不會根據(jù)系統(tǒng)的反饋而改變自己的行為。適應性調(diào)度算法能夠根據(jù)系統(tǒng)的反饋調(diào)整自己的行為,采用不同的負載分配策略。一個適應性調(diào)度算法是許多種調(diào)度算法的集合,根據(jù)系統(tǒng)的各種參數(shù)來選擇一種合適的算法。
10.1調(diào)度算法概述7/30/20234中南大學信息科學與工程學院調(diào)度算法的分類10.1調(diào)度算法概述7/25/20234中南調(diào)度算法的目標和有效性評價
分布式調(diào)度的基本目標是盡快得到計算結(jié)果和有效地利用資源。其具體目標有2個:負載平衡(LoadBalancing):它的努力目標是維持整個分布式系統(tǒng)中各個資源上的負載大致相同。負載共享(LoadSharing):它的目標僅僅是防止某個處理機上的負載過重。10.1調(diào)度算法概述7/30/20235中南大學信息科學與工程學院調(diào)度算法的目標和有效性評價10.1調(diào)度算法概述7/25/2調(diào)度算法的目標和有效性評價
從調(diào)度算法的有效性來看,調(diào)度算法分為最優(yōu)調(diào)度算法和次優(yōu)調(diào)度算法。從理論上來說,最優(yōu)調(diào)度只有在能夠完全獲知所有任務在處理、同步和通信方面的需求,以及硬件的處理和時間特性的基礎上才能實現(xiàn)。實際的應用很難實現(xiàn),特別是需要獲知的信息處于動態(tài)變化的情況下。即使在這些需要的信息都是可以預見的情況下,常用的調(diào)度問題仍然是一個NP難題。調(diào)度的復雜性將隨調(diào)度需要考慮的任務和約束特性的數(shù)量呈現(xiàn)出指數(shù)增長。10.1調(diào)度算法概述7/30/20236中南大學信息科學與工程學院調(diào)度算法的目標和有效性評價10.1調(diào)度算法概述7/25/2調(diào)度算法的目標和有效性評價選擇調(diào)度算法時,通常需要綜合考慮如下因素通信代價:這個參數(shù)考慮了向一個給定的節(jié)點傳送或者從一個給定節(jié)點接收一個報文所花費的時間,更為重要的是必須考慮為一個進程分配一個執(zhí)行地點而引起的通信代價。執(zhí)行代價:這個參數(shù)反映的是將一個進程分配到一個指定的執(zhí)行節(jié)點,在這個節(jié)點的執(zhí)行環(huán)境下,執(zhí)行這個程序所需的額外開銷。資源利用率參數(shù):表明基于分布式系統(tǒng)當前各個節(jié)點的負載情況,給一個進程分配的執(zhí)行節(jié)點是否合適。10.1調(diào)度算法概述7/30/20237中南大學信息科學與工程學院調(diào)度算法的目標和有效性評價10.1調(diào)度算法概述7/25/2調(diào)度算法的目標和有效性評價次優(yōu)的調(diào)度算法分為兩類:近似的次優(yōu)調(diào)度算法:在近似次優(yōu)調(diào)度方法中,負載分配算法僅搜索一個解空間的子集,當尋找到一個好的解時,終止執(zhí)行。使用近似的次優(yōu)調(diào)度算法必須能夠判定所得到的解是否是可以被接受的,也就是說,必須能夠確定最優(yōu)解和次優(yōu)解之間的近似程度。啟發(fā)式的次優(yōu)調(diào)度算法:使用比較簡明的規(guī)則和一些直覺的規(guī)則來進行調(diào)度。這些啟發(fā)式的規(guī)則往往是不能證明其正確性,在特定情況下可能還是錯誤的,但是在絕大多數(shù)的情況下是能夠被接受的。10.1調(diào)度算法概述7/30/20238中南大學信息科學與工程學院調(diào)度算法的目標和有效性評價10.1調(diào)度算法概述7/25/2
靜態(tài)調(diào)度算法是根據(jù)系統(tǒng)的先驗知識做出決策。運行時負載不能重新分配。設計調(diào)度策略時要考慮的三個主要因素是處理機的互連、任務的劃分和任務的分配。通常用圖模型表示任務和處理機的結(jié)構(gòu)。我們用任務優(yōu)先圖或者任務交互作用圖對任務集合建模。任務優(yōu)先圖又稱為有向無環(huán)圖(DAG),每個鏈接定義了任務間的優(yōu)先關系。節(jié)點和鏈接上的標記表示任務執(zhí)行時間和任務完成后啟動后續(xù)任務所需的時間間隔。任務交互作用圖中,鏈接定義了兩個任務間的相互關系。每個鏈接賦予一對數(shù),表示這兩個任務在同一個處理機上時的通信開銷和在不同處理機上時的通信開銷。10.2靜態(tài)調(diào)度7/30/20239中南大學信息科學與工程學院靜態(tài)調(diào)度算法是根據(jù)系統(tǒng)的先驗知識做出決策。運行時負載10.2靜態(tài)調(diào)度7/30/202310中南大學信息科學與工程學院10.2靜態(tài)調(diào)度7/25/202310中南大學信息科學與工任務劃分與分配
任務劃分的一個主要目標就是盡可能消除處理器間通信引起的開銷。一個給定任務劃分的粒度被定義為任務的計算量與通信量的比值。粒度太大,就會降低并行度,因為潛在并行任務可能被劃分進同一個任務而分配給一個處理器。粒度太小,進程切換和通信的開銷就會增加。任務聚類:在圖模型中,任務的劃分被稱作任務聚類,即在給定的圖模型中對小任務進行分類。任務劃分把任務圖當作一個整體,將圖中的小任務(節(jié)點)劃分成不同的聚類,聚類中的小任務串行執(zhí)行,不同的聚類之間并行執(zhí)行。任務聚類中可以使用兩種策略:
將不相關的任務映射到一個聚類中;將DAG中一條優(yōu)先路徑上的任務映射到一個聚類中。10.2靜態(tài)調(diào)度7/30/202311中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202311中南大任務劃分與分配任務劃分的方法關鍵路徑劃分:主要思想是在給定的任務優(yōu)先圖中垂直或者水平劃分。關鍵路徑(最長路徑)的概念常常在垂直劃分中使用。水平劃分把給定的任務分成若干層,任務的優(yōu)先級由它們所在的層次決定。通信延遲最小劃分:主要思想是把通信頻繁的節(jié)點歸成一類。然而,這些需要通信的任務分配在一個處理器上會喪失任務間的并發(fā)性。如果減小通信延遲的好處抵銷了并行任務串行化的損失,就采用通信延遲最小劃分。任務復制:為了消除任務間的通信開銷,將任務在處理機上進行復制有時是最有效的方法。這個方法保留了任務原有的并行性;但是存儲空間要求和同步開銷增加了??梢岳萌蝿諒椭苼磉_到容錯性。任務復制也被用來實現(xiàn)無錯調(diào)度,以保證處理器出現(xiàn)錯誤時最后計算結(jié)果正確。
10.2靜態(tài)調(diào)度7/30/202312中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202312中南大任務劃分與分配10.2靜態(tài)調(diào)度消除通信延遲的劃分133112T2T3T4T5T63133312T17/30/202313中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度消除通信延遲的劃分13311任務劃分與分配任務復制:10.2靜態(tài)調(diào)度7/30/202314中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202314中南大任務劃分與分配基于任務優(yōu)先圖的任務調(diào)度甘特圖(ganttchart)能夠最有效描述進程對處理器的分配情況。甘特圖以處理器為縱坐標,以時間為橫坐標。圖中的每個方塊表示進程在某個系統(tǒng)中的開始時間、持續(xù)時間和結(jié)束時間。處理器內(nèi)的時間延遲和處理器間的時間延遲都能夠在圖中體現(xiàn)。
10.2靜態(tài)調(diào)度7/30/202315中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202315中南大任務劃分與分配基于任務優(yōu)先圖的任務調(diào)度
10.2靜態(tài)調(diào)度7/30/202316中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202316中南大任務劃分與分配基于任務優(yōu)先圖的任務調(diào)度通信延遲和任務復制對調(diào)度的影響:
10.2靜態(tài)調(diào)度7/30/202317中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202317中南大任務劃分與分配基于任務優(yōu)先圖的任務調(diào)度線性聚類與非線性聚類:如果至少有一個聚類中包含兩個獨立的任務,則聚類是非線性的;否則,聚類就是線性的。
10.2靜態(tài)調(diào)度7/30/202318中南大學信息科學與工程學院任務劃分與分配10.2靜態(tài)調(diào)度7/25/202318中南大兩種最優(yōu)調(diào)度算法
多數(shù)調(diào)度算法是NP完全的。下面介紹2種有約束的調(diào)度問題,他們有多項式時間的執(zhí)行復雜度。兩種方法都假設通信代價可以忽略,優(yōu)先圖中每個節(jié)點的執(zhí)行時間是一樣的,即一個時間單元。具體限制如下:在第一個有約束的調(diào)度問題中,優(yōu)先圖是一棵樹。在第二個有約束的調(diào)度問題中,只有兩個處理器可用。兩種調(diào)度算法都是最高層優(yōu)先(highest-level-first)方法,也就是說,通過節(jié)點的優(yōu)先級來選擇節(jié)點。
10.2靜態(tài)調(diào)度7/30/202319中南大學信息科學與工程學院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度7/25/202319中南兩種最優(yōu)調(diào)度算法
10.2靜態(tài)調(diào)度
T1
T2
T3
T4
T5
T6
T7
T8
T9
T10
T11
T12
T13
時間
處理器
P1
P2
P3
0
T1
T2
T3
T4
T5
T7
T6
T9
T10
T8
T12
T11
T13
(a)
樹結(jié)構(gòu)的任務優(yōu)先圖
(b)對三個處理器的調(diào)度
樹結(jié)構(gòu)任務優(yōu)先圖的最優(yōu)調(diào)度7/30/202320中南大學信息科學與工程學院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度兩種最優(yōu)調(diào)度算法
10.2靜態(tài)調(diào)度任務優(yōu)先圖對雙處理器的最優(yōu)調(diào)度7/30/202321中南大學信息科學與工程學院兩種最優(yōu)調(diào)度算法10.2靜態(tài)調(diào)度任務優(yōu)先圖對雙處理器的最優(yōu)基于任務相互關系圖的任務調(diào)度任務相互關系圖由無向圖Gt(Vt,Et)表示,Vt是進程集合,Et是邊集合,每條邊用相關兩個進程的通信代價標記;處理器圖Gp(Vp,Ep)用頂點集Vp和邊集Ep表示,Vp中的每個元素是一個處理器,Ep中的每個元素是一個通信信道;然后進行分配M:進行Vt→Vp的變換和執(zhí)行時間的估計。假設w(u)和w(u,v)分別表示節(jié)點u和鏈接(u,v)的代價。
10.2靜態(tài)調(diào)度7/30/202322中南大學信息科學與工程學院基于任務相互關系圖的任務調(diào)度10.2靜態(tài)調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度對分配M的評估:處理器p的計算負載為:處理器p的通信負載為:整個應用程序中總的計算量是:
整個應用程序中總的通信量是:
7/30/202323中南大學信息科學與工程學院10.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度對分配M的評估:程序總的執(zhí)行時間大概是:
α是依據(jù)處理器的執(zhí)行速度確定的值,β是依據(jù)每個通信信道的通信速度和通信進程間的距離確定的值。注意如果兩個進程u和v在Gt中鄰接,它們在Gp的映像(M的映像結(jié)果)可能鄰接也可能不鄰接。理想的情況下,所有通信進程被分配在鄰接的處理機上,以此減少處理器間通信。(兩個進程通常不應該映射在一個處理器上,任務聚類時,這兩個進程應當聚類到同一進程.)
7/30/202324中南大學信息科學與工程學院10.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度映射的勢:評估映射質(zhì)量的一個指標是任務圖Gt中的邊映射到處理器圖Gp中的邊的數(shù)目。這個數(shù)目被稱作映射的勢(cardinality),就是Gt中映射到Gp中鄰接處理器的通信進程對的數(shù)目。映射的勢不會超過Gt中的鏈接數(shù)目。如果一個映射的勢最大,它就是一個理想的映射。
7/30/202325中南大學信息科學與工程學院10.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度圖中,映射的勢是8,任務關系圖中邊的為13條。
7/30/202326中南大學信息科學與工程學院10.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度7/25/2010.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度嵌入:設想任務相互關系圖和處理器圖被各自看作Gt和Gp。為了通過Gt得到對Gp的有效模擬,也就是在Gp中嵌入Gt。嵌入的不同代價指標:Gt的邊的膨脹。Gt的邊的膨脹定義為被映射成Gt里的一條邊的Gp中對應的路徑的長度。嵌入的膨脹為Gt中的最大邊膨脹。嵌入的擴大。嵌入的擴大定義為Gt里的節(jié)點數(shù)對Gp里的節(jié)點數(shù)的比率。嵌入的擁塞。嵌入的擁塞定義為包含Gp中的一條邊的最大路徑數(shù),Gp中的每條路徑表示Gt中的一條邊。嵌入的負載。嵌入的負載是Gt分配給Gp中任意處理器的進程的最大數(shù)目。
7/30/202327中南大學信息科學與工程學院10.2靜態(tài)調(diào)度基于任務相互關系圖的任務調(diào)度7/25/20典型的動態(tài)調(diào)度算法由以下6個策略組成:啟動策略決定誰應該激活負載平衡活動。轉(zhuǎn)移策略決定一個節(jié)點是否在合適的狀態(tài)參與負載轉(zhuǎn)移。選擇策略選擇最適合轉(zhuǎn)移最能起平衡作用的任務,并發(fā)送給合適的目標處理器。收益性策略量化系統(tǒng)中負載不平衡程度,并且作為系統(tǒng)負載平衡潛在受益的估計,評估系統(tǒng)負載平衡是否是有收益的。定位策略尋找合適的節(jié)點共享負載。信息策略決定收集系統(tǒng)中其他節(jié)點狀態(tài)信息的時機、收集的方法和收集的信息。
10.3動態(tài)調(diào)度7/30/202328中南大學信息科學與工程學院典型的動態(tài)調(diào)度算法由以下6個策略組成:10.3動態(tài)調(diào)度7/動態(tài)負載平衡算法的分類局部和全局
局部負載分配處理單個處理器上的進程對時間片(單元)的分配。全局負載分配首先進行進程對處理器的分配,然后完成每個處理器內(nèi)這些進程的局部調(diào)度。集中控制的和分散控制的(在動態(tài)類型中)在分散控制中,決策工作被分配給不同的處理器。在集中控制中,這些工作是由一個處理器完成的。10.3動態(tài)調(diào)度7/30/202329中南大學信息科學與工程學院動態(tài)負載平衡算法的分類10.3動態(tài)調(diào)度7/25/20232動態(tài)負載平衡算法的分類協(xié)作的和非協(xié)作的(對分散控制)協(xié)作的--分布式對象間有協(xié)同操作,非協(xié)作的--處理器獨立做出決策。非自適應的和自適應的非自適應負載分配只使用一種負載分配算法,不會依據(jù)系統(tǒng)反饋而改變自己的行為。自適應負載分配能夠根據(jù)系統(tǒng)反饋調(diào)整分配算法。典型地,一個自適應負載分配算法是許多負載分配算法的集合,依據(jù)系統(tǒng)的各種參數(shù)來選擇一個合適的算法。10.3動態(tài)調(diào)度7/30/202330中南大學信息科學與工程學院動態(tài)負載平衡算法的分類10.3動態(tài)調(diào)度7/25/2023310.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類動態(tài)負載平衡算法的設計決策包括如下一些內(nèi)容:非搶先式的和搶先式的:搶先式的主要目的是負載共享,節(jié)點只分配新到達的任務,又稱為任務放置(placement)。搶先式的算法的主要目的是充分利用系統(tǒng)資源,能夠重新分配正在運行的任務,又稱為進程遷移(migration)。采用何種信息策略。信息策略有三種:(a)周期策略;(b)需求策略;(c)狀態(tài)變化驅(qū)動策略。集中控制算法和分散控制算法:集中控制算法有一個中心處理器從系統(tǒng)中其他處理器收集負載信息。分散控制算法是通過每個處理器發(fā)送自己負載變化情況給所有處理器或者它的鄰居來實現(xiàn)的。
7/30/202331中南大學信息科學與工程學院10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類7/25/2023310.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類動態(tài)負載平衡算法的設計決策包括如下一些內(nèi)容:采用何種啟動策略。啟動策略有三種:發(fā)送者啟動的、接收者啟動的和對稱啟動的。資源復制。任務轉(zhuǎn)移的時候,涉及到的文件和數(shù)據(jù)也必須被復制到目標處理器。為了減少轉(zhuǎn)移的代價,常用的任務和數(shù)據(jù)可以事先被復制和分配到不同的處理器。進程分類。依據(jù)特征來區(qū)分進程類型。如果系統(tǒng)中運行的進程有很大的區(qū)別,它們就必須分在不同的類。當系統(tǒng)中有多個進程類型時,負載平衡算法必須考慮進程的類型,根據(jù)不同的類型做出改變。7/30/202332中南大學信息科學與工程學院10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類7/25/2023310.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)
負載平衡算法使用的參數(shù):
系統(tǒng)的規(guī)模:處理器的數(shù)目是影響負載平衡決策的一個參數(shù)。系統(tǒng)負載情況:需要避免顛簸現(xiàn)象。處理器的輸入流量:進程可以以任何隨機模式到達處理器,如果處理器能夠測定自己的輸入流量并且和其他處理器比較,它就能比較容易評估系統(tǒng)即時的負載水平,從而對任務轉(zhuǎn)移做出更好的決策。轉(zhuǎn)移的負載門限。系統(tǒng)中觸發(fā)任務轉(zhuǎn)移的負載門限是一個關鍵參數(shù),因為選擇不當會導致系統(tǒng)不平衡和任務轉(zhuǎn)移的連鎖反應。
7/30/202333中南大學信息科學與工程學院10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)
負載平衡算法使用的參數(shù):
任務大小。一般來說,轉(zhuǎn)移一個運行時間太短的任務是不恰當?shù)摹n愃频?,太大的進程或者涉及到大量數(shù)據(jù)和文件的進程最好在本地處理器上執(zhí)行。管理成本。組成管理成本的主要因素是:處理器當前負載的測量、處理器決策使用的負載信息、決策發(fā)生的位置和處理器間任務的傳送。
7/30/202334中南大學信息科學與工程學院10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)
負載平衡算法使用的參數(shù):
負載平衡的視界。一個節(jié)點能夠在其鄰接節(jié)點范圍內(nèi)為一個任務尋找可能的目標節(jié)點,在其上運行該任務。這個鄰接節(jié)點范圍的直徑稱為視界(horizon)。這個參數(shù)設置了尋找目標節(jié)點過程中探查的鄰接節(jié)點的數(shù)量。資源要求。任務對系統(tǒng)資源的要求會影響它的轉(zhuǎn)移。需要較多資源的進程可能會持續(xù)等待資源變得可用,這就可能影響系統(tǒng)的響應時間。
7/30/202335中南大學信息科學與工程學院10.3動態(tài)調(diào)度動態(tài)負載平衡算法的分類、設計決策和使用的參10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題
工作站共享問題包括:對工作站使用模式的分析,設計分配遠程處理能力的算法和結(jié)構(gòu),研究遠程執(zhí)行設備。
全局調(diào)度機構(gòu)的主要目標有:性能要求:調(diào)度機構(gòu)占用整個系統(tǒng)的開銷最小,它們不應該占用不使用此機構(gòu)的應用程序的時間,也不應該使被調(diào)度的應用程序的執(zhí)行產(chǎn)生大的延遲。支持的系統(tǒng)規(guī)模:能支持幾百個甚至上千個工作站。
7/30/202336中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/2010.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題
容錯:一個或幾個機器崩潰時,系統(tǒng)的遠程執(zhí)行設備應該在幾秒鐘之后能夠繼續(xù)工作。公平性:不管分配作業(yè)到哪個機器上,為該作業(yè)提供的性能都是同樣可接受的。自治性:工作站屬于個人所有,其他人使用不應影響主人的工作。7/30/202337中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/210.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題
有關負載的信息是如何傳送的,使用公布的還是回答查詢的辦法?即選擇哪一種信息策略。誰主動發(fā)起遠程執(zhí)行的請求,是作業(yè)進入的顧客節(jié)點(源節(jié)點)還是處理此作業(yè)的節(jié)點(服務員節(jié)點)?這里所要解決的是選擇什么樣的啟動策略。誰來決策為一個作業(yè)(程序)選擇一個合適的執(zhí)行主機,請求的發(fā)起者還是一個集中的服務員節(jié)點?這里要解決的是定位策略的問題。這是設計全局調(diào)度設施在結(jié)構(gòu)上要解決的三個主要問題。7/30/202338中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)工作站共享問題7/25/210.4空閑工作站的調(diào)度結(jié)構(gòu)集中式調(diào)度
集中式調(diào)度是在系統(tǒng)中有一個中央調(diào)度服務員,負責搜集狀態(tài)信息并做出全部調(diào)度決策。各機器周期性地向它發(fā)送狀態(tài)更新報文,報告它們的負載信息;顧客向它發(fā)送遠程執(zhí)行請求。中央調(diào)度服務員根據(jù)負載情況,建立一個主機候選者的有序表,對顧客的遠程執(zhí)行請求進行響應。使用中央調(diào)度服務員查詢狀態(tài)會減少報文傳送數(shù)目。但是容易產(chǎn)生狀態(tài)信息過時的問題。解決集中式調(diào)度的容錯問題的典型方法是提供多個備用服務員。集中調(diào)度的最后一個問題是在何處運行調(diào)度程序。調(diào)度程序沒有任何特殊要求,可放到任何空閑機器上,并可根據(jù)需要遷移。7/30/202339中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)集中式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度
在全分散方案中,每個機器自己進行選擇活動。它必須不斷地記錄整個系統(tǒng)狀態(tài)或者當需要時查詢系統(tǒng)狀態(tài)信息。在前一種情況下,每個機器(即使是忙碌的機器)要定期地產(chǎn)生更新報文并向其他主機廣播(公布)。而每個主機中維持一個主機狀態(tài)表。在后一種情況下只有對主機選擇有興趣的那些主機才關心狀態(tài)信息(查詢)。采用查詢方法,即每個需要獲得空閑主機的顧客機發(fā)送查詢報文請求得到當前狀態(tài)信息,請求中包括所需資源的說明。該顧客從所有愿意成為候選主機的機器那里得到回答,并從中選取一個最合適的機器。7/30/202340中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度
兩個要解決的問題。第一是查詢者可能要求接收大量的、幾乎是同時到來的回答報文,以及N2報文的傳送要消耗網(wǎng)絡的帶寬。第二是可能產(chǎn)生沖突。
第一個問題的解決方法:一個相當簡單的辦法是放寬選擇主機的標準,它可以不是最佳的,即不是負載最輕的,但可以是較輕的、較好的。查詢者只考慮全部回答報文中的一部分,扔掉其余部分。第二個問題解決辦法是在遷移程序前先發(fā)送一個執(zhí)行請求,被選擇機只對第一個請求回答并等待申請者傳送被執(zhí)行的程序。7/30/202341中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)分散式調(diào)度7/25/20210.4空閑工作站的調(diào)度結(jié)構(gòu)混合式調(diào)度集中式方法支持的規(guī)模較大,但集中式方法可靠性較差,不易擴充。分散式方法具有較高可靠性,實現(xiàn)簡單,容易擴充,但效率較低?;旌鲜秸{(diào)度結(jié)構(gòu)中,每個工作站有一個局部調(diào)度程序,還有一個后臺作業(yè)隊列,用戶提交的作業(yè)和遠程作業(yè)都放到此隊列中。有一個工作站除了局部調(diào)度程序和作業(yè)隊列外,還有一個協(xié)調(diào)程序(協(xié)調(diào)者)。協(xié)調(diào)者定期(例如每兩分鐘)向各個工作站查詢,看有哪些工作站可用作遠程執(zhí)行的源,哪些工作站后臺作業(yè)隊列中有作業(yè)等待處理。中央?yún)f(xié)調(diào)者為有后臺作業(yè)等候的工作站上的調(diào)度程序分配空閑工作站資源。7/30/202342中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)混合式調(diào)度7/25/2023410.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法
進程轉(zhuǎn)移是指進程的重新定位。其目的主要是為了有效地利用系統(tǒng)資源.用戶在執(zhí)行若干相對獨立的任務時,可把它們從某些重負載工作站移到另外一些輕負載工作站上加快完成。進程轉(zhuǎn)移的形式:通過進程放置(placement)的非搶先(non-preemptive)方式和通過進程遷移(migration)的搶先(preemptive)方式.7/30/202343中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法10.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法
進程轉(zhuǎn)移和遠程執(zhí)行的一般要求有以下兩點:透明性。指的是一個進程執(zhí)行的行為及結(jié)果不應受執(zhí)行位置的影響,應該是位置無關的.為了轉(zhuǎn)移此進程不必用特定方式重新編寫程序。也就是說,這些進程轉(zhuǎn)移到遠程執(zhí)行環(huán)境后必須與在原地一樣(名字、操作和數(shù)據(jù),但不包括硬件)有效性。遷移一個進程需要時間,支持該進程遠程執(zhí)行也需要時間,這些時間應盡量短。7/30/202344中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法10.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法
判斷是否值得進行進程遷移和遠程執(zhí)行有多個計算量很大的進程在一個工作站上運行;運行時間遠遠超過在遠程啟動執(zhí)行一個進程的時間;從所選擇的遠程節(jié)點上被驅(qū)逐的可能性很??;進程剛建立不久,還未來得及使用很多地址空間。7/30/202345中南大學信息科學與工程學院10.4空閑工作站的調(diào)度結(jié)構(gòu)進程轉(zhuǎn)移和遠程執(zhí)行的目的和方法10.5進程轉(zhuǎn)移和遠程執(zhí)行Sprite的進程遷移和遠程執(zhí)行設備
Sprite是對進程遷移透明性支持較完全的一個系統(tǒng)。它將高度透明性作為進程遷移設計的一個主要目標,采用四種不同的技術(shù)支持這些透明性:
利用專用的文件服務器,使得一些系統(tǒng)調(diào)用(如文件操作)位置無關;利用狀態(tài)轉(zhuǎn)移(transfer)技術(shù),將與遷移進程有關的一些狀態(tài)轉(zhuǎn)移到目的節(jié)點;利用轉(zhuǎn)發(fā)(forward)技術(shù),轉(zhuǎn)發(fā)與位置有關的系統(tǒng)調(diào)用;采用專門技術(shù),對幾個特殊的系統(tǒng)調(diào)用(如fork、exec等)7/30/202346中南大學信息科學與工程學院10.5進程轉(zhuǎn)移和遠程執(zhí)行Sprite的進程遷移和遠程執(zhí)行10.5進程轉(zhuǎn)移和遠程執(zhí)行Sprite的進程遷移和遠程執(zhí)行設備
Sprite系統(tǒng)的進程遷移包括以下幾個步驟:
向目的節(jié)點發(fā)送一個RPC,確認是否允許遷移該進程。當要遷移該進程時,使用標準信號中斷該進程的執(zhí)行。傳送該進程的“進程狀態(tài)”,包括各寄存器的內(nèi)容、用戶標識符和小組標識符、信號處理信息、基地節(jié)點和該進程標識符。傳送虛擬地址空間。把所有重寫的頁送到文件服務器,把對應的交換文件的頁表和說明符送到目的節(jié)點。將該進程已打開的文件的說明符和當前工作目錄打包并傳送。發(fā)送一個RPC結(jié)束遷移,允許被遷移的進程在目的節(jié)點恢復執(zhí)行。最后,該進程在目的節(jié)點上恢復。
7/30/202347中南大學信息科學與工程學院10.5進程轉(zhuǎn)移和遠程執(zhí)行Sprite的進程遷移和遠程執(zhí)行10.5進程轉(zhuǎn)移和遠程執(zhí)行V系統(tǒng)中的可搶先的遠程執(zhí)行設備
V系統(tǒng)的可搶先遠程執(zhí)行設備使用預復制方法提高性能:為了減少凍結(jié)時間,可使用預復制方法,在凍結(jié)前就多次復制全部地址空間,每次復制上次復制以來被修改的頁。多次復制后被修改的部分僅剩下很少的部分,這時再凍結(jié),把剩余部分復制過去。這樣僅用最短時間凍結(jié)。7/30/202348中南大學信息科學與工程學院10.5進程轉(zhuǎn)移和遠程執(zhí)行V系
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- WJB-3擠壓式注漿泵產(chǎn)品介紹
- 9-通風系統(tǒng)設計
- 2024年工作總結(jié)暨新年計劃
- 環(huán)境保護與廢料管理
- 氣動油泵產(chǎn)品介紹
- 《豐富多樣主題插圖》課件
- 項目管理中的客戶關系維護試題及答案
- 農(nóng)業(yè)植保員考試的復盤試題及答案
- 產(chǎn)品市場占有率下降原因分析風險評估重點基礎知識點
- 2025年國際金融理財師考試投資分析方法試題及答案
- 參展商服務手冊
- 隨機過程-華東師范大學中國大學mooc課后章節(jié)答案期末考試題庫2023年
- 湖南省對口招生考試醫(yī)衛(wèi)專業(yè)試題(2024-2025年)
- 公共危機管理(本)-第五次形成性考核-國開(BJ)-參考資料
- 孕期碘缺乏病的健康宣教
- 電梯調(diào)試單機試車方案
- 【MOOC】面向?qū)ο蟪绦蛟O計-濮陽職業(yè)技術(shù)學院 中國大學慕課MOOC答案
- 子宮平滑肌瘤手術(shù)臨床路徑表單
- GB/T 36547-2024電化學儲能電站接入電網(wǎng)技術(shù)規(guī)定
- 中華傳統(tǒng)文化進中小學課程教材指南
- 汽車發(fā)動機火花塞市場洞察報告
評論
0/150
提交評論