真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

STL-空間配置器-創(chuàng)新互聯(lián)

1、為什么需要空間配置器?

創(chuàng)新互聯(lián)建站是由多位在大型網(wǎng)絡公司、廣告設計公司的優(yōu)秀設計人員和策劃人員組成的一個具有豐富經(jīng)驗的團隊,其中包括網(wǎng)站策劃、網(wǎng)頁美工、網(wǎng)站程序員、網(wǎng)頁設計師、平面廣告設計師、網(wǎng)絡營銷人員及形象策劃。承接:成都網(wǎng)站設計、網(wǎng)站建設、外貿(mào)網(wǎng)站建設、網(wǎng)站改版、網(wǎng)頁設計制作、網(wǎng)站建設與維護、網(wǎng)絡推廣、數(shù)據(jù)庫開發(fā),以高性價比制作企業(yè)網(wǎng)站、行業(yè)門戶平臺等全方位的服務。

內(nèi)存碎片:

STL-空間配置器

頻繁分配小內(nèi)存導致分配不出來大內(nèi)存,這就是外碎片;并且頻繁分配小內(nèi)存效率低

比如,系統(tǒng)依次分配了16、8、16、4、8byte,還剩一個8byte未分配,這時要分配一個24byte的空間,系統(tǒng)回收兩個16byte,總的空間剩余40byte, 但是卻分配不出來一個24byte。

二級空間配置器是為頻繁分配小內(nèi)存而生的一種算法,其實就是消除一級空間配置器的外碎片問題

2、一級空間配置器和二級空間配置器

STL-空間配置器

如果申請的內(nèi)存大小超過128,那么空間配置器就自動調(diào)用一級空間配置器。反之調(diào)用二級空間配置器。而且在這里要說明的是空間配置器默認使用的是一級空間配置器。

一、一級空間配置器

    一級空間配置器是malloc-free的封裝,實現(xiàn)類似C++中new-handler機制:一旦申請空間不成功,在丟出bad-allloc異常之前,會先調(diào)用用戶自己指定的處理例程new-handler()。

   一級空間配置器的allocate()和reallocate()都是在調(diào)用malloc和realloc不成功時,改調(diào)用oom_malloc和oom_realloc,后兩者都能循環(huán)調(diào)用內(nèi)存不足處理例程,期待在某次調(diào)用之后可以獲得足夠內(nèi)存而達到目的 ,但是若處理例程未被用戶設定,oom_malloc和oom_realloc便會拋出bad-alloc的異?;蛴胑xit(1)終止程序。

代碼如下:

// 一級空間配置器(malloc/realloc/free)

template //非類型模板參數(shù)
class MallocAllocTemplate
{

//1:分配內(nèi)存成功,則直接返回
//2:若分配失敗,則檢查是否設置處理的句柄handler
//有則調(diào)用以后再分配,不斷重復這個過程,直到分配成功為止.
//沒有設置處理的句柄handler,則直接結(jié)束程序
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) //調(diào)用自定義的句柄處理函數(shù)handler釋放并分配內(nèi)存
 {
  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)()))(); //設置操作系統(tǒng)分配內(nèi)存失敗時的句柄處理函數(shù)
 {
  void(*tmp)() = MallocAllocHandler;
  MallocAllocHandler = f;
  return(tmp);
 }

};
template
ALLOC_FUN MallocAllocTemplate::MallocAllocHander = 0; //句柄函數(shù)初始化為0

二、二級空間配置器

     二級空間配置器是由一個內(nèi)存池和自由鏈表配合實現(xiàn)的

  STL-空間配置器

startFree相當于水位線,標志內(nèi)存池的大小

自由鏈表中其實是一個大小為16的指針數(shù)組,間隔為8的倍數(shù)。各自管理大小分別為8,16,24,32,40,48,56,64,72,80,88,96,104, 112,120,128 字節(jié)的小額區(qū)塊。在每個下標下掛著一個鏈表,把同樣大小的內(nèi)存塊鏈接在一起。類似于哈希桶。

代碼如下:

// 二級空間配置器
template
class DefaultallocTemplate //二級空間配置器
{
public:
 enum{ ALIGN = 8 }; //基準值對齊
 enum{ MAX_BYTES = 128 }; //大字節(jié)
 enum{ FREELISTS = MAX_BYTES / ALIGN }; //自由鏈表大小
 union obj
 {
  union obj* listLink; //自由鏈表中指向下一個內(nèi)存塊的指針
  char clientData[1]; //調(diào)試用
 };
 static size_t FreeListIndex(size_t bytes) //得到所需內(nèi)存塊在自由鏈表中的下標
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }
 static size_t RoundUpNum(size_t bytes) //得到內(nèi)存塊大小的向上對齊數(shù)(8的倍數(shù))
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }
 static obj* FreeList[FREELISTS]; //維護自由鏈表
 static char* startFree; //水位線(維護內(nèi)存池)
 static char* endFree; //池底
 static size_t heapSize;

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

  if (FreeList[index]) //自由鏈表上有內(nèi)存塊
  {
   obj* ret = FreeList[index]; //取走當前下標的第一個給用戶
   FreeList[index] = ret->listLink;  //FreeList[index]指向下一個
  }
  else  //若自由鏈表沒有,則調(diào)用refill從內(nèi)存池填充自由鏈表并返回內(nèi)存池的第一個內(nèi)存塊
  {
   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::Deallocate(p, size);
  else //放回二級空間配置器的自由鏈表
  {
   size_t index = FreeListIndex(size);
   obj* tmp = (obj*)p;
   tmp->listLink = FreeList[index];
   Freelist[index] = tmp;
  }
 }

 //從內(nèi)存池拿出內(nèi)存填充自由鏈表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申請20個size大小的內(nèi)存塊
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1) //只分配到一個內(nèi)存
  {
   return chunk;
  }

  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //將剩余內(nèi)存塊掛到自由鏈表上
  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;
 }

 //從內(nèi)存池中分配大塊內(nèi)存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的內(nèi)存塊
  size_t Needbytes = size * nobjs; //所總共需要的內(nèi)存塊
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不夠分配總size大小,但是夠分配單個size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else    //一個內(nèi)存塊都分配不出來
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系統(tǒng)申請2倍Needbytes加上已分配的heapsize/8的內(nèi)存到內(nèi)存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //從系統(tǒng)堆中分配內(nèi)存失敗
   {
    //到后面更大的自由鏈表中去取
    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);
     }
    }
    //山窮水盡
    //最后的一根救命稻草,找一級空間配置器分配內(nèi)存
    //(其他進程歸還內(nèi)存,調(diào)用自定義的句柄處理函數(shù)釋放內(nèi)存)
    startFree = MallocAllocTemplate::Allocate(getBytes);
   }
   heapSize += getBytes; //從系統(tǒng)堆分配的總字節(jié)數(shù)(可以用于下次分配時進行調(diào)節(jié))
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存
  }
  return ret;
 }
};
template
typename DefaultAllocTemplate::obj*
DefaultAllocTemplate::FreeList[FREELISTSIZE] = { 0 };

template
char* DefaultAllocTemplate::startFree = 0;

template
char* DefaultAllocTemplate::endFree = 0;

template
size_t DefaultAllocTemplate::heapSize = 0;

部分代碼解釋:

static size_t FreeListIndex(size_t bytes)//得到所需內(nèi)存塊在自由鏈表中的下標
 {
  return ((bytes + ALIGN - 1) / ALIGN - 1);
 }

   此函數(shù)就是找到需要分配的內(nèi)存塊在自由鏈表中的什么地方,((bytes + ALIGN - 1) / ALIGN - 1),把要分配的內(nèi)存大小提升一個數(shù)量級(+7,每間隔8為一個數(shù)量級),然后除以8,減1,剛好能找到對應的下標,取出一塊內(nèi)存塊給用戶。

static size_t RoundUpNum(size_t bytes) //得到內(nèi)存塊大小的向上對齊數(shù)(8的倍數(shù))
 {
  return (bytes + ALIGN - 1)&~(ALIGN - 1);
 }

    此函數(shù)是得到所需內(nèi)存塊大小的向上對齊數(shù)。在自由鏈表中,內(nèi)存塊大小總是8的倍數(shù),但是并不是每次所需內(nèi)存大小都是8的倍數(shù)。所以就要取比所需大小大或相等的內(nèi)存塊,這就是向上取整。&~(ALIGN - 1)相當于將低8位置0,只取高8位,高8位總是8的倍數(shù),正好符合題意。

很關鍵的兩個函數(shù)static void* Refill(size_t size)和static char* ChunkAlloc(size_t size, int& nobjs):

//從內(nèi)存池拿出內(nèi)存填充自由鏈表
 static void* Refill(size_t size)
 {
  int nobjs = 20;//申請20個size大小的內(nèi)存塊
  char* chunk = ChunkAlloc(size, nobjs);
  if (nobjs == 1)//只分配到一個內(nèi)存
  {
   return chunk;
  }

  size_t index = FreeListIndex(size);
  obj* cur = chunk + size;
  obj* next = NULL;

  //將剩余內(nèi)存塊掛到自由鏈表上
  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-空間配置器

 當在自由鏈表的下標處沒有內(nèi)存塊時,我們就必須調(diào)用refill去填充自由鏈表。申請時一般一次性申請20個內(nèi)存塊大小的內(nèi)存。通過移動startFree指針將內(nèi)存池內(nèi)的一段內(nèi)存給“切割”出來,然后切成小塊掛在自由鏈表下面。返回第一塊內(nèi)存塊給用戶,其余的都掛在自由鏈表下,方便下次分配,根據(jù)局部性原理,這將極大地提升了分配內(nèi)存空間的效率。

//從內(nèi)存池中分配大塊內(nèi)存
 static char* ChunkAlloc(size_t size, int& nobjs)
 {
  char* ret = NULL;
  size_t Leftbytes = endFree - startFree; //剩余的內(nèi)存塊
  size_t Needbytes = size * nobjs; //所總共需要的內(nèi)存塊
  if (Leftbytes >= Needbytes)
  {
   ret = startFree;
   startFree += Needbytes;
  }
  else if (Leftbytes >= size) //不夠分配總size大小,但是夠分配單個size大小的
  {
   ret = startFree;
   nobjs = Leftbytes / size;
   startFree += nobjs*size;
  }
  else    //一個內(nèi)存塊都分配不出來
  {
   if (Leftbytes > 0)
   {
    size_t index = FreeListIndex(Leftbytes);
    ((obj*)startFree)->listLink = FreeList[index];
    FreeList[index] = (obj*)startFree;
    startFree = NULL;
   }
   //向操作系統(tǒng)申請2倍Needbytes加上已分配的heapsize/8的內(nèi)存到內(nèi)存池
   size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4);
   startFree = (char*)malloc(getBytes);
   if (startFree == NULL) //從系統(tǒng)堆中分配內(nèi)存失敗
   {
    //到后面更大的自由鏈表中去取
    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);
     }
    }
    //山窮水盡
    //最后的一根救命稻草,找一級空間配置器分配內(nèi)存
    //(其他進程歸還內(nèi)存,調(diào)用自定義的句柄處理函數(shù)釋放內(nèi)存)
    startFree = MallocAllocTemplate::Allocate(getBytes);
   }
   heapSize += getBytes; //從系統(tǒng)堆分配的總字節(jié)數(shù)(可以用于下次分配時進行調(diào)節(jié))
   endFree = startFree + getBytes;

   return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存
  }
  return ret;
 }

ChunkAlloc要做的就是去找操作系統(tǒng)要內(nèi)存,一次性要20個,但是要考慮很多情況:

(1)內(nèi)存池里有足夠20塊大的內(nèi)存

(2)內(nèi)存池里有小于20塊大于等于1塊的內(nèi)存大小

(3)內(nèi)存池里連1塊內(nèi)存那么大的都沒有

具體這樣做:

 (1)如果有足夠的內(nèi)存,那么一次性就給20塊,返回第一塊給用戶,其余的掛在自由鏈表上。
 (2)只有一塊或者多塊,返回一塊給用戶。
 (3) 沒有內(nèi)存了,找操作系統(tǒng)要。
 (4)操作系統(tǒng)沒有了,啟用最后一根救命稻草,調(diào)用一級空間配置器,通過句柄函數(shù)釋放內(nèi)存,分配內(nèi)存。

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內(nèi)外云服務器15元起步,三天無理由+7*72小時售后在線,公司持有idc許可證,提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢,專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應用場景需求。


網(wǎng)站題目:STL-空間配置器-創(chuàng)新互聯(lián)
本文鏈接:http://weahome.cn/article/dpodcd.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部