Java: Czy LinkedBlockingQueue uwzględnia kolejność klientów?

Question

Mam 3 wątki: 2 konsumentów, ConsumerA i ConsumerB i Producer.

również mieć LinkedBlockingQueue queue

W czasie t = 1: ConsumerA połączenia queue.take()

czasie t = 2: Consumer B wywołuje queue.take()

w czasie t = 3 : Producer połączenia queue.put (foo)

Czy masz gwarancję, że ConsumerA otrzyma foo przed ConsumerB? Innymi słowy, kolejność, w jakiej konsumenci wywołują take(), jest kolejnością, w której każdy jest powiadamiany?

Jeśli nie, czy istnieje alternatywna struktura danych, która da wyższy priorytet na podstawie kolejności?

Answer 1

Od patrząc na kod źródłowy, nie jest gwarantowana. Jest tam strzeżony mechanizm blokowy z przypadkowym wybudzeniem jednego wątku, w zależności od tego, jak działa harmonogram.

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

Pełny kod: http://kickjava.com/src/java/util/concurrent/LinkedBlockingQueue.java.htm

Edycja: po prostu spojrzał ponownie na ReenterantLock i kondycji, gwinty są sygnalizowane w kolejności FIFO, widocznie. Pierwszy wątek oczekiwania na wstawienie zostanie najpierw zasygnalizowany. Są to jednak szczegóły dotyczące implementacji! Nie polegaj na nich.

implementacja nie jest wymagane określić dokładnie te same gwarancje lub semantyki dla wszystkich trzech form czekania, ani nie jest zobowiązany do wspierania przerwania faktycznego zawieszenia gwintu

Answer 2

W wielu przypadkach kolejność wątków wprowadzanych do kolejki będzie w odpowiedniej kolejności. Jednak kolejka LinkedBlocking używa nieuczciwej blokady. To, co robi, pozwala wątkom wtargnąć jeden na drugiego. Chociaż rzadko się zdarza, następujące rzeczy mogą się zdarzyć.

• Wątek A wchodzi i sonduje.
• Wątek B wchodzi próbuje sondować - Temat A posiada blokady i parków B. wątku
• wykończenia nawlec i sygnały B
• Wątek C wchodzi i nabywa blokadę przed B w odparkowane pełni
• próbach Wątek B do odpytywania - wątek C zawiera blokadę i parki Gwint B.

Jest to jedna z możliwości.

Answer 3

Więc kopanie przez wnętrzności źródła Java 6 (pominąć udział między zasad horyzontalnych, jeśli nie dbają o znalezieniu rzeczywisty kod odpowiedzialny za te rzeczy)

---

Klasa java.util.concurrent.LinkedBlockingQueue realizuje używając mutex wystąpienia java.util.concurrent.locks.ReentrantLock.

Z kolei zmienne synchronizacyjne są generowane za pomocą java.util.concurrent.locks.ReentrantLock.newCondition(), która wywołuje java.util.concurrent.locks.ReentrantLock$Sync.newCondition().

Sposób java.util.concurrent.locks.ReentrantLock$Sync.newCondition() zwraca wystąpienie java.util.concurrent.AbstractQueuedSynchronizer$ConditionObject który realizuje normalne połączenia zmiennej synchronizacji do await(), signal() i signalAll() opisane przez interfejs java.util.concurrent.locks.Condiion.

---

Patrząc na kod źródłowy dla klasy ConditionObject, utrzymuje dwóch członków nazywa firstWaiter i lastWaiter, które są pierwsze i ostatnie węzły w kolejce blokady CLH (instancje java.util.concurrent.locks.AbstractQueuedSynchronizer$Node).

Dokumentacja w tejże klasy:

Wątek mogą próbować pozyskać jeśli jest pierwszy w kolejce. Ale bycie pierwszym nie gwarantuje sukcesu; daje tylko prawo do walki. Tak więc obecnie opublikowany wątek rywalizacyjny może wymagać ponownego odczytania.

Więc uważam, że odpowiedź jest to, że metoda LinkedBlockingQueue prób take() dać preferencyjnego traktowania tych wątku nazwie take() wcześniej. Da to pierwszy wątek, który wywoła take() pierwszą szansę na chwycenie elementu kolejki, gdy stanie się dostępny, ale z powodu przekroczenia czasu, przerwań itp., Że wątek nie jest gwarantowany jako pierwszy wątek, aby uzyskać element poza kolejka.

Należy pamiętać, że jest to całkowicie specyficzne dla tej konkretnej implementacji. Generalnie powinieneś założyć, że wywołania do take() obudzą losowy wątek oczekujący, gdy element kolejki stanie się dostępny i niekoniecznie pierwszy, który zadzwonił pod numer take().