Что такое многопоточное программирование

Многопоточное программирование и его проблемы

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

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

Но сначала мы поговорим об основах. Важное предупреждение: это очень поверхностная и обзорная статья. Если вам кажется, что в ней сказано недостаточно — вам не кажется. Подробности позже. Сейчас общее.

Concurrent vs Parallel vs Async

На Stackoverflow есть популярный вопрос: «чем concurrent отличается от parallel в контексте программирования?». Вот мое видение вопроса.

Concurrent — это постановка проблемы. Я хочу, чтобы некоторые части моего кода выполнялись независимо друг от друга, одновременно.

Parallel — это один из способов решения проблемы одновременности, когда задачи выполняются на отдельных процессорах или ядрах параллельно.

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

Скажем, Erlang реализует сразу два подхода к одновременному выполнению задач: он запускает несколько планировщиков, каждый из которых работает на своем процессорном ядре, и распределяет между ними потоки виртуальной машины. Но так как потоков обычно гораздо больше, чем планировщиков, то каждый планировщик внутри себя реализует вытесняющую многозадачность на основе сокращений(reductions). При этом конкретный поток работает абсолютно, идеально синхронно со стороны кода. Я расскажу о планировщике Erlang в деталях в одной из следующих статей. Там все очень интересно.

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

Ради справедливости нужно заметить, что есть экспериментальные реализации многопоточного движка JavaScript, который реализует concurrency. Вот, взгляните: https://medium.com/@voodooattack/multi-threaded-javascript-introduction-faba95d3bd06

Многозадачность

Я выделяю два основных вида многозадачности.

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

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

Такая многозадачность реализована в Erlang, Go и Haskell.

Кооперативная
Тут все наоборот: потоки сами передают управление другим потокам, когда захотят. В старых ОС были именно такие планировщики. Кооперативная многозадачность реализована во многих языках, например в Python, OCaml, Ruby, Node.js.

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

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

Проблемы планирования задач

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

Переключение контекста
У первой проблемы есть несколько возможных решений. Самое простое — просто подождать, пока задача закончится. Но что вы будете делать, если в одной из задач вдруг окажется бесконечный цикл? По такому принципу работает JavaScript, однако при достаточно долгом выполнении одной задачи вмешается уже сам браузер и предложит остановить обнаглевший скрипт.

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

Приоритеты
Теперь второй вопрос: как отсортировать очередь задач, чтобы всем досталось немного времени, и никто не обиделся? Ну, можно вообще не париться, и просто выполнять задачи по очереди: первый зашел, первый вышел (FIFO). Но в таком случае при постоянном притоке задач каждая задача будет вынуждена подождать, пока до нее дойдет очередь.

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

Наконец, можно реализовать систему приоритетов, как это сделано в планировщиках современных ОС.

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

Общая память

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

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

Для решения этой проблемы применяют блокировки, неблокирующий доступ (CAS) и некоторые особенности конкретных языков.

Блокировки
Блокировки работают очень просто: прежде чем писать в переменную, поток должен захватить семафор. Остальные потоки будут вынуждены ждать, пока семафор не освободится, и лишь потом один из других потоков снова захватит семафор, и так далее. Разумеется, это медленно работает, а также намертво блокирует ожидающие потоки. Кроме того, можно прекрасным образом написать код с взаимными блокировками.

Краевой случай семафора — мьютекс, максимально упрощенный семафор. Главное в нем то, что только один поток в один момент времени может владеть мьютексом. Операционные системы часто имеют свои высокопроизводительные реализации мьютексов — фьютексы в Linux, FAST_MUTEX в Windows. Кроме того, в различных языках есть свои специализированные реализации мьютексов для особых задач.

Не-блокировки
Чтобы избежать части проблем, придумали неблокирующие реализации синхронизации. Одна из них — CAS, compare and set. Я оставлю ссылку, чтобы вы могли почитать о том, как это работает: https://ru.wikipedia.org/wiki/Сравнение_с_обменом. И вот еще вам небольшая презентация: slideshare.net/23derevo/nonblocking-synchronization

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

Haskell первым реализовал еще один подход к проблеме синхронизации — STM, software transactional memory. По сути, это реализация транзакционного чтения-записи в общую память, аналогично тому, как устроены транзакции в базах данных. Подробнее можно почитать тут: https://ru.wikipedia.org/wiki/Программная_транзакционная_память

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

Concurrent vs Parallel vs Async

Многозадачность

Я выделяю два основных вида многозадачности.

Такая многозадачность реализована в Erlang, Go и Haskell.

Проблемы планирования задач

Наконец, можно реализовать систему приоритетов, как это сделано в планировщиках современных ОС.

Общая память

Источник

Немного о многопоточном программировании. Часть 1. Синхронизация зло или все-таки нет

Мне по работе часто приходится сталкиваться с высоконагруженными многопоточными или многопроцессными сервисами (application-, web-, index-server).
Достаточно интересная, но иногда неблагодарная работа — оптимизировать все это хозяйство.
Растущие потребности клиентов часто упираются в невозможность просто заменить железную составляющую системы на более современную, т.к. производительность компьютеров, скорость чтения-записи жестких дисков и сети растут много медленнее запросов клиентов.
Редко помогает увеличение количества нодов кластера (система как правило распределенная).
Чаще приходится запустив профайлер, искать узкие места, лезть в source code и править ляпы, которые оставили коллеги, а иногда и сам, чего греха таить, много лет назад.
Некоторые из проблем, связаных с синхронизацией, я попытаюсь изложить здесь. Это не будет вводный курс по многопоточному программированию — предпологается, что читатель знаком с понятием thread и context switch, и знает для чего нужны mutex, semaphore и т.д.

Любому разработчику, многопоточно проектирующему что-то большее чем «Hello world», ясно, что создать полностью асинхронный код невероятно сложно — нужно что-то писать в общий channel, изменить структуру в памяти (к примеру повернуть дерево hash-таблицы), забрать что-то из очереди и т.д.
Синхронизируя такой доступ, мы ограничеваем одновременное исполнение некоторых критичных участков кода. Как правило это один, редко несколько потоков (например 1 writer/ N readers).
Необходимость синхронизации неоспорима. Чрезмерная же синхронизация очень вредна — кусок программы более-менее шустро работаюший на 2-х или 3-х потоках, уже для 5-ти потоков может выполняться почти «singlethreaded», а на 20-ти даже на очень неплохом железе практически ложится спать.

Однако практика показывает, что иногда и недостаточная синхронизация исполнения приводит к тому же результату — система залипает. Это происходит, когда исполняемый параллельно код содержит например обращения к HDD (непрерывный seek), или при множественном обращении к различным большим кускам памяти (например постоянный сброс кэша при context switch — CPU cache просто тупо отваливается).

Используйте семафоры (semaphore)

Такой метод использования семафоров довольно прост и не обязательно требует полного понимания процесса, но имеет множество недостатков, в том числе тот факт, что максимальное количество потоков для каждого блока будет скорее всего подбираться в бою (в продакшен, на системе клиента) — что не всегда есть хорошо. Зато огромным преимуществом такого способа оптимизации является возможность быстро увеличить количество потоков всего сервиса, без изменения execution plan, т.е. практически без переделки всего движка — просто проставив несколько семафоров на предыдущее значение в узких местах. Я не сторонник необдуманно использовать семафоры, но в качестве временного решения (для успокоения клиента), я не раз использовал этот метод, что бы впоследствии спокойно переделать «правильно», вникнув в исходный код.

Расставляйте приоритеты (priority)

Приоритеты являются очень удобным механизмом, так же позволяющим довольно просто «облегчить» приложение. Например, если в системе логи пишутся отдельным потоком, то уменьшив ему приоритет до минимального, можно сильно «облегчить» процесс, не уменьшая log-level.
Например конструкцию следующего вида можно использовать если пул со множеством потоков обрабатывает задачи разной приоритетности:

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

Divide et impera (Разделяй и властвуй)

Довольно часто не требуется мгновенное исполнение какого-либо участка кода — т.е. некоторое действие или часть задачи можно отложить. Например писать логи, считать посещения, переиндексировать кэш, и т.д.
Существенно повысить скорость выполнения можно, выделяя куски синхронного кода в отдельные задачи, с последующим выполнением их позже (например фоново — используя т.н. background service). Это может быть отдельный поток, пул потоков или даже другой процесс aka RPC (например асинхронный вызов WebService). Естественно временная стоимость вызова (помещения в очередь и т.д.) этой задачи должна быть меньше стоимости самого исполнения.
Пример с отдельным LOG-потоком:

Очереди, FIFO, LIFO и многопоточность

Организация очереди, пула данных или последовательного буфера дело не хитрое, однако нужно иметь в виду, что при многопоточности и прочих равных условиях очередь LIFO стоит сделать выбором номер один (конечно если при этом последовательность действий не важна). Иногда можно комбинировать или группировать LIFO и FIFO (элементы LIFO сделать маленькими очередями FIFO или например строить буфер с конца и т.д.). Смысл таких извращений кроется в кеше процессора и отчасти в виртуальной организации памяти. Т.е. вероятность того, что последние элементы из LIFO еще находятся в кеше процессора несравненно выше вероятности того же у FIFO той же длинны.

ReadWriteMutex

Очень часто синхронизировать необходимо только в случае изменения объекта. Например при записи в общий файл, при изменении структуры списков или hash таблиц и т.д. При этом, как правило, это разрешается только одному потоку, при этом часто даже читающие потоки блокируются (что бы исключить dirty read и вылет программы с исключением, поскольку записи до конца изменения не совсем валидны).
Блокировку таких объектов правильнее делать используя RW-mutex, где читающие потоки не блокируют друг друга, и только при блокировке записи происходит полная синхронизация кода (исполняется одним потоком).
При использовании read/write-mutex, нужно всегда точно представлять, как происходит чтение объекта, поскольку в некоторых случаях, даже при чтении, объект может изменятся (например при построении внутреннего cache при первичной инициализации или реинициализации после записи). В этом случае идеальный API предоставляет callback для блокировки, либо блокирует самостоятельно в случае многопоточности, либо возможное использование RW-mutex, со всеми исключениями, подробнейше описано в документации к API. В некоторых реализациях RW-mutex нужно заранее знать (сообщать mutex) количество reader-потоков, иногда writer-потоков. Это связано с конкретной реализацией блокировки записи (как правило используются семафоры). Несмотря на эти и другие ограничения, при наличии нескольких reader-потоков, желательно по возможности пытаться выполнить синхронизацию именно на таком mutex.

Читайте документацию, читайте source code

Проблема незнания, иногда непонимания того, что скрывается за тем или иным классом или объектом, особенно критично проявляется при использовании их в многопоточном приложении. Особенно это касается и базовых объектов синхронизации. Попробую разъяснить, что я имею в виду, на примере неправильного использования RW-mutex.
Один мой коллега как-то использовал fair RW-mutex, построеный на семафорах. Он поленился динамически передавать количество reader-потоков в класс RWMutex (задал статически «максимально возможное» значение 500) и написал следующий код для writer-потока:

И при хорошей нагрузке, сервер ~~уходил в глубокий запой~~ ложился в спячку. Все дело в том, что он сделал две ошибки — взяв статичное значение 500 и не разобрался как будет вести себя такой RW-mutex на этой конкретной платформе. Т.к. RW-mutex был сделан fair — использовался код, подобный следующему:

Т.е. при добавлении в хеш-таблицу hashTab 100-а значений, при одновременном чтении несколькими reader-потоками, мы имели 100*500 блокировок (и выпадание в осадок на несколько милисекунд из-за context switch). Самое интересное в этой истории, что это был базовый класс RWSyncHashTable, активно используемый повсеместно в нашем коде.
Нужно четко запомнить: некоторые конструкции API могут быть уже синхронизированы. Иногда это даже конструктор и деструктор объекта. В этом случае дополнительная синхронизация — часто вред. Это как раз тот случай, когда кашу маслом испортишь.
Читайте источники, заглядывайте в документацию к API — и такие ляпы, с большей вероятностью, обойдут Вас стороной.

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

Наверное стоит закончить на этом первую часть (а-то много букв). Если где-то написал прописные для кого-то истины, прошу простить покорно — не со зла. Предложения, пожелания, критика приветствуются.

Источник