Мы в 1cloud стараемся рассказывать о различных технологиях — например, контейнерах, SSL или флеш-памяти.

Сегодня мы продолжим тему памяти. Разработчик Роберт Элдер (Robert Elder) в своем блоге опубликовал материал с описанием возможностей виртуальной памяти, которые известны не всем инженерам. Мы представляем вашему вниманию основные мысли этой заметки.

Примечание: Исходный материал содержит большое количество сложных терминов и технологических описаний, поэтому если вы обнаружили какую-то ошибку или неточность — напишите нам личным сообщением, чтобы мы могли внести правки и сделать материал лучше.

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

Прежде чем переходить к статье Элдера, можете посмотреть видео, на котором Джейсон Питт (Jason Pitt) рассказывает о том, что такое виртуальная память.

Как это работает

Элдер создал на своем сайте таблицу с физическим и виртуальным представлениями 256-байтного адресного пространства. Ниже представлен скриншот этой таблицы. Интерактивная версия доступна в блоге инженера по этой ссылке.



Обозначения, встречающиеся в интерактивной таблице Элдера:

0x0	Это указатель на страничную структуру верхнего уровня. На машинах Intel это значение хранится в регистре CR3. С ARM все немного сложнее.
	Первая страничная структура. При двухуровневой организации таблиц часто называется «директорией» страниц. В нашем случае каждая запись в директории занимает 8 бит (1 байт) и содержит информацию о месторасположении таблицы страниц.
	Вторая страничная структура – это так называемая таблица страниц (page table). Каждая запись содержит информацию о расположении физической страницы.
	Физическая страница, с которой в настоящий момент ведется работа.
	Активная запись директории страниц или таблицы страниц.
	Выбранное расположение в памяти.
	Память, доступная для чтения (Readable Memory). В данном примере разрешения не анализируются, однако в реальной системе будет осуществляться проверка бита на соответствие требуемому методу доступа.
	Память, доступная для записи (Writeable Memory).
	Память, для которой разрешено выполнение (Executable Memory).
	Недоступная виртуальная память (Inaccessible Virtual Memory).
	Неинициализированная физическая память (Unitialised Physical Memory). К ней нельзя обратиться через адресное пространство виртуальной памяти – это вызовет страничное нарушение.
	Недоступная физическая память (Inaccessible Physical Memory). Участки памяти, к которым нельзя получить доступ.

Отображение адресов «один в один» (Identity Mapping)

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

Рекурсивное отображение (Recursive Mapping)

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

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

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

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

Отображение на одну страницу (Everything Mapped to the Same Page)

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

Страничные нарушения (Page Faults Everywhere)

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

Переключение контекста между двумя процессами (Context Switching Between 2 Processes)

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

Решение проблемы внешней фрагментации (Solving External Fragmentation)

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

Из этой ситуации есть два выхода:

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

Первый вариант может вызывать снижение производительности, если копируемый кусок памяти будет очень большим (скажем, 1 ГБ). Однако это не все трудности: после перемещения значения нам придется каким-то образом сообщить процессу, которому был выдан этот участок памяти, что указатель изменился.

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

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

Копирование при записи (Copy-On-Write)

Виртуальная память крайне полезна для повышения производительности при выполнении команды fork. Если делать полные копии каждой страницы памяти, которую использует процесс, то это приведет к пустой трате циклов CPU и RAM. Идея копирования при записи состоит в том, что мы просто отображаем образ памяти родительского процесса в адресное пространство дочернего процесса.

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

Эксперимент со страницами

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

#include <stdio.h>

const char a            = 'a';
      char b            = 'b';
      char c(void){return 0;};
const char d            = 'd';
      char e            = 'e';
      char f(void){return 0;};

int main(){
        printf("a: %p, b: %p, c: %p, d: %p, e: %p, f: %p\n", (void *)&a, (void *)&b, (void *)&c, (void *)&d, (void *)&e, (void *)&f);
        return 0;
}

Вот, что он получил на выходе:

a: 0x400618, b: 0x601040, c: 0x40052d, d: 0x400619, e: 0x601041, f: 0x400538

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

Вызов функции с помощью констант

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

#include <stdio.h>

const unsigned int a = 0x12345678; /* Пока что просто плейсхолдеры */
const unsigned int b = 0x90123456;
const unsigned int c = 0x78901234;
const unsigned int d = 0x56789012;

unsigned int func1(unsigned int i){
        return i + 8;
}

int main(void){
        unsigned int * i;
        unsigned int num;
        /*  Print out the bytecode for 'func1' */
        for(i = (unsigned int*)func1; i < (unsigned int*)main; i++){
                printf("%p: 0x%08X\n", (void *)i, *i);
        }
        num = func1(29);
        printf("%u\n", num); /* Выводит 37*/
}

На выходе имеем:

0x40052d: 0xE5894855
0x400531: 0x8BFC7D89
0x400535: 0xC083FC45
0x400539: 0x55C35D08
37

Можно просто скопировать эти значения в целочисленные константы, которые будут расположены в памяти одна за другой (пример может не сработать, если ваша система отличается от системы Элдера). Теперь, поскольку они находятся на одной странице, можно обратиться к ним как к исполняемым данным и использовать вместо указателя на функцию указатель на «a».

#include <stdio.h>

const unsigned int a = 0xE5894855;  /*  Эти значения нужно скорректировать */
const unsigned int b = 0x8BFC7D89;  /*  в зависимости от  */
const unsigned int c = 0xC083FC45;  /*  вывода программы. */
const unsigned int d = 0x55C35D08;

unsigned int func1(unsigned int i){
        return i + 8;
}

int main(void){
        unsigned int * i;
        unsigned int num;
        /*  Print out the bytecode for 'func1' */
        for(i = (unsigned int*)func1; i < (unsigned int*)main; i++){
                printf("%p: 0x%08X\n", (void *)i, *i);
        }
        /*  Cast the address of 'a' to a function pointer and call it */
        num = ((unsigned int (*)(unsigned int))&a)(29);
        printf("%u\n", num); /* Выводит 37*/
}

На выходе по-прежнему имеем число 37.

Заключение

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