时间轮算法HashedWheelTimer处理定时任务

前言

 最近博主在研究蚂蚁金服sofastack平台的sofa-jraft框架,其中涉及到选举部分的定时任务实现HashedWheelTimer,拿出来单独整理一下,其也是netty处理大量连接超时的心跳检测实现。

 

算法描述

关于时间轮算法,有点类似于HashMap。在new 一个HashedWheelTimer实例的时候,可以传入几个参数。

第一,一个时间长度,这个时间长度跟具体任务何时执行没有关系,但是跟执行精度有关。这个时间可以看作手表的指针循环一圈的长度。

然后第二,刻度数。这个可以看作手表的刻度。比如第一个参数为24小时,刻度数为12,那么每一个刻度表示2小时。时间精度只能到两小时。时间长度/刻度数值越大,精度越大。=

然后添加一个任务的时候,根据hash算法得到hash值并对刻度数求模得到一个下标,这个下标就是刻度的位置。

然而有一些任务的执行周期超过了第一个参数,比如超过了24小时,就会得到一个圈数round。

简点说,添加一个任务时会根据任务得到一个hash值,并根据时间轮长度和刻度得到一个商值round和模index,比如时间长度24小时,刻度为12,延迟时间为32小时,那么round=1,index=8。时间轮从开启之时起每24/12个时间走一个指针,即index+1,第一圈round=0。当走到第7个指针时,此时index=7,此时刚才的任务并不能执行,因为刚才的任务round=1,必须要等到下一轮index=7的时候才能执行。

时间轮算法HashedWheelTimer处理定时任务

 

 

测试案例

    /**
     * 每5秒执行一次
     * @param args
     */
    public static void main(String[] args) {
        final Timer timer = new HashedWheelTimer(Executors.defaultThreadFactory(),5,TimeUnit.SECONDS,2);
        TimerTask task = new TimerTask() {
            @Override
            public void run(Timeout timeout) throws Exception {
                System.out.println("task=========>>>>>>>>");
                timer.newTimeout(this,5,TimeUnit.SECONDS);
            }
        };

        timer.newTimeout(task,5,TimeUnit.SECONDS);

    }

 

 

 参考

https://blog.csdn.net/nmgrd/article/details/77199666

https://www.cnblogs.com/eryuan/p/7955677.html

上一篇:Codeforces Round #733


下一篇:SYN4631型PCIe转串口授时卡pcie总线转串口授时