分布式操作系統(tǒng)4

1、第四章分布式系統(tǒng)中的進程和處理機4.1 線程一、線程簡介在系統(tǒng)要求更高的吞吐量、更高的性能，并在同一地址空間，共享同一緩沖區(qū)，創(chuàng)建兩個服務進程不可能達到目的，從而需要新的機制線程像微小進程，按照順序執(zhí)行，有自己的程序計數(shù)器和堆棧。當一個線程被阻塞時，運行同一進程中的另一線程。所有線程共享全局變量，能夠存取每個虛擬地址，線程之間沒有保護，每個線程能夠讀寫其他線程的堆棧，甚至清除另一線程的堆棧：線程是同一任務的一部分且緊密合作計算機計算機進程線程程序計數(shù)器A）三個進程，每個進程有一個線程B）一個進程有三個線程線程的狀態(tài)運行線程占有CPU，處于激活狀態(tài)阻塞等待其他線程的某個事件觸發(fā)后才能喚醒并能夠運

2、行的線程就緒等候CPU服務的線程結(jié)束結(jié)束為線程退出，但還沒有被父進程回收二、線程的用途派遣者/工作者模型從系統(tǒng)郵箱內(nèi)讀出輸入請求，檢查請求，選擇一個空閑的工作者線程處理當工作者線程被喚醒后，檢查任何一個線程可訪問的共享塊緩沖區(qū)是否可以滿足，若不滿足，則給磁盤發(fā)出消息，要求所需的數(shù)據(jù)塊，等待磁盤操作完成調(diào)用調(diào)度程序，開始另一線程郵 箱共享塊Cache工作者線程派遣者線程文件服務器進程工作請求達到構(gòu)造服務器的方法n線程特點：并行，阻塞系統(tǒng)調(diào)用n單線程進程服務器的主循環(huán)是接收一個請求，檢查請求，在下一個請求到來前完成請求，當?shù)却疟P操作時，服務是空閑的且不處理另一請求特點：不并行，阻塞系統(tǒng)調(diào)用n有限

3、狀態(tài)機當請求到來后，有唯一的一個線程檢查它，如果緩沖區(qū)能滿足，進行運行，否則，向磁盤發(fā)送一條消息，但并不阻塞服務線程，而將當前請求的狀態(tài)記錄在一張表中，然后處理下一條消息。下條消息如果是請求新工作則激活它，若是磁盤對上次操作的回答，則從表中取出相關(guān)信息并處理特點：并行，非阻塞系統(tǒng)調(diào)用2. 團隊模型所有線程都是平等的，每個都獲得和處理自己的請求，但由于缺少派遣者，請求到來線程不能處理，可以通過維護一個作業(yè)隊列，掛起的作業(yè)保存在作業(yè)隊列中使用這種組織結(jié)構(gòu)，線程在查看系統(tǒng)郵箱前應先查看作業(yè)隊列郵 箱工作者線程文件服務器進程工作請求達到管道線模型第一個線程產(chǎn)生一些數(shù)據(jù)傳給下一個線程處理。數(shù)據(jù)持續(xù)從一個

4、線程傳到另一個線程，經(jīng)過的每一個線程都進行處理。郵 箱工作者線程文件服務器進程工作請求達到多線程的優(yōu)點：n多客戶端有用一個客戶端將一個文件復制到多個服務器n與RPC或通信無關(guān)并行處理程序編寫比較容易n可以在同一地址空間的不同CPU中并行運行三、線程包的設計問題線程包：與線程相關(guān)的用戶可得的原語集線程管理：靜態(tài)多線程程序編寫或編譯時就要決定選擇多少線程，每個線程分配一個固定的堆棧簡單但不靈活動態(tài)多線程線程在運行過程中動態(tài)地創(chuàng)建和回收線程結(jié)束的兩種方式完成時自動退出被外界終止：如文件服務器進程線程共享存儲器的操作打開互斥體如果一個或多個線程由于互斥體被鎖住而阻塞，則只能打開其中的一個，其余的繼續(xù)等

5、待鎖住互斥體如果一個互斥體處于打開狀態(tài)，它將僅僅用一個原子操作鎖住互斥體。試鎖嘗試鎖住互斥體，如果互斥體是打開狀態(tài)，則試鎖將返回成功的狀態(tài)標志碼，否則，返回失敗的狀態(tài)碼但不阻塞線程條件變量互斥體用于短期加鎖，以監(jiān)視進入臨界區(qū)；條件變量是用于長時間等待直到資源可用線程的代碼通常由多個過程構(gòu)成，局部變量和參數(shù)不會產(chǎn)生任何麻煩，但相對于線程的全局變量而不是相對于整個程序的全局變量會產(chǎn)生麻煩解決辦法禁止使用全局變量給每個線程分配它自己的私有全局變量引入新的庫過程來創(chuàng)建、設置和讀取這些線程全局變量四、實現(xiàn)一個線程包在用戶空間中實現(xiàn)線程特點：n用戶級的線程包能夠在不支持線程的操作系統(tǒng)中實現(xiàn)n線程切換比使用

6、內(nèi)核陷阱要快n允許每一個進程有自己定制的調(diào)度算法n阻塞調(diào)用的實現(xiàn)存在問題，非阻塞系統(tǒng)調(diào)用將需要修改現(xiàn)存的許多用戶程序n線程產(chǎn)生頁面錯時，內(nèi)核將阻塞整個進程的執(zhí)行1.用戶級線程中同一進程內(nèi)部線程的切換的實現(xiàn)存在困難在內(nèi)核中實現(xiàn)線程特點：調(diào)度者行為模擬內(nèi)核線程的功能，像用戶空間內(nèi)實現(xiàn)的線程包一樣有更好的性能和更大的靈活性，特別地，用戶線程不必發(fā)出特殊的非阻塞系統(tǒng)調(diào)用或者事先檢查發(fā)出某個系統(tǒng)調(diào)用是否安全；當一個線程由于系統(tǒng)調(diào)用或頁面錯阻塞時，若其他線程就緒，系統(tǒng)可以運行同一進程呢感中的其他線程特點：通過避免在用戶空間和內(nèi)核空間進行不必要的切換實現(xiàn)高效率五、線程和遠程過程調(diào)用（RPC）大量的RPC調(diào)用

7、是調(diào)用與它們在同一機器上的進程可以使一個進程中的線程以一種比普通方法更有效的方法調(diào)用同一機器上的另一進程中的線程n當服務器線程S啟動時，輸出它的接口告訴內(nèi)核，這個接口定義了哪些過程及其相關(guān)參數(shù)，當客戶線程C啟動時，從內(nèi)核輸入該接口，獲得用于調(diào)用的特殊標志。內(nèi)核現(xiàn)在知道C以后將調(diào)用S，并且創(chuàng)建特殊的數(shù)據(jù)結(jié)構(gòu)為調(diào)用做準備n當一個新消息進入服務器時，內(nèi)核動態(tài)創(chuàng)建一新線程去為此請求服務，并把消息映像到服務器地址空間，然后建立新線程的堆棧來存取該消息特點：線程不會因等待新任務而阻塞，不必保留環(huán)境創(chuàng)建新線程比存儲一個存在的線程花費少因為不需在服務器線程4.2 系統(tǒng)模型傳統(tǒng)系統(tǒng)中只有一個處理機，進程在處理機

8、上運行不會出現(xiàn)怎樣利用處理機的問題。而在多處理機中成為一個主要的設計問題分布式系統(tǒng)中的系統(tǒng)模型n工作站模型（Workstation model）n處理機池模型（processor poor model）n混合模型一、工作站模型系統(tǒng)是由分布在建筑物中或校園中并由高速局域網(wǎng)連接起來的工作站構(gòu)成的工作站類型：無盤工作站價格便宜容易維護無磁盤的風扇產(chǎn)生的噪音對稱性和靈活性有盤工作站分頁和臨時文件分頁、臨時文件和系統(tǒng)二進制文件分頁、臨時文件、系統(tǒng)二進制文件和文件緩沖完整的局部文件系統(tǒng)分頁和臨時文件所有用戶文件保存在中央文件服務器中，文件利用磁盤分頁和存儲臨時文件（臨時的、不能共享的、并在登陸會話結(jié)束后丟

9、棄的文件）分頁、臨時文件和系統(tǒng)二進制文件在第一種模型的基礎上可以保存二進制文件，從而減少網(wǎng)絡負擔。為了保持各工作站上的文件版本的一致性，需要相關(guān)管理乘隙進行跟蹤用戶程序的版本號分頁、臨時文件、系統(tǒng)二進制文件和文件緩沖保持長期集中存儲，并且可以通過使用文件時把它們保存在本地的方法而減少網(wǎng)絡負載，但需保持緩沖一致性完整的局部文件系統(tǒng)每臺機器基本上是獨立的并與外界進行有限的聯(lián)系，但共享困難磁盤使用優(yōu)點缺點無盤成本低，軟硬件容易維護，對稱靈活網(wǎng)絡使用頻繁，文件服務器可能成為瓶頸分頁，可檫除文件和無盤相比，使網(wǎng)絡的負擔更輕由于需要大量的磁盤，費用比較高分頁、過期文件，二進制文件使網(wǎng)絡的負擔更輕費用比較高

10、，二進制的更新比較復雜分頁、過期文件，二進制文件，緩沖減輕網(wǎng)絡和文件服務器的負擔費用比較高，存在cache一致性的問題完全本地文件系統(tǒng)幾乎沒有網(wǎng)絡負擔，不需要文件服務器失去了透明性工作站模型的缺點：處理機芯片不斷下降工作站配備多個CPU將變得經(jīng)濟可行用戶大多數(shù)時間不使用工作站大多數(shù)用戶擁有資源但沒有利用，少量用戶對資源的需要緊張，造成資源的分配不合理二、使用空閑工作站最早嘗試使用空閑工作站：Rsh machine command在指定機器上運行指定的命令可以利用空閑工作站但：n用戶必須指明機器名稱，n用戶程序在遠程機器的不同于本地機器中的環(huán)境上運行n若用戶登陸到正在運行的空閑機器上，造成新登陸

11、用戶的低性能使用工作站模型的關(guān)鍵問題：1。怎樣找出一臺空閑機器2。遠程進程怎樣透明地運行3。若空閑機器的主人回來重新使用它時怎么辦怎樣找出一臺空閑機器定位空閑工作站的方法服務器驅(qū)動工作站空閑時，將其名字、網(wǎng)絡地址和屬性輸入到某注冊文件工作站空閑時在網(wǎng)絡上廣播發(fā)送消息申明其可用性，但需要所有的機器維護注冊文件服務器驅(qū)動存在競爭危險遠程管理者注冊注冊表宿主機空閑工作站21435697.8.1。機器空閑注冊2。請求空閑工作站 并得到應答3。申請機器4。使注銷5。設置環(huán)境6。啟動進程7。進程運行8。進程退出9。報告始發(fā)者客戶端驅(qū)動申請端廣播發(fā)送請求說明其需要運行的進程，內(nèi)存需求等詳細信息，工作站接收到

12、消息后經(jīng)過一段與工作站當前負荷成正比的延遲后返回應答消息，申請端接收到返回應答時，從中挑選一個并啟動運行（負載最輕的工作站應答最先返回）遠程進程怎樣透明地運行程序運行時運行環(huán)境必須一致開始運行時需要同樣的文件系統(tǒng)、工作目錄、條件變量。無盤工作站訪問文件服務器；有盤工作站需要將請求返回到宿主機上執(zhí)行某些系統(tǒng)調(diào)用必須返回宿主機讀鍵盤、寫屏幕、所有查詢機器狀態(tài)的系統(tǒng)調(diào)用都必須在進程真正的機器上運行等與時間有關(guān)的系統(tǒng)調(diào)用可能因機器時鐘不同步而出問題其他復雜問題寫臨時文件機器主人回來怎么辦？n什么也不做簡單，不切實際，應該保證機器對于機器主人的響應n殺掉正在進入的進程所有的工作信息會丟失，并且可能造成文

13、件系統(tǒng)的混亂狀態(tài)n將進程移植到另一臺機器上因為搜索和收集待移植的進程相關(guān)的內(nèi)核數(shù)據(jù)結(jié)構(gòu)比較困難，在實踐中很少使用環(huán)境必須清理：進程移植所有子進程以及子進程的子進程也需要移植郵箱、網(wǎng)絡連接和其他系統(tǒng)范圍的數(shù)據(jù)結(jié)構(gòu)也必須刪除，并且制定一些規(guī)定，用來忽略相關(guān)的消息清理本地臨時文件清理緩存信息三、處理機池模型處理機池模型是通過建造處理機池，根據(jù)需要動態(tài)地分配給用戶，用戶個人工作站為高性能的圖形終端可在固定資金下提供更多的計算能力允許簡單的線性增加將計算能力集中在一個處理機池中的最有力根據(jù)是排隊論：用戶隨機地請求服務器工作，當服務器忙時，用戶排隊等待服務，并依次給予服務設每秒從用戶來的總輸入請求速度為，

14、 為系統(tǒng)處理請求的速度，為了達到穩(wěn)定處理，必須 。則發(fā)出請求和得到完全響應之間平均的時間間隔T與 ， 的關(guān)系為：T = 1 / ( )例如：一個文件服務器每秒能處理50次請求，而每秒只接收40次請求，則平均響應時間為 1/10 秒或100ms, 當為0時（沒有負載），文件服務器的響應時間為1/50秒。用戶用戶用戶計算機完成工作輸入隊列用戶每秒共產(chǎn)生個請求系統(tǒng)每秒能處理個請求圖4-12 一個基本的排隊系統(tǒng)假設我們有n個私有多處理機，每個有多個CPU，每個都成為一個請求到達速度為的獨立排隊系統(tǒng)，并且CPU的處理速度為 ，平均響應時間為T，若將所有的CPU放在一個處理機池中，則對應系統(tǒng)的輸入率為 n

15、 ，服務率為 n 。將這個合成系統(tǒng)的平均響應時間記為T1。根據(jù)上面公式，可以得到：T1 = 1 / ( n n ) = 1/n 1/ ( ) = 1/n T = T/n結(jié)論：用一個是小系統(tǒng)功能n倍的大系統(tǒng)來代替n個獨立的小系統(tǒng)的資源可把平均響應時間減少為原來的1/n 原因：通常情況下，只有少數(shù)服務器繁忙或過載，大多數(shù)空閑，處理機池模型就是減少了這種時間的浪費。排隊理論的結(jié)論就是根本反對分布式系統(tǒng)的論據(jù)之一工作站模型與處理機模型的比較：n處理機模型價格昂貴，成本高平均響應時間要小有利于運行大的仿真程序排隊論的假設僅當所有的請求分配在所有的處理機上并行處理時才是正確的對于機器主人回來后的問題處理比

16、較方便適合于需要大規(guī)模的計算（大型軟件開發(fā)、大型模擬、大矩陣的計算等）n工作站模型用戶響應時間恒定成本低，易于擴充適合于負荷較小的處理四、混合模型提供每個用戶一個私有工作站并附加處理機池為了保證時間，交互式工作在工作站上運行，所有的非交互式進程運行在處理機池中。這種模型具有快速的交互響應、有效的資源利用和簡單的設計4.3處理機分配一、分配模型處理器分配：不可遷移當創(chuàng)建新進程時，系統(tǒng)決定為該進程分配處理機，一旦分配完畢，進程將一直在這臺處理機上運行，直至結(jié)束可遷移可以將已經(jīng)開始的進程遷移到別的處理機上繼續(xù)運行處理機分配的目標：CPU利用率最大化平均響應時間最小化/最小化響應率響應率：一臺機器上運

17、行一個進程的時間除以這個進程在一個無負載的標準處理機上運行時因該花的時間二、處理機分配算法的設計問題n確定性與啟發(fā)性算法確定性算法適用于當進程的所有行為都是實現(xiàn)知道的情況，但只有極少數(shù)系統(tǒng)的所有信息是預先知道的另一個 是系統(tǒng)的負載是完全不可預測的，工作請求可能每分鐘都會發(fā)生很大的變化，處理機分配只能使用特別的啟發(fā)性算法n集中式與分布式算法將所有信息搜集到一個地點便于做出更好的決定，但系統(tǒng)不夠健壯，中心機器的負載過重n最優(yōu)與次優(yōu)算法最優(yōu)解的計算代價比次優(yōu)解的計算代價要大得多n本地與全局算法本地算法：若機器的負載低于某個閥值，就讓該進程在這臺機器上運行，否則就清除該進程算法簡單，達不到最優(yōu)全局算法

18、：在對本地機器是否太忙作出決定前，能夠為該進程搜集到其他地方的信息，根據(jù)所有的負載情況決定是否在本機上運行該進程代價大n發(fā)送者發(fā)起與接收者發(fā)起算法發(fā)送者發(fā)起：將一些新進程卸載到其他機器上接收者發(fā)起：找到一臺愿意給它一些事情做的機器機器判斷其負擔重發(fā)送者尋找空閑機器機器宣告其可用接收者尋找工作做請求幫助機器負擔過重機器空閑三、處理機分配算法的實現(xiàn)問題測量負載的方法：根據(jù)機器的進程數(shù)量作為其負載情況根據(jù)運行或就緒狀態(tài)的進程計數(shù)采用CPU忙的時間所占的比例核心程序運行可能造成低CPU的利用率處理額外開銷：一個好的算法應該考慮到算法本身所占用的CPU時間、內(nèi)存的使用以及網(wǎng)絡帶寬復雜性：軟件的復雜性對系

19、統(tǒng)性能、正確性和健壯性的影響：隨機選擇一臺機器；算法1：直接發(fā)送算法2：詢問機器是否過載算法3：詢問K臺機器，確定它們的確切負載情況，新進程發(fā)送最小負載機器穩(wěn)定性不同機器異步運行，系統(tǒng)很少平衡四、處理機分配算法舉例n圖論確定性算法構(gòu)成系統(tǒng)的進程已知其CPU和內(nèi)存要求，并知道系統(tǒng)中每對進程之間的平均通信量，若系統(tǒng)的CPU數(shù)量小于進程數(shù)，則要求將多個進程指派到同一個CPU，算法的思想是使這種指派能夠使網(wǎng)絡的通信量最小化CPU1CPU2CPU3GEABCDIHF32345381224642313個處理機分配9個進程的兩種方法CPU1CPU2CPU3GEABCDIHF3234538122464231一

20、個集中式的算法協(xié)調(diào)者保存各工作站的使用情況表（每個工作站一個條目），根據(jù)使用情況表決定處理機的分配創(chuàng)建進程時，若創(chuàng)建進程的機器認為該進程應到其他的機器上運行，則將請求協(xié)調(diào)者分配處理機，若有則準許該請求，否則拒絕該請求當一個工作站用戶在其他機器上運行進程時，其罰分增加，每秒增加一個固定值，當有被拒絕的請求時，將從使用情況表中減去罰分，當沒有等待的請求，處理機也未被使用時，將移去一個值結(jié)論：一個等待了很久的、沒有使用任何處理機的申請將總會優(yōu)先于已經(jīng)占用了許多處理機的事情，從而公平地分配系統(tǒng)資源但中央節(jié)點可能在大型系統(tǒng)中成為瓶頸0進程2完成進程1完成進程2分配處理機進程1分配處理機進程2到達進程1到

21、達圖4-16 上下算法的操作時間層次式算法對每組K個工作，分配給管理者一個任務，跟蹤機器的使用情況，若系統(tǒng)比較大，則將會有更多的管理者，在眾多的管理者中設置高層管理者，形成層次關(guān)系問題：管理者崩潰避免單個管理者 發(fā)送者發(fā)起的分布式啟發(fā)性算法當創(chuàng)建進程時，創(chuàng)建進程的機器將對一個隨機選取的機器發(fā)送詢問，檢查該機器的負載是否低于某個閥值，若是則發(fā)送進程，否則選擇其他機器進行相應的動作，在N次詢問后還沒有合適的機器，算法將停止，新進程在它的機器上運行接收者發(fā)起的分布式啟發(fā)性算法當一個進程結(jié)束時，系統(tǒng)將檢查自己是否有足夠的工作可做，若不是，將隨機向一臺機器申請工作，若沒有，系統(tǒng)將繼續(xù)詢問其他機器，在連續(xù)

22、N此詢問都沒有申請到工作時，系統(tǒng)暫時停止申請，開始處理系統(tǒng)隊列中一個等待的進程，當這個進程結(jié)束時，再開始新的申請，若系統(tǒng)無事可做則將進入空閑狀態(tài)，一定的時間后，從新開始申請。投標算法思想：試圖將計算機系統(tǒng)變成小型的經(jīng)濟社會，由買賣雙方和需求關(guān)系確定的價格組成每個處理機在一個公共可讀文件中公布其近似價格，價格根據(jù)處理機速度、內(nèi)存容量、浮點運算能力以及其他特性決定處理機價格新進程通過查詢現(xiàn)在有誰在提供它所需要的服務，然后確定一個它可以支付的處理機集。通過計算，將從這個集合中選出一個最好的，根據(jù)應用程序的不同，最好的可以指最便宜的、最快的或最高性能價格比的，然后向第一選中的處理機發(fā)出出價處理機收集所

23、有出價后，作出決定，通知被選中的和未選中的進程，并開始執(zhí)行被選中的進程，公共文件中此處理機的價格將被更新為最新價格4.4 分布式系統(tǒng)調(diào)度時間片010AC1BD2AC3BD4AC5BD01234567012345處理機時間片兩個有聯(lián)系的作業(yè)不協(xié)調(diào)的運行情況8個處理機、每個分為8個時間片的調(diào)度矩陣4.5 容錯失效：系統(tǒng)不能達到應達到的技術(shù)要求一、組成部件錯誤暫時性錯誤發(fā)生一次后消失間斷性錯誤錯誤出現(xiàn)后，自動消失，然后又出現(xiàn)，自動反復永久性錯誤在錯誤部件修理好之前一直存在 和構(gòu)造容錯系統(tǒng)的目標是要確保即使在錯誤發(fā)生的情況下，整個系統(tǒng)也能夠繼續(xù)正常運行一個部件在規(guī)定的一秒時間內(nèi)的失效概率為p，則連續(xù)k

24、秒正常工作，然后再失效的概率為p(1-p)k 。失效發(fā)生的期望值為：ppkpkk/1)1 (11失效發(fā)生平均時間二、系統(tǒng)失效nFail-silent 錯誤失效的處理機只是停止工作，對接下來的輸入不作反應也不產(chǎn)生進一步的輸出nByzantine 錯誤出錯的處理機繼續(xù)運行，產(chǎn)生問題的錯誤答案，并可能和其他出錯的處理機一起“惡意”地工作，給人一重正常運行的假象處理Byzantine 錯誤比Fail-silent 錯誤更加困難三、同步系統(tǒng)與異步系統(tǒng)同步系統(tǒng)總能在一個已知的限定時間內(nèi)對一條消息進行響應異步系統(tǒng)無法確定一條消息的響應時間具體為多少四、使用冗余解決容錯的辦法是使用冗余技術(shù)：信息冗余增加額外數(shù)

25、據(jù)位以使出錯的數(shù)據(jù)完全恢復時間冗余動作執(zhí)行后，必要時可再次執(zhí)行物理冗余要使用額外物理部件以使整個系統(tǒng)能容許一些部件的損失或失效冗余處理機的辦法：主動復制 所有處理機在所有時間內(nèi)都是服務器使用主機后備 僅使用一個處理機作為服務器，當其失效時用另一個后備機器來替換兩種方法的問題：n需要復制的程度n沒有錯誤時，平均情況和最壞情況的性能1.發(fā)生錯誤時，平均情況和最壞情況下的性能五、使用主動復制方法的容錯使用物理冗余來提供容錯的技術(shù)ABCA1A2A3B1B2B3C1C2C3三模冗余系統(tǒng)需要多少份復制取決于想要達到的容錯量K容錯：系統(tǒng)可在k個部件出錯后仍能夠達到系統(tǒng)的設計要求而正常工作Fail-silen

26、t錯誤，則有k+1個部件可以達到要求Byzantine錯誤，則需要2k+1個部件才能達到k容錯前提條件：所有的請求達到所有服務器的順序應相同，即原子廣播問題六、使用主機后備的容錯在任何時刻都有一臺服務器完成所有的工作，若主服務器失效，后備的服務器將承擔其所有任務特點：在正常工作時，消息只發(fā)送給一個服務器，簡單，也不存在消息排序問題實際應用中所需機器也少得多在出現(xiàn)Byzantine錯誤時，產(chǎn)生假象，而恢復一個失效的主機也是復雜和耗時的客戶主服務器后備服務器1.請求2.工作6.響應5.確認4.工作3.更新圖、寫操作簡單主備份協(xié)議問題：主服務器在響應客戶請求前崩潰；沒問題，客戶超時重發(fā)主服務器在更新

27、前崩潰；后備機成為主機，客戶再次發(fā)送請求，但如處理具有副作用，則會產(chǎn)生問題系統(tǒng)在第四步后在6前崩潰客戶請求可能執(zhí)行三次處理操作主機-后備機的切換：n后備機定期向主機詢問狀態(tài)n后備機取代主機，主機變?yōu)楹髠錂Cn后備機強行停止或重啟主機n共享磁盤七、容錯系統(tǒng)中的協(xié)同一致分布式協(xié)同一致算法的目標是使所有無故障處理機對待某些問題的意見達到一致，并在有限的步驟內(nèi)進行處理存在的問題：n消息傳遞的可靠性n進程崩潰，是fail-silent 錯誤還是Byzantine錯誤1.系統(tǒng)是同步還是異步兩軍作戰(zhàn)問題要求：兩對蘭色軍隊同時攻擊紅色軍隊，才能取勝，否則失敗問題：利用不可靠通道進行通信，在消息傳遞正常的情況下兩

28、進程達成協(xié)同一致是不可能的Byzantine將軍問題N個藍軍中有m個叛徒，采用可靠通信機制進行通信，要求忠誠將軍達成協(xié)同一致問題可變化為N個將軍交換各自的軍隊人數(shù)圖、3個忠誠將軍和一個叛變將軍的Byzantine將軍問題(a) 各個將軍通報各自部隊的戰(zhàn)斗力（1K為單位）(b) 每個將軍根據(jù)（a）匯編出的向量(c) 每個將軍從第二步得到的向量1234有問題的處理器XYZ1 Got(1,2,x,4) 1 Got 2 Got 3 Got2 Got(1,2,y,4) (1,2,y,4) (1,2,x,4) (1,2,x,4)3 Got(1,2,y,4) (a,b,c,d) (e,f,g,h) (1,2

29、,y,4)4 Got(1,2,z,4) (1,2,y,4) (1,2,z,4) (i,j,k,l)abc步驟：n每個將軍發(fā)送可靠消息給其他所有的將軍，聲明自己的軍隊人數(shù)n將第二步聲明的結(jié)果收集組成向量形式n每個將軍將收集的向量傳遞給其他每一個將軍1.每個將軍檢查所有新接收向量的每一個元素，若有某個值占多數(shù)，則將該值放入結(jié)果向量中圖、2個忠誠將軍和一個叛變將軍的Byzantine將軍問題沒有一個忠誠將軍認為元素1，2，3中占多數(shù)，無法判斷123有問題的處理器XY1 Got(1,2,x) 1 Got 2 Got 3 Got2 Got(1,2,y) (1,2,y) (1,2,x) (1,2,x)3

30、Got(1,2,y) (a,b,c) (e,f,g) (1,2,y)abc結(jié)論：n有m個處理機出錯的系統(tǒng)中要實現(xiàn)協(xié)同一致，只有當有2m+1個正常處理機時才可能，處理機總數(shù)為3m+1。只有大于2/3的處理機正常工作時，協(xié)同一致才可能。n對一個具有異步式處理機和對傳輸時延沒有限制的分布式系統(tǒng)，由于不可區(qū)別特別慢的或失效的處理機，因此，哪怕只有一個處理機失效，協(xié)同都是不可能的。4.6 實時分布式系統(tǒng)一、什么是實時系統(tǒng)實時系統(tǒng)同外部世界交互，其中涉及時間，當某個激勵出現(xiàn)時，系統(tǒng)必須以一定的方式和在限定的時間內(nèi)響應，若返回結(jié)果正確，但已超時，系統(tǒng)也認為失效。實例：播放音樂要求實時許多涉及外部世界的其他應

31、用，也是實時的實時系統(tǒng)的激勵通常是周期的，有時激勵是非周期的，激勵也可是突發(fā)性的在大的周期性系統(tǒng)中，其復雜性表現(xiàn)于存在著多種事件分布式實時系統(tǒng)的構(gòu)造CCDevCDevCDevCDev傳感器執(zhí)行機構(gòu)網(wǎng)絡根據(jù)時限的嚴格程度和超過限制時間的后果的嚴重性。通常將實時系統(tǒng)分為：軟實時系統(tǒng)可以偶爾錯過時限硬實時系統(tǒng)不允許任何一個實時請求超過時限對于實時系統(tǒng)的誤解：n是用匯編代碼來編寫的驅(qū)動程序n是快速計算1.告訴的計算機將使實時系統(tǒng)過時無用二、設計問題時鐘同步在多計算機情況下，每臺機器的時間不一樣，保持時間同步是一個關(guān)鍵問題事件觸發(fā)系統(tǒng)與時間觸發(fā)系統(tǒng)事件觸發(fā)系統(tǒng)當許多事件一次性發(fā)生時，引起大量的中斷，產(chǎn)生

32、時間風暴，可能導致計算機崩潰在低負荷時會更快響應，但在高負載時會更加過載時間觸發(fā)系統(tǒng)不會存在事件風暴，但對于時間間隔的選取必須非常小心適應于相對靜態(tài)環(huán)境預知性理想情況下，設計時應清楚系統(tǒng)能夠滿足的所有時限，甚至是最大負載時限。容錯性許多實時系統(tǒng)控制著安全關(guān)鍵設備，因此容錯是非常普遍的問題，可以采用主動復制，但僅限于不存在有擴展的協(xié)議讓所有的部分在任何時間，任何事件上都必須進行協(xié)同一致。主機后備方法因機器切換時間開銷可能會超過時限而很少使用容錯實時系統(tǒng)必須能同時處理最大量設備失效和最大量負載的情況可安全停機的fail-safe系統(tǒng)：當出現(xiàn)嚴重問題時能夠強制停止執(zhí)行語言支持設計專用程序設計語言專用

33、語言應在編譯時能計算出每個任務的最大執(zhí)行時間語言應有表達最小和最大延遲的方法能表示當期待的時間在限定時間內(nèi)未發(fā)生時該做什么的方法提供處理周期性事件的語句Every(25 msec)三、實時通信預知性與確定性是實時系統(tǒng)成功的真正關(guān)鍵在實時系統(tǒng)中實現(xiàn)可預知性，要求處理機之間的通信是預知的，但LAN網(wǎng)絡協(xié)議（以太網(wǎng)）中未提供傳輸時間的上限，因此不可能事先給出最大時限令牌環(huán)LAN：網(wǎng)絡中有K臺機器，每臺機器在捕獲令牌時最多可發(fā)送含n個字節(jié)的信包，因此可知時間上限，同時也能處理多優(yōu)先級系統(tǒng)的通信問題TDMA（時分多路）協(xié)議，通信以固定大小的禎組織，含n個時隙，每個時隙分給一個處理機進行發(fā)送信包廣域網(wǎng)實時分布式系統(tǒng)存在信包丟失率相對較高的問題，標準協(xié)議處理方法：在傳送每一個傳輸信包時設置一個定時器，若定時器在信包確認消息收到之前走完，就重發(fā)信包。這種無限的傳輸延遲是無法接受的發(fā)送者的簡單解決辦法：總傳輸信包兩次（或多次），若可選擇，最好是通過相互獨立的連接浪費帶寬，但可靠時間觸發(fā)協(xié)議(TTP)TTP應用在MARS實時系統(tǒng)MARS系統(tǒng)的節(jié)點包含多個CPU，對外呈現(xiàn)單一的容錯，fail-silent型節(jié)點，節(jié)點間通過兩個可靠的和獨立的TDMA廣播網(wǎng)連接，所有信包在兩個網(wǎng)中并行發(fā)送。MARS是一個時間觸發(fā)系統(tǒng)，時鐘必須同步所有