Изображения у вас есть память, содержащая байты: [++++++ ----- ++++ - ++ - ++++++++ -------- ++ +++]
Скажем, "+" означает выделение, а "-" означает свободный.
Я ищу формулу для вычисления процента фрагментации.
Фон: я реализую крошечное управление динамической памятью для встроенного устройства со статической памятью. Моя цель - иметь что-то, что я могу использовать для хранения небольших объемов данных. В основном входящие пакеты по беспроводному соединению ~ 128 байтов каждый.
Благодарим вас за помощь.
Как говорит Р., это зависит от того, что вы подразумеваете под "процентом фрагментации", но одна простая формула, которую вы могли бы использовать, была бы следующей:
(free - freemax)
---------------- x 100% (or 100% for free=0)
free
где
free = total number of bytes free
freemax = size of largest free block
Таким образом, если вся память находится в одном большом блоке, фрагментация равна 0%, и если память вырезана на сотни маленьких блоков, она будет близка к 100%.
Рассчитайте, сколько 128-байтных пакетов вы могли бы поместить в текущий макет памяти. Пусть это число n.
Рассчитайте, сколько 128-байтных пакетов вы могли бы поместить в макет памяти с тем же количеством байтов, что и текущий, но без отверстий (т.е., например, переместите все + влево). Пусть это число N.
Ваш "коэффициент фрагментации" будет равен альфа = n/N
Если ваши распределения примерно одинакового размера, просто разделите память на 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 очень плохо (не может выделить какой-либо).
Если у вас были [++++++ ----- ++++ - ++ - ++++++++ -------- +++++] и вы хотели измерить фрагментацию свободного пространства (или любого другого распределения) Вы можете измерить средний смежный размер блока Всего блоков/Количество смежных блоков.
В этом случае это будет 4/(5 + 2 + 1 + 8)/4 = 4