Лекция
Привет, Вы узнаете о том , что такое сборка мусора, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сборка мусора, утечка памяти, достижимость объекта, сбор циклических ссылок , настоятельно рекомендую прочитать все из категории Языки и методы программирования. Теория трансляции.
сборка мусора (англ. garbage collection) в программировании — одна из форм автоматического управления памятью. Специальный процесс, называемый сборщиком мусора (англ. garbage collector), периодически освобождает память, удаляя объекты, которые уже не будут востребованы приложениями.
В компьютерном программировании , отслеживание сборки мусора является одной из форм автоматического управления памятью , которая состоит из определения того, какие объекты должны быть высвобождены ( «сборка мусора») путем отслеживания , какие объекты достижимы цепочкой ссылок из определенных «корня» объектов, и принимая во внимании отдыхают как "мусор" и собирают их. Сборка мусора с отслеживанием является наиболее распространенным типом сборки мусора - настолько, что «сборка мусора» часто относится к отслеживанию сборки мусора, а не к другим методам, таким как подсчет ссылок, - и при реализации используется большое количество алгоритмов.
Сборка мусора была впервые применена Джоном Маккарти в 1959 году в среде программирования на разработанном им функциональном языке программирования Лисп. Впоследствии она применялась в других системах программирования и языках, преимущественно — в функциональных и логических. Необходимость сборки мусора в языках этих типов обусловлена тем, что структура таких языков делает крайне неудобным отслеживание времени жизни объектов в памяти и ручное управление ею. Широко используемые в этих языках списки и основанные на них сложные структуры данных во время работы программ постоянно создаются, надстраиваются, расширяются, копируются, и правильно определить момент удаления того или иного объекта затруднительно.
В промышленных процедурных и объектных языках сборка мусора долго не использовалась. Предпочтение отдавалось ручному управлению памятью, как более эффективному и предсказуемому. Но со второй половины 1980-х годов технология сборки мусора стала использоваться и в директивных (императивных), и в объектных языках программирования, а со второй половины 1990-х годов все большее число создаваемых языков и сред, ориентированных на прикладное программирование, включают механизм сборки мусора либо как единственный, либо как один из доступных механизмов управления динамической памятью. В настоящее время она используется в Оберон, Java, Python, Ruby, C#, D, F#, Go и других языках.
Традиционным для директивных языков способом управления памятью является ручной. Его сущность в следующем:
В любом языке, допускающем создание объектов в динамической памяти, потенциально возможны две проблемы: висячие ссылки и утечки памяти.
Висячая ссылка (англ. dangling pointer) — это ссылка на объект, который уже удален из памяти. После удаления объекта все сохранившиеся в программе ссылки на него становятся «висячими». Память, занимаемая ранее объектом, может быть передана операционной системе и стать недоступной, или быть использована для размещения нового объекта в той же программе. В первом случае попытка обратиться по «повисшей» ссылке приведет к срабатыванию механизма защиты памяти и аварийной остановке программы, а во втором — к непредсказуемым последствиям.
Появление висячих ссылок обычно становится следствием неправильной оценки времени жизни объекта: программист вызывает команду удаления объекта до того, как его использование прекратится.
Создав объект в динамической памяти, программист может не удалить его после завершения использования. Если ссылающейся на объект переменной будет присвоено новое значение и на объект нет других ссылок, он становится программно недоступным, но продолжает занимать память, поскольку команда его удаления не вызывалась. Такая ситуация и называется утечкой памяти (англ. memory leak).
Если объекты, ссылки на которые теряются, создаются в программе постоянно, то утечка памяти проявляется в постепенном увеличении объема используемой памяти; если программа работает долго, объем используемой ею памяти постоянно растет, и через какое-то время ощутимо замедляется работа системы (из-за необходимости при любом выделении памяти использовать свопинг), либо программа исчерпывает доступный объем адресного пространства и завершается с ошибкой.
Неформально объект становится достижимым, если на него ссылается хотя бы одна переменная в программе, либо напрямую, либо через ссылки из других доступных объектов. Точнее, к объектам можно добраться только двумя способами:
Определение достижимости «мусора» не является оптимальным, поскольку последний раз программа использует объект задолго до того, как этот объект выпадет из области действия среды. Иногда проводится различие между синтаксическим мусором , теми объектами, которые программа не может достичь, и семантическим мусором , теми объектами, которые программа фактически никогда больше не будет использовать. Например:
Проблема точного определения семантического мусора может быть легко продемонстрирована как частично разрешимая : программа, которая выделяет объект X , запускает произвольную входную программу P и использует X тогда и только тогда, когда P завершается, потребует сборщика семантического мусора для решения проблемы остановки. проблема . Хотя консервативные эвристические методы обнаружения семантического мусора остаются активной областью исследований, практически все практические сборщики мусора сосредоточены на синтаксическом мусоре.
Еще одна сложность этого подхода заключается в том, что в языках с ссылочными типами и типами значений без упаковки сборщик мусора должен каким-то образом различать, какие переменные в стеке или поля в объекте являются обычными значениями, а какие - ссылками: в памяти, целое число и ссылка могут выглядеть одинаково. Затем сборщик мусора должен знать, следует ли рассматривать элемент как ссылку и следовать ему, или это примитивное значение. Одним из распространенных решений является использование указателей с тегами .
Если бы память компьютера была бесконечной, можно было бы просто оставлять ненужные объекты в памяти. Автоматическое управление памятью со сборкой мусора — эмуляция такого бесконечного компьютера на конечной памяти . Многие ограничения сборщиков мусора (нет гарантии, что финализатор выполнится; управляет только памятью, но не другими ресурсами) вытекают из этой метафоры.
В системе со сборкой мусора обязанность освобождения памяти возлагается на среду исполнения программы. Программист лишь создает динамические объекты и пользуется ими, он может не заботиться об удалении объектов, поскольку это делает за него среда. Для этого в состав среды исполнения включается специальный программный модуль, называемый «сборщиком мусора». Этот модуль периодически запускается, определяет, какие из созданных в динамической памяти объектов более не используются, и освобождает занимаемую ими память.
Периодичность запуска сборщика мусора определяется особенностями системы. Сборщик может работать в фоновом режиме, запускаясь при неактивности программы (например, когда программа простаивает, ожидая ввода данных пользователем). Сборщик мусора запускается безусловно, останавливая выполнение программы (англ. Stop-the-world), когда очередную операцию выделения памяти оказывается невозможно выполнить из-за того, что вся доступная память исчерпана. После освобождения памяти прерванная операция выделения памяти возобновляется, и программа продолжает исполняться дальше. Если же оказывается, что освободить память невозможно, среда исполнения останавливает программу с сообщением об ошибке «Недостаточно памяти».
Оптимальным было бы удалять из памяти объекты, к которым в процессе дальнейшей работы программы не будет ни одного обращения. Однако выявление таких объектов невозможно, поскольку сводится к алгоритмически неразрешимой задаче об остановке (для этого достаточно предположить, что некоторый объект X будет использован в том и только в том случае, если успешно завершится программа P). Поэтому сборщики мусора используют консервативные оценки, позволяющие гарантировать, что в будущем объект не будет использоваться.
Обычно критерием того, что объект еще используется, является наличие ссылок на него: если в системе нет больше ссылок на данный объект, то он, очевидно, больше не может быть использован программой, а следовательно, может быть удален. Этот критерий используется большинством современных сборщиков мусора и называется еще достижимостью объекта. Он не является теоретически наилучшим, так как в число достижимых, согласно ему, попадают и те объекты, которые уже никогда не будут использованы, но на которые пока еще существуют ссылки, но гарантирует защиту от появления «висячих» ссылок и может быть реализован достаточно эффективно.
Неформально можно задать следующее рекурсивное определение достижимого объекта:
Алгоритм выставления флагов
Простой алгоритм определения достижимых объектов, «алгоритм пометок» (Mark and Sweep), заключается в следующем:
Если два или более объектов ссылаются друг на друга, но ни на один из этих объектов нет ссылок извне, то вся группа считается недостижимой. Данный алгоритм позволяет гарантированно удалять группы объектов, использование которых прекратилось, но в которых имеются ссылки друг на друга. Такие группы часто называются «islands of isolation» (острова изоляции).
Алгоритм подсчета ссылок
Другой вариант алгоритма определения достижимости — обычный подсчет ссылок. Его использование замедляет операции присваивания ссылок, но зато определение достижимых объектов тривиально — это все объекты, значение счетчика ссылок которых превышает нуль. Без дополнительных уточнений этот алгоритм, в отличие от предыдущего, не удаляет циклически замкнутые цепочки вышедших из употребления объектов, имеющих ссылки друг на друга.
Как только определено множество недостижимых объектов, сборщик мусора может освободить память, занимаемую ими, и оставить остальное как есть. Также можно после освобождения памяти переместить все или часть оставшихся объектов в другие области памяти, обновив вместе с этим все ссылки на них. Эти два варианта реализации называются, соответственно, неперемещающим и перемещающим.
Обе стратегии имеют как достоинства, так и недостатки.
Скорость выделения и освобождения памяти
Неперемещающий сборщик мусора быстрее освобождает память (поскольку эта операция сводится к пометке соответствующих блоков памяти как свободных), но тратит больше времени на ее выделение (поскольку память фрагментируется, и при выделении необходимо найти в памяти нужное количество блоков подходящего размера).
Перемещающий сборщик требует сравнительно больше времени при сборе мусора (тратится дополнительное время на дефрагментацию памяти и изменение всех ссылок на перемещаемые объекты), зато перемещение позволяет использовать чрезвычайно простой и быстрый (O(1)) алгоритм выделения памяти. При дефрагментации объекты передвигаются так, чтобы разделить всю память на две большие области — занятую и свободную, и сохраняется указатель на их границу. Для выделения новой памяти достаточно лишь переместить эту границу, вернув кусок из начала свободной памяти.
Скорость доступа к объектам в динамической памяти
Объекты, поля которых используются совместно, перемещающий сборщик позволяет размещать в памяти недалеко друг от друга. Тогда они вероятнее окажутся в кэше процессора одновременно, что уменьшит количество обращений к относительно медленному ОЗУ.
Совместимость с инородным кодом
Перемещающий сборщик мусора вызывает затруднения при использовании кода, который не управляется системой автоматического управления памятью (такой код называется инородным (англ. foreign) в традиционной терминологии или неуправляемым (англ. unmanaged) в терминологии Microsoft). Указатель на память, выделенную в системе с неперемещающим сборщиком, можно просто передать инородному коду для использования, удерживая хотя бы одну обычную ссылку на объект, чтобы сборщик его не удалил. Перемещающий сборщик меняет положение объектов в памяти, синхронно меняя все ссылки на них, но поменять ссылки в инородном коде он не может, в результате переданные инородному коду ссылки после перемещения объекта станут некорректными. Для работы с инородным кодом используются различные специальные приемы, например, pinning — явная блокировка объекта, запрещающая его перемещение во время сборки мусора.
Как показывает практика, недавно созданные объекты чаще становятся недостижимыми, чем объекты, существующие длительное время. В соответствии с этой закономерностью многие современные сборщики мусора подразделяют все объекты на несколько поколений — серий объектов с близким временем существования. Как только память, выделенная одному из поколений, заканчивается, в этом поколении и во всех более «молодых» производится поиск недостижимых объектов. Все они удаляются, а оставшиеся переводятся в более «старое» поколение.
Использование поколений сокращает время цикла сборки мусора, поскольку уменьшается число просматриваемых в ходе сборки объектов, однако этот метод требует от среды исполнения отслеживания ссылок между разными поколениями.
Неизменные объекты (англ. immutable objects)
Правила языка программирования могут устанавливать, что объекты, объявленные специальным образом или относящиеся к определенным типам, являются принципиально неизменяемыми. Например, такими являются символьные строки в Java и ряде других языков. За счет информации о неизменности система управления памятью может экономить место. Например, когда строковой переменной присваивается значение "Hello", строка размещается в памяти и переменная получает ссылку на нее. Но если впоследствии такой же строкой будет инициализирована другая переменная, то система найдет ранее созданную строку "Hello" в памяти и присвоит второй переменной ссылку на нее же, вместо того, чтобы размещать строку в памяти повторно. Поскольку строка является принципиально неизменной, на логику работы программы такое решение никак не повлияет, но строка не будет дублироваться в памяти, сколько бы раз она ни использовалась. И только когда все ссылки на нее будут удалены, строка будет уничтожена сборщиком мусора.
Как правило, такие константные объекты хранятся в специально выделенных областях памяти, называемых «пулами» (область для хранения неизменных строк — «строковый пул»), для эффективной работы с которыми могут применяться довольно специфичные алгоритмы.
Финализаторы
Финализатор — это код, который автоматически выполняется непосредственно перед удалением объекта из памяти сборщиком мусора. Финализаторы используются для того, чтобы проверить, выполнена ли очистка объекта, и освободить дополнительную память, если она выделялась при создании или работе объекта в обход системы управления памятью.
Неквалифицированные программисты нередко пытаются применять финализаторы для освобождения файлов, сетевых сокетов и других системных ресурсов, используемых объектами. Это крайне плохая практика: поскольку момент удаления объекта сборщиком мусора зависит от объема доступной памяти и интенсивности ее использования программой, невозможно предсказать, когда будет вызван финализатор и будет ли он вызван вообще. Для освобождения любых системных ресурсов, кроме оперативной памяти, финализаторы не подходят; программист должен вручную закрыть файлы или сокеты командой наподобие close(), когда объект реально перестает использоваться.
Сборщик мусора может восстанавливать только те объекты, которые не имеют ссылок, указывающих на них прямо или косвенно из корневого набора. Однако некоторым программам требуются слабые ссылки , которые должны использоваться, пока существует объект, но не должны продлевать его время жизни. При обсуждении слабых ссылок обычные ссылки иногда называют сильными ссылками . Объект имеет право на сборку мусора, если на него нет сильных (то есть обычных) ссылок, даже если на него все еще могут быть некоторые слабые ссылки.
Слабая ссылка - это не просто любой указатель на объект, о котором сборщик мусора не заботится. Этот термин обычно зарезервирован для правильно управляемой категории специальных справочных объектов, которые можно безопасно использовать даже после того, как объект исчезнет, потому что их значение переходит к безопасному (обычно null). Небезопасная ссылка, которая неизвестна сборщику мусора, просто останется висящей, продолжая ссылаться на адрес, по которому ранее находился объект. Это не слабая ссылка.
В некоторых реализациях слабые ссылки делятся на подкатегории. Например, виртуальная машина Java предоставляет три формы слабых ссылок, а именно мягкие ссылки , фантомные ссылки , и обычные слабые ссылки. Объект с мягкой ссылкой подлежит возврату только в том случае, если сборщик мусора решит, что программе не хватает памяти. В отличие от мягкой ссылки или обычной слабой ссылки, фантомная ссылка не предоставляет доступа к объекту, на который она ссылается. Вместо этого фантомная ссылка - это механизм, который позволяет сборщику мусора уведомлять программу, когда указанный объект стал фантомно достижимым.. Объект является фантомно достижимым, если он все еще находится в памяти и на него ссылается фантомная ссылка, но его финализатор уже выполнен. Точно так же Microsoft.NET предоставляет две подкатегории слабых ссылок , а именно длинные слабые ссылки (восстановление треков) и короткие слабые ссылки.
Также могут быть разработаны структуры данных со слабыми функциями отслеживания. Например, полезны слабые хеш-таблицы . Как и обычная хеш-таблица, слабая хеш-таблица поддерживает связь между парами объектов, где каждая пара понимается как ключ и значение. Однако на самом деле хеш-таблица не содержит четких ссылок на эти объекты. Особое поведение имеет место, когда либо ключ, либо значение, либо оба становятся мусором: запись хэш-таблицы самопроизвольно удаляется. Существуют дополнительные усовершенствования, такие как хеш-таблицы, которые имеют только слабые ключи (ссылки на значения - обычные, сильные ссылки) или только слабые значения (ссылки на ключи сильные).
Слабые хэш-таблицы важны для поддержания ассоциаций между объектами, так что объекты, участвующие в ассоциации, могут по-прежнему становиться мусором, если ничто в программе больше не ссылается на них (кроме ассоциированной хеш-таблицы).
Использование для этой цели обычной хэш-таблицы может привести к «утечке логической памяти»: накоплению доступных данных, которые программе не нужны и не будут использовать.
Сборщики трассировки называются так потому, что они отслеживают рабочий набор памяти. Эти сборщики мусора выполняют сборку циклически. Обычно циклы запускаются, когда не хватает свободной памяти для диспетчера памяти, чтобы удовлетворить запрос на выделение. Но циклы часто могут быть запрошены мутатором напрямую или выполняться по расписанию. Оригинальный метод включает в себя наивную метку-и-развертку, в которой весь набор памяти затрагивается несколько раз.
Наивная метка и очистка в действии на куче, содержащей восемь объектов . Об этом говорит сайт https://intellect.icu . Стрелки обозначают ссылки на объекты . Круги представляют сами объекты. Объекты №1, №2, №3, №4 и №6 строго связаны из корневого набора. С другой стороны, объекты # 5, # 7 и # 8 не имеют прямых или косвенных ссылок из корневого набора; следовательно, они мусор.
В наивном методе отметки и очистки каждый объект в памяти имеет флаг (обычно один бит), зарезервированный только для использования при сборке мусора. Этот флаг всегда сброшен , за исключением цикла сбора.
Первый этап - это этап отметки, который выполняет обход дерева всего «корневого набора» и маркирует каждый объект, на который указывает корень, как «используемый». Все объекты, на которые эти объекты указывают и т. Д., Также помечаются, так что помечается каждый объект, доступный через корневой набор.
На втором этапе, этапе развертки , вся память просматривается от начала до конца, проверяются все свободные или используемые блоки; те, которые не помечены как «используемые», недоступны никаким корням, и их память освобождается. Для объектов, которые были помечены как используемые, флаг использования сбрасывается, готовясь к следующему циклу.
Этот метод имеет несколько недостатков, наиболее заметным из которых является то, что вся система должна быть приостановлена во время сбора; никакие изменения рабочего набора недопустимы. Это может привести к тому, что программы будут периодически «зависать» (и, как правило, непредсказуемо), что делает невозможными некоторые приложения, работающие в реальном времени и критичные ко времени. Кроме того, необходимо проверить всю рабочую память, большую часть ее дважды, что может вызвать проблемы в системах с выгружаемой памятью .
Пример трехцветной маркировки на куче с 8 объектами. Белые, серые и черные объекты представлены соответственно светло-серым, желтым и синим цветом.
Из-за этих проблем с производительностью большинство современных сборщиков мусора с трассировкой реализуют какой-либо вариант абстракции трехцветной маркировки , но простые сборщики (такие как сборщик маркировки и очистки ) часто не делают эту абстракцию явной. Трехцветная маркировка работает, как описано ниже.
Созданы три набора - белый , черный и серый :
Во многих алгоритмах изначально черный набор начинается как пустой, серый набор - это набор объектов, на которые напрямую ссылаются корни, а белый набор включает все другие объекты. Каждый объект в памяти всегда находится ровно в одном из трех наборов. Алгоритм работает следующим образом:
Когда серый набор пуст, сканирование завершено; черные объекты доступны из корней, в то время как белые объекты недоступны и могут быть собраны мусором.
Поскольку все объекты, которые не могут быть немедленно доступны из корней, добавляются к белому набору, а объекты могут перемещаться только из белого в серый и из серого в черный, алгоритм сохраняет важный инвариант - ни один черный объект не ссылается на белые объекты. Это гарантирует, что белые объекты могут быть освобождены после того, как серый набор станет пустым. Это называется трехцветным инвариантом . Некоторые варианты алгоритма не сохраняют этот инвариант, но используют модифицированную форму, для которой сохраняются все важные свойства.
У трехцветного метода есть важное преимущество - его можно выполнять «на лету», не останавливая работу системы на значительный период времени. Это достигается путем пометки объектов по мере их выделения и во время мутации с сохранением различных наборов. Контролируя размер наборов, система может выполнять сборку мусора периодически, а не по мере необходимости. Кроме того, исключается необходимость касаться всего рабочего набора на каждом цикле.
Как только недостижимый набор определен, сборщик мусора может просто освободить недостижимые объекты и оставить все остальное как есть, или он может скопировать некоторые или все доступные объекты в новую область памяти, обновив все ссылки на эти объекты как необходимо. Они называются «неподвижными» и «движущимися» (или, альтернативно, «неуплотняющимися» и «уплотняющими») сборщиками мусора соответственно.
Поначалу алгоритм перемещения может показаться неэффективным по сравнению с алгоритмом без движения, поскольку для каждого цикла потребуется гораздо больше работы. Но алгоритм перемещения дает несколько преимуществ в производительности как во время самого цикла сборки мусора, так и во время выполнения программы:
Одним из недостатков движущегося сборщика мусора является то, что он разрешает доступ только по ссылкам, которые управляются средой сбора мусора, и не позволяет выполнять арифметические операции с указателями . Это связано с тем, что любые указатели на объекты будут признаны недействительными, если сборщик мусора перемещает эти объекты (они становятся висячими указателями ). Для взаимодействия с машинным кодом сборщик мусора должен копировать содержимое объекта в место за пределами области памяти, в которой выполняется сборщик мусора. Альтернативный подход - закрепить объект в памяти, не позволяя сборщику мусора перемещать его и позволяя напрямую использовать память для собственных указателей (и, возможно, позволяя арифметику указателей).
Коллекционеры не только различаются по тому, движутся они или неподвижны, их также можно разделить на категории по тому, как они обращаются с наборами белых, серых и черных объектов во время цикла сбора.
Самый простой подход - это полупространственный коллектор , появившийся в 1969 году. В этом движущемся коллекторе память разделена на «из космоса» и «в космос» одинакового размера. Первоначально объекты распределяются в «пространстве» до тех пор, пока оно не заполнится и не запустится цикл сбора. В начале цикла «в космос» становится «из космоса», и наоборот. Объекты, доступные из корневого набора, копируются из «из космоса» в «в космос». Эти объекты сканируются по очереди, и все объекты, на которые они указывают, копируются в «пространство», пока все доступные объекты не будут скопированы в «пространство». Как только программа продолжит выполнение, новые объекты снова будут размещены в «пространстве».
Этот подход очень прост, но поскольку для выделения объектов используется только одно полупространство, использование памяти в два раза выше по сравнению с другими алгоритмами. Этот метод также известен как остановка и копирование . Алгоритм Чейни является усовершенствованием полупространственного коллектора.
Знак и разверткиСборщик мусора хранит бит или два с каждым объектом для записи, является ли он белым или черным. Серый набор хранится в виде отдельного списка или с использованием другого бита. Поскольку дерево ссылок просматривается во время цикла сбора (фаза «метки»), эти биты обрабатываются сборщиком. Последний "проход" по областям памяти освобождает белые объекты. Стратегия отметки и зачистки имеет то преимущество, что после определения запрещенного набора можно использовать либо подвижную, либо неподвижную стратегию сбора. Этот выбор стратегии может быть сделан во время выполнения, если позволяет доступная память. Его недостатком является «раздувание» объектов на небольшое количество, например, каждый объект имеет небольшую стоимость скрытой
продолжение следует...
Часть 1 Отслеживание сборки мусора. Сборка мусора в программировании, утечка памяти
Часть 2 Требования к языку и системе - Отслеживание сборки мусора. Сборка
Часть 3 Сборка мусора в реальном времени - Отслеживание сборки мусора. Сборка
Исследование, описанное в статье про сборка мусора, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое сборка мусора, утечка памяти, достижимость объекта, сбор циклических ссылок и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Языки и методы программирования. Теория трансляции
Комментарии
Оставить комментарий
Языки и методы программирования. Теория трансляции
Термины: Языки и методы программирования. Теория трансляции