分布式進程管理

分布式進程管理1第一頁，共七十頁，2022年，8月28日10.1進程遷移進程遷移就是將一個進程的狀態(tài)，從一臺機器(源機)轉(zhuǎn)移到另一臺機器(目標機)上，從而使該進程能在目標機上執(zhí)行。這個概念主要來自于對大量互連系統(tǒng)間負載平衡方法的研究，但其應用已超出了這個領域。2第二頁，共七十頁，2022年，8月28日10.1.1進程遷移的動機 進程遷移在分布式操作系統(tǒng)中很重要，主要有以下幾個原因：①負載共享。通過將進程從負載較重的節(jié)點遷移到負載較輕的節(jié)點，使系統(tǒng)負載達到平衡，從而提高整體執(zhí)行效率。②減少通信開銷?？梢詫⑾嗷ラg緊密作用的進程遷移到同一節(jié)點，以減少它們相互作用期間的通信耗費。③可獲得性。運行時間較長的進程在出現(xiàn)錯誤時可能需要遷移。那么，一個想繼續(xù)的進程既可以遷移到另外的系統(tǒng)，也可以推遲運行，待錯誤恢復后在當前系統(tǒng)中重新開始。④利用特定資源。3第三頁，共七十頁，2022年，8月28日10.1.2進程遷移機制

在設計一個進程遷移機制時要考慮許多問題，其中包括：①由誰來激發(fā)遷移？②進程的哪一部分被遷移?如何進行遷移？③如何處理未完成的消息和信號？4第四頁，共七十頁，2022年，8月28日10.1.2進程遷移機制1.遷移激發(fā) 由誰激發(fā)遷移取決于遷移機制的目的。若其目的在于負載平衡，那么，通常由操作系統(tǒng)中掌管系統(tǒng)負載的組件決定什么時候進行遷移；若其目的在于獲得特定資源，那么，可由需要資源的進程自行決定何時進行遷移，這種遷移也稱為自遷移（Self-migration）。 對前一種情況，整個遷移作用以及多系統(tǒng)的存在，對進程都可以是透明的；對后一種情況，進程必須了解分布式系統(tǒng)的分布情況。5第五頁，共七十頁，2022年，8月28日10.1.2進程遷移機制

2.遷移什么當遷移一個進程時，必須在源系統(tǒng)上破壞該進程，并在目標系統(tǒng)上建立它。這才是進程的移動，而不是復制進程。因此，進程映像，至少包括進程控制塊，必須移動。另外，這個進程與其他進程間的任何鏈接也必須更新。6第六頁，共七十頁，2022年，8月28日10.1.2進程遷移機制進程遷移舉例：

7第七頁，共七十頁，2022年，8月28日10.1.2進程遷移機制

從執(zhí)行的角度看,進程控制塊移動的困難之處在于進程地址空間的傳送和進程打開文件的傳送?？紤]第一個問題——進程地址空間的傳送，假設用虛擬存儲策略(分段或分頁)，有兩種方法：①遷移時傳送整個地址空間。②僅傳送那些在主存中的地址空間部分，在需要時再傳送虛擬地址空間中的段。8第八頁，共七十頁，2022年，8月28日10.1.2進程遷移機制

3.消息和信號處理 對于那些未完成的消息和信號，可通過一種機制進行處理：在遷移進行時，暫時存儲那些完成的消息和信號，然后將它們直接送到新的目的地，有必要在遷移出發(fā)的位置將正在發(fā)出的信息維持一段時間，以確保所有的未完成消息和信號都被傳送到目的地。9第九頁，共七十頁，2022年，8月28日10.1.3.一種遷移方案下面討論在IBM的AIX操作系統(tǒng)上的一種遷移機制，它是自我遷移的典型代表。AIX操作系統(tǒng)是一種分布式的UNIX操作系統(tǒng)，在LOCUS操作系統(tǒng)上可得到類似的機制。實際上，AIX系統(tǒng)是對LOCUS的改進。10第十頁，共七十頁，2022年，8月28日10.1.3.一種遷移方案 遷移按以下事件序列進行：①當進程決定遷移自身時，它選擇一個目標機，發(fā)送一個遠程消息，該消息帶有進程的部分映像及打開文件信息。②在接收端，內(nèi)核服務進程生成一個后代，將這個信息交給它。③這個新進程收集完成其操作所需的數(shù)據(jù)、環(huán)境、自變量及棧信息。如果程序文本是不純的，那么它是被拷貝過來的；如果是純的，那么它就是全局文件系統(tǒng)所要求的頁面。④遷移完成時通知源進程，源進程就發(fā)送一個最后完成消息給新進程，然后破壞自己。11第十一頁，共七十頁，2022年，8月28日10.1.4進程遷移的協(xié)商進程遷移涉及到進程遷移的決定，在某些情況下，由單個實體作決定。但是，有些系統(tǒng)允許指定的目標系統(tǒng)參與作決定，主要是為了保持對用戶的響應時間。

Charlotte采用的是遷移協(xié)商（NegotiationofMigration）機制，是由若干個Starter進程負責遷移策略(什么時候?qū)⒛膫€進程遷移到什么地方)，及作業(yè)調(diào)度和內(nèi)存分配。因此，Starter可以在這3方面進行協(xié)調(diào)，每個Starter進程可以控制一簇機器，Starter從它控制的每臺機器的內(nèi)核獲取當時的詳細負載統(tǒng)計信息。12第十二頁，共七十頁，2022年，8月28日10.1.4進程遷移的協(xié)商

必須由兩個Starter進程聯(lián)合來決定遷移，按以下步驟進行：①由控制源系統(tǒng)S的Starter決定將進程P遷移到特定的目標系統(tǒng)D，它發(fā)送一個消息給D的Starter,要求傳送。②如果D的Starter準備接受進程P，就回復一個肯定的確認。③S的Starter通過服務請求的方式將這個決定傳給S的內(nèi)核，或者將消息傳給S機上的KernJob(KJ)進程，將來自遠程進程的消息轉(zhuǎn)換成服務請求。④S的內(nèi)核將進程P傳給D。⑤如果D資源不足，它可以拒絕接受，否則，D的內(nèi)核就把來自S的信息傳給它的控制Starter。⑥Starer通過一個遷入（MigrateIn）請求與D協(xié)商決定遷移策略。⑦D保留必要的資源以避免死鎖和流控問題，然后給S返回一個接收信息。13第十三頁，共七十頁，2022年，8月28日10.1.4進程遷移的協(xié)商進程遷移的協(xié)商：

14第十四頁，共七十頁，2022年，8月28日10.1.4進程遷移的協(xié)商 Charlotte進程遷移功能有三個重要的特征：①它把決策機制從嵌入內(nèi)核的遷移機制中分離出來。②遷移對遷移進程和與其相連的進程是透明的。③遷移進程可以在任何時候被搶先，被中斷的進程可以移到另一個節(jié)點中。15第十五頁，共七十頁，2022年，8月28日10.1.5進程驅(qū)逐協(xié)商進程允許一個系統(tǒng)將遷移到其上的進程驅(qū)逐出去。

Sprite提供了這種驅(qū)逐能力。在Sprite中，每個進程在其生存期內(nèi)都好像僅在一個主機上運行。這臺主機是該進程的“家節(jié)點”(HomeNode)，如果某進程被遷移，它就成為目標機上的“外來進程”(ForeignProcess)。目標機任何時候都可驅(qū)逐外來進程，于是外來進程有可能被迫遷移回其“家節(jié)點”。16第十六頁，共七十頁，2022年，8月28日10.1.5進程驅(qū)逐Sprite的驅(qū)逐機制包含如下部分：①每個節(jié)點都有一個根據(jù)當前的負載來決定什么時候接受新的外來進程的監(jiān)管進程。②如果一個進程被驅(qū)逐，它就遷移回其家節(jié)點，在其他節(jié)點可以使用時該進程又可進行遷移。③盡管驅(qū)逐所有進程需要一段時間，但被標記驅(qū)逐的所有進程可以被立即掛起。④將被驅(qū)逐進程的整個地址空間傳送回家節(jié)點，通過在以前的主機恢復遷移進程的內(nèi)存映像，可以減少遷移進程的時間。17第十七頁，共七十頁，2022年，8月28日10.1.6搶占及非搶占進程的遷移搶占進程的遷移，包括傳送一個部分運行的進程，或者是已生成但還未運行的進程。非搶占進程的遷移在負載平衡中很有用。其優(yōu)點是可以避免頻繁的進程遷移，其不足在于對負載分配的突變反應不靈敏。遷移非搶占進程的方法較簡單，僅傳送那些尚未運行的進程，因此，不要求傳送進程的狀態(tài)。這兩種遷移，都必須將進程運行的環(huán)境信息傳給遠程節(jié)點，這包括用戶當前的工作目錄和進程繼承的權(quán)限。18第十八頁，共七十頁，2022年，8月28日10.2分布式全局狀態(tài)

10.2.1全局狀態(tài)及分布式快照在緊耦合系統(tǒng)中存在的所有同步問題，如互斥、死鎖、饑餓，在分布式系統(tǒng)中同樣存在。由于系統(tǒng)沒有全局狀態(tài)，故這方面的設計策略更復雜。由于分布式系統(tǒng)結(jié)構(gòu)中的時間滯后不可避免，因而其與同步相關問題的解決更加復雜，因此，用進程/事件圖來解釋這個問題。19第十九頁，共七十頁，2022年，8月28日10.2.1全局狀態(tài)及分布式快照確定全局狀態(tài)的例子：

20第二十頁，共七十頁，2022年，8月28日10.2.1全局狀態(tài)及分布式快照不一致和一致的全局狀態(tài)：

21第二十一頁，共七十頁，2022年，8月28日10.2.1全局狀態(tài)及分布式快照 為了尋求一個合適的解決方案，首先對下面術語給出定義：①通道。如果兩個進程交換信息，那么它們之間就有一個通道。為了方便，通道只是單向的。②狀態(tài)。一個進程的狀態(tài)就是該進程所帶通道發(fā)送和接收的消息序列。③快照。一張快照記錄一個進程的狀態(tài)，每張快照包括上次快照后所有通道上發(fā)送和接收的所有消息的記錄。④全局狀態(tài)。所有進程的聯(lián)合狀態(tài)。⑤分布式快照?？煺占粋€進程一個。22第二十二頁，共七十頁，2022年，8月28日10.2.1全局狀態(tài)及分布式快照面對的問題是，由于消息傳送的時間滯后，不能決定真正的全局狀態(tài)。我們希望通過從所有進程收集快照來決定全局狀態(tài)。我們希望分布式快照記錄一個一致的全局狀態(tài)：如果每個接收消息進程狀態(tài)中的接收記錄都與該消息在發(fā)送消息進程狀態(tài)中的發(fā)送記錄相對應，那么全局狀態(tài)是一致的。如果一個進程記錄了一條消息的接收，但相應的發(fā)送消息進程沒有記錄消息已發(fā)送的信息，就會發(fā)生不一致的全局狀態(tài)。23第二十三頁，共七十頁，2022年，8月28日10.2.2分布式快照算法在記錄一致的全局狀態(tài)的分布式快照算法中，假設消息按序發(fā)送并且沒有丟失，算法用到一個專門的控制消息，叫做marker。一些進程在發(fā)送更多消息前，記錄其狀態(tài)并通過所有輸出的通道發(fā)送給marker，從而激發(fā)該算法。每個進程P都按如下步驟進行。第一次收到marker(來自進程q)，接收進程p執(zhí)行如下步驟：①記錄其當前局部狀態(tài)Sp。②將從q到p的輸入通道記錄為空狀態(tài)。③將marker沿所有輸出通道傳送給其所有鄰居。24第二十四頁，共七十頁，2022年，8月28日10.2.2分布式快照算法在記錄了狀態(tài)后，當p從另外的輸入通道(來自進程r)收到一個marker時，接受進程p就執(zhí)行下面的步驟：①將從r到p的狀態(tài)記為：從p記錄其狀態(tài)Sp到它接收來自r的marker這段時間內(nèi)，p從r收到的消息序列。②一旦所有輸入通道都收到marker，算法在這個進程上中止。25第二十五頁，共七十頁，2022年，8月28日10.2.2分布式快照算法現(xiàn)對算法討論如下：①通過發(fā)送一個marker，使任何進程都可開始該算法。實際上，幾個節(jié)點各自獨立地記錄狀態(tài)，算法仍有效。②若每個消息(包括marker)都在有限時間內(nèi)傳送，則算法將在有限時間內(nèi)終止。③這是一個分布式算法，每個進程都記錄自己的狀態(tài)和所有輸入通道的狀態(tài)。④一旦所有狀態(tài)都記錄了(算法在所有進程都中止了)，算法就得到一致的全局狀態(tài)。⑤算法不受影響，也不被進程采用的任何其他的分布式算法影響。26第二十六頁，共七十頁，2022年，8月28日10.2.2分布式快照算法進程和通道圖：27第二十七頁，共七十頁，2022年，8月28日10.2.2分布式快照算法快照舉例：進程1 進程3

輸出通道 輸出通道

2發(fā)送1，2，3，4，5，6 2發(fā)送1，2，3，4，5，6，7，83發(fā)送1，2，3，4，5，6 進入通道進入通道 1接收1，2，3存儲4，5，6進程2 2接收1，2，3存儲4

輸出通道 4接收1，2，33發(fā)送1，2，3，4 進程44發(fā)送1，2，3，4 輸出通道進入通道 3發(fā)送1，2，31接收1，2，3，4存儲5，6進入通道

2接收1，2，3，4，5，6，7，8 2接收1，2存儲3，428第二十八頁，共七十頁，2022年，8月28日10.3分布式進程管理——互斥在第3章和第4章中曾提到的并發(fā)進程執(zhí)行的相關問題，其中兩個主要問題就是互斥和死鎖。這兩章主要討論在單機系統(tǒng)中只有一個主存而有多個進程的環(huán)境下解決這個問題的方法。為解決分布式操作系統(tǒng)和沒有共享主存的多處理器中發(fā)生的相關問題，就需要新的解決方法?；コ夂退梨i算法必須依靠消息的交換，而不能依靠對主存的訪問。本小節(jié)和10.4節(jié)分別討論分布式操作系統(tǒng)中的互斥和死鎖問題。29第二十九頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題當兩個或多個進程競爭系統(tǒng)資源時，有必要利用互斥機制，假設兩個或更多的進程都要使用單一非共享資源，如打印機。把這樣的資源看做是臨界資源，程序中使用這類資源的部分看做是程序的臨界段。在某一時刻僅允許一個程序位于其臨界段。30第三十頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題 進程的并發(fā)運行要求能夠定義臨界段和實行互斥，要支持互斥必須滿足以下要求：①在某一時刻，僅允許若干擁有同一資源或共享臨界段的進程中的一個進入臨界段。②在非臨界段運行結(jié)束的進程，不能影響其他進程。③訪問臨界段的進程，不能無限期地被延遲，即無死鎖和饑餓發(fā)生。④沒有進程在臨界段時，應允許任何要求進入臨界段的進程進入。⑤對進程執(zhí)行速度或進程數(shù)無任何假定。⑥一個進程在其臨界段中只逗留有限時間。31第三十一頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題分布式進程管理中互斥問題模型:32第三十二頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題互斥算法可以是集中式的，也可以是分布式的。在集中式算法中，將有一個節(jié)點作為控制節(jié)點，控制對所有共享對象的訪問。當任一進程要求訪問臨界段時，它就發(fā)送一個Request消息給本地資源控制進程，資源控制進程就發(fā)送一個Request消息給控制節(jié)點。當其共享對象可用時，控制節(jié)點就返回一個Reply(允許)消息；當進程使用完資源后，就發(fā)送一個Release消息給控制節(jié)點。這個集中式算法有兩個特點：①只有控制節(jié)點才能分配資源。②所有必要信息都集中在控制節(jié)點，包括所有資源的性質(zhì)和位置，以及每個資源的分配狀態(tài)。33第三十三頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題 分布式算法應有如下特性：①所有節(jié)點差不多有同等的信息量。②每個節(jié)點只有整個系統(tǒng)的部分信息，必須根據(jù)這些信息作決定。③所有節(jié)點共同負責作最后決定。④所有節(jié)點對最后決定所起的作用相同。⑤一般，一個節(jié)點失效，不會引起整個系統(tǒng)的失效。⑥沒有調(diào)整事件計時的統(tǒng)一的系統(tǒng)共同時鐘。34第三十四頁，共七十頁，2022年，8月28日10.3.1分布式互斥問題 需要對第②點和第⑥點作進一步說明：對第②點，一些分布式算法允許節(jié)點之間相互交流信息。即使這樣，在某一時刻，仍有一些信息可能被滯留在傳遞中，未能及時到達其他節(jié)點。因此，由于消息傳遞的滯后性，當前節(jié)點的信息可能不是最新的。對第⑥點，由于系統(tǒng)通信的延遲，要求所有系統(tǒng)有一個統(tǒng)一的時鐘是不可能的；使所有本地時鐘都與中央時鐘完全同步也很困難，經(jīng)過一段時間后，有些本地時鐘可能偏移。35第三十五頁，共七十頁，2022年，8月28日10.3.2分布式系統(tǒng)的事件定序——時戳方法大多數(shù)互斥和死鎖的分布式算法的基本操作是對事件進行定序（EventOrdering）。沒有統(tǒng)一時鐘或沒有同步的局部時鐘是主要問題。為了解決這個問題，用“時戳”對分布式系統(tǒng)中的事件定序，而不需要物理時鐘。36第三十六頁，共七十頁，2022年，8月28日10.3.2分布式系統(tǒng)的事件定序——時戳方法首先對事件下一定義。討論一個系統(tǒng)的行為、一個事件，如一個進程進入或離開臨界段。時戳方法就是對由消息傳送的事件定序。網(wǎng)絡中的每個系統(tǒng)i都有一個本地計數(shù)器Ci，它相當于一個時鐘。每次系統(tǒng)傳送一條消息就將其計數(shù)器加1，消息按

(m，Ti，i) 形式傳送，其中，m為消息的內(nèi)容；Ti為消息的時戳；i為該站點的編號。 當該消息達到時，接收系統(tǒng)j將它的時鐘置為

Cj=1+max[Cj，Ti]

在每個站點，事件的順序按下面的規(guī)則決定。對i處的消息x和j處消息y，如果滿足下面一個條件，就稱x先于y：①Ti＜Tj②Ti=Tj并且i＜j37第三十七頁，共七十頁，2022年，8月28日10.3.2分布式系統(tǒng)的事件定序——時戳方法時戳算法運行示例1：時戳算法運行示例2：38第三十八頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法1.Lamport算法 最早提出的分布式互斥方法是Lamport算法，它基于分布式隊列的概念，該算法基于以下假設：①分布式系統(tǒng)由N個站點組成，每個站點有惟一編號，從1到N。每個站點都僅有一個進程負責進行互斥訪問資源，也負責處理那些同時到達的請求。②按發(fā)送的順序接收從一個進程到另一個進程的消息。③每條消息都在有限時間內(nèi)正確地送到目的地。④網(wǎng)絡是全互連的，進程間可以兩兩直接發(fā)送信息。 假設②和③可通過一個可靠傳輸協(xié)議來實現(xiàn)。為了簡便，假設每個站點僅控制一個資源。39第三十九頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法算法所用的數(shù)據(jù)結(jié)構(gòu)可以是一個隊列，也可以是一個數(shù)組，若是數(shù)組，則每個站點占其中一個數(shù)據(jù)項：項q[j]表示來自Pj的消息。數(shù)組初始化為

q[j]=(Release，0，j)j=1，…，N本算法中用到以下3種消息。①(Request，Ti，i)：Pi請求訪問資源。②(Reply，Tj，j)：Pj允許對它所控制的資源進行訪問。③(Release，Tk，k)：Pk釋放以前分配給它的一個資源。40第四十頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法Lamport算法如下：①當Pi請求訪問資源時，它發(fā)送一個請求(Request，Ti，i)，時戳是當前本地時鐘值。它將此消息放入自身數(shù)組的q[i]中，然后，將這個消息傳給所有其他進程。②Pj收到請求(Request，Ti，i)后，將這個消息放入自身數(shù)組的q[i]中，并傳送(Reply，Tj，j)給所有其他進程（并且將這個消息也放置在自身數(shù)組中）。這一步就是為了滿足上述規(guī)則，以確保在作決定時沒有更早的消息在傳送。注意：若Pj在收到Request消息前也已提出過對同一資源的訪問請求，那么其Reply消息上的時戳就應比（Ti，i）小。41第四十一頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法③Pi滿足下面兩個條件就可訪問一個資源(進入其臨界段)：數(shù)組q中Pi的請求消息是數(shù)組中最早的請求消息。由于消息在所有站點的順序一致，這個規(guī)則允許在任一時刻僅有一個進程訪問資源。Pi確定已收到其它所有進程的其時戳都比（Ti，i）小的響應消息。這個規(guī)則確保Pi已知道所有在它當前請求前面的請求。④Pi通過發(fā)送(Release,Ti,i)消息來釋放所占用的資源。該消息也置入其自身的數(shù)組項中，并傳遞給所有其他進程。⑤當Pi接收到(Release,Tj,j)消息，它用該消息替換q(j)的當前內(nèi)容。⑥當Pi接收到(Reply,Tj,j)消息，它用該消息替換q(j)的當前內(nèi)容。 很容易證明此算法滿足互斥要求,且公平，不死鎖，不饑餓。42第四十二頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法2.Ricart算法Ricart對Lamport算法進行了一些簡化，希望將Release消息刪去以優(yōu)化原始算法。Ricart算法的假設與Lamport算法的假設基本點相同。同前，每個站點都有一個進程負責控制資源的分配。該進程有一個數(shù)組q并遵循以下規(guī)則。①當Pi請求訪問資源時，它發(fā)出一個請求(Request，Ti，i)。時戳為當前本地時鐘之值。它將這條消息放入自身數(shù)組q[i]中，然后，將消息發(fā)送給所有其他進程。43第四十三頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法②當Pj收到請求(Request，Ti，i)后，按如下規(guī)則處理：如果Pj正處于臨界段中，就延遲發(fā)送Reply消息(見規(guī)則4)；如果Pj并不等待進入臨界段，就發(fā)送(Reply，Tj，j)給所有其他進程；如果Pj等待進入其臨界段，并且到來的消息在Pj的Request后，則將到來的消息放入其數(shù)組的q[i]中，并延遲發(fā)送Reply消息；如果Pj等待進入其臨界段，但是到來的消息在Pj的Request前，就將到來的消息放入其數(shù)組的q[i]中，并發(fā)送(Reply，Tj，j)給Pi。③如果Pi從所有其他進程都收到了Reply消息，它就可以訪問資源。④當Pi離開臨界段時，它給每個掛起的Request發(fā)送一個Reply消息，從而釋放資源。44第四十四頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法Ricart算法的狀態(tài)圖：45第四十五頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法簡單小結(jié)：當一個進程想要進入臨界段時，它就給所有其他進程發(fā)送一條帶時戳的Request消息，當它從所有其他進程收到Reply后，它就可以進入臨界段。當一個進程收到另一個進程的Request時，它必須酌情發(fā)送一個Reply：如果該進程不想進入臨界段，它就馬上發(fā)送Reply。若它想要進入臨界段，它就將自己的Request的時戳與收到的Request的時戳進行比較，如果后者較遲，它就延遲發(fā)送Reply；否則馬上發(fā)送Reply。 這里，Reply消息實際上起到了Lamport算法中Release消息所起到的釋放資源的作用。46第四十六頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法

本算法主要存在以下的問題：①所有進程都必需知道系統(tǒng)中每個進程的名字。當有新進程加入時，會造成大量開銷。②若一進程意外失效，則會導致發(fā)出Request的進程收不到全部響應。因此，系統(tǒng)必需提供某種機制，當某進程失效時，將其名字通知其它進程。47第四十七頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法3.令牌方法 下面討論一種有效的令牌方法。這個算法需要2個數(shù)據(jù)結(jié)構(gòu)：令牌從一進程傳到另一個進程，它實際上是一個數(shù)組token，其第k個元素記錄上一次令牌傳到進程Pk的時戳；每個進程也有一個數(shù)組Request，其第j個元素記錄上次從Pj收到Request的時戳。48第四十八頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法

算法過程如下：最初，將令牌隨機分配給一個進程，即將該進程的tokenpresent置為true，表示進程此時擁有令牌。當一個進程要進入臨界段時，如果它擁有令牌就可進入；否則，它向所有其他進程廣播帶時戳的Request請求消息，等待直到它得到令牌。當進程Pi離開臨界段時，它必須將令牌傳給其他進程，它按i+1，i+2，…，1，2，…，i–1的順序搜索Request數(shù)組，找到第一個滿足Pj最新要求的、時戳比其token中記錄的Pj上一次擁有令牌的時間值要大的進程Pj，也就是滿足：Request[j]＞token[j]的Pj。這一規(guī)則就是為了確保令牌不會被重復發(fā)放給已經(jīng)使用過令牌獲得了資源，而且沒有更新需求產(chǎn)生的進程。49第四十九頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法令牌傳遞算法(進程Pi)：ifnottoken-presentthen

beginclock:=clock+1;[Prelude]broadcast(request,clock,i);wait(access,token);token-present:=True

end;endif;token-held:=True;<criticalsection>token(i):=clock;[Postlude]token-held:=false;forj:=i+1ton,1toi–1doif(request(j)＞token(j))∧token-present

thenbegintoken-present:=False;send(j,access,token)

endendif;(a)接左圖：Whenreceived(request,t,j)dorequest(j):=max(request(j),t);

iftoken-present∧nottoken-heldthen<textofpostlude>

endifenddo;(b)記號說明：

send(j,access,token)將access消息和令牌token傳給進程jbroadcast(request,clock,i)將進程i的請求消息和時戳clock傳給所有其他進程

received(request,t,j)從進程j收到請求消息及時戳t50第五十頁，共七十頁，2022年，8月28日10.3.3分布式互斥算法

該算法滿足下面兩種情況之一：①如果請求進程沒有令牌，則需要N條消息(N–1條廣播請求，1條傳送令牌)。②如果進程已擁有令牌就不需要消息。51第五十一頁，共七十頁，2022年，8月28日10.4分布式死鎖在第4章中，將死鎖定義為一個進程集的永久阻塞，這些進程或者競爭系統(tǒng)資源或者相互通信。這個定義對分布式系統(tǒng)和單個系統(tǒng)同樣有效。與互斥一樣，死鎖在分布式系統(tǒng)中會引起比共享內(nèi)存系統(tǒng)更為復雜的問題。由于沒有一個站點能精確地知道整個系統(tǒng)的當前狀態(tài)，并且兩個進程的消息可能遇到不可預測的延遲，因此，死鎖處理在分布式系統(tǒng)中相當復雜。有兩種類型的死鎖：資源分配引起的死鎖和消息通信引起的死鎖。52第五十二頁，共七十頁，2022年，8月28日10.4.1資源分配中的死鎖只有滿足以下所有條件時，才會出現(xiàn)資源分配的死鎖：①互斥。②占有并等待。③非搶占。④循環(huán)等待。分布式死鎖處理遇到的困難在于“死鎖幻象”(PhantomDeadlock)。53第五十三頁，共七十頁，2022年，8月28日10.4.1資源分配中的死鎖死鎖幻象：54第五十四頁，共七十頁，2022年，8月28日10.4.2死鎖預防

第4章討論的死鎖預防方法中有兩種可以用在分布式環(huán)境中：①對網(wǎng)絡中所有可共享資源進行線性排序。其缺點在于，由于資源并不是按它們使用的順序請求。因此，資源可能比需要占有的時間要長。②一個進程一次請求它所需要的全部資源，通過阻塞該進程直到所有請求同時被滿足為止，這可破壞占有并等待的條件。55第五十五頁，共七十頁，2022年，8月28日10.4.2死鎖預防這兩種方法都需要進程事先就知道它所需要的資源，這并不總是可能的。下面討論兩個不需要這種預見知識的算法，由于我們是圍繞數(shù)據(jù)庫討論，所以只對事務而不是對進程來討論。這里介紹的方法利用了時戳。每個事務在生存期內(nèi)都帶有其產(chǎn)生的時戳，從而使事務有了嚴格的順序。如果資源R已在事務T1中用過而被另一個事務T2請求，就可以通過比較兩者的時戳來解決沖突，這個比較可避免循環(huán)等待條件的形成。對這個基本方法作兩種變化，就得到了wait-die方法和wound-wait方法。56第五十六頁，共七十頁，2022年，8月28日10.4.2死鎖預防(a)wait-die方法

(b)wound-wait方法57第五十七頁，共七十頁，2022年，8月28日10.4.2死鎖預防wait-die算法演示：58第五十八頁，共七十頁，2022年，8月28日10.4.3死鎖避免 死鎖避免就是動態(tài)確定如果滿足一個資源分配請求，是否會引起死鎖。由于以下原因分布式死鎖避免并不實際可行：①每個節(jié)點必須記錄系統(tǒng)的全局狀態(tài)，這就需要大量的存儲和通信耗費。②檢測安全全局狀態(tài)的進程必須是互斥的，否則，兩個節(jié)點各自考慮一個不同進程的資源請求，可能得出滿足請求是安全的結(jié)論，但實際上同時滿足這兩個請求會發(fā)生死鎖。③對有大量進程和資源的分布式系統(tǒng)而言，檢查安全狀態(tài)，需要相當大的開銷。59第五十九頁，共七十頁，2022年，8月28日10.4.4死鎖檢測1.分布式死鎖檢測策略分布式死鎖檢測的困難在于，每個站點僅知道自己的資源，而死鎖可能涉及分布式資源。根據(jù)系統(tǒng)控制是集中的、分層的還是分布式的，相應有幾種策略：集中式策略，由一個站點來負責死鎖檢測。分布式，需要所有進程合作來檢測死鎖。60第六十頁，共七十頁，2022年，8月28日10.4.4死鎖檢測2.分布式死鎖檢測算法現(xiàn)在討論一種分布式死鎖檢測算法。該算法用于一個分布式數(shù)據(jù)庫系統(tǒng)，其中每個站點只有部分數(shù)據(jù)庫信息，并且事務可在每處初始化。一個站點中的所有數(shù)據(jù)對象都有兩個參數(shù)：惟一標號Di和變量Lock-by(Di)，后面這個變量在數(shù)據(jù)對象沒有任何事務加鎖時為空；否則，其值就是加鎖事務的標號。61第六十一頁，共七十頁，2022年，8月28日10.4.4死鎖檢測

一個站點中的所有事務j都有4個參數(shù)：①惟一標號Tj。②變量Held-by(Tj)，如果事務Tj在運行或者處于就緒態(tài)，就置為空；否則，其值就等于另外某個事務的標號，這個事務占有了事務Tj所請求的數(shù)據(jù)對象。③變量Wait-by(Tj)，如果事務Tj不等待其他事務，就置為空；否則，其值就等于處于阻塞事務序列頭的事務標號。④隊列RequestQ(Tj)，它包括對Tj占有的數(shù)據(jù)對象的所有尚未滿足的請求。隊列的每個元素都形如(Tk，Dk)，其中Dk是Tj占有的數(shù)據(jù)對象，Tk是請求Dk的事務。62第六十二頁，共七十頁，2022年，8月28日10.4.4死鎖檢測{事務Tj收到更新的消息}begin

ifWait-for(Tj)≠Wait-for(Ti)thenWait-for(Tj):=Wait-for(Ti);

ifWait-for(Tj)∩Request-Q(Tj)=nil

thenupdate(Wait-for(Ti),Request-Q(Tj))

elsebeginDECLAREDEADLOCK;{initiatedeadlockresolutionasfollows}{Tj被選擇作為夭折的事務}{Tj釋放它所占用的全部數(shù)據(jù)對象}send-clear(Tj,Held-by(Tj));allocateeachdataobjectDiheld-byTjto

thefirstrequesterTkinRequest-Q(Tj);

foreverytransactionTninRequest-Q(Tj)

requestingdataobjectDiheld-byTjdoEnqueue(Tn,Request-Q(Tk))；

endend.{事務Tk收到clear(Tj,Tk)消息}beginpurgethetuplehavingTjastherequ