[[403367]]

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

Hydra：好的，有了前面公平模式的基礎(chǔ)，非公平模式理解起來就非常簡單了。公平模式下，SynchronousQueue底層使用的是TransferQueue，是一個先進(jìn)先出的隊(duì)列，而非公平模式與它不同，底層采用了后進(jìn)先出的TransferStack棧來實(shí)現(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); 
} 

運(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后會進(jìn)行阻塞，直到有消費(fèi)者線程調(diào)用take方法取走了數(shù)據(jù)，才會喚醒被阻塞的線程。并且，數(shù)據(jù)的出隊(duì)與入隊(duì)順序是相反的，即非公平模式下采用的是后進(jìn)先出的順序。

原圖

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

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

volatile SNode next; // 指向下一個節(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。此外還有一個mode屬性用來表示節(jié)點(diǎn)的狀態(tài)，它使用TransferStack中定義的3個常量來表示不同狀態(tài)：

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

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

volatile SNode head; 

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

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

原圖

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

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

原圖

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

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

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

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

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

原圖

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

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

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

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

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

原圖

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

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

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

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