Мультипрограммирование с переменными разделами.
В принципе, система свопинга может базироваться на фиксированных разделах. На практике, однако, использование фиксированных разделов приводит к большим потерям используемой памяти, когда задача существенно меньше раздела.
Более эффективной представляется схема с переменными (динамическими) разделами. В этом случае вначале вся память свободна и не разделена заранее на разделы. Вновь поступающей задаче выделяется необходимая память. После выгрузки процесса память временно освобождается. По истечении некоторого времени память представляет собой набор занятых и свободных участков (рис. 8.4) Смежные свободные участки могут быть объединены в один.
Рис. 8.4 Динамика распределения памяти между процессами. Серым цветом показана неиспользуемая память.
Типовой цикл работы менеджера памяти состоит в анализе запроса на выделение свободного участка (раздела), выборке его среди имеющихся в соответствие с одной из стратегий (first fit, best fit, worst fit), загрузке процесса в выбранный раздел и последующем внесении изменений в таблицы свободных и занятых областей. Аналогичная корректировка необходима и после завершения процесса. Связывание адресов может быть осуществлено на этапах загрузки и выполнения.
Этот метод более гибок по сравнению с методом фиксированных разделов
Этому методу также присуща внешняя фрагментация вследствие наличия большого числа участков свободной памяти. Проблемы фрагментации могут быть различными. В худшем случае мы можем иметь участок свободной (потерянной) памяти между двумя процессами. Если все эти куски объединить в один блок, мы смогли бы разместить больше процессов. Выбор между first-fit и best-fit слабо влияет на величину фрагментации.
Статистический анализ показывает, что при наличии n блоков пропадает n/2 блоков, то есть 1/3 памяти! Это известное 50% правило (два соседних свободных участка в отличие от двух соседних процессов могут быть объединены в один).
Одно из решений проблемы внешней фрагментации - разрешить адресному пространству процесса не быть непрерывным, что разрешает выделять процессу память в любых доступных местах (будет рассмотрен ниже).
Другим способом борьбы с внешней фрагментацией является сжатие, то есть перемещение всех занятых (свободных) участков в сторону возрастания (убывания) адресов, так, чтобы вся свободная память образовала непрерывную область. Этот метод иногда называют схемой с перемещаемыми разделами. В идеале фрагментация после сжатия должна отсутствовать.
Сжатие, однако, является дорогостоящей процедурой, алгоритм выбора оптимальной стратегии сжатия очень труден, и, как правило, сжатие осуществляется в комбинации с выгрузкой и загрузкой по другим адресам.
10. Виртуальная память.
Уже давно существует проблема размещения в памяти программ, размер которых превышает размер доступной памяти. Один из вариантов ее решения организация структур с перекрытием рассмотрен в предыдущей главе. При этом предполагалось активное участие программиста в процессе сегментации и загрузки программы. Было предложено переложить проблему на компьютер. Развитие архитектуры компьютеров привело к значительному усложнению организации памяти, соответственно, усложнились и расширились задачи операционной системы по управлению памятью. Одним из главных усовершенствований архитектуры стало появление виртуальной памяти (virtual memory). Она впервые была реализована в 1959 г. на компьютере Атлас, разработанном в Манчестерском университете, и стала популярной только спустя десятилетие.
При помощи виртуальной памяти обычно решают две задачи. Во-первых, виртуальная память позволяет адресовать пространство, гораздо большее, чем емкость физической памяти конкретной вычислительной машины. В соответствии с принципом локальности для реальных программ обычно нет необходимости в помещении их в физическую память целиком.
Возможность выполнения программы, находящейся в памяти лишь частично имеет ряд вполне очевидных преимуществ:
Программа не ограничена величиной физической памяти. Упрощается разработка программ, поскольку можно задействовать большие виртуальные пространства, не заботясь о размере используемой памяти.
Поскольку появляется возможность частичного помещения программы (процесса) в память и гибкого перераспределения памяти между программами, можно разместить в памяти больше программ, что увеличивает загрузку процессора и пропускную способность системы.
Объем ввода-вывода для выгрузки части программы на диск может быть меньше, чем в варианте классического свопинга, в итоге, каждая программа будет работать быстрее.
Таким образом, возможность обеспечения (при поддержке операционной системы) для программы видимости практически неограниченной (32- или 64-разрядной) адресуемой пользовательской памяти при наличии основной памяти существенно меньших размеров очень важный аспект. Но введение виртуальной памяти позволяет решать другую не менее важную задачу обеспечение контроля доступа к отдельным сегментам памяти и в частности защиту пользовательских программ друг от друга и защиту ОС от пользовательских программ.
С целью защиты виртуальная память поддерживалась и на компьютерах с 16-разрядной адресацией, в которых объем основной памяти зачастую существенно превышал 64 Кбайта (размер виртуальной памяти). Например, 16-разрядный компьютер PDP-11/70 мог иметь до 2 Мбайт оперативной памяти. Операционная система этого компьютера, тем не менее, поддерживала виртуальную память, основным смыслом которой являлось обеспечение защиты и перераспределения основной памяти между пользовательскими процессами.
Напомним, что в системах с виртуальной памятью те адреса, которые генерирует программа, - (логические адреса) - называются виртуальными, и они формируют виртуальное адресное пространство. В отсутствие механизма виртуальной памяти виртуальное адресное пространство непосредственно отображается в физическое пространство.
Хотя известны и чисто программные реализации виртуальной памяти, это направление получило наиболее широкое развитие после получения соответствующей аппаратной поддержки. Идея аппаратной части механизма виртуальной памяти состоит в том, что адрес памяти, вырабатываемый командой, интерпретируется аппаратурой не как реальный адрес некоторого элемента основной памяти, а как некоторая структура, где адрес является лишь одним из компонентов наряду с атрибутами, характеризующими способ обращения по данному адресу.
Традиционно считается, что существует три модели виртуальной памяти: страничная, сегментная и их комбинация - сегментно-страничная модель. По-видимому, более правильно считать, что существует (и поддерживается аппаратно большинством платформ) страничная модель виртуальной памяти. Сегментно-страничная модель является синтезом страничной модели и идеи сегментации, изложенной в предыдущей главе. Причем для тех архитектур, в которых сегменты не поддерживаются аппаратно их реализация задача архитектурно-независимой компоненты менеджера памяти. Сегментная организация в чистом виде практически не встречается.
Архитектурные средства поддержки виртуальной памяти.
Очевидно, что невозможно создать полностью машинно-независимый компонент управления виртуальной памятью. С другой стороны, имеются существенные части программного обеспечения, связанного с управлением виртуальной памятью, для которых детали аппаратной реализации совершенно не важны. Одним из достижений современных ОС является грамотное и эффективное разделение средств управления виртуальной памятью на аппаратно-независимую и аппаратно-зависимую части. Коротко рассмотрим, что и каким образом входит в аппаратно-зависимую часть подсистемы управления виртуальной памятью. Компоненты аппаратно-независимой подсистемы рассмотрены в следующей главе.
Итак, мы имеем большое (для 32-разрядных архитектур это обычно 2**32 = 4 Гб) виртуальное адресное пространство и физическое пространство существенно меньшего размера. Пользовательский процесс или ОС должны иметь возможность осуществить запись по виртуальному адресу, а задача ОС сделать так, чтобы записанная информация оказалась в физической памяти (впоследствии при нехватке оперативной памяти она может быть вытеснена во внешнюю память).
Таким образом, важный компонент менеджера виртуальной памяти система или функция отображения (трансляции) адресов. Механизм преобразования виртуальных адресов в физические должен предусматривать ведение таблиц, показывающих, какие области виртуальной памяти в текущий момент находятся в физической памяти и где именно размещаются. Если бы такое отображение осуществлять побайтно, то информация об отображении была бы велика, и для ее хранения потребовалось бы больше реальной памяти, чем для процессов. Необходим способ, позволяющий существенно сократить объем информации отображения. Поэтому обычно отображаемая информация группируется в блоки (программа занимает целое количество блоков памяти).
Страничная память
В наиболее простом и наиболее часто используемом случае страничной виртуальной памяти виртуальная память и физическая представляются состоящими из наборов блоков или страниц одинакового размера. Виртуальные адреса делятся на страницы (page), соответствующие единицы в физической памяти образуют страничные кадры (page frames), а в целом система поддержки страничной виртуальной памяти называется пейджингом (paging). Передача информации между памятью и диском всегда осуществляется целыми страницами. Страницы, в отличие от сегментов, имеют фиксированную длину, обычно являющуюся степенью числа 2, и не могут перекрываться.
Виртуальный адрес в страничной системе упорядоченная пара (p,d), где p - номер страницы в виртуальной памяти, а d - смещение в рамках страницы p, где размещается адресуемый элемент. Процесс может выполняться, если его текущая страница находится в оперативной памяти. Если текущей страницы в главной памяти нет, она должна быть переписана (подкачана) из внешней памяти. Поступившая страница может быть размещена в любой свободный страничный кадр. Система отображения виртуальных адресов в физические сводится к системе отображения виртуальных страниц в физические и представляет собой таблицу страниц.
Для преобразования адресного пространства каждого процесса используется одна или несколько таблиц страниц, которые обычно хранятся в оперативной памяти. Для ссылки на таблицу страниц используется специальный регистр процессора. Особенности хранения таблицы страниц описаны ниже. Интерпретация виртуального (логического) адреса показана на рис. 9.1
Рис. 9.1 Связь логического и физического адресов при страничной организации памяти.
Динамическое преобразование адресов в системе осуществляется следующим образом. Выполняемый процесс обращается по виртуальному адресу v = (p,d). Механизм отображения ищет номер страницы p в таблице отображения и определяет, что эта страница находится в страничном кадре p', формируя реальный адрес из p' и d.
Например, в машинной инструкции move reg,0, адрес 0 находится на первой виртуальной странице, которая может быть локализована, во втором страничном кадре. В реальных системах функция отображения хранит бит присутствия страницы в физической памяти. При отсутствии страницы в памяти возникает исключительная ситуация, называемая страничное нарушение (page fault). Обработка страничного нарушения приводит к тому, затребованная страница подкачивается из конкретного места вторичной памяти в свободный страничный кадр физической памяти и продолжается прерванный код. При отсутствии свободных страничных кадров на диск выгружается мало используемая страница.
Номер страницы, как индекс хранится в таблице страниц (page table), которая адресуется при помощи специального регистра процессора, и позволяет определить номер кадра по виртуальному адресу. Помимо этой основной задачи при помощи атрибутов, записанных в строке таблицы страниц, можно организовать контроль доступа к конкретной странице и ее защиту.
Используя схему пэйджинга, мы не имеем внешней фрагментации. Однако сталкиваемся с внутренней фрагментацией: адресное пространство процесса занимает целое число страниц, и в среднем половина страницы на процесс пропадает.
Важный аспект - различие точек зрения пользователя и системы на используемую память. С точки зрения пользователя его память - единое непрерывное пространство, содержащее, только одну программу. Реальное отображение скрыто от пользователя и контролируется ОС. Заметим, что процессу пользователя недоступна чужая память. Он не имеет возможности адресовать память за пределами своей таблицы страниц, которая включает только его собственные страницы.
Для управления физической памятью ОС поддерживает структуру таблицы кадров. Она имеет одну запись на каждый физический кадр, показывающий его состояние.
Отображение должно происходить корректно даже в сложных случаях. ОС поддерживает одну или несколько (при наличии нескольких сегментов памяти) таблиц страниц для каждого процесса, для ссылки, на которую, как уже говорилось, обычно используется специальный регистр. При переключении процессов диспетчер должен найти его таблицу страниц, указатель на которую, таким образом, входит в контекст процесса.
В большинстве современных компьютеров со страничной организацией виртуальной памяти все таблицы страниц хранятся в основной памяти, а быстрота доступа к элементам таблицы текущей виртуальной памяти достигается, как будет показано ниже, за счет наличия сверхбыстродействующей буферной памяти (кэша).