1、同同 步步SynchronizationChapter 5第五章第五章 同同 步步 與進(jìn)程及進(jìn)程間通信緊密相關(guān)的問(wèn)題是進(jìn)程間如何協(xié)作和同步。 多個(gè)進(jìn)程不能同時(shí)訪(fǎng)問(wèn)一個(gè)共享資源，而是相互協(xié)作，彼此授權(quán)暫時(shí)地獨(dú)占訪(fǎng)問(wèn)。 多個(gè)進(jìn)程有時(shí)可能需要就事件的順序達(dá)成一致，比方說(shuō)來(lái)自進(jìn)程P的消息m1是在來(lái)自進(jìn)程Q的消息m2之前或是之后被發(fā)送出去。同 步 分布式系統(tǒng)的同步比單處理器系統(tǒng)或多處理器系統(tǒng)的同步更加困難，本章主要討論同步的問(wèn)題及其解決方法。 與同步相關(guān)的兩個(gè)主題是分布式系統(tǒng)中的互斥和分布式事務(wù)。分布式互斥保護(hù)共享資源不被多個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)。分布式事務(wù)也作類(lèi)似的事情，但是他通過(guò)高級(jí)的并發(fā)控制機(jī)制來(lái)優(yōu)化訪(fǎng)問(wèn)

2、。Clock SynchronizationWhen each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time.物理時(shí)鐘 時(shí)鐘測(cè)量中存在誤差。 單機(jī)單時(shí)鐘中少許偏差不會(huì)有多大問(wèn)題，因?yàn)檫@臺(tái)機(jī)器上的所有進(jìn)程使用同一個(gè)時(shí)鐘，所以它們內(nèi)部仍然會(huì)保持一致。真正重要的是相對(duì)時(shí)間。 在分布式系統(tǒng)中不同的機(jī)器都有自己的時(shí)鐘，它們存在不同時(shí)鐘偏移，導(dǎo)致時(shí)鐘逐漸不同步。 需要在不同機(jī)器提供準(zhǔn)確時(shí)間。時(shí)間同步算法 可以采用WWV (短

3、波廣播站)接收器接收精確時(shí)間 如果一臺(tái)機(jī)器上有WWV接收器，那么我們需要使其他所有的機(jī)器與他同步。 如果沒(méi)有一臺(tái)機(jī)器器有WWV接收器，每臺(tái)機(jī)器都按自己的機(jī)時(shí)間計(jì)時(shí)，這時(shí)我們的目標(biāo)是盡可能使所有機(jī)器的時(shí)間保持同步。Cristians AlgorithmGetting the current time from a time server.發(fā)送請(qǐng)求者在得到應(yīng)答后，就將它的時(shí)鐘設(shè)為CUTC，有兩個(gè)問(wèn)題。問(wèn)題1：時(shí)間決不能倒退。 如果發(fā)送請(qǐng)求者的時(shí)鐘快，那么CUTC小于發(fā)送請(qǐng)求者的時(shí)間值C。問(wèn)題2：從時(shí)間服務(wù)器發(fā)送的應(yīng)答到達(dá)發(fā)送請(qǐng)求者需要花費(fèi)一定時(shí)間。然而更糟糕的是這種延遲可能較大，而且隨著網(wǎng)絡(luò)負(fù)載的

4、改變而改變。消息傳送時(shí)間的最佳估計(jì)值是(T1-T0-I)/2，當(dāng)應(yīng)答消息到達(dá)時(shí)，消息中的時(shí)間值加上此值就得到了時(shí)間服務(wù)器當(dāng)前時(shí)間的估計(jì)值。(當(dāng)前時(shí)間)（每臺(tái)機(jī)器定期向時(shí)間服務(wù)器發(fā)送消息詢(xún)問(wèn)當(dāng)前時(shí)間）Cristian算法（續(xù)） 適用于一臺(tái)機(jī)器有wwv接收器（時(shí)間服務(wù)器），其它機(jī)器都要與那臺(tái)機(jī)器同步的系統(tǒng)。 每臺(tái)機(jī)器以不大于/2秒周期定期向時(shí)間服務(wù)發(fā)送消息查詢(xún)當(dāng)前時(shí)間，時(shí)間服務(wù)器接到消息后就盡快發(fā)送含有當(dāng)前時(shí)間CUTC的消息來(lái)應(yīng)答。Cristian算法（續(xù)） 時(shí)鐘的改變必須逐步進(jìn)行。假設(shè)計(jì)時(shí)器每秒產(chǎn)生100次中斷。正常情況下，每次中斷將時(shí)間加10ms，需要慢時(shí)，中斷服務(wù)程序每次僅加9ms，需要快時(shí)

5、每次加11ms，直到調(diào)好為止。而不是立即將時(shí)間調(diào)到需要的值。 對(duì)延遲問(wèn)題可由發(fā)送者測(cè)量從向服務(wù)器發(fā)送請(qǐng)求到接收到應(yīng)答的時(shí)間間隔，進(jìn)行修正。The Berkeley Algorithma)The time daemon asks all the other machines for their clock valuesb) （時(shí)間守護(hù)程序定期地把他的時(shí)間告訴其他機(jī)器，并詢(xún)問(wèn)他們各自的時(shí)間）c)b) The machines answer（各臺(tái)機(jī)器將它們各自的時(shí)間與時(shí)間守護(hù)程序時(shí)間的差值告訴時(shí)間守護(hù)程序）d)c) The time daemon tells everyone how to adju

6、st their clock（基于這些值，時(shí)間守護(hù)程序計(jì)算出它們的平均值，并通知各臺(tái)機(jī)器如何調(diào)整各自的時(shí)鐘） 這種方法適合于沒(méi)有WWV接收器的系統(tǒng)。邏輯時(shí)鐘 在許多應(yīng)用中，只要所有的機(jī)器具有相同的時(shí)間就夠了，無(wú)須與真實(shí)時(shí)間相同。 重要的是時(shí)鐘的內(nèi)部一致性，而不是它們是否與真實(shí)時(shí)間接近。 通常重要的不是所有的進(jìn)程在時(shí)間上完全一致，而是它們?cè)谑录陌l(fā)生順序上要達(dá)成一致。Lamport時(shí)間戳 為了同步邏輯時(shí)鐘，Lamport定義了一個(gè)稱(chēng)作“先發(fā)生”的關(guān)系。表達(dá)式ab讀作“a在b之前發(fā)生”，這種先發(fā)生關(guān)系有兩種情況： （1）如果a和b是同一個(gè)進(jìn)程中的兩個(gè)事件，且a在b之前發(fā)生,則a b為真。 （2）

7、如果a是一個(gè)進(jìn)程發(fā)送消息的事件，而b為另一個(gè)進(jìn)程接收這個(gè)消息的事件，則ab也為真。 先發(fā)生關(guān)系是一個(gè)傳遞關(guān)系，所以若ab且bc, 則a c。 如果事件x和y發(fā)生在兩個(gè)互不交換消息的進(jìn)程中，那么x y不真，y x也同樣不真，稱(chēng)這兩個(gè)事件為并發(fā)的。Lamport時(shí)間戳 我們需要一種測(cè)量時(shí)間的方法，使得對(duì)于每個(gè)事件a，我們都能為他分配一個(gè)所有進(jìn)程都認(rèn)可的時(shí)間值C(a)。 這些時(shí)間值必須具有如下性質(zhì)：如果ab，那么C(a) C(b)。 另外，時(shí)鐘時(shí)間值C必須總是前進(jìn)（增加），不能倒退（減少）。校正時(shí)間的操作是給時(shí)間加上一個(gè)正值，而不能是減掉一個(gè)正值。 我們現(xiàn)在有了一個(gè)為分布式系統(tǒng)中的所有事件分配時(shí)間的

8、方法，它遵守下面的規(guī)則： （1）若在同一進(jìn)程中a在b之前發(fā)生，則C(a) C(b)。 （2）若a和b分別代表發(fā)送一個(gè)消息和接收該消息的事件， 則C(a) JFK; reserve JFK - Nairobi; reserve Nairobi - Malindi;END_TRANSACTION (a)BEGIN_TRANSACTION reserve WP - JFK; reserve JFK - Nairobi; reserve Nairobi - Malindi full =ABORT_TRANSACTION (b)事務(wù)的分類(lèi)1、單層事務(wù)：把事務(wù)看成是滿(mǎn)足ACID特性的一系列操作。如前面講的

9、訂三個(gè)航班的操作組織在一個(gè)事務(wù)中。單層事務(wù)的主要局限是它們不允許提交或取銷(xiāo)部分結(jié)果。2、嵌套事務(wù)：上面提到的局限性可以通過(guò)使用嵌套事務(wù)來(lái)解決。一個(gè)嵌套事務(wù)由許多子事務(wù)構(gòu)成?？梢允鬼攲邮聞?wù)分支為在不同的機(jī)器上并行運(yùn)行的子事務(wù)，以提高性能或簡(jiǎn)化編程。這些子事務(wù)中的任何一個(gè)都可以執(zhí)行一個(gè)或多個(gè)子事務(wù)，或者經(jīng)過(guò)分支擁有自己的子事務(wù)。3、分布式事務(wù)：一個(gè)單層事務(wù)需要處理分布在多臺(tái)機(jī)器上的數(shù)據(jù)。這種類(lèi)型的事務(wù)稱(chēng)為分布式事務(wù)。 嵌套事務(wù)和分布式事務(wù)之間的差別很微小。嵌套事務(wù)是一個(gè)按照邏輯關(guān)系分解成一層層子事務(wù)的事務(wù)。分布式事務(wù)邏輯上是一個(gè)單層的、不可分割的事務(wù)，它的操作對(duì)象是分布式的的數(shù)據(jù)。Distribu

10、ted Transactionsa)A nested transactionb)A distributed transaction事務(wù)的實(shí)現(xiàn)1、私有工作空間、私有工作空間原理：在一個(gè)進(jìn)程開(kāi)始一個(gè)事務(wù)時(shí)，它被分配一個(gè)私有工作空間，該空間包含所有它有權(quán)訪(fǎng)問(wèn)的文件，在事務(wù)提交或中止前，它的所有讀寫(xiě)操作都在私有空間進(jìn)行，而不是直接對(duì)文件系統(tǒng)進(jìn)行操作。 問(wèn)題：所有的東西都復(fù)制到私有空間的開(kāi)銷(xiāo)大。優(yōu)化方法：（1）當(dāng)進(jìn)程只是讀取一個(gè)文件而不對(duì)其他修改時(shí)，不復(fù)制，只是產(chǎn)生一個(gè)空私有工作空間。 （2）不復(fù)制整個(gè)文件，而是只將索引（判斷文件所在磁盤(pán)塊位置有關(guān)的數(shù)據(jù)塊）復(fù)制到私有工作空間。Private Works

11、pacea)The file index and disk blocks for a three-block fileb)The situation after a transaction has modified block 0 and appended block 3c)After committing2. Writeahead Log（寫(xiě)前日志）a) A transactionb) d) The log before each statement is executed 事務(wù)中的每條語(yǔ)句執(zhí)行前都要寫(xiě)入一條日志記錄x = 0;y = 0;BEGIN_TRANSACTION; x = x +

12、 1; y = y + 2 x = y * y;END_TRANSACTION; (a) Logx = 0 / 1 (b)Logx = 0 / 1y = 0/2 (c) Logx = 0 / 1y = 0/2x = 1/4 (d)記錄舊值和新值并發(fā)控制 并發(fā)控制的目的是允許幾個(gè)事務(wù)同時(shí)執(zhí)行，但是被操作的數(shù)據(jù)項(xiàng)集合（例如，文件或者數(shù)據(jù)庫(kù)記錄）要保持一致的狀態(tài)。 通過(guò)允許事務(wù)以某一特定的順序存取數(shù)據(jù)項(xiàng)，藉此使最后得到的結(jié)果跟事務(wù)順序執(zhí)行的一樣，從而實(shí)現(xiàn)這種一致性。Concurrency Control (1)General organization of managers for handling

13、 transactions.主要責(zé)任是保證事務(wù)的原子性, 它通過(guò)將事務(wù)原語(yǔ)轉(zhuǎn)化成調(diào)度器的調(diào)度請(qǐng)求來(lái)處理事務(wù)原語(yǔ)。主要任務(wù)是正確地控制并發(fā)。他決定哪個(gè)事務(wù)，在何時(shí)被允許將讀或?qū)懖僮鱾鹘o數(shù)據(jù)管理器。他完成對(duì)數(shù)據(jù)的讀寫(xiě)操作。數(shù)據(jù)管理器不關(guān)心哪個(gè)事務(wù)正在做讀或?qū)懖僮?。Concurrency Control (2)General organization of managers for handling distributed transactions.TransactionsSerializabilitya) c) Three transactions T1, T2, and T3d) Possibl

14、e schedulesBEGIN_TRANSACTION x = 0; x = x + 1;END_TRANSACTION (a)BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION (b)BEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION (c)Schedule 1x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3LegalSchedule 2x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x +

15、 3;LegalSchedule 3x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;Illegal(d)Two-Phase Locking (1)Two-phase locking.Two-Phase Locking (2)Strict two-phase locking.悲觀(guān)的時(shí)間戳排序 每一個(gè)事務(wù)T開(kāi)始時(shí)給它分配一個(gè)時(shí)間戳ts(T)，事務(wù)T的每個(gè)操作都被蓋上時(shí)間戳ts(T), 系統(tǒng)中每個(gè)數(shù)據(jù)項(xiàng)x都 有一個(gè)相關(guān)的讀時(shí)間戳tsRD(x), 寫(xiě)時(shí)間戳tsWR(x), (1) tsRD (x) 設(shè)置成最近讀x的事務(wù)的時(shí)間戳。 (2) tsWR (x) 是最近修改x的事務(wù)的時(shí)間戳。操作方式：1、假設(shè)事務(wù)T發(fā)出read(x) 操作 a.如果ts(T) tsWR (x), 則執(zhí)行讀操作。同時(shí)tsRD(x)被設(shè)置成 maxtsRD(x), ts(T)。2、假設(shè)事務(wù)T發(fā)出write(x)操作a.如果 ts(T) tsRD(x)，那么它改變x的值, 因?yàn)闆](méi)有更晚的事務(wù)讀過(guò)它。tsWR