面试题:多线程循环打印 ABC


被多个面试官问过这道题,最近一次被问到时,面试官建议我写篇博客写清楚,那我整理一下。

题目:三个线程 ThreadA、ThreadB、ThreadC,分别会打印 A、B、C,请问如何让三个线程循环交替执行,在控制台打印 ABCABCABC……?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class PrintABC {

// 由 ThreadA 执行
public void printA() {
while (true) {
System.out.print("A");
}
}

// 由 ThreadB 执行
public void printB() {
while (true) {
System.out.print("B");
}
}

// 由 ThreadC 执行
public void printC() {
while (true) {
System.out.print("C");
}
}

// 控制台上打印 ABCABCABCABC……
}

(知乎上有一道类似的题目:交替打印FooBar


总体有两种思路:自旋或阻塞。

  • 自旋:ThreadA、ThreadB、ThreadC 一直自旋判断是否应该打印字母。

    为了避免过度自旋造成对 CPU 的浪费,可以在自旋失败时休眠线程,或者主动让出 CPU 时间,以减少自旋次数。

  • 阻塞:ThreadA、ThreadB、ThreadC 在可以打印字母时执行方法,否则休眠,直到被唤醒。

    具体的实现有很多种,总体又可以分为互斥量法(上锁)和信号量法(阻塞等待信号量)。

下面是具体代码实现:

自旋

使用一个计数器,每次打印一个字母都会自增 1。

三个方法各自死循环,直到计数器对 3 取余是相应的数字。为了避免浪费资源,在自旋失败时让出 CPU 时间。(还可以使用 LockSupport.park() 挂起线程)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class PrintABC {

private volatile int counter = 0;

public void printA() {
while (true) {
while (counter % 3 != 0) {
Thread.yield();
}
System.out.print("A");
counter++;
}
}

public void printB() {
while (true) {
while (counter % 3 != 1) {
Thread.yield();
}
System.out.print("B");
counter++;
}
}

public void printC() {
while (true) {
while (counter % 3 != 2) {
Thread.yield();
}
System.out.print("C");
counter++;
}
}
}

自旋配合 CyclicBarrier

自旋法的改良版,在原来自旋的基础之上,在方法执行完后使用栅栏 CyclicBarrier,直到三个线程都打印字母后,才开启下一轮,减少自旋的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class PrintABC {

private final CyclicBarrier cyclicBarrier = new CyclicBarrier(3);
private volatile int counter = 0;

public void printA() throws InterruptedException, BrokenBarrierException {
while (true) {
while (counter % 3 != 0) {
Thread.yield();
}
System.out.print("A");
counter++;
cyclicBarrier.await();
}
}

public void printB() throws InterruptedException, BrokenBarrierException {
while (true) {
while (counter % 3 != 1) {
Thread.yield();
}
System.out.print("B");
counter++;
cyclicBarrier.await();
}
}

public void printC() throws InterruptedException, BrokenBarrierException {
while (true) {
while (counter % 3 != 2) {
Thread.yield();
}
System.out.print("C");
counter++;
cyclicBarrier.await();
}
}
}

synchronized 上锁

使用同一把锁(synchronized 修饰同一个对象)和一个计数器。

当计数器对 3 取余是相应的数字时,打印字母,否则线程休眠(释放锁)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class PrintABC {

private final Object o = new Object();
private int counter = 0;

public void printA() throws InterruptedException {
while (true) {
synchronized (o) {
while (counter % 3 != 0) {
o.wait();
}
System.out.print("A");
counter++;
o.notifyAll();
}
}
}

public void printB() throws InterruptedException {
while (true) {
synchronized (o) {
while (counter % 3 != 1) {
o.wait();
}
System.out.print("B");
counter++;
o.notifyAll();
}
}
}

public void printC() throws InterruptedException {
while (true) {
synchronized (o) {
while (counter % 3 != 2) {
o.wait();
}
System.out.print("C");
counter++;
o.notifyAll();
}
}
}
}

Lock 上锁

跟 synchronized 上锁的逻辑几乎相同,但是通过 Condition 降低了锁的粒度,因此唤醒其他线程时,不是全体唤醒,而是精准唤醒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class PrintABC {

private final Lock lock = new ReentrantLock();
private final Condition condition1 = lock.newCondition();
private final Condition condition2 = lock.newCondition();
private final Condition condition3 = lock.newCondition();
private volatile int counter = 0;

public void printA() throws InterruptedException {
while (true) {
lock.lock();
try {
while (counter % 3 != 0) {
condition1.await();
}
System.out.print("A");
counter++;
condition2.signal();
} finally {
lock.unlock();
}
}
}

public void printB() throws InterruptedException {
while (true) {
lock.lock();
try {
while (counter % 3 != 1) {
condition2.await();
}
System.out.print("B");
counter++;
condition3.signal();
} finally {
lock.unlock();
}
}
}

public void printC() throws InterruptedException {
while (true) {
lock.lock();
try {
while (counter % 3 != 2) {
condition3.await();
}
System.out.print("C");
counter++;
condition1.signal();
} finally {
lock.unlock();
}
}
}
}

Semaphore 信号量

使用三个 Semaphore 对象,分别控制三个方法的执行。

只有获取到信号量时,方法才可以执行。当方法执行完成后,释放一个下一个方法所需的信号量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class PrintABC {

private final Semaphore semaphore1 = new Semaphore(1);
private final Semaphore semaphore2 = new Semaphore(0);
private final Semaphore semaphore3 = new Semaphore(0);

public void printA() throws InterruptedException {
while (true) {
semaphore1.acquire();
System.out.print("A");
semaphore2.release();
}
}

public void printB() throws InterruptedException {
while (true) {
semaphore2.acquire();
System.out.print("B");
semaphore3.release();
}
}

public void printC() throws InterruptedException {
while (true) {
semaphore3.acquire();
System.out.print("C");
semaphore1.release();
}
}
}

BlockingQueue

与 Semaphore 是同一个原理,使用信号量的方式(阻塞队列能否拿到元素),控制线程执行或等待。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class PrintABC {

private final BlockingQueue<Integer> queue1 = new LinkedBlockingQueue<>(1);
private final BlockingQueue<Integer> queue2 = new LinkedBlockingQueue<>(1);
private final BlockingQueue<Integer> queue3 = new LinkedBlockingQueue<>(1);

public PrintABC() throws InterruptedException {
queue1.put(1);
}

public void printA() throws InterruptedException {
while (true) {
queue1.take();
System.out.print("A");
queue2.put(2);
}
}

public void printB() throws InterruptedException {
while (true) {
queue2.take();
System.out.print("B");
queue3.put(3);
}
}

public void printC() throws InterruptedException {
while (true) {
queue3.take();
System.out.print("C");
queue1.put(1);
}
}
}