java.util.concurrent.Timer.ScheduledThreadPoolExecutor..

目录

简介

定时器在实际应用中是一种非常常用和有效的工具。其原理是将要执行的任务按照执行时间的顺序进行排序,然后在特定的时间执行。 JAVA提供了java.util.Timer、java.util.concurrent.ScheduledThreadPoolExecutor等多种Timer工具,但是这些工具在执行效率上还是存在一些缺陷,所以netty提供了HashedWheelTimer,一个优化的Timer类。

让我们看看 Netty 的 Timer 有何不同。

java.util.Timer

Timer 是由 JAVA 在 1.3 中引入的。所有的任务都存放在里面的TaskQueue中:

private final TaskQueue queue = new TaskQueue();

TaskQueue的底层是一个TimerTask数组,用来存放待执行的任务。

private TimerTask[] queue = new TimerTask[128];

看起来 TimerTask 只是一个数组,但 Timer 使这个队列成为一个平衡的二进制堆。

添加TimerTask时,会插入到Queue的尾部,然后调用fixup方法进行rebalance:

    void add(TimerTask task) {
        // Grow backing store if necessary
        if (size + 1 == queue.length)
            queue = Arrays.copyOf(queue, 2*queue.length);
        queue[++size] = task;
        fixUp(size);
    }

当正在运行的任务从堆中移除时,会调用fixDown方法进行重新平衡:

    void removeMin() {

        queue[1] = queue[size];
        queue[size--] = null;  // Drop extra reference to prevent memory leak
        fixDown(1);
    }

fixup的原理是比较当前节点和它的父节点。如果小于父节点,则与父节点交互,然后遍历流程:

    private void fixUp(int k) {
        while (k > 1) {
            int j = k >> 1;
            if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

fixDown的原理是比较当前节点与其子节点,如果当前节点大于子节点,则降级:

    private void fixDown(int k) {
        int j;
        while ((j = k << 1)  0) {
            if (j  queue[j+1].nextExecutionTime)

                j++; // j indexes smallest kid
            if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

二叉平衡堆的算法这里就不详细描述了。您可以自行查找相关文章。

java.util.concurrent.ScheduledThreadPoolExecutor

虽然Timer非常好用,线程安全,但是对于Timer来说,如果要提交任务,需要创建一个TimerTask类来封装具体的任务,不是很通用。

所以JDK在5.0中引入了一个更通用的ScheduledThreadPoolExecutor,它是一个使用多个线程执行特定任务的线程池。当线程池中的线程数等于1时,ScheduledThreadPoolExecutor相当于Timer。

ScheduledThreadPoolExecutor 将任务存储在 DelayedWorkQueue 中。

DelayedWorkQueue 是一种基于堆的数据结构,类似于 DelayQueue 和 PriorityQueue。

由于堆需要不断地重新平衡 siftUp 和 siftDown 操作,所以它的时间复杂度是 O(log n)。

以下是DelayedWorkQueue的shiftUp和siftDown的实现代码:

       private void siftUp(int k, RunnableScheduledFuture key) {
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                RunnableScheduledFuture e = queue[parent];
                if (key.compareTo(e) >= 0)
                    break;

图片[1]-java.util.concurrent.Timer.ScheduledThreadPoolExecutor..-唐朝资源网

queue[k] = e; setIndex(e, k); k = parent; } queue[k] = key; setIndex(key, k); } private void siftDown(int k, RunnableScheduledFuture key) { int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; RunnableScheduledFuture c = queue[child]; int right = child + 1; if (right 0) c = queue[child = right]; if (key.compareTo(c) queue[k] = key; setIndex(key, k); }

HashedWheelTimer

因为Timer和ScheduledThreadPoolExecutor的底层都是基于堆结构的。 ScheduledThreadPoolExecutor虽然对Timer进行了改进,但是两者的效率差不多。

那么有没有更有效的方法呢?比如O(1)有没有可能实现?

我们知道Hash可以实现高效的O(1)查找,想象一下如果我们有一个无限滴答的时钟,然后将要执行的任务按照间隔时间的顺序分配给这些滴答,每当时钟移动一个秤,就可以执行这个秤中的相应任务,如下图:

这种算法称为简单计时轮算法。

但是这个算法是理论上的,因为不可能为所有间隔长度分配相应的刻度。这会消耗大量的无效内存空间。

所以我们可以做一个妥协,先对区间的长度进行散列。这样可以缩短间隔时间的基数,如下图所示:

本例中,我们选择8为底,区间除以8,余数作为hash位置,商作为节点的值。

每次遍历和轮询节点时,将节点的值减一。当节点的值为0时,表示该节点可以被获取并执行。

此算法称为 HashedWheelTimer。

netty 提供了这个算法的实现:

public class HashedWheelTimer implements Timer 

HashedWheelTimer使用HashedWheelBucket数组来存储具体的TimerTask:

private final HashedWheelBucket[] wheel;

图片[2]-java.util.concurrent.Timer.ScheduledThreadPoolExecutor..-唐朝资源网

先看一下创建轮子的方法:

    private static HashedWheelBucket[] createWheel(int ticksPerWheel) {
        //ticksPerWheel may not be greater than 2^30
        checkInRange(ticksPerWheel, 1, 1073741824, "ticksPerWheel");
        ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);
        HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];
        for (int i = 0; i < wheel.length; i ++) {
            wheel[i] = new HashedWheelBucket();
        }
        return wheel;
    }

我们可以自定义wheel中刻度的大小,但是ticksPerWheel不能超过2^30。

然后将ticksPerWheel的值调整为2的整数倍。

然后创建一个包含 ticksPerWheel 元素的 HashedWheelBucket 数组。

这里需要注意的是,虽然整体轮子是哈希结构,但是轮子中的每个元素,即HashedWheelBucket,都是链式结构。

HashedWheelBucket 中的每个元素都是一个 HashedWheelTimeout。 HashedWheelTimeout 中有一个 remainingRounds 属性,用来记录 Timeout 元素会在 Bucket 中保留多长时间。

long remainingRounds;

总结

netty中的HashedWheelTimer可以实现更高效的Timer功能,我们用一下吧。

更多信息请参考

最流行的解读,最深刻的干货,最简洁的教程,还有很多你不知道的小技巧等你来发现!

© 版权声明
THE END
喜欢就支持一下吧
点赞101 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片