深度长文 | 循序渐进解读计算机中的时间—系统&硬件篇(上)
本文字数:5800字
预计阅读时间:25分钟
导读
上篇从日常代码出发,着重讨论了Java、MySQL等应用层中日期时间的表示和存储等操作、可能遇到的坑,及时区转换相关方法。中篇将刨根问底,探究 System.currentTimeMillis() 方法在不同平台是如何实现的,底层的区别是什么,及在实际开发中用到此方法的注意事项。
1 奇怪的现象
上篇中讲过 System.currentTimeMillis() 的用法,也提到了高频调用时会产生一定性能问题,我们先来看现象:用以下代码大致测量 System.currentTimeMillis() 方法的执行速度(运行一亿次,求平均时间):
1long sum = 0L;
2int N = 100000000;
3long begin = System.currentTimeMillis();
4for (int i = 0; i < N; i++) {
5 sum += System.currentTimeMillis();
6}
7long end = System.currentTimeMillis();
8System.out.println("sum = " + sum + "ms");
9System.out.println("total time = " + (end - begin) + "ms");
10System.out.println("average time = " + (end - begin) * 1.0E6 / N + " ns/iter");
查看不同系统的输出如图所示:
1、Windows(Windows 10,Intel(R) Core(TM) i5-6500):
2、macOS(macOS High Sierra,2.3 GHz Intel Core i5,MacBook Pro 2017):
3、Linux(3.10.0-327.28.3.el7.x86_64,Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz,服务器实体机):
●默认TSC时间源
●切换为另外一常用时间源:HPET
梳理以上实验:
结果是没有预料到的,最快和最慢差异能达到两个数量级,原因我们下面细细道来。
2 深入探索 System.currentTimeMillis()
System.currentTimeMillis() 是一个 native 方法,它的代码可以参考OpenJDK①
,我们找出此方法的JVM实现如下② :
1JVM_LEAF(jlong, JVM_CurrentTimeMillis(JNIEnv *env, jclass ignored))
2 JVMWrapper("JVM_CurrentTimeMillis");
3 return os::javaTimeMillis();
4JVM_END
调用了 os::javaTimeMillis() 方法,不同系统有不同的实现。Mac和Linux(TSC)的执行时间相近,我们挑选Windows和Linux系统探究原理并比较。
2.1
Windows实现
在 hotspot/src/os/windows/vm/os_windows.cpp③中追踪其实现如下:
1jlong os::javaTimeMillis() {
2 if (UseFakeTimers) {
3 return fake_time++;
4 } else {
5 FILETIME wt;
6 GetSystemTimeAsFileTime(&wt);
7 return windows_to_java_time(wt);
8 }
9}
10
11jlong windows_to_java_time(FILETIME wt) {
12 jlong a = jlong_from(wt.dwHighDateTime, wt.dwLowDateTime);
13 return (a - offset()) / 10000;
14}
15
16jlong offset() {
17 return _offset;
18}
19
20static jlong _offset = 116444736000000000;
由此可见该方法关口在于Windows的 GetSystemTimeAsFileTime() 方法,在Microsoft开发网站上④说明为:
该方法返回一个 FILETIME 类型的数据,其中包含两个32位字段:dwLowDateTime 和 dwHighDateTime,分别代表当前 FILETIME 的低位和高位。
组合起来返回1601年1月1日(UTC)以来以100ns为间隔的数量,减去 116444736000000000(1601年1月1日至1970年1月1日的100纳秒间隔个数)再除以 10000,即是当前Unix时间戳毫秒数。
为什么是1601年?因为现行 Gregorian Calendar 的时间周期是400年一轮(四年一闰,百年不闰,四百年再闰),1601年是距离Windows系统开始开发最近的一个400年周期点,把它作为系统时间的起点,那么把NT时间转换为常规日期表达(或相反)就不用做任何跳跃操作。
这个方法是在 kernel32.dll 中实现的,在VC中执行GetSystemTimeAsFileTime(&f)方法,从调试的 disassembly 模式调出执行的汇编语句如下图:执行的两句语句如下图,会首先去 call 调用 kernel32.dll 中的方法:
然后 jmp 到其具体实现:
关键流程:
执行后的结果,dwHighDateTime 和 dwLowDateTime 两个字段即为取出的数据:
进行转换操作:((dwHighDateTime << 32) + dwLowDateTime - offset) / 10000 即可转换为我们熟悉的Unix时间戳:
整个流程已经明晰,追踪下来可以了解到:此方法的执行逻辑仅仅是到固定的内存空间取这两个32位字段的值,没有经过任何用户态和内核态的转换过程。有一个后台进程会定期更新此内存空间中的字段值,保证是能取到的最新时间。
但是我们日常使用的Windows都不是实时操作系统(RTOS),系统提供的时间精度并没有到纳秒级别,我们来测试一下实际可以达到的最小时间间隔:
1
2
3
4
5int values[N];
6int main(void)
7{
8 int i;
9 for (i = 0; i < N; i++) {
10 FILETIME f;
11 GetSystemTimeAsFileTime(&f);
12 values[i] = (int) f.dwLowDateTime;
13 }
14 for (i = 1; i < N; i++)
15 if (values[i-1] != values[i])
16 printf("%d %d\n", i, values[i] - values[i-1]);
17 return 0;
18}
以上代码调用 1,000,000 次 GetSystemTimeAsFileTime 方法,并将得到的时间放到一个数组中,然后找出相邻两位不同的数字并求差,就是可以测算出的最小时间间隔。实验结果如下:
可以看到平均最小时间间隔为5000个100ns,即0.5毫秒,远没有达到ns级,但是已经够 System.currentTimeMillis() 的精度要求了。
综上,Windows系统下的 System.currentTimeMillis() 执行速度极快,约为4.77ns,最小时间间隔约为0.5毫秒。
2.2
Linux实现
在 hotspot/src/os/linux/vm/os_linux.cpp⑤中追踪其实现如下:
1jlong os::javaTimeMillis() {
2 timeval time;
3 int status = gettimeofday(&time, NULL);
4 assert(status != -1, "linux error");
5 return jlong(time.tv_sec) * 1000 + jlong(time.tv_usec / 1000);
6}
乘除法的时间消耗不会到百纳秒级别,可见该方法的关口在于 gettimeofday() 方法。接下来让我们一步一步深入Linux源码探个究竟。首先要明确实验机器的环境,如下图:
在 linux/v3.10/source/arch/x86/vdso/vclock_gettime.c⑥中找到 gettimeofday 方法:
1int gettimeofday(struct timeval *, struct timezone *)
2 __attribute__((weak, alias("__vdso_gettimeofday")));
可以看到,这里使用了vDSO(virtual dynamic shared object,直译为虚拟动态共享对象)。
关于 vsyscall 和 vDSO,内容着实精彩,但不是本文重点,感兴趣的同学可以参考⑦。
继续查看 __vdso_gettimeofday() 方法(部分):
1notrace int __vdso_gettimeofday(struct timeval *tv, struct timezone *tz)
2{
3 long ret = VCLOCK_NONE;
4 if (likely(tv != NULL)) {
5 // 实际获取时钟源时间的方法
6 ret = do_realtime((struct timespec *)tv);
7 tv->tv_usec /= 1000;
8 }
9 // 如果通过虚拟系统调用未获取到,则执行真正的系统调用,陷入内核态获取时间
10 if (ret == VCLOCK_NONE)
11 return vdso_fallback_gtod(tv, tz);
12 return 0;
13}
可以看到,其中主流程调用了 do_realtime() 方法获得当前机器时间,do_realtime 方法源码如下:
1#define gtod (&VVAR(vsyscall_gtod_data))
2
3notrace static int __always_inline do_realtime(struct timespec *ts)
4{
5 unsigned long seq;
6 u64 ns;
7 int mode;
8
9 ts->tv_nsec = 0;
10 do {
11 seq = read_seqcount_begin(>od->seq);
12 mode = gtod->clock.vclock_mode;
13 ts->tv_sec = gtod->wall_time_sec;
14 ns = gtod->wall_time_snsec;
15 ns += vgetsns(&mode);
16 ns >>= gtod->clock.shift;
17 } while (unlikely(read_seqcount_retry(>od->seq, seq)));
18
19 timespec_add_ns(ts, ns);
20 return mode;
21}
上述源码中可以看出,虚拟内存调用的逻辑和Windows中的逻辑很相近,都是从一个地址空间(上述源码通过变量gtod寻址)上定义好的数据结构中读取出当前机器时间。同时,一些后台线程会定期更新此结构的字段。
值得注意的是,Windows中两次读取高位数字并比较来确保读取的多个值的顺序一致性,这点在Linux中通过内存屏障来保证,这便是 read_seqcount_begin 和 read_seqcount_retry 的作用。同时,Intel x86的强内存排序也可以做到这一点。若有兴趣的同学可以详细了解源码及系统实现方法。
当前机器时间由两个字段表示:wall_time_sec 和 wall_time_snsec。wall_time_sec 代表机器从机器计时起点开始经过的秒数,wall_time_snsec 代表相对于最后一秒经过的纳秒级别时间,其精度可以通过 gtod->clock.shift 控制。参考了一些文献中的实验,现有 wall_time_snsec 的精度一般可以达到一毫秒以内。
至此,只是从固定地址空间读取和计算,并不会耗费很多时间。然而Linux并不满足于直接读取出的时间数值,试图继续通过 vgetsns() 方法获取更高精度的时间。vgetsns() 方法源码如下:
1notrace static inline u64 vgetsns(int *mode)
2{
3 long v;
4 cycles_t cycles;
5 if (gtod->clock.vclock_mode == VCLOCK_TSC)
6 cycles = vread_tsc();
7 else if (gtod->clock.vclock_mode == VCLOCK_HPET)
8 cycles = vread_hpet();
9 else if (gtod->clock.vclock_mode == VCLOCK_PVCLOCK)
10 cycles = vread_pvclock(mode);
11 else
12 return 0;
13 v = (cycles - gtod->clock.cycle_last) & gtod->clock.mask;
14 return v * gtod->clock.mult;
15}
至此我们终于见到了文章开篇问题中提到的时间源问题!系统中存在几个高频计时器,vgetsns() 方法会根据当前系统指定的计时器种类去读取该计时器中的“cycles”,即经过了多少个高频时钟周期,然后通过 gtod-> mask 和 gtod-> mult 字段进行时间的转换,并加到 wall_time_snsec 代表的纳秒时间数值中。
由文章开篇的现象可知,不同时间源获取时间的代价不同,追踪至此我们可以得出,就是在 vgetsns() 方法中消耗的时间成本导致的,而不同时间源的获取成本不同,则是由于其硬件构造和发展。
至此,可以说是部分“破案”了,之所以不同系统不同时间源差异如此之大,是由于实现方式不同。
Windows平台只是到固定的内存空间取两个32位字段的值并进行计算,所以最快;Linux中在此基础上通过读取高频计时器来提高获取的时间精度,所以普遍稍慢;也就是在这一步骤中,不同计时器的读取代价不同,造成总的执行成本有巨大差异。
说了这么久时间源的问题,但还没有了解时间源的相关概念,下面我们详细介绍。
3 常见的时钟、定时器硬件和时间源概念
不论软件层面如何读取如何计算,时间点的获取和时间段的计量总是要通过硬件来完成的。本章主要介绍几种常见的时钟和定时器硬件,及Linux在硬件上层抽象出的“时间源”数据结构。
3.1
常见时钟和定时器硬件
3.1.1 实时时钟(RTC)
和其他时钟硬件不同,实时时钟RTC(Real Time Clock)输出的是UTC时刻,而其他硬件如TSC、PIT、HPET等输出的都只是周期数,即“我已经走过XXX个cycle了,我的频率是XXX,你自己去算吧!”
这是因为RTC是独立于CPU和其他所有芯片的,即使当PC电源被切断RTC还可以继续工作。RTC和 CMOS RAM 被集成在一个芯片(Motorola 146818或其他等价的芯片)上,它靠主板上的一个小电池或蓄电池独立供电。
当然,既然RTC已经如此独特,它输出的时间精度自然不会很高(秒级),不然也没别的硬件什么事儿了。它可以在IRQ8上发出周期性的中断,主要用于在系统启动初始化时不依靠网络等外界帮助获取当前时间等,剩下的高精度需求就交给其他时间源来做。
3.1.2 时间戳计数器(TSC)
所有的 80x86 微处理器都包含一条CLK输入引线,它接收外部振荡器的时钟信号,从CLK管脚输入,以提供执行指令所需时钟沿。80x86 提供了一个 TSC 寄存器,该寄存器的值在每次收到一个时钟信号时加一。
比如 CPU 的主频为 1GHZ,则每一秒时间内,TSC 寄存器的值将增加 1G 次,或者说每一个纳秒加一次。x86 还提供了 rtdsc 指令来读取该值,因此 TSC 也可以作为时钟设备。
要注意,当使用这个寄存器时,必须考虑到时钟信号的频率。
3.1.3 可编程间隔定时器(PIT)
可编程间隔定时器PIT(Programmable Interval Timer)以内核确定的固定频率不停地发出时钟中断,类似于“打拍子”。
由于PIT出现较早,时钟频率也不高,渐渐被更加精确的HPET所取代,在此不过多介绍。
3.1.4 高精度事件定时器(HPET)
HPET是由微软和英特尔联合开发的定时器芯片,用以取代PIT提供高精度的时钟中断(10MHz以上)。一个HPET芯片包含了8个32位或64位的独立计数器,每个计数器由自己的时钟信号驱动,每个计时器又包含了一个比较器和一个寄存器(保存一个数值,表示触发中断的时机)。每一个比较器都比较计数器中的数值和寄存器的数值,相等就会产生中断。
3.1.5 其他定时器硬件
其他定时器硬件还包括:CPU本地定时器、ACPI电源管理定时器等。他们处于不同的位置,也有不同的时钟频率,但是由于综合功能和性能不及TSC和HPET,多数系统并未以其作为 current_clocksource。
3.2
clocksource数据结构
上文讲了众多的时间相关硬件,Linux为了管理这些硬件,抽象出来clocksource数据结构。查看实验机器可用的clocksource,包括:tsc、hpet、acpi_pm:
在linux/v3.10/source/include/linux/clocksource.h#L166⑧中可以找到clocksource数据结构的定义:
1struct clocksource {
2 /*
3 * Hotpath data, fits in a single cache line when the
4 * clocksource itself is cacheline aligned.
5 */
6 cycle_t (*read)(struct clocksource *cs);
7 cycle_t cycle_last;
8 cycle_t mask;
9 u32 mult;
10 u32 shift;
11 u64 max_idle_ns;
12 u32 maxadj;
13
14 struct arch_clocksource_data archdata;
15
16
17 const char *name;
18 struct list_head list;
19 int rating;
20 int (*enable)(struct clocksource *cs);
21 void (*disable)(struct clocksource *cs);
22 unsigned long flags;
23 void (*suspend)(struct clocksource *cs);
24 void (*resume)(struct clocksource *cs);
25
26 /* private: */
27
28 /* Watchdog related data, used by the framework */
29 struct list_head wd_list;
30 cycle_t cs_last;
31 cycle_t wd_last;
32
33} ____cacheline_aligned;
此数据结构中定义了很多时间源相关参数,比较重要的是 rating、shift、mult。
3.2.1 rating
精度越高的时间源,频率越高,rating值越大。从该源码的注释中可以得知:
●1--99:不适合于用作实际的时钟源,只用于启动过程或用于测试;
●100--199:基本可用,可用作真实的时钟源,但不推荐;
●200--299:精度较好,可用作真实的时钟源;
●300--399:很好,精确的时钟源;
●400--499:理想的时钟源,如有可能就必须选择它作为时钟源;
linux/v3.10/source/drivers/clocksource/acpi_pm.c#L66⑨中显示,ACPI时间源的rating是200;
linux/v3.10/source/arch/x86/kernel/hpet.c#L748⑩中显示,HPET时间源的rating是250;
linux/v3.10/source/arch/x86/kernel/tsc.c#L775⑪中显示,TSC时间源的rating是300。对应的,时间源硬件的频率查看如下:
可见,TSC时间源简直“超凡脱俗”。
3.2.2 shift 和 mult
由于除RTC外的硬件输出都是“节拍数”,所以要根据硬件频率换算成具体的时间段,公式为:时间段 = 节拍数 / 频率 。其中,节拍数可以通过 clocksource 数据结构中的成员变量 read 所指向的函数获取。例如 clocksource_tsc 的定义中深挖到最后是通过 rdtsc 指令来获取当前计数值cycles的。
可是这些和shift、mult两个变量有什么关系呢?计算机中对于除法的计算转化为乘法和移位更加方便,公式就变成了:时间段 = 节拍数 * mult >> shift。
在 linux/v3.10/source/include/linux/clocksource.h#L275⑫中定义如下:
1static inline s64 clocksource_cyc2ns(cycle_t cycles, u32 mult, u32 shift)
2{
3 return ((u64) cycles * mult) >> shift;
4}
3.3
不同时间源的比较
3.3.1 如何比较
由于有上述好多种时间源,不可避免要比较各个功能性能优劣,并将它们放在最合适的位置。比较的维度有多种:
●从功能上说,RTC时间源有自己独特的直接返回UTC时刻且“不断电” 的能力,虽然只能精确到秒级,但是足以应对系统时间初始化等场景。
整体来讲,系统的默认时间源是在根据硬件发展不停变化的,现在大多数默认时间源是TSC,在2007版的《深入理解Linux内核》一书中,当时最优的时间源还是HPET:
所以,大家要尽量在稳定基础理论的前提下,具体实操时了解确认最新的技术。针对现有的硬件,还要给大家提醒一个可能遇到的“坑”:多线程使用问题。
3.3.2 不同时间源的多线程使用的“坑”
文章开头已经给出,在Linux环境下,TSC和HPET的执行速度大概是 27.43 ns/次 和 574.93 ns/次 。这是单线程执行的结果,实际开发中会有很多多线程场景,或一个物理机上有多个程序在跑,那么他们会互相有影响吗?
3.3.2.1 现象
我们通过实验来验证。测试代码如下:
1public class Time {
2 static double sumAvg = 0;
3 public static void main(String[] args) throws InterruptedException {
4 // 测试机器24核,所以以24为上限进行测试,
5 for (int threadNums = 1; threadNums <= 24; threadNums++) {
6 // 各线程平均时间的累加,用于最后计算平均时间的平均数(可能中文表述难以理解,看代码吧)
7 sumAvg = 0;
8 // 控制主线程在子线程执行之后再进行平均值计算
9 final CountDownLatch countDownLatch = new CountDownLatch(threadNums);
10 for (int i = 0; i < threadNums; i++) {
11 // 每个线程测试平均每次 System.currentTimeMillis() 的请求时间
12 new Thread(() -> {
13 int N = 10000000;
14 long begin = System.currentTimeMillis();
15 for (int j = 0; j < N; j++) {
16 System.currentTimeMillis();
17 }
18 long end = System.currentTimeMillis();
19 double thisAvg = (end - begin) * 1.0E6 / N;
20 sumAvg += thisAvg;
21 countDownLatch.countDown();
22 }).start();
23 }
24 countDownLatch.await();
25 System.out.println("thread numbers = " + threadNums + ", average time = " + sumAvg / threadNums + " ns/iter");
26 }
27 }
28}
●使用TSC时间源
Excel图表表示更为清晰:
忽略double的丢失精度,可以看出:随着线程数增加,单个请求的耗时变化并不算大,只有在线程数接近核数时才些许上升。
●使用HPET时间源
在10个线程的时候已经达到了 44564ns/iter ,为了不影响服务没有继续增加线程数。但是趋势已经非常明显:随着线程数增加,单个请求的耗时呈线性增长。合理猜想,HPET时间源可能会串行化请求,或是有某个或多个步骤是处于临界区的,导致多个线程之间的相互影响,性能线性下降。至于理论依据还有待从硬件的角度考察。
●可能造成的问题
由于处理器在使用HPET时会相互影响,因此存在潜在的安全问题。一个进程可能会执行紧密循环调用 gettimeofday() 方法,从而导致所有其他进程调用此方法时性能降低。况且本来HPET的时间成本就较高,所以更要谨慎使用。
3.3.2.2 高并发下可用的解决方案
(1)如果并发量高但是对时间精确度要求不高的话可以使用独立线程缓存时间戳。只要用一个变量存当前时间戳,每过固定的一段间隔更新一次,其他调用需求直接取这个变量即可,实现举例如下:
1class MillisecondClock {
2 // 自定义的间隔时间段
3 private long gap = 0;
4 // 要缓存的当前时间点
5 private volatile long now = 0;
6
7 private MillisecondClock(long gap) {
8 this.gap = gap;
9 this.now = System.currentTimeMillis();
10 start();
11 }
12
13 private void start() {
14 new Thread(new Runnable() {
15
16 public void run() {
17 try {
18 Thread.sleep(gap);
19 } catch (InterruptedException e) {
20 e.printStackTrace();
21 }
22 now = System.currentTimeMillis();
23 }
24 }).start();
25 }
26
27 public long now() {
28 return now;
29 }
30}
(2)如果有必要,使用JNI将 System.currentTimeMillis() 方法调用的 gettimeofday() 方法换成 clock_gettime() 方法,会更加高效,详细不再展开;
(3)使用 System.nanoTime() 方法;至此,系统常用的时钟、定时器硬件及系统为其抽象出的数据结构及其区别简要介绍完毕。
4 总结
中篇主要抓住 System.currentTimeMillis() 方法深入探索,挖掘不同平台的性能区别及实现方案。由此入手,引出了常用的时钟、定时器硬件及系统抽象等相关概念。下篇将全面从系统入手,探究Linux计时体系结构,简要讲述用及“时间”和“定时器”时系统中做了哪些操作。
参考资料:
[1]http://hg.openjdk.java.net/jdk8
[2]http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/share/vm/prims/jvm.cpp
[3]http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/os/windows/vm/os_windows.cpp
[4]https://docs.microsoft.com/zh-cn/windows/win32/api/sysinfoapi/nf-sysinfoapi-getsystemtimeasfiletime
[5]http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/os/linux/vm/os_linux.cpp
[6]https://elixir.bootlin.com/linux/v3.10/source/arch/x86/vdso/vclock_gettime.c#L281
[7]https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html
[8]https://elixir.bootlin.com/linux/v3.10/source/include/linux/clocksource.h#L166
[9]https://elixir.bootlin.com/linux/v3.10/source/drivers/clocksource/acpi_pm.c#L66
[10]https://elixir.bootlin.com/linux/v3.10/source/arch/x86/kernel/hpet.c#L748
[11]https://elixir.bootlin.com/linux/v3.10/source/arch/x86/kernel/tsc.c#L775
[12]https://elixir.bootlin.com/linux/v3.10/source/include/linux/clocksource.h#L275
[13]https://elixir.bootlin.com/linux/v3.10/source
[14]http://pzemtsov.github.io/2017/07/23/the-slow-currenttimemillis.html
[15]https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html
也许你还想看
(▼点击文章标题或封面查看)
2019-11-14
2019-11-14
2019-07-11
加入搜狐技术作者天团
千元稿费等你来!
戳这里!☛
看完啦?留言支持一下再走吧~~~
▼▼▼