定时器的实现原理

定时器的实现依赖的是CPU时钟中断，时钟中断的精度就决定定时器精度的极限。一个时钟中断源如何实现多个定时器呢？对于内核，简单来说就是用特定的数据结构管理众多的定时器，在时钟中断处理中判断哪些定时器超时，然后执行超时处理动作。而用户空间程序不直接感知CPU时钟中断，通过感知内核的信号、IO事件、调度，间接依赖时钟中断。用软件来实现动态定时器常用数据结构有：时间轮、最小堆和红黑树。

海量定时任务 、定时器设计 、 时间轮实现以及应用精讲

现场手撕定时器实现、 定时器实现方案（单线程、多线程）

Linux内核定时器相关(Linux v4.9.7, x86体系架构)的一些相关代码：

内核启动注册时钟中断

内核时钟中断处理流程

内核定时器时间轮算法

单层时间轮算法的原理比较简单：用一个数组表示时间轮，每个时钟周期，时间轮 current 往后走一个格，并处理挂在这个格子的定时器链表，如果超时则进行超时动作处理，然后删除定时器，没有则剩余轮数减一。原理如图：

Linux 内核则采用的是 Hierarchy 时间轮算法，Hierarchy 时间轮将单一的 bucket 数组分成了几个不同的数组，每个数组表示不同的时间精度，Linux 内核中用 jiffies 记录时间，jiffies记录了系统启动以来经过了多少tick。下面是Linux 4.9的一些代码：

Hierarchy 时间轮的原理大致如下，下面是一个时分秒的Hierarchy时间轮，不同于Linux内核的实现，但原理类似。对于时分秒三级时间轮，每个时间轮都维护一个cursor，新建一个timer时，要挂在合适的格子，剩余轮数以及时间都要记录，到期判断超时并调整位置。原理图大致如下:

定时器的使用方法

在Linux 用户空间程序开发中，常用的定期器可以分为两类：

1. 执行一次的单次定时器 single-short；

2. 循环执行的周期定时器 Repeating Timer；

其中，Repeating Timer 可以通过在 Single-Shot Timer 终止之后，重新再注册到定时器系统里来实现。当一个进程需要使用大量定时器时，同样利用时间轮、最小堆或红黑树等结构来管理定时器。而时钟周期来源则需要借助系统调用，最终还是从时钟中断。Linux 用户空间程序的定时器可用下面方法来实现：

• 通过 alarm() 或 setitimer() 系统调用，非阻塞异步，配合 SIGALRM 信号处理；

• 通过 select() 或 nanosleep() 系统调用，阻塞调用，往往需要新建一个线程；

• 通过 timefd() 调用，基于文件描述符，可以被用于 select/poll 的应用场景；

• 通过 RTC 机制, 利用系统硬件提供的 Real Time Clock 机制, 计时非常精确；

上面方法没提 sleep()，因为 Linux 中并没有系统调用 sleep()，sleep() 是在库函数中实现，是通过调用 alarm() 来设定报警时间，调用 sigsuspend() 将进程挂起在信号 SIGALARM 上，而且 sleep() 也只能精确到秒级上，精度不行。当使用阻塞调用作为定时周期来源时，可以单独启一个线程用来管理所有定时器，当定时器超时的时候，向业务线程发送定时器消息即可。

一个基于时间轮的定时器简单实现

在实际项目中，一个常用的做法是新起一个线程，专门管理定时器，定时来源使用 rtc、select 等比较精确的来源，定时器超时后向主要的 work 线程发消息即可，或者使用 timefd 接口。

LinuxC/C++服务器开发/架构师 面试题、学习资料、教学视频和学习路线图（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享有需要的可以自行添加
学习交流群960994558