ТЕОРИЯ И ПРАКТИКА МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ Тема 15 Методика разработки и анализа неблокирующих алгоритмов. Д.ф.-м.н., профессор А.Г. Тормасов Базовая кафедра «Теоретическая и Прикладная Информатика», МФТИ

Тема Методика анализа процесса соисполнения асинхронных параллельных алгоритмов Разрешенные и не разрешенные условия гонок в программах Условия корректности алгоритмов Машинный анализ алгоритмов 2Кафедра информатики МФТИ

Анализ алгоритмов Проблема наличия состояний конкурентного доступа к памяти (состояний гонки), приводящих к некорректной работе многопоточных алгоритмов. Недостатки использования блокировок Эффективность исполнения Взаимоблокировки, блокирование потоков из-за ошибки Проблемы существующих методов детектирования состояний гонки Сложность формального доказательства, построение заново для нового алгоритма Ситуация, приводящая к некорректной работе, может возникать очень редко Ситуация, не приводящая к некорректной работе, может определяться как ошибочная Необходим метод детектирования состояний гонки, приводящих к некорректной работе многопоточных алгоритмов Универсальный Автоматизируемый Учитывающий специфику многопоточного алгоритма и аппаратной платформы 3

4 Модель исполнения потоков N потоков исполнения, - атомарная инструкция на архитектуре x86 N+1 набор ячеек памяти - ячейки памяти, доступные только из i-го потока, i=1..N - ячейки общей памяти, доступные из всех N потоков S – состояние исполнения потоков – совокупность значений всех ячеек памяти – линеаризованная история исполнения ( - одна из инструкций ) p – функция корректности, учитывающая специфику решаемой задачи Задается извне Критерий наличия состояний гонки, приводящих к некорректной работе алгоритма. Формально определяет правильность решения задачи. Допустимый вариант - условия на значения после завершения работы потоков Не учитываются исключительные ситуации – прерывания, ошибки доступа к памяти и т.д.

5 Анализ инструкций потоков Классификация инструкций: Операции чтения. Поток считывает значение одной из общих ячеек памяти. Обозначение – R. Операции записи. Поток записывает значение в одну из общих ячеек памяти. Обозначение – W. Другие операции. Операции, не входящие ни в один из вышеописанных классов. Обозначение – X. Обозначение, где i – номер общей ячейки памяти, j – номер потока исполнения (например, ). Рассмотрим две операции в разных потоках и. Лемма. Состояние исполнения S после выполнения операций может зависеть от их порядка, если j=k Такие операции – некоммутирующие. A=R, B=W A=W, B=R A=W, B=W

6 Моделирование соисполнения двух потоков Два потока исполнения Функция корректности задана в виде, где - состояние исполнения после завершения работы потоков (результирующее состояние исполнения). - начальная вершина, - конечная. Уровень вершины - i+j. Ориентированный путь из начальной вершины в конечную - полный путь. Всего таких путей, а. Лемма. Существует взаимно-однозначное соответствие между вариантами совместного исполнения потоков и полными путями в соответствующем графе совместного исполнения потоков. Дуги, где j=1,…,n+1 - представляют i-ую операцию, выполняемую первым потоком. Дуги, где i=1,…,k+1 - представляют j-ую операцию, выполняемую вторым потоком. Полный путь представляет соответствующий ему вариант совместного исполнения потоков. Граф совместного исполнения потоков – ориентированный граф

Классы эквивалентности путей на графе 7

Построение представителей классов 8

Оценка числа классов эквивалентности 9

Анализ графа совместного исполнения 10 Для анализа достаточно вычислить результирующие состояния исполнения S только для одного представителя каждого из классов. Удалив из графа дуги, которые не входят в полные пути, соответствующие выбранным представителям классов, получим редуцированный граф совместного исполнения потоков. Результирующее состояние исполнения потоков может быть вычислено в неопределенных коэффициентах, двигаясь от начальной вершины графа к конечной (подробнее метод будет рассмотрен на примерах). Чтобы определить, возможно ли возникновение неразрешенного состояния гонки, остается проанализировать полученное состояние S с помощью функции корректности p. Рассуждения достаточно просто обобщить на случай фиксированного числа потоков, большего двух.

11 Методика анализа Построение графа совместного исполнения потоков Поиск эквивалентных путей на графе Анализ представителя каждого из классов эквивалентности с помощью функции корректности p Ответ на вопрос о правильной работе многопоточного алгоритма

Примеры. Изменение ячейки в двух потоках 12 Представление состояния исполнения потоков S в виде совокупности векторов (a,b,c), где a – это значение ячейки памяти, b – считанное значение ячейки, которым оперирует первый поток, c – считанное значение ячейки, которым оперирует второй поток. - модификация считанного значения, c помощью функции f. Первый поток выполняет Второй поток выполняет Начальное состояние исполнения (m,-,-). Функция корректности p – требование константности результирующего состояния исполнения потоков. Число вариантов исполнения 20, анализируемых 4.

Примеры. Транзакционное изменение двух ячеек 13 Функция корректности p – требование константности результирующего состояния исполнения потоков. Число вариантов исполнения 28, анализируемых 4.

14 Ветвления в алгоритмах. Алгоритм Петерсона Усложнение анализа. В функции корректности p могут быть указаны условия на одновременную достижимость участков кода. Существует алгоритм, уменьшающий сложность перебора, за счет использования ранее доказанных свойств коммутирующих операций. A1: ready[0]=1; A2: turn=1; A3: while ( ready[1] && A4: turn==1); A5: //действие 1 A6: ready[0]=0; B1: ready[1]=1; B2: turn=0; B3: while ( ready[0] && B4: turn==0); B5: //действие 2 B6: ready[1]=0;

15 Неблокирующая реализация алгоритма очереди Исследование неблокирующих реализаций алгоритмов – одно из приоритетных направлений для дальнейшей работы. массив int q[N], int tail, int head. head содержит номер первого элемента tail – номер свободной ячейки, следующей за последним элементом Корректная работа параллельного добавления элементов при начальном состоянии N > 2, q[0] = c, q[1] = 0, q[2] = 0, head = 0, tail = 1. … while (1) { A1(B1): t=tail; A2(B2): if (t == N) return 0; A3(B3): if (q[t] != NULL) { A4(B4): CAS(tail, t, t+1); continue;} A5(B5): if (CAS(q[t], NULL, x)) { A6(B6): CAS(tail, t, t+1); return 1;} }

Выводы Предложена методика анализа конкурентного исполнения программ Ее можно автоматизировать Развитие – перестановки операций, связанные с аппаратной платформой; циклы; обобщение на n потоков Приглашаю желающих заниматься этой темой в качестве НИР. 16

(с) А. Тормасов, г. Базовая кафедра «Теоретическая и Прикладная Информатика» ФУПМ МФТИ crec.mipt.ru_ Для коммерческого использования курса просьба связаться с автором. Теоретическая и Прикладная Информатика, МФТИ17