高級操作系統(tǒng)

1、2022-4-101高級操作系統(tǒng)Advanced Operating System熊 焰Y0551_3600689中國科學(xué)技術(shù)大學(xué)計算機系2022-4-102第二章 分布式系統(tǒng)同步n分布式系統(tǒng)時鐘同步n分布式互斥n分布式選舉算法n分布式系統(tǒng)死鎖2022-4-1032.1分布式系統(tǒng)時鐘同步在分布式系統(tǒng)中：n進程之間的通信：采用消息傳遞(Message-passing)，而不是通過共享存儲器進行通信的。n與進程通信密切相關(guān)的問題：進程之間是如何彼此協(xié)作和同步的。 例如，分布式系統(tǒng)中臨界區(qū)是如何實現(xiàn)的以及資源是如何分配的？在單機系統(tǒng)中，臨界區(qū)、互斥和同步一般都是采用信號燈和管程等方法來解決的。這些方

2、法卻并不能很好地應(yīng)用于分布式系統(tǒng)，其原因是這些方法都是建立在共享存儲器2022-4-1042.1分布式系統(tǒng)時鐘同步 基礎(chǔ)上的。兩個采用信號燈進行交互的進程必須能夠訪問到這個信號燈。如果這兩個進程是運行在同一臺機器上，那么它們只要將信號燈存放在機器的內(nèi)核中，就可以共享到這個信號燈。但是，如果它們運行在不同的機器上，則共享信號燈的方法再也無效了。因此，需要一些新的方法來解決分布式系統(tǒng)中進程間交互的問題。 在這一章我們將討論分布式系統(tǒng)中與進程間協(xié)作和同步有關(guān)的問題。首先，我們引入時間的度量，因為時間在分布式同步中起著重要的作用，其次,介紹分布式互斥和選舉算法;最后,討論分布式系統(tǒng)的死鎖。 2022-

3、4-1052.1分布式系統(tǒng)時鐘同步 分布式系統(tǒng)中的同步比單機系統(tǒng)中的同步要復(fù)雜的多,原因是前者必須使用分布式算法。在分布式系統(tǒng)中,由某一個機器收集整個系統(tǒng)的所有信息,然后,讓這個進程考察這些信息并作出一個決定通常是不大可能的,也不是人們所希望的。因此,分布式算法應(yīng)具有下列特性: 1.相關(guān)的信息是分布在多個機器上的。 2.進程根據(jù)局部信息來作出決定。 3.對系統(tǒng)中任一個機器的失敗應(yīng)能容錯。 4.不存在公共時鐘或其它全局時間源。 2022-4-1062.1分布式系統(tǒng)時鐘同步 前三點表明由一個機器收集所有的信息進行處理是不可能的。例如,在資源分配時,將所有請求發(fā)送給一個管理者進程,由它根據(jù)表中的信息

4、來考察所有的請求并決定資源的分配。這在分布式系統(tǒng)中必將造成某一個進程負(fù)擔(dān)過重。此外,一個分布式系統(tǒng)應(yīng)該比單機系統(tǒng)更可靠。如果一個機器崩潰了,其余的機器應(yīng)能繼續(xù)工作,而不至于使系統(tǒng)癱瘓。第四點也是非常重要的。在單機系統(tǒng)中,時間是確定的。如果一個進程想要知道時間,則它可以調(diào)用一個系統(tǒng)調(diào)用由內(nèi)核告訴它當(dāng)前的時間值。如果一個進程先得到時間值而另一個進程后得到時間值,那么,先得到的時間值一定比后得到的時間值小，然而,在分布式系統(tǒng)中,所有機器要在時間上達到一致是非常困難的。 2022-4-1072.1分布式系統(tǒng)時鐘同步 首先,我們看一看在分布式系統(tǒng)中缺乏全局時間所產(chǎn)生的影響?？疾霼nixUnix中的mak

5、emake程序。通常,一個大程序分成多個源文件。這樣,對其中某一個文件的修改只需要對被修改的這個文件進行重編譯,而無須對所有的源文件進行編譯。當(dāng)調(diào)用makemake程序時，MakeMake程序考察所有源文件和對應(yīng)目標(biāo)文件的修改時間。如果源文件input.cinput.c的修改時間為2155且對應(yīng)目標(biāo)文件input.oinput.o的修改時間為2151,那么,makemake程序知道input.cinput.c已被修改。input.cinput.c必須被重新編譯。如果output.coutput.c的修改時間為2144且對應(yīng)目標(biāo)文件outpuoutpu t.ot.o的修改時間為2145,則不需要

6、對output.coutput.c進行重新編譯。MakeMake程序在考察完所有源文件和其對應(yīng)目2022-4-1082.1分布式系統(tǒng)時鐘同步 標(biāo)文件的修改時間后決定那些文件需要重新編譯并調(diào)用編譯器對其進行編譯。在分布式環(huán)境中,由于無法在全局時間上達到一致,所以,情況并非這樣簡單。假定output.ooutput.o的修改時間為2144,在這以后,outpuoutpu- - t.ct.c被修改并被賦予的時間為2143,原因是output.coutput.c所在機器上的時鐘要比output.ooutput.o所在機器上的時鐘慢。所以,makemake程序不調(diào)用編譯器進行編譯，結(jié)果,最終可執(zhí)行二進制

7、程序?qū)⒑杏尚吕显次募傻哪繕?biāo)文件，導(dǎo)致該可執(zhí)行程序無法運行而程序員卻不知道原因而一直尋找程序代碼的錯誤。因此，在分布式系統(tǒng)中，時鐘同步是非常重要的，也是必不可少的。 2022-4-1092.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 所有計算機上都有一個： 記錄時間的電路-稱之為時鐘-它實際上是一個定時器-一個以某個頻率進行震蕩的石英晶體。 與定時器相關(guān)的兩個寄存器分別稱之為計數(shù)器計數(shù)器和保持寄存器保持寄存器。晶體每震蕩一次,計數(shù)器就減一。當(dāng)計數(shù)器變?yōu)?時,一個中斷產(chǎn)生并將保持寄存器的值重新裝入到計數(shù)器中。 因此,我們可以對定時器進行編程使得定時器每秒鐘中斷60次。每一次中斷稱之為

8、一次時鐘滴答時鐘滴答。 在單機系統(tǒng)中,時鐘快一點或慢一點都無關(guān)緊要,因為單機上的所有進程都使用同一個時鐘。每一個進程所得到的時鐘值在本機內(nèi)是一致的。但是,在分2022-4-10102.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 布式系統(tǒng)中,情況與單機系統(tǒng)完全不同。雖然每一個晶體震蕩器的頻率相當(dāng)穩(wěn)定,但也無法保證不同機器上晶體的震蕩頻率完全相同。實際上,分布式系統(tǒng)中，n個計算機上的時鐘值都不相同。因此,需要一種方法將所有機器上的時鐘進行同步。 LamportLamport在1978年指出時鐘同步是可能的并提出了一個邏輯時鐘同步算法。在1990年,LamportLamport擴展了他的工作。

9、LamportLamport指出時鐘的同步不是絕對的。如果兩個進程并不交互,則它們的時鐘就無須同步。 2022-4-10112.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 原因是時鐘不同步不會產(chǎn)生什么問題。系統(tǒng)中的進程不需要在事件發(fā)生的確切時間上達成一致而只需要在事件發(fā)生的先后順序上達成一致即可。在makemake例子中,makemake只需要知道input.cinput.c是否比input.oinput.o生成的早即可,而無須知道input.cinput.c和input.oinput.o確切的生成時間。在許多應(yīng)用中,只要所有機器都認(rèn)可某一時間就足夠了, 而這個時間無須與收音機每小時廣播

10、的時間相同。例如,盡管現(xiàn)在真正的時間是10:02,但只要所有機器都認(rèn)為現(xiàn)在是10:00,我們說系統(tǒng)的時鐘是同步的。我們把這種并不一定是真正時間但所有機器都一致認(rèn)可的時鐘稱之為邏輯時鐘邏輯時鐘。如果我們2022-4-10122.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 增加一個條件:所有的時鐘不僅一致而且與實際時間之間的誤差不超過某個值。那么,這種時鐘我們稱之為物理時鐘物理時鐘。 為了將邏輯時鐘進行同步,LamportLamport定義了一種稱之為在之前發(fā)生在之前發(fā)生的關(guān)系。表達式ab讀做”a在b之前發(fā)生”。它表示所有的進程都認(rèn)為事件a先發(fā)生,而事件b后發(fā)生。ab存在于下列兩種情況: 1

11、.如果a和b都是同一個進程中的兩個事件且a在b之前發(fā)生,則ab為真。 2.如果a是一個進程發(fā)送一個消息的事件且b是另一個進程接收該消息的事件,則ab為真。 2022-4-10132.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 在之前發(fā)送在之前發(fā)送是一個傳遞關(guān)系,如果ab且bc,則ac。如果兩個事件x和y分別發(fā)生在兩個不同的進程內(nèi)且x和y不是同一個消息的發(fā)送和接收事件,則xy不為真, yx亦不為真。我們將這兩個事件稱之為是并發(fā)事件并發(fā)事件。 度量時間的方法：對于每一個事件a,我們給a分配一個所有進程都認(rèn)可的時間值C(a)。這種時間值必須具有一個特性:如果ab,則C(a)C(b)。時鐘時間C

12、是一直向前走的(即增加)，不會向后退(即減少)。時間的修改只能增加而不能減少。 2022-4-10142.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 例如，圖圖2-12-1（a a）中有三個進程。每一個進程都運行在不同的機器上且每一個機器都有一個自己的時鐘以各自的速度走時。當(dāng)進程0中的時鐘滴答6次時，進程1滴答8次，而進程3滴答10次。每一個時鐘的走時速度是恒定的。在時間為6時,進程0發(fā)送了一個消息A給進程1。進程1在時間為16時收到了消息。如果消息中含有消息開始發(fā)送的時間值6,則進程1認(rèn)為該消息的傳輸花費了10次滴答。同理,消息B從進程1傳輸?shù)竭M程2花費了16次滴答。但是,由進程2發(fā)給

13、進程1的消息C在發(fā)送時的時間值為60而在接收時的時間值為56。這樣,消息C的傳輸時間為負(fù)值。 2022-4-10152.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 0 1 2 0 1 2 0 0 0 0 0 0 6 A 8 10 6 A 8 10 12 16 20 12 16 20 18 24 B 30 18 24 B 30 24 32 40 24 32 40 30 40 50 30 40 50 36 48 C 60 36 48 C 60 42 56 70 42 61 70 48 D 64 80 48 D 69 80 54 72 90 70 77 90 60 80 100 76 85 1

14、00 (a) (b) 圖圖2-1.2-1. (a)三個進程,每一個進程都有自己的時鐘。三個時鐘都以不同的速度走時。 (b)LamportLamport修改時鐘算法。 2022-4-10162.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法LamportLamport解決這個問題的算法：每一個消息都含有一個發(fā)送者時鐘的發(fā)送時間,當(dāng)消息到達時,接收者將自己時鐘的接收時間與發(fā)送時間相比較。如果接收時間小于等于發(fā)送時間,則接收者的時鐘被修改成發(fā)送時間加1。如果接收時間大于發(fā)送時間,則不改變接收者的時鐘。 因此,消息C到達進程1的時間改為61,消息D到達進程0的時間改為70(見圖圖2-1(b)2-1(

15、b)。LamportLamport算法還必須滿足一個要求：任意兩個事件的時間之差至少為1。如果一個進程連續(xù)發(fā)送或接收兩個消息,則這兩個消息的時間之差也至少為1。 我們對不同進程內(nèi)兩個同時發(fā)生的事件是這樣賦時間值的:2022-4-10172.1分布式系統(tǒng)時鐘同步2.1.1 邏輯時鐘同步算法 事件發(fā)生的時間值與該事件所屬進程的進程號連接起來,中間用.加以分隔。例如,進程1和進程2中兩個事件恰好同時在時間為40時發(fā)生。進程1中的事件發(fā)生時間為40.1而進程2中的事件發(fā)生時間為40.2。 由此我們可以對系統(tǒng)中所有事件按如下方法賦時間值: 1.在同一進程中,如果事件a在事件b之前發(fā)生,則 C(a)C(b

16、)。 2.如果a和b分別是一個消息的發(fā)送和接收事件,則 C(a)1時,時鐘太快。當(dāng)dC/dt1時,時鐘太慢。只有dC/dt=1時,時鐘不快不慢。 2022-4-10202.1分布式系統(tǒng)時鐘同步2.1.2 物理時鐘同步算法 如果兩個時鐘朝著UTCUTC兩個相反的方向漂移,則在它們同步后的t時刻,它們之間的相差為2t。如果 操作系統(tǒng)的設(shè)計者要保證任意兩個時鐘相差不超過，則時鐘必須每/2秒同步一次。Cristian算法： 假定：有一臺機器擁有一個WWWWWW接收器。我們稱這臺機器為時間服務(wù)器。 算法：每一臺機器周期地(周期低于/2秒)向時間服務(wù)器發(fā)送一個消息請求獲得當(dāng)前標(biāo)準(zhǔn)時間。時間服2022-4-

17、10212.1分布式系統(tǒng)時鐘同步2.1.2 物理時鐘同步算法 務(wù)器盡可能快地將一個含有當(dāng)前時間CUTC的消息回送給發(fā)送請求的機器。發(fā)送機器收到回答消息后,就將自己的時鐘調(diào)到CUTC。 大問題：由于發(fā)送機器的時間不得向后調(diào),所以,當(dāng)發(fā)送機器的時間比標(biāo)準(zhǔn)時間CUTC快,則將產(chǎn)生嚴(yán)重問題。一個解決辦法是:假定定時器每秒鐘中斷100次,則每一次中斷將引起時間增加10ms。當(dāng)時間快時,則每一次中斷時間將增加9ms。同樣,當(dāng)時間慢時,則每一次中斷時間將增加11ms。這個過程一直持續(xù)到時間正確為止。 小問題：服務(wù)器的回答消息在路途上花費了一定的延2022-4-10222.1分布式系統(tǒng)時鐘同步2.1.2 物理

18、時鐘同步算法 遲。這個延遲將隨著網(wǎng)絡(luò)負(fù)載的變化而變化。 一個解決方法：發(fā)送機器精確地記錄從發(fā)送請求到收到回答這段時間。開始發(fā)送時間T0和收到回答時間T1（均用發(fā)送機器的時鐘來度量）。假定時間服務(wù)器處理請求消息和中斷所花費的時間為I。那么,回答消息的延遲為(T1- T0-I)/2。如果請求消息和回答消息所走的路徑不同,則回答消息的延遲將不能除以2。此外,當(dāng)網(wǎng)絡(luò)擁擠或不可靠時, T1- T0將異常的大。所以,當(dāng)T1- T0超過某個閥值,則將其丟棄。 2022-4-10232.1分布式系統(tǒng)時鐘同步2.1.2 物理時鐘同步算法Berkeley算法： 在CristianCristian算法中,時間服務(wù)器

19、是被動的而且需要一個WWWWWW接收器。而在BerkeleyBerkeley算法中,時間服務(wù)器是主動的且無須一個WWWWWW接收器。 算法：時間服務(wù)器周期地輪詢每一個機器當(dāng)前的時間。收到所有機器當(dāng)前時間后,計算其平均值。然后,將該平均值發(fā)送給每一個機器。每一個機器都將自己的時鐘調(diào)到這個平均值。但是時間服務(wù)器的時鐘必須由操作員周期地手工調(diào)整。更為精確的做法是每一個機器還將這個平均值+服務(wù)器到每一個機器的延遲。 2022-4-10242.1分布式系統(tǒng)時鐘同步2.1.2 物理時鐘同步算法平均算法： 上面兩個算法都是集中式物理時鐘同步算法?，F(xiàn)在我們介紹一種非集中式物理時鐘同步算法。算法的基本思想:將時

20、間劃分成固定長度的再同步間隔。ith 間隔從T0+iR時刻開始到T0+(i+1)R時刻結(jié)束,其中,T0是過去認(rèn)可的一個時刻,R是一個系統(tǒng)參數(shù)。在每一個間隔的開始,每一個機器都廣播自己時鐘當(dāng)前的時間值。由于不同機器上時鐘的速度不相同,所以,這些廣播不會恰好同時進行。每一個機器廣播自己的時間后,它就啟動自己的定時器來收集在第S間隔內(nèi)其它機器發(fā)來的時間值。當(dāng)所有機器含有時間值的廣播到2022-4-10252.1分布式系統(tǒng)時鐘同步2.1.2 物理時鐘同步算法 達后,它計算所有時間值的平均值并將自己時鐘調(diào)整到這個平均值。一種改進的方法：先去掉m個最大值和m個最小值。然后,在計算所剩時間值的平均值。其目的

21、是為了消除某些機器時鐘的損壞所造成的時鐘值過大和過小的異常情況。提高時間值的正確性。該算法還可以考慮每一個廣播消息的延遲。消息延遲可以通過已知網(wǎng)絡(luò)拓?fù)浠蛘咛讲煜⒎祷氐臅r間來獲得。 2022-4-10262.2分布式互斥2.2.1 一個集中式互斥算法 在具有多個進程的系統(tǒng)中,當(dāng)一個進程要讀或者修改某個共享數(shù)據(jù)結(jié)構(gòu)時,它就必須首先進入一個臨界區(qū)取得互斥權(quán)來確保其它進程不能同時使用該共享數(shù)據(jù)結(jié)構(gòu)。在單機系統(tǒng)中,臨界區(qū)是采用信號燈和管程來保護共享數(shù)據(jù)結(jié)構(gòu)。本節(jié)將討論分布式系統(tǒng)中的臨界區(qū)和互斥是如何實現(xiàn)的。 分布式系統(tǒng)中最直接的互斥方法就是模擬單機系統(tǒng)中的集中式互斥算法。集中式互斥算法：我們選擇一個進

22、程作為協(xié)調(diào)器(例如,在具有最高網(wǎng)絡(luò)地址機器上運行的進程)。當(dāng)進程1要進入臨界區(qū)時,它發(fā)送一個請求消息給協(xié)調(diào)器,告訴協(xié)2022-4-10272.2分布式互斥2.2.1 一個集中式互斥算法 調(diào)器它要進入哪一個臨界區(qū)并申請訪問權(quán)。如果當(dāng)前沒有一個進程在所申請的臨界區(qū)內(nèi),則協(xié)調(diào)器回送一個允許訪問的回答消息給申請進程。當(dāng)回答消息到達時,申請進程1進入臨界區(qū)。假定此時進程2也要求進入同一個臨界區(qū)。由于進程1已在臨界區(qū)內(nèi),所以,協(xié)調(diào)器不回送回答消息給等待回答消息的進程2。然后,暫時將進程2的申請進行排隊,進程2阻塞。當(dāng)進程1退出臨界區(qū)時,它就發(fā)送一個釋放互斥訪問的消息給協(xié)調(diào)器。協(xié)調(diào)器從請求隊列中取出第一個申

23、請,然后,回送一個允許訪問的回答消息給發(fā)送該申請的進程(即進程2)。解除該申請進程的阻塞并進入臨界區(qū)。算法的過程見圖圖2-22-2。 2022-4-10282.2分布式互斥2.2.1 一個集中式互斥算法 0 1 2 0 1 2 0 1 2 請求 OK 請求 不回答 釋放 OK C 請求隊列為空 C C 協(xié)調(diào)器 圖圖2-2 2-2 (a)進程1向協(xié)調(diào)器請求進入臨界區(qū)并獲得允許。 (b)進程2向協(xié)調(diào)器請求進入同一個臨界區(qū),協(xié)調(diào)器不回答。 (c)當(dāng)進程1退出臨界區(qū)時,告訴協(xié)調(diào)器,由協(xié)調(diào)器發(fā)送回答給進程2，進 程2進入臨界區(qū) 22022-4-10292.2分布式互斥2.2.2 一個分布式互斥算法 19

24、78年，LamportLamport提出了第一個分布式互斥算法。1981年RicartRicart和AgrawalaAgrawala使得該算法更加有效。RicartRicart和AgrawalaAgrawala算法的要求:系統(tǒng)中的所有事件都是順序的。也就是說,任意兩個事件發(fā)生的順序是明確的。LamportLamport的邏輯時鐘為分布式互斥提供了郵戳。 RicartRicart和AgrawalaAgrawala算法:當(dāng)一個進程要進入一個臨界區(qū)時,它就建立一個消息。該消息含有要進入的臨界區(qū)名字、自己的進程號以及當(dāng)前時間。然后,將該消息發(fā)送給所有其它進程。假定消息的發(fā)送是可靠的。這里,我們也可以使

25、用可靠的組通信來廣播該消息。當(dāng)一個進程收到另一個進程發(fā)來的一個請求消息時,2022-4-10302.2分布式互斥2.2.2 一個分布式互斥算法 它根據(jù)消息中指定臨界區(qū)的狀態(tài)采取相應(yīng)的措施。我們將其分成下列三種情況:1.如果接收者不在指定的臨界區(qū)內(nèi)且又不想進入該臨 界區(qū),則它回送一個OK消息給發(fā)送者。2.如果接收者已在指定的臨界區(qū)內(nèi),則不回答而將請求排隊。3.如果接收者要進入指定臨界區(qū)但還未進入，則它將 接收的請求消息中郵戳和它發(fā)送的請求消息中的郵 戳進行比較。若前者的郵戳比后者的郵戳小，則接 收者回送一個OK消息給發(fā)送者。若后者的郵戳比前2022-4-10312.2分布式互斥2.2.2 一個分

26、布式互斥算法 者的郵戳小，則接收者將收到的請求排隊。 一個進程在發(fā)送完請求消息后就一直等待所有進程回送的OK消息。只要所有的OK消息都到達，則它就可以進入指定的臨界區(qū)。當(dāng)該進程離開臨界區(qū)時，它就發(fā)送一個OK消息給所有在本進程內(nèi)排隊要進入同一個臨界區(qū)的進程并將這些進程的請求從隊列中移去。 圖圖2-32-3的例子:假定進程0和進程2都要同時進入同一個臨界區(qū)。進程0給每一個進程發(fā)送一個其郵戳為8的請求。同時，進程2也給每一個進程發(fā)送一個其郵戳為12的請求。由于進程1不要進入臨界區(qū)，所以，它分別給進程0和進程2發(fā)送OK消息。進程0和進程2都發(fā)2022-4-10322.2分布式互斥2.2.2 一個分布式

27、互斥算法 現(xiàn)沖突并比較郵戳。因為進程0請求消息中的郵戳8比進程2請求消息中的郵戳12小,因此,進程2發(fā)送一個OK消息給進程0,進程0將進程2的請求排隊并進入臨界區(qū)。當(dāng)進程0離開臨界區(qū)時,它將進程2的請求從隊列中移去并發(fā)送一個OK消息給進程2允許進程2進入臨界區(qū)。 2022-4-10332.2分布式互斥2.2.2 一個分布式互斥算法 進入臨界區(qū) 0 8 0 0 8 8 12 OK OK OK 1 2 12 1 2 1 2 12 OK 圖圖2-32-3 (a)兩個進程要同時進入同一臨界區(qū)。 (b)進程0的郵戳小,所以,先進入臨界區(qū)。 (c)當(dāng)進程0結(jié)束訪問臨界區(qū)時,它發(fā)送一個OK消息,因此,進 程

28、2可以進入臨界區(qū)。 2022-4-10342.2分布式互斥2.2.2 一個分布式互斥算法 RicartRicart和AgrawalaAgrawala算法和集中式算法一樣,既無死鎖又無餓死也無單點失敗。每一次進入臨界區(qū)要求發(fā)送2(n-1)個消息,其中,n為系統(tǒng)中進程總數(shù)。但是,一個進程崩潰將不響應(yīng)所有的請求。解決的方法:當(dāng)一個請求到達時,接收者或者回送一個允許訪問消息或者回送一個不允許訪問消息。每當(dāng)一個請求或回答丟失時,發(fā)送者超時表明目的進程已崩潰。一個請求被拒絕后,發(fā)送者應(yīng)該阻塞,等待以后發(fā)來的OK消息。同集中式算法相比,本算法的缺點是速度慢、復(fù)雜以及代價高。 2022-4-10352.2分布式互斥2.2.3 一個令牌環(huán)算法 令牌環(huán)算法是一個完全不同的分布式互斥算法。一個總線網(wǎng)絡(luò)中的進程沒有任何順序(見圖圖2-4(a