情報科学屋さんを目指す人のメモ(FC2ブログ版)

何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。

ブログ内検索

スポンサーサイト このエントリーを含むはてなブックマーク

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
スポンサー広告 | 編集

java.util.ConcurrentModificationExceptionでつまづいた このエントリーを含むはてなブックマーク

今回は、Javaの便利なコレクションインターフェイスNavigableSet(TreeSet)/NavigableMap(TreeMap)を使ってConcurrentModificationExceptionを発生させてしまう問題が起こったときのことを、反省の意味で書き留めておきます実は、NavigableSetであることにそんなに意味はなくて、SortedSetでも同じ問題は起こるのですが^^;

注意:この記事、「つまり原因は?」の節以降だけで良かった気がします(冒頭半分近くはずっとNavigableSetの説明ですし)

NavigableSetインターフェイス

NavigableSetインターフェイス(java.util.NavigableSet)は、便利機能を追加したSortedSetです。標準ライブラリには、TreeSetとConcurrentSkipListSetの2つの実装がありますが、ここで触れるのはTreeSetのほうです。

便利って、何が便利なのかというと、データ構造的にはSortedListを実現しているのですが、以降に紹介するようなインターフェイスが追加されており、便利なのです。

サンプルコード用の準備

ためしに、格納するためのクラスMyElementを定義します。ただ、int型のnumberを持つだけのComparableインターフェイスを実装したクラスです。

public class MyElement implements Comparable<MyElement> {
	public final int number;
	public MyElement(int number) {
		this.number = number;
	}

	@Override
	public int compareTo(MyElement o) {
		return this.number - o.number;
	}
	
	@Override
	public String toString() {
		return String.valueOf(this.number);
	}
}

そして、これを実際に格納してみます。

NavigableSet<MyElement> elements = new TreeSet<MyElement>();
MyElement element1 = new MyElement(1);
MyElement element2 = new MyElement(2);
MyElement element3 = new MyElement(3);
MyElement element4 = new MyElement(4);
MyElement element5 = new MyElement(5);

elements.add(element1);
elements.add(element2);
elements.add(element3);
elements.add(element4);
elements.add(element5);

System.out.println(elements); // output: [1, 2, 3, 4, 5]

後々必要になるかもしれないという理由だけでちょっと変な書き方をしましたが、elementsというNavigableSet型の変数を用意して、番号1,2,3,4,5を持つMyElementオブジェクトを追加しました。さて、このとき、NavigableSetでは、以下のような便利メソッドが使えます。

便利なNavigableSetのインタフェイス(参照系)

tailSet(E fromElement, boolean inclusive) : NavigableSet<E>

NavigableSet<MyElement> greaterThan6 = elements.tailSet(new MyElement(6), false);
System.out.println(greaterThan6); // output: [8, 10]
NavigableSet<MyElement> greaterThanOrEqualTo6 = elements.tailSet(new MyElement(6), true);
System.out.println(greaterThanOrEqualTo6); // output: [6, 8, 10]

tailSetでは、与えられたfromElement以上・もしくはそれより大きい部分(集合)を抜き出して返します正確には、「抜き出す」とはちょっと違います

SortedSetにも同じメソッド名がありますが、これの特徴は、引数inclusiveのtrue/falseで「以上」と「より大きい」を使い分けられる点にあります。これがないと、「より大きい」をするために、「以上」を行ってから先頭を取り除いたりしなければなりません。まさに便利

headSet(E toElement, boolean inclusive) : NavigableSet<E>

NavigableSet lessThan6 = elements.headSet(new MyElement(6), false);
System.out.println(lessThan6); // output: [2, 4]
NavigableSet<MyElement> lessThanOrEqualTo6 = elements.headSet(new MyElement(6), true);
System.out.println(lessThanOrEqualTo6); // output: [2, 4, 6]

headSetは、tailSetの真逆で、「以下」と「より小さい」を抜き出します。

subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

NavigableSet<MyElement> greaterThanOrEqualTo4LessThan8 = elements.subSet(new MyElement(4), true, new MyElement(8), false);
System.out.println(greaterThanOrEqualTo4LessThan8); // output: [4, 6]

subSetは、headSetとtailSetに似ていて、fromElement以上/より大きくて、toElement以下/より小さい部分集合を返します。つまり、subSetはheadSetとtailSetを続けて行う感じです。便利。これまたSortedSetにもありますが、含む含まないが変更できる点が異なります。

ceiling(E e) : E

MyElement leastOfGreaterThanEqualTo6 = elements.ceiling(new MyElement(6));
System.out.println(leastOfGreaterThanEqualTo6); // output: 6
MyElement leastOfGreaterThanEqualTo7 = elements.ceiling(new MyElement(7));
System.out.println(leastOfGreaterThanEqualTo7); // output: 8

ceilingは、日本語に訳せば「切り上げ」であり、引数e以上の要素のうちで一番小さい要素を返します。SortedSetでやろうとしたら、tailSet(E fromElement)メソッドを使った後に先頭を取り出すことになります。ceiling(E e)があると便利。

floor(E e) : E

MyElement greatestOfLessThanEqualTo6 = elements.floor(new MyElement(6));
System.out.println(greatestOfLessThanEqualTo6); // output: 6
MyElement greatestOfLessThanEqualTo5 = elements.floor(new MyElement(5));
System.out.println(greatestOfLessThanEqualTo5); // output: 4

floorはceilingの反対向きの機能です。引数e以下の要素のうちで一番大きい要素を返します。これまた便利です。これくらいSortedSetの組み合わせでやればいい気もしますが、複雑なことをするときに、「ceiling」や「floor」だけで取り出せると、1行でたくさんの処理が分かりやすく処理できるのです。便利。

higher(E e) : E

MyElement leastOfGreaterThan6 = elements.higher(new MyElement(6));
System.out.println(leastOfGreaterThan6); // output: 8
MyElement leastOfGreaterThan7 = elements.higher(new MyElement(7));
System.out.println(leastOfGreaterThan7); // output: 8

higherは、ceilingの「以上」を「より大きい」にしたバージョンです。eより大きくて、一番小さい要素を返します。これをSortedSetで実現しようとするとceilingより面倒で、tailSetの後に先頭が「以上」でひっかかったのか「より大きい」で引っかかったかを判別して、場合によっては先頭から2番目を取り出す必要が出てきます。これは面倒です。この面倒を解決してくれるNavigableSetは便利ですね。

lower(E e) : E

MyElement greatestOfLessThan6 = elements.lower(new MyElement(6));
System.out.println(greatestOfLessThan6); // output: 4
MyElement greatestOfLessThan5 = elements.lower(new MyElement(5));
System.out.println(greatestOfLessThan5); // output: 4

lowerは、floorの「以下」を「より小さい」にしたバージョンです。eより小さくて、一番大きい要素を返します。

便利なNavigableSetのインタフェイス(変更+参照系)

pollFirst() : E / pollLast() : E

MyElement first = elements.pollFirst();
System.out.println(first); // output: 2
System.out.println(elements); // output: [4, 6, 8, 10]

MyElement last = elements.pollLast();
System.out.println(last); // output: 10
System.out.println(elements); // output: [4, 6, 8]

pollFirst()とpollLast()はそれぞれ、先頭(一番小さい要素)を取り出して削除するメソッドと、末尾(一番大きい要素)を取り出して削除するメソッドです。便利。

ConcurrentModificationException

ここからが本題です。NavigableSet(TreeSet)を使って下手なことをすると、ConcurrentModificationExceptionが発生します。たとえば、次のようなコードです。

for(MyElement element : elements) { // invoke "ConcurrentModificationException" after removal.
	System.out.println(element.number);
	if(element.number > 3) {
		// not invoke "ConcurrentModificationException" here.
		elements.remove(element);
	}
}

こんなことしなければいいのですが、iteratorでループさせて、3より大きい要素を削除しようとしています。一般に、iteratorで廻している最中にSetやMapに変更を加えてはいけません。この場合は、removeを行ってしまった時点では例外は発生しませんが、その直後にiteratorが次に進もうとするときConcurrentModificationExceptionが発生します。もちろんaddも駄目です。

NavigableSetを保持するクラスを作ったら

さて、こんな便利なNavigableSetをメンバとして保持しているクラスを作ろうとします。たとえば次のような、NavigableSet(TreeSet)に委譲するクラスを考えます。

public class MyElementSet {
	NavigableSet data = new TreeSet();
	public MyElementSet() { }
	public boolean add(int number) {
		return data.add(new MyElement(number));
	}
	public boolean remove(int number) {
		return data.remove(new MyElement(number));
	}
	public NavigableSet greaterThan(int number) {
		return data.tailSet(new MyElement(number), false);
	}
	
	/* other methods */
}

こんなことしないと思いつつもイメージなのでご愛敬。どんな状況かというと、もっとMyElementに機能があって、MyElementSetにもたくさん機能がある感じです。とりあえずaddとremoveを作り、参照用のメソッドも作ろうとしてgreaterThanを作ったとします。そしてこのとき、NavigableSet便利だから、返値をNavigableSetのままにしておいた方が便利なんじゃないか?という発想です(←ここが問題だった)。

マルチスレッド用に書き換えてみる

さて、このクラスをマルチスレッドで使うことにしたとします。マルチスレッドで動かしたら駄目そうだな、ということで、だいたい次のようにしてみるわけです。

public class MyElementSet {
	NavigableSet data = new TreeSet();
	public MyElementSet() { }
	synchronized public boolean add(int number) {
		return data.add(new MyElement(number));
	}
	synchronized public boolean remove(int number) {
		return data.remove(new MyElement(number));
	}
	synchronized public NavigableSet greaterThan(int number) {
		return data.tailSet(new MyElement(number), false);
	}
	
	/* other methods */
}

よし、これでNavigableSet型(actual typeはTreeSet)のメンバ「data」へのアクセスは同時に発生しないはずだ。とかなるわけです。しかし、先ほどの「便利だからNavigableSet型で返そう」という判断がめんどくさいことになります。

NavigableSet型を返したことによる弊害

さて、このコードを利用すると、「greaterThan」メソッドによって中身の一部が取得できて、利用する側のコードでいろいろ複雑な作業が出来てしまうわけです。。

たとえばこれを利用するコードの中で、greaterThanメソッドで取得したNavigableSet型のオブジェクトのサイズを測るとします。つまり「size()」メソッドを使います。そして、運が悪いと、「ConcurrentModificationException」が投げられます自分はここにはまりました

tailSet、headSet、subSetなどで取得したNavigableSetはViewである

ポイントは二つあります。一つ目は、tailSetで取得していたNavigableSetは、中身のコピーでもなんでもなく、もとのNavigableSetの条件に一致する部分集合だけを抜き出して見ることが出来るViewと呼ばれるものなのだということです。なので、tailSetで取得したNavigableSetにaddやremoveを行うともとのNavigableSetに反映されます。そして、先ほど例外を投げた「size()」メソッドも同様に、もとのNavigableSetの中でサイズを「測定」しているのです。

TreeSetのsize()メソッドが、Iteratorを使う

もう一つのポイントは、TreeSetのsize()メソッドが内部でiteratorを使っているということです。

つまり原因は?

つまり、このConcurrentModificationExceptionが投げられたのは、size()メソッドが内部でiterationを行ってサイズを測定している間に、別のスレッドがMyElementSet#add/removeを利用して大本のNavigableSetを書き換えてしまったことが原因だったのです。

反省

どうしてこんなことになってしまったかというと、次のあたりが原因です。

  • NavigableSet#tailSetの返値があくまでViewであり、同期を取るべきオブジェクトが分身することを知らなかった。
  • 分身した同期を取るべきオブジェクトを、カプセル化してしているMyElementSetクラスの外側に出せるメソッドを作ってしまった

しっかり、中身を参照させるときは、コピーを作成しないと危ないですね。じゃぁNavigableSetを返すところでコピーを作り直すべきなのかなぁとも思いますが、メソッドがコピーしたものを返しているのかどうかをドキュメントに書かないとまた面倒なことになりますメソッド名で分かるようなものであればいいですが書くのが面倒と言うより、こういう問題に気がついて、「どうなんだろう?」と思ってドキュメントを見るべきだと気がついてもらえないと駄目ということろがやっかいに感じるんですよね。もちろん自分が気がつかないというか、忘れそうと言う意味で、です。なので、どこから使われるか分からないインターフェイスに含まれるメソッド関しては、Collectionではなくて配列を戻り値にするのがいいのかなぁと思いました。

こうやって自分がバグを作り込んだ仕組みを書き出してみると、自分のどこが悪くて、次からどうすると同じような問題を起こさずに済みそうかがよく分かりました←これ最大の発見

Effective Java 第2版
改訂第2版 Java言語プログラミングレッスン (上)
増補改訂版Java言語で学ぶデザインパターン入門

スポンサーサイト
Java | コメント:0 | トラックバック:0 | 編集

C#での、正しいマルチスレッドプログラムの書き方を求めて このエントリーを含むはてなブックマーク

注意:.NET Framework 4、Visual Studio 2010に対応してアップデートした記事はこちら→「C#での、正しいマルチスレッドプログラムの書き方を求めて(2011年11月版)

C#におけるマルチスレッドプログラムの作成方法は、たくさんのホームページで紹介されています。しかし、それらは正しく動いたとしても、それがC#や.NET Frameworkを作成した人々の期待したコードであるかどうかは残念ながら、コードを見るだけでは分かりません生意気なこと言ってすいません

また、BackgroundWorkerという、簡単に別スレッドを作成してメソッドを実行する方法も用意されてはいますが、それで満足していいのかという欲求もあります。より高度なスレッドの扱い方を会得したい。

そんなとき、やはり頼るべきはMicrosoft謹製 msdnライブラリでしょう。

しかし、実際にmsdnライブラリでマルチスレッドプログラミングついて調べていると、リンクが散らばっていて、どこを見ればいいのか分かりません。

そこで、msdn内のマルチスレッドに関するページをまとめてみました。msdnは重く、検索に時間がかかるので、このページをブックマークしておくと楽だと思います。

C# | コメント:0 | トラックバック:0 | 編集

オペレーティングシステムの勉強 このエントリーを含むはてなブックマーク

今日はオペレーティングシステムについていろいろ勉強しました。

記録として、重要単語一覧を書いてみます。

まぁ、オペレーティングシステムまとめ みたいな感じ。

OSって、奥が深いですね。こうやって今使っているOSにもこういう機能があるっていうことがなんとなく不思議に感じます。

↓ちょっと高いんだよなぁ
Operating System Concepts
OS自作入門

数学・情報科学 | コメント:0 | トラックバック:0 | 編集
 | HOME | 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。