Интерпретация правила порядка выполнения программы в параллелизме Java

Правило порядка выполнения программы гласит: «Каждое действие в потоке происходит до каждого действия в этом потоке, которое происходит позже в порядке выполнения программы».

1. Я прочитал в другой теме < /a> что действие

  • читает и пишет в переменные
  • блокировки и разблокировки мониторов
  • запуск и присоединение к потокам

Означает ли это, что чтение и запись могут быть изменены по порядку, но чтение и запись не могут изменить порядок с действиями, указанными во 2-й или 3-й строке?

2.Что означает "порядок программы"?

Объяснение с примерами было бы очень полезно.

Дополнительный связанный вопрос

Предположим, у меня есть следующий код:

long tick = System.nanoTime(); //Line1: Note the time
//Block1: some code whose time I wish to measure goes here
long tock = System.nanoTime(); //Line2: Note the time

Во-первых, это однопоточное приложение для простоты. Компилятор замечает, что ему нужно дважды проверить время, а также замечает блок кода, который не имеет зависимости от окружающих строк, отмечающих время, поэтому он видит возможность реорганизации кода, что может привести к тому, что блок 1 не будет окружен вызовами синхронизации. во время фактического выполнения (например, рассмотрите этот порядок Строка1->Строка2->Блок1). Но я как программист вижу зависимость между Line1,2 и Block1. Строка 1 должна непосредственно предшествовать Блоку 1, для завершения Блока 1 требуется конечное время, и сразу же за ним следует Строка 2.

Итак, мой вопрос: правильно ли я измеряю блок?

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

PS: я украл этот код из другого вопроса, который я задал в ТАК недавно.


person Abs    schedule 27.03.2013    source источник
comment
Почему бы вам не нажать Спецификация языка Java?   -  person Marko Topolnik    schedule 27.03.2013
comment
Я настоятельно рекомендую приобрести копию Java Concurrency in Practice от Goetz et al. Хотя он начинает немного стареть, он по-прежнему является чем-то вроде золотого стандарта для ссылок на параллельное программирование. Вам также может быть полезен этот GoogleTalk от Джереми Мэнсона (соавтора самой модели памяти): youtube.com/watch?v=WTVooKLLVT8   -  person Andrew Bissell    schedule 27.03.2013
comment
@Andrew: На самом деле, я видел видео Джереми Мэнсона, и поэтому мне было любопытно узнать больше о модели памяти. Глядя на пример в его блоге здесь мне кажется, что его пример фактически нарушает правило порядка выполнения программы, поскольку он перемещает переменные x и y вокруг других блокировок монитора и доступа к переменным. Почему это правило не нарушается? Если он прав, что я упускаю? Он также кратко рассказывает о концепции тараканьего мотеля в своем видео, так что я уверен, что он прав.   -  person Abs    schedule 27.03.2013
comment
@wagaboy Я добавил к своему ответу еще немного обсуждения порядка программ. Правило PO менее строгое, чем вы думаете; это не означает, что каждое действие в потоке должно выполняться последовательно, а скорее то, что результаты всех действий в этом потоке должны быть такими же, как если бы они выполнялись по порядку. . Это известно как семантика внутрипотоковой как-будто-последовательной. Если мы удалим блок synchronized из примера Мэнсона (не относящийся к порядку однопоточной программы), то, поскольку ни одна из операций не влияет ни на одну из других, их можно свободно переупорядочивать.   -  person Andrew Bissell    schedule 27.03.2013


Ответы (5)


Вероятно, это помогает объяснить, почему такое правило вообще существует.

Java — это процедурный язык. т.е. вы говорите Java, как сделать что-то для вас. Если Java выполнит ваши инструкции не в том порядке, в котором вы написали, это, очевидно, не сработает. Например. в приведенном ниже примере, если Java сделает 2 -> 1 -> 3, то тушеное мясо будет испорчено.

1. Take lid off
2. Pour salt in
3. Cook for 3 hours

Итак, почему правило не говорит просто: «Java выполняет то, что вы написали, в том порядке, в котором вы написали»? В двух словах, потому что Java умна. Возьмем следующий пример:

1. Take eggs out of the freezer
2. Take lid off
3. Take milk out of the freezer
4. Pour egg and milk in
5. Cook for 3 hours

Если бы Java был таким же, как я, он просто выполнял бы его по порядку. Однако Java достаточно умен, чтобы понять, что он более эффективен И что конечный результат будет таким же, если он сделает 1 -> 3 -> 2 -> 4 -> 5 (вам не нужно снова идти в морозильник, и рецепт не меняется).

Таким образом, правило «Каждое действие в потоке происходит до каждого действия в этом потоке, которое происходит позже в порядке выполнения программы» означает: «В одном потоке ваша программа будет работать как если бы он был выполнен именно в том порядке, в котором вы его написали. Мы можем изменить порядок за кулисами, но мы гарантируем, что ничто из этого не изменит вывод.

Все идет нормально. Почему это не делает то же самое в нескольких потоках? В многопоточном программировании Java недостаточно умен, чтобы делать это автоматически. Это будет для некоторых операций (например, объединение потоков, запуск потоков, когда используется блокировка (монитор) и т. д.), но для других вещей вам нужно явно указать, чтобы он не выполнял переупорядочение, которое изменило бы вывод программы (например, volatile маркер на полях , использование замков и т. д.).

Примечание:
Небольшое дополнение о том, что "происходит до отношений". Это причудливый способ сказать, что независимо от того, что может сделать переупорядочение Java, событие А произойдет раньше, чем событие Б. В нашем странном более позднем примере с тушеным мясом: «Шаг 1 и 3 происходит до шага 4». и молоко в "". Также, например, «Шаг 1 и 3 не нуждаются в отношении происходит до, потому что они никак не зависят друг от друга».

По дополнительному вопросу и ответу на комментарий

Во-первых, давайте установим, что означает «время» в мире программирования. В программировании у нас есть понятие «абсолютного времени» (сколько сейчас времени в мире?) и понятие «относительного времени» (сколько времени прошло с момента x?). В идеальном мире время есть время, но если у нас нет встроенных атомных часов, абсолютное время нужно время от времени корректировать. С другой стороны, для относительного времени нам не нужны поправки, поскольку нас интересуют только различия между событиями.

В Java System.currentTime() имеет дело с абсолютным временем, а System.nanoTime() — с относительным временем. Вот почему в Javadoc к nanoTime говорится: «Этот метод может использоваться только для измерения прошедшего времени и не связан ни с каким другим понятием системного или настенного времени».

На практике и currentTimeMillis, и nanoTime являются нативными вызовами, и поэтому компилятор не может практически доказать, что переупорядочивание не повлияет на правильность, то есть не изменит порядка выполнения.

Но давайте представим, что мы хотим написать реализацию компилятора, которая действительно просматривает нативный код и переупорядочивает все, если это допустимо. Когда мы смотрим на JLS, все, что он говорит нам, это то, что «вы можете изменить порядок всего, что угодно, пока это не может быть обнаружено». Теперь, как автор компилятора, мы должны решить, не нарушит ли переупорядочение семантику. Для относительного времени (nanoTime) было бы явно бесполезно (т. е. нарушает семантику), если бы мы изменили порядок выполнения. Теперь, не нарушит ли семантика, если мы переупорядочим абсолютное время (currentTimeMillis)? Пока мы можем ограничить разницу между источником мирового времени (скажем, системными часами) и тем, что мы решим (например, «50 мс»)*, я говорю «нет». Для приведенного ниже примера:

long tick = System.currentTimeMillis();
result = compute();
long tock = System.currentTimeMillis();
print(result + ":" + tick - tock);

Если компилятор сможет доказать, что compute() требует меньшего, чем максимальное отклонение от системных часов, которое мы можем разрешить, тогда было бы законно переупорядочить это следующим образом:

long tick = System.currentTimeMillis();
long tock = System.currentTimeMillis();
result = compute();
print(result + ":" + tick - tock);

Поскольку это не нарушит спецификацию, которую мы определили, и, следовательно, не нарушит семантику.

Вы также спросили, почему это не включено в JLS. Я думаю, что ответ будет «чтобы JLS был коротким». Но я мало что знаю об этой области, поэтому вы можете задать отдельный вопрос об этом.

*: В реальных реализациях эта разница зависит от платформы.

person Enno Shioji    schedule 27.03.2013
comment
Спасибо за ответ «объясни-мне-мне-5». Я добавил дополнительный вопрос на основе вашего ответа. - person Abs; 28.03.2013
comment
@EnnoShioji Я очень сомневаюсь, что компилятор когда-либо изменит порядок вызова System.currentTime(), если результаты вызова могут каким-либо образом повлиять на результат вычислений, которые происходят позже в порядке программы. - person Andrew Bissell; 28.03.2013
comment
@AndrewBissell: если результат вычислений зависит от относительного времени, вы будете использовать относительные часы. Независимо от того, существуют ли реализации, которые действительно выполняют такое переупорядочение, такое переупорядочение кажется нормальным, если оно имеет преимущества в производительности. - person Enno Shioji; 28.03.2013
comment
@AndrewBissell: Да, и кстати, для currentTimeMillis на расчет может повлиять поправка ОС к часам (т. Е. Ток - тик может стать даже отрицательным, когда ОС вносит поправку в этот интервал). Таким образом, даже без какого-либо переупорядочения связанных вещей у вас все равно будет эта проблема. - person Enno Shioji; 28.03.2013
comment
@EnnoShioji Мне хорошо известны все проблемы с использованием System.currentTimeMillis(). Но независимо от того, насколько грубым является измерение, вполне возможно, что переупорядочение операции может привести к тому, что ей будет присвоено другое значение. Это абсолютно нарушит правило порядка выполнения программы, если результаты вызова каким-либо образом связаны с результатами других программ. - person Andrew Bissell; 28.03.2013
comment
@EnnoShioji Еще немного размышлений по этому поводу, и я не уверен, что невозможно изменить порядок System.currentTimeMillis() без побочных эффектов на результат программы. Как вы заметили, его ни в коем случае нельзя использовать для измерения выполнения программы, поэтому, к счастью, нам не нужно слишком беспокоиться об этом! - person Andrew Bissell; 29.03.2013
comment
@EnnoShioji Ваш ответ на мой дополнительный вопрос многое проясняет, но он по-прежнему не дает окончательного ответа, можно ли изменить порядок currentTimeMillis () или nanoTime () . Вы упомянули, что подразумевается, что компилятор не будет переупорядочивать ваш код. Существуют ли явные правила, о которых должны знать разработчики компиляторов для таких функций? Если да, то почему он не является частью спецификации, такой как JSR? - person Abs; 30.03.2013
comment
@wagaboy: я отредактировал вторую часть ответа. Надеюсь, это имеет смысл? - person Enno Shioji; 30.03.2013
comment
@EnnoShioji Как и в предыдущем обсуждении здесь, вы можете найти интересное выступление Мартина Томпсона в InfoQ. Около 45:00 он замечает, что действительно System.nanoTime() не является упорядоченной инструкцией, как вы сказали, что это может иметь место. Хороший урок для меня не интерпретировать правила — даже правила JMM — слишком жестко! infoq.com/presentations/performance-testing-java - person Andrew Bissell; 24.07.2013
comment
@AndrewBissell: в 45:37 Томпсон говорит, что RDTSC не является упорядоченной инструкцией ЦП, а это означает, что ЦП может изменить ее порядок. Однако Питер Лоури говорит, что эффект от этого меньше. чем 10 наносекунд. Вместо RDTSC nanoTime также может использовать HPET, я не знаю, как это делает. В любом случае ‹10 нс от переупорядочивания процессором — это довольно мало; но остается вопрос: запрещают ли какие-либо правила переупорядочение JIT-компилятором? - person Jaan; 16.12.2014
comment
что мы можем ограничить разницей от источника мирового времени (скажем, системных часов) до того, что мы решим (например, 50 мс), что означает @EnnoShioji - person Mohendra Amatya; 05.05.2021

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

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

x = 1;
z = z + 1;
y = 1;

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

Со вторым пунктом списка вступает в действие правило блокировки монитора: «Разблокировка монитора происходит до каждой последующей блокировки основного монитора». (Параллелизм в Java на практике стр. 341). Это означает, что поток, получивший данную блокировку, будет иметь согласованное представление о действиях, которые произошли в других потоках, прежде чем снять эту блокировку. Однако обратите внимание, что эта гарантия применяется только в том случае, если два разных потока release или acquire используют одну и ту же блокировку. Если поток A выполняет кучу действий перед снятием блокировки X, а затем поток B получает блокировку Y, то нет уверенности в том, что поток B будет иметь непротиворечивое представление о действиях A до X.

Порядок операций чтения и записи в переменные может быть изменен с помощью start и join, если а.) это не нарушает порядок выполнения программы внутри потока, и б.) переменные не имеют других " к ним применяется семантика синхронизации потоков, скажем, путем сохранения их в volatile полях.

Простой пример:

class ThreadStarter {
   Object a = null;
   Object b = null;
   Thread thread;

   ThreadStarter(Thread threadToStart) {
      this.thread = threadToStart;
   }

   public void aMethod() {
      a = new BeforeStartObject();
      b = new BeforeStartObject();
      thread.start();
      a = new AfterStartObject();
      b = new AfterStartObject();

      a.doSomeStuff();
      b.doSomeStuff();
   }
}

Поскольку поля a и b и метод aMethod() никак не синхронизированы, а действие запуска thread не изменяет результаты записи в поля (или действия с этими полями), компилятор может свободно переупорядочить thread.start() в любом месте метода. Единственное, что нельзя сделать с порядком aMethod(), это изменить порядок записи одного из BeforeStartObject в поле после записи AfterStartObject в это поле или переместить один из doSomeStuff() вызовов. в поле до того, как в него будет записано AfterStartObject. (То есть предполагается, что такое переупорядочение каким-то образом изменит результаты вызова doSomeStuff().)

Здесь важно помнить, что в отсутствие синхронизации поток, запущенный в aMethod(), теоретически может наблюдать одно или оба поля a и b в любом из состояний, которые они принимают во время выполнения aMethod() (включая null).

Ответ на дополнительный вопрос

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

person Andrew Bissell    schedule 27.03.2013
comment
Спасибо за подробное объяснение и продолжение. - person Abs; 28.03.2013
comment
@wagaboy Есть ли что-то еще, что вы ищете здесь? Просто интересно, почему мой ответ не был принят. - person Andrew Bissell; 28.03.2013
comment
Я долгое время скрываюсь, но новый постер на SO. Поэтому я не уверен, как работают голоса и выборы. Я нахожу ваши комментарии и ответы очень полезными, поэтому я проголосовал и выбрал их. Я также сделал то же самое с ответом Энно, так как нашел его полезным. По какой-то причине SO выбрал только этот ответ (может быть, потому, что у этого ответа больше голосов?). Пришло время мне перейти к разделу часто задаваемых вопросов. - person Abs; 28.03.2013
comment
@wagaboy SO позволяет ОП выбирать только один ответ. Так что принятый ответ был последним, который вы приняли - person John Vint; 28.03.2013
comment
Возможно, я не понимаю здесь всей картины, но как ваше утверждение о видимости a и b во внутреннем потоке коррелирует с тем фактом, что между утверждениями существует отношение «происходит-до» внутри потока, и есть отношение «происходит-до» между thread.start() и самой первой строкой кода в этом новом потоке. Поскольку отношение HB является транзитивным, не означает ли это, что код в новом потоке может наблюдать a и b ТОЛЬКО как BeforeStartObject и даже не null ? - person I4004; 23.04.2016
comment
@AndrewBissell, я не думаю, что это утверждение правильное: здесь важно помнить, что в отсутствие синхронизации поток, запущенный в aMethod(), теоретически может наблюдать одно или оба поля a и b в любое из состояний, которые они принимают во время выполнения aMethod() (включая null). См. stackoverflow.com/questions/16248898/ - person I4004; 31.07.2017

Прежде чем я отвечу на вопрос,

читает и пишет в переменные

Должно быть

volatile чтение и volatile запись (одного и того же поля)

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

На ваши вопросы:

Означает ли это, что чтение и запись могут быть изменены по порядку, но чтение и запись не могут изменить порядок с действиями, указанными во 2-й или 3-й строке?

На самом деле ответ зависит от того, какое действие происходит первым, а какое вторым. Взгляните на JSR 133 Cookbook для разработчиков компиляторов. Существует сетка Can Reorder, в которой перечислены допустимые изменения порядка компилятора, которые могут произойти.

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

Что означает «порядок программы»?

Это из JLS

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

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

Например

public static Object getInstance(){
    if(instance == null){
         instance = new Object();
    }
    return instance;
}

Можно переупорядочить на

public static Object getInstance(){
     Object temp = instance;
     if(instance == null){
         temp = instance = new Object();
     }
     return temp;
}
person John Vint    schedule 27.03.2013

это просто означает, что хотя поток может быть мультиплексирован, но внутренний порядок действия/операции/инструкции потока останется постоянным (относительно)

поток 1: T1op1, T1op2, T1op3... поток 2: T2op1, T2op2, T2op3...

хотя порядок операций (Tn'op'M) между потоками может различаться, но операции T1op1, T1op2, T1op3 внутри потока всегда будут выполняться в этом порядке, и поэтому T2op1, T2op2, T2op3

например:

T2op1, T1op1, T1op2, T2op2, T2op3, T1op3
person Ankit    schedule 27.03.2013

Учебник по Java http://docs.oracle.com/javase/tutorial/essential/concurrency/memconsist.html говорит, что отношение «происходит до» — это просто гарантия того, что запись в память одним конкретным оператором видна другому конкретному оператору. Вот иллюстрация

int x;

synchronized void x() {
    x += 1;
}

synchronized void y() {
    System.out.println(x);
}

synchronized создает отношение «происходит до», если мы удалим его, не будет гарантии, что после того, как поток A увеличит x поток B напечатает 1, он может напечатать 0

person Evgeniy Dorofeev    schedule 27.03.2013