第3章 时间的衡量和计算
我们的作息、行为和活动都与时间息息相关，从人类的角度来看，时间是以时分秒来计算和衡量的。例如，某一时刻做某件事情或某个任务持续了多久等情况，我们基本都以时分秒来计算。但内核中却不是这样，从内核的角度，它的时间以滴答（jiffy）来计算。滴答，通俗地讲，是时间系统周期性地提醒内核某时间间隔已经过去的行为。另一方面，内核服务于用户，所以它还需要拥有将滴答转为时分秒的能力。因此，内核的任务就分为维护并响应滴答和告知用户时间两部分。
3.1 数据结构
我们从gettimeofday系统调用说起，它的功能是获取当前时间，结果以timeval和timezone（时区）结构体的形式返回，timeval的tv_sec字段表示从Epoch（1970-01-01 00:00:00 UTC）到现在的秒数，tv_usec表示微秒。
内核先通过ktime_get_real_ts64获得以timespec表示的当前时间，然后转化为timeval形式，timespec64的tv_sec以秒为单位，tv_nsec以纳秒为单位，实现过程展开如下。
以上代码段中，第一个与时间相关的结构体为timekeeper（简称tk，稍后详解），它的主要功能是保持或者记录时间，从timekeeping_get_ns函数可以看到，tk的tkr_mono->clock字段指向clocksource类型的对象，表示当前使用的时钟源。当前时间等于上次更新时的时间（xtime_nsec）加上从上次更新到此刻的时间间隔，时间间隔是通过时钟源度过的时钟周期（cycle_delta）计算得来的。各时钟源的时钟频率不同，所以它们时钟周期的时间单位就不同，内核需要拥有将设备时钟周期数与纳秒相互转换的能力，mult和shift字段就是负责实现该需求的。请注意，“上次更新”是指内核更新时间，是“写”动作，gettimeofday是“读”动作，并不会导致xtime_nsec变化。
时钟源以clocksource结构体（简称cs）表示，它是本章第二个核心的结构体，主要字段如表3-1所示。
表3-1 clocksource字段表
flags字段有多种标志，前三种可以由时钟设备的驱动设置，后几种一般由内核控制，如表3-2所示。
表3-2 时钟设备标志表
rating字段代表cs的等级，内核只会选择一个时钟源作为watchdog（即看门狗），也只会选择一个时钟源作为系统的时钟源（与全局变量tk_core.timekeeper对应），同等条件下，等级更高的时钟源拥有更高的优先级。
内核会选择一个不需要被监控的连续时钟源作为看门狗，它负责在程序运行的时候监控其他的时钟源，如果某一个时钟源的误差超过了可接受的范围，那么，则将其置为CLOCK_SOURCE_UNSTABLE，并将其rate字段置为0。
时钟源设备在初始化后可以调用clocksource_register_hz等函数完成注册，内核会在所有时钟源中选择rating值最大的作为保持时间的时钟源，用户调用gettimeofday获取当前时间时，就通过该时钟源读取时钟周期数来计算得到结果。
我们通过内核得到了当前的时间，但内核基本不会关心时分秒，它的重心在于某个时间间隔已经过去这类事件；这就依赖于另一种设备了，它们可以实现定时器的功能，在设定的时间间隔过去之后产生中断提醒内核。当然，有些设备既有保持时间的功能，又有定时器的功能。为方便读者理解，本文以下将保持时间的设备称为时钟源，将关注时间事件的设备称为时钟中断设备（或称为时钟事件设备，为了突出时钟事件的本质）。
本章的另一个核心结构体clock_event_device（简称evt）就与内核这第二个需求相关，它的主要字段如表3-3所示。
表3-3 clock_event_device字段表
set_state_xxx是切换当前设备状态的回调函数，xxx可以有共有periodic、oneshot、oneshot_stopped和shutdown四种。其中，periodic表示周期性地触发时钟中断，oneshot表示单触发。所谓周期性是指触发一次中断之后自动进入下一次中断计时，单触发是指触发一次中断之后停止。rating字段表示设备的等级，等级越高优先级越高。最常用的设备特性（features字段）有PERIODIC、ONESHOT和C3STOP三种，其中C3STOP表示系统处于C3状态的时候设备停止。
时钟中断产生后，内核会调用event_handler字段的回调函数处理中断，该函数完成时钟中断相关的逻辑，还可以回调set_next_event设置下一次时钟中断。时钟中断对内核而言是必不可少的，内核对各模块的时间控制基本都依赖它。
内核使用了几个常见的变量和宏定义，具体如下。
HZ：一秒内的滴答数。现代内核并不一直采用周期性的滴答，硬件允许的情况下，更倾向于采用动态（非周期性）时钟中断，但HZ作为很多模块衡量时间的基准被保留了下来。
jiffies：累计的滴答数。内核主要存在jiffy和ktime_t两个时间单位，后者本质上就是纳秒，内核对相关计算进行优化并提供了使用它的函数，因而产生了ktime_t。我们可以使用ktime_get获得当前以ktime_t为单位的时间，使用ktime_to_ns和ns_to_ktime等完成转换。
在涉及时钟设备或者时钟中断设备的操作时，比如读取时钟周期数、设置下一个中断等，会使用纳秒为单位；如前文所述，设备数据结构中的mult和shift字段可以实现纳秒与周期数的转化。其余方面，除非需要跟踪时间，基本都使用jiffy为单位。
tick_period：ktime_t类型的全局变量，周期性时钟中断的时间间隔。稍后会发现，即使采用动态时钟中断的系统，它在运行的某些阶段依然可能周期性地触发中断。该变量就是为了计算周期性时钟中断的条件下，下一次中断的触发时间。
tick_cpu_device：每cpu变量，类型为tick_device，简称td。tick_device结构体的evtdev字段指向该cpu的evt，mode字段表示其工作模式，分为TICKDEV_MODE_PERIODIC和TICKDEV_MODE_ONESHOT两种。
tick_cpu_sched：每cpu变量，类型为tick_sched，简称ts，它与系统调度和更新系统时间有关。
3.2 时钟芯片
不同的架构或平台使用的设备不一定相同，下面介绍几个x86架构上常见的设备。
RTC（Real-timeClock）：实时时钟，兼具时钟源和时钟中断两种功能，它可以为人们提供精确的实时时间，或者为电子系统提供精确的时间基准，目前绝大多数计算机上都会有它。RT C有一个特性，那就是系统关机以后依然处于工作状态。就提供实时时间而言，RT C的准确度一般要比其他几个设备高；就时钟中断而言，RT C只能产生周期信号，频率变化范围从2Hz到8192Hz，且必须是2的倍数，所以在现代计算机上它的第二个功能基本被其他设备取代。
PIT（Programmable interval timer）：可编程间隔计时器，时钟中断设备，频率固定为1.193182MHz，所以在老式的系统中它也可以充当时钟源的角色。PIT可满足周期性和单触发两种时钟中断要求。
TSC（Time Stamp Counter）：时间戳计数器，是一个64位的寄存器，从奔腾处理器开始就存在于x86架构的处理器中。TSC记录处理器的时钟周期数，程序可以通过RDTSC指令来读取它的值。采用TSC作为系统的时钟源是有挑战的，比如处理器降频的时候，TSC如何保持固定频率，不过在现代的x86处理器中，这些问题已经得到了解决。TSC以其高精度、低开销的优势成为优选。
HPET（High Precision Event Timer）：俗称高精度定时器，兼具时钟源和时钟中断两种功能，它有一组定时器可以同时工作，数量从3到256个不等。每个定时器都可以满足周期性和单触发两种时钟中断要求，可以代替PIT及RTC。
APIC（Advanced Programmable Interrupt Controller）：高级可编程中断控制器，用作时钟中断设备，单从名字看就比PIT高一个档次。APIC的资料网络上多如牛毛，这里不详细阐述。每个cpu都有一个local（本地）APIC，这里的时间设备就是本地APIC的一部分。它的精度较高，可以满足周期性和单触发两种时钟中断要求。
就cs而言，PIT、TSC和HPET的cs对象rating字段的默认值如表3-4所示（RTC并不在cs和evt的选项中）。
表3-4 cs设备rating表
因为TSC的优先级最高，所以大多数计算机会采用TSC作为时钟源。然而TSC的频率是开机的时候计算得出的（见下），小的误差在运行过程中会被放大，最终导致较明显的时间偏差。RT C倒是可以很好地完成保持时间的任务，但它的频率太低，精度不够。
TSC对应的cs的flags字段有IS_CONTINUOUS和MUST_VERIFY两个标记，所以它可以满足CLOCK_SOURCE_VALID_FOR_HRES的要求，但不能作为系统的watchdog，而属于会被watchdog监控的时钟源。
就evt而言，PIT、HPET和APIC的evt对象的rating字段的默认值如表3-5所示。
表3-5 evt设备rating表
3.3 从内核的角度看时间
内核维护了多种时间，其中最常用REALTIME、MONOTONIC和BOOTTIME三种。
REALTIME时间：又称作WALLTIME（墙上时间），甚至可以称为xtime时间或者系统时间，xtime在分析gettimeofday系统调用的时候已经出现过了，它就是根据cs的时钟周期计算得出的时间。
需要注意的是，REALTIME时间和RTC时间并不是同一个概念。前者是内核维护的当前时间，RT C时间是RT C对应芯片维护的硬件时间。二者也是有联系的，系统启动的时候，内核会读取RTC的时间作为REALTIME时间，之后才独立。另外，settimeofday系统调用会更新REALTIME时间，并不会更新RTC时间。所以，仅仅设置系统时间，重启机器后设置不会生效。我们可以使用hwclock-hctosys和hwclock-systohc两个命令（Hardware Clock to System）完成二者的同步，或者设置系统时间后运行hwclock-w命令同步到RT C时间。
MONOTONIC时间：不是绝对时间，表示系统启动到当前所经历的非休眠时间，单调递增，系统启动时该值由0开始（timekeeping_init函数），之后一直增加。它不受REALTIME时间变更的影响，也不计算系统休眠的时间，也就是说，系统休眠时它不会增加。
tk的xtime_sec表示REALTIME时间，wall_to_monotonic字段表示由xtime计算得到MONOTONIC时间需要加上的时间段。
在3.10版的内核中，total_sleep_time字段表示系统休眠的时间。下面以xtime表示REALTIME时间，xtime_org表示系统启动时的xtime初值，wtm表示tk的wall_to_monotonic字段，wtm_org表示系统启动时wtn的初值，boot_time表示系统启动时REALTIME时间。则3.10版内核中存在6个公式。
xtime+wtm=monotonic公式（1）
由于系统启动时monotonic为0，所以有如下关系。
wtm_org=-xtime_org=-old_boot_time公式（2）
系统每次休眠，xtime都会变大，但由于monotonic时间不计算休眠时间，所以有如下关系。
xtime_before_suspend+wtm_before_suspend=monotonic_before_suspend
(xtime_before_suspend+sleep)+wtm_after_suspend=monotonic_after_suspend
monotonic_before_suspend=monotonic_after_suspend
得出：wtm_after_suspend=wtm_before_suspend-sleep
所以，每次休眠过后xtime增加了sleep，wtm也要相应地减去sleep，在不考虑主动修改xtime造成影响的情况下，累计所有的sleep时间得到如下关系。
wtm_current=wtm_org-total_sleep_time 公式（3）
软件上主动修改xtime亦如此，比如sys_settimeofday系统调用。
记delta=xtime_after_set-xtime_before_set
有：wtm_after_set=wtm_before_set-delta
不考虑休眠的情况下，累计所有的delta，得到如下关系。
wtm_current=wtm_org-total_delta 公式（4）
将休眠和修改均考虑在内，有如下关系。
wtm_current=wtm_org-total_sleep_time-total_delta公式（5）
用户修改了系统时间后，系统启动时间也会随之变化。原因很简单，正常逻辑下修改之后的时间比修改之前的要正确。
new_boot_time=old_boot_time+total_delta
结合公式（2）有如下关系。
new_boot_time=-wtm_org+total_delta
结合公式（5）有如下关系。
new_boot_time=-wtm_current-total_sleep_time公式（6）
公式（1）和公式（6）就是内核计算MONOTONIC时间和系统启动时REALTIME时间的原理，getboottime/getboottime64就是利用了公式（6）获得系统启动的时间。
在5.05版的内核中，tk移除了total_sleep_time字段，以offs_real字段表示MONOTONIC与REALTIME之间的差，以offs_boot表示MONOTONIC与BOOTTIME之间的差，getboottime/getboottime64直接使用offs_real-offs_boot，即可达到目的。
BOOTTIME时间：表示系统启动到现在的时间，它也不是绝对时间，与MONOTONIC时间不同的是，BOOTTIME时间会记录系统休眠的时间。
timekeeper为内核实现了几个获取时间的函数，它们为获取不同种类的时间提供了方便，如表3-6所示。上文中BOOTTIME表示时间种类，boot_time表示系统启动时的时间，但内核中并没有把这两个概念很好地区分，请注意区分下面几个BOOTTIME。
表3-6 获取时间的函数表
需要注意的是，MONOTONIC时间也并不是完全单调的，它会受NTP（Network Time Protocol，网络时间协议）的影响，真正不受影响的是RAWMONOTONIC时间。
3.4 周期性和单触发的时钟中断
现代计算机上一般都会包含多种时钟中断设备，它们可以支持周期性和单触发的时钟中断，下文以PIT和APICTimer的组合为例。
TSC的频率是运行时计算得出的，内核启动时会利用PIT得到该值（PIT的频率固定，利用PIT设定时间段，除该时间段内TSC的周期数）。所以PIT会优先工作，调用clockevents_register_device函数注册它的evt。注册过程中会执行tick_check_new_device设置该cpu对应的td，将evt赋值给td的evtdev字段。td的默认状态（mode字段）为TICKDEV_MODE_PERIODIC，这样PIT的evt的event_handler字段被赋值为tick_handle_periodic。这是第一个阶段，系统处于周期性时钟中断模式，即tick阶段。
APIC Timer进入工作（setup_APIC_timer）之后，由于它的rating比PIT高，td的evtdev字段被替换成APIC的evt，此时可以尝试切换至nohz模式。
nohz模式（也可称为tickless模式、oneshot模式、动态时钟模式），主要要求系统当前的cs要有CLOCK_SOURCE_VALID_FOR_HRES标志（timekeeping_valid_for_hres函数）和evt可以满足单触发模式（tick_is_oneshot_available函数）两个条件。条件满足的情况下，内核会切换到nohz模式，进入第二个阶段。所谓的nohz模式是指时钟中断不完全周期性地工作的模式，在该模式下时钟中断的间隔可以动态调整。
nohz模式又分为两种模式：高精度模式和低精度模式。满足nohz条件的情况下，切换到哪个模式由hrtimer_hres_enabled变量的值决定，该值可通过内核启动参数设置。等于0时，调用tick_nohz_switch_to_nohz切换到普通nohz模式，否则调用hrtimer_switch_to_hres切换到高精度模式。
低精度和高精度模式不同点如下。
从字面上理解，后者比前者精度要高，事实也确实如此。低精度模式最高的频率就是HZ，cpu处于非idle的状态下，它一般也是以周期性的方式工作，之所以称之为nohz是因为它的频率可以大于HZ，比如在idle状态下。高精度模式的最高频率由时钟中断设备决定，该特性与hrtimer完美配合（见15.2.3.3），可以满足对时间间隔要求较高的应用场景。
低精度模式下，evt的event_handler字段被赋值为tick_nohz_handler，高精度模式下被赋值为hrtimer_interrupt。
时钟中断发生后，低精度模式的tick_nohz_handler会在函数本体内完成进程时间计算、进程调度等操作；而hrtimer_interrupt只负责去处理到期的hrtimer，进程时间计算、进程调度等操作是通过ts的sched_timer字段表示的hrtimer完成的，tick_sched_timer函数最终负责完成这些操作（见15.2.3.3小节）。
要理解高精度模式，必须对hrtimer有清楚的认识，hrtimer并不同于timer，它们虽然有相似的函数，但hrtimer可以触发对时钟中断设备编程的动作。
3.5 时间相关的系统调用
时间相关的应用程序比比皆是，它们都需要内核的系统调用支持，比如获取当前时间或为某些操作定时。
3.5.1 获取时间
除了前面分析过的gettimeofday和settimeofday系统调用外，内核可能还会实现time和stime系统调用，后面二者都是以秒为单位的，它们的存在也许只是为了向前兼容，程序应该采用前二者。
除此之外，内核还提供了兼容POSIX标准的系统调用clock_gettime和clock_settime等，它们的区别主要在精度上，如表3-7所示。
表3-7 获取设置时间的系统调用表
并不是所有的时间操作都是通过系统调用来完成的，比如更新RTC时间的hwclock命令，它实际上是通过读写文件来实现功能的（如/dev/rtc，内核为RTC提供了一个统一的架构）。
3.5.2 给程序定个闹钟
就像生活中很多时候需要闹钟一样，很多程序也需要定时提醒。
alarm，在早期的平台上作为系统调用，现代平台上基本在C库中调用其他系统调用实现，精度为秒。
setitimer，alarm多数情况下会通过调用setitimer实现，后者是一个系统调用，通过它可以设置一个定时器。getitimer与之对应，用来获得定时器的当前时间。setitimer的精度为微秒，函数原型（用户空间）如下。
第一个参数表示定时器的类型，可以有ITIMER_REAL、ITIMER_VIRTUAL和ITIMER_PROF三种值。该函数不会阻塞当前进程，定时器设置完毕后返回继续执行，到期后内核会发送信号至当前进程。定时器的类型、意义和对应的到期信号的对应关系如表3-8所示。
表3-8 定时器类型和信号表
每一种类型的定时器相互独立，但对一个进程而言，同一时刻、同一种定时器只能存在一个；如果还有同类定时器未执行，重新调用该函数会将原定时器取消。
setitimer与alarm相似，需要配合信号机制使用，示例代码如下。
itimerval结构体的it_value字段表示第一次运行定时器的时间（相对时间）；it_interval字段表示循环运行定时器的时间间隔，为0表示不自动重新启动定时器。
timer_create族，精度为纳秒，时间到期依然是通过信号告知进程，函数原型（用户空间）如下。
第一个参数表示时钟类型，POSIX协议共定义了超过10个合法值，但并不是每一个都被内核支持，CLOCK_REALTIME是必定会支持的，如果内核支持MonotonicClock，那么CLOCK_MONOTONIC也会被支持。evp为sigevent结构体指针，timerid用于保存创建成功的定时器的id。与setitimer不同的是，使用timer_create同一时刻同一种定时器可以有多个，每个定时器都以它们的id区分。本质上，setitimer创建的定时器对进程而言是全局的，内核不会在每次调用setitimer的时候去创建一个新的定时器；timer_create会触发创建新定时器的动作，内核维护定时器的链表，有效的id是用户使用定时器的唯一方式。
操作成功，返回0，定时器的id存入timerid变量中，否则返回非0值，timerid的值无意义。定时器创建成功后，就可以利用它的id使用了，如表3-9所示。
表3-9 timer_create函数族表
与setitimer相同，timer_settime也可以设置定时器到期后自动重新计时。同一个定时器，到期的时候，有可能它上次到期时产生的信号还处在挂起状态，那么信号可能会丢失，timer_getoverrun就是计算这类事件发生的次数的。
timer_create看似功能比setitimer强大，但同时也多了管理新建定时器的操作，所以本着够用即可的原则，除非setitimer不能满足应用场景要求，才会选择前者。
3.6 实例分析
时间是系统的节拍，也是很多机制的基础，我们需要掌握内核计算、维护时间以及时钟中断的原理。
3.6.1 实现智能手机的长按操作
我们在手机主界面上操作时，滑动可以翻页，长按可以进入应用编辑状态，进行文件夹创建或应用删除等操作。那么手机操作系统是如何区分滑动和长按的呢？有时我们尝试长按进行应用编辑却失败的原因是什么呢？
首先，滑动和长按的区别在于手指移动的距离。以手指触摸屏幕的第一个点作为起点，后续的点中只要任何一个点和它的距离超过了阈值，就会被认为是滑动。所以尝试长按的时候，手指的抖动也可能导致失败。
其次，长按有时间的设定，比如0.5秒。如果在0.5秒内手指抬起，会被视为点击，达到0.5秒才会被认为是长按。
从代码角度，0.5秒是如何实现的呢？手指按下得到第一个点时，应用发送一个0.5秒后启动长按事件的请求，事件启动前如果手指抬起或者滑动距离超过阈值，发送取消事件的请求。0.5秒时间内如果没有取消，长按触发。
所以，处理事件请求的模块需要有计时功能，有两种实现方法，一种是不断读取当前时间，另外一种是使用定时器等。
3.6.2 系统的时间并不如你所想
读者可以做一个实验，当我们把同步网络时间功能关闭，系统时间与真实时间的误差会越来越大。
这是由我们选择的时钟导致的，选择时钟时优先考虑的是精度，也就是可以测量的最小时间，优点是可以快速响应时间精度要求高的请求。
系统中的RT C时钟与真实时间接近，但它的精度不够，往往都不会被选中，所以时间误差会越来越大。
另外一个有误差的时间是睡眠，睡眠的过程主要包括让出CPU、重新可执行和被执行三步。前两步之间的时间是实际的睡眠时间，后两步之间的时间是不固定的。进程被唤醒后，当前CPU可能在执行其他进程，其他进程执行完毕后可能还有其他优先级更高的进程需要执行。所以从调用sleep到函数返回，除了实际的睡眠时间，还包括进程调度时间，也是有误差的。