[Java] Synchronized Collection vs Concurrent Collection

Kumpulan Tersinkronisasi

Kumpulan tersinkronisasi biasanya berisi kelas-kelas seperti ini:

Vector
Hashtable
Collections.synchronizedXXX

Semua kelas ini menjamin sinkronisasi dengan menggunakan kata kunci synchronized pada metode yang dideklarasikan secara publik, sehingga hanya satu thread yang dapat menggunakan nilai internalnya.

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

Pada kelas Vector, perhatikan metode add() yang menambahkan elemen. Kata kunci synchronized terlihat. Ini berarti bahwa insersi elemen pada Vector dijamin secara sinkron.

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(); }

}

Pada kelas Hashtable, metode contains() yang memeriksa keberadaan nilai yang sama, juga menggunakan kata kunci synchronized seperti kelas Vector.

Collections.synchronizedXXX

Perhatikan kelas SynchronizedList yang dibuat menggunakan metode Collections.synchronizedList().

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

}

Metode-metode di kelas SynchronizedList semuanya menggunakan kata kunci synchronized. Namun, mereka menggunakan blok synchronized untuk mencapai sinkronisasi melalui mutex. Semua metode berbagi objek mutex, sehingga ketika satu thread memasuki blok synchronized, semua blok synchronized pada metode lain terkunci.

Kelemahan Kumpulan Tersinkronisasi

Dalam lingkungan multithreading, Anda mungkin perlu menggunakan koleksi tersinkronisasi, tetapi idealnya Anda harus menggunakan mekanisme sinkronisasi lain. Ada dua alasan utama untuk ini.

Menggunakan Beberapa Operasi sebagai Satu Operasi Tunggal

Kelas koleksi tersinkronisasi menjamin sinkronisasi dalam lingkungan multithreading. Namun, ada masalah ketika Anda perlu menggabungkan beberapa operasi untuk digunakan sebagai satu operasi tunggal. Penggunaan koleksi tersinkronisasi ini mungkin tidak berfungsi dengan baik.

```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() {

}

Jika Anda menjalankan kode di atas, akan terjadi kesalahan jika Thread A menjalankan remove(0) pada saat yang sama ketika Thread B menjalankan clear(). Oleh karena itu, Anda perlu membungkusnya dengan blok sinkron seperti di bawah ini.

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

Penurunan Performa

Jika Anda membuat semua metode yang ingin menggunakan objek bersama menjadi metode synchronized, atau menentukan blok synchronized yang sama di dalam metode, maka ketika satu thread memperoleh kunci, thread lain tidak akan dapat menggunakan semua metode synchronized dan akan terkunci. Fenomena berulang ini dapat menyebabkan penurunan kinerja.

Kumpulan Bersamaan

Berikut adalah jenis-jenis koleksi paralel yang disediakan oleh paket java.util.concurrent. Saya hanya akan membahas beberapa di antaranya dalam artikel ini.

CopyOnWriteArrayList
- Ini adalah subkelas dari kelas List dan merupakan koleksi paralel yang memprioritaskan kinerja operasi pencarian sambil mengulangi daftar objek.
ConcurrentMap
- Ini adalah koleksi paralel, dan jika Anda melihat antarmuka, put-if-absent, replace, dan operasi penghapusan bersyarat lainnya didefinisikan di sini. Ini mengizinkan menambahkan item baru hanya jika item yang baru ditambahkan tidak ada sebelumnya.
ConcurrentHashMap
- Ini adalah subkelas ConcurrentMap, yang menggantikan HashMap dan merupakan koleksi paralel yang menyediakan paralelisme.
ConcurrentLinkedQueue
- Ini adalah Queue FIFO (First In First Out) dan merupakan koleksi paralel yang menyediakan paralelisme. Jika tidak ada elemen yang akan diambil dari antrian, antrian tersebut akan langsung dikembalikan dan akan melanjutkan ke tugas lain.
LinkedBlockingQueue
- Ini mirip dengan ConcurrentLinkedQueue. Namun, jika antrian kosong, operasi mengambil elemen dari antrian akan menunggu hingga elemen baru ditambahkan, dan sebaliknya, jika antrian memiliki ukuran yang ditentukan, operasi menambahkan elemen baru ke antrian akan menunggu hingga ada ruang kosong di antrian.
ConcurrentSkipListMap, ConcurrentSkipListSet
- Ini adalah bentuk SortedMap dan SortedSet yang dikembangkan untuk meningkatkan paralelisme.

Dengan hanya mengganti kelas koleksi tersinkronisasi lama dengan koleksi paralel, Anda dapat meningkatkan kinerja secara keseluruhan tanpa risiko yang berarti.

Mari kita bahas lebih dalam tentang koleksi tersinkronisasi dan bandingkan dengan koleksi paralel.

CopyOnWriteArrayList

Ada dua cara untuk membuat ArrayList tersinkronisasi:

Collections.synchronizedList()
CopyOnWriteArrayList

Collections.synchronizedList() ditambahkan pada versi JDK 1.2. Koleksi ini disinkronkan untuk semua operasi baca dan tulis, yang membuatnya menjadi desain yang tidak fleksibel. Oleh karena itu, CopyOnWriteArrayList muncul sebagai solusi.

Operasi Baca

SynchronizedList mengunci sendiri saat operasi baca dan tulis. Namun, CopyOnWriteArrayList membuat array sementara baru dengan menyalin elemen dari array asli setiap kali operasi tulis dilakukan, melakukan operasi tulis pada array sementara ini, dan kemudian memperbarui array asli. Karena alasan ini, operasi baca tidak terkunci, sehingga lebih cepat dibandingkan dengan SynchronizedList.

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

}

Kode di atas adalah metode get(), dan tidak ada synchronized, sehingga tidak terkunci.

Operasi Tulis

CopyOnWriteArrayList menggunakan kunci eksplisit saat melakukan operasi tulis. Pada akhirnya, kedua jenis koleksi terkunci pada operasi ini. Namun, CopyOnWriteArrayList menggunakan operasi salinan array yang relatif mahal, sehingga kinerja dapat terpengaruh jika operasi tulis sering dilakukan.

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

}

Kode di atas adalah metode add(), dan ia menggunakan blok synchronized untuk mengunci dan melakukan salinan array.

Iterator

Dalam CopyOnWriteArrayList, saat iterator diekstraksi, data koleksi saat itu digunakan untuk iterasi, dan jika data ditambahkan atau dihapus dari koleksi selama iterasi, perubahannya akan tercermin dalam salinan yang dibuat terlepas dari loop iterasi. Karena itu, tidak ada masalah dengan penggunaan bersamaan.

CopyOnWriteArraySet

Ada dua cara untuk membuat Set tersinkronisasi:

Collections.synchronizedSet()
CopyOnWriteArraySet

Seperti namanya, CopyOnWriteArraySet memiliki mekanisme kerja yang hampir sama dengan CopyOnWriteArrayList, kecuali karakteristik struktur datanya.

Operasi Baca

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

}

Kode di atas adalah metode contains(), dan Anda dapat melihat bahwa CopyOnWriteArraySet mendefinisikan CopyOnWriteArrayList secara internal dan menggunakan metodenya.

```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); }

}

Jika Anda melihat metode contains() dari CopyOnWriteArrayList, Anda dapat melihat bahwa itu tidak terkunci.

Operasi Tulis

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

}

Metode add() juga menggunakan metode dari 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; } }

Jika Anda melihat metode addIfAbsent(), Anda dapat melihat bahwa operasi tulis terkunci dan salinan array dilakukan. Oleh karena itu, seperti CopyOnWriteArrayList, CopyOnWriteArraySet juga lebih baik untuk menghindari banyak operasi tulis.

ConcurrentHashMap

Ada dua cara untuk membuat HashMap tersinkronisasi:

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

ConcurrentHashMap adalah Map yang didasarkan pada hash seperti HashMap. Ini menjamin sinkronisasi dengan cara yang lebih efisien daripada synchronizedMap.

Sebelum Java 8, metode ini menggunakan Segment yang mewarisi ReentrantLock, dan mengunci setiap area secara terpisah.

Mulai Java 8, ia mengunci setiap bucket tabel secara terpisah. Saat menyisipkan simpul ke dalam bucket kosong, ia menggunakan algoritma CAS bukan kunci, dan perubahan lainnya memperoleh kunci sebagian (blok synchronized) berdasarkan simpul pertama dari setiap bucket, sehingga meminimalkan kompetisi thread dan menjamin sinkronisasi.

Mari kita lihat kode metode putVal() yang menyisipkan simpul baru ke ConcurrentHashMap dan melihat bagaimana sinkronisasi dijamin. Sebagai catatan, kode contoh ini menggunakan Java 11.

Metode putVal() dapat dibagi menjadi dua kasus (total empat cabang):

Menyisipkan simpul ke dalam bucket hash kosong
Jika sudah ada simpul di bucket 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"); } } ... } } ... }

Menyisipkan simpul ke dalam bucket hash kosong

(1) Untuk menyisipkan simpul baru, ia memperoleh nilai bucket yang bersangkutan (tabAt()) dan memeriksa apakah kosong.

```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) Ia mengakses variabel volatile yang ada di dalam simpul dan menyimpan simpul baru jika nilainya sama dengan nilai lama (null). Jika tidak sama, ia akan kembali ke loop for. Metode ini disebut algoritma 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); }

Algoritma CAS digunakan untuk menyelesaikan masalah atomicity dan visibility, sehingga menjamin sinkronisasi.

Jika sudah ada simpul di bucket hash

(3) Jika sudah ada simpul, ia menggunakan blok synchronized untuk mengontrol akses agar hanya satu thread yang dapat mengaksesnya. Dalam hal ini, ia mengunci bucket hash Node<K, V> yang tidak kosong, sehingga thread yang mengakses bucket yang sama akan terkunci.

(4) Ganti dengan simpul baru.

(5) Jika terjadi tabrakan hash, tambahkan ke Separate Chaing.

(6) Jika terjadi tabrakan hash, tambahkan ke pohon.

Referensi

Pertanyaan Wawancara yang Diharapkan dan Jawabannya

Apa kelemahan dari Vector, HashTable, Collections.SynchronziedXXX?

Kelas Vector, HashTable, dan SynchronziedXxx menggunakan metode synchronized atau blok, dan mereka berbagi satu objek kunci. Oleh karena itu, jika satu thread memperoleh kunci untuk koleksi, thread lain tidak akan dapat menggunakan metode apa pun dan akan terkunci. Ini dapat menyebabkan penurunan kinerja aplikasi.

Apa perbedaan antara SynchronizedList dan CopyOnArrayList?

SynchronizedList mengunci dirinya sendiri selama operasi baca dan tulis. Namun, CopyOnArrayList mengunci blok yang bersangkutan selama operasi tulis, membuat array sementara baru dengan menyalin elemen dari array asli, melakukan operasi tulis pada array sementara ini, dan kemudian memperbarui array asli. Karena alasan ini, operasi baca tidak terkunci, sehingga lebih cepat dibandingkan dengan SynchronizedList. Namun, operasi tulis menggunakan operasi salinan array yang relatif mahal, sehingga lebih lambat dibandingkan dengan SynchronizedList.

Oleh karena itu, jika operasi baca lebih sering dilakukan daripada operasi tulis, lebih efektif menggunakan CopyOnArrayList.

Apa perbedaan antara SynchronizedMap dan ConcurrentHashMap?

SynchronziedMap mengunci dirinya sendiri selama operasi baca dan tulis. Namun, ConcurrentHashMap mengunci setiap bucket tabel secara terpisah. Jika menyisipkan simpul ke dalam bucket kosong, ia menggunakan algoritma CAS bukan kunci, dan perubahan lainnya memperoleh kunci sebagian (blok synchronized) berdasarkan simpul pertama dari setiap bucket, sehingga meminimalkan kompetisi thread dan menjamin sinkronisasi.