分布式系統(tǒng)與WEB服務(wù)課件

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,南京理工大學(xué)計算機(jī)學(xué)院,分布式系統(tǒng)與,WEB,服務(wù),第三章 分布式系統(tǒng)的同步 和進(jìn)程,第三章 分布式系統(tǒng)的同步 和進(jìn)程,3,1,時鐘同步,分布式算法的主要特征：,相關(guān)信息分布在多臺機(jī)器上,進(jìn)程僅依據(jù)局部的信息作出決定,一臺機(jī)器的故障不應(yīng)引起整個系統(tǒng)的失敗,沒有共用的全局時鐘。,31 時鐘同步 分布式算法的主要特征：,1,邏輯時鐘,先看一個例子,:,0,6,12,18,24,30,36,42,48,54,60,0,8,16,24,32,40,48,56,64,72,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,三個有自己時鐘的進(jìn)程,時鐘不同,運(yùn)行的結(jié)果是消息,C,在時間,60,上被發(fā)送,卻在時間點(diǎn),54,上到達(dá),1邏輯時鐘000ABCD三個有自己時鐘的進(jìn)程,時鐘不同,Lamport,的算法以,”,先于,”,關(guān)系,為基礎(chǔ)，每個消息都攜帶它的發(fā)送時間,當(dāng)它到達(dá)目的地時，如果目的地的時間早于它的發(fā)送時間，那么就把目的地的時間向前拔,至少要比發(fā)送時間大,1,個單位,.,0,6,12,18,24,30,36,42,48,70,76,0,8,16,24,32,40,48,61,69,77,85,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,用,Lamport,的算法糾正時鐘,Lamport的算法以”先于”關(guān)系為基礎(chǔ)，每個消,該算法解決了全局時鐘問題，它的條件就是兩個相關(guān)事件之間必須至少相差一個時間,2,時鐘同步算法,邏輯時鐘只給出事物的相對時間,與真實(shí)時間并不對應(yīng),故要引入外部物理時鐘,常用的時鐘同步算法,:,克里司帝安,(CRISTIAN),算法,具有國家標(biāo)致時間接收器的機(jī)器,注意,:,調(diào)整的方法,通過調(diào)節(jié)單位時間內(nèi)的中斷的時間,來逐步完成時鐘的調(diào)整,.,該算法解決了全局時鐘問題，它的條件就,伯克利算法,計算平均時間,它是一個集中式算法,不能在大規(guī)模的分布式系統(tǒng)中使用,原理,:,定期輪詢每臺機(jī)器的時間,由結(jié)果計算平均時間,各機(jī)器依此調(diào)整時間,.,3,同步時鐘的具體使用,至多一次消息傳送,消息的時間戳比存儲的時間戳的值早,就拒絕接受該消息,伯克利算法,基于時鐘的緩沖存儲器（,CACHE,）的一致性,使用,CACHE,會出現(xiàn)一致性問題，原解決的方法,:,區(qū)分讀寫緩存,現(xiàn)在可用同步時鐘來解決。即通過提供有效期（,利用有效的租約）,來控制,CACHE,一致性問題。,基于時鐘的緩沖存儲器（CACHE）的一致性,3.2,互斥操作,有多個進(jìn)程的系統(tǒng)經(jīng)常會碰到臨界區(qū)的操作。當(dāng)一個進(jìn)程要訪問某個共享數(shù)據(jù)時，它要先進(jìn)人臨界區(qū)進(jìn)行互斥操作，確保沒有別的進(jìn)程同時訪問該數(shù)據(jù)。在單機(jī)系統(tǒng)中，臨界區(qū)可以用信號燈、管程來實(shí)現(xiàn)。那么在分布式系統(tǒng)中，由于,不能共享主存,，怎么實(shí)現(xiàn)臨界區(qū)和互斥操作呢,?,下面我們討論幾種算法。,集中式算法,該方法就是模擬單機(jī)系統(tǒng),指定一個管理員進(jìn)行許可管理,該算法保證了互斥,每個臨界區(qū)只需三條消息,(,申請,許可,釋放,),3.2 互斥操作 有多個進(jìn)程的系統(tǒng)經(jīng)常,1,0,2,OK,請求,C,管理員,隊列空,管理員,1,0,2,不回答,請求,C,隊列空,1,0,2,OK,釋放,C,管理員,隊列空,2,(A),進(jìn)程,1,向管理員請求進(jìn)入臨界區(qū),得到許可,(B),進(jìn)程,2,向管理員請求進(jìn)入臨界區(qū),管理員不回答,(C),進(jìn)程,2,向管理員請求進(jìn)入臨界區(qū),管理員許可,缺點(diǎn),:,集中式算法管理員是系統(tǒng)的瓶頸,102OK請求C管理員隊列空管理員102不回答請求C隊列空1,分布式算法,算法的條件,:,系統(tǒng)中的事件必須有全局的順序,算法的工作過程如下,:,當(dāng)一個進(jìn)程要進(jìn)入臨界區(qū)時，它構(gòu)造一條包括臨界區(qū)名、進(jìn)程號和當(dāng)前時間的請求消息，然后把該消息廣播給其他的所有進(jìn)程。這里假設(shè)，消息的發(fā)送是可靠的。,當(dāng)一個進(jìn)程收到請求后，根據(jù)它的狀態(tài)采取相應(yīng)的動作：,(1),當(dāng)接收者不在臨界區(qū)，并且也不想進(jìn)入臨界區(qū)，就應(yīng)答發(fā)送者,OK,消息。,(2),如果接收者已經(jīng)在臨界區(qū)中，它不回答僅僅把請求加入隊列。,(3),如果接收者不在臨界區(qū)，但它也想進(jìn)入臨界區(qū)，就要將收到消息的時間戳和它廣播消息的時間戳比較,.,如果到來的消息時間戳早，接收者回答發(fā)送者,OK,消息；反之接收者把到來的請求加入隊列，不回答,.,分布式算法,在發(fā)完進(jìn)入臨界區(qū)請求后，進(jìn)程將等待所有的允許消息，一旦得到許可，就可進(jìn)入臨界區(qū)，當(dāng)退出時向隊列中的所有進(jìn)程發(fā),OK,消息，并將它從隊列中刪除。,所有進(jìn)程都要參與決定是否進(jìn)入臨界區(qū)，若有進(jìn)程不能做，算法將出錯。,由于所有進(jìn)程都要參加算法，所以比集中式算法慢，復(fù)雜，開銷大。,改進(jìn)算法：,不需所有進(jìn)程同意，部分回答,OK,即可,令牌環(huán)算法,進(jìn)程只有擁有令牌時,才能進(jìn)入臨界區(qū),一個進(jìn)程從相鄰的進(jìn)程收到令牌時先檢查自己是非要進(jìn)入臨界區(qū),;,如果要,就進(jìn)入,否則就將令牌傳遞給下一個進(jìn)程,.,缺點(diǎn),:,令牌可能丟失且檢測困難，一個要進(jìn)入臨界區(qū)的進(jìn)程最差情況下要等待其他進(jìn)程進(jìn)入和退出臨界區(qū)所用時間總和,在發(fā)完進(jìn)入臨界區(qū)請求后，進(jìn)程將等待所有的允許消息，,三種算法的特點(diǎn)比較,集中式算法簡單、高效，每次進(jìn)入和離開臨界區(qū)只需,3,次消息傳遞：,請求、許可；釋放,，分布式算法中，,n,個進(jìn)程需要,(n-1),個請求和,(n-1),個許可，總共要,2(n,1),個消息。在令牌環(huán)算法中，所需的消息數(shù)是不固定的。如果每個進(jìn)程都要進(jìn)入臨界區(qū)，那么每個令牌都有一次進(jìn)人和退出，平均每次進(jìn)入有,個消息傳遞；如果令牌被一個進(jìn)程占有很長時間，那么進(jìn)入臨界區(qū)需要的消息就不確定。,進(jìn)程從它發(fā)出進(jìn)入臨界區(qū)的請求到它進(jìn)入臨界區(qū)的時間延遲在三個算法中是不同的,當(dāng)臨界區(qū)很短并且使用頻率很低時，進(jìn)入臨界區(qū)時間延遲的決定因素是進(jìn)人臨界區(qū)的控制機(jī)制當(dāng)臨界區(qū)很長并且使用的頻率很高時，決定因素在于等待時間，消息數(shù)就能說明這一點(diǎn)。,這三種算法出現(xiàn)故障時,都會有很大影響,要避免系統(tǒng)的崩潰,須注意,:,在容錯系統(tǒng)中,次三種算法都不適用,.,三種算法的特點(diǎn)比較,3.3,選舉算法,在分布式系統(tǒng)中，大多數(shù)算法要求有一個進(jìn)程充當(dāng)管理員或初始啟動者等特殊角色。前面幾個算法就有這樣的例子。一般來說，由哪個進(jìn)程充當(dāng)特定角色無關(guān)緊要，但是必須有一個進(jìn)程做這個工作。下面我們來看如何選一個進(jìn)程擔(dān)當(dāng)特定角色。,選舉算法的目的是當(dāng)選舉完成后，能夠讓所有的進(jìn)程知道誰是管理員,.,3.3選舉算法 在分布式系統(tǒng)中，大多,1.,霸道算法,該算法提出。當(dāng)一個進(jìn)程,P,注意到管理員不再對請求作出反應(yīng)時，它就開始選舉進(jìn)程,P,執(zhí)行下列步驟：,(1),向所有,進(jìn)程號比它大,的進(jìn)程發(fā)送,ELECTION,消息；,(2),如果沒有進(jìn)程響應(yīng)，進(jìn)程,P,成為管理員；,(3),如果有進(jìn)程響應(yīng)，該響應(yīng)進(jìn)程成為管理員，,P,結(jié)束選舉。,注意：,一個進(jìn)程只能從號碼比它小的進(jìn)程處得到一個選擇消息,1.霸道算法,2,0,5,3,6,4,1,7,(A),進(jìn)程,4,啟動選舉,2,0,5,3,6,4,1,7,(B),進(jìn)程,5,6,響應(yīng),讓,4,停止,2,0,5,3,6,4,1,7,(C),進(jìn)程,5,6,都啟動選舉,2,0,5,3,6,4,1,7,(D),進(jìn)程,6,讓進(jìn)程,5,停止選舉,2,0,5,3,6,4,1,7,(E),進(jìn)程,6,成為管理員,發(fā)通知,霸道算法圖示,20536417(A)進(jìn)程4啟動選舉20536417(B)進(jìn),2.,環(huán)形算法,這個算法使用環(huán)，但不是令牌環(huán)。,這里假定所有的進(jìn)程都是有序號的，即每個進(jìn)程都知道它的后繼進(jìn)程。當(dāng)一個進(jìn)程發(fā)現(xiàn)管理員不能工作時，它把包含其進(jìn)程號的,ELECTION,消息發(fā)給它的后繼進(jìn)程；接收消息的進(jìn)程再向后繼進(jìn)程發(fā)送,ELECTION,消息。如果接收進(jìn)程沒有反應(yīng)，發(fā)送消息的進(jìn)程便向下一個進(jìn)程發(fā)消息。每一次發(fā)送,ELECTION,，進(jìn)程都要將自己的進(jìn)程號加入消息。,2,0,4,6,5,1,3,7,使用環(huán)形選舉算法,選舉消息,選舉消息,2,3,2,5,5,6,5,6,0,出現(xiàn)故障的管理員,2.環(huán)形算法20465137使用環(huán)形選舉算法,最后，第一個發(fā)出該選舉（,ELECTION,）消息進(jìn)程收到該消息,再將其轉(zhuǎn)換為協(xié)調(diào)（,COORDINATOR,）消息后，再循環(huán)一周,通知誰是管理員，誰是組成員，,這時消息包中進(jìn)程號最高的進(jìn)程將成為管理員。,當(dāng)這個消息循環(huán)一周后，由發(fā)送進(jìn)程把它從網(wǎng)上清除。,圖中,2,和,5,都發(fā)現(xiàn),7,失效，分別建立選舉消息，兩條消息都沿環(huán)運(yùn)行，結(jié)果是一樣的，只是浪費(fèi)了帶寬。,最后，第一個發(fā)出該選舉（ELECTION）消息進(jìn)程,3,4,線,程,進(jìn)程因等待而掛起,使進(jìn)程中可并行部分不能執(zhí)行,從而使系統(tǒng)性能下降,故引入,-,線程,.,1.,線程：就是可以共享地址空間的輕型進(jìn)程，它有自己的程序寄記數(shù)器棧和寄存器集合。,它與進(jìn)程的主要區(qū)別是它的地址空間是共享的。,線程相對于進(jìn)程，猶如進(jìn)程相對于機(jī)器,2.,線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng),.,多線程組織的常用模型：,34 線 程 進(jìn)程因等待而掛起,使進(jìn)程中可,1),分配器工作者模型,有一個分配器線程喚醒工作者線程可用信號燈,2),團(tuán)隊模型,地位平等 線程各自獲取和處理自己的請求,.,3),流水線模型,管道線模型，第一個線程產(chǎn)生一些數(shù)據(jù)傳給下一個線程處理，且持續(xù)下去。,多線程可分時工作在單,CPU,上也可工作在多處理器系統(tǒng)上,而且多線程系統(tǒng)設(shè)計的好將可與多處理機(jī)工作性能相當(dāng),.,1)分配器工作者模型,共享緩沖區(qū),到達(dá)的工作請求,郵箱,文件服務(wù)器進(jìn)程,分配器線程,工作者線程,到達(dá)的工作請求,到達(dá)的工作請求,內(nèi)核,分配器,/,工作者模型,流水線模型,團(tuán)體模型,進(jìn)程中線程三種組織方式,共享緩沖區(qū)到達(dá)的工作請求郵箱文件服務(wù)器進(jìn)程分配器線程工作者線,3.,線程包的設(shè)計的相關(guān)問題,線程包就是供用戶或程序員調(diào)用的關(guān)于線程的一組原語。,線程的管理方法有靜態(tài)和動態(tài)方法兩種。,靜態(tài),即開始就確定好線程的個數(shù),，動態(tài),個數(shù),不定,線程的代碼與進(jìn)程一樣，由多個過程組成。,線程包中臨界區(qū)控制利用互斥體（,mutex),其總處于：,打開和鎖住兩種狀態(tài),lock mutex;,check data structures lock mutex,while(resource busy)mark resource as free;,wait(condition varable);unlock mutex;,mark resource as busy;wakeuo(condition variable);,unlock mutex;,互斥變量與條件變量的使用,3.線程包的設(shè)計的相關(guān)問題,線程可由算法進(jìn)行調(diào)度，如優(yōu)先級調(diào)度、循環(huán)調(diào)度等,4.,線程包的實(shí)現(xiàn),在用戶空間實(shí)現(xiàn)線程（如圖）,這種方法是將線程包完全放在,用戶空間,，內(nèi)核對此一無所知，在這種方法中，內(nèi)核只是管理普通的單線程進(jìn)程。這種方法最明顯的優(yōu)點(diǎn),是它可以在一個不支持多線程的操作系統(tǒng)上實(shí)現(xiàn)用戶線程包。同時它還允許每個進(jìn)程有自己特定的調(diào)度算法,.,線,程,1,線,程,2,線,程,3,線,程,4,線,程,5,線,程,6,運(yùn)行期系統(tǒng),內(nèi) 核,內(nèi)核空間,用戶空間,線程可由算法進(jìn)行調(diào)度，如優(yōu)先級調(diào)度、循環(huán)調(diào)度等線線線線,缺點(diǎn)是：,數(shù)量太多會引起資源緊張,.,同時,(1),它也難實(shí)現(xiàn)阻塞系統(tǒng)的調(diào)用,.,(2),它的調(diào)度是非搶先式的,.,進(jìn)程內(nèi)部無時鐘中斷,無法進(jìn)行時間片的調(diào)度,.,2),在操作系統(tǒng)內(nèi)核實(shí)現(xiàn)（如圖）,不需要運(yùn)行系統(tǒng),線程創(chuàng)建或撤銷,只需一次系統(tǒng)調(diào)用,比在用戶空間實(shí)現(xiàn)線程開銷大,.,可通過在撤銷時加標(biāo)記，當(dāng)做為新線程創(chuàng)建時僅需激活即可。,線,程,1,線,程,2,線,程,3,線,程,4,線,程,5,線,程,6,內(nèi) 核,用戶空間,內(nèi)核空間,缺點(diǎn)是：線線線線線線內(nèi) 核用戶空間內(nèi)核空間,3),調(diào)度員活動方法,結(jié)合前兩種的優(yōu)點(diǎn),(,用戶線程的高性能和內(nèi)核線程的實(shí)現(xiàn)簡單,),原理：當(dāng)使用調(diào)度員活動方法時，內(nèi)核給每個進(jìn)分配