第5章同步和互斥

第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

資源管理方式

全集中管理方式：所有資源都由一個服務員管理；集中分布管理方式：一個資源由一個服務員管理；全分布管理方式：一個資源是由多個服務員共同管理。(a)

全集中式

(b)

全分布式

(c)

集中分布式

第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

控制空間

說明資源管理分散程度的參數(shù)：參加一個資源的多重管理的服務員數(shù)；被多個服務員管理的資源數(shù)。(a)

集中的控制(b)

低度的分散控制

(c)

中度的分散控制(d)

高度的分散控制

(e)

全分散控制

按參加多重管理的服務員數(shù)排序：第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

(a)

沒有資源被多重管理

(b)

一個資源被多重管理

(c)

兩個資源被多重管理

(d)

三個資源被多重管理

(e)

四個資源被多重管理

按由多個服務員管理的資源數(shù)目排序

第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

控制空間：

參加多重管理的服務員數(shù)目

控制空間

最大集中

最大分散

被多重管理的資源數(shù)目第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

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

5.1分布式系統(tǒng)中的資源管理

1

2

3

全部

各個活動

(a)一致性的最大集中

1

2

3

全部各個活動

(b)一致性的最大分散

1

N

1

N

一致性：第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

均等性：

責

任

和

權

限

0

Y

1

N

(a)各服務員的不同管理權限和責任

各服務員

責

任

和

權

限

1

Y

N

各服務員

(b)均等性中的最大集中

0

1

0

責

任

和

權

限

N

Y

(c)均等性中的最大分散

各服務員

第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

參加每個活動的服務員數(shù)目：第五章同步和互斥

5.1分布式系統(tǒng)中的資源管理

單個資源的控制空間

：可以將單個資源控制空間和集體資源控制空間合并成一個五維空間。方法是加上資源個數(shù)、控制程度。計算機與網絡系統(tǒng)的4種體系結構Host/TerminalWorkstation/FileServerClient/ServerPeer-to-Peer資源分配原則1、全集中管理方式中：資源申請者總是向惟一的服務員提出，服務員按一定順序處理每個申請，如果資源已經被分配則申請者等待。只要不發(fā)生死鎖和占用資源者無限期占用資源的情況，任何申請者必定能在有限時間內獲得資源。比如Host系統(tǒng)2、集中分布管理方式中：申請者先向一個服務員提出申請，如果暫時不能獲得資源就轉向另一個服務員申請。這時可能發(fā)生“餓死”現(xiàn)象。當然，也有可能發(fā)生死鎖3、全分布管理方式中：申請者向任一服務員提出申請，服務員共同協(xié)商分配資源。還會發(fā)生“餓死”和死鎖現(xiàn)象嗎？第五章同步和互斥

5.2同步機構

分布式系統(tǒng)中同步機構的作用

同步點：為了達到合作，各個進程在執(zhí)行的過程中必須存在若干點，超過這些點時，一個進程在另一個進程執(zhí)行完某一活動前不能繼續(xù)執(zhí)行，這些點稱為這兩個進程之間的同步點。

分布計算系統(tǒng)中共享資源的兩類：一類是各進程可以同時訪問的，如中央處理機(允許多個進程交疊使用一個處理機)、只讀文件和不允許修改的存放子程序和數(shù)據的主存區(qū)域等；另一類是不允許多個進程同時訪問的，每次只允許一個進程使用，如大多數(shù)外部設備(如打印機)、可寫的文件以及主存中可修改的區(qū)域等。同步機構在互斥控制中的作用是對活動的執(zhí)行進行排序。

第五章同步和互斥

5.2同步機構

分布式系統(tǒng)中同步機構的作用

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

5.2同步機構

分布計算系統(tǒng)的計算方式分成三種：完全分割的計算。一個操作所激發(fā)的不同活動由不同的消費者分別獨自處理。在這種情況下，同步機構的目的是保證所有相互干擾的活動成為有序的，使得該操作保持原子性(要么完成操作，要么干脆不發(fā)生)。分割和部分復制的計算。一個操作所激發(fā)的活動中，某些是由不同的消費者獨自處理的，某些操作是由一些消費者共同處理。它兼有前面兩種計算形式的特點。對于不同的計算方式，同步機構的目的和要求也是不同的。第五章同步和互斥

5.2同步機構

評價同步機構的標準：響應時間和吞吐量。各種機構應盡量利用系統(tǒng)的并行性質，以提高吞吐量和縮短響應時間?；謴湍芰?。同步機構應能使系統(tǒng)從故障中恢復過來。開銷。指使用同步機構的代價，包括額外增加的報文長度、數(shù)量和對它們的處理時間，以及用于存放同步信息所需的額外存儲空間。公平性。操作發(fā)生沖突時，同步機構應能避免生產者餓死，各生產者具有平等的權利。

第五章同步和互斥

5.2同步機構

評價同步機構的標準：可擴充性。系統(tǒng)擴充新的處理機時同步機構應不影響其正常運行。連接方式。使用某些同步機構要求生產者在邏輯上全部互連，這樣所產生的開銷可能很大；有些同步機構只要求一個生產者知道其鄰居的情況，開銷也較少。初始化。使用同步機構要求系統(tǒng)應容易進行初始化，知道進程何時可以進行生產和消費活動。排序方法。當生產者對一序列操作進行某種指定排序時，必須交換報文，各種同步機構實現(xiàn)效率可能大不相同。

第五章同步和互斥

5.2同步機構

分布式系統(tǒng)中同步機構：同步實體：物理時鐘、事件計數(shù)器、邏輯時鐘、循環(huán)令牌和順序器、進程等。

集中式同步機構和分布式同步機構：在集中式同步機構中，每個生產者每次發(fā)動一個操作時均要訪問該同步實體。集中式同步實體有一個為所有必須相互同步的進程都知道的名字，任何時候這些進程的任何一個均可訪問這一同步實體。執(zhí)行每個功能如進程調度、數(shù)據訪問控制等均要經過集中的同步實體進行控制。分布式同步機構不存在一個集中的同步實體，執(zhí)行各種功能時是分散控制的。第五章同步和互斥

5.2同步機構

分布式系統(tǒng)中同步機構：集中式同步機構和分布式同步機構的優(yōu)缺點：集中式同步機構最大的缺點是不可靠，一旦出故障就可能造成全局不工作；另外在性能方面也大大下降，因為集中會產生一個瓶頸。但實現(xiàn)簡單。

分布式同步機構在可靠性和性能方面優(yōu)于集中式同步機構，也有很多種，主要有多重物理時鐘、多重邏輯時鐘、循環(huán)令牌等。但實現(xiàn)復雜。第五章同步和互斥

5.2同步機構

物理時鐘準確時間值的獲取和物理時鐘的同步

獲取物理時鐘的準確值：物理時鐘服務器WWV或GEOS請求時間返回準確時間然后，根據通信延遲進行準確地校正。物理時鐘需要從UTC(UniversalTimCoordinator)獲得當前時間。UTC提供當前國際標準時間，有兩個著名站點WWV和GEOS。第五章同步和互斥

5.2同步機構

物理時鐘準確時間值的獲取和物理時鐘的同步

物理時鐘的同步過程：A通過網絡向B發(fā)送請求；B讀取本地時鐘值；B的時鐘值通過網絡傳遞給A；按照網絡所需的傳輸延遲對B的時鐘值進行校正；比較A的時鐘值和B的時鐘值。物理時鐘的同步方式：集中式、分布式。第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘集中式物理時鐘的實現(xiàn)方式：基于廣播的方式、請求驅動的方式。在基于廣播的集中式物理時鐘的實現(xiàn)方案中，集中的時鐘服務員定期地向系統(tǒng)中的各個成員廣播當前的時間?；趶V播的方式1：顧客只是簡單地將本地時間同所接收到的時間進行對比，當然這種對比考慮到了通常的網絡傳輸延遲，然后校正自己的本地時鐘。

第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘基于廣播的方式1：時間校正方法：如果顧客的時鐘值大于時鐘服務員的時鐘值，顧客將自己的時鐘調慢，使之逐漸接近準確的時間。時鐘值不能往回調，因為映像到此時鐘的事件已經產生。如果顧客的時鐘值落后于時鐘服務員的時鐘值，則顧客將時鐘值向前撥，同時將時鐘適當?shù)卣{快。

第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘時間校正方法：第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘基于廣播的方式2（Berkeley算法）：顧客收到廣播時間之后向集中的時間服務員發(fā)送它本地的當前時間值；每個顧客到時間服務員有不同的平均延遲，這些延遲時間預先存放在時間服務員處。時間服務員根據這些延遲對不同顧客傳送來的當?shù)貢r間進行校正；任何校正過的時間如果同時間服務員上的時間差值超過了對應節(jié)點到時間服務員的延遲時間常量，那么這個時間將不被列入考慮之列。因為這個時間可能是由于系統(tǒng)故障導致的，被認為是不準確的。

第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘基于廣播的方式2（Berkeley算法）：剩余被校正的時間值連同時間服務員上的時間值一起進行平均，這個平均值作為當前時間。時間服務員為每個顧客計算誤差，然后將每個誤差發(fā)送給對應的顧客。每個顧客校正自己的時鐘。同前一個處理方式一樣，時鐘是不能往回撥的，但是可以按誤差值將自己的時鐘慢下來。

第五章同步和互斥

5.2同步機構

物理時鐘集中式物理時鐘基于廣播的方式2（Berkeley算法）：第五章同步和互斥

5.2同步機構

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

5.2同步機構

物理時鐘集中式物理時鐘請求驅動方式：當前時間=737

返回值=740

校正后時間=750

新的當前時間=750

當前時間=740

顧客

時間服務員

請求當前時間

當前時間=740

第五章同步和互斥

5.2同步機構

物理時鐘分布式物理時鐘每個節(jié)點計算機以預先定義好的時間間隔定期地廣播它的當前時間。由于時鐘存在漂移，假定廣播報文并不是很準確地在同一時刻發(fā)出。一旦一個節(jié)點廣播了它的當前時間，就立即啟動一個定時器，在定時期內接收其它節(jié)點的報文，每個報文標明了當?shù)氐漠斍皶r間，然后分別按對應的網絡延遲對其它節(jié)點的時間值進行校正。

第五章同步和互斥

5.2同步機構

物理時鐘分布式物理時鐘時間值校正方法：(1)計算所有節(jié)點的平均值，把這個值作為當前時間。這種方法可能會產生不準確的結果，因為某些報文由于重發(fā)超出了通常的網絡延遲。(2)設定一個容錯門限延遲，這個門限為單次發(fā)送的最大網絡延遲，任何超過這個門限延遲的值被認為是錯誤的并被丟棄。其他未被丟棄的值進行平均，平均值作為當前時間。(3)丟棄m個最大的時間值和m個最小的時間值，這些值被認為是不準確的。剩下的進行平均，平均值作為當前時間。

第五章同步和互斥

5.2同步機構

物理時鐘分布式物理時鐘時間值校正方法：第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘可以給分布計算系統(tǒng)中的事件一個唯一的排序。邏輯時鐘的本質是基于Lamport定義的“在先發(fā)生關系”。在先發(fā)生關系

如果a和b均是同一進程中的兩個事件，并且a在b之前出現(xiàn)，則a→b；若a代表“一個進程發(fā)送一個報文”這個事件，b代表“另一個進程接收這個報文”這個事件，則a→b；如果a→b，且b→c，則a→c。

兩個不同的事件a和b，如果a→b，或b→a，則事件a和b是因果關聯(lián)的。如果a→b和b→a均不成立，則稱事件a和b是并發(fā)的。

第五章同步和互斥

5.2同步機構

邏輯時鐘在先發(fā)生關系的時空圖

水平方向代表空間，垂直方向代表時間，圓點代表事件，豎線代表進程，進程之間帶箭頭的線代表報文。

第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

設Ci代表進程i的邏輯時鐘，該邏輯時鐘就是一個函數(shù)，它給進程i中的事件a分配一個正整數(shù)值Ci(a)。

時鐘條件： 對任何事件a和b，如果a→b，則C(a)<C(b)。但相反的結論不能成立。若a和b是同一進程Pi中的兩個時間，并且a→b，則Ci(a)<Ci(b)；若a代表“一個Pi進程發(fā)送一個報文”這個事件，b代表“另一個進程Pj接收這個報文”這個事件，Ci(a)<Cj(b)。第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

標量邏輯時鐘

每個進程Pi有一個邏輯時鐘LCi，LCi被初始化為init(init≥0)并且它是一個非減的整數(shù)序列。進程Pi發(fā)送的每個報文m都被標上LCi的當前值和進程的標號i，從而形成一個三元組(m,LCi,i)。任何一個邏輯時鐘LCi基于以下兩條規(guī)則更新它的邏輯時鐘值：當發(fā)生一個事件(一個外部發(fā)送或內部事件)之前，我們更新LCi：LCi:=LCi+d (d>0)當收到一個帶時間戳的報文(m,LCj,j)時，我們更新LCi：LCi:=max(LCi,LCj)+d (d>0)第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

標量邏輯時鐘

第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

向量邏輯時鐘

在向量邏輯時鐘中，每個進程Pi和一個時間向量LCi[1,…,n]相關聯(lián)，其中向量元素LCi[i]描述了進程Pi的邏輯時間進展情況，即自身的邏輯時間進展情況；向量元素LCi[j]表示進程Pi所知的關于進程Pj的邏輯時間進展情況；向量LCi[1,…,n]組成進程Pi對于邏輯全局時間的局部視圖。第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

向量邏輯時鐘

任何一個邏輯時鐘LCi基于以下兩條規(guī)則更新它的邏輯時鐘值：當發(fā)生一個事件(一個外部發(fā)送或內部事件)之前，Pi更新LCi[i]：

LCi[i]:=LCi[i]+d (d>0)每個報文捎帶發(fā)送方在發(fā)送時的時鐘向量，當收到一個帶時間戳的報文(m,LCj,j)時，Pi更新LCi：

LCi[k]:=max(LCi[k],LCj[k]) 1≤k≤n

LCi[i]:=LCi[i]+d (d>0)第五章同步和互斥

5.2同步機構

邏輯時鐘邏輯時鐘

向量邏輯時鐘

定義：在先發(fā)生關系：a→bLCi<LCj

（P160）并發(fā)關系：a‖b

LCi‖LCj第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

系統(tǒng)的全局狀態(tài)的定義令LSi為進程Pi的局部狀態(tài)，則全局狀態(tài)GS=(LS1，LS2，…,LSn)。

兩個集合：（P162有誤）

集合transit包括了進程Pi和進程Pj之間的通信通道上的所有報文，集合inconsistent包括了所有接收事件記錄在Pj而發(fā)送事件沒有記錄在Pi的報文。其中m是報文，s(m)是報文m的發(fā)送事件，r(m)是報文m的接收事件。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

系統(tǒng)的全局狀態(tài)的定義一致的全局狀態(tài)和非一致的全局狀態(tài)：全局狀態(tài)GS是一致的，當且僅當全局狀態(tài)GS是非傳送中的，當且僅當如果一個全局狀態(tài)是一致的并且是非傳送中的，那么它就是強一致的，也就是說，局部狀態(tài)集是一致的并且沒有正在傳送中的報文。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

系統(tǒng)的全局狀態(tài)的定義第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

全局狀態(tài)的獲?。煺账惴ǎ杭偃鐔铀惴ǖ倪M程為P，那么它首先記錄自己的局部狀態(tài)，然后它沿著它的輸出通道發(fā)送一個標志(marker)，指示接收者應該參與記錄一個全局狀態(tài)的工作。當接收者Q通過它的輸入通道C收到一個標志，它將依據不同條件執(zhí)行以下不同操作：如果Q還沒有記錄自己的局部狀態(tài)，它首先記錄自己的局部狀態(tài)，并記錄通道C的狀態(tài)為空報文序列，然后也沿著它自己的輸出通道發(fā)送一個標志。如果Q已經記錄了自己的局部狀態(tài)，通過通道C收到的標志用來指示Q應該記錄通道的狀態(tài)。通道的狀態(tài)是Q記錄它的局部狀態(tài)以來到收到這個標志前所收到的報文系列。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

全局狀態(tài)的獲?。煺账惴ǎ喝绻粋€進程已經沿它的每個輸入通道接收到一個標志，并對每個標志進行了處理，就稱它已經完成了它的那部分算法。一個進程的局部狀態(tài)，連同它的所有輸入通道的狀態(tài)將被發(fā)送到這個快照的發(fā)起進程。

第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

全局狀態(tài)的獲?。煺账惴ǎ篜1

P2

P3

C12

C21

C32

C23

C13

C31

P1啟動了快照算法，它同時執(zhí)行三個動作：(a)記錄局部狀態(tài)；(b)發(fā)送一個標志到C12和C13；(c)設置一個計數(shù)器對來自輸入通道C21和C31的報文進行計數(shù)。

第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

全局狀態(tài)的獲取（快照算法）：P1

P2

P3

C12

C21

C32

C23

C13

C31

一旦進程P2從通道C12接收到標志，它也執(zhí)行三個動作：(a)記錄其局部狀態(tài)并記錄通道C12的狀態(tài)為空；(b)發(fā)送一個標志到通道C21和C23；(c)設置一個計數(shù)器對來自輸入通道C32的報文進行計數(shù)。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

全局狀態(tài)的獲?。煺账惴ǎ侯愃频?，進程P3也執(zhí)行三個動作。我們假定從進程P1來的標志比從進程P3來的標志早到達進程P2。一旦從進程P3來的標志到達進程P2，P2就記錄通道C32的狀態(tài)為自設置計數(shù)器以來沿著這個通道接收到的報文的序列。于是進程P2完成了自己的那部分算法，因為它已經從每個輸入通道接收到一個標志并已經記錄了自己的局部狀態(tài)。類似地，進程P3在接收到從P1和P2發(fā)來的標志后，屬于它的那部分算法終止。進程P1在接收到從P2和P3發(fā)來的標志后，屬于它的那部分算法終止。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

一致全局狀態(tài)的充要條件Z字形路徑：一條Z字形路徑存在于進程Pi的檢查點A到進程Pj的檢查點B(Pi和Pj可以是同一個進程)，當且僅當存在報文m1，m2，…，mn(n≥1)滿足：m1是進程Pi在檢查點A之后發(fā)送的；如果ml(1≤l≤n)被進程Pk接收，則ml+1在同一個或后面的檢查點間隔被Pk發(fā)出。注意，ml+1可能在ml被接收之前或之后發(fā)送；mn被進程Pj在檢查點B之前接收。在Z字形路徑中，因果關系路徑中那樣的報文鏈是允許的，另外還允許這樣的報文鏈，即鏈中的任何報文在前一個報文被接收之前發(fā)送，只要發(fā)送和接收在同一個檢查點間隔里即可。

第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

一致全局狀態(tài)的充要條件Z字形路徑實例：從C11到C31的由報文m1和m2組成的路徑是一條Z字形路徑。從C11到C32的由報文m1和m3組成的路徑是一條Z字形路徑，同時也是一條因果關系路徑。檢查點C22形成一條由報文m4和m1組成的Z字形循環(huán)。第五章同步和互斥

5.3系統(tǒng)的全局狀態(tài)

一致全局狀態(tài)的充要條件一致性定理：一個檢查點集S，其中每個檢查點屬于不同的進程，它們屬于同一個一致性的全局狀態(tài)當且僅當S中不存在這樣的檢查點，它有一條到S中任何其他檢查點(包括它自身)的Z字形路徑。推論：檢查點C可以屬于一個一致性全局狀態(tài)當且僅當C不屬于一個Z字形循環(huán)；屬于不同進程的兩個檢查點A和B，它們可以屬于同一個一致性全局狀態(tài)當且僅當沒有包括A或B的Z字形循環(huán)；在A和B之間不存在Z字形路徑。

第五章同步和互斥

5.4互斥算法

互斥問題互斥問題就是定義一些基本的操作來解決共享資源的多個并發(fā)進程的沖突問題。

互斥算法的主要目標是保證在任一個時刻只能有一個進程訪問臨界區(qū)。一個正確的互斥算法必須避免沖突(死鎖和餓死)和保證公平性。為此，算法應滿足以下三個條件：已獲得資源的進程必須先釋放資源之后，另一個進程才能得到資源；不同的請求應該按照這些請求的產生順序獲得滿足，請求應該按照某種規(guī)則進行排序，例如使用邏輯時鐘確定請求的順序；若獲得資源的每個進程最終都釋放資源，則每個請求最終都能滿足。第五章同步和互斥

5.4互斥算法

互斥問題衡量互斥算法性能的參數(shù)：

完成一次互斥操作所需的報文數(shù)目；同步延遲，即從一個進程離開臨界區(qū)之后到下一個進程進入臨界區(qū)之前的時間間隔；響應時間，即從一個進程發(fā)出請求到該進程離開該臨界區(qū)之間的時間間隔。第五章同步和互斥

5.4互斥算法

集中式互斥算法第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法

Lamport時間戳互斥算法由以下5條規(guī)則組成：一個進程Pi如果為了申請資源，它向其它各個進程發(fā)送具有時間戳Tm:Pi的申請資源的報文，并把此報文也放到自己的申請隊列中；一個進程Pj如果收到具有時間戳Tm:Pi的申請資源的報文，它把此報文放到自己的申請隊列中，并將向Pi發(fā)送一個帶有時間戳的承認報文。如果Pj正在臨界區(qū)或正在發(fā)送自己的申請報文，則此承認報文要等到Pj從臨界區(qū)中退出之后或Pj發(fā)送完自己的申請報文之后再發(fā)送，否則立即發(fā)送；一個進程Pi如果想釋放資源，它先從自己的申請隊列中刪除對應的Tm:Pi申請報文，并向所有其他進程發(fā)送具有時間戳的Pi釋放資源的報文；

第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法

Lamport時間戳互斥算法由以下5條規(guī)則組成：一個進程Pj如果收到Pi釋放資源的報文，它從自己的申請隊列中刪除Tm:Pi申請報文；當滿足下述兩個條件時，申請資源的進程Pi獲得資源：Pi的申請隊列中有Tm:Pi申請報文，并且根據時間戳它排在所有其它進程發(fā)來的申請報文前面；Pi收到所有其它進程的承認報文，其上面的時間戳值大于Tm。第五章同步和互斥

5.4互斥算法

Lamport時間戳互斥算法(實際上3個，P168-170)Lamport時間戳互斥算法實例：第五章同步和互斥

5.4互斥算法

Ricart-Agrawala互斥算法

一個進程申請資源時向所有其他進程發(fā)出申請報文；其它進程收到申請報文后若不在臨界區(qū)并且自己未申請進入臨界區(qū)，或者自己雖然發(fā)出了申請報文，但自己的報文排在收到的申請報文之后，則回答表示同意；申請資源的進程僅在收到所有進程的回答報文后才進入臨界區(qū)使用資源；一個進程使用完資源后，它向所有未給回答的其它申請發(fā)送回答報文。第五章同步和互斥

5.4互斥算法

Ricart-Agrawala互斥算法

Ricart-Agrawala互斥算法實例：第五章同步和互斥

5.4互斥算法

Maekawa互斥算法

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

5.4互斥算法

Maekawa互斥算法

請求子集的例子：考慮一個七個進程的例子，每個進程的請求子集如下：R1：{P1，P3，P4}；R2：{P2，P4，P5}；R3：{P3，P5，P6}；R4：{P4，P6，P7}；R5：{P5，P7，P1}；R6：{P6，P1，P2}；R7：{P7，P2，P3}。第五章同步和互斥

5.4互斥算法

Maekawa互斥算法

Maekawa算法的兩個極端情況：(1)退化為集中式互斥算法。Pc(c∈{1，2，…，n})作為協(xié)調者，對所有進程Pi，有：Ri：{Pc}，1≤i≤n(2)完全分布式的互斥算法。對所有進程Pi，有：Ri：{P1，P2，…，Pn}，1≤i≤n第五章同步和互斥

5.4互斥算法

簡單令牌環(huán)互斥算法

在有n個進程的系統(tǒng)中，將這n個進程組成一個首尾相連的邏輯環(huán)。每個進程在環(huán)中有一個指定的位置，位置可以按網絡地址進行排列，當然也可以采用任何其他可行的方式排列，但每個進程必須知道在環(huán)中哪個進程是它后面的進程。一個進程擁有令牌時就可以進入臨界區(qū)，令牌可在所有的進程間傳遞。如果得到令牌的進程不打算進入臨界區(qū)，它只是簡單地將令牌傳送給它后面的進程。第五章同步和互斥

5.4互斥算法

簡單令牌環(huán)互斥算法

問題：如果令牌丟失，需要重新產生一個令牌，但檢測令牌是否丟失是比較困難的。另外一個問題是進程的崩潰，但進程的崩潰比較容易檢測。這個算法在高負載的情況下工作得很好。然而，它在輕負載的情況下工作得很差，出現(xiàn)很多不必要的報文傳遞。

第五章同步和互斥

5.4互斥算法

Ricart-Agrawala令牌環(huán)互斥算法

初始時，令牌被賦予給任何一個進程。請求進入臨界區(qū)的進程Pj不知道哪個進程擁有令牌，所以它向所有其它進程發(fā)送一個帶時間戳的請求報文，請求得到令牌。每個進程有一個請求隊列記錄有所有進程的請求，令牌中記錄有每個進程最后一個持有令牌的時間。如果當前擁有令牌的進程Pi不再需要令牌，它就按照i+1，i+2，…，n，1，2，…，i-1的順序尋找第一個符合條件的進程Pj，并將令牌傳遞給進程Pj。說明：雖然該算法不是按照每個請求的時間順序來滿足的，但是，由于令牌是按一個方向繞環(huán)傳遞的，所以不會有餓死現(xiàn)象發(fā)生。

第五章同步和互斥

5.4互斥算法

基于時間戳的令牌互斥算法

每個進程保持一張進程狀態(tài)表，記錄它所知的進程狀態(tài)，進程狀態(tài)包括該進程是否為請求進程，以及得到該狀態(tài)的時間。令牌是一個特殊的報文，該報文中包含了發(fā)送該令牌的進程的進程狀態(tài)表。初始化時，每個進程的狀態(tài)表中各個進程均為非請求狀態(tài)，時鐘值為0，并任意指定一個進程為令牌的持有者。請求時，一個進程請求進入臨界區(qū)時，如果它持有令牌，它不發(fā)送任何請求報文，將自己的進程狀態(tài)表中相應于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時鐘值，直接進入臨界區(qū)。如果它不持有令牌，則它向所有其它進程發(fā)送帶有時間戳的請求報文。發(fā)出請求報文后，將自己的進程狀態(tài)表中相應于自己一欄的狀態(tài)改為請求態(tài)，并記錄該狀態(tài)的時鐘值。第五章同步和互斥

5.4互斥算法

基于時間戳的令牌互斥算法

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

5.4互斥算法

基于時間戳的令牌互斥算法

收到令牌時，收到令牌的進程把隨令牌傳來的進程狀態(tài)表和自己的進程狀態(tài)表進行比較。若隨令牌傳來的進程狀態(tài)表中某進程的時間戳大于自己的進程狀態(tài)表中相應進程的時間戳，則將自己的進程狀態(tài)表中相應進程的狀態(tài)和時間戳該成隨令牌傳來的進程狀態(tài)表中相應的狀態(tài)和時間戳。說明：同Ricart-Agrawala令牌環(huán)互斥算法相比，具有更強的公平性，因為它是基于請