前言
源碼大家可以到這里搜索下載
正文
Timer內(nèi)部有2個(gè)比較重要的成員變量
private final TaskQueue queue = new TaskQueue();
private final TimerThread thread = new TimerThread(queue);
一個(gè)是任務(wù)隊(duì)列，一個(gè)是執(zhí)行任務(wù)的線程。我們線看下這個(gè) TimerThread，它繼承自Thread，并聲明了一個(gè)mainLoop方法，當(dāng)點(diǎn)用 thread.start后，它就會(huì)執(zhí)行這個(gè)方法
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) {
}
}
}
我們看這個(gè)方法，典型的就是一個(gè)生產(chǎn)者消費(fèi)者的模型。
如果queue里沒(méi)有數(shù)據(jù)，那么它就通過(guò)點(diǎn)用wait方法釋放鎖，等待被生產(chǎn)者喚醒。當(dāng)方法再次被喚醒的時(shí)候，代碼先去檢查queue是不是空的，是空的就繼續(xù)wait，否則的話，通過(guò)queue的getMin函數(shù)獲取一個(gè)任務(wù)task，
如果當(dāng)前時(shí)間大于等于task的執(zhí)行時(shí)間：
說(shuō)明該任務(wù)該執(zhí)行了，如果當(dāng)前任務(wù)不是重復(fù)任務(wù)，那么直接把任務(wù)從queue中移除并執(zhí)行task的run方法，否則的話，修改task的下次執(zhí)行時(shí)間并執(zhí)行task的run方法。
如果當(dāng)前時(shí)間小于task的執(zhí)行時(shí)間：
那么wait(executionTime - currentTime)久后，循環(huán)執(zhí)行本方法。
我們?cè)倏聪律a(chǎn)者的方法，這個(gè)方法是timer的一個(gè)方法
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();
}
}
這個(gè)方法非常簡(jiǎn)單，就是把參數(shù)做了一系列的驗(yàn)證加到了queue里。那么問(wèn)題來(lái)了，每個(gè)task的觸發(fā)時(shí)間是不固定的，而消費(fèi)者函數(shù)里每次都是通過(guò)getMin函數(shù)來(lái)獲取應(yīng)該執(zhí)行的task的，那這一切是如何做到的呢？我們先看下queue的getMin函數(shù)
TimerTask getMin() {
return queue[1];
}
我們看到這個(gè)函數(shù)默認(rèn)就把第一個(gè)task返回了，沒(méi)辦法，我們?cè)倏聪耡dd函數(shù)吧。
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);
}
幾行代碼非常簡(jiǎn)單，如果需要，就執(zhí)行擴(kuò)容操作，然后把task追加到queue的尾部(task的存放從index=1開(kāi)始)，重點(diǎn)是fixup這個(gè)函數(shù)。我們來(lái)看下這個(gè)函數(shù)
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;
}
}
先說(shuō)結(jié)論，這個(gè)函數(shù)執(zhí)行完成以后，優(yōu)先級(jí)最高的task被放到了1的位置。要達(dá)到這個(gè)目的，我們直接通過(guò)遍歷這個(gè)queue也能做到，只不過(guò)這樣做的時(shí)間復(fù)雜度是O(n)。
因此，我們考慮用數(shù)組實(shí)現(xiàn)一個(gè)完全二叉樹(shù)。我們把元素按順序插入數(shù)組中后做如下規(guī)定：
假設(shè)某個(gè)元素的index=k(k>=1)，那么k的左節(jié)點(diǎn)的下標(biāo)為2k，右節(jié)點(diǎn)的下標(biāo)為2k+1。
如果已知節(jié)點(diǎn)的下標(biāo)為j，那么它的頂點(diǎn)下標(biāo)為k/2。
當(dāng)我們向1插入數(shù)據(jù)的時(shí)候，此時(shí)數(shù)組只有1位置有數(shù)據(jù)。
當(dāng)我們向2插入數(shù)據(jù)的時(shí)候，如果queue[2] < queue[1]，那么1和2交換位置
當(dāng)我們向3插入數(shù)據(jù)的時(shí)候，如果queue[3] < queue[1]，那么1和3交換位置
當(dāng)我們向4插入數(shù)據(jù)的時(shí)候，如果queue[4] < queue[2]，那么4和2交換位置，如果queue[2] < queue[1]，那么1和2交換位置
當(dāng)我們向5插入數(shù)據(jù)的時(shí)候，如果queue[5] < queue[2]，那么5和2交換位置，如果queue[2] < queue[1]，那么1和2交換位置
...
以上就是fixUp函數(shù)做的事情，我們看到，經(jīng)過(guò)lgn(n為數(shù)組長(zhǎng)度，位置0不存任何元素)次比較，新插入的元素就在這個(gè)二叉樹(shù)中找到了自己的位置，并且頂點(diǎn)1上的元素一定是最小的(優(yōu)先級(jí)最高的)。因此，此算法的時(shí)間復(fù)雜度是O(lgn)
我們看下fixDown函數(shù)
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函數(shù)的遍歷方向和fixUp函數(shù)正好相反，是從頂點(diǎn)向下遍歷。
假設(shè)現(xiàn)在位置1的元素的優(yōu)先級(jí)被改掉了，那么先比較1的兩個(gè)葉子節(jié)點(diǎn)的大小，找出優(yōu)先級(jí)比較高的(我們假設(shè)3比較高)和頂點(diǎn)1比較，如果頂點(diǎn)的優(yōu)先級(jí)比較高，那么此次遍歷結(jié)束，否則的話，1和該3位置的元素互換互，然后再以3為頂點(diǎn)，找葉子節(jié)點(diǎn)重復(fù)上述運(yùn)算，知道某個(gè)節(jié)點(diǎn)的葉子節(jié)點(diǎn)的優(yōu)先級(jí)都比該節(jié)點(diǎn)低或者遍歷到了數(shù)組的尾部結(jié)束。
通過(guò)上述介紹，我們大致了解Timer的原理，代碼雖然少，但是卻非常精悍。如果讓我實(shí)現(xiàn)這個(gè)TaskQueue我可能會(huì)選擇SparseArray吧，省內(nèi)存，系統(tǒng)自動(dòng)排序，就是效率差很多。
