第九章網絡及分布式操作系統(tǒng)

第九章網絡與分布式操作系統(tǒng)

由于網絡操作系統(tǒng)與分布式操作系統(tǒng)所采用的技術大多是相通的，幫將它們入在一起介紹。

9.1計算機網絡

一、網絡的概念：計算機網絡是利用通信設備和通信線路，將地理上分散而且有相對獨立功能的多個計算機系統(tǒng)，按照某種原則相互連接在一起構成的計算機體系，它是計算機技術和通信技術相結合的產物。二、網絡組成：1、組成：獨立計算機、通信處理機、通信線路。2.結點:網絡中的主機及所附帶的外部設備,也叫站點。

三、網絡分類：（一）按網絡覆蓋的地理范圍，可將網絡分為局域網和廣域網、城域網。（二）按照入網計算機的統(tǒng)一性分為：同構網絡和異構網絡1、同構網絡：在分布式操作系統(tǒng)中常采用同構網絡因為進程的動態(tài)遷移要求遷出站點與遷入站點具有相同或兼容的硬件環(huán)境。2、異構網絡：由不同類型的機器所構成的計算機網絡。在大型網絡操作系統(tǒng)中，常采用異構網絡，因為它對入網機器的類型沒有任何限制。四、網絡的拓撲：網絡系統(tǒng)中的各個站點在物理上的聯(lián)結方式。每種拓撲結構各有優(yōu)點、缺點，對拓撲結構的評估常用以下標準：1、基本成本：將系統(tǒng)中各站點聯(lián)結起來所花費的代價。2、通信成本：把一個信息由站點A傳送到站點B的距離3、可靠性：如果一個通信鏈或站點失效，是否影響基余站點之間的通信。（一）全聯(lián)通拓樸結構：每個站點都直接與其它站點相連，這種結構的代價是昂貴的，因系統(tǒng)中任兩個站點之間必須有直接的通信鏈。*基本成本高，按站點數(shù)成平方地增長。*傳送速度快，因任兩站點間的信息傳送僅涉及一條通信鏈*可靠性高，因僅當所有通信鏈都失效時，系統(tǒng)割裂。（二）部分互聯(lián)結構：1、僅在一部分站點之間存在通信鏈，因而基本成本較低。2、通信速度慢，由消息的傳遞可能要經過幾個中間站點。3、可靠性較差。（三）層次結構：除根站點外，每個站點均有唯一的父親和若干個兒子1、基本成本低2、通信時往往要涉及幾個節(jié)點3、除葉站點外，任何一個站點的失效將把網絡分割為幾個互不相交的子樹。（四）星型結構：1、基本成本與站點數(shù)成線性比例關系2、通信成本較低因一個站點與另一個站點之間的通信至多僅需兩步。3、可靠性差:一方面中心站點可能成為系統(tǒng)的瓶頸，另一方面，中心站點一旦失效，網絡癱瘓。（五）環(huán)形結構（六）總線結構

9.2通信與協(xié)議1、OSI：由ISO制訂的開放系統(tǒng)參考模型OSI成為網絡通信的標準，邏輯上，不同主機的各層之間能相互通信（對等通信）。2、協(xié)議：不同主機相同層次間對等的通信規(guī)則稱為協(xié)議，K層之間的對等通信協(xié)議稱為K層協(xié)議。在實現(xiàn)時，信息自發(fā)送站點由上層向下層傳遞，橫向止于物理層，最后在接收站點自下層至上層縱向傳遞。發(fā)送站點的每一層均對信息做某種處理，加上一個“頭”，然后向下層傳播，接收站點的每一層將對應的“頭”去掉。3、

OSI中，各層協(xié)議主要功能：（1）物理層：負責兩個站點之間字位流的傳輸。（2）鏈路層，負責提供傳輸錯誤的恢復功能（3）網絡層：負責將消息分解為傳輸單位，并選擇路徑。（4）傳輸層：負責站點之間的消息傳送。（5）會話層：負責進程間通信。（6）表示層：負責數(shù)據轉換。（7）應用層：負責提供用戶界面。

9.3計算模型一、數(shù)據遷移：當處于站點A的用戶想要存取駐留于站點B的數(shù)據（文件）時，系統(tǒng)有兩種方式：（1）將整個文件都傳送給站點A,此后對文件的訪問便成為局部的了，當用戶A不再需要該文件時，它便被送回到站點B。

（2）僅將文件的一部分傳送到A，如果以后還需要，再傳送另一部分，當站點A用戶不再需要該文件時，將其修改部分傳送回站點B。二、計算遷移在某些環(huán)境中，遷移計算比遷移數(shù)據效果更好例如：設站點A處的進程P要使用站點B處的文件，它不是將B處的文件取過來，而是執(zhí)行一個遠程過程調用，以調用一個在B點已定義好的過程，該過程可對P所需的文件進行適當計算，然后將結果發(fā)送給進程P。另一種方法是：進程P發(fā)一個消息到站點B，然后由站點B處的操作系統(tǒng)創(chuàng)建一個代理進程Q，其功能是執(zhí)行P所指定的任務，當Q完成使命后，通過消息將結果送給P，此法允許P、Q在不同站點并行。三、作業(yè)遷移當一個作業(yè)到達時，它可以全部或部分地在不同站點處執(zhí)行，其優(yōu)點是：1、負載平衡：作業(yè)或作業(yè)步可以在網上分布以均衡工作負載，2、計算加速：如果一個作業(yè)可以劃分為若干子作業(yè)，這些子作業(yè)可以在不同站點處并行執(zhí)行，則整個作業(yè)的處理時間能被縮短。3、硬件優(yōu)選：有些作業(yè)可能只適合于在專用處理機上運行，例如矩際求逆。4、軟件優(yōu)選：有的作業(yè)可能需要某些站點處的特別軟件，而該軟件不適合遷移，或遷移開銷比作業(yè)開銷大。四、進程遷移：進程遷移是將正運行于某站點處理的進程遷移到另一站點，由于在遷移時刻進程已經在原站點運行了一段時間，遷移時不僅需要遷移其代碼和數(shù)據，還應遷移與進程有關的數(shù)據結構，即進程控制塊，進程遷移的目的是實現(xiàn)負載平衡。

9.4事件定序即確定兩個事件發(fā)生的先后次序關系，這在集中或緊耦合系統(tǒng)中是容易做到的，因系統(tǒng)中只有一個公共內存和一個實時時鐘；然而在網絡和分布式系統(tǒng)中，沒有公共內存和實時時鐘，要確定事件發(fā)生的次序有時是不可能的，網絡或分布式系統(tǒng)中的“前發(fā)生”關系只是一種偏序（非自反）。一、前發(fā)生關系：1、進程內的事件：由于一個進程用的程序是有序的而且在各自的處理機上運行，故一個進程內的所有事件是有序的。2、前發(fā)生關系：（1）如果A和B是同一進程內部的事件，而且A在B前執(zhí)行，則AB（2）如果A是一個由某一進程發(fā)送消息的事件，B是由另一進程接收該消息的事件，則AB；（消息只有在被發(fā)送后才能被接收）。（3）如果AB且BC，則有AC.由于一個事件不可能在其本身之前發(fā)生，因而關系“”是非自反的偏序。

如果兩事件A和B之間不存在“”關系，則二者

可以并發(fā)執(zhí)行，且它們之間無因果關系。例：三個進程P、Q、R，它們在不同處理機上運行，圖中圓圈表示事件，箭頭表示進程間的消息傳送，由圖可知：(參見備課本)

二、全序關系：為了確定兩事件發(fā)生的次序，或者需要一個公共時鐘，或需要完全同步的時鐘，在網絡和分布式系統(tǒng)中很難實現(xiàn)：1、定義：（在不使用物理時鐘前提下定義前發(fā)生關系）全序要求：對于事件A和B，如果AB，則A的郵戳時間應小于B的郵戳時間。2、在分布式和網絡中實現(xiàn)上述全序要求方法：在每個進程內部定義一個邏輯時鐘LCi；它給同一進程內的各事件賦予不同的數(shù)：某一事件的邏輯時鐘值就是它的時間郵戳，在一進程內部，邏輯時鐘可以保證：如果事件A在事件B之前發(fā)生，則有Lci(A)<Lci(B).在不同的進程之間此法行不通。例：設兩個進程P1和P2相互通信，假設P1于Lci(A)=200時發(fā)送消息給P2（事件A），而P2于Lci(B)=190時接收到此消息(事件B)，顯然違反定義。解決上述矛盾的方法是：進程在接受到一個消息時，而且該消息的郵戳時間比接收進程的郵戳時間當前值還大時，接收進程推進他的邏輯時鐘。具體地，如果進程P接到一個郵戳時間為t的消息(事件B)，Lci(B)<t,則她推進其時鐘，使Lci(B)=t+1。

9.5進程互斥為了解決網絡和分布式系統(tǒng)中互斥問題，必須提供類似信號燈的同步機構。為簡單起見，這里只討論二值信號燈的實現(xiàn)（相當于鎖），由于網絡和分布式系統(tǒng)中的互斥所涉及的進程可能位于不同站點，它們之間沒有公共內存，因此比較復雜，這里假設共有n個處理機，所有處理機依次編號為1—N，每個處理機中僅有一個進程，且進程與處理機具有相同編號。

一、集中方式：1、基本思想：系統(tǒng)中有一個進程負責協(xié)調對于臨界區(qū)的進入。每一個要求進入臨界區(qū)的進程都必須發(fā)送一個請求給協(xié)調者進程，僅當收到協(xié)調者進程的回答信號后，它才能進入自己的臨界區(qū)；當一個進程退出臨界區(qū)時，也需發(fā)送一個釋放信號給協(xié)調者進程，然后繼續(xù)執(zhí)行。當收到一個請求消息時，協(xié)調者進程需考查是否有某些進程正在其臨界區(qū)內，若無，協(xié)調者進程發(fā)送一個回答消息給請求進程，否則請求進程需排隊等待，若協(xié)調者進程收到一個釋放消息，則它給等待隊列中的某一進程發(fā)送回答信號允許它進入其臨界區(qū)。2、特點：（1）無死鎖（2）如協(xié)調者進程是公平的，如FCS,則不會發(fā)生“餓死”現(xiàn)象。（3）每次進入臨界區(qū)需三個消息：請求、回答、釋放.二、分布方式：1、方法：當一個進程P要進入其臨界區(qū)時。它產生一個新的時間郵戳TS，并發(fā)送一個Request(P,TS)給所有其它進程，當某個進程接收到此消息時它可能立即回答（如果它當前不在其臨界區(qū)內）；也可能延遲回答（如果它當前正在其臨界區(qū)內）。一個收到系統(tǒng)中所有進程回答信號的進程可以進入它的臨界區(qū)，當一個進程退出其臨界區(qū)后，它需要給所有向它發(fā)來請求消息的進程發(fā)送回答消息。2、進程作出立即回答或延遲回答的決定因素：（1）如果進程正在它的臨界區(qū)內，延遲回答（2）如果一個進程不想進入特的臨界區(qū)，立即回答;(2)如果一個進程想進入但尚未進入它的臨界區(qū)，該進程考查所有保存的請求表，此表用于保存該進程已收到但尚未回答的消息，并將當前收到的REQUEST(P,TS)消息中的TS與該表中所有消息的TS作比較，如果這個TS比表中所有消息的TS都小,則立即回答進程P，否則REQUEST被加到等待表中3、上述算法特性：（1）可實現(xiàn)互斥（2）確保無死鎖（3）無“餓死“情況（4）每次進入臨界區(qū)需2（N-1）個消息。三、標志傳遞方式：1、方法：該法僅適用于邏輯拓樸結構為環(huán)形的系統(tǒng)，為實現(xiàn)互斥，系統(tǒng)中有一個標志。它作為特殊類型的消息在系統(tǒng)中環(huán)行。當一個進程接收到這個標志后，它就可以進入其臨界區(qū)，并扣留這個標志；當它退出臨界區(qū)之后，標志才被釋放，并沿環(huán)路繼續(xù)繞行，如果一個接收到標志的進程并不想進入其臨界區(qū)，只需放行此標志。2、此法特點：（1）可實現(xiàn)互斥。因系統(tǒng)中只有一個標志，則最多只有一個進程在其臨界區(qū)內。（2）無“餓死”情況（在單向環(huán)形系統(tǒng)中）（3）兩種失效情況：一是如果標志丟失，則應能發(fā)現(xiàn)并選擇一個進程產生新標志。二是如果一個進程夭折了，則邏輯環(huán)斷裂，此時系統(tǒng)應能重構一個新的邏輯環(huán)。

9.6進程同步與進程通信在網絡與分布式系統(tǒng)中，同步機制與通信機制通常結合在一起:通信可以同步進行，也可以異步進行，對于前者，通信伴隨著同步；對于后者，通信不伴隨同步。當通信信息量為零時，進程之間便可以實現(xiàn)單一的同步。同步與通信機制常分為兩類，消息傳遞和遠程過程調用。一、消息傳遞：消息傳遞分為同步和異步兩類，前者需等待接收者的回答后繼續(xù)，后者不需等待來自接收者的回答。（一）同步消息傳遞：1、需提供以下系統(tǒng)調用命令：（1）發(fā)送命令：send（接收者、消息、回答）將消息發(fā)送到指定的接收者，然后掛起，等待來自接收者的回答，之后繼續(xù)。（2）接收命令：receive（發(fā)送者、消息），等待接收來自發(fā)送進程的消息。（3）回答命令：reply（發(fā)送者，回答），將回答信息傳給發(fā)送進程，使之繼續(xù)執(zhí)行。2、異步消息傳遞的形式(高等教育出版社《操作系統(tǒng)教程》周長林P219)(一)異步消息傳遞：1、所需系統(tǒng)調用命令：(1)發(fā)送命令：send（接收者，消息/回答），將消息或回答發(fā)害給接收者，然后繼續(xù)。(2)接收命令：receive（發(fā)送者，消息/回答），由發(fā)送者處接收消息或回答，然后繼續(xù)2、進程間異步消息傳遞形式：利用發(fā)送命令與接收命令可在任意時刻實現(xiàn)同步要求：(P219)二、遠程過程調用：與一般的過程調用相比較，遠程過程調用的突出特點是調用者與被調用者分別屬于不同進程，它們均是主動體，而且二者常運行于網絡或分布式系統(tǒng)中不同站點上，這帶來如下問題：(1)在本地過程調用中，調用參數(shù)及返回結果一般通過堆棧在調用者與被調用者之間傳遞；而在遠程調用中，調用參數(shù)與結果通常作為消息在調用者之間傳遞；(2)在本地過程調用中，調用過程與被調用過程同時存在，并且屬于同一地址空間，而在遠程過程調中，調用者與被調用者有不同的生存期，而且通常無公共存儲區(qū)域。(一)遠程過程調用形式(P220圖10-12)方法：調用進程稱作顧客進程，被調用進程稱為服務進程，顧客進程調用服務進程中的過程，調用參數(shù)以消息的形式由調用者傳送給被調用者,調用者掛起，被調用者執(zhí)行相應的過程，執(zhí)行完畢將返回值以消息形式傳送給調用者，然后二者分別繼續(xù)。(二)遠程過程調用的實現(xiàn)：在遠程過程所在站點內，應當存在一個“代理進程”，它受調用進程之托，執(zhí)行被調用的遠程過程，代理進程和調用進程有不同生存期，這有以下情況:(1)對每一個遠程過程調用建立一個代理進程，即代理進程在調用時建立，結束時撤消，這樣，代理進程的生存期間調用期間，一個站點可以同時存在多個執(zhí)行同一遠程過程的進程，并發(fā)性好，空間開銷小，時間開銷大。(2)對每位顧客建立一個代理進程，即顧客進程開始時建立代理進程，顧客進程結束時撤消代理進程,這樣，代理進程生存期與顧客進程相同。一個站點可以同時存在多個執(zhí)行同一遠程進程的進程，并發(fā)性好，空間開銷大，時間開銷小。(3)為每次服務建立一個代理進程，即在一個站點中僅存在一個執(zhí)行遠程過程的代理進程，該進程不間斷地執(zhí)行，讀取服務請求消息，執(zhí)行相應過程,然后返回回答消息，這一服務進程可被多個顧客調用，此時，時間與空間開銷較小，但響應速度慢。

9.7死鎖處理傳統(tǒng)系統(tǒng)中所用的死鎖預防、避免，以及檢測等算法的思想一般也適合于網絡和分存式系統(tǒng)，只需做某些適當?shù)男薷?。例如：只要在系統(tǒng)事件之間定義一個全序，資源分配預防死鎖技術就可用于網絡和分布式環(huán)境中，也即，系統(tǒng)內所有資源被賦予一個唯一的編號，一個進程可以要求一個編號為I的資源，當且僅當它未占有編號比I更小的資源。只要確定系統(tǒng)中某個進程為銀行家，由它保持執(zhí)行銀行家算法所必需的信息，并負責系統(tǒng)中資源的分配，則銀行家算法也同樣適合于網絡和分布式系統(tǒng)一、死鎖預防：(一)死鎖產生的四個必要條件：互斥條件，請求和保持條件、不剝奪條件、環(huán)路等待條件(二)網絡與分布式系統(tǒng)中預防死鎖的方法：通過剝奪資源以破壞循環(huán)等待條件。方法：賦給每個進程一個唯一的優(yōu)先數(shù)，這個優(yōu)先數(shù)被用于決定一個進程Pi是否等待另外一個進程Pi。例如：如果Pi具有更高的優(yōu)先數(shù)，可以令Pi等待Pj，否則Pi回退，即死掉。缺陷：可能出現(xiàn)餓死現(xiàn)象，因為有些低優(yōu)先級的進程可能總是被回退，為此有人提出用時間郵戳的設象，系統(tǒng)中的每個進程，在其產生時