Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Моисеев, Михаил Юрьевич
05.13.11
Кандидатская
2011
Санкт-Петербург
174 с. : ил.
Стоимость:
499 руб.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И СРЕДСТВ ОБНАРУЖЕНИЯ ОШИБОК В МНОГОПОТОЧНЫХ ПРОГРАММАХ
1.1. Критерии оценки методов и средств обнаружения ошибок
1.2. Общие подходы к анализу параллельных программ
1.2.1. Подходы на основе анализа частичных порядков
1.2.2. Подходы на основе анализа наборов конструкций синхронизации
1.2.3. Подходы на основе извлечения инвариантов
1.2.4. Подходы на основе преобразования к последовательной программе
1.3. Методы обнаружения ошибок в многопоточных программах
1.3.1. Комбинирование алгоритмов анализа
1.3.2. Использование аппроксимаций
1.4. Средства обнаружения ошибок в многопоточных программах на языке С
Выводы
ГЛАВА 2. МОДЕЛЬ МНОГОПОТОЧНОЙ ПРОГРАММЫ И ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ СТАТИЧЕСКОГО АНАЛИЗА
2.1. Общая структура предлагаемого подхода
2.2. Модель многопоточной программы
2.2.1 Объекты и функции РИтгеасП
2.2.2 Представление объектов и функций РЛнеасП в модели программы
2.3. Представление динамических свойств многопоточной программы
2.3.1. Состояние программы
2.3.2. Представление информации о параллельном выполнении программы
ГЛАВА 3. МЕТОДЫ АНАЛИЗА ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ
ПРОГРАММЫ
ЗЛ. Организация совместного выполнения алгоритмов анализа
3.2. Алгоритм определения действий над объектами синхронизации
3.3. Алгоритм определения состояний объектов синхронизации
3.3.1 Способы построения допустимых комбинаций
3.3.2 Построение неполных комбинаций
3.3.3 Правила расчета состояний объектов синхронизации
3.3.4 Анализ конструкции state
3.4. Алгоритм построения отношений параллельности
3.5. Алгоритм построения отношений синхронизации
3.6. Алгоритм учета взаимного влияния потоков программы
3.7. Итеративный алгоритм анализа конструкций
3.7.1 Правила работы итеративного алгоритма
3.7.2 Завершимость итеративного алгоритма
3.7.3 Сохранение полноты результатов анализа
ГЛАВА 4. АЛГОРИТМЫ ОБНАРУЖЕНИЯ ОШИБОК В
МНОГОПОТОЧНЫХ ПРОГРАММАХ
4.1 Классификация программных ошибок
4.2 Правила обнаружения программных дефектов
4.2.1 Правила обнаружения ошибок управления ресурсами и динамической памятью
4.2.2 Правила обнаружения утечек ресурсов и памяти
4.2.3 Правила обнаружения ошибок работы с буферами
4.2.4 Правила обнаружения ошибок отсутствия инициализации
4.2.5 Правила обнаружения ошибок синхронизации
4.3 Обнаружение множественных дефектов
ГЛАВА 5. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ
5.1 Реализация разработанных методов
5.2 Проведение экспериментальных исследований
5.3 Оценки полноты и точности
5.4 Оценка вычислительной сложности
5.4.1 Вычислительная сложность правил, использующих
допустимые комбинации
5.4.2 Вычислительная сложность итеративного алгоритма.
5.4.3 Сравнение с существующими подходами
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ 1. РАСШИРЕНИЕ ПРЕДЛОЖЕННОГО ПОДХОДА НА
ДРУГИЕ ОБЪЕКТЫ СИНХРОНИЗАЦИИ РТНКЕАБЗ
ПРИЛОЖЕНИЕ 2. КОРРЕКТНОСТЬ ПРЕДСТАВЛЕНИЯ АТОМАРНЫХ
КОНСТРУКЦИЙ
ПРИЛОЖЕНИЕ 3. КОРРЕКТНОСТЬ ПРАВИЛ ПОСТРОЕНИЯ ОТНОШЕНИЙ ПАРАЛЛЕЛЬНОСТИ С ВИРТУАЛЬНЫМИ БЛОКАМИ ..169 ПРИЛОЖЕНИЕ 4. СОХРАНЕНИЕ ПОЛНОТЫ РЕЗУЛЬТАТОВ ПРИ АНАЛИЗЕ МНОГОПОТОЧНЫХ ПРОГРАММ
единственным источником недетерминизма выполнения программы является планировщик ОС, то вычислительную сложность методов, не использующих
аппроксимации, можно оценить как ), где I — максимально возможное число переключения контекста, с - число выбора потоков при каждом переключении контекста. Величина I прямо пропорциональна размеру программы, величина С - числу параллельно выполняющихся потоков.
Предлагается подход, основанный на аппроксимации поведения планировщика, ограничивающей недетерминизм планировщика некоторым число выполняемых конструкций (Delay-bounding). Для этого используется детерминированный планировщик и рассматриваются все возможные варианты переключения контекста в течение выполнения 1 конструкций. Утверждается, что предложенная аппроксимация несущественно влияет на полноту анализа и позволяет обнаруживать большое число программных ошибок. Вычислительная сложность предложенной аппроксимации
оценивается как
Экспериментальные результаты приводятся только для тестовых программ, что не позволяет судить о применимости предложенного подхода для обнаружения ошибок в реальных программных проектах.
Рассмотренные подходы используют ограничение на число возможных вариантов выполнения многопоточной программы, что может существенно снижать полноту результатов анализа. Перед применением подобных аппроксимаций необходимо получить оценку полноты результатов с помощью проведения экспериментальных исследований на реальных программных системах.
Одним из способов снижения ресурсоемкое анализа является аппроксимация функций. Основная идея заключается в том, что вызываемая функция анализируется один раз (при первом вызове), при этом выполняется построение аппроксимации этой функции. Построенная аппроксимация потом используется при каждом вызове данной функции. Сложность
Название работы | Автор | Дата защиты |
---|---|---|
Исследование и разработка методов и программных средств классификации текстовых документов | Гулин, Владимир Владимирович | 2013 |
Программное обеспечение для многоуровневого структурирования контента информационного пространства по системной модели | Бармин, Александр Александрович | 2014 |
Методы и программные средства поиска информации на основе прецедентов в интеллектуальных поисковых системах | Зо Лин Кхаинг | 2016 |