Go内存分配与GC

Go语言GMP介绍

Go语言相比Java，有更好的并发能力（GMP模型），同时其占用的服务器资源也较少，了解一下GMP的理念。从操作系统层面来看，线程是指内核级线程，是操作系统最小调度单元，创建、销毁、调度交由内核完成，可充分利用多核。协程（用户线程）与线程存在M:1的映射关系，从属于同一个内存级线程，无法并行，并且，一个协程阻塞会导致从属同一线程的所有协程无法执行。

Goroutine

经Golang优化后的协程，其有如下特点：1）与线程存在映射关系，为M:N；2）创建、销毁、调度在用户态完成，对内核透明，足够轻便；3）可利用多个线程，实现并行；4）通过调度器的斡旋，实现和线程间的动态绑定和灵活调度；5）栈空间大小可动态扩缩，因地制宜；

在/runtime/proc.go的代码注释中，有对GMP的解释，其核心数据结构在/runtime/runtime2.go:

• 其中g是Golang中对协程的抽象，g有自己的运行栈，状态及执行的任务函数，g需要绑定到p上才能执行，p就是g的cpu；
• m即machine，是golang中对线程的抽象，m不直接执行g，而是先和p绑定，由其代理执行；借由p的存在，m无需和g绑死，也无需记录g的状态信息，因此g在全生命周期中可以跨m执行。
• p也即processor，是golang中的调度器。对于g而言，p是其调度器，g只有被p调度，才得以执行；对m而言，p是其执行代理，为其提供必要信息的同时，隐藏了繁杂的调度细节；

// Goroutine scheduler, Design doc at https://golang.org/s/go11sched.
// The scheduler's job is to distribute ready-to-run goroutines over worker threads.
//
// The main concepts are:
// G - goroutine.
// M - worker thread, or machine.
// P - processor, a resource that is required to execute Go code.
//     M must have an associated P to execute Go code, however it can be
//     blocked or in a syscall w/o an associated P.

gmp模型其要点和调度规则如下：

• M是线程的抽象；G是goroutine；P是承上启下的调度器；M调度G前，需要和P绑定；
• 全局有多个M和多个P，但同时并行的G的最大数量等于P的数量；
• G的存放队列有三类：P的本地队列、全局队列和wait队列（图中未展示，为io阻塞就绪态goroutine队列）；
• M调度G时，优先取P本地队列，其次取全局队列，最后取wait队列；这样的好处是，取本地队列时，可以接近于无锁化，减少全局锁竞争；
• 为防止不同P的闲忙差异过大，设立work-stealing机制，本地队列为空的P可以尝试从其他P本地队列偷取一半的G补充到自身队列;

GMP调度

g0是一种特殊的调度协程，不执行用户函数，负责执行g之间的切换调度，与m的关系为1:1。goroutine的类型可分为两类：

• 1）负责调度普通g的g0，与m的关系为一对一；
• 2）负责执行用户函数的普通g，被调度执行的g永远在g和g0的状态间切换；

当g0找到可执行g时，会调用gogo方法，调度g执行用户定义的任务。当g需要主动让渡时，会触发mcall方法，将执行权限重新交给g0；

广义”调度”可分为几种类型：

• 主动调度：一种用户主动执行让渡过程，主要方式是在代码中执行runtime.Gosched方法(runtime/proc.go)，此时当前g会当让出执行权，主动进行队列等待下次被调度执行。
• 被动调度：因不满足某执行条件，g可能陷入阻塞态无法被调度，直到关注的条件达成后，g才从阻塞中被唤醒(对应runtime/proc.go#gopark方法，恢复则是goready方法)。
• 正常调度: g中的执行任务已完成，g0会将当前g置为死亡状态，发起新一轮调度；
• 抢占调度：倘若g执行系统调用超过指定的时长，且全局p资源比较短缺，此时将p和g接绑，用解绑的p用于其他g的调度；

值得一提的是，前3种调度方式都由m下的g0完成。而抢占调用则是由一个全局监控协程monitor g来监控，倘若发现满足抢占调度的条件，则会从第三方的角度出手干预，主动发起该动作。从宏观上：

• 以g0 -> g -> g0 的一轮循环为例进行串联；
• g0 执行 schedule() 函数，寻找到用于执行的 g；
• g0 执行 execute() 方法，更新当前 g、p 的状态信息，并调用gogo()方法，将执行权交给g；
• g 因主动让渡(gosche_m())、被动调度(park_m())、正常结束(goexit0())等原因，调用m_call函数，执行权重新回到g0手中；
• g0执行schedule()函数，开启新一轮循环.

p每执行61次，会从全局队列中获取一个goroutine进行执行，同时会额外将全局队列中的一个goroutine放到本地队列中。若本地队列已满，则会返回来将本地队列中一半的g放回全局队列中，帮助当前p缓解执行压力;

Go内存模型与分配机制

在操作系统中，存在寄存器、高速缓存、内存和磁盘，越接近cpu存储的容量越小，其对应的价格就越高昂。页表、分页管理等机制来减少内存碎片。

Golang中的内存模型，以空间换时间，一次缓存，多次复用。堆mheap正是基于该思想，产生的数据结构。依次细化粒度，建立了 mcentral、mcache 的模型，下面对三者作个梳理：

• mheap：全局的内存起源，访问要加全局锁；
• mcentral：每种对象大小规格（全局共划分为68种）对应的缓存，锁的粒度也仅限于同一种规格以内；
• mcache：每个P（正是GMP中的P）持有一份的内存缓存，访问时无锁，多级规格，提高利用率；

内存单元mspan

page和mspan的2个概念，page：最小的存储单元，默认大小为8KB，mspan大小为page的整数倍，且从8B到80KB 被划分为67种不同的规格，对应源代码在runtime/sizeclasses.go，mspan具有如下特点：

• 根据规格大小，产生了等级的制度，mspan是Golang内存管理的最小单元，runtime/mheap.go；
• 消除了外部碎片，但不可避免会有内部碎片；
• 宏观上能提高整体空间利用率，同等级的mspan会从属同一个mcentral，最终会被组织成链表，因此带有前后指针（prev、next）；
• 正是因为有了规格等级的概念，才支持mcentral实现细锁化，全局总览，留个印象；
• mspan会基于bitMap辅助快速找到空闲内存块（块大小为对应等级下的object大小），此时需要使用到Ctz64算法.

线程缓存mcache

• mcache是每个P独有的缓存，因此交互无锁；
• mcache将每种spanClass等级的mspan各缓存了一个，总数为2（nocan维度） * 68（大小维度）= 136;
• mcache中还有一个为对象分配器tiny allocator，用于处理小于16B对象的内存分配；

中心缓存mcentral

要点:

• 每个mcentral对应一种spanClass；
• 每个mcentral下聚合了该spanClass下的mspan;
• mcentral下的mspan分为两个链表，分别为有空间mspan链表partial和满空间mspan链表full`;
• 每个mcentral一把锁;

全局堆缓存mheap

• 对于Golang上层应用而言，堆是操作系统虚拟内存的抽象，以页（8KB）为单位，作为最小内存存储单元；
• 负责将连续页组装成mspan，全局内存基于bitMap标识其使用情况，每个bit对应一页，为0则自由，为1则已被mspan组装；
• 通过heapArena聚合页，记录了页到mspan的映射信息，建立空闲页基数树索引radix tree index，辅助快速寻找空闲页；
• 是mcentral的持有者，持有所有spanClass下的mcentral，作为自身的缓存，内存不够时，向操作系统申请，申请单位为 heapArena（64M）；

对象分配流程

不论是以下哪种方式，最终都会殊途同归步入mallocgc方法中，例如：new(T)、&T{}、make(xxxx)，Golang中，依据object的大小，会将其分为下述三类：tiny微对象(0, 16B)、small小对象(16B，32KB)、large大对象(32KB，正无穷). 对于微对象的分配流程：

1. 从P专属mcache的tiny分配器取内存（无锁）
2. 根据所属的spanClass，从P专属mcache缓存的mspan中取内存（无锁）
3. 根据所属的spanClass从对应的mcentral中取mspan填充到mcache，然后从mspan中取内存（spanClass粒度锁）；
4. 根据所属的spanClass，从mheap的页分配器pageAlloc取得足够数量空闲页组装成mspan填充到mcache，然后从mspan中取内存（全局锁）；
5. mheap`向操作系统申请内存，更新页分配器的索引信息，然后重复（4）；

对于小对象的分配流程是跳过（1）步，执行上述流程的（2）-（5）步； 对于大对象的分配流程是跳过（1）-（3）步，执行上述流程的（4）-（5）步.

Go垃圾回收原理

做Java的都对GC比较熟悉，在JVM中常见的GC算法有：标记整理（Mark-Sweep）、标记压缩（Mark-Compact）、半空间复制（类似于G1），通过引用计数寻找不可达对象，便于垃圾回收。

Go中三色标记法

Golang GC中用到的三色标记法属于标记清扫-算法下的一种实现，由荷兰的计算机科学家Dijkstra提出，下面阐述要点：

• 对象分为三种颜色标记：黑、灰、白，黑对象代表，对象自身存活，且其指向对象都已标记完成；
• 灰对象代表，对象自身存活，但其指向对象还未标记完成；白对象代表，对象尙未被标记到，可能是垃圾对象
• 标记开始前，将根对象（全局对象、栈上局部变量等）置黑，将其所指向的对象置灰；
• 标记规则是，从灰对象出发，将其所指向的对象都置灰. 所有指向对象都置灰后，当前灰对象置黑；
• 标记结束后，白色对象就是不可达的垃圾对象，需要进行清扫；

为了应对并发情况下，对象标记出现漏标、多标的情况，可使用屏障机制。漏标问题的本质就是，一个已经扫描完成的黑对象指向了一个被灰\白对象删除引用的白色对象. 一套用于解决漏标问题的方法论称之为强弱三色不变式：

• 强三色不变式：白色对象不能被黑色对象直接引用;
• 弱三色不变式：白色对象可以被黑色对象引用，但要从某个灰对象出发仍然可达该白对象（间接破坏了（1）、（2）的联动）；