参考文章:
数据结构&算法-----（2）高级数据结构
中堆的部分
定时任务中每一个任务Job都对应堆中的一个节点, 对应定时任务的到期时间
Delay 延迟时间 到期时间
每次取堆顶元素执行
注意:
在添加/删除元素时候需要保证根节点 最大/最小
① 向堆中添加元素
② 取出堆中的最大 / 最小 (堆顶) 元素
使用链表or数组实现
思考: 删除堆顶元素中的下沉操作, 在树的节点很多的时候会比较耗性能. 而且在定时任务中取任务是一个很频繁的操作
下沉其实是为了取出小顶堆中最小元素, 每次下沉进行元素比对会造成性能浪费
参考文章:
那些惊艳的算法们（三）—— 时间轮
while-true-sleep
核心思想: 我只需要把任务放到它需要被执行的时刻，然后等着时针转到这个时刻时，取出该时刻放置的任务，执行就可以了
遍历数组, 每个下标放置一个链表, 链表节点放置任务, 遍历到了就取出执行
多一个维度: 分 / 秒 / 天…, 刻度会成倍的增加
任务上记录一个round, 遍历到了就将 round-1, 为0时取出执行就可以了
但是需要遍历所有的任务, 效率较低
cron表达式的底层原理
使用多个不同时间维度的轮, 天轮: 记录几点执行; 月轮, 记录几号执行
月轮遍历到了, 将任务取出放到天轮里边, 即可以实现几号几点执行
分层时间轮: 避免遍历所有元素
public class Timer {
// 用于存放任务, 小顶堆, getMin方法取出任务
private final TaskQueue queue = new TaskQueue();
// 用于执行任务的线程
private final TimerThread thread = new TimerThread(queue);
// 调用start()方法, 触发多线程执行. 以多线程形式运行 TimerThread 中的 run 方法
// 注意: 并不是多线程运行业务逻辑, 业务逻辑在TimerTask里面
public Timer(String name) {
thread.setName(name);
thread.start();
}
// schedule方法会触发调用
private void sched(TimerTask task, long time, long period) {
if (time < 0)
throw new IllegalArgumentException("Illegal execution time.");
if (Math.abs(period) > (Long.MAX_VALUE >> 1))
period >>= 1;
synchronized(queue) { // 锁了一下任务队列
if (!thread.newTasksMayBeScheduled)
throw new IllegalStateException("Timer already cancelled.");
synchronized(task.lock) { // Task可以往多个Timer加, 使用双重校验
if (task.state != TimerTask.VIRGIN)
throw new IllegalStateException(
"Task already scheduled or cancelled");
task.nextExecutionTime = time;
task.period = period;
task.state = TimerTask.SCHEDULED;
}
queue.add(task); // 将task放入queue, 调用notify唤醒队列
if (queue.getMin() == task)
queue.notify();
}
}
// 有多个重载, 可以指定确定的时间也可以指定相对的时间
public void schedule(TimerTask task, Date firstTime, long period) {
if (period <= 0)
throw new IllegalArgumentException("Non-positive period.");
sched(task, firstTime.getTime(), -period);
}
// schedule和scheduleAtFixedRate区别:
// schedule 预设的执行时间 nextExecutTime 12:00:00, 12:00:02, 12:00:04
// schedule 真正的执行时间 取决上一个任务的结束时间 ExecutTime 03 05 08 丢任务（少执行了次数）
// scheduleAtFixedRate 严格按照预设时间 12:00:00 12:00:02 12:00:04（执行时间会乱）
public void scheduleAtFixedRate(TimerTask task, Date firstTime, long period) {
if (period <= 0)
throw new IllegalArgumentException("Non-positive period.");
sched(task, firstTime.getTime(), period);
}
}
class TimerThread extends Thread {
public void run() {
try {
mainLoop();
} finally {
synchronized(queue) {
newTasksMayBeScheduled = false;
queue.clear(); // 任务执行完后清理队列
}
}
}
private void mainLoop() {
while (true) {
try {
TimerTask task; // 接收一个TimerTask
boolean taskFired;
synchronized(queue) {
while (queue.isEmpty() && newTasksMayBeScheduled)
queue.wait(); // 队列为空时阻塞, 放一个任务进来会notify解除阻塞
if (queue.isEmpty())
break;
long currentTime, executionTime;
task = queue.getMin(); // 从小顶堆中取出Task
synchronized(task.lock) {
if (task.state == TimerTask.CANCELLED) {
queue.removeMin(); // 从堆顶取出来后就会删掉任务
continue;
}
currentTime = System.currentTimeMillis(); // 当前时间
// 获取Task的下一次执行时间, 重新加入堆. 下一次时间点的任务相当于是一个新的任务
executionTime = task.nextExecutionTime;
if (taskFired = (executionTime<=currentTime)) {
if (task.period == 0) {
queue.removeMin();
task.state = TimerTask.EXECUTED;
} else {
queue.rescheduleMin( // 将新的任务重新入队
// 如果后面task.run();方法超时, 有可能会导致任务的丢失
task.period<0 ? currentTime - task.period : executionTime + task.period);
}
}
}
if (!taskFired)
queue.wait(executionTime - currentTime);
}
if (taskFired)
task.run(); // task直接调的run方法, 并不是通过start启动的
// 相当于是以单线程的方式执行, 因为任务超时会导致任务阻塞
// 解决方案: 在TimerTask的run()方法中使用线程池去执行
} catch(InterruptedException e) {
}
}
}
}
严重依赖系统时间
不能给定相对时间执行, eg: 每周一执行找不到
注意, 同一个job定义, 执行的是多个实例
通过System.identityHashCode打印出hashcode值不一样
每一次任务的jobDataMap也不同
取的map不同, 每次打印都是1
