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
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
}
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
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
}
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
}
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
}
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
}
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