操作系统原理精讲（四）.pptVIP

第10章 分布式系统中的同步问题 10.1 时钟同步 分布式系统特点： 相关的信息分布在多台机器上 没有共享内存进程只根据本地可用的信息做出决策 系统中不存在公共时钟或其它精确的全局时间源 在集中式系统中，时间是很明确的 时钟同步例子 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 逻辑时钟(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和b c都成立，a c也成立 并发事件： 如果事件x和y发生在不同的进程中，且这两进程间不交换信息 那么x y和y x都不成立。这两个事件就称为并发事件 并发意味着两个事件发生时，无法确定哪个事件先发生，或者说不需要考虑此事 Lamport算法(1)： 时钟时间C必须向前（不断增加），不能后退（减小） 对时间的更新，只能是在时钟上加一个正数，不能减正数 例子说明(1) 三个进程运行在不同的有自己时钟的机器上，每个时钟按自己的速度运行 可以看到，进程0中时钟有6次嘀嗒时，进程1已经有了8次，而进程2已经有了10次 例子说明(2) 设，计时器每秒生成60次中断，每次中断称为一个时钟嘀嗒 从进程2发送该进程1的消息C，其发送时刻为60，到达时刻为56 同样，从进程1到进程0的消息D，其发送时刻为64，到达时刻为54 这显然是不可能的，也是必须避免出现的情况 Lamport算法(4)： 消息c的发送时间为60，它的到达时间一定在时刻61或61之后 让每条消息都携带发送者时钟的发送时刻 当消息到达接收时，如果接收者的时钟指示值先于发送消息的时间 接受者的时钟值就应快于消息发送时刻加1之后时间值 Lamport算法(5)： 两个事件之间，时钟至少应间隔一个嘀嗒 如果一个进程依次快速发送或接收两条消息，就必须调整时钟 使两个事件之间（至少）间隔一个时钟嘀嗒 Lamport算法(6)： 附加条件, 没有两个事件是精确地在同一时刻发生的： 1.在同一进程中，如果a在b前面发生， 那么C(a)C(b) 2.如果a与b分别代表诮息的发送和接收， 那么C(a)C(b) 3.对于所有的事件a与b而言，C(a)≠C(b) Lamport算法(7)： 算法给出系统中所有事件的整体定序方法 该算法在学术界中得到广泛认同 10.3 物理时钟(1) 在某些系统中，实际的时钟时间非常重要，需要物理时钟 如何使物理时钟与世界的时钟同步？ 物理时间之间如何保持同步？ 物理时钟(2) 原子钟可以准确度量时间 世界时（Universal Coordinated Time）简称UTC UTC是现代计时的基础 National Institute of Standard Time NIXT, 国家标准时间组织短波电台，WWV 每个UTC秒的起始时刻，WWV就发送一个短脉冲 WWV本身的误差大约为+-1毫秒 10.4 时钟同步算法 如果某台机器有WWV接收器 时钟同步的目的是使其它机器与这台机器同步 时钟同步算法的基本模型(1) 设每台机器都有个计时器，该计时器每秒中断H次 计时器溢出时，中断处理程序就将软件时钟加1 软件时钟是从过去某一已知时间开始所经历的tick数 这个时钟的值称为C。当UTC时间为t时，机器p的时钟值为Cp (t) 理想情况下dC/dt应为1 时钟同步算法的基本模型(2) 理论上，当H = 60时，计时器应每小时生成216,000次ticks 实际上，计时器芯片的相对误差大约为10-5， 即每小时的tick数的范围为215,998到216,002 准确地说，如果存在一个常数p 1 - ρ≤ dC/dt ≤ 1 + ρ 成立，就可以认为计时器是正常工作的 如果两个时钟偏离UTC的方