Java Puzzlers Advent Calendar 2016 – Coffee Break —

Java

このエントリーは http://qiita.com/advent-calendar/2016/java_puzzlers の 21 日目です。

昨日は @zr_tex8r さんのの「ループ以外の文にラベルは付けられるか?」でした。

明日は @khasunuma さんの「誰も投稿しそうにないので、もう少し頑張ってみる」です。

連日高度な Java Puzzle が投稿されていて楽しませていただいてます。

「ジャバチョットデキル」という凄い人たちの投稿でクリティカルヒットを食らってダウンしてます。(^_^;

ここらへんで CoffeeBreak ということで息抜きパズルでエントリーさせていただきます。

古典的なありふれたネタですがお楽しみください。

ちなみにこのプログラムはパズル用なので実用性の欠片もありません。

問題

次のプログラムをコンパイル、実行すると標準出力にどんな結果を表示するでしょうか?

(1)

1767504129 pool-1-thread-1
1767504129 pool-1-thread-3
1767504129 pool-1-thread-2
1767504129 pool-1-thread-4
-243838107 ForkJoinPool.commonPool-worker-25
1829062017 ForkJoinPool.commonPool-worker-18
1664456421 ForkJoinPool.commonPool-worker-18
856650241 ForkJoinPool.commonPool-worker-25
executor.shutdown()

ExecutorService を使った方は同じハッシュ・コード値を必ず返す。

(2)

1767504129 pool-1-thread-4
1767504129 pool-1-thread-2
1767504129 pool-1-thread-1
1767504129 pool-1-thread-3
1829062017 ForkJoinPool.commonPool-worker-25
1829062017 ForkJoinPool.commonPool-worker-18
1829062017 ForkJoinPool.commonPool-worker-18
1829062017 ForkJoinPool.commonPool-worker-25
executor.shutdown()

ExecutorService、ForkJoin ともに同じハッシュ・コード値を必ず返す。

(3)

-230323071 pool-1-thread-1
1767504129 pool-1-thread-4
-2046939163 pool-1-thread-3
-230323071 pool-1-thread-2
-243838107 ForkJoinPool.commonPool-worker-25
1829062017 ForkJoinPool.commonPool-worker-18
1664456421 ForkJoinPool.commonPool-worker-18
856650241 ForkJoinPool.commonPool-worker-25
executor.shutdown()

同じハッシュ・コード値を返す場合もある

(4)

1647295788 pool-1-thread-1
-591109637 pool-1-thread-4
1767504129 pool-1-thread-2
357637727 pool-1-thread-3
-243838107 ForkJoinPool.commonPool-worker-25
1829062017 ForkJoinPool.commonPool-worker-18
1664456421 ForkJoinPool.commonPool-worker-18
856650241 ForkJoinPool.commonPool-worker-25
executor.shutdown()

おのおのユニークなハッシュ・コード値を返す。

(5)

実行時例外

(6)

コンパイルエラー

 

答え

正解は‥‥

 

 

 

 

 

 

(1) ではありません。

 

 

 

(2)  でもありません。

 

 

 

(3) が正解といいたいところですが違います。

実はこのように出力されることもあります。

ただし、100 パーセントこのように出力される保証はなくプログラムのコードには致命的な大きな問題がひそんでいます。

よって、不正解ということでご了承くださいませ。

 

 

 

正解は (5) 実行時例外です。

java.util.ConcurrentModificationException が投げられます。

65 行目の System.out.println(friends.hashCode() + ” ” + Thread.currentThread().getName()); が原因です。

java.util.ConcurrentModificationException とはどんな例外なのでしょうか?

Javadoc を見てみましょう。

この例外は、オブジェクトの並行変更を検出したメソッドによって、そのような変更が許可されていない場合にスローされます。
 
たとえば、あるスレッドが Collection で繰り返し処理を行なっている間に、別のスレッドがその Collection を変更することは一般に許可されません。

通常、そのような環境では、繰り返し処理の結果は保証されません。

いくつかのイテレータ (Iterator) の実装 (JRE が提供するすべての一般的な目的のコレクションの実装の、イテレータの実装を含む) は、その動作が検出された場合にこの例外をスローすることを選択できます。

この例外をスローするイテレータは、フェイルファストイテレータと呼ばれます。

イテレータは、将来の予測できない時点において予測できない動作が発生する危険を回避するために、ただちにかつ手際よく例外をスローします。

この例外は、オブジェクトが別のスレッドによって並行して更新されていないことを必ずしも示しているわけではありません。

単一のスレッドが、オブジェクトの規約に違反する一連のメソッドを発行した場合、オブジェクトはこの例外をスローします。

たとえば、フェイルファストイテレータを持つコレクションの繰り返し処理を行いながら、スレッドがコレクションを直接修正する場合、イテレータはこの例外をスローします。

通常、非同期の並行変更がある場合、確かな保証を行うことは不可能なので、フェイルファストの動作を保証することはできません。

フェイルファストオペレーションは最善努力原則に基づき、ConcurrentModificationException をスローします。

したがって、正確を期すためにこの例外に依存するプログラムを書くことは誤りです。

ConcurrentModificationException は、バグを検出するためにのみ使用してください。

以上、 Javadoc より

つまり、 Java の同期化コレクションはマルチスレッドなどによる並行的な変更には完全に対応できないということです。

だから並行的な変更への対処はイテレーション開始後に Collection が変更されたのを検出すると ConcurrentModificationException 例外をただちに投げるというフェイルファストという設計になっている。

ただし、このフェイルファスト設計は実行性能に与える影響を抑えるためにそれほど優秀な設計にはなってないようです。

では、この問題の鍵はどこにあるのだろう?

どうして? Iterator で回してないのにと思われる人は純な心の持ち主でしょう。

hashCode() メソッドの実装は次のようになっています。

拡張 for 文を使っていますね。

これは内部でイテレータを使ってます。だから java.util.ConcurrentModificationException が投げられます。

もう少し確認するために次のような変更をプログラムに加えてみましょう。

65 行目の System.out.println(friends.hashCode() + ” ” + Thread.currentThread().getName()); を

System.out.println(“My Friends: ” + friends + ” ” + Thread.currentThread().getName()); に変更して実行してみます。

これでも java.util.ConcurrentModificationException が投げられます。

どうしてでしょう?

まず、文字列の連結操作により StringBuilder クラスの次のメソッドが呼ばれます。

続いて String クラスの次のメソッドが呼ばれます。

そして、AbstractCollection<E> クラスの次のメソッドが実行されます。

おおっ! Iterator でぶん回してますね

問題の hashCode() メソッド同様に内部で Iterator を使ってます。

このように間接的に Iterator を使っていることに気づかずに致命的なミスをおかしてしまう可能性があります。

Collection の取り扱いには細心の注意が必要です。

それではこのプログラムの修正はどうすればいいでしょうか?

この問題のプログラムは Collection への要素の追加、削除を次のように synchronized メソッドで排他制御を行ってます。

これでは Collection をイテレーションしている間に別のスレッドによる変更操作が行われてしまいます。

排他制御を行うには public void update() メソッドを public synchronized void update() メソッドに変更すれば OK です。

要素の追加、削除のメソッドは排他制御を行う必要はこれでなくなります。

synchronized による排他制御を行いたくない場合は ReentrantLock を使う方法があります。

最後に CopyOnWriteArrayList<E> を使う方法があります。

ただし、これは今までの排他制御とは異なります。

CopyOnWriteArrayList<E> の Javadoc を読んでみましょう。

public class CopyOnWriteArrayList<E> extends Object implements List<E>, RandomAccess, Cloneable, Serializable

基になる配列の新しいコピーを作成することにより、すべての推移的操作(add、setなど)が実装されるArrayListのスレッド・セーフな変数です。
 
通常、これは非常に効率が悪いのですが、トラバーサル操作が変更を数の点で大幅に上回る場合には、代替手段よりも効率が良い場合があります。

また、これは、トラバーサルを同期できない場合や、同期することを望まないが、並行スレッド間の干渉を排除する必要がある場合に有用です。

「スナップショット」スタイルのイテレータ・メソッドは、イテレータの作成時点での配列状態への参照を使用します。

この配列がイテレータの有効期間中に変更されることは決してないため、干渉は不可能であり、イテレータはConcurrentModificationExceptionをスローしないことが保証されます。

イテレータは、イテレータの作成以降のリストへの追加、削除、または変更を反映しません。

イテレータ自体に対する要素変更操作(remove、setおよびadd)はサポートされません。これらのメソッドは、UnsupportedOperationExceptionをスローします。

nullを含むすべての要素が許可されます。

メモリー整合性効果: ほかの並行処理コレクションと同様、オブジェクトをCopyOnWriteArrayListに配置する前のスレッド内のアクションは、別のスレッドでのその要素へのアクセスまたはCopyOnWriteArrayListからの削除に続くアクションよりも前に発生します。

このクラスは、Java Collections Frameworkのメンバーです。

つまり、スナップショット(コピー)を作ってそれをイテレーションすることによってスレッド・セーフを可能にしているようです。

private final List<String> friends = new ArrayList<>(16); を

private final CopyOnWriteArrayList<String> friends = new CopyOnWriteArrayList<>(); に変更するだけのお手軽仕様です。

ただし、CopyOnWriteArrayList<E> は初期容量を設定できないのでお間違いなく!

いかがでしたでしょうか?

本当に古典的なありふれたパズルですが懐かしさと初めて java.util.ConcurrentModificationException を投げられたときの ??? ってのを思い出していただければ幸いです。

ここでネタばらし・・・ この問題は 「Java 並行処理プログラミング」という古い本にも載っているほど超有名なネタでした。

これだけだと CoffeeBreak ネタとしては面白みに欠けていますのでグリコのキャラメルのおまけのような問題をもう一問どうぞ。

ていうか、これが本題です。

グリコのキャラメルのおまけのような問題

次のプログラムをコンパイル、実行すると標準出力にどんな結果を表示するでしょうか?

ただし、public static void parkUntil(long deadline) メソッドの理由無き復帰はないものとする。

(1)

今日も一日がんばるぞい!
1時 2時 3時
□フo(^-^)コーヒーブレイク
そろそろ休憩おわりにしようか?
4時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
(゙ `-´)/ コラッ!!  休憩は3時間だぞ。働け!
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
7時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
コーヒーブレイク終了
9時 10時
仕事終わった! 愛する家族の元へ帰ろう!

(2)

今日も一日がんばるぞい!
1時 2時 3時
□フo(^-^)コーヒーブレイク
3時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
そろそろ休憩おわりにしようか?
4時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
(゙ `-´)/ コラッ!!  休憩は3時間だぞ。働け!
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
7時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
コーヒーブレイク終了
9時 10時
仕事終わった! 愛する家族の元へ帰ろう!

(3)

実行時例外

(4)

コンパイルエラー

 

答え

 

 

 

 

 

 

 

正解は‥‥

 

 

 

 

(1) ではありません。

 

 

 

 

 

(2) です。

worker スレッドが開始された直後に LockSupport.unpark(worker); が実行されます。(45 行目)

これは引数で指定したスレッドにパーミットを与えます。

このパーミットは一つだけ蓄積可能となります。

よって、worker スレッドの LockSupport.parkUntil(t); (30 行目) はパーミットを消費してすぐにリターンされます。

故に標準出力に

今日も一日がんばるぞい!
1時 2時 3時
□フo(^-^)コーヒーブレイク
3時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~

と表示されます。

そして 48行目の LockSupport.unpark(worker); が実行されて

そろそろ休憩おわりにしようか?
4時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~

と続きます。

while ループで再び LockSupport.parkUntil(t); が実行されます。

指定された待機時間を経過してないのでスレッドは再び待機します。

51 行目で worker.interrupt(); と割り込みをかけます。

ところがこの割り込みに対して InterruptedExceptionがスローされません。

割り込みによる処理をなにもしていないので LockSupport.parkUntil(t); による指定された待機時間までの待機は解除されすぐにリターンされます。

while ループで指定された待機時間まで延々と標準出力に次のように出力されます。

(゙ `-´)/ コラッ!!  休憩は3時間だぞ。働け!
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
6時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
7時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
            .
            .
            .
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
8時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
コーヒーブレイク終了
9時 10時
仕事終わった! 愛する家族の元へ帰ろう!

これをスッキリした出力にするためには 45 行目の LockSupport.unpark(worker); を削除し、

worker スレッドへの割り込みの対処を次のようにすれば期待する出力が得られます。

今日も一日がんばるぞい!
1時 2時 3時
□フo(^-^)コーヒーブレイク
そろそろ休憩おわりにしようか?
4時やん。 まだ、コーヒーブレイク タイム。 □フo(^O^)プハァ~
(゙ `-´)/ コラッ!!  休憩は3時間だぞ。働け!
はい、はい。
6時 7時 8時 9時 10時 仕事終わった! 愛する家族の元へ帰ろう!

参考にこのプログラムで使った java.lang.Object java.util.concurrent.locks.LockSupport クラスのメソッドの Javadoc を載せておきます。

public static void unpark(Thread thread)

指定されたスレッドのパーミットが使用可能でない場合に、使用可能にします。

スレッドがparkでブロックされた場合は、ブロックを解除します。

それ以外の場合は、そのparkの次回の呼出しがブロックされないよう保証されます。

指定されたスレッドが起動していない場合、この操作の効果は一切保証されません。

パラメータ:thread – unparkを実行するスレッドまたはnull。その場合、この操作に効果はない

public static void parkUntil(long deadline)

パーミットが利用可能でない場合、指定された期限まで、スレッドのスケジューリングに関して現在のスレッドを無効にします。
 
パーミットが使用可能な場合、これは消費され、呼出しはただちに復帰します。

それ以外の場合、現在のスレッドは、スレッド・スケジューリングに関して無効になり、次の4つのいずれかが起きるまで待機します。
 
•ほかのスレッドが、現在のスレッドをターゲットとしてunparkを呼び出す。
•ほかのスレッドが現在のスレッドに割り込みを行う。または
•指定された期限が経過する。または
•呼出しが、見せかけで(理由もなく)復帰する。

このメソッドは、これらのどれがメソッド復帰の原因となったかはレポートしません。

呼出し側は、スレッドの初回parkの原因となった状態を再チェックする必要があります。

呼出し側は、スレッドの割込み状態や、復帰時の現在時刻なども判定できます。

パラメータ:deadline – 待機用の、元期からのミリ秒単位の絶対時間

以上、Coffee Break ネタでした。(^_^)

さらに、おまけ

次のプログラムの出力結果を答えよ。

 

 

 

 

答え

 

 

 

 

 

Results of Math and StrictMath were not the same.
-2
true
false

これはクイズ要素も引っかけ要素もまるで無いです。

強いてあげれば3行目の出力結果くらいですね。

よくあるオーバーフローねたです。(^_^;

API ドキュメントにすべて解説してありますので知らなくて興味のある人は覗いてみましょう。

java.lang.Object java.lang.Math public static double log(double a)

java.lang.Object java.lang.StrictMath public static double log(double a)

public static int floorDiv(int x, int y)

public static int floorMod(int x, int y)

以上、お終い!

Hatena タグ: