第 3章 分布式同步控制东北大学信息学院于 戈
2002年 6月
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
2
主要内容
3.1 时钟同步控制
3.2 互斥控制
3.3 选举算法
3.4 原子性事务管理
3.5 分布式死锁处理
3.6 习题
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
3
3.1 时钟同步
分布式算法的特点
相关 信息散布 在多个场地上
每个进程只能基于 本地信息 做决定
应避免因 单点失败 造成整个系统的失败
不存在公共时钟或精确的 全局时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
4
时钟同步问题
例,makefile误差时间
output.o,
cc –C output.c
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
5
逻辑时钟
计时器：石英晶体 +计数器
时钟偏差（ clock skew）
逻辑时钟：相对时间
物理时钟：真实时间
“之前”关系,?
– 事件 a在 b之前出现，则 a?b
– a为发送消息 m,b为接收 m，则 a?b
– 具有传递性,a?b,b?c,则 a?c
并发事件（ concurrent）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
6
Lamport算法
C(a)表示事件 a的时钟值。性质：
– if a?b;则 C(a)<C(b)
–?a,b C(a)? C(b)
– C是递增的
校正算法
– a?b，
– if C(b)<C(a),则 C(b) = C(a) +1
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
7
Lamport算法时间慢 快 慢 快
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
8
物理时钟与现实时钟
太阳日：连续的两次日中天的时间
太阳秒,solar-day/86400
平均太阳秒：如，格林威治时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
9
现实时钟
铯原子钟,9192631770次跃迁 =1秒
TAI秒：国际原子时间
UTC秒：世界时间（在 TAI秒中加入闰秒）
时间服务,WWV电台,GEOS卫星
10 20
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
10
时钟同步算法
如何与现实时钟同步
如何使不同机器之间相互同步
设机器时钟值 Cp(t),t 为 UTC时间
– 最大偏移率
– 精确时钟,dC/dt =1
– 快时钟,dC/dt 〉 1
– 慢时钟,dC/dt < 1
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
11
Christian’s 算法 -- 逐步调整法
时间服务器，可接受 WWV的 UTC时间
每隔 δ/2ρ校准时间（ 允许误差 δ,存在误差 ρ）
o 假设：每秒产生 100次中断，每次中断将时间加 10毫秒
若调慢时钟，中断服务程序每次只加 9毫秒；
若加快时钟，则加 11毫秒。
传播时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
12
Berkeley 算法 – 主 动式方法
1,时间 监控器定期查询其他机器 时间
2,计算出平均值
3,通知其他机器调整时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
13
平均值算法 – 非集中式方法
1,所有 机器广播 自己的时钟 时间
2,启动本地计时器收集在 S时间间隔中到达的其他 机器 广播 的时间
3,执行 平均时间计算 算法，得到新的时间值
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
14
多重外部时间源法
例,OSF DCE方法
1,接受所有时间源的当前 UTC区间
2,去掉与其他区间不相交的区间
3,将相交部分的中点作为校准时间时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
15
同步时钟的应用
最多一次消息提交
1,每个消息携带一个 ID和一个时间印 ts（ timestamp）
2,服务器的表 T中，记录每个连接 C最近的时间印 t
3,如果到达的消息 m,ts(m)<t,则拒绝 m
服务器设置的全局变量
G = CurrentTime – MaxLifetime – MaxClockSkew
所有 <G的时间印从表 T中清除
对于具有新的 ID的到达消息 m,如果 ts(m)<G则拒绝 m,
否则，接受 m
按照?T,定期地将 G写入磁盘。
当系统重启后,G’=G+?T
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
16
同步时钟的应用
基于时钟的缓存一致性
1,当客户读取一个副本到缓存时，设置一个租期（
lease）
2,在租期过期之前，客户可更新副本，重续租期
3,如果已经过期，缓存中的副本失效改进的一致性协议
当客户修改文件时，只需将所有没有到期的缓存副本设为无效
如果某个客户崩溃，则等待直到该客户的租期过期
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
17
3.2 互 斥
基本概念
– 当一个进程使用某个共享资源，其他进程不允许对这个资源操作
临界区：
– 对共享资源进行操作的程序段
基本方法：
– 信号量、管程
问题：
– 死锁
– 饥饿
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
18
集中式算法
协调者：确定那个进程可进入临界区
通信量,3个消息：请求 -许可 -释放
缺点：单点失败
C C C
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
19
分布式算法（ Ricart-Agrawala算法 ）
1,在一个进程 P打算进入临界区 R之前，向所有其他进程广播消息 <临界区 R名、进程号、时间印 >
2,当一个进程 P’收到消息后，做如下决定：
若 P’不在临界区 R中，也不想进入 R，它就向 P发送 OK消息；
若 P’已经在临界区 R中,则不回答,并将 P放入请求队列；
若 P’也同时要进入临界区 R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果 P时间印小，
则 P发送 OK消息 ;否则，不回答，并将 P放入请求队列 ；
3,当 P收到所有的 OK消息后，进入 R。否则，等待。
4,当 P退出 R时，如果存在等待队列，则取出一个请求者，向其发送 OK消息。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
20
分布式算法举例举例,共有 0,1,2三个进程 。
进程 0,2申请进入临界 区
0
2
0 0
2 2
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
21
分布式算法评价
缺点：
n点失败
n点瓶颈
2（ n-1)个消息
改进方案：
– 超时重发
– 组通信
– 简单多数同意
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
22
令牌环算法
构造一个逻辑环,得到令牌才可进入临界区
3
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
23
三种互斥算法的比较算法 每次进出需要的消息 进入前的延迟（按消息次数） 存在问题集中式 3 2 协调者崩溃分布式 2（ n-1） 2（ n-1） 任何一个进程崩溃令牌环 1到 ∞ 0到 n-1 丢失令牌，进程崩溃
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
24
3.3 选举算法
作用：做出统一的的决定
– 例如：确定协调者
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
25
欺负（ Bully）算法
将进程进行排序
1,P向高的进程发
E消息
2,如果没有响应，
P选举获胜
3,如果有进程 Q
响应,则 P结束，
Q接管选举并继续下去。
4 5
6
5
6
4
6
5
6
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
26
环算法
所有进程按逻辑或物理次序排序，形成一个环
1,当一个进程 P发现协调者 C失效后，向后续进程发送 E消息
2,每个进程继续向后传递 E消息，直到返回 P
3,P在将新确定的协调者
C’传给所有进程
5
2
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
27
3.4 原子性事务
原子性,组成原子事 务 的一组操作要么全部执行，要么一个也不执行，并且事 务 失败后能返回到最初状态
例 1,老式磁带系统（备份）
例 2：汇款（提款?存款）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
28
事务的性质
1,原子性（ Atomic）,对外部世界来说，事务的发生是不可分割的；
2,一致性（ Consistent）,事务不会破坏系统的恒定；
3,隔离性（ Isolated）,并发的事务之间不会互相干扰； 可串行性（ Serializable）,多个事务并发执行的结果，与它们顺序地执行效果相同。
4,持久性（ Durable）,一旦一个事务提交，它的更新结果不会因故障而丢失。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
29
事务模型
稳定存储器（ Stable Storage）：
– 通过一对双工磁盘实现
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
30
事务原语
（ 1） BEGIN_TRA NSACTION：标记一个事务的开始；
（ 2） END_TRANSACTION：结束事务并设法提交；
（ 3） ABORT_TRANSACTION：取消事务并恢复旧值；
（ 4） READ：从一个文件 （ 或其他类型的对象,如数据库 ） 读取数据；
（ 5） WRITE：将数据写入一个文件（或其他类型的对象，如数据库）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
31
事务举例
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
当第三个航班的机票预定失败后事务中止预定三个航班机票：中转站是 JFK,Nairobi
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
32
事务的实现
私有工作空间与影子更新：
当进程启动事务 T时，分配一个私有工作空间 W，
在提交或中止 T前所有的读写操作都是在 W中进行
0‘ 3‘
影子块
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
33
先 写日志 （ WAL）
就地更新（ in-place）
日志纪录
– 〈 事务标识，文件标识，块号，前像，后像 〉
例：
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
34
先 写日志 协议
回滚（ Rollback）,
– 反做 （ undo） 废弃事务的更新结果
只有当日志成功地写入稳存之后，才可以修改文件。
– 如果事务执行成功并被提交，则它的提交记录将被写入日志。
– 如果事务异常中止，则用日志来备份初始状态。
从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。
在系统崩溃后,日志也可用来进行的恢复。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
35
两阶段提交协议 （ 2PC）
准备阶段：取得一致决定
执行阶段：执行命令（提交或废弃）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
36
并发控制 (Concurrency Control)
正确性标准：可串行性（ serializable）
封锁
– 加锁：获得资源上的封锁
– 解锁：释放已拥有的锁
封锁的类型和相容性
– 读锁 (R)
– 写锁 (W)
锁的粒度
– 细粒度：如字段
– 粗粒度：如文件
R W
R √?
W
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
37
两阶段封锁协议 (2PL)
1,加锁阶段
2,开锁阶段
严格的 2PL
与 2PC结合
避免级联废弃
（ cascaded abort)
死锁：
等待图（ WFG）
超时检测（ timeout)
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
38
乐观法 (Optimistic)
1,读阶段：将文件读入私有工作区
2,确认阶段：提交前，检查是否有冲突
– 有，则废弃事务，重启。
– 无，则提交事务
3,写阶段：如可以提交，则将修改内容从私有工作区，写入文件。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
39
时间印法 (Timestamp)
每个事务的操作带有该事务的时间印
每个文件带有对它操作的最后一个提交事务的读时间印、写时间印
算法：
1,如果当前事务 T的时间印 〉 文件的时间印，
则执行；
2,否则,废弃 T;
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
40
时间印法举例
设有三个事务 α,β,γ。 T(α)<T(β)<T(γ)
T T
(φ)
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
41
三种方法比较并发度 死锁 性能
2PL 低 有 中乐观法 高 无 高（废弃度低时）
时间印法 较高 无 较高
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
42
3.5 分布式系统的死锁处理
死锁解决策略
– 鸵鸟法：留给用户考虑
– 检测法：发现死锁，进行处理
– 预防法：在设计上使死锁不可能发生
– 避免法：在运行中，防止出现死锁
银行家算法 [Dijkstra,1965]
P<has,max>,free
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
43
集中式检测 方法
进程 -资源等待图
– 节点：进程 P、资源 R
– 有向边,(1)P?R请求关系 ; (2) R? P拥有关系 ;
死锁检测协调者
– 负责检测死锁
资源图的维护策略：
– 当资源图中，有一条边加入 /删除时，通知协调者
– 每个进程周期性地向协调者发送图的更新消息
– 协调者在需要时，向参入者请求
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
44
假死锁问题,B释放 R,请求 T。若 请求 T消息 先到达 协调者
解决方案一,协调者确认（消息的全局时序）
集中式检测 方法举例
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
45
分布式检测方法
Chandy－ Misra－ Haas分布式死锁检测算法，
探测消息,〈 阻塞 Pid，请求 Pid,接收 Pid 〉
e.g,（ 0,2,3）,（ 0,4,6）,（ 0,5,7 ）,（ 0,8,0）构成死锁
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
46
分布式深度限制算法（ DWDL）
90%的死锁发生在两个进程之间
算法：
// p1为请求者 ; L(p1)为 p1的寿命
1) if ( waitQueue = p2->p1->p0 ) then
if ( L(p1)<L(p2) or L(p1))<L(p0) then restart p1;
else restart p0;
2) if (waitQueue = p1->p1'->p0 ) then
if ( L(p'1)<L(p1) or L(p'1)<L(p0)) then restart p'1;
else restart p0;
3) if (waitQueue = p2->p1->p'1->p0 ) then
if ( L(p1)<L(p2) or L(p1)<L(p0)) then restart p1;
else restart p'1;
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
47
等待 -死亡 算法 (wait-die)
– 设请求进程 0的时间印 t0,拥有资源的进程 1的时间印 t1
– 如果 t0<t1,0等待 ;
– 否则，撤销 0
分布式死锁预防
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
48
分布式死锁的预防
负伤 -等待 算法 （ wound-wait)
– 设请求进程 0的时间印 t0,拥有资源的进程 1的时间印 t1
– 如果 t0<t1，撤销 1;
– 否则,0等待
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
49
习 题
1,在右图中加入一条与 A并发的新消息。它既不在 A
之前，也不在 A之后。
2,假定有两台机器 A和 B,它们的时钟都是每毫秒滴答
1000次。但实际上 B每毫秒滴答 900次。如果每分钟根据 UTC时间校正一次时钟，那么 A和 B之间的最大时钟偏差是多少？
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
50
习 题
3,假定 A和 B是相互独立的两个临界区，进程 0要进入 A，进程 1要进入 B,R-A分布式互斥算法会导致死锁吗？说明理由。
4,对所介绍的 bully选举算法，进行优化。
5,事务时间印为 50的进程申请事务时间印为 100的进程占用的资源。按以下两种策略，结果会如何?(1)
等待 -死亡；（ 2）负伤 -等待。
2002年 6月
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
2
主要内容
3.1 时钟同步控制
3.2 互斥控制
3.3 选举算法
3.4 原子性事务管理
3.5 分布式死锁处理
3.6 习题
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
3
3.1 时钟同步
分布式算法的特点
相关 信息散布 在多个场地上
每个进程只能基于 本地信息 做决定
应避免因 单点失败 造成整个系统的失败
不存在公共时钟或精确的 全局时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
4
时钟同步问题
例,makefile误差时间
output.o,
cc –C output.c
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
5
逻辑时钟
计时器：石英晶体 +计数器
时钟偏差（ clock skew）
逻辑时钟：相对时间
物理时钟：真实时间
“之前”关系,?
– 事件 a在 b之前出现，则 a?b
– a为发送消息 m,b为接收 m，则 a?b
– 具有传递性,a?b,b?c,则 a?c
并发事件（ concurrent）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
6
Lamport算法
C(a)表示事件 a的时钟值。性质：
– if a?b;则 C(a)<C(b)
–?a,b C(a)? C(b)
– C是递增的
校正算法
– a?b，
– if C(b)<C(a),则 C(b) = C(a) +1
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
7
Lamport算法时间慢 快 慢 快
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
8
物理时钟与现实时钟
太阳日：连续的两次日中天的时间
太阳秒,solar-day/86400
平均太阳秒：如，格林威治时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
9
现实时钟
铯原子钟,9192631770次跃迁 =1秒
TAI秒：国际原子时间
UTC秒：世界时间（在 TAI秒中加入闰秒）
时间服务,WWV电台,GEOS卫星
10 20
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
10
时钟同步算法
如何与现实时钟同步
如何使不同机器之间相互同步
设机器时钟值 Cp(t),t 为 UTC时间
– 最大偏移率
– 精确时钟,dC/dt =1
– 快时钟,dC/dt 〉 1
– 慢时钟,dC/dt < 1
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
11
Christian’s 算法 -- 逐步调整法
时间服务器，可接受 WWV的 UTC时间
每隔 δ/2ρ校准时间（ 允许误差 δ,存在误差 ρ）
o 假设：每秒产生 100次中断，每次中断将时间加 10毫秒
若调慢时钟，中断服务程序每次只加 9毫秒；
若加快时钟，则加 11毫秒。
传播时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
12
Berkeley 算法 – 主 动式方法
1,时间 监控器定期查询其他机器 时间
2,计算出平均值
3,通知其他机器调整时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
13
平均值算法 – 非集中式方法
1,所有 机器广播 自己的时钟 时间
2,启动本地计时器收集在 S时间间隔中到达的其他 机器 广播 的时间
3,执行 平均时间计算 算法，得到新的时间值
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
14
多重外部时间源法
例,OSF DCE方法
1,接受所有时间源的当前 UTC区间
2,去掉与其他区间不相交的区间
3,将相交部分的中点作为校准时间时间
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
15
同步时钟的应用
最多一次消息提交
1,每个消息携带一个 ID和一个时间印 ts（ timestamp）
2,服务器的表 T中，记录每个连接 C最近的时间印 t
3,如果到达的消息 m,ts(m)<t,则拒绝 m
服务器设置的全局变量
G = CurrentTime – MaxLifetime – MaxClockSkew
所有 <G的时间印从表 T中清除
对于具有新的 ID的到达消息 m,如果 ts(m)<G则拒绝 m,
否则，接受 m
按照?T,定期地将 G写入磁盘。
当系统重启后,G’=G+?T
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
16
同步时钟的应用
基于时钟的缓存一致性
1,当客户读取一个副本到缓存时，设置一个租期（
lease）
2,在租期过期之前，客户可更新副本，重续租期
3,如果已经过期，缓存中的副本失效改进的一致性协议
当客户修改文件时，只需将所有没有到期的缓存副本设为无效
如果某个客户崩溃，则等待直到该客户的租期过期
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
17
3.2 互 斥
基本概念
– 当一个进程使用某个共享资源，其他进程不允许对这个资源操作
临界区：
– 对共享资源进行操作的程序段
基本方法：
– 信号量、管程
问题：
– 死锁
– 饥饿
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
18
集中式算法
协调者：确定那个进程可进入临界区
通信量,3个消息：请求 -许可 -释放
缺点：单点失败
C C C
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
19
分布式算法（ Ricart-Agrawala算法 ）
1,在一个进程 P打算进入临界区 R之前，向所有其他进程广播消息 <临界区 R名、进程号、时间印 >
2,当一个进程 P’收到消息后，做如下决定：
若 P’不在临界区 R中，也不想进入 R，它就向 P发送 OK消息；
若 P’已经在临界区 R中,则不回答,并将 P放入请求队列；
若 P’也同时要进入临界区 R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果 P时间印小，
则 P发送 OK消息 ;否则，不回答，并将 P放入请求队列 ；
3,当 P收到所有的 OK消息后，进入 R。否则，等待。
4,当 P退出 R时，如果存在等待队列，则取出一个请求者，向其发送 OK消息。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
20
分布式算法举例举例,共有 0,1,2三个进程 。
进程 0,2申请进入临界 区
0
2
0 0
2 2
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
21
分布式算法评价
缺点：
n点失败
n点瓶颈
2（ n-1)个消息
改进方案：
– 超时重发
– 组通信
– 简单多数同意
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
22
令牌环算法
构造一个逻辑环,得到令牌才可进入临界区
3
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
23
三种互斥算法的比较算法 每次进出需要的消息 进入前的延迟（按消息次数） 存在问题集中式 3 2 协调者崩溃分布式 2（ n-1） 2（ n-1） 任何一个进程崩溃令牌环 1到 ∞ 0到 n-1 丢失令牌，进程崩溃
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
24
3.3 选举算法
作用：做出统一的的决定
– 例如：确定协调者
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
25
欺负（ Bully）算法
将进程进行排序
1,P向高的进程发
E消息
2,如果没有响应，
P选举获胜
3,如果有进程 Q
响应,则 P结束，
Q接管选举并继续下去。
4 5
6
5
6
4
6
5
6
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
26
环算法
所有进程按逻辑或物理次序排序，形成一个环
1,当一个进程 P发现协调者 C失效后，向后续进程发送 E消息
2,每个进程继续向后传递 E消息，直到返回 P
3,P在将新确定的协调者
C’传给所有进程
5
2
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
27
3.4 原子性事务
原子性,组成原子事 务 的一组操作要么全部执行，要么一个也不执行，并且事 务 失败后能返回到最初状态
例 1,老式磁带系统（备份）
例 2：汇款（提款?存款）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
28
事务的性质
1,原子性（ Atomic）,对外部世界来说，事务的发生是不可分割的；
2,一致性（ Consistent）,事务不会破坏系统的恒定；
3,隔离性（ Isolated）,并发的事务之间不会互相干扰； 可串行性（ Serializable）,多个事务并发执行的结果，与它们顺序地执行效果相同。
4,持久性（ Durable）,一旦一个事务提交，它的更新结果不会因故障而丢失。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
29
事务模型
稳定存储器（ Stable Storage）：
– 通过一对双工磁盘实现
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
30
事务原语
（ 1） BEGIN_TRA NSACTION：标记一个事务的开始；
（ 2） END_TRANSACTION：结束事务并设法提交；
（ 3） ABORT_TRANSACTION：取消事务并恢复旧值；
（ 4） READ：从一个文件 （ 或其他类型的对象,如数据库 ） 读取数据；
（ 5） WRITE：将数据写入一个文件（或其他类型的对象，如数据库）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
31
事务举例
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
当第三个航班的机票预定失败后事务中止预定三个航班机票：中转站是 JFK,Nairobi
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
32
事务的实现
私有工作空间与影子更新：
当进程启动事务 T时，分配一个私有工作空间 W，
在提交或中止 T前所有的读写操作都是在 W中进行
0‘ 3‘
影子块
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
33
先 写日志 （ WAL）
就地更新（ in-place）
日志纪录
– 〈 事务标识，文件标识，块号，前像，后像 〉
例：
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
34
先 写日志 协议
回滚（ Rollback）,
– 反做 （ undo） 废弃事务的更新结果
只有当日志成功地写入稳存之后，才可以修改文件。
– 如果事务执行成功并被提交，则它的提交记录将被写入日志。
– 如果事务异常中止，则用日志来备份初始状态。
从日志的未尾开始，向回逐个读取日志记录，反做记录中描述的修改，即回滚处理。
在系统崩溃后,日志也可用来进行的恢复。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
35
两阶段提交协议 （ 2PC）
准备阶段：取得一致决定
执行阶段：执行命令（提交或废弃）
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
36
并发控制 (Concurrency Control)
正确性标准：可串行性（ serializable）
封锁
– 加锁：获得资源上的封锁
– 解锁：释放已拥有的锁
封锁的类型和相容性
– 读锁 (R)
– 写锁 (W)
锁的粒度
– 细粒度：如字段
– 粗粒度：如文件
R W
R √?
W
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
37
两阶段封锁协议 (2PL)
1,加锁阶段
2,开锁阶段
严格的 2PL
与 2PC结合
避免级联废弃
（ cascaded abort)
死锁：
等待图（ WFG）
超时检测（ timeout)
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
38
乐观法 (Optimistic)
1,读阶段：将文件读入私有工作区
2,确认阶段：提交前，检查是否有冲突
– 有，则废弃事务，重启。
– 无，则提交事务
3,写阶段：如可以提交，则将修改内容从私有工作区，写入文件。
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
39
时间印法 (Timestamp)
每个事务的操作带有该事务的时间印
每个文件带有对它操作的最后一个提交事务的读时间印、写时间印
算法：
1,如果当前事务 T的时间印 〉 文件的时间印，
则执行；
2,否则,废弃 T;
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
40
时间印法举例
设有三个事务 α,β,γ。 T(α)<T(β)<T(γ)
T T
(φ)
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
41
三种方法比较并发度 死锁 性能
2PL 低 有 中乐观法 高 无 高（废弃度低时）
时间印法 较高 无 较高
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
42
3.5 分布式系统的死锁处理
死锁解决策略
– 鸵鸟法：留给用户考虑
– 检测法：发现死锁，进行处理
– 预防法：在设计上使死锁不可能发生
– 避免法：在运行中，防止出现死锁
银行家算法 [Dijkstra,1965]
P<has,max>,free
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
43
集中式检测 方法
进程 -资源等待图
– 节点：进程 P、资源 R
– 有向边,(1)P?R请求关系 ; (2) R? P拥有关系 ;
死锁检测协调者
– 负责检测死锁
资源图的维护策略：
– 当资源图中，有一条边加入 /删除时，通知协调者
– 每个进程周期性地向协调者发送图的更新消息
– 协调者在需要时，向参入者请求
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
44
假死锁问题,B释放 R,请求 T。若 请求 T消息 先到达 协调者
解决方案一,协调者确认（消息的全局时序）
集中式检测 方法举例
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
45
分布式检测方法
Chandy－ Misra－ Haas分布式死锁检测算法，
探测消息,〈 阻塞 Pid，请求 Pid,接收 Pid 〉
e.g,（ 0,2,3）,（ 0,4,6）,（ 0,5,7 ）,（ 0,8,0）构成死锁
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
46
分布式深度限制算法（ DWDL）
90%的死锁发生在两个进程之间
算法：
// p1为请求者 ; L(p1)为 p1的寿命
1) if ( waitQueue = p2->p1->p0 ) then
if ( L(p1)<L(p2) or L(p1))<L(p0) then restart p1;
else restart p0;
2) if (waitQueue = p1->p1'->p0 ) then
if ( L(p'1)<L(p1) or L(p'1)<L(p0)) then restart p'1;
else restart p0;
3) if (waitQueue = p2->p1->p'1->p0 ) then
if ( L(p1)<L(p2) or L(p1)<L(p0)) then restart p1;
else restart p'1;
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
47
等待 -死亡 算法 (wait-die)
– 设请求进程 0的时间印 t0,拥有资源的进程 1的时间印 t1
– 如果 t0<t1,0等待 ;
– 否则，撤销 0
分布式死锁预防
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
48
分布式死锁的预防
负伤 -等待 算法 （ wound-wait)
– 设请求进程 0的时间印 t0,拥有资源的进程 1的时间印 t1
– 如果 t0<t1，撤销 1;
– 否则,0等待
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
49
习 题
1,在右图中加入一条与 A并发的新消息。它既不在 A
之前，也不在 A之后。
2,假定有两台机器 A和 B,它们的时钟都是每毫秒滴答
1000次。但实际上 B每毫秒滴答 900次。如果每分钟根据 UTC时间校正一次时钟，那么 A和 B之间的最大时钟偏差是多少？
2002-6-14
东北大学软件所 于戈 第三章 分布式同步控制
50
习 题
3,假定 A和 B是相互独立的两个临界区，进程 0要进入 A，进程 1要进入 B,R-A分布式互斥算法会导致死锁吗？说明理由。
4,对所介绍的 bully选举算法，进行优化。
5,事务时间印为 50的进程申请事务时间印为 100的进程占用的资源。按以下两种策略，结果会如何?(1)
等待 -死亡；（ 2）负伤 -等待。
