分布式操作系統(tǒng)復(fù)習(xí)大綱.ppt

1、分布式操作系統(tǒng)復(fù)習(xí)大綱,（一）分布式操作系統(tǒng),（0）分布式操作系統(tǒng)的定義 （1）分布式系統(tǒng)的體系結(jié)構(gòu)類型 （2）構(gòu)造分布式操作系統(tǒng)的途徑 （3）分布式操作系統(tǒng)的層次結(jié)構(gòu) （4）多機(jī)，網(wǎng)絡(luò)和分布式操作系統(tǒng)間差別 （5）透明性(Transparency)意義 （6）分布式計(jì)算機(jī)系統(tǒng)的資源管理 （7）分布式操作系統(tǒng)的同步算法,（0）分布式操作系統(tǒng)的定義,文獻(xiàn)中已經(jīng)給出分布式系統(tǒng)的各種定義，沒有一個(gè)是滿意的并且沒有一個(gè)為其他所同意。為此，給出一個(gè)松散的特征就夠了。 Tanenbaum給出如下定義： A distributed system is a collection of independent

2、computers that appears to its user as a single coherent system. 分布式操作系統(tǒng)是分布式系統(tǒng)的操作系統(tǒng)。,（1）分布式系統(tǒng)的體系結(jié)構(gòu)類型,Tanenbaum和Renesse將分布式系統(tǒng)分成五類： 小型機(jī)類型(minicomputer model) 工作站類型(workstation model) 處理機(jī)池類型(processor pool model) 工作站-服務(wù)器類型(workstation-server model) 混合類型(hybrid model),（2）構(gòu)造分布式操作系統(tǒng)的途徑,從頭開始； 修改、擴(kuò)充式； 層次式。,（

3、3）分布式操作系統(tǒng)的層次結(jié)構(gòu),一個(gè)分布式操作系統(tǒng)大致可分成四層，由內(nèi)向外依次是： 執(zhí)行層； 進(jìn)程通信層； 服務(wù)支持層； 用戶接口層。,（4）多機(jī)、網(wǎng)絡(luò)和分布式操作系統(tǒng)間差別,（5）透明性(Transparency)意義,（6）分布式計(jì)算機(jī)系統(tǒng)的資源管理,從單個(gè)資源與多個(gè)管理者的相互關(guān)系 從多個(gè)資源與多個(gè)管理者的相互關(guān)系 從實(shí)用的角度 分布式計(jì)算機(jī)系統(tǒng)的資源管理的算法,從單個(gè)資源與多個(gè)管理者的相互關(guān)系,全集中管理方式 即專制(autocratic)管理 功能分布管理方式即分擔(dān)管理或分割(partitioned)管理 浮動(dòng)管理方式即 輪流(successive)管理 全分散管理方式即 民主(dem

4、ocratic)管理,從多個(gè)資源與多個(gè)管理者的相互關(guān)系,集中:所有資源屬一個(gè)管理者管理。 分管：每一資源只屬一個(gè)管理者管理。 部分管理：每一資源屬于若干管理者管理。 合管：每一資源屬于全部管理者共同管理。,從實(shí)用的角度,分布式計(jì)算機(jī)系統(tǒng)的資源管理的算法,招標(biāo)（投標(biāo)）算法 回聲算法 由近及遠(yuǎn)算法,（7）分布式操作系統(tǒng)的同步算法,偏序Happened-Before關(guān)系(筒稱HB)的定義 時(shí)鐘（clock）條件的定義 系統(tǒng)的邏輯時(shí)鐘的定義 事件e的時(shí)間戳的定義 全序先于（）關(guān)系的定義 向量時(shí)鐘的定義和向量時(shí)鐘的實(shí)現(xiàn)規(guī)則以及例子,（7）分布式操作系統(tǒng)的同步算法,集中式互斥算法 分布式算法（Lampor

5、t算法） 分布式算法（Ricart-Agrawala算法） 令牌算法 欺負(fù)（霸主Bully）算法 局部狀態(tài)的定義 全局狀態(tài)的定義 一致的全局狀態(tài)、不一致的全局狀態(tài)、無過渡的全局狀態(tài)和強(qiáng)一致的全局狀態(tài)的定義及例子,偏序Happened-Before關(guān)系(筒稱HB)的定義：,a b 若a和b是同一進(jìn)程中的兩個(gè)事件，且a在b前發(fā)生；或者， 若a是一進(jìn)程中發(fā)送消息的事件，b是另一進(jìn)程中接收同一消息的事件。 該關(guān)系是傳遞的，即若a b且b c，則有a c。 該關(guān)系是非自反的，即a(aa)，因一事件不可能它自身之前發(fā)生。,時(shí)鐘（clock）條件的定義：,對系統(tǒng)中的任何事件a和b，若a b，則LC(a)必須

6、小于LC(b)。,系統(tǒng)的邏輯時(shí)鐘的定義：,系統(tǒng)的邏輯時(shí)鐘（Logic Clock簡記為LC）是滿足時(shí)鐘條件的系統(tǒng)事件集合到非負(fù)整數(shù)的映射。 當(dāng)事件e 進(jìn)程Pi時(shí)， LC(e)= LCi(e)。,事件e的時(shí)間戳的定義：,稱事件e的邏輯時(shí)鐘值LC(e)為事件e的時(shí)間戳（Time Stamp簡記為TS）。,全序先于（）關(guān)系的定義：,我們稱進(jìn)程pi中的事件a先于進(jìn)程pj中的事件b(以a b表示) 當(dāng)且僅當(dāng) LCi (a) LCj (b)；或 LCi (a) = LCj (b)，且pipj，其中關(guān)系“”是進(jìn)程的一個(gè)任意偏序。 實(shí)現(xiàn)關(guān)系“”的一個(gè)簡單方法是給系統(tǒng)中每個(gè)進(jìn)程賦以一個(gè)唯一的進(jìn)程號(hào)，且規(guī)定：若i

7、 j，則pi pj。 a b定義了一個(gè)全序關(guān)系。,向量時(shí)鐘的定義和向量時(shí)鐘的實(shí)現(xiàn)規(guī)則以及例子：,設(shè)n為分布式系統(tǒng)中進(jìn)程個(gè)數(shù)，每個(gè)進(jìn)程Pi裝配一個(gè)向量時(shí)鐘VCi1, n，它是一個(gè)長度為n的向量?？梢园阉胂鬄橐粋€(gè)函數(shù)，賦給任何事件a一個(gè)向量VCi(a)。 VCi的第i個(gè)分量VCii對應(yīng)于Pi自己的邏輯時(shí)間，即Pi的內(nèi)部事件計(jì)數(shù)。 VCij，ji是Pi對Pj邏輯時(shí)間最佳猜測。更具體講，在任何時(shí)間點(diǎn)，VCi的第j個(gè)分量VCij指示在Pi當(dāng)前時(shí)間點(diǎn)“發(fā)生之前HB”在Pj最近事件出現(xiàn)的邏輯時(shí)間，即進(jìn)程Pj中在因果關(guān)系上處于當(dāng)前Pi之前的事件計(jì)數(shù)。,向量時(shí)鐘的實(shí)現(xiàn)規(guī)則,IR1向量時(shí)鐘VCi，在進(jìn)程Pi的任

8、何兩個(gè)相繼事件之間被增加。 VCi i := VCi i + d (d0) IR2如果進(jìn)程Pi的事件a是發(fā)送消息m事件，則消息m被賦予一個(gè)向量時(shí)間戳tm= VCi (a)； 進(jìn)程Pj接收同樣消息m時(shí)VCj作如下修改： kVCj k := max(VCj k, tmk),向量時(shí)鐘例子,集中式互斥算法,分布式算法（Lamport算法）,分布式算法（Ricart-Agrawala算法）,令牌算法,選舉算法,欺負(fù)（霸主Bully）算法,局部狀態(tài)的定義：,transit(LSi, LSj) = mij | send(mij) LSi rec(mij) LSj inconsistent (LSi, LSj

9、) = mij | send(mij) LSi rec(mij) LSj,全局狀態(tài)的定義：,一個(gè)系統(tǒng)的全局狀態(tài)GS是一個(gè)它的所有場點(diǎn)的局部狀態(tài)集合；即 GS = LS1, LS2, ., LSn 其中n是系統(tǒng)中場點(diǎn)的個(gè)數(shù)。,一致的全局狀態(tài)、不一致的全局狀態(tài)、無過渡的全局狀態(tài)和強(qiáng)一致的全局狀態(tài)的定義及例子：,一個(gè)全局狀態(tài) GS = LS1, LS2, ., LSn 是一致的(consistent)當(dāng)且僅當(dāng) 1 i n1j n (inconsistent(LSi, LSj) =) 一個(gè)全局狀態(tài)是無過渡的(transitless)，當(dāng)且僅當(dāng) 1 i n1j n (transit(LSi, LSj)

10、= ) 因此， 在一個(gè)無過渡的全局狀態(tài)中，所有通信通道均為空。 如果一個(gè)全局狀態(tài)是一致的和無過渡的，則稱為強(qiáng)一致的(strongly consistent)。,例子,（二）分布式共享內(nèi)存,（1）體系結(jié)構(gòu)和動(dòng)力 （2）實(shí)現(xiàn)分布式共享內(nèi)存的算法 （3）存儲(chǔ)一致性 （4）一致性協(xié)議,（1）體系結(jié)構(gòu)和動(dòng)力,（2）實(shí)現(xiàn)分布式共享內(nèi)存的算法,中央服務(wù)器(Central-Server)算法 遷移算法 讀復(fù)制(Read-Replicatin)算法 完全復(fù)制算法,（3）存儲(chǔ)一致性,嚴(yán)格一致性（Strict Consistency） 順序的一致性 (Sequential consistency) 因果一致性 一般

11、一致性(General Consistency) 處理機(jī)一致性 (Processor consistency) 管道（PRAM）一致性 弱一致性(Weak consistency) 釋放一致性(Release consistency) 入口一致性(Release consistency),（4）一致性協(xié)議。,寫-使無效協(xié)議和 寫更新協(xié)議,（三）分布式系統(tǒng)中的死鎖,（1）死鎖和饑餓的定義 （2）分布式死鎖的策略 （3）利用時(shí)間戳預(yù)防死鎖方法 （4）死鎖檢測方法,（1）死鎖和饑餓的定義,（2）分布式死鎖的策略,四個(gè)策略被用來處理死鎖： 鴕鳥(ostirch)算法：忽略死鎖問題。 檢測和恢復(fù)(det

12、ection and recovery)：允許死鎖出現(xiàn)，檢測并試圖恢復(fù)之。 預(yù)防(prevention)：靜態(tài)地使死鎖結(jié)構(gòu)上成為不可能。 避免(avoidance)：由仔細(xì)地分配資源算法避免死鎖。,（3）利用時(shí)間戳預(yù)防死鎖方法,等-死（wait-die）方法 因傷（wound-wait）等待,（4）死鎖檢測方法,集中式死鎖檢測方式 層次式死鎖檢測方法 其它分布式方法Chandy-Misra-Haas算法 分布式事務(wù)處理死鎖檢測方法,(四)并發(fā)程序設(shè)計(jì)的數(shù)學(xué)模型,（1）Petri網(wǎng)模型 （2）時(shí)態(tài)邏輯模型,（1） Petri網(wǎng)模型,Petri網(wǎng)結(jié)構(gòu)和Petri網(wǎng)圖的定義 標(biāo)志的定義 作標(biāo)志的Petri網(wǎng)結(jié)構(gòu)和作標(biāo)志的Petri網(wǎng)圖的定義 能行的轉(zhuǎn)移的定義 點(diǎn)燃的規(guī)則 用作標(biāo)志的Petri網(wǎng)結(jié)構(gòu)和作標(biāo)志的Petri網(wǎng)圖模擬并發(fā)程序設(shè)計(jì)的例子，例如，臨界區(qū)，有界緩沖取，讀者和作者，五個(gè)哲學(xué)家問題等，點(diǎn)燃45次,（2）時(shí)態(tài)邏輯模型,模態(tài)邏輯的定義 時(shí)態(tài)邏輯的定義，線性離散時(shí)態(tài)