Глубокое погружение в Java Memory Model30.08.2022 20:31

ebnmiu3gfh1rn74kqsnvqrv2rnm.png

Я провел в изучении JMM много часов и теперь делюсь с вами знаниями в простой и понятной форме.

В этой статье мы подробно разберем Java Memory Model (JMM) и применим полученные знания на практике. Да, в интернете накопилось достаточно много информации про JMM/happens-before, и, кажется, что очередную статью про такую заезженную тему можно пропускать мимо. Однако я постараюсь дать вам намного большее и глубокое понимание JMM, чем большинство информации в интернете. После прочтения этой статьи вы будете уверенно рассуждать о таких вещах как memory ordering, data race и happens-before. JMM — сложная тема и не стоит верить мне на слово, поэтому большинство моих утверждений подтверждается цитатами из спеки, дизассемблером и jcstress тестами.


Введение: контекст

В современном мире код часто выполняется не в том порядке, в котором он был написан в программе. Он часто переупорядочивается на уровне:


  1. Компилятора байткода (в частности, javac)
  2. Компилятора машинного кода (в частности, JIT компилятор HotSpot C1/C2). Например, среди компиляторов широко распространена такая оптимизация как Instruction scheduling
  3. Процессора. Например, в мире процессоров широко распространены такие практики как Out-of-order execution, Branch Prediction + Speculation, Prefetching, а также многие другие

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

Все эти оптимизации делаются с целью повысить производительность программ:


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

Хорошо, но как в таком хаосе мы вообще можем написать корректную программу?

Есть хорошие новости, и плохие. Начнем с хорошей:


  1. Java дает гарантию as-if-serial выполнения кода — вне зависимости от используемой JDK итоговый результат выполнения будет не отличим от такого порядка, как если бы действия выполнялись действительно последовательно согласно порядку в коде
  2. Процессоры тоже делают только такие переупорядочивания, которые не изменят итогового результата выполнения инструкций
  3. Процессоры имеют Cache Coherence механизм, который гарантирует консистентность данных среди локальных кэшей: как только значение попадает в локальный кэш одного ядра, оно будет видно всем остальным ядрам

Рассмотрим на примере — этот однопоточный код может быть переупорядочен как угодно под капотом, но в итоге мы гарантированно увидим результат обеих записей при чтении: 

a = 5;
b = 7;
int r1 = a; /* always 5 */
int r2 = b; /* always 7 */

Какой порядок инструкций мог быть под капотом?
Например, такой: 

b = 7;
a = 5;
int r2 = b; /* 7 */
int r1 = a; /* 5 */

Или такой: 

b = 7;
int r2 = b; /* 7 */
a = 5;
int r1 = a; /* 5 */

Но здесь важно лишь то, что выполняемые под капотом действия в итоге приводят к ожидаемому результату. Такие переупорядочивания легальны потому, что эти 2 набора из записи/чтения никак не связаны друг с другом.

Теперь плохие новости:


  1. Java дает as-if-serial гарантию только для единственного треда в изоляции. Это означает, что в многопоточной программе при работе с shared данными мы можем не увидеть записи там, где полагаемся на порядок выполнения действий в коде другого треда. Другими словами, для первого треда в изоляции валидно переупорядочивать инструкции местами, если это не повлияет на его результат выполнения, но переупорядочивание может повлиять на другие треды
  2. Процессор также дает гарантию только для единственного ядра в изоляции
  3. Cache Coherence действительно гарантирует чтение актуальных значений, но пропагация записи происходит не мгновенно, а с некоторой задержкой

Обо всем этом мы еще поговорим далее.

Теперь давайте перейдем к примеру из заголовка к статье: 

public class MemoryReorderingExample {
    private int x;
    private int y;

    public void T1() {
        x = 1;
        int r1 = y;
    }

    public void T2() {
        y = 1;
        int r2 = x;
    }
}

Проанализируем программу: если в первом треде мы видим 0 при чтении y, то запись в x точно произошла, так как чтение идет после записи в порядке программы. Аналогично рассуждаем и о втором треде: если мы видим 0 при чтении x, то запись в y точно произошла. Таким образом, кажется, что мы никогда не можем получить такой результат, когда увидим 0 на обоих чтениях. Однако, хоть это и может показаться странным, но в данной программе мы вполне можем наблюдать результат чтения (r1, r2) = (0, 0). А причины следующие:


  1. Instructions reordering. Оба треда могли поменять местами инструкции записи и чтения, так как эти действия никак не связаны
  2. Visibility. Даже если переупорядочивания не было, записи могут быть просто не видны из-за оптимизаций компилятора или задержки при пропагации записи на уровне кеша

Совсем не нужно верить мне на слово, поэтому давайте напишем тест при помощи инструмента jcstress, который позволяет писать concurrency тесты для Java: 

@JCStressTest
@Description("Classic test that demonstrates memory reordering")
@Outcome(id = "1, 1", expect = Expect.ACCEPTABLE, desc = "Have seen both writes")
@Outcome(id = {"0, 1", "1, 0"}, expect = Expect.ACCEPTABLE, desc = "Have seen one of the writes")
@Outcome(id = "0, 0", expect = Expect.ACCEPTABLE_INTERESTING, desc = "Have not seen any write")
public class JmmReorderingDekkerTest {

    @Actor
    public final void actor1(DataHolder dataHolder, II_Result r) {
        r.r1 = dataHolder.actor1();
    }

    @Actor
    public final void actor2(DataHolder dataHolder, II_Result r) {
        r.r2 = dataHolder.actor2();
    }

    @State
    public static class DataHolder {
        private int x;
        private int y;

        public int actor1() {
            x = 1;
            return y;
        }

        public int actor2() {
            y = 1;
            return x;
        }
    }
}

Вот как нужно интерпретировать результат теста:


  • (1, 1): Expect.ACCEPTABLE — мы прочитали обе записи. Это корректное поведение
  • (0, 1), (1, 0): Expect.ACCEPTABLE — мы прочитали одно из значений слишком рано. Это корректное поведение
  • (0, 0): Expect.ACCEPTABLE_INTERESTING — мы не увидели ни одной записи. Это случай instructions reordering/visibility

Запускаем тест на Intel Core i7–11700 (x86), Windows 10×64, OpenJDK 17 (инструкцию по сборке и запуску тестов вы сможете найти в моем репозитории, который я приведу в конце статьи): 

RESULT         SAMPLES     FREQ       EXPECT  DESCRIPTION
  0, 0   2,188,517,311   18,91%  Interesting  Have not seen any write
  0, 1   4,671,980,718   40,36%   Acceptable  Have seen one of the writes
  1, 0   4,708,890,866   40,68%   Acceptable  Have seen one of the writes
  1, 1       5,569,185    0,05%   Acceptable  Have seen both writes

Как видите, в 18,91% случаев от общего количества прогонов мы не увидели ни одной записи. Стало страшно? Читайте далее, чтобы не попасть в такую ситуацию.



Введение: JMM

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

Мы поняли, что as-if-serial семантики недостаточно для многопоточных программ. Почему же не распространить as-if-serial гарантию на всю программу и ядра процессора? Ответ простой — это сильно ударило бы по производительности программ или процессора.

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

Более надежное решение — это создание так называемой модели памяти (memory model), которая строго описывает как потоки взаимодействуют между собой через память (memory ordering). Модель памяти делает легальными многие оптимизации компилятора, JVM и процессора, но в то же время закрепляет условия, при которых программа будет вести себя корректно в многопоточной среде. Таким образом, модель памяти:


  • Разрешает выполнение различных оптимизаций компилятора, JVM или процессора
  • Строго закрепляет условия, при которых программа считается правильно синхронизированной, и закрепляет поведение правильно синхронизированных программ
  • Описывает отношение между высокоуровневым кодом и памятью
  • Является trade-off между строгостью исполнения кода и возможными оптимизациями

Так вот, Java имеет свою модель памяти под названием Java Memory Model (JMM). По умолчанию JMM разрешает переупорядочивание действий и не гарантирует видимости изменений. Однако при выполнении определенных условий нам гарантируется порядок действий, консистентный с порядком в коде, а также видимость всех изменений. Таким образом, JMM позволяет нам писать программы, которые будут полностью корректно работать среди множества различных имплементаций JDK и микро-архитектур процессоров, в то же время сохраняя преимущества оптимизаций.



Введение: Memory Ordering

Для полного понимания модели памяти нам необходимо разобрать такое понятие как Memory Ordering.

Memory Ordering описывает наблюдаемый программой порядок, в котором происходят действия с памятью.

Смотрите: со стороны программы есть только действия записи и чтения из переменных и их порядок в коде. Также со стороны программы кажется, что мы имеем единую память, записи в которую становятся сразу видны другим тредам. Программа не подозревает ни о каких compiler reordering/instructions reordering/caching/register allocation и прочих оптимизациях под капотом. Если по какой-то причине мы наблюдаем результат, не консистентный с порядком в программе, то со стороны программы (высокоуровнево) это выглядит так, что действия c памятью просто были переупорядочены. Другими словами, порядок взаимодействия с памятью (memory order) может отличаться от порядка действий в коде (program order).

Для большего понимания давайте взглянем на уже знакомую нам программу с точки зрения Memory Ordering:

В случае (r1, r2) = (0, 0) мы можем просто сказать, что произошел StoreLoad memory reordering, то есть чтение произошло до записи. Не важно, по какой низкоуровневой причине это случилось, а важно лишь то, что в итоге со стороны программы действия с памятью были выполнены в неконсистентном порядке.

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


  1. Как сохраняется порядок программы при работе с памятью? Если программа не синхронизирована, то разрешены все переупорядочивания
  2. Валиден ли наблюдаемый memory order? Если программа не синхронизирована, то memory order, неконсистентный с program order, тоже может быть валидным

Дать ответ на каждый из вопросов — это и есть задача модели памяти.

В свою очередь, Memory Reordering — это высокоуровневое понятие, которое абстрагирует и обобщает низкоуровневые проблемы, которые мы рассматривали выше. Всего существует 4 типа memory reordering:


  1. LoadLoad: переупорядочивание чтений с другими чтениями. Например, действия r1, r2 могут выполниться в порядке r2, r1
  2. LoadStore: переупорядочивание чтений с записями, идущими позже в порядке программы. Например, действия r, w могут выполниться в порядке w, r
  3. StoreStore: переупорядочивание записей с другими записями. Например, действия w1, w2 могут выполниться в порядке w2, w1
  4. StoreLoad: переупорядочивание записей с чтениями, идущими позже в порядке программы. Например, действия w, r могут выполниться в порядке r, w

В дальнейшем, когда я буду говорить «переупорядочивание» или «reordering», я буду иметь в виду именно Memory Reordering, если не сказано обратное.

Memory Model описывает, какие переупорядочивания возможны. В зависимости от строгости модели памяти подразделяются на следующие виды:


  1. Sequential Consistency: запрещены все переупорядочивания
  2. Relaxed Consistency: разрешены некоторые переупорядочивания
  3. Weak Consistency: разрешены все переупорядочивания

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

В частности, Java Memory Model не дает никаких гарантий, пока не использованы необходимые примитивы синхронизации. И напротив, посмотрите на главу Memory Ordering из Intel Software Developer«s Manual:


  • Reads are not reordered with other reads [запрещает LoadLoad reordering]
  • Writes are not reordered with older reads [запрещает LoadStore reordering]
  • Writes to memory are not reordered with other writes [запрещает StoreStore reordering]
  • Reads may be reordered with older writes to different locations but not with older writes to the same location [разрешает StoreLoad reordering]

Как видите, Intel разрешает только StoreLoad переупорядочивания, а все остальные запрещены. Да, модель памяти x86 достаточно строга, но есть и намного более слабые модели памяти процессоров — например, ARM разрешает все переупорядочивания.

Однако даже если вы пишите программу под x86, вам все равно необходимо считаться с более слабой Java Memory Model, так как последняя разрешает все переупорядочивания на уровне компилятора. Модель памяти языка — прежде всего.



Instructions Ordering vs Memory Ordering

Еще раз закрепим: Instructions Ordering и Memory Ordering — это не одно и то же. Инструкции могут переупорядочиваться под капотом как угодно, но их memory effect должен подчиняться некоторым Memory Ordering правилам, которые гарантируются (или не гарантируются) Memory Model. Наконец, memory ordering — это высокоуровневое понятие, созданное для простоты понимания работы с памятью.

Например, Intel запрещает LoadLoad переупорядочивания, но под капотом все равно делает спекулятивные чтения. Как это возможно? Дело в том, что процессор следит за тем, чтобы результат выполнения инструкций не нарушал memory ordering правил. Если какое-то правило нарушается, то процессор возвращается к более раннему состоянию: результат чтения отбрасывается, а записи не коммитятся в память. Например, из того же Intel Software Developer«s Manual:


The processor-ordering model described in this section is virtually identical to that used by the Pentium and Intel486 processors. The only enhancements in the Pentium 4, Intel Xeon, and P6 family processors are:
  • Added support for speculative reads, while still adhering to the ordering principles above.



Введение: data race

Все случаи, где может произойти Memory Reordering, можно покрыть одним понятием — data race. Гонка возникает тогда, когда с shared данными работает одновременно два или больше тредов, где как минимум один из них пишет и их действия не синхронизированы.

Смотрите более конкретное определение в спеке:


  1. JLS §17.4.1. Shared Variables:
    Memory that can be shared between threads is called shared memory or heap memory.

    All instance fields, static fields, and array elements are stored in heap memory. In this chapter, we use the term variable to refer to both fields and array elements.

    Two accesses to (reads of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write.

  2. JLS §17.4.5. Happens-before Order:
    When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race.

Для действий в гонке не гарантируется никакого консистентного результата (порядка) — от запуска к запуску может быть совершенно разный результат операций.

Как же нам добиться полной корректности многопоточной программы? Давайте обратимся за ответом снова к спеке — JLS §17.4.3. Programs and Program Order:


A set of actions is sequentially consistent if all actions occur in a total order (the execution order) that is consistent with program order, and furthermore, each read r of a variable v sees the value written by the write w to v such that:
  • w comes before r in the execution order, and
  • there is no other write w' such that w comes before w' and w' comes before r in the execution order.
    Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program. Within a sequentially consistent execution, there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread.

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

Таак, sequential consistency, где-то мы это уже слышали… Ах да, SC запрещает все Memory Reordering! Это звучит как то, что нам нужно. Идем далее: чтобы добиться sequential consistency, необходимо избавиться от всех data race в программе. Звучит просто, но не так просто это сделать. Как вы уже заметили, JMM определяет понятие data race через так называемое happens-before. А это значит, что для написания корректных многопоточных программ нам придется изучить и понять, что такое happens-before.

Ну что ж, поехали!



JMM: Happens-before

Happens-Before — это концепция, которая гарантирует memory ordering, консистентный с порядком в коде. Из спеки (§17.4.5. Happens-before Order):


Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second.

Happens-before определяется как отношение между двумя действиями:


  1. Пусть есть поток T1 и поток T2 (необязательно отличающийся от потока T1), и действия x и y, выполняемые в потоках T1 и T2 соответственно
  2. Если x happens-before y, то во время выполнения y треду T2 должны быть видны все изменения, сделанные в x тредом T1

Если мы свяжем доступ к shared переменной с помощью happens-before, то мы избавимся от data race, а значит избавимся и от memory reordering.

Давайте сразу проясним один момент: нет, happens-before не означает, что инструкции будут действительно выполняться в таком порядке. Если переупорядочивание инструкций все равно приводит к консистентному результату, то такое переупорядочивание инструкций не запрещено. JLS:


It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

Далее мы рассмотрим все действия, для которых JMM гарантирует отношение happens-before.


[Happens-Before] Same thread actions

Если действие x идет перед y в коде программы и эти действия происходят в одном и том же треде, то x happens-before y:


If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).

Это формальное определение as-if-serial семантики, которую я уже упоминал в начале статьи: если действие A идет перед действием B в порядке программы, то B гарантированно увидит все изменения, которые должны быть сделаны в A.

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

Для этого треда гарантируется, что x = 1 happens-before r1 = y. Однако эти действия никак не связаны: запись в x не влияет на чтение y. Другими словами, на чтении y нам не нужно видеть изменений, сделанных при записи в x. Поэтому даже если инструкции будут переупорядочены, то happens-before между этими действиями не будет нарушено.

Сравните:

В такой программе действия связаны — на записи в y нам необходимо наблюдать запись в x. Именно в данном случае happens-before запрещает переупорядочивание инструкций, гарантируя, что при записи в y мы увидим результат записи в x.


[Happens-Before] Monitor lock

Освобождение монитора happens-before каждым последующим захватом того же самого монитора.


An unlock action on monitor m happens-before all subsequent lock actions on m


[Happens-Before] Volatile

Запись в volatile переменную happens-before каждым последующим чтением той же самой переменной.


A write to a volatile variable v happens-before all subsequent reads of v by any thread


[Happens-Before] Final thread action

Финальное действие в треде T1 happens-before любым действием в треде T2, которое обнаруживает, что тред T1 завершен.


The final action in a thread T1 happens-before any action in another thread T2 that detects that T1 has terminated.

Это приводит нас к таким happens-before:


  • Финальное действие в T1 happens-before завершением вызова T1.join() в T2
  • Финальное действие в T1 happens-before завершением вызова T1.isAlive() в T2 (если вызов возвращает false)


[Happens-before] Thread start action

Действие запуска треда (Thread.start()) happens-before первым действием в этом треде.


An action that starts a thread happens-before the first action in the thread it starts.


[Happens-before] Thread interrupt action

Если тред T1 прерывает тред T2, то интеррапт happens-before обнаружением интеррапта. Обнаружить интеррапт можно или по исключению InterruptedException, или с помощью вызова Thread.interrupted/Thread.isInterrupted.


If thread T1 interrupts thread T2, the interrupt by T1 happens-before any point where any other thread (including T2) determines that T2 has been interrupted (by having an InterruptedException thrown or by invoking Thread.interrupted or Thread.isInterrupted).


[Happens-Before] Default initialization

Дефолтная инициализация (0, false или null) при создании переменной happens-before любыми другими действиями в треде.


The write of the default value (zero, false, or null) to each variable happens-before the first action in every thread.

Although it may seem a little strange to write a default value to a variable before the object containing the variable is allocated, conceptually every object is created at the start of the program with its default initialized values.


Happens-before transitivity

Важно отметить, что отношение happens-before является транзитивным. То есть, если hb(x,y) и hb(y,z), то hb(x,z).

Это приводит нас к одному очень важному и интересному наблюдению. Мы знаем, что два последовательных действия в одном и том же треде связаны с помощью happens-before (same thread actions). Тогда если действие A в одном треде связано отношением happens-before с действием B в другом треде, то благодаря транзитивности второму треду во время и после выполнения действия B будут видны все изменения, сделанные первым тредом до и во время выполнения действия A.

Еще раз: если есть последовательные действия [A1, A2] в первом треде, последовательные действия [B1, B2] во втором треде, и hb(A2, B1), то hb(A1, B1), hb(A1, B2) и hb(A2, B2), потому что:


  1. Для последовательных действий в треде гарантируется happens-before: hb(A1, A2), hb(B1, B2)
  2. happens-before транзитивен: если hb(A1, A2) (same thread), hb(A2, B1) (hb), hb(B1, B2) (same thread), то hb(A1, B1), hb(A1, B2) и hb(A2, B2)

Вот как мы можем применить это знание:


  • Не только освобождение монитора, но и все действия до освобождения будут видны другому треду после захвата этого же монитора
  • Не только запись в volatile поле, но и все действия до записи будут видны другому треду после чтения этого же поля
  • Не только финальное действие, но и все предыдущие действия треда T1 будут видны другому треду после завершения T1.join()
  • … не будем продолжать — идея понятна

Давайте с учетом этой информации запишем более полное определение happens-before:


  1. Пусть есть поток T1 и поток T2 (необязательно отличающийся от потока T1), и действия x и y, выполняющиеся в потоках T1 и T2 соответственно
  2. Если x happens-before y, то во время и после выполнения y должны быть видны все изменения, сделанные до и во время выполнения x



Happens-before: Practice

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

public class MemoryReorderingExample {
    private int x;
    private boolean initialized = false;

    public void writer() {
        x = 5; /* W1 */
        initialized = true; /* W2 */
    }

    public void reader() {
        boolean r1 = initialized; /* R1 */
        if (r1) {
            int r2 = x; /* R2, may read default value (0) */
        }
    }
}

Можно подумать, что если мы прочитали значение true на R1, то прочитаем и значение 5 на R2, так как в порядке программы запись в x идет перед записью в initialized. Но на самом деле мы можем наблюдать значение по умолчанию (0) при чтении x по следующим причинам:


  1. Instructions reordering (½) — записи W1 и W2 были переставлены местами
  2. Instructions reordering (2/2) — чтения R1 и R2 были переставлены местами
  3. Visibility — запись в x не пропагирована другим ядрам на момент чтения

Другими словами, с точки зрения программы мы говорим, что произошел StoreStore или LoadLoad memory reordering.

Давайте лично убедимся в том, что такие переупорядочивания возможны, написав jcstress тест: 

@JCStressTest
@Description("Triggers memory reordering")
@Outcome(id = "-1", expect = Expect.ACCEPTABLE, desc = "Not initialized yet")
@Outcome(id = "5", expect = Expect.ACCEPTABLE, desc = "Returned correct value")
@Outcome(id = "0", expect = Expect.ACCEPTABLE_INTERESTING, desc = "Initialized but returned default value")
public class JmmReorderingPlainTest {

    @Actor
    public final void actor1(DataHolder dataHolder) {
        dataHolder.writer();
    }

    @Actor
    public final void actor2(DataHolder dataHolder, I_Result r) {
        r.r1 = dataHolder.reader();
    }

    @State
    public static class DataHolder {
        private int x;
        private boolean initialized = false;

        public void writer() {
            x = 5;
            initialized = true;
        }

        public int reader() {
            if (initialized) {
                return x;
            }
            return -1; // return mock value if not initialized
        }
    }
}

Запускаем тест на Intel Core i7–11700 (x86), Windows 10×64, OpenJDK 17 и получаем следующие результаты: 

Results across all configurations:

RESULT        SAMPLES     FREQ       EXPECT  DESCRIPTION
    -1  5,004,050,680   38,73%   Acceptable  Not initialized yet
     0        168,651   <0,01%  Interesting  Initialized but returned default value
     5  7,916,756,029   61,27%   Acceptable  Returned correct value

Как видите, в <0,01% случаев мы получили неконсистентный Memory Order.

Далее мы доведем эту программу до полной корректности, используя happens-before.


Monitor lock

Monitor lock (Intrinsic lock) не только предоставляет happens-before между освобождением и взятием лока, но также является и мьютексом, который позволяет обеспечить эксклюзивный доступ к критической секции (критическая секция — это секция, в которой ведется работа с shared данными). Каждый объект в Java содержит внутри себя такой лок (отсюда и название intrinsic), но его нельзя использовать напрямую — чтобы воспользоваться им, необходимо применить keyword synchronized.

Вот как мы можем исправить приведенную выше программу с помощью монитора: 

public class SynchronizedHappensBefore {
    private final Object lock = new Object();

    private int x;
    private boolean initialized = false;

    public void writer() {
        synchronized (lock) {
            x = 5; /* W1 */
            initialized = true; /* W2 */
        } /* RELEASE */
    }

    public synchronized void reader() {
        synchronized (lock) { /* ACQUIRE */
            boolean r1 = initialized; /* R1 */
            if (r1) {
                int r2 = x; /* R2, guaranteed to see 5 */
            }
        }
    }
}

В данном примере мы используем монитор объекта lock, свойство happens-before которого гарантирует, что после получения монитора reader увидит все изменения, которые сделал writer до освобождения монитора. Следите внимательно: если hb(W1, W2) (same thread), hb(W2, RELEASE) (same thread), hb(RELEASE, ACQUIRE) (monitor lock), hb(ACQUIRE, R1) (same thread), hb(R1, R2) (same thread), то hb(W2, R1) и hb(W1, R2) (transitivity).

Таким образом, если writer освободил монитор и мы захватили его после в reader, то благодаря happens-before нам гарантируется видимость всех действий, которые идут перед освобождением монитора в порядке программы.



Volatile

Volatile предоставляет happens-before гарантию между записью и чтением из volatile переменной. Семантика volatile отличается от монитора только тем, что не устанавливает exclusive access.

Вот так с помощью volatile мы исправляем ту же самую программу: 

public class VolatileHappensBefore {

    private int x;
    private volatile boolean initialized;

    public void writer() {
        x = 5; /* W1 */
        initialized = true; /* W2 */
    }

    public void reader() {
        boolean r1 = initialized; /* R1 */
        if (r1) {
            int r2 = x; /* R2, guaranteed to see 5 */
        }
    }
}

В данном примере мы синхронизируемся на volatile поле initialized, свойство happens-before которого гарантирует, что мы увидим все изменения, которые сделал writer до записи в volatile переменную. Следите внимательно: если hb(W1, W2) (same thread), hb(W2, R1) (volatile), hb(R1, R2) (same thread), то hb(W1, R2) (transitivity).

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

Как видите, пользоваться happens-before достаточно просто. Это все, что вам нужно, чтобы писать свободные от data race и корректные с точки зрения Memory Ordering программы.



Cache Coherence

В самом начале статьи я уже затрагивал тему Cache Coherence, а теперь разберемся в ней подробнее.

Перед тем как идти дальше, рассмотрим устройство кэша на базовом уровне:


  1. Процессор никогда не работает с памятью напрямую — все операции чтения и записи проходят через кэш. Когда процессор хочет загрузить значение из памяти, то он обращается в кэш. Если значения там нет, то кэш сам ответственнен за выгрузку значения из памяти с последующим сохранением в кэше. Когда процессор хочет записать значение в память, то он записывает значение в кэш, который в свою очередь ответственен за сброс значения в память
  2. Кэш состоит из множества «линий» (cache line) фиксированного размера, в которые кладутся значения из памяти. Размер линий варьируется от 16 до 256 байт в зависимости от архитектуры процессора. Кэш сам знает, как мапить адрес линии кэша в адрес памяти
  3. Кэш имеет фиксированный размер, поэтому может хранить ограниченное количество записей. Например, если размер кэша 64 KB, а размер линии кэша 64 байт, то всего кэш может содержать 1024 линии. Поэтому, если при выгрузке нового значения места в кэше не хватает, то из кэша вымещается одно из значений
  4. Большинство современных архитектур процессоров имеют несколько уровней кэша: обычно это L1, L2, и L3. Верхние уровни кэша (L1, L2) являются локальными — каждое ядро процессора имеет собственный, отдельный от других ядер кэш. Кэш на самом нижнем уровне (L3) является общим и шарится между всеми ядрами
    1. Доступ к каждому последующему уровню кэша стоит дороже, чем к предыдущему. Например, доступ к L1 может стоить 3 цикла, L2 — 12 циклов, а к L3 — 38 циклов
    2. Каждый последующий кэш имеет больший размер, чем предыдущий. Например, L1 может иметь размер 80 KB, L2 — 1.25 MB, а L3 — 24 MB

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


Структура кэша

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

Cache Coherence (когерентность кэша) — это механизм процессора, гарантирующий, что любое ядро всегда читает самое актуальное значение из кэша. Данным механизмом обладают многие современные архитектуры процессоров в той или иной имплементации. Самый популярный из протоколов — это MESI протокол и его производные. Например, Intel использует MESIF, а AMD — MOESI протокол.

В MESI протоколе линия кэша может находиться в одном из следующих состояний:


  1. Invalid — линия кэша устарела (содержит неактуальные значения), поэтому из нее нельзя читать
  2. Shared — линия кэша актуальна и эквивалентна памяти. Когда значение из памяти первые загружается в кэш, то линия кэша устанавливается именно в shared состояние. Процессор может только читать из такой линии кэша, но не писать в нее. Если несколько ядер читают один и тот же адрес памяти, то эта линия кэша будет реплицирована сразу в несколько локальных кэшей, отсюда и название «shared»
  3. Exclusive — линия кэша актуальна и эквивалентна памяти. Однако как только одно из ядер процессора переводит линию кэша в это состояние, никакое другое ядро не может держать эту линию кэша у себя, отсюда и название «exclusive». Если одно из ядер процессора переводит линию кэша в exclusive стейт, все остальные ядра должны пометить свою копию как invalid
  4. Modified — линия кэша была изменена (dirty), то есть ядро записало в нее новое значение. Именно в это состояние переходит exclusive линия кэша после записи в нее. Аналогично, только одно из ядер процессора может держать линию кэша в Modified состоянии. Если линия вымещается из кэша, то кэш ответственен за то, чтобы записать новое значение в память перед выгрузкой

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

Когда любое ядро хочет прочитать какой-нибудь адрес в памяти, то алгоритм действ

© Habrahabr.ru