linux编程之经典多级时间轮定时器(C语言版)

发表于 11/7/2022 6:04:18 PM 阅读（1175）

　一. 多级时间轮实现框架

微信截图_20221107164603.png

　　上图是5个时间轮级联的效果图。中间的大轮是工作轮，只有在它上的任务才会被执行；其他轮上的任务时间到后迁移到下一级轮上，他们最终都会迁移到工作轮上而被调度执行。

　　多级时间轮的原理也容易理解：就拿时钟做说明，秒针转动一圈分针转动一格；分针转动一圈时针转动一格；同理时间轮也是如此：当低级轮转动一圈时，高一级轮转动一格，同时会将高一级轮上的任务重新分配到低级轮上。从而实现了多级轮级联的效果。

　　1.1 多级时间轮对象

　　微信截图_20221107164808.png

　　多级时间轮应该至少包括以下内容：

　　每一级时间轮对象

　　轮子上指针的位置关于轮子上指针的位置有一个比较巧妙的办法：那就是位运算。比如定义一个无符号整型的数：

　　微信截图_20221107164832.png

　　通过获取当前的系统时间便可以通过位操作转换为时间轮上的时间，通过与实际时间轮上的时间作比较，从而确定时间轮要前进调度的时间，进而操作对应时间轮槽位对应的任务。

　　为什么至少需要这两个成员呢？

　　定义多级时间轮，首先需要明确的便是级联的层数，也就是说需要确定有几个时间轮。

　　轮子上指针位置，就是当前时间轮运行到的位置，它与真实时间的差便是后续时间轮需要调度执行，它们的差值是时间轮运作起来的驱动力。

　　多级时间轮对象的定义

　微信截图_20221107164856.png

　　1.2 时间轮对象

　　微信截图_20221107164914.png

　　我们知道每一个轮子实际上都是一个哈希表，上面我们只是实例化了五个轮子的对象，但是五个轮子具体包含什么，有几个槽位等等没有明确(即struct tvec和struct tvec_root)。

微信截图_20221107164932.png

　　此外，每一个时间轮都是哈希表，因此它的类型应该至少包含两个指针域来实现双向链表的功能。这里我们为了方便使用通用的struct list_head的双向链表结构。

　　1.3 定时任务对象

　　微信截图_20221107165005.png

　　定时器的主要工作是为了在未来的特定时间完成某项任务，而这个任务经常包含以下内容：

　　任务的处理逻辑(回调函数)

　　任务的参数

　　双向链表节点

　　到时时间

　　定时任务对象的定义

　微信截图_20221107165026.png

　　在时间轮上的效果图：

　　微信截图_20221107165050.png

　　1.4 双向链表

　　在时间轮上我们采用双向链表的数据类型。采用双向链表的除了操作上比单链表复杂，多占一个指针域外没有其他不可接收的问题。而多占一个指针域在今天大内存的时代明显不是什么问题。至于双向链表操作的复杂性，我们可以通过使用通用的struct list结构来解决，因为双向链表有众多的标准操作函数，我们可以通过直接引用list.h头文件来使用他们提供的接口。

　　struct list可以说是一个万能的双向链表操作框架，我们只需要在自定义的结构中定义一个struct list对象即可使用它的标准操作接口。同时它还提供了一个类似container_of的接口，在应用层一般叫做list_entry，因此我们可以很方便的通过struct list成员找到自定义的结构体的起始地址。

　　关于应用层的log.h, 我将在下面的代码中附上该文件。如果需要内核层的实现，可以直接从linux源码中获取。

　　1.5 联结方式

　　多级时间轮效果图：

　　微信截图_20221107165120.png

　　二. 多级时间轮C语言实现

　　2.1 双向链表头文件: list.h

　　提到双向链表，很多的源码工程中都会实现一系列的统一的双向链表操作函数。它们为双向链表封装了统计的接口，使用者只需要在自定义的结构中添加一个struct list_head结构，然后调用它们提供的接口，便可以完成双向链表的所有操作。这些操作一般都在list.h的头文件中实现。Linux源码中也有实现（内核态的实现）。他们实现的方式基本完全一样，只是实现的接口数量和功能上稍有差别。可以说这个list.h文件是学习操作双向链表的不二选择，它几乎实现了所有的操作：增、删、改、查、遍历、替换、清空等等。这里我拼凑了一个源码中的log.h函数，终于凑够了多级时间轮中使用到的接口。

微信截图_20221107165224.png