前言：用来记录Go的语言特性，主要参考为B站《幼麟实验室》及《深度探索Go语言》。

一、基础知识

1.1 数据结构

1.1.1 String

编码：定长编码非常浪费内存，所以采用变长编码。**那么怎么划分边界呢？**最高几位空出来作为标识位，标记该字符占用几个字节。

这是 Go 默认的编码方式：UTF-8 编码：

==string的结构：==

• 一个起始地址：用来标记字符串起始位置；但是怎么找到结尾呢？C 是在字符串结尾处放个\0，但这限制了内容不能出现这个字符，所以 Go 并不这样做；
• 一个字符串长度：用来标记该字符有多长(字节个数，而不是字符个数！)，这样就能够找到字符串在哪结束了。

Go 的字符串内容不能修改，所以 Go 的编译器会把定义好的字符串内容分配到只读内存段。可以通过[]byte()将字符串转换为字节slice，这样会为slice变量重新分配一段内存，并拷贝之前字符串的内容，可脱离只读内存的限制。

问：rune 和 byte 的区别？

本质区别就是：

1
2

type byte = uint8
type rune = int32

• rune 等同于 int32，即4个字节长度，常用来处理 unicode 或 utf-8 字符。比如用来处理中文字符。
• byte 等同于 uint8，即一个字节长度，常用来处理 ascii 字符(共128个)。

在go中修改字符串，需要先将字符串转化成数组，[]byte 或 []rune，然后再转换成 string 型。

1
2
3
4
5
6
7
8
9

str := "你好 world"
// str[i] 其实是 byte
for i := 0; i < len(str); i++ {
    fmt.Printf("%c", str[i]) // ä½&nbsp;好 world
}
// 使用range，其实是使用rune类型来编码的，rune类型用来表示utf8字符，一个rune字符由一个或多个byte组成。
for _, value := range str {
    fmt.Printf("%c", value) // 你好 world
}

1.1.2 Slice

1.1.2.1 数据结构

Slice 有三个部分：

• 元素存哪里(data)
• 存了多少个元素(len)
• 可以存多少个元素(cap)

例如：

• 若通过var ints []int或new创建数组，data是该数组的起始地址，但初始化为nil，len=0，cap=0，因为不会开辟底层内存给它；

• 若通过make([]int, 2, 5)创建数组，不仅会分配上述三部分，还会开辟一段内存作为它的底层数组；

1.1.2.2 append

append可以为没有底层内存空间的Slice开辟一段内存，并赋值。

可以把不同的Slice关联到同一个数组，它们会共用底层数组，例如：

这三个Slice访问和修改的都是同一个底层数组，s1和s2若访问超过其len的元素，会产生访问越界。

上图中，若再给s2添加元素会怎样？这个底层数组是不能用了，得开辟新数组，原来的元素要拷贝过去，还要添加新元素，此时s2就不指向原底层数组了：

1.1.2.3 ==扩容规则==

当使用append添加元素，容量不够时，该怎么重新分配容量呢？

1. 预估扩容后的容量：

   预估规则：

   • oldLen*2 < cap：旧容量*2 还是小于最少要分配的容量，那么就分配最少要分配的容量，此处为5；
   • 否则：oldLen < 1024时，直接 *2，oldLen >= 1024时，就先扩 1/4。
   

2. **预估元素需要占用多大内存：**直接分配 预估容量 * 元素类型大小 内存可以嘛？不可以的！因为不一定有刚好一样大的预置规格的内存块。这就是第三步要做的事。

3. 匹配到合适的内存规格：之前例子中，预估容量为 5，64位下就需要申请 40 字节内存，而最接近的内存规格为 48 字节。也就是能装 6 个该元素，所以 扩容后容量为 6。

4. 分配完新的底层 Array 空间后，就把原 Array 中的数据拷贝到新的上面。

问：Slice 和 Array 有啥区别？

• 1 2	arr := [2]int{1, 2} // 声明了一个数组 sli := []int{1, 2} // 声明了一个Slice

• Array 长度是固定的；Slice 是动态数组，长度可变；

• Slice 是在 Array 基础上实现的，Slice有仨字段，首个就是对底层 Array 的引用，所以 Slice 是引用型。

在 C 语言中，数组变量是指向第一个元素的指针，但是 Go 语言中并不是。

由于值传递，数组进行赋值、传递时，实际上会复制整个数组：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

a := [...]int{1, 2, 3} 	// ... 会自动计算数组长度
b := a					// 值拷贝，复制整个数组
a[0] = 100
fmt.Println(a, b) 		// [100 2 3] [1 2 3]

// 为了避免复制数组，一般会传递指向数组的指针。
a := [...]int{1, 2, 3}
b := &a
(*b)[0] = 100
fmt.Println(a, *b)		// [100 2 3] [100 2 3]

问：Slice 的性能陷阱？

1. 大量内存得不到释放

在已有切片的基础上进行切片，不会创建新的底层数组。因为原来的底层数组没有发生变化，内存会一直占用，直到没有变量引用该数组。因此很可能出现这么一种情况，原切片由大量的元素构成，但是我们在原切片的基础上切片，虽然只使用了很小一段，但底层数组在内存中仍然占据了大量空间，得不到释放。比较推荐的做法，使用 copy 替代 re-slice。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 1. 无法释放 origin，造成内存浪费
func lastNumsBySlice(origin []int) []int {
	return origin[len(origin)-2:]
}

// 2. 自动回收 origin，节省内存
func lastNumsByCopy(origin []int) []int {
	result := make([]int, 2)
	copy(result, origin[len(origin)-2:])
	return result
}

1.1.3 结构体与内存对齐

太强了，看视频吧去。拨云见日，茅塞顿开！

1.1.3.1 访问内存

CPU是将内存地址通过地址总线传输给内存，内存准备好数据后通过数据总线传给CPU：

若想一次读取 8字节 的数据，就需要64位数据总线，这里的数据总线位数就是机器字长。如何能只传输一个地址，读取 8字节 数据呢？

为了更高的访问效率，内存布局如下：就是8个chip排列在一起(每个chip由8个bank组成，即 1字节 内存)，共用同一个内存地址，各自寻找 1字节，然后组合起来成为 8字节：

所以每次访问内存都只能从起始地址%8==0处开始访问。

1.1.3.2 内存对齐

为了提高访问效率(保证一次读取)，编译器会把各种类型的数据安排到合适的地址，并占用合适的长度。

内存对齐要求数据存储起始地址，及占用的字节数都要是它对齐边界的倍数：

1.1.3.3 结构体对齐

共两个条件：

• 各成员要对齐边界；
• 结构体总内存大小 % 对齐边界 == 0。

可以看出，结构体各字段的顺序会影响结构体占用内存的大小。

==为什么要有结构体总内存大小 % 对齐边界 == 0？==

如下情况，若不是整数倍的话，只有第一个T的内存是对齐的，第2个T就没有对齐。

问：什么是内存对齐？

答：为了提高访问效率，编译器会把各种类型的数据安排到合适的地址，并占用合适的长度。内存对齐要求数据存储起始地址，及占用的字节数都要是它**==对其边界==的倍数**。

问：如何确定数据类型的对齐边界？

机器字长是最大对齐边界，而数据类型的对齐边界是：min(类型大小, 最大对齐边界)。

==为什么不统一按照最大对齐边界或类型大小分配呢？==

为了减少浪费，提高性能。

如果是int8类型，只占 1字节，若对齐到最大边界，就会浪费 7字节，所以对齐到 1字节 最合适；

如果是int64类型，占用 8字节，若对齐到 8字节，如下情况中就会浪费前面的 6字节，所以对齐到最大对齐边界最合适。

如果是结构体类型，对齐边界就是包含类型中最大的对齐边界。

问：为什么要内存对齐？

有些CPU能访问任意地址，是因为做了处理：比如读1-8的内存：会先读0-7，只取1-7，再读8-15，只取8，组合起来就是1-8，但是这样会降低访问效率。为了避免这样读取，因此要内存对齐。

1.1.4 Map

1.1.4.1 概述

Map主要由哈希函数和桶组成。

• 哈希函数用来实现key-value的映射，是决定哈希表的读写性能的关键，哈希函数映射的结果一定要尽可能均匀。如果使用结果分布较为均匀的哈希函数，那么哈希的增删改查的时间复杂度为 O(1)；但是如果哈希函数的结果分布不均匀，那么所有操作的时间复杂度可能会达到 O(n)。

• 桶用来解决哈希映射的冲突问题，常见方法有：开放寻址法和拉链法。

==Point 1：==

因为哈希之后的地址空间通常远大于实际地址空间，因此需要对哈希值进行处理，常用有两种方法：

• 取模法：hash % m；
• 与运算(Go采用)：hash & (m-1)。这里m必须是2的整数次幂，这样可以确保不会出现空桶。

==Point 2：==

上述对哈希值的操作会造成哈希冲突，因此需要对哈希冲突进行处理，常用有两种方法，如图所示：

• 开放寻址法：
  • 写入：对当前元素进行哈希映射得到地址，若该地址空闲，可以直接填入；若已被占用，则需要将当前元素分配在该地址后的空闲地址；
  • **读取：**若映射地址中存储元素的Key与当前元素的Key不同，则需要遍历该地址之后的地址空间，直到地址为空或找到目标Key。
• 拉链法（最常用）：
  • 写入：对当前元素进行哈希映射得到地址，若该地址空闲，可以直接填入；若已被占用，则需要在链表的末尾追加新的键值对；
  • **读取：**遍历映射地址的键值对链表，直到搜索到相同的Key(存在)或链表末尾(不存在)。

1.1.4.2 数据结构

runtime.hmap 是最核心的结构体：

 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

type hmap struct {
	count     int		// 记录 已存储键值对的数目
	flags     uint8		
    B         uint8		// 记录 桶(buckets)的数目是2的多少次幂
	noverflow uint16	// 记录 使用的溢出桶的数目
	hash0     uint32	// 哈希的种子，为哈希函数的结果引入随机性

	buckets    unsafe.Pointer	// 记录 桶的位置
    oldbuckets unsafe.Pointer	// 记录 扩容阶段旧桶的位置，大小是当前 buckets 的一半
	nevacuate  uintptr			// 记录 扩容阶段旧桶迁移进度：下一个要进行迁移的旧桶编号

	extra *mapextra				// 记录 溢出桶相关信息
}

// 记录溢出桶相关信息
type mapextra struct {
	overflow    *[]*bmap		// 记录 目前已被使用的溢出桶的地址
	oldoverflow *[]*bmap		// 记录 扩容阶段旧桶使用到的溢出桶的地址
	nextOverflow *bmap			// 下一个空闲溢出桶
}

type bmap struct {
    topbits  [8]uint8		// 每个topbit都是对应hash值的高8位，索引
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr		// 溢出桶，布局与常规bmap相同，是为了减少扩容次数
}

Go语言中，Map类型的变量本质上是一个指向hmap结构体的指针。

使用的桶的数据结构为bmap结构，每一个bmap都能存储8个键值对，当哈希表中存储的数据过多，单个桶已经装满时就会使用 extra.nextOverflow 中的桶存储溢出的数据。随着哈希表存储的数据逐渐增多，我们会扩容哈希表或者使用更多溢出桶存储溢出的数据。

1.1.4.3 初始化

==字面量：==

Go语言中通过key: value的方法表示键值对，可以通过如下方式初始化：

1
2
3
4
5

hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}

• 当**哈希表中的元素数量 <= 25 **时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

1
2
3
4

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

• 当**哈希表中的元素数量 > 25 **时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

1
2
3
4
5
6

hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

==运行时：==

根据传入的B来确定需要创建的桶的数量：

• 若桶的数量 < 2^4，此时认为数据量较小，使用溢出桶的概率较低，因此不创建溢出桶；
• 若桶的数量 > 2^4，会额外创建2^(B-4)个溢出桶。

**注意：**正常桶和溢出桶在内存中的存储空间是连续的。

1.1.4.4 读写操作

==访问：==

共有两种访问方式：

1
2

v     := hash[key] // => v     := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)

赋值语句左侧接受参数的个数会决定使用的运行时方法：

• 当接受一个参数时，会使用 runtime.mapaccess1，该函数仅会返回一个指向目标值的指针（感觉这里的指针并不是一个地址，感觉还是目标值）；
• 当接受两个参数时，会使用 runtime.mapaccess2，除了返回目标值之外，它还会返回一个用于表示当前键对应的值是否存在的 bool 值。

查找过程⭐：哈希会依次遍历正常桶和溢出桶中的数据，它会先比较哈希的高 8 位和桶中存储的 tophash(==减少key的对比次数，缩小查找成本==)，后比较传入的和桶中的key(==因此key需要是可比较类型==)以加速数据的读写。

每一个桶都是一整片的内存空间，当发现桶中的 tophash 与传入键的 tophash 匹配之后，我们会通过指针和偏移量获取哈希中存储的键 keys[x] 并与 key 比较，如果两者相同就会获取目标值的指针 values[x] 并返回。

==写入：==

首先会根据传入的key拿到对应的哈希和桶，然后通过遍历比较桶中存储的 tophash 和key的哈希，

• 如果当前键值对在哈希中存在，那么就会直接返回目标区域的内存地址；
• 如果当前键值对在哈希中不存在，哈希会为新键值对规划存储的内存地址并存入。

1.1.4.5 ⭐扩容

除了用散列均匀的哈希函数来提高读写性能，还可以通过对地址空间适时扩容减少哈希冲突以提高性能。

负载因子：count/(2^B)，即存储键值对的数目/桶的数目，用来判断是否需要进行扩容。不难理解，装载因子越大，哈希的读写性能就越差。

扩容规则：

• count/(2^B) > 6.5 –> 翻倍扩容(hamp.B++)；
• 使用了"过多"的溢出桶 -> 等量扩容。

注：“过多” 指：

1. `B <= 15`时，`noverflow >= 2^B`；
1. `B > 15`时，`noverflow >= 2^15`。

**翻倍扩容：**会创建旧桶数目2倍的新桶，然后将旧桶中的键值对分流到对应的两个新桶中，b = hash(key) & (2^B-1)，(这个地方很有意思)。

等量扩容：所谓等量扩容就是创建和旧桶数目一样多的新桶，然后把原来的键值对迁移到新桶中。**这里有一个问题：**既然是等量的，那何必扩容呢？

**答：**当发生大规模删除操作时，旧桶中存放的键值对可能非常稀疏，因此为了紧凑内存，需要将这些键值对重新排列到新桶中。

==Point 3==

扩容时，需要把旧桶中的数据迁移到新桶，但并不需要一次性迁移完。

渐进式扩容：把键值对迁移的时间分摊到多次哈希表操作中，可以避免瞬时的性能抖动。在哈希表每次进行读写操作时，如果检测到当前处于扩容阶段，就完成一部分键值对迁移任务，直到所有的旧桶迁移完毕。

**具体过程：**扩容时，字段oldbuckets指向旧桶，nevacuate记录下一个待迁移的旧桶。

个人觉得，Go本质上还是拉链法，但是它做了一些内存上的优化，以空间换时间，给每个桶预先分配可以放8个数据的空间，和传统的拉链法相比，好处就是不需要频繁的分配内存，同时在某些极限情况下，也可以节省一些空间，传统的拉链法还需要存放前后数据的指针，在64位机器上又是16个字节的开销，但是用数组的方式组织的话，就不需要存储前后的指针。如果一个桶里面存放了超过8个数据，还是需要另一个bmap来放多余的数，然后把两个bmap连接起来。我觉得对比一下，传统的拉链法就是一个节点只能放一个数据，而go是一个节点可以放8个数据，这8个数据是按照数组来组织的。

1.1.4.5 小结

Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些 tophash 就成为可以帮助哈希快速遍历桶中元素的缓存。

哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。

1.1.5 sync.map

问：sync.map 和 mutex+map 有啥区别？sync.map 为啥要有俩 map(read+dirty)？一个不行吗？

一个是不行的，你总不能读不加锁，写加锁吧？这样照样会有并发访问的问题(是会报错的)。但是如果是 read+dirty，就可以对 read 的所有操作都不加锁，对 dirty 的所有操作都要加锁，就可以避免并发问题。我觉得最关键的差别就是这个地方！也是很精妙的地方！

参考文章：

• https://eddycjy.com/posts/go/sync-map/

• https://mp.weixin.qq.com/s/vtvlye801ePWRY7RvtkDmA ⭐

先来看看 sync.map 的底层数据结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type Map struct {
    mu Mutex						// 保护 dirty 和 read
    read atomic.Value 				// readOnly，只读类型，所以是并发安全的
    dirty map[interface{}]*entry	// 一个非线程安全的原始 map
    misses int						// 计数作用。当读数据时，该字段不在 read 中，尝试从 dirty 中读取，不管是否在 dirty 中读取到数据，misses+1。当 misses 累计到 len(dirty) 时，会将 dirty 拷贝到 read 中，并将 dirty 清空，以此提升读性能。
}

// read 的类型为 atomic.Value，它会通过 atomic.Value 的 Load 方法将其断言为 readOnly 对象
read, _ := m.read.Load().(readOnly) // m 为 sync.Map
// read 的真实类型即是 readOnly
type readOnly struct {
    m       map[interface{}]*entry	// read 中的 go 内置 map 类型，但是它不需要锁。
    amended bool	// 当 sync.Map.diry 中的包含了某些不在 m 中的 key 时，amended 的值为 true.
}

// map 存储的值类型是 *entry，它包含一个指针 p，指向用户存储的 value 值。
type entry struct {
    p unsafe.Pointer // *interface{}
}

• mu：保护 dirty；
• read：存只读数据。读是并发安全的，但如果要更新 read，则需要加锁保护；
• dirty：包含最新写入的数据。当 misses 计数达到一定值，将其赋值给 read；
• misses：计数作用。当读数据时，该字段不在 read 中，尝试从 dirty 中读取，不管是否在 dirty 中读取到数据，misses+1。当 misses 累计到 len(dirty) 时，会将 dirty 拷贝到 read 中，并将 dirty 清空，以此提升读性能。

1.1.5.1 查询数据

Load():

• 首先，从只读数据read中读取(因为不用加锁)，若有就直接返回，若无再继续往下；
• 若read没有，且dirty中有新数据，就会去dirty查找；
• 先加锁，然后再次检查read，若还没有，才真正去dirty查找，并且对miss计数器+1(无论是否找到)；
• 若miss的值 >= dirty中的元素数量，就把dirty赋给read，因为穿透次数太多了，然后就可以把dirty置为空了。

 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
33
34
35
36
37
38
39
40

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先从 m.read 中通过 Load 方法得到 readOnly
    read, _ := m.read.Load().(readOnly)
    // 从 read 中的 map 中查找 key
    e, ok := read.m[key]
    
    // 如果 read 没有，并且 dirty 有新数据，那么去 dirty 中查找
    if !ok && read.amended {
        m.mu.Lock()
        // 双重检查：避免在本次加锁的时候，有其他 goroutine 正好将 Map 中的 dirty 数据复制到了 read 中。
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        // 如果 read 中还是不存在，并且 dirty 中有新数据
        if !ok && read.amended {
            e, ok = m.dirty[key]
            // m 计数 +1
            m.missLocked()
        }
        
        m.mu.Unlock()
    }
    
    if !ok {
        return nil, false
    }
    return e.load()	// 返回指针指向的值
}

func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {
        return
    }
    
    // 将dirty置给read，因为穿透概率太大了(原子操作，耗时很小)
    m.read.Store(readOnly{m: m.dirty})
    m.dirty = nil	// 清空 dirty
    m.misses = 0	// 重置 misses
}

1.1.5.2 删除数据

Delete()：

• 首先，从只读数据read中读取，若有的话，就直接从read中"删除"(并非真的删除，只是标记一下)；
• 若read中没有，就获得锁，然后再检查一遍read，然后就从dirty中删除；

 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
33
34
35
36
37
38
39

func (m *Map) Delete(key interface{}) {
    // 读出 read，断言为readOnly 类型
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果 read 中没有，并且 dirty 中有新元素，那么就去 dirty 中去找。这里用到了 amended，当 read 与 dirty 不同时为 true，说明 dirty 中有 read 没有的数据。
    if !ok && read.amended {
        m.mu.Lock()
        // 再检查一次，因为前文的判断和锁不是原子操作，防止期间发生了变化。
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        
        if !ok && read.amended {
            // 直接删除
            delete(m.dirty, key)
        }
        m.mu.Unlock()
    }
    
    if ok {
        // 如果 read 中存在该 key，则将该 value 赋值 nil(采用标记的方式删除！)
        e.delete()
    }
}

// 如果 read 中有该键，则从 read 中删除，其删除方式是通过原子操作
func (e *entry) delete() (hadValue bool) {
    for {
        p := atomic.LoadPointer(&e.p)
        // 如果 p 指针为空，或者被标记清除
        if p == nil || p == expunged {
            return false
        }
        
        // 通过原子操作，将 e.p 标记为 nil
        if atomic.CompareAndSwapPointer(&e.p, p, nil) {
            return true
        }
    }
}

1.1.5.3 增改数据

Store()：

• 首先，从只读数据read中获取该key，若存在，并且没有被标记删除，就尝试更新；
• 如果在read中不存在或已被标记删除，就在dirty中判断是否存在，若已存在，就尝试更新；
• 若在dirty中不存在，就加入dirty；

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

func (m *Map) Store(key, value interface{}) {
    // 如果 m.read 中存在该键，且该键没有被标记删除(expunged)
    // 则尝试直接存储(见 entry 的 tryStore 方法)
    // 注意：如果 m.dirty 中也有该键(key 对应的 entry)，由于都是通过指针指向，所有 m.dirty 中也会保持最新 entry 值。
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    
    // 如果不满足上述条件，即 read 不存在或者已经被标记删除
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
   
    if e, ok := read.m[key]; ok { // read 存在该 key
    // 如果 entry 被标记 expunge，则表明 dirty 没有 key，可添加入 dirty，并更新 entry。
        if e.unexpungeLocked() { 
            // 加入 dirty 中，这儿是指针
            m.dirty[key] = e
        }
        // 更新 entry 指向新的 value 地址
        e.storeLocked(&value) 
        
    } else if e, ok := m.dirty[key]; ok { // read 不存在该 key，但 dirty 存在该 key，更新
        e.storeLocked(&value)
        
    } else { // read 和 dirty 都没有
        // 如果 read 与 dirty 相同，则触发一次 dirty 刷新(因为当 read 重置的时候，dirty 已置为 nil 了)
        if !read.amended { 
            // 将 read 中未删除的数据加入到 dirty 中
            m.dirtyLocked() 
            // amended 标记为 read 与 dirty 不相同，因为后面即将加入新数据。
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value) 
    }
    m.mu.Unlock()
}

// 将 read 中未删除的数据加入到 dirty 中
func (m *Map) dirtyLocked() {
    if m.dirty != nil {
        return
    }
    
    read, _ := m.read.Load().(readOnly)
    m.dirty = make(map[interface{}]*entry, len(read.m))
    
    // 遍历 read
    for k, e := range read.m {
        // 通过此次操作，dirty 中的元素都是未被删除的，可见标记为 expunged 的元素不在 dirty 中！！！
        if !e.tryExpungeLocked() {
            m.dirty[k] = e
        }
    }
}

// 判断 entry 是否被标记删除，并且将标记为 nil 的 entry 更新标记为 expunge
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    
    for p == nil {
        // 将已经删除标记为 nil 的数据标记为 expunged
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

// 对 entry 尝试更新(原子 cas 操作)
func (e *entry) tryStore(i *interface{}) bool {
    p := atomic.LoadPointer(&e.p)
    if p == expunged {
        return false
    }
    for {
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
    }
}

// read 里将标记为 expunge 的更新为 nil
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// 更新 entry
func (e *entry) storeLocked(i *interface{}) {
    atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

在此，给出 map+锁 和 sync.map 的性能测试代码：

benchmark-for-map.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

package mapbench

import "sync"

type MyMap struct {
	sync.Mutex
	m map[int]int
}

type MyRwMap struct {
	sync.RWMutex
	m map[int]int
}

var myMap *MyMap
var myRwMap *MyRwMap
var syncMap *sync.Map

func init() {
	myMap = &MyMap{
		m: make(map[int]int, 100),
	}
	myRwMap = &MyRwMap{
		m: make(map[int]int, 100),
	}

	syncMap = &sync.Map{}
}

func builtinMapStore(k, v int) {
	myMap.Lock()
	defer myMap.Unlock()
	myMap.m[k] = v
}

func builtinMapLookup(k int) int {
	myMap.Lock()
	defer myMap.Unlock()
	if v, ok := myMap.m[k]; !ok {
		return -1
	} else {
		return v
	}
}

func builtinMapDelete(k int) {
	myMap.Lock()
	defer myMap.Unlock()
	if _, ok := myMap.m[k]; !ok {
		return
	} else {
		delete(myMap.m, k)
	}
}

func builtinRwMapStore(k, v int) {
	myRwMap.Lock()
	defer myRwMap.Unlock()
	myRwMap.m[k] = v
}

func builtinRwMapLookup(k int) int {
	myRwMap.RLock()
	defer myRwMap.RUnlock()
	if v, ok := myRwMap.m[k]; !ok {
		return -1
	} else {
		return v
	}
}

func builtinRwMapDelete(k int) {
	myRwMap.Lock()
	defer myRwMap.Unlock()
	if _, ok := myRwMap.m[k]; !ok {
		return
	} else {
		delete(myRwMap.m, k)
	}
}

func syncMapStore(k, v int) {
	syncMap.Store(k, v)
}

func syncMapLookup(k int) int {
	v, ok := syncMap.Load(k)
	if !ok {
		return -1
	}

	return v.(int)
}

func syncMapDelete(k int) {
	syncMap.Delete(k)
}

benchmark-for-map_test.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
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

package mapbench

import (
	"math/rand"
	"testing"
	"time"
)

func BenchmarkBuiltinMapStoreParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			builtinMapStore(k, k)
		}
	})
}

func BenchmarkBuiltinRwMapStoreParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			builtinRwMapStore(k, k)
		}
	})
}

func BenchmarkSyncMapStoreParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			syncMapStore(k, k)
		}
	})
}

func BenchmarkBuiltinMapLookupParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			//k := r.Int()
			k := r.Intn(100000000)
			builtinMapLookup(k)
		}
	})
}

func BenchmarkBuiltinRwMapLookupParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			//k := r.Int()
			k := r.Intn(100000000)
			builtinRwMapLookup(k)
		}
	})
}

func BenchmarkSyncMapLookupParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			syncMapLookup(k)
		}
	})
}

func BenchmarkBuiltinMapDeleteParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			builtinMapDelete(k)
		}
	})
}

func BenchmarkBuiltinRwMapDeleteParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			builtinRwMapDelete(k)
		}
	})
}

func BenchmarkSyncMapDeleteParalell(b *testing.B) {
	b.RunParallel(func(pb *testing.PB) {
		r := rand.New(rand.NewSource(time.Now().Unix()))
		for pb.Next() {
			// The loop body is executed b.N times total across all goroutines.
			k := r.Intn(100000000)
			syncMapDelete(k)
		}
	})
}

1.2 语言基础

1.2.1 函数调用

1.2.1.1 栈帧布局

按照编程语言定义的函数，会被编译器编译为一堆机器指令，写入可执行文件，在运行时被加载到内存，位于虚拟地址空间的代码段。

当出现函数调用时，编译器就会对应生成一条call指令，程序执行到这条指令时，就会跳转到对应函数入口处执行，而每个函数最后都有一个ret指令，负责在函数调用结束后，跳转回调用处继续执行。

函数执行时需要足够的内存空间来存放局部变量、参数、返回值等数据，这些数据对应到虚拟地址空间的栈。

栈的执行顺序是从低地址到高地址，所有函数的栈帧格式都是统一的。执行到call指令会做两件事情：

• 首先是将下一条指令入栈，也即返回地址，当执行完调用函数就会跳转回这里；
• 然后会跳转到被调用函数入口处开始执行，这个过程是通过偏移量+栈指针sp完成的。

指令运行时，CPU用特定寄存器来存储运行时的栈基和栈指针，同时也有指令指针寄存器用来存放下一条要运行的指令。

Go语言中不是逐步扩张栈帧的，而是一次性分配。然后通过栈指针+偏移值使用栈帧。

==Point：==

一次性分配栈帧主要是为了避免栈访问越界。

而Go语言编译器会在函数头部插入检测代码，当发现需要进行**“栈增长”**，就会另外分配一段足够大的栈空间，并把原来栈上的数据拷贝过来，同时释放原来那段栈空间。

**==call和ret指令==：**此处最好是看视频理解。

需要注意的是，可执行文件存放在代码段，所用的参数、变量等存放在栈空间，寄存器是指向栈空间的！

1.2.1.2 传参与返回值

==传值与传引用：==

• **传值：**函数调用时会对参数进行拷贝，被调用方和调用方两者持有不相关的两份数据；
• **传引用：**函数调用时会传递参数的指针，被调用方和调用方两者持有相同的数据，任意一方做出的修改都会影响另一方。

不同语言会选择不同的方式传递参数，Go 语言选择了传值的方式，无论是传递基本类型、结构体还是指针，都会对传递的参数进行拷贝。

==传参：==

**过程：**下图swap函数并不能实现交换a, b的作用。

1. 首先需要分配main的栈帧空间，即BP of main 和 SP of main中间的空间；
2. 将main中的局部变量入栈；
3. 从右至左依次将参数入栈(值拷贝)；
4. call会将返回地址入栈，即return addr；
5. 然后就是swap的栈帧了；
6. 可以发现，执行交换操作只是对参数(同时也是swap的内部变量)进行操作，对main中原本的数据并不能造成影响，因此交换失败。

下图swap函数能实现交换a, b的作用。

1. 前两步同上；
2. 从右至左依次将参数入栈，这里同样是值拷贝，只不过值为a、b的地址；
3. 交换时，是直接将addrA和addrB指向的数据进行交换，因此可以交换成功。

==Point：==

Go 语言中传指针也是传值。将指针作为参数传入某个函数时，函数内部会复制指针，也就是会同时出现两个指针指向原有的内存空间。因此，在传递数组或者内存占用非常大的结构体时，我们应该尽量使用指针作为参数类型来避免发生数据拷贝进而影响性能。

==返回值：==

通常返回值是通过寄存器返回，但是Go支持返回多个返回值，也就是有可能返回值的数目大于寄存器个数，因此Go选择在栈上存储返回值。

**匿名返回值：**下图返回结果为1。

被调用函数执行完毕，ret会给返回值赋值，并执行defer函数，这里有一个问题：是先给返回值赋值还是先执行defer函数呢？

**答：**先给返回值赋值，再执行defer函数。

命名返回值：

和上边那个完全相同，只改动一个地方，返回结果为2。==这是因为被调用函数的返回值b一直在调用者栈帧中。==

参数空间分配：

若调用多个函数，将以最大的参数+返回值空间为标准来分配。如下图，将会按照B的参数+返回值空间进行分配，B执行完后，C的参数+返回值会从低地址到高地址进行分配，不满的空间就空着。

1.2.1.3 小结

Go 通过栈传递函数的参数和返回值，==参数和返回值居然是在调用者的栈帧中！！！==在调用函数之前会在栈上为返回值分配合适的内存空间，随后将入参从右到左按顺序压栈并拷贝参数，返回值会被存储到调用方预留好的栈空间上，我们可以简单总结出以下几条规则：

1. 通过堆栈传递参数，入栈的顺序是从右到左，而参数的计算是从左到右；
2. 函数返回值通过堆栈传递并由调用者预先分配内存空间；
3. 调用函数时都是传值，接收方会对入参进行复制再计算；

1.2.2 闭包

函数，可以作为参数传递，可以做函数返回值，也可以绑定到变量。称这样的参数、返回值或变量为**function value**。

function value本质上是一个指针，但是并不直接指向函数指令入口，而是指向一个runtime.funcval的结构体，这个结构体里只有一个地址，就是这个二函数指令的入口地址。

将一个函数赋值给多个变量，这些变量会共用同一个funcval。

那么既然funcval中只有一个地址，为啥不直接使用这个地址呢？

这是为了处理闭包。

闭包的一个示例：

Go 语言中，闭包就是有捕获列表的Function Value。捕获列表中存储的值，通过funcval的地址+偏移量来获取。

==闭包需要维持捕获变量在外层函数和内层函数中的一致性。==

1.2.3 方法

1.2.3.1 方法的本质

如果定义一个类型A，并给他关联一个方法，然后就可以通过类型A的变量来调用这个方法，这种调用方式其实是"语法糖"，实际上和下边那个调用方式一样。

Go语言中，函数类型只和参数与返回值相关，所以下边输出为True，可以说明==方法本质上就是普通函数，接收者就是隐含的第一个参数==。

1.2.3.2 方法调用

其实和函数调用一样。

举例说明过程：

1. Go语言中传参值拷贝，此处为值接收者，所以参数首先为：data=addr1 4；
2. 执行Name()中第一行时，data指向新的string，更新为：data=addr2 8；
3. 返回值就是值拷贝的参数，因此main中的局部变量并未受到影响。

再举个例子对比：

1. Go语言中传参值拷贝，此处为指针接收者，所以参数首先为：pa=&a；
2. 执行Name()中第一行时，修改pa地址处的变量，也就是a，a指向新的string，更新为：data=addr2 8；
3. 返回值就是值拷贝的参数，即a指向的变量。此处main中的局部变量a也会被修改。

上述例子中，通过值调用值接收者的方法，通过指针调用指针接收者的方法，那么如果用值调用指针接收者的方法或用指针调用值接收者的方法，是否可行呢？

答：可行，这些也是"语法糖"，在编译阶段，编译器会进行转换。

1.2.3.3 方法表达式和方法变量

来看看将一个方法赋给一个变量是怎么一回事？

Go语言中，函数作为变量、参数和返回值时都是以Function Value形式存在的，闭包也只是有捕获列表的Function Value而已。

先来看看什么是方法表达式和方法变量：

从本质上讲，方法表达式和方法变量都是Function Value。

看这段代码：

1.2.4 接口

1.2.4.1 概述

计算机科学中，接口是计算机系统中多个组件共享的边界，不同的组件能够在边界上交换信息。如下图所示，接口的本质是引入一个新的中间层，调用方可以通过接口与具体实现分离，解除上下游的耦合，上层的模块不再需要依赖下层的具体模块，只需要依赖一个约定好的接口。

Go 语言中的接口是一种内置的类型，它定义了一组方法的签名。Go 语言中接口的实现都是隐式的，类型实现接口时只需要实现接口中的全部方法。

• 在 Java 中：实现接口需要显式地声明接口并实现所有方法；
• 在 Go 中：实现接口的所有方法就隐式地实现了接口；

1.2.4.2 数据结构

Go 语言根据接口类型是否包含一组方法将接口类型分成了两类：

• 使用 runtime.iface 结构体表示包含方法的接口，又称非空接口类型；
• 使用 runtime.eface 结构体表示不包含任何方法的 interface{} 类型，又称空接口类型，可以接收任意类型的数据；

runtime.eface 结构体：

1
2
3
4

type eface struct { // 16 字节
	_type *_type			// 动态类型：表示类型元数据
	data  unsafe.Pointer	// 动态值：记录在哪
}

举例说明：赋值前_type和data字段都为nil，赋值后：

runtime.iface 结构体：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type iface struct { // 16 字节
	tab  *itab				// 记录动态类型和方法列表
	data unsafe.Pointer		// 动态值
}

type itab struct { // 32 字节
	inter *interfacetype	// 接口的类型元数据，包含接口的方法列表：需要实现的方法
	_type *_type			// 接口的动态类型元数据
	hash  uint32			// 类型哈希值：用于快速判断类型是否相等，类型断言时会用到
	_     [4]byte
	fun   [1]uintptr		// 方法地址数组：用于快速调用方法，无需再去接口的类型元数据寻找方法地址
}

• hash 是对 _type.hash 的拷贝，当我们想将 interface 类型转换成具体类型时，可以使用该字段快速判断目标类型和具体类型 runtime._type 是否一致；
• fun 是一个动态大小的数组，它是一个用于动态派发的虚函数表，存储了一组函数指针。虽然该变量被声明成大小固定的数组，但是在使用时会通过原始指针获取其中的数据，所以 fun 数组中保存的元素数量是不确定的。

举例说明：赋值前tab和data字段都为nil，赋值后：

==Point：==

itab结构体内容一旦确定(接口类型和动态类型)，实际上是不会改变的，因此是可复用的。Go语言会将itab缓存起来，并且以接口类型和动态类型的组合为key(接口类型的hash ^ 动态类型的hash)，以&itab为value构造一个哈希表。需要一个itab时，会先在这里边寻找，如果已经有对应的itab，就直接拿来用，如果没有，就新创建并添加。

1.2.5 类型断言

类型断言作用在抽象类型上，包括：空接口和非空接口。而断言的目标类型可以是具体类型或非空接口类型。这样就组合出来了四种类型断言：

• 空接口.(具体类型)
• 非空接口.(具体类型)
• 空接口.(非空接口)
• 非空接口.(非空接口)

1.2.5.1 空接口.(具体类型)

1.2.5.2 非空接口.(具体类型)

1.2.5.3 空接口.(非空接口)

1.2.5.4 非空接口.(非空接口)

1.2.5.5 小结

类型断言的关键是：明确接口的**==动态类型==及对应的动态类型实现了哪些方法**，而明确这些的关键又在于动态类型的类型元数据，以及空接口与非空接口的**“数据结构”**。

1.2.6 反射

反射的作用就是把类型元数据暴露给用户使用。

反射包中有两对非常重要的函数和类型，两个函数分别是：

• reflect.TypeOf 能获取类型信息；
• reflect.ValueOf 能获取数据的运行时表示。

两个类型是 reflect.Type 和 reflect.Value，它们与函数是一一对应的关系：

1.2.6.1 三大法则

Go 语言反射的三大法则：

1. 从 interface{} 变量可以反射出反射对象；
2. 从反射对象可以获取 interface{} 变量；
3. 要修改反射对象，其值必须可设置；

法则1

为什么是从 interface{} 变量到反射对象？我们也可以执行reflect.ValueOf(1)呀，1是int类型呀，并不是interface{}？

由于 reflect.TypeOf、reflect.ValueOf 两个方法的入参都是 interface{} 类型，所以在方法执行的过程中发生了类型转换。因为 Go 语言的函数调用都是值传递的，所以变量会在函数调用时进行类型转换。基本类型 int 会转换成 interface{} 类型，这也就是为什么第一条法则是从接口到反射对象。

• 通过TypeOf获得变量类型；
• 通过ValueOf获得变量值；
• 然后就可以通过Method获得类型实现的方法；
• 通过Field获得类型包含的全部字段。

法则2

从反射对象可以获取 interface{} 变量。reflect 中的 reflect.Value.Interface 就能完成这项工作。

不过调用 reflect.Value.Interface 方法只能获得 interface{} 类型的变量，还需要进行类型断言才能变成原类型。

从反射对象到接口值的过程是从接口值到反射对象的镜面过程，两个过程都需要经历两次转换：

• 从接口值到反射对象：
  • 从基本类型到接口类型的类型转换；
  • 从接口类型到反射对象的转换；
• 从反射对象到接口值：
  • 反射对象转换成接口类型；
  • 通过显式类型转换变成原始类型(如果原来就是接口类型，那么不必这一步)。

法则3

假如想要更新原变量的值，如果这样写，是不行的：

1
2
3
4
5
6

func main() {
	i := 1
	v := reflect.ValueOf(i)
	v.SetInt(10)
	fmt.Println(i)
}

需要这样写：

1
2
3
4
5
6

func main() {
	i := 1
	v := reflect.ValueOf(&i)
	v.Elem().SetInt(10)
	fmt.Println(i)
}

1. 调用 reflect.ValueOf 获取变量指针；
2. 调用 reflect.Value.Elem 获取指针指向的变量；
3. 调用 reflect.Value.SetInt 更新变量的值：

1.2.6.2 类型和值

TypeOf

如何传递参数

可以思考一下此处栈上参数列表应该是怎样的？

由于TypeOf的参数是空接口类型，空接口是动态类型，实际大小不知道，因此需要传递地址，但是如果传递a的地址进去，就会违背Go语言值拷贝的特性，可能会修改原a的值，那么应该怎么做呢？

实际上在编译阶段，会对a进行copy，实际传的是copy of a的地址，所有参数为空接口类型的情况，都是这样。

返回值是什么？

通过TypeOf返回的，其实是一个非空接口变量：

ValueOf

参数传递

同TypeOf，同时，ValueOf会将这个临时变量地址显式的逃逸到堆上。

例：

a的地址被显式的逃逸到堆，注意此处的返回值ptr=&a：

接下来调用v.Elem()，会拿到v.ptr指向的变量a，并把它包装成reflect.Value类型的返回值(ptr又变为&a)，赋值给v：

然后在调用v.SetString()，此时通过参数v拿到a的地址，修改的就是原来的a：

1.2.7 方法集

问题：T和*T的方法集是啥关系？

T和*T是两种类型，分别有着自己的类型元数据，而根据自定义类型的类型元数据，可以找到该类型关联的方法列表，既然T和*T各有各的方法集，那为什么还要限制T和*T不能定义同名方法？又怎么会有"*T的方法集包含T的方法集"这种说法？

**答：**首先，可以确定的是，T的方法集里，全部都是有明确定义的接收者为T类型的方法；而*T的方法集里，除了有明确定义的接收者为*T的方法以外，**还会有编译器生成的一些"包装方法"：**这些包装方法是对接收者为T类型的同名方法的"包装"，为什么编译器要为接收者为T的方法包装一个接收者为*T的同名方法呢？

你可能会想到 Go 支持通过指针变量访问方法。但这里首先要明确一点：通过*T类型的变量直接调用T类型接收者的方法只是一种语法糖，经验证，这种调用方式，编译器会再调用端进行指针解引用，并不会用到这里的包装方法。

==实际上，编译器生成包装方法主要是为了支持接口。==

非空接口的数据结构只包含两个指针，一个和类型元数据相关，一个和接口装载的数据相关，虽然有数据指针，但却不能像上述语法糖那样，通过指针解引用来调用值接收者的方法。**原因：**方法的接收者是方法调用时隐含的第一个参数，Go 中的函数参数是通过栈来传递的，如果参数指针类型，那就很好实现：平台确定了，指针大小就确定了。但如果要解引用为值类型，就要有明确的类型信息，编译器才能确定这个参数要在栈上占用多大的内存空间。而对于接口，编译阶段并不能确定它会装载哪一类的数据，所以编译器并不能生成对应的指令来解引用。

总而言之，==接口不能直接使用接收者为值类型的方法==。

针对这个问题，编译器选择为值类型接收者的方法，生成指针接收者"同名"包装方法这一解决方案。

因此，回到最初的问题：“为什么还要限制T和*T不能定义同名方法？”，如果给T和*T定义了同名方法，就有可能和编译器生成的包装方法发生冲突，所以 Go 干脆不允许为T和*T定义同名方法。

至于，"*T的方法集包含T的方法集的所有方法"，这种说法可以这样理解。虽然编译器会为所有接收者为T的方法生成接收者为*T的包装方法，但是链接器会把程序中确定用不到的方法都裁剪掉，所以如果去分析可执行文件的话，就会发现不止是这些包装方法，就连我们明确定义的方法，也不一定会存在于可执行文件中。不过，一定要从可执行文件中去分析，不能通过反射去验证，因为反射的实现也是基于接口。若通过反射来验证，会被链接器认为用到了这个方法，从而把它保留下来，这就"测不准"了。

1.2.8 泛型

go 1.17

在代码中经常会用到一些本地缓存组件，它们是复用性极高的基础组件，在使用体验上和map差不多，都提供了Set和Get方法。为了支持任意类型，这些方法都使用了空接口类型的参数，内部实际存储数据的是个值类型为空接口的map。

使用Set方法时，一般不会觉得有什么不方便，因为从具体类型或接口类型，到空接口的赋值不需要额外处理。但是Get方法使用时，需要通过类型断言，把取出来的数据转换成预期的类型。比如想从本地缓存c里面取出来一个string，就需要这样写：

1
2
3
4
5

if v, ok := c.Get("key"); ok {
    if s, ok := v.(string); ok {
        // use s
    }
}

如果是仅仅多这一步，那也无可厚非，可实际上并不这么简单。

**空接口本质上是一对指针，用来装载值类型时会发生装箱，造成变量逃逸。**例如用Cache来缓存int64类型，缓存对象c底层是个map，在map的buckets中存储着元素的哈希值、key和value，对于c而言，bucket这里存储的value是一个一个的空接口，而实际上的int64会在堆上单独分配，空接口的data指针指向堆上的int64，相较于直接把int64存储在map的bucket里，堆分配方式凭空多出来一次堆分配，而且还多占用了两倍的内存空间。

针对这个问题，改造上述缓存为泛型缓存。

• 将Cache改为cache，因为 Go 1.17 的泛型实现还不支持导出，泛型相关的类型和函数只能在当前包中使用；
• Go 1.17 的泛型支持默认是关闭的，构建可执行文件时应指定参数来显式的开启，而且，据观察build命令只有在编译main包时，才会透传这个参数，这就限制了只能在main包中使用泛型。

改造好后，同样用来存储int64类型的数值，然后，通过反射观察底层map存储的是什么样类型的元素，下边的代码会打印int64，也就是说，泛型缓存cache的底层map会直接在bucket中存储int64类型的数值，没有额外的堆分配。

可以看出，泛型能够解决这个问题。但是，这不是没有代价的。

泛型的实现：

使用泛型最直接的代价就是：编译器会为同一套模板的每个类型，都生成一套代码，可能会导致可执行文件大小有所增加；而且，即便使用泛型，要想在一个缓存对象里面存储多种不同类型的值，依然要使用空接口，否则，一个缓存对象就只能存储一种类型的值。

所以说，泛型本质上是编译阶段的代码生成，它并不会替代空接口，空接口主要用来实现语言的动态特性，它们的适用场景根本不同~

go 1.18

Go 从 1.18 正式开始支持泛型，这里的T就是类型参数，与java、c++对比，没有使用<>，而是使用[]：

同时，为了让编译器能够更高效的检查类型参数的合法性，还引入了类型参数的约束条件。这个约束条件在语法层面是通过接口来实现的，它明确描述了调用方传入的类型参数，需要符合什么样的要求。

这里的fmt.Stringer接口限制了调用ToString方法时，传入的参数必须实现了String()方法，如果传入的参数不符合要求，就无法通过编译。当然，此处的接口也并不是原来的接口。

若使用原来的接口，就只能通过接口的方法集来约束类型参数，但这有时是行不通的。因为，这些内置类型是没有实现任何方法的，比如int32、int64。

例如，写了一个Sum()函数，想让它支持所有整型类型，该如何实现呢？

Go 1.18 将接口扩展了一下。原来的接口只能定义方法集，扩展后的接口增加了类型集，通过类型集指明哪些类型是被支持的。

例如，Integer接口用作约束条件时，就可以支持所有的有符号整型。

但这依然不够，如果我们自定义了type MyInt int类型，同样也希望被支持，这个约束条件又该怎么写呢？总不能每次新增加自定义类型都去改一下接口的类型集吧？

为了解决这个问题，Go 新增加了符号~，只要写~int，就可以支持**int类型以及基于int创建的所有自定义类型**，

**注意：**这种扩展后的接口，目前只用于泛型的约束条件。

现在有了泛型，只需要实现一遍功能函数，就可以通过多种类型参数来调用。

**问题：**编译器会不会给每种支持的类型都生成一套代码呢？// ==TODO==

貌似不用。通过字典和gcshape实现。没听懂。先这样吧。。。

1.3 常用关键字

1.3.1 defer

使用defer的最常见场景是在函数调用结束后完成一些收尾工作，通常用来：

• 关闭文件描述符；
• 关闭数据库连接；
• 解锁资源

通常使用defer会遇到两个常见的问题：

• defer 关键字的调用时机以及多次调用 defer 时执行顺序是如何确定的；
• defer 关键字使用传值的方式传递参数时会进行预计算，导致不符合预期的结果。

==执行顺序==

deferProc()负责把要执行的函数信息保存起来，称之为**defer注册**；defer注册完成后，会继续执行后面的逻辑，直到返回之前通过deferreturn执行注册的defer函数。即：先注册，再延迟调用。

defer会在函数返回之前，按照倒序执行。这是因为goroutine运行时会有一个对应的结构体g，其中有一个字段指向defer链表头，defer链表链起来的是一个个_defer结构体，新注册的defer会添加到链表头，执行时从头开始，因此执行顺序是注册顺序的倒序。

==预计算参数==

Go 语言中所有的函数调用都是传值的，虽然 defer 是关键字，但是也继承了这个特性。如下代码：

1
2
3
4
5
6
7
8
9

func main() {
	startedAt := time.Now()
	defer fmt.Println(time.Since(startedAt))
	
	time.Sleep(time.Second)
}

$ go run main.go
0s

为什么会输出0呢？这是因为：调用 defer 关键字会立刻拷贝函数中引用的外部参数，所以 time.Since(startedAt) 的结果不是在 main 函数退出之前计算的，而是在 defer 关键字调用时计算的，最终导致上述代码输出 0s。

想要解决这个问题的方法非常简单，我们只需要向 defer 关键字传入匿名函数：

1
2
3
4
5
6
7
8
9

func main() {
	startedAt := time.Now()
	defer func() { fmt.Println(time.Since(startedAt)) }()
	
	time.Sleep(time.Second)
}

$ go run main.go
1s

1.3.1.1 数据结构

defer在Go语言中的结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

type _defer struct {
	siz       int32		// 参数和返回值共占多少字节
	started   bool		// 标记defer是否已经执行
	openDefer bool		// 
	sp        uintptr	// 调用者栈指针
	pc        uintptr	// 返回地址
	fn        *funcval	// defer 关键字中传入的函数，即注册函数
	_panic    *_panic	// 触发延迟调用的结构体，可能为空
	link      *_defer	// 下一个_defer指针
}

可以看出runtime._defer 结构体其实是_defer调用链表上的一个元素，所有的结构体都会通过 link 字段串联成链表。

1.3.1.2 执行机制

堆分配、栈分配和开放编码是处理 defer 关键字的三种方法。

• Go 1.12 引入：堆分配runtime._defer 结构体；

• Go 1.13 引入：栈分配的结构体；

• Go 1.14- 引入：基于开放编码的 defer。

1.3.1.3 堆分配

deferproc函数执行时，需要堆分配一段空间，存放_defer结构体及参数与返回值。实际上Go语言也会预分配不同规格的_defer池，执行时从空闲_defer池中取出一个，没有合适的或空闲的就会进行堆分配，用完之后再放入_defer池，以避免频繁的堆分配与回收。

Go 1.12 defer很慢！原因：

• _defer结构体堆分配：即使有预分配的deferpool，也需要去堆上获取和释放，而且，参数还要在堆栈间来回拷贝；
• _defer注册通过链表：链表本身的操作就慢！

1.3.1.4 栈上分配

先来对比一下1.12版本和1.13版本中，defer指令编译后有什么不同？

1.12 将_defer结构体分配在堆上。在1.13中，通过在编译阶段，增加局部变量，把defer信息保存到当前函数栈的局部变量区域，再通过deferprocStack把栈上这个_defer结构体注册到_defer链表中，执行依然是通过deferreturn实现。优化点：减少defer信息的堆分配。

1.13中的defer，官方提供的性能提升是30%。

1.3.1.5 开放编码

Go 1.14是通过在编译阶段插入代码，把defer函数的执行逻辑展开在所属函数内，从而免于创建_defer结构体，而且不需要注册到_defer链表。这种方式省去了构造_defer链表项，并注册到链表的过程。举例说明：

A1可以简单的通过：定义局部变量，并在return前插入调用A1的指令 来实现延迟调用效果。但是对于A2呢？他在编译阶段是无法确定是否被调用的，因此需要一些处理。

Go语言通过一个**标识变量df**来解决这个问题。

df变量中的每一位对应一个defer函数是否要被执行。

这里先以A1举例：

• df变量首先需要通过异或运算|=将第1位置为1；
• return前插入的调用指令也应该进行修改，需要判断df变量第1位是否>0，若>0，在调用A1前，需要将df变量的第1位置为0，这是为了避免重复调用。

再以A2举例：

• 首先插入 判断是否需要将A2的标志位置为1 的代码；
• 然后在return前插入 检查df标志位 的代码。

这种方法将性能提高了一个数量级，但不是没有代价。

如果在code to do something，也就是还未执行到defer函数调用处，就发生了panic或runtime.Goexit函数，后面这些代码根本无法执行到，因此需要通过栈扫描的方式来发现。所以，defer变快了，但panic变得更慢了。

1.3.1.6 小结

需要注意的是，栈上分配和开放编码的方法均不适用于循环中的defer，因此也保留1.12中的堆分配方法。

1.3.2 panic和recover

• panic 能够改变程序的控制流，调用 panic 后会立刻停止执行当前函数的剩余代码，并在当前 Goroutine 中递归执行调用方的 defer；
• recover 可以中止 panic 造成的程序崩溃。它是一个只能在 defer 中发挥作用的函数，在其他作用域中调用不会发挥作用。

1.3.2.1 现象

• 跨协程失效：panic 只会触发当前 Goroutine 的 defer；
• 失效的崩溃恢复：recover 只有在 defer 中调用才会生效；
• 嵌套崩溃：panic 允许在 defer 中嵌套多次调用。

跨协程失效

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func main() {
	defer println("in main")
	go func() {
		defer println("in goroutine")
		panic("")
	}()

	time.Sleep(1 * time.Second)
}

❯ go run test_go.go
in goroutine
panic:
...

上述代码没有执行main中的defer，只执行了 goroutine 中的defer。

**总结：**当程序发生崩溃时只会调用当前 goroutine 的defer。

失效的崩溃恢复

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func main() {
	defer println("in main")
	if err := recover(); err != nil {
		fmt.Println(err)
	}
	panic("unknown err")
}

❯ go run test_go.go
in main
panic: unknown err
...

在主程序中调用 recover 试图中止程序的崩溃，但是从运行的结果中我们也能看出，程序没有正常退出。应该如下面这样写：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func main() {
	defer println("in main")
	defer func() {
		if err := recover(); err != nil {
			fmt.Println("错误发现:", err)
		}
	}()
	panic("unknown err")
}

❯ go run test_go.go
错误发现: unknown err
in main

可以发现程序正常执行。

总结：recover 只有在发生 panic 之后调用才会生效。然而在上面的控制流中，recover 是在 panic 之前调用的，并不满足生效的条件，所以需要在 defer 中使用 recover 关键字。

嵌套崩溃

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func main() {
	defer println("in main")
	defer func() {
		defer func() {
			panic("panic again and again")
		}()
		panic("panic again")
	}()

	panic("panic once")
}

❯ go run test_go.go
in main
panic: panic once
        panic: panic again
        panic: panic again and again
...

可以确定程序多次调用 panic 也不会影响 defer 函数的正常执行，所以使用 defer 进行收尾工作一般来说都是安全的。

1.3.2.2 数据结构

panic 关键字在 Go 语言的源代码是由数据结构 runtime._panic 表示的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

type _panic struct {
	argp      unsafe.Pointer	// defer的参数空间
	arg       interface{}		// panic的参数
	link      *_panic			// link to earlier panic
	recovered bool				// 是否被 recover 恢复
	aborted   bool				// 是否被终止
	pc        uintptr
	sp        unsafe.Pointer
	goexit    bool
}

和defer一样，panic也是一个链表，当有新的panic出现，也是在链表头插入新的_panic结构体。

panic执行defer时，是从头开始执行的。首先把_defer的started字段置为true，标记该defer已经开始执行，并且会把panic字段指向当前执行的panic，表示这个defer是由这个panic触发的。

如果函数A2能够正常执行，那么就会移除A2。

之所以这样设计，是为了应对defer函数没有正常结束的情况。假如此时A2顺利执行，那么执行A1：

因为A1也会触发panic，那么需要将panicA1链在panic头部，此时正在执行的panic就变成了panicA1，然后也会去执行defer链表，从标记字段会发现A1已经在执行了，且触发他的panic是panicA，所以会根据该指针找到panicA，把他**aborted标记为已终止**。

所以现在panicA已终止，A1也执行完毕，A1会被移除，当前defer链表为空。

接下来就该打印panic信息了，注意：**panic打印异常信息时，会从链表尾开始，即panic的发生顺序逐个输出。**所以此处会先panicA，再panic A1。

1.3.2.3 recover

上述过程没有添加recover，接下来看看添加recover之后的情况。

recover只做一件事，就是把当前panic的recovered字段变为true。

**以下为例。**当执行完A2时，会将当前panicA的recovered=true。每个defer执行完毕，panic都会检查当前recovered是否为true。此时会发现panicA已经被恢复了，就会把他从panic链表中移除，并且移除A2。不过A2被移除之前，要保存_defer.sp和_defer.pc，接下来就要利用这两个值跳出panicA的处理流程。

sp和pc是注册defer函数时保存的。这里sp就是函数A的栈指针，而pc就是调用deferproc函数的返回地址。

通过sp可以返回到函数A的栈帧，通过pc可以返回到调用deferproc处(即判定r>0)处。若此时r=0，那么code to do something就会被重复执行，所以会将寄存器中的r=1，这样就可以跳转到deferreturn处，继续执行defer链表。**注意：deferreturn只负责执行当前函数A注册的defer函数，**他是通过栈指针来判断的。

所以，A2执行完毕，还会继续执行A1，执行完毕就结束了。

**这里要注意：**只有当defer函数执行完毕，panic才会去检查是否被恢复。但是如果defer先recover，然后又panic了呢？

此时，由于发生了panic，所以会将panicA2注册到panic链表头，并成为当前的panic，他会去执行defer链表，当执行A2时，从标记字段发现A2已经开始执行，并且触发者是panicA，那么会将panicA终止(aborted=true)，并把A2从defer链表移除。继续执行下一个defer，A1就是由panicA2触发的了。

A1执行完毕后，会被移除，此时defer链表为空。

接下来就要输出panic信息了。

注意：在输出已经被recover的panic时，打印时会带上recovered标记。panic每一项被输出后，程序退出。

小结

• 用defer进行收尾工作通常是安全的，这是因为panic可以终止其他代码的执行，但不会影响到defer的执行。

• 在判断panic的执行过程时，只需要把握住两个链表defer和panic的执行顺序即可。

二、运行时

2.1 并发编程

2.1.1 GMP

2.1.1.1 概述

Go语言在并发编程方面有强大的能力，这离不开语言层面对并发编程的支持。谈到Go语言调度器，绕不开的是操作系统、进程与线程这些概念。

**多个线程可以属于同一个进程并共享内存空间。**因为多线程不需要创建新的虚拟内存空间，所以它们也不需要内存管理单元处理上下文的切换，线程之间的通信也正是基于共享的内存进行的，与重量级的进程相比，线程显得比较轻量。这不是挺好的嘛，为啥还要引入goroutine？

**引入goroutine的原因：**虽然线程比较轻量，但是在调度时也有比较大的额外开销。每个线程都会占用 1M 以上的内存空间，在切换线程时不止会消耗较多的内存，恢复寄存器中的内容还需要向操作系统申请或者销毁资源，每一次线程上下文的切换都需要消耗 ~1us 左右的时间，但是 Go 调度器对 Goroutine 的上下文切换约为 ~0.2us，减少了 80% 的额外开销。

==Point：==

Go语言中：

• 协程对应的数据结构是runtime.g；
• 工作线程对应的数据结构是runtime.m；
• 后来引入了runtine.p，**引入原因：**一开始所有的g都在一个全局队列中，多个m从全局队列中获取g时需要频繁的加解锁及等待；引入p后，m就可以直接从关联的p处获取待执行的g，不用每次都和众多m从一个全局队列中争抢任务，提高了并发性能。

其中，allgs、allm、allp分别记录所有的g、m和p。

首先看一个简单的场景

只有一个mian.main。

在main goroutine创建前，G、P、M的情况如上图。

• main goroutine创建后，被加入当前P的本地队列中；
• 然后通过mstart开启调度循环。这个mstart是所有工作线程的入口，主要就是调用schedule函数，也就是执行调度循环。

• 当前队列中只有main goroutine等待执行，所以m0切换到main goroutine；

• 执行入口自然是runtime.main，它会做很多事情：创建监控线程、进行包初始化等，包括调用main.main，然后就可以执行main.main了！

  

一个改进的场景

在main.main中又创建新的goroutine。

• 我们通过go关键字创建goroutine，会被编译器转换为newproc函数调用。(main goroutine也是由newproc创建的)
• 创建goroutine时，我们只负责指定入口、参数，而newproc会给goroutine构造一个栈帧，目的是让协程任务结束后，返回到go exit函数中，进行协程资源回收处理等工作。

• 新创建的goroutine，此处叫做hello goroutine，会被添加到当前P的本地runq中；
• 然后main.main就会返回了，然后exit()函数被调用，进程就结束了。所以此处hello goroutine并未能执行。

**问题：**问题在于，当main.main返回后，直接会调用exit()函数，会把进程都结束掉，没给hello goroutine调度执行的时间。所以应该在main.main返回前，拖延点时间给hello goroutine执行。

2.1.1.2 goroutine创建、让出与恢复

还通过一个例子来看一下。

通过函数栈帧看一下newproc的调用过程：

• main函数栈帧自然分配在main goroutine的协程栈中；

• newproc主要做的就是切换到g0栈去调用newproc1函数；为什么要切换到g0栈呢？简单来说，g0栈空间大。因为runtime中很多函数都有no-split标记，意味着这个函数不支持栈增长，而协程栈空间本来就小，容易栈溢出，而g0的栈直接分配在线程栈上，栈空间足够大。

  

• newproc1(协程入口, 参数地址, 参数大小, 父协程, 返回地址)；

• newproc1首先通过acquirem()禁止当前m被抢占。**为什么不能被抢占？**因为接下来要执行的程序中，可能会把当前p保存到局部变量中，若此时m被抢占，p关联到别的m，等再次恢复时，继续使用这个局部变量里保存的p，就会造成问题。所以为了保持数据的一致性，会暂时禁止m被抢占。

• 接下来，会尝试获取一个空闲的g，如果当前p和调度器中都没有空闲的g，就创建一个并添加到全局变量allgs中。此处我们依然将此添加的g记为hello goroutine，此时它的状态是_Gdead，而且已然拥有自己的协程栈。

• 接下来，如果协程入口函数有参数，就把参数移动(拷贝)到协程栈上。

• 接下来，会把goexit()的地址+1，压入协程栈，即返回地址；

• 再把协程(hello goroutine)对应的g的startpc置为协程入口函数的起始地址，gopc置为父协程调用newproc后的返回地址，g.sched结构体用于保存现场：g.sched.sp置为协程栈指针，g.sched.pc置为协程入口函数的起始地址。

• 等到这个协程得到调度执行的时候，通过g.sched恢复现场，就会从协程入口函数处开始执行，而函数结束后便会返回到goexit()中，执行协程资源回收等收尾工作。到此，协程如何出场与收场就都有了着落。
• 接下来，newproc1还会给新建的goroutine赋予一个唯一id。给g.goid赋值前，会把协程的状态置为_Grunnable，这个状态意味着这个g可以进到run queue中了。
• 所以接下来会调用runqput把这个g放到当前p的本地队列中。
• 接下来判断，如果当前有空闲p，而且没有处于spinning状态的m，即所有m都忙，而且主协程已经开始执行了，那么就调用wakep()：启动一个m并把它置为spinning状态。
• 最后与一开始的acquirem()呼应，会调用releasem()允许当前m被抢占；而spinning状态的m启动后，会一直执行调度循环寻找任务，从本地runq到全局runq再到其他p的runq，只为找到个待执行的g。但此时，若main.main已经返回，那也不会执行剩余的g。

此处我们通过等待一个channel来实现调度执行g。

• 当前main goroutine会阻塞在<-ch这里等待数据；
• 然后chanrecv()通过gopark()函数挂起当前goroutine，让出cpu；
• gopark()首先会调用acquirem()禁止当前m被抢占，然后把main goroutine的状态从_Grunning修改为_Gwaiting，main goroutine就不再是执行中状态了；
• 接下来调用releasem()解除m的抢占禁令；
• 最后调用mcall(park_m)：负责保存当前协程的执行现场；
• 然后切换到g0栈，调用由mcall的参数传入的这个函数，对应到这里就是park_m()函数；
• park_m()函数会根据g0找到当前m，把m.curg置为nil。此时当前m正在执行的g便不再是main goroutine了；
• 最后会调用schedule()寻找下一个待执行的g。
• 然后，hello goroutine要么被当前m0调度执行，要么被其他m调度执行，总归是能执行了。

• 等到hello goroutine执行完毕，关闭main gorutine等待的channel时，不止会修改channel的closed状态，还会处理等待队列中的g，最终调用goready()函数来结束这个g的等待状态；
• 而goready()函数会切换到g0栈，并执行runtime.ready()函数，目前待ready的协程自然是main goroutine，此时它的状态是_Gwaiting，接下来会被修改为_Grunnable，表示它又可以被调度执行了。
• 然后，它会被放入当前p的本地runq中，同协程创建时一样，接下来也会检查是否有空闲的p，并且没有spinning状态的m，是的话，也会调用weakp()函数启动新的m；
• 接下来hello goroutine结束，main goroutine得到调度执行，最终结束进程。

总结：底层通过newproc创建goroutine，通过gopark实现协程让出，使用goready把协程恢复到runnable状态放回到runq中

接下来，就需要了解调度循环schedule()是做啥的了，以及如何把一个可运行的协程真正的运行起来？

2.1.1.3 goroutine让出、抢占、监控和调度

协程让出CPU分为两种：主动让出和被动让出(抢占)。其中，主动让出指协程自身要等待某种条件而主动让出，被动让出指调度器通过某种规则强制使协程让出。

主动让出

主动让出主要包括三种形式：time.Sleep()，<-chan和I/O操作。

1. time.Sleep()

整体过程：协程执行time.Sleep()时，状态会从_Grunning变为_Gwaiting，并进入到对应的timer中等待，而timer中持有一个回调函数，在指定时间到达后调用这个回调函数，把等在这里的协程恢复到_Grunnable状态并放回到runq中。

**这里有一个问题？**谁负责触发timer注册的回调函数呢？

答：其实每个p都有一个最小堆，存储在p.timers中，用于管理自己的timer，堆顶的timer就是接下来要触发的那一个。而每次调度时，都会调用checkTimers()函数，检查并执行那些已经到时间的timer。不过这不够稳妥，万一所有的m都在忙，那么就不能及时触发调度了，可能会导致timer执行时间发生较大偏差。所以还会通过监控线程来增加一层保障。

(接上)。监控线程是由main goroutine创建的，与GPM中的工作线程不同，并不需要依赖p，也不由GPM调度。

监控线程有多个任务，其中一项便是保障timer的正常执行。监控线程检测到接下来有timer要执行时，若此时无空闲m，便会创建新的工作线程m以保障timer可以顺利执行。

2. <-chan

**整体过程：**协程等待一个channel时，其状态也会从_Grunning变为_Gwaiting，并进入到对应channel的读队列或写队列中等待，等待的channel可读、可写了会通知到相关协程。

3. I/O

整体过程：协程等待一个I/O事件，也需要进行让出。以epoll为例，若I/O事件尚未就绪，需要注册要等待的I/O事件到监听队列中，而每个监听对象都可以关联一个event data，所以就在这里记录是哪个协程在等待，等到事件就绪时再把它恢复到runq中即可。与timer和channel不同的是，没有谁能通知协程是否就绪，因此想要获取I/O事件就绪情况需要主动轮询(netpoll)，这里的主动轮询是指非阻塞的查询是否有已就绪的IO事件。全局变量sched会记录上次netpoll执行的时间lastpoll，监控线程检测到距离上次轮询已经超过10ms便会再次执行netpoll。

抢占

监控线程要本着公平调度的原则，对运行时间过长的p实行**“抢占”**操作。就是告诉那些运行时间超过特定阈值(10ms)的g，该让出了！

问题：那么，怎么知道运行时间过长了呢？

p里面有一个schedtick字段，每当调度执行一个新的g，并且不继承上个g的时间片时，就会把p.schedtick++，而sysmontick.schedwhen记录上一次调度的时间。监控线程如果监测到sysmontick.schedtick与p.schedtick不相等，说明这个p发生了新的调度，就会同步sysmontick.schedtick的值，并更新调度时间sysmontick.schedwhen；但若二者相等，说明没发生新的调度，或者即使发生了新的调度，也沿用了之前的时间片，所以可以通过当前时间与sysmontick.schedwhen的差值来判断当前p上的g是否运行时间过长。

问题：那如果真的运行时间过长了，怎么通知它让出呢？

答：Go 1.14之前使用的是栈增长。栈增长共三种情况：

其中，和协程调度相关的是第三种。当runtime希望某个协程让出CPU时，就会把他的stackguard0(栈下界)赋值为stackPreempt，这是一个非常大的值，真正的栈指针不会指向这个位置，因此用作特殊标识。

进而会跳转到morestack处，而morestack会调用runtime.newstack()函数，负责栈增长工作。不过他在进行栈增长工作前会先判断stackguard0是否等于stackPreempt，等于的话就不进行栈增长了，而是执行一次协程调度。

所以，Go 1.14之前实际上是通过设置stackguard为stackPreempt来完成协程让出的。

这种方式的缺点是过度依赖栈增长代码，如果来个空的for{}循环，因为与栈增长无关，程序就会卡死在这个地方。

这一问题在Go 1.14版本得到解决。因为实现了异步抢占。

不同系统中的实现不尽相同，如Unix中。会向协程关联的m发送信号(sigPreempt)，接下来目标线程会被信号中断，转去执行runtime.sighandler()，在sighandler()函数中检测到信号为sigPreempt后，就会调用runtime.doSigPreempt()，它会向当前被打断的协程上下文中注入一个异步抢占函数调用，处理完信号后sighandler()返回，被中断的协程得到恢复，立刻执行被注入的异步抢占函数，该函数最终会调用runtime中的调度逻辑，这就让出了！

上述已经回答了问题。

其实，为了充分利用CPU，监控线程还会抢占处在系统调用中的p，因为一个协程要执行系统调用，就要切换到g0栈，在系统调用没执行完之前，这个**m和g其实绑定了**，不能被分开，也就用不到p，所以在陷入系统调用前，当前m会让出p，解除m.p与当前p的强关联，只在m.oldp中记录这个p。p的数目毕竟有限，如果有其他协程正在等待执行，那就会把他关联到其他m。不过如果当前m从系统调用中恢复，会先检测之前的p是否被占用，没有的话就继续使用，否则再去申请一个，没申请到的话，就把当前g放入全局runq中，然后当前线程就睡眠了。

调度

协程让出了、抢占了之后，总需要给这个m再找个待执行的g来执行吧？这就用到了**schedule()**。

• 首先，要确定当前m是否和当前g绑定了。如果绑定了，那当前m就不能执行其他g，会阻塞当前m，等到当前g再次得到调度执行时，就会把m唤醒；如果没有绑定，就先看看GC是不是在等待执行。如果GC正等待执行，就去执行GC，回来再继续执行调度程序；
• 接下来，会检查有没有要执行的timer；
• 获取下一个要执行的g时，会先去本地runq中查找，没有的话就调用findrunnable()，这个函数直到获取到待执行的g才会返回：在findrunnable()处，也会先判断是否要执行GC，然后先尝试从本地runq中获取，没有的话就从全局runq中获取一部分，如果还没有，就先尝试执行netpoll，恢复那些I/O事件已经就绪的g，它们会被放回全局runq中，然后才会尝试从其他p那里steal一些任务；
• 当调度程序终于获得一个待执行的g后，还需要检查是否已经绑定某个m，如果已经绑定了某个m，还得把这个g送回去，而当前m不得不再次进行schedule()调度；如果没有绑定的m，就调用execute()在当前m上执行这个g；
• execute()会建立当前m与g的关联关系，并把g的状态从_Grunnable改为_Grunning，如果不继承上一个协程的时间片，就把p这里的调度计数p.schedtick+1；
• 最后，会调用gogo()函数，从g.sched这里恢复协程栈指针、指令指针等继续执行。

2.1.2 Mutex

Mutex的由来，应该是mutual exclusion的前缀组合，称为"互斥锁"。

2.1.2.1 两种模式

Go语言sync包中Mutex的数据结构是这样的：

1
2
3
4

type Mutex struct {
    state int32		// 存储互斥锁的状态
    sema  uint32	// 信号量, 用作等待队列
}

• state存储互斥锁的状态，加锁和解锁都是通过atomic包提供的函数原子性的操作该字段：

• sema用作一个信号量，主要用作等待队列。

Mutex有两种模式：

• **正常模式：在正常模式下，一个尝试加锁的goroutine会先自旋几次，尝试通过原子操作获得锁。若几次自旋(自旋阶段)**后仍不能获得锁，则通过信号量排队等待，所有等待者会按照先入先出(FIFO)的顺序排队。

但是当锁被释放，第一个等待者被唤醒后并不会直接拥有锁，而是需要和后来者竞争，也就是那些处于自旋阶段，尚未排队等待的goroutine，这种情况下后来者更有优势：一方面，它们正在CPU运行，自然比刚唤醒的goroutine更有优势，另一方面处于自旋状态的goroutine可以有很多，而被唤醒的goroutine每次只有一个，所以被唤醒的goroutine有很大概率拿不到锁。

这种情况下它会被重新插入到队列的头部，而不是尾部。而当一个goroutine本次加锁等待的时间超过1ms后，它会把当前Mutex从正常模式切换至饥饿模式。

• **饥饿模式：**在饥饿模式下，Mutex的所有权从执行Unlock的goroutine，直接传递给等待队列头部的goroutine。后来者不会自旋，也不会尝试获得锁，即使Mutex处于Unlocked状态。它们会直接从队列的尾部排队等待。

当一个等待者获得锁后，它会在以下两种情况时将Mutex由饥饿模式切换回正常模式：

• 此轮获得锁的等待者的等待时间小于1ms，也就是它刚来不久；
• 它是最后一个等待者，等待队列已经空了，后面自然就没有饥饿的goroutine了。

综上所述：在正常模式下自旋和排队时同时存在的，执行Lock的goroutine会先一边自旋，尝试过几次后如果还没拿到锁，就需要去排队等待了。这种在排队之前先让大家来抢的模式，能够有更高的吞吐量，因为频繁的挂起、唤醒goroutine会带来较多的开销。但是又不能无限制的自旋，要把自旋的开销控制在较小的范围内。所以，在正常模式下，Mutex会有更好的性能，但是可能会出现队列尾端的goroutine迟迟抢不到锁的情况(尾端延迟)。

而饥饿模式下不再尝试自旋，所有goroutine都要排队，严格的先来后到，对于防止出现尾端延迟非常重要。

2.1.2.2 Lock和Unlock

首先看一下关于Mutex.state的几个常量定义：state的类型是int32。

• 第一位用作锁状态标识，置为1就表示已加锁，对应掩码常量为mutexLocked。
• 第二位用于记录是否已有goroutine被唤醒了，置为1表示已唤醒，对应掩码常量为mutexWoken。
• 第三位标识Mutex的工作模式，0代表正常模式，1代表饥饿模式，对应掩码常量为mutexStarving。
• 而常量mutexWaiterShift等于3，表示除了最低3位以外，state的其他位用来记录有多少个等待者在排队。

接下来看一下Lock和Unlock的代码，精简掉注释和部分race检测相关的代码。

两个方法中主要通过atomic函数实现了Fast path，相应的Slow path被单独放在了lockSlow和unlockSlow方法中，这样是为了便于编译器对Fast path进行内联优化。

Lock方法中的Fast path期望Mutex处于Unlocked状态，没有goroutine在排队，更不会饥饿。理想状况下，一个CAS操作就可以获得锁。但是如果CAS操作没能获得锁，就需要进入Slow path，也就是lockSlow方法。

Unlock方法同理，首先通过原子操作从state中减去mutexLocked，也就是释放锁。然后根据state的新值来判断是否需要执行Slow path。如果新值为0，也就意味着没有其他goroutine在排队，所以不需要执行额外操作；如果新值不为0，那就需要进入Slow path，看看是不是需要唤醒某个goroutine。

2.1.2.3 Slow path

**问题：**当一个goroutine尝试给mutex加锁时，如果其他goroutine已经加了锁还没有释放，而且当前mutex工作在正常模式下，是不是就要开始自旋了呢？

答：不一定。因为如果当前是单核场景，或者 GOMAXPROCS=1，或者当前没有其他P正在运行。这些情况下自旋是没有意义的：

• 自旋的goroutine在等待持有锁的goroutine释放锁，而持有锁的goroutine在等待自旋的goroutine让出CPU。
• 除此之外，如果当前P的本地runq不为空，相较于自旋来说，切换到本地goroutine更有效率，所以为保障吞吐量也不会自旋。

问：Goroutine 自旋的条件？

最终，==只有在多核场景下，且GOMAXPROCS > 1，且至少有一个其他的P正在running，且当前P的本地runq为空的情况下，才可以自旋。==

进入自旋的goroutine会先去争抢mutex的唤醒标识位，设置mutexWoken标识位的目的是在正常模式下，告知持有锁的goroutine在Unlock的时候不用再唤醒其他goroutine了，已经有goroutine在这里等待，以免唤醒太多的等待goroutine。

Mutex中的自旋，底层是通过procyield循环执行30次PAUSE，自旋次数上限为4，而且每自旋一次都要重新判断是否可以继续自旋。如果锁被释放了，或者锁进入了饥饿模式，亦或者已经自旋了4次，都会结束自旋。

结束自旋或者根本不用自旋的goroutine就该尝试原子操作修改mutex的状态了。把此时mutex.state保存到old中，把要修改为的新state记为new：

• 如果old处于饥饿模式或加锁状态，goroutine就得去排队，所以这些情况下排队规模要加1。

• 如果是正常模式，就要尝试设置lock位，所以new中这一位要置为1；

• 如果当前goroutine等待的时间已经超过1ms，而且锁还没被释放，就要将mutex的状态切换为饥饿模式。

把排队规模和几个标识位都设置好后，在执行原子操作修改state前，若是当前goroutine持有唤醒标识的话，还需要将唤醒标识位重置，因为，接下来无论是去抢锁还是单纯去排队：

• 如果原子操作成功了，要么成功抢到了锁，要么是成功进到了等待队列，当前goroutine都不再是被唤醒的goroutine了，所以要释放唤醒标识。
• 而如果原子操作失败，也就意味着其他goroutine在我们保存mutex.state到old后又修改了state的值，当前goroutine就要回过头去继续从自旋检查这里开始再次尝试，所以也需要释放自己之前抢到的唤醒标识位，从头再来。

Lock操作的Slow path

继续展开原子操作成功的分支：

• 如果是抢锁操作成功了，那么加锁的Slow path就可以宣告结束了；
• 如果是排队规模设置成功了，还要决定是排在等待队列头部还是尾部。如果当前goroutine已经排过队了，是在Unlock时从等待队列中唤醒的，那就要排到等待队列头部；如果是第一次排队，就得排到等待队列尾部，并且从第一次排队开始记录当前goroutine的等待时间。接下来就会让出，进到等待队列里，队列里的goroutine被唤醒时，要从上次让出的地方开始继续执行。接下来会判断，如果mutex处在正常模式，那就接着从自旋开始抢锁，如果唤醒后mutex处在饥饿模式，那就没有其他goroutine会和自己抢了，锁已经轮到自己这里，只需要把mutex.state中lock标识位设置为加锁，把等待队列规模减去1，再看看是不是要切换到正常模式，也就是自己的等待时间是不是小于1ms，或者等待队列已经空了，最后设置好mutex.state就一切ok了。

Unlock操作的Slow path

进到Unlock的Slow path说明除去lock标识位以外，剩下的位不全为0。

• 如果处在正常模式，若等待队列为空，或者已经有goroutine被唤醒或获得了锁，或者锁进入了饥饿模式，那就不需要唤醒某个goroutine，直接返回即可。否则就要尝试抢占mutexWoken标识位，获取唤醒一个goroutine的权利。抢占成功后，就会通过runtime_Semrelease函数唤醒一个goroutine；如果抢占不成功就进行循环尝试，直到等待队列为空，或者已经有一个goroutine被唤醒或获得了锁，或者锁进入了饥饿模式，则退出循环。

• 而在饥饿模式下，后来的goroutine不会争抢锁，而是直接排队，锁的所有权是直接从执行Unlock的goroutine传递给等待队列中首个等待者的，所以不用抢占mutexWoken标识位。第一个等待者唤醒后，会继承当前goroutine的时间片立刻开始运行，也就是继续lockSlow这里goroutine被唤醒以后的逻辑。

2.1.3 信号量

上节主要讲解 sync.Mutex 的第一个字段 state，本节主要讲解 sync.Mutex 的第二个字段 sema。

**问题：**协程等待一个锁时，要如何休眠、等待和唤醒呢？

**答：**这要靠runtime.semaphore来实现，这是可供协程使用的信号量。runtime内部会通过一个大小为251的sematable来管理所有semaphore，怎么通过这个大小固定的table来管理执行阶段数量不定的semaphore呢？大致思路如下：

这个sematable存储的是251课平衡树的根，平衡树中每个节点都是一个sudog类型的对象，要使用一个信号量时，需要提供一个记录信号量数值的变量，根据它的地址进行计算，映射到sematable中的一颗平衡树上，找到对应的节点就找到了该信号量的等待队列。

例如，我们常用的sync.Mutex中，有一个sema字段，用于记录信号量的数值，如果有协程想要等待这个Mutex，就会根据sema字段的地址计算映射到sematable中的某棵平衡树上，找到对应的节点，也就找到了这个Mutex的等待队列了。所以，syne.Mutex是通过信号量来实现排队的。

而channel需要有读(发送)等待队列以及写(接收)等待队列，还要支持缓冲区功能，所以并没有直接使用信号量来实现排队，而是自己实现了一套排队逻辑。

不过，无论是信号量还是channel，底层实现都离不开runtime.mutex，因为它们都需要保障在面临多线程并发时，不会出现同步问题。

2.1.4 抢占式调度

2.1.4.1 Go 1.13

Go 1.13 的抢占方式是依赖于栈增长检测代码的，并不算严格意义上的抢占式调度。

首先看一段代码：

按理来说，这段代码运行后应该会不断输出递增的数字，但是在 Go 1.14 之前，运行这段代码会发生阻塞。

运行环境是双核CPU，排查之后发现是在执行STW时发生的阻塞。

GC 开始前需要STW来进行开启写屏障等准备工作，所以STW就是要抢占所有的P，让GC得以正常工作。而示例程序中的main goroutine没能被抢占，它一直在执行，而STW一直在等待它让出，这样就陷入了僵局。

**问题：**为什么会陷入这样的局面？

答：首先，梳理下STW的主要逻辑。GC需要抢占所有的P，但这不是说抢占就ok的，所以它会记录下自己要等待多少个P让出，当这个值减为0，目的就达到了。对于当前P、以及陷入系统调用的P(_Psyscall)、还有空闲状态的P，直接将其设置为_Pgcstop即可。对于还有G在运行的P，则会将对应的g.stackguard0设置为一个特殊标识(runtime.stackPreempt)，告诉它GC正在等待它让出。此外，还会设置一个gcwaiting标识(sched.gcwaiting=1)，接下来就通过这两个标识符的配合，来实现运行中的P的抢占。

这是怎么实现的呢？

goroutine创建之初，栈的大小时固定的，为了防止出现栈溢出的情况，编译器会在有明显栈消耗的函数头部插入一些检测代码。通过g.stackguard0来判断是否需要进行栈增长，但如果g.stackguard0被设置为特殊标识runtime.stackPreempt，便不会执行栈增长，而是去执行一次调度(schedule())，在schedule()调度执行时，会检测gcwaiting标识，若发现GC在等待执行，便会让出当前P，将其置为_Pgcstop状态。

这样看来，示例main goroutine之所以没能让出，是因为空的for循环并没有调用函数，也就没有机会执行栈增长检测代码，所以它并不知道GC在等待它让出。

2.1.4.2 Go 1.14 之后

依赖栈增长检测代码的抢占方式，遇到没有函数调用的情况就会出现问题。

在 Go 1.14 及之后，这一问题得到了解决。在Linux系统上，这种真正的抢占式调度是基于信号来实现的，所以也称为异步抢占。

函数preemptone用来抢占一个P，定位到该函数，对比 1.13 和 1.14 的实现有何不同。

信号发送

1.13 中，preemptone函数主要负责设置g.preempt=true，并将g.stackguard0设置为特殊标识(stackPreempt)。

而在 1.14 中，增加了最后这个if语句块：

• 第一个判断用于确认当前硬件环境是否支持这种异步抢占，这个常量值(preemptMSupported)是在编译期间就确定的；
• 第二个判断(debug.asyncpreemptoff)用于检测用户是否允许开启异步抢占，默认情况下是允许的，但是用户可以通过GODEBUG环境变量来禁用异步抢占。
• 如果这两条验证都通过了，就将p.preempt字段置为true，实际的抢占操作会交由preemptM函数来完成。

定位到preemptM函数，它的主要逻辑是通过runtime.signalM函数，向指定M发送sigPreempt信号，怎么发送的呢？

signalM函数会通过调用操作系统中信号相关的系统调用，将指定信号发送给目标线程。信号发出去了，异步抢占的前一半工作就算是完成了。

信号处理

后一半工作就要由接收到信号的工作线程来完成了。

线程接收到信号后，会调用对应的信号handler来处理，Go 语言中的信号交由runtime.sighandler来处理，sighandler在确定信号为sigPreempt以后，会调用doSigPreempt函数。它会首先判断runtime是否要对指定的G进行异步抢占，通过什么来判断呢？

首先，指定的G与其对应P的preempt字段都要为true，而且指定的G还要处在_Grunning状态，还要确认在当前位置打断G并执行抢占是安全的，那么怎么确保安全性呢？

• 指定的G可以挂起并安全的扫描它的栈和寄存器，并且当前被打断的位置并没有打断写屏障；
• 指定的G还有足够的栈空间来注入一个异步抢占函数调用(asyncPreempt)；
• 这里可以安全的和runtime进行交互，主要就是确定当前并没有持有runtime相关的锁，继而不会在后续尝试获得锁时发生死锁。

确认了要抢占这个G，并且此时抢占是安全的以后，就可以放心的通过pushCall向G的执行上下文中注入异步抢占函数调用了，被注入的异步抢占函数(asyncPreempt)是一个汇编函数，它会先把各个寄存器的值保存在栈上，也就是先保存现场到栈上，然后调用runtime.asyncPreempt2函数，这个函数最终会去执行schedule()，到这里，异步抢占就完成了。

再去执行上边的示例程序，发现可以正常运行。也就是说，即使空的for循环没有被插入栈增长检测代码，在 1.14 中，通过注入异步回调函数的方式，同样能实现抢占式调度。

2.1.5 Channel

2.1.5.1 数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

type hchan struct {
	qcount   uint
	dataqsiz uint
	buf      unsafe.Pointer
	elemsize uint16
	closed   uint32
	elemtype *_type
	sendx    uint
	recvx    uint
	recvq    waitq
	sendq    waitq

	lock mutex
}

问：channel底层数据结构是怎么设计的？

通过make创建一个缓冲区大小为5，元素类型为int的channel，ch是存在于函数栈帧上的一个指针，指向堆上的hchan数据结构。

• 因为channel支持协程间并发访问，所以要有一把锁lock来保护整个数据结构。
• 对于有缓冲来讲，需要知道缓冲区在哪，已经存储了多少个元素，最多存储多少个元素，每个元素占多大空间，所以实际上，缓冲区就是个数组buf、elemsize。
• 因为 Go 运行中，内存复制、垃圾回收等机制依赖数据的类型信息，所以hchan还要有一个指针，指向元素类型的类型元数据elemtype。
• 此外，channel支持交替的读(接收)写(发送)，需要分别记录读、写下标的位置recvx、sendx。
• 当读和写不能立即完成时，需要能够让当前协程在channel上等待，待到条件满足时，要能够立即唤醒等待的协程，所以要有两个等待队列，分别针对读(接收)和写(发送)recvq、sendq。
• 此外，channel能够close，所以还要记录它的关闭状态closed。

综上所述，channel底层就长这个样子：

初始状态下，ch的缓冲区为空，读、写下标都指向下标0的位置，等待队列也都为空。然后，一个协程g1向ch发送数据[1,5]，此时缓冲区已满，若还要继续发送数字6，g1就会进到ch的发送等待队列中。这是一个sudog类型的链表，里面会记录哪个协程在等待，等待哪个channel，等待发送的数据在哪儿等信息。

接下来协程g2从ch接收一个元素，recvx指向下一个位置，第0个位置就空出来了，所以会唤醒sendq中的g1，将这里的数据发送给ch，然后缓冲区再次满了，sendq队列为空。

这个过程中，sendx和recvx都会从0到4再到0，循环移动，所以channel的缓冲区也被称为环形缓冲区。

2.1.5.2 发送数据

阻塞式发送

如果使用以下方式给channel发送数据：

1

ch <- 10

不阻塞的情况：

• 缓冲区还有空闲位置；
• 有协程在等着接收数据；

阻塞的情况：

• ch为nil；
• ch没有缓冲区，而且也没有协程等着接收数据；
• ch有缓冲区，但缓冲区已用尽。

非阻塞式发送

1
2
3
4
5
6

select {
case ch <- 10:
    ...
default:
    ...
}

若采用这种写法，如果检测到ch可以发送数据，就会执行case分支；如果会发生阻塞就执行default分支。

2.1.5.3 接收数据

阻塞式接收

以下是接收数据的三种写法，都允许发生阻塞：

1
2
3

<-ch			// 1. 丢弃结果
v := <-ch		// 2. 将结果赋值给v
v, ok := <-ch	// 3. comma ok风格的写法，ok为false表示ch已关闭，此时v是channel元素类型的零值

不阻塞的情况：

• 在缓冲区中有数据；
• 有协程等着发送数据；

阻塞的情况：

• ch为nil；
• ch无缓冲而且没有协程等着发送数据；
• ch有缓冲但缓冲区无数据；

非阻塞式接收

1
2
3
4
5
6

select {
case <-ch:
    ...
default:
    ...
}

若采用非阻塞式接收方式，如果检测到ch的recv操作不会阻塞时，就会执行case分支；如果会阻塞就会执行default分支。

2.1.5.4 多路select

上面的select只是针对单个channel的操作。多路select是指存在两个或更多的case分支，每个分支可以是一个channel的send或recv操作。

例如一个协程通过多路select等待ch1和ch2，这里default分支是可选的，暂且把这个协程记为g1。

多路select会被编译器转换为对runtime.selectgo函数调用，首先看参数：

• 第一个参数cas0指向一个数组，数组里装的是select中所有的case分支，顺序是send在前recv在后；
• 第二个参数order0指向一个uint16类型的数组，数组大小等于case分支的2倍，实际上被用作两个数组：第一个数组用来对所有channel的轮询进行乱序，第二个数组用来对所有的channel的加锁操作进行排序。轮询需要乱序才能保障公平性，而按照固定算法确定加锁顺序才能避免死锁；
• 第三个参数pc0和race检测相关；
• nsends和nrecvs分别表示所有case中，执行send和recv操作的分支分别有多少个。
• block表示多路select是否要阻塞等待。对应到代码中，就是有default分支的不会被阻塞，没有的会阻塞。

再看返回值：

• 第一个返回值int类型，代表最终哪个case分支被执行了，对应到cas0指向的数组下标。但是如果进入到default分支，就会对应-1。
• 第二个返回值bool类型，用于在执行recv操作的case分支时，表明是实际接收到了一个值，还是因channel关闭而得到了零值。

• 多路select需要进行轮询来确定哪个case分支可操作了，但是轮询前需要先加锁，所以selectgo函数执行时，会先按照有序的加锁顺序，对所有的channel加锁；

• 然后按照乱序的轮询顺序检查所有channel的等待队列和缓冲区；

• 假如检查到ch1时，发现有数据可读，那就直接拷贝数据，进入对应分支；

• 假如所有的channel都不可操作，就把当前协程添加到所有channel的sendq或recvq中，对应这个例子，g1会被添加到ch1的recvq及ch2的sendq中，之后g1会被挂起，并解锁所有的channel；

• 假如接下来ch1有数据可读了，g1就会被唤醒，完成对应的分支操作后，会再次按照加锁顺序对所有channel加锁，然后从所有的sendq或recvq中将自己移除；

• 最后全部解锁后返回。