內(nèi)部結(jié)構(gòu)
- 可重入鎖
- 用于根據(jù)delay時(shí)間排序的優(yōu)先級(jí)隊(duì)列
- 用于優(yōu)化阻塞通知的線程元素leader
- 用于實(shí)現(xiàn)阻塞和通知的Condition對(duì)象
delayed和PriorityQueue
在理解delayQueue原理之前我們需要先了解兩個(gè)東西,delayed和PriorityQueue.
- delayed是一個(gè)具有過期時(shí)間的元素
- PriorityQueue是一個(gè)根據(jù)隊(duì)列里元素某些屬性排列先后的順序隊(duì)列
delayQueue其實(shí)就是在每次往優(yōu)先級(jí)隊(duì)列中添加元素,然后以元素的delay/過期值作為排序的因素,以此來達(dá)到先過期的元素會(huì)拍在隊(duì)首,每次從隊(duì)列里取出來都是最先要過期的元素
offer方法
- 執(zhí)行加鎖操作
- 吧元素添加到優(yōu)先級(jí)隊(duì)列中
- 查看元素是否為隊(duì)首
- 如果是隊(duì)首的話，設(shè)置leader為空，喚醒所有等待的隊(duì)列
- 釋放鎖
代碼如下：
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
q.offer(e);
if (q.peek() == e) {
leader = null;
available.signal();
}
return true;
} finally {
lock.unlock();
}
}
take方法
- 執(zhí)行加鎖操作
- 取出優(yōu)先級(jí)隊(duì)列元素q的隊(duì)首
- 如果元素q的隊(duì)首/隊(duì)列為空,阻塞請(qǐng)求
- 如果元素q的隊(duì)首(first)不為空,獲得這個(gè)元素的delay時(shí)間值
- 如果first的延遲delay時(shí)間值為0的話,說明該元素已經(jīng)到了可以使用的時(shí)間,調(diào)用poll方法彈出該元素,跳出方法
- 如果first的延遲delay時(shí)間值不為0的話,釋放元素first的引用,避免內(nèi)存泄露
- 判斷l(xiāng)eader元素是否為空,不為空的話阻塞當(dāng)前線程
- 如果leader元素為空的話,把當(dāng)前線程賦值給leader元素,然后阻塞delay的時(shí)間,即等待隊(duì)首到達(dá)可以出隊(duì)的時(shí)間,在finally塊中釋放leader元素的引用
- 循環(huán)執(zhí)行從1~8的步驟
- 如果leader為空并且優(yōu)先級(jí)隊(duì)列不為空的情況下(判斷還有沒有其他后續(xù)節(jié)點(diǎn)),調(diào)用signal通知其他的線程
- 執(zhí)行解鎖操作
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
for (;;) {
E first = q.peek();
if (first == null)
available.await();
else {
long delay = first.getDelay(NANOSECONDS);
if (delay <= 0)
return q.poll();
first = null; // don't retain ref while waiting
if (leader != null)
available.await();
else {
Thread thisThread = Thread.currentThread();
leader = thisThread;
try {
available.awaitNanos(delay);
} finally {
if (leader == thisThread)
leader = null;
}
}
}
}
} finally {
if (leader == null && q.peek() != null)
available.signal();
lock.unlock();
}
}
get點(diǎn)
整個(gè)代碼的過程中并沒有使用上太難理解的地方,但是有幾個(gè)比較難以理解他為什么這么做的地方
leader元素的使用
大家可能看到在我們的DelayQueue中有一個(gè)Thread類型的元素leader,那么他是做什么的呢,有什么用呢？
讓我們先看一下元素注解上的doc描述:
Thread designated to wait for the element at the head of the queue.
This variant of the Leader-Follower pattern serves to minimize unnecessary timed waiting.
when a thread becomes the leader, it waits only for the next delay to elapse, but other threads await indefinitely.
The leader thread must signal some other thread before returning from take() or poll(...), unless some other thread becomes leader in the interim.
Whenever the head of the queue is replaced with an element with an earlier expiration time, the leader field is invalidated by being reset to null, and some waiting thread, but not necessarily the current leader, is signalled.
So waiting threads must be prepared to acquire and lose leadership while waiting.
上面主要的意思就是說用leader來減少不必要的等待時(shí)間,那么這里我們的DelayQueue是怎么利用leader來做到這一點(diǎn)的呢:
這里我們想象著我們有個(gè)多個(gè)消費(fèi)者線程用take方法去取,內(nèi)部先加鎖,然后每個(gè)線程都去peek第一個(gè)節(jié)點(diǎn).
如果leader不為空說明已經(jīng)有線程在取了,設(shè)置當(dāng)前線程等待
if (leader != null)
available.await();
如果為空說明沒有其他線程去取這個(gè)節(jié)點(diǎn),設(shè)置leader并等待delay延時(shí)到期,直到poll后結(jié)束循環(huán)
else {
Thread thisThread = Thread.currentThread();
leader = thisThread;
try {
available.awaitNanos(delay);
} finally {
if (leader == thisThread)
leader = null;
}
}
take方法中為什么釋放first元素
first = null; // don't retain ref while waiting
我們可以看到doug lea后面寫的注釋,那么這段代碼有什么用呢？
想想假設(shè)現(xiàn)在延遲隊(duì)列里面有三個(gè)對(duì)象。
- 線程A進(jìn)來獲取first,然后進(jìn)入 else 的else ,設(shè)置了leader為當(dāng)前線程A
- 線程B進(jìn)來獲取first,進(jìn)入else的阻塞操作,然后無限期等待
- 這時(shí)在JDK 1.7下面他是持有first引用的
- 如果線程A阻塞完畢,獲取對(duì)象成功,出隊(duì),這個(gè)對(duì)象理應(yīng)被GC回收,但是他還被線程B持有著,GC鏈可達(dá),所以不能回收這個(gè)first.
- 假設(shè)還有線程C 、D、E.. 持有對(duì)象1引用,那么無限期的不能回收該對(duì)象1引用了,那么就會(huì)造成內(nèi)存泄露.
