Введение к работе
з
Актуальность темы
Используемые в настоящее время вычислительные устройства всё в большей степени являются многоядерными и многопроцессорными, что позволяет разрабатывать для них эффективные параллельные программы и существенно увеличивает производительность целевых систем. Однако проектирование и разработка программ с использованием взаимодействующих потоков, одновременно выполняющих различные действия, является сложной задачей, что приводит к большому количеству ошибок. К самым частым и сложным в обнаружении ошибкам много поточных программ относятся состояния гонки (data races) - несинхронизированные обращения из различных потоков к одному и тому же участку памяти.
Проявление состояний гонки в приложении в значительной степени зависит от чередования потоков, поэтому они возникают недетерминировано, а результаты их воздействия слабо локализуемы и приводят к повреждению глобальных структур данных. При этом, как правило, не происходит немедленного сбоя в работе программы, - ошибка проявляется в дальнейшем, в виде необъяснимых потерь данных и пр. Эта особенность затрудняет обнаружение гонок на этапах тестирования и эксплуатации приложения. По этим причинам существует потребность в специальных подходах и технологиях, которые позволяли бы обнаруживать гонки автоматически.
Методы автоматического обнаружения гонок можно разделить на два основных класса - статические и динамические. Статические методы основаны на анализе исходного кода или исполняемых файлов программы без её запуска. Такой подход обладает рядом существенных преимуществ. Во-первых, статические детекторы не воздействуют на программу во время её выполнения и не замедляют ход её работы. Во-вторых, они анализируют весь код программы, в том числе и тот, который выполняется очень редко, при выполнении специфических условий. Наконец, они не зависят от аппаратной платформы и системного окружения. Однако, задача проверки существования состояний гонки с помощью статического анализа NP-трудна, и поэтому на практике используются эвристические подходы,
4 что приводит к существенному понижению точности и большому количеству ложных срабатываний.
В связи с этим активно развиваются динамические методы обнаружения гонок, позволяющие анализировать программу непосредственно во время её исполнения. Динамический детектор располагает полной информацией о ходе выполнения программы, но на практике его точность ограничена накладными расходами на потребляемую память и ресурсы процессора. В общем случае нужно анализировать все синхронизационные события в программе и все обращения к разделяемым переменным и объектам, что приводит к большим накладным расходам. Большинство разработок динамических детекторов для Java-программ останавливаются на этапе прототипа и не применимы для обнаружения гонок в средних и крупных приложениях с достаточной степенью точности. В общем доступе существуют лишь два продукта, готовых к использованию - TSan и IBM MSDK, - но эксперименты показали, что их поведение нестабильно даже на небольших модельных приложениях, а на приложениях порядка тысячи классов и десяти потоков накладные расходы приводят к ошибкам переполнения памяти.
Цель и задачи работы
Основной целью данной работы является разработка метода динамического обнаружения гонок, позволяющего получить приемлемую производительность без существенной потери точности и разработка технологии, реализующей данный метод. Для достижения этой цели были поставлены и решены следующие задачи:
-
Проведение анализа существующих подходов к автоматическому поиску гонок в много поточных программах и изучение существующих детекторов.
-
Разработка метода повышения производительности динамического обнаружения гонок в Java-программ ах без существенной потери точности.
-
Создание алгоритма для динамического обнаружения гонок на основе этого метода.
-
Разработка на языке Java программного инструмента (динамического детектора) для обнаружения состояний гонки в многопоточных Java-программах, реализующего этот алгоритм.
5 Методы исследования
Для решения задач работы используются методы представления формальных спецификаций, динамический анализ программ, методы динамического обнаружения гонок, объектно-ориентированное проектирование и Java-технологии.
Основные положения, выносимые на защиту
-
Метод динамического поиска гонок, основанный на идее ограничения анализируемой области программы и корректной обработки операций вызова исключенного кода на основании синхронизационных контрактов.
-
Созданный на основе этого метода алгоритм для динамического поиска гонок, являющийся модификацией алгоритма happens-be fore и позволяющий сократить количество анализируемых операций без существенной потери точности поиска.
-
Язык описания синхронизационных контрактов для Java-программ, позволяющий описывать необходимые для динамического анализа свойства исключённого кода (контракты).
Реализация и внедрение результатов работы
На основании приведенных выше результатов выполнена программная реализация динамического детектора JDRD, основанная на трансформации байт-кода Java-программ. Проведена экспериментальная оценка предложенного подхода на двух небольших промышленных Java-приложениях и на одном достаточно крупном приложении (2000 классов, порядка 30 потоков), показавшая эффективность подхода и приемлемость накладных расходов. Полученный детектор JDRD внедрен в цикл разработки ряда коммерческих продуктов компании ООО «Эксперт-Система СЗ».
Научная новизна работы
1. Разработан новый метод отслеживания синхронизационных событий на основе явно описанных контрактов, основанных на отношении happens-before и создаваемых для классов и методов приложения. Это позволяет исключить из анализа значительные замкнутые фрагменты кода (в частности, сторонние пакеты и библиотеки) без потери значащей
информации о взаимодействии потоков, тем самым позволяя достичь существенного (до нескольких раз) снижения накладных расходов без существенной потери точности. Существующие подходы и программные продукты лишены такой возможности.
-
Разработан язык описания синхронизационных контрактов. Полученные описания хранятся в отдельных файлах конфигурации, а не в исходном коде детектора. Таким образом, добавление, удаление или изменение контрактов не требует перекомпиляции детектора. Кроме того, контракты можно создавать и для сторонних библиотек - в отличие от аннотаций, для использования которых необходим доступ к исходному коду программы. Так, были описаны контракты программных средств синхронизации Java (пакет java.util.concurrent) и контракты низкоуровневых механизмов, на которых они базируются. Это позволило обеспечить корректную обработку всех этих средств, в то время как в существующих реализациях осуществлена лишь частичная поддержка этих средств.
-
Новизной обладает выполненная реализация динамического детектора: как показало исследование, проведённое в рамках данной работы, в открытом доступе динамических детекторов, применимых для больших Java-приложений (тысячи классов, десятки потоков), на данный момент не
существует; а также нет информации о наличии таких средств,
і реализованных в виде коммерческих продуктов .
Практическая значимость результатов исследований
Разработанные метод и алгоритм повышают производительность точных динамических детекторов для Java-программ, поэтому их применение позволит повысить скорость обнаружения гонок и снизить влияние детектора на анализируемое приложение.
Описанные в главе 4 детали реализации jDRD представляют собой решения нескольких важных технических проблем, типичных для динамических
Безусловно, есть вероятность, что подобные средства существуют в виде закрытых разработок в крупных компаниях-производителях Java-приложений. Но мы не можем ничего сделать с этой неопределённостью.
7 детекторов. Использование этих решений позволит избежать некоторых утечек памяти и нарушения работы сериализации.
Внедрение созданного инструментального средства (детектора) JDRD в цикл разработки ПО позволит повысить качество разрабатываемых программных продуктов. Предложенный язык описания синхронизационных контрактов позволяет пере использовать единожды описанью контракты. Накопление контрактов библиотек позволит снизить трудозатраты на применение детектора к новым приложениям, а накопление контрактов модулей - регулярно использовать детектор на этапе модульного тестирования.
Личный вклад автора
Автором лично были разработаны метод синхронизационных контрактов и язык их описания; создана модификация точного алгоритма обнаружения гонок, позволяющая сократить количество обрабатываемых операций без существенной потери точности обнаружения гонок. На основе данного алгоритма реализован динамический детектор гонок для Java-программ и проведено его экспериментальное исследование.
Степень достоверности и апробация результатов работы
Основные результаты диссертационной работы изложены в работах [1-5]. Статьи [1-3] опубликованы в журнале, входящем в перечень ВАК, из них работы [1-2] написаны в соавторстве, автору принадлежит классификация и описание существующих подходов.
Результаты работы докладывались на семинаре кафедры системного программирования математико-механического факультета СПбГУ, на санкт-петербургском городском семинаре по программной инженерии, на конференциях CEE-SEC(R) 2012 (Москва), JPomt 2013 (Санкт-Петербург) и ТМРА 2013 (Кострома), а также на семинаре в ИСП РАН (Москва). Доклад на CEE-SEC(R) получил приз им. Бертрана Мейераза лучшую исследовательскую работу.
Экспериментальная оценка эффективности
Реализованный в рамках представленной работы динамический детектор jDRD использовался на нескольких промышленных Java-приложениях:
клиентское приложение к системе отслеживания ошибок JIRA (около 400 классов, 10 потоков), обнаружено 14 гонок;
консольный тест пропускной способности системы распространения котировок (около 700 классов, 15 потоков), обнаружено 6 гонок;
мониторинговый программный комплекс для сбора различных метрик с целевой системы (клиент-серверное приложение, в совокупности порядка 2000 классов и 30 потоков), обнаружено 16 гонок.
Каждый эксперимент осуществлялся итеративно, с постепенным сокращением области анализа и соответствующей доработкой синхронизационных контрактов. На каждой итерации фиксировалось количество обнаруженных гонок и различные метрики, позволяющие оценить величину накладных расходов. В результате всех экспериментов было обнаружено 36 гонок. Синхронизационные контракты показали свою эффективность - их добавление сокращало количество векторных часов и частоту совершения операций с ними, снижало потребление памяти и общую нагрузку на приложение.
Структура и объём диссертации
Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения. Текст диссертации изложен на 112 страницах и содержит 13 рисунков и 6 таблиц. Список литературы содержит 75 наименований.
