Управление памятью с помощью связанных списков. Алгоритмы предоставления памяти

Управление памятью с помощью битовых массивов

При таком методе управления, ОС разбивает память на единичные блоки, и каждому блоку соответствует один бит в так называемом битовом массиве либо битовой карте. Занятому под процесс блоку соответствует единица, свободному - нуль. Битовая карта является достаточно простым способом отслеживания распределения памяти. Однако, поиск серии заданной длины является достаточно медленной операцией, посколькю искомая последовательность может пересекать границы слов. При выборе маленького размера единичного блока, битовая карта может занимать значительный объем памяти. При выборе большого блока могут возникнуть значительные потери из-за частичного использования последнего блока серии.

правление памятью с помощью связных списков

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

- атрибута занятости - P - занят (process), H - свободен, дыра (hole);

- адреса начала фрагмента;

- длины фрагмента;

- указателя на следующую запись.

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

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

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

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

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

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

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