juan_gandhi | java synchronization gone wild and back

java synchronization gone wild and back

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.

Flat | Top-Level Comments Only

mmm... http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom ???

The idiom, however nice, was just a patch for a bug. :) You may call it an idiom, a hack, depending on the attitude. The point is, it would not exist if jvm worked properly with volatiles in previous versions.

Well, whatever it is, isn't it actually nicer than the double-check idiom (new and improved, now with one fewer bug)?

In the simple and easy form above - I'd rather agree, that yes, it is cleaner. But in my real practice somehow it always looked uglier.

I'd say that the bug and the idiom are independent. Having 'synchronized' without 'volatile' obviously was an idiocy, but why should I bother writing explicit synchronization incantations and runtime hints to initialize a singleton if the runtime already provides the mechanism. IBM (linked by

upstartn) says the same thing:

Instead of double-checked locking, use the Initialize-on-demand Holder Class idiom, which provides lazy initialization, is thread-safe, and is faster and less confusing than double-checked locking[.]

yes :)

Oh shit... you wrote it 8 months ago! Pity I was not subscribed to your blog back then.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот, что говорит комментарий в реализации 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Интересно, а какова физика этого явления? Дело в том, что если в ячейку X ровно один поток имеет возможность записывать значение, а остальные потоки имеют права прочесть это значение, но строго после того, как поток значение записал, то никакой неодназначности быть не может. Единственное, что мне приходит в голову: процесс заглядывает вперед, заполняет конвеер и "подсасывает" значения переменных в процессорный кеш. И читает, соответственно, тоже из кеша.
Я прямо скажем абсолютно никакой специалист по архитектуре ЭВМ и не понимаю, а может ли такое случиться. Интересно понять, а что же происходит на самом деле.

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

Любопытно, с phtread_mutex'ами проделывать подобные операции всегда

безопасно.
(http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libpthread/pthread_mutex.c?rev=1.27&content-type=text/x-cvsweb-markup)
/*
* 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.
*
* A memory barrier after a lock and before an unlock will provide
* this behavior. This code relies on pthread__simple_lock_try() to issue
* a barrier after obtaining a lock, and on pthread__simple_unlock() to
* issue a barrier before releasing a lock.
*/

Неужели synchronized в Java работает по-другому? Вот, например, в статье в Java World за 2001ый год Алан Голуб пишет буквально следующее:
"Memory barriers surround synchronization To summarize, synchronization implies a memory barrier. In that case, two exist: one barrier associated with entering a synchronized block or method and another associated with leaving it"
Неужели "гонит"?

пардон, вот сама статья (http://www.roseindia.net/software-tutorials/detail/2715)

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

Как я там уже где-то писал в комментариях, теория не работает потому, что нужно выставлять барьер между инициализацией класса и "публикацией" ссылки класса "наружу". Потому что, де факто инициализация может случиться позже присваивания. Из-за пресловутого operation reordering. И тогда первый тред, который еще не зашел в синхронизированный блок, может увидеть не NULL ссылку на недостроенный объект и начать работать с ним. В плюсах будет точно такая же фигня.
Volatile в java, насколько я понимаю, делает этот самый memory barrier на кажду операцию доступа к volatile переменной. Таким образом, проверка
if (worker == NULL)
вне synchronized перестает, наверное, "облегченной". Вот тут, например, (http://blogs.msdn.com/brada/archive/2004/05/12/130935.aspx) говорят, что лучше не использовать volatile, а явным образом использовать memory barrier. В частности, это всегда корректно даже при отложенной инициализации.

насколько я понял, выход из лока как раз гарантирует синхронизацию, независимо от количества процессоров и их кэшей. store.release semantics, whatever that means. то есть вторая проверка _никогда_ не увидит null, если инициализация уже произошла. проблема в том, что _первая_ проверка может увидеть не null из-за реордеринга операций внутри лока. использование слова volatile решает именно эту проблему, запрещая реордеринг операции присвоения волатильной переменной. интересно, что слово volatile в естественном языке означает нечто обратное по смыслу, а сюда бы как раз подошло ключевое слово типа "solid" или "enforce" на худой конец.

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

Криворукая Сановская архитектура. Вместо того, чтобы делать консистентность кэшей в железе (как Интел), они полагаются на явные барьеры в программах. Т.е. есть такая явная инструкция "синхронизировать кэш". Экономии железа при этом с гулькин нос, но зато сколько геморрою! И, кстати, как я понимаю, производительность при железной (как у Интела) синхронизации кэшей все равно получается лучше за счет того, что меньше невинных неразделяемых данных сваливается из кэша в память.

C# singleton

довольно вредная дурацкая misleading статья, поскольку:

1. статические констракторы что, святым духом обеспечивают единственность инициализации? тем же самым lock(), так что performance inefficiency решения №2 никуда не девается.

2. singleton pattern в его классическом понимании is dead. во всех случаях, когда действительно нужен единственный инстанс класса, его можно просто заменить на static class.

3. если не синглтон, а просто статический член с долгой инициализацией, то что делать?

4. ну и наконец, заявление "it's broken in .NET too" безо всяких пояснений никуда не годится. как именно broken? почему broken?

1. Я посмотрел MSIL для 2-го решения и 5-го. Во втором используется lock, собственно как это и видно из исходника. В пятом не используются локи, по крайней мере я не нашёл. Если я правильно понимаю, то вся хитрость в реализации CLR, которая гарантирует единственность выполнения статического конструктора на AppDomain (возможно эта реализация использует lock в своём unmanaged code, не знаю как проверить). Наверное стоило скомпилировать в native code и проверить так, но я не знаю assembler.

Производительность всегда можно померять.

2. В .NET инстанс статического класса создастся даже тогда, когда есть вызовы его статических членов. Если у нас есть статические члены не связанные по функциональности с нашим "синглтоном", то хотелось бы развязать вызовы этих членов и создании инстанса класса. С другой стороны понятно, что это кривизна дизайна.

3. Так этот вопрос совершенно не касается singleton. Возможно в этом случае lock является лучшим вариантом.

4. Согласен.

3. как не касается? решение, преподносимое как самое лучшее, будет работать только для "настоящего" синглтона, а для просто статического члена - всё равно надо double checking and all that jazz.

2. В .NET инстанс статического класса создастся даже тогда, когда есть вызовы его статических членов.

мнэ... huh?

0. на самом деле я, конечно, погорячился. просто обидно стало, что годами проверенный код вдруг так походя записали в bad. действительно интересно, чем обеспечивается единственность вызова статического констрактора - но даже если тем же локом или unmanaged аналогом, то реализация со вложенным классом всё равно мне больше нравится, несмотря даже на "лишний" элемент в скопе. а в джаве так и этого минуса нет, там вложенный класс виден внешнему, даже если он private.

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

Ага. А потом окажется, что CLR under the hood делает лок и мы оказываемся не только с локом, но и с лишним классом впридачу. :)

Что там народ из CLR team говорит по этому поводу?

а, вот ещё. class Nested у нас internal и таким образом будет бессмысленно болтаться в скопе всех клиентов внешнего класса в этой сборке.

гм, я так и думал. double-checking paradigm is not broken in CLR, except maybe the implementation running on alpha (if such implementation even exists). all other hardware (x86, ia64, amd64) provide memory model strong enough to avoid the problem. see http://blogs.msdn.com/cbrumme/archive/2003/05/17/51445.aspx

дочитал этот крайне интересный текст до середины, дальше не хватило сил, потому что с самого начала было понятно, как писать правильно (C#):

private static object workerSyncRoot = new object();
private static My worker;
public  static My Worker
{
  get 
  {
    if (worker == null)
      lock (workerSyncRoot)
        if (worker == null)
          worker = new MyImpl();
    return worker;
  }
}

я правильно угадал концовку?

во-от, а значит, чтобы и на железе с weak memory model работало, нужно просто барьер в нужный момент передёрнуть, типа:

    if (worker == null)
      lock (workerSyncRoot)
        if (worker == null)
        {
          My tempWorker = new MyImpl();
          Thread.MemoryBarrier();
          worker = tempWorker;
        }
    return worker;

прямо collision detection напрашивается с рандомной задержкой от x до y миллисекунд. :)

(до чего же все-таки джава ебанутая)

singleton is a sick pattern

<<
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.
>>

Nope. The only real reason could be that the Java compiler remembers the value of "worker" in the virtual machine registers/stack before it gets the mutex, and then when the mutex synchronizes the memory, the old value from the registers continues to be used throughout the constructor. That's why "volatile" fixes it: it requires that the value gets pulled from the memory afresh every time. I would expect it from C++, but then Java has synchronization as a language statement, so it should treat these statements as barriers for storing temporary values in registers.

BTW, probably a simpler initialization is something like this (my Java nay contain syntax errors):

class My;

// this class will provide synchronization for
// the initialization of class My
class MyHelper {
    static synchronized void getMy()
    {
        My::initialize();
    }
};

class My {
protected:
    friend class MyHelper;

    static My worker;

    static void initialize()
    {
        if (worker == null)
            worker = new My();
    }

public:
    static My worker() 
    {
        MyHelper::getMy();
        return worker;
    }
};

Overall the Java synchronized stuff is way too uglier than it seems at first :-( And singletons are Evil.

That's why "volatile" fixes it: it requires that the value gets pulled from the memory afresh every time.

yes, but that's exactly why the solution with "volatile" is not the best: you incur the performance hit every time you access the member.

Though in this particular case it doesn't matter much :-) I suppose even in the more serious cases an extra access to the cache tends to be not that bad.

I'd rather call MemoryBarrier() explicitly inside the lock and be done with it.

Well, the problem is exactly that if some value is in a CPU register, calling MemoryBarrier() is not going to update it. You need to call MemoryBarrier() and then also reload the new consistent value from memory (more specifically, from cache that is now known to be consistent with memory) to the CPU register. Since the compiler/optimizer makes the decisions about what and when is going from the memory to the CPU registers, you need to communicate the idea of careful treatment your variable to the compiler. The keyword "volatile" does that.

as far as I understand, the problem is in reordering instructions set. that's why we can have non-null value when the constructor is not complete yet.

if what you are saying about cpu registers is true, no multithreaded code would ever work without "volatile" keyword, which is quite hard to believe.

After some thinking, the trick is that usually any function call is considered a "CPU register barrier" for any non-local variable. So yeah, you're probably right.

Man, you are right! That's the sound reason for using The Initialization On Demand Axiom (idiom).

and, if you don't like nested classes, you can simply call MemoryBarrier() inside the lock.

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

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

Сомневаюсь, что это чем-то гарантировано. (http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html)

А, действительно, они правы: то есть, выполнится-то оно гарантировано в правильном порядке, а вот что оно другим процессором будет увидено в правильном порядке - не гарантировано. Мораль опять сводится к тому, что у Сана архитектура странная и ушибленная на голову.

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

Flat | Top-Level Comments Only

java synchronization gone wild and back

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject