Асинхронная разработка на C++ под мобильные устройства

От Java Threads к лямбдам

Продвинутое использование Celery

Многопоточность в браузере. Модель акторов

Устройство асинхронных фреймворков для Python

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

«Асинхронность» и «параллельность» — довольно-таки ортогональные понятия, и один подход задачи другого не решает. 

Тем не менее асинхронности нашлось отличное применение в наше высоконагруженное время быстрых интернет-сервисов с тысячами и сотнями тысяч клиентов, ждущих обслуживания одновременно. 

Откровенно говоря, есть только два варианта работы с сокетом — синхронный и асинхронный.

С синхронным в целом все понятно — пришел клиент, открылся сокет, передали данные, если это все — сокет закрылся. В этом случае пока мы не закончили локальный диалог с одним клиентом — не можем начать его с другим. По такому принципу обычно работают простые серверы, которым не надо держать сотни и тысячи клиентов. В случае если нагрузка возрастает, но не критично — можно создать еще один или несколько потоков (или даже процессов) и обрабатывать подключения еще и в них. Это обкатанный годами, стабильно работающий подход, который, например, использует сервер Apache, — никаких неожиданностей, данные от клиентов обрабатываются в порядке строгой очереди, а в случае запуска какого-то «долгого» кода — например, каких-то вычислений или хитрого запроса в БД — это все никак не влияет на других клиентов.

Но есть проблема: сервер не может плодить потоки и процессы вечно — есть же, в конце концов, вполне ощутимые ресурсы, которые тратятся при каждом таком действии, и имеется верхний порог использования этих ресурсов. И вот тогда все вдруг вспомнили про асинхронность и системные вызовы для неблокирующего ввода-вывода. Зачем плодить кучу сокетов и потоков, выедать ресурсы, если можно данные от многих клиентов сразу одновременно слушать на одном сокете?

Архитектура однопроцессорной машины

Классификация Джонсона (MIMD машины)

Классификация Флинна

Технологии параллелизации на Java

• Модель акторов — Википедия
• OpenCL — Википедия
• OpenMP — Википедия
• Обзор java.util.concurrent.* / Блог компании Luxoft / Хабрахабр
• jcuda.org - Java bindings for CUDA
• Hadoop — Википедия
• Akka для Java разработчика (часть 1) / Хабрахабр
• Parallel Collections - Overview - Scala Documentation
• Apache Spark™ - Lightning-Fast Cluster Computing
• Thread (Java Platform SE 8 )
• Программная транзакционная память — Википедия

Внутренний и внешний параллелизм в СУБД Teradata

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

Основной единицей параллелизма является виртуальный процессор доступа (Access Module Processor). Все запросы и операции загрузки данных, резервного копирования, построения индексов распределяются между AMP. В первой версии AMP были физическими процессорами, но затем стали виртуальными. На отдельном SMP-узле (Symmetric MultiProcessor — «симметричная многопроцессорность») могут работать несколько AMP, реализованных в виде процессов операционной системы, а все такие узлы объединяются в систему с массовой параллельной обработкой (Massively Parallel Processing, MPP). Процессоры AMP позволяют распределять ресурсы, распараллеливая все операции.

В СУБД Teradata параллельная обработка запросов осуществляется на основе хеш-секционирования данных и их распределения между всеми процессорами AMP. Перед началом работы, на этапе конфигурирования, задается число процессоров AMP — от двух до двадцати на узел, в зависимости от мощности базовых аппаратных средств. Все операции, такие как сканирование таблиц и индексов, проекция, выборка, соединение, агрегирование и сортировка данных, распределяются между процессорами AMP и выполняются параллельно. Каждая операция с данными, отнесенными к одному процессору AMP, выполняется независимо от операций других AMP.

What Every Dev Must Know About Multithreaded Apps

Concurrency: What Every Dev Must Know About Multithreaded Apps

Win32 threads

Когда стартует процесс посредством функции CreateProcess, он имеет один поток для выполнения команд. Поток состоит из двух объектов: объект ядра (через него система управляет потоком) и стек, в котором хранятся параметры, функции и переменные потока. 

Чтобы создать дополнительный поток, надо вызвать функцию CreateThread. В результате создается объект ядра — компактная структура данных, используемая системой для управления потоком. Этот объект, по сути, не является потоком. Также из адресного пространства родительского процесса для потока выделяется память. И поскольку все потоки одного процесса будут выполняться в его адресном пространстве, то они будут разделять его глобальные данные.

Вернемся к функции CreateThread и рассмотрим ее параметры.

• Первый параметр — указатель на структуру PSECURITYATTRIBUTES, которая определяет атрибуты защиты и свойства наследования, для установки значений по умолчанию достаточно передать NULL. 
• Второй параметр типа DW0RD определяет, какую часть адресного пространства поток может использовать под свой стек. 
• Третий параметр PTHREADSTART_ROUTIME pfnStartAddr — указатель на функцию, которую необходимо привязать к потоку и которую он будет выполнять. Эта функция должна иметь вид DWORD WINAPI ThreadFunc(PVOID pvParam), она может выполнять любые операции; когда она завершится, то возвратит управление, а счетчик пользователей объекта ядра потока будет уменьшен на 1, в случае, когда этот счетчик будет равен 0, данный объект будет уничтожен. 
• Четвертый параметр функции CreateThread — указатель на структуру PVOID, содержащую параметр для инициализации выполняемой в потоке функции (см. описание третьего параметра). 
• Пятый параметр (DWORD) определяет флаг, указывающий на активность потока после его создания. Последний, шестой параметр (PDWORD) — адрес переменной, куда будет помещен идентификатор потока, если передать NULL, тем самым мы сообщим, что он нам не нужен. В случае успеха функция возвращает дескриптор потока, с его помощью можно манипулировать потоком; при фейле функция возвращает 0.

Существуют четыре пути завершения потока, три из которых нежелательные: это завершение потока через вызов функции ExitThread, через вызов TerminateThread, при завершении родительского процесса без предварительного завершения потока. Лишь 1 путь – самозавершение потока, которое происходит при выполнении назначенных ему действий, является благоприятным. Потому что только в этом случае гарантируется освобождение всех ресурсов операционной системы, уничтожение всех объектов C/C++ с помощью их деструкторов.

Еще пара слов о создании потока. Функция CreateThread находится в Win32 API, при этом в библиотеке Visual C++ имеется ее эквивалент _beginthreadex, у которой почти тот же список параметров. Рекомендуется создавать потоки именно с ее помощью, поскольку она не только использует CreateThread, но и выполняет дополнительные операции. Кроме того, если поток был создан с помощью последней, то при уничтожении вызывается _endthreadex, которая очищает блок данных, занимаемый структурой, описывающей поток.

Потоки планируются на выполнение с учетом приоритета. Если бы все потоки имели равные приоритеты, то для выполнения каждого (в WinNT) выделялось бы по 20 мс. Но это не так. В WinNT имеется 31 (от нуля) поточный приоритет. При этом 31 — самый высокий, на нем могут выполняться только самые критичные приложения — драйверы устройств; 0, самый низкий, зарезервирован для выполнения потока обнуления страниц. Тем не менее разработчик не может явно указать номер приоритета для выполнения своего потока. Зато в Windows есть таблица приоритетов, где указаны символьные обозначения сгруппированных номеров приоритетов. При этом конечный номер формируется не только на основе этой таблицы, но и на значениях приоритета родительского процесса. Значения скрыты за символьными константами по той причине, что Microsoft оставляет за собой право их изменить и пользуется им от версии к версии своей операционки. При создании поток получает обычный (normal) уровень приоритета. Его можно изменить функцией SetThreadPriority, принимающей два параметра: HANDLE hThread — дескриптор изменяемого потока, int nPriority — уровень приоритета (из таблицы). С помощью функции GetThreadPriority можно получить текущий приоритет, передав в нее дескриптор нужного потока. Перед изменением приоритета потока его надо приостановить, это делается функцией SuspendThread. После изменения приоритета поток надо снова отдать планировщику для планирования выполнения функцией ResumeThread. Обе функции получают дескриптор потока, с которым работают. Все описанные операции кроме приостановки и возобновления применимы и к процессам. Они не могут быть приостановлены/возобновлены, поскольку не затрачивают процессорное время, поэтому не планируются.

Примитивы для работы в многопоточной среде

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

Семафор — исторически самый первый механизм для синхронизации, разработанный Дейкстрой в 1968 году. Позволяет войти в критическую секцию определенному количеству потоков, при входе в нее потока уменьшает свое значение и увеличивает в момент его выхода. Обязательным условием является атомарное выполнение операций проверки значения семафора + увеличения значения, а так же проверки значения + уменьшения значения. 

Развитием семафора служит мьютекс, который является попросту двоичным семафором и поэтому в критической секции допускает выполнение только одного потока. Блокировки чтения-записи позволяют нескольким потокам читать значение общей переменной, находящейся в критической секции, но записывать только одному. Во время ожидания спин-блокировка не блокируется, а продолжает активный опрос заблокированного ресурса. Спин-блокировка — плохое решение проблемы синхронизации для одноядерного процессора, поскольку занимает все вычислительные ресурсы.

Похож на семафоры механизм условных переменных, тем не менее они, в отличие от семафоров (и мьютексов), не содержат реальных значений. Они следят за выполнением внешних условий.

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

Для обмена информацией между процессами/потоками используются сообщения, подразделяемые на три группы: внутрипроцессные (для передачи информации между потоками одного процесса), межпроцессные (для передачи инфы между процессами — с зависимостью от потоков) и процесс — процесс (поточно независимая передача инфы между процессами).

В то же время при использовании блокировок для избегания гонок могут наступить мертвые (dead lock) и живые (live lock) блокировки. Мертвая блокировка имеет место, когда один поток заблокирован на ожидании определенного ресурса от другого потока, но тот не может дать его (например, ожидает результат от первого). Мертвая блокировка может произойти при выполнении четырех хорошо определенных условий. Поэтому при написании многопоточного кода у программиста есть возможность избежать дидлока, но на практике это выглядит гораздо сложнее. Живая блокировка хуже мертвой тем, что в первом случае потоки заблокированы, а во втором они постоянно конфликтуют.

Существует насколько несовместимых между собой прикладных поточных программных интерфейсов. Все они в основном используют одинаковые примитивы, отличия лишь в зависимости от операционной системы. 

Модель вытесняющей многопоточности в Windows NT 6.1

Windows NT 6.1 использует модель вытесняющей многопоточности. Когда запускается приложение, стартует процесс, в нем могут выполнять свою работу один или несколько потоков, все они разделяют общую память и общее адресное пространство. Поток же, в свою очередь, — это обособленная последовательность команд, выполняемая независимо.

Существует три вида потоков:

• пользовательского уровня — создается в пользовательской программе (на уровне пользователя). Эти потоки в Windows NT проецируются на потоки уровня ядра, так их видит процессор (Ни о каких потоках процессор не знает вообще! У процессора есть контекст исполнения (состояние регистров) и оперативная память. Загрузили программу в память, установили регистры - пошло выполнение. Пришло прерывание - посмотрела ОС, что пора переключать, сохранила контекст, загрузила новый - пошло исполнение другого потока. Такого объекта, как "поток", на уровне процессора не существует. А проецируются друг на друга структуры в памяти, т.е. чисто искусственные образования ОС.);
• поток ядра — управляется ядром операционной системы;
• аппаратный поток — единица, исполняемая на процессоре.

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

Но в связи с тем, что в программе одновременно выполняется несколько действий, может возникнуть куча проблем. Их удобно классифицировать под четыре типа.

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

Для решения всех этих проблем предназначены примитивы для работы в многопоточной среде. 

Гиперпоточность и многоядерные процессоры

Разработчики процессоров столкнулись с рядом проблем в увеличении тактовой частоты: 

• невозможно рассеивать выделяемую кристаллом теплоту, 
• нельзя дальше уменьшать размер транзисторов, 
• однако главной проблемой стало то, что при увеличении тактовой частоты быстродействие программ не повышалось. 

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

На одном камне выполнение нескольких процессов/потоков может быть только конкурентным. То есть их работа чередуется: после того как определенный поток отработает свой квант времени, в течение которого он выполнил полезную нагрузку, его текущее состояние сохранится в памяти, а он будет выгружен из процессора и заменен следующим находящимся в очереди на выполнение потоком — произойдет переключение контекста, на что тратится драгоценное время. А пока идет обмен данными между процессором и оперативной памятью, из-за ограниченной пропускной способности системной шины микропроцессор нервно курит бамбук, в сторонке ожидая данные. На помощь могут прийти аппаратный и программный (например, из операционной системы) планировщики, чтобы подгружать данные в кеш. Однако кеш очень ограничен по объему, поэтому такое решение не может служить панацеей. Выходом стала параллельная обработка, при которой в реальном времени одновременно выполняются несколько процессов. А чтобы ее реализовать, потребовалось фундаментально перепроектировать и перестроить камень — совместить в одном корпусе два исполняющих кристалла и более.

Декомпозиция задачи в параллельной разработке

Самое важное — посмотреть на разработку иначе, не последовательно, выделить единицу выполняемой работы, провести декомпозицию задачи. Имеется три способа: декомпозиция по заданиям, декомпозиция по данным, декомпозиция по информационным потокам.

Первый способ декомпозиции самый простой: мы просто привязываем отдельную функцию к определенному потоку и запускаем его на выполнение. Параллельная обработка готова. Однако могут быть проблемы — конкуренция, если в исполняемой единице используются общие глобальные данные. Но об этом мы поговорим позже.

Второй способ тоже достаточно понятный метод распараллеливания: например, большой массив данных обрабатывается несколькими потоками, каждый из которых работает над частью, ограниченной определенными пределами.

Декомпозиция по информационным потокам служит для задач, когда работа одного потока зависит от результата выполнения другого. Например, во время чтения из файла поток — обработчик считанных данных не может начать работу, пока поток-читатель не считает определенный объем данных.