Стратегии распределения памяти для сегментов переменной длины

Задачи: найти стратегию распределения, которая

1. хорошо загружает память

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

Решения:

1. Вести список свободной памяти.

2. Уплотнение множества фрагментов один экстент (непрерывная область)

Список свободной памяти – список пустот в нашей оперативной памяти.

Различают 3 классических способа ведения списков.

1. Список пустот, упорядоченных по возрастанию адресов

Пустота (указатель на следующую пустоту, длина)

Позволяет соседние пустоты объединять в одну пустоту.

Существует 2 стратегии поиска подходящей пустоты:

a. Выбор первой подходящей пустоты ().

b. Выбор самой подходящей пустоты ().

Во многих случаях первая стратегия лучше загружает оперативную память, чем вторая.

2. Список пустот, упорядоченных по размерам пустот

При этом: 1 стратегия поиска дает 2-ю.

Пустота (указатель на следующую пустоту, длина)

Модификация способа 2:

Список пустот дополняется дополнительным списком (дополнительными указателями).

указывает на 1-ю пустоту размера

Минусы:

a. Список трудно сопровождать.

b. Трудно объединить соседние пустоты.

3. Организация пустот системой расщепления.

Память представлена множеством блоков размера где размер физической памяти.

Сопровождается список.

Некоторые списки могут быть пустыми.

Поиск пустоты размера :

a. Поиск начинается в списке . Если он не пуст, то выделяет пустоту.

b. Если нет, поиск продолжается в списке . Если что-то есть, то пустота делится пополам, пустоты отправляется в список , а вторая часть пустоты предоставляется запросу.

c.

d. Если список S пуст, то запрос неудовлетворен.

Плюсы:

a. Легко сопровождать списки.

b. Легко объединять соседей.

Если не найдена пустота нужного размера:

1. Отказать в запросе

2. Вытеснить какой-нибудь сегмент

3. Выполнить операцию уплотнения (перегруппировка пустот и их объединение в единое целое)

Целесообразность:

· Сумма пустот больше размера запроса

· Если ЦП не загружен работой

· Пустоты должны быть относительно велики (определяет трудоемкость уплотнения)

Стратегии подкачки:

1. Стратегия подкачки по запросу (по прерыванию).

2. Опережающая подкачка – при известной связи между сегментами/страницами.

Экономия на обработке прерываний.

Издержки – можно подкачать лишнего.

Стратегии вытеснения:

1. Случайный выбор.

Часто вытесняются нужные объекты.

2. FIFO.

Часто вытесняются нужные объекты.

3. Вытесняется по давности использования (LRU – Least Recently Used).

Имеет трудоемкое сопровождение.

Стратегия очень близка к оптимальной в большинстве случаев.

4. Оптимальное вытеснение – нереализуема.

Должна вытеснять объект, к которому не будет обращений дольше всего.

Используется для сравнения других стратегий.

5. Предписанные пользователем приоритеты.

6. Приоритеты, задаваемые задачам системой на основе измерений.

7. Смешанные методы – основаны на здравом смысле.

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

a. АО неактивной задаче, АО только для чтения.

b. АО неактивной задаче, АО только для записи.

c. АО управляемый программой, к которой не было обращений уже секунд.

d. АО задачи, ожидающий в/в.

e. АО любой другой задачи.