Содержание
- 2. 4.1. Атомарные действия (операции)
- 3. Определение действия и контекста действия Действием (action) называется изменение контекста потока. Контекстом действия называется область памяти,
- 4. Определение атомарного действия Действие называется атомарным (atomic action), или непрерываемым, или непрерывным если они удовлетворяет двум
- 5. Две группы атомарных действия Атомарные действия делят на две группы: элементарные атомарные действия (fine grained atomic
- 6. Элементарные атомарные действия К элементарным атомарным действиям относятся команды микропроцессора, которые не могут быть прерваны во
- 7. Непрерываемые команды микропроцессора Условно (теоретически) считают, что атомарными являются следующие команды микропроцессора: операции над данными, хранящимися
- 8. Составные атомарные действия К составным атомарным действиям относятся последовательности элементарных атомарных действий, которые не прерываются во
- 9. Маскирование прерываний Так как переключение между потоками происходит только по прерываниям, то на однопроцессорном компьютере атомарность
- 10. Маскирование прерываний Запрещение прерываний не обеспечивает атомарность составного действия на мультипроцессорной системе, т. к. в этом
- 11. 4.2. Частные и разделяемые переменные
- 12. Определение частной и разделяемой переменной Переменная, доступ к которой имеет только один поток, называется частной (private)
- 13. Доступ параллельных потоков к разделяемым переменным Предполагаем, что параллельные потоки для доступа (записи или чтения) к
- 14. Примеры атомарных и неатомарных действий shared x, y; private a, b; a = x; // атомарное
- 15. 4.3. Параллельные потоки
- 16. Параллельные и псевдопараллельные потоки Одновременно исполняемые потоки называются параллельными, если каждый из них исполняется своим процессором.
- 17. Обмен сигналами между параллельными потоками Мы рассматриваем параллельные потоки как программы, параллельно исполняемыми на одном компьютере.
- 18. Аксиомы параллельности Аксиома 1 (Non-interference postulate). Параллельные потоки, которые не имеют общих разделяемых переменных, не взаимодействуют
- 19. Гонка потоков Если результат исполнения псевдопараллельных потоков зависит от последовательности атомарных действий, исполняемых этими потоками, то
- 20. 4.4. Определение синхронизации
- 21. Определение синхронизации Неформально, под синхронизацией параллельных потоков понимают обмен между этими потоками управляющими сигналами, которые координируют
- 22. Порядок управляющих сигналов обеспечивает некоторые фиксированные последовательности атомарных действий, исполняемых параллельными потоками. Следовательно, можно сказать, что
- 23. Определение условного атомарного действия Поэтому, под синхронизацией параллельных потоков понимаем исполнение потоком атомарного действия в зависимости
- 24. Обозначение условного атомарного действия Введем для условного атомарного действия следующее обозначение: где условие является логическим (булевым)
- 25. Исполнение условного атомарного действия Условное атомарное действие выполняется следующим образом: оператор await ждет до тех пор,
- 26. Взаимное исключение. := В этом случае происходит безусловное выполнение атомарного действия. Этот случай называется взаимным исключением.
- 27. Условная синхронизация Условная синхронизация. В этом случае оператор await просто оповещает о наступлении некоторого события, т.
- 28. 4.5. Проблема взаимного исключения
- 29. Формулировка проблемы Проблема взаимного исключения возникает при решении задачи ограничения совместного доступа параллельных потоков к общему
- 30. Требования к решению задачи взаимного исключения Безопасность (safety requirement) – в любой момент времен в критической
- 31. Можно отметить, что из выполнения требования 3 следует выполнение требования 2. Однако требование 3 иногда невозможно
- 32. 4.6. Программное решение проблемы взаимного исключения
- 33. Программное решение проблемы взаимного исключения для двух параллельных потоков было впервые дано Петерсоном (Peterson G. L.,
- 34. Алгоритм Петерсона bool x1, x2; int q; // обеспечивает ассиметричное решение задачи взаимного исключения x1 =
- 35. void thread2() { while (true) { nonCriticalSection2(); x2 = true; q = 1; while (x1 &&
- 36. Доказательство правильности алгоритма Петерсона 1. Безопасность. Поток thread1 находится в критической секции 1 только в том
- 37. Определим следующий предикат: который является инвариантом критической секции 1, т. е. если поток thread1 находится внутри
- 38. Теперь рассмотрим предикат: В результате получили, что Следовательно, потоки thread1 и thread2 не могут одновременно находиться
- 39. 2. Поступательность. Поток thread1 может быть заблокирован только при условии, если Аналогично, поток thread2 может быть
- 40. Рассмотрим предикат Следовательно, потоки thread1 и thread2 не могут быть заблокированы одновременно.
- 41. 3. Справедливость. Предположим обратное, т. е., что поток thread1 заблокирован. Тогда выполняется условие (1) Отсюда следует,
- 42. Но из пункта 2 следует, что поток thread2 не может быть заблокирован одновременно с потоком thread1.
- 43. 4.7. Программное решение условной синхронизации
- 44. Решение проблемы условной синхронизации для двух потоков bool event; event = false; void thread1() { beforeEvent1();
- 45. void thread2() { beforeEvent2(); event = true; // установить событие afterEvent2(); } Очевидно, что поток thread1
- 46. 4.8. Непрерываемые (атомарные) команды микропроцессора
- 47. Определение атомарных команд микропроцессора Для решения задач синхронизации в микропроцессорах существуют команды, которые изменяют содержимое памяти
- 48. Команда xchg В микропроцессоре Intel x86 существует команда xchg (а в настоящее время и много других
- 49. Решение проблемы взаимного исключения для N-параллельных потоков С помощью команды xchg можно решить проблему взаимного исключения
- 50. Решение int lock = 0; void thread_i() { while (true) { register int key_i = 1;
- 51. Доказательство правильности работы алгоритма 1. Безопасность. Доказываем от противного. Предположим, что и при некоторых . Это
- 52. 2. Поступательность. Доказываем от противного. Предположим, что все потоки выполняют циклы while (key_i == 1) //
- 53. 3. Справедливость. О справедливости нельзя сказать ничего определенного, так как не задан порядок доступа процессоров к
- 54. Занятие ожиданием Программная и аппаратная реализации синхронизации имеют существенный недостаток: впустую тратится процессорное время в циклах
- 56. Скачать презентацию