内存管理问题
内存碎片大小和管理内存碎片的效率问题(即空间和时间效率的问题):
内存碎片是指当回收一块内存时,一般将内存直接放入free链表中,由于内存越分配越小,内存块就会特别多而且特别小,当需要一块大的内存块的时候无法找到.原因就在于回收内存的时候,不能把相邻两块可用内存合并.
解决方法:
- 小块内存单独分配,大块内存有系统自动分配.(nginx和stl就是使用这种方法)
- 伙伴算法.
- slab算法.
伙伴算法
- 将空闲页面分为m个组,第1组存储20个单位的内存块,第2组存储21个单位的内存块,第3组存储22个单位的内存块,第4组存储23个单位的内存块,以此类推.直到m组.
- 每个组是一个链表,用于连接同等大小的内存块.
- 伙伴块的大小是相等的,并且第1块和第2块是伙伴,第三块和第四块是伙伴.以此类推.
伙伴算法分配内存
若申请的内存大小为n则将n向上取整为2的幂设次数为s,则需要分配s大小的内存块,定位大相应数组,
- 如果该数组有剩余内存块,则分配出去.
- 若没有剩余内存块就沿数组向上查找,然后再将该内存块分割出来s并将剩余的内存块放入相应大小的数组中.
例如分配5大小的内存块
----------->定位到大小为8的链表中 -------->若该链表中之中没有空余元素,则定位到16的链表中,16中有剩余元素,则取出该元素,并分割出大小为8的内存块供用户使用,然后将剩余的8连接到大小为8的数组中.
伙伴算法的内存合并
当用户用完内存后会归还,然后根据该内存块实际大小(向上取整为2的幂)归入链表中,在归入之前,
- 我们还要检测他的伙伴内存块是否空闲,
- 如果空闲就合并在一起,合并后转到1,继续执行.
- 若果不是空闲的就直接归入链表中.
一般来说,伙伴算法实现中会用位图记录内存块是否被使用,用于伙伴内存的合并.
伙伴算法的特点
显而易见,伙伴算法会浪费大量的内存,(如果需要大小为9的内存块必须分配大小为16的内存块).而优点也是明显的,分配和合并算法都很简单易行.但是,当分配和回收较快的时候,例如分配大小为9的内存块,此时分配16,然后又回收,即合并伙伴内存块,这样会造成不必要的cpu浪费,应该设置链表中内存块的低潮个数,即当链表中内存块个数小于某个值的时候,并不合并伙伴内存块,只要当高于低潮个数的时候才合并.
slab算法
一般来说,伙伴算法的改进算法用于操作系统分配和回收内存,而且内存块的单位较大,利于Linux使用的伙伴算法以页为单位.对于小块内存的分配和回收,伙伴算法就显得有些得不偿失了.
对于小块内存,一般采用slab算法,或者叫做slab机制.
Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为SunOS 操作系统首次引入的一种算法。Jeff的分配器是围绕对象缓存进行的。在内核中，会为有限的对象集（例如文件描述符和其他常见结构）分配大量内存。Jeff发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目而初始化的状态。例如，如果内存被分配给了一个互斥锁，那么只需在为互斥锁首次分配内存时执行一次互斥锁初始化函数（mutex_init）即可。后续的内存分配不需要执行这个初始化函数，因为从上次释放和调用析构之后，它已经处于所需的状态中了。
Linux slab分配器使用了这种思想和其他一些思想来构建一个在空间和时间上都具有高效性的内存分配器。
图中给出了 slab结构的高层组织结构。在最高层是 cache_chain，这是一个 slab 缓存的链接列表。这对于 best-fit算法非常有用，可以用来查找最适合所需要的分配大小的缓存（遍历列表）。cache_chain 的每个元素都是一个 kmem_cache 结构的引用（称为一个 cache）。它定义了一个要管理的给定大小的对象池。
每个缓存都包含了一个 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背后的动机
与传统的内存管理模式相比， slab缓存分配器提供了很多优点。首先，内核通常依赖于对小对象的分配，它们会在系统生命周期内进行无数次分配。slab缓存分配器通过对类似大小的对象进行缓存而提供这种功能，从而避免了常见的碎片问题。slab分配器还支持通用对象的初始化，从而避免了为同一目而对一个对象重复进行初始化。最后，slab分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。
本文地址：http://xnerv.wang/memory-allocation-buddy-system-and-slab-allocator/
转载自：内存分配-----伙伴算法和slab算法