面試官：好了，你也休息了十分鐘了催束，咱們接著往下聊聊SynchronousQueue的非公平模式吧集峦。
Hydra：好的，有了前面公平模式的基礎(chǔ)，非公平模式理解起來就非常簡單了塔淤。公平模式下摘昌，SynchronousQueue底層使用的是TransferQueue，是一個先進先出的隊列高蜂，而非公平模式與它不同聪黎，底層采用了后進先出的TransferStack棧來實現(xiàn)。
下面我們還是先寫一個例子來看看效果备恤，首先創(chuàng)建3個線程使用put方法向SynchronousQueue中插入數(shù)據(jù)稿饰，結(jié)束后再使用3個線程調(diào)用take方法：
SynchronousQueue<Integer> queue=new SynchronousQueue<>(false);
@AllArgsConstructor
class PutThread implements Runnable{
int i;
@SneakyThrows
@Override
public void run() {
queue.put(i);
System.out.println("putThread "+i+" end");
}
}
class TakeThread implements Runnable{
@SneakyThrows
@Override
public void run() {
System.out.println("takeThread take: "+queue.take());
}
}
for (int i = 1; i <=3; i++) {
new Thread(new PutThread(i)).start();
Thread.sleep(1000);
}
for (int i = 1; i <=3 ; i++) {
new Thread(new TakeThread()).start();
Thread.sleep(1000);
}
運行上面的代碼，查看結(jié)果：
takeThread take: 3
putThread 3 end
takeThread take: 2
putThread 2 end
takeThread take: 1
putThread 1 end
可以看到露泊，生產(chǎn)者線程在執(zhí)行完put后會進行阻塞喉镰，直到有消費者線程調(diào)用take方法取走了數(shù)據(jù)，才會喚醒被阻塞的線程惭笑。并且侣姆，數(shù)據(jù)的出隊與入隊順序是相反的，即非公平模式下采用的是后進先出的順序沉噩。
面試官：就是把結(jié)構(gòu)從隊列換成了棧捺宗，真就這么簡單？
Hydra：并不是川蒙，包括底層節(jié)點以及出入棧的邏輯都做了相應(yīng)的改變偿凭。我們先看節(jié)點，在之前的公平模式中隊列的節(jié)點是QNode派歌，非公平模式下棧中節(jié)點是SNode，定義如下：
volatile SNode next; // 指向下一個節(jié)點的指針
volatile SNode match; // 存放和它進行匹配的節(jié)點
volatile Thread waiter; // 保存阻塞的線程
Object item;
int mode;
SNode(Object item) {
this.item = item;
}
和QNode類似痰哨，如果是生產(chǎn)者構(gòu)建的節(jié)點胶果，那么item非空，如果是消費者產(chǎn)生的節(jié)點斤斧，那么item為null早抠。此外還有一個mode屬性用來表示節(jié)點的狀態(tài)，它使用TransferStack中定義的3個常量來表示不同狀態(tài)：
static final int REQUEST = 0; //消費者
static final int DATA = 1; //生產(chǎn)者
static final int FULFILLING = 2; //匹配中狀態(tài)
TransferStack中沒有攜帶參數(shù)的構(gòu)造函數(shù)撬讽，使用一個head節(jié)點來標記棧頂節(jié)點：
volatile SNode head;
面試官：基本結(jié)構(gòu)就講到這吧蕊连，還是老規(guī)矩，先從入隊操作開始分析吧游昼。
Hydra：當棧為空甘苍、或棧頂元素的類型與自己相同時，會先創(chuàng)建一個SNode節(jié)點烘豌，并將它的next節(jié)點指向當前棧頂?shù)?code>head载庭，然后將head指針指向自己。這個過程中通過使用CAS保證線程安全，如果失敗則退出囚聚，在循環(huán)中采取自旋的方式不斷進行嘗試靖榕，直到節(jié)點入棧成功。用一張圖來表示兩個線程同時入棧的場景：
當節(jié)點完成入棧后顽铸，調(diào)用awaitFulfill方法茁计，等待匹配的操作的到來。在這一過程中谓松，會使節(jié)點對應(yīng)的線程進行自旋或掛起操作星压，直到匹配操作的節(jié)點將自己喚醒，或被其他線程中斷毒返、等待超時租幕。
當入棧后的節(jié)點是棧頂節(jié)點，或者節(jié)點的類型為FULFILLING匹配狀態(tài)時拧簸，那么可能會馬上完成匹配劲绪，因此先進行自旋，當超過自旋次數(shù)上限后再掛起盆赤。而如果節(jié)點在自旋過程中贾富，有新的節(jié)點壓入棧頂，會將非棧頂節(jié)點剩余的自旋次數(shù)直接清零牺六，掛起線程避免浪費資源颤枪。
面試官：你上面也說了，掛起的線程有可能會超時或者被中斷淑际，這時候應(yīng)該怎么處理畏纲？
Hydra：當這兩種情況出現(xiàn)時，SNode會將match屬性設(shè)為自身春缕，退出awaitFulfill方法盗胀，然后調(diào)用clean方法將對應(yīng)的節(jié)點清理出棧。具體情形可分為兩種情況锄贼。先說簡單的情況票灰，如果清理的是棧頂節(jié)點，那么直接將head節(jié)點指向它的next節(jié)點宅荤，即將當前棧頂結(jié)點彈出即可屑迂。
面試官：那么如果要刪除的節(jié)點不是棧頂?shù)墓?jié)點呢？
Hydra：如果清理的不是棧頂節(jié)點冯键，會稍微有一些麻煩惹盼。因為棧的底層是一個單向的鏈表結(jié)構(gòu)，所以需要從棧頂head節(jié)點開始遍歷琼了，遍歷到被刪除節(jié)點的后繼節(jié)點為止逻锐。所以在清除工作開始前夫晌，先使用了一個past節(jié)點標記需要刪除節(jié)點的下一個節(jié)點，作為結(jié)束遍歷的標記昧诱。
然后創(chuàng)建一個標記節(jié)點p晓淀，初始時指向head結(jié)點，開始循環(huán)盏档，如果p的next節(jié)點不是需要被刪除的節(jié)點凶掰，那么就將p向后移一個位置，直到找到這個需要被刪除的中斷或超時的節(jié)點蜈亩，然后將p的next指向這個刪除節(jié)點的next節(jié)點懦窘，在邏輯上完成鏈表中節(jié)點的刪除。
面試官：單一類型節(jié)點的入棧應(yīng)該說完了吧稚配，接下來說說不同類型節(jié)點間是如何實現(xiàn)的匹配操作吧畅涂？
Hydra：好的，那我們先回顧一點上面的知識道川，前面說過每個節(jié)點有一個mode屬性代表它的模式午衰，REQUEST表示它是消費者，DATA表示是生產(chǎn)者冒萄，FULFILLING表明正處于匹配中的狀態(tài)臊岸。
在一個新的線程調(diào)用方法時，先判斷它的類型mode是什么尊流，如果和當前棧頂head節(jié)點類型不同帅戒，且head節(jié)點的狀態(tài)不為匹配中時，將它的狀態(tài)設(shè)置為FULFILLING|mode崖技，壓入棧中逻住。然后將嘗試匹配新的head節(jié)點和它的next節(jié)點，如果匹配成功迎献，會將next節(jié)點的match屬性設(shè)置為head節(jié)點鄙信，喚醒掛起的next節(jié)點中的線程。
在完成匹配后忿晕，當前頭結(jié)點對應(yīng)的線程會協(xié)助推進head節(jié)點，將head指向next節(jié)點的下一個節(jié)點银受，即完成了棧頂兩節(jié)點的出棧践盼。最終消費者線程會返回匹配的生產(chǎn)者節(jié)點中的item數(shù)據(jù)值，而生產(chǎn)者線程也會結(jié)束運行退出宾巍。
我們以棧中當前節(jié)點為DATA類型咕幻，新節(jié)點為REQUEST類型畫一張圖，來直觀的感受一下上面的流程：
面試官：總算是講完了顶霞，能對SynchronousQueue做一個簡單的總結(jié)嗎肄程？
Hydra：SynchronousQueue基于底層結(jié)構(gòu)锣吼，實現(xiàn)了線程配對通信這一機制。在它的公平模式下使用的是先進先出（FIFO）的隊列蓝厌，非公平模式下使用的是后進先出（LIFO）的棧玄叠，并且SynchronousQueue沒有使用synchronized或ReentrantLock，而是使用了大量的CAS操作來保證并發(fā)操作拓提《潦眩可能我們在平常的工作中使用場景不是很多，但是在線程池的設(shè)計中使用了SynchronousQueue代态，還是有很重要的應(yīng)用場景的寺惫。
面試官：講的還行，不過剛才這些和公平模式聽起來感覺區(qū)別不大啊蹦疑，沒有什么技術(shù)含量西雀。這樣吧，你明天過來我們加試一場歉摧，我再給你打分艇肴。
Hydra：（溜了溜了，還是找家別的靠譜公司吧……）
最后
如果覺得對您有所幫助判莉，小伙伴們可以點贊豆挽、轉(zhuǎn)發(fā)一下~非常感謝
微信搜索：碼農(nóng)參上，來加個好友券盅，點贊之交也好啊~
公眾號后臺回復“面試”帮哈、“導圖”、“架構(gòu)”锰镀、“實戰(zhàn)”娘侍，獲得免費資料哦~
