第 1 部分: Linux 应用层的时间编程

引子

    我们都生活在时间中，但却无法去思考它。什么是时间呢？ 似乎这是一个永远也不能被回答的问题。然而作为一个程序员，在工作中，总有那么几次我必须思考什么是时间。 比如，需要知道一段代码运行了多久；要在 log 文件中记录事件发生时的时间戳； 再比如需要一个定时器以便能够定期做某些计算机操作。我发现，在计算机世界中， 时间在不同场合也往往有不同的含义，让试图思考它的人感到迷茫。但值得庆幸的是， Linux 中的时间终究是可以理解的。因此我打算讨论一下有关时间的话题，尝试着深入理解 Linux 系统中 C 语言编程中的时间问题。主要内容如下：

• 第 1 部分是应用程序中的时间问题。有三个方面：程序计时需要；获取当前时间；定时器。
• 第 2 部分包括时间硬件简介和 GlibC 实现时间函数的原理。
• 第 3 和第 4 部分是 Linux 内核对时间的支持和实现原理。

现在开始第 1 部分，探讨应用开发中的时间编程问题。在这一部分中，所有的例子代码都在 GlibC 2.14， 内核 2.6.33 的 Linux 系统下编译并验证执行过。读者如果使用低版本的 GlibC 和 Linux 内核有可能无法正确执行。

获取当前时间

时间的获取

在程序当中, 我们经常要输出系统当前的时间，比如日志文件中的每一个事件都要记录其产生时间。 在 C 语言中获取当前时间的方法有以下几种，它们所获得的时间精度从秒级到纳秒，各有所不同。

表 1. C 时间函数

function | 定义 | 含义 | 返回值 | 精度 —– | —– | —– | —– | —–
time() | time 函数获得从 1970 年 1 月 1 日 0 点到当前的秒数，存储在time_t结构之中。 | time_t | 秒 gettimeofday() | gettimeofday 函数返回从 1970 年 1 月 1 日 0 点以来，到现在的时间。用 timeval 数据结构表示。 | struct timeval { time_t tv_sec; long int tv_usec; }; | 微秒 clock_gettime() | clock_gettime 函数返回从 1970 年 1 月 1 日 0 点以来，到现在的时间。用 timespec 数据结构表示。 支持不广泛。属于实时扩展。| struct timespec { time_t tv_sec; long int tv_nsec; }; | 纳秒 ftime() | 函数返回从 1970 年 1 月 1 日 0 点以来，到现在的时间。用timeb数据结构表示。 已经过时, 被 time() 替代。尽量不使用。 | struct timeb { time_t time; unsigned short millitm; short timezone; short dstflag; }; | 毫秒

GUN/Linux 提供了三个标准的 API 用来获取当前时间，time()/gettimeofday()/clock_gettime()， 它们的区别仅在于获取的时间精度不同，您可以根据需要选取合适的调用。ftime() 是老的一些系统中的时间调用， 很多 Linux 版本虽然支持它，但仅仅是为了向前兼容性，新开发的软件不建议使用 ftime() 来获得当前时间。

时间显示和转换

目前我们得到的时间是一个数字，无论精度如何，它代表的仅是一个差值。比如精度为秒的 time() 函数， 返回一个 time_t 类型的整数。假设当前时间为 2011 年 12 月 7 日下午 20 点 29 分 51 秒， 那么 time_t 的值为：1323318591。即距离 1970 年 1 月 1 日零点，我们已经过去了 1323318591 秒。 （这里的 1970 年 1 月 1 日零点是格林威治时间，而不是北京时间。）我们下面讨论的时间如果不特别 说明都是格林威治时间，也叫 GMT 时间，或者 UTC 时间。

字符串“1323318591 秒”对于多数人都没有太大的意义，我们更愿意看到“2011 年 12 月 7 日”这样的显示。 因此当我们得到秒，毫秒，甚至纳秒表示的当前时间之后，往往需要将这些数字转换为人们所熟悉的时间表示方法。

由于国家，习惯和时区的不同，时间的表示方法并没有一个统一的格式。为了满足各种时间显示的需求， 标准 C 库提供了许多时间格式转换的函数。这些函数的数量众多，容易让人迷惑，记住它们的用法十分不易。 在这里我借用 Michael Kerrisk 在《Linux Programming Interface》一书中的插图，来对这些标准 C 函数进行一个总体的概览。

图 1. 各种时间显示格式转换函数关系图

图 1. 各种时间显示格式转换函数关系图

从上图可以看到，time()/gettimeofday() 从内核得到当前时间之后，该当前时间值可以被两大类函数转换为更加容易阅读的显示格式：

• 固定格式转换
• 用户指定格式转换函数。

固定格式转换 用 ctime() 函数转换出来的时间格式是系统固定的，调用者无法改动，因此被称为固定格式转换。 如果您对日期格式没有特殊的要求，那么用它基本上就可以了，简单，不用记忆很多的参数。

典型的 ctime() 格式如下： Wed Dec 7 20:45:43 PST 2011

用户指定格式转换

有些人觉得这个格式太长，类似 Wed，星期三这样的信息很多情况下都没有啥用途。人们可能更喜欢其他格式： 比如2011-12-07 20:45。在这种情况下，就需要进行时间显示格式转换。做法为： 先把从内核得到的时间值转换为 struct tm 类型的值，然后调用 strftime() 等函数来输出自定义的时间格式字符串。

下面我列举一些实例，以便读者更清晰地理解众多的时间转换函数的用法。

各标准 C 时间转换函数的解释和举例

char *ctime(const time_t *clock);

使用函数 ctime 将秒数转化为字符串. 这个函数的返回类型是固定的： 一个可能值为”Thu Dec 7 14:58:59 2000”。这个字符串的长度和显示格式是固定的。

清单 1，time 的使用

#include <time.h>
int main ()
{
 time_t time_raw_format;
 time ( &time_raw_format ); //获取当前时间
 printf (" time is [%d]\n", time_raw_format);
 //用 ctime 将时间转换为字符串输出
 printf ( "The current local time: %s", ctime(&time_raw_format));
 return 0;
}

自定义格式转换

为了更灵活的显示，需要把类型 time_t 转换为 tm 数据结构。tm 数据结构将时间分别保存到 代表年，月，日，时，分，秒等不同的变量中。不再是一个令人费解的 64 位整数了。 这种数据结构是各种自定义格式转换函数所需要的输入形式。

清单 2，数据结构 tm

struct tm {
int tm_sec; /* Seconds (0-60) */
int tm_min; /* Minutes (0-59) */
int tm_hour; /* Hours (0-23) */
int tm_mday; /* Day of the month (1-31) */
int tm_mon; /* Month (0-11) */
int tm_year; /* Year since 1900 */
int tm_wday; /* Day of the week (Sunday = 0)*/
int tm_yday; /* Day in the year (0-365; 1 Jan = 0)*/
int tm_isdst; /* Daylight saving time flag
 > 0: DST is in effect;
 = 0: DST is not effect;
 < 0: DST information not available */
};

可以使用 gmtime() 和 localtime() 把 time_t 转换为 tm 数据格式， 其中 gmtime() 把时间转换为格林威治时间；localtime 则转换为当地时间。

清单 3，时间转换函数定义

#include <time.h>
struct tm *gmtime(const time_t *timep);
struct tm *localtime(const time_t *timep);

使用 tm 来表示时间，您就可以调用 asctime() 和 strftime() 将时间转换为字符串了。asctime() 的输出格式固定， 和 ctime() 相同。strftime() 则类似我们最熟悉的 printf() 函数，您可以通过输入参数自定义时间的输出格式。

size_t strftime(char *outstr, size_t maxsize, const char *format,
            const struct tm *timeptr);

清单 4，时间显示转换

int main ()
{
    time_t time_raw_format;
    struct tm * time_struct;
    char buf [100];
    time ( &time_raw_format );
    time_struct = localtime ( &time_raw_format );
    strftime (buf,100,"It is now: %I:%M%p.",time_struct);
    puts (buf);
    return 0;
}

该例子程序的输出结果如下：

It is now: 02:45PM.

从以上的例子可以看到，利用从 time() 得到的时间值，可以调用各种转换函数将其转换成更方便人们阅读的形式。

此外从前面的总结中我们也了解到，还有两个 C 函数可以获得当前时间，gettimeofday() 以及 clock_gettime()， 它们分别返回 struct timeval 或者 timespec 代表的高精度的时间值。在目前的 GLibC 中，还没有直接把 struct timeval/timespec 转换为 struct tm 的函数。一般的做法是将 timeval 中的 tv_sec 转换为 tm， 使用上面所述的方法转换为字符串，最后在显示的时候追加上 tv_usec，比如下面的例子代码：

清单 5，更多时间显示转换

struct timeval tv;
time_t nowtime; 
struct tm *nowtm; 
char tmbuf[64], buf[64]; 
gettimeofday(&tv, NULL); //获取当前时间到 tv
nowtime = tv.tv_sec; //nowtime 存储了秒级的时间值
nowtm = localtime(&nowtime); //转换为 tm 数据结构
//用 strftime 函数将 tv 转换为字符串，但 strftime 函数只能达到秒级精度
strftime(tmbuf, sizeof tmbuf, "%Y-%m-%d %H:%M:%S", nowtm);
//将毫秒值追加到 strftime 转换的字符串末尾 
snprintf(buf, sizeof buf, "%s.%06d", tmbuf, tv.tv_usec);

时间的测量

有时候我们要计算某段程序执行的时间，比如需要对算法进行时间分析。基本的实现思路为在被测试代码的 开始和结束的地方获取当时时间，相减后得到相对值，即所需要的统计时间。为了实现高精度的时间测量， 必须使用高精度的时间获取方式，一般有两种方法：

• 系统调用 gettimeofday
• 汇编指令 RDTSC。

##gettimeofday

可以使用 gettimeofday() 函数进行时间测量，其精度在 us 级别，可以用来做一般的时间分析。

gettimeofday() 将时间保存在结构 tv 之中。gettimeofday() 的第二个参数代表时区， 在 Linux 中已经废弃不用，只能用 NULL 传入。一个典型的例子程序如下：

清单 6，gettimeofday 例子程序

void function() 
{ 
 unsigned int i,j; 
 double y; 
 for(i=0;i<1000;i++) 
 for(j=0;j<1000;j++) 
 y=sin((double)i); //耗时操作
} 
 
main() 
{ 
 struct timeval tpstart,tpend; 
 float timeuse; 
 
 gettimeofday(&tpstart,NULL); //记录开始时间戳
 function(); 
 gettimeofday(&tpend,NULL); //记录结束时间戳
 timeuse = 1000000*(tpend.tv_sec-tpstart.tv_sec)+ 
tpend.tv_usec-tpstart.tv_usec; //计算差值
 timeuse /= 1000000; 
 printf("Used Time:%f\n",timeuse); 
 exit(0); 
}

这个程序输出函数的执行时间，我们可以使用这个来进行系统性能的测试，或者是函数算法的效率分析。 在我个人机器上的输出结果是：Used Time:0.556070

##RDTSC

gettimeofday() 是一个系统调用，在某些场合下频繁调用它是不合适的。比如性能要求很高的代码段内。 因为 gettimeofday() 需要用户态/内核态切换，开销较大。Intel X86 处理器提供了 TSC 硬件， 并且可以用非特权指令 rdtsc 来读取该硬件的时间值，这就避免了过度的内核用户态切换。

如何使用 RDTSC

参考下面的例子代码，采用 GCC 的汇编扩展，定义 rdtsc 的函数，它返回当前时间戳。

#define rdtsc(low,high) __asm__ \
    __volatile__("rdtsc" : "=a" (low), "=d" (high))

在 C 代码中使用 rdtsc 十分简单。比如：

清单 7，RDTSC 例子程序

unsigned long long get_cycles()
{
    unsigned low, high;
    unsigned long long val;
    rdtsc(low,high);
    val = high;
val = (val << 32) | low; //将 low 和 high 合成一个 64 位值
    return val;
}
 
double get_cpu_mhz(void)
{
    FILE* f;
    char buf[256];
    double mhz = 0.0;
 
f = fopen("/proc/cpuinfo","r"); //打开 proc/cpuinfo 文件
    if (!f)
        return 0.0;
    while(fgets(buf, sizeof(buf), f)) {
        double m;
        int rc;
rc = sscanf(buf, "cpu MHz : %lf", &m); //读取 cpu MHz
        if (mhz == 0.0) {
            mhz = m;
            break;
        }
    }
    fclose(f);
return mhz; //返回 HZ 值
}
 
int main()
{
    double mhz;
    mhz = get_cpu_mhz();
    cycles_t c1, c2;
 
    for(;;)
    {
        c1 = get_cycles(); 
        sleep(1);
        c2 = get_cycles();
 //c2 和 c1 的差值应该为 1000000us，即 1 秒
        printf("1 sec = %g usec\n", (c2 - c1) / mhz); 
    }
}

函数 get_cycles 将返回 64 位整数，代表当前时间，单位是 CPU 的 cycle 数。 函数 get_cpu_mhz 获得当前 CPU 的工作频率。用两个 CPU cycle 的差值除以 CPU 频率，就是微妙。

但 RDTSC 只能在 IA 系列处理器上使用。而且由于处理器的乱序执行，RDTSC 有些情况下并不准确， 在 SMP 下使用 RDTSC 也有一定的问题。但这些问题只有在需要极高时间精度的情况下才会出现，对于一般的时间测量要求， 采用 RDTSC 是一个可以考虑的选择。

计时器的使用

有时我们需要定时完成一些任务。简单的方法是使用 while 循环加 sleep。比如每隔 1 分钟检查链接情况的 heartbeat 任务等。

清单 8，sleep 加循环

while(condtion)
{
 //do something
 sleep(interval);
}

这可以满足很多程序的定时需要，但假如您不希望程序“偷懒”，即上例中 sleep 的时候您还是希望程序做些有用的工作， 那么使用定时器是通常的选择。Linux 系统上最常用的定时器是 setitmer 计时器。

setitimer

Linux 为每一个进程提供了 3 个 setitimer 间隔计时器：

• ITIMER_REAL：减少实际时间，到期的时候发出 SIGALRM 信号。
• ITIMER_VIRTUAL：减少有效时间 (进程执行的时间)，产生 SIGVTALRM 信号。
• ITIMER_PROF：减少进程的有效时间和系统时间 (为进程调度用的时间)。这个经常和上面一个使用用来计算系统内核时间和用户时间。产生 SIGPROF 信号。

所谓 REAL 时间，即我们人类自然感受的时间，英文计算机文档中也经常使用 wall-clock 这个术语。 说白了就是我们通常所说的时间，比如现在是下午 5 点 10 分，那么一分钟的 REAL 时间之后就是下午 5 点 11 分。

VIRTUAL 时间是进程执行的时间，Linux 是一个多用户多任务系统，在过去的 1 分钟内，指定进程实际在 CPU 上的执行时间往往并没有 1 分钟，因为其他进程会被 Linux 调度执行，在那些时间内，虽然自然时间在流逝， 但指定进程并没有真正的运行。VIRTUAL 时间就是指定进程真正的有效执行时间。比如 5 点 10 分开始的 1 分钟内， 进程 P1 被 Linux 调度并占用 CPU 的执行时间为 30 秒，那么 VIRTUAL 时间对于进程 P1 来讲就是 30 秒。 此时自然时间已经到了 5 点 11 分，但从进程 P1 的眼中看来，时间只过了 30 秒。

PROF 时间比较独特，对进程 P1 来说从 5 点 10 分开始的 1 分钟内，虽然自己的执行时间为 30 秒， 但实际上还有 10 秒钟内核是在执行 P1 发起的系统调用，那么这 10 秒钟也被加入到 PROF 时间。 这种时间定义主要用于全面衡量进程的性能，因为在统计程序性能的时候， 10 秒的系统调用时间也应该算到 P1 的头上。这也许就是 PROF 这个名字的来历吧。

使用 setitimer Timer 需要了解下面这些接口 API:

int getitimer(int which,struct itimerval *value); 
int setitimer(int which,struct itimerval *newval, 
struct itimerval *oldval);

itimerval 的定义如下：

struct itimerval { 
struct timeval it_interval; 
struct timeval it_value; 
}

getitimer 函数得到间隔计时器的时间值，保存在 value 中。

setitimer 函数设置间隔计时器的时间值为 newval. 并将旧值保存在 oldval 中；which 表示使用三个计时器中的哪一个。

itimerval 结构中的 it_value 是第一次调用后触发定时器的时间，当这个值递减为 0 时，系统会向进程发出相应的信号。 此后将以 it_internval 为周期定时触发定时器。

给出一个具体的例子：

清单 9，setitmer 例子

void print_info(int signo) 
{ 
 printf(“timer fired\n”); //简单的打印，表示 timer 到期
} 
 
void init_sigaction(void) 
{ 
 struct sigaction act; 
 act.sa_handler= print_info; 
 act.sa_flags=0; 
 sigemptyset(&act.sa_mask); 
 sigaction(SIGPROF,&act,NULL); //设置信号 SIGPROF 的处理函数为 print_info
} 
 
void init_time() 
{ 
 struct itimerval value; 
 value.it_value.tv_sec=2; 
 value.it_value.tv_usec=0; 
 value.it_interval=value.it_value; 
 setitimer(ITIMER_PROF,&value,NULL); //初始化 timer，到期发送 SIGPROF 信号
} 
 
int main() 
{ 
// len=strlen(prompt); 
 init_sigaction(); 
 init_time(); 
 while(1); 
 exit(0); 
}

这个程序使用 PROF 时间，每经过两秒 PROF 时间之后就会打印一下 timer fired 字符串。

需要指出：setitimer 计时器的精度为 ms，即 1000 分之 1 秒，足以满足绝大多数应用程序的需要。 但多媒体等应用可能需要更高精度的定时，那么就需要考虑使用下一类定时器：POSIX Timer。

POSIX Timer

间隔定时器 setitimer 有一些重要的缺点，POSIX Timer 对 setitimer 进行了增强，克服了 setitimer 的诸多问题：

首先，一个进程同一时刻只能有一个 timer。假如应用需要同时维护多个 Interval 不同的计时器，必须自己写代码来维护。 这非常不方便。使用 POSIX Timer，一个进程可以创建任意多个 Timer。

setitmer 计时器时间到达时，只能使用信号方式通知使用 timer 的进程，而 POSIX timer 可以有多种通知方式，比如信号，或者启动线程。

使用 setitimer 时，通知信号的类别不能改变：SIGALARM，SIGPROF 等，而这些都是传统信号，而不是实时信号， 因此有 timer overrun 的问题；而 POSIX Timer 则可以使用实时信号。

setimer 的精度是 ms，POSIX Timer 是针对有实时要求的应用所设计的，接口支持 ns 级别的时钟精度。

表 2. POSIX Timer 函数

使用 Posix Timer 的基本流程很简单，首先创建一个 Timer。创建的时候可以指定该 Timer 的一些特性，比如 clock ID。

clock ID 即 Timer 的种类，可以为下表中的任意一种：

表 3. POSIX Timer clock ID

CLOCK_REALTIME 时间是系统保存的时间，即可以由 date 命令显示的时间，该时间可以重新设置。 比如当前时间为上午 10 点 10 分，Timer 打算在 10 分钟后到时。假如 5 分钟后， 我用 date 命令修改当前时间为 10 点 10 分，那么 Timer 还会再等十分钟到期，因此实际上 Timer 等待了 15 分钟。 假如您希望无论任何人如何修改系统时间，Timer 都严格按照 10 分钟的周期进行触发，那么就可以使用 CLOCK_MONOTONIC。

CLOCK_PROCESS_CPUTIME_ID 的含义与 setitimer 的 ITIMER_VIRTUAL 类似。计时器只记录 当前进程所实际花费的时间；比如还是上面的例子，假设系统非常繁忙，当前进程只能获得 50%的 CPU 时间， 为了让进程真正地运行 10 分钟，应该到 10 点 30 分才允许 Timer 到期。

CLOCK_THREAD_CPUTIME_ID 以线程为计时实体，当前进程中的某个线程真正地运行了一定时间才触发 Timer。

设置到期通知方式

timer_create 的第二个参数 struct sigevent 用来设置定时器到时时的通知方式。该数据结构如下：

清单 10，结构 sigevent

struct sigevent {
    int sigev_notify; /* Notification method */
    int sigev_signo; /* Notification signal */
    union sigval sigev_value; /* Data passed with notification */
    void (*sigev_notify_function) (union sigval);
    /* Function used for thread
    notification (SIGEV_THREAD) */
    void *sigev_notify_attributes;
    /* Attributes for notification thread (SIGEV_THREAD) */
    pid_t sigev_notify_thread_id;
    /* ID of thread to signal (SIGEV_THREAD_ID) */
};

其中 sigev_notify 表示通知方式，有如下几种：

表 3. POSIX Timer 到期通知方式

如果采用 SIGEV_NONE 方式，使用者必须调用timer_gettime 函数主动读取定时器已经走过的时间。类似轮询。

如果采用 SIGEV_SIGNAL 方式，使用者可以选择使用什么信号，用 sigev_signo 表示信号值，比如 SIG_ALARM。

如果使用 SIGEV_THREAD 方式，则需要设置 sigev_notify_function，当 Timer 到期时， 将使用该函数作为入口启动一个线程来处理信号；sigev_value 保存了传入 sigev_notify_function 的参数。 sigev_notify_attributes 如果非空，则应该是一个指向 pthread_attr_t 的指针， 用来设置线程的属性（比如 stack 大小,detach 状态等）。

SIGEV_THREAD_ID 通常和 SIGEV_SIGNAL 联合使用，这样当 Timer 到期时，系统会向由 sigev_notify_thread_id 指定的线程发送信号，否则可能进程中的任意线程都可能收到该信号。这个选项是 Linux 对 POSIX 标准的扩展， 目前主要是 GLibc 在实现 SIGEV_THREAD 的时候使用到，应用程序很少会需要用到这种模式。

启动定时器

创建 Timer 之后，便可以调用 timer_settime() 函数指定定时器的时间间隔，并启动该定时器了。

int timer_settime(timer_t timerid, int flags,
    const struct itimerspec *new_value,
    struct itimerspec * old_value);

第一次看到 timer_settime 的参数列表或许会令人觉得费解。先来看看 new_value 和 old_value， 它们都是 struct itimerspec 数据结构。

struct itimerspec
{
 struct timespec it_interval; //定时器周期值
 struct timespec it_value; //定时器到期值
};

启动和停止 Timer 都可以通过设置 new_value 来实现：

new_value->it_interval 为定时器的周期值，比如 1 秒，表示定时器每隔 1 秒到期；

new_value->it_value 如果大于 0，表示启动定时器，Timer 将在 it_value 这么长的时间过去后到期， 此后每隔 it_interval 便到期一次。如果 it_value 为 0，表示停止该 Timer。

有些时候，应用程序会先启动用一个时间间隔启动定时器，随后又修改该定时器的时间间隔， 这都可以通过修改 new_value 来实现；假如应用程序在修改了时间间隔之后希望了解之前的时间间隔设置， 则传入一个非 NULL 的 old_value 指针，这样在 timer_settime() 调用返回时，old_value 就保存了上一次 Timer 的时间间隔设置。多数情况下我们并不需要这样，便可以简单地将 old_value 设置为 NULL，忽略它。

下面给出一个使用 posix timer 的例子程序。最传统的例子就是创建通知方式为 SIGEV_SIGNAL 的 Timer。 这样当定时器到期时，将产生信号通知，主程序需要定义自己的信号处理函数，来处理信号到期事件。 这种例子比比皆是，我打算在这里写一个采用通知方式为 SIGEV_THREAD 的例子。该例子程序从 main 函数开始主线程，在开始的时候打印出主线程的进程 ID 和线程 ID。

清单 11，打印 TID

pid_t tid = (pid_t) syscall (SYS_gettid);
printf("start program in PID:[%d]TID:[%d]\n",getpid(),tid);

获得 ThreadID 的系统调用尚未被 GLibC 标准化，因此这里直接调用 syscall。

然后，主线程初始化创建 Timer 所需要的数据结构：

清单 12，设置通知方式

se.sigev_notify = SIGEV_THREAD;
se.sigev_value.sival_ptr = &timer_id;
se.sigev_notify_function = timer_thread;
se.sigev_notify_attributes = NULL;
status = timer_create(CLOCK_REALTIME, &se, &timer_id);

这里将通知方式设为 SIGEV_THREAD，timer_thread 为线程入口函数。

然后主线程设置定时器间隔，并启动 Timer：

清单 13，启动 Timer

ts.it_value.tv_sec = 5;
ts.it_value.tv_nsec = 0;
ts.it_interval.tv_sec = 5;
ts.it_interval.tv_nsec = 0;
status = timer_settime(timer_id, 0, &ts, 0);

此后主线程进入一个循环，在循环中等待线程条件变量：

清单 14，主程序中的循环

while (counter < 5) {
 status = pthread_cond_wait (&cond, &mutex);
}

条件变量 cond 将在 timer_thread() 处理函数中触发，这样每 5 秒钟，定时器将调用 timer_thread() 处理函数，并唤醒主线程等待的条件变量一次。5 次之后测试程序退出。

现在我们看看 timer_thread() 函数：

清单 15，timer_thread 函数

void timer_thread (void *arg)
{
 status = pthread_mutex_lock (&mutex);
 if (++counter >= 5) {
 status = pthread_cond_signal (&cond);
 }
 status = pthread_mutex_unlock (&mutex);
 pid_t tid = (pid_t) syscall (SYS_gettid);
 printf ("Timer %d in PID:[%d]TID:[%d]\n", counter,getpid(),tid);
}

在整个程序中我们都没有使用信号，定时器到期时，将启动新的线程运行 timer_thread。因此在该函数中， 我们还打印了当前的线程号以便可以看出它们确实在不同线程中运行。

这里是运行该程序的一个输出：

-bash-3.2$ gcc threadtimer.c -lrt -lpthread -o test
-bash-3.2$ ./test
start program in PID:[21483]TID:[21483]
Timer 1 in PID:[21483]TID:[21498]
Timer 2 in PID:[21483]TID:[21510]
Timer 3 in PID:[21483]TID:[21534]

可以看到每次 Timer 都运行在不同的线程中。

小结

至此，希望我已经讲述了 Linux 系统提供的大多数关于时间的编程方法。使用这些方法我们可以：

• 获得当前时间，并转换为合适的显示方式；
• 衡量程序运行经过的时间；
• 使用定时器完成周期性的任务；

另外不知道您是否和我一样，对于 Linux 系统如何实现这些机制十分好奇。计算机毕竟是一个机器， 底层硬件提供了怎样的功能，操作系统和 C 库如何协同工作才可以提供这些一丝不苟的，优美的方法呢？ 我将在后续的部分试图探讨这个话题。

硬件和 GLibC 库的细节

引子

熟悉了基本的编程方法之后，我们的兴趣就在于，计算机如何实现这一切的呢？在那些应用层 API 和底层系统硬件之间，操作系统和库函数究竟做了些什么？

首先看下 Linux 时间处理的一般过程：

图 1. 时间处理过程

时间处理过程

应用程序部分已经在第一部分详细介绍过了，在第二部分我将介绍硬件和 GlibC 相关实现的一些概况。

硬件

PC 机里常见的时钟硬件有以下这些。

RTC (Real Time Clock，实时时钟)

人们需要知道时间的时候，可以看看钟表。计算机系统中钟表类似的硬件就是外部时钟。它依靠主板上的电池， 在系统断电的情况下，也能维持时钟的准确性。计算机需要知道时间的时候，就需要读取该时钟。

在 x86 体系中，这个时钟一般被称为 Real Time Clock。RTC 是主板上的一个 CMOS 芯片， 比如 Motorola 146818，该芯片独立于 CPU 和其他芯片，可以通过 0x70 和 0x71 端口操作 RTC。 RTC 可以周期性地在 IRQ 8 上触发中断，但精度很低，从 2HZ 到 8192HZ

以 Motorola 146818 为例，软件可以通过 I/O 指令读写以下这些值：

图 2. Motorola 146818

Motorola 146818

可以看到，RTC 能提供精确到秒的实时时间值。

TSC (Time Stamp Counter）

CPU 执行指令需要一个外部振荡器产生时钟信号，从 CLK 管脚输入。x86 提供了一个 TSC 寄存器， 该寄存器的值在每次收到一个时钟信号时加一。比如 CPU 的主频为 1GHZ，则每一秒时间内， TSC 寄存器的值将增加 1G 次，或者说每一个纳秒加一次。x86 还提供了 rtdsc 指令来读取该值， 因此 TSC 也可以作为时钟设备。TSC 提供了比 RTC 更高精度的时间，即纳秒级的时间精度。

PIT (Programmable Interval Timer)

PIT 是 Programmable Interval Timer 的缩写，该硬件设备能定时产生中断。早期的 PIT 设备是 8254， 现在多数可以集成在 Intel 的 I/O Control Hub 电路中，可以通过端口 0x40~0x43 访问 PIT。 系统利用 PIT 来产生周期性的时钟中断，时钟中断通过 8259A 的 IRQ0 向 CPU 报告。它的精度不高， 其入口 clock 的频率为 1MHz，理论上能产生的最高时钟频率略小于 0.5MHz。实际系统往往使用 100 或者 1000Hz 的 PIT。

HPET (High Precision Event Timer)

PIT 的精度较低，HPET 被设计来替代 PIT 提供高精度时钟中断（至少 10MHz）。它是由微软和 Intel 联合开发的。 一个 HPET 包括了一个固定频率的数值增加的计数器以及 3 到 32 个独立的计时器，这每一个计时器有包涵了一个 比较器和一个寄存器（保存一个数值，表示触发中断的时机）。每一个比较器都比较计数器中的数值和寄存器中的数值， 当这两个数值相等时，将产生一个中断。

APIC Timer (Advanced Programmable Interrupt Controller Timer)

APIC (“Advanced Programmable Interrupt Controller”) 是早期 PIC 中断控制器的升级，主要用于多处理器系统， 用来支持复杂的中断控制以及多 CPU 之间的中断传递。APIC Timer 集成在 APIC 芯片中，用来提供高精度的定时中断， 中断频率至少可以达到总线频率。系统中的每个 CPU 上都有一个 APIC Timer，而 PIT 则是由系统中所有的 CPU 共享的。Per CPU 的 Timer 简化了系统设计，目前 APIC Timer 已经集成到了所有 Intel x86 处理器中。

以上这些硬件仅仅是 x86 体系结构下常见的时间相关硬件，其他的体系结构如 mips、arm 等还有它们常用的硬件。 这么多的硬件令人眼花缭乱，但其实无论这些硬件多么复杂，Linux 内核只需要两种功能：

• 一是定时触发中断的功能；
• 另一个是维护和读取当前时间的能力。

一些硬件提供了中断功能，一些硬件提供了读取时间的功能，还有一些硬件则能够提供两种功能。 下表对上面描述过的硬件进行了一个简单的总结：

表 1. 时钟硬件汇总表

也许您已经发现，这些硬件提供的功能非常简单，为了满足应用程序的各种各样的需求，Linux 内核和 C 标准库还需要做很多工作，才能让我们使用诸如 gettimeofday()、setitimer() 等函数进行时间相关的操作。

C 库函数的工作

我们在第一部分已经详细介绍了标准 C 库中关于时间函数的用法。表 2 罗列了一些主要的 API。

表 2. 应用层时间 API 分类

本文力图简短，无法对上表中的每一个 API 进行详细分析。幸运的是，我们只需要研究几个典型 API 的实现， 便可以举一反三，了解其他 API 的大致实现思想。

time() 的实现

第一个典型 API 是 time()，我们参考 GlibC2.13 版本的实现。

清单 1.time 的 GlibC 实现

time_t time (time_t *t)
{
 INTERNAL_SYSCALL_DECL (err);
 time_t res = INTERNAL_SYSCALL (time, err, 1, NULL);//系统调用
 return res;
}

可以看到，GlibC 的 time() 函数只是调用了 time 系统调用，来返回时间值。同样，如果我们查看 gettimeofday() 等很多 API，将会发现它们也是仅仅调用了 Linux 的系统调用来完成指定的功能。 根据我的分析，下面这些函数都是直接调用了 Linux 的系统调用来完成工作：

表 3. 时间 API 及其系统调用

ftime() 的实现

ftime() 在 Glibc 中的代码实现在 sysdeps/unix/bsd/ftime.c，因为在 Linux 系统中 ftime 系统调用已经过时了， 目前如果还有调用 ftime() 的应用程序 GLibc 将用 gettimeofday() 来模拟，具体代码如下：

清单 2，ftime 的 GlibC 实现

int ftime (timebuf)
 struct timeb *timebuf;
{
 struct timeval tv;
 struct timezone tz;
 
 if (__gettimeofday (&tv, &tz) < 0) //调用 gettimeofday
 return -1;
 
 timebuf->time = tv.tv_sec;
 timebuf->millitm = (tv.tv_usec + 500) / 1000;
 if (timebuf->millitm == 1000) {
 ++timebuf->time;
 timebuf->millitm = 0; }
 timebuf->timezone = tz.tz_minuteswest;
 timebuf->dstflag = tz.tz_dsttime;
 return 0;
}

timer_create() 的实现

多数 GLibC 中的时间函数只是对系统调用的简单封装，不过 timer_create 要算是一个特例， 虽然它的大部分功能都是通过系统调用 sys_timer_create 完成的。但是如果 GlibC 发现 timer 的到期通知方式被设置为 SIGEV_THREAD 时，Glibc 需要自己完成一些辅助工作，因为内核无法在 Timer 到期时启动一个新的线程。

考察文件 nptl\sysdeps\unix\sysv\linux\timer_create.c，可以看到 GLibc 发现用户需要启动新线程通知时， 会自动调用 pthread_once 启动一个辅助线程（__start_helper_thread），用 sigev_notify_attributes 中指定的属性设置该辅助线程。

然后 Glibc 启动一个普通的 POSIX Timer，将其通知方式设置为：SIGEV_SIGNAL | SIGEV_THREAD_ID。 这样就可以保证内核在 timer 到期时通知辅助线程。通知的 Signal 号为 SIGTIMER，并且携带一个包含了 到期函数指针的数据。这样，当该辅助 Timer 到期时，内核会通过 SIGTIMER 通知辅助线程，辅助线程可以在 信号携带的数据中得到用户设定的到期处理函数指针，利用该指针，辅助线程调用 pthread_create() 创建一个新的线程来调用该处理函数。这样就实现了 POSIX 的定义。

综上所述，除了少数 API(比如 timer_create），需要 GLibC 做部分辅助工作之外， 大部分 GLibC API 的工作可以总结为：调用相应的系统调用。

ctime() 的实现

还有一些 API 我们还没有分析，即那些时间格式转换函数。这些函数的功能是将一个时间值转换 为人类容易阅读的形式，因此这些函数的实现完全是在 GlibC 中完成，而无需内核的系统调用。下面我们看一看 ctime() 吧：

清单 3，ctime 的 GlibC 实现

char * ctime (const time_t *t)
    { return asctime (localtime (t));}

localtime() 和 asctime() 的实现都比较复杂，但归根结底是进行复杂的格式转换，时区转换计算等等。 这些工作都是完全在 GlibC 内部实现的，无须内核参与。感兴趣的读者可以仔细研究 Glibc time 目录下的 localtime.c、tzset.c 等具体实现。

小结

在这一部分中，我们首先了解到了一些硬件时钟设备的简单知识。无论这些设备本身如何复杂和不同， 它们只提供两个主要功能：计时功能和定时中断功能。要想利用这两个基本功能来满足应用的需求似乎 还有很多工作，比如：如何衡量实时时间和 CPU 时间？

通过对 GlibC 的简单分析，我们也看到库函数实际上把复杂问题统统交给了内核。GlibC 仅仅是一个中转站， 把用户请求发给内核。因此想了解更多，我们必须进入内核。

在接下来的第三部分和第四部分，我们将介绍 Linux 内核的时间系统。

Linux 内核的工作

引子

时间系统的工作需要软硬件以及操作系统的互相协作，在上一部分，我们已经看到大多数时间函数都依赖 内核系统调用，GlibC 仅仅做了一次请求的转发。因此必须深入内核代码以便了解更多的细节。

内核自身的正常运行也依赖于时钟系统。Linux 是一个典型的分时系统，CPU 时间被分成多个时间片， 这是多任务实现的基础。Linux 内核依赖 tick，即时钟中断来进行分时。

为了满足应用和内核自己的需求，内核时间系统必须提供以下三个基本功能：

• 提供系统 tick 中断（驱动调度器，实现分时）
• 维护系统时间
• 维护软件定时器

目前的 Linux 内核版本为 3.8，其时间系统比较复杂，复杂的原因来自几个方面：

首先 Linux 要支持不同的硬件体系结构和时钟电路，Linux 是一个通用操作系统， 支持平台的多样性导致时间系统必须包含各种各样的硬件处理和驱动代码。

目前的 Linux 内核版本为 3.8，其时间系统比较复杂，复杂的原因来自几个方面：

首先 Linux 要支持不同的硬件体系结构和时钟电路，Linux 是一个通用操作系统，支持平台的多样性导致时间系统 必须包含各种各样的硬件处理和驱动代码。

其次，早期 Linux 的时钟实现采用低精度时钟框架（ms 级别），随着硬件的发展和软件需求的发展， 越来越多的呼声是提高时钟精度（ns 级别）；经过若干年的努力，人们发现无法在早期低精度时钟体系结构上 优雅地扩展高精度时钟。最终，内核采用了两套独立的代码实现，分别对应于高精度和低精度时钟。这使得代码复杂度增加。

最后，来自电源管理的需求进一步增加了时间系统的复杂性。Linux 越来越多地被应用到嵌入式设备， 对节电的要求增加了。当系统 idle 时，CPU 进入节电模式，此时一成不变的时钟中断将频繁地打断 CPU 的睡眠状态，新的时间系统必须改变以应对这种需求，在系统没有任务执行时，停止时钟中断，直到有任务需要执行时再恢复时钟。

以上几点，造成了内核时间系统的复杂性。不过 Linux 内核并不是从一开始就如此复杂，所以还是让我们从头说起吧。

早期的 Linux 时间系统

在 Linux 2.6.16 之前，内核只支持低精度时钟。内核围绕着 tick 时钟来实现所有的时间相关功能。 Tick 是一个定期触发的中断，一般由 PIT (Programmable Interrupt Timer) 提供，大概 10ms 触发一次 (100HZ)， 精度很低。在这个简单体系结构下，内核如何实现三个基本功能？

第一大功能：提供 tick 中断。

以 x86 为例，系统初始化时选择一个能够提供定时中断的设备 (比如 Programmable Interrupt Timer, PIT)， 配置相应的中断处理 IRQ 和相应的处理例程。当硬件设备初始化完成后，便开始定期地产生中断， 这便是 tick 了。非常简单明了，需要强调的是 tick 中断是由硬件直接产生的真实中断，这一点在当前的 内核实现中会改变，我们在第四部分介绍。

第二大功能：维护系统时间。

RTC (Real Time Clock) 有独立的电池供电，始终保存着系统时间。Linux 系统初始化时，读取 RTC，得到当前时间值。

读取 RTC 是一个体系结构相关的操作，对于 x86 机器，定义在 arch\x86\kernel\time.c 中。 可以看到最终的实现函数为 mach_get_cmos_time，它直接读取 RTC 的 CMOS 芯片获得当前时间。 如前所述，RTC 芯片一般都可以直接通过 IO 操作来读取年月日等时间信息。得到存储在 RTC 中的时间值之后， 内核调用 mktime () 将 RTC 值转换为一个距离 Epoch（既 1970 年元旦）的时间值。此后直到下次重新启动， Linux 不会再读取硬件 RTC 了。

虽然内核也可以在每次需要的得到当前时间的时候读取 RTC，但这是一个 IO 调用，性能低下。实际上， 在得到了当前时间后，Linux 系统会立即启动 tick 中断。此后，在每次的时钟中断处理函数内，Linux 更新当前的时间值，并保存在全局变量 xtime 内。比如时钟中断的周期为 10ms，那么每次中断产生， 就将 xtime 加上 10ms。

当应用程序通过 time 系统调用需要获取当前时间时，内核只需要从内存中读取 xtime 并返回即可。 就这样，Linux 内核提供了第二大功能，维护系统时间。

第三大功能：软件定时器

能够提供可编程定时中断的硬件电路都有一个缺点，即同时可以配置的定时器个数有限。但现代 Linux 系统中 需要大量的定时器：内核自己需要使用 timer，比如内核驱动的某些操作需要等待一段给定的时间，或者 TCP 网络协议栈代码会需要大量 timer；内核还需要提供系统调用来支持 setitimer 和 POSIX timer。 这意味着软件定时器的需求数量将大于硬件能够提供的 timer 个数，内核必须依靠软件 timer。

简单的软件 timer 可以通过 timer 链表来实现。需要添加新 timer 时，只需在一个全局的链表中添加一个新的 Timer 元素。 每次 tick 中断来临时，遍历该链表，并触发所有到期的 Timer 即可。但这种做法缺乏可扩展性： 当 Timer 的数量增加时，遍历链表的花销将线形增加。如果将链表排序，则 tick 中断中无须遍历列表， 只需要查看链表头即可，时间为 O(1)，但这又导致创建新的 Timer 的时间复杂度变为 O(n)， 因为将一个元素插入排序列表的时间复杂度为 O（N）。这些都是可行但扩展性有限的算法。在 Linux 尚未 大量被应用到服务器时，系统中的 timer 个数不多，因此这种基于链表的实现还是可行的。

但随着 Linux 开始作为一种服务器操作系统，用来支持网络应用时，需要的 timer 个数剧增。 一些 TCP 实现对于每个连接都需要 2 个 Timer，此外多媒体应用也需要 Timer，总之 timer 的个数达到了需要考虑扩展性的程度。

timer 的三个操作：添加 (add_timer)、删除 (del_timer) 以及到期处理（tick 中断）都对 timer 的精度和延迟有巨大影响，timer 的精度和延迟又对应用有巨大影响。例如，add_timer 的延迟太大， 那么高速 TCP 网络协议就无法实现。为此，从 Linux2.4 开始，内核通过一种被称为时间轮的算法来保证 add_timer()、del_timer() 以及 expire 处理操作的时间复杂度都为 O(1)。

时间轮算法简述

时间轮算法是一种实现软件 timer 的算法，由计算机科学家 George Varghese 等提出，在 NetBSD(一种操作系统) 上实现并替代了早期内核中的 callout 定时器实现。

最原始的时间轮如下图所示。

图 1. 原始的时间轮

原始的时间轮

上图中的轮子有 8 个 bucket，每个 bucket 代表未来的一个时间点。我们可以定义每个 bucket 代表一秒， 那么 bucket [1] 代表的时间点就是“1 秒钟以后”，bucket [8] 代表的时间点为“8 秒之后”。Bucket 存放着一个 timer 链表，链表中的所有 Timer 将在该 bucket 所代表的时间点触发。中间的指针被称为 cursor。这样的一个时间轮工作如下：

加入Timer：如果新 Timer 在时间点 6 到期，它就被加入 bucket[6] 的 timer 链表。 定位 bucket[6] 是一个数组访问的过程，因此这个操作是 O(1) 的。

删除Timer：类似的，删除 Timer 也是 O(1) 的。比如删除一个 6 秒钟后到期的 timer， 直接定位到 bucket[6], 然后在链表中删除一个元素是 O(1) 的。

处理Timer: 处理Timer的逻辑在时钟中断程序中，每次时钟中断产生时，cursor 增加一格， 然后中断处理代码检查 cursor 所指向的 bucket，假如该 bucket 非空，则触发该 bucket 指向的 Timer 链表中的所有 Timer。这个操作也是 O(1) 的。

全都是 O(1) 操作？那这个算法岂不是完美的？可惜不是，我们的这个时间轮有一个限制：新 Timer 的到期时间 必须在 8 秒之内。这显然不能满足实际需要，在 Linux 系统中，我们可以设置精度为 1 个 jiffy 的定时器， 最大的到期时间范围可以达到 (2^32-1/2 ) 个 jiffies(一个很大的值)。如果采用上面这样的时间轮， 我们需要很多个 bucket，需要巨大的内存消耗。这显然是不合理的。

为了减少 bucket 的数量，时间轮算法提供了一个扩展算法，即 Hierarchy 时间轮。 图 1 里面的轮实际上也可以画成一个数组，

图 2. 时间轮的另一种表示

时间轮的另一种表示

Hierarchy 时间轮将单一的 bucket 数组分成了几个不同的数组，每个数组表示不同的时间精度，下图是其基本思路：

图 3. Hierarchy 时间轮

Hierarchy 时间轮

这样的一个分层时间轮有三级，分别表示小时，分钟和秒。在 Hour 数组中，每个 bucket 代表一个小时。 采用原始的时间轮，如果我们要表示一天，且 bucket 精度为 1 秒时，我们需要 246060=86,400 个 bucket；而采用分层时间轮，我们只需要 24+60+60=144 个 bucket。

让我们简单分析下采用这样的数据结构，Timer 的添加/删除/处理操作的复杂度。

添加Timer

根据其到期值，Timer 被放到不同的 bucket 数组中。比如当前时间为 (hour:11, minute:0, second:0)， 我们打算添加一个 15 分钟后到期的 Timer，就应添加到 MINUTE ARRAY 的第 15 个 bucket 中。 这样的一个操作是 O(m) 的，m 在这里等于 3，即 Hierarchy 的层数。

图 4. 添加 15 分钟到期 Timer

添加 15

删除Timer：

Timer 本身有指向 bucket 的指针，因此删除 Timer 是 O(1) 的操作，比如删除我们之前添加的 15 分钟后到期的 Timer， 只需要从该 Timer 的 bucket 指针读取到 MINUTE ARRAY Element 15 的指针，然后从该 List 中删除自己即可。

定时器处理：

每个时钟中断产生时（时钟间隔为 1 秒），将 SECOND ARRAY 的 cursor 加一，假如 SECOND ARRAY 当前 cursor 指向的 bucket 非空，则触发其中的所有 Timer。这个操作是 O(1) 的。

可以看到，添加，删除定时器处理的操作复杂度都很低。

难道 Hierarchy 时间轮完美了？可惜还不是。

为了处理 60 秒之外的那些保存在 MINUTES ARRAY 和 HOUR ARRAY 中的 Timer，时钟中断处理还需要做一些额外的工作： 每当 SECOND ARRAY 处理完毕，即 cursor 又回到 0 时，我们应该将 MINUTE ARRAY 的当前 cursor 加一， 并查看该 cursor 指向的 bucket 是否为空，如果非空，则需要将这些 Timer 移动到前一个 bucket 中。 此外 MINUTE ARRAY 的 bucket[0] 的 Timer 这时候应该都移动到 SECOND ARRAY 中。同样，当 MINUTE ARRAY 的 cursor 重新回到 0 时，我们还需要对 HOUR ARRAY 做类似的处理。这个操作是 O(m) 的，其中 m 是 MINUTE ARRAY 或者 HOUR ARRAY 的 bucket 中时钟的个数。多数情况下 m 远远小于系统中所有 active 的 Timer 个数，但的确，这还是一个费时的操作。

Linux 内核采用的就是 Hierarchy 时间轮算法，Linux 内核中用 jiffies 表示时间而不是时分秒， 因此 Linux 没有采用 Hour/Minutes/Second 来分层，而是将 32bit 的 jiffies 值分成了 5 个部分， 用来索引五个不同的数组（Linux 术语叫做 Timer Vector，简称 TV），分别表示五个不同范围的未来 jiffies 值。

这个时间轮的精度为 1 个 jiffy，或者说一个 tick。每个时钟中断中，Linux 处理 TV1 的当前 bucket 中的 Timer。 当 TV1 处理完（类似 SECOND ARRAY 处理完时），Linux 需要处理 TV2，TV3 等。这个过程叫做 cascades。 TV2 当前 bucket 中的时钟需要从链表中读出，重新插入 TV2；TV2->bucket[0] 里面的 timer 都被插入 TV1。 这个过程和前面描述的时分秒的时间轮时一样的。cascades 操作会引起不确定的延迟，对于高精度时钟来讲，这还是一个致命的缺点。

但时间轮还是所有 Timer 实现的基础，在它的基础上，Linux 提供了间隔 Timer 和 POSIX Timer 供应用程序使用。

动态 Timer、Interval Timer 和 POSIX Timer

早期 Linux 考虑两种定时器：内核自身需要的 timer，也叫做动态定时器；其次是来自用户态的需要, 即 setitimer 定时器， 也叫做间隔定时器。2.5.63 开始支持 POSIX Timer。2.6.16 引入了高精度 hrtimer。本节介绍 hrtimer 出现之前 Linux 内核中动态 Timer，间隔 Timer 和 POSIX Timer 的概念，发展和实现原理。

动态 Timer

动态 timer 由内核自身使用，其实也是其他 Timer 的实现基础。使用动态 Timer 的接口函数有三个：

add_timer() 
del_timer() 
init_timer()

使用时，先调用 init_timer() 初始化一个定时器，指定到期时间和到期处理函数；初始化完成后， 内核代码可以用 add_timer() 启动定时器，或者用 del_timer() 来取消一个已经启动的定时器。

add_timer 采用时间轮算法将定时器加入 per CUP 变量 tvec_bases 中，根据其 expire 时间， 可能被加入 5 个 Timer Vector 之一。此后，tick 中断将根据时间轮算法处理。当本 timer 到期时，触发其处理函数。

动态 Timer 有两个方面的用途：一是内核自己使用，比如某些驱动程序需要定时服务的时候使用它； 二是用来实现用户层 Timer。下面首先讲解间隔 Timer。

间隔 timer

间隔 timer 就是应用程序调用setitimer建立的定时器。

Linux 的间隔 Timer 实现经历了一个简单的发展过程。

Linux2.4 版本内核在进程描述符中有以下这些数据结构，用来实现间隔 timer:

struct timer_list real_timer; 
unsigned long it_real_value, it_prof_value, it_virt_value;
unsigned long it_real_incr, it_prof_incr, it_virt_incr;

real_timer 是一个动态 timer，用于 ITIMER_REAL 时钟。其他的 unsigned long 类型的值分别用来维护 各种时钟的到期时间和到期后的 interval 时间，用 jiffies 值表示。

ITIMER_REAL 是用内核动态 Timer 来实现的，每次创建 ITIMER_REAL 时钟时，内核调用 init_timer 创建一个定时器对象，并用 add_timer 将该定时器添加到系统 Timer 时间轮中，该定时器的到期处理函数 被设定为 it_real_fn()。此函数将向当前进程发送 SIGALRM 信号，并重新调用 add_timer() 重新启动自身。 这样便实现了 ITIMER_REAL 时钟。进程描述符中的 it_real_value 仅用于读取，以便用户通过 /proc 读取时钟信息。

另外两种间隔 Timer 则不能简单地依靠动态 Timer 来实现。因为它们参照的是进程的时间而非实时时间， 因此要依赖进程的时间统计。实现原理如下：

每次时钟中断产生时，内核判断中断触发时进程是否正处于内核态，如果在内核态，则将 it_prof_value 和 it_virt_value 都减一；如果在用户态，则只对 it_prof_value 减一，而 it_virt_value 不变。 当 it_prof_value 为 0 时，对当前进程发送 SIGPROF 信号，并把 it_prof_incr 的值重新填入 it_prof_value， 等待下次到期触发。当 it_virt_value为 0 时，则对当前进程发送 SIGVTALRM 信号，并用it_virt_incr的值重新填充 it_virt_value。这样就实现了 POSIX 对 setitimer 所定义的 ITIMER_VIRTUAL 和 ITIMER_PROF 时钟。

不过这种实现有一个问题：在 Linux 中线程是一个单独的调度实体，即轻量级进程。因此一个进程中的每个线程 都拥有自己的进程描述符。这意味着每个线程都有自己的 it_virt_value 和 it_prof_value。 因此 ITIMER_VIRTUAL，ITIMER_PROF 的计时范围是 per-thread，而 POSIX 规定间隔 Timer 必须是 per-process 的。

比如某进程有 2 个线程，现在建立一个 2 秒到期的 ITIMER_VIRTUAL，假设第一个线程得到了 1 秒的 CPU 时间， 此时线程 2 也得到了 1 秒的 CPU 时间。按照 POSIX 标准，此时定时器应该到期。但是根据我们前面所描述的原理， 这个时候 ITIMER_VIRTUAL 并没有被触发。如果是在 Thread1 中调用 setitimer，则线程 2 的进程描述符中 it_virt_value 为 0，线程 1 进程描述符中的 it_virt_value 此时为 1 秒，还没有到期，因此进程则必须等到 线程 1 运行到 2 秒才能触发这个定时器。这不符合 POSIX 标准，因此从 2.6.12 开始，对上述基本实现进行了 一定的改进，虽然从原理上说，这个改进很小，但代码却有比较大的改变。

Per-process ITIMER_VIRTUAL 和 ITIMER_PROF

2.6.12 中合并了 Roland McGrath 的 per-process timer 系列 Patch。使得 itimer.c，posix-timer.c 有了不少改变， 还多了一个 posix-cpu-timer.c 文件。虽然代码实现上有很大的不同，但实际上基本的实现思路还是和之前介绍的差不多， 不过进一步考虑了对多线程情况下的修正。这里简单介绍一下实现的思路。

每个进程描述符中，引入了两个计数器：utime 和 stime。utime 代表当前进程（也可能是一个线程）花费在用户态的时间。

在时钟中断中，如果内核发现中断时当前进程（线程）正在用户态，则 utime 增加一个 jiffies； 如果在内核态则 utime 不增加，stime 增加。总的说来，就是统计好当前进程或线程的运行时间。 现在，按下时钟中断暂且不表。

创建 ITIMER_VIRTUAL时 (内核响应函数为do_setitimer)，内核将该 Timer 的value 和 interval 分别设置到当前进程描述符的 signal->it_virt_value 和 signal->it_virt_incr 中。 假设一个程序有 2 个线程，Thread1 和 Thread2。内核将有两个进程描述符对应这两个线程， taskStruct1 和 taskStruct2。再假设程序是在 Thread1 中调用 setitimer。那么 taskStrcut1的 signal->it_virt_value 和 signal->it_virt_incr 被设置；而 taskStruct2 的相应数据则保持为 0。 让我们再回到时钟中断。

统计完 utime 和 stime 之后，时钟中断开始检查当前进程描述符的 signal->it_virt_value 值， 如果该值非零，则表明有一个 ITIMER_VITURAL，到期时间为 signal->it_virt_value。老的内核实现在 这里就判断 utime 是否大于 it_virt_value，如果大于则表明时钟到期。为了统计多线程情况， 从 2.6.12 开始，时钟中断在这里不仅要查看当前进程描述符的 utime，还要加上当前进程组中所有线程的 utime， 然后再判断总的 utime 是否大于 signal->it_virt_value。比如前面所假设的例子，Thread2 被时钟中断打断时， 统计自己的 utime，但由于其 signal->it_virt_value 为 0，因此没有其他的工作需要做了。 当 Thread1 被时钟中断打断时，其 signal->it_virt_value 大于 0，因此中断处理中要遍历线程组中所有的线程， 将每个线程的 utime 汇总，即总的 utime=taskStruct1->utime+taskStruct2->utime。 再用这个总的 utime 和 signal->it_virt_value（即时钟到期时间）进行比较是否到期。仅此而已。

ITIMER_PROF 的思路类似，但它不仅要比较 utime，还要比较 stime。不再赘述。

Posix timer

从 2.5.63 开始，内核能够支持 posix timer 了，之前，其支持是有限的：只支持 CLOCK_REALTIME 和 CLOCK_MONOTONIC 两种 clock ID。这两种 POSIX Timer 建立在内核动态 Timer 之上，精度是一个 tick。比如，创建 realtime 定时器， 内核将调用 init_timer() 创建一个动态 Timer，并制定其到期处理函数位 posix_timer_fn；当启动该定时器时， 内核将调用 add_timer() 启动该内核动态 Timer；当该定时器到期时，将触发 posix_timer_fn，该函数采用 定时器注册的通知方式进行处理，比如 SIGEV_SIGNAL，该函数就会调用 sigaddset 发送一个信号。

其他两种 Timer(CLOCK_PROCESS_CPUTIME_ID 和 CLOCK_THREAD_CPUTIME_ID) 的实现有点儿复杂。因为用户 可以创建任意多的 POSIX Timer。CLOCK_REALTIME 和 CLOCK_MONOTONIC 基于数量不限的动态 Timer， 因此可以创建任意数目的定时器。

但 CLOCK_PROCESS_CPUTIMER_ID 和 CLOCK_THREAD_CPUTIME_ID，并不依赖动态 Timer，必须在进程描述符中想办法。

2.6.12 在进程描述符中引入了两个 cpu_timers 数组 (所谓 CPU TIME，即进程/线程真正在 CPU 上执行的时间， 包括内核态时间和用户态的时间):

一个在进程描述符 task_stuct 中。另一个放在进程描述符的 signal 数据结构中。用 task 表示进程描述符， 两个 cpu timers 数组如下：

task->cpu_timers[3]：用来维护 per-thread 的 CPU Timer

task->signal->cpu_timers[3]：用来维护 per-process 的 CPU Timer.

该数组的每个元素都维护一个 Timer 列表。如下图所示：

图 5. 进程控制块中的 CPU-TIMER

进程控制块中的 CPU-TIMER

可以看到 Linux 采用排序列表来存放 CLOCK_PROCESS_CPUTIMER_ID 和 CLOCK_THREAD_CPUTIME_ID 的 Timer， 即上图中红色的列表（cpu_timer[CPUCLOCK_SCHED]）。每当定时中断发生时，会检查这两个链表，如果发现有 到期的定时器就触发它们。通过这两个数组，内核支持用户创建任意多 CLOCK_PROCESS_CPUTIMER_ID/CLOCK_THREAD_CPUTIME_ID 类型的 POSIX 定时器。

小结

随着时光推移，精度为 jiffy 的时钟已经不能满足所有的要求了。越来越强的呼声是高精度时钟， 通过提高 HZ 毕竟是有限的，一些系统上已经采用了 1000 的 HZ 配置，再继续增高将导致时钟中断的开销过大， 从而降低整个系统的处理能力。经过了多年的不断尝试和开发，Linux 内核终于在 2.6.16 版本中加入了 HRTIMER。 我们在下一部分将继续介绍内核的高精度时间系统。

Linux 内核的工作

回顾

近年来，随着 Linux 的广泛使用，对时间编程提出了更高的要求。实时应用、多媒体软件对时钟和定时器的精度 要求不断提高，在早期 Linux 内核中，定时器所能支持的最高精度是一个 tick。为了提高时钟精度， 人们只能提高内核的 HZ 值 (一个内核参数，代表内核时钟中断的频率)。更高的 HZ 值，意味着时钟中断更加频繁， 内核要花更多的时间进行时钟处理。而内核的任何工作对于应用来说纯粹是无益的开销。当 HZ 值提高到 1000 之后， 如果继续提高，Linux 的可用性将下降。

另外一方面，我们已看到，类似 HPET(High Precision Event Timer) 等系统硬件已经能够提供纳秒级别的时钟中断， 如何利用这些高精度时钟硬件来提供更高精度的定时服务是这一部分的主要话题。

2.6.16 以来的新变化

在 2.6.16 之前，Linux 开发人员花了很多的努力试图在原有代码体系结构下实现高精度时钟，但这种努力被证明是徒劳的。

因此从 2.6.16 开始，RedHat 公司的 Ingo Molar 和 Thomas Gleixner 对时间系统进行了比较大的重构。引入了以下几个新的模块：

Generic Timer Framework

早期 Linux 内核也需要支持众多不同的时钟硬件设备，但内核本身对这些设备的使用相对简单。内核将硬件的不同操作封装 在 Arch 层里面。比如 x86 体系结构下，设置 PIT(Programmable Interrupt Timer) 是在 8259 芯片初始化时完成的， 调用的 API 名字叫做 setup_pit_timer()，而在其他体系结构中，没有 8259，其初始化 time_init()中的具体实现又有所不同， 会采用不同的 API 命名和不同的表示 Timer 硬件的数据结构。因为早期 Linux 上只需要做一次时钟初始化，操作具体硬件的次数有限， 因此这种不同体系结构用不同实现细节的做法没有什么问题。

新的内核能够支持 tickless 模式，即当内核空闲时为了省电而关闭时钟中断。为此，内核需要频繁操作 Timer 硬件， 在这种情况下，采用统一的抽象层有助于代码的维护。这便是 Generic Timer Frame，它将各种不同硬件抽象为三个统一的数据结构：

• Clock Source，由 struct clocksource 表示。这个数据结构主要用来抽象那些能够提供计时功能的系统硬件，比如 RTC(Real Time Clock)、TSC(Time Stamp Counter) 等。
• Clock Event Device，由 struct clock_event_device 表示。这个数据结构主要用来封装和抽象那些能提供定时中断能力的系统硬件，比如 HPET 等。
• Tick Device，由 struct tick_device 表示。这个数据结构建立在 clock event device 之上，专门用来表示产生 tick 的设备。tick 是一个定时中断。因此归根结底需要一个 Clock Event Device 来完成，但 Clock Event Device 不仅可以用来提供 tick，在高精度 Timer 模式下，还用来提供其他功能。

Generic Timer Frame 把各种不同时间硬件的区别同上层软件隔离开来， 使得时间系统能够方便地支持新的时钟硬件，而无需大量修改硬件无关代码。

高精度定时器 hrtimer(High Resolution Timer)

高精度时钟不能建立在已有的时间轮算法上，虽然时间轮是一种有效的管理数据结构， 但其 cascades 操作有不可预料的延迟。它更适于被称为”timeout”类型的低精度定时器，即不等触发便被取消的 Timer。 这种情况下，cascades 可能造成的时钟到期延误不会有任何不利影响，因为根本等不到 cascades， 换句话说，多数 Timer 都不会触发 cascades 操作。而高精度定时器的用户往往是需要等待其精确地被触发， 执行对时间敏感的任务。因此 cascades 操作带来的延迟是无法接受的。所以内核开发人员不得不放弃时间轮算法， 转而寻求其他的高精度时钟算法。最终，开发人员选择了内核中最常用的高性能查找算法红：黑树来实现 hrtimer。

在描述 hrtimer 的实现之前，先了解其使用方法是必要的。

hrtimer 的编程接口和方法

使用 hrtimer 之需要了解三个 API：

用 hrtimer_init() 初始化一个 Timer 对象，用 hrtimer_start() 设定到期时间和到期操作， 并添加启动该 Timer。remove_hrtimer() 删除一个 Timer。

Hrtimer 的实现

高精度定时器和低精度定时器的实现有以下两个主要的不同点：

• 高精度定时器由红黑树管理，而非时间轮。
• Hrtimer 与系统时钟 tick 无关，不使用 jiffies，用纳秒作为计时单位。

所有的 hrtimer 实例都被保存在红黑树中，添加 Timer 就是在红黑树中添加新的节点；删除 Timer 就是删除树节点。红黑树的键值为到期时间。

Timer 的触发和设置管理不在定期的 tick 中断中进行，而是动态调整：当前 Timer 触发后，在中断处理的时候，将高精度时钟硬件的下次中断触发时间设置为红黑树中最早到期的 Timer 的时间。时钟到期后从红黑树中得到下一个 Timer 的到期时间，并设置硬件，如此循环反复。

图 1 显示了内核中用来管理 hrtimer 的数据结构及他们之间的关系。

数据结构

每一个具体的高精度定时器用 struct hrtimer 表示，并且是红黑树的一个节点。

在多处理器系统中，每个 CPU 都保存和维护自己的高精度定时器，为了同步和通知的需要处理器间的消息通信 将引入不可忍受的延迟。要知道，hrtimer 的精度要求是纳秒级别的。在每个 CPU 上，hrtimer 还分为两大类：

• Monotonic：与系统时间无关的自然流失的时间，不可以被人修改。
• Real time：实时时间即系统时间，可以被人修改。

因此每个 CPU 都需要两个 clock_base 数据结构：一个指向所有 monotonic hrtimer；另一个指向所有的 realtime hrtimer。

clock_base 数据结构中，active 指向一个红黑树，每个 hrtimer 都是该红黑树的一个节点，用到期时间作为 key。 这样所有的定时器便按照到期时间的先后被顺序加入这棵平衡树。first 指向最近到期的 hrtimer, 即红黑树最左边的叶子节点。

这种数据结构组织是很清晰和简单的，理解了这些数据结构，描述 hrtimer 的具体操作便十分容易了。

添加 Timer，即在相应的 clock_base 指向的红黑树中增加一个新的节点，红黑树的 key 由 hrtimer 的到期时间表示， 因此越早到期的 hrtimer 在树上越靠左。

删除 Timer，即从红黑树上删除该 hrtimer。

hrtimer 是如何触发的

我们所描述过的低精度定时器都是依赖系统定期产生的 tick 中断的。而高精度时钟模式下，定时器直接由高精度 定时器硬件产生的中断触发。比如目前系统中有 3 个 hrtimer，其到期时间分别为 10ns、100ns 和 1000ns。 添加第一个 hrtimer 时，系统通过当前默认的 clock_event_device 操作时钟硬件将其下一次中断触发时间设置为 10ns 之后； 当 10ns 过去时，中断产生，通过系统的中断处理机制，最终会调用到 hrtimer_interrrupt() 函数，该函数从红黑树中 得到所有到期的 Timer，并负责调用 hrtimer 数据结构中维护的用户处理函数（或者通过软中断执行用户指定操作）； hrtimer_interrupt 还从红黑树中读取下一个到期的 hrtimer，并且通过 clock_event_device 操作时钟硬件将下一次 中断到期时间设置为 90ns 之后。如此反复操作。

这样就突破了 tick 的精度限制，用户操作可以精确到 ns 级别，当然中断依然存在延迟， 这种延迟在几百个纳秒级别，还是比较高的精度。

Tick 时钟模拟

在高精度时钟模式下，内核系统依然需要一个定时触发的 tick 中断，以便驱动任务切换等重要操作。 可是我们在上一节看到，高精度时钟模式下，系统产生时间中断的间隔是不确定的，假如系统中没有创建任何 hrtimer， 就不会有时钟中断产生了。但 Linux 内核必须要一个严格定时触发的 tick 中断。

因此系统必须创建一个模拟 tick 时钟的特殊 hrtimer，并且该时钟按照 tick 的间隔时间（比如 10ms） 定期启动自己，从而模拟出 tick 时钟，不过在 tickless 情况下，会跳过一些 tick。关于 tickless，和本文主旨无关，不再赘述。

内核时间系统的总体运行情况

至此，我们可以用下面这张图来总结高精度模式下，内核时间系统的总体运行情况。

图 2. 内核时间系统概览

内核时间系统概览

Linux 用 Generic Timer Framework 层来屏蔽底层硬件的细节，对上抽象出 Clock Sources 和 Clock Event 两个数据结构，分别用来表示计时的硬件和定时的硬件。

用基于红黑树的 hrtimer 系统维护高精度时钟，并用一个特殊的 hrtimer 模拟系统时钟 tick，产生定期的系统时钟中断。

模拟的系统时钟 tick 将驱动传统的低精度定时器系统（基于时间轮）和内核进程调度。

用户层 Timer 的支持和改变

高精度时钟主要应用于实时系统。在用户层，实时时钟的编程接口就是我们在第一部分介绍的 POSIX Timer。 本文的第三部分介绍了基于 2.6.16 之前内核的 POSIX Timer 实现细节。

当 hrtimer 加入内核之后，POSIX Timer 的实现细节有一些改变，其中 per process 和 per thread 定时器的 实现基本没有变化。但针对 CLOCK_REALTIME 和 CLOCK_MONOTONIC 两个时钟源的基本实现有所改变。 以前它们依赖内核中的动态定时器实现，现在这类 Timer 都采用了新的 hrtimer。换句话说， 每个时钟源为 CLOCK_REALTIME/CLOCK_MONOTONIC 的 POSIX Timer 都由一个内核 hrtimer 实现。

传统的间隔 Timer 虽然不属于实时应用，也没有很高的时钟精度要求，但在新的内核中， 间隔 Timer 也使用了 hrtimer，而非传统的动态 Timer。因此 setitimer 在内核中也不再由时间轮管理了。

总体来说，用户请求的 Timer，无论是精度较低的间隔 Timer 还是精度高的 POSIX Timer， 内核都采用 hrtimer 来支持。而由时间轮算法维护的内核动态 Timer 则仅仅在内核内部使用， 比如一些驱动程序中还依旧使用 add_timer() 等动态 Timer 接口实现定时需求。

时区问题

结束之前，我们探讨一个尚未展开的话题，即时区问题。这是非常容易让人迷惑的一个话题。因此放在文章的结尾处讨论会好些。

首先介绍两个缩写： UTC 和 LCT。

UTC 就是 Coordinated Universal Time，是全世界通用的时间标准。它是格林威治时间 (GMT) 的后继者， 在计算机领域，GMT 术语不再广泛使用，因为它的精度不够高。UTC 是 1963 年标准化的，采用了高精度的原子钟。 因此在科学领域，包括计算机科学，都采用 UTC 而不再使用 GMT 这个术语。我们可以认为 UTC 就是时区 0 的标准时间。 LCT(Local Civil Time) 即当地时间，比如北京时间。

假如您耐心读到了这里，应该已经了解了系统时间 (system time) 和硬件时间 (RTC time) 的区别。硬件时间存放在 RTC(Real Time Clock) 硬件中。Linux 系统启动时，会读取 RTC 时间，并该时间来初始化系统时间；正常运行时， 系统时间在每次 tick 中断中加以更新和维护；当系统关闭时，Linux 用系统时间来更新硬件时间。

Linux 系统时间总是 UTC 时间。那么硬件 RTC 中保存的是 UTC 还是 LCT 呢？

微软的 Windows 系统认定该时间为 LCT，即当地时间。我在上海的家里打开电脑，RTC 的时间是 2013-01-25 10:00:00， 当系统启动后，会发现屏幕最右下角显示的当前时间就是 2013 年 1 月 25 日上午 10 点。

而在 Linux 系统中，RTC 的时间究竟是 LCT 还是 UTC 是由一个配置文件决定。RedHat 发行版中， 该配置文件叫做/etc/sysconfig/clock。当该文件中有”UTC=true”这一行设定时，Linux 系统会将 RTC 时间解读为 UTC 时间，否则就解读为 LCT。（Debian 发行版依赖/etc/default/rcS 的设定来决定从 RTC 读入的是 UTC 还是 LCT）假设 RTC 中的时间还是 2013-01-25 10:00:00，并且/etc/sysconfig/clock 中有一行”UTC=true”，那么系统启动后就会将系统时间设置为 2013-01-25 10:00:00。如果/etc/sysconfig/clock 中 没有这一行，系统 init 进程会将 RTC 中的时间解释为 LCT，并根据当前的时区配置计算出 UTC 时间， 再用该时间设置系统时间 (hwclock 命令)。RTC 时间不变，现在的系统时间就变成了 2013-01-25 02:00:00， 因为我的电脑在上海，系统计算出 UTC 为 8 小时之前。我们用 time()、gettimeofday() 等获得的时间值都是系统时间，即 UTC 时间。

可是桌面程序显示时间时，最好显示当地时间，您恐怕也不愿意每次看时间都需要在脑海中把格林威治时间转成当地时间吧。 因此桌面应用通常会显示本地时间，我们常用的 date 命令也缺省显示 LCT。这是怎么做到的呢？

查看 date 的源代码，可以发现它用 localtime() 将调用 gettimeofday() 得到的 UTC 时间转换为 LCT 时间再进行输出。

那么 localtime() 是如何转换 LCT 的呢？感谢 POSIX 在这里有一个标准，Linux 系统将时区信息写入/etc/localtime 文件。 该文件一般是/usr/share/zone 中某个文件的拷贝或者软链接。LibC 的 localtime 函数会读取/etc/localtime 获取本机的时区设置，然后进行复杂的时区转换，将给定 time_t 表示的 UTC 时间转换为 LCT。此外， 在读取/etc/localtime 之前，localtime() 会先读取环境变量 TZ，因此用户也可以通过设置该环境变量来临时 改变时区设置。/etc/localtime 文件中还包含了 Day Light Saving，即夏令时的信息。在实行夏令时的地区， /etc/localtime 文件中包含了如何计算夏令时的必要信息，因此 LibC 函数 localtime 才能够正确地将 UTC 转换为 LCT。

结束语

至此本文终于告一段落，用了 4 篇文章走马观花地试图指出时间系统的完整图景，不足之处甚至错误一定很多。 希望读者包涵并和我交流。

关于 Linux 内核时间系统的更多细节，读者可参考继续 IBM deeveloperWorks 的文章 Linux 下定时器的实现方式 分析以及 Linux 时钟管理。它们都有更加精彩而详细的解说。

文档信息
--------------
* 作者:
* 版权声明：自由转载-非商用
* 转载: []

Linux 应用层的时间编程