91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

STL-空間配置器

發布時間：2020-08-06 04:11:27 來源：網絡 閱讀：631 作者：追夢途中 欄目：編程語言

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
助
手
芷江| 屯门区| 侯马市| 瑞昌市| 汾阳市| 遂平县| 夏津县| 色达县| 新乡县| 长葛市| 郎溪县| 古浪县| 来宾市| 禄丰县| 青川县| 上犹县| 郎溪县| 阳东县| 克东县| 揭东县| 小金县| 泊头市| 五华县| 扎鲁特旗| 彭水| 海宁市| 祁阳县| 左贡县| 龙陵县| 斗六市| 招远市| 石阡县| 察雅县| 临澧县| 崇义县| 金山区| 闵行区| 合肥市| 涞水县| 澎湖县| 龙山县|