Синхронизированные коллекции
Синхронизированные коллекции - это, как правило, следующие классы:
- Vector
- Hashtable
- Collections.synchronizedXXX
Все эти классы используют ключевое слово synchronized для публично объявленных методов, чтобы гарантировать синхронность, контролируя доступ к внутренним значениям только для одного потока.
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;
}
...
}
Если посмотреть на метод add(), который добавляет элементы в класс Vector, то можно увидеть ключевое слово synchronized. Это означает, что вставка элементов в Vector по умолчанию синхронизирована.
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();
}
}
Если посмотреть на метод contains() в классе Hashtable, который проверяет наличие одинакового значения, то можно увидеть, что он использует ключевое слово synchronized, как и в классе Vector.
Collections.synchronizedXXX
Рассмотрим класс SynchronizedList, который создается с помощью метода Collections.synchronizedList().
```javascript
static class SynchronizedList extends SynchronizedCollection implements List {
}
Если посмотреть на методы класса SynchronizedList, то можно увидеть, что все они используют ключевое слово synchronized. Однако в этом случае синхронизация реализована с помощью мьютекса через блок synchronized. Все методы делят один объект мьютекса, поэтому когда один поток входит в блок synchronized, блокируется доступ к другим методам.
Недостатки синхронизированных коллекций
В многопоточной среде может возникнуть необходимость использовать синхронизированные коллекции, однако рекомендуется использовать другие методы синхронизации, по возможности. Есть две основные причины.
Объединение нескольких операций в одну
Синхронизированные классы коллекций обеспечивают синхронность в многопоточной среде. Однако если необходимо объединять несколько операций в одну, то могут возникать проблемы. Использование синхронизированных коллекций может привести к неправильной работе.
```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() {
}
Если запустить этот код, то когда поток A выполнит операцию remove(0), поток B может выполнить операцию clear(), что приведет к ошибке. Поэтому необходимо обернуть эти действия в блок синхронизации:
```javascript
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);
}
Снижение производительности
Если все методы, которые должны получить доступ к общему объекту, сделать synchronized, или определить один и тот же блок synchronized внутри методов, то когда один поток получит блокировку, другие потоки не смогут использовать синхронизированные методы и будут заблокированы. Повторение этого процесса может привести к снижению производительности.
Concurrent Collections
Пакет java.util.concurrent предоставляет различные типы параллельных коллекций. В этой статье мы рассмотрим только некоторые из них.
- CopyOnWriteArrayList
- Подкласс класса List, в котором приоритет отдается производительности операций чтения списка элементов.
- ConcurrentMap
- Параллельная коллекция, в которой, как видно из интерфейса, определены операции put-if-absent, replace, conditional remove, которые добавляют элементы только в том случае, если их нет в коллекции.
- ConcurrentHashMap
- Подкласс ConcurrentMap, параллельная коллекция, которая заменяет HashMap и обеспечивает
параллельность.
- ConcurrentLinkedQueue
- Очередь FIFO, параллельная коллекция, обеспечивающая параллельность. Если в очереди нет элементов, то она сразу же возвращает значение и переходит к выполнению других задач.
- LinkedBlockingQueue
- Похожа на ConcurrentLinkedQueue, однако, если очередь пуста, то операция извлечения элемента из очереди будет ждать, пока не будет добавлен новый элемент. И наоборот, если очередь имеет фиксированный размер, то операция добавления нового элемента в очередь будет ждать, пока не появится свободное место в очереди.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Это продвинутые версии классов SortedMap и SortedSet, оптимизированные для повышения
параллельности.
Простая замена синхронизированных коллекций на параллельные может значительно повысить производительность без каких-либо существенных рисков.
Давайте подробнее рассмотрим параллельные коллекции в сравнении с синхронизированными.
CopyOnWriteArrayList
Есть два способа создать синхронизированный ArrayList:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() был добавлен в JDK версии 1.2. Эта коллекция синхронизирована для всех операций чтения и записи, поэтому ее дизайн можно считать негибким. Поэтому появилась CopyOnWriteArrayList.
SynchronizedList блокирует доступ к самому объекту при чтении и записи. Однако CopyOnWriteArrayList при любой операции записи создает новый временный массив, копируя в него элементы из исходного массива, выполняет операции записи в этот временный массив и затем обновляет исходный массив. Благодаря этому операции чтения не блокируются, поэтому CopyOnWriteArrayList работает быстрее, чем SynchronizedList.
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
В приведенном выше коде метода get() нет synchronized, поэтому блокировки нет.
CopyOnWriteArrayList использует явные блокировки для выполнения операций записи. В итоге, оба типа коллекций блокируются во время этой операции. Однако CopyOnWriteArrayList выполняет трудоемкую операцию копирования массива, поэтому при большом количестве операций записи может возникнуть проблема с производительностью.
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
В приведенном выше коде метода add() используется блок synchronized для блокировки и копирования массива.
В CopyOnWriteArrayList итератор работает с копией данных коллекции, созданной в момент получения итератора. Поэтому изменения, внесенные в коллекцию после получения итератора (добавление или удаление элементов), не влияют на итератор.
CopyOnWriteArraySet
Есть два способа создать синхронизированный Set:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Как видно из названия метода, работа CopyOnWriteArraySet аналогична CopyOnWriteArrayList, за исключением особенностей структуры данных.
```javascript
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
}
В приведенном выше коде метода contains() видно, что CopyOnWriteArraySet использует методы 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);
}
}
Если посмотреть на метод contains() в CopyOnWriteArrayList, то можно увидеть, что блокировки нет.
```javascript
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
}
Метод add() также использует методы 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;
}
}
Если посмотреть на метод addIfAbsent(), то видно, что при операции записи происходит блокировка и копирование массива. Поэтому, как и в случае с CopyOnWriteArraySet, лучше избегать большого количества операций записи.
ConcurrentHashMap
Есть два способа создать синхронизированный HashMap:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap - это Map на основе хэша, как и HashMap. Он обеспечивает синхронность более эффективным способом, чем synchronizedMap.
До Java 8 в нем использовался Segment, который наследовал ReentrantLock, для разделения областей и блокировки в каждой из них.
Начиная с Java 8, используется метод блокировки каждого бакет таблицы независимо друг от друга. При вставке узла в пустой бакет используется алгоритм CAS, а при других изменениях блокировка накладывается на первый узел в бакете (с помощью synchronized block) для минимизации конфликтов потоков и обеспечения синхронности.
Рассмотрим код метода putVal(), который вставляет новый узел в ConcurrentHashMap, чтобы понять, как обеспечивается синхронность. Обратите внимание, что приведенный ниже код относится к Java 11.
Метод putVal() можно разделить на два случая (всего четыре разветвления):
- Вставка узла в пустой хэш-бакет
- Хэш-бакет уже содержит узлы
```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");
}
}
...
}
}
...
}
Вставка узла в пустой хэш-бакет
(1) Для вставки нового узла, проверяется значение соответствующего бакета (tabAt()), чтобы убедиться,
что он пустой.
```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) Получается доступ к volatile-переменной, которая хранится в узле, сравнивается с существующим значением (null), и если значения совпадают, то сохраняется новый узел. В противном случае выполняется возврат к циклу for. Этот подход реализует алгоритм 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);
}
Алгоритм CAS решает проблему атомарности и видимости, обеспечивая синхронность.
Хэш-бакет уже содержит узлы
(3) Если узел уже существует, то используется блок synchronized, чтобы гарантировать, что доступ к нему имеет только один поток. В этом случае, блокируется доступ к непустому хэш-бакету типа Node, поэтому потоки, пытающиеся получить доступ к тому же бакету, переходят в состояние блокировки.
(4) Заменяется новый узел.
(5) Если возникает коллизия хэшей, то новый узел добавляется в список Separate Chaing.
(6) Если возникает коллизия хэшей, то новый узел добавляется в дерево.
Ссылки
Ожидаемые вопросы и ответы на собеседовании
В чем недостатки Vector, HashTable, Collections.SynchronizedXXX?
Классы Vector, HashTable, SynchronizedXxx используют synchronized-методы или блоки и делят один объект блокировки. Поэтому, когда один поток получает блокировку, другие потоки не могут использовать все методы и находятся в состоянии блокировки. Это может привести к снижению производительности приложения.
В чем разница между SynchronizedList и CopyOnArrayList?
SynchronizedList блокирует доступ к самому объекту при чтении и записи. Однако CopyOnArrayList при операции записи блокирует этот блок и создает новый временный массив, копируя в него элементы из исходного массива, выполняет операции записи в этот временный массив и затем обновляет исходный массив. Благодаря этому операции чтения не блокируются, поэтому CopyOnArrayList работает быстрее, чем SynchronizedList. Однако операция записи выполняет трудоемкую операцию копирования массива, поэтому CopyOnArrayList медленнее, чем SynchronizedList при записи.
Поэтому, если операций чтения больше, чем операций записи, то лучше использовать CopyOnArrayList.
В чем разница между SynchronizedMap и ConcurrentHashMap?
SynchronziedMap блокирует доступ к самому объекту при чтении и записи. Однако ConcurrentHashMap использует метод блокировки каждого бакет таблицы независимо друг от друга. Если в пустой бакет вставляется узел, то вместо блокировки используется алгоритм CAS, а при других изменениях блокировка накладывается только на тот бакет, к которому осуществляется доступ. Это минимизирует конфликты потоков и обеспечивает синхронность.