【文章內(nèi)容簡(jiǎn)介】 如上圖圓表示進(jìn)程，方框表示資源，開始時(shí)如同a，b，c所示，過來一段時(shí)間，B釋放R并請(qǐng)求T，這是一個(gè)合法的操作，機(jī)器0向協(xié)調(diào)者發(fā)送一條消息申明它釋放資源R，機(jī)器1向協(xié)調(diào)者發(fā)送一條消息聲明進(jìn)程B正在等待它的資源T，不幸的是機(jī)器1的消息先到達(dá)協(xié)調(diào)者，導(dǎo)致生成資源圖如圖d所示。協(xié)調(diào)者得出錯(cuò)誤的結(jié)論——死鎖存在，這種情況稱為假死鎖。解決辦法是：使用Lamport算法以提供全局統(tǒng)一的時(shí)間，對(duì)協(xié)調(diào)者收到的消息按照時(shí)間戳排序。答：算法允許進(jìn)程一次請(qǐng)求多個(gè)資源，例如下圖所示的資源圖。圖中只給出進(jìn)程，每條弧穿過一個(gè)資源，當(dāng)某個(gè)進(jìn)程等待資源時(shí)，生成一個(gè)探測(cè)消息（阻塞的進(jìn)程，發(fā)送消息的進(jìn)程，接收消息的進(jìn)程）發(fā)送給占用資源的進(jìn)程。消息到達(dá)后，如果接受者也在等待其他進(jìn)程占用的資源，則跟新探測(cè)消息，第一個(gè)字段保持不變，第二個(gè)字段改為當(dāng)前的進(jìn)程號(hào)，第三個(gè)字段改為等待的進(jìn)程號(hào)，跟新后的探測(cè)消息發(fā)送給等待的占有資源的進(jìn)程。如果存在多個(gè)進(jìn)程則要發(fā)送多個(gè)不同的消息。如果消息又回到最初的發(fā)送者說明存在一個(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）將每個(gè)進(jìn)程的標(biāo)識(shí)符添加到探測(cè)消息的末尾，將編號(hào)最大的進(jìn)程中止或者發(fā)送消息請(qǐng)求的進(jìn)程自殺。多個(gè)進(jìn)程發(fā)現(xiàn)同一環(huán)路會(huì)選擇同一個(gè)犧牲者。事務(wù)時(shí)間戳為50的進(jìn)程申請(qǐng)事務(wù)時(shí)間戳為100的進(jìn)程占用的資源。按以上兩種策略，結(jié)果會(huì)如何? 答：（時(shí)間戳越小的進(jìn)程越是年老）waitdie死鎖預(yù)防算法：當(dāng)較老的進(jìn)程請(qǐng)求年輕進(jìn)程所占有的資源時(shí)，老進(jìn)程只能等待；如果年輕進(jìn)程請(qǐng)求老進(jìn)程占有的資源時(shí)，年輕進(jìn)程會(huì)被終止。Woundwait死鎖預(yù)防算法：當(dāng)老進(jìn)程請(qǐng)求年輕進(jìn)程所擁有的資源時(shí)，老進(jìn)程搶占年輕進(jìn)程的資源，年輕進(jìn)程被終止；當(dāng)年輕進(jìn)程請(qǐng)求老進(jìn)程所擁有的資源時(shí)，年輕進(jìn)程等待。答：發(fā)送者發(fā)起的分布式啟發(fā)算法：當(dāng)創(chuàng)建進(jìn)程時(shí)，創(chuàng)建進(jìn)程的機(jī)器將對(duì)一個(gè)隨機(jī)選取的機(jī)器發(fā)生詢問，詢問它的負(fù)載是否低于某個(gè)閾值，如果是，將發(fā)送進(jìn)程否則將選擇另一臺(tái)機(jī)子發(fā)送詢問。如果在N次詢問內(nèi)還沒有找到合適的機(jī)器，算法停止新進(jìn)程將在創(chuàng)建它的機(jī)器上運(yùn)行。該算法的缺點(diǎn)是：在負(fù)載十分嚴(yán)重的情況下，所有機(jī)器都會(huì)不停的毫無意義的向其他機(jī)器發(fā)送詢問，想找到一臺(tái)愿意接受更多工作的機(jī)器，在這種情況下，幾乎沒有進(jìn)程會(huì)被減輕負(fù)載，但卻會(huì)引起相當(dāng)可觀的額外開銷。接收者發(fā)起的分布式啟發(fā)算法：當(dāng)一個(gè)進(jìn)程結(jié)束時(shí)，系統(tǒng)將檢查自己是否有足夠的工作可做，如果沒有，將隨機(jī)向一臺(tái)機(jī)器申請(qǐng)工作，如果那臺(tái)機(jī)器沒有要給予的工作，系統(tǒng)將繼續(xù)詢問第二，第三臺(tái)機(jī)器，如果詢問N臺(tái)機(jī)器都沒有申請(qǐng)到工作，系統(tǒng)將暫停申請(qǐng)開始處理系統(tǒng)隊(duì)列中一個(gè)等待進(jìn)程，當(dāng)這個(gè)進(jìn)程結(jié)束后，開始下一輪的申請(qǐng)；如果系統(tǒng)無事可做，則將進(jìn)入空閑狀態(tài)，一定時(shí)間后從新開始申請(qǐng)。給算法的缺點(diǎn)是：系統(tǒng)在無事可做時(shí)會(huì)造成相當(dāng)大的詢問負(fù)載。，在主機(jī)崩潰后存在的問題及解決方法。答：主機(jī)后備容錯(cuò)方法的主要思想是在任何時(shí)候，服務(wù)器都由主機(jī)完成所有工作，如果主機(jī)失效，則由后備機(jī)接管工作。在RPC過程中，主機(jī)崩潰后產(chǎn)生的情況如下：1）主機(jī)在執(zhí)行任務(wù)前崩潰，則沒有損失，客戶端會(huì)超時(shí)重發(fā)直到連上后備機(jī)，任務(wù)至執(zhí)行一次；2）主機(jī)在執(zhí)行任務(wù)后，向后備機(jī)發(fā)送跟新消息前崩潰，此時(shí)后備機(jī)接管，消息再次到來，任務(wù)被執(zhí)行2次；3）主機(jī)在后備機(jī)執(zhí)行任務(wù)后自己發(fā)送相應(yīng)消息前崩潰，則任務(wù)被執(zhí)行3次，一次由主機(jī)完成，一次由后備機(jī)完成，一次由后備機(jī)接管時(shí)完成。如果請(qǐng)求消息帶有序號(hào)，則可以減少任務(wù)執(zhí)行次數(shù)。，failsilent類型和Byzantine類型處理機(jī)錯(cuò)誤各需要至少多少個(gè)處理機(jī)才能滿足要求？說明理由。答：failsilent類型處理機(jī)錯(cuò)誤是指失效的處理機(jī)只是停止運(yùn)行，對(duì)接下來的輸入不做反應(yīng)也不產(chǎn)生進(jìn)一步的輸出，即宣布它不在工作了。對(duì)于這樣的錯(cuò)誤，需要K+1個(gè)這樣的處理機(jī)以滿足K容錯(cuò)要求，因?yàn)槿鬕個(gè)處理機(jī)停止工作，那么剩下的那個(gè)處理機(jī)繼續(xù)工作。Byzantine類型的錯(cuò)誤是指出錯(cuò)的處理機(jī)繼續(xù)運(yùn)行，產(chǎn)生問題的錯(cuò)誤答案，并可能和其他出錯(cuò)的處理機(jī)一起“惡意”地工作。對(duì)于這類錯(cuò)誤，那么至少需要2K+1個(gè)處理機(jī)才能滿足K容錯(cuò)要求，因?yàn)槌鲥e(cuò)的處理機(jī)仍然運(yùn)行并發(fā)出錯(cuò)誤或隨機(jī)應(yīng)答，最壞情況下，K個(gè)失效處理器偶然產(chǎn)生同樣的應(yīng)答，剩下K+1個(gè)未出錯(cuò)的處理機(jī)也將產(chǎn)生相同應(yīng)答，因此客戶或者表決器只要相信大多數(shù)應(yīng)答就可得到正確的結(jié)果。答：Lamport等人設(shè)計(jì)了一種遞歸算法可在特定條件下解決這一問題。例如：N = 4（有四個(gè)將軍），M = 1（其中有一個(gè)叛徒），對(duì)這樣的參數(shù)，參數(shù)運(yùn)行四步。第一步，每個(gè)將軍發(fā)送可靠的消息給其他所有的將軍，聲明自己真實(shí)的軍隊(duì)人數(shù)，忠誠(chéng)的將軍聲明的是真值，叛徒則可能對(duì)其他每個(gè)將軍都撒一個(gè)不同的謊。如圖a；第二步，把第一步聲明的結(jié)果組成向量形式，如圖b；第三步，每個(gè)將軍把圖b中各自的向量傳遞給其他每一個(gè)將軍，這里叛徒再一次撒謊，使用了12個(gè)新值。A—J。如圖c；第四步，每個(gè)將軍檢查所有新接收向量的每一個(gè)元素，若某個(gè)值占多數(shù)則把該值放入結(jié)果向量中，dcba將軍1(G1) 1K將軍2(G2) 2K將軍4(G4) 4K將軍3(G3) X,Y,ZG1 = (1K, 2K, X, 4K)G2 = (1K, 2K, Y, 4K)G3 = (1K, 2K, 3K, 4K)G4 = (1K, 2K, Z, 4K)G1 = [ (1K,2K,X,4K) (1K,2K,Y,4K) (A,B,C,D) (1K,2K,Z,4K) ]G2 = [ (1K,2K,X,4K) (1K,2K,Y,4K) (E,F,G,H) (1K,2K,Z,4K) ]G3 = [ (1K,2K,X,4K) (1K,2K,Y,4K) (1K,2K,3K,4K) (1K,2K,Z,4K) ]G1 = [ (1K,2K,X,4K) (1K,2K,Y,4K) (I,J,K,L) (1K,2K,Z,4K) ]G1 = (1K, 2K, UNKNOW, 4K)G2 = (1K, 2K, UNKNOW, 4K)G4 = (1K, 2K, UNKNOW, 4K)G2 = (1K, 2K, 3K, 4K)，動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度的含義是什么？比較動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度算法。答：動(dòng)態(tài)調(diào)度是指在程序運(yùn)行期間進(jìn)行調(diào)度決定下面運(yùn)行哪一個(gè)進(jìn)程。靜態(tài)調(diào)度是指在系統(tǒng)開始運(yùn)行前就已經(jīng)進(jìn)行，算法的輸入包含了所有任務(wù)的列表及它們各自的運(yùn)行時(shí)間。兩者比較如下：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)行期間無法承受復(fù)雜的調(diào)度計(jì)算花費(fèi)。，并給出以下TMR系統(tǒng)可應(yīng)付多少個(gè)故障元件（設(shè)備和表決器），舉例說明可屏蔽掉的最壞的情況。答：主動(dòng)復(fù)制是使用物理冗余來提供容錯(cuò)的一種著名的技術(shù)，這種方法也適用于電子電路的容錯(cuò)。主動(dòng)復(fù)制的一個(gè)主要問題是需要復(fù)制多少份才合適，這取決于要達(dá)到的容錯(cuò)量。如果系統(tǒng)在k個(gè)部件出錯(cuò)時(shí)仍能達(dá)到系統(tǒng)設(shè)計(jì)的要求而正常工作，那么這個(gè)系統(tǒng)稱為是k級(jí)容錯(cuò)的。如failslient類型，有k+1個(gè)這樣的部件可以滿足k級(jí)容錯(cuò)，若k個(gè)處理機(jī)簡(jiǎn)單停止工作，那么可以使用剩下的那個(gè)處理機(jī)的結(jié)果；如byzantine類型，至少需要2k+1個(gè)部件才可以滿足k級(jí)容錯(cuò)，最壞情況下k個(gè)失效的處理機(jī)偶然（甚至有意）地產(chǎn)生相同的應(yīng)答，然而剩下的k+1個(gè)未出錯(cuò)的處理機(jī)也將產(chǎn)生相同的應(yīng)答，因此客戶機(jī)可以根據(jù)大多數(shù)的應(yīng)答得到正確結(jié)果。如上圖中的TMR系統(tǒng)是每個(gè)設(shè)備復(fù)制三次，每級(jí)電路都設(shè)置三個(gè)表決器，每個(gè)表決器都有三個(gè)輸出和一個(gè)輸入，若兩個(gè)或者三個(gè)輸入相同，輸出則等于輸入，因此它可以處理6個(gè)失效的元件。Eg：第一行的元件全部失效的情況。，并舉例說明三模冗余能否處理Byzabtine故障。答：三模冗余是使用物理冗余來提供容錯(cuò)的技術(shù)，是使用主動(dòng)復(fù)制方法的容錯(cuò)。在電子電路中有設(shè)備A、B、C，然后每個(gè)設(shè)備復(fù)制三次，結(jié)果就是每級(jí)電路都設(shè)置了三個(gè)表決器，每個(gè)表決器有三個(gè)輸入和一個(gè)輸出，若兩個(gè)或者三個(gè)輸入相同，輸出則等于輸入，若三個(gè)輸入各不相同，輸出就是不定值，這種設(shè)計(jì)就是TMR。若處理機(jī)是Byzabtine類型的，出錯(cuò)的處理機(jī)仍然工作并發(fā)出錯(cuò)誤的隨機(jī)的應(yīng)答，那么至少需要2k+1個(gè)處理機(jī)才能達(dá)到k級(jí)容錯(cuò)。最壞情況下k個(gè)失效的處理機(jī)偶然（甚至有意）地產(chǎn)生相同的應(yīng)答，然而剩下的k+1個(gè)未出錯(cuò)的處理機(jī)也將產(chǎn)生相同的應(yīng)答，因此客戶機(jī)可以根據(jù)大多數(shù)的應(yīng)答得到正確結(jié)果。三模冗余在每組中有一個(gè)部件出現(xiàn)Byzabtine故障時(shí)可以處理，而一組中有兩個(gè)甚至三個(gè)同時(shí)出現(xiàn)Byzabtine故障則不能處理。答：整個(gè)系統(tǒng)可以表示為一張帶權(quán)圖，每個(gè)節(jié)點(diǎn)表示一個(gè)進(jìn)程，每條邊表示兩個(gè)進(jìn)程之間的通信量。從數(shù)學(xué)角度看，整個(gè)問題就變成了如何根據(jù)特定的限制將圖劃分成k（k為系統(tǒng)中cpu數(shù)量）個(gè)不相連的子圖（如每個(gè)子圖的總cpu和內(nèi)存需求在一定限制內(nèi)）。對(duì)于每種滿足限制的解決方案，子圖內(nèi)部的邊意味著機(jī)器內(nèi)部的通信，可以忽略。從一個(gè)子圖連向另一個(gè)子圖的邊表示網(wǎng)絡(luò)通信。該算法的目標(biāo)就是在滿足限制下，找到一種劃分方式使網(wǎng)絡(luò)通信量最小。下圖表示了圖的兩種劃分:方案A:通信量=(3＋2＋4＋4)＋(2＋8＋5＋2)＝30方案B:通信量=(3＋2＋4＋4)＋(3＋5＋5＋2)＝28。答：事件觸發(fā)是指，當(dāng)一個(gè)重要的外部事件觸發(fā)時(shí)，它被傳感器察覺到，并導(dǎo)致與傳感器相連的cpu得到一個(gè)中斷請(qǐng)求。時(shí)間觸發(fā)是指，在每隔固定的時(shí)間t后產(chǎn)生一次時(shí)鐘中斷，對(duì)選定的傳感器進(jìn)行采樣，并且驅(qū)動(dòng)（特定的）執(zhí)行機(jī)構(gòu)。舉例，考慮一個(gè)100層樓的電梯控制器設(shè)計(jì)。假定電梯正在60層安靜的等待顧客，有人在一層按下按鈕。就在100毫秒后，另一人在100層按下按鈕。在事件觸發(fā)系統(tǒng)中，第一次按鈕產(chǎn)生一個(gè)中斷，將使電梯啟動(dòng)下行，就在他做出下行決定后，第二個(gè)按下按鈕的事件到來，因此第二個(gè)事件被記錄下來以作將來的參考，但電梯還是繼續(xù)下行。若考慮時(shí)間觸發(fā)系統(tǒng)，沒500毫秒采樣一次。若兩次按下按鈕都在一次采樣周期中出現(xiàn)，控制器就不得不進(jìn)行決定，例如按最近用戶優(yōu)先原則，此時(shí)電梯將上行。由以上例子可以看出，事件觸發(fā)的設(shè)計(jì)在低負(fù)載時(shí)會(huì)更快響應(yīng)，但在高負(fù)載時(shí)可能崩潰。時(shí)間觸發(fā)相反，僅適用于相對(duì)靜態(tài)的環(huán)境。？答：文件服務(wù)分為兩種類型：上載/下載模式和遠(yuǎn)程訪問模式。上載/下載模式。只提供兩種主要的操作（讀文件和寫文件），讀操作將整個(gè)文件從文件服務(wù)器傳輸?shù)秸?qǐng)求客戶端，寫操作則剛好相反，文件系統(tǒng)運(yùn)行在客戶端。優(yōu)點(diǎn)是系統(tǒng)概念簡(jiǎn)單，應(yīng)用程序取得需要的文件，并在本地使用它。當(dāng)程序結(jié)束時(shí)，將所有修改的文件或新創(chuàng)建的文件寫回去，不需要管理復(fù)雜的文件服務(wù)接口，文件傳輸效率高。缺點(diǎn)是客戶端需要足夠的存儲(chǔ)空間，當(dāng)需要部分文件是需要傳輸整個(gè)文件。遠(yuǎn)程訪問模式。提供了大量的操作，如打開、關(guān)閉文件，讀寫部分文件等等。文件系統(tǒng)在服務(wù)器端運(yùn)行。優(yōu)點(diǎn)是客戶不需要大量存儲(chǔ)空間，當(dāng)需要部分文件是不需要傳輸整個(gè)文件。（文件共享的四種語(yǔ)義）。答：1）UNIX語(yǔ)義。系統(tǒng)使所有的操作都有一個(gè)絕對(duì)時(shí)間順序，READ操作讀取最近一個(gè)WRITE操作后的內(nèi)容，要求對(duì)一個(gè)文件系統(tǒng)的任何操作對(duì)所有進(jìn)程都是及時(shí)可見的。2）會(huì)話語(yǔ)義。對(duì)于打開文件的修改最初只對(duì)修改文件的進(jìn)程是可見的，當(dāng)文件關(guān)閉后，對(duì)文件的修改對(duì)其他進(jìn)程才是可見的。3）不可修改語(yǔ)義。不允許打開文件進(jìn)行寫操作，只提供CREATE和READ兩種操作。只能進(jìn)程講的的共享和復(fù)制。4） 事務(wù)語(yǔ)義。使用原子事務(wù)，即所有的操作要么全做，要么全不做。答：1）直接寫，當(dāng)緩存中的文件被更新后，新的值在緩存在保存，而且同時(shí)發(fā)送到服務(wù)器，而當(dāng)另外的進(jìn)程訪問文件時(shí)，讀到的是最新值，但是存在一個(gè)問題，其他進(jìn)程在更新之前讀到的文件內(nèi)容可能是過期的，那么在每次用到文件時(shí)需要從服務(wù)器中讀取文件版本進(jìn)行比較，查看是否過期，但是每次都要在服務(wù)器和客戶端之間通信，這樣就體現(xiàn)不出緩存的作用了。2）延遲寫，操作不立即發(fā)送給服務(wù)器，而是延遲一段時(shí)間，也就減少了網(wǎng)絡(luò)消息，當(dāng)進(jìn)程