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

第4章分布式進程和處理機中國科技大學軟件學院丁箐1主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)2主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)34.1進程和線程現(xiàn)代操作系統(tǒng)使用進程加載程序線程能在進程內創(chuàng)建別的進程每個線程擁有自己的Stack一個進程內的所有線程共享代碼和數(shù)據段StackthreadMain()StackthreadStackthreadCodesegmentDatasegment4進程和線程多個進程通過系統(tǒng)進程間通信原語，如：信號量、管程、消息進行通信。多個線程可以通過共享內存通訊線程進程；進程處理機；5進程模型例：4個程序組成的多道程序邏輯上，4個獨立的、順序的進程的概念模型物理上，任意時刻只有一個是活動的6操作系統(tǒng)的進程結構調度器：處理分時中斷、調度7進程的狀態(tài)1–進程a等待輸入而阻塞，2–調度器選擇另一個就緒進程b3–啟動進程b運行4–當輸入完成后,進程a進入就緒隊列8進程的實現(xiàn)—進程表進程管理內存管理文件管理RegistersProgramcounterProgramstatuswordStackpointerProcessstatePrioritySchedulingparametersPointertotextsegmentPointertodatasegmentPointertostacksegmentRootdirectoryWorkingdirectoryFiledescriptorsUserIDGroupIDProcessIDParentprocessProcessgroupSignalsStartingtimeCPUtimeusedChildren’sCPUtimeTimeofnextalarm9線程——效益和風險效益增加性能和資源利用率（甚至在單處理機系統(tǒng)）？風險增加復雜性調試困難Forhidinglatencyandincreasingthroughput10多線程應用常遭遇的問題Wheretothread?Howlongwouldittaketothread?Howmuchre-design/effortisrequired?Isitworththreadingaselectedregion?Whatshouldtheexpectedspeedupbe?Willtheperformancemeetexpectations?Willitscaleasmorethreads/dataareadded?Whichthreadingmodeltouse?11線程模型每個線程可共享所屬進程的資源12線程模型每個線程擁有自己的棧局部變量、返回地址13線程的用途例1：包含3個線程的字處理器14例2:多線程的Web服務器15多線程設計方法學Partitioning區(qū)分計算和數(shù)據Communication在計算間共享數(shù)據Agglomeration任務分組以提高性能Mapping分配任務到處理機和線程16并行編程模型功能分解任務并行劃分計算，關聯(lián)數(shù)據相同問題的獨立任務數(shù)據分解不同數(shù)據上執(zhí)行相同操作將數(shù)據劃分為片，關聯(lián)計算17多線程示例代碼

(a):分派者線程（dispatcher）源代碼

(b):工作者線程（worker）源代碼18線程與進程的三種組織

（a）分派者/工作者模型（b）團隊模型（c）管道模型19LAME（MP3Encoder）PipelineStrategy20服務器組織的比較模式并行

非阻塞式系統(tǒng)調用性能

編程容易程度單線程進程

低√多線程進程√

高√有限狀態(tài)機√√高

21線程包的設計線程包：為用戶編程提供的線程操作原語程序庫線程的管理靜態(tài)線程：線程的數(shù)量在編譯時預先確定動態(tài)線程：在運行時隨時創(chuàng)建或撤銷線程共享數(shù)據的存取：臨界區(qū)方法編程

22線程的互斥控制小型互斥變量mutexlockunlock用于進/出臨界區(qū)條件變量用于對資源的長期等待與mutexlockmutex;checkdatastructures;while(resourcebusy)wait(conditionvariable);markresourceasbusyunlock;

（a）獲得資源lockmutex;markresouceasfree;unlockmutex;wakeup(conditionvariable);（b）釋放資源，喚醒線程23使用全局變量線程之間的沖突

例：全局變量error24線程私有全局變量

解決方法：設置私有的全局變量引入新的庫過程

例：

提供庫函數(shù)1.創(chuàng)建一個線程的全局變量

create_global(“bufptr”);2.設置一個全局變量

set_global(“bufptr”,&buf)3.讀一個全局變量

bufptr=read_global(“bufptr”)#pragma

ompparallelforprivate()25實現(xiàn)線程：在用戶空間

用戶級的線程包能夠在不支持線程的操作系統(tǒng)中實現(xiàn)

切換效率高允許每一個進程有自已定制的調度算法26實現(xiàn)線程：在內核空間當一個線程想去創(chuàng)建一個新線程或撤消已存在的線程時，它發(fā)出一個內核調用，由它完成創(chuàng)建和回收工作。

27實現(xiàn)線程：調度者行為

將用戶級線程多個轉接到內核線程上通過避免在用戶空間和內核空間之間不必要的轉換來實現(xiàn)高效率

28例:調度器激活方法目標

：既有用戶進程的優(yōu)點(高性能、靈活),又有內核進程的優(yōu)點（實現(xiàn)簡單）。

方案：避免不必要的“用戶/內核”間的切換實現(xiàn)：Upcall機制：下層內核可調用上層用戶運行系統(tǒng)29例:調度器激活方法算法：內核為每個進程分配虛擬的處理機；由進程的用戶運行系統(tǒng)為線程分配處理機當線程x在內核被阻塞后，調度器Upcall其運行系統(tǒng)，重新調度其他就緒線程當線程x可運行后，調度器Upcall其運行系統(tǒng)，重新調度當產生硬件中斷后，如果與進程A有關，則Upcall其運行系統(tǒng)，重新調度30線程和遠程過程調用（RPC）

如何加速RPC？大量的RPC調用是調用與它們在同一機器上的進程——共享參數(shù)堆棧彈出線程（pop-upthread）31Pop-Up式線程與RPC作用：負責接收消息。例：receive_msg(addr,&buf)

（a）消息到達前（b）消息到達后32Unix中的線程API調用33Windows中的進程管理基本概念34Job、Process、Thread的相互關系35Win32的API調用36主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)374.2系統(tǒng)模型工作站模型無盤工作站有盤工作站38工作站上磁盤的作用對文件服務器的依賴程度硬盤使用優(yōu)點缺點無盤成本低,軟硬件容易維護,對稱靈活網絡使用比較頻繁,文件服務器可能會成為瓶頸分頁，可擦除文件和無盤相比,使網絡的負擔更輕由于需要大量的磁盤,費用比較高分頁，過期文件，二進制文件使網絡的負擔更輕費用比較高,二進制的更新比較復雜分頁，過期文件，二進制文件，緩沖減輕網絡的負擔,也減輕文件服務器的負擔費用比較高,存在cache一致性的問題完全本地文件系統(tǒng)幾乎沒有網絡負擔,消除了對文件服務器的需要失去了透明性39使用空閑工作站

怎樣找出一臺空閑機器？服務器驅動客戶端驅動遠程進程怎樣透明地運行？如果（空閑）機器的主人回來重新使用它時怎么辦？什么也不做殺掉正在進入的進程移植到另一臺機器上去40空閑處理機遠程執(zhí)行：rshmachinecommand

基于注冊表算法41工作站管理處理機池模型42工作站管理排隊模型平均響應時間T=1/(λ–μ)n臺處理機平均響應時間T1=T/n計算機完成工作用戶用戶每秒共產生μ個請求系統(tǒng)每秒能處理λ個請求43工作站管理混合模型：前臺交互式任務：個人工作站后臺任務：處理機池44主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)45分配模型處理機分配策略

非遷移型遷移型分配目標最大CPU利用率最快響應時間響應比：實際運行時間/實際需要時間負載平衡46在兩個處理機中兩個進程的響應時間

分配方案1：處理機1運行進程A，處理機運行進程B，

平均響應時間

=（10＋8）/2＝9分配方案2：處理機1運行進程B，處理機運行進程A，

平均響應時間

=（30＋6）/2＝18處理機1

10MIPS處理機2

100MIPS沒有隊列5秒隊列進程A(1億條指令)B(3億條指令)10秒30秒6秒8秒47處理機分配設計確定性vs

啟發(fā)式（試探性）集中式vs

分布式最優(yōu)vs

較優(yōu)局部的vs

全局的發(fā)送者發(fā)起的vs

接收者發(fā)起的

48

(a)發(fā)送者尋找空閑機器(b)接收者尋找工作做49處理機分配算法的實現(xiàn)問題

如何測量負載情況？如何處理額外開銷？復雜性問題50Eager的啟發(fā)式算法所有的機器測量自己的負載以決定自己是否欠載。每當創(chuàng)建一個新的進程時，創(chuàng)建它的機器檢查自己是否過載，如果是，那么它將搜索一個能夠運行該進程的遠程機器。

轉發(fā)法：隨機選擇一臺機器A，向它發(fā)送新進程。如果A已經過載，A也同樣隨機選擇另一臺機器B，向B發(fā)送進程。查詢法：隨機選擇一臺機器A，向它發(fā)送一個負載情況詢問。如果欠載，A就會得到這個進程；否則，將重新選擇一臺機器。比較法：詢問k臺機器，確定它們的確切負載情況。將新過程傳送到負載最小的那臺機器上。51基于圖的確定性算法例：3個處理機，9個進程方案A:通信量=(3＋2＋4＋4)＋(2＋8＋5＋2)＝30方案B:通信量=(3＋2＋4＋4)＋(3＋5＋5＋2)＝2852集中的啟發(fā)式的up-down算法目標：工作站公平地享用系統(tǒng)的計算能力使用情況表：〉0表示使用資源；<0表示需要系統(tǒng)資源，0為初始值時間P1到達P1分配到處理器P2到達P2分配到處理器P1完成P2完成使用情況表積分53層次式的算法

主任委員會部門領導工作人員54發(fā)送者/接收者算法發(fā)送者發(fā)起的分布式啟發(fā)性算法負載十分重的情況下，額外開銷接收者發(fā)起的分布式啟發(fā)性算法系統(tǒng)欠載時使系統(tǒng)開銷增大55投標算法（經濟模型）User-relatedparameters:price,resourcequantity,funds,anduser-specifiedparameters…方式：Vecteryauction、CDA等等56主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)57協(xié)同調度（co-scheduling）將一組協(xié)同進程安排在不同處理機的同一時間片內以產生最小的時間延遲。ACBDACBDACBD0101234501012345243567（a）簡單輪轉（b）分組調度處理器處理器時間片時間片58進一步閱讀

M.Maheswaran,S.Ali,H.J.Siegel,D.Hensgen,andR.F.Freund,“Dynamicmatchingandschedulingofmeta-tasksonheterogeneouscomputingsystems,”JournalofParallelandDistributedComputing,Vol.59,No.2,Nov.1999,pp.107–131.J.B.Weissman,“Schedulingmulti-componentapplicationsinheterogeneouswide-areanetworks,”9thIEEEHeterogeneousComputingWorkshop(HCW’00),May2000.

Buyya,R.,Abramson,D.,andGiddy,J.,StockingerH.,EconomicModelsforResourceTradinginaServiceOrientedGridComputingEnvironments,MonashUniversity,http:///ecogrid/,Oct2000(inpublication)ChunmingChen,Muthucumaru

Maheswaran,andMichaelToulouse,“Supportingco-allocationinanauctioningbasedresourceallocatorforGridsystems,”11thIEEEHeterogeneousComputingWorkshop(HCW2002),Apr.2002,(toappear).59主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)604.5容錯基本概念差錯（error）：如程序bug故障（fault）：短暫型、間歇型、永久型失效（failure）失效模型p為每秒失效概率平均失效時間=Σkp(1-p)k-1=1/p61系統(tǒng)失效——在部件出錯時仍能正常工作

故障類型Fail-silent（Fail-stop）故障拜占庭（Byzantine）故障系統(tǒng)類型同步系統(tǒng)：在規(guī)定時間內有響應異步系統(tǒng)：設一個上限62冗余技術

冗余類型信息冗余：海明碼時間冗余：原子事務處理物理冗余：雙機組織冗余處理機的方法主動復制（activereplication）主機后備(primarybackup)

設計問題需要復制的程度無故障時，平均情況和最壞情況下的系統(tǒng)性能有故障時，平均情況和最壞情況下的系統(tǒng)性能

63主動復制容錯技術（使用物理冗余來提供容錯）相同的部件K-容錯度：在有k個部件發(fā)生故障時，系統(tǒng)仍能正確運行Fail-stop型故障：k+1冗余度拜占庭型故障：2k+1冗余度有限狀態(tài)機方法：接收請求，給出應答

所有的請求到達所有服務器的順序應相同原子廣播問題（atomicbroadcastproblem）對所有請求做全局計數(shù)編號Lamport邏輯時鐘

64主動復制方法三模冗余方法65主備份方法（primarybackup）主服務器失效，則后援服務器接替其任務

接管模型客戶主系統(tǒng)備份系統(tǒng)1.請求2.執(zhí)行3.更新

4.執(zhí)行

6.應答

5.確認66協(xié)同一致問題消息傳遞總是可靠嗎？進程會崩潰嗎？若會，是fail_silent錯誤還是byzantine錯誤？系統(tǒng)是同步還是異步?67兩軍問題通信不可靠處理機出錯30005000300012368Lamport遞歸算法拜占庭將軍問題例：3個忠誠將軍，1個叛變將軍結果：（1，2，未知，4）69Lamport遞歸算法若三個將軍中，有兩個忠誠將軍，一個叛變將軍，則不能判斷出哪個將軍叛變。若要有m個處理機出錯的系統(tǒng)實現(xiàn)協(xié)同一致，最少要有2m＋1個正常處理機。處理機總數(shù)為3m+170主要內容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調度4.5

容錯4.6實時分布式系統(tǒng)714.6實時分布式系統(tǒng)什么是實時系統(tǒng)：當某個激勵出現(xiàn)時，系統(tǒng)必須以一定的方式在限定的時間內響應它。如果超時，即使結果正確，也認為是系統(tǒng)失效實時系統(tǒng)類型軟實時系統(tǒng)：允許偶爾錯過截至時間（deadline）硬實時系統(tǒng)：嚴格不允許，如飛機導航72實時事件流事件類型周期的、非周期的、突發(fā)的例：3個事件流+1個意外事件時間ABCABCABCABCABACBACBAACBX無法預料的事件A的周期B的周期C的周期工作負荷空閑73分布式實時系統(tǒng)結構DevCDevCDevCDevCDevCDevCC外部設備計算機網絡執(zhí)行機構傳感器74對實時系統(tǒng)的誤解誤解之一：實時系統(tǒng)就是用匯編代碼來編寫的驅動程序。誤解之二：實時計算是快速計算。誤解之三：高速的計算機將使實時系統(tǒng)過時無用。75設計問題：事件觸發(fā)系統(tǒng)當一個重要的外部事件觸發(fā)時，它被傳感器察覺到，并導致與傳感器相連的CPU得到一個中斷請求。通常是中斷驅動的。主要問題當事件風暴（eventshower）發(fā)生時，在重載情況下會失效。76設計問題：時間觸發(fā)系統(tǒng)每⊿T毫秒產生一次時鐘中斷。在每一次時鐘滴答時，對（選定的）傳感器進行采樣，并且驅動（特定的）執(zhí)行機構。中斷僅在時鐘滴答時發(fā)生。⊿T的選擇必須非常小心地選擇。若⊿T太小，系統(tǒng)將產生許多時鐘中斷，將浪費大量的時間來響應它們77設計問題：結論：事件觸發(fā)的設計使得在低負載時會更快的響應，但在高負載時，會更加過載，并有可能崩潰失效。時間觸發(fā)的設計有相反的特征，并且僅適用于相對靜態(tài)環(huán)境，在這種環(huán)境中，事先就已經知道了系統(tǒng)大量的行為。78設計問題：可