“Системное программное обеспечение”

Лекция 9

Глава 8. Управление памятью

1.  Иерархия памяти. Именующая функция и функция памяти. Эволюция видов организации памяти.

2. Особенности страничной и сегментной организации памяти.

Комбинированная сегментно-страничная организация.

Литература

·  [Дейтел 87] Введение в операционные системы. М."Мир",1987.

·  [Кейлингерт 85] Элементы операционных систем, М."Мир", 1985.

·  [Кейслер 86] Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.

·  [Колин 75] Введение в операционные системы, М."Мир", 1975.

·  [Цикритзис 77] Операционные системы, М."Мир", 1977.

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

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

Рассмотрим иерархическую организацию памяти, рис. 8.

Время доступа к памяти

уменьшается

Кэш-память

Скорость доступа к памяти

возрастает

Стоимость памяти в расчете Оперативная

на бит растет память

Емкость памяти уменьшается

Внешняя

память

Рис.8 Иерархическая организация памяти

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

Система с несколькими уровнями иерархии памяти должна обеспечивать

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

Функции для управления памятью

Управление памятью можно представлять, как отображение информации в память посредством трех функций13 .

·  Именующей функции f1, однозначно отображающей данное пользователем имя в идентификатор информации, к которой это имя относится.

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

·  Функции содержимого f3 ,отображающей каждый адрес памяти в значение, которое по этому адресу находится.

Имена, заданные f1 Однозначные f2 Ячейки f3 Значения

пользователем идентификаторы памяти

Результат каждого из этих трех отображений зависит от времени. Это значит, что он может меняться в продолжение всего времени обработки задания системой, Например, результат отображения f1 не устанавливается до тех пор, пока задание не будет связано с системными модулями и файлами, которые в нем упоминаются. Результат отображения f2 может быть зафиксирован после загрузки задания. Однако при некоторых стратегиях распределения памяти отображение f2 меняется в течение всего времени, пока задание находится в оперативной памяти. Ясно, что результат отображения f3 меняется каждый раз, когда выполняется команда записи в память.

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

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

Эволюция видов организации памяти

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

Реальная память. Однопользовательские системы, когда программа должна занимать один сплошной блок ячеек памяти использовались в ОС первого поколения.

Распределение памяти с выделением непрерывного

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

Размер программ, очевидно ограничивается емкостью

имеющейся оперативной памяти, однако существует

Программа возможность выполнения программ, превышающих по

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

оверлейных сегментов. Использование оверлейных

сегментов дает возможность размещать в ОП

не всю программу, а только часть, периодически подкачивая

Свободно и откачивая во внешнюю память отдельные модули.

Операционная система

Реализация оверлейной структуры

Часть программы

пользователя, находящаяся

в ОП в течение всего

времени выполнения

Модуль Модуль Модуль

инициализации обработки вывода

Оверлейная область

 

Мультипрограммные системы с реальной памятью.

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

Очередь заданий для раздела 1 Операционная система

X1 Y1 Z1 Раздел 1

Очередь заданий для раздела 2

Раздел 2

X2 Y2 Z2

Рис 9. Мультипрограммирование с фиксированными разделами, с трансляцией и загрузкой в абсолютных адресах

Очередь заданий

X Y Z Операционная система

Раздел 1

Задания могут перемещаться в любой

свободный раздел, размер которого это допускает Раздел 2

Рис 10. Мультипрограммирование с фиксированными разделами, с трансляцией и загрузкой перемещаемых модулей

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

Задание Х 40К Операционная система

Задание Y 60K

Задание Х 40К

Задание Y 60K

Свободно

Рис 11. Начальное распределение разделов при мультипрограммировании с переменными разделами

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

·  стратегия наиболее подходящего, когда задание помещеют в наиболее подходящий по размеру учесток, где остается меньше свободной памяти;

·  стратегия первого подходящего, когда задание размещается в первом подходящем по размеру участке;

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

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

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

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

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

Сегментация

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

Как уже указывалось, в системе с сегментацией каждый адрес представляет пару [s, d]: s - имя сегмента и d - смещение. Каждой программе соответствует всегда присутствующая в памяти таблица сегментов, в которой каждому сегменту данного процесса соответствует одна запись. С помощью этой таблицы система отображает программные адреса в истинные адреса ОП. Адрес таблицы хранится в аппаратном регистре, называемом регистром таблицы сегментов.

Регистр таблицы сегментов

s d d

+ +

Слово Граница

Признак Биты защиты Граница База s-тая строка таблицы

сегментов

Рис. 12 Вычисление адреса при сегментации

f3(слово)= f3(f3(f3(регистр таблицы сегментов)+s)+d)

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

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

Если в какой-то момент система пожелает переключить свое внимание на другой процесс, она просто заменят содержимое регистра таблицы сегментов на адрес другой таблицы сегментов, после чего ссылки вида [s,d] интерпретируются в соответствии с новой таблицей.

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

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

Страничная организация памяти (paging) - это такой способ управления памятью, при котором пространство адресов памяти разбивается на блоки фиксированной длины, называемыми физическими страницами.(page frame) . В этом случае адреса образуются подобно тому, как это делалось при сегментации пространства программных адресов. Каждый адрес представляет собой пару [p,d], где р - имя страницы, а d - смещение относительно начала страницы.

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

-  признак, показывающий находится ли данная страница в ОП;

-  указатель местоположения страницы (в ОП или вспомогательной памяти);

-  биты защиты для контроля способа доступа.

Кроме того, существует специальный регистр - регистр таблицы страниц, где находится информация о местоположении таблицы страниц, соответствующей выполняемой в данный момент программе.

Регистр таблицы страниц

Страница

р d d

+ +

Слово

Признак Биты защиты Указатель местоположения страницы р-тая

строка таблицы страниц

Рис.13 Вычисление адреса при страничной организации памяти

f3(слово)= f3(f3(f3(регистр таблицы страниц)+p)+d)

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

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

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

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

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

Комбинированная сегментно-страничная организация памяти

Сегментно-страничная организация (paging/segmentation) состоит в том, что память разбивается на страницы для каждого сегмента по его собственной таблице страниц. Адреса при этом состоят их трех компонент [s,p,d], где s- номер сегмента, и вход в таблицу сегментов осуществляется через регистр таблицы сегментов, в которой s-тая запись содержит базовый адрес и границу таблицы страниц для этого сегмента; p - определяет запись в таблице страниц, которая указывает на p-тую страницу сегмента s; d- смещение, которое необходимо прибавить к базовому адресу страницы, чтобы добраться до искомого слова. Таким образом, адрес [s,p,d] может означать d-е слово p-той страницы s-того сегмента того задания, которое определяется содержимым регистра таблицы сегментов.

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

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

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

Регистр таблицы сегментов

Страница

s р d d

+ + Слово

Таблица сегментов

Граница База таблицы страниц s-тая строка

таблицы

сегментов

+

 

Таблица страниц

Признак Биты защиты Указатель местоположения страницы р-тая

строка таблицы

Граница страниц (длина таблицы страниц)

Рис. 14 Вычисление адреса при сегментно-страничной организации памяти

f3(слово)= f3(f3(f3(f3(регистр таблицы сегментов)+s)+p)+d)

Ассоциативные регистры для быстрого доступа к страницам

Номер Номер Указатель

сегмента страницы местоположения

страницы Страница[s1,p1]

s1 p1 Страница[s2,p2]

s2 p2

s3 p3

. . . Страница[s3,p3]

13 [Деннинг1971] Denning P. J. … An Undergraduate Course on Operating System Principls, Cosine Committee on Education if the Nat. Acad. jf Engrng., Washington, D. C. - Отчет, представляющий собой полный курс пол операционным системам, который лег в основу построения книги [Цикритзис 77]