前言
源码大家可以到这里搜索下载
正文
Timer内部有2个比较重要的成员变量
private final TaskQueue queue = new TaskQueue();
private final TimerThread thread = new TimerThread(queue);
一个是任务队列，一个是执行任务的线程。我们线看下这个 TimerThread，它继承自Thread，并声明了一个mainLoop方法，当点用 thread.start后，它就会执行这个方法
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) {
}
}
}
我们看这个方法，典型的就是一个生产者消费者的模型。
如果queue里没有数据，那么它就通过点用wait方法释放锁，等待被生产者唤醒。当方法再次被唤醒的时候，代码先去检查queue是不是空的，是空的就继续wait，否则的话，通过queue的getMin函数获取一个任务task，
如果当前时间大于等于task的执行时间：
说明该任务该执行了，如果当前任务不是重复任务，那么直接把任务从queue中移除并执行task的run方法，否则的话，修改task的下次执行时间并执行task的run方法。
如果当前时间小于task的执行时间：
那么wait(executionTime - currentTime)久后，循环执行本方法。
我们再看下生产者的方法，这个方法是timer的一个方法
private void sched(TimerTask task, long time, long period) {
if (time < 0)
throw new IllegalArgumentException("Illegal execution time.");
// Constrain value of period sufficiently to prevent numeric
// overflow while still being effectively infinitely large.
if (Math.abs(period) > (Long.MAX_VALUE >> 1))
period >>= 1;
synchronized(queue) {
if (!thread.newTasksMayBeScheduled)
throw new IllegalStateException("Timer already cancelled.");
synchronized(task.lock) {
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);
if (queue.getMin() == task)
queue.notify();
}
}
这个方法非常简单，就是把参数做了一系列的验证加到了queue里。那么问题来了，每个task的触发时间是不固定的，而消费者函数里每次都是通过getMin函数来获取应该执行的task的，那这一切是如何做到的呢？我们先看下queue的getMin函数
TimerTask getMin() {
return queue[1];
}
我们看到这个函数默认就把第一个task返回了，没办法，我们再看下add函数吧。
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);
}
几行代码非常简单，如果需要，就执行扩容操作，然后把task追加到queue的尾部(task的存放从index=1开始)，重点是fixup这个函数。我们来看下这个函数
private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;//k = k/2;
if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
break;
TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
k = j;
}
}
先说结论，这个函数执行完成以后，优先级最高的task被放到了1的位置。要达到这个目的，我们直接通过遍历这个queue也能做到，只不过这样做的时间复杂度是O(n)。
因此，我们考虑用数组实现一个完全二叉树。我们把元素按顺序插入数组中后做如下规定：
假设某个元素的index=k(k>=1)，那么k的左节点的下标为2k，右节点的下标为2k+1。
如果已知节点的下标为j，那么它的顶点下标为k/2。
当我们向1插入数据的时候，此时数组只有1位置有数据。
当我们向2插入数据的时候，如果queue[2] < queue[1]，那么1和2交换位置
当我们向3插入数据的时候，如果queue[3] < queue[1]，那么1和3交换位置
当我们向4插入数据的时候，如果queue[4] < queue[2]，那么4和2交换位置，如果queue[2] < queue[1]，那么1和2交换位置
当我们向5插入数据的时候，如果queue[5] < queue[2]，那么5和2交换位置，如果queue[2] < queue[1]，那么1和2交换位置
...
以上就是fixUp函数做的事情，我们看到，经过lgn(n为数组长度，位置0不存任何元素)次比较，新插入的元素就在这个二叉树中找到了自己的位置，并且顶点1上的元素一定是最小的(优先级最高的)。因此，此算法的时间复杂度是O(lgn)
我们看下fixDown函数
private void fixDown(int k) {
int j;
while ((j = k << 1) <= size && j > 0) {
if (j < size &&
queue[j].nextExecutionTime > 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;
}
}
fixDown函数的遍历方向和fixUp函数正好相反，是从顶点向下遍历。
假设现在位置1的元素的优先级被改掉了，那么先比较1的两个叶子节点的大小，找出优先级比较高的(我们假设3比较高)和顶点1比较，如果顶点的优先级比较高，那么此次遍历结束，否则的话，1和该3位置的元素互换互，然后再以3为顶点，找叶子节点重复上述运算，知道某个节点的叶子节点的优先级都比该节点低或者遍历到了数组的尾部结束。
通过上述介绍，我们大致了解Timer的原理，代码虽然少，但是却非常精悍。如果让我实现这个TaskQueue我可能会选择SparseArray吧，省内存，系统自动排序，就是效率差很多。
