Распределение памяти фиксированными разделами
Распределение памяти динамическими разделами
Перемещаемые разделы
Страничное распределение памяти
Сегментное распределение
Алгоритмы распределения памяти
Рассмотрим наиболее общие подходы к распределению памяти, которые были характерны для разных периодов развития операционных систем. Некоторые из них сохранили актуальность и широко используются в современных ОС, другие же представляют в основном только познавательный интерес.
Все алгоритмы распределения памяти разделены на два класса:
- Алгоритмы, в которых используется перемещение сегментов процессов между оперативной памятью и диском;
- Алгоритмы, в которых внешняя память не привлекается.
 |
Рис 1. Классификация методов распределения памяти.
Распределение памяти фиксированными разделами
Главной операцией управления памятью является размещение программы в основной памяти для ее выполнения процессором. Практически во всех современных многозадачных системах эта задача предполагает использование сложной схемы, известной как виртуальная память. Виртуальная память, в свою очередь, основана на использовании одной или обеих базовых технологий - сегментов и страниц. Перед тем как перейти к рассмотрению этих методов организации виртуальной памяти, мы должны познакомиться с более простыми методами.
Простейший способ управления оперативной памятью состоит в том, что память разбивается на несколько областей фиксированной величины, называемых разделами. Разбиение всего объема оперативной памяти на несколько разделов может осуществляться единовременно (то есть в процессе генерации варианта операционной системы) или по мере необходимости оператором системы.
В большинстве схем управления памятью предполагается, что операционная система занимает некоторую фиксированную часть основной памяти и что остальная часть основной памяти доступна для использования многочисленным процессам. Простейшая схема управления этой доступной памятью - ее распределение на области с фиксированными границами.
Ниже показаны два примера фиксированного распределения. Одна возможность состоит в использовании разделов одинакового размера. В этом случае любой процесс, размер которого не превышает размер раздела, может быть загружен в любой доступный раздел. Если все разделы заняты и нет ни одного процесса в состоянии готовности или работы, операционная система может выгрузить процесс из любого раздела и загрузить другой процесс, обеспечивая тем самым процессор работой.
| ОС |
 Задача А
|
 Задача Б
|
 Задача В
|
|
|
а)
|
| - неиспользуемая память |
|
|
| ОС |
|
|
|
| ||||||
|
| ||||||
|
| ||||||
| ||||||
 | ||||
| ||||
|
б)
| | |||
| |||
Рис 2. Распределение памяти фиксированными разделами:
а) с общей очередью, б) с отдельными очередями.
Это может быть выполнено оператором вручную во время старта системы или во время генерации системы.
Очередной новый процесс, поступивший на выполнение, помещается либо в общую очередь (Рис. 2.а), либо в очередь к некоторому разделу (Рис. 2.б).
Подсистема управления памятью в этом случае выполняет следующие задачи:
ü Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел.
ü Осуществляет загрузку программы в один из разделов и настройку адресов.
При очевидном преимуществе – простоте реализации, данный метод имеет существенный недостаток – жесткость.
При использовании разделов с одинаковым размером возникают две трудности:
• Программа может быть слишком велика для размещения в разделе. В этом случае программист должен разрабатывать программу, использующую оверлеи, с тем, чтобы в любой момент времени ей требовался только один раздел основной памяти. Когда требуется модуль, который в настоящий момент отсутствует в основной памяти, пользовательская программа должна сама загрузить этот модуль в раздел памяти программы (независимо от того, является ли этот модуль кодом или данными).
• Использование основной памяти при этом крайне неэффективно. Любая программа, независимо от ее размера, занимает раздел целиком. Этот феномен появления неиспользованной памяти из-за того, что загружаемый блок по размеру меньше раздела, называется внутренней фрагментацией.
Отсюда - ограничение количества, выполняемых задач количеством разделов. С другой стороны - разбиение памяти на разделы не позволяет выполнить процессы, программы которых не помещаются ни в один из разделов. Бороться с этими трудностями (хотя и не устранить полностью) можно посредством использования разделов разных размеров.
В том случае, когда разделы имеют одинаковый размер, размещение процессов в памяти представляет собой тривиальную задачу. Не имеет значения, в каком из свободных разделов будет размещен процесс. Если все разделы заняты процессами, которые не готовы к немедленной работе, любой из них может быть выгружен для освобождения памяти для нового процесса.
Когда разделы имеют разные размеры, есть два возможных подхода к назначению процессов разделам памяти. Простейший путь состоит в том, чтобы каждый процесс размещался в наименьшем разделе, способном полностью вместить данный процесс. В таком случае для каждого раздела требуется очередь нивелировщика, в которой хранятся выгруженные из памяти процессы, предназначенные для данного раздела памяти (Рисунок 2.б).
Достоинство такого подхода заключается в том, что процессы могут быть распределены между разделами памяти так, чтобы минимизировать внутреннюю фрагментацию.
Хотя этот метод представляется оптимальным с точки зрения отдельного раздела, он не оптимален с точки зрения системы в целом. Представим, что в системе в некоторый момент времени нет ни одного процесса размером от 12 до 16 Мб. В результате раздел размером 16 Мб будет пустовать, в то время как он мог бы с успехом использоваться меньшими процессами. Таким образом, более предпочтительным подходом является использование одной очереди для всех процессов (Рисунок 2.а).
В момент, когда требуется загрузить процесс в основную память, выбирается доступный наименьший раздел, способный вместить данный процесс. Если все разделы заняты, следует принять решение об освобождении одного из них. По-видимому, следует отдать предпочтение процессу, занимающему наименьший раздел, способный вместить загружаемый процесс. Можно учесть и другие факторы, такие как приоритет процесса или его состояние (заблокирован он или активен).
Использование разделов разного размера по сравнению с использованием разделов одинакового размера придает дополнительную гибкость данному методу. Кроме того, схемы с фиксированными разделами относительно просты, они предъявляют минимальные требования к операционной системе; накладные расходы работы процессора невелики. Однако у этих схем имеются серьезные недостатки:
• Количество разделов, определенное в момент генерации системы, огранивает количество активных (не приостановленных) процессов;
• Поскольку размеры разделов устанавливаются заранее, в момент генерации системы, небольшие процессы приводят к неэффективному использована памяти. В средах, где заранее известны потребности в памяти всех задач, применение описанной схемы может быть оправдано, но в большинстве случаев эффективность этой технологии крайне низка.
Такой способ управления памятью применялся в ранних мультипрограммных ОС.
