Марк – компактный алгоритм
В информатике алгоритм mark-compact — это тип сборки мусора алгоритма , используемый для освобождения недоступной памяти . Алгоритмы Mark-Compact можно рассматривать как комбинацию алгоритма Mark-Sweep и алгоритма копирования Чейни . Сначала помечаются доступные объекты, затем на этапе сжатия доступные (отмеченные) объекты перемещаются в начало области кучи. Уплотнение сборки мусора используется современными JVM , Microsoft Common Language Runtime и компилятором Glasgow Haskell .
Алгоритмы
[ редактировать ]После маркировки живых объектов в куче тем же способом, что и при использовании алгоритма маркировки-очистки , куча часто оказывается фрагментированной . Цель алгоритмов mark-compact — сдвинуть живые объекты в памяти вместе, чтобы исключить фрагментацию. Задача состоит в том, чтобы правильно обновить все указатели на перемещенные объекты, большинство из которых после сжатия получат новые адреса в памяти. Проблема обработки обновлений указателя решается по-разному.
Табличное уплотнение
[ редактировать ]
Табличный алгоритм был впервые описан Хэддоном и Уэйтом в 1967 году. [1] Он сохраняет относительное расположение живых объектов в куче и требует лишь постоянного объема накладных расходов.
Уплотнение происходит снизу вверх (низкие адреса) к верху (высокие адреса). При обнаружении живых (то есть помеченных) объектов они перемещаются по первому доступному младшему адресу, а запись добавляется в таблицу разрывов с информацией о перемещении. Для каждого действующего объекта запись в таблице разрывов состоит из исходного адреса объекта до уплотнения и разницы между исходным адресом и новым адресом после уплотнения. Таблица разрывов хранится в сжимаемой куче, но в области, помеченной как неиспользуемая. Чтобы гарантировать, что сжатие всегда будет успешным, минимальный размер объекта в куче должен быть больше или равен размеру записи таблицы разрывов.
По мере сжатия перемещенные объекты копируются в нижнюю часть кучи. В конечном итоге объект необходимо будет скопировать в пространство, занимаемое таблицей разрывов, которую теперь необходимо переместить в другое место. Эти движения таблицы разрывов ( называют их перекатыванием таблицы авторы ) приводят к тому, что записи о перемещении становятся неупорядоченными, что требует сортировки таблицы разрывов после завершения уплотнения. Стоимость сортировки таблицы разрывов равна O ( n log n ), где n — количество живых объектов, найденных на этапе маркировки алгоритма.
Наконец, записи перемещения таблицы разрывов используются для настройки полей указателей внутри перемещаемых объектов. Живые объекты проверяются на наличие указателей, которые можно найти в отсортированной таблице разрывов размера n за время O(log n ), если таблица разрывов отсортирована, при общем времени работы O ( n log n ). Затем указатели корректируются на величину, указанную в таблице перемещения.
Алгоритм ЛИСП 2
[ редактировать ]Чтобы избежать сложности O ( n log n ), алгоритм LISP 2 использует три разных прохода по куче. Кроме того, объекты кучи должны иметь отдельный слот указателя пересылки, который не используется за пределами сборки мусора.
После стандартной маркировки алгоритм выполняется в следующие три прохода:
- Вычислите место пересылки для живых объектов.
- Отслеживайте свободный и активный указатель и инициализируйте оба указателя в начале кучи.
- Если действующий указатель указывает на действующий объект, обновите указатель пересылки этого объекта на текущий свободный указатель и увеличьте свободный указатель в соответствии с размером объекта.
- Переместите живой указатель на следующий объект
- Заканчивается, когда живой указатель достигает конца кучи.
- Обновить все указатели
- Для каждого живого объекта обновите его указатели в соответствии с указателями пересылки объектов, на которые они указывают.
- Перемещение объектов
- Для каждого живого объекта переместите его данные в место пересылки.
Этот алгоритм имеет размер O ( n ) в зависимости от размера кучи; его сложность выше, чем у табличного подхода, но n в табличном подходе — это размер только используемого пространства, а не всего пространства кучи, как в алгоритме LISP2. Однако алгоритм LISP2 проще реализовать.
Компрессор
[ редактировать ]Алгоритм сжатия компрессора [2] имеет наименьшую сложность среди известных сегодня алгоритмов уплотнения. Он расширяет сборку мусора IBM для Java. [3] Последовательная версия Compressor поддерживает карту перемещения, которая сопоставляет старый адрес каждого объекта с его новым адресом (т. е. его адрес до сжатия сопоставляется с адресом после сжатия). На первом проходе сопоставление вычисляется для всех объектов в куче. На втором проходе каждый объект перемещается на новое место (сжимается до начала кучи), а все указатели внутри него изменяются в соответствии с картой перемещения.
Вычисление карты перемещения на первом проходе можно сделать очень эффективным, работая с небольшими таблицами, не требующими прохода по всей куче. Это позволяет снизить сложность компрессора, включая один проход по небольшим таблицам и один проход по всей куче. Это представляет собой наиболее известную сложность алгоритмов уплотнения.
У Compressor также есть параллельная версия, в которой несколько потоков сжатия могут работать вместе для параллельного сжатия всех объектов. У Compressor также есть параллельная версия, в которой потоки сжатия могут работать одновременно с программой, осторожно позволяя программе получать доступ к объектам по мере их перемещения к началу кучи. Параллельная и параллельная версии Compressor используют примитивы виртуальной памяти.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ БК Хэддон; В.М. Уэйт (август 1967 г.). «Процедура сжатия элементов хранения переменной длины» (PDF) . Компьютерный журнал . 10 (2): 162–165. дои : 10.1093/comjnl/10.2.162 .
- ^ Кермани, Хаим; Петранк , Эрез (июнь 2006 г.). Компрессор: параллельное, инкрементальное и параллельное уплотнение. Материалы 27-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . Материалы 27-й конференции ACM SIGPLAN по разработке и реализации языков программирования. стр. 354–363. дои : 10.1145/1133255.1134023 .
- ^ Абуайад, Диаб; Оссия, Йоав; Петранк, Эрез; Зильберштейн, Ури (октябрь 2004 г.). Эффективный параллельный алгоритм сжатия кучи . Конференция ACM по объектно-ориентированному программированию, системам, языкам и приложениям. стр. 224–236. дои : 10.1145/1028976.1028995 .
| Аппаратное обеспечение |
|
|---|---|
| Виртуальная память | |
| Сегментация памяти | |
| Распределитель памяти | |
| Ручное управление памятью | |
| Сбор мусора | |
| Безопасность памяти | |
| Проблемы | |
| Другой | |
