Java: LinkedBlockingQueue tiene conto dell'ordine dei consumatori?

Question

Ho 3 thread: 2 consumatori, ConsumerA e ConsumerB e uno Producer.

Ho anche un LinkedBlockingQueue queue

A t = 1: ConsumerA chiamate queue.take()

A t = 2: Consumer B chiede queue.take()

A t = 3 : Producer chiamate queue.put (foo)

È garantito che ConsumerA riceva foo prima di ConsumerB? In altre parole, l'ordine in cui i consumatori invocano take() è l'ordine in cui ciascuno viene informato?

In caso contrario, esiste una struttura dati alternativa che darà maggiore priorità in base all'ordine?

Answer 1

Dall'esame del codice sorgente, non è garantito. C'è un meccanismo di blocco custodito in atto con il risveglio di un thread a caso, a seconda di come si sente lo scheduler.

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

codice completo: http://kickjava.com/src/java/util/concurrent/LinkedBlockingQueue.java.htm

Edit: appena guardò di nuovo ReenterantLock e Condizioni, i fili sono segnalati in ordine FIFO, a quanto pare. Quindi, il primo thread in attesa dell'inserimento verrà segnalato per primo. Tuttavia, questi sono dettagli di implementazione! Non fare affidamento su di loro.

un'implementazione non è necessaria per definire esattamente le stesse garanzie o semantica per tutte e tre le forme di attesa, né è tenuto a sostenere interruzione della sospensione effettiva del filo

Answer 2

In molti casi l'ordine dei thread che entrano nella coda sarà nell'ordine appropriato. Tuttavia, la coda LinkedBlocking utilizza un blocco ingiusto. Ciò che fa è consentire ai thread di entrare l'uno sull'altro. Sebbene sia raro potrebbe accadere il seguente.

• Thread A entra e sondaggi.
• Discussione B entra cerca di sondaggio - Discussione A detiene la serratura e parchi Discussione B.
• infilare un finiture e segnali B
• Discussione C entra e acquisisce il blocco prima B in rimosse dal parcheggio completamente
• tentativi thread B per sondare - Il thread C tiene il blocco e parcheggia il thread B.

Questa è una possibilità.

Answer 3

Così scavare attraverso le viscere della sorgente di Java 6 (saltare la parte tra le regole orizzontali, se non si cura di trovare il codice vero responsabile di questa roba)

---

La classe java.util.concurrent.LinkedBlockingQueue implementa mutex usando istanze di java.util.concurrent.locks.ReentrantLock.

A sua volta, le variabili di sincronizzazione vengono generate utilizzando java.util.concurrent.locks.ReentrantLock.newCondition() che chiama java.util.concurrent.locks.ReentrantLock$Sync.newCondition().

Procedimento java.util.concurrent.locks.ReentrantLock$Sync.newCondition() restituisce un'istanza di java.util.concurrent.AbstractQueuedSynchronizer$ConditionObject che implementa le normali chiamate variabili sincronizzazione a await(), signal() e signalAll() descritte dall'interfaccia java.util.concurrent.locks.Condiion.

---

Guardando il codice sorgente per la classe ConditionObject, che mantiene due membri chiamati firstWaiter e lastWaiter che sono i primi e gli ultimi nodi in una coda di blocco CLH (istanze di java.util.concurrent.locks.AbstractQueuedSynchronizer$Node).

La documentazione a che gli stati di classe:

Un thread può cercare di acquisire se è primo in coda. Ma essere i primi non garantisce il successo; dà solo il diritto di contendere. Pertanto, il thread di concorrenti attualmente rilasciato potrebbe dover essere nuovamente visualizzato.

Così Credo che la risposta è che il metodo take() in LinkedBlockingQueue tentativi di dare un trattamento preferenziale a quelle thread che chiama take() in precedenza. Fornirà il primo thread per chiamare take() la prima possibilità di catturare un oggetto di coda quando diventa disponibile, ma a causa di timeout, interruzioni, ecc. Che thread non è garantito essere il primo thread per rimuovere l'elemento dal coda.

Ricordare che questo è completamente specifico per questa particolare implementazione. In generale, si dovrebbe supporre che le chiamate a take() si sveglieranno un thread di attesa casuale quando un elemento di coda diventa disponibile e non necessariamente il primo che ha chiamato take().