Что такое Mark-and-sweep?

Что такое Mark-and-Sweep?

Mark-and-Sweep — это фундаментальный алгоритм сборки мусора (Garbage Collection, GC), используемый для автоматического управления памятью в средах выполнения, таких как JVM (для Java/Kotlin в Android) или ART/Dalvik. Основная цель алгоритма — выявление и освобождение памяти, занятой объектами, которые больше не достижимы из корневых точек (например, активных потоков, статических полей, локальных переменных), тем самым предотвращая утечки памяти.

Принцип работы алгоритма

Алгоритм состоит из двух ключевых фаз, выполняемых последовательно:

1. Фаза Mark (Пометка)

На этом этапе сборщик мусора обходит граф достижимых объектов, начиная с корневых точек (GC Roots). Каждый объект, доступный из корней, помечается как «живой». Этот обход аналогичен поиску в глубину (DFS) по ссылочной структуре приложения.

// Пример: объекты, достижимые из корней, помечаются
class User(val name: String)
val root = User("Alice") // Корневая точка
val child = User("Bob")
root.friend = child // Связь между объектами
// В фазе Mark будут помечены root и child

2. Фаза Sweep (Очистка)

После пометки всех достижимых объектов, сборщик сканирует всю память кучи (heap). Объекты, которые не были помечены на предыдущем этапе, считаются мусором и удаляются. Их память освобождается для последующих аллокаций.

// Псевдокод фазы Sweep
for (Object obj : heap) {
    if (!obj.isMarked()) {
        freeMemory(obj); // Освобождение памяти
    } else {
        obj.unmark(); // Сброс пометки для следующего цикла GC
    }
}

Пример работы в Android (Kotlin)

Рассмотрим сценарий, где объекты становятся недостижимыми:

fun createTempData() {
    val list = mutableListOf("A", "B", "C") // Объект создается в куче
    // list достижима из корней (локальная переменная)
    processList(list)
    // После выхода из функции list больше не достижима (становится мусором)
}
// На следующем цикле Mark-and-Sweep:
// 1. Mark: list не помечается, так как нет ссылок из корней.
// 2. Sweep: память list освобождается.

Преимущества Mark-and-Sweep

• Автоматическое управление памятью: Избавляет разработчика от ручного освобождения памяти, снижая риск утечек.
• Универсальность: Алгоритм справляется с циклическими ссылками (например, два объекта ссылаются друг на друга, но недостижимы из корней), которые были бы проблемой для счетчиков ссылок.
• Стабильность: Гарантирует, что используемые объекты не будут преждевременно удалены.

Недостатки и оптимизации в Android

• Простой Mark-and-Sweep приостанавливает выполнение программы (STW — Stop-The-World) на время сборки, что может вызывать фризы интерфейса. В Android это критично для плавности UI.
• Фрагментация памяти: Освобожденные области могут быть разрозненными, что требует компактизации (compacting) для оптимизации памяти.
• Накладные расходы: Поиск по всей куче в фазе Sweep ресурсоемок.

В Android (ART) используются продвинутые варианты:

• Generational GC: Разделение объектов на молодые и старые поколения для частой сборки в молодой части.
• Concurrent Mark-Sweep (CMS): Параллельное выполнение пометки/очистки без полной остановки приложения.
• Compacting GC: Перемещение живых объектов для устранения фрагментации.

Заключение

Mark-and-Sweep — это основа сборки мусора в Android, обеспечивающая автоматическое освобождение памяти. Понимание его работы помогает писать оптимизированный код, избегать утечек (например, удерживая ссылки в статических полях) и анализировать логи GC в Android Studio Profiler. Современные реализации в ART минимизируют его недостатки, сохраняя отзывчивость приложений.