Достижимость объектов кучи от множества корней
Явный граф кучи можно обойти от корней, помечая каждый объект по ссылке один раз и классифицируя выделения памяти, которых не может достичь ни один корень.
Какие выделения памяти должен сохранять диспетчер памяти, когда ссылки образуют граф?
- Представление объектов кучи как идентификаторов с исходящими ссылками
- Трассировка каждого пути, начинающегося из явного множества корней
- Прекращение повторного обхода помеченных объектов при наличии цикла в графе
- Определение недостижимых выделений памяти без их освобождения в этой модели
mark добавляет идентификатор объекта перед переходом к его потомкам. mark-list передает растущее множество помеченных объектов по соседним ссылкам, поэтому объект, достигнутый несколькими путями, появляется один раз. Первая куча оставляет garbage и orphan выделенными, но недостижимыми из корня a.
Вторая куча содержит цикл из a через b и c обратно в a. contains? останавливает повторный обход, а mark-roots начинает второй обход из x. unreachable затем сканирует каждое выделение памяти и классифицирует только dead вне множества помеченных объектов. Этот урок моделирует трассировку и классификацию, а не само освобождение памяти.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает ((a b d c) (garbage orphan)). Вторая возвращает ((a b c x y) (dead)).
В первом запуске проследите путь от корня через b к d перед возвратом к c, затем понаблюдайте, как сканирование кучи отклоняет помеченные идентификаторы. Во втором запуске найдите срабатывание contains?, которое останавливает цикл от c к a, и последующий обход из корня x.
Измените программу и сравните результат.
Добавьте ссылку из orphan в a, сохраняя корень a. Предскажите, станут ли garbage и orphan достижимыми.
Показать подсказку
Достижимость следует по ссылкам наружу от корней. Ссылка из недостижимого объекта в сторону корня не делает этот объект достижимым.