如何创建LIFO执行器？

Question

我想创建一个线程池,它将执行最近提交的任务.关于如何实现这一目标的任何建议？

谢谢

Answer 1

您可能只需要实现自己的BlockingQueue包装,将offer/poll映射到堆栈.然后使用它作为BlockingQueue传递给a 的实现ThreadPoolExecutor.我的建议是包装一个现有的Deque实现,如ArrayDeque.

• 这是不同步的,所以你需要BlockingQueue用同步器包装每个方法(如果不是更奇特的东西).
• 您还需要为阻塞操作引入wait/ notify条件.
• 最后,您需要将一组BlockingQueue极性("put"或"take"侧)映射到出队的同一端(将其视为堆栈).

请注意,在更快的并发堆栈上有一些工作(参见Herlihy关于多处理器编程艺术的书),但我不认为JDK中有任何实现,我不确定Herlihy的实现是否提供阻塞风格.

Deque上的实现

我检查了Android文档,这表明Deque适合你,所以这是一个实现.在堆栈周围做包装也是一个相当容易的步骤,但Deque是首选.

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); }
}

Answer 2

与andersoj建议的类似,但是有BlockingDeque的可用性.

您可以将LinkedBlockingDeque类扩展为始终在提供和删除时弹出并首先推送.

public class FIFOBlockingDeque<T> extends LinkedBlockingDeque<T> {

 @Override
 public boolean offer(T t) {
  return super.offerFirst(t);
 }

 @Override
 public T remove() {
  return super.removeFirst();
 }
}

然后将其作为参数传递给ThreadPoolExecutor(BlockingDeque extends BlockingQueue)

编辑:要回答您的评论问题,您可以使用提供的java.util.Stack而不是继承Deque.它被认为是遗留的,如果你只局限于Java库本身,这将是最好的.

您可以使用push和pop来代替offerFirst和removeFirst.当然,您必须实现BlockingQueue并完成该实现.