Методические указания к выполнению курсовой работы по дисциплине ОС (раздел “Управление оперативной памятью”) (стр. 1 )

Методические указания к выполнению курсовой работы по дисциплине ОС

(раздел “Управление оперативной памятью”)

УКАЗАНИЯ К ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ

·  Разработать структуру планировщика – диспетчера, реализующего функцию динамического управления памятью при:

1)  страничной;

2)  сегментной;

3)  сегментно – страничной организацией памяти.

·  Создать подсистему управления ОП в составе:

§ база данных для управления ОП.

§ таблица трансляции.

§ таблица страниц (сегментов, сегментно – страничной организацией).

§ Менеджер страниц (сегментов, сегментно – страничной организации).

·  Определить рабочую область менеджера памяти.

·  Разработать алгоритмы обработки прерываний по обращению к ОП:

4) прерывание по таймеру интервалов;

5) прерывание по сбою страницы (сегмента, сегментно – страничной организации);

6) прерывание по переполнению рабочего набора;

7) прерывание по ошибке адресации;

8) страничное (сегментное, сегментно – страничное) прерывание.

·  Курсовая работа должна содержать:

§  введение (постановку задачи).

§  теоретические основы управления памяти:

a) анализ алгоритмов управления.

b)  обработка прерываний по обращению к ОП.

§  обработчик прерываний.

§  менеджер памяти.

§  структуры таблиц и очередей.

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

I.  Прерывание по таймеру интервалов.

1.  Загрузка Т = В.

2.  Генерация прерывания по окончанию работы.

3.  Циркуляция.

4.  Изменение рабочего набора.

5.  Деактивация.

II.  Страничный сбой (загрузка страниц ОП).

1.  Читать таймер интервалов.

2.  Проверить таблицу страниц.

3.  Определить дескриптор страниц.

4.  Добавить дескриптор страницы.

5.  Сохранить карту.

6.  Деактивизировать.

7.  Поставить в очередь на ввод.

III.  Страничное прерывание (пересылка страницы с диска в ОП).

1.  Загрузить дескриптор страницы.

2.  Установить элементы карты.

3.  Добавить процесс.

4.  Добавить дескриптор страницы.

5.  Удалить процесс.

6.  Поставить в очередь на ввод.

IV.  Переполнение рабочего набора

1.  Освободить страницу (определить дескриптор).

2.  Удалить процесс (i).

3.  Добавить процесс (i + 1).

4.  Сохранить регистры (связь - вперед).

5.  Выбрать следующий процесс.

6.  Загрузить вектор состояния.

V.  Ошибка адресации (процесс аннулируется).

1.  Освободить страницы процесса.

2. МЕТОДЫ УПРАВЛЕНИЯ СТРАНИЦАМИ

2.1. БАЗОВЫЕ КОНЦЕПЦИИ МЕТОДА УПРАВЛЕНИЯ СТРАНИЦАМИ

При страничной организации основная память делится на блоки фиксированного размера, называемые рамками страниц. Каждая программа пользователя делится на блоки соответствующего размера, называемые страницами. Страницы организуются в логическом адресном пространстве, а рамки страниц - в физическом. Поскольку страницы и рамки страниц имеют различные идентификаторы, возникают ситуации, касающиеся взаимосвязи между логическим адресным пространством (ЛАП) и физическим адресным пространством (ФАП):

1. ЛАП < ФАП. В этом случае основной акцент делается на повышение эффективности использования памяти.

2. ЛАП = ФАП. Страничная организация служит не только для увеличения эффективности использования памяти, но и для расширения возможности разделенного использования процедур (т. е. несколькими пользователями). Возможно использование эффективного оверлейного механизма, реализованного аппаратно.

3. ЛАП > ФАП. Этот случай предполагает виртуальную память и дает наибольшие преимущества.

Идентификация. Страницы и рамки страниц снабжают числовыми идентификаторами, устанавливаемыми по следующему правилу:

Пусть p есть размер страницы в словах (например, 512).

Пусть т есть размер основной памяти в словах, такой, что m=n*p по модулю 1024 есть 0; р по модулю 2К есть 0 и i*p=j*1024. Таким образом, основная память состоит из участков по 1К слов в каждом. Кроме этого, размер страницы есть степень числа 2, а 1К памяти содержит четное число страниц. Набор целых чисел 0, 1, 2, ..., п—1 соответствует идентификаторам страничных рамок.

Пусть М есть размер программы пользователя в словах. Для размещения этой программы в памяти необходимо N стра­ниц, так что М=N*p. Набор целых чисел от 0 до п—1 соот­ветствует идентификаторам страниц пользователя. Заметим, что требование равенства нулю m по модулю р не является обязательным. Это означает, что программа пользователя не должна заполнять целиком все страницы. Последняя страница может быть заполнена лишь частично.

Используя двоичную арифметику – представление страницы степенью числа 2 легко реализуемо. Наиболее предпочтительны размеры страниц 8К, 16К, и даже 64К.

Конструкция виртуального адреса. Виртуальный адрес — это адрес логического пространства процесса пользователя (обычно для случая ЛАП > ФАП). Все ссылки к логическому пространству должны быть преобразованы в физический адрес основной памяти. Для этого системе необходимы идентификатор рамки страницы и смещение внутри нее. Система должна пре­образовать виртуальный адрес в физический. Каждый вирту­альный адрес есть пара (р, i), где р - номер страницы процес­са пользователя, а i—индекс страницы (такой, что i<w, где w—размер страницы).

Например, если машина имеет 16-бит слово, позволяю­щее ей адресоваться к 64К слов и, если размер страницы соста­вит 512 слов, то логическое адресное пространство будет со­стоять из 128 страниц. Для идентификатора р необходимо 7 бит, а для индекса 9 бит. Полное 16-бит слово будет иметь вид

идентификатор - страницы

индекс - слова

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

 

Рис. 1 Отображение страницы на основную память. Виртуальный адрес = (р, i). Физический адрес - x = размер страницы + i. Отрицательное значение идентификатора рамки страницы указывает на то, что страница в данный момент отсутствует в памяти.

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

Эти операции осуществляются Устройством Управления Памятью (УУП) со­гласованно с программой пользователя. Для этого копия таблицы страниц процесса должна быть загружена в УУП.

 

Рис. 2. Обобщенная процедура страничного обмена. Блок # - это адрес рамки страницы в основной памяти (поэтому умножения на размер страницы не требуется).

По схеме, изображенной на рис. 2, УУП поддерживает список адресов таблиц для n пользователей. Аппаратно реализованный регистр слу­жит для указания текущего пользователя, т. е. пользователя, чья таблица страниц является в настоящий момент активной. Элемент таблицы, содержащий карту пользователя (в УУП), загружается в аппаратный регистр базы таблицы страниц. Каждый адрес памяти содержит идентификатор страницы и ин­декс. Идентификатор страницы в комбинации с содержимым базового регистра таблицы страниц указывает на элемент таблицы страниц. Содержимым этого элемента является адрес рамки страницы в памяти. Физический адрес получается добавлением индекса к адресу рамки страницы.

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

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

1. БИТ-ПРИСУТСТВИЯ указывает, находится ли страница в данный момент в основной памяти.

2. БИТ (Ы)-АКТИВНОСТИ указывает на использование за последнее время данной страницы процедурами страничного обмена.

3. БИТ-ИЗМЕНЕНИЯ указывает на то, что содержимое страницы памяти изменялось (или не изменялось) с момента ее загрузки в память.

Наиболее важными из этих битов являются БИТ-ПРИСУТ­СТВИЯ и БИТ-ИЗМЕНЕНИЯ. Бит присутствия анализируется при каждой адресной ссылке программы пользователя. Равен­ство его нулю означает, что страница была удалена из памяти. Бит изменения определяет необходимость записи страницы на диск при ее замене в памяти. Единичное его значение означает, что в содержимом страницы были сделаны изменения, и, следовательно, она должна быть записана на диск. (Нулевое значение предполагает использование прежней копии.) В сис­темах, в которых страницы инструкций (в противоположность страницам данных) являются реентерабельными, бит измене­ния никогда не устанавливается.

2.2. МЕТОДЫ УПРАВЛЕНИЯ СТРАНИЦАМИ

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

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

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

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

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

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

2. Предположим, что 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). Такая си­туация называется сбоем страницы.

3. Предположим, что x(t) не принадлежит М(с, t -1) и что m(c, t—1) = с; следовательно, память полна и страницу необходимо заменить. Пусть y(t) есть удаляемая из памяти страница, выбранная алгоритмом замены. Тогда (M(c, t - 1) удалить y(t)) Ux(t) > M (c, t). Хороший алгоритм замены старается минимизировать число обменов “диск - память”.

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

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, Тt2) определяется как

С(Т1, T2)=T2*

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

Принцип локальности. Пусть некоторая программа состоит из набора страниц 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) есть ожидаемый рабочий набор:

w(h) = ожидаемое значение [w(t, h)].

Свойства w(h):

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

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

2.4. ПРОБЛЕМЫ УПРАВЛЕНИЯ СТРАНИЦАМИ

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

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

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

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

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

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

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

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

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

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

3. ПРОЕКТИРОВАНИЕ СИСТЕМЫ УПРАВЛЕНИЯ СТРАНИЦАМИ

Для создания системы управления страницами необходимо детально знать УУП и архитектуру системы в целом.

Уп­равление страницами предполагает ответ на следующие воп­росы:

·  Что происходит во время загрузки страницы в память?

·  Как осуществляется контроль нескольких конкурирующих запросов на загрузку или освобождение страниц?

·  Какой эффект оказывает планирование ввода-вывода на об­служивание страничных запросов и общую производительность системы?

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

Пример функционального описания этих взаимодействий. Ряд процессов находится в очереди на выполнение. При возникновении доступа к пространству основной памяти про­цессу с наивысшим приоритетом назначается квант времени q[i], и он помещается в очередь выполняющихся процессов. Эти процессы выполняются в течение времени В, таком, что В меньше пли равно q[i]. По окончании В секунд выполнения процесс возвращается в очередь выполняющихся процессов. Из этой процедуры исключаются следующие ситуации:

1)  время выполнения t[i] процесса превосходит квант времени (t[i]>q[i]); при этом процесс помещается в очередь на выполнение, а его t[i] устанавливается в нуль.

2)  процесс блокируется на время выполнения запроса к си­стемной службе.

3)  процесс завершил свое выполнение.

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

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

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

1)  готовые для повторного распределения.

2)  в измененном состоянии, требующем для повторного ис­пользования страницы ее удаления из памяти.

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

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

Страница перестает быть активной и, следовательно, ста­новится доступной, если к ней не производилось обращения в течение J секунд. Таким образом, либо она не является членом рабочего набора, либо процесс не находится в активном состоя­нии из-за окончания своего кванта времени, блокирования за­просом к системной службе или выхода за границы рабочего набора в тот момент, когда доступные страницы отсутствуют. Итак, менеджер страницы управляет динамическими (т. е. имеющими переменный размер) рабочими наборами для каж­дой активной программы. Менеджер страниц распределяет их по двум очередям: “обменной” очереди и “доступной” очереди (так как страницы из нее не нуждаются в обмене). Если про­цесс адресуется к странице, которая была недавно удалена из его рабочего набора, то вероятность того, что эта страница еще находится в одной из очередей в памяти, достаточно велика. Если счетчик доступных страниц не равен нулю, требуемая страница может быть немедленно распределена процессу.

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

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

4. ДАННЫЕ ДЛЯ УПРАВЛЕНИЯ СТРАНИЦАМИ

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

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

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

Мнемоника	Назначение
признак-активности	Указывает на то, что страница в настоящий мо­мент времени принадлежит рабочему набору процесса (возможно, и не находясь при этом в активном состоянии)
признак-ссылки	Указывает на то, что за интервал времени J к странице производилось обращение
признак-изменения	Указывает на то, что страница модифицирова­лась процессом
защита-записи	Указывает на то, что страница защищена от воз­можного изменения ее содержимого
индекс-блока	Указывает адрес физической страницы для вир­туальной страницы в основной памяти

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