Table of Contents

本文是 Concurrency in Go 这本书的第一章「并发介绍」的阅读笔记。

为什么并发编程难

并发编程难不需要太多的解释。有时候需要很长时间或者较大的并发量，才能发现并发问题。幸运的是，这些问题是有共性的，我们讨论它们是如何产生的、产生的原因和如何解决它们。

竞争条件

如果两个或者多个操作必须按照正确的顺序执行，然而程序并没有保证这个顺序，就会发生竞争条件（Race Conditions），导致意想不到的 Bug。大多数情况下，会出现在所谓的数据竞争（data race）中，当一个并发操作尝试读取变量，而在某个不确定的时间另一个并发操作尝试写入这个变量。下面是个例子：

func main() {
	var data int
	go func() {
		data++
	}()

	if data == 0 {
		fmt.Printf("the value is %d", data)
	}
}

上面代码有三处地方试图访问 data 变量：data++、if data == 0 判断、打印 data。data++ 操作在一个协程里，导致程序执行的顺序是不确定的，有三种可能的结果：

不打印任何东西。data++ 在 if data == 0 之前执行
打印 “the value is 0”。if data == 0 和打印 data 都在 data++ 之前执行
打印 “the value is 1”。if data == 0 在 data++ 之前执行，但 data++ 在打印 data 之前执行

大多数情况下，引入数据竞争的原因是我们使用顺序性思维来思考问题。如上面的代码，会习惯性假设协程中的 data++ 会在 if 语句之前执行。

一些人会在代码里随意添加 sleep，如：

func main() {
	var data int
	go func() { data++ }()

	time.Sleep(time.Second) // This is bad!
	if data == 0 {
		fmt.Printf("the value is %d", data)
	}
}

我们解决了数据竞争了吗？其实并没有，之前的三种结果仍然可能出现，只是从概率上增大了 the value is 1 出现的概率。概率上接近逻辑的正确性，永远不会真的变成逻辑上的正确。并且这种做法会让程序执行低效。

竞争条件的 Bug 是难以发现的，往往代码看上去是在以正确的顺序在执行，可能事实上以正确的顺序执行只是概率上比较大，早晚可能暴露出 Bug。

原子性

当某物被认为是原子的，或者具有原子性时，这意味着在其所处的上下文（context）中，它是不可分割（indivisible）或不可中断（uninterruptible）的。

理解上下文概念是很重要的。在一个上下文里某个操作是原子性的，可能在另一个上下文里不是原子性的。在进程上下文中是原子操作可能在操作系统上下文中不是原子操作；在操作系统上下文中是原子操作可能在机器上下文中不是原子操作；而在机器上下文中，某些被认为是原子性的操作，在应用程序环境里却未必如此。换句话说，一个操作是否具有原子性取决于当前定义的范围。

现在让我们来看下不可分割和不可中断的含义。在定义的上下文中，原子性的事情将会完整地发生，并且没有其他事情同时发生。来看个例子：

i++

这个操作看起来是具体原子性的，但简单的分析后，其实有三个操作：

获取 i 的值
增加 i 的值
存储 i 的值

尽管这三个操作中的每一个都是具有原子性的，但根据你的上下文，它们的组合可能不具有原子性的。这揭示了原子操作的一个有趣现象：将它们组合在一起并不一定会产生更大的原子操作。使操作成为原子操作取决于你希望其在哪个上下文中具有原子性。如果所处的上下文是没有并发的程序，则此代码在该上下文中是有原子性的。如果所处的上下文是不向其他 goroutine 暴露 i 的 goroutine，则此代码也是具有原子性的。

原子性之所以重要，是因为如果某个操作是原子的，在并发上下文中它就隐式地安全的。这使得我们能够组合逻辑正确的程序，并且——正如我们后面将看到的那样——甚至可以作为优化并发程序的一种方式。

大多数语句都不是原子的，更别说函数、方法和程序了。如果原子性是组合逻辑正确程序的关键，而大多数语句都不是原子的，那么我们如何保证原子性呢？简单来说，我们可以通过采用各种技术来强制实现原子性。然后这个问题就变成了如何确定代码中哪些地方需要具有原子性以及在什么粒度上进行。

内存访问同步

假设有这样一个数据竞争：两个并发协程试图访问相同的内存区域，它们访问内存方式不是原子的。如：

func main() {
	var data int
	go func() { data++ }()
	
	if data == 0 {
		fmt.Printf("the value is %d", data)
	} else {
		fmt.Printf("the value is %d", data)
	}
}

这里只是添加了一个 else 语句，不管 data 为何值，都会有打印输出。数据竞争还是存在的，所以该程序的输出也是完全不确定的。

实际上，程序需要独占访问共享资源有一个专有名词：临界区（critical section）。在这个例子中，有三个临界区：

main 的子协程增加 data 的值
main 协程的 if 语句，获取 data 判断是否为 0
main 协程的打印语句，获取 data 的值

有很多方法保护程序的临界区。其中一个办法是在临界区之间同步访问内存，如下：

func main() {
	var data int
	var mu sync.Mutex
	go func() {
		mu.Lock()
		data++
		mu.Unlock()
	}()

	mu.Lock()
	if data == 0 {
		fmt.Printf("the value is %d", data)
	} else {
		fmt.Printf("the value is %d", data)
	}
	mu.Unlock()
}

通过加锁，将三个临界区划分两个，子协程的 data++ 操作加锁，main 协程 data == 0 和打印 data 两个操作整体加锁。这样保证同一时间只有一个协程能操作 data 内存，即同步访问内存。

虽然这样解决了数据竞争，但并没有真正解决竞争条件。因为这个程序的执行顺序仍然是不确定的，加锁只是缩小了不确定的范围。这个例子中，子协程的 data++ 操作和 main 里的 if 语句块执行顺序仍然是不确定的。

死锁

死锁是指所有并发协程都在相互等待的状态，在这种情况下，程序将无法恢复。看一个例子：

type value struct {
	mu    sync.Mutex
	value int
}

var wg sync.WaitGroup

func main() {
	printSum := func(v1, v2 *value) {
		defer wg.Done()
		v1.mu.Lock()
		defer v1.mu.Unlock()

		time.Sleep(2 * time.Second)

		v2.mu.Lock()
		defer v2.mu.Unlock()

		fmt.Printf("sum=%v\n", v1.value+v2.value)
	}

	var a, b value
	wg.Add(2)
	go printSum(&a, &b)
	go printSum(&b, &a)
	wg.Wait()
}

执行程序后，会报死锁错误。

fatal error: all goroutines are asleep - deadlock!

看下这个程序的执行时序图：

本质上，第一个调用 printSum 函数将 a 的锁锁住，并尝试锁 b 的锁，但与此同时，第二个调用 printSum 函数将 b 的锁锁住，并尝试锁 a 的锁。最终两个 goroutine 无限地相互等待。为了保持这个例子的简单性，使用 time.Sleep 来触发死锁。

当我们用时序图方式呈现时，这种死锁发生的原因似乎非常明显，但我们需要更严格的定义。事实证明，出现死锁必须满足一些条件，在 1971 年，Ed Coffman 在一篇论文中列举了这些条件。并成为帮助检测、预防和纠正死锁的基础。

产生死锁的必要条件：

互斥条件：一个资源每次只能被一个进程使用
请求与保持条件：一个进程因请求资源阻塞时，对已获得的资源保持不放
不剥夺条件: 进程已获得的资源，在末使用完之前，不能强行剥夺
循环等待条件: 若干进程之间形成一种头尾相接的循环等待资源关系

检查上面设计的程序并确定它是否满足所有四个条件：

printSum 函数确实需要 a 和 b 的独占权，因此它满足「互斥条件」
因为 printSum 持有 a 或 b 并且正在等待另一个，所以它满足「请求与保持条件」
没有提供任何方式让 goroutines 被抢占，满足「不剥夺条件」
printSum 的第一次调用正在等待 printSum 的第二次调用，反之亦然，即满足「循环等待条件」

显而易见，这是一个典型的死锁。

这些法则也使我们能够预防死锁。如果确保这些条件中至少有一个不成立，就可以防止死锁的发生。不幸的是，在实践中这些情况很难推断，因此也很难预防。

活锁

活锁是程序并发操作，但这些操作不能让程序向前推进。

举个例子。在狭窄的走廊里，遇到另一个人，他移到一边让你过去，但你也做了同样的事。所以你移动到另一边，但他也做了同样的事情。想象一下这种情况永远持续下去，就会理解什么是活锁。

用代码来演示下：

func livelockDemo() {
    cadence := sync.NewCond(&sync.Mutex{})
    go func() {
        for range time.Tick(1 * time.Millisecond) {
            cadence.Broadcast()
        }
    }()

    takeStep := func() {
        cadence.L.Lock()
        cadence.Wait()
        cadence.L.Unlock()
    }

    tryDir := func(dirName string, dir *int32, out *bytes.Buffer) bool {
        fmt.Fprintf(out, " %v", dirName)
        atomic.AddInt32(dir, 1)
        takeStep()

        if atomic.LoadInt32(dir) == 1 {
            fmt.Fprint(out, ". Success!")
            return true
        }

        takeStep()
        atomic.AddInt32(dir, -1)

        return false
    }

    var left, right int32
    tryLeft := func(out *bytes.Buffer) bool {
        return tryDir("left", &left, out)
    }

    tryRight := func(out *bytes.Buffer) bool {
        return tryDir("right", &right, out)
    }

    walk := func(walking *sync.WaitGroup, name string) {
        var out bytes.Buffer
        defer func() {
            fmt.Println(out.String())
        }()

        defer walking.Done()
        fmt.Fprintf(&out, "%v is trying to scoot:", name)
        for i := 0; i < 5; i++ { // 保证活锁代码一定能退出
            if tryLeft(&out) || tryRight(&out) { // 先尝试移动到左边，如果失败，尝试移动到右边
                return
            }
        }

        fmt.Fprintf(&out, "\n%v tosses her hands up in exasperation!", name)
    }

    var peopleInHallway sync.WaitGroup
    peopleInHallway.Add(2)
    go walk(&peopleInHallway, "Alice")
    go walk(&peopleInHallway, "Barbara")

    peopleInHallway.Wait()
}

上面代码演示活锁，每个人都必须以相同的速度或节奏移动。takeStep 模拟各方之间的恒定节奏。运行结果可能是这样的：

Alice is trying to scoot: left right left right left right left right left right
Alice tosses her hands up in exasperation!
Barbara is trying to scoot: left right left right left right left right left right
Barbara tosses her hands up in exasperation!

可以看到 Alice 和 Barbara 在最终放弃之前一直同向移动。

上述代码演示了活锁的一个非常常见的原因：两个或多个并发进程试图在没有协调的情况下防止死锁。如果走廊里的两个人达成一致，只有一个人移动，就不会有僵局。一个人站着不动，另一个人移到另一边，然后他们继续走。

活锁比死锁更难发现，因为程序看起来工作中。如果一个活锁程序正在机器上运行，并且你也查看了 CPU 利用率以确定它是否在做事情，根据活锁的不同，它甚至可能会发出其他信号，让你认为它在工作。然而一直以来，你的程序都在玩一场永恒的走廊移动游戏。

活锁是饥饿问题的一个子集，接下来看看饥饿。

饥饿

饥饿是并发程序无法获得执行所需的所有资源的情况。

当讨论活锁时，每个 goroutine 所缺乏的资源是共享资源（锁）。活锁需要与饥饿分开讨论，因为在活锁中，所有并发进程都同样处于饥饿状态，并且没有完成任何工作。更广泛地说，饥饿通常意味着有一个或多个贪婪的并发协程不公平地阻止一个或多个并发协程尽可能高效地完成工作，或者可能根本没有。

下面是个例子，包含一个「贪婪」的协程和「礼貌」的协程。

func starvationDemo() {
    var wg sync.WaitGroup
    var sharedLock sync.Mutex

    const runtime = 1 * time.Second

    greedyWorker := func() {
        defer wg.Done()
        var count int
        for begin := time.Now(); time.Since(begin) <= runtime; {
            sharedLock.Lock()
            time.Sleep(3 * time.Nanosecond)
            sharedLock.Unlock()
            count++
        }

        fmt.Printf("Greedy worker was able to execute %v work loops\n", count)
    }

    politeWorker := func() {
        defer wg.Done()
        var count int
        for begin := time.Now(); time.Since(begin) <= runtime; {
            sharedLock.Lock()
            time.Sleep(1 * time.Nanosecond)
            sharedLock.Unlock()
            sharedLock.Lock()
            time.Sleep(1 * time.Nanosecond)
            sharedLock.Unlock()
            sharedLock.Lock()
            time.Sleep(1 * time.Nanosecond)
            sharedLock.Unlock()
            count++
        }

        fmt.Printf("Polite worker was able to execute %v work loops.\n", count)
    }

    wg.Add(2)
    go greedyWorker()
    go politeWorker()
    wg.Wait()
}

运行上面 starvationDemo 代码得到的结果可能是这样的：

Greedy worker was able to execute 1431274 work loops
Polite worker was able to execute 550443 work loops.

贪婪的协程在整个循环中贪婪地持有共享锁，而有礼貌的协程仅在需要时持有共享锁。两个协程都做了相同数量的工作量（这里是睡眠 3 纳秒），结果是在相同的时间内，相比较于有礼貌的协程，贪婪协程完成了两倍多的工作量。

注意在这里用于识别饥饿的技术：度量。记录和采样指标是检测和解决饥饿问题的好方法之一。可以通过记录工作完成时间，然后确定工作速率是否符合预期来检测和解决饥饿问题。

饥饿状态可能会导致程序表现出低效或不正确的行为。前面的例子展示了低效，但如果有一个并发进程贪婪的以至于完全阻止另一个并发进程完成工作，则会遇到更大的问题。

还应考虑来自 Go 进程外部的饥饿情况。饥饿也可以适用于 CPU、内存、文件句柄、数据库连接等，任何必须共享的资源都有可能发生饥饿。

确定并发安全性

开发并发代码中最困难的地方，其实也是其他所有问题的根源：人。每行代码背后至少有一个人。

作为一个与现有代码打交道的开发者，如何利用并发写代码，如何安全地使用代码并不总是那么明确的，比如现有下面这个函数例子：

// CalculatePi 计算 π 从 begin 到 end 之间的数字
func CalculatePi(begin, end int64, pi *Pi)

这个例子可能会引发很多问题：

如何使用这个函数？
为了并发使用，否需要多次实例化这个函数?
传入 Pi 后，函数的所有的实例都在 Pi 上运行，需要内存访问同步吗？或者 Pi 类型是否做了这件事？

一个函数的使用已发上面这些问题，想象以下任何一个中等规模的程序，可能就会理解并发的复杂性了。

可以给上面的函数一些注释，比如是这样的：

// CalculatePi 计算 π 从 begin 到 end 之间的数字
// 在内部，CalculatePi 将并发创建 FLOOR((end-begin)/2)
// CalculatePi 会递归地调用自己
// Pi 的写入同步由 Pi 的结构体内部处理
func CalculatePi(begin, end int64, pi *Pi)

这样就会明白，使用这个函数不用担心并发和同步问题。这些注释解释了以下内容：

谁负责并发？
并发原语如何解决并发问题的？
谁负责内存访问同步？

当写一个公开的函数、方法或者变量时，如果问题上下文中涉及并发，为了其他同事和未来的自己考虑：宁可注释多一些，也应该涵盖这三个方面。

这个函数模糊地暗示了对他的模型理解是错误的。可以修改成纯函数，确保使用者不会做多余的工作。

还要考虑一下，也许这个函数中的歧义表明开发者对它的建模是错误的。也许应该改为纯函数确保函数没有副作用：

func CalculatePi(begin, end int64) []uint

这个函数的签名移出了可能带来同步的问题，但仍然可能有并发使用的问题。可以再次修改函数签名：

func CalculatePi(begin, end int64) <-chan uint

返回值是一个 channel，表明 CalculatePi 至少会启动一个协程。

这样修改的同时，也需要考虑性能，需要平衡代码明确性和性能。明确性很重要，尽可能地保证未来使用这些代码的人能正确使用它，性能重要性是显而易见的，这两者间不是互相排斥，但难以协调。

面对复杂的简单化

在计算机科学领域，并发编程是一个难点，但是需要了解一点：并发问题不是不可解决的。使用 Go 的并发原语（如 channel 原语为并发协程间的通信提供了可组合和安全的方式），能够安全地、清晰地写出并发代码。

首先讨论 Go 语言提供低延迟的 GC。语言里有 GC 是否是正确，经常会在开发者之间产生争论。Go 语言出色的 GC，大大减少了使用者对 GC 的细节关注。内存管理是计算机科学领域另一个难点。与并发结合时，写出正确的代码变得困难。如果对 GC 带来的暂停时间不敏感，那么用户不需要管理内存，写并发代码会更容易。