Алгоритм выделения страниц памяти и таблиц страниц

Question

Я хочу разработать алгоритм выделения и освобождения страниц памяти и таблиц страниц. Какие структуры данных обеспечат наилучшую производительность и простейшую реализацию?

Answer 1

Наиболее распространенный алгоритм и структура данных, что неудивительно, называется таблицей страниц .По своей сути он состоит из одного массива, сопоставляющего блоки виртуального адресного пространства с блоками физического адресного пространства;Нераспределенные страницы установлены в ноль.Когда процесс пытается получить доступ к не отображенной памяти, система берет ранее неиспользованный блок физической памяти и отображает его в таблице страниц.

Поскольку большинство областей виртуальной памяти слишком велики для таблицы страниц одного уровня (32битовой машине с 4k-страницами потребуется 32 бита * (2 ^ 32 байта / 4 килобайта) = 4 мегабайта на виртуальное адресное пространство, в то время как для 64-битного потребуется экспоненциально больше), используются многоуровневые таблицы страниц: верхний уровень состоит изуказатели на таблицы страниц второго уровня, которые указывают на фактические области физической памяти (возможно, с большим количеством уровней косвенности).Это позволяет системе экономить память на табличном столе, когда большие области адресного пространства остаются неиспользованными.

Answer 2

Несмотря на то, что ОС обычно реализует таблицы страниц, более простое решение может выглядеть примерно так:

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

При создании связанного списка убедитесь, что он отсортирован по индексу.

Если вы хотите выделить память, отсканируйте связанный список, и это займет O (N).где N - уже выполненные распределения.

При удалении будет сканироваться массив для поиска определенного индекса и удаляться узел в связанном списке.

После удаления узла создайте отдельный связанный список, содержащийэти бесплатные выделения.

Вставка будет выглядеть следующим образом.1. Проверьте в свободном списке, есть ли элемент в списке запрашиваемого размера.2. Если нет, выделите память после последнего элемента связанного списка

Удаление будет работать следующим образом: 1. Переместите узел в свободный список.

Убедитесь, что свободный список и связанный списокотсортировано по индексу.

Этот подход не решает проблему фрагментации в распределителях памяти. Одним из простых способов является использование сжатия.Регулярно сканируйте связанный список свободных узлов и для каждого элемента перемещайте элементы в массиве и соответствующим образом обновляйте индекс узла в связанном списке.