Я немного изучал сборку мусора, в основном применяемую к серверным приложениям/приложениям реального времени, и начал набрасывать алгоритм, с помощью которого можно было бы иметь асинхронную систему сборки мусора. Поскольку я начинаю эту тему сейчас, поэтому я не очень хорошо разбираюсь в алгоритмах gc, мне было интересно узнать о возможных ловушках такой реализации. Алгоритм очень грубый и со многими неопределенными частями.
Вот как я об этом думал:
- каждый поток имеет собственное пространство кучи для управления и хранит список принадлежащих ему указателей, которые используются другими потоками. При этом сборка мусора работает полностью асинхронно с запущенными потоками, и:
- Фаза 1 начинается с отслеживания корней потоков и маркировки всех достижимых ими объектов. Если мы попадаем в пространство другого потока, мы прекращаем следовать этому указателю и помечаем этот указатель как «используемый» в потоке-владельце.
- после того, как мы пометили все регионы, мы выбираем регион (возможно, с наибольшим количеством мертвых ссылок) и начинаем копировать его живые ссылки на объекты в другое пространство. (это может быть все пространство кучи потоков, но я думаю, что эта операция может быть слишком интенсивной по памяти)
- копирование начинается с установки с помощью CAS флага, указывающего на то, что объект копируется. Любое изменяемое действие, выполняемое над этим конкретным объектом, пока этот флаг установлен, будет вращать блокировку до тех пор, пока новый адрес не будет установлен потоком gc. Когда копирование заканчивается, новый адрес устанавливается на старый, и любая изменяемая ссылка, которая должна быть выполнена на объекте, будет перенаправляться на новый объект.
- после обновления всех ссылок, сделанных на эти указатели с помощью CAS, старое пространство, наконец, освобождается (новые указатели не будут обновлены с неправильным адресом, поскольку каждый мутатор сначала проверяет, изменились ли ссылки)
Вот и все!
Во всяком случае, я очень взволнован возможной реализацией, которая не останавливает мир и использует только быстрые спин-блокировки, которые применяются только к копируемому объекту. Но я хотел бы знать, возможно ли это реализовать, или есть ли возможность где-то иметь висячий указатель, или утечки памяти, или это неэффективно, и т. д. Любая информация, которая будет способствовать этому, будет принята с благодарностью!
Я совсем не уверен в том, как, например. он будет обрабатывать циклические ссылки из разных потоков. Я думаю, что это будет обработано естественным образом, поскольку мы обновляем все указатели опасностей, которые есть в текущем потоке gc'ed. Также может быть какой-то одновременный доступ, который я не рассматривал.
Благодарю вас!
---- РЕДАКТИРОВАТЬ: благодаря вкладу Эрнеста я думаю не об использовании алгоритма копирования, а, возможно, о простой маркировке и развертке. Это потому, что нам нужно будет проверять каждый раз, когда мы обращаемся к переменной объекта, был ли обновлен указатель. Мне кажется, это довольно большие накладные расходы. Не так ли?