Looking for non-blocking solution that avoids use of locks

[Olli Plough]

Hello,

I sometimes have a situation that simplified looks like this:

(1) if(aConcurrentNonBlockingCollection.isEmpty())
(2) aAtomicBoolean.getAndSet(true)

Both aConcurrentNonBlockingCollection.isEmpty() and
aAtomicBoolean.getAndSet(true) are atomic and non-blocking using non-
blocking abstract data types from java.util.concurrent. Problem is now
that because of a possible context switch between line (1) and (2) I
end up having to enclose that 2 lines with a lock. Now the lock itself
is not non-blocking and uses synchronized in the end which has much
worse performance characteristics than those non-blocking new ADT in
java.util.concurrent.

Does anybody have an idea how to solve this with the use of non-
blocking synchronization objects? So far I went with
ConcurrentHashMap.putIfAbsent with the use of which I could get round
the problem in some cases. But it sometimes cannot be done this way...

Cheers, Oliver

 

[Olli Plough]

Here is a construct I forgot to mention:

(1) if(aAtomicBoolean.get())
(2) aSemaphore.acquire()

The idea is to reduce locking/synchronisation to a situation where it
is necessary and not having to pay the performance penalty for locking
when it is not needed. Again, for this to work I have to enclose those
2 lines with a mutex and the "nice" lock-free solution is obstructed.
Might have to create a new AtomicSomething class that if a atomic
evaluated condition is true, executes another block within the same
atomic scope the previous condition was evaluated in. Hope somebody is
able to see what I am trying get communicated ... ;-).

Regards, Oliver

 

[Eric Sosman]

Hello,

I sometimes have a situation that simplified looks like this:

(1) if(aConcurrentNonBlockingCollection.isEmpty())
(2) aAtomicBoolean.getAndSet(true)

Both aConcurrentNonBlockingCollection.isEmpty() and
aAtomicBoolean.getAndSet(true) are atomic and non-blocking using non-
blocking abstract data types from java.util.concurrent. Problem is now
that because of a possible context switch between line (1) and (2) I
end up having to enclose that 2 lines with a lock. [...]

Why? No, really: "Why?"

Even if you wrap the two method calls in a single lock,
the rest of the program has no reason to believe that the
state of aAtomicBoolean has anything to do with whether
aConcurrentNonBlockingCollection is or isn't empty. If some
other piece of the code finds that aAtomicBoolean is true,
all it knows is that aConcurrentNonBlockingCollection *was*
empty at some time in the past; aAtomicBoolean says nothing
about what may have happened to the collection since that
time. If you leave the code as it stands (adding a semicolon),
the rest of the program gets exactly the same information: if
aAtomicBoolean is true, aConcurrentNonBlockingCollection was
once found to be empty. The conclusions the rest of the code
can draw from inspecting aAtomicBoolean are identical, so the
code as shown is every bit as good as a wrapped version.

So, again: "Why?" (I suspect the answer may be "Because
I simplified my situation so much that there's nothing left
of it," in which case you should perhaps de-simplify it some.)

 

[Mark Space]

Hello,

I sometimes have a situation that simplified looks like this:

(1) if(aConcurrentNonBlockingCollection.isEmpty())
(2) aAtomicBoolean.getAndSet(true)

public class MySortaAtomicBoolean {
public boolean getState() {
return aConcurrentNonBlockingCollection.isEmpty();
}
}

But as Eric says, probably we're missing some important detail here....

 

[Olli Plough]

I think this would be it:

AtomicBoolean condition = new AtomicBoolean(false); // where
condition is an inst var, of course
if(condition.compareAndSet(false, true))
aSemaphore.acquire();

So I don't have to do this every time I access a shared variable:

myLock.lock();
// ...
myLock.unlock();

With the solution with the AtomicBoolean above I block some other
thread only if I really have to block it, not always as with using a
lock (much less lock contention). If the condition applies, a
semaphore is closed so that I can safely do my thing. When I'm done
with it, I check my condition and signal the semaphore if required:

if(condition.get())
aSemaphore.signal();

Then I can build in my specific evaluated condition
aConcurrentNonBlockingCollection.isEmpty() or whatever:

AtomicBoolean condition = new AtomicBoolean(false);
if(condition.compareAndSet(false,
aConcurrentNonBlockingCollection.isEmpty()))
aSemaphore.acquire();

Either this is great or I'm missing something and the whole thing is
not thread-safe. Hope not ... What do you think?

Regards, Oliver

 

[Mark Space]

I think this would be it:

AtomicBoolean condition = new AtomicBoolean(false); // where
condition is an inst var, of course
if(condition.compareAndSet(false, true))
aSemaphore.acquire();

This looks useful to me. I'd even call it a coding pattern for
detecting edges (transitions) in state. Only one thread, the first one,
to set condition to true will enter the block in the if statement.

I think I'd declare "condition" as "final", but that's all I'd change.

AtomicBoolean condition = new AtomicBoolean(false);
if(condition.compareAndSet(false,
aConcurrentNonBlockingCollection.isEmpty()))
aSemaphore.acquire();

OTOH, I have no idea what you are tying to do here. Which ones are the
non-blocking collections? I think they are all actually labeled
"blocking", like ArrayBlockingQueue. If you don't want to block if the
Queue is empty, just call poll(). It'll return with null if nothing is
found.

If I've got the wrong sort of classes (not ArrayBlockingQueue and
friends) then sorry, but I'm missing something.

 

[Daniel Pitts]

Hello,

I sometimes have a situation that simplified looks like this:

(1) if(aConcurrentNonBlockingCollection.isEmpty())
(2) aAtomicBoolean.getAndSet(true)

Both aConcurrentNonBlockingCollection.isEmpty() and
aAtomicBoolean.getAndSet(true) are atomic and non-blocking using non-
blocking abstract data types from java.util.concurrent. Problem is now
that because of a possible context switch between line (1) and (2) I
end up having to enclose that 2 lines with a lock. Now the lock itself
is not non-blocking and uses synchronized in the end which has much
worse performance characteristics than those non-blocking new ADT in
java.util.concurrent.

Does anybody have an idea how to solve this with the use of non-
blocking synchronization objects? So far I went with
ConcurrentHashMap.putIfAbsent with the use of which I could get round
the problem in some cases. But it sometimes cannot be done this way...

Cheers, Oliver

You do realize that the isEmpty() can change an any time (from true to
false, or false to true).

What is your ultimate goal? Why do you need to export the fact that your
thread saw an empty collection in the first place?