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

[Stephan Saalfeld]

Thanks for the articles!

I have more comments on the matter.  In fact, all types have the same
problem.  Even for a non-native ComplexType read and write would not be
atomic and thus not thread-safe.  The problem is that, for non-native
types, it is sufficient for multi-threaded code to synchronize on the
type instance itself.  For native types (e.g. ComplexDoubleType) and for
other proxy mechanisms such as Composites or ReadWriteConverters, this
doesn't work.  How about a getLock() (or getMonitor()) method as part of
Type whose purpose is to return a lock that enables synchronization on
that particular's type content.  Should that lock be constant for a
type's lifetime?  Proxy types for which access is atomic could return
themselves, just as Types that actually contain their content.

I like Tobias' proposal with a Hash of locks for NativeTypes, something
similar is necessary for other writable proxies.

Best,
Stephan



On Thu, 2014-10-30 at 14:51 +0100, Adrian Daerr wrote:
> 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