巴赫曼模块NT255

NT255

NT255定时器接口封装

作为定时器，需要封装以下4类接口给用户使用：

• 创建定时器：init_timer
• 添加定时任务：add_timer
• 取消定时任务：cancel_timer
• 执行到期任务：expire_timer

其中执行到期任务有两种工作方式：

1. 轮询: 每隔一个时间片去查找哪些任务到期
2. 睡眠/唤醒：不停查找deadline最近任务，到期执行，否则sleep；sleep期间，任务有改变，线程会被唤醒

接下来将介绍分别用跳表、红黑树、时间轮来实现定时器。

跳表实现定时器

跳表简介

跳表是一种动态的数据结构，采用空间换时间的思想，在有序链表基础上加入多级索引，通过索引进行二分快速查找，支持快速删除、插入和查找操作（平均时间复杂度为O(logN)，最坏为O(N)），效率可与平衡树媲美，实现比其简单。

下面通过一张图来简单说明跳表操作。跳表的层即为基本的有序链表，存储所有的数据，可理解为数据层；往上则为索引层，理想状态下，上一层为下一层节点数的一半。比如，要查找下图的数据为11的节点，从begin''出发，向右走，如果下一个节点大于11则往下走，直到找到目标节点。可见，跳表要比原始链表少比较一些节点，但前提是需要花更多空间存储索引节点。