Блог

Я пытаюсь реализовать небольшой скриптовый язык и собирался решить, какой алгоритм сборки мусора соответствует моим преимуществам. Я выбрал Mark amp; 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 amp; Sweep — это алгоритм сборки мусора, и я думал, что эти переменные теперь являются моим мусором. Функция завершила свою работу, и она должна вернуть выделенную память системе.

Я попробовал следующее, каждый объект содержит бит метки, и после создания бит метки устанавливается в 0. Когда программа отправляет объект, который удерживается переменной, она преобразует его отметку в 1, и ошибка free не возникает, потому что все в программе знают, что у него есть владелец. До сих пор этот подход работал так хорошо. Но если у меня много переменных, как в примере, как я могу удалить несколько указателей?

Здесь мое предположение состояло в том, чтобы сначала разорвать право собственности между x и его объектом. Затем попросите каждую переменную пометить свои объекты (и если объект является кортежем, то он рекурсивно устанавливает бит метки своих объектов равным 1). Теперь (1,2, …) бит метки объекта устанавливается равным 1 с помощью переменной ‘a’; Я могу попытаться освободить его, но программа не позволяет. Если я сделаю это для каждой переменной в моей таблице, сложность будет выглядеть огромной (у меня есть фаза пометки и развертки для каждого объекта).

Мой вопрос в том, прав ли я относительно алгоритма разметки и развертки? Являются ли корни моими переменными? Как я могу удалить несколько указателей и даже циклические ссылки?

Для разметки и развертки вам необходимо иметь возможность сканировать все выделенные объекты с одной стороны и все доступные объекты с другой.

• Предполагая, что бит метки чист для всех выделенных объектов, просканируйте все объекты, доступные из корневых переменных. Когда объект найден, если он уже отмечен, пропустите его, в противном случае пометьте его и рекурсивно перечислите объекты, на которые он указывает. Этот этап сложный, потому что эта рекурсия может зайти слишком глубоко, поэтому необходимы более продуманные подходы, чем обычная рекурсия.

• Как только все доступные объекты будут отмечены, просканируйте все выделенные объекты: для каждого объекта, если он отмечен, снимите пометку, в противном случае он недоступен, поэтому соберите его (т. Е. сделайте его доступным для перераспределения или освободите его).

В конце фазы развертки все выделенные объекты не помечены, поэтому предположение остается в силе. Немного более эффективная реализация чередовала бы два состояния, избегая необходимости очищать бит метки для достижимых объектов, тем самым уменьшая пропускную способность памяти, требуемую на этапе развертки.

Когда вы изменяете ссылки на объекты в ходе обычной работы ваших программ, вам не нужно делать ничего особенного: просто сохраните адрес новой ссылки.

Чтобы эффективно удалять объекты, на которые ссылаются ваши глобальные переменные, вы должны просто заставить эти переменные указывать на null или какой-либо другой объект.

Преимущества разметки и развертки заключаются в относительной простоте алгоритма и способности собирать сложные структуры с помощью циклов. Недостатком является время, затрачиваемое на режим остановки мира, особенно в многопоточных приложениях и приложениях реального времени или даже интерактивных с пользователем. Были найдены более продвинутые методы для решения этих проблем, но их реализация может быть очень сложной.