При разработке виртуализации процессора мы сосредоточились на общем механизме, известном как limited direct execution (или LDE). Идея LDE проста: по большей части пусть программа работает непосредственно на аппаратном обеспечении; однако в определенные ключевые моменты времени (например, когда процесс выдает системный вызов или происходит прерывание таймера) ОС включается и убеждается в том, что всё происходит правильно. Таким образом, ОС, с небольшой аппаратной поддержкой, изо всех сил старается уйти с пути работающей программы, чтобы обеспечить эффективную виртуализацию; однако, вмешиваясь в эти критические моменты времени, ОС гарантирует, что она сохраняет контроль над аппаратным обеспечением. Эффективность и контроль-две главные цели любой современной операционной системы.
При виртуализации памяти мы будем следовать аналогичной стратегии, достигая одновременно эффективности и контроля, обеспечивая при этом желаемую виртуализацию. Эффективность диктует, что мы используем аппаратную поддержку, которая сначала будет довольно примитивной (например, всего несколько регистров), но вырастет до довольно сложной (например, TLBs, поддержка таблиц страниц и т. д., Как вы увидите). Контроль подразумевает, что ОС гарантирует, что ни одно приложение не имеет доступа к какой-либо памяти, кроме своей собственной; таким образом, чтобы защитить приложения друг от друга, а ОС от приложений, нам понадобится помощь аппаратного обеспечения и здесь. Наконец, нам потребуется немного больше от системы виртуальных машин с точки зрения гибкости; в частности, мы хотели бы, чтобы программы могли использовать свои адресные пространства так, как им заблагорассудится, что облегчит программирование системы. И таким образом мы приходим к проблеме:
КАК ЭФФЕКТИВНО И ГИБКО ВИРТУАЛИЗИРОВАТЬ ПАМЯТЬ
Как построить эффективную виртуализацию памяти? Как мы обеспечиваем гибкость, необходимую приложениям? Как мы можем контролировать, к каким ячейкам памяти приложение может получить доступ, и таким образом гарантировать, что доступ к памяти приложения должным образом ограничен? Как все это сделать эффективно?
Общий метод, который мы будем использовать, который вы можете рассматривать как дополнение к нашему общему подходу limited direct execution, - это то, что называется аппаратной трансляцией адресов или просто трансляцией адресов для краткости. С помощью преобразования адресов аппаратное обеспечение преобразует каждый доступ к памяти (например, команду fetch, load или store), изменяя виртуальный адрес, предоставляемый инструкцией, на физический адрес, где на самом деле находится требуемая информация. Таким образом, для каждой ссылки на память аппаратное обеспечение выполняет преобразование адресов для перенаправления ссылок на память приложения в их фактическое местоположение в памяти.
Конечно, аппаратное обеспечение само по себе не может виртуализировать память, поскольку оно просто эффективно обеспечивает низкоуровневый механизм для этого. ОС должна вмешиваться в ключевые моменты, чтобы настроить аппаратное обеспечение так, чтобы происходили правильные переводы; таким образом, она должна управлять памятью, отслеживая, какие места свободны и какие используются, и разумно вмешиваться, чтобы сохранить контроль над тем, как используется память.
И снова цель всей этой работы-создать прекрасную иллюзию: что у программы есть своя личная память, где хранятся ее собственный код и данные. За этой виртуальной реальностью скрывается уродливая физическая истина: многие программы фактически делятся памятью одновременно, когда процессор (или процессоры) переключается между запуском одной программы и следующей. Благодаря виртуализации ОС (с помощью аппаратного обеспечения) превращает уродливую машинную реальность в полезную, мощную и простую в использовании абстракцию.
Допущения
Наши первые попытки виртуализации памяти будут очень простыми, почти смехотворными. Продолжайте, смейтесь сколько хотите; довольно скоро ОС будет смеяться над вами, когда вы попытаетесь понять все тонкости TLB, многоуровневых таблиц страниц и других технических чудес. Вам не нравится идея, что ОС смеется над вами? Что ж, тогда вам может не повезти; именно так работает ОС.
В частности, на данный момент мы будем считать, что адресное пространство пользователя должно располагаться последовательно в физической памяти. Мы также предположим для простоты, что размер адресного пространства не слишком велик; в частности, что он меньше размера физической памяти. Наконец, мы также предположим, что каждое адресное пространство имеет точно такой же размер. Не волнуйтесь, если эти предположения кажутся нереалистичными; мы будем дополнять их по мере продвижения, тем самым достигая реалистичной виртуализации памяти.
Пример
Чтобы лучше понять, что нам нужно сделать для реализации трансляции адресов и зачем нам нужен такой механизм, давайте рассмотрим простой пример. Представьте себе, что существует процесс, адресное пространство которого показано на рис. 15.1. здесь мы рассмотрим короткую кодовую последовательность, которая загружает значение из памяти, увеличивает его на три, а затем сохраняет значение обратно в память. Вы можете себе представить, что представление этого кода на языке Си может выглядеть следующим образом:
ИНТЕРПОЗИЦИЯ-ЭТО МОЩНАЯ СИЛА
Интерпозиция-это универсальный и мощный метод, который часто используется с большим эффектом в компьютерных системах. При виртуализации памяти аппаратное обеспечение будет вмешиваться в каждый доступ к памяти и переводить каждый виртуальный адрес, выданный процессом, на физический адрес, где фактически хранится требуемая информация. Однако общая техника интерпозиции применима гораздо шире; действительно, почти любой четко определенный интерфейс может быть добавлен в систему, чтобы расширить функциональность или улучшить какой-либо другой аспект системы. Одним из обычных преимуществ такого подхода является прозрачность; интерпозиция часто выполняется без изменения интерфейса клиента, таким образом, не требуя никаких изменений для него.
Компилятор превращает эту строку кода в сборку, которая может выглядеть примерно так (в сборке x86). Используйте objdump на Linux или otool на Mac, чтобы дизассемблировать его:
Этот фрагмент кода относительно прост; он предполагает, что адрес x был помещен в регистр ebx, а затем загружает значение по этому адресу в регистр общего назначения eax с помощью инструкции movl (для перемещения “длинного слова”). Следующая инструкция добавляет 3 к eax, а последняя инструкция сохраняет значение в eax обратно в память в том же месте.
На рис. 15.1 проследите, как код и данные располагаются в адресном пространстве процесса; кодовая последовательность из трех команд расположена по адресу 128 (в разделе кода вверху), а значение переменной x-по адресу 15 КБ (в стеке внизу). На рисунке начальное значение x равно 3000, как показано в его расположении в стеке.
Когда эти инструкции выполняются, с точки зрения процесса, происходят следующие обращения к памяти
- Получить инструкцию по адресу 128
- Выполнить эту инструкцию (загрузка с адреса 15 КБ)
- Получить инструкцию по адресу 132
- Выполнить эту инструкцию (без ссылки на память)
- Получить инструкцию по адресу 135
- Выполнить эту инструкцию (хранить по адресу 15 КБ)
С точки зрения программы, ее адресное пространство начинается с адреса 0 и увеличивается максимум до 16 КБ; все ссылки на память, которые она генерирует, должны находиться в этих пределах. Однако для виртуализации памяти ОС хочет поместить процесс в другое место в физической памяти, не обязательно по адресу 0. Таким образом, у нас возникает проблема: как мы можем переместить этот процесс в память таким образом, чтобы он был прозрачен для процесса? Как мы можем создать иллюзию виртуального адресного пространства, начинающегося с 0, когда на самом деле адресное пространство находится на каком-то другом физическом адресе?
Пример того, как может выглядеть физическая память после размещения адресного пространства этого процесса в памяти, приведен на рис.15.2. На рисунке вы можете видеть, что ОС использует первый слот физической памяти для себя и что она переместила процесс из приведенного выше примера в слот, начинающийся с адреса физической памяти 32 КБ. Два других слота свободны (16 КБ-32 КБ и 48 КБ-64 КБ).
Динамическое (аппаратно-зависимое) перемещение
Чтобы получить некоторое представление об аппаратной трансляции адресов, мы сначала обсудим ее первое воплощение. Впервые в конце 1950-х годов в машинах с разделением времени появилась простая идея, называемая base and bounds; эта техника также называется динамическим перемещением; мы будем использовать оба термина взаимозаменяемо.
В частности, нам понадобятся два аппаратных регистра внутри каждого процессора: один называется базовым регистром, а другой-границами (иногда называемыми лимитрегистром). Эта пара базы и границ позволит нам разместить адресное пространство в любом месте физической памяти и сделать это, гарантируя, что процесс может получить доступ только к своему собственному адресному пространству.
SOFTWARE-BASE RELOCATION
В первые дни, до появления аппаратной поддержки, некоторые системы выполняли грубую форму перемещения исключительно с помощью программных методов. Основной метод называется статическим перемещением, при котором часть программного обеспечения, известная как загрузчик, берет исполняемый файл, который должен быть запущен, и переписывает его адреса в нужное смещение в физической памяти. Например, если инструкция была загружена с адреса 1000 в регистр (например, movl 1000, %eax), а адресное пространство программы было загружено, начиная с адреса 3000 (а не 0, как думает программа), загрузчик переписал бы инструкцию, чтобы смещать каждый адрес на 3000 (например, movl 4000, %eax). Таким образом, достигается простое статическое перемещение адресного пространства процесса. Однако статическое перемещение имеет множество проблем. Во-первых, и это самое главное, он не обеспечивает защиту, так как процессы могут генерировать плохие адреса и таким образом незаконно получать доступ к памяти других процессов или даже ОС; в целом, аппаратная поддержка, вероятно, необходима для истинной защиты. Еще одним недостатком является то, что после размещения трудно впоследствии переместить адресное пространство в другое место.
В этой установке каждая программа записывается и компилируется так, как если бы она была загружена по нулевому адресу. Однако, когда программа начинает работать, ОС решает, где в физической памяти она должна быть загружена, и устанавливает базовому регистру это значение. В приведенном выше примере ОС решает загрузить процесс по физическому адресу 32 КБ и таким образом устанавливает базовому регистру это значение.
Интересные вещи начинают происходить, когда процесс запущен. Теперь, когда любая ссылка на память генерируется процессом, она преобразуется процессором следующим образом:
Каждая ссылка на память, генерируемая процессом, является виртуальным адресом; аппаратное обеспечение, в свою очередь, добавляет содержимое базового регистра к этому адресу, и в результате получается физический адрес, который может быть выдан системе памяти.
Чтобы лучше понять это, давайте проследим, что происходит, когда выполняется одна команда. В частности, давайте рассмотрим одну инструкцию из нашей предыдущей последовательности:
Счетчик программ (PC) установлен на 128; когда аппаратное обеспечение должно извлечь эту инструкцию, оно сначала добавляет значение к значению Базового регистра 32 КБ (32768), чтобы получить физический адрес 32896; затем аппаратное обеспечение извлекает инструкцию из этого физического адреса. Затем процессор начинает выполнять инструкцию. В какой-то момент процесс затем выдает нагрузку с виртуального адреса 15 КБ, которую процессор берет и снова добавляет в базовый регистр (32 КБ), получая конечный физический адрес 47 КБ и таким образом желаемое содержимое.
АППАРАТНОЕ ДИНАМИЧЕСКОЕ ПЕРЕМЕЩЕНИЕ
При динамическом перемещении небольшое количество оборудования проходит долгий путь. А именно, базовый регистр используется для преобразования виртуальных адресов (генерируемых программой) в физические адреса. Регистр границ (или пределов) гарантирует, что такие адреса находятся в пределах адресного пространства. Вместе они обеспечивают простую и эффективную виртуализацию памяти.
Преобразование виртуального адреса в физический - это именно тот метод, который мы называем трансляцией адресов; то есть аппаратное обеспечение берет виртуальный адрес, на который, по мнению процесса, оно ссылается, и преобразует его в физический адрес, где на самом деле находятся данные. Поскольку это перемещение адреса происходит во время выполнения и поскольку мы можем перемещать адресные пространства даже после запуска процесса, этот метод часто называют динамическим перемещением.
Теперь вы можете спросить: Что случилось с этим регистром границ (limit)? В конце концов, разве это не "base and bounds" подход? Действительно, так оно и есть. Как вы могли догадаться, регистр границ существует, чтобы помочь с защитой. В частности, процессор сначала проверит, что ссылка на память находится в пределах границ, чтобы убедиться, что она легальна; в простом примере выше регистр границ всегда будет установлен на 16 КБ. Если процесс генерирует виртуальный адрес, превышающий границы, или отрицательный, процессор вызовет исключение, и процесс, скорее всего, будет завершен. Таким образом, смысл границ состоит в том, чтобы убедиться, что все адреса, генерируемые процессом, являются законными и находятся в пределах “границ” процесса.
Следует отметить, что регистры base и bounds - это аппаратные структуры, хранящиеся на чипе (по одной паре на процессор). Иногда люди называют часть процессора, которая помогает с преобразованием адресов, блоком управления памятью (MMU); по мере развития более сложных методов управления памятью мы будем добавлять в MMU больше схем.
Небольшое отступление о связанных регистрах, которые могут быть определены одним из двух способов. Одним из способов (как описано выше) он удерживает размер адресного пространства, и поэтому аппаратное обеспечение сначала проверяет виртуальный адрес по нему, прежде чем добавлять базу. Во втором случае он содержит физический адрес конца адресного пространства, и таким образом аппаратное обеспечение сначала добавляет базу, а затем удостоверяется, что адрес находится в пределах границ. Оба метода логически эквивалентны; для простоты мы обычно принимаем первый метод.
Пример трансляции адресов
Чтобы более подробно понять преобразование адресов с помощью base-and-bounds, давайте рассмотрим пример. Представьте себе, что процесс с адресным пространством размером 4 КБ (да, нереально маленьким) был загружен по физическому адресу 16 КБ. Вот результаты ряда переводов адресов:
Как вы можете видеть из примера, легко добавить базовый адрес к виртуальному адресу (который по праву можно рассматривать как смещение в адресное пространство), чтобы получить результирующий физический адрес. Только если виртуальный адрес "слишком большой" или отрицательный, результат будет ошибкой, вызывающей исключение.
Аппаратная поддержка: выводы
Давайте теперь подведем итоги поддержки, которая нам нужна от аппаратного обеспечения (см. Также рис.15.3). Во-первых, как обсуждалось в главе о виртуализации ЦП, нам требуются два различных режима ЦП. ОС работает в привилегированном режиме (или режиме ядра), где она имеет доступ ко всей машине; приложения работают в пользовательском режиме, где они ограничены в том, что они могут делать. Один бит, возможно, хранящийся в каком-то слове состояния процессора, указывает, в каком режиме в данный момент работает процессор; в определенных особых случаях (например, системный вызов или какое-либо другое исключение или прерывание) процессор переключает режимы.
Аппаратное обеспечение также должно обеспечивать сами base and bounds регистры; таким образом, каждый процессор имеет дополнительную пару регистров, часть блока управления памятью (MMU) процессора. Когда пользовательская программа запущена, аппаратное обеспечение преобразует каждый адрес, добавляя значение base к виртуальному адресу, сгенерированному пользовательской программой. Аппаратное обеспечение также должно быть в состоянии проверить, является ли адрес действительным, что достигается с помощью регистра bounds и некоторых схем внутри процессора.
Аппаратное обеспечение должно предоставлять специальные инструкции для изменения регистров base and bounds, позволяя ОС изменять их при запуске различных процессов. Эти инструкции являются привилегированными; только в режиме ядра (или привилегированном) регистры могут быть изменены. Представьте себе, какой хаос может вызвать пользовательский процесс, если он может произвольно изменять базовый регистр во время работы. Только представьте! А затем быстро выбросьте из головы такие мрачные мысли, потому что они являются тем ужасным материалом, из которого состоят кошмары.
СТРУКТУРА ДАННЫХ-СВОБОДНЫЙ СПИСОК
ОС должна отслеживать, какие части свободной памяти не используются, чтобы иметь возможность выделять память процессам. Конечно, для такой задачи можно использовать множество различных структур данных; самая простая (которую мы будем считать здесь) - это свободный список, который просто представляет собой список диапазонов физической памяти, которые в настоящее время не используются.
Наконец, ЦП должен иметь возможность генерировать исключения в ситуациях, когда пользовательская программа пытается незаконно получить доступ к памяти (с адресом, который является вышел за границы или out of bounds); в этом случае ЦП должен прекратить выполнение пользовательской программы и организовать запуск обработчика исключений ОС “out of bounds”. Затем обработчик ОС может выяснить, как реагировать, в этом случае, скорее всего, завершая процесс. Аналогично, если пользовательская программа пытается изменить значения (привилегированных) базовых и граничных регистров, ЦП должен вызвать исключение и запустить обработчик “tried to execute a privileged operation while in user mode”. Центральный процессор также должен предоставить метод, чтобы сообщить ему о местоположении этих обработчиков; таким образом, требуется еще несколько привилегированных инструкций.
Проблемы с операционной системой
Точно так же, как аппаратное обеспечение предоставляет новые функции для поддержки динамического перемещения, ОС теперь имеет новые проблемы, которые она должна решать; сочетание аппаратной поддержки и управления ОС приводит к реализации простой виртуальной памяти. В частности, есть несколько критических моментов, когда ОС должна участвовать в реализации нашей версии виртуальной памяти на основе base-and-bounds.
Во-первых, ОС должна принять меры при создании процесса, найдя место для своего адресного пространства в памяти. К счастью, учитывая наши предположения о том, что каждое адресное пространство (а) меньше размера физической памяти и (б) того же размера, это довольно легко для ОС; она может просто рассматривать физическую память как массив слотов и отслеживать, свободен ли каждый из них или используется. Когда создается новый процесс, ОС придется искать структуру данных (часто называемую свободным списком), чтобы найти место для нового адресного пространства, а затем отметить его использование. С адресными пространствами переменного размера жизнь сложнее, но мы оставим эту проблему для будущих глав.
Давайте рассмотрим пример. На рис. 15.2 видно, что ОС использует для себя первый слот физической памяти и что она переместила процесс из приведенного выше примера в слот, начинающийся с адреса физической памяти 32 КБ. Остальные два слота свободны (16 КБ-32 КБ и 48 КБ-64 КБ); таким образом, свободный список должен состоять из этих двух записей.
Во-вторых, ОС должна выполнять некоторую работу, когда процесс завершается (то есть когда он завершается изящно или насильственно убит из-за неправильного поведения), восстанавливая всю свою память для использования в других процессах или ОС. После завершения процесса ОС, таким образом, помещает свою память обратно в свободный список и очищает все связанные структуры данных по мере необходимости.
В-третьих, ОС также должна выполнить несколько дополнительных шагов при переключении контекста. В конце концов, на каждом процессоре есть только одна пара регистров base и bounds, и их значения различаются для каждой запущенной программы, поскольку каждая программа загружается по другому физическому адресу в памяти. Таким образом, ОС должна сохранять и восстанавливать пару base-and-bounds при переключении между процессами. В частности, когда ОС решает прекратить выполнение процесса, она должна сохранить значения base-and-bounds регистров в памяти в некоторых структурах процесса, таких как структура процесса или блок управления процессом (PCB). Аналогично, когда ОС возобновляет запущенный процесс (или запускает его в первый раз), она должна установить значения base-and-bounds на ЦП в правильные значения для этого процесса.
Следует отметить, что когда процесс остановлен (то есть не запущен), ОС может довольно легко перемещать адресное пространство из одного места в памяти в другое. Чтобы переместить адресное пространство процесса, ОС сначала исключает процесс из планировщика; затем ОС копирует адресное пространство из текущего местоположения в новое; наконец, ОС обновляет сохраненный базовый регистр (в структуре процесса), чтобы указать на новое местоположение. Когда процесс возобновляется, его (новый) базовый регистр восстанавливается, и он начинает работать снова, не обращая внимания на то, что его инструкции и данные теперь находятся в совершенно новом месте в памяти.
В-четвертых, ОС должна предоставлять обработчики исключений или вызываемые функции, как описано выше; ОС устанавливает эти обработчики во время загрузки (с помощью привилегированных инструкций). Например, если процесс пытается получить доступ к памяти за ее пределами, процессор вызовет исключение; ОС должна быть готова принять меры, когда такое исключение возникнет. Общей реакцией ОС будет враждебность: она, скорее всего, прекратит оскорбительный процесс. Операционная система должна быть очень защищена от машины, на которой она работает, и поэтому она не принимает любезно процесс, пытающийся получить доступ к памяти или выполнить инструкции, которые он не должен. До свидания, процесс плохого поведения; было приятно познакомиться.
Рис. 15.5 и 15.6 иллюстрируют большую часть взаимодействия оборудования и ОС на временной шкале. На первом рисунке показано, что ОС делает во время загрузки, чтобы подготовить машину к использованию, а на втором показано, что происходит, когда процесс (процесс А) начинает работать; обратите внимание, как его переводы памяти обрабатываются аппаратным обеспечением без вмешательства ОС. В какой-то момент (середина второго рисунка) происходит прерывание таймера, и ОС переключается на процесс B, который выполняет “плохую нагрузку” (на недопустимый адрес памяти); в этот момент ОС должна вмешаться, завершив процесс и очистив его, освободив память B и удалив его запись из таблицы процессов. Как вы можете видеть из рисунков, мы все еще придерживаемся базового подхода ограниченного прямого исполнения. В большинстве случаев ОС просто настраивает оборудование соответствующим образом и позволяет процессу работать непосредственно на процессоре; только когда процесс ведет себя неправильно, ОС должна быть вовлечена.
Резюме
В этой главе мы расширили понятие ограниченного прямого выполнения с помощью специального механизма, используемого в виртуальной памяти, известного как преобразование адресов. С помощью трансляции адресов ОС может контролировать каждый доступ к памяти из процесса, гарантируя, что доступы остаются в пределах адресного пространства. Ключом к эффективности этого метода является аппаратная поддержка, которая быстро выполняет перевод для каждого доступа, превращая виртуальные адреса (представление процесса памяти) в физические (фактическое представление). Все это выполняется таким образом, чтобы быть прозрачным для процесса, который был перемещен; процесс понятия не имеет, что его ссылки на память на самом деле ведут в память виртуальную, создавая прекрасную иллюзию.
Мы также видели одну конкретную форму виртуализации, известную как base and bounds или динамическое перемещение. Виртуализация Base-and-bounds довольно эффективна, так как требуется лишь немного больше аппаратной логики, чтобы добавить базовый регистр к виртуальному адресу и проверить, что адрес, сгенерированный процессом, находится в границах. Base and-bounds также обеспечивает защиту; ОС и аппаратное обеспечение объединяются, чтобы гарантировать, что ни один процесс не может генерировать ссылки на память вне своего собственного адресного пространства. Защита, безусловно, является одной из самых важных целей ОС; без него ОС не могла бы управлять машиной (если бы процессы были свободны для перезаписи памяти, они могли бы легко делать неприятные вещи, такие как перезапись trap table и захват системы).
К сожалению, этот простой метод динамического перемещения имеет свои недостатки. Например, как вы можете видеть на рис.15.2, перемещенный процесс использует физическую память от 32 до 48 КБ; однако, поскольку стек процессов и куча не слишком велики, все пространство между ними просто теряется. Этот тип отходов обычно называют внутренней фрагментацией, так как пространство внутри выделенной единицы используется не полностью (т. е. фрагментируется) и, таким образом, тратится впустую. В нашем нынешнем подходе, хотя физической памяти может быть достаточно для большего числа процессов, мы в настоящее время ограничены размещением адресного пространства в слоте фиксированного размера, и поэтому может возникнуть внутренняя фрагментация. Таким образом, нам понадобится более сложный механизм, чтобы попытаться лучше использовать физическую память и избежать внутренней фрагментации. Нашей первой попыткой будет небольшое обобщение базы и границ, известное как сегментация, которую мы обсудим далее.