>> |
No.26498
@node Консервативный сборщик мусора
@subsection Консервативный сборщик мусора
Помимо скрытого типизирования, одна из больших ограничений
реализаций Скимы в плане представлния данных это сборщик мусора.
Сборщик должен проходить каждый существующий объект в куче чтобы
определить какие объекты уже не живы что бы их можно было собрать.
Есть много разных способов для его реализации. Сборщик Гиля построен поверх
библиотеки, Богем-Демер-Вейзеровского консервативного сборщика мусора (БДВ-СМ).
БДВ-СМ "просто работает", по большей части. Но так как интересно, как же эта штука работает,
мы прикладываем сюда верхнеуровневое описание того, что делает БДВ-СМ.
Сборщик мусора имеет две логические фазы: фазу маркировки @dfn{mark}, в
которой перечисляется множество существующих объектов, и фаза @dfn{sweep},
в которой объекты, до которых сборщик не дошел на стадии маркировки, собираются.
Правильное функционирование сборщика зависит от того, сможет ли он обойти все живые объекты.
На стадии маркировки, сборщик сканирует системные глобальные переменные
и локальные переменные на стэке, что бы определить какие объекты
моментально доступны через код на С. Затем он сканирует эти объекты
что бы определить на что ссылаются уже они, и так далее. Сборщик устанавливает
логический бит @dfn{mark bit} на каждый объект, который он находит, так что
каждый объект проходится всего один раз. %!% Как понимаю, что бы не было рекурсии
Когда сборщик не может найти немаркированные объекты, которые
следуют за маркированными, он считает, что все объекты, на которых
нет метки, никогда не будут вызваны из программы (так как нет пути по
которому они могут быть вызваны ни через глобальную, ни через локальную
зону видимости) и поэтому их можно деаллоцировать.
Выше мы не описывали как сборщик определяет локальные и глобальные переменные;
как обычно, тут есть много разных подходов. Обычно, программист должен
поддерживать список указателей на все глобальные переменные, которые отссылаются
в кучу, и другой список, который содержит локальные переменные (существование
которых определенно входом и выходом из каждой функции) для работы сборщика.
Список глобальных переменных обычно не очень трудно поддерживать, потому как они
относительно редки. И напротив, поддерживать список локальных переменных
(по личному опыту автора) является ночным кошмаром разработчика. Поэтому,
БДВ-СМ @dfn{conservative garbage collection}, делающий использование локального
списка переменных ненужным.
Трюк, который используется в консервативном сборщике заключается в том, что
весь С стэк рассматривается просто как кусок памяти, подразумаевая, что
@emph{каждое} слово на нём, стэке, это указатель на кучу.
Поэтому, сборщик маркирует каждый объект, чей адрес лежит где-то на С стэке,
не понимая как это слово следует интерпритировать.
В дополнение к стэку, БДВ-СМ так же сканирует статичные секции с данными.
Это означает, что глобальные значения так же сканируются когда проверяются
все живые объекты Скимы.
Очевидно, что такая система иногда будет оставлять объекты, которые являются мусором,
и которые должны быть освобождены. На практике это не проблема, так как область консервативного
сканирования фиксированна. Ским стэк поддерживается отдельно от Си стэка, и сканируется
точно (в отличии от консервативного подхода). Управляемая СМ куча так же поделена
на части, которые могут содержать указатели (такие как векторы), и части, которые их
содержать не могут (такие как байтвекторы), ограничивая возможность воспринимать
сырое целоые число как ссылку на живой объект.
Все интересующиеся могут ознакомиться с БДВ-СМ на странице @uref{http://www.hboehm.info/gc/},
что бы получить больше информации о консервативных СМ, а так же о реализации
БДВ-СМ в частности.
|