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

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

Другой способ (предыдущий здесь) отслеживания состояния памяти предоставляет поддержка связных
списков занятых и свободных фрагментов памяти, где сегментом является (в одном списке может встречаться и то и то - см. рисунок далее)=

• или процесс (память занимаемая процессом)
• или участок между двумя процессами.

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

1. Каждая запись в списке содержит=
2. информацию о том является ли область памяти =
   • свободной (Н, от hole — дыра)
   • или занятой процессом (Р, process)
3. адрес, с которого начинается эта область;
4. ее длину;
5. содержит указатель на следующую запись.

(на рисунке ниже вы можете видеть, что каждый элемент списка действительно разделён на 4 секции)

В нашем примере список отсортирован по адресам. Такая сортировка имеет
следующее преимущество: когда процесс завершается или скачивается("выгружается") на диск,
изменение списка представляет собой несложную операцию. Закончившийся про-
цесс обычно имеет двух соседей (кроме тех случаев, когда он находится на самом
верху или на дне памяти). Соседями могут быть процессы или свободные фрагмен-
ты, что приводит к четырем комбинациям, показанным на рис. 4.8=

1. На рис. 4.8, а корректировка списка требует замены Р на Н - процесс освобождает память - например, самостоятельно закончив свою работу - но его соседи "и справа и слева" всё ещё занимают её
2. На рис. 4.8, б, в две записи соединяются в одну, а список становится на запись короче - область память справа была изначально свободной теперь же с завершение процесса X она увеличивается - так как к ней добавляется новая освобождённая память
3. На рис. 4.8, в - ситуация аналогична предыдущему пункту , только изначально свободная запись в этот раз оказывается "слева"
4. На рис. 4.8, г объединяются три записи, а из списка удаляются два пункта - изначально области и справа и слева от процесса были свободны.

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

Рис. 4.8- четыре комбинации соседей для завершения процесса Х

Если процессы и свободные участки хранятся в списке, отсортированном по
адресам, существует несколько алгоритмов для предоставления памяти процессу,
создаваемому заново (или для существующих процессов, скачиваемых с диска).
Допустим, менеджер памяти знает, сколько памяти нужно предоставить. Простей-
ший алгоритм представляет собой выбор первого подходящего участка. Менед-
жер памяти просматривает список областей до тех пор, пока не находит достаточ-
но большой свободный участок. Затем этот участок делится на две (не обязательно равных) части:

• одна отдается процессу
• а другая остается неиспользуемой.

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

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

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

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

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

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

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

При поддержке отдельных списков для процессов и свободных фрагментов воз-
можна небольшая оптимизация. Вместо создания отдельного набора структур дан-
ных для списка свободных участков, как это сделано на рис. 4.7, е, можно исполь-
зовать сами свободные области. Первое слово каждого незанятого фрагмента
может содержать размер фрагмента, а второе слово может указывать на следую-
щую запись. Узлы списка на рис. 4.7, в, для которых требовались три слова и один
бит (Р/Н), больше не нужны.

Еще один алгоритм распределения называется «быстрый подходящий», он
поддерживает отдельные списки для некоторых из наиболее часто запрашиваемых
размеров. Например, могла бы существовать таблица с п записями, в которой пер-
вая запись указывает на начало списка свободных фрагментов размером 4 Кбайт,
вторая запись является указателем на список незанятых областей размером
8 Кбайт, третья — 12 Кбайт и т. д. Свободный фрагмент размером, скажем, 21 байт,
мог бы располагаться или в списке областей 20 Кбайт или в специальном списке
участков дополнительных размеров.

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

_____________________________________________
Источники(читать подробнее)=
из книги Э. Таненбаума "Современные операционные системы"

Ключевые слова и фразы(для поиска)=