温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

STL-空间配置器

发布时间:2020-08-06 04:11:27 来源:网络 阅读:634 作者:追梦途中 栏目:编程语言

1、为什么需要空间配置器?

内存碎片:

STL-空间配置器

频繁分配小内存导致分配不出来大内存,这就是外碎片;并且频繁分配小内存效率低

比如,系统依次分配了16、8、16、4、8byte,还剩一个8byte未分配,这时要分配一个24byte的空间,系统回收两个16byte,总的空间剩余40byte, 但是却分配不出来一个24byte。

二级空间配置器是为频繁分配小内存而生的一种算法,其实就是消除一级空间配置器的外碎片问题


2、一级空间配置器和二级空间配置器

STL-空间配置器

如果申请的内存大小超过128,那么空间配置器就自动调用一级空间配置器。反之调用二级空间配置器。而且在这里要说明的是空间配置器默认使用的是一级空间配置器。

一、一级空间配置器

     一级空间配置器是malloc-free的封装,实现类似C++中new-handler机制:一旦申请空间不成功,在丢出bad-allloc异常之前,会先调用用户自己指定的处理例程new-handler()。

    一级空间配置器的allocate()和reallocate()都是在调用malloc和realloc不成功时,改调用oom_malloc和oom_realloc,后两者都能循环调用内存不足处理例程,期待在某次调用之后可以获得足够内存而达到目的 ,但是若处理例程未被用户设定,oom_malloc和oom_realloc便会抛出bad-alloc的异常或用exit(1)终止程序。

代码如下:

// 一级空间配置器(malloc/realloc/free)

template<int inst> //非类型模板参数
class MallocAllocTemplate
{

//1:分配内存成功,则直接返回
//2:若分配失败,则检查是否设置处理的句柄handler
//有则调用以后再分配,不断重复这个过程,直到分配成功为止.
//没有设置处理的句柄handler,则直接结束程序

public:
 static void* Allocate(size_t size) //用于分配空间

 {
  void* ret = malloc(size);
  if (0 == ret)
  {
   ret = OomMalloc(size);
  }
  return ret;
 }

 static void Deallocate(void* p) //收回
 {
  free(p);
 }

 static void* Reallocate(void* p, size_t newsize) //用于指定地址重新分配空间
 {
  void* ret = realloc(p, newsize);
  if (ret == 0)
  {
   ret = OomRealloc(p, newsize);
  }
  return ret;
 }
private:
 static void* OomMalloc(size_t size)  //调用自定义的句柄处理函数handler释放并分配内存
 {
  ALLOC_FUN handler;
  void* ret;
  while (1)
  {
   handler = MallocAllocHandler;
   if (0 == handler)
   {
    cout << "out of memory" << endl;
    exit(-1);
   }

   handler();
   ret = malloc(size);
   if (ret)
   {
    return(ret);
   }
  }
 }

 static void* OomRealloc(void*p, size_t newsize)
 {
  ALLOC_FUN handler;
  void* ret;
  while (1)
  {
   handler = MallocAllocHandler;
   if (0 == handler)
   {
    cout << "out of memory" << endl;
    exit(-1);
   }

   handler();
   ret = realloc(newsize);
   if (ret)
   {
    return(ret);
   }
  }
 }
 static void(*SetMallocHandler(void(*f)()))(); //设置操作系统分配内存失败时的句柄处理函数
 {
  void(*tmp)() = MallocAllocHandler;
  MallocAllocHandler = f;
  return(tmp);
 }
 
};
template<int inst>
ALLOC_FUN MallocAllocTemplate<inst>::MallocAllocHander = 0; //句柄函数初始化为0



二、二级空间配置器

      二级空间配置器是由一个内存池和自由链表配合实现的

   STL-空间配置器

startFree相当于水位线,标志内存池的大小

自由链表中其实是一个大小为16的指针数组,间隔为8的倍数。各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104, 112,120,128 字节的小额区块。在每个下标下挂着一个链表,把同样大小的内存块链接在一起。类似于哈希桶。

代码如下:

// 二级空间配置器
template<bool threads,int inst>
class DefaultallocTemplate //二级空间配置器
{
public:
 enum{ ALIGN = 8 }; //基准值对齐
 enum{ MAX_BYTES = 128 }; //最大字节
 enum{ FREELISTS = MAX_BYTES / ALIGN }; //自由链表大小
 union obj
 {
  union obj* listLink; //自由链表中指向下一个内存块的指针
  char clientData[1]; //调试用
 };
 static size_t FreeListIndex(size_t bytes) //得到所需内存块在自由链表中的下标
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }
 static size_t RoundUpNum(size_t bytes) //得到内存块大小的向上对齐数(8的倍数)
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }
 static obj* FreeList[FREELISTS];  //维护自由链表
 static char* startFree;  //水位线(维护内存池)
 static char* endFree;  //池底
 static size_t heapSize;


 static void* Allocate(size_t size)
 {
  if (size > MAX_BYTES)
  {
   return MallocAllocTemplate<inst>::Allocate(size);
  }
  void* ret = NULL;
  size_t index = FreeListIndex(size);

  if (FreeList[index]) //自由链表上有内存块
  {
   obj* ret = FreeList[index]; //取走当前下标的第一个给用户
   FreeList[index] = ret->listLink;  //FreeList[index]指向下一个
  }
  else   //若自由链表没有,则调用refill从内存池填充自由链表并返回内存池的第一个内存块
  {
   return Refill(RoundUpNum(size));
  }
  return ret;
 }

 static void* Reallocate(void* p, size_t oldsize, size_t newsize)
 {
  void* ret = NULL;
  if (oldsize > (size_t)MAX_BYTES&&newsize > (size_t)MAX_BYTES)
   return (realloc(p, newsize));
  if (RoundUpNum(oldsize) == RoundUpNum(newsize))
   return p;
  ret = Allocate(newsize);
  size_t copysize = oldsize > newsize ? newsize : oldsize;
  memcopy(ret, p, copysize);
  DeAllocate(p, oldsize);
  return ret;
 }
 static void Deallocate(void* p, size_t size)
 {
  if (size> MAX_BYTES) //如果大于MAX_BYTES直接交还给一级空间配置器释放
   return MallocAllocTemplate<inst>::Deallocate(p, size);
  else //放回二级空间配置器的自由链表
  {
   size_t index = FreeListIndex(size);
   obj* tmp = (obj*)p;
   tmp->listLink = FreeList[index];
   Freelist[index] = tmp;
  }
 }

 
 //从内存池拿出内存填充自由链表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申请20个size大小的内存块
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1) //只分配到一个内存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //将剩余内存块挂到自由链表上
  FreeList[index] = cur;
  for (int i = 1; i < nobjs-1; ++i)
  {
   next=(obj*)((char*)cur +size);
   cur->listLink = next;
   cur = next;
  }
  cur->listLink = NULL;
  return chunk;
 }
 
 //从内存池中分配大块内存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的内存块
  size_t Needbytes = size * nobjs; //所总共需要的内存块
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不够分配总size大小,但是够分配单个size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else     //一个内存块都分配不出来
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系统申请2倍Needbytes加上已分配的heapsize/8的内存到内存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //从系统堆中分配内存失败
   {
    //到后面更大的自由链表中去取
    for (int i = size; i < MAX_BYTES; i += ALIGN)
    {
     size_t index = FreeList[FreeListIndex(i)];
     if (FreeList[index])
     {
      startFree = FreeList[index];
      FreeList[index] = FreeList[index]->listLink;
      endFree = startFree + size;
      return ChunkAlloc(size, nobjs);
     }
    }
    //山穷水尽
    //最后的一根救命稻草,找一级空间配置器分配内存
    //(其他进程归还内存,调用自定义的句柄处理函数释放内存)

    startFree = MallocAllocTemplate<inst>::Allocate(getBytes);
   }
   heapSize += getBytes; //从系统堆分配的总字节数(可以用于下次分配时进行调节)
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //递归调用获取内存
  }
  return ret;
 }
};
template<bool threads, int inst>
typename DefaultAllocTemplate<threads, inst>::obj*
DefaultAllocTemplate<threads, inst>::FreeList[FREELISTSIZE] = { 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;


部分代码解释:

static size_t FreeListIndex(size_t bytes)//得到所需内存块在自由链表中的下标
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }

    此函数就是找到需要分配的内存块在自由链表中的什么地方,((bytes + ALIGN - 1) / ALIGN - 1),把要分配的内存大小提升一个数量级(+7,每间隔8为一个数量级),然后除以8,减1,刚好能找到对应的下标,取出一块内存块给用户。


static size_t RoundUpNum(size_t bytes) //得到内存块大小的向上对齐数(8的倍数)
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }

     此函数是得到所需内存块大小的向上对齐数。在自由链表中,内存块大小总是8的倍数,但是并不是每次所需内存大小都是8的倍数。所以就要取比所需大小大或相等的内存块,这就是向上取整。&~(ALIGN - 1)相当于将低8位置0,只取高8位,高8位总是8的倍数,正好符合题意。


很关键的两个函数static void* Refill(size_t size)和static char* ChunkAlloc(size_t size, int& nobjs):

//从内存池拿出内存填充自由链表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申请20个size大小的内存块
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1)//只分配到一个内存
  {
   return chunk;
  }
 
  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //将剩余内存块挂到自由链表上
  FreeList[index] = cur;
  for (int i = 1; i < nobjs-1; ++i)
  {
   next=(obj*)((char*)cur +size);
   cur->listLink = next;
   cur = next;
  }
  cur->listLink = NULL;
  return chunk;
 }


   STL-空间配置器

 当在自由链表的下标处没有内存块时,我们就必须调用refill去填充自由链表。申请时一般一次性申请20个内存块大小的内存。通过移动startFree指针将内存池内的一段内存给“切割”出来,然后切成小块挂在自由链表下面。返回第一块内存块给用户,其余的都挂在自由链表下,方便下次分配,根据局部性原理,这将极大地提升了分配内存空间的效率



//从内存池中分配大块内存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的内存块
  size_t Needbytes = size * nobjs; //所总共需要的内存块
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不够分配总size大小,但是够分配单个size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else     //一个内存块都分配不出来
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系统申请2倍Needbytes加上已分配的heapsize/8的内存到内存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //从系统堆中分配内存失败
   {
    //到后面更大的自由链表中去取
    for (int i = size; i < MAX_BYTES; i += ALIGN)
    {
     size_t index = FreeList[FreeListIndex(i)];
     if (FreeList[index])
     {
      startFree = FreeList[index];
      FreeList[index] = FreeList[index]->listLink;
      endFree = startFree + size;
      return ChunkAlloc(size, nobjs);
     }
    }
    //山穷水尽
    //最后的一根救命稻草,找一级空间配置器分配内存
    //(其他进程归还内存,调用自定义的句柄处理函数释放内存)

    startFree = MallocAllocTemplate<inst>::Allocate(getBytes);
   }
   heapSize += getBytes; //从系统堆分配的总字节数(可以用于下次分配时进行调节)
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //递归调用获取内存
  }
  return ret;
 }

ChunkAlloc要做的就是去找操作系统要内存,一次性要20个,但是要考虑很多情况:

(1)内存池里有足够20块大的内存

(2)内存池里有小于20块大于等于1块的内存大小

(3)内存池里连1块内存那么大的都没有

具体这样做:

 (1)如果有足够的内存,那么一次性就给20块,返回第一块给用户,其余的挂在自由链表上。
 (2)只有一块或者多块,返回一块给用户。
 (3) 没有内存了,找操作系统要。
 (4)操作系统没有了,启用最后一根救命稻草,调用一级空间配置器,通过句柄函数释放内存,分配内存。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI