Введение к работе
Актуальность темы
Программные системы, в которых используется динамически выделяемая память, нуждаются в ее освобождении. К таким системам можно отнести большинство реализаций современных языков программирования, некоторые распределенные базы данных и многое другое. При явном, «ручном» освобождении памяти, возникают хорошо известные трудности. Преждевременное удаление объектов ведет к образованию так называемых «висячих указателей» (dangling pointers), а неосвобождение памяти из-под неиспользуемых объектов вызывает «утечки памяти» (memory leaks). По этой причине еще в 60-ые годы прошлого века начали появляться системы автоматического управления памятью, получившие название сборщиков мусора (Garbage collectors или GC).
В настоящее время для большинства современных языков программирования существуют автоматические сборщики мусора. В языках, в которых отсутствуют указатели и прямой доступ к памяти, таких как Java, Lisp и Python, сборщик мусора обычно встроен в систему поддержки времени исполнения. В высокопроизводительных языках, таких как С и СИ—Ь, он, как правило, реализуется либо в виде внешней библиотеки с использованием консерванивного сборщика мусора, либо при активном участии программиста.
Ручное управление памятью существенно усложнятся при переходе к распределенной вычислительной системе, поскольку в таких условиях один объект может использоваться совместно несколькими процессорами. Как следствие, большой практический интерес представляет использование автоматического сбора мусора в распределенной среде. При этом на системы управления памятью накладываются дополнительные ограничения. К наиболее важным из них можно отнести перечисленные ниже.
Количество и объем сообщений, посылаемых GC, не должно оказывать существенного влияния на работу приложения. По возможно-
сти, при использовании GC должны отсутствовать синхронизации между всеми узлами распределенной системы, что особенно актуально для систем с медленными сетевыми каналами.
Во многих случаях от системы автоматического сбора мусора требуют устойчивости к частичным сбоям (fault-tolerance), таким как аварийный останов узлов, разрыв сетевых соединений, а также появление ошибок в пересылаемых сообщениях.
Производительность сборщика мусора не должна существенно ухудшаться при увеличении количества узлов в распределенной системе. Масштабируемость особенно важна для крупных распределенных систем, построенных по технологии GRID, поскольку с помощью такой технологии можно объединять большое количество машин в единую систему — «виртуальную организацию» (термин, принятый в GRID).
Накладываемые требования существенно усложняют решение задачи сбора мусора. Сборщик мусора, работающий на одном узле, невозможно применить без изменений в распределенной среде, поскольку это требует синхронизации всех узлов распределенной системы. Такой подход немасштабируем в силу того, что время на синхронизацию растет при увеличении количества узлов. Отмеченные обстоятельства привели к тому, что к настоящему времени разработано достаточно много алгоритмов сбора мусора в распределенной среде, которые могут работать без синхронизации. Вместе с тем, несмотря на большое количество работ по этой теме, многие ее аспекты остаются недостаточно изученными, особенно если рассматривать вопросы практического применения. Системы, в которых используются сборщики мусора, сильно отличаются друг от друга в плане технических возможностей, предоставляемых сборщикам. По этой причине создание системы сбора мусора зачастую требует решения ряда математических, алгоритмических и технических задач, обусловленных требованиями целевой системы.
Достаточно широким классом систем, в которых возникает задача сбора мусора, являются средства создания параллельных и распределенных программ. Как правило, реализации семантики параллельных языков программирования, используемых в такого рода средствах, исключает возможность ручной сборки мусора, вследствие чего и возникает эта задача.
Одним из таких средств является система автоматизированного динамического распараллеливания NewTS, которая призвана в большей степени, чем аналоги, быть приспособленной к работе в гетерогенной среде. Система NewTS основана на использовании идей Т-подхода. Ключевыми моментами системы являются следующие:
программы для NewTS разрабатываются на традиционных высокопроизводительных языках (С и Сн—ь);
распараллеливание обеспечивается небольшим количеством модификаторов (атрибутов функций и переменных), обрабатываемых на этапе трансляции исходного кода;
ускорение достигается путем параллельного исполнения функций программы.
В первых версиях NewTS использовалась система сбора мусора, основанная на использовании весового счетчика ссылок. Она обладала рядом недостатков. В частности, в ней копирование ссылок было не «атомарным», что могло вызывать приостановку работы вычислительного приложения (при этом снижался коэффициент распараллеливания); отсутствовала возможность сбора циклического мусора, система не была устойчивой к сетевым сбоям и аварийному отключению узлов. Поскольку сборщик мусора является одним из основных компонентов системы, его недостатки существенно уменьшают класс задач, эффективно распараллеливаемых с помощью NewTS. По этой причине разработка эффективного сборщика мусора для NewTS является крайне актуальной задачей.
Цель и задачи работы
Целью диссертационной работы является исследование и разработка механизмов автоматического управления памятью в распределенных системах. В качестве системы, на которой апробируются разработанные алгоритмы, была выбрана система автоматизированного динамического распараллеливания NewTS.
Для достижения этой цели поставлены следующие задачи:
разработка математической модели управления распределенными объектами; описание алгоритмов сбора мусора в рамках этой модели, доказательство их корректности;
разработка подсистемы сбора ациклического мусора, обеспечивающая «атомарное» копирование ссылок;
разработка и реализация системы сбора циклического мусора, способной работать в больших вычислительных комплексах.
Научная новизна работы
Научной новизной обладают следующие результаты диссертационной работы.
Предложена математическая модель системы управления распределенными ссылками, описывающая работу ациклического сборщика мусора, обеспечивающего «атомарное» копирование ссылок. Доказана корректность представленного в модели алгоритма.
Предложен комбинированный метод сбора циклического мусора, не требующий останова пользовательского приложения и синхронизации при доступе к ссылкам.
Практическая значимость
Созданная программная реализация системы сбора ациклического мусора в настоящее время используется в системе NewTS как основной метод
управления распределенными ссылками. Она показала свою работоспособность как на модельных примерах, так и в практических задачах, реализованных для NewTS. В их числе: программный комплекс Vortex, обсчитывающий обтекание твердых тел потоком жидкости; приложения rt и PovRay, используемые для построения изображений методом трассировки лучей; программа анализа и индексирования текстовых документов, используемая в автоматизированной системе информационной обработки (АСИО), разработанной в МГУ им. М.В. Ломоносова. Разработанные механизмы опробованы на ряде модельных программ, в числе которых решение задачи N тел методом Барнса-Хата, решение задачи поиска подграфа в графе с помеченными ребрами.
Доклады и публикации
Основные положения работы докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing Week'05 (г. Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на семинаре «Проблемы современных информационно-вычислительных систем» в МГУ им. М.В. Ломоносова под руководством д.ф.-м.н., проф. В.А. Васе-нина.
По материалам диссертации опубликовано семь работ.
Структура и объем диссертации
