go内存管理和垃圾收集简介

go语言的内存分两部分,一部分用作堆,供内存分配用,另一部分是bitmap,用来管理堆。两部分从同一地址开始,向高地址方向增长的是内存池,向低地址方向增长的是bitmap。

内存分配

对于较大的内存申请,直接从堆上申请,释放时也直接返回给堆。

而当一个go routine申请小于32k字节的内存,则从go routine私有的内存池中分配内存。因为是私有的,所有在多数情况下,分配内存不需要上锁。如果私有内存池没有内存了,则需要向中心内存池申请内存,中心内存池是共享数据,此时需要上锁。如果中心内存池也没有内存了,则从堆里申请内存。

私有内存池和中心内存池里的内存都是按照大小分开管理的,这样,分配和释放内存都非常快,而且也不容易产生碎片。通常,中心内存池从堆上申请一大块内存,然后将其打碎成多个同样大小的块,并串成一个free list。而当私有内存池向中心内存池申请内存时,也会一次性多要一些内存块,供以后使用,避免私有内存池和中心内存池之间过于频繁地交互,增加上锁的代价。

而当私有内存池内有过多的剩余内存时,会将其中一部分还给中心内存池,供其它go routine使用,以此避免其它go routine在有内存的时却申请不到内存的情况。

看完这部分代码,让我联想到Is Parallel Programming Hard第四节Counting的讲解,虽然它讲的是同步而非内存管理,但是由于结构类似,让我很快就理解了这部分内存管理的实现。

垃圾收集

对于每一个堆上的word,在bitmap上有对应的四个bit,记录了该word是否已经被分配、是否是一个边界、是否被标注等等。开始垃圾收集时,先标注所有全局变量,然后标注所有go routine的栈,并从这些被标注的对象开始,递归标注所有它们引用的对象,当这个过程停止后,所有活着的对象都被标注好了,而那些已经被分配但是没有被标注的对象所占用的内存则可以释放了。这是一个经典的mark-sweep算法。

gc启动的条件是每次分配内存之后检查,

	if(dogc && mstats.heap_alloc >= mstats.next_gc)
		runtime·gc(0);

而在gc之后会更新next_gc

	mstats.next_gc = mstats.heap_alloc+mstats.heap_alloc*gcpercent/100;

如果gcpercent为100,而本次gc后堆分配了4M,则下一次gc为堆增长到8M。参见gcpercent变量定义之前的注释。

由于引用未必都是指向一个对象的首地址,比如可以指向一个结构中的某个域,那么如何获得该域所在对象的首地址和大小呢。bitmap中的边界位就是为了回答这个问题。从引用所指向的地址向两边找,如果碰到对应的边界位被置上,则到达了对象的边界,这样就确定引用对象的首地址和大小。

go channel实现

Go语言经过多年的发展,于最近推出了第一个稳定版本。相对于C/C++来说,Go有很多独特之出,比如提供了相当抽象的工具,如channel和goroutine。本文主要介绍channel的实现方式。

简介

channel有四个操作:

  • 创建:c = make(chan int)
  • 发送:c <- 1
  • 提取:i <- c
  • 关闭:close(c)

根据创建方式的不同,channel还可分为有buffer的channel和没有buffer的channel。buffer的大小由make的第二个参数指定,默认为0,即没有buffer。创建有buffer的channel的方式是:c = make(chan int, 10)

channel的实现主要在文件src/pkg/runtime/chan.c里面。它的数据结构如下:

struct	Hchan
{
	uint32	qcount;			// total data in the q
	uint32	dataqsiz;		// size of the circular q
	uint16	elemsize;
	bool	closed;
	uint8	elemalign;
	Alg*	elemalg;		// interface for element type
	uint32	sendx;			// send index
	uint32	recvx;			// receive index
	WaitQ	recvq;			// list of recv waiters
	WaitQ	sendq;			// list of send waiters
	Lock;
};

发送流程

Hchan中的两个WaitQrecvqsendq)是两个队列,分别保存等待从该channel提取和发送的goroutine。以向没有buffer的channel发送为例,

  • 如果向该channel发送数据的goroutine发现recvq不为空,则从recvq中取出一个goroutine,然后把数据传给它,发送完成,发送方goroutine可以继续执行。提取方goroutine则结束block状态,可以被调度执行。
  • 否则,发送方goroutine被存入sendq队列,且发送方goroutine进入block状态,调度算法选择其它goroutine执行。

如果channel有buffer,

  • 如果buffer里有空间,则把数据存入buffer,发送完成;如果recvq队列里有等待的goroutine,则取出一个,并将其唤醒,等待调度执行。发送方goroutine继续执行。
  • 如果buffer已满,则发送方goroutine被存入sendq队列,发送方goroutine进入block状态,调度算法选择其它goroutine执行。

如果向已经关闭的channel发送数据,程序会报错并异常退出。如下面的程序:

package main

func main() {
	c := make(chan int)
	d := make(chan int)
	go func() {
		<-d
		close(c)
	} ()
	d <- 4
	c <- 3
}

从已经关闭的channel收取数据不会报错,也不会异常退出,但是我不确定得到什么样的值。除此之外,提取和发送的实现基本是相对的,就不再介绍了。

Buffer空间

buffer的空间紧挨着channel,是在创建的channel的时候一起分配的,

c = (Hchan*)runtime·mal(n + hint*elem->size);

其中hint即为buffer的元素个数,会保存在dataqsiz里,另外一起管理buffer的还有qcountsendxrecvx,分别表示buffer里的元素个数,下一次发送操作存放数据的位置,以及下一次提取数据的位置。这个buffer是个circular buffer。

Channel与Select

channel配合select语句,可以实现multiplex的效果,如:

select {
case <-c1:
case <-c2:
}

c1c2哪个channel先有数据到达,哪个case先执行;都没有数据,就block住;都有数据,以一个公平的方式随机选择一个case执行。select语句本身没有增加channel的操作方式,但是它本身的实现也很有趣:

  • 当select被block住,它所在的goroutine将被挂在多个channel的sendq或者recvq上。比如上面的例子中,select所在的goroutine将被挂在c1c2recvq上,如果这时有另外两个goroutine同时分别向c1c2发送数据,那么它们将操作同一个goroutine(尽管是不同的channel),这种情况下,要么加锁,要么用原子操作。这就是为什么dequeue里要使用runtime·cas的原因,虽然调用dequeue之前上锁了,但那是给sendq/recvq上锁,不是给goroutine上锁。
  • 不同goroutine里面的select语句可能操作同一组channel,那么就有上锁的必要。Go的实现里每个channel有自己的锁,所以select就需要上多个锁,稍有不慎,可能导致死锁。Go的实现是用bubble sort把channel的地址(即Hchan*)排序,然后依次上锁。
  • 最后就是如何实现相对公平。

相对公平的另一个说法就是每个channel被选中的概率是相等的。实现如下:

	for(i=0; i<sel->ncase; i++)
		sel->pollorder[i] = i;
	for(i=1; i<sel->ncase; i++) {
		o = sel->pollorder[i];
		j = runtime·fastrand1()%(i+1);
		sel->pollorder[i] = sel->pollorder[j];
		sel->pollorder[j] = o;
	}

每个迭代做的事情就是在前i个元素里随机选择一个放在第i个位置上。这个算法比programming pearls里面的难理解,因为每个元素可能被移动多次。我们分两种情况来讨论,对于任意一个位置i,最终落在这个位置的元素可能来自i之前(包括i)或者i之后。

如果是来自与i之前(包括i),那么它在之后就不能被交换出去。所以它留在位置i的概率为(1/i) * i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n = 1/n

如果来自i之后(如位置k),那么在换到i之后,不能有其后的元素再和i交换,所以概率为(1/k) * k/(k+1) * ... * (n-1)/n = 1/n

由以上两种情况可知,任何一个元素出现在位置i的概率都是1/n

因此,按照pollorder的顺序依次检查case是否能够执行,对于每个case来说,是公平的。