Стратегии управления памятью

⇐ ПредыдущаяСтр 55 из 69Следующая ⇒

(1) Стратегии выборки(вталкивания) — когда осуществляется выборка новой программы в памяти: по запросам системы или с предупреждением их;
• стратегии выборки по запросу;
• стратегии упреждающей выборки.
(2) Стратегии размещения — в какое место оперативной памяти будет помещаться программа: как можно более плотно с занятием свободных “дыр”, чтобы свести к минимуму потери памяти; или необходимо стремиться к возможно более быстрому размещению программы, чтобы свести к минимуму потери машинного времени;
(3) Стратегии замещения(выталкивания) — если при размещении новой программы, оперативная память уже заполнена, то по какому критерию выводить из памяти находящиеся в ней программы: замещать в памяти программы, которые находились в ней дольше других или те, которые использовались наименее часто.
Применительно к системам виртуальной памяти стратегии можно подразделить следующим образом.

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

Стратегии размещения. Имеют целью определить, в какое место первичной памяти помещать поступающую страницу или сегмент. В системах со страничной организацией решение о размещении принимается достаточно тривиально, поскольку поступающая страница, может быть помещена в любой свободный страничный кадр. Системы с сегментной организацией требуют подхода, аналогичного тому, который мы рассматривали в системах мультипрограммирования с переменными разделами.
При размещении новых программ, поступающих в ОП реализуют, как правило одну из трех стратегий:
• стратегия наиболее подходящего, когда задание помещеют в наиболее подходящий по размеру учесток, где остается меньше свободной памяти;
• стратегия первого подходящего, когда задание размещается в первом подходящем по размеру участке;
стратегия наименее подходящего, когда задание размещают в участке, где остается максимальное свободное пространство, эта абсурдная на первый взгляд стратегия дает возможность в дальнейшем использовать “дыры” максимального размера, для дальнейшего их объединения и использования.

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

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

(a) с общей очередью процессов,

(b) с отдельными очередями процессов.

Один процесс в памяти. Частный случай схемы с фиксированными разделами работа менеджера памяти однозадачной ОС. В памяти размещается один пользовательский процесс. Остается определить, где располагается пользовательская программа по отношению к ОС - сверху, снизу или посередине. Причем часть ОС может быть в ROM (например, BIOS, драйверы устройств). Главный фактор, влияющий на это решение - расположение вектора прерываний, который обычно локализован в нижней части памяти, поэтому ОС также размещают в нижней. Пример — MS-DOS. Чтобы пользовательская программа не портила кода ОС, требуется защита ОС, которая может быть организована при помощи одного регистра, содержащего адрес границы ОС.

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

Потребность в таком способе загрузки появляется, если логическое адресное пространство системы мало, например 1 мегабайт (MS-DOS), а программа относительно велика. На современных 32-разрядных системах, где виртуальное адресное пространство измеряется гигабайтами, проблемы с нехваткой памяти решаются другими способами.

Организация структуры с перекрытием. Можно поочередно загружать в память ветви A-B, A-C-D и A-C-E программы.

Коды ветвей оверлейной структуры программы находятся на диске как абсолютные образы памяти и считываются драйвером оверлеев при необходимости. Для конструирования оверлеев необходимы специальные алгоритмы перемещения и связывания. Для описания оверлейной структуры обычно используется специальный несложный язык. Совокупность файлов исполняемой программы дополняется файлом (обычно с расширением.odl), описывающим дерево вызовов внутри программы. Например, для примера, приведенного на рисунке: A-(B, C), C-(D, E) Синтаксис подобного файла может распознаваться загрузчиком. Привязка к памяти происходит в момент очередной загрузки одной из ветвей программы. Оверлеи не требуют специальной поддержки со стороны ОС. Они могут быть полностью реализованы на пользовательском уровне с простой файловой структурой. ОС лишь делает несколько больше операций ввода-вывода. Типовое решение порождение линкером специальных команды, которые включают загрузчик каждый раз: когда требуется обращение к одной из перекрывающихся ветвей программы. Программист должен тщательно проектировать оверлейную структуру. Это требует полного знания структуры программы, кода, данных, языка описания оверлейной структуры. Поэтому применение оверлеев ограничено компьютерами с лимитами на память и т.д. В дальнейшем проблема оверлейных сегментов, контролируемых программистом, отпадает благодаря появлению систем виртуальной памяти со свойством локальности, которое дает возможность хранить в памяти только ту информацию, которая необходима в каждый конкретный момент вычислений.

Свопинг. В системах с разделением времени возможна ситуация, когда память не в состоянии содержать все пользовательские процессы. Приходится прибегать к свопингу - перемещению процессов из главной памяти на диск и обратно целиком. Частичная выгрузка процессов на диск связана с пейджингом (paging). Выгруженный процесс может быть возвращен в то же самое адресное пространство или в другое. Это ограничение диктуется методом связывания. Для схемы связывания на этапе выполнения можно загрузить процесс в другое место памяти. Свопинг не имеет непосредственного отношения к управлению памятью, скорее он связан с подсистемой планирования процессов. В системах со свопингом время переключения контекстов лимитируется временем загрузки выгрузки процессов. Для эффективной утилизации процессора необходимо, чтобы величина кванта времени существенно его превышала. Оптимизация свопинга может быть связана с выгрузкой лишь реально используемой памяти или выгрузкой процессов, реально не функционирующих. Кроме того, выгрузка обычно осуществляется в специально отведенное пространство для свопинга, то есть быстрее, чем через стандартную файловую систему (пространство выделяется большими блоками, поиск файлов и методы непосредственного выделения не используются). Во многих версиях Unix свопинг обычно запрещен, однако он стартует, когда возрастает загрузка системы.

Мультипрограммирование с переменными разделами. В этом случае вначале вся память свободна и не разделена заранее на разделы. Вновь поступающей задаче выделяется необходимая память. После выгрузки процесса память временно освобождается. По истечении некоторого времени память представляет собой набор занятых и свободных участков. Смежные свободные участки могут быть объединены в один.

Динамика распределения памяти между процессами. Типовой цикл работы менеджера памяти состоит в анализе запроса на выделение свободного участка, выборке его среди имеющихся в соответствие с одной из стратегий (наиболее подходящий, первый попавшийся, наименее подходящий), загрузке процесса в выбранный раздел и последующем внесении изменений в таблицы свободных и занятых областей. Аналогичная корректировка необходима и после завершения процесса. Связывание адресов может быть осуществлено на этапах загрузки и выполнения. Этот метод более гибок по сравнению с методом фиксированных разделов, присуща внешняя фрагментация из за большого числа участков свободной памяти. В худшем случае мы можем иметь участок свободной памяти между двумя процессами. Если все эти куски объединить в один блок, мы смогли бы разместить больше процессов. Одно из решений проблемы внешней фрагментации - разрешить адресному пространству процесса не быть непрерывным, что разрешает выделять процессу память в любых доступных местах. Один из способов - это paging, используемый во многих современных ОС. Другой способ — сжатие-перемещение всех занятых (свободных) участков в сторону возрастания (убывания) адресов так, чтобы вся свободная память образовала непрерывную область. Этот метод иногда называют схемой с перемещаемыми разделами. В идеале фрагментация после сжатия должна отсутствовать. Но сжатие дорогостояще, алгоритм выбора оптимальной стратегии сжатия очень труден, и сжатие осуществляется в комбинации с выгрузкой и загрузкой по другим адресам.

⇐ Предыдущая 50 51 52 53 545556 57 58 59 Следующая ⇒