【正文】 解決死鎖。如果消息又回到最初的發(fā)送者說(shuō)明存在一個(gè)又死鎖的環(huán)路系統(tǒng)解除死鎖的方法：1）令最初發(fā)送探測(cè)消息的進(jìn)程自殺。在RPC過(guò)程中，主機(jī)崩潰后產(chǎn)生的情況如下：1）主機(jī)在執(zhí)行任務(wù)前崩潰，則沒(méi)有損失，客戶(hù)端會(huì)超時(shí)重發(fā)直到連上后備機(jī)，任務(wù)至執(zhí)行一次；2）主機(jī)在執(zhí)行任務(wù)后，向后備機(jī)發(fā)送跟新消息前崩潰，此時(shí)后備機(jī)接管，消息再次到來(lái)，任務(wù)被執(zhí)行2次；3）主機(jī)在后備機(jī)執(zhí)行任務(wù)后自己發(fā)送相應(yīng)消息前崩潰，則任務(wù)被執(zhí)行3次，一次由主機(jī)完成，一次由后備機(jī)完成，一次由后備機(jī)接管時(shí)完成。答：Lamport等人設(shè)計(jì)了一種遞歸算法可在特定條件下解決這一問(wèn)題。兩者比較如下：1）靜態(tài)調(diào)度適合時(shí)間觸發(fā)系統(tǒng)的設(shè)計(jì)，動(dòng)態(tài)調(diào)度適合事件觸發(fā)系統(tǒng)的設(shè)計(jì)；2）在資源利用方面動(dòng)態(tài)調(diào)度比靜態(tài)調(diào)度有更大潛力；3）若給定足夠的處理能力，對(duì)靜態(tài)系統(tǒng)一個(gè)最優(yōu)或次優(yōu)的調(diào)度可以事先獲得，動(dòng)態(tài)系統(tǒng)在運(yùn)行期間無(wú)法承受復(fù)雜的調(diào)度計(jì)算花費(fèi)。，并舉例說(shuō)明三模冗余能否處理Byzabtine故障。從數(shù)學(xué)角度看，整個(gè)問(wèn)題就變成了如何根據(jù)特定的限制將圖劃分成k（k為系統(tǒng)中cpu數(shù)量）個(gè)不相連的子圖（如每個(gè)子圖的總cpu和內(nèi)存需求在一定限制內(nèi)）。假定電梯正在60層安靜的等待顧客，有人在一層按下按鈕。上載/下載模式。優(yōu)點(diǎn)是客戶(hù)不需要大量存儲(chǔ)空間，當(dāng)需要部分文件是不需要傳輸整個(gè)文件。只能進(jìn)程講的的共享和復(fù)制。4）集中控制，就是在文件服務(wù)器上保存了進(jìn)程對(duì)文件的操作方式等信息，類(lèi)似于鎖機(jī)制的管理，避免寫(xiě)操作的文件被其他進(jìn)程操作，但是當(dāng)修改的操作結(jié)束時(shí)，會(huì)將操作結(jié)束消息通知服務(wù)器，操作的結(jié)果也就立即會(huì)送到服務(wù)器。這種方法簡(jiǎn)單，但是有個(gè)問(wèn)題，當(dāng)主服務(wù)器停機(jī)時(shí)，所有的更細(xì)將不能進(jìn)行。通寫(xiě)協(xié)議易于理解和使用。順序一致性所允許的6種語(yǔ)句交叉執(zhí)行情況：a = 1。if(a == 0) kill(P1)if(b == 0) kill(P2)a = 1。答：錯(cuò)誤共享是指無(wú)關(guān)的變量出現(xiàn)在同一頁(yè)上，當(dāng)一進(jìn)程使用它們之一時(shí)，進(jìn)程也得到了其他變量。圖（a）給出了處理機(jī)1上的進(jìn)程P要讀一頁(yè)的六種情況。在所有的六例中，在寫(xiě)操作執(zhí)行以前，協(xié)議保證要寫(xiě)得進(jìn)程的地址空間中只有頁(yè)的一個(gè)拷貝存在，這樣可以保證一致性。消息傳送完成后，頁(yè)管理者對(duì)頁(yè)的擁有者做出改變，同時(shí)設(shè)置無(wú)效頁(yè)。四消息方法，申請(qǐng)者向頁(yè)管理者提交請(qǐng)求，頁(yè)管理者返回消息指出擁有者是誰(shuí)。圖（b）給出了處理機(jī)1上的進(jìn)程P要寫(xiě)一頁(yè)的六種情況，第一種情況，因?yàn)轫?yè)映射為只讀模式嗎，所以寫(xiě)操作只是發(fā)生了，而不激活陷阱程序；第二種情況，也被改為W狀態(tài)，并寫(xiě)入；第三種情況，該頁(yè)有其他拷貝，所以在寫(xiě)以前，必須先置無(wú)效這些拷貝。圖中所示的情況會(huì)發(fā)生錯(cuò)誤共享，因?yàn)閮蓚€(gè)變量A和B恰好位于基于分頁(yè)的DSM系統(tǒng)的同一頁(yè)上，即使不是共享變量，由于他們出現(xiàn)在同一頁(yè)上，當(dāng)一進(jìn)程使用它們之一時(shí)，進(jìn)程也得到了另一個(gè)變量，因此發(fā)生錯(cuò)誤共享。if(b == 0) kill(P2)。if(b == 0) kill(P2)if(a == 0) kill(P1)a = 1。；在如下并行執(zhí)行的進(jìn)程P1和P2，列出順序一致性所允許的6種語(yǔ)句交叉執(zhí)行情況。 once協(xié)議。3）用組復(fù)制文件，如圖c所示，所有的寫(xiě)系統(tǒng)調(diào)用同時(shí)傳送到所有的服務(wù)器，于是，其他的拷貝在源文件產(chǎn)生時(shí)就產(chǎn)生了。答：1）直接寫(xiě)，當(dāng)緩存中的文件被更新后，新的值在緩存在保存，而且同時(shí)發(fā)送到服務(wù)器，而當(dāng)另外的進(jìn)程訪問(wèn)文件時(shí)，讀到的是最新值，但是存在一個(gè)問(wèn)題，其他進(jìn)程在更新之前讀到的文件內(nèi)容可能是過(guò)期的，那么在每次用到文件時(shí)需要從服務(wù)器中讀取文件版本進(jìn)行比較，查看是否過(guò)期，但是每次都要在服務(wù)器和客戶(hù)端之間通信，這樣就體現(xiàn)不出緩存的作用了。2）會(huì)話語(yǔ)義。缺點(diǎn)是客戶(hù)端需要足夠的存儲(chǔ)空間，當(dāng)需要部分文件是需要傳輸整個(gè)文件。若兩次按下按鈕都在一次采樣周期中出現(xiàn)，控制器就不得不進(jìn)行決定，例如按最近用戶(hù)優(yōu)先原則，此時(shí)電梯將上行。下圖表示了圖的兩種劃分:方案A:通信量=(3＋2＋4＋4)＋(2＋8＋5＋2)＝30方案B:通信量=(3＋2＋4＋4)＋(3＋5＋5＋2)＝28。最壞情況下k個(gè)失效的處理機(jī)偶然（甚至有意）地產(chǎn)生相同的應(yīng)答，然而剩下的k+1個(gè)未出錯(cuò)的處理機(jī)也將產(chǎn)生相同的應(yīng)答，因此客戶(hù)機(jī)可以根據(jù)大多數(shù)的應(yīng)答得到正確結(jié)果。如果系統(tǒng)在k個(gè)部件出錯(cuò)時(shí)仍能達(dá)到系統(tǒng)設(shè)計(jì)的要求而正常工作，那么這個(gè)系統(tǒng)稱(chēng)為是k級(jí)容錯(cuò)的。A—J。對(duì)于這樣的錯(cuò)誤，需要K+1個(gè)這樣的處理機(jī)以滿(mǎn)足K容錯(cuò)要求，因?yàn)槿鬕個(gè)處理機(jī)停止工作，那么剩下的那個(gè)處理機(jī)繼續(xù)工作。接收者發(fā)起的分布式啟發(fā)算法：當(dāng)一個(gè)進(jìn)程結(jié)束時(shí)，系統(tǒng)將檢查自己是否有足夠的工作可做，如果沒(méi)有，將隨機(jī)向一臺(tái)機(jī)器申請(qǐng)工作，如果那臺(tái)機(jī)器沒(méi)有要給予的工作，系統(tǒng)將繼續(xù)詢(xún)問(wèn)第二，第三臺(tái)機(jī)器，如果詢(xún)問(wèn)N臺(tái)機(jī)器都沒(méi)有申請(qǐng)到工作，系統(tǒng)將暫停申請(qǐng)開(kāi)始處理系統(tǒng)隊(duì)列中一個(gè)等待進(jìn)程，當(dāng)這個(gè)進(jìn)程結(jié)束后，開(kāi)始下一輪的申請(qǐng)；如果系統(tǒng)無(wú)事可做，則將進(jìn)入空閑狀態(tài)，一定時(shí)間后從新開(kāi)始申請(qǐng)。答：算法允許進(jìn)程一次請(qǐng)求多個(gè)資源，例如下圖所示的資源圖。在準(zhǔn)備提交階段，協(xié)調(diào)者向日志中寫(xiě)入Prepare，然后向所有服務(wù)器發(fā)送準(zhǔn)備提交消息，服務(wù)器接收到消息后，檢查自己是否準(zhǔn)備提交，如果是就向日志中寫(xiě)入Ready，然后向協(xié)調(diào)者發(fā)送準(zhǔn)備好消息。除了一個(gè)進(jìn)程外的其他進(jìn)程都放棄了，那么這個(gè)進(jìn)程就是新的協(xié)調(diào)者，它將選舉獲勝的消息發(fā)送給所有進(jìn)程，告知它是新的協(xié)調(diào)者。答：RICART和AGRAWALE算法要求系統(tǒng)中所有事件都是全序的，也就是說(shuō)，對(duì)任何事件組消息，哪個(gè)先發(fā)必須無(wú)歧義，算法如下：當(dāng)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，他要建立一個(gè)包括他要進(jìn)入的臨界區(qū)的名字、處理機(jī)號(hào)、當(dāng)前時(shí)間的消息，然后將消息發(fā)送給所有其他進(jìn)程，也包括發(fā)送給自身，當(dāng)一個(gè)進(jìn)程接收另一個(gè)進(jìn)程消息時(shí)，它取決于接受方的狀態(tài)以及臨界區(qū)的名字有三種情況：1）接受者不在臨界區(qū)，也不想進(jìn)入臨界區(qū)，他就向發(fā)送者發(fā)送OK消息；2）接受者已經(jīng)在臨界區(qū)，它不必回答，而是負(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è)。？說(shuō)明先發(fā)生關(guān)系，并說(shuō)明在LAMPORT算法中怎樣給事件分配時(shí)間。答：每組分配地址，有三種方式：?jiǎn)尾?，多播，廣播，發(fā)送進(jìn)程將消息發(fā)送給組地址，消息將會(huì)發(fā)布給所有成員要求發(fā)送端提供一份目的地址的顯示列表；判定編址，消息將被發(fā)送給所有成員，每條消息包含了判定條件，如果判定條件評(píng)估為T(mén)RUE，則消息被接受，否則消息丟棄。，試說(shuō)明在那些環(huán)節(jié)需要拷貝，并說(shuō)明減少拷貝次數(shù)的方法。主要步驟如下：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)核將消息發(fā)送到服務(wù)器存根；5）服務(wù)器存根取出消息中的參數(shù)后調(diào)用服務(wù)器過(guò)程；6）服務(wù)器完成工作后將結(jié)果返回至服務(wù)器存根；7）服務(wù)器存根將它們打包并激活內(nèi)核陷阱；8）遠(yuǎn)程內(nèi)核將消息發(fā)送會(huì)客戶(hù)內(nèi)核；9）客戶(hù)內(nèi)核將消息提交給客戶(hù)存根；10）客戶(hù)存根從消息中取出結(jié)果返回給客戶(hù)。確認(rèn)消息從一個(gè)內(nèi)核傳送到另一個(gè)內(nèi)核，無(wú)論是客戶(hù)還是服務(wù)器都看不到確認(rèn)消息?？蛻?hù)機(jī)運(yùn)行時(shí)，向名字服務(wù)器發(fā)送請(qǐng)求信息，名字服務(wù)器將ASCII服務(wù)器名映射成服務(wù)器地址，客戶(hù)機(jī)收到給地址后，可以訪問(wèn)服務(wù)器。試給出服務(wù)器進(jìn)程編址的幾種方法，并說(shuō)明如何定位進(jìn)程。舉例見(jiàn)書(shū)p189。10. 什么是有狀態(tài)服務(wù)器和無(wú)狀態(tài)服務(wù)器，給出相應(yīng)的例子，并說(shuō)明有狀態(tài)服務(wù)器存在的問(wèn)題。因?yàn)橐粋€(gè)HTML文件可能包含文本，圖像，音頻，視頻等文件，故當(dāng)一個(gè)線程獲得其中一個(gè)文件并顯示它時(shí)，同時(shí)還有其它線程正從服務(wù)器讀取其它文件。家庭普適系統(tǒng)，即將各種家用電子設(shè)備（如電視，手機(jī)等）整合在一起的系統(tǒng)。具體說(shuō)來(lái)，就是隱藏了多個(gè)計(jì)算機(jī)的處理過(guò)程，資源的物理分布。基于總線的多處理機(jī)系統(tǒng)包含多個(gè)連接到一條公共總線的CPU以及一個(gè)存儲(chǔ)器模塊。2011 遼寧大學(xué)分布式操作系統(tǒng)復(fù)習(xí)題1. 說(shuō)明分布式系統(tǒng)相對(duì)于集中式系統(tǒng)的優(yōu)點(diǎn)和缺點(diǎn)?；诮粨Q的多處理機(jī)系統(tǒng)是把存儲(chǔ)器劃分為若干個(gè)模塊，通過(guò)縱橫式交換器將這些存儲(chǔ)器模