同期化されたコレクション
同期化されたコレクションは、主に以下のクラスがあります。
- Vector
- Hashtable
- Collections.synchronizedXXX
これらのクラスはすべて、publicに宣言されたメソッドにsynchronizedキーワードを使用することで、内部の値を 1つのスレッドだけが使用できるように制御し、同時性を保証しています。
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;
}
...
}
Vectorクラスの要素を追加するadd()メソッドを見てみると、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();
}
}
Hashtableクラスで同じvalueが存在するかどうかを確認するcontains()メソッドを見てみると、Vectorクラスと 同様にsynchronizedキーワードが使用されていることが確認できます。
Collections.synchronizedXXX
Collections.synchronizedList()メソッドを使用して作成されるSynchronizedListクラスを見てみましょう。
```javascript
static class SynchronizedList extends SynchronizedCollection implements List {
}
SynchronizedListクラスのメソッドを見てみると、すべてsynchronizedキーワードが使用されていることがわかります。ただし、 synchronizedブロックを使用して、mutexを介して同期を実装しています。すべてのメソッドはmutexオブジェクトを共有しているため、 1つのスレッドがsynchronizedブロックに入った瞬間、他のメソッドのsynchronizedブロックがすべてロックされます。
同期化されたコレクションの問題点
マルチスレッド環境で同期化されたコレクションを使用しなければならない場合もありますが、できる限り別の同期方法を使用することをお勧めします。理由は 大きく2つあります。
同期化されたコレクションクラスは、マルチスレッド環境で同時性を保証します。しかし、複数の操作をまとめて1つの単一操作として 活用する必要がある場合、問題が発生します。このような同期化されたコレクションを使用しても、正しく動作しない場合があります。
```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() {
}
上記のコードを実行すると、Thread Aがremove(0)を実行した瞬間にThread Bがclear()を実行すると、エラーが発生します。 そのため、以下のように同期ブロックで囲む必要があります。
```javascript
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);
}
共有オブジェクトを使用しようとするすべてのメソッドをsynchronizedメソッドにしたり、メソッド内部に同じ synchronizedブロックを定義すると、1つのスレッドがロックを取得した瞬間、他のスレッドはすべての同期メソッドを 使用できなくなり、ブロッキング状態になります。このような繰り返しの現象は、パフォーマンスの低下につながる可能性があります。
並行コレクション
java.util.concurrentパッケージで提供されている並行コレクションの種類は次のとおりです。このうち、今回は一部だけを扱います。
- CopyOnWriteArrayList
- Listクラスのサブクラスであり、オブジェクトリストを反復処理して検索する操作のパフォーマンスを最優先とした 並行コレクションです。
- ConcurrentMap
- 並行コレクションであり、インターフェースを見ると、追加しようとするアイテムが既存にない場合にのみ、新しく追加する put-if-absent、replace、conditional removeなどの操作が定義されています。
- ConcurrentHashMap
- ConcurrentMapのサブクラスであり、HashMapを置き換えて並列性を確保した並行コレクションです。
- ConcurrentLinkedQueue
- FIFO方式のQueueであり、並列性を確保した並行コレクションです。キューから取り出す要素がない場合は、すぐに リターンし、他の作業を実行します。
- LinkedBlockingQueue
- ConcurrentLinkedQueueに似ています。ただし、キューが空の場合、キューからアイテムを取り出す操作は、 新しいアイテムが追加されるまで待機し、逆にキューにサイズが指定されている場合、キューが指定されたサイズまで いっぱいになっている場合、キューに新しいアイテムを追加する操作は、キューに空のスペースが空くまで 待機するという違いがあります。
- ConcurrentSkipListMap、ConcurrentSkipListSet
- それぞれSortedMapとSortedSetクラスの並列性を高めるために進化した形です。
従来使用していた同期化されたコレクションクラスを並行コレクションに置き換えるだけで、特別なリスク要因なく、全体的な パフォーマンスを大幅に向上させることができます。
並行コレクションと対照的な同期化されたコレクションを比較しながら、詳しく見ていきましょう。
CopyOnWriteArrayList
同期化されたArrayListを作成する方法は、以下の2つがあります。
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList()は、JDK 1.2バージョンで追加されました。このコレクションは、すべての読み取りと書き込み操作に対して 同期化されているため、柔軟性に欠ける設計と言えるでしょう。そこで、これを補完するCopyOnWriteArrayListが登場しました。
SynchronizedListは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、 CopyOnWriteArrayListは、すべての書き込み操作時に、元の配列にある要素をコピーして新しい一時的な配列を作成し、 この一時的な配列に書き込み操作を実行した後、元の配列を更新します。これにより、読み取り操作はロックがかからないため、 SynchronizedListよりもパフォーマンスが向上します。
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
上記はget()メソッドですが、synchronizedがないため、ロックがかかりません。
CopyOnWriteArrayListは、書き込み操作を実行する際に、明示的なロックを使用します。結局のところ、2種類の コレクションはどちらもこの操作でロックがかかります。この時、CopyOnWriteArrayListは、比較的コストの高い 配列のコピー作業を行うため、書き込み作業が頻繁に行われると、パフォーマンスの問題が発生する可能性があります。
```javascript
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
}
上記はadd()メソッドですが、synchronizedブロックによってロックをかけ、配列のコピー作業を実行しています。
CopyOnWriteArrayListでiteratorを取り出す時点のコレクションデータに基づいて反復処理し、反復処理中に コレクションにデータが追加または削除された場合でも、反復処理と無関係なコピーを対象に反映されるため、同時使用に問題はありません。
CopyOnWriteArraySet
同期化されたSetを作成する方法は、以下の2つがあります。
- Collections.synchronizedSet()
- CopyOnWriteArraySet
メソッドの名前を見ればわかるように、CopyOnWriteArrayListと動作方法は、データ構造の特徴を除けばほぼ同じです。
```javascript
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
}
上記はcontains()メソッドですが、CopyOnWriteArraySetは内部的にCopyOnWriteArrayListを 定義し、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);
}
}
CopyOnWriteArrayListのcontains()メソッドを見てみると、ロックがかかっていないことがわかります。
```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もCopyOnWriteArrayListと同様に、書き込み作業はあまり行わない方が良いでしょう。
ConcurrentHashMap
同期化されたHashMapを作成する方法は、以下の2つがあります。
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMapは、HashMapと同じように、HashをベースにしたMapです。synchronizedMapに 比べて、より効率的な方法で同時性を保証します。
Java 8以前は、ReentrantLockを継承したSegmentを使用して、領域を区切ることで、領域ごとにロックをかける 方法でした。
Java 8以降は、各テーブルバケットを独立してロックする方法を使用しています。空のバケットにノードを挿入する場合は、 ロックの代わりにCASアルゴリズムを使用し、それ以外の変更は、各バケットの最初のノードを基準に部分的なロック (synchronized block)を取得することで、スレッド競合を最小限に抑え、同時性を保証します。
ConcurrentHashMapに新しいノードを挿入するputVal()メソッドのコードを見て、どのように同時性を保証しているかを確認して みましょう。ちなみに、以下のコード例はJava 11基準です。
putVal()メソッドは、大きく以下の2つのケース(分岐は合計4つ)に分けられます。
- 空のハッシュバケットにノードを挿入する場合
- ハッシュバケットにすでにノードが存在する場合
```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ブロックを使用して、1つのスレッドだけがアクセスできるように制御します。この時、 空でないNode型のハッシュバケットにロックをかけるため、同じバケットにアクセスするスレッドは、Blocking状態になります。
(5) ハッシュ衝突が発生した場合、Separate Chaingに追加します。
(6) ハッシュ衝突が発生した場合、ツリーに追加します。
参考
予想される面接の質問と回答
Vector、HashTable、Collections.SynchronziedXXXの問題点は?
Vector、HashTable、SynchronziedXxxクラスは、synchronizedメソッドまたはブロックを使用しており、 1つのロックオブジェクトを共有しています。そのため、コレクションに1つのスレッドがロックを取得した場合、他のスレッドは すべてのメソッドを使用できなくなり、Blocking状態になります。これは、アプリケーションのパフォーマンス低下につながる可能性があります。
SynchronizedListとCopyOnArrayListの違いは?
SynchronizedListは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、CopyOnArrayListは、書き込み 操作時に、該当ブロックにロックをかけ、元の配列にある要素をコピーして新しい一時的な配列を作成し、この一時的な配列に書き込み操作を実行した後、 元の配列を更新します。これにより、読み取り操作はロックがかからないため、SynchronizedListよりも読み取りパフォーマンスが向上します。ただし、 書き込み操作は、コストの高い配列のコピー作業を行うため、SynchronizedListよりも書き込みパフォーマンスが低下します。
そのため、変更作業よりも読み取り作業が多い場合は、CopyOnArrayListを使用する方が効果的です。
SynchronizedMapとConcurrentHashMapの違いは?
SynchronziedMapは、読み取りと書き込み操作時に、インスタンス自体にロックがかかります。しかし、ConcurrentHashMapは、各 テーブルバケットを独立してロックする方法を使用しています。もし、空のバケットにノードを挿入する場合、ロック(Lock)の代わりにCASアルゴリズムを 使用し、それ以外の変更は、アクセスしたバケットのみにロックがかかり、スレッド競合を最小限に抑え、同時性を保証します。