No capítulo anterior, explicamos a fila de bloqueio implementada no ArrayBlockingQueue, usando o formulário de matriz.
O comprimento da matriz deve ser determinado ao criar. Se o comprimento da matriz for pequeno, a fila de matriz será facilmente bloqueada. Se o comprimento da matriz for grande, ele desperdiçará facilmente a memória.
A estrutura de dados da fila é naturalmente adequada para a forma de listas vinculadas, e o LinkedBlockingQueue é uma fila de bloqueio implementada usando listas vinculadas.
1. Implementação da lista vinculada
1.1 Classe interna do nó
/ *** O nó da lista vinculado também é usado para implementar uma lista vinculada de uma via*/ nó de classe estática <E> {e item; // apontar para o próximo nó do nó da lista vinculado <E> Next; Nó (e x) {item = x; }}Há uma variável E que armazena dados e há uma próxima referência variável apontando para o próximo nó. Ele pode implementar a lista única mais simples.
1.2 Como implementar a lista de links
/ *** Seu próximo ponto para a cabeça da fila, e este nó não armazena dados*/ nó transitório <E> Head; / *** Nó da cauda da fila*/ nó transitório privado <E> Último;
Para implementar uma lista vinculada, deve haver duas variáveis, uma representa o chefe da lista vinculada e a outra representa a última lista vinculada. A cabeça e a última são inicializadas quando o objeto LinkedBlockingQueue é criado.
last = head = novo nó <E> (nulo);
Observe que um pequeno truque é usado aqui. O nó da cabeça da lista vinculada não armazena dados. O próximo nó aponta para realmente armazenar os primeiros dados na lista vinculada. O último no final da lista vinculado armazena os últimos dados na lista vinculada.
1.3 Inserir e excluir nós
/ *** Insira o nó na cauda da fila*/ private void Enqueue (nó <E> nó) {// Assert putlock.isheldbycurrentThread (); // O encadeamento atual deve ter obtido o bloqueio de putlock // apontar a próxima referência do nó da fila original para o novo nó do nó e, em seguida, defina o nó do nó no nó da cauda da fila last //, que percebe o nó de inserção na cauda da fila last = last.next = node; }É muito simples inserir um nó no final da lista vinculada. Aponte o próximo nó da fila original por último ao novo nó e atribua o novo nó do nó ao último nó no final da fila. Isso permite a inserção de um novo nó.
// Remova o nó da cabeça da fila e retorne os dados do nó excluído private e dequeue () {// assert Takelock.isheldbyCurrentThread (); // O encadeamento atual deve ter obtido o bloqueio de takelock // afirma cabeças.item == null; Nó <e> h = cabeça; // Os dados do primeiro elemento na fila são armazenados no primeiro nó <e> primeiro = h.next; h.next = h; // Ajuda GC // Definir o novo valor da cabeça é equivalente a excluir o primeiro nó. Porque o nó da cabeça em si não armazena a cabeça de dados = primeiro; // os dados do cabeçalho da fila e x = primeiro.item; // remova os dados originais primeiro.item = null; retornar x; }Observe que a cabeça não é o cabeçalho, seu próximo ponto para o cabeçalho, por isso é muito simples excluir o cabeçalho, que é atribuir a cabeça.
Ao excluir, preste atenção à situação em que a lista vinculada está vazia. O valor da cabeça.Next é adicionado usando o método de enquadrão. Quando Head.Next == Last, significa que o último elemento foi excluído. Quando Head.Next == NULL, ele não pode ser excluído porque a lista vinculada já está vazia. Não há julgamento aqui porque o julgamento foi feito no local onde o método Dequeue é chamado.
2. Reentrantlock e condição síncronos de bloqueio
Como a fila de bloqueio deve ser bloqueada e esperada quando a fila está vazia e a fila está cheia, duas condições são naturalmente necessárias. Para garantir a segurança da simultaneidade com vários threads, é necessária uma trava de sincronização. Isso foi dito no ArrayBlockingQueue.
Aqui falaremos sobre as diferentes coisas sobre o LinkedBlockingQueue.
/ ** Bloqueio exclusivo, usado para lidar com problemas de simultaneidade para inserir operações de fila, ou seja, operações de venda e oferta*/ private final reentrantlock putlock = new reentrantlock (); / ** Condição da condição com a qual a fila não está satisfeita, é gerada por putlock bloqueio*/ condição final privada notfull = putlock.newcondition (); / ** Bloqueio exclusivo, usado para lidar com problemas de simultaneidade para excluir operações da cabeça da fila, ou seja, operações de pesquisa e pesquisa*/ private Reentrantlock Takelock = new Reentrantlock (); / ** Condição de que a fila não esteja vazia, ele usa a condição final privada gerada pelo Takelock Lock*/ condição final privada NotEmpty = Takelock.newcondition ();
2.1 Putlock e Takelock
Encontramos dois bloqueios usados:
De acordo com a declaração acima, pode haver operações de inserção e exclusão de elementos ao mesmo tempo, então não haverá problema?
Vamos analisá -lo em detalhes. Para filas, as operações são divididas em três tipos:
Portanto, use a trava da putlock para manter a última variável segura e use Takelock Lock para manter a variável da cabeça segura.
Para todas as variáveis de contagem envolvidas no número de elementos na fila, o AtomicInteger é usado para garantir problemas de segurança de simultaneidade.
/ ** O número de elementos na fila, use a variável AtomicInteger aqui para garantir problemas de segurança de simultaneidade*/ private final Atomicinteger count = new atomicinteger ();
2.2 Notfull e NotEpty
2.3 Processo de controle
Ao inserir um elemento:
Ao excluir elementos:
Observe também que o sinal e os métodos de condição devem ser chamados quando um bloqueio é adquirido. Portanto, existem métodos SignalNotEmpty e SignalNotfull:
/*** Acorde o segmento esperando sob a condição noturna, ou seja, ao remover o cabeçalho da fila, o thread que é considerado vazio e forçado a esperar. * Observe que, como, para chamar o método de condição do sinal, a trava correspondente deve ser obtida, o método takelock.lock () é chamado aqui. * Quando um elemento é inserido na fila (ou seja, operação de venda ou oferta), a fila definitivamente não está vazia e esse método será chamado. */ private void SignalNotEmpty () {Final Reentrantlock Takelock = this.takelock; Takelock.lock (); tente {notempty.signal (); } finalmente {Takelock.unlock (); }} /*** Acorde o thread aguardando sob a condição noturna, ou seja, quando o elemento é adicionado no final da fila, a rosca cheia e forçada a esperar. * Observe que, para chamar o método de condição do sinal, a trava correspondente deve ser obtida, portanto, o método putlock.lock () é chamado aqui* quando o elemento (ou seja, a operação de pegar ou votar) é excluído na fila, a fila será definitivamente insatisfeita e chamará este método. */ private void SignalNotfull () {final reentrantlock putlock = this.putLock; putlock.lock (); tente {notfull.signal (); } finalmente {putlock.unlock (); }}3. Método do elemento inserir
public void put (e e) lança interruptedException {if (e == null) lança novo nullPointerException (); // Registre o número de elementos antes da operação de inserção int c = -1; // Crie um novo nó nó <E> nó = novo nó <E> (e); final reentrantlock putlock = this.putLock; contagem final do atomicinteger = this.count; putlock.lockInterruptível (); tente {// indicar que a fila está cheia, então você precisa chamar o método notfull.await para fazer com que o thread atual aguarde enquanto (count.get () == Capacidade) {notfull.await (); } // Insira um novo elemento Enjeue (nó); // Adicione 1 ao número de elementos na fila atual e retorne o número de elementos antes de adicionar 1. C = count.getAndinCrement (); // C + 1 <Capacidade significa que a fila não está cheia e o thread que pode estar esperando a operação de inserção for despertado se (c + 1 <capacidade) notfull.signal (); } finalmente {putlock.unlock (); } // c == 0 significa que a fila está vazia antes da inserção. Quando a fila estiver vazia para um elemento que está sendo colocado, // acorde o thread aguardando a exclusão // impedir a aquisição frequente de bloqueios de takelock, consuma desempenho se (c == 0) sinalizeNoTempty (); }Tomando o método de put como exemplo, o processo geral é o mesmo que introduzimos anteriormente. Aqui está um código muito estranho. Quando o elemento é inserido, se você achar que a fila não está cheia, chame Notfull.Signal () para acordar o thread aguardando a inserção.
Todo mundo está muito confuso. De um modo geral, esse método deve ser colocado no elemento excluído (Take Series Method), porque quando excluímos um elemento, a fila deve estar sub-cheia e, em seguida, chame o método notfull.signal () para acordar o thread aguardando a inserção.
Isso é feito principalmente aqui porque, ao chamar o método do sinal, o bloqueio correspondente deve ser obtido primeiro. O bloqueio usado no método da série Take é Takelock. Se você deseja chamar o método notfull.signal (), você deve primeiro obter o bloqueio de putlock. Isso fará com que o desempenho diminua, para que outro método seja usado.
4. Exclua o elemento de cabeçalho da fila
public e Take () lança interruptedException {e x; int c = -1; contagem final do atomicinteger = this.count; Final Reentrantlock Takelock = this.takelock; Takelock.lockInterruptível (); tente {// significa que a fila está vazia, então você precisa chamar o método NotEmpty.await para fazer com que o thread atual aguarde enquanto (count.get () == 0) {notempty.await (); } // exclua o elemento do cabeçalho da fila e retorne -o x = dequeue (); // retorna o número das filas atuais e subtraia o número das filas por um c = count.getAndDecRement (); // c> 1 significa que a fila não está vazia, por isso acorda o thread que pode estar aguardando a operação de exclusão se (c> 1) nothempty.signal (); } finalmente {Takelock.unlock (); } /*** C == Capacidade significa que a fila está cheia antes da operação de exclusão. * Acorde o thread aguardando a inserção somente quando um elemento é excluído da fila completa* impede a aquisição frequente de bloqueios de putlock, consumindo desempenho*/ if (c == Capacidade) sinalizeNotl (); retornar x; }Por que o método NotEmpty.Signal () é chamado, compare nossa explicação no método do elemento de inserção.
5. Veja os elementos do cabeçalho da fila
// visualize o elemento do cabeçalho da fila public e peek () {// A fila está vazia, retorne nulo se (count.get () == 0) retorna nulo; Final Reentrantlock Takelock = this.takelock; Takelock.lock (); tente {// obtenha o nó do cabeçalho da fila primeiro nó <E> primeiro = head.next; // primeiro == null significa que a fila está vazia, retorna nulo se (primeiro == null) retorna nulo; else // retorna o elemento do cabeçalho da fila retornar primeiro.item; } finalmente {Takelock.unlock (); }}Veja o elemento do cabeçalho da fila, que envolve o nó da cabeça, para que a trava de takelock seja usada.
Vi. Outros métodos importantes
6.1 Remover (objeto o) Método
// Remova o elemento especificado da fila o Public boolean Remover (objeto o) {if (o == null) retornar false; // Porque não é excluir o elemento do cabeçalho da lista, as duas variáveis de cabeça e a última estão envolvidas, // putlock e takelock devem ser trancados totalmente (); tente {// atravessar toda a fila, p representa o nó atual e a trilha representa o nó anterior do nó atual // porque é uma lista vinculada de mão única, dois nós precisam ser gravados para (nó <e> trilh = cabeça, p = track.next; p! (O.Equals (P.Item)) {desvincular (P, Trail); retornar true; }} retornar false; } finalmente {totalmentellock (); }}Exclua o elemento especificado da lista. Como o elemento excluído não está necessariamente na cabeça da lista, pode haver duas variáveis de cabeça e, por último, então você deve usar os bloqueios de putlock e takelock ao mesmo tempo. Por ser uma lista vinculada de mão única, é necessária uma trilha variável auxiliar para gravar o nó anterior, para que o nó atual P possa ser excluído.
6.2 UNLIGH (NODE <E> P, NODE <E> Trail) Método
// Exclua o nó atual P, e a trilha representa o nó anterior de p void desvincular (nó <e> p, nó <e> tril) {// Defina os dados do nó atual como null p.item = null; // Isso exclui a trilha P do nó.next = p.next; // Se o nó p for o último último da fila e for excluído, defina a trilha para o último if (last == p) last = Trail; // subtraia o número de elementos por um, se a fila original estiver cheia, chame o método notfull.signal () // de fato, isso é chamado diretamente sem julgamento, porque o bloqueio de putlock deve ser obtido aqui se (Count.GetAndDecRement () == Capacidade) Notfull.Signal (); }Para excluir um nó p na lista vinculada, você só precisa apontar o próximo da trilha anterior do n para o próximo nó próximo do nó p.
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.