マルチスレッドプログラミングでsynchronizedメソッドが期待通りに動作しない

Question

前提・実現したいこと

マルチスレッドプログラミングの勉強をしておりますが、以下のコードで競合が発生する理由がわかりません。

発生している問題

後述のコードのMutexクラスのlock()で

 if (isLock)

だと競合が発生します（Gateクラスのcheck()で「＊＊＊＊＊ BROKEN ＊＊＊＊＊」を表示します）。
しかし、上述のif文を以下のようにwhile文にすると、競合が発生しません。

 while (isLock)

以下の理由からif文でも競合が起きないと考えていましたが、実際は競合が起きています。

• unlock()でnotify()メソッドを使って、1スレッドのみウェイトセットから出している
• lock()はsynchronizedをつけているためため、同時に1つのスレッドしか実行できない

　　→unlock()のnotify()によって起こされたスレッドか、新しくlock()を呼んだスレッドのみ

該当のソースコード

public class Main {
    public static void main(String[] args) {
        System.out.println("Testing Gate, hit CTRL+C to exit.");
        Gate gate = new Gate();
        new UserThread(gate, "Alice", "Alaska").start();
        new UserThread(gate, "Bobby", "Brazil").start();
        new UserThread(gate, "Chris", "Canada").start();
    }
}

public class UserThread extends Thread {
    private final Gate gate;
    private final String myname;
    private final String myaddress;

    public UserThread(Gate gate, String myname, String myaddress) {
        this.gate = gate;
        this.myname = myname;
        this.myaddress = myaddress;
    }

    @Override
    public void run() {
        System.out.println(myname + " BEGIN");
        while (true) {
            gate.pass(myname, myaddress);
        }
    }
}

public class Gate {
    private int counter = 0;
    private String name = "Nobody";
    private String address = "Nowhere";
    private final Mutex mutex = new Mutex();

    public void pass(String name, String address) {
        mutex.lock();
        try {
            counter++;
            this.name = name;
            this.address = address;
            check();
        } finally {
            mutex.unlock();
        }
    }

    @Override
    public String toString() {
        String s = null;

        mutex.lock();
        try {
            s = "No." + counter + ": " + name + ", " + address;
        } finally {
            mutex.unlock();
        }
        return s;
    }

    private void check() {
        if (name.charAt(0) != address.charAt(0)) {
            System.out.println("***** BROKEN ***** " + toString());
        }
    }
}

public class Mutex {
    private boolean isLock;

    public synchronized void lock() {
        try {
            // 誰かがロック取得済の場合はウェイトセットに入れる
            // while (isLock) {
            if (isLock) {
                wait();
                System.out.println("isLock=" + isLock);
            }

            isLock = true;
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public synchronized void unlock() {
        // ウェイトセットの中から1スレッドのみ出す
        notify();
        isLock = false;
    }
}

試したこと

jdbでMutexクラスの「System.out.println("isLock=" + isLock);」の行にブレークポイントをはり、他のスレッドの様子を確認したところ、lock()内に2つのスレッドがいました（以下のjdbのログのスレッド0x1beとスレッド0x1bf）。
スレッド0x1beはlock()の「if (isLock) {」の部分を、スレッド0x1bfはlock()の「System.out.println("isLock=" + isLock);」の部分を実行しているようです。

$ jdb Main
jdbの初期化中...
> stop in Mutex:10
遅延したブレークポイントMutex:10。
クラスがロードされた後に設定されます。
> run

Thread-0[1] threads
グループsystem:
  (java.lang.ref.Reference$ReferenceHandler)0x173 Reference Handlerは実行中です
  (java.lang.ref.Finalizer$FinalizerThread)0x174  Finalizer        は条件を待機中です
  (java.lang.Thread)0x175                         Signal Dispatcherは実行中です
グループmain:
  (UserThread)0x1be                               Thread-0         はモニター内で待機中です
  (UserThread)0x1bf                               Thread-1         は実行中です(ブレークポイント)
  (UserThread)0x1c1                               Thread-2         はモニター内で待機中です
  (java.lang.Thread)0x1c5                         DestroyJavaVM    は実行中です
グループInnocuousThreadGroup:
  (jdk.internal.misc.InnocuousThread)0x1a2        Common-Cleaner   は条件を待機中です
Thread-0[1] thread 0x1be
Thread-0[1] where
  [1] Mutex.lock (Mutex.java:8)
  [2] Gate.pass (Gate.java:9)
  [3] UserThread.run (UserThread.java:16)
Thread-0[1] thread 0x1bf
Thread-1[1] where
  [1] Mutex.lock (Mutex.java:10)
  [2] Gate.pass (Gate.java:9)
  [3] UserThread.run (UserThread.java:16)
Thread-1[1]

~~
lock()の中に2つスレッドがいて、正常にロックを実装できていないことが競合が起きている原因だと思いますが、なぜsynchronizedメソッドの中に同時に複数のスレッドが入れるのかがわかりません。
新しくlock()を呼んだスレッドはもちろん、notify()によってウェイトセットから出てきたスレッドも、synchronizedによるロックの獲得待ちをするため、lock()には同時に1つのスレッドしか入れない認識です。
~~

2020.10.12追加

以下の記事は、Mutexクラスのlock()のif文をwhile文に修正した状態でプログラムを実行した場合のものです。
if文だと、そもそも競合状態になる場合があることがわかりました（quickquipさんの回答参照）。

jdbの表示の読み方が間違っていたようです。jdbのlockコマンドでロックに関する情報を確認したところ、lock()の中を実行中のスレッドは1つしかありませんでした。ロック獲得待ちをしているスレッドでwhereコマンドを実行した時に表示される行番号は、実行しようとしているメソッドの中でjdbがブレークポイントをはれる最初の行番号を表示するようです（「try {」やコメント行にはブレークポイントが設定できない。そのため、その次の行の「if (isLock) {」の行番号が表示される）。

Thread-0[1] threads
グループsystem:
  (java.lang.ref.Reference$ReferenceHandler)0x173 Reference Handlerは実行中です
  (java.lang.ref.Finalizer$FinalizerThread)0x174  Finalizer        は条件を待機中です
  (java.lang.Thread)0x175                         Signal Dispatcherは実行中です
グループmain:
  (UserThread)0x1be                               Thread-0         は実行中です(ブレークポイント)
  (UserThread)0x1bf                               Thread-1         はモニター内で待機中です
  (UserThread)0x1c1                               Thread-2         はモニター内で待機中です
  (java.lang.Thread)0x1c6                         DestroyJavaVM    は実行中です
グループInnocuousThreadGroup:
  (jdk.internal.misc.InnocuousThread)0x1a2        Common-Cleaner   は条件を待機中です
Thread-0[1] where
  [1] Mutex.lock (Mutex.java:10)
  [2] Gate.pass (Gate.java:9)
  [3] UserThread.run (UserThread.java:16)
Thread-0[1] thread 0x1bf
Thread-1[1] where
  [1] Mutex.lock (Mutex.java:8)
  [2] Gate.pass (Gate.java:9)
  [3] UserThread.run (UserThread.java:16)
Thread-1[1] thread 0x1c1
Thread-2[1] where
  [1] Mutex.lock (Mutex.java:8)
  [2] Gate.pass (Gate.java:9)
  [3] UserThread.run (UserThread.java:16)
  
// lockコマンドでthis（lock()がロックする時に使うインスタンス）のロックの情報を表示してやると、
// 実行中のスレッド（ロックを獲得しているスレッド）はThread-0のみで、Thread-1とThread-2は
// ロック獲得待ちであることがわかる。
Thread-2[1] lock this
com.sun.tools.example.debug.expr.ParseException: Unable to complete expression. Thread not suspended for method invoke
  所有者: Thread-0、エントリ数: 1
 スレッドを待機中: Thread-1
 スレッドを待機中: Thread-2
Thread-2[1]

補足情報（FW/ツールのバージョンなど）

• OS

macOS Catalina バージョン10.15.7

• Javaのバージョン

$ java -version
openjdk version "11.0.8" 2020-07-14
OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.8+10)
OpenJDK 64-Bit Server VM AdoptOpenJDK (build 11.0.8+10, mixed mode)

Comments

[xebme]

OSは何ですか。Linuxはsuprious wake upが起こりやすいようです。
Gateのpass()をsynchronizedすればMutexが不要になり問題解決すると思いますが質問の答えではありません。

[xebme]

頻度から考えてtoString()のmutex再入の問題ですかね。<-- これは別の問題。Java API に記述されているsuprious wake upが最も近いと思います。

[ichiro200555]

ありがとうございます。

> OSは何ですか。Linuxはsuprious wake upが起こりやすいようです。
OSはmacOS Catalina バージョン10.15.7です。
suprious wake upというワードは初めて聞きました。自分なりに調べてみます。

> Gateのpass()をsynchronizedすればMutexが不要になり問題解決すると思いますが質問の答えではありません。
おっしゃる通りpass()をsynchronizedすれば問題解決するのですが、今回は簡単なMutexクラスを自作するというテーマで学習しております。

[ichiro200555]

suprious wake upで間違いなさそうです。

notify()やnotifyAll()を呼んでいなくても、ウェイトセットからスレッドが出てしまう場合があるんですね（※1）。大変勉強になりました。
xebmeさんにベストアンサーをつけたいので、suprious wake upの件を回答として書いていただけますでしょうか。

※1
https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/lang/Object.html#wait()
https://www.jpcert.or.jp/java-rules/thi03-j.html
http://blogs.wankuma.com/nagise/archive/2007/08/22/91406.aspx

[dodox86]

違うスレッドであっても、同じMutexクラスのオブジェクトを参照していて、その同じオブジェクトでsynchronizedメソッドのlock()を実行しているのだけれども、その中でthisなwait()を実行することによって別のスレッドからsynchronizedなlock()に入れてしまう、と言うことではないのでしょうか
（そのことを指しているのでしょうか）

ちなみにWindows 10でOpenJDK 14.0.1(64bit)でも再現しました。

関連質問
[Java: synchronizedの実装 - teratail#84457](https://teratail.com/questions/84457)
の質問回答および、文中でリンクされている記事の内容

[ichiro200555]

先のコメントで「suprious wake upで間違いなさそうです」と書きましたが先走りました。
確かにnotify()やnotifyAll()を呼ばなくてもウェイトセットからスレッドが出てしまう場合があることはわかりましたが、synchronizedメソッドの中に同時に複数のスレッドが入れる件はまだ未解決でした。

[ichiro200555]

dodox86さん、どうもありがとうございます。

wait()を実行したスレッドはウェイトセットに入りロックを解放する。よって、別のスレッドがlock()に入れるようになるということは理解しています。

lock()の中でwait()を実行中以外のスレッドが複数います。この部分がわかりません。

xebmeさんのアドバイスにより、wait()はwhileループで囲まなければならないことがわかったため、以下の修正したMutexクラスを使って質問事項のソースコードをjdb上で動かしました。

public class Mutex {
　private boolean isLock;

　　public synchronized void lock() {
　　　try {
　　　　while (isLock) {
　　　　　wait();
　　　　}

　　　　isLock = true;
　　　} catch (InterruptedException e) {
　　　　throw new RuntimeException(e);
　　　}
　}

　public synchronized void unlock() {
　　notify();
　　isLock = false;
　}
}

$ jdb Main
jdbの初期化中...
> stop in Mutex:10
遅延したブレークポイントMutex:10。
クラスがロードされた後に設定されます。
> run

Thread-0[1] threads
グループsystem:
　(java.lang.ref.Reference$ReferenceHandler)0x173 Reference Handlerは実行中です
　(java.lang.ref.Finalizer$FinalizerThread)0x174 Finalizer は条件を待機中です
　(java.lang.Thread)0x175 Signal Dispatcherは実行中です
グループmain:
　(UserThread)0x1be Thread-0 は実行中です(ブレークポイント)
　(UserThread)0x1bf Thread-1 はモニター内で待機中です
　(UserThread)0x1c0 Thread-2 はモニター内で待機中です
　(java.lang.Thread)0x1c5 DestroyJavaVM は実行中です
グループInnocuousThreadGroup:
　(jdk.internal.misc.InnocuousThread)0x1a2 Common-Cleaner は条件を待機中です
Thread-0[1] thread 0x1be
Thread-0[1] where
　[1] Mutex.lock (Mutex.java:10)
　[2] Gate.pass (Gate.java:9)
　[3] UserThread.run (UserThread.java:16)
Thread-0[1] thread 0x1bf
Thread-1[1] where
　[1] Mutex.lock (Mutex.java:6)
　[2] Gate.pass (Gate.java:9)
　[3] UserThread.run (UserThread.java:16)
Thread-1[1] thread 0x1c0
Thread-2[1] where
　[1] java.lang.Object.wait (nativeメソッド)
　[2] java.lang.Object.wait (Object.java:328)
　[3] Mutex.lock (Mutex.java:7)
　[4] Gate.pass (Gate.java:9)
　[5] UserThread.run (UserThread.java:16)

そうすると、スレッドが3ついることがわかりました（(UserThread)0x1be、(UserThread)0x1bf、(UserThread)0x1c0）。
(UserThread)0x1beのスレッドは、Mutexクラスの「isLock = true;」を実行中のようです。
(UserThread)0x1bfのスレッドは、Mutexクラスの「while (isLock) {」を実行中のようです。
(UserThread)0x1c0のスレッドは、Mutexクラスの「wait();」を実行中のようです。
よって、(UserThread)0x1beと(UserThread)0x1bfのスレッドがsynchronizedなlock()の中で実行中の状態になっています。ここがわかりません。lock()にはsynchronizedをつけているため、wait()実行中以外のスレッドがなぜ同時に複数存在できるのかがわかりません。

[dodox86]

> wait()実行中以外のスレッドがなぜ同時に複数存在できるのかがわかりません。

this.wait()を実行することで、ロックを解放します。ここまでは質問者さんも同じ理解ですね。更に進めて、synchronizedメソッドはインスタンスメソッドをsynchronizedブロックで囲んだようなもので、synchronizedブロックはすべてのベースクラスであるObjectクラスの.lock()、すなわちそのインスタンスlock()に相当すると私は理解してます。つまり、現時点のコードについては、this.wait()を実行するとsynchronizedメソッドのロックが解除されるので、別スレッドがそのメソッドに入ってきてしまう、と言う現象だと踏んでいます。もちろん、当方に間違いがあればご指摘ください。

[dodox86]

ああ、すみません、修正されたコメント中のコードをちゃんと読み込んでいませんでした。しかしながら、
今現在、isLockがtrueだとして
1. Mutex.lock()でisLock=trueなのでwait()実行
2. スレッド切り替えでMutex.unlock()でnotify()
3. notify()されたので、wait()をしていたスレッドが再び立ち上がる。しかしまだisLockはtrueのまま。そのままwait()を実行してしまう。
4. notify()したスレッドに再度切り替わって、isLock=false
なんて動きになったら、やはり再入できてしまうのでは？、なんて思いました。当方のコードの読み取り検討不足かもしれませんが。

[ichiro200555]

dodox86さん、どうもありがとうございます。

> 3. notify()されたので、wait()をしていたスレッドが再び立ち上がる。しかしまだisLockはtrueのまま。そのままwait()を実行してしまう。
結城浩の『Java言語で学ぶデザインパターン 入門 【マルチスレッド編】』によれば、

・notify()で起こされたスレッドは、実行を再開するためにもう一度ロックを取得しなければならない
・notify()したスレッドは、notify()した瞬間にロックを解除するわけではない。ロックを解除するためにはsynchronizedメソッド（またはブロック）を抜ける必要がある

ため、私のコードで言えばunlock()を抜けるまではロックが解放されません。よって、3.の事象は発生しないはずです。

[dodox86]

@ichiro200555さん
フォローの情報、どうもありがとうございます。

> notify()したスレッドは、notify()した瞬間にロックを解除するわけではない。ロックを解除するためにはsynchronizedメソッドかsynchronizedブロックを抜ける必要がある
なるほど、その点は意識していませんでした。では私の上記コメントでの指摘はあたりませんね。失礼しました。

[ichiro200555]

@dodox86さん
いえいえ、とんでもないです。コメントどうもありがとうございました。

[dodox86]

追加情報ですが、当初の質問文中のコードをWindows 10のWSL(Ubuntu 18.04.4)上のOpenJDK "1.0.0_252" 64bitで実行すると、問題は再現しませんでした。（"BROKEN..."表示されず）ご参考まで。

Answer 1

Alice,Bobby,Chrisがlock呼び出しでオブジェクトロック待ちに→Aliceがオブジェクトロック取得してlockを実行→Aliceがlockを終了→Bobbyがオブジェクトロック取得してlockを実行waitに/Aliceがlockの後続処理を終えてunclockを呼び出しオブジェクトロック待ちに→Aliceがオブジェクトロック取得してunlockを実行→notifyでBobbyがオブジェクトロック待ちに→Aliceがunlockを終了→Chrisがオブジェクトロック取得してlockを実行
でBobbyとChrisが同時実行している状態になりますね。

Comments

[xebme]

これが起きるのは次の場合でしょう。
・Aliceがnotify()する前にChrisがlock()を呼びsynchronizedで待っている
・Aliceがnotify()してBobbyがwaitセットから外れるがChrisの後で待つ
・Aliceがunlock()から抜ける
たぶんこちらの方が高頻度で発生するでしょう。理由として適切ですね。
spurious wakeupsは２番目の理由です。
https://stackoverflow.com/questions/1038007/why-should-wait-always-be-called-inside-a-loop

[ichiro200555]

quickquipさん、xebmeさん、どうもありがとうございます。

理解できました。つまり、

ウェイトセットから出たスレッドがlock()実行時のオブジェクトロック（synchronizedのロック）の獲得待ちをしているとき、同じようにlock()実行時のオブジェクトロックの獲得待ちをしていた別のスレッドがオブジェクトロックを獲得してしまう場合がある。そのスレッドはlock()内の処理を終え、オブジェクトロックを解放し、lock()の後続の処理を進める。その後、ウェイトセットから出たスレッドがlock()実行時のオブジェクトロックを獲得したとき、isLockの検査をせずに処理を進めてしまうため、lock()〜unlock()間がクリティカルセクションにならず、競合状態になる可能性がある。

ということですね。

[ichiro200555]

また、synchronizedメソッドの中に同時に複数のスレッドが入れる件については、私がjdbの表示の読み方を間違えていたようです。その件については記事に追加しましたので、よろしければご確認ください。