А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 115
Текст из файла (страница 115)
Когда значение счетчика обнуляется, обращение к объекту становится невозможным и, следовательно, объект может быть удален. Однако такой метод не в состоянии выявить зацикленную структуру без внешних ссылок на нее (обращение к такой структуре невозможно из-за отсутствия в программе ссылок на нее, но и удаление ее также невозможно, поскольку части структуры вза- 568 Глава 7. Среды времени выполнения имно ссылаются друг на друга, так что счетчики не обнулены). Пример такой структуры приведен в примере 7.11.
Подсчет ссылок решает проблему с висящими указателями, поскольку указателей на удаленный объект не остается. Однако это достаточно дорогой метод, поскольку приводит к накладным расходам для каждой операции по сохранению указателя. ° Выделение пимяти областями (ге8!оп-Ьазед айосабоп) используется для наборов объектов, времена жизни которых связаны с некоторой фазой вычислений. Когда объекты создаются только для использования на некотором шаге вычислений, можно выделить память для них в одной области, которая затем, по завершении этого шага, будет освобождена. Такой метод распределения памяти имеет ограниченное применение, но там, где он может использоваться, он весьма эффективен.
Вместо удаления объектов по одному он удаляет всю область целиком. 7.4.6 Упражнения к разделу 7.4 Упражнение 7.4.1. Предположим, что куча состоит из семи блоков, начиная с адреса О. Размеры блоков, начиная с младшего адреса, — 80, 30, 60, 50, 70, 20 и 40 байт. При размещении объекта в блоке (если позволяет размер последнего) он помещается в старших адресах блока и образует меньший блок. Однако размеры блоков не могут быть меньше 8 байт, так что если объект почти такого же размера, как и блок, в котором он располагается, то объекту выделяется весь блок полностью, а сам объект располагается в младших адресах блока. Как будет выглядеть список свободной памяти после удовлетворения запросов на 32, 64, 48 и 16 байт в указанном порядке, если используется метод а) первого подходящего; б) наилучшего подходящего.
7.5 Введение в сборку мусора Данные, обращение к которым невозможно, в общем случае известны как мусор (8агЪайе). Многие высокоуровневые языки программирования снимают бремя управления памятью вручную с плеч программиста путем использования автоматической сборки мусора, которая освобождает память, занятую недостижимыми данными. Возникновение сборки мусора датируется !958 годом, когда она была применена в начальной реализации !.!зр.
Другими важными примерами языков программирования, использующих сборку мусора, являются )ака, Рег!, М1,, Мск(ц)а-3, Рго!о8 и Ята!Кайо 5б9 7.5. Введение в сборку мусора В этом разделе мы рассмотрим ряд концепций сборки мусора. Понятие "достижимости" объекта, пожалуй, интуитивно понятное, но нам следует быть точными. Точные правила рассматриваются в разделе 7.5.2.
В разделе 7.5.3 мы рассмотрим простой, но несовершенный метод сборки мусора — подсчет ссылок, основанный на той идее, что как только программа теряет все ссылки на объект, она уже не может обратиться к занимаемой им памяти. В разделе 7.6. рассматриваются сборщики, основанные на отслеживании, алгоритмы которых определяют объекты, к которым возможны обращения, и превращают все остальные блоки кучи в свободные.
7.5.1 Цели проектирования сборщиков мусора Сборка мусора представляет собой утилизацию блоков памяти, в которых хранятся объекты, более не требующиеся программе. Мы должны считать, что объекты имеют тип, который сборщик мусора в состоянии определить во время выполнения программы. Исходя из типа объекта можно определить, насколько велик сам объект и какие его компоненты содержат ссылки (указатели) на другие объекты. Мы также считаем, что ссылки на объекты всегда указывают на адрес начала объекта и никогда — на место внутри объекта. Таким образом, все ссылки на объект имеют одно и то же значение и могут быть легко идентифицированы. Пользовательская программа, о которой в дальнейшем мы будем говорить как о лпчлаеоре (ппйаюг), модифицирует набор объектов в куче.
Мутатор создает объекты, запрашивая пространство для них у диспетчера памяти, и, кроме того, может создавать и удалять ссылки на существующие объекты. Объекты становятся мусором, когда мутатор не в состоянии "достичь" его в том смысле, который будет точно определен в разделе 7.5.2. Сборщик мусора находит недостижимые объекты и утилизируег отведенное им пространство, передавая его диспетчеру памяти, который отслеживает свободную память в куче. Основное требование: безопасность типов Ие все языки программирования являются хорошими кандидатами для автоматической сборки мусора.
Чтобы сборщик мусора корректно работал, он должен быть в состоянии сообщить, является ли любой данный элемент данных или его компонент указателем (или может использоваться в качестве такового) на блок выделенной памяти. Язык, в котором можно определить тип любого компонента данных, называется безопасным с точки зрения глилов (1уре заГе). Сушествуют безопасные с точки зрения типов языки наподобие МЕ, в котором типы могут быть определены во время компиляции. Имеются и другие безопасные языки наподобие )ача, типы которого не могут быть определены во время компиляции, но могут быть определены во время выполнения. Такие языки называются динамически типизированными (бупапйсайу турец).
Если язык не является ни статически, 570 Глава 7. Среды времени выполнения ни динамически безопасным с точки зрения типов, говорят, что он небезопасен (цпзаГе). Небезопасные языки программирования, которые, к сожалению, включают такие важные языки, как С н С++, являются плохими кандидатами для автоматической сборки мусора.
В небезопасных языках допускается произвольная работа с адресами — к указателям могут применяться арифметические операции для создания новых указателей; произвольные целые числа могут рассматриваться как указатели. Таким образом, программа теоретически может в любой момент времени обратиться к любой ячейке памяти.
Следовательно, ни одна ячейка памяти не может рассматриваться как недостижимая н никакая память не может быть безопасно угилизирована. На практике большинство программ на языках программирования С и С+~- не генерируют указатели произвольным образом, и можно разработать теоретически ненадежный сборщик мусора, который, тем не менее, эмпирически будет хорошо работать.
Мы рассмотрим консервативный сборщик мусора для С и С+ь в разделе 7.8.3. Критерии производительности Сборка мусора часто настолько дорогостояща, что, хотя она и изобретена десятилетия назад и абсолютно предотвращает утечки памяти, она все еще должна быть принятой многими широко распространенными языками программирования. За время существования сборки мусора предложена масса различных подходов, но ни один из них не может претендовать на звание наилучшего алгоритма сборки мусора. Перед рассмотрением различных вариантов давайте сначала перечислим критерии производительности, которые должны учитываться при проектировании сборщика мусора.
° Общее время работы. Сборка мусора может быть очень медленной. Очень важно, чтобы она не увеличивала существенно общее время работы приложения. Поскольку сборщик мусора должен обойти огромное количество данных, его производительность сильно зависит от того, как он использует подсистему памяти. ° Использование памяти. Очень важно, чтобы сборщик мусора устранял фрагментацию и позволял эффективнее использовать доступную память.
° Работа в паузах. Простые сборщики мусора знамениты тем, что заставляют программы — мутаторы — внезапно, безо всякого предупреждения приостанавливаться на длительное время, пока не будет выполнена сборка мусора. Таким образом, помимо минимизации времени работы, желательно, чтобы максимальная пауза в работе основной программы была минимизирована. В качестве важного частного случая программы, работающие 571 7.5. Введение в сборку мусора в реальном времени, требуют, чтобы определенные вычисления укладывались в отведенные для них временные рамки.
Следует либо подавлять работу сборщика мусора в программах реального времени, либо ограничивать время максимальной паузы. Таким образом, сборщики мусора редко используются в приложениях реального времени. ° Локальность программ. Мы не можем оценить скорость работы сборщика мусора только по его времени работы. Сборщик мусора управляет размещением данных и, таким образом, влияет на локальность данных в мутаторе.
Он может повысить временную локальность мутатора, освобождая память и повторно используя ее; он может повысить пространственную локальность мутатора, перемешая совместно используемые данные в один и тот же кэш или страницы. Некоторые из перечисленных целей проектирования конфликтуют друг с другом, и компромисс может быть достигнут путем тщательного рассмотрения типичного поведения программы. Кроме того, объекты с разными характеристиками могут потребовать различной обработки, с применением разных методов для объектов разного вида.
Например, среди выделенных объектов обычно доминируют объекты малого размера, так что выделение памяти для малых объектов не должно приводить к большим накладных расходам. С другой стороны, рассмотрим сборщик мусора, который переносит достижимые объекты. Перенос больших объектов — более дорогостояшая операция, чем перенос малых. Еше один пример: вообше говоря, чем дольше мы ждем вызова сборщика, основанного на отслеживании, тем больше становится объектов, которые могут быть собраны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
