1.按序打印
解法一：使用volatile
public class FooWithVolatile {
    private volatile int count;

    public FooWithVolatile() {

    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        count++;

    }

    public void second(Runnable printSecond) throws InterruptedException {
        // printSecond.run() outputs "second". Do not change or remove this line.
        while(count != 1) { }
        printSecond.run();
        count++;
    }

    public void third(Runnable printThird) throws InterruptedException {
    	while(count != 2) { }
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}



类似的，我们也可以使用AtomicInteger，不过其实AtomicInteger底层也是使用了volatile字段，只不过在计算时会使用CAS解决原子性问题，但是这里的while循环对自增操作进行了阻塞，所以不会出现三个线程同时对count自增的情况，所以没必要使用AtomicInteger，更何况CAS操作里面的while循环也是很耗费资源的

解法二：使用CountDownLatch
public class FooWithCountDownLatch {
    private CountDownLatch second = new CountDownLatch(1);
    private CountDownLatch third = new CountDownLatch(1);

    public FooWithCountDownLatch() {
    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        second.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
    	second.await();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        third.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
    	third.await();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}



类似的，这里我们使用两个“门栓”栓住（阻塞）second方法和third方法执行run方法打印结果，当first方法执行完毕后，释放second的门栓让second方法打印结果，second方法执行完毕后，释放third的门栓让third方法打印结果



2.交替打印FooBar
class FooBarWithCountDownLatch {
    private int n;
    private CountDownLatch fooLatch = new CountDownLatch(0);
    private CountDownLatch barLatch = new CountDownLatch(1);

    public FooBarWithCountDownLatch(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        for (int i = 0; i < n; i++) {
            fooLatch.await();
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            fooLatch = new CountDownLatch(1);
            barLatch.countDown();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {

        for (int i = 0; i < n; i++) {
            barLatch.await();
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            barLatch = new CountDownLatch(1);
            fooLatch.countDown();
        }
    }
}


这里要注意，CountDownLatch和CyclicBarrier不一样，CountDownLatch是一次性的，countDown到0之后不会自己恢复成1，所以要每次new一个CountDownLatch对象。



3.打印零与奇偶数
public class ZeroEvenOdd {
    private int n;
    private CountDownLatch zero = new CountDownLatch(0);
    private CountDownLatch even = new CountDownLatch(1);
    private CountDownLatch odd = new CountDownLatch(1);

    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            zero.await();
            printNumber.accept(0);
            zero = new CountDownLatch(1);
            if(i % 2 == 0) {
                odd.countDown();
            } else {
                even.countDown();
            }
        }
        
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i < n; i+=2) {
            even.await();
            printNumber.accept(i);
            even = new CountDownLatch(1);
            zero.countDown();
        }

    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i < n; i+=2) {
            odd.await();
            printNumber.accept(i);
            odd = new CountDownLatch(1);
            zero.countDown();
        }
    }
}


这道题没什么好说的，做法也同样很多样，只要仔细点，都可以做对，但是我感觉都没直接用CoutDownLatch好。



4.H2O
public class H2O {
    private Semaphore hSemaphore = new Semaphore(2);
    private Semaphore oSemaphore = new Semaphore(0);

    public H2O() {

    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSemaphore.acquire();
        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
        releaseHydrogen.run();
        oSemaphore.release();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSemaphore.acquire(2);
        // releaseOxygen.run() outputs "H". Do not change or remove this line.
        releaseOxygen.run();
        hSemaphore.release(2);
    }
}


实在想不到Semaphore以外的做法，虽然看题解确实有，但是反而不怎么好

一、Print in Order


Suppose we have a class:


public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}


The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().


Example 1:
 Input: [1,2,3]
 Output: "firstsecondthird"
 Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.



方法1：信号量，semaphore和mutex都是内核对象，都可用于进程间的同步，并且都特别占用系统资源,区别是，mutex只能由一个线程(进行)访问被保护的资源。semaphore 是一种带计数的mutex的锁定，可定义同时访问被保护的资源的线程数





import java.util.concurrent.Semaphore;
class Foo {
    private static Semaphore firstSemaphore = new Semaphore(1);
    private static Semaphore secordSemaphore = new Semaphore(0);
    private static Semaphore thirdSemaphore = new Semaphore(0);
    public Foo() {

    }
    public void first(Runnable printFirst) throws InterruptedException {
        firstSemaphore.acquire();
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        secordSemaphore.release();
    }
    public void second(Runnable printSecond) throws InterruptedException {
        secordSemaphore.acquire();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        thirdSemaphore.release();
    }
    public void third(Runnable printThird) throws InterruptedException {
        thirdSemaphore.acquire();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
        firstSemaphore.release();
    }
}


方法2、原子类AtomicInteger,AtomicInteger是一个提供原子操作的Integer类，通过线程安全的方式操作加减





import java.util.concurrent.atomic.AtomicInteger;
class Foo {

    private final AtomicInteger count = new AtomicInteger(0);
    public Foo() {

    }
    public void first(Runnable printFirst) throws InterruptedException {
        //自旋，避免进入内核态，不过浪费CPU资源
        while (count.get() != 0) {}
        printFirst.run();
        count.incrementAndGet();
    }
    public void second(Runnable printSecond) throws InterruptedException {
        while (count.get() != 1) {}
        printSecond.run();
        count.incrementAndGet();
    }
    public void third(Runnable printThird) throws InterruptedException {
        while (count.get() != 2) {}
        printThird.run();
        count.set(0);
    }
}


方法3：倒计时器CountDownLatch，参考方法2。在多线程协作完成业务功能时，CountDownLatch能让我们很轻松实现下面这个需求，当需要等待其他多个线程完成任务之后，主线程才能继续往下执行业务功能


二、Print FooBar Alternately


Suppose you are given the following code:


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");
    }
  }
}


The same instance of FooBar will be passed to two different threads. Thread A will call foo()while thread B will call bar(). Modify the given program to output "foobar" n times.

 Example 2:
 Input: n = 2
 Output: "foobarfoobar"
 Explanation: "foobar" is being output 2 times.



这题其实是题目一的升级版，也可以使用信号量来轻松完成，这里给出其他解法


线程问题无非是要保证一致性、有序性和避免死锁，可见性可以使用volatile来保证，有序性可以使用锁来保证，死锁问题我们可以打破死锁的条件，也就是需要批量申请好资源或者按顺序获取到所有资源后才算获取到锁，比如





class FooBar {
    private int n;

    private List<String> als;

    public FooBar(int n) {
        this.n = n;
        als = new ArrayList<>(2);
    }

    synchronized void  apply(String pre,String next) {
        while (als.contains(pre)||als.contains(next)) {
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        als.add(pre);
        als.add(next);
    }

    synchronized void  free(String pre,String next) {
        als.remove(pre);
        als.remove(next);
        notifyAll();
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        for (int i = 0; i < n; i++) {
                apply("bar","foo");
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                free("foo","bar");

        }
    }

    public void bar(Runnable printBar) throws InterruptedException {

        for (int i = 0; i < n; i++) {
            apply("foo","bar");
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            free("bar","foo");
        }
    }
}


但是上面的示例无法满足本题要求，当n=1时输出结果可能是foobar也可以是barfoo，同理n=k时也会有顺序性问题，看似通过add和remove字符串顺序来解决，但是没有达到效果，具体分析过程留给读者完成


我们换种方法来完成，使用标准的生产-消费模型





class FooBar {
    private int n;
    private Object lock;
    private Boolean printFooStatus;
    public FooBar(int n) {
        this.n = n;
        lock = new Object();
        printFooStatus = true;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
              synchronized (lock) {
                  //必须使用while
                  while (!printFooStatus){
                      lock.wait();
                  }
                  // printFoo.run() outputs "foo". Do not change or remove this line.
                  printFoo.run();
                  printFooStatus = false;
                   //必须放在synchronized里面
                  lock.notifyAll();
              }
        }
    }
    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (lock) {
                //必须使用while
                while (printFooStatus) {
                    lock.wait();
                }
                // printBar.run() outputs "bar". Do not change or remove this line.
                printBar.run();
                printFooStatus = true;
                //必须放在synchronized里面
                lock.notifyAll();
            }
        }
    }
}


这里需要注意的几个点：

 1、初学者理解wait()的时候都认为是将当前线程阻塞，所以Thread.currentThread().wait();视乎很有道理。但是不知道大家有没有发现，在JDK类库中wait()和notify()方法并不是Thread类的，而是Object()中的。在其他线程调用此对象的 notify() 方法或 notifyAll() 方法前，当前线程等待
 2、始终使用while循环来调用wait方法，永远不要在循环外调用wait方法，这样做的原因是尽管并不满足条件，但是由于其他线程调用notifyAll方法会导致被阻塞线程意外唤醒，此时执行条件不满足，它会导致约束失效
 3、唤醒线程，应该使用notify还是notifyAll?notify会随机通知等待队列中的一个线程，而notifyAll会通知等待队列中所有线程，可知notify是有风险的 ，可能导致某些线程永远不会被通知到
 4、当前线程必须拥有此对象监视器，然后才可以放弃对此监视器的所有权并等待 ，直到其他线程通过调用notify方法或notifyAll方法通知在此对象的监视器上等待的线程醒来,然后该线程将等到重新获得对监视器的所有权后才能继续执行。否则会报IllegalMonitorStateException 错误


不过Object的wait\notify\notifyAll原理是基于内核中的对象监视器Monitor完成的,有可能导致大量的上下文切换。为了更好的性能，往往使用基于AQS的显示锁ReetrantLock中的成员变量ConditionObject代替。AQS中存在一个同步队列，当一个线程没有获取到锁时就会进入到同步队列中进行阻塞，如果被唤醒后获取到销，则移出同步队列。另外AQS中还存在一个条件队列，通过addWaiter方法，可以将wait()方法调用的线程放入到条件队列中，线程进入等待状态，当调用signal或者signalAll方法时，线程就会被唤醒，之后进入到同步队列中。其中条件队列是通过链表实现的，所以可以支持多个等待队列。也就是说使用基于AQS接口的await\signal\signalAll原理是基于JAVA代码层实现的，性能有更大的优势


所以本题的另外一种写法是





import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
class FooBar {
    private int n;
    private Boolean printFooStatus;
    private ReentrantLock reentrantLock;
    private Condition condition;
    public FooBar(int n) {
        this.n = n;
        printFooStatus = true;
        //不管使用公平锁还是非公平锁，在本题中都没有区别
        reentrantLock= new ReentrantLock(false);
        condition = reentrantLock.newCondition();
    }
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            reentrantLock.lock();
            try {
                while (!printFooStatus){
                    condition.await();
                }
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
            } catch (Exception e) {
               e.printStackTrace();
            } finally {
                printFooStatus = false;
                //同理：必须放在锁内
                 condition.signalAll();
                reentrantLock.unlock();

            }
        }
    }
    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
          reentrantLock.lock();
          try {
              while (printFooStatus){
                  condition.await();
              }
              // printBar.run() outputs "bar". Do not change or remove this line.
              printBar.run();
          } catch (Exception e) {
             e.printStackTrace();
          } finally {
              printFooStatus = true; 
              //同理：必须放在锁内
               condition.signalAll();
              reentrantLock.unlock();

          }
        }
    }
}


三、Print Zero Even Odd


Suppose you are given the following code:


class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // constructor
  public void zero(printNumber) { ... }  // only output 0's
  public void even(printNumber) { ... }  // only output even numbers
  public void odd(printNumber) { ... }   // only output odd numbers
}


The same instance of ZeroEvenOdd will be passed to three different threads:



Thread A will call zero() which should only output 0's.
Thread B will call even() which should only ouput even numbers.
Thread C will call odd() which should only output odd numbers.
 Each of the thread is given a printNumbermethod to output an integer. Modify the given program to output the series 010203040506… where the length of the series must be 2n.



Example 1:
 Input: n = 2
 Output: "0102"
 Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). "0102" is the correct output.

 Example 2:
 Input: n = 5
 Output: "0102030405"



提示：使用信号量


四、Building H2O


There are two kinds of threads, oxygen and hydrogen. Your goal is to group these threads to form water molecules. There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given a releaseHydrogen and releaseOxygen method respectfully, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must be able to immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

 In other words:


If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.
If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.
 We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that bond and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

 Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.



Example 1:
 Input: "HOH"
 Output: "HHO"
 Explanation: "HOH" and "OHH" are also valid answers.





class H2O {

    private Object lock = new Object();
    private int counter =0;
    public H2O() {

    }
    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {

     synchronized (lock) {
            while(counter==2){
                lock.wait();
            }
            releaseHydrogen.run();
            counter++;
            lock.notifyAll();
      }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        synchronized (lock) {
            while(counter!=2){
                lock.wait();
            }
            releaseOxygen.run();
            counter=0;
            lock.notifyAll();
      }

    }
}

文章来源：www.liangsonghua.me
作者介绍：京东资深工程师-梁松华，在稳定性保障、敏捷开发、JAVA高级、微服务架构方面有深入的理解

什么？导致我leetcode超时的不是算法是并发？
（我写这篇文章真的只是为了打发时间，内容严重逻辑不清，既 不易懂 也 不深入，我不认为这篇文章具有阅读价值，所以看到这里就可以把它关掉了！）

本文由 CDFMLR 原创，收录于个人主页 https://clownote.github.io，并同时发布到 CSDN。本人不保证 CSDN 排版正确，敬请访问 clownote 以获得良好的阅读体验。

问题的提出
Emmmm，我很久很久（快半年了吧）没有刷过题了，昨天晚上无聊就打开了 leetcode 随便写了一道题：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-substring

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

emmmm，首先的想法是动规，我一般都不爱用动规，空间消耗大。做了那么久开发再回来看算法，就觉得，时间稍微慢点可以等，内存一满就彻底炸了。
然后，我想到了最长公共子串，把这个字符串和它的反串求一个最长公共子串就是最长回文子串了。。。最长公共子串又是动规。😠
不想用动规，又不齿于暴力，那就硬写吧。
我的思路是遍历一次字符串，尝试以每个字符为回文中心，尽量去往两边“拓展”，得到以每个字符为中心的最长回文串，取这些拓展得的回文串中最长的输出。
我这个思路时间应该也许大概是 $O(n^2)$ 吧（颓废到连这个都不会算了😭）；空间可能比较好，都是调整指针的值，$O(1)$ 吧。
然后，我准备开始写代码，突然意识到回文有两！种！情！况！

第一种，形如 aba，中心是一个字符 b；
第二种，形如 abba，中心在两个字符 b 之间，或者也可以看作中心是两个字符 bb

所以，遍历字符串时，每个迭代要拓展两次，一次是以当前字符为中心（aba 型），一次是以当前字符+后一个字符为中心（abba 型）。
Golang 实现如下：
func longestPalindrome(s string) string {
	if s == "" {
		return s
	}
	b := []byte(s)
	l, r := 0, 0
	for i := 0; i < len(b); i++ {
		laba := ext(b, i, i)
		labba := ext(b, i, i+1)

		var m int
		if laba > labba {
			m = laba
		} else {
			m = labba
		}
		if m > r-l+1 {
			l = i - (m-1)/2
			r = i + m/2
		}
	}
	return string(b[l : r+1])
}

func ext(b []byte, l, r int) int {
	for l >= 0 && r < len(b) && b[l] == b[r] {
		l--
		r++
	}
	return r - l - 1 // r - l + 1 - 2
}

提交跑一下，4ms（击败91.02%），2.3MB（击败49.75%）。
emmm，我不理解为什么空间占用这么高，传参到时候 Golang 里的 []byte 应该是传了引用呀（可以理解成也就是传指针），其他的基本都是 int 了，我暂时想不到好办法继续在空间上做优化。
所以我考虑了一下能不能在时间上更进一步。考虑这一段代码：
laba := ext(b, i, i)
labba := ext(b, i, i+1)

就是分别计算 aba 型和 abba 型的回文拓展。先算完一个，再算另一个，我想这里会比较耗时。如果让他们同时算会发生什么？
试试看，主要的改动就是开两个 goroutine 去执行这两个函数：
func ext(b []byte, l, r int, cl chan int) {
	for l >= 0 && r < len(b) && b[l] == b[r] {
		l--;
		r++;
	}
	cl <- r - l -1
}

func longestPalindrome(s string) string {
	if s == "" {
		return s
	}
	b := []byte(s )
	l, r := 0, 0
	for i := 0; i < len(b); i++ {
        
		cl1 := make(chan int)
		cl2 := make(chan int)

		go ext(b, i, i, cl1)
		go ext(b, i, i+1, cl2)

		laba := <- cl1
		labba := <- cl2

		var m int
		if laba > labba {
			m = laba
		} else {
			m = labba
		}
		if m > r - l + 1 {
			l = i - (m - 1) / 2
			r = i + m / 2
		}
	}
	return string(b[l: r + 1])
}

提交，😱😱😱，40ms，6.2MB，发生了什么？
我以为问题出在这里：
laba := <- cl1
labba := <- cl2

这里是先阻塞在 laba 这里等 cl1 传出来，然后再等 cl2 出来。万一 cl2 先算完出来了，还是要阻塞到 cl1 出来，可能这里耗时了。所以再改一下 longestPalindrome的策略，用一个 for-select：
select 不能 fallthrough，所以为了及时 break，减少一次阻塞把每个 case 里都写了退出判断，恶心了一点。
func longestPalindrome(s string) string {
	if s == "" {
		return s
	}
	b := []byte(s )
	l, r := 0, 0
	for i := 0; i < len(b); i++ {
		// laba := ext(b, i, i)
		// labba := ext(b, i, i+1)
		cl1 := make(chan int)
		cl2 := make(chan int)

		go ext(b, i, i, cl1)
		go ext(b, i, i+1, cl2)

		var laba int
		var labba int
		cnt := 0
LOOP:		for {
			select {
			case laba = <- cl1:
				cnt++
				if (cnt >= 2) {
					break LOOP
				}
			case labba = <- cl2:
				cnt++
				if (cnt >= 2) {
					break LOOP
				}
			default:
				if (cnt >= 2) {
					break LOOP
				}
			}
		}

		var m int
		if laba > labba {
			m = laba
		} else {
			m = labba
		}
		if m > r - l + 1 {
			l = i - (m - 1) / 2
			r = i + m / 2
		}
	}
	return string(b[l: r + 1])
}

再提交，应该会快一点吧，结果是——超。出。时。间。限。制。而且超的还很多，只过了22个测试用例。
我哭了，并发了不是应该更快吗？是 leetcode 的锅吧。
还是在本地测试一下吧：
func main() {
	s := []string{"babad", "cbbd", "", "a", "aa", "aaa", "aaaa"}
	for i := 0; i < 10000; i++ {
		longestPalindrome(s[i%7])
	}
}

随便搞几个例子循环着跑10000次，$ time go run 看一下。
第一个版本（不并发）:
real    0m0.246s
user    0m0.216s
sys     0m0.137s

最后一个版本（for-select）:
real    0m1.005s
user    0m1.036s
sys     0m0.518s

\拍桌 还真的是并发导致了慢啊！
但是，为什么？
问题的分析
为了研究这个问题，我们把刚才三个版本的代码都简化一下：
v1，不并发：
// v1.go

package main

import (
	"math/rand"
	"time"
)

func somethingCost() bool {
	// time.Sleep(time.Duration(rand.Intn(10)) * time.Millisecond)
	time.Sleep(1 * time.Millisecond)
	return true
}

func main() {
	rand.Seed(time.Now().UnixNano())

	for i := 0; i < 100; i++ {
		foo := somethingCost()
		bar := somethingCost()

		if foo == bar {
			continue
		}
	}
}

v2，并发，阻塞在第一个 channel：
// v2.go

package main

import (
	"math/rand"
	"time"
)

func somethingCost(ch chan bool) {
	// time.Sleep(time.Duration(rand.Intn(10)) * time.Millisecond)
	time.Sleep(1 * time.Millisecond)
	ch <- true
}

func main() {
	rand.Seed(time.Now().UnixNano())

	ch1 := make(chan bool)
	ch2 := make(chan bool)

	for i := 0; i < 100; i++ {
		go somethingCost(ch1)
		go somethingCost(ch2)

		foo := <-ch1
		bar := <-ch2

		if foo == bar {
			continue
		}
	}
}

v3，运用 select：
// v3.go

package main

import (
	"math/rand"
	"time"
)

func somethingCost(ch chan bool) {
	// time.Sleep(time.Duration(rand.Intn(10)) * time.Millisecond)
	time.Sleep(1 * time.Millisecond)
	ch <- true
}

func main() {
	rand.Seed(time.Now().UnixNano())

	ch1 := make(chan bool)
	ch2 := make(chan bool)

	for i := 0; i < 100; i++ {
		cnt := 0

		go somethingCost(ch1)
		go somethingCost(ch2)

	LOOP:
		for {
			select {
			case <-ch1:
				cnt++
			case <-ch2:
				cnt++
			default:
				if cnt >= 2 {
					break LOOP
				}
			}
		}
	}
}

我们首先在 somethingCost 里睡眠了相同的时间，来模拟执行一个慢速任务，运行代码得到类似如下的结果：
$ time go run v1.go

real    0m0.553s
user    0m0.204s
sys     0m0.159s

$ time go run v2.go

real    0m0.379s
user    0m0.182s
sys     0m0.135s

$ time go run v3.go

real    0m0.362s
user    0m0.314s
sys     0m0.138s


【补充】real时间、user时间和sys时间。

real时间是指挂钟时间，也就是命令开始执行到结束的时间。这个短时间包括其他进程所占用的时间片，和进程被阻塞时所花费的时间。
user时间是指进程花费在用户模式中的CPU时间，这是唯一真正用于执行进程所花费的时间，其他进程和花费阻塞状态中的时间没有计算在内。
sys时间是指花费在内核模式中的CPU时间，代表在内核中执系统调用所花费的时间，这也是真正由进程使用的CPU时间。

参考： Linux命令大全. time命令[OL].https://man.linuxde.net/time, 2020

用物理实验的方法，多次重复实验，得到如下结果：




【注】实验环境：


Computer: MacBook Pro (13-inch, 2017, Two Thunderbolt 3 ports)


CPU: 2.3 GHz Intel Core i5


RAM: 8 GB 2133 MHz LPDDR3


OS: macOS Mojave 10.14.6


Golang: go version go1.12 darwin/amd64



实验次数少，数据不太好，不管了，我懒得搞大规模的实验（其实我只是边研究边写这篇文章打发时间）。
从实验的结果来看，有两点比较肯定：

Real 时间上，v3 略优于 v2 优于 v1
User 时间上，v1 约等于 v2 优于 v3

由此，可以推知：

在现实环境（正常的多核计算机）使用中，如 v3 版本的程序，使用 goroutine-for-select 的方案可以运行得比较快（real time，与不并发相比），但在等待返回的 channel 不多时与不使用 for-select 区别不大。
在 goroutine 和 channel 比较少的时候使用 for-select 的策略，进程所花费的时间（user time）会明显加大。

注意，是在 goroutine 和 channel 比较少的时候 v2 的 user time 优于 v3。当我们增多 goroutine，比如开到 1000 个，结果就不一样了（我不想用 v1 依次执行1000次函数，结果可想而知，没有可比性了）：
$ time go run v2.go

real    0m5.824s
user    0m8.036s
sys     0m3.967s

$ time go run v3.go

real    0m1.919s
user    0m3.006s
sys     0m0.244s

所以，在慢速任务比较多的时候，使用类似于 v3 的 for-select 会大幅度提高效率。
我们再来看一下如果任务速度比较快，例如我们直接把 Sleep 注释掉，然后开最外层的循环次加到100次：
$ time go run v1.go

real    0m0.302s
user    0m0.168s
sys     0m0.127s

$ time go run v2.go

real    0m0.373s
user    0m0.198s
sys     0m0.149s

$ time go run v3.go

real    0m0.353s
user    0m0.301s
sys     0m0.142s

这种情况下 v2、 v3 就显得没有优势了，这时多线程上下午切换等等的开支会造成比较大的额外开支，导致整体运行效率低下。这也就是我们提交到 leetcode 的代码超时的问题所在。
（啊，我不想写了，打中文好麻烦，开模mo糊fu拼音都不能满足我的需求。反正我已经知道我想要的答案了，而且还在研究过程中得到了更多的收获，还有好多东西我没写，但懒得写了，想知道的话自己去研究啊，方法我给你了，控制个变量总会了吧！我再写句烂总结就去睡觉了，再见！🤯）
问题的总结
（不想写！）
这个故事告诉我们，不要在需要并发的任务少，通信不复杂的情况下（比如刷 leetcode 的算法题）尝试使用处理高并发的手段，异步的方法还是用来处理比较慢的任务比较好。
（扯不下去了，就这样吧，这篇文章明天发。）
某个头疼的夜				（澄清：头疼 $\neq$ 发烧；我没发烧，没得肺炎，只是很烦！）

题目来源：https://leetcode.com/problems/print-in-order/

问题描述

1114. Print in Order

Easy

Suppose we have a class:

public class Foo {

  public void first() { print("first"); }

  public void second() { print("second"); }

  public void third() { print("third"); }

}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

 

Example 1:

Input: [1,2,3]

Output: "firstsecondthird"

Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: [1,3,2]

Output: "firstsecondthird"

Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

 

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.

------------------------------------------------------------

题意

编写线程间同步的代码，使得三个并行执行的线程按固定顺序输出

------------------------------------------------------------

思路

用两个共享变量first_flag和second_flag，分别控制第二个线程和第三个线程的执行，使用wait()和notifyAll()进行线程间通信。注意notify/notifyAll唤醒的线程是从wait之后开始执行而不是从同步块的首部开始执行。

------------------------------------------------------------

代码

class Foo {
    private Boolean first_flag = false;
    private Boolean second_flag = false;

    public Foo() {
        
    }

    public synchronized void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        notifyAll();
        first_flag = true;
    }

    public synchronized void second(Runnable printSecond) throws InterruptedException {
        while (!first_flag) {
            wait();
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        notifyAll();
        second_flag = true;
    }

    public synchronized void third(Runnable printThird) throws InterruptedException {
        while (!second_flag) {
            wait();
        }
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}