Изучение теории сбора мусора

Прочтите эти документы в порядке. Они находятся в прогрессивном предмете / порядке порядка (не хронологическом).

Список, взятый непосредственно с страницы курса «Управление памятью» профессора Кэтрин Маккинли здесь , где вы найдете ссылки на все статьи.

Я прошел курс в прошлом семестре, поэтому я прочитал все это, и я должен сказать, что я узнал, что я начал изучать!

• Обработка списка в реальном времени на последовательном компьютере , Baker, CACM, 21 (4) 280-294, 1978.
• Алгоритм сжатия нерекурсивного списка , Чейни, CACM, 13 (11): 677–678, 1970.
• Сборщик мусора в реальном времени, основанный на сроках жизни объектов , Либерман и Хьюитт, CACM, 26 (6): 419-44, 1983.
• Утилизация генерации: неразрушающий высокопроизводительный алгоритм восстановления памяти , Ungar, Труды первого симпозиума по программированию программного обеспечения ACM SIGSOFT / SIGPLAN по практическим средам разработки программного обеспечения, 1984, стр. 157-167.
• Простая генерация мусора и быстрое распределение , Appel, Software – практика и опыт 19 (2): 171-183, февраль 1989.
• Сборник мусора на основе возраста , Д. Стефанович, К.С. Маккинли, JEB Moss, Конференция ACM по объектно-ориентированным системам программирования, языкам и приложениям. (OOPSLA), стр. 370–381. Денвер СО, ноябрь 1999 года.
• Старая первая assembly мусора на практике: оценка на виртуальной машине Java , Д. Стефанович, М. Герц, С.М. Блэкберн, К.С. Маккинли и Дж. Б. Мосс, «Производительность системы памяти», Берлин, Германия, стр. 175-184, июнь 2002 г. ,
• Beltway: Знакомство с сборкой мусора Gridlock , SM Blackburn, R. Jones, KS McKinley и JEB Moss, Конференция ACM по программированию и внедрению языка программирования, Берлин, Германия, стр. 153-164, июнь 2002 г.
• Эффективная машинно-независимая процедура сбора мусора в различных структурах списка , Schorr & Waite, CACM, 10 (8): 501–506, 1967.
• Сравнение алгоритмов уплотнения для сбора мусора , Cohen & Nicolau, ACM Transactions на языках программирования и системах (TOPLAS), том 5, выпуск 4, стр. 532-555, октябрь 1983 г.
• MC2: Высокопроизводительная assembly мусора для ограниченных по размеру сред , Sachindran, Berger & Moss, Конференция ACM по объектно-ориентированным системам программирования, Языки и приложения, стр. 81-96, Ванкувер, Британская Колумбия, октябрь 2004 г.
• Immix: сборщик мусора маркировки с эффективностью пространства, быстрой сборкой и работой мутаторов , Blackburn & McKinley, конференция ACM по программированию и внедрению языка программирования, стр.22–32, Тусон, AZ, июнь 2008 г.
• Эффективный инкрементный автоматический сборщик мусора , Deutsch & Bobrow, CACM, 19 (9): 522-526, сентябрь 1976 года.
• Уличный подсчет ссылок: быстрая assembly мусора без ожидания , С.М. Блэкберн и К.С. Маккинли, Труды конференции ACM 2003 SIGPLAN по объектно-ориентированным системам программирования, языкам и приложениям, стр. 344-359, Annehiem, CA, октябрь 2003 г.
• Трассировка цикла: эффективная параллельная коллекция циклов разметки, Frampton & Blackburn, 2009. (В представлении ISMM.)
• Многопроцессорная компактификационная assembly мусора , Guy L. Steele, Jr., CACM 18 (9): 495-508, 1975.
• Сбор мусора на лету: совместная работа , EW Dijkstra, L. Lamport, AJ Martin, CS Scholten и EFM Steffens, Сообщения ACM, 21 (11): 966–975, ноябрь 1978 г.
• Корректно-консервативная выработка алгоритмов сборочной сборки мусора , Вечева, Яхава и Бэкона, Конференция ACM по программированию и разработке языков программирования, Оттава, Онтарио, стр. 341-353, 2006.
• Сборщик мусора в режиме реального времени с низким накладным и последовательным использованием , Бэкон, Чэн и Раджан, симпозиум ACM по принципам языков программирования, Новый Орлеан, Луизиана, стр. 285-298, 2003.
• Налоговые и налоговые: демократическое планирование сбора мусора в реальном времени , Ауэрбах, Бэкон, Чэн, Гроув, Бирон, Грейси, Макклоски, Мичик и Сьямпаконе, Международная конференция ACM по встроенному программному обеспечению, Атланта, Джорджия, стр. 245-254 , 2008.
• Сбор мусора в непригодной среде , Х. Бем и М. Вайзер, Практика и опыт использования программного обеспечения, 18 (9): 807-820, 1988.
• Hoard: масштабируемый модуль памяти для многопоточных приложений , ED Berger, KS McKinley, RD Blumofe и PR Wilson, Девятая международная конференция по архитектурной поддержке языков программирования и операционных систем, Кембридж, Массачусетс, стр. 117-128, ноябрь 2000 г. ,
• Cork: обнаружение утечки динамической памяти для собранных мусором языков , Jump & McKinley, при представлении ACM Transactions на практике и практике использования программного обеспечения, 2009. (Сокращенная версия представлена ​​на конференции ACM по языкам программирования, Ницца, Франция, январь 2009 г.)
• Leak Pruning , Bond & McKinley, Конференция ACM по архитектуре поддержки языков программирования и операционных систем, Вашингтон, округ Колумбия, март 2009 года. (Чтобы появиться.)
• Free-me: статический анализ для индивидуальной рекультивации объектов , Guyer & McKinley, конференция ACM по программированию и разработке языков программирования, Оттава, Канада, стр. 364-375, июнь 2006 г.
• Сбор мусора может быть быстрее, чем распределение стека , Appel, письма для обработки информации 25 (4): 275-279, 17 июня 1987 года.
• Преимущество коллекции мусора: улучшение положения на рынке Хуан, Блэкберн, Маккинли, Мосс, Ван и Чэн, конференция ACM по объектно-ориентированным системам программирования, языкам и приложениям, Ванкувер, Британская Колумбия, стр. 69-80, октябрь 2004 г.
• Демистификация магии: низкоуровневое программирование высокого уровня , Дэниел Фрэмптон, Стивен М. Блэкберн, Перри Ченг, Робин Гарнер, Дэвид П. Гроув, Дж. Элиот Б. Мосс и Сергей Иванович Салишев. Международная конференция ACM по средам виртуального исполнения, Вашингтон, округ Колумбия, март 2009 года. (Чтобы появиться.)
• Мифы и реалии: влияние производительности коллекции мусора , С.М. Блэкберн, П. Ченг и К.С. Маккинли, конференция ACM SIGMETRICS по измерениям и моделированию компьютерных систем, стр. 25–36, Нью-Йорк, Нью-Йорк, июнь 2004 г.
• Единая теория сбора мусора , Бэкон, Ченг и Раджан, Конференция ACM по объектно-ориентированному программированию, системам, языкам и приложениям, Ванкувер, Британская Колумбия, Канада, стр. 50-68, 2004.

Существует целая книга по сборке мусора и неплохая, если я могу добавить:

Ричард Джонс и Рафаэль Линс, garbage collection, Wiley and Sons (1996), ISBN 0471941484

Ричард Джонс также поддерживает хороший сайт, собирающий ресурсы сбора мусора .

Самые ранние compilationи мусора очень читаемы. Вы можете начать с опроса Пола Уилсона «Методы сбора мусора Uniprocessor Garbage» (1992, LNCS, т. 637), а затем погрузиться в оригинальную литературу по темам, которые звучат интересно.

Я хочу изучить теорию сбора мусора. Как мне это сделать?

Я также дабллер, заинтересованный в сборе мусора (до такой степени, что я написал свой собственный сборщик мусора, получивший название HLVM ). Я узнал, прочитав столько исследовательских работ по сбору мусора, сколько мог взять себя в руки и сам сыграл с идеями, как на своей виртуальной машине, так и на написании высокоуровневых симуляций с безопасным хранением.

Очевидный ответ – учебник для компилятора … Вопрос в том, нужно ли изучать лексический анализ, parsing и другие вещи, которые обычно предшествуют сборке мусора в тексте?

Лексический анализ, parsing и прочее не имеют отношения к сбору мусора. Вы можете получить устаревший обзорный garbage collection из книги компилятора, но вам нужно прочитать исследовательские работы, чтобы получить актуальное представление, например, в отношении многоядерности.

Короче говоря, каковы предпосылки для изучения теории сбора мусора?

Вам нужно знать основные теории диаграмм, указатели, стеки, streamи и (если вас интересуют многоstreamовые) примитивы параллелизма низкого уровня, такие как блокировки.

Сбор мусора связан с определением доступности. Когда программа больше не может получить ссылку на значение, потому что это значение становится недоступным, GC может перерабатывать память, значение которой занимает. Достижимость определяется путем перемещения кучи, начиная с набора «глобальных корней» (глобальные переменные и указатели на стеки streamа и в регистры ядра)

Конструкция GC имеет много аспектов, но вы можете начать с четырех основных алгоритмов сбора мусора:

• Марк-и-развертка (Маккарти, 1960)
• Mark-and-compact (Haddon and Waite, 1967)
• Стоп-копия (Чейни, 1970)
• Mark-region (McKinley et al. , 2007)

Возможно, наиболее заметной эволюцией этих основных идей является сборщик мусора, который был стандартным дизайном defacto в течение многих лет.

Мое личное чувство заключается в том, что некоторые из неясных работ по сборке мусора содержат столько же полезной информации, что и я настоятельно рекомендую:

• Беговая дорожка Бейкера (красивый GC в реальном времени).
• VCGC (совершенно другая трехцветная схема маркировки).

Вам также может понравиться изучить три вида барьера для записи (Dijkstra’s, Steele’s и Yuasa’s), а также посмотреть на маркировку карты и вспомнить методы набора.

Затем вам также может понадобиться изучить фактические дизайнерские решения, которые некоторые разработчики выбрали для языковых реализаций, таких как Java и .NET, а также компилятор SML / NJ для стандартного ML, компилятора OCaml, компилятора Glasgow Haskell и других. Различия между принятыми приемами столь же велики, как сходство между ними!

Есть также некоторые большие связанные с тангенсом документы, такие как compilation точных мусора Хендерсона в непринужденной среде . Я использовал эту технику, чтобы избежать необходимости писать стековый ходок для HLVM.

Сайт memorymanagement.org является бесценным ресурсом, в частности глоссарием терминов, связанных с GC.

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

На самом деле, мне очень нравится статья в Википедии в качестве вступительного объяснения со многими хорошими указателями. Определенно одна из лучших статей CS в Википедии.

Глава 9, «Управление памятью», по объектно-ориентированной разработке программного обеспечения, 2-е издание Бертран Майер довольно информативна.

Я бы начал с чтения этой статьи: единой теории сбора мусора, Бэкона, Ченга и Раджана, конференции ACM по объектно-ориентированному программированию, системам, языкам и приложениям, Ванкувер, Британская Колумбия, Канада, стр. 50-68, 2004 ,

Вы также можете взглянуть на Squeak: Open Personal Computing , который охватывает сборщик мусора Squeak Smalltalk, среди других проблем дизайна ST. Вы также должны взглянуть на Squeak – он почти полностью написан на Smalltalk, и все источники, включая GC, свободно доступны и легко изучаются с использованием браузеров Smalltalk.