交替打印奇数偶数

本文讨论一个很简单但我觉得比较有意思的设计题:

采用多线程交替打印奇数偶数

首先,题目的意图可以说是非常简单:使用多线程来打印奇数偶数,但是要求是交替打印。同时,
没有对线程数量和打印的数字大小做限制。所以,一个最简单的方案是:

  • 采用两个线程,一个打印偶数,一个打印奇数
  • 使用一个局部变量来保存这个数字
  • 采用一个bool类型的值来在两个线程之间流转

由于这个数字需要在多个线程之间流转,在不加锁的情况下我们就必须把它声明为volatile的。

同时,对数字涉及到加1这个操作,还必须注意这里的原子性。 于是有了:

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
public class OneByOnePrint1 {
private static final int MAX_NUM = 100;
private volatile int begin;
//为什么flag需要时volatile的?
private volatile boolean flag = true;

private Object lock = new Object();

public class PrintOuShu implements Runnable {
@Override
public void run() {
while (begin < MAX_NUM) {
if (flag) {
System.out.println(Thread.currentThread() + "偶数打印线程: " + begin);
//注意这里加锁是为了保证这个begin++操作的原子性
synchronized (lock) {
begin++;
flag = false;
}
}
}
}
}

public class PrintJiShu implements Runnable {
@Override
public void run() {
while (begin < MAX_NUM) {
if (!flag) {
synchronized (lock) {
System.out.println(Thread.currentThread() + "奇数打印线程: " + begin);
begin++;
flag = true;
}
}
}
}
}

public static void main(String[] args) {
OneByOnePrint1 oneByOnePrint = new OneByOnePrint1();
ExecutorService executorService = Executors.newCachedThreadPool();
executorService.submit(oneByOnePrint.new PrintJiShu());
executorService.submit(oneByOnePrint.new PrintOuShu());
}
}

上述方案可以说是简单有效,其中的加锁操作synchronized由于锁的竞争很少,在jdk1.6的锁性能优化过后
性能也比较不错,大部分情况应该没有问题。
不过作为一个精益求精的程序员,我们可以考虑如果采用多个线程来打印呢?
上述的代码依赖bool类型的flag来控制两个线程之间的流转,当时多个线程时这里就会每个线程都进入
打印逻辑。也就是会出现这样的输出:

Thread[pool-1-thread-2,5,main]偶数打印线程: 0
Thread[pool-1-thread-3,5,main]偶数打印线程: 0
Thread[pool-1-thread-1,5,main]奇数打印线程: 1
Thread[pool-1-thread-2,5,main]偶数打印线程: 3
Thread[pool-1-thread-1,5,main]奇数打印线程: 3
Thread[pool-1-thread-3,5,main]偶数打印线程: 4

之所以会出现这样的结果是因为对于多个“偶数打印线程”我们没有做互斥,使得他们同时进入了打印数字
这个临界区,于是,结合双检查锁,我们可以想到这么个方案:

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 PrintOuShu implements Runnable {

@Override
public void run() {
while (begin < 100) {
if (flag) {
//锁保证了只有一个线程进入临界区
synchronized (lock) {
//有可能其他的偶数打印线程已经进来过,flag就可能已经是false.再次检查
if (flag) {
System.out.println(Thread.currentThread()+"偶数打印线程: " + begin);
begin++;
flag = false;
}
}
}
}
}
}

public class PrintJiShu implements Runnable {

@Override
public void run() {
while (begin < 100) {
if (!flag) {
//同上面的偶数打印线程
synchronized (lock) {
if (!flag) {
System.out.println(Thread.currentThread()+"奇数打印线程: " + begin);
begin++;
flag = true;
}
}
}
}
}
}

然后在这种情况下的输出则比较正常(截取最后几行):

Thread[pool-1-thread-6,5,main]偶数打印线程: 94
Thread[pool-1-thread-4,5,main]奇数打印线程: 95
Thread[pool-1-thread-6,5,main]偶数打印线程: 96
Thread[pool-1-thread-4,5,main]奇数打印线程: 97
Thread[pool-1-thread-6,5,main]偶数打印线程: 98
Thread[pool-1-thread-4,5,main]奇数打印线程: 99
Thread[pool-1-thread-5,5,main]偶数打印线程: 100
Thread[pool-1-thread-2,5,main]奇数打印线程: 101

我们看到,最后几行明显是突破了我们的范围限制,这是为什么?

本质上来说,它其实也是我们前面说到的多线程之间的”race condition”问题。
考虑这种情况:

  • 当前数字为98
  • 共有2个偶数线程,当前同时进入到if(flag)判断里
  • 线程1首先获取到锁,把数字更新为99, flag设为false. 线程2还继续在等待者锁
  • 此时,奇数线程获取到锁并把数字更新为100
  • 线程2获取到锁,打印出来

这是因为我们在第二次检查的时候,仅仅检查了flag是否为true而没有检查数字的范围,它与前面的
双检查锁异曲同工。所以我们改为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class PrintOuShu implements Runnable {
@Override
public void run() {
while (begin < MAX_NUM) {
if (flag) {
synchronized (lock) {
if (flag && begin < MAX_NUM) {
System.out.println(Thread.currentThread()+"偶数打印线程: " + begin);
begin++;
flag = false;
}
}
}
}
}
}

这样,我们就可以使用任意的奇数打印线程和偶数打印线程数量,并且井然有序。 另外,在有多个打印线程
的时候,每次获取不多锁的时候还可以增加适当的睡眠已减少CPU的空转。


上面提到的方法始终有一个很大的问题:
线程一直处于空转状态

在任何设计过程中,不必要的CPU空转都是很应该避免的事情,而为了避免空转,让某个线程“睡眠”或者“阻塞”
是解决方案。所以我们需要再看看基于锁机制的解决方法。
在Java中,支持阻塞-唤醒的有几种:

1
2
3
Object.wait/notify/notifyAll
Thread.sleep/notify/notifyAll
Condition.wait

前面两种方案都是在某个对象上等待或者释放,对于我们的需求:“交替打印”,在两个线程的情况下其实选择哪
种方案无关紧要,如果考虑到奇数打印线程和偶数打印线程都是任意的情况下,则基于单个对象的锁我们就需要
慎重考虑: 有两种完全不同类型的线程,他们之间交替执行,但是同一种类型的线程有多个,如果两种不同
类型的线程竞争的是同一个锁,则需要非常仔细的编写代码已避免死锁。我们尝试用Lock接口来处理:

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
private Lock newLock = new ReentrantLock();
private Condition outShuCondition = newLock.newCondition();
private Condition jishuShuCondition = newLock.newCondition();
public class PrintOuShu implements Runnable {
@Override
public void run() {
while (begin < MAX_NUM) {
try {
newLock.lock();
if(begin % 2 == 0){
System.out.println(Thread.currentThread() + "偶数打印线程: " + begin);
begin++;
}
jishuShuCondition.signal();
try {
outShuCondition.await();
} catch (InterruptedException e) {
e.printStackTrace();
}

}finally {
newLock.unlock();
}
}
}
}

public class PrintJiShu implements Runnable {

@Override
public void run() {
while (begin < MAX_NUM) {
try {
newLock.lock();
if(begin % 2 == 1){
System.out.println(Thread.currentThread() + "奇数打印线程: " + begin);
begin++;

}
outShuCondition.signal();
try {
jishuShuCondition.await();
} catch (InterruptedException e) {
e.printStackTrace();
}

}finally {
newLock.unlock();
}
}
}
}

上面的代码基于Condition类的唤醒机制,对于任意个数的奇数打印线程和偶数打印线程适应性都非常好。在实际的
场景中,可能应该更加倾向于这种解决方法。