Qual implementação de fila simultânea devo usar em Java?

132

No JavaDocs:

  • Um ConcurrentLinkedQueue é uma escolha apropriada quando muitos threads compartilham o acesso a uma coleção comum. Essa fila não permite elementos nulos.
  • ArrayBlockingQueue é um "buffer limitado" clássico, no qual uma matriz de tamanho fixo mantém elementos inseridos pelos produtores e extraídos pelos consumidores. Esta classe suporta uma política de justiça opcional para solicitar threads de produtor e consumidor em espera
  • O LinkedBlockingQueue normalmente tem uma taxa de transferência mais alta que as filas baseadas em matriz, mas desempenho menos previsível na maioria dos aplicativos simultâneos.

Eu tenho 2 cenários, um requer a fila para oferecer suporte a muitos produtores (threads usando) com um consumidor e o outro é o contrário.

Não entendo qual implementação usar. Alguém pode explicar quais são as diferenças?

Além disso, qual é a 'política de justiça opcional' na ArrayBlockingQueue?

David Hofmann
fonte
1
Você esqueceu de perguntar sobre PriorityBlockingQueue também, o que é útil para especificar uma ordem na qual os threads são processados.
IgorGanapolsky

Respostas:

53

Basicamente, a diferença entre eles são características de desempenho e comportamento de bloqueio.

Tomando o mais fácil primeiro, ArrayBlockingQueueé uma fila de tamanho fixo. Portanto, se você definir o tamanho em 10 e tentar inserir um 11º elemento, a instrução insert será bloqueada até que outro thread remova um elemento. O problema da justiça é o que acontece se vários encadeamentos tentarem inserir e remover ao mesmo tempo (em outras palavras, durante o período em que a Fila foi bloqueada). Um algoritmo de justiça garante que o primeiro thread que solicita seja o primeiro que recebe. Caso contrário, um determinado encadeamento poderá esperar mais tempo do que outros, causando um comportamento imprevisível (algumas vezes, um encadeamento levará apenas alguns segundos porque outros encadeamentos iniciados posteriormente foram processados ​​primeiro). A desvantagem é que é preciso sobrecarga para gerenciar a justiça, diminuindo a produtividade.

A diferença mais importante entre LinkedBlockingQueuee ConcurrentLinkedQueueé que, se você solicitar um elemento de LinkedBlockingQueueae a fila estiver vazia, seu encadeamento aguardará até que exista algo lá. A ConcurrentLinkedQueueretornará imediatamente com o comportamento de uma fila vazia.

Qual deles depende se você precisar do bloqueio. Onde você tem muitos produtores e um consumidor, parece que sim. Por outro lado, onde você tem muitos consumidores e apenas um produtor, pode não precisar do comportamento de bloqueio e pode ficar feliz em pedir que os consumidores verifiquem se a fila está vazia e siga em frente.

Yishai
fonte
67
A resposta é enganosa. O LinkedBlockingQueue e o ConcurrentLinkedQueue têm o método "poll ()", que remove o cabeçalho da fila ou retorna nulo (não bloqueia) e o método "offer (E e)", que é inserido na cauda da fila e não é bloqueado. A diferença é que apenas o LinkedBlockingQueue possui operações de bloqueio além das operações sem bloqueio - e, por esse privilégio, você paga o preço que o LinkedBlockingQueue realmente possui algum bloqueio. A outra resposta explica isso.
Nakedible
123

ConcurrentLinkedQueue significa que nenhum bloqueio é realizado (ou seja, nenhuma chamada sincronizada (isso) ou Lock.lock ). Ele utilizará uma operação CAS - Compare e Swap durante as modificações para verificar se o nó principal / final ainda é o mesmo de quando foi iniciado. Nesse caso, a operação é bem-sucedida. Se o nó da cabeça / cauda for diferente, ele girará e tentará novamente.

LinkedBlockingQueue terá um bloqueio antes de qualquer modificação. Portanto, suas chamadas de oferta serão bloqueadas até que elas atinjam o bloqueio. Você pode usar a sobrecarga de oferta que leva um TimeUnit para dizer que só deseja esperar X tempo antes de abandonar a adição (geralmente bom para filas de tipo de mensagem em que a mensagem é obsoleta após um número X de milissegundos).

Justiça significa que a implementação do bloqueio manterá os encadeamentos ordenados. Ou seja, se o Thread A entrar e depois o Thread B, o Thread A obterá o bloqueio primeiro. Sem justiça, é indefinido o que realmente acontece. Provavelmente será o próximo segmento agendado.

Quanto a qual usar, depende. Costumo usar ConcurrentLinkedQueue porque o tempo que meus produtores levam para colocar trabalho na fila é diverso. Não tenho muitos produtores produzindo exatamente no mesmo momento. Mas o lado do consumidor é mais complicado porque a pesquisa não entra em bom estado de sono. Você tem que lidar com isso sozinho.

Justin Rudd
fonte
1
E sob quais condições o ArrayBlockingQueue é melhor que o LinkedBlockingQueue?
Kolobok
@akapelko ArrayBlockingQueue permite pedidos mais detalhados.
IgorGanapolsky
2
O que isso significa - "ele girará e tentará novamente". ?
Lester
9

O título da sua pergunta menciona Bloquear filas. No entanto, nãoConcurrentLinkedQueue é uma fila de bloqueio.

Os BlockingQueues são ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, e SynchronousQueue.

Alguns destes não são claramente apto para a sua finalidade ( DelayQueue, PriorityBlockingQueue, e SynchronousQueue). LinkedBlockingQueuee LinkedBlockingDequesão idênticos, exceto que o último é uma Fila de extremidade dupla (implementa a interface Deque).

Como ArrayBlockingQueuesó é útil se você quiser limitar o número de elementos, eu continuaria LinkedBlockingQueue.

Powerlord
fonte
Eu removi a palavra Bloqueio do título, obrigado. Deixe-me ver se eu entendi, o que você disse significa que o LinkedBlockingQueue pode ser usado em consumidores com várias opções / produz cenários sobre o mesmo objeto?
David Hofmann
1
Eu pensei que ArrayBlockingQueue permite uma ordenação mais refinada de threads? Daí a sua vantagem.
IgorGanapolsky
4

ArrayBlockingQueue tem menor espaço de memória, pode reutilizar o nó do elemento, não como o LinkedBlockingQueue, que precisa criar um objeto LinkedBlockingQueue $ Node para cada nova inserção.

Deng
fonte
1
bom ponto! eu prefiro ArrayBlockingQueue mais do que LinkedBlockingQueue
trilhões
2
Isso não é necessariamente verdade - se a sua fila ficar quase vazia o tempo todo, mas precisar aumentar, o espaço ArrayBlockingQueuepara memória será muito pior - ainda haverá uma grande matriz alocada na memória o tempo todo, enquanto o espaço LinkedBlockingQueueterá memória insignificante quando estiver quase vazio.
Krease 8/08/14
1
  1. SynchronousQueue(Retirado de outra pergunta )

SynchronousQueueé mais uma transferência, enquanto o LinkedBlockingQueuejust permite um único elemento. A diferença é que a put()chamada para a SynchronousQueuenão retornará até que haja uma take()chamada correspondente , mas com LinkedBlockingQueuetamanho 1, a put()chamada (para uma fila vazia) retornará imediatamente. É essencialmente a BlockingQueueimplementação para quando você realmente não deseja uma fila (não deseja manter nenhum dado pendente).

  1. LinkedBlockingQueue( LinkedListImplementação, mas não exatamente a implementação do JDK) LinkedListEle usa o nó estático da classe interna para manter os links entre os elementos)

Construtor para LinkedBlockingQueue

public LinkedBlockingQueue(int capacity) 
{
        if (capacity < = 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node< E >(null);   // Maintains a underlying linkedlist. ( Use when size is not known )
}

Classe de nó usada para manter links

static class Node<E> {
    E item;
    Node<E> next;
    Node(E x) { item = x; }
}

3) ArrayBlockingQueue (Implementação de matriz)

Construtor para ArrayBlockingQueue

public ArrayBlockingQueue(int capacity, boolean fair) 
{
            if (capacity < = 0)
                throw new IllegalArgumentException();
            this.items = new Object[capacity]; // Maintains a underlying array
            lock = new ReentrantLock(fair);
            notEmpty = lock.newCondition();
            notFull =  lock.newCondition();
}

Maior diferença entre IMHO ArrayBlockingQueuee LinkedBlockingQueueé clara a partir do construtor um tem matriz de estrutura de dados subjacente e outro linkedList .

ArrayBlockingQueueusa o algoritmo de condição dupla de bloqueio único e LinkedBlockingQueueé uma variante do algoritmo "fila de dois bloqueios" e possui 2 condições de 2 bloqueios (takeLock, putLock)

Vipin
fonte
0

ConcurrentLinkedQueue não tem bloqueio, LinkedBlockingQueue não. Toda vez que você chama o LinkedBlockingQueue.put () ou o LinkedBlockingQueue.take (), é necessário adquirir o bloqueio primeiro. Em outras palavras, o LinkedBlockingQueue tem baixa concorrência. Se você gosta de desempenho, tente ConcurrentLinkedQueue + LockSupport.

user319609
fonte