ТЕОРИЯИПРАКТИКА

МНОГОПОТОЧНОГО

ПРОГРАММИРОВАНИЯ

15Тема

Методика разработки и анализа неблокирующих алгоритмов.

Д.ф.-м.н., профессор А.Г. Тормасов

Базовая кафедра «Теоретическая и Прикладная Информатика», МФТИ

Кафедра информатики МФТИ 2

Тема

• Методика анализа процесса соисполнения асинхронных параллельных алгоритмов

• Разрешенные и не разрешенные условия гонок в программах

• Условия корректности алгоритмов

• Машинный анализ алгоритмов

Анализ алгоритмов

• Проблема наличия состояний конкурентного доступа к памяти (состояний гонки), приводящих к некорректной работе многопоточных алгоритмов.

• Недостатки использования блокировок• Эффективность исполнения• Взаимоблокировки, блокирование потоков из-за ошибки

• Проблемы существующих методов детектирования состояний гонки• Сложность формального доказательства, построение заново для нового алгоритма• Ситуация, приводящая к некорректной работе, может возникать очень редко• Ситуация, не приводящая к некорректной работе, может определяться как ошибочная

• Необходим метод детектирования состояний гонки, приводящих к некорректной работе многопоточных алгоритмов• Универсальный• Автоматизируемый• Учитывающий специфику многопоточного алгоритма и аппаратной платформы

3

4

Модель исполнения потоков

N потоков исполнения

, - атомарная инструкция на архитектуре x86

N+1 набор ячеек памяти

- ячейки памяти, доступные только из i-го потока, i=1..N

- ячейки общей памяти, доступные из всех N потоков

S – состояние исполнения потоков – совокупность значений всех ячеек памяти

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

Не учитываются исключительные ситуации – прерывания, ошибки доступа к памяти и т.д.

1 2, ,..., NT T T

1{ ,..., }i

i ii zT o o i

jo

1 2 1, ,..., NM M M

1{ ,..., }i

i ii qM m m

1

1 11 1{ ,..., }

N

N NN qM m m

1 2 1, ,..., NM M M

1 2 1, ,..., NM M M

1{ ,..., }i

i ii ZH h h l

moijh

5

Анализ инструкций потоков

Классификация инструкций:

Операции чтения. Поток считывает значение одной изобщих ячеек памяти. Обозначение – R.

Операции записи. Поток записывает значение в одну изобщих ячеек памяти. Обозначение – W.

Другие операции. Операции, не входящие ни в один извышеописанных классов. Обозначение – X.

Обозначение , где i – номер общей ячейки памяти, j – номер потока исполнения (например, ).

Рассмотрим две операции в разных потоках и .Лемма. Состояние исполнения S после выполнения операцийможет зависеть от их порядка, если j=k

Такие операции – некоммутирующие.

ijO

31R

jxA k

yB

A=R, B=W A=W, B=R A=W, B=W

6

Моделирование соисполнения двух потоков

Два потока исполнения

Функция корректности задана в виде , где - состояние исполнения

после завершения работы потоков (результирующее состояние исполнения).

1 1 2 21 1 2 1 1 2{ ,..., }, { ,..., }, , k nT o o T o o k z n z

i i i+1 i ij j j j j+1

i=1,k+1 i=1,k i=1,k+1j=1,n+1 j=1,n+1 j=1,n

G:=(V,A),V= v ,A= (v ,v ) (v ,v )

- начальная вершина, - конечная. Уровень вершины - i+j.

Ориентированный путь из начальной вершины в конечную - полный путь. Всего таких путей , а .

Лемма. Существует взаимно-однозначное соответствиемежду вариантами совместного исполнения потоков иполными путями в соответствующем графе совместного исполнения потоков.

Дуги , где j=1,…,n+1 - представляют i-ую операцию, выполняемую первым потоком. Дуги , где i=1,…,k+1 - представляют j-ую операцию, выполняемую вторым потоком. Полный путь представляет соответствующий ему вариант совместного исполнения потоков.

11v k+1

n+1v ijv

i i+1j j(v ,v )

i ij j+1(v ,v )

kn kC

2nn2n

2C

n

*( )p p S *S

Граф совместного исполнения потоков – ориентированный граф

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

7

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

8

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

9

Анализ графа совместного исполнения

10

Для анализа достаточно вычислить результирующие состояния исполнения S

только для одного представителя каждого из классов.

Удалив из графа дуги, которые не входят в полные пути, соответствующие

выбранным представителям классов, получим редуцированный граф

совместного исполнения потоков.

Результирующее состояние исполнения потоков может быть вычислено в

неопределенных коэффициентах, двигаясь от начальной вершины графа к

конечной (подробнее метод будет рассмотрен на примерах).

Чтобы определить, возможно ли возникновение неразрешенного состояния

гонки, остается проанализировать полученное состояние S с помощью

функции корректности p.

Рассуждения достаточно просто обобщить на случай фиксированного числа

потоков, большего двух.

11

Методика анализа

Построение графа совместного исполнения потоков

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

Анализ представителя каждого из классов эквивалентности с помощью функции корректности p

Ответ на вопрос о правильной работе многопоточного алгоритма

Примеры. Изменение ячейки в двух потоках

12

1

2

3

4

(m,m,-)

1R

1V ( )f

1W

2R

2V ( )f

2W

2R

2V ( )f

2W

1R

1V ( )f

1W

(m,m+1,-) (m,m,m+1)

3(m+1,m+1,m+ ) 3(m+1,m+ ,m+1)

3(m+1,m+1,m+ +1)

5

3(m+1,m+ +1,m+1)

3 5 3 5 3(m+1+ ,m+1+ ,m+1+ )

(m,-,m)

+ +

+

(m,-,-)

Представление состояния исполнения потоков S в виде совокупности векторов (a,b,c), где a – это значение ячейки памяти, b – считанное значение ячейки, которым

оперирует первый поток, c – считанное значение ячейки, которым

оперирует второй поток.

- модификация считанного значения,c помощью функции f.Первый поток выполняет Второй поток выполняет

Начальное состояние исполнения (m,-,-).

Функция корректности p – требование константности результирующего состояния исполнения потоков.

Число вариантов исполнения 20, анализируемых 4.

( )iV f

1 1 1( ) , ( ) 1R V W f f x x

2 2 2( ) , ( ) 1R V W f f x x

Примеры. Транзакционное изменение двух ячеек

13

Функция корректности p – требование константности результирующего состояния исполнения потоков.

Число вариантов исполнения 28, анализируемых 4.11R

11V ( )f

+

12R

22R

12R

21R

21V ( )f

11W

21W

11R

11V ( )f

11W

21R

21V ( )f

1 2(m ,-,-)(m ,-,-)

1 1 2(m ,m ,-)(m ,-,-)

21W2

2R

4

8+

1 1 1 4 2(m - k,m - k,m - k)(m ,-,-)

1 1 1 4 2 2(m - k,m - k,m - k)(m ,m ,-)

1 1 1 4 2 2(m - k,m - k,m - k)(m ,m k,-)

1 1 1 4 2 2 2 8(m - k,m - k,m - k)(m k,m k,m k)

1 1 2(m ,m - k,-)(m ,-,-)

1 1 1 2 2 21 1 1 1 1 1R V ( ) W , R V ( ) W , ( ) , ( )f g f x x k g x x k

14

Ветвления в алгоритмах. Алгоритм Петерсона

Усложнение анализа.

В функции корректности p могут быть указаны условия на одновременную достижимость участков кода.

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

A1: ready[0]=1;A2: turn=1;A3: while

( ready[1] &&A4: turn==1);A5: //действие 1A6: ready[0]=0;

B1: ready[1]=1;B2: turn=0;B3: while

( ready[0] &&B4: turn==0);B5: //действие 2B6: 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.

A1

A2

A3

B1

B2

B3

A4

A5

B4

B5

A6 B6

Состояние исполнения:(tail,tA,tB) (1,-,-)(q[1],q[2]) (0,0)

+

+

+

+++

(1,-,-) (0,0)

(1,1,-) (0,0)

(1,-,1) (0,0)

(1,1,1) (0,0)

(1,1,-) (0,0)

(1,1,1) (0,0)

(1,1,-) (0,0)

(1|2,1,-|1) (a,0)

(2,1,-|1) (a,0)

(1,1,1) (0,0)

(1|2,1,1|2) (a,0)

(2,1,1|2) (a,0)

(1,1,1) (0,0)

(1|2,-|1,1) (b,0)

(2,1|2,1) (b,0)

(1,-,1) (0,0)

(1,-,1) (0,0)

(1,1,1) (0,0)

(2,-|1,1) (b,0)

(1,1,1) (0,0)

(1,1,1) (0,0)

(1,1,1) (0,0)

(1,1,1) (0,0)

+(2,1,1|2)

(a,0)

(2,1,1|2) (a,0)

(2,1,1|2) (a,0)

(1|2,1,1|2) (a,0)

(1|2,1,1|2) (a,0)

(1|2,1|2,1) (b,0)

(1|2,1|2,1) (b,0)

(1|2,1|2,1) (b,0)

(2,1|2,1) (b,0)

(2,1|2,1) (b,0)

(2,1|2,1) (b,0)(2,1|2,2|1)

(a|b,b|a)(2|3,1|2,2|1)

(a|b,b|a)(3|2,1|2,2|1)

(a|b,b|a)(3,1|2,2|1) (a|b,b|a)

(1|2,1,1|2) (a,0)

(1|2,1|2,1) (b,0)

… 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;} }

16

Выводы

• Предложена методика анализа конкурентного исполнения программ

• Ее можно автоматизировать

• Развитие – перестановки операций, связанные с аппаратной платформой; циклы; обобщение на n потоков

• Приглашаю желающих заниматься этой темой в качестве НИР.

(с) А. Тормасов, 2010-11 г.

Базовая кафедра «Теоретическая и Прикладная Информатика» ФУПМ МФТИ

tor@ crec .mipt .ru_

Для коммерческого использования курса просьба связаться с автором.

Теоретическая и Прикладная Информатика, МФТИ 17