synchronizedを元のプログラムに入れたい

Question

前提・実現したいこと

下のプログラムはタートルが衝突を検知するとその場で止まるというプログラムであるが、このプログラムは実行しているとすり抜けてしまう。
そこでsynchronizedを用いてプログラムを正常に動くようにしたい。

該当のソースコード

public class TurtleCollision extends TurtleFrame {
	public void start() {
		Turtle m1 = new Turtle(50, 200, 90), m2 = new Turtle(350, 200, 270);
		this.add(m1);
		m1.speed((int)(Math.random() * 20.0) + 10);
		this.add(m2); m2.tColor = Color.DEEPPINK;
		m2.speed((int)(Math.random() * 20.0) + 10);
		ExecutorService executor = Executors.newCachedThreadPool();
		final double step = 10.0; // 步幅
		executor.execute(()-> {
			while (m1.getX() < 400){
				if (0 == Double.compare(m1.getX() + step, m2.getX())) { // 衝突チェック
					System.out.println("m1:collision at " + m1.getX());
					break;
				}
				m1.fd(step); // 1步進む
			}
		});
		executor.execute(()-> {
			while (m2.getX() > 0){
				if (0 == Double.compare(m1.getX(), m2.getX() - step)) { // 衝突チェック
					System.out.println("m2:collision at " + m2.getX());
					break;
				}
				m2.fd(step); // 1步進む
			}
		});
	}
public static void main(String[] args) {
		new TurtleCollision().start();
	}
}

試したこと

synchronized void startSynchro()としてstart内のプログラムをコピーし、そこにsynchronizedを挿入して実行したが、うまくいかなかった。

package prog2;
import tg.*;
import java.util.*;
import java.util.concurrent.*;
import javafx.scene.paint.Color;
public class TurtleCollision extends TurtleFrame {
	public void start() {
		Turtle m1 = new Turtle(50, 200, 90), m2 = new Turtle(350, 200, 270);
		this.add(m1);
		m1.speed((int)(Math.random() * 20.0) + 10);
		this.add(m2); m2.tColor = Color.DEEPPINK;
		m2.speed((int)(Math.random() * 20.0) + 10);
		ExecutorService executor = Executors.newCachedThreadPool();
		final double step = 10.0; // 步幅
		executor.execute(()-> {
			while (m1.getX() < 400){
				if (0 == Double.compare(m1.getX() + step, m2.getX())) { // 衝突チェック
					System.out.println("m1:collision at " + m1.getX());
					break;
				}
				m1.fd(step); // 1步進む
			}
		});
		executor.execute(()-> {
			while (m2.getX() > 0){
				if (0 == Double.compare(m1.getX(), m2.getX() - step)) { // 衝突チェック
					System.out.println("m2:collision at " + m2.getX());
					break;
				}
				m2.fd(step); // 1步進む
			}
		});
	}
	synchronized void startSynchro(){
		Turtle m1 = new Turtle(50, 200, 90), m2 = new Turtle(350, 200, 270);
		this.add(m1);
		m1.speed((int)(Math.random() * 20.0) + 10);
		this.add(m2); m2.tColor = Color.DEEPPINK;
		m2.speed((int)(Math.random() * 20.0) + 10);
		ExecutorService executor = Executors.newCachedThreadPool();
		final double step = 10.0; // 步幅
		synchronized(executor) {
			executor.execute(()-> {
				while (m1.getX() < 400){
					if (0 == Double.compare(m1.getX() + step, m2.getX())) { // 衝突チェック
						System.out.println("m1:collision at " + m1.getX());
						break;
					}
					m1.fd(step); // 1步進む
				}
			});
			executor.execute(()-> {
				while (m2.getX() > 0){
					if (0 == Double.compare(m1.getX(), m2.getX() - step)) { // 衝突チェック
						System.out.println("m2:collision at " + m2.getX());
						break;
					}
					m2.fd(step); // 1步進む
				}
			});
		}
	}
public static void main(String[] args) {
		new TurtleCollision().startSynchro();
	}
}

このようにいれ、wait()なども試しましたが、一向にうまくいきません。どのようにsynchronizedを挿入すればいいのでしょうか

Comments

[dodox86]

衝突を正しく検知したいためにsynchronizedを付けたいとのことですが、それで解決できる見込みがあるのでしょうか。

[xebme]

教材は『すべての人のためのJavaプログラミング』ですね。JavaFxが必要ですね。
https://www.i.h.kyoto-u.ac.jp/users/tsuiki/javaEveryone3/download.html
tgパッケージをコピーすれば動かせるのですが。

[xebme]

m1、m2が共有できるオブジェクトをsynchronizedしてください。<-- それほど容易ではないことがわかりました。衝突を判定するときに、m1,m2の内部状態がメモリに書き戻されていなければならないからです。synchronizedを使えば、L2キャッシュにデータがあったとしてもメモリ書き戻しが保証されます。

Answer 1

すれ違いが起きる状況と解決方法

Turtleが1ステップ実行したあとに必ず衝突判定が行われるなら、すれ違いは起きません。衝突した直後の状況を考えてみます。

• m1が1ステップ前進 (衝突)
• m2が1ステップ前進 (すれ違い)
• m1またはm2が衝突を判定 (衝突ではない)

2つのスレッドは自由に動けるのでこれが起こります。そこで、衝突判定と前進を分割不可分なセットにします。セットを排他的に実行できるよう、synchronizedを使います。synchronized(<オブジェクト>) のオブジェクトは2つのスレッドが共有するオブジェクトです。

  synchronized(<共有オブジェクト>) {
    if (衝突) メッセージを表示して終了;
    前進;
  }

メモリの同期

マルチコア・プラットフォームで、スレッドが別々のコアで実行すると、共有オブジェクトの更新結果がキャッシュに残り、メモリに書き戻されない状況が生まれます。他のコアで実行するスレッドはメモリの更新前の値を見ることになります。

m1、m2の座標は、前進によって更新されますが、2つのスレッドが衝突判定できるには、m1、m2の値が正しくメモリに書き戻されなければなりません。synchronized によってメモリへの書き戻しが保証されます。(vlatileは1変数のみアトミックに書き戻す)

synchronized/volatileのコストは高くつきます。

synchronizedを使わない解法

synchronizedを使わず、失敗させることで結果的に同期する方法があります。AtomicIntegerを使う解法を紹介します。

      // stepに換算したm2とm1の距離
      final AtomicInteger stepsRemained = new AtomicInteger((int)((m2.getX() - m1.getX()) / step));
      
      executor.execute(()-> {
         while (stepsRemained.updateAndGet(v -> (v == 0) ? 0 : --v ) > 0) m1.fd(step); // 1步進む
         System.out.println("m1:collision at " + m1.getX());
      });
      
      executor.execute(()-> {
         while (stepsRemained.updateAndGet(v -> (v == 0) ? 0 : --v ) > 0) m2.fd(step); // 1步進む
         System.out.println("m2:collision at " + m2.getX());
      });

m1 、m2の2つの状態を管理するのは難しい。Turtleの距離だけをみるよう問題を単純化しました。