13 февраля 2013 г.

Квест по внутренностям JMM



class AtomicInteger { 
    private volatile int value;
    public AtomicInteger(final int value) {
        this.value = value;
    }
....
}

AtomicInteger sharedRef;

Thread 1

Thread 2

sharedRef = new AtomicInteger(42);

if( sharedRef != null ) {
    System.out.println(sharedRef.get());
}

  1. Может ли этот код вывести 0?
  2. ...Если может — то как? Сможете ли вы теперь теми же глазами смотреть на AtomicInteger?
  3. ...Если нет — то почему?

P.S. Я, если честно, точного ответа не знаю. Хотя пара правдоподобных вариантов у меня есть.

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

  1. Если, не ошибаюсь, то из-за того что sharedRef не volatile, т.е. запись ссылки и её чтение не связаны никакими ребрами happens before, а value не объявлен как final, то есть вероятность того, что второй поток увидит ссылку на sharedRef, но вот поле value всё ещё будет содержать defaultValue, т.е. 0. И да, тут скорее конечно надо другими глазами не на AtomicInteger смотреть, а на new.

    ОтветитьУдалить
    Ответы
    1. Ну насчет новыми глазами смотреть на конструкторы -- это я уже писал. Только когда это конкретно к AInteger применяется -- выглядит иначе, поскольку атомарные типы интуитивно воспринимаются как полностью потокобезопасные.

      Моя первая версия была именно такая. Однако вот один очень авторитетный человек считает, что AI является полностью безопасным для любой публикации. Есть ли у него основания так считать?

      Удалить
    2. Подумал-поразмыслил. Возможно volatile поле влияет на реордеринг в пользу атомика, но механизм мне не ясен в этом случае. Взгляд зацепился за final параметр, но в отличие от final поля эффекта никакого от него не будет IMHO. Ну и совсем бессовестное предположение, что JVM знает об атомиках и не позволяет их небезопасных публикаций.

      Удалить
    3. Нет, никакого специального читерства здесь нет -- интринсики JVM не привносят дополнительной семантики по сравнению с кодом, который они заменяют -- только оптимизацию. Все честно по JMM

      Удалить
    4. Тогда, я честно расписываюсь в своём невежестве и неумении интерпретировать спецификацию JMM, по крайней мере для этого случая) Было бы любопытно узнать ваши объяснения с крокетом и блудницами.

      Удалить
    5. Главное не торопиться посыпать голову пеплом. Даг Ли _каждый_ раз плачется, что вообще никто не умеет на регулярной основе строить корректные доказательства на чистой JMM :)

      Удалить
  2. Я, думаю, что мы никодгда не получил ноль, только если пометим поле sharedRef как final. По крайней мере я всегда стараюсь так делать, когда с атомиками работаю, мне почему-то так спокойнее %)

    Кстати, а почему в твоем примере поле констуктора final? Вроде в моих сорсах оно так не помечено. Ты туда его нарошно поставил?

    ОтветитьУдалить
    Ответы
    1. final для локальных переменных никакой memory семантики не несет. Я просто сам привык так писать, вот и написал.

      Публикация через final ссылку -- это безопасная публикация. Здесь, конечно, никакого шухера не будет. Но вопрос-то в том -- безопасно ли публиковать атомики небезопасно )

      Удалить
  3. Ах, да не ответил почему ноль-то можем получить.
    Код Thread1 по идее можно переписать так.
    localRef = new AtomicInteger();
    localRef.value = 42; // volatile store
    sharedRef = localRef;
    Какие же ограничения нагладываются volatile? Читаем тут один абзац: http://developer.android.com/training/articles/smp.html

    Non-volatile accesses may be reorded with respect to volatile accesses in the usual ways, for example the compiler could move a non-volatile load or store “above” a volatile store, but couldn’t move it “below”. Volatile accesses may not be reordered with respect to each other. The VM takes care of issuing the appropriate memory barriers.

    Т.е. строочка "sharedRef = localRef;" вполне легально "could move above a volatile store" т.е. сточки "localRef.value = 42" и мы получаем ноль.

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

    Вот почему такого эффекта не будет если пометить sharedRef как final, я объяснить не могу. Но я уверен, что JVM, начиная с версии 5.0, сделает все возможное и невозможное, чтобы в случае с final мы никогда не увидели 0.

    ОтветитьУдалить
    Ответы
    1. Хорошее рассуждение, я тоже так сначала рассуждал. Однако -- теперь я уже практически уверен -- нет, 0 получить здесь нельзя, если реализация JVM соответствует JMM. Вопрос -- почему.

      У Далвика, кстати, все же другая модель памяти, насколько я помню. Возможно, что в его модели как раз 0 возможен.

      Удалить
    2. Ты имеешь ввиду реализация JMM другая, или сама JMM другая?

      Удалить
    3. Руслан, поясни все же откуда у тебя такая уверенность. Я просто открываю мануал от DL http://g.oswego.edu/dl/jmm/cookbook.html и в первой же табличке "Can Reorder" вижу, что если volatile store первая операция, а normal store вторая операция (т.е. наш случай, согласно развернотому коду выше в комментах), то запрета на реордеринг нет.

      Удалить
    4. Я имею в виду у Далвика спецификация другая. В частности, насколько я помню, у них volatile больше похож на наш lazySet.

      Все эти рассуждения -- про "может переставляться" и "не может переставляться" -- это не более, чем упрощенные эвристики. Они могут работать в большинстве случаев (и работают), но надо помнить, что всегда есть тонкие случаи, и только спецификация изначально истинна, а все остальное -- лишь тень от света, на стене бытия

      Удалить
    5. Ну вот здесь http://stackoverflow.com/questions/4588076/is-dalviks-memory-model-the-same-as-javas, чувак, который работает над далвиком утвреждает, что, начиная с версии 3.0 у них практически все согласно JSR-133.

      А ты спецификацию умеешь интерпретировать, чтобы ее конкретно на этот случай спроецировать?

      Или можно проще поступить. Взять запустить данный код, посмотреть во что он скомпилится на наличие барьеров памяти. Если таковой в нужном месте не обнаружится, то на твоей платформе можно ожидать нолик.

      Ну, вобщем, с нетерпением жду от тебя подробностей решения данного квеста :)

      Удалить
    6. Я не очень в курсе относительно Далвика, могу ошибаться. Некоторое время назад -- еще в яндексе -- я услышал что у них несколько ослабленная модель памяти, отложилось в памяти. Возможно, они уже поправились.

      Интерпретировать спецификацию "вообще" я не буду браться. Но в этом конкретном случае у меня получилось построить доказательство. Там используются несколько непривычные свойства JMM, поэтому я не вполне был уверен в корректности. Но еще вчера авторитетный человек (c) подтвердил, что таки-да, именно так и именно поэтому.

      Скомпилировать -- это слишком грубо. Например, формально lazySet в данном случае не даст тебе необходимых гарантий -- но фактически сгенерированный код на x86 их таки даст

      Удалить
  4. safe publication

    Thread 2 не может получить ссылку на AtomicInteger до того как он окончательно сконструирован. Конструктор AtomicInteger нигде не утекает ссылками на себя. Поэтому в момент присвоения значение в sharedRef AtomicInteger всегда инициализирован. Ну, а volatile на value гарантирует видимость значения в других потоках.

    ОтветитьУдалить
    Ответы
    1. >Thread 2 не может получить ссылку на AtomicInteger до того как он окончательно сконструирован.

      Почему, собственно, не может? Кто ему помешает?

      Удалить
    2. Прошу прощения. Упустил из вида коментарий про небезопасную публикацию sharedRef. Теперь стало интересее.

      Удалить
    3. Руслан,поясни плз "Почему, собственно, не может? Кто ему помешает?"
      Ведь в предъявленном коде описан конструктор, и видно что утечки в нём нет.

      Удалить
  5. В JSR-133 есть такие строки:
    A write to a volatile field happens-before every subsequent read of that volatile

    не является ли это ответом?

    ОтветитьУдалить
    Ответы
    1. Ключевое слово - subsequent. В исходном примере нет явных гарантий, что чтение произойдёт после записи.

      Удалить
    2. Ну скажем так -- ответом это не является. Частью ответа -- возможно.

      Удалить
    3. "In the Java Memory Model a volatile field has a store barrier inserted after a write to it and a load barrier inserted before a read of it. Qualified final fields of a class have a store barrier inserted after their initialisation to ensure these fields are visible once the constructor completes when a reference to the object is available."

      Не приводит ли store barrier после volatile write к такому же эффекту как и гарантированая видимость final поля?

      Удалить
    4. Откуда цитата? По-моему, все как раз наоборот -- StoreStore барьер должен быть _до_ волатильной записи, а LoadLoad _после_ волатильного чтения. И, на самом деле, для волатильной записи нужен (рекомендуется) еще StoreLoad барьер

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

      Удалить
    5. Так через JMM и нельзя доказать корректность. С точки зрения исключительно JMM результат может быть 0.

      Удалить
    6. Хорошо, вы меня почти уговорили )

      Удалить
  6. кстати, а вот таки интересный пример из жизни насекомых

    CHM:

    static final class HashEntry {
    final K key;
    final int hash;
    volatile V value;
    final HashEntry next;

    HashEntry(K key, int hash, HashEntry next, V value) {
    this.key = key;
    this.hash = hash;
    this.next = next;
    this.value = value;
    }
    }


    в CHM, как известно, нельзя положить пару key-null

    однако CHM$Segment.get как бы намекает на что-то

    /**
    * Reads value field of an entry under lock. Called if value
    * field ever appears to be null. This is possible only if a
    * compiler happens to reorder a HashEntry initialization with
    * its table assignment, which is legal under memory model
    * but is not known to ever occur.
    */
    V readValueUnderLock(HashEntry e) {
    lock();
    try {
    return e.value;
    } finally {
    unlock();
    }
    }

    /* Specialized implementations of map methods */

    V get(Object key, int hash) {
    if (count != 0) { // read-volatile
    HashEntry e = getFirst(hash);
    while (e != null) {
    if (e.hash == hash && key.equals(e.key)) {
    V v = e.value;
    if (v != null)
    return v;
    return readValueUnderLock(e); // recheck
    }
    e = e.next;
    }
    }
    return null;
    }

    О чём это нам хотел сказать Doug Lea ?

    ОтветитьУдалить
    Ответы
    1. Прям как spurious wake up. Он есть. Но никто никогда не видел (вроде только на солярке бывает).

      Удалить
    2. нет, здесь именно тот случай, о котором и спрашивает Руслан - по сути вопроса HashEntry ничем не отличается от AtomicInteger

      Удалить
    3. Верно. Именно тот случай. Мне просто вот это понравилось:
      which is legal under memory model, but is not known to ever occur

      Удалить
    4. В моих сорсах нашел еще javadoc к HashEntry:
      * Because the value field is volatile, not final, it is legal wrt
      * the Java Memory Model for an unsynchronized reader to see null
      * instead of initial value when read via a data race. Although a
      * reordering leading to this is not likely to ever actually
      * occur, the Segment.readValueUnderLock method is used as a
      * backup in case a null (pre-initialized) value is ever seen in
      * an unsynchronized access method.

      По сути тот же комментарий, что Володя привел, только другими словами.

      Т.е. в javadoc пишут, что это легально с точки зрения JMM получить неиницилизированное значение, хотя в реальности это нигде и не случается. Руслан же на сколько я понял все же утверждает, что зря они соломку подстилают, не может там никто увидеть неинициализированного значения. Поправьте меня, пожалуйста, если я все же что-то не так понял.

      Удалить
    5. !flood mode on
      Ruslan. Have a fresh view of JMM.
      !flood mode off

      Удалить
    6. Возможно, этот код остался в CHM еще со времен, когда j.u.c был реализован под 1.4.

      Удалить
    7. ой вряд ли, если посмотреть и сравнить backport-util-concurrent ...

      Удалить
  7. Этот комментарий был удален автором.

    ОтветитьУдалить
  8. Чет у меня подозрение что дело все же в volatile поле. Т.е. переменная sharedRef получит ссылку на объект AtomicInteger когда выполнится конструтор, а так как выполнится конструктор то произойдет запись в volatile поле value. И в итоге получаем hb записи value и чтение. Результат ноль не увидим.

    ОтветитьУдалить
  9. Ответ: нет не возможно.
    Код для пояснения:
    public class A {
    B bRef;
    public static void main(String[] args) {
    A a = new A();
    a.bRef = new B(a,42);
    }
    }
    class B{
    volatile int value;
    public B(A a,final int c) {
    this.value=c;
    //будет null. ссылка ещё не запаблишилась.
    System.out.println(a.bRef);
    }
    }

    Запис volatile переменной happens-before паблишинга ссылки на B. Поэтому так зареордериться не сможет.
    В итоге если bRef!=null то value уже не 0.

    ОтветитьУдалить
    Ответы
    1. Нет, ваше объяснение не верно, хотя само утверждение конечно верно. program order, который согласован с HB, не распространяется на другие потоки сам по себе. То, что запись volatile упорядочена до записи ссылки на созданный объект не означает, что запись ссылки упорядочена с чтением этой ссылки в другом потоке.

      В следущем посте подробно разбирается почему все-таки утверждение верно.

      Удалить
    2. Прочитал ваш следующий пост.
      Собственно не нашёл принципиальной разницы в логике. Возможно я не совсем полно описал ход мыслей. Но так или иначе всё сводиться к пунку 8 из вашего следующего поста, о чем я и пытался сказать.

      Удалить
    3. Принципиальная разница в логике, которую вижу я, состоит в том, что у вас ни разу не звучало ни total synchronization order, ни, хотя бы, synchronized-with. А это принципиально для доказательства -- если вы, конечно, его поняли. Ваше рассуждение переносится на случай не-volatile поля совершенно без изменений. Но это точно не верно, потому что без volatile доказательство работать не будет.

      Это лишний раз доказывается вашим примером -- тот код, который вы приводите, демонстрирует всего лишь intra-thread semantics, которая совершенно не зависит от наличия или отсутствия volatile.

      Удалить
    4. Доказательство(если это можно так назвать, скорей объяснение) не переноситься на случай без volatile поля, так как будет возможен реордеринг. В случае с volatile реордеринг записи в переменную и паблишинг ссылки не возможен. Так как паблишинг ссылки атомарен, то в другом потоке мы можем увидить либо null либо ссылку на наш объект. Соответственно полседующий read volatile увидит 42, так как ссылка не могла быть запаблишина до volatile write.

      Удалить
    5. Скажите, откуда вы взяли, что нельзя переставить обычную запись, идущую после волатильной, до этой волатильной?

      Удалить
  10. >>ваше объяснение не верно, хотя само утверждение конечно верно
    Руслан, неверно ни утверждение, ни ваше доказательство http://cheremin.blogspot.ru/2013/02/jmm-solution.html :)

    В вашем доказательстве ошибочно следующее утверждение:
    "Поскольку (2) и (6) — synchronized actions, то из ![ (2) sw (6) ] => [(6) sw (2) ] => [(6) hb (2)]"
    Ошибочно оно потому, что SW - частичный порядок, и потому из ![ (2) sw (6) ] не следует [(6) sw (2) ]. Единственный полный порядок определяемый JMM - это SO, но ведь тут речь не про него.

    Алексей Шипишёв писал на конкаренси интерест аналогичный вопрос (http://cs.oswego.edu/pipermail/concurrency-interest/2013-November/011951.html) со своим обоснованием, где допустил похожую ошибку.
    А вот и обоснование возможности прочитать 0, в котором пока никто ошибки не нашёл: http://cs.oswego.edu/pipermail/concurrency-interest/2013-November/011954.html
    Кроме того, утверждение, что 0 прочитать возможно, "заверено печатью" Дага Ли:http://cs.oswego.edu/pipermail/concurrency-interest/2013-November/011966.html

    ОтветитьУдалить
    Ответы
    1. Как раз в феврале мы с Алексеем и обсуждали этот вопрос -- ему в приватной переписке ДЛ упомянул, что это верно, но доказательства не привел. На пару мы придумали вот это доказательство, про которое ДЛ сказал "вчерне сойдет". Когда я уже готовил доклад для JPoint я обнаружил косяк, на который вы ссылаетесь, поэтому в моем докладе этого примера уже не было (а как я его хотел...). А в ноябре у Алексея таки дошли руки попытаться таки "починить" доказательство с использованием commitment procedure, и он вышел в c-i, откуда и появился тред, на который вы ссылаетесь. Такая вот история :)

      Удалить
    2. вот это переплетение событий! :)

      Удалить