【文章內(nèi)容簡(jiǎn)介】 1）網(wǎng)絡(luò)上的每個(gè)系統(tǒng)（站點(diǎn)）維護(hù)一個(gè)計(jì)數(shù)器，起時(shí)鐘的作用（2）每個(gè)站點(diǎn)有一個(gè)數(shù)字型標(biāo)識(shí)，消息的格式為（m,Ti,i），m為消息內(nèi)容， Ti為時(shí)間戳，i為站點(diǎn)標(biāo)識(shí)（3）當(dāng)系統(tǒng)發(fā)送消息時(shí)，將時(shí)鐘加一（4）當(dāng)系統(tǒng)j接收消息時(shí)，將它的時(shí)鐘設(shè)為當(dāng)前值和到達(dá)的時(shí)間戳這兩者的最大者加一（5）在每個(gè)站點(diǎn)，時(shí)間的排序遵循以下規(guī)則：對(duì)來(lái)自站點(diǎn)i的消息x和站點(diǎn)j的消息y，如果TiTj或Ti=Tj，且ij則說(shuō)消息x早于消息y（哪個(gè)事件在實(shí)際上首先發(fā)生并不重要，重要的是所有進(jìn)程對(duì)事件的發(fā)生順序意見(jiàn)一致）2. 全局狀態(tài)全局狀態(tài)定義了每個(gè)進(jìn)程的本地狀態(tài)和正在傳輸中的消息，使用分布式快照算法。分布式快照反映了該系統(tǒng)可能處于的狀態(tài)，它的基本思想是，每個(gè)進(jìn)程記錄它的狀態(tài)，對(duì)每個(gè)進(jìn)入通道來(lái)記錄發(fā)送給它的消息。對(duì)每個(gè)通道，進(jìn)程記錄在它自己記錄下?tīng)顟B(tài)后和在發(fā)送方記錄下它自己狀態(tài)之前到達(dá)的任何消息?？梢杂们锌诘膱D示表示，如下圖：a 一致的切口b 不一致的切口3. 選舉算法中Bully算法的思想當(dāng)進(jìn)程P注意到需要選舉一個(gè)進(jìn)程作協(xié)調(diào)者時(shí)：（1）向所有進(jìn)程號(hào)比它高的進(jìn)程發(fā)ELECTION消息（2）如果得不到任何進(jìn)程的響應(yīng)，進(jìn)程P獲勝，成為協(xié)調(diào)者（3）如果有進(jìn)程號(hào)比它高的進(jìn)程響應(yīng)，該進(jìn)程接管選舉過(guò)程，進(jìn)程P任務(wù)完成（4）當(dāng)其他進(jìn)程都放棄，只剩一個(gè)進(jìn)程時(shí)，該進(jìn)程成為協(xié)調(diào)者（5）一個(gè)以前被中止的進(jìn)程恢復(fù)后也有選舉權(quán)（a）進(jìn)程 4 啟動(dòng)選舉（b）進(jìn)程 5 和進(jìn)程 6 響應(yīng)（c）進(jìn)程5和6接管選舉，成為協(xié)調(diào)者（d）進(jìn)程 6 響應(yīng)進(jìn)程 5 的消息，接管選舉（e）進(jìn)程 6 成為協(xié)調(diào)者，通知所有進(jìn)程4. 選舉算法中環(huán)算法的思想。不使用令牌；按進(jìn)程號(hào)排序，每個(gè)進(jìn)程都知道自己的后繼者；進(jìn)程P注意到需要選舉一個(gè)進(jìn)程作協(xié)調(diào)者時(shí)：（1）創(chuàng)建一條包含該進(jìn)程號(hào)的ELECTION消息，發(fā)給后繼進(jìn)程（2）后繼進(jìn)程再將自己的進(jìn)程號(hào)加入ELECTION消息，依次類(lèi)推（3）最后回到進(jìn)程P，它再發(fā)送一條COORDINATOR消息到環(huán)上，包含新選出的協(xié)調(diào)者進(jìn)程（進(jìn)程號(hào)最大者）和所有在線進(jìn)程5. 無(wú)線環(huán)境下的選舉算法。無(wú)線環(huán)境下不能保證其消息傳送是可靠的以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不改變（1）源節(jié)點(diǎn)向其相鄰節(jié)點(diǎn)發(fā)送ELECTION消息開(kāi)始一個(gè)選舉（2）當(dāng)節(jié)點(diǎn)第一次收到ELECTION消息時(shí)，會(huì)將發(fā)送者作為其父節(jié)點(diǎn)，然后將ELECTION消息發(fā)給其相鄰節(jié)點(diǎn)（父節(jié)點(diǎn)除外）。等到其他節(jié)點(diǎn)的確認(rèn)消息都收到后，再向父節(jié)點(diǎn)確認(rèn)（消息中包含資源容量）。（3）而從某個(gè)節(jié)點(diǎn)再次收到ELECTION消息時(shí)，只是確認(rèn)。6. 分布式互斥算法（1）當(dāng)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，它向所有其他進(jìn)程發(fā)一條打了時(shí)間戳的消息Request（2）當(dāng)收到所有其他進(jìn)程的Reply消息時(shí)，就可以進(jìn)入臨界區(qū)了（3）當(dāng)一個(gè)進(jìn)程收到一條Request消息時(shí)，必須返回一條Reply消息：1）如該進(jìn)程自己不想進(jìn)入臨界區(qū)，則立即發(fā)送Reply消息2）如該進(jìn)程想進(jìn)入臨界區(qū)，則把自己的Request消息時(shí)間戳與收到的Request消息時(shí)間戳相比較，如自己的晚，則立即發(fā)送Reply消息；否則，就推遲發(fā)送Reply消息 進(jìn)程 0 和 2 都想進(jìn)入臨界區(qū) 進(jìn)程 0 的時(shí)間戳低， 搶先進(jìn)入臨界區(qū) 進(jìn)程 0 退出臨界區(qū)后，發(fā)應(yīng)答給進(jìn)程2， 進(jìn)程2 隨后進(jìn)入臨界區(qū)7. 實(shí)現(xiàn)事務(wù)的方法（1）私有工作空間1）為進(jìn)程提供一個(gè)私有工作空間，包含進(jìn)程要訪問(wèn)的所有對(duì)象2）進(jìn)程的讀寫(xiě)操作在私有工作空間進(jìn)行，而不對(duì)實(shí)際的文件系統(tǒng)進(jìn)行3）開(kāi)銷(xiāo)大，可以進(jìn)行優(yōu)化使之可行，如讀操作不復(fù)制，寫(xiě)操作時(shí)復(fù)制，而且初始只復(fù)制索引（包含文件磁盤(pán)塊的位置信息，如UNIX的i節(jié)點(diǎn)）（如果事務(wù)中止，私有工作空間被釋放，指向的私有塊被刪除；如果事務(wù)提交，私有索引被移到父輩空間，不再被訪問(wèn)的塊被釋放掉） 包含三個(gè)塊的文件及其索引 塊0被修改，塊3被添加后的情況事務(wù)提交之后（2）寫(xiě)前日志（write ahead log）：先寫(xiě)日志，再做實(shí)際修改1）日志內(nèi)容：哪個(gè)事務(wù)在對(duì)文件進(jìn)行修改，哪個(gè)文件和數(shù)據(jù)被改動(dòng)，新值和舊值是什么…2）日志寫(xiě)入后，改動(dòng)才被寫(xiě)入文件3）事務(wù)中止，使用寫(xiě)前日志回退到原來(lái)的狀態(tài)4）借助穩(wěn)定存儲(chǔ)器中的寫(xiě)前日志：當(dāng)系統(tǒng)崩潰后，完成事務(wù)或取消事務(wù)x = 0。y = 0。BEGIN_TRANSACTION。 x = x + 1。 y = y + 2 x = y * y。END_TRANSACTION。 (a) 一個(gè)事務(wù)Log[x = 0/1] (b)Log[x = 0/1][y = 0/2] (c) Log[x = 0/1][y = 0/2][x = 1/4] (d)（b）（c）語(yǔ)句執(zhí)行前的日志8. 死鎖預(yù)防的等死算法和傷等算法（1）等死算法:若一個(gè)老事務(wù)想得到一個(gè)正被新事務(wù)占用的資源，那么它會(huì)很禮貌的等待。反之，若一個(gè)新事務(wù)想得到一個(gè)被老事務(wù)占用的資源，它將被中止。盡管它還會(huì)重新開(kāi)始，但很可能又會(huì)立即被中止。在老事務(wù)釋放資源之前，這個(gè)循環(huán)可能要重復(fù)多次。（2）傷等算法允許搶占，只允許老進(jìn)程搶占新進(jìn)程。若一個(gè)老進(jìn)程希望得到一個(gè)被新進(jìn)程占用的資源，那么老進(jìn)程將會(huì)搶占，于是新事務(wù)被中止，如a所示。隨后新事務(wù)可能會(huì)立即重新開(kāi)始，并試著請(qǐng)求資源，如b所示，然后被迫等待。9. 集中式的死鎖檢測(cè)中的假死鎖問(wèn)題（1）集中式的死鎖檢測(cè)算法1）每臺(tái)機(jī)器都有一幅資源圖以描述自己所擁有的進(jìn)程和資源2）有一臺(tái)中心機(jī)器擁有整個(gè)系統(tǒng)（所有資源圖的集合）的資源圖3）當(dāng)協(xié)調(diào)者檢測(cè)到了環(huán)路時(shí)它就中止一個(gè)進(jìn)程以解決死鎖（2）假死鎖舉例 1）A和B進(jìn)程運(yùn)行在機(jī)器0上，C運(yùn)行在機(jī)器1上，共有三種資源S，R，和T。如圖，開(kāi)始A擁有S并想請(qǐng)求R，但B正在使用R，C擁有T并想請(qǐng)求S。圖c為協(xié)調(diào)者看到的情況。2）這種配置是安全的，一旦B結(jié)束運(yùn)行，A就可以得到R然后結(jié)束，并釋放C所等待的S。過(guò)一會(huì)，B釋放R并請(qǐng)求T，這是一個(gè)完全合法的安全操作。3）機(jī)器0向協(xié)調(diào)者發(fā)送一條消息聲明它釋放R，機(jī)器1向協(xié)調(diào)者發(fā)送了一條消息聲明進(jìn)程B正在等待它的資源T。4）不幸的是，機(jī)器1的消息首先到達(dá)，這導(dǎo)致協(xié)調(diào)者生成了一副如圖d所示的資源圖，根據(jù)其信息，協(xié)調(diào)者將錯(cuò)誤的得出死鎖存在的結(jié)論，并中止某個(gè)進(jìn)程。這種情況稱(chēng)為假死鎖。5）由于信息的不完整和延遲，使得分布式系統(tǒng)中的許多死鎖算法產(chǎn)生了類(lèi)似的假死鎖問(wèn)題。10. 分布式的死鎖檢測(cè)ChandyMisraHaas算法的思想當(dāng)某個(gè)進(jìn)程等待資源時(shí)，例如P0等待P1，將調(diào)用ChandyMisraHaas算法。（1）生成一個(gè)探測(cè)消息并發(fā)送給占用資源的進(jìn)程。1）消息由三個(gè)數(shù)字構(gòu)成：阻塞的進(jìn)程，發(fā)送消息的進(jìn)程，接受消息的進(jìn)程。2）由P0到P1的初始消息包含三元組（0，0，1）。（2）消息到達(dá)后，接受者檢查以確認(rèn)它自己是否也在等待其他進(jìn)程。1）若是，就更新消息，字段1保持不變，字段2改成當(dāng)前進(jìn)程號(hào)，字段3改為等待的進(jìn)程號(hào)。2）然后消息接著被發(fā)送到等待的進(jìn)程。3）若存在多個(gè)等待進(jìn)程，就要發(fā)送多個(gè)不同的消息。（3）不論資源在本地還是在遠(yuǎn)程，該算法一直繼續(xù)下去。1）圖中（0，2，3），（0，4，6），（0，5，7）和（0，8，0）都是遠(yuǎn)程消息。