Лекция N 9 Управление памятью

 

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

Ø Стратегии выборки, которые ставят своей целью определение момента, когда следует "втолкнуть" очередной блок данных или программы в ОП;

Ø Стратегии размещения - в какое место ОП следует разместить поступающую программу;

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

 

Иерархия памяти

 

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

 

Связное и несвязное распределение памяти

 

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

 

 

Блочная организация памяти

 

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

Адреса в системе поблочного отображения при отсутствии комбинированной организации памяти являются двухкомпонентными("двумерными").

Чтобы обратиться к конкретному элементу данных, программа указывает блок, в котором этот элемент располагается, и смещение этого элемента относительно начала блока, т.е. в упорядоченной паре (b, d) b является номером блока, в котором размещается соответствующий элемент, а d - смещением относительно начального адреса этого блока. Подобная организация внутренней памяти используется, например, в так называемом реальном режиме функционирования ЭВМ типа IBM PC с микропроцессором 80х86, при этом обе величины - b и d - содержат по 4 шестнадцатеричных цифры; для получения физического адреса, соответствующего паре (b, d), величина b сдвигается в сторону старших разрядов на четыре двоичных разряда, а затем к младшим шестнадцати двоичным разрядам b добавляется d и в результате сложения получается физический адрес элемента.

 

 

Виртуальная память

 

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

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

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

В случае, когда используется только сегментная или только страничная адресация, виртуальный адрес, как уже указывалось, состоит из двух компонент: номера блока и смещения в рамках этого блока. Если же используется комбинированная сегментно-страничная организация, то применяется трехкомпонентная (трехмерная) организация, т.е. для элемента виртуальной памяти адрес определяется как упорядоченная трой ка v = (s, p, d), где s - номер сегмента, p - номер страницы, а d - смещение в рамках страницы; по этой тройке находится нужный физический элемент.

В блочных системах могут быть использованы различные способы преобразования виртуального адреса в реальный физический: прямого, ассоциативного или комбинированного (ассоциативно-прямого) преобразования. В качестве примера рассмотрим общий вид схемы прямого преобразования виртуального адреса (b,d) в реальный (b'+ d), представленной на рис.1.

 

 

Рис.1. Схема прямого преобразования виртуального адреса в реальный

 

Программно-аппаратные средства защиты виртуальной памяти

 

Для иллюстрации возможности этих средств рассмотрим вид типичной строки таблицы блоков (сегментов или страниц), хотя в различных ЭВМ вид этих строк может различаться; для одной и той же ЭВМ вид строки таблицы сегментов также может отличаться от вида строки таблицы строк.

 

p

a

L

R

W

E

A

b'

Рис.2. Строка таблицы блоков

На этом рисунке использованы следующие обозначения:

р - бит присутствия;

а - адрес внешней памяти для случая, когда р=0, т.е. блока нет в физической внутренней памяти;

L - длина блока;

R - бит разрешения только чтения данных;

W - бит разрешения записи и чтения данных;

Е - бит разрешения выполнения команд, содержащихся в этом блоке;

А - бит разрешения дополнения данного блока данных новыми данными, записываемыми в конец этого блока;

b' - базовый адрес блока, если он уже находится в реальной ОП.

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

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

При d > L вырабатывается прерывание по выходу за пределы блока и затем ОС прекращает выполнение данного процесса. Если d < L или d=L, то происходит контроль по битам защиты R, W, Е и А, чтобы удостовериться, что соответствующая операция доступа разрешена. Если такое разрешение имеется, то с помощью аппаратных средств вычисляется физический адрес, соответствующий поступившему виртуальному адресу. Если же соответствующий вид доступа запрещен, то происходит прерывание по защите блока и затем ОС прекращает выполнение текущего процесса.

 

Управление виртуальной памятью

 

1. Стратегии выталкивания страниц

 

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

§ использование принципа оптимальности;

§ выталкивание случайной страницы;

§ выталкивание первой по времени пришедшей страницы(принцип FIFO);

§ выталкивание дольше всего не использовавшейся страницы;

§ выталкивание наименее часто использовавшейся страницы;

§ выталкивание не использовавшейся в последнее время страницы;

§ использование рабочего множества.

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

 

2. Стратегии подкачки страниц

 

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

 

3. Стратегии размещения

 

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

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

Большинство имеющихся в литературе данных, как теоретических, так и эмпирических, свидетельствуют о том, что в ЭВМ целесообразно выбирать страницы относительно небольшого размера. Например, в защищенном режиме работы ЭВМ с микропроцессором 80х86 при х > 2 используется размер страницы, равный 4 Кб.