В этой статье мне хотелось бы задокументировать всё, что я знаю о том, какие средства можно использовать для эффективного использования вычислительных ресурсов систем и/или удобства разработки.
И, надеюсь, кому-нибудь это может оказаться полезно, ибо кто-нибудь может чего-нибудь не знать, или, наоборот, окажется полезно мне, если кто-нибудь покажет что-нибудь ещё/укажет на изъяны в моих знаниях.
- Параллелизм
- Кооперативность
- Асинхронность
- Коллбэки
- Промисы (promises, обещания) — монады
- async/await — обещания + корутины
Параллелизм
Когда-то процессоры были одноядерные (до 2001 года), а в системах был только один процессор (до 1966 года). А затем инструкции стали выполняться одновременно в рамках одной системы.
Потоки
Потоки — абстракция операционной системы, позволяющая выполнять некие куски кода параллельно. Каждый поток имеет «контекст», в который входит кусок памяти под стек и копию регистров процессора. Очевидно, что потоков в системе может быть запущено куда больше, чем у нас имеется процессоров и ядер, поэтому операционная система занимается тем, что schedule'ит (занимается диспетчеризацией, планированием) выполнение процессов, восстанавливая регистры в ядрах процессора для работы некоторого потока некоторое время, затем сохраняет обратно и даёт выполняться следующему.
Планирование должно быть хорошим, чтобы каждый поток работал примерно одинаковое время (но при этом достаточно малое, т.е. нас не удовлетворит, если каждый поток будет работать по несколько секунд), а так же само планирование занимало как можно меньше времени. Тут мы, традиционно, приходим к балансу latency/throughput: если давать потокам работать очень маленькие промежутки времени — задержки будут минимальны, но отношение времени полезной работы к времени на переключение контекстов уменьшится, и в итоге полезной работы будет выполнено меньше, а если слишком много — задержки станут заметны, что может проявиться на пользовательском интерфейсе/IO.
Тут же хотелось бы отметить довольно важную вещь, к которой будем отсылаться позже. Потоки можно погружать в сон. Мы можем попросить операционную систему усыпить поток на некоторое время. Тогда она может учитывать это при планировании, исключив этот поток из очереди на получение процессорного времени, что даст больше ресурсов другим потокам, либо снизит энергопотребление. Кроме того, в теории можно настраивать приоритеты, чтобы некоторые потоки работали дольше, либо чаще, чем другие.
Синхронизация
Ядер у нас стало много, а память как была одна сплошная, так и осталась (хотя в современной организации памяти можно ногу сломать, там и физическая, и виртуальная, и страницы туда-сюда ходят, что-то где-то кешируется, проверяется на ошибки, странно, что всё это до сих пор работает вообще).
И когда мы из нескольких потоков начинает менять одну и ту же память — всё может пойти совершенно не так, как мы этого хотели. Могут возникать «гонки», когда в зависимости от того, в каком порядке выполнятся операции, вас ожидает разный результат, что может приводить к потере данных. И, что ещё хуже — данные могут совсем портиться в некоторых случаях. К примеру, если мы записываем некоторое значение на невыровненный адрес памяти, нам нужно записать в две ячейки памяти, и может получиться так, что один поток запишет в одну ячейку, а другой в другую. И если вы записывали указатель, или индекс массива — то скорее всего вы получите падение программы через какое-то время, когда попытаетесь обратиться к чужой памяти.
Чтобы этого не происходило, нужно использовать примитивы синхронизации, чтобы получать гарантии того, что некоторые блоки кода будут выполняться в строгом порядке относительно каких-то других блоков кода.
Spinlock
Самый простой примитив: у нас есть boolean'овая переменная, если true — значит блокировка кем-то была получена, false — свободна. И два метода: Lock, Unlock. Unlock устанавливает значение в false. Lock в цикле делает либо TAS, либо CAS (об этом будет далее), чтобы атомарно сменить false на true, и пытаться до тех пор, пока не получится.
Имея такую штуку мы можем делать блоки кода, которые будут выполняться эксклюзивно (т.е. пока один выполняется, другой стартовать не может). В начале блока он выполняет метод Lock, в конце Unlock. Важно, чтобы он не попытался сделать Lock второй раз, иначе некому будет сделать Unlock и получится deadlock.
Возможно навешивание плюшек. Например, сохранение идентификатора потока, кто захватил блокировку, чтобы никто кроме захватившего потока, не мог сделать Unlock, и если мы сделали Lock второй раз — он не зациклился, такая реализация это называется «мьютексом». А если вместо boolean'а у нас беззнаковое число, а Lock ждёт числа больше нуля, уменьшая его на единицу, получается «семафор», позволяющий работать некоторому заданному числу блоков одновременно, но не более.
Поскольку блокировка работает в бесконечном цикле она просто «жгёт» ресурсы, не делая ничего полезного. Существуют реализации, которые при неудачах говорят планировщику «я всё, передай остаток моего времени другим потокам». Или, например, есть «адаптивные мьютексы», которые при попытке получить блокировку, которую удерживает поток, который в данный момент выполняется — использует spinlock, а если не выполняется — передаёт выполнение другим потокам. Это логично, т.к. если поток, который может освободить ресурс сейчас работает, то у нас есть шансы, что он вот-вот освободится. А если он не выполняется — есть смысл подождать чуть больше и передать выполнение другому потоку, возможно даже тому, кого мы ждём.
По возможности стоит избегать использования спинлоков, их можно использовать только если блоки кода, которые они защищают, выполняются невероятно быстро, что шансы коллизии крайне малы. Иначе мы можем затратить довольно большое количество ресурсов просто на обогрев комнаты.
Лучшая альтернатива блокировкам — усыпление потока, чтобы планировщик исключил его из претендентов на процессорное время, а затем просьба из другого потока разбудить первый поток обратно, чтобы он обработал новые данные, которые уже на месте. Но это справедливо только для очень длительных ожиданий, если же скорости освобождения блокировок соразмерны с одним «тактом» выполнения потока — производительнее использовать спинлоки.
Барьер памяти
В погоне за скоростью работы, архитекторы процессоров создали очень много тёмной магии, которая пытается предсказывать будущее и может переставлять процессорные инструкции местами, если они не зависят друг от друга. Если у вас каждый процессор работает только со своей памятью — вы никогда не заметите, что инструкции a = 5 и b = 8 выполнились в другом порядке, не так, как вы написали в коде.
Но при параллельном исполнении это может привести к интересным случаям. Пример из википедии:
// Processor #1:
while (f == 0);
// Memory fence required here
print(x);// Processor #2:
x = 42;
// Memory fence required here
f = 1;Казалось бы, что здесь может пойти не так? Цикл завершится, когда f будет присвоена единица, на момент чего переменная x вроде как уже будет равна 42. Но нет, процессор может произвольно менять местами такие инструкции и в итоге сначала может выполниться f = 1, а затем x = 42 и может вывестись не 42, а что-нибудь другое. И даже более того. Если с порядком записи всё нормально, может быть изменён порядок чтения, где значение x прочитается перед тем, как мы войдём в цикл.
Для противодействия этому используются барьеры памяти, специальные инструкции, которые препятствуют тому, чтобы инструкции были перемещены сквозь них. На хабре есть отличный перевод на эту тему.
Атомарность
Поскольку некоторые операции с памятью могут быть потоконебезопасны (например, прибавить к числу другое число и сохранить его обратно), существуют операции для проведения атомарных операций, для которых есть специальные процессорные инструкции.
Наиболее часто используемые:
- Test-and-Set — записывает значение, возвращает предыдущее.
- Compare-and-Swap — записывает значение только в том случае, если текущее значение переменной совпадает с неким ожидаемым, возвращает успех записи.
Возвращаясь к нашему спинлоку, операция получения блокировки может быть реализована как при помощи TAS:
void lock() {
// Мы будем записывать 1 до тех пор, пока между нашими выполнениям кто-то не запишет в неё 0
while (test_and_set(&isLocked, 1) == 0);
}Так и при помощи CAS:
void lock() {
// Пытаемся записать 1, ожидая 0
while (!compare_and_swap(&isLocked, 0, 1))
}… как я сказал, мне бы хотелось задокументировать всё, но… получилось довольно много, поэтому я разобью это дело на три статьи. Stay tuned.
UPD: Вторая часть.
Комментарии (38)
12sd
25.12.2016 09:33+6Concurrency is not parallelsim.
«In programming, concurrency is the composition of independently executing processes, while parallelism is the simultaneous execution of (possibly related) computations. Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.»
Rulexec
25.12.2016 10:04-2Да, так и есть. Но ничто не мешает конкурентным процессам выполняться одновременно. Поэтому я всё-таки считаю, что параллелизм это одна из возможных оптимизаций конкурентных подходов, которые существуют вне зависимости от того, есть ли у нас возможность выполнять что-то параллельно на самом деле или нет.
Абсолютно любой многопоточный алгоритм можно переписать в кооперативном стиле, когда код каждого потока будет делать явные yield'ы, чтобы передать управление другому потоку. Или выполнять код в виртуальной машине, считая операции (так, например, в Erlang'е работают их сверхлёгкие процессы).
А когда у нас появляется многопоточность — наши подходы никак не меняются и в основном мы просто создаём столько потоков, сколько у нас логических ядер, и в них выполняем функции, которые берём с какой-нибудь очереди задач. В которую кладём обработчики разных событий, которые возникают от асинхронного I/O.
(а синхронный I/O вряд ли уже кто использует, но его можно реализовать и без параллельного выполнения, достаточно в цикле проверять, есть ли данные, не блокируя, и передавать выполнение другому потоку, если данных нет)
mayorovp
26.12.2016 08:56Но, вообще говоря, параллелизм — это один из способов достижения конкурентности.
m_z
26.12.2016 13:44Не способ. При параллелизме нет конкурентности. Параллелизмом лишь можно ускорить конкурентность. Да и что значит «достижение»? Например, если шедулер решил все треды выполнять на каком-то одном ядре из 8, конкурентность никуда не пропадёт.
mayorovp
26.12.2016 14:01Поведение планировщика — это деталь реализации.
m_z
26.12.2016 19:11Так о том и речь. Распараллеливает шедулер, если он этого делать не будет, конкурентность не исчезнет. А если реализовать конкурентность через параллелизм, то как только все ядра получат по треду, работа выполняться будет, но пользоваться системой будет нельзя. Потому заголовок статьи бессмысленный.
mayorovp
26.12.2016 19:24Как это — не исчезнет? Если написать намеренно плохой алгоритм планирования потоков, то конкурентность именно что исчезнет.
m_z
26.12.2016 22:11А почему исчезнет? Можно с другой стороны подойти. Если параллелизм это один из способов, то вот задача: как выполнить конкурентно 20 потоков на 2 ядрах, используя этот способ?
mayorovp
26.12.2016 22:42Какая разница, сколько ядер? Наблюдаемое поведение от их количества не зависит.
Если есть ОС с вытесняющей многозадачностью и адекватным планировщиком, то с точки зрения программы все ее потоки выполняются параллельно.
Особенный только случай 1 ядра. Но даже там применяются те же самые примитивы синхронизации.
nightwolf_du
25.12.2016 14:31Неплохо еще поднять тему lock-free коллекций ( использование, общая методология написания,… )
iperov
25.12.2016 18:02-18Корейцы еще 10 лет назад переплюнули ваши представления о высоконагруженной многопоточности.
Посмотрите на их архитектуры MMORPG серверов. Только в свободном доступе эти исходники не увидеть. Можно только реверс-инженерить.
Так вот ваши асинки, корутины-шмарутины — это детский лепет, на фоне действительно мощных и работающих механизмов.
Такое ощущение, что все придумыватели многопоточных механизмов сами вообще не создавали высоконагруженных серверов, а только как теоретики что-то там выдумывают, и издают об этом книги.
Des333
25.12.2016 18:32+7Ну, если Вы эти механизмы изучили, так поделитесь знаниями с общественностью.
Думаю, это будет очень полезно и интересно многим читателям хабра.
Заранее спасибо!iperov
25.12.2016 20:29-22К сожалению, «поделиться» в сфере IT у русских на последнем месте. Я не исключение. Ведь из затраченного времени хочется извлечь прибыль, а в России не выжить без прибыли, это не Норвегия.
В идеале бы создать ITлантиду.
ITлантида — место куда сложно попасть, но если попал, не надо париться о прибыли, люди снабжаются сверхнеобходимого, все работают ради творчества и прогресса, делятся своими наработками с остальным миром, негров правда завозят по пропускам, должен же кто-то чинить унитазы.
marsermd
25.12.2016 23:18+7Не видел ни одного крутого специалиста, который бы считал невыгодным делиться опытом.
NDA — другое дело, но если вы говорите о реверс-инжиниринге, NDA вряд ли применяется.
oYASo
25.12.2016 21:30+13Классный пост:
- Посмотрите на архитектуры, которые закрыты;
- Асинки и корутины-шмарутины говно, ведь у Корее есть принципиальное новые средства синхронизации (на самом деле не новые, ведь они уже 10 лет назад все придумали);
- Мировой computer science говно, то ли дело Корея!
- Ну и, конечно, только в Корее есть MMORPG, которые справляются с большими нагрузками :)
В общем, кончай ты играть в Линейку и иди делать уроки, мамка придет и наругает!
exaw
25.12.2016 20:10+3какие средства можно использовать для эффективного использования вычислительных ресурсов систем
+ векторизация (SIMD)Rulexec
26.12.2016 06:25Не упоминал про неё, ибо подумал, что она совсем уж микропараллельна, спасибо.
Ещё про GPU ничего не сказал, хотя там параллельность так параллельность (в которых сотни ядер). Но оно специфично относительно мощных вычислений, а мне бы просто за событиями смотреть и байты туда-сюда копировать.
alex-khv
26.12.2016 07:39К примеру, если мы записываем некоторое значение на невыровненный адрес памяти, нам нужно записать в две ячейки памяти, и может получиться так, что один поток запишет в одну ячейку, а другой в другую.
Можете подробнее разъяснить нарушение данных, если вести запись в невыровненный адрес.
Deosis
26.12.2016 08:18Поток А: записать по адресу 01 значение АА
Поток В: записать по адресу 01 значение ВВ
Возможна такая ситуация: (атомарна запись 2 значений)
А: записывает А по адресу 01 (00: ХАХХ)
переключаем на поток В
В: делает полную запись (00: ХВВХ)
А: записывает вторую половину значения (00: ХВАХ)
Получается по адресу 01 значение ВА
mayorovp
26.12.2016 08:52+1Вот в этом заголовке есть ошибка: "Promises/A+ — мгновенно стартующие монады с PubSub'ом".
Во-первых, не любая поддержка событий является PubSub'ом. Конкретно тот механизм, который предусмотрен в Promises/A+ — точно не PubSub. PubSub подразумевает подписку на сообщения на основе данных или метаданных — но никак не прямое указание источника событий для обработки.
Во-вторых, почему все прошлые заголовки относились к надъязыковым понятиям — а тут вдруг используется нечто javascript-специфичное? В том же C# есть аналог этих самых обещаний.
В-третьих, почему вдруг обещания будут рассматриваться после async/await — в то время как async/await на обещаниях и построены?
Rulexec
26.12.2016 14:17- Да, некорректно, просто не нашёл другого короткого понятия. Тут я имею в виду, что в случае с данной реализацией промисов всё сделано так, что можно сразу нескольким обработчикам дожидаться результата промиса. И метод .then там это примерно «если промис ещё резолвится, сделай addThenListener(callback), а если зарезолвен, то сделай callback(data)». Да, совсем не PubSub, чистые события.
- Промисы реализует кто как хочет, они действительно везде есть, но я хочу показать один из примеров, как их реализовывать не стоит (хотя некоторые плюсы всё же есть, о них тоже расскажу).
- Я расскажу о том, как работают обещания перед тем, как будет про async/await, всё будет ок.
Удалил вообще из содержания пункт про Promises/A+.
AnROm
26.12.2016 10:20+1сохранение идентификатора потока, кто захватил блокировку, чтобы никто кроме захватившего потока, не мог сделать Unlock, и если мы сделали Lock второй раз — он не зациклился, такая реализация это называется «мьютексом». А если вместо boolean'а у нас беззнаковое число, а Lock ждёт числа больше нуля, уменьшая его на единицу, получается «семафор», позволяющий работать некоторому заданному числу блоков одновременно, но не более.
Да, мьютекс в ядре реализован с помощью спин-блокировок, но если мьютекс уже захвачен, при попытке захватить его другой поток просто заснет, т.е. будет «пассивная» блокировка. Поэтому мне не совсем понятно, почему о мьютексах и семафорах написано в разделе Spinlock. Возможно, во фразе «поток не зацикливается» и имеется в виду «засыпание», но мне кажется, что для кого-то это не очевидно.mayorovp
26.12.2016 11:09Нет, тут говорилось о рекурсивных мьютексах. То есть о таких мьютексах, которые один и тот же поток может захватить несколько раз не устраивая сам себе взаимоблокировку.
CrazyOpossum
26.12.2016 13:58В асинхронности ещё можно поговорить о ново-(старо-)модном Functional Reactive Programming. Более требовательный к дизайну, зато на разработке не будет боли с callback hell.
P.S. Таки конкурентность != парелеллизм. Это всё таки о целях, а не о реализации.mayorovp
26.12.2016 14:02Какое отношение FRP имеет к асинхронности?
CrazyOpossum
26.12.2016 14:30-1Такое же как и остальное перечисленное — это ещё один паттерн. В отличие от параллельного программирования, асинхронное требует всего один механизм на уровне системных вызовов — select, poll, epoll или ещё что. Все перечисленные неявно его используют, разница только на верхнем уровне.
Отвечая на сам вопрос: FRP — это stateless способ выбрать ответ на пришедший запрос в реальном времени.mayorovp
26.12.2016 15:15Нет, FRP — это способ организации кода для поддержки зависимых значений в соответствии друг с другом. Еще его можно рассматривать как методику, позволяющую управлять потоками данных вместо потоков команд.
А вот про stateless способ выбрать ответ на входящий запрос я почему-то слышу впервые… Не могли бы вы пояснить эту мысль?
CrazyOpossum
26.12.2016 15:46«Нет» — слишком категорично, я написал определение «для чего», а вы — «как», оба могут быть верными.
Не могли бы вы пояснить эту мысль?
В чистом (в смысле функционального программирования) FRP состояние передаётся в качестве ещё одного аргумента вместе с нашим горизонтальным временем. На выходе соответственно получаем ответ и изменённый state. Профит в том, что прошлое не задерживается в графе, что сильно упрощает последующую отладку.
А где-то в глубине — обычный event-loop, дёргающий FRP граф, когда срабатывает poll. Я бы это не называл «способ организации кода», всё-таки это про проектирование, а не про написание кода.mayorovp
26.12.2016 16:35Если речь идет об "измененном state" — это по определению не stateless подход, пусть даже код 100500 раз чистый, функциональный и простой в отладке.
nrcpp
Спасибо за статью, жду следующих частей. Особенно актуально, если вы опишите асинхронность и остальное в контексте вопросов MS C# Certification, раздел Manage program flow.
Rulexec
Вторая часть