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

На правах рукописи

Трифанов Виталии Юрьевич

ДИНАМИЧЕСКОЕ ОБНАРУЖЕНИЕ СОСТОЯНИЙ ГОЖИ В МНОГОПОТОЧНЫХ МУА-ПРОГРАММАХ

Специальность: 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

7 НОЯ 2013

Санкт-Петербург - 2013

005537406

Работа выполнена на кафедре системного программирования математако-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: кандидат физико-математических наук, доцент

Кознов Дмитрий Владимирович

Официальные оппоненты: Лисс Александр Рудольфович,

доктор технических наук, профессор, начальник исследовательского отделения ОАО «Концерн «ОкеанПрибор»

Ицыксон Владимир Михайлович, кандидат технических наук, доцент ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет»

Ведущая организация: Федеральное государственное бюджетное

учреждение науки «Институт системного программирования Российской академии наук» (ИСП РАН)

Защита диссертации состоится «28» ноября 2013 года в 17 часов 00 минут на заседании диссертационного совета Д 212.227.06 при НИУ ИТМО по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49, конференц-зал центра интернет-образования.

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

Автореферат разослан «26» октября 2013 г.

Ученый секретарь диссертационного совета Д 212.227.06

Лобанов Игорь Сергеевич

Общая характеристика работы

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

Используемые в настоящее время вычислительные устройства всё в большей степени являются многоядерными и многопроцессорными, что позволяет разрабатывать для них эффективные параллельные программы и существенно увеличивает производительность целевых систем. Однако проектирование и разработка программ с использованием взаимодействующих потоков, одповремешю выполняющих различные действия, является сложной задачей, что приводит к большому количеству ошибок. К самым частым и сложным в обнаружении ошибкам многопоточных программ относятся состояния гонки (data races) — несинхронизированные обращения из различных потоков к одному и тому же участку памяти.

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

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

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

В связи с этим активно развиваются динамические методы обнаружения гонок, позволяющие анализировать программу непосредственно во время её исполнения. Динамический детектор располагает полной информацией о ходе выполнения программы, но на практике его точность ограничена накладными расходами на потребляемую память и ресурсы процессора. В общем случае нужно анализировать все синхронизационные события в программе и все обращения к разделяемым переменным и объектам, что приводит к большим накладным расходам. Большинство разработок динамических детекторов для Java-nporpaMM останавливаются на этапе прототипа и не применимы для обнаружения гонок в средних и крупных приложениях с достаточной степенью точности. В общем доступе существуют лишь два продукта, готовых к использованию - TSan и IBM MSDK, — но эксперименты показали, что их поведение нестабильно даже на небольших модельных приложениях, а на приложениях порядка тысячи классов и десяти потоков накладные расходы приводят к ошибкам переполнения памяти.

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

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

1. Проведение аналша существующих подходов к автоматическому поиску гонок в много поточных программах и изучение существующих детекторов.

2. Разработка метода повышения производительности динамического обнаружения гонок в Java-про грамм ах без существенной потери точности.

3. Создание алгоритма для динамического обнаружения гонок на основе этого метода

4. Разработка на языке Java программного инструмента (динамического детектора) для обнаружения состояний гонки в многопоточных Java-программах, реализующего этот алгоритм.

Методы исследования

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

Основные положения, выносимые на защиту

1. Метод динамического поиска гонок, основанный на идее ограничения анализируемой области программы и корректной обработки операций вызова исключенного кода на основании синхронизационных контрактов.

2. Созданный на основе этого метода алгоритм для динамического поиска гонок, являющийся модификацией алгоритма Иарреш-Ьейне и позволяющий сократить количество анализируемых операций без существенной потери точности поиска

3. Язык описания синхронизационных контрактов для ,1ауа-программ, позволяющий описывать необходимые для динамического анализа свойства исключённого кода (контракты).

Реализация и внедрение результатов работы

На основании приведенных выше результатов выполнена программная реализация динамического детектора ¡ТЖТ), основанная на трансформации байт-кода 1а\а-программ. Проведена экспериментальная оценка предложенного подхода на двух небольших промышленных ,1ауа-приложениях и на одном достаточно крупном приложении (2000 классов, порядка 30 потоков), показавшая эффективность подхода и приемлемость накладных расходов. Полученный детекторвнедрен в цикл разработки ряда коммерческих продуктов компании ООО «Эксперт-Система СЗ».

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

1. Разработан новый метод отслеживания синхронизационных событий на основе явно описанных контрактов, основанных на отношении Ьаррепя-ЬеРаге и создаваемых для классов и методов приложения. Это позволяет исключить из анализа значительные замкнутые фрагменты кода (в частности, сторонние пакеты и библиотеки) без потери значащей

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

2. Разработан язык описания синхронизационных контрактов. Полученные описания хранятся в отдельных файлах конфигурации, а не в исходном коде детектора. Таким образом, добавление, удаление или изменение ко трактов не требует перекомпиляции детектора. Кроме того, контракты можно создавать и для сторонних библиотек — в отличие от аннотаций, для использования которых необходим доступ к исходному коду программы. Так, были описаны контракты программных средств синхронизации Java (пакет javautil.concurrent) и контракты низкоуровневых механизмов, на которых они базируются. Это позволило обеспечить корректную обработку всех этих средств, в то время как в существующих реализациях осуществлена лишь частичная поддержка этих средств.

3. Новизной обладает выполненная реализация динамического детектора: как показало исследование, проведённое в рамках данной работы, в открытом доступе динамических детекторов, применимых для больших Java-приложений (тысячи классов, десятки потоков), на данный момент не существует; а также нет информации о наличии таких средств, реализованных в виде коммерческих продуктов1.

Практическая значимость результатов исследований

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

Описанные в главе 4 детали реализации jDRD представляют собой решения нескольких важных технических проблем, типичных для динамических

1 Безусловно, есть вероятность, что подобные средства существуют в виде закрытых разработок в крупных компаниях-производителях Java-приложений. Но мы не можем ничего сделать с этой неопределённостью.

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

Внедрение созданного инструментального средства (детектора) jDRD в цикл разработки ПО позволит повысить качество разрабатываемых программных продуктов. Предложенный язык описания синхронизационных контрактов позволяет переиспользовать единожды о писаные контракты. Накопление контрактов библиотек позволит снизить трудозатраты на применение детектора к новым приложениям, а накопление контрактов модулей — регулярно использовать детектор на этапе модульного тестирования.

Личный вклад автора

Автором лично были разработаны метод синхронизационных контрактов и язык их описания; создана модификация точного алгоритма обнаружения гонок, позволяющая сократить количество обрабатываемых операций без существенной потери точности обнаружения гонок. На основе данного алгоритма реализован динамический детектор гонок для Java-nporpaMM и проведено его экспериментальное исследование.

Степень достоверности и апробация результатов работы

Основные результаты диссертационной работы изложены в работах [1-5]. Статьи [1-3] опубликованы в журнале, входящем в перечень ВАК, ив них работы [1-2] написаны в соавторстве, автору принадлежит классификация и описание существующих подходов.

Результаты работы докладывались на семинаре кафедры системного программирования магематико-механического факультета СПбГУ, на санкт-петербургском городском семинаре по программной инженерии, на конференциях CEE-SEC(R) 2012 (Москва), JPoint 2013 (Санкт-Петербург) и ТМРА 2013 (Кострома), а также на семинаре в ИСП РАН (Москва). Доклад на CEE-SEC(R) получил приз им. Бертрана Мейераза лучшую исследовательскую работу.

Экспериментальная оценка эффективности

Реализованный в рамках представленной работы динамический детектор jDRD использовался на нескольких промышленных Java-приложениях:

• клиентское приложение к системе отслеживания ошибок JIRA (около 400 классов, 10 потоков), обнаружено 14 гонок;

• консольный тест пропускной способности системы распространения котировок (около 700 классов, 15 потоков), обнаружено 6 гонок;

• мониторинговый программный комплекс для сбора различных метрик с целевой системы (клиент-серверное приложение, в совокупности порядка 2000 классов и 30 потоков), обнаружено 16 гонок.

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

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

Диссертация состоит из введения, шести глав, заключения, списка литературы и приложения. Текст диссертации изложен на 112 страницах и содержит 13 рисунков и 6 таблиц. Список литературы содержит 75 наименований.

Основное содержание работы

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

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

гонок и существующие способы улучшения производительности. Подробно описывается алгоритм «Ьаррегк-ЬсГоге», на котором базируется большинство точных динамических детекторов. После этого сформулированы и обоснованы основные требования к промышленному динамическому детектору — точность и производительность. Существующие детекторы проанализированы с точки зрения этих критериев. Приводятся результаты применения существующих инструментов, показавшие значительные трудности с их практическим использованием. Сделаны выводы об отсутствии готового к использованию динамического детектора гонок, о необходимости разработки нового метода динамического обнаружения гонок и его полноценной реализации.

Во второй главе описывается предлагаемый метод обнаружения гонок. Подробно описывается основная идея — исключить из анализа вспомогательные и сторонние библиотеки, анализируя лишь код самого приложения. Вводится понятие области поиска гонок как части программного кода приложения, в которой осуществляется отслеживание обращений к разделяемым данным и поиск гонок, возникающих между этими обращениями. Вводится понятие области отслеживания операций синхронизации как области кода, в которой отслеживаются и обрабатываются операции синхронизации. Сокращение последней приводит к «потере» значительного числа синхронизационных событий, что, в свою очередь, повлечет за собой множество ложных срабатываний. Чтобы избежать потери точности, предлагается полностью описать поведение не анализируемого кода в многопоточной среде и трактовать вызовы описанных методов как соответствующие операции синхронизации. Вводится понятие Иаррет-Ье/оге контракта как описания связи между двумя вызовами методов класса (или двух различных классов) в терминах отношения "Ьарреги-ЬеГоге". Наррепз-ЬеГоге контракт, описание потокобезопасного метода и описание типа непотокобезопасного метода (является ли он модифицирующим или нсмодиф ицирующим) представляют собой частные случаи синхронизационного контракта - единичной частичной спецификации поведения методов в много поточной среде. Под синхронизационным контрактом программной компоненты понимается объединение всех синхронизационных контрактов для

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

Далее детально описывается предлагаемый алгоритм обнаружения гонок. Этот алгоритм базируется на точном алгоритме happens-before. Он осуществляет обработку операций обращения к разделяемым данным и обнаружение гонок только в области поиска гонок, то есть отслеживаются следующие события:

• обращения к полям классов, принадлежащих области поиска гонок и не помеченных модификатором volatile;

• вызовы методов классов, не принадлежащих к области поиска гонок, для которых нет описанных happens-before контрактов, и которые не являются потокобезопасными.

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

Далее анализируются ограничения и точность алгоритма. В конце главы описываются возможности разработанного языка описания синхронизационных контрактов.

Предложенный метод и основанный на нём алгоритм имеют ряд преимуществ:

• снижение накладных расходов, пропорциональное отношению объёма не анализируемого кода к объёму анализируемого;

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

• поддержка средств пакета java.util.concurrent: в отличие от блокировок и volatile-переменных, которые поддерживаются в Java на уровне языка, механизмы из javautil.concurrent представляют собой средства более высокого уровня, состоящие из классов и методов, которые обеспечивают то

или иное многопоточное поведение; описание контрактов этих методов (проделанное в рамках данной работы) обеспечивает их корректную обработку;

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

• отслеживание декларируемых контрактов: одна из основных проблем детекторов, основывающихся на алгоритме "happens-before", заключается в том, что детектор может увидеть случайно возникшую синхронизацию и пропустить гонку. Отслеживание синхронизации на основе описанного в документации поведении класса снижает вероятность этого, поскольку будут отслеживаться лишь те высокоуровневые события синхронизации, которые заявлены авторами класса а не все события, происходящие внутри этого класса Так, например, методы put и get класса ConcurrentHashMap выполняют внутри себя порядка двадцати синхронизационных операций — обращений к внутренним volatile-переменным и другим средствам (в частности, из java.util.concurrent). Однако в документации этого класса явно указано, что с точки зрения синхронизации между потоками, вызывающими данные методы, верен только один инвариант - вызов put предшествует последующему вызову get по тому же ключу. Если этот факт описан в синхронизационном контракте класса, то детектор обрабатывает только этот контракт, а не все события внутри класса ConcurrentHashMap, за счёт чего получается не только прирост производительности, но и меньшее количество несущественной информации. Другой пример: в Java метод System.out.println, используемый для стандартного вывода сообщений, полностью синхронизирован внутри себя (содержит критическую секцию). Таким образом, если два потока одновременно выводят что-то на экран, между ними происходит синхронизация. Однако это может осуществляться, например, из метода, который не является потокобезопасным. В этом случае, если два потока одновременно вызвали этот метод, возможна гонка, которую можно

пропустить по причине «случайного» отслеживания вызовов Бу^ет.оШ.ргШп. Если же опираться только на документированное поведение метода, а не на фактическое, то такого не произойдет и гонка будет отслежена — детектор обнаружит, что два потока одновременно вызвали непотокобезопасный метод.

В третьей главе описывается программная реализация предложенных выше идей - динамический детектор гонок ]01Ю. Сначала обсувдаются основные требования, с учетом которых разрабатывалась архитектура jDRD: максимальная скорость работы, возможность модификации или замены алгоритма поиска гонок и переносимость файлов конфигурации. Затем описывается компонентная модель jDRD, представленная на рис. 1.

Исследуемое приложение

а

Модифицированные

классы приложения

-;

а

Java Virtual Machine

Модифицирует ^ байт-код

Race Detection Module

a

Events Interceptor a

4

Vector clock Interceptor a

V

Statistics Module я

V

Reporting Module CI

jDRDTransforme^—^

Contracts Manager

CI

д ^

сопЛд.хт! ИЬч:опГ!д.хт|

Рис. 1. Компонентная модель детектора

Перехват хода выполнения программы, отслеживание событий синхронизации и обращений к разделяемым данным осуществляется с помощью Java-areнта jDRD. Он подключается к виртуальной машине Java (JVM), вызывается ей при загрузке каждого нового класса и делегирует трансформацию байт-кода этого класса модулю jDRDTransformer. Последний анализирует байт-код и обнаруживает операции, которые необходимо отслеживать — например, операции синхронизации, обращения к разделяемым данным и т.д. jDRDTransformer модифицирует байт-код этих операций: вставляет вызовы соответствующих методов модуля VectorClocklnterceptor. Например, для обработки операции входа в монитор вставляется вызов метода onMonitorEnter, для обработки записи разделяемого поля - onFieldWrite и т.д. Далее модуль VectorClocklnterceptor вызовет модуль RaceDetectionModule, который осуществляет непосредственное обнаружение гонок по алгоритму happens-before. Модуль RaceDetectionModule содержит реализацию алгоритма happens-before и хранит векторные часы. При необходимости данный модуль может быть полностью заменен на реализацию другого алгоритма (например, lockset). В случае обнаружения гонки этот модуль обращается к модулю журналирования, который отвечает за предоставление отчетов об обнаруженных гонках и сбор статистической информации о работе детектора. Информацию о том, в какие классы и в каких точках нужно вставить вызовы, Java-агент jDRD получает из модулей Configurator и ContractsManager. Первый отвечает за happens-before контракты, второй — за остальную конфигурацию детектора

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

Во-вторых, разработан способ хранения векторных часов для синхронизационных объектов, связанных с happens-before контрактами. Основная сложность здесь заключалась в том, что в качестве синхронизационного объекта может выступать произвольный набор объектов и примитивных типов данных -это становится известно только на этапе прочтения конфигурации. Проблема решена путем динамического генерирования новых классов - по одному на каждый уникальный синхронизационный объект.

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

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

Наконец, описывается процедура подготовки тестового окружения и основные приемы анализа гонок, о которых просигнализировал jDRD. Их можно поделить на две категории по отношению к месту возникновения:

• одновременное обращение из нескольких потоков к полю класса из области анализа;

• одновременный вызов нескольких методов одного и того же объекта, не принадлежащего области анализа (т.н. «чужой» или "foreign" объект), из нескольких потоков.

Первый тип гонки свидетельствует либо об ошибке программирования в коде приложения, которую необходимо устранить, либо о так называемой благоприятной гонке (benign race), которая была внесена в программу умышленно

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

Второй тип гонки свидетельствует о том, что детектор зафиксировал одновременный вызов нескольких (возможно, одних и тех же) методов одного fore/g/г-объекта из кода приложения из различных потоков. Поскольку изначально детектор не обладает полной информацией того, как трактовать foreign-вызовы, он расценивает их как обращения на запись к объекту, на котором вызываются эти методы. Если эти вызовы на самом деле не являются модифицирующими, то их нужно пометить как "read" в секции Contracts конфигурационного файла Изначально конфигурационный файл содержит определенную информацию -например, все методы, начинающиеся на "get", детектор трактует как обращения на чтение, а начинающиеся на "set" - как на запись. Если же такие вызовы являются потокобезопасными или обеспечивают синхронизацию, нужно создать соответствующий контракте конфигурационном файле.

В шестой главе описываются результата экспериментального исследования разработанного детектора]Г)RD наряде промышленных Java-приложений:

• нагрузочный тест производительности системы доставки котировок — небольшое по количеству кода приложение с большим потоком данных и высокой много поточностью;

• клиентское приложение к системе отслеживания ошибок JIRA — пользовательское приложение;

• сервер мониторинговой системы (многопоточная нагруженная система);

• пользовательский клиент мониторинговой системы.

Каждый экс пер им сиг описан по следующему шаблону.

• Краткое описание и характеристика тестируемого приложения.

• Результаты запуска детектора в базовом режиме: обрабатываются все низкоуровневые синхронизационные события во всём приложении. Приводятся численные параметры результатов запуска — рост

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

• Результаты запуска доступных динамических детекторов на этих же приложениях (IBM MSDK, TSan). Отметим, что MSDK и TSan удалось запустить только на первых двух (небольших) приложениях - на остальных они либо вовсе не запускались, либо «подвисали» и выдавали ошибку переполнения памяти.

• Результаты запуска jDRD в juc-режпме: описаны и применяются синхронизационные контракты для классов пакета java.util.concurrent. Производятся те же замеры, что и в базовом режиме.

• Результаты запуска jDRD в полном режиме: дополнительно описаны и применяются синхронизационные контракты сторонних библиотек. Операции синхронизации отслеживаются только в коде приложения.

• Сравнение результатов запуска jDRD в трёх различных режимах (базовом, juc и полном) — количество обнаруженных гонок, производительность и т.д.

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

В заключении сформулированы основные результаты работы и предложены направления дальнейших исследований.

В приложении приведено описание созданного языка спецификации синхронизационных контрактов.

Список работ, опубликованных по теме диссертации

Статьи в журналах из перечня ВАК:

1. Трифанов В.Ю., Цителов Д.И. Динамические методы обнаружения гонок в параллельных программах. Журнал «Компьютерные инструменты в образовании». №5, 2011. С. 3-15.

2. Трифанов В.Ю., Цителов Д.И. Статические и post-mortem методы обнаружения гонок в параллельных программах. Журнал «Компьютерные инструменты в образовании». №6, 2011. С. 3-13.

3. Трифанов В.Ю. Обнаружение состояний гонки в Java-nporpaMMax на основе синхронизационных контрактов. Журнал «Компьютерные инструменты в образовании». №4, 2012. С. 16-29.

В других изданиях:

4. Трифанов В. Динамическое обнаружение гонок в Java-nporpaMMax с помощью векторных часов. «Системное программирование». Вып. 5: Сб. статей. / Под ред. ЛН.Терехова, Д.Ю.Булычева. - СПб.: Изд-во СПбГУ, 2010. С. 95-116.

5. Цителов Д., Трифанов В. Динамический поиск гонок в Java-nporpaMMax на основе синхронизационных контрактов. Материалы конференции «Инструменты и методы анализа программ (ТМРА-2013)», Кострома, 2013. с. 195-208.

Подписано в печать 25.10.2013г. Формат 60x84/16 У.п.л. 1 Уч.-изд.л 1 . Тир. ЮОэкз. Отпечатано в типографии ООО «Турусел» 197376, Санкт-Петербург, ул. Профессора Попова д.38. toroussel@mail.ru Зак. № 13497 от 25.10.2013г.

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

На правах рукописи

04201453053

Трифанов Виталий Юрьевич

Динамическое обнаружение состояний гонки в многопоточных 1ауа-программах

Специальность: 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат физико-математических наук, доцент Кознов Дмитрий Владимирович

Санкт-Петербург -2013

Оглавление

Введение................................................................................................................4

Глава 1. Обзор методов автоматического обнаружения гонок......................16

1.1 Статический подход..................................................................................16

1.2 Динамическое обнаружение гонок..........................................................23

1.2.1 Многопоточная модель памяти..........................................................25

1.2.2 Отношение happens-before..................................................................26

1.2.3 Алгоритм happens-before.....................................................................28

1.2.4 Алгоритм lockset..................................................................................33

1.2.5 Другие подходы...................................................................................35

1.3 Обнаружение гонок после завершения работы программы..................37

1.4 Гибридные алгоритмы...............................................................................39

1.5 Выводы........................................................................................................42

Глава 2. Синхронизационные контракты.........................................................48

2.1 Терминология.............................................................................................51

2.2 Потоконебезопасные методы...................................................................56

2.3 Потокобезопасные методы.......................................................................57

2.4 Happens-before контракты.........................................................................59

2.5 Использование синхронизационных контрактов...................................60

2.6 Синхронизационные контракты в Java....................................................63

2.7 Отслеживание операций синхронизации................................................65

2.8 Алгоритм обнаружения гонок..................................................................67

2.9 Ограничения подхода................................................................................69

2.10 Точность подхода....................................................................................70

2.11 Язык описания синхронизационных контрактов.................................72

Глава 3. Архитектура разработанного детектора гонок.................................75

3.1 Основные принципы..................................................................................75

3.2 Архитектура.....................................................................................76

Глава 4. Особенности реализации детектора гонок........................................80

4.1 Контролирование роста размера векторных часов................................80

4.2 Хранение векторных часов.......................................................................81

4.3 Обеспечение корректной работы сериализации.....................................83

Глава 5. Методика использования детектора...................................................84

5.1 Способы использования............................................................................84

5.2 Область применения..................................................................................85

5.3 Подготовка тестового окружения............................................................86

5.4 Анализ результатов работы детектора....................................................87

Глава 6. Экспериментальное исследование ...........................................89

6.1 Об экспериментальном исследовании динамических детекторов.......89

6.2 Методика.....................................................................................................90

6.3 Лабораторное исследование.....................................................................92

6.4 Эксперимент на тесте с конечным временем выполнения...................94

6.5 Эксперимент на крупном приложении....................................................95

6.6 Анализ результатов....................................................................................97

Заключение..........................................................................................................99

Список литературы...........................................................................................103

Приложение. Описание языка спецификации контрактов...........................110

Введение

Актуальность работы

Используемые в настоящее время вычислительные устройства всё в большей степени являются многоядерными и многопроцессорными, что позволяет разрабатывать для них эффективные параллельные программы. Однако проектирование программы в терминах нескольких взаимодействующих потоков управления, одновременно выполняющих разные действия, является сложной задачей и приводит к большому количеству ошибок. К самым частым и сложным в обнаружении ошибкам многопоточных программ относится состояние гонки (data race)1 - несинхронизированные обращения из различных потоков к одному и тому же участку памяти, хотя бы одно из которых является обращением на запись [61].

Подавляющее большинство современных языков программирования, таких, как С#, Java, C/C++, Python, поддерживают многопоточность - возможность создания в процессе выполнения программы нескольких потоков {threads), которые исполняются параллельно. В основе лежит модель разделяемой памяти. В ней для публикации изменений, сделанных потоком, а также для получения изменений, сделанных другими потоками, существуют операции синхронизации.

1 Существуют два разных англоязычных термина — «race condition» и «data race». Первый означает влияние порядка выполнения операций в программе, определяемого извне, на корректность её работы; второй — наличие двух конфликтующих обращений к общему участку памяти из различных потоков [61]. Строго говоря, это различные термины, но они, по сути, описывают одну и ту же ситуацию — несинхронизированные конкурентные обращения к одним и тем же разделяемым данным из различных потоков. В русских переводах как «состояние гонки», так и «гонка» употребляются для перевода обоих этих терминов и используются как в отечественных научных статьях - см., например, [3] - так и на различных Интернет-ресурсах, в частности в MSDN и Wikipedia. В данной работе оба этих русскоязычных термина используются как синонимичные и соответствуют английскому «data race».

2 Здесь также существует некоторае разногласие - в некоторых работах в определении гонки требуется, чтобы оба конфликтующих обращения были обращениями на запись (модификацию), в некоторых - хотя бы одно. Данная работа в этом вопросе следует работам [60,61] и считает гонкой ситуацию, когда хотя бы одно из конфликтующих обращений является обращением на запись.

Состояние гонки наступает, когда два или более потоков в параллельной программе одновременно обращаются к одной структуре данных в общей памяти, между этими обращениями нет принудительного упорядочивания по времени и хотя бы одно из этих обращений является записью [61].

На рис. 1 представлен пример гонки в программе, написанной на языке с моделью разделяемой памяти. Из этого примера видно, что при отсутствии синхронизации между потоками возможны проблемные ситуации, когда потоки не «видят» изменений, сделанных друг другом. В данном случае первый поток увеличил значение переменной i, равное Б, на х, а второй - на у, но в итоге переменная i оказалась равной у+5, а не х+у+Б. Таким образом, в программе возникло состояние гонки.

Threadl Memory Thread2

^^ i n t i = 5 ^^

load i load i

i = i + x i = i + у

i = x+5

store x

i = y+5

Рис. 1. Пример гонки в Java-nporpaMMe.

Состояния гонки могут быть причинами серьезных проблем - так, описанная в примере выше ситуация может произойти с банковским счетом, который два разных потока пытаются одновременно увеличить на х и у рублей соответственно. При отсутствии должной синхронизации вместо итогового увеличения на х + у рублей может произойти увеличение лишь на х или на у. Если же речь идет о медицинских системах, то гонки могут привести еще к куда более серьезным последствиям - например, от передозировок, допущенных аппаратом лучевой терапии Therac-25 по причине гонок, скончались, как минимум, два человека [54]. Также состояние гонки послужило одной из причин

аварии в энергосистеме США и Канады в 2003 году, в результате которой порядка 50 миллионов человек остались без электричества [19].

«Ручное» обнаружение гонок крайне затруднительно в силу следующих причин.

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

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

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

Единственным способом гарантировать отсутствие ошибок синхронизации является полное исключение доступа к механизмам возникновения таких ошибок на уровне языка программирования. По этому пути идут некоторые современные языки - Erlang, Jocaml и другие. Однако большинство используемых в индустрии

языков, таких как C/C++, Java, С#, основываются на модели разделяемой памяти и не предоставляют подобной защиты.

Для избегания гонок разрабатываются дополнительные библиотеки классов и аннотаций, например Intel ТВВ [47] или механизмы из пакета java.util.concurrent [32], появившиеся в Java 1.5. Такие средства не дают гарантии отсутствия гонок, но помогают программисту создавать корректный код. Другой подход -верификация посредством построения формальной модели программы и последующее доказательство корректности этой модели. Существует ряд утилит [34, 50], реализующих такой подход и показавших свою состоятельность на небольших программах и модулях. Как правило, подобные утилиты используются для проверки программ, в которых цена ошибки очень высока. Например, NASA использовало утилиту JavaPathFinder для поиска ошибок в программном обеспечении космического аппарата [50]. К сожалению, задача проверки существования потенциальных состояний гонки в программе и родственная задача обнаружения взаимных блокировок являются NP-трудными [60,61]. Поэтому верифицирующие утилиты требуют колоссального количества ресурсов, экспоненциально возрастающего с увеличением размера программы, и неприменимы даже для программ среднего размера.

Таким образом, задача автоматического обнаружения гонок является сложной и актуальной, исследования здесь ведутся более двадцати лет. За это время было создано большое количество детекторов гонок, использующих различные подходы, методы и алгоритмы, а также опубликовано более пятидесяти статей. Существуют два принципиально разных подхода к автоматическому обнаружению гонок - статический и динамический [60]. Статический подход предполагает анализ программы без её фактического запуска. Динамический анализ, наоборот, выполняется одновременно с программой и собирает информацию о ходе её работы. Далее эту информацию можно обрабатывать сразу же (on-the-fly подход), а можно лишь накапливать, а

непосредственный анализ осуществлять после завершения программы {postmortem подход).

Основными качественными критериями методов автоматического обнаружения гонок являются точность и полнота поиска. Под точностью понимается отсутствие ложных срабатываний {false positives) - если детектор сигнализировал о гонке, то эта гонка возможна — то есть, она в действительности может произойти в каком-то достижимом пути выполнения программы. Полнота означает отсутствие пропущенных гонок {false negatives) - ситуаций, в которых детектор не сигнализировал о возможной гонке.

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

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

Данную проблему динамичеких детекторов не удается решить стандартными методами. В работе [38] представлен точный детектор FastTrack, использующий наиболее оптимизированную на настоящий момент реализацию векторных часов (базовой структуры точных динамических детекторов). Его производительность сравнима с производительностью неточных алгоритмов. Однако число операций, требующих обработки, остается огромным.

Единственный способ радикально сократить накладные расходы - анализировать меньшее количество данных. По этому пути идут авторы подхода семплирования [21,55]. Однако эта неполнота анализа приводит к пропуску гонок. Таким образом, указанных двух подходов к повышению производительности динамических детекторов с сохранением точности недостаточно.

Эта проблема динамических детекторов - невозможность одновременного достижения высокой точности поиска и низких накладных расходов, по-видимому, является основным препятствием к их широкому практическому применению. Более того, это является одной из причин малого числа реально существующих, индустриальных динамических детекторов. В общем доступе существуют всего два детектора для 1ауа-программ, вышедшие за рамки исследовательского прототипа и пригодных хотя бы для проведения лабораторного эксперимента, и оба они показали свою фактическую неприменимость уже на приложениях малого объёма (менее 1000 классов, порядка 10 потоков). Таким образом, можно сделать вывод, что на настоящий момент в индустрии не существует доступного промышленного динамического детектора для 1ауа-программ, удовлетворяющего одновременно требованиям точности и производительности3.

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

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

1. Проведение анализа существующих подходов к автоматическому поиску

гонок в многопоточных программах и изучение существующих детекторов.

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

2. Разработка метода повышения производительности динамического обнаружения гонок в Java-nporpaMMax без существенной потери точности.

3. Создание алгоритма для динамического поиска гонок на основе этого метода.

4. Разработка на языке Java программного инструмента (динамического детектора) для обнаружения состояний гонки в многопоточных Java-программах, реализующего этот алгоритм.

Методы исследования

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

Описание исследования

Для решения поставленной задачи предлагается идея сокращения области поиска гонок и отслеживания операций синхронизации без существенной потери точности. В основе лежат следующие практические наблюдения. Широчайший класс индустриальных Java-систем активно использует сторонние библиотеки. Культура программирования на языке Java такова, что это взаимодействие осуществляется через лаконичный, тщательно документированный прораммный интерфейс (далее - API). В частности, как правило, достаточно хорошо документировано поведение конкретных классов и интерфейсов этого API в многопоточной среде. Кроме того, если класс или интерфейс может использоваться как средство синхронизации (например, классы пакета java.util.concurrent или класс javax.swing.SwingUtilities), то в документации к классу детально описываются способы его использования для обеспечения этой синхронизации.

С другой стороны, для широчайшего класса систем источником ненадежности априори предполагается разрабатываемый код: считается, что используемые сторонние библиотеки д