Что такое простой алгоритм сборки мусора для экспериментов с простым интерпретатором?

Я экспериментировал с дизайном языка программирования и пришел к необходимости реализовать систему сборки мусора. Теперь первое, что пришло в голову, это подсчет ссылок, но это не будет обрабатывать циклы ссылок. Большинство страниц, на которые я натыкаюсь при поиске алгоритмов, представляют собой ссылки на настройку сборщиков мусора в существующих языках, таких как Java. Когда я нахожу что-либо, описывающее конкретные алгоритмы, мне не хватает деталей для реализации. Например, большинство описаний включают «когда вашей программе не хватает памяти...", что вряд ли произойдет в ближайшее время в 4-гигабайтной системе с большим количеством подкачки. Так что я ищу несколько руководств с хорошими деталями реализации, такими как настройка, когда запускать сборщик мусора (т.е. собирать после X выделений памяти или каждые Y минут и т. д.)

Чтобы дать еще пару подробностей о том, что я пытаюсь сделать, я начну с написания основанного на стеке интерпретатора, похожего на Postscript, и моей следующей попыткой будет, вероятно, язык S-выражений, основанный на одном из диалектов Лиспа.Я реализую на прямом C. Моя цель - как самообразование, так и документирование различных этапов в виде "как разработать и написать интерпретатор " учебник.

Что касается того, что я сделал до сих пор, я написал простой интерпретатор, который реализует императивный язык в стиле C, который анализируется и обрабатывается виртуальной машиной в стиле стековой машины (см. lang2e.sourceforge.net) , Но этот язык не выделяет новую память при входе в какую-либо функцию и не имеет никакого указателя типы данных, поэтому в то время не было необходимости в каком-либо расширенном управлении памятью. Для моего следующего проекта я думаю начать с подсчета ссылок для объектов без указателя (целые числа, строки и т. д.), а затем отслеживать любой объект типа указателя (который может генерировать циклические ссылки) в отдельном пуле памяти. . Затем всякий раз, когда пул увеличивается более чем на X единиц распределения по сравнению с тем, что было в конце предыдущего цикла сборки мусора, снова запускайте сборщик.

Мои требования заключаются в том, чтобы он не был слишком неэффективным, но при этом его было легко реализовать и четко документировать (помните, я хочу превратить его в документ или книгу, чтобы другие могли следовать ему). Алгоритм, который у меня сейчас есть, — это трехцветная маркировка, но похоже, что сборщик поколений был бы немного лучше, но его сложнее задокументировать и понять. Поэтому я ищу четкий справочный материал (желательно доступный в Интернете), который включает достаточно деталей реализации, чтобы начать.