Динамическое распределение памяти. Организация виртуальной памяти

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

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

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

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

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

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

Если таблица страниц указывает на размещение требуемой информации во внешней памяти, то немедленно обращение к оперативной памяти не происходит, так как операционная система должна организовать процесс организации нужной страницы из внешнего запоминающего устройства в оперативную память. Для каждой из программ обрабатываемой в мультипрограммном режиме организуется только своя виртуальная память и создается своя таблица страниц. При этом все программы делят между собой одну общую физическую память. Таблицы страниц хранятся в оперативной памяти, и обращение к нужной строке активной таблицы страниц происходит по адресу, который определяется номером активной программы и номером виртуальной страницы, как показано на рисунке (рис.9). Программа обычно состоит из нескольких массивов подпрограмм одной или нескольких секций данных. Так как заранее длины этих секций неизвестны то удобно, чтобы при программировании каждый массив имел свою собственную нумерацию байт начинающуюся с нуля и продолжающуюся в возрастающем порядке. Желательно также, чтобы составленная таким образом программа могла работать при динамическом распределении памяти, не требуя от программиста усилий по объединению различных ее частей в единый массив. Эта задача решается с помощью сегментно-страничной организации памяти. Виртуальная память каждой программы делится на части - сегменты с независимой адресацией байт. К виртуальному адресу добавляются дополнительные разряды, определяющие номер сегмента. Возникает четырех ступенчатая иерархия в организации программ:

• программа;

• сегмент;

• страница;

• байт.

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