Comments 60
Продвинулся в понимании того, с чем работаю, спасибо!
Вы абсолютно правы, x86 обладает намного более строгими гарантиями по сравнению с ARM/Power. Об этом я также упоминал несколько раз в статье
Кстати, вот яркий пример. Взгляните на данный тест - https://github.com/blinky-z/JmmArticleHabr/blob/main/jcstress/tests/object/JmmReorderingObjectTest.java. Суть его в том, что мы можем прочитать неконсистентное состояние объекта, даже если увидели non-null
ссылку. Он воспроизводится на ARM, но совсем не воспроизводится на x86, т.к. последний запрещает StoreStore
/LoadLoad
reordering.
Так. Тут происходит что-то очень интересное, но не совсем очевидное.
1) Я так понимаю, что в некоторых случаях в ссылку Foo.mock оказывается записан валидный объект ДО того, как констуктор этого Foo.mock отработает. Ноооо... в каком треде происходит выполнение инструкции static final Foo mock = new Foo();
и почему?
2) У вас в строке 90 приписан комментарий return instance; // can return null
Это сбивает с толку - действительно ли в этой строке может вернуться null? Это же нарушает reordering в пределах одного потока. И в ваших тестах нет ни одного подобного случая.
Не обращайте внимания на mock - с ним все нормально. Это лишь заглушка, чтобы вернуть что-то из метода, если
reader
сработал раньше, чемwriter
. В тесте это@Outcome(id = "-1", expect = Expect.ACCEPTABLE, desc = "Object is not seen")
Да, это очень тонкий момент. Суть в том, что может произойти LoadLoad reordering и второе чтение (которое мы возвращаем из метода) произойдет раньше, чем первое, так как они не связаны. К сожалению, у меня его не получилось воспроизвести этот reordering в этом тесте, поэтому я написал отдельный тест - https://github.com/blinky-z/JmmArticleHabr/blob/main/jcstress/tests/object/JmmReorderingObjectSameReadNullTest.java. В нем LoadLoad воспроизводится даже на x86 из-за переупорядочивания инструкций в компиляторе
Ну и последний кейс, который воспроизводится в этом тесте - это обнаружение неконсистентного состония объекта. Можно наивно предположить, что если мы увидели non-null
ссылку на объект, то увидим и внутренние поля объекта, но это не так. Например, writer мог вызвать конструктор после записи адреса в ссылку. То есть, порядок инструкций мог быть такой после переупорядочивания:
| Writer | Reader |
|:---------------------------------------------:|:-----------------:|
| _instance = <new> /* memory allocation */ | |
| instance = _instance /* publish */ | |
| | r1 = instance |
| | r2 = r1.x /* 0 */ |
| _instance.<init> /* constructor invocation */ | |
Эмммм, по-моему вы заблуждаетесь.
В п.2 чтения как раз таки связаны, и они не могут быть поменяны местами, т.к. это ломает консистентность в пределах одного потока. Точнее, сами чтения-то не связаны, а вот чтение + последующая return - очень даже связаны. Если в строке 87 instance == null
выполняется, инструкция return instance;
не может быть выполнена, ибо они в одном потоке.
А вот в процедуре создания объекта mock как раз таки возможна та самая перестановка, о которой я говорю в своем пункте 1, а вы - в своем последнем абзаце, когда вызов конструктора и присваивание ссылки на созданный объект меняются местами. В этом случае (очевидно предположить, что инициализация статической переменной mock случается в каком-то третьем потоке [утверждение требует проверки - ред.]) в строке 88 может быть возвращен "недозаполненный" объект mock, который триггерит @Outcome(id = "0", expect = Expect.ACCEPTABLE_INTERESTING, desc = "Object's data is null")
Подумал еще раз и понял, что ситуацию с перестановкой местами вызова конструктора и присваивания ссылки мы также можем видеть и для instance = new Foo();
в строке 83. В этом случае строка 90 return instance;
тоже может возвращать недозаполненный объект и триггерить outcome 0.
Но возвращать null строка 90 все равно не может
Подумал третий раз и увидел, что в тех случаях, когда мы возвращаем объект mock, мы не делаем проверок на его содержимое и всегда возвращаем -1, так что моя гипотеза в п.1 скорее всего неактуальна (хотя стоило бы проверить на всякий случай)
По поводу объекта mock
:
он всегда консистентен, так как static поля инициализируются во время инициализации класса, как это сказано в JLS §12.4. Initialization of Classes and Interfaces. Имплементация инициализации такова, что static поля инициализируются внутри уникального для каждого класса лока, который и дает видимость объекта - см. JLS §12.4.2. Detailed Initialization Procedure
он нужен нам только для того, чтобы вернуть что-то, если мы прочитали
instance
слишком рано (до вызоваwriter
)
В данном тесте следует смотреть только на работу с переменной instance
.
В п.2 чтения как раз таки связаны, и они не могут быть поменяны местами, т.к. это ломает консистентность в пределах одного потока. Точнее, сами чтения-то не связаны, а вот чтение + последующая return - очень даже связаны. Если в строке 87
instance == null
выполняется, инструкцияreturn instance;
не может быть выполнена, ибо они в одном потоке.
А что такое консистентность в пределах одного потока, это happens-before для действий в потоке? Но если компилятор/процессор переупорядочит эти инструкции, разве нарушится happens-before? Ведь эти чтения никак не аффектят друг друга и между ними нет никакой записи (обычно говорится, что это independent reads). Другими словами, со стороны одного потока кажется, что эта переменная не изменяется, поэтому он может переупорядочить инструкции чтения.
Запомните: чтения в гонке могут быть переупорядочены как угодно и даже для одной и той же переменной.
Именно поэтому, обычно при работе с benign data race мы вычитываем только единожды переменную в локальную, чтобы далее больше не иметь гонки и работать с локальной переменной. Например, если бы мы переписали reader
так:
public Foo cachingReader() {
Foo local = instance;
if (local == null) {
return Foo.mock; // return mock value if not initialized
}
return local; // can not return null
}
То никогда не могли бы вернуть null
.
Да, я не смог воспроизвести этот случай в этом тесте, но это все равно возможно хотя бы потому, что некоторые микроархитектуры как ARM разрешают LoadLoad переупорядочивание, а мы не используем барьер при чтении.
Конечно, не надо верить мне на слово, поэтому посмотрите на этот тест - https://github.com/blinky-z/JmmArticleHabr/blob/main/jcstress/tests/object/JmmReorderingObjectSameReadNullTest.java. Он воспроизводится даже на x86 (где запрещены LoadLoad переупорядочивания) из-за оптимизаций компилятора.
Также советую прочитать статью Алексея Шипилева Safe Publication and Safe Initialization in Java, там этот момент тоже затрагивается.
Кстати, вот еще у Алексея Шипилева есть пункт про этот момент, где мы читаем null
на повторном чтении - https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-benign-is-resilient
Сильно советую прочитать эту статью целиком - рассказывает о многих интересных фактах о JMM, которые остались за рамками моей статьи.
Конечно, не надо верить мне на слово, поэтому посмотрите на этот тест - https://github.com/blinky-z/JmmArticleHabr/blob/main/jcstress/tests/object/JmmReorderingObjectSameReadNullTest.java. Он воспроизводится даже на x86 (где запрещены LoadLoad переупорядочивания) из-за оптимизаций компилятора.
С этим тестом как раз все понятно, там чтения и потенциальная возможность/целесообразность их переупорядочивания вполне очевидна.
С п.2 все не так очевидно. Хотя, я, кажется, начинаю понимать, что вы имеете в виду.
Теоретически, можно предположить, что скомпилированный код
а) сначала прочитает значение переменной instance для использования в строке 90 return instance;
В этот момент может прочитаться null
б) позднее еще раз прочитает значение переменной instance для использования в строке 87 if (instance == null)
, и в этот момент прочитается не-null
Так получается?
Теоретически, вроде бы, действительно я не вижу противоречия упомянутым правилам happens-before при таком раскладе. Но выглядит как-то совсем бредово...
а) сначала прочитает значение переменной instance для использования в строке 90
return instance;
В этот момент может прочитаться nullб) позднее еще раз прочитает значение переменной instance для использования в строке 87
if (instance == null)
, и в этот момент прочитается не-nullТак получается?
Именно так. Выглядит бредово, да) Но к сожалению, независимые чтения в гонке и даже для одной и той же переменной могут быть переставлены как угодно. Вот если бы мы поставили LoadLoad барьер после первого чтения и до второго, так такого бы не случилось. Например:
public Foo reader() {
if (instance == null) {
return Foo.mock; // return mock value if not initialized
}
VarHandle.loadLoadFence();
return instance; // can return null
}
Кстати, вот яркий пример. Взгляните на данный тест - https://github.com/blinky-z/JmmArticleHabr/blob/main/jcstress/tests/object/JmmReorderingObjectTest.java. Суть его в том, что мы можем прочитать неконсистентное состояние объекта, даже если увидели non-null
ссылку. Он воспроизводится на ARM, но совсем не воспроизводится на x86, т.к. последний запрещает StoreStore
/LoadLoad
reordering.
Заметил несколько фактических ошибок, некоторые существенные, например, при синхронизации через volatile.
Укажите, пожалуйста, на ошибки. Буду только рад поправить и сделать материал лучше
Проанализируем программу: если в первом треде мы видим
0
при чтенииy
, то запись вx
точно произошла
Не 0, а 1. И далее во всем абзаце.
Writes are not reordered with older reads [запрещает LoadStore reordering]
Не LoadStore, а StoreLoad.
Reads may be reordered with older writes to different locations but not with older writes to the same location [разрешает StoreLoad reordering]
Не StoreLoad, а LoadStore.
В разделе "volatile", код с volatile неверный, так так если поток reader читает в r1, потом поток writer выполняет "initialized = true; /* W2 */", по проверка в reader "if (r1)" не пройдёт, хотя x уже гарантировано имеет значение 5. Уберите ненужное присваивание "boolean r1 = initialized; /* R1 */" и сразу пишите "if (initialized)".
Дальше не читал ещё :)
Не 0, а 1. И далее во всем абзаце.
Нет, я говорю именно про ситуацию, когда читаем 0. Давайте посмотрим еще раз на пример:
private int x;
private int y;
public void T1() {
x = 1; // W1
int r1 = y; // R1
}
public void T2() {
y = 1; // W2
int r2 = x; // R2
}
Если мы прочитали на R1 любое значение (хоть 0, хоть 1, но нас интересует именно 0), то запись W1 точно произошла, а значит на чтении R2 мы должны будем увидеть 1
. Аналогично рассуждаем и о втором треде. Таким образом, мы можем увидеть 0
только на одном из чтений, но никак не на обоих, так как это просто невозможно если смотреть с точки зрения порядка в программе, ведь хотя бы одна запись должна была произойти.
Другими словами, выполнение программы начинается или с записи x
, или с записи y
. Если мы прочитали (0, 0), то это означало бы, что выполнение программы началось с чтений, но ведь они идут после записей? Однако это происходит по причине memory reordering, так как Java не дает sequential consistency по умолчанию.
Не LoadStore, а StoreLoad.
Нет, это называется именно LoadStore
(читать так: loads can be reordered after stores).
Не StoreLoad, а LoadStore.
И здесь тоже именно StoreLoad
(читать так: stores can be reordered after loads). Кстати, причина наличия такого переупорядочивания в x86 - это Store Buffer.
Насчёт 0 или 1 - именно, что любое число, а не только 0, как написано (было написано) в статье.
Насчёт LoadStrore и StoreLoad, ваши же определения выше противоречат им. Или поменяйте определения, или поменяйте тут. То есть, вы смешиваете memory reordering и memory barrier.
Да, наверное момент с 0
мог запутать, но я специально хотел сделать акцент на том, что мы можем прочитать 0
только в одном из чтений. В любом случае, уже переписал понятнее.
Насчет LoadStore/StoreLoad - перечитал несколько раз, все равно не понимаю.
К примеру, если взять LoadStore reordering, я даю такое определение:
LoadStore: переупорядочивание чтений с записями, идущими позже в порядке программы. Например, действия
r, w
могут выполниться в порядкеw, r
Затем привожу цитату из Intel Software Developer’s Manual (8.2.2 Memory Ordering in P6 and More Recent Processor Families):
- Writes are not reordered with older reads [запрещает LoadStore reordering]
Здесь говорится, что записи не будут переупорядочены с чтениями, которые идут ранее (older) в программе. Соответственно, это запрещает LoadStore переупорядочивание, определение которого я дал выше.
И наконец, определение LoadStore барьера:
2. LoadStore
- дает гарантию, что все load операции до барьера произойдут перед store операциями после барьера
Данный барьер запрещает переупорядочивание load операций с store операциями, которые идут позже в программе, а точнее после барьера. Соответственно, этот барьер тожеи запрещает LoadStore переупорядочивание.
Проанализируем программу: если в первом треде мы видим 0 при чтении y, то запись в x точно произошла
Не 0, а 1. И далее во всем абзаце.
Код в статье правильный: вот этот же пример в JCStress.
Возможно, из описания не совсем понятно, что этот код делает.
Можно попробовать объяснить вот так:
Код:
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;
}
}
Тут T1()
выполняется в первом потоке, T2()
- во втором.
Обычно люди, незнакомые с JMM, полагают, что в таком случае действия в каждом потоке выполняются последовательно.
И в итоге, они считают, что есть всего 4 варианта того, в каком порядке выполняются действия потоков:
x = y = 0;
T1 | T2 T1 | T2
-------------------------- --------------------------
x = 1; | x = 1; |
int r1 = y; | | y = 1;
| y = 1; int r1 = y; |
| int r2 = x; | int r2 = x;
T1 | T2 T1 | T2
-------------------------- --------------------------
| y = 1; x = 1; |
x = 1; | | y = 1;
int r1 = y; | | int r2 = x;
| int r2 = x; int r1 = y; |
Как видите, во всех четырёх случаях первым всегда идёт либо x = 1;
либо y = 1;
, а значит результата (r1==0, r2==2)
быть не должно.
А в JMM такой результат допустим.
Значит описанный выше "интуитивный" подход не работает в java, и программистам нужно разбираться с happens-before
, volatile
и остальной JMM.
Все верно. Другими словами, выполнение программы начинается всегда с какой-либо записи. Если мы прочитали (0, 0), то это означало бы, что выполнение программы началось с чтений, но это противоречит порядку программы.
К сожалению, JMM не дает sequential consistency по умолчанию. Если говорить просто, sequential consistency - это когда мы берем действия всех тредов, как они идут в порядке программы, и просто перемешиваем как угодно.
JMM дает более слабую, "data race free", гарантию - sequential consistency гарантируется только в том случае, если программа не имеет data race. В вышеприведенном примере мы явно имеем data race, так как читаем и пишем в shared переменную из разных тредов без установки отношения happens-before
Отредактировал этот момент, надеюсь теперь стало более понятно)
В коментарии выше ошибка: вариантов 6, а не четыре.
x = y = 0;
T1 | T2 T1 | T2
-------------------------- --------------------------
x = 1; | | y = 1;
int r1 = y; | | int r2 = x;
| y = 1; x = 1; |
| int r2 = x; int r1 = y; |
T1 | T2 T1 | T2
-------------------------- --------------------------
x = 1; | | y = 1;
| y = 1; x = 1; |
int r1 = y; | | int r2 = x;
| int r2 = x; int r1 = y; |
T1 | T2 T1 | T2
-------------------------- --------------------------
x = 1; | | y = 1;
| y = 1; x = 1; |
| int r2 = x; int r1 = y; |
int r1 = y; | | int r2 = x;
В разделе "volatile", код с volatile неверный, так так если поток reader читает в r1, потом поток writer выполняет "initialized = true; /* W2 /", по проверка в reader "if (r1)" не пройдёт, хотя x уже гарантировано имеет значение 5. Уберите ненужное присваивание "boolean r1 = initialized; / R1 */" и сразу пишите "if (initialized)".
Вы не поверите, но это абсолютно одинаковый код :) Чтобы выполнить if-условие, необходимо сначала выполнить чтение. Нет разницы, вынесем мы это чтение в отдельную переменную или нет.
Чтобы подтвердить свои слова, приведу дизассемблер обоих вариантов:
public static void reader1() {
boolean r1 = initialized; /* R1 */
if (r1) {
int r2 = x; /* R2 */
}
/*
x86:
0x000002239b45b5de: movsx esi,BYTE PTR [rsi+0x74] ;*getstatic initialized {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader1@0 (line 14)
0x000002239b45b5e2: cmp esi,0x0
0x000002239b45b5e5: movabs rsi,0x223b7c037e0 ; {metadata(method data for {method} {0x00000223b7c032d8} 'reader1' '()V' in 'jit_disassembly/JmmVolatileConditionRead')}
0x000002239b45b5ef: movabs rdi,0x110
0x000002239b45b5f9: je 0x000002239b45b609
0x000002239b45b5ff: movabs rdi,0x120
0x000002239b45b609: mov rbx,QWORD PTR [rsi+rdi*1]
0x000002239b45b60d: lea rbx,[rbx+0x1]
0x000002239b45b611: mov QWORD PTR [rsi+rdi*1],rbx
0x000002239b45b615: je 0x000002239b45b628 ;*ifeq {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader1@5 (line 15)
0x000002239b45b61b: movabs rsi,0x7114bd448 ; {oop(a 'java/lang/Class'{0x00000007114bd448} = 'jit_disassembly/JmmVolatileConditionRead')}
0x000002239b45b625: mov esi,DWORD PTR [rsi+0x70] ;*getstatic x {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader1@8 (line 16)
*/
}
public static void reader2() {
if (initialized) { /* R1 */
int r2 = x; /* R2 */
}
/*
x86:
0x000002239b45b25e: movsx esi,BYTE PTR [rsi+0x74] ;*getstatic initialized {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader2@0 (line 21)
0x000002239b45b262: cmp esi,0x0
0x000002239b45b265: movabs rsi,0x223b7c03930 ; {metadata(method data for {method} {0x00000223b7c03388} 'reader2' '()V' in 'jit_disassembly/JmmVolatileConditionRead')}
0x000002239b45b26f: movabs rdi,0x110
0x000002239b45b279: je 0x000002239b45b289
0x000002239b45b27f: movabs rdi,0x120
0x000002239b45b289: mov rbx,QWORD PTR [rsi+rdi*1]
0x000002239b45b28d: lea rbx,[rbx+0x1]
0x000002239b45b291: mov QWORD PTR [rsi+rdi*1],rbx
0x000002239b45b295: je 0x000002239b45b2a8 ;*ifeq {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader2@3 (line 21)
0x000002239b45b29b: movabs rsi,0x7114bd448 ; {oop(a 'java/lang/Class'{0x00000007114bd448} = 'jit_disassembly/JmmVolatileConditionRead')}
0x000002239b45b2a5: mov esi,DWORD PTR [rsi+0x70] ;*getstatic x {reexecute=0 rethrow=0 return_oop=0}
; - jit_disassembly.JmmVolatileConditionRead::reader2@6 (line 22)
*/
}
Ссылка на программу, которую я тестировал (также привел там disasm и для arm64) - https://gist.github.com/blinky-z/bd0143794421878ee10dd4846da59df3
Чтобы выполнить if-условие, необходимо сначала выполнить чтение. Нет разницы, вынесем мы это чтение в отдельную переменную или нет.
Если между этим чтением и if переменная initialized сменит значение, то if пойдёт по уже неправильной ветке. Ну очевидно же.
А я еще раз настаиваю: чтение и if condition - это две разные операции. Между чтением и сравниванием есть некоторый интервал времени, поэтому нет разницы, вынесете вы чтение в отдельную переменную или нет. Мы ведь не CAS используем здесь. Посмотрите приведенный выше disasm - там это очень наглядно видно.
И даже если представить, что вы правы, то нас интересует только валидность memory order, а не когда произойдет что-то.
Например, оба этих порядка полностью валидны (с точки зрения Sequential Consistency):
write(x, true) -> write(initialized, true) -> read(initialized):true -> read(x): 5
write(x, true) -> read(initialized):false -> write(initialized, true)
Раздел Happens-before: Practice
Instructions reordering (2/2) — чтения R1 и R2 были переставлены местами
и чуть ниже
hb(R1, R2)
(same thread)
Но ведь данные чтения никак не аффектят друг друга, а поэтому их можно переупорядочить :) Перечитайте раздел [Happens-Before] Same thread actions - там написано о том, как переупорядочивание действий в треде не нарушает happens-before.
Только в том случае, если связать с помощью happens-before действия в разных тредах, happens-before будет гарантировать, что инструкция чтения R2
произойдет только после R1
(запретит LoadLoad memory reordering), а инструкция записи W1
произойдет до W2
(запретит StoreStore memory reordering), иначе happens-before в цепочке действий (W1,W2,R1,R2)
было бы нарушено.
Другими словами, пока мы не свяжем W2
и R1
с помощью happens-before (что дает нам volatile), то не будет happens-before между наборами действий (W1,W2)
и (R1,R2)
.
Прекрасная статья.
У Вас действительно хорошо получается объяснять понятным языком: читая статью я несколько раз ловил себя на мысли, что сам я не смог бы объяснить данный момент проще и понятней.
В качестве конструктивной критики: боюсь что таких слов "имплементация" и "консистентность" в русском языке нет. Я так понимаю это implementation и consistency написанные русскими буквами.
Это не критично, но всё-таки немного режет глаз.
Как вариант, эти слова можно заменить на "реализация" и "согласованность/соответсвие", или даже просто использовать английские термины.
Также я заметил вот такую ошибку в тексте:
Shared — линия кэша актуальна и эквивалентна памяти. Когда значение из памяти первые загружается в кэш, то линия кэша устанавливается именно в shared состояние.
Судя по Table 1.1 в статье о MESI на вики, в этом случае состояние будет Exclusive.
Да, это про implementation и consistency. Лично я придерживаюсь мнения, что говорить "имплементация" - наоборот корректнее, чем "реализация". Та же вики под Реализацией имеет в виду что-то другому, чем Имплементация. Не знаю, насколько валидно говорить "консистентность" (наверное правильнее "согласованность"?), но это понятие используется повсеместно и если всем все понятно, то проблемы нет :)
Насчет перевода в Exclusive состояние еще уточню, но кажется вы правы, спасибо!
Понятно.
Я, почему-то, наоборот, слово "имплементация" встречал в основном в политическо-юридическом контексте.
А в программировании и в IT - я в основном встречал "реализация": "реализация алгоритма на языке java", "реализация наследуемых абстрактных методов в дочернем классе" и т.п.
Кстати, определение термина имплементация в википедии использует термин "реализация":
Имплементация (программирование) — программная или аппаратная реализация какого-либо протокола, алгоритма, технологии
Вообще-то имплементация есть в русском языке. И до информатики она применялась в юриспруденции с тем же самым смыслом, например "имплементация закона".
Комментарий удалён
Итак, ядра действительно всегда видят актуальное значение, но только кроме короткого временного окна после записи. Другими словами, нам гарантируется eventual visibility изменений.
Исправить этот пример можно пометив переменную как
volatile
— только в этом случае нам гарантируется eventual visibility изменений.
Любопытный факт: cтрого говоря, в java нет гарантий того, что volatile
запись должна в течение какого-то времени стать видимой другим потокам.
В итоге формально допустима volatile
запись, которая никогда не станет видимой другим потокам.
Более того, допустима реализация JVM, в которой все записи никогда не видны другим потокам.
Конечно же, java-программисты надеются, что в используемых на практике реализациях JVM таких "оптимизаций" нет.
А вот в c++ eventual visibility гарантируется:
18 An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.
11 Implementations should make atomic stores visible to atomic loads within a reasonable amount of time.
Стандарт нигде не говорит явно, что запись в volatile
переменную должна стать видимой. Однако этот факт неявно исходит из следующего определения sequential consistency в JMM:
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.
Таким образом, если мы пометим переменную как volatile, то нам гарантируется видимость изменений.
Разберем на примере. Обозначим запись в переменную как write(x, V)
и чтение как read(x):V
, где V - записываемое или читаемое значение. Пусть где-то в программе мы пишем значение 1
в shared переменную x
и где-то читаем эту переменную. Тогда возможны такие execution order:
...read(x):0 -> ... -> write(x, 1)
...write(x, 1) -> ... -> read(x):?
Первый случай нас не очень интересует. А вот во втором случае, если мы не пометим переменную как volatile
, нам не гарантируется видимости изменений, так как между записью и чтением нет отношения happens-before, а значит и нет sequential consistency. Но если бы мы пометили переменную как volatile
, то между этими действиями был бы установлен happens-before, а значит есть sequential consistent, а значит есть и видимость изменений.
По-моему, immediately visible to every thread тут означает, что чтение переменной всегда возвращает последнюю с точки зрения execution order запись в эту переменную.
При этом этот так называемый "execution order" при Sequential consistency не подразумевает привязки к реальному времени исполнения инструкций.
И поэтому я не думаю, что приведённая цитата гарантирует, что volatile
записи обязательно становятся видимыми в других потокам.
Почему я так считаю:
Sequential consistency (SC) (в отличии от Strict consistency) обычно не подразумевает, что действия становятся видимы мгновенно.
При этом в SC:есть общий для всех потоков порядок чтений и записей (т.н. execution order)
program order чтений и записей каждого потока соблюдается в execution order
упорядоченность операций по реальному времени исполнения в execution order соблюдать не требуется
Пример.
Реальное время выполнения инструкций процессором:T1 T2 | ------------ |t=0 x=1; | | | |t=10ns y=2; | | | |t=20ns | x=3; V
Возможные execution order:
x=1 -> y=2 -> x=3
x=1 -> x=3 -> y=2
x=3 -> x=1 -> y=2
Опять же, насколько я понимаю, в SC не ограничена задержка, с которой запись в одном потоке становится видимой другим потокам.
И поэтому, например,x=3
из T2 может стать видимым в T1, допустим, через год - и это не нарушит SC.в остальной JMM реальное время не соблюдается и никакого immediately visible to every thread нет.
В частности, в статье выше упоминалось про happens-before:
Давайте сразу проясним один момент: нет, happens-before не означает, что инструкции будут действительно выполняться в таком порядке. Если переупорядочивание инструкций все равно приводит к консистентному результату, то такое переупорядочивание инструкций не запрещено.
Если инструкции переупорядочиваются, значит в случае с happens-before привязки к реальному времени исполнения инструкций нет — важно лишь чтобы результат был таким же.
Логично предположить, что в и случае SC - инструкции внутри, к примеру,
synchronized{}
блоков также разрешено переупорядочивать.
Соответсвенно эти инструкции также не будут выполняться по одной и сразу становиться immediately visible to every thread.Также было бы странно, если бы eventual visibility гарантировалась только для SC (т.е. только для data-race-free программ): ведь самые заоптимизированные по многопоточной производительности алгоритмы (типа содержимого java.util.concurrent) частенько используют всякие хаки типа кода с data race-ами.
Было бы странно, если бы именно таким алгоритмам не гарантировалась eventual visibility.
Все-таки Sequential Consistency - это про обеспечение такого memory order, который консистентен с порядком действий всех тредов в программе без привязки к реальному времени выполнения. Вы правы насчет видимости в strict consistency - это действительная самая строгая гарантия, но совсем не нужная в Memory Model.
Как я это понимаю. Возьмем тот же Dekker алгоритм. Вот его program order тредов:
Thread 0 | Thread 1
-------------------
x = 1 | y = 1
r1 = y | r2 = x
Для него, например, среди множества других валидны такие SC execution order (он же memory order):
x = 1
y = 1
r1 = y // 1
r2 = x // 1
------
x = 1
r1 = y // 0
y = 1
r2 = x // 1
Причем мы не знаем, как действительно выполнялись инструкции под капотом, но нам это и не важно.
Однако давайте все-таки заглянем на уровень процессорных инструкций. Возьмем для разбора второй memory order. Для него порядок выполнения инструкций мог быть таким:
CORE 0 : write(x, 1) read(y):0
CORE 0 time: |--------->--------|------->
CORE 1 : write(y, 1) read(x):1
CORE 1 time: --------------|--------------->-----|--------->
time : --------------------------------------------->
Как видите, порядок выполнения инструкций не совпадает с memory order. Например, read(y)
был вызван после write(y)
, но все равно обнаруживает 0. Это вызвано тем, что write операции занимают некоторое время (что включает в себя и полную пропагацию записи на все локальные кэши процессора).
И наоборот, если бы в теории мы имели strict consistency модель, то операции записи должны были бы завершаться мгновенно. Другими словами, memory order должен быть полностью эквивалентен порядку выполнения инструкций:
CORE 0: write(x, 1) -> read(y):1
CORE 1: write(y, 1) -> read(x):1
Но это не возможно просто физически. Об этом же говорится в wiki SC:
The sequential consistency is weaker than strict consistency, which requires a read from a location to return the value of the last write to that location; strict consistency demands that operations be seen in the order in which they were actually issued.
Небольшое замечание по поводу strict consistency.
Вы пишите:
если бы в теории мы имели strict consistency модель, то операции записи должны были бы завершаться мгновенно
...
Но это не возможно просто физически.
И потом приводите такую цитату:
The sequential consistency is weaker than strict consistency, which requires a read from a location to return the value of the last write to that location; strict consistency demands that operations be seen in the order in which they were actually issued.
Но эта цитата не утверждает, что операции должны завершаться мгновенно.
Она утверждает, что, начиная с момента времени, когда операция становится выполненной, она должна стать видимой другим процессорам.
Но при этом выполнение операции вполне может занимать какое-то время.
В Вашем примере если write(x,1)
становится выполненным в момент времени t
, то любой read(x)
начатый позже t
должен возвратить 1
или более позднюю запись.
Пример процессора, которые мог бы реализовать это физически:
с когерентным кэшем без Invalidation Queue и Store Buffer
следующая инструкция начинает выполняться только после того, как выполнилась текущая инструкция
write
становится выполненным когда означение записано в cache lineread
становится выполненным когда значение прочитано из кэша
Но разве
...strict consistency demands that operations be seen in the order in which they were actually issued.
Не говорит как раз это? Например, в моем примере инструкция read(y)
"issued" после write(y)
, но со стороны программы memory order такой:
write(x,1) -> read(y):0 -> write(y, 1) -> read(x):1
Не совсем понятно, что Вы имеете ввиду под "как раз это".
Я так понял, что Вы написали, что у процессора, соответсвующего strict consistency, операции записи должны выполняться мгновенно (в смысле физического времени) и что это невозможно физически.
На мой взгляд, приведённая Вами цитата не требует от процессора мгновенных(в смысле физического времени) операций записи, и что процессор, соответсвующий strict consistency, создать вполне возможно.
Поразмыслил еще раз и понял, что я действительно не прав. Спасибо за такое полезное замечание!
Для начала, укажу на свою ошибку: "immediately visible to every thread" надо понимать так, как вы и сказали. То есть, если запись становится видной хотя бы одному треду, то и все остальные треды увидят эту запись.
Далее я буду излагать свой порядок мыслей по порядку, чтобы мы единообразно понимали написанное в спеке.
На уровне SC модели действительно нет никакого времени, а есть лишь порядок и видимость предыдущих действий. Разберем еще раз определение в спеке:
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.
Здесь говорится следующее:
SC говорит, что программа будет выполнена в execution order (он же memory order), который консистентен с program order
SC говорит, что если произошла запись ранее (по порядку) в memory order, то мы увидим эту запись. Но SC не говорит, когда будет видна запись
Sequential consistency можно имплементировать или исполняя все на одном ядре, или исполняя на многоядерном процессоре, но имея блокирующий "switch", который разрешает доступ к памяти только ядру (треду) за раз, причем в program order:
![](https://habrastorage.org/getpro/habr/upload_files/821/b9d/8cf/821b9d8cf6f233d8ec72084613d455d9.png)
Теперь снова вернемся к Dekker алгоритму и рассмотрим его в рамках sequential consistency. Благодаря тому, что в Dekker алгоритме x = 1
PO r1 = y
, y = 1
PO r2 = x
(PO = program order), то SC соблюдет этот порядок и выполнит чтения только после одной из записей.
Но здесь действительно есть подвох: пропагация записи может занять и год, и два, и вообще не случиться. Со стороны модели главное то, что и чтение не будет выполнено, пока не завершится запись. Но нам то этого не достаточно - мы хотим увидеть эту запись когда-нибудь.
Таким образом, если мы не гарантируем eventual visibility для записей, то это не нарушит sequential consistency модель.
В итоге хочу сказать, что вы правы. Я поискал по всей спеке слова "visibility" и "eventual" и не нашел ни единого подтверждения этому.
Хорошо, что в итоге разобрались.
Похожее обсуждение было недавно на stackoverflow.
Видимо подобные вопросы продолжат возникать у java-программистов и в будущем.
И возможно эта ветка комментариев кому-нибудь из них поможет разобраться.
Кстати, даже если эта цитата действительно означает eventual visibility для volatile
, то это будет работать только в data-race-free программах (ведь java гарантирует Sequential consistency только в таких случаях).
Как мы знаем, программа data-race-free только если в ней вообще нет data race.
В итоге, стоит только добавить в java-приложение какой-нибудь тестовый класс с data race внутри, и гарантия eventual visibility для volatile
исчезает сразу во всех классах нашего приложения.
Кроме того, в String.hashCode()
чтение и запись поля hash
- это data race.
Получается тем, кто в java хочет eventual visibility для volatile
, нельзя использовать строки.
Я это вижу так, что в JMM только некоторый набор операций может быть быть выполнен в SC memory order. Если есть другие data race, то для них не гарантируется никакого консистентного порядка, но для связанных happens-before гарантируется. Кажется, на этом делает акцент и спека:
A set of actions is sequentially consistent if all actions occur in a total order
Очень качественный материал, большое спасибо!
Помню как 5-7+ лет назад читал "what every developer should know about memory", блог Mechanical Sympathy и смотрел видео от Шипелев и Куксенко и пересказы эти видео на хабре.
Но нигде не было такого полного изложения от проблемы до решения, с точки зрения джавы.
Еще раз спасибо!
Всегда интересовал вопрос с публикацией immutable map.
Есть фиксированная map которую я загружаю из файла в начале приложения, а потом много потоком ее читают.
Обычно используют CHM, но можно ли просто взять HashMap (перегрузить модифицируешь методы или завернуть в immutable colletion) и сделать безопасный publish чтобы читатели не брали локи на get как в CHM?
Кажется что если это final map и создается в констукторе то должно работать, но уверености нет.
Спасибо, прекрасная статья!
JMM: Happens-before: практика
volatile
private int x; private boolean initialized = false;
public void writer() {
x = 5; /* W1 /
initialized = true; / W2 */
}
хотел уточнить, вот здесь W1 и W2 сохраняет РО за счет того, что переменная волатильная и это HB (W1, W2)..
я видимо что-то упустил, все же не совсем понятно, каким образом достигается HB (W1, W2), ведь они никак кроме РО не связаны ? получается что в любом месте кода в конце можно поставить волатайл костыль и весь код как-будто обернется synchronized блоком ?!
внутри синхронайзед блока РО также может перемешиваться, но это неважно, т.к. оборачивается тот код, который в целом должен быть логически непротиворечив относительно РО..
а если бы между W1 и W2 были бы еще какие-то операции W3, W4, то они ведь могут перемешиваться типо W1, W3, W4 или W4, W1, W3, для них самих же не должно быть HB, а только HB [W1, W3, W4] (в любом порядке) к W2 ?
может кто в курсе, попытался запускать примеры в jcstress, в частности JmmReorderingPlainTest без/с волатайл переменной, никакой разницы
RESULT SAMPLES FREQ EXPECT DESCRIPTION
-1 165,823,101 26.66% Acceptable Not initialized yet
0 0 0.00% Interesting Initialized but returned default value
5 456,263,043 73.34% Acceptable Returned correct value
может какие-то параметры для запуска нужно выставлять, Interesting всегда 0 ?
Глубокое погружение в Java Memory Model