Статический анализ проблем синхронизации параллельных алгоритмов в вычислительных системах с общей памятью

• Автор: Бабичев, Сергей Леонидович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Долгопрудный
• Количество страниц: 106 с. : ил.

Содержание

Список сокращений
ВВЕДЕНИЕ
Глава 1. ОБЗОР ОСНОВНЫХ МЕТОДОВ И МОДЕЛЕЙ
1.1. Развитие современных вычислительных систем и его влияние на архитектуру программ
1.2. Обзор работ по теме
1.3. Сети Петри как инструмент моделирования дискретных систем
1.4. Терминология сетей Петри
1.5. Свойства сетей Петри как средства анализа исполнительных потоков многопоточных программ
1.5.1. Последовательное исполнение
1.5.2. Синхронизация
1.5.3. Слияние
1.5.4. Параллельное исполнение
1.5.5. Моделирование конфликтов
1.6. Классификация сетей Петри
1.6.1. Классификация активностей
1.6.2. Сифоны и ловушки
1.6.3. Применимость сифонов и ловушек в задачах определения тупиков
1.7. Резюме
Глава 2. МЕТОДЫ АНАЛИЗА СЕТЕЙ ПЕТРИ
2.1. Методы анализа активности сетей Петри
2.2. Метод дерева достижимости
2.2.1. Алгоритм построения дерева достижимости

2.3. Метод сифонов и ловушек
2.3.1. Теорема о минимальных сифонах
2.3.2. Теорема о задаче квадратичного программирования
2.3.3. Метод математического программирования
2.3.4. Метод минимальных сифонов
2.4. Сравнение методов
2.5. Резюме
Глава 3. СИНТЕЗ СОВОКУПНОЙ МОДЕЛИ
3.1. Примитивы синхронизации
3.1.1. Соглашения о терминологии
3.1.2. Примитив типа Mutex
3.1.3. Примитив типа Event
3.1.4. Действие типа Thread
3.1.5. Точка исполнения Action
3.2. Синтез совокупной сети Петри
3.2.1. Формализованный язык описания модели
3.2.2. Лексический анализ
3.2.3. Грамматический анализ ФОЯМ
3.2.4. Структуры данных грамматического анализа
3.2.5. Построение синтаксического дерева
3.2.6. Оптимизация
3.2.7. Исследование свойств совокупной сети Петри
3.3. Примеры использования
3.3.1. Классический пример тупика
3.3.2. Проблема синхронизации Apache deadlock bug #42031
3.3.3. Проблема обедающих философов
3.4. Резюме

Глава 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДОВ АНАЛИЗА
4.1. Практические задачи системного программирования, требующие решения
4.2. Пул вычислительных потоков (ПВП)
4.2.1. Требования, накладываемые на реализацию ПВП
4.2.2. Организация ПВП и методы работы с пулом
4.2.3. Оптимизация использования ПОВП
4.2.4. Операции ПОВП
4.2.5. Использование ПОВП для обработки запросов ввода-вывода
4.3. Апробация модели - драйвер-фильтр ввода/вывода
4.4. Апробация модели - решение задачи целочисленного математического программирования
4.5. Резюме
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ МАТЕРИАЛОВ

(71У 7 — /Ло,(72У = —/х2о,У 7 0, где (71 и (72 соответственно определяют позиции вР-5и 5 соответственно. Согласно лемме Фаркаша-Минковского ( [46], [13]) данная система имеет решение тогда и только тогда, когда система (2.7) не имеет решения:
итС1 + утС2 С О
итр 1о + итр20 < 0 (2.7)

Из теории выпуклых множеств ( [51]), любое решение системы и (71 + утС2 0 с и 57 0 может быть выражено как неотрицательная линейная комбинация конечного множества решений той же системы, обычно называемых генераторами. Пусть К (Б) есть множество генераторов. Ясно, что Б(Б) = О и система (2.7) не имеет решений тогда и только тогда, когда
и1 р10 + УТр,20, /[и, у 6 К(Б). (2.8)
Свойство 5: Сеть Петри безтупиковая, если 1Ло(С2(Б)) 7= 1 удовлетворяется для любого минимального сифона Б такого, что <Ф(Б) ф 0 и условие (2.8)
не удовлетворяется для всех остальных минимальных сифонов.
Для задач небольшого размера, условие (2.8) может быть прямо выведено из системы (2.6) путём алгебраических преобразований. Прямолинейный подход состоит из
1. записать уравнение состояния
2. установить маркировку каждой позиции в сифоне, который мы собирается рассмотреть, в О
3. решить связанные уравнения
4. заменить решения в оставшихся неравенствах-ограничениях
5. упростить неравенства для получения заключительной системы.