《分布式操作系统》知识点（1～7）一
注：
（6）1 ?P210：（6）代表該習(xí)題是第6章的內(nèi)容，1是題號(hào)（第1題），P210是所在書中的大體頁(yè)數(shù)。
（6）1在交換式Dash多處理機(jī)系統(tǒng)中，為了保持緩存一致性，采用了Dash協(xié)議，某一簇中的一CPU寫一未緩存的數(shù)據(jù)塊，之后另外一簇的另外一CPU讀該數(shù)據(jù)塊。試詳細(xì)說明寫操作和讀操作是如何進(jìn)行的。P210
答：寫操作：寫數(shù)據(jù)塊的CPU先在本地總線發(fā)送請(qǐng)求察看鄰近CPU的緩存中是否有該數(shù)據(jù)塊。鄰近CPU的緩存中沒有該數(shù)據(jù)塊，本次查找失敗，數(shù)據(jù)塊所在的其他地方，CPU發(fā)送信包到其宿主所在簇。這里塊的狀態(tài)為UNCACHED，標(biāo)記為DIRTY并發(fā)送給請(qǐng)求者。
讀操作：讀數(shù)據(jù)塊的CPU首先檢查自己的內(nèi)存，緩存中無(wú)此字，則在本地簇中發(fā)出請(qǐng)求，詢問本地簇的其他CPU緩存中是否有此字。數(shù)據(jù)塊不在任何簇的緩存中，CPU發(fā)一請(qǐng)求信包給該塊的宿主所在簇。宿主所在簇的目錄管理硬件檢查它的表以確定其狀態(tài)。此處狀態(tài)為DIRTY，則擁有DIRTY塊的簇將數(shù)據(jù)塊發(fā)送給請(qǐng)求簇，將其狀態(tài)改為CLEAN，它還要給宿主所在簇發(fā)回一個(gè)拷貝以更新存儲(chǔ)器，此時(shí)塊的狀態(tài)置為CLEAN。
?
（6 P207）2在基于總線的多處理機(jī)系統(tǒng)中，遵循write once協(xié)議，假設(shè)有C1，C2，C3，C4四個(gè)CPU，一操作序列如下：C1讀一字W1（只存在于共享存儲(chǔ)器中）、C1繼續(xù)讀該字、C2讀該字；C1修改該字、C3讀該字、C4讀該字。試詳細(xì)說明以上操作序列是如何執(zhí)行的。
答：如下圖：
C1將將字W1的地址放到總線上，并在控制總線上加上“讀”信號(hào)，存儲(chǔ)器讀出需要的數(shù)據(jù)，將其放在總線上，在控制總線上加“準(zhǔn)備好”信號(hào)，C1即可以讀到字W1。由于C1的緩存中含有字W1，所以C1第二次讀取時(shí)從緩存中讀取字W1。C2讀取字W1時(shí)，C1監(jiān)聽到此讀操作，不做響應(yīng)，內(nèi)存響應(yīng)C2 的請(qǐng)求，經(jīng)過總線將字W1 發(fā)給C2。C1將新值寫入字W1，C2監(jiān)聽到此寫操作，將自己的緩存項(xiàng)置為無(wú)效，C1的緩存塊狀態(tài)置為DIRTY，此時(shí)C1 擁有字W1的唯一拷貝，存儲(chǔ)器中的字已失效。C3發(fā)出字請(qǐng)求訪問信號(hào)，C1發(fā)現(xiàn)總線上的訪問請(qǐng)求，則發(fā)信號(hào)禁止存儲(chǔ)器響應(yīng)，然后C1 提供C3需要的字并將自己的項(xiàng)置為無(wú)效。C3發(fā)現(xiàn)字來(lái)自其他的緩存而不是存儲(chǔ)器，則將其狀態(tài)置為DIRTY，則也相應(yīng)地標(biāo)示了自己的緩存項(xiàng)。同樣，C4發(fā)出字請(qǐng)求，C3發(fā)信號(hào)禁止存儲(chǔ)器響應(yīng)，C3提供C需要的字并將自己的項(xiàng)置為無(wú)效，C4將自己的狀態(tài)置為DIRTY。
?
（5）3在分布式系統(tǒng)，為了獲得文件讀寫的效率，需要使用高速緩存，說明設(shè)置緩存的各種方法及用途。并說明解決一致性問題的四種算法及各種算法存在的問題。P185
答：設(shè)置緩存的方法和用途：
有三種可使用的選擇來(lái)精確定義高速緩存的位置。
第一個(gè)是在每個(gè)用戶進(jìn)程自己的地址空間直接進(jìn)行文件高速緩存。典型地，高速緩存由系統(tǒng)調(diào)用庫(kù)管理。當(dāng)打開、關(guān)閉、讀和寫文件時(shí)，該庫(kù)只是保存最常用的文件，這樣當(dāng)重新使用文件時(shí)，它已經(jīng)是可用的了。當(dāng)該進(jìn)程退出時(shí)，所有被修改過的文件都回寫到服務(wù)器中。盡管這種模式的系統(tǒng)開銷很小，但它僅當(dāng)單個(gè)進(jìn)程重復(fù)地打開和關(guān)閉文件時(shí)才有效率。一個(gè)數(shù)據(jù)庫(kù)管理程序進(jìn)程可能滿足這種要求，但是在通常的程序開發(fā)環(huán)境中，大多數(shù)進(jìn)程對(duì)每個(gè)文件只讀一次，因此庫(kù)中的高速緩存是無(wú)益可獲的。
第二個(gè)是設(shè)置高速緩存的地方是在內(nèi)核中。這里的缺點(diǎn)是在所有情況下都需要內(nèi)核調(diào)用，甚至對(duì)于高速緩存命中。但事實(shí)是，高速緩存使進(jìn)程獲益比補(bǔ)償多。例如，假設(shè)一個(gè)兩遍掃描編譯器作為兩個(gè)進(jìn)程運(yùn)行。第一遍掃描寫一個(gè)中間文件而由第一遍掃描來(lái)讀。當(dāng)?shù)谝槐閽呙柽M(jìn)程結(jié)束后，該中間文件可能在高速緩存中，所以在第二遍掃描進(jìn)程讀入時(shí)沒有必要進(jìn)行服務(wù)器調(diào)用。
第三個(gè)是在一個(gè)單獨(dú)的用戶級(jí)高速緩存管理者進(jìn)程中，用戶級(jí)高速緩存器管理者的優(yōu)點(diǎn)是它保持了(微)內(nèi)核獨(dú)立于文件系統(tǒng)編碼，因?yàn)樗峭耆铝⒌?#xff0c;因此易十編程，并巨更加靈活。
解決一致性問題的四種算法：
1直接寫算法：（WRITE-THRONG算法）當(dāng)修改一個(gè)高速緩存項(xiàng)（文件或塊）時(shí)，新的值保存在高速緩存中并立即寫到服務(wù)器。
2延遲寫：延遲寫操作使得語(yǔ)義變得不清楚。當(dāng)另一個(gè)進(jìn)程讀此文件時(shí)，它所得結(jié)果取決于時(shí)間選擇。延遲寫只好在運(yùn)行效率和清晰的語(yǔ)義之間權(quán)衡。
3關(guān)閉時(shí)寫：僅當(dāng)文件關(guān)閉后才將文件寫到服務(wù)器，與對(duì)話語(yǔ)義相配；
4集中控制算法：當(dāng)打開一個(gè)文件時(shí)，打開該文件的機(jī)器向服務(wù)器發(fā)送一條消息。服務(wù)器保存誰(shuí)打開了哪個(gè)文件以及打開是為了讀還是寫或者兩者兼有。如果文件是為讀而打開，允許其他進(jìn)程為讀而打開，避免為寫而打開。如果某個(gè)進(jìn)程為寫而打開一個(gè)文件，必須禁止所有其他訪問。當(dāng)關(guān)閉文件時(shí)，必須報(bào)告，以便服務(wù)器更新。
四種算法存在的問題：
直接寫：有效，但不影響寫流量。高速緩存向任何客戶提供文件時(shí)，須先和服務(wù)器進(jìn)行核對(duì)，這要付出一些時(shí)間代價(jià)。對(duì)寫來(lái)說，網(wǎng)絡(luò)傳輸是相同的，就像根本沒有高速緩存一樣。
延遲寫：效率較高，但可能語(yǔ)義不清。
關(guān)閉時(shí)寫：與會(huì)話語(yǔ)義相配。如果兩個(gè)已放入高速緩存的文件被依次回寫，第二個(gè)或覆蓋第一個(gè)。解決此問題的唯一方法是注意它是否比第一次出現(xiàn)時(shí)已好得很多了。
集中控制：UNIX語(yǔ)義，但不健壯，不能規(guī)模化。盡管發(fā)送自發(fā)消息是肯定可行的，但卻非常生硬，必須要小心。
?
（5）4給出實(shí)現(xiàn)文件復(fù)制的三種方法，并舉例說明更新復(fù)制文件的Gifford算法，并說明某些服務(wù)器崩潰時(shí)，應(yīng)該采取什么措施。P190
答：文件復(fù)制的三種方法：
顯式文件復(fù)制，是為編程人員控制整個(gè)進(jìn)程而用。當(dāng)進(jìn)程產(chǎn)生一個(gè)文件時(shí)，可以在其他服務(wù)器上生成另外的拷貝。如果目錄服務(wù)存在允許一個(gè)文件有多個(gè)拷貝，所有拷貝的網(wǎng)絡(luò)地址都可以和這個(gè)文件名聯(lián)系起來(lái)。
懶惰復(fù)制，只要在某個(gè)服務(wù)器上建立每個(gè)文件的一個(gè)拷貝，服務(wù)器自己在其他的服務(wù)器上也可自動(dòng)生成副本。
用組復(fù)制文件，所有的寫系統(tǒng)調(diào)用同時(shí)傳送到所有的服務(wù)器。于是，其他的拷貝在原文件產(chǎn)生時(shí)就產(chǎn)生了。
Gifford算法即表決（voting）。基本思想：在讀或?qū)懸粋€(gè)復(fù)制文件之前要求申請(qǐng)并獲得多個(gè)服務(wù)器的允許。服務(wù)器在改變文件時(shí)，將一個(gè)新的版本號(hào)和新的文件聯(lián)系起來(lái)。版本號(hào)用來(lái)該文件的版本。讀一個(gè)已有N個(gè)復(fù)制存在的文件時(shí)，客戶需要獲得一個(gè)讀法定數(shù)Nr，修改一個(gè)文件需要一個(gè)寫法定數(shù)Nw，Nr和Nw的值必須滿足約束條件Nr+Nw>N。即只有在適當(dāng)數(shù)目的服務(wù)器參與時(shí)，文件才能被讀或?qū)憽?/strong>
舉例：例如，有5個(gè)服務(wù)器，客戶已確定它們中的下個(gè)有版本號(hào)8，則其他兩個(gè)的版本號(hào)不可能是9。因?yàn)槿魏螐陌姹咎?hào)8到版本號(hào)9的成功更新需要3個(gè)服務(wù)器同意，而不是兩個(gè)。
解決辦法：虛像表決(Voting With Ghosts)通過為每個(gè)已經(jīng)崩潰的服務(wù)器建立一個(gè)沒有存儲(chǔ)器的虛擬服務(wù)器解決了這個(gè)問題。虛設(shè)者不允許出現(xiàn)在讀法定數(shù)中(畢竟它沒有任何文件)，但它可以加入寫法定數(shù)中，在這種情況下，它只須去掉寫入的文件即可。只要有一個(gè)真實(shí)的服務(wù)器存在，寫操作就能成功。當(dāng)一個(gè)崩潰的服務(wù)器重新啟動(dòng)時(shí)，它必須獲得一個(gè)讀法定數(shù)來(lái)找到最新的版本。在它開始正常工作之前，它將為自己拷貝一份該拷貝。由于該算法和基本的表決算法.具有相同的特性，因此它是可行的。
?
（5）5 試說明舉例什么是有狀態(tài)服務(wù)器，什么是無(wú)狀態(tài)服務(wù)器，并對(duì)有狀態(tài)和無(wú)狀態(tài)服務(wù)器進(jìn)行詳細(xì)的比較。P183
答：有狀態(tài)服務(wù)器：服務(wù)器應(yīng)該保存兩個(gè)請(qǐng)求之間的客戶的狀態(tài)信息。畢竟，集中式操作系統(tǒng)保存了關(guān)于活動(dòng)進(jìn)程的狀態(tài)信息。
無(wú)狀態(tài)服務(wù)器：當(dāng)客戶發(fā)送一個(gè)請(qǐng)求給服務(wù)器時(shí)，服務(wù)器完成請(qǐng)求，發(fā)送一個(gè)應(yīng)答，然后從內(nèi)部表中移出該請(qǐng)求的所有信息。在請(qǐng)求之間，服務(wù)器不保存具體客戶的信息。
為了更好地理解這個(gè)差別，我們考慮擁有打開、讀、寫和關(guān)閉文件通用命令的文件服務(wù)器。文件打開之后，服務(wù)器必須保存哪個(gè)客戶打開了哪個(gè)文件的信息。典型地，當(dāng)一個(gè)文件打開時(shí)，客戶將獲得一個(gè)文件描述符或其他用于后續(xù)調(diào)用的編號(hào)，以便識(shí)別這個(gè)文件。當(dāng)有請(qǐng)求到來(lái)時(shí)，服務(wù)器就使用.文件描述符來(lái)確定需要哪個(gè)文件。將文件描述符變換成文件本身的表就是狀態(tài)信息。
對(duì)于不保留狀態(tài)信息的服務(wù)器，每一個(gè)請(qǐng)求必須是獨(dú)立的。為了使服務(wù)器能夠工作，它必須包含全文件名和文件中的偏移址。此信息增加了消息的長(zhǎng)度。
研究狀態(tài)信息的另一種方法是:如果服務(wù)器壞了并且它的所有表都永久性丟失了，將會(huì)發(fā)生什么情況，當(dāng)服務(wù)器重新啟動(dòng)時(shí)，它已不能再知道哪些客戶打開了哪些文件。以后對(duì)已打開文件進(jìn)行讀與寫操作就會(huì)失敗，而且如果有可能的話，將完全由客戶決定恢復(fù)。其結(jié)果是，不保留狀態(tài)的服務(wù)器比保留狀態(tài)的服務(wù)器有助于更好地容錯(cuò)。這是贊成前者的理由之一。
正如我們已提到的那樣，無(wú)狀態(tài)服務(wù)器在本質(zhì)上有更多的容錯(cuò)。不需要OPEN和CLOSE調(diào)用，這就減少了消息編號(hào)，特別對(duì)于那些整個(gè)文件用一次就可讀出的普通情況，服務(wù)器不用浪費(fèi)空間來(lái)存放表。使用表時(shí)，如果太多的客戶一次打開太多的文件，則將表填滿，從而不能打開新的文件。最后對(duì)于狀態(tài)服務(wù)器，如在文件們一開始客戶出了故障，服務(wù)器就會(huì)處于困境中。如果它對(duì)此束手無(wú)策，它的表最終將充滿垃圾。如果它超時(shí)了還未打開文件，那么客戶因兩個(gè)請(qǐng)求之間等待時(shí)間太長(zhǎng)將被拒絕服務(wù)，而校正程序就會(huì)失去校正功能。無(wú)狀態(tài)服務(wù)就不存在這些問題。
有狀態(tài)服務(wù)器也可以對(duì)這些問題進(jìn)行處理。由于READ和WRITE消息并不是必須包含文件名，所以他可以以更短些。這樣就可使用更小的網(wǎng)絡(luò)帶寬。由于關(guān)于打開文件(在UNIX項(xiàng)中，i節(jié)點(diǎn))的信息在文件關(guān)閉之前都可保存在主存儲(chǔ)器中，所以有較好的性能。由于人多數(shù)文件都是按順序讀的，可以預(yù)先讀信息塊減少延遲。如果一個(gè)客戶已用完時(shí)間片并且兩次發(fā)送了同一請(qǐng)求，例如APEEND ,那么用狀態(tài)信息(通過每一條消息的次序號(hào))就可以很容易地檢測(cè)到，在無(wú)狀態(tài)操作的不可靠通信前，實(shí)現(xiàn)冪等性需要更多的努力。最后，在一個(gè)真正的無(wú)狀態(tài)系統(tǒng)中，要使文件鎖定是不可能的，因?yàn)榻㈡i定的唯一效果是使?fàn)顟B(tài)進(jìn)入系統(tǒng)。在無(wú)狀態(tài)系統(tǒng)中，文件鎖定必須通過一個(gè)特定的鎖定服務(wù)器來(lái)完成。
?
（5）6 在分布式系統(tǒng)中，可支持上載/下載文件模式或遠(yuǎn)程訪問模式，說明這兩種模式并進(jìn)行比較。P174~P175
答：在上載/下載模式中，文件服務(wù)只提供兩種上要的操作:讀文件和寫文件。前一個(gè)操作是將整個(gè)文件從一個(gè)文件服務(wù)器傳送到提出i求的客戶;后一個(gè)操作是將整個(gè)文件從客戶傳送到服務(wù)器。因此這種概念模式是在任一方向上傳送整個(gè)文件。這些文件可以存儲(chǔ)在內(nèi)存或本地的硬盤中，視需要而定。
上載/下載的優(yōu)點(diǎn)是概念簡(jiǎn)單。應(yīng)用程序取得它們所需的文件，然后在本地使用它們。任何修改過的文件或新創(chuàng)建的文件在程序結(jié)束時(shí)都要將它回寫。使用這種模式不需要掌握復(fù)雜的文件接口，而且整個(gè)文件傳送也是高效的.，但是，客戶端必須具有足夠大的存儲(chǔ)空間來(lái)存儲(chǔ)所需的所有文件。而且，如果只需要文件的一小部分，移動(dòng)整個(gè)文件是很浪費(fèi)的。
文件服務(wù)的另一種類型是遠(yuǎn)程訪問模式，在這種模式中，文件服務(wù)提供了大量的操作用于打開和關(guān)閉文件，讀寫文件的一部分，在文件中來(lái)回移動(dòng)檢查和改變文件屬性，等等。而在上載/下載模式中，文件服務(wù)只提供物理存儲(chǔ)和傳送，在這里文件系統(tǒng)運(yùn)行在服務(wù)器上而不是運(yùn)行在客戶端。遠(yuǎn)程存取模式的優(yōu)點(diǎn)是在客戶端不需要很大的空間，與下又需要文件的一小部分時(shí)，不需要傳送整個(gè)文件。
?
（4）7 分布式協(xié)同一致算法的目標(biāo)是使所有無(wú)故障處理機(jī)對(duì)待某些問題的意見達(dá)到一致，在3個(gè)正常處理機(jī)，2個(gè)出錯(cuò)處理機(jī)的情況下，用Lamport算法能否達(dá)成一致，給出算法的具體步驟。P156
答：用Lamport算法不能達(dá)成一致,至少得5個(gè)正常的處理機(jī)才能達(dá)成一致。
在Lamport等的論文中，已證明了一個(gè)有m個(gè)處理機(jī)出錯(cuò)的系統(tǒng)中要實(shí)現(xiàn)協(xié)同一致，只有當(dāng)有2m + 1個(gè)正常處理機(jī)時(shí)才可能。處理機(jī)總數(shù)為3m+ 1。換種說法即是，只有大于2/3的處理機(jī)正常工作時(shí)，協(xié)同一致才是可能的。
Lamport具體算法的步驟：
1.每個(gè)將軍發(fā)送消息給其它將軍，聲明自己真實(shí)的軍隊(duì)人數(shù)
2.把第一步聲明的結(jié)果收集組成向量的形式。（b）
3.每個(gè)將軍將各自的向量傳遞給其它每個(gè)將軍。（c）
4.每個(gè)將軍檢查所有接收向量的第i個(gè)元素。若某個(gè)值占多數(shù)，放入結(jié)果向量中，否則，標(biāo)記為UNKNOWN。
總結(jié)
以上是生活随笔為你收集整理的《分布式操作系统》知识点（1～7）一的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《分布式操作系统》部分知识点整理
- 下一篇： 《分布式操作系统》知识点（8～14）二