Марк-компактный алгоритм - Mark-compact algorithm

В Информатика, а mark-compact алгоритм это тип вывоз мусора алгоритм используется для восстановления недостижимая память. Марк-компактные алгоритмы можно рассматривать как комбинацию алгоритм разметки и Алгоритм копирования Чейни. Сначала помечаются достижимые объекты, затем на этапе уплотнения доступные (отмеченные) объекты перемещаются в начало области кучи. Сжатие сборки мусора используется Microsoft с общеязыковая среда выполнения и по Компилятор Glasgow Haskell.

Алгоритмы

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

Уплотнение на основе таблицы

Иллюстрация алгоритма уплотнения таблицы-кучи. Объекты, которые на этапе маркировки определены как достижимые (живые), окрашены, свободное место - пустым.

Табличный алгоритм был впервые описан Хэддоном и Уэйтом в 1967 году.^[1] Он сохраняет относительное размещение живых объектов в куче и требует лишь постоянного количества накладных расходов.

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

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

Наконец, записи о перемещении таблицы разбиения используются для настройки полей указателей внутри перемещаемых объектов. Живые объекты проверяются на наличие указателей, которые можно найти в отсортированной таблице разбиения размера. п в O (журналп) время, если таблица разбиения отсортирована, для общего времени работы О(п бревноп). Затем указатели корректируются на величину, указанную в таблице перемещения.

Алгоритм LISP2

Чтобы избежать О(п бревноп) сложность, LISP2 Алгоритм использует 3 разных прохода по куче. Кроме того, объекты кучи должны иметь отдельный слот указателя пересылки, который не используется вне сборки мусора.

После стандартной маркировки алгоритм выполняет следующие 3 прохода:

1. Вычислить место пересылки для живых объектов.
   • Следите за свободный и жить указатель и инициализируйте как начало кучи.
   • Если жить указатель указывает на живой объект, обновите указатель пересылки этого объекта до текущего свободный указатель и увеличить свободный указатель в соответствии с размером объекта.
   • Переместите жить указатель на следующий объект
   • Конец, когда жить указатель достигает конца кучи.
2. Обновить все указатели
   • Для каждого живого объекта обновите его указатели в соответствии с указателями пересылки объектов, на которые они указывают.
3. Переместить объекты
   • Для каждого живого объекта переместите его данные в место пересылки.

Этот алгоритм О(п) от размера кучи; он имеет лучшую сложность, чем табличный подход, но табличный подход п - это размер только используемого пространства, а не всего пространства кучи, как в алгоритме LISP2. Однако алгоритм LISP2 проще реализовать.

Смотрите также

• Устранение мертвого кода

Рекомендации

1. Б. К. Хэддон и В. М. Уэйт (август 1967 г.). «Процедура уплотнения элементов хранения переменной длины» (PDF). Компьютерный журнал. 10 (2): 162–165. Дои:10.1093 / comjnl / 10.2.162.