从C和C++内存管理来谈谈JVM的垃圾回收算法设计-上

从C和C++内存管理来谈谈JVM的垃圾回收算法设计-上

• 引言
• C内存模型
• malloc堆内存分配过程
• malloc为什么结合使用brk和mmap
• malloc如何通过内存池管理Heap区域
• 垃圾收集器

引言

本文想和大家来探讨一下JVM是如何对堆内存进行管理和垃圾回收,相关书籍如深入理解JVM第三版中已经介绍过了相关的垃圾回收算法及其实现,但是基于文字介绍无法让大家对垃圾回收有具象的理解，所以本文想从c内存模式和malloc函数介绍起,带领大家回顾一下如何使用c语言完成堆内存的申请和释放。

再使用c使用编写一个简易的垃圾回收器，最终重新回顾一遍JVM垃圾回收算法，相信此时各位应该会有一个具象的理解。

C内存模型

每部分含义如下:

细节注意:

• 栈(stack): 是由系统自动分配和释放，存放函数的参数值，返回值，局部变量等; 栈是有一定大小的，通常情况下，栈只有2M，不同系统栈的大小可能不同; 当在函数或块内部声明一个局部变量时，如：int nTmp; 系统会判断申请的空间是否足够，足够，在栈中开辟空间，提供内存；不够空间，报异常提示栈溢出。
• 堆(heap):是用来存放动态申请或释放的区域。需要程序员分配和释放，系统不会自动管理，如果用完不释放，将会造成内存泄露，直到进程结速后，系统自动回收。

堆的大小问题:

堆是可以申请大块内存的区域，但堆的大小到底有多大，下面分析下，以32位系统为例。

在linux中，堆区的内存申请，在32位系统中，理论上：2^32=4G，但如上面的内存分布图可知：内核占用1G空间。

如上所知，理论上，使用malloc最大能够申请空间大约3G。但这是理论值，因为实际中，还会包含代码区，全局变量区和栈区。

char  *buf = (char*) malloc(3GB);   // 理论上

堆内存使用注意事项:

1. 碎片问题：如果频繁地调用内存分配和释放，将会使堆内存造成很多内存碎片，从而造成空间浪费和效率低下。
2. 对于比较固定，或可预测大小的，可以程序启动时，即分配好空间，如：某个对象不会超过500个，那个可先生成，object ptr = (object)malloc(object_size*500);
3. 结构对齐，尽量使结构不浪费内存
4. 超堆大小问题：如果申请内存超过堆大小，会出现虚拟内存不足等问题
5. 尽量不要申请很大的内存
6. 申请内存后，都在判断内存是否分配成功，分配成功后才能使用，否则会出现段错误

本部分参考文献

malloc堆内存分配过程

从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk 和 mmap（不考虑共享内存）。

• brk 的实现方式是将代表堆最大内存的_edata指针往高地址推（分配的内存小于 128k ）。
• mmap 的实现方式是在 Memory Mapping Segment 找一块空闲的虚拟内存（分配的内存大于 128k ）。

这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系。

在标准 C 库中，提供了 malloc / free 函数分配释放内存，这两个函数底层是由 brk，mmap，munmap 这些系统调用实现的。

下面我们使用几个案例来理解一下malloc内存分配过程:

1、进程调用 A = malloc ( 30k ) 以后，内存空间如下图所示。malloc 函数会调用 brk 系统调用，将 _edata 指针往高地址推 30K，就完成虚拟内存分配。

你可能会问：只要把_edata + 30K 就完成内存分配了？

事实是这样的，_edata + 30K 只是完成虚拟地址的分配，A 这块内存现在还是没有物理页与之对应的，等到进程第一次读写 A 这块内存的时候，发生缺页中断，这个时候，内核才分配 A 这块内存对应的物理页。也就是说，如果用 malloc 分配了 A 这块内容，然后从来不访问它，那么，A 对应的物理页是不会被分配的。

2. 进程调用 B = malloc(40K) 以后，内存空间如下图所示。

3、当 malloc 分配大于 128k 的内存时，使用 mmap 分配内存。在堆和栈之间找一块空闲内存分配（对应独立内存，而且初始化为 0 ）。

这么做的原因是 brk 分配的内存需要等到高地址内存释放以后才能释放（例如，在 B 释放之前，A 是不可能释放的，这就是内存碎片产生的原因，什么时候收缩看下面），而 mmap 分配的内存可以单独释放。，如下图所示，这里分配 200k 。

4、进程调用 D = malloc(100k) 以后，内存空间如下图所示。

5、进程调用 free© 以后，C 对应的虚拟内存和物理内存一起释放。

6、进程调用 free(B) 以后，如下图所示，B 对应的虚拟内存和物理内存都没有释放，因为只有一个 _edata 指针，如果往回推，那么 D 这块内存怎么办呢？当然，B 这块内存是可以重用的，如果这个时候再来一个 40K 的请求，那么 malloc 很可能就将 B 这块内存返回的。

7、进程调用 free(D) 以后，如下图所示，B 和 D 连接起来变成一块 140K 的空闲内存。当最高地址空间的空闲内存超过128K（可由 M_TRIM_THRESHOLD 选项调节）时，执行内存紧缩操作（trim）。在上一个步骤 free 的时候，发现最高地址空闲内存超过 128 K，于是内存紧缩，如下图所示。

本部分内容参考文献

malloc为什么结合使用brk和mmap

brk:

• 一般如果用户分配的内存小于 128 KB，则通过 brk() 申请内存。而brk()的实现的方式很简单，就是通过 brk() 函数将堆顶指针向高地址移动，获得新的内存空间。
• malloc 通过 brk() 方式申请的内存，free 释放内存的时候，并不一定会把内存归还给操作系统，而是缓存在 malloc 的内存池中，待下次使用，这样就可以重复使用。

brk系统调用优点:

• 可以减少缺页异常的发生，提高内存访问效率。

brk系统调用缺点:

• 由于申请的内存没有归还系统，在内存工作繁忙时，频繁的内存分配和释放会造成内存碎片。brk()方式之所以会产生内存碎片，是由于brk通过移动堆顶的位置来分配内存，并且使用完不会立即归还系统，重复使用，如果高地址的内存不释放，低地址的内存是得不到释放的。

正是由于使用brk()会出现内存碎片，所以在我们申请大块内存的时候才会使用mmap()方式，mmap()释放后就直接归还系统了，所以不会出现这种小碎片的情况。

既然堆内内存brk和sbrk不能直接释放，为什么不全部使用 mmap 来分配，munmap直接释放呢？

既然堆内碎片不能直接释放，导致疑似“内存泄露”问题，为什么 malloc 不全部使用 mmap 来实现呢(mmap分配的内存可以会通过 munmap 进行 free ，实现真正释放)？而是仅仅对于大于 128k 的大块内存才使用 mmap ？

其实，进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用，频繁调用系统调用都比较消耗系统资源的。并且， mmap 申请的内存被 munmap 后，重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间，第一次调用产生了大量缺页中断 (1M/4K 次 ) ，当munmap 后再次分配 1M 空间，会再次产生大量缺页中断。缺页中断是内核行为，会导致内核态CPU消耗较大。

另外，如果使用 mmap 分配小内存，会导致地址空间的页内空闲碎片更多，内核的管理负担更大。同时堆是一个连续空间，并且堆内碎片由于没有归还 OS ，如果可重用碎片，再次访问该内存很可能不需产生任何系统调用和缺页中断，这将大大降低 CPU 的消耗。 因此， glibc 的 malloc 实现中，充分考虑了 sbrk 和 mmap 行为上的差异及优缺。

本部分参考文献1

本部分参考文献2

扩展知识:

用户进程的内存页分为两种：

• file-backed pages（文件背景页）
• anonymous pages（匿名页）

比如进程的代码段、映射的文件都是file-backed，而进程的堆、栈都是不与文件相对应的、就属于匿名页。

file-backed pages在内存不足的时候可以直接写回对应的硬盘文件里，称为page-out，不需要用到交换区(swap)；而anonymous pages在内存不足时就只能写到硬盘上的交换区(swap)里，称为swap-out。

• 文件背景页:

对于有文件背景的页面，程序去读文件时，可以通过read也可以通过mmap去读。当你通过任何一种方式从磁盘读文件时，内核都会给你申请一个page cache，来缓存硬盘上的内容。这样的话，读过一遍的数据，本进程或其他进程下次再读的时候就直接从page cache里去拿，就很快了，提升系统的整体性能。因此用户的read/write实际上是跟page cache的相互拷贝。

而用户的mmap则会将一段虚拟地址（3G）以下映射到page cache上，这样的话，用户就可以通过读写这段虚拟地址来修改文件内容，省去了内核和用户之间的拷贝。

• 匿名页

没有文件背景的页面，即匿名页（anonymous page），如堆，栈，数据段等，不是以文件形式存在，因此无法和磁盘文件交换，但可以通过硬盘上划分额外的swap分区或使用swap文件进行交换。swap分区可以将不活跃的页交换到硬盘中，缓解内存紧张。swap分区可以当做针对匿名页伪造的文件背景。

扩展知识: 文件背景页和匿名页,脏页刷新

扩展知识: 标准IO,直接IO和mmap

malloc如何通过内存池管理Heap区域

由于brk/sbrk/mmap属于系统调用，如果每次申请内存，都调用这三个函数中的一个，那么每次都要产生系统调用开销（即cpu从用户态切换到内核态的上下文切换，这里要保存用户态数据，等会还要切换回用户态），这是非常影响性能的；其次，这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果高地址的内存没有被释放，低地址的内存就不能被回收。

鉴于此，malloc采用的是内存池的实现方式，malloc内存池实现方式更类似于STL分配器和memcached的内存池，先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可。

• 分配内存 < DEFAULT_MMAP_THRESHOLD，走__brk，从内存池获取，失败的话走brk系统调用
• 分配内存 > DEFAULT_MMAP_THRESHOLD，走__mmap，直接调用mmap系统调用

其中，DEFAULT_MMAP_THRESHOLD默认为128k，可通过mallopt进行设置。

重点看下小块内存(size < DEFAULT_MMAP_THRESHOLD)的分配，glibc使用的内存池如下图示：

内存池保存在bins这个长128的数组中，每个元素都是一双向个链表。其中：

• bins[0]目前没有使用
• bins[1]的链表称为unsorted_list，用于维护free释放的chunk。
• bins[2,63)的区间称为small_bins，用于维护＜512字节的内存块，其中每个元素对应的链表中的chunk大小相同，均为index*8。
• bins[64,127)称为large_bins，用于维护>512字节的内存块，每个元素对应的链表中的chunk大小不同，index越大，链表中chunk的内存大小相差越大，例如: 下标为64的chunk大小介于[512, 512+64)，下标为95的chunk大小介于[2k+1,2k+512)。同一条链表上的chunk，按照从小到大的顺序排列。

chunk数据结构:

glibc在内存池中查找合适的chunk时，采用了最佳适应的伙伴算法。举例如下：

1. 如果分配内存<512字节，则通过内存大小定位到smallbins对应的index上(floor(size/8))
   • 如果smallbins[index]为空，进入步骤3
   • 如果smallbins[index]非空，直接返回第一个chunk
2. 如果分配内存>512字节，则定位到largebins对应的index上
   • 如果largebins[index]为空，进入步骤3
   • 如果largebins[index]非空，扫描链表，找到第一个大小最合适的chunk，如size=12.5K，则使用chunk B，剩下的0.5k放入unsorted_list中
3. 遍历unsorted_list，查找合适size的chunk，如果找到则返回；否则，将这些chunk都归类放到smallbins和largebins里面
4. index++从更大的链表中查找，直到找到合适大小的chunk为止，找到后将chunk拆分，并将剩余的加入到unsorted_list中
5. 如果还没有找到，那么使用top chunk
6. 目前内存池无空闲内存可用，那么如果内存<128k，使用brk；内存>128k，使用mmap获取新内存

top chunk:

如下图示: top chunk是堆顶的chunk，堆顶指针brk位于top chunk的顶部。移动brk指针，即可扩充top chunk的大小。当top chunk大小超过128k(可配置)时，会触发malloc_trim操作，调用sbrk(-size)将内存归还操作系统。

free释放内存时，有两种情况：

• chunk和top chunk相邻，则和top chunk合并
• chunk和top chunk不相邻，则直接插入到unsorted_list中

参考文献,涉及多线程情况下内存分配

垃圾收集器

经过上面的介绍,相信大家理解简单了解了C语言的内存模型和堆内存分配和回收过程，但是目前棘手问题在于，我们必须手动通过free函数释放某块内存，能否自动释放不再被引用的内存块呢？

这就是垃圾收集器需要做的事情，再聊垃圾收集器实现思路前，我们先来看两个概念:

• 显式分配器：要求应用显式地释放任何已经分配的块。例如c标准库中的malloc. c程序通过调用malloc函数来分配一个块，并通过调用free函数来释放一个块。c++中的new和delete操作符和c中搞得malloc和free相当。（就是自己手动释放内存）
• 隐式分配器：要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块。隐式分配器也叫做垃圾收集器，而自动释放未使用的已分配的块的过程叫做垃圾收集。例如java，ML，Lisp之类的高级语言就依赖垃圾收集来释放已分配的块。（就是不用程序猿自己手动释放内存）

本文由于篇幅限制，暂时聊到这里，下一篇文章中，我们将尝试使用具体的代码来实现一个建议的垃圾收集器，最后再回到JVM垃圾回收算法的实现中。