高級操作系統(tǒng)答案

1、名詞解釋：分布式系統(tǒng): 一個分布式系統(tǒng)是若干個具有自治功能的獨立計算機的集合，但是對該系統(tǒng)的用戶來說，感覺該系統(tǒng)就像一臺計算機一樣。硬件方面：每臺計算機都是獨立、自主的計算機；軟件方面：用戶感覺在獨占系統(tǒng)。分布式系統(tǒng)物理上是分布的，邏輯上是一個整體。分布透明性: 分布透明性是一種現(xiàn)象，通過這種現(xiàn)象，系統(tǒng)中分布式的各個方面在用戶與應用之間隱藏了起來，即分布式系統(tǒng)在用戶和應用程序面前呈現(xiàn)為單個計算機系統(tǒng)。包括：訪問透明、位置透明、移植透明、重定位透明、復制透明、并發(fā)透明、故障透明和持久性透明。多線程文件服務器：多線程是這樣一種機制，它允許在程序中并發(fā)執(zhí)行多個指令流，每個指令流都稱為一個線程，彼此間

2、互相獨立。文件服務器是一種器件，它的功能就是向服務器提供文件。標識符：是用戶編程時使用的名字。我們用標識符這個名詞來表示各資源項的名稱。標識符可以用于多種目的，如訪問，定位，調(diào)度，分配，故障控制，同步以及對象或資源的共享。在系統(tǒng)結構的各層次上，標識符以不同的方式出現(xiàn)。中間件：答案1：指一個軟件層，放在應用程序和網(wǎng)絡操作系統(tǒng)之間，它提供了一個編程抽象以及對底層網(wǎng)絡、硬件、操作系統(tǒng)和編程語言異構性的屏蔽。答案2：中間件是一種獨立的系統(tǒng)軟件或服務程序，分布式應用軟件借助這種軟件在不同的技術之間共享資源。中間件位于客戶機/ 服務器的操作系統(tǒng)之上，管理計算機資源和網(wǎng)絡通訊。是連接兩個獨立應用程序或獨立系

3、統(tǒng)的軟件。相連接的系統(tǒng)，即使它們具有不同的接口，但通過中間件相互之間仍能交換信息。執(zhí)行中間件的一個關鍵途徑是信息傳遞。通過中間件，應用程序可以工作于多平臺或 OS 環(huán)境。RPC：答：RPC是remote procedure call（遠程過程調(diào)用）的簡稱。RPC思想是使遠程的過程調(diào)用就像在本地的過程一樣，調(diào)用者不應該意識到此調(diào)用的過程是在其他機器上實行的。 RPC的執(zhí)行步驟： (1) 客戶過程以普通方式調(diào)用相應的客戶存根； (2) 客戶存根建立消息，打包并激活內(nèi)核陷阱； (3) 內(nèi)核將消息發(fā)送到遠程內(nèi)核； (4) 遠程內(nèi)核將消息發(fā)送到服務器存根； (5) 服務器存根將消息解包，取出其中參數(shù)后調(diào)

4、用服務器過程； (6) 服務器完成工作或將結果返回服務器存根； (7) 服務器存根將它打包并激活內(nèi)核陷阱； (8) 遠程內(nèi)核將消息發(fā)送至客戶內(nèi)核； (9) 客戶內(nèi)核將消息交給客戶存根； (10) 客戶存根將消息解包，從中取出結果返回給客戶； 遠程對象調(diào)用：遠程對象調(diào)用是通過調(diào)用遠程對象的方法實現(xiàn)的。遠程對象調(diào)用=遠程方法調(diào)用。失效：系統(tǒng)出錯或不能滿足它的承諾（提供服務）。容錯：避免系統(tǒng)失效。在故障發(fā)生時系統(tǒng)仍能正常運行（提供服務）解答題簡述處理機分配算法中的接受者發(fā)起的分布式啟發(fā)性算法的算法實現(xiàn)過程及算法的特點。發(fā)送者發(fā)起的分布式啟發(fā)算法：當創(chuàng)建進程時，創(chuàng)建進程的機器將對一個隨機選取的機器發(fā)生

5、詢問，詢問它的負載是否低于某個閾值，如果是，將發(fā)送進程否則將選擇另一臺機子發(fā)送詢問。如果在N次詢問內(nèi)還沒有找到合適的機器，算法停止新進程將在創(chuàng)建它的機器上運行。該算法的缺點是：在負載十分嚴重的情況下，所有機器都會不停的毫無意義的向其他機器發(fā)送詢問，想找到一臺愿意接受更多工作的機器，在這種情況下，幾乎沒有進程會被減輕負載，但卻會引起相當可觀的額外開銷。試舉例說明沒有統(tǒng)一時鐘的分布式系統(tǒng)會發(fā)生什么問題？解答：當每臺機器有它自己的時鐘時，一個發(fā)生于另一事件之后的事件可能會被標記為一個比另一個事件更早的時間。例一致性協(xié)議中，復制的寫協(xié)議有哪幾種？請簡單解釋？答：復制的寫協(xié)議：寫操作可以在多個副本上執(zhí)行

6、。包括兩種類型：主動復制和基于法定數(shù)量的協(xié)議。 主動復制：每個副本有一個關聯(lián)的進程，該進程執(zhí)行更新操作。操作被發(fā)送到每個副本。 基于法定數(shù)量的協(xié)議，其基本思想是：在讀或寫一個復制的數(shù)據(jù)項之前要求申請并獲得多個服務器的允許。試描述客戶和服務器之間使用套接字的面向連接的通信是如何進行的？答：為了實現(xiàn)服務器與客戶機的通信，服務器和客戶機都必須建立套接字。服務器與客戶機的工作原理可以用下面的過程來描述。 (1)服務器先用socket函數(shù)來建立一個套接字，用這個套接字完成通信的監(jiān)聽。 (2)用bind函數(shù)來綁定一個端口號和IP地址。因為本地計算機可能有多個網(wǎng)址和IP，每一個IP和端口有多個端口。需要指定

7、一個IP和端口進行監(jiān)聽。 (3)服務器調(diào)用listen函數(shù)，使服務器的這個端口和IP處于監(jiān)聽狀態(tài)，等待客戶機的連接。 (4)客戶機用socket函數(shù)建立一個套接字，設定遠程IP和端口。 (5)客戶機調(diào)用connect函數(shù)連接遠程計算機指定的端口。 (6)服務器用accept函數(shù)來接受遠程計算機的連接，建立起與客戶機之間的通信。 (7)建立連接以后，客戶機用write函數(shù)向socket中寫入數(shù)據(jù)。也可以用read函數(shù)讀取服務器發(fā)送來的數(shù)據(jù)。 (8)服務器用read函數(shù)讀取客戶機發(fā)送來的數(shù)據(jù)，也可以用write函數(shù)來發(fā)送數(shù)據(jù)。 (9)完成通信以后，用close函數(shù)關閉socket連接。 客戶機與服

8、務器建立面向連接的套接字進行通信，請求與響應過程可用圖來表示。文件更新有哪幾種主要算法？簡述其算法思想？ 答：文件更新有主拷貝復制和表決（Voting）算法兩種主要算法。主拷貝復制算法：指定一個服務器為主服務器，其它服務器為從服務器；當要更新一個復制文件，將該更新文件送至主服務器；在主服務器處完成修改，然后向各從服務器發(fā)命令，完成修改；容錯方法：將日志寫在穩(wěn)定存儲器。 表決（Voting）算法：基本思想：在讀或寫一個復制文件之前要求申請并獲得多個服務器的允許，并將新的版本號與文件聯(lián)系起來，用以識別文件版本； 讀法定數(shù)（read quorum）Nr:讀文件操作前必須達到的服務器數(shù)； 寫法定數(shù)（w

9、rite quorum）Nw:更新文件前必須達到的服務器數(shù)； Nr與Nw遵循的規(guī)則：NwN/2（服務器總數(shù)的一半），NrNwN?；谖锢頃r鐘的同步算法有哪幾種？簡述他們的算法實現(xiàn)過程。答：主要有三種：Cristian算法、Berkeley算法、Averaging算法。Cristian算法： 有一個時間服務器，提供標準時鐘，其它系統(tǒng)通過詢問與它同步。 在/2秒的周期內(nèi)，每個機器向服務器發(fā)出校時請求，服務器用CUTC進行響應，各機器根據(jù)響應值重置自己的時鐘。 由于時鐘是不可回卷的，對于當前時鐘值已經(jīng)大于CUTC的機器必須動態(tài)調(diào)整自己時鐘的H值，減慢時鐘推進的速率，逐漸地消化與標準時鐘之間的差距。

10、由于請求與響應的傳輸與處理會產(chǎn)生延遲，進而影響時鐘的精度。因此要求詢問者要統(tǒng)計它與服務器之間的RTT，并利用它對得到的時間響應值進行修正。Berkeley算法： 時間服務器（time daemon）沒有標準時鐘，它通過定期地詢問各個機器的當前時間并從中求出平均值作為當前的標準時間，然后再廣播給各個機器。當前時鐘慢于新標準時間的機器重置自己的時鐘；當前時鐘快于新標準時間的機器要調(diào)整自己的H值，以消化這個時間誤差。時間服務器的時鐘由系統(tǒng)管理員手工校正。Averaging算法： 定義一個固定的同步間隔R，每經(jīng)過R時刻，所有的機器廣播自己的當前時鐘。在經(jīng)過規(guī)定的接收間隔S之后，所有的機器根據(jù)接收到的時

11、鐘值計算自己的當前時鐘值。 由于大家都不考慮傳輸延遲，所以實際得到的時鐘值是滯后的，即在R+t的時刻得到R時刻的時鐘值，并將其作為自己R+t時刻的時鐘值。 時鐘值計算的最簡單方法是求平均值。如果要求更精確，則可以去掉m個最大值和n個最小值之后再計算平均值，這可以過濾掉一些病態(tài)的時鐘值。簡述處理機分配算法中圖論算法的算法思想及目標。答：圖論算法的思想：整個系統(tǒng)可以表示為一張帶權圖，每個節(jié)點表示一個進程；子圖內(nèi)每條邊表示兩個進程之間的通信量；從一個子圖連向另一個子圖的邊表示網(wǎng)絡通信。 算法的目標：在滿足所有的資源限制下，找到一種劃分方式使網(wǎng)絡通信量最小。請說出路徑N: 的名稱解析過程答：這個路徑名

12、的解析是從命名圖中節(jié)點N開始的，首先在節(jié)點N的目錄表中查找名字label-1，得到label-1所代表的節(jié)點的標識符；然后在label-1所代表的節(jié)點的目錄表中查找名字label-2，得到label-2所代表的節(jié)點的標識符；此過程一直進行下去，如果N:在命名圖中是實際存在的，就能夠得到label-n所代表的節(jié)點的標識符，從而得到該節(jié)點的內(nèi)容。以客戶為中心的一致性模型有哪幾種？試分別舉例說明答：單調(diào)讀一致性：當一個進程讀了數(shù)據(jù)項x的值后，所有后續(xù)的對x的讀操作，都將返回相同的值，或者更新的值。也就是說，單調(diào)讀一致性保證，如果一個進程已經(jīng)在t時刻看到x的值，那么以后它不會再看到較老版本的x的值。例

13、：讀email(舊金山-紐約）例a：符合單調(diào)讀一致性例b: 不能保證單調(diào)讀一致性；單調(diào)寫一致性：一個進程對數(shù)據(jù)項x的寫操作，必須在該進程對x的所有后續(xù)寫操作之前完成。例：軟件庫更新（版本1,.,n)例a：符合單調(diào)寫一致性例b: 不能保證單調(diào)寫一致性；讀自己寫一致性（寫后讀）：一個進程對數(shù)據(jù)項x的寫操作結果，總能被該進程對x的后續(xù)讀操作讀到。例1：Web網(wǎng)頁更新、瀏覽：服務器更新，本地緩存未更新。例2：數(shù)字圖書館密碼更新：管理服務器更新密碼，其他服務器拷貝尚未更新。例a：符合寫后讀一致性例b: 不能保證寫后讀一致性；寫跟隨讀一致性（讀后寫）：一個進程在對數(shù)據(jù)項x讀操作之后對x的寫操作，必須在x已

14、讀出的相同值或者更近的值之上進行例：BBS跟帖（讀原文章A,寫回應文章B）例a：符合寫跟隨讀一致性例b: 不能保證寫跟隨讀一致性存儲器一致性模型有哪幾種？試分別解釋其含義。所謂存儲一致性模型，實際上是系統(tǒng)設計者與應用程序員之間的一種約定。如果應用軟 件遵從一定的規(guī)則訪問虛擬內(nèi)存系統(tǒng)，則應用軟件可以獲得正確的存儲訪問結果；反之，如果破壞了約定的規(guī)則，則存儲訪問的正確性不受保證。按照一致性從強到弱的順序，可以區(qū)別為下面幾種類別。 (1)、嚴格一致性模型 這是對一致性要求最嚴格的一種模型，它由下面的條件來描述：任何對內(nèi)存位置X的讀操作將返回最近位置對X進行寫操作的值。 在DSM系統(tǒng)中，這是一種理想的

15、模型，但是受到網(wǎng)絡延遲的影響而不可能實現(xiàn)。在DSM系 統(tǒng)中實現(xiàn)的多種一致性模型，都是對嚴格一致性模型在不同程度上的放松。而在單機環(huán)境下，任何存儲訪問序列都滿足嚴格一致性要求。 (2)、順序一致性模型 順序一致性對存儲器的限制比嚴格一致性要弱一些，順序一致性的存儲器要滿足以下的條件： 1） 每個進程的內(nèi)部操作順序是確定不變的； 2） 假如所有的CPU上的進程都對某一個存儲單元執(zhí)行操作，那么，它們的操作順序是確定的，即任一進程都可以感知到這些進程同樣的操作順序。 上述條件的含義是指，當多個進程分別在不同的機器上并發(fā)執(zhí)行的時候，只要所有的進 程都保持同樣的順序訪問存儲器，那么，任何有效的交叉訪問執(zhí)行

16、都是可以接受的。在 順序一致性模型中，時間不再是影響一致性的因素，它關心的是：所有進程都必須能夠感受到一直的內(nèi)存訪問序列。 順序一致性模型不確保進程的一次讀操作可以返回由另一進程所寫入的最新值。在沒有顯式的同步操作的情況下，再一次運行同樣的程序不能保證獲得同樣的結果。 (3)、因果一致性模型 因果一致性模型是對順序一致性的弱化，它要求在具有潛在因果關系（Happened - Bef ore）的操作之間保持其一致的順序。一般性的描述如下：有潛在性因果相關的寫操作必須以同樣的順序被各個進程所感知，而并發(fā)的寫操作在不同的機器上有不同的順序。在基于因果順序一致性模型的存儲管理系統(tǒng)中合法的操作序列在順序

17、一致性或者嚴格一致性模型中可能會成為非法操作。 (4)、管道一致性模型 管道一致性模型是在因果一致性模型上的進一步弱化，它滿足下面的條件：由某一個進程完成的寫操作可以被其他所有的進程按照順序的感知到，而從不同進程中來的寫操作對不同的進程可以有不同的順序。 管道一致性模型相對來說比較容易實現(xiàn)，所以在應用中具有一定的吸引力。實際上，它對于不同進程所感知到的寫操作順序并沒有保證，除非是從同一個進程源來的寫操作，則必須按照順序到達別的所有的進程，類似于它們處在一條管道中一樣。除此以外在管道一致性 模型中，有不同進程產(chǎn)生的寫操作完全是并行的。 （5）、弱一致性模型 盡管管道一致性模型與較之嚴格的一致性模

18、型相比，能夠獲得更好的性能。但因為它對同一個進程(源)所產(chǎn)生的結果仍然作了必須按序送達到所有別的進程的要求，所以在很多應用方面仍然受到了模型的限制。并非所有的進程都要求看到所有的寫操作的結果，讓他們按照順序看到寫操作的結果更是沒有必要。這樣處理，模型的開銷會嚴重影響應用程序的性能?？紤]到運算的中間結果在大多數(shù)情況下并沒有必須傳送出去的必要的具體情況，我們必須對一致性要求作進一步的放松，修改為只有在需要傳播寫操作的結果的時候才將結果傳送出去，除此之外，一切讀寫操作都完全是并行的。為了達到同步操作的目的，在弱一致性模型中引入了同步變量。弱一致性模型必須滿足的條件有下面幾點: l 對同步變量的訪問滿

19、足一致性的要求 l 對同步變量的訪問，只有在以前的寫操作在各處都完成之后才能完成。 l 對數(shù)據(jù)的操作（讀或寫），只有在以前的對同步變量的操作完成之才能完成。 第一點說明所有的進程都能以同樣的順序感知到所有對同步變量的訪問。當一個進程訪問某同步變量時，它會把對該同步變量的訪問廣播出去，在該進程對該同步變量訪問操作成功之前，任何別的進程對同步變量的訪問都將被阻塞。 第二點說明對同步變量的訪問會導致對內(nèi)存進行刷新的結果。當一個同步訪問完成之后，那么，所有先前的寫操作可以同時確保完成。當某進程對一個共享數(shù)據(jù)作了更新之后面，它可以通過同步操作將新值傳播出去。 第三點說明當一個進程在讀一個共享數(shù)據(jù)（非同步

20、變量）時，通過同步操作，它能獲得該共享數(shù)據(jù)的最新值。（6）、釋放一致性模型 對于同步變量的訪問，弱一致性模型存在一個問題：無法區(qū)分進程是準備進入臨界區(qū)還是已經(jīng)完成對共享變量的操作而準備退出臨界區(qū)，其結果就是進程在以下兩種情況下都必須采取同步操作： l 將局部寫操作的結果傳播出去 l 從別的機器上收集共享數(shù)據(jù)的最新值 如果將進入和退出臨界區(qū)這兩個動作區(qū)分，則可以實現(xiàn)一種更為高效的存儲一致性模型-釋放一致性模型。釋放一致性模型提供了兩類同步操作：Acquire和Release。某進程將要進入臨界區(qū)時執(zhí)行Acquire操作，退出時執(zhí)行Release操作。也可以不用臨界區(qū)而用柵欄（Barrier）同步

21、來實現(xiàn)釋放的一致性協(xié)議。柵欄是一種同步機制，它要求所有的進程全都到達程序的某一點后，各個進程才能繼續(xù)往下執(zhí)行。 借助于Acquire和Release操作，我們可以把某些特殊的共享變量保護起來，并維護它們的一致性。當然，應用程序必須確知它需要維護其一致性的數(shù)據(jù)，這也給應用程序的編制增加了一些協(xié)議開銷，但是整體性能提高了。通常，如果一個分布式共享存儲系統(tǒng)滿足釋放一致性，則它必須遵守以下的規(guī)則： l 某進程只有在成功完成Acquire操作之后，才能確保對一般共享變量（非共享同步變量）訪問的正確性。 l 某進程只有在完成對共享數(shù)據(jù)的讀寫操作之后，Release操作才能完成。l Acquire和Rele

22、ase操作必須滿足管道一致性要求。為了更進一步提高性能，另外一種實現(xiàn)釋放一致性模型的協(xié)議被稱之為懶惰釋放一致性（Lazy Release Consistency），與之對應，一般的實現(xiàn)被稱為勤釋放一致性（Eager Release Consistency）。它們之間的區(qū)別在于，勤釋放一致性協(xié)議在Release操作結束之后，將所有已修改的數(shù)據(jù)傳送給所有的別的進程。這樣，別的進程都將擁有此最新數(shù)據(jù)的一個副本并可在本地訪問它們。但實際情況是有可能別的進程并不需要該共享數(shù)據(jù)，這樣就浪費了帶寬并給程序帶來不必要的延遲。懶惰釋放一致性協(xié)議在Release操作結束之后，并不急于傳送新的數(shù)據(jù)，而是在別的進程執(zhí)

23、行Acquire操作之后，由別的進程向它提出獲取新的數(shù)據(jù)的請求時，它響應該請求并把共享數(shù)據(jù)的最新值傳送給特定的進程，這樣系統(tǒng)的性能又獲得了提高。（7）、單項一致性模型另外一種用于提高臨界區(qū)操作并行性的一致性模型是單項一致性模型。和釋放一致性類似，它要求編程人員在臨界區(qū)的開始和結束時使用Acquire和Release操作，但與釋放一致性不同的是，它要求每個共享變量都與某同步變量相關聯(lián)，同步變量可以是鎖或者柵欄。以并行訪問一個數(shù)組的不同元素為例，它要求給不同的數(shù)組元素加不同的鎖，只有 當對同步變量的Acquire操作完成之后，相關的共享數(shù)據(jù)才得到一致性保證。單項一致性模型也不同于懶惰釋放一致性模型，后者并不將共享數(shù)據(jù)與鎖或柵欄相關聯(lián)，而是在對同步變量作Acquire操作之后，才能確定它需要那些共享數(shù)據(jù)。滿足單項一致性的條件是:l 在當前擁有者對數(shù)據(jù)的更新操作為完成之前，不能執(zhí)行另一個進程對同步變量的Acquire操作。 l 如果某一個進程正以互斥模式訪問某同步變量。則在該進程釋放此同步變量之前，任何別的進程即使在非互斥模式下都將無法獲得該同步變量。l 如果某進程正以互斥模式訪問一個同步變量，則在該進程完成操作之后，任何進程在以