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

[Adrian Daerr]

Hi,

>> By lock-free I mean setting the value and then checking whether the
>> value is actually what was expected (and if not, retry).
>
> A naïve implementation of this technique could easily result in a very
> nasty ping-pong effect: if one thread tries to clear a bit and the next
> thread tries to set it, it is very to run into a trap when not leaving a
> way for one thread to win.
>
> The safest way to resolve this issue is to reinstate the lock-on-write
> method that was in place earlier
[..]
>
> 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*]:

> 	final long original = dataAccess.getValue(i1);
> 	if ( value ) {
> 		final long newValue = original | (1l << shift);
> 		dataAccess.setValue(i1, newValue);
> 		if ( newValue != dataAccess.getValue( i1 ) ) {
> 			synchronized (dataAccess) {
> 				dataAccess.setValue( i1, dataAccess.getValue(i1) | (1l << shift) );
> 			}
> 		}
> 	}
[snip]

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

FWIW,
cheers and good luck,
Adrian


[1]
TL;DR : You cannot have as-if-serial semantics across threads unless you 
use synchronized.

"Double-checked locking: Clever, but broken
Do you know what synchronized really means?" By Brian Goetz
http://www.javaworld.com/article/2074979/java-concurrency/double-checked-locking--clever--but-broken.html

and its follow-up article

"Can double-checked locking be fixed?
No matter how you rig it, double-checked locking still fails" (also by 
Brian Goetz)
http://www.javaworld.com/article/2075306/java-concurrency/can-double-checked-locking-be-fixed-.html