java synchronization gone wild and back

[juan_gandhi]

Hey, so, you, like everyone else, decided to make your static initialization thread-safe. You have a singleton that is hard to instantiate, and You have something like this:

static My worker;

static My worker() {
  if (worker == null) {
    worker = new MyImplementation();
  }
  return worker;
}

and it does not work, because, say, a dozen of servlet threads in parallel are trying to reinitialize your singleton like crazy; a minute that it takes to instantiate one, turns into 12 minutes, since all 12 are trying to do the same.

Okay, you synchronize it:

static My worker;

static synchronized worker() {
  if (worker == null) {
    worker = new MyImplementation();
  }
  return worker;
}

In this case you lock execution on the whole class; your class may have a bunch of other singletons, and they will all stand in line waiting for this specific singleton to be retrieved - looks stupid, right? so you introduce a gentle check:

static My worker;

static worker() {
  if (worker == null) {
    synchronized {
      worker = new MyImplementation();
    }
  }
  return worker;
}

See, before instantiating, you check whether it is instantiated already.

The trouble is, your twelve threads will get through this check and wait on the same barrier before synchronized block, and then will instantiate the singleton, one after another, taking 12 minutes in total. Okay, you get angry, you open a book and steal a solution, the famous double-check trick:

static My worker;

static worker() {
  if (worker == null) {
    synchronized {
      if (worker == null) {
        worker = new MyImplementation();
      }
    }
  }
  return worker;
}

Now you feel good, the threads would not reinitialize the same singleton, because when the second threads penetrates the synchronized block, worker is already not null. You feel good... but then you open Josh and Neal's Java Puzzlers, and see that oops, this won't work on a multiprocessor machine. Why? See, by the time the first thread leaves the syncrhonized block, the value of worker may not reach the memory shared by the threads.

So, the solution suggested is this:

static My worker;
private interface HR {
  My getWorker();
}

private static HR catbert = new HR() {
  My worker = new MyImplementation();
  My getWorker() {
    return worker;
  }
}

static worker() {
  return catbert.getWorker();
}

See, the trick is that the singleton is provided by a static class, which is loaded strictly once, which is guaranteed by the class loader.

Now enters "new Java 5", not sure which one, 1.5.0.6 or 1.5.0.7. Bug fixed. All you have to do is declare My worker volatile:

volatile static My worker;

static worker() {
  if (worker == null) {
    synchronized {
      if (worker == null) {
        worker = new MyImplementation();
      }
    }
  }
  return worker;
}

So, now we are back to circle 3: after a bugfix, double checks are legal again.

Comments

[birdwatcher.livejournal.com]

if (worker == null) {
    synchronized {
        if (worker == null) {

О, большое спасибо -- до этого места я когда-то сам придумал, но не был уверен. И что, говорите не будет работать? Только на джаве или вообще?

[ivan-gandhi.livejournal.com]

Теперь будет! :)

[ex-ex-zhuzh.livejournal.com]

«вообще» тоже не будет. скажем, вместо synchronized «вообще» бывает pthread_mutex_lock()/pthread_mutex_unlock() или эквивалент. эти операции обычно не включают memory barrier instructions. поэтому на мультипроцессорах всё поломается. нужно явно где-то добывать и вставлять эти самые memory barrier instructions. на линуксе это будет smp_mb() и семействo, на виндозе MemoryBarrier() и т.д.

[birdwatcher.livejournal.com]

Облом. А зачем тогда может понадобиться pthread_mutex_lock() без smp_mb() ?

[ex-ex-zhuzh.livejournal.com]

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

[birdwatcher.livejournal.com]

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

[ex-ex-zhuzh.livejournal.com]

когда читаем внутри, нет проблем. проблема, когда НЕ читаем, т.е. там не NULL. то есть указатель на объект уже записан в память, а состояние самого объекта ещё нет. на унипроцессоре это нормально, система гарантирует, что когда состояние понадобится, оно уже будет в памяти (система знает, когда именно оно понадобится). на мультипроцессоре это не так.

[birdwatcher.livejournal.com]

Разве, когда выполняется эта строчка,
   worker = new MyImplementation();
все остальные процессоры не стоят? Потому что если они стоят, то worker либо null, либо показывает на нормальный объект.

[ex-ex-zhuzh.livejournal.com]

не стоят, нет, с чего бы?

[birdwatcher.livejournal.com]

Ага, увидел. Спасибо.

[ex-ex-zhuzh.livejournal.com]

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

[ex-ex-zhuzh.livejournal.com]

а, понял, где ерунда: pthread_mutex_lock() как раз содержит memory barrier, но проку в этом мало — мы пытаемся читать переменную снаружи барьера!

[itman.livejournal.com]

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

http://ivan-ghandhi.livejournal.com/480761.html?thread=2363385#t2363385

[ex-ex-zhuzh.livejournal.com]

первая проверка на NULL происходит до входа в mutex. если второй процесс уже внутри, но не выполнил ещё unlock, никакого барьера нет.

[itman.livejournal.com]

Вот, что говорит комментарий в реализации pthrad_mutex_*:

* Note regarding memory visibility: Pthreads has rules about memory
* visibility and mutexes. Very roughly: Memory a thread can see when
* it unlocks a mutex can be seen by another thread that locks the
* same mutex.

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

[ex-ex-zhuzh.livejournal.com]

последовагельность действий такая.

первый тред проверяет указатель на ноль, входит в мьютекс, инициализирует объект.
второй тред проверяет указатель на ноль.

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

[itman.livejournal.com]

Согласно комментариям:
* A memory barrier after a lock and before an unlock will provide
* this behavior.
Врет комментарий? (пардон нет пока времени разбираться в коде)

[ex-ex-zhuzh.livejournal.com]

возьмём снова это утверждение:

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

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

[itman.livejournal.com]

Эээ.... на самом деле Вы, ИМХО, немного запутываете общественность. Или я сам запутался :-) Вот здесь это правильнее описано. (http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html)

Проблема заключается в том, что ссылка на непроиницилизированный объект может появиться раньше, чем объект сконструируется, а не в том, что второй тред увидит эту ссылку до момента выхода из синхронизированного блока. И существует вероятность, что он будет работать с неинициализорованным объектом. А memory barrier между инициализацией и присвоением shared variable гарантирует, что подобной гадости не произойдет. Видимо, аналогичным образом работает и присвоение volatile переменной, которая выставляет барьер перед присваиванием.

[ex-ex-zhuzh.livejournal.com]

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

Можно и так сказать.

А memory barrier между инициализацией и присвоением shared variable гарантирует, что подобной гадости не произойдет.

Да, если мы умеем вставлять memory barrier в произвольном месте кода, это решает проблему. К сожалению, никакой стандарт не предусматривает такой операции.

[itman.livejournal.com]

Никакой Сишный или Джавовский стандарт?