To jest post przetłumaczony przez AI.
Wybierz język
Tekst podsumowany przez sztuczną inteligencję durumis
- Zsynchronizowane kolekcje, takie jak Vector, Hashtable, Collections.synchronizedXXX, wewnętrznie wykorzystują słowo kluczowe synchronized, aby zapewnić współbieżność, ale mogą prowadzić do problemów z wydajnością, gdy wiele operacji jest grupowanych lub wykonywanych jednocześnie.
- Pakiet java.util.concurrent zapewnia różne klasy kolekcji równoległych, takie jak CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap, które oferują lepszą wydajność niż zsynchronizowane kolekcje.
- Kolekcje równoległe, takie jak CopyOnWriteArrayList, ConcurrentHashMap, są bardziej wydajne podczas odczytu w porównaniu ze zsynchronizowanymi kolekcjami, a ich użycie jest efektywne w przypadku niewielkiej liczby operacji zapisu.
Zsynchronizowane kolekcje
Zsynchronizowane kolekcje są reprezentowane głównie przez następujące klasy:
- Vector
- Hashtable
- Collections.synchronizedXXX
Wszystkie te klasy wykorzystują słowo kluczowe synchronized w metodach zadeklarowanych jako publiczne, aby zapewnić, że tylko jeden wątek może uzyskać dostęp do wartości wewnętrznych, co gwarantuje jednoczesność.
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;
}
... W klasie Vector, w metodzie add() służącej do dodawania elementów, widać słowo kluczowe synchronized. Oznacza to, że w Vector operacja wstawiania elementu jest wewnętrznie synchronizowana.
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;
}
... W klasie Hashtable, w metodzie contains() sprawdzającej istnienie identycznej wartości, można zaobserwować, że podobnie jak w klasie Vector, użyto słowa kluczowego synchronized.
Collections.synchronizedXXX
Przyjrzyjmy się klasie SynchronizedList, utworzonej za pomocą metody 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);}
}
... W klasie SynchronizedList, wszystkie metody korzystają ze słowa kluczowego synchronized. Jednak do synchronizacji użyto bloku synchronized, a mutexem jest obiekt. Ponieważ wszystkie metody współdzielą obiekt mutex, gdy jeden wątek wejdzie do bloku synchronized, wszystkie pozostałe metody zostaną zablokowane.
Problemy zsynchronizowanych kolekcji
W środowiskach wielowątkowych czasami konieczne jest użycie zsynchronizowanych kolekcji, ale generalnie zaleca się wykorzystanie innych mechanizmów synchronizacji. Istnieją dwa główne powody:
Połączenie wielu operacji w jedną operację
Zsynchronizowane klasy kolekcji zapewniają jednoczesność w środowiskach wielowątkowych. Jednak w przypadku, gdy konieczne jest połączenie wielu operacji w jedną operację, mogą pojawić się problemy. Użycie takich zsynchronizowanych kolekcji może prowadzić do błędnego działania.
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();
}
}
}
}); Po uruchomieniu powyższego kodu, jeśli wątek A wykona operację remove(0), a wątek B wykona operację clear() w tym samym momencie, wystąpi błąd. W związku z tym należy je połączyć w bloku synchronized, jak pokazano poniżej:
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);Spadek wydajności
Zdefiniowanie wszystkich metod, które chcą korzystać z obiektu współdzielonego, jako metod synchronized lub zdefiniowanie tego samego bloku synchronized wewnątrz metod może prowadzić do sytuacji, w której gdy jeden wątek uzyska zablokowanie, pozostałe wątki nie będą mogły używać żadnej ze zsynchronizowanych metod i będą znajdować się w stanie blokowania. Ta powtarzalna sytuacja może prowadzić do spadku wydajności.
Kolekcje współbieżne
Pakiet java.util.concurrent zawiera różne rodzaje kolekcji równoległych. W tym artykule omówione zostaną tylko niektóre z nich.
- CopyOnWriteArrayList
- Podklasa klasy List, która priorytetowo traktuje wydajność operacji odczytu i iteracji nad listą obiektów.
- ConcurrentMap
- Kolekcja równoległa, której interfejs definiuje operacje put-if-absent, replace, conditional remove, które dodają element tylko wtedy, gdy ten element nie istnieje.
- ConcurrentHashMap
- Podklasa ConcurrentMap, równoległa kolekcja, która zastępuje HashMap i zapewnia jednoczesność.
- ConcurrentLinkedQueue
- Kolejka FIFO, która zapewnia jednoczesność. Jeśli kolejka jest pusta, operacja pobierania elementu zwraca natychmiastowo wartość i przechodzi do wykonywania innych zadań.
- LinkedBlockingQueue
- Podobna do ConcurrentLinkedQueue. Różnica polega na tym, że jeśli kolejka jest pusta, operacja pobierania elementu z kolejki jest blokowana do momentu dodania nowego elementu, a jeśli kolejka ma określony rozmiar, dodanie elementu do kolejki jest blokowane do momentu zwolnienia miejsca w kolejce.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Są to bardziej rozwinięte wersje klas SortedMap i SortedSet, które zwiększają jednoczesność.
Zastąpienie istniejących klas kolekcji zsynchronizowanych kolekcjami równoległymi może znacznie zwiększyć wydajność bez dodatkowych ryzyk.
Porównajmy szczegółowo kolekcje zsynchronizowane z kolekcjami równoległymi.
CopyOnWriteArrayList
Istnieją dwa sposoby utworzenia zsynchronizowanej ArrayList:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() został dodany w wersji JDK 1.2. Ta kolekcja jest synchronizowana dla wszystkich operacji odczytu i zapisu, co czyni ją nieelastyczną w projektowaniu. Dlatego pojawiła się kolekcja CopyOnWriteArrayList, która ma na celu uzupełnienie tych niedociągnięć.
Operacje odczytu
W SynchronizedList, podczas operacji odczytu i zapisu, zablokowana jest sama instancja. Jednak CopyOnWriteArrayList podczas każdej operacji zapisu kopiuje elementy z oryginalnej tablicy do nowej tymczasowej tablicy, wykonuje operację zapisu na tej tymczasowej tablicy, a następnie aktualizuje oryginalną tablicę. Dzięki temu operacje odczytu nie są blokowane, co czyni ją wydajniejszą niż 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);
}
... Powyżej znajduje się metoda get(), która nie jest zsynchronizowana, więc nie jest blokowana.
Operacje zapisu
CopyOnWriteArrayList używa jawnego blokowania podczas wykonywania operacji zapisu. Oznacza to, że obie kolekcje są blokowane podczas tej operacji. Jednak CopyOnWriteArrayList wykonuje kosztowne kopiowanie tablicy, co może prowadzić do problemów z wydajnością, jeśli zostanie wykonanych wiele operacji zapisu.
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);
}
...
}
} Powyżej znajduje się metoda add(), która wykorzystuje blok synchronized do blokowania i kopiowania tablicy.
Iterator
W CopyOnWriteArrayList, iteracja jest wykonywana na podstawie danych kolekcji w momencie pobrania iteratora. Podczas iteracji dodawanie lub usuwanie danych z kolekcji odbywa się na kopii, a nie na oryginalnej kolekcji, co eliminuje problemy z jednoczesnym dostępem.
CopyOnWriteArraySet
Istnieją dwa sposoby utworzenia zsynchronizowanego Set:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Jak sama nazwa wskazuje, CopyOnWriteArraySet działa w zasadzie tak samo jak CopyOnWriteArrayList, z wyjątkiem cech struktury danych.
Operacje odczytu
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} Powyżej znajduje się metoda contains(), która wykorzystuje wewnętrznie zdefiniowaną CopyOnWriteArrayList i korzysta z jej metod.
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;W metodzie contains() CopyOnWriteArrayList widać, że nie jest ona blokowana.
Operacje zapisu
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} Metoda add() również korzysta z metod 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;
}W metodzie addIfAbsent() widać, że operacja zapisu jest blokowana i kopiowana jest tablica. Tak więc, podobnie jak w przypadku CopyOnWriteArrayList, w przypadku CopyOnWriteArraySet zaleca się unikanie częstych operacji zapisu.
ConcurrentHashMap
Istnieją dwa sposoby utworzenia zsynchronizowanej HashMap:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap, podobnie jak HashMap, jest mapą opartej na funkcji mieszającej. Zapewnia ona jednoczesność w sposób bardziej efektywny niż synchronizedMap.
W wersjach Javy wcześniejszych niż 8, użyto Segmentu dziedziczącego po ReentrantLock, aby podzielić mapę na segmenty i zastosować blokowanie w każdym segmencie.
W wersjach Javy od 8 wzwyż, używana jest metoda blokowania każdego wiadra tablicy niezależnie. W przypadku dodania nowego węzła do pustego wiadra, zamiast blokowania używany jest algorytm CAS, a w pozostałych przypadkach stosowane jest częściowe blokowanie (blok synchronized) względem pierwszego węzła w wiadrze, co minimalizuje konkurencję wątków i zapewnia jednoczesność.
Sprawdźmy, jak ConcurrentHashMap zapewnia jednoczesność, analizując kod metody putVal(), która dodaje nowy węzeł. Pamiętaj, że poniższy przykład kodu pochodzi z Javy 11.
Metoda putVal() można podzielić na dwa główne przypadki (łącznie cztery rozgałęzienia):
- W przypadku dodania węzła do pustego wiadra.
- W przypadku, gdy wiadro już zawiera węzeł.
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");
}
}
...
}
}
... Dodanie węzła do pustego wiadra
(1) Aby dodać nowy węzeł, pobiera się wartość wiadra (tabAt()) i sprawdza, czy jest puste.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) Uzyskuje się dostęp do zmiennej volatile w węźle, porównuje się ją z wartością bieżącą (null) i zapisuje nowy węzeł, jeśli wartości są takie same. W przeciwnym razie przechodzi się do pętli for. Jest to algorytm CAS.
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); Algorytm CAS rozwiązuje problemy atomowości i widoczności, zapewniając jednoczesność.
W przypadku, gdy wiadro już zawiera węzeł
(3) Jeśli wiadro już zawiera węzeł, używa się bloku synchronized, aby zapewnić dostęp tylko jednemu wątkowi. W tym przypadku, blokowane jest wiadro Node
(4) Wymienia się nowy węzeł.
(5) W przypadku kolizji funkcji mieszającej, nowy element jest dodawany do łańcucha oddzielnego.
(6) W przypadku kolizji funkcji mieszającej, nowy element jest dodawany do drzewa.
Odnośniki
Spodziewane pytania na rozmowie kwalifikacyjnej i odpowiedzi
Jakie są problemy z Vector, HashTable i Collections.SynchronziedXXX?
Klasy Vector, HashTable i SynchronziedXxx używają zsynchronizowanych metod lub bloków, wspólnie używając jednego obiektu blokującego. W związku z tym, gdy jeden wątek uzyska blokowanie kolekcji, pozostałe wątki nie będą mogły używać żadnej z metod i będą znajdować się w stanie blokowania. Może to prowadzić do spadku wydajności aplikacji.
Jaka jest różnica między SynchronizedList a CopyOnArrayList?
SynchronizedList blokuje całą instancję podczas operacji odczytu i zapisu. Natomiast CopyOnArrayList podczas operacji zapisu blokuje dany blok i kopiuje elementy z oryginalnej tablicy do nowej tymczasowej tablicy, wykonuje operację zapisu na tej tymczasowej tablicy, a następnie aktualizuje oryginalną tablicę. Dzięki temu operacje odczytu nie są blokowane, co czyni ją wydajniejszą niż SynchronizedList w przypadku operacji odczytu. Jednak operacja zapisu wiąże się z kosztownym kopiowaniem tablicy, co czyni ją mniej wydajną niż SynchronizedList w przypadku operacji zapisu.
W związku z tym, w przypadku częstszych operacji odczytu niż zapisu, bardziej efektywne jest użycie CopyOnArrayList.
Jaka jest różnica między SynchronizedMap a ConcurrentHashMap?
SynchronziedMap blokuje całą instancję podczas operacji odczytu i zapisu. Natomiast ConcurrentHashMap blokuje każde wiadro tablicy niezależnie. W przypadku dodania nowego węzła do pustego wiadra, zamiast blokowania używany jest algorytm CAS, a w pozostałych przypadkach stosowane jest częściowe blokowanie (blok synchronized) względem pierwszego węzła w wiadrze, co minimalizuje konkurencję wątków i zapewnia jednoczesność.
