分布式考试复习要点

分布式复习要点第一章绪论： SETIHOME (通过全球网络搜寻地外文明并对数据进行分析的科学研究计划) SETI 中文含义：The Search of Extraterrestrial IntelligeneeBOINC 即伯克利开放式网络计算平台，是目前主流的分布式计算平台之一。网络计算必须具备：通用的计算平台、通用的访问方式、网络服务器。网络计算按照数据处理方式和规模的不同分为高性能计算、网格计算、分布式计 算和云计算分布式系统的关键技术：1，分布式存储技术2，分布式文件系统3，分布式并行处理技术4，分布式数据库管理技术5，分布式系统负载调度技术第二章：执行优先图用途:支持对并发的设计1. 消息传递由发送和接收两个基本操作构成语句并发(并行)的条件：Bernstein条件：当两个语句并发执行时，可能产生与顺序执行不同的结果。让我们先定义两个符号： R(S): Si的读集，即在Si中被引用的所有变量的集合。 W(S): Si的写集，即在Si中被修改的所有变量的集合。Bernstein提出了以下三个条件，对于两个并发执行的语句S】和S2，必须满 足这三个条件才能使它们并发执行的结果与它们以任意次序顺序执行的结果相 同。R(S1)AW(S2)=0R(S2)AW(S1)=0W(S1)AW(S2)=0使用SS2表示语句S1和S2满足这三个条件，可以并行或并发执行。例23假设S1为a:=x+y, S2为b:=x+z，用bernstein条件证明这两个语 句可以并发执行。解：按照 bernstein 判定条件，因为 R(S/=x，y，R(S2)=x，z， W(S1)=a， W(S2)=b它们满足以下三个条件，即： R(S1)AW(S2)=0 R(s2)nw(S)=e w(S1)nw(S2)=0所以这两个语句可以并发执行第三章： 并行算法可以从不同的角度分类为：-数值计算并行算法和非数值计算并行算法-同步并行算法和异步并行算法-共享存储并行算法和分布存储并行算法常见的并行计算模型： PRAM 模型 :由 Fortune 和 Wylliel978 年提出，又称 SIMD-SM 模型。有一个 集中的共享存储器和一个指令控制器，通过SM的R/W交换数据。 异步模型(APRAM):又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局 部存储器、局部时钟、局部程序。BSP模型：块同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块 内异步并行，块间显式同步。logP模型：由Culler(1993)年提出，是一种分布存储的、点到点通讯的多处理 机模型。PRAM( Parallel Random Access Machine)模型，即并行随机存取模型，是一种抽象 的并行计算模型。第四章：Petri网是1962年由德国科学家卡尔A佩特里首先提出。 Petri 网可以刻画系统的结构，也可以描述系统的动态行为。 Petri 网是一种基于图的形式化模型。 Petri 网以研究模型的组织结构和动态行为为目标，主要关注系统中可能发生的 状态变化以及变化之间的关系。petri 网的性质： Petri 网由于其结构、参数和初始状态标识的不同,而使其状态转换过程表现出 不同的特性在用Petri网建模后,就可以对系统进行特性分析，以检查实际系统的 特性.借助Petri网可以研究两类特性:与初始标识有关的称为行为特性，而与初始标 识无关的称为结构特性。其中行为特性包括可达性，活性等;结构特性包括安全性，有界性，可逆性和守可达性： 是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态.如果存在一个从M0到Mn的触发序列，我们称标识Mn是从M0可达的，触发序 列转化为o= M0tlMlt2M2.tnMn或简化为o=tlt2.tn.可用M0o Mn表示三 者之间的关系，即从标识M0经过触发序列o到达标识Mn.Petri网称为活性的v = 如果在任何状态Me R(MO)下,通过适当的触发序列后,每个迁 移最终都可以被触第六章： 临界区：每个进程中访问临界资源的一段程序代码。 互斥的主要目标是保证在一个时刻只能有一个进程访问临界区。互斥算法的分类1. 基于令牌的算法：通过令牌拥有权来控制对共享资源的访问。2. 非基于令牌的算法：通过进程之间的消息交换来协商对共享资源的访问。 互斥算法应满足的条件： 无死锁：当资源可用时进程不应该永远等待 无饥饿现象：每个对资源的访问请求最终都应能得到满足 公平性：进程对资源访问权的获得应是相对公平的。衡量互斥算法性能的参数：每个请求的消息数同步延迟：一个进程离开临界区到下一个进程进入该临界区的时间间隔，对共 享资源的有效访问间隔。反应时间：进程发出访问请求到执行完访问操作的时间间隔，主要依赖于系统 的负载和调度的合理性。第七章：死锁问题： 系统中有进程处于相互的无限等待状态(被阻塞) 资源死锁和通信死锁簣待图：将系统中进程对资源的占用与需求共享情况用有向图表示-进程集合PO, P1 ,Pn为节点集，当且仅当进程Pi等待一个被进程Pj占用的资 源时，边(Pi, Pj)存在于图中。资源(resources)分类根据资源性质：可剥夺资源（抢占）和不可剥夺资源可抢占资源：指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从 占有者进程处抢来。不可抢占资源：指只有占用者进程不再需要使用该资源而主动释放资源外，其它进 程不得在占有者进程使用资源过程中强行抢占。 可抢占资源如：CPU、主存、硬盘，该类资源可为多个进程共享（可抢占） 不可抢占资源如：打印机、读卡机，磁带驱动器，该类资源可为某个进程独享（不可抢占）等待-死亡方案例题 例题：根据表1 描述的5 个进程的优先级及请求时间等信息，用等待-死亡方 案画出时间轴上 5 个进程执行的时间和先后顺序。并说明进程之间的等待关系等待-死亡方案和伤害-等待预防方案的区别： 两种方案的区别：在等待-死亡”方案中，年长的进程必须等待年轻的进程释放它的资源，因 此进程越“年长”，它就越容易引起等待。与此相反，在“因伤等待”方案中， 年长的进程决不会等待年轻的进程。在等待-死亡”方案中，进程pi可能被撤离若干次。在伤害-等待”方案 中，进程pi撤离的次数较少。分布式死锁检测： 边跟踪算法：各节点将自己的资源需求作为探测器沿依赖关系发送出去，如果 某节点收到自己发出的探测器，则表明存在资源依赖回路。 扩散计算算法：当需要检测时，进程向它所依赖的进程发起询问，并将因此而 引发的各个询问关联成等待图，或者通过接收应答将图消解，或者从中发现死 锁。 全局状态检测：通过建立一致的全局状态图来检测是否有死锁发生。第八章： 一般型路由算法适合于所有类型的网络 但是对于某种特定网络不是很有效 特殊型路由算法 只对特定的网络类型有效，如超立方、网格等 这些算法由于利用了特定网络的拓扑属性，所以效率往往较高 最短路由算法和非最短路由算法： 最短路径算法 对给定的源-目标对给出一个代价最小的路径 路径的代价 所有跳步（连接）代价的线性和。缺点：可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下，随机路由可能是有效的。 一般类型网络的最短路径路由算法： Dijkstra 集中式算法 Ford 分布式算法 ARPAnet 路由算法第十章： 可依赖系统(Dependable, Trustworthy) 可用性(availability) 系统可为用户服务的能力 可靠性( Reliability) 系统可连续工作的能力 安全性( Safety) 系统故障时产生危害的程度 可维护性( Maintainability) 系统故障修复的难度 平均无故障时间(MTTF)Mean Time To Failure 平均能够正常运行多长时间，才发生一次故障。用来度量可靠性 p 为每秒失效概率平均无故障时间(MTTF)=刍8kp(l-pZ=l/p例：p=10-6, MTTF=1C6秒=11.6天 平均维修时间( MTTR) Mean Time To Repair 系统发生故障后维修和重新恢复正常运行平均花费的时间 用来度量可维护性 可用性= (MTTF / (MTTF + MTTR)故障的类型： 按照故障出现的概率 短暂型(tra nsie nt):出现一次，再也不出现间歇型(intermittent):消失后，再重复出现 永久型(permanent):直存在按照故障产生的原因节点故障 硬件故障 软件故障 时序故障容错(fault tolerance) 即使发生故障，系统仍能提供服务 系统的容错能力用可允许的故障节点数量来衡量。 如果系统能够在 k 个节点出现故障的情况下仍然能够完成任务，则称该 系统为k-容错系统。冗余类型： 信息冗余：如，海明码。 时间冗余：如，重发，重做 物理冗余： 软件 : 如复制进程 硬件：如复制电路 信息冗余和物理冗余都属于空间冗余第十一章;调度算法的目标和有效性评价：有许多参数用于确定或测量一个调度算法的有效性： 通信代价：使用这个参数的调度算法可能要考虑到向一个给定的节点传送或者 从一个给定节点接收一个报文花费的时间，更为重要的是必须考虑到为一个进 程分配一个执行地点而引起的通信代价。 执行代价：这个参数反映的是将一个进程分配到一个指定的执行节点，在这个 节点的执行环境下，执行这个程序所需的额外开销。资源利用率：常用来表明基于分布式系统当前各个节点的负载情况，给一个进 程分配的执行节点是否是合适的。资源利用率参数常用负载状态来表示，常用 的负载参数有资源的队列长度、内存的使用等等。设计调度策略时要考虑的三个主要因素：静态调度算法的目标是调度一个任务集合， 使它们在各个目标节点上有最短的执行时间。总体上来说，设计调度策略时要考虑 的三个主要因素是处理机的互连、任务的划分和任务的分配。通常用图模型表示任 务和处理机的结构。我们可以用任务优先图和任务交互作用图对任务集合建模。任务优先图是一有向无环图(DAG)，基于任务优先图的任务调度 甘特图(ga ntt chart )用来描述进程对处理器的分配情况。 甘特图以处理器为纵坐标，以时间为横坐标。第十二章：动态调度的组成要素动态调度算法有六个策略：启动策略、转移策略、选择策略、收益性策略、定位策略 和信息策略。1) 启动策略的责任是决定谁应该激活负载平衡活动。2) 转移策略决定一个节点是否在合适的状态参与负载转移。3) 选择策略选择最适合转移最能起平衡作用的任务，并发送给合适的目标 处理器。4) 收益性策略量化系统中负载不平衡程度，并且作为系统负载平衡潜在受 益的估计，评估系统负载平衡是否是有收益的。5) 定位策略是寻找合适的节点共享负载。6) 信息策略决定收集系统中其他节点状态信息的时机、收集的方法和收集的信息。第十三章：分布式事务的特性：ACID 原子性(atomicity) 旨事务执行时的不可分割性。这个特性确保了 每个事务要么全部发生，要么全部不发生。 一致性(consistency) 事务执行的结果必须使数据库从一个一致性状态转到另一个一致性状态。 隔离性(isolaty) 一个事务的执行不被其他事务干扰。 持久性(durability) 一个事务一旦提交，它对数据库中数据的改变应该是永久性的。无论系统发生任何故障，都不会丢失该事务的执行结果