Data races is pure evil

Nondeterminism is unavoidable, but data races are pure evil (by Hans Boehm) -- любопытная статья, которая висит у меня в закладках несколько месяцев.

Ханс пишет про то, что многие люди пытаются уйти от синхронизации к data race based протоколам во имя увеличения масштабируемости (scalability). И это совершенно не оправдано — мало того, что код с гонками получается ошибочным в 9 случаях из 10, так еще и надежды на масштабируемость — это, по большей части, лишь фантазии. Ханс обращает внимание на важную вещь: синхронизация это (вообще говоря) локальная операция. То есть, в идеальном мире, она вносит только локальные задержки, но не уменьшает масштабируемость.

А почему компилятор не синхронизирует код за меня?

Основная гарантия, которую дает программисту JMM, это что программы без гонок (data race free) выполняются так, как будто они sequentially consistent. Гонки (data race), напомню, это пара чтение/запись или запись/запись одной переменной, когда операции в этой паре не упорядочены через happens-before. И чтобы их упорядочить, если они еще не, нужно добавить каких-то действий синхронизации.

Нет никакой ложки...

...и нет никаких реордерингов. Reordering — это поэтическая метафора. Процессоры вовсе не переставляют инструкции. Процессоры просто выполняют код хуй знает какиначе, чем он написан. Как именно? — да как считают нужным, не нравится — не покупайте. Компиляторы — сюрприз — тоже не переставляют инструкции. Компиляторы делают с вашим кодом что-то противоестественноекакую-то неведомую и непонятную херню. Не верите — выведите дизасм достаточно длинного метода на яве, и попробуйте точно объяснить смысл хотя бы пары дюжин подряд идущих инструкций. Там есть комментарии, но вряд ли это вам поможет. Не нравится — пишите свой, с перестановками и циклами причинности.

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

Студентка Люся выучила все билеты по логике и стала мужиком.

Хорошо, давайте разберем предыдущий пост. Для доказательства нам понадобится всего ничего: волос с головы Путина, менструальная кровь девственницыJMM в мягком переплете, и мозг со способностями к математической логике.

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

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

Моя душа несколько успокоилась, когда все комментировавшие предыдущий пост дали правильные ответы. А то я так часто слышу про 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; }

Какие ребра существуют здесь?

Если вы знаете, что такое happens-before...

...то ответьте мне на несколько простых вопросов. Дан такой код:

Thread 1	Thread 2
volatile int va;
va = 10;	int b = va;

Вопросы (отвечать желательно по порядку, не забегая вперед):

1. Какие здесь есть межпоточные ребра HB?
2. Может ли в b оказаться что-то, кроме 10?
3. Может ли в b оказаться 0?
4. Изменится ли что-либо, если здесь заменить volatile store на lazySet?

Вдогонку про публикацию

Вдогонку к предыдущему посту, и к вот этому посту Алексея. Для прояснения ситуации.

Итак, вот это

public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях тундры...
public T sharedRef;
 
sharedRef = new T( 10 );
 

НЕбезопасная публикация

Вот это:

public class T {
   public int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public volatile T sharedRef;
 
sharedRef = new T( 10 );
 

безопасная публикация -- потому что через volatile-ссылку.

Вот это:

public class T {
   public final int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

безопасная публикация -- потому что для final-полей особые гарантии.

А вот это:

public class T {
   public volatile int field1;
 
   public T( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

НЕбезопасная публикация -- потому что обычные записи (sharedRef=new T()) можно переставлять до волатильных записей! Поэтому волатильность поля field1 не гарантирует нам, что ссылка на объект T будет опубликована после инициализации этого поля.

UPD: В данном конкретном случае, когда в классе всего одно поле — публикация таки безопасна. Дискуссию по этому поводу можно прочитать здесь, а формальное доказательство здесь. Однако неочевидно, можно ли перенести это рассуждение на классы со "смешанным составом" полей (volatile+non volatile)

UPD по просьбам читателей: вот это

public class T {
   private int field1;
 
   public T( final int field1 ){
      synchronized( this ) {
         this.field1 = field1;
      }
   }
    
   public synchronized int getField1(){
      return this.field1;
   }
   
   public synchronized void setField1( final int field1 ){
      this.field1 = field1;
   }
}
 
//...где-то в дебрях кода...
public T sharedRef;
 
sharedRef = new T( 10 );
 

Это такая хитрая штука: формально публикация небезопасна, но фактически это ненаблюдаемо -- если вы не полезете к field1 какими-нибудь неправославными методами, то для доступа через геттер/сеттер все безопасно.

(Un)Safe publication

Безопасная/небезопасная публикация ссылок — источник огромного количества ошибок в многопоточном коде. Мне иногда кажется, что таких ошибок вообще большинство. Т.е. если программист обладает >= базовыми знаниями по concurrency в яве, то почти наверняка он все равно частенько будет писать код, некорректный по JMM, и в большинстве случаев некорректность будет связана именно с понятием небезопасной публикации.

Да что я все о каких-то абстрактных программистах рассказываю. Давайте честно: unsafe publishing я регулярно обнаруживаю в своем собственном коде, и если бы только старом... Так нет — это, наверное, единственная ошибка, которую я продолжаю регулярно, раз за разом совершать при написании многопоточного кода.

Для такой распространенности есть две большие причины. Во-первых, публикация ссылки — это обманчиво простая операция. Не, ну что может быть проще, чем просто присвоить ссылку на объект какому-то полю, а? Очень сложно постоянно держать в памяти, что если этим присвоением ты делаешь объект доступным другому потоку — то вокруг сразу начинают виться драконы (да, да, и те самые тоже), и простая операция моментально становится очень непростой с точки зрения JMM.

Это первая причина. А вторая состоит в том, что такого рода нарушения JMM очень редко когда становятся причиной реальных багов. Т.е. программист очень редко получает прямую недусмысленную обратную связь от реального мира вида "написал херню — получил регулярно возникающий но сложный в отладке гейзенбаг". Обычно обратная связь приходит лишь в виде пиздюлейругани от старших товарищей — что, все же, обладает гораздо меньшим воспитательным эффектом...

Чуть подробнее...

(Не)Безопасная публикация

//есть у нас такой класс
public class T {
   public int field1;

   public T( final int field1 ){
      this.field1 = field1;
   }
}

//...где-то в дебрях кода...
public T sharedRef;

//Thread 1
sharedRef = new T( 10 ); //а почему бы и не 10? 42 сегодня взяла отгул

//Thread 2
System.out.println( "sharedRef.field1 = " + sharedRef.field1 );

Какие варианты вывода мы здесь можем наблюдать в соответствии с JMM?

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

Ок, у меня есть специально для вас сценарий повеселее: NullPointerException. Сценарий здесь тоже довольно очевиден — поток №2 может прочитать значение sharedRef до того, как поток №1 туда запишет что-то. В таком случае поток №2 увидит значение по-умолчанию, null.

Мы такого варианта не хотим, поэтому делаем так:

//Thread 2
if( sharedRef != null ){
    System.out.println("sharedRef.field1 = " + sharedRef.field1 );
} else {
    //...
}

Увы, но здесь уже начинаются чудеса. А именно — мы все еще можем увидеть NPE в этом коде! Почему? Да потому что второе чтение sharedRef может вернуть совсем не то значение, что первое. В потоке №1 у нас есть две записи в sharedRef: первая, неявная — запись значения по-умолчанию (null). Вторая, явная — запись ссылки на созданный объект. С точки зрения потока №2 эти записи никак не упорядочены (==нет ребер hb, обязующих его видеть записи именно в "нужном" порядке), и он вполне может увидеть сначала запись sharedRef=new T(), и только потом sharedRef=null.

Disclaimer: Я не уверен на 100% действительно ли JMM допускает такие перестановки. Некоторые уважаемые люди с этим не согласны, а процедура определения возможных трасс для кода с гонками в JMM исключительно ебанутаясложная, и строго ее проходить никому не охота. Но для дальнейшего это не суть важно

Ок, это легко вылечить:

//Thread 2
final T localRef = sharedRef;
if( localRef != null ){
    System.out.println("sharedRef.field1 = " + localRef.field1 );
} else {
    //...
}

мы прикрыли свою задницу от NPE, и теперь уже можем сосредоточиться на выводимых значениях. А значений, увы, мы можем увидеть больше одного. Мы можем увидеть в выводе sharefRed.field1 = 10 — как и ожидалось. Неожиданным может быть то, что мы можем видеть и вывод sharefRed.field1 = 0. Причина все та же. Короткая строчка sharedRef = new T(10) на самом деле это целый ряд операций: (выделение памяти, заполнение полей значениями по-умолчанию, выполнение конструктора, запись ссылки в sharedRef). То, что в коде потока 1 они идут именно в таком порядке не означает, что поток 2 их увидит так же. Он совершенно спокойно может увидеть сначала присвоение ссылки на "пустой" объект с дефолтными значениями полей (увидеть ссылку до присвоения полям начальных значений он не может — это JMM явно запрещает). Более того, если бы в T было больше одного поля (field1, field2, field3...) мы могли бы увидеть в потоке 2 любую комбинацию из инициализированных/неинициализированных полей.

Эти вот два примера — это и есть суть того, что называется небезопасной публикацией, или, неформально, публикацией "через data race" (где здесь гонка — надеюсь, очевидно).

Смотрите, какая штука: в рамках каждого отдельного потока все инструкции упорядочены по happens-before (порядок HB согласован с т.н. program order — порядком инструкций в коде программы). И когда мы в потоке 2 читаем значение, записанное потоком 1 в sharedRef в строчке 14 — кажется очевидным, что раз мы его прочитали, значит эта запись произошла до нашего чтения! То есть интуитивное восприятие последовательности событий подсказывает, что сам факт чтения создает нам ребро HB — которое как раз и необходимо, чтобы весь код стал корректно синхронизированным.

И вот эта-то трактовка, кажущаяся настолько интуитивной-интуитивной, что даже в доказательстве не нуждается — она-то как раз и совершенно не верна. Фактический порядок исполнения инструкций в конкретном запуске программы — это совсем другое, нежели формальный порядок happens-before, верный для любого запуска этой программы на любом железе и под любой JVM. Это очень важный момент: если вы в ходе исполнения программы зафиксировали, что какое-то событие А произошло до события Б — это вовсе не значит, что можно утверждать, что A hb B.

Есть одно важное исключение — семантика final полей. Если бы поле field1 было бы финальным — то как раз сам факт чтения ненулевого значения sharedRef действительно порождал бы HB. Но это особое ребро HB, некоммутативное с обычными — подробнее я уже писал здесь.

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

Где-то я эту хрень уже видел...

Ну конечно. Unsafe publishing — это основа того, почему не работает double-checking locking:

private static DCLSingleton singleton = null;
public static DCLSingleton getInstance(){
   if( singleton == null ){
       synchronized( DCLSingleton.class ){
          if( singleton == null ){
              singleton = new DCLSingleton();
          }
       }
   }
   return singleton;
}

вот если какой-то поток видит singleton != null до захвата монитора — то он может видеть эту ссылку через data race. Как следствие — ссылка-то будет не нулевая, а вот содержимое может быть каким угодно.

Сюда же относится SettableFuture из этого поста — вот этот вариант:

public class SettableFuture<V> implements Future<V> {
    private V slot;

    public V get() throws InterruptedException, ExecutionException {
        synchronized( this ) {
            while ( slot == null ) {
                wait();
            }
        }
        return slot;
    }

    public void set( final V value ) {
        slot = value;
        synchronized( this ) {
            notifyAll();
        }
    }
}

Опасность небезопасной публикации в том, что она заметно усложняет создание потокобезопасного объекта. В самом деле, если нам нужен объект, корректно работающий в многопоточном окружении, и нас пока не заботит производительность — то мы можем просто защитить все методы объекта монитором — и спать спокойно?

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

Пуленепробиваемо потокобезопасный объект в яве можно создать лишь двумя способами. Первый, и самый лучший — делать его immutable. Для объектов с final полями при условии корректной инициализации Священное ПисаниеJMM отдельной главой гарантирует их безопасную работу в многопоточном окружении, даже при передаче через data race. Благослови боже immutability.

Второй, довольно некрасивый — защищать монитором все методы и еще и все конструкторы. Эта тема некоторое время муссировалась в cuncurrency-interests, и в итоге все Пророки согласились, что объект, у которого все поля закрыты, доступ к ним только через методы, а все методы и конструкторы защищены монитором — будет корректно работать, как его не передавай.

Проблема с этим, вторым, методом — в том, что о нем почти никто не знает. Существуют тонны примитивно-потокобезопасных объектов, со всеми методами synchronized, но много ли вы видели объектов с защищенным конструктором? Более того, в ранних версиях одной из священных книг (чуть ли не "Философии джавы") было даже указано, что синхронизировать конструктор нет смысла, и что это явная ошибка. Это было до ревизии модели памяти в 1.5, но кто заметил? Даже синтаксический сахар synchronized как аттрибут метода на конструктор не распространяется...

Представьте, сколько сейчас по разным библиотекам разбросано классов, которые их авторы предполагали потокобезопасными — хотя они таковыми не являются? Тут и сон с аппетитом потерять недолго.

Почему же это не тревожит широкие народные массы?

По легенде, в одном из советских НИИ годов 60-х висел плакат с летящим шмелем, и надписью: "Большая масса тела шмеля вкупе с малой несущей поверхностью его крыльев не позволяет шмелю летать. Но шмель не знает об этом, и летает только поэтому"
Ну, во-первых, потому что во многих православных паттернах работы с многопоточностью безопасность публикации обеспечивается их авторами. И работает, даже если использующий эти паттерны программист вообще не задумывается о безопасной публикации. Например, многие ли задумываются о том, что передавая в Executor Runnable со ссылкой на какие-то данные, которые нужно обработать, мы тем самым публикуем ссылку на эти данные для потоков внутри Executor-а? Между тем это именно публикация ссылки, и она безопасна — потому что об этом позаботились разработчики Executor-а.

А вот вторая причина интереснее и скандальнее. Во всем виноват Интел и его монополия :)

Дело в том, что JMM разрабатывалась, как и многое в мире джавы, так, чтобы оставить максимум свободы для потенциальных оптимизаций как разработчикам JVM, так и железу. Но, разумеется, ни те, ни другие не используют всех оставленных им возможностей — что могут, что востребовано — то и используется. (Это нормальная ситуация для любой сложной и долгоживущей системы: избыточность как плата за невозможность точного предвидения будущего. Системы без избыточности как правило нежизнеспособны в долгосрочной перспективе).

"Write once — run everywhere" — красивый, но весьма условный слоган. Везде — это где именно? Вот лично я только однажды в жизни запускал ява-код на не-x86 архитектуре — когда игрался с J2ME. А если ограничиться SE/EE — кто запускал свой код не на интелловской архитектуре? Думаю, почти никто. Если я ошибаюсь — отпишитесь в комментариях, мне любопытно в скольких неожиданных местах ваш код начал внезапно глючить :)

А что такого плохого у нас с Intel? Да все у нас хорошо, даже слишком. У интелловских x86 архитектур (т.е. не-Intanium) очень жесткая аппаратная модель памяти: total store order, TSO. Это означает, если очень упрощенно, что интелловские (и не только интелловские — архитектура x86 стандарт де-факто для большого куска рынка) процессоры выполняют записи всегда в том порядке, в котором они идут в коде программы. Другая формулировка: все потоки в системе видят все записи в одном и том же порядке, и этот порядок согласован с порядком соответствующих инструкций записи в коде потоков. Это уже гораздо больше, чем требует JMM от кода, выполняемого без дополнительных инструкций синхронизации. В частности, для случая небезопасной публикации это означает, что публикация в железной модели памяти x86 всегда безопасна. И единственным источником непредсказуемости остается JIT — который тоже может переставлять инструкции.

Может-то он может, да будет ли? Ну вот давайте, для примера, рассмотрим тот же DCL. Если взять псевдокод — getInstance() будет выглядеть примерно так (это дикая помесь байткода с явой и ассемблером — но вроде суть понятна):

if( DCLSingleton.instance != null ) 
   jmp #end;

monitorEnter DCLSingleton.class;
if( DCLSingleton.instance != null )
   monitorExit DCLSingleton.class;
   jmp #end;

localRef = allocate( sizeof(T) );
call DCLSingleton.<init>( localRef );
DCLSingleton.instance = localRef;

monitorExit DCLSingleton.class;

end:
   return DCLSingleton.instance;

Если JIT сгенерирует прямо и непосредственно вот это — то на x86 все будет в шоколаде, ни один котенок не пострадает, никакой возможности увидеть ссылку на недоинициализированный объект не будет, потому что присвоение ссылки в shared variable идет после вызова конструктора, и x86 сам записи не переставляет — значит все потоки увидят именно сначала те записи, которые выполнены в рамках конструктора, а уж потом публикацию ссылки.

Разумеется, JIT мог бы сам переставить запись DCLSingleton.instance = localRef до вызова конструктора. Но для JIT это будет довольно опасная оптимизация, потому что он же не знает, что там, внутри DCLSingleton.<init>( localRef )? Может, там программист заложился на то, что instance == null — тогда, переставив запись JIT нарушит intra-thread semantics. Поэтому сделать такое он может только если ему на стадии оптимизации текущего метода доступна информация о коде конструктора. Современные JIT-ы не выполняют межпроцедурную оптимизацию, поэтому информацию о коде вызываемого метода JIT может получить только если он еще раньше принял решение встроить (inline) вызываемый метод. Тогда код конструктора становится частью кода текущего метода, и JIT может убедиться, что упреждающая запись instance ничего не нарушит.

А зачем бы JIT-у встраивать вызов конструктора? Встраивание — это агрессивная оптимизация, применяемая для очень горячего кода. Но ведь вся идея DCL в том-то и состоит, чтобы сделать синхронизированный код не горячим. Я уж молчу, что суть синглетона в том, чтобы конструктор вообще вызвался только один раз.

Это все мои, довольно спекулятивные предположения о том, как именно работает JIT. Они могут быть неверными в деталях, но суть остается та же — JIT довольно редко делает что-то, что нарушает hardware TSO. Один уважаемый человек™ рассказывал, что он как-то потратил день чтобы так написать DCL, чтобы он ломался бы хотя бы один раз на миллиард вызовов.

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

UPD: Перечитал и ужаснулся — какое-то неверное представление тут создается :) Что я здесь хотел сказать: что есть очевидный, но довольно узкий сегмент высоконагруженного, высококонкурентного кода, в котором небезопасная публикация будет довольно стабильно генерировать ошибки даже на x86. В "обычном" же малонагруженном коде — типа начальной инициализации — в силу жесткости аппаратной модели памяти x86, и в силу того, что наиболее агрессивные оптимизации JIT применяет только к горячему коду небезопасность публикации будет незаметна. Она либо вообще не будет создавать ошибок, либо будет создавать их настолько редко и невоспроизводимо, что вы скорее примете их за баги в JVM/железе.

Тогда зачем мне весь этот гемморой?

В самом деле, возникает немного крамольная мысль: насколько оно полезно с практической точки зрения — писать корректный по JMM код? Если ошибки будут возникать только в лабораторных условиях в одном случае из миллиарда — так может я лучше потрачу время на поиск логических ошибок в коде, которые будут проявляться чаще? Система в целом не сильнее своего самого слабого звена — это применимо как к производительности, так и к надежности. Насколько оправдано тратить время на избавление от гонок в коде, если есть такие источники ненадежности как общий недостаток мозгов у разработчиков, ошибки в JVM, баги в железе и нашествие помидоров-убийц?

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

Дело еще и в том, что, по поему мнению, правила существуют не для того, чтобы их соблюдать, а для того, чтобы в обязательном порядке включать голову когда собираешься их нарушить. Нарушение JMM по незнанию или невнимательности — это именно недосмотр, ошибка. Нарушение JMM с осознанием того, какие выгоды ты от этого получаешь, и какие косяки где и как могут возникнуть в твоем коде — это вполне нормальная инженерная практика. Лично я предпочитаю знать, какие места в моем коде опасны, а так же почему они опасны, насколько опасны, и почему я их в таком виде оставил.

Мы не будем вечно сидеть на TSO. Поддержание такой строгой модели памяти стоит довольно недешево, и сильно ограничивает дальнейшее увеличение количества ядер. У интела уже есть Itanium с ослабленной моделью памяти, очевидно будут и другие модели. Кроме того на рынок серверов сейчас активно лезет ARM — и скорее всего таки пролезет. Ну и Азул тот же самый... Все идет к тому, что иметь дело с ослабленными аппаратными моделями памяти нам все равно придется — и мне кажется, лучше готовиться к этому заранее.

lazySet: тайные страницы JMM

Подолжая раскрывать темы, недостаточно раскрытые на докладе -- сейчас про lazySet. Тема это непростая, и не потому, что там все сложно, а потому, что нужно повторить основы JMM. У меня уже давно бродит мысль написать цикл статей "Скрытые главы JMM", но все руки не доходят -- это ж надо будет advanced JMM перечитать внимательно и пристально, все теоремы разбирая... Вот, может, в старости...

Так что сейчас будет краткое введение, голопом по европам.

Дисклаймер: все что идет дальше -- это мое личное понимание JMM. Оно может быть неполным, неправильным, и вообще полной херней. Я вас предупреждал!

...Когда пишут про JMM -- почти всегда пишут про частичный порядок "происходит до" (partial happens before order). Это действительно самая ходовая часть JMM -- в большинстве практических случаев достаточно знать правила формирования ребер HB, и счастье будет уже здесь, и моментально.

Но JMM гораздо более сложная конструкция, чем только HB. JMM -- это такой набор ограничений на исполнение java кода. Эти ограничения позволяют сделать одно очень сильное утверждение относительно возможных сценариев его исполнения. А именно: если у нас в коде нет гонок (data race), то любой сценарий исполнения будет sequentially consistent.

По пунктам: что такое гонки (data race)? Пусть у нас в программе есть разделяемая (т.е используемая из >1 потока) переменная, и хоть один поток в нее пишет. Почему важна запись понятно: если никто не пишет, а все только читают, то это не интересно, никаких конфликтов. А вот если есть запись и чтение(-я) -- тогда все любопытнее. Если запись и чтение не упорядочены (через HB) то говорят, что этот набор инструкций (запись и чтения) образует гонку. Код без гонок называется data race free, DRF

В чем проблема с гонками? В том, что в них становятся заметными весь тот треш, угар и содомия (для наших читателей из Питера: здесь нет пропаганды гомосексуализма, я гарантирую это!), которую творят с вашим кодом современные оптимизирующие компиляторы и (в большей степени) современные CPU и контроллеры памяти. Все эти instruction reordering, out-of-order execution, speculative branch prediction, write combining, и прочие ужасы царизма. Это то, что, по-идее, программисту видно быть не должно -- ибо он поседеет, если это увидит. Другими словами: в коде с гонками начинают течь широко используемые абстракции -- что код исполняется так, как вы его написали, что память у нас общая и однородная, и т.п. Вы начинаете видеть грязную кухню реального мира :)

Вернемся к баранам. Что такое sequentially consistent (SC) execution? Неформально: SC для многопоточной программы -- это когда ваш код исполняется так, как будто он исполняется на единственном устройстве выполнения, безо всяких буферов, кэшей и внеочередного выполнения операций. Т.е. каждая инструкция атомарна, и ее результат сразу же доступен (виден) всем остальным потокам. Инструкции выполняются строго в том порядке, как они идут в коде. Переход от исполнения кода одного потока к коду другого возможен только в промежутке между двумя инструкциями. Еще проще -- это back to i386. Разумеется, реально ваш код может исполняться как угодно -- но результат в любой точке должен быть только такой, какой возможен при каком-нибудь SC сценарии.

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

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


Теперь, когда мы прониклись величием решаемой JMM задачи, можно уже отметить одну мелочь: для того, чтобы доказать свойство (DRF -> SC) одного частичного порядка HB недостаточно. Нужны еще две важных вещи.

Во-первых это причинность (causality). Неформально: что у любого события есть первопричина. Не допускаются циклы причинности: когда А является причиной для Б, а Б -- является причиной для А. Причинность, в частности, запрещает в яве значениям переменных возникать из воздуха ("out of thin air") -- для любого прочитанного из переменной значения должна существовать в коде программы операция записи, которая это значение туда записала (и она не должна происходить после этого чтения). Для явы это архиважно, потому что если бы значение ссылки могло возникнуть из ниоткуда -- вся безопасность языка и среды накрылась бы медным тазом.

Во-вторых, это Total Synchronization Order. В JMM некоторые операции (захват/освобождение монитора, чтение/запись волатильной переменной, и всякая эзотерика, типа условных "первое/последнее действие в потоке", операция запускающая поток, операция обнаруживающая завершение потока... см подробнее JLS 17.4.2) объявлены как Synchronized Actions. Особенность этих SA в том, что они образуют Total Synchronization Order. Ключевое здесь именно total -- полный порядок, в отличие от partial happens-before order, который частичный порядок.

Частичный порядок означает, что между некоторыми операциями есть точно определенный порядок -- А всегда (во всех сценариях исполнения) идет до Б. А между некоторыми операциями такого однозначного порядка нет -- в одних сценариях исполнения В может идти до Г, в других -- Г до В. И более того -- в одном и том же сценарии исполнения один поток может видеть сначала результат Г, а потом результат В, а другой поток -- сначала результат В, а потом Г. Т.е. порядок В и Г не определен в обоих смыслах: и поскольку он в разных сценариях (запусках) может быть разным, и поскольку даже в одном сценарии он может видиться разным с разных точек зрения.

А вот полный порядок означает, что между любыми двумя операциями всегда есть какой-то порядок. Либо А до Б, либо Б до А -- третьего не дано. И этот порядок всеми виден одинаково.

То есть тот факт, что synchronization actions образуют полный порядок означает (в переводе с математического на русский), что любая пара synchronization actions всегда упорядочена, и этот порядок виден всеми потоками программы одинаково.

Получается, что synchronization actions -- они уже sequentially consistent. И чтобы получить SC для всей программы нам осталось только как-то "растянуть" эту sequentially consistency на все остальные инструкции в коде. И мы это делаем с помощью частичного порядка happens-before -- присоединяя по транзитивности к уже существующим и всегда упорядоченным synchronization actions обычные инструкции. И если нам удастся по транзитивности присоединить все инструкции в программе (а это удастся если в программе нет гонок) -- то мы и получим SC для всей программы в целом!

То есть, если очень кратко -- мы создаем в программе становый хребет из synchronization actions, которые по-определению sequentially consistent. И ребрами HB присоединяем к нему то, что можно присоединить. Если в программе нет гонок -- то нам удастся присоединить все инструкции, и вся программа окажется доказуемо SC.


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

volatile va = 0;
volatile vb = 1;
a = 0;

//Thread 1:
va = 1;
a = vb;

//Thread 2: 
print( "va=" + va + ", a=" + a ); 
//может ли вывести "va=0, a=1"?

Может этот код вывести "va=1, a=0"? Т.е. может ли быть a = vb переставлено до va = 1?

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

Однако если допустить, что такая перестановка возможна и допустима, то мы получаем ситуацию, когда Thread 1 видит (в соответствии со своей внутри-поточной семантикой) сначала волатильную запись va=1, а потом волатильное чтение a=vb. А Thread 2 видит другой порядок -- сначала чтение vb, потом запись va. А это означает, что у нас нет единого, согласованного между всеми потоками порядка SA-операций. То есть такая перестановка недопустима, ее нужно запрещать.

Вот здесь мы подходим (наконец-то! вы там еще не уснули?) различию между volatile write и lazySet.

Для того, чтобы обеспечить обычное ребро HB между volatile write и read одной и той же переменной достаточно всего двух барьеров -- store-store до записи:

membar(store&load|store)
store va

и load-load после чтения:

load va
membar(load|store&load)

Этого достаточно, чтобы все, что было записано до store va было гарантированно видно после load va. Но этого не достаточно, чтобы обеспечить TSO -- нужно еще запретить реордеринг для synchronized actions. И вот для этого нужен дополнительный StoreLoad после записи:

membar( store&load | store )
store va
membar( store | load )

Именно отсутствием этого store-load и отличается lazySet. lazySet не является sychronized action, он не участвует в total synchronization order, и обходится без соответствующего барьера. А store-load -- единственный необходимый явный барьер на x86 (остальные выполняются неявно, в силу довольно большой строгости аппаратной модели памяти x86). Реализуется он как lock add %esp, 0x00 -- и это довольно дорогая операция. Поэтому если вы можете доказать корректность своей программы без того, чтобы какая-то конкретная волатильная запись была частью TSO -- можно на нем сэкономить. Правда, доказать это весьма непросто. Единственный известный мне метод -- это прислать код в concurrency-interest на ревизию Дагу Ли лично :)

[*] JSR-133 Cookbook for compile writers

final-поля для безопасной публикации

В догонку к обсуждениям семантики final-полей. Обычный класс, с изменямыми полями, сложно безопасно опубликовать через data race (т.е. без синхронизации):

sharedRef = new Mutable();

Но можно опубликовать через "обертку" -- класс с final-ссылкой:

sharedRef = new ImmutableReference(new Mutable());

И у меня давно уже бродит идея -- почему бы не сделать сам класс для себя "публикующей оберткой"?

public class SelfPublisher {

    private int value;

    private final SelfPublisher safeThis;

    public SelfPublisher( final int value ) {
        this.value = value;
        this.safeThis = this;
    }

    public int getValue(){
        return safeThis.value;
    }
}

Насколько я вижу -- это позволит совершенно безопасно публиковать его через даже data race. Ценой -- увы -- дополнительных затрат памяти на избыточное поле. Ну и дополнительной операции присваивания в конструкторе.

P.S. Код -- уродлив, по моим критериям изящества. Это, скорее, трюк, чем пример для подражания :) И use case для него тоже довольно туманен. Но сама идея мне показалась любопытной.

Гарантии для final-полей

На днях была интересная переписка с Глебом Смирновым, автором статьи про модель памяти на Хабре. Мы обсуждали тонкости спецификации final-полей. Камнем преткновения был такой пример:

public class A {
    public int value;
    public final int finalValue;

    public A(final int value, final int finalValue) {
        this.value = value;
        this.finalValue = finalValue;
    }
    ....
}

//где-то в коде Thread1:
public A sharedReference = new A();

//где-то в коде Thread2:
if( sharedReference != null ){
    //
    final int finalValue = sharedReference.finalValue;
    final int value = sharedReference.value;
}

Довольно общеизвестно, что спецификация final-полей в JMM гарантирует, что доступ к .finalValue корректный (== запись значения в .finalValue внутри конструктора происходит до чтения .finalValue через общедоступную ссылку, присвоенную после завершения конструктора). Вопрос в том, является ли корректным в том же смысле чтение поля .value? Т.е. можно ли сесть на хвост (piggyback) той магии, которая приводит к корректной передаче значений final-полей между потоками?

На первый взгляд кажется, что можно -- ведь обычные ребра happens-before транзитивны: A hb B, B hb C => A hb C. При этом дано, что действия, идущие до А в program order идут до А и в happens-before order -- т.е. в рамках одного потока частичный порядок HB совпадает с порядком инструкций в коде программы. Значит, поскольку присвоение значения полю .value в конструкторе происходит до присвоения .finalValue, а присвоение .finalValue происходит до чтения в потоке 2, а оно, в свою очередь, происходит до чтения .value в потоке 2 -- то по транзитивности получается, что присвоение .value в конструкторе happens-before чтения .value в потоке 2.

Однако©, на самом деле© -- это неправда. Ну, мне так кажется :)

---

Во-первых, определение отношения порядка в случае операций с final-полями содержит такое уточнение (Евангелие от ИоанаJMM, 17.5.1): Given a write w, a freeze f, action a (that is not a read of a final field), a read r1 of the final field frozen by f and a read r2 such that hb(w, f), hb(f, a), mc(a, r1) and dereferences(r1 , r2), then when determining which values can be seen by r2, we consider hb(w, r2) (but these orderings do not transitively close with other happens-before orderings). (выделение мое)

То есть то отношение порядка, порождаемое семантикой final-полей -- это такое особое happens-before. Оно почти как обычное happens-before, но не транзитивно с ним.

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

---

Чтобы определить семантику final-полей нам понадобится несколько новых терминов. А именно:

Заморозка (freeze) -- это специальное действие, которое происходит в момент завершения (нормального, или с выбросом исключения) конструктора объекта, содержащего final-поле.

Помимо заморозки нам понадобятся еще два специальных частичных порядка (кроме уже всем знакомого happens-before):

• порядок разыменования (dereference chain, обозначается далее как dereferences(a,b))
• порядок доступа к памяти (memory chain, обозначается далее как mc(a,b))

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

---

То, что идет дальше, лично мне кажется смесью определений самих порядков ("что такое MC/DC"), и условий (которые формулируются, в том числе, в терминах только что введенных MC/DC), которым должны удовлетворять допустимые по JMM сценарии исполнения. Мне это кажется очень неудобным для восприятия, но я оставляю эту часть как она есть

Порядок разыменования, dereferences: Если A -- чтение/запись поля объекта О, причем О инициализирован не текущим потоком, тогда в текущем потоке должна существовать операция чтения R, которая видит адрес объекта О, и такая, что dereferences(R, A). Другими словами: операция чтения адреса объекта должна происходить до (в смысле порядка разыменования) любой операции чтения/записи полей объекта.

Порядок доступа к памяти, mc:

1. Если чтение R видит результат записи W, то mc(W,R) (запись происходит до чтения в смысле частичного порядка доступа к памяти)
2. Если dereferences(А,Б) (А происходит до Б в смысле порядка разыменования), то и mc(А, Б) (А происходит до Б и в смысле порядка доступа к памяти) Т.е dereferences является "подмножеством" mc.
3. Если W -- запись адреса объекта О, производимая не тем потоком, который О инициализировал, то, в этом же потоке должно существовать некоторое чтение R, которое видит адрес объекта О, и такое, что mc(R,W) (R происходит до W в смысле порядка доступа к памяти)

---

Теперь само определение семантики final-полей:
Дано:

1. Некоторая запись W
2. Заморозка F
3. Произвольное действие с памятью (кроме чтения final-поля) A
4. Чтение R1 финального поля, замороженного F
5. Чтение R2

Пусть между собой эти действия связаны такими соотношениями: hb(W,F), hb(F, A), mc(A, R1), dereferences(R1, R2).

Тогда: определяя, какие значения могут быть прочитаны R2, мы можем полагать, что W и R2 связаны порядком happens-before: hb(W, R2). Но: это отношение порядка не транзитивно с другими отношениями порядка HB.

Отдельно заметим, что отношение порядка разыменования (dereferences) рефлексивно -- т.е. dereferences(a,a) всегда верно. Поэтому в определении выше R2 может совпадать с R1.

Только те записи, что подходят под определение семантики final-полей -- гарантированно упорядочены до чтения final-поля. (Я понимаю этот пункт просто как еще одно напоминание, что гарантии, даваемые для final-полей распространяются ровно настолько, насколько указывает данное определение, и не дальше)

---

Теперь попробую изложить то же самое на простом языке и более развернуто.

hb(W,F): Наша "некоторая запись" происходит до завершения конструктора, или до "заморозки", что то же самое в данном случае.

hb(F, A): "некоторое действие с памятью" происходит после завершения конструктора ("заморозки").

mc(A, R1): Чтение final-поля видит результат "некоторого действия с памятью"

dereferences(R1, R2): R2 это либо само чтение значения поля (т.е. R2==R1), либо это чтение поля/элемента какого-то объекта, доступного по цепочке ссылок, начинающейся в final-поле.

Что это за загадочное "некоторое действие А"? Насколько я понимаю смысл -- это должна быть публикация ссылки на объект. Но точнее описать не могу -- для меня пока загадка, почему же это действие описано настолько абстрактно -- может ли А быть чем-то кроме публикации ссылки?

---

Уф. Выдыхаем...

Что можно видеть из этого определения? Во-первых, возможности "сесть на хвост" -- по крайней мере, в том смысле, в котором был пример в начале статьи -- нельзя. Семантика final-полей гарантирует видимость записей, идущих до freeze только для тех чтений, что идут через цепь разыменований, начиная с самого final-поля. Поскольку увидеть .value через эту цепь нельзя, то видимость значения, записанного в это поле в конструкторе не гарантируется.

В этом определении мне интересны еще несколько вещей (помимо его зубодробительности, конечно).

Во-первых, оно идет в некотором смысле в обратном направлении по отношению к обычным определениям JMM. В "обычном" определении логика такая: мы сначала определяем упорядоченность действий (через набор правил порождения ребер happens-before + транзитивность), а потом говорим, что если hb(А,Б) => то Б гарантированно видит результат действия А. Здесь же ситуация обратная: мы говорим, что если Б видит результат А => то определенные действия происходящие до А происходят до определенных действий, происходящих после Б.

Во-вторых здесь необычная ситуация с определением того, для каких операций чтения/записи пригодно это определение. Формально все начинается с любой операции записи, идущей до заморозки. Но в конце оказывается, что ребро HB можно установить по этому определению начиная с любой записи -- да не к любому чтению. А поскольку ребро это еще и не транзитивно -- то получается, что ограничивая спектр операций чтения, на которых ребро может заканчиваться -- мы тем самым ограничиваем и спектр операций записи, на которых оно может начинаться. А именно: ребро может начинаться только на таких операциях записи, результаты которых могут увидеть чтения из того самого ограниченного списка. Для других операций записи эффект ребра HB просто не наблюдаем :) Причем если бы нам оставили транзитивность -- мы бы могли по транзитивности продлить ребро HB с "разрешенного" чтения до следующей в program order операции, которая уже могла бы быть любым (в том числе и "не разрешенным") чтением. Но у нас транзитивность отобрали. И поэтому вместо любой операции записи это определение позволяет проводить ребра HB только от таких записей, которые а) происходят до завершения конструктора б) результаты которых видны по цепочке ссылок начиная с final-поля, инициализированного в этом конструкторе.

В третьих, обратите внимание, что от записей W не требуется, чтобы они происходили внутри конструктора. Они могут происходить где угодно, только бы была возможность показать, что они происходят до завершения конструктора (до заморозки). Это как раз и означает, что мы можем передать в конструктор объекта сколь угодно сложный объектный граф, заполненный где-то на стороне (но гарантированно до окончания конструктора), присвоить в конструкторе ссылку на него final-полю, и далее мы можем быть уверены, что всё его содержимое будет видимо любому потоку, читающему граф через разыменование final-поля. Это тоже своеобразный piggybacking, и вот такой piggybacking моделью памяти джавы разрешен.

StackOverflow: AtomicReferenceFieldUpdater semantic

Очередной интересный вопрос на stackoverflow -- неочевидное место в документации к AtomicReferenceFieldUpdater:

Note that the guarantees of the compareAndSet method in this class are weaker than in other atomic classes. Because this class cannot ensure that all uses of the field are appropriate for purposes of atomic access, it can guarantee atomicity and volatile semantics only with respect to other invocations of compareAndSet and set.

Автору вопроса (да и мне теперь тоже) не очень понятен смысл фразы "weaker guarantees" -- в чем именно-то они "слабее"?. Что за загадочная фраза "all uses of the field are appropriate for purposes of atomic access" -- какие использования поля здесь имеются в виду "подходящими" для атомарных операций, а какие -- нет?

Меня сильно смущает приводимый пример с тем, что атомарность и волатильность поддерживаются только между вызовами compareAndSet() и set(). А что с обычным присвоением (this.value = ...)? Я-то наивно считал, что set() полностью эквивалентен по семантике обычному присвоению значения полю (поля, с которыми работает *Updater, обязаны быть volatile -- это проверяется при создании *Updater-а), просто set() это то же самое, только через reflection, с соответствующими дополнительными проверками и накладными расходами. Получается -- это не так?

Исследования кода показывают, что, например, в обычных AtomicXXX классах set() -- это просто присвоение:

public class AtomicReference<V>  implements java.io.Serializable {
    //...
    private volatile V value;
    //...
    public final void set(V newValue) {
        value = newValue;
    }

В AtomicReferenceFieldUpdaterImpl это несколько иначе:

public void set(T obj, V newValue) {
        if (obj == null || obj.getClass() != tclass || cclass != null ||
            (newValue != null && vclass != null &&
             vclass != newValue.getClass()))
           updateCheck(obj, newValue);

        unsafe.putObjectVolatile(obj, offset, newValue);
    } 

Но название putObjectVolatile(..) как бы намекает, что это то же самое, что и обычное присвоение значения волатильному полю.

Будем ждать прояснения ситуации.

UPD: В дискуссии с ryakh прояснилось, что же имеется в виду. Судя по всему, этот любопытный пункт в документации оставлен для платформ, на которых нет аппаратной поддержки для атомарных CAS-ов (или чего-то, им равномощного). В этом случае реализация RMW-операций потребует использования програмных блокировок. Но блокировки могут обеспечить атомарность только по отношению к другим операциям, защищенным той же блокировкой. Таким образом возникает выбор: либо на таких платформах надо все операции volatile store защищать программными блокировками -- что будет дико неэффективно. Либо оставлять обычные операции чтения/записи volatile-переменных как есть, а блокировками защищать только операции классов AtomicXXX и XXXUpdater. Но во втором случае мы получаем потенциальную возможность для обычной записи volatile a = 3 пересечься с атомарным изменением

synchronized(internalLock){ 
    if(a == 1) {
        /*a=3 может вклиниться сюда*/ 
        a = 2; 
    }
}.

Отсюда и получается ограничение, описанное в документации: если вы используете XXXUpdater для выполнения CAS-ов над каким-то полем, то вы должны забыть про обычную запись в это поле, и использовать для этого только метод XXXUpdater.set() -- только тогда рантайм может гарантировать, что атомарные изменения действительно будут атомарными на всех доступных платформах.

Хочу заметить, что чтение можно спокойно делать напрямую, без XXXUpdater.get() -- чтение, очевидно, никак не интерферирует с атомарными изменениями.

Мне кажется, это еще один пример того, что write once, run anywhere -- слоган довольно условный. Есть масса способов написать на джаве вполне рабочую программу, которая будет годами отлично выполнять свои функции на целом спектре аппаратных платформ -- но не будет полноценно кроссплатформенной из-за какой-нибудь такого рода пропущенной "мелочи".

На этом примере так же легко можно видеть, как желание дать разработчикам более низкоуровневые инструменты вступает в противоречие с кроссплатформенными абстракциями. В самом деле, если бы у нас были только классы AtomicXXX -- полностью инкапсулирующие все манипуляции со своим значением -- никаких уточнений в документацию и не потребовалось бы. Но нам дали XXXUpdater, с помощью которого можно несколько улучшить компоновку объектов в памяти, и уменьшить затраты памяти -- и в нагрузку мы получили еще и тонкости взаимодействия между атомарными изменениями через Updater, и обычными записями...

Puzzler из concurrency-interest

Замечательную штуку вчера продемонстрировал Hans Boehm в листе рассылки concurrency-interest (любопытно, что тема началась с запроса на легализацию разных трюков с s.m.Unsafe -- дискуссии concurrency-interest частенько очень сильно плутают). Ханс писал про опасность методов типа lock.tryLock() -- в смысле сложности их правильного понимания. Вот, например, код:

//Thread 1:
x = 17;
l.lock();

//Thread 2:
while ( l.tryLock() ) {
    l.unlock();
}
... x ...  // какое значение у x в этой точке?

Чтобы ответить на вопрос, обязан ли x быть равным 17 в конце второго потока надо ответить на вопрос "есть ли здесь data race?"

С одной стороны, с точки зрения "универсального" определения программа считается data race free если для всех sequentally consistent трасс над ней отсутствует конкурентный доступ к данным. В данном случае, кажется, это выполняется -- во всех SC трассах сначала в x пишется 17, и только потом x читается -- поэтому кажется, что код data race free, а значит после цикла во втором потоке x должен быть равен 17.

С другой стороны, JMM определяет data race free несколько иначе -- все конкурирующие доступы к данным должны быть упорядочены через happens-before. Поскольку между потоком 1 и 2 нет никаких ребер HB, то доступы к x на запись и на чтение в разных потоках не упорядочены через HB, и, следовательно, они образуют гонку -- а значит, значение x после цикла во втором потоке не определено.

---

Найти правильную точку зрения сравнительно просто -- достаточно вспомнить, что критические секции (и вообще, и в java в частности) имеют семантику "можно войти, нельзя выйти" (roach motel semantics) -- код может вноситься внутрь секции, но не может выноситься из нее. Это значит, что x=17 и l.lock() в потоке 1 могут быть переупорядочены -- присвоение может быть внесено в критическую секцию. Это сразу дает право сказать, что здесь таки есть гонка, и значение x во втором потоке действительно не определено.

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

А ошибка в рассуждениях в том, что, когда мы придумываем SC трассы над кодом, мы делаем два неявных предположения о том, что такое лок. Первое из них -- что лок неявно содержит некое состояние -- каким потоком он сейчас захвачен. Это состояние меняется вызовами lock()/unlock(), а так же запрашивается, и, возможно, меняется вызовом tryLock(). И это предположение верно -- у лока действительно есть это внутреннее состояние.

Но есть еще и второе предположение -- что изменения этого состояния методами lock()/unlock()/tryLock() -- имеют семантику volatile store/load. И вот это уже не верно. В соответствии со спецификацией, lock()/tryLock() имеют (==обязаны иметь) только семантику acquire, а unlock() -- только семантику release. А это значит, что мы не все трассы рассмотрели.

Путаницы добавляет тот факт, что на реализация блокировок обычно делается через CAS, а CAS на x86 имеет семантику full fence. То есть на x86 для любой реализации монитора (из мне известных) lock() будет иметь семантику full fence просто в силу того, что аппаратная модель памяти соответствующего процессора более слабых барьеров не предусматривает. И код Ханса будет скорее всего работать корректно (==не будет содержать гонок). Но это особенности именно аппаратной модели памяти конкретного процессора. Скажем, на пресловутых Azul-ах есть CAS без семантики барьера, и есть односторонние барьеры. И там вполне можно реализовать (правда, не на уровне java, а разве что на уровне интринсиков JIT-а) монитор, у которого lock() будет иметь честную семантику только acqiure.

Собственно, если я правильно понял Ханса, он и обращает внимание на то, что с введением методов типа tryLock() монитор становится легко принять за этакую неявную volatile переменную -- что не соответствует реальной семантике операций с мониторами.

AtomicXXX.lazySet() -- разъяснения

По совету друга я вознес мольбу Господу о ниспослании мудрости, и Господь послал мне этого. Немного. Зато несколько раз -- с первого раза я не понял. Произошло это посредством листа рассылки concurrency-interest -- ну, нечего придираться, пути господни неисповедимы. Начало треда я в архивах не нашел почему-то, так что могу дать ссылку только на продолжение: вот.

Вкратце:

Что касается спецификации:
lazySet был введен после последней редакции JMM, поэтому в JMM нет описания такого отношения порядка, который он порождает. Т.е. по сути javadoc специфицирующий lazySet можно рассматривать как расширение JMM. Аналогичным свойством обладает weakCompareAndSet -- его ordering constraints тоже не формализуются в текущей редакции JMM. Идет обсуждение того, как включить такие вещи в очередную редакцию JMM, но пока в попутчиках согласья нет, и вряд ли очередная редакция JMM выйдет в ближайшее время. Вообще варианты более "тонких" мембаров, частным случаем которых является lazySet (== Fences.orderWrites + store) планируется внедрять в специальный класс Fences, соответственно все обсуждение подобных вещей обычно сосредоточено вокруг него. И черновики будущей спецификации можно посмотреть в его class-javadoc. Я там пока нифига не понял, но попытки буду продолжать.

Что касается текущего состояния:

Да, то, что написано в lazySet javadoc действительно означает, что все записи, произведенные до lazySet() гарантированно станут видимы до того, как станет видимым запись lazySet(). При этом чтения, идущие до lazySet() в program order вовсе не обязаны реально происходить до него -- они могут быть переупорядочены и отложены, и завершиться уже после завершения lazySet() -- в этом, собственно, отличие от обычного volatile store.

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

На самом деле я здесь не вижу существенной разницы с обычным volatile store -- нигде в JMM не прописано, что volatile store должен завершиться немедленно. JMM задает лишь ограничения на то, что все записи и чтения идущие до vstore в program order действительно будут исполнены и их результаты видимы до того, как будет исполнена и видима vstore.

Что касается текущей реализации:

Хотя формально запись может быть отложена на сколько угодно, фактически все существующие JVM реализуют lazySet() консервативно -- выполняют запись немедленно. То есть запись может быть отложена уже только процессором, задержавшись в его store buffer.

Таким образом, использование lazySet в disruptor, похоже, в целом легально, и ускорение, им создаваемое -- вполне объяснимо.

P.S. В процессе разбирательств выяснилось, что некоторые вещи в JMM я до сих пор понимаю больше интуитивно. Кажется, в ближайшее время у меня будут посты на эту тему

AtomicXXX.lazySet() strikes back

Наткнулся тут на любопытную вещь -- я всегда был уверен, что в JMM все поведение всегда можно описать с помощью несложного набора правил построения ребер happens-before. Ну, то есть, я не говорю, что применение этих правил всегда просто -- законы Ньютона тоже не очень сложные, а какой мрак и ужас из них получается, скажем, в небесной механике и движении твердого тела -- но сами правила довольно просты, и применимы к любому java-коду. Но похоже это не совсем так. Этот самый AtomicXXX.lazySet() мутит воду.

Простое объяснение -- неволатильная запись в волатильную переменную -- меня только запутывает. До этого момента в джаве, вообще-то, не было волатильной/не волатильной записи в отрыве от типа поля (ну, если не трогать сатанинский Unsafe). То есть если поле волатильное -- то все операции с ним волатильные, поле не волатильное -- все операции не волатильные.

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

Это не праздный интерес. В коде Disruptor-а встречается такая идиома:

AtomicLong sequence = new AtomicLong();
...
//поток 1: издатель
...write some values into shared objects...
sequence.lazySet(seq);

//поток 2: обработчик
while( sequence.get() != seq ){
   //spin wait
}
...read shared objects fields

По смыслу кода понятно, что автор его уверен -- последовательность sequence.lazySet()/get() обеспечивает завершение всех операций записи, идущих до нее в program order, и видимость результатов этих операций из второго потока. Другими словами -- это практически happens-before edge. Но вот с чего он так в этом уверен -- для меня совершенно не очевидно.

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

А с другой стороны -- я сейчас гоняю бенчмарки, разбирая по частям disruptor и вытаскивая какие компоненты ключевые для его производительности. И вот оказывается, что если вместо lazySet использовать обычный set() -- скорость падает в 2 раза примерно (это без нагрузки -- на холостом ходу). То есть смысл определенно есть -- но вот надежен ли этот способ оптимизации -- мне как-то неочевидно.

Задал вопрос на stackoverflow -- посмотрим, может там понимают

AtomicXXX.lazySet(...)

Еще один любопытный метод в атомиках -- AtomicXXX.lazySet(T value). Присваивает значение переменной "когда-нибудь" (eventually). Спроектирован для end-of-life cleanup в неблокирующих структурах данных, когда надо очистить значение переменной (например, записать туда null), и больше с этой переменной ничего делаться не будет, поэтому в принципе все равно, когда именно значение будет реально записано (и увидено другими потоками), но важно, что когда-нибудь это-таки произойдет (чтобы GC гарантированно мог собрать "отвязанный" объект). По-сути получается, что это non-volatile write в волатильную переменную.

О сколько нам открытий чудных
Готовит javadoc-ов дух...

weakCompareAndSet

В классах AtomicXXX, наряду с известным методом compareAndSet (CAS) есть еще довольно странный метод weakCompareAndSet (WCAS). Не так давно я наткнулся на довольно длинную дискуссию в concurrency-interest. Хотя сама дискуссия довольно уже старая (2006г) но для меня содержала много нового, чем хочется поделиться.

Итак, чем отличается weakCAS от обычного CAS?

1. Может откатиться (ничего не изменить и вернуть false) даже если значение expected совпадает с текущим значением в ячейке памяти (другими словами -- может откатиться "без причины")
2. Не создает (=не обязан создавать) ребра happens-before

Теперь чуть подробнее:

С первым пунктом все довольно просто -- обычный CAS откатывается только в случае, значение в ячейке памяти не совпадает с ожидаемым. Если CAS вернул false -- вы можете быть уверены, что actualValue!=expectedValue. В случае с weakCAS такой уверенности нет -- значения могут совпадать, а weakCAS все равно откатится. Разумеется, можно сделать цикл с проверкой, но есть тонкости -- часто доказательство lock-free для алгоритма базируется на том, что CAS либо удался (и тогда текущий поток "продвинулся"), либо нет (и это означает, что "продвинулся" какой-то другой поток) -- в итоге всегда получается общий прогресс. С weakCAS такое рассуждение уже не прокатит -- формально говоря, он может откатываться сколько пожелает.

Второй пункт важнее и интереснее. Обычный CAS имеет семантику volatile read+write. В частности, это означает, что между двумя CAS-ами одной переменной всегда существует ребро happens-before. Именно это позволяет использовать его, например, для создания спин-локов. weakCAS такой семантики не имеет, никаких ребер не создает, и сделать на его основе спин-лок не получится.

Откуда же есть пошел weakCAS? Ну, если верить concurrency-interest, мотивация была в том, что не на всех моделях процессоров есть инструкция вида CAS. На некоторых есть альтернативный вариант -- load-linked/store conditional. CAS и LL/SC эквивалентны в том смысле, что любой алгоритм, который можно реализовать через CAS можно реализовать и через LL/SC. Но при этом LL/SC откатывается если значение по указанному адресу изменялось с момента чтения (т.е. в случае сценария ABA CAS пройдет, а LL/SC откатится). Есть еще варианты -- например, какие-то реализации LL/SC могут откатываться если изменилась любая ячейка памяти, лежащая на той же cache line, что и нужная. Чтобы на этих процессорах эмулировать честный CAS потребуется цикл с перепроверкой. Но в некоторых случаях "честности" и не нужно, и тогда можно использовать слабый CAS без дополнительных оберток.

Вторая тонкость -- на мой взгляд, более важная -- про happens before. Честный CAS, как я уже писал, состоит, собственно, из двух частей: атомарной проверки-и-присвоения, и двустороннего мембара (full fence). И если первая часть как-то очевидна (само название операции об этом и говорит), то вторая -- это некоторое дополнительная фича именно java-api для AtomicXXX. Не во всех процессорах инструкции CAS обязательно выполняют full fence, и, более того, далеко не во всех алгоритмах, требующих атомарной операции compare-and-set, обязательно требуется и full fence в каждом случае. Между тем, full fence это операция, потенциально, с большой латентностью (особенно, если ядер достаточно много). Поэтому, особенно для многоядерных систем, неплохо бы иметь возможность делать CAS без full fence, когда это необходимо. weakCAS именно такую возможность и предоставляет.

Почему тогда weakCAS малоизвестен? Ну просто потому, что в самых распространенных интеловских и AMD-шных процессорах инструкции "CAS без full fence" просто нет -- там есть только LOCK CMPXCHG, который делает точно то, что требуется спецификацией AtomicXXX.compareAndSet(...). Поэтому на этих машинах weakCAS == CAS.

Вторая причина состоит в том, что довольно сложно решить, где именно может быть применим CAS без fence. В concurrent-interest на эту тему пишут, что "если вы не Daug Lea, и у вас нет крайне веских причин оптимизировать какой-то CAS в вашем коде -- забудьте про weakCAS".

Когда же можно подумать об его использовании? Первый, очевидный, случай -- это счетчики. В частности, в дискуссии concurrent-interest выступал Cliff Click, рассказывая, что ему, для Azul box с 700-800 ядрами, требовались performance counter-ы, которые бы как можно меньше тормозили (на Azul, как я понимаю, есть более богатый выбор вариантов инструкции CAS -- и с барьерами, и без них). В самом деле, если все, что вам нужно -- это атомарный инкремент некоторой переменной -- довольно глупо в пару к нему покупать еще и full fence. Особенно если у вас 800 ядер, частенько выполняющих этот инкремент. Более общо: если вам не нужна синхронизация, а нужна только атомарная операция типа "считать-изменить-записать" -- можно использовать weakCAS, и радоваться от мысли, что, если когда-нибудь ваш код будет выполняться на Azul-ах (какая честь для вашего кода!) -- он будет работать быстрее :)

Второй случай, менее очевидный и более сложный -- когда у вас в алгоритме есть несколько последовательных CAS-ов, и вы понимаете, что "ключевым" (linearization point) из них является только какой-то один -- тогда именно его можно оставить честным, а предыдущие -- weakCAS. Мне это напоминает технику synchronization piggybacking.

Вообще, после таких обсуждений я начинаю понимать Daug Lea, который хочет добавить в джаву класс Fences с методами типа orderReads(..), orderWrites(), orderAccesses(), reachabilityFence(..)

Снова о reflection

Я уже как-то писал, что при перезаписи final полей через reflection "гарантируются все необходимые барьеры памяти". Но я немного пораскинул мозгами, и задался новым вопросом -- а какие именно барьеры здесь необходимы? Ведь все остальные примитивы синхронизации в JMM описываются не через барьеры памяти, а через happens-before-edge -- ребро частичного порядка операций. Т.е. для того, чтобы какая-то операция чтения в одном потоке гарантированно увидела какую-то операцию записи в другом потоке оба потока должны что-то сделать (потому как ребро-то соединяет два узла графа) -- синхронизироваться на одном мониторе, скажем, или читать одну volatile переменную (и тогда и запись и чтение будут волатильными, с соответствующими последствиями в виде, в частности запрета целого класса оптимизаций для них).

Но если я записываю final переменную через reflection -- что должно выступать в роли второго узла для happens-before-edge? Т.е. при каких условиях очередная операция чтения final переменной a из потока Thread2 увидит новое значение этой переменной, записанное туда потоком Thread1 через reflection?

...Потому что если ответ будет в духе "ближайшая же операция чтения" -- то это очень круто, потому что тогда таким образом можно реализовывать ассиметричную синхронизацию. Т.е. скажем, fixed-size hash-map-based cache из недавнего поста можно будет сделать dynamically resizeable без потерь в скорости чтения -- просто при расширении новый, расширенный массив записывать в final поле через reflection.

...Но не очень понятно, как такое можно реализовать технически. Т.е. финальность поля ведь дает возможность JIT-у делать множество специфических оптимизаций (ну, мне так кажется :) ) -- что ж теперь, их все откатывать?

UPD: Как мне правильно подсказали в комментариях -- хрен вам, а не ассиметричная синхронизация. JLS говорит, что единственный способ использовать перезапись final полей корректно -- это выполнять ее сразу после создания объекта, и до того, как ссылка на него будет опубликована и доступна другим (потокам). В остальных случаях значение-то поля запишется, но видимости его никто не гарантирует, просто потому, что JVM не обязана откатывать уже выполненные оптимизации, сделанные в предположении, что значение финальных полей не изменяется. Т.е. мембары-то JVM может и выполнит (а обязана ли?), но если где-то JIT при оптимизации заложился на неизменность значения финального поля, и, скажем, скэшировал его значение в локальную переменную (а то и в регистр процессора) -- то JVM имеет полное право продолжать выполнять этот оптимизированный код, игнорируя тот факт, что значение поля уже изменилось.

Даже более того -- если значение финального поля инициализируется константой (compile-time-constant) -- то даже изменение сразу после создания может не сработать, потому что значение поля в каких-то случаях может быть инлайнировано еще javac.

Еще с JavaOne

Вспомнился еще один вопрос по JMM, который прояснился на JavaOne -- что происходит с гарантиями видимости final полей, которые дает JMM, если final поля перезаписываются через reflection? Оказывается, ведут они себя прилично -- перезапись final полей через reflection гарантирует выполнение всех mambars/fences, необходимых, чтобы перезаписанное значение стало доступным всем потокам.