Looking for non-blocking solution that avoids use of locks

Discussion in 'Java' started by Olli Plough, Nov 25, 2008.

  1. Olli Plough

    Olli Plough Guest

    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, Nov 25, 2008
    #1
    1. Advertising

  2. Olli Plough

    Olli Plough Guest

    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
    Olli Plough, Nov 25, 2008
    #2
    1. Advertising

  3. Olli Plough

    Eric Sosman Guest

    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
    lid
    Eric Sosman, Nov 25, 2008
    #3
  4. Olli Plough

    Mark Space Guest

    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....
    Mark Space, Nov 25, 2008
    #4
  5. Olli Plough

    Olli Plough Guest

    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
    Olli Plough, Nov 27, 2008
    #5
  6. Olli Plough

    Mark Space Guest

    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.
    Mark Space, Nov 28, 2008
    #6
  7. Olli Plough

    Daniel Pitts Guest

    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/>
    Daniel Pitts, Nov 29, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hendra Gunawan
    Replies:
    1
    Views:
    12,397
    Allan Herriman
    Apr 8, 2004
  2. Andre Kelmanson

    blocking i/o vs. non blocking i/o (performance)

    Andre Kelmanson, Oct 10, 2003, in forum: C Programming
    Replies:
    3
    Views:
    910
    Valentin Tihomirov
    Oct 12, 2003
  3. nukleus
    Replies:
    14
    Views:
    814
    Chris Uppal
    Jan 22, 2007
  4. Christian
    Replies:
    5
    Views:
    719
    Esmond Pitt
    Dec 2, 2007
  5. Serge Savoie
    Replies:
    4
    Views:
    254
    Serge Savoie
    Oct 1, 2008
Loading...

Share This Page