Я пытаюсь реализовать небольшой язык сценариев и собираюсь решить, какой алгоритм сборки мусора соответствует моим преимуществам. Я выбрал Mark & Sweep, но, думаю, неправильно понял концепцию.
Допустим, вызывается произвольная функция, и она создает следующие переменные (возможно, они не имеют имен, но для простоты предположим, что они созданы в этой функции).
f() {
/*f creates following variables*/
x = (1,2,(3,4,(5,6))); //this is tuple
a = x;
y = x[2];
z = y[2];
p = (10,y);
}
В приведенном выше примере все является объектом (целые числа, строки, кортежи, двойные числа и т. Д.), А кортежи содержат указатели на его объекты. Более того, каждый объект живет в куче. Когда функция выходит из области видимости, она должна удалить выделенные переменные. Область действия функции выглядит следующим образом.
+-----+
| |
| x +---------->(1,2,+)
+-----+ ^ |
| v
+-----+ | (3,4,+)
| | | ^ |
| a +-----------+ | v
+-----+ | (5,6)
| ^
+-----+ | |
| | | |
| y +----------------+ |
+-----+ | |
| |
+-----+ | |
| | | |
| z +---------------------+
+-----+ |
|
+-----+ |
| | |
| p +----------->(10,+)
+-----+
Все переменные (a, x, y, z, p) должны быть удалены, но вопрос в том, как? Я знаю, что Mark & Sweep - это алгоритм сборки мусора, и я подумал, что эти переменные теперь мой мусор. Функция завершила свою работу и должна вернуть выделенную память системе.
Я попробовал следующее, каждый объект содержит бит метки, и после создания бит метки устанавливается в 0. Когда программа помещает объект, удерживаемый переменной, она конвертирует свою метку в 1, и не возникает свободных ошибок, потому что все в Программа знает, что у нее есть владелец. Пока все хорошо, этот подход сработал. Но если у меня много переменных, как в примере, как я могу удалить несколько указателей?
Здесь я предположил, что сначала нужно разорвать владение между x и его объектом. Затем произнесите каждую переменную, чтобы пометить свои объекты (и если объект является кортежем, то он устанавливает рекурсивный бит меток для своих объектов в 1). Теперь (1,2, ...) бит метки объекта устанавливается в 1 переменной 'a'; Я могу попытаться освободить его, но программа не позволяет. Если я сделаю это для каждой переменной в моей таблице, сложность будет выглядеть огромной (у меня есть метка и фаза развертки для каждого объекта).
У меня вопрос, я прав насчет алгоритма Mark & Sweep? Корни мои переменные? Как я могу удалить несколько указателей и даже циклические ссылки?