建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
面試官：好了，你也休息了十分鐘了，咱們接著往下聊聊SynchronousQueue的非公平模式吧。
嵐縣網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站從2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。
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è)線(xiàn)程使用put方法向SynchronousQueue中插入數(shù)據(jù)，結(jié)束后再使用3個(gè)線(xiàn)程調(diào)用take方法：
- SynchronousQueue
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)者線(xiàn)程在執(zhí)行完put后會(huì)進(jìn)行阻塞，直到有消費(fèi)者線(xiàn)程調(diào)用take方法取走了數(shù)據(jù)，才會(huì)喚醒被阻塞的線(xiàn)程。并且，數(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; // 保存阻塞的線(xiàn)程
- Object item;
- int mode;
- SNode(Object item) {
- this.item = item;
- }
和QNode類(lèi)似，如果是生產(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)棧為空、或棧頂元素的類(lèi)型與自己相同時(shí)，會(huì)先創(chuàng)建一個(gè)SNode節(jié)點(diǎn)，并將它的next節(jié)點(diǎn)指向當(dāng)前棧頂?shù)膆ead，然后將head指針指向自己。這個(gè)過(guò)程中通過(guò)使用CAS保證線(xiàn)程安全，如果失敗則退出，在循環(huán)中采取自旋的方式不斷進(jìn)行嘗試，直到節(jié)點(diǎn)入棧成功。用一張圖來(lái)表示兩個(gè)線(xiàn)程同時(shí)入棧的場(chǎng)景：
原圖
當(dāng)節(jié)點(diǎn)完成入棧后，調(diào)用awaitFulfill方法，等待匹配的操作的到來(lái)。在這一過(guò)程中，會(huì)使節(jié)點(diǎn)對(duì)應(yīng)的線(xiàn)程進(jìn)行自旋或掛起操作，直到匹配操作的節(jié)點(diǎn)將自己?jiǎn)拘?，或被其他線(xiàn)程中斷、等待超時(shí)。
當(dāng)入棧后的節(jié)點(diǎn)是棧頂節(jié)點(diǎn)，或者節(jié)點(diǎn)的類(lèi)型為FULFILLING匹配狀態(tài)時(shí)，那么可能會(huì)馬上完成匹配，因此先進(jìn)行自旋，當(dāng)超過(guò)自旋次數(shù)上限后再掛起。而如果節(jié)點(diǎn)在自旋過(guò)程中，有新的節(jié)點(diǎn)壓入棧頂，會(huì)將非棧頂節(jié)點(diǎn)剩余的自旋次數(shù)直接清零，掛起線(xiàn)程避免浪費(fèi)資源。
原圖
面試官：你上面也說(shuō)了，掛起的線(xiàn)程有可能會(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)我活?lèi)型節(jié)點(diǎn)的入棧應(yīng)該說(shuō)完了吧，接下來(lái)說(shuō)說(shuō)不同類(lèi)型節(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è)新的線(xiàn)程調(diào)用方法時(shí)，先判斷它的類(lèi)型mode是什么，如果和當(dāng)前棧頂head節(jié)點(diǎn)類(lèi)型不同，且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)中的線(xiàn)程。
在完成匹配后，當(dāng)前頭節(jié)點(diǎn)對(duì)應(yīng)的線(xiàn)程會(huì)協(xié)助推進(jìn)head節(jié)點(diǎn)，將head指向next節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即完成了棧頂兩節(jié)點(diǎn)的出棧。最終消費(fèi)者線(xiàn)程會(huì)返回匹配的生產(chǎn)者節(jié)點(diǎn)中的item數(shù)據(jù)值，而生產(chǎn)者線(xiàn)程也會(huì)結(jié)束運(yùn)行退出。
我們以棧中當(dāng)前節(jié)點(diǎn)為DATA類(lèi)型，新節(jié)點(diǎn)為REQUEST類(lèi)型畫(huà)一張圖，來(lái)直觀的感受一下上面的流程：
原圖
面試官：總算是講完了，能對(duì)SynchronousQueue做一個(gè)簡(jiǎn)單的總結(jié)嗎?
Hydra：SynchronousQueue基于底層結(jié)構(gòu)，實(shí)現(xiàn)了線(xiàn)程配對(duì)通信這一機(jī)制。在它的公平模式下使用的是先進(jìn)先出(FIFO)的隊(duì)列，非公平模式下使用的是后進(jìn)先出(LIFO)的棧，并且SynchronousQueue沒(méi)有使用synchronized或ReentrantLock，而是使用了大量的CAS操作來(lái)保證并發(fā)操作?？赡芪覀?cè)谄匠５墓ぷ髦惺褂脠?chǎng)景不是很多，但是在線(xiàn)程池的設(shè)計(jì)中使用了SynchronousQueue，還是有很重要的應(yīng)用場(chǎng)景的。
面試官：講的還行，不過(guò)剛才這些和公平模式聽(tīng)起來(lái)感覺(jué)區(qū)別不大啊，沒(méi)有什么技術(shù)含量。這樣吧，你明天過(guò)來(lái)我們加試一場(chǎng)，我再給你打分。
Hydra：(溜了溜了，還是找家別的靠譜公司吧……)
新聞標(biāo)題：面試侃集合|SynchronousQueue非公平模式篇
URL網(wǎng)址：http://www.5511xx.com/article/djeeooh.html
