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

• Автор: Трифанов, Виталий Юрьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 112 с. : ил.

Оглавление
Введение

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

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

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

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

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

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

1.2.4 Алгоритм lockset

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

1.3 Обнаружение гонок после завершения работы программы
1.4 Гибридные алгоритмы
1.5 Выводы
Глава 2. Синхронизационные контракты
2.1 Терминология
2.2 Потоконебезопасные методы
2.3 Потокобезопасные методы
2.4 Happens-before контракты
2.5 Использование синхронизационных контрактов
2.6 Синхронизационные контракты в Java
2.7 Отслеживание операций синхронизации
2.8 Алгоритм обнаружения гонок
2.9 Ограничения подхода
2.10 Точность подхода

2.11 Язык описания синхронизационных контрактов
Глава 3. Архитектура разработанного детектора гонок
3.1 Основные принципы
3.2 Архитектура jDRD
Глава 4. Особенности реализации детектора гонок
4.1 Контролирование роста размера векторных часов
4.2 Хранение векторных часов
4.3 Обеспечение корректной работы сериализации
Глава 5. Методика использования детектора
5.1 Способы использования
5.2 Область применения
5.3 Подготовка тестового окружения
5.4 Анализ результатов работы детектора
Глава 6. Экспериментальное исследование ]П1Ш
6.1 Об экспериментальном исследовании динамических детекторов
6.2 Методика
6.3 Лабораторное исследование
6.4 Эксперимент на тесте с конечным временем выполнения
6.5 Эксперимент на крупном приложении
6.6 Анализ результатов
Заключение
Список литературы
Приложение. Описание языка спецификации контрактов

Введение
Актуальность работы
Используемые в настоящее время вычислительные устройства всё в большей степени являются многоядерными и многопроцессорными, что позволяет разрабатывать для них эффективные параллельные программы. Однако проектирование программы в терминах нескольких взаимодействующих потоков управления, одновременно выполняющих разные действия, является сложной задачей и приводит к большому количеству ошибок. К самым частым и сложным в обнаружении ошибкам многопоточных программ относится состояние гонки (data race)' - несинхронизированные обращения из различных потоков к одному и тому же участку памяти, хотя бы одно из которых является обращением на запись2 [61].
Подавляющее большинство современных языков программирования, таких, как С#, Java, C/C++, Python, поддерживают многопоточность - возможность создания в процессе выполнения программы нескольких потоков (threads), которые исполняются параллельно. В основе лежит модель разделяемой памяти. В ней для публикации изменений, сделанных потоком, а также для получения изменений, сделанных другими потоками, существуют операции синхронизации.
1 Существуют два разных англоязычных термина — «race condition» и «data race». Первый означает влияние порядка выполнения операций в программе, определяемого извне, на корректность её работы; второй - наличие двух конфликтующих обращений к общему участку памяти из различных потоков [61]. Строго говоря, это различные термины, но они, по сути, описывают одну и ту же ситуацию — несинхронизированные конкурентные обращения к одним и тем же разделяемым данным из различных потоков. В русских переводах как «состояние гонки», так и «гонка» употребляются для перевода обоих этих терминов и используются как в отечественных научных статьях - см., например, [3] - так и на различных Интернет-ресурсах, в частности в MSDN и Wikipedia. В данной работе оба этих русскоязычных термина используются как синонимичные и соответствуют английскому «data race».
2 Здесь также существует некоторае разногласие - в некоторых работах в определении гонки требуется, чтобы оба конфликтующих обращения были обращениями на запись (модификацию), в некоторых - хотя бы одно. Данная работа в этом вопросе следует работам [60,61] и считает гонкой ситуацию, когда хотя бы одно из
конфликтующих обращений является обращением на запись.

выигрывая в производительности по сравнению с Eraser. Тем не менее, точность детектора все равно осталась низкой, а эксперименты проводились лишь на микротестах производительности.
Ещё одна модификация алгоритма lockset описана в [33]. В этой работе представлен алгоритм Goldilocks - lockset алгоритм, к которому добавлены механизмы, позволяющие корректно обрабатывать все остальные способы синхронизации, отличные от постоянной защиты критических секций мониторами. Речь идет о корректной публикации локальных данных потока в разделяемую память, о защите разделяемых данных разными мониторами в разные промежутки времени и о защите полей объекта посредством защиты всего объекта с помощью переменной блокировки. Утилита для Java-программ, основанная на алгоритме Goldilocks, корректно обрабатывает операции start и join за счёт наследования множеств блокировок, удерживаемых потоками, но всё же не поддерживает механизм низкоуровневой синхронизации с помощью средств пакета java. util. concurrent [32], который очень часто используется в Java-приложениях.
1.2.5 Другие подходы
Динамический анализ Java-программ традиционно осуществлялся посредством инструментирования байт-кода с использованием соответствующих библиотек [14, 16]. С распространением аспектно-ориентированного подхода [71], призванного упростить решение подобных задач (перехват работы программы и внедрение в неё дополнительной сквозной функциональности), возникла идея применить этот подход к обнаружению гонок. Так, в АОП-систему AspectJ [17] были добавлены точки соединения lock, unlock и mayBeShared9, которые упрощают использование Aspect! для отслеживания и обнаружения гонок. Однако последняя точка соединения обладает недостаточно высокой точностью и может указывать на объекты, которые не являются разделяемыми. Кроме того,
4 Точки соединения (pointeurs) - места в программе, удовлетворяющие определённым предикатам.