【Java】手撕面试题：多个线程顺序执行问题

Z时代
2024-01-10
分类：技术分享

大家在换工作面试中，除了一些常规算法题，还会遇到各种需要手写的题目，所以打算总结出来，给大家个参考。

第一篇打算总结下阿里最喜欢问的多个线程顺序打印问题，我遇到的是机试，直接写出运行。同类型的题目有很多，比如

三个线程分别打印 A，B，C，要求这三个线程一起运行，打印 n 次，输出形如“ABCABCABC....”的字符串

两个线程交替打印 0~100 的奇偶数

通过 N 个线程顺序循环打印从 0 至 100

多线程按顺序调用，A->B->C，AA 打印 5 次，BB 打印10 次，CC 打印 15 次，重复 10 次

用两个线程，一个输出字母，一个输出数字，交替输出 1A2B3C4D...26Z

其实这类题目考察的都是线程间的通信问题，基于这类题目，做一个整理，方便日后手撕面试官，文明的打工人，手撕面试题。

【Java】手撕面试题：多个线程顺序执行问题

使用 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，并通知另一线程从等待集合中释放，然后自身线程加入等待集合并释放锁即可。

【Java】手撕面试题：多个线程顺序执行问题

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 的思路一样。

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 次

代码就不贴了，思路相同。

使用 Semaphore

先看下如何解决第一题：三个线程循环打印 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();
}}