分布式系统分类

1、分布式系统分类-分布式计算系统：集群计算系统&网格计算系统（硬件，操作系统，网络都不尽相同）-分布式信息系统：事务处理系统&企业应用集成-分布式普适系统Grid computingProvide users with seamless access to:Storage capacityProcessingNetwork bandwidthHeterogeneous and geographically distributed systems系统体系结构： 集中式 & 非集中式 & 混合模式远程过程调用（RPC）： 机器A上的进程调用机器B上的进程时，A上的调用进程被挂起，B上被调用的开始执行

2、调用方可以通过使用参数将信息传送给被调用方，然后可以通过传回的结果得到信息。RPC操作分为客户部分和服务器部分。命名系统 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 费林分类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 单指令流单数据流（尚未撰写） 单一指令流单一资料流计算机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 单指令流多数据流 单一指令流多资料流计算机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 多指令流单数据流（尚未撰写） 多指令流单一资料流计算机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 多指令流多数据流 多指令流多资料流计算机Subclassifying MIMDmemoryshare

5、d memory systems: multiprocessorsno shared memory: networks of computers, multicomputersinterconnect 互联busswitchdelay/bandwidthtightly coupled systems loosely coupled systemsTransparency 透明性 (访问access、位置location、迁移migration、重定位relocation、复制replication、并发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目标 (可访问、透明性、开放性、可扩展性、可靠性)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的步骤：客户过程以正常的方式调用客户存根客户存根生成一个消息，然后调用本地的操作系统客户端操作系统将消息发送给远程操作系统远程操作系统将消息交给服务器存根

10、服务器存根将参数提取出来，然后调用服务器服务器执行要求的操作，操作完成后将结果返回给服务器存根服务器存根讲结果打包成一个消息，然后调用本地操作系统服务器操作系统将含有结果的消息发送回客户端操作系统客户端操作系统将消息交给客户存根客户存根将结果从消息中提取出来，返回给调用它的客户过程。并发的方法Two Phase locking两阶段锁协议Strict two phase locking严格的两阶段锁Read/write lock读写锁Two version locking两版本锁时钟物理时钟和逻辑时钟物理时钟：-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问题：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 时间偏移Simplest synchronization techniqueIssue RPC to obtain timeSet timeCristians algorithmCompensate for delaysNote times:request sent: T0reply received: T1Assume network delays are symmetricBerkeley algorithm时间守护程序主动询

13、问其他机器的时钟值，其他机器作出应答，时间守护程序通知每台机器如何调整时钟。网络时间协议NTP逻辑时钟：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向量时钟：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 当前的多核计算机是一种典型的smp架构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数字签名Arbitrated protocolIntegrity of the documentAu