第5章同步和互斥

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、件)之前，Pi更新LCii：LCii:=LCii+d (d0) b) 每個報文捎帶發(fā)送方在發(fā)送時的時鐘向量，當收到一個帶時間戳的報文(m,LCj,j)時，Pi更新LCi： LCik:=max(LCik,LCjk)1knLCii:= LCii+d (d0) 第五章第五章 同步和互斥同步和互斥 5.2 5.2 同步機構(gòu)同步機構(gòu) v 邏輯時鐘邏輯時鐘邏輯時鐘 2) 向量邏輯時鐘 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) 進程 P 進程 Q 進程 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) 時間 空間 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為進程Pi的局部狀態(tài)，則全局狀態(tài)GS=(LS1，LS2，, LSn)。 1) 兩個集合：（P162有誤） )()(|),(jijiLSmrLSmsmLSLStransit)()(|),(jijiLSmrLSmsmLSLSntinconsiste集合transit包括了

29、進程Pi和進程Pj之間的通信通道上的所有報文，集合inconsistent包括了所有接收事件記錄在Pj而發(fā)送事件沒有記錄在Pi的報文。其中m是報文，s(m)是報文m的發(fā)送事件，r(m)是報文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是一致的，當且僅當 ),(,jiLSLSntinconsistejib) 全局狀態(tài)GS是非傳送中的，當且僅當 ),(,jiLSLStransitji如果一個全局狀態(tài)是一致的并且是非傳送中的，那么它就是強一致的，也就

30、是說，局部狀態(tài)集是一致的并且沒有正在傳送中的報文。 第五章第五章 同步和互斥同步和互斥 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) 強一致全局狀態(tài) (b) 強一致全局狀態(tài) (c) 一致的全局狀態(tài) (d) 不一致的全局狀態(tài) 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@?。煺账惴ǎ?) 假如啟動算法的進程為P，那么它首先記錄自己的局部狀態(tài)，然后它沿

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

32、）：3) 如果一個進程已經(jīng)沿它的每個輸入通道接收到一個標志，并對每個標志進行了處理，就稱它已經(jīng)完成了它的那部分算法。4) 一個進程的局部狀態(tài)，連同它的所有輸入通道的狀態(tài)將被發(fā)送到這個快照的發(fā)起進程。 第五章第五章 同步和互斥同步和互斥 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啟動了快照算法，它同時執(zhí)行三個動作：(a)記錄局部狀態(tài)；(b)發(fā)送一個標志到C12和C13；(c)設置一個計數(shù)器對來自輸入通道C21和C31的報文進行計數(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) 一旦進程P2從通道C12接收到標志，它也執(zhí)行三個動作：(a)記錄其局部狀態(tài)并記錄通道C12的狀態(tài)為空；(b)發(fā)送一個標志到通道C21和C23；(c)設置一個計數(shù)器對來自輸入通道C32的報文進行計數(shù)。 第五章第五章 同步和互斥同步和互斥 5.35.3系統(tǒng)的全局狀態(tài)系統(tǒng)的全局狀態(tài) v 全局狀態(tài)全局狀態(tài)的獲?。煺账惴ǎ旱墨@取（快照算法）：3) 類似地，進程P3也執(zhí)行三個動作。我們假定從進程P1來的標志比從進程P3來的

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

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

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

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

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

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

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

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

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

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

44、隊列中。3) 進程Pi只有收到Ri中的所有進程的回答后，才能進入臨界區(qū)。4) 在釋放臨界區(qū)時，進程Pi只給Ri中的所有進程發(fā)送釋放報文。 第五章第五章 同步和互斥同步和互斥 5.45.4互斥算法互斥算法 v MaekawaMaekawa互斥算法互斥算法 請求子集的例子請求子集的例子：考慮一個七個進程的例子，每個進程的請求子集如下：考慮一個七個進程的例子，每個進程的請求子集如下：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算法的兩個極端情況：算法的兩個極端情況：(1) (1) 退化為集中式互斥算法。退化為集中式互斥算法。P Pc c(c1(c1，2 2，n)n)作為協(xié)調(diào)者，作為協(xié)調(diào)者，對所有進程對所有進程P Pi i，有：，有：R Ri i：PPc c ，1in1in(2) (2) 完全分布式的

46、互斥算法。對所有進程完全分布式的互斥算法。對所有進程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個進程的系統(tǒng)中，將這個進程的系統(tǒng)中，將這n n個進程組成一個首尾相連的邏個進程組成一個首尾相連的邏輯環(huán)。每個進程在環(huán)中有一個指定的位置，位置可以按網(wǎng)絡輯環(huán)。每個進程在環(huán)中有一個指定的位置，位置可以按網(wǎng)絡地址進行排列，當然也可以采用任何其他可行的方式排列，地址進行排列，當然也可以采用任何其他可行的方式排列，但每個進程必

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

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

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

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

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

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