正在學習中,如果有錯,還請多多指教,根據不斷的理解,會進行更改,更改之前的樣子都會保留下來,記錄錯誤是最大的進步,嗯嗯!
STL源碼剖析簡體中文完整版(高清晰掃描帶目錄)PDF 下載地址 http://www.linuxidc.com/Linux/2016-04/129761.htm
具有次配置力的SGI空間配置器(SGI是STL的一種版本,也有其他的版本)
這裡我就不貼出來具體成員和接口的實現了,網上可以搜到STL的源碼
C++中,new一個變量可以分為兩個階段,1.分配空間 2.調用構造函數;delete變量也分為兩個步驟,1.調用析構函數 2.釋放空間
SGI的alloc將這兩部分分開,讓空間的分配釋放和構造析構由不同的函數調用,區分他們的操作
空間的分配和釋放由alloc::alloclate() alloc::dealloclate()實現 構造和析構由alloc::construct() alloc::destory()函數負責,他們在頭文件
#include<stl_alloc.h> //負責內存空間的配置和釋放 2 #include<stl_construct.h> //負責對象內容的構造和析構 這兩個頭文件都包含在#include<memory>當中
先講一下析構和構造的大概思路
下面就比較重要了,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()就會四處尋找可用內存,嘗試釋放一些沒用的空間,如果還是無法找到就去調用第一級配置器,因為一級配置器裡有內存不足處理例程