Очередь без блокировки и с ограниченным размером в Java

Question

Я пытаюсь расширить реализацию очереди без блокировки в Java согласно этой публикации.

Для моей реализации я ограничен в использовании только атомарных переменных / ссылок. Кроме того, моя очередь должна иметь максимальный размер. И поэтому putObject() должен блокироваться, когда очередь заполнена, и getObject(), если очередь пуста.

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

Например, при использовании AtomicInteger операции модификации будут атомарными. Но есть еще проблема, что я должен обработать ситуацию проверки и изменения в putObject() и getObject(), верно? Таким образом, все еще существует ситуация, когда поток очереди будет прерван после проверки текущего размера очереди.

На данный момент у меня вопрос, можно ли решить эту проблему с моими нынешними ограничениями?

поздравил

Answer 1

Если у вас есть жизнеспособная, правильно работающая очередь без блокировки, добавить максимальный размер можно так же просто, как просто добавить AtomicInteger и выполнить проверки inc, dec в нужное время.

При добавлении элемента вы в основном заранее резервируете место в очереди. Что-то вроде:

while (true) {
    int curr = count.get();
    if (curr < MAX) {
        if (count.compareAndSet(curr, curr + 1)) {
            break;
        }
    }
    else {
        return FULL;
    }
}

Затем вы добавляете новый элемент и связываете его. Получая, вы можете просто получить доступ к голове как обычно и проверить, есть ли что-нибудь, что можно вернуть из очереди. Если да, вы возвращаете его, а затем уменьшаете счетчик. Если нет, просто верните ПУСТО. Обратите внимание, что я не использую счетчик, чтобы проверить, действительно ли очередь пуста, поскольку счетчик может быть равен 1, в то время как в очередь еще ничего не связано из-за подхода с предварительным резервированием. Поэтому я просто верю, что у вашей очереди есть способ сказать вам "у меня есть что-то во мне" или нет (это должно быть, или get() никогда не сработает).

Answer 2

Это очень распространенная проблема, которая обычно решается с помощью кольцевого буфера. Это то, что используют сетевые адаптеры, так же как и библиотека Disruptor. Я предлагаю вам взглянуть на Disruptor и хороший пример того, что вы можете сделать с кольцевыми буферами.