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

《分布式系統(tǒng)與WEB服務(wù)課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《分布式系統(tǒng)與WEB服務(wù)課件（88頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),南京理工大學(xué)計(jì)算機(jī)學(xué)院,分布式系統(tǒng)與,WEB,服務(wù),第三章 分布式系統(tǒng)的同步 和進(jìn)程,第三章 分布式系統(tǒng)的同步 和進(jìn)程,3,1,時(shí)鐘同步,分布式算法的主要特征：,相關(guān)信息分布在多臺(tái)機(jī)器上,進(jìn)程僅依據(jù)局部的信息作出決定,一臺(tái)機(jī)器的故障不應(yīng)引起整個(gè)系統(tǒng)的失敗,沒有共用的全局時(shí)鐘。,31 時(shí)鐘同步 分布式算法的主要特征：,1,邏輯時(shí)鐘,先看一個(gè)例子,:,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,7

2、0,80,90,100,A,B,C,D,三個(gè)有自己時(shí)鐘的進(jìn)程,時(shí)鐘不同,運(yùn)行的結(jié)果是消息,C,在時(shí)間,60,上被發(fā)送,卻在時(shí)間點(diǎn),54,上到達(dá),1邏輯時(shí)鐘000ABCD三個(gè)有自己時(shí)鐘的進(jìn)程,時(shí)鐘不同,Lamport,的算法以,”,先于,”,關(guān)系,為基礎(chǔ)，每個(gè)消息都攜帶它的發(fā)送時(shí)間,當(dāng)它到達(dá)目的地時(shí)，如果目的地的時(shí)間早于它的發(fā)送時(shí)間，那么就把目的地的時(shí)間向前拔,至少要比發(fā)送時(shí)間大,1,個(gè)單位,.,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

3、,C,D,用,Lamport,的算法糾正時(shí)鐘,Lamport的算法以”先于”關(guān)系為基礎(chǔ)，每個(gè)消,該算法解決了全局時(shí)鐘問題，它的條件就是兩個(gè)相關(guān)事件之間必須至少相差一個(gè)時(shí)間,2,時(shí)鐘同步算法,邏輯時(shí)鐘只給出事物的相對(duì)時(shí)間,與真實(shí)時(shí)間并不對(duì)應(yīng),故要引入外部物理時(shí)鐘,常用的時(shí)鐘同步算法,:,克里司帝安,(CRISTIAN),算法,具有國家標(biāo)致時(shí)間接收器的機(jī)器,注意,:,調(diào)整的方法,通過調(diào)節(jié)單位時(shí)間內(nèi)的中斷的時(shí)間,來逐步完成時(shí)鐘的調(diào)整,.,該算法解決了全局時(shí)鐘問題，它的條件就,伯克利算法,計(jì)算平均時(shí)間,它是一個(gè)集中式算法,不能在大規(guī)模的分布式系統(tǒng)中使用,原理,:,定期輪詢每臺(tái)機(jī)器的時(shí)間,由結(jié)果計(jì)算平均

4、時(shí)間,各機(jī)器依此調(diào)整時(shí)間,.,3,同步時(shí)鐘的具體使用,至多一次消息傳送,消息的時(shí)間戳比存儲(chǔ)的時(shí)間戳的值早,就拒絕接受該消息,伯克利算法,基于時(shí)鐘的緩沖存儲(chǔ)器（,CACHE,）的一致性,使用,CACHE,會(huì)出現(xiàn)一致性問題，原解決的方法,:,區(qū)分讀寫緩存,現(xiàn)在可用同步時(shí)鐘來解決。即通過提供有效期（,利用有效的租約）,來控制,CACHE,一致性問題。,基于時(shí)鐘的緩沖存儲(chǔ)器（CACHE）的一致性,3.2,互斥操作,有多個(gè)進(jìn)程的系統(tǒng)經(jīng)常會(huì)碰到臨界區(qū)的操作。當(dāng)一個(gè)進(jìn)程要訪問某個(gè)共享數(shù)據(jù)時(shí)，它要先進(jìn)人臨界區(qū)進(jìn)行互斥操作，確保沒有別的進(jìn)程同時(shí)訪問該數(shù)據(jù)。在單機(jī)系統(tǒng)中，臨界區(qū)可以用信號(hào)燈、管程來實(shí)現(xiàn)。那么在分布

5、式系統(tǒng)中，由于,不能共享主存,，怎么實(shí)現(xiàn)臨界區(qū)和互斥操作呢,?,下面我們討論幾種算法。,集中式算法,該方法就是模擬單機(jī)系統(tǒng),指定一個(gè)管理員進(jìn)行許可管理,該算法保證了互斥,每個(gè)臨界區(qū)只需三條消息,(,申請(qǐng),許可,釋放,),3.2 互斥操作 有多個(gè)進(jìn)程的系統(tǒng)經(jīng)常,1,0,2,OK,請(qǐng)求,C,管理員,隊(duì)列空,管理員,1,0,2,不回答,請(qǐng)求,C,隊(duì)列空,1,0,2,OK,釋放,C,管理員,隊(duì)列空,2,(A),進(jìn)程,1,向管理員請(qǐng)求進(jìn)入臨界區(qū),得到許可,(B),進(jìn)程,2,向管理員請(qǐng)求進(jìn)入臨界區(qū),管理員不回答,(C),進(jìn)程,2,向管理員請(qǐng)求進(jìn)入臨界區(qū),管理員許可,缺點(diǎn),:,集中式算法管理員是系統(tǒng)的瓶頸,

6、102OK請(qǐng)求C管理員隊(duì)列空管理員102不回答請(qǐng)求C隊(duì)列空1,分布式算法,算法的條件,:,系統(tǒng)中的事件必須有全局的順序,算法的工作過程如下,:,當(dāng)一個(gè)進(jìn)程要進(jìn)入臨界區(qū)時(shí)，它構(gòu)造一條包括臨界區(qū)名、進(jìn)程號(hào)和當(dāng)前時(shí)間的請(qǐng)求消息，然后把該消息廣播給其他的所有進(jìn)程。這里假設(shè)，消息的發(fā)送是可靠的。,當(dāng)一個(gè)進(jìn)程收到請(qǐng)求后，根據(jù)它的狀態(tài)采取相應(yīng)的動(dòng)作：,(1),當(dāng)接收者不在臨界區(qū)，并且也不想進(jìn)入臨界區(qū)，就應(yīng)答發(fā)送者,OK,消息。,(2),如果接收者已經(jīng)在臨界區(qū)中，它不回答僅僅把請(qǐng)求加入隊(duì)列。,(3),如果接收者不在臨界區(qū)，但它也想進(jìn)入臨界區(qū)，就要將收到消息的時(shí)間戳和它廣播消息的時(shí)間戳比較,.,如果到來的消息時(shí)

7、間戳早，接收者回答發(fā)送者,OK,消息；反之接收者把到來的請(qǐng)求加入隊(duì)列，不回答,.,分布式算法,在發(fā)完進(jìn)入臨界區(qū)請(qǐng)求后，進(jìn)程將等待所有的允許消息，一旦得到許可，就可進(jìn)入臨界區(qū)，當(dāng)退出時(shí)向隊(duì)列中的所有進(jìn)程發(fā),OK,消息，并將它從隊(duì)列中刪除。,所有進(jìn)程都要參與決定是否進(jìn)入臨界區(qū)，若有進(jìn)程不能做，算法將出錯(cuò)。,由于所有進(jìn)程都要參加算法，所以比集中式算法慢，復(fù)雜，開銷大。,改進(jìn)算法：,不需所有進(jìn)程同意，部分回答,OK,即可,令牌環(huán)算法,進(jìn)程只有擁有令牌時(shí),才能進(jìn)入臨界區(qū),一個(gè)進(jìn)程從相鄰的進(jìn)程收到令牌時(shí)先檢查自己是非要進(jìn)入臨界區(qū),;,如果要,就進(jìn)入,否則就將令牌傳遞給下一個(gè)進(jìn)程,.,缺點(diǎn),:,令牌可能丟失

8、且檢測(cè)困難，一個(gè)要進(jìn)入臨界區(qū)的進(jìn)程最差情況下要等待其他進(jìn)程進(jìn)入和退出臨界區(qū)所用時(shí)間總和,在發(fā)完進(jìn)入臨界區(qū)請(qǐng)求后，進(jìn)程將等待所有的允許消息，,三種算法的特點(diǎn)比較,集中式算法簡(jiǎn)單、高效，每次進(jìn)入和離開臨界區(qū)只需,3,次消息傳遞：,請(qǐng)求、許可；釋放,，分布式算法中，,n,個(gè)進(jìn)程需要,(n-1),個(gè)請(qǐng)求和,(n-1),個(gè)許可，總共要,2(n,1),個(gè)消息。在令牌環(huán)算法中，所需的消息數(shù)是不固定的。如果每個(gè)進(jìn)程都要進(jìn)入臨界區(qū)，那么每個(gè)令牌都有一次進(jìn)人和退出，平均每次進(jìn)入有,個(gè)消息傳遞；如果令牌被一個(gè)進(jìn)程占有很長(zhǎng)時(shí)間，那么進(jìn)入臨界區(qū)需要的消息就不確定。,進(jìn)程從它發(fā)出進(jìn)入臨界區(qū)的請(qǐng)求到它進(jìn)入臨界區(qū)的時(shí)間延遲在

9、三個(gè)算法中是不同的,當(dāng)臨界區(qū)很短并且使用頻率很低時(shí)，進(jìn)入臨界區(qū)時(shí)間延遲的決定因素是進(jìn)人臨界區(qū)的控制機(jī)制當(dāng)臨界區(qū)很長(zhǎng)并且使用的頻率很高時(shí)，決定因素在于等待時(shí)間，消息數(shù)就能說明這一點(diǎn)。,這三種算法出現(xiàn)故障時(shí),都會(huì)有很大影響,要避免系統(tǒng)的崩潰,須注意,:,在容錯(cuò)系統(tǒng)中,次三種算法都不適用,.,三種算法的特點(diǎn)比較,3.3,選舉算法,在分布式系統(tǒng)中，大多數(shù)算法要求有一個(gè)進(jìn)程充當(dāng)管理員或初始啟動(dòng)者等特殊角色。前面幾個(gè)算法就有這樣的例子。一般來說，由哪個(gè)進(jìn)程充當(dāng)特定角色無關(guān)緊要，但是必須有一個(gè)進(jìn)程做這個(gè)工作。下面我們來看如何選一個(gè)進(jìn)程擔(dān)當(dāng)特定角色。,選舉算法的目的是當(dāng)選舉完成后，能夠讓所有的進(jìn)程知道誰是管理

10、員,.,3.3選舉算法 在分布式系統(tǒng)中，大多,1.,霸道算法,該算法提出。當(dāng)一個(gè)進(jìn)程,P,注意到管理員不再對(duì)請(qǐng)求作出反應(yīng)時(shí)，它就開始選舉進(jìn)程,P,執(zhí)行下列步驟：,(1),向所有,進(jìn)程號(hào)比它大,的進(jìn)程發(fā)送,ELECTION,消息；,(2),如果沒有進(jìn)程響應(yīng)，進(jìn)程,P,成為管理員；,(3),如果有進(jìn)程響應(yīng)，該響應(yīng)進(jìn)程成為管理員，,P,結(jié)束選舉。,注意：,一個(gè)進(jìn)程只能從號(hào)碼比它小的進(jìn)程處得到一個(gè)選擇消息,1.霸道算法,2,0,5,3,6,4,1,7,(A),進(jìn)程,4,啟動(dòng)選舉,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,

11、6,都啟動(dòng)選舉,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啟動(dòng)選舉20536417(B)進(jìn),2.,環(huán)形算法,這個(gè)算法使用環(huán)，但不是令牌環(huán)。,這里假定所有的進(jìn)程都是有序號(hào)的，即每個(gè)進(jìn)程都知道它的后繼進(jìn)程。當(dāng)一個(gè)進(jìn)程發(fā)現(xiàn)管理員不能工作時(shí)，它把包含其進(jìn)程號(hào)的,ELECTION,消息發(fā)給它的后繼進(jìn)程；接收消息的進(jìn)程再向后繼進(jìn)程發(fā)送,ELECTION,消息。如果接收進(jìn)程沒有反應(yīng)，發(fā)送消息的進(jìn)程便向下一個(gè)進(jìn)程發(fā)消息。每一次發(fā)送,ELECTION,，進(jìn)程都要將自己的進(jìn)

12、程號(hào)加入消息。,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)形選舉算法,最后，第一個(gè)發(fā)出該選舉（,ELECTION,）消息進(jìn)程收到該消息,再將其轉(zhuǎn)換為協(xié)調(diào)（,COORDINATOR,）消息后，再循環(huán)一周,通知誰是管理員，誰是組成員，,這時(shí)消息包中進(jìn)程號(hào)最高的進(jìn)程將成為管理員。,當(dāng)這個(gè)消息循環(huán)一周后，由發(fā)送進(jìn)程把它從網(wǎng)上清除。,圖中,2,和,5,都發(fā)現(xiàn),7,失效，分別建立選舉消息，兩條消息都沿環(huán)運(yùn)行，結(jié)果是一樣的，只是浪費(fèi)了帶寬。,最后，第一個(gè)發(fā)出該選舉（ELECTION）消息進(jìn)程,

13、3,4,線,程,進(jìn)程因等待而掛起,使進(jìn)程中可并行部分不能執(zhí)行,從而使系統(tǒng)性能下降,故引入,-,線程,.,1.,線程：就是可以共享地址空間的輕型進(jìn)程，它有自己的程序寄記數(shù)器棧和寄存器集合。,它與進(jìn)程的主要區(qū)別是它的地址空間是共享的。,線程相對(duì)于進(jìn)程，猶如進(jìn)程相對(duì)于機(jī)器,2.,線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng),.,多線程組織的常用模型：,34 線 程 進(jìn)程因等待而掛起,使進(jìn)程中可,1),分配器工作者模型,有一個(gè)分配器線程喚醒工作者線程可用信號(hào)燈,2),團(tuán)隊(duì)模型,地位平等 線程各自獲取和處理自己的請(qǐng)求,.,3),流水線模型,管道線模型，第一個(gè)線程產(chǎn)生一些數(shù)據(jù)傳給下一個(gè)線程處理，且持續(xù)下去。,

14、多線程可分時(shí)工作在單,CPU,上也可工作在多處理器系統(tǒng)上,而且多線程系統(tǒng)設(shè)計(jì)的好將可與多處理機(jī)工作性能相當(dāng),.,1)分配器工作者模型,共享緩沖區(qū),到達(dá)的工作請(qǐng)求,郵箱,文件服務(wù)器進(jìn)程,分配器線程,工作者線程,到達(dá)的工作請(qǐng)求,到達(dá)的工作請(qǐng)求,內(nèi)核,分配器,/,工作者模型,流水線模型,團(tuán)體模型,進(jìn)程中線程三種組織方式,共享緩沖區(qū)到達(dá)的工作請(qǐng)求郵箱文件服務(wù)器進(jìn)程分配器線程工作者線,3.,線程包的設(shè)計(jì)的相關(guān)問題,線程包就是供用戶或程序員調(diào)用的關(guān)于線程的一組原語。,線程的管理方法有靜態(tài)和動(dòng)態(tài)方法兩種。,靜態(tài),即開始就確定好線程的個(gè)數(shù),，動(dòng)態(tài),個(gè)數(shù),不定,線程的代碼與進(jìn)程一樣，由多個(gè)過程組成。,線程包中臨

15、界區(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è)計(jì)的相關(guān)問題,線程可由算法進(jìn)行調(diào)度，如優(yōu)先級(jí)調(diào)度、循環(huán)調(diào)度等,4.,線程包的實(shí)現(xiàn),在用戶空間實(shí)現(xiàn)線程（如圖）,這

16、種方法是將線程包完全放在,用戶空間,，內(nèi)核對(duì)此一無所知，在這種方法中，內(nèi)核只是管理普通的單線程進(jìn)程。這種方法最明顯的優(yōu)點(diǎn),是它可以在一個(gè)不支持多線程的操作系統(tǒng)上實(shí)現(xiàn)用戶線程包。同時(shí)它還允許每個(gè)進(jìn)程有自己特定的調(diào)度算法,.,線,程,1,線,程,2,線,程,3,線,程,4,線,程,5,線,程,6,運(yùn)行期系統(tǒng),內(nèi) 核,內(nèi)核空間,用戶空間,線程可由算法進(jìn)行調(diào)度，如優(yōu)先級(jí)調(diào)度、循環(huán)調(diào)度等線線線線,缺點(diǎn)是：,數(shù)量太多會(huì)引起資源緊張,.,同時(shí),(1),它也難實(shí)現(xiàn)阻塞系統(tǒng)的調(diào)用,.,(2),它的調(diào)度是非搶先式的,.,進(jìn)程內(nèi)部無時(shí)鐘中斷,無法進(jìn)行時(shí)間片的調(diào)度,.,2),在操作系統(tǒng)內(nèi)核實(shí)現(xiàn)（如圖）,不需要運(yùn)行系統(tǒng),線程創(chuàng)建或撤銷,只需一次系統(tǒng)調(diào)用,比在用戶空間實(shí)現(xiàn)線程開銷大,.,可通過在撤銷時(shí)加標(biāo)記，當(dāng)做為新線程創(chuàng)建時(shí)僅需激活即可。,線,程,1,線,程,2,線,程,3,線,程,4,線,程,5,線,程,6,內(nèi) 核,用戶空間,內(nèi)核空間,缺點(diǎn)是：線線線線線線內(nèi) 核用戶空間內(nèi)核空間,3),調(diào)度員活動(dòng)方法,結(jié)合前兩種的優(yōu)點(diǎn),(,用戶線程的高性能和內(nèi)核線程的實(shí)現(xiàn)簡(jiǎn)單,),原理：當(dāng)使用調(diào)度員活動(dòng)方法時(shí)，內(nèi)核給每個(gè)進(jìn)分配