面試官：呦，小伙子來的挺早澳慷А评汰！
Hydra：那是，不能讓您等太久了傲『纭（別廢話了快開始吧被去，還趕著去下一場呢）。
面試官：前面兩輪表現(xiàn)還不錯奖唯，那我們今天繼續(xù)說說隊列中的SynchronousQueue吧惨缆。
Hydra：好的，SynchronousQueue和之前介紹過的隊列相比，稍微有一些特別坯墨，必須等到隊列中的元素被消費(fèi)后寂汇，才能繼續(xù)向其中添加新的元素，因此它也被稱為無緩沖的等待隊列捣染。
我還是先寫一個例子吧骄瓣，創(chuàng)建兩個線程，生產(chǎn)者線程putThread向SynchronousQueue中放入元素液斜，消費(fèi)者線程takeThread從中取走元素：
SynchronousQueue<Integer> queue=new SynchronousQueue<>(true);
Thread putThread=new Thread(()->{
for (int i = 0; i <= 2; i++) {
try {
System.out.println("put thread put:"+i);
queue.put(i);
System.out.println("put thread put:"+i+" awake");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread takeThread=new Thread(()->{
int j=0;
while(j<2){
try {
j=queue.take();
System.out.println("take from putThread:"+j);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
putThread.start();
Thread.sleep(1000);
takeThread.start();
執(zhí)行上面的代碼累贤，查看結(jié)果：
put thread put:0
take from putThread:0
put thread put:0 awake
put thread put:1
take from putThread:1
put thread put:1 awake
put thread put:2
take from putThread:2
put thread put:2 awake
可以看到，生產(chǎn)者線程在執(zhí)行put方法后就被阻塞少漆，直到消費(fèi)者線程執(zhí)行take方法對隊列中的元素進(jìn)行了消費(fèi)臼膏，生產(chǎn)者線程才被喚醒，繼續(xù)向下執(zhí)行示损。簡單來說運(yùn)行流程是這樣的：
面試官：就這渗磅？應(yīng)用誰不會啊，不講講底層原理就想蒙混過關(guān)检访？
Hydra：別急啊始鱼，我們先從它的構(gòu)造函數(shù)說起，根據(jù)參數(shù)不同脆贵，SynchronousQueue分為公平模式和非公平模式医清，默認(rèn)情況下為非公平模式
public SynchronousQueue(boolean fair) {
transferer = fair ? new TransferQueue<E>() : new TransferStack<E>();
}
我們先來看看公平模式吧，該模式下底層使用的是TransferQueue隊列卖氨，內(nèi)部節(jié)點(diǎn)由QNode構(gòu)成会烙，定義如下：
volatile QNode next; // next node in queue
volatile Object item; // CAS'ed to or from null
volatile Thread waiter; // to control park/unpark
final boolean isData;
QNode(Object item, boolean isData) {
this.item = item;
this.isData = isData;
}
item用來存儲數(shù)據(jù)，isData用來區(qū)分節(jié)點(diǎn)是什么類型的線程產(chǎn)生的筒捺，true表示是生產(chǎn)者柏腻，false表示是消費(fèi)者，是后面用來進(jìn)行節(jié)點(diǎn)匹配（complementary ）的關(guān)鍵系吭。在SynchronousQueue中匹配是一個非常重要的概念五嫂，例如一個線程先執(zhí)行put產(chǎn)生了一個節(jié)點(diǎn)放入隊列，另一個線程再執(zhí)行take產(chǎn)生了一個節(jié)點(diǎn)肯尺，這兩個不同類型的節(jié)點(diǎn)就可以匹配成功沃缘。
面試官：可是我看很多資料里說SynchronousQueue是一個不存儲元素的阻塞隊列，這點(diǎn)你是怎么理解的蟆盹？
Hydra：通過上面節(jié)點(diǎn)中封裝的屬性孩灯，可以看出SynchronousQueue的隊列中封裝的節(jié)點(diǎn)更多針對的不是數(shù)據(jù)，而是要執(zhí)行的操作逾滥，個人猜測這個說法的出發(fā)點(diǎn)就是隊列中存儲的節(jié)點(diǎn)更多偏向于操作這一屬性峰档。
面試官：好吧败匹，接著往下說隊列的結(jié)構(gòu)吧。
Hydra：TransferQueue中主要定義的屬性有下面這些：
transient volatile QNode head;
transient volatile QNode tail;
transient volatile QNode cleanMe;
TransferQueue() {
QNode h = new QNode(null, false); // initialize to dummy node.
head = h;
tail = h;
}
比較重要的有頭節(jié)點(diǎn)head讥巡、尾節(jié)點(diǎn)tail掀亩、以及用于標(biāo)記下一個要刪除的節(jié)點(diǎn)的cleanMe節(jié)點(diǎn)。在構(gòu)造函數(shù)初始化中創(chuàng)建了一個節(jié)點(diǎn)欢顷，注釋中將它稱為dummy node槽棍，也就是偽造的節(jié)點(diǎn)，它的作用類似于AQS中的頭節(jié)點(diǎn)的作用抬驴，實(shí)際操作的節(jié)點(diǎn)是它的下一個節(jié)點(diǎn)炼七。
要說SynchronousQueue，真是一個神奇的隊列布持，不管你調(diào)用的是put和offer豌拙，還是take和poll，它都一概交給核心的transfer方法去處理题暖，只不過參數(shù)不同按傅。今天我們拋棄源碼，通過畫圖對它進(jìn)行分析胧卤，首先看一下方法的定義：
E transfer(E e, boolean timed, long nanos);
面試官：呦呵唯绍，就一個方法？我倒要看看它是怎么區(qū)分實(shí)現(xiàn)的入隊和出隊操作…
Hydra：在方法的參數(shù)中枝誊，timed和nanos用于標(biāo)識調(diào)用transfer的方法是否是能夠超時退出的况芒，而e是否為空則可以說明是生產(chǎn)者還是消費(fèi)者調(diào)用的此方法。如果e不為null叶撒，是生產(chǎn)者調(diào)用牛柒，如果e為null則是消費(fèi)者調(diào)用。方法的整體邏輯可以分為下面幾步：
1痊乾、若隊列為空，或隊列中的尾節(jié)點(diǎn)類型和自己的類型相同椭更，那么準(zhǔn)備封裝一個新的QNode添加到隊列中哪审。在添加新節(jié)點(diǎn)到隊尾的過程中，并沒有使用synchronized或ReentrantLock虑瀑，而是通過CAS來保證線程之間的同步湿滓。
在添加新的QNode到隊尾前，會首先判斷之前取到的尾節(jié)點(diǎn)是否發(fā)生過改變舌狗，如果有改變的話那么放棄修改叽奥，進(jìn)行自旋，在下一次循環(huán)中再次判斷痛侍。當(dāng)檢查隊尾節(jié)點(diǎn)沒有發(fā)生改變后朝氓，構(gòu)建新的節(jié)點(diǎn)QNode，并將它添加到隊尾。
2赵哲、當(dāng)新節(jié)點(diǎn)被添加到隊尾后待德，會調(diào)用awaitFulfill方法，會根據(jù)傳遞的參數(shù)讓線程進(jìn)行自旋或直接掛起枫夺。方法的定義如下将宪，參數(shù)中的timed為true時，表示這是一個有等待超時的方法橡庞。
Object awaitFulfill(QNode s, E e, boolean timed, long nanos);
在awaitFulfill方法中會進(jìn)行判斷较坛，如果新節(jié)點(diǎn)是head節(jié)點(diǎn)的下一個節(jié)點(diǎn)，考慮到可能很快它就會完成匹配后出隊扒最，先不將它掛起丑勤，進(jìn)行一定次數(shù)的自旋，超過自旋次數(shù)的上限后再進(jìn)行掛起扼倘。如果不是head節(jié)點(diǎn)的下一個節(jié)點(diǎn)确封，避免自旋造成的資源浪費(fèi)，則直接調(diào)用park或parkNanos掛起線程再菊。
3爪喘、當(dāng)掛起的線程被中斷或到達(dá)超時時間，那么需要將節(jié)點(diǎn)從隊列中進(jìn)行移除纠拔，這時會執(zhí)行clean()方法秉剑。如果要被刪除的節(jié)點(diǎn)不是鏈表中的尾節(jié)點(diǎn)，那么比較簡單稠诲，直接使用CAS替換前一個節(jié)點(diǎn)的next指針侦鹏。
如果要刪除的節(jié)點(diǎn)是鏈表中的尾節(jié)點(diǎn)，就會有點(diǎn)復(fù)雜了臀叙，因為多線程環(huán)境下可能正好有其他線程正在向尾節(jié)點(diǎn)后添加新的節(jié)點(diǎn)略水，這時如果直接刪除尾節(jié)點(diǎn)的話，會造成后面節(jié)點(diǎn)的丟失劝萤。
這時候就會用到TransferQueue中定義的cleanMe標(biāo)記節(jié)點(diǎn)了渊涝，cleanMe的作用就是當(dāng)要被移除的節(jié)點(diǎn)是隊尾節(jié)點(diǎn)時，用它來標(biāo)記隊尾節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)床嫌。具體在執(zhí)行過程中跨释，又會分為兩種情況：
-
cleanMe節(jié)點(diǎn)為null，說明隊列在之前沒有標(biāo)記需要刪除的節(jié)點(diǎn)厌处。這時會使用cleanMe來標(biāo)識該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)鳖谈，標(biāo)記完成后退出clean方法，當(dāng)下一次執(zhí)行clean方法時才會刪除cleanMe的下一個節(jié)點(diǎn)阔涉。
-
cleanMe節(jié)點(diǎn)不為null缆娃，那么說明之前已經(jīng)標(biāo)記過需要刪除的節(jié)點(diǎn)捷绒。這時刪除cleanMe的下一個節(jié)點(diǎn)，并清除當(dāng)前cleanMe標(biāo)記龄恋，并再將當(dāng)前節(jié)點(diǎn)未修改前的前驅(qū)節(jié)點(diǎn)標(biāo)記為cleanMe疙驾。注意，當(dāng)前要被刪除的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)不會發(fā)生改變郭毕，即使這個前驅(qū)節(jié)點(diǎn)已經(jīng)在邏輯上從隊列中刪除掉了它碎。
執(zhí)行完成clean方法后，transfer方法會直接返回null显押，說明入隊操作失敗扳肛。
面試官：講了這么多，入隊的還都是一個類型的節(jié)點(diǎn)吧乘碑？
Hydra：是的挖息，TransferQueue隊列中，只會存在一個類型的節(jié)點(diǎn)兽肤，如果有另一個類型的節(jié)點(diǎn)過來套腹，那么就會執(zhí)行出隊的操作了。
面試官：好吧资铡，那你接著再說說出隊方法吧电禀。
Hydra：相對入隊來說，出隊的邏輯就比較簡單了笤休。因為現(xiàn)在使用的是公平模式尖飞，所以當(dāng)隊列不為空，且隊列的head節(jié)點(diǎn)的下一個節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)匹配成功時店雅，進(jìn)行出隊操作政基，喚醒head節(jié)點(diǎn)的下一個節(jié)點(diǎn)，進(jìn)行數(shù)據(jù)的傳遞闹啦。
根據(jù)隊列中節(jié)點(diǎn)類型的不同沮明，可以分為兩種情況進(jìn)行分析：
1、如果head節(jié)點(diǎn)的下一個節(jié)點(diǎn)是put類型窍奋，當(dāng)前新節(jié)點(diǎn)是take類型珊擂。take線程取出put節(jié)點(diǎn)的item的值，并將其item變?yōu)?code>null费变，然后推進(jìn)頭節(jié)點(diǎn)，喚醒被掛起的put線程圣贸，take線程返回item的值挚歧，完成數(shù)據(jù)的傳遞過程。
head節(jié)點(diǎn)的下一個節(jié)點(diǎn)被喚醒后吁峻，會推進(jìn)head節(jié)點(diǎn)滑负，雖然前面說過隊列的head節(jié)點(diǎn)是一個dummy節(jié)點(diǎn)在张，并不存儲數(shù)據(jù)，理論上應(yīng)該將第二個節(jié)點(diǎn)直接移出隊列矮慕，但是源碼中還是將head節(jié)點(diǎn)出隊帮匾，將原來的第二個節(jié)點(diǎn)變成了新的head節(jié)點(diǎn)。
2痴鳄、同理瘟斜，如果head節(jié)點(diǎn)的下一個節(jié)點(diǎn)是take類型，當(dāng)前新節(jié)點(diǎn)是put類型痪寻。put線程會將take節(jié)點(diǎn)的item設(shè)為自己的數(shù)據(jù)值螺句，然后推進(jìn)頭節(jié)點(diǎn)，并喚醒掛起的take線程橡类，喚醒的take線程最終返回從put線程獲得的item的值蛇尚。
此外，在take線程喚醒后顾画，會將自己QNode的item指針指向自己取劫，并將waiter中保存的線程置為null，方便之后被gc回收研侣。
面試官：也就是說谱邪，在代碼中不一定非要生產(chǎn)者先去生產(chǎn)產(chǎn)品，也可以由消費(fèi)者先到達(dá)后進(jìn)行阻塞等待义辕？
Hydra：是的虾标，兩種線程都可以先進(jìn)入隊列。
面試官：好了灌砖，公平模式下我是明白了璧函，我去喝口水，給你十分鐘時間基显，回來我們聊聊非公平模式的實(shí)現(xiàn)吧蘸吓。
Hydra：……
如果覺得對您有所幫助，小伙伴們可以點(diǎn)贊撩幽、轉(zhuǎn)發(fā)一下~非常感謝
微信搜索：碼農(nóng)參上库继，來加個好友，點(diǎn)贊之交也好啊~
公眾號后臺回復(fù)“面試”窜醉、“導(dǎo)圖”宪萄、“架構(gòu)”、“實(shí)戰(zhàn)”榨惰，獲得免費(fèi)資料哦~
