北京大学计算机系：《操作系统原理 Principles of Operating System》课程教学资源（PPT课件讲稿）第十章 分布式系统中的同步问题

第10章分布式系统中的同步问题 101时钟同步 分布式系统特点: 相关的信息分布在多台机器上 没有共享内存进程只根据本地可用的信息做 出决策 系统中不存在公共时钟或其它精确的全局时 间源 在集中式系统中,时间是很明确的

第10章 分布式系统中的同步问题 10.1 时钟同步 分布式系统特点： • 相关的信息分布在多台机器上 • 没有共享内存进程只根据本地可用的信息做 出决策 • 系统中不存在公共时钟或其它精确的全局时 间源 • 在集中式系统中，时间是很明确的

时钟同步例子 UNX的Make,检查文件最后修改时间 创建 input.o后,源 nput. C修改了,要重新 编译 input.C 设 ouput.o的修改时间是2000。创建 output o后即修改了源 output. c 但编辑 output. c的机器时钟慢,修改后 output.c时间被1999 make不会重新编译 output. c,程序的运行 会出现问题

时钟同步例子 UNIX的Make，检查文件最后修改时间 • 创建input.o后，源input.C修改了，要重新 编译input.C • 设 ouput.o 的 修 改 时 间 是 2000 。 创 建 output.o后即修改了源output.c • 但编辑 output.c的机器时钟慢，修改后 output.c时间被1999 • make不会重新编译output.c，程序的运行 会出现问题

10.2逻辑时钟(1) 只关心时钟内部一致性,不关心时钟是否与 实际时间一致 1978年 Lamport指出,系统中的时钟并不 需要绝对的同步 ·重要的不是进程有完全一致的时间,而是事 件发生的先后次序要一致

10.2 逻辑时钟(1) • 只关心时钟内部一致性，不关心时钟是否与 实际时间一致 • 1978年Lamport指出，系统中的时钟并不 需要绝对的同步 • 重要的不是进程有完全一致的时间，而是事 件发生的先后次序要一致

10.2逻辑时钟(2) 发生之前( happens- before)关系定义 表达式a→b读作“a发生在b前” 即所有进程都认为事件a先发生,然后才发 生事件b 事件a,有一个时间值c(a) 如果a和b是同一进程中的事件,而且a发生 在b前 那么a→b为true,c(a)<c(b)

10.2 逻辑时钟(2) 发生之前（happens-before）关系定义 • 表达式a b读作“a发生在b前” • 即所有进程都认为事件a先发生，然后才发 生事件b • 事件a，有一个时间值C（a） • 如果a和b是同一进程中的事件，而且a发生 在b前 • 那么a b为true, C（a）<C（b）

10.2逻辑时钟(3) 传递性 Happens-before关系具有传递性 如果a→b和bc都成立,日c也成立

10.2 逻辑时钟(3) • 传递性 Happens-before关系具有传递性 如果a b和b c都成立，a c也成立

并发事件 如果事件x和y发生在不同的进程中,且这 两进程间不交换信息 那么x→y和y→x都不成立。这两个事件就 称为并发事件 并发意味着两个事件发生时,无法确定哪个 事件先发生,或者说不需要考虑此事

并发事件： • 如果事件x和y发生在不同的进程中，且这 两进程间不交换信息 那么x y和y x都不成立。这两个事件就 称为并发事件 • 并发意味着两个事件发生时，无法确定哪个 事件先发生，或者说不需要考虑此事

Lamport算法(1): 时钟时间C必须向前(不断增加),不能后 退(减小) 对时间的更新,只能是在时钟上加一个正数, 不能减正数

• 时钟时间C必须向前（不断增加），不能后 退（减小） • 对时间的更新，只能是在时钟上加一个正数， 不能减正数 Lamport算法(1)：

006 A 12 16 16 20 18 B 24 32 004 18 B 24 32 40 30 0640 446A2 48 6 70 m09 77 90 8 100 个进程,有各自的时钟 Lamport算法

Lamport算法(2): 例子说明(1) 三个进程运行在不同的有自己时钟的机器上, 每个时钟按自己的速度运行 可以看到,进程0中时钟有6次嘀嗒时,进 程1已经有了8次,而进程2已经有了10次

例子说明(1) • 三个进程运行在不同的有自己时钟的机器上， 每个时钟按自己的速度运行 • 可以看到，进程0中时钟有6次嘀嗒时，进 程1已经有了8次，而进程2已经有了10次 Lamport算法(2)：

Lamport算法(3): 例子说明(2) 设,计时器每秒生成60次中断,每次中断 称为一个时钟嘀嗒 从进程2发送该进程1的消息C,其发送时刻 为60,到达时刻为56 同样,从进程1到进程0的消息D,其发送时 刻为64,到达时刻为54 这显然是不可能的,也是必须避免出现的情 况

• 设，计时器每秒生成60次中断，每次中断 称为一个时钟嘀嗒 • 从进程2发送该进程1的消息C，其发送时刻 为60，到达时刻为56 • 同样，从进程1到进程0的消息D，其发送时 刻为64，到达时刻为54 • 这显然是不可能的，也是必须避免出现的情 况 例子说明(2) Lamport算法(3)：