分布式操作系統(tǒng)

1、2.3 命名服務(wù),2.3.1 概述（名字、屬性、名字服務(wù)系統(tǒng)、名字服務(wù)的要求） 2.3.2 一般的命名方式 2.3.3 分布式系統(tǒng)中的命名方式 2.3.4 名字服務(wù)器的設(shè)計,2.3命名服務(wù)2.3.1概述,在一個分布式系統(tǒng)中，名字可用于指稱或索引各種類型的資源，包括計算機、 服務(wù)、端口、個體對象以及用戶。 分布式系統(tǒng)中資源的共享與通信需要名字； 用戶(客戶) 請求計算機操作諸多資源中的某特定的對象時需要使用名字； 進程之間不能共享由計算機系統(tǒng)管理的資源，除非它們能協(xié)調(diào)一致地對資源進行命名； 用戶之間也不能通過分布式系統(tǒng)相互通信，除非他們能對其他用戶進行命名,一、名字與屬性,名字，統(tǒng)稱為名稱(na

2、me) 人們可讀的文本名，便于人們識別和記憶 系統(tǒng)標(biāo)識符，軟件用來對資源進行解釋和存儲的名字形式，是一個定長的位串 下面是幾種名稱： 物理網(wǎng)址和邏輯網(wǎng)址：這類名稱可視為名字的位置或地址 端口、進程和組標(biāo)識符：這類名稱可視為消息的目的地 資源標(biāo)識符：由服務(wù)器和內(nèi)核管理的資源的低層獨立定位的標(biāo)識符 文件：使用人們可讀的文本名字進行存取的信息集,一、名字與屬性（續(xù),客戶用文本名對資源的操作過程(Amoeda) 存取一個資源涉及到將其文件名映射成對應(yīng)的資源標(biāo)識符， 再將該資源標(biāo)識符映射成一個端口標(biāo)識符和一個特定服務(wù)的標(biāo)識符； 然后將這個端口標(biāo)識符映射成一個網(wǎng)絡(luò)地址，將這個特定服務(wù)的標(biāo)識符映射到相關(guān)服務(wù)

3、器中的資源,一、名字與屬性（續(xù),分布式系統(tǒng)中使用的許多名稱都是有特定含義的，客戶(用戶或進程) 使用這樣的名稱請求服務(wù)系統(tǒng)對它管轄的命名對象和資源進行操作。 若系統(tǒng)管理很多對象，那么每個對象都得命名，考慮到效率，這個名稱應(yīng)能直接映射它所代表的對象。 例如，當(dāng)要求刪除一個文件時，該文件的名稱就被傳遞給文件服務(wù)系統(tǒng)；請求向一個進程發(fā)信號時，該進程的標(biāo)識符被提供給進程管理系統(tǒng)。 這樣一些名稱僅用在管理這些命名對象的服務(wù)系統(tǒng)的上下文(共享對象除外) 中,一、名字與屬性（續(xù),引用超出任何單一服務(wù)系統(tǒng)范圍的實體時，也要命名。典型例子包括： 用戶(帶有專用名、邏輯名、用戶標(biāo)識符和電子郵件地址等) 計算機(帶

4、有名字宿主名，如mac41) 服務(wù)系統(tǒng)本身(如文件服務(wù)、打印服務(wù)等)。 所有這些名稱必須是有意義的、可讀的 因為用戶和系統(tǒng)管理員需要通過這些名稱訪問分布式系統(tǒng)的主要組件和配置，程序員在編程過程中需要這些名稱去訪問相應(yīng)的服務(wù)(系統(tǒng)) ，用戶借助它們進行通信。 考慮到 Internet 提供的連接能力，這些命名要求在范圍上應(yīng)該是全球的,一、名字與屬性（續(xù),名稱和對象之間的聯(lián)結(jié)稱為聯(lián)編(binding)。 特定服務(wù)名被服務(wù)系統(tǒng)聯(lián)編到相關(guān)對象或資源的實際表示上 用戶名、計算機名和服務(wù)(系統(tǒng))名被聯(lián)編到命名對象的屬性上，所有這些對象都把地址作為屬性之一。 一般而言，屬性值 或是基本值，如整數(shù)； 或是自身

5、的名稱，如 Internet 地址230.1 32.123.112等。 最終，所有的名稱被簡化成基本值或不能再進一步“查找”的基本名。與名稱相關(guān)的屬性不僅對用戶而且對其他服務(wù)都是有用的。 例如，在電子郵件系統(tǒng)中，Internet域名系統(tǒng)(DNS)用來從電子郵件地址中查找郵件主機地址，但由另外的軟件來傳遞和存儲郵件消息,二、名字服務(wù)系統(tǒng),名字服務(wù)系統(tǒng)管理著一個聯(lián)編數(shù)據(jù)庫，其中存儲著文本名(可讀的)及其相關(guān)的屬性。其支持的操作有： 解析一個名字在該數(shù)據(jù)庫中查找給定名字的相關(guān)屬性； 為新名字生成新的聯(lián)編； 刪除聯(lián)編； 列出已聯(lián)編的名字等操作。 注意：雖然把聯(lián)編集看作一個數(shù)據(jù)庫，但一般說來名字不是簡單

6、鍵，常常由若干部分組成(例如，)，這些部分需在數(shù)據(jù)庫的不同區(qū)域中分別查找，這些不同區(qū)域即上下文 (context,二、名字服務(wù)系統(tǒng)（續(xù),名字管理從其他服務(wù)中獨立出來的原因： 很大程度上是因為分布式系統(tǒng)的開放性； 一致性 (unification) ：讓不同的服務(wù)器或服務(wù)系統(tǒng)管理的資源出現(xiàn)在同一命名方案中似乎比較方便的。 例如在UNlX中的NFS中，一些文件在本地磁盤上管理，而另一些則在遠(yuǎn)程服務(wù)器上，所有的文件出現(xiàn)在單一的名字空間層次結(jié)構(gòu)中。此外，一些“文件”的名字涉及到本地設(shè)備或命名過的管道。,二、名字服務(wù)系統(tǒng)（續(xù),集成(integration)：在分布式系統(tǒng)中，不一定總能預(yù)測共享的范圍。有時

7、候，需要共享和命名在不同管理域中創(chuàng)建的資源，這可能會引起問題， 例如，合并兩個用戶集，分配給每個用戶的登錄名可能會發(fā)生沖突。更壞的情況是，這兩組用戶可能有完全不同的命名規(guī)則,三、名字服務(wù)的一般要求,名字服務(wù)越來越復(fù)雜。 幾個例子： Grapevine：最早的可擴充多域名字服務(wù)系統(tǒng)之一 Global Name Service：DEC系統(tǒng)研究中心開發(fā)的全球名字服務(wù)，是 Grapevine的下一代，目標(biāo)為： 處理任意數(shù)量的名字并為任意數(shù)量的管理組織服務(wù)：例如，該系統(tǒng)應(yīng)能處理世界上所有計算機用戶的E-mail地址,三、名字服務(wù)的一般要求（續(xù),長生命期：在其生命期中，名字空間的組織和實現(xiàn)名字服務(wù)的一些組

8、件將會發(fā)生許多變化。 高可靠性：絕大多數(shù)服務(wù)系統(tǒng)依賴于名字服務(wù)系統(tǒng)，一旦它崩潰了，其他服務(wù)系統(tǒng)就無法工作。 故障隔離：局部故障不會導(dǎo)致整個名字服務(wù)系統(tǒng)失效。 容忍懷疑：在一個較大的開放系統(tǒng)中，不存在所有客戶都信賴的組件。 DNS：Internet域命名系統(tǒng)(DNS)使用得非常廣泛，它命名Internet上的對象(用戶和計算機,2.3.2一般的命名方式,在計算機系統(tǒng)中，每個對象一般有兩個名字： 由用戶識別的文本名(符號名) 由系統(tǒng)使用的內(nèi)部名 內(nèi)部名可以是該對象的實際位置， 也可以是查詢該對象的地址的一種表示形式。 通過某種映射，系統(tǒng)可把用戶定義的符號名轉(zhuǎn)換成相應(yīng)的內(nèi)部名。 名字和對象之間的關(guān)系

9、： 同一對象可能有多個名字； 同一名字也可用來代表不同的對象(在不同的作用域內(nèi),2.3.2一般的命名方式（續(xù),A、B各有三個文件，其目錄包含了每個文件的文件名及指向?qū)?yīng)文件在磁盤上地址的指針。 這里，相同的文件名可用來指稱不同的文件。例如，兩個目錄中都含有s. pas，但它卻代表兩個不同的文件。 不同的文件名也可以指稱同一個文件。例如，A目錄中的test.dat和B 目錄中的old.dat兩者的指針都指向“文件1,2.3.2一般的命名方式（續(xù),由于系統(tǒng)可以有多個用戶，因此，目錄常常組織成層次結(jié)構(gòu) 。 文件名的含義： 不僅指文件名本身 而且也應(yīng)包括它與根之間所有目錄的名字(路徑名)。 一個例子：

10、tset.dat文件的 完全路徑名是root: A:test.dat,2.3.2一般的命名方式（續(xù),大多數(shù)系統(tǒng)允許用戶設(shè)置一個默認(rèn)目錄或當(dāng)前目錄，此時用戶不必寫出完全路徑名。 一個例子： 假定A設(shè)置它的默認(rèn)目錄為root:A， 當(dāng)用戶使用文件名my.c時，操作系統(tǒng) 就自動地把默認(rèn)目錄名作為 my.c的前綴，形成完全路 徑名root: A: my. c,2.3.3分布式系統(tǒng)中的命名方式,分布式系統(tǒng)中的命名更復(fù)雜： 由于分布式環(huán)境中的名字可用來指稱不同場點或不同場點的不同層次結(jié)構(gòu)上的對象，因此與單機系統(tǒng)相比，其命名和名字的映射工作更加復(fù)雜。 以下討論分布式環(huán)境下的 名字管理器的主要功能 命名方案

11、標(biāo)識符和字符串名,一、名字管理器的主要功能,DOS中名字管理部分的功能： 通過管理名字在系統(tǒng)的地址去定位命名過的對象； 創(chuàng)建、刪除、改變對象的名字； 改變對象的位置，以支持對象在系統(tǒng)中的遷移； 利用對象名字來支持對象的共享； 創(chuàng)建一個對象組；,一、名字管理器的主要功能（續(xù),從組中刪除成員或?qū)⒊蓡T加入其中； 枚舉組中的成員； 測試組中成員之間的關(guān)系； 借助組名共享資源或共享服務(wù)程序； 支持對象組的遞歸結(jié)構(gòu)； 完成外部名(符號名)到內(nèi)部名(系統(tǒng)名) 的映射工作,二、分布式系統(tǒng)中的命名方案,分布式系統(tǒng)中常用的命名方案有絕對命名、相對命名和層次式命名三種。 由絕對命名方案命名的名字是全系統(tǒng)范圍唯一的、

12、無二義性的。在機內(nèi)，這類名字通常是由時鐘或計數(shù)器之值產(chǎn)生的位串。 由相對命名方案命名的名字依賴于使用它的上下文。對于不同的使用者，一個對象的名字可以是不同的，或者說，一個對象的名字不唯一,二、分布式系統(tǒng)中的命名方案（續(xù),層次式命名方案用如下方式組織系統(tǒng)中的對象名： 對象被分劃成若干組； 每組給定全局唯一的組名； 每組中的每個對象在組內(nèi)給定唯一的名字； 一個組中對象名還可按此方式進一步分劃成若干子組,二、分布式系統(tǒng)中的命名方案-實例1,VMS的命名體系：層次式，完全路徑名由一個設(shè)備名接任何個數(shù)的目錄名再接文件名和擴展文件名構(gòu)成。 圖2-22展示了VMS中兩個設(shè)備 Userdisk 和Sysdis

13、k的目錄結(jié)構(gòu)。 Userdisk有兩個目錄dirl和dir2。文件letter.dom 的完全路徑名是Userdisk: dir2.me letter.dom,二、分布式系統(tǒng)中的命名方案-實例2,DEC網(wǎng)命名方式：把類似VMS的命名體系再向上擴充一層，使之包含場點名，如圖2-23所示。 遠(yuǎn)程場點上的文件可通過把該場點名加在相應(yīng)文件的路徑名之首來進行訪問。 例如，在sitel上的文件letter.dom的完全路徑名現(xiàn)在為sitel:userdisk:dir2. meletter.dom,二、分布式系統(tǒng)中的命名方案-實例2（續(xù),DEC網(wǎng)命名方案中，場點名必須唯一，且每個場點必須知道系統(tǒng)中所有其他場

14、點的名字。這種方案容易實現(xiàn)，用戶也比較容易掌握。但存在下面的問題： 由于文件的位置事實上已作為文件名的一部分，那么當(dāng)一文件從一場點遷移到另一場點時，意味著該文件的名字也必須改變，從而導(dǎo)致凡涉及到訪問該文件名的所有操作也不得不作相應(yīng)的修改。 若一文件有多個副本且位于不同的場點上，它們就會有不同的名字，那么對它們的任何更改都容易導(dǎo)致不一致性。 系統(tǒng)的某些細(xì)節(jié)(如場點) 對用戶是可見的。一般說來，這是分布式系統(tǒng)的設(shè)計者所不希望的,二、分布式系統(tǒng)中的命名方案-設(shè)計原則,設(shè)計命名方案的一個基本觀點：名字是依賴于位置還是獨立于位置。 這也可以說是性能對靈活性的問題。 在不依賴于位置的命名方案中，對象的名字

15、不含其在系統(tǒng)中的位置。這使得可對系統(tǒng)中的遠(yuǎn)程或本地資源(對象)進行一致的存取。 但在依賴于位置的命名方案中，就可能出現(xiàn)像DEC網(wǎng)命名方案的問題。 移動文件要注意改名，后續(xù)操作也要注意名字問題 多副本情況一致性的維護問題 透明性的問題,三、唯一標(biāo)識符和字符串名,UID 系統(tǒng)中的每一對象給定一個唯一的標(biāo)識符(UID)，即在系統(tǒng)中，它唯一地指稱該對象。一個對象的UID 在其整個生命期內(nèi)決不改變。特別，當(dāng)一對象從一場點遷移到另一場點時其UID 仍保持不變。 一個UID是相關(guān)對象的絕對名字，它通常是利用系統(tǒng)時鐘產(chǎn)生的。 UID 也可作為一種權(quán)限使用，此時，與其相關(guān)的對象是受保護的，它既不能由用戶改變，也

16、不應(yīng)被用戶忘卻。 為了使UID 在全系統(tǒng)范圍內(nèi)唯一，也可以將局部宿主ID作為它的一部分。 此外，它還可含有一些隨機生成的位，使得它難以猜測，從而起到保密作用,三、唯一標(biāo)識符和字符串名（續(xù),字符串名(簡稱串名)具有如下特征： 同一串名可由不同的用戶用來訪問不同的對象； 不同的串名可由(不同的)用戶用來訪問相同的對象； 對象可以在場點間遷移不必改變其串名,三、唯一標(biāo)識符和字符串名（續(xù)）-總結(jié),在大多數(shù)系統(tǒng)中，字符串名主要供用戶使用，而UID僅供操作系統(tǒng)使用。 UID通常是定長、壓縮形式的(一般有64128位)，這就有利于系統(tǒng)級的構(gòu)造、使用和管理； 字符串名一般較長且往往是可變長的(如10-100字

17、節(jié))，這對用戶是方便的，但不太適合在系統(tǒng)級使用。 操作系統(tǒng)提供了從字符串名到UID 的映射,2.3.4名字服務(wù)器的設(shè)計,名字服務(wù)器(name server)的主要功能：將一個符號串名(一個整數(shù)串名或字符串名)映射成系統(tǒng)內(nèi)唯一的物理地址。名字服務(wù)器管理著包含有“名字及其物理地址”的對照表，系統(tǒng)中的所有服務(wù)程序都由名字服務(wù)器來尋址和定位。 例子,2.3.4名字服務(wù)器的設(shè)計（續(xù),劍橋大學(xué)設(shè)計CDCS中的服務(wù)程序族利用其名字服務(wù)器來尋址和定位。 為了引用一個服務(wù)程序，client 將代表某個服務(wù)程序名字的一個ASCII串發(fā)送給名字服務(wù)器，名字服務(wù)器收到這一信息后，就查看該串是否在其管理的表中。若在，它

18、就返回所指服務(wù)程序的所在處理機編號、用于編址它的端口和相應(yīng)的協(xié)議等。 在CDCS中，名字服務(wù)器本身的地址是固定的，系統(tǒng)提供了向名字服務(wù)器管理的表中添加或從中刪除信息的命令。不過，出于保護原因，這類命令只能由系統(tǒng)管理人員使用,2.3.4名字服務(wù)器的設(shè)計（續(xù),設(shè)計名字服務(wù)器一般有中央方式、復(fù)制方式和分劃方式三種途徑。 用中央方式設(shè)計時，全系統(tǒng)僅有一個(中央)名字服務(wù)器，系統(tǒng)中的所有服務(wù)程序都由它來尋址和定位。但由于性能及可靠性方面的原因，這種方式不常采用。 用復(fù)制方式時，每個場點都有一個名字服務(wù)器的副本，用以管理該場點上的所有服務(wù)程序及本場點與其他場點間相互請求的服務(wù)信息,2.3.4名字服務(wù)器的設(shè)

19、計（續(xù),分劃方式意指： 若系統(tǒng)由若干子系統(tǒng)(子網(wǎng))組成，則對于每個子系統(tǒng)，用一個名字服務(wù)器管理本子系統(tǒng)上的所有服務(wù)程序及本子系統(tǒng)與其他子系統(tǒng)相互請求的服務(wù)信息； 或者若系統(tǒng)的名字空間可根據(jù)某種方式來分劃，則對于每個經(jīng)這樣分劃后的實體，用單獨的或復(fù)制式的名字服務(wù)器管理； 或者將名字空間組織成層次結(jié)構(gòu)來管理,2.4 DOS中的同步,分布式系統(tǒng)中的進程通信 消息傳遞（Send、Receive、Replay等原語） RPC 組通信 這并不是分布式系統(tǒng)的全部內(nèi)容。 與此緊密相關(guān)的是進程之間如何協(xié)作及如何彼此同步。 比如說，在分布式系統(tǒng)中臨界區(qū)如何實現(xiàn)，資源如何分配,2.4 DOS中的同步（續(xù),在單CPU

20、系統(tǒng)中，臨界區(qū)、互斥和其它同步問題經(jīng)常使用信號量、管程等方法來解決，這些方法在分布式系統(tǒng)中并不十分適用，因為它們依賴于共享存儲器的存在。 比如，有兩個進程通過使用信號量而相互作用，它們必須都能訪問信號量。 如果它們在同一臺機器上運行，能夠共享內(nèi)核中的信號量，并通過執(zhí)行系統(tǒng)調(diào)用訪問它。 如果它們運行在不同機器上，這種方法就不適用了，而需要其它技術(shù)。 甚至看似簡單的問題，比如判斷事件A在事件B之前還是之后發(fā)生的問題也需要認(rèn)真考慮,2.4 DOS中的同步（續(xù),2.4 分布式操作系統(tǒng)中的同步 2.4.1 時鐘同步 問題提出 邏輯時鐘與事件定序 時間戳 時鐘同步算法 2.4.2 互斥 集中式算法、分布式

21、算法、令牌環(huán)算法、選舉算法,2.4.1 時鐘同步,集中式系統(tǒng)的同步算法：在某地收集系統(tǒng)的所有有關(guān)信息，然后讓某個進程分析并做出決定。 在DOS中的分布式算法有如下性質(zhì)： 相關(guān)信息分散在多臺機器中； 進程決策僅僅依賴于本地信息； 系統(tǒng)中單點故障應(yīng)該避免； 沒有公用時鐘或其它精確的全局時間資源存在。 前三點都說明在一處收集所有信息并對它進行處理是不可接受的。 比如，資源分配（以一種無死鎖的的方式分配）向單一的管理進程發(fā)送所有I/O請求，由它來檢查它們，根據(jù)表中的信息準(zhǔn)予或拒絕請求是不實際的。在大系統(tǒng)中，這種解決方法會給某個進程帶來太重的負(fù)擔(dān),2.4.1 時鐘同步,進一步而言，一個單點故障會造成系統(tǒng)

22、不可靠。最理想的情況是，一個分布式系統(tǒng)應(yīng)該比單機系統(tǒng)更可靠，一臺機器崩潰不影響其它機器的繼續(xù)運行，不通過集中而獲得同步所使用的方法應(yīng)該與傳統(tǒng)操作系統(tǒng)所用的方法不同。 上述的最后一點是十分關(guān)鍵的，在集中式系統(tǒng)中時間的概念很清楚，當(dāng)進程想知道時間時，它使用系統(tǒng)調(diào)用，由內(nèi)核提供。 如果進程A詢問時間，之后進程B也詢問時間，B得到的時間值就應(yīng)該大于或等于A所得到的時間值，但一定不會小于A得到的時間值。 在分布式系統(tǒng)中，獲得時間上的一致是并不容易,一個簡單的例子：在缺少全局時間時的UNIX下的make程序-DOS中很難獲得時間上的一致,UNIX系統(tǒng)中一個大程序通?？杀环指畛啥鄠€源文件，如果某個源文件發(fā)生

23、變化，只需將該文件重新編譯即可，而不需要對所有的文件進行重編譯。 Make程序所使用的方法： 當(dāng)編程者修改完所有的源文件，他啟動make程序，看一下源文件和目標(biāo)文件最后一次修改的時間，如果源文件INPUT.C時間為2151，而相應(yīng)的目標(biāo)文件INPUT.O時間為2150，make就知道INPUT.C在INPUT.O創(chuàng)建后被改動過。因此，INPUT.C必須重新編譯。相反，若INPUT.C時間為2144，而INPUT.O時間為2145，就不必再重編譯了。make檢查所有的源文件并找出哪一個需要重編譯，調(diào)用編譯器重新編譯它,一個簡單的例子：在缺少全局時間時的UNIX下的make程序-DOS中很難獲得時

24、間上的一致（續(xù),在沒有統(tǒng)一時間的分布式系統(tǒng)中：假設(shè)OUTPUT.O的時間為2144，緊隨其后OUTPUT.C被修改，但是由于它所在機器上的時鐘略慢，造成OUTPUT.C時間為2143，如圖2-24所示。make將不再調(diào)用編譯器，最終可執(zhí)行的二進制程序?qū)ㄓ衫系脑次募托碌脑次募a(chǎn)生的混合目標(biāo)文件，這樣可能將不能再正常執(zhí)行,一、問題提出,所有的計算機都有一個計時電路（計時器），通常是由一個精確的石英晶體制成，當(dāng)其在張力限度內(nèi)時，石英晶體以一定的頻率振蕩。 與每個晶體相關(guān)的是兩個寄存器、一個計數(shù)器和一個保持寄存器。每次振蕩時使計數(shù)器減1，當(dāng)計數(shù)器減為0時，產(chǎn)生一次中斷，計數(shù)器重新從保持寄存器中

25、裝入起始值，通過這種方法可以編程使得一個計時器每秒能產(chǎn)生60次中斷或以其它希望的頻率產(chǎn)生中斷成為可能，每次中斷稱作一個時鐘點（clock tick）。 當(dāng)系統(tǒng)剛啟動時，總是要求操作者輸入日期和時間，然后將它們轉(zhuǎn)換成某一已知起始時間后的時鐘值，并將它存儲在存儲器中，在每個時鐘點時，中斷服務(wù)程序?qū)⒋酥导?，用這種方法進行（軟）時鐘計時,一、問題提出（續(xù),在單機單時鐘中，如果時鐘被瞬間關(guān)閉其問題不會太大，因為這臺機器上所有進程使用同一時鐘，它們?nèi)詫?nèi)在地保持一致。 比如，文件INPUT.C時間為2151，文件INPUT.O時間為2150，make將重新編譯源文件，假設(shè)時鐘關(guān)閉的時間為2，真正的時間則

26、分別為2153和2152，有用的只是相對時間,一、問題提出（續(xù),多CPU系統(tǒng)中，每個CPU將擁有自己的時鐘，情況發(fā)生變化。盡管每個晶體振蕩頻率總是相當(dāng)穩(wěn)定，但保證不同計算機上的晶體以完全相同的頻率振蕩是不太現(xiàn)實的。 實際上，當(dāng)系統(tǒng)有N臺計算機時，所有N個晶體將以略微不同的速度振蕩，導(dǎo)致（軟）時鐘逐漸不同步，當(dāng)同時讀這些時鐘時，也會得到不同的值。這種在時間值上的不同稱作時鐘偏移（clock skew）。 一個程序期望與文件、目標(biāo)文件、進程或消息相聯(lián)系的時間應(yīng)是正確的，且與產(chǎn)生它們的機器（即使用哪個時鐘）無關(guān),一、問題提出（續(xù),問題：同步所有時鐘產(chǎn)生一個單一的、無二義的時間標(biāo)準(zhǔn)是否可能。 解決：L

27、amport（1978）闡明了時鐘同步是可能的，并且描述了實現(xiàn)的算法，他還繼續(xù)對這個問題進行了一些研究（Lamport 1990,二、邏輯時鐘與事件定序,Lamport的觀點： 時鐘同步不需要絕對同步。如果兩個進程無相互作用，它們的時鐘無須同步，因為即使缺少同步也覺察不出來，不會產(chǎn)生什么問題。 通常并不必需所有進程在時間上完全一致，而是它們在事件發(fā)生的順序要上完全一致。 在上述make程序的例子中，計時目的在于說明INPUT.C比INPUT.O早或晚產(chǎn)生，而并不是它們各自產(chǎn)生的絕對時間,二、邏輯時鐘與事件定序（續(xù),如有特殊限制，不僅時鐘要完全一致，而且不能與真實時間有一點點的誤差，這種時鐘稱作

28、物理時鐘(physical clocks)， 本節(jié)將討論Lamport算法，它用邏輯時鐘進行同步,二、邏輯時鐘與事件定序（續(xù),Lamport 為同步邏輯時鐘定義了“先發(fā)生”關(guān)系：表達式AB讀做“A在B之前發(fā)生”，意思是所有進程認(rèn)為先發(fā)生事件A，接著發(fā)生事件B，這種關(guān)系有如下兩種情況： 如果A和B是在同一進程中的兩個事件，且A發(fā)生在B之前，則AB為真。 如果A是一個進程發(fā)送消息的事件，B為另一個進程接收這一消息的事件，則AB為真，消息不能在發(fā)送之前接收，也不能在發(fā)送的同時接收，因為傳送過程還需要一定時間。 先發(fā)生是一個傳遞關(guān)系，即，若AB且BC則AC。 “先發(fā)生”也稱為前趨關(guān)系（happen-b

29、efore relation） 如果兩個事件X和Y，出現(xiàn)在不同進程中，但并不交換消息（甚至不由第三方間接交換），則XY為假，YX也為假。則事件X和Y稱為并發(fā)事件，即它們之間不存在誰先誰后的問題,二、邏輯時鐘與事件定序（續(xù),水平方向表示空間(不同的進程)，垂直方向表示時間。設(shè)A、B為任意兩個事件，當(dāng)且僅當(dāng)在圖中不存在從A到B或從B到A的一條路徑時，事件A 與事件B 是并發(fā)的。 一些存在前趨關(guān)系的事件是：p1q2，r0q4 ，q3rl，p1q4。 并發(fā)事件是： q0和p2，r0和q3，r0和p3，q3和p3。 無法知道兩個并發(fā)事件(例如q0和p2) 哪一個先發(fā)生。既然這兩個事件沒有一個影響另一個，

30、因此哪一個先發(fā)生并不重要,三、時間戳,需要一種測量時間的方法，使得對每一事件a，在所有進程中都認(rèn)可給它分配一個時間值C(a），即打上時間戳，這些時間值必須有如下性質(zhì)： 若AB則C(A)C(B)。 若a和b是同一進程中的兩個事件，且ab，則C(a)C(b) 同理，若a是一個進程發(fā)送消息的事件，b為另一個進程接收消息的事件，那么C(a)C(b)。 時鐘時間值C必須向前走（遞增），不能倒退（減少）。校正時間的操作是給時間加上一個正值，而不是減一個正數(shù),三、時間戳Lamport算法怎么給事件分配時間,各進程運行在不同的機器上，每個機器都有自己的時鐘，以各自不同的速率工作。進程0的時鐘滴答（tick）了

31、6下時，進程1的時鐘滴答了8下，進程2的時鐘滴答了10下。 在時刻6，進程0把A消息發(fā)送到進程1，消息到達的時間取決于你信任哪一個時鐘，不管怎樣，當(dāng)它到達時，進程1讀到的時刻是16，若消息自身攜帶的起始時刻是6，進程1會推算到它需滴答10下才到達，這個值是可能的。依次類推，消息B從進程1到進程2需要滴答16下這也是可能的。 問題：消息C從進程2到進程1是在60時刻離開，56時刻到達。同理，消息D從進程1到進程0是在64時刻離開，54時刻到達，這是絕對不可能出現(xiàn)的，必須防止這種情況的出現(xiàn),三、時間戳Lamport算法怎么給事件分配時間（續(xù),Lamport的解決方案：直接使用先發(fā)生關(guān)系，因為C在6

32、0時刻離開，它只能在61時刻或更晚時刻到達 所以每條消息都攜帶發(fā)送者的時鐘以指出其發(fā)送的時刻，當(dāng)消息到達時，接收者時鐘若比消息發(fā)送時鐘小，就立即將自己的時鐘調(diào)到比發(fā)送時間大1或更多的值。 在圖b中，C現(xiàn)在到達的時間是61。同樣D到達的時間是70,三、時間戳Lamport算法怎么給事件分配時間（續(xù),為適應(yīng)全局統(tǒng)一時間的需要，只需對此作一點補充即可，即在每兩個事件之間，時鐘必須至少滴答一下，如果一個進程以相當(dāng)快的速度連續(xù)發(fā)送或接收兩條消息，它必須在這中間至少滴答一下。 在某些情況下需要一個附加條件：兩個事件不會精確地同時發(fā)生，為了實現(xiàn)這個目標(biāo)，我們可以將事件所在的進程號附加在事件發(fā)生時間的低位，并

33、用小數(shù)點分開。這樣，如果在進程1和進程2中同時發(fā)生了2個事件，發(fā)生時刻都是40，則前者記為40.1，后者記為40.2,三、時間戳-Lamport算法怎么給事件分配時間（續(xù),使用這種方法，分布式系統(tǒng)中將時間分配給所有事件的方法遵照如下規(guī)則： 若在同一進程中a發(fā)生在b之前，則C(a)C(b)； 若a和b分別代表發(fā)送消息和接收消息，則C(a)C(b)； 對所有事件a和b，C(a)C(b) 這個算法給我們提供了對系統(tǒng)中所有的事件進行排序的一種方法，許多其它的分布式算法也需要這種排序以避免混亂,四、時鐘同步算法,所有算法都有相同的系統(tǒng)基礎(chǔ)模型： 每臺機器上假設(shè)都有一個每秒產(chǎn)生H次中斷的計時器。當(dāng)時間到時

34、，中斷處理程序?qū)④洉r鐘加1，軟時鐘記錄從過去某一約定值開始的中斷次數(shù)。我們把這個時鐘值記為C。 更特殊的，當(dāng)UTC時間為t時，在機器p上的時間值是Cp(t)， 最完美的情況是對所有的p和t，有Cp(t)=t，換言之，dC/dt理想值為1。 UTC：世界協(xié)調(diào)時間(Universal Time Coordinated)。 GPS 系統(tǒng)中有兩種時間區(qū)分，一為UTC，另一為LT（地方時）。兩者的區(qū)別為時區(qū)不同，UTC就是0時區(qū)的時間，地方時為本地時間,四、時鐘同步算法（續(xù),真正計時器并不是每秒精確的中斷H次，理論上當(dāng)H=60時，計時器每小時應(yīng)該產(chǎn)生216,000個滴答。 實際上，用現(xiàn)代計時時鐘芯片可以

35、獲得相關(guān)的延遲是10-5，意味著一臺機器每小時可以獲得 215,998216,002范圍的滴答，若存在某一常數(shù)，便有,四、時鐘同步算法（續(xù),計時器可以在它規(guī)定的范圍內(nèi)工作，制造商標(biāo)明的常數(shù)是最大漂移速度。稍慢的、精確的、稍快的時鐘如圖2-27所示,四、時鐘同步算法（續(xù),若兩個時鐘相對于UTC時間以相反方向漂移，在它們同步后的t時間內(nèi)，它們可能的差值為2t，若操作系統(tǒng)的設(shè)計者要保證每兩個時鐘之間的相差不超過，時鐘必須至少在每/(2)秒內(nèi)再同步一次（用軟件方法），不同算法實現(xiàn)再同步的方法不同,1.Cristian算法,非常適合于只有一臺機器上有WWV接收器，其它所有機器與它同步的系統(tǒng)。 把擁有WW

36、V接受器的那臺機器稱作時間服務(wù)器，算法是基于Cristian(1989)和以前的一些工作。 每臺機器以小于或等于/(2)秒的周期定期地向時間服務(wù)器發(fā)送消息詢問當(dāng)前的時間，時間服務(wù)器接到消息后就盡快回答含有當(dāng)前時間CUTC值的消息，如圖2-28所示,1.Cristian算法（續(xù),當(dāng)發(fā)送者得到回答后，就將它的時鐘設(shè)為CUTC，但是這種算法有兩個問題： 第一個重要的問題是時間決不能倒退，若發(fā)送者的時鐘快，CUTC將會比發(fā)送者的時間值C小，若把發(fā)送者的時間值直接改成CUTC會導(dǎo)致嚴(yán)重的錯誤，比如在時鐘變化后，編譯產(chǎn)生的目標(biāo)文件的時間早于時鐘變化前源文件的修改時間。 這種變化必須逐步進行，一種方法是假設(shè)

37、將計時器設(shè)置為每秒產(chǎn)生100次中斷，通常，每次中斷將時間加10毫秒，當(dāng)時鐘需要慢下來時，中斷服務(wù)程序每次僅加9毫秒，直到調(diào)整好為止。同樣時鐘要加快時，每次中斷服務(wù)程序?qū)r鐘加11毫秒，而不是立即把時間調(diào)到所需要的值,1.Cristian算法（續(xù),另一個小問題是從時間服務(wù)器端發(fā)送的應(yīng)答到發(fā)送者要花費時間，這種延遲可能較大，而且隨著網(wǎng)絡(luò)負(fù)荷的改變而改變。 Cristian的處理方法是試圖測量這個延遲值。 最簡單的方法：發(fā)送者精確地記錄從向時間服務(wù)器發(fā)送請求到接收到應(yīng)答的時間間隔，假設(shè)起始時間是T0與結(jié)束時間T1，他們都是通過同一個時鐘來測量的，就算發(fā)送者的時鐘與UTC有一定的差值，它所測得的時間間

38、隔還是較精確的。在沒有其它任何信息時，消息傳送時間的最佳估計值是（T1-T0）/2，當(dāng)應(yīng)答消息到達時，消息中的時間值再加上此值就得到了當(dāng)前時間服務(wù)器的時間估計值，如果理論上知道了最小的傳送時間，那么與時間估算相關(guān)的其它性質(zhì)也能推算出來,1.Cristian算法（續(xù),如果知道時間服務(wù)器中斷處理的時間和處理消息的時間，這樣的估算還能進一步改進，設(shè)中斷處理的時間是I，那么傳輸時間間隔為T1-T0-I，所以估算單向傳輸時間為它的一半。 系統(tǒng)中確實存在著從A到B的消息和從B到A的消息傳輸路徑不同，因此就有不同的傳輸時間，但我們目前先不考慮這種情況。 為了提高精確度，Cristian建議不要只做一次測量，

39、而做一系列測量，測量中T1-T0超出一定范圍就認(rèn)為是網(wǎng)絡(luò)阻塞，為不可信值。對剩余的測量值取平均值會得到較好的估算值，也就是說，最快返回的消息是最精確的，因為消息遇到阻塞最少，所以它最能代表純粹的傳輸時間,2.Berkeley算法,在Berkeley UNIX中采取了完全相反的方法，這里的時間服務(wù)器（實際是時間守護進程）是主動的，它定期地詢問每臺機器的時間。然后基于這些回答，計算出平均值并告訴所有的機器將它們的時鐘撥快或撥慢到一個新的值。這種方法適合于沒有WWV接收器的系統(tǒng)，時間守護進程的時間必須由操作者定期地手工設(shè)置，這種方法如圖2-29所示,2.Berkeley算法（續(xù),a),時間守護進程在

40、3:00把它的時間告訴其它機器，并且詢問它們各自的時間 (b)，各機器將它們各自的時間與時間守護進程時間的差值告訴時間守護進程， (c)守護進程計算出它們的平均值，通知各機器如何調(diào)整各自的時間,3.平均值算法,上述兩種方法都高度集中的，有不足之處。存在一些非集中式算法，如： 一種分布式時鐘同步算法： 它是將時間劃分成固定長度的再同步間隔，第i次間隔開始于T0+iR，而結(jié)束于 T0+(i+1)R，這里的T0是過去某一約定的時間，R是一個系統(tǒng)參數(shù)。 在每次間隔的開始處，每臺機器根據(jù)自己的時鐘廣播發(fā)送當(dāng)前的時間，由于在不同機器上的時鐘不可能完全同速工作，這種廣播就不會完全同時發(fā)生,3.平均值算法（續(xù)

41、,在機器廣播發(fā)送時間之后，它啟動本地計時器收集在S時間間隔中到達的其它廣播，當(dāng)所有廣播到達后，執(zhí)行一個算法，得到新的時間值。 僅將這些值取平均值；最簡單 先除去m個最大值和m個最小值，平均其余值。去掉兩端值可認(rèn)為是一種對m個錯誤時鐘發(fā)出毫無意義的時間值的一種自我保護。 給每條消息值加上一個從源到目的地的傳送時間估計值，這種估計值可參考網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或計算試探消息的響應(yīng)時間而得出,4.多個外部時鐘源,對使用UTC進行同步又要求特別精確的系統(tǒng)來說，可給系統(tǒng)安裝如WWV，GEOS或其它UTC源的多接收器來實現(xiàn)的。 時間源自身固有的不精確性以及信號傳送的不定性，最好的操作系統(tǒng)能做的也只是建立一個UTC

42、時間范圍。 一般來說，不同的時間源會產(chǎn)生不同的時間范圍，這種范圍需要機器和它們達成一致,4.多個外部時鐘源（續(xù),為達到一致，每個具有UTC源的處理機定期在每一UTC精確分的開始處廣播其時間范圍，但 沒有處理機會同時獲得時間包， 傳輸和接收延遲依賴于纜線的距離和包必須經(jīng)過的網(wǎng)關(guān)數(shù)，它對于每一對UTC源和處理機之間都不相同。 其它因素，如多臺機器要同時在以太網(wǎng)上傳輸而發(fā)生的碰撞。 更進一步，如一臺處理機忙于處理以前的包，它可能在相當(dāng)長的幾微秒內(nèi)不去理會到來的時間包，從而導(dǎo)致了時間的不確定性,4.多個外部時鐘源（續(xù),解決：Open Software Foundation（開放軟件組織）的分布式計算環(huán)

43、境的處理方法 某個接收器接收到所有時間源的UTC時間范圍后， 首先檢查是否有與其他范圍不相交的UTC范圍。如果有，這些UTC范圍一定是錯誤的，棄而不用。剩余的時間范圍都是準(zhǔn)確的UTC時間所在的范圍； 因此接著就求出這些范圍相交的部分； 最后將相交部分的中點作為準(zhǔn)確的UTC時間，并將內(nèi)部時鐘設(shè)置為該值,4.多個外部時鐘源（續(xù),2.4.2互斥,涉及多個進程的系統(tǒng)使用臨界區(qū)容易編程 當(dāng)一個進程必須讀或修改某些共享數(shù)據(jù)結(jié)構(gòu)時，它首先進入臨界區(qū)獲得互斥鎖，保證沒有其它的進程能同時使用該共享數(shù)據(jù)結(jié)構(gòu)。 在單處理機系統(tǒng)中，使用信號量、管程和一些近似的結(jié)構(gòu)來保護臨界區(qū)。 幾個例子：在分布式系統(tǒng)中臨界區(qū)和互斥是

44、如何實現(xiàn)的,一、集中式算法,在分布式系統(tǒng)中獲得互斥的最直接方法是仿照單處理機系統(tǒng)的方法，選一個進程為協(xié)調(diào)者（比如在最大網(wǎng)絡(luò)地址機器上運行的進程）。無論什么時候進程要進入臨界區(qū)，它將向協(xié)調(diào)者發(fā)送請求消息，說明它想進入哪個臨界區(qū)并希望獲得允許。如果當(dāng)前該臨界區(qū)內(nèi)沒有其它任何進程，協(xié)調(diào)者就發(fā)送允許進入消息，如圖2-30(a)所示。當(dāng)應(yīng)答到達時，請求者就可以進入臨界區(qū),一、集中式算法（續(xù),現(xiàn)在假設(shè)有另一個進程，如圖2-30(b)所示，請求進入同一個臨界區(qū)，協(xié)調(diào)者知道該臨界區(qū)已有一個進程，所以不能同意該請求，最好的辦法是發(fā)出拒絕允許應(yīng)答。而在圖2-30中，協(xié)調(diào)者回避應(yīng)答，這樣就阻塞了進程2，使它等待應(yīng)答

45、。另一方面，協(xié)調(diào)者還可以發(fā)送“拒絕請求”應(yīng)答。兩種方法都會把進程2放入等待隊列，等待臨界區(qū)的釋放,一、集中式算法（續(xù),當(dāng)進程1從臨界區(qū)退出時，它向協(xié)調(diào)者發(fā)送釋放互斥消息訪問，如圖2-30(c)所示，協(xié)調(diào)者從推遲請求隊列中取出最前面的進程，向它發(fā)送允許進入消息。如果該進程仍然阻塞（即，這是第一條發(fā)給它的允許進入消息）它去除阻塞且進入臨界區(qū)；如果明確發(fā)送一消息拒絕它進入臨界區(qū)，此進程應(yīng)該不時地查詢輸入的消息，或者接著將它阻塞等待許可響應(yīng)。不管怎么樣，當(dāng)它發(fā)現(xiàn)允許進入時，它就可以進入臨界區(qū),一、集中式算法（續(xù),優(yōu)點： 算法保證了互斥的實現(xiàn)，協(xié)調(diào)者僅能讓某一進程在某一時刻進入臨界區(qū)。 也很公平，因為允

46、許請求的順序同它們接收的順序一致，沒有進程永遠(yuǎn)等待（沒有饑餓）。 容易實現(xiàn)，每用一次臨界區(qū)只需3條消息（請求，允許，釋放），它不僅能管理臨界區(qū)，也可用于更普遍的資源分配。 缺點： 協(xié)調(diào)者是一個單點故障，如它崩潰，整個系統(tǒng)將癱瘓，如果進程在請求之后被阻塞，以上這兩種情況都沒有消息返回，請求者不能從“拒絕請求”中辨認(rèn)出協(xié)調(diào)者已崩潰。 此外，大系統(tǒng)中單協(xié)調(diào)者會成為執(zhí)行的瓶頸,二、分布式算法,分布式互斥算法，第一次出現(xiàn)的是在1978年Lamport關(guān)于時鐘同步的論文中，后來Ricart 和Agrawale對它作了進一步的改進， 算法前提：Ricart 和Agrawale算法要求系統(tǒng)中所有事件都是全序的

47、。也就是說，對任何事件組如消息，哪個先發(fā)生必須無歧異。 算法： 當(dāng)一個進程想進入臨界區(qū)時，它要建立一個包括它要進入的臨界區(qū)的名字、處理機號和當(dāng)前時間的消息， 然后將消息發(fā)送給所有其它進程。概念上講也包括發(fā)送給它自身。發(fā)送的消息假設(shè)是可靠的，即每條消息都應(yīng)該被確認(rèn)，如可能應(yīng)使用可靠的組通信，避免使用單個的消息通信,二、分布式算法（續(xù),當(dāng)一個進程接收另一個進程請求消息時，根據(jù)接收方的狀態(tài)以及臨界區(qū)的名字。有三種情況要加以區(qū)別： 若接收者不在臨界區(qū)中，也不想進入臨界區(qū)，它就向發(fā)送者發(fā)送OK消息。 若接收者已經(jīng)在臨界區(qū)中，它就不必回答，而是負(fù)責(zé)對請求隊列排隊。 若接收者要進入臨界區(qū)，但是還沒有進入時，

48、它要將發(fā)來的消息和它發(fā)送給其余進程的時間戳對比，取小的那個，如果來的消息的時戳小，接收者發(fā)送OK消息，如果接收者本身的時間戳更小，那么接收者負(fù)責(zé)排列請求隊列而不發(fā)送任何消息,二、分布式算法（續(xù),在發(fā)送完允許進入臨界區(qū)的請求后，進程將不做任何事，僅等待所有的允許消息，一旦得到允許，它就進入臨界區(qū)，它從臨界區(qū)退出時，向隊列中的所有的進程發(fā)送OK消息，并把它從隊列中刪除,二、分布式算法（續(xù),分析：如果沒有沖突，則正常工作。但是，假設(shè)兩個進程要同時試圖進入一個臨界區(qū)，如圖2-31(a)所示,二、分布式算法（續(xù),進程0發(fā)出時戳為8的請求，而同時進程2發(fā)出時間戳為12的請求。進程1不想進入臨界區(qū)，所以它向

49、2個發(fā)送者發(fā)回OK。進程0和2同時發(fā)現(xiàn)沖突，比較時間戳，進程2發(fā)現(xiàn)自己的大，它只好同意進程0進入臨界區(qū)，向0發(fā)送OK，進程0就把進程2的請求排在隊列中，為以后處理用，自己進入臨界區(qū)，如圖2-31(b)所示,二、分布式算法（續(xù),當(dāng)進程0結(jié)束退出臨界區(qū)時，它把進程2的請求從隊列中取出，并向進程2發(fā)送OK，允許進程2進入臨界區(qū)，如圖2-31(c)所示。 算法之所以能夠使用，因為在產(chǎn)生請求沖突時，遵守按時間戳排序，小時戳優(yōu)先的規(guī)則,二、分布式算法（續(xù),注意：如果進程2比進程0早發(fā)送消息，進程0在它請求進入臨界區(qū)之前獲得了進程2的請求消息，它允許進程2進入臨界區(qū)，當(dāng)進程2接收到進程0的請求時，它發(fā)現(xiàn)自己

50、已經(jīng)在臨界區(qū)了，所以把進程0排在等待隊列中,二、分布式算法（續(xù),問題： 互斥必須無死鎖或無饑餓。 每次進入臨界區(qū)需要2(n-1)條消息，這里n為系統(tǒng)中的進程數(shù)目。最好的是不存在單點故障。 若有一個進程崩潰，它就不能回答請求，這種不發(fā)言將被解釋為不允許進入臨界區(qū)，這樣就阻止了任何試圖進入臨界區(qū)的進程。 因為n個進程之一失效的可能性是單協(xié)調(diào)者失效的n倍，我們必須設(shè)法換一種n倍復(fù)雜和需要更多啟動網(wǎng)絡(luò)通信的算法,二、分布式算法（續(xù),修補：當(dāng)請求到達時，不管它是許可還是拒絕，接收者都要發(fā)送應(yīng)答，一旦請求或應(yīng)答消息丟失，發(fā)送者的等待時間到，它繼續(xù)發(fā)送直到得到應(yīng)答或者認(rèn)為目的進程已經(jīng)崩潰為止。在收到拒絕應(yīng)答

51、后，發(fā)送者應(yīng)該阻塞等待直到獲得OK消息。 另一個問題： 要么組間通信必須使用原語， 要么每個進程必須維持一張組成員表，包括進入組進程、離開組進程和崩潰進程。這種方法最適用于小的從不改變成員的進程組。 集中式算法中，處理所有請求會產(chǎn)生瓶頸的問題；在分布式算法中，所有進程都要參與決定是否進入臨界區(qū)，若一個進程不能處理消息，那么強迫所有進程并行完成同一件事并不能改善整體的性能,二、分布式算法（續(xù),對該算法有一點小的改進 不需獲得每個進程允許后方可進入臨界區(qū)，只要防止任何兩個進程同時進入同一個臨界區(qū)即可， 算法可改成：當(dāng)一個進程從大多數(shù)進程那里獲得允許而并不需要所有進程都允許時，它就可以進入臨界區(qū)。

52、這種算法中，一個進程在批準(zhǔn)另一個進程進入臨界區(qū)之后，在這個進程退出臨界區(qū)之前，它不能再允許其它進程進入該臨界區(qū)。 總之，這種算法還是比原來集中式算法慢，復(fù)雜，昂貴，而且不健壯,三、令牌環(huán)算法,如圖a所示的總線網(wǎng)，進程沒有固定次序。用軟件的方法，構(gòu)造出一個邏輯環(huán)，環(huán)中每個進程都有一個位置，如圖b所示。 進程在環(huán)上的位置可以用網(wǎng)絡(luò)地址的數(shù)字序號指定，也可以用其它方法指定。排序的方法并不重要，重要的是每個進程都要知道誰在它的下一個位置,三、令牌環(huán)算法（續(xù),算法思想： 令牌環(huán)被初始化后，進程0首先獲得令牌。 這樣，令牌開始繞環(huán)運動，它從進程K傳遞到進程K+1（以點到點的方式傳遞）。 當(dāng)進程從它的前一個

53、鄰居手中得到令牌時，檢查它所試圖進入的臨界區(qū)，如果該臨界區(qū)是空的，則該進程可以進入臨界區(qū)，做它要做的工作，然后離開臨界區(qū)。它退出后，將令牌傳遞到它的下一個鄰居，不允許使用同一令牌進入第二個臨界區(qū)。 若一個進程得到了它相鄰進程傳遞來的令牌，但它并不想進入臨界區(qū)，就將該令牌往下傳遞。這樣，如果沒有任何其它的進程想進入臨界區(qū)時，令牌就會高速地沿環(huán)繞行,三、令牌環(huán)算法（續(xù),優(yōu)點： 在任何時刻只有一個進程擁有令牌，所以只有一個進程可以進入臨界區(qū)。 由于令牌以固定順序運動，所以不會出現(xiàn)饑餓進程。 一旦一個進程想進入臨界區(qū)，最不理想的情況是等待所有其它進程進入后再退出臨界區(qū)所用的時間之和,三、令牌環(huán)算法（續(xù)

54、,算法存在的問題： 比如，令牌一旦丟失，它必須重新生成。實際上，檢測令牌丟失是很困難的，因為在網(wǎng)絡(luò)上，令牌兩次出現(xiàn)的時間是不定的，一個小時沒有發(fā)現(xiàn)令牌并不意味著它丟失了，也許某個進程還在使用它。 當(dāng)進程崩潰時，該算法也會出現(xiàn)麻煩，但是恢復(fù)卻容易得多。如果我們需要進程在接收到令牌后發(fā)回確認(rèn)消息，當(dāng)相鄰進程試圖傳遞給它令牌但卻沒有成功時，它就會檢測到死進程。這時就將死進程從進程組中移出。它的下個進程就會從令牌持有者的手中接收到令牌。當(dāng)然，這樣做需要每個進程都能維持當(dāng)前環(huán)設(shè)置情況,四、三種算法的比較,四、三種算法的比較（續(xù),有關(guān)“每次進入需要的消息” 集中式算法最簡單，也最有效的，它在進程進入和退出

55、臨界區(qū)時，只用了3條消息，即請求進入，同意進入和退出時釋放。 分布式算法需要N-1條，（給每個其它進程）請求消息，及另外的N-1條允許消息，總共有 2(N-1)條消息， 對于令牌算法該數(shù)目是可變的，如果每個進程總是想進入一個臨界區(qū)，則令牌的每次傳遞將導(dǎo)致一次進出臨界區(qū)。平均每一次進入臨界區(qū)入口都有一條消息。在其它極限情況下，令牌也許將幾小時幾小時地沿環(huán)傳遞而沒有進程想使用它，在這種情況下，每一次進入臨界區(qū)入出口消息數(shù)是無界的,四、三種算法的比較（續(xù),有關(guān)“延遲” 進程需要進入臨界區(qū)到它能進入臨界區(qū)的延遲也隨著這三種算法而變化： 當(dāng)臨界區(qū)很少被使用時，造成延遲的主要因素是控制進入臨界區(qū)的機制。

56、當(dāng)臨界區(qū)被經(jīng)常使用時，延遲的主要因素是等待其它進程使用的過程。 表2-1表示前一種情況，假設(shè)網(wǎng)絡(luò)在某一時刻只能處理一條消息： 在集中式算法的情況下，進入臨界區(qū)只需要處理2條消息的時間， 在分布式算法的情況下需要2(N-1)條消息， 對令牌環(huán)算法，時間從0（剛接收到令牌）到N-1（釋放令牌）變化,四、三種算法的比較（續(xù),問題： 這三種算法在進程崩潰時都損失慘重，為了避免由于某些崩潰造成的系統(tǒng)癱瘓，必須引入特殊的方法和附加的復(fù)雜性。 更具諷刺意義的是分布式算法比集中式算法對崩潰事件更敏感。這些算法都不能用于容錯系統(tǒng)，但如果崩潰事件很少發(fā)生的話，這些算法都是可以接受的,五、選舉算法,許多分布式算法需

57、要一個進程充當(dāng)協(xié)調(diào)者、發(fā)起者、排序者或其他特定的角色。通常，選擇哪個進程充當(dāng)協(xié)調(diào)者并不重要，重要的是要有進程負(fù)責(zé)。 如果所有進程的地位都相同，沒有特性上的區(qū)別，就無法選擇其中一個為特殊進程，假設(shè)每一個進程有一個特殊的號碼，比如它的網(wǎng)絡(luò)地址，通常選舉算法總是找擁有最大號碼的進程，把它指定為協(xié)調(diào)者，各算法在選舉時有不同的方法。 假設(shè)每個進程都知道所有其它進程的進程號，但不知道目前哪些進程正常，哪些進程不正常。選舉算法的目的是確定選舉何時開始，它在所有進程都同意的基礎(chǔ)上選出協(xié)調(diào)者,五、選舉算法-1.欺負(fù)（Bully）算法1,由Garcia-Molina(1982)提出的 當(dāng)一個進程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)

58、請求時，它就發(fā)起選舉。進程P負(fù)責(zé)選舉如下： P向所有號碼比它大的進程發(fā)送選舉(ELECTION)消息。 若無人響應(yīng)，P獲勝成為協(xié)調(diào)者。 若有號碼比它大的進程響應(yīng)，響應(yīng)者接管，P的工作完成,五、選舉算法-1.欺負(fù)（Bully）算法2,在某一時刻，一個進程只能從號碼比它小的進程那里得到一個選舉（ELECTION）消息，當(dāng)它到達時，接收者就發(fā)送回OK消息，表明它的存在并接管，然后接收者主持選舉（除非它正在主持別的選舉）。除了一個進程外的其余進程都得放棄，這一個進程就是新的協(xié)調(diào)者，它把選舉獲勝的消息發(fā)送給所有進程，告之它是新的協(xié)調(diào)者。 若一個進程剛剛崩潰過，而又得到恢復(fù)，它也有選舉權(quán)，若它剛好是當(dāng)前運

59、行進程中號碼最大的，它就會獲得選舉的勝利，從而接管協(xié)調(diào)者的工作，所以最大的進程總能取勝，故而將該算法命名為欺負(fù)算法,五、選舉算法-1.欺負(fù)（Bully）算法3,五、選舉算法2.環(huán)算法1,基于沒有令牌的環(huán)，假設(shè)所有的進程是按物理或邏輯排序的，每一個進程都知道誰是它的后繼者。 當(dāng)任何一個進程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時，它就構(gòu)造一個包含它自身進程號的選舉消息發(fā)送給它的后繼者，如果后繼者失效，消息將繞過后繼者，到達后繼者的后繼者，或者再下一個，直到找到一個運行進程。每次接收者都把自己的進程號加入到消息表中。 最后，消息到達了始發(fā)者的手中，始發(fā)者接受到包括自己進程號的消息后，將消息的類型轉(zhuǎn)化為協(xié)調(diào)者消息，該消息將再一次繞環(huán)運行，向所有的進程通知誰是協(xié)調(diào)者（在成員表中進程號碼最大的那個）和新的環(huán)成員。當(dāng)消息循環(huán)一周后，被去掉，每個進程都恢復(fù)工作,五、選舉算法2.環(huán)算法2,進程2和進程5同時發(fā)現(xiàn)協(xié)調(diào)者7失效 兩條消息沿環(huán)運動，消息中有完全一樣的成員，相對順序也相同，當(dāng)兩條消息再繞環(huán)一周時，都被去掉。 有多余的消息循環(huán)沒有壞處，最多是浪費了一點帶寬,2.5 原子事務(wù)處理,迄今為止研究的所有同步技術(shù)在其本質(zhì)上來說都是處于底層的，比如信號量。這些技術(shù)需要程序員密切注意互斥、臨界區(qū)管理、死鎖預(yù)防、崩潰恢復(fù)等問題的細(xì)節(jié)。 需要的是更高層次的抽象，也就是隱藏技術(shù)問題，允許程序員將精力集中在算法和進程如何