<返回更多

.Net 之时间轮算法(终极版)

2022-07-05    交流科技圈
加入收藏

关于时间轮算法的起始

我也认真的看了时间轮算法相关,大致都是如下的一个图

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述 个人认为的问题

大部分文章在解释这个为何用时间轮的时候都再说

 

为什么要用时间轮实现

  1. 1. 通常用于实现linux内核任务、游戏类的buf计时。
  2. 2. 单个时间轮局限性:保存的任务数量少,不能超过当前时间轮。
  3. 3. 多层时间轮,典型:日-时-分-秒
  4. 4. 传统JAVA实现定时:Timer,只能单线程,会阻塞;Executors.newScheduledThreadPoll, 使用的最小堆来实现,任务还是不能太多,添加时间复杂度为O(logn)

时间轮定时器最大的优点

  1. 1. 是任务的添加与移除,都是O(1)级的复杂度;
  2. 2. 不会占用大量的资源;
  3. 3. 只需要有一个线程去推进时间轮就可以工作了
 
privateTask[很长] tasks;

publicList<Task> getTaskList( longtimestamp) {

returntask. get(timestamp)

}

// 假装这里真的能一毫秒一个循环

publicvoidrun{

while( true){

getTaskList(System.currentTimeMillis).后台执行

Thread.sleep( 1);

}

}

假如这个数组长度达到了亿亿级,我们确实可以这么干。那如果将精度缩减到秒级呢?我们也需要一个百亿级长度的数组。

先不说内存够不够,显然你的定时器要这么大的内存显然很浪费。

基于个人的理解对其进行改造和实现

对于以上的描述,我自己还是很不认同的,我为啥要声明这么大的数组,难道不能有一个任务,我就放一个任务么,实际数组的长度应该是你任务数的长度吧。

要不然,为啥要这么浪费。想不通,可能还有别的解释,谁有答案可以告诉我。

在实际的使用中,一般都为秒级,毫秒级都很少,因为毫秒级的不准。

所以,我可以根据这些通过hash字典构建一个 这样的时间轮算法,也作为我自己想实现定时任务框架的一部分。

逻辑:核心为一个字典,key 为时间戳,值为任务列表。整体就是每个添加的任务都有一个触发的时间(秒),到了这个秒,时间就会触发,自然会去执行相关的任务。有了任务才会添加,不会任何任务都添加的。任务触发的时候,会获取任务下一次执行的时间,并插入到任务列表里。

static void Main( string[] args)

{

ScheduledTask scheduledTask = newScheduledTask( => { Console.WriteLine( $" {DateTime.Now}" ); }, newTimeSpan( 0, 0, 5));

TimeWheel timeWheel = newTimeWheel;

timeWheel.AddTask(scheduledTask);

timeWheel.Run;

Console.WriteLine( "开始运行时间轮!");

Console.ReadLine;

} ///<summary>

///时间轮算法(终极)实现

///大部分都是支持秒级,所以,按照秒级进行实现

///</summary>

publicclassTimeWheel

{

///<summary>

///任务列表

///</summary>

publicConcurrentDictionary< long, List<IScheduledTask>> Tasks = new;

publicvoidRun

{

while( true)

{

varnow = DateTime.Now;

Task.Run( => { Trigger(now); });

varoffset = 500- now.Millisecond;

SpinWait.SpinUntil( => false, 1000+ offset);

}

}

publicvoidTrigger(DateTime dateTime)

{

vartimeStamp = GenerateTimestamp(dateTime);

varoldTimeStamp = timeStamp - 1;

Tasks.TryRemove(oldTimeStamp, outvar_);

Tasks.TryGetValue(timeStamp, outvarresult);

if(result?.Any == true)

{

foreach( varitem inresult)

{

Task.Run(item.GetAction);

varNewTime = item.GetNextTime;

if(NewTime.HasValue)

{

AddTask(NewTime.Value, item);

}

}

}

}

publicvoidAddTask(IScheduledTask scheduledTask)

{

vartimeStamp = GenerateTimestamp(scheduledTask.GetNextTime.Value);

Tasks.AddOrUpdate(timeStamp, newList<IScheduledTask> { scheduledTask }, (k, v) =>

{

v.Add(scheduledTask);

returnv;

});

}

publicvoidAddTask(DateTime dateTime, IScheduledTask scheduledTask)

{

vartimeStamp = GenerateTimestamp(dateTime);

Tasks.AddOrUpdate(timeStamp, newList<IScheduledTask> { scheduledTask }, (k, v) =>

{

v.Add(scheduledTask);

returnv;

});

}

privatelongGenerateTimestamp(DateTime dateTime)

{

returnnewDateTimeOffset(dateTime.ToUniversalTime).ToUnixTimeSeconds;

}

privateDateTime GetDatetime( longtimeStamp)

{

vard = DateTimeOffset.FromUnixTimeSeconds(timeStamp);

returnd.LocalDateTime;

}

} publicinterfaceIScheduledTask

{

publicAction GetAction;

publicDateTime? GetNextTime;

}

///<summary>

///定时器任务,普通任务

///间隔指定的时间

///</summary>

publicclassScheduledTask: IScheduledTask

{

privateAction _action;

privateTimeSpan timeSpan;

publicScheduledTask(Action action, TimeSpan timeSpan)

{

this._action = action;

this.timeSpan = timeSpan;

}

publicAction GetAction

{

returnthis._action;

}

publicDateTime? GetNextTime

{

returnDateTime.Now.AddSeconds(timeSpan.TotalSeconds);

}

}

最后的效果

在这里插入图片描述

当然,也可以通过CRON表达式来实现更为高级的。

后期再来个更高级一点的。 github地址

https://github.com/kesshei/TimeWheelDemo

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>