PriorityBlockingQueue put() operation

[Michael Spiegel-2]

Hi,

I apologize if this question has been answered before of if the answer
is trivially obvious.  The documentation for
java.util.concurrent.PriorityBlockingQueue states that the put(E e)
method will never block, and such claims are not made about the add(E
e) method.  The method bodies for both methods are identical, ignoring
the fact that one method returns boolean and the other doesn't return
a value.  The methods body is an invocation to the offer(E e) method.
I believe that offer() is a blocking method, since it locks the
ReentrantLock around the data structure.  So is put() a blocking
method? I must be missing something obvious.

Thanks!
--Michael
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[tpeierls]

On Sat, Nov 7, 2009 at 3:01 PM, Michael Spiegel <michael.m.spiegel@...> wrote:

Hi,

I apologize if this question has been answered before of if the answer
is trivially obvious.  The documentation for
java.util.concurrent.PriorityBlockingQueue states that the put(E e)
method will never block, and such claims are not made about the add(E
e) method.  The method bodies for both methods are identical, ignoring
the fact that one method returns boolean and the other doesn't return
a value.  The methods body is an invocation to the offer(E e) method.
I believe that offer() is a blocking method, since it locks the
ReentrantLock around the data structure.  So is put() a blocking
method? I must be missing something obvious.

Simply holding a lock doesn't necessarily make a method into a blocking method. A blocking method conventionally has "throws InterruptedException" in its signature, a sign to calling code that the method might wait (i.e., block) until some condition holds, and that the caller should be prepared to handle the possibility of interruption while it waits.

The add() method comes from java.util.Collection; it's not a blocking method. The (untimed) offer() method comes from java.util.Queue; it isn't a blocking method, either. 

BlockingQueue.put() *is* generally a blocking method; it waits for the queue to have room for the new element and throws InterruptedException if interrupted while waiting. But since PriorityBlockingQueue is unbounded, it always has room, so it never has to wait and there is no need for it to throw InterruptedException. So PriorityBlockingQueue.put() is not a blocking method.

--tim

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Martin Buchholz-3]

There is a terminology problem here.
Since locks are used, none of the methods are "non-blocking"
in the currently popular technical sense.

I don't know how best to describe an algorithm that
will need to acquire a lock, but once it does so,
will be able to proceed immediately, and not have to
wait indefinitely for some other thread to take action.
The word "wait-free" is taken.

Martin

On Sat, Nov 7, 2009 at 12:01, Michael Spiegel <michael.m.spiegel@...> wrote:

Hi,

I apologize if this question has been answered before of if the answer
is trivially obvious.  The documentation for
java.util.concurrent.PriorityBlockingQueue states that the put(E e)
method will never block, and such claims are not made about the add(E
e) method.  The method bodies for both methods are identical, ignoring
the fact that one method returns boolean and the other doesn't return
a value.  The methods body is an invocation to the offer(E e) method.
I believe that offer() is a blocking method, since it locks the
ReentrantLock around the data structure.  So is put() a blocking
method? I must be missing something obvious.

Thanks!
--Michael
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[tpeierls]

On Sat, Nov 7, 2009 at 3:48 PM, Martin Buchholz <martinrb@...> wrote:

There is a terminology problem here.
Since locks are used, none of the methods are "non-blocking"
in the currently popular technical sense.

True, but I think the term "blocking method" is more usefully (if sloppily) applied only to "throws IE" situations.

 

I don't know how best to describe an algorithm that
will need to acquire a lock, but once it does so,
will be able to proceed immediately, and not have to
wait indefinitely for some other thread to take action.
The word "wait-free" is taken.

"Effectively non-blocking"? "Contentious"? :-)

This is not a distinction I'd want to force on people who just want to use j.u.c types without becoming concurrency experts.

--tim

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

On Sat, Nov 7, 2009 at 12:01 PM, Michael Spiegel wrote:

Hi,

I apologize if this question has been answered before of if the answer
is trivially obvious.  The documentation for
java.util.concurrent.PriorityBlockingQueue states that the put(E e)
method will never block, and such claims are not made about the add(E
e) method.  The method bodies for both methods are identical, ignoring
the fact that one method returns boolean and the other doesn't return
a value.  The methods body is an invocation to the offer(E e) method.
I believe that offer() is a blocking method, since it locks the
ReentrantLock around the data structure.  So is put() a blocking
method? I must be missing something obvious.

Thanks!
--Michael

Wikipedia currently makes this distinction:

  "In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress."

  http://en.wikipedia.org/wiki/Non-blocking_synchronization

So non-blocking < lock-free < wait-free ?

Consider old (blocking) java.io and the newer asynchronous java.nio.  They both use locks of some sort, but nio is non-blocking.

Object.wait is typically a good indicator of  blocking.  (As is throws IE.)

--Joe

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

The term non-blocking here (BlockingQueue.put) is being used in a different sense to that of the non-blocking/wait-free/lock-free algorithms. It is an unfortunate terminology clash but the lock-free/wait-free/non-blocking terminology is only considering mutual-exclusion/atomicity related blocking (for want of a better term).

 

In general any method that has to wait for a state-related condition to hold (space in buffer, item in buffer, data on socket, time-X-has-elapsed) is a blocking method, and any method that doesn't have to wait is a non-blocking method. And this is independent of whether locking is also involved.

 

David

-----Original Message-----
From: concurrency-interest-bounces@... [mailto:concurrency-interest-bounces@...]On Behalf Of Joe Bowbeer
Sent: Sunday, 8 November 2009 9:01 AM
To: concurrency-interest@...
Subject: Re: [concurrency-interest] PriorityBlockingQueue put() operation

On Sat, Nov 7, 2009 at 12:01 PM, Michael Spiegel wrote:

Hi,

I apologize if this question has been answered before of if the answer
is trivially obvious.  The documentation for
java.util.concurrent.PriorityBlockingQueue states that the put(E e)
method will never block, and such claims are not made about the add(E
e) method.  The method bodies for both methods are identical, ignoring
the fact that one method returns boolean and the other doesn't return
a value.  The methods body is an invocation to the offer(E e) method.
I believe that offer() is a blocking method, since it locks the
ReentrantLock around the data structure.  So is put() a blocking
method? I must be missing something obvious.

Thanks!
--Michael

Wikipedia currently makes this distinction:

  "In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress."

  http://en.wikipedia.org/wiki/Non-blocking_synchronization

So non-blocking < lock-free < wait-free ?

Consider old (blocking) java.io and the newer asynchronous java.nio.  They both use locks of some sort, but nio is non-blocking.

Object.wait is typically a good indicator of  blocking.  (As is throws IE.)

--Joe

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Martin Buchholz-3]

On Sat, Nov 7, 2009 at 15:00, Joe Bowbeer <joe.bowbeer@...> wrote:

Wikipedia currently makes this distinction:

  "In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress; wait-free if there is also guaranteed per-thread progress."

  http://en.wikipedia.org/wiki/Non-blocking_synchronization

So non-blocking < lock-free < wait-free ?

I read it a little differently.
"lock-free" is a kind of "non-blocking synchronization",
the weakest kind.  So:
non-blocking <= lock-free < wait-free

non-blocking synchronization cannot involve locks,
since some thread can acquire the lock and never be scheduled again,
causing *all* threads to
"have their execution indefinitely postponed by mutual exclusion".

Martin
 

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest