前言
源碼大家可以到這里搜索下載
正文
Timer內部有2個比較重要的成員變量
private final TaskQueue queue = new TaskQueue();
private final TimerThread thread = new TimerThread(queue);
一個是任務隊列，一個是執(zhí)行任務的線程命浴。我們線看下這個 TimerThread，它繼承自Thread贱除，并聲明了一個mainLoop方法生闲，當點用 thread.start后，它就會執(zhí)行這個方法
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) {
}
}
}
我們看這個方法月幌，典型的就是一個生產(chǎn)者消費者的模型碍讯。
如果queue里沒有數(shù)據(jù)，那么它就通過點用wait方法釋放鎖扯躺，等待被生產(chǎn)者喚醒捉兴。當方法再次被喚醒的時候，代碼先去檢查queue是不是空的录语，是空的就繼續(xù)wait倍啥，否則的話，通過queue的getMin函數(shù)獲取一個任務task澎埠，
如果當前時間大于等于task的執(zhí)行時間：
說明該任務該執(zhí)行了虽缕，如果當前任務不是重復任務，那么直接把任務從queue中移除并執(zhí)行task的run方法蒲稳，否則的話氮趋，修改task的下次執(zhí)行時間并執(zhí)行task的run方法。
如果當前時間小于task的執(zhí)行時間：
那么wait(executionTime - currentTime)久后江耀，循環(huán)執(zhí)行本方法凭峡。
我們再看下生產(chǎn)者的方法，這個方法是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();
}
}
這個方法非常簡單决记，就是把參數(shù)做了一系列的驗證加到了queue里摧冀。那么問題來了，每個task的觸發(fā)時間是不固定的，而消費者函數(shù)里每次都是通過getMin函數(shù)來獲取應該執(zhí)行的task的索昂，那這一切是如何做到的呢建车？我們先看下queue的getMin函數(shù)
TimerTask getMin() {
return queue[1];
}
我們看到這個函數(shù)默認就把第一個task返回了，沒辦法椒惨，我們再看下add函數(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);
}
幾行代碼非常簡單，如果需要康谆，就執(zhí)行擴容操作领斥，然后把task追加到queue的尾部(task的存放從index=1開始)，重點是fixup這個函數(shù)沃暗。我們來看下這個函數(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;
}
}
先說結論月洛，這個函數(shù)執(zhí)行完成以后，優(yōu)先級最高的task被放到了1的位置孽锥。要達到這個目的嚼黔，我們直接通過遍歷這個queue也能做到，只不過這樣做的時間復雜度是O(n)惜辑。
因此唬涧，我們考慮用數(shù)組實現(xiàn)一個完全二叉樹。我們把元素按順序插入數(shù)組中后做如下規(guī)定：
假設某個元素的index=k(k>=1)盛撑，那么k的左節(jié)點的下標為2k碎节，右節(jié)點的下標為2k+1。
如果已知節(jié)點的下標為j抵卫，那么它的頂點下標為k/2狮荔。
當我們向1插入數(shù)據(jù)的時候，此時數(shù)組只有1位置有數(shù)據(jù)陌僵。
當我們向2插入數(shù)據(jù)的時候，如果queue[2] < queue[1]创坞，那么1和2交換位置
當我們向3插入數(shù)據(jù)的時候碗短，如果queue[3] < queue[1]，那么1和3交換位置
當我們向4插入數(shù)據(jù)的時候题涨，如果queue[4] < queue[2]偎谁，那么4和2交換位置，如果queue[2] < queue[1]纲堵，那么1和2交換位置
當我們向5插入數(shù)據(jù)的時候巡雨，如果queue[5] < queue[2]，那么5和2交換位置席函，如果queue[2] < queue[1]铐望，那么1和2交換位置
...
以上就是fixUp函數(shù)做的事情，我們看到，經(jīng)過lgn(n為數(shù)組長度正蛙，位置0不存任何元素)次比較督弓，新插入的元素就在這個二叉樹中找到了自己的位置，并且頂點1上的元素一定是最小的(優(yōu)先級最高的)乒验。因此愚隧，此算法的時間復雜度是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ù)正好相反，是從頂點向下遍歷锻全。
假設現(xiàn)在位置1的元素的優(yōu)先級被改掉了狂塘，那么先比較1的兩個葉子節(jié)點的大小，找出優(yōu)先級比較高的(我們假設3比較高)和頂點1比較鳄厌，如果頂點的優(yōu)先級比較高荞胡，那么此次遍歷結束，否則的話部翘，1和該3位置的元素互換互硝训，然后再以3為頂點，找葉子節(jié)點重復上述運算新思，知道某個節(jié)點的葉子節(jié)點的優(yōu)先級都比該節(jié)點低或者遍歷到了數(shù)組的尾部結束窖梁。
通過上述介紹，我們大致了解Timer的原理夹囚，代碼雖然少纵刘，但是卻非常精悍。如果讓我實現(xiàn)這個TaskQueue我可能會選擇SparseArray吧荸哟，省內存假哎，系統(tǒng)自動排序，就是效率差很多鞍历。
