Esta é uma postagem traduzida por IA.
Selecionar idioma
Texto resumido pela IA durumis
- Coleções sincronizadas, como Vector, Hashtable e Collections.synchronizedXXX, usam a palavra-chave synchronized internamente para garantir a simultaneidade, mas podem resultar em problemas de desempenho quando várias operações são agrupadas ou quando o desempenho diminui.
- O pacote java.util.concurrent fornece várias classes, como CopyOnWriteArrayList, ConcurrentMap e ConcurrentHashMap, que fornecem coleções paralelas que oferecem um desempenho superior às coleções sincronizadas.
- Coleções paralelas como CopyOnWriteArrayList e ConcurrentHashMap têm um desempenho de leitura superior ao das coleções sincronizadas e são eficientes para usar quando as operações de escrita são relativamente raras.
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
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
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... 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().
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... 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.
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() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); 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:
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.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... 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.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} 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
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} O método contains() mostrado acima usa o método do CopyOnWriteArraySet, pois o CopyOnWriteArraySet define internamente o CopyOnWriteArrayList.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;Observando o método contains() do CopyOnWriteArrayList, notamos que ele não está travado.
Operação de gravação
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} O método add() também usa o método do CopyOnWriteArrayList.
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
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[] tab = table;;) {
Node 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(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 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 pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)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.
static final Node tabAt(Node[] tab, int i) {
return (Node)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.
static final boolean casTabAt(Node[] tab, int i, Node c, Node 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
(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.
