Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 130
Текст из файла (страница 130)
Алгоритм маркировки устанавливает бит сбора мусора каждого активного элемента в положение «выключен». 2. Сбор элементов. После того как алгоритм маркировки отметил активные элементы, все остальные элементы, у которых бнт сбора мусора установлен в положении «включен», рассматриваются как мусор и могут быть возвращены в список свободного пространства. Для этого достаточно просто по- 10.4. Управление кучей 473 следовательно просмотреть всю кучу. По мере просмотра проверяется бит сбора мусора каждого элемента. Если этот бит находится в положении «выключен», то элемент пропускается; если же в положении «включен», то элемент присоединяется к списку свободного пространства. Во время этого просмотра все биты сбора мусора устанавливаются в положение «включен» (для подготовки к последующему сбору мусора).
Наиболее сложной частью процедуры сбора мусора является маркировка. Поскольку в момент инициирования процедуры сбора мусора ресурсы памяти исчерпаны, любой элемент в куче либо активен (то есть используется), либо является мусором. К сожалению, анализ самого элемента не позволяет определить, является ли он мусором, поскольку ничто внутри элемента нс указывает на то, что он больше не доступен из другого активного элемента. Более того, даже наличие указателя на этот элемент из какого-либо другого элемента кучи не гарантирует, что этот элемент является активным; дело в том, что оба элемента могут оказаться мусором. Следовательно, простого сканирования кучи, при котором просматриваются указатели и элементы, на которые существуют указатели, помечаются как активные, недостаточно. Когда элемент кучи является активным? Очевидно, в том случае, если на этот элемент есть указатель из другого иктивного элемента кучи или извне кучи.
Если можно определить все такие внешние указатели и отметить соответствующие элементы кучи, то можно начинать итерационный процесс маркировки, в ходе которого ищутся в этих активных элементах указатели на другие, пока не отмеченные элементы. Зги новые элементы также отмечаются и в пих ищутся новые указатели и т.
д. Требуется достаточно аккуратно использовать указатели, поскольку при маркировке подразумевается выполнение следующих трех условии: 1) любой активный элемент должен быть достижим по цепи указателей, начинающейся вне кучи; 2) должна иметься возможность обнаружения всех указателей вне кучи, указывающих на элемент внутри нее; 3) для каждого активного элемента должна иметься возможность определить все поля внутри него, которые содержат указатели на другие элементы кучи.
В 1.13Р эти три условия выполняются, что позволяет использовать в этом языке технологию сбора »1усора. Но если хотя бы одно их этих предположений не выполнено, то в процессе маркировки некоторые активные элементы могут быть пропущены. Например, в С предположения 2 и 3 могут не выполняться. Если бы в С использовался сбор мусора, в результате могли бы быть восстановлены активные элементы и, таким образом, образовались бы повисшие ссылки.
Полезно разобрать, каким образом достигается выполнение этих предположений в типичной реализации 1.1ЯР. Во-первых, все элементы кучи имеют одинаковый формат, обычно состоящий из двух полей для указателей и рядадополнительных битов для системных данных (в том числе бита сбора мусора). Поскольку каждый элемент кучи содержит ровно два указателя и они расположены всегда в одних и тех же позициях в элементе, предположение 3 всегда выполняется. Вовторых, имеется только небольшой набор системных структур данных, которые могут содержать указатели на элементы кучи.
Если начинать маркировку с этих 474 Глава 10. Управление памятью системных структур данных, можно с уверенностью сказать, что все указатели внутрь кучи будут обнаружены, тем самым гарантируется выполнение условия 2. Наконец, к элементу кучи можно получить доступ только по цепи указателей, начинающейся вне кучи. Например, указатель на некоторый элемент кучи не может быть получен добавлением константы к какому-либо другому указателю — таким образом, выполняется условие 1.
В примере 10.1 показано, как во время выполненияя программы на 1 1ЯР процедура сбора мусора взаимодействует со стеком и кучей. Пример 10.1. Распределение памяти в ).)ЗР Взаимоотношения между стеком и кучей в Ь)ВР проиллюстрированы на рис. 10.3. На этом рисунке предполагается следующее; + куча содержит 15 элементов, из которых 9 в настоящий момент принадлежат списку 6 ее свободного пространства (см. рис. 10.3, а); + пользователем были введены следующие два определения; (Оетоп и (х у г) (оопп х (12 у г))) (се)оп 12(ч и) (оопп ч и)) Выполнение выражения (11 'а '(Ь с) '(о е)) происходитследующим образом: 1.
Вызывается функция 11 и аргументы х, у и 2 добавляются в стек с использованием девяти доступных элементов кучи из списка 1гее свободного пространства (см. рис. 10.3, б). 2. Вызывается функция 12 с указателями на ее аргументы ч и н (см. рис. 10.3, в). 3. Список 1гее свободного пространства пуст. В процессе сборки мусора сначала отмечаются элементы, на которые имеются указатели из стека, а на втором проходе все оставшиеся элементы помещаются в список 1гее свободного пространства (см, рис, 10.3, г).
4. Вычисляется значение для 12 и помещается в стек (см. рис, 10.3, д). 5. Вычисляется значение для (1 и помещается в стек (см, рис. 10.3, е). Система Ь!8Р автоматически отображает результат для пользователя б. Все элементы в вычислении теперь являются мусором Когда список Ггее свободного пространства в очередной раз станет пустым, эти элементы будут восстановлены для повторного использования во время очередной инициализации процедуры сбора мусора. 10.4.3.
Элементы переменного размера Управление кучей, в которой программист выделяет и возвращает элементы переменного размера, сложнее, чем в случае с использованием элементов фиксированного размера, хотя многие из уже описанных концепций применимы и здесь. Элементы переменного размера встречах)тся во многих ситуациях. Например, если память используется для определяемых программистом структур да)щых, сохраняемых последовательно, например массивов, то требуются блоки памяти различных размеров; то же самое касается и записей активаций для задач, которые могут быть размещены в куче в последовательных блоках переменных размеров.
10.4. Управление кучей 475 Вызов функции 11 с аргументами а, (Ь, с), (д, е) б Начальное состояние Стек Куча Стек Куча Стек Куча Стек Куча Вычисление 12=((Ьс)де) д Вычисление (1 =(а(Ьс)де) е Стек Куча ( ) 1 Активные (выделенные) узлы (,Д Неактивные узлы (мусор) И Указатель пц~( (конец списка) Узлы 11 освобождаются ж Рис. 10.3. Расположение в памяти кучи и стека языка (зВР Вызов функции (2 Сбор мусора — отмечается 9 узлов с аргументами (Ьс)(де) в г 476 Глава 1О. Управление памятью Основные трудности в случае элементов переменного размера связаны с повторным использованием освободившейся памяти.
Даже если мы возвраьцаем в список свободных элементов кучи два блока размером по пять слов каждый, может оказаться невозможным удовлетворить последующий запрос на блок из шести слов. Такая проблема не возникала в более простом случае использования блоков фиксированного размера, возвращаемое пространство всегда могло быть сразу же повторно использовано. Начальное распределение и повторное использование В случае использования элементов фиксированного размера можно было сразу же разбить кучу на множество элементов и затем осуществить начальное распределение памяти на основе списка свободного пространства, содержащего эти элементы. Но для элементов персмещюго размера такой метод неприменим.
Вместо этого нам желателыю поддерживать свободное пространство в блоках максимально возможного размера. Тогда мы изначально рассматриваем всю кучу как просто один блок свободной памяти. Для начального распределения подходит укизатель кучи, Когда запрашивается блок из дГ слов, то указатель кучи перемещается на Мелов, а его прежнее значение возвращается в качестве указателя на вновь размещенный элемент. Когда освобождается память позади стоящего впереди указателя кучи, она может быть объединена в список свободного пространства. Рано или поздно указатель кучи достигнет конца блока, составляющего кучу. Теперь следует повторно использовать ту часть памяти, которая на данный момент не задействована под активныс элементы.
С учетом того, что эти элементы имеют различный размер, можно предложить два способа повторного использования этой памяти: 1) испольэовать список свободного пространства, проводя в нем поиск блока подходящсто размера и возврац~ая послс выделения памяти оставшуюся часть блока снова в список свободно~о пространства; 2) уплотнить свободное пространство, переместив все активные элементы к одному краю кучи, оставляя нрп этом все свободное пространство в виде единого блока и нерсустанавливая указатель кучи на начало этого блока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
