код для выделения памяти
Разбираемся с управлением памятью в современных языках программирования
Привет, Хабр! Представляю вашему вниманию перевод статьи «Demystifying memory management in modern programming languages» за авторством Deepu K Sasidharan.
В данной серии статей мне бы хотелось развеять завесу мистики над управлением памятью в программном обеспечении (далее по тексту — ПО) и подробно рассмотреть возможности, предоставляемые современными языками программирования. Надеюсь, что мои статьи помогут читателю заглянуть под капот этих языков и узнать для себя нечто новое.
Углублённое изучение концептов управления памятью позволяет писать более эффективное ПО, потому как стиль и практики кодирования оказывают большое влияние на принципы выделения памяти для нужд программы.
Часть 1: Введение в управление памятью
Управление памятью — это целый набор механизмов, которые позволяют контролировать доступ программы к оперативной памяти компьютера. Данная тема является очень важной при разработке ПО и, при этом, вызывает затруднения или же вовсе остаётся черным ящиком для многих программистов.
Для чего используется оперативная память?
Когда программа выполняется в операционный системе компьютера, она нуждается в доступе к оперативной памяти (RAM) для того, чтобы:
Стек используется для статичного выделения памяти. Он организован по принципу «последним пришёл — первым вышел» (LIFO). Можно представить стек как стопку книг — разрешено взаимодействовать только с самой верхней книгой: прочитать её или положить на неё новую.
Использование стека в JavaScript. Объекты хранятся в куче и доступны по ссылкам, которые хранятся в стеке. Тут можно посмотреть в видеоформате
Куча используется для динамического выделения памяти, однако, в отличие от стека, данные в куче первым делом требуется найти с помощью «оглавления». Можно представить, что куча это такая большая многоуровневая библиотека, в которой, следуя определённым инструкциям, можно найти необходимую книгу.
Почему эффективное управление памятью важно?
В отличие от жёстких дисков, оперативная память весьма ограниченна (хотя и жёсткие диски, безусловно, тоже не безграничны). Если программа потребляет память не высвобождая её, то, в конечном итоге, она поглотит все доступные резервы и попытается выйти за пределы памяти. Тогда она просто упадет сама, или, что ещё драматичнее, обрушит операционную систему. Следовательно, весьма нежелательно относиться легкомысленно к манипуляциям с памятью при разработке ПО.
Различные подходы
Современные языки программирования стараются максимально упростить работу с памятью и снять с разработчиков часть головной боли. И хотя некоторые почтенные языки всё ещё требуют ручного управления, большинство всё же предоставляет более изящные автоматические подходы. Порой в языке используется сразу несколько подходов к управлению памятью, а иногда разработчику даже доступен выбор какой из вариантов будет эффективнее конкретно для его задач (хороший пример — C++). Перейдём к краткому обзору различных подходов.
Ручное управление памятью
Язык не предоставляет механизмов для автоматического управления памятью. Выделение и освобождение памяти для создаваемых объектов остаётся полностью на совести разработчика. Пример такого языка — C. Он предоставляет ряд методов (malloc, realloc, calloc и free) для управления памятью — разработчик должен использовать их для выделения и освобождения памяти в своей программе. Этот подход требует большой аккуратности и внимательности. Так же он является в особенности сложным для новичков.
Сборщик мусора
Сборка мусора — это процесс автоматического управления памятью в куче, который заключается в поиске неиспользующихся участков памяти, которые ранее были заняты под нужды программы. Это один из наиболее популярных вариантов механизма для управления памятью в современных языках программирования. Подпрограмма сборки мусора обычно запускается в заранее определённые интервалы времени и бывает, что её запуск совпадает с ресурсозатратными процессами, в результате чего происходит задержка в работе приложения. JVM (Java/Scala/Groovy/Kotlin), JavaScript, Python, C#, Golang, OCaml и Ruby — вот примеры популярных языков, в которых используется сборщик мусора.
Получение ресурса есть инициализация (RAII)
RAII — это программная идиома в ООП, смысл которой заключается в том, что выделяемая для объекта область памяти строго привязывается к его времени существования. Память выделяется в конструкторе и освобождается в деструкторе. Данный подход был впервые реализован в C++, а так же используется в Ada и Rust.
Автоматический подсчёт ссылок (ARC)
Данный подход весьма похож на сборку мусора с подсчётом ссылок, однако, вместо запуска процесса подсчёта в определённые интервалы времени, инструкции выделения и освобождения памяти вставляются на этапе компиляции прямо в байт-код. Когда же счётчик ссылок достигает нуля, память освобождается как часть нормального потока выполнения программы.
Автоматический подсчёт ссылок всё так же не позволяет обрабатывать циклические ссылки и требует от разработчика использования специальных ключевых слов для дополнительной обработки таких ситуаций. ARC является одной из особенностей транслятора Clang, поэтому присутствует в языках Objective-C и Swift. Так же автоматический подсчет ссылок доступен для использования в Rust и новых стандартах C++ при помощи умных указателей.
Владение
Это сочетание RAII с концепцией владения, когда каждое значение в памяти должно иметь только одну переменную-владельца. Когда владелец уходит из области выполнения, память сразу же освобождается. Можно сказать, что это примерно как подсчёт ссылок на этапе компиляции. Данный подход используется в Rust и при этом я не смог найти ни одного другого языка, который бы использовал подобный механизм.
В данной статье были рассмотрены основные концепции в сфере управления памятью. Каждый язык программирования использует собственные реализации этих подходов и оптимизированные для различных задач алгоритмы. В следующих частях, мы подробнее рассмотрим решения для управления памятью в популярных языках.
Читайте так же другие части серии:
Ссылки
Вы можете подписаться на автора статьи в Twitter и на LinkedIn.
Механизмы выделения памяти в Go
Когда я впервые попытался понять то, как работают средства выделения памяти в Go, то, с чем я хотел разобраться, показалось мне таинственным чёрным ящиком. Как и в случае с любыми другими технологиями, самое важное здесь скрывается за множеством слоёв абстракций, сквозь которые нужно пробраться для того, чтобы что-то понять.
Автор материала, перевод которого мы публикуем, решил добраться до сути средств выделения памяти в Go и рассказать об этом.
Физическая и виртуальная память
Всем средствам для выделения памяти приходится работать с адресным пространством виртуальной памяти, которым управляет операционная система. Давайте посмотрим на то, как работает память, начав с самого низкого уровня — с ячеек памяти.
Вот как можно представить ячейку оперативной памяти.
Схема ячейки памяти
Если, очень упрощённо, представить себе ячейку оперативной памяти и то, что её окружает, то у нас получится следующее:
Схема взаимодействия физической памяти и процессора
Шина данных ответственна за транспортировку данных между процессором и физической памятью.
Теперь поговорим о линии адреса и об адресуемых байтах.
Линии шины адреса между процессором и физической памятью
Адреса байтов в виртуальном адресном пространстве не соответствуют тем адресам, которые процессор использует для обращения к физической памяти. В результате нужна система, позволяющая преобразовывать виртуальные адреса в физические. Взглянем на то, как выглядят виртуальные адреса памяти.
Представление виртуального адресного пространства
В итоге, когда процессор выполняет инструкцию, которая ссылается на адрес памяти, первым шагом является перевод логического адреса в линейный адрес. Это преобразование выполняется блоком управления памятью.
Упрощённое представление взаимосвязи виртуальной и физической памяти
Так как логические адреса слишком велики для того, чтобы удобно было бы работать с ними по отдельности (это зависит от различных факторов), память организуется в структуры, называемые страницами. При этом виртуальное адресное пространство делится на небольшие области, страницы, которые в большинстве ОС имеют размер 4 Кб, хотя обычно этот размер можно изменить. Это — наименьшая единица управления памятью в виртуальной памяти. Виртуальная память ничего не хранит, она просто задаёт соответствие между адресным пространством программы и физической памятью.
Процессы видят лишь адреса виртуальной памяти. Что происходит, если программе нужно больше динамической памяти (такую память ещё называют heap memory, или «кучей»)? Вот пример простого кода на ассемблере, в котором у системы запрашивается дополнительная динамически распределяемая память:
Вот как это можно представить в виде схемы.
Увеличение динамически распределяемой памяти
Программа запрашивает дополнительную память, пользуясь системным вызовом brk (sbrk / mmap и так далее). Ядро обновляет сведения о виртуальной памяти, но при этом в физической памяти новые страницы пока не представлены, и здесь наблюдается отличие между виртуальной и физической памятью.
Средство выделения памяти
После того, как мы, в общих чертах, обсудили работу с виртуальным адресным пространством, поговорили о том, как выполняется запрос дополнительной динамической памяти (памяти в куче), нам легче будет говорить о средствах для выделения памяти.
Демонстрация внешней фрагментации
На предыдущей схеме, на шаге p4, у нас нет достаточного количества последовательно расположенных блоков памяти для выполнения запроса на выделение шести таких блоков, хотя общий объём свободной памяти сделать это позволяет. Такая ситуация приводит к фрагментации памяти.
Как уменьшить фрагментацию памяти? Ответ на этот вопрос зависит от конкретного алгоритма выделения памяти, от того, какая базовая библиотека используется для работы с памятью.
Сейчас мы рассмотрим средство для выделения памяти TCMalloc, на котором основаны механизмы выделения памяти Go.
TCMalloc
В основе TCMalloc лежит идея разделения памяти на несколько уровней ради уменьшения фрагментации памяти. Внутри TCMalloc управление памятью делится на две части: работа с памятью потоков и работа с кучей.
▍Память потоков
Каждая страница памяти разбивается на последовательность фрагментов определённых размеров, выбираемых в соответствии с классами размеров. Это позволяет уменьшить фрагментацию. В результате в распоряжении каждого потока оказывается кэш для маленьких объектов, который позволяет очень эффективно выделять память под объекты, размер которых меньше или равен 32 Кб.
Куча, управляемая TCMalloc, представляет собой коллекцию страниц, в которой набор последовательных страниц может быть представлен в виде диапазона страниц (span). Когда нужно выделить память под объект, размер которого превышает 32 Кб, для выделения памяти используется куча.
Куча и работа со страницами
Когда для размещения в памяти маленьких объектов места не хватает, за памятью обращаются к куче. Если и в куче недостаточно свободной памяти — дополнительная память запрашивается у операционной системы.
В результате представленная модель работы с памятью поддерживает пул памяти пользовательского пространства, её применение значительно улучшает эффективность выделения и освобождения памяти.
Надо отметить, что средство выделения памяти Go изначально было основано на TCMalloc, но оно немного от него отличается.
Средство выделения памяти Go
Мы знаем, что среда выполнения Go планирует выполнение горутин на логических процессорах. Подобно этому, версия TCMalloc, используемая в Go, делит страницы памяти на блоки, размеры которых соответствуют определённым классам размеров, которых существует 67.
Если вы не знакомы с планировщиком Go — здесь можно о нём почитать.
Классы размеров в Go
Так как минимальным размером страницы в Go является 8192 байта (8 Кб), если такую страницу разделить на блоки, размером 1 Кб, то мы получим 8 таких блоков.
Страница размером 8 Кб разделена на блоки, соответствующие классу размера 1 Кб
Подобными последовательностям страниц в Go управляют с использованием структуры, называемой mspan.
▍Структура mspan
Структура mspan представляет собой двусвязный список, объект, который содержит начальный адрес страницы, сведения о размере страницы и количество страниц, входящих в него.
▍Структура mcache
Как и TCMalloc, Go предоставляет каждому логическому процессору локальный кэш для потоков, известный как mcache. В результате, если горутина нуждается в памяти, она может получить её непосредственно из mcache. Для этого не нужно выполнять блокировки, так как в любой момент времени на одном логическом процессоре выполняется лишь одна горутина.
Структура mcache содержит, в виде кэша, структуры mspan различных классов размера.
Взаимодействие между логическим процессором, mcache и mspan в Go
Так как у каждого логического процессора есть собственный mcache, при выделении памяти из mcache нет необходимости в блокировках.
Каждый класс размера может быть представлен одним из следующих объектов:
Что же попадает в mcache? Объекты, размер которых не превышает 32 Кб, попадают прямо в mcache с использованием mspan соответствующего класса размера.
Что происходит в том случае, если в mcache нет свободной ячейки? Тогда получают новый mspan нужного класса размера из списка объектов mspan, который называется mcentral.
▍Структура mcentral
Структура mcentral собирает все диапазоны страниц определённого класса размера. Каждый объект mcentral содержит два списка объектов mspan.
Каждая структура mcentral существует внутри структуры mheap.
▍Структура mheap
Структура mheap представлена объектом, который занимается в Go управлением кучей. Существует всего один такой глобальный объект, владеющий виртуальным адресным пространством.
Как видно из вышеприведённой схемы, структура mheap содержит массив структур mcentral. Этот массив содержит структуры mcentral для всех классов размеров.
Так как у нас есть структура mcentral для каждого класса размера, когда mcache запрашивает структуру mspan из mcentral, на индивидуальном уровне mcentral применяется блокировка, в результате одновременно могут быть обслужены и запросы от других mcache, запрашивающих структуры mspan других размеров.
Что происходит в том случае, если список mcentral пуст? Тогда mcentral получает последовательность страниц из mheap для выделения фрагментов памяти требуемого класса размера.
Процесс выделения памяти под объекты
Память, запрашиваемая в куче, выделяется из арены. Рассмотрим этот механизм.
Виртуальная память Go
Взглянем на использование памяти простой программой, написанной на Go:
Сведения о процессе программы
Виртуальное адресное пространство даже такой простой программы составляет примерно 100 МБ, в то время как показатель RSS равняется всего 696 Кб. Для начала попытаемся выяснить причину такого расхождения.
Данные по map и smap
Тут можно видеть области памяти, размер которых примерно равен 2 МБ, 64 МБ, 32 МБ. Что это за память?
▍Арены
Оказывается, что виртуальная память в Go состоит из набора арен. Исходный размер памяти, предназначенный для кучи, соответствует одной арене, то есть — 64 МБ (это актуально для Go 1.11.5).
Текущий размер арены в различных системах
В результате память, необходимая для текущих нужд программы, выделяется небольшими порциями. Этот процесс начинается с одной арены размером 64 МБ.
Те числовые показатели, о которых мы тут говорим, не стоит принимать за некие абсолютные и неизменные значения. Они могут меняться. Раньше, например, Go резервировал непрерывное виртуальное пространство заранее, на 64-битных системах размер арены составлял 512 ГБ (тут интересно подумать о том, что произойдёт, если реальная потребность в памяти окажется настолько большой, что соответствующий запрос будет отвергнут mmap?).
Собственно говоря, кучей мы называем набор арен. В Go арены воспринимаются как фрагменты памяти, разделённые на блоки размером 8192 байта (8 Кб).
Одна арена размером 64 МБ
В Go есть ещё пара разновидностей блоков — span и bitmap. Память под них выделяется за пределами кучи, они хранят метаданные арен. Они, в основном, используются при сборке мусора.
Вот общая схема работы механизмов выделения памяти в Go.
Общая схема механизмов выделения памяти в Go
Итоги
В целом можно отметить, что в этом материале мы описали подсистемы работы с памятью Go в весьма общих чертах. Основной идеей работы подсистемы памяти в Go является выделение памяти с использованием различных структур и кэшей разных уровней. При этом учитывается размер объектов, для которых выделяется память.
Представление единого блока непрерывных адресов памяти, получаемого от операционной системы, в виде многоуровневой структуры, повышает эффективность работы механизма выделения памяти за счёт того, что такой подход позволяет избежать блокировок. Выделение ресурсов с учётом размеров объектов, которые нужно хранить в памяти, позволяет уменьшить фрагментацию, и, после освобождения памяти, позволяет ускорить сборку мусора.
Уважаемые читатели! Сталкивались ли вы с проблемами, вызванными неправильной работой с памятью в программах, написанных на Go?
Динамическое выделение памяти
malloc
В предыдущей главе уже обсуждалось, что локальные переменные кладутся на стек и существую до тех пор, пока мы не вышли из функции. С одной стороны, это позволяет автоматически очищать память, с другой стороны, существует необходимость в переменных, время жизни которых мы можем контролировать самостоятельно. Кроме того, нам необходимо динамическое выделение памяти, когда размер используемого пространства заранее не известен. Для этого используется выделение памяти на куче. Недостатков у такого подхода два: во-первых, память необходимо вручную очищать, во-вторых, выдеение памяти – достаточно дорогостоящая операция.
Для выделения памяти на куче в си используется функция malloc (memory allocation) из библиотеки stdlib.h
Функция выделяет size байтов памяти и возвращает указатель на неё. Если память выделить не удалось, то функция возвращает NULL. Так как malloc возвращает указатель типа void, то его необходимо явно приводить к нужному нам типу. Например, создадим указатель, после этого выделим память размером в 100 байт.
После того, как мы поработали с памятью, необходимо освободить память функцией free.
Используя указатель, можно работать с выделенной памятью как с массивом. Пример: пользователь вводит число – размер массива, создаём массив этого размера и заполняем его квадратами чисел по порядку. После этого выводим и удаляем массив.
Здесь (int *) – приведение типов. Пишем такой же тип, как и у указателя.
size * sizeof(int) – сколько байт выделить. sizeof(int) – размер одного элемента массива.
После этого работаем с указателем точно также, как и с массивом. В конце не забываем удалять выделенную память.
Теперь представим на рисунке, что у нас происходило. Пусть мы ввели число 5.
Функция malloc выделила память на куче по определённому адресу, после чего вернула его. Теперь указатель p хранит этот адрес и может им пользоваться для работы. В принципе, он может пользоваться и любым другим адресом.
Когда функция malloc «выделяет память», то она резервирует место на куче и возвращает адрес этого участка. У нас будет гарантия, что компьютер не отдаст нашу память кому-то ещё. Когда мы вызываем функцию free, то мы освобождаем память, то есть говорим компьютеру, что эта память может быть использована кем-то другим. Он может использовать нашу память, а может и нет, но теперь у нас уже нет гарантии, что эта память наша. При этом сама переменная не зануляется, она продолжает хранить адрес, которым ранее пользовалась.
Это очень похоже на съём номера в отеле. Мы получаем дубликат ключа от номера, живём в нём, а потом сдаём комнату обратно. Но дубликат ключа у нас остаётся. Всегда можно зайти в этот номер, но в нём уже кто-то может жить. Так что наша обязанность – удалить дубликат.
Иногда думают, что происходит «создание» или «удаление» памяти. На самом деле происходит только перераспределение ресурсов.
Освобождение памяти с помощью free
Т еперь рассмотри, как происходит освобождение памяти. Переменная указатель хранит адрес области памяти, начиная с которого она может им пользоваться. Однако, она не хранит размера этой области. Откуда тогда функция free знает, сколько памяти необходимо освободить?
Работа с двумерными и многомерными массивами
Создадим «треугольный» массив и заполним его значениями
Чтобы создать трёхмерный массив, по аналогии, необходимо сначала определить указатель на указатель на указатель, после чего выделить память под массив указателей на указатель, после чего проинициализировать каждый из массивов и т.д.
calloc
Ф ункция calloc выделяет n объектов размером m и заполняет их нулями. Обычно она используется для выделения памяти под массивы. Синтаксис
realloc
Е щё одна важная функция – realloc (re-allocation). Она позволяет изменить размер ранее выделенной памяти и получает в качестве аргументов старый указатель и новый размер памяти в байтах:
Функция realloc может как использовать ранее выделенный участок памяти, так и новый. При этом не важно, меньше или больше новый размер – менеджер памяти сам решает, где выделять память.
Пример – пользователь вводит слова. Для начала выделяем под слова массив размером 10. Если пользователь ввёл больше слов, то изменяем его размер, чтобы хватило места. Когда пользователь вводит слово end, прекращаем ввод и выводим на печать все слова.
Хочу обратить внимание, что мы при выделении памяти пишем sizeof(char*), потому что размер указателя на char не равен одному байту, как размер переменной типа char.
Ошибки при выделении памяти
1. Бывает ситуация, при которой память не может быть выделена. В этом случае функция malloc (и calloc) возвращает NULL. Поэтому, перед выделением памяти необходимо обнулить указатель, а после выделения проверить, не равен ли он NULL. Так же ведёт себя и realloc. Когда мы используем функцию free проверять на NULL нет необходимости, так как согласно документации free(NULL) не производит никаких действий. Применительно к последнему примеру:
Хотелось бы добавить, что ошибки выделения памяти могут случиться, и просто выходить из приложения и выкидывать ошибку плохо. Решение зависит от ситуации. Например, если не хватает памяти, то можно подождать некоторое время и после этого опять попытаться выделить память, или использовать для временного хранения файл и переместить туда часть объектов. Или выполнить очистку, сократив используемую память и удалив ненужные объекты.
Таким образом, если указатель хранит адрес, то его не нужно изменять. Для работы лучше создать дополнительную переменную указатель, с которой работать дальше.
3. Использование освобождённой области. Почему это работает в си, описано выше. Эта ошибка выливается в другую – так называемые висячие указатели (dangling pointers или wild pointers). Вы удаляете объект, но при этом забываете изменить значение указателя на NULL. В итоге, он хранит адрес области памяти, которой уже нельзя воспользоваться, при этом проверить, валидная эта область или нет, у нас нет возможности.
Эта программа отработает и выведет мусор, или не мусор, или не выведет. Поведение не определено.
Если же мы напишем
то программа выкинет исключение. Это определённо лучше, чем неопределённое поведение. Если вы освобождаете память и используете указатель в дальнейшем, то обязательно обнулите его.
4. Освобождение освобождённой памяти. Пример
5. Одновременная работа с двумя указателями на одну область памяти. Пусть, например, у нас два указателя p1 и p2. Если под первый указатель была выделена память, то второй указатель может запросто скомпрометировать эту область:
Рассмотрим код ещё раз.
Теперь оба указателя хранят один адрес.
А вот здесь происходит непредвиденное. Мы решили выделить под p2 новый участок памяти. realloc гарантирует сохранение контента, но вот сам указатель p1 может перестать быть валидным. Есть разные ситуации. Во-первых, вызов malloc мог выделить много памяти, часть которой не используется. После вызова ничего не поменяется и p1 продолжит оставаться валидным. Если же потребовалось перемещение объекта, то p1 может указывать на невалидный адрес (именно это с большой вероятностью и произойдёт в нашем случае). Тогда p1 выведет мусор (или же произойдёт ошибка, если p1 полезет в недоступную память), в то время как p2 выведет старое содержимое p1. В этом случае поведение не определено.
Два указателя на одну область памяти это вообще-то не ошибка. Бывают ситуации, когда без них не обойтись. Но это очередное минное поле для программиста.
Различные аргументы realloc и malloc.
При вызове функции malloc, realloc и calloc с нулевым размером поведение не определено. Это значит, что может быть возвращён как NULL, так и реальный адрес. Им можно пользоваться, но к нему нельзя применять операцию разадресации.
Вызов realloc(NULL, size_t) эквиваленте вызову malloc(size_t).
Однако, вызов realloc(NULL, 0) не эквивалентен вызову malloc(0) 🙂 Понимайте это, как хотите.
Примеры
Пусть есть ряд
1, 4, 4, 6, 7, 8, 9, 11, 12, 11, 15
Тогда если период среднего будет 3, то мы получим ряд
(1+4+4)/3, (4+4+6)/3, (4+6+7)/3, (6+7+8)/3, (7+8+9)/3, (8+9+11)/3, (9+11+12)/3, (11+12+11)/3, (12+11+15)/3
Видно, что сумма находится в «окне», которое скользит по ряду. Вместо того, чтобы каждый раз в цикле находить сумму, можно найти её для первого периода, а затем вычитать из суммы крайнее левое значение предыдущего периода и прибавлять крайнее правое значение следующего.
Будем запрашивать у пользователя числа и период, а затем создадим новый массив и заполним его средними значениями.
Это простой пример. Большая его часть связана со считыванием данных, вычисление среднего всего в девяти строчках.
3. Бином Ньютона. Создадим треугольную матрицу и заполним биномиальными коэффициентами
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике