Bộ sưu tập đồng bộ
Các bộ sưu tập được đồng bộ hóa thường bao gồm các lớp sau:
- Vector
- Hashtable
- Collections.synchronizedXXX
Tất cả các lớp này đều sử dụng từ khóa synchronized cho các phương thức được khai báo công khai để đảm bảo sự đồng bộ bằng cách kiểm soát việc chỉ một luồng có thể sử dụng giá trị bên trong.
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;
}
...
}
Hãy xem xét phương thức add() để thêm phần tử vào lớp Vector. Bạn có thể thấy từ khóa synchronized. Nói cách khác, việc chèn phần tử trong Vector được đảm bảo đồng bộ.
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();
}
}
Hãy xem xét phương thức contains() trong lớp Hashtable để kiểm tra xem có giá trị nào giống nhau hay không. Cũng giống như lớp Vector, từ khóa synchronized được sử dụng.
Collections.synchronizedXXX
Hãy xem xét lớp SynchronizedList được tạo ra bằng cách sử dụng phương thức Collections.synchronizedList().
```javascript
static class SynchronizedList extends SynchronizedCollection implements List {
}
Nhìn vào các phương thức của lớp SynchronizedList, bạn có thể thấy rằng từ khóa synchronized được sử dụng cho tất cả chúng. Tuy nhiên, nó sử dụng khối synchronized để thực hiện đồng bộ hóa thông qua mutex. Tất cả các phương thức đều chia sẻ đối tượng mutex, vì vậy khi một luồng đi vào khối synchronized, khối synchronized của các phương thức khác sẽ bị khóa.
Vấn đề của bộ sưu tập đồng bộ
Trong môi trường đa luồng, có những trường hợp bạn cần sử dụng các bộ sưu tập được đồng bộ hóa, nhưng tốt hơn nên sử dụng các phương thức đồng bộ hóa khác. Có hai lý do chính:
Kết hợp nhiều thao tác thành một thao tác duy nhất
Các lớp bộ sưu tập được đồng bộ hóa đảm bảo sự đồng bộ trong môi trường đa luồng. Tuy nhiên, có thể gặp vấn đề khi cần kết hợp nhiều thao tác để sử dụng chúng như một thao tác duy nhất. Việc sử dụng các bộ sưu tập được đồng bộ hóa này có thể không hoạt động chính xác.
```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() {
}
Nếu bạn chạy đoạn mã trên, khi Thread A thực hiện remove(0), Thread B thực hiện clear(), lỗi sẽ xảy ra. Vì vậy, bạn cần kết hợp chúng lại trong khối đồng bộ hóa như bên dưới.
```javascript
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);
}
Việc tạo tất cả các phương thức muốn sử dụng đối tượng chia sẻ thành các phương thức synchronized hoặc định nghĩa các khối synchronized giống nhau bên trong các phương thức sẽ khiến các luồng khác bị chặn khi một luồng nhận được khóa. Hiện tượng này sẽ khiến hiệu suất bị giảm.
Bộ sưu tập đồng thời
Gói java.util.concurrent cung cấp các loại bộ sưu tập song song sau. Bài viết này chỉ đề cập đến một phần trong số chúng.
- CopyOnWriteArrayList
- Là lớp con của lớp List và là bộ sưu tập song song ưu tiên hiệu năng cho các thao tác duyệt danh sách đối tượng.
- ConcurrentMap
- Là bộ sưu tập song song. Nếu bạn nhìn vào giao diện, nó định nghĩa các thao tác put-if-absent, replace, remove có điều kiện, v.v., những thao tác này chỉ thêm các mục nếu chúng không tồn tại trong bộ sưu tập.
- ConcurrentHashMap
- Là lớp con của ConcurrentMap, đây là bộ sưu tập song song thay thế HashMap và đảm bảo
sự song song.
- ConcurrentLinkedQueue
- Là một hàng đợi theo phương thức FIFO, nó là một bộ sưu tập song song. Nếu không có phần tử nào để lấy ra khỏi hàng đợi, nó sẽ trả về ngay lập tức và tiếp tục thực hiện các công việc khác.
- LinkedBlockingQueue
- Tương tự như ConcurrentLinkedQueue. Tuy nhiên, nếu hàng đợi trống, thao tác lấy phần tử ra khỏi hàng đợi sẽ chờ cho đến khi có phần tử mới được thêm vào. Ngược lại, nếu hàng đợi có kích thước cố định, thao tác thêm phần tử mới vào hàng đợi sẽ chờ cho đến khi có chỗ trống trong hàng đợi.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Đây là phiên bản được phát triển để tăng cường sự song song cho các lớp SortedMap và SortedSet
tương ứng.
Chỉ cần thay thế các lớp bộ sưu tập được đồng bộ hóa hiện có bằng các bộ sưu tập song song, bạn có thể tăng hiệu năng đáng kể mà không gặp rủi ro nào.
Hãy cùng xem xét kỹ hơn về các bộ sưu tập được đồng bộ hóa so với các bộ sưu tập song song.
CopyOnWriteArrayList
Có hai cách để tạo ArrayList được đồng bộ hóa:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() được thêm vào trong phiên bản JDK 1.2. Bộ sưu tập này được đồng bộ hóa cho tất cả các thao tác đọc và ghi, vì vậy nó có thể được coi là thiết kế không linh hoạt. Do đó, CopyOnWriteArrayList đã được phát triển để khắc phục điều này.
SynchronizedList khóa chính bản thân nó khi thực hiện các thao tác đọc và ghi. Tuy nhiên, CopyOnWriteArrayList tạo một mảng tạm mới bằng cách sao chép các phần tử trong mảng gốc cho mỗi thao tác ghi, thực hiện thao tác ghi vào mảng tạm và sau đó cập nhật mảng gốc. Nhờ đó, các thao tác đọc không bị khóa, vì vậy hiệu năng tốt hơn SynchronizedList.
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
Phương thức get() ở trên không có synchronized, vì vậy nó không bị khóa.
CopyOnWriteArrayList sử dụng khóa rõ ràng khi thực hiện thao tác ghi. Cuối cùng, cả hai loại bộ sưu tập đều bị khóa trong thao tác này. Tuy nhiên, vì CopyOnWriteArrayList thực hiện việc sao chép mảng tốn kém hơn, nếu có nhiều thao tác ghi, hiệu suất có thể bị ảnh hưởng.
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
Phương thức add() ở trên sử dụng khối synchronized để khóa và thực hiện thao tác sao chép mảng.
Trong CopyOnWriteArrayList, dữ liệu bộ sưu tập tại thời điểm lấy iterator được sử dụng để lặp lại. Trong khi lặp, các thay đổi được thêm vào hoặc xóa khỏi bộ sưu tập sẽ được phản ánh trong bản sao không liên quan đến vòng lặp, do đó không có vấn đề nào về việc sử dụng đồng thời.
CopyOnWriteArraySet
Có hai cách để tạo Set được đồng bộ hóa:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Như tên của phương thức cho thấy, ngoại trừ các đặc điểm của cấu trúc dữ liệu, cách thức hoạt động của CopyOnWriteArraySet gần giống với CopyOnWriteArrayList.
```javascript
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
}
Phương thức contains() ở trên cho thấy rằng CopyOnWriteArraySet định nghĩa CopyOnWriteArrayList bên trong và sử dụng các phương thức của 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);
}
}
Nhìn vào phương thức contains() của CopyOnWriteArrayList, bạn có thể thấy rằng nó không bị khóa.
```javascript
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
}
Phương thức add() cũng sử dụng phương thức của 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;
}
}
Nhìn vào phương thức addIfAbsent(), bạn có thể thấy rằng nó khóa khi thực hiện thao tác ghi và sao chép mảng. Do đó, giống như CopyOnWriteArrayList, CopyOnWriteArraySet cũng không nên thực hiện quá nhiều thao tác ghi.
ConcurrentHashMap
Có hai cách để tạo HashMap được đồng bộ hóa:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap là một Map dựa trên Hash giống như HashMap. So với synchronizedMap, nó đảm bảo sự đồng bộ hiệu quả hơn.
Trước Java 8, nó sử dụng Segment kế thừa từ ReentrantLock để chia các vùng và khóa theo vùng.
Từ Java 8 trở đi, nó sử dụng phương pháp khóa độc lập từng bucket trong bảng. Khi chèn một nút vào một bucket trống, thay vì khóa, nó sử dụng thuật toán CAS. Các thay đổi khác sẽ khóa một phần (khối synchronized) bắt đầu từ nút đầu tiên của từng bucket để giảm thiểu tranh chấp luồng và đảm bảo sự đồng bộ.
Hãy xem xét đoạn mã của phương thức putVal() để chèn một nút mới vào ConcurrentHashMap để xem nó đảm bảo sự đồng bộ như thế nào. Xin lưu ý rằng mã ví dụ này dựa trên Java 11.
Phương thức putVal() có thể được chia thành hai trường hợp (tổng cộng bốn nhánh):
- Khi chèn một nút vào một bucket hash trống
- Khi một nút đã tồn tại trong 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");
}
}
...
}
}
...
}
Khi chèn một nút vào một bucket hash trống
(1) Để chèn một nút mới, nó sẽ lấy giá trị của bucket đó (tabAt()) và kiểm tra xem nó có trống hay không.
```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) Nó truy cập biến volatile trong nút và so sánh với giá trị hiện tại (null). Nếu giống nhau, nó sẽ lưu trữ nút mới. Nếu không giống nhau, nó sẽ quay lại vòng lặp for. Phương pháp này là thuật toán 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);
}
Thuật toán CAS được sử dụng để giải quyết các vấn đề về tính nguyên tử và khả năng hiển thị, đảm bảo sự
đồng bộ.
Khi một nút đã tồn tại trong bucket hash
(3) Nếu nút đã tồn tại, nó sẽ sử dụng khối synchronized để kiểm soát việc chỉ một luồng có thể truy cập. Lúc này, nó sẽ khóa bucket hash không trống có kiểu Node, vì vậy các luồng truy cập cùng một bucket sẽ bị chặn.
(4) Thay thế bằng một nút mới.
(5) Nếu xảy ra xung đột hash, nó sẽ được thêm vào Separate Chaing.
(6) Nếu xảy ra xung đột hash, nó sẽ được thêm vào cây.
Tham khảo
Câu hỏi phỏng vấn dự kiến và câu trả lời
Vấn đề của Vector, HashTable, Collections.SynchronziedXXX là gì?
Các lớp Vector, HashTable, SynchronziedXxx sử dụng các phương thức hoặc khối synchronized và chia sẻ một đối tượng khóa duy nhất. Do đó, khi một luồng nhận được khóa cho bộ sưu tập, các luồng khác sẽ không thể sử dụng bất kỳ phương thức nào và sẽ bị chặn. Điều này có thể dẫn đến giảm hiệu năng của ứng dụng.
Sự khác biệt giữa SynchronizedList và CopyOnArrayList là gì?
SynchronizedList khóa chính bản thân nó khi thực hiện các thao tác đọc và ghi. Tuy nhiên, CopyOnArrayList khóa khối đó khi thực hiện thao tác ghi, tạo một mảng tạm mới bằng cách sao chép các phần tử trong mảng gốc, thực hiện thao tác ghi vào mảng tạm và sau đó cập nhật mảng gốc. Nhờ đó, các thao tác đọc không bị khóa, vì vậy hiệu năng đọc tốt hơn SynchronizedList. Tuy nhiên, thao tác ghi sẽ thực hiện việc sao chép mảng tốn kém hơn, vì vậy hiệu năng ghi kém hơn SynchronizedList.
Do đó, nếu thao tác đọc nhiều hơn thao tác sửa đổi, việc sử dụng CopyOnArrayList sẽ hiệu quả hơn.
Sự khác biệt giữa SynchronizedMap và ConcurrentHashMap là gì?
SynchronziedMap khóa chính bản thân nó khi thực hiện các thao tác đọc và ghi. Tuy nhiên, ConcurrentHashMap sử dụng phương pháp khóa độc lập từng bucket trong bảng. Nếu chèn một nút vào một bucket trống, nó sẽ sử dụng thuật toán CAS thay vì khóa. Các thay đổi khác sẽ khóa một phần (khối synchronized) bắt đầu từ nút đầu tiên của từng bucket để giảm thiểu tranh chấp luồng và đảm bảo sự đồng bộ.