Javaのリストにマルチスレッドでアクセスする３種類の方法のおさらい

# はじめに
みなさんは、Javaのリストにマルチスレッドでアクセスするときにどのようなコードを書いていますでしょうか。
最近、コードレビューしたアプリには３種類のリストの同期方法が混在していて少し分かりにくい状況に。
改めてリストにマルチスレッドでアクセスする方法を整理してみました。

1. Listをsynchronized
2. synchronizedList
3. CopyOnWriteArrayList

# 同期し忘れているコード
まずは、同期し忘れていて、[java.util.ConcurrentModificationException](https://docs.oracle.com/javase/jp/8/docs/api/java/util/ConcurrentModificationException.html) が発生するプログラムを書いてみます。

+ MainClassで複数のスレッドからアクセスされるリストを定義します。
+ IterateClassでは、別スレッドからイテレータを使ってリストにアクセスします。
+ EditClassでは、別スレッドからリストに要素を追加したり削除したりします。

```MainClass.java
package sample;

import java.util.ArrayList;
import java.util.List;

class MainClass {

	List<String> list = new ArrayList<>();

	static MainClass inst = new MainClass();

	public static void main(String[] args) {
		inst.execute();
	}

	void execute() {
		IterateClass iteClass = new IterateClass();
		Thread iteThread = new Thread(iteClass);
		iteThread.start();

		EditClass editClass = new EditClass();
		Thread editThread = new Thread(editClass);
		editThread.start();

		synchronized (this) {
			try {
				wait(10 * 1000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}

		iteClass.setEndFlag(false);
		editClass.setEndFlag(false);
	}

	List<String> getList() {
		return list;
	}

	static MainClass getInstance() {
		return inst;
	}
}
```

```IterateClass.java
package sample;

import java.util.Iterator;
import java.util.List;

class IterateClass implements Runnable {

	boolean endFlag = true;

	@Override
	public void run() {
		while (endFlag) {
			synchronized (this) {
				try {
					printList();
					wait(100);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

	void printList() {
		List<String> list = MainClass.getInstance().getList();

		Iterator<String> ite = list.iterator();
		while (ite.hasNext()) {
			System.out.print(ite.next() + ", ");
		}
		System.out.println("");
	}

	void setEndFlag(boolean p_endFlag) {
		endFlag = p_endFlag;
	}
}
```

```EditClass.java
package sample;

import java.util.List;

class EditClass implements Runnable {

	boolean endFlag = true;

	@Override
	public void run() {
		while (endFlag) {
			synchronized (this) {
				addElement("a");
				addElement("b");
				addElement("c");
				addElement("d");
				addElement("e");
				deleteElement();
				deleteElement();
				deleteElement();
				deleteElement();
				deleteElement();
			}
		}
	}

	void addElement(String str) {
		List<String> list = MainClass.getInstance().getList();
		list.add(str);
	}

	void deleteElement() {
		List<String> list = MainClass.getInstance().getList();
		list.remove(0);
	}

	void setEndFlag(boolean p_endFlag) {
		endFlag = p_endFlag;
	}
}
```

実行すると`java.util.ConcurrentModificationException`が発生します。

```
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at sample.IterateClass.printList(IterateClass.java:31)
	at sample.IterateClass.run(IterateClass.java:15)
	at java.lang.Thread.run(Thread.java:745)
```

# Listをsynchronized

リストにアクセスするところをsynchronizedで同期します。
プログラムはこうなります。

```MainClass.java
import java.util.ArrayList;
import java.util.List;

class MainClass {

	List<String> list = new ArrayList<>();
```

```IterateClass.java
	void printList() {
		List<String> list = MainClass.getInstance().getList();

		synchronized (list) {
			Iterator<String> ite = list.iterator();
			while (ite.hasNext()) {
				System.out.print(ite.next() + ", ");
			}
		}

		System.out.println("");
	}
```

```EditClass.java
	void addElement(String str) {
		List<String> list = MainClass.getInstance().getList();
		synchronized (list) {
			list.add(str);
		}
	}

	void deleteElement() {
		List<String> list = MainClass.getInstance().getList();
		synchronized (list) {
			list.remove(0);
		}
	}
```

● 実行結果

１０秒間、リストの内容がコンソール出力されます。

```

d, e, 
a, 
a, b, c, d, 
a, b, 
c, d, e, 
a, b, c, 


a, b, c, d, e, 
c, d, e, 

a, b, c, 
a, 
a, b, c, d, e,
...
```

# synchronizedList
Collections FrameworkのsynchronizedListを使います。

リストは、Collections.synchronizedList を使います。
要素の追加や削除は `synchronized` する必要がなくなります。
一方、リストのイテレーション操作は引き続き `synchronized` する必要があります。

```MainClass.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class MainClass {
	List<String> list = Collections.synchronizedList(new ArrayList<>());
```

```IterateClass.java
	void printList() {
		List<String> list = MainClass.getInstance().getList();

		synchronized (list) {
			Iterator<String> ite = list.iterator();
			while (ite.hasNext()) {
				System.out.print(ite.next() + ", ");
			}
		}

		System.out.println("");
	}
```

※ JavaDocにも、リストのイテレーション操作時にsynchronizedが必要だと記載されています。

```EditClass.java
	void addElement(String str) {
		List<String> list = MainClass.getInstance().getList();
		list.add(str);
	}

	void deleteElement() {
		List<String> list = MainClass.getInstance().getList();
		list.remove(0);
	}
```


# CopyOnWriteArrayList
`java.util.concurrent` パッケージの `CopyOnWriteArrayList` を使います。
「synchronizedList」のプログラムでは、リストのイテレーション操作をsynchronizedしていましたが、こちらはsynchronizedする必要ありません。「同期し忘れている」と同じプログラムでOKです。

```MainClass.java
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

class MainClass {
	List<String> list = new CopyOnWriteArrayList<>();
```

```IterateClass.java
	void printList() {
		List<String> list = MainClass.getInstance().getList();

		Iterator<String> ite = list.iterator();
		while (ite.hasNext()) {
			System.out.print(ite.next() + ", ");
		}
		System.out.println("");
	}
```

```EditClass.java
	void addElement(String str) {
		List<String> list = MainClass.getInstance().getList();
		list.add(str);
	}

	void deleteElement() {
		List<String> list = MainClass.getInstance().getList();
		list.remove(0);
	}
```

CopyOnWriteArrayList は、一見、簡単なのですが、内部はリストのコピーなので、メモリを消費し処理が遅いです。
リストのイテレーション操作がほとんどで、要素の追加や削除はめったに発生しない場合に利用する方法です。

# ConcurrentModificationException
　イテレータの操作をしている間に他のスレッドがコレクションの要素数が変わってしまう変更を加えるときに発生する[ConcurrentModificationException](https://docs.oracle.com/javase/jp/8/docs/api/java/util/ConcurrentModificationException.html)は、JavaDocに但し書きがあります。

```javadoc.html
通常、非同期の並行変更がある場合、確かな保証を行うことは不可能なので、
フェイルファストの動作を保証することはできません。
フェイルファスト・オペレーションは最善努力原則に基づき、
ConcurrentModificationExceptionをスローします。
したがって、正確を期すためにこの例外に依存するプログラムを書くことは誤りです。
ConcurrentModificationExceptionはバグを検出するためにのみ使用すべきです。
```

　コレクションをイテレータで処理中に、別スレッドから要素数を変更するような操作を行ったときに、`ConcurrentModificationException`をスローできればスローするが、検知できない場合もあるということを言っています。
　`ArrayList`や`LinkedList`のソースを見ると、XXXListには変更回数を管理するmodCountフィールドがあります。add()やremove()のときに変更回数modCountの値をインクリメントします。そして、XXXListの内部にはインナークラスとしてListIteratorクラスをかかえています。ListIteratorクラスは、modCount値に変更があったかどうかを比較する際の正解値としてexpectedModCountフィールドをもっています。インナークラスListIteratorのインスタンスが生成されるタイミングで、ListIteratorクラスのexpectedModCountフィールドにmodCount値をセットします。イテレータは、操作を行うたびにメソッドの最初や最後にmodCount値とexpectedModCount値を比較します。イテレータを使って、add()やremove()を行う場合は、最初に値の比較をして、要素数を変更したあとにexpectedModCount値を更新します。また、modCount値とexpectedModCount値を比較だけではなく、現在のカーソル値とコレクションの要素数の比較も随所で行います。
　このように変更を検知する様々な仕組みがあるものの、通常のXXXListやsynchronizedListのイテレータ操作部分は、まったくロックがかかっていません。いくらmodCount値やexpectedModCount値をチェックしたところで、そもそもこの値は、複数スレッドから同時に変更されてしまう状態では、信頼できない値なのです。よって、modCount値とexpectedModCount値の比較結果も信頼することができません。
　マルチスレッドでリスト操作を行い、`ConcurrentModificationException`が発生しないことを確認しても、場合によっては、バグが残っている可能性があることを頭の片隅に置いておく必要があります。