Конференции ИВТ СО РАН

V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям с участием иностранных ученых

1-3 ноября, г. Новосибирск, Россия

Тезисы докладов

Информационные технологии

Распараллеливание размечающего алгоритма сборки мусора для SMP-архитектур

Марков А.Н.

Институт Систем Информатики им. А.П.Ершова (Новосибирск)

Во многих современных языках и системах программирования задача освобождения неиспользуемой памяти перекладывается с плеч программиста на создателей компиляторов и/или сред исполнения. Автоматическое освобождение памяти получило название сборка мусора (garbage collection). Большинство алгоритмов сборки мусора останавливают работу всей программы (stop-the-world), таким образом от времени работы сборки мусора может зависеть время работы всего приложения. Заметим, что практически все алгоритмы сборки мусора являются последовательными по своей сути. В то же время, широкое распространение получают мультипроцессорные системы, имеющие SMP-архитектуру, т. е. состоящие из нескольких равноправных процессоров с общей памятью. Цель этой работы - повысить эффективность одного из алгоритмов сборки мусора за счет его распараллеливания.

Данная работа посвящена распараллеливанию размечающего (mark-sweep) алгоритма сборки мусора. Остановимся подробнее на оригинальном, последовательном размечающем алгоритме сборки мусора. Сборка мусора состоит из двух стадий: маркировка, т.е разметка графа объектов (начальная маркировка, замыкание) и выметание, т.е освобождение неиспользуемых объектов. В приложении выделяется набор корневых объектов (roots), таких как глобальные переменные, локальные переменные, размещенные на стеках всех работающих потоков. Начальная маркировка заключается в том, что помечаются все корневые объекты. Замыкание заключается в том, что рекурсивно помечаются объекты, доступные из уже помеченных. Таким образом все объекты, доступные от корневых (объекты, к которым приложение может обращаться) будут помечены. На стадии выметания производится сканирование всех объектов. Память, занятая непомеченными объектами, освобождается.

Параллельный размечающий алгоритм состоит из той же последовательности фаз, однако каждая из его фаз распараллеливается на несколько потоков. Для балансировки нагрузки между потоками используется принцип заимствования заданий (work stealing). Для начальной маркировки набор корневых объектов делится между потоками. После начальной маркировки каждый поток производит замыкание. Пометка объекта может осуществляться либо атомарной операцией, либо производится выделенным потоком. Для распараллеливания выметания вся область памяти делится на некоторое количество регионов, каждый поток выметает свой регион.

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]