Концепция виртуальной памяти

 

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

 

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

 

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

 

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

 

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

 

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

 

 

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

 

Поблочное отображение

 

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

 

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

 

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

 

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

 

Адреса в системе поблочного отображения являются двухкомпонентными («двумерными»). Чтобы обратиться к конкретному элементу данных, программа указывает блок, в котором этот элемент располагается, и смещение этого элемента относительно начала блока (рис 9.6). Виртуальный адрес v указывается при помощи упорядоченной пары (b, d), где b — номер блока, в котором размещается соответствующий элемент, a d — смещение относительно начального адреса этого блока.

 

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

 

31) Системы с комбинированной странично-сегментной организацией. Таблица процессов и преобразование адресов.

 

9.7 Системы с комбинированной странично-сегментной организацией

 

9.7.1. Основные концепции

 

И сегментная, и страничная организации имеют важные достоинства как способы построения виртуальной памяти. Начиная с систем середины 60-х годов, в частности с информационно-вычислительной системы с разделением времени Multics и системы разделения времени TSS корпорации IBM, во многих вычислительных машинах применяется комбинированная странично-сегментная организация памяти. Эти системы обладают достоинствами обоих способов реализации виртуальной памяти. Сегменты обычно содержат целое число страниц, причем не обязательно, чтобы все страницы сегмента находились в первичной памяти одновременно, а смежные страницы виртуальной памяти не обязательно должны оказываться смежными в реальной памяти. В системе со странично-сегментной организацией применяется трехкомпонентная (трехмерная) адресация, т. е. адрес виртуальной памяти v определяется как упорядоченная тройка v = (s, p, d), где s — номер сегмента, р — номер страницы, а d — смещение в рамках страницы, по которому находится нужный элемент (рис. 9.18).

 

 

Рис. 9.18 Формат виртуального адреса в странично-сегментной системе

 

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

 

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

 

Выполняющийся процесс делает ссылку по виртуальному адресу n = (s, р, d). Самые последние по времени обращения страницы имеют соответствующие строки в ассоциативной таблице. Система производит ассоциативный поиск, пытаясь найти строку с параметрами (s, р) в ассоциативной таблице. Если такая строка здесь обнаруживается, то адрес страничного кадра р', по которому эта страница размещается в первичной памяти, соединяется со смещением d, образуя реальный адрес r, соответствующий виртуальному адресу v, - и на этом преобразование адреса завершается.

 

В обычном случае большинство запросов на преобразование адресов удается удовлетворить подобным ассоциативным поиском. Если же требуемого адреса в ассоциативной памяти нет, то преобразование осуществляется способом полного прямого отображения. Это делается следующим образом: базовый адрес b таблицы сегментов прибавляется к номеру сегмента s, так что образуется адрес b+s строки для сегмента s в таблице сегментов по первичной памяти. В этой строке указывается базовый адрес s' таблицы страниц для сегмента s. Номер страницы р прибавляется к s', так что образуется адрес p+s' строки в таблице страниц для страницы р сегмента s. Эта таблица позволяет установить, что виртуальной странице р соответствует номер кадра р'. Этот номер кадра соединяется со смещением d, так что образуется реальный адрес r, соответствующий виртуальному адресу v = (s, р, d).

 

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

 

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

 

 

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

 

Протокол ARP

 

В этом разделе мы рассмотрим то, как при посылке IP-пакета определяется Ethernet-адрес назначения. Для отображения IP-адресов в Ethernetадреса используется протокол ARP (Address Resolution Protocol - адресный протокол). Отображение выполняется только для отправляемых IP-пакетов, так как только в момент отправки создаются заголовки IP и Ethernet.

 

ARP-таблица для преобразования адресов

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

 

---------------------------------------------

| IP-адрес Ethernet-адрес |

---------------------------------------------

| 223.1.2.1 08:00:39:00:2F:C3 |

| 223.1.2.3 08:00:5A:21:A7:22 |

| 223.1.2.4 08:00:10:99:AC:54 |

---------------------------------------------

Табл.1. Пример ARP-таблицы

Принято все байты 4-байтного IP-адреса записывать десятичными числами, разделенными точками. При записи 6-байтного Ethernet-адреса каждый байт указывается в 16-ричной системе и отделяется двоеточием.

 

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

 

Порядок преобразования адресов

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

 

Запросы и ответы протокола ARP

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

По сети передается широковещательный ARP-запрос.

Исходящий IP-пакет ставится в очередь.

 

Каждый сетевой адаптер принимает широковещательные передачи. Все драйверы Ethernet проверяют поле типа в принятом Ethernet-кадре и передают ARP-пакеты модулю ARP. ARP-запрос можно интерпретировать так: "Если ваш IP-адрес совпадает с указанным, то сообщите мне ваш Ethernet-адрес". Пакет ARP-запроса выглядит примерно так:

 

 

-----------------------------------------------------------

| IP-адрес отправителя 223.1.2.1 |

| Ethernet-адрес отправителя 08:00:39:00:2F:C3 |

-----------------------------------------------------------

| Искомый IP-адрес 223.1.2.2 |

| Искомый Ethernet-адрес <пусто> |

-----------------------------------------------------------

Табл.2. Пример ARP-запроса

 

 

Каждый модуль ARP проверяет поле искомого IP-адреса в полученном ARP-пакете и, если адрес совпадает с его собственным IP-адресом, то посылает ответ прямо по Ethernet-адресу отправителя запроса. ARP-ответ можно интерпретировать так: "Да, это мой IP-адрес, ему соответствует такой-то Ethernet-адрес". Пакет с ARP-ответом выглядит примерно так:

 

-----------------------------------------------------------

| IP-адрес отправителя 223.1.2.2 |

| Ethernet-адрес отправителя 08:00:28:00:38:A9 |

-----------------------------------------------------------

| Искомый IP-адрес 223.1.2.1 |

| Искомый Ethernet-адрес 08:00:39:00:2F:C3 |

-----------------------------------------------------------

Табл.3. Пример ARP-ответа

 

 

Этот ответ получает машина, сделавшая ARP-запрос. Драйвер этой машины проверяет поле типа в Ethernet-кадре и передает ARP-пакет модулю ARP. Модуль ARP анализирует ARP-пакет и добавляет запись в свою ARP-таблицу.

 

Обновленная таблица выглядит следующим образом:

 

---------------------------------------------

| IP-адрес Ethernet-адрес |

---------------------------------------------

| 223.1.2.1 08:00:39:00:2F:C3 |

| 223.1.2.2 08:00:28:00:38:A9 |

| 223.1.2.3 08:00:5A:21:A7:22 |

| 223.1.2.4 08:00:10:99:AC:54 |

---------------------------------------------

Табл.4. ARP-таблица после обработки ответа

 

 

Продолжение преобразования адресов

Новая запись в ARP-таблице появляется автоматически, спустя несколько миллисекунд после того, как она потребовалась. Как вы помните, ранее на шаге 2 исходящий IP-пакет был поставлен в очередь. Теперь с использованием обновленной ARP-таблицы выполняется преобразование IPадреса в Ethernet-адрес, после чего Ethernet-кадр передается по сети. Полностью порядок преобразования адресов выглядит так:

По сети передается широковещательный ARP-запрос.

Исходящий IP-пакет ставится в очередь.

Возвращается ARP-ответ, содержащий информацию о соответствии IP- и Ethernet-адресов. Эта информация заносится в ARP-таблицу.

Для преобразования IP-адреса в Ethernet-адрес у IP-пакета, постав ленного в очередь, используется ARP-таблица.

Ethernet-кадр передается по сети Ethernet.

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

 

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

 

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

 

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