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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、進(jìn)程達(dá)成協(xié)同一致是不可能的Byzantine將軍問題N個藍(lán)軍中有m個叛徒，采用可靠通信機(jī)制進(jìn)行通信，要求忠誠將軍達(dá)成協(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將軍問題沒有一個忠誠將軍認(rèn)為元素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個處理機(jī)出錯的系統(tǒng)中要實現(xiàn)協(xié)同一致，只有當(dāng)有2m+1個正常處理機(jī)時才可能，處理機(jī)總數(shù)為3m+1。只有大于2/3的處理機(jī)正常工作時，協(xié)同一致才可能。n對一個具有異步式處理機(jī)和對傳輸時延沒有限制的分布式系統(tǒng)，由于不可區(qū)別特別慢的或失效的處理機(jī)，因此，哪怕只有一個處理機(jī)失效，協(xié)同都是不可能的。4.6 實時分布式系統(tǒng)一、什么是實時系統(tǒng)實時系統(tǒng)同外部世界交互，其中涉及時間，當(dāng)某個激勵出現(xiàn)時，系統(tǒng)必須以一定的方式和在限定的時間內(nèi)響應(yīng)，若返回結(jié)果正確，但已超時，系統(tǒng)也認(rèn)為失效。實例：播放音樂要求實時許多涉及外部世界的其他應(yīng)

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

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

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