Похожие презентации:
Синхронизация потоков
1. 4. Синхронизация потоков
2. 4.1. Атомарные действия (операции)
3. Определение действия и контекста действия
• Действием (action) называется изменениеконтекста потока.
• Контекстом действия называется область
памяти, к которой действие имеет доступ.
4. Определение атомарного действия
• Действие называется атомарным (atomicaction), или непрерываемым, или
непрерывным если они удовлетворяет двум
требованиям:
– не прерывается во время своего исполнения;
– контекст действия изменяется только самим
действием.
• Атомарные действия будем обозначать
следующим образом:
атомарное_действие := <действие>
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).