Управление памятью в системах автоматизированного распараллеливания программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Конев, Илья Михайлович

• Конев, Илья Михайлович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Конев, Илья Михайлович

Введение

Актуальность темы.

Цель и задачи работы.

Основные результаты работы

Научная новизна работы.

Практическая значимость

Доклады и публикации.

Структура и объем диссертации.

Краткое содержание работы.

1 Автоматическое управление памятью в Т-системе

1.1 Т-система как подход к распараллеливанию программ.

1.2 Распределенные ссылки и работа с ним в Т-системе

1.3 Недостатки подсистемы работы с распределенными ссылками в первых версиях NewTS.

1.4 Выводы.

2 Основные методики автоматического управления памятью

2.1 Основные понятия.

2.2 Основные алгоритмы для последовательных систем

2.2.1 Подсчет ссылок (reference counting).

2.2.2 Алгоритмы пометки и очистки (mark-and-sweep collection)

2.2.3 Копирующие коллекторы (copying collection)

2.2.4 Выводы.

2.3 Автоматическое управление памятью в распределенных системах . 34 2.3.1 Распределенный подсчет ссылок.

2.3.2 Распределенные трассирующие алгоритмы.

2.3.3 Устойчивость к частичным сбоям в распределенной системе

2.3.4 Выводы.

2.4 Управление памятью в средствах параллельного программирования

2.5 Особенности управления памятью в NewTS.

3 Сборщик ациклического мусора

3.1 Базовый алгоритм для сбора ациклического мусора

3.2 Математическая модель системы распределенных объектов.

3.2.1 Основные понятия.

3.2.2 Модель подсчета ссылок.

3.2.3 Корректность модели с подсчетом ссылок.

3.2.4 Удаление недостижимых объектов в системе с подсчетом ссылок

3.3 Оптимизации системы подсчета ссылок.

3.3.1 Преобразование ссылок при передаче данных.

3.4 Реализация сборщика ациклического мусора.

3.5 Практические испытания.

3.5.1 Тестирование в однопроцессорной системе.

3.5.2 Тестирование в многопроцессорной системе.

3.6 Выводы.

4 Сборщик циклического мусора

4.1 Алгоритм сбора циклического мусора.

4.1.1 Сбор циклического мусора в остановленной системе.

4.1.2 Имитация останова системы без синхронизаций.

4.1.3 Построение корневого множества и обход графа

4.2 Особенности программной реализации алгоритма сбора циклического мусора.

4.2.1 Создание копии вычислительного графа.

4.2.2 Определение корневого множества.

4.2.3 Распределенный обход вычислительного графа (тагк-фаза)

4.2.4 Удаление недостижимых клеток (sweep-фаза).

4.3 Практические испытания.

4.4 Выводы.

Введение диссертации (часть автореферата) на тему «Управление памятью в системах автоматизированного распараллеливания программ»

Актуальность темы

Программные системы, в которых используется динамически выделяемая память, нуждаются в ее освобождении. К таким системам можно отнести большинство реализаций современных языков программирования, некоторые распределенные базы данных и многое другое. При явном, «ручном» освобождении памяти возникают хорошо известные трудности. Преждевременное удаление объектов ведет к образованию так называемых «висячих указателей» (dangling pointers), а неосвобождение памяти из-под неиспользуемых объектов вызывает «утечки памяти» (memory leaks). По этой причине еще в 60-ые годы прошлого века начали появляться системы автоматического управления памятью, получившие название систем сбора мусора (garbage collectors или GC).

В настоящее время для большинства современных языков программирования существуют автоматические сборщики мусора. В языках, в которых отсутствуют указатели и прямой доступ к памяти, таких как Java, Lisp и Python, сборщик мусора обычно встроен в систему поддержки времени исполнения. В высокопроизводительных языках, таких как С и С++, он, как правило, реализуется в виде внешней библиотеки и, как следствие, не требует специальной поддержки со стороны компилятора или средств поддержки времени исполнения (runtime).

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

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

• Во многих случаях от системы автоматического сбора мусора требуют высокой степени устойчивости к частичным сбоям (fault-tolerance), таким как аварийный останов узлов, разрыв сетевых соединений, а также появление ошибок в пересылаемых сообщениях.

• Производительность сборщика мусора не должна существенно ухудшаться при увеличении количества узлов в распределенной системе. Масштабируемость особенно важна для крупных распределенных систем, построенных по технологиям GRID [38], поскольку с помощью такой технологии можно объединять большое количество машин в единую систему — «виртуальную организацию» (в терминологии, принятой в GRID).

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

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

Одним из таких средств является система автоматизированного динамического распараллеливания NewTS [4, б, 8], которая призвана в большей степени, чем аналоги, быть приспособленной к работе в гетерогенной среде. Система NewTS основана на использовании идей Т-подхода. Ключевыми моментами системы являются следующие:

• программы для NewTS разрабатываются на традиционных высокопроизоводи-тельных языках (С и С++);

• распараллеливание обеспечивается небольшим количеством модификаторов (атрибутов функций и переменных), обрабатываемых на этапе трансляции исходного кода;

• ускорение достигается путем параллельного исполнения функций программы.

В первых версиях NewTS использовалась система сбора мусора, основанная на использовании весового счетчика ссылок. Она обладала рядом недостатков. В частности, в ней копирование ссылок было не «атомарным», что могло вызывать приостановку работы вычислительного приложения (при этом снижался коэффициент распараллеливания); отсутствовала возможность сбора циклического мусора, система не была устойчивой к сетевым сбоям и аварийному отключению узлов. Поскольку сборщик мусора является одним из основных компонентов системы, его недостатки существенно уменьшают класс задач, эффективно распараллеливаемых с помощью NewTS. По этой причине разработка эффективного сборщика мусора для NewTS является актуальной задачей.

Цель и задачи работы

Целью диссертационной работы является исследование и разработка механизмов автоматического управления памятью в распределенных системах. В качестве системы, на которой апробируются разработанные алгоритмы, была выбрана система автоматизированного динамического распараллеливания NewTS [4, б, 8].

Для достижения этой цели поставлены следующие задачи:

1. разработка математической модели управления распределенными объектами; описание алгоритмов сбора мусора в рамках этой модели, доказательство их корректности;

2. разработка подсистемы сбора ациклического мусора, обеспечивающая «атомарное» копирование ссылок;

3. разработка и реализация системы сбора циклического мусора, способной эффективно работать в больших вычислительных комплексах.

Основные результаты работы

В рамках диссертационной работы получены следующие результаты:

1. построена математическая модель управления распределенными объектами;

2. разработан алгоритм сбора ациклического мусора, обеспечивающий «атомарное» копирование ссылок;

3. доказана корректность разработанного алгоритма в рамках построенной модели распределенных объектов;

4. разработанный алгоритм реализован в системе автоматизированного распараллеливания NewTS;

5. разработан алгоритм сбора циклического мусора, позволяющий обеспечить параллельную работу распределенного приложения и сборщика мусора;

6. на его основе реализована система освобождения неиспользуемых ресурсов (циклического мусора) для ядра NewTS.

Научная новизна работы

Научной новизной обладают следующие результаты диссертационной работы.

• Предложена математическая модель системы управления распределенными ссылками, описывающая работу ациклического сборщика мусора, обеспечивающего «атомарное» копирование ссылок. Доказана корректность представленного в модели алгоритма.

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

Практическая значимость

Созданная программная реализация системы сбора ациклического мусора в настоящее время используется в системе NewTS как основной метод управления распределенными ссылками. Она показала свою работоспособность как на модельных примерах, так и в практических задачах, реализованных для NewTS. В их числе: программный комплекс Vortex, обсчитывающий обтекание твердых тел потоком жидкости [9]; приложения rt [1] и PovRay [72], используемые для построения изображений методом трассировки лучей; программа анализа и индексирования текстовых документов, для текущей версии автоматизированной системы информационной обработки (АСИО [2]), разработанной в МГУ им. М. В. Ломоносова. Разработанные механизмы опробованы на ряде модельных программ, в числе которых решение задачи N тел методом Барнса-Хата, решение задачи поиска подграфа в графе с помеченными ребрами.

Доклады и публикации

Основные положения работы докладывались на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года) на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing Week'05 (г. Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на семинаре «Проблемы современных информационно-вычислительных систем» в МГУ им. М.В. Ломоносова под руководством д.ф.-м.н., проф. В.А. Васенина.

По материалам диссертации опубликовано восемь работ [15, 16, 8, 13, 7, 12, 11, 14].

Структура и объем диссертации

Работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации — 128 страниц. Список литературы содержит 85 наименований.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Конев, Илья Михайлович

4.4 Выводы

В данной главе представлен алгоритм сбора циклического мусора, основанный на использовании комбинации подсчета ссылок и mark-sweep алгоритма. Разработанный алгоритм позволяет обеспечить сбор циклического мусора без синхронизации узлов и необходимости остановки мутаторов. Сбор мусора может производиться в любом заранее заданном множестве объектов. Такая функциональность является принципиально новой для NewTS и позволяет расширить класс распараллеливаемых программ.

Заключение

В диссертационной работе получены следующие результаты.

• Построена математическая модель управления распределенными объектами. В рамках модели предложен алгоритм сбора ациклического мусора, обеспечивающий «атомарное» копирование ссылок. Доказана корректность работы этого алгоритма.

• Алгоритм сбора ациклического мусора реализован в программном комплексе NewTS. Результаты тестирования и практические испытания показали соответствие реализации предъявляемым к ней требованиям, эффективность с позиции временных затрат на поддержку операций в ядре системы и создаваемой ею сетевой нагрузки.

• Разработан алгоритм сбора циклического мусора, позволяющий обеспечить параллельную работу распределенного приложения и сборщика мусора.

• Алгоритм сбора циклического мусора реализован в программном комплексе NewTS. Корректность функционирования и работоспособность алгоритма подтверждены результатами его тестирования на модельных приложениях.

Список литературы диссертационного исследования кандидат физико-математических наук Конев, Илья Михайлович, 2007 год

1. Афонин С. А., Козицын А. С., Титов А. В. Автоматизированная система обработки информации в интересах обеспечения безопасности критически важных объектов // Проблемы безопасности и противодействия терроризму. — МЦНМО, 2006. — С. 383-400.

2. Васепин В. А., Водомеров А. Н. Формальная модель системы автоматизированного распараллеливания программ // Программирование. — 2007. — № 4.

3. Васенин В. А., Водомеров А. Н., Инюхин А. В. Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные Технологии. — 2007. — № 5. — 32 с.

4. Васенин В. А., Роганов В. A. GRACE: распределенные приложения в интернет // Открытые системы. — 2001. — № 5. — С. 29-33.

5. Водомеров А. Н. Методы и средства автоматизированного распараллеливания приложений в распределенной среде: Дис. .канд. физ.-мат. наук: 05.13.11 / МГУ им. М. В. Ломоносова. — Москва, 2007. — 144 с.

6. Конев И. М. Механизмы организации ссылок в открытой Т-системе // Тез. докл. науч. конф. «Ломоносовские чтения» (18-28 апреля, МГУ им. Ломоносова, Москва). — М.: 2005. С. 122-123.

7. Конев И. М. К созданию системы автоматического сбора мусора в новой версии Т-системы // Тез. докл. науч. конф. «Ломоносовские чтения» (17-27 апреля, МГУ им. Ломоносова, Москва). — М.: Изд-во Московского университета, 2006,— С. 89-90.

8. Конев И. М. О некоторых способах организации рефлексии объектов при разработке параллельных программ // Тез. докл. науч. конф. «Ломоносовские чтения» (16-25 апреля, МГУ им. Ломоносова, Москва). — М.: 2007.

9. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Информационные технологии. — 2007. — № 10. — С. 71-79.

10. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Приложение к журналу «Информационные технологии». — № 10. М.: Изд-во «Новые технологии», 2007. 32 с.

11. Моделирование нестационарных нагрузок при движении тел в вязкой жидкости: Отчет №4775 / С. В. Гувернюк, Г. Я. Дынникова, П. Р. Андронов и др.; Ин-т механики МГУ. — М., 2005.- 93 с.

12. Т-система с открытой архитектурой / С. М. Абрамов, А. И. Адамович, А. В. Инюхин и др. // Тр. Междунар. науч. конф. «Суперкомпьютерные системы и их применение SSA'2004» (26-28 октября 2004, г. Минск).- Минск: ОИПИ НАН Беларуси, 2004. — С. 18-22.

13. Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы, — П.: Питер, 2003. 880 с.

14. Abdullahi S. E.-Y. Empirical Studies of Distributed Garbage Collection: Ph.D. thesis / Department of Computer Science, Queen Mary and Westfield College, University of London. — UK, London, 1996. 318 pp.

15. Baden S. B. Low-Overhead Storage Reclamation in the Smalltalk-80 Virtual Machine // Smalltalk-80: Bits of History, Words of Advice. — Addison-Wesley Publishing Company, 1983.-Pp. 331-342.

16. Baker H. G. The treadmill: real-time garbage collection without motion sickness // SIGPLAN Not. 1992. - Vol. 27, no. 3. - Pp. 66-70.

17. Bennett J. K. The design and implementation of distributed Smalltalk // OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications. New York, NY, USA: ACM Press, 1987. - Pp. 318-330.

18. Bevan D. I. Distributed garbage collection using reference counting // Proceedings of the Parallel Architectures and Languages Europe, Volume I,— London, UK: Springer-Verlag, 1987.-Pp. 176-187.

19. Boehm H.-J. Space efficient conservative garbage collection // PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation. — New York, NY, USA: ACM, 1993. Pp. 197-206.

20. Boehm H.-J., Demers A. J., Shenker S. Mostly parallel garbage collection // Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation (PLDI). —Vol. 26.- 1991.-Pp. 157-164. citeseer.ist.psu.edu/boehm91mostIy.html.

21. Brownbridge D. R. Cyclic reference counting for combinator machines // Proc. of a conference on Functional programming languages and computer architecture. — New York, NY, USA: Springer-Verlag New York, Inc., 1985. Pp. 273-288.

22. The Charm Parallel Programming Language and System: Part I Description of Language Features / L. Kal'e, B. Ramkumar, A. Sinha, A. Gursoy; University of Illinois, University of Iowa. - Urbana, Iowa City, USA, 1995. - 27 pp.

23. Cilk: An efficient multithreaded runtime system: Tech. rep. / R. D. Blumofe, C. F. Joerg, В. C. Kuszmaul et al. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1996.

24. Cohen J., Trilling L. Remarks on garbage collection using a two level store // Tidskrift for Informations Behandeling, Denmark. — 1967. — Vol. 7. — Pp. 22-30.

25. Collins G. E. A method for overlapping and erasure of lists // Commun. ACM. — 1960.— Vol. 3, no. 12. Pp. 655-657.

26. Define F. К. H. A., bins R. D. Distributed cyclic reference counting // Canada-France Conference on Parallel and Distributed Computing. — 1994. — Pp. 95-100. citeseer.ist.psu.edu/dehne94distributed.html.

27. Dickman P. Optimizing Weighted Reference Counts for Scalable Fault-Tolerant Distributed Object-Support Systems. — Submitted for HICSS 26.

28. El-Habbash A., Horn C., Harris N. Garbage collection in an object oriented distributed environment // Proceedings of the ECOOP/OOPSLA Workshop on Garbage Collection.— Ottawa, Canada: 1990. citeseer.ist.psu.edu/338568.html.

29. Fenichel R. R., Yochelson J. C. A lisp garbage-collector for virtual-memory computer systems // Commun. ACM. 1969. - Vol. 12, no. 11.- Pp. 611-612.

30. Frigo M., Leiserson С. E., Randall К. H. The implementation of the Cilk-5 multithreaded language // Proc. of the ACM SIGPLAN 1998 conference on Programming language design and implementation. New York, NY, USA: ACM Press, 1998. - Pp. 212-223.

31. Fuchs M. Garbage collection on an open network // IWMM '95: Proceedings of the International Workshop on Memory Management. — London, UK: Springer-Verlag, 1995. — Pp. 251-265.

32. GNU prof Электронный ресурс. — Электрон, текст, дан. — Б. изд., 2007. — Режим доступа: http://www.gnu.Org/software/binutils/manual/gprof-2.9.l/htmlmono/gprof.html, свободный. — Электрон, текст, док.

33. Grimshaw A. S. An introduction to parallel object-oriented programming with mentat: Tech. rep. Charlottesville, VA, USA: 1991.

34. GUM: a portable parallel implementation of Haskell / P. W. Trinder, K. Hammond, J. J. S. Mattson et al. // Proc. of the ACM SIGPLAN 1996 conference on Programming language design and implementation. — N.Y.: ACM Press, 1996. — Pp. 79-88.

35. Halstead R. H. Implementation of Multilisp: Lisp on Multiprocessor // Proc. of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, United States. — N.Y.: ACM Press, 1984,- Pp. 9-17.

36. Henry G. Baker J. List processing in real time on a serial computer // Commun. ACM.— 1978. Vol. 21, no. 4. - Pp. 280-294.

37. Hudak P., Keller R. M. Garbage collection and task deletion in distributed applicative processing systems // LFP '82: Proceedings of the 1982 ACM symposium on LISP and functional programming. New York, NY, USA: ACM Press, 1982. - Pp. 168-178.

38. Hughes J. A distributed garbage collection algorithm // Proc. of a conference on Functional programming languages and computer architecture. — New York, NY, USA: Springer-Verlag New York, Inc., 1985,- Pp. 256-272.

39. Jones R. E., Lins R. D. Cyclic weighted reference counting without delay // Parallel Architectures and Languages Europe. — 1993. — Pp. 712-715. citeseer.ist.psu.edu/jones92cyclic.html.

40. Keller R., Nguyen V. PACX-MPI Project Homepage Электронный ресурс. — Электрон, текст, дан. — 2003. — Режим доступа: http://www3.niu.edu/mpi/, свободный. — Электрон, текст, док.

41. Knizhnik К. Reflection Package for С++ Электронный ресурс.— Электрон. текстовые дан. — Б. изд., 2004. — Режим доступа: http://www.garret.ru/~knizhnik/cppreflection/docs/reflect.html, свободный. — Электрон, версия печ. публикации.

42. Kranz D. A., R. Н. Halstead J., Mohr Е. Mul-t: a high-performance parallel lisp // PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation. New York, NY, USA: ACM Press, 1989. - Pp. 81-90.

43. Lang В., Dupont F. Incremental incrementally compacting garbage collection // SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniques. — New York, NY, USA: ACM, 1987. Pp. 253-263.

44. Lermen C.-W., Maurer D. A protocol for distributed reference counting // LFP '86: Proceedings of the 1986 ACM conference on LISP and functional programming. — New York, NY, USA: ACM Press, 1986. Pp. 343-350.

45. Lieberman H., Hewitt C. A real-time garbage collector based on the lifetimes of objects // Commun. ACM. 1983. - Vol. 26, no. 6. - Pp. 419-429.

46. Lins R. D. Cyclic reference counting with lazy mark-scan // Information Processing Letters. — 1990.-Vol. 44, no. 4.-Pp. 215-220. citeseer.ist.psu.edu/lins90cyclic.html.

47. Maheshwari U. Distributed garbage collection in a client-server, transaction, persistent object system: Tech. rep. — Cambridge, MA, USA: 1993.

48. Maheshwari U., Liskov B. Collecting distributed garbage cycles by back tracing // PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing. New York, NY, USA: ACM, 1997. - Pp. 239-248.

49. Marti J. Rlisp '88: An Evolutionary Approach to Program Design and Reuse.— World Scientific Pub Co Inc, 1988. 257 pp.

50. McCarthy J. Recursive functions of symbolic expressions and their computation by machine, part i // Commun. ACM.- I960. Vol. 3, no. 4.- Pp. 184-195.

51. Miranda E. Brouhaha — a portable Smalltalk interpreter // OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications. — New York, NY, USA: ACM Press, 1987. Pp. 354-365.

52. Mohamed-Ali K. A. Object-Oriented Storage Management and Garbage Collection in Distributed Processing Systems: Academic dissertation / Royal Institute of Technology, Dept of Computer Systems. — Stockholm, Sweden, 1984.

53. MPI: A Message-Passing Interface Standard Электронный ресурс.— Электрон, текст, дан.— Knoxville, Tennessee: University of Tennessee, 1995.— Режим доступа: http://www.mpi-forum.org/docs/mpi-ll.ps, свободный. — Электрон, версия печ. публикации.

54. MPICH-G2 Электронный ресурс. — Электрон, текст, дан, — 2005,— Режим доступа: http://www3.niu.edu/mpi/, свободный. — Электрон, текст, док.

55. Nori А. К. A Storage Reclamation Scheme for Applicative Multiprocessor Systems: Ph.D. thesis / University of Utah. — Salt Lake City, Utah, 1979.

56. On-the-fly garbage collection: An exercise in cooperation / E. W. Dijkstra, L. Lamport, A. J. Martin et al. // Commun. ACM. 1978. - Vol. 21, no. 11. - Pp. 966-975.

57. OProffie Электронный ресурс.— Электрон, текст, дан.— Режим доступа: http://oprofile.sourceforge.net, свободный. — Электрон, текст, док.

58. The Persistence of Vision Raytracer Электронный ресурс.— Электрон, текст, дан.— 2007. — Режим доступа: http://www.povray.org/, свободный, — Электрон, текст, док.

59. Randall К. H. Cilk: Efficient Multithreaded Computing: Ph.D. thesis / Massachusetts Institute of Technology. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1998.

60. Richter J. Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework Электронный ресурс.— Электрон, текст, дан, — Б. изд.— Режим доступа: http://msdn.microsoft.com/msdnmag/issues/1100/gci/, свободный. — Электрон, текст, док.

61. Robert Н. Halstead J. Multilisp: a language for concurrent symbolic computation // A CM Trans. Program. Lang. Syst. — 1985. — Vol. 7, no. 4. — Pp. 501-538.

62. Rodriguez-Riviera G., Russo V. Cyclic distributed garbage collection without global synchronization in corba. — 1997. citeseer.ist.psu.edu/95492.html.

63. Rudalics M. Correctness of distributed garbage collection algorithms: Tech. rep. — Johannes Kepler Universitat, Linz, Austria: 1990.

64. Shapiro M., Gruber O., Plainfosse D. A garbage detection protocol for a realistic distributed object-support system: Tech. Rep. 1320: 1990. citeseer.ist.psu.edu/shapiro90garbage.html.

65. Thomas R. E. A data flow architecture with improved asymptotic: Tech. rep. — Cambridge, MA, USA: 1981.

66. Tuning Garbage Collection with the 1.4.2 Javatin. Virtual Machine [Электронный ресурс].— Электрон, текст, дан.— Б. изд., 2007.— Режим доступа: http://java.sun.eom/docs/hotspot/gcl.4.2/, свободный, — Электрон, текст, док.

67. Weizenbaum J. Symmetric list processor // Communications of ACM.— 1963.— Vol. 6, no. 9. Pp. 524-536.

68. Wise D. S., Friedman D. P. The one-bit reference count // BIT Numerical Mathematics. — 1977. Vol. 17, no. 3. - Pp. 351-359.