Как рассчитать фрагментацию?

Question

Представьте, что у вас есть память, содержащая кучу байтов:

++++ ++-- ---+ +++-
-++- ++++ ++++ ----
---- ++++ +

Допустим, + означает выделение и - означает освобождение.

Я ищу формула о том, как рассчитать процент фрагментации .

Фон

Я реализую крошечное управление динамической памятьюдля встроенного устройства со статической памятью.Моя цель - иметь то, что я могу использовать для хранения небольших объемов данных.В основном входящие пакеты через беспроводное соединение, около 128 байтов каждый.

Answer 1

Как говорит Р., все зависит от того, что вы подразумеваете под «процентом фрагментации», но можно использовать одну простую формулу:

(free - freemax)
----------------   x 100%    (or 100% for free=0)
    free

где

free     = total number of bytes free
freemax  = size of largest free block

Таким образом, если вся память находится в одном большом блоке, фрагментация равна 0%, а если вся память разделена на сотни крошечных блоков, она будет близка к 100%.

Answer 2

Подсчитайте, сколько 128-байтовых пакетов вы можете уместить в текущем макете памяти. Позвольте быть этим числом п.

Подсчитайте, сколько 128-байтовых пакетов вы можете разместить в макете памяти с таким же количеством выделенных байтов, что и текущий, но без дырок (то есть, например, переместите все + влево). Позвольте быть этим числом N.

Ваш "коэффициент фрагментации" будет альфа = n / N

Answer 3

Если все ваши ресурсы примерно одинакового размера, просто разделите вашу память на TOTAL/MAXSIZE частей, каждая из которых состоит из MAXSIZE байтов.Тогда фрагментация не имеет значения.

Чтобы ответить на ваш вопрос в целом, магического числа для «фрагментации» не существует.Вы должны оценить достоинства различных функций, отражая фрагментированную память.Вот один, который я бы порекомендовал, в зависимости от размера n:

fragmentation(n) = -log(n * number_of_free_slots_of_size_n / total_bytes_free)

Обратите внимание, что log как раз для отображения вещей в масштабе от 0 до бесконечности;Вы не должны на самом деле оценить это на практике.Вместо этого вы можете просто оценить:

freespace_quality(n) = n * number_of_free_slots_of_size_n / total_bytes_free

с 1.0 идеальным (способным выделить максимально возможное количество объектов размером n) и 0.0 очень плохим (неспособным выделить любой).

Answer 4

Если у вас было [++++++ ----- ++++ - ++ - ++++++++ -------- +++++] и Вы хотели измерить фрагментацию свободного пространства (или любое другое распределение) Вы можете измерить средний размер смежных блоков Всего блоков / Количество смежных блоков.

В этом случае это будет 4 / (5 + 2 + 1 + 8) / 4 = 4