Модели многопоточности, или «Прощайте дедлоки»
Автор: Дмитрий Литовченко
Статья является выборочным переводом главы 5 из книги «Erlang and OTP in Action», Martin Logan, Eric Merritt, Richard Carlsson, издательство Manning.
От переводчика.
Целевая аудитория статьи — как матёрые программисты, которых угнетает индустриальный стандарт «shared memory with locks» и истосковавшиеся по качественной многопоточности в их любимом языке программирования, так и новички, которые до сего дня побаивались создания второго потока в своей игре, а если и создавали, то моментально наступали на целый набор разнообразных граблей, заточенных или ржавых, заботливо разбросанных реализацией shared memory with locks на их языке программирования. На самом деле, вопрос хоть и сложный, но не всё так плохо! Читайте.
Модели многопоточности, или «Прощайте дедлоки!»
Общая память и локи
STM (Software Transactional Memory)
Потоки данных, Будущие результаты и Обещания (Futures & Promises)
Асинхронный обмен сообщениями
Модели многопоточности, или «Прощайте дедлоки!»
Эта статья имеет цель преподать основы моделей многопоточности при написании многопоточных программ, чтобы облегчить понимание принципов многопоточности в вашем любимом языке программирования, и упростить выбор в пользу наиболее простого и надёжного варианта из имеющихся.
Параллельные системы начали приобретать популярность в последние годы, с ростом числа ядер в персональных компьютерах и серверных платформах. Сам факт, что вы в данный момент читаете эту статью (и упомянутую выше книгу) это подтверждает. Самой большой проблемой параллельных систем является способ обмена потоков общим состоянием (shared state). Как ваши потоки обмениваются друг с другом состоянием?
На первый взгляд это кажется невинной и маленькой проблемой, однако лучшие умы мира долгие годы бились над ней и нашли всего несколько подходящих решений. Было испытано множество разных подходов, и всего четыре из них набрали заметный процент популярности на рынке параллельных решений. С целью осветить эти подходы и была создана данная статья. Мы рассмотрим:
- общую память и локи;
- программную транзакционную память (STM, software transactional memory);
- поток данных - Будущие результаты и Обещания (futures and promises);
- асинхронные сообщения между потоками.
Мы постараемся сравнить эти способы друг с другом, и выделить плюсы и минусы каждого.
Общая память и локи
Это самый корявый способ, хочу заметить. Общая память и локи — это GOTO нашего времени. Так же, как и GOTO прошлых лет, эта модель параллельности используется везде, где только можно, и существует на рынке в течение десятков лет. Так же, как и с GOTO, здесь имеется ряд уловок и способов, чтобы «выстрелить себе в ногу». Этот способ параллельного программирования успешно воспитал целые поколения инженеров с глубоким подсознательным страхом параллельности. В наше время этот страх сильно осложняет адаптацию программистов к новому поколению многоядерных систем. Так же как и GOTO, следует признать, что у общей памяти есть своя узкая ниша применения, на низком уровне, где по другому, вероятно, просто не получится. Если вы работаете на таком уровне, вы вполне осознаёте почему используете общую память, и плюсы и минусы этого способа. Для примера, реализация бизнес логики, сетевых серверов и служб не являются этой узкой нишей, и вам следовало бы ознакомиться с другими способами.
Общая память обычно является блоком RAM (памяти общего доступа), доступ к которому имеют несколько параллельных потоков (или процессов, несущественно). Этот блок памяти защищён некоторым «замком», который гарантирует что в один момент времени только один процесс имеет доступ к данному блоку памяти, остальные в это время либо ожидают своей очереди, либо пробуют захватить «замок», и при неудаче продолжают своё выполнение, отложив следующую попытку на будущее. В простейшем случае, процессы выстраиваются в очередь на доступ к данному блоку памяти. В роли «замка» выступают имеющиеся в вашем языке программирования примитивы: Lock, Semaphore, Mutex и так далее.
Данный подход имеет ощутимую сложность — это организация доступа к тяжело нагруженным блокам данных, которые нужны всем и каждому. Имеется возможность, а во многих случаях и высока вероятность создания сложных тупиковых ситуаций (deadlock), когда пары или группы потоков зависают в ожидании друг друга, которые разработчику совсем непросто обнаружить без долгой отладки. Не счесть историй, когда система зависала во время взаимной блокировки (deadlock) после недель или месяцев, а то и года успешной работы. Такой подход к параллельности годится для небольших программ с небольшим количеством процессов. При увеличении количества процессов (например, рост числа клиентов сервиса, или рост популярности вашей ММОРПГ) сложность такой системы возрастает в разы, и ситуация быстро выходит из-под контроля.
Такой тип параллельности используется в множестве популярных в наше время языков программирования: C, C++, Java, Perl, Python (в Python посредством единственного глобального лока). Использование общей памяти — вездесущий и общеупотребимый подход к многопоточности, в частности из-за легкости и простоты реализации, который легко совмещается с моделью императивных языков программирования. К несчастью, широкое распространение этого метода негативно повлиял на наше умение думать о проблемах параллельности и использовать параллельность в больших масштабах.
STM (Software Transactional Memory)
Первый нетрадиционный способ обеспечения обмена состоянием между потоками — программная транзакционная память, сокращённо STM (Software Transactional Memory). Один из самых популярных примеров такой параллельности — компилятор GHC для языка Haskell. Википедия содержит хорошо подобранные факты и ссылки по многим вопросам компьютерных наук, потому мы тоже будем опираться на факты, изложенные в ней.
STM — это механизм контроля аналогичный транзакциям баз данных для контроля доступа к общей памяти при параллельных вычислениях. Он работает, как альтернатива синхронизациям на основе замков (lock), и часто сделан без них в «беззамочной форме» (lock free). В этом контексте, транзакция — это фрагмент кода, выполняющий операции чтения и записи из общей памяти, и этот ряд операций происходит логически как бы в один момент времени, другой код не может вклиниться и выполнить доступ к общей памяти между ними. По завершении транзакции следующий, конкурирующий, фрагмент кода проверяет, подходят ли данные в памяти для записи результатов его работы? Если данные в памяти не соответствуют его ожиданиям, результат отбрасывается и операция переделывается заново.
(Пример с бейсбольным мячом — в оригинальной статье автор рассылает бейсбольный мяч членам любимой команды, чтобы они оставили подписи на нём. Мы же используем более близкий нашей молодёжи пример с «Обходным листом» университета).
Пример с Обходным листом.
Допустим, вы студент, и у вас на руках имеется Обходной Лист, который надо пронести по всем факультетам, библиотеке, ректорату и проч. и собрать подписи всех ответственных лиц. Допустим, что это очень особенный лист, с которого я могу снимать копии и передавать кому следует на подпись. Я не даю им копию навсегда, я просто передаю копию на подпись и забираю обратно. Таким образом 10 деканатов, библиотека и ректорат получают копии моего чистого обходного листа. Внезапно, деканат математического факультета первым подписал мой Обходной Лист и вернул мне их копию. Я заменяю чистый лист в своей руке на эту подписанную копию. Через секунду мне присылают мой лист с подписью физического факультета. Я сравниваю его с листом в моей руке и замечаю, что они различаются. Ох ведь, так не годится! Я выбрасываю пришедший лист с подписью физиков, и отсылаю им копию моего листа с подписью математиков. Мне ведь нужны все подписи на одном листе, а не раздельно! Эта операция повторяется много раз, по мере возвращения подписанных копий моего листа до тех пор, отбрасываем несовпадающие листы и отправляем повторно мою копию до тех пор, пока все подписи не собраны на одном листе. По сути я контролирую тот факт, что у меня на руках всегда свежайшая копия моего Обходного Листа.
STM имеет несколько преимуществ. Первое и самое главное преимущество не сразу бросается в глаза при просмотре примера выше. STM — это оптимистическая модель. Каждый поток делает своё дело не задумываясь о том, работает ли другой поток с теми же данными или нет. В конце манипуляции, если всё в порядке и ничего на принимающей стороне не поменялось, результат отправляется на принимающую сторону. Если возникает конфликт версий или данных, то результат отбрасывается и операция проводится повторно, уже с новыми данными.
Хорошее свойство этой модели — никто не ждёт никаких ресурсов. Потоки могут писать в разные поля структуры не заботясь о «замках». Плохое свойство — работу иногда придётся переделывать. Также имеются некоторые, ощутимые накладные расходы на систему транзакций, которые влияют на скорость выполнения. В некоторых ситуациях может возникнуть перерасход памяти: если N процессов работают над M байтами памяти — понадобится N*M байт для хранения N копий этих данных. В целом, для непрограммиста и для новичков этот подход к параллельности намного более понятен и прост, чем традиционный способ с общей памятью и замками (shared memory & locks) и может быть неплохим способом погрузиться в мир разработки параллельных программ.
Потоки данных, Будущие результаты и Обещания (Futures & Promises)
Ещё один подход к параллельному программированию это «Обещания результатов» (futures, promises). Примеры такого подхода могут быть найдены в Mozart-Oz, в Java, в С++ (библиотека ASIO, Boost.Asio), Python (библиотека Twisted). Снова, Википедия даёт исчерпывающее описание по данной теме, и мы построим повествование на этом описании.
В компьютерных науках, обещания результатов (futures and promises) — это родственные конструкции, используемые для синхронизации в некоторых параллельных языках программирования. Оба они ссылаются на объект, который является посредником в предоставлении результата, который не является немедленно доступным, потому что его вычисление ещё не завершилось.
Вернёмся к нашему Обходному Листу. Мне снова надо подписать мой Обходной Лист, на этот раз на факультете Информационных Технологий. Я просто иду в их деканат и передаю им мой Обходной Лист, но поскольку в данный момент они немного заняты (пьют кофе, к примеру), они дают мне Расписку (в данном случае future), в которой мне обещают вернуть мой подписанный Обходной Лист в аккурат тот момент, когда они освободятся. В шоке я сижу под деканатом и читаю эту Расписку, пока не выходит секретарь деканата и не вручает мне мой Обходной Лист с подписью деканата. Расписка мне больше не нужна, её можно выбросить.
Обещания (promise) очень похожи на только что описанную Расписку деканата (future). К примеру, я прихожу в ректорат, где собрались все деканы, кроме декана факультета ИТ, чья подпись мне и нужна. У меня забирают мой лист и мне вручают Письменное Обещание, что как только он появится, ему передадут мой лист на подпись. В шоке я сижу под ректоратом и смотрю на эту записку, пока случайный декан мне не выносит мой Обходной Лист, подписанный деканом факультета ИТ. Записка более не нужна и её я выбрасываю.
Будущий результат (future) это некий контракт, что определённый поток в какой-то момент времени ОБЯЗАТЕЛЬНО возвратит мне результат, согласно данному контракту. В отличие от этого Обещание (promise) это обещание, что в какой-то момент времени, какой-то поток, неважно какой, исполнит мою задачу и вернёт мне обещанный результат. По сути это стиль программирования основанный на потоке данных и концептуально достаточно простой. Этот принцип делает обмен данными в параллельных системах простым и понятным, и служит хорошей основой для построения более сложных структур вроде каналов данных. Однако, хотя Будущие результаты и Обещания позволяют обойти самые известные проблемы параллельного программирования, это всё ещё общая память со всеми скрытыми проблемами.
По сути Будущие результаты и Обещания — это общее состояние разных потоков. Они хорошо обходят с самые крупные проблемы, но не полностью решают их. Следующий механизм подходит к проблеме с другой стороны. Что позволяет ему ловко решить все известные проблемы общей памяти, в основном ценой дополнительных расходов памяти и времени на копирование данных. Но не будем забегать вперёд...
Асинхронный обмен сообщениями
По этой модели параллельности работает язык Erlang, но при желании несложно настроить подобную модель в любом другом языке, главное понять идею. Процессы содержат своё состояние в себе, и общаются друг с другом только посредством сообщений, которые не хранятся в общей памяти, а копируются от процесса к процессу, и ложатся в специальный, личный для этого процесса, «почтовый ящик». Такая коммуникация является полностью асинхронной, никто никого не ожидает и сообщения обрабатываются другими процессами по мере возможности, когда удобно им. Более сложные модели коммуникации могут быть построены на этом примитиве. Такая модель совместной работы иногда ещё называется Actor Model.
Вернёмся к нашему Обходному Листу. На этот раз вместо того, чтобы ножками бегать по университету и подписывать везде наш лист, мы передаём наш лист в специальную бесплатную службу, которая по чистой случайности специализируется на Обходных Листах. Мы размещаем наш лист в конверте с подробной запиской, что с ним нужно сделать, и возвращаемся к своим делам. Через две недели в мой почтовый ящик приходит ответ с моим Обходным Листом, подписанным всеми инстанциями, и сопроводительной запиской с подробностями исполнения моего задания.
Вся суть этого метода в том, чтобы наладить сообщение между независимыми процессами, которые посылают друг другу запросы и ответы. Семантически эти сообщения никак не связаны с пославшими их процессами. Это означает, что если вы пишете проект на языке А, вас совершенно не затруднит связать эту программу с другой, написанной на языке Б, главное договориться о формате и обработке сообщений. Всё, о чём следует позаботиться, это о потоках сообщений, текущих через части вашей системы.
Само собой, это изящное решение достаётся нам совсем не бесплатно. Во многих случаях передача сообщений между параллельными процессами сделана с помощью глубокого копирования (включая все поля и их под-поля) исходящего сообщения. Проблема в том, что для больших структур, цена копирования становится ощутимой. Дополнительный расход памяти может негативно повлиять на вашу систему, особенно если у вас жёсткие ограничения по памяти, а сообщения имеют большой размер. На практике вам придётся следить за тем, чтобы посылаемые и принимаемые сообщения имели по возможности небольшой размер.
Подобно Будущим Результатам и Обещаниям, самая страшная проблема параллельного программирования — взаимная блокировка — практически решена, пусть всё ещё возможна, но очень маловероятна.
От переводчика.
Подобное можно реализовать в С++ (и любом другом языке) с помощью любой подходящей библиотеки обмена сообщениями внутри процесса. Лично рекомендую библиотеку ZeroMQ, набор примеров здесь. Она идеально подходит и для связи процессов как на одной машине, так и по сети.
#многозадачность, #многопоточность
24 августа 2012