[C++] часть 1: многопоточность, конкурентность и параллелизм: ОСНОВЫ
Простое руководство по изучению многопоточности, конкурентности и параллелизма в C++
Вначале, когда ещё только состоялось моё знакомство с многопоточностью в C++, многое было мне непонятным и сбивало с толку. Сложность программы расцветала буйным цветом (именно так: подобно прекрасному цветку), конкурентность и параллелизм с их недетерминированным поведением меня просто убивали, и всё было как в тумане. Так что мне легко понять всех приступающих к изучению этих понятий. Спешу избавить вас от мучений и предлагаю вашему вниманию это простое руководство по изучению конкурентности, параллелизма и многопоточности в C++ (в конце данной статьи расписан план, в соответствии с которым мы будем двигаться дальше).
А пока освежим в памяти основные понятия и попробуем на вкус код, выполняемый в многопоточной среде.
1. Что такое поток?
В любом процессе создаётся уникальный поток выполнения, который называется основным потоком. Он может с помощью операционной системы запускать или порождать другие потоки, которые делят то же адресное пространство родительского процесса (сегмент кода, сегмент данных, а также другие ресурсы операционной системы, такие как открытые файлы и сигналы). С другой стороны, у каждого потока есть свой идентификатор потока, стек, набор регистров и счётчик команд. По сути, поток представляет собой легковесный процесс, в котором переключение между потоками происходит быстрее, а взаимодействие между процессами — легче.
2. Что такое конкурентность/параллелизм
Планировщик распределяет процессорное время между разными потоками. Это называется аппаратным параллелизмом или аппаратной конкурентностью (пока что считаем здесь параллелизм и конкурентность синонимами): когда несколько потоков выполняются на разных ядрах параллельно, причём каждый занимается конкретной задачей программы.
→ Примечание: чтобы определить количество задач, которые реально можно выполнять в многопоточном режиме на том или ином компьютере, используется функция std::thread::hardware_concurrency() . Если число потоков будет превышать этот лимит, может начаться настоящая чехарда с переключением задач (когда слишком частые переключения между задачами — много раз в секунду — создают лишь иллюзию многопоточности).
3. Основные операции с потоками с помощью std::thread
- Заголовочный файл| #include <thread>
- Запуск потока| std::thread t(callable_object, arg1, arg2, ..)
Создаёт новый поток выполнения, ассоциируемый с t, который вызывает callable_object(arg1, arg2) . Вызываемый объект (т.е. указатель функции, лямбда-выражение, экземпляр класса с вызовом функции operator ) немедленно выполняется новым потоком с (выборочно) передаваемыми аргументами. Они копируются по умолчанию. Если хотите передать по ссылке, придётся использовать метод warp к аргументу с помощью std::ref(arg) . Не забывайте: если хотите передать unique_ptr, то должны переместить его ( std::move(my_pointer) ), так как его нельзя копировать. - Жизненный цикл потока| t.join() и t.detach()
Если основной поток завершает выполнение, все второстепенные сразу останавливаются без возможности восстановления. Чтобы этого не допустить, у родительского потока имеются два варианта для каждого порождённого:
→ Блокирует и ждёт завершения порождённого потока, вызывая на нём метод join .
→ Прямо объявляет, что порождённый поток может продолжить выполнение даже после завершения родительского, используя метод detach . - Запомните: объект потока можно перенести, но нельзя копировать.
Здесь вы можете найти пример кода, иллюстрирующий практически всё, что написано выше.
4. Зачем нужна синхронизация?
Из-за того, что несколько потоков делят одно адресное пространство и ресурсы, многие операции становятся критичными, и тогда многопоточности требуются примитивы синхронизации. И вот почему:
- Память — дом с привидениями
Память никогда больше не будет обычным хранилищем данных — теперь это обитель привидений. Представьте: поток смотрит Netflix, уютно устроившись перед Smart TV, и тут вдруг экран мигает и выключается. В панике поток набирает 112, а в ответ… «Доставка пиццы, спасибо, что позвонили». Что происходит? А то, что в доме полно привидений (где в роли привидений другие потоки): они все в одной комнате и взаимодействуют с одними и теми же объектами (это называется гонка данных), но друг для друга они привидения.
Поток должен объявить, что он использует. А затем, прежде чем трогать этот объект, проверить, не использует ли его кто-то ещё. Зелёный поток смотрит ТВ? Значит, никто не должен трогать ТВ (другие могут рядышком сесть и посмотреть, если что). Это можно сделать с помощью мьютекса.
- Нужны атомарные операции!
Большинство операций неатомарные. Если операция неатомарная, можно увидеть её промежуточное состояние, так как она не является неделимой. Например: запись 64 битов, 32 бита за один раз. Во время этой операции другой поток может увидеть 32 старых бита и 32 новых, получая совершенно неверный результат. По этой причине результаты таких операций должны казаться атомарными, даже если они такими не являются.
→ Примечание: даже инкремент не является атомарной операцией: int tmp = a; a = tmp + 1;
Самое простое решение здесь — использовать шаблон std::atomic , который разрешает атомарные операции разных типов. - Когерентность кеша и выполнение с изменением очерёдности
Каждое ядро пытается сохранить результаты какой-то работы, помещая недавние значения в локальный кеш. Но несколько потоков выполняются на разных ядрах, и значения, хранящиеся в кеше, больше не могут быть валидными, так что рано или поздно кеш должен обновляться. В то же время изменения не видны другим, пока кеш не очищен. Чтобы распространить изменения и обеспечить корректную видимость памяти, нужны определённые механизмы.
Кроме того, для повышения эффективности процессор и/или компилятор может поменять очерёдность выполнения команд. Это может привести к непредсказуемому поведению в параллельно выполняемой программе, в связи с чем необходимо гарантировать исполнение критически важных команд в первоначальном порядке.
Эта работа выполняется примитивами синхронизации, предполагающими использование барьеров доступа к памяти (строки кода, которые не вычеркнуть какими-то операциями) для обеспечения согласованности и предотвращения изменения очерёдности выполнения (инструкции внутри барьеров памяти нельзя вытащить оттуда).
Пример кода
Обратимся к коду. Теперь вы сами можете проверить это недетерминированное поведение многопоточности.
В отличие от однопоточной реализации, каждое выполнение даёт разный и непредсказуемый результат (единственное, что можно сказать определённо: строки А и B упорядочены по возрастанию). Это может вызвать проблемы, когда очерёдность команд имеет значение.
Но что здесь происходит? После того как поток А оценивает «значение» как истинное, поток B меняет его. Теперь мы внутри блока if , даже если нарушены ограничения.
Если два потока имеют доступ к одним и тем же данным (один к записи, другой — к чтению), нельзя сказать наверняка, какая операция будет выполняться первой.
Доступ должен быть синхронизирован.
Заключение
Вы можете сказать: «Батюшки! Сколько всего намешано в этой статье!» Просто помните, что не надо пытаться понять всё и сразу, важно ухватить основные идеи.
Предлагаю пока что поиграть с примерами и посмотреть, как в них проявляется многопоточность. Можете подумать над другими примерами, где нужна синхронизация, и протестировать их (подсказка: потоки, удаляющие элементы из начала очереди. Не забывайте: прежде чем удалять, надо проверить, не пуста ли очередь).
Что такое поток в с
тут рассказать про проблему запуска 100500 потоков, что каждый поток затрачивает ресурсы ОС, есть НЕбесплатное переключение контекста потоков и пр
Переключение контекста
Большое количество потоков требует больших вычислительных ресурсов на их планирование и выполнение.
Чем больше потоков, тем больше переключений и тем больше памяти требуется для хранения контекстов.
Переключение контекста
Зачастую бывает полезно ограничить количество потоков в приложении, чтобы снизить накладные расходы и достичь наибольшей выгоды от многопоточности.
Очередь перед кассой
Представим, что вы в магазине. Вместе с вами там еще сотни людей. А теперь представим, что, чтобы расчитать вашу покупку, к вам подходит новый нанятый кассир, который считает ваш товар, принимает у вас деньги, отдает сдачу. А после того, как этот кассир обслужил вас, его увольняют и нанимают нового кассира для другого покупателя. Это НЕВЫГОДНО. Так примерно и происходит, если под каждую задачу запускать новый поток. ОС — магазин, покупатели — задачи, кассиры — потоки.
Пул потоков
Проблему огромного количества потоков в приложении призван решить пул потоков.
Пул потоков
В стандартной библиотеке C++ нет пула потоков.
Но его несложно реализовать с помощью стандартных средств C++ для своих целей.
Пример ThreadPool
Пример ThreadPool
Основной метод любого пула потоков – это метод, с помощью которого можно добавлять задачу на выполение.
В примере выше, это метод enqueue .
Метод enqueue
- метод возвращает future на результат выполнения функции
- принимает функцию func , которую необходимо выполнить
- и принимает аргументы args , которые необходимо передать в функцию func во время выполнения
Метод enqueue
Аргументы повторяют аргументы функции std::async (за исключением первого параметра std::launch policy ).
По факту, std::async может не создавать новый поток для исполнения задачи, а использовать поток из встроенного пула, но это зависит от конкретной реализации компилятора.
Пример
Как устроен пул потоков
объяснить как работают пулы потоков.
Как устроен пул потоков
По сути, это применение шаблона producer-consumer.
В качестве consumer’ов выступают потоки, которые выполняют поставленные в очередь задачи.
В качестве producer’ов – пользовательский код.
Модификации пула потоков
Иногда, чтобы решить задачу в “виртуальном” мире достаточно посмотреть как подобная задача решается в “реальном” мире.
Динамическое добавление и снятие потоков
В магазине не на всех кассах сидят кассиры. Но в случае большой загруженности магазина на свободные кассы приходят работники.
В случае отсутствия покупателей кассиры могут выполнять другую работу, либо берут отгулы, что экономит магазину ресурсы.
Локальные очереди для каждого потока
У каждой кассы собираются небольшие очереди. Это помогает очередям двигаться быстрее, а не толкаться в большой очереди мешая друг другу добираться до свободных кассиров.
Но иногда у одной кассы собирается большая очередь, а другие пустуют.
Резюме
- пул потоков предоставляет высокоуровневую абстракцию, позволяющую не задумываться о ручном управлении потоками
- пул потоков позволяет избежать накладных расходов на создание и уничтожение нового потока
- пул потоков помогает уменьшить суммарное время, затрачиваемое на переключение контекста потоков
Асинхронное программирование
Как приготовить ужин
есть два способа приготовить ужин. Рассказать, как готовить стейк: надо не отходя от плиты и скороводы ждать пока стейк две минуты прожарится на одной стороне, потом надо перевернуть его и опять НЕ отходя от плиты опять ждать. Приходится ждать, а не погамать в AoE 2… это Синхронный метод готовки ужина.
Как приготовить ужин
Но есть альтернативный способ приготовить ужин — асинхронный. Подготавливется мясо, солится, перчится, ставится в духовку, заводится будильник на полтора часа и все. Через полтора часа звонит будильник, вы идете к плите и ужин уже готов. А в то время, пока запекается мясо, можно заниматься другими делами.
Cинхронная модель
Обычно в программировании используется последовательное синхронное выполнение инструкций и вызовов функций, которые блокируют поток выполнения.
Пример
Cинхронная модель
Одна из проблем такого подхода в том, что часто приходится ждать неких внешних событий: чтение файла с диска, передача/получение данных по сети и т.д.
Cинхронная модель
При этом текущий поток вынужден ждать, а не выполнять полезную работу.
Это приводит к проблемам производительности приложения.
Асинхронная модель
В асинхронной модели программирования поток может приостановить выполнение задачи, сохранив текущее состояние, и начать выполнение другой задачи.
Асинхронная модель
Системные вызовы выполняются в неблокирующем режиме, что позволяет потоку продолжить работу.
Пример
Замечание
Представленный выше код является псевдокодом. Реальный код не представлен на слайдах для упрощения понимания примера.
Чтобы увидеть работающий код, смотрите пример к лекции.
Псюсы асинхронности
Использование асинхронного программирования позволяет одному потоку обрабатывать несколько задач, а не простаивать, пока выполняется системный вызов.
Функции обратного вызова
Функции обратного вызова (callback) – функции, которые будут вызываны после того, как завершится задача, запущенная в асинхронном режиме.
Callback
С помощью callback’ов можно обрабатывать результат асинхронных операций.
Callback
В примере лямбда on_read_callback является callback-функцией.
Лямбда on_read_callback будет вызвана после того как будут получены данные по сети и завершится системный вызов.
Проблемы callback-функций
Код с использованием callback-функций становится запутанным, нарушается последовательность кода.
Легко “заблудиться”, в какой момент и в каком порядке будут вызываться callback-функции.
Проблемы callback-функций
Всегда необходимо заботиться о времени жизни объектов, которые используются в callback-функциях.
Совет
Всегда, когда имеете дело с callback-функциями, думайте о времени жизни объектов, с которыми работаете в callback’ах.
Сопрограммы
Чтобы решить проблемы, связанные с использованием callback-функций, можно воспользоваться сопрограммами (coroutine).
Сопрограммы
Сопрограмми называются функции, имеющие несколько точек входа, в то время как, у обычных функций есть только одна.
Пример
Точки входа
Функция Echo является сопрограммой. У нее три точки входа:
- Как у обычных функций в начале тела функции;
- После асинхронного чтения данных из сокета;
- После асинхронной записи данных в сокет.
co_await
Оператор co_await приостанавливает сопрограмму и возвращает управление вызывающему коду.
co_await
После того как завершится операция, запущенная в асинхронной функции, сопрограмма продолжит свою работу с того места, где была приостановлена, т.е. со своей следующей точки входа.
Преимущества сопрограмм
Использование сопрограмм позволяет писать асинхронный код, который выглядит как синхронный. Такой код проще реализовывать, отлаживать и использовать.
Резюме
асинхронное программирование позволяет избежать появления узких мест производительности и увеличить общую скорость реагирования приложения
асинхронность необходимо использовать при наличии потенциально блокирующих работу действий
асинхронность полезна при обращении к потоку пользовательского интерфейса
Резюме
- при разработке callback-функций продумывайте, как объекты “доживут” до вызова callback’a
Резюме
использование сопрограмм в асинхронном программировании помогает упростить код
в зависимости от реализации сопрограммы иногда бывают эффективнее callback’ов
сопрограммы полезны не только при асинхронности, например, еще и при реализации генераторов
Атомарные операции
Атомарные vs неатомарные
Операция называется атомарной, если она выполняется как единое целое, либо не выполняется вовсе. Т.е. она не может быть частично выполнена или частично не выполнена.
Если один поток выполняет атомарную операцию, то другие потоки не могут “вмешаться” в выполнение этой операции (например, получить её промежуточное значение).
Атомарные vs неатомарные
Неатомарные операции такой гарантией не обладают.
Неатомарная переменная
Атомарная переменная
atomic
- load() — получить текущее значение
- store() — присвоить новое значение
- is_lock_free() — возвращает true, если операции на данном типе неблокирующие
- operator++ — инкремент
- exchange() — установить новое значение и вернуть предыдущее
- compare_exchange_strong() — аналог CAS
- compare_exchange_weak() — аналог CAS
- …
CAS (Compare and Swap)
Операция атомарно сравнивает значение одного объекта с другим и при равенстве измениет значение объекта.
compare_exchange
compare_exchange
Разница между compare_exchange_weak и compare_exchange_strong заключается в том, что compare_exchange_weak на некоторых платформах может вернуть false и НЕ выполнить обмен даже в случае равных значений.
Lock-free программирование
Неблокирующая синхронизация – подход в параллельном программировании, в котором принят отказ от традиционных примитивов блокировки.
Недостатки блокировок
- блокировки — довольно медленные операции
- при блокировках поток с низким приоритетом может заблокировать поток, с более высоким приоритетом
Определение
Процедура считается lock-free, если для нее гарантируется прогресс как минимум одного потока, выполняющего эту процедуру. Другие потоки могут ждать, но минимум один поток должен прогрессировать.
Операция называется wait-free, если она завершается за определенное количество шагов, не зависящих от состояние и действий других потоков.
Реализация lock-free
Неблокирующие алгоритмы строятся на атомарных операциях.
Одна из самых значимых операций при lock-free программировании – это сравнение с обменом (CAS).
Lock-free stack
Чтобы лучше разобраться с lock-free алгоритмами, необходимо рассмотреть пример.
Для этого реализуем потокобезопасной стек с использованием lock-free программирования.
Что такое поток (stream)?
В книжках пишут про стандартные потоки ввода-вывода в C++, запись в поток и чтение из потока.
Что такое поток, и что он из себя представляет?
Поток это просто абстракция. Удобная абстракция для решения задач.
Но если так будет легче — считайте, что это такая труба. С одной стороны в нее пихаются данные, а с другой куда то уходят (например, на консоль или в файл). Так как труба не нулевого размера, часть данных там может «задерживаться» — это так называемая буферизация. Понимание этого может облегчить понимание некоторого странного поведения стандартных потоков.
Рассмотрим например, такое чтение с консоли:
и такие данные на вход:
Как это будет работать? Вначале стандартному потоку нужно прочитать число. Он будет читать до тех пор, пока там число. В n попадет 123. В «трубе осталось «a aaa». Дальше нужно прочитать строку. А строка читается до пробела или перевода строки. Поэтому прочитается только одно a. А многие полагают, что прочитается три а. Я привел этот пример не просто так. На него многие попадаются.
Как это реализовано внутри? Очень просто. Есть очередь (то есть, если очень грубо — массив), откуда читают данные байт за байтом. Если в очереди ничего нет — библиотечный код обращается к функциям операционной системы и читает с консоли/файла/сокета) и складывает в очередь. Конечно, в некоторых случаях эта очередь может быть реализована на базе операционной системы, а может и явно. Но для пользователя (то есть программиста) это прозрачно.
Аналогично работает и вывод.
Чем удобны потоки?
После того, как поток «подключен» к файлу или консоли, дальше все идет одинаково. Можно, к примеру написать функции, которые будут выводить в поток, но при этом абсолютно не знать, куда именно они выводят. Это позволяет писать обобщенные алгоритмы и прочие вкусности.
Например, нужно сделать функцию форматированного вывода числа на консоль (со спец. пожеланиями). Можно конечно закодить вывод на std::cout, но как протестить? Можно написать функцию, которая будет на вход получать ostream (предок std::cout) и выводить в него. Потом можно использовать такую функцию и выводить в stringstream, который легко преобразовывается в строку и результат можно выверить тестом.
Урок №207. Потоки ввода и вывода
Функционал потоков ввода/вывода не определен как часть языка C++, а предоставляется Стандартной библиотекой C++ (и, следовательно, находится в пространстве имен std). На предыдущих уроках мы подключали заголовочный файл библиотеки iostream и использовали объекты cin и cout для простого ввода/вывода данных. На этом уроке мы детально рассмотрим библиотеку iostream.
Библиотека iostream
При подключении заголовочного файла iostream, мы получаем доступ ко всей иерархии классов библиотеки iostream, отвечающих за функционал ввода/вывода данных (включая класс, который называется iostream). Иерархия этих классов выглядит примерно следующим образом:
Первое, что вы можете заметить в этой иерархии — множественное наследование (то, что на самом деле не рекомендуется использовать). Тем не менее, библиотека iostream была разработана и тщательно протестирована соответствующим образом, дабы избежать типичных ошибок, которые возникают при работе с множественным наследованием, поэтому вы можете спокойно использовать эту библиотеку.
Потоки в С++
Второе, что вы могли бы заметить — это частое использование слова «stream» (т.е. «поток»). По сути, ввод/вывод в языке C++ реализован с помощью потоков. Абстрактно, поток — это последовательность символов, к которым можно получить доступ. Со временем поток может производить или потреблять потенциально неограниченные объемы данных.
Мы будем иметь дело с двумя типами потоков. Поток ввода (или «входной поток») используется для хранения данных, полученных от источника данных: клавиатуры, файла, сети и т.д. Например, пользователь может нажать клавишу на клавиатуре в то время, когда программа не ожидает ввода. Вместо игнорирования нажатия клавиши, данные помещаются во входной поток, где затем ожидают ответа от программы.
И наоборот, поток вывода (или «выходной поток») используется для хранения данных, предоставляемых конкретному потребителю данных: монитору, файлу, принтеру и т.д. При записи данных на устройство вывода, это устройство может быть не готовым принять данные немедленно. Например, принтер все еще может прогреваться, когда программа уже записывает данные в выходной поток. Таким образом, данные будут находиться в потоке вывода до тех пор, пока принтер не начнет их использовать.
Некоторые устройства, такие как файлы и сети, могут быть источниками как ввода, так и вывода данных.
Хорошая новость заключается в том, что программисту не нужно знать детали взаимодействия потоков с разными устройствами и источниками данных, ему нужно только научиться взаимодействовать с этими потоками для чтения и записи данных.
Ввод/вывод в C++
Хотя класс ios является дочерним классу ios_base , очень часто именно этот класс будет наиболее родительским классом, с которым вы будете работать/взаимодействовать напрямую. Класс ios определяет кучу разных вещей, которые являются общими для потоков ввода/вывода.
Класс istream используется для работы с входными потоками. Оператор извлечения >> используется для извлечения значений из потока. Это имеет смысл: когда пользователь нажимает на клавишу клавиатуры, код этой клавиши помещается во входной поток. Затем программа извлекает это значение из потока и использует его.
Класс ostream используется для работы с выходными потоками. Оператор вставки << используется для помещения значений в поток. Это также имеет смысл: вы вставляете свои значения в поток, а затем потребитель данных (например, монитор) использует их.
Класс iostream может обрабатывать как ввод, так и вывод данных, что позволяет ему осуществлять двунаправленный ввод/вывод.
Наконец, остались 3 класса, оканчивающиеся на _withassign . Эти потоковые классы являются дочерними классам istream , ostream и iostream (соответственно). В большинстве случаев вы не будете работать с ними напрямую.
Стандартные потоки в C++
Стандартный поток — это предварительно подключенный поток, который предоставляется программе её окружением. Язык C++ поставляется с 4-мя предварительно определенными стандартными объектами потоков, которые вы можете использовать (первые три вы уже встречали):
cin — класс istream_withassign , связанный со стандартным вводом (обычно это клавиатура);
cout — класс ostream_withassign , связанный со стандартным выводом (обычно это монитор);
cerr — класс ostream_withassign , связанный со стандартной ошибкой (обычно это монитор), обеспечивающий небуферизованный вывод;
clog — класс ostream_withassign , связанный со стандартной ошибкой (обычно это монитор), обеспечивающий буферизованный вывод.
Небуферизованный вывод обычно обрабатывается сразу же, тогда как буферизованный вывод обычно сохраняется и выводится как блок. Поскольку clog используется редко, то его обычно игнорируют.