非同期処理 wait,notifyAllの使い方
解決済
回答 4
投稿
- 評価
- クリップ 1
- VIEW 4,528
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class CountPal extends Thread{
private static Long count = 0L;
private static List<CountPal> threads = Collections.synchronizedList(new LinkedList<>());
private final long from;
private final long until;
public CountPal(long from, long until) {
this.from = from;
this.until = until;
}
@Override
public void run() {
long total = 0L;
for(long i = from; i < until; i++){
if(checkPal(i)){
total += i;
}
}
synchronized (count) {
count += total;
}
threads.remove(this);
}
private boolean checkPal(long i){
String str = Long.toString(i);
int m = 0;
int n = str.length() - 1;
while(m < n){
if(str.charAt(m) != str.charAt(n)){
return false;
}
m++;
n--;
}
return true;
}
public static void main(String[] args) {
try (Scanner s = new Scanner(System.in)) {
long max = s.nextLong();
for(long x = 1; x <= max; x += 10000){
CountPal temp = new CountPal(x, Math.min(x + 10000, max + 1));
threads.add(temp);
temp.start();
}
// すべてのスレッドが終了するまで待つ
while(threads.size() != 0){
try {
System.out.println(threads.size()); // 現在のスレッド数ダンプ
Thread.sleep(1000);
} catch (InterruptedException e) { }
}
System.out.println(count);
}
}
}
ある数を入力し、その数以下の回文数(121のように左右どちらから読んでも同じになる数)の合計を求めるプログラムです(本題のプログラム問題を解くために作成した、時間はかかるが確実に正しい答えを出すための副産物的なプログラムです)。
適当な数(10000)で分割し、スレッドを生成して手分けしてカウントするようなプログラムなのですが、「すべてのスレッドが終了するまで待つ」という部分が上手く書けません。
現状、生成したThreadをListに詰め、終了する際にThreadがListから自身を取り除くようにし、ListのThreadが0になるまで待つ、という構成なのですが、0になってからも1秒未満とはいえ余計に待つことになります。
調べるとwait()やnotifyAll()を使うらしいことはわかったのですが、何に対してこのメソッドを使えばいいのかがわかりません。
また、Listを使う以外の方法がもしありましたら教えてください。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+3
発想を変えて、Threadを使わず、Streamでparallelにしちゃうのはどうでしょうか?
import java.util.Scanner;
import java.util.stream.LongStream;
public class CountPal3 extends Thread{
private static boolean checkPal(long i){
String str = Long.toString(i);
int m = 0;
int n = str.length() - 1;
while(m < n){
if(str.charAt(m) != str.charAt(n)){
return false;
}
m++;
n--;
}
return true;
}
public static void main(String[] args) {
try (Scanner s = new Scanner(System.in)) {
long max = s.nextLong();
long count = LongStream
.rangeClosed(0, (max - 1) / 10000).parallel()
.map(i -> i * 10000 + 1)
.map(x -> LongStream.range(x, Math.min(x + 10000, max + 1))
.filter(CountPal3::checkPal).sum()).sum();
System.out.println(count);
}
}
}
実行結果比較
$ 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さんのコードが不安定になる理由(たぶん、でも自信無し)
synchronized (count) {
count += total;
}
原因は上の部分ですが、count
がLongだからではなく、count
が新しいオブジェクトに置き換わっているからだと思われます。上のコードは、オートボクシングせずに、かつ、+=
の糖衣構文も分解すると下記になります。
synchronized (count) {
count = new Long(count.longValue() + total)
}
そう、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およびラッパークラスかどうかに関係なく発生する可能性があると思われます。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
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で動作確認)。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.CountDownLatch;
public class CountPal extends Thread {
private static Long count = 0L;
// リストを同期化する必要はなくなる。
private static List<CountPal> threads = new ArrayList<CountPal>();
private final long from;
private final long until;
private CountDownLatch doneSignal = null;
public CountPal(long from, long until) {
this.from = from;
this.until = until;
}
public void setDoneSignal(CountDownLatch doneSignal) {
this.doneSignal = doneSignal;
}
@Override
public void run() {
if (doneSignal == null) {
throw new IllegalStateException("doneSignal is null.");
}
long total = 0L;
for (long i = from; i < until; i++) {
if (checkPal(i)) {
total += i;
}
}
synchronized (count) {
count += total;
}
doneSignal.countDown();
}
private boolean checkPal(long i) {
String str = Long.toString(i);
int m = 0;
int n = str.length() - 1;
while (m < n) {
if (str.charAt(m) != str.charAt(n)) {
return false;
}
m++;
n--;
}
return true;
}
public static void main(String[] args) {
try (Scanner s = new Scanner(System.in)) {
long max = s.nextLong();
for (long x = 1; x <= max; x += 10000) {
CountPal temp = new CountPal(x, Math.min(x + 10000, max + 1));
threads.add(temp);
}
System.out.println(threads.size());
CountDownLatch doneSignal = new CountDownLatch(threads.size());
for (CountPal thread : threads) {
thread.setDoneSignal(doneSignal);
thread.start();
}
try {
doneSignal.await();
} catch (InterruptedException e) {
System.out.println(e);
}
// 変数countは、読み取り時も同期化する必要がある。
synchronized (count) {
System.out.println(count);
}
}
}
}
ちなみに、変数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
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+1
全てのスレッド終了を待機したいなら、全てのスレッドにjoin()するだけで良いのでは?
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+1
「どう修正すべきか」は他の方の回答で触れられていますので、そちらに譲ります。
調べると
wait()
やnotifyAll()
を使うらしいことはわかったのですが、何に対してこのメソッドを使えばいいのかがわかりません。
(あくまで私見ですが)java.lang.Object
クラスのwait()
,notify()
,notifyAll()
メソッドは、その動作仕様を多くのJavaプログラマに正しく理解されておらず、ほとんどのケースで間違って使われる機能だと思います。
Java 1.0時代から存在する機能ですが、非常に原始的なスレッド間同期機構のため、可能な限り利用を避けることをおすすめします。Java 1.5以降はjava.util.concurrent
パッケージにスレッド間同期のツール群が導入されたため、そちらを探せば大抵の欲しい機能は提供されると思います。
Webでよく見かける、下記のようなwait()
コード例は完全に誤っています。
try {
wait();
} catch (InterruptException e) {}
少なくとも「スプリアス・ウェイクアップ(Spurious Wakeup)」に言及していない解説は、全て誤っていると解釈して差し支えありません。正しい使い方は下記記事に譲ります。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 88.32%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2016/04/29 21:11 編集
ありがとうございます。
オリジナルのコードでも違う値になることがあるのですか…やはりLong型countの扱いで怪しいことになっているのでしょうか。
2016/04/30 13:31
2016/04/30 14:49
Javaのドキュメントやいろいろなサイトを見渡しましたが、Objectを継承しているオブジェクト(プリミティブ以外全てになりますけど)という条件しかみつけらませんでした。Longのようなラッパークラスだと排他制御されない場合があるという資料があれば教えてください。
なお、KiyoshiMotokiさんがリンクを貼った資料はオブジェクト再利用によるデッドロックの可能性であって、今回のコードの問題とは無関係かと思われますが、どうなのでしょうか?
2016/05/02 10:39 編集
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 を参照ください。
2016/05/02 10:44
改めて考えてみると加算用のstatic syncronizedメソッドを用意して、そこ経由で加算すればよかったですね。
2016/05/03 23:29
詳細な解説、ありがとうございます。
私の環境でも、ロック専用のオブジェクトを使用して同期化するよう修正したところ、計算が不安定になる現象が再現しなくなることを確認できました。
ご指摘の通り、ロック対象のオブジェクトの参照が変化してしまうために、うまく同期化できていなかったようです。
それにしても、"parallel"は便利そうですね。
Java8は不勉強のため"parallel"の存在を知りませんでしたが、提示いただいた検証結果を見る限り、実行性能も優秀なようです。