Концепции программирования: Сборка мусора

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

Что такое сборка мусора?

Сборка мусора — это форма автоматического управления памятью. Нужна, по сути, для того, чтобы у разработчика было на одну причину для беспокойства меньше.

Когда вы выделяете память, например, создавая переменную, данные попадают либо в стек, либо в кучу (чтобы лучше разобраться, чем они отличаются, читайте статью «Что такое стек и куча»). Когда вы выделяете участок памяти в стеке, вы всегда указываете локальную область видимости, точно зная нужный размер блока памяти. В стек попадают примитивные типы данных, массивы заданного размера и прочее. Стек — автономное хранилище памяти. С ним вам ни о чём не нужно беспокоиться: стек сам оперативно выделяет и чистит память. Для других переменных — объектов, буферов, строк или глобальных переменных — память выделяется в куче.

В отличие от стека куча не автономна. Переменная, отправленная на хранение в кучу, останется там на протяжении всей работы программы и может менять состояние, пока вы вручную не освободите участки памяти, которые больше не нужны. Сборщик мусора — это инструмент, который снимает с разработчика бремя ручного управления кучей. Большинство современных языков, например, Java, .NET framework, Python, Ruby или Go используют сборку мусора. А вот C и C++ нет. В этих языках над разработчикам висит чрезвычайно важная задача собственноручно вычищать память.

Зачем нужна сборка мусора?

Сборка мусора освобождает разработчика от целого ряда проблем. Во-первых, это утечка памяти. Если программа не освобождает память от ставших ненужными данных регулярно, то чем больше памяти вы будете выделять в кучу, тем больше эта память будет накапливаться. В результате произойдет переполнение кучи. Даже если разработчик старательно чистит хранилище, стоит появиться всего одной переменной, которую долго не удаляют, и всё — получите утечку памяти. А это плохо.

Допустим, утечек памяти у вас нет. Не расслабляйтесь. Что если вы попытаетесь дать ссылку на переменную, которую уже удалили или переместили? Такая ситуация называется висячий указатель. В лучшем случае в ответ вы получите околесицу и, надеюсь, вызовите ошибку проверки вскоре после того, как используете переменную. А в худшем поверх старой области памяти система запишет новые данные, которые будут выдавать на вид правильные (но логически неверные) ответы. Вы вообще не будете понимать, что творится. Именно такие ошибки памяти сложнее всего устранять.

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

Как и когда запускается сборка мусора?

Зависит от алгоритма. Не существует какого-то одного раз и навсегда установленного способа собирать мусор. Как и компиляторы с интерпретаторами, механизмы сборки мусора совершенствуются со временем. Иногда сборщик мусора работает с заранее определенными временными интервалами, а иногда он ждёт определенных условий, которые должны возникнуть до его запуска. Сборщик мусора почти всегда работает в отдельном потоке в тандеме с программой. В зависимости от реализации языка программирования сборщик мусора либо приостанавливает программу, чтобы разом вымести весь мусор (такую остановку называют stop-the-world или пусть-весь-мир-подождет), либо удаляет память небольшими партиями, либо работает параллельно с программой.

Углубляться дальше — значит разбирать сборку мусора на конкретных языках, а это не наша цель. Поэтому переходим к основным алгоритмам сборки мусора.

Алгоритмы сборки мусора

Алгоритмов существует превеликое множество. Я приведу лишь самые распространенные, с которыми вы неизбежно столкнётесь. Заметьте, многие стандартные алгоритмы сборки мусора строятся друг на друге.

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

Одно из важных преимуществ сборки мусора с помощью подсчёта ссылок заключается в том, что системе всегда понятно, когда есть мусор (когда на счётчике ноль). Но есть у этого способа и крупные минусы. Циклические ссылки просто-напросто невозможно вычистить. Если объект А ссылается на объект B, а объект В — обратно на А, сборщик мусора, работающий по принципу подсчёта ссылок, их никогда в жизни не удалит. А ещё подсчёт ссылок — очень неэффективный с точки зрения производительности метод, потому что по каждому объекту памяти постоянно идет работа счётчиков.

Из-за указанных недостатков современные сборщики мусора построены на других алгоритмах.

Пометка-очистка (Mark-Sweep)
Пометка-очистка, как и почти все остальные способы сборки мусора, не считая подсчёта ссылок, является отслеживающим алгоритмом. Суть таких алгоритмов — отслеживать объекты, доступные из одного или нескольких “корней”, с целью выявить недоступные (и, следовательно, неиспользуемые) области памяти. В отличие от подсчёта ссылок при пометке-очистке не производится постоянная проверка, а значит, этот алгоритм теоретически может выполняться в любой момент.

Самая простая форма такого алгоритма — примитивная пометка-очистка, при которой для каждого выделенного блока памяти хранится специальный бит для сборки мусора. Алгоритм дважды пропускает через себя все объекты: сначала сборщик по биту находит и помечает все пассивные объекты памяти, а потом удаляет их.

Пометка-очистка эффективнее подсчёта ссылок, потому что тут не нужно следить за счетчиками. А ещё такой метод позволяет удалять циклические ссылки. Однако примитивная пометка-очистка — это классический пример сборки мусора по принципу stop-the-world: пока выполняется алгоритм, вся программа вынуждена приостановить работу (не примитивные алгоритмы собирают мусор частями или параллельно с программой). Поскольку отслеживающая сборка мусора может осуществляться в любое время, вам не удастся предугадать, когда программа в очередной раз встанет. Кроме того, алгоритм дважды перебирает память кучи, а это еще больше замедляет программу. А еще при пометке-очистке не приводится в порядок фрагментированная память. Приведу наглядную аналогию. Представьте, что динамическая память (куча) — это цельная сетка. После метода пометки-очистки она будет выглядеть, как очень неудачная игра в Тетрис. Из-за фрагментации впоследствии снижается эффективность выделения памяти в куче. Так что этот алгоритм еще предстоит оптимизировать.

Пометка-сжатие (Mark-Compact)
Алгоритмы типа пометка-сжатие используют ту же логику, что пометка-очистка, с добавлением ещё как минимум одного действия с отмеченной областью памяти. Делается это, чтобы сжать и дефрагментировать память. Такой метод решают проблему с фрагментацией, которая произошла в результате пометки-очистки. В результате выделение памяти происходит эффективнее — по принципу выбивания (bump allocation), который похож на работу стека («последним пришёл — первым вышел»). С другой стороны, из-за дополнительных итераций пометка-сжатие выполняется и обрабатывается дольше.

Копирование
Копирование (также известное как алгоритм Чейни) чем-то похоже на пометку-сжатие. Однако вместо того, чтобы по несколько раз перебирать одну и ту же область памяти, алгоритм просто копирует “выжившие” блоки памяти в совершенно новую область после фазы отметки, а это по умолчанию сжимает память. По окончанию копирования старая область памяти очищается, а все ссылки на сохранившуюся память теперь ведут в новые области памяти. При таком подходе сборщикам мусора приходится обрабатывать намного меньше информации. Кроме того, процесс копирования быстрее, чем даже пометка-очистка, потому что фазы очистки тут попросту нет.

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

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

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

Заключение

Сборка мусора — не самая легкая для понимания тема, в которой и не обязательно досконально разбираться, если вы работаете с современными языками программирования. Но это недостаточно веский довод, чтобы проигнорировать эту тему. Да, сборка мусора почти не имеет отношения к коду, который вы пишете, но этот процесс — неотъемлемая часть любой языковой реализации. А алгоритм сборки мусора, используемый в языке, часто становится основной причиной, по которой люди либо любят, либо терпеть не могут некоторые реализации.

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

Пока я собирал информацию для этой статьи, я заметил любопытную вещь. Большинство заметок на тему сборки мусора описывают этот процесс исключительно применительно к основной реализации Java. Конечно, сборка мусора встречается не только в Java, но думаю, такая гегемония именно этого языка в статьях про сборку мусора вызвана тем, что Java очень часто сравнивают с C++, где сборки мусора вообще нет. Надеюсь, что в будущем появится больше постов о том, как сборка мусора осуществляется в других языка. Пока же приходится довольствоваться тем, что есть!
  • 0

1 комментарий