# TimeWheel

**Repository Path**: Createtree/timewheel

## Basic Information

- **Project Name**: TimeWheel
- **Description**: TimeWheel lib for C
- **Primary Language**: C
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2023-04-03
- **Last Updated**: 2024-11-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# TimeWheel

## Overview

### 1.时间轮的简单介绍

时间轮(TimeWheel)作为一种高效率的计时器实现方案，在1987年发表的论文[Hashed and Hierarchical Timing Wheels](https://dl.acm.org/doi/10.1145/37499.37504 "Hashed and hierarchical timing wheels: data structures for the efficient implementation of a timer facility")中被首次提出。
其被发明的主要目的在于解决当时操作系统的计时器功能实现中，维护一个定时器的开销随着所维护定时器数量的增多而逐渐变大的问题(时间复杂度为：O(n)、O(log n))。
这导致操作系统无法同时高效的维护大量计时器，进一步导致一些优秀的、需要使用到大量定时器的的网络协议、实时控制系统等程序的实际表现不尽人意。

### 2.传统的计时器功能实现方式

计时器作为一种普遍的需求，理解起来是很简单的。计时器主要由两部分组成，即用户指定一个任务(task)，并在等待指定的时间(delayTime)后task将会被回调执行。
在时间轮算法被发明出来之前，操作系统计时器功能的实现方式主要可以分为两种：基于无序队列和基于有序队列。

#### 基于无序队列实现的计时器

新创建的计时器直接放在队列的末尾，时间复杂度为O(1)。
在每次硬件时钟tick中断时(per tick)，遍历当前队列中所有的计时器，将当前时间下过期的计时器移出队列并调度执行task,时间复杂度O(n)。
基于无序队列的计时器中，所维护的计时器总数量越多，则每次硬件时钟中断时的处理流程开销越大，最坏情况下甚至无法在一次时钟tick的间隔内完成计时器队列的遍历。

#### 基于有序队列实现的计时器

有序队列下，所有计时器按照过期时间进行排序，新创建的计时器加入队列时的时间复杂度为O(log n)(通常使用完全二叉堆来实现有序队列)。
在每次硬件时钟tick中断时，仅检查队列的头部元素(最早过期的任务)是否过期。如果未过期则直接结束，如果已过期则将队首元素出队调度task，并再次重复上述过程，直至最新的队首元素不过期或队列为空。平均时间复杂度为O(1)。
基于有序队列的计时器中，所维护的计时器总数量越多，则每次用户创建新的计时器时的延迟越高，在需要反复创建大量计时器的场合下，性能不佳
可以看到，在基于队列的计时器模块运行时，最关键的两个功能(创建新计时器/处理每次tick)至少有一个会随着总计时器数量的增大，而引起性能大幅度的下降。

> 引用来源：[时间轮工作原理解析](https://www.cnblogs.com/xiaoxiongcanguan/p/17128575.html "博客-时间轮工作原理解析")

## Feature

- 可以自由设定不同的时间轮级数和刻度数。
- 虽然插入新的定时器时间复杂度为O(1)但是在多级时间轮之间轮转时会有CPU消耗。
- 开放了所有数据结构和接口，并且所有接口都是可重入的，可以通过进一步封装来简化操作。

## Usage

### 创建时间轮

使用 `tw_create_twb()`函数创建一个时间轮。该函数需要三个参数：

* `levelMax`：时间轮层级数目；
* `levelx`：各层级的刻度数目，是一个长度为 `levelMax`的数组，每个元素表示该层级上的刻度数目(2^n)；
* `TickFrequence`：时间轮的运行频率，单位为Hz。

```C
uint8_t levelx[3] = {8, 8, 8}; // 24位三级时间轮，每级包含2^8个刻度
twb_t* twb = tw_create_twb(3, levelx, 1000); // 创建时间轮，时钟频率为1kHz
```

> 24位三级时间轮可以表示2^(8+8+8) = 33,554,432个时刻。
> Tips：时间轮最大为32位，层级数可以任意，但是位数不能超过32

### 创建定时任务

使用 `tw_task_create()`函数创建一个定时任务。该函数需要五个参数：

* `ptwb`：时间轮对象；
* `ticktime`：定时任务的刻度时间，最小延时1Tick，使用 `tw_tick2ms(tick)` 转换为ms；
* `function`：定时任务的处理函数；
* `param`：定时任务的参数；
* `id`: 定时器任务的ID。

```C
uint32_t task_function(void* param)
{
    printf("Time's up!\n");
    return 0;
}

twTick_t ticktime = 10; // 10Tick后执行
twStatus status = tw_task_create(twb, ticktime, task_function, NULL, 1);
if (status != TW_OK) {
    printf("Failed to create task!\n");
}
```

> TimeWheel根据返回值来重新安排下一次调用的时间(tick)。
> 返回0表示一次性任务。
>
> tips: 使用 `tw_ms2tick()/tw_tick2ms()` 将ms和tick转换

### 修改定时任务传入的参数

通过ID找到任务并传入参数：

```C
tw_task_set_param_id(twb, id, &data);
```

通过twt句柄找到任务并传入参数：

```C
twt_t *twt = tw_task_find_id(twb, id);
tw_task_set_param(twt, &data);
```

> 如果保存过twt句柄使用 `tw_task_set_param()` 更高效，但是这种方式需要注意twt是否已经释放。

由于传入定时器任务的参数是 `void *` 指针，访问时应当根据实际传入的参数来转换类型再访问，下面是一个例子：

```C
uint32_t example_task(void *pdata)
{
    int *value = (int*)pdata;
    printf("data:%d\n", *value);
}
```

> `pdata` 指向的数据可能在外部被修改

### 运行时间轮

使用 `tw_run()`函数运行时间轮。该函数需要一个参数：

* `ptwb`：时间轮对象。

```C
tw_run(twb); // 开始运行时间轮
```

> 需要定时调用，频率为 `twb.frequence`

### 销毁时间轮

使用 `tw_destroy_twb()`函数销毁时间轮。该函数需要一个参数：

* `pptwb`：时间轮对象的指针。

```C
tw_destroy_twb(&twb); // 销毁时间轮
```

### 更多用法请参考源文件中的注释

## Update Log

### v1.0

* [X] 基本操作接口
* [X] 所有接口的单元测试
* [X] 通过Visual Studio检查内存泄漏