第九章網(wǎng)絡(luò)與分布式操作系統(tǒng)-piazza

1、Centralized vs Distributed Systems,Centralized System: System in which major functions are performed by a single physical computerOriginally, everything on single computerLater: client/server modelDistributed System:

2、physically separate computers working together on some taskEarly model: multiple servers working togetherProbably in the same room or buildingOften called a “cluster”Later models: peer-to-peer/wide-spread collaborati

3、on,Distributed Systems: Motivation/Issues,Why do we want distributed systems?Cheaper and easier to build lots of simple computersEasier to add power incrementallyUsers can have complete control over some componentsCo

4、llaboration: Much easier for users to collaborate through network resources (such as network file systems)The promise of distributed systems:Higher availability: one machine goes down, use anotherBetter durability: st

5、ore data in multiple locationsMore security: each piece easier to make secure Reality has been disappointingWorse availability: depend on every machine being upLamport: “a distributed system is one where I can’t do w

6、ork because some machine I’ve never heard of isn’t working!”Worse reliability: can lose data if any machine crashesWorse security: anyone in world can break into systemCoordination is more difficultMust coordinate mu

7、ltiple copies of shared state information (using only a network)What would be easy in a centralized system becomes a lot more difficult,Distributed Systems: Goals/Requirements,Transparency: the ability of the system to

8、mask its complexity behind a simple interfacePossible transparencies:Location: Can’t tell where resources are locatedMigration: Resources may move without the user knowingReplication: Can’t tell how many copies of re

9、source existConcurrency: Can’t tell how many users there areParallelism: System may speed up large jobs by spliting them into smaller piecesFault Tolerance: System may hide varoius things that go wrong in the systemT

10、ransparency and collaboration require some way for different processors to communicate with one another,,Networking Definitions,Network: physical connection that allows two computers to communicatePacket: unit of transf

11、er, sequence of bits carried over the networkNetwork carries packets from one CPU to anotherDestination gets interrupt when packet arrivesProtocol: agreement between two parties as to how information is to be transmit

12、ted,網(wǎng)絡(luò)與分布式操作系統(tǒng),由于網(wǎng)絡(luò)操作系統(tǒng)與分布式操作系統(tǒng)所采用的技術(shù)大多是相通的，將它們放在一起介紹。   計算機網(wǎng)絡(luò)  一、網(wǎng)絡(luò)的概念： 計算機網(wǎng)絡(luò)是利用通信設(shè)備和通信線路，將地理上分散而且有相對獨立功能的多個計算機系統(tǒng)，按照某種原則相互連接在一起構(gòu)成的計算機體系，它是計算機技術(shù)和通信技術(shù)相結(jié)合的產(chǎn)物。 二、網(wǎng)絡(luò)組成： 1、組成：

13、獨立計算機、通信處理機、通信線路。 2.結(jié)點:網(wǎng)絡(luò)中的主機及所附帶的外部設(shè)備,也叫站點。,三、網(wǎng)絡(luò)分類： （一）按網(wǎng)絡(luò)覆蓋的地理范圍，可將網(wǎng)絡(luò)分為局域網(wǎng) 和廣域網(wǎng)、城域網(wǎng)。 （二）按照入網(wǎng)計算機的統(tǒng)一性分為：同構(gòu)網(wǎng)絡(luò)和異 構(gòu)網(wǎng)絡(luò) 1、同構(gòu)網(wǎng)絡(luò)：在分布式操作系統(tǒng)中常采用同構(gòu)網(wǎng)絡(luò)因為進程的動態(tài)遷移要求遷出站點與遷

14、入站點具有相同或兼容的硬件環(huán)境。 2、異構(gòu)網(wǎng)絡(luò)：由不同類型的機器所構(gòu)成的計算機網(wǎng)絡(luò)。在大型網(wǎng)絡(luò)操作系統(tǒng)中，常采用異構(gòu)網(wǎng)絡(luò)，因為它對入網(wǎng)機器的類型沒有任何限制。,四、網(wǎng)絡(luò)的拓?fù)洌?網(wǎng)絡(luò)系統(tǒng)中的各個站點在物理上的聯(lián)結(jié)方式。每種拓?fù)浣Y(jié)構(gòu)各有優(yōu)點、缺點，對拓?fù)浣Y(jié)構(gòu)的評估常用以下標(biāo)準(zhǔn)： 1、基本成本：將系統(tǒng)中各站點聯(lián)結(jié)起來所花費的代 價。

15、 2、通信成本：把一個信息由站點A傳送到站點B的距離 3、可靠性：如果一個通信鏈或站點失效，是否影響基余站點之間的通信。 （一）全聯(lián)通拓樸結(jié)構(gòu)：每個站點都直接與其它站點相連，這種結(jié)構(gòu)的代價是昂貴的，因系統(tǒng)中任兩個站點之間必須有直接的通信鏈。 *基本成本高，按站點數(shù)成平方地增長。 *傳送速度快，因任兩站點間的信息傳送僅涉及一條通信鏈

16、 *可靠性高，因僅當(dāng)所有通信鏈都失效時，系統(tǒng)割裂。（二）部分互聯(lián)結(jié)構(gòu)： 1、僅在一部分站點之間存在通信鏈，因而基本成本較低。 2、通信速度慢，由消息的傳遞可能要經(jīng)過幾個中間站點。 3、可靠性較差。,（三）層次結(jié)構(gòu)： 除根站點外，每個站點均有唯一的父節(jié)點和若干個子節(jié)點 1、基本成本低

17、 2、通信時往往要涉及幾個節(jié)點 3、除葉站點外，任何一個站點的失效將導(dǎo)致不連通 （四）星型結(jié)構(gòu)： 1、基本成本與站點數(shù)成線性比例關(guān)系 2、通信成本較低因一個站點與另一個站點之間的通信至多僅需兩步。 3、可靠性差:一方面中心站點可能成為系統(tǒng)的瓶頸，另一方面，中心站點一旦失效，網(wǎng)絡(luò)癱瘓。 （五）環(huán)形結(jié)構(gòu) （六）

18、總線結(jié)構(gòu),通信與協(xié)議OSI中，各層協(xié)議主要功能： （1）物理層：負(fù)責(zé)兩個站點之間字位流的傳輸。 （2）鏈路層，負(fù)責(zé)提供傳輸錯誤的恢復(fù)功能 （3）網(wǎng)絡(luò)層：負(fù)責(zé)將消息分解為傳輸單位，并選擇路 徑。 （4）傳輸層：負(fù)責(zé)站點之間的消息傳送。 （5）會話層：負(fù)責(zé)進程間通信。 （6）表示層：負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)換。 （7）應(yīng)用層：負(fù)責(zé)提供用戶界面。,R

19、outing,Routing: the process of forwarding packets hop-by-hop through routers to reach their destinationNeed more than just a destination address! Need a pathPost Office Analogy:Destination address on each letter is

20、not sufficient to get it to the destinationTo get a letter from here to Florida, must route to local post office, sorted and sent on plane to somewhere in Florida, be routed to post office, sorted and sent with carrier

21、 who knows where street and house is…Internet routing mechanism: routing tablesEach router does table lookup to decide which link to use to get packet closer to destinationDon’t need 4 billion entries in table: routin

22、g is by subnetCould packets be sent in a loop? Yes, if tables incorrectRouting table contains:Destination address range ? output link closer to destinationDefault entry (for subnets without explicit entries),Naming

23、in the Internet,How to map human-readable names to IP addresses?E.g. www.berkeley.edu ? 128.32.139.48E.g. www.google.com ? different addresses depending on location, and loadWhy is this necessary?IP addresses are har

24、d to rememberIP addresses change:Say, Server 1 crashes gets replaced by Server 2Or – google.com handled by different serversMechanism: Domain Naming System (DNS),Setting up Routing Tables,How do you set up routing ta

25、bles?Internet has no centralized state!No single machine knows entire topologyTopology constantly changing (faults, reconfiguration, etc)Need dynamic algorithm that acquires routing tablesIdeally, have one entry per

26、 subnet or portion of addressCould have “default” routes that send packets for unknown subnets to a different router that has more informationPossible algorithm for acquiring routing tableRouting table has “cost” for

27、each entryIncludes number of hops to destination, congestion, etc.Entries for unknown subnets have infinite costNeighbors periodically exchange routing tablesIf neighbor knows cheaper route to a subnet, replace your

28、entry with neighbors entry (+1 for hop to neighbor)In reality:Internet has networks of many different scalesDifferent algorithms run at different scales,Domain Name System,DNS is a hierarchical mechanism for naming N

29、ame divided in domains, right to left: www.eecs.berkeley.eduEach domain owned by a particular organizationTop level handled by ICANN (Internet Corporation for Assigned Numbers and Names)Subsequent levels owned by orga

30、nizationsResolution: series of queries to successive serversCaching: queries take time, so results cached for period of time,Top-level,com,edu,Mit.edu,169.229.131.81,128.32.61.103,128.32.139.48,berkeley.edu,www,calmail

31、,eecs,,,berkeley,MIT,,,,,,,How Important is Correct Resolution?,If attacker manages to give incorrect mapping:Can get someone to route to server, thinking that they are routing to a different serverGet them to log into

32、 “bank” – give up username and passwordIs DNS Secure?Definitely a weak linkWhat if “response” returned from different server than original query?Get person to use incorrect IP address!Attempt to avoid substitution a

33、ttacks:Query includes random number which must be returned July 2008 hole in DNS security located!Dan Kaminsky (security researcher) discovered an attack that broke DNS globallyOne person in an ISP convinced to load

34、particular web page, then all users of that ISP end up pointing at wrong addressHigh profile, highly advertised need for patching DNS Big press release, lots of mysterySecurity researchers told no speculation until pa

35、tches applied,計算機模型 一、數(shù)據(jù)遷移： 當(dāng)處于站點A的用戶想要存取駐留于站點B的數(shù)據(jù)（文件）時，系統(tǒng)有兩種方式：（1）將整個文件都傳送給站點A,此后對文件的訪問便成為局部的了， 當(dāng)用戶A不再需要該文件時，它便被送回到站點B。（2）僅將文件的一部分傳送到A，如果以后還需要，再傳送另一部分，當(dāng)站點A用戶不再需要該文件時， 將其修改部分傳送回站點B。 二、計

36、算遷移 在某些環(huán)境中，遷移計算比遷移數(shù)據(jù)效果更好例如：設(shè)站點A處的進程P要使用站點B處的文件，它不是將B處的文件取過來，而是執(zhí)行一個遠(yuǎn)程過程調(diào)用，以調(diào)用一個在B點已定義好的過程，該過程可對P所需的文件進行適當(dāng)計算，然后將結(jié)果發(fā)送給進程P。 另一種方法是：進程P發(fā)一個消息到站點B，然后由站點B處的操作系統(tǒng)創(chuàng)建一個代理進程Q，其功能是執(zhí)行P所指定的任務(wù)，當(dāng)Q完成使命后，通過消 息將結(jié)果

37、送給P，此法允許P、Q在不同站點并行。,三、作業(yè)遷移 當(dāng)一個作業(yè)到達時，它可以全部或部分地在不同站點處執(zhí)行，其優(yōu)點是： 1、負(fù)載平衡：作業(yè)或作業(yè)步可以在網(wǎng)上分布以均衡工作負(fù)載， 2、計算加速：如果一個作業(yè)可以劃分為若干子作業(yè)，這些子作業(yè)可以在不同站點處并行執(zhí)行，則整個作業(yè)的處理時間能被縮短。 3、硬件優(yōu)選：有些作業(yè)可能只適合于在專用處理機上運行，例如矩際求逆。

38、 4、軟件優(yōu)選：有的作業(yè)可能需要某些站點處的特別軟件，而該軟件不適合遷移，或遷移開銷比作業(yè)開銷大。 四、進程遷移： 進程遷移是將正運行于某站點處理的進程遷移到另一站點，由于在遷移時刻進程已經(jīng)在原站點運行了一段時間，遷移時不僅需要遷移其代碼和數(shù)據(jù)，還應(yīng)遷移與進程有關(guān)的數(shù)據(jù)結(jié)構(gòu)，即進程控制塊，進程遷移的目的是實現(xiàn)負(fù)載平衡。,互斥 為了解決網(wǎng)絡(luò)和分布式系統(tǒng)中互斥問題，必須提供類似信號燈的同步機構(gòu)。為簡單起見，這里只討論

39、二值信號燈的實現(xiàn)（相當(dāng)于鎖），由于網(wǎng)絡(luò)和分布式系統(tǒng)中的互斥所涉及的進程可能位于不同站點，它們之間沒有公共內(nèi)存，因此比較復(fù)雜，這里假設(shè)共有n個處理機，所有處理機依次編號為1—N，每個處理機中僅有一個進程，且進程與處理機具有相同編號。 一、集中方式： 1、基本思想：系統(tǒng)中有一個進程負(fù)責(zé)協(xié)調(diào)對于臨界區(qū)的進入。每一個要求進入臨界區(qū)的進程都必須發(fā)送一個請求給協(xié)調(diào)者進程，僅當(dāng)收到協(xié)調(diào)者進程的回答信號后，它才能進入自己的臨界區(qū)；當(dāng)一

40、個進程退出臨界區(qū)時，也需發(fā)送一個釋放信號給協(xié)調(diào)者進程，然后繼續(xù)執(zhí)行。 當(dāng)收到一個請求消息時，協(xié)調(diào)者進程需考查是否有某些進程正在其臨界區(qū)內(nèi)，若無，協(xié)調(diào)者進程發(fā)送一個回答消息給請求進程，否則請求進程需排隊等待，若協(xié)調(diào)者進程收到一個釋放消息，則它給等待隊列中的某一進程發(fā)送回答信號允許它進入其臨界區(qū)。 2、特點： （1）無死鎖 （2）如協(xié)調(diào)者進程是公平的，如FCS,則不會發(fā)生“饑餓”現(xiàn)象。

41、 （3）每次進入臨界區(qū)需三個消息：請求、回答、釋放.,二、分布方式： 1、方法：當(dāng)一個進程P要進入其臨界區(qū)時。它產(chǎn)生一個新的時間郵戳TS，并發(fā)送一個Request(P,TS)給所有其它進程，當(dāng)某個進程接收到此消息時它可能立即回答（如果它當(dāng)前不在其臨界區(qū)內(nèi)）；也可能延遲回答（如果它當(dāng)前正在其臨界區(qū)內(nèi)）。一個收到系統(tǒng)中所有進程回答信號的進程可以進入它的臨界區(qū)，當(dāng)一個進程退出其臨界區(qū)后，它需要給所有向它發(fā)來請求消息的進程發(fā)送回

42、答消息。 2、進程作出立即回答或延遲回答的決定因素： （1）如果進程正在它的臨界區(qū)內(nèi)，延遲回答 （2）如果一個進程不想進入特的臨界區(qū)，立即回答; (2)如果一個進程想進入但尚未進入它的臨界區(qū)，該進程考查所有保存的請求表，此表用于保存該進程已 收到但尚未回答的消息，并將當(dāng)前收到的REQUEST(P,TS)消息中的TS與該表中所有消息的TS作比較，如果這個TS比表中所有消息的TS都小,則立即回答進程P

43、，否則REQUEST被加到等待表中 3、上述算法特性： （1）可實現(xiàn)互斥 （2）確保無死鎖 （3）無“餓死“情況 （4）每次進入臨界區(qū)需2（N-1）個消息。,DISTRIBUTED COORDINATION,FULLY DISTRIBUTED APPROACH Approach due to Lamport. These are the general propert

44、ies for the method:The general mechanism is for a process P[i] to send a request ( with ID and time stamp ) to all other processes.When a process P[j] receives such a request, it may reply immediately or it may defe

45、r sending a reply back.When responses are received from all processes, then P[i] can enter its Critical Section.When P[i] exits its critical section, the process sends reply messages to all its deferred requests.,Mut

46、ual Exclusion/Synchronization,DISTRIBUTED COORDINATION,FULLY DISTRIBUTED APPROACH The general rules for reply for processes receiving a request: If P[j] receives a request, and P[j] process is in its critic

47、al section, defer (hold off) the response to P[i].If P[j] receives a request,, and not in critical section, and doesn't want to get in, then reply immediately to P[i].If P[j] wants to enter its critical secti

48、on but has not yet entered it, then it compares its own timestamp TS[j] with the timestamp TS[i] from T[i].If TS[j] > TS[i], then it sends a reply immediately to P[i]. P[i] asked first.Otherwise the reply

49、is deferred until after P[j] finishes its critical section.,Mutual Exclusion/Synchronization,DISTRIBUTED COORDINATION,The Fully Distributed Approach assures: Mutual exclusionFreedom from deadlockFreedom from st

50、arvation, since entry to the critical section is scheduled according to the timestamp ordering. The timestamp ordering ensures that processes are served in a first-come, first-served order.2 X ( n - 1 ) messages needed

51、 for each entry. This is the minimum number of required messages per critical-section entry when processes act independently and concurrently. Problems with the method include: Need to know identity of ev

52、eryone in system.Fails if anyone dies - must continually monitor the state of all processes.Processes are always coming and going so it's hard to maintain current data.,Mutual Exclusion/Synchronization,三、令牌傳遞方式：

53、 1、方法：該法僅適用于邏輯拓樸結(jié)構(gòu)為環(huán)形的系統(tǒng)，為 實現(xiàn)互斥，系統(tǒng)中有一個標(biāo)志。它作為特殊類型的 消息在系統(tǒng)中環(huán)行。當(dāng)一個進程接收到這個標(biāo)志后， 它就可以進入其臨界區(qū)，并扣留這個標(biāo)志；當(dāng)它退出 臨界區(qū)之后，標(biāo)志才被釋放，并沿環(huán)路繼續(xù)繞行，如 果一個接收到標(biāo)志的進程并不想進入其臨界區(qū)，只需 放行此標(biāo)志。 2、此法特點： （1

54、）可實現(xiàn)互斥。因系統(tǒng)中只有一個標(biāo)志，則最多 只有一個進程在其臨界區(qū)內(nèi)。 （2）無“餓死”情況（在單向環(huán)形系統(tǒng)中） （3）兩種失效情況： 一是如果標(biāo)志丟失，則應(yīng)能發(fā)現(xiàn)并選擇一個進 程產(chǎn)生新標(biāo)志。 二是如果一個進程夭折了，則邏輯環(huán)斷裂，此 時系統(tǒng)應(yīng)能重構(gòu)一

55、個新的邏輯環(huán)。,死鎖處理 傳統(tǒng)系統(tǒng)中所用的死鎖預(yù)防、避免，以及檢測等算法的思想一般也適合于網(wǎng)絡(luò)和分存式系統(tǒng)，只需做某些適當(dāng)?shù)男薷?。例如：只要在系統(tǒng)事件之間定義一個全序，資源分配預(yù)防死鎖技術(shù)就可用于網(wǎng)絡(luò)和分布式環(huán)境中，也即，系統(tǒng)內(nèi)所有資源被賦予一個唯一的編號，一個進程可以要求一個編號為I的資源，當(dāng)且僅當(dāng)它未占有編號比I更小的資源。只要確定系統(tǒng)中某個進程為銀行家，由它保持執(zhí)行銀行家算法所必需的信息，并負(fù)責(zé)系統(tǒng)中資源

56、的分配，則銀行家算法也同樣適合于網(wǎng)絡(luò)和分布式系統(tǒng),一、死鎖預(yù)防： (一)死鎖產(chǎn)生的四個必要條件：互斥條件，請求和保持條件、不剝奪條件、環(huán)路等待條件 (二)網(wǎng)絡(luò)與分布式系統(tǒng)中預(yù)防死鎖的方法:通過剝奪資源以破壞循環(huán)等待條件。 方法：賦給每個進程一個唯一的優(yōu)先數(shù)，這個優(yōu)先數(shù)被用于決定一個進程Pi 是否等待另外一個進程 Pi。例如：如果Pi具有更高的優(yōu)先數(shù)，可以令Pi等待Pj，否則Pi回退，即死

57、掉。 缺陷：可能出現(xiàn)饑餓現(xiàn)象，因為有些低優(yōu)先級的進程可能總是被回退，為此有人提出用時間郵戳的設(shè)想，系統(tǒng)中的每個進程，在其產(chǎn)生時被賦予一個唯一的時間郵戳，下面介紹兩個方案：,方案一：死等：資源申請者回退：此方案基于非剝奪技術(shù)，當(dāng)一個進程Pi 要求另外一個進程Pj保持的資源時，Pi被允許等待, 僅當(dāng)它具有比

58、Pj更小的郵戳?xí)r間，即Pi是比Pj更老 的，否則Pi回退。方案二：剝奪式等待：資源占有者回退：此法基于剝奪技術(shù)，是死等方案的改進，當(dāng)進 程Pi要求進程Pj當(dāng)前占有的資源時，則Pi獲準(zhǔn)等待的 條件是它具有比Pj更大的郵戳?xí)r間，即Pi比Pj更年輕, 否則Pj回退。,二、死鎖檢測： 死鎖預(yù)防技術(shù)可能剝奪一些資源或回退一些 進

59、 程，即使死鎖不會出現(xiàn)。為了防止不必要的剝奪和 回退，可以允許死鎖發(fā)生，并在發(fā)生后將死鎖檢測 出來，為此需要構(gòu)造資源分配狀態(tài)圖，若此圖出現(xiàn) 環(huán)路，則死鎖發(fā)生。 (一)資源等待圖的保存方法：要求每個站點保持一個局 部等待圖，圖中站點對應(yīng)占有和申請局部于該站點 資源的那些進程，這些進程可能是局部于本站

60、點的, 也可能是屬于其它站點的。 (二)判斷： 如果注意一個局部等待圖中出現(xiàn)了環(huán)路，則死 鎖已經(jīng)發(fā)生，但若每個站點的局部等待圖均無環(huán)路, 并不意味著沒有死鎖，為了確定沒有思鎖，必須證 明所有局部等待圖之“并”沒有環(huán)路，兩個或多個局 部圖之“并”已經(jīng)出現(xiàn)了一個環(huán)路。,The problem here is h

61、ow to get agreement with an unreliable mechanism. In order to do an election, as we just discussed, it would be necessary to work around the following problems. UNRELIABLE COMMUNICATIONS Can have faulty li

62、nks - can use a timeout to detect this. FAULTY PROCESSES Can have faulty processes generating bad messages.Cannot guarantee agreement.,DISTRIBUTED COORDINATION,Reaching Agreement Between Processes,分布式文件系

63、統(tǒng),Caching vs. Remote Access局部性原理：Many remote accesses can be handled by a local cache. There's a great deal of locality of reference in file accesses. Servers can be accessed only occasionally rather than for each

64、access.網(wǎng)絡(luò)效率：Caching causes data to be moved in a few big chunks rather than in many smaller pieces; this leads to considerable efficiency for the network.一致性：Cache consistency is the major problem with caching. When

65、there are infrequent writes, caching is a win. In environments with many writes, the work required to maintain consistency overwhelms caching advantages.復(fù)雜性：Caching requires a whole separate mechanism to support acquir

66、ing and storage of large amounts of data. Remote service merely does what's required for each call. As such, caching introduces an extra layer and mechanism and is more complicated than remote service.,How to perform

67、 Authorization for Distributed Systems?,Issues: Are all user names in world unique?No! They only have small number of characterskubi@mit.edu ? kubitron@lcs.mit.edu ? kubitron@cs.berkeley.eduHowever, someone thought th

68、eir friend was kubi@mit.edu and I got very private email intended for someone else…Need something better, more unique to identify personSuppose want to connect with any server at any time?Need an account on every mach