Похожие презентации:
cpp09
1. Осенний семестр Преподаватель: ст. преп. Чуканов В.С
Peter the GreatSaint-Petersburg Рolytechnic University
Наука Программирования
Занятие №9
Введение в параллельное программирование.
Decorator. NVI
Осенний семестр
Преподаватель: ст. преп. Чуканов В.С
2. Понятие потока
Thread – «легковесный» поток исполненияРегистры
Стэк
Указатель на текущую исполняемую инструкцию
Instruction pointer
main
async/thread
coroutines
2
Process
Thread
Fiber
3. Threads vs Fibers
ThreadsPre-emptive scheduling
Исполнение потока может быть прервано другим потоком по
решению ОС
Множество потоков единовременно совершают вычисления
+ Распараллеливание
- Общий доступ к данным
Fibers
Cooperative scheduling
Не прерываются другими fiber, выполняются до ключевой
команды – yield
и возобновляются далее по вызову
3
В некотором смысле - это user-managed thread
4. Парадигмы параллельного исполнения
Программирование на уровне задач{Задача + данные} => в отложенное исполнение
std::async
Программирование на уровне потоков
std::thread
Ручной менеджмент потоков
Есть возможность получить terminate()/создать
бесконечный поток при некорректной обработке
взаимодействий
4
5. std::async
template <class Fn, class... Args>future<typename result_of<Fn(Args...)>::type>
async (launch policy, Fn&& fn, Args&&... args);
Асинхронный запуск функции
Возвращает объект std::future
policy
std::launch::deferred
Отложенный запуск без создания нового потока
Запуск происходит на момент вызова get()/wait у future
std::launch::async
Для выполнения выделяется новый поток
std::launch::async | std::launch::deferred (По умолчанию)
Выделение потока не контролируется
5
6. std::future
Результат отложенного исполненияМожет быть создан только 3мя способами
async
promise::get_future
packaged_task::get_future
Future базируется на механизме «shared state»
Хранит статус исполнения отложенной функции
Когда ready – результат можно достать
Ожидание исполнения – wait()
Вызов get() осуществит wait() и вернет результат
исполнения отложенной функции
The behavior is undefined if valid() is false before the call to this
function.
Any shared state is released. valid() is false after a call to this member
function.
6
7. async + get: объявления/include
#include <iostream>#include <vector>
#include <algorithm>
#include <numeric>
#include <future>
#include <string>
struct X {
void foo(int i, std::string const& str) {
std::cout << str << ' ' << i << '\n';
}
void bar(std::string const& str) {
std::cout << str << '\n';
}
int operator()(int i) {
std::cout << i << '\n';
return i + 10;
}
};
7
8. async + get: вызов
int main(){
X x;
// Вызов (& x) -> foo (42, "Hello") с политикой по умолчанию:
// может одновременно напечатать "Hello 42" или отложить
выполнение
auto a1 = std::async(&X::foo, &x, 42, "Hello");
// Вызывает x.bar ("world!") С отложенной политикой
// выводит "мир!" когда вызывается a2.get () или a2.wait ()
auto a2 = std::async(std::launch::deferred, &X::bar, x,
"world!");
// Вызов X () (43); с асинхронной политикой
// одновременно выводит "43"
auto a3 = std::async(std::launch::async, X(), 43);
a2.wait();
// выводит "мир!"
std::cout << a3.get() << '\n'; // выводит "53"
} // если на этом этапе a1 не выполняется, деструктор a1 выводит
здесь "Hello 42"
8
9. Возможные результаты исполнения
910. Обоснование результатов
Исполнены все функцииВсе future, созданные с помощью async вызывают wait()
на деструкторе
Нестабильность результатов
Потоки используют std::cout как общий ресурс
Порядок операций в «линии времени» не
детерминирован
Подобная ситуация называется data race
10
«гонка данных»: кто быстрее получил доступ, тот и
выполнился первым
11. Параллельные алгоритмы стандартной библиотеки
Доступно с C++1760+ алгоритмов перегружено для параллельного
исполнения
Параллелизация по потокам и по данным
По потокам – одна задача на поток
По данным – одна инструкция для вектора данных
(SIMD)
Контроль исполнения осуществляется при помощи
execution_policy
std::execution::seq - последовательно
std::execution::par - параллельно
std::execution::par_unseq – параллельно + векторно
11
12. Параллельные алгоритмы
1213. std::sort
// Sort and time parallel.start = clk::now();
std::sort(std::execution::par_unseq, input_parallel.begin(),
input_parallel.end());
end = clk::now();
std::cout << "parallel " << std::chrono::duration<float>(end start).count() << " s" << std::endl;
// Sort and time serial.
start = clk::now();
std::sort(std::execution::seq, input_serial.begin(),
input_serial.end());
end = clk::now();
std::cout << "serial " << std::chrono::duration<float>(end start).count() << " s" << std::endl;
13
14. std::sort
I7 9700K 32Gb RAMЧисло элементов = 4 ∗ 108
14
15. std::packaged_task
async не допускает контроля распределенияпотоков
std::packaged_task - инструмент упаковки функции
в перемещаемый объект для выполнения в потоке
Конструируется от лямбды/функции
Сохраняет ее сигнатуру в operator ()
Вызов от аргументов передается в хранимую функцию
Возвращает std::future
template< class R, class ...ArgTypes >
class packaged_task<R(ArgTypes...)>;
15
16. packaged_task: пример
// unique function to avoid disambiguating the std::pow overload setint f(int x, int y) { return std::pow(x, y); }
void task_lambda()
{
std::packaged_task<int(int, int)> task( [](int a, int b) {
return std::pow(a, b);
});
std::future<int> result = task.get_future();
task(2, 9);
std::cout << "task_lambda:\t" << result.get() << '\n';
}
16
17. packaged_task: пример с bind
void task_bind(){
std::packaged_task<int()> task(std::bind(f, 2, 11));
std::future<int> result = task.get_future();
task();
std::cout << "task_bind:\t" << result.get() << '\n';
}
17
18. std::thread
Класс потокаСтатический метод для вычисления числа аппаратных
потоков
std::thread::hardware_concurrency
Исполняет переданную функцию от переданных
аргументов
Аргументы КОПИРУЮТСЯ
Для передачи объекта по ссылке необходимо «завернуть» его
в обертку std::ref/cref
join()
Синхронизирует исполнение потока с вызывающим
ВАЖНО
18
На деструкторе thread должен быть уже завершен (выполнен
join), в противном случае программа аварийно завершится
(std::terminate)
19. thread: example
int main() {std::thread first(foo);
// spawn new thread that calls foo()
std::thread second(bar, 0); // spawn new thread that calls bar(0)
std::cout << "main, foo and bar now execute concurrently...\n";
// synchronize threads:
first.join();
second.join();
// pauses until first finishes
// pauses until second finishes
std::cout << "foo and bar completed.\n";
return 0;
}
19
20. thread + packaged_task
void task_thread(){
std::packaged_task<int(int, int)> task(f);
std::future<int> result = task.get_future();
std::thread task_td(std::move(task), 2, 10);
task_td.join();
std::cout << "task_thread:\t" << result.get() << '\n';
}
20
21. mutex
MutexMutual exclusive
std::mutex
Создание мьютекса не вызывает блокировки доступа
Механизм блокировки доступа потока к секции кода
21
Секция кода = критическая секция
22. mutex
Механизм блокировкиПока объект «замок» существует – он «закрыт» тем потоком,
кто его создал
std::lock_guard lock(m)
До С++17, устаревшая реализация
std::scoped_lock lock(m)
На деструкторе замок снимается
Можно использовать для нескольких mutex сразу
Всегда можно локализовать замок, создав его в { }
std::unique_lock
Можно управлять блокировкой через lock()/unlock()
{
std::scoped_lock lock(cout_mutex);
std::cout << i << '\n';
}
return i + 10;
22
23. Mutex: Deadlock
Проблемабесконечного
ожидания
Два потока ждут
оба ресурса для
продолжения
исполнения
Решается через
scoped_lock
23
Либо через
std::lock()
mutex mut_a;
mutex mut_b;
static void deadlock_func_1() {
cout << "bad f1 acquiring mutex A..." << endl;
lock_guard<mutex> la{mut_a};
this_thread::sleep_for(100ms);
cout << "bad f1 acquiring mutex B..." << endl;
lock_guard<mutex> lb{mut_b};
cout << "bad f1 got both mutexes." << endl;
}
static void deadlock_func_2() {
cout << "bad f2 acquiring mutex B..." << endl;
lock_guard<mutex> lb{mut_b};
this_thread::sleep_for(100ms);
cout << "bad f2 acquiring mutex A..." << endl;
lock_guard<mutex> la{mut_a};
cout << "bad f2 got both mutexes." << endl;
}
void main () {
thread t1 {deadlock_func_1};
thread t2 {deadlock_func_2};
t1.join();
t2.join();
}
24. atomic
Атомарная операция — это операция, которуюневозможно наблюдать в промежуточном состоянии,
она либо выполнена, либо нет
std::atomic<int> a;
load – вернуть значение
store – записать значение
fetch_add – атомарно сложить и записать результат
обратно
compare_exchange_* - производит сравнение и замену
значения с новым
24
25. Сфера применения атомарных операций
Атомарные операции – инструмент реализациимодели памяти С++
Атомарные операции
… реализуют «неблокирующие» вызовы (lock-free)
Т.е. атомарность обеспечивается архитектурой процессора и
не требует блокировки остальных потоков
… задают отношение порядка в рамках инструкций
одного потока
Одни операции не могут быть начаты раньше, чем другие
25
… задают синхронизацию значений между потоками
26. Упорядочивание операций: memory_order_relaxed
Гарантирует только свойство атомарностине может участвовать в процессе синхронизации
данных между потоками
модификация переменной будет видна в другом
потоке не сразу
Второй поток "увидит" значения одной и той
же переменной в том же порядке, в котором
происходили её модификации в исходном потоке
порядок модификаций разных переменных в
потоке thread1 не сохранится в потоке thread2
26
27. Упорядочивание операций: memory_order_relaxed
Поток №1производит
вычисления, пока не
прерван извне
Поток №2
использует atomic
для установки флага
27
#include <atomic>
#include <iostream>
std::atomic<bool> stopped{ false };
void thread1() {
while (!stopped.load(std::memory_order_relaxed)) {
// ...
}
}
void thread2() {
stopped.store(true, std::memory_order_relaxed);
}
28. memory_order_relaxed: пример неверного использования
memory_order_relaxed не обеспечивает синхронизацию памятиОбеспечивается только передача флага ready
std::string data;
std::atomic<bool> ready{ false };
void thread1() {
data = "very important bytes";
ready.store(true, std::memory_order_relaxed);
}
void thread2() {
while (!ready.load(std::memory_order_relaxed));
std::cout << "data is ready: " << data << "\n"; //
potentially memory corruption is here
}
28
29. memory_order_relaxed: пример неверного использования
2930. Упорядочивание операций: sequential consistency
Самый строгий вариант упорядочивания операцийmemory_order_seq_cst
Порядок модификаций разных атомарных переменных
в потоке thread1 сохранится в потоке thread2
Все потоки будут видеть один и тот же порядок
модификации всех атомарных переменных. Сами
модификации могут происходить в разных потоках
Все модификации памяти (не только модификации
над атомиками) в потоке thread1, выполняющей store
на атомарной переменной, будут видны после
выполнения load этой же переменной в потоке thread2
30
31. memory_order_seq_cst: пример
3132. memory_order_seq_cst
Позволяет создавать упорядочивание операций спамятью между потоками (Lock-free)
Многопоточная программа может быть выполнена
только с memory_order_seq_cst, а дальнейшие
оптимизации – переход части флагов на
memory_order_relaxed
С сохранением корректности, разумеется
Предыдущий пример с relaxed будет работать с seq_cst
корректно
Более полный контроль и проектирование lock-
free структур данных дает
std::memory_order_acquire/
std::memory_order_release
32
33. NVI
Non virtual interfaceПаттерн для вынесения общей функциональности
в базовый класс
class AlgorithmBase {
public:
void run(Input const& in) {
using clk = std::chrono::high_resolution_clock;
decltype(clk::now()) start, end;
start = clk::now();
_run_virtual(in);
end = clk::now();
logTime(end - start);
}
protected:
virtual void _run_virtual(Input const& in) = 0;
};
33
34. Decorator
Задача: конструирование функциональности наран-тайме
Единицы функциональности могут быть собраны
в различных комбинациях
Количество комбинаций – экспоненциально?
Механизмы (множественного) наследования не
подходят
Функциональность задается для конкретных объектов,
а не классов
Комбинация ф-стей может существовать одна, а класс задает
множество объектов
34
35. Decorator
Общая наиболее значимая функциональность =>pure virtual
Декоратор
Наследник базового класса Base
Содержит указатель на декорируемый класс Base*
Декоратор делегирует вызов в декорируемый
класс
Наследники декоратора реализуются для каждой
новой единицы функциональности
Пользователь конструирует итоговую
функциональность цепочкой декораторов
35
36. Decorator: классы окон
3637. Decorator: решение через паттерн
virtual voiddraw() = 0;
void draw() override {
cout << "window";
}
37
void draw() override {
cout << "decorator";
window->draw();
}
38. Decorator: Динамическое создание функциональности
Каждый класс-декоратор делегирует вызов вовложенный объект
Цепочка вложенных вызовов формирует
динамическое поведение из отдельных
поведенческих блоков
Widget* aWidget = new BorderDecorator(
new HorizontalScrollBarDecorator(
new VerticalScrollBarDecorator(
new Window(80, 24))));
aWidget->draw();
38
39. Заключение
Параллелизм уровня задачПараллелизм уровня потоков
Паттерн разбиения функциональности на единицы и компоновки из них нового
поведения
Atomic
Функция, исполняемая в любом потоке
Результат – future
Future – отложенный результат исполнения
Decorator
Ручной менеджмент потоков
Отсутствие join() до деструктора потока = вызов terminate
packaged_task
Менеджмент потоков автоматизирован
Единица исполнения – функция
Позволяет управлять моделью памятью С++
NVI
39
Паттерн выделения общей функциональности в базовый класс
Программирование