Работа с памятью — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Куча)
(Куча)
 
Строка 21: Строка 21:
 
Для каждого <tex>malloc/new/new[]</tex> должны вызываться <tex>free/delete/delete[]</tex>, т.к. память сама не освобождается при выходе из функций. Не вызвав эти функции, куча останется неосвобожденнной, и произойдут утечки памяти.
 
Для каждого <tex>malloc/new/new[]</tex> должны вызываться <tex>free/delete/delete[]</tex>, т.к. память сама не освобождается при выходе из функций. Не вызвав эти функции, куча останется неосвобожденнной, и произойдут утечки памяти.
  
 
Рассмотрим процесс выделения памяти в куче на примере простой программы:
 
 
[[Файл:vmmap_before.png|right|thumb|200px|Память не выделена]]
 
[[Файл:vmmap_after.png||right|thumb|200px|Выделена память под массив]]
 
[[Файл:vmmap_delete.png||right|thumb|200px|Память освобождена]]
 
 
int main()
 
{
 
    int *a = new int [1000000];
 
    delete [] a;
 
    return 0;
 
}
 
 
До выполнения
 
int *a = new int [1000000];
 
куча в адресном пространстве программы занимает <tex>1152kB</tex>, а после выполнения команды - <tex>5060kB</tex>. Значит, память была выделена именно в куче, и объем выделенной памяти равен <tex>3908kB</tex>, что почти в точности соответствует объему массива <tex>int</tex> из <tex>1000000</tex> элементов при выделении <tex>4B</tex> на элемент.
 
 
После выполнения
 
delete [] a;
 
размер кучи снова равен <tex>1152kB</tex>, как и до выделение памяти под массив.
 
  
 
{{TODO| t=Переписать раздел про кучу подробнее и понятнее. Идея в том, чтобы сначала показать, что можно делать для эффективного распределения памяти, а потом обрадовать людей тем, что куча уже реализована.}}
 
{{TODO| t=Переписать раздел про кучу подробнее и понятнее. Идея в том, чтобы сначала показать, что можно делать для эффективного распределения памяти, а потом обрадовать людей тем, что куча уже реализована.}}

Текущая версия на 22:33, 23 июля 2011

Эта статья находится в разработке!

Физическая память[править]

Общие понятия[править]

Физическая (оперативная) память может быть представлена как массив байт. Процессор имеет возможность обращаться к данным из этого массива по индексу ячейки памяти (физическому адресу). В старых процессорах (например, i8086) каждый процесс использовал команды процессора для физической адресации к оперативной памяти, что, конечно, приводило к многочисленным ошибкам при неправильной (или злонамеренной) работе с памятью. Попытки разделить доступ разным процессам к физической памяти привели к появлению в i80286 процессорах защищенного режима (protected mode)[1]. В i80386 процессоре защищенный режим был расширен механизмом страничной адресации, которая по сей день является основным механизмом изоляции памяти процессов.

Работал этот механизм приблизительно так: каждый процесс мог обращаться к любой ячейке памяти из диапазона [0, 2^32 - 1] (такой диапазон называется виртуальным адресным пространством). Адресное пространство (виртуальное и физическое) условно делилось на блоки (страницы) по 4Кб, таким образом адрес ячейки (32-битное число) естественным образом можно было интерпретировать как пару (индекс страницы (20 бит), смещение в странице (12 бит)).
Страницы адресного пространства
Адрес разбивается на индекс страницы и смещение
Получив запрос на обращение к ячейке памяти (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 блоков содержался в специальной странице.
Таблица представляет собой двухуровневое дерево

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

Куча[править]

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

Память можно выделять и освобождать напрямую через системные функции [math]VirtualAlloc[/math] и [math]VirtualFree[/math]. Вызывая [math]VirtualAlloc[/math], указывая размер блока памяти и желаемый атрибут доступа (обычно: чтение-запись). Система выделяет от свободной памяти блок. Теперь в программе выделена память, и есть указатель на нее. Когда память надо освободить - вызывайте [math]VirtualFree[/math]. Система переведёт память обратно в свободную. Но как говорилось ранее с памятью нужно работать эффективно, поэтому существует куча, которая манипулирует страницами для эффективной работы с памятью. Хорошая новость заключается в том, что работа с кучей реализована на уровне ОС и вам можно не реализовывать ее самостоятельно.

В стандартной библиотеке, пришедшей из языка C, [math]libc[/math] реализованы функции [math]malloc()[/math] и [math]free()[/math], соответственно для выделения и освобождения памяти. В самом C++ есть аналогичные функции [math]new (new[])[/math] и [math]delete(delete[])[/math].

Для каждого [math]malloc/new/new[][/math] должны вызываться [math]free/delete/delete[][/math], т.к. память сама не освобождается при выходе из функций. Не вызвав эти функции, куча останется неосвобожденнной, и произойдут утечки памяти.


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

Аллокаторы[править]

TODO: Написать про аллокаторы


История[править]

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

Изначально, на самых первых компьютерах память для процессора представляла из себя просто массив байт. Например, для процессора i8086 размер этого массива был 2^20 байт (1МБ). Конечно, памяти в машине могло быть меньше. В этом случае запись в некоторые ячейки памяти игнорировалась. TODO: Уточнить, что происходит при чтении из несуществующей физической памяти (вероятно, читалась минус единица). Исполняемая программа могла читать или писать в любое место памяти. Из-за этого программа с ошибкой или вредоносная программа могли привести к некорректной работе всей системы.

Недостаток такого подхода к работе с памятью попытались исправить с помощью введения защищенного режима (protected mode) для i80286.[2] Защищенный режим позволял изолировать процессы друг от друга, чтобы один не мог испортить данные другого. Механизм изоляции процессов появившийся в 286, был не очень удобным и в настоящий момент практически не используется.

В настоящий момент времени для изоляции процессов используется механизм страничной адресации (paging[3]), введенный в i80386 процессоре.


TODO: Сейчас может сложиться впечатление, будто мы противопоставляем защищенный режим и страничную адресацию. Реально под термином защищенный режим понимаются две вещи: сегментная адресация (segmentation) и страничная адресация. 286 имел только сегментную адресацию. Сегментная адресация была неудобна и в настоящий момент практически не используется (кроме, например, Thread Information Block в винде[4]).


Адресное пространство

Определение[править]

Хранение в физической памяти
(серым выделена заполненная память)

При запуске программы операционная система создает процесс, которому выделяется адресное пространство размером [math]4GB[/math] в 32-битных системах, и [math]2^{64}B[/math] в 64-битных, представляющее из себя массив байт. В этом массиве можно писать и читать данные из любого его места. Ясно, что адресное пространство не может полностью содержаться в физической памяти, поэтому представим, что эта память просто дана каждому процессу, неважно, где она находится. Важно помнить, что у каждого процесса свое адресное пространство, которое не пересекается с адресными пространствами других программ. Адресное пространство существует, пока живёт процесс.

Старт процесса[править]

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

Хранение адресного пространства[править]

Хранение в физической памяти[править]

Адресное пространство разбито на страницы объемом по [math]4kB[/math]. Для каждой страницы в хранится ее адрес в физической памяти, либо указание, что эта страница пуста (в таком случае хранить саму страницу не надо - поэтому все адресные пространства помещаются в физической памяти). Физическая память формируется из оперативной памяти ([math]RAM[/math]), места на жестком диске, отведенного под [math]swap[/math], и места на жестком диске, где хранится непосредственно код программы и подгружаемых библиотек.

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

Обращение к адресному пространству[править]

При обращении к той или иной странице, если она не находится в оперативной памяти, она загружается туда. Для этого, либо в оперативке находится свободное место, либо выбирается страница, которая будет выгружена оттуда. Если эта страница уже существует на жестком диске, и не была изменена за время ее пребывания в оперативной памяти, она просто удаляется оттуда; иначе — записывается в [math]swap[/math].

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

Page fault[править]

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

Визуализация с помощью VMMap[править]

Окно программы VMMap

Для визуализации адресного пространства можно использовать программу VMMap. В главном окне на диаграмме можно видеть распределение физической памяти адресного пространство между самой программой, подключенными библиотеками, переменными и др. Как видно из скриншота, адресное пространство занимает в физической памяти много меньше, чем предоставленные ему [math]4GB[/math] (или [math]2^{64}B[/math] для 64-битных систем), то есть, оно не хранит пустые страницы. Именно поэтому даже на 64-битных системах возможно одновременно запускать несколько процессов, и не бояться того, что объем физической памяти сильно меньше [math]2^{64}B[/math].


Ссылки[править]