分布式算法举例
举例： 共有0，1，2三个进程。 进程0，2申请进入临界区
0
0
0
2
2
2
23/56
分布式算法评价
缺点：
• • •
n点失败 n点瓶颈 2（n-1)个消息
改进方案：

超时重发 组通信 简单多数同意
比原来集中式算法慢，复杂，昂贵，而且不健壮
24/56
令牌环算法
构造一个逻辑环，得到令牌才可进入临界区
例2：汇款（提款存款）
32/56
事务模型
稳定存储器（Stable Storage）： 通过一对双工磁盘实现
33/56
事务原语
（1）BEGIN_TRA NSACTION：标记一个事务的开始； （2）END_TRANSACTION：结束事务并设法提交； （3）ABORT_TRANSACTION：取消事务并恢复旧值； （ 4 ） READ ：从一个文件（或其他类型的对象，如数据 库）读取数据； （5）WRITE：将数据写入一个文件（或其他类型的对象， 如数据库）
34/56
事务举例
预定三个航班机票：中转站是JFK、Nairobi
BEGIN TRANSACTION reserve WP－JFK reserve JFK－Nairobi reserve Nairobi－Malindi END TRANSACTION BEGIN TRANSACTION reserve WP－JFK reserve JFK－Nairobi Nairobi－Malindi full ABORT TRASACTION
使用同步时钟
1. 当客户读取一个副本到缓存时，设置一个租期(lease) ① 2. 在租期过期之前，客户可更新副本，重续租期 ② 3. 如果已经过期，缓存中的副本失效
改进的一致性协议 • 当客户修改文件时，只需将所有没有到期的缓存副 本设为无效 • 如果某个客户崩溃，则等待直到该客户的租期过期

相关信息分布在多台机器中 进程只根据本地信息进行决策 应避免系统中的单点故障 不存在公共时钟或精确的全局时间
4/56
时钟同步问题
例：makefile误差
output.o ： cc –C output.c
进行编译的 计算机 2144 2145 创建output.o 进行编辑的 计算机 2142 2143 2144 创建output.c 时间 2145 根据本地时 钟的时间 2146 2147 根据本地时 钟的时间
3
25/56
三种互斥算法的比较
算法 集中式 分布式 令牌环
每次进出 进入前的延迟 需要的消息 （按消息次数） 3 2（n-1） 1到∞ 2 2（n-1） 0到n-1
存在问题
协调者崩溃 任何一个进程崩 溃 丢失令牌，进程 崩溃
26/56
主要内容
3.1 时钟同步
3.2 互斥
3.3 选举算法
3.4 原子性事务
o 假设：每秒产生100次中断， 每次中断将时间加10毫秒 若调慢时钟，中断服务程序 每次只加9毫秒； 若加快时钟，则加11毫秒。 传播时间=(T1-T0-I)/2
12/56
Berkeley 算法 – 主动式方法
1. 时间监控器定期查询其他机器时间 2. 计算出平均值 3. 通知其他机器调整时间
时间守护 3:00 3:00 3:00 3:00 +25 -10 -20 3:00 0 3:05 +5 +15 网络
3:25 (a)
2:50
3:25 (b)
2:50
3:05 (c)
3:05
13/56
平均值算法 – 非集中式方法
1. 将时间划分成固定长度的再同步间隔，第i
次间隔开始于T0+iR，而结束于 T0+(i+1)R 2. 在每个时间间隔，所有机器广播自己的时 钟时间 3. 启动本地计时器收集在第S时间间隔中到达 的其他机器广播的时间 4. 执行平均时间计算算法，得到新的时间值 （取平均值，去掉两端值 ）
36/56
隔离性（Isolated）
BEGIN_TRANSACTION x = 0; x = x+1; END_TRANSACTION (a) BEGIN_TRANSACTION x = 0; x = x+2; END_TRANSACTION (b) 时间 调度1 调度2 调度3 x=0; x=x+1; x=0; x=x+2; x=0; x=x+3; x=0; x=0; x=x+1; x=x+2; x=0; x=x+3; x=0; x=0; x=x+1; x=0; x=x+2; x=x+3; (d) 合法 合法 不合法 BEGIN_TRANSACTION x = 0; x = x+3; END_TRANSACTION (c)

dC/dt>1
稍快时钟
时钟时间,C

最大偏移率 精确时钟： dC/dt =1 快时钟： dC/dt 〉1 慢时钟： dC/dt < 1
dC/dt=1 最佳时 钟 稍慢时 dC/dt<1 钟
UTC，t
11/56
Christian’s 算法 -- 逐步调整法
时间服务器，可接受WWV的UTC时间 每隔δ/2ρ校准时间（ 允许误差δ ，存在误差ρ ） 校准原则：单调增
• • • •
服务器一直保存一个全局变量 G = CurrentTime – MaxLifetime – MaxClockSkew 所有<G的时间戳从表T中清除 对于具有新的ID的到达消息m，如果ts(m)<G则拒绝 m，否则，接受m 按照T，定期地将G写入磁盘 当系统重启后，G’=G+T
16/56
2
5 4 0 7
原有协调 者崩溃 (b)
1
ok
ok
2 5 6 4
1
选举
4 0
选举
5
选举
选举
6
3
0
7
(c)
6 3
选举
7
(a)
3
2
4 0 7
(d)
1
5
ok
2
4 0 7
(e)
1
5
协调者
(a) 进程4发起选举 (b) 进程5和6响应 (c) 进程5和6主持发 起选举 (d) 进程6响应 (e) 进程6获胜，并 通知所有进程
3.5 分布式系统中的死锁
27/56
3.3 选举算法
许多分布式算法需要一个进程充当协调者，发 起者，排序者或其他特定的角色 作用：做出统一的决定

例如：确定协调者
28/56
欺负(Bully)算法
2 1
选举
将进程进行排序
1. P向高的进程发送选
举消息 2. 如果没有响应，P选 举获胜 3. 如果有进程Q响应， 则P结束，Q接管选 举，并继续
第3章 分布式系统的同步
计算机科学与技术
钟发荣
1/56
主要内容
3.1 时钟同步
3.2 互斥
3.3 选举算法
3.4 原子性事务
3.5 分布式系统中的死锁
2/56
主要内容
3.1 时钟同步
3.2 互斥
3.3 选举算法
3.4 原子性事务
3.5 分布式系统中的死锁
3/56
3.1 时钟同步
分布式算法的特点
37/56
事务的实现
私有工作空间与影子更新：
当进程启动事务T时，分配一个私有工作空间W， 在提交或中止T前所有的读写操作都是在W中进行
3.1 时钟同步
3.2 互斥
3.3 选举算法
3.4 原子性事务
3.5 分布式系统中的死锁
31/56
3.4 原子性（Atomic）事务
隐藏技术，允许程序员专注于算法以及找出让进程并行 工作的方法 原子性： 组成原子事务的一组操作要么全部执行，要 么一个也不执行，并且事务失败后能返回到最初状态 例1： 老式磁带系统（备份）
7/56
校正算法



Lamport算法
0 0 6 12 18 24 30 36 42 48 54 60 D A 1 0 8 16 24 32 40 48 56 64 72 80 C B 2 0 10 20 30 40 50 60 70 80 90
100
0 0 6 12 18 24 30 36 42 48 70 76 D A
×n
9/56
现实时钟
铯原子钟：9192631770次跃迁=1秒 TAI秒：国际原子时间（巴黎BIH计算平均值） UTC秒：世界时间（在太阳秒中加入闰秒） 时间服务：WWV电台、GEOS卫星
பைடு நூலகம்
10
20
10/56
时钟同步算法
如何与现实时钟同步 如何使不同机器之间相
互同步 设机器时钟值Cp(t), t 为 UTC时间
基于时钟的缓存一致性
17/56
主要内容
3.1 时钟同步
3.2 互斥
3.3 选举算法
3.4 原子性事务
3.5 分布式系统中的死锁
18/56
3.2 互 斥
基本概念

当一个进程使用某个共享资源，其他进程不允许对 这个资源操作 对共享资源进行操作的程序段 信号量、管程
临界区（Critical Section）：
并发事件（concurrent）
6/56
Lamport算法
对每一事件a，指派所有进程都认可的时 间值C(a）

if ab，则C(a)<C(b) a,b，C(a) C(b) C是递增的 ab，则C(a)<C(b) C递增，只能加正数 2事件间至少间隔一个滴答 某些情况下需区别：进程1和进程2在40时刻 的发生时间：40.1，40.2