思维导图：定时器设计

news/2024/5/17 16:14:31/文章来源:https://blog.csdn.net/qq_39354847/article/details/126961406

思维导图：定时器设计

Linux 服务器经典定时器设计，根据网上的各种资料简单整理了个思维导图
请添加图片描述

单个思维导图估计也就个人看看，如果各位有兴趣可以从以下几个问题入手

为啥要有专门的定时器模块
定时器有啥用
怎么定时
关于定时器的设计与几种方案的讨论
和其他模块的结合

下面是 Xmind 生成的 markdown 大纲，方便各位基于我的导图去修改

大纲

为什么需要

定时事件应用
- 心跳检测
- 技能冷却
- 武器冷却
- 倒计时
- 检测连接
高效地组织并管理定时事件：把每个定时事件封装成定时器

Linux 定时机制

alarm/setitimer：设置超时时间，等待并捕获 SIGALARM 信号
套接字超时选项
多路复用超时参数 select/poll/epoll：看是否返回 0
timer_create：本质也是借助信号
timerfd_create：通过判断文件描述符来判，可以配合 IO 多路复用

和 IO 协程调度模块的结合（sylar）

用 epoll_wait 来做的超时等待，毫秒级
IO协程调度器的idle协程会在调度器空闲时阻塞在epoll_wait上，等待IO事件发生。加入定时器功能后，epoll_wait的超时时间改用当前定时器的最小超时时间来代替。epoll_wait返回后，根据当前的绝对时间把已超时的所有定时器收集起来，执行它们的回调函数。
由于epoll_wait的返回并不一定是超时引起的，也有可能是IO事件唤醒的。要再判断一下定时器有没有超时，用绝对时间就可以轻松判断啦

定时器设计与实现

成员

超时时间
- 相对时间：注册的时候一般是超时时间
- 绝对时间：排序和确认超时的时候一般绝对时间
  - gettimeofday 获取绝对时间，依赖系统时间
  - 可能存在校时问题导致定时机制失效
    - 用小的超时步长 + 多次超时才触发 + 检测系统时间有没有往回调
    - 直接换个时间源如 clock_gettime(CLOCK_MONOTONIC_RAW) 获取系统单调时间
任务回调函数

接口设计

初始化
添加定时器
删除定时器
找到最近要发生的定时任务
更新检测定时器
清除定时器

数据结构设计

考虑：支持动态修改并维护有序，高效找到最近要发生的定时任务
几种方案
- 依赖一个固定周期触发的 tick 信号
  - 升序链表
    - 时间复杂度：添加 O（N），找最小，删除O（1）
      - tick 信号的周期对定时器性能影响比较大：周期小，精度高，CPU 负担高；周期大，精度低，CPU 负担小
      - 定时器数量比较多的时候，插入开销大
  - 时间轮：哈希思想，将定时器散列到不同的有序链表上
    - 每个链表的定时器数量的不会太常，这样插入效率也不会太拉跨；N 越大散列越均匀，插入效率越高。如果 N = 1 那就退化成升序链表了
    - 几种实现
      - 最简单的不带取模的直接一个槽为对应一个时间（纯哈希表）
        增删改查都O(1)
        可能要很多槽为，空间爆炸
      - 带取模的
        特征：同一条链表上每个定时器前后节点定时时间差 N * si 的整数倍（不一定是差 1 个 N）；ts = （cs + （ti / si) %N
        先 O(1) 找到对应槽为，按有序链表操作
      - 多级时间轮（优雅）
        根据定时任务出发的紧急程度，分布到不同层级的时间轮中
        均衡了时间（简单的单时间轮差不了多少）和空间
- 直接把超时时间当作 tick 周期
  - 基本思路：每次都取出所有定时器中超时时间最小的超时值作为一个tick，这样，一旦tick触发，超时时间最小的定时器必然到期。处理完已超时的定时器后，再从剩余的定时器中找出超时时间最小的一个，并将这个最小时间作为下一个tick，如此反复，就可以实现较为精确的定时。根据绝对时间去排序
  - 具体实现
    - 最小堆：增删O(log2N)，删除O（n）因为查找要O（n）可以配合 hash map 来辅助快速索引，查最小O（1）直接根节点
    - 红黑树：都 O(log2N)，查最小就是查红黑树的最左节点
    - 其他：跳表