Go 语言设计与实现-Part1

https://draveness.me/golang/

slice的实现
运行时是SliceHeader结构体

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

扩容：当切片的容量不足时就会调用 runtime.growslice 函数为切片扩容，扩容就是为切片分配一块新的内存空间并将原切片的元素全部拷贝过去。
在分配内存空间之前需要先确定新的切片容量，Go 语言根据切片的当前容量选择不同的策略进行扩容：

如果期望容量大于当前容量的两倍就会使用期望容量；
如果当前切片的长度小于 1024 就会将容量翻倍；
如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

runtime.growslice 函数最终会返回一个新的 slice 结构，其中包含了新的数组指针、大小和容量，
共享：

哈希表

处理哈希冲突的方法：开放寻址（线性探测），拉链法，再哈希
hmap的结构

type hmap struct {
    count     int
    flags     uint8
    B         uint8
    noverflow uint16
    hash0     uint32

    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr

    extra *mapextra
}

count 表示当前哈希表中的元素数量
B 表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 len(buckets) == 2^B；
hash0 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入；
oldbuckets 是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半；

image.png

哈希表 hmap 的桶就是 bmap，每一个 bmap 都能存储 8 个键值对，当哈希表中存储的数据过多，单个桶无法装满时就会使用 extra.overflow 中桶存储溢出的数据。上述两种不同的桶在内存中是连续存储的，将它们分别称为正常桶和溢出桶。

type bmap struct {
    tophash [bucketCnt]uint8
}

这个桶的结构体 bmap 在 Go 语言源代码中的定义只包含一个简单的 tophash 字段，tophash 存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能。

编译期间对bmap进行重建

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

读取和写入
在 bucketloop 循环中，哈希会依次遍历正常桶和溢出桶中的数据，它会比较这 8 位数字和桶中存储的 tophash，每一个桶都存储键对应的 tophash，每一次读写操作都会与桶中所有的 tophash 进行比较，用于选择桶序号的是哈希的最低几位，而用于加速访问的是哈希的高 8 位，这种设计能够减少同一个桶中有大量相等 tophash 的概率。

image.png
哈希的扩容不是一个原子的过程。

哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，整个扩容过程并不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流；除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会对哈希进行『内存整理』减少对空间的占用

哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑进行更新

string的实现

type StringHeader struct {
    Data uintptr
    Len  int
}

funnc String(b []byte) string {
    return *(*string)(unsafe.Pointer(&b))
}

interface

iface:带有一组方法的接口，eface:不带任何方法的 interface{}

type eface struct { // 16 bytes
    _type *_type
    data  unsafe.Pointer
}
type _type struct {
    size       uintptr
    ptrdata    uintptr
    hash       uint32
    tflag      tflag
    align      uint8
    fieldAlign uint8
    kind       uint8
    equal      func(unsafe.Pointer, unsafe.Pointer) bool
    gcdata     *byte
    str        nameOff
    ptrToThis  typeOff
}

type iface struct { // 16 bytes
    tab  *itab
    data unsafe.Pointer
}
type itab struct { // 32 bytes
    inter *interfacetype
    _type *_type
    hash  uint32
    _     [4]byte
    fun   [1]uintptr
}
type interfacetype struct {
    typ     _type
    pkgpath name
    mhdr    []imethod
}

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

type Type interface {
        Align() int
        FieldAlign() int
        Method(int) Method
        MethodByName(string) (Method, bool)
        NumMethod() int
        ...
        Implements(u Type) bool
        ...
}

type Value struct {
        // contains filtered or unexported fields
}

func (v Value) Addr() Value
func (v Value) Bool() bool
func (v Value) Bytes() []byte
...

我们通过 reflect.TypeOf、reflect.ValueOf 可以将一个普通的变量转换成『反射』包中提供的 Type 和 Value，随后就可以使用反射包中的方法对它们进行复杂的操作。

将反射对象还原成接口类型的变量，reflect 中的 reflect.Value.Interface 方法

select的实现
select 在 Go 语言的源代码中不存在对应的结构体，但是 select 控制结构中的 case 却使用 runtime.scase 结构体来表示：

type scase struct {
    c           *hchan
    elem        unsafe.Pointer
    kind        uint16
    pc          uintptr
    releasetime int64
}

kind 表示 runtime.scase 的种类

const (
    caseNil = iota
    caseRecv
    caseSend
    caseDefault
)

在编译期间，Go 语言会对 select 语句进行优化，它会根据 select 中 case 的不同选择不同的优化路径：

空的 select 语句会被转换成 runtime.block 函数的调用，直接挂起当前 Goroutine；
如果 select 语句中只包含一个 case，就会被转换成 if ch == nil { block }; n; 表达式；首先判断操作的 Channel 是不是空的；然后执行 case 结构中的内容；
如果 select 语句中只包含两个 case 并且其中一个是 default，那么会使用 runtime.selectnbrecv 和 runtime.selectnbsend 非阻塞地执行收发操作；
在默认情况下会通过 runtime.selectgo 函数获取执行 case 的索引，并通过多个 if 语句执行对应 case 中的代码；

Go 语言会在运行时执行编译期间展开的 runtime.selectgo 函数，该函数会按照以下的流程执行：

随机生成一个遍历的轮询顺序 pollOrder 并根据 Channel 地址生成锁定顺序 lockOrder；
根据 pollOrder 遍历所有的 case 查看是否有可以立刻处理的 Channel；
如果存在就直接获取 case 对应的索引并返回；
如果不存在就会创建 runtime.sudog 结构体，将当前 Goroutine 加入到所有相关 Channel 的收发队列，并调用 runtime.gopark 挂起当前 Goroutine 等待调度器的唤醒；
当调度器唤醒当前 Goroutine 时就会再次按照 lockOrder 遍历所有的 case，从中查找需要被处理的 runtime.sudog 结构对应的索引；

defer的实现

type _defer struct {
    siz     int32
    started bool
    sp      uintptr
    pc      uintptr
    fn      *funcval
    _panic  *_panic
    link    *_defer
}

runtime._defer 结构体是延迟调用链表上的一个元素，所有的结构体都会通过 link 字段串联成链表。
编译期，将 defer 关键字被转换 runtime.deferproc，在调用 defer 关键字的函数返回之前插入 runtime.deferreturn
运行时，runtime.deferproc 会将一个新的 runtime._defer 结构体追加到当前 Goroutine 的链表头，runtime.deferreturn 会从 Goroutine 的链表中取出 runtime._defer 结构并依次执行；
后调用的 defer 函数会先执行：后调用的 defer 函数会被追加到 Goroutine _defer 链表的最前面，运行 runtime._defer 时是从前到后依次执行
函数的参数会被预先计算：调用 runtime.deferproc 函数创建新的延迟调用时就会立刻拷贝函数的参数，函数的参数不会等到真正执行时计算
因为go的return是一个非原子性操作，比如语句 return i，实际上分两步进行，即将i值存入栈中作为返回值，然后执行跳转，而defer的执行时机正是跳转前，所以说defer执行时还是有机会操作返回值的

panic和recover的实现

type _panic struct {
    argp      unsafe.Pointer
    arg       interface{}
    link      *_panic
    recovered bool
    aborted   bool

    pc        uintptr
    sp        unsafe.Pointer
    goexit    bool
}

argp 是指向 defer 调用时参数的指针；
arg 是调用 panic 时传入的参数；
link 指向了更早调用的 runtime._panic 结构；
recovered 表示当前 runtime._panic 是否被 recover 恢复；
aborted 表示当前的 panic 是否被强行终止；
panic 函数可以被连续多次调用，它们之间通过 link 的关联形成一个链表。

编译器会将关键字 panic 转换成 runtime.gopanic，该函数的执行过程包含以下几个步骤：

创建新的 runtime._panic 结构并添加到所在 Goroutine _panic 链表的最前面；
在循环中不断从当前 Goroutine 的 _defer 中链表获取 runtime._defer 并调用 runtime.reflectcall 运行延迟调用函数；
调用 runtime.fatalpanic 中止整个程序；

编译器将recover转换为runtime.gorecover

如果调用延迟执行函数时遇到了 gorecover 就会将 _panic.recovered 标记成 true 并返回 panic 的参数；
在这次调用结束之后，gopanic 会从 _defer 结构体中取出程序计数器 pc 和栈指针 sp 并调用 recovery 函数进行恢复程序
recovery 会根据传入的 pc 和 sp 跳转回 deferproc
编译器自动生成的代码会发现 deferproc 的返回值不为 0，这时会跳回 deferreturn 并恢复到正常的执行流程
如果没有遇到 gorecover 就会依次遍历所有的 _defer 结构，并在最后调用 fatalpanic 中止程序、打印 panic 的参数并返回错误码 2

make和new的区别

在编译期间的类型检查阶段，Go 语言就将代表 make 关键字的 OMAKE 节点根据参数类型的不同转换成了 OMAKESLICE、OMAKEMAP 和 OMAKECHAN 三种不同类型的节点，这些节点会调用不同的运行时函数来初始化相应的数据结构。
new 的作用是根据传入的类型分配一片内存空间并返回指向这片内存空间的指针

runtime.newobject 函数会是获取传入类型占用空间的大小，调用 runtime.mallocgc 在堆上申请一片内存空间并返回指向这片内存空间的指针：

func newobject(typ *_type) unsafe.Pointer {
    return mallocgc(typ.size, typ, true)
}

type Context interface {
    Deadline() (deadline time.Time, ok bool)
    Done() <-chan struct{}
    Err() error
    Value(key interface{}) interface{}
}

Deadline — 返回 context.Context 被取消的时间，也就是完成工作的截止日期；
Done — 返回一个 Channel，这个 Channel 会在当前工作完成或者上下文被取消之后关闭，多次调用 Done 方法会返回同一个 Channel；
Err — 返回 context.Context 结束的原因，它只会在 Done 返回的 Channel 被关闭时才会返回非空的值；

如果 context.Context 被取消，会返回 Canceled 错误；
如果 context.Context 超时，会返回 DeadlineExceeded 错误；

Value — 从 context.Context 中获取键对应的值，对于同一个上下文来说，多次调用 Value 并传入相同的 Key 会返回相同的结果，该方法可以用来传递请求特定的数据；

context 包中最常用的方法还是 context.Background、context.TODO，这两个私有变量都是通过 new(emptyCtx) 语句初始化的，它们是指向私有结构体 context.emptyCtx 的指针
取消信号
context.WithCancel 函数能够从 context.Context 中衍生出一个新的子上下文并返回用于取消该上下文的函数（CancelFunc）。一旦我们执行返回的取消函数，当前上下文以及它的子上下文都会被取消，所有的 Goroutine 都会同步收到这一取消信号。

func WithCancel(parent Context) (ctx Context, cancel CancelFunc) {
    c := newCancelCtx(parent)
    propagateCancel(parent, &c)
    return &c, func() { c.cancel(true, Canceled) }
}

context.propagateCancel 会构建父子上下文之间的关联，当父上下文被取消时，子上下文也会被取消：

func propagateCancel(parent Context, child canceler) {
    done := parent.Done()
    if done == nil {
        return // 父上下文不会触发取消信号
    }
    select {
    case <-done:
        child.cancel(false, parent.Err()) // 父上下文已经被取消
        return
    default:
    }

    if p, ok := parentCancelCtx(parent); ok {
        p.mu.Lock()
        if p.err != nil {
            child.cancel(false, p.err)
        } else {
            p.children[child] = struct{}{}
        }
        p.mu.Unlock()
    } else {
        go func() {
            select {
            case <-parent.Done():
                child.cancel(false, parent.Err())
            case <-child.Done():
            }
        }()
    }
}

当 parent.Done() == nil，也就是 parent 不会触发取消事件时，当前函数会直接返回；
当 child 的继承链包含可以取消的上下文时，会判断 parent 是否已经触发了取消信号；

如果已经被取消，child 会立刻被取消；
如果没有被取消，child 会被加入 parent 的 children 列表中，等待 parent 释放取消信号；

在默认情况下，运行一个新的 Goroutine 同时监听 parent.Done() 和child.Done() 两个 Channel
在 parent.Done() 关闭时调用 child.cancel 取消子上下文；

cancel

func (c *cancelCtx) cancel(removeFromParent bool, err error) {
    c.mu.Lock()
    if c.err != nil {
        c.mu.Unlock()
        return
    }
    c.err = err
    if c.done == nil {
        c.done = closedchan
    } else {
        close(c.done)
    }
    for child := range c.children {
        child.cancel(false, err)
    }
    c.children = nil
    c.mu.Unlock()

    if removeFromParent {
        removeChild(c.Context, c)
    }
}

传值

func WithValue(parent Context, key, val interface{}) Context {
    if key == nil {
        panic("nil key")
    }
    if !reflectlite.TypeOf(key).Comparable() {
        panic("key is not comparable")
    }
    return &valueCtx{parent, key, val}
}

type valueCtx struct {
    Context
    key, val interface{}
}

func (c *valueCtx) Value(key interface{}) interface{} {
    if c.key == key {
        return c.val
    }
    return c.Context.Value(key)
}

state 表示当前互斥锁的状态，而 sema 是用于控制锁状态的信号量。

type Mutex struct {
    state int32
    sema  uint32
}

最低三位分别表示 mutexLocked、mutexWoken 和 mutexStarving，剩下的位置用来表示当前有多少个 Goroutine 等待互斥锁的释放：

image.png

mutexLocked — 表示互斥锁的锁定状态；
mutexWoken — 表示从正常模式被从唤醒；
mutexStarving — 当前的互斥锁进入饥饿状态；
waitersCount — 当前互斥锁上等待的 Goroutine 个数；

自旋锁和互斥量

自旋锁(spin lock)与互斥量(mutex)的比较

自旋锁是一种非阻塞锁，也就是说，如果某线程需要获取自旋锁，但该锁已经被其他线程占用时，该线程不会被挂起，而是在不断的消耗CPU的时间，不停的试图获取自旋锁。
互斥量是阻塞锁，当某线程无法获取互斥量时，该线程会被直接挂起，该线程不再消耗CPU时间，当其他线程释放互斥量后，操作系统会激活那个被挂起的线程，让其投入运行。

两种锁适用于不同场景：

如果是多核处理器，如果预计线程等待锁的时间很短，短到比线程两次上下文切换时间要少的情况下，使用自旋锁是划算的。
如果是多核处理器，如果预计线程等待锁的时间较长，至少比两次线程上下文切换的时间要长，建议使用互斥量。
如果是单核处理器，一般建议不要使用自旋锁。因为，在同一时间只有一个线程是处在运行状态，那如果运行线程发现无法获取锁，只能等待解锁，但因为自身不挂起，所以那个获取到锁的线程没有办法进入运行状态，只能等到运行线程把操作系统分给它的时间片用完，才能有机会被调度。这种情况下使用自旋锁的代价很高。
如果加锁的代码经常被调用，但竞争情况很少发生时，应该优先考虑使用自旋锁，自旋锁的开销比较小，互斥量的开销较大

once

type Once struct {
    done uint32
    m    Mutex
}
func (o *Once) Do(f func()) {
    if atomic.LoadUint32(&o.done) == 0 {
        o.doSlow(f)
    }
}

func (o *Once) doSlow(f func()) {
    o.m.Lock()
    defer o.m.Unlock()
    if o.done == 0 {
        defer atomic.StoreUint32(&o.done, 1)
        f()
    }
}

Cond

func main() {
    c := sync.NewCond(&sync.Mutex{})
    for i := 0; i < 10; i++ {
        go listen(c)
    }
    time.Sleep(1*time.Second)
    go broadcast(c)

    ch := make(chan os.Signal, 1)
    signal.Notify(ch, os.Interrupt)
    <-ch
}

func broadcast(c *sync.Cond) {
    c.L.Lock()
    c.Broadcast()
    c.L.Unlock()
}

func listen(c *sync.Cond) {
    c.L.Lock()
    c.Wait()
    fmt.Println("listen")
    c.L.Unlock()
}

errorGroup

type Group struct {
    cancel func()

    wg sync.WaitGroup

    errOnce sync.Once
    err     error
}
func (g *Group) Go(f func() error) {
    g.wg.Add(1)

    go func() {
        defer g.wg.Done()

        if err := f(); err != nil {
            g.errOnce.Do(func() {
                g.err = err
                if g.cancel != nil {
                    g.cancel()
                }
            })
        }
    }()
}

func (g *Group) Wait() error {
    g.wg.Wait()
    if g.cancel != nil {
        g.cancel()
    }
    return g.err
}

SingleFlight

type service struct {
    requestGroup singleflight.Group
}

func (s *service) handleRequest(ctx context.Context, request Request) (Response, error) {
    v, err, _ := requestGroup.Do(request.Hash(), func() (interface{}, error) {
        rows, err := // select * from tables
        if err != nil {
            return nil, err
        }
        return rows, nil
    })
    if err != nil {
        return nil, err
    }
    return Response{
        rows: rows,
    }, nil
}
func (g *Group) Do(key string, fn func() (interface{}, error)) (v interface{}, err error, shared bool) {
    g.mu.Lock()
    if g.m == nil {
        g.m = make(map[string]*call)
    }
    if c, ok := g.m[key]; ok {
        c.dups++
        g.mu.Unlock()
        c.wg.Wait()
        return c.val, c.err, true
    }
    c := new(call)
    c.wg.Add(1)
    g.m[key] = c
    g.mu.Unlock()

    g.doCall(c, key, fn)
    return c.val, c.err, c.dups > 0
}
func (g *Group) DoChan(key string, fn func() (interface{}, error)) <-chan Result {
    ch := make(chan Result, 1)
    g.mu.Lock()
    if g.m == nil {
        g.m = make(map[string]*call)
    }
    if c, ok := g.m[key]; ok {
        c.dups++
        c.chans = append(c.chans, ch)
        g.mu.Unlock()
        return ch
    }
    c := &call{chans: []chan<- Result{ch}}
    c.wg.Add(1)
    g.m[key] = c
    g.mu.Unlock()

    go g.doCall(c, key, fn)

    return ch
}

Go 1.10 将全局的四叉堆分割成了 64 个更小的四叉堆

var timers struct {
    lock         mutex
    gp           *g
    created      bool
    sleeping     bool
    rescheduling bool
    sleepUntil   int64
    waitnote     note
    t            []*timer
}

这个结构体中的字段 t 就是最小四叉堆
在最新版本的实现中，计时器桶已经被移除⁷，所有的计时器都以最小四叉堆的形式存储在处理器 runtime.p 中。

image.png

type p struct {
    ...
    timersLock mutex
    timers []*timer

    numTimers     uint32
    adjustTimers  uint32
    deletedTimers uint32
    ...
}

timers — 存储计时器的最小四叉堆；

type timer struct {
    pp puintptr

    when     int64
    period   int64
    f        func(interface{}, uintptr)
    arg      interface{}
    seq      uintptr
    nextwhen int64
    status   uint32
}

f — 每当计时器被唤醒时都会调用的函数

Go 语言会在两个模块触发计时器，运行计时器中保存的函数：

调度器调度时会检查处理器中的计时器是否准备就绪；runtime.checkTimers 是调度器用来运行处理器中计时器的函数

系统监控会检查是否有未执行的到期计时器；如果超过 10ms 的时间没有轮询，调用 runtime.netpoll 轮询网络；

channel的实现

Channel 在运行时的内部表示是 runtime.hchan，该结构体中包含了一个用于保护成员变量的互斥锁，从某种程度上说，Channel 是一个用于同步和通信的有锁队列

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
}

qcount — Channel 中的元素个数
dataqsiz — Channel 中的循环队列的长度
buf — Channel 的缓冲区数据指针
sendx — Channel 的发送操作处理到的位置
recvx — Channel 的接收操作处理到的位置
elemsize 和 elemtype 分别表示当前 Channel 能够收发的元素类型和大小
sendq 和 recvq 存储了当前 Channel 由于缓冲区空间不足而阻塞的 Goroutine 列表，这些等待队列使用双向链表 runtime.waitq 表示，链表中所有的元素都是 runtime.sudog 结构：

type waitq struct {
    first *sudog
    last  *sudog
}

发送数据

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {
    lock(&c.lock)

    if c.closed != 0 {
        unlock(&c.lock)
        panic(plainError("send on closed channel"))
    }

如果当前 Channel 的 recvq 上存在已经被阻塞的 Goroutine，那么会直接将数据发送给当前的 Goroutine 并将其设置成下一个运行的 Goroutine；
如果 Channel 存在缓冲区并且其中还有空闲的容量，我们就会直接将数据直接存储到当前缓冲区 sendx 所在的位置上；
如果不满足上面的两种情况，就会创建一个 runtime.sudog 结构并将其加入 Channel 的 sendq 队列中，当前 Goroutine 也会陷入阻塞等待其他的协程从 Channel 接收数据；

发送数据会出发Goroutine调度的时机

发送数据时发现 Channel 上存在等待接收数据的 Goroutine，立刻设置处理器的 runnext 属性，但是并不会立刻触发调度
发送数据时并没有找到接收方并且缓冲区已经满了，这时就会将自己加入 Channel 的 sendq 队列并调用 runtime.goparkunlock 触发 Goroutine 的调度让出处理器的使用权

接收数据

如果 Channel 为空，那么就会直接调用 runtime.gopark 挂起当前 Goroutine；
如果 Channel 已经关闭并且缓冲区没有任何数据，runtime.chanrecv 函数会直接返回；
如果 Channel 的 sendq 队列中存在挂起的 Goroutine，就会将 recvx 索引所在的数据拷贝到接收变量所在的内存空间上并将 sendq 队列中 Goroutine 的数据拷贝到缓冲区；
如果 Channel 的缓冲区中包含数据就会直接读取 recvx 索引对应的数据；
在默认情况下会挂起当前的 Goroutine，将 runtime.sudog 结构加入 recvq 队列并陷入休眠等待调度器的唤醒；

从 Channel 接收数据时，会触发 Goroutine 调度的两个时机：

当 Channel 为空时；
当缓冲区中不存在数据并且也不存在数据的发送者时；

关闭channel
将 recvq 和 sendq 两个队列中的数据加入到 Goroutine 列表 gList 中，与此同时该函数会清除所有 sudog 上未被处理的元素
该函数在最后会为所有被阻塞的 Goroutine 调用 runtime.goready 触发调度

调度

image.png

struct P {
    Lock;

    uint32  status;
    P*  link;
    uint32  tick;
    M*  m;
    MCache* mcache;

    G** runq;
    int32   runqhead;
    int32   runqtail;
    int32   runqsize;

    G*  gfree;
    int32   gfreecnt;
};

处理器持有一个由可运行的 Goroutine 组成的运行队列 runq，还反向持有一个线程。调度器在调度时会从处理器的队列中选择队列头的 Goroutine 放到线程 M 上执行。如下所示的图片展示了 Go 语言中的线程 M、处理器 P 和 Goroutine 的关系。
基于工作窃取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器管理，不同的处理器通过工作窃取对任务进行再分配实现任务的平衡，也能提升调度器和 Go 语言程序的整体性能

抢占式调度
抢占式多任务处理（Preemption）是计算机操作系统中，一种实现多任务处理（multi task）的方式，相对于协作式多任务处理而言。协作式环境下，下一个进程被调度的前提是当前进程主动放弃时间片；抢占式环境下，操作系统完全决定进程调度方案，操作系统可以剥夺耗时长的进程的时间片，提供给其它进程。

每个任务赋予唯一的一个优先级（有些操作系统可以动态地改变任务的优先级）；
假如有几个任务同时处于就绪状态，优先级最高的那个将被运行；
只要有一个优先级更高的任务就绪，它就可以中断当前优先级较低的任务的执行；

基于协作的抢占式调度的工作原理：
编译器会在调用函数前插入 runtime.morestack
Go 语言运行时会在垃圾回收暂停程序、系统监控发现 Goroutine 运行超过 10ms 时发出抢占请求 StackPreempt
当发生函数调用时，可能会执行编译器插入的 runtime.morestack 函数，它调用的 runtime.newstack 会检查 Goroutine 的 stackguard0 字段是否为 StackPreempt；
如果 stackguard0 是 StackPreempt，就会触发抢占让出当前线程；
基于信号的抢占式调度
SIGURG信号
STW 和栈扫描是一个可以抢占的安全点（Safe-points），所以 Go 语言会在这里先加入抢占功能⁸。基于信号的抢占式调度只解决了垃圾回收和栈扫描时存在的问题
非均匀内存访问（Non-uniform memory access，NUMA）调度器
G — 表示 Goroutine，它是一个待执行的任务；
M — 表示操作系统的线程，它由操作系统的调度器调度和管理；
P — 表示处理器，它可以被看做运行在线程上的本地调度器；

type g struct {
    _panic       *_panic // 最内侧的 panic 结构体
    _defer       *_defer // 最内侧的延迟函数结构体
    m              *m
    sched          gobuf
    atomicstatus   uint32
    goid           int64
}

m — 当前 Goroutine 占用的线程，可能为空；
atomicstatus — Goroutine 的状态；
sched — 存储 Goroutine 的调度相关的数据；
goid — Goroutine 的 ID，该字段对开发者不可见，Go 团队认为引入 ID 会让部分 Goroutine 变得更特殊，从而限制语言的并发能力¹⁰；

Goroutine的状态

等待中：Goroutine 正在等待某些条件满足，例如：系统调用结束等，包括 _Gwaiting、_Gsyscall 和 _Gpreempted 几个状态；
可运行：Goroutine 已经准备就绪，可以在线程运行，如果当前程序中有非常多的 Goroutine，每个 Goroutine 就可能会等待更多的时间，即 _Grunnable；
运行中：Goroutine 正在某个线程上运行，即 _Grunning；

M
Go 语言并发模型中的 M 是操作系统线程。调度器最多可以创建 10000 个线程，但是其中大多数的线程都不会执行用户代码（可能陷入系统调用），最多只会有 GOMAXPROCS 个活跃线程能够正常运行。
在大多数情况下，我们都会使用 Go 的默认设置，也就是线程数等于 CPU 个数，在这种情况下不会触发操作系统的线程调度和上下文切换，所有的调度都会发生在用户态，由 Go 语言调度器触发，能够减少非常多的额外开销。

type m struct {
    g0   *g 
    curg *g
    ...
}

其中 g0 是持有调度栈的 Goroutine，curg 是在当前线程上运行的用户 Goroutine，这也是操作系统线程唯一关心的两个 Goroutine。
g0 是一个运行时中比较特殊的 Goroutine，它会深度参与运行时的调度过程，包括 Goroutine 的创建、大内存分配和 CGO 函数的执行。

P
调度器中的处理器 P 是线程和 Goroutine 的中间层，它能提供线程需要的上下文环境，也会负责调度线程上的等待队列，通过处理器 P 的调度，每一个内核线程都能够执行多个 Goroutine，它能在 Goroutine 进行一些 I/O 操作时及时切换，提高线程的利用率。

因为调度器在启动时就会创建 GOMAXPROCS 个处理器，所以 Go 语言程序的处理器数量一定会等于 GOMAXPROCS，这些处理器会绑定到不同的内核线程上并利用线程的计算资源运行 Goroutine。

type p struct {
    m           muintptr

    runqhead uint32
    runqtail uint32
    runq     [256]guintptr
    runnext guintptr
    ...
}

反向存储的线程维护着线程与处理器之间的关系，而 runhead、runqtail 和 runq 三个字段表示处理器持有的运行队列，其中存储着待执行的 Goroutine 列表，runnext 中是线程下一个需要执行的 Goroutine。

调度器启动
我们从环境变量 GOMAXPROCS 获取了程序能够同时运行的最大处理器数之后就会调用 runtime.procresize 更新程序中处理器的数量，在这时整个程序不会执行任何用户 Goroutine，调度器也会进入锁定状态，
调用 runtime.procresize 就是调度器启动的最后一步，在这一步过后调度器会完成相应数量处理器的启动，等待用户创建运行新的 Goroutine 并为 Goroutine 调度处理器资源。
编译器会将所有的 go 关键字被转换成 runtime.newproc 函数
先从处理器的 gFree 列表或者调度器的 sched.gFree 列表中查找空闲的 Goroutine，如果不存在空闲的 Goroutine，就会通过 runtime.malg 函数创建一个栈大小足够的新结构体，并将当前结构体追加到全局的 Goroutine 列表 allgs 中。
runtime.newproc1 会设置新的 Goroutine 结构体的参数，包括栈指针、程序计数器并更新其状态到 _Grunnable：
在最后，该函数会将初始化好的 Goroutine 加入处理器的运行队列并在满足条件时调用 runtime.wakep 函数唤醒新的处理执行 Goroutine
运行队列
runtime.runqput 函数会将新创建的 Goroutine 运行队列上，这既可能是全局的运行队列，也可能是处理器本地的运行队列。
简单总结一下，Go 语言中有两个运行队列，其中一个是处理器本地的运行队列，另一个是调度器持有的全局运行队列，只有在本地运行队列没有剩余空间时才会使用全局队列。
调度循环
runtime.schedule 函数的会从不同地方查找待执行的 Goroutine：

为了保证公平，当全局运行队列中有待执行的 Goroutine 时，通过 schedtick 保证有一定几率会从全局的运行队列中查找对应的 Goroutine；
从处理器本地的运行队列中查找待执行的 Goroutine；
如果前两种方法都没有找到 Goroutine，就会通过 runtime.findrunnable 进行阻塞地查找 Goroutine

runtime.findrunnable通过以下的过程获取可运行的 Goroutine：

从本地运行队列、全局运行队列中查找；
从网络轮询器中查找是否有 Goroutine 等待运行；
通过 runtime.runqsteal 函数尝试从其他随机的处理器中窃取待运行的 Goroutine，在该过程中还可能窃取处理器中的计时器；

总而言之，当前函数一定会返回一个可执行的 Goroutine，如果当前不存在就会阻塞等待。

接下来由 runtime.execute 函数执行获取的 Goroutine，做好准备工作后，它会通过 runtime.gogo 将 Goroutine 调度到当前线程上。
最终在当前线程的 g0 的栈上调用 runtime.goexit0 函数，该函数会将 Goroutine 转换会 _Gdead 状态、清理其中的字段、移除 Goroutine 和线程的关联并调用 runtime.gfput 重新加入处理器的 Goroutine 空闲列表 gFree：
在最后 runtime.goexit0 函数会重新调用 runtime.schedule 触发新的 Goroutine 调度，我们可以认为调度循环永远都不会返回。

触发调度

调度器的 runtime.schedule 函数重新选择 Goroutine 在线程上执行，所以我们只要找到该函数的调用方就能找到所有触发调度的时间点

运行时还会在线程启动 runtime.mstart 和 Goroutine 执行结束 runtime.goexit0 触发调度。我们在这里会重点介绍运行时触发调度的几个路径：

runtime.goexit0 触发调度。我们在这里会重点介绍运行时触发调度的几个路径：

主动挂起 — runtime.gopark -> runtime.park_m
系统调用 — runtime.exitsyscall -> runtime.exitsyscall0
协作式调度 — runtime.Gosched -> runtime.gosched_m -> runtime.goschedImpl
系统监控 — runtime.sysmon -> runtime.retake -> runtime.preemptone

调度时间点不是直接将线程的运行权交给其他任务，而是通过调度器的 runtime.schedule 重新调度。

主动挂起
runtime.gopark 是触发调度最常见的方法，该函数会将当前 Goroutine 暂停，被暂停的任务不会放回运行队列
该函数会将当前 Goroutine 的状态从 _Grunning 切换至 _Gwaiting，调用 runtime.dropg 移除线程和 Gorooutine 之间的关联，在这之后就可以调用 runtime.schedule 触发新一轮的调度了。

当 Goroutine 等待的特定条件满足后，运行时会调用 runtime.goready 将因为调用 runtime.gopark 而陷入休眠的 Goroutine 唤醒。
runtime.ready 会将准备就绪的 Goroutine 的状态切换至 _Grunnable 并将其加入处理器的运行队列中，等待调度器的调度。

系统调用
Go 语言基于协作式和信号的两种抢占式调度，在这里我们介绍 Go 语言中的协作式调度。runtime.Gosched 就是主动让出处理器，允许其他 Goroutine 运行。该函数无法挂起 Goroutine，调度器会自动调度当前 Goroutine：
最终在 g0 的栈上调用 runtime.goschedImpl 函数，运行时会更新 Goroutine 的状态到 _Grunnable，让出当前的处理器并将 Goroutine 重新放回全局队列，在最后，该函数会调用 runtime.schedule 重新触发调度
Go 语言的运行时会通过调度器改变线程的所有权，它也提供了 runtime.LockOSThread 和 runtime.UnlockOSThread 让我们有能力绑定 Goroutine 和线程完成一些比较特殊的操作
runtime.LockOSThread 会通过如下所示的代码绑定 Goroutine 和当前线程：
当 Goroutine 完成了特定的操作之后，就会调用以下函数 runtime.UnlockOSThread 分离 Goroutine 和线程：

IO多路复用
select和poll的区别

select
监听能力有限 — 最多只能监听 1024 个文件描述符；
内存拷贝开销大 — 需要维护一个较大的数据结构存储文件描述符，该结构需要拷贝到内核中；
时间复杂度 𝑂(𝑛) — 返回准备就绪的事件个数后，需要遍历所有的文件描述符；

操作系统中还提供了一个比较相似的 poll 函数，它使用链表存储文件描述符，摆脱了 1024 的数量上限。
epoll、kqueue、solaries 等多路复用模块都要实现以下五个函数，这五个函数构成一个虚拟的接口：

func netpollinit()
func netpollopen(fd uintptr, pd *pollDesc) int32
func netpoll(delta int64) gList
func netpollBreak()
func netpollIsPollDescriptor(fd uintptr) bool

runtime.netpollinit — 初始化网络轮询器，通过 sync.Once 和 netpollInited 变量保证函数只会调用一次；
runtime.netpollopen — 监听文件描述符上的边缘触发事件，创建事件并加入监听；
runtime.netpoll — 轮询网络并返回一组已经准备就绪的 Goroutine，传入的参数会决定它的行为³；
* 如果参数小于 0，无限期等待文件描述符就绪；
* 如果参数等于 0，非阻塞地轮询网络；
* 如果参数大于 0，阻塞特定时间轮询网络；
runtime.netpollBreak — 唤醒网络轮询器，例如：计时器向前修改时间时会通过该函数中断网络轮询器⁴；
runtime.netpollIsPollDescriptor — 判断文件描述符是否被轮询器使用；

操作系统中 I/O 多路复用函数会监控文件描述符的可读或者可写，而 Go 语言网络轮询器会监听 runtime.pollDesc 结构体的状态，该结构会封装操作系统的文件描述符：

type pollDesc struct {
    link *pollDesc

    lock    mutex
    fd      uintptr
    ...
    rseq    uintptr
    rg      uintptr
    rt      timer
    rd      int64
    wseq    uintptr
    wg      uintptr
    wt      timer
    wd      int64
}

runtime.pollDesc 结构体会使用 link 字段串联成一个链表存储在 runtime.pollCache 中

type pollCache struct {
    lock  mutex
    first *pollDesc
}

runtime.pollCache 是运行时包中的全局变量，该结构体中包含一个用于保护轮询数据的互斥锁和链表头：

image.png

func (c *pollCache) alloc() *pollDesc {
    lock(&c.lock)
    if c.first == nil {
        const pdSize = unsafe.Sizeof(pollDesc{})
        n := pollBlockSize / pdSize
        if n == 0 {
            n = 1
        }
        mem := persistentalloc(n*pdSize, 0, &memstats.other_sys)
        for i := uintptr(0); i < n; i++ {
            pd := (*pollDesc)(add(mem, i*pdSize))
            pd.link = c.first
            c.first = pd
        }
    }
    pd := c.first
    c.first = pd.link
    unlock(&c.lock)
    return pd
}

每次调用该结构体都会返回链表头还没有被使用的 runtime.pollDesc，这种批量初始化的做法能够增加网络轮询器的吞吐量。Go 语言运行时会调用 runtime.pollCache.free 方法释放已经用完的 runtime.pollDesc 结构，它会直接将结构体插入链表的最前面：

func (c *pollCache) free(pd *pollDesc) {
    lock(&c.lock)
    pd.link = c.first
    c.first = pd
    unlock(&c.lock)
}

因为文件 I/O、网络 I/O 以及计时器都依赖网络轮询器，所以 Go 语言会通过以下两条不同路径初始化网络轮询器：
网络轮询器的初始化会使用 runtime.poll_runtime_pollServerInit 和 runtime.netpollGenericInit 两个函数：
runtime.netpollGenericInit 会调用平台上特定实现的 runtime.netpollinit 函数，即 Linux 上的 epoll，它主要做了以下几件事情：

是调用 epollcreate1 创建一个新的 epoll 文件描述符，这个文件描述符会在整个程序的生命周期中使用；
通过 runtime.nonblockingPipe 创建一个用于通信的管道；
使用 epollctl 将用于读取数据的文件描述符打包成 epollevent 事件加入监听；
初始化的管道为我们提供了中断多路复用等待文件描述符中事件的方法，runtime.netpollBreak 函数会向管道中写入数据唤醒 epoll：
因为目前的计时器由网络轮询器管理和触发，它能够让网络轮询器立刻返回并让运行时检查是否有需要触发的计时器。

轮询事件
调用 internal/poll.pollDesc.init 初始化文件描述符时不止会初始化网络轮询器，还会通过 runtime.poll_runtime_pollOpen 函数重置轮询信息 runtime.pollDesc 并调用 runtime.netpollopen 初始化轮询事件：
runtime.netpollopen 的实现非常简单，它会调用 epollctl 向全局的轮询文件描述符 epfd 中加入新的轮询事件监听文件描述符的可读和可写状态：
事件循环

等待事件
runtime.netpollblock 是 Goroutine 等待 I/O 事件的关键函数，它会使用运行时提供的 runtime.gopark 让出当前线程，将 Goroutine 转换到休眠状态并等待运行时的唤醒。
轮询等待
Go 语言的运行时会在调度或者系统监控中调用 runtime.netpoll 轮询网络，该函数的执行过程可以分成以下几个部分：

根据传入的 delay 计算 epoll 系统调用需要等待的时间；
调用 epollwait 等待可读或者可写事件的发生；
在循环中依次处理 epollevent 事件；
系统监控sysmon
系统监控在每次循环开始时都会通过 usleep 挂起当前线程，该函数的参数是微秒，运行时会遵循以下的规则决定休眠时间：

初始的休眠时间是 20μs；
最长的休眠时间是 10ms；
当系统监控在 50 个循环中都没有唤醒 Goroutine 时，休眠时间在每个循环都会倍增；
当程序趋于稳定之后，系统监控的触发时间就会稳定在 10ms。它除了会检查死锁之外，还会在循环中完成以下的工作：

运行计时器 — 获取下一个需要被触发的计时器；
轮询网络 — 获取需要处理的到期文件描述符；
抢占处理器 — 抢占运行时间较长的或者处于系统调用的 Goroutine；
垃圾回收 — 在满足条件时触发垃圾收集回收内存；

如果上一次轮询网络已经过去了 10ms，那么系统监控还会在循环中轮询网络，检查是否有待执行的文件描述符
上述函数会非阻塞地调用 runtime.netpoll 检查待执行的文件描述符并通过 runtime.injectglist 将所有处于就绪状态的 Goroutine 加入全局运行队列中
该函数会将所有 Goroutine 的状态从 _Gwaiting 切换至 _Grunnable 并加入全局运行队列等待运行，如果当前程序中存在空闲的处理器，就会通过 runtime.startm 函数启动线程来执行这些任务。
抢占处理器

当处理器处于 _Prunning 或者 _Psyscall 状态时，如果上一次触发调度的时间已经过去了 10ms，我们就会通过 runtime.preemptone 抢占当前处理器；
当处理器处于 _Psyscall 状态时，在满足以下两种情况下会调用 runtime.handoffp 让出处理器的使用权：
1. 当处理器的运行队列不为空或者不存在空闲处理器时²；
2. 当系统调用时间超过了 10ms 时³；
  系统监控通过在循环中抢占处理器来避免同一个 Goroutine 占用线程太长时间造成饥饿问题。

如果需要触发垃圾回收，我们会将用于垃圾回收的 Goroutine 加入全局队列，让调度器选择合适的处理器去执行。

内存分配，tcmalloc

线性内存分配
C 和 C++ 等需要直接对外暴露指针的语言就无法使用该策略
空闲链表分配
空闲链表分配器（Free-List Allocator）可以重用已经被释放的内存，它在内部会维护一个类似链表的数据结构。当用户程序申请内存时，空闲链表分配器会依次遍历空闲的内存块，找到足够大的内存，然后申请新的资源并修改链表
因为不同的内存块以链表的方式连接，所以使用这种方式分配内存的分配器可以重新利用回收的资源，但是因为分配内存时需要遍历链表，所以它的时间复杂度就是 𝑂(𝑛)。空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的就是以下四种方式：

首次适应（First-Fit）— 从链表头开始遍历，选择第一个大小大于申请内存的内存块；
循环首次适应（Next-Fit）— 从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；
最优适应（Best-Fit）— 从链表头遍历整个链表，选择最合适的内存块；
隔离适应（Segregated-Fit）— 将内存分割成多个链表，每个链表中的内存块大小相同，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块；

image.png

如上图所示，该策略会将内存分割成由 4、8、16、32 字节的内存块组成的链表，当我们向内存分配器申请 8 字节的内存时，我们会在上图中的第二个链表找到空闲的内存块并返回。隔离适应的分配策略减少了需要遍历的内存块数量，提高了内存分配的效率。

分级分配

线程缓存分配（Thread-Caching Malloc，TCMalloc）是用于分配内存的的机制，它比 glibc 中的 malloc 函数还要快很多²。Go 语言的内存分配器就借鉴了 TCMalloc 的设计实现高速的内存分配，它的核心理念是使用多级缓存根据将对象根据大小分类，并按照类别实施不同的分配策略。

对象大小

Go 语言的内存分配器会根据申请分配的内存大小选择不同的处理逻辑，运行时根据对象的大小将对象分成微对象、小对象和大对象三种：

类别	大小
微对象	(0, 16B)
小对象	[16B, 32KB]
大对象	(32KB, +∞)

多级缓存

内存分配器不仅会区别对待大小不同的对象，还会将内存分成不同的级别分别管理，TCMalloc 和 Go 运行时分配器都会引入线程缓存（Thread Cache）、中心缓存（Central Cache）和页堆（Page Heap）三个组件分级管理内存：

image.png

线程缓存属于每一个独立的线程，它能够满足线程上绝大多数的内存分配需求，因为不涉及多线程，所以也不需要使用互斥锁来保护内存，这能够减少锁竞争带来的性能损耗。当线程缓存不能满足需求时，就会使用中心缓存作为补充解决小对象的内存分配问题；在遇到 32KB 以上的对象时，内存分配器就会选择页堆直接分配大量的内存。

这种多层级的内存分配设计与计算机操作系统中的多级缓存也有些类似，因为多数的对象都是小对象，我们可以通过线程缓存和中心缓存提供足够的内存空间，发现资源不足时就从上一级组件中获取更多的内存资源。

虚拟内存布局
线性内存
Go 语言程序的 1.10 版本在启动时会初始化整片虚拟内存区域，如下所示的三个区域 spans、bitmap 和 arena 分别预留了 512MB、16GB 以及 512GB 的内存空间，这些内存并不是真正存在的物理内存，而是虚拟内存：

image.png

spans 区域存储了指向内存管理单元 runtime.mspan 的指针，每个内存单元会管理几页的内存空间，每页大小为 8KB；
bitmap 用于标识 arena 区域中的那些地址保存了对象，位图中的每个字节都会表示堆区中的 32 字节是否包含空闲；
arena 区域是真正的堆区，运行时会将 8KB 看做一页，这些内存页中存储了所有在堆上初始化的对象；

稀疏内存

image.png

稀疏内存是 Go 语言在 1.11 中提出的方案，使用稀疏的内存布局不仅能移除堆大小的上限⁵，还能解决 C 和 Go 混合使用时的地址空间冲突问题⁶。不过因为基于稀疏内存的内存管理失去了内存的连续性这一假设，这也使内存管理变得更加复杂：
内存管理组件
所有的 Go 语言程序都会在启动时初始化如上图所示的内存布局，每一个处理器都会被分配一个线程缓存 runtime.mcache 用于处理微对象和小对象的分配，它们会持有内存管理单元 runtime.mspan。
每个类型的内存管理单元都会管理特定大小的对象，当内存管理单元中不存在空闲对象时，它们会从 runtime.mheap 持有的 134 个中心缓存 runtime.mcentral 中获取新的内存单元，中心缓存属于全局的堆结构体 runtime.mheap，它会从操作系统中申请内存。
内存管理单元
runtime.mspan 是 Go 语言内存管理的基本单元，该结构体中包含 next 和 prev 两个字段，它们分别指向了前一个和后一个 runtime.mspan：

type mspan struct {
    next *mspan
    prev *mspan
    ...
}

串联后的上述结构体会构成如下双向链表，运行时会使用 runtime.mSpanList 存储双向链表的头结点和尾节点并在线程缓存以及中心缓存中使用。

跨度类

type mspan struct {
    ...
    spanclass   spanClass
    ...
}

Go 语言的内存管理模块中一共包含 67 种跨度类，每一个跨度类都会存储特定大小的对象并且包含特定数量的页数以及对象

线程缓存
runtime.mcache 是 Go 语言中的线程缓存，它会与线程上的处理器一一绑定，主要用来缓存用户程序申请的微小对象。每一个线程缓存都持有 67 * 2 个 runtime.mspan，这些内存管理单元都存储在结构体的 alloc 字段中：

image.png

线程缓存在刚刚被初始化时是不包含 runtime.mspan 的，只有当用户程序申请内存时才会从上一级组件获取新的 runtime.mspan 满足内存分配的需求。

func (c *mcache) refill(spc spanClass) {
    s := c.alloc[spc]
    s = mheap_.central[spc].mcentral.cacheSpan()
    c.alloc[spc] = s
}

如上述代码所示，该函数会从中心缓存中申请新的 runtime.mspan 存储到线程缓存中，这也是向线程缓存中插入内存管理单元的唯一方法。

中心缓存
runtime.mcentral 是内存分配器的中心缓存，与线程缓存不同，访问中心缓存中的内存管理单元需要使用互斥锁：

type mcentral struct {
    lock      mutex
    spanclass spanClass
    nonempty  mSpanList
    empty     mSpanList
    nmalloc uint64
}

每一个中心缓存都会管理某个跨度类的内存管理单元，它会同时持有两个 runtime.mSpanList，分别存储包含空闲对象的列表和不包含空闲对象的链表：

image.png

该结构体在初始化时，两个链表都不包含任何内存，程序运行时会扩容结构体持有的两个链表，nmalloc 字段也记录了该结构体中分配的对象个数。
如果 runtime.mcentral 在两个链表中都没有找到可用的内存单元，它会调用 runtime.mcentral.grow 触发扩容操作从堆中申请新的内存：

页堆
runtime.mheap 是内存分配的核心结构体，Go 语言程序只会存在一个全局的结构，而堆上初始化的所有对象都由该结构体统一管理，该结构体中包含两组非常重要的字段，其中一个是全局的中心缓存列表 central，另一个是管理堆区内存区域的 arenas 以及相关字段。

image.png
扩容
runtime.mheap.grow 方法会向操作系统申请更多的内存空间，传入的页数经过对齐可以得到期望的内存大小，我们可以将该方法的执行过程分成以下几个部分：

通过传入的页数获取期望分配的内存空间大小以及内存的基地址；
如果 arena 区域没有足够的空间，调用 runtime.mheap.sysAlloc 从操作系统中申请更多的内存；
扩容 runtime.mheap 持有的 arena 区域并更新页分配器的元信息；
在某些场景下，调用 runtime.pageAlloc.scavenge 回收不再使用的空闲内存页；

内存分配
堆上所有的对象都会通过调用 runtime.newobject 函数分配内存，该函数会调用 runtime.mallocgc 分配指定大小的内存空间，这也是用户程序向堆上申请内存空间的必经函数：

微对象 (0, 16B) — 先使用微型分配器，再依次尝试线程缓存、中心缓存和堆分配内存；
小对象 [16B, 32KB] — 依次尝试使用线程缓存、中心缓存和堆分配内存；
大对象 (32KB, +∞) — 直接在堆上分配内存；

微对象
Go 语言运行时将小于 16 字节的对象划分为微对象，它会使用线程缓存上的微分配器提高微对象分配的性能，我们主要使用它来分配较小的字符串以及逃逸的临时变量。微分配器可以将多个较小的内存分配请求合入同一个内存块中，只有当内存块中的所有对象都需要被回收时，整片内存才可能被回收。
当内存块中不包含空闲的内存时，下面的这段代码会从先线程缓存找到跨度类对应的内存管理单元 runtime.mspan，调用 runtime.nextFreeFast 获取空闲的内存；当不存在空闲内存时，我们会调用 runtime.mcache.nextFree 从中心缓存或者页堆中获取可分配的内存块：
小对象

确定分配对象的大小以及跨度类 runtime.spanClass；
从线程缓存、中心缓存或者堆中获取内存管理单元并从内存管理单元找到空闲的内存空间；
调用 runtime.memclrNoHeapPointers 清空空闲内存中的所有数据；

大对象
运行时对于大于 32KB 的大对象会单独处理，我们不会从线程缓存或者中心缓存中获取内存管理单元，而是直接在系统的栈中调用 runtime.largeAlloc 函数分配大片的内存：

垃圾回收

三色标记算法
三色标记算法将程序中的对象分成白色、黑色和灰色三类⁴：

垃圾收集的根对象会被标记成灰色
白色对象 — 潜在的垃圾，其内存可能会被垃圾收集器回收；
黑色对象 — 活跃的对象，包括不存在任何引用外部指针的对象以及从根对象可达的对象；
灰色对象 — 活跃的对象，因为存在指向白色对象的外部指针，垃圾收集器会扫描这些对象的子对象；

当三色的标记清除的标记阶段结束之后，应用程序的堆中就不存在任何的灰色对象，我们只能看到黑色的存活对象以及白色的垃圾对象，垃圾收集器可以回收这些白色的垃圾

从灰色对象的集合中选择一个灰色对象并将其标记成黑色；
将黑色对象指向的所有对象都标记成灰色，保证该对象和被该对象引用的对象都不会被回收；
重复上述两个步骤直到对象图中不存在灰色对象；
屏障技术
内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前的多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证代码对内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作⁶。
三色不变性

强三色不变性 — 黑色对象不会指向白色对象，只会指向灰色对象或者黑色对象；

弱三色不变性 — 黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径⁷；

插入写屏障
Dijkstra 在 1978 年提出了插入写屏障，通过如下所示的写屏障，用户程序和垃圾收集器可以在交替工作的情况下保证程序执行的正确性：

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

上述插入写屏障的伪代码非常好理解，每当我们执行类似 *slot = ptr 的表达式时，我们会执行上述写屏障通过 shade 函数尝试改变指针的颜色。如果 ptr 指针是白色的，那么该函数会将该对象设置成灰色，其他情况则保持不变。

删除写屏障
该算法会使用如下所示的写屏障保证增量或者并发执行垃圾收集时程序的正确性：

writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

上述代码会在老对象的引用被删除时，将白色的老对象涂成灰色，这样删除写屏障就可以保证弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用。

增量收集器
增量式（Incremental）的垃圾收集是减少程序最长暂停时间的一种方案，它可以将原本时间较长的暂停时间切分成多个更小的 GC 时间片，虽然从垃圾收集开始到结束的时间更长了，但是这也减少了应用程序暂停的最大时间：
并发收集器
并发（Concurrent）的垃圾收集不仅能够减少程序的最长暂停时间，还能减少整个垃圾收集阶段的时间，通过开启读写屏障、利用多核优势与用户程序并行执行，并发垃圾收集器确实能够减少垃圾收集对应用程序的影响：

Go 语言的并发垃圾收集器会在扫描对象之前暂停程序做一些标记对象的准备工作，其中包括启动后台标记的垃圾收集器以及开启写屏障，如果在后台执行的垃圾收集器不够快，应用程序申请内存的速度超过预期，运行时就会让申请内存的应用程序辅助完成垃圾收集的扫描阶段，在标记和标记终止阶段结束之后就会进入异步的清理阶段，将不用的内存增量回收。

回收堆目标
STW 的垃圾收集器虽然需要暂停程序，但是它能够有效地控制堆内存的大小，Go 语言运行时的默认配置会在堆内存达到上一次垃圾收集的 2 倍时，触发新一轮的垃圾收集，这个行为可以通过环境变量 GOGC 调整，在默认情况下它的值为 100，即增长 100% 的堆内存才会触发 GC。

image.png

Go 语言 v1.5 引入并发垃圾收集器的同时使用垃圾收集调步（Pacing）算法计算触发的垃圾收集的最佳时间，确保触发的时间既不会浪费计算资源，也不会超出预期的堆大小。如上图所示，其中黑色的部分是上一次垃圾收集后标记的堆大小，绿色部分是上次垃圾收集结束后新分配的内存，因为我们使用并发垃圾收集，所以黄色的部分就是在垃圾收集期间分配的内存，最后的红色部分是垃圾收集结束时与目标的差值，我们希望尽可能减少红色部分内存，降低垃圾收集带来的额外开销以及程序的暂停时间。

-w1183

清理终止阶段；
暂停程序，所有的处理器在这时会进入安全点（Safe point）；
如果当前垃圾收集循环是强制触发的，我们还需要处理还未被清理的内存管理单元；
标记阶段；
将状态切换至 _GCmark、开启写屏障、用户程序协助（Mutator Assiste）并将根对象入队；
恢复执行程序，标记进程和用于协助的用户程序会开始并发标记内存中的对象，写屏障会将被覆盖的指针和新指针都标记成灰色，而所有新创建的对象都会被直接标记成黑色；
开始扫描根对象，包括所有 Goroutine 的栈、全局对象以及不在堆中的运行时数据结构，扫描 Goroutine 栈期间会暂停当前处理器；
依次处理灰色队列中的对象，将对象标记成黑色并将它们指向的对象标记成灰色；
使用分布式的终止算法检查剩余的工作，发现标记阶段完成后进入标记终止阶段；
标记终止阶段；
暂停程序、将状态切换至 _GCmarktermination 并关闭辅助标记的用户程序；
清理处理器上的线程缓存；
清理阶段；
将状态切换至 _GCoff 开始清理阶段，初始化清理状态并关闭写屏障；
恢复用户程序，所有新创建的对象会标记成白色；
后台并发清理所有的内存管理单元，当 Goroutine 申请新的内存管理单元时就会触发清理；

全局变量

runtime.gcphase 是垃圾收集器当前处于的阶段，可能处于 _GCoff、_GCmark 和 _GCmarktermination，Goroutine 在读取或者修改该阶段时需要保证原子性；
runtime.gcBlackenEnabled 是一个布尔值，当垃圾收集处于标记阶段时，该变量会被置为 1，在这里辅助垃圾收集的用户程序和后台标记的任务可以将对象涂黑；
runtime.gcController 实现了垃圾收集的调步算法，它能够决定触发并行垃圾收集的时间和待处理的工作；
runtime.gcpercent 是触发垃圾收集的内存增长百分比，默认情况下为 100，即堆内存相比上次垃圾收集增长 100% 时应该触发 GC，并行的垃圾收集器会在到达该目标前完成垃圾收集；
runtime.writeBarrier 是一个包含写屏障状态的结构体，其中的 enabled 字段表示写屏障的开启与关闭；
runtime.worldsema 是全局的信号量，获取该信号量的线程有权利暂停当前应用程序；

所有触发的垃圾收集的代码：

runtime.sysmon 和 runtime.forcegchelper — 后台运行定时检查和垃圾收集；
runtime.GC — 用户程序手动触发垃圾收集；
runtime.mallocgc — 申请内存时根据堆大小触发垃圾收集；

image.png

后台触发
运行时会在应用程序启动时在后台开启一个用于强制触发垃圾收集的 Goroutine，该 Goroutine 的职责非常简单 — 调用 runtime.gcStart 方法尝试启动新一轮的垃圾收集：

func init() {
    go forcegchelper()
}

func forcegchelper() {
    forcegc.g = getg()
    for {
        lock(&forcegc.lock)
        atomic.Store(&forcegc.idle, 1)
        goparkunlock(&forcegc.lock, waitReasonForceGGIdle, traceEvGoBlock, 1)
        gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
    }
}

为了减少对计算资源的占用，该 Goroutine 会在循环中调用 runtime.goparkunlock 主动陷入休眠等待其他 Goroutine 的唤醒，runtime.forcegchelper 在大多数时间都是陷入休眠的，但是它会被系统监控器 runtime.sysmon 在满足垃圾收集条件时唤醒：
系统监控在每个循环中都会主动构建一个 runtime.gcTrigger 并检查垃圾收集的触发条件是否满足，如果满足条件，系统监控会将 runtime.forcegc 状态中持有的 Goroutine 加入全局队列等待调度器的调度。

手动触发
用户程序会通过 runtime.GC 函数在程序运行期间主动通知运行时执行，该方法在调用时会阻塞调用方知道当前垃圾收集循环完成，在垃圾收集期间也可能会通过 STW 暂停整个程序：
申请内存

当前线程的内存管理单元中不存在空闲空间时，创建微对象和小对象需要调用 runtime.mcache.nextFree 方法从中心缓存或者页堆中获取新的管理单元，在这时就可能触发垃圾收集；
当用户程序申请分配 32KB 以上的大对象时，一定会构建 runtime.gcTrigger 结构体尝试触发垃圾收集；
runtime.gcController 会在每个循环结束后计算触发比例并通过 runtime.gcSetTriggerRatio 设置 gc_trigger，它能够决定触发垃圾收集的时间以及用户程序和后台处理的标记任务的多少，利用反馈控制的算法根据堆的增长情况和垃圾收集 CPU 利用率确定触发垃圾收集的时机。

垃圾收集启动
垃圾收集在启动过程一定会调用 runtime.gcStart 函数
runtime.stopTheWorldWithSema 和 runtime.startTheWorldWithSema 是一对用于暂停和恢复程序的核心函数，它们有着完全相反的功能
后台标记模式
在垃圾收集启动期间，运行时会调用 runtime.gcBgMarkStartWorkers 为全局每个处理器创建用于执行后台标记任务的 Goroutine，每一个 Goroutine 都会运行 runtime.gcBgMarkWorker，所有运行 runtime.gcBgMarkWorker 的 Goroutine 在启动后都会陷入休眠等待调度器的唤醒：
这些 Goroutine 与处理器是一一对应的关系，当垃圾收集处于标记阶段并且当前处理器不需要做任何任务时，runtime.findrunnable 函数会在当前处理器上执行该 Goroutine 辅助并发的对象标记：
用于并发扫描对象的工作协程 Goroutine 总共有三种不同的模式 runtime.gcMarkWorkerMode，这三种不同模式的 Goroutine 在标记对象时使用完全不同的策略，垃圾收集控制器会按照需要执行不同类型的工作协程：

gcMarkWorkerDedicatedMode — 处理器专门负责标记对象，不会被调度器抢占；
gcMarkWorkerFractionalMode — 当垃圾收集的后台 CPU 使用率达不到预期时（默认为 25%），启动该类型的工作协程帮助垃圾收集达到利用率的目标，因为它只占用同一个 CPU 的部分资源，所以可以被调度；
gcMarkWorkerIdleMode — 当处理器没有可以执行的 Goroutine 时，它会运行垃圾收集的标记任务直到被抢占；

并发扫描
runtime.gcBgMarkWorker 是后台的标记任务执行的函数，该函数的循环中执行了对内存中对象图的扫描和标记，我们分三个部分介绍该函数的实现原理：

获取当前处理器以及 Goroutine 打包成 parkInfo 类型的结构体并主动陷入休眠等待唤醒；
根据处理器上的 gcMarkWorkerMode 模式决定扫描任务的策略；
所有标记任务都完成后，调用 runtime.gcMarkDone 方法完成标记阶段；

工作池
在调用 runtime.gcDrain 函数时，运行时会传入处理器上的 runtime.gcWork，这个结构体是垃圾收集器中工作池的抽象，它实现了一个生产者和消费者的模型，我们可以以该结构体为起点从整体理解标记工作：

image.png

写屏障、根对象扫描和栈扫描都会向工作池中增加额外的灰色对象等待处理，而对象的扫描过程会将灰色对象标记成黑色，同时也可能发现新的灰色对象，当工作队列中不包含灰色对象时，整个扫描过程就会结束。

为了减少锁竞争，运行时在每个处理器上会保存独立的待扫描工作，然而这会遇到与调度器一样的问题 — 不同处理器的资源不平均，导致部分处理器无事可做，调度器引入了工作窃取来解决这个问题，垃圾收集器也使用了差不多的机制平衡不同处理器上的待处理任务。
runtime.gcWork.balance 方法会将处理器本地一部分工作放回全局队列中，让其他的处理器处理，保证不同处理器负载的平衡。

runtime.gcWork 为垃圾收集器提供了生产和消费任务的抽象，该结构体持有了两个重要的工作缓冲区 wbuf1 和 wbuf2，这两个缓冲区分别是主缓冲区和备缓冲区：
当我们向该结构体中增加或者删除对象时，它总会先操作主缓冲区，一旦主缓冲区空间不足或者没有对象，就会触发主备缓冲区的切换；而当两个缓冲区空间都不足或者都为空时，会从全局的工作缓冲区中插入或者获取对象

标记辅助
为了保证用户程序分配内存的速度不会超出后台任务的标记速度，运行时还引入了标记辅助技术，它遵循一条非常简单并且朴实的原则，分配多少内存就需要完成多少标记任务。每一个 Goroutine 都持有 gcAssistBytes 字段，这个字段存储了当前 Goroutine 辅助标记的对象字节数。在并发标记阶段期间，当 Goroutine 调用 runtime.mallocgc 分配新的对象时，该函数会检查申请内存的 Goroutine 是否处于入不敷出的状态：
申请内存时调用的 runtime.gcAssistAlloc 和扫描内存时调用的 runtime.gcFlushBgCredit 分别负责『借债』和『还债』，通过这套债务管理系统，我们能够保证 Goroutine 在正常运行的同时不会为垃圾收集造成太多的压力，保证在达到堆大小目标时完成标记阶段。
每个 Goroutine 持有的 gcAssistBytes 表示当前协程辅助标记的字节数，全局垃圾收集控制器持有的 bgScanCredit 表示后台协程辅助标记的字节数，当本地 Goroutine 分配了较多的对象时，可以使用公用的信用 bgScanCredit 偿还。我们先来分析 runtime.gcAssistAlloc 函数的实现：
如果全局信用不足以覆盖本地的债务，运行时会在系统栈中调用 runtime.gcAssistAlloc1 执行标记任务，该函数会直接调用 runtime.gcDrainN 完成指定数量的标记任务并返回：
如果在完成标记辅助任务后，当前 Goroutine 仍然入不敷出并且 Goroutine 没有被抢占，那么运行时会执行 runtime.gcParkAssist；在该函数中，如果全局信用依然不足，runtime.gcParkAssist 会将当前 Goroutine 陷入休眠、加入全局的辅助标记队列并等待后台标记任务的唤醒。
用于还债的 runtime.gcFlushBgCredit 实现比较简单，如果辅助队列中不存在等待的 Goroutine，那么当前的信用会直接加到全局信用 bgScanCredit 中：
如果辅助队列不为空，上述函数会根据每个 Goroutine 的债务数量和已完成的工作决定是否唤醒这些陷入休眠的 Goroutine；如果唤醒所有的 Goroutine 后，标记任务量仍然有剩余，这些标记任务都会加入全局信用中。

GC为什么要STW两次

首先说明一下，下面说的停，都是STW，stop the world，全世界暂停，所有运行的都停下来了。
这个流程可以由下面这张图展示：

-w1183

第一个过程

先告诉所有人，停一下，我来记录一下当前状态。

第二个过程

告诉所有人，你们继续，该干嘛干嘛，我标记一下要用的对象

image

一开始所有点是白色，首先从根节点出发，标记相连的点为灰色（相连证明有引用），并且将所有灰色的点存起来；

image

然后遍历所有灰色的点，标记所有灰色的点相连的点为灰色，并且将自己标记为黑色；然后重复，直到没有点是灰色；

第三个过程

告诉所有人，再停一下，在第二个过程中，因为所有人继续在工作，那么就会产生新的垃圾，因为第一个过程记录了状态，所以需要标记一下新的垃圾；然后清除所有白色的点，因为白色的点是没人引用的，也就是垃圾。

为什么要这样GC

你一定会有这样的疑问：

为什么要暂停两次？
为什么不直接标记？

如果再标记的过程中不断的在创建新的对象，那么永远就标记不完了。
如果标记的过程中，原来的被标记的对象引用发生变更也会导致问题。

那么既然会导致那么多问题，为什么不直接停下来，标记完回收完了再开始呢？
因为慢~

所以这样GC的原因是既要保证GC正常执行，又要保证效率，不能停的时间太长。

第一个过程

其实第一次停的时候，启动了一个写屏障 (write barrier)它需要记录后续过程中新创建的对象

第二个过程

这个过程称为三色标记，有点类似广度优先搜索。

第三个过程

这次是必须停，因为在第二个过程中引用会发生变化，从而需要停止后重新扫描一遍；然后关闭写屏障，最后再清理。

重点

什么时候需要stw？

开启写屏障时需要stw
关闭写屏障前需要stw

什么时候是并发执行的？

开启写屏障之后的标记过程与其他程序并发执行
关闭写屏障之后的清扫过程与其他程序并发执行

GC的触发条件

那毕竟GC还是需要STW的，虽然可能停止时间很短，但是对于程序来说，整个程序停止1秒那对于用户来说就是致命打击。所以GC肯定需要一个触发的条件，不能想来就来。

GC百分比

这是一个触发的条件，默认GC百分比设置的是100，意思是，如果这次回收之后总共占用2M的内存，那么下次触发的条件时当超过4M的时候；同理，当这次回收之后总共占用4M，那么下次触发条件就是8M。

2分钟

这个简单，当一定时间（2分钟）没有执行过GC就触发GC（称为GC forced）
监控服务 sysmon 每隔 2 分钟就会检查一次垃圾回收状态，如超出 2 分钟未曾触发，那就强制执行。

手动

使用命令runtime.GC()手动触发GC

Go 语言设计与实现-Part1

https://draveness.me/golang/

第一个过程

第二个过程

第三个过程

为什么要这样GC

第一个过程

第二个过程

第三个过程

重 点

GC的触发条件

GC百分比

2分钟

手动

重点