少年击剑更吹箫,剑气箫心一例消。这篇文章主要讲述Linux(程序设计):63---高性能定时器之时间轮相关的知识,希望能为你提供帮助。
一、时间轮概述
- 前面的文章(javascript:void(0))我们设计了一个基于排序链表的定时器存在一个问题:那就是添加定时器的效率偏低
- 本文我们介绍一种高性能定时器——时间轮
时间轮结构分析
- 此处的时间轮属于简单的时间轮,复杂的时间轮可能有多个轮子,不同的轮子可能拥有不同的粒度。相邻的两个轮子,精度高的转一圈,精度低的仅往前移动一槽,就像水表一样
文章图片
- 实线的指针指向轮子上的一个槽(slot)
- 实线的指针以恒定的速度顺时针转动,每转动一步就指向下一个槽(虚线的指针指向的槽),每次转动称为一个滴答(tick),一个滴答的时间称为时间轮的槽间隔si(slot interval),它实际上就是心搏时间
- 每条链表上的定时器有相同的特征:它们的定时时间相差N*si的整数倍。时间轮正是利用这个关系将定时器散列到不同的链表中
- 定时器的插入:假设现在的指针指向槽cs,我们要添加一个定时时间为ti的定时器,则该定时器将被插入槽ts(timer slot)对应的链表中:ts = ( cs + (ti/si) ) %N
-
时间轮的特点:
- 1.前面文章介绍的定时器链表使用一条唯一的链表来管理所有的定时器,插入操作的效率会随着定时器数目的增多而降低。而时间轮使用哈希表的思想,将定时器散列到不同的链表上。这样每条链表上的定时器数目都将明显少于原来的排序链表上的定时器数目,插入操作的效率基本不受定时器数目的影响
- 2.对于时间轮而言,要提到定时精度,就要是si值足够小;要提到执行效率,则要求N值足够大
【Linux(程序设计):63---高性能定时器之时间轮】
推荐阅读
- Linux(内核剖析):26---中断下半部之(工作队列机制(workqueue_structcpu_workqueue_struct))
- Linux(内核剖析):23---中断下半部之(下半部总体概述)
- Linux(内核剖析):05---进程之进程的创建与终结(forkvforkexit)
- Linux(内核剖析):22---中断之中断控制接口(禁止/激活/屏蔽中断)
- Linux(内核剖析):19---中断总体概述
- Linux(内核剖析):07---进程调度总体概述(多任务系统策略时间片)
- Linux(程序设计):62---定时机制之I/O复用系统调用的超时参数
- Linux(内核剖析):18---内核数据结构总结(数据结构选择与算法复杂度分析)
- Linux(程序设计):61---定时机制之SIGALRM信号(附升序的定时器链表设计定时器链表处理非活动连接)