Введение
ГЛАВА 1. Сравнительный анализ существующих методов и средств обнаружения ошибок в многопоточных программах 16
1.1. Критерии оценки методов и средств обнаружения ошибок 17
1.2. Общие подходы к анализу параллельных программ 20
1.2.1. Подходы на основе анализа частичных порядков 20
1.2.2. Подходы на основе анализа наборов конструкций синхронизации 24
1.2.3. Подходы на основе извлечения инвариантов 26
1.2.4. Подходы на основе преобразования к последовательной программе 28
1.3. Методы обнаружения ошибок в многопоточных программах 31
1.3.1. Комбинирование алгоритмов анализа 31
1.3.2. Использование аппроксимаций 34
1.4. Средства обнаружения ошибок в многопоточных программах на языке С 36
Выводы 38
ГЛАВА 2. Модель многопоточной программы и представление результатов статического анализа 40
2.1. Общая структура предлагаемого подхода 40
2.2. Модель многопоточной программы 42
2.2.1 Объекты и функции Pthreads 44
2.2.2 Представление объектов и функций Pthreads в модели программы 54
2.3. Представление динамических свойств многопоточной программы 61
2.3.1. Состояние программы 61
2.3.2. Представление информации о параллельном выполнении программы з
ГЛАВА 3. Методы анализа параллельного выполнения программы 71
3.1. Организация совместного выполнения алгоритмов анализа 71
3.2. Алгоритм определения действий над объектами синхронизации... 74
3.3. Алгоритм определения состояний объектов синхронизации 80
3.3.1 Способы построения допустимых комбинаций 81
3.3.2 Построение неполных комбинаций 85
3.3.3 Правила расчета состояний объектов синхронизации 88
3.3.4 Анализ конструкции state 88
3.4. Алгоритм построения отношений параллельности 89
3.5. Алгоритм построения отношений синхронизации 97
3.6. Алгоритм учета взаимного влияния потоков программы 99
3.7. Итеративный алгоритм анализа конструкций 108
3.7.1 Правила работы итеративного алгоритма 110
3.7.2 Завершимость итеративного алгоритма 113
3.7.3 Сохранение полноты результатов анализа 114
ГЛАВА 4. Алгоритмы обнаружения ошибок в многопоточных программах 119
4.1 Классификация программных ошибок 119
4.2 Правила обнаружения программных дефектов 121
4.2.1 Правила обнаружения ошибок управления ресурсами и динамической памятью 122
4.2.2 Правила обнаружения утечек ресурсов и памяти 123
4.2.3 Правила обнаружения ошибок работы с буферами 124
4.2.4 Правила обнаружения ошибок отсутствия инициализации 125
4.2.5 Правила обнаружения ошибок синхронизации 126
4.3 Обнаружение множественных дефектов 130
ГЛАВА 5. Практическая реализация и оценка эффективности разработанных методов 132
5.1 Реализация разработанных методов 132
5.2 Проведение экспериментальных исследований 135
5.3 Оценки полноты и точности 138
5.4 Оценка вычислительной сложности 142
5.4.1 Вычислительная сложность правил, использующих допустимые комбинации 142
5.4.2 Вычислительная сложность итеративного алгоритма 147
5.4.3 Сравнение с существующими подходами 148
Заключение 150
Список использованных источников 154
