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

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

系統(tǒng)模型4.3

處理機分配4.4

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

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

系統(tǒng)模型4.3

處理機分配4.4

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

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

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

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

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

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

編程容易程度單線程進程

低√多線程進程√

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

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

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

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

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

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

例：

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

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

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

bufptr=read_global(“bufptr”)#pragma

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

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

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

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

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

28例:調(diào)度器激活方法目標

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

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

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

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

系統(tǒng)模型4.3

處理機分配4.4

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

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

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

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

系統(tǒng)模型4.3

處理機分配4.4

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

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

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

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

平均響應(yīng)時間

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

平均響應(yīng)時間

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

10MIPS處理機2

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

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

分布式最優(yōu)vs

較優(yōu)局部的vs

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

接收者發(fā)起的

48

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

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

轉(zhuǎn)發(fā)法：隨機選擇一臺機器A，向它發(fā)送新進程。如果A已經(jīng)過載，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層次式的算法

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

系統(tǒng)模型4.3

處理機分配4.4

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

容錯4.6實時分布式系統(tǒng)57協(xié)同調(diào)度（co-scheduling）將一組協(xié)同進程安排在不同處理機的同一時間片內(nèi)以產(chǎn)生最小的時間延遲。ACBDACBDACBD0101234501012345243567（a）簡單輪轉(zhuǎn)（b）分組調(diào)度處理器處理器時間片時間片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主要內(nèi)容4.1進程和線程4.2

系統(tǒng)模型4.3

處理機分配4.4

分布式系統(tǒng)中的調(diào)度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ī)定時間內(nèi)有響應(yīng)異步系統(tǒng)：設(shè)一個上限62冗余技術(shù)

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

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

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

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

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

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

4.執(zhí)行

6.應(yīng)答

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

系統(tǒng)模型4.3

處理機分配4.4

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

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