手撕面試題：多個線程交替打印問題
大家在換工作面試中，除了一些常規(guī)算法題，還會遇到各種需要手寫的題目，所以打算總結(jié)出來，給大家個參考。
全文 2929 字，剩下的是代碼，P6 及以下閱讀只需要 8 分鐘，高 P 請直接關(guān)閉
第一篇打算總結(jié)下阿里最喜歡問的多個線程順序打印問題，我遇到的是機試，直接寫出運行。同類型的題目有很多，比如
三個線程分別打印 A，B，C，要求這三個線程一起運行，打印 n 次，輸出形如“ABCABCABC....”的字符串 兩個線程交替打印 0~100 的奇偶數(shù) 通過 N 個線程順序循環(huán)打印從 0 至 100 多線程按順序調(diào)用，A->B->C，AA 打印 5 次，BB 打印10 次，CC 打印 15 次，重復(fù) 10 次 用兩個線程，一個輸出字母，一個輸出數(shù)字，交替輸出 1A2B3C4D...26Z
其實這類題目考察的都是線程間的通信問題，基于這類題目，做一個整理，方便日后手撕面試官，文明的打工人，手撕面試題。
使用 Lock
我們以第一題為例：三個線程分別打印 A，B，C，要求這三個線程一起運行，打印 n 次，輸出形如“ABCABCABC....”的字符串。
思路：使用一個取模的判斷邏輯 C%M ==N，題為 3 個線程，所以可以按取模結(jié)果編號：0、1、2，他們與 3 取模結(jié)果仍為本身，則執(zhí)行打印邏輯。
public?class?PrintABCUsingLock?{
????private?int?times;?//?控制打印次數(shù)
????private?int?state;???//?當(dāng)前狀態(tài)值：保證三個線程之間交替打印
????private?Lock?lock?=?new?ReentrantLock();
????public?PrintABCUsingLock(int?times)?{
????????this.times?=?times;
????}
????private?void?printLetter(String?name,?int?targetNum)?{
????????for?(int?i?=?0;?i?????????????lock.lock();
????????????if?(state?%?3?==?targetNum)?{
????????????????state++;
????????????????i++;
????????????????System.out.print(name);
????????????}
????????????lock.unlock();
????????}
????}
????public?static?void?main(String[]?args)?{
????????PrintABCUsingLock?loopThread?=?new?PrintABCUsingLock(1);
????????new?Thread(()?->?{
????????????loopThread.printLetter("B",?1);
????????},?"B").start();
????????
????????new?Thread(()?->?{
????????????loopThread.printLetter("A",?0);
????????},?"A").start();
????????
????????new?Thread(()?->?{
????????????loopThread.printLetter("C",?2);
????????},?"C").start();
????}
}
main 方法啟動后，3 個線程會搶鎖，但是 state 的初始值為 0，所以第一次執(zhí)行 if ?語句的內(nèi)容只能是 線程 A，然后還在 for 循環(huán)之內(nèi)，此時 state = 1，只有 線程 B 才滿足 1% 3 == 1，所以第二個執(zhí)行的是 B，同理只有 線程 C 才滿足 2% 3 == 2，所以第三個執(zhí)行的是 C，執(zhí)行完 ABC 之后，才去執(zhí)行第二次 for 循環(huán)，所以要把 i++ 寫在 for 循環(huán)里邊，不能寫成 for (int i = 0; i < times;i++) ?這樣。
使用 wait/notify
其實遇到這類型題目，好多同學(xué)可能會先想到的就是 join()，或者 wati/notify 這樣的思路。算是比較傳統(tǒng)且萬能的解決方案。也有些面試官會要求不能使用這種方式。
思路：還是以第一題為例，我們用對象監(jiān)視器來實現(xiàn)，通過 wait 和 notify() 方法來實現(xiàn)等待、通知的邏輯，A 執(zhí)行后，喚醒 B，B 執(zhí)行后喚醒 C，C 執(zhí)行后再喚醒 A，這樣循環(huán)的等待、喚醒來達到目的。
public?class?PrintABCUsingWaitNotify?{
????private?int?state;
????private?int?times;
????private?static?final?Object?LOCK?=?new?Object();
????public?PrintABCUsingWaitNotify(int?times)?{
????????this.times?=?times;
????}
????public?static?void?main(String[]?args)?{
????????PrintABCUsingWaitNotify?printABC?=?new?PrintABCUsingWaitNotify(10);
????????new?Thread(()?->?{
????????????printABC.printLetter("A",?0);
????????},?"A").start();
????????new?Thread(()?->?{
????????????printABC.printLetter("B",?1);
????????},?"B").start();
????????new?Thread(()?->?{
????????????printABC.printLetter("C",?2);
????????},?"C").start();
????}
????private?void?printLetter(String?name,?int?targetState)?{
????????for?(int?i?=?0;?i?????????????synchronized?(LOCK)?{
????????????????while?(state?%?3?!=?targetState)?{
????????????????????try?{
????????????????????????LOCK.wait();
????????????????????}?catch?(InterruptedException?e)?{
????????????????????????e.printStackTrace();
????????????????????}
????????????????}
????????????????state++;
????????????????System.out.print(name);
????????????????LOCK.notifyAll();
????????????}
????????}
????}
}
同樣的思路，來解決下第 2 題：兩個線程交替打印奇數(shù)和偶數(shù)
使用對象監(jiān)視器實現(xiàn)，兩個線程 A、B 競爭同一把鎖，只要其中一個線程獲取鎖成功，就打印 ++i，并通知另一線程從等待集合中釋放，然后自身線程加入等待集合并釋放鎖即可。
public?class?OddEvenPrinter?{
????private?Object?monitor?=?new?Object();
????private?final?int?limit;
????private?volatile?int?count;
????OddEvenPrinter(int?initCount,?int?times)?{
????????this.count?=?initCount;
????????this.limit?=?times;
????}
????public?static?void?main(String[]?args)?{
????????OddEvenPrinter?printer?=?new?OddEvenPrinter(0,?10);
????????new?Thread(printer::print,?"odd").start();
????????new?Thread(printer::print,?"even").start();
????}
????private?void?print()?{
????????synchronized?(monitor)?{
????????????while?(count?????????????????try?{
????????????????????System.out.println(String.format("線程[%s]打印數(shù)字:%d",?Thread.currentThread().getName(),?++count));
????????????????????monitor.notifyAll();
????????????????????monitor.wait();
????????????????}?catch?(InterruptedException?e)?{
????????????????????e.printStackTrace();
????????????????}
????????????}
????????????//防止有子線程被阻塞未被喚醒，導(dǎo)致主線程不退出
????????????monitor.notifyAll();
????????}
????}
}
同樣的思路，來解決下第 5 題：用兩個線程，一個輸出字母，一個輸出數(shù)字，交替輸出 1A2B3C4D...26Z
public?class?NumAndLetterPrinter?{
????private?static?char?c?=?'A';
????private?static?int?i?=?0;
????static?final?Object?lock?=?new?Object();
????public?static?void?main(String[]?args)?{
????????new?Thread(()?->?printer(),?"numThread").start();
????????new?Thread(()?->?printer(),?"letterThread").start();
????}
????private?static?void?printer()?{
????????synchronized?(lock)?{
????????????for?(int?i?=?0;?i?26;?i++)?{
????????????????if?(Thread.currentThread().getName()?==?"numThread")?{
????????????????????//打印數(shù)字1-26
????????????????????System.out.print((i?+?1));
????????????????????//?喚醒其他在等待的線程
????????????????????lock.notifyAll();
????????????????????try?{
????????????????????????//?讓當(dāng)前線程釋放鎖資源，進入wait狀態(tài)
????????????????????????lock.wait();
????????????????????}?catch?(InterruptedException?e)?{
????????????????????????e.printStackTrace();
????????????????????}
????????????????}?else?if?(Thread.currentThread().getName()?==?"letterThread")?{
????????????????????//?打印字母A-Z
????????????????????System.out.print((char)?('A'?+?i));
????????????????????//?喚醒其他在等待的線程
????????????????????lock.notifyAll();
????????????????????try?{
????????????????????????//?讓當(dāng)前線程釋放鎖資源，進入wait狀態(tài)
????????????????????????lock.wait();
????????????????????}?catch?(InterruptedException?e)?{
????????????????????????e.printStackTrace();
????????????????????}
????????????????}
????????????}
????????????lock.notifyAll();
????????}
????}
}
使用 Lock/Condition
還是以第一題為例，使用 Condition 來實現(xiàn)，其實和 wait/notify 的思路一樣。
Condition 中的
await()方法相當(dāng)于 Object 的wait()方法，Condition 中的signal()方法相當(dāng)于Object 的notify()方法，Condition 中的signalAll()相當(dāng)于 Object 的notifyAll()方法。不同的是，Object 中的
wait(),notify(),notifyAll()方法是和"同步鎖"(synchronized關(guān)鍵字)捆綁使用的；而 Condition 是需要與"互斥鎖"/"共享鎖"捆綁使用的。
public?class?PrintABCUsingLockCondition?{
????private?int?times;
????private?int?state;
????private?static?Lock?lock?=?new?ReentrantLock();
????private?static?Condition?c1?=?lock.newCondition();
????private?static?Condition?c2?=?lock.newCondition();
????private?static?Condition?c3?=?lock.newCondition();
????public?PrintABCUsingLockCondition(int?times)?{
????????this.times?=?times;
????}
????public?static?void?main(String[]?args)?{
????????PrintABCUsingLockCondition?print?=?new?PrintABCUsingLockCondition(10);
????????new?Thread(()?->?{
????????????print.printLetter("A",?0,?c1,?c2);
????????},?"A").start();
????????new?Thread(()?->?{
????????????print.printLetter("B",?1,?c2,?c3);
????????},?"B").start();
????????new?Thread(()?->?{
????????????print.printLetter("C",?2,?c3,?c1);
????????},?"C").start();
????}
????private?void?printLetter(String?name,?int?targetState,?Condition?current,?Condition?next)?{
????????for?(int?i?=?0;?i?????????????lock.lock();
????????????try?{
????????????????while?(state?%?3?!=?targetState)?{
????????????????????current.await();
????????????????}
????????????????state++;
????????????????i++;
????????????????System.out.print(name);
????????????????next.signal();
????????????}?catch?(Exception?e)?{
????????????????e.printStackTrace();
????????????}?finally?{
????????????????lock.unlock();
????????????}
????????}
????}
}
使用 Lock 鎖的多個 Condition 可以實現(xiàn)精準(zhǔn)喚醒，所以碰到那種多個線程交替打印不同次數(shù)的題就比較容易想到，比如解決第四題：多線程按順序調(diào)用，A->B->C，AA 打印 5 次，BB 打印10 次，CC 打印 15 次，重復(fù) 10 次
代碼就不貼了，思路相同。
以上幾種方式，其實都會存在一個鎖的搶奪過程，如果搶鎖的的線程數(shù)量足夠大，就會出現(xiàn)很多線程搶到了鎖但不該自己執(zhí)行，然后就又解鎖或 wait() 這種操作，這樣其實是有些浪費資源的。
使用 Semaphore
在信號量上我們定義兩種操作： 信號量主要用于兩個目的，一個是用于多個共享資源的互斥使用，另一個用于并發(fā)線程數(shù)的控制。
acquire（獲?。?當(dāng)一個線程調(diào)用 acquire 操作時，它要么通過成功獲取信號量（信號量減1），要么一直等下去，直到有線程釋放信號量，或超時。 release（釋放）實際上會將信號量的值加1，然后喚醒等待的線程。
先看下如何解決第一題：三個線程循環(huán)打印 A，B，C
public?class?PrintABCUsingSemaphore?{
????private?int?times;
????private?static?Semaphore?semaphoreA?=?new?Semaphore(1);?//?只有A?初始信號量為1,第一次獲取到的只能是A
????private?static?Semaphore?semaphoreB?=?new?Semaphore(0);
????private?static?Semaphore?semaphoreC?=?new?Semaphore(0);
????public?PrintABCUsingSemaphore(int?times)?{
????????this.times?=?times;
????}
????public?static?void?main(String[]?args)?{
????????PrintABCUsingSemaphore?printer?=?new?PrintABCUsingSemaphore(1);
????????new?Thread(()?->?{
????????????printer.print("A",?semaphoreA,?semaphoreB);
????????},?"A").start();
????????new?Thread(()?->?{
????????????printer.print("B",?semaphoreB,?semaphoreC);
????????},?"B").start();
????????new?Thread(()?->?{
????????????printer.print("C",?semaphoreC,?semaphoreA);
????????},?"C").start();
????}
????private?void?print(String?name,?Semaphore?current,?Semaphore?next)?{
????????for?(int?i?=?0;?i?????????????try?{
????????????????System.out.println("111"?+?Thread.currentThread().getName());
????????????????current.acquire();??//?A獲取信號執(zhí)行,A信號量減1,當(dāng)A為0時將無法繼續(xù)獲得該信號量
????????????????System.out.print(name);
????????????????next.release();????//?B釋放信號，B信號量加1（初始為0），此時可以獲取B信號量
????????????????System.out.println("222"?+?Thread.currentThread().getName());
????????????}?catch?(InterruptedException?e)?{
????????????????e.printStackTrace();
????????????}
????????}
????}
}
如果題目中是多個線程循環(huán)打印的話，一般使用信號量解決是效率較高的方案，上一個線程持有下一個線程的信號量，通過一個信號量數(shù)組將全部關(guān)聯(lián)起來，這種方式不會存在浪費資源的情況。
接著用信號量的方式解決下第三題：通過 N 個線程順序循環(huán)打印從 0 至 100
public?class?LoopPrinter?{
????private?final?static?int?THREAD_COUNT?=?3;
????static?int?result?=?0;
????static?int?maxNum?=?10;
????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????final?Semaphore[]?semaphores?=?new?Semaphore[THREAD_COUNT];
????????for?(int?i?=?0;?i?????????????//非公平信號量，每個信號量初始計數(shù)都為1
????????????semaphores[i]?=?new?Semaphore(1);
????????????if?(i?!=?THREAD_COUNT?-?1)?{
????????????????System.out.println(i+"==="+semaphores[i].getQueueLength());
????????????????//獲取一個許可前線程將一直阻塞,?for?循環(huán)之后只有?syncObjects[2]?沒有被阻塞
????????????????semaphores[i].acquire();
????????????}
????????}
????????for?(int?i?=?0;?i?????????????//?初次執(zhí)行，上一個信號量是?syncObjects[2]
????????????final?Semaphore?lastSemphore?=?i?==?0???semaphores[THREAD_COUNT?-?1]?:?semaphores[i?-?1];
????????????final?Semaphore?currentSemphore?=?semaphores[i];
????????????final?int?index?=?i;
?????????????new?Thread(()?->?{
????????????????try?{
????????????????????while?(true)?{
????????????????????????//?初次執(zhí)行，讓第一個?for?循環(huán)沒有阻塞的?syncObjects[2]?先獲得令牌阻塞了
????????????????????????lastSemphore.acquire();
????????????????????????System.out.println("thread"?+?index?+?":?"?+?result++);
????????????????????????if?(result?>?maxNum)?{
????????????????????????????System.exit(0);
????????????????????????}
????????????????????????//?釋放當(dāng)前的信號量，syncObjects[0]?信號量此時為?1，下次?for?循環(huán)中上一個信號量即為syncObjects[0]
????????????????????????currentSemphore.release();
????????????????????}
????????????????}?catch?(Exception?e)?{
????????????????????e.printStackTrace();
????????????????}
????????????}).start();
????????}
????}
}
使用 LockSupport
LockSupport 是 JDK 底層的基于 sun.misc.Unsafe 來實現(xiàn)的類，用來創(chuàng)建鎖和其他同步工具類的基本線程阻塞原語。它的靜態(tài)方法unpark()和park()可以分別實現(xiàn)阻塞當(dāng)前線程和喚醒指定線程的效果，所以用它解決這樣的問題會更容易一些。
（在 AQS 中，就是通過調(diào)用 LockSupport.park( )和 LockSupport.unpark() 來實現(xiàn)線程的阻塞和喚醒的。）
public?class?PrintABCUsingLockSupport?{
????private?static?Thread?threadA,?threadB,?threadC;
????public?static?void?main(String[]?args)?{
????????threadA?=?new?Thread(()?->?{
????????????for?(int?i?=?0;?i?10;?i++)?{
????????????????//?打印當(dāng)前線程名稱
????????????????System.out.print(Thread.currentThread().getName());
????????????????//?喚醒下一個線程
????????????????LockSupport.unpark(threadB);
????????????????//?當(dāng)前線程阻塞
????????????????LockSupport.park();
????????????}
????????},?"A");
????????threadB?=?new?Thread(()?->?{
????????????for?(int?i?=?0;?i?10;?i++)?{
????????????????//?先阻塞等待被喚醒
????????????????LockSupport.park();
????????????????System.out.print(Thread.currentThread().getName());
????????????????//?喚醒下一個線程
????????????????LockSupport.unpark(threadC);
????????????}
????????},?"B");
????????threadC?=?new?Thread(()?->?{
????????????for?(int?i?=?0;?i?10;?i++)?{
????????????????//?先阻塞等待被喚醒
????????????????LockSupport.park();
????????????????System.out.print(Thread.currentThread().getName());
????????????????//?喚醒下一個線程
????????????????LockSupport.unpark(threadA);
????????????}
????????},?"C");
????????threadA.start();
????????threadB.start();
????????threadC.start();
????}
}
理解了思路，解決其他問題就容易太多了。
比如，我們再解決下第五題：用兩個線程，一個輸出字母，一個輸出數(shù)字，交替輸出 1A2B3C4D...26Z
public?class?NumAndLetterPrinter?{
????private?static?Thread?numThread,?letterThread;
????public?static?void?main(String[]?args)?{
????????letterThread?=?new?Thread(()?->?{
????????????for?(int?i?=?0;?i?26;?i++)?{
????????????????System.out.print((char)?('A'?+?i));
????????????????LockSupport.unpark(numThread);
????????????????LockSupport.park();
????????????}
????????},?"letterThread");
????????numThread?=?new?Thread(()?->?{
????????????for?(int?i?=?1;?i?<=?26;?i++)?{
????????????????System.out.print(i);
????????????????LockSupport.park();
????????????????LockSupport.unpark(letterThread);
????????????}
????????},?"numThread");
????????numThread.start();
????????letterThread.start();
????}
}
寫在最后
好了，以上就是常用的五種實現(xiàn)方案，多練習(xí)幾次，手撕沒問題。
當(dāng)然，這類問題，解決方式不止是我列出的這些，還會有 join、CountDownLatch、也有放在隊列里解決的，思路有很多，面試官想考察的其實只是對多線程的編程功底，其實自己練習(xí)的時候，是個很好的鞏固理解 JUC 的過程。
以夢為馬，越騎越傻。詩和遠方，越走越慌。不忘初心是對的，但切記要出發(fā)，加油吧，程序員。
完
? ? ? ?
???覺得不錯，點個在看~
評論
圖片
表情