Как создать LIFO исполнителя?

Question

Я хотел бы создать пул потоков, который будет выполнять последнюю отправленную задачу. Любой совет, как этого добиться?

Спасибо

Answer 1

Возможно, вы могли бы просто реализовать свою собственную оболочку BlockingQueue, которая отображает предложение / опрос в стек.Затем используйте это как реализацию BlockingQueue, которую вы передаете ThreadPoolExecutor.Мое предложение должно заключаться в том, чтобы обернуть одну из существующих реализаций Deque, например ArrayDeque.

• Это не синхронизировано, поэтому вам нужно обернуть каждый из методов BlockingQueue синхронизатором (если не что-то более экзотическое).
• Вам также нужно будет ввести wait / notify условия для операций блокировки.
• Наконец, вам нужно сопоставить один набор полярностей BlockingQueue (сторона "положи" или "взять") с тем же концом dequeue, что и другой (чтобы рассматривать его какстек).

Обратите внимание, что есть некоторая работа (см. Книгу Херлихи по Искусство многопроцессорного программирования ) по более быстрым параллельным стекам, но я не думаю, что в 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

Аналогично тому, что предлагал Андерсой, однако есть возможность блокировки 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 расширяет BlockingQueue)

Edit: Чтобы ответить на свой вопрос с комментариями, вы можете вместо наследования от Deque, вы можете использовать поставляемый java.util.Stack. Это считается устаревшим, если вы ограничены самой библиотекой Java, это будет лучше.

Вы могли бы вместо предлагать первый и удалить первый, вы можете использовать push и pop. Конечно, вам придется реализовать BlockingQueue и завершить эту реализацию.

Answer 3

Этого легко добиться, используя PriorityQueue или PriorityBlockingQueue, в котором самые последние элементы в очереди получают наивысший приоритет.

Answer 4

Я думаю, что есть ошибка в реализации @andersoj LIFO, в методе BlockingLifoQueue.

Метод удаления должен быть таким:

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

    return deque.pollFirst(); // instead of pollLast()
  }

Извините, если я ошибаюсь, но для меня нет смысла ... опрашивать Последнего в ЛИФО.

Answer 5

ThreadPoolExecutor конструкторы принимают BlockingQueue, который используется для выполнения задач. Возможно, вам потребуется реализовать настроенную версию BlockingQueue для поддержки политики LIFO.