设计一个高效的定时任务系统( 二 ) _定时任务系统

系统调用 gettimeofday(对应库函数 time 和 gettimeofday)就是用来读 xtime 变量的，从而让用户程序获取系统时间。
实现定时器：既然已知每个 tick 是 10ms，用 tick 来做定时任务统计再好不过。无论是内核还是应用系统其实都有大量的定时任务需求，这些定时任务类型不一，但是都是依赖于 tick 。
已知的操作系统实现定时任务的方式有哪些呢?
①维护一个带过期时间的任务链表
简单且行之有效的方式。在一个全局链表中维护一个定时任务链。每次 tick 中断来临，遍历该链表找到 expire 到期的任务。
如果将任务以 expire 排序，每次只用找到链头的元素即可，时间复杂度为 O(1) 。
这种方式对于早期的 Linux 系统来说没有问题，随着现在的系统复杂度渐渐变化，它无法支撑如今的网络流量暴增时代的需求。
②时间轮(Timing-Wheel)算法

文章插图

时间轮很容易理解，上图有 n 个 bucket，每一个 bucket 表示一秒，当前 bucket 表示当前这一秒到来之后要触发的事件。
每个 bucket 会对应着一个链表，链表中存储的就是当前时刻到来要处理的事件。
那这里有个问题来了，如果有个定时任务需要在 16 小时后执行，换算成秒就是 57600s，难道我们的时间轮也要这么多个 bucket 吗。几万个对内存也是一种损耗。
为了减少 bucket 的数量，时间轮算法提供了一个扩展算法，即 Hierarchy 时间轮。

文章插图

Hierarchy 很好理解，层级制度。既然一个时间轮可能会导致 bucket 过多，那么为什么不能多弄几个轮子来代替时分秒呢?
基于时、分、秒各自实现一个 wheel，每个 wheel 维护一个自己的 cursor，在 Hour 数组中，每个 bucket 代表一个小时。
Minute 数组中每一个 bucket 代表 1 分钟，Second 数组中每个 bucket 代表 1 秒。
采用分层时间轮，我们只需要 24+60+60=144 个 bucket 就可以表示所有的时间。
完全模拟到时钟的用法，Second wheel 每转完 60 个 bucket ，要联动 Minute wheel 转动一格，同理 Minite wheel 转动 60 个 bucket 也要联动 Hours wheel 转动一格。
③维护一个基于小根堆算法的定时任务
小根堆的性质是满足除了根节点以外的每个节点都不小于其父节点的堆。基于这种性质从根节点开始遍历每个节点能保证获取到一个最小优先级的队列。
那么应用到定时器中，每次只用获取当前最小堆的 root 节点看是否到期即可。最小堆的插入时间复杂度为 O(lgn)，获取头结点时间复杂度为 O(1) 。
开箱即用的定时器
单机版定时器
①cron/crontab
cron 是 Linux 中的一个定时任务机制。cron 表示一个在后台运行的守护进程，crontab 是一个设置 cron 的工具，所有的定时任务都写在 crontab 文件中。
cron 调度的是 /etc/crontab 文件中的内容。crontab 的命令构成为时间+动作，其时间有分、时、日、月、周五种。
这里要注意，最小单位为分钟，默认是不到秒的级别，大家也给出了各种精确到秒的方案，有兴趣的可以搜索一下。
/etc/crontab 文件中的每一行都代表一项任务，它的格式是：

minutehourdaymonthdayofweekuser-namecommand * minute — 分钟，从 0 到 59 之间的任何整数 * hour — 小时，从 0 到 23 之间的任何整数 * day — 日期，从 1 到 31 之间的任何整数（如果指定了月份，必须是该月份的有效日期） * month — 月份，从 1 到 12 之间的任何整数（或使用月份的英文简写如 jan、feb 等等） * dayofweek — 星期，从 0 到 7 之间的任何整数，这里的 0 或 7 代表星期日（或使用星期的英文简写如 sun、mon 等等） * user-name - 用户，脚本以什么用户执行 * command — 要执行的命令（命令可以是 ls /proc >> /tmp/proc 之类的命令，也可以是执行你自行编写的脚本的命令 。）

②JDK 提供的定时器：Timer
Timer 的思路很简单，基于最小堆的方案创建一个 TaskQueue 来盛 TimerTask 。
Timer 中有一个 TimerThread 线程，该线程是 Timer 中唯一负责任务轮询和任务执行的线程。
这就意味着如果一个任务耗时很久，久到已经超过了下个任务的开始执行时间，那么就意味下一个任务会延迟执行。
另外 Timer 线程是不会捕获异常的，如果某个 TimerTask 执行过程中发生了异常而被终止，那么后面的任务将不会被执行。所以要做好异常处理防止出现异常影响任务继续。