Обзор моделей работы с потоками
Обзор моделей работы с потоками
Начало (С и native threads)
Первая модель, которую мы рассмотрим — это стандартные потоки ОС (threads). Их поддерживает каждая современная ОС, несмотря на разницу в API. В принципе, поток — это процесс выполнения инструкций, который работает на выделенном процессоре, выполнение которого контролирует планировщик (scheduler) ОС, и который может быть заблокирован. Потоки создаются внутри процесса и пользуются общими ресурсами. Это означает, что, например, память и декскрипторы файлов, являются общими для всех потоков процесса. Подобный подход и принято называть native threads.
Linux позволяет использовать данные потоки с помощью библиотеки pthread. BSDs тоже поддерживают pthreads. Потоки Windows работают немного иначе, но базовый принцип тот же.
Java and Green Threads
Когда появилась Java, она принесла с собой другой тип многопоточности, который называется green threads. Green threads — это, по сути, имитация потоков. Виртуальная машина Java берёт на себя заботу о переключении между разными green threads, а сама машина работает как один поток ОС. Это даёт несколько преимуществ. Потоки ОС относительно дороги в большинстве POSIX-систем. Кроме того, переключение между native threads гораздо медленнее, чем между green threads.
Это всё означает, что в некоторых ситуациях green threads гораздо выгоднее, чем native threads. Система может поддерживать гораздо большее количество green threads, чем потоков OС. Например, гораздо практичнее запускать новый green thread для нового HTTP-соединения к веб-серверу, вместо создания нового native thread.
Однако есть и недостатки. Самый большой заключается в том, что вы не можете исполнять два потока одновременно. Поскольку существует только один native thread, только он и вызывается планировщиком ОС. Даже если у вас несколько процессоров и несколько green threads, только один процессор может вызывать green thread. И всё потому, что с точки зрения планировщика заданий ОС всё это выглядит одним потоком.
Начиная с версии 1.2 Java поддерживает native threads, и с тех пор они используются по умолчанию.
Python
Python — это один из моих любимейших скриптовых языков и он был одним из первых предложивших работу с потоками. Python включает в себя модуль, позволяющий манипулировать native threads, поэтому он может пользоваться всеми благами настоящей многопоточности. Но есть и одна проблема.
Python использует глобальную блокировку интерпретатора (Global Interpreter Lock, GIL). Эта блокировка необходима для того, чтобы потоки не могли испортить глобальное состояние интерпретатора. Поэтому две инструкции Python не могут выполняться одновременно. GIL снимается примерно каждые 100 инструкций и в этот момент другой поток может перехватить блокировку и продолжить своё выполнение.
Сперва это может показаться серьёзным недостатком, однако на практике проблема не столь велика. Любой заблокированный поток как правило освобождает GIL. Расширения С также освобождают её когда не взаимодействуют с Python/C API, поэтому интенсивные вычисления можно перенести в C и избежать блокировки выполняющихся потоков Python. Единственная ситуация, когда GIL действительно представляет проблему — это ситуация когда поток Python пытается выполняться на многоядерной машине.
Stackless Python — это версия Python, которая добавляет “tasklets” (фактически green threads). По их мотивам был создан модуль greenlet, который совместим со де-факто стандартом: cPython.
Модель потоков Ruby постоянно меняется. Изначально Ruby поддерживал лишь собственную версию green threads. Это хорошо работает во многих сценариях, но не даёт пользоваться возможностями многопроцессорности.
JRuby перевёл потоки Ruby в стандартные потоки Java, которые, как мы выяснили выше, являются native threads. И это создало проблемы. Потокам Ruby нет необходимости взаимно синхронизоваться. Каждому потоку гарантируется, что никакой другой поток не получит доступа к используемому общему ресурсу. Подобное поведение было сломано в JRuby, так как native threads переключаются принудительно (preemptive) и поэтому любой поток может обратиться к общему ресурсу в произвольное время.
Из-за подобной несостыковки и желания получить native threads разработчиками C Ruby было решено, что Ruby будет переходить на них в версии 2.0. В состав Ruby 1.9 был включён новый интерпретатор, который добавил поддержку fibers, которое, насколько я знаю, являются более эффективной версией green threads.
Короче, модель потоков Ruby — это плохо документированная каша.
Perl предлагает интересную модель, которую Mozilla позаимстовала для SpiderMonkey, если я не ошибаюсь. Вместо использования глобальной блокировки интерпретатора как в Python, Perl сделал глобальное состояние локальным и фактически запускает новый интерпретатор для каждого нового потока. Это позволяет использовать настоящие native threads. Не обошлось и без пары загвоздок.
Во-первых, вы должны явно указывать переменные доступными для других потоков. Вот что происходит, когда всё становится локальным для потока. Приходится синхронизировать значения для межпоточного взаимодействия.
Во-вторых, создание нового потока стало очень дорогой операцией. Интерпретатор — большая штука и многократное копирование его съедает много ресурсов.
Erlang, JavaScript, C# and so on
Существует множество других моделей, которым время от времени находят применение. Например Erlang, использует архитектуру «ничего-общего» (shared nothing), которая стимулирует использование лёгких пользовательских процессов вместо потоков. Подобная архитектура просто великолепна для параллельного программирования, так как она устраняет всю головную боль насчёт синхронизации, а процессы настолько легки, что вы можете создать любое их количество.
JavaScript обычно не воспринимается как язык, который поддерживает работу с потоками, но она необходима и там. Модель работы с потоками в JavaScript очень похожа на ту, что используется в Perl.
C# использует native threads.
От себя: досаду на некоторую поверхностность статьи (которую я и сам осознаю) адресуйте автору. Я всего-навсего перевёл в меру своих скромных возможностей. 😉 Буду рад уточнениям и дополнениям в комментариях.
От себя 2: по мотивам комментариев таки подправил пару фраз. Прости, автор! 🙂
Источник
Другой взгляд на многопоточность
Вот уже в который раз хочется поднять тему многопоточного программирования. Сейчас я попытаюсь донести мысль, что если посмотреть на эту тему под другим — более простым, как мне кажется, углом, то она не будет казаться такой сложной и неприступной для начинающих. В этой статье будет минимум формализма и известных (и не очень) терминов.
Откуда ноги растут
В начале 2000-х годов наблюдалось замедление скорости роста производительности процессоров. К 2005 году увеличение тактовой частоты процессора практически остановилось. Сейчас мы можем вспомнить 2010 год и выход Intel Core i5—680 с тактовой частотой 3,60 ГГц. Прошло десять лет и сейчас можно приобрести Intel Core i9-10850K с частотой от 3,60 до 5,20 ГГц. Разница, как можно заметить, не велика. Этот пример очень синтетический и примитивный, но он наглядно показывает скорость и направление развития современных процессоров. Конечно, производительность процессора зависит не только от тактовой частоты, а еще и от других параметров — размера и количества кэшей, частоты шины, типа сокета и так далее. И зачастую, особенно на боевых машинах, оказывается, что выгоднее взять процессор с более низкой тактовой частотой.
Что делать?
Когда вертикальное масштабирование (качественный рост) приходит к своему пику и ждет очередной революции, в дело вступает горизонтальное масштабирование (количественный рост). Решение было простым, сделать из одного процессора несколько. Так появились многоядерные процессоры.
Ядра процессора должны с чем-то работать, выполнять команды и куда-то складывать результат. Такое место называется память. Чтобы смоделировать память, мы можем представить ее как очень длинный массив данных, где индекс массива это адрес.
Представим, что мы обладаем общей памятью и ядрами в количестве N штук.
Операций, которые можно выполнять с памятью, всего две — чтение по адресу(индексу) и запись по адресу(индексу) (как будто мы работаем с массивом). Пока что будем считать, что операции с памятью выполняются сразу и без каких-либо задержек.
Поток
К сожалению, придется ввести еще один термин, без него никак не получится перейти к многопоточному программированию.
Пусть ядро — это станок на заводе, тогда поток — это рабочий, который за ним работает. У каждого рабочего есть набор задач, которые он должен выполнить — это исходный код. Пока что будем считать, что исходный код исполняется по порядку, это значит, что операция 1 гарантировано выполнится до операции 2, операция 2 до операции 3 и так далее.
Давайте попробуем решить простую задачу. Какие варианты пар (a, b) возможны после завершения исполнения обоих потоков, положитесь на свою интуицию, стоит рассмотреть даже самые, казалось бы, невозможные варианты:
Ответ
Пусть поток 1 выполнился полностью, а поток 2 еще не стартовал. Тогда в результате будет пара (0, 1)
Аналогично, поток 2 выполнился полностью, а поток 1 еще не стартовал. Тогда в результате будет пара (1, 0).
Во всех остальных случаях (0, 0)
Случая (1, 1) быть не может, так как хотя бы один поток перед своим завершением обнулит какую-то переменную.
В итоге получается [ (0, 1), (1, 0), (0, 0) ]
Как вы могли догадаться, понимание результата работы многопоточного кода сводится к рассмотрению всех вариантов его исполнения. В данном случае формально такая модель исполнения называется моделью последовательной консистентности (sequential consistency, SC).
Согласно данной модели, любой результат исполнения многопоточной программы может быть получен как последовательное исполнение некоторого чередования инструкций потоков этой программы. (Предполагается, что чередование сохраняет порядок между инструкциями, относящимися к одному потоку.)
К сожалению, настоящие программы оперируют не двумя переменными и не только пишут в память, но еще и читают ее. Попробуйте решить следующий пример, тут немного сложнее:
Ответ
Всего существует 6 вариантов исполнения. 1 — 4 варианты дадут результат (1, 1), 5 вариант даст результат (0, 1), 6 вариант даст результат (1, 0).
Многопоточность была бы простой если бы все закончилось здесь.
Конец?
К сожалению, или к счастью, это еще не конец. На процессорах самых популярных архитектур — x86, Arm, Power PC и Alpha, исполнение предложенного выше примера может быть другим — возможен результат (0, 0).
Код на языке C рано или поздно завершается, хотя в модели SC не должен.
Это не вписывается в модель SC (sequential consistency), поскольку не существует такого исполнения, которое бы привело к результату (0, 0). Выше мы допустили, что «операции с памятью выполняются сразу и без каких-либо задержек». Но для современных процессоров это совсем не так.
Если вы разрабатываете ПО, вы часто сталкиваетесь с таким термином как кэш. Удобно копить результат и лишний раз не обращаться к удаленному ресурсу. База данных для сервера, это как оперативная память для процессора. Ходить в нее дорого-далеко-долго (кому что больше нравится). Куда удобнее прочитать один раз, положить в кэш и при повторном чтении читать из кэша. Тоже самое и с записью. Например вы используете в своей программе запись в лог и вам не всегда хочется писать каждое сообщение сразу в файл, вы можете их хранить некоторое время в памяти, а потом при накоплении какого-то количества записать их за один раз.
Сейчас мы разберем (в качестве модели) архитектуру x86.
Кэш для чтения, буфер записи (англ. Store Buffer) для записи — все просто.
1. Процессор всегда читает из кэша
2. Если в кэше такого адреса не найдено, процессор идет в память и копирует его в кэш и читает из кэша.
3. Процессор всегда пишет в буфер записи.
4. При записи нового значения в буфер запись происходит и в кэш.
5. Записи из буфера попадают в память.
Все хорошо, когда мы живем в мире одного ядра. Но когда ядер несколько начинаются вопросы.
Ядро 1 прочитало переменную f в кэш, ядро 2 изменило переменную f. Как ядро 1 узнает о изменении переменной?
Пока что, в нашей модели, никакой синхронизации между ядрами у нас нет. Так и сломался наш пример, возьмем вариант исполнения 1 (во вкладке ответ):
Мы хотим вернуть нашему примеру исполнение, чтобы он согласовывался с моделью SC — интуитивно понятной моделью.
Барьеры
Для таких случаев в процессорах x86 и Arm (а также и в других) предусмотрены специальные инструкции.
load memory fence — обновить кэш*, поток не выполняет инструкции дальше, пока не выполнит обновление кэша
store memory fence — записать накопленные в буфере записи данные в память, поток не выполняет инструкции дальше, пока не запишет все данные в память
*Обновление кэша происходит в соответствии с протоколом когеренции кэшей (для x86 это MESI) и на самом деле происходит при других обстоятельствах. Но это тема отдельного разговора. Пока для простоты можно считать load memory fence необходимой для этого операцией.
Тогда, чтобы исключить результат (0, 0) в нашем примере, нужно придумать, куда и какие именно барьеры поставить (барьер это инструкция, для простоты можно считать его вызовом функции — например store_memory_barrier(), и добавить до/после какой-либо строки).
Замечание-ответ
Простым решением конечно же будет являться такое добавление барьеров. После записи x и y необходимо, чтобы они попали в память. А перед чтением x и y нужно обновить кэш.
Но, подумайте, можно ли избежать лишнего добавления барьера, поскольку каждый барьер останавливает поток пока не обновится кэш или не запишется буфер записи. Если вы пишете конкурентный код, каждый барьер может оказывать решающее значение на производительность.
Попробуем раскрутить простое решение
1) Можем ли мы убрать store barrier? — не можем, тогда значения x и y навечно(в нашей модели) останутся в буфере записи.
2) Можем ли убрать load barrier? — тут сложнее. Интуитивно понятно, что если убираем load barrier в одном потоке, то убираем и в другом, поскольку модель симметрична. Перебрав все варианты я пришел к выводу, что можно! Поскольку load barrier ничего нам не дает — значения x и y в кэше еще отсутствуют. И если вы ответили так, то в нашей идеальной модели вы правы.
Но, к сожалению, в реальной операционной системе такой код работать не будет. Чтобы не переусложнять статью, при первой потребности опишу причины такого поведения в комментариях. Поэтому представляю рабочий вариант(решение через добавление обоих барьеров), который корректно будет исполнятся в любом случае (вариант на процессоре x86).
Код скомпилирован с ключом -O0 (отключение оптимизаций)
Если Вам удалось понять содержимое статьи, то любые другие элементы многопоточного программирования дадутся Вам намного легче.
Конец
Если Вы сталкиваетесь с многопоточностью впервые, скорее всего с первого и даже с третьего раза Вам будет понятно не всё. Для полного понимания нужна практика.
В этой статье не затрагивалась операционная система, блокировки, методы синхронизации, модели памяти, компиляторные оптимизации и многое другое. Если статья покажется читателям хорошей и самое главное понятной, я постараюсь в скором времени рассказать о других аспектах многопоточности в таком же ключе.
Поскольку это моя первая статья, я скорее всего допустил множество ошибок и неточностей, поэтому буду рад услышать комментарии. Спасибо за внимание!
Источник
