Timer & TimerTask @(Base)[JDK, Timer, TimerTask] Timer schedule(動詞) task在後臺執行。這個Task可能是只執行一次的task，也可能是按照一定規律執行的task。這也是JDK1.3提供的一個非常老的工具類 對於每一個維持sched
Timer & TimerTask
@(Base)[JDK, Timer, TimerTask]
Timer schedule(動詞) task在後臺執行。這個Task可能是只執行一次的task，也可能是按照一定規律執行的task。這也是JDK1.3提供的一個非常老的工具類
對於每一個維持schedule的Timer對象來說，內部都只有一個線程順序執行所有的task。所以每一個客戶端提交的task需要儘可能快的完成。如果中間有個線程執行時間非常久，就會hogs起線程，然後面的線程都delay，這樣會導致後續處理都很凌亂，讓他們全部弄成一團在執行。
當最後持有Timer引用的Object gc掉之後，並且所有的任務已經執行完了之後，timer的execution thread會gracefully終止（然後被垃圾回收）。這個時間可以變得無限長。這個execution線程並不是daemon的。所以他可以讓你的application無法終止。如果調用方想要儘快終止程式，可以調用caller的cancel方法。
如果timer的execute的線程異常終止，例如，當他的stop方法被調用的時候，當你再提交一個task進來的時候，就會拋出
IllegalStateExcetpion，因為Timer的cancel方法已經被調用了。這個類是線程安全的。
這個class通過Object.wait方法來調度任務。
註意： java 1.5 引入的併發包，中有一個ScheduledThreadPoolExecutor，是一個線程池，可以提供固定比率，或者時長的task。
[TOC]
Binary Heap
二叉堆是一種經過排序的完全二叉樹，其中任一非終端節點的數據值均不大於（或不小於）其左孩子和右孩子節點的值。 —— 維基百科
- 最大堆和最小堆是二叉堆的兩種形式。
- 最大堆：根結點的鍵值是所有堆結點鍵值中最大者。
- 最小堆：根結點的鍵值是所有堆結點鍵值中最小者。
- 最小堆，就是用於實現優先順序隊列的。
- 對於節點N，那麼他的兩個子節點就是2n, 2n+1，n為數組位置
Insert
首先插入尾部，然後一直與index/2，比較交換。
- 6 --> [6]
- 9 --> [6,9]
- 4 --> [6,9,4] --> 4 < arr[3/2-1] --> change(arr[0], arr[2]) --> [4,9,6]
- 7 --> [4,9,6] --> 7 < arr[4/2-1] --> change(arr[1], arr[3]) --> [4,7,6,9]
- 5 --> [4,7,6,9,5] --> 5 < arr[5/2-1] --> change[arr[1], arr[4]] --> [4,5,6,9,7]
- 1 --> [4,5,6,9,7,1] --> 1 < arr[3-1] --> change[arr[2], arr[5]]
每次插入完成之後總能保證第一個是最小的，這個交換操稱為fixUp，或者叫ShiftUp。
DELETE MIN
交換隊頭和隊尾，然後刪除隊尾，然後比較index2, index+2 交換到最小。
- [1,5,4,9,7,6] --> [6,5,4,9,7,1] --> [6,5,4,9,7] --> [4,5,6,9,7]
這個操作成為fixDown，或者ShiftDown。
PERFORMANCE
log(n) for add,removeMin,rescheduleMin.
constant time performance for the getMin operation.
LifeCycle
Constructor
新建TimerThread調度程式。執行mainLoop()
public void run() {
try { mainLoop(); }
finally { clean(); }
}MainLoop
等待在隊列上，有值喚醒後取出min操作.
while (true) {
sync(queue) {
while (queue.isEmpty()) { // avoid furious weak up
queue.wait(); // point 1
}
task = queue.getMain();
sync (task) { // avoid out-side modify // point 2
// do some cancel check
if (taskFired = (executionTime <= currentTime)) {
queue.rescheduleMin(); // or queue.removeMin();
}
}
if (!taskFired) { // point3
queue.wait(executionTime)
}
}
if (taskFired) { // point4
task.run()
}
}這段小代碼還是很精悍。
- Point 1: 利用queue對象的
wait/notify做了通知模型，當有新任務的時候就會喚醒 - Point 2: 鎖定task對象，避免task對象的內部狀態被別人更改，當確定完狀態之後，外部更改也就無效了，並且只是改狀態的時候加鎖
- Point 3: 當前task的執行時間還不到的時候，掛在queue對象上睡，為什麼掛在queue對象上睡呢，這一點很重要，當有新任務進來的時候可以響應到。
- Point 4: 喚醒之後，如果還不夠時間，就進入下一次迴圈。否則如果夠了的話就執行。
schedule
sync (queue) {
sync(task) {
// change state and nextTime
}
queue.add(task)
if (queue.getMin() == task) {
queue.notify();
}
}cancel Timer
synchronized(queue) {
thread.newTasksMayBeScheduled = false;
queue.clear();
queue.notify(); // In case queue was already empty.
}cancel one Time Task
sync(this.lock) {
this.state = CANCEL;
} purge
清除所有已經被cancel的task，一般小程式都不需要使用。
sync (queue) {
for (item in queue) {
queue.remove(item); // change current with the last
}
reindex();
}完
