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

Память, показанная на рис. 4.7, а, представлена в виде связного списка сегментов на рис. 4.7, в. Каждая запись в списке указывает, является ли область памяти свободной (Н, от hole — дыра) или занятой процессом (Р, process); адрес, с которого начинается эта область; ее длину; содержит указатель на следующую запись.

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

Простейший алгоритм представляет собой выбор первого подходящего участка. Менеджер памяти просматривает список областей до тех пор, пока не находит достаточно большой свободный участок. Затем этот участок делится на две части: одна отдается процессу, а другая остается неиспользуемой. Так происходит всегда, кроме статистически нереального случая точного соответствия свободного участка и процесса. Это быстрый алгоритм, потому что поиск уменьшен настолько, на­сколько возможно.

Алгоритм «следующий подходящий участок» действует с минимальными отличиями от правила «первый подходящий». Он работает так же, как и первый алгоритм, но всякий раз, когда находит соответствующий свободный фрагмент, он запоминает его адрес. И когда алгоритм в следующий раз вызывается для поиска, он стартует с того самого места, где остановился в прошлый раз вместо того, чтобы каждый раз начинать поиск с начала списка, как это делает алгоритм «первый под­ходящий».

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

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