9、协程

1、并发与并行

并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。
并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

2、Coroutine

Coroutine（协程）是一种用户态的轻量级线程，特点如下：
A、轻量级线程
B、非抢占式多任务处理，由协程主动交出控制权。
C、编译器/解释器/虚拟机层面的任务
D、多个协程可能在一个或多个线程上运行。
E、子程序是协程的一个特例。
不同语言对协程的支持：
A、C++通过Boost.Coroutine实现对协程的支持
B、Java不支持
C、Python通过yield关键字实现协程，Python3.5开始使用async def对原生协程的支持

3、goroutine

Go语言并发的基础是goroutine和channel，当然Go也提供了传统的对共享资源加锁的方式实现并发：原子函数（atomic函数-类似Java 中的AtomicInteger）和互斥锁（mutex-类似java中的Lock）。

goroutine奉行通过通信共享内存，而不是共享内存来通信

这里主要讲下goroutine和channel

goroutinue使用示例

示例1:使用关键字go来定义并启动一个goroutine:

func loop() {
    for i := 0; i < 10; i++ {
        fmt.Printf("%d ", i)
    }
}
func main() {
    go loop()
    loop()
    time.Sleep(time.Second) // 停顿一秒
}

示例二：信号量方式

package main
import (
   "fmt"
   "sync"
)
func main(){
   var wg sync.WaitGroup
   wg.Add(2)
   go func() {
      defer wg.Done()
      for i := 0; i < 10000; i++ {
         fmt.Printf("Hello,Go.This is %d\n", i)
      }
   }()
   go func() {
      defer wg.Done()
      for i := 0; i < 10000; i++ {
         fmt.Printf("Hello,World.This is %d\n", i)
      }
   }()
   wg.Wait()
}

sync.WaitGroup是一个计数的信号量，类似java中的CountDownLatch。使main函数所在主线程等待两个goroutine执行完成后再结束，否则两个goroutine还在运行时，主线程已经结束。
sync.WaitGroup使用非常简单，使用Add方法设设置计数器为2，每一个goroutine的函数执行完后，调用Done方法减1。Wait方法表示如果计数器大于0，就会阻塞，main函数会一直等待2个goroutine完成再结束。

示例三：使用通道channel在并发过程中实现通信

package main

import (
   "fmt"
)

func main() {
   ch := make(chan int)
   go func() {
      var sum int = 0
      for i := 0; i < 10; i++ {
         sum += i
      }
      //发送数据到通道
      ch <- sum
   }()
   //从通道接收数据
   fmt.Println(<-ch)
}

在计算sum和的goroutine没有执行完，将值赋发送到ch通道前，fmt.Println(<-ch)会一直阻塞等待，main函数所在的主goroutine就不会终止，只有当计算和的goroutine完成后，并且发送到ch通道的操作准备好后，main函数的<-ch会接收计算好的值，然后打印出来

概念

进程：一个程序对应一个独立程序空间
线程：一个执行空间，一个进程可以有多个线程
逻辑处理器：执行创建的goroutine，绑定一个线程
调度器：Go运行时中的，分配goroutine给不同的逻辑处理器
全局运行队列(global runqueue)：所有刚创建的goroutine队列
本地运行队列：逻辑处理器的goroutine队列

goroutine调度原理图.png

可以在程序开头使用runtime.GOMAXPROCS(n)设置逻辑处理器的数量。
如果需要设置逻辑处理器的数量，一般采用如下代码设置：
runtime.GOMAXPROCS(runtime.NumCPU())
调度器对可以创建的逻辑处理器的数量没有限制，但语言运行时默认限制每个程序最多创建10000个线程。

goroutine vs thread

1、内存占用
goroutine并不需要太多太多的内存占用，初始只需2kB的栈空间即可(自Go 1.4起)，按照需要可以增长。一般来说一个Goroutine成本在 4 — 4.5 KB,在go程序中，一次创建十万左右的goroutine很容易（4KB*100,000=400MB）。

线程初始1MB，并且会分配一个防护页(guard page)。在64位Linux系统,max user process限制线程数量：（可通过ulimit –a查看，默认值1024，通过ulimit –u可以修改此值）。
在使用Java开发服务器的过程中经常会遇到request per thread的问题，如果为每个请求都分配一个线程的话，大并发的情况下服务器很快就死掉，因为内存不够了，所以很多Java框架比如Netty都会使用线程池来处理请求，而不会让线程任意增长。
而使用goroutine则没有这个问题，你页可以看到官方的net/http库就是使用request per goroutine这种模式进行处理的，内存占用不会是问题。
2、上下文切换
从调度上看，goroutine的调度开销远远小于线程调度开销。
OS的线程由OS内核调度，每隔几毫秒，一个硬件时钟中断发到CPU，CPU调用一个调度器内核函数。这个函数暂停当前正在运行的线程，把他的寄存器信息保存到内存中，查看线程列表并决定接下来运行哪一个线程，再从内存中恢复线程的注册表信息，最后继续执行选中的线程。这种线程切换需要一个完整的上下文切换：即保存一个线程的状态到内存，再恢复另外一个线程的状态，最后更新调度器的数据结构。某种意义上，这种操作还是很慢的。

Go运行的时候包涵一个自己的调度器，这个调度器使用一个称为一个M:N调度技术，m个goroutine到n个os线程（可以用GOMAXPROCS来控制n的数量），Go的调度器不是由硬件时钟来定期触发的，而是由特定的go语言结构来触发的，他不需要切换到内核语境，所以调度一个goroutine比调度一个线程的成本低很多。

当线程阻塞时，其它的线程进可能被执行，这叫做线程的切换。切换的时候，调度器需要保存当前阻塞的线程的状态，恢复要执行的线程状态，包括所有的寄存器，16个通用寄存器、程序计数器、栈指针、段寄存器、16个XMM寄存器、FP协处理器、16个 AVX寄存器、所有的MSR等等。
goroutine的保存和恢复只需要三个寄存器：程序计数器、栈指针和DX寄存器。因为goroutine之间共享堆空间，不共享栈空间，所以只需把goroutine的栈指针和程序执行到那里的信息保存和恢复即可，花费很低。

其实， goroutine 用到的就是线程池的技术，当 goroutine 需要执行时，会从 thread pool 中选出一个可用的 M 或者新建一个 M。而 thread pool 中如何选取线程，扩建线程，回收线程，Go Scheduler 进行了封装，对程序透明，只管调用就行，从而简化了 thread pool 的使用。

Go调度器

Go的调度器内部有三个重要的结构：M，P， G
M:
代表真正的内核OS线程，和POSIX里的thread差不多
P:
代表调度的上下文(逻辑处理器），可以把它看做一个局部的调度器，使go代码在一个线程上跑，它是实现从N:1到N:M映射的关键。
M必须拿到P才能对G进行调度，P限定了go调度goroutine的最大并发度。每一个运行的M都必须绑定一个P。
G:
代表一个goroutine，它有自己的栈，instruction pointer和其他信息（正在等待的channel等等），用于调度。

Go调度器.png

调度方式：Goroutine 在 system call 和 channel call 时都可能发生阻塞，但这两种阻塞发生后，处理方式又不一样的。

系统调用时

当程序发生阻塞的 system call（如打开一个文件）时，P可以转而投奔另一个OS线程。

系统调用时处理方式.png

图中看到，当一个OS线程M0陷入阻塞时，P转而在OS线程M1上运行。调度器保证有足够的线程来运行所以的context P。
图中的M1可能是被创建，或者从线程缓存中取出。当MO返回时，它必须尝试取得一个context P来运行goroutine，一般情况下，它会从其他的OS线程那里steal偷一个context过来，如果没有偷到的话，它就把goroutine放在一个global runqueue里，然后自己就去睡大觉了（放入线程缓存里）。Contexts们也会周期性的检查global runqueue，否则global runqueue上的goroutine永远无法执行。

网络IO调用时

当goroutine需要做一个网络IO调用时，G会和P分离，并移到集成了网络轮询器的运行时，一旦该轮询器指示某个网络读或者写操作已经就绪，对应的goroutine就会重新分配到P上完成操作。

channel call时

当程序发起一个 channel call时，G会和P分离，G 的状态会设置为 waiting，M 继续执行其他的 G。当 G 的调用完成，会有一个可用的 M 继续执行它。

任务窃取

另一种情况是P所分配的任务G很快就执行完了（分配不均），这就导致了一个上下文P闲着没事儿干而系统却任然忙碌。

任务窃取.png

但是如果global runqueue没有任务G了，那么P就不得不从其他的上下文P那里拿一些G来执行。一般来说，如果上下文P从其他的上下文P那里要偷一个任务的话，一般就‘偷’run queue的一半，这就确保了每个OS线程都能充分的使用。

参考：

golang语言并发与并行——goroutine和channel的详细理解（一） - Go语言中文网 - Golang中文社区
Go语言开发（九）、Go语言并发编程-生命不息，奋斗不止-51CTO博客

Golang 的 goroutine 是如何实现的？ - 知乎
Goroutine 浅析
深入Go语言 - 8 goroutine_it知识共享