Конкурентность: Параллелизм

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


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



    Параллелизм


    Когда-то процессоры были одноядерные (до 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: Вторая часть.

    Share post

    Similar posts

    Comments 40

      +1
      Спасибо за статью, жду следующих частей. Особенно актуально, если вы опишите асинхронность и остальное в контексте вопросов MS C# Certification, раздел Manage program flow.
      +6
      Concurrency 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.»
        –2
        Да, так и есть. Но ничто не мешает конкурентным процессам выполняться одновременно. Поэтому я всё-таки считаю, что параллелизм это одна из возможных оптимизаций конкурентных подходов, которые существуют вне зависимости от того, есть ли у нас возможность выполнять что-то параллельно на самом деле или нет.

        Абсолютно любой многопоточный алгоритм можно переписать в кооперативном стиле, когда код каждого потока будет делать явные yield'ы, чтобы передать управление другому потоку. Или выполнять код в виртуальной машине, считая операции (так, например, в Erlang'е работают их сверхлёгкие процессы).

        А когда у нас появляется многопоточность — наши подходы никак не меняются и в основном мы просто создаём столько потоков, сколько у нас логических ядер, и в них выполняем функции, которые берём с какой-нибудь очереди задач. В которую кладём обработчики разных событий, которые возникают от асинхронного I/O.

        (а синхронный I/O вряд ли уже кто использует, но его можно реализовать и без параллельного выполнения, достаточно в цикле проверять, есть ли данные, не блокируя, и передавать выполнение другому потоку, если данных нет)
          0

          Но, вообще говоря, параллелизм — это один из способов достижения конкурентности.

            0
            Не способ. При параллелизме нет конкурентности. Параллелизмом лишь можно ускорить конкурентность. Да и что значит «достижение»? Например, если шедулер решил все треды выполнять на каком-то одном ядре из 8, конкурентность никуда не пропадёт.
              0

              Поведение планировщика — это деталь реализации.

                0
                Так о том и речь. Распараллеливает шедулер, если он этого делать не будет, конкурентность не исчезнет. А если реализовать конкурентность через параллелизм, то как только все ядра получат по треду, работа выполняться будет, но пользоваться системой будет нельзя. Потому заголовок статьи бессмысленный.
                  0

                  Как это — не исчезнет? Если написать намеренно плохой алгоритм планирования потоков, то конкурентность именно что исчезнет.

                    0
                    А почему исчезнет? Можно с другой стороны подойти. Если параллелизм это один из способов, то вот задача: как выполнить конкурентно 20 потоков на 2 ядрах, используя этот способ?
                      0

                      Какая разница, сколько ядер? Наблюдаемое поведение от их количества не зависит.


                      Если есть ОС с вытесняющей многозадачностью и адекватным планировщиком, то с точки зрения программы все ее потоки выполняются параллельно.


                      Особенный только случай 1 ядра. Но даже там применяются те же самые примитивы синхронизации.

          0
          Неплохо еще поднять тему lock-free коллекций ( использование, общая методология написания,… )
            +4
            На мой взгляд, lock-free структуры данных довольно неплохо описаны в статьях khizmax
            –1

            @Rulexec Вы забыли при event bus упомянуть.

              –18
              Корейцы еще 10 лет назад переплюнули ваши представления о высоконагруженной многопоточности.
              Посмотрите на их архитектуры MMORPG серверов. Только в свободном доступе эти исходники не увидеть. Можно только реверс-инженерить.
              Так вот ваши асинки, корутины-шмарутины — это детский лепет, на фоне действительно мощных и работающих механизмов.

              Такое ощущение, что все придумыватели многопоточных механизмов сами вообще не создавали высоконагруженных серверов, а только как теоретики что-то там выдумывают, и издают об этом книги.
                +7
                Ну, если Вы эти механизмы изучили, так поделитесь знаниями с общественностью.
                Думаю, это будет очень полезно и интересно многим читателям хабра.
                Заранее спасибо!
                  –22
                  К сожалению, «поделиться» в сфере IT у русских на последнем месте. Я не исключение. Ведь из затраченного времени хочется извлечь прибыль, а в России не выжить без прибыли, это не Норвегия.

                  В идеале бы создать ITлантиду.
                  ITлантида — место куда сложно попасть, но если попал, не надо париться о прибыли, люди снабжаются сверхнеобходимого, все работают ради творчества и прогресса, делятся своими наработками с остальным миром, негров правда завозят по пропускам, должен же кто-то чинить унитазы.
                    +7
                    Не видел ни одного крутого специалиста, который бы считал невыгодным делиться опытом.
                    NDA — другое дело, но если вы говорите о реверс-инжиниринге, NDA вряд ли применяется.
                      –16
                      Вы и не могли видеть. Крутые специалисты тусят только со своими крутыми специалистами строго в пределах своей компании. А вот джуниоры охотно делятся опытом :))
                        0
                        Хорошо что вы не знаете в какой компании я тусуюсь)
                      +8
                      Есть идея.
                      Вы не пишите каменты, а мы их, соответственно — не читаем. Для всех профит, и никто не потратил время бесплатно.
                        –12
                        Есть идея. Вы не выходите в интернет, и не насилуете свой нежный мозг сложной для вашей психики информацией?
                        0
                        К сожалению, «поделиться» в сфере IT у русских на последнем месте. Я не исключение. Ведь из затраченного времени хочется извлечь прибыль, а в России не выжить без прибыли, это не Норвегия

                        Только у посредственностей, которым тяжело дается изучение чего бы то ни было. Для остальных уже изученное — пройденный этап, они уже впереди, ведь они прошли это, поэтому могут делиться.
                          0
                          Лично по мне, пока ты не объяснил какую-либо технологию кому-нибудь ещё — ты её сам не понимаешь.

                          Я вот пока не написал эту статью, очень смутно представлял, как работают lock-free алгоритмы, хотя сам порой использовал какую-нибудь джавовую ConcurrentLinkedQueue.

                          А сейчас догнал, что они действительно lock-free, но не прям совсем так, чтобы не было блокировок — просто они не используются для блоков кода в принципе, алгоритм используя только атомарные переменные в цикле пытается применить некую операцию до тех пор, пока у него не получится (для добавления в очередь, например, это может быть просто CAS хвоста в цикле, если успеем заменить его до того, как успел кто-то другой — то и славно).

                          Ну а wait-free — это характеристика lock-free алгоритма, при которой есть гарантии, что, например, для нашего примера очереди, мы не будем крутиться в цикле вечно (т.е. если все подряд кроме нас будут успевать поменять хвост, а нам постоянно будет не везти) — т.е. гарантии того, что есть какое-то конечное время (возможно зависящее от размера структуры данных/количества одновременных её пользователей), за которое мы успешно совершим некую операцию.
                        0
                        Ничего там особо умного нет, корутины, запиленные на Си-чётамувас.
                        +13
                        Классный пост:
                        • Посмотрите на архитектуры, которые закрыты;
                        • Асинки и корутины-шмарутины говно, ведь у Корее есть принципиальное новые средства синхронизации (на самом деле не новые, ведь они уже 10 лет назад все придумали);
                        • Мировой computer science говно, то ли дело Корея!
                        • Ну и, конечно, только в Корее есть MMORPG, которые справляются с большими нагрузками :)


                        В общем, кончай ты играть в Линейку и иди делать уроки, мамка придет и наругает!
                        +3
                        какие средства можно использовать для эффективного использования вычислительных ресурсов систем

                        + векторизация (SIMD)
                          0
                          Не упоминал про неё, ибо подумал, что она совсем уж микропараллельна, спасибо.

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

                          Можете подробнее разъяснить нарушение данных, если вести запись в невыровненный адрес.
                            0

                            Поток А: записать по адресу 01 значение АА
                            Поток В: записать по адресу 01 значение ВВ
                            Возможна такая ситуация: (атомарна запись 2 значений)
                            А: записывает А по адресу 01 (00: ХАХХ)
                            переключаем на поток В
                            В: делает полную запись (00: ХВВХ)
                            А: записывает вторую половину значения (00: ХВАХ)
                            Получается по адресу 01 значение ВА

                            +1

                            Вот в этом заголовке есть ошибка: "Promises/A+ — мгновенно стартующие монады с PubSub'ом".


                            Во-первых, не любая поддержка событий является PubSub'ом. Конкретно тот механизм, который предусмотрен в Promises/A+ — точно не PubSub. PubSub подразумевает подписку на сообщения на основе данных или метаданных — но никак не прямое указание источника событий для обработки.


                            Во-вторых, почему все прошлые заголовки относились к надъязыковым понятиям — а тут вдруг используется нечто javascript-специфичное? В том же C# есть аналог этих самых обещаний.


                            В-третьих, почему вдруг обещания будут рассматриваться после async/await — в то время как async/await на обещаниях и построены?

                              0
                              1. Да, некорректно, просто не нашёл другого короткого понятия. Тут я имею в виду, что в случае с данной реализацией промисов всё сделано так, что можно сразу нескольким обработчикам дожидаться результата промиса. И метод .then там это примерно «если промис ещё резолвится, сделай addThenListener(callback), а если зарезолвен, то сделай callback(data)». Да, совсем не PubSub, чистые события.
                              2. Промисы реализует кто как хочет, они действительно везде есть, но я хочу показать один из примеров, как их реализовывать не стоит (хотя некоторые плюсы всё же есть, о них тоже расскажу).
                              3. Я расскажу о том, как работают обещания перед тем, как будет про async/await, всё будет ок.


                              Удалил вообще из содержания пункт про Promises/A+.
                              +1
                              сохранение идентификатора потока, кто захватил блокировку, чтобы никто кроме захватившего потока, не мог сделать Unlock, и если мы сделали Lock второй раз — он не зациклился, такая реализация это называется «мьютексом». А если вместо boolean'а у нас беззнаковое число, а Lock ждёт числа больше нуля, уменьшая его на единицу, получается «семафор», позволяющий работать некоторому заданному числу блоков одновременно, но не более.

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

                                Нет, тут говорилось о рекурсивных мьютексах. То есть о таких мьютексах, которые один и тот же поток может захватить несколько раз не устраивая сам себе взаимоблокировку.

                                0
                                В асинхронности ещё можно поговорить о ново-(старо-)модном Functional Reactive Programming. Более требовательный к дизайну, зато на разработке не будет боли с callback hell.

                                P.S. Таки конкурентность != парелеллизм. Это всё таки о целях, а не о реализации.
                                  0

                                  Какое отношение FRP имеет к асинхронности?

                                    –1
                                    Такое же как и остальное перечисленное — это ещё один паттерн. В отличие от параллельного программирования, асинхронное требует всего один механизм на уровне системных вызовов — select, poll, epoll или ещё что. Все перечисленные неявно его используют, разница только на верхнем уровне.
                                    Отвечая на сам вопрос: FRP — это stateless способ выбрать ответ на пришедший запрос в реальном времени.
                                      0

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


                                      А вот про stateless способ выбрать ответ на входящий запрос я почему-то слышу впервые… Не могли бы вы пояснить эту мысль?

                                        0
                                        «Нет» — слишком категорично, я написал определение «для чего», а вы — «как», оба могут быть верными.
                                        Не могли бы вы пояснить эту мысль?

                                        В чистом (в смысле функционального программирования) FRP состояние передаётся в качестве ещё одного аргумента вместе с нашим горизонтальным временем. На выходе соответственно получаем ответ и изменённый state. Профит в том, что прошлое не задерживается в графе, что сильно упрощает последующую отладку.
                                        А где-то в глубине — обычный event-loop, дёргающий FRP граф, когда срабатывает poll. Я бы это не называл «способ организации кода», всё-таки это про проектирование, а не про написание кода.
                                          0

                                          Если речь идет об "измененном state" — это по определению не stateless подход, пусть даже код 100500 раз чистый, функциональный и простой в отладке.

                                Only users with full accounts can post comments. Log in, please.