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

2.3命名服務(wù)

2.3.1概述（名字、屬性、名字服務(wù)系統(tǒng)、名字服務(wù)的要求）2.3.2一般的命名方式2.3.3分布式系統(tǒng)中的命名方式2.3.4名字服務(wù)器的設(shè)計(jì)12.3命名服務(wù)

2.3.1概述（名字、屬性、名字服務(wù)系統(tǒng)2.3命名服務(wù)

2.3.1概述

在一個(gè)分布式系統(tǒng)中，名字可用于指稱或索引各種類型的資源，包括計(jì)算機(jī)、服務(wù)、端口、個(gè)體對(duì)象以及用戶。分布式系統(tǒng)中資源的共享與通信需要名字；用戶(客戶)請(qǐng)求計(jì)算機(jī)操作諸多資源中的某特定的對(duì)象時(shí)需要使用名字；進(jìn)程之間不能共享由計(jì)算機(jī)系統(tǒng)管理的資源，除非它們能協(xié)調(diào)一致地對(duì)資源進(jìn)行命名；用戶之間也不能通過分布式系統(tǒng)相互通信，除非他們能對(duì)其他用戶進(jìn)行命名。22.3命名服務(wù)

2.3.1概述

在一個(gè)分布式系統(tǒng)中，名字可用一、名字與屬性

名字，統(tǒng)稱為名稱(name)人們可讀的文本名，便于人們識(shí)別和記憶系統(tǒng)標(biāo)識(shí)符，軟件用來對(duì)資源進(jìn)行解釋和存儲(chǔ)的名字形式，是一個(gè)定長(zhǎng)的位串下面是幾種名稱：物理網(wǎng)址和邏輯網(wǎng)址：這類名稱可視為名字的位置或地址端口、進(jìn)程和組標(biāo)識(shí)符：這類名稱可視為消息的目的地資源標(biāo)識(shí)符：由服務(wù)器和內(nèi)核管理的資源的低層獨(dú)立定位的標(biāo)識(shí)符文件：使用人們可讀的文本名字進(jìn)行存取的信息集3一、名字與屬性

名字，統(tǒng)稱為名稱(name)3一、名字與屬性（續(xù)）

客戶用文本名對(duì)資源的操作過程(Amoeda)存取一個(gè)資源涉及到將其文件名映射成對(duì)應(yīng)的資源標(biāo)識(shí)符，再將該資源標(biāo)識(shí)符映射成一個(gè)端口標(biāo)識(shí)符和一個(gè)特定服務(wù)的標(biāo)識(shí)符；然后將這個(gè)端口標(biāo)識(shí)符映射成一個(gè)網(wǎng)絡(luò)地址，將這個(gè)特定服務(wù)的標(biāo)識(shí)符映射到相關(guān)服務(wù)器中的資源。4一、名字與屬性（續(xù)）

客戶用文本名對(duì)資源的操作過程(Amoe一、名字與屬性（續(xù)）

分布式系統(tǒng)中使用的許多名稱都是有特定含義的，客戶(用戶或進(jìn)程)使用這樣的名稱請(qǐng)求服務(wù)系統(tǒng)對(duì)它管轄的命名對(duì)象和資源進(jìn)行操作。若系統(tǒng)管理很多對(duì)象，那么每個(gè)對(duì)象都得命名，考慮到效率，這個(gè)名稱應(yīng)能直接映射它所代表的對(duì)象。例如，當(dāng)要求刪除一個(gè)文件時(shí)，該文件的名稱就被傳遞給文件服務(wù)系統(tǒng)；請(qǐng)求向一個(gè)進(jìn)程發(fā)信號(hào)時(shí)，該進(jìn)程的標(biāo)識(shí)符被提供給進(jìn)程管理系統(tǒng)。這樣一些名稱僅用在管理這些命名對(duì)象的服務(wù)系統(tǒng)的上下文(共享對(duì)象除外)中。

5一、名字與屬性（續(xù)）

分布式系統(tǒng)中使用的許多名稱都是有特定一、名字與屬性（續(xù)）

引用超出任何單一服務(wù)系統(tǒng)范圍的實(shí)體時(shí)，也要命名。典型例子包括：用戶(帶有專用名、邏輯名、用戶標(biāo)識(shí)符和電子郵件地址等)計(jì)算機(jī)(帶有名字—宿主名，如mac41)服務(wù)系統(tǒng)本身(如文件服務(wù)、打印服務(wù)等)。所有這些名稱必須是有意義的、可讀的因?yàn)橛脩艉拖到y(tǒng)管理員需要通過這些名稱訪問分布式系統(tǒng)的主要組件和配置，程序員在編程過程中需要這些名稱去訪問相應(yīng)的服務(wù)(系統(tǒng))，用戶借助它們進(jìn)行通信?？紤]到Internet提供的連接能力，這些命名要求在范圍上應(yīng)該是全球的。6一、名字與屬性（續(xù)）

引用超出任何單一服務(wù)系統(tǒng)范圍的實(shí)體時(shí)一、名字與屬性（續(xù)）

名稱和對(duì)象之間的聯(lián)結(jié)稱為聯(lián)編(binding)。特定服務(wù)名被服務(wù)系統(tǒng)聯(lián)編到相關(guān)對(duì)象或資源的實(shí)際表示上用戶名、計(jì)算機(jī)名和服務(wù)(系統(tǒng))名被聯(lián)編到命名對(duì)象的屬性上，所有這些對(duì)象都把地址作為屬性之一。一般而言，屬性值或是基本值，如整數(shù)；或是自身的名稱，如Internet地址12等。最終，所有的名稱被簡(jiǎn)化成基本值或不能再進(jìn)一步“查找”的基本名。與名稱相關(guān)的屬性不僅對(duì)用戶而且對(duì)其他服務(wù)都是有用的。例如，在電子郵件系統(tǒng)中，Internet域名系統(tǒng)(DNS)用來從電子郵件地址中查找郵件主機(jī)地址，但由另外的軟件來傳遞和存儲(chǔ)郵件消息。7一、名字與屬性（續(xù)）

名稱和對(duì)象之間的聯(lián)結(jié)稱為聯(lián)編(bin二、名字服務(wù)系統(tǒng)

名字服務(wù)系統(tǒng)管理著一個(gè)聯(lián)編數(shù)據(jù)庫，其中存儲(chǔ)著文本名(可讀的)及其相關(guān)的屬性。其支持的操作有：解析一個(gè)名字——在該數(shù)據(jù)庫中查找給定名字的相關(guān)屬性；為新名字生成新的聯(lián)編；刪除聯(lián)編；列出已聯(lián)編的名字等操作。注意：雖然把聯(lián)編集看作一個(gè)數(shù)據(jù)庫，但一般說來名字不是簡(jiǎn)單鍵，常常由若干部分組成(例如，he@)，這些部分需在數(shù)據(jù)庫的不同區(qū)域中分別查找，這些不同區(qū)域即上下文(context)。8二、名字服務(wù)系統(tǒng)

名字服務(wù)系統(tǒng)管理著一個(gè)聯(lián)編數(shù)據(jù)庫，其中存儲(chǔ)二、名字服務(wù)系統(tǒng)（續(xù)）

名字管理從其他服務(wù)中獨(dú)立出來的原因：很大程度上是因?yàn)榉植际较到y(tǒng)的開放性；一致性(unification)：讓不同的服務(wù)器或服務(wù)系統(tǒng)管理的資源出現(xiàn)在同一命名方案中似乎比較方便的。例如在UNlX中的NFS中，一些文件在本地磁盤上管理，而另一些則在遠(yuǎn)程服務(wù)器上，所有的文件出現(xiàn)在單一的名字空間層次結(jié)構(gòu)中。此外，一些“文件”的名字涉及到本地設(shè)備或命名過的管道。……9二、名字服務(wù)系統(tǒng)（續(xù)）

名字管理從其他服務(wù)中獨(dú)立出來的原因二、名字服務(wù)系統(tǒng)（續(xù)）

……集成(integration)：在分布式系統(tǒng)中，不一定總能預(yù)測(cè)共享的范圍。有時(shí)候，需要共享和命名在不同管理域中創(chuàng)建的資源，這可能會(huì)引起問題，例如，合并兩個(gè)用戶集，分配給每個(gè)用戶的登錄名可能會(huì)發(fā)生沖突。更壞的情況是，這兩組用戶可能有完全不同的命名規(guī)則。10二、名字服務(wù)系統(tǒng)（續(xù)）

……10三、名字服務(wù)的一般要求

名字服務(wù)越來越復(fù)雜。幾個(gè)例子：Grapevine：最早的可擴(kuò)充多域名字服務(wù)系統(tǒng)之一GlobalNameService：DEC系統(tǒng)研究中心開發(fā)的全球名字服務(wù)，是Grapevine的下一代，目標(biāo)為：處理任意數(shù)量的名字并為任意數(shù)量的管理組織服務(wù)：例如，該系統(tǒng)應(yīng)能處理世界上所有計(jì)算機(jī)用戶的E-mail地址。11三、名字服務(wù)的一般要求

名字服務(wù)越來越復(fù)雜。11三、名字服務(wù)的一般要求（續(xù)）……長(zhǎng)生命期：在其生命期中，名字空間的組織和實(shí)現(xiàn)名字服務(wù)的一些組件將會(huì)發(fā)生許多變化。高可靠性：絕大多數(shù)服務(wù)系統(tǒng)依賴于名字服務(wù)系統(tǒng)，一旦它崩潰了，其他服務(wù)系統(tǒng)就無法工作。故障隔離：局部故障不會(huì)導(dǎo)致整個(gè)名字服務(wù)系統(tǒng)失效。容忍懷疑：在一個(gè)較大的開放系統(tǒng)中，不存在所有客戶都信賴的組件。DNS：Internet域命名系統(tǒng)(DNS)使用得非常廣泛，它命名Internet上的對(duì)象(用戶和計(jì)算機(jī))。12三、名字服務(wù)的一般要求（續(xù)）……122.3.2一般的命名方式

在計(jì)算機(jī)系統(tǒng)中，每個(gè)對(duì)象一般有兩個(gè)名字：由用戶識(shí)別的文本名(符號(hào)名)由系統(tǒng)使用的內(nèi)部名內(nèi)部名可以是該對(duì)象的實(shí)際位置，也可以是查詢?cè)搶?duì)象的地址的一種表示形式。通過某種映射，系統(tǒng)可把用戶定義的符號(hào)名轉(zhuǎn)換成相應(yīng)的內(nèi)部名。名字和對(duì)象之間的關(guān)系：同一對(duì)象可能有多個(gè)名字；同一名字也可用來代表不同的對(duì)象(在不同的作用域內(nèi))132.3.2一般的命名方式

在計(jì)算機(jī)系統(tǒng)中，每個(gè)對(duì)象一般有兩個(gè)2.3.2一般的命名方式（續(xù)）

A、B各有三個(gè)文件，其目錄包含了每個(gè)文件的文件名及指向?qū)?yīng)文件在磁盤上地址的指針。這里，相同的文件名可用來指稱不同的文件。例如，兩個(gè)目錄中都含有s.pas，但它卻代表兩個(gè)不同的文件。不同的文件名也可以指稱同一個(gè)文件。例如，A目錄中的test.dat和B目錄中的old.dat兩者的指針都指向“文件1”。142.3.2一般的命名方式（續(xù)）

A、B各有三個(gè)文件，其目錄包2.3.2一般的命名方式（續(xù)）

由于系統(tǒng)可以有多個(gè)用戶，因此，目錄常常組織成層次結(jié)構(gòu)。文件名的含義：不僅指文件名本身而且也應(yīng)包括它與根之間所有目錄的名字(路徑名)。一個(gè)例子：tset.dat文件的完全路徑名是root:A:test.dat。152.3.2一般的命名方式（續(xù)）

由于系統(tǒng)可以有多個(gè)用戶，因2.3.2一般的命名方式（續(xù)）

大多數(shù)系統(tǒng)允許用戶設(shè)置一個(gè)默認(rèn)目錄或當(dāng)前目錄，此時(shí)用戶不必寫出完全路徑名。一個(gè)例子：假定A設(shè)置它的默認(rèn)目錄為root:A，當(dāng)用戶使用文件名my.c時(shí)，操作系統(tǒng)就自動(dòng)地把默認(rèn)目錄名作為my.c的前綴，形成完全路徑名root:A:my.c。162.3.2一般的命名方式（續(xù)）

大多數(shù)系統(tǒng)允許用戶設(shè)置一個(gè)2.3.3分布式系統(tǒng)中的命名方式

分布式系統(tǒng)中的命名更復(fù)雜：由于分布式環(huán)境中的名字可用來指稱不同場(chǎng)點(diǎn)或不同場(chǎng)點(diǎn)的不同層次結(jié)構(gòu)上的對(duì)象，因此與單機(jī)系統(tǒng)相比，其命名和名字的映射工作更加復(fù)雜。以下討論分布式環(huán)境下的名字管理器的主要功能命名方案標(biāo)識(shí)符和字符串名172.3.3分布式系統(tǒng)中的命名方式

分布式系統(tǒng)中的命名更復(fù)雜：一、名字管理器的主要功能

DOS中名字管理部分的功能：通過管理名字在系統(tǒng)的地址去定位命名過的對(duì)象；創(chuàng)建、刪除、改變對(duì)象的名字；改變對(duì)象的位置，以支持對(duì)象在系統(tǒng)中的遷移；利用對(duì)象名字來支持對(duì)象的共享；創(chuàng)建一個(gè)對(duì)象組；……18一、名字管理器的主要功能

DOS中名字管理部分的功能：18一、名字管理器的主要功能（續(xù)）……從組中刪除成員或?qū)⒊蓡T加入其中；枚舉組中的成員；測(cè)試組中成員之間的關(guān)系；借助組名共享資源或共享服務(wù)程序；支持對(duì)象組的遞歸結(jié)構(gòu)；完成外部名(符號(hào)名)到內(nèi)部名(系統(tǒng)名)的映射工作。19一、名字管理器的主要功能（續(xù)）……19二、分布式系統(tǒng)中的命名方案

分布式系統(tǒng)中常用的命名方案有絕對(duì)命名、相對(duì)命名和層次式命名三種。由絕對(duì)命名方案命名的名字是全系統(tǒng)范圍唯一的、無二義性的。在機(jī)內(nèi)，這類名字通常是由時(shí)鐘或計(jì)數(shù)器之值產(chǎn)生的位串。由相對(duì)命名方案命名的名字依賴于使用它的上下文。對(duì)于不同的使用者，一個(gè)對(duì)象的名字可以是不同的，或者說，一個(gè)對(duì)象的名字不唯一。20二、分布式系統(tǒng)中的命名方案

分布式系統(tǒng)中常用的命名方案有絕對(duì)二、分布式系統(tǒng)中的命名方案（續(xù)）

層次式命名方案用如下方式組織系統(tǒng)中的對(duì)象名：對(duì)象被分劃成若干組；每組給定全局唯一的組名；每組中的每個(gè)對(duì)象在組內(nèi)給定唯一的名字；一個(gè)組中對(duì)象名還可按此方式進(jìn)一步分劃成若干子組。21二、分布式系統(tǒng)中的命名方案（續(xù)）

層次式命名方案用如下方式二、分布式系統(tǒng)中的命名方案-實(shí)例1

VMS的命名體系：層次式，完全路徑名由一個(gè)設(shè)備名接任何個(gè)數(shù)的目錄名再接文件名和擴(kuò)展文件名構(gòu)成。圖2-22展示了VMS中兩個(gè)設(shè)備Userdisk和Sysdisk的目錄結(jié)構(gòu)。Userdisk有兩個(gè)目錄dirl和dir2。文件letter.dom的完全路徑名是Userdisk:[dir2.me]letter.dom.22二、分布式系統(tǒng)中的命名方案-實(shí)例1

VMS的命名體系：層次式二、分布式系統(tǒng)中的命名方案-實(shí)例2

DEC網(wǎng)命名方式：把類似VMS的命名體系再向上擴(kuò)充一層，使之包含場(chǎng)點(diǎn)名，如圖2-23所示。遠(yuǎn)程場(chǎng)點(diǎn)上的文件可通過把該場(chǎng)點(diǎn)名加在相應(yīng)文件的路徑名之首來進(jìn)行訪問。例如，在sitel上的文件letter.dom的完全路徑名現(xiàn)在為sitel::userdisk:[dir2.me]letter.dom.23二、分布式系統(tǒng)中的命名方案-實(shí)例2

DEC網(wǎng)命名方式：把類似二、分布式系統(tǒng)中的命名方案-實(shí)例2（續(xù)）

DEC網(wǎng)命名方案中，場(chǎng)點(diǎn)名必須唯一，且每個(gè)場(chǎng)點(diǎn)必須知道系統(tǒng)中所有其他場(chǎng)點(diǎn)的名字。這種方案容易實(shí)現(xiàn)，用戶也比較容易掌握。但存在下面的問題：由于文件的位置事實(shí)上已作為文件名的一部分，那么當(dāng)一文件從一場(chǎng)點(diǎn)遷移到另一場(chǎng)點(diǎn)時(shí)，意味著該文件的名字也必須改變，從而導(dǎo)致凡涉及到訪問該文件名的所有操作也不得不作相應(yīng)的修改。若一文件有多個(gè)副本且位于不同的場(chǎng)點(diǎn)上，它們就會(huì)有不同的名字，那么對(duì)它們的任何更改都容易導(dǎo)致不一致性。系統(tǒng)的某些細(xì)節(jié)(如場(chǎng)點(diǎn))對(duì)用戶是可見的。一般說來，這是分布式系統(tǒng)的設(shè)計(jì)者所不希望的。24二、分布式系統(tǒng)中的命名方案-實(shí)例2（續(xù)）

DEC網(wǎng)命名方案中二、分布式系統(tǒng)中的命名方案-設(shè)計(jì)原則

設(shè)計(jì)命名方案的一個(gè)基本觀點(diǎn)：名字是依賴于位置還是獨(dú)立于位置。這也可以說是性能對(duì)靈活性的問題。在不依賴于位置的命名方案中，對(duì)象的名字不含其在系統(tǒng)中的位置。這使得可對(duì)系統(tǒng)中的遠(yuǎn)程或本地資源(對(duì)象)進(jìn)行一致的存取。但在依賴于位置的命名方案中，就可能出現(xiàn)像DEC網(wǎng)命名方案的問題。移動(dòng)文件要注意改名，后續(xù)操作也要注意名字問題多副本情況一致性的維護(hù)問題透明性的問題25二、分布式系統(tǒng)中的命名方案-設(shè)計(jì)原則

設(shè)計(jì)命名方案的一個(gè)基本三、唯一標(biāo)識(shí)符和字符串名

UID系統(tǒng)中的每一對(duì)象給定一個(gè)唯一的標(biāo)識(shí)符(UID)，即在系統(tǒng)中，它唯一地指稱該對(duì)象。一個(gè)對(duì)象的UID在其整個(gè)生命期內(nèi)決不改變。特別，當(dāng)一對(duì)象從一場(chǎng)點(diǎn)遷移到另一場(chǎng)點(diǎn)時(shí)其UID仍保持不變。一個(gè)UID是相關(guān)對(duì)象的絕對(duì)名字，它通常是利用系統(tǒng)時(shí)鐘產(chǎn)生的。UID也可作為一種權(quán)限使用，此時(shí)，與其相關(guān)的對(duì)象是受保護(hù)的，它既不能由用戶改變，也不應(yīng)被用戶忘卻。為了使UID在全系統(tǒng)范圍內(nèi)唯一，也可以將局部宿主ID作為它的一部分。此外，它還可含有一些隨機(jī)生成的位，使得它難以猜測(cè)，從而起到保密作用。26三、唯一標(biāo)識(shí)符和字符串名

UID26三、唯一標(biāo)識(shí)符和字符串名（續(xù)）

字符串名(簡(jiǎn)稱串名)具有如下特征：同一串名可由不同的用戶用來訪問不同的對(duì)象；不同的串名可由(不同的)用戶用來訪問相同的對(duì)象；對(duì)象可以在場(chǎng)點(diǎn)間遷移不必改變其串名。27三、唯一標(biāo)識(shí)符和字符串名（續(xù)）

字符串名(簡(jiǎn)稱串名)具有如下三、唯一標(biāo)識(shí)符和字符串名（續(xù)）-總結(jié)

在大多數(shù)系統(tǒng)中，字符串名主要供用戶使用，而UID僅供操作系統(tǒng)使用。UID通常是定長(zhǎng)、壓縮形式的(一般有64~128位)，這就有利于系統(tǒng)級(jí)的構(gòu)造、使用和管理；字符串名一般較長(zhǎng)且往往是可變長(zhǎng)的(如10-100字節(jié))，這對(duì)用戶是方便的，但不太適合在系統(tǒng)級(jí)使用。操作系統(tǒng)提供了從字符串名到UID的映射。28三、唯一標(biāo)識(shí)符和字符串名（續(xù)）-總結(jié)

在大多數(shù)系統(tǒng)中，字符串2.3.4名字服務(wù)器的設(shè)計(jì)

名字服務(wù)器(nameserver)的主要功能：將一個(gè)符號(hào)串名(一個(gè)整數(shù)串名或字符串名)映射成系統(tǒng)內(nèi)唯一的物理地址。名字服務(wù)器管理著包含有“名字及其物理地址”的對(duì)照表，系統(tǒng)中的所有服務(wù)程序都由名字服務(wù)器來尋址和定位。例子：292.3.4名字服務(wù)器的設(shè)計(jì)

名字服務(wù)器(nameserve2.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）劍橋大學(xué)設(shè)計(jì)CDCS中的服務(wù)程序族利用其名字服務(wù)器來尋址和定位。為了引用一個(gè)服務(wù)程序，client將代表某個(gè)服務(wù)程序名字的一個(gè)ASCII串發(fā)送給名字服務(wù)器，名字服務(wù)器收到這一信息后，就查看該串是否在其管理的表中。若在，它就返回所指服務(wù)程序的所在處理機(jī)編號(hào)、用于編址它的端口和相應(yīng)的協(xié)議等。在CDCS中，名字服務(wù)器本身的地址是固定的，系統(tǒng)提供了向名字服務(wù)器管理的表中添加或從中刪除信息的命令。不過，出于保護(hù)原因，這類命令只能由系統(tǒng)管理人員使用。302.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）劍橋大學(xué)設(shè)計(jì)CDCS中的服務(wù)2.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）設(shè)計(jì)名字服務(wù)器一般有中央方式、復(fù)制方式和分劃方式三種途徑。用中央方式設(shè)計(jì)時(shí)，全系統(tǒng)僅有一個(gè)(中央)名字服務(wù)器，系統(tǒng)中的所有服務(wù)程序都由它來尋址和定位。但由于性能及可靠性方面的原因，這種方式不常采用。用復(fù)制方式時(shí)，每個(gè)場(chǎng)點(diǎn)都有一個(gè)名字服務(wù)器的副本，用以管理該場(chǎng)點(diǎn)上的所有服務(wù)程序及本場(chǎng)點(diǎn)與其他場(chǎng)點(diǎn)間相互請(qǐng)求的服務(wù)信息。312.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）設(shè)計(jì)名字服務(wù)器一般有中央方式2.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）分劃方式意指：若系統(tǒng)由若干子系統(tǒng)(子網(wǎng))組成，則對(duì)于每個(gè)子系統(tǒng)，用一個(gè)名字服務(wù)器管理本子系統(tǒng)上的所有服務(wù)程序及本子系統(tǒng)與其他子系統(tǒng)相互請(qǐng)求的服務(wù)信息；或者若系統(tǒng)的名字空間可根據(jù)某種方式來分劃，則對(duì)于每個(gè)經(jīng)這樣分劃后的實(shí)體，用單獨(dú)的或復(fù)制式的名字服務(wù)器管理；或者將名字空間組織成層次結(jié)構(gòu)來管理。322.3.4名字服務(wù)器的設(shè)計(jì)（續(xù)）分劃方式意指：322.4DOS中的同步

分布式系統(tǒng)中的進(jìn)程通信消息傳遞（Send、Receive、Replay等原語）RPC組通信這并不是分布式系統(tǒng)的全部?jī)?nèi)容。與此緊密相關(guān)的是進(jìn)程之間如何協(xié)作及如何彼此同步。比如說，在分布式系統(tǒng)中臨界區(qū)如何實(shí)現(xiàn)，資源如何分配。332.4DOS中的同步

分布式系統(tǒng)中的進(jìn)程通信332.4DOS中的同步（續(xù)）

在單CPU系統(tǒng)中，臨界區(qū)、互斥和其它同步問題經(jīng)常使用信號(hào)量、管程等方法來解決，這些方法在分布式系統(tǒng)中并不十分適用，因?yàn)樗鼈円蕾囉诠蚕泶鎯?chǔ)器的存在。比如，有兩個(gè)進(jìn)程通過使用信號(hào)量而相互作用，它們必須都能訪問信號(hào)量。如果它們?cè)谕慌_(tái)機(jī)器上運(yùn)行，能夠共享內(nèi)核中的信號(hào)量，并通過執(zhí)行系統(tǒng)調(diào)用訪問它。如果它們運(yùn)行在不同機(jī)器上，這種方法就不適用了，而需要其它技術(shù)。甚至看似簡(jiǎn)單的問題，比如判斷事件A在事件B之前還是之后發(fā)生的問題也需要認(rèn)真考慮。342.4DOS中的同步（續(xù)）

在單CPU系統(tǒng)中，臨界區(qū)、互斥2.4DOS中的同步（續(xù)）

2.4分布式操作系統(tǒng)中的同步2.4.1時(shí)鐘同步問題提出邏輯時(shí)鐘與事件定序時(shí)間戳?xí)r鐘同步算法2.4.2互斥集中式算法、分布式算法、令牌環(huán)算法、選舉算法352.4DOS中的同步（續(xù)）

2.4分布式操作系統(tǒng)中的同步2.4.1時(shí)鐘同步

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

集中式系統(tǒng)的同步算法：在某地收集系統(tǒng)的2.4.1時(shí)鐘同步

進(jìn)一步而言，一個(gè)單點(diǎn)故障會(huì)造成系統(tǒng)不可靠。最理想的情況是，一個(gè)分布式系統(tǒng)應(yīng)該比單機(jī)系統(tǒng)更可靠，一臺(tái)機(jī)器崩潰不影響其它機(jī)器的繼續(xù)運(yùn)行，不通過集中而獲得同步所使用的方法應(yīng)該與傳統(tǒng)操作系統(tǒng)所用的方法不同。上述的最后一點(diǎn)是十分關(guān)鍵的，在集中式系統(tǒng)中時(shí)間的概念很清楚，當(dāng)進(jìn)程想知道時(shí)間時(shí)，它使用系統(tǒng)調(diào)用，由內(nèi)核提供。如果進(jìn)程A詢問時(shí)間，之后進(jìn)程B也詢問時(shí)間，B得到的時(shí)間值就應(yīng)該大于或等于A所得到的時(shí)間值，但一定不會(huì)小于A得到的時(shí)間值。在分布式系統(tǒng)中，獲得時(shí)間上的一致是并不容易。372.4.1時(shí)鐘同步

進(jìn)一步而言，一個(gè)單點(diǎn)故障會(huì)造成系統(tǒng)不可一個(gè)簡(jiǎn)單的例子：在缺少全局時(shí)間時(shí)的UNIX下的make程序---DOS中很難獲得時(shí)間上的一致UNIX系統(tǒng)中一個(gè)大程序通?？杀环指畛啥鄠€(gè)源文件，如果某個(gè)源文件發(fā)生變化，只需將該文件重新編譯即可，而不需要對(duì)所有的文件進(jìn)行重編譯。Make程序所使用的方法：當(dāng)編程者修改完所有的源文件，他啟動(dòng)make程序，看一下源文件和目標(biāo)文件最后一次修改的時(shí)間，如果源文件INPUT.C時(shí)間為2151，而相應(yīng)的目標(biāo)文件INPUT.O時(shí)間為2150，make就知道INPUT.C在INPUT.O創(chuàng)建后被改動(dòng)過。因此，INPUT.C必須重新編譯。相反，若INPUT.C時(shí)間為2144，而INPUT.O時(shí)間為2145，就不必再重編譯了。make檢查所有的源文件并找出哪一個(gè)需要重編譯，調(diào)用編譯器重新編譯它。38一個(gè)簡(jiǎn)單的例子：在缺少全局時(shí)間時(shí)的UNIX下的make程序-一個(gè)簡(jiǎn)單的例子：在缺少全局時(shí)間時(shí)的UNIX下的make程序---DOS中很難獲得時(shí)間上的一致（續(xù)）在沒有統(tǒng)一時(shí)間的分布式系統(tǒng)中：假設(shè)OUTPUT.O的時(shí)間為2144，緊隨其后OUTPUT.C被修改，但是由于它所在機(jī)器上的時(shí)鐘略慢，造成OUTPUT.C時(shí)間為2143，如圖2-24所示。make將不再調(diào)用編譯器，最終可執(zhí)行的二進(jìn)制程序?qū)ㄓ衫系脑次募托碌脑次募a(chǎn)生的混合目標(biāo)文件，這樣可能將不能再正常執(zhí)行。39一個(gè)簡(jiǎn)單的例子：在缺少全局時(shí)間時(shí)的UNIX下的make程序-一、問題提出所有的計(jì)算機(jī)都有一個(gè)計(jì)時(shí)電路（計(jì)時(shí)器），通常是由一個(gè)精確的石英晶體制成，當(dāng)其在張力限度內(nèi)時(shí)，石英晶體以一定的頻率振蕩。與每個(gè)晶體相關(guān)的是兩個(gè)寄存器、一個(gè)計(jì)數(shù)器和一個(gè)保持寄存器。每次振蕩時(shí)使計(jì)數(shù)器減1，當(dāng)計(jì)數(shù)器減為0時(shí)，產(chǎn)生一次中斷，計(jì)數(shù)器重新從保持寄存器中裝入起始值，通過這種方法可以編程使得一個(gè)計(jì)時(shí)器每秒能產(chǎn)生60次中斷或以其它希望的頻率產(chǎn)生中斷成為可能，每次中斷稱作一個(gè)時(shí)鐘點(diǎn)（clocktick）。當(dāng)系統(tǒng)剛啟動(dòng)時(shí)，總是要求操作者輸入日期和時(shí)間，然后將它們轉(zhuǎn)換成某一已知起始時(shí)間后的時(shí)鐘值，并將它存儲(chǔ)在存儲(chǔ)器中，在每個(gè)時(shí)鐘點(diǎn)時(shí)，中斷服務(wù)程序?qū)⒋酥导?，用這種方法進(jìn)行（軟）時(shí)鐘計(jì)時(shí)。40一、問題提出所有的計(jì)算機(jī)都有一個(gè)計(jì)時(shí)電路（計(jì)時(shí)器），通常是由一、問題提出（續(xù)）在單機(jī)單時(shí)鐘中，如果時(shí)鐘被瞬間關(guān)閉其問題不會(huì)太大，因?yàn)檫@臺(tái)機(jī)器上所有進(jìn)程使用同一時(shí)鐘，它們?nèi)詫?nèi)在地保持一致。比如，文件INPUT.C時(shí)間為2151，文件INPUT.O時(shí)間為2150，make將重新編譯源文件，假設(shè)時(shí)鐘關(guān)閉的時(shí)間為2，真正的時(shí)間則分別為2153和2152，有用的只是相對(duì)時(shí)間。41一、問題提出（續(xù)）在單機(jī)單時(shí)鐘中，如果時(shí)鐘被瞬間關(guān)閉其問題不一、問題提出（續(xù)）多CPU系統(tǒng)中，每個(gè)CPU將擁有自己的時(shí)鐘，情況發(fā)生變化。盡管每個(gè)晶體振蕩頻率總是相當(dāng)穩(wěn)定，但保證不同計(jì)算機(jī)上的晶體以完全相同的頻率振蕩是不太現(xiàn)實(shí)的。實(shí)際上，當(dāng)系統(tǒng)有N臺(tái)計(jì)算機(jī)時(shí)，所有N個(gè)晶體將以略微不同的速度振蕩，導(dǎo)致（軟）時(shí)鐘逐漸不同步，當(dāng)同時(shí)讀這些時(shí)鐘時(shí)，也會(huì)得到不同的值。這種在時(shí)間值上的不同稱作時(shí)鐘偏移（clockskew）。一個(gè)程序期望與文件、目標(biāo)文件、進(jìn)程或消息相聯(lián)系的時(shí)間應(yīng)是正確的，且與產(chǎn)生它們的機(jī)器（即使用哪個(gè)時(shí)鐘）無關(guān)。42一、問題提出（續(xù)）多CPU系統(tǒng)中，每個(gè)CPU將擁有自己的時(shí)鐘一、問題提出（續(xù)）問題：同步所有時(shí)鐘產(chǎn)生一個(gè)單一的、無二義的時(shí)間標(biāo)準(zhǔn)是否可能。解決：Lamport（1978）闡明了時(shí)鐘同步是可能的，并且描述了實(shí)現(xiàn)的算法，他還繼續(xù)對(duì)這個(gè)問題進(jìn)行了一些研究（Lamport1990）。43一、問題提出（續(xù)）問題：同步所有時(shí)鐘產(chǎn)生一個(gè)單一的、無二義的二、邏輯時(shí)鐘與事件定序

Lamport的觀點(diǎn)：時(shí)鐘同步不需要絕對(duì)同步。如果兩個(gè)進(jìn)程無相互作用，它們的時(shí)鐘無須同步，因?yàn)榧词谷鄙偻揭灿X察不出來，不會(huì)產(chǎn)生什么問題。通常并不必需所有進(jìn)程在時(shí)間上完全一致，而是它們?cè)谑录l(fā)生的順序要上完全一致。在上述make程序的例子中，計(jì)時(shí)目的在于說明INPUT.C比INPUT.O早或晚產(chǎn)生，而并不是它們各自產(chǎn)生的絕對(duì)時(shí)間。44二、邏輯時(shí)鐘與事件定序

Lamport的觀點(diǎn)：44二、邏輯時(shí)鐘與事件定序（續(xù)）

如有特殊限制，不僅時(shí)鐘要完全一致，而且不能與真實(shí)時(shí)間有一點(diǎn)點(diǎn)的誤差，這種時(shí)鐘稱作物理時(shí)鐘(physicalclocks)，本節(jié)將討論Lamport算法，它用邏輯時(shí)鐘進(jìn)行同步。45二、邏輯時(shí)鐘與事件定序（續(xù)）

如有特殊限制，不僅時(shí)鐘要完全二、邏輯時(shí)鐘與事件定序（續(xù)）

Lamport為同步邏輯時(shí)鐘定義了“先發(fā)生”關(guān)系：表達(dá)式A→B讀做“A在B之前發(fā)生”，意思是所有進(jìn)程認(rèn)為先發(fā)生事件A，接著發(fā)生事件B，這種關(guān)系有如下兩種情況：如果A和B是在同一進(jìn)程中的兩個(gè)事件，且A發(fā)生在B之前，則A→B為真。如果A是一個(gè)進(jìn)程發(fā)送消息的事件，B為另一個(gè)進(jìn)程接收這一消息的事件，則A→B為真，消息不能在發(fā)送之前接收，也不能在發(fā)送的同時(shí)接收，因?yàn)閭魉瓦^程還需要一定時(shí)間。先發(fā)生是一個(gè)傳遞關(guān)系，即，若A→B且B→C則A→C?！跋劝l(fā)生”也稱為前趨關(guān)系（happen-beforerelation）如果兩個(gè)事件X和Y，出現(xiàn)在不同進(jìn)程中，但并不交換消息（甚至不由第三方間接交換），則X→Y為假，Y→X也為假。則事件X和Y稱為并發(fā)事件，即它們之間不存在誰先誰后的問題。46二、邏輯時(shí)鐘與事件定序（續(xù)）

Lamport為同步邏輯時(shí)二、邏輯時(shí)鐘與事件定序（續(xù)）

水平方向表示空間(不同的進(jìn)程)，垂直方向表示時(shí)間。設(shè)A、B為任意兩個(gè)事件，當(dāng)且僅當(dāng)在圖中不存在從A到B或從B到A的一條路徑時(shí)，事件A與事件B是并發(fā)的。一些存在前趨關(guān)系的事件是：p1→q2，r0→q4，q3→rl，p1→q4。并發(fā)事件是：q0和p2，r0和q3，r0和p3，q3和p3。無法知道兩個(gè)并發(fā)事件(例如q0和p2)哪一個(gè)先發(fā)生。既然這兩個(gè)事件沒有一個(gè)影響另一個(gè)，因此哪一個(gè)先發(fā)生并不重要。47二、邏輯時(shí)鐘與事件定序（續(xù)）

水平方向表示空間(不同的進(jìn)程三、時(shí)間戳

需要一種測(cè)量時(shí)間的方法，使得對(duì)每一事件a，在所有進(jìn)程中都認(rèn)可給它分配一個(gè)時(shí)間值C(a），即打上時(shí)間戳，這些時(shí)間值必須有如下性質(zhì)：若A→B則C(A)<C(B)。若a和b是同一進(jìn)程中的兩個(gè)事件，且a→b，則C(a)<C(b)同理，若a是一個(gè)進(jìn)程發(fā)送消息的事件，b為另一個(gè)進(jìn)程接收消息的事件，那么C(a)<C(b)。時(shí)鐘時(shí)間值C必須向前走（遞增），不能倒退（減少）。校正時(shí)間的操作是給時(shí)間加上一個(gè)正值，而不是減一個(gè)正數(shù)。48三、時(shí)間戳

需要一種測(cè)量時(shí)間的方法，使得對(duì)每一事件a，在所有三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間

各進(jìn)程運(yùn)行在不同的機(jī)器上，每個(gè)機(jī)器都有自己的時(shí)鐘，以各自不同的速率工作。進(jìn)程0的時(shí)鐘滴答（tick）了6下時(shí)，進(jìn)程1的時(shí)鐘滴答了8下，進(jìn)程2的時(shí)鐘滴答了10下。在時(shí)刻6，進(jìn)程0把A消息發(fā)送到進(jìn)程1，消息到達(dá)的時(shí)間取決于你信任哪一個(gè)時(shí)鐘，不管怎樣，當(dāng)它到達(dá)時(shí)，進(jìn)程1讀到的時(shí)刻是16，若消息自身攜帶的起始時(shí)刻是6，進(jìn)程1會(huì)推算到它需滴答10下才到達(dá)，這個(gè)值是可能的。依次類推，消息B從進(jìn)程1到進(jìn)程2需要滴答16下這也是可能的。問題：消息C從進(jìn)程2到進(jìn)程1是在60時(shí)刻離開，56時(shí)刻到達(dá)。同理，消息D從進(jìn)程1到進(jìn)程0是在64時(shí)刻離開，54時(shí)刻到達(dá)，這是絕對(duì)不可能出現(xiàn)的，必須防止這種情況的出現(xiàn)。49三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間各進(jìn)程運(yùn)行三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間（續(xù)）Lamport的解決方案：直接使用先發(fā)生關(guān)系，因?yàn)镃在60時(shí)刻離開，它只能在61時(shí)刻或更晚時(shí)刻到達(dá)所以每條消息都攜帶發(fā)送者的時(shí)鐘以指出其發(fā)送的時(shí)刻，當(dāng)消息到達(dá)時(shí)，接收者時(shí)鐘若比消息發(fā)送時(shí)鐘小，就立即將自己的時(shí)鐘調(diào)到比發(fā)送時(shí)間大1或更多的值。在圖b中，C現(xiàn)在到達(dá)的時(shí)間是61。同樣D到達(dá)的時(shí)間是70。50三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間（續(xù)）Lam三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間（續(xù)）為適應(yīng)全局統(tǒng)一時(shí)間的需要，只需對(duì)此作一點(diǎn)補(bǔ)充即可，即在每?jī)蓚€(gè)事件之間，時(shí)鐘必須至少滴答一下，如果一個(gè)進(jìn)程以相當(dāng)快的速度連續(xù)發(fā)送或接收兩條消息，它必須在這中間至少滴答一下。在某些情況下需要一個(gè)附加條件：兩個(gè)事件不會(huì)精確地同時(shí)發(fā)生，為了實(shí)現(xiàn)這個(gè)目標(biāo)，我們可以將事件所在的進(jìn)程號(hào)附加在事件發(fā)生時(shí)間的低位，并用小數(shù)點(diǎn)分開。這樣，如果在進(jìn)程1和進(jìn)程2中同時(shí)發(fā)生了2個(gè)事件，發(fā)生時(shí)刻都是40，則前者記為40.1，后者記為40.2。51三、時(shí)間戳—Lamport算法怎么給事件分配時(shí)間（續(xù)）為適應(yīng)三、時(shí)間戳-Lamport算法怎么給事件分配時(shí)間（續(xù)）使用這種方法，分布式系統(tǒng)中將時(shí)間分配給所有事件的方法遵照如下規(guī)則：若在同一進(jìn)程中a發(fā)生在b之前，則C(a)<C(b)；若a和b分別代表發(fā)送消息和接收消息，則C(a)<C(b)；對(duì)所有事件a和b，C(a)≠C(b)這個(gè)算法給我們提供了對(duì)系統(tǒng)中所有的事件進(jìn)行排序的一種方法，許多其它的分布式算法也需要這種排序以避免混亂。52三、時(shí)間戳-Lamport算法怎么給事件分配時(shí)間（續(xù)）使用這四、時(shí)鐘同步算法所有算法都有相同的系統(tǒng)基礎(chǔ)模型：每臺(tái)機(jī)器上假設(shè)都有一個(gè)每秒產(chǎn)生H次中斷的計(jì)時(shí)器。當(dāng)時(shí)間到時(shí)，中斷處理程序?qū)④洉r(shí)鐘加1，軟時(shí)鐘記錄從過去某一約定值開始的中斷次數(shù)。我們把這個(gè)時(shí)鐘值記為C。更特殊的，當(dāng)UTC時(shí)間為t時(shí)，在機(jī)器p上的時(shí)間值是Cp(t)，最完美的情況是對(duì)所有的p和t，有Cp(t)=t，換言之，dC/dt理想值為1。

UTC：世界協(xié)調(diào)時(shí)間(UniversalTimeCoordinated)。GPS系統(tǒng)中有兩種時(shí)間區(qū)分，一為UTC，另一為L(zhǎng)T（地方時(shí)）。兩者的區(qū)別為時(shí)區(qū)不同，UTC就是0時(shí)區(qū)的時(shí)間，地方時(shí)為本地時(shí)間。53四、時(shí)鐘同步算法所有算法都有相同的系統(tǒng)基礎(chǔ)模型：53四、時(shí)鐘同步算法（續(xù)）真正計(jì)時(shí)器并不是每秒精確的中斷H次，理論上當(dāng)H=60時(shí)，計(jì)時(shí)器每小時(shí)應(yīng)該產(chǎn)生216,000個(gè)滴答。實(shí)際上，用現(xiàn)代計(jì)時(shí)時(shí)鐘芯片可以獲得相關(guān)的延遲是10-5，意味著一臺(tái)機(jī)器每小時(shí)可以獲得215,998～216,002范圍的滴答，若存在某一常數(shù)ρ，便有：54四、時(shí)鐘同步算法（續(xù)）真正計(jì)時(shí)器并不是每秒精確的中斷H次，理四、時(shí)鐘同步算法（續(xù)）計(jì)時(shí)器可以在它規(guī)定的范圍內(nèi)工作，制造商標(biāo)明的常數(shù)ρ是最大漂移速度。稍慢的、精確的、稍快的時(shí)鐘如圖2-27所示。55四、時(shí)鐘同步算法（續(xù)）計(jì)時(shí)器可以在它規(guī)定的范圍內(nèi)工作，制造商四、時(shí)鐘同步算法（續(xù)）若兩個(gè)時(shí)鐘相對(duì)于UTC時(shí)間以相反方向漂移，在它們同步后的Δt時(shí)間內(nèi)，它們可能的差值為2ρΔt，若操作系統(tǒng)的設(shè)計(jì)者要保證每?jī)蓚€(gè)時(shí)鐘之間的相差不超過δ，時(shí)鐘必須至少在每δ/(2ρ)秒內(nèi)再同步一次（用軟件方法），不同算法實(shí)現(xiàn)再同步的方法不同。56四、時(shí)鐘同步算法（續(xù)）若兩個(gè)時(shí)鐘相對(duì)于UTC時(shí)間以相反方向漂1.Cristian算法

非常適合于只有一臺(tái)機(jī)器上有WWV接收器，其它所有機(jī)器與它同步的系統(tǒng)。把擁有WWV接受器的那臺(tái)機(jī)器稱作時(shí)間服務(wù)器，算法是基于Cristian(1989)和以前的一些工作。每臺(tái)機(jī)器以小于或等于δ/(2ρ)秒的周期定期地向時(shí)間服務(wù)器發(fā)送消息詢問當(dāng)前的時(shí)間，時(shí)間服務(wù)器接到消息后就盡快回答含有當(dāng)前時(shí)間CUTC值的消息，如圖2-28所示。

571.Cristian算法

非常適合于只有一臺(tái)機(jī)器上有WWV接1.Cristian算法（續(xù)）

當(dāng)發(fā)送者得到回答后，就將它的時(shí)鐘設(shè)為CUTC，但是這種算法有兩個(gè)問題：第一個(gè)重要的問題是時(shí)間決不能倒退，若發(fā)送者的時(shí)鐘快，CUTC將會(huì)比發(fā)送者的時(shí)間值C小，若把發(fā)送者的時(shí)間值直接改成CUTC會(huì)導(dǎo)致嚴(yán)重的錯(cuò)誤，比如在時(shí)鐘變化后，編譯產(chǎn)生的目標(biāo)文件的時(shí)間早于時(shí)鐘變化前源文件的修改時(shí)間。這種變化必須逐步進(jìn)行，一種方法是假設(shè)將計(jì)時(shí)器設(shè)置為每秒產(chǎn)生100次中斷，通常，每次中斷將時(shí)間加10毫秒，當(dāng)時(shí)鐘需要慢下來時(shí)，中斷服務(wù)程序每次僅加9毫秒，直到調(diào)整好為止。同樣時(shí)鐘要加快時(shí)，每次中斷服務(wù)程序?qū)r(shí)鐘加11毫秒，而不是立即把時(shí)間調(diào)到所需要的值。581.Cristian算法（續(xù)）

當(dāng)發(fā)送者得到回答后，就將它1.Cristian算法（續(xù)）

另一個(gè)小問題是從時(shí)間服務(wù)器端發(fā)送的應(yīng)答到發(fā)送者要花費(fèi)時(shí)間，這種延遲可能較大，而且隨著網(wǎng)絡(luò)負(fù)荷的改變而改變。Cristian的處理方法是試圖測(cè)量這個(gè)延遲值。最簡(jiǎn)單的方法：發(fā)送者精確地記錄從向時(shí)間服務(wù)器發(fā)送請(qǐng)求到接收到應(yīng)答的時(shí)間間隔，假設(shè)起始時(shí)間是T0與結(jié)束時(shí)間T1，他們都是通過同一個(gè)時(shí)鐘來測(cè)量的，就算發(fā)送者的時(shí)鐘與UTC有一定的差值，它所測(cè)得的時(shí)間間隔還是較精確的。在沒有其它任何信息時(shí)，消息傳送時(shí)間的最佳估計(jì)值是（T1-T0）/2，當(dāng)應(yīng)答消息到達(dá)時(shí)，消息中的時(shí)間值再加上此值就得到了當(dāng)前時(shí)間服務(wù)器的時(shí)間估計(jì)值，如果理論上知道了最小的傳送時(shí)間，那么與時(shí)間估算相關(guān)的其它性質(zhì)也能推算出來。591.Cristian算法（續(xù)）

另一個(gè)小問題是從時(shí)間服務(wù)器1.Cristian算法（續(xù)）

如果知道時(shí)間服務(wù)器中斷處理的時(shí)間和處理消息的時(shí)間，這樣的估算還能進(jìn)一步改進(jìn)，設(shè)中斷處理的時(shí)間是I，那么傳輸時(shí)間間隔為T1-T0-I，所以估算單向傳輸時(shí)間為它的一半。系統(tǒng)中確實(shí)存在著從A到B的消息和從B到A的消息傳輸路徑不同，因此就有不同的傳輸時(shí)間，但我們目前先不考慮這種情況。為了提高精確度，Cristian建議不要只做一次測(cè)量，而做一系列測(cè)量，測(cè)量中T1-T0超出一定范圍就認(rèn)為是網(wǎng)絡(luò)阻塞，為不可信值。對(duì)剩余的測(cè)量值取平均值會(huì)得到較好的估算值，也就是說，最快返回的消息是最精確的，因?yàn)橄⒂龅阶枞钌?，所以它最能代表純粹的傳輸時(shí)間。601.Cristian算法（續(xù)）

如果知道時(shí)間服務(wù)器中斷處理2.Berkeley算法

在BerkeleyUNIX中采取了完全相反的方法，這里的時(shí)間服務(wù)器（實(shí)際是時(shí)間守護(hù)進(jìn)程）是主動(dòng)的，它定期地詢問每臺(tái)機(jī)器的時(shí)間。然后基于這些回答，計(jì)算出平均值并告訴所有的機(jī)器將它們的時(shí)鐘撥快或撥慢到一個(gè)新的值。這種方法適合于沒有WWV接收器的系統(tǒng)，時(shí)間守護(hù)進(jìn)程的時(shí)間必須由操作者定期地手工設(shè)置，這種方法如圖2-29所示。612.Berkeley算法

在BerkeleyUNIX中采取2.Berkeley算法（續(xù)）

(a),時(shí)間守護(hù)進(jìn)程在3:00把它的時(shí)間告訴其它機(jī)器，并且詢問它們各自的時(shí)間(b)，各機(jī)器將它們各自的時(shí)間與時(shí)間守護(hù)進(jìn)程時(shí)間的差值告訴時(shí)間守護(hù)進(jìn)程，(c)守護(hù)進(jìn)程計(jì)算出它們的平均值，通知各機(jī)器如何調(diào)整各自的時(shí)間。622.Berkeley算法（續(xù)）

(a),時(shí)間守護(hù)進(jìn)程在3:3.平均值算法

上述兩種方法都高度集中的，有不足之處。存在一些非集中式算法，如：一種分布式時(shí)鐘同步算法：它是將時(shí)間劃分成固定長(zhǎng)度的再同步間隔，第i次間隔開始于T0+iR，而結(jié)束于T0+(i+1)R，這里的T0是過去某一約定的時(shí)間，R是一個(gè)系統(tǒng)參數(shù)。在每次間隔的開始處，每臺(tái)機(jī)器根據(jù)自己的時(shí)鐘廣播發(fā)送當(dāng)前的時(shí)間，由于在不同機(jī)器上的時(shí)鐘不可能完全同速工作，這種廣播就不會(huì)完全同時(shí)發(fā)生。633.平均值算法

上述兩種方法都高度集中的，有不足之處。存在一3.平均值算法（續(xù)）在機(jī)器廣播發(fā)送時(shí)間之后，它啟動(dòng)本地計(jì)時(shí)器收集在S時(shí)間間隔中到達(dá)的其它廣播，當(dāng)所有廣播到達(dá)后，執(zhí)行一個(gè)算法，得到新的時(shí)間值。僅將這些值取平均值；——最簡(jiǎn)單先除去m個(gè)最大值和m個(gè)最小值，平均其余值。去掉兩端值可認(rèn)為是一種對(duì)m個(gè)錯(cuò)誤時(shí)鐘發(fā)出毫無意義的時(shí)間值的一種自我保護(hù)。給每條消息值加上一個(gè)從源到目的地的傳送時(shí)間估計(jì)值，這種估計(jì)值可參考網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或計(jì)算試探消息的響應(yīng)時(shí)間而得出643.平均值算法（續(xù)）在機(jī)器廣播發(fā)送時(shí)間之后，它啟動(dòng)本地計(jì)時(shí)器4.多個(gè)外部時(shí)鐘源

對(duì)使用UTC進(jìn)行同步又要求特別精確的系統(tǒng)來說，可給系統(tǒng)安裝如WWV，GEOS或其它UTC源的多接收器來實(shí)現(xiàn)的。時(shí)間源自身固有的不精確性以及信號(hào)傳送的不定性，最好的操作系統(tǒng)能做的也只是建立一個(gè)UTC時(shí)間范圍。一般來說，不同的時(shí)間源會(huì)產(chǎn)生不同的時(shí)間范圍，這種范圍需要機(jī)器和它們達(dá)成一致。654.多個(gè)外部時(shí)鐘源

對(duì)使用UTC進(jìn)行同步又要求特別精確的系統(tǒng)4.多個(gè)外部時(shí)鐘源（續(xù)）

為達(dá)到一致，每個(gè)具有UTC源的處理機(jī)定期在每一UTC精確分的開始處廣播其時(shí)間范圍，但沒有處理機(jī)會(huì)同時(shí)獲得時(shí)間包，傳輸和接收延遲依賴于纜線的距離和包必須經(jīng)過的網(wǎng)關(guān)數(shù)，它對(duì)于每一對(duì)UTC源和處理機(jī)之間都不相同。其它因素，如多臺(tái)機(jī)器要同時(shí)在以太網(wǎng)上傳輸而發(fā)生的碰撞。更進(jìn)一步，如一臺(tái)處理機(jī)忙于處理以前的包，它可能在相當(dāng)長(zhǎng)的幾微秒內(nèi)不去理會(huì)到來的時(shí)間包，從而導(dǎo)致了時(shí)間的不確定性。664.多個(gè)外部時(shí)鐘源（續(xù)）

為達(dá)到一致，每個(gè)具有UTC源的處理4.多個(gè)外部時(shí)鐘源（續(xù)）

解決：OpenSoftwareFoundation（開放軟件組織）的分布式計(jì)算環(huán)境的處理方法某個(gè)接收器接收到所有時(shí)間源的UTC時(shí)間范圍后，首先檢查是否有與其他范圍不相交的UTC范圍。如果有，這些UTC范圍一定是錯(cuò)誤的，棄而不用。剩余的時(shí)間范圍都是準(zhǔn)確的UTC時(shí)間所在的范圍；因此接著就求出這些范圍相交的部分；最后將相交部分的中點(diǎn)作為準(zhǔn)確的UTC時(shí)間，并將內(nèi)部時(shí)鐘設(shè)置為該值。674.多個(gè)外部時(shí)鐘源（續(xù)）

解決：OpenSoftware4.多個(gè)外部時(shí)鐘源（續(xù)）

684.多個(gè)外部時(shí)鐘源（續(xù)）

682.4.2互斥

涉及多個(gè)進(jìn)程的系統(tǒng)使用臨界區(qū)容易編程當(dāng)一個(gè)進(jìn)程必須讀或修改某些共享數(shù)據(jù)結(jié)構(gòu)時(shí)，它首先進(jìn)入臨界區(qū)獲得互斥鎖，保證沒有其它的進(jìn)程能同時(shí)使用該共享數(shù)據(jù)結(jié)構(gòu)。在單處理機(jī)系統(tǒng)中，使用信號(hào)量、管程和一些近似的結(jié)構(gòu)來保護(hù)臨界區(qū)。幾個(gè)例子：在分布式系統(tǒng)中臨界區(qū)和互斥是如何實(shí)現(xiàn)的。692.4.2互斥

涉及多個(gè)進(jìn)程的系統(tǒng)使用臨界區(qū)容易編程69一、集中式算法

在分布式系統(tǒng)中獲得互斥的最直接方法是仿照單處理機(jī)系統(tǒng)的方法，選一個(gè)進(jìn)程為協(xié)調(diào)者（比如在最大網(wǎng)絡(luò)地址機(jī)器上運(yùn)行的進(jìn)程）。無論什么時(shí)候進(jìn)程要進(jìn)入臨界區(qū)，它將向協(xié)調(diào)者發(fā)送請(qǐng)求消息，說明它想進(jìn)入哪個(gè)臨界區(qū)并希望獲得允許。如果當(dāng)前該臨界區(qū)內(nèi)沒有其它任何進(jìn)程，協(xié)調(diào)者就發(fā)送允許進(jìn)入消息，如圖2-30(a)所示。當(dāng)應(yīng)答到達(dá)時(shí)，請(qǐng)求者就可以進(jìn)入臨界區(qū)。70一、集中式算法

在分布式系統(tǒng)中獲得互斥的最直接方法是仿照單處一、集中式算法（續(xù)）

現(xiàn)在假設(shè)有另一個(gè)進(jìn)程，如圖2-30(b)所示，請(qǐng)求進(jìn)入同一個(gè)臨界區(qū)，協(xié)調(diào)者知道該臨界區(qū)已有一個(gè)進(jìn)程，所以不能同意該請(qǐng)求，最好的辦法是發(fā)出拒絕允許應(yīng)答。而在圖2-30中，協(xié)調(diào)者回避應(yīng)答，這樣就阻塞了進(jìn)程2，使它等待應(yīng)答。另一方面，協(xié)調(diào)者還可以發(fā)送“拒絕請(qǐng)求”應(yīng)答。兩種方法都會(huì)把進(jìn)程2放入等待隊(duì)列，等待臨界區(qū)的釋放。71一、集中式算法（續(xù)）

現(xiàn)在假設(shè)有另一個(gè)進(jìn)程，如圖2-30(一、集中式算法（續(xù)）

當(dāng)進(jìn)程1從臨界區(qū)退出時(shí)，它向協(xié)調(diào)者發(fā)送釋放互斥消息訪問，如圖2-30(c)所示，協(xié)調(diào)者從推遲請(qǐng)求隊(duì)列中取出最前面的進(jìn)程，向它發(fā)送允許進(jìn)入消息。如果該進(jìn)程仍然阻塞（即，這是第一條發(fā)給它的允許進(jìn)入消息）它去除阻塞且進(jìn)入臨界區(qū)；如果明確發(fā)送一消息拒絕它進(jìn)入臨界區(qū)，此進(jìn)程應(yīng)該不時(shí)地查詢輸入的消息，或者接著將它阻塞等待許可響應(yīng)。不管怎么樣，當(dāng)它發(fā)現(xiàn)允許進(jìn)入時(shí)，它就可以進(jìn)入臨界區(qū)。72一、集中式算法（續(xù)）

當(dāng)進(jìn)程1從臨界區(qū)退出時(shí)，它向協(xié)調(diào)者發(fā)一、集中式算法（續(xù)）

優(yōu)點(diǎn)：算法保證了互斥的實(shí)現(xiàn)，協(xié)調(diào)者僅能讓某一進(jìn)程在某一時(shí)刻進(jìn)入臨界區(qū)。也很公平，因?yàn)樵试S請(qǐng)求的順序同它們接收的順序一致，沒有進(jìn)程永遠(yuǎn)等待（沒有饑餓）。容易實(shí)現(xiàn)，每用一次臨界區(qū)只需3條消息（請(qǐng)求，允許，釋放），它不僅能管理臨界區(qū)，也可用于更普遍的資源分配。缺點(diǎn)：協(xié)調(diào)者是一個(gè)單點(diǎn)故障，如它崩潰，整個(gè)系統(tǒng)將癱瘓，如果進(jìn)程在請(qǐng)求之后被阻塞，以上這兩種情況都沒有消息返回，請(qǐng)求者不能從“拒絕請(qǐng)求”中辨認(rèn)出協(xié)調(diào)者已崩潰。此外，大系統(tǒng)中單協(xié)調(diào)者會(huì)成為執(zhí)行的瓶頸。73一、集中式算法（續(xù)）

優(yōu)點(diǎn)：73二、分布式算法

分布式互斥算法，第一次出現(xiàn)的是在1978年Lamport關(guān)于時(shí)鐘同步的論文中，后來Ricart和Agrawale對(duì)它作了進(jìn)一步的改進(jìn)，算法前提：Ricart和Agrawale算法要求系統(tǒng)中所有事件都是全序的。也就是說，對(duì)任何事件組如消息，哪個(gè)先發(fā)生必須無歧異。算法：當(dāng)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，它要建立一個(gè)包括它要進(jìn)入的臨界區(qū)的名字、處理機(jī)號(hào)和當(dāng)前時(shí)間的消息，然后將消息發(fā)送給所有其它進(jìn)程。概念上講也包括發(fā)送給它自身。發(fā)送的消息假設(shè)是可靠的，即每條消息都應(yīng)該被確認(rèn)，如可能應(yīng)使用可靠的組通信，避免使用單個(gè)的消息通信。74二、分布式算法

分布式互斥算法，第一次出現(xiàn)的是在1978年L二、分布式算法（續(xù)）

當(dāng)一個(gè)進(jìn)程接收另一個(gè)進(jìn)程請(qǐng)求消息時(shí)，根據(jù)接收方的狀態(tài)以及臨界區(qū)的名字。有三種情況要加以區(qū)別：若接收者不在臨界區(qū)中，也不想進(jìn)入臨界區(qū)，它就向發(fā)送者發(fā)送OK消息。若接收者已經(jīng)在臨界區(qū)中，它就不必回答，而是負(fù)責(zé)對(duì)請(qǐng)求隊(duì)列排隊(duì)。若接收者要進(jìn)入臨界區(qū)，但是還沒有進(jìn)入時(shí)，它要將發(fā)來的消息和它發(fā)送給其余進(jìn)程的時(shí)間戳對(duì)比，取小的那個(gè)，如果來的消息的時(shí)戳小，接收者發(fā)送OK消息，如果接收者本身的時(shí)間戳更小，那么接收者負(fù)責(zé)排列請(qǐng)求隊(duì)列而不發(fā)送任何消息。75二、分布式算法（續(xù)）

當(dāng)一個(gè)進(jìn)程接收另一個(gè)進(jìn)程請(qǐng)求消息時(shí)，二、分布式算法（續(xù)）

在發(fā)送完允許進(jìn)入臨界區(qū)的請(qǐng)求后，進(jìn)程將不做任何事，僅等待所有的允許消息，一旦得到允許，它就進(jìn)入臨界區(qū)，它從臨界區(qū)退出時(shí)，向隊(duì)列中的所有的進(jìn)程發(fā)送OK消息，并把它從隊(duì)列中刪除。76二、分布式算法（續(xù)）

在發(fā)送完允許進(jìn)入臨界區(qū)的請(qǐng)求后，進(jìn)程二、分布式算法（續(xù)）

分析：如果沒有沖突，則正常工作。但是，假設(shè)兩個(gè)進(jìn)程要同時(shí)試圖進(jìn)入一個(gè)臨界區(qū)，如圖2-31(a)所示77二、分布式算法（續(xù)）

分析：如果沒有沖突，則正常工作。但是二、分布式算法（續(xù)）

進(jìn)程0發(fā)出時(shí)戳為8的請(qǐng)求，而同時(shí)進(jìn)程2發(fā)出時(shí)間戳為12的請(qǐng)求。進(jìn)程1不想進(jìn)入臨界區(qū)，所以它向2個(gè)發(fā)送者發(fā)回OK。進(jìn)程0和2同時(shí)發(fā)現(xiàn)沖突，比較時(shí)間戳，進(jìn)程2發(fā)現(xiàn)自己的大，它只好同意進(jìn)程0進(jìn)入臨界區(qū)，向0發(fā)送OK，進(jìn)程0就把進(jìn)程2的請(qǐng)求排在隊(duì)列中，為以后處理用，自己進(jìn)入臨界區(qū)，如圖2-31(b)所示。78二、分布式算法（續(xù)）

進(jìn)程0發(fā)出時(shí)戳為8的請(qǐng)求，而同時(shí)進(jìn)程二、分布式算法（續(xù)）

當(dāng)進(jìn)程0結(jié)束退出臨界區(qū)時(shí)，它把進(jìn)程2的請(qǐng)求從隊(duì)列中取出，并向進(jìn)程2發(fā)送OK，允許進(jìn)程2進(jìn)入臨界區(qū)，如圖2-31(c)所示。算法之所以能夠使用，因?yàn)樵诋a(chǎn)生請(qǐng)求沖突時(shí)，遵守按時(shí)間戳排序，小時(shí)戳優(yōu)先的規(guī)則。

79二、分布式算法（續(xù)）

當(dāng)進(jìn)程0結(jié)束退出臨界區(qū)時(shí)，它把進(jìn)程2二、分布式算法（續(xù)）

注意：如果進(jìn)程2比進(jìn)程0早發(fā)送消息，進(jìn)程0在它請(qǐng)求進(jìn)入臨界區(qū)之前獲得了進(jìn)程2的請(qǐng)求消息，它允許進(jìn)程2進(jìn)入臨界區(qū)，當(dāng)進(jìn)程2接收到進(jìn)程0的請(qǐng)求時(shí)，它發(fā)現(xiàn)自己已經(jīng)在臨界區(qū)了，所以把進(jìn)程0排在等待隊(duì)列中。80二、分布式算法（續(xù)）

注意：如果進(jìn)程2比進(jìn)程0早發(fā)送消息，二、分布式算法（續(xù)）

問題：互斥必須無死鎖或無饑餓。每次進(jìn)入臨界區(qū)需要2(n-1)條消息，這里n為系統(tǒng)中的進(jìn)程數(shù)目。最好的是不存在單點(diǎn)故障。若有一個(gè)進(jìn)程崩潰，它就不能回答請(qǐng)求，這種不發(fā)言將被解釋為不允許進(jìn)入臨界區(qū)，這樣就阻止了任何試圖進(jìn)入臨界區(qū)的進(jìn)程。因?yàn)閚個(gè)進(jìn)程之一失效的可能性是單協(xié)調(diào)者失效的n倍，我們必須設(shè)法換一種n倍復(fù)雜和需要更多啟動(dòng)網(wǎng)絡(luò)通信的算法。81二、分布式算法（續(xù)）

問題：81二、分布式算法（續(xù)）

修補(bǔ)：當(dāng)請(qǐng)求到達(dá)時(shí)，不管它是許可還是拒絕，接收者都要發(fā)送應(yīng)答，一旦請(qǐng)求或應(yīng)答消息丟失，發(fā)送者的等待時(shí)間到，它繼續(xù)發(fā)送直到得到應(yīng)答或者認(rèn)為目的進(jìn)程已經(jīng)崩潰為止。在收到拒絕應(yīng)答后，發(fā)送者應(yīng)該阻塞等待直到獲得OK消息。另一個(gè)問題：要么組間通信必須使用原語，要么每個(gè)進(jìn)程必須維持一張組成員表，包括進(jìn)入組進(jìn)程、離開組進(jìn)程和崩潰進(jìn)程。這種方法最適用于小的從不改變成員的進(jìn)程組。集中式算法中，處理所有請(qǐng)求會(huì)產(chǎn)生瓶頸的問題；在分布式算法中，所有進(jìn)程都要參與決定是否進(jìn)入臨界區(qū)，若一個(gè)進(jìn)程不能處理消息，那么強(qiáng)迫所有進(jìn)程并行完成同一件事并不能改善整體的性能82二、分布式算法（續(xù)）

修補(bǔ)：當(dāng)請(qǐng)求到達(dá)時(shí)，不管它是許可還是二、分布式算法（續(xù)）

對(duì)該算法有一點(diǎn)小的改進(jìn)不需獲得每個(gè)進(jìn)程允許后方可進(jìn)入臨界區(qū)，只要防止任何兩個(gè)進(jìn)程同時(shí)進(jìn)入同一個(gè)臨界區(qū)即可，算法可改成：當(dāng)一個(gè)進(jìn)程從大多數(shù)進(jìn)程那里獲得允許而并不需要所有進(jìn)程都允許時(shí)，它就可以進(jìn)入臨界區(qū)。這種算法中，一個(gè)進(jìn)程在批準(zhǔn)另一個(gè)進(jìn)程進(jìn)入臨界區(qū)之后，在這個(gè)進(jìn)程退出臨界區(qū)之前，它不能再允許其它進(jìn)程進(jìn)入該臨界區(qū)?？傊@種算法還是比原來集中式算法慢，復(fù)雜，昂貴，而且不健壯。83二、分布式算法（續(xù)）

對(duì)該算法有一點(diǎn)小的改進(jìn)83三、令牌環(huán)算法

如圖a所示的總線網(wǎng)，進(jìn)程沒有固定次序。用軟件的方法，構(gòu)造出一個(gè)邏輯環(huán)，環(huán)中每個(gè)進(jìn)程都有一個(gè)位置，如圖b所示。進(jìn)程在環(huán)上的位置可以用網(wǎng)絡(luò)地址的數(shù)字序號(hào)指定，也可以用其它方法指定。排序的方法并不重要，重要的是每個(gè)進(jìn)程都要知道誰在它的下一個(gè)位置。84三、令牌環(huán)算法

如圖a所示的總線網(wǎng)，進(jìn)程沒有固定次序。用軟件三、令牌環(huán)算法（續(xù)）

算法思想：令牌環(huán)被初始化后，進(jìn)程0首先獲得令牌。這樣，令牌開始繞環(huán)運(yùn)動(dòng)，它從進(jìn)程K傳遞到進(jìn)程K+1（以點(diǎn)到點(diǎn)的方式傳遞）。當(dāng)進(jìn)程從它的前一個(gè)鄰居手中得到令牌時(shí)，檢查它所試圖進(jìn)入的臨界區(qū)，如果該臨界區(qū)是空的，則該進(jìn)程可以進(jìn)入臨界區(qū)，做它要做的工作，然后離開臨界區(qū)。它退出后，將令牌傳遞到它的下一個(gè)鄰居，不允許使用同一令牌進(jìn)入第二個(gè)臨界區(qū)。若一個(gè)進(jìn)程得到了它相鄰進(jìn)程傳遞來的令牌，但它并不想進(jìn)入臨界區(qū)，就將該令牌往下傳遞。這樣，如果沒有任何其它的進(jìn)程想進(jìn)入臨界區(qū)時(shí)，令牌就會(huì)高速地沿環(huán)繞行。85三、令牌環(huán)算法（續(xù)）

算法思想：85三、令牌環(huán)算法（續(xù)）

優(yōu)點(diǎn)：在任何時(shí)刻只有一個(gè)進(jìn)程擁有令牌，所以只有一個(gè)進(jìn)程可以進(jìn)入臨界區(qū)。由于令牌以固定順序運(yùn)動(dòng)，所以不會(huì)出現(xiàn)饑餓進(jìn)程。一旦一個(gè)進(jìn)程想進(jìn)入臨界區(qū)，最不理想的情況是等待所有其它進(jìn)程進(jìn)入后再退出臨界區(qū)所用的時(shí)間之和。86三、令牌環(huán)算法（續(xù)）

優(yōu)點(diǎn)：86三、令牌環(huán)算法（續(xù)）

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

算法存在的問題：87四、三種算法的比較

88四、三種算法的比較

88四、三種算法的比較（續(xù)）

有關(guān)“每次進(jìn)入需要的消息”集中式算法最簡(jiǎn)單，也最有效的，它在進(jìn)程進(jìn)入和退出臨界區(qū)時(shí)，只用了3條消息，即請(qǐng)求進(jìn)入，同意進(jìn)入和退出時(shí)釋放。分布式算法需要N-1條，（給每個(gè)其它進(jìn)程）請(qǐng)求消息，及另外的N-1條允許消息，總共有2(N-1)條消息，對(duì)于令牌算法該數(shù)目是可變的，如果每個(gè)進(jìn)程總是想進(jìn)入一個(gè)臨界區(qū)，則令牌的每次傳遞將導(dǎo)致一次進(jìn)出臨界區(qū)。平均每一次進(jìn)入臨界區(qū)入口都有一條消息。在其它極限情況下，令牌也許將幾小時(shí)幾小時(shí)地沿環(huán)傳遞而沒有進(jìn)程想使用它，在這種情況下，每一次進(jìn)入臨界區(qū)入出口消息數(shù)是無界的。89四、三種算法的比較（續(xù)）

有關(guān)“每次進(jìn)入需要的消息”89四、三種算法的比較（續(xù)）

有關(guān)“延遲”進(jìn)程需要進(jìn)入臨界區(qū)到它能進(jìn)入臨界區(qū)的延遲也隨著這三種算法而變化：當(dāng)臨界區(qū)很少被使用時(shí)，造成延遲的主要因素是控制進(jìn)入臨界區(qū)的機(jī)制。當(dāng)臨界區(qū)被經(jīng)常使用時(shí)，延遲的主要因素是等待其它進(jìn)程使用的過程。表2-1表示前一種情況，假設(shè)網(wǎng)絡(luò)在某一時(shí)刻只能處理一條消息：在集中式算法的情況下，進(jìn)入臨界區(qū)只需要處理2條消息的時(shí)間，在分布式算法的情況下需要2(N-1)條消息，對(duì)令牌環(huán)算法，時(shí)間從0（剛接收到令牌）到N-1（釋放令牌）變化。90四、三種算法的比較（續(xù)）

有關(guān)“延遲”90四、三種算法的比較（續(xù)）

問題：這三種算法在進(jìn)程崩潰時(shí)都損失慘重，為了避免由于某些崩潰造成的系統(tǒng)癱瘓，必須引入特殊的方法和附加的復(fù)雜性。更具諷刺意義的是分布式算法比集中式算法對(duì)崩潰事件更敏感。這些算法都不能用于容錯(cuò)系統(tǒng)，但如果崩潰事件很少發(fā)生的話，這些算法都是可以接受的。91四、三種算法的比較（續(xù)）

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

由Garcia-Molina(1982)提出的當(dāng)一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請(qǐng)求時(shí)，它就發(fā)起選舉。進(jìn)程P負(fù)責(zé)選舉如下：P向所有號(hào)碼比它大的進(jìn)程發(fā)送選舉(ELECTION)消息。若無人響應(yīng)，P獲勝成為協(xié)調(diào)者。若有號(hào)碼比它大的進(jìn)程響應(yīng)，響應(yīng)者接管，P的工作完成。93五、選舉算法--1.欺負(fù)（Bully）算法1

由Garcia五、選舉算法--1.欺負(fù)（Bully）算法2

在某一時(shí)刻，一個(gè)進(jìn)程只能從號(hào)碼比它小的進(jìn)程那里得到一個(gè)選舉（ELECTION）消息，當(dāng)它到達(dá)時(shí)，接收者就發(fā)送回OK消息，表明它的存在并接管，然后接收者主持選舉（除非它正在主持別的選舉）。除了一個(gè)進(jìn)程外的其余進(jìn)程都得放棄，這一個(gè)進(jìn)程就是新的協(xié)調(diào)者，它把選舉獲勝的消息發(fā)送給所有進(jìn)程，告之它是新的協(xié)調(diào)者。若一個(gè)進(jìn)程剛剛崩潰過，而又得到恢復(fù)，它也有選舉權(quán)，若它剛好是當(dāng)前運(yùn)行進(jìn)程中號(hào)碼最大的，它就會(huì)獲得選舉的勝利，從而接管協(xié)調(diào)者的工作，所以最大的進(jìn)程總能取勝，故而將該算法命名為欺負(fù)算法。94五、選舉算法--1.欺負(fù)（Bully）算法2

在某一時(shí)刻，一五、選舉算法--1.欺負(fù)（Bully）算法3

95五、選舉算法--1.欺負(fù)（Bully）算法3

95五、選舉算法—2.環(huán)算法1

基于沒有令牌的環(huán)，假設(shè)所有的進(jìn)程是按物理或邏輯排序的，每一個(gè)進(jìn)程都知道誰是它的后繼者。當(dāng)任何一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時(shí)，它就構(gòu)造一個(gè)包含它自身進(jìn)程號(hào)的選舉消息發(fā)送給它的后繼者，如果后繼者失效，消息將繞過后繼者，到達(dá)后繼者的后繼者，或者再下一個(gè)，直到找到一個(gè)運(yùn)行進(jìn)程。每次接收者都把自己的進(jìn)程號(hào)加入到消息表中。最后，消息到達(dá)了始發(fā)者的手中，始發(fā)者接受到包括自己進(jìn)程號(hào)的消息后，將消息的類型轉(zhuǎn)化為協(xié)調(diào)者消息，該消息將再一次繞環(huán)運(yùn)行，向所有的進(jìn)程通知誰是協(xié)調(diào)者（在成員表中進(jìn)程號(hào)碼最大的那個(gè)）和新的環(huán)成員。當(dāng)消息循環(huán)一周后，被去掉，每個(gè)進(jìn)程都恢復(fù)工作。96五、選舉算法—2.環(huán)算法1

基于沒有令牌的環(huán)，假設(shè)所有的進(jìn)程五、選舉算法—2.環(huán)算法2

進(jìn)程2和進(jìn)程5同時(shí)發(fā)現(xiàn)協(xié)調(diào)者7失效兩條消息沿環(huán)運(yùn)動(dòng)，消息中有完全一樣的成員，相對(duì)順序也相同，當(dāng)兩條消息再繞環(huán)一周時(shí)，都被去掉。有多余的消息循環(huán)沒有壞處，最多是浪費(fèi)了一點(diǎn)帶寬。97五、選舉算法—2.環(huán)算法2

進(jìn)程2和進(jìn)程5同時(shí)發(fā)現(xiàn)協(xié)調(diào)者7失2.5原子事務(wù)處理

迄今為止研究的所有同步技術(shù)在其本質(zhì)上來說都是處于底層的，比如信號(hào)量。這些技術(shù)需要程序員密切注意互斥、臨界區(qū)管理、死鎖預(yù)防、崩潰恢復(fù)等問題的細(xì)節(jié)。需要的是更高層次的抽象，也就是隱藏技術(shù)問題，允許程序員將精力集中在算法和進(jìn)程如何并行運(yùn)行上。這樣的抽象是存在的，而且被廣泛應(yīng)用在分布式系統(tǒng)中。我們稱其為原子事務(wù)，或簡(jiǎn)稱為事務(wù)。術(shù)語原子操作也被廣泛使用。982.5原子事務(wù)處理

迄今為止研究的所有同步技術(shù)在其本質(zhì)上來2.5原子事務(wù)處理

2.5.1原子事務(wù)簡(jiǎn)介2.5.2事務(wù)模型2.5.3實(shí)現(xiàn)992.5原子事務(wù)處理

2.5.1原子事務(wù)簡(jiǎn)介992.5.1原子事務(wù)簡(jiǎn)介

原子事務(wù)的最初模型來源于商業(yè)社會(huì)。計(jì)算機(jī)模型有些類似。一個(gè)進(jìn)程宣布它想同其他的一個(gè)或幾個(gè)進(jìn)程開始一個(gè)事務(wù)。它們可以就不同的選擇進(jìn)行協(xié)商、創(chuàng)建、刪除對(duì)象，執(zhí)行一段時(shí)間的操作。然后發(fā)起者宣布它希望其它進(jìn)程能保證任務(wù)完成。如果其它進(jìn)程都同意，那么就達(dá)成了永久的協(xié)議。如果有一個(gè)或幾個(gè)進(jìn)程拒絕（或在同意前崩潰），那么就會(huì)返回到事務(wù)開始前的狀態(tài)。這時(shí)對(duì)象，文件，數(shù)據(jù)庫等方面的副作用都會(huì)神奇地消失。這種要么全有要么全無的特性簡(jiǎn)化了程序員的工作。1002.5.1原子事務(wù)簡(jiǎn)介

原子事務(wù)的最初模型來源于商業(yè)社會(huì)。2.5.1原子事務(wù)簡(jiǎn)介（續(xù)）

計(jì)算機(jī)系統(tǒng)中對(duì)事務(wù)的使用可以回溯到20世紀(jì)60年代。這種設(shè)計(jì)的最大優(yōu)點(diǎn)：對(duì)任何原因引起的運(yùn)行錯(cuò)誤，所有的磁帶都可以倒卷(rewound)，其工作可以毫無損失的重新開始。老式的磁帶系統(tǒng)具有了原子事務(wù)要么全有要么全無的特性。1012.5.1原子事務(wù)簡(jiǎn)介（續(xù)）

計(jì)算機(jī)系統(tǒng)中對(duì)事務(wù)的使用可以2.5.1原子事務(wù)簡(jiǎn)介（續(xù)）

當(dāng)前如何在線更新數(shù)據(jù)庫的銀行應(yīng)用的例子?？蛻敉ㄟ^帶有調(diào)制解調(diào)器的PC機(jī)連接到銀行，想將一個(gè)帳戶下的錢取出再存入另一帳戶。操作通過下面兩步執(zhí)行：提?。ń痤~，帳戶1）。存入（金額，帳戶2）。如果電話連接在第一步之后第二步之前中斷，那么第一個(gè)帳戶已被取出而第二個(gè)帳戶卻沒有存入。錢就消失在了未知的空間中。將這兩個(gè)操作組成一個(gè)原子事務(wù)可以解決這個(gè)問題。要么兩個(gè)都執(zhí)行，要么一個(gè)也不執(zhí)行。關(guān)鍵是事務(wù)執(zhí)行失敗后能返回到最初狀態(tài)。這種能力是原子事務(wù)必須提供的。1022.5.1原子事務(wù)簡(jiǎn)介（續(xù)）

當(dāng)前如何在線更新數(shù)據(jù)庫的銀行2.5.2事務(wù)模型事務(wù)模型提出前的一些假設(shè)：假設(shè)系統(tǒng)由一些相互獨(dú)立的進(jìn)程組成，每個(gè)進(jìn)程都會(huì)隨機(jī)出錯(cuò)。假定通信錯(cuò)誤已經(jīng)被底層軟件透明地處理盡管通信一般來說是不太可靠的，消息會(huì)丟失，但是底層可以采用超時(shí)重發(fā)協(xié)議恢復(fù)丟失的消息。1032.5.2事務(wù)模型事務(wù)模型提出前的一些假設(shè)：103一、穩(wěn)定存儲(chǔ)器存儲(chǔ)器有三種分類。第一種是普通的RAM存儲(chǔ)器，當(dāng)電源出錯(cuò)或機(jī)器崩潰時(shí)會(huì)丟失信息。第二種是磁盤存儲(chǔ)器，它不受CPU錯(cuò)的影響，但磁頭錯(cuò)會(huì)導(dǎo)致信息丟失。最后一種是穩(wěn)定存儲(chǔ)器(stablestorage)。它不受洪水地震之類大災(zāi)難之外的任何其它錯(cuò)誤的影響。104一、穩(wěn)定存儲(chǔ)器存儲(chǔ)器有三種分類。104穩(wěn)定存儲(chǔ)器的實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器可以通過兩個(gè)普通磁盤來實(shí)現(xiàn)。如圖所示，驅(qū)動(dòng)器2上的每一塊是驅(qū)動(dòng)器1上相應(yīng)塊的精確拷貝。當(dāng)更新一個(gè)塊時(shí)，首先更新并檢查驅(qū)動(dòng)器1上的塊，然后驅(qū)動(dòng)器2上的塊。105穩(wěn)定存儲(chǔ)器的實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器可以通過兩個(gè)普通磁盤來實(shí)現(xiàn)。105系統(tǒng)崩潰的恢復(fù)假設(shè)系統(tǒng)在更新驅(qū)動(dòng)器1之后更新驅(qū)動(dòng)器2之前崩潰，如圖b。在恢復(fù)時(shí)，磁盤可以一塊一塊地進(jìn)行比較，當(dāng)兩個(gè)相應(yīng)塊不一致時(shí)，可以假定驅(qū)動(dòng)器1是正確的（因?yàn)轵?qū)動(dòng)器1總是先于驅(qū)動(dòng)器2更新），因此將新塊從驅(qū)動(dòng)器1拷貝到驅(qū)動(dòng)器2。當(dāng)恢復(fù)過程完成后，兩個(gè)驅(qū)動(dòng)器又一致了。106系統(tǒng)崩潰的恢復(fù)假設(shè)系統(tǒng)在更新驅(qū)動(dòng)器1之后更新驅(qū)動(dòng)器2之前崩潰磁盤塊自然損壞后的恢復(fù)另一個(gè)潛在的問題是磁盤塊的自然損壞。垃圾微?；蛘咭话愕哪p和破裂都將使一個(gè)以前正確的磁盤塊會(huì)無緣無故或沒有警告地出現(xiàn)奇偶校驗(yàn)錯(cuò)，如圖c所示。當(dāng)檢測(cè)到這樣的錯(cuò)誤時(shí)，壞塊可以通過另一臺(tái)驅(qū)動(dòng)器上的相應(yīng)塊恢復(fù)。107磁盤塊自然損壞后的恢復(fù)另一個(gè)潛在的問題是磁盤塊的自然損壞。1一、穩(wěn)定存儲(chǔ)器（續(xù)）實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器的價(jià)值：它很適合于需要高度容錯(cuò)的應(yīng)用，例如原子事務(wù)。當(dāng)數(shù)據(jù)寫入穩(wěn)定存儲(chǔ)器并讀出以檢驗(yàn)它們是否正確寫入時(shí)，它們相繼丟失的機(jī)會(huì)非常小。108一、穩(wěn)定存儲(chǔ)器（續(xù)）實(shí)現(xiàn)穩(wěn)定存儲(chǔ)器的價(jià)值：108二、事務(wù)原語

使用事務(wù)編程需要由操作系統(tǒng)提供或者由語言運(yùn)行系統(tǒng)提供特殊原語，例如：BEGIN_TRANSACTION：標(biāo)記一個(gè)事務(wù)的開始。END_TRANSACTION：結(jié)束事務(wù)并設(shè)法提交。ABORT_TRANSACTION：取消事務(wù)；恢復(fù)舊值。READ：從一個(gè)文件（或其它對(duì)象）讀取數(shù)據(jù)。WRITE：將數(shù)據(jù)寫入一個(gè)文件（或其它對(duì)象）。109二、事務(wù)原語

使用事務(wù)編程需要由操作系統(tǒng)提供或者由語言運(yùn)行系二、事務(wù)原語（續(xù)）

更精確的原語列表取決于事務(wù)中正在使用的對(duì)象類型。在一個(gè)郵件系統(tǒng)中，可能有發(fā)送、接收以及轉(zhuǎn)發(fā)郵件等原語。而在一個(gè)帳目系統(tǒng)中可能會(huì)有很大的不同。讀取和寫入?yún)s是典型的應(yīng)用。在一個(gè)事務(wù)中，也允許使用普通語句、過程調(diào)用等。110二、事務(wù)原語（續(xù)）

更精確的原語列表取決于事務(wù)中正在使用的二、事務(wù)原語（續(xù)）——事務(wù)體

BEGIN_TRANSACTION和END_TRANSACTION用來限定事務(wù)的范圍。介于它們之間的操作構(gòu)成了事務(wù)體。這些操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行。這些操作可能是系統(tǒng)調(diào)用，庫過程，或者是某種語言中用括號(hào)括起來的語句，這取決于實(shí)現(xiàn)的需要。111二、事務(wù)原語（續(xù)）——事務(wù)體

BEGIN_TRANSACT二、事務(wù)原語-例子考慮到保定火車站買一張從保定到汕頭的火車。由于沒有直達(dá)火車，只能買聯(lián)票。保定石家莊；石家莊廣州；廣州汕頭。下面通過3個(gè)操作預(yù)定了這3條獨(dú)立的路線的座票。

BEGIN_TRANSACTION reserve保定-石家莊 reserve石家莊-廣州 reserve廣州-汕頭 END_TRANSACTION112二、事務(wù)原語-例子考慮到保定火車站買一張從保定到汕頭的火車。二、事務(wù)原語-例子（續(xù)）現(xiàn)在假設(shè)前兩條路線已經(jīng)預(yù)定成功，但是第三條已經(jīng)定滿了。那么事務(wù)就會(huì)因此而中止，前兩個(gè)預(yù)定的結(jié)果也將被取消——售票系統(tǒng)的數(shù)據(jù)庫恢復(fù)到了事務(wù)開始前的狀態(tài)，就像什么也沒有發(fā)生一樣。BEGIN_TRANSACTION reserve保定-石家莊 reserve石家莊-廣州 廣州-汕頭full→ABORT_TRANSACTIONEND_TRANSACTION113二、事務(wù)原語-例子（續(xù)）現(xiàn)在假設(shè)前兩條路線已經(jīng)預(yù)定成功，但是三、事務(wù)的特性

事務(wù)有四個(gè)重要的特性，它們是：原子性(Atomic)：對(duì)外部世界來說，事務(wù)的發(fā)生是不可分割的。一致性(Consistent)：事務(wù)不會(huì)破壞系統(tǒng)的恒定。獨(dú)立性(Isolated)：并發(fā)的事務(wù)不會(huì)互相干擾。持久性(Durable)：一旦一個(gè)事務(wù)提交，改變就是永遠(yuǎn)存在的。這幾個(gè)屬性通常按其首字母簡(jiǎn)稱為ACID。114三、事務(wù)的特性

事務(wù)有四個(gè)重要的特性，它們是：114原子性所有事務(wù)具有的第一個(gè)特性是原子性。這個(gè)特性確保了每個(gè)事務(wù)要么全部發(fā)生，要么全部不發(fā)生。如果發(fā)生，就是不可分割的，瞬間的操作。當(dāng)一個(gè)事務(wù)處在處理過程中時(shí)，其它進(jìn)程（無論是否與事務(wù)有關(guān)）都不能看到任何中間狀態(tài)。115原子性所有事務(wù)具有的第一個(gè)特性是原子性。115原子性—例假設(shè)某個(gè)事務(wù)要在一個(gè)10字節(jié)的文件末尾添加數(shù)據(jù)。如果在事務(wù)處理過程中其它進(jìn)程讀取了這個(gè)文件，那么無論該事務(wù)已添加了多少內(nèi)容，那些進(jìn)程看到的只能是10個(gè)字節(jié)。如果事務(wù)成功結(jié)束，這時(shí)文件在結(jié)束的瞬時(shí)增長(zhǎng)到了新的大小，無論有多少個(gè)操作存在，都不會(huì)有中間狀態(tài)。116原子性—例假設(shè)某個(gè)事務(wù)要在一個(gè)10字節(jié)的文件末尾添加數(shù)據(jù)。1一致性

第二個(gè)特性說明事務(wù)是一致的，這意味著如果系統(tǒng)擁有某種必須經(jīng)常保持的不變性，那么一旦在事務(wù)開始之前保持有這樣的性質(zhì)，則事務(wù)結(jié)束后該性質(zhì)就還應(yīng)該存在。例如在一個(gè)銀行系統(tǒng)中，最關(guān)鍵的不變性是資金守恒規(guī)則。在任何內(nèi)部轉(zhuǎn)帳之后，銀行的資金帳目應(yīng)與轉(zhuǎn)帳前保持一致，但是在事務(wù)執(zhí)行的短暫時(shí)刻內(nèi)，這種不變性會(huì)受到損害。然而事務(wù)結(jié)束之后，這種損害就沒有了。117一致性

第二個(gè)特性說明事務(wù)是一致的，這意味著如果系統(tǒng)擁有某獨(dú)立性

第三個(gè)特性說明事務(wù)是獨(dú)立的或連續(xù)的。這意味著如果兩個(gè)或兩個(gè)以上的事務(wù)在同時(shí)運(yùn)行，那么對(duì)它們自己和其它進(jìn)程來說，最終結(jié)果看起來就象是所有的事務(wù)是按某種次序（依賴于系統(tǒng)）順序運(yùn)行的。118獨(dú)立性

第三個(gè)特性說明事務(wù)是獨(dú)立的或連續(xù)的。118獨(dú)立性—例下面三個(gè)事務(wù)被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行。如果它們順序執(zhí)行，那么X的最終結(jié)果應(yīng)該是1，2或3，取決于哪一個(gè)事務(wù)最后運(yùn)行（X可以是一個(gè)共享變量，一個(gè)文件或其他對(duì)象）。119獨(dú)立性—例下面三個(gè)事務(wù)被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行。119獨(dú)立性—例在d中我們看到了稱之為調(diào)度表的不同次序，其中事務(wù)可以是交錯(cuò)的。調(diào)度1是真正串行的，即事務(wù)嚴(yán)格按順序來運(yùn)行，因此它滿足連續(xù)性的定義。調(diào)度2不是串行的，但是它也是合法的，因?yàn)樗祷氐腦值與嚴(yán)格串行返回的值一致。第三個(gè)調(diào)度是非法的，因?yàn)樗鼘的值置成了5，這是順序執(zhí)行所不可能產(chǎn)生的。120獨(dú)立性—例在d中我們看到了稱之為調(diào)度表的不同次序，其中事務(wù)可獨(dú)立性（續(xù)）為保證獨(dú)立的操作正確交替執(zhí)行是系統(tǒng)的責(zé)任。通過給予系統(tǒng)按照自己需要選擇操作執(zhí)行順序的自由——假設(shè)它得到的答案是正確的——我們消除了程序員自己進(jìn)行互斥處理的需要，因此簡(jiǎn)化了編程。121獨(dú)立性（續(xù)）為保證獨(dú)立的操作正確交替執(zhí)行是系統(tǒng)的責(zé)任。121持久性

第四個(gè)特性說明事務(wù)是持久的。這是指這樣一個(gè)事實(shí)，即一旦一個(gè)事務(wù)提交，無論發(fā)生什么，這個(gè)事務(wù)都會(huì)向前進(jìn)行，結(jié)果不會(huì)再變了。提交之后發(fā)生的任何錯(cuò)誤都不可能使結(jié)果取消或丟失。

122持久性

第四個(gè)特性說明事務(wù)是持久的。122四、嵌套事務(wù)

事務(wù)可以包含子事務(wù)，這通常稱作嵌套事務(wù)。頂層事務(wù)可以在不同的處理機(jī)上創(chuàng)建并行運(yùn)行的子事務(wù)，以提高性能、簡(jiǎn)化編程。這些子事務(wù)中的任何一個(gè)都可以執(zhí)行一個(gè)或多個(gè)子事務(wù)，或者創(chuàng)建自己的子事務(wù)。123四、嵌套事務(wù)

事務(wù)可以包含子事務(wù)，這通常稱作嵌套事務(wù)。123四、嵌套事務(wù)（續(xù)）

子事務(wù)引起的問題：假設(shè)一個(gè)事務(wù)啟動(dòng)了幾個(gè)并行的子事務(wù)，其中一個(gè)已經(jīng)提交，其操作結(jié)果在父事務(wù)中已經(jīng)生效。經(jīng)過更進(jìn)一步的計(jì)算，父事務(wù)被終止，并將系統(tǒng)恢復(fù)到了頂層事務(wù)開始前的狀態(tài)。結(jié)果，已經(jīng)提交了的子事務(wù)的結(jié)果也必須被恢復(fù)。于是上面提到的的持久性只是對(duì)頂層事務(wù)而言。持久性：提交之后發(fā)生的任何錯(cuò)誤都不可能使結(jié)果取消或丟失。124四、嵌套事務(wù)（續(xù)）

子事務(wù)引起的問題：124四、嵌套事務(wù)（續(xù)）

由于事務(wù)可以嵌套任意多層，因此需要管理措施以使其一切正常。但語義卻是清楚的。當(dāng)任何事務(wù)或子事務(wù)開始的時(shí)候，在概念上給予它一個(gè)整個(gè)系統(tǒng)全部對(duì)象的私有拷貝，可以按照其意愿進(jìn)行操作。如果事務(wù)被終止，那么它的私有空間就會(huì)消失，就象事務(wù)從來都沒有存在過一樣。如果事務(wù)提交了，那么它的私有空間就會(huì)取代父輩的空間。因此如果一個(gè)子事務(wù)提交后又開始了一個(gè)新的子事務(wù)，那么它就可以看到第一個(gè)子事務(wù)的結(jié)果了。125四、嵌套事務(wù)（續(xù)）

由于事務(wù)可以嵌套任意多層，因此需要管理2.5.3實(shí)現(xiàn)

如果每個(gè)進(jìn)程執(zhí)行一個(gè)事務(wù)僅僅只是更新它自己使用的對(duì)象（文件、數(shù)據(jù)庫記錄等），那么事務(wù)就不會(huì)是原子的，而且事務(wù)異常終止時(shí)它所作的更改也不會(huì)神奇的消失。此外，運(yùn)行多個(gè)事務(wù)時(shí)也不會(huì)是串行的。顯然，需要其它的實(shí)現(xiàn)方法。經(jīng)常使用的有兩種方法：私有工作空間寫前日志1262.5.3實(shí)現(xiàn)

如果每個(gè)進(jìn)程執(zhí)行一個(gè)事務(wù)僅僅只是更新它自己使一、私有