Go
by smallnest

为什么说并发编程很难？

最近看到一本关于算法的新书，买过来学习。
这本书中有一道并发问题，也是我先前多次分过的一道题：水分子的产生：

这是一道并发题，在《The Little Book of Semaphores》v2.2.1 2006年版本中就有这道题("Building H2O"),而且据作者说这道题已经在伯克利大学的操作系统课程中十余年了，看起来是Andrews的并发编程的一道练习题。

这道题也被收编到leetcode的并发题中：H2O 生成。题目和这本书中的内容一样，是一道标记为中等难度的题目。

所以说这道题至少存在30年了，理论上大家对这道题目研究的就是透透的。

书中的解答和力扣中国的评论区解答的第一名是类似的,这是书上的解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public H2O() {
    
}
 private Semaphore h = new Semaphore(2);
 private Semaphore o = new Semaphore(2);
public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
	h.acquire(1);
    releaseHydrogen.run();
    o.release(1);
}
public void oxygen(Runnable releaseOxygen) throws InterruptedException {
    o.acquire(2);
	releaseOxygen.run();
    h.release(2);
}

首先这个解答有一个明显的瑕疵：private Semaphore o = new Semaphore(2);这一句应该初始化为0，而不是2，否则氧原子初始的时候毫无顾忌的就执行，一下释放四个氢原子。这是问题一。

力扣中国评论区第一名初始化就是正确的：

1
2
3
4
5
6
7
8
public H2O() {
    
}
 private Semaphore h = new Semaphore(2);
 private Semaphore o = new Semaphore(0);
 ......

这个代码看起来非常的简洁清爽，而且易懂，如果你提交代码，很快就通过，而且时间花费也很好，但是这个解答就对么？

回顾一下这个题目，其中有一条要求，就是每个水分子的原子必须来自不同的线程。

但是上面的Java实现，两个氢原子可能来自同一个线程，违反了“三三成组”的原则。

可是为什么答案还能提交通过呢？只能说力扣的测试集设置的不好，它并没有区分H来自哪个线程，只要输出"HHO"的组合就算通过了。

一个修改版Java代码实现如下，代码也不复杂，增加了一个phaser同步原语：

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
import java.util.concurrent.Phaser;
import java.util.concurrent.Semaphore;
class H2O {
    private Semaphore semO;
    private Semaphore semH;
    private Phaser phaser;
    public H2O() {
        semO = new Semaphore(1);
        semH = new Semaphore(2);
        phaser = new Phaser(3);
    }
    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        semH.acquire();
        releaseHydrogen.run();
        phaser.arriveAndAwaitAdvance();
        semH.release();
    }
    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        semO.acquire();
        releaseOxygen.run();
        phaser.arriveAndAwaitAdvance();
        semO.release();
    }
}

所以你看，即使是一个存在了30年的并发老题，要想写对也不容易。

我在百度也Review了几十个同学的good coder题，发现有至少一半以上的同学都出现过并发的问题，所以虽然说使用Go、Java语言很容易写并发程序，但是能写好确实是意见比较困难的事。

重点来了，这里我给大家推荐我的一本即将上线的新书《深入理解Go并发编程》，经过了4年多的沉淀和积累，厚积薄发，全面介绍Go并发编程方方面面，敬请期待。

在这本书中，也剖析了这道题，并给出了Go语言的一个解法：

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
package water
import (
    "context"
    "github.com/marusama/cyclicbarrier"
    "golang.org/x/sync/semaphore"
)
type H2O struct {
    semaH *semaphore.Weighted
    semaO *semaphore.Weighted
    b     cyclicbarrier.CyclicBarrier
}
func New() *H2O {
    return &H2O{
        semaH: semaphore.NewWeighted(2),
        semaO: semaphore.NewWeighted(1),
        b:     cyclicbarrier.New(3),
    }
}
func (h2o *H2O) hydrogen(releaseHydrogen func()) {
    h2o.semaH.Acquire(context.Background(), 1)
    // releaseHydrogen() 输出一个H
    releaseHydrogen()
    h2o.b.Await(context.Background())
    h2o.semaH.Release(1)
}
func (h2o *H2O) oxygen(releaseOxygen func()) {
    h2o.semaO.Acquire(context.Background(), 1)
    // releaseOxygen() 输出一个O
    releaseOxygen()
    h2o.b.Await(context.Background())
    h2o.semaO.Release(1)
}