前言
得有半个多月没写博客了, 说来甚是惭愧, 不过这半个多月一直也都是在刷题, 正好也有个比赛出去了一段时间, 导致了一直也没碰这个博客, 等这段面试集中期过去了, 可以恢复正常的写博客了. 今天想要总结 都的是linux下内存管理的一些问题.
内存管理会出现的问题
不断的内存分配与释放会导致很多内存碎片, 由于内存在不断的分配过程中越分配越小, 所以在后期很难找到一块较大的内存满足程序的需求, 这个问题的出现的一个原因是在内存释放的时候, 不能把相邻的空闲内存合并为更大的内存, 为了解决这些问题, 我们一般有如下解决办法:
- 小块内存单独分配, 大块内存由系统自动分配.(stl使用的就是这种方式, 当需要的内存大小于128KB时, 会由第二级内存配置器来进行分配, 第二级内存配置器使用的是free list链表, 用来给小块内存分配内存, 大于128KB的内存由一级内存配置器来进行分配, 可以认为是由系统来进行分配)
- 伙伴算法
- slab算法
后两种就是linux下使用的解决办法.
伙伴算法
- 将空闲内存分为m个组, 第一组储存2^0个单位的内存块, 第二组储存2^1个单位的内存块, 第三组储存2^2个单位的储存块, 以此类推, 直到m组.
- 每个组是一个链表, 用来储存同等大小的内存块.
- 伙伴块的大小是固定的, 并且同一个组里面的内存块是伙伴.
分配内存的过程:
- 如果申请的内存大小是n个单位块, 则先将n向上取整为2的n次幂, 假设为s, 然后我们从前面的数组中定位到s.
- 如果该组中有剩余内存块就分配出去
- 如果没有剩余内存块的话, 向上查找, 然后再将该内存块分割出来, 并将剩余的块放到数组中去.
举个例子吧, 如果我们需要的是5个单位大小的内存块, 先向上取整为2的幂次方, 最近的也就是8, 所以我们去第四组看看, 如果这个链表为空的话, 也就是说如果这个链表中没有空闲内存给我们的话, 我们就向上找, 定位到第五组, 如果这个链表不为空, 那么我们取出这个空闲内存块, 然后分割出大小为8个单位块的内存供用户使用, 然后将剩余的8个单位块大小的内存块放到第四组的链表中去.
伙伴算法内存归并的过程:
- 我们检测归还内存的伙伴内存块是否空闲, 如果空闲就合并在一起, 不空闲就直接放回到合适的链表中.
- 一般来说, 伙伴算法中会使用位图来记录内存块是否被使用, 用于伙伴内存的内并.
伙伴算法的优缺点:
优点: 分配和回收内存都十分的方便, 可以解决外部碎片的问题, 在不断的回收和释放过程中仍然可以保存有较大的内存块. 分配内存速度也很快, 基本是O(lgN)的效率.
缺点: 导致较大的内部碎片, 比如我们需要一个9个单位块大小的内存块, 但是按伙伴算法会直接给我们分配一个16个单位块大小的内存块, 显然有7个单位块大小的内存是被浪费的. 同时, 如果在分配和回收比较多的情况下, 为了避免无用的合并, 应该设置链表中内存块的低潮个数, 只有当链表中内存块个数小于某个值时, 并不合并伙伴内存块, 只在高于低潮个数的情况下再合并.
slab算法
一般来说, 伙伴算法都用于比较大的内存分配情况下, linux下的伙伴算法使用页为单位, 而页的大小基本都是4KB, 因此对于小块内存的分配和回收, 伙伴算法就不太适用了, 这个时候我们就需要用到slab算法或者叫slab机制.
- slab分配器是最早Jeff Bonwick在SunOS中使用的一种分配内存的方式, slab分配器的核心是对象缓存. 在内核中, 会为有限的对象集(例如文件描述符或进程描述符或其他常见数据结构)分配大量内存. Jeff发现对内核中普通对象进行初始化的时间超过了对其进行分配和释放所需的时间, 因此他的结论是对于常用的一些数据结构, 内核不应该将内存释放回一个全局的内存池, 而是将内存保持为针对特定目的而初始化的状态. 例如, 如果内存被分配给了一个互斥锁, 那么只需要在为这个互斥锁首次分配内存的时候执行一次互斥锁初始化函数, 后续如果还要用到这块内存作为互斥锁的话, 就不再需要初始化了, 因为在锁被释放之后, 内存并没有被用作其他用途或被破坏, 因此仍然处于所需的状态.
- linux slab分配器使用了这种思想和其他一些思想来构建一个在空间和时间上都具有高效性的内存分配器.
上图给出了slab结构的高层组织结构, 在最高层是cache_chain, 这是一个slab缓存的链接列表,
每个缓存都包含了一个 slabs 列表，这是一段连续的内存块（通常都是页面）。存在3 种 slab:
- slabs_full:完全分配的slab
- slabs_partial:部分分配的slab
- slabs_empty:空slab，或者没有对象被分配
slab 列表中的每个 slab都是一个连续的内存块（一个或多个连续页），它们被划分成一个个对象。这些对象是从特定缓存中进行分配和释放的基本元素。注意 slab 是 slab分配器进行操作的最小分配单位，因此如果需要对 slab 进行扩展，这也就是所扩展的最小值。通常来说，每个 slab 被分配为多个对象.
由于对象是从 slab 中进行分配和释放的，因此单个 slab 可以在 slab列表之间进行移动。例如，当一个 slab中的所有对象都被使用完时，就从slabs_partial 列表中移动到 slabs_full 列表中。当一个 slab完全被分配并且有对象被释放后，就从 slabs_full 列表中移动到slabs_partial 列表中。当所有对象都被释放之后，就从 slabs_partial 列表移动到 slabs_empty 列表中。
slab算法优点: 很明显, 这个算法的引入是大大增加了内核的效率的, 因为在内核中很多数据结构的分配和释放是非常频繁的, 比如文件描述符或进程描述符或Socket等等. 使用slab算法大大提高了内核的效率, 同时也避免了小的内存对象不断分配和释放可能带来的碎片的问题. 最后 slab算法还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。