程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> STL庫的內存配置器(allocator),stlallocator

STL庫的內存配置器(allocator),stlallocator

編輯:C++入門知識

STL庫的內存配置器(allocator),stlallocator


正在學習中,如果有錯,還請多多指教,根據不斷的理解,會進行更改,更改之前的樣子都會保留下來,記錄錯誤是最大的進步,嗯嗯!

具有次配置力的SGI空間配置器(SGI是STL的一種版本,也有其他的版本)

這裡我就不貼出來具體成員和接口的實現了,網上可以搜到STL的源碼

C++中,new一個變量可以分為兩個階段,1.分配空間 2.調用構造函數;delete變量也分為兩個步驟,1.調用析構函數 2.釋放空間

SGI的alloc將這兩部分分開,讓空間的分配釋放和構造析構由不同的函數調用,區分他們的操作

空間的分配和釋放由alloc::alloclate()  alloc::dealloclate()實現 構造和析構由alloc::construct() alloc::destory()函數負責,他們在頭文件

 1 #include<stl_alloc.h> //負責內存空間的配置和釋放 2 #include<stl_construct.h> //負責對象內容的構造和析構 這兩個頭文件都包含在#include<memory>當中

先講一下析構和構造的大概思路  

    • 這裡提到一個概念_type_traits<T>(這是個模板),首先通過value_type()獲得迭代器所指向對象的類型然後使用_type_traits進行類型判別,該對象是否是trivial(無關痛癢的) destructor,我對這裡的理解是,當迭代器所指對象的類型為POD(Plain Old Data)類型(PS:POD類型可以理解為傳統的C語言類型,就是int那一類的)是不需要專門調用析構函數的,等待系統自動釋放int所占用的空間即可,但當迭代器所指對象的類型為string對象(或者是其他你自己寫的類的對象),就不能依靠系統,需要調用專門的析構函數挨個析構。進行類型判別之後,就可以提高工作效率。(destory()對char*等類型也有相應的特化)
    • 構造函數就采用泛式構造,使用new進行構造
  • 下面講一下我對空間的配置與釋放的理解
    • C++對內存配置的基本操作依靠::operator new()和::operator delete()這兩個全局函數,這兩個函數只起到分配和釋放內存的作用,並不會調用構造函數和析構函數,他們就相當於C語言中的malloc()和free()函數,SGI正是以malloc()和free()進行空間的管理
    • 為了解決內存碎片的問題(當不斷地malloc空間時候,找到足夠大小的空間就拿來用,不可避免的的會產生內存碎片),於是就有了內存池的概念(內存池就是系統實現給開辟出一大塊空間等待使用,當需要空間的時候直接從內存池中取,當內存池中的內存也不夠使用時,再去Heap中開辟新的空間注入到內存池當中)

下面就比較重要了,SGI空間配置器采用了兩級配置器,分為第一級配置器和第二級配置器,第一級配置器就是拿malloc()實現的,第二級配置器采用了內存池的概念;

先來講第一級配置器,第一級配置器的實現就是用的malloc()(因為很重要所以多說幾遍),它會不斷地嘗試開辟內存,如果沒有內存可供開辟,就會嘗試釋放空間,然後再取嘗試開辟空間,第一級配置器比較重要的一點就是實現了類似C++中new-handler機制,用來處理內存不足的情況

內存池是使用鏈表結構實現的(個人感覺和哈希桶的方法類似),而不采用順序表,這樣就可以更好的解決內存碎片的問題了。

注意,這裡的freelists是鏈表!

注意!這裡之前寫的不太清楚,freelists是一個順序表,每一個單元下邊都連接這一個鏈表,當區塊被客端(client)使用就會像上圖一樣將區塊撥出去,然後改變指針指向下一個節點(就是采用頭刪)

每個鏈表節點所管理的區塊大小也是不一樣的,第一個節點管理8bytes,第二個16bytes。。。以此類推,最後一個節點管理128bytes,所以當超過128字節第二級配置器無法處理,就只好調用第一級配置器(內存不足時也會調用第一級配置器,因為第一級配置器裡面有內存不足處理例程)

下面給出鏈表節點的實現

1 union obj
2 {
3     union obj *free_list_link;
4     char client_data[1];//The client sees this;
5 };   

裡面的聯合體指針就是指向下一個節點的指針,那個char是指向實際內存塊的指針,采用聯合體可以減少內存的消耗,不必專門維護一個指向下一個節點的指針

當節點所指的內存塊是空閒塊時,obj被看做一個指針,指向下一個節點,當節點已經被分配了內存之後,被視為一個指針,指向實際區塊

當分配函數allocate()(alloc中申請內存的函數)發現沒有可用的區塊之後,就會去內存池中申請新的區塊(調用chunk_alloc()函數) ,默認申請20個區塊,當內存池的可用內存不足20個區塊,有多少給多少,如果連一個區塊的內存都不夠,就往內存池中注入內存(就是再去開辟一些放進內存池裡),就會去free_lists中遍歷,尋找內存池分配給自由鏈表但是卻處於空閒狀態的節點,將這些節點的存儲空間歸還個內存池,再遞歸去使用chunk_alloc()函數判斷是否空間夠分配;如果很不幸,還是不夠用,那麼注意!!會將內存池中剩余的小空間分配成低位區塊分給自由鏈表(就是說假如需要申請16個字節的節點區塊,不夠了,但是內存池中有8個字節的空間,當然不能夠浪費咯,趕緊分配出去)然後去往內存池中注入內存(就是再去開辟一些放進內存池裡)。

這個是《STL源碼剖析》裡的一個例子

當整個系統堆得內存都不夠了的時候,就chunk_malloc()就會四處尋找可用內存,嘗試釋放一些沒用的空間,如果還是無法找到就去調用第一級配置器,因為一級配置器裡有內存不足處理例程

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved