Индекс
НазадОглавлениеВперед


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

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

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

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


Рис.3.1. Функции управления памятью

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

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

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

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

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

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

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

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

Отметим, что иногда виртуальной памятью называют именно эти свойства аппаратуры вычислительной системы и вытекающие из них возможности для процессов работать с виртуальным адресным пространством большего размера, чем размер имеющейся в системе реальной памяти. Мы же следуем более широкой интерпретации [13]: виртуальная память это то адресное пространство, в котором разрабатывается процесс. Такое понимание соответствует определению ОС "с точки зрения пользователя", которое мы дали в разделе 1.4. В данном случае ОС скрывает от процесса организацию низкоуровневого ресурса (реальной памяти) и конструирует ресурс более высокого уровня (виртуальная память), более удобный в обращении. Такая интерпретация не принимает во внимание, на каком этапе - загрузки или выполнения - производится трансляция адресов, и имеется ли в системе аппаратная поддержка этой трансляции. В частном случае размер виртуальной памяти может быть и меньше реальной.

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

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

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

Многоуровневая память строится обычно по иерархическому принципу. Это означает, что для каждого следующего уровня время доступа больше, чем для предыдущего: t[i] > t[i-1], и объем больше: V[i] > V[i-1]. Последнее обстоятельство делает возможным дублирование информации на уровнях: если данные имеются на i-ом уровне, то их копии сохраняются и на всех уровнях с большими номерами. Обозначим через h[i] отношение присутствия - вероятность того, что данные, запрошенные на i-ом уровне памяти, уже имеются на этом уровне. Если мы имеем n уровней памяти, то для n-го уровня отношение присутствия равно 1 и среднее время доступа tav[n] совпадает с t[n]. Для всех уровней с меньшими номерами среднее время доступа может быть определено рекурсивно:

  tav[i] = h[i] * t[i] + ( 1 - h[i] ) * tav[i-1].

На программном уровне мы не можем воздействовать ни на t[i], ни на V[i], которое в значительной степени определяет и h[i]. Но мы можем влиять на величину h[i], выбирая для хранения на уровне с меньшим номерам только те данные, обращение к которым производится наиболее часто.

В общем случае проектирование менеджера памяти в составе ОС требует выбора трех основных стратегий:

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

3.2. Фиксированные разделы.

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

Примером ОС, работающей в такой модели, памяти может быть OS/360, ныне уже не применяющаяся, но существовавшая в двух основных вариантах: MFT (с фиксированным числом задач) и MVT (с переменным числом задач). В первом варианте при загрузке ОС реальная память разбивалась на разделы оператором. Каждая задача (процесс) занимала один раздел и выполнялась в нем. Во втором варианте число разделов и их положение в памяти не было фиксированным. Раздел создавался в свободном участке памяти перед началом выполнения задачи и имел размер, равный объему памяти, заказанному задачей. Созданный раздел фиксировался в памяти на время выполнения задачи, но уничтожался при окончании ее выполнения.

В более общем случае для процесса может выделяться и несколько разделов памяти, причем их выделение/освобождение может выполняться динамически (пример - MS DOS). Однако, общими всегда являются следующие правила:

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

Дырой называется область реальной памяти, которая не может быть использована. Различают дыры внешние и внутренние. Рисунок 3.2 иллюстрирует внешние и внутренние дыры в системе OS/360.


Рис.3.2. Разделы в реальной памяти OS/360

Внутренней дырой называется память, которая распределена процессу, но им не используется. Так, на Рис 3.2.а процессу 1 выделен раздел P1, но виртуальное адресное пространство процесса меньше размера раздела, оставшееся пространство раздела составляет внутреннюю дыру.

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

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

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

Модель с фиксированными разделами представляет весьма ограниченную версию управления памятью. Вытеснение здесь вообще не реализуется, процесс, которому недостает памяти, просто блокируется до освобождения требуемого ресурса (в OS/360 MFT можно было наблюдать даже такое явление: задача, требующая объема памяти, превышающего размер раздела, просто "запирала" этот раздел до перезагрузки системы). Стратегия подкачки здесь примитивная: весь процесс размещается в реальной памяти при его создании. В варианте MFT практически отсутствует и стратегия размещения: процесс размещается с начала раздела, а решение о размещении раздела и о распределении задач по разделам принимает оператор. А вот в варианте MVT, поскольку границы разделов не зафиксированы, ОС необходимо принимать решение о размещении. В этой ОС уровень мультипрограммирования был невысок (обычно 4 - 5 процессов), поэтому стратегия размещения принималась простейшая, а вот в системах с более высоким уровнем мультипрограммирования и, следовательно, со значительной фрагментацией памяти может оказаться целесообразным выбор более сложной и гибкой стратегии.

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

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

Выбранная структура представления свободной памяти не ограничивает выбор стратегии размещения.

Простейшей стратегией размещения является стратегия "первый подходящий" (first hit): просматривается список свободных блоков (или карта памяти) и выбирается первый же найденный блок, у которого размер не меньше требуемого. Если размер найденного блока превышает запрошенный, то оставшаяся его часть оформляется как свободный блок. При всей своей простоте эта стратегия дает неплохие результаты и применяется в большинстве систем с фиксированными разделами и с сегментацией (см. ниже). При значительной фрагментации алгоритм может быть модифицирован кольцевым поиском. Если всякий раз поиск начинается с начала списка/карты, то маленькие свободные участки будут накапливаться в списка/карты и для нахождения свободного блока значительной длины надо будет сначала выбрать и отбросить много маленьких блоков. При кольцевом поиске поиск всякий раз начинается с того места, на котором он закончился в прошлый раз, а при достижении конца списка/карты - продолжается с начала. Таким приемом сокращается среднее время поиска.

Другой несложной стратегией является "самый подходящий" (best hit): просматривается весь список свободных блоков (или карта памяти) и выбирается блок, размер которого равен запросу или превышает его на минимальную величину. Хотя на первый взгляд этот метод может показаться более эффективным, он дает в среднем худшие результаты, чем "первый подходящий". Во-первых, это объясняется тем, что здесь следует обязательно просмотреть весь список или карту, во-вторых, тем, что здесь более интенсивно накапливаются внешние дыры, так как остатки от "самых подходящих" блоков оказываются маленького размера. Существенным же преимуществом этой стратегии является то, что она охраняет большие свободные блоки от "разбазаривания по мелочам".

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

Поскольку модель с фиксированными разделами ограничивает виртуальное адресное пространство размерами реальной памяти, возникает проблема больших программ, не вмещающихся в доступную память. Преодоление этого ограничения достигается созданием программ с оверлейной (overlay - перекрытие) структурой. Структура межмодульных вызовов оверлейной программы имеет вид дерева. В корне дерева (нулевой уровень) находится модуль-монитор, из которого происходят обращения к модулям, расположенным на ветвях дерева. Каждый модуль первого уровня в свою очередь может быть корнем поддерева и т.д. Принцип оверлейности или перекрытия заключается в том, что ветви дерева занимают одни и те же области в виртуальном адресном пространстве программы. Поскольку модули, расположенные в разных ветвях дерева, не могут выполняться одновременно, то только монитор является резидентным в оперативной памяти все время выполнения программы, ветви же сменяют друг друга в одной и той же области памяти. На самом деле построить программу, имеющую идеальную древовидную структуру, довольно трудно, поскольку при этом обязательно догматическое соблюдение дисциплины программирования "сверху вниз". Необходимо тщательно следить, чтобы ветви дерева не пересекались: никакой модуль не имеет права передавать управление в модуль, расположенный на другой ветви, или обращаться к данным, определенным в модуле другой ветви. Реальные программы обычно нарушают эти правила, так как при их разработке используется комбинация дисциплин "сверху вниз" и "снизу вверх", за счет чего появляются низкоуровневые процедуры, обращения к которым производится из любых ветвей дерева. Выход из противоречия состоит либо в помещении этих процедур в корневой модуль, либо в создании еще одной или нескольких резидентных областей для размещения модулей, содержащих эти процедуры. В системах, поддерживающих развитые средства создания оверлейных программ (та же OS/360), выполнение функции именования - отображения имен входных точек и общих переменных на виртуальное адресное пространство возлагается на редактор связей (link editor), который и формирует содержимое адресного пространства процесса в соответствии с оверлейной структурой, описываемой программистом с помощью специального языка. На Рисунке 3.3 представлен пример оверлейной структуры программы.



а). межмодульные связи

a)
б). распределение памяти
Рис.3.3. Пример оверлейной структуры программы

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

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

3.3. Односегментная модель

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

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


Рис.3.4. Односегментная модель

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

Другой возможностью, которую открывает динамическая трансляция адресов, является вытеснение сегментов. Если даже после перемещения сегментов запрос на память не может быть удовлетворен, то ОС может переписать какой-либо сегмент на внешнюю память и освободить занимаемую им реальную память. Поскольку контекст процесса, который содержится в вытесненном сегменте, сохраняется, то впоследствии ОС может вновь загрузить этот сегмент в реальную память, откорректировать базовый адрес в его дескрипторе и возобновить выполнение процесса. Перемещение сегментов и (см. ниже) страниц между оперативной и внешней памятью и наоборот называется свопингом (swapping), а составные его части - вытеснением (swap out) и подкачкой (swap in). Поскольку в модели происходит вытеснение сегментов, должна быть реализована какая-то его стратегия. Естественно, что наилучшим кандидатом на вытеснение должен быть сегмент процесса, находящегося в заблокированном состоянии. Но следует при этом иметь в виду, что процесс может быть заблокирован потому, что он ожидает завершения операции ввода/вывода. При вводе/выводе, использующем канал или прямой доступ к памяти, аппаратура ввода/вывода не выполняет трансляцию адресов (см. главу 6), а производит обмен данными с областью памяти, реальный адрес которой был задан ей при инициировании операции. Сегмент, участвующий в такой операции ввода/вывода, должен быть заблокирован не только от вытеснения, но и от перемещения в реальной памяти. (Эти же соображения должны учитываться и в других моделях памяти). При отсутствии подходящих кандидатов на вытеснение в очереди заблокированных процессов жертва может быть выбрана из очереди готовых процессов. Естественно назначить жертвой процесс, имеющий самый низкий приоритет у планировщика процессов. Но если брать этот приоритет единственным критерием, то имеется потенциальная опасность возникновения избыточных перемещений. Процесс, имеющий низкий приоритет, может быть несколько раз вытеснен и вновь подкачан, но между всеми подкачками и вытеснениями может так и не получить ни одного кванта обслуживания на центральном процессоре. В системах с динамическими приоритетами процесс (например, Unix), подкачанный в оперативную память защищается от вытеснения некоторой временной выдержкой, в течение которой он имеет шанс повысить свой приоритет и получить квант обслуживания. Также и вытесненный процесс должен быть некоторое время выдержан на внешней памяти прежде чем он может быть подкачан. В системах со статическими приоритетами приоритет процесса у планировщика определяет и его приоритет в очереди к ресурсу реальной памяти.

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

3.4. Многосегментная модель

Расширим модель, рассмотренную в предыдущем разделе на случай N сегментов.

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

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

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


Рис.3.5. Трансляция адресов. Многосегментная модель


Рис.3.6. Примерная структура дескриптора сегмента

Допустимое количество сегментов определяется разрядностью соответствующего поля виртуального адреса и может быть весьма большим. Либо аппаратура должна иметь специальный регистр размера таблицы дескрипторов (такой регистр есть в Intel-Pentium), либо ОС должна подготавливать для процесса таблицу максимально возможного размера, отмечая в ней дескрипторы несуществующих сегментов (например, нулевым значением поля size). Отметим, что для систем, упаковывающих номер сегмента и смещение в одно адресное число, разрядность смещения не является ограничением на длину виртуального сегмента. Виртуальный сегмент большего размера представляется в таблице двумя и более обязательно смежными дескрипторами. С точки зрения процесса он обращается к одному сегменту, задавая в нем большое смещение, на самом же деле переполнение поля смещения переносится в поле номера сегмента. Если же простая двоичная арифметика не обеспечивает модификацию номера сегмента, возможность работы с большими сегментами может поддерживаться ОС путем особой обработки прерывания-ловушки "защита памяти".

Каковы преимущества многосегментной модели памяти?

Самое первое преимущество заключается в том, что у процесса появляется возможность разместить данные, обрабатываемые различным образом, в разных сегментах своего виртуального пространства (так, в ОС Unix, например, каждый процесс имеет при начале выполнения три сегмента: кодов, данных и стека). Каждому сегменту могут быть определены свои права доступа. Поскольку обращения к памяти могут быть трех видов: чтение, запись и передача управления, то для описания прав доступа достаточно 3-битного поля Read-Write-eXecute, каждый разряд которого определяет разрешение одного из видов доступа. Аппаратные средства большинства архитектур обеспечивают контроль права доступа при трансляции адресов: поле прав доступа включается в дескриптор сегмента и, если поступивший вид обращения не разрешен, то выполняется прерывание-ловушка "нарушение доступа".

Другое важное преимущество многосегментной модели заключается в том, что процесс имеет возможность использовать виртуальное адресное пространство, размер которого больше, чем размер доступной реальной памяти. Это достигается за счет того, что не обязательно все сегменты процесса должны одновременно находиться в реальной памяти. Дескриптор каждого сегмента содержит бит present, который установлен в 1, если сегмент подкачан в оперативную память, или в 0 - если сегмент вытеснен из нее. Аппаратура трансляции адресов проверяет этот бит и при нулевом его значении выполняет прерывание-ловушку "отсутствие сегмента" (segment falure). В отличие от большинства других ловушек, которые в основном сигнализируют об ошибках, при которых дальнейшее выполнение процесса невозможно, эта не приводит к фатальным для процесса последствиям. ОС, обрабатывая это прерывание, находит образ вытесненного сегмента на внешней памяти, и подкачивает его в реальную память. Естественно, что процесс, обратившийся к вытесненному сегменту, переводится в ожидание, это ожидание может затянуться, если у ОС имеются проблемы с ресурсом реальной памяти. Когда сегмент будет подкачан, процесс перейдет в очередь готовых и будет активизирован вновь с той команды, которая вызвала прерывание-ловушку. В тех аппаратных системах, которые не обрабатывают бит присутствия в дескрипторе сегмента, можно вместо него использовать поле size: ОС должна сбрасывать это поле в 0 при вытеснении сегмента и восстанавливать при его подкачке.

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

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

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

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

В многосегментной модели значительно увеличивается объем управляющей информации, сохраняемой в блоке контекста процесса, даже когда процесс не выполняется. Реальная память, занимаемая блоками контекста неактивных и даже полностью вытесненных процессов, не может быть отдана другим процессам. Такие участки памяти носят название заголовочных дыр. Если потери реальной памяти на заголовочные дыры оказываются недопустимо большими, то имеет смысл разбить блок контекста процесса на две части: меньшую, обязательно сохраняемую в реальной памяти, и большую, которая может быть вытеснена. В литературе [21, 30] описана ОС MULTICS, в которой для номера сегмента отводилось 18 двоичных разрядов. Таблица сегментов процесса могла быть настолько большой, что и одна она не помешалась в оперативной памяти. Для преодоления этого противоречия таблица сегментов разбивалась на страницы, которые подвергались свопингу. (ОС MULTICS была признана неудачным проектом и не получила широкого распространения, но значительно повлияла на последующие проекты ОС, прежде всего - на Unix.)

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

Что касается стратегии подкачки, то все ОС применяют в сегментной модели "ленивую" политику: вытесненный сегмент подкачивается в реальную память только при обращении к нему. Некоторые системы (например, OS/2) позволяют управлять начальной подкачкой сегментов при запуске процесса: сегмент может быть определен программистом как предварительно загружаемый (preload) или загружаемый по вызову (load on call). Разработать неубыточную стратегию упреждающей (до обращения) подкачки сегментов при свопинге пока не представляется возможным из-за отсутствия надежных методов предсказания того, к какому сегменту будет обращение в ближайшем будущем.

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

Получить сегмент:

  seg = getSeg (segsize, access);

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

Освободить сегмент:

  freeSeg(seg);
сегмент с заданным виртуальным номером становится недоступным для процесса.

Изменить размер сегмента:

  chSegSize(seg, newsize).

Изменить права доступа к сегменту:

  chSegAccess(seg, newaccess).

В конкретных системах этот минимальный набор может быть расширен дополнительным системным сервисом.

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

3.5. Страничная модель

Страничную организацию памяти легко представить как многосегментную модель с фиксированным размером сегмента. Такие сегменты называются страницами. Вся доступная реальная память разбивается на страничные кадры (page frame), причем границы кадров в реальной памяти фиксированы. Иными словами, реальная память представляется как массив страничных кадров. Виртуальный адрес состоит из номера страницы и смещения в странице, система поддерживает таблицу дескрипторов страниц для каждого процесса. Дескриптор страницы в основном подобен дескриптору сегмента, но в нем может быть сокращена разрядность поля base, так как в нем хранится не полный реальный адрес, а только номер страничного кадра, а необходимость в поле size вообще отпадает, так как размер страниц фиксирован. Проблема размещения значительно упрощается, так как любой страничный кадр подходит для размещения любой страницы, необходимо только вести учет свободных кадров. За счет этого страничная организация оказывается удобной даже при отсутствии свопинга, так как позволяет разместить непрерывное виртуальное адресное пространство в несмежных страничных кадрах. (Иногда для обозначения свопинга на уровне страниц применяют специальный термин "paging" - страничный обмен.) Внешние дыры в страничной модели отсутствуют, зато появляются внутренние дыры за счет недоиспользованных страниц. При наличии в системе свопинга нулевое значение бита present вызывает прерывание-ловушку "страничный отказ" (page falure) и подкачку страницы в реальную память. Для учета занятых/свободных страниц подходит техника битовой карты, но большинство ОС используют в качестве элементов карты (таблицы страничных кадров) не биты, а куда более сложные структуры, из которых могут составляться и многосвязные списки (в том числе и списки свободных кадров).

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

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

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

Несоблюдение этих правил делает весьма вероятным возникновение такой ситуации, когда система будет занята только хаотичным перемещением страниц. (Например, выполнение команды процессора S/390: MVС память,память может потребовать трех страниц памяти: команды, первого и второго операндов. Если одной из страниц недостает, процесс блокируется в ожидании ее подкачки. Но при неудачной стратегии за время этого ожидания он может потерять другие необходимые страницы и повторная попытка выполнить команду вновь приведет к прерыванию-ловушке). В англоязычной литературе эту ситуацию называют trash - толкотня, в русскоязычной часто используется транскрипция - трэш.

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


Рис.3.7. Зависимость частоты отказов от объема реальной памяти

С точки зрения стратегии размещения не имеет значения, какой страничный кадр занимать при подкачке. Но как выбрать один кадр из всего пула кадров? Конечно, наилучшим кандидатом является полностью свободный кадр - такой, который еще не занимался или был когда-то распределен процессу, ныне уже закончившемуся. Но если суммарный объем виртуальных адресных пространств всех процессов существенно превышает объем реальной памяти, то такие страницы являются более чем дефицитным ресурсом. Выход состоит в том, что для каждого распределенного кадра в таблице страничных кадров (и/или в таблице дескрипторов) ведется учет факторов, определяющих выбор его в качестве жертвы для вытеснения, и из всех кадров выбирается тот, который является лучшим (с точки зрения принятой стратегии) кандидатом в жертвы (OS/2, Windows 95). Несколько более сложное решение - ОС ведет список свободных (условно свободных) кадров и очередная жертва выбирается из этого списка. Страничный кадр попадает в список жертв, если его "показатель жертвенности" превышает некоторое граничное значение, но может быть еще "спасен" из списка жертв, если во время пребывания в этом списке он будет востребован. Помещение кадра в список жертв может выполняться либо сразу по достижении "показателя жертвенности" граничного значения (VM), либо (ленивая политика - Unix) размер списка поддерживается в определенных границах за счет периодического его пополнения путем просмотра всей таблицы страничных кадров.

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

Стратегия FIFO - первый на входе - первый на выходе - является простейшей. Согласно этой стратегии из реальной памяти вытесняется та страница, которая была раньше других в нее подкачана. Для реализации этой стратегии ОС достаточно организовать список-очередь страниц в реальной памяти с занесением подкачиваемой страницы в "голову" списка и выборкой страницы для вытеснения из "хвоста" списка. Хотя стратегия FIFO и лучше, чем RANDOM, она не учитывает частоты обращений: может быть вытеснена страница, к которой происходят постоянные обращения. Более того, при некоторых комбинациях страничных требований FIFO может давать аномальные результаты: увеличение числа страничных отказов при увеличении числа доступных страничных кадров (см. задания в конце главы).

Многие используемые в современных ОС стратегии вытеснения могут рассматриваться как разновидности стратегии LRU (least recently used) - наименее используемая в настоящее время: вытесняется та страница, к которой дольше всего не было обращений. Это можно рассматривать как попытку приближения к стратегии OPT путем экстраполяции потока страничных требований из прошлого на будущее. Разновидности LRU различаются тем, как они учитывают время использования страницы. Очевидно, что запоминание точного времени обращения к каждой странице обошлось бы слишком дорого. Стратегии LRU используют биты used и dirty дескриптора страницы для оценки этого времени. Бит used устанавливается в 1 аппаратно при любом обращении к странице, бит dirty устанавливается аппаратно при обращении к странице для записи; оба бита сбрасывается ОС по своему усмотрению. Все множество присутствующих в реальной памяти страниц разбивается на четыре подмножества, в зависимости от значений этих полей:

  1. неиспользованные чистые (used=0, dirty=0),
  2. неиспользованные грязные (used=0, dirty=1),
  3. использованные чистые (used=1, dirty=0),
  4. использованные грязные (used=1, dirty=1).

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

Интересным образом используется бит dirty в стратегии SCC (second cycle chance) - цикл второго шанса. Алгоритм этого варианта стратегии LRU осуществляет циклический просмотр таблицы страничных кадров. Разумеется, лучшим кандидатом является неиспользованная страница (подмножества 1 и 2). Но если таковых нет, то выбирается страница с нулевым полем dirty (подмножество 3). Просмотренные страницы, оказавшиеся грязными, ОС не трогает (пока), но сбрасывает в них поле dirty. Таким образом, даже если при полном обороте поиска не будет найдена жертва, она обязательно найдется при втором обороте. "Второй шанс" здесь состоит в том, что страница, принудительно отмеченная как чистая, может еще в промежутке между двумя поисками восстановить поле dirty. При такой стратегии поле dirty уже не отражает истинного состояния страницы, ОС должна сохранять действительное состояние в расширении дескриптора страницы.

Более сложные варианты стратегии LRU предусматривают более, чем одноразрядный, учет времени. Метод временного штампа (timestamp) предусматривает хранение для каждой страницы многоразрядного кода. Периодически этот код сдвигается на разряд влево, а в освободившийся старший разряд заносится текущее значение поля used, после чего поле used сбрасывается в 0. Код временного штампа хранит, таким образом, предысторию использования страниц. Наилучшей жертвой оказывается та страница, у которой значение штампа (если интерпретировать его как целое число без знака) минимальное.

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

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

Указанные стратегии применимы как к локальному, так и к глобальному управлению памятью. В первом случае каждому процессу выделяется статический пул страничных кадров и свопинг ведется в пределах этого пула (например, AS/400). Это дает возможность применять для разнотипных процессов разные стратегии, но требует принятия решения о размере каждого пула. В случае же глобального управления выбранная стратегия применяется по всему доступному множеству страничных кадров и производится постоянное перераспределение ресурсов между процессами (например, VM, MVS). Динамическое перераспределение - качество полезное, но, если оно не учитывает уровень мультипрограммирования, то может привести к толкотне.

Ряд глобальных стратегий, управляющих уровнем мультипрограммирования, основывается на идее рабочего набора - WS (working set). Идея эта базируется на явлении локализации обращений к памяти. Любая программа не обращается ко всему своему адресному пространство одновременно. На каждом временном отрезке программа работает только с некоторым подмножеством адресов и, соответственно, с некоторым подмножеством страниц. Временной отрезок, на котором это подмножество квазипостоянно, называется фазой программы. Почти полное обновление этого подмножества называется сменой фазы. Рабочим набором процесса S(w) называется перечень страниц, к которым процесс обращался в течении последнего интервала виртуального времени w. Методы, основанные на идее рабочего набора, стремятся к тому, чтобы выполняющийся процесс постоянно имел свой рабочий набор в реальной памяти и страницы, входящие в рабочие наборы выполняющихся процессов не вытеснялись. Если у ОС нет возможности разместить в реальной памяти весь рабочий набор процесса, она снижает уровень мультипрограммирования, переводя процесс в состояние ожидания. При разблокировании процесса ОС имеет возможность перед его активизацией выполнить упреждающую подкачку (preload) всего его рабочего набора и тем самым значительно снизить частоту страничных отказов.

На практике, однако, идеальная реализация стратегии WS не представляется возможной по тем же соображениям, что и для идеальной LRU: нет возможности запоминать время каждого обращения. Адаптированный метод WS состоит в его определении через фиксированные интервалы времени. В начале каждого интервала все страницы, для которых распределены страничные кадры, считаются входящими в рабочий набор. В течение интервала все запросы процесса на новые страницы удовлетворяются. По окончании интервала те страницы, которые не были использованы (бит used), удаляются из рабочего набора. Зафиксированный в конце интервала рабочий набор служит исходным для следующего интервала.

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

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

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

Выделение памяти происходит при помощи системного вызова:

  vaddr = getMem(size)
который возвращает виртуальный адрес выделенной области заданного размера. На самом деле размер выделенной области кратен размеру страницы, а ее адрес выровнен по границе страницы.

Освобождение памяти:

  freeMem(vaddr)

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

    heapId = createHeap(size);
    vaddr = getHeapMem(heapID,size)
    freeHeapMem(vaddr)

3.6. Сегментно-страничная модель

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

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


Рис.3.8. Трансляция адресов. Cегментно-страничная модель

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

Поскольку в модели, приведенной на рис.3.8, каждый сегмент имеет собственную таблицу страниц, сами таблицы страниц могут занимать значительный объем в памяти. Простейшее решение этой проблемы представляет Windows 3.x: в системе существует единственная таблица страниц. Сегментная часть трансляции адреса имеет, таким образом, на выходе адрес в общем для всех процессов виртуальном страничном пространстве, объем которого превышает объем реальной памяти не более, чем в 4 раза. Подобное же, хотя и более гибкое и защищенное решение представляет VSE: система обеспечивает общий объем виртуальной памяти (до 2 Гбайт), который разбивается на разделы (до 12 статических и до 200 динамических), суммарный объем адресных пространств всех разделов не превышает общего объема виртуальной памяти. Простота решения, однако, может существенно сказываться на его эффективности: во-первых, из-за ограничений на размер виртуальной памяти, во-вторых, из-за необходимости выделять смежные дескрипторы в таблице страниц для страниц, смежных в виртуальной памяти. Поэтому действительно многозадачные системы применяют множественные таблицы страниц и включают память, занимаемую таблицами страниц, в страничный обмен. Вытеснение и загрузка частных таблиц страниц производится либо исключительно самой ОС (Unix), либо ОС использует для этого имеющиеся аппаратные средства (так, ОС, ориентированные на Intel-Pentium, используют каталоги страниц).

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

3.7. Плоская модель памяти.

Начиная с модели Intel-80386, в микропроцессорах Intel-Pentium адрес состоит из 16-разрядного номера сегмента и 32-разрядного смещения. 32-разрядное поле смещения позволяет адресовать до 4 Гбайт в пределах одного сегмента, что более чем достаточно для большинства мыслимых приложений и позволяет реализовать действительно "плоскую" (flat) модель виртуальной памяти процесса, представляющую собой линейное непрерывное пространство адресов..

Однако, при размере страницы 4 Кбайт таблица страниц должна содержать более 106 элементов и занимать 4 Мбайт памяти. Для экономии памяти аппаратура трансляции адреса микропроцессора поддерживает таблицы страниц двух уровней. Страничная таблица верхнего уровня называется каталогом страниц. Старшие 10 байт 32-разрядного смещения являются номером элемента в страничном каталоге. Элемент страничного каталога адресует таблицу страниц второго уровня. Следующие 10 байт смещения являются номером элемента в таблице страниц второго уровня. Элемент таблицы второго уровня адресует страничный кадр в реальной памяти, а младшие 12 байт смещения являются смещением в странице. Сегментная часть аппарата трансляции адреса оказывается излишней, в Intel-Pentium она не может быть отключена, но тот же эффект достигается, если каждому процессу назначается только один сегмент, и для процесса создается таблица сегментов, содержащая только один элемент. Поле base этого элемента адресует страничный каталог процесса, а каждый элемент страничного каталога - одну таблицу страниц. Структуры элементов каталога страниц и таблицы страниц второго уровня идентичны, каждая таблица страниц (каталог или таблица второго уровня) содержит 1024 элемента и сама занимает страничный кадр в памяти. Таблицы страниц участвуют в страничном обмене так же, как и страницы, содержащие любые другие данные и коды.

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

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

Большинство разработчиков приложений горячо приветствовали введение плоской модели памяти в современных ОС (OS/2 Warp, Windows 95, Windows NT), так как представление виртуального адреса в виде одного 32-разрядного слова избавляет программиста от необходимости различать ближние и дальние указатели и упрощает программирование. Но справедливы и предупреждения [17] о том, что отказ от сегментного структурирования виртуального адресного пространства кое в чем ограничивает возможности программиста. Большая же эффективность плоской модели памяти является объективным фактором, так как, во-первых, оперирование с 32-разрядными адресными словами уменьшает число команд в программе, а во-вторых, поскольку в 4-Гбайтном виртуальном адресном пространстве процесса могут быть размещены и процедуры, реализующие системные вызовы, то обращения процесса к ОС происходят как к собственным локальным процедурам и не требуют переключений контекста.

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

3.8. Одноуровневая модель памяти.

Дальнейшее расширение разрядной сетки процессоров может привести к появлению совершенно новых моделей памяти. Сейчас трудно с уверенностью прогнозировать, какая модель будет доминировать, на сегодняшний день большинство 64-разрядных ОС представляют собой клоны Unix, и расширенный виртуальный адрес используется в них для отображения в память файлов. Более активно использует 64-разрядный адрес AS/400. На примере последней мы и рассмотрим одноуровневую (single-level) модель памяти. Эта модель была реализована уже в System/38 и в ранних моделях AS/400 на базе 48-разрядного адреса, но мы сосредоточимся на ее 64-разрядной реализации в Advanced Series на процессоре Power PC

Отметим прежде всего, что эта "новая" модель памяти на самом деле является "хорошо забытой старой": в вычислительной системе Atlas (Англия, 1966г.) - первой системе с виртуальной памятью - была реализована именно эта модель. Впоследствии эта модель не нашла применения из-за ограниченных возможностей аппаратных средств, современное же состояние аппаратных средств позволяет вновь к ней вернуться на качественно ином уровне.

64-разрядное адресное слово позволяет процессу иметь плоскую виртуальную память размером до 64 Эбайт (эксабайт). В AS/400 эта возможность позволяет реализовать два принципиально важных свойства модели памяти:

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

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

Плоская структура адресного пространства в одноуровневой модели снимает необходимость в сегментной фазе динамической трансляции адреса. В процессоре Power PC имеется возможность программного отключения трансляции сегмента в аппаратном процессе трансляции адреса. AS/400 может работать как в режиме с сегментацией, так и без нее. Режим с сегментацией включается только при повышенном уровне защиты.

Размер страницы в современных моделях AS/400 - 4Кбайт. Даже в процессоре Intel80386 таблица страниц для 32-разрядного адресного пространства не размещается в оперативной памяти и применяется двухэтапная трансляция номера страницы, как же решается эта проблема для 64-разрядного адресного пространства? Здесь применяется, так называемая, инверсная таблица страниц. В оперативной памяти хранятся дескрипторы не всех виртуальных страниц, а только тех, которые уже размещены в оперативной памяти. Поскольку виртуальное адресное пространство общее для всех процессов, таблица страниц также одна. При трансляции виртуального адреса требуемая страница прежде всего ищется в таблице страниц реальной памяти, а при неуспешном результате такого поиска - на внешней памяти. Для поиска в таблице страниц применяется метод хеширования. 64-разрядный виртуальный адрес путем несложных преобразований, состоящих их ряда побитовых логических операций, преобразуется в номер элемента таблицы страниц. Число элементов в таблице страниц зависит от размера оперативной памяти в системе и выбирается таким образом, что таблица страниц занимает фиксированный процент реальной оперативной памяти. Поскольку разрядность номера элемента значительно меньше разрядности виртуального адреса в процессе преобразования виртуальных адресов неизбежны коллизии - случаи преобразования разных виртуальных адресов в один и тот же номер элемента. Поэтому в элементе таблицы страниц зарезервировано место для нескольких (восьми) дескрипторов страниц, и после выбора элемента продолжается линейный поиск страницы в элементе таблицы. В таблице страниц также предусмотрена область переполнения - для случая, если число коллизий на один элемент таблицы превысит размер элемента, но на практике до ее использования дело не доходит.

Механизм поиска в таблице страниц может показаться достаточно сложным и времяемким, но, во-первых, архитектура микропроцессора Power PC включает в себя конвейер, а во-вторых, значительный объем ассоциативного буфера страниц (512 и более элементов) позволяет более чем в 90% случаев даже не производить поиск в таблице страниц.

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

Контрольные вопросы

  1. Часто единственным достоинством виртуальной памяти называют возможность обеспечить для процесса объем виртуального адресного пространства, превышающий объем реальной памяти. Назовите другие достоинства виртуальной памяти.
  2. В чем достоинства и недостатки преобразования виртуальных адресов в реальные во время выполнения программы? Какая часть работы по этому преобразованию выполняется аппаратным обеспечением, а какая - ОС?
  3. Иногда считают, что виртуальная память может быть обеспечена только в системах с аппаратной поддержкой динамической трансляции адреса. Докажите, что это не так.
  4. Почему при поиске свободной памяти стратегия "самый подходящий" оказывается хуже, чем "первый подходящий".
  5. Сравните сегментную и страничную модели виртуальной памяти. Какая из них представляется Вам лучшей и почему?
  6. Дополните приведенные в разделе 3.5. соображения по поводу выбора размера страницы.
  7. Смоделируйте ситуацию применения дисциплины вытеснения FCFS, в которой увеличение числа реальных страниц приведет к увеличению числа страничных отказов.
  8. Что такое кластерная подкачка страниц? Почему в современных ОС она становится все более популярной?
  9. Каким образом ОС может определять, к каким страницам будут обращения в ближайшее время?
  10. Большой размер виртуальной памяти процесса может приводить к тому, что даже таблица страниц не будет помещаться в реальной памяти. Какими путями решается эта проблема в современных ОС?
  11. Каким образом снижение стоимости памяти влияет на дисциплины управления памятью?
  12. Какие принципиальные изменения в концепции памяти может повлечь за собой увеличение разрядности адреса?

НазадОглавлениеВперед
Индекс