Введение
Глава 1. Общие понятия и существующие методы анализа многопоточных алгоритмов для обнаружения состояний гонок 15
1.1. Понятие об оптимизации и промежуточном коде 15
1.2. Оптимизирующие компиляторы 17
1.3. Средства статического анализа 20
1.4. Метод статического анализа на основе графа совместного исполнения потоков 26
Глава 2. Реализации модели статического анализа нахождения состояния гонки в многопоточных алгоритмах с использованием линеаризованного графа потока управления 32
2.1. Анализ оптимизаций на промежуточном представлении 32
2.2. Линеаризация графа потока управления через линейку оптимизаций LLVM 37
2.3. Анализ инструкций SSA-формы LLVM IR, не влияющих на математическую модель поиска RC 41
2.4. Получения сокращенного оптимизированного промежуточного представления LLVM – Reduced Opt LLVM IR 46
2.5. Контекстно-зависимая линеаризация графа потока управления на сокращенном промежуточном представлении программы 51
2.6. Поиск состояний гонок в исследуемом методе на Reduced CFG 54
2.7. Модель автоматизация поиска состояний гонок 59
Глава 3. Практические результаты и анализ применения программной реализации модели поиска состояний гонок в многопоточных алгоритмах 62
3.1. Спинлок (спин-блокировка) 62
3.2. Некорректный алгоритм спин-блокировки 67
3.3. Алгоритм Петерсона 69
3.4. Стек Трейбера 70
3.5. Выводы 84
Заключение 85
Список использованных источников 87
