10 ноября 2012 г.

Для тех, кто не решился написать ответы к предыдущему посту

Моя душа несколько успокоилась, когда все комментировавшие предыдущий пост дали правильные ответы. А то я так часто слышу про vwrite hb vread, что начал сомневаться, помнит ли вообще кто-то, что это не совсем верное утверждение.

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

Другими словами, не существует никаких ребер happens-before между строками кода в программе — ребра существуют в конкретном сценарии выполнения этого кода (в оригинале звучит как execution — сценарий, или маршрут выполнения. Но однажды я услышал термин "трасса над кодом", и он подкупил меня своей образностью, так что я часто использую его). Нет HB между какой-то волатильной записью и каким-то волатильным чтением, есть HB между событием волатильной записи некоторого значения, и событием волатильного чтения его же (из той же переменной, понятно).

А вот вопрос немного сложнее:

Thread 1

Thread 2

volatile int va;
int a;

va = 1;
a = 10;
va = 1;

if( va == 1 ){
int la = a;
}
Какие ребра существуют здесь?

14 комментариев:

  1. Так Вы опишите конкретный сценарий. Здесь может не быть вообще никаких ребер, либо ребро между первым присваиванием и чтением либо между вторым присваиванием и чтением.

    Кстати, я не удивлюсь, если компилятор вообще выкинет одно из этих присваиваний. Хорошо бы позыркать.

    ОтветитьУдалить
  2. Мне здесь интересно вот что -- как я могу отличить трассу, где я увидел второе присваивание, от трассы, где я увидел первое? Потому что если я не могу их различить, то я же и не могу ничего из этого выводить.

    ОтветитьУдалить
  3. Ну, в данном примере, если все, что выполняется в треде2, произошло после того, что выплняется в треде 1, через некоторое время, то мы можем гарантировать что в la запишется 10. Без второго volatile write в la могло бы быть и 0, и 10.

    Если же оба треда выполняются одновременно, то мы ничего не можем гарантировать.

    ps у Вас рекапча фашистская!

    ОтветитьУдалить
  4. Если у нас есть какое-то дополнительное условие -- например, если поток 2 запускается из потока 1 где-то позже приведенного куска -- то и вопросов нет. Но тогда как раз volatile нам вообще нафиг не упал, la=10 и без него будет гарантировано.

    Если же под "произошло после" вы подразумеваете именно хронологическое "после", то нет, насколько я понимаю это ничего не гарантирует само по себе. Кроме того интересна реализация -- как именно вы собираетесь засечь время в первом потоке, как сообщить эту засечку во второй поток, и с чем сравнивать? Я вот не вижу способа организовать протокол сверки часов между потоками без действий синхронизации.

    P.S. Увы, я не представляю, откуда она взялась и как ее убрать

    ОтветитьУдалить
  5. Странно, ваш комментарий пришел мне на почту, но здесь его нет.

    >я имею в виду хронологически. например, запуская данный код в разных потоках по часам.

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

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

    Это хорошее замечание, хоть и не совсем верное. На самом деле модель памяти задает способ определения допустимых сценариев исполнения. Используя JMM вы можете сказать, что вот такая-то трасса над этим кодом возможна в JVM, а такая-то -- нет.

    Вы правы в том смысле, что нужно задать конкретный вопрос -- какую трассу я хочу проверить на допустимость. И с этой точки зрения лично мне все более-менее понятно. Но вот с точки зрения формализма: когда я строю ребраHB, как мне различать события, которые не различимы с точки зрения другого потока?

    ОтветитьУдалить
  6. Хм.. Тут я начинаю гадать. Чисто интуитивно, события в разных тредах, помимо реберhb связаны еще и некими причинно-следственными связями. В данном примере мы пишем в la только если va == 1.

    Мы дважды присваиваем va одно и то же значение - это не имеет смысла в одном потоке - и поэтому приводит к парадоксам в многопоточности.

    ОтветитьУдалить
  7. Т. е. я хочу подчеркнуть, что обе записи в va неразличимы в рамках потока, который пишет, а не только в других потоках.

    ОтветитьУдалить
  8. Этот набор операций не являетя happens-before consistent - из-за неразличимости двух записей в va. По факту получается, что одно межпоточное ребро hb здесь всё-таки есть -- между первой записью в va и положительной веткой if-а.

    ОтветитьУдалить
  9. @артем
    >я хочу подчеркнуть, что обе записи в va неразличимы в рамках потока, который пишет, а не только в других потоках.

    Как раз в своем потоке они вполне различимы -- в момент первой записи a=0, в момент второй a=10.

    @Lerm

    >Этот набор операций не являетя happens-before consistent

    Да, интересное уточнение, я забыл про этот термин. А вы разбирались с понятием HBC -- оно несет что-то большее, чем DRF? Потому что я лично просто вижу здесь прежде всего гонку

    ОтветитьУдалить
  10. Если первая запись меняет состояние, то вторая - уже нет.
    В ней нект никакого смысла.

    ОтветитьУдалить
  11. @ Ruslan

    Это интересный вопрос - по моему пониманию, если набор действий не является happens-before consistent, то JMM в общем случае не может полностью описать результат исполнений программы. С другой стороны, это не означает, что результат исполнений оказывается всегда неопределенным - если нет DR.

    В данном примере data race возникает из-за того, что существует такое исполнение, когда существует ребро hb только между первой записью в va и чтением из него - в этом случае по переменной 'a' получается data race, поскольку запись в неё не упорядочена по рёбрам hb с её чтением.
    С другой стороны, можно было бы модифицировать пример следующим образом для T1:
    a = 10;
    va = 1;
    va = 1;
    В этом случае, при любом исполнении включающем положительную ветвь if-а в T2 мы будем иметь ребра hb упорядочивающие записи в 'a' по отношению к чтению из неё, поэтому можем однозначно вычислить значение la (т.е. у нас нет data race). Если у нас нет DR, то результат исполнения должен быть SC, хотя, формально, такие исполнения не будут well-formed, поскольку набор действий всё равно не является happens-before consistent.

    ОтветитьУдалить
  12. @Lerm
    >JMM не может полностью описать результат исполнений программы

    Тут я не очень понял. В джаве нет понятия undefined behavior. Насколько я понимаю, в случае не DRF кода вы можете получить огромный набор допустимых трасс, но он всегда будет конечным, и вы всегда можете сказать, допустима или нет конкретная трасса.

    ОтветитьУдалить
  13. либо 0 либо 10, потому что:

    1. Присваивание a и va начальным значениям это события произршедшие до старта потоков, значит hb коду внутри потоков
    2. Внутри потоков hb между инструкциями
    3. Между потоками, ребра идут по va, поэтому
    3.1 Если чтение va _до_ первого присваивания то la не существует
    3.2 Если чтение va _до_ второго присваивания, то la может видить или не видеть 10 из а. Даже если a уже равно 10 в первом потоке, второй может этого события не увидеть
    3.3 Если чтение va _после_ второго присваивания la всегда 10

    PS: А задачки на lazySet есть?
    PPS: Ты не пробовал расковырять логику устройства ConcurrentLinkedQueue? Смушают заигрывания с GC и lazySet, не лезет у меня это в мозг пока :(

    ОтветитьУдалить
    Ответы
    1. Вот вопрос -- как вы разделите 3.2 и 3.3? Какие наблюдаемые во втором потоке события могут дать вам возможность эти случаи разделить?

      А в чем именно проблема с CLQ? Последний раз как я туда смотрел там все было умеренно сложно.

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

      Удалить