交替打印奇数偶数

Posted on | Edited on | In , ,

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

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

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

  • 采用两个线程，一个打印偶数，一个打印奇数
  • 使用一个局部变量来保存这个数字
  • 采用一个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类的唤醒机制，对于任意个数的奇数打印线程和偶数打印线程适应性都非常好。在实际的
场景中，可能应该更加倾向于这种解决方法。