Синхронизация потоков

1. 4. Синхронизация потоков

2. 4.1. Атомарные действия (операции)

3. Определение действия и контекста действия

• Действием (action) называется изменение
контекста потока.
• Контекстом действия называется область
памяти, к которой действие имеет доступ.

4. Определение атомарного действия

• Действие называется атомарным (atomic
action), или непрерываемым, или
непрерывным если они удовлетворяет двум
требованиям:
– не прерывается во время своего исполнения;
– контекст действия изменяется только самим
действием.
• Атомарные действия будем обозначать
следующим образом:
атомарное_действие := <действие>

5. Две группы атомарных действия

• Атомарные действия делят на две
группы:
– элементарные атомарные действия (fine
grained atomic actions);
– составные атомарные действия (coarse
grained atomic actions).

6. Элементарные атомарные действия

• К элементарным атомарным действиям
относятся команды микропроцессора,
которые не могут быть прерваны во время
своего исполнения.

7. Непрерываемые команды микропроцессора

• Условно (теоретически) считают, что
атомарными являются следующие команды
микропроцессора:
– операции над данными, хранящимися в регистрах
микропроцессора;
– операции чтения данных из памяти в регистры
микропроцессора;
– операции записи данных в память из регистров
микропроцессора.

8. Составные атомарные действия

• К составным атомарным действиям
относятся последовательности
элементарных атомарных действий, которые
не прерываются во время своего
исполнения.

9. Маскирование прерываний

• Так как переключение между потоками
происходит только по прерываниям, то на
однопроцессорном компьютере атомарность
составного действия обеспечивается
запрещением (маскированием) прерываний:
disable_interrupt();
составное_действие;
enable_interrupt();

10. Маскирование прерываний

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

11. 4.2. Частные и разделяемые переменные

12. Определение частной и разделяемой переменной

• Переменная, доступ к которой имеет только
один поток, называется частной (private)
или личной переменной потока.
• Переменная, доступ к которой имеют
несколько одновременно исполняемых
(параллельных, конкурирующих) потоков,
называется переменной разделяемой
(shared) потоками.

13. Доступ параллельных потоков к разделяемым переменным

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

14. Примеры атомарных и неатомарных действий

shared x, y;
private a, b;
a = x;
y = b;
// атомарное действие
// атомарное действие
x = x + 1;
// неатомарное действие, которое эквивалентно
// следующей последовательности атомарных действий
private r;
r = x;
++r;
x = r;
x = y;
private r;
r = y;
x = r;
// неатомарное действие, которое эквивалентно
// следующей последовательности атомарных действий

15. 4.3. Параллельные потоки

16. Параллельные и псевдопараллельные потоки

• Одновременно исполняемые потоки
называются параллельными, если
каждый из них исполняется своим
процессором.
• Одновременно исполняемые потоки
называются псевдопараллельными
или конкурирующими (concurrent),
если они исполняются одним
процессором.

17. Обмен сигналами между параллельными потоками

• Мы рассматриваем параллельные потоки как
программы, параллельно исполняемыми на
одном компьютере.
• В общем случае параллельные потоки могут
обмениваться сигналами только через общую
память.
• В случае параллельных потоков,
исполняемых в контексте одного процесса,
общая память представляется
разделяемыми (глобальными) переменными.

18. Аксиомы параллельности

• Аксиома 1 (Non-interference postulate). Параллельные потоки,
которые не имеют общих разделяемых переменных, не
взаимодействуют (интерферируют) друг с другом.
• Аксиома 2 (Atomicity postulate). Операции чтения и записи
значения частной переменной потока в разделяемые
переменные являются атомарными.
• Аксиома 3 (Interleaving postulate – Постулат чередования).
Результатом исполнения псевдопараллельных (конкурирующих)
потоков является последовательность атомарных действий
этих потоков.

19. Гонка потоков

• Если результат исполнения псевдопараллельных
потоков зависит от последовательности атомарных
действий, исполняемых этими потоками, то говорят,
что эти потоки находятся в состоянии гонки (race
condition).
• Как правило, состояние гонки является причиной
ошибок работы многопоточных приложений.
• Причиной состояния гонки потоков является
неправильная синхронизация этих потоков.

20. 4.4. Определение синхронизации

21. Определение синхронизации

• Неформально, под синхронизацией параллельных
потоков понимают обмен между этими потоками
управляющими сигналами, которые координируют их
исполнение.
• Если
рассматривать
параллельные
потоки
формально, то синхронизация таких потоков это
достижение некоторого фиксированного порядка
(соотношения) между управляющими сигналами,
которыми обмениваются эти потоки.

22.

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

23. Определение условного атомарного действия

• Поэтому, под синхронизацией
параллельных потоков понимаем исполнение
потоком атомарного действия в зависимости
от некоторого условия.
• Такое атомарное действие называется
условным.
• Другими словами, с точки зрения
синхронизации потоков каждый поток
последовательно исполняет условные
атомарные действия.

24. Обозначение условного атомарного действия

• Введем для условного атомарного
действия следующее обозначение:
<await(условие) действие>
• где условие является логическим
(булевым) выражением, значением
которого является истина или ложь.

25. Исполнение условного атомарного действия

• Условное атомарное действие выполняется
следующим образом:
– оператор await ждет до тех пор, пока значение условия не
станет истинным;
– как только условие стало истинным, выполняется действие.
• В общем случае не существует эффективной
реализации условного атомарного действия.
• Поэтому на практике рассматривают его частные
случаи:
– взаимное исключение,
– условная синхронизация.

26. Взаимное исключение

• Взаимное исключение.
<await(true) действие> := <действие>
• В этом случае происходит безусловное
выполнение атомарного действия.
• Этот случай называется взаимным
исключением.
• Код, исполняемый внутри атомарного
действия, называется критической
секцией.

27. Условная синхронизация

• Условная синхронизация.
<await(условие)>
• В этом случае оператор await просто
оповещает о наступлении некоторого
события, т. е. что произошло некоторое
действие.
• Этот случай называется условная
синхронизация.

28. 4.5. Проблема взаимного исключения

29. Формулировка проблемы

• Проблема взаимного исключения возникает при
решении задачи ограничения совместного доступа
параллельных потоков к общему ресурсу.
• Формулировка проблемы: требуется обеспечить,
чтобы в любой момент времени с общим ресурсом
мог работать только один из параллельных
потоков.
• Для решения этой задачи, программный код, который
работает с общим ресурсом, заключается в
критическую секцию.

30. Требования к решению задачи взаимного исключения

1. Безопасность (safety requirement) – в любой
момент времен в критической секции может
находиться только один поток;
2. Поступательность (progress requirement) – любой
поток должен находиться в критической секции
ограниченное время (нет тупиков);
3. Справедливость (fairness requirement) – любой
поток получает доступ в критическую секцию за
ограниченное время (нет голодания).

31.

• Можно отметить, что из выполнения
требования 3 следует выполнение
требования 2.
• Однако требование 3 иногда
невозможно выполнить.
• В этом случае доказывают, что
решение задачи удовлетворяет только
требованию 2.

32. 4.6. Программное решение проблемы взаимного исключения

33.

• Программное решение проблемы
взаимного исключения для двух
параллельных потоков было впервые
дано Петерсоном (Peterson G. L., 1981).

34. Алгоритм Петерсона

bool x1, x2;
int q;
// обеспечивает ассиметричное решение задачи взаимного исключения
x1 = false;
x2 = false;
void thread1()
{
while (true)
{
nonCriticalSection1();
x1 = true;
q = 2;
while (x2 && q == 2);
criticalSection1();
x1 = false;
}
}
// поток 1 хочет войти в критическую секцию
// но, сначала предоставляет право входа потоку 2
// ждет, пока поток 2 находится в своей критич. секции

35.

void thread2()
{
while (true)
{
nonCriticalSection2();
x2 = true;
q = 1;
while (x1 && q == 1);
criticalSection2();
x2 = false;
}
}

36. Доказательство правильности алгоритма Петерсона

• 1. Безопасность.
– Поток thread1 находится в критической секции 1
только в том случае, если выполняется условие:
(( x2 q 2) 0) (( x2 q 2) 1)
(( x2 q 2) 1) (( x2 q 1) 1)
– Кроме того, если поток thread1 находится в
критической секции 1, то выполняется условие:
( x1 true) 1

37.

– Определим следующий предикат:
Q1 x1 ( x2 q 1)
– который является инвариантом
критической секции 1, т. е. если поток
thread1 находится внутри критической
секции 1, то выполняется условие:
Q1 1
– Аналогично, введем инвариант для
критической секции 2:
Q2 x2 ( x1 q 2)

38.

– Теперь рассмотрим предикат:
Q1 Q 2 ( x1 ( x 2 q 1)) ( x 2 ( x1 q 2))
( x1 x 2) ( x1 q 2) ( x 2 q 1)
( x1 x 2) (( x1 x 2) ( x1 q 1) ( x 2 q 2) (q 1 q 2))
( x1 x1 x 2 x 2) ( x1 x 2 x1 q 1) ( x1 x 2 x 2 q 2) 0
– В результате получили, что
Q1 Q2 0
– Следовательно, потоки thread1 и thread2
не могут одновременно находиться в своих
критических секциях.

39.

• 2. Поступательность.
– Поток thread1 может быть заблокирован
только при условии, если
( x2 q 2) 1
– Аналогично, поток thread2 может быть
заблокирован только при условии, если
( x1 q 1) 1

40.

– Рассмотрим предикат
( x 2 q 2) ( x1 q 1)
x1 x 2 q 1 q 2 0
0
– Следовательно, потоки thread1 и thread2
не могут быть заблокированы
одновременно.

41.

• 3. Справедливость.
– Предположим обратное, т. е., что поток
thread1 заблокирован. Тогда выполняется
условие
( x2 q 2) 1
– Отсюда следует, что
x2 1 (q 2) 1
(1)

42.

– Но из пункта 2 следует, что поток thread2 не может
быть заблокирован одновременно с потоком
thread1.
– Откуда следует, что выполняется условие
( x1 q 1) 1
– Следовательно, поток thread2 пройдет цикл while
и установит значения
x2 false
или
q 1
что противоречит условию (1).
– Следовательно, наше предположение неверно.
– Поэтому требование справедливости также
выполняется.

43. 4.7. Программное решение условной синхронизации

44. Решение проблемы условной синхронизации для двух потоков

bool event;
event = false;
void thread1()
{
beforeEvent1();
while(!event); // ждать наступления события
afterEvent1();
}

45.

void thread2()
{
beforeEvent2();
event = true;
afterEvent2();
}
// установить событие
• Очевидно, что поток thread1 выполнит
функцию afterEvent1 только в том случае,
если поток thread2 установит истинным
значение переменной event.

46. 4.8. Непрерываемые (атомарные) команды микропроцессора

47. Определение атомарных команд микропроцессора

• Для решения задач синхронизации в
микропроцессорах существуют команды, которые
изменяют содержимое памяти атомарным образом,
т. е. не прерываются во время своего исполнения.
• При исполнении такой команды микропроцессор
«запирает» (закрывает доступ) шину передачи
данных.
• Поэтому эти команды могут использоваться для
синхронизации потоков, исполняемых на разных
процессорах.

48. Команда xchg

• В микропроцессоре Intel x86 существует команда
xchg (а в настоящее время и много других команд),
которая не прерывается во время своего исполнения
и реализует следующую функцию:
void xchg(register int r, int* x)
{
register int temp;
temp = r;
r = *x;
*x = temp;
}

49. Решение проблемы взаимного исключения для N-параллельных потоков

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

50. Решение

int lock = 0;
void thread_i()
{
while (true)
{
register int key_i = 1;
while (key_i == 1)
xchg(key_i, &lock);
criticalSection_i();
xchg(key_i, &lock);
nonCriticalSection_i();
}
}
// ключ для входа в критическую секцию
// ждем, пока вход закрыт
// выход из критической секции

51. Доказательство правильности работы алгоритма

• 1. Безопасность.
– Доказываем от противного.
– Предположим, что
– при некоторых
keyi 0
i j
и
key j 0
.
– Это может быть только в том случае, если одна команда
xchg прервала исполнение другой такой команды.
– Но это невозможно, так как команда xchg атомарная.
– Следовательно, наше предположение неверно и в
критической секции может находиться только один из
потоков.

52.

• 2. Поступательность.
– Доказываем от противного.
– Предположим, что все потоки выполняют циклы
while (key_i == 1) // ждем, пока вход закрыт
xchg(key_i, &lock);
– Отсюда следует,n что
key lock n 1
i
i 1
– Но это невозможно, так как величина
n
key lock n
i
i 1
является инвариантом в силу атомарности
команды xchg.
– Следовательно, тупик невозможен.

53.

• 3. Справедливость.
– О справедливости нельзя сказать
ничего определенного, так как не
задан порядок доступа процессоров к
шине данных.

54. Занятие ожиданием

• Программная и аппаратная реализации
синхронизации имеют существенный
недостаток:
– впустую тратится процессорное время в циклах
ожидания while для разрешения входа в
критическую секцию.
• Поэтому все эти алгоритмы синхронизации
получили общее название занятие
ожиданием (busy waiting).

55. Спин-лок

• Однако, аппаратная реализация
синхронизации используется в
мультипроцессорных системах, так как нет
другого решения.
• Цикл ожидания while с атомарными
командами микропроцессора называется
спин-локом, или спин-блокировкой, или
активным ожиданием (spin lock, иногда live
lock).