Параллельное программирование. Проблемы многопоточных приложений. Примитивы синхронизации потоков

1. Параллельное программирование

ПРОБЛЕМЫ МНОГОПОТОЧНЫХ
ПРИЛОЖЕНИЙ.
ПРИМИТИВЫ СИНХРОНИЗАЦИИ
ПОТОКОВ.

2. План лекции

Проблемы многопоточных приложений
◦ Введение
◦ Задачи читателей и писателей
◦ Задачи спящего парикмахера
◦ Не DeadLock
◦ Доступ к разделяемым данным
◦ Atomicity-Violation Bugs
◦ Order-Violation Bugs
◦ DeadLock
◦ Примеры MSSQL
◦ Примитивы синхронизации
◦
◦
◦
◦
◦
Критические секции
Мьютексы
Семафоры
События
Обработка таймаутов

3. Простое различие

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

4. Реализация параллельных вычислений

• Многопоточная
• Многопроцессная
• Распределенная

5. Parallelism vs Concurrency

6. Parallelism vs Concurrency

Сходства
◦ Более быстрое выполнение по
сравнению с одной очередью
◦ Последовательное выполнение в
рамках одной очереди
◦ Борьба за ресурсы
(теряется скорость паралеллизма)

7. Parallelism vs Concurrency

Отличия
◦ В случае Concurrency
◦ необходима очередь
◦ первый получает любой подарок
◦ В случае Parallelism
◦ очередь не нужна (выигрыш по скорости)
◦ заранее известно кто какой подарок
возьмет

8. Parallelism vs Concurrency

Лабораторная работа №1
◦ Concurrency ?
◦ Parallelism?

9. Проблемы

◦Shared resources
◦DeadLocks
◦ABA problem

10. Проблемы и примеры

◦ SharedResources
◦ Банковский счет (неверная запись переменной)
◦ Слишком много молока (одновременное выполнение действия)
◦ Проблема спящего парикмахера (неверное состояние системы)
◦ DeadLocks
◦ Проблема обедающих философов (взаимная блокировка, бездействие, простаивание)
◦ ABA problem

11. Проблемы и примеры

SharedResources

12. Гонки потоков. Банковский счет.

13. Гонки потоков. Терминал оператора.

14. Гонки потоков. Одновременное снятие.

15. Гонки потоков. Длительные операции.

16. Гонки потоков. Длительные операции.

Нужна блокировка двойного выполнения.
Варианты?

17. Гонки потоков. Длительные операции.

18. Критическая секция

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

19. Гонки потоков. Одновременное снятие.

Эксклюзивный
доступ
Код снятия со
счета
Решена ли проблема?

20. Гонки потоков. Двойное списание.

21. Гонки потоков. Невозможность снятия.

22. Гонки потоков. Невозможность снятия.

23. Гонки потоков. Подвисание интерфейса.

24. Гонки потоков. Подвисание интерфейса.

25. Гонки потоков. Трансфер денег.

26. SharedResources. Безопасная запись.

◦ Доступ к ресурсу не изменяет ресурс – например операция чтения;
◦ Изменение данных является идемпотентным – повторные запросы на
изменение приводят к одинаковому результату;
◦ Изменение данных выполняется только одним объектом –
персональный доступ, критическая секция.

27. Проблемы и примеры

DeadLocks

28. Гонки потоков. Взаимная блокировка.

29. DeadLock

30. DeadLock

31. Проблема обедающих философов.

◦ Пять философов
◦ Перед каждым тарелка спагетти.
◦ Между парой философов вилка.
◦ Либо есть двумя вилками
◦ Либо размышлять
◦ Может посмотреть и взять ближайшую вилку,
если она доступна
◦ Может положить вилку

32. Проблема обедающих философов.

Нужен алгоритм действия философов.
Варианты?

33. Еще проблемы

◦ Livelock – потоки работают, но ничего не делают, потому как
не могут захватить все необходимые ресурсы.
◦ Starvation (голодание) – потоку может совсем не доставаться
ресурсов.
◦ Lack of fairness – кому-то достается больше ресурсов, кому то
меньше.
◦ Shared Resources –
◦ DeadLocks –
◦ ABA - ??

34. DeadLocks

◦
◦
◦
◦
Соблюдать последовательность входа и выхода в критические секции
Использовать библиотечные классы (std, boost)
Обрабатывать исключения
Использовать правильную стратегию синхронизации

35. Примитивы синхронизации потоков.

◦
◦
◦
◦
Простые блокирующие методы
Блокирующие конструкции
Сигналы
Неблокирующие конструкции

36. Примитивы синхронизации потоков.

Простые блокирующие методы

37. Простые блокирующие методы

◦ Wait
◦ Sleep
◦ Join

38. Простые блокирующие методы

Ожидание может завершиться по следующим причинам:
◦ Выполнилось условие ожидания
◦ Закончилось время ожидания
◦ Поток прерван функцией TerminateThread

39. Простые блокирующие методы. Условие ожидания

Минусы:
◦ Нагрузка на процессор
◦ Простои

40. Простые блокирующие методы. Таймаут

WaitForSingleObject(.. INFINITE)
WaitForMultipleObjects(.. INFINITE)

41. Примитивы синхронизации потоков.

Блокирующие конструкции

42. Блокирующие конструкции

◦ Семафор — объект, ограничивающий количество потоков, которые
могут войти в заданный участок кода.
◦ Мьютекс – семафор, разрешающий вход только одному потоку.

43. С++ Критическая секция

1.
Назначение: предоставление доступа ОДНОМУ потоку
2.
Скорость: высокая
3.
Область видимости: процесс
4.
Пример:
1.
2.
3.
4.
5.
6.
CRITICAL_SECTION cs;
InitializeCriticalSection( &cs);
EnterCriticalSection( &cs);
// ?? Только один поток
LeaveCriticalSection( &cs);
DeleteCriticalSection( &cs);

44. С++ Мьютекс

Именованная критическая секция, доступная для использования в
рамках операционной системы.
1.
Назначение: предоставление доступа ОДНОМУ потоку
2.
Скорость: медленнее
3.
Область видимости: ОС
4.
Пример:
1.
2.
3.
4.
5.
6.
HANDLE hMutex;
hMutex = CreateMutex( NULL, false, NULL);
WaitForSingleObject(hMutex, INFINITE);
// ?? Только один поток
ReleaseMutex( hMutex);
CloseHandle( &cs);

45. С++ Семафор

1.
Назначение: предоставление доступа НЕСКОЛЬКИМ потокам
2.
Скорость: медленнее
3.
Область видимости: ОС
4.
Пример:
1.
2.
3.
4.
5.
HANDLE hSemaphore;
hSemaphore = CreateSemaphore(NULL, [CURRENT],[MAX], NULL);
WaitForSingleObject(hSemaphore, INFINITE);
// ?? Не более MAX потоков
ReleaseSemaphore(hSemaphore, 1, NULL);

46. Примитивы синхронизации потоков.

Сигналы

47. С++ Событие

1.
HANDLE hEvent;
2.
hEvent = CreateEvent(NULL, false (autoreset event), false, NULL);
3.
WaitForSingleObject(hEvent, INFINITE);
4.
// ?? один поток за счет autoreset
5.
CloseHandle(hEvent);

48. Список литературы

Википедия
◦ Введение
◦ https://habrahabr.ru/company/piter/blog/274569
◦ Проблемы параллельного программирования
◦ https://ru.wikipedia.org/wiki/Проблема_спящего_парикмахера
◦ https://ru.wikipedia.org/wiki/Проблема_обедающих_философов
◦ Threading in C#
◦ http://www.albahari.com/threading
◦ Best practices
◦ https://msdn.microsoft.com/en-us/library/ff601929.aspx
◦ https://msdn.microsoft.com/en-us/library/1c9txz50(v=vs.110).aspx

49. Введение в параллельное программирование

“To put it quite bluntly: as long as there were no
machines, programming was no problem at all;
when we had a few weak computers,
programming became a mild problem, and now
we have gigantic computers, programming has
become an equally gigantic problem."
-- E. Dijkstra, 1972 Turing Award Lecture

50. Знаменитый закон Мура

I Закон Мура (1965): каждые 2 года количество транзисторов в
интегральной микросхеме удваивается.
Следствие Хауса: производительность центрального процессора
компьютера удваивается каждые 18 месяцев.
Мур, 2007: закономерности перестанут работать вследствие
атомарной природы вещества и ограничения скорости света.

51. Вопросы