網(wǎng)絡與分布式計算 復習提綱.docx

1.2 什么是分布式計算系統(tǒng)？它的實質(zhì)是什么？分布式計算系統(tǒng)是由多個相互連接的計算機組成的一個整體，這些計算機在一組系統(tǒng)軟件（分布式操作系統(tǒng)或中間件）環(huán)境下，合作執(zhí)行一個共同的或不同的任務，最少依賴于集中的控制過程、數(shù)據(jù)和硬件。實質(zhì)：分布計算系統(tǒng)=分布式硬件+分布式控制+分布式數(shù)據(jù)。1.10多處理機與多計算機的區(qū)別是什么？同構多計算機和異構多計算機各有什么特點？區(qū)別：多計算機是將多個計算機聯(lián)合起來處理問題,多處理機是在一個系統(tǒng)內(nèi)集成多個處理器.廣義上說，使用多臺計算機協(xié)同工作來完成所要求的任務的計算機系統(tǒng)都是多處理機系統(tǒng)。即多計算機系統(tǒng)。狹義上說：多處理機系統(tǒng)的作用是利用系統(tǒng)內(nèi)的多個CPU來并行執(zhí)行用戶的幾個程序，以提高系統(tǒng)的吞吐量或用來進行冗余操作以提高系統(tǒng)的可靠性。同構計算機的特點：1.每個節(jié)點是一臺計算機，包含CPU和存儲器。2.節(jié)點間的通信量較少。3.同構計算機系統(tǒng)的互連有兩種結構：基于總線的多計算機系統(tǒng)和基于交換的多計算機系統(tǒng)。異構計算機的特點：1.節(jié)點可能是多處理機系統(tǒng)、集群或并行高性能計算機。2.節(jié)點間通過互聯(lián)網(wǎng)絡如Internet連接起來的。3.有兩種實現(xiàn)方法：采用分布式操作系統(tǒng)和中間件軟件層。1.16什么是中間件，它的功能是什么？它在分布式系統(tǒng)中的地位是什么？中間件是一種獨立的系統(tǒng)軟件或服務程序，分布式應用軟件借助這種軟件在不同的技術之間共享資源。中間件位于客戶機/ 服務器的操作系統(tǒng)之上，管理計算機資源和網(wǎng)絡通訊，是連接兩個獨立應用程序或獨立系統(tǒng)的軟件功能：命名服務 作業(yè)調(diào)度 高級通信服務 資源管理 數(shù)據(jù)持久化 分布式事務分布式文檔系統(tǒng) 安全服務地位：中間件的一個重要目標是對應用程序隱藏底層平臺的異構型，因此中間件系統(tǒng)都提供一組完整度不同的服務集。這些服務是通過中間件系統(tǒng)提供的接口來調(diào)用的。一般禁止跳過中間件層直接調(diào)用底層操作系統(tǒng)的服務。1.18分布式系統(tǒng)有哪些計算模式？（必考）1.面向對象模式2.面向服務模式3.公用計算模式4.志愿參與模式（詳見書p21-p22頁）2.5有哪些名字服務形式？名字服務器的組成與功能是什么？名字服務形式：（1）名字服務：名字服務是根據(jù)實體的名字查找它的屬性（地址）。（2）目錄服務：目錄服務既可以根據(jù)實體的名字查找實體的屬性，當不知道實體名時也可以根據(jù)實體的一個或多個屬性及其值查找并得到一個匹配這些屬性的實體列表。（3）合約服務：是一種增強的目錄服務，通過技術規(guī)范來定位一個命名實體。名字服務器組成：（1）名字服務器操作 ：管理、查詢操作和行政管理。增加、刪除和修改上下文的目錄項。訪問優(yōu)先權。（2）名字解析 ：根據(jù)名字解析請求，得到被解析對象地址。（3）緩存 ：緩存名字查詢和解析的結果。（4）多副本管理 ：副本修改和副本一致性維護。（5）通信 ：客戶端的名字代理通信和名字服務器之間（6）數(shù)據(jù)庫 ：存放名字解析上下文或其子域。名字服務器功能：管理名字解析上下文、實現(xiàn)名字查詢與解析和其它名字服務器通信協(xié)調(diào)。2.7什么是迭代名字解析，什么是遞歸名字解析，它們各有什么優(yōu)缺點？迭代名字解析：建議考試畫圖解釋：遞歸名字解析：也畫圖解釋各自優(yōu)缺點：遞歸名字解析缺點：要求每臺名字服務器具有較高的性能。遞歸名字解析優(yōu)點：1.遞歸名字解析過程中，各名字服務器解析的緩存結果使用更為高效。2.如果主機與服務器距離很遠，那么采用遞歸名字解析將更為高效。迭代的優(yōu)缺點與上面相反。2.14什么是目錄服務？目錄項和屬性及屬性值的關系是什么？目錄服務：目錄服務既可以根據(jù)實體的名字查找實體的屬性，當不知道實體名時也可以根據(jù)實體的一個或多個屬性及其值查找并得到一個匹配這些屬性的實體列表。關系：目錄項是一個命名對象的信息集合。每個命名對象包括若干個屬性，每個屬性有一個屬性類型和相應的一個或多個屬性值。2.18輕量數(shù)據(jù)訪問協(xié)議LDAP和目錄訪問協(xié)議DAP的關系和區(qū)別是什么？1.LDAP的最初目標是向用戶提供目錄服務時避免DAP的大量開銷。2.LDAP的操作集對DAP做了簡化，刪除了read和list操作，用search代替。3.DAP是目錄用戶代理（DUA）與目錄系統(tǒng)代理（DSA）之間的請求/響應協(xié)議。LDAP是用戶用來訪問目錄服務的一個協(xié)議。4.建議再回答下LDAP的模型：3.7什么是遠程執(zhí)行邏輯機模型？對邏輯機模型的要求是什么？概念：建議畫圖。要求：（1）遠程進程必須能訪問駐留在源計算機上的文件系統(tǒng)。（2）遠程進程能接收邏輯機內(nèi)任何進程發(fā)來的信號，也能將信號提供給邏輯機內(nèi)任何進程。（3）進程組保持在邏輯機內(nèi)。（4）基于樹型的進程父子關系在邏輯機內(nèi)必須得以保持。3.13何為異步進程遷移算法？何為同步進程遷移算法？它們的優(yōu)缺點是什么？異步進程遷移算法：這類算法允許非遷移進程在遷移過程中繼續(xù)運算，只有遷移進程被中斷進行相關的操作。優(yōu)點：可以得到較好的執(zhí)行效率。缺點：和原有環(huán)境的兼容性不好，不能方便的移植。同步遷移算法：這類算法在遷移過程中所有進程（包括非遷移的協(xié)同進程）都被掛起，進程之間需要同步來清空通信信道中的中途消息，所有進程均要阻塞等待遷移事件完成后，才能從中斷處繼續(xù)運行。優(yōu)點：算法簡單，具有較好的可移植性和易于實現(xiàn)。缺點：需要中央控制管理進程參與，所有進程都被迫中斷，等待遷移過程的結束。3.15比較進程遠程執(zhí)行與進程遷移兩種機制。進程遠程執(zhí)行的要求：（1）尋找管理機制。（2）進程遠程執(zhí)行是透明的，應與位置無關。（3）主人優(yōu)先原則進程的遷移可以支持：（1）動態(tài)系統(tǒng)管理與維護（2）動態(tài)負載平衡（load balancing），系統(tǒng)中重負載處理機轉移一部分負載到輕負載的處理機上運行，使得整個集群系統(tǒng)中的所有處理機的負載趨向均衡，從而提高系統(tǒng)的整體運行效率。（3）系統(tǒng)容錯（4）主人優(yōu)先使用原則注：此題我未找到較好的答案。4.1在水平時間軸上表示阻塞發(fā)送/接收和非阻塞發(fā)送/接收進程與操作系統(tǒng)內(nèi)核之間操作的時間關系。沒有具體答案，先方便理解一下阻塞和非阻塞：阻塞和非阻塞關注的是程序在等待調(diào)用結果（消息，返回值）時的狀態(tài).阻塞調(diào)用是指調(diào)用結果返回之前，當前線程會被掛起。調(diào)用線程只有在得到結果之后才會返回。非阻塞調(diào)用指在不能立刻得到結果之前，該調(diào)用不會阻塞當前線程。例子：你打電話問書店老板有沒有分布式系統(tǒng)這本書，你如果是阻塞式調(diào)用，你會一直把自己“掛起”，直到得到這本書有沒有的結果，如果是非阻塞式調(diào)用，你不管老板有沒有告訴你，你自己先一邊去玩了， 當然你也要偶爾過幾分鐘check一下老板有沒有返回結果。這個圖不知道對不對：4.2試敘述如何實現(xiàn)阻塞發(fā)送/接收和非阻塞發(fā)送/接收，對操作系統(tǒng)有什么要求？通過發(fā)送原語send和接收原語receive實現(xiàn)要求操作系統(tǒng)能實現(xiàn)4種不同的可靠性語義。至少一次：保證正確完成消息傳送至少一次至多一次：保證正確完成消息傳送至多一次。在沒有節(jié)點崩潰和網(wǎng)絡斷開情況下，它只正確地執(zhí)行一次消息傳送。事務語義：它保證消息的原子性。不管節(jié)點崩潰或網(wǎng)絡端口與否，它或者完成一次消息傳送，或者什么也不做。精確一次：無論在什么情況下，保證正確完成一次消息傳送，不管是否有節(jié)點崩潰或網(wǎng)絡斷開，它接近某種程度的容錯機制。4.4對以下每個應用程序，你認為“至多一次”和“至少一次”語義哪個最好？（1）在文件服務器上讀寫文件：至少一次。（2）銀行服務：至多一次（3）編譯一個程序：至少一次4.9什么是因果定律？它和FIFO全定序相比，哪個更嚴格？因果定律：不管含有因果關系的消息是由同一個發(fā)送進程多播，還是不同發(fā)送進程多播，所有接收進程要保證先接收“因”消息，后接收“果”消息。FIFO：對同一個發(fā)送進程發(fā)出的多播消息，要求所有接收進程按發(fā)送的順序接收，而對不同發(fā)送進程的多播消息可按不同順序接收。相比之下，因果排序更嚴格。4.12RPC被認為是分布式最初的中間件，它能實現(xiàn)分布式系統(tǒng)的透明性嗎？p92 在RPC過程中，客戶可以簡單的忽略不關心的內(nèi)容，客戶并不直接執(zhí)行send和receive原語，也不關心消息的傳遞，所有這些都隱藏在樁中，從而實現(xiàn)RPC的透明性。建議；本題雖然已完，但最好將RPC的基本操作看一遍。5.7Richart_Agrawala算法如何改進了Lamport算法，它的優(yōu)點是什么？（必考）Lamport算法的開銷是3（N-1）個消息，Richart算法只要2（N-1）個消息，N是競爭資源的進程數(shù)。Lamport算法前2步：1.Pi 資源請求消息Request（Ti ：P i）發(fā)送2.Pj收到Request（T i：P i），按T順序置于其消息隊列，如果沒有資源請求或請求時間晚于收到消息的時間戳，回應Reply（T j：P j）Richart算法前2步：1.Pi 資源請求消息Request（Ti ：Pi）發(fā)送2.Pj收到Request（Ti：Pi），按T順序置于其消息隊列如果沒有資源請求或請求時間晚于收到消息的時間戳，回應Reply（Tj：Pj）；否則推遲返回應答消息進程從臨界區(qū)退出，向需要請請求資源的進程補發(fā)應答消息標紅處即為改進優(yōu)點：1.它具有對稱性2.具有完全的分布式控制3.對通信鏈路相對速度的不敏感性5.8比較集中式算法、Ricart_Agrawala算法和令牌算法的開銷和問題集中式算法的問題：容易出現(xiàn)單點故障Ricart算法的問題：由于不應答被認為是資源被占用，所以如果有某個節(jié)點故障，會導致該算法的異常終止。同時各進程對資源的使用情況缺乏了解。令牌算法的問題：檢測令牌丟失困難開銷：集中式算法開銷最大，Richar算法需要2（N-1）個消息，令牌算法最多需要N-1個消息。5.11共享K個相同資源的互斥算法和Ricart_Agrawala算法的共同點和區(qū)別是什么？相同點：基于相同的概念，每個競爭進程都維持一個推遲應答數(shù)組RD，數(shù)組元素是表示相應進程是否推遲發(fā)出應答消息。區(qū)別：1.應答消息到達的環(huán)境。在Ricart算法中，正在等待進入臨界區(qū)的進程要得到N-1個應答消息。在共享K個相同資源的互斥算法中，N-K個應答消息是在進程等待時到達，K-1個消息是進程已在臨界區(qū)或等待進入臨界區(qū)或離開臨界區(qū)后到達。2.在Ricart算法中，其他競爭進程推遲應答數(shù)組的每一項RDi是布爾型，因為應答只能是一個，或是推遲，或是不推遲。在共享K個相同資源的互斥算法中，可能有多個應答消息被推遲，這樣RDi應聲明為整數(shù)型。5.13在基于事件優(yōu)先權算法中，如何保證低優(yōu)先權的進程有機會進入臨界區(qū)，而不挨餓。沒找到答案，不敢亂寫。8.2圖8.1（b）為什么違背嚴格一致性？因為B讀到的不是a，而是數(shù)據(jù)項x的初值null，客戶A的寫操作沒有立即傳播到B，未能及時完成對副本的修改。8.3圖8.2（b）為什么違背順序一致性？因為進程C看到數(shù)據(jù)項x是先寫a后寫b，而進程D看到數(shù)據(jù)項x是先寫b后寫a。8.4圖8.3（c）為什么符合因果一致性定律？因為W（x）a和W（x）b是并發(fā)寫，因此也符合因果一致性要求。8.5圖8.4（b）為什么遵循因果一致性，但對FIFO一致性是無效的？看了半天暫時還不會，但是書p200-p205的幾種一致性必須弄懂，是必考的。8.7比較“傳播更新通知”、“傳播更新數(shù)據(jù)”和“傳播更新操作”和它們的應用場合傳播更新通知：只傳播一個簡短的數(shù)據(jù)通知，不包含其他信息。寫操作對讀操作的比率很高時，傳播效果好。傳播更新數(shù)據(jù)：在副本間傳送被修改過的數(shù)據(jù)。讀操作對寫操作的比率很高時，傳播效果好。傳播更新操作：不傳播被修改過的數(shù)據(jù)，而是告訴各副本應該執(zhí)行的操作。要求每個副本有一個進程來執(zhí)行更新操作，主動的保持各副本關聯(lián)數(shù)據(jù)的一致性。應用場合：傳播更新通知：無效化協(xié)議傳播更新數(shù)據(jù)：讀操作對寫操作的比率很高時傳播更新操作：主動復制8.9一個文件被復制在10個服務器上，列出表決算法的“讀集團”和“寫集團”。這是12個服務器是的例子：此算法要求N（R）+N（W）>N N（W）>N/2此題的N=10;那么寫集團可以為6 7 8 9 10相應的讀集團為5 6 7 8 9 10 （NW=6） 4 5 6 7 8 9 10(NW=7)以此類推。8.14在基于頁面的DSM中如何維護副本擁有者和副本集這類控制信息？擁有4種算法：集中管理算法固定分布管理算法廣播分布管理算法動態(tài)分布管理算法在書p223-225，此處不詳述。9.2分布式文件系統(tǒng)的共享語義指的是什么，有哪幾種共享語義？文件共享語義是為了理解文件的行為。不同共享語義將導致不同編程實現(xiàn)方法。種類：（1）UNIX語義（順序一致性語義）（2）會話語義（3）不修改共享文件語義（4）事務語義見書p2929.4NFS如何訪問遠程文件，它的虛擬文件系統(tǒng)的作用是什么？如何訪問：遠程共享文件或它的子目錄是通過虛inode（即vnode）形式掛接在本地文件目錄中。NFS客戶端與遠程文件系統(tǒng)服務器之間通信采用安全的遠程過程調(diào)用（RPC）方式，實現(xiàn)身份驗證和消息驗證，采用了RPC重傳技術，對文件共享進行訪問控制。作用：1.允許和操作系統(tǒng)使用不同的文件系統(tǒng)實現(xiàn)的接口。2.是物理文件系統(tǒng)與服務之間的一個接口層，對每個文件系統(tǒng)的所有細節(jié)進行抽象，使得不同的文件系統(tǒng)在系統(tǒng)中運行的其他進程看來，都是相同的。9.9NFS的RPC實現(xiàn)了何種可靠性語義？通過復合調(diào)用以及RPC重傳可靠性語義有：至少一次：保證正確完成消息傳送至少一次至多一次：保證正確完成消息傳送至多一次。在沒有節(jié)點崩潰和網(wǎng)絡斷開情況下，它只正確地執(zhí)行一次消息傳送。事務語義：它保證消息的原子性。不管節(jié)點崩潰或網(wǎng)絡端口與否，它或者完成一次消息傳送，或者什么也不做。精確一次：無論在什么情況下，保證正確完成一次消息傳送，不管是否有節(jié)點崩潰或網(wǎng)絡斷開，它接近某種程度的容錯機制。我們可以看出：符合“至少一次”的可靠性語義。11.5CORBA的主要特點是什么？功能是什么？簡述CORBA系統(tǒng)中ORB的作用。特點：（1）CORBA定義了一種面向對象的軟件構件構造方法，使不同的應用可以共享由此構造出來的軟件構件；（2）每個對象都將其內(nèi)部操作細節(jié)封裝起來，同時又向外界提供了精確定義的接口，從而降低了應用系統(tǒng)的復雜性，也降低了軟件開發(fā)費用；（3）CORBA的平臺無關性實現(xiàn)了對象的跨平臺引用，開發(fā)人員可以在更大的范圍內(nèi)選擇最實用的對象加入到自己的應用系統(tǒng)之中；（4）CORBA的語言無關性使開發(fā)人員可以在更大的范圍內(nèi)相互利用別人的編程技能和成果， 是實現(xiàn)軟件復用的實用化工具功能：（1）存取來自現(xiàn)行桌面應用程序的分布信息和資源；（2）使現(xiàn)有業(yè)務數(shù)據(jù)和系統(tǒng)成為可供利用的網(wǎng)絡資源；（3）為某一特定業(yè)務用的定制的功能和能力來增強現(xiàn)行桌面工具和應用程序；（4）改變和發(fā)展基于網(wǎng)絡的系統(tǒng)以反映新的拓撲結構或新資源；ORB的作用：ORB初始化 ORB接口操作 獲取初始對象引用 與線程有關的操作 策略設置與管理 對象引用操作11.6什么是接口定義語言？它在分布式計算環(huán)境中起到什么作用？概念：是一個描述軟件組件接口的語言規(guī)范。 IDL用中立語言的方式進行描述，能使軟件組件（不同語言編寫的）間相互通信。 IDL通常用于RPC（Remote Procedure Call，遠程過程調(diào)用）軟件。 IDL提供了一個“橋”來連接不同的系統(tǒng)。作用：（1）用IDL定義對象接口文件（2）用ORB攜帶的編譯器對IDL定義的對象接口文件進行編譯。然后將此圖畫上：11.7在CORBA的體系結構中，根據(jù)接口的可移植性和定義方式，接口分為哪幾類，各起什么作用？1.ORB核心實現(xiàn)對所有ORB都相同的接口2. 對象適配器接口連接對象實現(xiàn)和ORB。3. 接口定義語言IDL和靜態(tài)接口客戶用ORB攜帶的IDL編譯器，編譯對象接口IDL文件，生成特定編程語言（如C+）的Stub和Sleketon代碼。4. 動態(tài)接口在預先不知道服務對象接口的情況下，客戶通過查詢或采用其他手段獲得服務對象的接口描述信息，然后使用動態(tài)調(diào)用接口來構造客戶請求，并發(fā)送給對象實現(xiàn)。在對象實現(xiàn)方，可用動態(tài)骨架接口分發(fā)用戶請求的機制，以便動態(tài)處理客戶方的請求。11.17簡述JAVA RMI體系結構遠程方法調(diào)用RMI（Remote Method Invocation）是Java特有的分布式計算技術。它實質(zhì)上是通過Java編程語言擴展了常規(guī)的過程調(diào)用，在網(wǎng)上不僅可以傳送對象的數(shù)據(jù)，而且可以傳送對象的代碼?；卮鹣旅孢@張圖即可：12.6什么是web契約，它要說明什么問題？概念：契約是供求雙方間進行交換的一種約定，在面向服務的分布式計算系統(tǒng)中，契約是系統(tǒng)之間交換數(shù)據(jù)時應遵守的約定（技術契約）。說明的問題：服務功能描述（What） 服務訪問描述（How）服務位置描述（Where）12.7什么是服務的抽象描述？什么是服務的具體描述？它們描述的內(nèi)容是什么?抽象描述：即服務功能描述，表達了契約公開的接口具體內(nèi)容：端口類型（接口）定義（portType）操作定義（Operation Definition）消息定義（Message Definition）類型定義（Type Definition）策略定義（Policy Definition）具體描述：即服務訪問描述和服務位置描述，為抽象描述補充相關的實現(xiàn)細節(jié)，即如何訪問服務，同時關注從何處得到所需要的服務。具體內(nèi)容：端口類型（接口）綁定（Port Binding）操作綁定（Operaion Binding）消息綁定（Message Binding）服務定義（Service Definition）端口定義（Port Definition）地址定義（Address Definition）策略定義12.8什么是WSDL？它與XML有什么關系？WSDL用來描述什么實體？WSDL:即web服務描述語言。關系：1.wsdl是一個基于XML的語言，它描述 了和特定Web服務之間的交互機制，并且使用該語言可以約束服務提供者以及使用服務的所有請求者 2.wsdl是一個基于XML的規(guī)范模式， 提供了一個標準的服務表示語言，可用于描述Web服務所暴露的公共接口細節(jié)WSDL用于描述網(wǎng)絡服務。 12.9什么是SOAP？它與HTTP和WSDL有什么關系？SOAP:簡易對象訪問協(xié)議。關系：SOAP是個通信協(xié)議， SOAP在HTTP協(xié)議的基礎上，把編寫成XML的REQUEST參數(shù), 放在HTTP BODY上提交給WEB SERVICE服務器。WEB SERVICE服務器處理完成后，把結果也寫成XML作為RESPONSE送回用戶端，為了使用戶端和WEB SERVICE可以相互對應，可以使用WSDL作為這種通信方式的描述文件，利用WSDL工具可以自動生成WS和用戶端的框架文件。12.10什么是UDDI?它與HTTP、WSDL和SOAP的關系是什么？UDDI:通用描述、發(fā)現(xiàn)和集成關系：WSDL用來描述服務；UDDI用來注冊和查找服務；SOAP作為傳輸層，用來在消費者和服務提供者之間傳送消息。SOAP是Web服務的默認機制，其他的技術為可以服務實現(xiàn)其他類型的綁定。用戶可以在UDDI注冊表（registry）查找服務，取得服務的WSDL描述，然后通過SOAP來調(diào)用服務，同時UDDI采用的也是HTTP協(xié)議?；虼穑篧eb服務提供方通過WSDL描述所提供的服務,并將這一描述告知Web 服務注冊服務器。注冊服務器依據(jù)WSDL的描述,依照UDDI的協(xié)定更新服務目錄并在Internet 上發(fā)布。用戶在使用Web服務前先向注冊服務器發(fā)出請求,獲得Web 服務提供者的地址和服務接口信息,之后使用SOAP協(xié)議與Web服務提供者建立連接,進行通信。12.13什么是SOA概念框架？SOA試圖解決什么問題？SOA的概念架構采用分層模式，這個架構自底向上是操作系統(tǒng)層、服務組件層、服務層、業(yè)務流程編排層和訪問表現(xiàn)層。把圖畫上：試圖解決的問題：（1）企業(yè)業(yè)務模式的變化：傳統(tǒng)的業(yè)務部門的消失，如企業(yè)運輸部門（2）過去的IT系統(tǒng)建設以部門為基礎整合，是部門內(nèi)的垂直整合；現(xiàn)在需要在企業(yè)各部門間進行水平整合（3）企業(yè)IT系統(tǒng)抽象程度低（4）企業(yè)IT系統(tǒng)改變或者升級時，原有的硬件和軟件資源希望在新系統(tǒng)中盡可能重用12.17試述BPEL、SCA和SDO之間的關系1. 服務編排和流程整合服務的串聯(lián)，即業(yè)務流程BPEL、服務的構建和使用SCA數(shù)據(jù)的描述SDO，這三部分構成了SOA架構鐵三角2. SOA中，需要有數(shù)據(jù)模型與其他的數(shù)據(jù)模式交互（如數(shù)據(jù)庫，文件），與SCA相應的數(shù)據(jù)模型為SDO3. SCA組件的實現(xiàn)類型包括BPEL