Компактор памяти в С?

Question

У меня есть программа, которая имитирует оптимальное управление памятью.По сути, хотя в списке дыр есть доступные дыры, достаточно большие для процесса, который мы пытаемся выделить, процессы выделяются и добавляются в список процессов.Однако, в конце концов, мы достигли точки, где дыры становятся очень фрагментированными, и нам необходимо выполнить уплотнение.

Самый простой способ сделать это, очевидно, создать новый список и добавить все процессы в последовательном порядке.Однако это не очень реалистично, поскольку в реальном мире у вас не будет места для перемещения и создания нового списка.

Можете ли вы придумать способ перенести все процессы на один конец памяти и освободить место на другой?В основном он настроен как этот массив дырок (дыры - это структуры, содержащие начальный индекс и размер) и массив процессов (процессы также являются структурами, которые содержат идентификатор процесса, начальный индекс и размер).

Answer 1

Вы можете перетасовать выделенную память до конца доступной памяти один за другим.

Псевдокод:

sort procs by start_index                           (descending)
avail_end = END_OF_MEM - p[0].size                  (adjust alignment)

for p in procs

     memmove( avail_end, p.start_index , p.size )
     avail_end = avail_end  - p.size

это должно привести к одному свободному блоку памяти в начале доступнойобъем памяти.Вы также можете остановить эту функцию после перемещения одной области (после достижения порога времени) и продолжить позже (проверяя, есть ли разрыв между выделенными областями последующего процесса, чтобы пропустить ненужные перемещения).

Answer 2

Если массив отверстий отсортирован по начальному индексу, вы можете выполнить итерацию по массиву, взять два отверстия и переместить фрагмент памяти между ними в начальный индекс первого отверстия.

---

Дальнейшее объяснение:

Каждое отверстие имеет начальный индекс и конечный индекс, равный start_index + size.Сравнивая конечный индекс первого отверстия с начальным индексом второго, вы получаете размер промежуточного фрагмента памяти.Затем вы можете сделать memmove фрагмента памяти для первого начального индекса.

Answer 3

При освобождении памяти (и создании отверстия) вы уже объединяете ее с соседними отверстиями?В противном случае это хорошая идея для уменьшения фрагментации.