2014-0914 第 3 章 分布式系统的同步.pptVIP

3.5 分布式系统中的死锁 3.5.2 分布式死锁预防 wound-wait算法 算法思想 当一个老进程想得到一个年轻进程占用的资源时，老进程抢占年轻进程的资源，年轻进程终止。 当一个年轻进程想得到一个老进程占用的资源时，年轻进程等待。 例子 老进程 10 新进程 20 请求资源 拥有资源 抢占 新进程 20 老进程 10 请求资源 拥有资源 等待 3.6 小结 分布式系统的同步 Lamport时钟同步算法 利用物理时钟进行同步 分布式系统中互斥算法 协调者选举算法：欺负算法和环算法 事务模型以及如何实现；三种并发控制方案：加锁、乐观并发控制和时间戳。 分布式系统中进行死锁检测和预防的算法。 Cristian’s算法 Berkeley算法 平均值算法 集中式算法 分布式算法 令牌环算法 3.2 互斥 3.2.2 分布式算法 Ricart和Agrawale算法 每次进入临界区需要2(n-1)条消息，n为系统中进程数。 如何解决多点失效 当请求到达时，不管是许可还是拒绝，都要发送应答。 一旦请求或应答丢失，发送者的等待时间到，它继续发送直到得到应答或者认为目的进程已经崩溃为止。 使用组通信原语 算法改进 当一个进程从大多数进程哪里获得允许而并不需要所有进程都允许时就可以进入临界区。 3.2 互斥 3.2.3 令牌环算法 0 2 4 9 7 1 6 5 8 3 进程 网络 2 3 4 5 6 7 8 9 0 1 令牌持有者可能进入临界区或将令牌往下传递 用软件的方法构造出一个逻辑环，环中每个进程都有一个位置，每个进程都知道谁在自己的下一个位置。优点：消息比分布式算法少。缺点：令牌丢失、进程崩溃。 图3-10 (a) 网络中一组未排序的进程 (b) 用软件构造进程的逻辑环 3.2 互斥 3.2.4 三种算法的比较 算法 每次进出需要的消息 进入前的延迟（按消息次数） 问题 集中式 3 2 协调者崩溃 分布式 2(n-1) 2(n-1) 任何一个进程崩溃 令牌环 1到无穷大 0到n-1 丢失令牌，进程崩溃 集中式、分布式和令牌环三种算法的性质的比较：进程进入或退出临界区需要的消息数目，每次进入前的延迟以及一些与算法有关的问题。 表3-1 三种互斥算法比较 3.3 选举算法 3.3.1 欺负(bully)算法 假设每个进程有一个特殊的号码，通常选举算法总是找拥有最大号码的进程。 欺负算法：当一个进程发现协调者不再相应请求时，它发起选举。进程P选举过程如下： P向所有号码比它大的进程发送选举(Election)消息 若无人响应，P获胜成为协调者。 若有号码比它大的进程响应，响应者接管，P的工作完成。 由于最大的进程总能取胜，因而将该算法命名为欺负算法。 实际应用中进程的号码是否应该有实际意义？ 3.3 选举算法 3.3.1 欺负(bully)算法 4 2 1 5 6 0 3 7 选举 选举 选举 4 2 1 5 6 0 3 7 OK OK 以前的协调者崩溃 4 2 1 5 6 0 3 7 选举 选举 选举 4 2 1 5 6 0 3 7 OK 4 2 1 5 6 0 3 7 协调者 协调者 （a） （b） （c） （d） （e） 3.3 选举算法 3.3.2 环算法 1 0 7 6 5 5 6 0 5 6 5 2 3 4 2 2 3 选举过程 ? 发起者沿环发送选举消息，若某点失效则绕过。 ? 每次发送者都将自己的进程号加入到消息中。 ? 最后，消息到达始发者手中，沿环发送协调者消息。 3.4 原子事务 3.4.1 原子事务简介 两个例子 老式磁带 银行转帐 （1）提取（金额，账户1） （2）存入（金额，账户2） 计算机 输入磁带 今天的更新 以前的库存 新的库存 输出磁带 3.4 原子事务 3.4.2 事务模型 稳定存储器 不受洪水地震之类大灾难之外的任何其他错误的影响，可以通过两个磁盘实现。适合于需高度容错的应用，例如事务。 s a h f w b t o s a h f w b t o s a1 h f w b t o s a h f w b t o s a h f w b t o s a f w b t o 错误的校验和 驱动器1 驱动器2 (a) (b) (c) 3.4 原子事务 3.4.2 事务模型 事务原语 BEGIN_TRANSACTION: 标记一个事务的开始； END_TRANSACTION: 结束事务并设法提交； ABORT_TRANSACTION; 取消事务；恢复旧值； READ：从一个文件（或其他对象）读取数据； WRITE：将