1. 并发概述

1.1 竞争

当两个或多个操作必须按正确的顺序执行，而程序未保证这个顺序，将会发生竞争。

例如：

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

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

上述代码中，go func()和main()都尝试访问变量data，但是不能保证以确定的顺序访问，肯能会出现三种结果：

1. 不打印任何数据；data++在if data == 0之前执行
2. 打印the value is 0，if data == 0和打印语句在data++之前
3. 打印the value is 1，if data == 0在data++之前，但是打印语句在data++之后

这为代码的运行带来了非常大的不确定性。

1.2 原子性

原子性表示一个操作在其运行的环境中是不可分割的或不可中断的。

判断一个事物是否是原子性的，一定要根据其运行的环境（或上下文Context）来判断，相同的事物在不同的环境中不一定都是原子性的。

1.3 临界区

在上述的代码示例中，两个并发的协程(go开启的协程和main协程)试图访问相同的内存区域(data)，并且访问的操作不是原子性的，这样的情况带来了竞争。

访问共享数据的代码被称为临界区。例如上例的代码中临界区有三个：

• data++
• if data == 0
• fmt.Printf("the value is %d\n", data)

1.4 死锁、活锁和饥饿

死锁(deadlock)

死锁程序是所有并发进程都在彼此等待的程序。

例如：

func deadLock() {
	type val struct {
		mu sync.Mutex
		v  int
	}

	var wg sync.WaitGroup
	printSum := func(v1, v2 *val) {
		defer wg.Done()
		v1.mu.Lock()
		defer v1.mu.Unlock()

		time.Sleep(2 * time.Second) // 尽可能让死锁发生的概率提高，因为无法保证 goroutine 的执行顺序

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

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

	var a, b val
	wg.Add(2)
	go printSum(&a, &b) // 锁定 a, 等待 b
	go printSum(&b, &a) // 锁定 b, 等待 a
	wg.Wait()
}

上述代码中，两个协程分别锁定了对方想要获得的资源，造成了死锁。（使用sleep的原因是因为无法保证goroutine的执行顺序）

死锁的条件

死锁的条件(coffman条件)，有四个：

1. 相互排斥，并发进程同时拥有资源独占权
2. 等待条件，并发进程必须同时拥有一个资源，并等待额外的资源
3. 没有抢占，并发进程拥有的资源只能被该进程释放
4. 循环等待，并发进程间相互等待

活锁(livelock)

活锁程序是正在主动执行并发操作的程序，但是这些操作无法向前推进程序的状态。

一个现实的例子：走廊中相向而行的两个人，相遇之后，其中一个选择走向另一边把路让出来，而另一个人也是这么想的，此时就形成了活锁。两个程序一直在运行，但是没有任何的进展。

以下程序模拟上述过程：

package ch01

import (
	"bytes"
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

func livelock() {
	cadence := sync.NewCond(&sync.Mutex{})
	go func() {
		for range time.Tick(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.Fprintf(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 tring to scoot:", name)
		for i := 0; i < 5; i++ {
			if tryLeft(&out) || tryRight(&out) {
				return
			}
		}
		fmt.Fprintf(&out, "\n%v tosses her hand up in exasperation!", name)
	}

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

}

输出：

Alice is tring to scoot: left right left right left right left right left right
Alice tosses her hand up in exasperation!
Barbara is tring to scoot: left right left right left right left right left right
Barbara tosses her hand up in exasperation!

由输出可以看到，在程序强制（设定了最高尝试次数）退出前，两个协程会持续的进行竞争，并且程序毫无进展。

饥饿(starvation)

饥饿指的是在任何情况下，并发进程都无法获取工作所需的全部资源。

饥饿发生时，通常意味着有一个或多个贪婪进程在不公平的阻止其他进程获取资源，以尽可能的有效完成工作。

下例中，创建了一个贪婪的goroutine和一个平和的goroutine：

func starvation() {
	const runtime = time.Second
	var wg sync.WaitGroup
	var sharedLock sync.Mutex

	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()
}

Greedy worker was able to execute 33 work loops
Polite worker was able to execute 12 work loops

可以看出，做同样的工作(3ns)，在相同的时间内，贪婪的协程的进行的工作量是平和协程的两倍多。

因为贪婪协程不必要的扩大了临界区，并且导致平和协程无法获取所有的共享资源，导致了饥饿问题。

Reference

1. Go 语言并发之道
2. https://en.wikipedia.org/wiki/Critical_section
3. https://en.wikipedia.org/wiki/Deadlock#Livelock