[[403367]]

面試官：好了，你也休息了十分鐘了，咱們接著往下聊聊SynchronousQueue的非公平模式吧。

Hydra：好的，有了前面公平模式的基礎(chǔ)，非公平模式理解起來(lái)就非常簡(jiǎn)單了。公平模式下，SynchronousQueue底層使用的是TransferQueue，是一個(gè)先進(jìn)先出的隊(duì)列，而非公平模式與它不同，底層采用了后進(jìn)先出的TransferStack棧來(lái)實(shí)現(xiàn)。

下面我們還是先寫(xiě)一個(gè)例子來(lái)看看效果，首先創(chuàng)建3個(gè)線程使用put方法向SynchronousQueue中插入數(shù)據(jù)，結(jié)束后再使用3個(gè)線程調(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); 
} 

運(yùn)行上面的代碼，查看結(jié)果：

takeThread take: 3 
putThread 3 end 
takeThread take: 2 
putThread 2 end 
takeThread take: 1 
putThread 1 end 

可以看到，生產(chǎn)者線程在執(zhí)行完put后會(huì)進(jìn)行阻塞，直到有消費(fèi)者線程調(diào)用take方法取走了數(shù)據(jù)，才會(huì)喚醒被阻塞的線程。并且，數(shù)據(jù)的出隊(duì)與入隊(duì)順序是相反的，即非公平模式下采用的是后進(jìn)先出的順序。

原圖

面試官：就是把結(jié)構(gòu)從隊(duì)列換成了棧，真就這么簡(jiǎn)單?

Hydra：并不是，包括底層節(jié)點(diǎn)以及出入棧的邏輯都做了相應(yīng)的改變。我們先看節(jié)點(diǎn)，在之前的公平模式中隊(duì)列的節(jié)點(diǎn)是QNode，非公平模式下棧中節(jié)點(diǎn)是SNode，定義如下：

volatile SNode next; // 指向下一個(gè)節(jié)點(diǎn)的指針 
volatile SNode match; // 存放和它進(jìn)行匹配的節(jié)點(diǎn) 
volatile Thread waiter;  // 保存阻塞的線程 
Object item;                 
int mode; 
SNode(Object item) { 
    this.item = item; 
} 

和QNode類似，如果是生產(chǎn)者構(gòu)建的節(jié)點(diǎn)，那么item非空，如果是消費(fèi)者產(chǎn)生的節(jié)點(diǎn)，那么item為null。此外還有一個(gè)mode屬性用來(lái)表示節(jié)點(diǎn)的狀態(tài)，它使用TransferStack中定義的3個(gè)常量來(lái)表示不同狀態(tài)：

static final int REQUEST    = 0; //消費(fèi)者 
static final int DATA       = 1; //生產(chǎn)者 
static final int FULFILLING = 2; //匹配中狀態(tài) 

TransferStack中沒(méi)有攜帶參數(shù)的構(gòu)造函數(shù)，使用一個(gè)head節(jié)點(diǎn)來(lái)標(biāo)記棧頂節(jié)點(diǎn)：

volatile SNode head; 

面試官：基本結(jié)構(gòu)就講到這吧，還是老規(guī)矩，先從入隊(duì)操作開(kāi)始分析吧。

Hydra：當(dāng)棧為空、或棧頂元素的類型與自己相同時(shí)，會(huì)先創(chuàng)建一個(gè)SNode節(jié)點(diǎn)，并將它的next節(jié)點(diǎn)指向當(dāng)前棧頂?shù)膆ead，然后將head指針指向自己。這個(gè)過(guò)程中通過(guò)使用CAS保證線程安全，如果失敗則退出，在循環(huán)中采取自旋的方式不斷進(jìn)行嘗試，直到節(jié)點(diǎn)入棧成功。用一張圖來(lái)表示兩個(gè)線程同時(shí)入棧的場(chǎng)景：

原圖

當(dāng)節(jié)點(diǎn)完成入棧后，調(diào)用awaitFulfill方法，等待匹配的操作的到來(lái)。在這一過(guò)程中，會(huì)使節(jié)點(diǎn)對(duì)應(yīng)的線程進(jìn)行自旋或掛起操作，直到匹配操作的節(jié)點(diǎn)將自己?jiǎn)拘?，或被其他線程中斷、等待超時(shí)。

當(dāng)入棧后的節(jié)點(diǎn)是棧頂節(jié)點(diǎn)，或者節(jié)點(diǎn)的類型為FULFILLING匹配狀態(tài)時(shí)，那么可能會(huì)馬上完成匹配，因此先進(jìn)行自旋，當(dāng)超過(guò)自旋次數(shù)上限后再掛起。而如果節(jié)點(diǎn)在自旋過(guò)程中，有新的節(jié)點(diǎn)壓入棧頂，會(huì)將非棧頂節(jié)點(diǎn)剩余的自旋次數(shù)直接清零，掛起線程避免浪費(fèi)資源。

原圖

面試官：你上面也說(shuō)了，掛起的線程有可能會(huì)超時(shí)或者被中斷，這時(shí)候應(yīng)該怎么處理?

Hydra：當(dāng)這兩種情況出現(xiàn)時(shí)，SNode會(huì)將match屬性設(shè)為自身，退出awaitFulfill方法，然后調(diào)用clean方法將對(duì)應(yīng)的節(jié)點(diǎn)清理出棧。具體情形可分為兩種情況。先說(shuō)簡(jiǎn)單的情況，如果清理的是棧頂節(jié)點(diǎn)，那么直接將head節(jié)點(diǎn)指向它的next節(jié)點(diǎn)，即將當(dāng)前棧頂節(jié)點(diǎn)彈出即可。

面試官：那么如果要?jiǎng)h除的節(jié)點(diǎn)不是棧頂?shù)墓?jié)點(diǎn)呢?

Hydra：如果清理的不是棧頂節(jié)點(diǎn)，會(huì)稍微有一些麻煩。因?yàn)闂５牡讓邮且粋€(gè)單向的鏈表結(jié)構(gòu)，所以需要從棧頂head節(jié)點(diǎn)開(kāi)始遍歷，遍歷到被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)為止。所以在清除工作開(kāi)始前，先使用了一個(gè)past節(jié)點(diǎn)標(biāo)記需要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，作為結(jié)束遍歷的標(biāo)記。

然后創(chuàng)建一個(gè)標(biāo)記節(jié)點(diǎn)p，初始時(shí)指向head節(jié)點(diǎn)，開(kāi)始循環(huán)，如果p的next節(jié)點(diǎn)不是需要被刪除的節(jié)點(diǎn)，那么就將p向后移一個(gè)位置，直到找到這個(gè)需要被刪除的中斷或超時(shí)的節(jié)點(diǎn)，然后將p的next指向這個(gè)刪除節(jié)點(diǎn)的next節(jié)點(diǎn)，在邏輯上完成鏈表中節(jié)點(diǎn)的刪除。

原圖

面試官：?jiǎn)我活愋凸?jié)點(diǎn)的入棧應(yīng)該說(shuō)完了吧，接下來(lái)說(shuō)說(shuō)不同類型節(jié)點(diǎn)間是如何實(shí)現(xiàn)的匹配操作吧?

Hydra：好的，那我們先回顧一點(diǎn)上面的知識(shí)，前面說(shuō)過(guò)每個(gè)節(jié)點(diǎn)有一個(gè)mode屬性代表它的模式，REQUEST表示它是消費(fèi)者，DATA表示是生產(chǎn)者，F(xiàn)ULFILLING表明正處于匹配中的狀態(tài)。

在一個(gè)新的線程調(diào)用方法時(shí)，先判斷它的類型mode是什么，如果和當(dāng)前棧頂head節(jié)點(diǎn)類型不同，且head節(jié)點(diǎn)的狀態(tài)不為匹配中時(shí)，將它的狀態(tài)設(shè)置為FULFILLING|mode，壓入棧中。然后將嘗試匹配新的head節(jié)點(diǎn)和它的next節(jié)點(diǎn)，如果匹配成功，會(huì)將next節(jié)點(diǎn)的match屬性設(shè)置為head節(jié)點(diǎn)，喚醒掛起的next節(jié)點(diǎn)中的線程。

在完成匹配后，當(dāng)前頭節(jié)點(diǎn)對(duì)應(yīng)的線程會(huì)協(xié)助推進(jìn)head節(jié)點(diǎn)，將head指向next節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即完成了棧頂兩節(jié)點(diǎn)的出棧。最終消費(fèi)者線程會(huì)返回匹配的生產(chǎn)者節(jié)點(diǎn)中的item數(shù)據(jù)值，而生產(chǎn)者線程也會(huì)結(jié)束運(yùn)行退出。

我們以棧中當(dāng)前節(jié)點(diǎn)為DATA類型，新節(jié)點(diǎn)為REQUEST類型畫(huà)一張圖，來(lái)直觀的感受一下上面的流程：

原圖

面試官：總算是講完了，能對(duì)SynchronousQueue做一個(gè)簡(jiǎn)單的總結(jié)嗎?

Hydra：SynchronousQueue基于底層結(jié)構(gòu)，實(shí)現(xiàn)了線程配對(duì)通信這一機(jī)制。在它的公平模式下使用的是先進(jìn)先出(FIFO)的隊(duì)列，非公平模式下使用的是后進(jìn)先出(LIFO)的棧，并且SynchronousQueue沒(méi)有使用synchronized或ReentrantLock，而是使用了大量的CAS操作來(lái)保證并發(fā)操作。可能我們?cè)谄匠５墓ぷ髦惺褂脠?chǎng)景不是很多，但是在線程池的設(shè)計(jì)中使用了SynchronousQueue，還是有很重要的應(yīng)用場(chǎng)景的。

面試官：講的還行，不過(guò)剛才這些和公平模式聽(tīng)起來(lái)感覺(jué)區(qū)別不大啊，沒(méi)有什么技術(shù)含量。這樣吧，你明天過(guò)來(lái)我們加試一場(chǎng)，我再給你打分。

Hydra：(溜了溜了，還是找家別的靠譜公司吧……)