分布式系統(tǒng)分類(lèi)

1、分布式系統(tǒng)分類(lèi)-分布式計(jì)算系統(tǒng)：集群計(jì)算系統(tǒng)&網(wǎng)格計(jì)算系統(tǒng)（硬件，操作系統(tǒng)，網(wǎng)絡(luò)都不盡相同）-分布式信息系統(tǒng)：事務(wù)處理系統(tǒng)&企業(yè)應(yīng)用集成-分布式普適系統(tǒng)Grid computingProvide users with seamless access to:Storage capacityProcessingNetwork bandwidthHeterogeneous and geographically distributed systems系統(tǒng)體系結(jié)構(gòu)： 集中式 & 非集中式 & 混合模式遠(yuǎn)程過(guò)程調(diào)用（RPC）： 機(jī)器A上的進(jìn)程調(diào)用機(jī)器B上的進(jìn)程時(shí)，A上的調(diào)用進(jìn)程被掛起，B上被調(diào)用的開(kāi)始執(zhí)行

2、調(diào)用方可以通過(guò)使用參數(shù)將信息傳送給被調(diào)用方，然后可以通過(guò)傳回的結(jié)果得到信息。RPC操作分為客戶(hù)部分和服務(wù)器部分。命名系統(tǒng) NamingProblemGiven an essentially unstructured name (e.g., an identier), how canwe locate its associated access point?Simple solutions (broadcasting)Home-based approachesDistributed Hash Tables (structured P2P)Hierarchical location service

3、Flynns Taxonomy 費(fèi)林分類(lèi)SISD HYPERLINK /w/index.php?title=%E5%96%AE%E6%8C%87%E4%BB%A4%E6%B5%81%E5%96%AE%E6%95%B8%E6%93%9A%E6%B5%81&action=edit&redlink=1 o 單指令流單數(shù)據(jù)流（尚未撰寫(xiě)） 單一指令流單一資料流計(jì)算機(jī)SIMD HYPERLINK /wiki/%E5%8D%95%E6%8C%87%E4%BB%A4%E6%B5%81%E5%A4%9A%E6%95%B0%E6%8D%AE%E6%B5%81 o 單指令流多數(shù)據(jù)流 單一指令流多資料流計(jì)算機(jī)MISD

4、 HYPERLINK /w/index.php?title=%E5%A4%9A%E6%8C%87%E4%BB%A4%E6%B5%81%E5%96%AE%E6%95%B8%E6%93%9A%E6%B5%81&action=edit&redlink=1 o 多指令流單數(shù)據(jù)流（尚未撰寫(xiě)） 多指令流單一資料流計(jì)算機(jī)MIMD HYPERLINK /wiki/%E5%A4%9A%E6%8C%87%E4%BB%A4%E6%B5%81%E5%A4%9A%E6%95%B0%E6%8D%AE%E6%B5%81 o 多指令流多數(shù)據(jù)流 多指令流多資料流計(jì)算機(jī)Subclassifying MIMDmemoryshare

5、d memory systems: multiprocessorsno shared memory: networks of computers, multicomputersinterconnect 互聯(lián)busswitchdelay/bandwidthtightly coupled systems loosely coupled systemsTransparency 透明性 (訪(fǎng)問(wèn)access、位置location、遷移migration、重定位relocation、復(fù)制replication、并發(fā)concurrency、故障failure)Location transparency:us

6、ers dont care where resources areMigration transparency:resources move at willReplication transparency:users cannot tell whether there are copies of resourcesConcurrency transparency:users share resources transparentlyParallelism transparency:operations take place in parallel without users knowledge

7、Design issuesTransparencyReliabilityPerformanceScalability目標(biāo) (可訪(fǎng)問(wèn)、透明性、開(kāi)放性、可擴(kuò)展性、可靠性)Centralized model 集中式模型No networkingTraditional time-sharing systemDirect connection of user terminals to systemOne or several CPUsNot easily scalableLimiting factor: number of CPUs in systemContention for same resour

8、cesPeer to peer modelEach machine on network has (mostly) equivalent capabilitiesNo machines are dedicated to serving othersE.g., collection of PCs:Access other peoples filesSend/receive email (without server)Gnutella-style content sharingSETIhome computationProcessor pool modelWhat about idle works

9、tations(computing resources)?Let them sit idleRun jobs on themAlternativelyCollection of CPUs that can be assigned processes on demandUsers wont need heavy duty workstationsGUI on local machineComputation model of Plan 9RPC的步驟：客戶(hù)過(guò)程以正常的方式調(diào)用客戶(hù)存根客戶(hù)存根生成一個(gè)消息，然后調(diào)用本地的操作系統(tǒng)客戶(hù)端操作系統(tǒng)將消息發(fā)送給遠(yuǎn)程操作系統(tǒng)遠(yuǎn)程操作系統(tǒng)將消息交給服務(wù)器存根

10、服務(wù)器存根將參數(shù)提取出來(lái)，然后調(diào)用服務(wù)器服務(wù)器執(zhí)行要求的操作，操作完成后將結(jié)果返回給服務(wù)器存根服務(wù)器存根講結(jié)果打包成一個(gè)消息，然后調(diào)用本地操作系統(tǒng)服務(wù)器操作系統(tǒng)將含有結(jié)果的消息發(fā)送回客戶(hù)端操作系統(tǒng)客戶(hù)端操作系統(tǒng)將消息交給客戶(hù)存根客戶(hù)存根將結(jié)果從消息中提取出來(lái)，返回給調(diào)用它的客戶(hù)過(guò)程。并發(fā)的方法Two Phase locking兩階段鎖協(xié)議Strict two phase locking嚴(yán)格的兩階段鎖Read/write lock讀寫(xiě)鎖Two version locking兩版本鎖時(shí)鐘物理時(shí)鐘和邏輯時(shí)鐘物理時(shí)鐘：-Real-time Clock: CMOS clock (counter) cir

11、cuit driven by a quartz oscillator-OS generally programs a timer circuit to generate an interrupt periodically問(wèn)題：Getting two systems to agree on timeTwo clocks hardly ever agreeQuartz oscillators oscillate at slightly different frequenciesClocks tick at different ratesCreate ever-widening gap in per

12、ceived timeClock DriftDifference between two clocks at one point in timeClock Skew 時(shí)間偏移Simplest synchronization techniqueIssue RPC to obtain timeSet timeCristians algorithmCompensate for delaysNote times:request sent: T0reply received: T1Assume network delays are symmetricBerkeley algorithm時(shí)間守護(hù)程序主動(dòng)詢(xún)

13、問(wèn)其他機(jī)器的時(shí)鐘值，其他機(jī)器作出應(yīng)答，時(shí)間守護(hù)程序通知每臺(tái)機(jī)器如何調(diào)整時(shí)鐘。網(wǎng)絡(luò)時(shí)間協(xié)議NTP邏輯時(shí)鐘：Lamports algorithmEach message carries a timestamp of the senders clockWhen a message arrives:if receivers clock message timestampset system clock to (message timestamp + 1)else do nothingClock must be advanced between any two events in the same pr

14、ocess向量時(shí)鐘：Rules:Vector initialized to 0 at each processVi j = 0 for i, j =1, , NProcess increments its element of the vector in local vector before timestamping event: Vi i = Vi i +1 Message is sent from process Pi with Vi attached to itWhen Pj receives message, compares vectors element by element a

15、nd sets local vector to higher of two valuesVj i = max(Vi i, Vj i) for i=1, , N Modes of communicationunicast11Point-to-pointanycast1nearest 1 of several identical nodesIntroduced with IPv6; used with BGPnetcast1 many, 1 at a timemulticast1manygroup communicationbroadcast1allFor multicast atomic Rel

16、iable unreliableorderingDistributed shared memoryGoal:allow networked computers to share a region of virtual memoryHow do you make a distributed memory system appear local?Physical memory on each node used to hold pages of shared virtual address space. Processes address it like local memory. Motivat

17、ionSMP systems SMP: HYPERLINK /wiki/Symmetric_multiprocessing Symmetric HYPERLINK /wiki/Symmetric_multiprocessing multiprocessing 當(dāng)前的多核計(jì)算機(jī)是一種典型的smp架構(gòu)Run parts of a program in parallelShare single address spaceShare data in that spaceUse threads for parallelismUse synchronization primitives to preven

18、t race conditionsCan we achieve this with multicomputers?All communication and synchronization must be done with messagesIssuesAccess (MMU)CacheReplicationconsistencyTerms: types of ciphersrestricted ciphersymmetric algorithmpublic key algorithmTerms: types of ciphersSubstitution CiphersTransposition CiphersCombined ciphersRotor machinesOne-time padspublic key algorithmDiffie-Hellman exponential key exchangeRSA algorithm數(shù)字簽名Arbitrated protocolIntegrity of the documentAu