Страничный способ организации виртуальной памяти

Как уже упоминалось, при страничном способе организации виртуальной памяти все фрагменты программы, на которые она разбивается (за исключением последней ее части), получаются одинаковыми. Одинаковыми полагаются и единицы памяти, которые предоставляются для размещения фрагментов программы. Эти одинаковые части называют страницами и говорят, что оперативная память разбивается на физические страницы, а программа – на виртуальные страницы. Часть виртуальных страниц задачи размещается в оперативной памяти, а часть – во внешней. Обычно место во внешней памяти, в качестве которой в абсолютном большинстве случаев выступают накопители на магнитных дисках (поскольку они относятся к быстродействующим устройствам с прямым доступом), называют файлом подкачки, или страничным файлом (paging file). Иногда этот файл называют swap-файлом, тем самым подчеркивая, что записи этого файла – страницы – замещают друг друга в оперативной памяти. В некоторых операционных системах выгруженные страницы располагаются не в файле, а в специальном разделе дискового пространства. Разбиение всей оперативной памяти на страницы одинаковой величины, причем кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двухмерном. Первая координата адресного пространства – это номер страницы, вторая координата – номер ячейки внутри выбранной страницы (его называют индексом). Таким образом, физический адрес определяется парой (Рp, i), а виртуальный адрес – парой (Pv, i), где Pv – номер виртуальной страницы, Рр – номер физической страницы, i – индекс ячейки внутри страницы. Количество битов, отводимое под индекс, определяет размер страницы, а количество битов, отводимое под номер виртуальной страницы, - объем потенциально доступной для программы виртуальной памяти. Отображение, осуществляемое системой во время исполнения, сводится к отображению Pv в Рр и приписыванию к полученному значению битов адреса, задаваемых величиной i. При этом нет необходимости ограничивать число виртуальных страниц числом физических, то есть не поместившиеся страницы можно размещать во внешней памяти, которая в данном случае служит расширением оперативной.

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

- только чтение;

- чтение и запись;

- только выполнение.

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

При обращении к виртуальной странице, не оказавшейся в данный момент в оперативной памяти, возникает прерывание, и управление передается диспетчеру памяти, который должен найти свободное место. Обычно предоставляется первая же свободная страница. Если свободной физической страницы нет, то диспетчер памяти по одной из вышеупомянутых дисциплин замещения (LRU, LFU, FIFO, случайный доступ) определит страницу, подлежащую расформированию или сохранению во внешней памяти. На ее месте он разместит новую виртуальную страницу, к которой было обращение из задачи, но которой не оказалось в оперативной памяти. Напомним, что алгоритм LFU выбирает для замещения ту страницу, на которую не было ссылки на протяжении наиболее длительного периода времени. Алгоритм LRU ассоциирует с каждой страницей время ее последнего использования. Для замещения выбирается та страница, которая дольше всех не использовалась. Для использования дисциплин LRU и LFU в процессоре должны быть соответствующие аппаратные средства. В дескрипторе страницы размещается бит обращения, который становится единичным при обращении к дескриптору. Если объем физической памяти небольшой и даже часто требуемые страницы не удается разместить в оперативной памяти, возникает так называемая «пробуксовка». Другими словами, пробуксовка – это ситуация, при которой загрузка нужной страницы вызывает перемещение во внешнюю память той страницы, с которой мы тоже активно работаем. Чтобы этого не допускать, желательно увеличить объем оперативной памяти (сейчас это просто, поскольку стоимость модуля оперативной памяти многократно снизилась), уменьшить количество параллельно выполняемых задач или прибегнуть к более эффективным дисциплинам замещения. Для абсолютного большинства современных операционных систем характерна дисциплина замещения страниц LRU как самая эффективная. Так, именно эта дисциплина используется в OS/2 и в Linux. Однако в операционных системах Windows NT/2000/XP разработчики, желая сделать их максимально независимыми от аппаратных возможностей процессора, отказались от этой дисциплины и применили правило FIFO. А для того чтобы хоть как-то компенсировать неэффективность правила FIFO, была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск или просто расформированы. Принцип буферизации прост. Прежде чем замещаемая страница действительно окажется во внешней памяти или просто расформированной, она помечается как кандидат на выгрузку. Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на ее место в «буфер» попадает следующий «кандидат». Величина такого «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT/2000/XP намного ниже, чем в других операционных системах, и явление пробуксовки начинается даже при существенно большем объеме оперативной памяти. В ряде операционных систем с пакетным режимом работы для борьбы с пробуксовкой используется метод «рабочего множества». Рабочее множество – это множество «активных» страниц задачи за некоторый интервал Т, то есть тех страниц, к которым было обращение за этот интервал времени. Реально количество активных страниц задачи (за интервал Т) все время изменяется, и это естественно, но, тем не менее, для каждой задачи можно определить среднее количество ее активных страниц. Это количество и есть рабочее множество задачи. Наблюдения за исполнением множества различных программ показали, что даже если интервал Т равен времени выполнения всей работы, то размер рабочего множества часто существенно меньше, чем общее число страниц программы. Таким образом, если операционная система может определить рабочие множества исполняющихся задач, то для предотвращения пробуксовки достаточно планировать на выполнение только такое количество задач, чтобы сумма их рабочих множеств не превышала возможности системы. Как и в случае с сегментным способом организации виртуальной памяти, страничный механизм приводит к тому, что без специальных аппаратных средств он существенно замедляет работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов. Наиболее эффективным механизмом кэширования является ассоциативный кэш. Именно такой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начиная с i80386, который поддерживает страничный способ распределения памяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно быстрое обращение к памяти размером 128 Кбайт. Итак, основным достоинством страничного способа распределения памяти является минимальная фрагментация. Поскольку на каждую задачу может приходиться по одной незаполненной странице, очевидно, что память можно использовать достаточно эффективно; этот метод организации виртуальной памяти был бы одним из самых лучших, если бы не два следующих обстоятельства (недостатка).

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

- таблицы страниц нужно размещать в памяти:

- таблицы нужно обрабатывать - именно с ними работает диспетчер памяти – на этот тратится время.

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

- межстраничные переходы, как правило, осуществляются чаще, нежели межсегментные;

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

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

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

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

- Разбиение программы на сегменты позволяет размещать сегменты в памяти целиком.

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

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

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

Вопрос №8 Страничный способ организации виртуальной памяти и схема нахождения физического адреса

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

При страничном способе организации виртуальной памяти она разбивается на части одинаковой длины. Это страницы. В этом случае принято, что память разбита на физические страницы, а задача на виртуальные. Часть страниц размещается в ОП, часть во внешней памяти, обычно на винчестерах в файлах подкачки или страничном файле. Задача может занимать несколько полных страниц и только последняя может содержать меньше информации. Разбиение памяти осуществляется на страницы одинаковой величины, кратной степени 2, часто 4К. Для того чтобы обратится к какой-либо ячейке, должен быть образован двумерный адрес: а) номер страницы; б) номер ячейки внутри страницы (называется индексом). Количество битов, отведенное под нумерацию индекса, определяет размер страницы, а количество битов, отводимое под номер страницы, определяет объем возможной виртуальной памяти.

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

Регистр таблицы страниц Виртуальный адрес команды

(из дескриптора задачи) P I

64020

Таблица страниц текущей задачи Страница № 25

  По этому адресу находится команда иди данное

№ страниц Права доступа 624 25000

(физический)

25 25624

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

Адрес таблицы страниц (дескрипторов страниц задачи) находится в поле дескриптора задачи (в примере – 64000), виртуальный адрес исполняемого данного или исполняемого кода состоит из двух полей – Р (страницы) и I (индекса). При трансляции программы каждой команде (или данному) был определен виртуальный адрес – номер страницы и смещение команды на этой странице, например, 20 и 624. Когда программа операционной системой устанавливается для выполнения процессором (или в очередь на выполнение), то операционная система в таблицу дескрипторов страниц этой задачи записывает реальные адреса начала этих страниц в оперативной памяти (или на винчестере, если страница находится там). Но, для того, чтобы найти место расположение дескрипторов страниц данной задачи, в дескрипторе задачи находим адрес их начала.

Например, в дескрипторе задачи находится запись, что таблица дескрипторов страниц этой задачи начинается с адреса 64000. Виртуальный адрес указывает, например, в нашем случае, что команда (или данное) находится на 20 виртуальной странице этой задачи. По этим данным операционная система находит ячейку, где записан номер физической страницы в ОП – 64000+20= 64020. Допустим, 20-й странице задачи ОС выделила 25-ю физическую страницу в ОП. Теперь ОС рассчитывает реальный адрес нашей команды – 25000+624=25624.

При обращении к странице, которой не оказалось в данный момент в оперативной памяти, возникает прерывание, по которому управление передается диспетчеру памяти. Диспетчер памяти находит свободное место (первая свободная страница). Может случиться, что свободного места нет. Тогда по одной из дисциплин замещения страниц (FIFO – first in first out -первый пришёл первый выбывает, LRU – least recently used - замещается последняя из недавно используемых, LFU – least frequently used - замещается тот, который реже остальных используется, или по случайному выбору замещаемого сегмента) происходит ротация страниц.

В подавляющем большинстве операционных систем используют дисциплину замещения LRU, как наиболее эффективную. Но она требует соответствующих аппаратных средств, иначе работа вычислительной системы сильно замедляет свою работу. Разработчики Windows NT, чтобы максимально не зависеть от аппаратных возможностей ЭВМ, применили правило замещения страниц FIFO.

№ страницы (адрес страничного кадра)

Для ОС

“Грязный”

Обращения

Защиты памяти

Присутствия

…

…

Дескриптор страницы

Для описания каждой страницы создается соответствующий дескриптор длиной 32 бита.

20 битов (12 – 31) определяют № страницы. Если добавить к этому номеру 12 нулей, то получается физический адрес начала страницы в памяти.

0-й бит – это бит присутствия. Если он равен 0, то эта виртуальная страница находится на винчестере и, для ее передачи в оперативную память необходимо прерывание и передача её в ОП. Если бит равен 1, то страница уже находится в оперативной памяти.

1-й и 2-й биты используются операционной системой для защиты памяти.

5-й бит – бит обращения. Эта страница уже работала в ОП и она может участвовать при замещении страниц диспетчером.

6-й бит – “грязный”. Этот бит указывает, что страница модифицировалась и при необходимости занесения на её место новой страницы, необходимо её переписать во внешнюю память поверх старой записи.

3, 4, 7 и 8 биты содержат 0 и не используются.

9 – 11 биты зарезервированы для использования системными программистами при разработке подсистемы виртуальной памяти (если будут разрабатывать что-нибудь новенькое).

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

Но страничный способ организации памяти имеет два существенных недостатка:

Первый: Страничный способ требует больших накладных расходов:

- таблицы страниц нужно размещать в памяти;

- время процессора тратится на обработку этих таблиц.

Второй: Программы разбиваются на страницы случайным образом, это приводит к тому, что:

- часто происходят межстраничные переходы, гораздо чаще, чем межсегментные. Чаще нужно тратить время на смену страниц;

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

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

Вопрос №№ 9,10 Сегментно-страничный способ организации виртуальной памяти и схема нахождения и формирования физического адреса

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

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

S –сегмент Р – страница I - индекс

Из таблицы сегментов Виртуальный адрес

Номер физической Число Права страницы страниц доступа 15 36000 20

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

35015 35000

36010

Номер физиче- Права ской страницы доступа   10 45000

  Нужная команда

36000 Таблица страниц задачи 45000 страница № 45

45600

Схема преобразования виртуального адреса в физический адрес при сегментно-страничной организации памяти

Если в таблице дескрипторов сегментов указано, что таблица сегментов нашей задачи находится по адресу 35000, а в виртуальном адресе указан 15-й сегмент, то ОС по этим данным найдет запись, где будет адрес начала нашего сегмента (35000+15=35015). Поэтому адресу находим адрес начала таблицы страниц (допустим, 36000). Складывая его с № страницы виртуального адреса находим запись в таблице страниц, где указан адрес физической страницы. Складывая этот адрес с индексом виртуального адреса, находим физический адрес нашей исполняемой программы.

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

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

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

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

Дата добавления: 2015-05-29