1. 题目
1115. 交替打印FooBar
我们提供一个类：
class FooBar {
public void foo() {
for (int i = 0; i < n; i++) {
print("foo");
}
}
public void bar() {
for (int i = 0; i < n; i++) {
print("bar");
}
}
}
两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。
请设计修改程序，以确保 "foobar" 被输出 n 次。
示例 1:
输入: n = 1
输出: "foobar"
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。
示例 2:
输入: n = 2
输出: "foobarfoobar"
解释: "foobar" 将被输出两次。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-foobar-alternately
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 分析
本题有两个要求
- 顺序性，即foo要在bar之前打印，需要考虑先执行print bar的情况。
- 交替性，foo和bar需要轮流打印。
2.1. 方案一（基于volatile）
用一个变量来标记当前打印的是foo还是bar。这样就知道下一个操作需要打印foo还是bar。这个变量需要在线程间进行共享。共享没有问题，FooBar内的变量对同一个对象是可以访问的。但是需要能够及时同步。因此我们需要一个volatile变量。
1.0版本:
class FooBar {
private int n;
volatile boolean flag = true;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (!flag){
}
// printFoo.run() outputs "foo". Do not change or remove this line.
printFoo.run();
flag = false;
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printBar.run() outputs "bar". Do not change or remove this line.
while (flag){
}
printBar.run();
flag = true;
}
}
}
提交，超时了。为啥呢？
考虑CPU单核的情况，while (flag){}如果是bar线程先运行，将会不停执行while。foo线程无法抢占时间片，自然无法开始第一步print foo了。在多核环境下，虽然不会造成另一线程无法抢占时间片的问题，但是while循环是很耗时的，占用大量CPU资源，这也会使得运行时间变长而超时。
基于这样的分析，修改一下，增加Thread.sleep()，每次循环的时候，休眠一会儿。
2.0版本:
class FooBar {
private int n;
volatile boolean flag = true;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (!flag){
Thread.sleep(20);
}
// printFoo.run() outputs "foo". Do not change or remove this line.
printFoo.run();
flag = false;
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printBar.run() outputs "bar". Do not change or remove this line.
while (flag){
Thread.sleep(20);
}
printBar.run();
flag = true;
}
}
}
提交，进步了一点。还是超时。
我们已经把休眠时间调整的很小了（20ms），希望程序可以快点切换到下一个打印。我们或许可以通过继续把休眠时间调整的更小来通过这道题，但是我们有一个更好的方法。Thread.yield()
3.0版本来了:
class FooBar {
private int n;
volatile boolean flag = true;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (!flag){
Thread.yield();
}
// printFoo.run() outputs "foo". Do not change or remove this line.
printFoo.run();
flag = false;
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printBar.run() outputs "bar". Do not change or remove this line.
while (flag){
Thread.yield();
}
printBar.run();
flag = true;
}
}
}
通过了！！！
摘抄自LeetCode评论：https://leetcode-cn.com/problems/print-foobar-alternately/solution/xian-cheng-ping-zhang-de-wen-ti-yi-ban-you-san-cho/
while循环是比较耗费性能的，可能会导致执行结果超时。可以通过Thread.yield进一步控制线程的执行，而非比较粗力度的循环。当某个线程调用yield()方法时，就会从运行状态转换到就绪状态后，CPU从就绪状态线程队列中只会选择与该线程优先级相同或者更高优先级的线程去执行。总之加上Thread.yield性能会更高一点，因此用时会更少
什么是Thread.yield()?
摘抄自：https://www.cnblogs.com/java-spring/p/8309931.html
Java线程中的Thread.yield( )方法，译为线程让步。顾名思义，就是说当一个线程使用了这个方法之后，它就会把自己CPU执行的时间让掉，
让自己或者其它的线程运行，注意是让自己或者其他线程运行，并不是单纯的让给其他线程。
yield()的作用是让步。它能让当前线程由“运行状态”进入到“就绪状态”，从而让其它具有相同优先级的等待线程获取执行权；但是，并不能保证在当前线程调用yield()之后，其它具有相同优先级的线程就一定能获得执行权；也有可能是当前线程又进入到“运行状态”继续运行！
举个例子：一帮朋友在排队上公交车，轮到Yield的时候，他突然说：我不想先上去了，咱们大家来竞赛上公交车。然后所有人就一块冲向公交车，
有可能是其他人先上车了，也有可能是Yield先上车了。
但是线程是有优先级的，优先级越高的人，就一定能第一个上车吗？这是不一定的，优先级高的人仅仅只是第一个上车的概率大了一点而已，
最终第一个上车的，也有可能是优先级最低的人。并且所谓的优先级执行，是在大量执行次数中才能体现出来的。
2.2 方案二 Semaphore
Semaphore
https://blog.csdn.net/hanchao5272/article/details/79780045
基于Semaphore的代码如下:
class FooBar {
private int n;
private Semaphore semaphore = new Semaphore(1);
private volatile boolean foo = false;
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
semaphore.acquire();
// printFoo.run() outputs "foo". Do not change or remove this line.
printFoo.run();
foo = true;
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (!foo) {
}
// printBar.run() outputs "bar". Do not change or remove this line.
printBar.run();
foo = false;
semaphore.release();
}
}
}
作者：san-mu-32
链接：https://leetcode-cn.com/problems/print-foobar-alternately/solution/tong-guo-yi-ge-xin-hao-liang-kong-zhi-foohe-barde-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
涉及多线程，运行时间并不稳定。和方案一类似，在while循环中加入Thread.yield()，速度有一定提升。
2.3. 方案三 notify && wait
https://www.jianshu.com/p/1dafbf42cc54
class FooBar {
private int n;
private volatile boolean isFoo;
public FooBar(int n) {
this.n = n;
}
public synchronized void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
// synchronized (lock) {
// printFoo.run() outputs "foo". Do not change or remove this line.
printFoo.run();
isFoo = true;
this.notify();
if (i < n - 1) {
this.wait();
}
// }
}
}
public synchronized void bar(Runnable printBar) throws InterruptedException {
if (!isFoo) {
this.wait();
}
for (int i = 0; i < n; i++) {
// synchronized (lock) {
// printBar.run() outputs "bar". Do not change or remove this line.
printBar.run();
this.notify();
if (i < n - 1) {
this.wait();
}
// }
}
}
}
运行时间不稳定，应该是LeetCode的问题。
2.4. 方案四 CyclicBarrier
https://www.jianshu.com/p/333fd8faa56e
class FooBar {
private int n;
public FooBar(int n) {
this.n = n;
}
CyclicBarrier cb = new CyclicBarrier(2);
volatile boolean fin = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while(!fin);
printFoo.run();
fin = false;
try {
cb.await();
} catch (BrokenBarrierException e) {
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
try {
cb.await();
} catch (BrokenBarrierException e) {
}
printBar.run();
fin = true;
}
}
}
作者：KevinBauer
链接：https://leetcode-cn.com/problems/print-foobar-alternately/solution/java-bing-fa-gong-ju-lei-da-lian-bing-by-kevinbaue/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.5. 方案五 CyclicBarrier + CountdownLatch
CyclicBarrier用于保证每一轮的foobar的打印。CountdownLatch用于保证单轮内，先打印foo，再打印bar。
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
class FooBar {
private int n;
private CountDownLatch a;
private CyclicBarrier barrier;// 使用CyclicBarrier保证任务按组执行
public FooBar(int n) {
this.n = n;
a = new CountDownLatch(1);
barrier = new CyclicBarrier(2);// 保证每组内有两个任务
}
public void foo(Runnable printFoo) throws InterruptedException {
try {
for (int i = 0; i < n; i++) {
printFoo.run();
a.countDown();// printFoo方法完成调用countDown
barrier.await();// 等待printBar方法执行完成
}
} catch(Exception e) {}
}
public void bar(Runnable printBar) throws InterruptedException {
try {
for (int i = 0; i < n; i++) {
a.await();// 等待printFoo方法先执行
printBar.run();
a = new CountDownLatch(1); // 保证下一次依旧等待printFoo方法先执行
barrier.await();// 等待printFoo方法执行完成
}
} catch(Exception e) {}
}
}
作者：bonaluo
链接：https://leetcode-cn.com/problems/print-foobar-alternately/solution/javashi-yong-yi-ge-countdownlatchhe-yi-ge-cyclicba/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
3. 总结
本题需要解决两个问题。
- 两个线程必须先后执行，
- foo线程必须保证先执行。
为了解决这两个问题，5个方案选择了不同的方案组合。主要分为无锁和有锁两种方案。
为了解决foo线程先执行的问题。有使用volatile变量和CountdownLatch两种方法。volatile变量使用的是无锁的方案。通过一个死循环，组织bar线程先运行。优点是可以快速感知状态变换，无需线程切换。缺点是资源消耗大，需要使用Thread.yield()。否则会超时。CountdownLatch采用的是有锁的方案，因此会有线程的切换，单不会大量占用系统资源。在线程占用时间长的场景体验更佳。
为了让两个线程先后执行，需要在foo线程执行后挂起线程，让bar线程运行。在bar线程运行后，再让foo线程执行。无锁方案，继续用volatile变量即可。有锁方案则可以有几种选择。Semaphore，CyclicBarrier，notify&wait，Lock。
4. 引申
在 单核 / 单CPU 的系统上使用 自旋锁 是没有意义的，因为它就一个运行线程/核心，你占着不放，那么其他线程将得不到运行，其他线程得不到运行，这个锁就不能被解锁。换句话说，在 单核 / 单CPU 系统使用 自旋锁，除了浪费点时间外没有一点好处。这时如果让这个线程（记为线程A）休眠，其他线程就得以运行，然后就可能会解锁这个 自旋锁，线程A就可能在重新被唤醒后，如愿以偿的持有锁。
在 多核 / 多CPU 的系统上，特别是大量的线程只会短时间的持有锁的时候，这时如果使用 互斥锁，在使线程睡眠和唤醒上浪费大量的时间，也许会显著降低程序的运行性能。使用 自旋锁，线程可以充分利用系统调度程序分配的时间片(经常阻塞很短的时间，不用休眠，然后马上继续它们后面的工作了)，以达到更高的处理能力和吞吐量。
