What exactly is the leader used for in DelayQueue?

I was trying to understand DelayQueue in java.util.concurrent, but leader confused me.

First of all, we can implement a DelayQueue without leader like this:

public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        q.offer(e);

        if (q.peek() == e) {
            available.signal();
        }
        return true;
    } finally {
        lock.unlock();
    }
}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        for (;;) {
            E first = q.peek();
            if (first == null) {
                available.await();
            } else {
                long delay = first.getDelay(TimeUnit.NANOSECONDS);
                if (delay <= 0) {
                    return q.poll();
                } else {
                    available.awaitNanos(delay);
                }
            }
        }
    } finally {
        lock.unlock();
    }
}

Secondly, it seems does not minimize unnecessary timed waiting. According to the annotation:

This variant of the Leader-Follower pattern (http://www.cs.wustl.edu/~schmidt/POSA/POSA2/) serves to minimize unnecessary timed waiting

I take that as minimizing awaitNanos (using await instead of awaitNanos) but I really doubt that. If the new element isn't the head of the queue, then no thread will be signalled. (see offer method as below)

if (q.peek() == e) {
    leader = null;  // set leader to null
    available.signal();
}

So it only makes a difference when new elements is the head. But in this case, the leader will be set to null, and the signalled thread won't go this way(take method):

else if (leader != null)
    available.await();

The thread will always do awaitNanos.

So, can anybody explain that to me? Did I got the wrong idea somewhere?

According to the comment of source code:

It waits only for the next delay to elapse, but other threads await indefinitely.

The leader is not used for minimizing awaitNanos, it is used for avoiding unnecessary wake up & sleep. If you let all threads available.awaitNanos(delay) in take method, they will be called up simultaneously but only one can really get element from the queue, the others will fall into sleeping again, which is unnecessary and resource-wasting.

With Leader-Follower pattern, the leader available.awaitNanos(delay), the non-leader threads available.await(). So the leader will wake up first and retrieving an expried element, then signal another waiting thread if necessary. This is more efficient.

Example

Suppose I have one element E in the queue, it will be expried after T nanoseconds, and there are two threads Thread_1 and Thread_2.

Without leader(the implemetion you provide in the question)

• Thread_1 calls take method, and finds E is available after T nanoseconds, so it calls available.awaitNanos(T).
• Thread_2 calls take method, and finds E is available after T nanoseconds, so it calls available.awaitNanos(T).

After T nanoseconds, Thread_1 wake up and take element E. Thread_2 wake up and get nothing, so it has to sleep again. The wake up and sleep again of Thread_2 is unnecessary.

With leader

• Thread_1 calls take method, and finds E is available after T nanoseconds, so it becomes leader and calls available.awaitNanos(T).
• Thread_2 calls take method, and finds E is available after T nanoseconds, but Thread_2 also notices there is already a leader, so Thread_2 calls available.await().

After T nanoseconds, Thread_1 wake up and take element E. Thread_2 will sleep until new elements are put in the queue.