Букварь по SMP для Android

Android 3.0 и более поздние версии платформы оптимизированы для поддержки многопроцессорных архитектур. Этот документ вводит вопросы, которые могут возникнуть при написании кода для симметричных многопроцессорных систем в C, C++, и языке программирования Java (далее просто "Java" для краткости). Он предназначен в качестве базы для разработчиков Android приложений, а не как полное обсуждение этого вопроса. Основное внимание уделяется архитектуре процессора ARM.

Если вы спешите, вы можете пропустить раздел Теория и перейти непосредственно к разделу Практика , но это не рекомендуется.

Введение

SMP это аббревиатура для “Symmetric Multi-Processor”(симметричный мультипроцессор). Он описывает конструкцию, в которой два или более одинаковых ядра процессора используют общую основную памяти. Еще несколько лет назад, все Android устройства были однопроцессорные (Uni-Processor ).

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

Большинство продаваемых сегодня Android устройств строятся вокруг SMP конструкций, делая вещи немного более сложными для разработчиков программного обеспечения. Разные виды "race condition" (состояния гонки), которые могут возникнуть в многопоточном приложении гораздо хуже на SMP, когда два или более ваших потока работают одновременно на разных ядрах. Более того, работа SMP на ARM является более сложной, чем SMP на x86. Код, который был тщательно протестирован на x86 может сломаться на ARM.

Остальная часть этого документа будет объяснять почему, и говорить вам, что вы должны сделать, чтобы убедиться, что ваш код ведет себя правильно.

Теория

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

Смотрите Дополнительную литературу в конце документа для ссылок на более тщательное изучение предмета.

Модели согласованности памяти

Модели согласованности памяти, или часто просто "модели памяти", описывают гарантии, которые аппаратная архитектура предоставляет относительно доступа к памяти. Например, если записать значение по адресу А, а затем записать значение по адресу B, модель может гарантировать, что каждое ядро процессора видит эти записи в таком порядке.

Большинство программистов привыкли к модели последовательной консистентности, который описан следующим образом (Adve & Gharachorloo):

  • Все операции с памятью, кажется, выполняются по одной
  • Все операции на одном процессоре, кажется, выполняются в порядке, описанном программой этого процессора.

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

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

Вот простой пример, с кодом, работающим на двух потоках:

Поток 1 Поток 2
A = 3
B = 5
reg0 = B
reg1 = A

В этом и всех последующих лакмусовых примерах, ячейки памяти представлены заглавными буквами (A, B, C), а регистры процессора начинаются с “reg”. Вся память изначально заполнена нулями. Инструкции выполняются сверху вниз. Здесь, поток 1 сохраняет значение 3 по адресу А, а затем значение 5 по адресу B. Поток 2 загружает значение из адреса B в reg0, а затем загружает значение из адреса А в reg1. (Обратите внимание, что мы пишем в одном порядке, а вычитываем в другом.)

Предполагается, что поток 1 и поток 2 выполняются на разных процессорных ядрах. Вы должны всегда делать это предположение, думая о многопоточном коде.

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

Регистры Состояния
reg0=5, reg1=3 возможно (поток 1 выполнился первым)
reg0=0, reg1=0 возможно (поток 2 завершился первым)
reg0=0, reg1=3 возможно (одновременное выполнение)
reg0=5, reg1=0 никогда

Чтобы попасть в ситуацию, где мы видим B=5 прежде чем мы видим сохранение в А, чтение или запись должны произойти не в том порядке. На машине с последовательной консистентностью это произойти не может.

Большинство однопроцессорных систем, в том числе x86 и ARM, имеют последовательную консистентность. Большинство SMP систем, включая x86 и ARM, нет.

Согласованность процессора

x86 SMP обеспечивает процессорную консистенцию, которая немного слабее, чем последовательная. В то время как архитектура гарантирует, что порядок загрузки не меняется по отношению другим загрузкам, и порядок сохранения не меняется по отношению к других сохранениям, но не гарантирует, что сохранение с последующей загрузкой будет наблюдаться в ожидаемом порядке.

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

Поток 1 Поток 2
A = true
reg1 = B
if (reg1 == false)
    critical-stuff
B = true
reg2 = A
if (reg2 == false)
    critical-stuff

Идея состоит в том, что поток 1 использует A для указания, что он занят, а поток 2 использует B. Поток 1 устанавливает А, а затем проверяет, установлен ли B; если нет, то можно смело предположить, что он имеет монопольный доступ к критической секции. Поток 2 делает нечто подобное. (Если поток обнаруживает, что А и B установлены, алгоритм очередности используется для обеспечения равноправия.)

На машине с последовательной консистенцией, это работает правильно. На x86 и ARM SMP, сохранение в A и загрузка из B в потоке 1 может "наблюдаться" в другом порядке потоком 2. Если бы это произошло, мы могли бы фактически выполнить следующую последовательность (пустые строки были вставлены, чтобы подчеркнуть очевидный порядок операций):

Поток 1 Поток 2
reg1 = B


A = true
if (reg1 == false)
    critical-stuff

B = true
reg2 = A

if (reg2 == false)
    critical-stuff

Это приводит к тому, что обе reg1 и reg2 установлены в “false”, что позволяет потокам выполнить код в критической секции одновременно. Чтобы понять, как это может произойти, полезно знать немного о кэше процессора.

Поведение кэша процессора

Это существенная тема сама по себе. Чрезвычайно краткий обзор следующим образом. (Мотивация для этого материала это обеспечение некоторой основы для понимания того, почему SMP системы ведут себя так, как они это делают.)

Современные процессоры имеют один или несколько кэшей между процессором и основной памятью. Они помечены L1, L2, и так далее, причем более высокие числа последовательно «дальше» от процессора. Кэш-память добавляет размер и стоимость к оборудованию, а также увеличивает энергопотребление, так что ARM процессоры, используемые в устройствах Android, как правило, имеют небольшой кэш L1 и маленький или вообще не имеют L2/L3.

Загрузка или сохранение значения в кэш L1 работает очень быстро. Выполнение того же самого в основную память может быть в 10-100 раз медленнее. Таким образом, процессор будет пытаться работать с кэшем как можно больше. Политика записи кэша определяет когда данные, записанные в него, пересылаются в основную память. Кэш со сквозной записью будет немедленно инициировать запись в память, в то время как кэш с обратной записью будет ждать, пока не закончится место, и необходимо будет выселить некоторые записи. В любом случае, процессор продолжит выполнение инструкций мимо той, что выполняла сохранение, возможно выполнение десятка инструкций до того, как запись будет видна в основной памяти. (В то время как кэш со сквозной записью имеет политику мгновенной посылки данных в основную память, он только инициирует запись. Он не должен ждать её завершения.)

Поведение кэша становится релевантным к этому обсуждению, когда каждое ядро ​​процессора имеет свой собственный кэш. В простой модели, кэши не имеют возможности взаимодействовать друг с другом напрямую. Значения, содержащееся в кэше ядра №1 не являются общими или видимыми для кэша ядра №2, за исключением загрузки или сохранения в/из основной памяти. Длинные задержки доступа к памяти сделает межпоточное взаимодействия вялым, так что полезно определить способ для обмена данными между кэшами. Этот обмен называется связность кэша, и правила связности определяются процессорной архитектурой модели консистенции кэша.

Имея это в виду, давайте вернемся к примеру Деккера. Когда ядро ​​1 выполняет “A = 1”, значение сохраняется в кэше ядра 1. Когда ядро ​​2 выполняет “if (A == 0)”, оно может считать из основной памяти или оно может считать от основного кэша ядра 2; в любом случае оно не будет видеть сохранение, выполненное ядром 1. (“A” может быть в кэше ядра 2 в связи с предыдущей загрузкой из “A”.)

Для модели согласованности памяти, чтобы быть последовательно консистентной, ядро ​​1 должно подождать, пока все другие ядра будут в курсе “A = 1”, прежде чем оно сможет выполнить “if (B == 0)” (либо с помощью строгих правил связности кэша, или полностью отключить кэши, чтобы все работало с оперативной памяти). Это будет бить по производительности при каждой операции сохранения. Расслабляющие правила для упорядочения сохранений с последующими нагрузками повышает производительность, но накладывает бремя на разработчиков программного обеспечения.

Другие гарантии, сделанные согласованностью модели процессора являются менее дорогими при выполнении. Например, для того, чтобы не наблюдались записи в память не по порядку, просто необходимо обеспечить, чтобы сохранения публиковались для других ядер в том же порядке, как они были сделаны. Для этого не нужно ждать пока сохранение №1 завершиться и опубликуется прежде чем можно будет начать сохранение №2, просто необходимо обеспечить, чтобы публикация №2 не завершилось раньше завершения публикации №1. Это позволяет избежать "пузыря" производительности.

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

Еще одно замечание: кэши процессора не работают с отдельными байтами. Данные считываются или записываются как строки кэша; для многих процессоров ARM это 32 байта. Если вы читаете данные по адресу из основной памяти, вы также будете считывать некоторые соседние значения. Запись данных приведет к тому, что строки кэша будут прочитаны из памяти и обновлены. В результате, вы можете вызвать загрузку значения в кэш как побочный эффект чтения или записи чего-то рядом, добавив к общей ауре таинственности.

Возможность наблюдения

Прежде чем идти дальше, полезно определить более строгим образом, что подразумевается под "возможностью наблюдения" загрузки или сохранения. Предположим ядро ​​1 выполняет “A = 1”. Сохранение инициируется , когда процессор выполняет инструкцию. В какой-то момент позже, возможно через деятельность связности кэша, сохранение наблюдается ядром 2. В кэше со сквозной записью это в действительности не завершается пока сохранение не поступит в основную память, но модель согласованности памяти не диктует, когда что-то завершится, а просто когда наблюдается.

(В драйвере устройства ядра, который обращается к отображенным в память адресам ввода/вывода, может быть очень важно знать, когда вещи действительно завершились. Мы не собираемся идти в этом направлении здесь.)

Возможность наблюдения может быть определена следующим образом:

  • "Запись по адресу в памяти, как говорят, наблюдается наблюдателем Pn, когда при последующем чтении по этому адресу наблюдателем Pn вернется значение, записанное операцией записи."
  • "Чтение по адресу памяти, как говорят, наблюдается наблюдателем Pm, когда последующая запись по этому адресу наблюдателем Pm не имеет бы никакого влияния на значение возвращенное чтением." (Рассуждения о слабой консистентности модели памяти в ARM)

Менее формальным способом описать это (где "вы" и "Я" являемся ядрами процессора) будет:

  • Я наблюдаю вашу запись, когда я могу считать то, что вы записали
  • Я наблюдаю ваше чтение, когда я больше не могут повлиять на значение, которое вы считываете

Понятие наблюдения записи является интуитивно понятным; наблюдение чтения менее понятно (так что не волнуйтесь).

С этим в уме, мы готовы говорить об ARM.

Слабый порядок в ARM

ARM SMP обеспечивает слабые гарантии согласованности памяти. Он не гарантирует, что загрузки или сохранения упорядочены по отношению друг к другу.

Поток 1 Поток 2
A = 41
B = 1 // “A is ready”
loop_until (B == 1)
reg = A

Напомним, что все адреса изначально содержат нули. Инструкция “loop_until” читает B многократно в цикле, пока мы не прочитали 1 из B. Идея заключается в том, что поток 2 ждет пока поток 1 обновит A. Поток 1 устанавливает А, а затем устанавливает B в 1, чтобы указать доступность данных.

На x86 SMP, это гарантированно работает. Поток 2 будет наблюдать сохранения, сделанные потоком 1 в программном порядке, и поток 1 будет наблюдать загрузки потока 2 в программном порядке.

На ARM SMP, загрузки и сохранения можно наблюдать в любом порядке. Возможно, что после выполнения всего кода, reg будет содержать 0. Кроме того, возможно что он будет содержать 41. Если вы явно не определили порядок, вы не знаете, как это произойдет.

(Для тех, у кого есть опыт работы с другими системами, модель памяти ARM эквивалентна PowerPC во многих отношениях.)

Барьеры памяти данных

Барьеры памяти предоставляют возможность для вашего кода сказать процессору, что имеет значение порядок доступа к памяти. Однопроцессорные ARM/x86 предлагают последовательную согласованность, и, таким образом, нет никакой потребности в них. (Барьерные инструкции могут быть выполнены, но не являются полезными%; по крайней мере в одном случае они ужасно дорогие, мотивируя отдельные сборки для целей SMP.)

Есть четыре основные ситуации для рассмотрения:

  1. сохранение с последующим еще одним сохранением
  2. загрузка с последующей еще одной загрузкой
  3. загрузка с последующим сохранением
  4. сохранение с последующей загрузкой

Сохранить/сохранить и загрузить/загрузить

Напомним, наш предыдущий пример:

Поток 1 Поток 2
A = 41
B = 1 // “A is ready”
loop_until (B == 1)
reg = A

Потоку 1 необходимо обеспечить, чтобы сохранение в А происходило до сохранения в B. Это ситуация "сохранение/сохранение". Точно так же, потоку 2 необходимо обеспечить, чтобы загрузка B происходила до загрузки A; это ситуация загрузка/загрузка. Как упоминалось ранее, загрузки и сохранения можно наблюдать в любом порядке.

Возвращаясь к обсуждению кэша, предположим, что А и В находятся на отдельных строках кэша, с минимальной связностью кэша. Если сохранение в А остается локальным, а сохранение в B публикуется, ядро 2 увидите B=1, но не увидит обновление для А. С другой стороны, предположим, мы читаем A раньше, или оно живет в той же строке кэша, вместе с чем-то, что мы недавно читали. Ядро 2 вертится пока не увидит обновление B, затем загружает А из локального кэша, где значение по-прежнему равено нулю.

Мы можем исправить это следующим образом:

Поток 1 Поток 2
A = 41
store/store barrier
B = 1 // “A is ready”
loop_until (B == 1)
load/load barrier
reg = A

Барьер сохранение/сохранение гарантирует, что все наблюдатели будет наблюдать запись в A прежде чем они будут наблюдать запись в B. Он не дает никаких гарантий относительно порядка чтения в потоке 1, но у нас нет ни одного чтения, так что все в порядке. Барьер загрузка/загрузка в потоке 2 делает аналогичные гарантии для загрузок.

Поскольку барьер сохранение/сохранение гарантирует, что поток 2 будет наблюдать сохранения в программном порядке, зачем нам барьер загрузки/загрузки в потоке 2? Потому что мы также должны гарантировать, что поток 1 будет наблюдать загрузки в программном порядке.

Барьер сохранение/сохранение мог бы работать с помощью сбрасывания всех грязных записей из локального кэша, гарантируя, что другие ядра увидят их до того, как они увидят любые будущие сохранения. Барьер загрузка/загрузка может очистить локальный кэш полностью и ждать завершения никаких-либо загрузок «в полете», гарантируя, что будущие загрузки будут наблюдаться после предыдущих загрузок. Что на самом деле делает процессор не имеет значения, при условии, что соответствующие гарантии сохраняются. Если мы используем барьер в ядре 1, но не в ядре 2, ядро 2 все еще может читать из локального кэша.

Поскольку архитектуры имеют различные модели памяти, эти барьеры требуются для ARM SMP, но не для x86 SMP.

Загрузить/сохранить и сохранить/загрузить

Фрагмент алгоритма Деккера, показанного ранее, проиллюстрировал необходимость барьера сохранение/загрузки. Вот пример, где требуется барьер загрузки/сохранения:

Поток 1 Поток 2
reg = A
B = 1 // “I have latched A”
loop_until (B == 1)
A = 41 // update A

Поток 2 мог наблюдать запись B=1 в потоке 1 до того, как он мог бы наблюдать загрузку A в потоке 1, и, как результат, сохранение A=41 до того, как поток 1 будет иметь шанс прочитать А. Вставка барьера загрузка/сохранение в каждом потоке решает проблему:

Поток 1 Поток 2
reg = A
load/store barrier
B = 1 // “I have latched A”
loop_until (B == 1)
load/store barrier
A = 41 // update A

Сохранение в локальный кэш можно наблюдать до загрузки из основной памяти, так как доступ к основной памяти гораздо медленнее. В этом случае, предположим, что кэш ядра 1 имеет строку кэша для B, но не для А. Загрузка из А инициирована, и пока она происходит, выполнение продолжается. Запись для B происходит в локальном кэше, и в каком-то смысле становится доступным для ядра 2, в то время как загрузка из А все еще продолжается. Поток 2 способен выйти из цикла, прежде чем он сможет наблюдать нагрузку из А в потоке 1.

Трудный вопрос: нужен ли нам барьер в потоке 2? Если процессор не выполняет спекулятивные операции записи, и не выполняет команды не по порядку, может ли поток 2 сохранить в A до чтения потоком 1, если поток 1 гарантирует порядок загрузки/сохранения? (Ответ: нет.) Что делать, если есть третий поток наблюдающий за А и В? (Ответ: теперь он вам нужен, или вы могли бы наблюдать B==0 / A==4 на третьем ядре.) Самое безопасное это вставить барьеры в обоих местах, а не беспокоиться о деталях.

Как упоминалось ранее, барьеры сохранений/нагрузок единственный вид требующийся для x86 SMP.

Барьерные инструкции

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

  • Sparc V8 имеет "membar" инструкцию, которая принимает 4-элементный битовый вектор. Четыре категории барьеров могут быть определены индивидуально.
  • Alpha предоставляет "rmb" (загрузка/загрузка), "wmb" (сохранение/сохранение), и "mb" (полное). (Общая информация: ядро ​​Linux предоставляет три барьерные функции памяти с этими именами и поведением.)
  • x86 имеет различные варианты; "mfence" (введен с SSE2) предоставляет полный барьер.
  • ARMv7 имеет “dmb st” (сохранение/сохранение) и “dmb sy” (полный).

“Полный барьер” означает, что все четыре категории включены.

Важно осознавать, что единственное, что гарантировано барьерными инструкциями это порядок. Не относитесь к ним как к "точеке синхронизации" связности кэша или как к синхронным инструкциям "сбрасывания". Инструкция ARM “dmb” не имеет прямого влияния на другие ядра. Важно понимать это, когда пытаетесь выяснить, где нужно использовать барьерные инструкции.

Адресная зависимость и причинная консистентность

(Это немного более сложная тема и её можно пропустить.)

Процессор ARM обеспечивает один частный случай, когда барьера загрузка/загрузка можно избежать. Рассмотрим следующий ранее приведенный пример, но немного измененный:

Поток 1 Поток 2
[A+8] = 41
store/store barrier
B = 1 // “A is ready”
loop:
    reg0 = B
    if (reg0 == 0) goto loop
reg1 = 8
reg2 = [A + reg1]

Здесь вводится новое обозначение. Если “A” указывает на адрес памяти, “A+n” указывает на адрес памяти со сдвигом на 8 байт относительно А. Если A это базовый адрес объекта или массива, [A+8] может быть полем в объекте или элементом массива.

“loop_until”, который вы видели в предыдущем примере, был расширен, чтобы показать загрузку B в reg0. reg1 присваивается числовое значение 8, а reg2 загружается из адреса [A+reg1] (то же место, к которому обращается поток 1).

Это не будет работать правильно, потому что загрузку из B можно было наблюдать после загрузки из [A+reg1]. Мы можем исправить это с помощью барьера загрузки/загрузки после цикла, но на ARM мы также можем просто сделать следующее:

Поток 1 Поток 2
[A+8] = 41
store/store barrier
B = 1 // “A is ready”
loop:
    reg0 = B
    if (reg0 == 0) goto loop
reg1 = 8 + (reg0 & 0)
reg2 = [A + reg1]

Что же мы сделали здесь, мы изменили назначение reg1 с константы (8) на значение, которое зависит от того, что мы загрузили из B. В этом случае, мы делаем побитовый AND со значением 0, что дает ноль, а значит reg1 все еще будет иметь значение 8. Тем не менее, процессор ARM считает, что загрузка из [A+reg1] зависит от загрузки из B, и будет гарантировать, что оба значения будут наблюдаются в программном порядке.

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

ARM не обеспечивает гарантии контроля зависимостей . Чтобы проиллюстрировать это, необходимо окунуться на мгновение в ARM код: (Barrier Litmus Tests and Cookbook).

LDR r1, [r0]
CMP r1, #55
LDRNE r2, [r3]

Загрузки из r0 и r3 можно наблюдать не по порядку, хотя загрузка из r3 не будет выполнять вообще, если [r0] не имеет значения 55. Вставка AND r1, r1, #0 и замена последней команды с LDRNE r2, [r3, r1] обеспечит правильный порядок без явного барьера. (Это яркий пример того, почему вы не можете думать о вопросах согласованности с точки зрения выполнения команд. Всегда думайте в терминах доступа к памяти.)

Пока мы углубились, стоит отметить, что ARM не обеспечивает причинную консистентность:

Поток 1 Поток 2 Поток 3
A = 1 loop_until (A == 1)
B = 1
loop:
  reg0 = B
  if (reg0 == 0) goto loop
reg1 = reg0 & 0
reg2 = [A+reg1]

Здесь поток 1 устанавливает A, сигнализируя потоку 2 . Поток 2 видит это, и устанавливает B, чтобы сигнализировать потоку 3. Поток 3 видит это, и загружает из А, используя адресную зависимость для того, чтобы загрузка B и загрузка А наблюдались в программном порядке.

Возможно, что reg2 будет содержать ноль в конце этого. Тот факт, что сохранение в потоке 1 заставляет что-то случиться в потоке 2, который заставляет что-то случиться в потоке 3, не означает, что поток 3 будет наблюдать сохранения в этом порядке. (Вставка барьера загрузка/сохранение в потоке 2 исправляет это.)

Итоги барьеров памяти

Барьеры имеют различные разновидности для различных ситуаций. Хотя преимущества производительности могут быть только при использовании правильного типа барьера, есть при этом риски поддержания кода — кроме случая, когда лицо обновляющее код полностью понимает его, другие же могут ввести неправильный тип операции и вызвать загадочную поломку. Из-за этого, а также из-за того, что ARM не обеспечивает широкий выбор вариантов барьерных функций, многие атомарные примитивы используют полные барьерные инструкции, когда требуется барьер.

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

Атомарные операции

Атомарные операции гарантируют, что операция, которая требует ряда шагов всегда ведет себя так, как будто бы это была одна операция. Например, рассмотрим не атомарный инкремент (“++A”), выполняющийся для той же переменной одновременно двумя потоками:

Поток 1 Поток 2
reg = A
reg = reg + 1
A = reg
reg = A
reg = reg + 1
A = reg

Если потоки выполняются одновременно сверху вниз, оба потока будут загружать 0 из А, увеличивать до 1, и сохранят значение обратно, оставляя окончательный результат 1. Если бы мы использовали атомарную операцию приращения, вы были бы гарантировали, что окончательный результат будет 2.

Основы атомарности

Наиболее фундаментальные операции — загрузка и запись 32-битный значений — по своей сути атомарные на ARM, пока данные выровнены по 32-битной границе. Например:

Поток 1 Поток 2
reg = 0x00000000
A = reg
reg = 0xffffffff
A = reg

Процессор гарантирует, что A будет иметь значение 0x00000000 или 0xFFFFFFFF. Оно никогда не будет содержать 0x0000ffff или любой другой частичный "микс" байтов.

Гарантии атомарности теряются, если данные не выровнены. Невыровненные данные могут колебаться в строке кэш-памяти, так что другие ядра будут видеть половинки, обновляемые независимо друг от друга. Поэтому, документация ARMv7 заявляет, что она обеспечивает "атомарность одной копии" для всех однобайтовых операций доступа, доступ к полусловам при выравнивание по полуслову, и слово получает доступ при выравнивании по словам. Доступ к двойному слову (64-разрядному значению) не атомарный, кроме случая, когда расположение выровнено по двойному слову и используются специальная инструкция загрузки/сохранения. Такое поведение очень важно понимать, когда несколько потоков выполняют несинхронизированные обновления в сжатые структуры или массивы примитивных типов.

Нет необходимости в функциях для 32-разрядных “атомарных чтений” или “атомарных сохранений” на ARM или x86. Где они предусмотрены для полноты, хотя они просто делают тривиальную загрузку или сохранение.

Операции, которые выполняют более сложные действия с данными в памяти, все вместе известны как чтение-модификация-запись (RMW) инструкции, потому что они загружают данные, изменяют их определенным способом, и записывают их обратно. Процессоры отличаются друг от друга в том, как они реализованы. ARM использует технику, называемую "Связанная загрузка/Условное сохранение" (“Load Linked / Store Conditional”, или LL/SC).

Связанная или заблокированная загрузка считывает данные из памяти как обычно, но ещё выполняет резервирование, помечая физический адрес памяти. Резервирование очищается, когда другое ядро пытается писать по этому адресу. Для выполнения LL/SC, данные считываются с резервированием, изменяются, а затем используется инструкция условной записи, чтобы попытаться записать данные обратно. Если зарезервированная часть находится на своем месте, значит сохранение выполнено успешно; если нет, значит сохранение не удалось. Атомарные функции, основанные на LL/SC обычно выполняются циклически, повторяя попытки последовательности чтение-модификация-запись до завершения без нарушений.

Операции чтение-модификация-запись не будут работать правильно, если они обрабатывали устаревшие данные. Если два ядра выполняют атомарный инкремент по тому же адресу, и один из них не в состоянии видеть, что сделал другой, потому что каждое ядро ​выполняет ​чтение и запись в локальном кэше, операция не будет на самом деле атомарной. Правила связности кэша процессора гарантируют, что атомарные операции RMW остаются атомарными в среде SMP.

Это не должно быть истолковано как означающее, что атомарные операции RMW используют барьеры памяти. На ARM, атомарность не имеют семантики барьеров памяти. В то время, как ряд атомарных RMW операций по одному адресу будет наблюдаться в программном порядке другими ядрами, нет никаких гарантий, что порядок будет соблюдаться для атомарных и не атомарных операций.

Часто имеет смысл объединить барьеры и атомарные операции вместе. В следующем разделе это описывается более подробно.

Сочетание атомарности и барьера

Как обычно, полезно освещать обсуждение примерами. Мы собираемся рассмотреть основной примитив для взаимного исключения называемый спин-блокировка. Идея состоит в том, что адрес памяти (который мы назовем “блокировка”) изначально содержит ноль. Когда поток хочет выполнить код в критической секции, он устанавливает блокировку в 1, выполняет критический код, а затем изменяет значение обратно в ноль по завершению. Если другой поток уже установил блокировку в 1, мы сидим и крутимся, пока блокировка не сбросится назад в ноль.

Чтобы сделать эту работу мы используем атомарный RMW примитив называемый сравнить-и-переставить. Функция принимает три аргумента: адрес памяти, ожидаемое текущее значение, и новое значение. Если значение в настоящее время в памяти соответствует тому, что мы ожидаем, то оно заменяется новым значением, и старое значение возвращается. Если текущее значение не то, что мы ожидали, мы ничего не изменим. Небольшой вариант этого называется сравнить-и-установить; вместо того, чтобы вернуть старое значение, возвращается логическое значение, указывающее успешно ли выполнена замена. Для наших потребностей любой примитив будет работать, но сравнить-и-установить несколько проще для примеров, поэтому мы используем его и будем просто называть его “CAS” (от английского compare-and-set).

Получение спин блокировки записывается как (используя C-подобный язык):

do {
    success = atomic_cas(&lock, 0, 1)
} while (!success)

full_memory_barrier()

critical-section

Если ни один поток не удерживает блокировку, значение блокировки будет 0, а операция CAS установит его в 1, чтобы указать, что она теперь у нас есть. Если другой поток захватил блокировку, значение блокировки будет 1, а операция CAS не удастся, потому что ожидаемое текущее значение не соответствует фактическому. Мы повторяем попытку в цикле. (Обратите внимание, цикл LL/SC кода может выполняться внутри функции atomic_cas.)

На SMP, спин-блокировка является хорошим способом, чтобы охранять небольшую критическую секцию. Если мы знаем, что другой поток собирается выполнить несколько инструкций, а затем снять блокировку, мы можем просто сжечь несколько циклов, пока мы ждем своей очереди. Однако, если случается, что другой поток выполняется на том же ядре, мы просто теряем время, потому что другой поток не сможет добиться прогресса, пока операционная система не распределит его выполнение снова (либо путем переноса его на другое ядро либо выполнив нашу выгрузку). Надлежащая реализация спин-блокировки оптимистично вращаться несколько раз, а затем падает обратно к примитивам ОС (например, к futex на Linux), что позволяет текущему потоку спать в ожидании завершения операций в другом потоке. На однопроцессорной системе вы вообще никогда не захотите "крутиться". Для краткости мы игнорируем все это.

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

full_memory_barrier вызов здесь на самом деле выполняет две независимые операции. Первая - задает инструкцию процессору выполнения полного барьера. Вторая - говорит компилятору, что нельзя изменять порядок кода вокруг барьера. Таким образом, мы знаем, что atomic_cas вызов будет выполнен, прежде чем выполнится что-либо в критической секции. Без этого барьера перестановок компилятора, компилятор имеет больше свободы в том, как он генерирует код, и порядок инструкций в скомпилированном коде может сильно отличается от порядка в исходном коде.

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

do {
    success = atomic_cas(&lock, 0, 1)   // acquire
} while (!success)
full_memory_barrier()

critical-section

full_memory_barrier()
atomic_store(&lock, 0)                  // release

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

Как упоминалось ранее, atomic_store операция является простым присваиванием на ARM и x86. В отличие от атомарных RMW операций, мы не можем гарантировать, что другие потоки сразу же увидят это значение. Это не проблема, хотя бы потому что нам нужно только держать другие потоки отдельно. Другие потоки будут оставаться в стороне, пока они не увидят сохраненный 0. Если это займет некоторое время, прежде чем они смогу наблюдать его, другие потоки будут вращаться немного дольше, но мы все равно правильно выполняем код.

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

Получение и освобождение

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

Перепишем пример спин-блокировки с учетом этого:

do {
    success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)

critical-section

atomic_release_store(&lock, 0)

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

Во-первых, рассмотрим atomic_release_store. Мы должны быть уверены, что сохранение нуля в слово блокировки наблюдается после любых загрузок или сохранений в критической секции выше. Другими словами, нам нужен барьер загрузки/сохранения и сохранения/сохранения. В предыдущем разделе мы узнали, что это не нужно для x86 SMP -- необходим только барьер сохранения/загрузки. Реализация atomic_release_store на x86 в связи с этим это только барьер сохранения порядка компилятором, следующий за простым сохранением. Барьер процессора не требуется.

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

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

local1 = arg1 / 41
local2 = threadStruct->field2
threadStruct->field3 = local2

do {
    success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)

local5 = globalStruct->field5
globalStruct->field6 = local5

atomic_release_store(&lock, 0)

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

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

do {
    success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)

local2 = threadStruct->field2
local5 = globalStruct->field5
local1 = arg1 / 41
threadStruct->field3 = local2
globalStruct->field6 = local5

atomic_release_store(&lock, 0)

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

Обратите внимание, что все операции в настоящее время происходят внутри критической секции. Поскольку ни одна из операций “threadStruct” не видна за пределами текущего потока, ничто другое не может увидеть их, пока мы не закончили здесь, так что это не имеет значения, когда именно они происходят.

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

Возвращаясь к более раннему моменту, можно констатировать, что на x86 все загрузки это загрузки получения, и все сохранения это освобождающие сохранения. В результате:

  • Загрузки не могут быть переупорядочены без нарушений по отношению друг к другу. Вы не можете взять загрузку и переместить её «вверх» через барьер получения.
  • Сохранения не могут быть перераспределены без нарушений по отношению друг к другу, потому что вы не можете переместить сохранение "вниз" через барьер освобождения.
  • Загрузка следующая за сохранением не может быть переупорядочена, потому что ни одна инструкция не будет это терпеть.
  • Сохранения следующее за загрузкой может быть переупорядочено, потому что каждая команда может перемещаться за другими в этом направлении.

Таким образом, вам нужен всего лишь барьер сохранения/загрузки на x86 SMP.

Маркировка атомарных операции "получением" или "освобождением" описывает не только выполняется ли барьер до или после элементарной операции, но и, как компилятору разрешено изменять порядок кода.

Практика

Отладка проблем согласованности памяти может быть очень трудной. Если отсутствующий барьер памяти приводит к тому, что некоторый код считывает устаревшие данные, возможно вы будете не в состоянии понять, почему, исследуя дампы памяти с помощью отладчика. К тому времени, когда вы сможете послать запрос отладчику, ядра процессора будут иметь возможность наблюдать полный набор обращений, а содержимое памяти и регистров процессора окажется в «невозможном» состоянии.

Чего не делать в С

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

C/C++ и "volatile"

При написании однопоточного кода, объявление переменной как “volatile” может быть очень полезным. Компилятор не будем пропускать или изменять порядок доступа к непостоянным местам. Объедините это с последовательной согласованностью предоставленной аппаратным обеспечением, и вам гарантированно, что загрузки и сохранения произойдут в ожидаемом порядке.

Тем не менее, доступ к непостоянной памяти может быть переупорядочен с обращениями к другим видам памяти, так что вы должны быть осторожны в многопоточных средах однопроцессорных систем (может потребоваться явный барьер компилятора для предотвращения переупорядочивания). Нет гарантий атомарности, и нет обеспечения барьеров памяти, так что “volatile” не поможет вам вообще в многопоточных SMP средах. Стандарты языка С и C++ обновляются, чтобы решить эту проблему с помощью встроенных атомарных операций.

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

Примеры

В большинстве случаев вы бы скорее отказались от примитивов синхронизации (таких как pthread mutex), чем от атомарных операций, но мы будем использовать атомарные операции для иллюстрации того, как они будут использоваться в практической ситуации.

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

MyThing* gGlobalThing = NULL;

void initGlobalThing()    // runs in thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}

void useGlobalThing()    // runs in thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

Идея заключается в том, что мы выделяем структуру, инициализируем её поля, и в самом конце мы "опубликовываем" её, сохраняя её в глобальную переменную. В этот момент, любой другой поток может увидеть её, ведь это же нормально, т.к. она полностью инициализирована, не так ли? По крайней мере, это было бы на x86 SMP или однопроцессорной системе (опять же, делая ошибочное предположение, что компилятор выводит код в точности, как у нас это есть в исходном коде).

Без барьера памяти, сохранение в gGlobalThing можно было бы наблюдать до инициализации поля на ARM. Другой поток читающий из thing->x может увидеть 5, 0, или даже неинициализированные данные.

Это может быть исправлено путем изменения последнего присвоения на:

    atomic_release_store(&gGlobalThing, thing);

Это гарантирует, что все остальные потоки будут соблюдать запись в правильном порядке, но как насчет считывания? В этом случае всё должно быть в порядке на ARM, так как правила адресной зависимости будут гарантировать, что любые загрузки со смещением относительно gGlobalThing наблюдаются после загрузки gGlobalThing. Однако, неразумно полагаться на архитектурные детали, так как это означает, что ваш код будет очень плохо непереносимым. Полное исправление также требует барьера после загрузки:

    MyThing* thing = atomic_acquire_load(&gGlobalThing);
    int i = thing->x;

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

MyThing gGlobalThing;

void initGlobalThing()    // runs in thread 1
{
    gGlobalThing.x = 5;
    gGlobalThing.y = 10;
    /* initialization complete */
    gGlobalThing.initialized = true;
}

void useGlobalThing()    // runs in thread 2
{
    if (gGlobalThing.initialized) {
        int i = gGlobalThing.x;    // could be 5 or 0
    }
}

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

Мы должны заменить сохранение на:

    atomic_release_store(&gGlobalThing.initialized, true);

и заменить загрузку на:

    int initialized = atomic_acquire_load(&gGlobalThing.initialized);

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

void RefCounted::release()
{
    int oldCount = atomic_dec(&mRefCount);
    if (oldCount == 1) {    // was decremented to zero
        recycleStorage();
    }
}

void useSharedThing(RefCountedThing sharedThing)
{
    int localVar = sharedThing->x;
    sharedThing->release();
    sharedThing = NULL;    // can’t use this pointer any more
    doStuff(localVar);    // value of localVar might be wrong
}

release() вызов уменьшает счетчик ссылок, используя атомную без барьерную операцию уменьшения. Т.к. это является атомарной RMW операцией, мы знаем, что она будет работать правильно. Если количество ссылок стало ноль, мы перерабатываем область памяти.

useSharedThing() функция извлекает то, что её нужно из sharedThing , а затем освобождает её копию. Однако, поскольку мы не использовали барьер памяти, а атомарные и не атомарные операции могут быть перераспределены, то для других потоков возможно наблюдать чтение sharedThing->x после того, как они будут наблюдать операцию очистки. Поэтому возможно, что localVar будет содержать значение из "переработанной" памяти, например новый объект был создан по тому же адресу другим потоком после того, как release() был вызван.

Это может быть исправлено путем замены вызова atomic_dec() на atomic_release_dec(). Барьер гарантирует, что чтение из sharedThing будет наблюдаться прежде мы переработаем объект.

В большинстве случаев выше, не будет на самом деле ошибок, потому что функция “recycle”, скорее всего, охраняется функциями, которые сами используют барьеры (функции libc кучи free()/delete(), или пул объектов охраняется семафорами). Однако, если функция рециркуляции использует алгоритм без блокировки, реализованный без барьеров, код выше может сломаться на ARM SMP.

Чего не делать в Java

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

Ключевые слова "synchronized" и "volatile" в Java

Ключевое слово “synchronized” предоставляет встроенный механизм блокировки языка Java. Каждый объект имеет связанный с ним "монитор", который может использоваться для обеспечения взаимно исключающего доступа.

Реализация “synchronized” блока имеет ту же базовую структуру, что и спин-блокировки, например: он начинается с получения CAS, и заканчивается освобождающимся сохранением. Это означает, что компиляторы и оптимизаторы кода могут свободно мигрировать код в “synchronized” блоке. Одним из практических последствий: вы не должны делать заключение, что код внутри синхронизированного блока происходит после того, что над ним, или до того, что под ним, в данном методе. Двигаясь дальше, если метод имеет два синхронизированных блока, которые захватывают один и тот же объект, и нет никаких операций в промежуточным коде, наблюдаемых другим потоком, компилятор может выполнять "укрупнение блокировки" и объединить их в единый блок.

Другое соответствующее ключевое слово “volatile”. Как определено в спецификации для Java 1.4 и более ранних версиях, определение volatile было примерно таким же слабым, как и его С коллега. Спецификация для Java 1.5 была обновлена для ​​обеспечения большей надежности, почти до уровня синхронизации монитора.

Эффекты volatile доступа может быть проиллюстрирован на примере. Если поток 1 пишет в volatile поле, и поток 2 впоследствии читает из этого же поля, то поток 2 гарантировано видит эту запись и все записи ранее сделанные потоком 1. В более общем смысле, записи сделанные любым потоком до точки, где он записывает поле, будет видно потоку 2, когда он выполнит чтение. По сути, запись в volatile поля подобно освобождению монитора, а чтение из volatile подобно получению монитора.

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

Следует отметить, что, в то время как загрузки и сохранения ссылок на объекты и большей части примитивных типов атомарные, long и double поля не используют атомарный доступ, если они не отмечены как volatile. Многопоточные обновления для не volatile 64-битных полей являются проблематичными даже в однопроцессорных системах.

Примеры

Вот простая, неправильная реализация монотонного счетчика: (Теория и практика Java: Управление изменчивостью).

class Counter {
    private int mValue;

    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

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

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

Если два потока выполняются в incr() одновременно, одно из обновлений может быть потеряно. Чтобы выполнить приращение атомарно, мы должны объявить incr() “synchronized”. С этим изменением, код будет корректно работать в многопоточном среде однопроцессорной системы.

Он по-прежнему сломан для SMP, однако. Различные потоки могут видеть разные результаты из get(), потому что мы вычитываем значение обычной загрузкой. Мы можем исправить проблему, так объявив get() “synchronized”. С этими изменениями, код очевидно правильный.

К сожалению, мы ввели возможность соперничества блокировок, которые могут снизить производительность. Вместо объявления синхронизации для get() мы могли бы объявить mValue как “volatile”. (Примечание: incr() все еще должен использовать synchronize.) Теперь мы знаем, что volatile запись в mValue будет видна любому последующему volatile чтению из mValue. incr() будет немного медленнее, но get() будет быстрее, так что даже в отсутствие разногласий это победа, если чтения превосходят численностью записи. (См. также AtomicInteger.)

Вот еще один пример, похожий по форме на предыдущие C примеры:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;

    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }

    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Он имеет те же проблемы, что и код C, а именно присвоение sGoodies = goods может наблюдаться до инициализации полей в goods. Если вы объявляете sGoodies с ключевым словом volatile, вы можете думать о загрузках, как если бы они были atomic_acquire_load() вызовом, и сохранения, как если бы они были atomic_release_store() вызовом.

(Отметим, что только sGoodies ссылка является volatile. Доступ к полям внутри него нет. Оператор z = sGoodies.x выполнит volatile загрузку MyClass.sGoodies с последующей не volatile загрузкой sGoodies.x. Если вы делаете локальную ссылку MyGoodies localGoods = sGoodies, z = localGoods.x не будет выполнять каких-либо volatile загрузок.)

Наиболее распространенная идиома языка программирования Java это печально известная "блокировка с двойной проверкой":

class MyClass {
    private Helper helper = null;

    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

Идея состоит в том, что мы хотим иметь один экземпляр Helper объекта, связанный с экземпляром MyClass. Мы должны создать только один раз, так что мы создаем и возвращаем его через специальную getHelper() функцию. Чтобы избежать гонки, в которой два потока создают экземпляр, мы должны синхронизировать создание объекта. Тем не менее, мы не хотим платить накладные расходы “synchronized” блока на каждом вызове, поэтому мы только делаем эту часть, если helper в настоящее время нулевой.

Это не корректно работает на однопроцессорных системах, если вы не используете традиционный компилятор исходного Java и только интерпретатор для VM. После добавления причудливых оптимизаторов кода и JIT компилятора идиома ломается. См. ссылку The “Double-Checked Locking is Broken” Declaration в приложении для более подробной информации, или Пункт 71 ("Используйте ленивую инициализацию рассудительно") книги Josh Bloch Effective Java, 2-е издание..

Запуск этого на многопроцессорной системе вводит дополнительный путь к провалу. Рассмотрим тот же код переписанный немного, как будто это было собрано в C-подобном языке (я добавил пару целочисленных полей для выполнения действий в Helper’s конструкторе):

if (helper == null) {
    // acquire monitor using spinlock
    while (atomic_acquire_cas(&this.lock, 0, 1) != success)
        ;
    if (helper == null) {
        newHelper = malloc(sizeof(Helper));
        newHelper->x = 5;
        newHelper->y = 10;
        helper = newHelper;
    }
    atomic_release_store(&this.lock, 0);
}

Теперь проблема должна быть очевидна: сохранение в helper происходит до барьера памяти, что означает, что другой поток может наблюдать ненулевое значение helper до сохранения в x/y поля.

Вы можете попробовать обеспечить, чтобы сохранение в helper происходило после atomic_release_store() на this.lock , перестраивая код, но это не поможет, потому что это нормально мигрировать код вверх — компилятор может двигать присваивание обратно выше atomic_release_store() в исходное положение.

Есть два способа это исправить:

  1. Сделайте простую вещь и удалить внешнюю проверку. Это гарантирует, что мы никогда не проверим значение helper вне блока синхронизации.
  2. Объявлять helper как volatile. С этим одним маленьким изменения, код в примере J-3 будет корректно работать на Java 1.5 и более поздних версиях. (Вы можете уделить минуту, чтобы убедить себя, что это правда.)

Следующий пример иллюстрирует два важных вопроса при использовании volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;

    void setValues() {    // runs in thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }

    void useValues1() {    // runs in thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
    void useValues2() {    // runs in thread 2
        int dummy = vol2;
        int l1 = data1;    // wrong
        int l2 = data2;    // wrong
    }

Глядя на useValues1(), если поток 2 еще не наблюдал обновление vol1, то он не может знать, были ли data1 или data2 уже установлены. Как только он видит обновление vol1, он знает, что изменение data1 также видно, потому что это было сделано до изменения vol1 . Тем не менее, он не может делать никаких предположений о data2, потому что сохранение было выполнено после volatile сохранения.

Код в useValues2() использует второе volatile поле, vol2, в попытке заставить виртуальную машину сгенерации барьер памяти. Это обычно не работает. Чтобы установить правильное отношение "происходит-до", оба потока должны взаимодействовать с тем же volatile полем. Вы должны были бы знать, что vol2 был установлен после data1/data2 в потоке 1 (Тот факт, что это не работает, вероятно, очевидно глядя на код; предусмотрительность здесь в попытке умно "вызвать" барьер памяти вместо создания упорядоченного ряда обращений.)

Что делать

Общие рекомендации

В C/C++, используйте pthread операции, такие как мьютексы и семафоры. Они включают в себя соответствующие барьеры памяти, обеспечивая правильное и эффективное поведение на всех версиях платформы Android. Удостоверьтесь в их правильном использовании, например опасайтесь сигнализации переменной условия без удержания соответствующего мьютекса.

Лучше всего избегать использования атомарных функций непосредственно. Блокировка и разблокировка pthread мьютекса требует одной атомарной операции каждая, если нет никакого соперничества, так что вы не сможете много сэкономить, заменив вызовы мьютекса атомарными операциями. Если вам нужен дизайн без блокировок, вы должны полностью понимать концепции этого всего документа, прежде чем начать (или, еще лучше, найти существующую библиотеку кода, о которой известно, что она правильно работает на SMP ARM).

Будьте предельно осмотрительны с "volatile” в C/C++. Это часто указывает на проблему параллелизма, которая должна случиться.

В Java, лучший ответ, как правило, использовать соответствующий служебный класс из java.util.concurrent пакета. Код хорошо написан и хорошо протестирован на SMP.

Возможно, самым безопасным, что вы можете сделать, это сделать ваш класс неизменным (immutable). Объекты классов, такие как String и Integer содержат данные, которые не могут быть изменены, как только создается класс, избегая всех проблем синхронизации. Книга Effective Java, 2-е издание. имеет конкретные инструкции в "Пункте 15: Минимизируйте изменчивость". Помните в частности важность декларирования полей ключевым словом “final” (Bloch).

Если ни один из этих вариантов не является жизнеспособным, блок “synchronized” в Java следует использовать для защиты любого поля, которое может быть доступно более чем одному потоку. Если мьютексы не будут работать для вашей ситуации, вы должны объявить общие поля как “volatile”, но вы должны проявлять большую осторожность, чтобы понять взаимодействие между потоками. Объявление “volatile” не спасет вас от распространенных параллельных ошибок программирования, но это поможет вам избежать таинственных провалов, связанных с оптимизацией компиляторов и SMP неудачами.

Модели памяти Java гарантирует, что присвоение final полей могут видеть все потоки, как только конструктор выполнен — это то, что обеспечивает правильную синхронизацию полей в неизменяемых классах. Эта гарантия не выполняется, если допускается, что частично построенный объект становится видимым для других потоков. Необходимо следовать безопасной практики строительства.(Технологии безопасного создания в Java).

Гарантии примитивов синхронизации

Библиотека pthread и VM делают пару полезных гарантий: все доступы, ранее выполнявшиеся потоком, который создает новый поток, видны в этом новом потоке, как только он запустился, и все доступы, выполняемые потоком, который завершился, видны когда join() для этого потока выполнился. Это означает, что вам не нужно никаких дополнительных синхронизаций при подготовке данных для нового потока или проверка результатов присоединенного потока.

Распространяются ли или нет эти гарантии на взаимодействие с пулом потоков зависит от реализации пула потоков.

В C/C++, pthread библиотека гарантирует, что любые доступы сделанные в потоке, прежде чем он разблокирует мьютекс, будут наблюдаемы другим потоками после того, как он захватит блокировку того же мьютекса. Она также гарантирует, что любые доступы сделанные перед вызовом signal() или broadcast() для условной переменной можно будет наблюдать в проснувшемся потоке.

Потоки и мониторы языка Java делают подобные гарантии для сопоставимых операций.

Предстоящие изменения в C/C++

Стандарты языка C и С++ развиваются, чтобы включить сложную коллекцию атомарных операций. Полная матрица вызовов для распространенных типов данных определена, с помощью семантики выбора барьеров памяти (выбирая из relaxed, consume, acquire, release, acq_rel, seq_cst).

Смотрите Дополнительная литература , раздел указателей на спецификации.

Заключительные примечания

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

  • Выучите определения происходит-до, синхронизируется-с, и другие необходимые понятия модели памяти Java. (Трудно понять, что “volatile” на самом деле означает.)
  • Узнайте, что компиляторы имеют и не имеют права делать, когда переупорядочивают код. (JSR-133 спецификации имеет много примеров законных преобразований, которые приводят к неожиданным результатам.)
  • Узнайте, как писать неизменяемые классы в Java и C++. (Это больше, чем просто "ничего не изменится после создания".)
  • Усвойте рекомендации в разделе Параллелизм книги Effective Java, 2-е издание. (Например, вам следует избегать вызова методов, которые предназначены для переопределения в то время как внутри синхронизированный блок.)
  • Осознайте какого рода барьеры можно использовать на x86 и ARM. (И на других процессоров, например, модификаторы инструкций получения/освобождения в Itanium.)
  • Прочитайте java.util.concurrent и java.util.concurrent.atomic API, чтобы видеть то, что доступно. Рассмотрите возможность использования аннотаций параллелизма как @ThreadSafe и @GuardedBy (из net.jcip.annotations).

Дополнительная литература в разделе приложение имеет ссылки на документы и веб-сайты, которые будут лучше освещают эти темы.

Приложение

Пример ошибок SMP

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

Модель памяти Java Билла Пью, на веб-сайте есть несколько тестовых программ. Один интересный тест ReadAfterWrite.java, который выполняет следующее:

Поток 1 Поток 2
for (int i = 0; i < ITERATIONS; i++) {
    a = i;
    BB[i] = b;
}
for (int i = 0; i < ITERATIONS; i++) {
    b = i;
    AA[i] = a;
}

Где a и b объявлены как volatile int поля, и AA и BB обычные массивы целых чисел.

Тест пытается определить, гарантирует ли VM, что после того, как значение записывается в volatile, следующее чтения из volatile видит новое значение. Тестовый код выполняет эти циклы миллион или около того раз, а затем проходит и ищет результаты несоответствий.

В конце выполнения,AA и BB будет полон постепенно возрастающих чисел. Потоки не будут работать бок о бок предсказуемым образом, но мы можем утверждать об отношении между содержимым массива. Например, рассмотрим этот фрагмент выполнения:

Поток 1 Поток 2
(initially a == 1534)
a = 1535
BB[1535] = 165
a = 1536
BB[1536] = 165




a = 1537
BB[1537] = 167
(initially b == 165)




b = 166
AA[166] = 1536
b = 167
AA[167] = 1536

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

Посмотрите на присваивание AA[166] в потоке 2. Мы захватили тот факт, что в точке, где поток 2 был на итерации 166, он может увидеть, что поток 1 был на итерации 1536. Если мы посмотрим на один шаг в будущее, на итерацию 1537 в потоке 1, мы ожидаем увидеть, что поток 1 увидел, что поток 2 был на итерации 166 (или более поздней версии). BB[1537] содержит 167, так что похоже все работает.

Теперь предположим, что мы не можем заметить, volatile запись в b:

Поток 1 Поток 2
(initially a == 1534)
a = 1535
BB[1535] = 165
a = 1536
BB[1536] = 165




a = 1537
BB[1537] = 165 // stale b
(initially b == 165)




b = 166
AA[166] = 1536
b = 167
AA[167] = 1536

Теперь, BB[1537] содержит 165, меньшее значение, чем мы ожидали, поэтому мы знаем, что есть проблема. Попробуйте, for i=166, BB[AA[i]+1] < i. (Это также ловит неудачи потока 2 в наблюдении записей в a, например, если мы пропустим обновление и присваивание AA[166] = 1535, мы получим BB[AA[166]+1] == 165.)

Если вы запустите тестовую программу под Dalvik (Android 3.0 "Honeycomb" или выше) на устройстве SMP ARM, это всегда будет работать. Если вы удалите слово “volatile” из объявлений a и b, тест будет последовательно терпеть неудачи. Программа тестирует чтобы увидеть, предоставляет ли VM последовательную консистентность порядка обращений к a и b, так что вы увидите только правильное поведение, когда переменные являются volatile. (Он также успешно выполнится, если вы запустите код на однопроцессорном устройстве, или запустить его когда что-то еще сильно использует процессор, так что ядро ОС ​​не будет планировать тестовые потоки на отдельные ядра процессора.)

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

Реализация синхронизации памяти

(Это не то что, большинство программистов найдут в своих реализация, но обсуждение освещает данную проблему.)

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

Начнем с фрагмента алгоритма Деккера. Первоначально оба flag1 и flag2 равны false:

Поток 1 Поток 2
flag1 = true
if (flag2 == false)
    critical-stuff
flag2 = true
if (flag1 == false)
    critical-stuff
flag1 и flag2 объявлены как логические volatile поля. Правила приобретения загрузки и освобождающих сохранений разрешает переупорядочивание доступа в каждом потоке, ломая алгоритм. К счастью, модель памяти Java имеет несколько вещей, которые рассмотрим здесь. Неофициально:

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

Взятые вместе, эти правила говорят, что volatile доступы в нашем примере должны наблюдаться в программном порядке всеми потоками. Таким образом, мы никогда не будем видеть, что эти потоки выполняют “critical-stuff” одновременно.

Еще один способ это думать об этом с точки зрения гонки данных. Гонка данных происходит, если два доступа к одной ячейке памяти разными потоками не упорядочены, по крайней мере один из них записывает в ячейку памяти, и по крайней мере одно из них не является действием синхронизации (Boehm и McKenney). Модель памяти заявляет, что программа без гонок данных должны вести себя так, как будто выполняться на машине с последовательной консистентностью. Поскольку оба flag1 и flag2 являются volatile, и доступ к volatile считается действием синхронизации, нет гонки данных и этот код должен выполниться последовательно консистентным образом.

Как мы видели в предыдущем разделе, мы должны вставить барьер сохранения/загрузки между двумя операциями. Код, выполняемый в виртуальной машине для доступа к volatile будет выглядеть примерно так:

загрузка volatile сохранение в volatile
reg = A
load/load + load/store barrier
store/store barrier
A = reg
store/load barrier

Загрузка из volatile это просто приобретение загрузки. Сохранение в volatile похож на освобождающие сохранения, но мы опустили барьер загрузки/сохранения из барьер перед сохранением, и добавили барьер сохранения/загрузки после.

Что мы действительно пытаемся гарантировать, так это то, что (с помощью потока 1 в качестве примера) запись во flag1 наблюдается до чтения из flag2. Мы могли выполнить вместо этого барьер сохранения/загрузки перед volatile загрузкой, и получить тот же результат, но т.к. загрузки имеют тенденцию превосходить число сохранений, то лучше связать барьер с сохранением.

В некоторых архитектурах, можно реализовать volatile сохранения с помощью атомарных операций и пропустить явный барьер сохранения/загрузки. На x86, например, атомарность обеспечивает полный барьер. Операции ARM LL/SC не включают барьер, поэтому для ARM мы должны использовать явные барьеры.

(Многое из этого связано с Дугом Ли и его страницей “JSR-133 Поваренная книга для разработчиков компиляторов”.)

Дополнительная литература

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

Модели согласованности общей памяти: Учебное пособие
Написанная в 1995 году Adve & Gharachorloo, это хорошее место для начала, если вы хотите углубиться в модели согласованности памяти.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Барьеры памяти
Неплохая статья, обобщающая вопросы.
http://en.wikipedia.org/wiki/Memory_barrier
Основы потоков
Введение в многопоточное программирования в C++ и Java, Ганса Бем. Отличное обсуждение гонок данных и основных методов синхронизации.
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html
Java параллелизм на практике
Опубликованая в 2006 году, эта книга охватывает широкий круг вопросов в мельчайших подробностях. Очень рекомендована для любого написание многопоточного кода в Java.
http://www.javaconcurrencyinpractice.com
JSR-133 (Модель памяти Java) Часто задаваемые вопросы
Короткое введение в модели памяти Java, в том числе объяснение синхронизации, volatile переменных, и создание final полей.
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Обзор пакета java.util.concurrent
Документация для java.util.concurrent пакета. В нижней части страницы находится раздел, озаглавленный "Свойства согласованности памяти", который объясняет гарантии, предоставляемые различными классами.
java.util.concurrent итоги пакета
Теория и практика Java: Технологии безопасного создания в Java
Эта статья подробно рассматривает опасности ссылок ставших видимыми в процессе конструирования объекта, а также предоставляет рекомендации по потокобезопасным конструкторам.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Теория и практика Java: Управление изменчивостью
Хорошая статья, описывающая, что вы можете и не можете достичь с помощью volatile полей в Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
Заявление о “Сломанной блокировке с двойной проверкой”
Подробное объяснение Билла Пью различных путей, в которых сломана блокировка с двойной проверкой. Включая C/C++ и Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Барьеры: Лакмусовые тесты и поваренная книга
Обсуждение вопросов ARM SMP, освещается короткие фрагменты ARM кода. Если вы нашли примеры в этом документе слишком не специфическими, или вы хотите прочитать официальное описание инструкции DMB, прочитайте это. Также описываются инструкции, используемые для барьеров памяти на исполняемом коде (возможно полезной, если вы генерируете код на лету).
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Барьеры памяти ядра Linux
Документация по барьерам памяти Linux ядра. Включает несколько полезных примеров и ASCII графику.
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21 (C++ стандарты) 14882 (C++ язык программирования), глава 29 ("Библиотека атомарных операций")
Черновик стандарта для атомарных операций C++.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3090.pdf
(введение: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf)
ISO/IEC JTC1 SC22 WG14 (C стандарты) 9899 (язык программирования С) глава 7.16 (“Атомарность <stdatomic.h>”)
Черновик стандарта для ISO/IEC 9899-201x C для выполнения атомарных операций. (См. также n1484 для опечаток.)
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1425.pdf
Алгоритм Деккера
“Первое известное правильное решение проблемы взаимного исключения в параллельном программировании”. Статья Википедии имеет полный алгоритм, с обсуждения того, как это должно было бы быть обновлено для работы с современными оптимизирующими компиляторами и SMP оборудованием.
http://en.wikipedia.org/wiki/Dekker's_algorithm
Комментарии ARM по сравнению с Alpha и адресные зависимости
Переписка по электронной почте об arm-ядре с Catalin Marinas. Включает хорошую сводку адресной зависимости и зависимостей управления.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
Что каждый программист должен знать о памяти
Очень длинная и подробная статья о различных типах памяти, в частности о кэше процессора, Ульриха Дреппера.
http://www.akkadia.org/drepper/cpumemory.pdf
Рассуждения о слабой консистентности модели памяти в ARM
Эта статья была написана Chong & Ishtiaq из ARM, Ltd. Она пытается описать модель памяти ARM SMP в строгой, но доступной манере. Определение "наблюдаемости", используемое здесь, исходит из этой статьи.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711
JSR-133 Поваренная книга для разработчиков компиляторов
Дуг Леа написал это в качестве дополнения к документации JSR-133 (Модель памяти Java). Это гораздо глубже в деталях, чем большинству людей нужно беспокоиться об этом, но он обеспечивает хорошую пищу для размышления.
http://g.oswego.edu/dl/jmm/cookbook.html
Семантика многопроцессорного машинного кода Power и ARM
Если вы предпочитаете объяснения в строгой математической форме, это прекрасное место, чтобы идти дальше.
http://www.cl.cam.ac.uk/~pes20/weakmemory/draft-ppc-arm.pdf