C ++ 11 представил стандартизированную модель памяти. Что это значит? И как это повлияет на программирование на C ++?

C ++ 11 представил стандартизированную модель памяти, но что именно это означает? И как это повлияет на программирование на C ++?

В этой статье ( Гэвин Кларк, которая цитирует Херба Саттера ) говорится, что

Модель памяти означает, что код C ++ теперь имеет стандартизированную библиотеку для вызова независимо от того, кто создал компилятор и на какой платформе он работает. Существует стандартный способ управления тем, как разные потоки взаимодействуют с памятью процессора.

«Когда вы говорите о разделении [кода] по различным ядрам, которые есть в стандарте, мы говорим о модели памяти. Мы собираемся оптимизировать ее, не нарушая следующие предположения, которые люди собираются сделать в коде», - сказал Саттер .

Что ж, я могу запомнить этот и подобные параграфы, доступные онлайн (так как у меня была своя собственная модель памяти с рождения: P), и даже могу публиковать ответы на вопросы, заданные другими, но, честно говоря, я не совсем понимаю это.

Программисты C ++ раньше разрабатывали многопоточные приложения, поэтому какое это имеет значение, если это потоки POSIX, потоки Windows или потоки C ++ 11? Каковы преимущества? Я хочу понять детали низкого уровня.

У меня также возникает ощущение, что модель памяти C ++ 11 как-то связана с поддержкой многопоточности C ++ 11, так как я часто вижу эти две вещи вместе. Если это так, как именно? Почему они должны быть связаны?

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

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

Спецификация C ++ не содержит ссылки на какой-либо конкретный компилятор, операционную систему или процессор. Он ссылается на абстрактную машину, которая является обобщением реальных систем. В мире Language Lawyer работа программиста заключается в написании кода для абстрактной машины; Задача компилятора - реализовать этот код на конкретной машине. Жестко программируя спецификацию, вы можете быть уверены, что ваш код будет компилироваться и выполняться без изменений в любой системе с совместимым компилятором C ++, будь то сегодня или через 50 лет.

Абстрактная машина в спецификации C ++ 98 / C ++ 03 принципиально однопоточная. Поэтому невозможно написать многопоточный код C ++, который является «полностью переносимым» по отношению к спецификации. Спецификация даже не говорит ничего об атомарности загрузки и хранения памяти или о порядке, в котором могут происходить загрузки и хранения, не говоря уже о мьютексах.

Конечно, вы можете написать многопоточный код на практике для конкретных конкретных систем, таких как pthreads или Windows. Но не существует стандартного способа написания многопоточного кода для C ++ 98 / C ++ 03.

Абстрактная машина в C ++ 11 является многопоточной по своему дизайну. Он также имеет четко определенную модель памяти ; то есть он говорит, что компилятор может и не может делать, когда дело доходит до доступа к памяти.

Рассмотрим следующий пример, где пара глобальных переменных доступна одновременно двум потокам:

           Global
           int x, y;

Thread 1            Thread 2
x = 17;             cout << y << " ";
y = 37;             cout << x << endl;

Что может выводить тема 2?

В C ++ 98 / C ++ 03 это даже не неопределенное поведение; сам вопрос не имеет смысла, потому что стандарт не предусматривает ничего, что называется «нитью».

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

Но с C ++ 11 вы можете написать это:

           Global
           atomic<int> x, y;

Thread 1                 Thread 2
x.store(17);             cout << y.load() << " ";
y.store(37);             cout << x.load() << endl;

Теперь все становится намного интереснее. Прежде всего, поведение здесь определено . Теперь поток 2 может печатать 0 0(если он выполняется до потока 1), 37 17(если он выполняется после потока 1) или 0 17(если он выполняется после того, как поток 1 назначает x, но до того, как он назначает y).

Он не может печатать 37 0, потому что режим по умолчанию для атомарных загрузок / хранилищ в C ++ 11 состоит в обеспечении последовательной согласованности . Это просто означает, что все загрузки и хранилища должны быть «такими, как если бы» происходили в том порядке, в котором вы их записали в каждом потоке, а операции между потоками могут чередоваться, как нравится системе. Таким образом, стандартное поведение атома обеспечивает атомарность и порядок загрузки и хранения.

Теперь на современном процессоре обеспечение последовательной согласованности может быть дорогостоящим. В частности, компилятор, вероятно, будет создавать полноценные барьеры памяти между каждым доступом здесь. Но если ваш алгоритм может терпеть неупорядоченные загрузки и хранения; т.е. если это требует атомарности, но не упорядоченности; то есть, если он может терпеть 37 0как вывод этой программы, то вы можете написать это:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_relaxed);   cout << y.load(memory_order_relaxed) << " ";
y.store(37,memory_order_relaxed);   cout << x.load(memory_order_relaxed) << endl;

Чем современнее процессор, тем больше вероятность, что он будет быстрее, чем в предыдущем примере.

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

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_release);   cout << y.load(memory_order_acquire) << " ";
y.store(37,memory_order_release);   cout << x.load(memory_order_acquire) << endl;

Это возвращает нас к заказанным нагрузкам и хранилищам - так что 37 0это уже невозможно - но это происходит с минимальными издержками. (В этом тривиальном примере результат такой же, как у последовательной последовательной последовательности; в более крупной программе это не так).

Конечно, если вы хотите видеть только выходные данные 0 0или 37 17, вы можете просто обернуть мьютекс вокруг исходного кода. Но если вы прочитали это далеко, держу пари, вы уже знаете, как это работает, и этот ответ уже дольше, чем я предполагал :-).

Итак, суть. Мьютексы великолепны, и C ++ 11 их стандартизирует. Но иногда по соображениям производительности вам нужны низкоуровневые примитивы (например, классический шаблон блокировки с двойной проверкой ). Новый стандарт предоставляет высокоуровневые гаджеты, такие как мьютексы и условные переменные, а также низкоуровневые гаджеты, такие как атомарные типы и различные варианты барьера памяти. Так что теперь вы можете писать сложные, высокопроизводительные параллельные подпрограммы полностью на языке, указанном в стандарте, и вы можете быть уверены, что ваш код будет компилироваться и выполняться без изменений как в сегодняшних, так и в завтрашних системах.

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

Подробнее об этом см. В этом блоге .

Я просто приведу аналогию, с которой я понимаю модели согласованности памяти (или модели памяти, для краткости). Он основан на оригинальной работе Лесли Лэмпорта «Время, часы и порядок событий в распределенной системе» . Аналогия уместна и имеет фундаментальное значение, но может быть излишней для многих людей. Тем не менее, я надеюсь, что это обеспечивает мысленный образ (графическое представление), который облегчает рассуждения о моделях согласованности памяти.

Давайте рассмотрим историю всех областей памяти на диаграмме пространства-времени, в которой горизонтальная ось представляет адресное пространство (т. Е. Каждая область памяти представлена ​​точкой на этой оси), а вертикальная ось представляет время (мы увидим, что в общем нет универсального понятия времени). Поэтому история значений, хранящихся в каждой ячейке памяти, представляется вертикальным столбцом по этому адресу памяти. Каждое изменение значения происходит из-за того, что один из потоков записывает новое значение в это место. По образу памяти , мы будем понимать совокупность / сочетание значений всех ячеек памяти , наблюдаемых в конкретный момент времени по определенной теме .

Цитата из «Учебник по согласованности памяти и согласованности кэша»

Интуитивная (и наиболее ограниченная) модель памяти - это последовательная согласованность (SC), в которой многопоточное выполнение должно выглядеть как чередование последовательных выполнений каждого составляющего потока, как если бы потоки были мультиплексированы по времени на одноядерном процессоре.

Этот глобальный порядок памяти может варьироваться от одного запуска программы к другому и может быть неизвестен заранее. Характерной особенностью SC является набор горизонтальных срезов на диаграмме адрес-пространство-время, представляющих плоскости одновременности (то есть изображения памяти). В данной плоскости все его события (или значения памяти) являются одновременными. Существует понятие абсолютного времени , в котором все потоки соглашаются, какие значения памяти являются одновременными. В SC в каждый момент времени существует только один образ памяти, общий для всех потоков. То есть в каждый момент времени все процессоры согласовывают образ памяти (т. Е. Совокупное содержимое памяти). Это означает не только то, что все потоки просматривают одинаковую последовательность значений для всех областей памяти, но и то, что все процессоры наблюдают одинаковуюкомбинации значений всех переменных. Это то же самое, что сказать, что все операции с памятью (во всех ячейках памяти) наблюдаются в одном и том же общем порядке всеми потоками.

В моделях с расслабленной памятью каждый поток будет разделять адресное пространство-время по-своему, единственное ограничение состоит в том, что срезы каждого потока не должны пересекаться друг с другом, поскольку все потоки должны согласовывать историю каждого отдельного расположения памяти (конечно, кусочки разных нитей могут пересекаться друг с другом). Не существует универсального способа его разрезать (нет привилегированного расслоения адрес-пространство-время). Ломтики не должны быть плоскими (или линейными). Они могут быть изогнуты, и это может заставить поток читать значения, записанные другим потоком, в том порядке, в котором они были записаны. Истории различных областей памяти могут произвольно скользить (или растягиваться) относительно друг друга при просмотре любым конкретным потоком., Каждый поток будет по-разному понимать, какие события (или, что то же самое, значения памяти) являются одновременными. Набор событий (или значений памяти), которые являются одновременными для одного потока, не являются одновременными для другого. Таким образом, в модели с расслабленной памятью все потоки все еще наблюдают одну и ту же историю (то есть последовательность значений) для каждой ячейки памяти. Но они могут наблюдать разные образы памяти (т. Е. Комбинации значений всех областей памяти). Даже если две разные ячейки памяти записаны одним и тем же потоком последовательно, два вновь записанных значения могут наблюдаться в другом порядке другими потоками.

[Изображение из Википедии]

Читатели, знакомые со Специальной теорией относительности Эйнштейна , заметят то, на что я намекаю. Перевод слов Минковского в царство моделей памяти: адресное пространство и время являются тенями адресного пространства-времени. В этом случае каждый наблюдатель (т. Е. Поток) будет проецировать тени событий (т. Е. Память хранит / загружает) на свою собственную мировую линию (т. Е. Свою временную ось) и свою собственную плоскость одновременности (свою ось адресного пространства) , Потоки в модели памяти C ++ 11 соответствуют наблюдателям , которые движутся относительно друг друга в специальной теории относительности. Последовательная согласованность соответствует галилеевому пространству-времени (т. Е. Все наблюдатели соглашаются в одном абсолютном порядке событий и общем смысле одновременности).

Сходство между моделями памяти и специальной теорией относительности обусловлено тем фактом, что оба определяют частично упорядоченный набор событий, часто называемый причинным набором. Некоторые события (например, хранилища памяти) могут влиять (но не подвергаться влиянию) других событий. Поток C ++ 11 (или наблюдатель в физике) - это не более чем цепочка (т. Е. Полностью упорядоченный набор) событий (например, память загружается и сохраняется по возможно различным адресам).

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

В модели памяти C ++ 11 аналогичный механизм (модель согласованности получения-выпуска) используется для установления этих локальных причинно-следственных связей .

Чтобы дать определение согласованности памяти и мотивацию для отказа от SC, я процитирую из «Учебник по согласованности памяти и согласованности кэша»

Для машины с общей памятью модель согласованности памяти определяет архитектурно видимое поведение ее системы памяти. Критерий корректности поведения разделений ядра одного процессора между « одним правильным результатом » и « многими неправильными альтернативами ». Это связано с тем, что архитектура процессора требует, чтобы выполнение потока преобразовывало заданное входное состояние в единое четко определенное выходное состояние, даже на ядре не в порядке. Однако модели согласованности совместно используемой памяти относятся к нагрузкам и хранилищам нескольких потоков и обычно допускают много правильных выполнений.не допуская много (больше) неправильных. Возможность многократного правильного выполнения обусловлена ​​тем, что ISA позволяет одновременно выполнять несколько потоков, часто с множеством возможных законных чередований инструкций из разных потоков.

Расслабленные или слабые модели согласованности памяти мотивируются тем фактом, что большинство упорядочений памяти в сильных моделях не нужны. Если поток обновляет десять элементов данных, а затем флаг синхронизации, программисты обычно не заботятся о том, обновляются ли элементы данных по порядку относительно друг друга, а только о том, что все элементы данных обновляются до обновления флага (обычно реализуется с использованием инструкций FENCE). ). Расслабленные модели стремятся использовать эту повышенную гибкость заказов и сохранять только те заказы, которые « нужны программистам».», Чтобы получить как более высокую производительность, так и правильность СЦ. Например, в определенных архитектурах буферы записи FIFO используются каждым ядром для хранения результатов подтвержденных (удаленных) хранилищ перед записью результатов в кэши. Эта оптимизация повышает производительность, но нарушает СЦ. Буфер записи скрывает задержку обслуживания пропуска магазина. Поскольку магазины являются обычным делом, возможность избежать остановки на большинстве из них является важным преимуществом. Для одноядерного процессора буфер записи можно сделать архитектурно невидимым, гарантируя, что загрузка по адресу A возвращает значение самого последнего хранилища в A, даже если одно или несколько хранилищ в A находятся в буфере записи. Обычно это делается путем обхода значения самого последнего хранилища для A до загрузки из A, где «самый последний» определяется порядком программы, или путем остановки загрузки A, если хранилище для A находится в буфере записи. Когда используется несколько ядер, у каждого будет свой обходной буфер записи. Без буферов записи аппаратное обеспечение - это SC, но с буферами записи - нет, что делает архитектурно видимые буферы записи в многоядерном процессоре.

Переупорядочение хранилища может произойти, если ядро ​​имеет буфер записи без FIFO, который позволяет хранилищам отправляться в другом порядке, чем порядок, в котором они были введены. Это может произойти, если первое хранилище пропадает в кэше, пока второе попадет, или если второе хранилище может объединиться с более ранним хранилищем (т. Е. До первого хранилища). Изменение порядка загрузки и загрузки также может происходить на ядрах с динамическим планированием, которые выполняют инструкции вне программного порядка. Это может вести себя так же, как и переупорядочение хранилищ на другом ядре (можете ли вы привести пример чередования между двумя потоками?). Переупорядочение более ранней загрузки с более поздним хранилищем (переупорядочение хранилища загрузок) может вызвать много неправильных действий, таких как загрузка значения после снятия блокировки, которая защищает его (если хранилище является операцией разблокировки).

Поскольку согласованность кэша и согласованность памяти иногда путаются, полезно также иметь такую ​​цитату:

В отличие от согласованности, согласованность кэша не видна программному обеспечению и не требуется. Согласованность стремится сделать кэши системы с общей памятью такими же функционально невидимыми, как кэши в одноядерной системе. Правильная согласованность гарантирует, что программист не сможет определить, есть ли у системы кеши и где она анализирует результаты загрузки и сохранения. Это связано с тем, что правильная согласованность гарантирует, что кэши никогда не разрешают новое или другое функциональное поведение (программисты могут по-прежнему иметь возможность определять вероятную структуру кэша с использованием синхронизацииИнформация). Основное назначение протоколов когерентности кэша заключается в поддержании инварианта «единица записи-несколько читателей» (SWMR) для каждой области памяти. Важное различие между согласованностью и согласованностью заключается в том, что согласованность указывается для каждой ячейки памяти , в то время как согласованность указывается для всех областей памяти.

Продолжая нашу ментальную картину, инвариант SWMR соответствует физическому требованию, чтобы в любом одном месте находилась не более одной частицы, но в любом месте может быть неограниченное количество наблюдателей.

_{Теперь это вопрос нескольких лет, но, будучи очень популярным, стоит упомянуть фантастический ресурс для изучения модели памяти C ++ 11. Я не вижу смысла резюмировать его выступление, чтобы сделать этот еще один полный ответ, но, учитывая, что это парень, который действительно написал стандарт, я думаю, что стоит посмотреть выступление.}

Херб Саттер в течение трех часов рассказывает о модели памяти C ++ 11 под названием «Атомное <> оружие», доступной на сайте Channel9 - часть 1 и часть 2 . Доклад довольно технический и охватывает следующие темы:

1. Оптимизации, гонки и модель памяти
2. Заказ - что: приобретать и выпускать
3. Порядок - Как: Мьютексы, Атомика и / или Заборы
4. Другие ограничения на компиляторы и оборудование
5. Код Gen & Performance: x86 / x64, IA64, POWER, ARM
6. Расслабленная атомика

В докладе говорится не об API, а о рассуждениях, предыстории, скрытности и скрытности (знаете ли вы, что к стандарту добавлена ​​расслабленная семантика только потому, что POWER и ARM не поддерживают эффективную синхронизированную загрузку?).

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

Когда вы говорите о потоках POSIX или Windows, то это немного иллюзия, так как на самом деле вы говорите о потоках x86, поскольку это аппаратная функция для одновременного запуска. Модель памяти C ++ 0x дает гарантии, будь то x86, ARM, MIPS или что-то еще, что вы можете придумать.

Для языков, не определяющих модель памяти, вы пишете код для языка и модели памяти, определенных архитектурой процессора. Процессор может выбрать изменение порядка доступа к памяти для повышения производительности. Таким образом, если ваша программа использует гонки данных (гонка данных - это когда несколько ядер / гиперпотоков могут одновременно обращаться к одной и той же памяти), то ваша программа не является кроссплатформенной из-за своей зависимости от модели памяти процессора. Вы можете обратиться к руководствам по программному обеспечению Intel или AMD, чтобы узнать, как процессоры могут изменить порядок доступа к памяти.

Очень важно, что блокировки (и семантика параллелизма с блокировкой) обычно реализуются кросс-платформенным способом ... Так что, если вы используете стандартные блокировки в многопоточной программе без гонок данных, вам не нужно беспокоиться о кроссплатформенных моделях памяти ,

Интересно, что компиляторы Microsoft для C ++ имеют семантику приобретения / выпуска для volatile, которое является расширением C ++ для решения проблемы отсутствия модели памяти в C ++ http://msdn.microsoft.com/en-us/library/12a04hfd(v=vs .80) .aspx . Однако, учитывая, что Windows работает только на x86 / x64, это мало что говорит (модели памяти Intel и AMD позволяют легко и эффективно реализовать семантику получения / выпуска на языке).

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

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

Ранее, атомика была бы сделана с использованием встроенных функций компилятора или некоторой библиотеки более высокого уровня. Заборы были бы сделаны с использованием специфических для процессора инструкций (барьеры памяти).

Приведенные выше ответы касаются самых фундаментальных аспектов модели памяти C ++. На практике большинство применений std::atomic<>«просто работают», по крайней мере, до тех пор, пока программист не выполнит чрезмерную оптимизацию (например, пытаясь ослабить слишком много вещей).

Есть одно место, где ошибки все еще распространены: блокировки последовательности . На https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf проведено отличное и легкое для чтения обсуждение проблем . Блокировки последовательности привлекательны, потому что читатель избегает записи в слово блокировки. Следующий код основан на рисунке 1 приведенного выше технического отчета и освещает проблемы, возникающие при реализации блокировок последовательностей в C ++:

atomic<uint64_t> seq; // seqlock representation
int data1, data2;     // this data will be protected by seq

T reader() {
    int r1, r2;
    unsigned seq0, seq1;
    while (true) {
        seq0 = seq;
        r1 = data1; // INCORRECT! Data Race!
        r2 = data2; // INCORRECT!
        seq1 = seq;

        // if the lock didn't change while I was reading, and
        // the lock wasn't held while I was reading, then my
        // reads should be valid
        if (seq0 == seq1 && !(seq0 & 1))
            break;
    }
    use(r1, r2);
}

void writer(int new_data1, int new_data2) {
    unsigned seq0 = seq;
    while (true) {
        if ((!(seq0 & 1)) && seq.compare_exchange_weak(seq0, seq0 + 1))
            break; // atomically moving the lock from even to odd is an acquire
    }
    data1 = new_data1;
    data2 = new_data2;
    seq = seq0 + 2; // release the lock by increasing its value to even
}

Как не интуитивно понятно, как кажется на первый взгляд, так data1и data2должно быть atomic<>. Если они не являются атомарными, то они могут быть прочитаны (в reader()) в то же время, что и написаны (в writer()). Согласно модели памяти C ++, это гонка, даже если на reader()самом деле никогда не использует данные . Кроме того, если они не являются атомарными, компилятор может кэшировать первое чтение каждого значения в регистре. Очевидно, вы этого не захотите ... вы хотите перечитывать в каждой итерации whileцикла in reader().

Также недостаточно сделать их atomic<>и получить к ним доступ memory_order_relaxed. Причина этого заключается в том, что читает НомерСтарт (в reader()) только ACQuire семантика. Проще говоря, если X и Y являются обращениями к памяти, X предшествует Y, X не является приобретением или выпуском, а Y является приобретением, то компилятор может изменить порядок Y до X. Если Y был вторым чтением seq, и X при чтении данных такое переупорядочение нарушило бы реализацию блокировки.

В статье дается несколько решений. Один с лучшей производительностью сегодня, вероятно , тот , который использует atomic_thread_fenceс memory_order_relaxed до того второго чтения в seqlock. В статье это рисунок 6. Я не воспроизводю код здесь, потому что любой, кто прочитал это далеко, действительно должен прочитать статью. Он более точный и полный, чем этот пост.

Последняя проблема заключается в том, что неестественно делать dataпеременные атомарными. Если вы не можете в своем коде, то вам нужно быть очень осторожным, потому что приведение от неатомарного к атомарному разрешено только для примитивных типов. Предполагается добавить C ++ 20 atomic_ref<>, что облегчит решение этой проблемы.

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

C и C ++ раньше определялись следом выполнения хорошо сформированной программы.

Теперь они наполовину определены трассировкой выполнения программы, а наполовину апостериори - многими упорядочениями объектов синхронизации.

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