제이온

[Java] Coleção Sincronizada vs Coleção Concorrente

  • Idioma de escrita: Coreana
  • País de referência: Todos os paísescountry-flag
  • TI

Criado: 2024-04-25

Criado: 2024-04-25 22:31

Coleção Sincronizada

As coleções sincronizadas são representadas principalmente pelas seguintes classes:


  • Vector
  • Hashtable
  • Collections.synchronizedXXX


Todos esses métodos declarados como públicos usam a palavra-chave synchronized para garantir a sincronização, controlando o acesso a valores internos por apenas um thread.


Vector

```javascript public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { ... public synchronized boolean add(E e) { modCount++; add(e, elementData, elementCount); return true; } ... }

Se observarmos o método add() da classe Vector, que adiciona um elemento, vemos a palavra-chave synchronized. Em outras palavras, a inserção de elementos no Vector é sincronizada internamente.

Hashtable

```javascript public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); }

}


Se observarmos o método contains() da classe Hashtable, que verifica se um valor idêntico existe, vemos que, como a classe Vector, a palavra-chave synchronized é usada.


Collections.synchronizedXXX

Vamos observar a classe SynchronizedList criada usando o método Collections.synchronizedList().


```javascript static class SynchronizedList extends SynchronizedCollection implements List {

}


Observando os métodos da classe SynchronizedList, notamos que todos usam a palavra-chave synchronized. No entanto, o mutex é usado para implementar a sincronização usando blocos synchronized. Como todos os métodos compartilham o objeto mutex, quando um thread entra no bloco synchronized, o bloco synchronized de outros métodos é bloqueado.


Problemas da coleção sincronizada

Embora seja necessário usar coleções sincronizadas em ambientes multithread, é melhor usar outros métodos de sincronização se possível. Existem duas razões principais para isso.


Quando várias operações são agrupadas como uma única operação

As classes de coleção sincronizadas garantem a sincronização em ambientes multithread. No entanto, se várias operações forem agrupadas como uma única operação, problemas podem surgir. O uso de coleções sincronizadas pode não funcionar corretamente nesses casos.


```javascript final List list = Collections.synchronizedList(new ArrayList()); final int nThreads = 2; ExecutorService es = Executors.newFixedThreadPool(nThreads);

for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {

}


Se o Thread A executar remove(0) e o Thread B executar clear() ao mesmo tempo, ocorrerá um erro. Portanto, a operação deve ser agrupada em um bloco sincronizado, como mostrado abaixo:


```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }


Degradação de desempenho

Se todos os métodos que desejam usar o objeto compartilhado forem convertidos em métodos sincronizados ou se um bloco synchronized idêntico for definido dentro do método, quando um thread obtiver a trava, os outros threads não poderão usar todos os métodos sincronizados e ficarão bloqueados. Essa repetição pode levar à degradação do desempenho.


Coleção Concorrente

O pacote java.util.concurrent fornece vários tipos de coleções paralelas. Abordaremos alguns deles neste artigo.


  • CopyOnWriteArrayList
    • Uma subclasse da classe List, esta coleção paralela prioriza o desempenho das operações de leitura, iterando sobre a lista de objetos.
  • ConcurrentMap
    • Uma coleção paralela que define operações como put-if-absent, replace e remoção condicional, que adicionam novos itens somente se não existirem.
  • ConcurrentHashMap
    • Uma subclasse de ConcurrentMap, esta coleção paralela substitui HashMap e fornece paralelismo.
  • ConcurrentLinkedQueue
    • Uma fila FIFO que fornece paralelismo. Retorna imediatamente se não houver elementos para serem removidos da fila e prossegue com outra tarefa.
  • LinkedBlockingQueue
    • Similar a ConcurrentLinkedQueue. No entanto, se a fila estiver vazia, a operação de remoção de itens da fila aguardará até que um novo item seja adicionado. Por outro lado, se a fila tiver um tamanho definido, a operação de adição de novos itens à fila aguardará até que haja espaço disponível na fila.
  • ConcurrentSkipListMap, ConcurrentSkipListSet
    • Uma forma aprimorada de SortedMap e SortedSet para aumentar o paralelismo.


A simples substituição das classes de coleção sincronizada existentes por coleções paralelas pode melhorar significativamente o desempenho geral sem fatores de risco adicionais.

Vamos examinar de perto as coleções sincronizadas em contraste com as coleções paralelas.


CopyOnWriteArrayList

Existem duas maneiras de criar uma ArrayList sincronizada:


  • Collections.synchronizedList()
  • CopyOnWriteArrayList


Collections.synchronizedList() foi adicionado na versão JDK 1.2. Esta coleção é sincronizada em todas as operações de leitura e gravação, o que a torna um design rígido. Portanto, o CopyOnWriteArrayList foi introduzido para superar esse problema.


Operação de leitura

O SynchronizedList trava a própria instância durante as operações de leitura e gravação. No entanto, o CopyOnWriteArrayList cria um novo array temporário copiando os elementos do array original durante cada operação de gravação, executa a operação de gravação nesse array temporário e, em seguida, atualiza o array original. Isso permite que as operações de leitura sejam concluídas sem trava, resultando em um melhor desempenho do que o SynchronizedList.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


O método get() mostrado acima não possui synchronized, portanto não é travado.


Operação de gravação

O CopyOnWriteArrayList usa uma trava explícita ao executar uma operação de gravação. Em última análise, ambas as coleções são travadas durante essa operação. Como o CopyOnWriteArrayList realiza a operação de cópia de array, que é relativamente cara, o desempenho pode ser afetado se muitas operações de gravação forem executadas.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


O método add() mostrado acima usa um bloco synchronized para travar e executar a operação de cópia de array.


Iterator

No CopyOnWriteArrayList, os dados da coleção no momento em que o iterator é extraído são usados para iteração. Como quaisquer alterações na coleção, como adição ou exclusão de dados, são refletidas na cópia durante a iteração, independentemente do loop, não há problemas de uso simultâneo.


CopyOnWriteArraySet

Existem duas maneiras de criar um Set sincronizado:


  • Collections.synchronizedSet()
  • CopyOnWriteArraySet


Como o nome do método indica, a funcionalidade do CopyOnWriteArraySet é quase idêntica à do CopyOnWriteArrayList, exceto pela estrutura de dados.


Operação de leitura

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


O método contains() mostrado acima usa o método do CopyOnWriteArraySet, pois o CopyOnWriteArraySet define internamente o CopyOnWriteArrayList.


```javascript public boolean contains(Object o) { return indexOf(o) >= 0; }

public int indexOf(Object o) { Object[] es = getArray(); return indexOfRange(o, es, 0, es.length); }

}


Observando o método contains() do CopyOnWriteArrayList, notamos que ele não está travado.


Operação de gravação

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


O método add() também usa o método do CopyOnWriteArrayList.


```javascript public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOfRange(e, snapshot, 0, snapshot.length) < 0 && addIfAbsent(e, snapshot); }

private boolean addIfAbsent(E e, Object[] snapshot) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && Objects.equals(e, current[i])) return false; if (indexOfRange(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } }


Observando o método addIfAbsent(), notamos que ele trava durante a operação de gravação e copia o array. Portanto, como o CopyOnWriteArraySet, é melhor evitar muitas operações de gravação com o CopyOnWriteArrayList.


ConcurrentHashMap

Existem duas maneiras de criar um HashMap sincronizado:


  • Collections.synchronizedMap(new HashMap<>())
  • ConcurrentHashMap


O ConcurrentHashMap é um mapa baseado em hash, assim como o HashMap. Ele fornece sincronização de maneira mais eficiente do que o synchronizedMap.


Antes do Java 8, o Segment, que herda do ReentrantLock, era usado para dividir o mapa em seções e travar cada seção separadamente.


Do Java 8 em diante, cada bucket da tabela é travado independentemente. Se um nó for inserido em um bucket vazio, o algoritmo CAS é usado em vez de uma trava. Para outras alterações, uma trava parcial (bloco synchronized) é obtida com base no primeiro nó do bucket, minimizando a contenção de threads e garantindo a sincronização.


Vamos verificar como a sincronização é garantida observando o código do método putVal(), que insere um novo nó no ConcurrentHashMap. Observe que o código de exemplo a seguir é para o Java 11.


O método putVal() pode ser dividido em dois casos (quatro bifurcações no total):


  • Inserindo um nó em um bucket de hash vazio
  • Se já houver um nó no bucket de hash


```javascript final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; K fk; V fv; if (tab null || (n = tab.length) 0) tab = initTable(); // (1) else if ((f = tabAt(tab, i = (n - 1) & hash)) null) { // (2) if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent // check first node without acquiring lock && fh hash && ((fk = f.key) key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; // (3) else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // (4) if (e.hash hash && ((ek = e.key) key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; // (5) if ((e = e.next) null) { pred.next = new Node<K,V>(hash, key, value); break; } } } // (6) else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } ... } } ... }


Inserindo um nó em um bucket de hash vazio

(1) Para inserir um novo nó, o valor do bucket correspondente (tabAt()) é obtido para verificar se está vazio.


```javascript static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); }


(2) O valor volátil armazenado no nó é acessado para comparação com o valor existente (nulo). Se forem iguais, um novo nó é armazenado. Caso contrário, o loop é reiniciado. Este método é o algoritmo CAS.


```javascript static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }


O algoritmo CAS é usado para resolver problemas de atomicidade e visibilidade, garantindo a sincronização.


Se já houver um nó no bucket de hash

(3) Se já houver um nó, um bloco synchronized é usado para permitir que apenas um thread acesse o bucket. Nesse caso, uma trava é aplicada ao bucket de hash do tipo Node<K, V> não vazio, fazendo com que os threads que acessam o mesmo bucket fiquem bloqueados.

(4) O nó é substituído por um novo.

(5) Se houver uma colisão de hash, ele é adicionado ao Separate Chaing.

(6) Se houver uma colisão de hash, ele é adicionado à árvore.


Referências


Perguntas e Respostas Esperadas em Entrevistas

Quais são os problemas do Vector, HashTable e Collections.SynchronziedXXX?

As classes Vector, HashTable e SynchronziedXxx usam métodos ou blocos synchronized e compartilham um único objeto de bloqueio. Portanto, se um thread obtiver o bloqueio na coleção, os outros threads não poderão usar nenhum método e ficarão bloqueados. Isso pode resultar em degradação do desempenho do aplicativo.


Qual a diferença entre SynchronizedList e CopyOnArrayList?

O SynchronizedList trava a própria instância durante as operações de leitura e gravação. No entanto, o CopyOnArrayList trava o bloco correspondente durante as operações de gravação, copia os elementos do array original para criar um novo array temporário, executa a operação de gravação nesse array temporário e, em seguida, atualiza o array original. Isso permite que as operações de leitura sejam concluídas sem trava, resultando em um melhor desempenho de leitura do que o SynchronizedList. No entanto, as operações de gravação têm um custo mais alto devido à operação de cópia de array, resultando em um desempenho de gravação mais lento do que o SynchronizedList.

Portanto, o uso do CopyOnArrayList é mais eficaz quando há mais operações de leitura do que operações de modificação.


Qual a diferença entre SynchronizedMap e ConcurrentHashMap?

O SynchronziedMap trava a própria instância durante as operações de leitura e gravação. No entanto, o ConcurrentHashMap trava cada bucket da tabela independentemente. Se um nó for inserido em um bucket vazio, o algoritmo CAS é usado em vez de uma trava. Para outras alterações, uma trava parcial (bloco synchronized) é obtida com base no primeiro nó do bucket, minimizando a contenção de threads e garantindo a sincronização.

Comentários0