0. 内存管理问题
内存碎片太小和管理内存碎片的效率问题
内存碎片:回收内存时,将内存块放入free链表中。因内存越分越小,内存块小而多。当需要一块大内存时,尽管此时空闲内存的总和可能足够满足需求,但是过于零散,没有一个合适的内存块。
原因:分配内存时,不能将相邻内存合并
解决办法:
- 小块内存单独分配(内存池),大内存由操作系统分配。[Nginx,STL采用]
- 伙伴算法
- slab算法
1. 伙伴算法
大致分为以下几步:
- 将空闲页面分为m个组。第1组1个块,第2组2个块,第三组4个块,...,第m组2^(m-1)块
- 每个组是一个链表,连接相同大小的块
- 伙伴块大小相等
分配内存
如果申请的内存大小为n,则向上取整为2的幂次数,定位到响应组,到组中(链表上)找空闲块分配出去;若没有空闲块,则到上一组找,直到找到为止,并将剩余的内存放到下面适当的组中。
合并内存
用完内存需要归还,根据实际内存块大小向上取整为2的幂次数,归入链表。
- 检测其伙伴块是否空闲
- 如果空闲就合并在一起,继续检测1
- 如果不空闲,直接归入链表
注:伙伴算法使用位图标记内存块的使用情况
特点
- 优点:解决外部碎片问题,尽量分配连续的页面,简单易行。
- 缺点:容易造成内存浪费,比如请求9K的内存,却要到16K的链表上找,尽管剩下的7K会下放到后面数组中,频繁的合并占用内存。可以设置低潮个数来解决这个问题。
slab算法
slab以内存池为思想,解决内部碎片问题,专门解决小内存问题。