第5章同步和互斥

1、第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 v資源管理方式資源管理方式 1) 全集中管理方式：所有資源都由一個(gè)服務(wù)員管理；2) 集中分布管理方式：一個(gè)資源由一個(gè)服務(wù)員管理；3) 全分布管理方式：一個(gè)資源是由多個(gè)服務(wù)員共同管理。 (a) 全集中式 (b) 全分布式 (c) 集中分布式 第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 v控制空間控制空間 說明資源管理分散程度的參數(shù)：1) 參加一個(gè)資源的多重管理的服務(wù)員數(shù)；2) 被多個(gè)服務(wù)員管理的資源數(shù)。 (a) 集中的控制(b) 低度的分散控制

2、(c) 中度的分散控制 (d) 高度的分散控制 (e) 全分散控制 按參加多重管理的按參加多重管理的服務(wù)員數(shù)排序服務(wù)員數(shù)排序 ：第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 (a) 沒有資源被多重管理 (b) 一個(gè)資源被多重管理 (c) 兩個(gè)資源被多重管理 (d) 三個(gè)資源被多重管理 (e) 四個(gè)資源被多重管理 按由多個(gè)服務(wù)員管理的資源數(shù)目排序按由多個(gè)服務(wù)員管理的資源數(shù)目排序 第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 控制空間 ： 參加多重管理的服務(wù)員數(shù)目 控制空間 最大集中 最大分散

3、被多重管理的資源數(shù)目第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 多個(gè)服務(wù)員參加對同一資源進(jìn)行控制的方式： 1) 順序方式：按某種順序，先由一個(gè)服務(wù)員控制一段時(shí)間，之后再由另一個(gè)服務(wù)員控制一段時(shí)間。 2) 分工方式：由不同的服務(wù)員并發(fā)或順序地控制同一資源執(zhí)行不同的活動(dòng)。3) 民主方式：所有服務(wù)員共同協(xié)商一致對同一資源執(zhí)行每個(gè)管理活動(dòng)。 說明各種多重管理形式的分散性的參數(shù)：1) 一致性是指由所有服務(wù)員共同完成的對同一個(gè)資源管理的活動(dòng)數(shù)目。 2) 所謂均等性是各服務(wù)員對同一資源進(jìn)行某一控制活動(dòng)時(shí)被分配的管理權(quán)限和責(zé)任的平等程度。3) 參加每個(gè)活動(dòng)

4、的服務(wù)員數(shù)目。第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 1 2 3 全部 各個(gè)活動(dòng) (a) 一致性的最大集中 1 2 3 全部各個(gè)活動(dòng) (b) 一致性的最大分散 1 N 1 N 一致性：第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 均等性： 責(zé) 任 和 權(quán) 限 0 Y 1 N (a)各服務(wù)員的不同管理權(quán)限和責(zé)任 各服務(wù)員 責(zé) 任 和 權(quán) 限 1 Y N 各服務(wù)員 (b)均等性中的最大集中 0 1 0 責(zé) 任 和 權(quán) 限 N Y (c)均等性中的最大分散 各服務(wù)員 第五章第五章 同步和互斥

5、同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 參加每個(gè)活動(dòng)的服務(wù)員數(shù)目：服務(wù)員數(shù)目123全部各個(gè)活動(dòng)(a) 最集中情況123全部各個(gè)活動(dòng)(b) 最分散情況1N1N服務(wù)員數(shù)目123全部各個(gè)活動(dòng)(a) 最集中情況123全部各個(gè)活動(dòng)(b) 最分散情況1N1N第五章第五章 同步和互斥同步和互斥 5.1 5.1 分布式系統(tǒng)中的資源管理分布式系統(tǒng)中的資源管理 單個(gè)資源的控制空間單個(gè)資源的控制空間 ： 服務(wù)員數(shù) 一致性 均等性 最集中 最分散 可以將單個(gè)資源控制空間和集體資源控制空間合并成一個(gè)五維空間。方法是加上資源個(gè)數(shù)、控制程度。計(jì)算機(jī)與網(wǎng)絡(luò)系統(tǒng)的4種體系結(jié)構(gòu)nHost / T

6、erminalnWorkstation / File ServernClient / ServernPeer-to-Peer資源分配原則n1、全集中管理方式中：資源申請者總是向惟一的服務(wù)員提出，服務(wù)員按一定順序處理每個(gè)申請，如果資源已經(jīng)被分配則申請者等待。只要不發(fā)生死鎖和占用資源者無限期占用資源的情況，任何申請者必定能在有限時(shí)間內(nèi)獲得資源。比如Host系統(tǒng)n2、集中分布管理方式中：申請者先向一個(gè)服務(wù)員提出申請，如果暫時(shí)不能獲得資源就轉(zhuǎn)向另一個(gè)服務(wù)員申請。這時(shí)可能發(fā)生“餓死”現(xiàn)象。當(dāng)然，也有可能發(fā)生死鎖n3、全分布管理方式中：申請者向任一服務(wù)員提出申請，服務(wù)員共同協(xié)商分配資源。還會(huì)發(fā)生“餓死”和

7、死鎖現(xiàn)象嗎？第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v分布式系統(tǒng)中同步機(jī)構(gòu)的作用分布式系統(tǒng)中同步機(jī)構(gòu)的作用 同步點(diǎn)：為了達(dá)到合作，各個(gè)進(jìn)程在執(zhí)行的過程中必須存在若干點(diǎn)，超過這些點(diǎn)時(shí)，一個(gè)進(jìn)程在另一個(gè)進(jìn)程執(zhí)行完某一活動(dòng)前不能繼續(xù)執(zhí)行，這些點(diǎn)稱為這兩個(gè)進(jìn)程之間的同步點(diǎn)。 分布計(jì)算系統(tǒng)中共享資源的兩類：一類是各進(jìn)程可以同時(shí)訪問的，如中央處理機(jī)(允許多個(gè)進(jìn)程交疊使用一個(gè)處理機(jī))、只讀文件和不允許修改的存放子程序和數(shù)據(jù)的主存區(qū)域等；另一類是不允許多個(gè)進(jìn)程同時(shí)訪問的，每次只允許一個(gè)進(jìn)程使用，如大多數(shù)外部設(shè)備(如打印機(jī))、可寫的文件以及主存中可修改的區(qū)域等。同步機(jī)構(gòu)在互斥控制中

8、的作用是對活動(dòng)的執(zhí)行進(jìn)行排序。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v分布式系統(tǒng)中同步機(jī)構(gòu)的作用分布式系統(tǒng)中同步機(jī)構(gòu)的作用 一致狀態(tài)：一個(gè)計(jì)算系統(tǒng)應(yīng)該在所有時(shí)間內(nèi)滿足一定的外部規(guī)定或約束，如果一個(gè)計(jì)算系統(tǒng)確實(shí)在所有時(shí)間內(nèi)滿足了一定的外部規(guī)定或約束，這時(shí)我們稱系統(tǒng)狀態(tài)是一致的。同步機(jī)構(gòu)的目的就是給進(jìn)程提供某種手段，使系統(tǒng)保持一致狀態(tài)。 分布計(jì)算系統(tǒng)的計(jì)算方式分成三種 ：1) 完全復(fù)制的計(jì)算。任何操作所激發(fā)的每個(gè)活動(dòng)必須由所有的消費(fèi)者共同處理，要求所有的活動(dòng)均應(yīng)完成。這時(shí)同步機(jī)構(gòu)的目的是保證消費(fèi)者處理活動(dòng)的次序必須相同。 第五章第五章 同步和互斥同步和互斥 5.2

9、 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) 分布計(jì)算系統(tǒng)的計(jì)算方式分成三種 ：2) 完全分割的計(jì)算。一個(gè)操作所激發(fā)的不同活動(dòng)由不同的消費(fèi)者分別獨(dú)自處理。在這種情況下，同步機(jī)構(gòu)的目的是保證所有相互干擾的活動(dòng)成為有序的，使得該操作保持原子性(要么完成操作，要么干脆不發(fā)生)。3) 分割和部分復(fù)制的計(jì)算。一個(gè)操作所激發(fā)的活動(dòng)中，某些是由不同的消費(fèi)者獨(dú)自處理的，某些操作是由一些消費(fèi)者共同處理。它兼有前面兩種計(jì)算形式的特點(diǎn)。對于不同的計(jì)算方式，同步機(jī)構(gòu)的目的和要求也是不同的。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) 評價(jià)同步機(jī)構(gòu)的標(biāo)準(zhǔn)：1) 響應(yīng)時(shí)間和吞吐量。各種機(jī)構(gòu)應(yīng)盡量利用系統(tǒng)的并行性質(zhì)

10、，以提高吞吐量和縮短響應(yīng)時(shí)間。2) 恢復(fù)能力。同步機(jī)構(gòu)應(yīng)能使系統(tǒng)從故障中恢復(fù)過來。 3) 開銷。指使用同步機(jī)構(gòu)的代價(jià)，包括額外增加的報(bào)文長度、數(shù)量和對它們的處理時(shí)間，以及用于存放同步信息所需的額外存儲(chǔ)空間。 4) 公平性。操作發(fā)生沖突時(shí)，同步機(jī)構(gòu)應(yīng)能避免生產(chǎn)者餓死，各生產(chǎn)者具有平等的權(quán)利。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) 評價(jià)同步機(jī)構(gòu)的標(biāo)準(zhǔn)：5) 可擴(kuò)充性。系統(tǒng)擴(kuò)充新的處理機(jī)時(shí)同步機(jī)構(gòu)應(yīng)不影響其正常運(yùn)行。6) 連接方式。使用某些同步機(jī)構(gòu)要求生產(chǎn)者在邏輯上全部互連，這樣所產(chǎn)生的開銷可能很大；有些同步機(jī)構(gòu)只要求一個(gè)生產(chǎn)者知道其鄰居的情況，開銷也較少。 7) 初

11、始化。使用同步機(jī)構(gòu)要求系統(tǒng)應(yīng)容易進(jìn)行初始化，知道進(jìn)程何時(shí)可以進(jìn)行生產(chǎn)和消費(fèi)活動(dòng)。 8) 排序方法。當(dāng)生產(chǎn)者對一序列操作進(jìn)行某種指定排序時(shí)，必須交換報(bào)文，各種同步機(jī)構(gòu)實(shí)現(xiàn)效率可能大不相同。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) 分布式系統(tǒng)中同步機(jī)構(gòu)分布式系統(tǒng)中同步機(jī)構(gòu)：同步實(shí)體：同步實(shí)體：物理時(shí)鐘、事件計(jì)數(shù)器、邏輯時(shí)鐘、循環(huán)令牌和順序器、進(jìn)程等。 集中式同步機(jī)構(gòu)和分布式同步機(jī)構(gòu)：集中式同步機(jī)構(gòu)和分布式同步機(jī)構(gòu)：1) 在集中式同步機(jī)構(gòu)中，每個(gè)生產(chǎn)者每次發(fā)動(dòng)一個(gè)操作時(shí)均要訪問該同步實(shí)體。集中式同步實(shí)體有一個(gè)為所有必須相互同步的進(jìn)程都知道的名字，任何時(shí)候這些進(jìn)程的任何一

12、個(gè)均可訪問這一同步實(shí)體。執(zhí)行每個(gè)功能如進(jìn)程調(diào)度、數(shù)據(jù)訪問控制等均要經(jīng)過集中的同步實(shí)體進(jìn)行控制 。2) 分布式同步機(jī)構(gòu)不存在一個(gè)集中的同步實(shí)體，執(zhí)行各種功能時(shí)是分散控制的。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) 分布式系統(tǒng)中同步機(jī)構(gòu)分布式系統(tǒng)中同步機(jī)構(gòu)：集中式同步機(jī)構(gòu)和分布式同步機(jī)構(gòu)的優(yōu)缺點(diǎn)：集中式同步機(jī)構(gòu)和分布式同步機(jī)構(gòu)的優(yōu)缺點(diǎn)：1) 1) 集中式同步機(jī)構(gòu)最大的缺點(diǎn)是不可靠，一旦出故障就可能集中式同步機(jī)構(gòu)最大的缺點(diǎn)是不可靠，一旦出故障就可能造成全局不工作；另外在性能方面也大大下降，因?yàn)榧性斐扇植还ぷ?；另外在性能方面也大大下降，因?yàn)榧袝?huì)產(chǎn)生一個(gè)瓶頸。但實(shí)現(xiàn)簡

13、單。會(huì)產(chǎn)生一個(gè)瓶頸。但實(shí)現(xiàn)簡單。 2)2) 分布式同步機(jī)構(gòu)在可靠性和性能方面優(yōu)于集中式同步機(jī)構(gòu)，分布式同步機(jī)構(gòu)在可靠性和性能方面優(yōu)于集中式同步機(jī)構(gòu)，也有很多種，主要有多重物理時(shí)鐘、多重邏輯時(shí)鐘、循環(huán)也有很多種，主要有多重物理時(shí)鐘、多重邏輯時(shí)鐘、循環(huán)令牌等。但實(shí)現(xiàn)復(fù)雜。令牌等。但實(shí)現(xiàn)復(fù)雜。第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘準(zhǔn)確時(shí)間值的獲取和物理時(shí)鐘的同步準(zhǔn)確時(shí)間值的獲取和物理時(shí)鐘的同步 獲取物理時(shí)鐘的準(zhǔn)確值 ：物理時(shí)鐘服務(wù)器WWV或GEOS請求時(shí)間返回準(zhǔn)確時(shí)間然后，根據(jù)通信延遲進(jìn)行準(zhǔn)確地校正。物理時(shí)鐘需要從UTC(Universal Tim Coo

14、rdinator)獲得當(dāng)前時(shí)間。UTC提供當(dāng)前國際標(biāo)準(zhǔn)時(shí)間，有兩個(gè)著名站點(diǎn)WWV和GEOS。第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘準(zhǔn)確時(shí)間值的獲取和物理時(shí)鐘的同步準(zhǔn)確時(shí)間值的獲取和物理時(shí)鐘的同步 物理時(shí)鐘的同步過程：1) A通過網(wǎng)絡(luò)向B發(fā)送請求；2) B讀取本地時(shí)鐘值；3) B的時(shí)鐘值通過網(wǎng)絡(luò)傳遞給A；4) 按照網(wǎng)絡(luò)所需的傳輸延遲對B的時(shí)鐘值進(jìn)行校正；5) 比較A的時(shí)鐘值和B的時(shí)鐘值。 物理時(shí)鐘的同步方式：集中式、分布式。第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘的實(shí)現(xiàn)

15、方式：基于廣播的方式、請求驅(qū)動(dòng)的方式。在基于廣播的集中式物理時(shí)鐘的實(shí)現(xiàn)方案中，集中的時(shí)鐘服務(wù)員定期地向系統(tǒng)中的各個(gè)成員廣播當(dāng)前的時(shí)間?；趶V播的方式1：顧客只是簡單地將本地時(shí)間同所接收到的時(shí)間進(jìn)行對比，當(dāng)然這種對比考慮到了通常的網(wǎng)絡(luò)傳輸延遲，然后校正自己的本地時(shí)鐘。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘基于廣播的方式1：時(shí)間校正方法：1) 如果顧客的時(shí)鐘值大于時(shí)鐘服務(wù)員的時(shí)鐘值，顧客將自己的時(shí)鐘調(diào)慢，使之逐漸接近準(zhǔn)確的時(shí)間。時(shí)鐘值不能往回調(diào)，因?yàn)橛诚竦酱藭r(shí)鐘的事件已經(jīng)產(chǎn)生。 2) 如果顧客的時(shí)鐘值落后于時(shí)鐘服務(wù)員的時(shí)鐘值

16、，則顧客將時(shí)鐘值向前撥，同時(shí)將時(shí)鐘適當(dāng)?shù)卣{(diào)快。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘時(shí)間校正方法： 當(dāng)前時(shí)間=720 基于廣播 機(jī)器 A 時(shí)鐘服務(wù)員 A 時(shí)鐘服務(wù)員廣播當(dāng)前時(shí)間 當(dāng)前時(shí)間=740 延遲為 10 當(dāng)前時(shí)間=720 校正當(dāng)前時(shí)間=750 新的當(dāng)前時(shí)間=750 機(jī)器 A B校正本地時(shí)間 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘基于廣播的方式2（Berkeley算法）：1) 顧客收到廣播時(shí)間之后向集中的時(shí)間服務(wù)員發(fā)送它本地的當(dāng)前時(shí)間值；2) 每

17、個(gè)顧客到時(shí)間服務(wù)員有不同的平均延遲，這些延遲時(shí)間預(yù)先存放在時(shí)間服務(wù)員處。時(shí)間服務(wù)員根據(jù)這些延遲對不同顧客傳送來的當(dāng)?shù)貢r(shí)間進(jìn)行校正； 3) 任何校正過的時(shí)間如果同時(shí)間服務(wù)員上的時(shí)間差值超過了對應(yīng)節(jié)點(diǎn)到時(shí)間服務(wù)員的延遲時(shí)間常量，那么這個(gè)時(shí)間將不被列入考慮之列。因?yàn)檫@個(gè)時(shí)間可能是由于系統(tǒng)故障導(dǎo)致的，被認(rèn)為是不準(zhǔn)確的。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘基于廣播的方式2（Berkeley算法）：4) 剩余被校正的時(shí)間值連同時(shí)間服務(wù)員上的時(shí)間值一起進(jìn)行平均，這個(gè)平均值作為當(dāng)前時(shí)間。 5) 時(shí)間服務(wù)員為每個(gè)顧客計(jì)算誤差，然后將每個(gè)

18、誤差發(fā)送給對應(yīng)的顧客。 6) 每個(gè)顧客校正自己的時(shí)鐘。同前一個(gè)處理方式一樣，時(shí)鐘是不能往回?fù)艿模强梢园凑`差值將自己的時(shí)鐘慢下來。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘基于廣播的方式2（Berkeley算法）： 當(dāng)前時(shí)間=724 時(shí)間向前撥 5 顧客 A 當(dāng)前時(shí)間=740 A 的校正時(shí)間=734 B 的校正時(shí)間=743 平均時(shí)間=739 時(shí)間服務(wù)員 當(dāng)前時(shí)間=738 調(diào)慢時(shí)鐘 顧客 B 延遲 10 延遲 5 1 1 2 3 4 5 1. 廣播服務(wù)員時(shí)間 2. A 的當(dāng)前時(shí)間 724 3. B 的當(dāng)前時(shí)間 738 4.向

19、前撥 5 5.放慢時(shí)鐘 4 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘請求驅(qū)動(dòng)方式：(1) 顧客向時(shí)間服務(wù)員發(fā)送請求，要求獲得當(dāng)前時(shí)間；(2) 時(shí)間服務(wù)員返回當(dāng)前時(shí)間值；(3) 顧客計(jì)算本地的時(shí)間值和服務(wù)員返回的時(shí)間值之間的差值，這個(gè)差值用于時(shí)鐘值的校正；它的實(shí)現(xiàn)不僅考慮了網(wǎng)絡(luò)延遲，還包含了報(bào)文的響應(yīng)和服務(wù)時(shí)間；(4) 如果校正值大于預(yù)先規(guī)定好的門限值，則被認(rèn)為是不準(zhǔn)確的，這可能是由于網(wǎng)絡(luò)故障引起的，不準(zhǔn)確的值被丟棄；(5) 如果服務(wù)員返回的時(shí)間值被認(rèn)為是準(zhǔn)確的，則對本地時(shí)鐘進(jìn)行校正，同樣地，本地時(shí)鐘不能往回?fù)埽荒苁贡镜貢r(shí)鐘

20、慢下來。第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘集中式物理時(shí)鐘集中式物理時(shí)鐘請求驅(qū)動(dòng)方式：當(dāng)前時(shí)間=737 返回值=740 校正后時(shí)間=750 新的當(dāng)前時(shí)間=750 當(dāng)前時(shí)間=740 顧客 時(shí)間服務(wù)員 請求當(dāng)前時(shí)間 當(dāng)前時(shí)間=740 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘分布式物理時(shí)鐘分布式物理時(shí)鐘每個(gè)節(jié)點(diǎn)計(jì)算機(jī)以預(yù)先定義好的時(shí)間間隔定期地廣播它的當(dāng)前時(shí)間。由于時(shí)鐘存在漂移，假定廣播報(bào)文并不是很準(zhǔn)確地在同一時(shí)刻發(fā)出。一旦一個(gè)節(jié)點(diǎn)廣播了它的當(dāng)前時(shí)間，就立即啟動(dòng)一個(gè)定時(shí)器，在定時(shí)期內(nèi)接收其它節(jié)點(diǎn)的報(bào)文，每個(gè)報(bào)文標(biāo)

21、明了當(dāng)?shù)氐漠?dāng)前時(shí)間，然后分別按對應(yīng)的網(wǎng)絡(luò)延遲對其它節(jié)點(diǎn)的時(shí)間值進(jìn)行校正。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘分布式物理時(shí)鐘分布式物理時(shí)鐘時(shí)間值校正方法：(1) 計(jì)算所有節(jié)點(diǎn)的平均值，把這個(gè)值作為當(dāng)前時(shí)間。這種方法可能會(huì)產(chǎn)生不準(zhǔn)確的結(jié)果，因?yàn)槟承﹫?bào)文由于重發(fā)超出了通常的網(wǎng)絡(luò)延遲。(2) 設(shè)定一個(gè)容錯(cuò)門限延遲，這個(gè)門限為單次發(fā)送的最大網(wǎng)絡(luò)延遲，任何超過這個(gè)門限延遲的值被認(rèn)為是錯(cuò)誤的并被丟棄。其他未被丟棄的值進(jìn)行平均，平均值作為當(dāng)前時(shí)間。(3)丟棄m個(gè)最大的時(shí)間值和m個(gè)最小的時(shí)間值，這些值被認(rèn)為是不準(zhǔn)確的。剩下的進(jìn)行平均，平均值作為當(dāng)前時(shí)間。 第五章第

22、五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 物理時(shí)鐘分布式物理時(shí)鐘分布式物理時(shí)鐘時(shí)間值校正方法： 701 x 737 742 706 x 746 742 744 750 739 收到時(shí)鐘值 本地當(dāng)前時(shí)間=740 x 表示超過延遲門限的時(shí)間值 平均值即新的當(dāng)前時(shí)間=743 (a) 丟棄超過容錯(cuò)門限的時(shí)鐘值 701 x 737 742 706 x 746 x 742 744 750 x 739 本地當(dāng)前時(shí)間=740 收到時(shí)鐘值 m=2，x 表示丟棄時(shí)間值 平均值即新的當(dāng)前時(shí)間=741 (b) 丟棄若干最大和最小的時(shí)鐘值 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步

23、機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘可以給分布計(jì)算系統(tǒng)中的事件一個(gè)唯一的排序。邏輯時(shí)鐘的本質(zhì)是基于Lamport定義的“在先發(fā)生關(guān)系” 。在先發(fā)生關(guān)系在先發(fā)生關(guān)系 1) 如果a和b均是同一進(jìn)程中的兩個(gè)事件，并且a在b之前出現(xiàn)，則ab； 2) 若a代表“一個(gè)進(jìn)程發(fā)送一個(gè)報(bào)文”這個(gè)事件，b代表“另一個(gè)進(jìn)程接收這個(gè)報(bào)文”這個(gè)事件，則ab； 3) 如果ab，且bc，則ac。 兩個(gè)不同的事件a和b，如果ab，或ba，則事件a和b是因果關(guān)聯(lián)的。如果ab和ba均不成立，則稱事件a和b是并發(fā)的。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘在先發(fā)生關(guān)系的時(shí)空圖在先發(fā)生關(guān)系的

24、時(shí)空圖 水平方向代表空間，垂直方向代表時(shí)間，圓點(diǎn)代表事件，豎線代表進(jìn)程，進(jìn)程之間帶箭頭的線代表報(bào)文。 r4 q1 q2 q3 q4 q5 q6 p1 p2 進(jìn)程 P 進(jìn)程 Q 進(jìn)程 R p4 p3 q7 r1 r2 r3 時(shí)間 空間 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘邏輯時(shí)鐘 設(shè)Ci代表進(jìn)程i的邏輯時(shí)鐘，該邏輯時(shí)鐘就是一個(gè)函數(shù)，它給進(jìn)程i中的事件a分配一個(gè)正整數(shù)值Ci(a)。 1) 時(shí)鐘條件： 對任何事件a和b，如果ab，則C(a)C(b)。但相反的結(jié)論不能成立。a) 若a和b是同一進(jìn)程Pi中的兩個(gè)時(shí)間，并且ab，則Ci(a)Ci(b)；

25、b) 若a代表“一個(gè)Pi進(jìn)程發(fā)送一個(gè)報(bào)文”這個(gè)事件，b代表“另一個(gè)進(jìn)程Pj接收這個(gè)報(bào)文”這個(gè)事件，Ci(a)0) b) 當(dāng)收到一個(gè)帶時(shí)間戳的報(bào)文(m,LCj,j)時(shí)，我們更新LCi： LCi:=max(LCi,LCj)+d(d0) 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘邏輯時(shí)鐘 2) 標(biāo)量邏輯時(shí)鐘 r3(5) r2(2) q1(1) q2(2) q4(4) q3(3) q5(5) q6(6) 進(jìn)程 P 進(jìn)程 Q 進(jìn)程 R p4(6) p3(3) p2(2) q7(7) r1(1) r4(6) 時(shí)間 空間 p1(1) 第五章第五章 同步和互斥同

26、步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘邏輯時(shí)鐘 2) 向量邏輯時(shí)鐘 在向量邏輯時(shí)鐘中，每個(gè)進(jìn)程Pi和一個(gè)時(shí)間向量LCi1,n相關(guān)聯(lián)，其中a) 向量元素LCii描述了進(jìn)程Pi的邏輯時(shí)間進(jìn)展情況，即自身的邏輯時(shí)間進(jìn)展情況；b) 向量元素LCij表示進(jìn)程Pi所知的關(guān)于進(jìn)程Pj的邏輯時(shí)間進(jìn)展情況；c) 向量LCi1,n組成進(jìn)程Pi對于邏輯全局時(shí)間的局部視圖。 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘邏輯時(shí)鐘 2) 向量邏輯時(shí)鐘 任何一個(gè)邏輯時(shí)鐘LCi基于以下兩條規(guī)則更新它的邏輯時(shí)鐘值：a) 當(dāng)發(fā)生一個(gè)事件(一個(gè)外部發(fā)送或內(nèi)部事

27、件)之前，Pi更新LCii：LCii:=LCii+d (d0) b) 每個(gè)報(bào)文捎帶發(fā)送方在發(fā)送時(shí)的時(shí)鐘向量，當(dāng)收到一個(gè)帶時(shí)間戳的報(bào)文(m,LCj,j)時(shí)，Pi更新LCi： LCik:=max(LCik,LCjk)1knLCii:= LCii+d (d0) 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機(jī)構(gòu)同步機(jī)構(gòu) v 邏輯時(shí)鐘邏輯時(shí)鐘邏輯時(shí)鐘 2) 向量邏輯時(shí)鐘 r2(0,0,2) r1(0,0,1) q7(1,7,2) q6(1,6,0) q4(1,4,0) q5(1,5,0) q2(1,2,0) 進(jìn)程 P 進(jìn)程 Q 進(jìn)程 R p4(4,5,0) p3(3,1,0) p2(2,1,

28、0) q1(0,1,0) q3(1,3,0) r3(1,4,3) r4(1,4,4) 時(shí)間 空間 p1(1,0,0) 定義：n在先發(fā)生關(guān)系：abLCiLCj （P160）n并發(fā)關(guān)系： ab LCiLCj第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài)的定義的定義令LSi為進(jìn)程Pi的局部狀態(tài)，則全局狀態(tài)GS=(LS1，LS2，, LSn)。 1) 兩個(gè)集合：（P162有誤） )()(|),(jijiLSmrLSmsmLSLStransit)()(|),(jijiLSmrLSmsmLSLSntinconsiste集合transit包括了

29、進(jìn)程Pi和進(jìn)程Pj之間的通信通道上的所有報(bào)文，集合inconsistent包括了所有接收事件記錄在Pj而發(fā)送事件沒有記錄在Pi的報(bào)文。其中m是報(bào)文，s(m)是報(bào)文m的發(fā)送事件，r(m)是報(bào)文m的接收事件。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài)的定義的定義2) 一致的全局狀態(tài)和非一致的全局狀態(tài)：a) 全局狀態(tài)GS是一致的，當(dāng)且僅當(dāng) ),(,jiLSLSntinconsistejib) 全局狀態(tài)GS是非傳送中的，當(dāng)且僅當(dāng) ),(,jiLSLStransitji如果一個(gè)全局狀態(tài)是一致的并且是非傳送中的，那么它就是強(qiáng)一致的，也就

30、是說，局部狀態(tài)集是一致的并且沒有正在傳送中的報(bào)文。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài)的定義的定義 P1 P2 切割 c1 c2 P1 P2 c1 c2 切割 P1 P2 c1 c2 切割 P1 P2 c1 c2 切割 (a) 強(qiáng)一致全局狀態(tài) (b) 強(qiáng)一致全局狀態(tài) (c) 一致的全局狀態(tài) (d) 不一致的全局狀態(tài) 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@?。煺账惴ǎ?) 假如啟動(dòng)算法的進(jìn)程為P，那么它首先記錄自己的局部狀態(tài)，然后它沿

31、著它的輸出通道發(fā)送一個(gè)標(biāo)志(marker)，指示接收者應(yīng)該參與記錄一個(gè)全局狀態(tài)的工作。2) 當(dāng)接收者Q通過它的輸入通道C收到一個(gè)標(biāo)志，它將依據(jù)不同條件執(zhí)行以下不同操作： a) 如果Q還沒有記錄自己的局部狀態(tài)，它首先記錄自己的局部狀態(tài)，并記錄通道C的狀態(tài)為空報(bào)文序列，然后也沿著它自己的輸出通道發(fā)送一個(gè)標(biāo)志。 b) 如果Q已經(jīng)記錄了自己的局部狀態(tài)，通過通道C收到的標(biāo)志用來指示Q應(yīng)該記錄通道的狀態(tài)。通道的狀態(tài)是Q記錄它的局部狀態(tài)以來到收到這個(gè)標(biāo)志前所收到的報(bào)文系列。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@?。煺账惴?/p>

32、）：3) 如果一個(gè)進(jìn)程已經(jīng)沿它的每個(gè)輸入通道接收到一個(gè)標(biāo)志，并對每個(gè)標(biāo)志進(jìn)行了處理，就稱它已經(jīng)完成了它的那部分算法。4) 一個(gè)進(jìn)程的局部狀態(tài)，連同它的所有輸入通道的狀態(tài)將被發(fā)送到這個(gè)快照的發(fā)起進(jìn)程。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@?。煺账惴ǎ篜1 P2 P3 C12 C21 C32 C23 C13 C31 1) P1啟動(dòng)了快照算法，它同時(shí)執(zhí)行三個(gè)動(dòng)作：(a)記錄局部狀態(tài)；(b)發(fā)送一個(gè)標(biāo)志到C12和C13；(c)設(shè)置一個(gè)計(jì)數(shù)器對來自輸入通道C21和C31的報(bào)文進(jìn)行計(jì)數(shù)。 第五章第五章 同步和互斥同步

33、和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@取（快照算法）：P1 P2 P3 C12 C21 C32 C23 C13 C31 2) 一旦進(jìn)程P2從通道C12接收到標(biāo)志，它也執(zhí)行三個(gè)動(dòng)作：(a)記錄其局部狀態(tài)并記錄通道C12的狀態(tài)為空；(b)發(fā)送一個(gè)標(biāo)志到通道C21和C23；(c)設(shè)置一個(gè)計(jì)數(shù)器對來自輸入通道C32的報(bào)文進(jìn)行計(jì)數(shù)。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲取（快照算法）：的獲取（快照算法）：3) 類似地，進(jìn)程P3也執(zhí)行三個(gè)動(dòng)作。我們假定從進(jìn)程P1來的標(biāo)志比從進(jìn)程P3來的

34、標(biāo)志早到達(dá)進(jìn)程P2。一旦從進(jìn)程P3來的標(biāo)志到達(dá)進(jìn)程P2，P2就記錄通道C32的狀態(tài)為自設(shè)置計(jì)數(shù)器以來沿著這個(gè)通道接收到的報(bào)文的序列。于是進(jìn)程P2完成了自己的那部分算法，因?yàn)樗呀?jīng)從每個(gè)輸入通道接收到一個(gè)標(biāo)志并已經(jīng)記錄了自己的局部狀態(tài)。類似地，進(jìn)程P3在接收到從P1和P2發(fā)來的標(biāo)志后，屬于它的那部分算法終止。進(jìn)程P1在接收到從P2和P3發(fā)來的標(biāo)志后，屬于它的那部分算法終止。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 一致全局狀態(tài)的充要條件一致全局狀態(tài)的充要條件 Z Z字形路徑字形路徑：一條Z字形路徑存在于進(jìn)程Pi的檢查點(diǎn)A到進(jìn)程Pj的檢查點(diǎn)B(Pi和Pj可

35、以是同一個(gè)進(jìn)程)，當(dāng)且僅當(dāng)存在報(bào)文m1，m2，mn(n1)滿足：a) m1是進(jìn)程Pi在檢查點(diǎn)A之后發(fā)送的；b) 如果ml(1ln)被進(jìn)程Pk接收，則ml+1在同一個(gè)或后面的檢查點(diǎn)間隔被Pk發(fā)出。注意，ml+1可能在ml被接收之前或之后發(fā)送；c) mn被進(jìn)程Pj在檢查點(diǎn)B之前接收。 在Z字形路徑中，因果關(guān)系路徑中那樣的報(bào)文鏈?zhǔn)窃试S的，另外還允許這樣的報(bào)文鏈，即鏈中的任何報(bào)文在前一個(gè)報(bào)文被接收之前發(fā)送，只要發(fā)送和接收在同一個(gè)檢查點(diǎn)間隔里即可。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 一致全局狀態(tài)的充要條件一致全局狀態(tài)的充要條件 Z Z字形路徑實(shí)例字形路徑實(shí)

36、例： P1 P2 P3 C11 C21 C22 m1 m2 C31 C32 C12 m3 m4 從C11到C31的由報(bào)文m1和m2組成的路徑是一條Z字形路徑。從C11到C32的由報(bào)文m1和m3組成的路徑是一條Z字形路徑，同時(shí)也是一條因果關(guān)系路徑。檢查點(diǎn)C22形成一條由報(bào)文m4和m1組成的Z字形循環(huán)。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 一致全局狀態(tài)的充要條件一致全局狀態(tài)的充要條件 一致性定理一致性定理：一個(gè)檢查點(diǎn)集S，其中每個(gè)檢查點(diǎn)屬于不同的進(jìn)程，它們屬于同一個(gè)一致性的全局狀態(tài)當(dāng)且僅當(dāng)S中不存在這樣的檢查點(diǎn)，它有一條到S中任何其他檢查點(diǎn)(包括它自身

37、)的Z字形路徑。 推論：1) 檢查點(diǎn)C可以屬于一個(gè)一致性全局狀態(tài)當(dāng)且僅當(dāng)C不屬于一個(gè)Z字形循環(huán)； 2) 屬于不同進(jìn)程的兩個(gè)檢查點(diǎn)A和B，它們可以屬于同一個(gè)一致性全局狀態(tài)當(dāng)且僅當(dāng) a) 沒有包括A或B的Z字形循環(huán)；b) 在A和B之間不存在Z字形路徑。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 互斥問題互斥問題互斥問題就是定義一些基本的操作來解決共享資源的多個(gè)并發(fā)互斥問題就是定義一些基本的操作來解決共享資源的多個(gè)并發(fā)進(jìn)程的沖突問題。進(jìn)程的沖突問題。 互斥算法的主要目標(biāo)是保證在任一個(gè)時(shí)刻只能有一個(gè)進(jìn)程訪問臨界區(qū)。一個(gè)正確的互斥算法必須避免沖突(死鎖和餓死)和保證公平性。為

38、此，算法應(yīng)滿足以下三個(gè)條件： 1) 已獲得資源的進(jìn)程必須先釋放資源之后，另一個(gè)進(jìn)程才能得到資源； 2) 不同的請求應(yīng)該按照這些請求的產(chǎn)生順序獲得滿足，請求應(yīng)該按照某種規(guī)則進(jìn)行排序，例如使用邏輯時(shí)鐘確定請求的順序； 3) 若獲得資源的每個(gè)進(jìn)程最終都釋放資源，則每個(gè)請求最終都能滿足。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 互斥問題互斥問題衡量互斥算法性能的參數(shù)： 1) 完成一次互斥操作所需的報(bào)文數(shù)目；2) 同步延遲，即從一個(gè)進(jìn)程離開臨界區(qū)之后到下一個(gè)進(jìn)程進(jìn)入臨界區(qū)之前的時(shí)間間隔；3) 響應(yīng)時(shí)間，即從一個(gè)進(jìn)程發(fā)出請求到該進(jìn)程離開該臨界區(qū)之間的時(shí)間間隔。 第五章第五章

39、同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 集中式互斥算法集中式互斥算法 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v LamportLamport時(shí)間戳互斥算法時(shí)間戳互斥算法 LamportLamport時(shí)間戳互斥算法由以下時(shí)間戳互斥算法由以下5 5條規(guī)則組成條規(guī)則組成 ：1) 一個(gè)進(jìn)程Pi如果為了申請資源，它向其它各個(gè)進(jìn)程發(fā)送具有時(shí)間戳Tm:Pi的申請資源的報(bào)文，并把此報(bào)文也放到自己的申請隊(duì)列中； 2) 一個(gè)進(jìn)程Pj如果收到具有時(shí)間戳Tm:Pi的申請資源的報(bào)文，它把此報(bào)文放到自己的申請隊(duì)列中，并將向Pi發(fā)送一個(gè)帶有時(shí)間戳的承認(rèn)報(bào)文。如果Pj正在臨界區(qū)或正

40、在發(fā)送自己的申請報(bào)文，則此承認(rèn)報(bào)文要等到Pj從臨界區(qū)中退出之后或Pj發(fā)送完自己的申請報(bào)文之后再發(fā)送，否則立即發(fā)送； 3) 一個(gè)進(jìn)程Pi如果想釋放資源，它先從自己的申請隊(duì)列中刪除對應(yīng)的Tm:Pi申請報(bào)文，并向所有其他進(jìn)程發(fā)送具有時(shí)間戳的Pi釋放資源的報(bào)文； 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v LamportLamport時(shí)間戳互斥算法時(shí)間戳互斥算法 Lamport時(shí)間戳互斥算法由以下5條規(guī)則組成 ：4) 一個(gè)進(jìn)程Pj如果收到Pi釋放資源的報(bào)文，它從自己的申請隊(duì)列中刪除Tm:Pi申請報(bào)文； 5) 當(dāng)滿足下述兩個(gè)條件時(shí)，申請資源的進(jìn)程Pi獲得資源： a) Pi的申請

41、隊(duì)列中有Tm:Pi申請報(bào)文，并且根據(jù)時(shí)間戳它排在所有其它進(jìn)程發(fā)來的申請報(bào)文前面； b) Pi收到所有其它進(jìn)程的承認(rèn)報(bào)文，其上面的時(shí)間戳值大于Tm。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v LamportLamport時(shí)間戳互斥算法時(shí)間戳互斥算法( (實(shí)際上實(shí)際上3 3個(gè)，個(gè)，P168-170) P168-170) Lamport時(shí)間戳互斥算法實(shí)例： P1 P2 P3 請求報(bào)文 承認(rèn)報(bào)文 釋放報(bào)文 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v Ricart-AgrawalaRicart-Agrawala互斥算法互斥算法 1) 一個(gè)進(jìn)程申請資源

42、時(shí)向所有其他進(jìn)程發(fā)出申請報(bào)文；2) 其它進(jìn)程收到申請報(bào)文后若不在臨界區(qū)并且自己未申請進(jìn)入臨界區(qū)，或者自己雖然發(fā)出了申請報(bào)文，但自己的報(bào)文排在收到的申請報(bào)文之后，則回答表示同意；3) 申請資源的進(jìn)程僅在收到所有進(jìn)程的回答報(bào)文后才進(jìn)入臨界區(qū)使用資源；4) 一個(gè)進(jìn)程使用完資源后，它向所有未給回答的其它申請發(fā)送回答報(bào)文。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v Ricart-AgrawalaRicart-Agrawala互斥算法互斥算法 Ricart-AgrawalaRicart-Agrawala互斥算法實(shí)例：互斥算法實(shí)例： P1 P2 P3 請求報(bào)文 回答報(bào)文 第五章第

43、五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v MaekawaMaekawa互斥算法互斥算法 請求子集：請求子集：在Maekawa互斥算法中，一個(gè)進(jìn)程P在發(fā)出申請報(bào)文后，不用得到所有其他進(jìn)程的回答，而只須得到一個(gè)進(jìn)程子集S中的所有進(jìn)程的回答即可進(jìn)入臨界區(qū)。稱S是P的請求子集。假設(shè)Ri和Rj分別是進(jìn)程Pi和Pj的請求子集，要求RiRjNULL。 1) 當(dāng)進(jìn)程Pi請求進(jìn)入臨界區(qū)時(shí)，它只向Ri中的進(jìn)程發(fā)送請求報(bào)文。2) 當(dāng)進(jìn)程Pj收到一個(gè)請求報(bào)文時(shí)，如果它自上一次臨界區(qū)釋放后還沒有發(fā)出過回答報(bào)文給任何進(jìn)程，且自己的請求隊(duì)列中無任何請求，它就給該請求報(bào)文一個(gè)回答。否則，請求報(bào)文被放入請求

44、隊(duì)列中。3) 進(jìn)程Pi只有收到Ri中的所有進(jìn)程的回答后，才能進(jìn)入臨界區(qū)。4) 在釋放臨界區(qū)時(shí)，進(jìn)程Pi只給Ri中的所有進(jìn)程發(fā)送釋放報(bào)文。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v MaekawaMaekawa互斥算法互斥算法 請求子集的例子請求子集的例子：考慮一個(gè)七個(gè)進(jìn)程的例子，每個(gè)進(jìn)程的請求子集如下：考慮一個(gè)七個(gè)進(jìn)程的例子，每個(gè)進(jìn)程的請求子集如下：R R1 1：PP1 1，P P3 3，P P4 4 ；R R2 2：PP2 2，P P4 4，P P5 5 ； R R3 3：PP3 3，P P5 5，P P6 6 ； R R4 4：PP4 4，P P6 6，P P7

45、 7 ；R R5 5：PP5 5，P P7 7，P P1 1 ；R R6 6：PP6 6，P P1 1，P P2 2 ；R R7 7：PP7 7，P P2 2，P P3 3 。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v MaekawaMaekawa互斥算法互斥算法 MaekawaMaekawa算法的兩個(gè)極端情況：算法的兩個(gè)極端情況：(1) (1) 退化為集中式互斥算法。退化為集中式互斥算法。P Pc c(c1(c1，2 2，n)n)作為協(xié)調(diào)者，作為協(xié)調(diào)者，對所有進(jìn)程對所有進(jìn)程P Pi i，有：，有：R Ri i：PPc c ，1in1in(2) (2) 完全分布式的

46、互斥算法。對所有進(jìn)程完全分布式的互斥算法。對所有進(jìn)程P Pi i，有：，有：R Ri i：PP1 1，P P2 2，P Pn n ，1in 1in 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 簡單令牌環(huán)互斥算法簡單令牌環(huán)互斥算法 1) 1) 在有在有n n個(gè)進(jìn)程的系統(tǒng)中，將這個(gè)進(jìn)程的系統(tǒng)中，將這n n個(gè)進(jìn)程組成一個(gè)首尾相連的邏個(gè)進(jìn)程組成一個(gè)首尾相連的邏輯環(huán)。每個(gè)進(jìn)程在環(huán)中有一個(gè)指定的位置，位置可以按網(wǎng)絡(luò)輯環(huán)。每個(gè)進(jìn)程在環(huán)中有一個(gè)指定的位置，位置可以按網(wǎng)絡(luò)地址進(jìn)行排列，當(dāng)然也可以采用任何其他可行的方式排列，地址進(jìn)行排列，當(dāng)然也可以采用任何其他可行的方式排列，但每個(gè)進(jìn)程必

47、須知道在環(huán)中哪個(gè)進(jìn)程是它后面的進(jìn)程。但每個(gè)進(jìn)程必須知道在環(huán)中哪個(gè)進(jìn)程是它后面的進(jìn)程。 2)2) 一個(gè)進(jìn)程擁有令牌時(shí)就可以進(jìn)入臨界區(qū)，令牌可在所有的進(jìn)一個(gè)進(jìn)程擁有令牌時(shí)就可以進(jìn)入臨界區(qū)，令牌可在所有的進(jìn)程間傳遞。程間傳遞。 3)3) 如果得到令牌的進(jìn)程不打算進(jìn)入臨界區(qū)，它只是簡單地將令如果得到令牌的進(jìn)程不打算進(jìn)入臨界區(qū)，它只是簡單地將令牌傳送給它后面的進(jìn)程。牌傳送給它后面的進(jìn)程。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 簡單令牌環(huán)互斥算法簡單令牌環(huán)互斥算法 P0P1P2P3P4P5P0P1P2P3P4P5問題：如果令牌丟失，需要重新產(chǎn)生一個(gè)令牌，但檢測令牌是否丟失是

48、比較困難的。 另外一個(gè)問題是進(jìn)程的崩潰，但進(jìn)程的崩潰比較容易檢測。 這個(gè)算法在高負(fù)載的情況下工作得很好。然而，它在輕負(fù)載的情況下工作得很差，出現(xiàn)很多不必要的報(bào)文傳遞。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v Ricart-AgrawalaRicart-Agrawala令牌環(huán)互斥算法令牌環(huán)互斥算法 1) 初始時(shí)，令牌被賦予給任何一個(gè)進(jìn)程。 2) 請求進(jìn)入臨界區(qū)的進(jìn)程Pj不知道哪個(gè)進(jìn)程擁有令牌，所以它向所有其它進(jìn)程發(fā)送一個(gè)帶時(shí)間戳的請求報(bào)文，請求得到令牌。每個(gè)進(jìn)程有一個(gè)請求隊(duì)列記錄有所有進(jìn)程的請求，令牌中記錄有每個(gè)進(jìn)程最后一個(gè)持有令牌的時(shí)間。 3) 如果當(dāng)前擁有令牌的

49、進(jìn)程Pi不再需要令牌，它就按照i+1，i+2，n，1，2，i-1的順序?qū)ふ业谝粋€(gè)符合條件的進(jìn)程Pj，并將令牌傳遞給進(jìn)程Pj。說明：雖然該算法不是按照每個(gè)請求的時(shí)間順序來滿足的，但是，由于令牌是按一個(gè)方向繞環(huán)傳遞的，所以不會(huì)有餓死現(xiàn)象發(fā)生。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 基于時(shí)間戳的令牌互斥算法基于時(shí)間戳的令牌互斥算法 每個(gè)進(jìn)程保持一張進(jìn)程狀態(tài)表，記錄它所知的進(jìn)程狀態(tài)，進(jìn)程狀態(tài)包括該進(jìn)程是否為請求進(jìn)程，以及得到該狀態(tài)的時(shí)間。令牌是一個(gè)特殊的報(bào)文，該報(bào)文中包含了發(fā)送該令牌的進(jìn)程的進(jìn)程狀態(tài)表。 1)初始化時(shí)，每個(gè)進(jìn)程的狀態(tài)表中各個(gè)進(jìn)程均為非請求狀態(tài)，時(shí)鐘值為0

50、，并任意指定一個(gè)進(jìn)程為令牌的持有者。 2) 請求時(shí)，一個(gè)進(jìn)程請求進(jìn)入臨界區(qū)時(shí)，如果它持有令牌，它不發(fā)送任何請求報(bào)文，將自己的進(jìn)程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時(shí)鐘值，直接進(jìn)入臨界區(qū)。如果它不持有令牌，則它向所有其它進(jìn)程發(fā)送帶有時(shí)間戳的請求報(bào)文。發(fā)出請求報(bào)文后，將自己的進(jìn)程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時(shí)鐘值。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 基于時(shí)間戳的令牌互斥算法基于時(shí)間戳的令牌互斥算法 3) 收到請求時(shí)，當(dāng)進(jìn)程A收到進(jìn)程B的請求報(bào)文時(shí)，A將B的請求報(bào)文中的時(shí)間戳同A的進(jìn)程狀態(tài)表中B的時(shí)間值進(jìn)行比較。若B的

51、請求報(bào)文中的時(shí)間戳大于A的進(jìn)程狀態(tài)表中B的時(shí)間值，則A修改自己的進(jìn)程狀態(tài)表。將A的進(jìn)程狀態(tài)表中對應(yīng)于B的一欄改為請求狀態(tài)，并記錄此狀態(tài)的時(shí)間。 4) 退出臨界區(qū)時(shí)，進(jìn)程A退出臨界區(qū)后，將自己的進(jìn)程狀態(tài)表中關(guān)于自己的一欄改為非請求狀態(tài)，時(shí)鐘值加1，并將該時(shí)鐘值作為該狀態(tài)的時(shí)間。然后檢查其進(jìn)程狀態(tài)表中是否記錄有某個(gè)進(jìn)程處于請求狀態(tài)，若有，則從處于請求狀態(tài)的進(jìn)程中選取一個(gè)請求最早的進(jìn)程B(具有最小的時(shí)間戳)，將令牌傳送給它，并在令牌中附上A的進(jìn)程狀態(tài)表。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 基于時(shí)間戳的令牌互斥算法基于時(shí)間戳的令牌互斥算法 5) 收到令牌時(shí)，收到令牌

52、的進(jìn)程把隨令牌傳來的進(jìn)程狀態(tài)表和自己的進(jìn)程狀態(tài)表進(jìn)行比較。若隨令牌傳來的進(jìn)程狀態(tài)表中某進(jìn)程的時(shí)間戳大于自己的進(jìn)程狀態(tài)表中相應(yīng)進(jìn)程的時(shí)間戳，則將自己的進(jìn)程狀態(tài)表中相應(yīng)進(jìn)程的狀態(tài)和時(shí)間戳該成隨令牌傳來的進(jìn)程狀態(tài)表中相應(yīng)的狀態(tài)和時(shí)間戳。說明：同Ricart-Agrawala令牌環(huán)互斥算法相比，具有更強(qiáng)的公平性，因?yàn)樗腔谡埱蟮南群箜樞騺頋M足的，而Ricart-Agrawala令牌環(huán)互斥算法是基于進(jìn)程的邏輯環(huán)結(jié)構(gòu)來滿足的。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v 選舉算法選舉算法 從進(jìn)程集中選出一個(gè)進(jìn)程執(zhí)行特別的任務(wù)。大部分選舉算法是基于全局優(yōu)先級的，就是說給每個(gè)進(jìn)程預(yù)先分配一個(gè)優(yōu)先級，選舉算法選擇一個(gè)具有最高優(yōu)先級的進(jìn)程作為協(xié)調(diào)者。 BullyBully選舉算法選舉算法 1)P發(fā)送選舉報(bào)文到所有優(yōu)先級比它高的進(jìn)程。2) 如果在一定時(shí)間內(nèi)收不到任何響應(yīng)報(bào)文，P贏得選舉成為協(xié)調(diào)者。它向所有比它的優(yōu)先級低的進(jìn)程發(fā)送通知報(bào)文，宣布自己是協(xié)調(diào)者。3) 如果收到一個(gè)優(yōu)先級比它高的進(jìn)程的回答，P的選舉工作結(jié)束。同時(shí)啟動(dòng)一個(gè)計(jì)時(shí)器，等待接收誰是協(xié)調(diào)者的通知報(bào)文，如果在規(guī)定時(shí)間內(nèi)得不到通知