Executor Service with LIFO ordering

Question

I wrote a lazy image downloader for my app using an ExecutorService. It gives me great control about how many downloads are running in parallel at what time and so on.

Now, the only problem that I have is that if I submit a task it ends up at the tail of the queue (FIFO).

Does anyone know how to change this to LIFO?

Answer 1

You can do it in two or three simple steps:

1. Create a LifoBlockingDeque class:

   public class LifoBlockingDeque <E> extends LinkedBlockingDeque<E> {
   
   @Override
   public boolean offer(E e) { 
       // Override to put objects at the front of the list
       return super.offerFirst(e);
   }
   
   @Override
   public boolean offer(E e,long timeout, TimeUnit unit) throws InterruptedException { 
       // Override to put objects at the front of the list
       return super.offerFirst(e,timeout, unit);
   }
   
   
   @Override
   public boolean add(E e) { 
       // Override to put objects at the front of the list
       return super.offerFirst(e);
   }
   
   @Override
   public void put(E e) throws InterruptedException { 
       //Override to put objects at the front of the list
       super.putFirst(e);
       }
   }
   

2. Create the executor:

   mThreadPool = new ThreadPoolExecutor(THREAD_POOL_SIZE, 
                                        THREAD_POOL_SIZE, 0L, 
                                        TimeUnit.MILLISECONDS, 
                                        new LifoBlockingDeque<Runnable>());
   

3. LinkedBlockingDeque is supported only from API Level 9. To use it on earlier versions do the following:

   Use the Java 1.6 implementation - download it from here.

   Then change

   implements BlockingDeque<E>
   

   to

   implements BlockingQueue<E>
   

   To make it compile on Android. BlockingDeque is subtype of BlockingQueue, so no harm done.

And you're done!

Answer 2

You will need to specify the queue type that the ExecutorService is using.

Typically you might be retrieving an ExecutorService via the static methods in Executors. Instead you will need to instantiate one directly and pass in the Queue type that you want that provides LIFO.

EG, to create a LIFO thread pool executor, you could use the following constructor.

ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue)

and pass in a LIFO queue as the final parameter.

There is no LIFO queue in the java collections that I am aware of (please correct me if wrong), but you could easily just create an anonymous inner class that extends LinkedBlockingQueue and overrides the appropriate methods.

For example, (untested)

ThreadPoolExecutor executor = new ThreadPoolExecutor(4, 16, 1, TimeUnit.MINUTES, new LinkedBlockingQueue() {

  @Override
  public void put(Object obj) { 
    // override to put objects at the front of the list
    super.addFirst(obj);
  }

});

UPDATE in response to comments.

We can use a blocking queue that wraps a priority queue. We have to wrap because the Executor expects runnables but we need timestamps too.

// the class that will wrap the runnables
static class Pair {

     long   timestamp;
    Runnable    runnable;

    Pair(Runnable r) {
        this.timestamp = System.currentTimeMillis();
        this.runnable = r;
    }
}


    ThreadPoolExecutor executor = new ThreadPoolExecutor(4, 16, 1, TimeUnit.MINUTES, new BlockingQueue<Runnable>() {

        private Comparator          comparator      = new Comparator<Pair>() {

                                                @Override
                                                public int compare(Pair arg0, Pair arg1) {
                                                    Long t1 = arg0.timestamp;
                                                    Long t2 = arg1.timestamp;
                                                    // compare in reverse to get oldest first. Could also do
                                                    // -t1.compareTo(t2);
                                                    return t2.compareTo(t1);
                                                }
                                            };

        private PriorityBlockingQueue<Pair> backingQueue    = new PriorityBlockingQueue<Pair>(11, comparator);

        @Override
        public boolean add(Runnable r) {
            return backingQueue.add(new Pair(r));
        }

        @Override
        public boolean offer(Runnable r) {
            return backingQueue.offer(new Pair(r));
        }

        @Override
        public boolean offer(Runnable r, long timeout, TimeUnit unit) {
            return backingQueue.offer(new Pair(r), timeout, unit);
        }

        // implement / delegate rest of methods to the backing queue
    });