Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to create LIFO executor?

I would like to create a thread pool which will execute the most recently submitted task. Any advice on how to accomplish this?

Thank you

like image 749
ab11 Avatar asked Jan 06 '11 21:01

ab11


People also ask

What is a Threadpool executor?

ThreadPoolExecutor is an ExecutorService to execute each submitted task using one of possibly several pooled threads, normally configured using Executors factory methods. It also provides various utility methods to check current threads statistics and control them.

What are the different types of executors?

There are two types of executor - those that run tasks locally (inside the scheduler process), and those that run their tasks remotely (usually via a pool of workers).

What is ExecutorService executor?

Executor just executes stuff you give it. ExecutorService adds startup, shutdown, and the ability to wait for and look at the status of jobs you've submitted for execution on top of Executor (which it extends).


1 Answers

You could probably just implement your own BlockingQueue wrapper that maps offer/poll to a stack. Then use this as the BlockingQueue implementation you pass to a ThreadPoolExecutor. My suggestion would be to wrap one of the existing Deque implementations such as ArrayDeque.

  • This is not synchronized, so you'll need to wrap each of the BlockingQueue methods with a synchronizer (if not something more exotic).
  • You'll also need to introduce wait/notify conditions for the blocking operations.
  • Finally, you'll need to map one set of the BlockingQueue polarities (either the "put" or the "take" side) to the same end of the dequeue as the other (to treat it like a stack).

Note that there is some work (see Herlihy's book on The Art of Multiprocessor Programming) on faster concurrent stacks, but I don't think there are any implementations in the JDK and I'm not sure if Herlihy's implementations offer blocking flavors.

An Implementation atop Deque

I checked the Android documentation, which suggests that Deque is around for you, so here's an implementation. It's a fairly easy step to do a wrapper around a stack, too, but Deque is preferred.

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.TimeUnit;


public final class BlockingLifoQueue<T> implements BlockingQueue<T>
{
  // we add and remove only from the end of the queue
  private final BlockingDeque<T> deque; 

  public BlockingLifoQueue()
  { deque = new LinkedBlockingDeque<T>(); }

  public boolean add(T e) {
    deque.addLast(e);
    return true;
  }

  public boolean contains(Object o)
  { return deque.contains(o); }

  public int drainTo(Collection<? super T> c)
  { return deque.drainTo(c); }

  public int drainTo(Collection<? super T> c, int maxElements)
  { return deque.drainTo(c,maxElements); }

  public boolean offer(T e)
  { return deque.offerLast(e); }

  public boolean offer(T e, long timeout, TimeUnit unit)
      throws InterruptedException
  { return deque.offerLast(e,timeout,unit); }

  public T poll(long timeout, TimeUnit unit) throws InterruptedException
  { return deque.pollLast(timeout, unit); }

  public void put(T e) throws InterruptedException
  { deque.putLast(e); }

  public int remainingCapacity()
  { return deque.size(); }

  public boolean remove(Object o)
  { return deque.remove(o); }

  public T take() throws InterruptedException
  { return deque.takeLast(); }

  public T element()
  {
    if (deque.isEmpty()) { 
      throw new NoSuchElementException("empty stack");
    }

    return deque.pollLast();
  }

  public T peek()
  { return deque.peekLast(); }

  public T poll()
  { return deque.pollLast(); } // deque.peekLast(); } -- fixed typo.

  public T remove()
  {
    if (deque.isEmpty()) { 
      throw new NoSuchElementException("empty stack");
    }

    return deque.pollLast();
  }

  public boolean addAll(Collection<? extends T> c)
  { 
    for (T e : c) { deque.add(e); }
    return true;
  }

  public void clear()
  { deque.clear();}

  public boolean containsAll(Collection<?> c)
  { return deque.containsAll(c); }

  public boolean isEmpty()
  {  return deque.isEmpty(); }

  public Iterator<T> iterator()
  { return deque.descendingIterator(); }

  public boolean removeAll(Collection<?> c)
  { return deque.removeAll(c); }

  public boolean retainAll(Collection<?> c)
  { return deque.retainAll(c); }

  public int size()
  { return deque.size(); }

  public Object[] toArray()
  { return deque.toArray(); }

  public <T> T[] toArray(T[] a)
  { return deque.toArray(a); }
}
like image 180
andersoj Avatar answered Sep 18 '22 14:09

andersoj