Не работал с CHM, поэтому не знаю что там да как делается.
Если вам нужно просто читать безопасно (в плане видимости) мапу из множества потоков, не изменяя ее, то сойдет любая иммутабельная мапа + safe publication с помощью, static, final или volatile поля
А я еще раз настаиваю: чтение и if condition - это две разные операции. Между чтением и сравниванием есть некоторый интервал времени, поэтому нет разницы, вынесете вы чтение в отдельную переменную или нет. Мы ведь не CAS используем здесь. Посмотрите приведенный выше disasm - там это очень наглядно видно.
И даже если представить, что вы правы, то нас интересует только валидность memory order, а не когда произойдет что-то.
Например, оба этих порядка полностью валидны (с точки зрения Sequential Consistency):
а) сначала прочитает значение переменной 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
}
Да, наверное момент с 0 мог запутать, но я специально хотел сделать акцент на том, что мы можем прочитать 0 только в одном из чтений. В любом случае, уже переписал понятнее.
Насчет LoadStore/StoreLoad - перечитал несколько раз, все равно не понимаю.
К примеру, если взять LoadStore reordering, я даю такое определение:
LoadStore: переупорядочивание чтений с записями, идущими позже в порядке программы. Например, действия r, w могут выполниться в порядке w, r
- Writes are not reordered with older reads [запрещает LoadStore reordering]
Здесь говорится, что записи не будут переупорядочены с чтениями, которые идут ранее (older) в программе. Соответственно, это запрещает LoadStore переупорядочивание, определение которого я дал выше.
И наконец, определение LoadStore барьера:
2. LoadStore
- дает гарантию, что все load операции до барьера произойдут перед store операциями после барьера
Данный барьер запрещает переупорядочивание load операций с store операциями, которые идут позже в программе, а точнее после барьера. Соответственно, этот барьер тожеи запрещает LoadStore переупорядочивание.
он нужен нам только для того, чтобы вернуть что-то, если мы прочитали 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 переупорядочивание, а мы не используем барьер при чтении.
Да, и здесь я должен исправиться. SC никак не связана с eventual visibility, и в частности эта цитата совсем не означает eventual visibility - выше ответил.
Поразмыслил еще раз и понял, что я действительно не прав. Спасибо за такое полезное замечание!
Для начала, укажу на свою ошибку: "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:
Теперь снова вернемся к Dekker алгоритму и рассмотрим его в рамках sequential consistency. Благодаря тому, что в Dekker алгоритме x = 1 PO r1 = y, y = 1 PO r2 = x (PO = program order), то SC соблюдет этот порядок и выполнит чтения только после одной из записей.
Но здесь действительно есть подвох: пропагация записи может занять и год, и два, и вообще не случиться. Со стороны модели главное то, что и чтение не будет выполнено, пока не завершится запись. Но нам то этого не достаточно - мы хотим увидеть эту запись когда-нибудь.
Таким образом, если мы не гарантируем eventual visibility для записей, то это не нарушит sequential consistency модель.
В итоге хочу сказать, что вы правы. Я поискал по всей спеке слова "visibility" и "eventual" и не нашел ни единого подтверждения этому.
Я это вижу так, что в JMM только некоторый набор операций может быть быть выполнен в SC memory order. Если есть другие data race, то для них не гарантируется никакого консистентного порядка, но для связанных happens-before гарантируется. Кажется, на этом делает акцент и спека:
A set of actions is sequentially consistent if all actions occur in a total order
Все-таки 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. Для него порядок выполнения инструкций мог быть таким:
Как видите, порядок выполнения инструкций не совпадает с memory order. Например, read(y) был вызван после write(y), но все равно обнаруживает 0. Это вызвано тем, что write операции занимают некоторое время (что включает в себя и полную пропагацию записи на все локальные кэши процессора).
И наоборот, если бы в теории мы имели strict consistency модель, то операции записи должны были бы завершаться мгновенно. Другими словами, memory order должен быть полностью эквивалентен порядку выполнения инструкций:
Но это не возможно просто физически. Об этом же говорится в 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.
Не обращайте внимания на 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 мог вызвать конструктор после записи адреса в ссылку. То есть, порядок инструкций мог быть такой после переупорядочивания:
В разделе "volatile", код с volatile неверный, так так если поток reader читает в r1, потом поток writer выполняет "initialized = true; /* W2 /", по проверка в reader "if (r1)" не пройдёт, хотя x уже гарантировано имеет значение 5. Уберите ненужное присваивание "boolean r1 = initialized; / R1 */" и сразу пишите "if (initialized)".
Вы не поверите, но это абсолютно одинаковый код :) Чтобы выполнить if-условие, необходимо сначала выполнить чтение. Нет разницы, вынесем мы это чтение в отдельную переменную или нет.
Чтобы подтвердить свои слова, приведу дизассемблер обоих вариантов:
Стандарт нигде не говорит явно, что запись в 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:
Первый случай нас не очень интересует. А вот во втором случае, если мы не пометим переменную как volatile, нам не гарантируется видимости изменений, так как между записью и чтением нет отношения happens-before, а значит и нет sequential consistency. Но если бы мы пометили переменную как volatile, то между этими действиями был бы установлен happens-before, а значит есть sequential consistent, а значит есть и видимость изменений.
Все верно. Другими словами, выполнение программы начинается всегда с какой-либо записи. Если мы прочитали (0, 0), то это означало бы, что выполнение программы началось с чтений, но это противоречит порядку программы.
К сожалению, JMM не дает sequential consistency по умолчанию. Если говорить просто, sequential consistency - это когда мы берем действия всех тредов, как они идут в порядке программы, и просто перемешиваем как угодно.
JMM дает более слабую, "data race free", гарантию - sequential consistency гарантируется только в том случае, если программа не имеет data race. В вышеприведенном примере мы явно имеем data race, так как читаем и пишем в shared переменную из разных тредов без установки отношения happens-before
Рад стараться :)
Не работал с CHM, поэтому не знаю что там да как делается.
Если вам нужно просто читать безопасно (в плане видимости) мапу из множества потоков, не изменяя ее, то сойдет любая иммутабельная мапа + safe publication с помощью, static, final или volatile поля
Рад, что вам понравилось!
А я еще раз настаиваю: чтение и if condition - это две разные операции. Между чтением и сравниванием есть некоторый интервал времени, поэтому нет разницы, вынесете вы чтение в отдельную переменную или нет. Мы ведь не CAS используем здесь. Посмотрите приведенный выше disasm - там это очень наглядно видно.
И даже если представить, что вы правы, то нас интересует только валидность memory order, а не когда произойдет что-то.
Например, оба этих порядка полностью валидны (с точки зрения Sequential Consistency):
Именно так. Выглядит бредово, да) Но к сожалению, независимые чтения в гонке и даже для одной и той же переменной могут быть переставлены как угодно. Вот если бы мы поставили LoadLoad барьер после первого чтения и до второго, так такого бы не случилось. Например:
Кстати, вот еще у Алексея Шипилева есть пункт про этот момент, где мы читаем
nullна повторном чтении - https://shipilev.net/blog/2016/close-encounters-of-jmm-kind/#wishful-benign-is-resilientСильно советую прочитать эту статью целиком - рассказывает о многих интересных фактах о JMM, которые остались за рамками моей статьи.
Да, понял вас. Ошибся, операции действительно могут не выполняться мгновенно, и ваша наивная имплементация выше это доказывает.
Я уже ответил по поводу volatile ниже, в коде все верно)
Но разве
Не говорит как раз это? Например, в моем примере инструкция
read(y)"issued" послеwrite(y), но со стороны программы memory order такой:write(x,1) -> read(y):0 -> write(y, 1) -> read(x):1Да, наверное момент с
0мог запутать, но я специально хотел сделать акцент на том, что мы можем прочитать0только в одном из чтений. В любом случае, уже переписал понятнее.Насчет LoadStore/StoreLoad - перечитал несколько раз, все равно не понимаю.
К примеру, если взять LoadStore reordering, я даю такое определение:
Затем привожу цитату из Intel Software Developer’s Manual (8.2.2 Memory Ordering in P6 and More Recent Processor Families):
Здесь говорится, что записи не будут переупорядочены с чтениями, которые идут ранее (older) в программе. Соответственно, это запрещает LoadStore переупорядочивание, определение которого я дал выше.
И наконец, определение LoadStore барьера:
Данный барьер запрещает переупорядочивание load операций с store операциями, которые идут позже в программе, а точнее после барьера. Соответственно, этот барьер тожеи запрещает LoadStore переупорядочивание.
По поводу объекта
mock:он всегда консистентен, так как static поля инициализируются во время инициализации класса, как это сказано в JLS §12.4. Initialization of Classes and Interfaces. Имплементация инициализации такова, что static поля инициализируются внутри уникального для каждого класса лока, который и дает видимость объекта - см. JLS §12.4.2. Detailed Initialization Procedure
он нужен нам только для того, чтобы вернуть что-то, если мы прочитали
instanceслишком рано (до вызоваwriter)В данном тесте следует смотреть только на работу с переменной
instance.А что такое консистентность в пределах одного потока, это happens-before для действий в потоке? Но если компилятор/процессор переупорядочит эти инструкции, разве нарушится happens-before? Ведь эти чтения никак не аффектят друг друга и между ними нет никакой записи (обычно говорится, что это independent reads). Другими словами, со стороны одного потока кажется, что эта переменная не изменяется, поэтому он может переупорядочить инструкции чтения.
Запомните: чтения в гонке могут быть переупорядочены как угодно и даже для одной и той же переменной.
Именно поэтому, обычно при работе с benign data race мы вычитываем только единожды переменную в локальную, чтобы далее больше не иметь гонки и работать с локальной переменной. Например, если бы мы переписали
readerтак:То никогда не могли бы вернуть
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, там этот момент тоже затрагивается.
Да, и здесь я должен исправиться. SC никак не связана с eventual visibility, и в частности эта цитата совсем не означает eventual visibility - выше ответил.
Поразмыслил еще раз и понял, что я действительно не прав. Спасибо за такое полезное замечание!
Для начала, укажу на свою ошибку: "immediately visible to every thread" надо понимать так, как вы и сказали. То есть, если запись становится видной хотя бы одному треду, то и все остальные треды увидят эту запись.
Далее я буду излагать свой порядок мыслей по порядку, чтобы мы единообразно понимали написанное в спеке.
На уровне SC модели действительно нет никакого времени, а есть лишь порядок и видимость предыдущих действий. Разберем еще раз определение в спеке:
Здесь говорится следующее:
SC говорит, что программа будет выполнена в execution order (он же memory order), который консистентен с program order
SC говорит, что если произошла запись ранее (по порядку) в memory order, то мы увидим эту запись. Но SC не говорит, когда будет видна запись
Sequential consistency можно имплементировать или исполняя все на одном ядре, или исполняя на многоядерном процессоре, но имея блокирующий "switch", который разрешает доступ к памяти только ядру (треду) за раз, причем в program order:
Теперь снова вернемся к Dekker алгоритму и рассмотрим его в рамках sequential consistency. Благодаря тому, что в Dekker алгоритме
x = 1POr1 = y,y = 1POr2 = x(PO = program order), то SC соблюдет этот порядок и выполнит чтения только после одной из записей.Но здесь действительно есть подвох: пропагация записи может занять и год, и два, и вообще не случиться. Со стороны модели главное то, что и чтение не будет выполнено, пока не завершится запись. Но нам то этого не достаточно - мы хотим увидеть эту запись когда-нибудь.
Таким образом, если мы не гарантируем eventual visibility для записей, то это не нарушит sequential consistency модель.
В итоге хочу сказать, что вы правы. Я поискал по всей спеке слова "visibility" и "eventual" и не нашел ни единого подтверждения этому.
Я это вижу так, что в JMM только некоторый набор операций может быть быть выполнен в SC memory order. Если есть другие data race, то для них не гарантируется никакого консистентного порядка, но для связанных happens-before гарантируется. Кажется, на этом делает акцент и спека:
Все-таки Sequential Consistency - это про обеспечение такого memory order, который консистентен с порядком действий всех тредов в программе без привязки к реальному времени выполнения. Вы правы насчет видимости в strict consistency - это действительная самая строгая гарантия, но совсем не нужная в Memory Model.
Как я это понимаю. Возьмем тот же Dekker алгоритм. Вот его program order тредов:
Для него, например, среди множества других валидны такие SC execution order (он же memory order):
Причем мы не знаем, как действительно выполнялись инструкции под капотом, но нам это и не важно.
Однако давайте все-таки заглянем на уровень процессорных инструкций. Возьмем для разбора второй memory order. Для него порядок выполнения инструкций мог быть таким:
Как видите, порядок выполнения инструкций не совпадает с memory order. Например,
read(y)был вызван послеwrite(y), но все равно обнаруживает 0. Это вызвано тем, что write операции занимают некоторое время (что включает в себя и полную пропагацию записи на все локальные кэши процессора).И наоборот, если бы в теории мы имели strict consistency модель, то операции записи должны были бы завершаться мгновенно. Другими словами, memory order должен быть полностью эквивалентен порядку выполнения инструкций:
Но это не возможно просто физически. Об этом же говорится в wiki SC:
Не обращайте внимания на 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 мог вызвать конструктор после записи адреса в ссылку. То есть, порядок инструкций мог быть такой после переупорядочивания:Отредактировал этот момент, надеюсь теперь стало более понятно)
Вы не поверите, но это абсолютно одинаковый код :) Чтобы выполнить if-условие, необходимо сначала выполнить чтение. Нет разницы, вынесем мы это чтение в отдельную переменную или нет.
Чтобы подтвердить свои слова, приведу дизассемблер обоих вариантов:
Ссылка на программу, которую я тестировал (также привел там disasm и для arm64) - https://gist.github.com/blinky-z/bd0143794421878ee10dd4846da59df3
Стандарт нигде не говорит явно, что запись в
volatileпеременную должна стать видимой. Однако этот факт неявно исходит из следующего определения sequential consistency в JMM:Таким образом, если мы пометим переменную как volatile, то нам гарантируется видимость изменений.
Разберем на примере. Обозначим запись в переменную как
write(x, V)и чтение какread(x):V, где V - записываемое или читаемое значение. Пусть где-то в программе мы пишем значение1в shared переменнуюxи где-то читаем эту переменную. Тогда возможны такие execution order:Первый случай нас не очень интересует. А вот во втором случае, если мы не пометим переменную как
volatile, нам не гарантируется видимости изменений, так как между записью и чтением нет отношения happens-before, а значит и нет sequential consistency. Но если бы мы пометили переменную какvolatile, то между этими действиями был бы установлен happens-before, а значит есть sequential consistent, а значит есть и видимость изменений.Все верно. Другими словами, выполнение программы начинается всегда с какой-либо записи. Если мы прочитали (0, 0), то это означало бы, что выполнение программы началось с чтений, но это противоречит порядку программы.
К сожалению, JMM не дает sequential consistency по умолчанию. Если говорить просто, sequential consistency - это когда мы берем действия всех тредов, как они идут в порядке программы, и просто перемешиваем как угодно.
JMM дает более слабую, "data race free", гарантию - sequential consistency гарантируется только в том случае, если программа не имеет data race. В вышеприведенном примере мы явно имеем data race, так как читаем и пишем в shared переменную из разных тредов без установки отношения happens-before