rtthread学习笔记系列(10/11) -- 系统定时器

https://github.com/wdfk-prog/RT-Thread-Study

10. 系统定时器

10.1 跳跃表

• 跳跃表是一种“随机”的数据结构，在很大的可能性下，它会得到O(log(N))的时间复杂度，而旧的列表得到O(N)。此外，当将RT_TIMER_SKIP_LIST_LEVEL设置为1时，它将与旧的双链表相同，无论是时间还是空间复杂性。基准测试表明，当RT_TIMER_SKIP_LIST_LEVEL为3时，当有100个计时器时，随机插入新计时器的平均时间比旧计时器快2倍，当有200个计时器时快3倍。但是，它恢复已弃用的函数rt_system_timer_init。bsp必须在系统启动时调用它。

定时器跳表 (Skip List) 算法

在前面介绍定时器的工作方式的时候说过，系统新创建并激活的定时器都会按照以超时时间排序的方式插入到 rt_timer_list 链表中，也就是说 t_timer_list 链表是一个有序链表，RT-Thread 中使用了跳表算法来加快搜索链表元素的速度。

跳表是一种基于并联链表的数据结构，实现简单，插入、删除、查找的时间复杂度均为 O(log n)。跳表是链表的一种，但它在链表的基础上增加了 “跳跃” 功能，正是这个功能，使得在查找元素时，跳表能够提供 O(log n)的时间复杂度，举例如下：

一个有序的链表，如下图所示，从该有序链表中搜索元素 {13, 39}，需要比较的次数分别为 {3, 5}，总共比较的次数为 3 + 5 = 8 次。

使用跳表算法后可以采用类似二叉搜索树的方法，把一些节点提取出来作为索引，得到如下图所示的结构：

在这个结构里把 {3, 18,77} 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了, 例如在搜索 39 时仅比较了 3 次（通过比较 3，18，39)。当然我们还可以再从一级索引提取一些元素出来，作为二级索引，这样更能加快元素搜索。

所以，定时器跳表可以通过上层的索引，在搜索的时候就减少比较次数，提升查找的效率，这是一种通过 “空间来换取时间” 的算法，在 RT-Thread 中通过宏定义 RT_TIMER_SKIP_LIST_LEVEL 来配置跳表的层数，默认为 1，表示采用一级有序链表图的有序链表算法，每增加一，表示在原链表基础上增加一级索引。

10.2 硬件定时器

• HARD_TIMER 模式的定时器超时函数在中断上下文环境中执行，可以在初始化 / 创建定时器时使用参数 RT_TIMER_FLAG_HARD_TIMER 来指定。

  在中断上下文环境中执行时，对于超时函数的要求与中断服务例程的要求相同：执行时间应该尽量短，执行时不应导致当前上下文挂起、等待。例如在中断上下文中执行的超时函数它不应该试图去申请动态内存、释放动态内存等。

  RT-Thread 定时器默认的方式是 HARD_TIMER 模式，即定时器超时后，超时函数是在系统时钟中断的上下文环境中运行的。在中断上下文中的执行方式决定了定时器的超时函数不应该调用任何会让当前上下文挂起的系统函数；也不能够执行非常长的时间，否则会导致其他中断的响应时间加长或抢占了其他线程执行的时间。

10.2.1 初始化&&删除

• 初始化

  • 动态分配,malloc定时器结构体 || 静态分配,外部分配
  • 设置相关参数
  • init tick;timeout = 0;
  • 初始化跳跃表链表

• 删除

  • 移除跳跃表链表
  • 从系统移除该对象

10.2.2 start

• 获取链表

10.2.2.1 线程定时器

• 调度上锁
• 从定时器计算线程结构体地址
• 标识线程定时器启动
• 调度解锁

10.2.2.2 定时器开始处理

• 当前正在执行超时处理函数,退出;(超时函数执行后会再次运行开始函数)
• 移除跳跃表定时器
• 定时器状移除激活状态
• 计算超时tick
• 提取跳表索引到_timer_list中

row_head[0]  = &timer_list[0];//遍历每一层的定时器列表for (row_lvl = 0; row_lvl < RT_TIMER_SKIP_LIST_LEVEL; row_lvl++){//当前层中，遍历定时器列表，直到 row_head 指向当前层的最后一个定时器。for (; row_head[row_lvl] != timer_list[row_lvl].prev;row_head[row_lvl]  = row_head[row_lvl]->next){struct rt_timer *t;rt_list_t *p = row_head[row_lvl]->next;/* 获取当前节点定时器的指针，并将其转换为 rt_timer 结构体类型。 */t = rt_list_entry(p, struct rt_timer, row[row_lvl]);//如果我们有两个定时器同时超时，最好是先插入的定时器被提前调用。因此，将新的计时器插入到some-timeout计时器列表的末尾。//当前节点定时器的超时时间和需要开启的定时器超时时间相同，继续遍历。if ((t->timeout_tick - timer->timeout_tick) == 0){continue;}//如果当前节点定时器比需要开启的定时器超时时间还长,退出elseif ((t->timeout_tick - timer->timeout_tick) < RT_TICK_MAX / 2){break;}}//将提取的索引更新至_timer_list中if (row_lvl != RT_TIMER_SKIP_LIST_LEVEL - 1)row_head[row_lvl + 1] = row_head[row_lvl] + 1;/*这个简单的计数器可以很好地均匀分布列表高度。通过使用tst_nr的最低有效位，它确保定时器被插入到不同的级别，从而实现平衡分布。目标是避免具有相似超时节拍的计时器聚类*///每次插入定时器时，计数器会递增。这个计数器的作用是在跳表中决定新的定时器节点应该插入到哪一层。random_nr++;tst_nr = random_nr;//将新的定时器节点插入到系统定时器列表的最后一层rt_list_insert_after(row_head[RT_TIMER_SKIP_LIST_LEVEL - 1],&(timer->row[RT_TIMER_SKIP_LIST_LEVEL - 1]));//从第二层开始，遍历每一层的定时器列表。for (row_lvl = 2; row_lvl <= RT_TIMER_SKIP_LIST_LEVEL; row_lvl++){//在相应级别的节点后插入计时器。 //RT_TIMER_SKIP_LIST_MASK = 3;1~3 ,5~7,9~11这样添加if (!(tst_nr & RT_TIMER_SKIP_LIST_MASK))rt_list_insert_after(row_head[RT_TIMER_SKIP_LIST_LEVEL - row_lvl],&(timer->row[RT_TIMER_SKIP_LIST_LEVEL - row_lvl]));elsebreak;//tst_nr右移以测试下一位tst_nr >>= (RT_TIMER_SKIP_LIST_MASK + 1) >> 1;}}

10.2.3 删除定时器&&STOP

• 从定时器链表中剔除
• 从object对象中剔除

10.2 软件定时器

10.2.1 系统定时器线程

1. 初始化跳表链表
2. 信号量初始化,挂起线程按优先级排队恢复
3. 线程初始化并启动,优先级4,时间片10;(FREERTOS的时间片长度不可设置,1个时间片执行一次切换)

10.2.1.1 _timer_thread_entry

1. 进入前设置信号量最大获取次数为1,二值信号量

2. 进入后 : 获取最近的超时时间

   • 当前定时器链表为空,说明没有定时器启动; -> 信号量阻塞该线程,直到定时器启动释放信号量
   • 不为空则返回最近的超时时间

3. 获取当前tick

4. 计算下一次定时器到达超时时间,使用信号量阻塞到该时间

5. 阻塞结束后执行超时检测

10.2.3软件定时器启动

1. 信号量在启动时释放;
2. 目的:如果定时器线程发现当前没有正在执行的定时器链表,则会进入RT_WAITING_FOREVER阻塞状态;
3. 此处释放信号量用于释放定时器线程,计算下一个唤醒时间

10.3 rt_timer_check 定时器链表检测

• systick irq中调用

1. 获取当前tick

rt_list_init(&list);//初始化链表//最底层跳表不为空while (!rt_list_isempty(&_timer_list[RT_TIMER_SKIP_LIST_LEVEL - 1])){//获取定时器结构体t = rt_list_entry(_timer_list[RT_TIMER_SKIP_LIST_LEVEL - 1].next,struct rt_timer, row[RT_TIMER_SKIP_LIST_LEVEL - 1]);//由于tick中断应该是很快进入的,所以判断超时时间<RT_TICK_MAX既可if ((current_tick - t->timeout_tick) < RT_TICK_MAX / 2){//从计时器列表中删除计时器_timer_remove(t);t->parent.flag |= RT_TIMER_FLAG_PROCESSING;//将计时器添加到临时列表rt_list_insert_after(&list, &(t->row[RT_TIMER_SKIP_LIST_LEVEL - 1]));/* call timeout function */t->timeout_func(t->parameter);/* re-get tick */current_tick = rt_tick_get();t->parent.flag &= ~RT_TIMER_FLAG_PROCESSING;//检查定时器对象是否被分离或重新启动//由于没有屏蔽中断,可能在执行过程中,其他中断停止该定时器;如果不直接退出,t的指向将会出问题if (rt_list_isempty(&list)){continue;}rt_list_remove(&(t->row[RT_TIMER_SKIP_LIST_LEVEL - 1]));if ((t->parent.flag & RT_TIMER_FLAG_PERIODIC) &&(t->parent.flag & RT_TIMER_FLAG_ACTIVATED)){/* start it */t->parent.flag &= ~RT_TIMER_FLAG_ACTIVATED;_timer_start(_timer_list, t);}}elsebreak;}

10. 3 其他定时器管理算法

https://zhuanlan.zhihu.com/p/549450132

有序链表：插入O(n)，删除O(1)，过期expire执行O(1)最小堆：插入O(logn)，删除O(logn)，过期expire执行O(1)红黑树：插入O(logn)，删除O(logn)，过期expire执行O(logn)哈希表+链表（时间轮）：插入O(1)，删除O(1)，过期expire平均执行O(1)（最坏为O(n)）

10.3.1 红黑树定时器

Nginx 定时器 :https://blog.csdn.net/dearQiHao/article/details/102878306

• 红黑树与AVL(二叉平衡树) 红黑树比 AVL 树具体更高效在哪里？

因为红黑树利用了缓存。

Robert Sedgewick, 红黑树的发明人，在《算法（第4版）》 中说过， 红黑树等价于2-3树。

其中2-节点 等价于普通平衡二叉树的节点，3-节点 本质上是非平衡性的缓存。

当需要再平衡（rebalance）时，增删操作时，2-节点 与 3-节点间 的 转化会吸收不平衡性，减少旋转次数，使再平衡尽快结束。

在综合条件下，增删操作相当时，数据的随机性强时，3-节点的非平衡性缓冲效果越明显。因此红黑树的综合性能更优。

继续追根溯源，红黑树的性能优势，本质上是用空间换时间。

11 数据结构

• 二叉搜索树、B树、B+树、AVL树、红黑树
• 树堆（Treap）和红黑树（RB-Tree）各有哪些优劣？