LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Minha pergunta se refere a essa pergunta feita anteriormente. Em situações em que estou usando uma fila para comunicação entre os encadeamentos do produtor e do consumidor, as pessoas geralmente recomendam o uso de LinkedBlockingQueueou ConcurrentLinkedQueue?

Quais são as vantagens / desvantagens de usar um em relação ao outro?

A principal diferença que posso ver da perspectiva da API é que a LinkedBlockingQueuepode ser opcionalmente limitada.

java multithreading data-structures concurrency queue Adamski
fonte

Respostas:

110

Para um segmento de produtor / consumidor, não tenho certeza se ConcurrentLinkedQueueé uma opção razoável - ele não implementa BlockingQueue, que é a interface fundamental para filas de produtor / consumidor IMO. Você teria que ligar poll(), esperar um pouco se não tivesse encontrado nada e, em seguida, pesquisar novamente etc ... levando a atrasos quando um novo item chega e ineficiências quando está vazio (devido ao acordar desnecessariamente do sono) .

Dos documentos para BlockingQueue:

BlockingQueue implementações são projetadas para serem usadas principalmente para filas produtor-consumidor

Eu sei que não diz estritamente que apenas as filas de bloqueio devem ser usadas para as filas produtor-consumidor, mas mesmo assim ...

Jon Skeet
fonte
4
Obrigado Jon - eu não tinha percebido isso. Então, onde / por que você usaria ConcurrentLinkedQueue?
Adamski de
27
Quando você precisa acessar a fila de vários threads, mas não precisa "esperar" por isso.
Jon Skeet de
2
A ConcurrentLinkedQueuetambém é útil se sua thread estiver verificando várias filas. Por exemplo, em um servidor multilocatário. Supondo que, por motivos de isolamento, você não use uma única fila de bloqueio e um discriminador de inquilino.
LateralFractal
seu caso só é verdadeiro se usarmos fila limitada , em fila ilimitadatake() e put()apenas consumir recursos extras (interms de sincronização) do que ConcurrentLinkedQueue . embora seja o caso de usar filas limitadas para cenários produtor-consumidor
amarnath harish
@Adamski IMO, ConcurrentLinkedQueue é apenas uma lista vinculada para ser usada em um ambiente multithread. A melhor analogia para isso seria ConcurrentHashMap e HashMap.
Nishit
69

Esta pergunta merece uma resposta melhor.

Java ConcurrentLinkedQueueé baseado no famoso algoritmo de Maged M. Michael e Michael L. Scott para bloqueio sem bloqueio sem bloqueio filas .

"Sem bloqueio" como um termo aqui para um recurso em disputa (nossa fila) significa que, independentemente do que o agendador da plataforma faz, como interromper um thread ou se o thread em questão é simplesmente muito lento, outros threads disputam o mesmo recurso ainda será capaz de progredir. Se houver um bloqueio envolvido, por exemplo, o encadeamento que o contém pode ser interrompido e todos os encadeamentos que aguardam esse bloqueio serão bloqueados. Bloqueios intrínsecos (osynchronized palavra chave) em Java também podem vir com uma grande penalidade para o desempenho - como quando o bloqueio tendenciosoestá envolvido e você tem contenção, ou depois que a VM decide "aumentar" o bloqueio após um período de carência de giro e bloquear threads em conflito ... é por isso que em muitos contextos (cenários de contenção baixa / média), fazendo comparação e -sets em referências atômicas podem ser muito mais eficientes e isso é exatamente o que muitas estruturas de dados sem bloqueio estão fazendo.

O Java ConcurrentLinkedQueuenão só não bloqueia, mas também tem a propriedade incrível de que o produtor não contende com o consumidor. Em um cenário de produtor / consumidor único (SPSC), isso realmente significa que não haverá contenção. Em um cenário de produtor múltiplo / consumidor único, o consumidor não contenderá com os produtores. Essa fila tem contenção quando vários produtores tentam offer(), mas isso é simultaneidade por definição. É basicamente uma fila sem bloqueio de uso geral e eficiente.

Por não ser um BlockingQueue, bem, bloquear um thread para esperar em uma fila é uma forma terrivelmente terrível de projetar sistemas simultâneos. Não. Se você não consegue descobrir como usar um ConcurrentLinkedQueueem um cenário de consumidor / produtor, apenas mude para abstrações de nível superior, como uma boa estrutura de ator.

Alexandru Nedelcu
fonte
8
Por seu último parágrafo, por que você diz que esperar em uma fila é uma maneira terrível de projetar sistemas simultâneos? Se temos um grupo de threads com 10 threads comendo tarefas de uma fila de tarefas, o que há de errado em bloquear quando a fila de tarefas tem menos de 10 tarefas?
Pacerier
11
@AlexandruNedelcu Você não pode fazer uma afirmação abrangente como "assustadoramente terrível", onde muitas vezes os próprios frameworks de ator que você diz para usar usam threadpools que você mesmo BlockingQueue . Se você precisa de um sistema altamente reativo e sabe como lidar com a contrapressão (algo que as filas de bloqueio mitigam), o não-bloqueio é claramente superior. Mas .. muitas vezes bloquear IO e bloquear filas pode executar o nonblocking, especialmente se você tiver tarefas de longa execução que são vinculadas a IO e não podem ser divididas e conquistadas.
Adam Gent
1
@AdamGent - Os frameworks de ator têm implementação de caixas de correio com base em filas de bloqueio, mas isso é um bug na minha opinião, porque o bloqueio não funciona em limites assíncronos e, portanto, só funciona em demos. Para mim, isso tem sido uma fonte de frustração, pois, por exemplo, a noção da Akka de lidar com o estouro é bloquear, em vez de descartar as mensagens, até a versão 2.4, isto é, que ainda não foi lançada. Dito isso, não acredito que existam casos de uso para os quais as filas de bloqueio possam ser superiores. Você também está confundindo duas coisas que não deveriam ser confundidas. Eu não falei sobre o bloqueio de E / S.
Alexandru Nedelcu,
1
@AlexandruNedelcu, embora eu geralmente concorde com você sobre a contrapressão, ainda não vi um sistema de "bloqueio livre" de cima para baixo. Em algum lugar em uma pilha de tecnologia, seja Node.js, Erlang, Golang, está usando algum tipo de estratégia de espera, seja uma fila de bloqueio (bloqueios) ou CAS girando seu bloqueio e, em alguns casos, uma estratégia de bloqueio tradicional é mais rápida. É muito difícil não ter bloqueios por causa da consistência e isso é especialmente importante com o bloqueio de io e agendadores que são ~ Produtor / Consumidor. ForkJoinPool funciona com tarefas de execução curta e ainda tem travas giratórias CAS.
Adam Gent
1
@AlexandruNedelcu Eu acho que se você puder me mostrar como você pode usar um ConcurrentLinkedQueue (que não é limitado btw, portanto, meu argumento de contrapressão fraca) para o padrão Produtor / Consumidor, que é um padrão necessário para agendadores e encadeamento, acho que vou desistir e admitir que O BlockingQueue nunca deve ser usado (e você não pode trapacear e delegar a outra pessoa fazendo o agendamento, ou seja, akka, já que isso por sua vez fará o bloqueio / espera, pois é um produtor / consumidor).
Adam Gent
33

LinkedBlockingQueuebloqueia o consumidor ou o produtor quando a fila está vazia ou cheia e o respectivo segmento de consumidor / produtor é colocado em hibernação. Mas esse recurso de bloqueio tem um custo: cada operação de colocação ou retirada é disputada por bloqueio entre os produtores ou consumidores (se houver), portanto, em cenários com muitos produtores / consumidores, a operação pode ser mais lenta.

ConcurrentLinkedQueuenão está usando bloqueios, mas CAS , em suas operações put / take potencialmente reduzindo a contenção com muitos encadeamentos de produtor e consumidor. Porém, sendo uma estrutura de dados "livre de espera", ConcurrentLinkedQueuenão será bloqueada quando vazia, o que significa que o consumidor precisará lidar com os valores take()retornados nullpor "espera ocupada", por exemplo, com a thread do consumidor consumindo CPU.

Então, qual é "melhor" depende do número de threads de consumo, da taxa que eles consomem / produzem, etc. Um benchmark é necessário para cada cenário.

Um caso de uso específico em que o ConcurrentLinkedQueueé claramente melhor é quando os produtores primeiro produzem algo e terminam seu trabalho, colocando o trabalho na fila, e somente depois que os consumidores começam a consumir, sabendo que o farão quando a fila estiver vazia. (aqui não há concorrência entre produtor-consumidor, mas apenas entre produtor-produtor e consumidor-consumidor)

dcernahoschi
fonte
uma dúvida aqui. Como você mencionou, o consumidor espera quando a fila está vazia ... quanto tempo ele espera. Quem vai avisar pra não esperar?
Brinal
@brindal A única maneira de esperar, que eu saiba, é em um loop. Que é um problema significativo ao qual não foi dada muita atenção nas respostas aqui. Apenas executar um loop à espera de dados consome muito tempo do processador. Você saberá quando seus fãs começarem a acelerar. O único remédio é adormecer. Portanto, é um problema em um sistema com fluxo de dados inconsistente. Talvez eu não tenha entendido a resposta de AlexandruNedelcu, mas um sistema operacional em si é um sistema simultâneo, que seria extremamente ineficiente se estivesse cheio de loops de eventos sem bloqueio.
orodbhen
ok, mas se unbounded blockingqueuefor usado, seria melhor do que o concorrente baseado em CASConcurrentLinkedQueue
amarnath harish
@orodbhen Adormecer também não eliminaria o desperdício. O sistema operacional tem que fazer muito trabalho para tirar um thread do repouso e programá-lo e executá-lo. Se as mensagens ainda não estiverem disponíveis, o trabalho feito pelo seu sistema operacional será desperdiçado. Eu recomendaria que seja melhor usar BlockingQueue, pois ele foi projetado especificamente para o problema produtor-consumidor.
Nishit
Na verdade, estou muito interessado na parte "taxa de consumo / produção", então qual é melhor se a taxa subir?
workplaylifecycle de
0

Outra solução (que não se adapta bem) são os canais de rendezvous: java.util.concurrent SynchronousQueue

Ovidiu Lupas
fonte
0

Se sua fila não for expansível e contiver apenas um encadeamento produtor / consumidor. Você pode usar a fila sem bloqueio (você não precisa bloquear o acesso aos dados).

Rahul
fonte