ЛЕКЦИЯ №8 Управление памятью

Термин "память" используется для обозначения любого устройства, способного хранить информацию. Мы будем иметь в виду оперативную память компьютера (ОЗУ). Управление памятью – одна из основных задач ОС, и занимается им менеджер памяти, который входит в состав ядра ОС.

1. Память и отображения, виртуальное адресное пространство

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

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

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

Появление виртуальной памяти стало одним из главных усовершенствований архитектуры компьютеров. Она была впервые реализована в 1959 г. на компьютере "Атлас" в Манчестерском университете и приобрела популярность только спустя десятилетие.

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

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

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

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

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

Размер виртуального адресного пространства программы прежде всего зависит от архитектуры процессора и от системы программирования и практически не зависит от объема реальной физической памяти.

Размер виртуального адресного пространства может быть меньше объема физической памяти (старые 16-разрядные ЭВМ могли адресовать только до 2¹⁶ = 64К адресов). В таком случае вся физическая память разбивалась на разделы объемом по 64К, и на каждый такой раздел с помощью специальных регистров осуществлялось отображение своего виртуального адресного пространства.

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

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

Главной особенностью виртуальной памяти является преобразование (или трансляция) адреса, к которому производится обращение со стороны программы, в реальный адрес. Причем это преобразование должно выполняться быстро. Механизмы динамического преобразования адресов (ДПА) преобразуют смежные адреса виртуальной памяти в необязательно смежные адреса реальной памяти. Таким образом, пользователь освобождается от необходимости учитывать размещение своих процедур и данных в реальной памяти. Программа обращается к виртуальной памяти по виртуальному адресу.

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

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

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

Две модели преобразования адреса – сегментная и страничная – могут применяться как в чистом виде, так и комбинироваться, и тогда сегменты реализуются как объекты переменных размеров, формируемые из страниц фиксированного размера. В таком случае адрес состоит из трех компонентов <сегмент, страница, смещение>.

2. Организация и распределение памяти

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

– Помещение в память только одной программы пользователя или нескольких программ одновременно.

– Выделение программам одинакового или различного числа ячеек памяти.

– Статическое разбиение памяти или динамическое планирование.

– Размещение программы в непрерывном блоке или разбивание ее на отдельные блоки с размещением их в "дырах".

Независимо от способа организации памяти выбирается та или иная стратегия управления для достижения оптимальных характеристик. Менеджер памяти выбирает конкретный подход и принимает решение по следующим вопросам:

– Выбор момента помещения новой программы в оперативную память – это можно делать по запросу системы или предварительно, предупреждая запрос.

– Выбор места памяти для размещения очередной программы.

– Размещение программы как можно более плотное с экономией памяти или как можно быстрое с экономией времени.

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

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

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

2. Простое непрерывное распределение и распределение с перекрытием (оверлейные структуры)

Самой простой схемой является простое непрерывное распределение (т.н. связное распределение), при котором вся память условно разделяется на три части:

область, занимаемая операционной системой;

область, в которой размещается исполняемая задача;

незанятая (свободная) область памяти.

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

Вариантов простого непрерывного распределения памяти существовало очень много (примером может являться ОС MS-DOS).

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

Этот сегмент сам обращается к ОС с указанием, какой сегмент нужно загрузить следующим.

Он возвращает управление главному сегменту задачи (модуль main), и уже тот обращается к ОС с указанием, какой сегмент нужно сохранить, а какой загрузить в ОП, и снова отдает управление одному из сегментов, находящихся в памяти.

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

3.Распределение статическими и динамическими разделами

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

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

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

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

Основным недостатком такого способа распределения является возникновение фрагментации памяти. В каждом из разделов может оставаться неиспользованная память, которая в сумме дает весьма ощутимые потери. Но использовать эти свободные части при таком способе распределения не представляется возможным.

Для сокращения потерь были предложены варианты:

– выделять раздел ровно такого объема, который нужен под текущую задачу;

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

Разделы с подвижными границами. Чтобы избавиться от фрагментации, можно попробовать размещать в ОП задачи плотно, одну за другой, выделяя каждой столько памяти, сколько для нее требуется (Первая ОС, реализовавшая этот способ – OS MVT – "мультипрограммирование с переменным числом задач", ОС для больших ЭВМ класса IBM 360). Специальный планировщик (диспетчер памяти) ведет список адресов свободной ОП. При появлении новой задачи он просматривает этот список и выделяет для задачи раздел, объем которого равен необходимому или чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом список свободной памяти модифицируется. При освобождении раздела диспетчер пытается объединить смежные свободные участки памяти.

Список свободных участков может быть упорядочен либо по адресам, либо по объему. Выделение памяти под новый раздел может осуществляться одним из трех способов:

– первый подходящий участок;

– самый подходящий участок;

– самый неподходящий участок;

В первом случае список упорядочивается по адресам. Правило "первый подходящий" приводит к тому, что память для небольших задач будет преимущественно выделяться в области младших адресов и, следовательно, повысится вероятность того, что в области старших адресов будут образовываться фрагменты достаточно большого объема. При таком способе диспетчеру приходится просматривать в среднем половину списка.

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

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

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

Методы распределения памяти, при которых задаче может не предоставляться сплошная область памяти, называются разрывными, или несвязными. Размещение задачи в нескольких областях требует соответствующей аппаратной поддержки – наличия относительной адресации. В настоящее время применяется сегментная, страничная и сегментно-страничная организация памяти (рассмотрим далее), причем способы организации памяти относятся как к виртуальному, так и к физическому адресному пространству.