Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Looking for non-blocking solution that avoids use of locks

Reply
Thread Tools

Looking for non-blocking solution that avoids use of locks

 
 
Olli Plough
Guest
Posts: n/a
 
      11-25-2008
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
 
Reply With Quote
 
 
 
 
Olli Plough
Guest
Posts: n/a
 
      11-25-2008
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
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      11-25-2008
Olli Plough wrote:
> 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.)

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      11-25-2008
Olli Plough wrote:
> 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....
 
Reply With Quote
 
Olli Plough
Guest
Posts: n/a
 
      11-27-2008
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
 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      11-28-2008
Olli Plough wrote:
> 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.

 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      11-29-2008
Olli Plough wrote:
> 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?

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
problem in running a basic code in python 3.3.0 that includes HTML file Satabdi Mukherjee Python 1 04-04-2013 07:48 PM
Re: Looking for a solution where VPN Client access can use site to site VPN (can the ASA 5510 help?) Igor MamuziŠ aka Pseto Cisco 0 01-06-2010 05:58 PM
Perl quoting convention that avoids excessive backslashes Kelly Jones Ruby 1 11-22-2008 09:22 PM
Future date avoids download? AbrahamLincolnIllinois@yahoo.com Javascript 2 09-09-2005 02:51 PM
Code Doesn't Listen...Avoids Sub & Inserts Data Twice??? SABmore ASP General 1 06-30-2005 07:30 AM



Advertisments