“实现三个线程交替打印 ABC”是一道面试经典问题。网络上实际上也有了很多的解决方案，包括通过 synchronized 、Semaphore 、ReentrantLock 或是 CyclicBarrier 等方式实现。

这里我总结一下这些方案的特点，并提出几种我自己的代码实现。

以下实现实际上在原问题上更近一步：结果必须输出特定数量的 ABC 字符串

问题分析

综合所有方案来看，本问题本质上是对一个状态机进行建模，也即不同的线程需要实现如下状态转换过程：

1
A -> B -> C -> A -> B -> C -> A ...

我们知道，线程并行时执行顺序是不确定的，因此需要通过锁机制确保以上的状态转移过程。思路应该是：

  1. 线程 A 首先获取锁 L 打印 A，此时线程 B 和 C 获取不到锁 L 被阻塞；
  2. 线程 A 打印任务结束，释放锁 L，此时 线程 B 需要拿到锁 L 打印 B ，我们需要确保线程 C 不能在此时获取锁；
  3. 线程 B 打印结束，线程 C 拿到锁 L ，线程 A 不能在此时获取锁；
  4. 以此类推…

因此，主要难点实际上在于，如何保证只有下一个状态的线程在锁释放后一定能拿到锁。

我们可以有两种主要的解决方案：

  1. 方案一： 对每两个线程之间维护一个锁，只有在上一个线程执行完毕后才能释放这个锁，让下一个状态的线程继续执行，其他锁都不会释放。
    1
    Thread A -- Lock1 --> Thread B -- Lock2 --> Thread C -- Lock3 --> Thread A --> Lock1 ...
  2. 方案二： 维护一个状态变量 state，记录当前状态。每个线程判断该变量目前是否符合自己的执行状态，进而决定打印字符/放弃操作。

很显然，第二种方案更加直观，并且仅需要维护一个锁（甚至不需要锁），占用资源更少。以下章节以方案二为基本思路给出两种比较清晰直白的解决方案。

关于方案一的实现，可以参考这些文章：

解决方案

ReentrantLock + Condition

下面是一个使用 ReentrantLock 和 Condition 实现三个线程交替打印 ABC 的整体代码：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class PrintABCLock {

    private static Lock lock;

    private static Condition condition;

    private static int TIMES = 3; // how many times "ABC" should print

    private static volatile int state = 0; // volatile is needed to ensure visibility

    private static Runnable printA = () -> {
        for (int i = 0; i < TIMES; i++) {
            try {
                lock.lock();
                while (state % 3 != 0) {
                    condition.await();
                }
                System.out.println("A");
                state = 1;
                condition.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    };

    private static Runnable printB = () -> {
        for (int i = 0; i < TIMES; i++) {
            try {
                lock.lock();
                while (state % 3 != 1) {
                    condition.await();
                }
                System.out.println("B");
                state = 2;
                condition.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    };

    private static Runnable printC = () -> {
        for (int i = 0; i < TIMES; i++) {
            try {
                lock.lock();
                while (state % 3 != 2) {
                    condition.await();
                }
                System.out.println("C");
                state = 0;
                condition.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    };

    public static void main(String[] args) throws InterruptedException {
        lock = new ReentrantLock();
        condition = lock.newCondition();

        Thread t1 = new Thread(printA);
        Thread t2 = new Thread(printB);
        Thread t3 = new Thread(printC);

        t1.start();
        t2.start();
        t3.start();
    }
}

运行结果如下：

1
2
3
4
5
6
7
8
9
10
11
PS C:\code\java\test>  c:; cd 'c:\code\java\test'; & 'C:\env\jdk21\bin\java.exe' '-XX:+ShowCodeDetailsInExceptionMessages' '-cp' 'C:\code\java\test\target\classes' 'org.example.PrintABCLock'
A
B
C
A
B
C
A
B
C
PS C:\code\java\test>

每个线程中大致流程是：

  1. 根据设定的打印次数，循环执行打印任务；
  2. 对于每一轮打印任务，线程首先获取锁；
  3. 自旋等待状态变量 state 符合自己的打印条件，如果不符合则释放锁并等待；
  4. 符合条件后打印字符，修改状态变量 state 并唤醒其他线程；
  5. 释放锁。
  6. 重复 2-5 直到打印次数达到设定值。

Q: state 一定需要使用 volatile 修饰吗？

A: 在此例中不一定，但一般建议使用 volatile。

我们知道，锁本身就能够保证变量的可见性和原子性，并且此处也没有防止指令重排序的需求。然而，当持有锁的线程忙等待（busy waiting）时，线程会持续占用锁并不会释放，此时 state 的修改不会被其他线程看到。因此，对于一些重要的线程间共享变量，我们仍然需要使用 volatile 修饰。

在此例中，自旋操作仅涉及 state 的读取，并且，即使自旋操作没有及时看到 state 的修改，也不会导致错误的结果（获取锁的线程仍会释放锁并继续自旋直到读取到 state 的变化）。但是，作为一个好的代码习惯，我仍然建议使用 volatile 修饰 state。

Atomic 变量（无锁方案）

实际上，通过上边的方法我们发现，我们使用锁（无论是 ReentrantLock 还是 synchronized）的目的实际上只是为了保证状态变量 state 的可见性和原子性。

因此，我们可以使用 AtomicInteger 类型的 state 变量，从而以 CAS 实现无锁方案。

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
import java.util.concurrent.atomic.AtomicInteger;

public class PrintABCAtomic {

    private static final AtomicInteger state = new AtomicInteger(0);

    private static int TIMES = 3;

    private static Runnable printA = () -> {
        for (int i = 0; i < TIMES; i++) {
            while (state.get() % 3 != 0) {
                Thread.yield();
            }
            System.out.println("A");
            state.incrementAndGet();
        }
    };

    private static Runnable printB = () -> {
        for (int i = 0; i < TIMES; i++) {
            while (state.get() % 3 != 1) {
                Thread.yield();
            }
            System.out.println("B");
            state.incrementAndGet();
        }
    };

    private static Runnable printC = () -> {
        for (int i = 0; i < TIMES; i++) {
            while (state.get() % 3 != 2) {
                Thread.yield();
            }
            System.out.println("C");
            state.set(0);   // not use incrementAndGet() here to prevent Integer overflow
        }
    };

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(printA);
        Thread t2 = new Thread(printB);
        Thread t3 = new Thread(printC);

        t1.start();
        t2.start();
        t3.start();
    }
}

运行结果如下：

1
2
3
4
5
6
7
8
9
10
11
PS C:\code\java\test>  c:; cd 'c:\code\java\test'; & 'C:\env\jdk21\bin\java.exe' '-XX:+ShowCodeDetailsInExceptionMessages' '-cp' 'C:\code\java\test\target\classes' 'org.example.PrintABCAtomic'
A
B
C
A
B
C
A
B
C
PS C:\code\java\test>

每个线程中大致流程是：

  1. 根据设定的打印次数，循环执行打印任务；
  2. 对于每一轮打印任务，线程自旋等待状态变量 state 符合自己的打印条件；
  3. 符合条件后打印字符，通过 CAS 操作修改状态变量 state；
  4. 重复 2-3 直到打印次数达到设定值。

其他方法

对于有状态的并行问题，实际上 CompletableFuture 也是一个不错的选择。我们可以使用 thenApply() 等方法来实现状态转移。

感兴趣的朋友可以自行实现。

番外：如果使用公平锁？…

公平锁是这样的一种锁：对每个锁对象维护一个 FIFO 线程队列，当线程尝试获取锁时，如果有其他线程在等待，那么这个线程会被放到队列的末尾，等待其他线程释放锁后再尝试获取锁。

我们能否利用公平锁来实现三个线程交替打印 ABC 呢？

省流：不能。

对于公平锁的 FIFO 队列，我们希望出队（即获取锁）的线程有序（A -> B -> C -> A …），那么必须确保线程入队有序。但是，我们知道，由于 JVM 指令重排序的原因，即使是顺序执行 Thread 的 start() 方法，也不能保证线程的执行顺序（因为每个线程的 start() 不存在 happens-before 关系）。因此，我们无法保证线程的入队顺序，进而也不能保证按一定顺序输出线程内数据。