Java: учитывает ли LinkedBlockingQueue порядок потребителей?

Question

У меня есть 3 потока: 2 потребителя, ConsumerA и ConsumerB, и Producer.

У меня также есть LinkedBlockingQueue queue

При t = 1: ConsumerA вызывает queue.take ()

при t = 2: Consumer B вызывает queue.take ()

при t = 3: Producer вызывает queue.put (foo)

Гарантируется ли, что ConsumerA получает foo до ConsumerB?Другими словами, порядок, в котором потребители вызывают take(), является порядком, в котором каждый уведомляется?

Если нет, существует ли альтернативная структура данных, которая будет предоставлять более высокий приоритет на основе порядка?

Answer 1

Во многих случаях порядок потоков, поступающих в очередь, будет в соответствующем порядке. Однако очередь LinkedBlocking использует несправедливую блокировку. То, что это делает, позволяет потокам нарываться друг на друга. Хотя редко может случиться следующее.

• Тема A входит и опрашивает.
• Поток B вводит попытки опроса - Поток A удерживает блокировку и паркует Поток B.
• резьба А заканчивает и сигнализирует В
• Поток C входит и получает блокировку до того, как B полностью не парковался
• Поток B пытается опросить - Поток C удерживает блокировку и паркует Поток B.

Это одна возможность.

Answer 2

При просмотре исходного кода это не гарантируется. Существует механизм защищенных блоков с произвольным пробуждением одного потока в зависимости от того, как чувствует себя планировщик.

 notEmpty.signal(); // propagate to a non-interrupted thread

Полный код: http://kickjava.com/src/java/util/concurrent/LinkedBlockingQueue.java.htm

Редактировать: просто снова посмотрел на ReenterantLock и Condition, потоки сигнализируются в порядке FIFO, очевидно Итак, первый поток, ожидающий вставки, будет сигнализироваться первым. Однако это детали реализации! Не надейтесь на них.

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

Answer 3

Итак, копаясь в недрах исходного кода Java 6 (пропустите часть между горизонтальными правилами, если вас не интересует фактический код, ответственный за этот материал)

---

Класс java.util.concurrent.LinkedBlockingQueue реализует мьютекс с использованием экземпляров java.util.concurrent.locks.ReentrantLock.

В свою очередь, переменные синхронизации генерируются с использованием java.util.concurrent.locks.ReentrantLock.newCondition(), что вызывает java.util.concurrent.locks.ReentrantLock$Sync.newCondition().

Метод java.util.concurrent.locks.ReentrantLock$Sync.newCondition() возвращает экземпляр java.util.concurrent.AbstractQueuedSynchronizer$ConditionObject, который реализует обычные вызовы переменных синхронизации для await(), signal() и signalAll(), описанные интерфейсом java.util.concurrent.locks.Condiion.

---

Глядя на исходный код класса ConditionObject, он сохраняет два члена с именами firstWaiter и lastWaiter, которые являются первым и последним узлами в очереди блокировки CLH (экземпляры java.util.concurrent.locks.AbstractQueuedSynchronizer$Node).

Документация в этом классе гласит:

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

Таким образом, я полагаю, что ответ здесь заключается в том, что метод take() в LinkedBlockingQueue пытается предоставить преференциальный режим тем потокам, которые ранее вызывали take(). Это даст первому потоку, который вызовет take(), первый шанс получить элемент очереди, когда он станет доступным, но из-за таймаутов, прерываний и т. Д. Этому потоку не гарантируется, что будет первым потоком, получить предмет из очереди.

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