[concurrency-interest] LinkedBlockingQueue v/sPriorityBlockingQueue - implementation differences

David Holmes dholmes at dltech.com.au
Thu Mar 10 21:11:14 EST 2005


MessageNeeraj,

Where are you getting this source code for LinkedBlockingQueue from? The
code you gave is not what I have (either from the JSR-166 source site, or
the JDK 1.5.0_01 download for windows or linux.) Hmmm I just noticed the
code you gave has no generic type parameters - is this from the backport?

If it is the backport then in the absence of atomics support it probably
uses a different approach - but I know nothing of the details of the
backport.

The real take() looks like:

public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            try {
                while (count.get() == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to a non-interrupted thread
                throw ie;
            }

            x = extract();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }

Cheers,
David Holmes
  -----Original Message-----
  From: Kumar, Neeraj [mailto:Neeraj.Kumar at FMR.com]
  Sent: Friday, 11 March 2005 12:03 PM
  To: David Holmes; Joshi, Rahul; concurrency-interest at altair.cs.oswego.edu
  Cc: Olin, Jordan; Kumar, Neeraj
  Subject: RE: [concurrency-interest] LinkedBlockingQueue
v/sPriorityBlockingQueue - implementation differences


  Hi David, Please take a look at these 2 take function . First 'take'
function of LinkedBlockingQueue uses a synchronized block ( on the
takeGuard_ object)  which makes sense but same function in the
PriorityBlockingQueue uses "final ReentrantLock lock = this.lock;" to
achieve the same purpose. Is there any special purpose of using
ReentrantLock in PriorityBlockingQueue class. Please help us in
understanding this.

  Thanks,

  Neeraj Kumar

  This 'take' is from LinkedBlockingQueue

  public Object take() throws InterruptedException {

  if (Thread.interrupted()) throw new InterruptedException();

  Object x = extract();

  if (x != null)

  return x;

  else {

  synchronized (takeGuard_) {

  try {

  for (; ; ) {

  x = extract();

  if (x != null) {

  return x;

  }

  else {

  takeGuard_.wait();

  }

  }

  }

  catch (InterruptedException ex) {

  takeGuard_.notify();

  throw ex;

  }

  }

  }

  }



  And take function for PriorityBlockingQueue is

  public Object take() throws InterruptedException {

  final ReentrantLock lock = this.lock;

  lock.lockInterruptibly();

  try {

  try {

  while (q.size() == 0)

  notEmpty.await();

  } catch (InterruptedException ie) {

  notEmpty.signal(); // propagate to non-interrupted thread

  throw ie;

  }

  Object x = q.poll();

  assert x != null;

  return x;

  } finally {

  lock.unlock();

  }

  }

    -----Original Message-----
    From: David Holmes [mailto:dholmes at dltech.com.au]
    Sent: Thursday, March 10, 2005 6:47 PM
    To: Joshi, Rahul; concurrency-interest at altair.cs.oswego.edu
    Cc: Olin, Jordan; Kumar,Neeraj
    Subject: RE: [concurrency-interest] LinkedBlockingQueue
v/sPriorityBlockingQueue - implementation differences


    Rahul,

    I don't know what implementation you are looking at but
LinkedBlockingQueue uses ReentrantLock and Condition as well.

    The key difference is that LinkedBlockingQueue can use the well known
two-lock algorithm for protecting the head and tail separately, for those
operations known to work on the head or the tail. Thus allowing greater
concurrency of put with take. Any operation not on the head or tail requires
both locks to be held.

    In contrast PriorityBlockingQueue is a simple and direct use of a Lock
and a Condition protecting access to an underlying PriorityQueue.

    David Holmes
      -----Original Message-----
      From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Joshi, Rahul
      Sent: Friday, 11 March 2005 9:22 AM
      To: concurrency-interest at altair.cs.oswego.edu
      Cc: Olin, Jordan; Kumar,Neeraj
      Subject: [concurrency-interest] LinkedBlockingQueue
v/sPriorityBlockingQueue - implementation differences


      Hi,
      I think we understand the functional differences of
LinkedBlockingQueue v/s PriorityBlockingQueue. When we walked through the
implementation code we found that both have a very different concurrency
implementation. Sometimes they confuse us a lot.

      I think we do not understand it clearly and need help from someone.
Lets take 'take' method implementation as an example. LinkedBlockingQueue
uses takeGuard_ for synchronization where as PriorityBlockingQueue has very
different implementation using 'ReentrantLock' and 'Condition'. Both has
very different style of implementation.

      Why there is a difference between implementation? Are we missing
something here?

      Thanks,
      Rahul Joshi


-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20050311/5989b1e8/attachment-0001.htm


More information about the Concurrency-interest mailing list