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

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

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

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

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

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

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

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

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

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

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

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

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

13、件服務(wù)器傳送到提出請(qǐng)求的客戶(hù)；寫(xiě)操作是將整個(gè)文件從客戶(hù)傳送到服務(wù)器。優(yōu)點(diǎn)：概念簡(jiǎn)單。使用這種模式不需要掌握復(fù)雜的文件接口，而且整個(gè)文件傳送也是高效的。缺點(diǎn)：客戶(hù)端必具有足夠大的存儲(chǔ)空間來(lái)存儲(chǔ)所需的所有文件。如果只需要文件的一小部分，移動(dòng)整個(gè)文件是很浪費(fèi)的。遠(yuǎn)程訪(fǎng)問(wèn)模式：文件服務(wù)提供了大量的操作用于打開(kāi)和關(guān)閉文件，讀寫(xiě)文件的一部分，在文件中來(lái)回移動(dòng)，檢查和改變文件屬性等。優(yōu)點(diǎn)：在客戶(hù)端不需要很大的空間，當(dāng)僅需要文件的一小部分時(shí)，不需要傳送整個(gè)文件。7 分布式協(xié)同一致算法的目標(biāo)是使所有無(wú)故障處理機(jī)對(duì)待某些問(wèn)題的意見(jiàn)達(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會(huì)得出結(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è)例子，并說(shuō)明為什么動(dòng)態(tài)調(diào)度適合于事件觸發(fā)系統(tǒng)，給出三種動(dòng)態(tài)調(diào)度算法。事件觸發(fā)系統(tǒng)：當(dāng)一個(gè)重要的外部事件觸發(fā)時(shí)，它被傳感器察覺(jué)到，并導(dǎo)致與傳感器相連的CPU得到一個(gè)中斷請(qǐng)求。時(shí)間觸發(fā)系統(tǒng)：每t毫秒產(chǎn)生一次時(shí)鐘中斷，在每一次時(shí)鐘滴答時(shí)，對(duì)傳感器進(jìn)行采樣，并驅(qū)動(dòng)執(zhí)行機(jī)構(gòu)。中斷僅在時(shí)鐘滴答時(shí)發(fā)生。例：考慮對(duì)一個(gè)100層樓的電梯控制器的設(shè)計(jì)。假定電梯在60層等客人。有

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

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

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

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

20、，在主服務(wù)器崩潰后，只正確執(zhí)行一次請(qǐng)求消息的處理是非常困難的。解決辦法：是使用主機(jī)和備份機(jī)之間共享的兩端口磁盤(pán)。在這種配置下，當(dāng)主機(jī)得到一個(gè)請(qǐng)求后，在做任何事之前先將請(qǐng)求寫(xiě)入磁盤(pán)，并且也把執(zhí)行的結(jié)果寫(xiě)人磁盤(pán)，不再需要向備份機(jī)發(fā)送消息并接收從備份機(jī)發(fā)來(lái)的消息了，若主機(jī)崩潰，備份機(jī)可通過(guò)讀磁盤(pán)而得到整個(gè)系統(tǒng)現(xiàn)在的狀態(tài)。11一個(gè)典型的集中的、啟發(fā)式的處理機(jī)分配算法，即上-下算法。說(shuō)明該算法的目標(biāo)，并說(shuō)明該算法的主要原理。目標(biāo)：讓一個(gè)等了很久的，沒(méi)有使用任何處理機(jī)的申請(qǐng)優(yōu)先于已經(jīng)占用了許多多處理機(jī)的申請(qǐng)。此為該算法的目標(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)程請(qǐng)求處理機(jī)、處理機(jī)進(jìn)入空閑狀態(tài)或者是發(fā)生了時(shí)鐘中斷。使用情況表中的記錄值可以為整數(shù)、零或是負(fù)數(shù)。整數(shù)表示用戶(hù)純粹是在使用系統(tǒng)資源，負(fù)數(shù)表示用戶(hù)需要系統(tǒng)資源，零則介于兩者中間。12 在支持多線(xiàn)程的系統(tǒng)中，可采用三種模型來(lái)組織多線(xiàn)程，詳細(xì)說(shuō)明這三種模型。如果在不支持多線(xiàn)程系統(tǒng)中實(shí)現(xiàn)文件服務(wù)，如何構(gòu)造文件服務(wù)器。派遣者/工作者模型: 某一個(gè)線(xiàn)程作為派遣者，它從系統(tǒng)郵箱內(nèi)讀出輸入請(qǐng)求，然后檢查請(qǐng)求，選擇一個(gè)空閑的工作者線(xiàn)程去處理它。然后派遣

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

23、請(qǐng)求到來(lái)前完成它。當(dāng)文件服務(wù)器等待磁盤(pán)操作時(shí)，它是空閑的且不處理另一請(qǐng)求，如果文件服務(wù)器運(yùn)行于一個(gè)專(zhuān)用的機(jī)器上，當(dāng)文件服務(wù)器等待磁盤(pán)時(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所擁有的資源，畫(huà)出簡(jiǎn)化的資源圖并說(shuō)明用Chandy-Misra-Hass提出的分布式死鎖檢測(cè)算法如何檢測(cè)死鎖，并打破死鎖。檢測(cè)死鎖：當(dāng)某個(gè)進(jìn)程等待資源時(shí)，例如進(jìn)程0等待進(jìn)程1。此時(shí)，生成一個(gè)特殊的探測(cè)消息并發(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)程號(hào)，第三個(gè)字段改為等待的進(jìn)程號(hào)。然后消息接著被發(fā)送到等待的進(jìn)程。如果在等待多個(gè)進(jìn)程，就需要發(fā)送多個(gè)不同的消息。不論資源時(shí)在本地還是在遠(yuǎn)程，該算法都要繼續(xù)下去。如果消息轉(zhuǎn)了一圈后又回到了最初的發(fā)送者，那么就說(shuō)明存在一個(gè)有死鎖的環(huán)路系統(tǒng)。打破死鎖：1.令最初發(fā)送探測(cè)消息的進(jìn)程自殺。但是如果多個(gè)進(jìn)程同時(shí)阻塞，同時(shí)發(fā)送探測(cè)消息，那么每個(gè)進(jìn)程都會(huì)發(fā)現(xiàn)死鎖，并因此而自殺。2.

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

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

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

28、互斥算法；假定A和B是相互獨(dú)立的兩個(gè)臨界區(qū)，進(jìn)程0按A、B順序進(jìn)入，進(jìn)程1按B、A順序進(jìn)入，R-A分布式互斥算法會(huì)導(dǎo)致死鎖嗎？說(shuō)明理由。RICART和AGRAWALE算法要求系統(tǒng)中所有事件都是全序的，也就是說(shuō)，對(duì)任何事件組消息哪個(gè)先發(fā)生哪個(gè)后發(fā)生必須無(wú)歧義，算法如下：（1）當(dāng)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，他要建立一個(gè)包括它要進(jìn)入的臨界區(qū)的名字、處理機(jī)號(hào)、當(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ì)請(qǐng)求隊(duì)列排隊(duì)。3接收者要進(jìn)入臨界區(qū)，但是還沒(méi)有進(jìn)入，它要負(fù)責(zé)將發(fā)來(lái)的消息和它發(fā)送給其他進(jìn)程的時(shí)間戳對(duì)比，取小的那個(gè)。如果來(lái)的消息時(shí)間戳小，接收者發(fā)送OK消息，否則接收者負(fù)責(zé)排列請(qǐng)求隊(duì)列而不發(fā)送任何消息。（3）在發(fā)送完允許進(jìn)入臨界區(qū)的請(qǐng)求后，進(jìn)程將不再做任何事，僅等待所有的允許消息，一旦得到允許它就進(jìn)入臨界區(qū)。（4）它從臨界區(qū)退出時(shí)向隊(duì)列中所有進(jìn)程發(fā)送OK消息，并將它從隊(duì)列中刪除。不會(huì)導(dǎo)致死鎖。進(jìn)程0、1分別進(jìn)入A、B臨界區(qū)，假設(shè)進(jìn)程0先在A中執(zhí)行完后，退出A臨界區(qū)，并發(fā)送ok消息給所有的等待進(jìn)程，之后申請(qǐng)臨界區(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的請(qǐng)求從隊(duì)列中取出，并向進(jìn)程0發(fā)送OK，允許進(jìn)程0進(jìn)入臨界區(qū)B，自己再去申請(qǐng)進(jìn)入臨界區(qū)A.所以不會(huì)產(chǎn)生死鎖。17在分布式系統(tǒng)中，許多算法都需要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者，因此需要協(xié)調(diào)者選舉算法。試說(shuō)明欺負(fù)算法的主要思想，并說(shuō)明在8個(gè)進(jìn)程的情況下號(hào)碼為3的進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者崩潰后的選舉過(guò)程。欺負(fù)算法：當(dāng)一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請(qǐng)求時(shí)，它發(fā)起選舉。進(jìn)程P選舉過(guò)程如下： P向所有號(hào)碼比它大的進(jìn)程發(fā)送選舉消息 若無(wú)人響應(yīng)，P獲勝成為協(xié)調(diào)者。 若有號(hà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首先申請(qǐng)資源S，之后P 1，P2，P3 隨后申請(qǐng)資源S，試說(shuō)明采用集中式的算法是如何實(shí)現(xiàn)互斥的。首先選擇一個(gè)進(jìn)程為協(xié)調(diào)者。無(wú)論什么時(shí)候進(jìn)程要進(jìn)入臨界區(qū)，它向協(xié)調(diào)者發(fā)送請(qǐng)求消息，說(shuō)明它想進(jìn)入哪個(gè)臨界區(qū)并希望獲得允許。如果當(dāng)前該臨界區(qū)內(nèi)沒(méi)有其他任何進(jìn)程，協(xié)調(diào)者就發(fā)出允許進(jìn)入消息。如當(dāng)P0請(qǐng)求資源S時(shí)，當(dāng)應(yīng)答到達(dá)時(shí)，P0就可以進(jìn)入臨界區(qū)。此時(shí)若P1請(qǐng)求資源S，協(xié)調(diào)者知道該臨界區(qū)

32、已經(jīng)有一個(gè)進(jìn)程，所以不能同意P1的請(qǐng)求。此時(shí)協(xié)調(diào)者可以發(fā)送“拒絕請(qǐng)求”應(yīng)答，把進(jìn)程2的請(qǐng)求臨時(shí)排在隊(duì)列中。或者協(xié)調(diào)者回避應(yīng)答，這樣就阻塞了進(jìn)程2，使它等待應(yīng)答。 當(dāng)進(jìn)程P1從臨界區(qū)退出時(shí)，它向協(xié)調(diào)者發(fā)送釋放互斥消息的訪(fǎng)問(wèn)，此時(shí)協(xié)調(diào)者從推遲請(qǐng)求隊(duì)列中取出最前面的進(jìn)程即P2，向它發(fā)送允許進(jìn)入消息。如果該進(jìn)程仍然阻塞，它不被阻塞且進(jìn)入臨界區(qū)。如果明確發(fā)送一消息拒絕它進(jìn)入臨界區(qū)，此進(jìn)程應(yīng)該查詢(xún)輸入的消息，或者接著將它阻塞，不管怎么樣，當(dāng)它發(fā)現(xiàn)允許進(jìn)入時(shí)，它還可以進(jìn)入臨界區(qū)。如果進(jìn)程在阻塞狀態(tài)，它就會(huì)被喚醒進(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下），舉例說(shuō)明進(jìn)程之間消息傳遞中違反先發(fā)生關(guān)系的情況，并說(shuō)明如何用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í)刻離開(kāi)，56時(shí)刻到達(dá)。同理，消息D從進(jìn)程1到進(jìn)程0是在64時(shí)序離開(kāi)，54時(shí)刻到達(dá)，這是絕對(duì)不可能出現(xiàn)的。Lamport的解決方案是：因?yàn)镃在60時(shí)刻離開(kāi)，只能在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è)例子，并說(shuō)明物理時(shí)鐘同步的三種算法，Cristian 算法、Berkeley算法及平均值算法。例子：導(dǎo)彈發(fā)射，不同的控制站必須同步時(shí)鐘，否則無(wú)法準(zhǔn)確的控制導(dǎo)彈的發(fā)送時(shí)間及導(dǎo)彈運(yùn)行軌道。Cristian 算法：每臺(tái)機(jī)器以小于或等于/2秒的周期定期地向時(shí)間服務(wù)器發(fā)送消息詢(xún)問(wèn)當(dāng)前的時(shí)間，時(shí)間服務(wù)器接到消息后就盡快回答含有當(dāng)前時(shí)間CUTC值的消息。Berkeley算法：時(shí)間守護(hù)進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

48、應(yīng)之外，還可以利用這段時(shí)間做其他工作。分布：分布技術(shù)把某個(gè)組件分割成多個(gè)部件，然后再將它們分散到系統(tǒng)中去。例子：因特網(wǎng)DNS名字空間是由域組成的分層樹(shù)狀結(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ì)說(shuō)明四種Architectural Style。1. 分層體系結(jié)構(gòu)：組件組成了不同的層，其中Li層中的組件可以調(diào)用下面的Li-1。2. 基于對(duì)象的體系結(jié)構(gòu)：是一種很松散的組織結(jié)構(gòu)。每個(gè)對(duì)象都對(duì)應(yīng)一個(gè)

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

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