关于任务调度有多种方式实现,常见的像Timer,ScheduledThreadPoolExecutor,以及时间轮
Timer原理
timer底层主要是依靠最小堆排序,把任务封装并存储在一个优先级队列中,这个队列底层还是依靠数组和最小堆排序构成。
Timer timer = new Timer();
timer.schedule(new java.util.TimerTask() {
@Override
public void run() {
System.out.println("1");
}
},1,1);
每次任务提交都要进行一次排序,把延迟时间最短的放在最上边,内部有一个线程不断从队列中获取任务
内部线程的run方法内部每次拿到最小时间的任务,和当前时间比较如果执行时间小于等于当前时间,把taskFired置为true,然后进行判断看是否有那种间隔时间在执行,如果有就再次入队列进行排序.如果不指定默认period为0,只执行一次。如果执行时间还未到就调用wait方法阻塞当前执行任务的线程
每次任务提交时会进行判断如果提交的任务是最小的任务就唤醒此线程这中方法虽然可以完成简单的任务调度但是如果代码报错或者某个任务执行时间过长会导致不能及时的执行。最耗费性能的地方在于每次添加都要进行排序影响性能
ScheduledThreadPoolExecutor原理
底层同样是采用最小堆排序不同的是采用了线程池可以解决单个任务执行时间过长和执行任务异常的情况。但是由于任务的存储采用最小堆排序所以插入和排序都要耗费一定性能
HashedWheelTimer原理
我们可以采用数组实现逻辑的环形结构,每一格代表固定时间,比如一格代表一分钟,只需要把对应的任务构成一个双向链表进行存储。例如一个任务需要15分钟后执行,那么它要放在15对8取模的位置。同时还要维护一个圈数。此时内部线程只需要按时遍历数组同时遍历对应数组的Task链表取出需要执行的任务。
首先要建立一个时间轮对象,HashedWheelTimer.参数分别代表每一格代表的时间,以及时间单位,以及时间轮的大小
这里的大小最终会被调整为离此数字最大的2的整数倍。因为这里涉及到一个取模运算,任何一个数字对2的整数倍取模都等于对2的整数倍减一进行按位与运算,由于位运算效率是大于除法取模运算的,而且可以让Hash散列比较均匀。
首先内部线程的run方法
HashedWheelBucket是数组的类型,其内部维护了一个任务链表。wheel代表创建的数组
重点在于final long deadline = waitForNextTick()方法内部
startTime是线程启动时间每次调用此方法tick都会加一相当于指针移动了一格。其实这里的currentTime代表的是线程运动的总时间。当deadline小于currentTime时说明已经改向下一个时间格子移动了
紧接着run方法内部的transferTimeoutsToBuckets()方法会把任务从队列中拿出
可以看到内部根据时间进行圈数的计算和格子的计算,并添加到对应的格子任务中
再接下来就是run方法处理任务了bucket.expireTimeouts(deadline)
内部遍历每一个任务进行圈数和执行时间的判断是否执行
不过此实现方式的缺点就是如果任务过长就会导致不能按时的执行,但解决了最小堆排序性能占用问题