Как я могу атомарно «поставить в очередь, если свободное место ИЛИ удалить из очереди, затем ставить в очередь» для очереди / списка Java?

Question

У меня есть требование для списка в Java с фиксированной емкостью, но который всегда позволяет потокам добавлять элементы в начало. Если он заполнен, он должен удалить элемент с конца, чтобы освободить место. Никакой другой процесс не удалит элементы, но другие процессы захотят перебирать элементы.

Есть ли в JDK что-то, что позволило бы мне сделать это атомарно?

Мой текущий план состоит в том, чтобы просто использовать какой-либо существующий потокобезопасный набор (например, LinkedBlockingQueue) и дополнительно синхронизировать его при проверке емкости / добавления / удаления. Будет ли это работать также?

Спасибо.

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

Answer 2

В JDK такого класса нет. Если вы собираетесь реализовать такую ​​коллекцию, вы можете использовать массив с плавающими указателями головы / хвоста - поскольку у вас фиксированный размер, вам вообще не нужен связанный список.

Answer 3

Возможно, вам удастся просто проверить / удалить / вставить без дополнительных блокировок:

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

Несмотря на то, что этот метод не синхронизирован, add и offer все еще остаются, поэтому самое худшее, что может произойти, это то, что поток # 1 вызовет offer, обнаружит, что очередь заполнена, поток # 2 выполнит То же самое, и оба будут удалять элементы, временно уменьшая количество элементов до значения меньше максимального, прежде чем оба потока успешно добавят свои элементы. Это, вероятно, не вызовет серьезных проблем.

Answer 4

Я работаю в старой версии Java (да, 1.3, у меня нет выбора), поэтому, даже если она есть в более поздних версиях Javas, я не могу ее использовать. Итак, я написал следующие строки:

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