Демонстрация сбоев программы при отсутствии барьеров памяти

    Джефф Прешинг (Jeff Preshing) опубликовал отличную демонстрацию, как нормальный код C++ возвращает непредсказуемый результат на многоядерных процессорах со слабо упорядоченной обработкой очереди запросов (Weakly-Ordered CPU), то есть на ARM-процессорах. Например, на iPhone или каком-нибудь современном Android-устройстве.

    Простая программа C++ с двумя потоками 20.000.000 раз прибавляет единичку к значению, защищённому мьютексом, — и каждый раз на выходе получается разный результат, который меньше 20.000.000!



    Как говорится, наш враг — CPU.

    В своём блоге Джефф Прешинг опубликовал много статей о lock-free программировании, методах неблокирующей синхронизации потоков. В том числе он много говорил об использовании блокировки с двойной проверкой и необходимости ставить барьеры памяти. Сейчас Джефф решил, что одна демонстрация лучше тысячи слов.

    Код демонстрационной программы, в которой каждый из двух потоков по 10.000.000 раз прибавляет единичку к общему значению sharedValue, защищённому мьютексом.

    Вот как выглядит самодельный мьютекс: простейший семафор, который принимает значение 1, если он занят, или 0, если свободен.

    int expected = 0;
    if (flag.compare_exchange_strong(expected, 1, memory_order_acquire))
    {
        // The lock succeeded
    }

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

    flag.store(0, memory_order_release);

    В своей программе Джефф умышленно убрал аргументы memory_order_acquire и memory_order_release для демонстрации, к чему это может привести:

    void IncrementSharedValue10000000Times(RandomDelay& randomDelay)
    {
        int count = 0;
        while (count < 10000000)
        {
            randomDelay.doBusyWork();
            int expected = 0;
            if (flag.compare_exchange_strong(expected, 1, memory_order_relaxed))
            {
                // Lock was successful
                sharedValue++;
                flag.store(0, memory_order_relaxed);
                count++;
            }
        }
    }

    Вот что генерирует XCode.



    Результат запуска программы на iPhone уже показывался.



    Из-за чего такое происходит? Дело в том, что процессоры со слабо-упорядоченной обработкой (Weakly-Ordered CPU) могут оптимизировать очередь запросов, так что ваши инструкции будут выполнять не в том порядке, в котором вы думали. Например, на диаграмме показано, как два потока из вышеприведённого примера на разных CPU используют общий мьютекс для изменения значения sharedValue.



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

    Почему CPU осуществляет переупорядочивание очереди запросов, это тема отдельной статьи. Бороться с этим нужно установкой барьеров памяти, которые разделяют пару соседних инструкций и гарантируют, что они не поменяются местами. Вот для чего нужны аргументы memory_order_acquire и memory_order_release. Возвращаем их на место.

    void IncrementSharedValue10000000Times(RandomDelay& randomDelay)
    {
        int count = 0;
        while (count < 10000000)
        {
            randomDelay.doBusyWork();
            int expected = 0;
            if (flag.compare_exchange_strong(expected, 1, memory_order_acquire))
            {
                // Lock was successful
                sharedValue++;
                flag.store(0, memory_order_release);
                count++;
            }
        }
    }

    Компилятор в этом случае вставляет инструкции dmb ish, которые работают как барьеры памяти в ARMv7.



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



    Сейчас мы столкнулись с массовым использованием Weakly-Ordered процессоров. Раньше они использовались только в серверах или в высокопроизводительных «маках» прошлого, где были многоядерные PowerPC. Сейчас многоядерные ARM — в каждом мобильном телефоне. Так что этот нюанс нужно учитывать при разработке мобильных приложений.

    В «специально глючном» коде Прешинга вероятность ошибки составляет 1 к 1000, а в обычной программе она будет 1 к 1.000.000, то есть такие глюки чрезвычайно трудно выловить на тестировании. Программа может работать идеально 999.999 раз, а при следующем запуске произойдёт сбой.
    Support the author
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 39

      +1
      std::atomic разве не решил бы проблему?
        +16
        Сам себе отвечу: решил бы. Автор оригинального кода об этом знает, но специально использует memory_order_relaxed, чтобы показать, как оно может глючить.
          –3
          Решил бы, конечно. Если он существует. Применительно к данному случаю, Objective C — надстройка над С.
            +1
            А что тут от Objective C?
              0
              Кстати, процессор, на котором исполняется код. В теории, Objective-C должен обладать той же проблемой, если Apple не принял каких-то дополнительных усилий.
              Но в любом случае, инструментарий довольно широк:
              @synchronized
              GCD
              pthread_*_lock.
              Будет время — оттестирую.

              Пс. ой, какую археологию я устроил :D
            +1
            В коде он и используется
            • UFO just landed and posted this here
                0
                У Apple актуален clang, gcc уже не актуален.
                0
                Дык std::atomic и используется.

                Вот семейка методов
                en.cppreference.com/w/cpp/atomic/atomic/compare_exchange
                вот возможные параметры-энумы
                en.cppreference.com/w/cpp/atomic/memory_order
                +4
                «Сейчас мы впервые столкнулись с массовым использованием многоядерных ARM-процессоров. Раньше они были только в серверах или в высокопроизводительных «маках» прошлого на PowerPC.»

                Вы ничего не перепутали? ARM и PowerPC — совершенно разные архитектуры.
                  0
                  Да, просто неточно выразился, исправил, tnx.
                    +3
                    Ну и, кстати, процессоры Intel поддерживают и активно используют out-of-order execution начиная с первых Pentium Pro. И барьеры памяти там точно так же применяются. Даже в GCC есть instrinic'и типа __sync_synchronize(). Вот цитата:

                    «Throughout the 1990s out-of-order execution became more common, and was featured in the IBM/Motorola PowerPC 601 (1993), Fujitsu/HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) and DEC Alpha 21264 (1998). Notable exceptions to this trend include the Sun UltraSPARC, HP/Intel Itanium, Transmeta Crusoe, Intel Atom, and the IBM POWER6.»

                    en.wikipedia.org/wiki/Out-of-order_execution
                      +3
                      В x86 реализован total store ordering, поэтому проблемы там совсем не так ярко выражены как на других платформах.

                      А out-of-order execution не совсем к месту. Процессор может быть OOO, но с различными store buffer, которые всё поставит в «правильном» порядке с точки зрения программиста.
                    +2
                    > Вы ничего не перепутали? ARM и PowerPC — совершенно разные архитектуры.
                    В контексте данной статьи автор мог смело писать их в одном предложении: модели памяти этих архитектур близнецы-братья.
                      0
                      ARM — родоначальник PowerPC
                      +11
                      Статья полезна как просветительская для тех, кто хочет разобраться в сути вещей, но прикладным программистам я бы рекомендовал просто использовать системные средства синхронизации или хорошо зарекомендовавшие себя библиотеки, написанные знающими тонкости людьми. Нужно заметить, что описанные проблемы возникают при использовании своих, безграмотно написанных реализаций mutex. Системные реализации mutex содержат в своем коде инструкции memory barriers (или другие средства синхронизации). Прикладной программист с высокой вероятностью все равно запутается во всем многообразии различных средств синхронизации на разных процессорах. Кроме out-of-order load/store на ARM есть куча других заморочек на других процессорах: протоколы кэшей, не гарантирующие консистентность, необходимость сбрасывать очередь инструкций, всякая aсquire/release логика на Itanium, и прочая низкоуровневая фигня, которую целиком прикладной программист не охватит если захочет писать программы на C/C++ под широкий спектр архитектур.
                      • UFO just landed and posted this here
                          +1
                          В C++ этот тоже есть.
                          • UFO just landed and posted this here
                              +4
                              К сожалению, я не могу так просто кинуть ссылку на вики. Такой ссылки нет. Но Вы можете посмотреть C++ standard 1.7 и 1.10. Можете посмотреть мою статейку. Там частично этот вопрос затронут. Хотя и не раскрыт полностью.
                              • UFO just landed and posted this here
                            0
                            Да, это очень хорошая спецификация. Отдельно упомяну страницу The JSR-133 Cookbook for Compiler Writers на которой Doug Lea (кстати автор знаменитого аллокатора памяти) систематизировал данные по распространенным архитектурам CPU в плане поддержки на них memory barriers и out-of-order load/store.
                              0
                              И что? Там запрещеены только store-store перестановки. На остальном можно спокойно огребать. Здесь как раз огребли на load-store или strore-load перестановке. В джаве нет припятствий к этому.
                              • UFO just landed and posted this here
                                  0
                                  1) Во первых тут написано не не любой field, а только volatile!
                                  2) Во вторых тут написано про same volatile, а не про перестановку чтения и записи разных полей.

                                  На хабре была хорошая статья про все эти штучки в джаве, почтитайте.
                                  Или у меня можете взглянуть, но там про .NET. В .NETе модель чуть построже.
                              0
                              Это std::mutex, — это еще ничего. Блокирующий объект синхронизации.
                              А если чуваки решили неблокирующие lock-free алгоритмы сделать на атомарных операциях?
                              Берут
                              en.cppreference.com/w/cpp/atomic/atomic/compare_exchange
                              нихрена это en.cppreference.com/w/cpp/atomic/memory_order не прочитали, да еще спецом изменили этот параметр и начинаются фокусы.

                              В стандартную библиотеку эти аргументы добавили видать для большей гибкости.
                              Если order аргумент в bool compare_exchange_strong( T& expected, T desired, std::memory_order order = td::memory_order_seq_cst ); не трогать, то по умолчанию будет memory_order_seq_cst.

                              Нехрен трогать этот параметр, если неискушен и не знаешь к чему это приведет.
                              +9
                              Автор молодец, создал проблему на пустом месте и теперь всем расказывает, что она есть.
                              1. Если не понимаешь зачем нужны и как пользоваться memory_order_acquire и иже с ними — не используй. По умолчанию все atomic операции в C++11 используют последовательную согласованность. Что даёт гарантию выполнения кода так, как он написан.
                              2. Код автора не верен.
                              if (flag.compare_exchange_strong(expected, 1, memory_order_acquire)) { // The lock succeeded }
                              compare_exchange_strong — read-write операция. Почему он использует только acquire? Допустим мы имеем два потока, один сделал exchange(сиречь release), другой читает(acquire). Но тип операции указан как acquire, а значит этот release не будет синзронизирован с acquire. Поэтому код должен выглядеть как:
                              if (flag.compare_exchange_strong(expected, 1, memory_order_acq_rel)) { // The lock succeeded }
                              3. В большинстве случаев надо использовать std::mutex и собратьев дабы не иметь никакой головной боли.
                                +1
                                По пункту 2 не совсем так. Тут не идет речь ни о какой синхронизации. memory_order_acquire просто гарантирует, что все инструкции, стоящии после барьера не будут переупорчдоченты так, что окажутся до барьера.

                                В данном случае это гарантирует, что никто не прочтет переменные до получения мьютекса — этого достаоточно для корректной работы.

                                memory_order_acquire гарантирует противоположную вещь — что инструкции стоящии до барьера не запрыгнут после барьера. Здесь это абсолютно пофиг.
                                  0
                                  memory_order_acquire, как и memory_order_release по одиночке ничего не гарантируют, только в паре. Хотя тут, по всей видимости, Вы правы; в данном конкретном случае нужна только синхронизация между последним store и read частью exchange.
                                    0
                                    Так там и есть пара. Вот второй: flag.store(0, memory_order_release);
                                      0
                                      Ну да, это я и имел ввиду во втором предложении.
                                0
                                Была подобная статья: habrahabr.ru/post/63697/
                                • UFO just landed and posted this here
                                    0
                                    В принципе, проверить можно. Только это очень дорого: на одну строчку кода придётся написать примерно строчек 30 спецификации и доказательств. Есть seL4, для которой эта титаническая работы была проделана. Но, в принципе, да, Вы правы. Синхронизация — это дополнительные алгоритмы и их реализации в системе, где могут возникнуть ошибки. Чем меньше таких мест, тем лучше. Но иногда просто не хватает энергоэффективности, и, всё равно, приходится использовать многоядерные решения.
                                      0
                                      Ох, помню, в университете было задание для одной функции строк в 30-40 из кода ядра какой-то *nix системы написать верифицирующую модель на Promela.
                                      0
                                      Как я понимаю, проверить любой код на отсутствие таких лаж невозможно.
                                      Это технически возможно, просто до поры до времени это не очень волновало даже самих производителей процессоров, но последние несколько лет ситация поменялась. Сейчас есть исследовательская группа в Кембридже (и сочувствующие в INRIA и прочих учреждениях), которая формализировала модели памяти SPARC, x86 и Power (раз и два). Есть люди, интересующиеся формальной верификацией поверх слабых моделей памяти (например, C++).
                                      0
                                      Почему-то глядя на эту тему, подумалось, что идет борьба разработчиков процессоров с программистами.
                                      Мне вот просто интересно, если в процессоре изначально обойтись без этих оптимизаций с перестановками инструкций, то потом в программах можно будет обойтись без барьеров памяти, то есть мьютексы будут более просты и менее затратны.
                                      Может это приведет к бОльшей производительности?
                                        +2
                                        Если в процессоре обойтись без «этих оптимизаций» то вы получите Intel386 с соответствующей производительностью.
                                          +1
                                          Для случаев, когда мьютекс слишком затратен, существуют spinlock'и и, как минимум, атомарные операции.
                                          Но без барьеров памяти всё равно не обойтись :)

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