操作系統(tǒng) 第8章網(wǎng)絡與分布式系統(tǒng)

1、操作系統(tǒng)（第3版）第 8 章 網(wǎng)絡與分布式處理第 8 章 網(wǎng)絡與分布式處理8.1 8.1 分布式系統(tǒng)概述分布式系統(tǒng)概述8.2 8.2 網(wǎng)絡服務器網(wǎng)絡服務器8.3 8.3 分布式進程管理分布式進程管理8.4 8.4 進程遷移進程遷移8.5 8.5 分布式進程通信分布式進程通信8.6 8.6 分布式進程同步與互斥分布式進程同步與互斥 8.7 8.7 分布式進程死鎖問題分布式進程死鎖問題8.1 分布式系統(tǒng)概述q 分布式能力包括以下幾個方面分布式能力包括以下幾個方面 通信結(jié)構(gòu)通信結(jié)構(gòu) 、網(wǎng)絡操作系統(tǒng)、網(wǎng)絡操作系統(tǒng) 、分布式操作系統(tǒng)、分布式操作系統(tǒng) q 通信結(jié)構(gòu)通信結(jié)構(gòu) 具有結(jié)構(gòu)的一組模塊構(gòu)成了通信結(jié)構(gòu)

2、具有結(jié)構(gòu)的一組模塊構(gòu)成了通信結(jié)構(gòu) 一個簡單的通信結(jié)構(gòu)一個簡單的通信結(jié)構(gòu) 通常，通信涉及三個方面：應用、計算機和網(wǎng)絡通常，通信涉及三個方面：應用、計算機和網(wǎng)絡 。因此，。因此，一個通信任務組織成相對獨立的三層：網(wǎng)絡存取層、傳輸層一個通信任務組織成相對獨立的三層：網(wǎng)絡存取層、傳輸層和應用層：和應用層：網(wǎng)絡存取層負責的是計算機與其連接網(wǎng)絡之間的數(shù)據(jù)交網(wǎng)絡存取層負責的是計算機與其連接網(wǎng)絡之間的數(shù)據(jù)交換換傳輸層為所有應用提供了可靠的傳輸機制傳輸層為所有應用提供了可靠的傳輸機制應用層包含了支持各用戶應用所需的邏輯應用層包含了支持各用戶應用所需的邏輯q 開放式系統(tǒng)互連通信結(jié)構(gòu)開放式系統(tǒng)互連通信結(jié)構(gòu) 開放式系

3、統(tǒng)互連開放式系統(tǒng)互連OSIOSI七層模型七層模型 物理層物理層 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層 網(wǎng)絡層網(wǎng)絡層 傳輸層傳輸層 會話層會話層 表示層表示層 應用層應用層8.1 分布式系統(tǒng)概述8.2 網(wǎng)絡服務器q 服務器的結(jié)構(gòu)服務器的結(jié)構(gòu) 服務器與網(wǎng)絡上的其它工作站服務器與網(wǎng)絡上的其它工作站樣，它有一個網(wǎng)絡接樣，它有一個網(wǎng)絡接口模塊，該模塊包括了與局域網(wǎng)交互所需的硬件和軟件；用口模塊，該模塊包括了與局域網(wǎng)交互所需的硬件和軟件；用戶工作站也包括了一個網(wǎng)絡接口。此外它還包含了與服務器戶工作站也包括了一個網(wǎng)絡接口。此外它還包含了與服務器通信的一些網(wǎng)絡邏輯通信的一些網(wǎng)絡邏輯 這種結(jié)構(gòu)的服務器功能強，而且靈活，其功能表

4、現(xiàn)在這種結(jié)構(gòu)的服務器功能強，而且靈活，其功能表現(xiàn)在它可用于控制各種類型的資源它可用于控制各種類型的資源 q 磁盤和文件服務器磁盤和文件服務器 文件服務器文件服務器 對文件進行幾種存儲和管理、自動備份和恢復、用戶流對文件進行幾種存儲和管理、自動備份和恢復、用戶流動性動性 、與其它文件服務器進行連接、與其它文件服務器進行連接 磁盤服務器磁盤服務器 許多文件服務器只不過提供了一個中心磁盤設施，作為個人計許多文件服務器只不過提供了一個中心磁盤設施，作為個人計算機用戶局部存儲器的擴充，這樣的系統(tǒng)有時叫磁盤服務器算機用戶局部存儲器的擴充，這樣的系統(tǒng)有時叫磁盤服務器 文件高速緩沖存儲器的一致性問題文件高速緩

5、沖存儲器的一致性問題 問題的產(chǎn)生問題的產(chǎn)生 因為使用文件高速緩沖存儲器保留最近存取的文件記錄，減因為使用文件高速緩沖存儲器保留最近存取的文件記錄，減少對遠程服務器必須進行的存取次數(shù)，致使有時產(chǎn)生文件高速緩少對遠程服務器必須進行的存取次數(shù)，致使有時產(chǎn)生文件高速緩沖存儲器的一致性問題沖存儲器的一致性問題 解決辦法解決辦法 - - 最簡單方法是對文件采用加鎖技術，以防止多個客戶機同最簡單方法是對文件采用加鎖技術，以防止多個客戶機同時存取一個文件時存取一個文件 8.2 網(wǎng)絡服務器 更有效的方法是允許任意多的進程同時打開一個文件讀更有效的方法是允許任意多的進程同時打開一個文件讀并創(chuàng)建各自的客戶機高速緩存

6、。但當有一個對服務器的請求是并創(chuàng)建各自的客戶機高速緩存。但當有一個對服務器的請求是打開文件的寫請求，而其它進程打開文件是讀存取對，文件服打開文件的寫請求，而其它進程打開文件是讀存取對，文件服務器采取兩個活動。務器采取兩個活動。 打印機服務器打印機服務器 打印機服務器可以處理許多用戶工作站的打印請求。這不打印機服務器可以處理許多用戶工作站的打印請求。這不僅可以節(jié)省打印費用，而且使得打印更加容易和打印速度更快僅可以節(jié)省打印費用，而且使得打印更加容易和打印速度更快 調(diào)制解調(diào)器服務器調(diào)制解調(diào)器服務器 當用戶向服務器請求存取調(diào)制解調(diào)器并提供一個電話號碼當用戶向服務器請求存取調(diào)制解調(diào)器并提供一個電話號碼后

7、，服務器啟動調(diào)制解調(diào)器，撥號、并報告結(jié)果。如果呼叫成后，服務器啟動調(diào)制解調(diào)器，撥號、并報告結(jié)果。如果呼叫成功，向用戶提供一個連接。功，向用戶提供一個連接。8.2 網(wǎng)絡服務器8.3 分布式進程管理q 分布式互斥分布式互斥 互斥算法分類互斥算法分類 集中式算法集中式算法 算法：一個節(jié)點作為控制節(jié)點，控制對所有共享目標的算法：一個節(jié)點作為控制節(jié)點，控制對所有共享目標的存取。只有控制節(jié)點才能對資源分配進行決策；控制節(jié)點中存取。只有控制節(jié)點才能對資源分配進行決策；控制節(jié)點中集中了所有必要信息，包括所有資源的標識和位置，以及每集中了所有必要信息，包括所有資源的標識和位置，以及每個資源的分配狀態(tài)個資源的分配

8、狀態(tài) 優(yōu)缺點：集中式互斥算法比較簡單，容易實現(xiàn)，但如優(yōu)缺點：集中式互斥算法比較簡單，容易實現(xiàn)，但如果控制節(jié)點失敗了，互斥機制就無法實現(xiàn)；每個資源的分配果控制節(jié)點失敗了，互斥機制就無法實現(xiàn)；每個資源的分配和回收要求與控制節(jié)點交換信息，因此，控制節(jié)點可能變?yōu)楹突厥找笈c控制節(jié)點交換信息，因此，控制節(jié)點可能變?yōu)槠款i瓶頸 分布式算法分布式算法 特征：平均來講，所有節(jié)點有著等量的信息。每個節(jié)點只特征：平均來講，所有節(jié)點有著等量的信息。每個節(jié)點只有整個系統(tǒng)的一部分描述，且必須基于這個信息進行決策。所有整個系統(tǒng)的一部分描述，且必須基于這個信息進行決策。所有節(jié)點對于系統(tǒng)的最后決策有著完全相等的作用。有節(jié)點對于

9、系統(tǒng)的最后決策有著完全相等的作用。 克服時鐘同步困難所采用的一個常見方法克服時鐘同步困難所采用的一個常見方法 分布式系統(tǒng)中的事件定序法分布式系統(tǒng)中的事件定序法8.3 分布式進程管理q 分布式算法分布式算法 Lamport分布式算法分布式算法 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：qj=(Release,0,j) j=1,n 使用的三類信息：使用的三類信息： (Request,Ti,i)表示進程表示進程Pi訪問資源的請求信息。訪問資源的請求信息。 (Reply,Tj,j)表示在表示在Pj的控制下允許訪問資源的信息。的控制下允許訪問資源的信息。 (Release,Tk,k)表示進程表示進程Pk釋放先前分配給它的資源

10、釋放先前分配給它的資源 8.3 分布式進程管理 算法描述：算法描述： 當當Pi請求訪問一個資源時，它泄放一個請求信息請求訪問一個資源時，它泄放一個請求信息(Request,Ti,i)，時標，時標Ti是本地時鐘的當前值，它把這個信息放是本地時鐘的當前值，它把這個信息放在它自己的數(shù)組項在它自己的數(shù)組項qi中，并將這個信息發(fā)送給其它所有進程中，并將這個信息發(fā)送給其它所有進程 當當Pj接收到信息接收到信息(Request,Ti,i)，時，它把這個信息放在，時，它把這個信息放在它自己的數(shù)組它自己的數(shù)組qj中，并發(fā)送信息中，并發(fā)送信息(Reply,Tj,j)給其它所有進程給其它所有進程 當下面兩個條件成立

11、時，當下面兩個條件成立時，PiPi可以訪問一個資源：可以訪問一個資源： 在數(shù)組在數(shù)組q q中，中，PiPi自己的請求信息是數(shù)組中最早請求的信自己的請求信息是數(shù)組中最早請求的信息。由于信息在所有節(jié)點的順序是一致的，這個規(guī)則允許一個息。由于信息在所有節(jié)點的順序是一致的，這個規(guī)則允許一個而且只有一個進程在任何時刻訪問所請求的資源而且只有一個進程在任何時刻訪問所請求的資源8.3 分布式進程管理 在本地數(shù)組中的所有其它信息比在本地數(shù)組中的所有其它信息比qiqi中的信息都晚一中的信息都晚一些。這保證些。這保證PiPi已了解了它的當前請求在所有請求之前已了解了它的當前請求在所有請求之前 進程進程PiPi釋放

12、資源時，它泄放信息釋放資源時，它泄放信息(Release,Ti,i)(Release,Ti,i)，把，把它放在自己的數(shù)組中，并傳送給其它所有進程它放在自己的數(shù)組中，并傳送給其它所有進程 當當PiPi接收到信息接收到信息(Release,Tj,j)(Release,Tj,j)時，它用這個信息置時，它用這個信息置換換qjqj的當前內(nèi)容的當前內(nèi)容 當當PiPi接收到接收到(Reply,Tj,j)(Reply,Tj,j)信息時，它用這個信息置換信息時，它用這個信息置換qjqj的當前內(nèi)容的當前內(nèi)容8.3 分布式進程管理 令牌傳遞法令牌傳遞法 令牌：令牌（令牌：令牌（tokentoken）是進程在任何時間

13、持有的一個實體，）是進程在任何時間持有的一個實體，持有令牌的進程不必請求許可權就可以進入它的臨界區(qū)。當進程持有令牌的進程不必請求許可權就可以進入它的臨界區(qū)。當進程離開它的臨界區(qū)時，再將令牌傳遞給另一個進程離開它的臨界區(qū)時，再將令牌傳遞給另一個進程 數(shù)據(jù)結(jié)構(gòu)：這個算法需要兩個數(shù)據(jù)結(jié)構(gòu)。一個是被傳遞的數(shù)據(jù)結(jié)構(gòu)：這個算法需要兩個數(shù)據(jù)結(jié)構(gòu)。一個是被傳遞的令牌，另一個是請求數(shù)組令牌，另一個是請求數(shù)組 算法描述：算法描述：算法的描述程序算法的描述程序 8.3 分布式進程管理8.4 進程遷移q 進程遷移進程遷移 定義定義 進程遷移是指，為了使進程在另一個機器上執(zhí)行，源機器進程遷移是指，為了使進程在另一個機器

14、上執(zhí)行，源機器向目標機傳送足夠數(shù)量的進程的狀態(tài)信息向目標機傳送足夠數(shù)量的進程的狀態(tài)信息 在分布式系統(tǒng)中，希望進程遷移的理由在分布式系統(tǒng)中，希望進程遷移的理由 負載均衡、通信性能的改善、可用性、利用專用的能力負載均衡、通信性能的改善、可用性、利用專用的能力q 進程遷移機制進程遷移機制 啟動遷移啟動遷移 由誰啟動遷移將依賴于遷移設施要實現(xiàn)的目標由誰啟動遷移將依賴于遷移設施要實現(xiàn)的目標 需要遷移哪些信息需要遷移哪些信息 當一個進程被遷移時，需要撤消源系統(tǒng)上的進程，并在當一個進程被遷移時，需要撤消源系統(tǒng)上的進程，并在目標系統(tǒng)上創(chuàng)建它。這是一個進程的移動，而不是進程映像的目標系統(tǒng)上創(chuàng)建它。這是一個進程的

15、移動，而不是進程映像的復制復制 遷移的兩種策略：遷移進程的整個地址空間；僅遷移進遷移的兩種策略：遷移進程的整個地址空間；僅遷移進程在內(nèi)存的那部分地址空間程在內(nèi)存的那部分地址空間 對尚未完成的信息和信號的考慮對尚未完成的信息和信號的考慮q 遷移處理遷移處理 在有些情況下，進程遷移由一個實體進行決策在有些情況下，進程遷移由一個實體進行決策 8.4 進程遷移8.5 分布式進程通信q信息傳送機制信息傳送機制 分布式信息傳送的最普通的模型：客戶機分布式信息傳送的最普通的模型：客戶機/ /服務器模型服務器模型 采用這種最簡單的形式時，信息傳送僅需要兩個功能：采用這種最簡單的形式時，信息傳送僅需要兩個功能：

16、發(fā)送和接收發(fā)送和接收q 遠程過程調(diào)用遠程過程調(diào)用 概念概念 遠程過程調(diào)用是對信息傳送基本模型的修改，允許不同遠程過程調(diào)用是對信息傳送基本模型的修改，允許不同機器上的程序使用簡單的過程調(diào)用和返回方式進行交互對話機器上的程序使用簡單的過程調(diào)用和返回方式進行交互對話 遠程過程調(diào)用的一般結(jié)構(gòu)遠程過程調(diào)用的一般結(jié)構(gòu) 命令格式命令格式 ：CALL P(xCALL P(x，y)y) P P是過程名字，是過程名字，x x為傳送的變量，為傳送的變量，y y是返回值參數(shù)是返回值參數(shù) 遠程過程調(diào)用中涉及的幾個設計問題遠程過程調(diào)用中涉及的幾個設計問題 參數(shù)傳遞問題參數(shù)傳遞問題 參數(shù)表示參數(shù)表示 客戶機與服務器的結(jié)合客

17、戶機與服務器的結(jié)合8.5 分布式進程通信q 確定分布式系統(tǒng)的全局狀態(tài)確定分布式系統(tǒng)的全局狀態(tài) 全局狀態(tài)和分布式瞬態(tài)全局狀態(tài)和分布式瞬態(tài) 在緊藕合系統(tǒng)中所有的并發(fā)問題，如互斥、死鎖和餓死在緊藕合系統(tǒng)中所有的并發(fā)問題，如互斥、死鎖和餓死等，在分布式系統(tǒng)中也會遇到等，在分布式系統(tǒng)中也會遇到 由于網(wǎng)絡傳輸?shù)难舆t，分布式系統(tǒng)的性質(zhì)帶來的時間滯由于網(wǎng)絡傳輸?shù)难舆t，分布式系統(tǒng)的性質(zhì)帶來的時間滯后使得所有與并發(fā)有關的問題復雜化后使得所有與并發(fā)有關的問題復雜化 所謂所謂全局狀態(tài)全局狀態(tài)是一致的，是指如果接收信息的進程已記是一致的，是指如果接收信息的進程已記錄它接收到了信息的狀態(tài)，那么，在發(fā)送信息的進程狀態(tài)中應錄

18、它接收到了信息的狀態(tài)，那么，在發(fā)送信息的進程狀態(tài)中應記錄它發(fā)送了那個信息記錄它發(fā)送了那個信息 所謂所謂分布式瞬態(tài)分布式瞬態(tài)是指每個進程有一組狀態(tài)的收集是指每個進程有一組狀態(tài)的收集 8.5 分布式進程通信 分布式瞬態(tài)算法分布式瞬態(tài)算法 所謂所謂分布式瞬態(tài)算法分布式瞬態(tài)算法是指記錄一致性全局狀態(tài)在分布式系是指記錄一致性全局狀態(tài)在分布式系統(tǒng)中采用的方法。該算法假定，信息應按照其發(fā)送的順序傳送，統(tǒng)中采用的方法。該算法假定，信息應按照其發(fā)送的順序傳送，并且在傳輸過程中沒有被丟失并且在傳輸過程中沒有被丟失 。算法用了一個專用的控制信息。算法用了一個專用的控制信息marker marker 進程進程p p接

19、收到接收到Q Q的的markermarker后，執(zhí)行：后，執(zhí)行：1 1，進程，進程P P記錄下它的局記錄下它的局部狀態(tài)部狀態(tài)SP 2SP 2，記錄從，記錄從Q Q到到P P進入（進入（incomingincoming）通道的狀態(tài)）通道的狀態(tài) 3 3，進程進程P P沿著所有向外發(fā)出的通道傳播這個沿著所有向外發(fā)出的通道傳播這個markermarker給它的所有鄰接給它的所有鄰接進程進程 8.5 分布式進程通信 在記錄它的狀態(tài)之后的任何時間，若在記錄它的狀態(tài)之后的任何時間，若P P接收了另一個進入接收了另一個進入通道（如來自進程通道（如來自進程R R）的）的markermarker時，它執(zhí)行如下：時

20、，它執(zhí)行如下： 進程進程P P記錄從記錄從R R到到P P的通道狀態(tài)。這個狀態(tài)是作為的通道狀態(tài)。這個狀態(tài)是作為P P記錄它的記錄它的局部狀態(tài)局部狀態(tài)SPSP，開始到它接收到來自，開始到它接收到來自R R的的markermarker時信息序列而記時信息序列而記錄的。錄的。 一旦沿著每個進入通道都已收到了一旦沿著每個進入通道都已收到了markermarker，這個算法就，這個算法就在進程在進程P P終止終止 8.5 分布式進程通信 進程同步主要是指彼此合作的進程在共享資源上協(xié)調(diào)其進程同步主要是指彼此合作的進程在共享資源上協(xié)調(diào)其操作順序。進程互斥則主要是指彼此競爭的進程嚴格按照次操作順序。進程互斥則

21、主要是指彼此競爭的進程嚴格按照次序（排它性的）使用資源。序（排它性的）使用資源。8-6-1 8-6-1 事件定序法事件定序法-同步和互斥的分布式算法的基本操作是事件的時間定同步和互斥的分布式算法的基本操作是事件的時間定序。由于缺乏一個公共的時鐘或同步局部時鐘的方法，序。由于缺乏一個公共的時鐘或同步局部時鐘的方法，可以用下面的方法進行表達?？梢杂孟旅娴姆椒ㄟM行表達。-當說系統(tǒng)當說系統(tǒng)i i中的事件中的事件a a出現(xiàn)在系統(tǒng)出現(xiàn)在系統(tǒng)j j中的事件中的事件b b之前（或之前（或之后）時，希望網(wǎng)絡中所有系統(tǒng)都能得出這個一致性之后）時，希望網(wǎng)絡中所有系統(tǒng)都能得出這個一致性的結(jié)論。但不幸的是，這種陳述是不

22、精確的。的結(jié)論。但不幸的是，這種陳述是不精確的。8.6 分布式進程同步與互斥- 首先一個事件的實際出現(xiàn)與某個其他系統(tǒng)觀察到它的首先一個事件的實際出現(xiàn)與某個其他系統(tǒng)觀察到它的時間之間可能有一個延遲；其次由于缺少同步設施，時間之間可能有一個延遲；其次由于缺少同步設施，可能在不同系統(tǒng)上讀出的時鐘值不同?？赡茉诓煌到y(tǒng)上讀出的時鐘值不同。- 為了克服上述兩個問題造成的影響，為了克服上述兩個問題造成的影響，LamportLamport建議采用建議采用時標方法為分布式系統(tǒng)中的事件定序。這個技術被廣時標方法為分布式系統(tǒng)中的事件定序。這個技術被廣泛地用在解決同步和互斥的分布式算法中。泛地用在解決同步和互斥的分

23、布式算法中。- 時標模式用來為傳輸?shù)男畔⒔M成的事件定序。時標模式用來為傳輸?shù)男畔⒔M成的事件定序。8.6 分布式進程同步與互斥圖8-15 時標算法的執(zhí)行情況8-6-2 8-6-2 分布式互斥分布式互斥 實施互斥的算法可以是集中式的，也可以是分布式的實施互斥的算法可以是集中式的，也可以是分布式的 集中式算法集中式算法-算法：一個節(jié)點作為控制節(jié)點，控制對所有共享目標算法：一個節(jié)點作為控制節(jié)點，控制對所有共享目標的存取。只有控制節(jié)點才能對資源分配進行決策；控的存取。只有控制節(jié)點才能對資源分配進行決策；控制節(jié)點中集中了所有必要信息，包括所有資源的標識制節(jié)點中集中了所有必要信息，包括所有資源的標識和位置，

24、以及每個資源的分配狀態(tài)和位置，以及每個資源的分配狀態(tài) -優(yōu)缺點：集中式互斥算法比較簡單，容易實現(xiàn)，但如優(yōu)缺點：集中式互斥算法比較簡單，容易實現(xiàn)，但如果控制節(jié)點失敗了，互斥機制就無法實現(xiàn)；每個資源果控制節(jié)點失敗了，互斥機制就無法實現(xiàn)；每個資源的分配和回收要求與控制節(jié)點交換信息，因此，控制的分配和回收要求與控制節(jié)點交換信息，因此，控制節(jié)點可能變?yōu)槠宽毠?jié)點可能變?yōu)槠宽?.6 分布式進程同步與互斥 分布式算法分布式算法特征：特征：- 平均來講，所有節(jié)點有著等量的信息平均來講，所有節(jié)點有著等量的信息-每個節(jié)點只有整個系統(tǒng)的一部分描述，且必須基于這個每個節(jié)點只有整個系統(tǒng)的一部分描述，且必須基于這個信息進行

25、決策信息進行決策-所有節(jié)點對于系統(tǒng)的最后決策有著完全相等的作用所有節(jié)點對于系統(tǒng)的最后決策有著完全相等的作用 -一個節(jié)點失敗了，一般不會導致整個系統(tǒng)崩潰一個節(jié)點失敗了，一般不會導致整個系統(tǒng)崩潰-不存在系統(tǒng)范圍的公共時鐘來協(xié)調(diào)與時間有關的事件不存在系統(tǒng)范圍的公共時鐘來協(xié)調(diào)與時間有關的事件8.6 分布式進程同步與互斥8-6-3 8-6-3 分布式算法分布式算法 LamportLamport分布式算法分布式算法- 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：qj=(Release,0,j) j=1,nqj=(Release,0,j) j=1,n- 使用的三類信息：使用的三類信息： (Request,Ti,i)(Request

26、,Ti,i)表示進程表示進程PiPi訪問資源的請求信息。訪問資源的請求信息。 (Reply,Tj,j)(Reply,Tj,j)表示在表示在PjPj的控制下允許訪問資源的信息。的控制下允許訪問資源的信息。 (Release,Tk,k)(Release,Tk,k)表示進程表示進程PkPk釋放先前分配給它的資源釋放先前分配給它的資源 8.6 分布式進程同步與互斥- 算法描述：算法描述： 當當PiPi請求訪問一個資源時，它泄放一個請求信息請求訪問一個資源時，它泄放一個請求信息(Request,Ti,i)(Request,Ti,i)，時標，時標TiTi是本地時鐘的當前值，它把這個信是本地時鐘的當前值，它

27、把這個信息放在它自己的數(shù)組項息放在它自己的數(shù)組項qiqi中，并將這個信息發(fā)送給其它所中，并將這個信息發(fā)送給其它所有進程有進程 當當PjPj接收到信息接收到信息(Request,Ti,i)(Request,Ti,i)，時，它把這個信息，時，它把這個信息放在它自己的數(shù)組放在它自己的數(shù)組qjqj中，并發(fā)送信息中，并發(fā)送信息(Reply,Tj,j)(Reply,Tj,j)給其它給其它所有進程所有進程8.6 分布式進程同步與互斥 當下面兩個條件成立時，當下面兩個條件成立時，PiPi可以訪問一個資源：可以訪問一個資源： 在數(shù)組在數(shù)組q q中，中，PiPi自己的請求信息是數(shù)組中最早請求的信自己的請求信息是數(shù)

28、組中最早請求的信息。由于信息在所有節(jié)點的順序是一致的，這個規(guī)則允許一息。由于信息在所有節(jié)點的順序是一致的，這個規(guī)則允許一個而且只有一個進程在任何時刻訪問所請求的資源個而且只有一個進程在任何時刻訪問所請求的資源 在本地數(shù)組中的所有其它信息比在本地數(shù)組中的所有其它信息比qiqi中的信息都晚一中的信息都晚一些。這保證些。這保證PiPi已了解了它的當前請求在所有請求之前已了解了它的當前請求在所有請求之前 進程進程PiPi釋放資源時，它泄放信息釋放資源時，它泄放信息(Release,Ti,i)(Release,Ti,i)，把，把它放在自己的數(shù)組中，并傳送給其它所有進程它放在自己的數(shù)組中，并傳送給其它所有

29、進程 當當PiPi接收到信息接收到信息(Release,Tj,j)(Release,Tj,j)時，它用這個信息置時，它用這個信息置換換qjqj的當前內(nèi)容的當前內(nèi)容 當當PiPi接收到接收到(Reply,Tj,j)(Reply,Tj,j)信息時，它用這個信息置換信息時，它用這個信息置換qjqj的當前內(nèi)容的當前內(nèi)容8.6 分布式進程同步與互斥 令牌傳遞法令牌傳遞法-令牌：令牌（令牌：令牌（tokentoken）是進程在任何時間持有的一個實）是進程在任何時間持有的一個實體，持有令牌的進程不必請求許可權就可以進入它的體，持有令牌的進程不必請求許可權就可以進入它的臨界區(qū)。當進程離開它的臨界區(qū)時，再將令牌

30、傳遞給臨界區(qū)。當進程離開它的臨界區(qū)時，再將令牌傳遞給另一個進程另一個進程-數(shù)據(jù)結(jié)構(gòu)：這個算法需要兩個數(shù)據(jù)結(jié)構(gòu)。一個是被傳數(shù)據(jù)結(jié)構(gòu)：這個算法需要兩個數(shù)據(jù)結(jié)構(gòu)。一個是被傳遞的令牌，另一個是請求數(shù)組遞的令牌，另一個是請求數(shù)組-算法描述算法描述8.6 分布式進程同步與互斥8.7 分布式進程死鎖問題q 資源分配中的死鎖資源分配中的死鎖 在分布式系統(tǒng)中在分布式系統(tǒng)中 , ,必須依據(jù)各節(jié)點的局部信息進行決策必須依據(jù)各節(jié)點的局部信息進行決策 死鎖的預防死鎖的預防 破壞環(huán)路等待條件破壞環(huán)路等待條件 破壞請求和保持條件破壞請求和保持條件 死鎖的檢測死鎖的檢測 系統(tǒng)是集中式的控制系統(tǒng)是集中式的控制：由于中心進程有一個完整的圖形