c++7f52bad3afa7a7c5a0678ccb6645>定时器，是一个比较常见的组件。单就服务端来说，框架层面须要利用定时器来做会话的超时，应用层面须要利用定时器来处理一些跟时间有关的业务逻辑。对于游戏这些大量需求定时器的业务，一个简单高效的定时器组件是必不可少的。
定时器组件的实现可以分为两部份：
第一部份比较简单，并且实现方法多种多样，但是基本都是跟语言相关的，因而并不是本文重点。所谓具象成的概念似乎就是指使用者怎样来用。
【文章福利】小编在群文件上传了一些个人认为比较好得学习书籍、视频资料，有须要的可以进群【977878001】领取！！！额外附赠一份价值699的内核资料包（含视频教程、电子书、实战项目及代码）
内核资料直通车：Linux内核源码技术学习路线+视频教程代码资料
学习直通车（腾讯课堂免费报考）：Linux内核源码/显存调优/文件系统/进程管理/设备驱动/网路合同栈
第二部份其实比起第一部份须要更多的代码量，并且实现方法很有限。
这些模型用处就是简单，找个学过数据结构的结业生能够写下来，不容易有bug。add的时间复杂度是n(lgn)，timeout的时间复杂度也是n(lgn)。
然而，假定我们的业务系统假如面对的是这样的需求：短期内注册了大量短时间内就要timeout的timer。很其实，最小堆的实现就有点难堪了。
下边步入正文，小说君就介绍下我们在应用层怎样实现一个linux内核风格的定时器。语言以C#为例。
为了做性能对比，我们要先实现一个基于最小堆的定时器管理器，最小堆的插口如下linux 应用定时器，具体实现就不港了，虽然是最基础的数据结构。
public class PriorityQueue : IEnumerable
{
public PriorityQueue(IComparer comparer);
public void Push(T v);
public T Pop();
public T Top();
}
public interface ITimeManager
{
ITimer AddTimer(uint afterTick, OnTimerTimeout callback, params object[] userData);
FixedTick();
}
public class TrivialTimeManager : ITimeManager
{
// ...
}
之后是linux内核风格定时器的管理器实现。首先有一个设计前提：
我们须要用tick来定义整个系统的时间精度下限。例如说对于游戏来说，10ms以下的精度不须要care，因而我们可以把tick的宽度定为10ms。也就是说先挂起来的WaitFor(8ms)和后挂起来的WaitFor(5ms)，有可能是后者先timeout的。一个tick为10ms，这么一个32bit的tick能抒发的时间细度就有将近500天嵌入式linux培训，远超过一个服务器组不重启的时间了。
虽然这些定时器实现，就是由于这个抉择，在面对之前提到的问题时，方才具有了更佳的性能表现。每次按照tick领到timeout数组，直接dispatch，领到这个数组的时间是一个常数，而最小堆方式领到这个数组须要的时间是m*lgn。
因为空间有限，我们不可能做到每位即将timeout的tick都有对应的数组。考虑到虽然80%以上的timer的时间都不会超过2.55s，我们只针对前256个tick做这些优化举措即可。
那怎么处理注册的256tick以后的timer？我们可以把时间还比较长的timer置于更粗细度的数组中，等到还剩下的tick数大于256以后再把她们取下来重新整理一下数组能够搞定。
假如我们保证每一次tick都严格的做到：
保证这两点，就须要每位tick都对所有数组做一次整理。这样就得不偿失了，所以这儿有个trade-off，就是我通过一个表针(index)，来标记我当前处理的position，每过256tick是一个cycle，才进行一次整理。而整理的成本就通过分摊在256tick中，增加了实际上的单位时间成本。
概念比较具象，接出来贴一部份代码。
常量定义：
public const int TimeNearShift = 8; public const int TimeNearNum = 1 << TimeNearShift;// 256 public const int TimeNearMask = TimeNearNum - 1;// 0x000000ff public const int TimeLevelShift = 6; public const int TimeLevelNum = 1 << TimeLevelShift;// 64 public const int TimeLevelMask = TimeLevelNum - 1;// 00 00 00 (0011 1111)
基础数据结构：
using TimerNodes = LinkedList; private readonly TimerNodes[TimeNearNum] nearTimerNodes; private readonly TimerNodes[4][TimeLevelNum] levelTimerNodes;
相当于是256+4*64个timer数组。
tick有32位，每一个tick只会timeout掉expire与index相同的timer。
循环不变式保证near表具有这样几个性质：
level表有4个，分别对应9到14bit，15到20bit，21到26bit，27到32bit。
因为原理都类似，我这儿拿9到14bit的表来说下循环不变式：
有了数据结构和循环不变式，前面的代码也就容易理解了。主要列一下AddTimer的逻辑和Shift逻辑。
private void AddTimerNode(TimerNode node)
{
var expire = node.ExpireTick;
if (expire < index)
{
throw new Exception();
}
// expire 与 index 的高24bit相同
if ((expire | TimeNearMask) == (index | TimeNearMask))
{
nearTimerNodes[expire & TimeNearMask].AddLast(node);
}
else
{
var shift = TimeNearShift;
for (int i = 0; i < 4; i++)
{
// expire 与 index 的高bit相同
var lowerMask = (1 <> shift)&TimeLevelMask].AddLast(node);
break;
}
shift += TimeLevelShift;
}
}
}
private void TimerShift()
{
// TODO index回绕到0的情况暂时不考虑
index++;
var ct = index;// mask0 : 8bit
// mask1 : 14bit
// mask2 : 20bit
// mask3 : 26bit
// mask4 : 32bit
var partialIndex = ct & TimeNearMask;
if (partialIndex != 0)
{
return;
}
ct >>= TimeNearShift;
for (int i = 0; i >= TimeLevelShift;
continue;
}
ReAddAll(levelTimerNodes[i], partialIndex);
break;
}
}
以上代码用c/c++重画后尝尝鲜味更佳。
实现大约就是这种了，接出来我们测一下究竟linux内核风格定时器比最小堆实现的定时器快了多少。
建立的测试用例和测试方式：
static IEnumerable BuildTestCases(uint first, uint second)
{
var rand = new Random();
for (int i = 0; i < first; i++)
{
yield return new TestCase()
{
Tick = (uint)rand.Next(256),
};
}
for (int i = 0; i < 4; i++)
{
var begin = 1U << (8 + 6*i);
var end = 1U << (14 + 6*i);
for (int j = 0; j < rand.Next((int)second * (4 - i)); j++)
{
yield return new TestCase()
{
Tick = (uint)rand.Next((int)(begin+end)/2),
};
}
}
}
{
var maxTick = cases.Max(c => c.Tick);
var results = new HashSet();
foreach (var c in cases)
{
TestCase c1 = c;
mgr.AddTimer(c.Tick, (timer, data) =>
{
if (mgr.FixedTicks == c1.Tick)
results.Add((uint) data[0]);
}, c.Id);
}
var begin = DateTime.Now;
for (int i = 0; i < maxTick+1; i++)
{
mgr.FixedTick();
}
var end = DateTime.Now;
}
建立测试用例时的参数first指大于等于256tick的timer数目，second是指小于256tick的timer数目。
first固定为一千万的测试结果：
加速比的波动不是非常显著，而且假如second继续降低，linux内核定时器的加速比实际上还是会因为shift频度的提高而逐渐增加。
second固定为1000的情况：
跟第一次测试的推论差不多，256tick以内的timer占比越高，相比最小堆定时器的优势越大。
最终结论，linux内核定时器比起最小堆定时器的优势还是很显著的，大部份情况下都有2倍以上的性能表现，强烈建议采用。
此次的代码放到github上linux 应用定时器，并且因为订阅号文章里没办法放链接linux软件，只要后台给小说君发消息「定时器」就会手动回复github链接。这个项目里不仅有一个工业级的linux风格定时器实现代码，还有小说君实现的一套基于这个定时器的Unity3D风格的Coroutine。
--内核技术英文网-建立全省最权威的内核技术交流分享峰会
原文地址：了解Linux内核风格的定时器实现-操作系统-内核技术英文网-建立全省最权威的内核技术交流分享峰会（版权归原作者所有，侵删）
