Dawn's Blogs

分享技术 记录成长

0%

GO专家编程读书笔记 (1) 常见数据结构实现原理之chan slice

发表于 更新于 分类于

chan

数据结构

channel 的数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
type hchan struct {
    qcount   uint           // 当前队列中剩余元素个数
    dataqsiz uint           // 环形队列长度，即可以存放的元素个数
    buf      unsafe.Pointer // 环形队列指针
    elemsize uint16         // 每个元素的大小
    closed   uint32            // 标识关闭状态
    elemtype *_type         // 元素类型
    sendx    uint           // 队列下标，指示元素写入时存放到队列中的位置
    recvx    uint           // 队列下标，指示元素从队列的该位置读出
    recvq    waitq          // 等待读消息的goroutine队列
    sendq    waitq          // 等待写消息的goroutine队列
    lock mutex              // 互斥锁，chan不允许并发读写
}

可以看到，channel 的底层数据结构由一个环形队列构成。

lock 保证了 channel 的线程安全，在一个时间点上只会被一个线程（协程）访问。

环形队列

channel 内部实现了一个环形队列作为其缓冲区，环形队列的长度（dataqsiz）是创建 channel 时指定的。如下所示：

img

等待队列

从 channel 读数据，如果 channel 缓冲区为空或者没有缓冲区，当前 goroutine 会被阻塞。同样的，向 channel 写数据，如果 channel 缓冲区已满或者没有缓冲区，当前 goroutine 会被阻塞。

被阻塞的 goroutine 将会挂在 channel 的等待队列（recvq 和 sendq）中：

  • 因读阻塞的 goroutine 会被向 channel 写入数据的 goroutine 唤醒。
  • 因写阻塞的 goroutine 会被从 channel 读数据的 goroutine 唤醒。

下图展示了一个没有缓冲区的 channel，有几个 goroutine 阻塞等待读数据：

img

一般情况下，sendq 和 recvq 至少有一个为空。

只有一个例外，就是用同一个 goroutine 使用 select 语句向 channel 一边读数据一边写数据。

channel 读写

写数据

向一个 channel 中写数据的流程如下：

  • 如果队列 recvq 不为空，则说明缓存区中没有数据或者没有缓冲区，此时从 recvq 中取出 G，并且把数据写入 G 中，最后唤醒 G。
  • 如果队列 recvq 为空：
    • 如果环形队列有空位，则将数据写入环形队列中。
    • 如果环形队列没有空位，则将当前 goroutine 加入到 sendq 中，等待被唤醒。

img

读数据

从一个 channel 中读数据的流程如下：

  • 如果队列 sendq 不为空：
    • 若没有缓冲区，则从 sendq 中取出一个 G 并且从 G 中读取数据，最后唤醒 G。
    • 如果有缓冲区，则从环形队列的队首取出一个数据，并且从 sendq 中取出一个 G 将 G 中的数据写入到环形队列的队尾，最后唤醒 G。
  • 如果队列 sendq 为空：
    • 若缓存区中有数据，则直接从环形队列中读取一个数据。
    • 如果没有数据，则将当前 goroutine 加入到 recvq 中等待被唤醒。

img

关闭 channel

关闭 channel 时会把 recvq 中的 G 全部唤醒，本该写入 G 的数据位置为 nil。把 sendq 中的 G 全部唤醒，但这些 G 会 panic。

panic 出现的常见场景还有：

  • 关闭已经关闭的 channel。
  • 关闭为 nil 的channel。
  • 向已经关闭的 channel 中写入数据。
  • 在 range channel 时，向此 channel 写数据的 goroutine 退出，系统检测到这种情况后会 panic（否则永久阻塞）。

slice

数据结构

slice 的数据结构底层为一个数组 array（array 为指向底层数组的指针），以及当前长度 len 和实际容量 cap。

1
2
3
4
5
type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

在 make([]int, 5, 10) 语句创建 slice 时，会创建一个容量为 10，长度为 5 的 slice。

注意，对 slice 的切片操作会复用底层数组。

扩容

当向 slice 中追加元素时，超过了容量，就会进行扩容。扩容就是申请一片更大的存储空间，将原来数组中存储的数据复制到这段新的地址空间中。扩容容量的选择遵循以下规则：

  • 如果原 slice 容量小于 1024，则新 slice 容量将扩大为原来的 2 倍。
  • 如果原 slice 容量大于等于 1024，则新 slice 容量将扩大为原来的 1.25 倍。

切片时指定容量

在通常的切片操作中是不指定容量的，即 slice[start:end]。

但是，也可以使用指定容量的切片操作，即 slice[start:end:cap]