OS之分布式系统中的同步问题.ppt

分布式系统中同步问题 一 时钟同步分布式系统特点 相关的信息分布在多台机器上没有共享内存进程只根据本地可用的信息做出决策系统中不存在公共时钟或其它精确的全局时间源在集中式系统中 时间是很明确的 时钟同步例子 UNIX的Make 检查文件最后修改时间创建input o后 源input C修改了 要重新编译input C设ouput o的修改时间是2000 创建output o后即修改了源output c但编辑output c的机器时钟慢 修改后output c时间被1999make不会重新编译output c 程序的运行会出现问题 二 逻辑时钟 1 只关心时钟内部一致性 不关心时钟是否与实际时间一致1978年Lamport指出 系统中的时钟并不需要绝对的同步重要的不是进程有完全一致的时间 而是事件发生的先后次序要一致 二 逻辑时钟 2 发生之前 happens before 关系定义表达式ab读作 a发生在b前 即所有进程都认为事件a先发生 然后才发生事件b事件a 有一个时间值C a 如果a和b是同一进程中的事件 而且a发生在b前那么ab为true C a C b 二 逻辑时钟 3 传递性Happens before关系具有传递性如果ab和bc都成立 ac也成立 并发事件 如果事件x和y发生在不同的进程中 且这两进程间不交换信息那么xy和yx都不成立 这两个事件就称为并发事件并发意味着两个事件发生时 无法确定哪个事件先发生 或者说不需要考虑此事 时钟时间C必须向前 不断增加 不能后退 减小 对时间的更新 只能是在时钟上加一个正数 不能减正数 Lamport算法 1 例子说明 1 三个进程运行在不同的有自己时钟的机器上 每个时钟按自己的速度运行可以看到 进程0中时钟有6次嘀嗒时 进程1已经有了8次 而进程2已经有了10次 Lamport算法 2 设 计时器每秒生成60次中断 每次中断称为一个时钟嘀嗒从进程2发送该进程1的消息C 其发送时刻为60 到达时刻为56同样 从进程1到进程0的消息D 其发送时刻为64 到达时刻为54这显然是不可能的 也是必须避免出现的情况 例子说明 2 Lamport算法 3 消息c的发送时间为60 它的到达时间一定在时刻61或61之后让每条消息都携带发送者时钟的发送时刻当消息到达接收时 如果接收者的时钟指示值先于发送消息的时间接受者的时钟值就应快于消息发送时刻加1之后时间值 例子说明 3 Lamport算法 4 Lamport算法 5 两个事件之间 时钟至少应间隔一个嘀嗒如果一个进程依次快速发送或接收两条消息 就必须调整时钟使两个事件之间 至少 间隔一个时钟嘀嗒 附加条件 没有两个事件是精确地在同一时刻发生的 1 在同一进程中 如果a在b前面发生 那么C a C b 2 如果a与b分别代表消息的发送和接收 那么C a C b 3 对于所有的事件a与b而言 C a C b Lamport算法 6 算法给出系统中所有事件的整体定序方法该算法在学术界中得到广泛认同 Lamport算法 7 三 时钟 1 在某些系统中 实际的时钟时间非常重要 需要物理时钟如何使物理时钟与世界的时钟同步 物理时间之间如何保持同步 原子钟可以准确度量时间世界时 UniversalCoordinatedTime 简称UTCUTC是现代计时的基础NationalInstituteofStandardTimeNIXT 国家标准时间组织短波电台 WWV每个UTC秒的起始时刻 WWV就发送一个短脉冲WWV本身的误差大约为 1毫秒 物理时钟 2 四 时钟同步算法 如果某台机器有WWV接收器时钟同步的目的是使其它机器与这台机器同步 时钟同步算法的基本模型 1 设每台机器都有个计时器 该计时器每秒中断H次计时器溢出时 中断处理程序就将软件时钟加1软件时钟是从过去某一已知时间开始所经历的tick数这个时钟的值称为C 当UTC时间为t时 机器p的时钟值为Cp t 理想情况下dC dt应为1 理论上 当H 60时 计时器应每小时生成216 000次ticks实际上 计时器芯片的相对误差大约为10 5 即每小时的tick数的范围为215 998到216 002准确地说 如果存在一个常数p1 dC dt 1 成立 就可以认为计时器是正常工作的 时钟同步算法的基本模型 2 如果两个时钟偏离UTC的方向相反那么在同步之后的 t时刻时它们的时差为2 t要保证两个时钟间时间差不超过 必须至少每隔 2 秒重新同步 Cristian算法 1 某台机器拥有WWV接收器的系统的算法时钟同步的目的就是使其它机器与有WWV接收器的机器保持同步有WWV接收器的机器称为时间服务器 timeserver Cristian算法 2 系统中每台机器至少每隔 2 秒就向时间服务器发送一条消息查询当前时间服务器尽快将携带当前时间CUTC的消息返回给请求者一种近似方法发送者得到时间服务器的响应后 直接将其时钟值设置为CUTC Cristian算法 3 笫一个问题 时间决不能倒退如果这个请求发送者的时钟比实际时间快这时仅将CUTC设置为时钟的当前值会引起严重问题 Cristian算法 4 对时钟的调整必须逐步进行一种方法 假设计时器每秒中断100次正常情况下 每次中断将时钟时间增加10毫秒如果要使时钟慢下来 中断程序就每次只将时间增加9直到将时间矫正过来为止 Cristian算法 5 同样 每次中断时将时间加11毫秒 就会逐渐将时钟调快 而不应直接将时钟值设快 Cristian算法 6 第二个问题时间服务器将当前时间发送给查询时间的机器需要时间这个延迟时间可能会很长 而且它也在变化Cristian的处理方法就是计算出准确的延迟时间为了提高估计值的准确性 建议要进行一系列的测量 BerkeleyUNIX算法 1 时间服务器是活动的 它定期向其他机器查询这些机器的时间根据得到的响应 时间服务器计算出一个平均值并通知其它机器调整其时钟 BerkeleyUNIX算法 2 重复这个过程 直到达到一定的缩减量为止这种方法适用于那些没有WWV接收器的系统在这样的系统中 操作员必须阶段性地手工设置时间的时间 五 互斥问题 在分布式系统中 临界区和互斥如何实现 1 集中式算法 在分布式系统中 实现互斥的最简单算法是模拟单处理机的情形 集中式算法基本思路 一个进程作为协调者其他进程要进入临界区须先发出请求消息说明要进入哪一个临界区如果在那个临界区中 当前没有其他进程那么协调者就发出批准当批准到达请求的机器后发出请求的进程就进入临界区 集中式算法评价 显然本算法中由协调者保证互斥算法是公平的因为按收到请求的先后顺序 考虑是否发出回答不会出现有某个进程永远等待的现象算法的缺点 协调者是一个单点失效的机制如果协调者垮台了 是 不允许 呢 还是它自身垮台了呢 2 分布式算法 1 Richart与Agrawala R A 算法要求在系统中 对所有事件安排一个次序进程在进入临界区之前 先构造一条消息消息中包含有要进入的临界区的名称 进程编号以及当前时间把该消息发给所有其他的进程 分布式算法 2 为简单起见 假定消息的发送是可靠的 每一进程都认可收到了此消息各个进程依据情况 发回消息如果接受方不在临界区中并且也不想进入 那么发出OK如果接受方已在临界区内 那么不应答 并把该消息放到队列中如果接受方也想进临界区 但还没有进入比较收到的消息和自己发出消息的时间戳 分布式算法 3 如果收到消息中的时间戳早 则发出OK如果自己的消息较早 那么不发消息 并把请求送入队列请求的进程要等到所有其他进程回送允许消息为止当所有的允许消息都到达后 该进程就可以进入申请的临界区退出临界区后 该进程向在其队列中的所有其他进程发出OK 分布式算法 4 算法关键当发生有冲突的申请时所有进程均同意有小时间戳一方取胜 分布式算法评价 算法中不存在单点失效却出来了多点失效一个进程垮台后 它不响应外来的请求还阻塞了后续试图进入临界区的进程该算法仅使出错概率增大了 而且还要占用大量网络资源 分布式算法评价 2 补救方法 在发送方设置有超时的反应机制该机制不断询问直到有一个回答收到或者在经过一段设定的时间段后 得出结论 接收方有故障这个算法 速度慢 复杂 开销也大但至少表明了 分布式算法是可行的 3 令牌环网算法 1 一个分布式系统 内部的进程构成了一个逻辑上的环形网所有的进程都知道它的后续者是谁设令牌从进程k传到进程k 1沿环传递当进程得到令牌后 首先看是否需要进入临界区如果需要 进程进入临界区 进行所需的操作在撤出临界区后 该进程让令牌沿环传递 令牌环网算法 2 本算法规定 进程不允许用同一张令牌进入第二个临界区如果一个进程得到了令牌 但不打算进入临界区那么它就继续传递令牌如果没有进程想进入临界区 令牌则沿着环路高速循环 令牌环网算法评价 1 算法的正确性是明显的因为任何时刻 只有一个进程持有令牌在临界区中只可能有一个进程由于巳经规定好令牌传递次序 所以不可能发生死锁最坏情况是 排在最后的进程要等到其他进程都进入临界区 完成操作 并离开之后 才轮到它 令牌环网算法评价 2 算法的问题如果令牌因为某种原因丢失了 就必须重新生成一个但是如何探测令牌是否丢失 却是一件难事令牌在一小时之内没有传递 不意味着丢失了 可能某个进程还在使用它 令牌环网算法评价 3 另一个问题 如果某个进程垮台了 算法也会碰到麻烦补救方法 进程收到令牌后 给予认可在进程试图把令牌递交给邻居后如果在规定时限内没有认可回答 就判定该邻居是死进程于是令牌越过死进程 传到下一个进程中 六 典型选举算法 威力 Bully 算法 分布式系统需要有一个进程担当协调者完成一些特别的工作任务如何选择进程来担当协调者 威力 Bully 算法 1 假定每台机器只有一个进程每一进程都有一个单独的编号还假定每一进程都了解其他进程的编号选举算法的目的试图挑出一个具有最高进程编号的进程 委任它为协调者确认如下规则 当选举开始以后 它会得出结论 威力 Bully 算法 2 所有的进程都同意某个进程将担任新的协调者当某一个进程P 发现协调者不再响应请求后它积极发起一场竞选活动P 掌握着一场选举 威力 Bully 算法 3 规则 首先 P发出选举消息给所有比它更高级别编号的进程其次 如果没有响应者 那么P就赢得这场选举 成为新的协调者最后 如果更高编号中有一个进程响应那么这个更高编号的进程就赢得选举P也就完成了使命 威力 Bully 算法 4 一个进程可能从小编号的进程中收到选举消息这时 这个接收进程回送OK消息给发送方从而表明它将接管选举工作接收方大员然后掌管这场选举活动 向其它进程发出消息宣布取得了选举胜利 并开始其协调者的工作 威力 Bully 算法 5 如果有一个最高级编号进程在运行它肯定会赢得选举并接管协调者的工作最有势力的大亨总是取得胜利小伙计可能是白忙一场这就是称之为 威力 Bully 算法 的原因 七 原子事务 原子事务来自于商业领域双方在方签字前 可以自由退出 没有任何责任但是签字之后 就无法再反悔了 交易就必须进行下去要么全部完成 要么全部取消 对主控磁带修改的可容错系统 早期计算机事务处理 修改在线数据库的银行应用程序 1 客户利用一台带有调制解调器的PC机呼叫银行服务打算从一个帐户中提取钱存入另一个帐户中操作分两步完成 提款 数量 帐户1 存款 数量 帐户2 修改在线数据库的银行应用程序 2 如果在第一个操作完成后第二个操作开始前电话连接被中断这笔钱已被记入第一个帐户的借方但是还没有记入第二个帐户贷方中这笔钱就消失了 修改在线数据库的银行应用程序 3 两个操作组合在一个原子事务中就可以解决这个问题两个操作要么全部完成 要么一个也不执行关键是在事务失败时 能回复到事务执行前的初始状态这是原子事务必须提供的功能 1 事务模型 三类存储器第一类RAM内存在关机或机器崩溃时都要清除RAM内存的内容第二类磁盘存储器不受CPU执行失败的影响 但是磁头破坏后也会丢失数据最后一类稳定存储器除了重大事故如自然界中的洪水和地震外 其它原因都无法破坏稳定器中的内容 a a s t o f h w a a s t o f h w 1 2 a a s t o f h w a a s t o f h w 1 2 a a s t o f h w a a s t o f h w 驱动器1 驱动器2 不良校验和 稳定存储器 a b c 稳定存储器的实现 1 可以用一对普通的磁盘实现驱动器2每个扇区是驱动器1相应扇区的完全备份修改某个扇区时 首先更新1中的相应扇区并加以验证其次再更新验证2中的相应扇区 稳定存储器的实现 2 假定在修改1之后 修改2之前系统崩溃系统恢复时 可以逐个比较两个驱动器中的扇区对应的两个扇区内容不同时可以假定驱动器1的内容是正确的将正确内容从驱动器1复制到驱动器2恢复过程结束之后 两个驱动器的内容再次保持一致 稳定存储器的实现 3 潜在的问题扇区损坏 灰尘或通常的磨损 划痕出现错误时 从另一个驱动器中扇区重新生成内容稳定存储器用于高度容错性的应用将数据写入稳定存储器并读出检查其书写正确后数据被丢失的可能性就很小 事务原语 1 原语由操作系统或语言的运行系统提供原语的例子 BEGIN TRANSACTION 开始一个事务命令END TEANSACTION 结束并提供事务的命令ABORT TRANSACTION 中断事务 恢复原先数据READ 从文件 或其它对象中 读取数据WEITE 向文件 或其它对象 写入数据 事务原语 2 原语集合由对象类型决定在邮件系统中应该有发送 接收和转交邮件的原语帐务系统中READ和WRITE是很典型的例子 事务原语 3 航班订票系统 BEGIN TRANSACTIONBEGIN TRANSACTION保留WP JFK 保留WP JFK 保留JFK Nairobi 保留JFK Nairobi 保留Nairobi Malindi Nairobi Malindi ABORT TRANSACTION END TRANSACTIONEND TRANSACTION 事务原语属性 1 三个必要属性 序列化 并发的事务互不干扰原子性 对外界来说 事务的执行是不可分割永久性 一旦事务被执行 它所做的修改就永久生效 事务原语属性 2 事务第一个属性 序列化保证两个或多个事务同时运行时对它们自己及其它进程而言最后的结果与这些事务按照某种次序次序与系统有关顺序运行时的结果一致 事务原语属性 3 第二个关键属性 原子性每个事务要么全部发生 要么都不发生如果事务发生 它的发生就是一个不可分割的瞬时动作事务进展过程中 其它进程都看不到事务发生的中间状态 事务原语属性 3 第三个属性 永久性一旦事务被提交 无论这时发生什么事务都会进行下去 其结果永久生效 嵌套事务 事务可以包含子事务 子事务称为嵌套事务假定一个事务并行启动多个子事务其中一个子事务已经提支其操作结果在父事务中已经生效在继续时 父事务被终止要将整个系统恢复到顶层事务启动前的状态结果 已经提交的子事务的结果也必须被恢复事务永久性就只适用于顶层事务了 事务管理措施 任何事务或子事务启动时提供系统中所有对象私存拷贝 供其操作如果事务被终止 私有空间消失 好象从没存在过如果提交事务 该事务私有空间代替父事务私有空间在提交一子事务后启动一新的子事务第二个子事务能看到第一个子事务执行结果 2 原子事务实现 私有工作空间 1 第一种方法 在实例启动事务时为该进程提供一个实际的私有工作空间 1 2 0 0 1 2 索引 自由块 1 2 0 0 3 0 1 2 原始索引 0 1 2 3 1 2 0 0 1 2 3 3 私有工作空间 磁盘 a b c 私有工作空间 2 优化基础 读文件进程读文件 不修改该文件不需要这个文件的私有拷贝只要使用实际的文件即可 除非修改该文件 进程启动事务时 建立包含指向父进程工作空间的反向指针 空的私有工作空间 私有工作空间 2 优化基础 写操作不将整个文件复制到私有工作空间 只复制文件的索引首次修改一个文件块时 先要复制该文件块 然后将复制块的地址插入文件索引复制后的新块有时称为影像块 原子事务实现 写前日志 1 修改文件前 先在稳定存储器日志上写入一个记录说明是哪个事务做的修改正在修改哪个文件夹哪个块修改前和修改后的值只有在正确完成日志的写操作之后 才修改文件 x 0 y 0 Begin transactionx x 1 y y 2 x y y End transcation x 0 1 日志 x 0 1 日志 y 0 2 x 0 1 日志 y 0 2 x 0 4 a b c d 写前日志 原子事务实现 写前日志 1 事务成功地执行完毕并被提交之后要在日志中写入一个提交记录如果终止事务 就可以利用日志恢复系统的原始状态回溯 从最后一条日志记录开始向前 读出每条记录 取消该记录中描述的操作日志还可以用于从系统崩溃中恢复执行 两段提交协议 1 两段提交协议 Gray 1978 使用最广泛的一种协议包含有关功能的一个进程作为协调者通常是执行事务的进程 两段提交协议 2 协调者写一条日志记录说明它要开始提交协议然后向事务中包含的其它进程 从属 发送消息通知这些进程准备提交 在日志文件中写 prepare 发送 prepare 消息 收录所有回答 写日志记录 发送 Commit 消息 第一阶段 第二阶段 在日志文件中写 Ready 发送 Ready 消息 发送 Finished 消息 在日志文件中写 Commit 承诺 成功执行的两段提交协议 协调者 子协调 两段提交协议 3 从属进程接到消息后检查自己是否就绪将结果写入日志并发送它的决定协调者接收到所有从属进程的响应后就可以确定提交还是终止事务 两段提交协议 4 如果所有进程都已准备好提交那么事务就提交如果有一个或几个进程不能提交事务中止 两段提交协议 5 无论提交或终止 协调者要写日志记录将其决定知所有的从属在写了这条日志记录之后 才真正地提交事务使用稳定存储器中的日志 协议在崩溃时有较大的弹性 八 并发控制 三种不同的并发控制算法 1 并发控制 加锁 最古老也是最广泛使用的并发控制算法 最简单的加锁形式 当进程在事务中要读或写某个文件时首先就为读文件加锁加锁可以由单个集中式的锁管理器完成也可以在每台机器上利用本地的锁管理器管理本地文件锁管理器都维护一个被锁定文件的列表用于拒绝其它进程试图锁定已加锁文件文件的锁通常由事务系统获取和释放 不需要编程人员的处理 并发控制 加锁的改进 方案太严格可以通区分读操作锁和写操作锁改进 读操作锁 为某文件设置了读操作锁仍允许为该文件设置其它的读操作锁读操作锁用于保证读文件的过程中文件不会被修改但是没有理由拒绝其它事务读这个文件 写操作锁 锁定一个文件执行写操作时不允许再为该文件设置任何类型的锁读操作锁是共享的 而写操作锁是互斥的 加锁的粒度 加锁的单位大小称为粒度加锁的单位可是更小的单位如单个的记录或页可能是更大的单位 如整个数据库粒度越细 加锁的准确度越高 能够达到的并行性也更好 细粒度的加锁操作需要更多的锁 代价更高而且更容易引起死锁 2 两段加锁方法 进程在它的成长阶段获取所需的全部锁在收缩阶段释放这些锁如果进程在到达收缩阶段前不允许修改任何文件那么在获取某些锁失败时 可以直接释放所有的锁稍待片刻后 再重断开始 两段加锁 锁的数量 时间 成长阶段 收缩阶段 锁点峰 两段加锁方法被广泛应用的原因 可以证明 如果所有事务都使用两段加锁方法那么将这些事务交叉后形成的时间表是序列化的 严格的两段加锁机制 收缩阶段在事务结束运行而提交或终止之后才发生 两段加锁的优点 每个事务读到的值都是由已经提交的事务修改过的值不会因为基于一个还不能使用的文件的原因 而终止该事务所有锁的分配和释放都由系统处理不需要事务了解这些过程 文件被访问时 系统为它加锁 事务结束时 释放相关的锁避免了级连式的事务终止的情况发生 由于使用了不该使用的文件而必须中止事务 九 常用的避免死锁的方法 1 以某种规范的顺序分配锁 避免出现占有一等待循环明确地维护一张图 说明哪个进程占有哪些锁 等待哪些锁然后通过检查该图中是否有回路就可以确定是否发生了死锁 常用的避免死锁的方法 2 超时方案限定锁的占有时间不超过T秒如果某个锁连续被同一事务占有的时间超过T秒断定发生了死锁 并发控制优化 隐含的技术思想惊人地简单 尽管继续做自己的事务 不必关心别人正在做什么如果有问题 以后再处理实际上 冲突很少发生因此大多数时间这种策略的效果很好 优化的并发控制方法 1 通过记录被事务读过和写过的文件处理冲突提交某个事务时 先检查所有其它事务确定事务启动之后 它的文件是否被修改过如果有 事务终止如果没有 事务提交 优化的并发控制方法 2 优化的并发控制最适合基于私有空间的实现方式每个事务以私有方式修改文件 不会互相干扰结果 新文件或者被提交 或者被释放优点 它不会引起死锁所有的进程不必等待所需要的锁 达到最大的并行度缺点是 有时会失败 要重新执行事务在负载较重的情况下 失败可能性聚增 1 时间戳 1 系统中每个文件都有相关的一个读时间戳和一个写时间戳Lamport算法可以保证这个时间戳是唯一的它们分别说明是哪个已提交的事务最后读 写了该文件 时间戳 2 某个进程试图访问文件时文件的读时间戳和写时间戳应比当前事务的时间戳更早 老 顺序关系说明事务正按照正常的次序执行 一切正常时间戳方法并不关心并发事务是否使用相同的文件只要有较小数字的事务总是在先即可 利用时间戳进行并发控制 利用时间戳进行并发控制 时间戳 3 事务碰到时间戳较大的文件时 必须终止时间戳方法不会发生死锁大大提升了它的优势 十 分布式系统中的死锁 两种死锁 通信死锁和资源死锁一个例子 进程A试着向进程B发送消息而进程B试图向进程C发送消息同时进程C又试图向进程A发送消息这种情况下导致死锁的原因很多比如 没有可用的缓冲区时就会发生死锁 资源死锁 发生在多个进程抢占需要互斥访问的I O设备 文件 锁或其它资源的情况下通信信道 缓冲区等也是资源因此通信死锁也可以认为是资源死锁 处理死锁的通用策略 无视死锁 忽略问题 检测 允许发生死锁 检测死锁 并试图从死锁中恢复 预防 静态的结构处理使死锁不可能发生 避免 通过仔细分配资源避免发生死锁 在分布式系统中 第一种方法应用普遍 效果好 1 分布式死锁的检测 只检测死锁 而不是禁止死锁的发生在基于原子事务的系统中检测到死锁时可以通过终止一个或多个事务解除死锁由于导致死锁而中止某事务时系统首先恢复到事务启动前的状态这时事务可以再次被启动第二次启动成功也是可能有的 集中式死锁检测方法 1 模拟非分布式的算法每台机器维护它上面运行的进程和资源构成的资源图用中心协调者维护整个系统的资源图 所有单个图的并集 在协调者检测到系统资源图中存在回路时杀死某个进程结束死锁 集中式死锁检测方法 2 分布式系统中 信息必须明确发送给某台机器每台机器维护自己的进程和资源图不论资源图中增加 减少弧线 消息都可送给协调器更新周期性地 送出相对先前所更新的弧线增加或删除的清单方法需要比较少的消息协调器在需要可以询问信息 虚假死锁 1 在分布式系统中 由于不完整或延迟的消息会产生虚假死锁解决问题的方法是用Lamport算法提供全局时间 虚假死锁 2 当协调者接收到机器的消息怀疑发生了死锁时它就向系统中的所有机器发送消息 我刚接收到时间戳为T的消息 它导致死锁如果谁有时间戳在此之前的消息 请立即发送给我 方法排除了虚假死锁 但需要全局时间 代价昂贵 2 分布式死锁检测方法 Chandy Misra Haas算法 1 允许进程一次请求多个资源 比如 锁 而不是一次一个事务的成长阶段的速度大大加快结果 进程就可能同时等待两个或更多资源 分布式死锁检测方法 Chandy Misra Haas算法 2 进程0被进程1阻塞时这时生成一条特殊的检测消息这条消息发送给占用所需资源的那个或那些进程 分布式死锁检测方法 Chandy Misra Haas算法 3 检测消息由三个数字构成 正被阻塞的进程号发送消息的进程号接收消息的进