Блокировка очереди FIFO с возможностью пропуска элементов?

Question

Короткая версия: Как лучше всего реализовать блокировку очереди FIFO в Java с возможностью временно пропускать или перепрыгивать элементы в очереди, если они не соответствуют определенным критериям в то время, когда онивыскочил из очереди?

Длинная версия:

Я уже много лет использую ArrayBlockingQueue в приложении, и он отлично работал для моих целей.Мне до сих пор нужно было только вызывать put () и take ().Он работал нормально.

Теперь существует требование, чтобы элемент удовлетворял определенным критериям, когда он извлекается с помощью take ().Если он не соответствует критериям, он должен вернуться в очередь, но в том же положении, в котором он находился ранее.

Представьте себе линию на таможне в международном аэропорту.По какой-то причине пассажирам выдали только форму таможенной декларации, когда они вышли на линию.Пассажиры все яростно строчат, чтобы закончить свою форму, прежде чем их очередь подходит.В передней части есть охранник.Когда таможенник готов к следующему пассажиру, охранник проверяет, заполнил ли первый пассажир на линии таможенную декларацию.Если это так, он отправляет pasenger таможеннику.Если нет, он проверяет второго пассажира, затем третьего и т. Д., Пока не найдет того, кто закончил.Он отправляет этого человека таможеннику.То же самое происходит каждый раз, когда таможенник освобождается, всегда запуская первого пассажира на линии.

При исследовании единственной вещи, которую я придумал, было использование двусторонней очереди (deque) и снятие элементов свперед, пока я не найду элемент, который соответствует критериям.Затем поместите элементы обратно на передний план в обратном порядке, в котором я их снял.

У кого-нибудь есть рекомендации?

Answer 1

2 возможных предложения в зависимости от того, можете ли вы прослушивать изменения состояния элементов:

• Если элементы могут уведомить вас о готовности, просто наберите номерих, когда они прибывают, и переместите их в PriorityQueue , как только они будут готовы.Затем просто вытяните первый элемент из PriorityQueue, заблокировав, если он пуст.

• Если вам нужно проверить каждый элемент, чтобы определить, изменился ли его статус, затему вас нет выбора, кроме как посещать каждый предмет по очереди, начиная с самого старого, пока не найдете тот, который готов.В этом случае вам действительно не нужна Очередь как основная структура данных;LinkedList на самом деле лучше подходит.

Второй случай не просто медленнее, он также хуже для работы с полной очередью элементов, которые не готовы;либо вы останавливаетесь на некоторое время (во время блокирования) в конце списка перед перезапуском, либо ваше поведение блокировки эквивалентно ожиданию занятости, поскольку оно периодически циклически переключается между элементами.

(Если бы я былЗастряв в реализации второго, я был бы склонен попытаться динамически настроить время ожидания перед перезапуском, основываясь на общем количестве накопленного времени, ожидающего готовности, и ожидаемой вероятности завершения хотя бы одного из них при следующем запуске.ходить по списку.)

Answer 2

Пусть ваша структура создаст вторую очередь.Получите блокировку записи на всю структуру, когда вы щелкаете.На мгновение проигнорируйте основную очередь и сначала проверьте вторичную очередь.Если он пуст, перейдите в основную очередь.Вытащите элемент из основной очереди.Если он готов, возьмите его и отпустите замок.Если это не так, поместите его во вторичную очередь и возьмите другую.Повторяйте до тех пор, пока вы не будете готовы.

Если вторичная очередь не была пуста, когда вы впервые попытались ее захватить, прокрутите вторичную очередь, чтобы увидеть, готова ли какая-либо из них.

Плюсы этого в том, что у вас всегда есть тот, кто готов сейчас.Если, конечно, вы не исчерпали свою основную очередь, но тогда уже никто не готов к этому, мало что вы можете сделать там.

Минусы этого в том, что если у вас есть очень медленные люди, вторичная очередьможет быть проблемой.Вы можете решить эту проблему, предоставив оценку оставшегося времени или что-то.Кроме того, всегда возможно, что плохие актеры могут лгать или иным образом связывать вас.Но если у вас нет способа вытеснить плохих актеров, у вас все равно возникнут проблемы с многопоточностью.

Вот не-поточно-безопасная версия алгоритма - он просто у меня в головес зерном соли.

class SnappyQueue<E> {
    Queue<E> main = ... // people waiting in line
    Queue<E> slugs = ... // people at the front but still writing
    void push(E e) { main.addLast(e); }
    E pop() {
        E first = slugs.peek();
        if(first != null) {
            for(E cur = slugs.pop(); cur != first; cur = slugs.pop()) {
                if(cur.isReady()) return cur; // we're done, one of the slugs is ready
                slugs.push(cur); // this slug isn't ready, put it back
            }
        }
        while(true) {
            E cur = main.pop();
            if(cur == null) return null; // nothing left
            if(cur.isReady()) return cur; // we found someone ready
            slugs.push(cur); // not ready, push them into the slug line
        }
    }
}