質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.51%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

4回答

6944閲覧

非同期処理 wait,notifyAllの使い方

swordone

総合スコア20649

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

1グッド

1クリップ

投稿2016/04/28 15:48

java

1import java.util.Collections; 2import java.util.LinkedList; 3import java.util.List; 4import java.util.Scanner; 5 6public class CountPal extends Thread{ 7 8 private static Long count = 0L; 9 private static List<CountPal> threads = Collections.synchronizedList(new LinkedList<>()); 10 11 private final long from; 12 private final long until; 13 14 public CountPal(long from, long until) { 15 this.from = from; 16 this.until = until; 17 } 18 19 @Override 20 public void run() { 21 long total = 0L; 22 for(long i = from; i < until; i++){ 23 if(checkPal(i)){ 24 total += i; 25 } 26 } 27 synchronized (count) { 28 count += total; 29 } 30 threads.remove(this); 31 } 32 33 private boolean checkPal(long i){ 34 String str = Long.toString(i); 35 int m = 0; 36 int n = str.length() - 1; 37 while(m < n){ 38 if(str.charAt(m) != str.charAt(n)){ 39 return false; 40 } 41 m++; 42 n--; 43 } 44 return true; 45 } 46 47 48 49 public static void main(String[] args) { 50 try (Scanner s = new Scanner(System.in)) { 51 long max = s.nextLong(); 52 for(long x = 1; x <= max; x += 10000){ 53 CountPal temp = new CountPal(x, Math.min(x + 10000, max + 1)); 54 threads.add(temp); 55 temp.start(); 56 } 57 // すべてのスレッドが終了するまで待つ 58 while(threads.size() != 0){ 59 try { 60 System.out.println(threads.size()); // 現在のスレッド数ダンプ 61 Thread.sleep(1000); 62 } catch (InterruptedException e) { } 63 } 64 System.out.println(count); 65 } 66 } 67 68}

ある数を入力し、その数以下の回文数(121のように左右どちらから読んでも同じになる数)の合計を求めるプログラムです(本題のプログラム問題を解くために作成した、時間はかかるが確実に正しい答えを出すための副産物的なプログラムです)。
適当な数(10000)で分割し、スレッドを生成して手分けしてカウントするようなプログラムなのですが、「すべてのスレッドが終了するまで待つ」という部分が上手く書けません。
現状、生成したThreadをListに詰め、終了する際にThreadがListから自身を取り除くようにし、ListのThreadが0になるまで待つ、という構成なのですが、0になってからも1秒未満とはいえ余計に待つことになります。
調べるとwait()やnotifyAll()を使うらしいことはわかったのですが、何に対してこのメソッドを使えばいいのかがわかりません。
また、Listを使う以外の方法がもしありましたら教えてください。

yohhoy👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

ベストアンサー

発想を変えて、Threadを使わず、Streamでparallelにしちゃうのはどうでしょうか?

Java

1import java.util.Scanner; 2import java.util.stream.LongStream; 3 4public class CountPal3 extends Thread{ 5 6 private static boolean checkPal(long i){ 7 String str = Long.toString(i); 8 int m = 0; 9 int n = str.length() - 1; 10 while(m < n){ 11 if(str.charAt(m) != str.charAt(n)){ 12 return false; 13 } 14 m++; 15 n--; 16 } 17 return true; 18 } 19 20 public static void main(String[] args) { 21 try (Scanner s = new Scanner(System.in)) { 22 long max = s.nextLong(); 23 long count = LongStream 24 .rangeClosed(0, (max - 1) / 10000).parallel() 25 .map(i -> i * 10000 + 1) 26 .map(x -> LongStream.range(x, Math.min(x + 10000, max + 1)) 27 .filter(CountPal3::checkPal).sum()).sum(); 28 System.out.println(count); 29 } 30 } 31 32}

実行結果比較

$ echo 1000000000 | time java CountPal 2 50045045045040 23.55 real 72.95 user 7.12 sys $ echo 1000000000 | time java CountPal2 100000 50045001340240 22.79 real 73.50 user 7.62 sys $ echo 1000000000 | time java CountPal3 50045045045040 19.99 real 66.79 user 0.90 sys

CountPalはswordoneさんのオリジナルコード、CountPal2はKiyoshiMotokiさんのコード、CountPal3が上のコードです。KiyoshiMotokiさんのコードが時々違う値を返すのは私にもわからないです。オリジナルのコードも値が大きいと時々違う値になるようです。脆弱性がまた出たからJava 1.8.0_92にあげたばかりなんですけど、なぜなんでしょうかね?


###オリジナルやKiyoshiMotokiさんのコードが不安定になる理由(たぶん、でも自信無し)

Java

1synchronized (count) { 2 count += total; 3}

原因は上の部分ですが、countがLongだからではなく、countが新しいオブジェクトに置き換わっているからだと思われます。上のコードは、オートボクシングせずに、かつ、+=の糖衣構文も分解すると下記になります。

Java

1synchronized (count) { 2 count = new Long(count.longValue() + total) 3}

そう、countには新しいオブジェクトが代入されます。この新しいcountは、synchronized によって現在ロックされているオブジェクトではありません。でも既に置き換わっているから大丈夫?と思うかも知れませんが、そうではありません。他のスレッドがcountを評価済みの場合は排他制御が失敗します。例えば、スレッドth1、th2、th3と三つある場合を考えます。現在のcountをct1として、新しく作られる度にct2、ct3とすると次のような動作が発生すると考えらます。

スレッド(ロックオブジェクト): 処理
th1: ct1でsynchronized -> ct1のロック成功
th2: ct1でsynchronized -> th1がロック済みのため、ブロック
th1(ct1): countからct1の値を取得
th1(ct1): 取得した値(ct1)からct2を生成
th1(ct1): countにct2を代入
th1: ct1のロック解除
th2: ct1のロックが解除されたのでブロック解除、ct1のロック成功
th3: ct2でsynchronized -> ct2のロック成功 (th3が見に行くときはcountはct2になっている)
th2(ct1): countからct2の値を取得
th3(ct2): countからct2の値を取得
th2(ct1): 取得した値(ct2)からct3を生成
th3(ct2): 取得した値(ct2)からct3'を生成
th2(ct1): countにct3を代入
th3(ct2): countにct3'を代入 // th2でct3の代入は無かったことに
th2: ct1のロック解除
th3: ct2のロック解除

th2の処理は無かったことにされ、その分すくない結果となります。重要なのは、synchronized(count)でロックが取れずブロックされた時点で、countの評価が終わっており、ブロック解除された後に再評価されない(上でいうと、ct2を取得し直さずに、ct1を使おうとする)と言う点です。そのため、待たされていたスレッドは古いオブジェクトを使ってロックをかけてしまい、新しいオブジェクトでロックをしようとする他のスレッドと処理が重複します。

なお、private static Long lock = 0L;とロック用にlockを作った場合は問題は起きませんでしたので、Longオブジェクトからと言う理由ではないと思われます。synchronizedの中で代入する形であれば、Mutable/Immutableおよびラッパークラスかどうかに関係なく発生する可能性があると思われます。

投稿2016/04/29 12:05

編集2016/04/30 05:36
raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2016/04/29 12:19 編集

なるほど、Streamが使えましたね。しかもこれなら分割する必要もなさそうですね。 ありがとうございます。 オリジナルのコードでも違う値になることがあるのですか…やはりLong型countの扱いで怪しいことになっているのでしょうか。
yohhoy

2016/04/30 04:31

結果が不安定になるのは、count変数への排他制御が壊れているからです。 KiyoshiMotokiさん回答へのコメントに理由を記載しています。
raccy

2016/04/30 05:49

> yohhoyさん Javaのドキュメントやいろいろなサイトを見渡しましたが、Objectを継承しているオブジェクト(プリミティブ以外全てになりますけど)という条件しかみつけらませんでした。Longのようなラッパークラスだと排他制御されない場合があるという資料があれば教えてください。 なお、KiyoshiMotokiさんがリンクを貼った資料はオブジェクト再利用によるデッドロックの可能性であって、今回のコードの問題とは無関係かと思われますが、どうなのでしょうか?
yohhoy

2016/05/02 03:44 編集

言葉足らずで申し訳ない。「Longのようなラッパークラスだと排他制御されない」ではなく、「LongのようなAutoboxing対象のクラスでは、raccyさん回答にあるように非常に注意深く使わないと、元質問のように容易に排他制御を壊す。しかし結局は(後述する)問題があるためsynchronized対象には使うべきでない」です。 https://www.jpcert.or.jp/java-rules/lck01-j.html では「一般に、データ型に関係なく、ボクシングした値を含むオブジェクトによるロックは安全ではない。」が該当します。 > synchronizedの中で代入する形であれば、Mutable/Immutableおよびラッパークラスかどうかに関係なく発生する可能性があると思われます。 上記の主張そのものには同意です。Long型をはじめとするラッパークラス固有の問題は、Autoboxing/Unboxingによりプログラマが気付きにくい形で上記のロックオブジェクト再代入が行われてしまう事です。 > なお、private static Long lock = 0L;とロック用にlockを作った場合は問題は起きませんでしたので 厳密には、別の問題がでます。互いに相関の無いクラスが上記ロックオブジェクトを用いた場合、値0を保持するLong型インスタンスがVM内で共有される可能があります。これは良くて意図しない排他制御によるパフォーマンス低下や、別のロックオブジェクトが絡む(=ロックがネスト)とデッドロックに繋がる可能性があります。 インスタンス共有の実例は http://bexhuff.com/2006/11/java-1-5-autoboxing-wackyness を参照ください。
swordone

2016/05/02 01:44

プリミティブlongではsyncronizedが使えなかったので、どうしようか迷った末のLongでした。 改めて考えてみると加算用のstatic syncronizedメソッドを用意して、そこ経由で加算すればよかったですね。
KiyoshiMotoki

2016/05/03 14:29

raccy様 詳細な解説、ありがとうございます。 私の環境でも、ロック専用のオブジェクトを使用して同期化するよう修正したところ、計算が不安定になる現象が再現しなくなることを確認できました。 ご指摘の通り、ロック対象のオブジェクトの参照が変化してしまうために、うまく同期化できていなかったようです。 それにしても、"parallel"は便利そうですね。 Java8は不勉強のため"parallel"の存在を知りませんでしたが、提示いただいた検証結果を見る限り、実行性能も優秀なようです。
guest

0

waitメソッドは1つのスレッドがもう一つのスレッドのからのnotifyメソッドの呼び出しを待機するだけのものなので、
今回のように1つのスレッドが複数のスレッドの終了を待つようなケースには不向きです。
https://docs.oracle.com/javase/jp/6/api/java/lang/Object.html#wait()

恐らく不可能ではないでしょうが、管理用のスレッドを別に用意するなど、複雑な実装になりそうです。


代わりに、CountDownLatchクラスを使用することをお勧めします。

マニュアルに

ほかのスレッドで実行中の操作セットが完了するまで、1 つ以上のスレッドを待機可能にする同期化支援機能です。

とある通り、まさに今回のようなケースに有用なクラスです。
http://docs.oracle.com/javase/jp/7/api/index.html?java/util/concurrent/CountDownLatch.html

CountDownLatchクラスを使うと、ご提示のコードは以下のように書き直すことができます(Java7で動作確認)。

java

1import java.util.ArrayList; 2import java.util.List; 3import java.util.Scanner; 4import java.util.concurrent.CountDownLatch; 5 6public class CountPal extends Thread { 7 8 private static Long count = 0L; 9 10 // リストを同期化する必要はなくなる。 11 private static List<CountPal> threads = new ArrayList<CountPal>(); 12 13 private final long from; 14 private final long until; 15 16 private CountDownLatch doneSignal = null; 17 18 public CountPal(long from, long until) { 19 this.from = from; 20 this.until = until; 21 } 22 23 public void setDoneSignal(CountDownLatch doneSignal) { 24 this.doneSignal = doneSignal; 25 } 26 27 @Override 28 public void run() { 29 if (doneSignal == null) { 30 throw new IllegalStateException("doneSignal is null."); 31 } 32 33 long total = 0L; 34 for (long i = from; i < until; i++) { 35 if (checkPal(i)) { 36 total += i; 37 } 38 } 39 synchronized (count) { 40 count += total; 41 } 42 43 doneSignal.countDown(); 44 } 45 46 private boolean checkPal(long i) { 47 String str = Long.toString(i); 48 int m = 0; 49 int n = str.length() - 1; 50 while (m < n) { 51 if (str.charAt(m) != str.charAt(n)) { 52 return false; 53 } 54 m++; 55 n--; 56 } 57 return true; 58 } 59 60 public static void main(String[] args) { 61 try (Scanner s = new Scanner(System.in)) { 62 long max = s.nextLong(); 63 for (long x = 1; x <= max; x += 10000) { 64 CountPal temp = new CountPal(x, Math.min(x + 10000, max + 1)); 65 threads.add(temp); 66 } 67 68 System.out.println(threads.size()); 69 70 CountDownLatch doneSignal = new CountDownLatch(threads.size()); 71 for (CountPal thread : threads) { 72 thread.setDoneSignal(doneSignal); 73 thread.start(); 74 } 75 76 try { 77 doneSignal.await(); 78 } catch (InterruptedException e) { 79 System.out.println(e); 80 } 81 82 // 変数countは、読み取り時も同期化する必要がある。 83 synchronized (count) { 84 System.out.println(count); 85 } 86 } 87 } 88 89}

ちなみに、変数countは、読み取り時も同期化する必要があります。
http://www.ibm.com/developerworks/jp/java/library/j-praxis/pr50.html
http://d.hatena.ne.jp/j5ik2o/20110220/1298215999

もしくは、AtmicLongクラスに置き換えても良いかもしれません。
http://docs.oracle.com/javase/jp/7/api/index.html?java/util/concurrent/CountDownLatch.html

あと、私の環境(*)だと、ご提示のコードと私のコードはともに変数maxが700000を超えた頃から計算結果が不安定になり、
ときどき異なる値を出力することがありました。

* OS : Mac OSX 10.9 CPU : Intel Core i7 (64bit) メモリ : 8Gb JDK1.7

詳しく調べてはいませんが、生成するスレッドの数が多すぎて、途中で死んでいるものがあるのかもしれません。

訂正

ちなみに、変数countは、読み取り時も同期化する必要があります。

は誤り。

なぜなら、CountDownLatchクラスは以下を保証しているため。

メモリー整合性効果:countDown() を呼び出す前のスレッド内のアクションは、別のスレッド内の対応する await() から正常に復帰したあとのアクションよりも happen-before です。

https://docs.oracle.com/javase/jp/6/api/

"happens-before"については、以下を参照。
https://docs.oracle.com/javase/specs/jls/se6/html/memory.html#17.4.5

投稿2016/04/29 10:31

編集2016/05/07 11:18
KiyoshiMotoki

総合スコア4791

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2016/04/29 10:50

countの読み取りの段階ではすべてのスレッド処理が終わっているはずだと思っているのですが…
KiyoshiMotoki

2016/04/29 10:58

ええと、どの部分に対するご意見でしょうか?
yohhoy

2016/04/29 11:04

synchronized構文の対象にLong型(プリミティブ型のラッパークラス)を指定するのはNGです。正しく排他制御されません。
yohhoy

2016/05/02 03:49 編集

はい。Long型はImmutable Objectであり、Autoboxing/Unboxing対象なので期待通り動作しません。 ときどき異なる値を出力することがあるのは、単に排他制御が壊れているからですね。回答中にも言及がありますが、このケースではAtmicLong利用がベストだと思います。 追記:swordoneさんも指摘する通り、doneSignal.await();後の変数countの読み取りをsynchronizedする必要性はありません。(してはダメということはなく、単にムダなだけです。)該当の読み取り処理のタイミングでは、他スレッドからの書き込み処理が同時に行われることが無いと保証されるためです。
KiyoshiMotoki

2016/05/03 14:52

yohhoy様 ご指摘ありがとうございます。 今回の事象の原因ではなかったようですが、勉強させていただきました。 ただ、 > doneSignal.await();後の変数countの読み取りをsynchronizedする必要性はありません。 > (中略) > 該当の読み取り処理のタイミングでは、他スレッドからの書き込み処理が同時に行われることが無いと保証されるためです。 につきましては、 「メインスレッドが(メインメモリからではなく)キャッシュメモリ上の値を読んでしまう可能性があるために」 同期化する必要がある、と指摘させていただきました。 しかし、私もだんだん自信がなくなってきました(w) メインスレッドは常にメインメモリからのみ値を読み取る、という確証が取れれば、おっしゃる通りご指摘の部分は同期化する必要はありませんね。
KiyoshiMotoki

2016/05/07 11:12 編集

swordone様、yohhoy様 > doneSignal.await();後の変数countの読み取りをsynchronizedする必要性はありません。 についてstackoverflowに質問してみたところ、お二人のご指摘の通り 「必要ない」 という回答を得ることができました。 http://stackoverflow.com/questions/37067254/is-this-synchronized-block-need 理由は"happens-before"という言語仕様によるもので、 "synchronized"や"Thread.join()"で同期化されたコードブロックは、その実行順序と、先に実行された処理の結果が後続のコードブロックから見えることが保証されているためだそうです。 http://docs.oracle.com/javase/specs/jls/se6/html/memory.html#17.4.5 また、CountDownLatchクラスのドキュメントにも、以下のように記載がありました。 https://docs.oracle.com/javase/jp/6/api/ > メモリー整合性効果:countDown() を呼び出す前のスレッド内のアクションは、別のスレッド内の対応する await() から正常に復帰したあとのアクションよりも happen-before です。 勉強させていただき、ありがとうございます。
guest

0

「どう修正すべきか」は他の方の回答で触れられていますので、そちらに譲ります。

調べるとwait()notifyAll()を使うらしいことはわかったのですが、何に対してこのメソッドを使えばいいのかがわかりません。

(あくまで私見ですが)java.lang.Objectクラスのwait(),notify(),notifyAll()メソッドは、その動作仕様を多くのJavaプログラマに正しく理解されておらず、ほとんどのケースで間違って使われる機能だと思います。

Java 1.0時代から存在する機能ですが、非常に原始的なスレッド間同期機構のため、可能な限り利用を避けることをおすすめします。Java 1.5以降はjava.util.concurrentパッケージにスレッド間同期のツール群が導入されたため、そちらを探せば大抵の欲しい機能は提供されると思います。

Webでよく見かける、下記のようなwait()コード例は完全に誤っています。

java

1try { 2 wait(); 3} catch (InterruptException e) {}

少なくとも「スプリアス・ウェイクアップ(Spurious Wakeup)」に言及していない解説は、全て誤っていると解釈して差し支えありません。正しい使い方は下記記事に譲ります。

投稿2016/05/02 04:04

yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2016/05/02 04:07

確かにwait()はwhileに囲まれている例が多かったです。ただその説明がnotifyAllされた時に複数のスレッドがwaitしている可能性があるから、という説明でしたが…
yohhoy

2016/05/02 06:31

「notifyAllされた時に複数のスレッドがwaitしている可能性があるから」も誤りではありませんが、スプリアス・ウェイクアップは公式ドキュメントでも説明されているメソッド動作仕様ですね。 https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Object.html#wait-- > (略)割り込みやスプリアス・ウェイクアップが発生する可能性があるので、このメソッドは常にループで使用される必要があります。
guest

0

全てのスレッド終了を待機したいなら、全てのスレッドにjoin()するだけで良いのでは?

投稿2016/04/28 17:33

Stripe

総合スコア2183

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2016/04/28 17:48

スレッドごとにjoin()したら、そのスレッドが終わるのを待たないといけないので、複数のスレッドを同時進行させることが出来なくなります。
Stripe

2016/04/28 17:51

ん? 全てのスレッドを同時進行させた後に、全てのスレッドに対してjoin()するんですよ?
KiyoshiMotoki

2016/04/29 10:43 編集

横から失礼します。 > 全てのスレッドを同時進行させた後に、全てのスレッドに対してjoin()するんですよ? 複数のスレッドに対してjoinすることはできません。 なぜなら、1つのスレッドに"join"した時点で、そのスレッドは相手のスレッドが終了するまでブロックされてしまうからです。 https://docs.oracle.com/javase/jp/6/api/java/lang/Thread.html#join()
swordone

2016/04/29 10:36

スレッドリストの末尾に対してjoin()することで待つことはできそうです。 一つ参考にさせていただきます。
KiyoshiMotoki

2016/04/29 10:44

> スレッドリストの末尾に対してjoin()することで待つことはできそうです。 うーむ、 計算が終了する順序が逆転しないことを保証できれば、これでも行けそうですが、、
swordone

2016/04/29 10:48

whileループの中でjoin()するので大丈夫かと。 whileに入る時点ではスレッド生成は終わってますし、末尾スレッドが先に終了してもwhileに捕まってまたjoin()できるので。 ただjoin()するためにスレッドをget()してからjoin()するまでの間にそのスレッドが終わるとまずいのか…
KiyoshiMotoki

2016/04/29 11:02 編集

> whileループの中でjoin()するので大丈夫かと。 なるほど、そう言うことですね。 > ただjoin()するためにスレッドをget()してからjoin()するまでの間にそのスレッドが終わるとまずいのか… 以下のコードで簡単に検証してみた限りでは、問題なさそうですね。 終了済みのスレッドや開始していないスレッドに対してjoinメソッドを呼び出しても、ブロックされず直ちに次の処理に移るだけのようです。 public class Main { public static void main(String[] args) throws InterruptedException { Thread worker = new Thread() { @Override public void run() { try { Thread.sleep(1000); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } System.out.println("done."); } }; worker.join(); System.out.println("First."); worker.start(); worker.join(); System.out.println("Second."); worker.join(); System.out.println("Third."); } }
Stripe

2016/04/29 12:13

単純な話のはずなんですが、、、 for(Thread thread : threads) { thread.start(); } for(Thread thread : threads) { thread.join(); }
swordone

2016/04/29 12:21

> 終了済みのスレッドや開始していないスレッドに対してjoinメソッドを呼び出しても、ブロックされず直ちに次の処理に移るだけのようです。 この特徴があるなら、全スレッドにjoin()でも可能なんですね。納得しました。
KiyoshiMotoki

2016/04/29 12:32

Stripe様 コードをご提示いただいき、ありがとうございます。 ようやく意図を理解できました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.51%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問