Как применять happens-before на практике и в чем основные преимущества этой концепции

Концепция happens-before как отношение частичного порядка между операциями чтения и записи в многопоточном приложении, вероятно, знакома каждому разработчику на Java. Как минимум такая тема постоянно всплывает на собеседованиях, и теорию, что характерно, все знают прекрасно. Однако на практике процесс переупорядочивания кода сопряжен с различными нюансами. Об этом — техлид IT_ONE Дмитрий Владимиров.

История вопроса

Вкратце вспомним процесс программирования. Код, который мы пишем на Java, превращается в байт-код. Тот попадает в виртуальную машину Java, а она, в свою очередь, производит машинный код, который выполняется на процессоре. В 2005 году на архитектуре x86 впервые появилась многоядерность. Возникла задача — найти оптимальный путь к выполнению кода. Для этого были придуманы различные переупорядочивания, которые можно разделить на три типа:

• Sequential Consistency — запрещены все переупорядочивания (по сути — как написали, так и работает). 
• Relaxed Consistency — разрешены некоторые переупорядочивания. 
• Weak Consistency — разрешены все переупорядочивания.

В этом материале мы рассмотрим первый вариант (тут и далее приведены примеры на псевдокоде, до степени смешения похожем на Java). Возьмем такой пример:

			private int a =1;
private int b =2;
private int r1 =a; // всегда 1
private int r2 =b; // всегда 2
		

Можно ли в этой последовательности совершить перестановку? Да, безусловно:

			private int a =1;
private int r1 =a; // всегда 1
private int b =2;
private int r2 =b; // всегда 2
		

Можно переставить и по-другому, например:

			private int b =2;
private int a =1;
private int r2 =b; // всегда 2
private int r1 =a; // всегда 1
		

Есть ли у нас какие-то гарантии, что результат выполнения программы при этом будет идентичным? Да, но существуют свои ограничения:

• Принцип as-if-serial: означает, что результат выполнения программы неотличим от порядка выполнения «как написано». Но только в одном потоке. 
• Процессор не меняет итоговый результат выполнения — вторая гарантия. Но она актуальна только в рамках одного ядра.
• Принцип cache coherence — означает, что все изменения в кэше ядра видны всем остальным ядрам процессора. Но эти изменения с кэшем происходят через некоторое время. Причин много: от организации доставки изменений до ограничения скорости света (да, это совсем короткий промежуток времени, но и им мы не можем пренебрегать).

Посмотрим на этот фрагмент кода — идиому Dekker lock:

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

Здесь есть две переменные: x и y. В первом методе мы в x записываем 1 и читаем y, а во втором в y записываем 1 и читаем x. Важно, что записи происходят до чтений и перед любым чтением есть запись. Что произойдет, если мы это будем запускать в параллели, в достаточном объеме и в достаточной интенсивности? Мы можем получить на выходе две 1, разные варианты сочетаний 0 и 1 или, чисто теоретически, два 0. Потому что x и y по умолчанию равны 0, и может случиться перестановка операторов, то есть изменение хода выполнения программы.

Через jcstress, фреймворк для нагрузочного тестирования Java-приложения, мы несколько раз запустили по 10 пачек автотестов. В итоге мы получили примерно 16-19% случаев, когда в результате выполнения кода вышло два 0. И менее 1% случаев, когда получились две 1.

Таким образом, этот процесс рандомный. Очевидно, что происходят некие перестановки и правила as-if-serial недостаточно для многопоточности.

Также замечу, что мы получили от 16 до 19 процентов абсолютно непредсказуемых результатов. Признайтесь, хоть кто-то ожидал увидеть два нуля? А они там случаются, и это не единичные случаи.

Конечно, мы можем добавить строгие требования и гарантии: работаем на такой-то архитектуре, запускаемся только так и никак иначе… Но тогда возникают сомнения в ключевом свойстве Java — «write once, run anywhere».

Магия JMM

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

Базовое понятие JMM — Memory Ordering, наблюдаемый программой порядок, в котором происходят действия с памятью. Его наличие критично, так как программа ничего не знает об условиях, в которых ее запускают: о многопоточности, многоядерности, действии кэша, перестановках, оптимизации и так далее. Она может лишь сообщить, как взаимодействует с памятью. Свидетельство тому — описанный выше пример теста, который продемонстрировал, что действия с памятью все-таки были переупорядочены.

Это значит, что мы написали код по одному принципу, а с памятью работаем иначе. Поэтому нужно ввести еще одно понятие — Program Order, порядок действий в коде.

Как сохраняется порядок программы при работе в памяти? И валиден ли наблюдаемый Memory Order?

JMM диктует нам очевидную вещь: если программа не синхронизирована, то разрешены все переупорядочивания. А если всё правильно синхронизировано, то запрещены.

Важно также, что если программа никак не синхронизирована, то порядок взаимодействия с памятью (memory order), который не консистентен с порядком выполнения программы (program order), валиден с точки зрения JMM. Ей всё равно, что мы написали и чего хотим: она работает в рамках своих понятий и может нам всё переставить — просто потому, что у нее есть такая возможность. А если программа правильно синхронизирована, валиден только консистентный порядок.

Вернемся к Dekker lock и перечислим возможные варианты чтения и записи:

			x=1, y=1, r1=y(=1), r2=x(=1)
x=1, y=1, r2=x(=1), r1=y(=1)
x=1, r1=y(=0), y=1, r2=x(=1)
y=1, x=1, r1=y(=1), r2=x(=1)
y=1, x=1, r1=x(=1), r2=y(=1)
y=1, r2=x(=0), x=1, r1=y(=1)
		

Как это читать? Слева направо. На примере первой строки: сначала в х записывается 1, потом в у записывается 1, потом в r1 записывается значение у, которое равно 1, потом в r2 записывается значение х, которое равно 1.

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

			r1=y(=0), r2=x(=0), y=1, x=1
		

Тут описано следующее: сначала в r1 записалось значение у, которое равно 0, потом в r2 записалось значение х, которое тоже было равно 0, а потом уже записали единицы в х и у — произошла перестановка порядка действий.

Итак, Java Memory Model не гарантирует нам консистентного порядка в памяти. Что делать?

Давайте обратимся к определению. Java Memory Model — sequential consistency-data race free (SC-DRF) модель. Это означает, что мы получим консистентность, если избавимся от всех data race — событий, когда с общими данными работают несколько потоков, как минимум один из которых должен писать, и действия потоков не синхронизированы. Но как от них избавиться? Первый вариант — не писать данные, только читать. Вариант надежный, как швейцарские часы. Но более частый — связать все действия с общими данными в synchronization order или в happens-before order.

Synchronization order можно добиться несколькими способами:

• volatile: обещают, что переменная будет синхронизирована сразу после изменения; 
• atomic: использовать некие объекты, обладающие свойством атомарности. Мы не видим промежуточные этапы, а только начало и конец; 
• мониторы.

Итак, вернемся к нашему коду и для исправления добавим в него volatile:

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

Запустив аналогичные пачки автотестов, мы убеждаемся, что результат два 0 не встречается. То же самое мы получим, если удалим volatile в одной из строк (перед x или y).

Happens-before в действии

Определение happens-before в JMM выглядит так: «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. Если одно действие случается до второго, то первое видно и выполняется.

Означает ли happens-before, что инструкции «под капотом» будут выполняться в том же порядке? Разумеется, нет. Это всё равно решают компилятор и процессор.

Например, здесь happens-before есть, и действия не связаны:

			x=1
r1=y
		

Здесь тоже happens-before есть, но действия связаны:

			x=1
y=x+1
		

Какие приемы помогут добиться синхронизации:

• monitor lock, 
• volatile, 
• final thread action: последнее действие в треде выполняется до закрытия треда, 
• thread start action: запуск треда происходит до первой команды в треде, 
• thread interrupt action: сначала выполняется interrupt, и после него выполняется выход из треда, 
• default initialization: действие происходит до первого обращения к параметру. 

И самое главное здесь — свойство транзитивности (transitivity), ради которого весь сыр-бор на собеседованиях и затевается.

Предположим, что у нас есть два действия x и y, связанные отношением happens-before, и два действия y и z, которые тоже связаны отношением happens-before.

Здесь мы получаем транзитивность: действия x и z тоже будут связаны отношением happens-before, даже в параллельных тредах.

В этом и заключается основное практическое преимущество happens-before.

Итог

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