Go语言中的并发机制系列-1|并发简介

Posted by ShenHengheng on 2018-11-13

本系列阅读笔记是基于 Golang 经典图书 Concurrency in GO ,主要有6个章节:

  • An Introduction to Concurrency
  • Modeling Your Code: Communicating Sequential Processes
  • Go’s Concurrency Building Blocks
  • Concurrency Patterns in Go
  • Concurrency at Scale
  • Goroutines and the Go Runtime

本部分主要介绍第一章:An Introduction to Concurrency ,并发的基本概念,程序中的并发若要控制为什么难?以及有哪些难题?

大家都知道,程序中若要实现并发或者程序员们要写对并发代码是很难做正确的,通常需要几次迭代才能使并发代码按照预期工作。即便如此,有的支持并发的系统虽然已经非常成熟了,但是系统内部仍存在一些未被发现或者忽略的 bug。这就是为什么并发那么难搞的原因。

竞争条件(Race Condition)

当两个或多个操作必须以正确的顺序执行时会发生竞争条件,但是程序尚未写入以确保保持此顺序。

大多数情况下,我们遇见的是数据竞争,在所谓的数据竞争中,其中一个并发操作尝试读取某一变量,而在某个未确定的时间,另一个并发操作试图写入同一个变量。

下面是一个典型的例子

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

在 Go 语言中,我们在某个函数前使用 go 关键字,表明你要创建一个 goroutine。

这里,第3行和第5行都试图访问变量 data ,但无法保证执行的顺序。因此运行此代码有三种可能的结果:

  • 什么也不打印. 第 3 行 在 第 5 行 之前执行
  • 打印 the value is 0. 在这种情况下, 第 5 行和第 6 行在第 3 行之前执行。
  • 打印 the value is 1. 在这种情况下, 第 5 行在第 3 行之前执行,但第 3 行在第 6 行之前执行。

为什么会产生这种结果?往往是因为程序员在编写程序时,并未考虑程序所出现的所有可能结果或者并未考虑完整。

有时候在出现可能并发的时候,大家(包括我)可能都会第一时间想到:我给它 sleep 一下不就行了。但是,这是非常糟糕的想法。实际上,一些开发人员在整个代码中插入 sleep 的陷阱,它似乎解决了并发问题。现在让我们在前面的程序中尝试:

var data int
go func() { data++ }()
time.Sleep(1*time.Second) // This is bad!
if data == 0 {
    fmt.Printf("the value is %v.\n" data)
}

解决数据竞争了吗?没有。事实上,上面出现的三个结果仍然可能发生,并且更不加确定是哪一个结果了!我们在调用我们的goroutine和检查变量值之间睡得越久,我们的程序越接近实现正确性,这种概率渐近地接近逻辑正确性;但它永远不会在逻辑上正确。除此之外,我们算法的效率越来越低。现在必须 sleep 一秒钟才能让我们更有可能看不到我们的数据竞争。如果我们使用了正确的方法,我们可能根本不必等待,或者等待可能只有一微秒。 结论:将 sleep 引入代码可以是调试并发程序的一种快捷方法,但它们不是解决方案!

原子性

当某些东西被认为是 原子 的,或具有原子属性时,这意味着在它运行的上下文中,它是不可分割的或不可中断的。

那么这究竟是什么意思,为什么在使用并发代码时知道这一点很重要?第一件非常重要的事情是“上下文”这个词。在某种情况下,某些东西可能是原子的,而不是另一种。在程序流程上下文中是原子的操作但在操作系统的上下文中可能不是原子的;在操作系统的上下文中是原子的操作但在您的机器的上下文中可能不是原子的;并且在您的机器上下文中是原子的操作但在您的应用程序的上下文中可能不是原子的。换句话说,操作的原子性可以根据当前定义的范围而改变。这个事实既可以支持也可以反对你!

在考虑原子性时,通常需要做的第一件事就是定义上下文或范围,操作将被认为是原子的。一切都从此开始。

“不可分割”“不间断” 这两个术语。这些术语意味着在你定义的上下文中,程序要不然完全执行,要不然完全不执行。下面看个例子:

 i++

这是一个非常简单的例子,几乎所有学过程序语言设计的同学都知道他是什么意思,但它很容易证明原子性的概念。它可能看起来像原子,但简短的分析揭示了几个操作:

  • 访问变量 i 的值.
  • 将变量 i 加 1.
  • 将加 1 之后i储存在变量i中.

虽然这些操作中的每一个都是原子的,但三者的组合可能不是,具体取决于您的上下文。这揭示了原子操作的一个有趣特性:组合它们不一定产生更大的原子操作。使操作原子化取决于您希望它在哪个上下文中是原子的。如果您的上下文是没有并发进程的程序,则此代码在该上下文中是原子的。如果你的上下文是一个不会将我暴露给其他goroutine的goroutine,那么这段代码就是原子的。

那我们为什么要关心呢?原子性很重要,因为如果某些东西是原子的,那么隐含地它在并发上下文中是安全的。这使我们能够编写逻辑上正确的程序,并且 - 我们稍后会看到 - 甚至可以作为优化并发程序的一种方法。

同步访问内存

假设我们有一个数据竞争:两个并发进程正在尝试访问相同的内存区域,并且它们访问内存的方式不是原子的。我们之前的简单数据竞争示例将通过一些修改很好地完成:

var data int
go func() { data++}()
if data == 0 {
    fmt.Println("the value is 0.")
} else {
    fmt.Printf("the value is %v.\n", data)
}

在这里添加了一个 else 子句,这样无论数据的值如何,我们总会获得一些输出。请记住,在编写存在数据竞争的程序时,输出将完全不确定。

实际上,程序中需要对共享资源进行独占访问的代码被称作 “临界区”。这被称为关键部分。在这个例子中,我们有三个临界区:

  • goroutine,开启一个 goroutine
  • if 语句, 检查变量的值是否为0.
  • fmt.Printf 语句,格式化打印我们的数据.

为了保证能够互斥访问,我们需要保护这些 “临界区” 代码,在 Golang 中是如何保护的呢?看下面的代码:

var memoryAccess sync.Mutex
var value int
go func() {
    memoryAccess.Lock()
    value++
    memoryAccess.Unlock()
}()
memoryAccess.Lock()
if value == 0 {
    fmt.Printf("the value is %v.\n", value)
} else {
    fmt.Printf("the value is %v.\n", value)
}
memoryAccess.Unlock()

无论何时开发人员想要访问数据变量的内存 (shared),他们必须首先调用Lock,当访问完成后,他们必须调用Unlock退出该临界区。这两个语句之间的代码可以认为它具有对数据的独占访问权。

死锁,活锁和饥饿

前面几节都讨论了程序的正确性,如果这些问题得到正确管理,你的程序永远不会给出错误的答案。不幸的是,即使您成功处理了这些类问题,还有另一类需要解决的问题:死锁,活锁和饥饿。这些问题都与确保您的计划始终有用的事情有关。如果处理不当,您的程序可能会进入一个完全停止运行的状态。

死锁

我们先看一段程序。

type value struct {
    mu sync.Mutex
    value int
}
var wg sync.WaitGroup
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()
  • 第 8 行,进入临界区.
  • 第 9 行,这里使用 defer 语句在 printSum 返回之前退出临界区。
  • 第 10 行, 我们 sleep 了一段时间来模拟工作(并触发死锁)。

运行结果:

fatal error: all goroutines are asleep - deadlock!

Figure 1. Demonstration of a timing issue giving rise to a deadlock

Figure 1. Demonstration of a timing issue giving rise to a deadlock

解释:我们第一次调用 printSum 锁定 a 然后尝试锁定 b,但与此同时我们对 printSum 的第二次调用已锁定 b 并试图锁定 a。两个 goroutine 彼此无限等待。

当且仅当以下所有条件同时存在于系统中时,才会出现资源上的死锁情况, 下面是产生死锁的四个必要条件1

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

这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。

Figure 2. 死锁的产生。两个进程都需要资源来继续执行。P1需要额外的资源R1并且拥有资源R2,P2需要额外的资源R2并且拥有R1;两个过程都不能继续

Figure 2. 死锁的产生。两个进程都需要资源来继续执行。P1需要额外的资源R1并且拥有资源R2,P2需要额外的资源R2并且拥有R1;两个过程都不能继续

让我们检查一下我们设计的程序,并确定它是否满足所有四个条件:

  1. printSum 函数确实需要a和b的独占访问权,因此它满足这个条件。
  2. 因为 printSum 函数持有 ab 并且正在等待另一个,所以它满足这个条件。
  3. 我们没有任何办法让我们的 goroutines 被抢先一步。
  4. 我们第一次调用 printSum 正在等待第二次调用,反之亦然。

活锁

活锁指的是任务或者执行者没有被阻塞,由于某些条件没有满足,导致一直重复尝试—失败—尝试—失败的过程。处于活锁的实体是在不断的改变状态,活锁有可能自行解开。

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.

wiki https://en.wikipedia.org/wiki/Deadlock/#Livelock

你有没有走过走廊走向另一个人?她移到一边让你通过,但你刚刚完成了同样的事情。所以你转移到另一边,但她也做了同样的事情。导致你们两个无法向前走。这种情景就是“程序”出现了“活锁”. 我们将通过下面这个例子来模拟上面这个场景。

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

程序解释

  • tryDir 允许一个人尝试向一个方向移动并返回移动是否成功,每个方向都表示为试图朝那个方向移动的人数,dir。
  • 第 14 行,首先,我们打算通过将该方向增加 1 来朝着一个方向前进。
  • 第 15 行,为了演示活锁,每个人必须以相同的速度移动。takeStep 模拟各方之间的常量的僵持。
  • 第 17 行,在这里,这个人意识到他们不能走向这个方向而放弃。我们通过将该方向减1来表明这一点。
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()

程序的输出:

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!

饥饿

饥饿指的进程无法访问到它需要的资源而不能继续执行时,引发饥饿最常见资源就是CPU时钟周期。

当我们讨论活锁时,每个goroutine缺乏的资源都是共享锁。活锁和饥饿是不同的概念,因为在活锁中,所有并发进程都是平等的,并且没有完成任何工作。更广泛地说,饥饿通常意味着存在一个或多个贪婪并发进程,这些进程持续占有共享资源而不公平地阻止一个或多个并发进程完成工作。

下面这段程序模拟饥饿的发生,通过创建两个 goroutine greedyWorkerpoliteWorker.

greedyWorker 贪婪地独占整个工作循环的共享锁,而 politeWorker 只在需要时尝试占有。两个 worker都进行相同数量的模拟工作(睡眠时间为3纳秒),但正如你在相同的时间内看到的那样,贪婪的工人几乎完成了两倍的工作量!

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

如果我们假设两个 worker 都具有相同大小的临界区,而不是认为 greedyWorker 的算法更有效(或者加锁和解锁的开销很大 ),我们得出的结论是,greedyWorker 不必要地扩大了对其临界区之外的共享锁的控制,并通过饥饿阻止了 politeWorker 的 goroutine 有效地执行工作。

我们还应该考虑饥饿来自 Go进程 之外的情况。请记住,饥饿也可以应用于CPU,内存,文件句柄,数据库连接:任何必须共享的资源都是饥饿的候选者!

总结

本部分主要介绍了并发中的基本概念,引入了 Golang 语言中有关解决并发问题的一些方法,但没有深入讲解,接下来的几个教程中重点剖析 Golang 语言有关并发的 API。