Fragmentation定義
在The Memory Fragmentation Problem Solved? 論文中,提出了四種Fragmentation的定義。
我們用百分比來表示記憶體碎片化的程度,也就是
(allocator_usage−live_data_usage)/live_data_usage
live_data是目前程式所使用的記憶體用量,因此最好的情況下,live data剛好等於allocator所使用的記憶體,那麼Fragmentation Rate就是0%。如果allocator使用了相當於live data三倍的記憶體,那麼就會是
200%。
我們以下圖為例協助我們理解並定義何謂fragmentation,這是gcc使用segregated 2^N allocator的記憶體用量變化圖,上方的線是allocator當下的記憶體用量,下方的線是程式當下的記憶體用量。橫軸是類似進度條的概念,以總共程式所分配的記憶體量作為橫軸的最大值,紀錄每分配一定數量的記憶體,當下程式和allocator的記憶體用量。

Couldn’t load preview
The file may have been moved or deleted, or is temporarily unavailable.
https://paper-attachments.dropboxusercontent.com/s_F2652FE930E94485436B9930178672E7BA87A1A57CC7E40AE91E2FBF5ECA3FAA_1469805118200_Selection_275.png
基於這個原則,我們提出了四種定義的方式,以各種不同的觀點來代入allocator usage和live data usage。
- average memory used by allocator / average memory requested by program
- 平均的意思圖中平均上方和下方線條每個點的平均值
- 在live data用量最大的當下的allocator usage和live data usage,分別是點1和點2。
- 在allocator最大記憶體用量的情況下,allocator usage和live data usage,分別是點3和點4。
- 在allocator用量最大的當下,取allocator usage,另外在live data最大用量的當下,取live data usage,這兩個未必是同一的點。這張圖的情況下是點3和點2。
- 這種作法可能的問題在於如果程式在allocator用量最大的當下,只使用了少少的memory,實際上是有fragementation的問題,但我們會傾向於低估fragmentation rate。