[ImageJ-devel] [fiji-devel] Lock-free bit fields, was Re: What's left to do for ImgLib2

[Johannes Schindelin]

Dear Adrian,

On Thu, 30 Oct 2014, Adrian Daerr wrote:

> > An alternative might be to give up lock-freedom in favor of wait-freedom
> > [*2*]. In this regard, a more performant version might be
> [..]
> > to use Optimistic Concurrency Control [*3*]:
> 
> Hum, I do not if this is really a comparable situation, but it looks a
> lot like the double-checked locking (DCL) idiom, which is broken [1].

Thank you for your concerns. Let me take the time for a proper discussion
rather than just linking to two articles of a highly respected developer.

Let's recapitulate the Double-Checked Locking problem for a moment: any
non-synchronized access in Java is *not* guaranteed to have the same
ordered memory-access as *any* other thread. In other words, a set of
synchronized threads might read, modify and write a certain field
correctly, all the while *another* thread might *still* receive the
unmodified value *afterwards*.

Example:

	newValue = array[i] | 1;
	array[i] = newValue;
	if (array[i] != newValue) {
		synchronized (array) {
			newValue = array[i] | 1;
			array[i] = newValue;
		}
	}

Let's assume that thread Albert is in the synchronized block, having just
read the very same array element as thread Bene, but Bene is just
modifying the value as per the second line. The Java Memory Model states
that Bene's modification is not necessarily seen, nor blocked by Albert's
synchronized write access because Bene is unsynchronized. And Albert's
modification will not necessarily be seen by Bene in the if() statement,
either – because Bene is unsynchronized.

So yes, the Double-Checked Locking problem applies here as well.

Ciao,
Johannes