Название: Операционные системы как системы управления вычислительными ресурсами - (Коршикова Л.А.)

Жанр: Технические

Просмотров: 1092


2.1. методы управления страницами

 

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

методы замены страниц, определяющие, какие страницы должны быть удалены из памяти;

методы выборки, определяющие, какие страницы необходимо загрузить в память (по запросу пользователя или заранее, до выдачи запроса);

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

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

При рассмотрении методов замены считается, что количество страниц, которое может быть загружено в память, значительно превосходит количество рамок страниц, необходимых для этого размещения. Пусть х – последовательность адресов страниц, т.е. страниц, к которым адресуется программа в ходе своего выполнения. Пусть x(t) есть страница, адресуемая в момент времени t. Строка W = x(1), х(2), x(3), ..., х(М) часто называется строкой страничных ссылок. Пусть с есть число заполненных в настоящий момент страничных рамок в памяти. Тогда М(с,t) представляет собой текущую конфигурацию программы пользователя в памяти, а п(с, t) – число страниц в М(с,t).

В зависимости от текущей конфигурации программы М(с,t) возможны три случая ссылки к текущей странице x(t).

Пусть x(t) есть элемент М(с, t – 1), т. е. текущая страница находится в памяти. Никаких изменений в памяти не производится, поэтому М(с,t – 1) > M(c, t). Такая ситуация называется сменой страницы.

Предположим, что x(t) не принадлежит m(с, t – 1). Далее предположим, что m(с, t – 1) меньше с; следовательно, память не заполнена до конца страницами программы. Тогда в память загружается текущая страница. В этом случае M(c,t – 1) Ux(t) > M(c,t) и m(c,t – 1) A + l > m(c,t). Такая ситуация называется сбоем страницы.

Предположим, что x(t) не принадлежит М(с,t – 1) и что

m(c,t – 1) = с; следовательно, память полна и страницу необходимо заменить. Пусть y(t) есть удаляемая из памяти страница, выбранная алгоритмом замены. Тогда (M(c,t – 1) удалить y(t))

Ux(t) > M(c,t). Хороший алгоритм замены старается минимизировать число обменов "диск – память".

2.2. Примеры некоторых алгоритмов обменов

1. МИН – алгоритм, МИНимизирующий число страничных замен. При возникновении необходимости обмена МИН анализирует каждую страницу в M(c,t – 1) по отношению к ее дальнейшему появлению в М(с,t). Алгоритм МИН выбирает для замены ту страницу в M(c, t – 1), ссылка к которой в будущей является наиболее отдаленной. Очевидно, что это весьма непрактично, так как для МИН заранее необходимо точно знать о будущих ссылках в последовательности страниц. Такую информированность можно поддерживать применительно к относительно статичным программам. Так как полностью статических программ весьма мало, строка будущих ссылок в общем случае не предсказуема.

2. ПНИС – Последний из Недавно ИСпользованных, алгоритм замены, сходный с алгоритмом МИН, за исключением того, что он просматривает строку адресных ссылок в обратном направлении. Алгоритм ПНИС отыскивает в W страницу, последняя адресация к которой была наиболее давней и которая по-прежнему принадлежит к M(c, t – 1). Исследования показали целесообразность использования алгоритмов ПНИС.

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

2.3. Модель рабочего набора процесса

Пусть программа (процесс) в момент времени t занимает m(t) страниц. С(Т1,Т2) за интервал времени (Т1,Т2) определяется как

.

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

Принцип локальности ссылок основан на понятии рабочего набора. Принцип локальности ссылок состоит в том, что если в период времени (Т – t,Т) программа обращалась к страницам (С1, С2,..., С n), то эта программа будет обращаться к тем же страницам и в период времени (Т, Т + t). Принцип локальности утверждает, что "если не слишком далеко заглядывать в будущее, то можно хорошо его прогнозировать исходя из прошлого". Набор страниц (С1, С2,..., С n) называется рабочим набором программы (правильнее, соответствующего процесса) в момент времени Т.

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

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

Рабочий набор w(k) для k-й адресной ссылки определяется как

w(k, h) = (I есть элемент N, такой, что I есть элемент W'),

где W' = x(k – h + l),...,x(k) – строка ссылок страницы, h > = 1 – "окно" (незанятый участок), i – индекс страницы.

Это означает, что содержимое w(k, h) – это открытый с одного конца участок длины h, определяемый строкой ссылок и оканчивающийся на x(k).

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

Для рабочего набора существует ряд важных характеристик. Предположим, что w(h) есть ожидаемый рабочий набор, который основывается на следующем:

1) пусть h > = l, тогда 1 = < w(h) < min (n, h). Это означает, что рабочий набор программы всегда один и не может превышать величины свободного участка ("окна") или общего числа страниц программы. Размер окна определяет число страниц, "просматриваемых" ссылками программы. Следовательно, в рабочем наборе может быть h страниц (h = < M) или п страниц (n < Н);

2) w(h) = < w (h + 1). Это означает, что рабочий набор со временем расширяется, приближаясь к своему верхнему пределу.

Локальный и глобальный методы управления страницами. Управление страницами в мультипрограммной системе может быть организовано локально или глобально. При глобальном подходе основная память разбивается на рабочие участки, отводимые затем каждой программе. Число участков может быть ограничено архитектурой устройства управления памятью или проектировщиком операционной системы. Алгоритм управления страницами применяется к каждой программе в системе. Если спроектированная операционная система обладает достаточной гибкостью, можно использовать различные алгоритмы для разных классов задач. При возникновении "сбоя страницы" замена осуществляется только в границах рабочей области данной программы.

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

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

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

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

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

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

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

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

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