分布式系统中的时间问题

分布式操作系统中的时间问题

摘要

实践表明，分布式操作系统的同步问题常常比单处理器或者多处理器系统中的同步问题更加困难。本文从时间同步问题开始着手讨论，分析在分布式系统中同步问题的重要性以及如何在分布式系统中实现时间的同步。本文讨论的问题及其解决方式本质上是比较常见的并且出现在分布式操作系统的不同情况下。

关键词：分布式操作系统、同步、时间问题

Abstract

The practice shows that the synchronization problems in distributed operating systems often more difficult than synchronous problem of single processor or multiprocessor system. This paper begins to discuss from the time synchronization problem, analysis of the importance of synchronization problems in distributed system and how to realize the time synchronization in distributed system. This paper discusses the problems and the solutions are relatively common and occur in different situations under the distributed operating system.

Key Words: distributed operating systems、synchronization、timing issue

一、时钟同步问题

分布式系统中的同步比集中式系统中的同步要复杂一些，因为分布式系统中的同步只能通过分布式算法来实现，如果像集中式系统一样，在某地收集有关系统的所有有关信息，让某个进程分析并做出决定是不切实际的，一般来说分布式算法有如下的性质：

相关的信息分布在多台机器中

进程决策仅仅依赖于本地信息

系统中单点故障应该避免

没有公共时钟和其他精确的全局时间资源存在

前三点都说明了收集所有的有关信息并对它进行处理是不可接受的。比如：资源分配（以一种无死锁的分配方式分配）向单一的管理进程发送所有俄I/O请求，由该管理进程来检查这些请求，但是根据表中的信息允许或者是拒绝请求是不切实际的，在一个大的系统中，这样就会给进程造成太大的负担。 进一步而言，一个故障点就会造成系统的不可靠。而对于分布式系统来说他应该比单机系统更可靠，也就是说最理想的情况是：一台机器的崩溃不会影响其他机器的使用，而不是因为一台机器的故障而系统停滞不前

在集中式系统中，时间的概念很清楚，当进程想知道时间时，它使用由内核提供的系统调用。比如进程A先询问时间，然后进程B再询问时间，那么B得到的时间值就应该大于等于A得到的时间值，因此在分布式系统中获得一致的时间很不容易。

例：make file误差

进行编译的 计算机

21442145创建output.o

2142214321462147根据本地时钟的时间 进行编辑的

计算机2144

创建output.c2145根据本地时钟的时间二、物理时钟问题

时间

在一些实时系统中，实际时钟时间很重要，对这些系统都需要用到外部的物理时钟，为了提高效率和冗余性，一般使用多个物理时钟，但是又会出现两个问题：1.如何使物理时钟与世界的时钟同步？2.物理时间之间如何保持同步？

太阳日：连续的两次日中天的时间

太阳秒：solar-day/86400

平均太阳秒：如，格林威治时间

每天太阳都是从东方地平线升起，升到天空最高处，然后落到西边。太阳在最高点称为中天，它发生在每天的中午，连续两次中天之间的时间称为太阳日，每天24小时，每小时3600秒，所以精确的定义太阳秒为1/86400个太阳日，太阳日的几何计算方法如上图。

原子时钟：原子时钟能精确地计算时间。

国际原子时间（TAI）：虽然TAI相对稳定但是也有各种问题

BIH：通过引入闺秒来解决问题。当原子秒计时与太阳秒计时差距增到800微秒时使用闺秒。如下图：

三、逻辑时钟问题

1.逻辑时钟简介

只关心时钟内部一致性，不关心时钟是否与实际时间一致

1978年 Lamport指出，系统中的时钟并不需要绝对的同步

重要的不是进程有完全一致的时间，而是事件发生的先后次序要一致 发生之前（happens-before）关系定义

http://mport算法

时钟时间C必须向前（不断增加），不能后退（减小）

对时间的更新，只能是在时钟上加一个正数，不能减正数

四、时钟同步的几种算法

1.时钟同步算法

条件：

如果某台机器有WWV接收器

时钟同步的目的是使其它机器与这台机器同步

如何与现实时钟同步？

如何使不同机器之间相互同步？

介绍时间同步算法：

设每台机器都有个计时器，该计时器每秒中断H次，计时器溢出时，中断处理程序就将软件时钟加1，

软件时钟是从过去某一已知时间开始所经

历的tick数，这个时钟的值称为C。当UTC时间为t时，机器p的时钟值为Cp(t)，理想情况下dc/dt应为1。

真正的时钟计数器不是每秒精确地中断H次，当H = 60时，计时器应每小时生成216,000次ticks，实际上，计时器芯片的相对误差大约为10-5，即每小时的tick数的范围为215,998到216,002，准确地说，如果存在一个常数p ，使得1 - ρ≤ dC/dt ≤ 1 + ρ成立，就可以认为计时器是正常工作的。

如果两个时钟偏离UTC的方向相反，那么在同步之后的△t时刻时它们的时差为2ρ△t，要保证两个时钟间时间差不超过δ必须至少每隔δ/2ρ秒重新同步。

2.Cristian算法

简介 Cristian 算法 ：

该算法非常适合只有一台机器上有WWV接收器而其他所有机器与他同步的系统。

系统中每台机器至少每隔δ/2ρ秒就向时间服务器发送一条消息查询当前时间，服务器尽快将携带当前时间CUTC的消息返回给请求者一种近似方

法，发送者得到时间服务器的响应后，直接将其时钟值设置为CUTC

如下图：

该算法的问题：

时间决不能倒退

如果这个请求发送者的时钟比实际时间快，这时仅将CUTC设置为时钟的当前值会引起严重问题。比如：时钟发生变化后，编译产生的目标文件产生的时间早于时钟变化前源文件的修改时间。

对时钟的调整必须逐步进行：假设计时器每秒中断100次正常情况下，每次中断将时钟时间增加10毫秒，如果要使时钟慢下来，中断程序就每次只将时间增加9，直到将时间矫正过来为止。如果时钟要加快时，中断程序就每次只将时间增加11毫秒，而不是立即把时间调整到所需要的值。

时间服务器将当前时间发送给查询时间的机器需要时间，这个延迟时间 可能会很长，而且它也在变化，Cristian的处理方法就是计算出准确的延迟时间，为了提高估计值的准确性，建议要进行一系列的测量

3.Berkeley UNIX算法

时间服务器是活动的，它定期向其他机器查询这些机器的时间，根据得到的响应，时间服务器计算出一个平均值，并通知其它机器调整其时钟，重复这个过程，直到达到一定的缩减量为止

这种方法适用于那些没有WWV接收器的系统在这样的系统中，操作员必须阶段性地手工设置时间的时间

如下图：

4.平均值算法—非集中式算法

1.所有机器广播自己的时钟时间

2.启动本地计时器收集在S时间间隔中到达的其他机器广播的时间

3.执行平均时间计算算法，得到新的时间值

5.多重外部时间源法

例：OSF DCE方法

1.接受所有时间源的当前UTC(世界统一时间)区间

2.去掉与其他区间不相交的区间

3.将相交部分的中点作为校准时间

五、 同步时钟的应用

1.最多一次消息提交

每个消息携带一个ID和一个时间印ts（timestamp）

服务器的表T中记录每个连接C最近的时间印t ，

如果到达的消息m，ts(m)<t, 则拒绝m

2.服务器设置的全局变量

G = CurrentTime – MaxLifetime – MaxClockSkew(当前时间-最大生存时间-最大时钟偏移)

所有<G的时间印从表T中清除

对于具有新的ID的到达消息m,如果ts(m)<G则拒绝m,否则，接受m 按照 T，定期地将G写入磁盘。

当系统重启后，G’=G+ T

3.基于时钟的缓存一致性

当客户读取一个副本到缓存时，设置一个租期（lease）

在租期过期之前，客户可更新副本，重续租期

如果已经过期，缓存中的副本失效

4.改进的一致性协议

当客户修改文件时，只需将所有没有到期的缓存副本设为无效

如果某个客户崩溃，则等待直到该客户的租期过期