分布式操作系統(tǒng)考試題

1、分布式操作系統(tǒng)1在交換式Dash多處理機系統(tǒng)中，為了保持緩存一致性，采用了Dash協(xié)議，某一簇中的一CPU寫一未緩存的數(shù)據(jù)塊，之后另外一簇的另外一CPU讀該數(shù)據(jù)塊。試詳細說明寫操作和讀操作是如何進行的。寫操作：該CPU查看緩存發(fā)現(xiàn)沒有該數(shù)據(jù)塊，它在本地發(fā)送請求查看鄰近CPU的緩存中是否有該數(shù)據(jù)塊。如果有，執(zhí)行緩沖區(qū)到緩沖區(qū)的傳送，如果塊狀態(tài)為干凈宿主所在簇的其他拷貝置為無效。如果在本地查找失敗，CPU發(fā)送體育館到其宿主所在簇。如果塊為未緩存，標記為臟并發(fā)送給請求者；如果塊為干凈，所有拷貝置為無效，標記為臟并發(fā)送給請求者；如果塊為臟，請求傳送到擁有該數(shù)據(jù)塊拷貝的遠程簇，該簇將自己的拷貝置為無效并

2、滿足寫操作。讀操作：另一CPU查看自己緩存與本地簇其他CPU緩存發(fā)現(xiàn)無此數(shù)據(jù)塊。該CPU發(fā)送請求包給宿主所在簇，發(fā)現(xiàn)所需塊的狀態(tài)為臟，目錄查找擁有該塊的簇的標志。該簇響應(yīng)請求。并將該數(shù)據(jù)塊發(fā)送給請求簇，將其狀態(tài)改為干凈，還要給宿主所在簇發(fā)回一個拷貝以更新存儲器，這時塊的狀態(tài)被置為干凈。2在基于總線的多處理機系統(tǒng)中，遵循write once協(xié)議，假設(shè)有C1，C2，C3，C4四個CPU，一操作序列如下：C1讀一字W1（只存在于共享存儲器中）、C1繼續(xù)讀該字、C2讀該字；C1修改該字、C3讀該字、C4讀該字。試詳細說明以上操作序列是如何執(zhí)行的。C1查看緩存發(fā)現(xiàn)沒有該字，從共享存儲器中讀取W1，同時緩

3、存中也存儲W1，狀態(tài)為干凈。C1又一次讀W1。查看自己緩存發(fā)現(xiàn)存在該字，從緩存中讀取W1。C2讀W1先在自己緩存中查找發(fā)現(xiàn)沒有緩存，從共享存儲器讀取W1并存儲在緩存中，狀態(tài)為干凈。C1修改W1將緩存中的該字修改，狀態(tài)變?yōu)榕K，同時C2監(jiān)聽到寫請求，將自己緩存中的W1置為無效。C3讀該字，C1發(fā)現(xiàn)讀請求發(fā)信號禁止存儲器響應(yīng)，C1向C3提供該字并將自己的項置為無效，C3發(fā)現(xiàn)該字來自其他緩存其狀態(tài)置為臟，并將自己緩存項標記為臟。C4讀該字，C3發(fā)現(xiàn)讀請求禁止存儲器響應(yīng)，并向C4提供該字，并且將自己的項置為無效。C4發(fā)現(xiàn)該字來自其他緩存，其狀態(tài)為臟，則標記自己緩存項為臟。3在分布式系統(tǒng)，為了獲得文件讀寫

4、的效率，需要使用高速緩存，說明設(shè)置緩存的各種方法及用途。并說明解決一致性問題的四種算法及各種算法存在的問題。在一個各自有主存和磁盤的客戶一服務(wù)器系統(tǒng)中，有四個地方可用來存儲文件或存儲部分文件:服務(wù)器磁盤，服務(wù)器主存，客戶磁盤(如果可用的話)或客戶主存。在服務(wù)器內(nèi)存設(shè)置緩存，可以減少I/O次數(shù)，而在客戶端內(nèi)存和磁盤中設(shè)置緩存，可以減少網(wǎng)絡(luò)通信。1.在服務(wù)器磁盤在服務(wù)器磁盤上，有允足的空間，存放在那里的所有文件對所有客戶都是可訪問的。而且，由于每一個文件只有一份拷貝，所以不會產(chǎn)生一致性的問題.2. 在服務(wù)器主存將最近使用的文件保留在服務(wù)器的主存中。客戶讀取一個剛好在服務(wù)器主存中的文件，可以消除磁盤

5、傳送，但網(wǎng)絡(luò)傳送仍然存在。在服務(wù)器主存中設(shè)置高速緩存：容易、對客戶是完全透明的。由于服務(wù)器可以保證其主存和磁盤拷貝同步。從客戶的觀點看，每個文件只有一個拷貝，不會產(chǎn)生一致性問題。3. 在客戶磁盤客戶磁盤保存數(shù)據(jù)多但速度慢。如果使用大量的數(shù)據(jù)，客戶磁盤高速緩存可能更好些。4. 客戶端高速緩存此時有三種可使用的選擇來精確定義高速緩存的位置：a)、在每個用戶進程自己的地址空間直接進行文件高速緩存。b)、在內(nèi)核中。c）、在一個單獨的用戶級高速緩存管理者進程中，它保持了(微)內(nèi)核獨立于文件系統(tǒng)編碼，因此易十編程，并巨更加靈活.四種算法：1直接寫算法：（WRITE-THRONG算法）當修改一個高速緩存項（

6、文件或塊）時，新的值保存在高速緩存中并立即寫到服務(wù)器；2延遲寫：延遲寫操作使得語義變得不清楚。當另一個進程讀此文件時，它所得結(jié)果取決于時間選擇。延遲寫只好在運行效率和清晰的語義之間權(quán)衡。3關(guān)閉時寫：僅當文件關(guān)閉后才將文件寫到服務(wù)器，與對話語義相配；4集中控制算法：a當打開一個文件時，打開該文件的機器向服務(wù)器發(fā)送一條消息。服務(wù)器保存誰打開了哪個文件以及打開是為了讀還是寫或者兩者兼有。b 如果文件是為讀而打開，允許其他進程為讀而打開，避免為寫而打開。如果某個進程為寫而打開一個文件，必須禁止所有其他訪問。c 當關(guān)閉文件時，必須報告，以便服務(wù)器更新。d缺點：不健壯，不能規(guī)模化。存在的問題：(1)直接寫

7、：有效，但不影響寫流量。(2)延遲寫：效率較高，但可能語義不清。(3)關(guān)閉時寫：與會話語義相配。(4)集中控制：UNIX語義，但不健壯，不能規(guī)?；?。4給出實現(xiàn)文件復(fù)制的三種方法，并舉例說明更新復(fù)制文件的Gifford算法，并說明某些服務(wù)器崩潰時，應(yīng)該采取什么措施。三種方法：1、顯式復(fù)制：當進程產(chǎn)生一個文件時，可以在其他服務(wù)器上生成另外的拷貝。如果目錄服務(wù)存在允許一個文件有多個拷貝，所有拷貝的網(wǎng)絡(luò)地址都可以和這個文件名聯(lián)系起來。2、懶惰復(fù)制：只要在某個服務(wù)器上建立每個文件的一個拷貝，服務(wù)器自己在其他的服務(wù)器上也可自動生成副本。3、使用組通信：所有的寫系統(tǒng)調(diào)用同時傳送到所有的服務(wù)器。于是，其他的拷

8、貝在原文件產(chǎn)生時就產(chǎn)生了。Gifford算法：即表決（voting）,其基本思想是在讀或?qū)懸粋€拷貝文件之前要求中請并獲得多個服務(wù)器的允許。下面舉一簡單的例子來說明該算法是如何工作的：假設(shè)一個文件在N個服務(wù)器上都有拷貝。建立一個更新文件的規(guī)則:首先客戶必須和超過半數(shù)的服務(wù)器聯(lián)系，并讓它們同意它進行更新。如果它們同意，就改變文件，并將一個新的版本號和新文件聯(lián)系起來。該版本號用來標識該文件的版本，這對所有新近更新的文件都是一樣的。當讀一個已有拷貝的文件時，客戶必須和超過半數(shù)的服務(wù)器聯(lián)系，并請求它們發(fā)送與該文件相聯(lián)系的版本號。如果所有版本號相一致，則說明這是最新的版本，如果企圖只更新剩余服務(wù)器，會因為

9、數(shù)目不足而失敗。例如，有5個服務(wù)器，客戶已確定它們中的三個有版本號8，則其他兩個的版本號不可能是9。因為任何從版本號8到版本號9的成功更新需要三個服務(wù)器同意，而不是兩個。Gifford的方案實際上比這更普通一些。在該方案中，讀一個已有N個拷貝存在的文件時，客戶需要獲得一個讀法定數(shù)，它是任何Nr個或更多服務(wù)器的任一集合。同樣，修改一個文件需要一個至少Nw個服務(wù)器的寫法定數(shù)Nr和Nw的值必須滿足約束條件Nr+Nw>N。只有在適當數(shù)目的服務(wù)器同意參與時，文件才能讀或?qū)懳募?。假設(shè)最近的寫法定數(shù)由從C到L的10個服務(wù)器組成，所有這些服務(wù)器得到了新版本和新版本號，任何隨后的由3個服務(wù)器組成的讀法定數(shù)

10、中將至少包含一個該集合中的成員。當客戶查看版本號時，它將知道哪一個是最新的并得到它。解決辦法：虛像表決通過為每個已崩潰的服務(wù)器建立一個沒有存儲器的虛擬服務(wù)器解決了服務(wù)器崩潰的問題。虛設(shè)者不允許出現(xiàn)在讀法定數(shù)中，但它可以加入寫法定數(shù)中。當一個崩潰的服務(wù)器重新啟動時，它必須獲得一個讀法定數(shù)來找到最新的版本。在它開始正常工作之前，它將為自己拷貝一份該拷貝。5 試說明舉例什么是有狀態(tài)服務(wù)器，什么是無狀態(tài)服務(wù)器，并對有狀態(tài)和無狀態(tài)服務(wù)器進行詳細的比較。無狀態(tài)服務(wù)器：當客戶發(fā)送一個請求到給服務(wù)器，服務(wù)器完成請求，發(fā)送一個應(yīng)答，然后從內(nèi)部表中移出關(guān)于該請求的所有信息。在請求之間，服務(wù)器不保存具體客戶的信息。

11、有狀態(tài)服務(wù)器：服務(wù)器保存兩個請求之間的客戶的狀態(tài)信息。 比較：無狀態(tài)服務(wù)器的優(yōu)點：容錯、不需要OPEN/CLOSE調(diào)用、沒有服務(wù)器表空間的浪費、沒有打開文件數(shù)目的限制、客戶崩潰時不會造成服務(wù)器錯誤。有狀態(tài)服務(wù)器的優(yōu)點：請求消息比較短，減少網(wǎng)絡(luò)帶寬、更好的性能、可以預(yù)讀，預(yù)先讀信息塊減少延遲、易于冪等性（客戶第二次發(fā)送相同請求時，可以不用再傳輸）、可以對文件加鎖。無狀態(tài)服務(wù)器在本質(zhì)上有更多的容錯。不需要OPEN和CLOSE調(diào)用，這就減少了消息編號，特別對于那些整個文件用一次就可讀出的普通情況，服務(wù)器不用浪費空間來存放表。使用表時，如果太多的客戶一次打開太多的文件，則將表填滿，就不能打開新的文件。

12、最后對于狀態(tài)服務(wù)器，如在文件打開時窗戶出了故障，服務(wù)器就會牌困境中。如果它對此束手無策，它的表最終將充滿垃圾。如果它超時了還未打開文件，那么客戶因兩個請求之間等待時間太長將被拒絕服務(wù)。有狀態(tài)服務(wù)器由于READ和WRITE消息并不是必須包含文件名，所以它可以更短些，這樣就使用更小的網(wǎng)絡(luò)帶寬。由于關(guān)于打開文件的信息在文件關(guān)閉之前都可保存在主存儲器中，所以有較好的性能。由于大多數(shù)文件都是按順序讀的，可以預(yù)先讀信息塊減少延遲。6 在分布式系統(tǒng)中，可支持上載/下載文件模式或遠程訪問模式，說明這兩種模式并進行比較。上載/下載模式：文件服務(wù)只提供兩種主要的操作：讀文件和寫文件。讀文件操作是將整個文件以一個文

13、件服務(wù)器傳送到提出請求的客戶；寫操作是將整個文件從客戶傳送到服務(wù)器。優(yōu)點：概念簡單。使用這種模式不需要掌握復(fù)雜的文件接口，而且整個文件傳送也是高效的。缺點：客戶端必具有足夠大的存儲空間來存儲所需的所有文件。如果只需要文件的一小部分，移動整個文件是很浪費的。遠程訪問模式：文件服務(wù)提供了大量的操作用于打開和關(guān)閉文件，讀寫文件的一部分，在文件中來回移動，檢查和改變文件屬性等。優(yōu)點：在客戶端不需要很大的空間，當僅需要文件的一小部分時，不需要傳送整個文件。7 分布式協(xié)同一致算法的目標是使所有無故障處理機對待某些問題的意見達到一致，在3個正常處理機，2個出錯處理機的情況下，用Lamport算法能否達成一致

14、，給出算法的具體步驟。假設(shè)：正常處理機為：ABC。錯誤處理機為：DE。1. 每個處理發(fā)送消息給其它處理機消息：A：1 B：2 C：3 D：x1 y1 z1 m1 E：x2 y2 z2 m2 2. 把第一步聲明的結(jié)果收集組成向量的形式A：（1，2，3，x1，x2）B：（1，2，3，y1，y2）C：（1，2，3，z1，z2）D：（1，2，3，4，m2）E：（1，2，3，m1，5）3. 每個處理現(xiàn)將各自的向量傳遞給其它處理機。A：（1，2，3，y1，y2）（1，2，3，z1，z2）（1，2，3，4，m2）（1，2，3，m1，5）每個處理機檢查所有接收向量的第i個元素。若某個值占多數(shù)，放入結(jié)果向量中，

15、否則，標記為UNKNOWNA會得出結(jié)論（1，2，3，UNKNOWN，UNKNOWN）其他處理機進行相同的操作ABC得到一致的向量（1，2，3，UNKNOWN，UNKNOWN）8在實時分布式系統(tǒng)中，事件觸發(fā)和時間觸發(fā)系統(tǒng)的含義是什么，給出一個例子，并說明為什么動態(tài)調(diào)度適合于事件觸發(fā)系統(tǒng)，給出三種動態(tài)調(diào)度算法。事件觸發(fā)系統(tǒng)：當一個重要的外部事件觸發(fā)時，它被傳感器察覺到，并導(dǎo)致與傳感器相連的CPU得到一個中斷請求。時間觸發(fā)系統(tǒng)：每t毫秒產(chǎn)生一次時鐘中斷，在每一次時鐘滴答時，對傳感器進行采樣，并驅(qū)動執(zhí)行機構(gòu)。中斷僅在時鐘滴答時發(fā)生。例：考慮對一個100層樓的電梯控制器的設(shè)計。假定電梯在60層等客人。有

16、人在一層按下按鈕。就在100毫秒后，另一人在100層上按下按鈕。在事件觸發(fā)系統(tǒng)中，第一次按鈕產(chǎn)生一個中斷，使電梯啟動下行，就在做出下行決定后，第二個按鈕事件到來，因此第二個事件被記錄下來以作為將來的參考，但電梯還是下行。在時間觸發(fā)系統(tǒng)中，它每500毫秒采樣一次，若兩次按下按鈕事件都在一次采樣周期中出現(xiàn)，控制就必須做出決定。動態(tài)調(diào)度是在運行期間檢測到事件時進行調(diào)度，用事件觸發(fā)系統(tǒng)可以在低負載更快的響應(yīng)。算法：1.比率單調(diào)算法 2.最早時限優(yōu)先法 3.最小余度法9主動復(fù)制容錯的典型例子是三模冗余容錯，說明某組成部件出錯和某表決器出錯時，是如何容錯的。如果在某一級上同時有兩個表決器出錯，其它所有部件

17、和表決器均正常，能否屏蔽錯誤，為什么？如果服務(wù)器采用主動復(fù)制的方法會存在什么問題，如何解決？每個設(shè)備復(fù)制三次，結(jié)果是每級電路都設(shè)置了三個表決器，每個表決器都有三個輸入和一個輸出。若兩個或三個輸入相同，輸出則等于該輸入。若三個輸入各不相同，輸出就是不定值。1. 假設(shè)A2失效，V1 V2 V3都得到兩個好的輸入和一個壞的輸入，每個都輸出正確值到第二級。2. A2 B3 C1都出錯，A2出錯V1 V2 V3都輸出正確值到第二級，同理B3出錯V4 V5 V6也都輸出正確值到第三級。C1出錯同理。這些影響都被屏蔽，輸出結(jié)果仍正確不能。因為每一級只有三個表決器，如果有兩個同時壞掉超過三分之二的要求，不能輸

18、出正確結(jié)果。存在問題：所有請求到達所有服務(wù)器的順序就相同。解決方法：1對所有請求做全局計數(shù)編號。 2使用Lamport邏輯時鐘。10使用主機后備容錯方法容錯的主要思想是：在任何一個時刻都有一臺服務(wù)器是主機，若主機失效了，后備的服務(wù)器將承擔其任務(wù)。試說明主機后備方法的工作原理及存在的問題，及解決辦法?？蛻糁鞣?wù)器備份服務(wù)器1.請求2.工作3.更新4.工作5.確認6.響應(yīng)工作原理：在任一時刻都有一臺服務(wù)器是主機，它完成所有的工作。若這個主服務(wù)器失效了，后備的服務(wù)器將承擔其任務(wù)。1. 如果主機在執(zhí)行任務(wù)前崩潰，則沒有損失。客戶端會超時重發(fā)直到連上后備機，任務(wù)只被執(zhí)行一次。解決方案：客戶端只是在超時后

19、，再次重新發(fā)送請求消息，直到發(fā)送一定次數(shù)后，或者因得不到響應(yīng)而停止發(fā)送請求消息，或者它的請求分別得到主服務(wù)器和備份服務(wù)器的處理，并且只執(zhí)行一次。2. 如果主機在執(zhí)行任務(wù)后向后備機發(fā)送更新消息前崩潰，此時后備機接管，請求消息再次到來，則任務(wù)被執(zhí)行2次。解決方案：還沒有有效的解決方案，一般來說，在主服務(wù)器崩潰后，只正確執(zhí)行一次請求消息的處理是非常困難的。3. 如果主機在后備機執(zhí)行任務(wù)后自己發(fā)送響應(yīng)消息前崩潰，則任務(wù)共被執(zhí)行三次。一次主機完成，一次后備機完成，一次后備機接管時完成。如果請求消息帶有序號，則可以減少任務(wù)執(zhí)行次數(shù)。解決方案：若每個請求消息都帶有標志信息，那么請求消息只被執(zhí)行兩次。一般來說

20、，在主服務(wù)器崩潰后，只正確執(zhí)行一次請求消息的處理是非常困難的。解決辦法：是使用主機和備份機之間共享的兩端口磁盤。在這種配置下，當主機得到一個請求后，在做任何事之前先將請求寫入磁盤，并且也把執(zhí)行的結(jié)果寫人磁盤，不再需要向備份機發(fā)送消息并接收從備份機發(fā)來的消息了，若主機崩潰，備份機可通過讀磁盤而得到整個系統(tǒng)現(xiàn)在的狀態(tài)。11一個典型的集中的、啟發(fā)式的處理機分配算法，即上-下算法。說明該算法的目標，并說明該算法的主要原理。目標：讓一個等了很久的，沒有使用任何處理機的申請優(yōu)先于已經(jīng)占用了許多多處理機的申請。此為該算法的目標即公平的分配系統(tǒng)資源。主要原理：算法中有一個協(xié)調(diào)者，保存著一張使用情況的表，每個工

21、作站在表中都有一個條目，初值為0。當有重要的時間發(fā)生時，將給協(xié)調(diào)者發(fā)信息以更新使用情況表。算法將根據(jù)使用情況表決定處理機的分配。這些決定發(fā)生在調(diào)度事件發(fā)生時：有進程請求處理機、處理機進入空閑狀態(tài)或者是發(fā)生了時鐘中斷。使用情況表中的記錄值可以為整數(shù)、零或是負數(shù)。整數(shù)表示用戶純粹是在使用系統(tǒng)資源，負數(shù)表示用戶需要系統(tǒng)資源，零則介于兩者中間。12 在支持多線程的系統(tǒng)中，可采用三種模型來組織多線程，詳細說明這三種模型。如果在不支持多線程系統(tǒng)中實現(xiàn)文件服務(wù)，如何構(gòu)造文件服務(wù)器。派遣者/工作者模型: 某一個線程作為派遣者，它從系統(tǒng)郵箱內(nèi)讀出輸入請求，然后檢查請求，選擇一個空閑的工作者線程去處理它。然后派遣

22、者喚醒睡眠的工作者。 工作者被喚醒后，它檢查共享塊緩沖區(qū)是否可以滿足這個請求。如不能滿足，給磁盤發(fā)送消息，要求所需的數(shù)據(jù)塊。且進入休眠狀態(tài)等待磁盤操作的完成.團隊模型：所有線程都是批平等的，每個都獲得和處理自己的請求。沒有派遣者。如果工作來了不能處理，尤其是如果每個線程用來處理一種特殊的工作，可以維護一個隊列，掛起的作業(yè)保存在作業(yè)隊列中。線程在察看系統(tǒng)信箱前先察看作業(yè)隊列。管道線模型：第一個線程產(chǎn)生一些數(shù)據(jù)傳給下一個線程去處理。數(shù)據(jù)持續(xù)從一個線程傳到另一個線程，經(jīng)過的每一個線程都進行處理。文件服務(wù)器在無多線程的情況下可以讓它作為單線程執(zhí)行。文件服務(wù)器的主循環(huán)是接收一個請求并檢查它，并且在下一個

23、請求到來前完成它。當文件服務(wù)器等待磁盤操作時，它是空閑的且不處理另一請求，如果文件服務(wù)器運行于一個專用的機器上，當文件服務(wù)器等待磁盤時，CPU也是空閑的。13 在機器0上進程0在等待機器0上進程1所擁有的資源，進程1在等待機器1上進程2所擁有的資源，進程2在等待進程機器1上3，4所擁有的資源，進程3在等待機器2上進程5所擁有的資源，機器2上的進程5在等待機器0上進程0所擁有的資源，畫出簡化的資源圖并說明用Chandy-Misra-Hass提出的分布式死鎖檢測算法如何檢測死鎖，并打破死鎖。檢測死鎖：當某個進程等待資源時，例如進程0等待進程1。此時，生成一個特殊的探測消息并發(fā)送給占用資源的進程。消

24、息由三個數(shù)字構(gòu)成：阻塞的進程，發(fā)送消息的進程，接收消息的進程，如由0到1的初始消息包含三元組(0,0,1)。接到消息后，接受者檢查以確定它自己是否也在等待其它進程。如果是，那么消息就要被更新，第一個字段保持不變，第二個字段改為當前進程號，第三個字段改為等待的進程號。然后消息接著被發(fā)送到等待的進程。如果在等待多個進程，就需要發(fā)送多個不同的消息。不論資源時在本地還是在遠程，該算法都要繼續(xù)下去。如果消息轉(zhuǎn)了一圈后又回到了最初的發(fā)送者，那么就說明存在一個有死鎖的環(huán)路系統(tǒng)。打破死鎖：1.令最初發(fā)送探測消息的進程自殺。但是如果多個進程同時阻塞，同時發(fā)送探測消息，那么每個進程都會發(fā)現(xiàn)死鎖，并因此而自殺。2.

25、將每個進程的標識符添加到探測消息的末尾，將編號最大的進程中止或者發(fā)送消息請求它自殺。多個進程發(fā)現(xiàn)同一環(huán)路會選擇同一個犧牲者。14在分布式系統(tǒng)事務(wù)提交操作可能需要不同機器上的多個進程的協(xié)作，舉一個實際例子，并說明實現(xiàn)原子性提交的兩階段提交協(xié)議的基本思想。基本思想：有一個進程作為協(xié)調(diào)者，通常是執(zhí)行事務(wù)的進程。在準備提交階段，協(xié)調(diào)者向日志中寫入Prepare，然后向所有服務(wù)器發(fā)送準備提交消息。服務(wù)器接收消息后，檢查自己是否準備提交，如果是，就向日志中寫入Ready，然后向協(xié)調(diào)者發(fā)送準備好消息。在提交階段，協(xié)調(diào)者接收所有響應(yīng)后決定提交或終止。如果所有服務(wù)器都準備提交，則提交事務(wù)。如果有一個服務(wù)器未準備

26、好，則終止事務(wù)。無論結(jié)果如何，協(xié)調(diào)者都會寫入日志，并發(fā)送決定消息。服務(wù)器接到消息后，也將結(jié)果寫入日志，并發(fā)送結(jié)束消息，完成整個過程。例子：航空訂票系統(tǒng)。預(yù)訂一張從A到D的機票。若選A作為協(xié)調(diào)者，在準備提交階段，協(xié)調(diào)者A向日志中寫入Prepare，然后向服務(wù)器B、C、D發(fā)送準備提交消息。服務(wù)器B、C、D接收消息后，檢查自己是否準備提交，如果是，就向日志中寫入Ready，然后向協(xié)調(diào)者A發(fā)送準備好消息。在提交階段，協(xié)調(diào)者A接收所有響應(yīng)后決定提交或終止。如果所有服務(wù)器都準備提交，則提交事務(wù)，完成訂票。如果有一個服務(wù)器未準備好，則終止事務(wù)。5說明基于時間戳的樂觀并發(fā)控制算法的基本原理，并舉例說明。基于時

27、間戳的并發(fā)控制方法是指在一個事物開始做BEGIN_TRANSACTION的時候給它分配一個時間戳。通過使用Lamport的算法，我們可以確保時間戳是唯一的。系統(tǒng)中的每個文件都擁有一個相關(guān)的讀取時間戳，以判斷哪個已經(jīng)提交的進程最近一次讀取或?qū)懭脒^該文件。如果事務(wù)都很短小而且在時間間隔上比較大，那么一般來說當一個進程試圖訪問某個文件時，該文件的讀寫時間戳將低于當前事務(wù)的時間戳。這種詞性意味著事務(wù)正在以正確的順序進行處理，一切正常。當次序不正確時，就表明一個晚于當前事務(wù)開始的事務(wù)試圖插入、訪問文件并提交。這種情況意味著當前事務(wù)開始的過早了，因此需要終止。6舉例說明RICART和AGRAWALE分布式

28、互斥算法；假定A和B是相互獨立的兩個臨界區(qū)，進程0按A、B順序進入，進程1按B、A順序進入，R-A分布式互斥算法會導(dǎo)致死鎖嗎？說明理由。RICART和AGRAWALE算法要求系統(tǒng)中所有事件都是全序的，也就是說，對任何事件組消息哪個先發(fā)生哪個后發(fā)生必須無歧義，算法如下：（1）當一個進程想進入臨界區(qū)時，他要建立一個包括它要進入的臨界區(qū)的名字、處理機號、當前時間的消息，然后將消息發(fā)送給所有其他進程，也包括發(fā)送給自身。（2）當一個進程接收到另一個進程消息時，它取決于接受方的狀態(tài)以及臨界區(qū)的命名，有三種情況：1接受者不在臨界區(qū)，也不想進入臨界區(qū)，他就向發(fā)送者發(fā)送OK消息。2接受者已經(jīng)在臨界區(qū)，它不必回答

29、，而是負責對請求隊列排隊。3接收者要進入臨界區(qū)，但是還沒有進入，它要負責將發(fā)來的消息和它發(fā)送給其他進程的時間戳對比，取小的那個。如果來的消息時間戳小，接收者發(fā)送OK消息，否則接收者負責排列請求隊列而不發(fā)送任何消息。（3）在發(fā)送完允許進入臨界區(qū)的請求后，進程將不再做任何事，僅等待所有的允許消息，一旦得到允許它就進入臨界區(qū)。（4）它從臨界區(qū)退出時向隊列中所有進程發(fā)送OK消息，并將它從隊列中刪除。不會導(dǎo)致死鎖。進程0、1分別進入A、B臨界區(qū)，假設(shè)進程0先在A中執(zhí)行完后，退出A臨界區(qū)，并發(fā)送ok消息給所有的等待進程，之后申請臨界區(qū)B，因為進程1此時在臨界區(qū)B中，所以進程1負責將進程0排在臨界隊列中，當

30、進程1執(zhí)行完后退出B，它將進程0的請求從隊列中取出，并向進程0發(fā)送OK，允許進程0進入臨界區(qū)B，自己再去申請進入臨界區(qū)A.所以不會產(chǎn)生死鎖。17在分布式系統(tǒng)中，許多算法都需要一個進程充當協(xié)調(diào)者，因此需要協(xié)調(diào)者選舉算法。試說明欺負算法的主要思想，并說明在8個進程的情況下號碼為3的進程發(fā)現(xiàn)協(xié)調(diào)者崩潰后的選舉過程。欺負算法：當一個進程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請求時，它發(fā)起選舉。進程P選舉過程如下： P向所有號碼比它大的進程發(fā)送選舉消息 若無人響應(yīng)，P獲勝成為協(xié)調(diào)者。 若有號碼比它大的進程響應(yīng)，響應(yīng)者接管，P的工作完成。假設(shè)8個進程為進程0到進程7，原協(xié)調(diào)者為進程7進程3發(fā)現(xiàn)協(xié)調(diào)者崩潰，進程3主持選舉，進程

31、4進程5和進程6應(yīng)答，通知進程3停止，進程4進程5進程6分別主持選舉，進程6通知進程5和進程4停止，進程6獲勝并通知所有進程。18在分布式系統(tǒng)中獲得互斥的方法之一是采用集中式的算法，如果有四個進程P0，P 1，P2，P3，P0首先申請資源S，之后P 1，P2，P3 隨后申請資源S，試說明采用集中式的算法是如何實現(xiàn)互斥的。首先選擇一個進程為協(xié)調(diào)者。無論什么時候進程要進入臨界區(qū)，它向協(xié)調(diào)者發(fā)送請求消息，說明它想進入哪個臨界區(qū)并希望獲得允許。如果當前該臨界區(qū)內(nèi)沒有其他任何進程，協(xié)調(diào)者就發(fā)出允許進入消息。如當P0請求資源S時，當應(yīng)答到達時，P0就可以進入臨界區(qū)。此時若P1請求資源S，協(xié)調(diào)者知道該臨界區(qū)

32、已經(jīng)有一個進程，所以不能同意P1的請求。此時協(xié)調(diào)者可以發(fā)送“拒絕請求”應(yīng)答，把進程2的請求臨時排在隊列中?；蛘邊f(xié)調(diào)者回避應(yīng)答，這樣就阻塞了進程2，使它等待應(yīng)答。 當進程P1從臨界區(qū)退出時，它向協(xié)調(diào)者發(fā)送釋放互斥消息的訪問，此時協(xié)調(diào)者從推遲請求隊列中取出最前面的進程即P2，向它發(fā)送允許進入消息。如果該進程仍然阻塞，它不被阻塞且進入臨界區(qū)。如果明確發(fā)送一消息拒絕它進入臨界區(qū)，此進程應(yīng)該查詢輸入的消息，或者接著將它阻塞，不管怎么樣，當它發(fā)現(xiàn)允許進入時，它還可以進入臨界區(qū)。如果進程在阻塞狀態(tài)，它就會被喚醒進入臨界區(qū)。19有三個進程分別運行在不同的機器上，每個機器都有自己的時鐘并以不同且不變的速率工作（

33、進程1的時鐘嘀嗒了6下時，進程2的時鐘嘀嗒了8下，而進程3的時鐘嘀嗒了10下），舉例說明進程之間消息傳遞中違反先發(fā)生關(guān)系的情況，并說明如何用Lamport方法解決。 Lamport解決方案使用先發(fā)生關(guān)系，每條消息攜帶發(fā)送者的時鐘以指出其發(fā)送的時刻，當消息到達時，接收者時鐘若比消息發(fā)送時鐘小，就立即將自己的時鐘調(diào)到比發(fā)送時間大1或更多的值。如上圖，其中消息C從進程2到進程1是在60時刻離開，56時刻到達。同理，消息D從進程1到進程0是在64時序離開，54時刻到達，這是絕對不可能出現(xiàn)的。Lamport的解決方案是：因為C在60時刻離開，只能在61時刻或更晚時刻到達，所以每條消息都攜帶發(fā)送者的時鐘以

34、指出其發(fā)送的時刻，當消息到達時，接收者時鐘若比消息發(fā)送時鐘小，就立即將自己的時鐘調(diào)到比發(fā)送時間大1或更多的值。在b中，我們看到C現(xiàn)在到達的時間是61，同樣D到達的時間是70。20在很多分布式系統(tǒng)應(yīng)用中，需要物理時鐘同步，舉一個例子，并說明物理時鐘同步的三種算法，Cristian 算法、Berkeley算法及平均值算法。例子：導(dǎo)彈發(fā)射，不同的控制站必須同步時鐘，否則無法準確的控制導(dǎo)彈的發(fā)送時間及導(dǎo)彈運行軌道。Cristian 算法：每臺機器以小于或等于/2秒的周期定期地向時間服務(wù)器發(fā)送消息詢問當前的時間，時間服務(wù)器接到消息后就盡快回答含有當前時間CUTC值的消息。Berkeley算法：時間守護進

35、程（時間服務(wù)器）定期地詢問每臺機器的時間。然后基于這些回答計算出平均值并告訴所有的機器將它們的時鐘撥快或撥慢到一個新的值。（適合于沒有WWV接收器的系統(tǒng)）平均值算法：將時間分成固定長度的再同步間隔，第i次間隔開始于T0+iR，結(jié)束于T0+(i+1)R .T0是過去某一約定的時間，R是一個系統(tǒng)參數(shù)。在每次間隔開始處，每臺機器根據(jù)自己的時鐘廣播發(fā)送當前的時間。 在機器廣播發(fā)送時間之后，它啟動本地計時器收集在S時間間隔中到達的其他廣播。當所有廣播到達后，執(zhí)行一個算法，得到新的時間值。這個算法可以是求這些值得平均值，或者是去掉m個最大值和m個最小值，平均其余值。21組通信系統(tǒng)中，原子性的含義是什么，舉

36、例說明為什么要保證原子性。在保證原子性的同時還要保證消息順序，舉例說明保證消息順序的必要性。原子性：當條消息發(fā)送給一個組后，不是該組所有成員都正確收到，就是均未收到。不允許出現(xiàn)組內(nèi)有些成員收到而有些成員收不到的情況。即要么全有要么全無。例：在一個復(fù)制的分布式數(shù)據(jù)庫系統(tǒng)中，假設(shè)有一個進程給所有的數(shù)據(jù)庫機器發(fā)送一個消息創(chuàng)建一個新記錄，接著又發(fā)送一條消息去修改該記錄如果有些組成員未接收到建設(shè)記錄的消息，它們就無法執(zhí)行修改操作，這樣數(shù)據(jù)庫也將變得不一致。如果系統(tǒng)能夠保證將每條消息發(fā)送到該組的所有成員，該過程就比較簡單。如果不能保證，該消息就不發(fā)給組中的任何一個成員，并將失敗報告給發(fā)送者以作適當?shù)幕謴?fù)處

37、理。保證消息順序：從圖中我們可以看出：進程1首先收到了來自進程0的消息，然后收到了來自進程4的消息。進程3開始沒有收到消息，繼而收到了進程4和進程0的消息。這樣進程4和進程0的兩條消息以不同的順序到達了進程1和進程3。如果進程0和進程4都想去改變數(shù)據(jù)庫中的同一個值，那么進程1和進程3執(zhí)行的最終結(jié)果是不相同的。不用說這與組內(nèi)部分成員收到消息而部分成員未收到消息的情形是一樣糟糕的。因此為了使得編程更加的合理，系統(tǒng)必須很好的定義一種關(guān)于消息傳遞順序的語義。22 說明RPC的主要步驟，在形式說明書中輸入?yún)?shù)、輸出參數(shù)、輸入/輸出參數(shù)的含義是什么，為什么要這樣規(guī)定。如果服務(wù)器是無狀態(tài)的，為什么讀一個文件

38、的過程需要給出position參數(shù)。RPC的主要步驟：（1） 客戶過程以普通方式調(diào)用相應(yīng)的客戶存根。（2） 客戶存根建立消息并激活內(nèi)核陷阱。（3） 內(nèi)核將消息發(fā)送到遠程內(nèi)核。（4） 遠程內(nèi)核將消息送到服務(wù)器存根。（5） 服務(wù)器存根取出消息中的參數(shù)后調(diào)用服務(wù)器的過程。（6） 服務(wù)器完成工作后將結(jié)果返回至服務(wù)器存根。（7） 服務(wù)器存根將它打包并激動內(nèi)核陷阱。（8） 遠程內(nèi)核將消息發(fā)送至客戶內(nèi)核。（9） 客戶內(nèi)核將消息交給客戶存根。（10） 客戶存根從消息中取出結(jié)果返回給客戶。每一過程都給出了參數(shù)類型。每個參數(shù)都被指明為輸入?yún)?shù)、輸出參數(shù)、或者輸入/輸出參數(shù)。一個輸入?yún)?shù)，文件名name，是從客戶進

39、程傳遞給服務(wù)器進程的，它告訴服務(wù)器進程對哪個文件進行讀、寫、創(chuàng)建、刪除等操作。參數(shù)bytes告訴服務(wù)器進程有多少個字節(jié)要傳送。參數(shù)position指明了文件從何處開始讀寫。輸出參數(shù)，如read中的buf用作服務(wù)器進程傳遞消息給客戶進程的。buf是文件服務(wù)器存放客戶所需數(shù)據(jù)的地方。輸入/輸出參數(shù)從客戶進程傳遞給服務(wù)器進程，經(jīng)服務(wù)器進程修改后返回給客戶進程。因為服務(wù)器是無狀態(tài)的，所以服務(wù)器不保存客戶的信息，所以就需要position參數(shù)來指明文件從何處開始讀寫。23說明RPC的主要思想。在客戶發(fā)出請求后，客戶機正常，但未收到應(yīng)答，應(yīng)該是那些原因造成的。并說明在服務(wù)器崩潰的情況下，可采用哪些方法處理

40、。主要思想：允許程度去調(diào)用位于其他機器上的過程。當位于機器A的一個進行調(diào)用機器B上的某個過程時，機器A上的該進程被扶起，被調(diào)用的過程在機器B上執(zhí)行。調(diào)用者將消息放在參數(shù)表中傳送給被調(diào)用者，結(jié)果作為過程的返回值給調(diào)用者。原因：客戶無法定位服務(wù)器?？蛻舭l(fā)送給服務(wù)器的請求消息丟失服務(wù)器發(fā)送給客戶的應(yīng)答消息丟失服務(wù)器在收到請求后崩潰客戶機在發(fā)送請求后崩潰。服務(wù)器崩潰的處理方案：1、等待服務(wù)器重新啟動，然后重發(fā)請求。該方法要求不斷重試直至應(yīng)答應(yīng)答消息來到并傳給客戶。這種技術(shù)稱為至少語義，它保證RPC至少執(zhí)行一次，但也有可能執(zhí)行多次。2、立即放棄并報告失敗。它是最多一次語義，確保了RPC最多執(zhí)行一次，但可

41、能沒有執(zhí)行。3、不作任何保證。當服務(wù)器崩潰時，客戶得不到任何幫助和保證。RPC可以不被執(zhí)行或執(zhí)行相當多次。這種方法的最大優(yōu)點就是易于實現(xiàn)。24說明客戶/服務(wù)器模式的主要思想，并說明在采用了阻塞的、有緩存的、可靠的發(fā)送和接收原語的情況下，系統(tǒng)是如何工作的。主要思想：構(gòu)造一種操作系統(tǒng)，它由一組協(xié)同進程組成，這組進程稱作服務(wù)器。為用戶提供服務(wù)的進程稱作客戶，客戶和服務(wù)器都運行在相同的微內(nèi)核中。進程調(diào)用send原語，它指定了目的地以及發(fā)送到該目的地的緩沖區(qū)數(shù)據(jù)。消息被發(fā)送時，發(fā)送的進程被阻塞。直到消息傳送完畢，其后的指令才能繼續(xù)執(zhí)行。之后對接收信息感興趣的進程可以讓內(nèi)核為之建立一個郵箱，并指定一個地址

42、以便于尋找網(wǎng)絡(luò)信包。所有具有該地址的輸入消息被放入郵箱中，調(diào)用receive時只要從郵箱中取出一條消息，郵箱為空時阻塞?？煽康脑Z有三種：重新定義非可靠原語。要求接收機器的內(nèi)核給發(fā)送機器的內(nèi)核發(fā)送一個確認消息。只有當收到這個確認消息后，發(fā)送內(nèi)核釋放用戶進程。客戶機在發(fā)送消息阻塞后，服務(wù)器的內(nèi)核不發(fā)送確認消息，而是將應(yīng)答作為確認消息。25 客戶為了發(fā)送消息給服務(wù)器，它必須知道服務(wù)器的地址，給出三種尋址機制的基本原理，并說明三種機制存在的問題。1.機器、進程編址方式：帶有機器號和進程號，機器號用于使內(nèi)核將消息正確地發(fā)送到適當?shù)臋C器上；進程號用來使內(nèi)核決定消息要給哪一個進程。 缺點：不透明；2.帶有

43、廣播的進程編址：進程在相當大且專用的地址空間中選擇自己的標識號，發(fā)送者廣播一個特殊的定位包，包含目的進程的地址，所有內(nèi)核檢查并察看地址是不是它們的。 缺點：給系統(tǒng)造成額外負擔。3.通過名字服務(wù)器進行地址查詢：在客戶機中存放ASCII服務(wù)器的名字，每次客戶機運行時，首先試圖使用服務(wù)器，客戶機發(fā)出一請求消息給一個特殊映射服務(wù)器，問一個目前服務(wù)器所在的機器號，有了這個地址后，可以直接發(fā)送請求。 缺點：需一個中間部件：26在實現(xiàn)客戶機-服務(wù)器協(xié)議時，需要哪些基本類型的包，說明每種包的源、目的地以及作用，并說明下圖的含義。包：包類型源地址目的地址作用請求REQ客戶服務(wù)器客戶請求服務(wù)器提供服務(wù)應(yīng)答REP服

44、務(wù)器客戶服務(wù)器對客戶應(yīng)答確認ACK客戶、服務(wù)器其他確認正確接受前面的包你在這里嗎AYA客戶服務(wù)器查看服務(wù)器是否崩潰我在這里IAA服務(wù)器客戶服務(wù)器沒有崩潰再試一次TA服務(wù)器客戶服務(wù)器沒有空間地址未知AV服務(wù)器客戶沒有進程在使用此地址圖的含義：客戶向服務(wù)器發(fā)送請求信息，服務(wù)器確認正確接受到請求信息，客戶再次確認服務(wù)器是否崩潰，服務(wù)器回答沒有崩潰，服務(wù)器對客戶請求應(yīng)答，客戶確認收到應(yīng)答。27分布式系統(tǒng)的目標是給用戶一種錯覺，就像使用單一計算機一樣，這需要透明性支持，說明分布式系統(tǒng)支持的各種類型的透明性。位置透明是用戶不知道資源位于何處，在一個真正的分布式系統(tǒng)中，用戶不知道硬、軟件資源如CPU、打印機

45、、文件和數(shù)據(jù)庫的位置。資源的名字不應(yīng)含有資源的位置信息。遷移透明是指資源無須更名就可自由地從一地遷向另一地。復(fù)制透明，系統(tǒng)就可以隨意地為文件和其他資源進行附加拷貝而無須用戶知道。并發(fā)透明，多個用戶可以自動的共享資源，當兩個用戶試圖同時更新相同的文件時，任一用戶不會發(fā)現(xiàn)其他用戶的存在。并行透明，系統(tǒng)活動可以在用戶沒有感覺的情況下并行發(fā)生。從理論上說，一個分布式系統(tǒng)在用戶面前的表現(xiàn)就像一個傳統(tǒng)的但處理機時分系統(tǒng)。系統(tǒng)活動可以再用戶沒有感覺的情況下并行發(fā)生。28詳細分析影響分布式系統(tǒng)規(guī)模（Size）可伸縮性的三個因素，即集中式的服務(wù)、數(shù)據(jù)和算法。試舉例說明分布和復(fù)制技術(shù)是如何提高可伸縮性的。許多服務(wù)

46、是以集中的方式實現(xiàn)的，它們由分布式系統(tǒng)中一臺特定的計算機上運行的單個服務(wù)器來提供。這種方案的問題是：用戶增多時該服務(wù)器將成為系統(tǒng)的瓶頸。即使它擁有無限的處理能力和存儲能力，在系統(tǒng)達到一定規(guī)模后與該服務(wù)器的通信也將發(fā)生困難，從而使得系統(tǒng)規(guī)模無法繼續(xù)增長。集中式數(shù)據(jù)：如果要保存5000萬人的電話號碼和地址，假設(shè)每條數(shù)據(jù)記錄占50個字條，一個2.5GB的硬盤就可以提供足夠的存儲空間。如果只用一個數(shù)據(jù)庫，無疑會使得這個數(shù)據(jù)庫的進出通信線路中都充滿了數(shù)據(jù)。集中式算法：在大型分布式系統(tǒng)中，海量的信息必須在許多線路之間進行跌幅傳送。收集并傳送所有的輸入和輸出信息的做法本身就有弊端，因為這些消息會造成部分網(wǎng)絡(luò)

47、過載。29在分布式操作系統(tǒng)中，說明單內(nèi)核的含義，并說明為什么采用微內(nèi)核技術(shù)，通常微內(nèi)核提供應(yīng)提供哪些服務(wù)？單內(nèi)核：每臺機器都運行一個傳統(tǒng)的內(nèi)核，內(nèi)核自身提供了大多數(shù)的服務(wù)。微內(nèi)核：內(nèi)核盡可能少的提供服務(wù)，大量的操作系統(tǒng)服務(wù)可從用戶級服務(wù)器上獲得。 微內(nèi)核具有更好的靈活性。提供的服務(wù)：1.進程間通信機制 2.某些內(nèi)存管理功能 3.少量的低層進程管理和調(diào)度 4. 低層輸入/輸出服務(wù)。30解決可伸縮性的技術(shù)包括隱藏通信延遲、分布和復(fù)制，試舉例說明分布和復(fù)制技術(shù)是如何解決可伸縮性的。隱藏通信延遲：盡量避免等待遠程服務(wù)對請求的響應(yīng)。例如，當對遠程計算機的某個服務(wù)發(fā)出請求時，在發(fā)出請求端，除了等待服務(wù)器響

48、應(yīng)之外，還可以利用這段時間做其他工作。分布：分布技術(shù)把某個組件分割成多個部件，然后再將它們分散到系統(tǒng)中去。例子：因特網(wǎng)DNS名字空間是由域組成的分層樹狀結(jié)構(gòu)，域又劃分為互不重疊的區(qū)。每個區(qū)內(nèi)的名字都由單個域名服務(wù)器處理。在不涉及太多細節(jié)的情況下，可以把每個路徑名想象成因特網(wǎng)上的主機名，與該主機的網(wǎng)絡(luò)地址相關(guān)。31在分布式系統(tǒng)中，軟件體系結(jié)構(gòu)是一個非常重要的概念，涉及如何組織軟件成分及如何交互等，詳細說明四種Architectural Style。1. 分層體系結(jié)構(gòu)：組件組成了不同的層，其中Li層中的組件可以調(diào)用下面的Li-1。2. 基于對象的體系結(jié)構(gòu)：是一種很松散的組織結(jié)構(gòu)。每個對象都對應(yīng)一個

49、組件，這些組件是通過過程調(diào)用機制來連接的。3. 以數(shù)據(jù)為中心的體系結(jié)構(gòu)：從這種思想發(fā)展而來：進程通信需要通過一個公用倉庫。4. 基于事件的體系結(jié)構(gòu)：進程基本上是通過事件的傳播來通信的，事件傳播還可以有選擇地攜帶數(shù)據(jù)。32客戶機服務(wù)器應(yīng)用可以將軟件成分分為三層，說明每一層的作用，并說明Internet搜索引擎是如何按三層結(jié)構(gòu)組織軟件成分的。（1）用戶接口層：用戶接口層含有直接與用戶交互所需的一切。（2）處理層：處理層通常包含有應(yīng)用程序。（3）數(shù)據(jù)層：數(shù)據(jù)層管理要使用的實際數(shù)據(jù)。 用戶輸入關(guān)鍵字字符串，然后顯示出Web網(wǎng)頁的列表。后端是由一個巨大的Web網(wǎng)頁數(shù)據(jù)庫組成，這些Web網(wǎng)頁是預(yù)取的，且已

50、加索引。搜索引擎的核心是把用戶的關(guān)鍵字字符串轉(zhuǎn)換成HTML頁面列表。在客戶-服務(wù)器模型中，這種信息檢索部分往往放在處理層。33 P2P是典型的非集中式體系結(jié)構(gòu)，說明在結(jié)構(gòu)化P2P系統(tǒng)中如何組織節(jié)點和數(shù)據(jù)，如何查找數(shù)據(jù)，如何進行成員管理。在結(jié)構(gòu)化的點對點體系結(jié)構(gòu)中，覆蓋網(wǎng)絡(luò)是用一個確定性的過程來構(gòu)成的。這個使用最多的進程是通過一個分布式哈希表來組織進程的。在基于DHT的系統(tǒng)中，從一個大的標識符空間中選取一個隨機關(guān)鍵值賦給該數(shù)據(jù)項。同樣從這個標識符空間中選取一個隨機數(shù)賦給該系統(tǒng)中的結(jié)點。根據(jù)某種距離尺度把數(shù)據(jù)項的關(guān)鍵值唯一地映射給結(jié)點的標識符。當查找數(shù)據(jù)項時，會返回對應(yīng)數(shù)據(jù)項的結(jié)點的網(wǎng)絡(luò)地址。這可以通過把數(shù)據(jù)項的請求跌幅給相應(yīng)的結(jié)點來完成。如果某個結(jié)點要加入該系統(tǒng)，它首先生成一個隨機標識符id。然后，結(jié)點就可以進行一個對id的查找，返回網(wǎng)絡(luò)地址succ(id)