- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Синхронизация потоков презентация
Содержание
- 1. Синхронизация потоков
- 2. 4.1. Атомарные действия (операции)
- 3. Определение действия и контекста действия Действием (action)
- 4. Определение атомарного действия Действие называется атомарным (atomic
- 5. Две группы атомарных действия Атомарные действия делят
- 6. Элементарные атомарные действия К элементарным атомарным действиям
- 7. Непрерываемые команды микропроцессора Условно (теоретически) считают, что
- 8. Составные атомарные действия К составным атомарным действиям
- 9. Маскирование прерываний Так как переключение между потоками
- 10. Маскирование прерываний Запрещение прерываний не обеспечивает атомарность
- 11. 4.2. Частные и разделяемые переменные
- 12. Определение частной и разделяемой переменной Переменная, доступ
- 13. Доступ параллельных потоков к разделяемым переменным Предполагаем,
- 14. Примеры атомарных и неатомарных действий shared x,
- 15. 4.3. Параллельные потоки
- 16. Параллельные и псевдопараллельные потоки Одновременно исполняемые потоки
- 17. Обмен сигналами между параллельными потоками Мы рассматриваем
- 18. Аксиомы параллельности Аксиома 1 (Non-interference postulate). Параллельные
- 19. Гонка потоков Если результат исполнения псевдопараллельных потоков
- 20. 4.4. Определение синхронизации
- 21. Определение синхронизации Неформально, под синхронизацией параллельных потоков
- 22. Порядок управляющих сигналов обеспечивает некоторые фиксированные последовательности
- 23. Определение условного атомарного действия Поэтому, под синхронизацией
- 24. Обозначение условного атомарного действия Введем для
- 25. Исполнение условного атомарного действия Условное атомарное действие
- 26. Взаимное исключение. := В этом
- 27. Условная синхронизация Условная синхронизация. В
- 28. 4.5. Проблема взаимного исключения
- 29. Формулировка проблемы Проблема взаимного исключения возникает при
- 30. Требования к решению задачи взаимного исключения Безопасность
- 31. Можно отметить, что из выполнения требования 3
- 32. 4.6. Программное решение проблемы взаимного исключения
- 33. Программное решение проблемы взаимного исключения для двух
- 34. Алгоритм Петерсона bool x1, x2;
- 35. void thread2() {
- 36. Доказательство правильности алгоритма Петерсона 1. Безопасность. Поток
- 37. Определим следующий предикат: который является инвариантом
- 38. Теперь рассмотрим предикат:
- 39. 2. Поступательность. Поток thread1 может быть заблокирован
- 40. Рассмотрим предикат Следовательно, потоки
- 41. 3. Справедливость. Предположим обратное, т. е., что
- 42. Но из пункта 2 следует, что поток
- 43. 4.7. Программное решение условной синхронизации
- 44. Решение проблемы условной синхронизации для двух потоков
- 45. void thread2() {
- 46. 4.8. Непрерываемые (атомарные) команды микропроцессора
- 47. Определение атомарных команд микропроцессора Для решения задач
- 48. Команда xchg В микропроцессоре Intel x86 существует
- 49. Решение проблемы взаимного исключения для N-параллельных потоков
- 50. Решение int lock = 0;
- 51. Доказательство правильности работы алгоритма 1. Безопасность. Доказываем
- 52. 2. Поступательность. Доказываем от противного. Предположим, что
- 53. 3. Справедливость. О справедливости нельзя сказать ничего
- 54. Занятие ожиданием Программная и аппаратная реализации синхронизации
- 55. Спин-лок Однако, аппаратная реализация синхронизации используется в
4.1. Атомарные действия (операции)
Слайд 3Определение действия и контекста действия
Действием (action) называется изменение контекста потока.
Контекстом действия
называется область памяти, к которой действие имеет доступ.
Слайд 4Определение атомарного действия
Действие называется атомарным (atomic action), или непрерываемым, или непрерывным
если они удовлетворяет двум требованиям:
не прерывается во время своего исполнения;
контекст действия изменяется только самим действием.
Атомарные действия будем обозначать следующим образом:
атомарное_действие := <действие>
не прерывается во время своего исполнения;
контекст действия изменяется только самим действием.
Атомарные действия будем обозначать следующим образом:
атомарное_действие := <действие>
Слайд 5Две группы атомарных действия
Атомарные действия делят на две группы:
элементарные атомарные действия
(fine grained atomic actions);
составные атомарные действия (coarse grained atomic actions).
составные атомарные действия (coarse grained atomic actions).
Слайд 6Элементарные атомарные действия
К элементарным атомарным действиям относятся команды микропроцессора, которые не
могут быть прерваны во время своего исполнения.
Слайд 7Непрерываемые команды микропроцессора
Условно (теоретически) считают, что атомарными являются следующие команды микропроцессора:
операции
над данными, хранящимися в регистрах микропроцессора;
операции чтения данных из памяти в регистры микропроцессора;
операции записи данных в память из регистров микропроцессора.
операции чтения данных из памяти в регистры микропроцессора;
операции записи данных в память из регистров микропроцессора.
Слайд 8Составные атомарные действия
К составным атомарным действиям относятся последовательности элементарных атомарных действий,
которые не прерываются во время своего исполнения.
Слайд 9Маскирование прерываний
Так как переключение между потоками происходит только по прерываниям, то
на однопроцессорном компьютере атомарность составного действия обеспечивается запрещением (маскированием) прерываний:
disable_interrupt();
составное_действие;
enable_interrupt();
disable_interrupt();
составное_действие;
enable_interrupt();
Слайд 10Маскирование прерываний
Запрещение прерываний не обеспечивает атомарность составного действия на мультипроцессорной системе,
т. к. в этом случае контекст действия, исполняемого одним процессором, может параллельно измениться потоком, исполняемым другим процессором.
Слайд 12Определение частной и разделяемой переменной
Переменная, доступ к которой имеет только один
поток, называется частной (private) или личной переменной потока.
Переменная, доступ к которой имеют несколько одновременно исполняемых (параллельных, конкурирующих) потоков, называется переменной разделяемой (shared) потоками.
Переменная, доступ к которой имеют несколько одновременно исполняемых (параллельных, конкурирующих) потоков, называется переменной разделяемой (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;
y = b; // атомарное действие
x = x + 1; // неатомарное действие, которое эквивалентно
// следующей последовательности атомарных действий
private r;
r = x;
++r;
x = r;
x = y; // неатомарное действие, которое эквивалентно
// следующей последовательности атомарных действий
private r;
r = y;
x = r;
Слайд 16Параллельные и псевдопараллельные потоки
Одновременно исполняемые потоки называются параллельными, если каждый из
них исполняется своим процессором.
Одновременно исполняемые потоки называются псевдопараллельными или конкурирующими (concurrent), если они исполняются одним процессором.
Одновременно исполняемые потоки называются псевдопараллельными или конкурирующими (concurrent), если они исполняются одним процессором.
Слайд 17Обмен сигналами между параллельными потоками
Мы рассматриваем параллельные потоки как программы, параллельно
исполняемыми на одном компьютере.
В общем случае параллельные потоки могут обмениваться сигналами только через общую память.
В случае параллельных потоков, исполняемых в контексте одного процесса, общая память представляется разделяемыми (глобальными) переменными.
В общем случае параллельные потоки могут обмениваться сигналами только через общую память.
В случае параллельных потоков, исполняемых в контексте одного процесса, общая память представляется разделяемыми (глобальными) переменными.
Слайд 18Аксиомы параллельности
Аксиома 1 (Non-interference postulate). Параллельные потоки, которые не имеют общих
разделяемых переменных, не взаимодействуют (интерферируют) друг с другом.
Аксиома 2 (Atomicity postulate). Операции чтения и записи значения частной переменной потока в разделяемые переменные являются атомарными.
Аксиома 3 (Interleaving postulate – Постулат чередования). Результатом исполнения псевдопараллельных (конкурирующих) потоков является последовательность атомарных действий этих потоков.
Аксиома 2 (Atomicity postulate). Операции чтения и записи значения частной переменной потока в разделяемые переменные являются атомарными.
Аксиома 3 (Interleaving postulate – Постулат чередования). Результатом исполнения псевдопараллельных (конкурирующих) потоков является последовательность атомарных действий этих потоков.
Слайд 19Гонка потоков
Если результат исполнения псевдопараллельных потоков зависит от последовательности атомарных действий,
исполняемых этими потоками, то говорят, что эти потоки находятся в состоянии гонки (race condition).
Как правило, состояние гонки является причиной ошибок работы многопоточных приложений.
Причиной состояния гонки потоков является неправильная синхронизация этих потоков.
Как правило, состояние гонки является причиной ошибок работы многопоточных приложений.
Причиной состояния гонки потоков является неправильная синхронизация этих потоков.
Слайд 21Определение синхронизации
Неформально, под синхронизацией параллельных потоков понимают обмен между этими потоками
управляющими сигналами, которые координируют их исполнение.
Если рассматривать параллельные потоки формально, то синхронизация таких потоков это достижение некоторого фиксированного порядка (соотношения) между управляющими сигналами, которыми обмениваются эти потоки.
Если рассматривать параллельные потоки формально, то синхронизация таких потоков это достижение некоторого фиксированного порядка (соотношения) между управляющими сигналами, которыми обмениваются эти потоки.
Слайд 22Порядок управляющих сигналов обеспечивает некоторые фиксированные последовательности атомарных действий, исполняемых параллельными
потоками.
Следовательно, можно сказать, что синхронизация параллельных потоков – это упорядочивание атомарных действий, исполняемых этими потоками.
Следовательно, можно сказать, что синхронизация параллельных потоков – это упорядочивание атомарных действий, исполняемых этими потоками.
Слайд 23Определение условного атомарного действия
Поэтому, под синхронизацией параллельных потоков понимаем исполнение потоком
атомарного действия в зависимости от некоторого условия.
Такое атомарное действие называется условным.
Другими словами, с точки зрения синхронизации потоков каждый поток последовательно исполняет условные атомарные действия.
Такое атомарное действие называется условным.
Другими словами, с точки зрения синхронизации потоков каждый поток последовательно исполняет условные атомарные действия.
Слайд 24Обозначение условного атомарного действия
Введем для условного атомарного действия следующее обозначение:
действие>
где условие является логическим (булевым) выражением, значением которого является истина или ложь.
где условие является логическим (булевым) выражением, значением которого является истина или ложь.
Слайд 25Исполнение условного атомарного действия
Условное атомарное действие выполняется следующим образом:
оператор await ждет
до тех пор, пока значение условия не станет истинным;
как только условие стало истинным, выполняется действие.
В общем случае не существует эффективной реализации условного атомарного действия.
Поэтому на практике рассматривают его частные случаи:
взаимное исключение,
условная синхронизация.
как только условие стало истинным, выполняется действие.
В общем случае не существует эффективной реализации условного атомарного действия.
Поэтому на практике рассматривают его частные случаи:
взаимное исключение,
условная синхронизация.
Слайд 26Взаимное исключение.
:=
В этом случае происходит безусловное выполнение атомарного
действия.
Этот случай называется взаимным исключением.
Код, исполняемый внутри атомарного действия, называется критической секцией.
Этот случай называется взаимным исключением.
Код, исполняемый внутри атомарного действия, называется критической секцией.
Взаимное исключение
Слайд 27Условная синхронизация
Условная синхронизация.
В этом случае оператор await просто оповещает о
наступлении некоторого события, т. е. что произошло некоторое действие.
Этот случай называется условная синхронизация.
Этот случай называется условная синхронизация.
Слайд 29Формулировка проблемы
Проблема взаимного исключения возникает при решении задачи ограничения совместного доступа
параллельных потоков к общему ресурсу.
Формулировка проблемы: требуется обеспечить, чтобы в любой момент времени с общим ресурсом мог работать только один из параллельных потоков.
Для решения этой задачи, программный код, который работает с общим ресурсом, заключается в критическую секцию.
Формулировка проблемы: требуется обеспечить, чтобы в любой момент времени с общим ресурсом мог работать только один из параллельных потоков.
Для решения этой задачи, программный код, который работает с общим ресурсом, заключается в критическую секцию.
Слайд 30Требования к решению задачи взаимного исключения
Безопасность (safety requirement) – в любой
момент времен в критической секции может находиться только один поток;
Поступательность (progress requirement) – любой поток должен находиться в критической секции ограниченное время (нет тупиков);
Справедливость (fairness requirement) – любой поток получает доступ в критическую секцию за ограниченное время (нет голодания).
Поступательность (progress requirement) – любой поток должен находиться в критической секции ограниченное время (нет тупиков);
Справедливость (fairness requirement) – любой поток получает доступ в критическую секцию за ограниченное время (нет голодания).
Слайд 31Можно отметить, что из выполнения требования 3 следует выполнение требования 2.
Однако
требование 3 иногда невозможно выполнить.
В этом случае доказывают, что решение задачи удовлетворяет только требованию 2.
В этом случае доказывают, что решение задачи удовлетворяет только требованию 2.
Слайд 33Программное решение проблемы взаимного исключения для двух параллельных потоков было впервые
дано Петерсоном (Peterson G. L., 1981).
Слайд 34Алгоритм Петерсона
bool x1, x2;
int q; // обеспечивает ассиметричное решение задачи
взаимного исключения
x1 = false;
x2 = false;
void thread1()
{
while (true)
{
nonCriticalSection1();
x1 = true; // поток 1 хочет войти в критическую секцию
q = 2; // но, сначала предоставляет право входа потоку 2
while (x2 && q == 2); // ждет, пока поток 2 находится в своей критич. секции
criticalSection1();
x1 = false;
}
}
x1 = false;
x2 = false;
void thread1()
{
while (true)
{
nonCriticalSection1();
x1 = true; // поток 1 хочет войти в критическую секцию
q = 2; // но, сначала предоставляет право входа потоку 2
while (x2 && q == 2); // ждет, пока поток 2 находится в своей критич. секции
criticalSection1();
x1 = false;
}
}
Слайд 35 void thread2()
{
while (true)
{
nonCriticalSection2();
x2 = true;
q = 1;
while (x1 && q == 1);
criticalSection2();
x2 = false;
}
}
x2 = true;
q = 1;
while (x1 && q == 1);
criticalSection2();
x2 = false;
}
}
Слайд 36Доказательство правильности алгоритма Петерсона
1. Безопасность.
Поток thread1 находится в критической секции 1
только в том случае, если выполняется условие:
Кроме того, если поток thread1 находится в критической секции 1, то выполняется условие:
Кроме того, если поток thread1 находится в критической секции 1, то выполняется условие:
Слайд 37Определим следующий предикат:
который является инвариантом критической секции 1, т. е. если
поток thread1 находится внутри критической секции 1, то выполняется условие:
Аналогично, введем инвариант для критической секции 2:
Аналогично, введем инвариант для критической секции 2:
Слайд 38Теперь рассмотрим предикат:
В результате получили, что
Следовательно, потоки thread1 и thread2 не
могут одновременно находиться в своих критических секциях.
Слайд 392. Поступательность.
Поток thread1 может быть заблокирован только при условии, если
Аналогично, поток
thread2 может быть заблокирован только при условии, если
Слайд 40Рассмотрим предикат
Следовательно, потоки thread1 и thread2 не могут быть заблокированы одновременно.
Слайд 413. Справедливость.
Предположим обратное, т. е., что поток thread1 заблокирован. Тогда выполняется
условие
(1)
Отсюда следует, что
(1)
Отсюда следует, что
Слайд 42Но из пункта 2 следует, что поток thread2 не может быть
заблокирован одновременно с потоком thread1.
Откуда следует, что выполняется условие
Следовательно, поток thread2 пройдет цикл while и установит значения
или
что противоречит условию (1).
Следовательно, наше предположение неверно.
Поэтому требование справедливости также выполняется.
Откуда следует, что выполняется условие
Следовательно, поток thread2 пройдет цикл while и установит значения
или
что противоречит условию (1).
Следовательно, наше предположение неверно.
Поэтому требование справедливости также выполняется.
Слайд 44Решение проблемы условной синхронизации для двух потоков
bool event;
event =
false;
void thread1()
{
beforeEvent1();
while(!event); // ждать наступления события
afterEvent1();
}
void thread1()
{
beforeEvent1();
while(!event); // ждать наступления события
afterEvent1();
}
Слайд 45 void thread2()
{
beforeEvent2();
event = true;
// установить событие
afterEvent2();
}
Очевидно, что поток thread1 выполнит функцию afterEvent1 только в том случае, если поток thread2 установит истинным значение переменной event.
afterEvent2();
}
Очевидно, что поток thread1 выполнит функцию afterEvent1 только в том случае, если поток thread2 установит истинным значение переменной event.
Слайд 47Определение атомарных команд микропроцессора
Для решения задач синхронизации в микропроцессорах существуют команды,
которые изменяют содержимое памяти атомарным образом, т. е. не прерываются во время своего исполнения.
При исполнении такой команды микропроцессор «запирает» (закрывает доступ) шину передачи данных.
Поэтому эти команды могут использоваться для синхронизации потоков, исполняемых на разных процессорах.
При исполнении такой команды микропроцессор «запирает» (закрывает доступ) шину передачи данных.
Поэтому эти команды могут использоваться для синхронизации потоков, исполняемых на разных процессорах.
Слайд 48Команда xchg
В микропроцессоре Intel x86 существует команда xchg (а в настоящее
время и много других команд), которая не прерывается во время своего исполнения и реализует следующую функцию:
void xchg(register int r, int* x)
{
register int temp;
temp = r;
r = *x;
*x = temp;
}
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();
}
}
{
register int key_i = 1; // ключ для входа в критическую секцию
while (key_i == 1) // ждем, пока вход закрыт
xchg(key_i, &lock);
criticalSection_i();
xchg(key_i, &lock); // выход из критической секции
nonCriticalSection_i();
}
}
Слайд 51Доказательство правильности работы алгоритма
1. Безопасность.
Доказываем от противного.
Предположим, что
и
при некоторых
.
Это может быть только в том случае, если одна команда xchg прервала исполнение другой такой команды.
Но это невозможно, так как команда xchg атомарная.
Следовательно, наше предположение неверно и в критической секции может находиться только один из потоков.
Слайд 522. Поступательность.
Доказываем от противного.
Предположим, что все потоки выполняют циклы
while (key_i ==
1) // ждем, пока вход закрыт
xchg(key_i, &lock);
Отсюда следует, что
Но это невозможно, так как величина
является инвариантом в силу атомарности команды xchg.
Следовательно, тупик невозможен.
xchg(key_i, &lock);
Отсюда следует, что
Но это невозможно, так как величина
является инвариантом в силу атомарности команды xchg.
Следовательно, тупик невозможен.
Слайд 533. Справедливость.
О справедливости нельзя сказать ничего определенного, так как не задан
порядок доступа процессоров к шине данных.
Слайд 54Занятие ожиданием
Программная и аппаратная реализации синхронизации имеют существенный недостаток:
впустую тратится
процессорное время в циклах ожидания while для разрешения входа в критическую секцию.
Поэтому все эти алгоритмы синхронизации получили общее название занятие ожиданием (busy waiting).
Поэтому все эти алгоритмы синхронизации получили общее название занятие ожиданием (busy waiting).
Слайд 55Спин-лок
Однако, аппаратная реализация синхронизации используется в мультипроцессорных системах, так как нет
другого решения.
Цикл ожидания while с атомарными командами микропроцессора называется спин-локом, или спин-блокировкой, или активным ожиданием (spin lock, иногда live lock).
Цикл ожидания while с атомарными командами микропроцессора называется спин-локом, или спин-блокировкой, или активным ожиданием (spin lock, иногда live lock).
