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

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

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

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，同時(shí)C2監(jiān)聽到寫請求，將自己緩存中的W1置為無效。C3讀該字，C1發(fā)現(xiàn)讀請求發(fā)信號禁止存儲器響應(yīng)，C1向C3提供該字并將自己的項(xiàng)置為無效，C3發(fā)現(xiàn)該字來自其他緩存其狀態(tài)置為臟，并將自己緩存項(xiàng)標(biāo)記為臟。C4讀該字，C3發(fā)現(xiàn)讀請求禁止存儲器響應(yīng)，并向C4提供該字，并且將自己的項(xiàng)置為無效。C4發(fā)現(xiàn)該字來自其他緩存，其狀態(tài)為臟，則標(biāo)記自己緩存項(xiàng)為臟。3在分布式系統(tǒng)，為了獲得文件讀寫

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

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

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

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

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

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

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

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

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

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

14、，給出算法的具體步驟。假設(shè)：正常處理機(jī)為：ABC。錯(cuò)誤處理機(jī)為：DE。1. 每個(gè)處理發(fā)送消息給其它處理機(jī)消息：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. 每個(gè)處理現(xiàn)將各自的向量傳遞給其它處理機(jī)。A：（1，2，3，y1，y2）（1，2，3，z1，z2）（1，2，3，4，m2）（1，2，3，m1，5）每個(gè)處理機(jī)檢查所有接收向量的第i個(gè)元素。若某個(gè)值占多數(shù)，放入結(jié)果向量中，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、組件，這些組件是通過過程調(diào)用機(jī)制來連接的。3. 以數(shù)據(jù)為中心的體系結(jié)構(gòu)：從這種思想發(fā)展而來：進(jìn)程通信需要通過一個(gè)公用倉庫。4. 基于事件的體系結(jié)構(gòu)：進(jìn)程基本上是通過事件的傳播來通信的，事件傳播還可以有選擇地?cái)y帶數(shù)據(jù)。32客戶機(jī)服務(wù)器應(yīng)用可以將軟件成分分為三層，說明每一層的作用，并說明Internet搜索引擎是如何按三層結(jié)構(gòu)組織軟件成分的。（1）用戶接口層：用戶接口層含有直接與用戶交互所需的一切。（2）處理層：處理層通常包含有應(yīng)用程序。（3）數(shù)據(jù)層：數(shù)據(jù)層管理要使用的實(shí)際數(shù)據(jù)。 用戶輸入關(guān)鍵字字符串，然后顯示出Web網(wǎng)頁的列表。后端是由一個(gè)巨大的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é)點(diǎn)和數(shù)據(jù)，如何查找數(shù)據(jù)，如何進(jìn)行成員管理。在結(jié)構(gòu)化的點(diǎn)對點(diǎn)體系結(jié)構(gòu)中，覆蓋網(wǎng)絡(luò)是用一個(gè)確定性的過程來構(gòu)成的。這個(gè)使用最多的進(jìn)程是通過一個(gè)分布式哈希表來組織進(jìn)程的。在基于DHT的系統(tǒng)中，從一個(gè)大的標(biāo)識符空間中選取一個(gè)隨機(jī)關(guān)鍵值賦給該數(shù)據(jù)項(xiàng)。同樣從這個(gè)標(biāo)識符空間中選取一個(gè)隨機(jī)數(shù)賦給該系統(tǒng)中的結(jié)點(diǎn)。根據(jù)某種距離尺度把數(shù)據(jù)項(xiàng)的關(guān)鍵值唯一地映射給結(jié)點(diǎn)的標(biāo)識符。當(dāng)查找數(shù)據(jù)項(xiàng)時(shí)，會返回對應(yīng)數(shù)據(jù)項(xiàng)的結(jié)點(diǎn)的網(wǎng)絡(luò)地址。這可以通過把數(shù)據(jù)項(xiàng)的請求跌幅給相應(yīng)的結(jié)點(diǎn)來完成。如果某個(gè)結(jié)點(diǎn)要加入該系統(tǒng)，它首先生成一個(gè)隨機(jī)標(biāo)識符id。然后，結(jié)點(diǎn)就可以進(jìn)行一個(gè)對id的查找，返回網(wǎng)絡(luò)地址succ(id)