如何在Java队列/列表中实现原子性的“如果有空闲空间则入队，否则出队再入队”操作？

Question

我有一个关于Java中列表的要求，它具有固定的容量，但始终允许线程在开头添加项目。如果已满，则应从末尾删除一个项目以腾出空间。没有其他进程将删除项目，但其他进程将希望遍历项目。

JDK中是否有可原子化执行此操作的内容？

我的当前计划只是使用一些现有的线程安全集合（例如LinkedBlockingQueue），并在检查容量/添加/删除时进一步同步它。那样行得通吗？

谢谢。

- Trencher

---

有趣的用例似乎没有被JDK覆盖。 - starblue

Answer 1

你的想法是可行的，但需要取出多个锁（见下面的示例）。考虑到在添加数据时需要同步多个操作，最好将LinkedList实现的Queue封装起来，以避免额外锁的开销。

// Create queue with fixed capacity.
Queue<Item> queue = new LinkedBlockingQueue<Item>(1000);

...

// Attempt to add item to queue, removing items if required.
synchronized(queue) { // First lock
  while (!queue.offer(item)) { // Second lock
    queue.take(); // Third lock
  }
}

- Adamski

Answer 2

我正在使用一个旧版本的Java（是的，1.3，我别无选择），所以即使在后来的Java中有它，我也不能使用它。因此，我按照以下方式编码：

public class Fifo  {
 private LinkedList fifoContents = new LinkedList();
 public synchronized void  put(Object element) {
     if ( fifoContents.size() > 100){               
          fifoContents.removeFirst();                
          logger.logWarning("*** Backlog, discarding messaage ");
     }
     fifoContents.add (element);
     return;
 }

 public synchronized Object get() throws NoSuchElementException {
     return fifoContents.removeFirst();
 }
}

- djna

Answer 3

你可能只需要测试/删除/插入而无需额外的锁定：

class DroppingQueue<E>
extends ArrayBlockingQueue<E> {
    public boolean add(E item) {
        while (! offer(item)) {
            take();
        }
        return true;
    }
}

尽管此方法不是同步的，但add和offer仍然是同步的，所以最坏的情况是线程#1将调用offer，发现队列已满，线程#2将执行相同操作，并且两个线程都会删除项目，暂时将项目数量减少到小于最大值，然后两个线程都成功添加其项目。这可能不会造成严重问题。

- finnw

---

我认为这个解决方案可能发生的最糟糕的情况是，每当线程#1取走一个项目时，其他一些线程在线程#1继续之前提供另一个项目。然而，这种情况比你的情况不太可能发生。 - Aleksi Yrttiaho

Answer 4

JDK中没有这样的类。 如果您要实现这样的集合，您可能希望使用带有浮动头/尾指针的数组 - 因为您有固定的大小，所以根本不需要链表。

- vtrubnikov