大家在换工作面试中,除了一些常规算法题,还会遇到各种需要手写的题目,所以打算总结出来,给大家个参考。
第一篇打算总结下阿里最喜欢问的多个线程顺序打印问题,我遇到的是机试,直接写出运行。同类型的题目有很多,比如
三个线程分别打印 A,B,C,要求这三个线程一起运行,打印 n 次,输出形如“ABCABCABC....”的字符串
两个线程交替打印 0~100 的奇偶数
通过 N 个线程顺序循环打印从 0 至 100
多线程按顺序调用,A->B->C,AA 打印 5 次,BB 打印10 次,CC 打印 15 次,重复 10 次
用两个线程,一个输出字母,一个输出数字,交替输出 1A2B3C4D...26Z
其实这类题目考察的都是线程间的通信问题,基于这类题目,做一个整理,方便日后手撕面试官,文明的打工人,手撕面试题。
使用 Lock
我们以第一题为例:三个线程分别打印 A,B,C,要求这三个线程一起运行,打印 n 次,输出形如“ABCABCABC....”的字符串。
思路:使用一个取模的判断逻辑 C%M ==N,题为 3 个线程,所以可以按取模结果编号:0、1、2,他们与 3 取模结果仍为本身,则执行打印逻辑。
public class PrintABCUsingLock { private int times; // 控制打印次数 private int state; // 当前状态值:保证三个线程之间交替打印 private Lock lock = new ReentrantLock(); public PrintABCUsingLock(int times) { this.times = times; } private void printLetter(String name, int targetNum) { for (int i = 0; i < times; ) { 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,所以第一次执行 if 语句的内容只能是 线程 A,然后还在 for 循环之内,此时 state = 1,只有 线程 B 才满足 1% 3 == 1,所以第二个执行的是 B,同理只有 线程 C 才满足 2% 3 == 2,所以第三个执行的是 C,执行完 ABC 之后,才去执行第二次 for 循环,所以要把 i++ 写在 for 循环里边,不能写成 for (int i = 0; i < times;i++) 这样。
使用 wait/notify
其实遇到这类型题目,好多同学可能会先想到的就是 join(),或者 wati/notify 这样的思路。算是比较传统且万能的解决方案。也有些面试官会要求不能使用这种方式。
思路:还是以第一题为例,我们用对象监视器来实现,通过 wait 和 notify() 方法来实现等待、通知的逻辑,A 执行后,唤醒 B,B 执行后唤醒 C,C 执行后再唤醒 A,这样循环的等待、唤醒来达到目的。
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 < times; i++) { synchronized (LOCK) { while (state % 3 != targetState) { try { LOCK.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } state++; System.out.print(name); LOCK.notifyAll(); } } } }
同样的思路,来解决下第 2 题:两个线程交替打印奇数和偶数
使用对象监视器实现,两个线程 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 < limit) { try { System.out.println(String.format("线程[%s]打印数字:%d", Thread.currentThread().getName(), ++count)); monitor.notifyAll(); monitor.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } //防止有子线程被阻塞未被唤醒,导致主线程不退出 monitor.notifyAll(); } } }
同样的思路,来解决下第 5 题:用两个线程,一个输出字母,一个输出数字,交替输出 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") { //打印数字1-26 System.out.print((i + 1)); // 唤醒其他在等待的线程 lock.notifyAll(); try { // 让当前线程释放锁资源,进入wait状态 lock.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } else if (Thread.currentThread().getName() == "letterThread") { // 打印字母A-Z System.out.print((char) ('A' + i)); // 唤醒其他在等待的线程 lock.notifyAll(); try { // 让当前线程释放锁资源,进入wait状态 lock.wait(); } catch (InterruptedException e) { e.printStackTrace(); } } } lock.notifyAll(); } } }
使用 Lock/Condition
还是以第一题为例,使用 Condition 来实现,其实和 wait/notify 的思路一样。
Condition 中的 await() 方法相当于 Object 的 wait() 方法,Condition 中的 signal() 方法相当于Object 的 notify() 方法,Condition 中的 signalAll() 相当于 Object 的 notifyAll() 方法。
不同的是,Object 中的 wait(),notify(),notifyAll()方法是和"同步锁"(synchronized关键字)捆绑使用的;而 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 < times; ) { 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 可以实现精准唤醒,所以碰到那种多个线程交替打印不同次数的题就比较容易想到,比如解决第四题:多线程按顺序调用,A->B->C,AA 打印 5 次,BB 打印10 次,CC 打印 15 次,重复 10 次
代码就不贴了,思路相同。
以上几种方式,其实都会存在一个锁的抢夺过程,如果抢锁的的线程数量足够大,就会出现很多线程抢到了锁但不该自己执行,然后就又解锁或 wait() 这种操作,这样其实是有些浪费资源的。
使用 Semaphore
在信号量上我们定义两种操作: 信号量主要用于两个目的,一个是用于多个共享资源的互斥使用,另一个用于并发线程数的控制。
acquire(获取) 当一个线程调用 acquire 操作时,它要么通过成功获取信号量(信号量减1),要么一直等下去,直到有线程释放信号量,或超时。
release(释放)实际上会将信号量的值加1,然后唤醒等待的线程。
先看下如何解决第一题:三个线程循环打印 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 < times; i++) { try { System.out.println("111" + Thread.currentThread().getName()); current.acquire(); // A获取信号执行,A信号量减1,当A为0时将无法继续获得该信号量 System.out.print(name); next.release(); // B释放信号,B信号量加1(初始为0),此时可以获取B信号量 System.out.println("222" + Thread.currentThread().getName()); } catch (InterruptedException e) { e.printStackTrace(); } } } }
如果题目中是多个线程循环打印的话,一般使用信号量解决是效率较高的方案,上一个线程持有下一个线程的信号量,通过一个信号量数组将全部关联起来,这种方式不会存在浪费资源的情况。
接着用信号量的方式解决下第三题:通过 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 < THREAD_COUNT; i++) { //非公平信号量,每个信号量初始计数都为1 semaphores[i] = new Semaphore(1); if (i != THREAD_COUNT - 1) { System.out.println(i+"==="+semaphores[i].getQueueLength()); //获取一个许可前线程将一直阻塞, for 循环之后只有 syncObjects[2] 没有被阻塞 semaphores[i].acquire(); } } for (int i = 0; i < THREAD_COUNT; i++) { // 初次执行,上一个信号量是 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) { // 初次执行,让第一个 for 循环没有阻塞的 syncObjects[2] 先获得令牌阻塞了 lastSemphore.acquire(); System.out.println("thread" + index + ": " + result++); if (result > maxNum) { System.exit(0); } // 释放当前的信号量,syncObjects[0] 信号量此时为 1,下次 for 循环中上一个信号量即为syncObjects[0] currentSemphore.release(); } } catch (Exception e) { e.printStackTrace(); } }).start(); } } }
使用 LockSupport
LockSupport 是 JDK 底层的基于 sun.misc.Unsafe 来实现的类,用来创建锁和其他同步工具类的基本线程阻塞原语。它的静态方法unpark()和park()可以分别实现阻塞当前线程和唤醒指定线程的效果,所以用它解决这样的问题会更容易一些。
(在 AQS 中,就是通过调用 LockSupport.park( )和 LockSupport.unpark() 来实现线程的阻塞和唤醒的。)
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++) { // 打印当前线程名称 System.out.print(Thread.currentThread().getName()); // 唤醒下一个线程 LockSupport.unpark(threadB); // 当前线程阻塞 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(); } }
理解了思路,解决其他问题就容易太多了。
比如,我们再解决下第五题:用两个线程,一个输出字母,一个输出数字,交替输出 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(); } }
写在最后
好了,以上就是常用的五种实现方案,多练习几次,手撕没问题。
当然,这类问题,解决方式不止是我列出的这些,还会有 join、CountDownLatch、也有放在队列里解决的,思路有很多,面试官想考察的其实只是对多线程的编程功底,其实自己练习的时候,是个很好的巩固理解 JUC 的过程。
相关推荐
0评论