Управление оперативной памятью (распределение и защита) в многозадачной ОС. Механизм реализации виртуальной памяти

Управление оперативной памятью (распределение и защита) в многозадачной ОС. Механизм реализации виртуальной памяти.

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

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

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

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

уменьшается

Кэш-память

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

возрастает

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

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

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

Внешняя

память

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

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

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

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

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

·  Именующей функции 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]

Стратегии управления памятью

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

-  когда осуществляется выборка новой программы в памяти: по запросам системы или с предупреждением их; (1)

-  в какое место оперативной памяти будет помещаться программа: как можно более плотно с занятием свободных “дыр”, чтобы свести к минимуму потери памяти; или необходимо стремиться к возможно более быстрому размещению программы, чтобы свести к минимуму потери машинного времени; (2)

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

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

(1)  Стратегии выборки (вталкивания):

·  стратегии выборки по запросу;

·  стратегии упреждающей выборки.

(2)  Стратегии размещения.

(3) Стратегии замещения(выталкивания).

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

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

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

При размещении новых программ, поступающих в ОП реализуют, как правило одну из трех стратегий:

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

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

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

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

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

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

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

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

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

First-in-first-out

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

Самостоятельно рассмотреть вопрос: “Аномалия FIFO”[Дейтел р.9.3.3.1]

Выталкивание дольше всего не использовавшейся страницы (LRU)

Least-recently-used

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

Выталкивание реже всего используемой страницы (LFU)

Least-frequently-used

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

Выталкивание не использовавшейся в последнее время страницы (NUR)

Not-used-recently

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

Поскольку желательно заменять ту страницу, которая в период нахождения в ОП не изменялась, то реализация NUR предусматривает использование двух признаков на страницу:

·  Бит-признак обращения 0 - если обращений не было;

1 - если обращения были;

·  Бит-признак модификации 0 - если страница не изменялась;

1 - если изменялась.

При поиске страницы для выталкивания проверяется сначала ее бит-признак обращения=0, поскольку мы пытаемся приблизиться здесь к алгоритму LRU, то первым кандидатом на выталкивание будут страницы, к которым вообще не было обращений. При отсутствии таковых, будут рассматриваться, как кандидаты на выталкивание страницы, где бит-признак модификации=0.

Следует отметить, что из рассмотренных выше стратегий NUR является и не слишком дорогой и достаточно эффективной.

Рабочее множество

Working set of pages

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

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

 

t-w w t

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

процесса

Страницы, к которым обращается

процесс в течение этого временного

интервала, составляют рабочее

множество этого процесса W(t,w)

Рис. 15 Определение рабочего множества страниц процесса

Рабочее множество страниц процесса W(t,w) в момент времени t есть набор страниц, к которым процесс обращается в течение интервала времени процесса от t-w до t, где время процесса - это время, в течение которого процесс имеет в своем распоряжении ЦП. Переменная w называется размером окна рабочего множества, причем выбор величины этого окна играет решающую роль с точки зрения эффективности стратегии управления памятью по рабочему множеству.

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

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

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

Стратегии вталкивания

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

Подкачка страниц по запросу

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

 

Распределение Процесс работает

памяти

 

 

F Время

Ожидание подкачки страницы, F- среднее время подкачки страницы

Рис. 16 Произведение “пространство-время” при подкачке страниц по запросу

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

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

Подкачка страниц с упреждением

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

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

·  Малый размер страницы приводит к увеличению таблиц страниц, и, как следствие, к табличной фрагментации.

·  Большой размер страницы приводит к тому, что в ОП будут переписываться команды и данные, к которым не будет обращений.

·  Ввод-вывод более эффективен при больших размерах страниц.

·  При небольших размерах страниц потери памяти на внутреннюю фрагментацию уменьшаются.

Вопросы

1. Оцените с точки зрения принципа оптимальности следующие

нетрадиционные алгоритмы выталкивания страниц применительно к мультипрограммной системе с виртуальной памятью:

·  “Глобальный LIFO”- выталкивается страница, самой последей поступившая в память;

·  “Локальный LIFO”- выталкивается самая последняя по времени поступления страница, вызванная процессом, который запросил новую страницу;

·  “Утомленная страница” - выталкивается страница, подвергшаяся наиболее интенсивным обращениям в системе;

·  “Истрепанная страница”- выталкивается страница., подвергшаяся наиболее интенсивным модификациям в системе.

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

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

3.  Перечислите несколько причин, по которым на некоторые страницы

должен действовать запрет на выталкивание из ОП.

4.  Предположим, что блок управления памятью принимает решение о том,

какую страницу следует вытолкнуть исключительно на основе анализа

битов-признаков обращения и модификации страницы. Приведите

несколько примеров некорректных решений..

5.  Почему в общем случае целесообразнее выталкивать немодифицированную

страницу, а не страницу, подвергшуюся модификации?

6.  Для каждой из приведенных ниже пар стратегий выталкивания страниц

укажите последовательность обращений, при которой обе стратегии выбрали бы для выталкивания одну и ту же страницу:

·  LRU, NUR;

·  LRU, LFU;

·  LRU, FIFO

·  NUR, FIFO

7.  Отмечалось, что стратегию FIFO достаточно просто реализовать, но

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

8.  Приведите аргументы за и против страницы малых размеров (страницы

больших размеров).

9. Объясните как влияет стиль программирования на скоростные

характеристики системы со страничной организацией. Рассмотрите

следующие подходы:

·  модульность;

·  минимальное использование операторов goto.

10. Приведите сходства и различия между страничной и сегментной

оргаизацией памяти.

11.Укажите общие и отличительные признаки систем с чисто сегментной и

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

12.Каким образом эволюционировали виды организации памяти.

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

Дополнительный материал

СВОПИНГ В ОС UNIX

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

1.  Управление пространством на устройстве выгрузки

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

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

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

алгоритм malloc /* алгоритм выделения пространства с ис- пользованием карты памяти */ входная информация: (1) адрес /* указывает на тип ис - пользуемой карты */ (2) требуемое число единиц ресурса выходная информация: адрес - в случае успешного завершения 0 - в противном случае { для (каждой строки карты) { если (требуемое число единиц ресурса располагается в строке карты) { если (требуемое число == числу единиц в строке) удалить строку из карты; в противном случае отрегулировать стартовый адрес в строке; вернуть (первоначальный адрес строки); } } вернуть (0); }

. Алгоритм выделения пространства с помощью карт памяти

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

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

2.  Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если они имеют адрес, смежный с адресом ресурсов из строки, непосредственно предшествующей или непосредственно следующей за данной (но не с адресами из обеих строк), ядро переустанавливает значение адреса и числа ресурсов в соответствующей строке с учетом вновь освободившихся ресурсов. Число строк в карте памяти остается неизменным.

3.  Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их адреса не соприкасаются с адресами каких-либо других ресурсов карты. Ядро создает новую строку и вставляет ее в соответствующее место в карте.

В традиционной реализации системы UNIX используется одно устройство выгрузки, однако в последних редакциях версии V допускается уже наличие множества устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольцевого списка" при условии, что на устройстве имеется достаточный объем непрерывного адресного пространства. Администраторы могут динамически создавать и удалять из системы устройства выгрузки. Если устройство выгрузки удаляется из системы, ядро не выгружает данные на него; если же данные подкачиваются с удаляемого устройства, сначала оно опорожняется и только после освобождения принадлежащего устройству пространства устройство может быть удалено из системы.

2. Выгрузка процессов

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

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

2.  Произведено обращение к системной функции brk, увеличивающей размер процесса.

3.  Размер процесса увеличился в результате естественного увеличения стека процесса.

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

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

Когда ядро принимает решение о том, что процесс будет выгружен из основной памяти, оно уменьшает значение счетчика ссылок, ассоциированного с каждой областью процесса, и выгружает те области, у которых счетчик ссылок стал равным 0. Ядро выделяет место на устройстве выгрузки и блокирует процесс в памяти (в случаях 1-3), запрещая его выгрузку до тех пор, пока не закончится текущая операция выгрузки. Адрес места выгрузки областей ядро сохраняет в соответствующих записях таблицы областей.

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

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

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

Выгрузка при выполнении системной функции fork

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

Выгрузка с расширением

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

3. Загрузка (подкачка) процессов

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

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

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

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

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

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

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

алгоритм swapper /* загрузка выгруженных процессов, * выгрузка других процессов с целью * расчистки места в памяти */ входная информация: отсутствует выходная информация: отсутствует { loop: для (всех выгруженных процессов, готовых к выполнению) выбрать процесс, находящийся в состоянии выгружен- ности дольше остальных; если (таких процессов нет) { приостановиться (до момента, когда возникнет необ- ходимость в загрузке процессов); перейти на loop; } если (в основной памяти достаточно места для размеще - ния процесса) { загрузить процесс; перейти на loop; } /* loop2: сюда вставляются исправления, внесенные в алго - * ритм */ для (всех процессов, загруженных в основную память, кроме прекративших существование и заблокированных в памяти) { если (есть хотя бы один приостановленный процесс) выбрать процесс, у которого сумма приоритета и продолжительности нахождения в памяти наи - большая; в противном случае /* нет ни одного приостанов - * ленного процесса */ выбрать процесс, у которого сумма продолжи - тельности нахождения в памяти и значения nice наибольшая; } если (выбранный процесс не является приостановленным или не соблюдены условия резидентности) приостановиться (до момента, когда появится воз - можность загрузить процесс); в противном случае выгрузить процесс; перейти на loop; /* на loop2 в исправленном алгорит- * ме */ }

Алгоритм подкачки

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

Во-первых, процесс подкачки производит выгрузку на основании приоритета, продолжительности нахождения в памяти и значения nice. Несмотря на то, что он производит выгрузку процесса с единственной целью - освободить в памяти место для загружаемого процесса, он может выгрузить и процесс, который не освобождает место требуемого размера. Например, если процесс подкачки пытается загрузить в память процесс размером 1 Мбайт, а в системе отсутствует свободная память, будет далеко не достаточно выгрузить процесс, занимающий только 2 Кбайта памяти. В качестве альтернативы может быть предложена стратегия выгрузки групп процессов при условии, что они освобождают место, достаточное для размещения загружаемых процессов. Эксперименты с использованием машины PDP 11/23 показали, что в условиях сильной загруженности такая стратегия может увеличить производительность системы почти на 10 процентов (см. [Peachey 84]).

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

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

Интерес к проблемам, связанным с подкачкой процессов, в последние годы спал в связи с реализацией алгоритмов подкачки страниц памяти.