一、 为什么要有空间配置器:
1、小块内存带来的内存碎片问题
单从内存分配的角度来讲,由于频繁分配、释放小块内存容易在堆中造成外碎片(极端情况下:堆中空闲的总量满足一个要求,但是这些空闲的块都不连续,导致任何一个单独的空闲的块都无法满足请求)
2、小块内存频繁申请释放带来的性能问题:
(1)开辟空间的时候,分配器会找一块空闲给用户,找空闲块需要时间,尤其是在外碎片比较多的情况。如果分配器找不到,就要考虑假碎片现象(释放的小块内存没有合并),这时候就要将这些已经释放的空闲块合并,这也需要时间。
(2)malloc在开辟空间的时候,这些空间会带有一些附加的信息,这样也会造成空间的利用率降低,尤其频繁申请小块内存时。
为了解决上述问题,STL提出了内存池的概念,内存池最基本的思想就是一次向heap申请一块很大的内存(内存池),如果申请小块内存就直接到内存池中去要,有效解决上述问题。
二、 STL的空间配置器(SGI版)
STL的空间配置器分两级,一级空间配置器(__malloc_alloc_template)和二级空间配置器(__default_alloc_template)。在STL中,默认分配的内存大于128这季节,调用一级空间配置器申请内存;如果小于等于128字节则认为是小块内存,去内存池中申请内存。一级空间配置器比较简单,直接封装了malloc()和free()处理。
1、一级空间配置器
(1)malloc()申请内存。
(2)malloc()失败后,调用oom_malloc():
a 如果客户端没有设置内存不足处理机制,则抛出bad_alloc。
b 设置了内存不足机制,调用内存处理机制,直到获取到一块足够内存。内存处理机制设置不当会存在死循环问题。
typedef void(*MALLOCALLOC)(); //将void (*)() 重命名成MALLOCALLOC
template<int inst>
class _MallocAllocTemplate
{
private:
static void* _OomMalloc(size_t); //malloc失败的时候调用的函数
static MALLOCALLOC _MallocAllocOomHandler; //函数指针,内存不足的时候的处理机制
public:
static void* _Allocate(size_t n) //分配空间n个字节的空间
{
void *result=0;
result = malloc(n);
if (0 == result) //若果malloc失败,则就调OOM_malloc
_OomMalloc(n);
return result;
}
static void _DeAllocate(void *p) //释放这块空间
{
free(p);
}
static MALLOCALLOC _SetMallocHandler(MALLOCALLOC f) //这是一个函数,参数是一个函数指针,返回值也是一个函数指针
{
MALLOCALLOC old = _MallocAllocOomHandler;
_MallocAllocOomHandler = f; //将内存分配失败的句柄设置为f(让它指向一个内存失败了,让系统去释放其他地方空间的函数)
return old;
}
};
template<int inst>
void(* _MallocAllocTemplate<inst>::_MallocAllocOomHandler)()=0; //默认不设置内存不足处理机制
template<int inst>
void* _MallocAllocTemplate<inst>::_OomMalloc(size_t n)
{
MALLOCALLOC _MyMallocHandler; //定义一个函数指针
void *result;
while (1)
{
_MyMallocHandler = _MallocAllocOomHandler;
if (0 == _MyMallocHandler) //没有设置内存不足处理机制
throw std::bad_alloc(); //则抛出异常
(*_MyMallocHandler)(); //调用内存不足处理的函数,申请释放其他地方的内存
if (result = malloc(n)) //重新申请内存
break;
}
return result; //申请成功时,则返回这块内存的地址
}
typedef _MallocAllocTemplate<0> malloc_alloc;
2、二级空间配置器
二级空间配置器使用内存池+自由链表的形式避免了小块内存带来的碎片化,提高了分配效率,提高利用率。假设分配8个字节大小的空间,他会去内存池分配多个8个字节大小的内存块,多余的挂在自由链表上。下一次需要8个字节,就可以去自由链表上去取。如果回收8个字节,则直接挂在自由链表。
为了方便管理,二级空间配置器在分配的时候都是以8的倍数对齐。这样只需维护16个free_list就可以了,free_list的16个节点分别管理大小为8,…128字节大小的内存即可。
自由链表的结点类型:
union _Obj
{
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};
内存池模型:
为了将自由链表的结点串起来,又不引入额外的指针,自由链表下面挂的最小的内存块是8个字节,足够存放一个地址,因此可以在这些内存块中存放其他内存块的地址,即将内存块连接起来。
二级空间配置器的类:
enum { _ALIGN = 8 }; //按照基准值8的倍数进行内存操作
enum { _MAXBYTES = 128 }; //自由链表中最大的块的大小是128
enum { _NFREELISTS = 16 }; //自由链表的长度,等于_MAXBYTES/_ALIGN
template <bool threads, int inst> //非模板类型参数
class _DefaultAllocTemplate
{
union _Obj //自由链表结点的类型
{
_Obj* _freeListLink; //指向自由链表结点的指针
char _clientData[1]; //this client sees
};
private:
static char* _startFree; //内存池的头指针
static char* _endFree; //内存池的尾指针
static size_t _heapSize; //记录内存池已经向系统申请了多大的内存
static _Obj* volatile _freeList[_NFREELISTS]; //自由链表
private:
static size_t _GetFreeListIndex(size_t bytes) //得到这个字节对应在自由链表中应取的位置
{
return (bytes +(size_t) _ALIGN - 1) / (size_t)_ALIGN - 1;
}
static size_t _GetRoundUp(size_t bytes) //对这个字节向上取成8的倍数
{
return (bytes + (size_t)_ALIGN - 1)&(~(_ALIGN-1)); //将n向上取成8的倍数
}
static void* _Refill(size_t n); //在自由链表中申请内存,n表示要的内存的大小
static char* _chunkAlloc(size_t size,int& nobjs); //在内存池中申请内存nobjs个对象,每个对象size个大小
public:
static void* Allocate(size_t n); //n要大于0
static void DeAllocate(void *p,size_t n); //n要不等于0
};
假设申请n(<= 128)个字节:
1、将n上调至8的倍数,在自由链表的相应结点下面找,如果该结点下面挂有未使用的内存,摘下来返回这块空间的地址。否则调用refill()去内存池申请内存。
2、向内存池申请的时候多申请几个,STL默认一次申请nobjs=20个,将多余的挂在自由链表上,这样能够提高效率。
进入refill函数后,先调用chunk_alloc(n,nobjs)函数去内存池申请内存,如果成功,返回refill函数。
如果nobjs=1,表示内存池只够分配一个,这时返回这个地址,否则表示nobjs大于1,将多余的内存块挂到自由链表上。
3、进入chunk_alloc(n,nobjs)有三种情况:
3.1剩余空间足够,直接分配好返回。
3.2剩余空间够n,但不够n*nobjs,此时nobjs=剩余空间/n,返回。
3.3内存池剩余空间不够一个n,向heap申请内存,在申请前将内存池中的剩余内存挂到自由链表上,之后向heap申请。
3.3.1申请成功,调一次chunk——alloc()重新分配。
3.3.2不成功,去自由链表中查看是否有大于n的空间,有的话返还给内存池,调用chunk_alloc重新分配。
3.3.3没有的话,调用1级分配器,是否有内存不足处理机制。
enum { _ALIGN = 8 }; //按照基准值8的倍数进行内存操作
enum { _MAXBYTES = 128 }; //自由链表中最大的块的大小是128
enum { _NFREELISTS = 16 }; //自由链表的长度,等于_MAXBYTES/_ALIGN
template <bool threads, int inst> //非模板类型参数
class _DefaultAllocTemplate
{
union _Obj //自由链表结点的类型
{
_Obj* _freeListLink; //指向自由链表结点的指针
char _clientData[1]; //this client sees
};
private:
static char* _startFree; //内存池的头指针
static char* _endFree; //内存池的尾指针
static size_t _heapSize; //记录内存池已经向系统申请了多大的内存
static _Obj* volatile _freeList[_NFREELISTS]; //自由链表
private:
static size_t _GetFreeListIndex(size_t bytes) //得到这个字节对应在自由链表中应取的位置
{
return (bytes +(size_t) _ALIGN - 1) / (size_t)_ALIGN - 1;
}
static size_t _GetRoundUp(size_t bytes) //对这个字节向上取成8的倍数
{
return (bytes + (size_t)_ALIGN - 1)&(~(_ALIGN-1)); //将n向上取成8的倍数
}
static void* _Refill(size_t n); //在自由链表中申请内存,n表示要的内存的大小
static char* _chunkAlloc(size_t size,int& nobjs); //在内存池中申请内存nobjs个对象,每个对象size个大小
public:
static void* Allocate(size_t n); //n要大于0
static void DeAllocate(void *p,size_t n); //n要不等于0
};
template<bool threads,int inst>
char* _DefaultAllocTemplate<threads,inst>::_startFree = 0; //内存池的头指针
template<bool threads, int inst>
char* _DefaultAllocTemplate<threads, inst>::_endFree=0; //内存池的尾指针
template<bool threads, int inst>
size_t _DefaultAllocTemplate<threads, inst>::_heapSize = 0; //记录内存池已经向系统申请了多大的内存
template<bool threads, int inst>
typename _DefaultAllocTemplate<threads, inst>::_Obj* volatile //前面加typename表示后面是个类型
_DefaultAllocTemplate<threads, inst>::_freeList[_NFREELISTS] = {0}; //自由链表
template<bool threads, int inst>
void* _DefaultAllocTemplate<threads, inst>::Allocate(size_t n) //分配空间
{
void *ret;
//先判断要分配的空间大小是不是大于128个字节
if (n>_MAXBYTES) //大于_MAXBYTES个字节则认为是大块内存,直接调用一级空间配置器
{
ret = malloc_alloc::_Allocate(n);
}
else //否则就去自由链表中找
{
_Obj* volatile *myFreeList = _freeList+_GetFreeListIndex(n); //让myFreeList指向自由链表中n向上取8的整数倍
_Obj* result = *myFreeList;
if (result == 0) //这个结点下面没有挂内存,则就要去内存池中申请
{
ret = _Refill(_GetRoundUp(n)); //到内存池中申请
}
else //已经在自由链表上找到了内存
{
*myFreeList= result->_freeListLink; //把第二块空间的地址放到自由链表上
ret = result;
}
}
return ret;
}
template<bool threads, int inst>
void _DefaultAllocTemplate<threads, inst>::DeAllocate(void *p, size_t n) //回收空间
{
//先判断这个字节的大小
if (n > _MAXBYTES) //如果n大于自由链表中结点所能挂的最大内存块,则就直接调用一级指针的释放函数
{
malloc_alloc::_DeAllocate(p);
}
else //将这块内存回收到自由链表中
{
_Obj* q = (_Obj*)p;
_Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(n);
q->_freeListLink = *myFreeList;
*myFreeList = q;
}
}
template<bool threads,int inst>
void* _DefaultAllocTemplate<threads, inst>::_Refill(size_t n) //n表示要申请的字节个数
{
int nobjs = 20; //向内存池申请的时候一次性申请20个
char* chunk = _chunkAlloc(n,nobjs); //因为现在链表中没有,所以要想内存池中申请,多余的再挂到自由链表下面
if (1 == nobjs) //只分配到了一个对象
{
return chunk;
}
_Obj* ret = (_Obj*)chunk; //将申请的第一个对象作为返回值
_Obj* volatile *myFreeList = _freeList+ _GetFreeListIndex(n);
*myFreeList =(_Obj*)(chunk+n); //将第二个对象的地址放到自由链表中
_Obj* cur= *myFreeList;
_Obj* next=0;
cur->_freeListLink = 0;
for (int i = 2; i < nobjs; ++i) //将剩下的块挂到自由链表上
{
next= (_Obj*)(chunk + n*i);
cur->_freeListLink = next;
cur = next;
}
cur->_freeListLink = 0;
return ret;
}
template<bool threads, int inst>
char* _DefaultAllocTemplate<threads, inst>::_chunkAlloc(size_t size, int& nobjs) //向系统中申请内存
{
char* result = 0;
size_t totalBytes = size*nobjs; //总共请求的内存大小
size_t leftBytes = _endFree - _startFree; //内存池剩余的大小
if (leftBytes>=totalBytes) //如果剩余的大小大于等于申请的大小,则返回这个这内存
{
result = _startFree;
_startFree += totalBytes;
return result;
}
else if (leftBytes>size) //如果剩余的内存足够分配一个size,
{
nobjs=(int)(leftBytes/size);
result = _startFree;
_startFree +=(nobjs*size);
return result;
}
else //内存池中的内存已经不够一个size了
{
size_t NewBytes = 2 * totalBytes+_GetRoundUp(_heapSize>>4); //内存池要开辟的新的容量
if (leftBytes >0) //剩余的内存挂到自由链表上
{
_Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(leftBytes);
((_Obj*)_startFree)->_freeListLink = *myFreeList;
*myFreeList = (_Obj*)_startFree;
}
//开辟新的内存
_startFree = (char*)malloc(NewBytes);
if (0 == _startFree) //如果开辟失败
{
//如果开辟失败的话,则表明系统已经没有内存了,这时候我们就要到自由链表中找一块比n还大的内存块,如果还没有的话,那就掉一级空间配置器
for (size_t i = size; i <(size_t)_MAXBYTES;i+=(size_t)_ALIGN)
{
_Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(i);
_Obj* p =*myFreeList;
if (NULL != p) //在自由链表找到一块内存块
{
_startFree =(char*)p;
//将这个内存块摘下来给内存池
*myFreeList = p->_freeListLink;
_endFree = _startFree + i;
return _chunkAlloc(size, nobjs); //内存池开辟好的话,就再调一次chunk分配内存
}
}
//要是再找不到的话,就调一级空间配置器,其中有内存不足处理机制,要是还不行的话,他会自动抛出异常
_endFree = NULL;
_startFree=(char*)malloc_alloc::_Allocate(NewBytes);
}
//开辟成功的,就更新heapSize(记录总共向系统申请了多少内存),,更新_endFree
_heapSize += NewBytes;
_endFree = _startFree + NewBytes;
return _chunkAlloc(size, nobjs); //内存池开辟好的话,就再调一次chunk分配内存
}
}
typedef _DefaultAllocTemplate<0,0> default_alloc;
三、空间配置器其他问题
1、空间配置器中的所有函数和变量都是静态的,所以程序结束后才会被释放。二级空间配置器中没有将申请的内存还给操作系统,知识将他们挂在自由链表,当程序结束时才会归还到操作系统。
2、由于没有将内存归还,所以会出现两种极端情况。
2.1不断开辟小块内存,最后整个heap挂在自由链表没有使用,再想要开辟一个大的内存失败。
2.2不断的开辟char,最后将整个heap全挂在自由链表第一个节点后面,再开辟一个6字节的内存,失败。
3、二级空间配置器造成内存碎片化问题,极端情况下一直申请char,浪费7/8的空间。