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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、請求到來前完成它。當文件服務器等待磁盤操作時，它是空閑的且不處理另一請求，如果文件服務器運行于一個專用的機器上，當文件服務器等待磁盤時，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。此時，生成一個特殊的探測消息并發送給占用資源的進程。消

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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