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

Методы распределения памяти должны отвечать на следующие вопросы:

- Каждому процессу следует выделять непрерывную область физической памяти или можно «кусками»;

- Должны ли части программы находиться в одном месте памяти в течение всего времени выполнения процесса или их можно сдвигать;

- Что делать если программа не помещаются в свободную память;

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

Классификация алгоритмов распределения памяти

	Алгоритмы распределения памяти
Без использования внешней памяти		С использованием внешней памяти
	Фиксированными разделами 1			Страничное распределение 4
	Динамическими разделами 2			Сегментное распределение 5
	Перемещаемыми разделами			Сегментно- страничное распределение 6

1. Распределение памяти фиксированными разделами наиболее простой способ управления памятью. Состоит в том, что вся ОП разбивается на несколько частей фиксированной величины (может быть не равные), разбиение может выполняться при установки ОС или старта системы оператором вручную. Очередной процесс, поступивший на выполнение, помещается дибо в общую очередь, либо в очередь к некоторому разделу.

Очереди к разделам

Очередь задач

Раздел 1 Раздел 1

Раздел 2 Раздел2

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

Функции ОС:

- Сравнить размер памяти, требуемый процессу, со свободными разделами и выбрать подходящий;

- Осуществить загрузку в один из разделов и настроить адреса

В настоящее время используется в специализированных ОС из-за своей простоты

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

Функции ОС:

- Ведение таблиц свободных и занятых областей, с указанием начального адреса и размера;

- При создании нового процесса, просмотр таблиц свободных и занятых областей, и выбор подходящего;

- Загрузка в выбранный раздел и внесение изменений в таблицы учета;

- После завершения процесса внесения изменения в таблицы учета.

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

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

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

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

Сегментная виртуальная память – организует перемещение данных сегментами, частями виртуального адресного пространства процесса произвольного размера, полученными с учетом смыслового значения данных.

Сегментно-страничная виртуальная память использует двухуровневое деление: виртуальное адресное пространство делятся на сегменты, а затем сегменты делятся на страницы. Единицей перемещения является страница.

Для временного хранения сегментов и страниц на диске отводиться специальный файл.

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

- номер физической страницы, в которую загружена данная виртуальная страница;

- признак присутствия =1, если страница находится в ОП;

- признак модификации = 1, если данные были изменены, то была проведена операция записи для данной страницы;

- признак обращения к странице (бит доступа)= количеству обращений к странице.

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

	Виртуальное адресное пространство процесса 1		Таблица страниц процесса 1		Физическая память
Виртуальн страницы				управ-
		ВП	ляющая
		ВП	инфор-		Пр1. стр 3
		A	мация
						Пр1. стр 5
	Виртуальное адресное пространство процесса 2		Таблица страниц процесса 2
Пр 2. стр 8
Пр1. стр А	A
Виртуальные страницы				управ-			B
		ВП	ляющая			C
		D			Пр 2. стр D	D
		ВП	инфор-		Пр 2. стр E	E
		ВП	мация			F
		Е
					Обмен
					с диском

Алгоритм работы.

- При каждом обращении к памяти выполняется поиск номера виртуальной страницы, содержащей требуемый адрес;

- По этому номеру определяется соответствующий элемент таблицы страниц и считывается служебная информация для этой страницы;

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

- Если страница выгружена на диск, то происходит страничное прерывание – данный процесс переводиться в состояние ожидания;

- Другой процесс из очереди процессов начинает работать (активизируется);

- Параллельно ОС пытается загрузит требуемую страницу в ОП, если место есть, то загрузка выполняется;

- Если свободного места в ОП нет, то одна из страниц перемещается на диск, а на ее место загружается требуемая;

- При перемещение страницы на диск анализируется признак модификации, если он = 0, то есть страница не изменялась, то записи на диск не проводится, если = 1, то проводиться запись данных на диск;

Возникает вопрос: какую страницу вытеснять на жесткий диск.

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

- Случайный выбор, на диск выгружается первая попавшая страница;

- Анализ числа обращений к странице по признаку обращения, чем меньше обращений, тем страница менее значима;

- Анализ времени обращения к странице, если к странице не было обращения долгое время, то и не будет в ближайшее время;

Интенсивность обмена может быть снижена за счет упреждающей загрузке, когда в память загружается не одна, а несколько прилегающих страниц. Используется эмпирическое правило: если есть обращение к одной странице, то будет и к соседним. Размер страницы должен быть оптимальным, если страница большая – то занимает много места в ОП, если маленькая – то происходит частый обмен. Процессор Intel – 4 кб

5. Сегментное распределение. Виртуальное адресное пространство процесса делиться на части – сегменты, размер которых определяется с учетом смыслового значения содержащийся в них информации. Отдельный сегмент может быть создан для подпрограмм, массива данных и т.д. Во время создания процесса в ОП ОС создает таблицу сегментов процесса, по аналогии с таблицей страниц.

Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов, делаются ссылки на один и тот же участок ОП, в который данный сегмент загружается в единственном экземпляре. Алгоритм работы тот же самый, что и при страничном распределении памяти.

Главный недостаток – дефрагментация ОП, которая возникает из-за разных размеров сегментов. Достоинство – возможность задать разные права доступа для разных сегментов.

6. Сегментно-страничное распределение сочетает достоинства обоих методов. Виртуальное адресное пространство делится на сегменты с учетом смысла данных, а сегменты и физическая память делится на страницы равного размера. Это позволяет сократить фрагментацию памяти и определять разные права доступа. Для каждого процесса создается своя таблица сегментов, а для каждого сегмента – своя таблица страниц. Обмен между ОП и диском проводится – страницами.