面试题精选:两个线程按顺序交替输出1-100

小灰灰 2021-09-24 15:44 260阅读 0赞

陆陆续续，各个公司的校招季都开始了，我也成为了我司的校招面试官，最近也面了不少同学了，面试过程中也发现了很多问题，即有面试者的、也有面试官的、更有自己的问题，这里先挖个坑，后续写个博客详细聊聊，感兴趣的同学可以关注下。另外，我也有个专栏[《面试题精选》][Link 1]，里面收录我之前写的一些面试题博客，长期更新、永久免费，近期我会多写一些面试题相关的博客，希望能帮助到在找工作的各位。

今天分享一道Java多线程的面试题，我在几年前面试的时候被问到过，当时我完全不知道怎么写，毕竟那个时候我还是运维。现在我面试别人的时候偶尔也会问这个题目。具体题目是这样的，两个线程交替按顺序输出1-100，第一个线程只能输出偶数，第二线程输出奇数，想象下两个小孩轮流喊数。  
![在这里插入图片描述][format_png_pic_center]  
如果你没有多线程编程的基础，这道题你肯定不知道怎么做，但对于稍微学过点多线程编程的人来说似乎没有那么难，所以我觉得这是道很好的卡是否有并发编程经验的题。另外，从这道题可以扩展出很多知识点，所以它成为了中高级工程师面试的常见题。 这道题有很多的解法，接下来让我们由简入繁、逐步深入了解下，最后我也给出这道题的一些扩展题，希望你有所收获。

两个线程交替输出，这就意味着它俩是需要协同的，协同意味着二者之间要有信息传递，如何相互传递信息？ 你可能直接想到，既然是0-100的数按顺序交替输出，那么每个进程只需要时不时看看计数器的值，然后看是否轮到自己输出了就行。没错，这就是解法一的思路。

### 解法一 ###

有了上面的思路，你肯定能快速写出以下代码：

public class PrintNumber extends Thread { 
        private static int cnt = 0;
        private int id;  // 线程编号 
        public PrintNumber(int id) { 
            this.id = id;
        }
    
        @Override
        public void run() { 
            while (cnt < 100) { 
                if (cnt%2 == id) { 
                    cnt++;
                    System.out.println("thread_" + id + " num:" + cnt);
                }
            }
        }
    
        public static void main(String[] args) { 
            Thread thread0 = new PrintNumber(0);
            Thread thread1 = new PrintNumber(1);
            thread0.start();
            thread1.start();
        }
    }

但当你实际运行后会发现！！！

thread_0 num:1
    thread_0 num:3
    thread_1 num:3
    thread_1 num:5
    thread_1 num:6
    thread_0 num:5
    thread_0 num:8
    thread_0 num:9
    thread_1 num:8
    thread_0 num:11
    thread_1 num:11
    .........

不仅顺序不对，还有重复和丢失！问题在哪？回到代码中`cnt++; System.out.println("thread_" + id + " num:" + cnt);` 这两行，它主要包含两个动作，`cnt++`和输出，当cnt++执行完成后可能就已经触发了另一个线程的输出。简化下执行流程，每个时刻JVM有4个动作要执行。

1.  thread\_0 cnt++
2.  thread\_0 print
3.  thread\_1 cnt++
4.  thread\_1 print

根据Java **as-if-serial语义**，jvm只保证单线程内的有序性，不保证多线程之间的有序性，所以上面4个步骤的执行次序可能是 1 2 3 4，也可能是1 3 2 4，更可能是1 3 4 2，对于上面的代码而言就是最终次序可能会发生变化。另外，cnt++ 可以拆解为两行底层指令，`tmp = cnt + 1; cnt = tmp`，当两个线程同时执行上述指令时就会面临和1 2 3 4步骤同样的问题，…… 没错，多线程下的行为，和你女朋友的心思一样难以琢磨。 如何解决这个问题？解决方案本质上都是保证代码执行顺和我们预期的一样就行，正确的解法一和后面几个解法本质上都是同样的原理，只是实现方式不一样。

解法一正确的代码如下：

public class PrintNumber extends Thread { 
        private static AtomicInteger cnt = new AtomicInteger();
        private int id;
        public PrintNumber(int id) { 
            this.id = id;
        }
    
        @Override
        public void run() { 
            while (cnt.get() <= 100) { 
                if (cnt.get()%2 == id) { 
                    System.out.println("thread_" + id + " num:" + cnt.get());
                    cnt.incrementAndGet();
                }
            }
        }
    
        public static void main(String[] args) { 
            Thread thread0 = new PrintNumber(0);
            Thread thread1 = new PrintNumber(1);
            thread0.start();
            thread1.start();
        }
    }

上面代码通过AtomicInteger的incrementAndGet方法将cnt++的操作变成了一个原子操作，避免了多线程同时操作cnt导致的数据错误，另外，`while (cnt.get()%2 == id`也能保证只有单个线程才能进入while循环里执行，只有当前线程执行完inc后，下一个线程才能执行print，所以这个代码是可以满足我们交替输出的需求的。 但是，这种方法**很难驾驭**，如果说我吧run函数写成下面这样：

@Override
        public void run() { 
            while (cnt.get() <= 100) { 
                if (cnt.get()%2 == id) { 
                    cnt.incrementAndGet();
                    System.out.println("thread_" + id + " num:" + cnt.get());
                }
            }
        }

只需要把print和cnt.incrementAndGet()换个位置，结果就完全不一样了，先inc可能导致在print执行前下一个线程就进入执行改变了cnt的值，导致结果错误。另外**这种方法其实也不是严格正确的**，如果不是print而是其他类似的场景，可能会出问题，所以这种写法**强烈不推荐**。

### 解法二 ###

事实上，我们只需要cnt++和print同时只有一个线程在执行就行了，所以我们可以简单将方法一中错误的方案加上synchronized即可，代码如下：

public class PrintNumber extends Thread { 
        private static int cnt = 0;
        private int id;  // 线程编号
        public PrintNumber(int id) { 
            this.id = id;
        }
    
        @Override
        public void run() { 
            while (cnt <= 100) { 
                if (cnt%2 == id) { 
                    synchronized (PrintNumber.class) { 
                        cnt++;
                        System.out.println("thread_" + id + " num:" + cnt);
                    }
                }
            }
        }
    
        public static void main(String[] args) { 
            Thread thread0 = new PrintNumber(0);
            Thread thread1 = new PrintNumber(1);
            thread0.start();
            thread1.start();
        }
    }

这里我用了synchronized关键词将cnt++和print包装成了一个同步代码块，可以保证只有一个线程可以执行。这里不知道有没有人会问，cnt需不需要声明为volatile，我的回答是不需要，因为synchronized可以保证可见性。

大家有没有发现，我上面代码中一直都用了`while (cnt.get()%2 == id)`来判断cnt是否是自己要输出的数字，这就好比两个小孩轮流报数，每个小孩都要耗费精力时不时看看是否到自己了，然后选择是否报数，这样显然太低效了。能不能两个小孩之间相互通知，一个小孩报完就通知下另一个小孩，然后自己休息，这样明显对双方来说损耗的精力就少了很多。如果我们代码能有类似的机制，这里就能损耗更少的无用功，提高性能。

这就得依赖于java的wait和notify机制，当一个线程执行完自己的工作，然后唤醒另一个线程，自己去休眠，这样每个线程就不用忙等。代码改造如下，这里我直接去掉了`while (cnt.get()%2 == id)`。

@Override
        public void run() { 
            while (cnt <= 100) { 
                synchronized (PrintNumber.class) { 
                    cnt++;
                    System.out.println("thread_" + id + " num:" + cnt);
                    PrintNumber.class.notify();
                    try { 
                        PrintNumber.class.wait();
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
                }
            }
        }

### 解法三 ###

能用synchronized的地方就能用ReentrantLock，所以解法三和解法二本质上是一样的，就是把synchronized换成了lock而已，然后把wait和notify换成Condition的signal和await，改造后的代码如下：

public class PrintNumber extends Thread { 
        private static Lock lock = new ReentrantLock();
        private static Condition condition = lock.newCondition();
        private int id;
        private static int cnt = 0;
        public PrintNumber(int id) { 
            this.id = id;
        }
    
        private static void print(int id) { 
    
        }
    
        @Override
        public void run() { 
            while (cnt <= 100) { 
                lock.lock();
                System.out.println("thread_" + id + " num:" + cnt);
                cnt++;
                condition.signal();
                try { 
                    condition.await();
                } catch (InterruptedException e) { 
                    e.printStackTrace();
                }
                lock.unlock();
            }
        }
    
        public static void main(String[] args) { 
            Thread thread0 = new PrintNumber(0);
            Thread thread1 = new PrintNumber(1);
            thread0.start();
            thread1.start();
        }
    }

到这里我所能想到的解法就这么多了，不知道你们还有没有其他的解法，接下来我出几道扩展问题，希望能帮你更深入理解这个题目涉及到的多线程的知识点。

### 扩展问题 ###

##### 1. 如果是三个线程交替输出呢？ #####

解析：三个线程的解法可以使用`while (cnt%3 == id)`的方式实现忙等，但简单的**唤醒+等待**的方式必然不适用了， 没有判断的synchronized必然实现不了，java Object的notify和wait方法只能唤醒全部线程，然后另外两个线程输出前都需要额外判断下是否轮到自己输出了。这时候lock中condition的优势就体现出来了，它可以通过设置不同的condition来实现不同线程的精确唤醒。

#### 2. 生产者消费者 ####

解析：两个线程按顺序交替输出本质上就是多线程之间的相互协同，而这个领域另外一个非常有名且更常见的问题就是**生产者消费者问题**，两个线程按顺序交替输出你可以认为是当生产者和单消费者的一种特殊情况，更多关于**生产者消费者问题**的实现可以参考我之前的博客[https://blog.csdn.net/xindoo/article/details/80004003][https_blog.csdn.net_xindoo_article_details_80004003]

#### 3. synchronized和各种lock的底层实现 ####

解析：这个可以参考下网上其他博客，这里不再详细展开

> 欢迎关注我的专栏[《面试题精选》][Link 1]，**长期更新、永久免费**，希望能帮到大家。

[Link 1]: https://blog.csdn.net/xindoo/category_9991116.html
[format_png_pic_center]: /images/20210923/989dbd52249e45b983ce4fb1f0d05acd.png
[https_blog.csdn.net_xindoo_article_details_80004003]: https://blog.csdn.net/xindoo/article/details/80004003