自由列表

自由列表(free list)是一種數據結構,用來實現動態記憶體分配方案。通過把一系列未分配的記憶體區域連線起來形成一個鍊表,利用每塊未分配區域的第一個字長(即一個word)來存儲指向next的指針。

如果一個記憶體池所存儲的對象都具有相同的size,那么自由列表最適合從這種的記憶體池中分配空間。(為神馬咧?因為鍊表結構就可以快速的挪動一個區域,只需要把這個區域的指針掛到已分配的鏈上或者掛到未分配的鏈上,但是如果管理對象大小不一,那么我們就需要找一塊合適記憶體區域,可是鍊表不能隨機訪問,找起來很慢的。)

自由列表使得分配空間和釋放空間非常簡單,如果釋放一塊空間,只需要把它掛到free list(釋放列表)上。如果是開闢一塊空間,那么只需要把簡單的把 free list上掛的最後一塊區域取下來然後使用它。如果每次開闢的空間大小不固定,那么我們就必須查找一塊夠大的空間才行,這是種代價很高的操作。

自由列表繼承了普通鍊表的那些缺點,很低的局部訪問性和很低的快取命中率,也不能自動合併相鄰的區域來滿足分配大塊記憶體的需求,這些和buddy allocation system(巴迪記憶體分配系統)是不一樣的。但是,針對大量的簡單應用程式,自由列表仍然是很有用的,因為這類程式沒有必要使用一套很成熟的記憶體分配系統或者使用時反而會導致太多的開銷。

相關詞條

熱門詞條

聯絡我們