Timer实现分析
2018-08-17 本文已影响7人
msrpp
分析Timer实现以前，先复习下堆算法，以小顶堆为例。
堆
堆是一个完全二叉树，按照广度遍历的方式存储在数组里。
3
5 7
6 9 8
以上面这个堆为例。
实际存储是这样的：此处我们保留了数组的第一个元素，这样方便计算父子节点关系，有父子坐标关系:leftSon = parent2;rightSon = parent2+1;
---+--+--+--+--+--+--
nul| 3| 5| 7| 6| 9|8
---+--+--+--+--+--+--
堆的操作主要分为两部:
1.往堆中插入数据,对应操作上浮，我们往堆里面增加一个元素时，先置到数组末尾。然后对比该节点和父节点的大小，如果子节点更小，则交换两者位置。继续将父节点和父父节点做上浮操作，直到堆顶。
2.去掉堆顶元素,对应操作下沉，去掉堆顶元素，此时变成一个无头堆，将数组最后的一个元素放到堆顶。可以看到此时的堆是不满足最小堆的，堆顶太大了。我们需要把堆顶下沉到它应该到的位置。那么问题来了，因为同一个父节点的两个子节点是无序的，所以此时两个子节点均可能是最小，要将三者之前的最小值置于父节点处，则有一次swap操作将父节点和其中一个子节点交换位置，继续对这个交换过后的子节点做下沉操作。直到下沉操作没有交换产生，则排序完毕。
Timer
下面来说Timer。Timer有一个内部线程thread，线程的生命周期始于Timer对象的构造函数，止于用户调用Timer对象的cancer()方法。
内部维护的queue是任务队列，可以通过Timer的schedule往队列放入创建的TimerTask实例来执行任务,调用其cancer()函数来取消任务，可以看到queue内部是个TimerTask的数组，实际结构是个以executionTime排序的小顶堆。
线程循环执行如下代码:
private void mainLoop() {
while (true) {
try {
TimerTask task;
boolean taskFired;
synchronized(queue) {
// Wait for queue to become non-empty
while (queue.isEmpty() && newTasksMayBeScheduled)
queue.wait();
if (queue.isEmpty())
break; // Queue is empty and will forever remain; die
// Queue nonempty; look at first evt and do the right thing
long currentTime, executionTime;
task = queue.getMin();
synchronized(task.lock) {
if (task.state == TimerTask.CANCELLED) {
queue.removeMin();
continue; // No action required, poll queue again
}
currentTime = System.currentTimeMillis();
executionTime = task.nextExecutionTime;
if (taskFired = (executionTime<=currentTime)) {
if (task.period == 0) { // Non-repeating, remove
queue.removeMin();
task.state = TimerTask.EXECUTED;
} else { // Repeating task, reschedule
queue.rescheduleMin(
task.period<0 ? currentTime - task.period
: executionTime + task.period);
}
}
}
if (!taskFired) // Task hasn't yet fired; wait
queue.wait(executionTime - currentTime);
}
if (taskFired) // Task fired; run it, holding no locks
task.run();
} catch(InterruptedException e) {
}
}
}
此处代码核心逻辑是：
