第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也成立