69
правок
Изменения
→Куча
[[Категория:С++ 2 семестр]]
{{В разработке}}
==Физическая память=====Общие понятия===
Физическая (оперативная) память может быть представлена как массив байт. Процессор имеет возможность обращаться к данным из этого массива по индексу ячейки памяти (физическому адресу). В старых процессорах (например, i8086) каждый процесс использовал команды процессора для физической адресации к оперативной памяти, что, конечно, приводило к многочисленным ошибкам при неправильной (или злонамеренной) работе с памятью. Попытки разделить доступ разным процессам к физической памяти привели к появлению в i80286 процессорах защищенного режима (''protected mode'')<ref>http://ru.wikipedia.org/wiki/Защищённый_режим</ref>. В i80386 процессоре защищенный режим был расширен механизмом страничной адресации, которая по сей день является основным механизмом изоляции памяти процессов.
Работал этот механизм приблизительно так: каждый процесс мог обращаться к любой ячейке памяти из диапазона [0, 2^32 - 1] (такой диапазон называется виртуальным адресным пространством). Адресное пространство (виртуальное и физическое) условно делилось на блоки (страницы) по 4Кб, таким образом адрес ячейки (32-битное число) естественным образом можно было интерпретировать как пару (индекс страницы (20 бит), смещение в странице (12 бит)). [[Файл:IMAG0047.jpg|right|thumb|200px|<center>Страницы адресного пространства</center>]] [[Файл:IMAG0048.jpg|right|thumb|200px|<center>Адрес разбивается на индекс страницы и смещение</center>]] Получив запрос на обращение к ячейке памяти (p, o), процессор обращался к уникальной для каждого процесса таблице (в первом приближении ее можно считать массивом из 2^20 32-битных чисел) по индексу страницы p. В этой таблице для всех страниц виртуального адресного пространства процесса прописывались индексы страниц физической памяти (20-битное число) и некоторая служебная информация (12-битное число: флаг доступности страницы в физической памяти (present flag), флаг возможности записи (write flag), флаг изменения страницы (dirty flag) и т.д.). В случае, если страница обнаруживалась в физической памяти, процессор вычислял физический адрес искомой ячейки, взяв ее смещение относительно начала страницы. В случае же если искомой странице не соответствовала страница в физической памяти, процессор бросал исключение page fault, которое перехватывала операционная система.
Конечно, 4Мб на каждый процесс -- непозволительная трата ресурсов, поэтому вместо массива использовалось двухуровневое дерево. Массив из 2^20 элементов условно делился на 2^10 блока по 2^10 записей. Если блок полностью состоял из отсутствующих в физической памяти страниц, страницы, содержащей его, не было. Список из 2^10 блоков содержался в специальной странице.[[Файл:IMAG0049.jpg|right|thumb|200px|<center>Таблица представляет собой двухуровневое дерево</center>]] Примерно так работает страничная адресация и в современных процессорах. Как же заполняется таблица виртуального адресного пространства? Операционная система позволяет с помощью своего API резервировать и освобождать страницы в виртуальном адресном пространстве и сопоставлять этим страницам физическую память. Конечно, если все процессы начнут забирать физическую память, рано или поздно система не сможет найти свободную страницу в физической памяти. В этом случае она начнет использовать файл подкачки (или раздел жесткого диска, как в linux). В первом приближении этот механизм работает так: ОС выбирает страницу, которую давно не использовали и, если она была модифицирована (установлен флаг dirty) или если ее образа нет в файле подкачки, сохраняет страницу в файле подкачки. Далее ОС модифицирует записи в таблицах виртуальных адресных пространств процессов, использовавших эту страницу, сбрасывая флаг present. На место этой страницы помещается страница из файла подкачки (если процесс хотел обратиться к странице, которую уже когда-то использовал) или она просто заполняется нулями. Страницы могут подгружаться не только из файла подкачки -- в адресное пространство загружается код процесса и код всех его зависимостей. В адресное пространство может быть спроецирован файл с жесткого диска. В этих случаях страницы могут загружаться из соотвествующих файлов. ===Куча=== Рассмотрим теперь пример использования памяти: попробуем представить себе как можно реализовать динамически расширяющийся массив (вектор). Нас будет интересовать операция расширения массива: предположим, массив уже занимает какую-то непрерывную область виртуального адресного пространства (под его данные было выделено несколько страниц виртуального адресного пространства). Мы хотим расширить этот массив, увеличив его размер вдвое, скопировать в новый массив старые данные. После чего старый массив нам становится не нужен. Тут возникают два вопроса: какие страницы резервировать и что делать со старыми страницами. Заметим, что резервирование новых страниц и сопоставление им физической памяти -- дорогое удовольствие. Понятно, что у нас может возникнуть необходимость выделить еще какие-то данные и старые выделенные страницы памяти могут нам пригодиться -- используя их мы сможем записать новые данные, не выделяя новые страницы. Также заметим, что нам нужно бережнее относиться к остаткам страницы (когда мы записываем данные, занимающие страницу не полностью) -- нужно помнить про свободные куски используемых страниц. Память можно выделять и освобождать напрямую через системные функции <tex>VirtualAlloc</tex> и <tex>VirtualFree</tex>. Вызывая <tex>VirtualAlloc</tex>, указывая размер блока памяти и желаемый атрибут доступа (обычно: чтение-запись). Система выделяет от свободной памяти блок. Теперь в программе выделена память, и есть указатель на нее. Когда память надо освободить - вызывайте <tex>VirtualFree</tex>. Система переведёт память обратно в свободную. Но как говорилось ранее с памятью нужно работать эффективно, поэтому существует куча, которая манипулирует страницами для эффективной работы с памятью. Хорошая новость заключается в том, что работа с кучей реализована на уровне ОС и вам можно не реализовывать ее самостоятельно. В стандартной библиотеке, пришедшей из языка C, <tex>libc</tex> реализованы функции <tex>malloc()</tex> и <tex>free()</tex>, соответственно для выделения и освобождения памяти. В самом C++ есть аналогичные функции <tex>new (new[])</tex> и <tex>delete(delete[])</tex>. Для каждого <tex>malloc/new/new[]</tex> должны вызываться <tex>free/delete/delete[]</tex>, т.к. память сама не освобождается при выходе из функций. Не вызвав эти функции, куча останется неосвобожденнной, и произойдут утечки памяти. {{TODO| t=Переписать раздел про кучу подробнее и понятнее. Идея в том, чтобы сначала показать, что можно делать для эффективного распределения памяти, а потом обрадовать людей тем, что куча уже реализована.}} ===Аллокаторы=== {{TODO| t=Написать про аллокаторы}}
== История ==
