时间轮详解

时间轮详解转载自:https://blog.csdn.net/paxhujing/article/details/52066620问题引入:游戏里面每个Player身上有很多buffs,在每一个tick(最小时间段)都要去检查buff里面的每一个buff是不是过期,产生的效果如何,造成在每个tick里面都去遍历一个长list,明显很不好。怎么优化?1.原始模型:buff的状态在每一个tick里面都要更新!可…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

转载自:https://blog.csdn.net/paxhujing/article/details/52066620

问题引入:游戏里面每个Player身上有很多buffs,在每一个tick(最小时间段)都要去检查buff里面的每一个buff是不是过期,产生的效果如何,造成在每个tick里面都去遍历一个长list,明显很不好。

怎么优化?

1.原始模型:

model1_thumb19

buff的状态在每一个tick里面都要更新!可以想象指针每移动一下,都会非常沉重地拖着所有的BuffList,好可怕……

2. 优化模型1:

我们要避免的是:原始模型在每一个tick里面都要遍历List,那么我们试下以Times为key,在加入buff里时分配好它的结束和启作用的时间属于哪一个Time,

model2_thumb14

这个模型要注意的问题:当要加的Buff起效果已超过了一轮Tick总数时! 比如时间轮总Tick数为12个,现在指针到了tick=2处,要加一个再经过tick为15(起效果)的buff,怎么办?

可以算得:2 + 15%12 = 5,把此buff放到tick=5的槽里面(每个buff都会记录下它的结束时间的),待tick从2跳一轮回到2再跳3下到tick=5,这个buff就会执行。

这个模型完美解决原始模型(每个Tick都遍历整个BuffList)的问题,似乎很完美哦,但是却引入了新的问题,我们的最小tick明显不可能以小时计算,如果我们把Tick划分到秒级别, 一轮就有12*3600 = 43200个key,

假如有一个Buff在每3s就起一个效果:(每3秒加一次血),那么这个buff就会被储存43200/3 = 14400个!!!!如果有大量这种buff,数据冗余就会非常大,储存空间随之也非常大……

要做到保证精度的同时,又保证效率,怎么两全呢?请看模型3.

3. 优化模型3

clock4_thumb14

网上下了个非常cool的时钟图做示例啦:

这就是要用分层时间轮模型:

复制代码
%%% 1.时钟原理说明:
%%% 1.1. 初始化一个三层时间轮:秒刻盘:0~59个SecList, 分刻盘:0~59个MinList, 时刻盘:0~12个HourList;
%%% 1.2. SecTick由外界推动,每跳一轮(60格),SecTick复位至0,同时MinTick跳1格;
%%% 1.3. 同理MinTick每跳一轮(60格),MinTick复位至0,同时HourTick跳1格;
%%% 1.4. 最高层:HourTick跳一轮(12格),HourTick复位至0,一个时间轮完整周期完成.
%%% 2.事件原理说明:
%%% 2.1. 设置时间为TimeOut的事件时,根据TimeOut算出发生此事件时刻的指针位置{TriggerHour,TriggerMin,TriggerSec};
%%% 2.2. 用{TriggerHour,TriggerMin,TriggerSec}与当前指针{NowHour,NowMin,NowSec}对比得出事件存放在哪一个指针(Tick);
%%% 2.3. 所有层的指针每跳到下一格(Tick01)都会触发格子的事件列表,处理每一个事件Event01:
%%% 2.3.1 根据事件Event01的剩余TimeOut算出Event01应该存在上一层(跳得更快)层的位置Pos;
%%% 2.3.2 把事件更新到新的Pos(更新TimeOut);
%%% 2.3.3 重复处理完Tick01里面所有的事件;
%%% 2.3.4 清空Tick01的事件;
%%% 2.3.5 最底层(跳最快)层所有的事件遇到指针Tick都会立即执行;
复制代码

我自己用Erlang实现了一个分层时间轮,有兴趣也可以参观下:)知易行难 欢迎大家用自己善长的语言造个漂亮的轮子,自己亲手写还是可以发现里面很多有意思的细节啦.

https://gist.github.com/zhongwencool/eca6609b59ed635de164




译文:Real-Time Concepts for Embedded Systems Chapter 11 Timer and Timer Services

http://www.embeddedlinux.org.cn/RTConforEmbSys/5107final/LiB0071.html

上面buff的优化思路也是来源于此,非常简单易懂的时间轮概念.

11.6 时间轮(time wheel)

如下图Figure11.11所示:时间轮是一个固定大小的数组结构,这个数组的每一个槽(元素)代表着软定时器的精度,(类似于时钟的最小刻度).时间轮的优点:通过排序的时间列表来有效的更新timers.它能非常效率地安装(instaallation),取消(cancellation)timer.(这2个操作的时间复杂度o(1)).

Figrue11.6_thumb5

Figure 11.11 timing wheel.

软时间设备(soft-timer facility)使用硬时间(hadware timer)来确定一个最小的刻度(tick).基于硬时间周期的timer,驱动着所有安装在这上面的软时间. 超时(timeout)的频率决定着软时间的精度,比如:如果定义tick精度为50ms,每个槽(slot)就代表50ms,这也是可以在这个timer里面安装的最小timeout事件了. 同时,一个双向链表会把timeout的事件处理(event handlers)(也叫callback funciton or callbacks)保存在每一个槽中,当timer 过期(expired)时会触发callbacks调用。所以timers列表也代表着过期时间处理事件列表。每个时间槽描述如图Figure11.12

1112_thumb2

Figure 11.12: Timeout event handlers.

时钟转盘每过一个tick就会指向下一时间(next time),当指针指到数组的最后一个槽时,下一时间又会回到指针最开始的槽。时间轮的概念就来自于此。因此:当安装一个新的事件(time event)时,转盘当前的位置决定了这个新事件到底应该放在哪一个槽,如下图Figure11.13所描述,每经过一个槽代表过去50ms

1113_thumb3

Figure 11.13: Installing a timeout event.

这个时间槽标记了如果有人想安装一个200ms的timeout事件,就可以把这个事件放在++200的槽中,当然这个转盘的起始位置在槽的开始位置(图中clock dial指的位置),换句话说:当转盘(clock dial)指向最开始的槽时,这个事件处理就会返回应该是数组的下标(index).

11.6.1 问题(Issues)

上面这个时间轮方法存在的系列的问题:

问题1: 槽的数量是有限的(也许不同的系统会有不同的限制),比如:你可以在Figure11.13非常明显地看出来:最大的可处理长度(总槽度)是350ms,当要安装一个400ms的事件时怎么办?这个会引起时间轮溢出,为了解决这个问题:一种方法就是禁止超过范围的事件安装,另一个更好的方法:把这些溢出的事件放在一个统一的事件缓冲(event buffer)里面,等转盘转到下一刻度时就从buffer中取出符合范围的事件,这样这些事件也可以被处理了,你可仔细研究Figure11.14得到答案:

1114_thumb1

Figure 11.14: Timing wheel overflow event buffer.

比如:当转盘位置在0刻度(图中位置1)处时,同时要安装一个400ms的timeout,这个事件必须暂时存在溢出缓冲buffer里面,随着转盘转到+50ms(图中位置2处),就会从缓冲区取出这个事件安装. 同理:500ms的事件也只能是在转盘到+150ms(图中位置3)处才能安装。转盘每指向下一刻时,都会检查这个事件缓冲区,这就要求缓冲区里面的事件列表是正增长,如果这个列表很长,那么新的事件插入时代价会非常大。

问题2:这个时间轮的精度,试想一下:当tick指到time wheel 到开始指向下一个时间刻度前,如又安装一个150ms的事件,那么这个事件是安装在+150ms,还是在+200呢?按平均来讲,出错的概率均等的情况下,那么这个出错可能会延迟或提前最小刻度的一半,在这里就是50ms/2=25ms.

问题3:非常重要的问题:关于callbacks的安装.理论上,每一个Callback都应该在时间过期时同时发生,但是在现实中,这是不可能的,每一个Callback的工作状态都不可预测,因此,执行的每一个callback的长度也不可预测,导致没有方法可以保证一个在很长列表后面的callback会被马上执行,这个问题是不合需求的,不能引放到系统里面。Figure11.15描述了这个问题:

1115_thumb4

Figure 11.15: Unbounded soft-timer handler invocation.

当t1 timeout刚过期时,事件处理函数1马上发生,类似,事件处理函数n会在到过t(n-1)时被触发,由于每一个处理函数的执行长度是不确定的,所有图中x,y是长度也是不定的。

理论上(Ideally),这个时间处理会规定一个处理事件的上限值;比如:当执行到事件处理函数n时距离事件处理函数1开始已超过200ms时,会把没有执行的其它事件忽略掉。这个问题很难,解决方法也是应用程序自己特定的[译注:可以点这里参见Linux下的实现]。

11.6.2 分层时间轮(Hierarchical Timing Wheels)

Figure11.14里面的问题1:溢出问题可以使用分层时间轮的方法解决。

软时间设备需要适应事件在跨越在不同范围的值,这个跨度可以非常大,比如:适应timers 范畴从100ms到5 分钟需要3000((5 × 60 × 10)跨度的时间轮,因为这个时间轮的精度最少要100ms,这也是此时间轮的最小精度啦:

 10 × 100ms = 1 sec
    10 entries/sec
    60 sec = 1 minute
    60 × 10 entries / min 
    因此: 
    5 × 60 × 10 =需要3000个刻度(entries).

一个分层的时间轮就好像一个数字刻盘指针型时钟,用多个时间轮安装在这个分层结构里面,取代上面单一的时间轮。这里面每个时间轮都有自己的粒度(granularity)精度,时间转盘与所有的时间轮联系在一起,当最低层的时间轮转一轮时,上一层的时间轮就转一个单位。使用分层时间轮刚上面的需要3000entries的现在仅需要75(10 + 60 + 5)entries就可以保证timeout从100ms到5分钟。这里用到的多维数组:

 

复制代码
 10 × 100ms = 1 sec
    10 entries/sec
    60 sec = 1 minute
    60 entries / min
    5 entries for 5 minutes
    因此:
    5 + 60 + 10 =只需要75个刻度(entries)
复制代码

1116_thumb4

Figure 11.16: A hierarchical timing wheel

这个模型不仅节省了大量的空间,并且保持着很高的精度和跨度,
Figure11.16说明了这一点。
举个例子:它可能会安装一个2分4秒300ms处timeout事件。首先安装2min,当2分钟发生时,它检查还有4.3s的事件才能timeout,所以它又安装了4s的timeout事件槽,当4s过去后,检查到还有300ms才能timeout,又安装了一个300ms事件,再过300ms,真正的timeout才会被执行.


如果你觉得上面意犹未尽:这里面还有一个大餐哦:

1.关于Linux 下定时器的实现方式分析 http://www.ibm.com/developerworks/cn/linux/l-cn-timers/

2. 浅析 Linux 中的时间编程和实现原理 http://www.ibm.com/developerworks/cn/linux/1308_liuming_linuxtime3/


时间轮是不是很神奇:上面译文有说到:分层模型Figure11.16节省了大量的空间?能说说是怎么做到的么,想想,事件假如说有1000个事件,这些事件的空间怎么也不可以被减少,那么它指的是什么空间呢?

如果你知道,请不要吝啬 :)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187180.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • angular5面试题_大数据面试题

    angular5面试题_大数据面试题Angular更新还是非常快的,目前(2020)的速度是每年2个主版本。网上也有不少面试题,不过很多都是针对老的版本,尤其是AngularJS的。因为最近在看Angular的面试题,所以特意总结一下。下面内容都是基于Angularv8.0以上的。顺便科普一下,Angular最早期的版本,也叫AnugularJS,使用javascript开发;新的版本,才叫Angular,也称为Angular2,使用typescript开发,Angular和AngularJS是不兼容的(当然也有2个版本的集成方案)。

    2022年10月18日
  • 苹果套路直播计算机隐藏版,套路计算器app,套路计算器隐藏官网版app预约 v1.0 – 浏览器家园…

    苹果套路直播计算机隐藏版,套路计算器app,套路计算器隐藏官网版app预约 v1.0 – 浏览器家园…套路计算器隐藏官网版app软件是一款最新人气计算器玩法,大家可以在这里发现非常多有趣的玩法,超级适合大家进行整蛊以及活跃气氛适应的,计算器里面会有各种好玩有趣的公式,帮你计算出各种想要的问题回答,非常类似于星座方面的玩法,说不定可以帮你解决你心中的各种问题疑问,如果你想尝试的话,就赶紧下载体验吧。套路计算器隐藏官网版app软件特色:1、玩法非常简单,输入自己的想要提的问题,就可以自动算出结果!2、…

  • 录制gif工具_GIF录制

    录制gif工具_GIF录制LicecapforMac下载地址下载完成后打开软件,界面如下图。整个软件界面为透明层,左下角可以设置图片FPS,右下角又两个按钮,分别为录制按钮和停止按钮。鼠标移动至软件边框处可以改变软件界面大小,这个大小就是你将要录制的界面大小。点击右下角record录制按钮,选择保存位置后,开始录制。点击录制按钮后,软件透明区域中的模拟器变为了可操作区域,进行一些操作后,点击stop停止按钮。在保存位置处生成一张gif图片。注意:发现无法录屏,可以通过设置打开录屏权限…

  • vim乱码恢复_linux保存退出命令

    vim乱码恢复_linux保存退出命令初始时,安装好Ubuntu以后,使用Vim退出以后会显示乱码,这是由于Ubuntu的Vim默认是链接到了/usr/bin/gnome,这是不同于一般使用习惯的Vim,所以我们如果需要使用一般习惯的Vim,并且解决Vim退出以后的乱码问题,我们必须使Vim链接到我们常用的Vim.basic,步骤如下:1.使用apt-get安装Vim包,系统默认安装的是Vim-gnome包,命令如下:sud

  • Wannacry(永恒之蓝)病毒「建议收藏」

    Wannacry(永恒之蓝)病毒「建议收藏」一、Wannacry(永恒之蓝)病毒2017.04-051)一种“蠕虫式”的勒索病毒软件,大小3.3MB,勒索病毒肆虐。2)由不法分子利用NSA(美国国家安全局)泄露的危险漏洞“EternalBlue”(永恒之蓝)进行传播。3)中国部分Windows操作系统用户遭受感染,校园网用户首当其冲,受害严重,大量实验室数据和毕业设计被锁定加密。部分大型企业的应用系统和数据库文件被加密后,无法正常工作,影响巨大。4)文件被加密,要求支付高比特币。5)比特币:比特币是一种P2P形式的虚拟的加密数字货币

    2022年10月17日
  • 50分钟学会Laravel 50个小技巧(基于laravel5.2,仅供参考)

    50分钟学会Laravel 50个小技巧(基于laravel5.2,仅供参考)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号